IP longest prefix match with a binary trie

Why this matters

A router is a device that passes network packets toward their destinations. Each packet carries a destination address. For IPv4, the address is four numbers from 0 to 255 separated by dots, such as 10.1.2.7.

The router keeps a routing table, which is a list of rules. A rule says: for addresses that start with these bits, send the packet out through this next hop, such as the port eth1.

More than one rule can match one address. A table might say 10.0.0.0/8 goes to eth1, and 10.1.2.0/24 goes to eth3. The address 10.1.2.7 matches both. The router uses the more specific rule, the one with the longer matching prefix. This choice is called longest prefix match.

The router makes this lookup for every packet, so it must be fast. Checking every rule for every packet gets slow when the table is large. A binary trie answers the question in at most 32 steps, however many rules the table holds.

Words used in this lesson

Bit: a single digit, either 0 or 1.
IPv4 address: a 32-bit number, written as four decimal numbers from 0 to 255 separated by dots. Each of those four numbers is an octet, a group of 8 bits.
Prefix: the leading bits of an address. The rule 10.0.0.0/8 uses the first 8 bits of 10.0.0.0.
Prefix length: the number after the slash. /8 means the first 8 bits matter, and /24 means the first 24 bits matter.
Next hop: where to send the packet next, such as eth1.
Binary trie: a tree where each node has up to two children, one for a 0 bit and one for a 1 bit. Walking down from the root reads one bit per step.
Optional: a C++ wrapper that holds either a value or nothing. The code uses it for "this node has a rule" and "no rule matched".

Addresses are bits

Each octet has 8 bits. The number 10 is 00001010 in binary, written with 8 digits. The number 1 is 00000001, the number 2 is 00000010, and the number 7 is 00000111. So the address 10.1.2.7 is these 32 bits, with a space after each octet to make it easier to read.

00001010 00000001 00000010 00000111

Now look at the rules. The rule 10.0.0.0/8 has a prefix of 8 bits, which is 00001010. Any address that starts with those 8 bits matches. The address 10.1.2.7 matches, and so does 10.200.0.1.

The rule 10.1.0.0/16 has a prefix of 16 bits, which is 00001010 00000001. Only addresses that start with 10 and then 1 match. 10.1.2.7 matches it. 10.9.9.9 does not.

A rule with length 0, written 0.0.0.0/0, has no bits to compare, so every address matches it. This is the default route. It is used when no other rule matches.

The simple method: check every rule

Write the simple version first, so you know what the answer should be. For each rule, check whether the address starts with that rule's bits. Among the rules that match, keep the one with the longest prefix.

Take the address 10.1.2.7 and these three rules: 10.0.0.0/8 to eth1, 10.1.0.0/16 to eth2, and 10.1.2.0/24 to eth3. All three match. The longest prefix is 24 bits, so the answer is eth3.

This works. Its cost is that every packet checks every rule. A table with 100,000 rules means 100,000 checks for each packet.

Building a binary trie

A binary trie answers the same question by reading bits one at a time. The root is the top of the tree. Its two children are for the first bit, 0 or 1. Each step down reads one more bit. So a path of 8 steps from the root spells out an 8-bit prefix.

Each rule is stored at the node that its prefix leads to. A rule with a 24-bit prefix is stored at the node 24 steps below the root.

The table below shows the bit path for each rule in the example.

Rule           Bits on the path from the root                          Next hop stored at
10.0.0.0/8     00001010                                                 node after 8 bits: eth1
10.1.0.0/16    00001010 00000001                                        node after 16 bits: eth2
10.1.2.0/24    00001010 00000001 00000010                               node after 24 bits: eth3
0.0.0.0/0      (no bits)                                                the root: wan

Rules share their first steps. The rules 10.0.0.0/8 and 10.1.0.0/16 both start with the path 00001010, so the trie uses one set of nodes for those 8 bits. The rule 10.1.0.0/16 then adds 8 more nodes for the bits 00000001. Inserting a rule creates only the nodes that are missing.

Insertion has one more detail. If a rule has the same prefix as an earlier rule, the new next hop replaces the old one. The trie keeps one next hop per prefix.

Looking up an address

To look up an address, start at the root and read its 32 bits from left to right. At each step, follow the child for the current bit. Keep a note of the last node you passed that holds a next hop. When there is no child for the next bit, stop. The saved next hop is the answer.

