Transcript group6
ECE 544 Project3
Amith V.S
Pavan Kulkarni
Suneet Dixit
Assumptions and Address Scheme
Assumptions
Routers do not fail in the life time of the Network.
Router to Router Links do not fail in the life time of the
Network.
IPs of all the Routers are preassigned.
Routers assign IPs to all the hosts in the Network.
Naming scheme and eventual address scheme
Edge routers are assigned IPs in the form X.X.n.0 where n
ranges from 1-254.
End hosts are assigned IPs in the form X.X.n.h where n is the
subnet number as assigned above and h ranges from 1-254
(since no. of hosts connected to network N < 255).
Content files are identified by their content ID ranging from 1254 (since no. of contents in the network K < 255).
Bootstrapping and Discovery
Modified Link State Algorithm - MLSF
Extends the functionality of Link state algorithm
to support the functionality of Content Provider
Network.
Initially each of the edge router sends the
contents that are available in their subnet along
with the distance vector to their adjacent routers.
After the convergence of the network each of the
router will have a table as shown below:
Time Stamp
Destination
Cost
Next Hop
Contents
Bootstrapping and Discovery
Discovery
Routers discover other routers with Hello Packets as
shown Below :
Router Source IP
Content Indicator Array
32 Bits
256 Bits
Edge routers discover their hosts and contents
present in them with Hello Packets as shown below
:
Host IP address
Content ID array
32 bits
Variable Length
Baseline Algorithm
Content routing algorithm
Once the Modified Distance Vector Algorithm – Routing
Table is established in each of the Router, the network is
now ready to respond to the get(ContentID) request.
How to route a content-request packet?
For each of the request issued by a host, the packets are
generated in following format:
Host Source IP
Flag
Content ID
32 Bits
8 bits
8 bits
The edge router receives this packet and converts it into
Router-Router request packet as shown below:
Host Source IP
32 Bits
Destination Router
IP
Flag
Content ID
32 Bits
8 Bits
8 Bits
Baseline Algorithm
How to route a content-request packet(cont..)?
This packets traverses the network through the shortest path
and reaches the edge router which is connected to the host
which has the content.
Each edge Router has a table mapping the Hosts IP address
to the contents the host has.
Referring to this table the packet is forwarded to the
appropriate host.
The host extracts the packet and gets the content ID
requested and generates the response packet as shown
Host
Destination IP
Flag
Content ID
Content
32 Bits
8 Bits
8 Bits
Upto 1466
Bytes
Baseline Algorithm
How the content is actually delivered?
While the request packet traverses through the network it
updates the bread crumbs table as shown below present in
each router :
Destination IP address
Next Hop IP address
32 Bits
32 Bits
The response packet refers the bread crumbs table to get
the next hop.
How network is updated when a host has a new content?
When a host has a new content, a new content packet is
generated as shown and forwarded to the edge router:
Host Source
IP
Flag
Content ID
Time Stamp
32 bits
8 bits
8 bits
32 Bits
Baseline Algorithm
How network is updated when a host has a new
content(cont..)?
The edge router gets this packet replaces the
host IP address with its own IP address and
broadcasts the packet to all the connecting
Routers.
This is continued as Spanning tree algorithm with
Time Stamp as the update parameter. Thus all
the router's MDVA table is updated.
How network is updated when a host deletes a
content(cont..)?
The same procedure is followed as above with
the flag set to delete content.
Data Transfer and Reliability
Message Forward
Host – Router is Unicast
Hello Packets and Update Packets between
Routers is Multicast
ARQ Scheme
Hop-by-hop acknowledgement scheme is being
used at every router
Advantages
Algorithm: A modified version of the Distance
Vector Table is being used which efficiently
calculates the shortest path to the host which has
the required contents
Scalability: The method employed can be
extended by using the unused bits of the IP
address making the system scalable
Latency: The method employs bread crumbs to
send data back to the requesting host. In this way
a low latency is maintained
Disadvantages
As Distance Vector Algorithm is a decentralized
routing algorithm, it takes time to converge the
table
Hop-by-hop acknowledgement scheme may
introduce latency
Appendix: Network Architecture
Example scenarios for analysis purposes:
Scenario 1: @host_H2: get (content_C3)
H2
C1
C2
R5
C3
H1
R1
R2
R3
R4
H3
Appendix: Network Architecture
Scenario 2: @host_H1: get (content_C2)
C
C 2
3
C
1
H
2
C
3
R5
H
1
R1
R2
R3
R4
C
2
H
3
Appendix: Network Architecture
Scenario 3: @host_H1: get (content_C1)
H1
H2
H3
C1
H4
C1
C2
C1
C3