Developing Challenges of Multi-Hop Mesh Telephony on Android

If you are reading this blog, you probably know that the Serval Project is all about making mesh telephony practical, so that people can communicate anywhere, any time.

For regular Android software development, it is often practical to use the Android emulator to reduce the time between updating source code and seeing the effect of the change.

For Serval, this isn't really an option, because we work below the Android API layer, and much of the software development challenge is related to making the WiFi chipsets do what we want.  We also have a fair amount of native code to do the mesh routing and telephony functions.  In fact, we currently have an entire distribution of Asterisk in the Serval Mesh software, which must be decompressed and installed when the Serval Mesh APK is installed or updated.

Together, these contribute to an update process that can take several minutes to between modifying a line of code and seeing it on an Android device, especially on the low-cost devices that are our primary targets, and when using the debug option in eclipse.

Those minutes add up over time, and so I decided to minimise the install time as much as possible, and also address another problem with developing our software, that is detecting when you have an actual multi-hop network.

To reduce the install time, I started looking at the Asterisk installation to see what we could safely throw out.  I managed to get rid of about half of the loadable modules, several utilities and all of the speech files that Asterisk comes bundled with.  This reduced the size of the APK by a little over 1MB, down to just under 5MB, and cut down the install time by about 15%.  Further savings came from removing unused audio codecs in our SIPDroid-derived SIP client, saving another 0.4MB, and getting the whole thing down to less than 4.5MB and installing about 25% faster than previously.

The bulk of the remaining time is about evenly split between installing Asterisk and testing that the WiFi control works properly.  For development, it probably makes sense to separate out the Asterisk installation from the other files we need to deploy on installation, as we really don't modify the Asterisk files between builds.  This shouldn't be too hard to do, but I have run out of time tonight.

Also, for our target handsets, we really don't need to test the WiFi control every time we update, so we should be able to set a flag to tell the software that we are in development mode, and just assume that the WiFi control works.  This now works by checking if a file called /sdcard/serval/developer-mode/fast-wifi exists, and if so, bypassing those tests, and thus saving about 15 seconds.

So over all the minimum time from hitting "run" in Eclipse to getting the software ready has been reduced from 85 seconds down to 48 seconds (without debugging).

The over significant development convenience task I have worked on in the last few days is one that is probably of more general interest.  The peer list now shows the number of hops to each of the nodes that your phone knows about, as shown in the image below.  This was produced by having two phones at opposite ends of my house, and having the phone shown here with me out on the street.

Each row of the peer list now shows the telephone number, e.g., 5550344, the batman link score, e.g., 243, the ping time to the peer, e.g., 19 milli-seconds, and either "direct" for nodes we can reach directly, or the number of hops to reach the node, e.g., 2 hop.

Importantly for debugging, this displays doesn't ask BATMAN how far to the node in question, but actually enquires of the time-to-live (TTL) field in the IP header, and thus returns the true distance from your phone to the phone in question (the return path might be a different length, though).

Actually, because of limitations with the Java UDP programming interface, the TTL field is read by the Serval DNA daemon (which is written in C), and included in the returned UDP packet to the requesting client.

This means that we can just look at the interface on the screen (and so can all of you who have been asking us for this feature) and see what is happening to routes, instead of having to connect to the phone with a USB cable and enter all sorts of commands to ask BATMAN and the operating system what might be happening.

So all in all we now have a slightly faster and easier development process, that I am sure will more than save the couple of person days of effort that they took to develop, and thus enable us to work faster instead of harder.

Deploying a Phone Tower, Serval Style (The Day In Pictures)

So yesterday we went to beautiful Normanville with the goal of testing the maximum range between phones running our mesh telephony software.

We didn't get particularly far on that front, but we did discover some very interesting things about the unique requirements of mesh routing between mobile telephones, which will likely be the subject of a upcoming blog post.

But what we did do was deploy a mobile phone tower of a different kind.  Romana has wanted to make her wheel chair into a mobile phone tower for some time, and yesterday was her chance, as the pictures show.

Romana in her chair with Lyn beginning to attach the 7 metre long squid pole we use as the mast.

Further attaching of the mast.

Beginning to raise the mast.  The blob on the top is a Huawei IDEOS U8150 mobile phone running our software and acting as the "repeater".

 The raising of the mast:

Victory! Romana's wheel chair is now a mobile phone tower.

 But it wasn't all hard work.  The weather was glorious, and the views most excellent, and others were out and about enjoying the day ...

Or hoping for a chip.

