Goals of Today’s Lecture

• Routing overview:
–Routing topics

• Link-state routing (Dijkstra’s algorithm)

• Distance-vector routing (Bellman-Ford)

1
Routing

• Routing: “control plane”

–Computing paths the packets will follow
–Routers talking amongst themselves
–Jointly creating a forwarding table

2
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.
3
Modeling a Network
• Modeled as a graph “A graph is essentially an interrelationship of
nodes/verices connected by edges”.
– Routers  nodes 5
– Link  edges 3
B C
2 5
A 2 1 F
3
1
2
D E
1
– Generally, graphs are suited to real-world applications, such
as graphs can be used to illustrate a transportation
system/network.
– Nodes-facilities that transfer products.
– Edges – routes that connect nodes.
4
 Link State Routing Protocol
• Link-state routing protocols are one of the two main classes
of routing protocols used in packet switching networks
for computer communications, the other being distance-
vector routing protocols.
• Each router independently calculates the shortest path
from itself to every other router.
• OSPF is an example of link-state routing protocol.
• OSPF is a scalable protocol, which keeps its routing tables
efficient by segmenting the network into areas.

5
Link state example

 Link state uses Dijkstra’s Algorithm

6
Dijkstra’s Shortest Path Algorithm
• Dijkstra's Algorithm finds the shortest path between a
given node (which is called the "source node") and all
other nodes in a graph.
• This algorithm uses the weights of the edges to find the
path that minimizes the total distance (weight) between the
source node and all other nodes.

7
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
8
Dijsktra’s Algorithm
1 Initialization:
2 S = {A};
3 for all nodes v
4 if v adjacent to A
5 then D(v) = c(A,v);
6 else D(v) = ;
7
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;

9
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 12 If D(w) + c(w,v) < D(v) then
D E 13 D(v) = D(w) + c(w,v); p(v) = w;
1
14 until all nodes in S;
10
Example: Dijkstra’s Algorithm
Step start S B C D E F
0 A 2 5 1  
1 AD 4 2
2 ADE 3 4
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

11
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)

12
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)

13
Distance Vector Routing
• A distance-vector routing protocol in data networks determines
the best route for data packets based on distance.
• Distance-vector routing protocols measure the distance by the
number of routers a packet has to pass, one router counts as one
hop.
• Each router knows the links to its neighbors
– Does not flood this information to the whole network
• Routers update their idea of the best path using info from
neighbors
• This iterative process converges with set of shortest paths

• Distance-vector routing protocols use the Bellman–Ford

algorithm to calculate the best route. 14
Information Flow in Distance Vector

Host C

Host A Host D

N1 N2

N3

N5

Host B
N4 Host E

N6 N7

15
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

16
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
• Each local iteration caused by: cost or msg from neighbor)
– Local link cost change
– Message from neighbor
recompute distance table
• Notify neighbors only if least cost
path to any destination changes.
– Neighbors then notify their neighbors if if least cost path to any dest
necessary has changed, notify
neighbors

17
Bellman-Ford - Overview
• Each router maintains a table
– 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
A 1 C 3 7
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
A 1 C 3 7
C
7 D 4 8

Smallest distance in row Y = shortest

Distance of A to Y, D(A, Y)
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

• RIP is limited to fairly small networks

– E.g., campus

20
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

21