TCP/IP Protocols ( 9) --IP Routing

Routing is one of the most important functions of IP. Datagrams to be routed can be generated either on the local host or on some other host. In the latter case this host must be configured to act as a router, or datagrams received through the network interfaces that are not ours are dropped (i.e., silently discarded).

A routing daemon is normally a user process. The most common daemons used on Unix systems are the programs routed and gated. Our main interest in the current chapter is how a single IP layer makes its routing decisions.

The routing table is accessed frequently by IP (on a busy host this could mean hundreds of times a second) but is updated much less frequently by a routing daemon (possibly about once every 30 seconds). The routing table can also be updated when ICMP "redirect" messages are received, and by the route command. This command is often executed when the system is bootstrapped, to install some initial routes. We'll also use the netstat command in this chapter to display the routing table.

Routing Principles

The information contained in the routing table drives all the routing decisions made by IP. The steps that IP performs when it searches its routing table:

1. Search for a matching host address.

2. Search for a matching network address.

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

netstat command with the -r option lists the routing table and the -n option prints IP addresses in numeric format, rather than as names.

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 .

M The route was modified by a redirect .

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 complexity of a host's routing table depends on the topology of the networks to which the host has access.

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

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

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

4. The final step is when other host-specific or network-specific routes are added. 

Initializing a Routing Table

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.

Route command example: route add default sun 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.

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.

ICMP Host and Network Unreachable Errors

The ICMP "host unreachable" error message is sent by a router when it receives an IP datagram that it cannot deliver or forward.

To Forward or Not to Forward

In linux Uncomment the line “#net.ipv4.ip_forward=1” in the file /etc/sysctl.conf to enable packet forwarding for IPv4.

ICMP Redirect Errors

The ICMP redirect error is sent by a router to the sender of an IP datagram when the datagram should have been sent to a different router.

A common use for redirects is to let a host with minimal routing knowledge build up a better routing table over time. The host can start with only a default route (either Rl or R2 from our example in Figure 9.3) and anytime this default turns out to be wrong, it'll be informed by that default router with a redirect, allowing the host to update its routing table accordingly. ICMP redirects allow TCP/IP hosts to be dumb when it comes to routing, with all the intelligence in the routers.

4.4BSD, when acting as a router, performs the following checks, all of which must be true before an ICMP
redirect is generated.

1. The outgoing interface must equal the incoming interface.

2. The route being used for the outgoing datagram must not have been created or modified by an ICMP redirect, and must not be the router's default route.

3. The datagram must not be source routed.

4. The kernel must be configured to send redirects.

Additionally, a 4.4BSD host that receives an ICMP redirect performs some checks before modifying its routing table. These are to prevent a misbehaving router or host, or a malicious user, from incorrectly modifying a system's routing table.

1. The new router must be on a directly connected network.

2. The redirect must be from the current router for that destination.

3. The redirect cannot tell the host to use itself as the router.

4. The route that's being modified must be an indirect route.

Our final point about redirects is that routers should send only host redirects and not network redirects. Subnetting makes it hard to specify exactly when a network redirect can be sent instead of a host redirect. Some hosts treat a received network redirect as a host redirect, in case a router sends the wrong type.

ICMP Router Discovery Messages

one way to initialize a routing table is with static routes specified in configuration files. This is often used to set a default entry. A newer way is to use the ICMP router advertisement and solicitation messages.

The general concept is that after bootstrapping, a host broadcasts or multicasts a router solicitation message. One or more routers respond with a router advertisement message. Additionally, the routers periodically broadcast or multicast their router advertisements, allowing any hosts that are listening to update their routing table accordingly.

Format of ICMP router solicitation message:

1	7	8	15	16	31
Type(10)		Code(0)		checksum
Unused (set as 0)

Format of ICMP router advertisement message:

1	7	8	15	16	31
Type(10)		Code(0)		checksum
number of address		address entry size(2)		lifetime
router address[1]
preference level[1]
router address[2]
...

Multiple addresses can be advertised by a router in a single message. Number of addresses is the number. Address entry size is the number of 32-bit words for each router address, and is always 2. Lifetime is the number of seconds that the advertised addresses can be considered valid.

One or more pairs of an IP address and a preference then follow. The IP address must be one of the sending router's IP addresses. The preference level is a signed 32-bit integer indicating the preference of this address as a default router address, relative to other router addresses on the same subnet. Larger values
imply more preferable addresses. The preference level 0x80000000 means the corresponding address, although advertised, is not to be used by the receiver as a default router address. The default value of the preference is normally 0.

Router Operation

When a router starts up it transmits periodic advertisements on all interfaces capable of broadcasting or multicasting. These advertisements are not exactly periodic, but are randomized, to reduce the probability of synchronization with other routers on the same subnet. The normal time interval between advertisements is between 450 and 600 seconds. The default lifetime for a given advertisement is 30minutes.

Another use of the lifetime field occurs when an interface on a router is disabled. In that case the router can transmit a final advertisement on the interface with the lifetime set to 0.

In addition to the periodic, unsolicited advertisements, a router also listens for solicitations from hosts. It responds to these solicitations with a router advertisement. If there are multiple routers on a given subnet, it is up to the system administrator to configure the preference level for each router as appropriate. For example, the primary default  router would have a higher preference than a backup.

Host Operation

Upon bootstrap a host normally transmits three router solicitations, 3 seconds apart. As soon as a valid advertisement is received, the solicitations stop.

A host also listens for advertisements from adjacent routers. These advertisements can cause the host's default router to change. Also, if an advertisement is not received for the current default, that default can time out.

As long as the normal default router stays up, that router will send advertisements every 10 minutes, with a lifetime of 30 minutes. This means the host's default entry won't time out, even if one or two advertisements are lost.

Implementation

The router discovery messages are normally generated by and processed by a user process (a daemon). This adds yet another program updating the routing table in Figure 9.1, although it would only add or delete a default entry. The daemon would have to be configured to act as a router or a host.