« On scheduling jury duty | Main | Queuing at doctors and movie theaters »
July 23, 2007
Why would I want contiguous addresses?
ARIN (the American Internet Registry)'s recent statement on v4 address allocation has generated a bit of a stir. The important text is:WHEREAS, community access to Internet Protocol (IP) numbering Resources has proved essential to the successful growth of the Internet; and,WHEREAS, ongoing community access to Internet Protocol version 4 (IPv4) numbering resources can not be assured indefinitely; and,
WHEREAS, Internet Protocol version 6 (IPv6) numbering resources are available and suitable for many Internet applications,
BE IT RESOLVED, that this Board of Trustees hereby advises the Internet community that migration to IPv6 numbering resources is necessary for any applications which require ongoing availability from ARIN of contiguous IP numbering resources; and,
BE IT ORDERED, that this Board of Trustees hereby directs ARIN staff to take any and all measures necessary to assure veracity of applications to ARIN for IPv4 numbering resources; and,
BE IT RESOLVED, that this Board of Trustees hereby requests the ARIN Advisory Council to consider Internet Numbering Resource Policy changes advisable to encourage migration to IPv6 numbering resources where possible.
Obviously, this is written in some sort of legal-speak, but the important bit is the section about "ongoing availability of contiguous IP numbering resources." Here's how to understand this: remember that IPv4 addresses are 32-bit numbers. If you only have one IP address, it doesn't much matter what it is, as long as it's valid. But if you have more than one, it's extremely convenient for all the numbers to be contiguous. Why? Because it's easier to talk about them.
This is pretty easy to see in the context of routing. Say I've just been assigned addresses A, B, and C. I want to tell all the links on which I'm connected to others "hey, if you want to talk to A, B, and C", talk to me. This requires me to send three separate data items and them to store three separate items. That's not so bad when I only have three addresses, but starts to get a little unwieldy if I have 3 million. It's much more convenient to have addresses which are sequential and then I can say "I have addresses A through A+2" (or A through "A+2000"). But you can only do this if your addresses are contiguous.1
In the IP address world, we actually want something a little more than
contiguous. We want bit alignment.
IP addresses are 32-bit numbers and the way that blocks
are expressed isn't by simple ranges but by prefixes. This is easier
to write up with 8-bit addresses (0-255). So, when I get a block of
addresses in this space, it looks like this: 240/5, which
means "all the addresses with the first 5 bits the same
as 240. When we write 240 in binary we get:
11110000 (I'm showing the
fixed bits in red.). So, this leaves us with 3 bits to play with and
they can take on any possible value. I.e.:
11110000
11110001
11110010
11110011
11110100
11110101
11110110
11110111
So, contiguous addresses are good, but packing them efficiently turns out to be a tricky problem, for two reasons:
- We have a federated assignment scheme, which means that
a central registry assigns big blocks to the
routing information registriesregional internet registries [correction from Kurtis Lindqvist -- EKR] (RIRs), who then assign them to others. IANA only doles out more addresses once the RIRs start to run out. This tends to cause fragmentation. - When people overrun their allocations and need more addresses, they naturally want to have a new, contiguous, block. So, either way say now, in case they have fragmented blocks, or we say yes, creating an available hole for the block they used to have, which is fragmented (I don't actually know how often people are made to give up their old blocks).
The end result is that as you start to run out of room you reach a state where you still have empty space but that you can't assign it in as big blocks as you'd like. Incidentally, this situation isn't that different from what happens with dynamic memory allocation for software, although the time scale is a lot shorter in that case.
1. For much the same reason, you see kidnappers in movies asking for nonsequential, unmarked bills.
Posted by ekr at July 23, 2007 8:20 AM | Filed under: Networking
Comments
OTOH, SRAM is cheap and port #s are few.
So you can always just have routers that have, say 8-16 Gb of SRAM and just route on individual IPv4 addresses with a single lookup (and who needs no steenkin TCAMs at that point).
Posted by: Nicholas Weaver at July 23, 2007 8:47 AM
Actually the abbreviation RIR normally refers to "Regional Internet Registry" in the context of IP address allocations.
Posted by: Kurtis Lindqvist at July 24, 2007 2:46 PM