Meanwhile, we moved to the jetty so that we could place our mobile phone tower (including blanket for the cool sea breeze).

The pole really does stand up quite high. It gets the phone about 6m above the deck of the jetty:

... which is a little higher than even the lamp post

Then we started walking along the beach towards Carrickallinga, slowly deploying a 6-hop mesh, and making multiple simultaneous voice calls amongst the nodes.

Corey and Romana did a great job standing on the jetty and talking to us via our impromptu phone network, while locals and visitors enjoyed the day:

This was also the first time that my son Caleb came along on a Serval expedition.  Little did he know that his pram was soon to become a phone tower as well.

Here I am with Lyn deploying a node some distance from the jetty:

Then it was Jeremy's turn:

Then the pram:

And all the while we were able to make calls among the various nodes.

We did encounter some serious mesh routing issues, which as I mentioned I will talk about soon, but for now I just wanted to let you all enjoy the pictures.

Photos and Update from Nigeria - and introduction to Rhizome

We have a partner organisation working in Nigeria looking at citizen-sourced journalism and using our mesh network as the connectivity among a number of camera-equipped cell phones, so that citizen journalists there can make a short video or news piece and then have it distribute automatically over the mesh using our Rhizome protocol.

Rhizome is our mesh file distribution protocol that allows user-created content and software updates to spread hop-by-hop over the mesh.  This hop-by-hop approach elegantly solves many of the problems with mesh-wide file transfer, in particular bandwidth starvation and instability of long links.

We have called it rhizome because it is like the vegetable reproductive process of the same name, because we think it is a good analogy for the way that Rhizome allows data to spread by small hops, but such that over time it can spread over great distances.

We are busy working on making Rhizome do all that the team in Nigeria needs, but in the meantime, the team in Nigeria have sent us some photos showing the mesh in action.

First, they sent photographic evidence of 10 IDEOS U8150 phones forming a mesh with our software:

10 Serval BatPhones on the mesh (and a call in progress!)

They also sent us this picture which I really love, because it shows a community getting started with out technology thousands of kilometres from where we are writing the software here in Australia.  This is what it is all about, people using and benefiting from the software that we are creating and releasing.

Finally, just a week after they got 10 phones on the mesh, they sent this shot showing 15 phones on the mesh.  This was just a case of them getting 15 phones within range, as the underlying BATMAN mesh protocol should be able to handle a couple of hundred devices without any difficulty:

One of the challenges we are looking at solving with this group is auto-update of the mesh software, over the mesh.  That is, we want to be able to load a signed software update onto any one of the phones on the mesh, and have the phones on the mesh share it automatically with one another.

This is a great idea, and the Rhizome protocol will allow us to do this, however it introduces some security challenges.

In particular, we don't want someone or some party seizing or cracking our signing key, and then being able to spread a trojan update that destroys the Serval mesh.

One approach we are looking at is making the update require that the new version be signed by a majority of keys from a pool, where each key would be held by a different mesh-friendly organisation.   The pool of trusted keys could then be similarly updated by a majority vote of existing trusted keys.

This will allow us to spread the keys among countries and jurisdictions and provide the kind of distributed resilience that the Serval Project is predicated on, and even allows the software to continue to be refined and distributed if the Serval Project as an organisation ceases to exist.

If you think that your organisation might like to be one of our key custodians, let me know.

More progress on the overlay mesh network

It is 5:58am and dawn is just beginning.

I have been up all night making the best of the need of an overnight sleep study for our son, which requires an adult to perform a specific function every 15 minutes throughout the night.

Programming in these little pieces feels a bit like the software development version of watching commercial television; just as you think you are about to witness something really interesting there is an interruption.

Nonetheless, I have made significant progress getting the overlay mesh to send and receive advertisements of a different kind; notices by one node that they can reach another node.

There are plenty of bugs that I know about, without even thinking about the ones that I don't know about, and also some code that is still plain old missing.  But even so, I have got the code forming a multi-hop mesh and keeping track of the routes to them.

I ran two nodes connected to two separate dummy networks, so that they couldn't see each other.  Then I connected an extra node in the middle that bridged the two networks, and after a short delay, viola, the nodes could all see each other.  The image shows the routing table from one of the nodes with only one network interface.

The 0000000* addresses in the neighbour table are clear evidence of some of those bugs I mentioned, as is the crazily large age field for one of those.

The FDB3BA1*, D64CEB4* and B167503* addresses are nodes that I had temporarily added to the mesh, and then removed again fairly recently, so the routes were (correctly) still hanging around with their link scores steadily dropping.

