The Mechanics of Routing


Routing is a complex set of mathematical processes that is embodied in highly specialized routing protocols. Routing protocols have numerous functions, including the following:

  • Discovery of neighboring routers (those that are directly connected).

  • Discovery of destination networks that are accessible via neighboring routers. After discovering destination network addresses, the router has a couple other chores:

    - Comparing different paths (routes) to the same destination network. This is known as route calculation.

    - Building a table of known destination networks and the corresponding router interface for each destination. This table is called the routing table.

This is a highly simplified explanation of the function of routing protocols and is in no way intended to be comprehensive. An entire book could be written on just one routing protocol. This chapter's goal is much more humble: to help you understand how routing protocols use IP addresses.

It is important to recognize the difference between a routing protocol and a routed protocol. A routing protocol is highly specialized and is limited to router-to-router communications. A routed protocol is much more broadly used. Routed protocols, such as IP and IPX, encapsulate application data for transport across networks. This chapter shows you how routing protocols are absolutely reliant upon the addressing systems of routed protocols.

Discovering Routes

One of the most critical functions of a routing protocol is its capability to discover routes. In other words, a router's protocols communicate with neighboring routers and exchange information about known network addresses and their reachability. In this manner, an iterative process lets all the routers in a network learn about all the network addresses supported within that network. An equally important function of this capability is that it provides a means of identifyingand sharingnews of a change in the network's topology. The network's topology or shape constrains potential paths through the network between any given pair of locations.

Before we delve too deeply into the intricacies of neighboring routers, you might be wondering how a router learns about network addresses. The answer is quite simple: The network administrator configures each interface on a router. Part of this configuration defines that port's communication parameters. Communication parameters can include the speed of the link connected to that interface, the type of network and internetwork protocols supported, and the network address or addresses that are attached via that port. For example, network and internetwork protocols would be the combination of Fast Ethernet and IP. Of course, routers can support a seemingly infinite combination of network and internetwork protocols, so that's just one simple example.

NOTE

Router-to-router communication usually occurs only via neighboring routers. Some routing protocols, such as Open Shortest Path First (OSPF), utilize IP-based multicast mechanisms that enable a richer pattern of interrouter communications. For the most part, sharing routing information is an iterative process facilitated by neighboring routers.


Figure 11-1 depicts the first step in the iterative process of route discovery. In this illustration, backbone Router #2 senses a change in the network's topology and evaluates how that impacts the reachability of destinations in its routing table. More importantly, the protocol begins telling its immediately adjacent neighbors that the topology has changed. Notice that I didn't say the router tells its neighbors that a link is down. The router's job isn't necessarily to troubleshoot the problem and figure out what no longer works. Instead, the routing protocol must figure out what is still accessible. It does so by sharing with its neighbors select pieces of information, including which destination networks are still available via which of their interfaces. Thus, IP addresses are a critical component the underlying mechanics of networking as opposed to being merely a passive means of uniquely identifying machines on a network.

Figure 11-1. Backbone Router #2 Senses a Change in the Network's Topology


Figure 11-2 illustrates Backbone Router #2's initial attempts at sharing the news of the topology change with its immediately adjacent neighbors. Those immediate neighbors are location C and Backbone Routers #1 and #3. The fact that a link has failed means that routes to destinations that previously relied on that link no longer work. The routers must communicate with each other to learn about what is still accessible (and via which router) in order to ascertain a new set of best paths to all destination networks that remain reachable.

Figure 11-2. Backbone Router #2 Tells Its Neighbors About a Change in the Network's Shape


The communication process between these routers is governed by the routing protocol that is used, as well as other highly variable factors such as internal timing mechanisms. This example uses a simplistic model in which information flows fairly evenly throughout the network.

NOTE

The neighbor-to-neighbor communication between adjacent routers that occurs after a change in the topology is called convergence. A network in convergence is unstable and can't deliver user packets reliably or effectively. Such instability is a direct function of the loss of consensus about the network's shape. This is normal, and it's a good reason to select a routing protocol that converges efficiently.

A network has converged (emphasis on past tense) when all routers agree on the network's new shape and have updated their routing tables to reflect that new topology. Consequently, the network has returned to a stable, operational state.


As the routers attempt to develop a new consensus on the network's shape, the neighbors of Backbone Router #2 share the information they have received with their other immediate neighbors. Figure 11-3 shows this step in the iterative process. It is important to recognize that, in Figure 11-3, two routers communicate route information with their immediate neighbors: Backbone Routers #1 and #3. Backbone Router #1 sends that information to locations A and B, as well as to Backbone Router #3. Thus, Backbone Router #3 hears the same story from two different neighbors.

