Forwarding tables and longest prefix match

A router does two jobs. Routing, the control plane, learns which networks exist and how to reach them: from its own interfaces, from routes an operator types in and from routing protocols. Forwarding, the data plane, uses the result. For every packet that arrives, the router looks up the destination address in its forwarding table and sends the packet out of one interface towards one next hop. The lookup rule is longest prefix match: several prefixes in the table can contain the destination (a default route contains every address), and the router uses the most specific of them, the matching prefix with the most bits. This lesson works the rule by hand, reads a routing table column by column, settles ties between routes to the same prefix, and counts why routers keep their prefixes in a trie.

Routing builds the table, forwarding uses it

The two planes are two programs with very different deadlines. The control plane runs routing protocols, which exchange messages every few seconds and recompute routes when something changes. Everything it learns goes into the routing information base (RIB), the table that holds all routing information received from routing peers, often several routes to the same prefix. From the RIB the router chooses one best route per prefix and installs it in the forwarding information base (FIB), which records for each reachable prefix at least the outgoing interface and the next hop (RFC 3222, section 5.3). The data plane reads only the FIB, once per packet. A 10 Gb/s Ethernet port can deliver about 14.9 million minimum-size frames a second (64 bytes each, plus 20 bytes of preamble and gap on the wire), which leaves about 67 nanoseconds per lookup.

Routes reach the RIB in three ways. Connected routes cover the subnets of the router’s own interfaces and need no next hop. Static routes are configured by an operator. Dynamic routes come from protocols: OSPF inside one network and BGP between networks, the subjects of the next lessons in this module.

Keeping the planes apart has visible effects. A router can go on forwarding with its last FIB while its routing software restarts, and OSPF’s graceful restart (RFC 3623) is built on exactly that: the neighbours keep sending traffic through the restarting router instead of routing around it. And while routing protocols work out a new answer after a failure, packets still follow the old FIB, so different routers can briefly disagree. The lessons on link-state and distance-vector routing come back to that moment.

Longest prefix match, worked by hand

A route matches a destination when the first n bits of the destination equal the first n bits of the route’s prefix, where n is the prefix length. RFC 1812, the requirements for IPv4 routers, calls this the Basic Match rule, and its next rule, Longest Match, keeps only the matching routes with the largest prefix length (RFC 1812, section 5.2.4.3). Here is a small table of the kind a campus router holds, with addresses from the documentation ranges of RFC 5737 standing in for public ones:

• 0.0.0.0/0 via 203.0.113.1: the default route to the upstream provider.
• 10.0.0.0/8 via 10.255.0.1: the whole internal network, through the core.
• 10.20.0.0/16 via 10.255.0.5: campus B.
• 10.20.30.0/24 via 10.255.0.9: the lab building on campus B.
• 10.20.30.128/25 on eth2, connected: the lab subnet this router is attached to.
• 192.0.2.7/32 via 10.255.0.13: a host route to one monitoring server.

# Longest prefix match by hand: every route whose prefix contains the destination is a candidate,
# and the router uses the candidate with the longest prefix (RFC 1812, section 5.2.4.3).
import ipaddress

TABLE = [
    # prefix, next hop or interface, why the route exists
    ("0.0.0.0/0", "203.0.113.1", "default route to the upstream provider"),
    ("10.0.0.0/8", "10.255.0.1", "the whole internal network, via the core"),
    ("10.20.0.0/16", "10.255.0.5", "campus B"),
    ("10.20.30.0/24", "10.255.0.9", "the lab building on campus B"),
    ("10.20.30.128/25", "eth2 (connected)", "the lab subnet this router is attached to"),
    ("192.0.2.7/32", "10.255.0.13", "a host route to one monitoring server"),
]
ROUTES = [(ipaddress.ip_network(p), hop) for p, hop, _ in TABLE]

for destination in ["10.20.30.200", "10.20.30.5", "10.20.99.1", "10.99.0.1", "198.51.100.10", "192.0.2.7"]:
    address = ipaddress.ip_address(destination)
    candidates = [(net, hop) for net, hop in ROUTES if address in net]
    best_net, best_hop = max(candidates, key=lambda c: c[0].prefixlen)
    matches = ", ".join(f"/{net.prefixlen}" for net, _ in candidates)
    print(f"{destination:<14} matches {matches:<22} -> {str(best_net):<16} via {best_hop}")

print()
print("10.20.30.200 in binary:", ".".join(f"{b:08b}" for b in ipaddress.ip_address("10.20.30.200").packed))
print("10.20.30.128 in binary:", ".".join(f"{b:08b}" for b in ipaddress.ip_address("10.20.30.128").packed))
print("The first 25 bits are equal, so 10.20.30.128/25 contains 10.20.30.200.")

10.20.30.200   matches /0, /8, /16, /24, /25  -> 10.20.30.128/25  via eth2 (connected)
10.20.30.5     matches /0, /8, /16, /24       -> 10.20.30.0/24    via 10.255.0.9
10.20.99.1     matches /0, /8, /16            -> 10.20.0.0/16     via 10.255.0.5
10.99.0.1      matches /0, /8                 -> 10.0.0.0/8       via 10.255.0.1
198.51.100.10  matches /0                     -> 0.0.0.0/0        via 203.0.113.1
192.0.2.7      matches /0, /32                -> 192.0.2.7/32     via 10.255.0.13

10.20.30.200 in binary: 00001010.00010100.00011110.11001000
10.20.30.128 in binary: 00001010.00010100.00011110.10000000
The first 25 bits are equal, so 10.20.30.128/25 contains 10.20.30.200.

The destination 10.20.30.200 lies inside five prefixes at once, nested like boxes: the default route, the /8, the /16, the /24 and the /25. The binary forms show why the /25 contains it: the first 25 bits of 10.20.30.200 and 10.20.30.128 are equal, and only the last seven differ. So the router puts the packet out of eth2, straight onto the attached subnet. An address outside every specific prefix, such as 198.51.100.10, still matches the default route, whose prefix length of 0 asks for no bits to match at all. A host route, with all 32 bits fixed, matches exactly one address.

Why trust the most specific route? It carries the most information. A /25 describes 128 addresses and a /8 more than 16 million, so the /25 was configured or announced by someone closer to those 128 addresses. Classless routing depends on this. A provider can announce one aggregate for all its customers, and a customer who moved to another provider without renumbering is still reached through the new provider, whose more specific route punches a hole in the old aggregate: longest match makes it win wherever both are heard (RFC 4632, sections 4.1 and 5.1). The same rule lets a wrong announcement of a more specific prefix capture traffic, which the routing security lesson of this module takes apart.

Reading a routing table

Operating systems and router vendors print their tables differently, but the same columns recur. Cisco’s CCNA exam topics list them as the components of a routing table: the routing protocol code, prefix, network mask, next hop, administrative distance, metric and gateway of last resort (CCNA 200-301 exam topics, 3.1).

• Prefix and mask: which destinations the route covers, such as 10.20.0.0/16.
• Next hop: the neighbouring router that receives the packet, such as 10.255.0.5; empty for a connected route.
• Interface: where the packet leaves the router, such as eth1.
• Source: connected, static, or the protocol that learned the route: O for OSPF on Cisco, proto static on Linux.
• Administrative distance: how much the router trusts the source, lower is better: 110 for OSPF on Cisco.
• Metric: the source’s own cost for the path, lower is better, such as 20.

On Linux, ip route show prints the table, and ip route get 10.20.30.5 asks the kernel which single route it would use for that address. The manual describes get as “equivalent to sending a packet along this path”, without sending anything (ip-route(8)). Asking for one address is the habit to build: a route can sit in the table and still carry none of the traffic you care about, as the next section shows.

Two kinds of entry deserve a name. The default route, 0.0.0.0/0 for IPv4 and ::/0 for IPv6, is the route of last resort, and Linux accepts the word default for it. Most hosts hold little else: one connected route for their own subnet and a default route to their gateway. A host route, /32 or /128, pins a single address, such as the loopback address of a router or one server that must take a special path. Linux can also hold routes that forward nothing: a blackhole route discards matching packets silently, and an unreachable route discards them and sends an ICMP host unreachable error. A network that announces an aggregate needs such a discard route, because RFC 4632 requires the originator of an aggregate to drop traffic that matches the aggregate but none of the more specific routes inside it; otherwise packets for unused addresses would loop towards the default route.