The important part is the route to D6850E3*, the node on the other network, for which the current route is via 30464E5*, which is the node bridging the two networks.  30464E5* was a node that I had previously bridging the networks just a short while earlier, and we can see the lingering route as it decays.

B167503* is the node currently bridging the link, and it's score is still climbing, and is about to overtake the recently removed node and become the route of choice.

So while I have a lot more work to do, the basic function of the mesh to discover multi-hop paths and switch routes based on appropriately calculated scores.

But right now, I am going to bed.

Why User-Land Mesh Networks Are Necessary For Heterogeneous WiFi Mesh Networks

The normal approach to creating a mesh network is to write a program that does some tricky stuff to work out how to get from node A to node Z via whatever nodes might be in the middle, and then tell this to the operating system so that packets get routed according to these instructions.

We are doing something different for Serval, in that we are having the program that does all that tricky stuff carry the messages between nodes, instead of asking the operating system to help out.

This has some disadvantages and some advantages.

First, the disadvantages, and why we think that they aren't such a problem for our application.

1. Such "user-land" overlay networks suffer from an inefficiency known as "double-copy", where every packet sent or received ends up getting copied not once by the kernel, but twice, once by the kernel, and once by the overlay program.  This is bad if you are processing lots of data.  But on a mesh network the actual throughput of data tends to be fairly low (it is one of the well known problems with mesh networks).  So this problem is kept under control.

2. Programs that want to know about the mesh network need to know about the overlay and have to use special calls to talk to the mesh.  This is bad if your primary goal is allowing people to run BitTorrent, SSH, for example, because you need to modify each of those programs to support the new network, and without operating system cooperation that can get a little messier than you might like.

However, for a mesh telephony platform, and where we know that bandwidth starvation is one of the greatest potential problems, there is actually merit in requiring people to go to some effort before they enable their application to consume the limited resources of the mesh.  We will be adding the support to the initial core applications we intend to run over the mesh, so this isn't really a big deal.

Now for some advantages:

1. We don't need operating system cooperation.  This makes it easier to port the mesh to all operating systems, both desktop and mobile.  It is especially important because the need to fiddle with routing tables requires root/administrative access on most platforms.

For mobile platforms, this is certainly true on Android, and I believe iOS, with together constitute the majority of smart phones.  This alone means that we have to take this path.

But it also gives us some additional upside here, in that it means we could make a USB key loaded with Serval mesh software that could be run on any desktop computer, and without administrative access or being "installed" could enable that computer to participate in the mesh.  In fact, it could probably even be an HTML5 application running in a web browser.

2. It separates us from the underlying network addressing. Many devices and networks only support IPv4, but there aren't enough IPv4 addresses to go around. But by pushing our mesh network addressing into a dedicated addressing layer we can solve this problem.

We use 256bit Elliptic Curve cryptography keys as the basis for our address

In fact, using this approach it is possible for every single Serval enabled device on a mesh to all have the same IPv4 address, provided we use only broadcast traffic, which we do for a very important reason:

Broadcast traffic is the only traffic which WiFi ad-hoc can reliably carry between devices with incompatible or buggy ad-hoc implementations.  For example, we cannot get unicast traffic to flow reliably between Mesh Potatoes and Huawei IDEOS U8150/U8180 phones.  However, we can get unicast traffic to flow between Mesh Potatoes and the original Android G1 developer phones, and between the G1 and the U8150/U8180 phones.

Unfortunately mesh routing protocols all tend to use broadcast traffic to discover available routes, and thus the routes choose the impossible Mesh Potato-U8150/U8180 links, which is very bad indeed.  But by making the mesh traffic itself broadcast we ensure that what the mesh routing protocol and what we are trying to do is the same, instead of merely similar.

Taking this a little further, by transporting the mesh topology management information in the same packets as the data we can directly measure the performance of the mesh delivering the traffic we really care about, rather than using different packets as an indirect measure -- especially since the distribution of packet sizes can otherwise be very different, and WiFi packet losses are not insensitive to packet length or differentiation between broadcast and unicast traffic.

Implementing this is of course a significant undertaking, and I have already spent a few weeks programming away.  But the effort is beginning to yield results.  Today for the first time I have the new overlay mesh detecting nodes and building the in-memory route table. You can see a screen grab here:

So here you can see some debug output from a Serval DNA node running in overlay mode using a file called dummy0 as a dummy network interface.

