Lowest-Cost Routing

EE 122: Intro to Communication Networks

Fall 2010 (MW 4-5:30 in 101 Barker)
Scott Shenker
TAs: Sameer Agarwal, Sara Alspaugh, Igor Ganichev, Prayag Narula
[Link]
Materials with thanks to Jennifer Rexford, Ion Stoica, Vern Paxson
and other colleagues at Princeton and UC Berkeley
1
Announcements
• Revision to lecture schedule
– Advanced topics on routing
• Revision to homework schedule
– 3a: get midterm questions right
– 3b: new topics
• Changes to class structure
– 5 minute “technology break”
– Administrivia right after break
– Group problem solving (when possible)
o Sit next to smart people

2
Goals of Today’s Lecture
• Routing overview:
– Routing vs. forwarding
– Routing topics

• Link-state routing (Dijkstra’s algorithm)

• Distance-vector routing (Bellman-Ford)

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
–Jointly creating a forwarding table

4
Why Does Routing Matter?
• Routing provides connectivity!
– Without routing, the network doesn’t function

• Routing finds “good” paths

– Propagation delay, throughput, packet loss

• Routing allows network to tolerate failures

– Limits packet loss during disruptions

• Routing can also provide “Traffic Engineering”

– Balance traffic over the routers and links
– Avoid congestion by directing traffic to lightly-loaded links
– (Not covered today)
5
Three Lectures on Routing
• Today: Lowest-cost routing
– Simple algorithms, basic issues

• Wednesday: Policy-based routing

– Interdomain routing

• Monday: Advanced topics

– Traffic engineering
– Improved resilience
– What future routing algorithms might look like….

6
Routing Requires Knowing Network
• Centralized global state
– Single entity knows the complete network structure
– Can calculate all routes centrally
Link State Routing
– Problems with this approach? E.g. Algorithm: Dijkstra
E.g. Protocol: OSPF
• Distributed global state
– Every router knows the complete network structure
– Independently calculates routes
– Problems with this approach? Distance Vector Routing
E.g. Algorithm: Bellman-Ford
E.g. Protocol: RIP
• Distributed global computation
– Every router knows only about its neighboring routers
– Participates in global joint calculation of routes
– Problems with this approach? 7
Modeling a Network
• Modeled as a graph
– Routers  nodes 5
– Link  edges 3
B C
o Possible edge costs 2 5
• Hop
A 2 1 F
• Delay 3
• Congestion level 1
2
• …. D E
1

• Goal of Routing
– Determine “good” path from source to destination
– “Good” usually means the lowest “cost” path
– Where cost is usually hop-count or latency
8
From Model to Reality
• In reality, attach prefixes to nodes
• Calculate routing tables in terms of prefixes
• But ignore this for now…..
– Just calculate paths between routers

9
Why Isn’t All Routing Lowest-Cost?
• Lowest-cost routing assumes all nodes evaluate
paths the same way
– i.e., use same “cost” metric

• Interdomain routing:
– Different domains care about different things
– Can exercise general “policy” goals

• Requires very different route computation

– Talk about on Wednesday….

10
Link State Routing
• Each router has complete network picture
– Topology
– Link costs

• How does each router get the global state?

– Each router reliably floods information about its
neighbors to every other router (more later)
• Each router independently calculates the
shortest path from itself to every other router
– Using, for example, Dijkstra’s Algorithm

11
Link State: Control Traffic
• Each node floods its local information
• Each node ends up knowing the entire
network topology node
Host C

Host A Host D

N1 N2

N3

N5

Host B
N4 Host E

N6 N7

12
Link State: Node State

C C
A D Host C C A D
A D

Host A Host D
B B
E E
B
E

N1 N2 C
A D

N3
C
A D B
E C
N5 A D

B C
E A D
Host B B
N4 Host E E
B
N6 E
N7

13
Dijkstra’s Shortest Path Algorithm
• INPUT:
– Network topology (graph), with link costs

• OUTPUT:
– Least cost paths from one node to all other nodes
– Produces “tree” of routes (why?)

14
Notation

• c(i,j): link cost from node i

to j; cost infinite if not
direct neighbors; ≥ 0
• D(v): current value of cost 5
of path from source to
destination v B
3
C
2 5
• p(v): predecessor node A
along path from source to 2 1 F
3
v, that is next to v 1
2
D E
• S: set of nodes whose 1
least cost path definitively
known
Source
15
Dijsktra’s Algorithm
• c(i,j): link cost from node i to j
1 Initialization:
2 S = {A}; • D(v): current cost source  v
3 for all nodes v • p(v): predecessor node along
4 if v adjacent to A path from source to v, that is
5 then D(v) = c(A,v); next to v
6 else D(v) = ∞; • S: set of nodes whose least
7 cost path definitively known
8 Loop
9 find w not in S such that D(w) is a minimum;
10 add w to S;
11 update D(v) for all v adjacent to w and not in S:
12 if D(w) + c(w,v) < D(v) then
// w gives us a shorter path to v than we’ve found so far
13 D(v) = D(w) + c(w,v); p(v) = w;
14 until all nodes in S;

16
Example: Dijkstra’s Algorithm
Step start S D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F)
0 A 2,A 5,A 1,A ∞ ∞
1
2
3
4
5

5 1 Initialization:
2 S = {A};
B 3 C 3 for all nodes v
2 5
4 if v adjacent to A
A 2 1 F 5 then D(v) = c(A,v);
3
1 2 6 else D(v) = ∞;
D E …
1

17
Example: Dijkstra’s Algorithm
Step start S D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F)
0 A 2,A 5,A 1,A ∞ ∞
1
2
3
4
5
…
5 8 Loop
3 9 find w not in S s.t. D(w) is a minimum;
B C 10 add w to S;
2 5
11 update D(v) for all v adjacent
A 2 1 F
3 to w and not in S:
1 2 • If D(w) + c(w,v) < D(v) then
D E • D(v) = D(w) + c(w,v); p(v) = w;
1
14 until all nodes in S;
18
Example: Dijkstra’s Algorithm
Step start S D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F)
0 A 2,A 5,A 1,A ∞ ∞
1 AD
2
3
4
5
…
5 8 Loop
3 9 find w not in S s.t. D(w) is a minimum;
B C 10 add w to S;
2 5
11 update D(v) for all v adjacent
A 2 1 F
3 to w and not in S:
1 2 • If D(w) + c(w,v) < D(v) then
D E • D(v) = D(w) + c(w,v); p(v) = w;
1
14 until all nodes in S;
19
Example: Dijkstra’s Algorithm
Step start S D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F)
0 A 2,A 5,A 1,A ∞ ∞
1 AD 4,D 2,D
2
3
4
5
…
5 8 Loop
3 9 find w not in S s.t. D(w) is a minimum;
B C 10 add w to S;
2 5
11 update D(v) for all v adjacent
A 2 1 F
3 to w and not in S:
1 2 • If D(w) + c(w,v) < D(v) then
D E • D(v) = D(w) + c(w,v); p(v) = w;
1
14 until all nodes in S;
20
Example: Dijkstra’s Algorithm
Step start S D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F)
0 A 2,A 5,A 1,A ∞ ∞
1 AD 4,D 2,D
2 ADE 3,E 4,E
3
4
5
…
5 8 Loop
3 9 find w not in S s.t. D(w) is a minimum;
B C 10 add w to S;
2 5
11 update D(v) for all v adjacent
A 2 1 F
3 to w and not in S:
1 2 • If D(w) + c(w,v) < D(v) then
D E • D(v) = D(w) + c(w,v); p(v) = w;
1
14 until all nodes in S;
21
Example: Dijkstra’s Algorithm
Step start S D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F)
0 A 2,A 5,A 1,A ∞ ∞
1 AD 4,D 2,D
2 ADE 3,E 4,E
3 ADEB
4
5
…
5 8 Loop
3 9 find w not in S s.t. D(w) is a minimum;
B C 10 add w to S;
2 5
11 update D(v) for all v adjacent
A 2 1 F
3 to w and not in S:
1 2 • If D(w) + c(w,v) < D(v) then
D E • D(v) = D(w) + c(w,v); p(v) = w;
1
14 until all nodes in S;
22
Example: Dijkstra’s Algorithm
Step start S D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F)
0 A 2,A 5,A 1,A ∞ ∞
1 AD 4,D 2,D
2 ADE 3,E 4,E
3 ADEB
4 ADEBC
5
…
5 8 Loop
3 9 find w not in S s.t. D(w) is a minimum;
B C 10 add w to S;
2 5
11 update D(v) for all v adjacent
A 2 1 F
3 to w and not in S:
1 2 • If D(w) + c(w,v) < D(v) then
D E • D(v) = D(w) + c(w,v); p(v) = w;
1
14 until all nodes in S;
23
Example: Dijkstra’s Algorithm
Step start S D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F)
0 A 2,A 5,A 1,A ∞ ∞
1 AD 4,D 2,D
2 ADE 3,E 4,E
3 ADEB
4 ADEBC
5 ADEBCF
…
5 8 Loop
3 9 find w not in S s.t. D(w) is a minimum;
B C 10 add w to S;
2 5
11 update D(v) for all v adjacent
A 2 1 F
3 to w and not in S:
1 2 • If D(w) + c(w,v) < D(v) then
D E • D(v) = D(w) + c(w,v); p(v) = w;
1
14 until all nodes in S;
24
Example: Dijkstra’s Algorithm
Step start S D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F)
0 A 2,A 5,A 1,A ∞ ∞
1 AD 4,D 2,D
2 ADE 3,E 4,E
3 ADEB
4 ADEBC
5 ADEBCF
5
3 To determine path A  C (say),
B C
2 5 work backward from C via p(v)
A 2 1 F
3
1 2
D E
1

