9.Routing
COMP 3331/9331:
Computer Networks and
Applications
Week 8
Network Layer: Data Plane + Control Plane
(Routing)
Chapter 4: Section 4.3
Chapter 5: Section 5.1 – 5.2, 5.6
1
4.1 Overview of Network layer
§ data plane
§ control plane
4.2 What’s inside a router
4.3 IP: Internet Protocol
§ datagram format
§ fragmentation
§ IPv4 addressing
§ network address translation
§ IPv6
Network Layer, data plane: outline
2
IPv6: motivation
v initial motivation: 32-bit address space soon
to be completely allocated.
v additional motivation:
§ header format helps speed
processing/forwarding
§ header changes to facilitate QoS
IPv6 datagram format:
§ fixed-length 40-byte header
§ no fragmentation allowed
3
https://www.google.com/intl/en/ipv6/statistics.html
IPv6 datagram format
priority: identify priority among datagrams in flow (traffic class)
flow Label: identify datagrams in same “flow.”
(concept of“flow” not well defined).
next header: identify upper layer protocol for data
data
destination address
(128 bits)
source address
(128 bits)
payload len next hdr hop limit
flow labelpriver
32 bits
4
Other changes from IPv4
v checksum: removed entirely to reduce processing
time at each hop
v options: allowed, but outside of header, indicated
by “Next Header” field
v ICMPv6: new version of ICMP
§ additional message types, e.g., “Packet Too Big”
§ multicast group management functions
5
Transition from IPv4 to IPv6
v not all routers can be upgraded
simultaneously
§ no “flag days”
§ how will network operate with mixed IPv4 and IPv6
routers?
v tunneling: IPv6 datagram carried as payload
in IPv4 datagram among IPv4 routers
IPv4 source, dest addr
IPv4 header fields
IPv4 datagram
IPv6 datagram
IPv4 payload
UDP/TCP payload
IPv6 source dest addr
IPv6 header fields
6
Tunneling (IPv6 over IPv4)
physical view:
IPv4 IPv4
A B
IPv6 IPv6
E
IPv6 IPv6
FC D
logical view:
IPv4 tunnel
connecting IPv6 routers E
IPv6 IPv6
FA B
IPv6 IPv6
7
flow: X
src: A
dest: F
data
A-to-B:
IPv6
Flow: X
Src: A
Dest: F
data
src:B
dest: E
B-to-C:
IPv6 inside
IPv4
E-to-F:
IPv6
flow: X
src: A
dest: F
data
B-to-C:
IPv6 inside
IPv4
Flow: X
Src: A
Dest: F
data
src:B
dest: E
physical view:
A B
IPv6 IPv6
E
IPv6 IPv6
FC D
logical view:
IPv4 tunnel
connecting IPv6 routers E
IPv6 IPv6
FA B
IPv6 IPv6
Tunneling (IPv6 over IPv4)
IPv4 IPv4
8
flow: X
src: A
dest: F
data
A-to-B:
IPv4
Flow: X
Src: A
Dest: F
data
src:B
dest: E
B-to-C:
IPv4 inside
IPv4
E-to-F:
IPv4
flow: X
src: A
dest: F
data
B-to-C:
IPv4 inside
IPv4
Flow: X
Src: A
Dest: F
data
src:B
dest: E
physical view:
A B
IPv4 IPv4
E
IPv4 IPv4
FC D
logical view:
IPv4 tunnel
connecting IPv4 routers E
IPv4 IPv4
FA B
IPv4 IPv4
Tunneling (IPv4 over IPv4)
IPv4 IPv4
9
Used in VPNs
5.1 introduction
5.2 routing protocols
v link state
v distance vector
v hierarchical routing
5.6 ICMP: The Internet
Control Message
Protocol
Network layer, control plane: outline
Self study (not on
exam)
10
Network-layer functions
v forwarding: move packets
from router’s input to
appropriate router output
data plane
control plane
Two approaches to structuring network control plane:
§ per-router control (traditional)
§ logically centralized control (software defined networking)
Recall: two network-layer functions:
§ routing: determine route
taken by packets from source
to destination
11
Per-router control plane
Routing
Algorithm
Individual routing algorithm components in each and every
router interact with each other in control plane to compute
forwarding tables
data
plane
control
plane
4.1 • OVERVIEW OF NETWORK LAYER 309
tables. In this example, a routing algorithm runs in each and every router and both
forwarding and routing functions are contained within a router. As we’ll see in Sec-
tions 5.3 and 5.4, the routing algorithm function in one router communicates with
the routing algorithm function in other routers to compute the values for its forward-
ing table. How is this communication performed? By exchanging routing messages
containing routing information according to a routing protocol! We’ll cover routing
algorithms and protocols in Sections 5.2 through 5.4.
The distinct and different purposes of the forwarding and routing functions can
be further illustrated by considering the hypothetical (and unrealistic, but technically
feasible) case of a network in which all forwarding tables are configured directly by
human network operators physically present at the routers. In this case, no routing
protocols would be required! Of course, the human operators would need to interact
with each other to ensure that the forwarding tables were configured in such a way
that packets reached their intended destinations. It’s also likely that human configu-
ration would be more error-prone and much slower to respond to changes in the net-
work topology than a routing protocol. We’re thus fortunate that all networks have
both a forwarding and a routing function!
Values in arriving
packet’s header
1
2
3
Local forwarding
table
header
0100
0110
0111
1001
1101
3
2
2
1
output
Control plane
Data plane
Routing algorithm
Figure 4.2 ! Routing algorithms determine values in forward tables
M04_KURO4140_07_SE_C04.indd 309 11/02/16 3:14 PM
12
data
plane
control
plane
Logically centralized control plane
A distinct (typically remote) controller interacts with local
control agents (CAs) in routers to compute forwarding tables
Remote Controller
CA
CA CA CA CA
13
5.1 introduction
5.2 routing protocols
v link state
v distance vector
v Hierarchical routing
5.6 ICMP: The Internet
Control Message
Protocol
Network layer, control plane: outline
14
Context and Terminology
“End hosts”
“Clients”, “Users”
“End points”
“Interior Routers”
“Border Routers”
“Autonomous System (AS)” or “Domain”
Region of a network under a single administrative entity
“Route” or “Path”
15
Internet Routing
v Internet Routing works at two levels
v Each AS runs an intra-domain routing protocol that
establishes routes within its domain
§ AS — region of network under a single administrative entity
§ Link State, e.g., Open Shortest Path First (OSPF)
§ Distance Vector, e.g., Routing Information Protocol (RIP)
v ASes participate in an inter-domain routing protocol that
establishes routes between domains
§ Path Vector, e.g., Border Gateway Protocol (BGP)
16
u
yx
wv
z
2
2
1
3
1
1
2
5
3
5
graph: G = (N,E)
N = set of routers = { u, v, w, x, y, z }
E = set of links ={ (u,v), (u,x), (u,w), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }
Graph abstraction
17
Graph abstraction: costs
u
yx
wv
z
2
2
1
3
1
1
2
5
3
5 c(x,x’) = cost of link (x,x’)
e.g., c(w,z) = 5
cost of path (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp)
key question: what is the least-cost path between u and z ?
routing algorithm: algorithm that finds that least cost path
18
Link Cost
v Typically simple: all links are equal
v Least-cost paths => shortest paths (hop count)
v Network operators add policy exceptions
§ Lower operational costs
§ Peering agreements
§ Security concerns
19
5.1 introduction
5.2 routing protocols
v link state
v distance vector
v hierarchical routing
5.6 ICMP: The Internet
Control Message
Protocol
Network layer, control plane: outline
20
Routing algorithm classes
Link State (Global)
• Routers maintain cost of each
link in the network
• Connectivity/cost changes
flooded to all routers
• Converges quickly (less
inconsistency, looping, etc.)
• Limited network sizes
Distance Vector (Decentralised)
• Routers maintain next hop &
cost of each destination.
• Connectivity/cost changes
iteratively propagate form
neighbour to neighbour
• Requires multiple rounds to
converge
• Scales to large networks
21
Link State Routing
v Each node maintains its local “link state” (LS)
§ i.e., a list of its directly attached links and their costs
(R1,R2, 2)
(R1,R4, 3)
(R1,R5, 2)
Host A
Host B
Host E
Host D
Host C
R1 R2
R3
R4
R5
R7R6
22
2
2
3
Link State Routing
v Each node maintains its local “link state” (LS)
v Each node floods its local link state
§ on receiving a new LS message, a router forwards the message
to all its neighbors other than the one it received the message from
Host A
Host B
Host E
Host D
Host C
R1 R2
R3
R4
R5
R7R6
(R1,R2, 2)
(R1, R4, 3)
(R1, R5, 2)
(R1,R2, 2)
(R1, R4, 3)
(R1, R5, 2)
(R1,R2, 2)
(R1, R4, 3)
(R1, R5, 2)
(R1,R2, 2)
(R1, R4, 3)
(R1, R5, 2)
(R1,R2, 2)
(R1, R4, 3)
(R1, R5, 2)
(R1,R2, 2)
(R1, R4, 3)
(R1, R5, 2)
(R1,R2, 2)
(R1, R4, 3)
(R1, R5, 2)
(R1,R2, 2)
(R1, R4, 3)
(R1, R5, 2)
(R1,R2, 2)
(R1, R4, 3)
(R1, R5, 2)
(R1,R2, 2)
(R1, R4, 3)
(R1, R5, 2)
23
Flooding LSAs
v Routers transmit Link State Advertisement (LSA)
on links
§ A neighbouring router forwards out on all links except
incoming
§ Keep a copy locally; don’t forward previously-seen LSAs
v Challenges
§ Packet loss
§ Out of order arrival
v Solutions
§ Acknowledgements and retransmissions
§ Sequence numbers
§ Time-to-live for each packet
24
Link State Routing
v Each node maintains its local “link state” (LS)
v Each node floods its local link state
v Eventually, each node learns the entire network topology
§ Can use Dijkstra’s to compute the shortest paths between nodes
Host A
Host B
Host E
Host D
Host C
R1 R2
R3
R4
R5
R7R6
A
B
E
D
C
A
B
E
D
C
A
B
E
D
C
A
B
E
D
C
A
B
E
D
C
A
B
E
D
C
A
B
E
D
C
25
A Link-State Routing Algorithm
Dijkstra’s algorithm
v net topology, link costs
known to all nodes
§ accomplished via “link state
broadcast”
§ all nodes have same info
v computes least cost paths
from one node (‘source”)
to all other nodes
§ gives forwarding table for
that node
v iterative: after k
iterations, know least cost
path to k dest.’s
notation:
v c(x,y): link cost from
node x to y; = ∞ if not
direct neighbors
v D(v): current value of
cost of path from source
to dest. v
v p(v): predecessor node
along path from source to
v
v N’: set of nodes whose
least cost path definitively
known
26
Dijsktra’s Algorithm
1 Initialization:
2 N’ = {u}
3 for all nodes v
4 if v adjacent to u
5 then D(v) = c(u,v)
6 else D(v) = ∞
7
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’
27
Example: Dijkstra’s Algorithm
Step
0
1
2
3
4
5
Set N’
A
D(B),p(B)
2,A
D(C),p(C)
5,A
D(D),p(D)
1,A
D(E),p(E) D(F),p(F)
A
ED
CB
F
2
2
1
3
1
1
2
5
3
5
∞ ∞
1 Initialization:
2 N’ = {A};
3 for all nodes v
4 if v adjacent to A
5 then D(v) = c(A,v);
6 else D(v) = ;
…
∞
28
Example: Dijkstra’s Algorithm
Step
0
1
2
3
4
5
Set N’
A
D(B),p(B)
2,A
D(C),p(C)
5,A
…
8 Loop
9 find w not in N’ s.t. 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 If D(w) + c(w,v) < D(v) then
13 D(v) = D(w) + c(w,v); p(v) = w;
14 until all nodes in N’;
A
ED
CB
F
2
2
1
3
1
1
2
5
3
5
D(D),p(D)
1,A
D(E),p(E) D(F),p(F)
∞ ∞
29
Example: Dijkstra’s Algorithm
Step
0
1
2
3
4
5
Set N’
A
AD
D(B),p(B)
2,A
D(C),p(C)
5,A
D(D),p(D)
1,A
D(E),p(E) D(F),p(F)
A
ED
CB
F
2
2
1
3
1
1
2
5
3
5
∞ ∞
…
8 Loop
9 find w not in N’ s.t. 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 If D(w) + c(w,v) < D(v) then
13 D(v) = D(w) + c(w,v); p(v) = w;
14 until all nodes in N’;
30
Example: Dijkstra’s Algorithm
Step
0
1
2
3
4
5
Set N’
A
AD
D(B),p(B)
2,A
D(C),p(C)
5,A
4,D
D(D),p(D)
1,A
D(E),p(E)
2,D
D(F),p(F)
A
ED
CB
F
2
2
1
3
1
1
2
5
3
5
∞ ∞
…
8 Loop
9 find w not in N’ s.t. 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 If D(w) + c(w,v) < D(v) then
13 D(v) = D(w) + c(w,v); p(v) = w;
14 until all nodes in N’;
2, A
31
Example: Dijkstra’s Algorithm
Step
0
1
2
3
4
5
Set N’
A
AD
ADE
D(B),p(B)
2,A
D(C),p(C)
5,A
4,D
3,E
D(D),p(D)
1,A
D(E),p(E)
2,D
D(F),p(F)
4,E
∞ ∞
A
ED
CB
F
2
2
1
3
1
1
2
5
3
5
…
8 Loop
9 find w not in N’ s.t. 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 If D(w) + c(w,v) < D(v) then
13 D(v) = D(w) + c(w,v); p(v) = w;
14 until all nodes in N’;
2, A
2, A
32
Example: Dijkstra’s Algorithm
Step
0
1
2
3
4
5
Set N’
A
AD
ADE
ADEB
D(B),p(B)
2,A
D(C),p(C)
5,A
4,D
3,E
D(D),p(D)
1,A
D(E),p(E)
2,D
D(F),p(F)
4,E
∞ ∞
A
ED
CB
F
2
2
1
3
1
1
2
5
3
5
…
8 Loop
9 find w not in N’ s.t. 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 If D(w) + c(w,v) < D(v) then
13 D(v) = D(w) + c(w,v); p(v) = w;
14 until all nodes in N’;
2,A
2,A
3,E 4,E
33
Example: Dijkstra’s Algorithm
Step
0
1
2
3
4
5
Set N’
A
AD
ADE
ADEB
ADEBC
D(B),p(B)
2,A
D(C),p(C)
5,A
4,D
3,E
D(D),p(D)
1,A
D(E),p(E)
2,D
D(F),p(F)
4,E
∞ ∞
A
ED
CB
F
2
2
1
3
1
1
2
5
3
5
…
8 Loop
9 find w not in N’ s.t. 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 If D(w) + c(w,v) < D(v) then
13 D(v) = D(w) + c(w,v); p(v) = w;
14 until all nodes in N’;
4,E
4,E
3,E
2,A
2,A
34
Example: Dijkstra’s Algorithm
Step
0
1
2
3
4
5
Set N’
A
AD
ADE
ADEB
ADEBC
ADEBCF
D(B),p(B)
2,A
D(C),p(C)
5,A
4,D
3,E
D(D),p(D)
1,A
D(E),p(E)
2,D
D(F),p(F)
4,E
∞ ∞
A
ED
CB
F
2
2
1
3
1
1
2
5
3
5
…
8 Loop
9 find w not in N’ s.t. 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 If D(w) + c(w,v) < D(v) then
13 D(v) = D(w) + c(w,v); p(v) = w;
14 until all nodes in N’;
4,E
4,E
3,E
2,A
2,A
35
Example: Dijkstra’s Algorithm
Step
0
1
2
3
4
5
Set N’
A
AD
ADE
ADEB
ADEBC
ADEBCF
D(B),p(B)
2,A
D(C),p(C)
5,A
4,D
3,E
D(D),p(D)
1,A
D(E),p(E)
2,D
D(F),p(F)
4,E
∞ ∞
A
ED
CB
F
2
2
1
3
1
1
2
5
3
5
To determine path A ® C (say),
work backward from C via p(v)
36
• Running Dijkstra at node A gives the shortest
path from A to all destinations
• We then construct the forwarding table
The Forwarding Table
Destination Link
B (A,B)
C (A,D)
D (A,D)
E (A,D)
F (A,D)
A
ED
CB
F
resulting shortest-path tree from A:
37
Issue #1: Scalability
v How many messages needed to flood link state messages?
§ O(N x E), where N is #nodes; E is #edges in graph
v Processing complexity for Dijkstra’s algorithm?
§ O(N2), because we check all nodes w not in N’ at each
iteration and we have O(N) iterations
v How many entries in the LS topology database? O(E)
v How many entries in the forwarding table? O(N)
38
v Inconsistent link-state database
§ Some routers know about failure before others
§ The shortest paths are no longer consistent
§ Can cause transient forwarding loops
Issue#2: Transient Disruptions
A
ED
CB
F
A and D think that this
is the path to C
E thinks that this
is the path to C
A
ED
CB
F
Loop!
39
Oscillations
oscillations possible:
v e.g., suppose link cost equals amount of carried traffic:
A
D
C
B
1 1+e
e0
e
1 1
0 0
initially
A
D
C
B
given these costs,
find new routing….
resulting in new costs
2+e 0
00
1+e 1
A
D
C
B
given these costs,
find new routing….
resulting in new costs
0 2+e
1+e1
0 0
A
D
C
B
given these costs,
find new routing….
resulting in new costs
2+e 0
00
1+e 1
40
5.1 introduction
5.2 routing protocols
v link state
v distance vector
v hierarchical routing
5.6 ICMP: The Internet
Control Message
Protocol
Network layer, control plane: outline
41
Distance vector algorithm
Bellman-Ford equation
let
dx(y) := cost of least-cost path from x to y
then
dx(y) = min {c(x,v) + dv(y) }v
cost to neighbor v
min taken over all neighbors v of x
cost from neighbor v to destination y
42
Bellman-Ford example
u
yx
wv
z
2
2
1
3
1
1
2
5
3
5
clearly, dv(z) = 5, dx(z) = 3, dw(z) = 3
du(z) = min { c(u,v) + dv(z),
c(u,x) + dx(z),
c(u,w) + dw(z) }
= min {2 + 5,
1 + 3,
5 + 3} = 4
node achieving minimum is next
hop in shortest path, used in forwarding table
B-F equation says:
43
How Distance-Vector (DV) works
Each router maintains its shortest distance to every
destination via each of its neighbours
via
B
via
C
to B
to C
to D
From node A
Neighbour
(next-hop)
Destinations distC(A, D): shortest
distance from A to D via C
A
44
How Distance-Vector (DV) works
Each router computes its shortest distance to every
destination via any of its neighbors
via
B
via
C
to B
to C
to D
MIN { distB(A,B), distC(A, B) }
A
min
dist
to B
to C
to D
From node A
A’s distance
vector (DV)
45
How Distance-Vector (DV) works
How does A initialize its dist() table and DV?
via
B
via
C
to B ? ?
to C ? ?
to D ? ?
From node A
A
min
dist
to B ?
to C ?
to D ?
A’s DV
46
How Distance-Vector (DV) works
A
B
C
c(A
,B
)
c(A,C)
Link costs
How does A initialize its dist() table and DV?
47
How Distance-Vector (DV) works
Each router initializes its dist() table based on its
immediate neighbors and link costs
via B via C
to B c(A,B) ∞
to C ∞ c(A,C)
to D ∞ ∞
From node A
A
B
C
c(A
,B
)
c(A,C)
mindist
to B c(A,B)
to C c(A,C)
to D ∞
A’s DV
48
How Distance-Vector (DV) works
Each router sends its DV to its immediate neighbors
via B via C
to B c(A,B) ∞
to C ∞ c(A,C)
to D ∞ ∞
From node A
A
B
C
mindist
to B c(A,B)
to C c(A,C)
to D ∞
A’s DV
mindist
to B 5
to C 6
to D 2
c(A
,B
)
c(A,C)
49
Assume that A’s DV
is as follows at
some later time
How Distance-Vector (DV) works
Routers process received DVs
A
B
C
A’s DV
mi
n
to B 5
to C 6
to D 2
c(A
,B
)
c(A,C)
via
A
via C
to A 5 ∞
to C 15 1
to D ∞ ∞
From node B B’s DV
mindist
to A 5
to C 1
to D ∞
5
50
How Distance-Vector (DV) works
A
B
C
A’s DV
mi
n
to B 5
to C 6
to D 2
c(A,C)
via
A
via C
to A 5 ∞
to C 15 1
to D ∞ ∞
From node B B’s DV
mindist
to A 5
to C 1
to D ∞
new = c(B,A) + mindist(A, C)
5
new = c(B,A) + mindist(A, D)
11
7
Routers process received DVs
And repeat…
51
7
Distance Vector Routing
v Each router knows the links to its neighbors
v Each router has provisional “shortest path” to
every other router -- its distance vector (DV)
v Routers exchange this DV with their neighbors
v Routers look over the set of options offered by their
neighbors and select the best one
v Iterative process converges to set of shortest paths
52
iterative, asynchronous:
each local iteration
caused by:
v local link cost change
v DV update message from
neighbor
distributed:
v each node notifies
neighbors only when its
DV changes
§ neighbors then notify their
neighbors if necessary
wait for (change in local link
cost or msg from neighbor)
recompute estimates
if DV to any dest has
changed, notify neighbors
each node:
Distance vector routing
53
Distance Vector
v c(i,j): link cost from node i to j
v distz(A,V): shortest dist. from A to V via Z
v mindist(A,V): shortest dist. from A to V
0 At node A
1 Initialization:
2 for all destinations V do
3 if V is neighbor of A
4 distV(A, V) = mindist(A,V) = c(A,V);
5 else
6 distV(A, V) = mindist(A,V) = ∞;
7 send mindist(A, *) to all neighbors
loop:
8 wait (until A sees a link cost change to neighbor V /* case 1 */
9 or until A receives mindist(V,*) from neighbor V) /* case 2 */
10 if (c(A,V) changes by ±d) /* Ü case 1 */
11 for all destinations Y do
12 distV(A,Y) = distV(A,Y) ± d
13 else /* Ü case 2: */
14 for all destinations Y do
15 distV(A,Y) = c(A,V) + mindist(V, Y);
16 update mindist(A,*)
15 if (there is a change in mindist(A, *))
16 send mindist(A, *) to all neighbors
17 forever
54
Distance Vector
v c(i,j): link cost from node i to j
v distZ(A,V): shortest dist. from A to V via Z
v mindist(A,V): shortest dist. from A to V
0 At node A
1 Initialization:
2 for all destinations V do
3 if V is neighbor of A
4 distV(A, V) = mindist(A,V) = c(A,V);
5 else
6 distV(A, V) = mindist(A,V) = ∞;
7 send mindist(A, *) to all neighbors
loop:
8 wait (until A sees a link cost change to neighbor V /* case 1 */
9 or until A receives mindist(V,*) from neighbor V) /* case 2 */
10 if (c(A,V) changes by ±d) /* Ü case 1 */
11 for all destinations Y do
12 distV(A,Y) = distV(A,Y) ± d
13 else /* Ü case 2: */
14 for all destinations Y do
15 distV(A,Y) = c(A,V) + mindist(V, Y);
16 update mindist(A,*)
15 if (there is a change in mindist(A, *))
16 send mindist(A, *) to all neighbors
17 forever
55
Example: Initialization
A C
12
7
B D3
1
via
B
via
C
to A - -
to B 2 ∞
to C ∞ 7
to D ∞ ∞
from Node A
via
A
via
C
via
D
to A 2 ∞ ∞
to B - - -
to C ∞ 1 ∞
to D ∞ ∞ 3
from Node B
from Node C
via
A
via
B
via
D
to A 7 ∞ ∞
to B ∞ 1 ∞
to C - - -
to D ∞ ∞ 1
via
B
via
C
to A ∞ ∞
to B 3 ∞
to C ∞ 1
to D - -
from Node D
min
dist
to A 0
to B 2
to C 7
to D ∞
min
dist
0
2
7
∞
min
dist
2
0
1
3
min
dist
∞
3
1
0
min
dist
7
1
0
1
56
Example: C sends update to A
via
B
via
C
to A - -
to B 2 ∞
to C ∞ 7
to D ∞ ∞
from Node A
via
A
via
C
via
D
to A 2 ∞ ∞
to B - - -
to C ∞ 1 ∞
to D ∞ ∞ 3
from Node B
from Node C
via
A
via
B
via
D
to A 7 ∞ ∞
to B ∞ 1 ∞
to C - - -
to D ∞ ∞ 1
via
B
via
C
to A ∞ ∞
to B 3 ∞
to C ∞ 1
to D - -
from Node D
min
dist
0
2
7
∞
min
dist
∞
3
1
0
min
dist
7
1
0
1
A C
12
7
B D3
1
min
dist
2
0
1
3
57
Example: C sends update to A
via
B
via
C
to A - -
to B 2 ∞
to C ∞ 7
to D ∞ ∞
from Node A
min
dist
0
2
7
∞
A C
12
7
B D3
1
min
dist
7
1
0
1
58
Example: C sends update to A
via
B
via
C
to A - -
to B 2 8
to C ∞ 7
to D ∞ 8
from Node A
min
dist
0
2
7
∞
A C
12
7
B D3
1
min
dist
7
1
0
1
59
Example: C sends update to A
via
B
via
C
to A - -
to B 2 8
to C ∞ 7
to D ∞ 8
from Node A
min
dist
0
2
7
8
A C
12
7
B D3
1
60
Example: now B sends update to A
via
A
via
C
via
D
to A 2 ∞ ∞
to B - - -
to C ∞ 1 ∞
to D ∞ ∞ 3
from Node B
from Node C
via
A
via
B
via
D
to A 7 ∞ ∞
to B ∞ 1 ∞
to C - - -
to D ∞ ∞ 1
via
B
via
C
to A ∞ ∞
to B 3 ∞
to C ∞ 1
to D - -
from Node D
min
dist
∞
3
1
0
min
dist
7
1
0
1
A C
12
7
B D3
1
min
dist
2
0
1
3
via
B
via
C
to A - -
to B 2 8
to C ∞ 7
to D ∞ 8
from Node A
min
dist
0
2
7
8 61
Example: now B sends update to A
via
A
via
C
via
D
to A 2 ∞ ∞
to B - - -
to C ∞ 1 ∞
to D ∞ ∞ 3
from Node B
from Node C
via
A
via
B
via
D
to A 7 ∞ ∞
to B ∞ 1 ∞
to C - - -
to D ∞ ∞ 1
via
B
via
C
to A ∞ ∞
to B 3 ∞
to C ∞ 1
to D - -
from Node D
min
dist
∞
3
1
0
min
dist
7
1
0
1
A C
12
7
B D3
1
min
dist
2
0
1
3
via
B
via
C
to A - -
to B 2 8
to C ∞ 7
to D ∞ 8
from Node A
min
dist
0
2
7
8 62
Example: now B sends update to A
via
A
via
C
via
D
to A 2 ∞ ∞
to B - - -
to C ∞ 1 ∞
to D ∞ ∞ 3
from Node B
from Node C
via
A
via
B
via
D
to A 7 ∞ ∞
to B ∞ 1 ∞
to C - - -
to D ∞ ∞ 1
via
B
via
C
to A ∞ ∞
to B 3 ∞
to C ∞ 1
to D - -
from Node D
min
dist
∞
3
1
0
min
dist
7
1
0
1
A C
12
7
B D3
1
min
dist
2
0
1
3
via
B
via
C
to A - -
to B 2 8
to C 3 7
to D 5 8
from Node A
min
dist
0
2
7
8
Make sure you know
why this is 5, not 4!
63
Example: now B sends update to A
via
A
via
C
via
D
to A 2 ∞ ∞
to B - - -
to C ∞ 1 ∞
to D ∞ ∞ 3
from Node B
from Node C
via
A
via
B
via
D
to A 7 ∞ ∞
to B ∞ 1 ∞
to C - - -
to D ∞ ∞ 1
via
B
via
C
to A ∞ ∞
to B 3 ∞
to C ∞ 1
to D - -
from Node D
min
dist
∞
3
1
0
min
dist
7
1
0
1
A C
12
7
B D3
1
min
dist
2
0
1
3
via
B
via
C
to A - -
to B 2 8
to C 3 7
to D 5 8
from Node A
min
dist
0
2
3
5 64
Example: After 1st Full Exchange
via
A
via
C
via
D
to A 2 8 ∞
to B - - -
to C 9 1 4
to D ∞ 2 3
from Node B
from Node C
via
A
via
B
via
D
to A 7 3 ∞
to B 9 1 4
to C - - -
to D ∞ 4 1
via
B
via
C
to A 5 8
to B 3 2
to C 4 1
to D - -
from Node D
min
dist
5
2
1
0
min
dist
3
1
0
1
A C
12
7
B D3
1
min
dist
2
0
1
2
via
B
via
C
to A - -
to B 2 8
to C 3 7
to D 5 8
from Node A
min
dist
0
2
3
5
Make sure you understand why
some entries are still ∞
All nodes know the best two-hop paths.
Make sure you believe this
65
Example: Now A sends update to B
from Node B
from Node C
from Node D
min
dist
5
2
1
0
min
dist
3
1
0
1
A C
12
7
B D3
1
min
dist
2
0
1
2
from Node A
min
dist
0
2
3
5
via
B
via
C
to A - -
to B 2 8
to C 3 7
to D 5 8
via
A
via
B
via
D
to A 7 3 ∞
to B 9 1 4
to C - - -
to D ∞ 4 1
via
B
via
C
to A 5 8
to B 3 2
to C 4 1
to D - -
via
A
via
C
via
D
to A 2 8 ∞
to B - - -
to C 9 1 4
to D ∞ 2 3
66
Example: Now A sends update to B
via
A
via
C
via
D
to A 2 8 ∞
to B - - -
to C 5 1 4
to D 7 2 3
from Node B
from Node C
from Node D
min
dist
5
2
1
0
min
dist
3
1
0
1
A C
12
7
B D3
1
min
dist
2
0
1
2
from Node A
min
dist
0
2
3
5
via
B
via
C
to A - -
to B 2 8
to C 3 7
to D 5 8
Updated
via
A
via
B
via
D
to A 7 3 ∞
to B 9 1 4
to C - - -
to D ∞ 4 1
via
B
via
C
to A 5 8
to B 3 2
to C 4 1
to D - -
67
Example: End of 2nd Full Exchange
via
A
via
C
via
D
to A 2 4 8
to B - - -
to C 5 1 4
to D 7 2 3
from Node B
from Node C
from Node D
min
dist
4
2
1
0
min
dist
3
1
0
1
A C
12
7
B D3
1
min
dist
2
0
1
2
from Node A
min
dist
0
2
3
4
via
B
via
C
to A - -
to B 2 8
to C 3 7
to D 4 8
via
A
via
B
via
D
to A 7 3 6
to B 9 1 3
to C - - -
to D 12 3 1
via
B
via
C
to A 5 4
to B 3 2
to C 4 1
to D - -
Check
Check: All nodes know the best three-hop paths.
68
Example: End of 3nd Full Exchange
via
A
via
C
via
D
to A 2 4 7
to B - - -
to C 5 1 4
to D 6 2 3
from Node B
from Node C
from Node D
min
dist
4
2
1
0
min
dist
3
1
0
1
A C
12
7
B D3
1
min
dist
2
0
1
2
from Node A
min
dist
0
2
3
4
via
B
via
C
to A - -
to B 2 8
to C 3 7
to D 4 8
via
A
via
B
via
D
to A 7 3 5
to B 9 1 3
to C - - -
to D 11 3 1
via
B
via
C
to A 5 4
to B 3 2
to C 4 1
to D - -
No further change in DVs à Convergence!
69
Intuition
v Initial state: best one-hop paths
v One simultaneous round: best two-hop paths
v Two simultaneous rounds: best three-hop paths
v …
v Kth simultaneous round: best (k+1) hop paths
v Must eventually converge
§ as soon as it reaches longest best path
v …..but how does it respond to changes in cost?
70
Problems with Distance Vector
Ø A number of problems can occur in a network using
distance vector algorithm
Ø Most of these problems are caused by slow
convergence or routers converging on incorrect
information
Ø Convergence is the time during which all routers come
to an agreement about the best paths through the
internetwork
• whenever topology changes there is a period of instability in
the network as the routers converge
Ø Reacts rapidly to good news, but leisurely to bad
news
71
DV: Link Cost Changes
A C
A 4 6
C 9 1
Node B
A B
A 50 5
B 54 1
Node C
Link cost changes here
A C
A 1 6
C 6 1
A B
A 50 5
B 54 1
A C
A 1 6
C 3 1
A B
A 50 5
B 51 1
A C
A 1 6
C 3 1
A B
A 50 2
B 51 1
B C
B 4 51
C 5 50
Node A B C
B 1 51
C 2 50
B C
B 1 51
C 2 50
B C
B 1 51
C 2 50
A C
A 1 3
C 3 1
A B
A 50 2
B 51 1
B C
B 1 51
C 2 50
Stable
state
A-B changed A sends its
DV to B, C
B sends its
DV to A, C
C sends its
DV to A, B
A C
14
50
B1
“good news travels fast”
to
via
Note: none of B’s
paths use link (A,C)
deduct 3 from distances
distB(A,*) and distA(B,*)
72
DV: Link Cost Changes
A C
A 4 6
C 9 1
Node B
A B
A 50 5
B 54 1
Node C
Link cost changes here
A C
A 60 6
C 65 1
A B
A 50 5
B 54 1
B C
B 4 51
C 5 50
Node A B C
B 60 51
C 61 50
Stable
state A-B changed
A C
14
50
B60
to
via
add 56 to distances
distB(A,*) and distA(B,*)
73
DV: Link Cost Changes
A C
A 4 6
C 9 1
Node B
A B
A 50 5
B 54 1
Node C
Link cost changes here
A C
A 60 6
C 65 1
A B
A 50 5
B 54 1
A C
A 60 6
C 110 1
A B
A 50 5
B 101 1
A C
A 60 6
C 110 1
A B
A 50 7
B 101 1
B C
B 4 51
C 5 50
Node A B C
B 60 51
C 61 50
B C
B 60 51
C 61 50
B C
B 60 51
C 61 50
A C
A 60 8
C 110 1
A B
A 50 7
B 101 1
B C
B 60 51
C 61 50
Stable
state
A-B changed A sends its
DV to B, C
B sends its
DV to A, C
C sends its
DV to A, B
A C
14
50
B60
“bad news travels slowly”
(not yet converged)
to
via
This is the “Counting to Infinity” Problem
74
The “Poisoned Reverse” Rule
v Heuristic to avoid count-to-infinity
v If B routes via C to get to A:
§ B tells C its (B’s) distance to A is infinite
(so C won’t route to A via B)
75
DV: Poisoned Reverse
A C
A 4 6
C 9 1
Node B
A B
A 50 5
B 54 1
Node C
B C
B 4 51
C 5 50
Node A
Stable
state
A C
14
50
B
to
via
If B routes through C to get to A:
B tells C its (B’s) distance to A is infinite
∞
∞
Mindist
4
5
Mindist
4
5∞
Mindist
5
1
Mindist
5
1
∞
76
DV: Poisoned Reverse
A C
A 4 6
C 9 1
Node B
A B
A 50 5
B 54 1
Node C
Link cost changes here
A C
A 60 6
C 65 1
A B
A 50 5
B 54 1
B C
B 4 51
C 5 50
Node A B C
B 60 51
C 61 50
Stable
state
A-B changed
A C
14
50
B60
to
via
If B routes through C to get to A:
B tells C its (B’s) distance to A is infinite
∞
∞
77
DV: Poisoned Reverse
A C
A 4 6
C 9 1
Node B
A B
A 50 5
B 54 1
Node C
Link cost changes here
A C
A 60 6
C 65 1
A B
A 50 5
B 54 1
A C
A 60 6
C 110 1
A B
A 50 5
B 101 1
A C
A 60 6
C 110 1
A B
A 50 7
B 101 1
B C
B 4 51
C 5 50
Node A B C
B 60 51
C 61 50
B C
B 60 51
C 61 50
B C
B 60 51
C 61 50
Stable
state
A-B changed A sends its
DV to B, C
B sends its
DV to A, C
A C
14
50
B60
to
via
If B routes through C to get to A:
B tells C its (B’s) distance to A is infinite
∞
∞ ∞
∞ ∞
∞
∞
∞
78
DV: Poisoned Reverse
A C
A 4 6
C 9 1
Node B
A B
A 50 5
B 54 1
Node C
Link cost changes here
A C
A 60 6
C 65 1
A B
A 50 5
B 54 1
A C
A 60 6
C 110 1
A B
A 50 5
B 101 1
A C
A 60 6
C 110 1
A B
A 50 61
B 101 1
B C
B 4 51
C 5 50
Node A B C
B 60 51
C 61 50
B C
B 60 51
C 61 50
B C
B 60 51
C 61 50
Stable
state
A-B changed A sends its
DV to B, C
B sends its
DV to A, C
A C
14
50
B60
to
via
If B routes through C to get to A:
B tells C its (B’s) distance to A is infinite
∞
∞ ∞
∞ ∞
∞
∞
∞
79
DV: Poisoned Reverse
A C
A 4 6
C 9 1
Node B
A B
A 50 5
B 54 1
Node C
Link cost changes here
A C
A 60 6
C 65 1
A B
A 50 5
B 54 1
A C
A 60 6
C 110 1
A B
A 50 5
B 101 1
A C
A 60 6
C 110 1
A B
A 50 61
B 101 1
B C
B 4 51
C 5 50
Node A B C
B 60 51
C 61 50
B C
B 60 51
C 61 50
B C
B 60 51
C 61 50
A B
A 50 61
B 101 1
B C
B 60 51
C 61 50
Stable
state A-B changed A sends its
DV to B, C
B sends its
DV to A, C
C sends its
DV to A, B
A C
14
50
B60
to
via
If B routes through C to get to A:
B tells C its (B’s) distance to A is infinite
∞
∞ ∞
∞ ∞
∞
∞
∞ ∞
A C
A 60 51
C 110 1
Converges after C receives
another update from B
∞
80
Will Poison-Reverse Completely Solve
the Count-to-Infinity Problem?
A C
1
B
D
1
1 1
1 1
2 2
∞
∞ ∞
100
100 100
3
∞
4
∞ 4
5
6
Numbers in blue denote the best cost
to destination D advertised along the link
81
Quiz: Link-state routing
v In link state routing, each node sends information
of its direct links (i.e., link state) to ________?
A. Immediate neighbours
B. All nodes in the network
C. Any one neighbor
D. No one
82
www.zeetings.com/salil
Answer: B
Answer: B
Quiz: Distance-vector routing
v In distance vector routing, each node shares its
distance table with ________?
A. All Immediate neighbours
B. All nodes in the network
C. Any one neighbor
D. No one
83
www.zeetings.com/salil
Answer: A
Answer: A
Quiz: Distance-vector routing
v Which of the following is true of distance vector
routing?
A. Convergence delay depends on the topology (nodes and
links) and link weights
B. Convergence delay depends on the number of nodes
and links
C. Each node knows the entire topology
D. A and C
E. B and C
84
www.zeetings.com/salil
Answer: A
Answer: A
Comparison of LS and DV algorithms
message complexity
v LS: with n nodes, E links, O(nE)
msgs sent
v DV: exchange between neighbors
only
§ convergence time varies
speed of convergence
v LS: O(n2) algorithm requires
O(nE) msgs
§ may have oscillations
v DV: convergence time varies
§ may be routing loops
§ count-to-infinity problem
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
• error propagate thru
network
85
Real Protocols
Link State
Open Shortest Path
First (OSPF)
Intermediate system to
intermediate system (IS-
IS)
Distance Vector
Routing Information
Protocol (RIP)
Interior Gateway
Routing Protocol
(IGRP-Cisco)
Border Gateway
Protocol (BGP)
86
5.1 introduction
5.2 routing protocols
v link state
v distance vector
v hierarchical routing
5.6 ICMP: The Internet
Control Message
Protocol
Network layer, control plane: outline
Self study (not on
exam)
87
ICMP: Internet Control Message Protocol
v Used by hosts & routers to communicate
network level infromation
§ Error reporting: unreachable host, network, port
§ Echo request/reply (used by ping)
v Works above IP layer
§ ICMP messages carried in IP datagrams
v ICMP message: type, code plus IP header and first
8 bytes of IP datagram payload causing error
IP Header IP HeaderICMP Header
8
Bytes
Contains source
address, checksum etc.
Contains TCP/UDP
port numbers
88
ICMP: Internet Control Message Protocol
v Type Code Description
0 0 echo reply(ping)
3 0 dest. network unreachable
3 1 dest host unreachable
3 3 dest port unreachable
3 4 frag needed; DF set
8 0 echo request(ping)
11 0 TTL expired
11 1 frag reassembly time exceeded
12 0 bad IP header
89
Traceroute and ICMP
Ø Source sends series of
UDP segments to dest
• first set has TTL =1
• second set has TTL=2, etc.
• unlikely port number
Ø When nth set of
datagrams arrives to nth
router:
• router discards datagrams
• and sends source ICMP
messages (type 11, code 0)
• ICMP messages includes IP
address of router
Ø when ICMP messages
arrives, source records
RTTs
stopping criteria:
Ø UDP segment eventually
arrives at destination host
Ø destination returns ICMP
“port unreachable”
message (type 3, code 3)
Ø source stops
3 probes
3 probes
3 probes
90
Summary
v Network Layer: Data
Plane
§ Overview
§ IP
v Network Layer:
Control Plane
§ Routing Protocols
• Link—state
• Distance Vector
§ ICMP
91
COMP 3331/9331:
Computer Networks and
Applications
Week 9
Data link Layer
Reading Guide: Chapter 6, Sections 6.1 – 6.4, 6.7
Link layer and LANs
our goals:
v understand principles behind link layer
services:
§ error detection, correction
§ sharing a broadcast channel: multiple access
§ link layer addressing
§ local area networks: Ethernet
93
Link layer, LANs: outline
6.1 introduction, services
6.2 error detection,
correction
6.3 multiple access
protocols
6.4 Switched LANs
§ addressing, ARP
§ Ethernet
§ Switches
§ VLANS (EXCLUDED)
6.5 link virtualization:
MPLS (EXCLUDED)
6.6 data center
networking
(EXCLUDED)
6.7 a day in the life of a
web request
94
From Macro- to Micro-
95
From Macro- to Micro-
• Previously, we looked at Internet scale…
Customer AS
Destination
AS Customer’s ISP
Other
Networks
Other
Networks
Link layer focus: Within a Subnet
96
Within a Subnet
Router
Link layer: introduction
terminology:
v hosts and routers: nodes
v communication channels that
connect adjacent nodes along
communication path: links
§ wired links
§ wireless links
§ LANs
v layer-2 packet: frame,
encapsulates datagram
data-link layer has responsibility of
transferring datagram from one node
to physically adjacent node over a link
global ISP
97
Link layer: context
v datagram transferred by
different link protocols over
different links:
§ e.g., Ethernet on first link,
frame relay on
intermediate links, 802.11
on last link
v each link protocol provides
different services
§ e.g., may or may not
provide rdt over link
transportation analogy:
v trip from Princeton to Lausanne
§ limo: Princeton to JFK
§ plane: JFK to Geneva
§ train: Geneva to Lausanne
v tourist = datagram
v transport segment =
communication link
v transportation mode = link
layer protocol
v travel agent = routing
algorithm
98
Link layer services
v framing, link access:
§ encapsulate datagram into frame, adding header, trailer
§ channel access if shared medium
§ “MAC” addresses used in frame headers to identify
source, dest
• different from IP address!
v reliable delivery between adjacent nodes
§ we learned how to do this already (chapter 3)!
§ seldom used on low bit-error link (fiber, some twisted
pair)
§ wireless links: high error rates
• Q: why both link-level and end-end
reliability?
99
v flow control:
§ pacing between adjacent sending and receiving nodes
v error detection:
§ errors caused by signal attenuation, noise.
§ receiver detects presence of errors:
• signals sender for retransmission or drops frame
v error correction:
§ receiver identifies and corrects bit error(s) without resorting to
retransmission
v half-duplex and full-duplex
§ with half duplex, nodes at both ends of link can transmit, but not
at same time
Link layer services (more)
100
Where is the link layer implemented?
v in each and every host
v link layer implemented in
“adaptor” (aka network
interface card NIC) or on a
chip
§ Ethernet card, 802.11
card; Ethernet chipset
§ implements link, physical
layer
v attaches into host’s system
buses
v combination of hardware,
software, firmware
controller
physical
transmission
cpu memory
host
bus
(e.g., PCI)
network adapter
card
application
transport
network
link
link
physical
101
Adaptors communicating
v sending side:
§ encapsulates datagram in
frame
§ adds error checking bits,
rdt, flow control, etc.
v receiving side
§ looks for errors, rdt,
flow control, etc
§ extracts datagram, passes
to upper layer at
receiving side
controller controller
sending host receiving host
datagram datagram
datagram
frame
102
103
What is framing?
Ø Physical layer talks in terms of bits.
Ø How do we identify frames within the sequence of bits?
Ø Need to do Framing
• Delimit the start and end of the frame
Ø Ethernet Framing
• Timing/Physical layer
104
Framing in Ethernet
Ø Start of frame is recognized by
• Preamble : Seven bytes with pattern 10101010
• Start of Frame Delimiter (SFD) : 10101011
Ø Inter Frame Gap is 12 Bytes (96 bits) of idle state
• 0.96 microsec for 100 Mbit/s Ethernet
• 0.096 microsec for Gigabit/s Ethernet
Preamble
7 Bytes
SFD
1 Byte
Dest
MAC
6 Bytes
Source
MAC
6 Bytes
Type/Le
ngth
2 Bytes
Payload
46-1500
Bytes
FCS/C
RC
4
Bytes
Inter
Frame
Gap