When two routes have the same prefix

Longest prefix match decides between different prefixes. When several routes share the same prefix, as happens whenever two protocols, or a protocol and an operator, describe the same network, the router needs another rule before it can install one of them. Within one protocol the metric decides, because the protocol’s own costs can be compared with each other: RFC 1812’s Best Metric rule compares metrics only between routes of the same routing domain. Between sources, metrics mean different things (a RIP hop count of 2 says nothing about an OSPF cost of 30), so routers rank the sources themselves. RFC 1812 calls this administrative preference, an integer from 0 to 255 where 0 is the most preferred and 255 means the route is never used (section 5.2.4.4). Cisco calls it administrative distance and documents its defaults: 0 for connected routes, 1 for static routes, 20 for routes from external BGP, 110 for OSPF, 120 for RIP and 200 for internal BGP. The distance is local to each router and is never sent to neighbours (Cisco).

# From the RIB (every route the router has learned) to the FIB (the one route used per prefix).
# For the same prefix, a lower administrative distance wins, then a lower metric. Distances are a
# vendor's local preference; these are the defaults Cisco documents (static 1, OSPF 110, RIP 120).
import ipaddress

RIB = [
    # prefix, source, administrative distance, metric, next hop
    ("10.20.0.0/16", "static", 1, 0, "10.255.0.21 (new firewall)"),
    ("10.20.0.0/16", "OSPF", 110, 20, "10.255.0.5"),
    ("10.20.30.0/24", "OSPF", 110, 30, "10.255.0.9"),
    ("10.20.30.0/24", "RIP", 120, 2, "10.255.0.17"),
    ("0.0.0.0/0", "static", 1, 0, "203.0.113.1 (primary link)"),
    ("0.0.0.0/0", "static", 250, 0, "198.51.100.1 (backup link, floating static)"),
]


def build_fib(rib):
    """Best route per prefix: lowest administrative distance, then lowest metric."""
    fib = {}
    for prefix, source, distance, metric, hop in rib:
        net = ipaddress.ip_network(prefix)
        best = fib.get(net)
        if best is None or (distance, metric) < (best[1], best[2]):
            fib[net] = (source, distance, metric, hop)
    return fib


def lookup(fib, destination):
    """Longest prefix match over the installed routes only."""
    address = ipaddress.ip_address(destination)
    nets = [net for net in fib if address in net]
    return max(nets, key=lambda n: n.prefixlen) if nets else None


def show(fib, title):
    print(title)
    for net in sorted(fib, key=lambda n: (n.prefixlen, n)):
        source, distance, metric, hop = fib[net]
        print(f"  {str(net):<15} {source:<7} [{distance}/{metric}] via {hop}")


fib = build_fib(RIB)
show(fib, "FIB built from the RIB:")
for destination in ["10.20.30.5", "10.20.99.1", "198.51.100.77"]:
    net = lookup(fib, destination)
    print(f"{destination:<14} uses {net} from {fib[net][0]} via {fib[net][3]}")

print()
print("The primary link fails, so its static default route is withdrawn:")
fib = build_fib([r for r in RIB if "primary" not in r[4]])
net = lookup(fib, "198.51.100.77")
print(f"198.51.100.77  uses {net} from {fib[net][0]} [{fib[net][1]}/{fib[net][2]}] via {fib[net][3]}")

FIB built from the RIB:
  0.0.0.0/0       static  [1/0] via 203.0.113.1 (primary link)
  10.20.0.0/16    static  [1/0] via 10.255.0.21 (new firewall)
  10.20.30.0/24   OSPF    [110/30] via 10.255.0.9
10.20.30.5     uses 10.20.30.0/24 from OSPF via 10.255.0.9
10.20.99.1     uses 10.20.0.0/16 from static via 10.255.0.21 (new firewall)
198.51.100.77  uses 0.0.0.0/0 from static via 203.0.113.1 (primary link)

The primary link fails, so its static default route is withdrawn:
198.51.100.77  uses 0.0.0.0/0 from static [250/0] via 198.51.100.1 (backup link, floating static)

