Wi-Fi and Neighborhood Conflicts: An Algorithm to Keep the Peace | Hacker News Reader

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

actu.epfl.ch

41 pointsWookai26 comments

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.

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

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

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.

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.

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.

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).

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 :)

All 802.11n devices supporting the 5G band support at least a bandwidth 20 MHz (as well as 40 MHz). In addition, you can use 5 and 10 MHz as well on some Atheros devices with open source drivers.

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.

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).

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.

> 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...

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.

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.

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

I'm thinking about it, but the current implementation that I wrote (which runs on OpenWrt) is currently somewhat too constrained to my Atheros hardware. I'll try to improve it though.

> 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?

Usually, 802.11 devices don't turn off between transmissions, so this has no effect. In fact, it's actually the opposite; using a narrower channel requires a slower clock rate, which also significantly reduces power consumption of the wireless device.

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

Well, I think that 802.11 is not that bad. Conceptually, the way it schedules packet transmissions over time turns out to be quite efficient (at least in WLANs scenarios), even though this efficiency is somewhat reduced with newer and faster PHY layers (packets transmission being faster, the time spent in backoff to avoid collisions increases the overhead).

From an engineering point of view, my personal opinion is that the fact that 802.11 operates in a completely decentralized way is probably more desirable than having a more complicated solution that would require AP-to-AP communication but would most likely provide only marginal gains (several researchers have shown the close-to-optimal nature of purely decentralized CSMA-style scheduling). In case of spectrum assignment, it can benefit from AP-to-AP communication, especially if you want or need to enforce particular optimization criteria, such as maximizing throughput or fairness (I've personally experimented with that kind of algorithms as well). But often the overall gain does not justify the extra complexity.

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_...

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.

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.

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

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".

Reply on news.ycombinator.com