Least Cost Algoritm

Least Cost Algoritm

VIRTUALLAYL L PACKET-SWITCHED networks base their routing decision on some form

of least-cost criterion. If the criterion is to minimize the number of hops, each link has a value

of 1. More typically, the link value is inversely proportional to the link capacity, proportional

to the current load on the link, or some combination of the two. In any case, these link or hop

costs are used as input to a least-cost routing algorithm, which can be simply stated as

follows:

Given a network of nodes connected by bidirectional links, where each link has a cost associated

with it in each direction, define the cost of a path between two nodes as the sum of

the costs of the links traversed. For each pair of nodes, find the path with the least cost.

Note that the cost of a link may differ in its two directions; this would be true, for example,

if the cost of a link equaled the length of the queue of packets awaiting transmission from

each of the two nodes on the link.

Most least-cost routing algorithms in use in packet-switched networks are variations of

one of two common algorithms, known as Dijkstra's algorithm and the Bellman-Ford algorithm.'

This lesson provides a summary of these two algorithms.

Dijkstra's Algorithm

Dijkstra's algorithm [DIJK59] can be stated as: Find the shortest paths from a given source

node to all other nodes by developing the paths in order of increasing path length. The algorithm

proceeds in stages. By the kth stage, the shortest paths to the k nodes closest to (least

cost away from) the source node have been determined; these nodes are in a set M. At stage

(k + 1), the node not in M that has the shortest path from the source node is added to M. As

each node is added to M, its path from the source is defined. The algorithm can be formally

described as follows. Use the following definitions:

One iteration of steps 2 and 3 adds one new node to M and defines the least-cost path

from s to that node. That path passes only through nodes that are in M; to see this, consider

the following line of reasoning. After k iterations, there are k nodes in M, and the least-cost

path from s to each of these nodes has been defined. Now consider all possible paths from s

to nodes not in M. Among those paths, there is one of least cost that passes exclusively

through nodes in M (see Problem 9.7), ending with a direct link from some node in M to a

node not in M. This node is added to M, and the associated path is defined as the least-cost

path for that node.

Table 9.4a shows the result of applying this algorithm to Figure 9.5, using s = 1. Note

that at each step, the path to each node plus the total cost of that path is generated. After the

final iteration, the least-cost path to each node and the cost of that path have been developed.

The same procedure can be used with node 2 as source node, and so on.

Bellman-Ford Algorithm

The Bellman-Ford algorithm [FORD621 can be stated as follows: 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 paths with a constraint of paths of, at most, two links, and so on. This

algorithm also proceeds in stages. The algorithm can be formally described as follows. Use

the following definitions:

For the iteration of step 2 with h = K, and for each destination node n, the algorithm

compares potential paths from s to n of length K + 1 with the path that existed at the end of

the previous iteration. If the previous, shorter, path has less cost, then that path is retained.

Otherwise, a new path with length K + 1 is defined from s to n; this path consists of a path

of length K from s 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 previous iteration (see Problem

9.8).

update its costs and paths. On the other hand, consider Dijkstra's algorithm. Step 3 appears

to require that each node must have complete topological information about the network.

That is, each node must know the link costs of all links in the network. Thus, for this algorithm,

information must be exchanged with all other nodes.

Evaluation of the relative merits of the two algorithms should be done with respect to

the processing time of the algorithm and the amount of information that must be collected

from other nodes in the network. The evaluation will depend on the implementation

approach and on the specific implementation.

A final point: Both algorithms are known to converge under static conditions of topology

and link costs and will converge to the same solution. If the link costs change over time,

the algorithm will attempt to catch up with these changes. However, if the link cost depends

on traffic, which in turn depends on the routes chosen, then a feedback condition exists, and

instabilities may result.