Computer and Communication Networks (paperback)

7.2. Least-Cost- Path Algorithms

In practice, the majority of Internet routing methods are based on least-cost algorithms. In such algorithms, a link cost is proportional to the links's current traffic load. However, the link cost may not always be proportional to the current load. The link cost is defined on both directions between each pair of nodes. Several least-cost-path algorithms have been developed for packet-switched networks. In particular, Dijkstra's algorithm and the Bellman-Ford algorithm are the most effective and widely used algorithms.

7.2.1. Dijkstra's Algorithm

Dijkstra's algorithm is a centralized routing algorithm that maintains information in a central location. The objective is to find the least-cost path from a given source node to all other nodes. This algorithm determines least-cost paths from a source node to a destination node by optimizing the cost in multiple iterations. Dijkstra's algorithm is as follows :

Begin Dijkstra's Algorithm

  1. Define:

    s =Source node

    k =Set of visited nodes by the algorithm

    ± ij =Cost of the link from node i to node j

    ² ij =Cost of the least-cost path from node i to node j

  2. Initialize:

    k ={ s }

    ² sj = ± sj for j s

  3. Next node:

    Find x k that ² sx = min ² sj for j k .

    Add x to k .

  4. Least-cost paths:

    ² sj = min( ² sj , ² sx + ± xj ) for j k

If any two nodes i and j are not connected directly, the cost for that link is infinity, indicated by ² ij =x. Steps 2 and 3 are repeated until paths are assigned to all nodes. At step 1, k represents s , and ² sj computes the cost of the least-cost path from s to node j . At step 2, we want to find x among the neighboring nodes but not in k such that the cost is minimized. At step 3, we simply update the least-cost path. The algorithm ends when all nodes have been visited and included in the algorithm.

Example.

Using Dijiksra's algorithm, find the least-cost path from node A to node B in Figure 7.2.

Solution.

The detailed operation is shown in the Table 7.1. The first step is to find a path from the source node A to all other nodes. Thus, at the fist row, k = {A}. It is obvious there are direct links from A to nodes C and F. Therefore, the least-cost path for either node is 1, as shown in Figure 7.2. We then fill the table with AC(1) and AF(1), respectively. Given k = { A }, there is no connections between A and nodes D, E, G, and B. The algorithm continues until all nodes have been included as k = A,C,F,E,D,G,B, and we obtain the least-cost path of ACEDB(7).

Table 7.1. Use of Dijkstra's algorithm

k

² AC

² AF

² AE

² AD

² AG

² AB

{A}

AC(1)

AF(1)

x

x

x

x

{A,C}

AC(1)

AF(1)

ACE(3)

ACD(6)

x

x

{A,C,F}

AC(1)

AF(1)

ACE(3)

ACD(6)

AFG(7)

x

{A,C,F,E}

AC(1)

AF(1)

ACE(3)

ACED(4)

AFG(7)

x

{A,C,F,E,D}

AC(1)

AF(1)

ACE(3)

ACED(4)

ACEDG(6)

ACEDB(7)

{A,C,F,E,D,G}

AC(1)

AF(1)

ACE(3)

ACED(4)

ACEDG(6)

ACEDB(7)

{A,C,F,E,D,G,B}

AC(1)

AF(1)

ACE(3)

ACED(4)

ACEDG(6)

ACEDB(7)

7.2.2. Bellman-Ford Algorithm

The Bellman-Ford algorithm finds the least-cost path from a source to a destination by passing through no more than links. The essence of the algorithm consists of the following steps

Begin Bellman-Ford Algorithm

  1. Define:

    s = Source node

    ± ij = Cost of the link from node i to node j

    ² ij ( ) = Cost of the least-cost path from i to j with no more than links

² sj ( 0)

=

x, for all j s

² ss ( )

=

0, for all

Least-cost path:

for any node j s with predecessor node i :

² sj ( + 1) = min i [ ² si ( ) + ± ij ]

If any two nodes i and j are not connected directly, ² ij ( ) =x. At step 2, every value of ² is initialized . At step 3, we increase the number of links in a sequence of iterations. During each iteration, we find the least-cost path, given the value of . The algorithm ends when all nodes have been visited and included in the algorithm.

Example.

Use the Bellman-Ford algorithm to find the least-cost path from node A to node B in Figure 7.2.

Solution.

Table 7.2 shows the details of least-cost-path iterations. For iteration = 1, only AC with cost 1 and AF with cost 1 exist, owing to the restriction enforced by = 1. This trend changes at iteration = 2, when ACE with cost 3 can be added to the set of least-cost paths. As seen, the result of the final least-cost path is identical to the one obtained by Dijkstras algorithm.

Table 7.2. Use of the Bellman-Ford algorithm

² AC

² AF

² AE

² AD

² AG

² AB

x

x

x

x

x

x

1

AC(1)

AF(1)

x

x

x

x

2

AC(1)

AF(1)

ACE(3)

ACD(6)

AFG(7)

x

3

AC(1)

AF(1)

ACE(3)

AED(4)

AFG(7)

ACDB(9)

4

AC(1)

AF(1)

ACE(3)

AED(4)

ACEG(6)

ACEDB(7)

We can now compare these two algorithms. In step 2 of Bellman-Ford, the calculation of the link cost to any node j requires knowledge of the link cost to all neighboring nodes. In step 3 of Dijkstra's algorithm, each node requires knowledge of the network topology at each time of iteration. The performance of each algorithm varies network to network and depends on the topology and size of a particular network. The comparison of these two algorithms, therefore, depends on the speed of each to achieve its objective at its corresponding step given a network under routing. A simulation can clarify the efficiency of each algorithm given a certain network topology.

Related

Категории