Read the first block of the output as the router’s decision for each prefix. The two routes to 10.20.0.0/16 differ in distance, so the static route (1) beats OSPF (110). The two routes to 10.20.30.0/24 come from OSPF and RIP, and RIP’s smaller metric of 2 does not matter, because OSPF’s distance of 110 wins before any metric is compared. Both default routes are static, and the one with distance 250 is a floating static route: a backup that stays out of the FIB while the primary exists, and floats in when the primary is withdrawn, as the last line shows.

When the best routes to a prefix tie on everything, a router may keep several of them and spread traffic across their next hops. RFC 1812 allows this as load splitting (section 5.2.4.5), and it is usually called equal-cost multipath.

How routers find the longest match quickly

Scanning the whole table for every packet gives the right answer, but its cost grows with the table, and the 67 nanoseconds of the first section leave no room for it. Routers keep their prefixes in tries instead. A binary trie stores one bit of the address per level: from the root, a 0 bit leads to one child and a 1 bit to the other, and a node where a prefix ends holds that prefix’s next hop. A lookup walks the destination’s bits from the most significant one and remembers the next hop of the last route it passed. When the path runs out, the remembered route is the longest match. A lookup therefore costs at most 32 steps for IPv4 and 128 for IPv6, however many prefixes the table holds. The program below builds a table of 2,001 random prefixes and looks up 1,000 seeded destinations three ways, counting the work each way does:

# Three ways to find the longest matching prefix, counted on the same table and destinations.
# Seeded, so every run prints the same numbers; counts of steps, not timings, so any computer agrees.
import random

rng = random.Random(2026)


def random_prefix():
    length = rng.choice([8, 12, 16, 16, 20, 22, 24, 24, 24, 24])
    value = rng.getrandbits(32) & ((0xFFFFFFFF << (32 - length)) & 0xFFFFFFFF)
    return value, length


TABLE = {}
while len(TABLE) < 2000:
    TABLE[random_prefix()] = f"hop{len(TABLE) % 16}"
TABLE[(0, 0)] = "default"
PREFIXES = list(TABLE.items())


def matches(address, value, length):
    return length == 0 or (address >> (32 - length)) == (value >> (32 - length))


def scan_all(address):
    """Check every prefix and keep the longest match."""
    best, checks = None, 0
    for (value, length), hop in PREFIXES:
        checks += 1
        if matches(address, value, length) and (best is None or length > best[0]):
            best = (length, hop)
    return best[1], checks


BY_LENGTH = sorted(PREFIXES, key=lambda p: -p[0][1])


def scan_longest_first(address):
    """Check prefixes from the longest down and stop at the first match."""
    for checks, ((value, length), hop) in enumerate(BY_LENGTH, start=1):
        if matches(address, value, length):
            return hop, checks


ROOT = {"hop": None, "kids": [None, None]}
for (value, length), hop in PREFIXES:
    node = ROOT
    for i in range(length):
        bit = (value >> (31 - i)) & 1
        if node["kids"][bit] is None:
            node["kids"][bit] = {"hop": None, "kids": [None, None]}
        node = node["kids"][bit]
    node["hop"] = hop


def trie_lookup(address):
    """Walk the address bit by bit and remember the last route passed."""
    node, best, steps = ROOT, ROOT["hop"], 1
    for i in range(32):
        node = node["kids"][(address >> (31 - i)) & 1]
        if node is None:
            break
        steps += 1
        if node["hop"] is not None:
            best = node["hop"]
    return best, steps


destinations = []
for _ in range(1000):
    if rng.random() < 0.5:  # half inside a prefix of the table, half anywhere
        (value, length), _hop = rng.choice(PREFIXES)
        destinations.append(value | (rng.getrandbits(32) & ((1 << (32 - length)) - 1)))
    else:
        destinations.append(rng.getrandbits(32))

results = {"scan every prefix": [], "scan longest first": [], "binary trie": []}
agree = True
for address in destinations:
    a, b, c = scan_all(address), scan_longest_first(address), trie_lookup(address)
    agree = agree and a[0] == b[0] == c[0]
    results["scan every prefix"].append(a[1])
    results["scan longest first"].append(b[1])
    results["binary trie"].append(c[1])

print(f"{len(PREFIXES):,} prefixes, {len(destinations):,} destinations; all three agree: {agree}")
for name, counts in results.items():
    print(f"{name:<19} average {sum(counts) / len(counts):>8.1f}   worst {max(counts):>5,} steps per lookup")
