The birthday problem (allocation collisions) for networks and MAC addresses

The birthday problem is a fairly simple to state situation. There is at least a 50% probability (e.g. even chance) that at least 2 of 23 randomly chosen people in a room have the same birthday. This comes from some elementary applications of statistics, and is documented on Wikipedia. While we care less about networks celebrating their annual journey around Sol, we care more about potential address collisions for statically assigned IP addresses. And, curiously, MAC addresses. Ok, first some Julia code:

function P(N::Integer,M::Integer)
  prod = 1.0
  for i in 0:N-1
    prod = prod * float(M-i)/float(M)
  end
  prod
end

Now cut and paste this into your REPL (julia command line, I’ll wait). Now, we can replicate the P(A') and P(A) calculations on the wikipedia page trivially.

julia> P(23,365)   # P(A')
0.49270276567601445
julia> 1-P(23,365) # P(A)
0.5072972343239855

And our mechanism is generic enough, that we can apply this to Classful networks with IPv4, and other things. The equivalent calculations for a IPv4 class C network (/24), with 1 gateway, 1 broadcast address, so 254 usable addresses …

julia> P(20,254)    # P(A')
0.4639660131994906
julia> 1-P(20,254)  # P(A)
0.5360339868005094

That is, just 20 defined (random) addresses in the class C are enough to get at least a 53.6% probability that there will be one address collision. You might think, “hey, this is for statically defined addresses, so who cares, we do DHCP everywhere”. Doesn’t matter though, as the DHCP server has to allocate an address, preferably an unused address. It has to test that address to see if it already exists (defensive coding … should really be done) in case another system allocated this address to itself. Of course, you might say “Darn it, we’ll just use class B’s everywhere. So lets look at that again. Remembering that a class B is 65536 - 2 = 256*256 - 2 = 65534 addresses. I mean, this is more than enough … right?

julia> P(302,65534)    # P(A')
0.49926691064939116
julia> 1-P(302,65534)  # P(A)
0.5007330893506088

Yeah … you only need 302 allocated addresses out of the pool of 65534 to get at least a 50% probability of a collision on allocation. What about a class A? I mean really … we shouldn’t get collisions … we have sooo many addresses … First, number of addresses

julia> 256^3 -2
16777214

so …

julia> P(4823,16777214)     # P(A')
0.49999139514729646
julia> 1-P(4823,16777214)   # P(A)
0.5000086048527035

Erp … just 4823 addresses out of 16M. In fact, if you look at it closely, you’ll realize that the crossover point goes as about the square root of the number of slots (IP address in this case). This of course, assumes that the space isn’t sparse, that all addresses are accessible. If the space is sparse, so that large chunks are never allocated or used for whatever reason, you wind up with an interesting problem. You reduce the size of the space by the size of the holes. Which reduces the number after which you will get a collision. Ok. So why on earth would I spend time tackling something that is ostensibly a solved problem? Well, there is another problem related to these, that people building out large data centers have likely seen. MAC address space collisions. Technically, MAC48 is obsolete. In practice, it is still very much in use. So we have to live with consequences of this. There are

julia> 256^6
281474976710656

addresses in this space. Which, if we use our preceding rough approximation of the square root of that number, we’d get about 16M unique random MAC addresses before we hit a collision. Or

julia> P(19753662,281474976710656)     # P(A')
0.5000000188521087
julia> 1-P(19753662,281474976710656)   # P(A)
0.49999998114789135

Imagine, if you will, a network with 1M machines, each with 32 VMs and unique MAC addresses per VM. You will have greater than a 50% chance of a MAC48 collision on this. This analysis assumes (of course) that the space isn’t sparse. It’s not like there is a vendor field … er … no … wait. There is. First 3 octets in the address are the vendor OUI. Second 3 are the address. So technically, your pool is really out of 16777216 per vendor. So … if this is a popular unit, say a LOM NIC, and the vendor wraps the MAC addresses, rather than requesting/paying for allocating another OUI segment … You could get a collision. Similarly a very large number of VMs on many machines in the DC … you could get a collision. The analysis gone through here is fairly naive, but it shows that such collisions are anything but improbable. Might be worth thinking about in the era of IoT. IPv6 could help with 3.4 x 1038 addresses … we’d need order of magnitude 1019 addresses see higher probabilities of collisions … This might seem like a long way off, but … imagine if you are working on an allocator for these addresses, and you have a 50% or more probability of generating a collision. Which suggests that you are going to have to rethink how you allocate addresses, what state are you going to preserve (do you really want to store even a small fraction of what you allocated???), etc. Someone once said something about N kilobytes being enough for any machine, or maximum of M computers as the total world market. Both scenarios had nothing to do with collisions, but were based upon some (wildly) incorrect assumptions about the future. While IPv6 looks like it will push out the pain for a while, there are other aspects to this that might need some looking at now, and planning for a future where we have the ability to easily extend the range as needed. I mean, we have 1019 addresses before we have to worry about higher probability of collisions … what could go wrong?