Routing tables

IP routing requires each router to make packet forwarding decisions independently of the other routers. Thus, an IP router isinterested only in finding the next hop on the way to a packet’s final destination. You can say that IP routing is a little myopic this way. But this myopia is a strength because it allows IP to route easily around failures. A router finds the next hop for a packet by looking up the packet’s destination IP address in a lookup table called the routing table. The router then forwards the packet out the network interface returned by this lookup.

To expand this description a little more, routing consists of the following steps:

1. Look up the destination IP address of the packet in the routing table to get a list of next-hop entries.

2. Select one next hop from this list.

3. Determine the MAC address of this next hop.

4. Update the packet and frame headers, a task that includes rewriting the destination MAC address and TTL in the IP header.

5. Forward the packet out the network interface specified by the selected next hop.

How Routing Table Lookups Work

Briefly, a routing table contains entries whose key is the IP address prefix and whose result is a list of next hops.A routing table does not contain an entry for every possible IP address that is reachable in the network. Instead, addresses are grouped into subnets, where a subnet is a group of addresses that share the same number of leftmost bits. The number of shared bits is denoted by a mask length (an alternate but older model is to denote the shared bits with a network mask). An IP address prefix is defined as the start of the shared bits along with the mask length. For example, the address prefix 1.1.1.0/24 includes every IP address from 1.1.1.0 to 1.1.1.255 because the upper 24 bits, 1.1.1,are shared across all those addresses.

In this figure, each first line expands the address or address prefix on the left into the associated four octets of 8 bits, for a total of 32 bits. The first line expands 1.1.1.0/24, showing that each of the first three octets contains 1 in binary, whereas the last octet is shown full of asterisks (*), meaning that the bit can be either 0 or 1.Thus, the addresses 1.1.1.1 and1.1.1.16 will be matched by the prefix 1.1.1.0/24. But the address1.1.2.1 will not be matched by this prefix, because the upper 24 bits of 1.1.2.1 differ from the upper 24 bits of the prefix entry.

Why is this interesting? An address prefix allows us to aggregate a bunch of addresses into a single entry. Consider a router with two links that can reach a block of about two hundred addresses. It might be ableto reach the first set of these addresses, starting from 1.1.1.1, via link 1, whereas it reaches the second set of these addresses,starting from 1.1.1.129, via link 2. The routing table on this router needs only two entries—one for 1.1.1.0/25, and the other for1.1.1.128/25—instead of two hundred routing table entries.

In a different scenario, let’s assume that only two addresses in the address block, say 1.1.1.31 and 1.1.1.67, live on link1, whereas the rest live on link 2. I now need three routing table entries,one each associating 1.1.1.31/32 and 1.1.1.67/32 with link 1, and one entry for 1.1.1.0/24 that associates the rest of the addresses with link 2. This is still a significant savings over listing every oneof the two hundred addresses.Thus, given a lookup table containing these three address prefixes, a routing table lookup for 1.1.1.31 needs to return link 1, and a routing table lookup for 1.1.1.2 needs to return link 2. This is done by selecting an entry with the longest prefix length from a given set of matching prefixes. For 1.1.1.31, the entry with the longest matching prefix is 1.1.1.31/32, whereas for the address 1.1.1.2, the entry with the longest matching prefix is 1.1.1.0/24. Therefore, this match algorithm is called the longest prefix match (LPM).

The longest prefix matching problem is the problem of finding the forwarding table entry containing the longest prefix among all prefixes (in other forwarding table entries) matching the incoming packet’s destination address. This longest prefix is called the longest matching prefix.

The forwarding table in router R1 is shown above. If an incoming packet at this router has a destination address of 200.11.0.1, it will match only the prefix 200.11.0.0/22 (entry #2) and hence will be forwarded to router R3. ref