Routing Algorithms

One of the main functions of the network layer is routing packets from source to destination. Network layer uses routing algorithms to decide which outgoing path should be selected for incoming packets. If network use datagram approach then the router may choose a different path for each incoming packet, since the best route may changed since last time. If network use virtual circuit then routing decisions are only made when a new virtual circuit is being set up. After that all packets are follow same route.

There exist several routing algorithms, which can be grouped into two classes: non-adaptive and adaptive. Non-adaptive algorithms do not look to current traffic and topology while making decisions; instead, they use routing tables that are downloaded at the booting time to make decisions. Therefore, this procedure also known as static routing. Adaptive routing algorithms change their routing decisions based on the topology and traffic.  

Some of the routing methods are discuss below,

Shortest Path Routing

In this mechanism, a graph of subnet is build with each node of the graph representing a router and each arc of the graph representing communication line. To select a route between a given pair of routers, the shortest path algorithm selects the shortest path between them on the graph. The meaning of the term shortest depend upon the algorithm, some select the route with less number of hops, some select the route with less distant and so on. One example of shortest path algorithm is Dijkstra’s algorithm (1959).  

Flooding

The idea is, sent every incoming packet to every outgoing line except the one arrived on. Flooding increase the congestion on the network, another problem is that it generates large number of duplicate packets. To deal with this several measure are used, one of them is to have a hop counter contained in the header of each packet, the count is decrement at each node or router, the packet being discarded when the count reaches to zero. For optimal functioning, the hoop counter should be initialized to the length of the path from source node to destination node. If it is not possible or sender does not know how long the path is, then hop counter initialize to worst case that is diameter of the subnet. Flooding is a static routing method. 

Distance Vector Routing

Distance vector routing algorithms operate by using a routing table. Each router maintains a table giving the best distance to each hop and which line use to reach there. The routing tables are uploaded dynamically by exchanging data with the other routers especially neighbors. The distance vector routing algorithm is also known as Bellman-Ford routing algorithm. It was the original ARPANET routing algorithm.

Link State Routing

Link-state routing algorithms use the following steps to generate routing table,

1.    Discover the neighbors and learn their network address

2.    calculate the delay or cost to each of its neighbors

3.    Construct a packet which include all information it has just learned

4.    Forward his packet to all other routers.

5.    By using the received packet each router, compute the shortest path to every other router in the network.

6.    Use this table to take routing decisions. 

Hierarchical Routing

In the case of large network, the network may structure hierarchically. It may be necessary to group the routers into regions, and regions into clusters, the cluster into zones, the zones into groups and so on. Kamoun and Kleinrock (1979) discovered that optimal number of levels for an N router subnet is lnN requires a total of elnN entries per router.

Another two routing algorithms are Broadcast routing and Multicast Routing.

 Next : NETWORK DEVICES (15-01-2013)

Previous : Bit Stuffing and Byte Stuffing
Index :   Computer Networks and Communication online coaching