Internet Routing

They say that any sufficiently advanced technology is indistinguishable from magic, and it’s not hard to see why. When you think about the incredible amount of advanced technology that makes it possible to view a Web site or send an e-mail to anyone in the world, it can definitely seem like magic. However, as we all know, there is no magic in the network, just basic engineering.

All networks are composed of computers that are connected to each other via a shared electrical connection (i.e., a wire). A computer can only communicate directly with other computers that share the same physical network. The magic of the Internet is that it makes possible communication between computers on separate physical networks. To do this, a router is needed to interconnect these networks. Routers are computers that contain some intelligence about the topology of the network and have the ability to forward (”route”) packets between the networks they are aware of. Without routers, your computer could not communicate with a computer on the other side of town, let alone on the other side of the world.

Figure One: Three separate physical networks linked with routers.

Figure One shows three separate networks. Because computers can only communicate directly if they share a network, computer A can talk to B, but A cannot talk to C or D. B can talk to systems A and C, but not to D. C can talk to B and D, but it can’t talk to A. D can talk to C, but not to any of the other systems. This is not a global network! A must rely on system B to deliver a message to D. B in turn sends the message to system C, counting on it for delivery. C then sends the message to D. Thus, in Figure One, computers B and C are routers. They link together the different physical networks and forward messages between them.

It’s worth keeping in mind that even though routers are required for computers to communicate between networks, routers are not the only machines that make routing decisions. Every network device that uses the Internet Protocol (IP) makes routing decisions. How does this work? Well, in simplified terms, when a Linux system has a packet to deliver, the destination address of the packet is looked up in a routing table. The routing table tells the system whether the packet should be delivered directly to a computer located on this physical network or if it needs to be forwarded to a different physical network.

Table Based Routing

At this point, it’s probably a good idea to take a look at this routing table. While we’ve included the routing table from one of our systems (running Red Hat 7) in Listing One, you can easily view the routing table for your own computer. Just use the route command with the -n option, and it should come right up. The -n option prevents route from converting IP addresses to host names, which creates a clearer display.

# route -n
Kernel IP routing table
Destination   Gateway       Genmask        Flags  Metric  Ref  Use  Iface
172.16.55.0   0.0.0.0       255.255.255.0  U      0       0    0    eth0
172.16.50.0   172.16.55.36  255.255.255.0  UG     0       0    0    eth0
127.0.0.0     0.0.0.0       255.0.0.0      U      0       0    0    lo
0.0.0.0       172.16.55.1   0.0.0.0        UG     0       0    0    eth0

As you can see in Listing One, each entry in the routing table starts with a Destination value. The Genmask field is the bit mask that will be applied to the destination address of the packet to see if it matches the Destination value in the table. For example, the address 172.16.50.183 would match the second entry in this table because performing a logical AND of that address with the Genmask of 255.255.255.0 yields 172.16.50.0.

When an address matches an entry in the table, the Gateway field tells the system how to reach the specified destination. If the Gateway field contains the IP address of a router, then that router is used. If the Gateway field contains all zeros (0.0.0.0) or an asterisk (*), the destination is a directly connected network, and the “gateway” is the computer’s network interface. The last field for each table entry is the network interface used for the route (Iface). In this example, it is either the first Ethernet interface (eth0) or the loopback interface (lo).

The remaining four fields display supporting information about the route. The Ref field shows the number of times the route has been referenced to establish an outbound connection, and the Use field shows the number of packets transmitted via the route. The Flags field describes certain characteristics of the route, such as U, which means the route is up (i.e., it’s “live”), and G, which means the route uses an external gateway. The Metric field shows the cost of using the route. Routing metrics are used by the routing protocols to determine the “cheapest” way to reach a given destination.

The first line in the sample table defines the connection of this host to the local Ethernet. This entry tells us that the local network is 172.16.55.0 and that the host connects to it through interface eth0. The second line tells us that 172.16.55.36 is the gateway to network 172.16.50.0. The third line defines the loopback network and states that the gateway to it is the interface lo. Finally, the last line defines the default route, as indicated by the destination value 0.0.0.0 (Destination contains the keyword “default” on some systems) and the Genmask value 0.0.0.0. If the destination of a packet does not match a specific route, the packet is sent to the default gateway.

