Wi-Fi and Neighborhood Conflicts: An Algorithm to Keep the Peace

http://actu.epfl.ch/news/wi-fi-and-neighborhood-conflicts-an-algorithm-to-k/

by Wookai • 12 years ago

41 26 12 years ago

actu.epfl.ch

Wookai• 12 years ago

Link to technical paper: http://infoscience.epfl.ch/record/186014/files/saw-infocom13...

exelius• 12 years ago

I actually had a similar idea recently but assumed it must have already been part of the protocol. Obviously it wasn't, and truly good ideas are never unique, so kudos to this guy for doing the work and coming up with a functional algorithm.

One question I have is how this would perform in an incredibly congested area like an apartment building. The author only modeled out 2-way conflict; I have no idea how this algorithm would react if placed in a situation with 15 competing Wi-Fi access points.

Overall a good, nerdy read - this is the kind of shit I keep coming to HN for.

hrzn7• 12 years ago

I'm the main inventor. Thanks a lot for the positive feedback!

You are actually right, similar ideas have already been proposed before. The main novelty here is that the algorithm adapts not only the channel (center frequency), but also the bandwidth (i.e., the actual amount of spectrum that is consumed).

Adapting the bandwidth gives a precious additional degree of freedom; in particular, in a case with many competing WLANs, the algorithm would typically tend to reduce the bandwidth consumed by each WLAN (assuming the interfering WLANs are not idle and actually sending traffic). Reducing the bandwidth potentially reduces the available capacity (if you were alone), but it's still much more efficient than letting Wi-Fi use the time domain to avoid interference, so it results in increased throughput compared to current situations.

It turns out that adapting the bandwidth is becoming a necessity, because newer versions of Wi-Fi consume more and more bandwidth. This is better if you are alone, but may be harmful if you have many neighbors.

azinman2• 12 years ago

Are you going to release this algorithm in any of the open source router projects like ddwrt?

cesarb2• 12 years ago

in a case with many competing WLANs, the algorithm would typically tend to reduce the bandwidth consumed by each WLAN

Wouldn't that use more battery, since for a narrower channel the radio would have to be kept on for longer to transmit (or receive) the same amount of data?

darkmighty• 12 years ago

I have a few questions!

First, what do you think of the b/g/n wireless structure? If you could redesign it from the ground up what would you change to maximize performance (given the same bandwidth)?

Second: would allowing routers to communicate improve your solution significantly?

Thanks, great work btw

cpitman• 12 years ago

I'm glad someone at least seems to be addressing congestion. Every 802.11 standard seems to have hopped on the "multiple bandwidth by 2x" bandwagon, which is great if I live in a single family house with tons of space.

I don't, I live in a city, in an apartment building, surrounded by apartment buildings. I can frequently see 30+ networks. I'm sure there are wireless phones and other devices crowding the spectrum as well. Give me more channels, or better ways to share spectrum, anything other than dividing the number of usable channels with every update.

cesarb2• 12 years ago

Every 802.11 standard seems to have hopped on the "multiple bandwidth by 2x" bandwagon, [...] anything other than dividing the number of usable channels with every update.

