9.2 Routing Principles

The place to start our discussion of IP routing is to understand what is maintained by the kernel in its routing table. The information contained in the routing table drives all the routing decisions made by IP.

In Section 3.3 we listed the steps that IP performs when it searches its routing table.

Search for a matching host address.
Search for a matching network address.
Search for a default entry. (The default entry is normally specified in the routing table as a network entry, with a network ID of 0.)

A matching host address is always used before a matching network address.

The routing done by IP, when it searches the routing table and decides which interface to send a packet out, is a routing mechanism. This differs from a routing policy, which is a set of rules that decides which routes go into the routing table. IP performs the routing mechanism while a routing daemon normally provides the routing policy.

Simple Routing Table

Let's start by looking at some typical host routing tables. On the host svr4 we execute the netstat command with the -r option to list the routing table and the -n option, which prints IP addresses in numeric format, rather than as names . (We do this because some of the entries in the routing table are for networks, not hosts . Without the -n option, the netstat command searches the file /etc/networks for the network names. This confuses the discussion by adding another set of names ” network names in addition to hostnames.)

 svr4 %  netstat -rn  Routing tables     Destination       Gateway            Flags    Refcnt  Use    Interface     140.252.13.65     140.252.13.35      UGH      0       0      emd0     127.0.0.1         127.0.0.1          UH       1       0      lo0     default           140.252.13.33      UG       0       0      emd0     140.252.13.32     140.252.13.34      U        4       25043  emd0

The first line says for destination 140.252.13.65 (host slip ) the gateway (router) to send the packet to is 140.252.13.35 ( bsdi ). This is what we expect, since the host slip is connected to bsdi with a SLIP link, and bsdi is on the same Ethernet as this host.

There are five different flags that can be printed for a given route.

`U`	The route is up.
`G`	The route is to a gateway (router). If this flag is not set, the destination is directly connected.
`H`	The route is to a host, that is, the destination is a complete host address. If this flag is not set, the route is to a network, and the destination is a network address: a net ID, or a combination of a net ID and a subnet ID.
`D`	The route was created by a redirect (Section 9.5).
`M`	The route was modified by a redirect (Section 9.5).

The G flag is important because it differentiates between an indirect route and a direct route. (The G flag is not set for a direct route.) The difference is that a packet going out a direct route has both the IP address and the link-layer address specifying the destination (Figure 3.3). When a packet is sent out an indirect route, the IP address specifies the final destination but the link-layer address specifies the gateway (that is, the next -hop router). We saw an example of this in Figure 3.4. In this routing table example we have an indirect route (the G flag is set) so the IP address of a packet using this route is the final destination (140.252.13.65), but the link-layer address must correspond to the router 140.252.13.35.

It's important to understand the difference between the G and H flags. The G flag differentiates between a direct and an indirect route, as described above. The H flag, however, specifies that the destination address (the first column of netstat output) is a complete host address. The absence of the H flag means the destination address is a network address (the host ID portion will be 0). When the routing table is searched for a route to a destination IP address, a host address entry must match the destination address completely, while a network address only needs to match the network ID and any subnet ID of the destination address. Also, some versions of the netstat command print all the host entries first, followed by the network entries.

The reference count column gives the number of active uses for each route. A connection-oriented protocol such as TCP holds on to a route while the connection is established. If we established a Telnet connection between the two hosts svr4 and slip, we would see the reference count go to 1. With another Telnet connection the reference count would go to 2, and so on.

The next column ("use") displays the number of packets sent through that route. If we are the only users of the route and we run the ping program to send 5 packets, the count goes up by 5. The final column, the interface, is the name of the local interface.

The second line of output is for the loopback interface (Section 2.7), always named lo0. The G flag is not set, since the route is not to a gateway. The H flag indicates that the destination address (127.0.0.1) is a host address, and not a network address. When the G field is not set, indicating a direct route, the gateway column gives the IP address of the outgoing interface.

The third line of output is for the default route. Every host can have one or more default routes. This entry says to send packets to the router 140.252.13.33 ( sun ) if a more specific route can't be found. This means the current host ( svr4 ) can access other systems across the Internet through the router sun (and its SLIP link), using this single routing table entry. Being able to establish a default route is a powerful concept. The flags for this route ( UG ) indicate that it's a route to a gateway, as we expect.

Here we purposely call sun a router and not a host because when it's used as a default router, its IP forwarding function is being used, not its host functionality.

The Host Requirements RFC specifically states that the IP layer must support multiple default routes. Many implementations , however, don't support this. When multiple default routes exist, a common technique is to round robin among them. This is what Solaris 2.2 does, for example.

The final line of output is for the attached Ethernet. The H flag is not set, indicating that the destination address (140.252.13.32) is a network address with the host portion set to 0. Indeed, the low-order 5 bits are 0 (Figure 3.11). Since this is a direct route (the G flag is not set) the gateway column specifies the IP address of the outgoing interface.

Implied in this final entry, but not shown by the netstat output, is the mask associated with this destination address (140.252.13.32). If this destination is being compared against the IP address 140.252.13.33, the address is first logically ANDed with the mask associated with the destination (the subnet mask of the interface, 0xffffffe0, from Section 3.7) before the comparison. For a network route to a directly connected network, the routing table mask defaults to the subnet mask of the interface. But in general the routing table mask can assume any 32-bit value. A value other than the default can be specified as an option to the route command.

The complexity of a host's routing table depends on the topology of the networks to which the host has access.

