CP372
Computer Networks
Routing Principles, Link State
Routing
Routing Principles
2
Routing: “Best” Path
• Routing: Determine “best” paths (routes),
from sending hosts to each receiving host,
through network of routers
• path: sequence of routers that packets Forwarding
will traverse as they flow from a given
initial source host to a given final
destination host
• “best”: least “cost”, “fastest”, “least
congested”
• Executed by a routing protocol
• Once finished, each router populates its Source Router
routing table with the next hop (i.e., next
router) on the identified good path from Destination Router
sending hosts to receiving hosts
3
Routing: Graph Abstraction
• The network of routers is abstracted
as a graph G(V,E)
• V: 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) }
• Distance: d(x,x’) = ”distance” of link 5
(x,x’) (e.g., d(w,z) = 5) 3
v w
• Inversely related to bandwidth 2 5
• Directly related to congestion u 2 1 z
3
1 2
• Routing: Finding the “shortest” x y
1
path between any pair of vertices in
the graph
4
Routing: Algorithm Classification
Global routing:
• Computes the least-cost path between a source and destination
using complete, global knowledge about the network
• The algorithm takes the connectivity between all nodes and all
link costs as inputs
Decentralized routing :
• No node has complete information about the costs of all
network links
• Instead, each node begins with only the knowledge of the costs
of its own directly attached links
• Then, through an iterative process of calculation and exchange
of information with its neighboring nodes to which it is directly
connected, a node gradually calculates the least-cost path to a
destination or set of destinations
5
Routing: Algorithm Classification
Static routing:
• Routes change very slowly over time.
• Often as a result of human intervention (for example, a human
manually editing a router’s forwarding table)
Dynamic routing :
• Routes change as the network traffic loads or topology change
• A dynamic routing algorithm can be run either periodically or in
direct response to topology or link cost changes
• Dynamic algorithms are more responsive to network changes
6
Routing: Algorithm Classification
Q: global or decentralized information?
Q: static or dynamic?
Global: Static:
• All routers have the complete graph • Routes change slowly
topology and link distances over time
• “Link state (LS)” algorithms: Iterative
selection of routes to destinations Dynamic:
• Routes change more
Decentralized: quickly
• Router knows distances to physically- – Periodic update
connected neighbors – In response to link
• “Distance vector (DV) ” algorithms: cost changes
Iterative process of route computing
and exchange with neighbors
7
Link State Routing
8
Link State Routing
• The network topology and all link costs are known, that is,
available as input to the LS algorithm
• In practice this is accomplished by having each node broadcast
link-state packets to all other nodes in the network, with each
link-state packet containing the identities and costs of its
attached links (link-state broadcast)
• The result of the nodes’ broadcast is that all nodes have an
identical and complete view of the network
• Each node can then run the LS algorithm and compute the same
set of least-cost paths as every other node
9
Link State Routing- Dijkstra’s Algorithm
• An example of a link-state routing algorithm is known as
Dijkstra’s algorithm, named after its inventor
• Dijkstra’s algorithm computes the least-cost path from one node
(the source) to all other nodes in the network
• Dijkstra’s algorithm is iterative
• After the kth iteration of the algorithm, the least-cost paths are
known to k destination nodes
10
Example 1
D(v) D(w) D(x) D(y) D(z) D(i): current distance of path
Step N' p(v) p(w) p(x) p(y) p(z) from source to destination i
0 u 7,u 3,u 5,u ∞ ∞ N': set of nodes whose least cost
1 uw 6,w 5,u 11,w ∞ path definitively known
2 uwx 6,w 11,w 14,x p(i): predecessor node along
3 uwxv 10,v 14,x path from source to i
4 uwxvy 12,y x
5 uwxvyz 9
5 7
Note: 4
Ties (i.e., two distances being
the same) can exist. Those 3 8
u w y z
are broken arbitrarily. 2
3
7 4
11
v
Link State Routing- Dijkstra’s Algorithm
Algorithm from source node u. N is the set of all nodes.
12
Example 2
D(v) D(w) D(x) D(y) D(z)
Step N' p(v) p(w) p(x) p(y) p(z)
0 u 2,u 5,u 1,u ∞ ∞
1 u, x 2,u 4,x 2,x ∞
2 u, x, y 2,u 3,y 4,y
3 u, x, y, v 3,y 4,y
4 u, x, y, v, w 4,y
5
5 u, x, y, v, w, z
v 3 w
2 5
u 2 1 z
3
1
x y 2
1
13
Example 2
Resulting shortest-path tree from u:
Resulting forwarding table in u:
v w
destination Link
u z v (u,v)
x y x (u,x)
y (u,x)
w (u,x)
z (u,x)
14
15
