University Institute of
Engineering
DEPARTMENT OF COMPUTER
SCIENCE & ENGINEERING
Bachelor of Engineering
(Computer Science & Engineering)
Subject Name: Computer Network
Subject Code: CSH-312/ ITH-312
Prepared By :Er. Monika(E9911)
DISCOVER . LEARN .
EMPOWER
Department of Computer and Science Engineering (CSE)
Routing Algorithms
The main function of NL (Network Layer) is routing packets
from the source machine to the destination machine.
There is Routing Algorithm to accomplish Routing.
Certain properties are desirable in a Routing algorithm
correctness, simplicity, robustness, stability, fairness,
optimality
• Routing algorithms can be grouped into two major
classes:
– Nonadaptive (Static Routing)
– Adaptive. (Dynamic Routing)
University Institute of Engineering (UIE)
Categories of Routing Algorithms
• Nonadaptive algorithm do not base their routing decisions on
measurements or estimates of the current traffic and topology.
Instead, the choice of the route is computed in [Link]
procedure is sometimes called static routing.
• Adaptive algorithm in contrast, change their routing decisions to
reflect changes in the topology, and usually the traffic as well.
Adaptive algorithms differ in:
-Where they get their information (e.g., locally, from adjacent routers, or from all
routers),
-When they change the routes (e.g., every ∆T sec, when the load changes or when
the topology changes), and
-What metric is used for optimization (e.g., distance, number of hops, or estimated
transit time). This procedure is called dynamic routing
The Optimality Principle
General statement about optimal routes without regard to network topology or
traffic is known as the optimality principle.
It states that if router J is on the optimal path from router I to router K, then the
.
optimal path from J to K also falls along the same
As a direct consequence of the optimality principle, we can see that the set of
optimal routes from all sources to a given destination form a tree rooted at the
destination. Such a tree is called a sink tree. The goal of all routing algorithms is to
discover and use the sink trees for all routers.
(a) A network. (b) A sink tree for router B.
Shortest Path Routing (Dijkstra’s)
• Start with the local node (router) as the root of the tree. Assign a cost of 0
to this node and make it the first permanent node.
• Examine each neighbor of the node that was the last permanent node.
• Assign a cumulative cost to each node and make it tentative
• Among the list of tentative nodes
– Find the node with the smallest cost and make it Permanent
– If a node can be reached from more than one route then select the
route with the shortest cumulative cost.
• Repeat steps 2 to 4 until every node becomes permanent
Shortest Path Routing (Dijkstra’s)
Flooding
• It is static algorithm, in which every incoming packet is sent out on
every outgoing line except the one it arrived on.
• Flooding obviously generates vast numbers of duplicate packets
• Infinite number unless some measures are taken to damp the
process.
• One such measure is to have a hop counter contained in the header
of each packet, which is decremented at each hop, with the packet
being discarded when the counter reaches zero. Ideally, the hop
counter should be initialized to the length of the path from source to
destination.
• A variation of flooding that is slightly more practical is selective
flooding. In this algorithm the routers do not send every incoming
packet out on every line, only on those lines that are going
approximately in the right direction.
• Flooding is not practical in most applications.
Intra- and Inter domain Routing
• Routing inside an autonomous system is referred to as intra domain
routing. (DISTANCE VECTOR, LINK STATE)
• Routing between autonomous systems is referred to as inter domain
routing. (PATH VECTOR)
Department of Computer and Science Engineering (CSE)
Distance Vector Routing
• In distance vector routing, the least-cost route between
any two nodes is the route with minimum distance.
• In this protocol, as the name implies, each node
maintains a vector (table) of minimum distances to every
[Link] steps are:
-Initialization
-Sharing
-Updating
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
Distance Vector Routing
• Initialization
• Each node can know only the distance between itself and
its immediate neighbors, those directly connected to it.
So for the moment, we assume that each node can send a
message to the immediate neighbors and find the
distance between itself and these neighbors.
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
Distance Vector Routing
• Sharing
• The whole idea of distance vector routing is the sharing
of information between neighbors. Although node A does
not know about node E, node C does. So if node C shares
its routing table with A, node A can also know how to
reach node E..
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
Distance Vector Routing
Updating
• When a node receives a two-column table from a neighbor, it needs to
update its routing table. Updating takes three steps:
• The receiving node needs to add the cost between itself and the
sending node to each value in the second column. (x+y)
• If the receiving node uses information from any row. The sending node
is the next node in the route.
• The receiving node needs to compare each row of its old table with the
corresponding row of the modified version of the received table.
– If the next-node entry is different, the receiving node chooses the
row with the smaller cost. If there is a tie, the old one is kept.
– If the next-node entry is the same, the receiving node chooses the
new row.
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
Updating in Distance Vector routing
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
SOLUTIONS FOR INSTABILITY
• Defining Infinity: redefine infinity to a smaller number,
such as 100. For our previous scenario, the system will be
stable in less than 20 updates. As a matter of fact, most
implementations of the distance vector protocol define
the distance between each node to be 1 and define 16 as
infinity. However, this means that the distance vector
routing cannot be used in large systems. The size of the
network, in each direction, cannot exceed 15 hops.
• Split Horizon: In this strategy, instead of flooding the
table through each interface, each node sends only part
of its table through each interface.
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
SOLUTIONS FOR INSTABILITY
• Split Horizon and Poison Reverse Using the split
horizon strategy has one drawback. Normally, the
distance vector protocol uses a timer, and if there is no
news about a route, the node deletes the route from its
table.
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
Count to Infinity Problem
The Count-to-Infinity Problem
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
Link State Routing
• Link State Routing is a dynamic routing algorithm used in computer networks
where each router has a complete map (topology) of the network.
Each router calculates the shortest path to every other router using Dijkstra’s
shortest path algorithm.
Key Features:
• Neighborhood Knowledge: Each router shares information about its directly
connected links (cost and identity) rather than the full routing table.
• Flooding: This information is broadcast to all routers in the network so that
everyone has the same view of the topology.
• Information Sharing: Updates are sent only when changes occur (not
periodically).
• Phases of LSR:
• Reliable Flooding: Every router eventually learns the complete network graph.
• Route Calculation: Each router applies Dijkstra’s algorithm to compute the optimal
path to every other node.
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
Link State Routing
Features of Link State Routing Protocols
• Link State Packet: A small packet that contains routing
information.
• Link-State Database: A collection of information gathered
from the link-state packet.
• Shortest Path First Algorithm (Dijkstra algorithm): A
calculation performed on the database results in the shortest
path
• Routing Table: A list of known paths and interfaces.
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
Link State Routing
• Calculation of Shortest Path
• To find the shortest path, each node needs to run the famous
Dijkstra algorithm. Let us understand how can we find the
shortest path using an example.
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
Link State Routing
• STEP 1: Initially, the shortest path tree set (sptSet) is empty,
and the distances are:
{0, ∞, ∞, ∞, ∞, ∞, ∞, ∞} (where ∞ = infinity). The vertex with
the minimum distance is chosen vertex 0.
Add vertex 0 to sptSet i.e sptSet = {0}.
Update distances of vertices adjacent to 0
• Distance to vertex 1 becomes 4.
• Distance to vertex 7 becomes 8.
• So, the distance array is updated to:
{0, 4, ∞, ∞, ∞, ∞, ∞, 8}
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
Link State Routing
• Pick the vertex with minimum distance value and not already
included in SPT (not in sptSET). The vertex 1 is picked and
added to sptSet. So sptSet now becomes {0, 1}. Update the
distance values of adjacent vertices of 1. The distance value of
vertex 2 becomes 12.
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
Link State Routing
• Pick the vertex with minimum distance value and not already
included in SPT (not in sptSET). Vertex 7 is picked. So sptSet
now becomes {0, 1, 7}. Update the distance values of adjacent
vertices of 7. The distance value of vertex 6 and 8 becomes
finite (15 and 9 respectively).
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
Link State Routing
• Pick the vertex with minimum distance value and not already
included in SPT (not in sptSET). Vertex 6 is picked. So sptSet
now becomes {0, 1, 7, 6}. Update the distance values of
adjacent vertices of 6. The distance value of vertex 5 and 8 are
updated.
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
Link State Routing
• We repeat the above steps until sptSet includes all vertices of
the given graph. Finally, we get the following Shortest Path
Tree (SPT).
• Shortest Path Calculation - Step 6
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
References :
• Computer Networks, Tanenbaum, Andrew, Fifth Edition,
PHI.
• Data Communication and Networking, Behrouz A.
Forouzan, Fourth [Link]
• [Link]
University Institute of Engineering (UIE)
THANK YOU
University Institute of Engineering (UIE)