A mathematical procedure that a dynamic router uses to calculate entries for its routing table.
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:
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: