Stuff Yaron Finds Interesting

Technology, Politics, Food, Finance, etc.

Thali and the Mesh Mess

Thali's base communication mechanism is Tor hidden services. This enables Thali devices to reach each other regardless of what NATs or Firewalls are in their way in a manner that is resistant to traffic analysis. But what happens when one isn’t on the Internet at all? We still want Thali devices to be able to communicate so a goal has been to support some kind of ad-hoc communication mechanism. That is, if two Thali devices are close enough to reach each other directly via a technology like Wi-Fi or Bluetooth they should be able to communicate securely and privately.
Ideally however we would go a step farther and use a technology that supports ad-hoc mesh networking. We list below some candidates but it is a bit early to jump on the mesh bandwagon. More on that in future articles.
The purpose of this article is to collect information on what appear to be the main players in the ad-hoc connectivity and mesh building contest.
[Note: This is a complete re-write of the existing Mesh Mess article.]

1 Radio Technologies

The following sections look at various radio technologies that are either already widespread or expected to become widespread in the near future. These are all technologies that Thali can leverage to provide connectivity.
Range This is just meant to provide a rough idea for both indoor and outdoor use with non-directional antennas.
Bandwidth Measured in Kb/s
Wavelength This is the size of the signal in inches. This gives one a sense of the size of the associated antenna. Mobile antennas can be anywhere from 1/10th to 1/2 the size of the wavelength. Stationary antennas are often uneven multiples of the signal size unless it’s huge.
Open Source/Open Standard Thali is an open source/open standard project so we need an ad-hoc mesh technology that is as well.
Supports IP We really don’t want to re-invent the Internet so we want an ad-hoc mesh technology that lets us route IP packets. That means it needs to be able to assign local IP addresses, listen for communications, etc. Ideally it would show up as an IP enabled network adapter.
Supported Platforms Thali wants to run everywhere, what platforms typically support this technology?
Supports direct ad hoc connections Enables two devices to talk directly to each other.
Supports discovery Has a mechanism to enable devices within in range of each other to discover each other.
Supports ad hoc meshes Is able to form a mesh for relay routing. Note that there are two distinct flavors of mesh. Low latency meshes are collections of devices that are connected in real time. In a low latency mesh if user A wants to talk to user Z, who is out of radio range, then there has to be, at the moment of the desired communication, some collection of other users standing between A and Z who are willing to relay packets in real time. If no such collection of users exist then the message won’t be delivered. High latency meshes, or opportunistic meshes, are used in situations where the density of devices is too low to support real time communication. In a high latency mesh devices opportunistically copy messages to each other hoping that those messages will eventually be delivered. For example, Joe wants to send a status update on a work item to Jane in an area like a factory with no Internet infrastructure. Joe’s device doesn’t see Jane’s device but does see Joseph’s. So Joe’s device asks Joseph’s device to take a copy of the message and if it ever sees Jane then pass it on. Joseph’s device might then give a copy to Jake’s device. If eventually Joe, Joseph or Jake see Jane’s device then the message will be passed on.

1.1 Wi-Fi Infrastructure Mode

Range Typically 300 ft indoors. Outdoors a range of a mile is not out of the question if there is direct line of sight. Longer distances are possible under good circumstances and with highly directional antennas.
Bandwidth This is all over the map depending on which variant of Wi-Fi is used. Anywhere from a low of 11 Mbps to a high of 1.3 Gbps.
Wavelength 4.92 inches (2.4 GHz) & 2.36 inches (5 GHz)
Open Source/Open Standard Near as I can tell you can’t even get the spec without paying $99. There do appear to be open source Wi-Fi drivers though.
Supports IP Yes
Supported Platforms Everything
Supports direct ad hoc connections Yes. A device can put itself into mobile hotspot mode (or similar names) where essentially it acts as a Wi-Fi Infrastructure access point and then other devices can connect to it. See the mesh section below for limitation.
Supports discovery Yes, it’s possible to enumerate local networks so long as they are advertising themselves. This can be used for discovery. I’m not completely sure what the battery implications of this are if one just leaves Wi-Fi on purely for discovery purposes. Also see limitations to being a mobile hotspot below.
Supports ad hoc meshes There is no native support for forming meshes. In theory one could use Wi-Fi Infrastructure mode as part of a mesh structure but only if at least some devices have other connectivity options. The problem is that if a device (think iOS 7) only supports normal Wi-Fi Infrastructure mode (and not say, Wi-Fi direct) then when it is connected to a Wi-Fi Infrastructure access point that is the only Wi-Fi access point it can talk to. Similarly when a device puts itself into Wi-Fi Infrastructure mode (e.g. mobile hotspot) unless it supports some other communication mechanism then it can only communicate with nodes that have connected to its mobile hotspot. So it is not possible to form a low latency mesh out of just Wi-Fi Infrastructure devices as one can’t form a chain, only a hub and spoke. One could potentially create a high latency mesh though. And often devices have multiple radios so it’s possible in some circumstances to use Wi-Fi Infrastructure mode as part of an over all mesh building strategy.

