Centralized and Distributed Routing Algorithms
Routing algorithms may be centralized or distributed. Centralized algorithms calculate all routing paths at one central device. This device is often called a Routing Control Center (RCC). The RCC periodically collects routing information from all routers and distributes optimal routing tables to them.
Centralized routing has several advantages. First, it relieves individual routers of the burden of route calculation. Second, it virtually ensures that all routing tables are the same.
Unfortunately, centralized routing also suffers from several serious flaws that have severely restricted its use. If any RCC should go down, the entire network is helpless or must, at best, rely on old routing tables. Lines leading to the RCC must have exceptionally high bandwidth because they will experience heavy utilization. Finally, depending on the size and hierarchical organization of the internetwork, routers close to the RCC may receive updated information well in advance of distant routers, creating routing loops.
Distributed algorithms calculate routing paths at each individual router. Each router periodically exchanges route information with (at a minimum) each of its neighbors. Distributed algorithms are more fault-tolerant than centralized algorithms. They also distribute update traffic over the entire network, so traffic bottlenecks are not such a serious problem. Like centralized routing, they might still generate routing loops. Overall, distributed routing algorithms are much more common than centralized routing algorithms.
Multi-Path and Single-Path Routing Algorithms
Some sophisticated routing protocols support multiple paths to the same destination. These multi-path algorithms permit traffic multiplexing over multiple lines; single-path algorithms do not. The advantages of multi-path algorithms are obvious; they can provide substantially better throughput and redundancy.
Flat and Hierarchical Routing Algorithms
Some routing algorithms operate in a flat space, and others use routing hierarchies. In a flat routing system, all routers are peers of all others. In a hierarchical routing system, some routers form what amounts to a routing backbone. Packets from non-backbone routers travel to the backbone routers, where they are sent through the backbone until they reach the general area of the destination. At this point, they travel from the last backbone router through zero or more non-backbone router(s) to the final destination.
Routing systems often designate logical groups of nodes called domains, autonomous systems, or areas. In hierarchical systems, some routers in a domain can communicate with routers in other domains; others can only communicate with routers within their domain. In very large networks, additional hierarchical levels might exist. Routers at the highest hierarchical level form the routing backbone.
The primary advantage of hierarchical routing is its capability to limit the pervasiveness of routing exchanges. Hierarchical routing limits routing exchanges because it mimics the organization of most companies and therefore supports their traffic patterns very well. Most network communication occurs within small company groups (domains).
Host-Intelligent or Router-Intelligent Routing Algorithms
Some routing algorithms assume that the source end-node will determine the entire route. This is usually referred to as source routing. In source routing systems, routers merely act as store-and-forward devices, mindlessly sending the packet to the next stop.
Other algorithms assume that the hosts know nothing about routes. In these algorithms, routers determine the path through the internetwork based on their own calculations.
In the first system, the hosts have the routing intelligence. In the latter system, routers have the routing intelligence.
The tradeoff between host-intelligent and router-intelligent routing is one of path optimality versus traffic overhead. Host-intelligent systems choose the better routes more often, because they typically discover all possible routes to the destination before the packet is actually sent. They then choose the best path based on that particular systems definition of optimal. The act of determining all routes, however, often requires substantial discovery traffic and a significant amount of time.
Intradomain and Interdomain Routing Algorithms
As discussed previously, some routing algorithms work only within domains; others work within and between domains. The nature of these two algorithm types is different. It stands to reason, therefore, that an optimal intradomain routing algorithm would not necessarily be an optimal interdomain routing algorithm.