Darwin the Sysadmin

Mimicking Evolution for better Wi-Fi in apartment complexes

Everyone hates unstable, unreliable Wi-Fi, and still, it’s everywhere. One of the most common reasons for slow Wi-Fi is other routers. There is a limited amount of data that can be transmitted through the air at any time, and other routers on the same channel as yours will reduce your precious download and upload speeds.

Competing with other routers for the same capacity is known as Wi-Fi congestion. In large apartment complexes, there may be hundreds of routers that share the same frequency as there are only 3 non-overlapping channels to choose from on the widely used 2.4GHz band.

In dense apartment complexes, a single router may share its wireless transfer capacity with more than 10 other routers. When one of the competing routers are transmitting data, you can send less data. When several of these routers are transmitting data, your Wi-Fi speeds might get so low that it essentially become unusable.

Channel Planning

Networks in our offices

When controlling every, or at least the majority, of routers in an apartment complex, one can carefully plan which routers uses which channel depending on which channel their neighbors are utilizing. In Domos, we can often control the channel of nearly every router in some apartment complexes, and we may therefore plan the channel selection such that the routers interfere as little as possible with each other.

Sounds great, right? Unfortunately, channel planning is not a simple problem. When an apartment complex has 100 routers, there are 3¹⁰⁰ or 700 000 000 000 000 000 000 000 possible ways the channels on all the routers can be setup. More than a mouthful, even for the greatest of super-computers. A computer that could test a billion solutions a second would still take 23.000 years to test all the solutions.

Figure 1

Figure 1 is a representation of two smaller apartment complexes. A colored circle represents a router and its channel. The line between the circle represents which routers can see each other. We can easily observe that there are several places where there is a non-optimal configuration of the routers.

The Channel Planning problem isn’t unique. Data Scientists are faced with similar problems with seemingly endless possible solutions and outcomes. Chess, for example, have more possible outcomes than there are atoms in the universe, making it inconvenient to calculate each of them. To conquer these problems scientist has come up with many methods, some use complex math, while other solutions are inspired by nature.

Genetic Algorithms

Genetic algorithms are inspired by nature, genes, and evolution (if you believe in that sort of stuff). Our own building blocks, DNA, have ridiculous amounts of possible combinations (around 4.5 million zeros worth). The clear majority of DNA combinations (99.9999999999% is an understatement) would not make a living creature, and yet here we are.

Evolution has, by using time and a few simple tricks, found these good, working sequences of DNA in the mix of seemingly infinite amounts of bad sequences. Since evolution is so good at making these combinations, some researchers found out we could use similar techniques for other problems. Genetic algorithms are problem-solving techniques where we represent the problem similarly to DNA, and then mimic evolution to get a good solution.

As it turns out, we can use Genetic Algorithms to set up a good configuration of routers.

Preparations: Representing the problem as a genetic sequence

DNA are, simply put, strings of interconnected Cytosine ©, Guanine (g), Adenine (a) and Thymine (t). Over-simplified, if your DNA has an ‘g’ in the 101242 place and a ‘t’ in the next place, you might have abnormally large pinky toes. The DNA are the genetic instructions that make you, you. When we write down DNA sequences, we write them as a list.

A DNA sequence example: g-c-g-b- … -b-g-t-g

How can we represent routers and their respective channels in a similar manner? There are 3 non-overlapping channels, let us call them r (red), g (green), b(blue), the actual channels are 1, 8, 13 per the protocol, but that doesn’t really matter. Much like the DNA sequence, we can write them down as a list. Router Channel sequence from figure 2: r-g-b-b- … — b-g-g

Figure 2

Figure 2 shows how similar DNA structures and the router channel problems are as structures. Since we can represent routers and their channels similarly to DNA, we can also mimic evolution, to get better configurations of routers and their channels. How it’s done is explained in 4 steps:

Step 1 — Genesis

The beginning for humans and all other, organisms here on earth was most scientist believe was the random chance of some molecules that happened to crash into each other and create the first organism.

We will mimic these random starts by generating a bunch, for example 100*, of random Channel Sequences.

1) r-g-b-b- … — b-g-g

2) g-r-r-b- … — r-b-g

….

100) b-g-g-r- … — g-b-r

  • The numbers were chosen for simplicity to explain