25
The Forwarding Table
• Running Dijkstra at node A gives the shortest
path from A to all destinations
• We then construct the forwarding table

5
Destination Link
3 B (A,B)
B C
2 5
C (A,D)
A 2 1 F
3
1 D (A,D)
2
D E
1 E (A,D)

F (A,D)

26
Complexity

• How much processing does running the

Dijkstra algorithm take?
• Assume a network consisting of N nodes
– Each iteration: check all nodes w not in S
– N(N+1)/2 comparisons: O(N2)
– More efficient implementations: O(N log(N))

27
Obtaining Global State
• Flooding
– Each router sends link-state information out its links
– The next node sends it out through all of its links
o except the one where the information arrived
o Note: need to remember previous msgs & suppress duplicates!

X A X A

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

X A X A

C B D C B D
(c) (d) 28
Flooding the Link State
• Reliable flooding
– Ensure all nodes receive link-state information
– Ensure all nodes use the latest version

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

• Solutions
– Acknowledgments and retransmissions
– Sequence numbers
29
When to Initiate Flooding
• Topology change
– Link or node failure
– Link or node recovery
• Configuration change
– Link cost change
– Potential problems with making cost dynamic!
• Periodically
– Refresh the link-state information
– Typically (say) 30 minutes
– Corrects for possible corruption of the data
30
Oscillating Load-Dependent Routing
• Assume link cost = amount of carried traffic
– All traffic sent to A

1 A A A A
1+e 2+e 0 0 2+e 2+e 0
D 0 0 B D 1+e 1 B D 0 0 B D 1+e 1 B
0 e 0 0 1 1+e 0 e
C C C C
1 1
e
… recompute … recompute … recompute
initially routing
0 A
0
D 0 0 B
Very Hard to AvoidCOscillations!

31
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
32
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

33
Convergence Delay
• Time elapsed before every router has a consistent
picture of the network
• Sources of convergence delay
– Detection latency
– Flooding of link-state information
– Recomputation of forwarding tables
• 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
34
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
35
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

B C B C

A F A F

D E Loop! D E

A and D think that this E thinks that this