1.2 Wi-Fi Direct

Range Typically 300 ft indoors. Outdoors a range of a mile is not out of the question if there is direct line of sight.
Bandwidth This is all over the map depending on which variant of Wi-Fi is used. Anywhere from a low of 11 Mbps to a high of 1.3 Gbps.
Wavelength 4.92 inches (2.4 GHz) & 2.36 inches (5 GHz)
Open Source/Open Standard If you aren’t a member of the Wi-Fi Alliance then it costs $99 just to see the Wi-Fi Direct specification. There are open source implementations of wi-fi direct though but I’m not sure how they pulled that off. It’s also not clear what the costs are to implement or if only hardware manufacturers have to pay. It’s confusing.
Supports IP Yes
Supported Platforms Recent releases of Android, Linux and Windows. OS/x and iOS do not appear to support it. Note that the hardware in the device also needs to support it so just having the right OS isn’t enough.
Supports direct ad hoc connections Yes, sorta. The whole point of Wi-Fi direct is to enable ad-hoc connections. But the Wi-Fi Direct standard apparently requires that a user confirm accepting a Wi-Fi Direct connection. So automated ad-hoc connections aren’t possible without direct user intervention. We are going to run experiments to see if the user dialog is needed for repeat connections and if we can maintain group IDs. But the inability to automatically make connections is a real problem.
Supports discovery Yes, Wi-Fi Direct groups can advertise their SSIDs like any other Wi-Fi access point and that can be used for discovery.
Supports ad hoc meshes There is no built in support for meshes. But unlike Wi-Fi Infrastructure mode a device can simultaneously be a member of multiple Wi-Fi Direct groups and so Wi-Fi Direct can be used to create even low latency meshes if one wants. Wi-Fi direct is also backwards compatible with Wi-Fi Infrastructure mode so in theory a normal Wi-Fi Infrastructure mode client could connect to a Wi-Fi direct group but the groups are required to have access passwords and the user would have to get that password before they could join. There are work arounds, of course, such as well known passwords or supplying passwords over a different transport.

1.3 Wi-Fi Aware (aka Neighbor Awareness Networking (NAN))

Range The information I can find online is astoundingly useless. It is designed just for discovery (ala BLE) but I can’t find anything on range, frequency, etc. But an article from Broadcom implies it is based on 802.11ac which would argue for the same range as Wi-Fi.
Bandwidth No clue, but it’s clearly just for discovery and meant to trigger the use of other technologies like Wi-Fi Direct.
Wavelength Don’t know for sure but if it’s 802.11ac then see above.
Open Source/Open Standard It costs $200 just to see the technical specification draft! So no, not open.
Supports IP Probably not
Supported Platforms I don’t know.
Supports direct ad hoc connections It’s intended as a discovery protocol but that’s about it, so I’m guessing only tiny bits of data can be sent.
Supports discovery That is it’s point in life.
Supports ad hoc meshes It may be amenable to some of the mesh hacks used on BLE but that isn’t it’s purpose.

1.4 Wi-Fi 802.11ah/900 Mhz

Range The target outdoors is around one-kilometer. For indoor we would expect improvements over high frequency wi-fi to be between 3x - 10x (e.g. 1000 ft to 3,000 ft) depending on bandwidth.
Bandwidth 26 channels, each channel has roughly 100 Kb/s
Wavelength 13.11 inches in (900 MHz) Note that spectrum in and around 900 MHz is available throughout most of the world. The big exception that I’m aware of is China where this standard will apparently run in various slices of 40 inches (300 MHz), 30 inches (400 Mhz) and 15 inches (780 Mhz) ranges.
Open Source/Open Standard Like other Wi-Fi standards it is pay to play. It also hasn’t actually been standardized yet. The standard is expected to be finalized in 2016.
Supports IP Yes
Supported Platforms Unknown
Supports direct ad hoc connections Yes, endpoints can connect directly to each other with one playing access point and the other playing client.
Supports discovery Stations can advertise themselves, so yes.
Supports ad hoc meshes There is the concept of a relay built directly into the standard but it’s not clear if the resulting topology is hub and spoke or a mesh.

