Transcript slides - Winlab

ECE 544 Project3
Viet Nguyen
Jianqing Liu
Yaqin Tang
Assumptions and Address Scheme

Assumptions




Each host can only connect to one router
Same content available at multiple end nodes
If two routers are connected, cost = 1
Naming scheme and eventual address scheme


Routers and end hosts: IP Address
Contents: ID from 0 to 255
Bootstrapping and Discovery

Algorithm


Routers boot up
- Neighbor router receive broadcast message,
send back their IP addresses
- Routers add its neighbors to routing table
Hosts boot up
- Broadcast DHCP requesting packet to
255.255.255.255
- Routers reply with info about default gateway
Bootstrapping and Discovery

Discovery


Routers discover other routers
- Sending broadcast message
- Add neighbors info into routing table step by step
Hosts discover their default router
- Through DHCP request
Bootstrapping and Discovery

Packet Format
- Router boot up packet
Type
Packet Length
Cost
Source Router’s IP Address
Neighbor Router’s IP Address
Bootstrapping and Discovery

Packet Format
- Host boot up packet
Type
Packet Length
TTL
yiaddr (Default Router’s IP Address)
chaddr (16 bytes, Host’s Ethernet Address)
Contents Advertisement


A host periodically sends an advertisement
message to tell its router about its contents
After receiving advertisement message, the
router stores both the host’s IP address and
its contents into its routing table
C1
C2
H1
R1
Destination
Cost
Next Hop
H1
1
H1
C1
1
H1
C2
1
H1
TTL
Content Advertisement packet
Packet type
Message Length
Number of
Contents
Host’s IP Address
Content ID #1
Content ID #2
….
…
Link-state Advertisement
packet
Packet type
Message Length
LS Age
Advertising router’s IP Address
LS sequence number
Number of neighbor routers
Neighbor node’s IP Address #1
Neighbor node’s IP Address #2
…
Neighbor node’s IP Address #n
Number of hosts
Host IP Address #1
Host IP Address #2
…
Host IP Address #3
NumOfContents
Content ID #1
Content ID #2
…
Information at each router



Link state table
Neighbors table
Routing table
Link state table (for each router)
Router’s Number
IP
of
neighbor
routers
List of
neighbo
r
routers
Number
of hosts
List of
hosts
Number of
contents
List of
contents
R5
1
R2
1
H2
1
C2
R2
2
R1, R5
0
-
0
-
TTL
@R1
H2
Each router store Link
state of OTHER router!
C2
C1
R5
H1
R1
R2
Neighbor table (for each router)
Number of
neighbor
routers
List of
neighbor
routers
Number
of hosts
List of
hosts
Number
of
contents
List of
contents
1
R2
1
H1
1
C1
@R1
H2
C2
C1
R5
H1
R1
R2
Routing table



Each router maintains its own routing table
Calculated from Link state table and neighbor
table
As each host can be either content requester
or content provider, routing is based on both
content identifiers and host addresses
C1
Destination
Cost
Next Hop
C2
@R1
H1
R1
H1
1
H1
C1
1
H1
C2
1
H1
Routing Protocol




We use link-state protocol with reduced
message format (Link-state packet - LSP)
Routers flood LSPs to all other routers
Once a router has a copy of the LSP from
every other router, it computes a complete
map for the topology of the network, and from
this map decide the best routes to each
destination
Algorithm: Dijkstra’s shortest-path algorithm
Routing Protocol (2)



LSP also carries a time to live. A node always
decrements the TTL of a newly received LSP
before flooding it to its neighbors.
It also “ages” the LSP while it is stored in the
node
When the TTL reaches 0, the node refloods
the LSP with a TTL of 0, which is interpreted
by all the nodes in the networks as a signal to
delete that LSP
Routing protocol (3)


Each router sends “hello” packet to its
immediate neighbors at defined intervals.
If a sufficiently long time passes without
receipt of a “hello” from a neighbor, the link
will be declared down, and a new LSP will be
generated to reflect this fact.
Router - ‘Hello’ Packet

Send to neighbor routers to say “I am alive”
Packet type
HELLO
Message Length
Router’s IP Address
Option
Routing protocol (4)

Only generate LSP if:



Timer expires
Change in topology (link dies, a neighbor router
dies)
A change in LSP table or neighbor table
causes a router to recalculate the routing
table!
Host: REQUEST packet format
Packet type
(REQUEST)
Content ID
SeqNum
Option
Requester’s IP Address
Content provider’s IP Address (=0)
SeqNum: used for supporting resume download from different content provider
How to route a content-request
packet (Content discovery)


@host_H1: get (content_C3)
H1 sends request to its router R1
C1
C2
C3
H1
R1
get(C3)
R2
R3
H3
How to route a content-request
packet (Content discovery)