Why the last saved next hop is the right one: each node you pass is deeper than the one before it, so it matches more bits. The last saved one has the longest matching prefix.

Worked example: 10.1.2.7

Use the four rules from the table, with the default route at the root.

Start at the root. The root holds wan, so save wan.
Read bits 1 to 8, which are 00001010. The node after 8 bits holds eth1. Save eth1.
Read bits 9 to 16, which are 00000001. The node after 16 bits holds eth2. Save eth2.
Read bits 17 to 24, which are 00000010. The node after 24 bits holds eth3. Save eth3.
Read bit 25. The node after 24 bits has no child, because no rule is longer than 24 bits. Stop.

The answer is eth3.

Worked example: 10.9.9.9

Start at the root. Save wan.
Read 00001010. The node after 8 bits holds eth1. Save eth1.
Read the next 8 bits, which are 00001001. The path so far follows 00000001 for the rule 10.1.0.0/16. The bits 0000 match, but the fifth bit is 1 where the path has 0. There is no child for that bit, so stop.

The answer is eth1, which is the longest rule that matched 10.9.9.9.

The code

The program reads the routing table first, then the addresses to look up. Each address is turned into a 32-bit number by parseIPv4. Then lookup walks its bits.

The input begins with a count of rules. Each rule line has a prefix in the form address/length, then a next hop name. After the rules comes a count of addresses, then one address per line.

4
10.0.0.0/8 eth1
10.1.0.0/16 eth2
10.1.2.0/24 eth3
0.0.0.0/0 wan
4
10.1.2.7
10.1.9.9
10.9.9.9
192.168.1.1

C++ · editable

#include <cstdint>
#include <iostream>
#include <memory>
#include <optional>
#include <string>
#include <vector>
using namespace std;

// Returns bit i of an address, where bit 0 is the leftmost (most significant) bit.
int bitAt(uint32_t value, int i) {
    return (value >> (31 - i)) & 1;
}

// Turns "10.1.2.7" into one 32-bit number.
uint32_t parseIPv4(const string& text) {
    uint32_t value = 0;
    size_t start = 0;
    for (int part = 0; part < 4; ++part) {
        size_t dot = text.find('.', start);
        size_t end = (part == 3) ? text.size() : dot;
        if (end == string::npos) throw invalid_argument("need four octets: " + text);
        int octet = stoi(text.substr(start, end - start));
        if (octet < 0 || octet > 255) throw invalid_argument("octet out of range: " + text);
        value = (value << 8) | uint32_t(octet);
        start = end + 1;
    }
    return value;
}

class RouteTable {
public:
    void addRoute(uint32_t prefix, int length, const string& hop) {
        Node* cur = &root_;
        for (int i = 0; i < length; ++i) {
            auto& next = cur->child[bitAt(prefix, i)];
            if (!next) next = make_unique<Node>();
            cur = next.get();
        }
        cur->hop = hop;
    }

optional<string> lookup(uint32_t address) const {
        const Node* cur = &root_;
        optional<string> best = cur->hop;
        for (int i = 0; i < 32; ++i) {
            cur = cur->child[bitAt(address, i)].get();
            if (cur == nullptr) break;
            if (cur->hop) best = cur->hop;
        }
        return best;
    }

private:
    struct Node {
        unique_ptr<Node> child[2];
        optional<string> hop;
    };
    Node root_;
};

int main() {
    RouteTable table;

int routeCount;
    cin >> routeCount;
    for (int k = 0; k < routeCount; ++k) {
        string cidr, hop;
        cin >> cidr >> hop;
        size_t slash = cidr.find('/');
        if (slash == string::npos) throw invalid_argument("missing / in " + cidr);
        uint32_t prefix = parseIPv4(cidr.substr(0, slash));
        int length = stoi(cidr.substr(slash + 1));
        table.addRoute(prefix, length, hop);
    }

int queryCount;
    cin >> queryCount;
    for (int k = 0; k < queryCount; ++k) {
        string ip;
        cin >> ip;
        optional<string> hop = table.lookup(parseIPv4(ip));
        cout << ip << " -> " << hop.value_or("no route") << "\n";
    }
}

Output:

10.1.2.7 -> eth3
10.1.9.9 -> eth2
10.9.9.9 -> eth1
192.168.1.1 -> wan