It might use 2x the bandwidth, but it will use it for half the time for the same amount of data, so it all evens out (almost; there's an unused "border" between channels, so 2x the bandwidth is a bit more than 2x faster, and it will use a bit less than half the time).

And the 802.11ac standard has a way to better share the wide channels and the narrow channels; see the "Dynamic Bandwidth Operation" chapter of the "802.11ac: A Survival Guide" book at http://chimera.labs.oreilly.com/books/1234000001739/ch03.htm...

jdthomas2• 12 years ago

Hmm, I have not read his paper, but based on the article's mention of "divided into 13 channels" this is clearly speaking of the 2.4Ghz spectrum. Rather than try to distribute that evenly, you are FAR better off upgrading your AP and switching to a 5Ghz channel. First, there are far more potential channels in 5Ghz. Second, they are wider bandwidth (40Mhz, 80Mhz if 80211ac). And third, 5Ghz does not propagate through walls as well (a _feature_ when you have neighbors also using the spectrum).

My other thoughts: if he is using 8 channels instead of the standard 3 (1,6,11) then there will be some overlap; 80211 devices tends to better handle in-channel interference. http://en.wikipedia.org/wiki/List_of_WLAN_channels

ar_turnbull• 12 years ago

I switched to 5g last year, but all of my neighbours have caught up. Worse still — we all have legacy networks on the 2.4ghz spectrum so that our older devices can access the Internet. There are probably two dozen networks accessible from my couch. It's crazy in apartment buildings.

I would suggest that it should become part of our condo fees / building management, but I have little confidence in our board.

ajhodges• 12 years ago

Not to mention there are many devices that still don't support 5ghz (a notable/annoying example being Chromecasts). Switching to 5ghz is not a solution to the problem outlined in this paper, it's a bandaid.

breakall• 12 years ago

I have this exact problem: a couple dozen 2.4 Ghz APs are visible to me. Actual throughput at a distance of 6 feet from a 2.4 Ghz router is 1 Mbps (tested with multiple APs). I switched to 5 Ghz and luckily no one else has! Unfortunately, this doesn't solve the problem for all devices -- for example, the Chromecast is 2.4 Ghz only. With the chromecast, I practically can't use the chromecast in a room other than the one that the AP is in. I was thrilled when the Amazon Fire TV Stick came out with 5 Ghz capability. This made it possible for me to stream Netflix, etc. to the tv in the other room.

hrzn7• 12 years ago

You're right; but actually the mention of 13 channels was just for the example. The algorithm works exactly in the same way for the 5G band as well (where you have similar problems as soon as you have a few neighbors using recent Wi-Fi devices).

jdthomas2• 12 years ago

Interesting, glanced through your paper. How do you find real devices behave at constrained channel widths (<20Mhz in 2.4, <40Mhz in 5)? I have a feeling those are not well tested scenarios :)

swinglock• 12 years ago

Unless he is using more channels than 1, 6 and 11 the article is dangerously poorly written. Unlike what the article suggests, all other channels overlap and will cause actual interference! Do not configure your AP using any other 2.4 GHz channel, even if they already have other APs in range.

hrzn7• 12 years ago

The algorithm takes into account the interference of partially overlapping channels. In fact, it is part of the optimization procedure to minimize this overlap (globally, over all WLANs, but in a decentralized way), while still using as much of the spectrum as possible. This is a general optimization that is relevant for both 2.4G and 5G bands (or pretty much any other band that provides a finite amount of spectrum).

BoppreH• 12 years ago

When I chose a channel for my router, there was a clear option labelled "auto". If this algorithm for channel selection is novel, what does "auto" do?

Also, kudos for the idea. This is a much needed feature in today's crowded condos.

pluma• 12 years ago

Current routers can change preset channels, or can even find them automatically, but they do not offer real-time adaptation.

mikecarlton• 12 years ago

Auto usually just means scan channels at boot time and pick one that seems good (presumably the least amount of traffic).

And on at least one SoC I worked with (Realtek) I swear the algorithm was "return 6".

rayiner2• 12 years ago

These sorts of technologies are really interesting, and will play a big part in getting the most out of limited wireless spectrum. But the big picture problem is that we're shoe-horning all this incredibly useful technology into the ghetto that is ISM band. We need more unlicensed spectrum, and we need better rules for that unlicensed spectrum that prohibit anti-social behavior: http://esd.mit.edu/WPS/esd-wp-2006-01.pdf.

hroi• 12 years ago

Dynamic Frequency Selection and Transmit Power Control (part of 802.11h) is already a requirement for 5GHz in many countries: http://en.wikipedia.org/wiki/Channel_allocation_schemes#DCA_...

rayiner2• 12 years ago

Kind of. DFS is about sharing the 5 GHz band with incumbent radar installations. Basically how it works is that you have to listen for radars using the channel, and if you hear one, you have to get off the channel within a certain number of milliseconds. But DFS systems don't switch channels in response to other Wi-Fi networks, nor do they switch channels in order to optimize aggregate bandwidth.

Wi-Fi and Neighborhood Conflicts: An Algorithm to Keep the Peace

Related Stories