The simplest (but least interesting) case is a host that is not connected to any networks at all. The TCP/IP protocols can still be used on the host, but only to communicate with itself! The routing table in this case consists of a single entry for the loopback interface.
Next is a host connected to a single LAN, only able to access hosts on that LAN. The routing table consists of two entries: one for the loopback interface and one for the LAN (such as an Ethernet).
The next step occurs when other networks (such as the Internet) are reachable through a single router. This is normally handled with a default entry pointing to that router.
The final step is when other host-specific or network-specific routes are added. In our example the route to the host slip, through the router bsdi, is an example of this.

Let's follow through the steps IP performs when using this routing table to route some example packets on the host svr4.

Assume the destination address is the host sun, 140.252.13.33. A search is first made for a matching host entry. The two host entries in the table ( slip and localhost ) don't match, so a search is made through the routing table again for a matching network address. A match is found with the entry 140.252.13.32 (the network IDs and subnet IDs match), so the emd0 interface is used. This is a direct route, so the link-layer address will be the destination address.
Assume the destination address is the host slip, 140.252.13.65. The first search through the table, for a matching host address, finds a match. This is an indirect route so the destination IP address remains 140.252.13.65, but the link-layer address must be the link-layer address of the gateway 140.252.13.35, and the interface is emd0.
This time we're sending a datagram across the Internet to the host aw.com (192.207.117.2). The first search of the routing table for a matching host address fails, as does the second search for a matching network address. The final step is a search for a default entry, and this succeeds. The route is an indirect route through the gateway 140.252.13.33 using the interface emd0.
In our final example we send a datagram to our own host. There are four ways to do this, using either the hostname, the host IP address, the loopback name, or the loopback IP address:
```
 ftp svr4      ftp 140.252.13.34      ftp localhost      ftp 127.0.0.1 
```
In the first two cases, the second search of the routing table yields a network match with 140.252.13.32, and the packet is sent down to the Ethernet driver. As we showed in Figure 2.4 it will be seen that this packet is destined for the host's own IP address, and the packet is sent to the loopback driver, which sends it to the IP input queue.

In the latter two cases, specifying the name of the loopback interface or its IP address, the first search of the routing table finds the matching host address entry, and the packet is sent to the loopback driver, which sends it to the IP input queue.

In all four cases the packet is sent to the loopback driver, but two different routing decisions are made.

Initializing a Routing Table

We never said how these routing table entries are created. Whenever an interface is initialized (normally when the interface's address is set by the ifconfig command) a direct route is automatically created for that interface. For point-to-point links and the loopback interface, the route is to a host (i.e., the H flag is set). For broadcast interfaces such as an Ethernet, the route is to that network.

Routes to hosts or networks that are not directly connected must be entered into the routing table somehow. One common way is to execute the route command explicitly from the initialization files when the system is bootstrapped. On the host svr4 the following two commands were executed to add the entries that we showed earlier:

 route add default sun 1     route add slip bsdi 1

The third arguments ( default and slip ) are the destinations, the fourth argument is the gateway (router), and the final argument is a routing metric. All that the route command does with this metric is install the route with the G flag set if the metric is greater than 0, or without the G flag if the metric is 0.

Unfortunately, few systems agree on which start-up file contains the route commands. Under 4.4BSD and BSD/386 it is /etc/netstart, under SVR4 it is /etc/inet/rc.inet, under Solaris 2.x it is /etc/rc2.d/S69inet, SunOS 4.1.x uses /etc/rc.local, and AIX 3.2.2 uses /etc/rc.net.

Some systems allow a default router to be specified in a file such as /etc/defaultrouter, and this default is added to the routing table on every reboot.

Other ways to initialize a routing table are to run a routing daemon (Chapter 10) or to use the newer router discovery protocol (Section 9.6).

A More Complex Routing Table

The host sun is the default router for all the hosts on our subnet, since it has the dialup SLIP link that connects to the Internet (see the figure on the inside front cover).

 sun %  netstat -rn  Routing tables     Destination       Gateway            Flags    Refcnt Use       Interface     140.252.13.65     140.252.13.35      UGH      0      171       le0     127.0.0.1         127.0.0.1          UH       1      766       lo0     140.252.1.183     140.252.1.29       UH       0      0         sl0     default           140.252.1.183      UG       1      2955      sl0     140.252.13.32     140.252.13.33      U        8      99551     le0

The first two entries are identical to the first two for the host svr4: a host-specific route to slip through the router bsdi, and the loopback route.

The third line is new. It is a direct route (the G flag is not set) to a host (the H flag is set) and corresponds to our point-to-point link, the SLIP interface. If we compare it to the output from the ifconfig command,

 sun  % ifconfig sl0  Sl0: flags=105<UP,POINTOPOINT,RUNNING>             inet 140.252.1.29 --> 140.252.1.183 netmask ffffff00

we see that the destination address in the routing table is the other end of the point-to-point link (the router netb ) and the gateway address is really the local IP address of the outgoing interface (140.252.1.29). (We said earlier that the gateway address printed by netstat for a direct route is the local IP address of the interface to use.)

The default entry is an indirect route ( G flag) to a network (no H flag), as we expect. The gateway address is the address of the router (140.252.1.183, the other end of the SLIP link) and not the local IP address of the SLIP link (140.252.1.29). Again, this is because it is an indirect route, not a direct route.

We should also note that the third and fourth lines output by netstat (the ones with an interface of sl0 ) are created by the SLIP software being used when the SLIP line is brought up, and deleted when the SLIP link is brought down.

No Route to Destination

All our examples so far have assumed that the search of the routing table finds a match, even if the match is the default route. What if there is no default route, and a match isn't found for a given destination?

The answer depends on whether the IP datagram being routed was generated on the host or is being forwarded (e.g., we're acting as a router). If the datagram was generated on this host, an error is returned to the application that sent the datagram, either "host unreachable" or "network unreachable." If the datagram was being forwarded, an ICMP host unreachable error is sent back to original sender. We examine this error in the following section.