COMPARATIVE STUDY AMONG ROUTING ALGORITHMS UNDER
DIFFERENT CIRCUMSTANCES


  COMPARATIVE STUDY AMONG ROUTING ALGORITHMS.doc (Size: 405 KB / Downloads: 0)


Introduction

The routing algorithm is used to establish the appropriate routing paths or the equivalent routing table entries in each node along a path. The routing algorithms can be classified into two major classes; non adaptive and adaptive. Nonadaptive routing algorithms do not base their routing decisions on measurements or estimates of the current traffic and topology. Instead, the choice of route is computed in advance this procedure is some times called static routing. These algorithms are simple and work well in environments where network traffic is relatively predictable and where network design is relatively simple. The most famous Non adaptive algorithms are Bifurcated, Dijkstra and Flooding routing algorithms [1].
Adaptive routing algorithms can change their routing decisions to reflect changes in topology and the traffic. Adaptive algorithms differ in where they can get their information, when change the routes and what metric is used for optimization. This procedure is some times called dynamic routing. The most famous adaptive algorithms are distance vector, page link state and Baran's routing algorithms [2, 3].


Nonadaptive routing algorithms

These algorithms don’t base their routing decisions on measurements or estimates of the current traffic, but the choice of route to get from any node I to any node J is computed in advance, off-line, and downloaded to all nodes when network is booted. Three nonadaptive routing are summarized here 1,4,5,6].


Flooding

Flooding is a very simple routing algorithm in which every incoming packet is sent out on every outgoing route except the one it arrived from. Flooding has two interesting characteristics that arise from the fact that all possible routes are tried. As long as there is a route from source to destination, the delivery of the packet is guaranteed. One copy of the packet arrives by the quickest possible route.
Flooding obviously generates vast numbers of duplicate packets. In fact, some measures are taken to damp the process. One such measure is to have a hop counter contained in the header of each packet. This counter 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. If the sender does not know how long the path is, it can initialize the counter to the worst case, namely, the full diameter of the subnet.


Adaptive Routing Algorithms

In these algorithms, routing decisions are changed to reflect any changes in topology and traffic. Adaptive algorithms differ in where they get their information (e.g., locally, from adjacent nodes, or from all nodes), when they change the routes (e.g., periodic, every load change, or when the topology changed), and the metric they used to optimize performance (e.g., distance, throughput, or estimated time delay). Three adaptive routing algorithms are summarized here [5,7,8].


Distance vector algorithm

In this algorithm, each node maintains a table (vector) giving the best known distance to each destination and which line to use. These tables are updated by exchanging the information with the neighbors. The distance vector algorithm is sometimes called the distributed Bellman-Ford routing algorithm.
In this algorithm, each node maintains a routing table indexed by, and contains one entry for each node in the network. This entry contains two parts: the preferred outgoing line to use for this destination, and an estimate of metric to that destination. This metric may be number of hops, time delay, total number of packets queued along the path, or something similar. In this algorithm, the end-to-end path is computed for each packet at all nodes. Also, in this algorithm, each node sends all information of routing table to only neighboring nodes [5].


The CPU of source and destination nodes

The CPU capability and number of CPUs of both source and destination nodes are very effective factors that the performance of all routing algorithms noticeably affected with.
Of course, improving the CPU capability leads to a positive influence on routing algorithms. Also, multiple powerful CPUs results in a positive influence on the routing algorithms. The degree of influence of this parameter on Ri has an anti-linear proportion to the increase of both data bus width and CPU's clock speed. Therefore, the following function reasonably describes this effect:


Average intermediate nodes delay

This parameter relies on bandwidth of links, number of nodes and traffic flow. There are many models that can determine average time delay. M/M/1 model is considered the simplest and efficient model that can perform this task. It is very intuitive that the more average node delay in the network, the more negative performance of the routing algorithms. Hereunder is the function that reasonably describes this effect: