Definition of Routing Algorithm in Network Encyclopedia.
What is Routing Algorithm (in computer networking)?
Routing Algorithm is a mathematical procedure that a dynamic router uses to calculate entries for its routing table.
How does Routing Algorithm work?
Routing algorithms are implemented as software running within the internal CPU of a router. They are implemented as a routing protocol because they involve procedures and protocols that allow routers to exchange information with one another in order to calculate the metrics of various paths or routes through an internetwork. Routing algorithms base their work off the values contained in a combination of variables. These values can be determined dynamically by inspecting header information in packets directed toward the router, or they can be manually specified by network administrators. The routing algorithm then processes the values of these variables to generate the internal routing table for the router. 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 algorithms are usually implemented as a combination of dynamic (real-time calculated) and static (specified by the network administrator) factors. Algorithms are usually implemented in a distributed fashion, with each router independently calculating its own routing tables, and in the case of dynamic routers, exchanging routing information with each other as well. This provides a degree of fault tolerance for the routing network: If one router goes down, all other routers can reconfigure their routing tables to route traffic around the failed router. When the failed router is restored, the routing tables are recalculated. Some routing algorithms support forwarding packets over several paths to a given destination (when such multiple paths exist). They can thus better manage network traffic by load balancing packets accordingly.
One major distinction between routing algorithms involves the space within which they operate. In a flat routing space, all routers are peers, while in a hierarchical routing space, different routing domains, areas, or autonomous systems are connected using a backbone routing network. The advantage of a hierarchical routing space is that it reduces the amount of intercommunication traffic that must take place between routers in order for them to calculate their routing tables. For example, routers that forward traffic only within their own routing table do not need to exchange routing information with routers in other domains. The downside, of course, is that a hierarchical system is much more difficult to implement and maintain than a flat routing space.
From a mathematical point of view, routing algorithms come in two common types: link state routing algorithms and distance vector routing algorithms. A link state routing algorithm is a hierarchical routing space algorithm that forms the basis of the Open Shortest Path First (OSPF) Protocol, while a distance vector routing algorithm is a flat routing space algorithm that forms the basis of the Routing Information Protocol (RIP). From a network administrator’s perspective, the differences between these algorithms are as follows:
- A routing protocol based on the distance vector routing algorithm is simpler to implement than one based on the link state routing algorithm. Link state algorithms require more processing power, and routers that implement it are generally more costly.
- Routing loops are less likely to occur when the link state algorithm is used.
- The two algorithms offer a trade-off with respect to network traffic between routers. Specifically, routers using the distance vector algorithm periodically send their entire routing table to other routers, but only to routers one hop away, while the link state algorithm floods the entire internetwork with information from each router, but only updated information is sent when needed.