The code has four parts.

bitAt reads one bit. Bit 0 is the leftmost bit, which is the highest bit of the 32-bit number. So bit i is found by shifting right by 31 - i and keeping the last bit.
parseIPv4 splits the text at the dots and builds the number. Each octet is shifted into place with value << 8. The stoi function turns text into an int, and it throws an error when the text is not a number.
addRoute walks or creates nodes along the prefix bits, then stores the next hop at the node reached after length bits.
lookup walks the 32 bits of the address. It starts with the default route saved at the root, and it updates the saved next hop each time it passes a node that holds one. It stops when there is no child for the next bit.

More examples

Example 2: a rule inside a rule

This table has a default route, a /16 rule and a /25 rule. The /25 rule is inside the /16 rule.

3
0.0.0.0/0 D
192.168.0.0/16 H
192.168.1.128/25 S
4
192.168.1.200
192.168.1.5
192.168.200.1
8.8.8.8

The /25 rule covers the addresses from 192.168.1.128 to 192.168.1.255. The first 25 bits of 192.168.1.128 are 192.168.1 followed by a bit 1. So 192.168.1.200 matches the /25 rule and gets S. The address 192.168.1.5 does not match /25, because its last octet starts with a 0 bit. It falls back to the /16 rule and gets H.

Here is the output from running the program.

192.168.1.200 -> S
192.168.1.5 -> H
192.168.200.1 -> H
8.8.8.8 -> D

The address 8.8.8.8 matches no rule except the default route, so it gets D.

Example 3: no default route and a host rule

A rule with length 32 matches exactly one address. It is called a host route. This example has a host rule inside a /24 rule, and no default route.

3
10.0.0.0/8 A
10.1.2.0/24 C
10.1.2.7/32 E
2
10.1.2.7
10.1.2.8

The address 10.1.2.7 matches all three rules, and the /32 rule is the longest, so the answer is E. The address 10.1.2.8 does not match the /32 rule, so it gets C. The output is the following.

10.1.2.7 -> E
10.1.2.8 -> C

Now remove the default route and the match fails. Here is a table with only two rules, and three addresses.

2
10.0.0.0/8 eth1
192.168.0.0/16 eth2
3
10.5.5.5
172.16.0.1
192.168.9.1

The output is the following. The address 172.16.0.1 matches neither rule, and there is no default route, so it prints no route.

10.5.5.5 -> eth1
172.16.0.1 -> no route
192.168.9.1 -> eth2

Why the walk is fast

The walk reads at most 32 bits, so a lookup takes at most 32 steps. The number of rules does not change that limit. A table with 10 rules and a table with 100,000 rules both need at most 32 steps per address.

The cost is memory. Each rule can add up to 32 nodes, and each node holds two child pointers and a next hop. Rules that share their first bits share nodes, so a table of related prefixes uses less memory than the worst case. Each step also jumps to another place in memory, which is slower than reading a plain array. Routing software often uses more compact versions of this tree, which merge chains of nodes that have only one child. This lesson uses the plain version so the logic is easy to follow.

Common mistakes

Reading bits from the wrong end. The bit number must count from the left, which is the highest bit. If bitAt shifts by i instead of 31 - i, the walk reads the last bit first and follows the wrong path. With the same input as the first example, this version prints wan for every address.

10.1.2.7 -> wan
10.1.9.9 -> wan
10.9.9.9 -> wan
192.168.1.1 -> wan

Returning the first rule found on the walk. The walk must keep going to find the longest match. If lookup returns as soon as it sees a next hop, it returns the shortest match. For 10.1.2.7, the output becomes eth1, which is the /8 rule, instead of eth3.

Keeping only the node reached last. The walk must save the last next hop it passed, not the last node it reached. If best is set to the node's hop every time, even when that hop is empty, the saved answer is lost. The output then shows no route for addresses that match a rule.

10.1.2.7 -> eth3
10.1.9.9 -> no route
10.9.9.9 -> no route
192.168.1.1 -> wan

Building a mask with a shift of 32. A common way to test a prefix is to build a mask, such as ~0u << (32 - length). When length is 0, the shift count is 32, which is as wide as the number itself. Shifting by the full width of the type is undefined behaviour in C++. The code below runs with a length of 0 at run time, and on this machine the result was all ones, which matches every address by mistake.

