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