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

Talk faster and not so loud…

… I’m in a hurry and my head is pounding.

Ever read something a dozen times only to notice something completely new the 13th time around? Not too long ago I was perusing some boring vendor specs (chances are it was ours) and noticed something on the transmit power specs:

– 6 Mbps | 23 dBm
– 9 Mbps | 23 dBm
– 12 Mbps | 23 dBm
– 18 Mbps | 23 dBm
– 24 Mbps | 23 dBm
– 36 Mbps | 22 dBm
– 48 Mbps | 20 dBm
– 54 Mbps | 19 dBm 

As the data rate increases, the maximum transmit power decreases. I’ve actually observed this before but I never stopped to think of why. Why does the transmit power decrease? 

I’m quite fortunate that I work for a company like Ruckus. I can walk into Bill Kish’s office (uber genius CTO) and ask him this very question. Instead of trying to put things in my own words and looking like I’m some smart guy, I’m going to start by quoting Bill: 

“OFDM backoff due to high peak to average power ratios of higher OFDM modulations.

OFDM signals are more challenging to amplify since with all the subcarriers you sometimes get ‘unlucky’ combinations of the values on the different subcarriers which results in high peak signal strength.  These high peaks would cause the amplifier to go non-linear, distorting the signals.  Sorta like ‘clipping’ in an audio amplifier.

This effect gets worse with higher order modulations.  So two things: for OFDM you need to turn down power compared to e.g. CCK and furthermore you need to turn down power even more for each higher order modulation.   Good radio design and good PAs (power amplifiers) can reduce this effect but not really eliminate it.”

I ran this through the GT translator and this is what popped out:

Let’s imagine that you have an audio source (e.g. your phone) connected to an amplifier and speakers. During slow, soft music (e.g. 1 Mbps CCK) everything is fine. However, when you start playing faster music like techno and house mixed together (OFDM) the chances of “too much music” coming out of your source and overpowering your amplifier increases. As the music gets faster and chances of a peak increase, the input volume to the amp needs to be reduced to avoid clipping. This is the very reason why AP manufactures sets decreasing transmit powers for higher OFDM modulation rates.

When any manufacturer tells you their maximum Tx power and EIRP that is almost always for the lowest data rates. Sure, that helps you just fine if you are trying to gain more coverage but coverage isn’t the main concern for most enterprise installations. Throughput and capacity are paramount. 

What’s the best way to compensate for this Tx power loss at higher speeds? Antennas.

Resisting… sales…. pitch…. 

🙂

GT

RTS/CTS. Request to Send / Clear to Send. But, don’t remember what it stands for because it’s lying to you.

RTS/CTS is one of those protocols that is widely misunderstood. At face value it appears that it’s job is some sort of “negotiation” to determine if it’s ok to talk. It reminds me a bit of my kids. “Dad, can I ask you a question?” Well, you just did dear. 🙂

“Requesting” to send is a bit of the same thing. A Wi-Fi device has to send send a frame to… request to send? No, it doesn’t do that. I truly don’t want people to know or remember what RTS/CTS stands for because it is misleading.

RTS/CTS has nothing to do with requesting access or clearing the way. If you don’t believe me, well, there is nothing I can do to help that.

Ok, you’re a believer. Read on.

RTS/CTS has the same function as toast. Yeah, like hot browned bread just out of the toaster. No one (except the English I think) eat toast plain. Americans eat toast with butter and preferably with butterand jelly. So, what is the toast good for? To carry your butter and jelly. Now, if truth be told, many of us would rather just eat the butter and the jelly out of the jar but civilized people don’t do that so we drowned some brown bread in loveliness and call ourselves sophisticated.

The purpose of toast is merely a carrier for butter and jelly. RTS/CTS is just a carrier as well. It carries something called a duration value. A duration is quite simple. It’s an amount of time that we want everyone in receiving range to stay quiet. Why do we want them to stay quiet? Because Wi-Fi is anarchy and anything that can be done to fix that can be helpful. Ok, that wasn’t as in-depth as you may have liked. Go here to see one problem it can solve: http://en.wikipedia.org/wiki/Hidden_node_problem.

When a device receives any frame (including RTS/CTS) with a duration value >0 (duration values are in microseconds) it will set something called a NAV timer. If you’ve never heard of this don’t fret. It’s just a fancy way of saying “countdown timer”.

Simply put, if any device hears a duration value, it sets it’s NAV and stays quiet at least that amount of time. Wish I could do that during family outings.

What’s the difference between an RTS and a CTS? Have you ever played Marco Polo as a kid? Someone says Marco and what do you do? You say Polo. If an RTS frame is sent to you (RTS’s are always unicast) the you MUST respond with a CTS frame. RTS frames have space for two addresses and CTS frames have space for one.

RTS and CTS frames are used quite often in Wi-Fi so when you are sniffing a network (www.sniffwifi.com) and you see them just remember that they are there to help your network. Or a denial of service attack. Ah, I love Wi-Fi. 🙂

GT