On most networks, the only system with a very complex routing table will be the router itself. Host computers tend to have much simpler, static routing tables that only contain three routes:

• The loopback route
• The route to the local network
• The route to the default router

These three routes are statically defined by the system administrator by either answering configuration questions during the initial installation or by using the route command to manually add routes to the routing table (which we’ll take a look at in a minute). This static table rarely changes once it is created. (Although Linux systems are most often configured as hosts, this does not have to be the case. See the Creating a Router sidebar for information about the switch that causes a Linux system to act as a router.)

echo “1″ /proc/sys/net/ipv4/ip_forward

Adding a Static Route

IP relies on the routing table to direct packets to their destinations, but IP does not build the routing table. Routes enter the routing table in one of two ways — either the system administrator enters them as static routes, or they are added to the table dynamically by a routing protocol. Manually adding static routes works very well when a single default route is used, but building the complex routing tables needed by routers requires a dynamic routing protocol.

The route command adds or deletes entries in the routing table. For example, to add the route 129.6.0.0 to the routing table, you would issue the command:

# route add -net 129.6.0.0 netmask
   255.255.0.0 gw 192.168.0.3 dev eth0

In the sample command, the keyword add tells route to add a new route to the table. The -net value is the destination address of the network reached via this route. The netmask value is the address mask that will appear in the Genmask field when the routing table is displayed. The gw value, which will appear in the Gateway field of the routing table display, is the address of the external gateway through which packets are sent to reach this destination address. Finally, the route command permits you to specify the network interface to use for the route. Generally, there is no need to define the interface, because the system will choose the correct interface to reach the specified router by default. However, the dev option exists so you can define the interface yourself if you want. These four items — the destination, the address mask, the gateway, and the interface — are the basic components of a route. After entering the route, you can issue the command route-n; again, you would see the output in Listing Two.

# route -n
Kernel IP routing table
Destination   Gateway      Genmask        Flags   Metric  Ref  Use  Iface
192.168.0.0   0.0.0.0      255.255.255.0  U       0       0    0    eth0
129.6.0.0     192.168.0.3  255.255.0.0    UG      0       0    0    eth0
127.0.0.0     0.0.0.0      255.0.0.0      U       0       0    0    lo
0.0.0.0       192.168.0.1  0.0.0.0        UG      0       0    0    eth0

The route command also accepts an argument called metric, which assigns a “cost” to the route. Static routing uses the metric to sort duplicate routes in the routing table. However, duplicate routes have no real use in static routing because the system stops searching the routing table on the first match. This means that even if a given route is down and a router with a slightly higher metric is up and running, static routing will always send packets to the router that is down. Obviously, this is not good. However, it’s not a major issue, because dynamic routing makes real use of routing metrics in order to avoid this problem.

Dynamic Routing Protocols

Routing protocols perform two functions — they select the “best” routes and communicate those routes to other routers on the network. Thus, a routing protocol is a recipe for defining and for disseminating routes.

Routing protocols are differentiated by the method they use for determining the best route and by the technique they use for distributing routing information. There are only two major algorithms used to select the “best” route:

• Link state algorithms allow routers to build a database that assigns a cost to every link in the network. A link state protocol selects the route that has the lowest total link cost as the best route. Open Shortest Path First (OSPF) is an example of a link state protocol.
• Distance vector algorithms use a metric that represents the number of routers through which the packet must travel. The fewer routers that must handle the packet, the more preferred the route. Routing Information Protocol (RIP) is an example of a distance vector protocol.

RIP is the routing protocol traditionally used by Unix systems. It is easy to explain and understand, so it is a good place to start a study of routing protocols. Additionally, RIP provides excellent examples of the technical problems and challenges that routing protocols present to software developers and network administrators, and for these reasons, we’re going to devote the rest of this article to looking at it.

Routing Information Protocol

RIP is the original routing protocol used on Unix systems and is still included in many Linux distributions. It defines the “best” route as being the route with the lowest routing metric. The RIP routing metric is a number from 1 to 15 that represents the number of routers that traffic must pass through. Each router is referred to as a “hop.”

When RIP starts, it broadcasts a request for routing information. Another router running RIP responds to the request by sending an update packet that contains the destination addresses and associated metrics it has in its own routing table. In addition to responding to requests, RIP routers issue updates every 30 seconds. If a router stops issuing updates for 180 seconds, the other routers on the network assume it is dead and delete any routes that go through it. Figure Two illustrates the format of a RIP update packet.

