To find a matched entry in the route table, a bitwise AND will be applied to the destination IP and the netmask in the route table. I wonder if the bitwise AND will ALSO be applied to the "Network Destination" of current entry in the route table and the netmask, then the two AND results are compared; or, there is only one AND(the destination IP and the netmask) and the result is directly compared to the "Network Destination" in the route table?
3
- 1Why applying it to the entry every time, if you can apply it once when the entry is created and store already applied value? That said, explanations are focused on the semantics of the routing, not on the efficient implementation. In practice, big routers have ~1000000 entries in each of their routing tables, so direct table search is a no-go, some form of O(1) search has to be used, perhaps implemented using hash functions or other kind of indexing. But the semantics of the process, e.g. which route will be eventually selected, stays the same, and it's what you see in an explanation.Nikita Kipriyanov– Nikita Kipriyanov2024-12-06 06:55:21 +00:00Commented Dec 6, 2024 at 6:55
- 1@NikitaKipriyanov I'm really interested in learning more about how you'd look up a route in a hash table, assuming the key is the subnet and mask, because I don't know how you'd work out that key given only a destination IP. My intuition would be that you'd just have to do a slow search and then cache that resultRob M– Rob M2024-12-06 11:07:07 +00:00Commented Dec 6, 2024 at 11:07
- 3@RobM More commonly I believe a binary tree or a trie is used (don't ask me about the difference between the two), where the lookup is incremental bit-by-bit or nibble-by-nibble until a route entry is found at any depth. For example see vincent.bernat.ch/en/blog/2017-ipv4-route-lookup-linux and vincent.bernat.ch/en/blog/2017-ipv6-route-lookup-linuxgrawity– grawity2024-12-06 12:16:31 +00:00Commented Dec 6, 2024 at 12:16
Add a comment |
1 Answer
I wonder if the bitwise AND will ALSO be applied to the "Network Destination" of current entry in the route table and the netmask,
Yes, but that's usually done when the route is added, not every time it's used. Some systems will do the 'AND' and store the canonical network address as destination, but I think it's more common to return an error when someone attempts to add such a route – with the message "destination has host bits set" or similar.
Either way, the result is that the routing table is guaranteed to only have entries where the host bits are already all-0s, thus the extra AND on every lookup is unnecessary.
Note that most software-based routing implementations don't actually do a linear lookup with each entry being ANDed. Instead, they use a structure such as a trie where lookup is done incrementally, bit-by-bit, and only the final result is verified in the regular way.
("Hardware" routing meanwhile often uses special TCAM memory which – assuming I understand it correctly – implements a bit-masked comparison operation in hardware, so you could say that it does 'AND' both the address and the route destination... although I think it would be more accurate to say that the host bits aren't compared in the first place, rather than being masked out before comparison.)
