Author: David Marn

This blog post concludes the work I did during the Google Summer of Code 2016.

Spending the summer on nodewatcher was a pleasantly laborious exercise. Although my proposal concerned a development of a new algorithm, I realized that I also had to prepare various other components so that the algorithm would work. I started by sketching a short plan of different components I had to integrate for my algorithm to work. To remind the readers, SWOON is an algorithm for an efficient allocation of wireless frequencies in a densely populated area where many wireless access points interfere with each other. Before any work could begin, I had to install a local version of nodewatcher. I did not want to interfere with wlanslovenija’s mature network and I needed a small network of my own to run these tests. To find such a network, I collaborated with a non-profit organization based in Berkeley, California. They provided me with access to a building outfitted with more than 10 wireless access points. The wireless access points in this testbed are extremely diverse. They come from various manufacturers and not all broadcast on the 5GHz band. This allowed me to work with issues unique to community networks: software has to be built ground-up to be extremely modular and it has to support a diverse range of equipment, since there is no central planning authority.

I started with writing the data collection module, on which I have reported in my previous blog posts. Once I was able to work with the data, I worked on a different algorithm which detected rogue nodes in networks. This is especially useful for network maintainers who now have information on which nodes are most harmful to their network. They can now significantly reduce interference by working together. Algorithms on this scale have to be extremely efficient: I derived a complexity bound of O(E * log(V)) where E is the number of edges and V is the number of vertices in a graph. This allows the algorithm to scale all the way to wlanslovenija’s network or more, as it is almost linear. In order to achieve such scalability and efficiency, I had to peruse state-of-the-art graph theory research and utilize complex data structures (the one I used is called a disjoint-set data structure) to quickly order datasets in accordance with our needs.

I then moved on to the main algorithm, which took weeks to even rigorously define, let alone code up. I first considered implementing the Beigel-Eppstein coloring algorithm, which is known to run in ~O(1.3^n) time, but the complexity of the algorithm rendered it impractical. It relies on 19 different subcases which are iteratively used to simplify the constraint satisfaction (CSP) instance. Instead, I reverted to a custom implementation of a state-of-the-art greedy approach, which had to be modified from the source code of NetworkX, a leading open-source graph manipulation package. I devised a custom way of ordering the nodes in a graph to correctly prioritize wireless access points. The algorithm starts with looking at all the ‘neighbors’ (other nodes your radio detects) and computes the ‘busyness’ of each frequency band. We then minimize joint interference through the algorithm.

We observed an interesting property when running this algorithm on our wireless testbed. Most frequencies were moved to minimize interference, but some got worse. At first, we thought it was a bug, but we did eventually discover that some nodes must pick up more interference for others to remain noiseless. This perfectly coincides with our goal, which is to minimize the interference over all nodes, not every single node.

Next steps

One major problem with the algorithm is how unreliable ‘signal’ data is. We were thinking of coming up with a better metric to measure link quality instead of using signal strength. We were considering using the number of packet collisions instead. The modular design allows us to painlessly replace the metric without having to understand the entire algorithm.

We also noticed openWRT’s iwinfo doesn’t provide information about channel widths of access points. Adding this data would allow more accurate calculations instead of assuming all channels are 20MHz wide.

Finally, nodewatcher doesn’t yet have support for issuing node-specific warnings. I’d love to use such a warning to let a maintainer know that their node needs to change the channel.

However, I am confident this algorithm will enhance our user’s experience.

All my contributions can be seen on this link:
https://github.com/wlanslovenija/nodewatcher/commits/development?author=CdavM

If you’re interested in the timeline of the development, look at the following pull requests on nodewatcher’s GitHub:
Bug fixes related to a local installation of nodewatcher:
https://github.com/wlanslovenija/nodewatcher/pull/18
https://github.com/wlanslovenija/nodewatcher/pull/20
Data collection module:
https://github.com/wlanslovenija/nodewatcher/pull/22
Command that users can use to export data from the data collection module:
https://github.com/wlanslovenija/nodewatcher/pull/23
Improving the data collection module:
https://github.com/wlanslovenija/nodewatcher/pull/24
Algorithm that detects rogue nodes in one’s network:
https://github.com/wlanslovenija/nodewatcher/pull/25
Additional options for user-friendly data export command:
https://github.com/wlanslovenija/nodewatcher/pull/26
Testing framework for the rogue node algorithm + improvements:
https://github.com/wlanslovenija/nodewatcher/pull/27
Channel allocation algorithm implementation (not merged yet):
https://github.com/wlanslovenija/nodewatcher/pull/28
Updated data in nodewatcher/core:
https://github.com/wlanslovenija/nodewatcher/pull/29

Hi everyone,

This is my first update on working on SWOON, an algorithm to automatically allocate channels to nodes in nodewatcher. Not a lot of time has passed since I started working and but the wlanslovenija community was immensely helpful in getting me started. Up to now, I only worked on my own coding projects, where I got to be the main architect behind the codebase. I decided where functions were defined, I decided on the coding style, I did code reviews and I was the one to approve branch merges (of which there were none, because I wrote all the code 🙂 ). Now, GSoC threw me in the middle of a well established open source project where you have to get accustomed to existing coding practices. And accustoming to this was more difficult than I expected. So people from wlanslovenija had to be really patient with me (and I think they’ll have to keep this up for a while 🙂 ). But I slowly got the hang of it. My overarching plan for the algorithm is to first read the data, then process the data and finally issue a warning to those who maintain nodes with inefficient channel allocations. My work on reading the data from nodes is almost done (almost because a new amazing feature was suggested only yesterday!). On a tangent, I think this shows another immense benefit of community oriented projects – everyone’s free to suggest additional features that would make this process more eficient. To get the data about neighboring nodes, one has to temporarily turn the wireless radios off. Because of that, nodewatcher-agent only performs a survey of neighbors every two hours. But we collect data much more regularly. So how do we deal with this? My current implementation simply stores the data into the database every hour and it does not take into account the age of the data. I will now work on comparing the current datapoint with the latest one and only insert it into the datastream if the data has changed. This will reduce the space we’re using and could even be expanded for use by other modules. It’s great to know that you can contribute to any aspect of the project. Mitar, a senior developer of nodewatcher, said that they built all of it themselves, so we can rewrite anything as well.

I also worked on a parallel implementation of the mechanism, which read the data from old dumps. This gave me the insight into the architecture that made writing the actual implementation much easier.

My next steps are to finish the data collection part and create a module to analyze this data. This is exciting for everyone because there’s no documentation about writing such modules so I’ll get to be the first one to do it! I can only hope I’ll document it well enough to make the process easier for those who will follow as new members in the community. The github PR can be found here.