Figure Two: The format of a RIP update packet.

It’s worth taking a moment to examine the fields in the RIP packet. The command field either contains a 1 if this is a request packet or a 2 if it is a response packet. The version field always contains a 1 for basic RIP, and the address family field always contains a 2, which indicates that the packet uses IP addresses. The last four word-length fields in Figure Two contain a destination address, two words of zeros, and a metric that shows the cost of reaching the destination through the router that sent out the update. These four words are repeated for every destination and metric in the router’s routing table.

When a router receives an update packet, RIP processes it in the following manner:

• If the update contains new routes that are not in the routing table they are added.
• If the update contains routes that are of lower cost than the same routes in the existing routing table, the new routes are used. The cost of a new route is determined by adding the cost of reaching the router that sent the update to the cost metric included in the update packet.
• If the update contains routes that have a cost of 15, those routes are deleted from the routing table if the update came from the gateway used for those routes. For example, if the routing table contains a route to network 172.16.50.0 through gateway 172.16.55. 36, and it receives a RIP update from 172.16.55.36 with a cost of 15 for the route to 172.16.50.0, the route is deleted.

Most Unix systems, and many Linux systems, use the routed (pronounced “Route ‘D’,” as in daemon) program to run RIP. When routed starts, it issues a request for routing updates and then listens for responses. If it is running on a computer with more than one network interface, routed also responds to RIP requests with an update packet. Use the -q option to prevent routed from issuing updates.

routed reads information from /etc/gateways to build the routing table. The most common use for the /etc/gateways file is to define a default route, as in this example:

net 0.0.0.0 gateway 172.16.12.1 metric 1 active

This entry starts with the keyword net followed by a network address. (The destination address 0.0.0.0 is used for the default route.) Next is the keyword gateway followed by the gateway’s address and the keyword metric followed by the cost of the route. All /etc/gateways entries end with either the keyword passive or active. A passive route is a permanent static route placed in the routing table and kept there as long as the system is up. An active route can be updated by RIP. active routes are used to “prime the pump” during the RIP startup phase, with the expectation that the routes will be updated when the protocol is up and running.

Figure Three: Routers connecting several different networks.

/etc/gateways is the only configuration file for routed, and it is rarely needed. On most systems, routed learns all it needs to build the correct routing table via the RIP protocol. It does not require manual configuration.

RIP is a simple protocol, and routed is a simple program. However, simplicity has a price. RIP has three fundamental limitations:

• Its network diameter is limited to 15 hops.
• It cannot send network bit masks with routing updates.
• It suffers from slow convergence (meaning it can take a long time for the routing table to reflect the current state of the network). Figure Three helps illustrate this problem.

Slow Convergence

In order to really understand the problems behind slow convergence and the techniques used to address them, you need to understand a problem known as “count-to-infinity.” The problem goes something like this; in Figure Three, the c-router reaches network 1 through b-router and then through a-router. Network 1 is two hops away from c- router and one hop away from b-router. Therefore, b-router advertises a cost of 1 for network 1, c-router advertises a cost of 2, and traffic is routed through b-router. This is all fine and dandy until something goes wrong.

Think about a scenario like this; if a-router crashes, b-router will wait for an update from a-router for 180 seconds. While waiting, b-router continues to send updates to c-router that keep the route to network 1 in c-router’s routing table. When b-router’s timer finally expires, it removes all routes through a-router from its routing table, including the route to network 1. It then receives an update from c-router advertising that c-router is two hops away from network 1. b-router installs this route and announces that it is three hops away from network 1. c-router receives this update, installs the route, and announces that it is four hops away from network 1. This continues until the cost of the route to network 1 reaches 15 in both routing tables. If the update interval is 30 seconds, this could take a long time! RIP deals with the problem of counting to infinity by employing two techniques — split horizon and poison reverse.

Split horizon prevents a router from advertising routes on the link from which those routes were obtained. This solves the problem described above, because c-router does not announce the route to network 1 on network 3 and therefore does not confuse b-router with bad updates. While this feature works for the example described above, it does not work for all count-to-infinity problems (more on this later.).

