Classification of Routing Algorithms
Introduction
Before going to the classification of routing algorithms, we must find out what routing is. So, routing can be defined as the process of establishing the paths that the data packets must take to get to their destination, which is the process of routing. A routing table will be established during this process and provide details on the paths that are taken by data packets. To decide the best route for an incoming data packet to travel in order to effectively reach its destination, several different routing algorithms are utilized.
The network layer's primary responsibility is to offer the optimum route, whether it may do so through the datagram service or it would be virtual circuit service. This process will be maintained by the routing protocols. The least expensive path from the source to desired end point is the one that will be the best path.
Classification of Routing Algorithms
An algorithm for routing is majorly classified into two categories they are
Routing Algorithms are
- The Adaptive Routing algorithm
- The Non-Adaptive Routing algorithm
Let’s discuss briefly about each routing algorithm and their types further.
Adaptive Routing Algorithm
- These algorithms are often referred to as "dynamic routing algorithms," because depending upon the network and topology, the dynamic decisions will be made.
- When the network topology or traffic load is changed, then these algorithms will adjust their routing decisions accordingly. In reaction to changes in routing decisions, both the network's structure and traffic change.
- These algorithms will choose the routes based on the dynamic information such as the current topology, load, and latency, etc. The distance, the number of hops, and the estimated transit time are used as the optimization parameters.
Three more categories have been created to further separate these adaptive algorithms. They are
- Isolated
- Distributed
- Centralized
Isolated algorithm
In this isolated algorithm each node in this system decides how to route traffic based on the information at hand, rather than soliciting input from the other nodes. The state of a specific connection will be not known to the respective transmitting nodes. The drawback of this algorithm is that the sending packets across a clogged network might cause delays. Hot potato routing and backward learning are the two examples based on this algorithm.
Distributed Algorithm
The distributed algorithm is also one of the adaptive algorithms. In this strategy, the node will gather the data from its neighbor’s before deciding how to route the packets. If there is a change in the intervals at which it gets information and sends packets, the packet may be delayed, which is considered to be a drawback. As it determines the least costing route between the source and the destination, this distributed algorithm is sometimes referred to as a decentralized algorithm.
A node initially just has knowledge of its own directly connected linkages, and through an iterative computation process, it determines the least-cost route to the destination. A decentralized algorithm, a distance vector algorithm only knows the direction in which the packet is to be transmitted and the least expensive way, never knows the entire journey from source to destination.
Centralized Algorithm
It also goes by the name "global routing algorithm" since it uses comprehensive and worldwide network knowledge to determine the least-cost route between source and destination. The connection between the nodes and the link cost are retrieved by this approach as inputs before any calculations are made.
Non-Adaptive Algorithm
Static routing algorithm is another name for non-adaptive routing algorithm. Non-adaptive routing algorithms do not rely their routing choices on network traffic or topology. That means These are the algorithms that, once they have chosen a route, do not alter it. At network launch, the routers will store the routing information.
Further, this non adaptive algorithms are categorized into other two of the algorithms they are
- Flooding
- Random walk
Flooding
Every incoming packet is sent to every outgoing link during flooding, with the exception of the one that has already been reached. Flooding has the drawback that each node may have multiple copies of the same packet. Flooding algorithm is more reliable than routing and has high traffic. The only problem in this algorithm is presence of duplicate packets.
Random walk
During random walks, a packet from a node is randomly transmitted to one of its neighbors. Sending packets onto the link that has the fewest pending connections is the typical way to apply this very reliable strategy. Random walks have the benefit of making excellent use of other routes.