IPv4 addresses are running out. IPv6 seems to offer the promise of a vast, effectively limitless address space. However, is that true? Could it be that even IPv6 addresses are too limited in size to allow potential future routing problems to be tackled? Maybe, if we want scalable, efficient routing. How could that be though?
IPv4 addresses are all but exhausted, IANA having run out in 2011, APNIC shortly thereafter and RIPE in 2012.The idea is that we switch to IPv6, overcoming the obstacles to transition that have now been engineered into it (e.g. usually a completely unrelated address space from IPv4, so significantly hampering IPv6 from being able to make transparent use of existing IPv4 forwarding capabilities).
IPv6 addresses are 128 bits in length, compared to the 32 bits of IPv4. So in theory IPv6 provides a massive address space compared to IPv4, of 2128 addresses. Exactly how massive? Well, some have calculated that that is enough to assign an IPv6 address to every atom on the surface of the earth, and still have addresses to spare. If every IPv6 address was assigned to a node with just 512 bytes of memory, then some have calculated the system in total would require more energy than it would take to boil all the oceans on earth – presuming that system exists only as pure energy! So by those estimates, the IPv6 address space seems like it is so massive that we couldn’t possibly ever come close to using all of it, least not while we’re confined to earth.
Those estimates however assume the addresses are used as pure numbers with perfect efficiency. In reality this will not be the case. To make computer networking efficient we need to encode information into the structure of the addresses, particularly so when those networks become large. The lower, least-significant 64 bits of an IPv6 address are effectively reserved for use on local networks, to allow for auto-configuration of IPv6 addresses on ethernets. Changing this would be quite difficult. So IPv6 actuall;y offers only 64 bits to distinguish between different networks, and then a further 64 bits to distinguish between hosts on a given network. Further, of the upper, most-significant 64 bits (i.e. the “network prefix” portion of an IPv6 address), already at least the first, most-significant 3 bits are taken up to distinguish different blocks of IPv6 space. This means the global networking portion of the IPv6 address space only has about 61 bits available to it.
IPv4 and IPv6 BGP FIB sizes: # of prefixes on a logarithmic scale. Courtesy of Geoff Huston.
Why could this be a problem? Isn’t 61 bits more than enough to distinguish between networks globally (i.e., as on the Internet)? Well, that’s an interesting question. The global Internet routing tables have continued to grow at super-linear pace, as can be seen in the plot above (courtesy of Geoff Huston), with at least quadratic growth and possibly exponential modes of growth. IPv4 routing tables have continued to grow despite the exhaustion of the address-space, by means of de-aggregation. IPv6 routing tables are also growing fast, though from a much smaller base. There have been concerns over the years that this growth might one day become a problem, that router memory might not be able to cope with it, and so that could bottleneck Internet growth.
At present with BGP, every distinct network publishes its prefix globally and effectively every other network must keep a note of that. Hence, the Internet routing tables grow in direct proportion to the number of distinct networks in number of entries. As each entry uses an amount of memory in logarithmic proportion to the size of the network, the routing table growth is slightly faster than the size of the network in terms of memory. So as the Internet grows at a rapid pace, the amount of memory needed at each router grows even more rapidly.
If we wanted to tackle this routing table growth (and it’s not clear we need to), we would have to re-organise addressing and routing slightly. Schemes where routing table memory growth happens more slowly than growth of the network are possible. Hierarchical routing schemes existed before, and BGP even had support for hierarchical routing through CIDR and aggregation. However, as hierarchical routing could lead to very inefficient routing (packets taking very roundabout paths, compared to the shortest path), other than in carefully coördinated networks, it never gained traction for Internet routing, and support for aggregation has now been deprecated from BGP. Other schemes involving tunnelling and encapsulation are possible, but they suffer from similar, intrinsic inefficiencies.
A more promising scheme is Cowen Landmark Routing. This scheme guarantees both sub-linear growth in routing table sizes, relative to growth of the network and efficient routing. In this scheme, networks are associated with landmarks, and packet addresses contain the address of the landmark and the destination node. One problem with turning this into a practical routing system for the Internet is the addressing. How do you fit 2 network node identifiers into an IPv6 address? Currently organisations running networks are identified by AS numbers, which are now 32-bit. However, 2×32 bit = 64 bits, and there are no more than 61 bits available at present in IPv6 for inter-networking.
Generally, any routing scheme that seeks to address routing table growth is near certain to want to impose some kind of structure on the addressing in similar ways. The 64 bits of IPv6 doesn’t give much room to manoeuvre. Longer addresses or, perhaps better, flexible-length addresses, might have been better.
Are IPv6 addresses too short? Quite possibly, if we ever wish to try tackle routing table growth while retaining efficient routing.
Paul Jakma's Blog 
Paul Marks said
I think the routing scalability problem will ultimately be solved using tunneling. When you wrap IPv6 in IPv6, it’s effectively a 256-bit (or even variable-length) address.
For an example of this, see http://en.wikipedia.org/wiki/Locator/Identifier_Separation_Protocol
The nice thing is that the outer IP header can be added/removed in the “core” of the Internet, without end devices ever needing to know it exists.
Paul Jakma said
Yes, indeed tunnelling solutions like LISP could solve routing scalability for a core of the internet. However, just like hierarchical routing, it can not guarantee efficient routing/forwarding (i.e. that the path taken isn’t appreciably more than the shortest-path on average, and guaranteed to be no more than a low number of extra-hops in the worst case).
Further, many (all?) of the mapping proposals for LISP seem to just result in the scaling issues shifted off the core routers to another set of routers – which doesn’t really seem as if it solves the problem. Indeed, in that case, that would make LISP worse than hierarchical routing (which could at least give scalable routing at all routers).
To get both scalable routing tables at ALL routers AND efficient forwarding, there are only a few schemes – Cowen landmark routing and the Brady-Cowen scheme are the only ones that come to my mind. Both those schemes require structure in the addresses used by the forwarding path.
Even for Cowen landmark routing, the least demanding of those schemes on the address, it seems like the IPv6 address size might be a bit too tight.
Paul Marks said
I think there may be a disconnect between optimal routing in CS papers, and practical routing in the Internet.
Internet routing is clearly not optimal, because an IP address doesn’t contain any spatial coordinates. But that carries an advantage, since it allows you to use an IP address anywhere in the world, as long as you’re plugged into BGP. The problem is, there’s not enough capacity to let everyone do that.
The key insight behind LISP is that everyone doesn’t really need to talk to everyone else. Some guy who wants to multi-home behind two residential ISPs can get a cheap router and publish his ISP-assigned IP addresses in the LISP database, and in theory it should work as long as he doesn’t need to communicate with millions of other networks simultaneously. Entities who do need that sort of connectivity can afford beefy routers with bigger cache.
LISP does require a big distributed database with billions of rows, but that’s a relatively easy problem once you allow lookups to take tens of milliseconds, instead of microseconds.
Paul Jakma said
Neither of the schemes in the papers I linked to require spatial information (in the sense of some external physical space) to be encoded into addresses. The “Landmark” in “landmark routing” has nothing to do with geographic routing, they are purely topographical landmarks.
IP addresses of course already *do* encode topographical information into the address. The most significant prefix is advertised to BGP globally. There may be further structure in the address relevant to the internal structure of the ISP.
Current IP routing on the Internet is basically hierarchical routing, but with very little hierarchy.
Landmark routing also involves a hierarchy, but allows local routing info to “leak” out a bit, in a controlled way, such that you *do* get scalable routing tables, but without the problems of poor routing in places that previous hierarchical schemes suffered from.
I still don’t see how LISP does anything but shift costs around, and shifts the burden of keeping large and fast-growing amounts of forwarding state to the edges. If the major ISPs are having problems with the costs of memory needed to support these routing tables, then I’m not sure how potentially much smaller players are going to have an easier time affording these costs.
The next problem is that LISP involves tunnelling. The Internet unfortunately has had its ability to adapt to larger packets engineered out of it. IPv6, sadly, bakes this damage in. See:
How does LISP avoid the problem of users on LISPed links being effectively unreachable from various parts of the Internet because of the MTU-blackhole brain-damage?