Shortest-Path Routing

Reading: Sections 4.2 and 4.3.4

COS 461: Computer Networks

Jennifer Rexford

1
Goals of Today’s Lecture
• Path selection
– Minimum-hop and shortest-path routing
– Dijkstra and Bellman-Ford algorithms
• Topology change
– Using beacons to detect topology changes
– Propagating topology or path information
• Routing protocols
– Link state: Open Shortest Path First
– Distance vector: Routing Information Protocol

2
What is Routing?
• A famous quotation from RFC 791
“A name indicates what we seek.
An address indicates where it is.
A route indicates how we get there.”
-- Jon Postel

3
Forwarding vs. Routing
• Forwarding: data plane
–Directing a data packet to an outgoing link
–Individual router using a forwarding table
• Routing: control plane
–Computing paths the packets will follow
–Routers talking amongst themselves
–Individual router creating a forwarding table

4
Why Does Routing Matter?
• End-to-end performance
– Quality of the path affects user performance
– Propagation delay, throughput, and packet loss

• Use of network resources

– Balance of the traffic over the routers and links
– Avoiding congestion by directing traffic to lightly-
loaded links

• Transient disruptions during changes

– Failures, maintenance, and load balancing
– Limiting packet loss and delay during changes
5
Shortest-Path Routing
• Path-selection model
–Destination-based
–Load-insensitive (e.g., static link weights)
–Minimum hop count or sum of link weights

2
3 1
1
4
2 1
5
4 3
6
Shortest-Path Problem
• Given: network topology with link costs
– c(x,y): link cost from node x to node y
– Infinity if x and y are not direct neighbors

• Compute: least-cost paths to all nodes

– From a given source u to all other nodes
– p(v): predecessor node along path from source to v
2
3 1
1
u 4
2 1
5
p(v)
4 3
v 7
Dijkstra’s Shortest-Path
Algorithm
• Iterative algorithm
– After k iterations, know least-cost path to k nodes

• S: nodes whose least-cost path definitively known

– Initially, S = {u} where u is the source node
– Add one node to S in each iteration

• D(v): current cost of path from source to node v

– Initially, D(v) = c(u,v) for all nodes v adjacent to u
– … and D(v) = ∞ for all other nodes v
– Continually update D(v) as shorter paths are learned

8
Dijsktra’s Algorithm

