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.
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:
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:
Data collection module:
Command that users can use to export data from the data collection module:
Improving the data collection module:
Algorithm that detects rogue nodes in one's network:
Additional options for user-friendly data export command:
Testing framework for the rogue node algorithm + improvements:
Channel allocation algorithm implementation (not merged yet):
Updated data in nodewatcher/core:
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.
I will contribute to one of the Freifunk projects; nodewatcher, via Google Summer of Code this summer and I wanted to keep you updated on my progress as well as exchange thoughts about my ideas.
First of all, nodewatcher is an open source, modular community oriented platform used for network planning, node deployment, node monitoring and maintenance. nodewatcher was initially developed to be primarily used by the wlan slovenija project. With 1336 nodes, it's really successful and a great example for community networks. As nodewatcher gets deployed elsewhere with even more nodes, it's natural to ask ourselves if we can be smarter about allocating spectrum to our wireless nodes - these nodes are mostly inexpensive wireless routers but it's natural to extend the meaning of the term to dedicated wireless access points (i.e. Unifi AP).
The theoretical foundation for this problem is fascinating by itself: Each node has a different amount of noise in each channel (the 2.4GHz band allows 3 non-overlapping channels where each channel is 20MHz wide) and each node wants to maximize its SNR (signal-to-noise ratio). I will term this as the greedy approach, which is already used in enterprise level devices. However, in an urban setting, nodes are close enough to each other for their signal to act as noise to other nodes. The greedy approach is no longer optimal as it bears a high price of anarchy. Instead, our goal is now to maximize the sum of channel capacities (under a power constraint). I will have to devise an algorithm to solve this problem and the algorithm does not seem trivial since the number of combinations is increasing exponentially with the number of nodes in the system. Even with only 10 nodes, we haveover 59000 possible allocations on 2.4GHz band and over 95 trillion on the 5GHz band.
Traditional networking literature tackles this optimization problem with Lagrange multipliers. An alternative is to look at approximate graph coloring schemes and compute chromatic numbers. I hope to experiment across various settings and approaches.
Over the course of the project, I hope to experiment with a real network which consists of at least 10 nodes and measure the improvements. One exciting thing about real life experiments is that nodewatcher was mostly used inside wlan slovenija's network and I get to run it independently! This will probably allow me to fix some bugs on the way and contribute to nodewatcher in this aspect as well.
The algorithm will initally be developed as a nodewatcher module, but I hope to eventually port it to openwrt (possibly after the summer ends). The main difficulty is that nodewatcher can act as a central level planner, whereas the openwrt scenario requires negotiation among nodes. So it's harder to convince a node to decrease its TX power to benefit other users. But imagine a network where nodes can communicate and achieve a socially optimal point of spectrum allocation! A glorious future awaits us.
Thanks to this year's GSoC, a lot of work has been done on nodewatcher v3 platform. It now has a better, modular monitoring agent that can run on OpenWrt-supported devices, with a new JSON-based output format that can be easily reused by other projects as well. The platform has been ported to the latest stable version of Django (1.6) together with all migrations and dependencies. Development environment setup now uses Docker and fig in order to make it very easy to dive into the code without having to battle with various dependencies.
The API for access to node configuration and monitoring data (registry API) has been much improved, with better, more usable querying capabilities and performance. During development we have discovered a bug with cascade deletions and polymorphic models in Django. Node configuration editor based on the registry API now supports references between form models that have not yet been saved -- this functionality enables configuration of bridge interfaces which are now also supported by the firmware generator. I have implemented type support in the datastream library for long-term monitoring data storage with a new type for storing graphs as datapoints. This enables nodewatcher v3 to use datastream to store how the network topology evolves over time.
All the code is available on GitHub in several repositories:
A quick update on what is happening regarding my GSoC project with bringing nodewatcher v3 platform closer to reality. Version 2 of nodewatcher used its own simple key-value format and a bunch of shell scripts to provide monitoring data. In order to bring this into the modern era where JSON and ubus are available as compact libraries on OpenWrt by default, I have in the last few days created a new modular OpenWrt monitoring agent that can run on nodes and periodically obtain data from various sources (directly from procfs, from uci, from netifd via ubus, from nl80211 netlink API via OpenWrt's libiwinfo, etc.).
The daemon is implemented in C and different data sources are implemented as loadable shared object modules, enabling simple extensibility. Nodewatcher agent then provides all of the collected data in two ways: a) it can directly output data to a JSON file that can be served via HTTP; and b) it also provides an ubus object called nodewatcher.agent that exposes a get_data method, so other applications can obtain the same structured data as an ubus blobmsg. The nodewatcher monitoring agent could perhaps also be reused by the proposed Freifunk Monitoring and Administration Panel.
The nodewatcher-agent repository is hosted on GitHub with a README file providing a quick description of the used format, the ubus API and the currently implemented modules:
I have also packaged the agent for OpenWrt so it can be installed together with its various data source modules via opkg. The packages are available in the nodewatcher firmware package repository:
The agent and its packages should be considered alpha and the schema is still subject to change.
My GSoC work focues on the next version of nodewatcher, an open source (GNU AGPL licensed) network planning, deployment, monitoring and maintenance platform for community wireless networks. Its main idea is to automate as much as possible in building and operating a community wireless network. It encompasses functionalities sometimes named “node database”, “network dashboard”, “network map”, but also a web-based firmware image generator, which allows easy generation of customized firmware images for each node individually.
The previous version (v2) that is currently deployed by wlan slovenia has most of the functionality hardcoded for the use in our network. With version 3 we are making nodewatcher into a fully modular platform that can be reused and adapted by various community wireless mesh networks around the world and this GSoC project will bring us closer to making this a reality. Development can be tracked on GitHub (https://github.com/wlanslovenija/nodewatcher, branch development) and on wlan slovenia development Trac (https://dev.wlan-si.net).
About the author
My name is Jernej Kos, a computer science researcher, software developer and network engineer with over nine years of experience. I enjoy working on interesting projects, specifically with backend architecture and low-level details. I have experience with scalable web application development, development of software for embedded devices, routing protocol internals and security protocols. I am currently involved with open source projects, the most prominent being wlan slovenia, where I have developed a modular platform for network monitoring and provisioning, an efficient L2TPv3 based VPN solution that runs on OpenWrt-supported devices, a big data time series processing library and a simple system for multiprocess serial communication. My current research interests include secure, Sybil-tolerant and privacy-aware decentralized services and novel location-independent compact routing protocols. To this end I have developed Boost.ASIO C++ bindings for CuveCP and in the course of my PhD thesis am working on a secure and scalable location-independent compact routing protocol that can be used in mesh networks and/or for building decentralized social networks.