Routing algorithms

By: Laurent Patrice

Faculty of Science and Technology
Mzumbe University
 Network routing
• Network routing is the process of selecting the best path for
data packets to travel from a source to a destination host across
a network
 It is a critical function in communication networks, ensuring
data reaches its intended destination efficiently, reliably, and
accurately
 A routing algorithm is a set of rules or a procedure used in
computer networks to find the most efficient path for data
packets to travel from a source to a destination
 Routing algorithms calculate the "least-cost" route based on
metrics like distance, bandwidth, or congestion.
Laurent Patrice Mzumbe University
 Network routing…
 These algorithms are fundamental to directing internet traffic,
helping routers make decisions to forward data quickly and reliably
across interconnected networks.
 Routing determines the most suitable path for transmitting data
between devices based on factors such as:
 Hop Count - The simplest cost, counting the number of routers
(hops) a packet passes through; each hop adds 1 to the cost
 Bandwidth - Faster links (higher bandwidth) have lower costs
 Delay/Load - Metrics can include transmission delay, queueing
delay, or link utilization
 Policy/Administrative Weight - Administrators manually assign
costs or weights to influence path selection, overriding automatic
metrics.
Laurent Patrice Mzumbe University
 Routing algorithm
• Routing relies on algorithms to
determine the best path for data
transfer
• The routing algorithm goal is to
determine the best paths from
sending host to receiving host
through network of routers
• Path: sequence of routers
packets traverse from given initial
source host to final destination
host
Laurent Patrice Mzumbe University
Laurent Patrice Mzumbe University
 Routing algorithm classification
Global: all routers have a complete
topology, link cost information
• “Link state” algorithms

Dynamic: Routes change

How fast Static: routes more quickly
do routes change slowly • Periodic updates or
change? over time due to link cost
changes

Decentralized: iterative process of computation, exchange of

information with neighbors
• Routers initially know only link costs to attached neighbors
• “Distance vector” algorithms

Laurent Patrice Mzumbe University

 Routing algorithm classification…
• One way in which we can classify routing algorithms is according to
whether they are global or decentralized.
• A global routing algorithm computes the least-cost path between a source
and destination using complete, global knowledge about the network.
• That is, the algorithm takes the connectivity between all nodes and all link
costs as inputs.
• This then requires that the algorithm somehow obtain this information
before actually performing the calculation.
• The calculation itself can be run at one site (a centralized global routing
algorithm) or replicated at multiple sites.
• The key distinguishing feature here, however, is that a global algorithm has
complete information about connectivity and link costs.
• Algorithms with global state information are often referred to as link-state
(LS) algorithms, since the algorithm must be aware of the cost of each link
in the network

Laurent Patrice Mzumbe University

 Routing algorithm classification…
• In a decentralized routing algorithm, the calculation of the least-cost path is
carried out in an iterative, distributed manner.
• No node has complete information about the costs of all network links.
 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 (that is, nodes that are at the other
end of links to which it itself is attached), a node gradually calculates the
least-cost path to a destination or set of destinations.
• The decentralized routing algorithm is called a distance-vector (DV)
algorithm, because each node maintains a vector of estimates of the costs
(distances) to all other nodes in the network

Laurent Patrice Mzumbe University

 Routing algorithm classification…
• The second way to classify routing algorithms is according to whether
they are static or dynamic.
• In static routing algorithms, 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 algorithms change the routing paths as the network
traffic loads or topology change.
• A dynamic algorithm can be run either periodically or in direct
response to topology or link cost changes.

Laurent Patrice Mzumbe University

 Routing algorithm classification…
• The third way to classify routing algorithms is according to whether
they are load sensitive or load-insensitive.
• In a load-sensitive algorithm, link costs vary dynamically to reflect the
current level of congestion in the underlying link.
• If a high cost is associated with a link that is currently congested, a
routing algorithm will tend to choose routes around such a congested
link

Laurent Patrice Mzumbe University

 Link-state Routing Algorithm
• Recall that in a link-state algorithm, the network topology and all link
costs are known, that is, available as input to the LS algorithm.
 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
• 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.
• The link-state routing algorithm is known as Dijkstra’s
algorithm
Laurent Patrice Mzumbe University
• Dijkstra’s algorithm computes the least-cost path from one node (the
source) to all other nodes in the network
• The algorithm is iterative and has the property that after the kth iteration
of the algorithm, the least-cost paths are known to k destination nodes,
and among the least-cost paths to all destination nodes, these k paths
will have the k smallest costs.
• Let us define the following notation:
 D(v): cost of the least-cost path from the source node to destination v
as of this iteration of the algorithm.
 p(v): previous node (neighbor of v) along the current least-cost path
from the source to v.
 N’ : subset of nodes; v is in N’ if the least-cost path from the source to
v is definitively known

Laurent Patrice Mzumbe University

• The global routing algorithm consists of an initialization step followed by a
loop.
• The number of times the loop is executed is equal to the number of nodes
in the network.
• Upon termination, the algorithm will have calculated the shortest paths
from the source node to every other node in the network.

Laurent Patrice Mzumbe University

• As an example, let’s consider the network in this Figure and compute the least-cost
paths from node u to all possible destinations
• A tabular summary of the algorithm’s computation is shown in the next slides,
where each line in the table gives the values of the algorithm’s variables at the end
of the iteration

Laurent Patrice Mzumbe University