@host_H1: get (content_C3)
R1 looks up its routing table for next hop
Destination Cost Next Hop
to send
Routing table @ R1: …
C3
3
R2
C1
C2
C3
H1
R1
get(C3)
R2
R3
H3
How to route a content-request
packet (Content discovery)


@host_H1: get (content_C3)
Routing table @ R2: Destination
Cost
Next Hop
2
R3
…
C3
C1
C2
C3
H1
R1
R2
get(C3)
R3
H3
How to route a content-request
packet (Content discovery)


@host_H1: get (content_C3)
Routing table @ R3: Destination
Cost
Next Hop
1
H3
…
C3
C1
C2
C3
H1
R1
R2
R3
get(C3)
H3
How to route a content-request
packet (Content discovery)


@host_H1: get (content_C3)
Request packet arrived at H3 !
C1
C2
C3
H1
Arrived
R1
R2
R3
H3
get(C3)
Delivering data

After request packet arrived, the host with the
needed content start data transfer process.
C1
C2
C3
H1
R1
R2
R3
Data transfer
H3
Delivering data: Error


If during transfer, the connection dies (router
down, link dies, etc.), both the provider and
the requester must be able to detect!
Proposed method: set limitation on how many
times we send the same packets (same
sequence number)

After detecting dead connection, discard this
connection: requester does CONTENT
DISCOVERY again, provider STOPS transferring
data
Delivering data: Error (2)

After retrieving IP address of new content
provider, the requester RESUME from the
last sequence number

Append to the file received from the last provider
Data Transfer and Reliability

Message Forward



Unicast: ACK & Data transmission
Broadcast: boot up & update file ID info
DATA Packet Format
Type
File ID
SeqNum
TTL
Source Address
Destination Address
Payload (file to be transmitted)
- TTL: time to live
- SeqNum: sequence #
- Offset: offset regard to fragmented file
Data Transfer and Reliability

Message Forward

ACK Packet Format
Type
File ID
SeqNum
TTL
Source Address
(File receiver’s IP Address)
Destination Address
(File sender’s IP Address)
Data Transfer and Reliability

ARQ Scheme


End-to-end
Routers know the cost of the entire network
Selective-repeat
- Transmit continuously, no waiting
- Receiver ACKs all successfully received packets
- Sender only retransmits unACKed packets when
their timers expire
- buffer needed at both transmitter and receiver
Data Transfer and Reliability

Selectiverepeat
Advantages and Disadvantages
Aspects
Good or not
Scalability
✔
Latency
✔
Bandwidth
✗
Reliability
✔
Scenario 1:

@host_H2: get (content_C3)
H2
C1
C2
R5
C3
H1
R1
get(C3)
R2
R3
R4
H3
Scenario 1:

@host_H2: get (content_C3)
@R1:
Destination
Cost
Next Hop
C3
4
R2
H2
C1
C2
R5
C3
H1
R1
get(C3)
R2
R3
R4
H3
Scenario 1:

@host_H2: get (content_C3)
@R2:
Destination
Cost
Next Hop
C3
3
R3
H2
C1
C2
R5
C3
H1
R1
R2
get(C3)
R3
R4
H3
Scenario 1:

@host_H2: get (content_C3)
@R3:
Destination
Cost
Next Hop
C3
2
R4
H2
C1
C2
R5
C3
H1
R1
R2
R3
get(C3)
R4
H3
Scenario 1:

@host_H2: get (content_C3)
@R4:
Destination
Cost
Next Hop
C3
1
H3
H2
C1
C2
R5
C3
H1
R1
R2
R3
R4
get(C3)
H3
Scenario 1:

@host_H2: get (content_C3)
H2
C1
C2
R5
C3
H1
R1
R2
R3
R4
H3
get(C3)
Arrived
Scenario 1:

@host_H2: get (content_C3)
H2
C1
C2
R5
C3
H1
R1
R2
R3
Data transfer
R4
H3
Appendix: Network Architecture
Scenario 2: @host_H1: get (content_C2)
C2
H2
C3
C1
C2
R5
C3
H1
R1
R2
R3
R4
- H1 send request for C2 to default router R1
- R1 choose shortest path, set DstAdrr as H2
- When H2 receives request, ACK back
- Connection between H1 & H2 established
H3
Appendix: Network Architecture
Scenario 2: @host_H1: get (content_C2)
C2
H2
C3
C1
C2
R5
C3
H1
R1
R2
R3
R4
H3
- H2 prepare fragmented file
- Begin file transmission
- Selective-repeat mechanism to ensure delivery
Appendix: Network Architecture
Scenario 3: @host_H1: get (content_C1)
- Basic mechanism is the same as discussed
H1
H2
H3
C1
H4
C1
C2
C1
C3
Appendix: Network Architecture
Scenario 3: @host_H1: get (content_C1)
- Link to H2 die:
- H1 send 10 ACKs for the same packet
- H1 gives up and request for C1 again starting with
the smallest sequence number lost