Figure 11-3. Second Iteration of Neighbor-to-Neighbor Communication


At the conclusion of the communications depicted in Figure 11-3, all routers in the network will have learned about the failure of the link between Backbone Router #2 and Location B. Depending on the complexity of the network's topology and the routing protocol being used, two or more complete iterations of this nature might be required before all the routers reach a consensus. Consensus is a unanimous agreement on which destination network addresses remain reachable, and the best path to use to reach them. The notion of "best path" is applicable only if there are two or more different paths through the network between any given source and destination network pair. The routing protocol would then have the opportunity to mathematically compare the redundant routes and select the one it deems best. Of course, "best" is a relative term, and the outcome of this comparison can change greatly depending on the criteria used in the comparison.

Calculating Routes

One aspect of routing that requires a bit more explanation is how routes are calculated. Yes, that's correct, calculated. Remember: This is a mathematical process. Calculating the "distance" to a destination using any given metric lets you make a direct comparison between two different routes to the same destination simply by comparing their respective metrics. Routing metrics are sometimes referred to as a route's cost.

There are four very different approaches to calculating a route's cost:

  • Distance vector

  • Link-state

  • Policy-based

  • Static

These approaches differ in how they calculate the best route to a destination. The first three are autonomous processes that rely extensively on independent sharing of information between neighboring routers. These three approaches are similar in that they are dynamic routing protocols that make decisions based in part on IP addresses. They differ in that they represent very different approaches to figuring out the best path to each destination network.

The fourth approach, static routing, features a correlation between destination network address and outbound router interface that is hard-coded or preprogrammed by the network administrator.

NOTE

There are times when a router might receive a packet addressed to a network that was previously unknown to that router. In such cases, the packet isn't necessarily discarded as being undeliverable. Instead, a concept known as a default gateway comes in handy. Essentially, you identify an interface on a router as the default gateway. If a packet comes in to an address that isn't in the routing table, it is forwarded out this interface. The concept of a default gateway doesn't guarantee that every packet gets delivered; it just increases the odds.

The concept of a default gateway is one that is universally present in all routing protocols regardless of the route calculation algorithm employed.


Distance Vector Routing

A distance vector routing protocol uses some arbitrary measure of distance to compare different routes to the same destination. The classic distance vector is hop count. A hop is a way to count the number of routers in a route. Typically, each router counts as one hop. If one path through a network to a specific destination requires passing through five routers, and another requires passing through only three routers, common sense fairly dictates that the three-router path is the better path.

Figure 11-4 shows a small network and how hops are calculated across it. If you look at that figure and think that the hop count should equal 4 instead of 3, you aren't far from the truth: There really are four routers in the path. But if you start counting from 0 instead of 1, the incrementing results in three hops instead of four. That's typical of hop-counting protocols.

Figure 11-4. Counting Hops En Route to a Destination


Distance vector algorithms date back to the late 1950s. As such, they are mature, stable, and remarkably simple. But time has marched on, and the early distance vector protocols (such as the myriad varieties of Routing Information Protocol [RIP]) are widely perceived as being obsolete due to the simplicity of their route-calculation algorithms.

Link-State Routing

The notion of making routing decisions based on some arbitrary measure of distance is logical. It formed the seminal work in the field of route calculation. In the halcyon days when networks were simple and nascent counting hops made sense, links were remarkably homogeneous. Over time, as networks and networking technologies matured and became more specialized, homogeneity was lost. In simpler terms, it was no longer safe to assume that all the links in an internetwork were T1s. Indeed, some of them could be T3 (with 44.573 Mbps of bandwidth), OC-3 (155.53 Mbps of bandwidth), OC-12 (622.12 Mbps of bandwidth), or even greater. Consequently, the perceived need for more-sophisticated means of route calculation arose.

Recognizing the need for a more sophisticated way of calculating routes and figuring out how to do that are two very different things. Depending on what your criteria are, a decision can have multiple "correct" answers. For example, if you were to drive from your home to a nearby mall, you would probably have to choose from several different routes. If you wanted to minimize the amount of traffic you encountered, you might opt for a backroads route that avoided major roads. If you wanted to maximize speed, you might pick a route that put you on the greatest number of streets with the highest speed limits. Alternatively, you might want to minimize the total number of miles you would have to travel, so you would select the shortest path possible. These simple scenarios demonstrate that, unless there is no topological diversity, there can be no single correct answer. So the search for a more sophisticated routing protocol quickly focused on finding appropriate metrics that would be inputs to the route calculation and selection processes.