1.5 Wi-Fi 802.11af/Whitespace

Range The general goal is to reach at least a Kilometer and given the low frequencies that would apply both indoor and outdoor. But there are various restrictions on its use in order to prevent collisions with existing channel users. In rural areas in the US the FCC allows powerful enough transmitters to cover 10 or 11 miles.
Bandwidth Each channel, depending on frequency, carries between 26.7 Mb/s and 35.6 Mb/s and up to four channels can be bonded to give an overall bandwidth of between 426.7 Mb/s and 568.9 Mb/s. Data rates can be lowered all the way down to 1.8 Mb/s in order to get longer range at low power.
Wavelength Uses TV VHF and UHF frequency bands so somewhere between 18 ft (54 MHz) and 15 inches (790 MHz)
Open Source/Open Standard Typically Wi-Fi pay to play.
Supports IP One assumes.
Supported Platforms Unknown
Supports direct ad hoc connections Yes
Supports discovery Without having read the standard I’m not sure but I’m going to guess since it’s a 802.11 family standard that it works like its brethren and supports advertising access points.
Supports ad hoc meshes As with 802.11ah it’s not clear if there is built in support for any kind of mesh infrastructure.

1.6 Bluetooth

Range 330 ft
Bandwidth Starting with Bluetooth 3.0 maximum throughput is 24 Mbps
Wavelength 4.92 inches (2.4 Ghz)
Open Source/Open Standard I haven’t investigated this enough. It sorta looks like if you just don’t actually use the Bluetooth logo you could at least implement software compliant with the publicly available standards for free. I strongly suspect that there is a fee to implement the hardware due to some kind of group licensing consortium.
Supports IP Sorta. There is a native serialization protocol that looks kind of like TCP but is not. So we can’t just drop a Bluetooth server socket into an HTTP server and expect anything to work. However they do support streams so we could probably hack up something. There is a profile for Bluetooth called Personal Area Network (PAN) that does support IP but it’s not supported on all platforms.
Supported Platforms Everything
Supports direct ad hoc connections In theory no because two Bluetooth devices are really only supposed to communicate when paired. But Android at least supports communication between unpaired Bluetooth devices.
Supports discovery Yes but not in a way that is useful for us. Typically there is a high power dedicated discovery mode that the user has to put the device into. Most devices limit how long one can stay in this mode. There is a sorta work around with Android where if one knows the Bluetooth UUID of the other device it’s possible to scan for its presence without going into high powered discovery mode.
Supports ad hoc meshes There is no protocol support for it but it’s certainly possible to connect to multiple bluetooth devices at once so it’s in theory possible to build a mesh.

1.7 Bluetooth Low Energy (BLE)

Range 330 ft
Bandwidth In practice 35 KB/s, the raw bandwidth is 1 Mb/s per channel and there are 40 channels but in practice most BLE systems only support communicating over one channel. BLE 4.2 is supposed to support larger packet sizes, currently the data load is 20 octets, which should increase effective throughput from an application perspective (e.g. get closer to the theoretical 1 Mb/s limit per channel).
Wavelength 4.92 inches (2.4 GHz)
Open Source/Open Standard I haven’t investigated this enough. It sorta looks like if you just don’t actually use the Bluetooth logo you could at least implement software compliant with the publicly available standards for free. I strongly suspect that there is a fee to implement the hardware due to some kind of group licensing consortium.
Supports IP No. There are proposal for an IP based PAN over BLE but I’m not aware of it being widely supported although it is officially part of BLE 4.2.
Supported Platforms Everywhere.
Supports direct ad hoc connections Yes. It’s possible to communicate over BLE without pairing.
Supports discovery This is pretty much BLE’s purpose in life. It provides a super lower power discovery mechanism to exchange small bits of data.
Supports ad hoc meshes In theory yes but the data rate is so low that it doesn’t seem likely. A more plausible use is to use BLE to negotiate a different channel like Bluetooth or Wi-Fi.

1.8 ZigBee 900 Mhz

