Routing Algorithm

Routing Algorithm

Routing is process of establishing the routes that data packets must follow to reach the destination. In this process, a routing table table is created which contains information regarding routes which data packets follow. Various routing algorithm are used for the purpose of deciding which route an incoming data packet needs to be transmitted on to reach destination efficiently.

Classification of Routing Algorithms: The routing algorithms can be classified as follows:

1.    Adaptive Algorithms –
These are the algorithms which change their routing decisions whenever network topology or traffic load changes. The changes in routing decisions are reflected in the topology as well as traffic of the network. Also known as dynamic routing, these make use of dynamic information such as current topology, load, delay, etc. to select routes. Optimization parameters are distance, number of hops and estimated transit time.

2.     Non-Adaptive Algorithms –
These are the algorithms which do not change their routing decisions once they have been selected. This is also known as static routing as route to be taken is computed in advance and downloaded to routers when router is booted.

**Performance criteria of routing algorithm

The variables are generally known as routing metrics and can include the following:

·          Hops: The number of intermediate routers between a given network and the local router 

·           Latency: The time delay in processing a packet through the router or over a given route 

• Congestion: The length of the packet queue at the incoming port of the router 
• Load: The processor use at the router or the number of packets per second that it is currently processing 
• Bandwidth: The available capacity of a route to support network traffic; decreases as network traffic increases 
• Reliability: The relative amount of downtime that a particular router might experience because of malfunctions 
• Maximum Transmission Unit (MTU): The largest packet size that the router can forward without needing to fragment the packet 

**Routing Strategies :

• Fixed Routing
• Flooding
• Dynamic Routing
• Random Routing
• Flow-based Routing                                                                                                              

Fixed Routing –
·       A route is selected for each source and destination pair of node in the network.

·       The route is fixed ; changes only if the topology of the network changes.

Fixed Routing : Example (1)

·       Figure – A simple packet switching network with six nodes (routers)

Figure – Central routing table based on least cost path algorithm

• A Central routing matrix is created based on the least-cost path which is stored in the network control center
• The matrix, shows for each source-destination of the route , the identity of the next node on the route.
• Drawback: If the network control center fails, then everything will collapse. Hence it is not reliable.
• Fixed Routing : Example (2)
• 

Figure – Routing table stored in different nodes of the network

• Routing Table is created for each node. This is called a distributed routing algorithm
• Routing table can be created using least-min path or min-hop reach method. Two famous path algorithms
  1. Dijkstra Algorithm
  2. Bellman Ford Algorithm

Advantages –

• Simple
• Works well in reliable network with stable load in reliable network
• Same for virtual circuit and datagram

Disadvantages –

• Lack of flexibility
• Doesn’t react to failure or network congestion

Reference: https://www.geeksforgeeks.org/