Transcript Sliding - Winlab

ECE 544 Project3
Anup Mathur
Anusha Sheelavant
Prakhar Srivastava
Assumptions

Assumptions






End hosts can only connect to routers
Same content available at multiple end nodes
All routers have static IP addresses
Routing tables are updated periodically and on
events
Routers are allowed to send ACK’s for reliable
transmission
Router can connect to a maximum 5 other
routers and 254 hosts.
Address Scheme

Naming scheme and eventual address
scheme



.
Router- R1,R2 .. R255 -- A.B.Rid.255
End hosts- H1, H2 .. H255 -- A.B.Rid.Hid
Content- Filename Algorithm
File name algorithm
Hashing with variable data
Break the input into a sequence of small units (bits, byte, words,
etc.) and combine all the units b[1], b[2], …, b[m] sequentially, as
follows
S ← S0; // Initialize the state.
for k in 1, 2, ..., m do // Scan the input data units.
S ← F(S, b[k]); // Combine data unit k into the state.
return G(S, n) // Extract the hash value from the state.
If b[k] are single bits, then F(S,b) could be
if highbit(S) = 0
then return 2 * S + b
else return (2 * S + b) ^ P
Here highbit(S) - the most significant bit of S; the '*' operator denotes
unsigned integer multiplication with lost overflow. '^' is the bitwise
exclusive OR operation applied to words; and P is a suitable fixed word.
Content name

Content id:


Type: format ex: jpg,txt,mpeg
Hash table value
The content name : type-hashvalue
Bootstrapping and Discovery

Algorithm


Routers and end hosts boot up (Hello packet?)
Discovery



Routers discover other routers
Hosts discover their router
Packet Format
Bootstrapping




Starting from router 0, connect router 1
Handshake packets are sent – informing the other router
about the presence.
Handshake packet contains the mac address and router
id.
If no router id is maintained, then the router with lower
mac address becomes the network start router.
Assigning id :0(start) to itself and the next number in the
series of 5.
Bootstrapping- Contd.







If the router is already connected to a network, it will
allocate the next router its number based on the formula
= id*5 +[1-5].
If the router already has an id, no new id is allocated.
The routing table is built by using OSPF algorithm.
The Algorithm also conveys the content id.
If the router id is more than 255, then we use the 2nd
octet of the Ip address.
If two networks are to be connected, the mac address
defines the subnet and is assigned in the first octet of the
ip address.
Each router then stores the mac address it was given
and assigns itself the number given by the parent router.
Host id learning




Whenever a host connects to a router, the
router assigns the ip address to the host as
A.B.Rid.Hid
As a consequence each router can be
connected to only 255 hosts as the id 255
cannot be given.
The router maintains a table of the number of
hosts connected, its sequentially assigned
and the router maintains an alive table,
which is refreshed with a timer overflow.
Hello Packet
Identifie
r: HEL
My
Router
ID (2
bytes)
Device ID
(1 byte)
Guest Router
ID
(2 bytes)
MAC Address
(6 bytes)
Identifier: HEL: Indicates that it is a “Hello” packet.
ASN : assigning value
ACK : Acknowledgement
My Router ID: The ID of the sender.
Guest Router ID: The ID of the router which is being
assigned the ID.
Device ID: ID which indicates whether the device is a router
or a end Host.
MAC Address: MAC Address of the sender.
Baseline Algorithm

Content routing algorithm




Updating the content library
Searching content
Content Host selection
Data transfer
Updating the content library

Host broadcasts the packet with :









Content id
Update Identifier
Broadcast Address
#of hops
At each router we forward to all nodes other than the
source.
At each router we keep a copy of packet.
At each router we check if the number of hops is greater
than the stored packet, discard.
If the router already has a copy with greater number of
hops replace the copy and forward.
No acknowledgements are sent by the other host upon
receiving the update- hosts update their content library.
Searching Content

Host broadcasts the packet with









Content id
Search Identifier
Broadcast Address
#ofhops
At each router we forward to all nodes other than the
source.
At each router we keep a copy of packet.
At each router we check if the number of hops is greater
than the stored packet, discard.
If the router already has a copy with greater number of
hops replace the copy and forward.
The content provider sends an acknowledgement back
to the source.
Content Host selection




At each router the packet with the lesser
number of hops or smaller time is forwarded.
This removes the problem of cyclic
transmission in broadcasting and also helps
in selection of the acknowledgement.
The first acknowledgement received by the
host is the path/source is chosen.
If two packets come at the same time, the
acknowledgment with lower number of hops
is considered.
Data transfer




Once the host receives an acknowledgement, a
transfer packet is sent to the host selected.
The transfer packet should contain the
destination address where the content was
found.
Once the transfer packet is received, the content
host starts making packets of the content and
starts transmitting to the Receiving host.
In transit between the routers using Sliding
window(selective repeat) algorithm with a
window size of 4 packets and packet id of 3 bits
Data transfer

End of file: identifier tag is filled with EOF
after the last data packet is sent, this closes
the data transmission.
Data Transfer restrictions




No of hops> 255 discard.
Time to live for the copy is the N*x times the
time stamp difference, for simplicity we are using
the N=2.
In sliding window, if the acknowledgment is not
received for length of sliding window time, an
event for updating the routing table is made.
The time to live should be updated in the
Selective sliding window if the acknowledgment
is not received.
Data Transfer and Reliability

Message Forward




Multicast is not supported
Unicast: we need the destination address
Broadcast is supported for 255.255.255.255
ARQ Scheme

Hop-by-hop – Sliding Window
Sliding window uses selective request
scheme
Packet Format
Identifier
(4bytes)
Packet
id (1
byte)
Content id
(16 bytes)
Dest
Address (4
bytes)
Source Address (4
bytes)
Next hop (4
bytes)
No of
Hops
(2
bytes)
CRC (16
bytes)
Timer (8
bytes)
Time Stamp
DATA
Identifiers can be
1. SEA (Search)
2. UPD (Update)
3. ACK (Acknowledgement)
4. REQ (Request)
5. DAT (Data)
6. EOF (End of file)
Acknowledgement packet
Identifier:
ACK
Packe
t id (1
byte)
Content
id (16
bytes)
Dest
Address
(4 bytes)
Next hop (4
bytes)
No of
Hops
(2
bytes)
CRC (16
bytes)
Timer (8
bytes)
Source Address (4
bytes)
EOF packet
Identifier:
EOF
Packe
t id (1
byte)
Content
id (16
bytes)
Dest
Address
(4 bytes)
Next hop (4
bytes)
No of
Hops
(2
bytes)
CRC (16
bytes)
Timer (8
bytes)
Source Address (4
bytes)
Advantages and Disadvantages



Scalable to other networks using the first octet of
the IP address to define other networks if no
gateway
Latency – we have tried to maintain a fast hoh-hop
link state, thus using a sliding window ARQ.
Disadvantage: Does not support multicast
Appendix: Network Architecture

Refer to the following 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)
C2
H2
C3
C1
C2
R5
C3
H1
R1
R2
R3
R4
H3
Appendix: Network Architecture
Scenario 3: @host_H1: get (content_C1)
H1
H2
H3
C1
H4
C1
C2
C1
C3