A workstation's routing table
Even workstations with a single interface have a routing table and must scan it before deciding what to do with a packet. The tests above are performed multiple times--once for each entry in the workstation's routing table. Note that having a routing table does not necessarily mean that the workstation can route; it is simply the means for determining how to send packets. Here is an example routing table from a workstation. The Destination field contains the network address, and the Genmask field contains the subnet mask. By reading this table from top to bottom, you make decisions about what to do with a packet just like the kernel does.

$ route -n
Kernel IP routing table

1. All packets for the network 192.168.18.0/23 (remember that /23 is just another representation of /255.255.254.0) are sent out via interface eth0 without using a gateway. This is denoted by 0.0.0.0 in the Gateway field and the lack of a G flag in the Flags field.
2. All packets for the network 127.0.0.0/8 are sent out via interface lo. This is known as the loopback interface, and it is reserved for sending packets to the local machine.
3. Any other packet will be forwarded to the gateway address (192.168.18.1), which is accessible via interface eth0. If you look at the Destination field, you will notice that the network is 0.0.0.0 with a Genmask of 0.0.0.0. This matches every packet, and is known as a default route.

When the kernel encounters this entry, it notices that the G flag is set, which means that the packet is to be sent to the IP address listed in the Gateway field for forwarding.

Note that the table is sorted in reverse order by the number of bits in the Genmask (subnet mask) field. This is so the kernel walks the table in most-to-least restrictive order (the last entry will always be the default route). As soon as a suitable > and Genmask (really, subnet and subnet mask) pair is found, the packet is sent via that interface. The routing table on a router functions exactly the same way, which is the topic of the next section.

A gateway's routing table
To forward packets, a router consults its routing table much like a workstation and sends the packet on its way over the appropriate interface. Where a router differs from workstation is in what sort of traffic it will accept. When routing is enabled in the Linux kernel, the router will accept packets destined for its Ethernet address, but with IP destination headers pointing somewhere else. A machine without routing might accept these packets from the wire (because of the correct Ethernet address), but would then discard them when it discovered that they were not destined for its IP address. The router knows that its job is to forward, so it accepts the packet and examines its headers to find out where it's headed. A routing table on a router looks like this and is taken from the router depicted in Figure 2.3.

Figure 2.3: Sample Router

$ route -n
Kernel IP routing table

We can tell a lot about this router by looking at the routing table (even without the aid of the illustration).

1. The first two entries are known as host routes; they can be used to access only a single destination IP. This is denoted by the H in the Flags field, and the fact that the Genmask is 255.255.255.255 (or /32). Both of these routes have a metric of 1 and a gateway on the 192.168.10.0/24 network, which is why the Iface is set to eth1. When the kernel encounters a packet destined for one of these exact IP addresses, it will be forwarded to the specified gateway over the eth1 interface.  
2. The next entry is just like the entry that a workstation has for its network interface. It is a network route for the locally connected network, 192.168.10.0/24. You can tell this because the gateway is set to 0.0.0.0 (which implies a local interface), and there is no G in the Flags field. We can safely assume that the eth1 interface has an IP address in the 192.168.10.0/24 subnet. The figure confirms this; the interface is 192.168.10.1.
   For those of you familiar with other Unices, this is one point where Linux differs. It does not need to use the IP address of the interface as the gateway for locally connected networks (although this type of configuration will also work). It automatically uses the interface listed in the Iface field. By looking at the figure, we might surmise that the 192.168.10.0/24 network is a network for routers.
3. The fourth entry is just like the third, except that it is for interface eth0, which we can see is connected to the 192.168.18.0/23 network. This is the network where the workstations are--the LAN.
4. The next two (fifth and sixth) entries are network routes which point out over gateways on the router network. All traffic which falls into IP address ranges denoted by the network address (Destination) and subnet mask (Genmask) will be forwarded to the appropriate WAN router. A safe bet would be that these correspond to IP address space in use in other locations. If you notice their Genmask, you will understand why they first appear now in the routing table. The table is sorted from most-restrictive to least-restrictive, and 255.255.192.0 is the widest subnet mask yet.
5. The next to last entry in the table is for the loopback device, lo, just like on a workstation.
6. The last entry is the default route. Just like workstations, routers have these in case they do not know where else to forward a packet. In our example, the default route points to the 192.168.10.20 machine, and is heavily used (note the Use field). 192.168.10.20 could be the Internet router or a firewall.

Preference for Two Equivalent Routes
Note that the table is sorted in reverse order by the number of bits in the Genmask field (just as it is on a workstation). The kernel checks each entry in the table against the destination IP address of the packet it received, and it forwards the packet on the first match it finds. This means that multiple (static) routes to the same destination are not used if you have simple static routing. In the case of a tie--two entries with identical Destination and Genmask--the one with the lower metric value is chosen. Should the metrics be equal, the more recent entry is chosen. The kernel doesn't remember when the entries were made for static routes, but it knows that when someone enters a route equivalent to an existing route, the intention is most likely to use the new route. This is convenient if you need to temporarily route around a particular gateway or have some other testing in mind. You can enter the temporary route, and it will be used. When you delete it, the previous route is used.

Unroutable Packets
Each of the other routers must also have routing table entries for the network(s) and host(s) it is expected to forward. If they don't, then they will either use their default route, or, if no default route exists, they will reply with an ICMP: host unreachable message. The pathological case is when the route points back to the sending router, which forms a loop. (Router A sends to router B, which sends to router A, and so on...). Fortunately, IP packets all contain a TTL (Time To Live) field which is decremented every time the packet is forwarded. Eventually (actually, very quickly), the packet will be discarded. Nonetheless, such misconfigurations mean that the packet will not find its destination, which results in performance degradation for correctly routed packets on the network. Just say No to routing loops!

Misconfigured Routes--ICMP Redirects
Another situation arises when router A forwards a packet to router B when it could (and should) have forwarded it directly to router C. That is, all three routers are on the same subnet, but router A is ignorant of (one or more of) router C's routes. When router A forwards a packet to router B, and router B notices that the packet should have been sent directly to router C, it forwards the packet, but alerts router A to the fact with an ICMP: redirect message telling router A how to forward packets of that type in the future. Router A notes this by adding a new (host route) entry in its routing table. You can quickly spot these entries because they have the UDGH flags all set. Of note is the D, which indicates that the route was added either dynamically or due to a redirect.