[Make-wifi-fast] the hidden station problem

[Make-wifi-fast] the hidden station problem

[Dave Taht]

I was watching myself do then make-wifi-fast Q&A and henning mentioned
the hidden station problem and it's interaction with minstrel...

https://www.youtube.com/watch?v=Rb-UnHDw02o

Since we are doing up some better testbeds, I am curious as to what
might be a good (simplified) setup (bench or air) for it, and/or if
there has been a paper that shows the interaction problems with
minstrel in particular.


-- 
Dave Täht
Let's go make home routers and wifi faster! With better software!
http://blog.cerowrt.org

Re: [Make-wifi-fast] the hidden station problem

[David Lang]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 3377 bytes --]

On Thu, 21 Apr 2016, Dave Taht wrote:

> I was watching myself do then make-wifi-fast Q&A and henning mentioned
> the hidden station problem and it's interaction with minstrel...
>
> https://www.youtube.com/watch?v=Rb-UnHDw02o
>
> Since we are doing up some better testbeds, I am curious as to what
> might be a good (simplified) setup (bench or air) for it, and/or if
> there has been a paper that shows the interaction problems with
> minstrel in particular.

the basic way to see this is to take two stations and move them far enough 
apart, or put shielding between them so that they cannot talk to each other.

Then position a third station so that it can see both of the first two.

If you really turn the power down, you may be able to get away with them fairly 
near each other with a metal sheet next to one of them.

You will see that you can talk to either of them quite nicely if the other is 
pretty idle, but if you have them both sending a lot of data at the same time, 
disaster strikes.



If you are writing a simulator, add a probability that a packet transmitted from 
an edge station to the central station doesn't get through. Ramp up this 
probability and watch what happens. A better simulator would scale the 
probability up based on the amount of airtime needed, so that as the sender 
slowes down, the probability goes up.




This is one of the hardest problems for wifi to deal with. It manifests as 
massive amounts of lost packets when the first two are sending to the third one, 
and no amount of backoff helps. Slowing down the transmit rate just makes things 
worse as it takes longer to transmit each bundle and so it's more likely to be 
stepped on.



Reading up on Minstrel at 
https://wireless.wiki.kernel.org/en/developers/documentation/mac80211/ratecontrol/minstrel 
there is a comment

> Inspection of the code in different rate algorithms left us bewildered. Why 
> did all the code bases we looked at contain the assumption that packets sent 
> at slow data rates are more likely to succeed than packets sent at higher 
> datarates? The physics behind this assumption baffled us. A slow data rate 
> packet has the highest possibility of being “shot down” by some other node 
> sending a packet.

the answer to this is that the higher data rates require a better signal to 
noise ratio, and so if the problem is that the stations are too far apart, or 
there is a wall between them that makes the signal weaker, or that there is just 
a lot of low-volume noise in the area, the slower data rates are far more likely 
to be understandable than the faster data rates. Since Wifi was designed long 
before anyone imagined how common it would become (I remember when the pcmcia 
cards were >$1000 each rather than the current <$10 for a much faster USB 
adapter), they designed the protocol to fall back to lower rates if the packets 
don't get through.

This works well if you are out in the boonies and trying for range. It fails 
horribly in very high density environments (this is why most conference wifi is 
worthless for example)


This is why it's a good idea to disable the lowest data rates if you know that 
you don't need them.



reading the minsrel page, it seems intuitively obvious to me that this random 
packet drop would really mess with their moving average and thus the decisions 
they end up making.

David Lang

Re: [Make-wifi-fast] the hidden station problem

[Dave Taht]

the original minstrel paper is well worth reading.

http://blog.cerowrt.org/post/minstrel/

