IP Routing

Dynamic Routing

After the public library, our Canadian visitor jumps into a taxi to go crash at a friend’s place in Brooklyn. “Go over the Brooklyn Bridge,” she tells the driver. They head downtown. Suddenly, the driver slams on his brakes and makes an abrupt turn. Cars all around jam on their brakes, and pedestrians run hither and thither. “The radio said it is an hour to go over the bridge! We will take the tunnel!” the driver shouts to the back seat. This is an example of dynamic routing in a transportation system. What is dynamic routing in IP networks? Dynamic routing protocols allow each router to automatically discover one or more paths to each destination in the network. When the network topology changes, such as when new paths are added or when paths go out of service, dynamic routing protocols automatically adjust the contents of the routing table to reflect the new network topology.

Dynamic routing relies on (frequent!) updates to discover changes in network topology. In the example in Figure 1-3, when the path R3 → R4 is added to the network it can be automatically discovered by a routing protocol, such as RIP, EIGRP, or OSPF.

The routing protocols in use today are based on one of two algorithms: Distance Vector or Link State. Distance Vector (DV) algorithms broadcast routing information to all neighboring routers. In other words, each router tells all of its neighbors the routes it knows. When a router receives a route (from a neighbor) that is not in its routing table, it adds the route to its table; if the router receives a route that is already in its routing table, it keeps the shorter route in its table. DV algorithms are sometimes also described as routing by rumor: bad routing information propagates just as quickly as good information. Link State algorithms operate on a different paradigm. First, each router constructs its own topological map of the entire network, based on updates from neighbors. Next, each router uses Dijkstra’s algorithm to compute the shortest path to each destination in this graph. Both DV and Link State algorithms are described in further detail in the chapters that follow.

In the previous paragraph, we spoke of the “shorter” or “shortest” path in the context of both DV and Link State algorithms. Since a router may know of multiple paths to a destination, each routing protocol must provide a mechanism to discover the “shorter” or “shortest” path based on one or more of the following criteria: number of hops, delay, throughput, traffic, reliability, etc. A metric is usually attached to this combination; lower metric values indicate “shorter” paths. For each routing protocol discussed in the chapters that follow, we will describe how the route metric is computed.

A network under a single administrative authority is described as an autonomous system (AS) in routing parlance. Interior gateway protocols (IGPs) are designed to support the task of routing internal to an AS. IGPs have no concept of political boundaries between ASs or the metrics that may be used to select paths between ASs. RIP, IGRP, EIGRP, and OSPF are IGPs. Exterior gateway protocols (EGPs) are designed to support routing between ASs. EGPs deploy metrics to select one inter-AS path over another. BGP is the most commonly used EGP.

Routing architectures may be broadly classified as flat or hierarchical. Flat routing implies that all routes are known to all peers -- all routers in the network are equal, possessing the same routing information. Hierarchical routing implies that some routers possess only local routes, whereas others possess a little bit more information, and still others possess even more.

Let’s draw an analogy to the postal system. When I write a letter to a friend in India, the postman in the U.S. may have no idea where India is. He forwards all foreign mail to a designated post office in his state. That designated post office must know every postal system in the world. Such a system, in which some post offices are regional and some handle foreign mail, could be described as hierarchical.

In large IP networks, only a few routers need to know every route in the network. These routers are sometimes described as core routers. Around the core routers is a layer of distribution routers that need not possess the complete routing table. When a distribution router receives a packet whose destination IP address does not appear in its local routing table, the distribution router simply forwards the packet to a core router.

In the earlier example of the high school student in New Zealand accessing a web site in Sri Lanka, the small router in the high school in New Zealand probably has only a tiny routing table, with no routing entries for Sri Lanka. The high school router will forward all traffic for unknown destinations to another router, which in turn may forward the traffic to another one. Large IP networks exhibit several layers of hierarchy.

As we will see in the chapters that follow, some routing protocols have features that make it easier to build hierarchies. These features include route aggregation, classlessness, the use of default routes, and the flexibility with which routes can be exchanged with other routing protocols.

RIP is an example of an almost completely flat routing protocol. OSPF exhibits several features that permit the design of hierarchical networks.

As with any other algorithm, routing algorithms may also be categorized based on their complexity, flexibility, overhead, memory and CPU utilization, robustness, and stability. These properties of routing algorithms are of interest to the routing engineer, since he provides the (router) infrastructure to execute these algorithms.