Network Layer:Routing
Routing protocols mobile network
national or global ISP
Routing protocol goal: determine
“good” paths (equivalently, routes),
from sending hosts to receiving host, application
transport
through network of routers network
link
physical
▪ path: sequence of routers packets network
link
physical
network
link
physical
traverse from given initial source host
to final destination host network
link
physical
network
link
▪ “good”: least “cost”, “fastest”, “least
physical network
link datacenter
physical network
congested”
▪ routing: a “top-10” networking
application
transport
network
challenge! enterprise
network
link
physical
11.2 INTRA- AND INTERDOMAIN ROUTING
Today, an internet can be so large that one routing protocol cannot
handle the task of updating the routing tables of all routers.
For this reason, an internet is divided into autonomous systems.
An autonomous system (AS) is a group of networks and routers
under the authority of a single administration.
Routing inside an autonomous system is called intra-domain
routing.
Routing between autonomous systems is called inter-domain routing
Popular routing protocols
Bellman Ford Algorithm Dijktra Algorithm
Routing algorithm classification
global: all routers have complete
topology, link cost info
• “link state” algorithms
How fast
dynamic: routes change
do routes static: routes change more quickly
change? slowly over time • periodic updates or in
response to link cost
changes
decentralized: iterative process of
computation, exchange of info with neighbors
• routers initially only know link costs to
attached neighbors
• “distance vector” algorithms
global or decentralized information?
Graph abstraction: link costs
5
ca,b: cost of direct link connecting a and b
v 3 w e.g., cw,z = 5, cu,z = ∞
2 5
u 2 1 z
3 cost defined by network operator:
1 2
x y could always be 1, or inversely related
1
to bandwidth, or inversely related to
congestion
graph: G = (N,E)
N: set of routers = { u, v, w, x, y, z }
E: set of links ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }
Dijkstra’s link-state routing algorithm
▪ centralized: network topology, link notation
costs known to all nodes
▪ cx,y: direct link cost from
• accomplished via “link state node x to y; = ∞ if not direct
broadcast” neighbors
• all nodes have same info
▪ D(v): current estimate of cost
▪ computes least cost paths from one of least-cost-path from source
node (“source”) to all other nodes to destination v
• gives forwarding table for that node ▪ N': set of nodes whose least-
cost-path definitively known
▪ iterative: after k iterations, know
least cost path to k destinations
Dijkstra’s link-state routing algorithm
1 Initialization:
2 N' = {u} /* compute least cost path from u to all other nodes */
3 for all nodes v
4 if v adjacent to u /* u initially knows direct-path-cost only to direct neighbors */
5 then D(v) = cu,v /* but may not be minimum cost! */
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) + cw,v )
13 /* new least-path-cost to v is either old least-cost-path to v or known
14 least-cost-path to w plus direct-cost from w to v */
15 until all nodes in N'
Dijkstra’s algorithm: an example
5
v 3 w
2 5
u 2 1 z
3
1 2
x 1
y
Initialization (step 0): For all a: if a adjacent to then D(a) = cu,a
find a not in N' such that D(a) is a minimum
add a to N'
update D(b) for all b adjacent to a and not in N' :
D(b) = min ( D(b), D(a) + ca,b )
Dijkstra’s algorithm: an example
5
v 3 w
2 5
u 2 1 z
3
1 2
x 1
y
resulting least-cost-path tree from u: resulting forwarding table in u:
destination outgoing link
v w
v (u,v) route from u to v directly
u z x (u,x)
y (u,x) route from u to all
x y w (u,x) other destinations
x (u,x) via x
Dijkstra’s algorithm: another example
x
9
5 7
4
8
3 w z
u y
2
3
7 4
v
Dijkstra’s algorithm: discussion
algorithm complexity: n nodes
▪ each of n iteration: need to check all nodes, w, not in N
▪ n(n+1)/2 comparisons: O(n2) complexity
message complexity:
▪ each router must broadcast its link state information to other n routers
▪ each router’s message crosses O(n) links: overall message complexity: O(n2)
Dijkstra’s algorithm: oscillations possible
▪ when link costs depend on traffic volume, route oscillations possible
▪ sample scenario:
• routing to destination a, traffic entering at b, c, d with rates 1, e (<1), 1
• link costs are directional, and volume-dependent
a 2+e
a a 2+e a
1 1+e 0 0 2+e 0
d b d 1+e 1 b d 0 0
b d 1+e 1 b
0 0
e 1 0 1 1 1 0
1 0
c c 0 1 c 1+e 1 0 1
1 c
e e e
e
given these costs, given these costs, given these costs,
initially find new routing…. find new routing…. find new routing….
resulting in new costs resulting in new costs resulting in new costs
Distance vector algorithm
Based on Bellman-Ford (BF) equation:
Bellman-Ford equation
Let Dx(y): cost of least-cost path from x to y.
Then:
Dx(y) = minv { cx,v + Dv(y) }
v’s estimated least-cost-path cost to y
min taken over all neighbors v of x direct cost of link from x to v
Bellman-Ford Example
Suppose that u’s neighboring nodes, x,v,w, know that for destination z:
Dv(z) = 5 Dw(z) = 3 Bellman-Ford equation says:
5
Du(z) = min { cu,v + Dv(z),
3 w
v 5 cu,x + Dx(z),
2
u 2 1 z cu,w + Dw(z) }
3
1 2
= min {2 + 5,
x 1
y 1 + 3,
5 + 3} = 4
Dx(z) = 3
node achieving minimum (x) is
next hop on estimated least-
cost path to destination (z)
Distance vector algorithm
key idea:
▪ from time-to-time, each node sends its own distance vector estimate
to neighbors
▪ when x receives new DV estimate from any neighbor, it updates its
own DV using B-F equation:
Dx(y) ← minv{cx,v + Dv(y)} for each node y ∊ N
Distance vector algorithm:
each node: iterative, asynchronous: each local
iteration caused by:
wait for (change in local link ▪ local link cost change
cost or msg from neighbor) ▪ DV update message from neighbor
recompute DV estimates using distributed, self-stopping: each
node notifies neighbors only when
DV received from neighbor its DV changes
▪ neighbors then notify their
if DV to any destination has neighbors – only if necessary
changed, notify neighbors ▪ no notification received, no
actions taken!
y
2 1
x z
7
A graph for Bellman-Ford algorithm
When to Share Routing Table
◼ Periodic Update
◼ A node sends its routing table, normally 30
seconds, in a periodic update
◼ Triggered Update
◼ A node sends its routing table to its neighbors
any time when there is a change in its routing
table
◼ 1. After updating its routing table, or
◼ 2. Detects some failure in the neighboring links
Note:
In distance vector routing, each node
shares its routing table with its
immediate neighbors periodically and
when there is a change.
Figure Two-node instability
Distance vector: link cost changes
60
link cost changes: y
4 1
▪ node detects local link cost change x z
50
▪ “bad news travels slow” – count-to-infinity
problem:
• y sees direct link to x has new cost 60, but z has said it has a path at cost of 5. So
y computes “my new cost to x will be 6, via z); notifies z of new cost of 6 to x.
• z learns that path to x via y has new cost 6, so z computes “my new cost to
x will be 7 via y), notifies y of new cost of 7 to x.
• y learns that path to x via z has new cost 7, so y computes “my new cost to
x will be 8 via y), notifies z of new cost of 8 to x.
• z learns that path to x via y has new cost 8, so z computes “my new cost to
x will be 9 via y), notifies y of new cost of 9 to x.
…
▪ see text for solutions. Distributed algorithms are tricky!