On Thu, Apr 21, 2016 at 10:57 AM, David Lang <david@lang.hm> wrote:
> On Thu, 21 Apr 2016, Dave Taht wrote:
>
>> I was watching myself do then make-wifi-fast Q&A and henning mentioned
>> the hidden station problem and it's interaction with minstrel...
>>
>> https://www.youtube.com/watch?v=Rb-UnHDw02o
>>
>> Since we are doing up some better testbeds, I am curious as to what
>> might be a good (simplified) setup (bench or air) for it, and/or if
>> there has been a paper that shows the interaction problems with
>> minstrel in particular.
>
>
> the basic way to see this is to take two stations and move them far enough
> apart, or put shielding between them so that they cannot talk to each other.
>
> Then position a third station so that it can see both of the first two.
>
> If you really turn the power down, you may be able to get away with them
> fairly near each other with a metal sheet next to one of them.
>
> You will see that you can talk to either of them quite nicely if the other
> is pretty idle, but if you have them both sending a lot of data at the same
> time, disaster strikes.
>
>
>
> If you are writing a simulator, add a probability that a packet transmitted
> from an edge station to the central station doesn't get through. Ramp up
> this probability and watch what happens. A better simulator would scale the
> probability up based on the amount of airtime needed, so that as the sender
> slowes down, the probability goes up.
>
>
>
>
> This is one of the hardest problems for wifi to deal with. It manifests as
> massive amounts of lost packets when the first two are sending to the third
> one, and no amount of backoff helps. Slowing down the transmit rate just
> makes things worse as it takes longer to transmit each bundle and so it's
> more likely to be stepped on.
>
>
>
> Reading up on Minstrel at
> https://wireless.wiki.kernel.org/en/developers/documentation/mac80211/ratecontrol/minstrel
> there is a comment
>
>> Inspection of the code in different rate algorithms left us bewildered.
>> Why did all the code bases we looked at contain the assumption that packets
>> sent at slow data rates are more likely to succeed than packets sent at
>> higher datarates? The physics behind this assumption baffled us. A slow data
>> rate packet has the highest possibility of being “shot down” by some other
>> node sending a packet.
>
>
> the answer to this is that the higher data rates require a better signal to
> noise ratio, and so if the problem is that the stations are too far apart,
> or there is a wall between them that makes the signal weaker, or that there
> is just a lot of low-volume noise in the area, the slower data rates are far
> more likely to be understandable than the faster data rates. Since Wifi was
> designed long before anyone imagined how common it would become (I remember
> when the pcmcia cards were >$1000 each rather than the current <$10 for a
> much faster USB adapter), they designed the protocol to fall back to lower
> rates if the packets don't get through.
>
> This works well if you are out in the boonies and trying for range. It fails
> horribly in very high density environments (this is why most conference wifi
> is worthless for example)
>
>
> This is why it's a good idea to disable the lowest data rates if you know
> that you don't need them.
>
>
>
> reading the minsrel page, it seems intuitively obvious to me that this
> random packet drop would really mess with their moving average and thus the
> decisions they end up making.
>
> David Lang



-- 
Dave Täht
Let's go make home routers and wifi faster! With better software!
http://blog.cerowrt.org

Re: [Make-wifi-fast] the hidden station problem

[Henning Rogge]

On Thu, Apr 21, 2016 at 7:57 PM, David Lang <david@lang.hm> wrote:
> On Thu, 21 Apr 2016, Dave Taht wrote:
>
>> I was watching myself do then make-wifi-fast Q&A and henning mentioned
>> the hidden station problem and it's interaction with minstrel...
>>
>> https://www.youtube.com/watch?v=Rb-UnHDw02o
>>
>> Since we are doing up some better testbeds, I am curious as to what
>> might be a good (simplified) setup (bench or air) for it, and/or if
>> there has been a paper that shows the interaction problems with
>> minstrel in particular.
>
>
> the basic way to see this is to take two stations and move them far enough
> apart, or put shielding between them so that they cannot talk to each other.
>
> Then position a third station so that it can see both of the first two.

Yes, three stations would be the minimum, but I would suggest trying
it with 4 stations (all of them in IBSS/Adhoc-Mode).

With three stations you still have one who can see everyone, which
might change the effects.

As soon as you have the chain of 3/4 stations, just setup IP
forwarding routes and send traffic over the chain in one or both
directions.

> If you really turn the power down, you may be able to get away with them
> fairly near each other with a metal sheet next to one of them.

Easy to do in an office building with 5 GHz devices... often you
cannot even reach offices through two walls.

> You will see that you can talk to either of them quite nicely if the other
> is pretty idle, but if you have them both sending a lot of data at the same
> time, disaster strikes.

Yes.

