9 ms·

Without a system with prefixes every router needs to hold the next step for every single ip address in use in memory all the time and needs to be able to look t

Without a system with prefixes every router needs to hold the next step for every single ip address in use in memory all the time and needs to be able to look them up fast.

JoeAltmaier 6y ago
And today we can't do that? That's what I mean by, obsolete before it was deployed. IPV6 was designed in an age of lesser storage/higher cost memory and embedded processor power. And no, not every one. Store the ones routed thru you. That's all you need. Look them up and keep a cache.
- poizan42 6y ago
  Every node on a local network would need to be able to know whether another node is on the local network (unless you want all traffic to go through a router). So do you send arp requests for every ip you try to contact? Distribute a list through DHCP? All upstream routers needs to know about your node. So every time someone somewhere in the world connects a new device a message gets sent up to the core routers of the internet? And the core routers needs to keep track of routing tables in the size of billions and be able to look entries up in nano seconds.
  - JoeAltmaier 6y ago
    Thanks, yes those seem like possible algorithms that would work great with today's technology. And yes, every time new traffic appears at a 'core' router, entering it into a cache would be another great algorithm. But they do that now, so no patents for us. I love it when somebody 'objects' to a plan, then proceeds to describe the solution succinctly.
    - cesarb 6y ago
      > every time new traffic appears at a 'core' router, entering it into a cache How does that new traffic appear in the core router? I has to appear in every core router, otherwise hosts connected to a a core router which didn't receive that traffic recently wouldn't know how to route to your host. So the answer would be flooding, which is extremely wasteful of bandwidth and processing power. Also, it's a cache, which means it expires, so you have to flood the host announcements constantly (and even if it doesn't expire, you have core routers going down and being replaced). Once you think over all the details on how to fix these issues, what you end up with is basically a routing algorithm, like BGP or others, only replacing the "network" by a single host. And once you arrive at a routing algorithm, consider that routing algorithms have a long history, and have already received a lot of research. That naive "flooding" algorithm is basically RIP, one of the oldest routing algorithms; there are good reasons why most people don't use RIP anymore.
      - JoeAltmaier 6y ago
        Sure, lots of history. Which is why new solutions are such a hard sell - everybody quote an authority and concludes 'it has to be this way'. Traffic appears at core routers because it already gets send there by peripheral routers as a gateway. Sharing routing information between peer routers is not unsolvable nor likely onerous. Strawman solutions (flood constantly) are being deliberately dense. I suspect because, folks are so very comfortable with what they know, and so very unwilling to extend themselves. How we got IPV6 in the first place. Which isn't working either.
        cesarb 6y ago
        > Traffic appears at core routers because it already gets send there by peripheral routers as a gateway. Sharing routing information between peer routers is not unsolvable nor likely onerous. Strawman solutions (flood constantly) are being deliberately dense. If by "sharing routing information between peer routers" you mean that, when a router learn of a new host, it shares that information with its peer routers, which then share that information with their peer routers, that is flooding. Without flooding, the traffic would not appear at every core router, which means most routers would not know of your host. > I suspect because, folks are so very comfortable with what they know, and so very unwilling to extend themselves. I once seriously considered how to make an Internet-scale non-hierarchical routing protocol, where the host identifier was a cryptographic hash of its cryptographic public key. The reverse path is easy; once A has successfully sent a packet to B, all routers in the middle know how to get from B to A. The forward path (from A to B) is the hard one. Every router knowing every host is non-viable; consider, for instance, what happens when my phone roams from the WiFi to the LTE and back (which happens many times per day) - if every router had to know of that change, for every roaming phone in the world, it would be enough to overwhelm all the links between them, not to mention their CPUs. I came to the conclusion that the amount of propagation of the route updates must be limited for it to be viable, so having every router know of every host is not possible. Either the routing information must be summarized somehow (which is what the hierarchical routing used with IPv4 and IPv6 does), or some other way which does not involve the routers (for instance, path routing, like MPLS) must be used. That is, I'm not rejecting your idea because I "feel comfortable" with hierarchical routing, I'm rejecting your idea because I've already given it (or something like it) serious consideration, and found it harder than what I had initially thought.
