Accuracy is perhaps the most general design goal, which refers to the capability of the routing algorithm to select the best route. The best route depends upon the metric(s) and metric weightings used to make the calculation. These metrics differ for each protocol and, as such, must be clearly defined and understood to assist in their proper deployment.
For example, one routing algorithm might use a number of hops and network delay as its metrics but might place more weight or consideration on delay during route calculation. Naturally, routing protocols must strictly define their metric calculation algorithms. In addition, these parameters must be clearly documented as they are implemented or modified. This is of course basic common sense, but this does not seem to be in common practice. The best bedtime reading for those suffering from insomnia is RFCs that cover this in great detail for every routing protocol.
Routing algorithms are usually designed to be as simple as possible. This means that routing algorithms should offer their functionality efficiently, with a minimum of software, CPU, and memory utilization. Efficiency is particularly important when the software implementing the routing algorithm must run on a router or other device that has limited physical resources. Although some people might disagree, the fact remains that not every company can afford, or is willing to buy, the latest and greatest technology available. Nor is it always advisable to do so from a technical perspective. Routing algorithms constantly perform routing calculations and exchange routing information with other network devices. These actions, if done inefficiently, can add significant traffic to a network.
Routing algorithms must be robust in their operation and route calculations. In other words, they must not malfunction by giving erroneous routes to a destination. The goal, of course, is to make this happen as infrequently as possible. Because routers are located at network junction points, they can cause considerable problems when they fail. The best routing algorithms are often those that have withstood the test of time and proven stable under a variety of network conditions.
Routing algorithms must be able to converge rapidly. Convergence is the process of agreement/notification, by or to all routers, on optimal or changed routes. When a network event causes routes to either go up or down or discovers new ones, routers will distribute routing update messages. Routing update messages permeate networks, consequently stimulating recalculation by the routing algorithm of optimal routes and eventually causing all routers to agree on these routes (convergence). Routing algorithms that converge slowly can cause routing loops.
An example of a routing loop is as follows: A packet arrives at Router A at time t1. Router A has already been updated and knows that the optimal route to the destination calls for Router B to be the next hop. Router A therefore forwards the packet to Router B. Router B has not yet been updated and so believes that the optimal next hop is Router A. Router B therefore forwards the packet back to Router A. The packet will continue to bounce back and forth between the two until Router B receives its routing update or the packet is discarded because it is too old.
Routing algorithms should also be flexible in their operation. In other words, routing algorithms need to adapt quickly and accurately to a variety of network circumstances. These circumstances can be any condition you would expect to find within a network, such as changes in routing tables, topology, connectivity, and so forth.
Suppose, for example, that a network link (circuit) such as a T1 has gone down. Many routing algorithms, upon becoming aware of this situation, will quickly select the next-best path for all routes normally using that link (circuit). Well-designed, flexible routing algorithms can be programmed to adapt to changes in network bandwidth, router buffer size, network delay, and other variables.
Routing Algorithm Types
Routing algorithms might be classified according to type. For example, algorithms might be:
Static Routing Algorithms(?)
Static routing algorithms are hardly algorithms at all. Static routing table mappings are established by the network administrator before the beginning of routing. They do not change unless the network administrator changes them. Algorithms that use static routes are simple to design and work well in environments in which network traffic is relatively predictable and network design is relatively simple. However, when the network grows in complexity or its needs change, the true drawbacks of this method are seen.
Because static routing systems cannot react to network changes, they are generally considered unsuitable for todays large, constantly changing networks. Most of the dominant routing algorithms in the 1990s are dynamic.
Dynamic Routing Algorithms
Dynamic routing algorithms adjust to changing network circumstances by analyzing incoming routing update messages. If the routing update message indicates that a network change has occurred, the routing software recalculates routes and sends out new routing update messages. These messages permeate the network, stimulating routers to rerun their routing algorithms and change their routing tables to reflect information contained in the update message.