#include <cstdint>
#include <cstdio>
int main(int argc, char**) {
    volatile int length = argc - 1;   // 0 when run with no arguments
    uint32_t mask = ~0u << (32 - length);
    std::printf("length %d mask %08x\n", (int)length, mask);
}

Output from g++ 15 on this machine:

length 0 mask ffffffff

The walk in this lesson never builds a mask, so it does not have this problem. If you write a mask version, handle length 0 as a special case that gives an all-zero mask. When the shift count is a constant, g++ warns about it at compile time, as in this message.

shift2.cpp:3:25: warning: left shift count >= width of type [-Wshift-count-overflow]
    3 |     uint32_t mask = ~0u << 32;
      |                     ~~~~^~~~~

Forgetting an include. The code uses optional, which lives in the <optional> header. Without that include, g++ reports an error like the following.

noinc.cpp: In function 'int main()':
noinc.cpp:4:10: error: 'optional' is not a member of 'std'
    4 |     std::optional<std::string> hop = std::string("eth1");
      |          ^~~~~~~~

The error message names the missing header. Add #include <optional> at the top of the file.

Bad input. The program does not check the text it reads, so bad input ends the program. A routing entry with a letter in it stops the run at the first bad number.

terminate called after throwing an instance of 'std::invalid_argument'
  what():  stoi

An octet above 255 gives a clearer message from the check in parseIPv4.

terminate called after throwing an instance of 'std::invalid_argument'
  what():  octet out of range: 10.0.0.300

A real program would catch these errors, print the bad line, and keep going. This lesson lets them end the run so the problem is easy to see.

Practice

Exercise 1. The table has 10.0.0.0/8 to A and 10.0.0.0/16 to B. What does the program print for 10.0.5.1 and for 10.200.0.1?

Show the answer

The output is 10.0.5.1 -> B and 10.200.0.1 -> A. The address 10.0.5.1 matches both rules, and the /16 rule is longer. The address 10.200.0.1 matches only the /8 rule, because its second octet is 200, not 0.

Exercise 2. The table has only 10.0.0.0/8 to A. What does the program print for 8.8.8.8?

Show the answer

The output is 8.8.8.8 -> no route. The address does not start with 10, and the table has no default route, so no rule matches.

Exercise 3. The table has 0.0.0.0/0 to D, 192.168.0.0/16 to H and 192.168.1.128/25 to S. Predict the output for 192.168.1.200, 192.168.1.5, 192.168.200.1 and 8.8.8.8.

Show the answer

The output is S, H, H and D, in that order. The /25 rule covers the last octet values from 128 to 255 inside 192.168.1. The other three addresses fall back to the /16 rule or the default route.

Exercise 4. Start with the table from Example 3, which has 10.0.0.0/8 to A, 10.1.2.0/24 to C and 10.1.2.7/32 to E. Add a new rule 10.1.2.0/24 to F. What does the program print for 10.1.2.8?

Show the answer

The output is F. The new rule has the same prefix as the rule that gave C, so it replaces the stored next hop at that node. The address 10.1.2.8 matches the /24 rule, and the /32 rule does not match it.

Exercise 5. Why does the walk keep going after it finds a match, instead of returning the first match it sees?

Show the answer

Each deeper node matches more bits of the address, so a longer rule can appear further down the path. If the walk stopped at the first match, it would return a shorter prefix. For 10.1.2.7, stopping at the /8 rule would give eth1, which is less specific than the /24 rule that gives eth3.

Summary

A routing table is a set of prefix rules. The router picks the rule with the longest matching prefix.
A binary trie stores each prefix as a path of bits, with the next hop at the node reached after the prefix length.
A lookup reads the 32 bits of the address, saves each next hop it passes, and returns the last one saved.
A lookup takes at most 32 steps, however many rules the table holds.
Common mistakes are reading bits from the wrong end, stopping at the first match, and shifting by the full width of an integer.

IP longest prefix match with a binary trie

Why this matters

Words used in this lesson

Addresses are bits

The simple method: check every rule

Building a binary trie

Looking up an address

Worked example: 10.1.2.7

Worked example: 10.9.9.9

The code

More examples

Example 2: a rule inside a rule

Example 3: no default route and a host rule

Why the walk is fast

Common mistakes

Practice

Summary

Stuck? Ask the tutor