Skip to Content

Interview Fundies: Longest Prefix Match

Posted on 3 mins read
Next Year’s Gartner MQ Leader in Enterprise Network Security

Next Year’s Gartner MQ Leader in Enterprise Network Security

Next Year’s Gartner MQ Leader in Enterprise Network Security

Given

Given the following simplified IPv4 route table:

Network          Netmask           Gateway
------------     -------------     -----------
0.0.0.0          0.0.0.0           172.16.1.10
10.0.0.0         255.0.0.0         172.16.1.20
10.0.0.0         255.255.255.0     172.16.1.30
10.128.0.0       255.252.0.0       172.16.1.40
10.128.0.0       255.255.0.0       172.16.1.50
10.128.132.0     255.255.254.0     172.16.1.60

Question

  1. To reach 8.8.8.8 what gateway will be chosen?
  2. To reach 10.128.0.10 what gateway will be chosen?
  3. To reach 10.128.134.52 what gateway will be chosen?
  4. What is the longest prefix in the table?
  5. What is the shortest prefix in the table?

Regularly, I devise a similar example on the whiteboard during an interview to assess routing fundamentals. More than one “credentialed” Network Engineer has answered incorrectly. Even worse, they answer correctly, but cannot answer the obligatory next question:

Why?

Routing tables are not evaluated top-down like an access control list. Instead, the table is evaluated and the longest prefix match is the winner.

Practical routing in hardware or as implemented in software contains more layers than described in this simple example. For example, our simple example does not differentiate between a routing table (one per routing protocol) and forwarding table (a separate table composed of the best routes across all route tables includes longest prefix match, administrative distance, and other parameters). The example is simply probing for fundamental understanding of longest prefix match which requires fundamental understanding of variable-length subnet masking (VLSM). If a candidate fails at longest prefix match, additional routing questioning is often moot.

Explain

Q1

  1. To reach 8.8.8.8 what gateway will be chosen?

172.16.1.10

The 8.8.8.8 destination only falls within one (1) of the prefixes: the default route 0.0.0.0/0 with next-hop gateway 172.16.1.10.

Q2

  1. To reach 10.128.0.10 what gateway will be chosen?

172.16.1.50

The 10.128.0.10 destination falls within (“matches”) four (4) of the prefixes: 0.0.0.0/0, 10.0.0.0/8, 10.128.0.0/14, and 10.128.0.0/16.

The longest matching prefix is 10.128.0.0/16 with next-hop gateway 172.16.1.50.

Q3

  1. To reach 10.128.134.52 what gateway will be chosen?

172.16.1.50

The 10.128.134.52 destination falls within (“matches”) four (4) of the prefixes: 0.0.0.0/0, 10.0.0.0/8, 10.128.0.0/14, and 10.128.0.0/16.

The longest matching prefix is 10.128.0.0/16 with next-hop gateway 172.16.1.50.

Note: 10.128.134.52 destination does not match the 10.128.132.0/23 prefix.

Q4

  1. What is the longest prefix in the table?

10.0.0.0/24

10.0.0.0/24 is the longest prefix in the table given its 24 network bits. The second longest prefix in the table is 10.128.132.0/23 given its 23 network bits.

Q5

  1. What is the shortest prefix in the table?

0.0.0.0/0

0.0.0.0/0 is the shortest prefix in the table given its 0 network bits. 0.0.0.0/0 prefix always represents the default route and the next-hop gateway for a default route (172.16.1.10 in our example) is also called a gateway of last resort.

The second shortest prefix in the table is 10.0.0.0/8 with its 8 network bits.