Routing in TCP/IP
In its most basic form, a router is a device that filters traffic by logical address. A classic network router operates at the Internet layer (OSI Network layer) using IP addressing information in the Internet layer header. In OSI shorthand, the Network layer is also known as Layer 3, and a router is sometimes called a Layer 3 device. In recent years, hardware vendors have developed routers that operate at higher layers of the OSI stack. You learn about Layer 4–7 routers later in this hour, but for now, think of a router as a device that is operating at the Internet layer or OSI Layer 3—the same level as IP addressing.
Routers are an essential part of any large TCP/IP network. Without routers the Internet could not function. In fact, the Internet never would have grown to what it is today without the development of network routers and TCP/IP routing protocols.
A large network such as the Internet contains many routers that provide redundant pathways from the source to the destination nodes. The routers must work independently, but the effect of the system must be that data is routed accurately and efficiently through the internetwork.
Routers replace Network Access layer header information as they pass data from one network to the next, so a router can connect dissimilar network types. Many routers also maintain detailed information describing the best path based on considerations of distance, bandwidth, and time. (You learn more about route-discovery protocols later in this hour.)
Routing in TCP/IP is a subject that has filled 162 RFCs (as of the last edition of this book) and could easily fill a dozen books. What is truly remarkable about TCP/IP routing is that it works so well. An average homeowner can call up an Internet browser and connect with a computer in China or Finland without a passing thought to the many devices forwarding the request around the world. Even on smaller networks, routers play a vital role in controlling traffic and keeping the network fast.
What Is a Router?
The best way to describe a router is to describe how it looks. In its simplest form (or, at least, in its most fundamental form) a router looks like a computer with two network adapters. The earlier routers were actually computers with two or more network adapters (called multihomed computers). Figure 8.1 shows a multihomed computer acting as a router.
Figure 8.1. A multihomed computer acting as a router.
The first step to understanding routing is to remember that the IP address belongs to the adapter and not to the computer. The computer in Figure 8.1 has two IP addresses—one for each adapter. In fact, it is possible for the two adapters to be on completely different IP subnets corresponding to completely different physical networks (as shown in Figure 8.1). In Figure 8.1, the protocol software on the multihomed computer can receive the data from segment A, check the IP address information to see whether the data belongs on segment B, replace the Network Access layer header with a header that provides physical address information for segment B (if the data is addressed to segment B), and transmit the data onto segment B. In this simple scenario, the multihomed computer acts as a router.
If you want to understand the scope of what the world’s networks are doing, imagine the scenario in the preceding paragraph with the following complications:
The router has more than two ports (adapters) and can, therefore, interconnect more than two networks. The decision of where to forward the data then becomes more complicated, and the possibility for redundant paths increases.
The networks that the router interconnects are each interconnected with other networks. In other words, the router sees network addresses for networks to which it is not directly connected. The router must have a strategy for forwarding data addressed to networks to which it is not directly attached.
The network of routers provides redundant paths, and each router must have a way of deciding which path to use.
The simple configuration in Figure 8.1, combined with the preceding three complications, offers a more detailed view of the router’s role (see Figure 8.2).
Figure 8.2. Routing on a complex network.
On today’s networks, most routers are not multihomed computers. It is more cost-effective to assign routing responsibilities to a specialized device. The routing device is specifically designed to perform routing functions efficiently, and the device does not include all the extra features found in a complete computer.
The Routing Process
Building on the discussion of the simple router described in the preceding section, a more general description of the router’s role is as follows:
1. | The router receives data from one of its attached networks. |
2. | The router passes the data up the protocol stack to the Internet layer. In other words, the router discards the Network Access layer header information and reassembles (if necessary) the IP datagram. |
3. | The router checks the destination address in the IP header. If the destination is on the network from whence the data came, the router ignores the data. (The data presumably has already reached its destination because it was transmitted on the network of the destination computer.) |
4. | If the data is destined for a different network, the router consults a routing table to determine where to forward the data. |
5. | After the router determines which of its adapters will receive the data, it passes the data down through the appropriate Network Access layer software for transmission through the adapter. |
The routing process is shown in Figure 8.3. It might occur to you that the routing table described in step 4 is a rather crucial element. In fact, the routing table and the protocol that builds the routing table are distinguishing characteristics of the router. Most of the discussion of routers is about how routers build routing tables and how the route protocols that assemble routing table information cause the collection of routers to serve as a unified system.
Figure 8.3. The routing process.
The two primary types of routing are named for where they get their routing table information:
Static routing— Requires the network administrator to enter route information manually.
Dynamic routing— Builds the routing table dynamically based on routing information obtained using routing protocols.
Static routing can be useful in some contexts, but as you might guess, a system that requires the network administrator to enter routing information manually has some severe limitations. First, static routing does not adapt well to large networks with hundreds of possible routes. Second, on all but the simplest networks, static routing requires a disproportionate investment of time from the network administrator, who must not only create but also continually update the routing table information. Also, a static router cannot adapt as quickly to changes in the network, such as a downed router.
By the Way
Most dynamic routers give the administrator the option of overriding dynamic route selection and configuring a static path to a specific address. Preconfigured static routes are sometimes used for network troubleshooting. In other cases, the administrator might provide a static path to take advantage of a fast network connection or to balance network traffic.
Routing Table Concepts
The role of the routing table and other Internet layer routing elements is to deliver the data to the proper local network. After the data reaches the local network, network access protocols will see to its delivery. The routing table, therefore, does not need to store complete IP addresses and can simply list addresses by network ID. (See Hour 4, “The Internet Layer” and Hour 5, “Subnetting and CIDR,” for a discussion of the host ID and network ID portions of the IP address.)
The contents of an extremely basic routing table are shown in Figure 8.4. A routing table essentially maps destination network IDs to the IP address of the next hop—the next stop the datagram makes on its path to the destination network. Note that the routing table makes a distinction between networks directly connected to the router itself and networks connected indirectly through other routers. The next hop can be either the destination network (if it is directly connected) or the next downstream router on the way to the destination network. The Router Port Interface in Figure 8.4 refers to the router port through which the router forwards the data.
Figure 8.4. The routing table.
The next-hop entry in the routing table is the key to understanding dynamic routing. On a complex network, several paths to the destination might exist, and the router must decide which of these paths the next hop will follow. A dynamic router makes this decision based on information obtained through routing protocols.
By the Way
A host computer, like a router, can have a routing table; because the host does not have to perform routing functions, its routing table usually isn’t as complicated. Hosts often make use of a default router or default gateway. The default gateway is the router that receives the datagram if it can’t be delivered on the local network or to another router.
A Look at IP Forwarding
Both hosts and routers have routing tables. A host’s routing table can be much simpler than a router’s routing table. The routing table for a single computer might contain only two lines: an entry for the local network and a default route for packets that can’t be delivered on the local segment. This rudimentary routing information is enough to point a datagram toward its destination. You’ll learn later in this hour that a router’s role is a bit more complex.
As you learned in Hour 4, the TCP/IP software uses ARP to resolve an IP address to a physical address on the local segment. But what if the IP address isn’t on the local segment? As Hour 4 explains, if the IP address isn’t on the local segment, the host sends the datagram to a router. You might have noticed by now that the situation is actually a bit more complicated. The IP header (refer to Figure 4.3) lists only the IP address of the source and destination. The header doesn’t have room to list the address of every intermediate router that passes the datagram toward its destination. As you read this hour, it is important to remember that the IP forwarding process does not actually place the router’s address in the IP header. Instead, the host passes the datagram and the router’s IP address down to the Network Access layer, where the protocol software uses a separate lookup process to enclose the datagram in a frame for local delivery to the router. In other words, the IP address of a forwarded datagram refers to the host that will eventually receive the data. The physical address of the frame that relays the datagram to a router on the local network is the address of the local adapter on the router.
A brief description of this process is as follows (see Figure 8.5):
Figure 8.5. The IP forwarding process.
The IP forwarding process described in step 6 of the preceding procedure is an important characteristic of a router. It is important to remember that a device will not act like a router just because it has two network cards. Unless the device has the necessary software to support IP forwarding, data will not pass from one interface to another. When a computer that is not configured for IP routing receives a datagram addressed to a different computer, the datagram is simply ignored.
Direct Versus Indirect Routing
If a router just connects two subnets, that router’s routing table can be simple. The router in Figure 8.6 will never see an IP address that isn’t associated with one of its ports, and the router is directly attached to all subnets. In other words, the router in Figure 8.6 can deliver any datagram through direct routing.
Figure 8.6. A router connecting two segments can reach each segment directly.
Consider the slightly more complex network shown in Figure 8.7. In this case, Router A is not attached to Segment 3 and does not have a way of finding out about Segment 3 without some help. This situation is called indirect routing. Most routed networks depend to some degree on indirect routing. Large corporate networks might have dozens of routers, with no more than one or two connected directly to each network segment. You’ll learn more about these larger networks later in this hour. For now, the important questions to ask about Figure 8.7 are the following: How does Router A find out about Segment 3? How does Router A know that datagrams addressed to Segment 3 should be sent to Router B and not to Router C?
Figure 8.7. A router must perform indirect routing if it forwards datagrams to a network to which it isn’t directly attached.
There are two ways that routers learn about indirect routes: from a system administrator or from other routers.
These two options correspond (respectively) to the static routing and dynamic routing methods. A system administrator can enter network routes directly into the routing table (static routing), or Router B can tell Router A about Segment 3 (dynamic routing). Dynamic routing offers several advantages. First, it does not require human intervention. Second, it is responsive to changes in the network. If a new network segment is attached to Router B, Router B can inform Router A about the change.
As it turns out, static routing is sometimes an effective approach for small, simple, and permanent networks. Static routing would probably be acceptable on the simple network shown in Figure 8.7, but as the number of routers increases, static routing becomes inadequate. The number of possible routes multiplies as you add segments to the network, creating additional work for the administrator. More importantly, the interaction of static routes on a large network can lead to inefficiencies and to quirky behavior, such as routing loops, in which a datagram cycles endlessly through the chain of routers without ever reaching its destination.
It is worth noting that it would also be possible to configure routing on the network shown in Figure 8.7 using defaults. In that case, Router A would not have to find out about Segment 3. It could just route to Router B any datagram with an unknown address and let Router B figure out what to do next. Once again, this scenario might work on the small network shown in Figure 8.7. But a default route is a static route, and configuring the routers themselves to route by default on a complex network can lead to the same inefficiencies and quirky behavior associated with static routing.
For these reasons, most modern routers use some form of dynamic routing. The routers communicate with each other to share information on network segments and network paths, and each router builds its routing table using the information obtained through this communication process. The following sections describe how dynamic routing works.
By the Way
Routers sometimes use a combination of static and dynamic routing. A system administrator might configure a few static paths and let others be assigned dynamically. Static routes are sometimes used to force traffic over a specific path. For example, a system administrator might want to configure the routers so that traffic is funneled to a high-bandwidth link.
Dynamic Routing Algorithms
The routers in a router group exchange enough information about the network so that each router can build a table that describes which way to send datagrams addressed to any particular segment. What exactly do the routers communicate? How does a router build its routing table? As you have probably figured out by now, the behavior of a router depends entirely upon the routing table. Several routing protocols are currently in use. Many of those routing protocols are designed around one of two routing methods: distance vector routing and link state routing.
These methods are best understood as different approaches to the task of communicating and collecting routing information. The following sections discuss distance vector and link state routing. Later in this hour, you take a closer look at a pair of routing protocols that use these methods: RIP (a distance vector routing protocol) and OSPF (a link state routing protocol).
By the Way
Distance vector and link state are classes of routing protocols. The implementations of actual protocols include additional features and details. Also, many routers support startup scripts, static routing entries, and other features that complicate any idealized description of distance vector or link state routing.
Distance Vector Routing
Distance vector routing (also called Bellman-Ford routing) is an efficient and simple routing method employed by many routing protocols. Distance vector routing once dominated the routing industry, and it is still quite common, although recently more sophisticated routing methods (such as link state routing) have been gaining popularity.
Distance vector routing is designed to minimize the required communication among routers and to minimize the amount of data that must reside in the routing table. The underlying philosophy of distance vector routing is that a router does not have to know the complete pathway to every network segment—it only has to know in which direction to send a datagram addressed to the segment (hence the term vector). The distance between network segments is measured in the number of routers a datagram must cross to travel from one segment to the other. Routers using a distance vector algorithm attempt to optimize the pathway by minimizing the number of routers that a datagram must cross. This distance parameter is referred to as the hop count.
Distance vector routing works as follows:
With each round of routing table updates, the routers receive a more complete picture of the network. Information about routes slowly disseminates across the network. Assuming nothing changes on the network, the routers will eventually learn the most efficient path to every segment.
An example of a distance vector routing update is shown in Figure 8.8. Note that at this point, other updates have already taken place because both Router A and Router B know about the network to which they are not directly attached. In this case, Router B has a more efficient path to Network 14, so Router A updates its routing table to send data addressed to Network 14 to Router B. Router A already has a better way to reach Network 7, so the routing table is not changed.
Figure 8.8. A distance vector routing update.
By the Way
The destinations listed in Figure 8.8 (Network 1, Network 2, and so on) are either whole IP networks or IP subnets, depending on the context.
Link State Routing
Distance vector routing is a worthy approach if you assume that the efficiency of a path coincides with the number of routers a datagram must cross. This assumption is a good starting point, but in some cases it is an oversimplification. (A route through a slow link takes longer than a route through a high-speed link, even if the number of hops is the same.) Also, distance vector routing does not scale well to large groups of routers. Each router must maintain a routing table entry for every destination, and the table entries are merely vector and hop-count values. The router cannot economize its efforts through some greater knowledge of the network’s structure. Furthermore, complete tables of distance and hop-count values must pass among routers even if most of the information isn’t necessary. Computer scientists began to ask whether they could do better, and link state routing evolved from this discussion. Link state routing is now the primary alternative to distance vector routing.
The philosophy behind link state routing is that every router attempts to build its own internal map of the network topology. Each router periodically sends status messages to the network. These status messages list the network’s other routers to which the router is directly connected and also the status of the link (whether the link is currently operational). The routers use the status messages received from other routers to build a map of the network topology. When a router has to forward a datagram, it chooses the best path to the destination based on the existing conditions.
Link state protocols require more processing time on each router, but the consumption of bandwidth is reduced because every router is not required to propagate a complete routing table. Also, it is easier to trace problems through the network because the status message from a given router propagates unchanged through the network. (The distance vector method, on the other hand, increments the hop count each time the routing information passes to a different router.)