Routers and forwarding tables

A router joins networks. For every packet it receives, it reads the destination IP address, looks it up in its forwarding table, and sends the packet out of the matching link toward the next router (the next hop). Each router only decides one step; the packet finds its way hop by hop.

A forwarding table

A destination matches an entry when its first prefix-length bits equal the network's. 10.1.2.7 matches the first three entries. Which one wins?

Longest prefix match

The router picks the matching entry with the longest prefix: it is the most specific. So 10.1.2.7 goes to D, 10.1.9.9 to C, and 10.200.0.1 to B. Anything that matches nothing else matches 0.0.0.0/0, which has no network bits at all: the default route, usually "towards the internet".

def to_number(ip):
    n = 0
    for part in ip.split("."):
        n = n * 256 + int(part)
    return n

table = [("10.0.0.0", 8, "B"), ("10.1.0.0", 16, "C"), ("10.1.2.0", 24, "D"), ("0.0.0.0", 0, "E")]

def next_hop(ip):
    best, best_len = None, -1
    for net, length, hop in table:
        mask = (0xFFFFFFFF << (32 - length)) & 0xFFFFFFFF
        if to_number(ip) & mask == to_number(net) and length > best_len:
            best, best_len = hop, length
    return best

for ip in ["10.1.2.7", "10.1.9.9", "10.200.0.1", "8.8.8.8"]:
    print(ip, "->", next_hop(ip))

Real routers hold close to a million internet routes and must decide in nanoseconds, so they use special hardware (TCAM) or tries over the address bits (see the Tries lesson in Data Structures) instead of checking every entry.

Forwarding and routing

Forwarding is the fast, per-packet step: look up, send out. Routing is the slower process that fills the tables, by routers telling each other about networks and link costs. The next lesson shows the two classic routing algorithms.

Each router also lowers the packet's TTL (time to live) by 1 and drops it at 0, so a packet caught in a loop cannot circle forever. The traceroute tool uses this to list the routers on a path.

Mark lesson complete