is the path to C is the path to C
36
Scaling Link-State Routing
• Overhead of link-state routing
– Flooding link-state packets throughout the network
– Running Dijkstra’s shortest-path algorithm
– Becomes unscalable when 100s of routers
• Introducing hierarchy through “areas”

Area 1 Area 2

area Area 0
border
router
Area 3 Area 4
37
Link-State Routing Is Conceptually Simple
• Each router keeps track of its incident links
– Link cost, and whether the link is up or down

• Each router broadcasts the link state

– To give every router a complete view of the graph

• Each router runs Dijkstra’s algorithm

– Compute shortest paths, then construct forwarding table

• Example protocols
– Open Shortest Path First (OSPF)
– Intermediate System – Intermediate System (IS-IS)

• Challenges: scaling, transient disruptions

– Any ideas for improvement? 38
Question
• Why use different routing algorithms at L2 and L3?
– Is Link-State “plug-and-play”?
– Could we make it “plug-and-play?”

39
 5 Minute Break

Questions Before We Proceed?

40
Feedback on Course
• Course moving: • Include History/Politics:
– Too slowly: 13% – Yes: 76%
– Too quickly: 30%
– OK:
• Include worked ex’s:
57%
– Yes: 82%
• Lectures should be:
– Harder:
• Project is:
18%
– Too easy: 11%
– Easier: 26%
– Too hard: 33%
– Same: 56%
– OK: 56%
• Homework should be:
– Harder:
• Support in Section
33%
– Yes: 80%
– Easier: 13%
– Don’t go: 12%41
– Same: 54%
Selected Comments
• Use newsgroups
• Weekly homeworks
• Relate project to course
• Don't skip break
• Test too easy
• Bspace is evil
• “Cancel the project and final, buy us dinner”
• “Make lectures less boring”
42
More Scalable Routing Algorithms?
• Avoid need for global state consistency
• Just focus on computing routes
• Distribute the computation, not the state….

43
Distance Vector Routing
• Each router knows the links to its neighbors
– Does not flood this information to the whole network
• Each router has provisional “shortest path”
– E.g.: Router A: “I can get to router B with cost 11 via
next hop router D”
• Routers exchange this information with their
neighboring routers
– Again, no flooding the whole network
• Routers update their idea of the best path using
info from neighbors
• This iterative process converges with set of
shortest paths 44
Information Flow in Distance Vector

Host C

Host A Host D

N1 N2

N3

N5

Host B
N4 Host E

N6 N7

45
Information Flow in Distance Vector

Host C

Host A Host D

N1 N2

N3

N5

Host B
N4 Host E

N6 N7

46
Information Flow in Distance Vector

Host C

Host A Host D

N1 N2

N3

N5

Host B
N4 Host E

N6 N7

47
Why Is This Different From Flooding?

48
Bellman-Ford Algorithm

• INPUT:
– Link costs to each neighbor
– Not full topology

• OUTPUT:
– Next hop to each destination and the
corresponding cost
– Does not give the complete path to the
destination

49
Bellman-Ford - Overview
• Each router maintains a table
– Row for each possible destination Each node:
– Column for each directly-attached
neighbor to node wait for (change in local link
– Entry in row Y and column Z of node X cost or msg from neighbor)
 best known distance from X to Y, via

Z as next hop = DZ(X,Y)

recompute distance table
• Each local iteration caused by:
– Local link cost change
– Message from neighbor if least cost path to any dest
has changed, notify
• Notify neighbors only if least cost
neighbors
path to any destination changes
– Neighbors then notify their neighbors if
necessary
50
Bellman-Ford - Overview
• Each router maintains a table
– Row for each possible destination
– Column for each directly-attached
neighbor to node
– Entry in row Y and column Z of node X
 best known distance from X to Y, via

Z as next hop = DZ(X,Y)

Neighbor
Node A (next-hop)
B C
B 3 D B 2 8
2 1
1 C 3 7
A C
7 D 4 8

Destinations DC(A, D)
Bellman-Ford - Overview
• Each router maintains a table
– Row for each possible destination
– Column for each directly-attached
neighbor to node
– Entry in row Y and column Z of node X
 best known distance from X to Y, via

