Routing algorithms are software programs that implement different routing protocols. They work by assigning a cost number to each link; the cost number is calculated using various network metrics.
- In order to transfer the packets from source to the destination, the network layer must determine the best route through which packets can be transmitted.
- Whether the network layer provides datagram service or virtual circuit service, the main job of the network layer is to provide the best route. The routing protocol provides this job.
- The routing protocol is a routing algorithm that provides the best path from the source to the destination. The best path is the path that has the “least-cost path” from source to the destination.
- Routing is the process of forwarding the packets from source to the destination but the best route to send the packets is determined by the routing algorithm.
Classification of a Routing algorithm
The Routing algorithm is divided into two categories:
- Adaptive Routing algorithm
- Non-adaptive Routing algorithm
Adaptive Routing algorithm
- An adaptive routing algorithm is also known as dynamic routing algorithm.
- This algorithm makes the routing decisions based on the topology and network traffic.
- The main parameters related to this algorithm are hop count, distance and estimated transit time.
An adaptive routing algorithm can be classified into three parts:
- Centralized algorithm: It is also known as global routing algorithm as it computes the least-cost path between source and destination by using complete and global knowledge about the network. This algorithm takes the connectivity between the nodes and link cost as input, and this information is obtained before actually performing any calculation. Link state algorithm is referred to as a centralized algorithm since it is aware of the cost of each link in the network.
- Isolation algorithm: It is an algorithm that obtains the routing information by using local information rather than gathering information from other nodes.
- Distributed algorithm: It is also known as decentralized algorithm as it computes the least-cost path between source and destination in an iterative and distributed manner. In the decentralized algorithm, no node has the knowledge about the cost of all the network links. In the beginning, a node contains the information only about its own directly attached links and through an iterative process of calculation computes the least-cost path to the destination. A Distance vector algorithm is a decentralized algorithm as it never knows the complete path from source to the destination, instead it knows the direction through which the packet is to be forwarded along with the least cost path.
Non-Adaptive Routing algorithm
- Non Adaptive routing algorithm is also known as a static routing algorithm.
- When booting up the network, the routing information stores to the routers.
- Non Adaptive routing algorithms do not take the routing decision based on the network topology or network traffic.
The Non-Adaptive Routing algorithm is of two types:
Flooding: In case of flooding, every incoming packet is sent to all the outgoing links except the one from it has been reached. The disadvantage of flooding is that node may contain several copies of a particular packet.
Random walks: In case of random walks, a packet sent by the node to one of its neighbors randomly. An advantage of using random walks is that it uses the alternative routes very efficiently.
Differences between Adaptive and Non-Adaptive Routing Algorithm
| Basis Of Comparison | Adaptive Routing algorithm | Non-Adaptive Routing algorithm |
|---|---|---|
| Define | Adaptive Routing algorithm is an algorithm that constructs the routing table based on the network conditions. | The Non-Adaptive Routing algorithm is an algorithm that constructs the static table to determine which node to send the packet. |
| Usage | Adaptive routing algorithm is used by dynamic routing. | The Non-Adaptive Routing algorithm is used by static routing. |
| Routing decision | Routing decisions are made based on topology and network traffic. | Routing decisions are the static tables. |
| Categorization | The types of adaptive routing algorithm, are Centralized, isolation and distributed algorithm. | The types of Non Adaptive routing algorithm are flooding and random walks. |
| Complexity | Adaptive Routing algorithms are more complex. |
Types of Routing Protocol in Computer Networks
1. Routing information protocol (RIP)
One of the earliest protocols developed is the inner gateway protocol, or RIP. we can use it with local area networks (LANs), that are linked computers in a short range, or wide area networks (WANs), which are telecom networks that cover a big range. Hop counts are used by the Routing Information Protocol (RIP) to calculate the shortest path between networks.
2. Interior gateway protocol (IGRP)
IGRP was developed by the multinational technology corporation Cisco. It makes use of many of the core features of RIP but raises the maximum number of supported hops to 100. It might therefore function better on larger networks. IGRPs are elegant and distance-vector protocols. In order to work, IGRP requires comparisons across indicators such as load, reliability, and network capacity. Additionally, this kind updates automatically when things change, such as the route. This aids in the prevention of routing loops, which are mistakes that result in an unending data transfer cycle.
3. Exterior Gateway Protocol (EGP)
Exterior gateway protocols, such as EGP, are helpful for transferring data or information between several gateway hosts in autonomous systems. In particular, it aids in giving routers the room they need to exchange data between domains, such as the internet.
4. Enhanced interior gateway routing protocol (EIGRP)
This kind is categorised as a classless protocol, inner gateway, and distance vector routing. In order to maximize efficiency, it makes use of the diffusing update method and the dependable transport protocol. A router can use the tables of other routers to obtain information and store it for later use. Every router communicates with its neighbour when something changes so that everyone is aware of which data paths are active. It stops routers from miscommunicating with one another. The only external gateway protocol is called Border Gateway Protocol (BGP).
5. Open shortest path first (OSPF)
OSPF is an inner gateway, link state, and classless protocol that makes use of the shortest path first (SPF) algorithm to guarantee effective data transfer. Multiple databases containing topology tables and details about the network as a whole are maintained by it. The ads, which resemble reports, provide thorough explanations of the path’s length and potential resource requirements. When topology changes, OSPF recalculates paths using the Dijkstra algorithm. In order to guarantee that its data is safe from modifications or network intrusions, it also employs authentication procedures. Using OSPF can be advantageous for both large and small network organisations because to its scalability features.
6. Border gateway protocol (BGP)
Another kind of outer gateway protocol that was first created to take the role of EGP is called BGP. It is also a distance vector protocol since it performs data package transfers using the best path selection technique. BGP defines communication over the internet. The internet is a vast network of interconnected autonomous systems. Every autonomous system has autonomous system number (ASN) that it receives by registering with the Internet Assigned Numbers Authority.