> If you are writing a simulator, add a probability that a packet transmitted
> from an edge station to the central station doesn't get through. Ramp up
> this probability and watch what happens. A better simulator would scale the
> probability up based on the amount of airtime needed, so that as the sender
> slowes down, the probability goes up.

Not sure how well current simulators can handle this.

> This is one of the hardest problems for wifi to deal with. It manifests as
> massive amounts of lost packets when the first two are sending to the third
> one, and no amount of backoff helps. Slowing down the transmit rate just
> makes things worse as it takes longer to transmit each bundle and so it's
> more likely to be stepped on.

I think reporting the "used airtime" in the beacons would help. This
might be a first step to detect the presence of hidden stations
because your own view of the airtime is different than the one of your
neighbor.

It would also be possible to add a hash of all known neighbor mac
addresses to your beacon. This way your neighbors KNOW if there is the
potential of a hidden station.

> Reading up on Minstrel at
> https://wireless.wiki.kernel.org/en/developers/documentation/mac80211/ratecontrol/minstrel
> there is a comment
>
>> Inspection of the code in different rate algorithms left us bewildered.
>> Why did all the code bases we looked at contain the assumption that packets
>> sent at slow data rates are more likely to succeed than packets sent at
>> higher datarates? The physics behind this assumption baffled us. A slow data
>> rate packet has the highest possibility of being “shot down” by some other
>> node sending a packet.

> the answer to this is that the higher data rates require a better signal to
> noise ratio, and so if the problem is that the stations are too far apart,
> or there is a wall between them that makes the signal weaker, or that there
> is just a lot of low-volume noise in the area, the slower data rates are far
> more likely to be understandable than the faster data rates. Since Wifi was
> designed long before anyone imagined how common it would become (I remember
> when the pcmcia cards were >$1000 each rather than the current <$10 for a
> much faster USB adapter), they designed the protocol to fall back to lower
> rates if the packets don't get through.

Exactly... the "lower bits per airtime" should help the receiver to
decode the frames. QAM64 (for high data rates) needs a lot more SNR
(or SNIR, Signal to Noise and Interference Ratio) than QPSK.

> This works well if you are out in the boonies and trying for range. It fails
> horribly in very high density environments (this is why most conference wifi
> is worthless for example)
>
> This is why it's a good idea to disable the lowest data rates if you know
> that you don't need them.
>
> reading the minsrel page, it seems intuitively obvious to me that this
> random packet drop would really mess with their moving average and thus the
> decisions they end up making.

I wonder if it would make sense to try the best data-rate again for a
second time if you detect you are in a hidden station environment with
a "low amount of airtime available".

Henning

Re: [Make-wifi-fast] the hidden station problem

[Dave Taht]

I have just finished re-consuming the entire (2600+ pages) 802.11-2012
specification. For those of you into that level of personal abuse, or
have insomnia, or want to make a dent in wifi's problems, I do
recommend a close reading. As specs go, it is pretty darn readable. I
made extensive notes on it, which I will publish at some point.
Probably of most interest to debloaters was section 9 on ampdu frame
formats (which sort of requires reading sec-3-8), various forms of
scheduling, how a block ack works (and could be more often disabled
via QosNoack), and so on.

the spec is now free:
http://standards.ieee.org/about/get/802/802.11.html and I would love
it if everyone here did try to get through section 9, which is only
about 50 pages.

In rereading it I was struck by how much most of our problems were in
areas that the standards viewed as out of scope!

and if you would like some insight as to how the 802.11wg works, see:

 http://grouper.ieee.org/groups/802/11/Publicity/What%20is%20802.11%20doing.pptx

I started at the 802.11ac one and then went off to sleep on a bed of
nails for relaxation.  (you kind of need to read both if you care
about ac, as it has extensive mods to the previous spec)

Nowhere in either spec was any reference to the hidden node problem.
AC pees on way more channels and does do some sort of dynamic backoff,
but... agh... I have to read the whole thing I guess.