Z as next hop = DZ(X,Y)

Node A
B C
B 3 D B 2 8
2 1
1 C 3 7
A C
7 D 4 8

Smallest distance in row Y = shortest

Distance of A to Y, D(A, Y)
Distance Vector Algorithm (cont’d)
1 Initialization:
2 for all neighbors V do • c(i,j): link cost from node i to j
3 if V adjacent to A • DZ(A,V): cost from A to V via Z
4 D(A, V) = c(A,V);
• else • D(A,V): cost of A’s best path to V
• D(A, V) = ∞;
• send D(A, Y) to all neighbors
loop:
8 wait (until A sees a link cost change to neighbor V /* case 1 */
9 or until A receives update from neighbor V) /* case 2 */
10 if (c(A,V) changes by ±d) /*  case 1 */
11 for all destinations Y that go through V do
12 DV(A,Y) = DV(A,Y) ± d
13 else if (update D(V, Y) received from V) /*  case 2 */
/* shortest path from V to some Y has changed */
14 DV(A,Y) = DV(A,V) + D(V, Y); /* may also change D(A,Y) */
15 if (there is a new minimum for destination Y)
16 send D(A, Y) to all neighbors 53
17 forever
 Example:1st Iteration (C  A)
Node A Node B
B C A C D
B 2 8 A 2 ∞ ∞
B 3 D
2 C ∞ 7 C ∞ 1 ∞
1
A 1 D ∞ 8 D ∞ ∞ 3
C
7
DC(A, B) = DC(A,C) + D(C, B) = 7 + 1 = 8
DC(A, D) = DC(A,C) + D(C, D) = 7 + 1 = 8
Node C Node D
loop:
… A B D B C
else if (update D(A, Y) from C) A 7 ∞ ∞ A ∞ ∞
DC(A,Y) = DC(A,C) + D(C, Y);
B ∞ 1 ∞ B 3 ∞
if (new min. for destination Y)
send D(A, Y) to all neighbors D ∞ ∞ 1 C ∞ 1
forever
 Example: 1st Iteration (B  A)
Node A Node B
B C A C D
B 2 8 A 2 ∞ ∞
B 3 D
2 C 3 7 C ∞ 1 ∞
1
A 1 D 5 8 D ∞ ∞ 3
C
7
DB(A, C) = DB(A,B) + D(B, C) = 2 + 1 = 3
DB(A, D) = DB(A,B) + D(B, D) = 2 + 3 = 5
Node C Node D
loop:
… A B D B C
else if (update D(A, Y) from B) A 7 ∞ ∞ A ∞ ∞
DB(A,Y) = DB(A,B) + D(B, Y);
B ∞ 1 B 3 ∞
if (new min. for destination Y)
send D(A, Y) to all neighbors D ∞ ∞ 1 C ∞ 1
forever
 Example: End of 1st Iteration
Node A Node B
B C A C D
B 2 8 A 2 3 ∞
B 3 D
2 C 3 7 C 9 1 4
1
A 1 D 5 8 D ∞ 2 3
C
7

Node C Node D
End of 1 Iteration
st
A B D B C
All nodes knows A 7 3 ∞ A 5 8
the best two-hop B 9 1 4 B 3 2
D ∞ 4 1 C 4 1
paths
 Example: 2nd Iteration (A  B)
Node A Node B
B C A C D
B 2 8 A 2 3 ∞
B 3 D
2 C 3 7 C 5 1 4
1
A 1 D 5 8 D 7 2 3
C
7
DA(B, C) = DA(B,A) + D(A, C) = 2 + 3 = 5
DA(B, D) = DA(B,A) + D(A, D) = 2 + 5 = 7
Node C Node D
loop:
… A B D B C
else if (update D(B, Y) from A) A 7 3 ∞ A 5 8
DA(B,Y) = DA(B,A) + D(A, Y);
B 9 1 4 B 3 2
if (new min. for destination Y)
send D(B, Y) to all neighbors D ∞ 4 1 C 4 1
forever
 Example: End of 2nd Iteration