1 Initialization:
2 S = {u}
3 for all nodes v
4 if v adjacent to u {
5 D(v) = c(u,v)
6 else D(v) = ∞
7
8 Loop
9 find w not in S with the smallest D(w)
10 add w to S
11 update D(v) for all v adjacent to w and not in S:
12 D(v) = min{D(v), D(w) + c(w,v)}
13 until all nodes in S
9
Dijkstra’s Algorithm Example
2 2
3 1 3 1
1 1
4 4
2 1 2 1
5 5
4 3 4 3

2 2
3 1 3 1
1 1
4 4
2 1 2 1
5 5
4 3 4 3
10
Dijkstra’s Algorithm Example
2 2
3 1 3 1
1 1
4 4
2 1 2 1
5 5
4 3 4 3

2 2
3 1 3 1
1 1
4 4
2 1 2 1
5 5
4 3 4 3
11
Shortest-Path Tree
• Shortest-path tree from u • Forwarding table at u

v 2 y
1 link
3 1
u
x 4 z
v (u,v)
2 1 w (u,w)
5 t
x (u,w)
w4 3
s y (u,v)
z (u,v)
s (u,w)
t (u,w)
12
Link-State Routing
• Each router keeps track of its incident links
– Whether the link is up or down
– The cost on the link

• Each router broadcasts the link state

– To give every router a complete view of the graph

• Each router runs Dijkstra’s algorithm

– To compute the shortest paths
– … and construct the forwarding table

• Example protocols
– Open Shortest Path First (OSPF)
– Intermediate System – Intermediate System (IS-IS)
13
Detecting Topology Changes
• Beaconing
– Periodic “hello” messages in both directions
– Detect a failure after a few missed “hellos”
“hello”

• Performance trade-offs
– Detection speed
– Overhead on link bandwidth and CPU
– Likelihood of false detection
14
Broadcasting the Link State
• Flooding
– Node sends link-state information out its links
– And then the next node sends out all of its links
– … except the one where the information arrived

X A X A

C B D C B D
(a) (b)

X A X A

C B D C B D
(c) (d) 15
Broadcasting the Link State
• Reliable flooding
– Ensure all nodes receive link-state information
– … and that they use the latest version

• Challenges
– Packet loss
– Out-of-order arrival

• Solutions
– Acknowledgments and retransmissions
– Sequence numbers
– Time-to-live for each packet
16
When to Initiate Flooding
• Topology change
– Link or node failure
– Link or node recovery

• Configuration change
– Link cost change

• Periodically
– Refresh the link-state information
– Typically (say) 30 minutes
– Corrects for possible corruption of the data
17
Convergence
• Getting consistent routing information to all nodes
– E.g., all nodes having the same link-state database

• Consistent forwarding after convergence

– All nodes have the same link-state database
– All nodes forward packets on shortest paths
– The next router on the path forwards to the next hop
2
3 1
1
4
2 1
5
4 3
18
Transient Disruptions
• Detection delay
– A node does not detect a failed link immediately
– … and forwards data packets into a “blackhole”
– Depends on timeout for detecting lost hellos

2
3 1
1
4
2 1
5
4 3
19
Transient Disruptions
• Inconsistent link-state database
– Some routers know about failure before others
– The shortest paths are no longer consistent
– Can cause transient forwarding loops

2 2
3 1 3 1
1 1
4 4
2 1 2 1
5
4 3 4 3

20
Convergence Delay
• Sources of convergence delay
– Detection latency
– Flooding of link-state information
– Shortest-path computation
– Creating the forwarding table

• Performance during convergence period

– Lost packets due to blackholes and TTL expiry
– Looping packets consuming resources
– Out-of-order packets reaching the destination

• Very bad for VoIP, online gaming, and video

21
Reducing Convergence Delay
• Faster detection
– Smaller hello timers
– Link-layer technologies that can detect failures

• Faster flooding
– Flooding immediately
– Sending link-state packets with high-priority

• Faster computation
– Faster processors on the routers
– Incremental Dijkstra algorithm

• Faster forwarding-table update

– Data structures supporting incremental updates
22
Scaling Link-State Routing
• Overhead of link-state routing
– Flooding link-state packets throughout the network
– Running Dijkstra’s shortest-path algorithm

• Introducing hierarchy through “areas”

Area 1 Area 2

area Area 0
border
router
Area 3 Area 4
23
Bellman-Ford Algorithm
• Define distances at each node x
– dx(y) = cost of least-cost path from x to y

• Update distances based on neighbors

– dx(y) = min {c(x,v) + dv(y)} over all neighbors v
v 2 y
3 1
1
u
x 4 z
2 1
5 t du(z) = min{c(u,v) + dv(z),
w4 3
s c(u,w) + dw(z)}
24
Distance Vector Algorithm
• c(x,v) = cost for direct link from x to v
– Node x maintains costs of direct links c(x,v)

• Dx(y) = estimate of least cost from x to y

– Node x maintains distance vector Dx = [Dx(y): y є N ]

• Node x maintains its neighbors’ distance vectors

– For each neighbor v, x maintains Dv = [Dv(y): y є N ]

• Each node v periodically sends Dv to its neighbors

– And neighbors update their own distance vectors
– Dx(y) ← minv{c(x,v) + Dv(y)} for each node y ∊ N

• Over time, the distance vector Dx converges

25
Distance Vector Algorithm

Each node:
Iterative, asynchronous:
each local iteration caused by:
• Local link cost change wait for (change in local link
cost or message from neighbor)
• Distance vector update
message from neighbor

Distributed: recompute estimates

• Each node notifies neighbors
only when its DV changes if DV to any destination has
• Neighbors then notify their changed, notify neighbors
neighbors if necessary

26
Distance Vector Example: Step
0
Optimum 1-hop paths
Table for A Table for B
E 3 C
Dst Cst Hop Dst Cst Hop 1
A 0 A A 4 A
F 1
B 4 B B 0 B 2
6
C  – C  –
1
D  – D 3 D 3 D
A 4
E 2 E E  –
B
F 6 F F 1 F
Table for C Table for D Table for E Table for F
Dst Cst Hop Dst Cst Hop Dst Cst Hop Dst Cst Hop
A  – A  – A 2 A A 6 A
B  – B 3 B B  – B 1 B
C 0 C C 1 C C  – C 1 C
D 1 D D 0 D D  – D  –
E  – E  – E 0 E E 3 E
F 1 F F  – F 3 F F 0 F
27
Distance Vector Example: Step
2
Optimum 2-hop paths
Table for A Table for B
E 3 C
Dst Cst Hop Dst Cst Hop 1
A 0 A A 4 A 1
2 F
B 4 B B 0 B
6
C 7 F C 2 F 1
D 7 B D 3 D 3 D
A 4
E 2 E E 4 F
B
F 5 E F 1 F
Table for C Table for D Table for E Table for F
Dst Cst Hop Dst Cst Hop Dst Cst Hop Dst Cst Hop
A 7 F A 7 B A 2 A A 5 B
B 2 F B 3 B B 4 F B 1 B
C 0 C C 1 C C 4 F C 1 C
D 1 D D 0 D D  – D 2 C
E 4 F E  – E 0 E E 3 E
F 1 F F 2 C F 3 F F 0 F
28
Distance Vector Example: Step
3
Optimum 3-hop paths
Table for A Table for B
E 3 C
Dst Cst Hop Dst Cst Hop 1
A 0 A A 4 A 1
2 F
B 4 B B 0 B
6
C 6 E C 2 F 1
D 7 B D 3 D 3 D
A 4
E 2 E E 4 F
B
F 5 E F 1 F
Table for C Table for D Table for E Table for F
Dst Cst Hop Dst Cst Hop Dst Cst Hop Dst Cst Hop
A 6 F A 7 B A 2 A A 5 B
B 2 F B 3 B B 4 F B 1 B
C 0 C C 1 C C 4 F C 1 C
D 1 D D 0 D D 5 F D 2 C
E 4 F E 5 C E 0 E E 3 E
F 1 F F 2 C F 3 F F 0 F
29
Distance Vector: Link Cost
Changes
Link cost changes: 1
Y
4 1
• Node detects local link cost change
X Z
• Updates the distance table 50

• If cost change in least cost path, notify neighbors

algorithm
terminates
“good
news
travels
fast”

30
Distance Vector: Link Cost
Changes
Link cost changes: 60
• Good news travels fast Y
4 1
• Bad news travels slow - “count to X Z
50
infinity” problem!

algorithm
continues
on!

31
Distance Vector: Poison
Reverse
If Z routes through Y to get to X : 60
• Z tells Y its (Z’s) distance to X is infinite (so Y Y
4 1
won’t route to X via Z) X Z
50
• Still, can have problems when more than 2
routers are involved
algorithm
terminates

32
Routing Information Protocol
(RIP)
• Distance vector protocol
– Nodes send distance vectors every 30 seconds
– … or, when an update causes a change in routing

• Link costs in RIP

– All links have cost 1
– Valid distances of 1 through 15
– … with 16 representing infinity
– Small “infinity”  smaller “counting to infinity” problem

• RIP is limited to fairly small networks

– E.g., used in the Princeton campus network

33
Comparison of LS and DV
algorithms
Message complexity Robustness: what happens
• LS: with n nodes, E links, O(nE) if router malfunctions?
messages sent
LS:
• DV: exchange between – Node can advertise incorrect
neighbors only link cost
– Convergence time varies – Each node computes only its
Speed of Convergence own table

• LS: O(n2) algorithm requires DV:

O(nE) messages – DV node can advertise
• DV: convergence time varies incorrect path cost
– May be routing loops – Each node’s table used by
– Count-to-infinity problem others (error propagates)

34
Conclusions
• Routing is a distributed algorithm
– React to changes in the topology
– Compute the shortest paths

• Two main shortest-path algorithms

– Dijkstra  link-state routing (e.g., OSPF and IS-IS)
– Bellman-Ford  distance vector routing (e.g., RIP)

• Convergence process
– Changing from one topology to another
– Transient periods of inconsistency across routers

• Next time: policy-based path-vector routing

– Reading: Section 4.3.3
35