I realised early in the development of the overlay network that I would need some convenient simulation tools to make it easier to debug the behaviour of the mesh.  I decided the best way to do this was to make the software itself also a network simulator.  So I added support to pretend an ordinary file is a network interface.  Any instances of the overlay pointed to the same file would all append their "packets" to the end of the file, and remember where they had got up to reading from the file, and keep an eye out for any packets deposited by other nodes.

Each packet also has a header that has space for location information, transmission power, time, node velocity and heading and a whole pile of other information that can be used to drop packets that are deemed to have been sent from too far away, or suffering collision during reception and so on.

The file then also represent a log of all activity on the mesh which has already proven very helpful for debugging.  I will also create a tool that allows for the creation of visualisations of the mesh in action to help understand why things go wrong, and to explain the operation of the mesh.  I will post such animations here once I get that far.

Back to the trace, the error messages are mostly information for me for development (although there is on link-list bug that I can see I will need to fix to avoid a memory leak).

There are a few 256bit addresses that can be seen.  The all-f's is the mesh broadcast address, while the one that starts with 9d5f is the address of a node on the mesh.

These addresses are really big, and so I have already implemented a variety of mechanisms for abbreviating the addresses.

For example, the broadcast address is used so often, that it has a one-byte abbreviation (0x0f).  For other addresses, we only need to transmit as much of the address is required for the receiver to discriminate it from all other nodes.  The birthday paradox comes into play here, and means that we typically need about twice the number of bits as the base-2 log of the number of nodes on the network.  For a small network of a few hundred nodes 24 bits (3 bytes) of address is a pleasant over-kill.  Even at a global scale, we need to accomodate around 10 billion addresses = ~2^34 addresses, and so about 70 bits (7 bytes) should be enough.

We also have abbreviation strategies where neighbouring nodes that talk with each other a lot can allocate a one-byte short code for each other, however, as you might be able to guess from the trace that abbreviation method is temporarily disabled in the code to keep my life a little simpler at present -- which is a good move because of the density of new features in the code.

At the end of the trace we see a summary of the overlay routing table which shows 7-digit address prefixes for all know nodes on this network, and the link-scores to each via the various routes known to each.

The scores have two components. The first being a BATMAN-like score derived from beacon counting, although we take into account that the remote node might have different interfaces running at different beacon rates.  The second part is the number of Serval gateways that are on the path.

This gateway count is there to prevent routing loops and other nasties in meshes where the overlay has managed to infer some hierarchy, or where inter-mesh links have been purposely provisioned.

I'll talk about inferred hierarchy in another post, but it is one of several measures we are taking to ensure that a Serval mesh can scale beyond the normal bandwidth-starvation limit imposed by all nodes trying to know about all other nodes all of the time.

Our premise is that you need frequent information for nearby nodes because their "bearing" can change wildly over short time frames, but that for more distant nodes their "bearing" on the mesh should change much more slowly, and so we should be able to cope with less frequent updates about the position of such distant nodes.

But meanwhile, as you can see we are making good progress, and the Serval DNA overlay mesh is beginning to come together.

Making Mesh Networks Scale

Mesh networks have great potential to create sustainable, resilient and low-cost communications capabilities.  This is why we are passionate about mesh networking at Serval Project.

However, the mesh routing protocols that I have seen to date almost all have a scalability ceiling.  This is because if you have 10 devices all talking to each other you get 100 messages, but if you have 1,000 devices all talking to each other you get 1,000,000 messages in the same time.  In computer science we would say that a mesh network has a complexity of O(N^2), because the mesh traffic scales with the square of the number of devices.

Eventually, not matter how fast the links on the mesh, the capacity gets used up.

Even on a "quiet" mesh where most of the devices aren't saying much, they still have to share O(N^2) information, and so the mesh just existing eventually causes it to collapse under its own weight.

What would be nice is a more graceful degradation, so that even in a mesh of say, 7 billion devices, that each local pool of devices could talk to one another, even though it would be impossible to allow all 7 billion to talk to each other.

It might seem pointless to allow a device to see only a few thousand nearby devices, as that represents only about 0.00001% of the devices on such a global mesh.

However, for telephony at least, it turns out that most phone calls are at most a few kilo-metres away, and thus would be possible over such a "local patch" on the global mesh.

So this is something that Serval is planning to do over the next few months.

We are going to take the BATMAN mesh routing protocol and modify it so that it can keep track of "near by" devices on the mesh without being swamped by location information from devices on the other side of the world (which from my perspective is probably you, because I live in Australia, which is on the other side of the world from most other places ;).