Step 2 — Survival of the fittest

Simply a bunch of random channel sequences doesn’t help much, we must figure which of the sequences yields good Wi-Fi for everyone in the apartment complex.

Determining fitness: In evolution, the likelihood or reproduction is the measure of fitness. 1 in 200 men alive today are direct descendants of Genghis Khan, so in evolutionary terms, he would be one of the most successful human ever [1].

We don’t really care how well a bunch of routers will reproduce (that’s not the kind of research we do), we do however want them to have as good Wi-Fi as possible.

We will measure the fitness for a channel sequences by how routers must use overlapping channels.

Figure 3 shows how three routers that are near each other are represented as sequences, and how the channels change the fitness.

In the previous section, we decided to start with a population of 100 random channel sequences. It is likely that most of these sequences are bad. It is however, also likely that some of them are better than the others. What we want to do now is pick the, let’s say 40, fittest sequences out of our population. These 40 sequences will live on and join us in the next section. While the other 60 (the unfit) will die a horrible death (erased from the memory).

Step 3 — Sex and X-men

Now we got 40 random sequences that happened to be better than some other random sequences. That does not seem like much (and it’s not). There were however, something in the building blocks of these solutions that made them better than the others. What we now want to do is to take these building blocks and let them evolve into better sequences.

We do this the same way evolution does, through mutation and reproduction. A mutation is a change in the DNA sequence. For our router sequences, a mutation would mean that a few of the routers changed their channel.

Reproduction is the process where offspring are made from parents. Sexual reproduction is when two individuals go together and share their genes and create offspring.

Out of the 40 left from the horrible survival of the fittest, we will pair them up and let them make babies. How? The children will have some of their mom’s qualities, some of their dad’s qualities and a bit of random sprinkled in (mutation). For example, like this:

Dad: d-d-d-d-d-d-d-d-d-d-d-d, Mum: m-m-m-m-m-m-m-m-m, Random mutation: X

Child 1: m-d-X-m-m-d-d-d-d-m-m-m-d, Child 2: d-m-m-m-d-X-d-d-m-m-X-d-d

Let’s take the 40 sequences or 20 pairs of parents and let them have two children each.

Step 4 — Repeat

Now we got 40 parents and 40 children, we have gone through one generation. If we add 20 random to the pool of sequences, were back at the initial population size of 100.

We can start the process over again. One generation is not enough, we didn’t go from single-celled organisms to humans in a few generations. We must repeat this process for thousands or millions of generations. New generations and survival of the fittest and in each generation, add some random solutions so that entire process isn’t fully determined by the random start.

The idea is that for each generation, the population get fitter, and when the process is repeated enough times we will eventually end up with a great channel sequence.

Summary

Figure 4

In figure 4 we see the result of a Genetic Algorithm on a small apartment complex. The one on the left is where the routers or the customer have chosen the channel them self. As we easily observe, there are several red routers that must compete. Two of their routers share their wireless transfer capacity with 3 other routers. On the right-hand side is the same apartment complex, after the genetic algorithm. The apartment complex has gone from 6 to 1 overlapping routers. Small apartment complexes like this would not need a Genetic Algorithm to find an optimal solution, but when the complexes have hundreds of routers it gets very complicated.

By mimicking the teachings of Charles Darwin, we’ve managed to reduce the average competing routers in larger Apartment Complexes by 66%.

Notes

- Simply looking at the number of competing routers is a bit simplistic to determine the best channels for an entire Apartment Complex. In Domos, we take into consideration Radio Noise and Signal-Strength of the routers, and also when and how much data router normally transmits. However, going into to detail on all of that here would have made this article too complicated.

- Does it seem like we need to check a lot of different sequences for this to work? Say we use a population of 1000 sequences. And we run the process for 10 000 generations. That means we have to check 1 000 *10 000 = 10 000 000 sequences, which is proccessed in a matter of a few minutes with a normal computer. A lot less than the 23 000 years to check every possible solution.

- There are many ways of recombining, mutating, adding randomness, determining fittest, survival, who pairs up with who, the order of which to perform the operation, etc. And the methodology is generally simplified in this text.

[1] http://blogs.discovermagazine.com/gnxp/2010/08/1-in-200-men-direct-descendants-of-genghis-khan/#.WJrnVzvhCMo