defaults = sum(1 for a in destinations if trie_lookup(a)[0] == "default")
print(f"destinations that only the default route matched: {defaults}")

2,001 prefixes, 1,000 destinations; all three agree: True
scan every prefix   average   2001.0   worst 2,001 steps per lookup
scan longest first  average   1447.8   worst 2,001 steps per lookup
binary trie         average     16.6   worst    25 steps per lookup
destinations that only the default route matched: 182

All three methods give the same next hop for every destination. A full scan checks all 2,001 prefixes every time. Sorting the table from the longest prefix down and stopping at the first match only brings the average to about 1,450 checks, because many destinations match only a short prefix or the default route near the end of the list. The trie needs about 17 node visits on average and never more than 25, one more than the longest prefix in the table. Real implementations compress the trie further. Linux keeps its FIB in a level-compressed trie, which skips runs of bits where no path branches and lets one node consume several bits at once (kernel documentation).

Default gateways that survive a router failure

A host’s default route points at one gateway address. If the router behind that address fails, every packet the host sends off its own subnet is lost, and hosts do not run the routing protocols that would notice. First-hop redundancy protocols let two or more routers share one gateway address instead. In version 3 of the Virtual Router Redundancy Protocol (VRRP), specified in RFC 9568, the routers of one virtual router share a virtual IP address and a virtual MAC address, 00-00-5E-00-01 followed by the virtual router’s ID for IPv4 (RFC 9568, section 7.3). The Active Router answers for both and sends advertisements, by default every second. The router that owns the address uses priority 255, and Backup routers use 1 to 254, with 100 as the default. A Backup that hears no advertisement for the Active_Down_Interval, three advertisement intervals plus a skew time that is shorter for higher priorities, takes over (section 6.1):

# How long hosts lose their default gateway when the VRRP Active Router fails silently (RFC 9568, section 6.1).
# Times are in centiseconds, as in the RFC; the advertisement interval defaults to 100 (1 second).
ADVER_INTERVAL = 100

print("priority  skew time  takes over after")
for priority in [254, 200, 150, 100, 50, 1]:
    skew = ((256 - priority) * ADVER_INTERVAL) / 256
    down = 3 * ADVER_INTERVAL + skew
    print(f"{priority:>8}  {skew / 100:>7.2f} s  {down / 100:>10.2f} s")

print()
print("With advertisements every 0.2 s instead of 1 s, a priority-100 Backup takes over after",
      f"{(3 * 20 + ((256 - 100) * 20) / 256) / 100:.2f} s.")

priority  skew time  takes over after
     254     0.01 s        3.01 s
     200     0.22 s        3.22 s
     150     0.41 s        3.41 s
     100     0.61 s        3.61 s
      50     0.80 s        3.80 s
       1     1.00 s        4.00 s

With advertisements every 0.2 s instead of 1 s, a priority-100 Backup takes over after 0.72 s.

With the default timers, a Backup of priority 100 takes over about 3.6 seconds after the Active Router falls silent, and the Backup with the highest priority always times out first, so two Backups do not take over at once. A shorter advertisement interval brings the gap under a second, at the cost of more advertisements on the link. The hosts notice nothing either way: their default route still names the same virtual address.

IPv6 follows the same rule

Nothing in longest prefix match depends on the width of the address. IPv6 prefixes run up to 128 bits, ::/0 is the default route and a /128 is a host route, so a binary trie for IPv6 is 128 levels deep instead of 32. The exercise uses addresses from 2001:db8::/32, the prefix reserved for documentation (RFC 3849), and asks you to handle both versions in one class, which also means that an IPv4 address must never match an IPv6 route.

Exercise

import ipaddress


class Trie:
    """A forwarding table that answers lookups by longest prefix match (IPv4 and IPv6)."""

    def __init__(self):
        # Replace this line with your code.
        pass

    def insert(self, prefix, next_hop):
        """Store next_hop for prefix, such as "10.20.0.0/16"; replace it if the prefix is already there."""
        # Replace this line with your code.
        pass

    def lookup(self, address):
        """The next hop of the longest stored prefix that contains address, or None."""
        # Replace this line with your code.
        return None