Initialization step:
• In the initialization step, the currently known least-cost paths
from u to its directly attached neighbors, v, x, and w, are
initialized to 2, 1, and 5, respectively.
• Note in particular that the cost to “w” is set to 5 (even
though we will soon see that a lesser-cost path does indeed
exist) since this is the cost of the direct (one hop) link from
“u” to “w”.
• The costs to “y” and “z” are set to infinity because they are
not directly connected to “u”.

Laurent Patrice Mzumbe University

The first iteration:
• In the first iteration, we look among those nodes not yet added to the set
N’ and find that node with the least cost as of the end of the previous
iteration.
• That node is “x”, with a cost of 1, and thus x is added to the set N’.
• Line 12 of the LS algorithm is then performed to update D(v) for all nodes
v, yielding the results shown in the second line (Step 1) in Table.
 The cost of the path to v is unchanged.
 The cost of the path to w (which was 5 at the end of the initialization)
through node x is found to have a cost of 4. Hence this lower-cost path
is selected and w’s predecessor along the shortest path from u is set to
x.
 Similarly, the cost to y (through x) is computed to be 2, and the table is
updated accordingly.
Laurent Patrice Mzumbe University
The second iteration:
• In the second iteration, nodes “v” and “y” are found to have the least-cost
paths (2), and we break the tie arbitrarily and add node y to the set N’ so
that N’ now contains u, x, and y.
• The cost to the remaining nodes not yet in N’, that is, nodes v, w, and z,
are updated via line 12 of the LS algorithm, yielding the results shown in
the third row in the Table.

• The iteration continues to all other nodes

Laurent Patrice Mzumbe University

• When the LS algorithm terminates, we have, for each node, its
predecessor along the least-cost path from the source node.

• In this manner we can construct the entire path from the source to all
destinations.
• The forwarding table in a node, say node “u”, can then be constructed
from this information by storing, for each destination, the next-hop node
on the least-cost path from “u” to the destination

Laurent Patrice Mzumbe University

• The figure below summarizes the least-cost path from the source node
“u” to all other nodes.

Laurent Patrice Mzumbe University

Exercise 1:
Apply the Dijkstra's algorithm and identify the least-cost routes
from source node “A” to all other nodes.

Laurent Patrice Mzumbe University

Exercise 2:
Apply the Dijkstra's algorithm and construct the routing table
of node C for the following network graph.

Laurent Patrice Mzumbe University

 Distance-Vector (DV) Routing Algorithm
• Whereas the Link-State algorithm is an algorithm using global information,
the distance vector (DV) algorithm is iterative, asynchronous, and distributed
 It is distributed in that each node receives some information from one or
more of its directly attached neighbors, performs a calculation, and then
distributes the results of its calculation back to its neighbors
It is iterative in that this process continues on until no more information
is exchanged between neighbors
 Is asynchronous in that it does not require all of the nodes to operate in
lockstep with each other
 Each router sends its distance vector to its neighbors independently,
when there is a change in the routing table (e.g., a link cost changes).
 Neighboring routers process these updates as they receive them,
without requiring global synchronization
Laurent Patrice Mzumbe University
Laurent Patrice Mzumbe University
Laurent Patrice Mzumbe University
• The DV follows three steps to compute the least-cost path

Laurent Patrice Mzumbe University

• Consider this network setup:

• Let us construct the routing table for Node A to all other nodes

Laurent Patrice Mzumbe University

• Initial routing tables for each node
Router A Router B
Destination Distance Next hop Destination Distance Next hop
A 0 A A 1 A
B 1 B B 0 B
C 2 C C 6 C
D ∞ - D 3 D

Router C Router D
Destination Distance Next hop Destination Distance Next hop
A 2 A A ∞ -
B 6 B B 3 B
C 0 - C 4 C
D 4 D D 0 -

Laurent Patrice Mzumbe University

• The first iteration when router “A” receives a routing table from its
neighbor “B”
Router A Router B

Destination Distance Next hop Destination Distance

A 0 A A 1
B 1 B B 0
C 2 C C 6
D ∞ - D 3

• The computed routing table for router “A” will be as shown below
Destination Distance Next hop
A 0 A
B 1 B
C 7 B
D 4 B

Laurent Patrice Mzumbe University

• The second iteration when router “A” receives a routing table from
its neighbor “C”
Router A Router C

Destination Distance Next hop Destination Distance

A 0 A A 2
B 1 B B 6
C 2 C C 0
D ∞ - D 4

• The computed routing table for router “A” will be as follows

Destination Distance Next hop
A 0 A
B 8 C
C 2 C
D 6 C

Laurent Patrice Mzumbe University

• Combine the two routing tables to identify the minimum distance
from “A” to other nodes
Routing table from first iteration Routing table from second iteration

Destination Distance Next hop Destination Distance Next hop

A 0 A A 0 A
B 1 B B 8 C
C 7 B C 2 C
D 4 B D 6 C

• The updated routing table for router “A” will be:

Destination Distance Next hop
A 0 A
B 1 B
C 2 C
D 4 B

Laurent Patrice Mzumbe University

• Exercise 1: Apply the Distance Vector algorithm to construct
a routing table for node C

Laurent Patrice Mzumbe University

• Exercise 2: Discuss the strength and weaknesses of Link State
and Distance Vector algorithms

Laurent Patrice Mzumbe University