4 ms·

lookup complexity is a very real cost factor for routing equipment and it's increasing faster (because interface speeds are increasing and prefixes are getting

lookup complexity is a very real cost factor for routing equipment and it's increasing faster (because interface speeds are increasing and prefixes are getting smaller) than hardware capabilities are . so no, we can't make every router cache every host id.

JoeAltmaier 6y ago
Sure we can. Especially UUIDS. They have a normal distribution of values (bits are random) so an associative cache would match entries faster than current devices can match highly-repetitive prefixes. This is an example of what the IPV6 folks suffered from. They could only see the issues of previous implementations, and took an incremental step along those solution axes. Instead of considering future trends (cheaper memory/processing power) and "skating toward the puck". Instead they followed the puck, and ended up well behind.
- corty 6y ago
  A cache with a few billion devices in it will be too large, and as soon as your cache may be large enough you will have even more devices. Also, for routing an address hierarchy is nice because of the O(log n) properties the address tree gives you. UUIDs do not do that, but subnets do. For the endpoints and smaller routers near the edges it is even more advantageous, those only need to know a few local prefixes, the rest goes to the next gateway. With UUIDs, every devices needs to learn all the addresses behind it, quite an impossible task, even if the lookup were fast and small enough for its cache.
  - JoeAltmaier 6y ago
    Again, for core routers, not at all. The UUID is random; it has the same order of lookup or better; endpoints need only the local routing info in the same way. Caches need only hold active routes, which is orders of magnitude smaller. The idea that its 'impossible' is 20 year old thinking. That's my whole point. We've wandered into a disappointing, underpowered solution that's not gaining traction. While real future-proof solutions exist right in front of us.
    - cesarb 6y ago
      > Caches need only hold active routes, which is orders of magnitude smaller. What do you do when there's no active route? If a router receives a packet from 192.0.2.1 to 198.51.100.2, but the router has never received a packet from 198.51.100.2, how does it know to which of its neighbors it should send the packet?
      - JoeAltmaier 6y ago
        We resolve arbitrary names (e.g. DNS) now, so clearly the solution is possible.
        cesarb 6y ago
        We resolve arbitrary names with DNS to a global identifier (an IP address), but for routing, what you need is a local identifier (which neighbor router to send the packet to), which means every router or set of routers would need its own database, and each database would need to know about every host in the world. This is exactly what we have nowadays with BGP, only with networks instead of hosts: every core router or set of core routers has a database which knows about every network in the world, and tells which neighbor AS to send the packet to.
        corty 6y ago
        Also, DNS caches are just locally used small subsets. Global lookups are again hierarchical, thats why it is called _domain_ name system. Thats why there are dots in the adresses. Also, DNS lookups are rare compared to IP route lookups, you look at DNS for every connection at most, limited by the TTL for caches. Route lookups happen for every packet.
    - corty 6y ago
      It doesn't, prefix lookup is solved faster and cheaper in hardware via CAM or TCAM, maybe combined with hashing, because you can limit yourself to a prefix, discarding the rest of the address. Even if you are right about the endpoints (which only need to know all devices in their specific subtree), as soon as you get to a part of the network where there is no longer just a limited tree below a given router hierarchically, you need a global view of all addresses. This view has to be current, correct and total. That is impossible to achieve, even if the lookup itself would work (which it won't, a conservative estimate of 4 billion active internet devices take up 64GB just for their addresses, not even including routes and metrics). You just cannot search those 64GB fast enough for each packet you are passing through your links (remember, even saturating 10GE in software is hard, and routers do have a lot of those ports in 40 or 100GE...).

JoeAltmaier 6y ago

Sure we can. Especially UUIDS. They have a normal distribution of values (bits are random) so an associative cache would match entries faster than current devices can match highly-repetitive prefixes. This is an example of what the IPV6 folks suffered from. They could only see the issues of previous implementations, and took an incremental step along those solution axes. Instead of considering future trends (cheaper memory/processing power) and "skating toward the puck". Instead they followed the puck, and ended up well behind.

corty 6y ago
A cache with a few billion devices in it will be too large, and as soon as your cache may be large enough you will have even more devices. Also, for routing an address hierarchy is nice because of the O(log n) properties the address tree gives you. UUIDs do not do that, but subnets do. For the endpoints and smaller routers near the edges it is even more advantageous, those only need to know a few local prefixes, the rest goes to the next gateway. With UUIDs, every devices needs to learn all the addresses behind it, quite an impossible task, even if the lookup were fast and small enough for its cache.
- JoeAltmaier 6y ago
  Again, for core routers, not at all. The UUID is random; it has the same order of lookup or better; endpoints need only the local routing info in the same way. Caches need only hold active routes, which is orders of magnitude smaller. The idea that its 'impossible' is 20 year old thinking. That's my whole point. We've wandered into a disappointing, underpowered solution that's not gaining traction. While real future-proof solutions exist right in front of us.
  - cesarb 6y ago
    > Caches need only hold active routes, which is orders of magnitude smaller. What do you do when there's no active route? If a router receives a packet from 192.0.2.1 to 198.51.100.2, but the router has never received a packet from 198.51.100.2, how does it know to which of its neighbors it should send the packet?
    - JoeAltmaier 6y ago
      We resolve arbitrary names (e.g. DNS) now, so clearly the solution is possible.
      - cesarb 6y ago
        We resolve arbitrary names with DNS to a global identifier (an IP address), but for routing, what you need is a local identifier (which neighbor router to send the packet to), which means every router or set of routers would need its own database, and each database would need to know about every host in the world. This is exactly what we have nowadays with BGP, only with networks instead of hosts: every core router or set of core routers has a database which knows about every network in the world, and tells which neighbor AS to send the packet to.
        corty 6y ago
        Also, DNS caches are just locally used small subsets. Global lookups are again hierarchical, thats why it is called _domain_ name system. Thats why there are dots in the adresses. Also, DNS lookups are rare compared to IP route lookups, you look at DNS for every connection at most, limited by the TTL for caches. Route lookups happen for every packet.
  - corty 6y ago
    It doesn't, prefix lookup is solved faster and cheaper in hardware via CAM or TCAM, maybe combined with hashing, because you can limit yourself to a prefix, discarding the rest of the address. Even if you are right about the endpoints (which only need to know all devices in their specific subtree), as soon as you get to a part of the network where there is no longer just a limited tree below a given router hierarchically, you need a global view of all addresses. This view has to be current, correct and total. That is impossible to achieve, even if the lookup itself would work (which it won't, a conservative estimate of 4 billion active internet devices take up 64GB just for their addresses, not even including routes and metrics). You just cannot search those 64GB fast enough for each packet you are passing through your links (remember, even saturating 10GE in software is hard, and routers do have a lot of those ports in 40 or 100GE...).