After reading this article you will learn about the two popular routing algorithms: 1. Dijkstra’s Algorithm 2. Bellman-Ford Algorithm.
1. Dijkstra’s Algorithm:
Almost all packet-switching networks base their routing on some form of packet-switching network. Most least-cost algorithms in use in packet-switching networks and in the internet are variations of either Dijkstra’s Algorithm or the Bellman-Ford Algorithm. In Dijkstra’s Algorithm, one first finds the shortest paths from a given source node to all other nodes by developing the path in order of increasing path length.
The algorithm proceeds in stages. By the nth stage the shortest path to the n nodes closest to (or least cost away from) the source node have been determined. These–nodes are in a set T. At stage n + 1 the node not in T that has the shortest path from the source node is added to T and its path from the source is defined.
This logic is represented below:
ADVERTISEMENTS:
N = set of nodes in the network
s = source node
T = set of nodes so far incorporated by the algorithm
w(i, j) = link cost from node i to node j; w(i, i) = 0; w(i, j) = ∞ if the two nodes are not directly connected; w(i, j) ≥ 0 if the two nodes are directly connected
ADVERTISEMENTS:
L(n) = cost of the least-cost path from node s to node n that is currently known to the algorithm; at termination, this is the cost of the least-cost path in the graph from s to n.
The algorithm works in three steps; steps 2 and 3 are repeated until final paths have been assigned to all nodes in the network, that is until T = N.
The three steps are:
1. Initialization:
ADVERTISEMENTS:
T = {s} that is, the set of nodes so far incorporated consists of only the source node
L(n) = w(s, n) for n, s
2. Get Next Node:
Find the next neighbouring node if it is not in T and it has the least-cost path from s and incorporate it into T. Also incorporate the edge that is incident on that node and a node in T that contributes to the path or expressed mathematically:
Add x to T; add to T the edge that is incident on x and that contributes the least-cost component to L(x), that is, the last hop in the path.
3. Update Least Cost Paths:
If the latter term is the minimum, the path from s to n is now the path from s to x concatenated with the edge from x to n. The algorithm concludes when all the nodes have been added to T, that is, when all the nodes have been incorporated. At this time the value of L(x) associated with each node x is the cost or the length of the least-cost path from s to x. In addition, T defines the least-cost path from s to each node.
2. Bellman-Ford Algorithm:
ADVERTISEMENTS:
This is the second of the two popular algorithms. The logic of this algorithm is to find the shortest paths from a given source node subject to the constraint that the paths contain at most one link, then find the shortest with a constraint of paths of at most two links, and so on. Obviously, the execution of this logic proceeds in stages.
In mathematical terms it is expressed as follows:
s = source code
w(i, j) = link cost from node i to node j; w(i, i) — 0; w(i, j) = ∞ if the two nodes are not directly connected; w(i, j) ≥ 0 if the two nodes are directly connected
h — maximum number of links in a path at the current stage of the algorithm
Lh(n) = cost of the least-cost path from node s to node n under the constraint of no more than h links
1. Initialization:
2. Update:
For each successive h ≥ 0; For each n ≠ s, compute
Connect n with the predecessor node j that achieves the minimum and eliminate any connection of n with a different predecessor node formed during an earlier iteration. The path from s to n terminates with the link from j to n.
The iterations are described further. For iterations in step 2 when h = K, and for each iteration node n, the algorithm compares potential paths from iteration.
If the previous shorter path has less cost than that path is retained s to n of length K + 1 with the path that existed at the end of the previous else a new path with length K + 1 is defined from s to n; this path consists of a path of length K from 5 to some node j, plus a direct hop from node j to node n. In this case, the path from s to j that is used is the K-hop path for j defined in the earlier iteration.
Comparisons between Dijkstra’s algorithm and Bellman-Ford algorithm are interesting. These deal with what information needs to be gathered. In step 2 of Bellman-Ford algorithm, the calculation for node n involves knowledge of the link cost to all neighbouring nodes to node n [that is, w(j, n)] plus the total path cost to each of those neighbouring nodes from a particular source node s [that is, Lh(j)].
Each node maintains some information; prime amongst the information maintained are a set of costs and associated paths for every other node in the network and also exchanging this information with its immediate neighbours from time to time.
Each node can, therefore, use the expression in step 2 of the Bellman-Ford mentioned above algorithm. Execution of step 2 of the Bellman-Ford algorithm will be based only on information from the neighbouring nodes and knowledge of its link costs, to update its costs and paths.
Now consider Dijkstra’s algorithm. In step 3 of the algorithm, it is required that each node must have complete topological information about the network. Therefore, each node must know the link costs of all the links in the network. This information can be obtained only from exchange of information with all the other nodes.
This becomes a prime requirement for the working of this algorithm. Other issues of comparison regarding the relative merits of the two algorithms require consideration of the processing time of the two algorithms and the amount of information that is needed to be collected from the other nodes of the network.
The overall evaluation of the two algorithms will also depend upon the approach to implementation and the specific implementation. Both algorithms are static algorithms. Therefore, it is no surprise that they converge under static conditions of topology.
If the link costs change over time, the algorithms will try to catch up with the changes. But, there is a rider over this. If the link costs depend upon traffic, which may in turn depend upon the selected routes, then a feedback situation will exist. This situation may be called one of congestion and may lead to instabilities.