Over time, consensus developed among network engineers on the need to have routing protocols that could make decisions based on current information on the state of the links in a network. This genre of routing protocol became known generically as link-state routing protocols.

Here are some examples of the types of link-state criteria that a routing protocol can use:

  • A link's speed

  • Delay encountered on a link

  • Historical information on a link's reliability (bit error rates)

  • Current utilization rates

Routers either have this data configured for their interfaces or can keep track of it. Reading through this short list of potential criteria, the most likely reaction is "Of course! That makes perfect sense!". Why wouldn't you want to base your routing decisions on such detailed information? A decision based on these criteria would enable much more accurate decisions than merely counting hops to a destinationor would it? To better appreciate the logic or illogic of making routing decisions on such criteria, consider the network topology illustrated in Figure 11-5.

Figure 11-5. Using Link-State Information to Calculate the Best Routes


Figure 11-5 shows the same network topology that has been used throughout this chapter. This figure, however, shows the effects of using a link-state routing protocol. The topology shows the bandwidth of each link. All but two of the links are T1s with 1.544 Mbps of bandwidth. Those two links interconnect backbone router #3 with #1 and #2. Given that a link-state routing protocol is used, bandwidth becomes a very important factor in selecting the optimal routemore so than just hop count. You might expect the shortest path to be the best one, but the quality of the links being compared can skew that perception.

Other potential issues with link-state protocols focus on the volatility of the data used to make routing decisions. If the shortest path is actually the lowest-bandwidth, most-congested link in the network, it would make much more sense to take a higher-bandwidth, less-congested path even it if were slightly more circuitous. But this generalization assumes that the information you are basing your routing decisions on is relatively stable. Some measures of a link's state are unstable. Utilization rates, for example, can vary tremendously from one second to the next.

This points out one of the great flaws in the link-state philosophy: A link's state can be highly dynamic. It can change faster than a network's routers can finish sharing routing information. Thus, making routing decisions on highly dynamic information can be counterproductive. Fear not. Many mechanisms have been developed that effectively dampen the volatility of data used to make routing decisions. I just mention this potential shortcoming of link-state routing protocols to help you better appreciate some of the complexity of making good routing decisions.

Policy-Based Routing

A small but very powerful group of routing protocols are geared toward global scalability. These protocols are collectively known as exterior gateway protocols (EGPs). EGPs are used only for communicating with, and across, the Internet. Such protocols are designed almost exclusively to provide the scalability that this role requires. They rely on administrator-configured policies and rules to determine what to do with IP packets. This is in stark contrast to both distance vector and link-state protocols, which focus on selecting the best possible route based on some arbitrary metric(s).

Examples of exterior protocols include the archaic Exterior Gateway Protocol (EGP) and the Border Gateway Protocol (BGP). BGP-4 is the routing protocol currently in use across the Internet for communicating routing information between service providers.

Static Routing

Statically configured routes are preprogrammed in a router. No routing protocol is needed, because no routing decisions are left up to the router. The network administrator decides which is the best path to take to reach any given network address, and it hard-codes that path into the router.

The benefit of static routing is that it imposes an absolute minimum of overhead on a router and network. No bandwidth or CPU cycles are consumed in an effort to maintain a current image of the network.

The drawback of static routing is that it is utterly inflexible. If the topology changes, a statically configured route has no way of detecting, or reacting, to such a change. Instead, the network administrator must manually update the statically configured routes to accommodate changes in topology. In lieu of a routing protocol, the network administrator must manually instruct the router what to do with packets destined for each network address. Implicit in this explanation of static routing is the fact that static routes are unidirectional. A network administrator may tell a router how to forward packets that have a particular network address, but that administrator has no control over packets that are inbound. Thus, routing in a statically configured network might well be asymmetric.

Static routing is not exactly a scalable approach to internetworking. This technique is typically found only in very simple networks or is used to secure specific areas within a network.

NOTE

For a much more complete exploration of routing, refer to IP Routing Fundamentals, ISBN 1-57870-071-X, published by Cisco Press.





IP Addressing Fundamentals
IP Addressing Fundamentals
ISBN: 1587050676
EAN: 2147483647
Year: 2002
Pages: 118
Authors: Mark Sportack

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net