What is Shortest Path Routing?
It refers to the algorithms that help to find the shortest path between a sender and receiver for
routing the data packets through the network in terms of shortest distance, minimum cost, and
minimum time.
It is mainly for building a graph or subnet containing routers as nodes and edges as
communication lines connecting the nodes.
Hop count is one of the parameters that is used to measure the distance.
Hop count: It is the number that indicates how many routers are covered. If the hop count is 6,
there are 6 routers/nodes and the edges connecting them.
Another metric is a geographic distance like kilometers.
We can find the label on the arc as the function of bandwidth, average traffic, distance,
communication cost, measured delay, mean queue length, etc.
Common Shortest Path Algorithms
Dijkstra’s Algorithm
Bellman Ford’s Algorithm
Floyd Warshall’s Algorithm
Dijkstra’s Algorithm
The Dijkstra’s Algorithm is a greedy algorithm that is used to find the minimum distance
between a node and all other nodes in a given graph. Here we can consider node as a router and
graph as a network. It uses weight of edge .ie, distance between the nodes to find a minimum
distance route.
Algorithm:
1: Mark the source node current distance as 0 and all others as infinity.
2: Set the node with the smallest current distance among the non-visited nodes as the current
node.
3: For each neighbor, N, of the current node:
Calculate the potential new distance by adding the current distance of the current node with the
weight of the edge connecting the current node to N.
If the potential new distance is smaller than the current distance of node N, update N's current
distance with the new distance.
4: Make the current node as visited node.
5: If we find any unvisited node, go to step 2 to find the next node which has the smallest current
distance and continue this process.
Example:
Consider the graph G:
Graph G
Now,we will start normalising graph one by one starting from node 0.
step 1
Nearest neighbour of 0 are 2 and 1 so we will normalize them first .
step 3
Similarly we will normalize other node considering it should not form a cycle and will keep track
in visited nodes.
Flooding algorithm
Flooding is a non-adaptive routing technique following this simple method: when a data packet
arrives at a router, it is sent to all the outgoing links except the one it has arrived on.
For example, let us consider the network in the figure, having six routers that are connected
through transmission lines.
Using flooding technique
An incoming packet to A, will be sent to B, C and D.
B will send the packet to C and E.
C will send the packet to B, D and F.
D will send the packet to C and F.
E will send the packet to F.
F will send the packet to C and E.
Types of Flooding
Flooding may be of three types
Uncontrolled flooding Here, each router unconditionally transmits the incoming data packets to
all its neighbours.
Controlled flooding They use some methods to control the transmission of packets to the
neighbouring nodes. The two popular algorithms for controlled flooding are Sequence Number
Controlled Flooding (SNCF) and Reverse Path Forwarding (RPF).
Selective flooding Here, the routers don't transmit the incoming packets only along those paths
which are heading towards approximately in the right direction, instead of every available paths