C++: forwarding with longest-prefix match

Pick the most specific route that matches a destination address, as a router does.

C++

#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

struct Route {
  std::uint32_t network;
  int prefix;
  std::string next_hop;
};

std::uint32_t ip(int a, int b, int c, int d) {
  return (static_cast<std::uint32_t>(a) << 24) | (b << 16) | (c << 8) | d;
}

std::string lookup(const std::vector<Route>& table, std::uint32_t dest) {
  int best = -1;
  std::string hop = "drop";
  for (const Route& r : table) {
    std::uint32_t mask = r.prefix == 0 ? 0 : 0xFFFFFFFFu << (32 - r.prefix);
    if ((dest & mask) == r.network && r.prefix > best) {
      best = r.prefix;
      hop = r.next_hop;
    }
  }
  return hop;
}

int main() {
  std::vector<Route> table = {
      {ip(10, 0, 0, 0), 8, "A"},
      {ip(10, 1, 0, 0), 16, "B"},
      {ip(10, 1, 2, 0), 24, "C"},
      {ip(0, 0, 0, 0), 0, "default"},
  };
  std::cout << "10.1.2.9 -> " << lookup(table, ip(10, 1, 2, 9)) << "\n";
  std::cout << "10.1.9.9 -> " << lookup(table, ip(10, 1, 9, 9)) << "\n";
  std::cout << "10.9.9.9 -> " << lookup(table, ip(10, 9, 9, 9)) << "\n";
  std::cout << "8.8.8.8  -> " << lookup(table, ip(8, 8, 8, 8)) << "\n";
}

Output

10.1.2.9 -> C
10.1.9.9 -> B
10.9.9.9 -> A
8.8.8.8  -> default

Explanation

A router holds a forwarding table of prefixes, each written as an address and a prefix length such as 10.1.0.0/16. An address matches a prefix if its first prefix-length bits are equal. Several prefixes can match one address, and the router must use the one with the longest prefix, which is the most specific.

A default route, 0.0.0.0/0, matches everything with a prefix length of zero, so it is used only when nothing else matches. The program builds a mask from the prefix length, compares the masked address with the stored network, and keeps the longest match.

Explore the dry run

Guided walkthroughReady

1#include <cstdint>

2#include <iostream>

3#include <string>

4#include <vector>

6struct Route {

7 std::uint32_t network;

8 int prefix;

9 std::string next_hop;

10};

12std::uint32_t ip(int a, int b, int c, int d) {

13 return (static_cast<std::uint32_t>(a) << 24) | (b << 16) | (c << 8) | d;

14}

16std::string lookup(const std::vector<Route>& table, std::uint32_t dest) {

17 int best = -1;

18 std::string hop = "drop";

19 for (const Route& r : table) {

20 std::uint32_t mask = r.prefix == 0 ? 0 : 0xFFFFFFFFu << (32 - r.prefix);

21 if ((dest & mask) == r.network && r.prefix > best) {

22 best = r.prefix;

23 hop = r.next_hop;

24 }

25 }

26 return hop;

27}

29int main() {

30 std::vector<Route> table = {

31 {ip(10, 0, 0, 0), 8, "A"},

32 {ip(10, 1, 0, 0), 16, "B"},

33 {ip(10, 1, 2, 0), 24, "C"},

34 {ip(0, 0, 0, 0), 0, "default"},

35 };

36 std::cout << "10.1.2.9 -> " << lookup(table, ip(10, 1, 2, 9)) << "\n";

37 std::cout << "10.1.9.9 -> " << lookup(table, ip(10, 1, 9, 9)) << "\n";

38 std::cout << "10.9.9.9 -> " << lookup(table, ip(10, 9, 9, 9)) << "\n";

39 std::cout << "8.8.8.8 -> " << lookup(table, ip(8, 8, 8, 8)) << "\n";

40}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
A prefix of length p keeps the top p bits. Length 0 is handled separately because shifting by 32 is undefined.	`/24 → 255.255.255.0`	—
The route matches if the masked address equals its network, and it wins if it is more specific than the best so far.	`/24 → 255.255.255.0`	—
Three routes match: /8, /16, and /24. The /24 is the longest, so the next hop is C.	`/24 → 255.255.255.0`	10.1.2.9 -> C
Only the default route matches.	`/24 → 255.255.255.0`	10.1.2.9 -> C 10.1.9.9 -> B 10.9.9.9 -> A 8.8.8.8 -> default

Cost and common mistakes

O(n) per lookup for n routes with a linear scan.

Shifting a 32-bit value by 32 or more is undefined behaviour in C++, so the zero-length prefix needs its own case.
Scanning the whole table is O(n). Real routers use tries or TCAM hardware to match in a few steps.

Try it yourself

Which hop is chosen for 10.1.2.200 if the /24 route is removed?

Reveal answer and reasoning

B, because the next most specific match is 10.1.0.0/16.

C++: forwarding with longest-prefix match

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading