Transcript Part I: Introduction

application
transport
network
data link
physical
The Network
Layer &
Routing
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
application
transport
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
application
transport
network
data link
physical
The network layer moves transport layer segments
from host to host in the network, to deliver them to
their destination. This layer involves each and every
host and router in the network. We will study the
key principles and algorithms of routing, with a focus
on the Internet Protocol (IP) service model.
4: Network Layer
4a-1
Network layer functions
 transport packet from
sending to receiving hosts
 network layer protocols in
every host, router
three important functions:
 path determination: route
taken by packets from source
to destination - routing
algorithms
 switching: move packets from
router’s input to appropriate
router output
 call setup: some network
architectures require router
call setup along path before
data flows (what types?)
application
transport
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
application
transport
network
data link
physical
4: Network Layer
4a-2
Virtual circuits
the source-to-destination path behaves much like a
telephone circuit


performance-wise
network actions along source-to-destination path
 call setup, teardown for each call
before data can flow
 each packet carries VC identifier (not destination host ID)

every router/switch on source-destination path maintains a
“state” for each passing connection

Recall: transport-layer connection only involved two end
systems
 link and router resources (bandwidth, buffers) may be
dedicated to the VC


to get circuit-like performance
but… what about start-up delay?
4: Network Layer
4a-3
Virtual circuits: signaling protocols
 used to setup, maintain and teardown the VC
 used in ATM, frame-relay and X.25
 not used in the Internet (why?)
application
transport 5. Data flow begins
network 4. Call connected
data link 1. Initiate call
physical
6. Receive data application
3. Accept call
2. incoming call
transport
network
data link
physical
4: Network Layer
4a-4
Datagram networks:
the Internet model
 no call setup at network layer
 routers: do not maintain state for the end-to-end
connections

no network-level concept of a “connection”
 packets are typically routed using only destination
host ID which is carried in the packet

packets between same source-destination pair may take
different paths
application
transport
network
data link 1. Send data
physical
application
transport
network
2. Receive data
data link
physical
4: Network Layer
4a-5
Routing
Routing protocol
Goal: determine “good” path
(sequence of routers) thru
network from source to dest.
Graph abstraction for
routing algorithms:
 graph nodes are
routers
 graph edges are
physical links

link cost: delay, $ cost,
or congestion level
5
2
A
B
2
1
D
3
C
3
1
5
F
1
E
2
 “good” path:
 typically means minimum
cost path
 other def’s possible
4: Network Layer
4a-6
Routing Algorithm classification
Global or decentralized
cost information?
Global:
 all routers have complete
topology & link cost info
 “link state” algorithms
Decentralized:
 router knows physicallyconnected neighbors, link
costs to route to neighbors
 iterative process of
computation & exchange of
info with neighbors
 “distance vector” algorithms
Static or dynamic?
Static:
 routes change slowly over
time
Dynamic:
 routes change more quickly
 periodic algorithmdriven updates
 responsive to link cost
changes
5
A
2
1
B
2
D
3
C
3
1
5
F
1
E
2
4: Network Layer
4a-7
4: Network Layer
4a-8
4: Network Layer
4a-9
4: Network Layer 4a-10
4: Network Layer 4a-11
4: Network Layer 4a-12
4: Network Layer 4a-13
Dijsktra’s Algorithm
1 Initialization:
2 N = {A}
// Source node is “A”
5
3 for all nodes v
3
4
if v adjacent to A
B
2
5
then D(v) = c(A,v)
A
2
3
6
else D(v) = infinity
1
D
7
1
8 Loop
9 find w not in N such that D(w) is a minimum
10 add w to N
11 update D(v) for all v adjacent to w and not in N:
12
D(v) = min( D(v), D(w) + c(w,v) )
13 /* new cost to v is either old cost to v or known
14 shortest path cost to w plus cost from w to v */
15 until all nodes in N
C
5
F
1
E
2
4: Network Layer 4a-14
Dijkstra’s algorithm: example
Step
0
1
2
3
4
5
start N
A
AD
ADE
ADEB
ADEBC
ADEBCF
D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F)
2,A
1,A
5,A
infinity
infinity
2,A
4,D
2,D
infinity
2,A
3,E
4,E
3,E
4,E
4,E
5
2
A
B
2
1
D
3
C
3
1
5
F
1
E
2
4: Network Layer 4a-15
Distance Vector Routing Algorithm
iterative:
 continues until no
nodes exchange info.
 self-terminating: no
“signal” to stop
asynchronous:
 nodes need
not
exchange info/iterate
in lock step!
distributed:
 each node
communicates only with
directly-attached
neighbors
Distance Table data structure
 each node has its own
 row for each possible destination
 column for each directly-
attached neighbor to node
 example: in node X, for
destination Y via neighbor Z:
DX(Y,Z)
distance from X to
= Y, via Z as next hop
Z
= c(X,Z) + minw {D (Y,w)}
4: Network Layer 4a-16
Distance Table: example
7
A
B
1
C
E
cost to destination via
D ()
A
B
D
A
1
14
5
B
7
8
5
C
6
9
4
D
4
11
2
2
8
1
E
2
D
E
D (C,D) = c(E,D) + min {DD(C,w)}
= 2+2 = 4
w
E
D (A,D) = c(E,D) + min {DD(A,w)}
= 2+3 = 5
E
D (A,B)
w
loop back through E!
= c(E,B) + min {D B(A,w)}
w
= 8+6 = 14
loop back through E!
4: Network Layer 4a-17
Distance table gives routing table
E
cost to destination via
Outgoing link
D ()
A
B
D
E
A
1
14
5
A
A,1
B
7
8
5
B
D,5
C
6
9
4
C
D,4
D
4
11
2
D
D,2
Distance table
to use, cost
Routing table
>> next link, cost
4: Network Layer 4a-18
Distance Vector Algorithm
(Bellman-Ford):
At all nodes, X:
1 Initialization:
2 for all adjacent nodes v:
3
D X(*,v) = infinity
/* the * operator means "for all rows" */
4
D X(v,v) = c(X,v)
5 for all destinations, y
6
send min D X(y,w) to each neighbor /* w over all X's neighbors */
w
4: Network Layer 4a-19
Distance Vector Algorithm (cont.):
8 loop
9 wait (until I see a link cost change to neighbor V
10
or until I receive update from neighbor V)
11
12 if (c(X,V) changes by d)
13 /* change cost to all dest's via neighbor v by d */
14 /* note: d could be positive or negative */
15 for all destinations y: D X(y,V) = D X(y,V) + d
16
17 else if (update received from V wrt destination Y)
18 /* shortest path from V to some Y has changed */
19 /* V has sent a new value for its min DV(Y,w) */
w
20 /* call this received new value "newval" */
X
21 for the single destination y: D(Y,V)
= c(X,V) + newval
22
X
23 if we have a new min D (Y,w)
for any destination Y
w
X
24
send new value of min D (Y,w)
to all neighbors
w
25
4: Network Layer
26 forever
4a-20
Comparison of LS and DV algorithms
Message complexity
 LS: with n nodes, E links,
O(nE) msgs sent/broadcast
 DV: exchange between
neighbors only
 convergence time varies
Speed of Convergence
 LS: O(n2) algorithm requires
O(nE) msgs
 may have oscillations
 DV: convergence time varies
 may be routing loops
 count-to-infinity problem
• poisoned reverse is
sometimes successful
Robustness: what happens
if router malfunctions?
LS:


node can advertise
incorrect link cost
each node computes only
its own table
DV:


DV node can advertise
incorrect path cost
each node’s table used by
others
• errors propagate
through the network
4: Network Layer 4a-21