On Thu, Apr 21, 2016 at 11:44 PM, Henning Rogge <hrogge@gmail.com> wrote:
> On Thu, Apr 21, 2016 at 7:57 PM, David Lang <david@lang.hm> wrote:
>> On Thu, 21 Apr 2016, Dave Taht wrote:
>>
>>> I was watching myself do then make-wifi-fast Q&A and henning mentioned
>>> the hidden station problem and it's interaction with minstrel...
>>>
>>> https://www.youtube.com/watch?v=Rb-UnHDw02o
>>>
>>> Since we are doing up some better testbeds, I am curious as to what
>>> might be a good (simplified) setup (bench or air) for it, and/or if
>>> there has been a paper that shows the interaction problems with
>>> minstrel in particular.
>>
>>
>> the basic way to see this is to take two stations and move them far enough
>> apart, or put shielding between them so that they cannot talk to each other.
>>
>> Then position a third station so that it can see both of the first two.
>
> Yes, three stations would be the minimum, but I would suggest trying
> it with 4 stations (all of them in IBSS/Adhoc-Mode).
>
> With three stations you still have one who can see everyone, which
> might change the effects.
>
> As soon as you have the chain of 3/4 stations, just setup IP
> forwarding routes and send traffic over the chain in one or both
> directions.
>
>> If you really turn the power down, you may be able to get away with them
>> fairly near each other with a metal sheet next to one of them.
>
> Easy to do in an office building with 5 GHz devices... often you
> cannot even reach offices through two walls.
>
>> You will see that you can talk to either of them quite nicely if the other
>> is pretty idle, but if you have them both sending a lot of data at the same
>> time, disaster strikes.
>
> Yes.
>
>> If you are writing a simulator, add a probability that a packet transmitted
>> from an edge station to the central station doesn't get through. Ramp up
>> this probability and watch what happens. A better simulator would scale the
>> probability up based on the amount of airtime needed, so that as the sender
>> slowes down, the probability goes up.
>
> Not sure how well current simulators can handle this.
>
>> This is one of the hardest problems for wifi to deal with. It manifests as
>> massive amounts of lost packets when the first two are sending to the third
>> one, and no amount of backoff helps. Slowing down the transmit rate just
>> makes things worse as it takes longer to transmit each bundle and so it's
>> more likely to be stepped on.
>
> I think reporting the "used airtime" in the beacons would help. This
> might be a first step to detect the presence of hidden stations
> because your own view of the airtime is different than the one of your
> neighbor.
>
> It would also be possible to add a hash of all known neighbor mac
> addresses to your beacon. This way your neighbors KNOW if there is the
> potential of a hidden station.
>
>> Reading up on Minstrel at
>> https://wireless.wiki.kernel.org/en/developers/documentation/mac80211/ratecontrol/minstrel
>> there is a comment
>>
>>> Inspection of the code in different rate algorithms left us bewildered.
>>> Why did all the code bases we looked at contain the assumption that packets
>>> sent at slow data rates are more likely to succeed than packets sent at
>>> higher datarates? The physics behind this assumption baffled us. A slow data
>>> rate packet has the highest possibility of being “shot down” by some other
>>> node sending a packet.
>
>> the answer to this is that the higher data rates require a better signal to
>> noise ratio, and so if the problem is that the stations are too far apart,
>> or there is a wall between them that makes the signal weaker, or that there
>> is just a lot of low-volume noise in the area, the slower data rates are far
>> more likely to be understandable than the faster data rates. Since Wifi was
>> designed long before anyone imagined how common it would become (I remember
>> when the pcmcia cards were >$1000 each rather than the current <$10 for a
>> much faster USB adapter), they designed the protocol to fall back to lower
>> rates if the packets don't get through.
>
> Exactly... the "lower bits per airtime" should help the receiver to
> decode the frames. QAM64 (for high data rates) needs a lot more SNR
> (or SNIR, Signal to Noise and Interference Ratio) than QPSK.
>
>> This works well if you are out in the boonies and trying for range. It fails
>> horribly in very high density environments (this is why most conference wifi
>> is worthless for example)
>>
>> This is why it's a good idea to disable the lowest data rates if you know
>> that you don't need them.
>>
>> reading the minsrel page, it seems intuitively obvious to me that this
>> random packet drop would really mess with their moving average and thus the
>> decisions they end up making.
>
> I wonder if it would make sense to try the best data-rate again for a
> second time if you detect you are in a hidden station environment with
> a "low amount of airtime available".
>
> Henning



-- 
Dave Täht
Let's go make home routers and wifi faster! With better software!
http://blog.cerowrt.org