For a packet to travel from source to destination it has to pass through multiple paths or sometimes a single path. So when a packet finds multiple paths to reach the destination, it has no judging methods available to find a right path. A router with the help of certain algorithms calculates the best path for the packet to reach the destination. These algorithms are called routing algorithms. This is the way in which a router finds the correct entry in its routing table. There are several algorithms available to find this best path but here I am going to discuss only the two basic types of algorithms.
Two basic routing algorithms are,
1. Distance-vector algorithm.
2. Link state routing algorithm.
Distance vector algorithm:
As from the name suggests it uses distance and direction to find the best path to reach the destination. The distance here is the number of hops a packet crosses to reach the destination. Each hop refers to a router across the path. The word vector refers to the direction of the packet to reach the destination. It has lesser convergence time and knowledge about the whole network when compared to link state routing algorithm. Working of this distance vector algorithm can be explained in three steps. The steps are as follows,
Step 1: In this algorithm, the information about every router connected directly and routing updates will be gathered by every single router. This information about the whole network will be sent periodically to all the neighboring routers connected to it. In this way every router updates the information in its routing table.
Step 2: All the information collected by a single router about the whole network will be sent only to its neighbors and not to all other routers in the routing table. If there is any change in the hop count or disabled paths it will updated only to its neighbors which in turn after a period passes to its neighbors.
Step 3: The above explained sharing of information will take place in a period of 30 seconds. If there is a change in the network like if a network fails or additionally a router is added to the network, the changed information will be updated only after that time period.
RIP and IGRP uses distance vector routing algorithm to perform routing.
Link state routing algorithm:
This is the most popular routing algorithm used in the real time networks. It uses three tables for the calculation of the routing table entries. It is also called as 'Shortest path first algorithm'. It has several advantages over distance vector algorithm. Some of them includes, its faster convergence time, ability to handle very large networks, reliable path prediction. It uses link state advertisements to find the information about the router. Here in steps working of link state algorithm can be analyzed. The steps are,
Step 1: As from its name 'Shortest path first algorithm' it uses several calculations to find the shortest path to reach the destination. This algorithm uses link state packets or advertisements to collect the information about the neighboring routers. Only links that are connected directly are considered as neighbors. In contrast to distance vector it sends info only about neighbors.
Step 2: In this algorithm instead of sending the routing table info only to the neighbors it sends to all the routers in the network. In this algorithm totally three tables are maintained. One is for collecting info about neighbors, one has info about the entire topology, final one is the actual routing table.
Step 3: In this algorithm there is no periodic updates involved. A router in the network will send updates to all the routers and only if there is a change in the network. That is why it is called as event triggered updates. This event triggered updates will help the router to find its path immediately without any errors.
OSPF routing protocol is the perfect example which uses link state algorithm alone.
1. Hop count.
3. Administrative Distance(AD)
4. Routing loops
5. Bandwidth and delay and so on.
Hybrid routing algorithm:
Some of the vendors make use of both the routing algorithms to create better performance and reliable delivery. So this hybrid protocol uses both Distance vector and Link state algorithm to making routing decisions. EIGRP which is a Cisco proprietary protocol is a perfect example for hybrid routing algorithms. EIGRP has faster convergence and good knowledge about the whole inter-network than Distance vector routing algorithm.
The article helped me a lot to understand about algorithms.