How are IP address compared to the default 0.0.0.0/0 or ::/0 on binary level?

Question

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.

Answer 1

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.

Answer 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.