Routing Algorithms

Routing algorithms are differentiated based on several key characteristics. These are as follows:

• The particular goals of the routing algorithm design affect the operation of the resulting routing protocol.

• Various types of routing algorithms exist with each algorithm having a different impact on network and router resources.

• Routing algorithms use a variety of metrics affecting route calculation.

The following sections discuss these routing algorithm attributes.

Design Goals

Routing algorithms have one or more of the following design goals:

• Optimality Refers to the ability of the routing algorithm to select the best route, depending on the metrics and metric weightings used to make the calculation. For example, a routing algorithm might use a number of hops and network delay, but the algorithm might put more weight on the delay variable than the hop count in the path calculation.

• Simplicity and low overhead The routing algorithm must offer its functionality with a minimum of software and utilization (CPU) overhead. Efficiency is important when the software implementing the routing algorithm runs on a computer with limited physical resources, such as memory (RAM).

• Robustness and stability Means the routing protocol should perform in the face of changing network conditions, such as hardware failures, high load conditions, or network outage. Because routers are located at network junction points and provide the internetwork connection, the router can cause considerable issues if there is a failure. The best routing algorithms are those that are stable under a variety of network conditions and topologies.

• Rapid convergence Convergence is the process of agreement, by all routers, on optimal routes within an internetwork. When a network event causes routes to fail or become available, routers distribute routing update messages, propagating through all attached networks, causing each internetwork router to recalculate optimal routes, in turn causing all routers to agree on these new routes. Routing algorithms converging slowly can cause routing loops or network outages.

• Flexibility The routing algorithm quickly and accurately adapts to changes in a network environment. If a network segment fails, many routing algorithms learn of the problem and will select the next-best path for all routes otherwise using the failed segment. Routing algorithms can be programmed to adapt to changes in network bandwidth, router queue size, and network delay.

Figure 11-1 illustrates the construction of a routing loop.

Figure 11-1. Construction of a Routing Loop

The following steps show you how a routing loop forms:

1. A packet arrives at Router 1.

2. Router 1 has already been updated and knows that the best (optimal) route to the destination (Network B) calls for Router 2 to be the next hop.

3. Router 1 forwards the packet to Router 2, but because Router 2 has not yet been updated to reflect a link failure to the destination (Router 3 attached to Network B), Router 2 believes that the best next hop is Router 1 because Router 1 is advertising a path to Router 3, albeit through Router 2.

4. Router 2 forwards the packet back to Router 1, and the packet continues to bounce back and forth between the two routers until Router 2 receives its routing update or until the packet has exceeded the maximum number of hops allowed (often a destination is considered unreachable at 16 hops).

Algorithm Types

Routing algorithms are classified by type with the following key differentiators:

• Static versus dynamic

• Single-path versus multipath

• Flat versus hierarchical

• Host-intelligent versus router-intelligent

• Intradomain versus interdomain

• Link-state versus distance vector

Each of these is discussed in the following sections.

Static Versus Dynamic

Static routing algorithms are table mappings (routes to destination networks) established by the network administrator before the beginning of routing. These mappings do not change without manual intervention, such as by a network administrator. Algorithms using static routes work well in environments where network traffic is predictable and where network design is simple.

Because static routing algorithms cannot react to network changes, static routing algorithms are considered unsuitable for large changing networks. Most of the routing algorithms used are dynamic routing algorithms, which adjust to changing network conditions by analyzing and evaluating routing update messages. If the update message indicates a network change, the routing software recalculates routes and sends out new routing update messages to attached routers. These messages propagate throughout the network, causing attached routers to rerun their algorithms and change their routing tables as deemed necessary.

Single-Path Versus Multipath

A single path is the only path that can be used to reach a destination network. However, a single path is not necessarily a static route because the best route to that network can change based on changes in the network.

Some routing protocols enable multiple paths to the same destination and are often used in load-sharing environments. Unlike single-path algorithms, multipath algorithms permit load-sharing over multiple links to the same destination.

Flat Versus Hierarchical

Some routing algorithms operate in a flat space, while others use routing hierarchies. These are described as follows:

• Flat routing system The routers are peers (equal) of all others.

• Hierarchical routing system Some routers are logically grouped to form a routing backbone.

Packets from nonbackbone routers travel to the backbone routers, where these packets are sent through the network backbone until they reach the destination network. Upon arrival at the destination network, these packets travel from the last backbone router throughout one or more nonbackbone routers to the final destination subnetwork or host.

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, while others can communicate only with routers within their own domain. In very large networks, additional hierarchical levels can exist, with routers at the highest hierarchical level forming the routing backbone, as illustrated in Figure 11-2.

Figure 11-2. Hierarchical Networks

In this figure, routers in Area 1, Area 2 and Area 3 can communicate directly with other routers within the same area. If a router in Area 2 needs to communicate with a router in Area 3, then all traffic exchanged between the two routers must go through the network backbone area in this case, Area 0.

An advantage of hierarchical routing over flat routing is that hierarchical routing can mimic the organization of most enterprises, providing a method to manage traffic patterns within the network. Most network communication occurs within small enterprise organizations (domains). Because intradomain routers need to know only about other routers within their domain, these intradomain routing algorithms can be simplified and routing update traffic between intra- and interdomain routers can be reduced.

Host-Intelligent Versus Router-Intelligent

Some routing algorithms presume that the source host will determine the entire route; this is referred to as source routing. These are host-intelligent algorithms. In source-routing systems, routers act as store-and-forward devices, sending the packet to the next hop without examining the contents of the packet header. In this case, the hosts have the routing intelligence.

Router-intelligent algorithms presume that hosts know nothing about routes and the routers determine the path through the internetwork based on their own calculations. In this case, the routers have the routing intelligence.

