Network Layer: The Most Complex Layer
Network Layer: The Most Complex Layer
Network Layer: The Most Complex Layer
Network
Biggest Challenges
Packet Switching
t1
t0
Network
Internal
Network Service
Messages
Messages
Segments
Transport
layer
Transport
layer
Network
service
Network
service
End
system
Network
layer
Network
layer
Network
layer
Network
layer
Data link
layer
Data link
layer
Data link
layer
Data link
layer
Physical
layer
Physical
layer
Physical
layer
Physical
layer
End
system
Connection-oriented :
Connection-setup required
Network layer must be informed about the new flow to be sent to the network
Network layer maintains state information about the flows it is handling
Network resources may be allocated
Connection-termination required
Complex than connectionless service
Datagram Transfer
Connection-Oriented (TCP)
Datagram operation
IP
Connection-Oriented
12
End system
4 3 21
21
2
1
1
12
2
21
Medium
A
1
2
12
2
1
Network
3
2
21
End system
123 4
Packet-Switching
Networks
Datagrams and Virtual Circuits
Connectionless
Connection-Oriented: Call setup control, Connection control
Backbone Network
Switch
Access Network
Message Switching
Message
Message
Message
Source
Message
Switches
Destination
Message switching
invented for telegraphy
Entire messages
multiplexed onto shared
lines, stored & forwarded
Headers for source &
destination addresses
Routing at message
switches
Connectionless
Switch 1
Switch 2
Destination
t
t
Delay
Minimum delay = 3 + 3T
source
BER=p=10-6
dest
BER=10-6
Pc (1 10 )
10 610 6
e 1 1 / 3
Approach 2: send 10
100-kbit packets
Probability packet arrives
correctly
5
Packet 1
Packet 1
Packet 2
Packet 2
Packet 2
t
1
t
1
Delay
t
1
t
1
t
1
Destination
t
L hops
3 hops
3 + 2(T/3) first bit received
Output
port
0785
1345
12
1566
2458
12
Hosts
Routers
In
Packet
Packet
Packet
Virtual circuit
Connection Setup
Connect
request
Connect
confirm
SW
1
Connect
request
Connect
confirm
SW
2
SW
n
Connect
request
Connect
confirm
Connect
request
CC
CR
CC
CR
Connect
confirm
3
1
Release
t
t
Output
port
Output
VCI
12
13
44
15
15
23
27
13
16
58
34
Cut-Through switching
Source
Switch 1
Switch 2
t
2
t
2
t
1
Destination
3
2
t
Minimum delay = 3 + T
Message:
L + LT
= L + (L 1) T + T
Packet
L + L P + (k 1) P = L + (L 1) P + T
Several
Packet-Switching
Networks
Routing in Packet Networks
3
6
4
Three
Node
(switch or router)
Which
is best?
Need
Need
Responsiveness to changes
Optimality
Robustness
Continues working under high load, congestion, faults, equipment failures, incorrect implementations
Simplicity
1
A
Host
VCI
Switch or router
5
5
2
2
6
8
6
3
C
Outgoing
Node VCI
3
2
3
3
A
1
A
5
Incoming
Node VCI
1
2
1
3
4
2
6
7
6
1
4
4
Outgoing
Node VCI
6
7
4
4
6
1
1
2
4
2
1
3
Node 6
Incoming
Node VCI
3
7
3
1
B
5
B
8
Outgoing
Node VCI
B
8
B
5
3
1
3
7
Node 4
Node 2
Incoming
Node VCI
C
6
4
3
Outgoing
Node VCI
4
3
C
6
Incoming
Node VCI
2
3
3
4
3
2
5
5
Outgoing
Node VCI
3
2
5
5
2
3
3
4
Node 5
Incoming
Node VCI
4
5
D
2
Outgoing
Node VCI
D
2
4
5
Destination
1
3
4
5
6
Node 2
Next node
1
1
4
5
5
Destination
1
2
4
5
6
Next node
1
4
4
6
6
Destination
1
2
3
5
6
Node 4
Next node
1
2
3
5
3
Node 6
Destination
Next node
1
3
2
5
3
3
4
3
5
5
Node 5
Destination
Next node
1
4
2
2
3
4
4
4
6
6
0011
0110
1001
1100
No
4
3
0001
0100
1011
1110
R1
0000
0111
1010
1
1
1
R2
0001
0100
1011
5
4
4
4
0011
0101
1000
1111
1000
1001
1010
1011
Prefix
4
3
0100
0101
0110
0111
R1
00
01
10
11
1
3
2
3
R2
00
01
10
11
3
4
3
5
5
1100
1101
1110
1111
Specialized Routing
Flooding
Deflection
Routing
Flooding
Send a packet to all nodes in a network
No routing tables available
Need to broadcast packet to all nodes (e.g. to
propagate link state information)
Approach
Send packet on all ports except one where it arrived
Exponential growth in packet transmissions
3
6
3
6
3
6
Limited Flooding
Time-to-Live
Deflection Routing
0,0
0,1
0,2
0,3
1,0
1,1
1,2
1,3
2,0
2,1
2,2
2,3
3,0
3,1
3,2
3,3
Tunnel from
last column to
first column or
vice versa
0,1
0,2
0,3
1,0
1,1
1,2
1,3
2,0
2,1
2,2
2,3
3,0
3,1
3,2
3,3
Packet-Switching
Networks
Shortest Path Routing
Routing Metrics
Means for measuring desirability of a path
Path Length = sum of costs or distances
Possible metrics
Distance Vector
Do you know the way to San Jose?
Sa
nJ
os
e
n
Sa
se
Jo
0
25
Distance Vector
Local Signpost
Direction
Distance
Routing Table
For each destination list:
Next Node
dest next dist
Distance
Table Synthesis
Neighbors exchange
table entries
Determine current best
next hop
Inform neighbors
Periodically
After changes
Shortest Path to SJ
Focus on how nodes find their shortest
path to a given destination node, i.e. SJ
Dj
Cij
i
Di
Sa
n
Jo
se
Sa
n
Jo
se
j'
Cij'
i
Di
Cij
Cij
j"
Dj
Dj"
Pick current
shortest path
3 Hops
From SJ
2 Hops
From SJ
1 Hop
From SJ
Sa
n
Jo
se
Hop-1 nodes
calculate current
(next hop, dist), &
send to neighbors
Bellman-Ford Algorithm
Minj
{ Cij + Dj }
Replace old (nj, Dj(d)) by new (nj*, Dj*(d)) if new next node or distance
Go to send step
Bellman-Ford Algorithm
Replace old (nj, Di(d)) by new (nj*, Dj*(d)) if new next node or distance
found
Go to send step
Iteration
Node 1
Node 2
Node 3
Node 4
Node 5
Initial
(-1, )
(-1, )
(-1, )
(-1, )
(-1, )
1
2
3
Table entry
@ node 3
for dest SJ
Table entry
@ node 1
for dest SJ
2
1
5
San
Jose
4
3
Iteration
Node 1
Node 2
Node 3
Node 4
Node 5
Initial
(-1, )
(-1, )
(-1, )
(-1, )
(-1, )
(-1, )
(-1, )
(6,1)
(-1, )
(6,2)
2
3
D3=D6+1
n3=6
D6=0
3 1
1
5
4
3
5
4
D5=D6+2
n5=6
D6=0
San
Jose
Iteration
Node 1
Node 2
Node 3
Node 4
Node 5
Initial
(-1, )
(-1, )
(-1, )
(-1, )
(-1, )
(-1, )
(-1, )
(6, 1)
(-1, )
(6,2)
(3,3)
(5,6)
(6, 1)
(3,3)
(6,2)
1
5
4
3
San
Jose
Iteration
Node 1
Node 2
Node 3
Node 4
Node 5
Initial
(-1, )
(-1, )
(-1, )
(-1, )
(-1, )
(-1, )
(-1, )
(6, 1)
(-1, )
(6,2)
(3,3)
(5,6)
(6, 1)
(3,3)
(6,2)
(3,3)
(4,4)
(6, 1)
(3,3)
(6,2)
1
5
4
3
6 4
San
Jose
Iteration
Node 1
Node 2
Node 3
Node 4
Node 5
Initial
(3,3)
(4,4)
(6, 1)
(3,3)
(6,2)
(3,3)
(4,4)
(4, 5)
(3,3)
(6,2)
2
3
1 5
1
5
4
3
San
Jose
Iteration
Node 1
Node 2
Node 3
Node 4
Node 5
Initial
(3,3)
(4,4)
(6, 1)
(3,3)
(6,2)
(3,3)
(4,4)
(4, 5)
(3,3)
(6,2)
(3,7)
(4,4)
(4, 5)
(5,5)
(6,2)
37
1
5
53
San
Jose
Iteration
Node 1
Node 2
Node 3
Node 4
Node 5
Initial
(3,3)
(4,4)
(6, 1)
(3,3)
(6,2)
(3,3)
(4,4)
(4, 5)
(3,3)
(6,2)
(3,7)
(4,4)
(4, 5)
(5,5)
(6,2)
(3,7)
(4,6)
(4, 7)
(5,5)
(6,2)
5 7
1
5
46
5
4
San
Jose
Iteration
Node 1
Node 2
Node 3
Node 4
Node 5
(3,3)
(4,4)
(4, 5)
(3,3)
(6,2)
(3,7)
(4,4)
(4, 5)
(2,5)
(6,2)
(3,7)
(4,6)
(4, 7)
(5,5)
(6,2)
(2,9)
(4,6)
(4, 7)
(5,5)
(6,2)
79
1
5
7
1
4
3
San
Jose
(b)
1
1
2
2
1
1
3
3
Update
Node 1
Node 2
Node 3
Before break
(2,3)
(3,2)
(4, 1)
After break
(2,3)
(3,2)
(2,3)
(2,3)
(3,4)
(2,3)
(2,5)
(3,4)
(2,5)
(2,5)
(3,6)
(2,5)
(2,7)
(3,6)
(2,7)
(2,7)
(3,8)
(2,7)
Poisoned Reverse
(b)
1
1
2
2
1
1
3
3
1
X
4
4
Update
Node 1
Node 2
Node 3
Before break
(2, 3)
(3, 2)
(4, 1)
After break
(2, 3)
(3, 2)
(-1, )
(2, 3)
(-1, )
(-1, )
(-1, )
(-1, )
(-1, )
Link-State Algorithm
Each source node gets a map of all nodes and link metrics (link
state) of the entire network
Find the shortest path on the map from the source node to all
destination nodes
IDs
i
Distances to its neighbors: {Cij | j Ni}
w
'
s
x
w
"
z'
x'
Dijkstras algorithm
Go to Step A
5
4
1
2
4
2
5
4
3
1
2
3
2
2
5
Iteration
D2
D3
D4
D5
D6
Initial
{1}
{1,3}
{1,2,3}
{1,2,3,6}
{1,2,3,4,6}
{1,2,3,4,5,6}
2
2
5
2
4
2
4
4
4
2
1
5
3
2
4
Reaction to Failure
If a link fails,
Router sets link distance to infinity & floods the
network with an update packet
All routers immediately update their link database &
recalculate their shortest paths
Recovery very quick
But watch out for old update messages
Add time stamp or sequence # to each update
message
Check whether each received update message is new
If new, add it to database and broadcast
If older, send update message on arriving link
loopless convergence
Support for precise metrics, and multiple
metrics if necessary (throughput, delay, cost,
reliability)
Support for multiple paths to a destination
algorithm
Source Routing
Example
3,6,B
1,3,6,B
6,B
3
6
A
4
Source host
2
Destination host