Recapping Routers

Hours 1, "What Is TCP/IP?," and 9, "Network Hardware," introduced you to the essential networking device known as a router. You learned that the role of the router is to forward datagrams by IP address. A router, therefore, is a network hardware device that implements the IP addressing scheme discussed in Hour 4, "The Internet Layer." As you'll recall, a router is similar to a computer with multiple network cards connected to multiple network segments (refer to Figure 9.2). When a router receives a datagram through one of its ports, it inspects the datagram to determine the destination IP address. If the destination address is located on the network segment from which the message came, there is no need to forward the datagram, and the router ignores it. If the destination address is located on a different network segment, the router forwards the datagram according to the information located in its routing table.

Routers are necessary for the following reasons:

• Routers provide the delivery mechanism necessary for IP addressing (see Hour 4 and Hour 5, "Subnetting"). The elegant and efficient hierarchy of networks and subnets requires network devices that can direct a datagram by IP address.

• Routers filter traffic so that every host does not have to listen to messages addressed to every other host. As you learned in Hour 9, switches also filter traffic, but most switches use physical addresses rather than hierarchical IP addresses and therefore are not as effective on large networks.

• Routers hide the details of the physical network. Because IP forwarding occurs above the Network Access layer, routers can connect dissimilar network types. A computer on an ethernet LAN in Connecticut can communicate with a computer on a token ring LAN in Istanbul even though token ring and ethernet network adapters aren't compatible.

Unfortunately, it is difficult to discuss some of the topics in this hour on a small scale. The figures and descriptions are sometimes simplified to make the concepts more manageable, but the real benefit of routers can best be seen on large, diverse, and dynamic networks where a group of routers must constantly share information to keep the lines alive.

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 10.1):

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 very simple. The router in Figure 10.2 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 10.2 can deliver any datagram through direct routing.

Consider the slightly more complex network shown in Figure 10.3. 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 10.3 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?

There are two ways that routers learn about indirect routes:

• From a system administrator

• From other routers

These two options correspond (respectively) to the static routing and dynamic routing methods described in Hour 9. A system administrator can enter network routes directly into the routing table. This approach is known as static routing. The other option is for Router B to tell Router A about Segment 3. This method is called 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 10.3, 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 (described in Hour 9).

It is worth noting that it would also be possible to configure routing on the network shown in Figure 10.3 using defaults. In that case, Router A would not really 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 10.3. 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.

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

• 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'll 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).

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 10.4. 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.

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. 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 really 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.)