- samoa42 6y ago
  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.

Without a system with prefixes every router needs to hold the next step for every single ip address in use in memory all the time and needs to be able to look them up fast.

JoeAltmaier 6y ago

And today we can't do that? That's what I mean by, obsolete before it was deployed. IPV6 was designed in an age of lesser storage/higher cost memory and embedded processor power. And no, not every one. Store the ones routed thru you. That's all you need. Look them up and keep a cache.

poizan42 6y ago
Every node on a local network would need to be able to know whether another node is on the local network (unless you want all traffic to go through a router). So do you send arp requests for every ip you try to contact? Distribute a list through DHCP? All upstream routers needs to know about your node. So every time someone somewhere in the world connects a new device a message gets sent up to the core routers of the internet? And the core routers needs to keep track of routing tables in the size of billions and be able to look entries up in nano seconds.
- JoeAltmaier 6y ago
  Thanks, yes those seem like possible algorithms that would work great with today's technology. And yes, every time new traffic appears at a 'core' router, entering it into a cache would be another great algorithm. But they do that now, so no patents for us. I love it when somebody 'objects' to a plan, then proceeds to describe the solution succinctly.
  - cesarb 6y ago
    > every time new traffic appears at a 'core' router, entering it into a cache How does that new traffic appear in the core router? I has to appear in every core router, otherwise hosts connected to a a core router which didn't receive that traffic recently wouldn't know how to route to your host. So the answer would be flooding, which is extremely wasteful of bandwidth and processing power. Also, it's a cache, which means it expires, so you have to flood the host announcements constantly (and even if it doesn't expire, you have core routers going down and being replaced). Once you think over all the details on how to fix these issues, what you end up with is basically a routing algorithm, like BGP or others, only replacing the "network" by a single host. And once you arrive at a routing algorithm, consider that routing algorithms have a long history, and have already received a lot of research. That naive "flooding" algorithm is basically RIP, one of the oldest routing algorithms; there are good reasons why most people don't use RIP anymore.
    - JoeAltmaier 6y ago
      Sure, lots of history. Which is why new solutions are such a hard sell - everybody quote an authority and concludes 'it has to be this way'. Traffic appears at core routers because it already gets send there by peripheral routers as a gateway. Sharing routing information between peer routers is not unsolvable nor likely onerous. Strawman solutions (flood constantly) are being deliberately dense. I suspect because, folks are so very comfortable with what they know, and so very unwilling to extend themselves. How we got IPV6 in the first place. Which isn't working either.
      - cesarb 6y ago
        > Traffic appears at core routers because it already gets send there by peripheral routers as a gateway. Sharing routing information between peer routers is not unsolvable nor likely onerous. Strawman solutions (flood constantly) are being deliberately dense. If by "sharing routing information between peer routers" you mean that, when a router learn of a new host, it shares that information with its peer routers, which then share that information with their peer routers, that is flooding. Without flooding, the traffic would not appear at every core router, which means most routers would not know of your host. > I suspect because, folks are so very comfortable with what they know, and so very unwilling to extend themselves. I once seriously considered how to make an Internet-scale non-hierarchical routing protocol, where the host identifier was a cryptographic hash of its cryptographic public key. The reverse path is easy; once A has successfully sent a packet to B, all routers in the middle know how to get from B to A. The forward path (from A to B) is the hard one. Every router knowing every host is non-viable; consider, for instance, what happens when my phone roams from the WiFi to the LTE and back (which happens many times per day) - if every router had to know of that change, for every roaming phone in the world, it would be enough to overwhelm all the links between them, not to mention their CPUs. I came to the conclusion that the amount of propagation of the route updates must be limited for it to be viable, so having every router know of every host is not possible. Either the routing information must be summarized somehow (which is what the hierarchical routing used with IPv4 and IPv6 does), or some other way which does not involve the routers (for instance, path routing, like MPLS) must be used. That is, I'm not rejecting your idea because I "feel comfortable" with hierarchical routing, I'm rejecting your idea because I've already given it (or something like it) serious consideration, and found it harder than what I had initially thought.
samoa42 6y ago
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.