from lpm import Trie


def build(routes):
    t = Trie()
    for prefix, hop in routes:
        t.insert(prefix, hop)
    return t


def test_default_route_matches_everything():
    """a /0 route matches any address of its version"""
    t = build([("0.0.0.0/0", "isp")])
    assert t.lookup("198.51.100.1") == "isp"
    assert t.lookup("10.1.2.3") == "isp"


def test_longest_prefix_wins():
    """the most specific containing prefix wins, whatever the insertion order"""
    t = build([("10.20.30.0/24", "lab"), ("0.0.0.0/0", "isp"), ("10.0.0.0/8", "core"), ("10.20.0.0/16", "campus")])
    assert t.lookup("10.20.30.5") == "lab"
    assert t.lookup("10.20.99.1") == "campus"
    assert t.lookup("10.99.0.1") == "core"
    assert t.lookup("198.51.100.1") == "isp"


def test_no_route_gives_none():
    """without a default route, an address outside every prefix has no route"""
    t = build([("10.0.0.0/8", "core"), ("192.168.0.0/16", "office")])
    assert t.lookup("11.0.0.1") is None
    assert t.lookup("192.169.0.1") is None
    assert t.lookup("192.168.255.255") == "office"


def test_host_route_and_neighbours():
    """a /32 matches one address only; its neighbours fall back to shorter prefixes"""
    t = build([("192.0.2.0/24", "net"), ("192.0.2.7/32", "monitor")])
    assert t.lookup("192.0.2.7") == "monitor"
    assert t.lookup("192.0.2.6") == "net"
    assert t.lookup("192.0.2.8") == "net"


def test_ipv6_routes():
    """the same rule for IPv6, and the versions never mix"""
    t = build([("::/0", "isp6"), ("2001:db8::/32", "site"), ("2001:db8:0:10::/64", "lab"), ("10.0.0.0/8", "core")])
    assert t.lookup("2001:db8:0:10::42") == "lab"
    assert t.lookup("2001:db8:ffff::1") == "site"
    assert t.lookup("2001:4860::8888") == "isp6"
    assert t.lookup("10.0.0.1") == "core"
    assert build([("::/0", "isp6")]).lookup("10.0.0.1") is None


def test_insert_replaces_next_hop():
    """inserting the same prefix again replaces its next hop"""
    t = build([("10.0.0.0/8", "old"), ("10.0.0.0/8", "new")])
    assert t.lookup("10.1.1.1") == "new"

Check yourself

Interview questions

What is the difference between a router’s RIB and its FIB?

The routing information base (RIB) holds every route the router has learned: connected subnets, static routes and everything its routing protocols received, including several routes to the same prefix. The forwarding information base (FIB) holds only the routes in use, one best route per prefix or a set of equal-cost ones, with the outgoing interface and next hop resolved, in a structure built for fast lookups. Routing protocols and operators change the RIB; the data plane reads only the FIB, once per packet, by longest prefix match.

A router holds 10.0.0.0/8 from OSPF and 10.1.0.0/16 as a static route. Which one forwards a packet to 10.1.5.9?

The static 10.1.0.0/16, because it is the longer of the two prefixes that contain 10.1.5.9. Administrative distance plays no part, since the two routes have different prefixes. It would matter only if OSPF also offered 10.1.0.0/16, and then the static route (distance 1) would win over OSPF (110) as well. A packet to 10.2.0.1 matches only the /8 and follows OSPF.

Key takeaways

• The control plane fills the RIB from connected, static and dynamic routes and installs one best route per prefix in the FIB; the data plane looks up every packet in the FIB.
• Longest prefix match: of all prefixes that contain the destination, the one with the most bits wins. The default route, 0.0.0.0/0 or ::/0, matches everything and wins only when nothing else matches.
• For the same prefix, the administrative distance (a local, vendor-defined ranking of sources) decides first, then the metric. Distance never overrides a longer prefix.
• A floating static route is a backup with a high distance; routes that tie on everything can share the traffic.
• A trie makes a lookup cost at most one step per address bit, 32 for IPv4 and 128 for IPv6, whatever the size of the table.
• VRRP gives hosts a virtual default gateway that a Backup router takes over, after about 3.6 seconds with the default timers.