1

Let's say I have an ipv4 destination address - 63.168.52.12

In binary format the address: 00111111.10101000.00110100.00001100

The default route in binary is 00000000.00000000.00000000.00000000

I am trying to understand how the default route matches all ip addresses. What does it mean for subnet mask to be zero? The first two bits match and the difference is at third bit. Is the IP checked bit by bit against the default route ip and looks for match? I read in another question that all IPv4 networks are subnets of the 0.0.0.0/0 network. I don't quite understand that statement.

2 Answers 2

3

The relevant part of the default route is the /0 prefix length, not really the 0.0.0.0 address part. Generally, /0 means "match at least the first zero bits of an address", making it match always.

Technically, the /0 length is expanded to the subnet mask 0.0.0.0 (or for comparison /16 to 255.255.0.0, /17 to 255.255.128.0 etc.). That subnet mask is used in a bitwise AND operation (masking) with the address to be matched. Since all bits become zero the result is always 0.0.0.0.

In operation, the routing table (FIB) entries are queried in the order of longest to shortest prefix:

if (destinationaddress AND entry.mask) == entry.prefix then use entry.gateway

Since /0 is the shortest possible prefix it's always checked last and matches any address.

2
  • So when matching, the subnet masks are compared and not the IP addresses ?
    – Cruise5
    Jan 18, 2022 at 16:51
  • The subnet mask is used to mask (bitwise AND operation) the destination address which is then compared to the route prefix, as described above.
    – Zac67
    Jan 18, 2022 at 18:04
2

The best way to think about the comparison is IMHO to have three possible values for a bit: zero, one, and "don't care". Don't care means that the bit matches both zero and one, it does not matter to a match. Let's use "*" for don't care.

Now, with "don't care" bits, you represent addresses/masks as bits in the masked parts, and don't care in the rest. E.g., a prefix 63.168.52.0/24 becomes 00111111.10101000.00110100.********, where the ******** matches any combination of 8 bits. Obviously, default route 0.0.0.0/0 becomes 32 don't care bits (32 stars) and matches any combination of bits.

IP table should implement longest prefix match, i.e., out of all matches (with don't care bits there will be more than one match, default route matches them all), the match with the least number of don't care bits should be selected. So, if the route matches both 63.168.52.* and ..., the former one is selected, because it has less "*" in it (aka longer prefix).

This of course raises the question on how to implement this. No, it is not just a comparison search. There is a special hardware, called TCAM (ternary content addressable memory). Content-adressable memory allows addressing memory based on content (think of it like searching in a table, based on content of the cell instead or row index). Ternary one, allows said content (cells) to be 'don't care bits' (match both one and zero). In software one have specialized data structures. One common datastructure is called trie, which is a tree like structure which can be used to do longest prefix match on variable length prefixes.

1
  • 1
    Usually, the routing table (FIB) cointains entries in the order longest-prefix/best-preference to shortest-prefix/worst-preference. That way, the topmost match returned by TCAM is the best match. You'd do the same thing in software but running a line-by-line match in a loop instead of the single-step TCAM lookup.
    – Zac67
    Jan 18, 2022 at 9:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.