Poison reverse makes a router advertise routes with an infinite distance on the link from which the routes were obtained. With poison reverse, c-router advertises network 1 with a cost of 15 to all systems on network 3 to positively state that network 1 cannot be reached through c-router.

Split horizon and poison reverse solve the problem described above. But what happens if c-router crashes? Again, refer to Figure Three. Because of split horizon, d-router and e-router do not advertise to c-router the route to network 3 because they learned the route from c-router. They do, however, advertise the route to network 3 to each other. When c-router goes down, d-router and e-router perform their own count to infinity before they remove the route to network 3. This problem can be addressed using a technique known as “triggered updates.”

With triggered updates, when an external router crashes or a local link goes down, the local router immediately sends an update to its neighbors. This update advertises the routes with infinite cost that were deleted from the local router’s routing table and tells the neighbors to also remove them. With triggered updates, neighbors are informed of changes quickly; bandwidth is also used efficiently, because triggered updates include only the routes that have changed.

For an example of how this works, let’s look again at Figure Three. If c-router crashes, e-router and d-router wait 180 seconds and remove the routes to networks 1, 2, and 3 from their routing tables. They then send each other triggered updates with a metric of 15 for networks 1, 2, and 3. Thus, they tell each other that they cannot reach these networks, and no count to infinity occurs.

Split horizon, poison reverse, and triggered updates handle most slow convergence problems. They do not, however, increase the RIP network diameter or add support for network bit masks. Another major drawback is that RIP cannot disseminate the network bit masks needed to properly interpret routes. This problem alone makes RIP a poor choice for modern networks. Fortunately, an updated version of RIP, known as RIPv2, solves this problem.

RIPv2

Figure Four: Format for RIPv2 update packet.

RIP Version 2 (RIPv2) adds a “network mask” field and a “next hop address” field to the original RIP packet. Remarkably, RIPv2 adds these capabilities while remaining completely compatible with RIP. RIP and RIPv2 routers can coexist on a single network without any problems. All of the features of RIPv2 are implemented in unused fields of the original RIP packet, as shown in Figure Four.

The command, version, address family, IP address, and metric fields are exactly the same as those used in basic RIP, except this time the version field contains a 2. The subnet mask field contains the network bit mask associated with the destination, and the “next hop address” field provides the address of the gateway. In basic RIP, the gateway is always assumed to be the router that sends out the update. The next hop address field specifically identifies the gateway to be used with that packet, allowing a RIPv2 router to provide updates for routers that don’t run RIPv2. If the next hop address is 0.0.0.0, the router that sends the update is assumed to be the gateway for the route.

The two remaining fields, routing domain and route tag, have limited utility. Route tag is not used by RIPv2. The routing domain value is the process number of the RIPv2 process that issued this update if the router runs multiple RIPv2 processes. Routers do not really run multiple RIPv2 processes, so this field always contains 0.

In addition to support for address masks, RIPv2 uses multicasting to reduce the load on systems that do not want RIPv2 updates; RIPv2 also provides an authentication scheme to prevent accidental updates from misconfigured hosts. RIPv2 is the only version of RIP that is suitable for use on a modern network.

Whereas routed is the program that implements RIP, you would use the gated program to run RIPv2. gated actually combines several different routing protocols in a single software package. This means that the routing table can be built using multiple protocols and routing policies can be implemented that prefer routes learned from one protocol over those from another. Needless to say, with all that flexibility comes a fair bit of complexity, and for that reason, configuring gated is outside the scope of this article. Check out the gated man page for more information. Refer to the For More Information sidebar for additional sources.

Still Not Perfect

Despite its improvements, RIPv2 is still RIP and still contains some of the same limitations. For example, it uses the same distance-vector algorithm for determining the best route and therefore limits the diameter of the network to 15 hops. The only way to get around this limitation is to use a protocol that employs a different algorithm. The best example of this is the link state protocol OSPF (Open Shortest Path First), which is used for large national networks. If you’re interested in learning more about OSPF, please check out the link in the For More Information sidebar. Still, if you’re just experimenting with routing, or want to convert your Linux box into a simple network router, RIPv2 should be more than adequate for the job.

Craig Hunt is the best-selling author of O’Reilly & Associates’ Internetworking with TCP/IP. He can be reached at craig.hunt@wrotethebook.com.