Node A Node B
B C A C D
B 2 8 A 2 3 11
B 3 D
2 C 3 7 C 5 1 4
1
A 1 D 4 8 D 7 2 3
C
7

Node C Node D
End of 2 Iteration
nd
A B D B C
All nodes knows the A 7 3 6 A 5 4
best three-hop B 9 1 4 B 3 2
D 12 4 1 C 4 1
paths
 Example: End of 3rd Iteration
Node A Node B
B C A C D
B 2 8 A 2 3 6
B 3 D
2 C 3 7 C 5 1 4
1
A 1 D 4 8 D 7 2 3
C
7

Node C Node D

End of 2nd Iteration: A B D B C

A 7 3 5 A 5 4
Algorithm B 9 1 4 B 3 2
Converges! D 11 4 1 C 4 1
 Distance Vector: Link Cost Changes
loop:
8 wait (until A sees a link cost change to neighbor V
9 or until A receives update from neighbor V) / 1
10 if (c(A,V) changes by ±d) /*  case 1 */ B
11 for all destinations Y that go through V do 4 1
12 DV(A,Y) = DV(A,Y) ± d
13 else if (update D(V, Y) received from V) /*  case 2 */
A C
14 DV(A,Y) = DV(A,V) + D(V, Y);
50
15 if (there is a new minimum for destination Y)
16 send D(A, Y) to all neighbors
17 forever

Node B A C A C A C A C
“good
A 4 6 A 1 6 A 1 6 A 1 3
news
C 9 1 C 9 1 C 9 1 C 3 1
travels
Node C A B A B A B A B fast”
A 50 5 A 50 5 A 50 2 A 50 2
B 54 1 B 54 1 B 51 1 B 51 1
time 60
Link cost changes here Algorithm terminates
 DV: Count to Infinity Problem
loop:
8 wait (until A sees a link cost change to neighbor V
9 or until A receives update from neighbor V) /
10 if (c(A,V) changes by ±d) /*  case 1 */ 60
11 for all destinations Y that go through V do B
12 DV(A,Y) = DV(A,Y) ± d 4 1
13 else if (update D(V, Y) received from V) /*  case 2 */ A C
14 DV(A,Y) = DV(A,V) + D(V, Y); 50
15 if (there is a new minimum for destination Y)
16 send D(A, Y) to all neighbors
17 forever

Node B A C A C A C A C
A 4 6 A 60 6 A 60 6 A 60 8 “bad
C 9 1 C 9 1 C 9 1 C 9 1 news
Node C A B A B A B A B travels
A 50 5 A 50 5 A 50 7 A 50 7 … slowly”
B 54 1 B 54 1 B 101 1 B 101 1

time 61
Link cost changes here
 Distance Vector: Poisoned Reverse
• If B routes through C to get to A: 60
B
- B tells C its (B’s) distance to A is infinite 4 1
(so C won’t route to A via B) A C
- Will this completely solve count to infinity 50
problem?

Node B A C A C A C A C A C
A 4 6 A 60 6 A 60 6 A 60 51 A 60 51
C 9 1 C 9 1 C 9 1 C 9 1 C 9 1

Node C A B A B A B A B A B
A 50 5 A 50 5 A 50 ∞ A 50 ∞ A 50 ∞
B ∞ 1 B ∞ 1 B ∞ 1 B ∞ 1 B ∞ 1

time
Link cost changes here; C updates D(C, A) = 60 as Algorithm terminates
B has advertised D(B, A) = ∞ 62
Routing Information Protocol (RIP)
• Simple 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., campus

63
Question
• Can we solve the count-to-infinity problem?

• Do we need to solve the count-to-infinity problem?

64
Summary
• Routing is a distributed algorithm
– Different from forwarding
– React to changes in the topology
– Compute the shortest paths
• Two main shortest-path algorithms
– Dijkstra  link-state routing (e.g., OSPF, 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: BGP
– Reading: K&R 4.6.3
65