Range Apparently up to 2 miles depending on lots of variables.
Bandwidth 915 MHz is available with 40 Kb/s, this falls to 20 Kb/s for the 868 Mhz band in Europe. In the US there are apparently at least 5 bands available so in theory if one had 5 antennas one could send 5 times the data rate.
Wavelength 13.11 inches (900 MHz)
Open Source/Open Standard It’s based on an IEEE standard but I noticed that you can’t download the spec without registering.
Supports IP Yes.
Supported Platforms Not many. One has to buy specialized hardware and then get drivers for it.
Supports direct ad hoc connections I’m honestly not completely sure. It’s not clear to me how long it takes for a new node to join a ZigBee network. ZigBee can run in a variety of configuration including coordinator mode with pre-provisioned keys, coordinator mode with real time discovered keys and coordinator free mode. The mode will determine how long it takes a new device to join an existing network. But I have no idea what the timings look like. But I suspect it’s at least theoretically possible to just jump on an existing unsecured network without even talking to the coordinator. So ad-hoc connectivity should work.
Supports discovery Yes, but see above. Discovery is handled by announcements which are flooded through the network but one has to first be on the network to send the announcements. ZigBee also supports devices that go to sleep and periodically ping to remind the network they are still there.
Supports ad hoc meshes ZigBee supports forming meshes as part of its protocol but it seems like a coordinator has to be involved. Although I’m honestly not completely sure. I’m also not clear what happens if the coordinator goes down. Is another coordinator allowed to step in? How do they deal with network splits?

1.9 goTenna

Range In densely populated areas between 0.5 - 1 mile up to 6 miles in the best circumstances.
Bandwidth 35 Kb/s (it uses BLE to connect the goTenna device to the phone so bandwidth can’t be higher than BLE supports)
Wavelength 78 inches (151-154 MHz)
Open Source/Open Standard Completely proprietary
Supports IP Here’s a better question, can you use it with anything other than their software? In other words, is this an app or a platform? Given that they say they are going to release an SDK one presumes there will be some kind of API. But it would appear that this is a centrally managed and completely closed platform.
Supported Platforms iOS and Android
Supports direct ad hoc connections That’s the idea, especially since it’s low power.
Supports discovery Yes.
Supports ad hoc meshes No. Apparently there are FCC regulations that explicitly prevent them from storing and forwarding messages so right now they are looking at point to point only. Obviously a devious SDK writer could do something naughty and build a mesh on top.

2 Mesh stacks

There are a number of projects that are trying to build meshes on top of existing radio technologies. Here is a sampling.

2.1 Serval

Serval is a project to enable phones to use wi-fi (and ISM 915 Mhz via dedicated extenders) to build meshes for voice, pictures, web, etc. It’s mostly focused on disaster recovery and providing services in under served or outrageously expensive areas. Serval can run over Wi-Fi Infrastructure as well as Wi-Fi ad-hoc on Android devices. Note however that an Android phone can only act as a mesh relay (via Wi-Fi Ad-hoc) if it has been rooted. Serval’s magic is that if you have a bunch of rooted devices or extenders then you can build a mesh automatically.

2.2 OpenGarden

Because of their successful app FireChat they get a lot of attention but their website is less than informative. The only thing I know for sure is that at the time I wrote this is that their SDK is not yet available and what little code they have released is GPL v3.

2.3 Commotion

This is a project to build metro area scale ad-hoc mesh wireless networks. Right now the project looks to be in extremely early stages and is not ready for anything like prime time (I know the feeling). They do use Serval for their key distribution but I’m not exactly clear on the relationship since they just talk about Serval in the context of crypto but Serval is its own stand alone mesh system. So do they use a mesh to handle keys for their mesh? Or are they using something more limited? It’s hard to tell.

3 Other relevant technologies

This is a grab bag of other technologies that seem to read on the mesh problem.

3.1 AllJoyn

It took awhile to figure out but it seems the real docs for AllJoyn are here. AllJoyn came up because it provides essentially the same features as UPnP. That is, a way for devices to discover, connect and control each other. Alljoyn provides a set of standard APIs which can in theory be plugged into lots of transports. So it’s theoretically possible to perform device discovery over BLE or Bluetooth or Wi-Fi or whatever. AllJoyn doesn’t exactly support forming meshes (it assumes there is an existing transport that handles that) but it is intended to allow for discovery and ad-hoc connectivity. It has its own set of protocols and could in theory be plugged into other protocols as well.

3.2 Simple Service Discovery Protocol (SSDP)

This is part of UPnP and is an IP Multicast based service discovery protocol.

3.3 Multicast DNS (mDNS)

This is an IETF standard and uses IP Multicast to provide self organizing DNS capabilities.

3.4 Chrome Copresence

This appears to be a software API for discovering nearby devices. There is an unverified belief that this is a replacement for Bump, the app Google purchased and that it will somehow support a non cruddy story for talking to iPhones. It might also be a Unicorn. We’ll have to wait to find out.

