Happy Birthday Paradox!

Disclaimer

I’ve read over my own words here and I thought that it would be good to insert a disclaimer. It isn’t normal for me to talk about a complex topic without some context but unfortunately I need to here because this is a blog and not a book. However, here are a few links that should provide some context if the subject of contention is new or a bit rusty. The first is a paper written by Marcus Burton. The second is the full meal deal, the CWAP book. Enjoy!

Now for the Beginning

The birthday paradox, also known as the birthday principle is a math equation that calculates probability of two people in a group having the same birthday (day/month). As an example, to guarantee that two people in a group have the same birthday you’d need 367 people because there are 366 possible birthdays.

Here is where I’ve earned myself some extra cash on the side and dazzled many an intoxicated onlooker. Let’s say there are 30 people in the room. I put $100 on the table and tell you that I’ll bet that two people in this room have the same birthday. Your gut tells you that you should take that bet but you are hesitant because I sound so confident. Keep your money in your pocket because I would have a 70% chance of winning. Yes, with only 30 people in the room there is a 70% chance of a duplicate birthday. This isn’t because people don’t want to go outside in the winter either. It’s all about the math. In fact, with only 23 people there is a 50.7% chance of duplicate birthdays. Why? Well, I’ll let you click the links above because I want to get somewhere Wi-Fi-ish with this blog and lots of math is a surefire way to get people to stop reading. 🙂

If we can assume for a minute that birthdays are randomly distributed then that makes for a great analogy to Wi-Fi. Wi-Fi uses a randomly generated number system called a random backoff timer to help avoid collisions . This is the basis for a system called contention. Two or more devices “contend” for access to the medium.

The Wi-Fi Paradox

The question is, what are the chances that a collision will occur? First, we need to know the number of possible “birthdays”. Before a device transmits regular data (not voice or video) it will randomize between 0 and 15. That give us 16 different possible choices. With that known, what are the chances of collision with x number of devices?

2 – 6%
3 – 18%
4 – 33%
5 – 50%

What that means is that if there are 4 devices contending for the medium there is a 33% chance of collision. Better stated, if you had that as a persistant situation, your network would have a 33% collision rate. That is of course unacceptable and would make for a poor Wi-Fi network.

For the life of me I can’t figure out where to conclude this thing. This is one of those discussions that will have a lot of rabbit holes and I can’t figure out when I’ve said enough. Good thing I love to talk because my writing is horrible.

Anyway, I think this deserves a follow up at some point. For now I want to leave you with a few questions to ponder on:

– Is it actually feasible and common that 4 or 5 devices would be contending with each other simultaneously (in the same contention windows)?
– Our example used the number 16 but what would happen if the randomization is with fewer numbers such 8 or 4?
– Will varying frame sizes make a difference in the collision rate?

GT