Intradomain Versus Interdomain

Some routing algorithms work only within domains. These are called intradomain algorithms. Other routing algorithms, called interdomain algorithms, work within and between domains. The nature of these two algorithm types is different in that the best intradomain-routing algorithm is not necessarily the best interdomain-routing algorithm.

Link-State versus Distance Vector

Link-state algorithms, also known as shortest path first (SPF) algorithms, flood routing information to all routers in the internetwork. Each router sends only the portion of the routing table that describes the state of its own links. Routers running link-state algorithms build a picture of the entire network in their routing tables.

Distance vector algorithms, also known as Bellman-Ford algorithms, require each router to send all or some portion of its routing table only to its neighbors, not to all routers in the internetwork.

Link-state algorithms send small updates everywhere in the internetwork, while distance vector algorithms send larger updates only to neighboring routers. Distance vector algorithms know only about their neighbors.

Because link-state algorithms converge quicker than distance-vector algorithms, link-state algorithms often are less prone to routing loops than their distance vector algorithm counterparts. Link-state algorithms require more router CPU power and memory than distance vector algorithms, however, making link-state algorithms potentially more expensive to implement and support. The trade-off here is that link-state protocols (based on link-state algorithms) are more scalable than distance vector protocols.

Technical Note: Distance Vector Routing Protocols

The following routing protocols are classified as distance-vector routing protocols:

• Routing Information Protocol/RIPv2 (RIP / RIPv2)

• Interior Gateway Routing Protocol (IGRP)

• Enhanced Interior Gateway Routing Protocol (EIGRP)

The following routing protocol is classified as a link-state routing protocol:

• Open Shortest Path First (OSPF)

The following routing protocols are classified as hybrid routing protocols:

• Border Gateway Protocol (BGP)

• EIGRP EIGRP is a Distance-Vector/Link-State Hybrid

Routing Metrics

Routing tables contain information used by routers to select the best route to a destination network/host. Routing tables are built by the routing algorithms (protocols) in use by the router. Routing algorithms can base route selection on a single metric, such as hop count, or on multiple metrics, combining them in a single (hybrid) metric.

The following list identifies metrics used by routing protocols in making path determinations; however, not all of these metrics are used by every routing protocol:

• Path length The most common routing metric. Some routing protocols allow network administrators to assign arbitrary costs to each network link. In this case, path length is the sum of the costs associated with each link traversed. Other routing protocols define hop count, a metric specifying the number of passes through network routers that a packet must take from source to destination.

• Reliability Refers to the dependability, often described in terms of bit-error rate (BER), of each network link. After a network failure, certain network links might be repaired quicker than other links, for whatever reason. Any reliability factor can be taken into account in the assignment of a reliability rating. Reliability is an arbitrary numeric value often assigned to network links by network administrators.

• Delay Refers to the length of time required to move a packet from source to destination through the internetwork. Delay depends on many factors:

  - Bandwidth of intermediate network links

  - Port queues at each router along the way

  - Network congestion on all intermediate network links

  - Physical distance to be traveled

  Because delay is a collection of several variables, it is a common and useful metric.

• Bandwidth Refers to the available traffic capacity of a network link. All other things being equal, a 10 Mbps Ethernet link is preferable to a 64 kbps leased line. Although bandwidth is a rating of maximum attainable link throughput, routes through links with greater bandwidth do not always provide better routes than routes through slower links. For example, if a faster link is busier, the actual time required to send a packet to the destination could be greater.

• Load Refers to the degree to which a network resource, such as a router, is busy. Load can be calculated in a variety of ways, such as CPU utilization or packets processed per second. Monitoring router resources on a continual basis can be resource-intensive in itself. Because of this Cisco does not recommend using the router IOS debug command unnecessarily.

• Communication cost It's important to acknowledge communication cost because some organizations are concerned about performance as much as they are concerned about operating expenditures. Although line delay might be longer, organizations might send packets over their own lines rather than through the public lines that cost money for usage time. An example would be a network deployment where a 56K Frame Relay link might be more cost-effective to deploy to a small office/home office (SOHO) environment than several dial-up links.

NOTE

When multiple routing protocols are used, the administrative distance determines the primary route used by the router. Administrative distance is the value used to reflect the desirability of a learned path to a neighbor router. The lower the administrative distance, the better the path, because the route is considered to be more believable.

You can think of each of these routing metrics as an aspect of taking a family road trip. There are several factors you need to weigh in a certain order to get from Point A (home) to Point B (vacation spot).

• The first metric is path length, or in this case, the number of highway junctions and/or stop lights encountered during the trip.

• There is the question of reliability of each of the available roads; perhaps one of the roads tends to flood during heavy rain or the like.

• Delay is another metric you need to consider. Are any of the considered roads to the destination experiencing delays, such as those caused by traffic accidents or construction?

• Link bandwidth is comparable to the number of lanes available on each road; it is fair to say that a four-lane highway can carry more vehicular traffic than a two-lane highway.

• What is the traffic load on each road being considered? The four-lane highway might be able to accommodate more vehicles, but the consideration here is the number of vehicles on that road when the family vehicle is using the same highway.

• Then there is the cost of each road; perhaps the two-lane highway is not as congested, but you can weigh the number of tolls to be paid against the additional time the trip would take over another road that had no tolls but more vehicles.

Routing protocols, like the vacation driver, can weigh certain metrics over others. For example, the driver might opt to take the four-lane highway, disregarding the number of other cars using the same road, and possibly congesting the route. Some routing protocols might put an additional weight on the bandwidth metric, discounting the delay metric in the total metric calculation.

NOTE

The network administrator has the ability to change manually the metric valuables in whatever routing protocol is used, although letting the routing protocol use its default options is recommend.