A Wait, isn’t a direct (or mesh) connection a traffic analysis bonanza?

Sorta. So right now our wireless devices, especially Wi-Fi, use fixed MAC addresses (although under an extremely limited set of circumstances, iOS 8 will send out randomized MAC addresses). This provides a constant ID that can be used to follow us around. But unless there is extra data to associate that MAC address with an identity then it just says “I’ve seen this person before” but not “This is Joe”. If Thali were to do something obvious like advertise a user’s public key as part of mesh discovery then we would not only have a fixed ID like a MAC address but we would be taking it further by using an ID that presumably can be easily associated with an identity. It would be the moral equivalent of doing discovery via email address or SSN. Obviously, a bad idea.
So we will have to use a different approach.
There are a couple of approaches to deal with this situation. First, we can decide to not do worse but not do better. If we assume that MACs are going to stay static then we don’t need to worry about using the same ID. We just have to worry about using an ID that isn’t immediately mappable to a user’s primary key. We could do something as simple as create a second public key to advertise that is only used in mesh and communicate that to friends and such. This is easy and cheap and reduces the problem back to MACs.
But I am hoping we will start to see MAC addresses changed randomly. There are reasons why this can hurt but it’s necessary if we are to pass the security laugh test (along with the ability to completely change how cell phones work, but that’s another story). Once this happens then the mesh ID for Thali would become a security hole, not a feature because we would be re-introducing a constant ID.
So this leads to the second approach. In theory we could try some fun games. For example, imagine that someone has 500 people in their address book. They could advertise their public key 500 times, each time encrypted with the public key of their friends. Of course you don’t want to advertise who your friends are. So what you would actually do is your identity with each of your friend’s public keys but not include any of the headers to identify which public key you used to encrypt the value. The result? Everyone else in the mesh network would need to slurp up the 500 keys you just published and then try to decrypt each and every key to see if any of them use their key. Now multiply that by how many people are on the network. This isn’t impossible btw. Say 500 addresses per user * 1000 users on the local mesh = 500,000 keys to test. Today that’s a bit much for a phone but in a year? Two years? Computing is growing vastly faster that human scale. Pretty much anything on human scale is going to be squashed by computing available. So maybe this kind of brute force approach makes sense?

B The non-contenders

The following are technologies that I don’t think are good contenders for our communication needs. We record them here so we can remember why we thought what we thought.

B.1 Near Field Communication (NFC)

Range 3.9 inches or less but in practice devices have to physically touch and touch in exactly the right place (where the antennas are) or it doesn’t work. This makes NFC very finicky in practice.
Bandwidth 106 Kb/s - 424 Kb/s in theory but in practice was really intended for tiny messages
Wavelength 870 Inches (13.56 MHz) - but given the tiny range actual antennas will be tiny
Open Source/Open Standard There is a patent pool so presumably it’s pay to play.
Supports IP Not really.
Supported Platforms Most phones
Supports direct ad hoc connections Yes
Supports discovery Yes but the small distances make discovery kind of a given.
Supports ad hoc meshes No.

B.2 Wi-Fi Ad-Hoc Mode

This isn’t really a contender but it’s going to cause enough confusion with Wi-Fi Direct that it’s worth calling out the differences. Wi-Fi Ad-Hoc Mode is part of the original Wi-Fi standards which contained two basic modes - infrastructure and ad-hoc. Most folks are used to infrastructure mode where there is a single access point that everybody connects to and all communication goes through that single access point. In ad-hoc mode it’s possible to set up peer to peer connections but a lot of key wi-fi features are missing.
  • There is a speed limitation of 11 Mbps.
  • There apparently is no signal strength monitoring.
  • There is no standard discovery story.
  • The security story is WEP although Windows 7 supports WPA2
  • A Wi-Fi adapter can be in infrastructure or ad-hoc mode, but not both. With Wi-Fi direct it’s possible for an adapter to be in infrastructure mode and simultaneously accept Wi-Fi Direct connections. So one can be both connected to the Internet and using Wi-Fi Direct.

2 Responses to Thali and the Mesh Mess

  1. You brushed off Commotion far too quickly. It’s not “based on Serval”, it’s primarily OLSRd on top of an Ad-Hoc network (but they also provide an Infrastructure network for legacy clients).

    Give it a second look.

  2. Administrator says:

    Thanks for the suggestion! I did take another look and updated the article accordingly. Do you think I did right by Commotion?

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>