This is an idea for a type of Wi-Fi mesh network that is resilient to devices joining and leaving, and allows networks to break into fragments when they get out of range and merge again when they come back in range. I just recently realized that this would also work for a wired network, in case anybody wants to make an overengineered ad-hoc wired network for some reason.

I invented this a year and a half ago, inspired by a mesh network project someone else was doing that used a different architecture. I posted it as a comment on a project log post of that project ([link]), but didn't think to post it here. One of the people behind that project replied to my comment and said he thought it could be good. That [link]ed project log post outlines their idea of how to accomplish this sort of thing, so read that if you want context for my idea.

My idea uses DHCP as the mechanism for managing the network. This might require the addition to DHCP of another message type beyond DORA, or maybe (preferably) the heartbeat messages I describe could be worked into existing lease renewal messages, with either very short leases or renewal much more frequently than the lease duration would require.

I wrote it with IPv4 in mind; requiring IPv6 could help with address conflicts, especially on large networks. I'm not yet sure how NAT could be implemented (though it probably wouldn't be too difficult, and I will probably add it at some point), so currently, each participating device has to get a public IP address if the network is to be connected to the Internet. (This means that there needs to be some kind of flag so that all participating devices know not to bridge between the mesh network and the Internet if any of the IP addresses used internally are not usable public addresses. In other words, if a network is founded without a list of public IP addresses to assign, it can never connect to the Internet, until I either add NAT or invent some protocol to get a list of allocable public IP addresses and reassign them to all participating devices. Such a flag could even be attached to the SSID so that Internet-connectable networks and non-Internet-connectable networks with the same name don't try to merge. But better to just figure out how to add NAT.)

I have not yet considered how to add security to this kind of network, but I will. Suggestions are welcome.

Original writeup follows, with a couple of added notes in [brackets].

------

The network must always have a certain number greater than one of active DHCP servers. Rather than allocating addresses directly out of the pool of available addresses, they each maintain a short list (~5?) of reserved addresses to allocate from, which the other DHCP servers will not allocate from, because their short lists will not contain those addresses. This guarantees that no address will be allocated to multiple devices by different DHCP servers. Every DHCP server knows the addresses of the others and exchanges heartbeats with them, synchronizing the lease file and refilling their short lists from the general pool of available addresses. They also need to sync their short lists to keep them mutually exclusive (or just sync the pool, but conflict resolution might be harder that way, and it’s more data to sync if sunc in full). There will have to be a conflict resolution method for refilling the short lists, but I think it would be a lot easier to do that than try to resolve conflicts between addresses after they've been allocated. It could be as simple as both DHCP servers that claimed an address from the pool waiting a random amount of time, and whichever one reacts first gets the contested address to add to its short list, and the other one claims a different address. If there are no addresses left in the pool to add to the short lists, the DHCP servers keep allocating addresses from their short lists until they run out. When they run out, they will no longer respond with address offers to joining devices’ discovery messages. In this way, the joining device is guaranteed to get an address even if the nearest DHCP server to it doesn’t have one to allocate.

If there are too few DHCP servers on the network, the existing ones will ask another device to become a DHCP server. They should probably pick a device as far away from them on the mesh as possible so that the distribution of DHCP servers on the mesh is more uniform. If there are too many, then they pick one to deactivate, at which point it becomes just another device on the network. In this case, they should probably pick the one nearest to the rest, for the same reason. If using a routing algorithm that doesn’t allow full knowledge of the network, such as BATMAN, they can each pick a device to activate/deactivate as a DHCP server and decide by a vote. (BATMAN hardly allows any knowledge of the layout of the network, so latency should probably be used as the metric in this case.)

A device joining the network will, as usual, send out a discovery message looking for DHCP servers. At least one will respond, and the joining device will then have to choose which one to use—the easiest thing to do would be to simply choose the first one to respond, because it’s probably closest. The others can be ignored, because if they don’t receive address requests back from the joining device, they won’t allocate the addresses they offered. The device that just joined will then remember which DHCP server gave it its address and exchange heartbeats with that DHCP server. These heartbeats include a list of the other DHCP servers' addresses. If a device notices a lack of heartbeat from its associated DHCP server, it will assume that DHCP server has gone offline suddenly and reassociate with a different one (because it knows all of their addresses), keeping the same address it already had. If a DHCP server notices a lack of heartbeat from any of its associated devices, it will first ask the other DHCP servers if that device is now associated with any of them, and, if not, add that address back to its short list (if the short list isn’t full) or to the general pool. If any device cannot contact any DHCP server, it assumes there are none left on the network (or that it’s founding a network) and becomes one. This, according to what has been discussed so far, would result in every remaining device becoming a DHCP server. [I no longer know why I thought this would happen.] Then they can then decide which ones to deactivate. With network IDs and the resulting merging process, described below, each device would still become a DHCP server, but would create its own network fragment. These fragments would then re- merge. This results in an extremely resilient network.

If a DHCP server goes down from the perspective of the other DHCP servers, they should first attempt to contact the devices it allocated addresses to, to see if any of them can still contact it. [How do they know which devices were associated with it?] If so, then messages can just be routed via them. (If the mesh routing works well enough, this would happen without them even noticing.) If it can't be contacted, the other DHCP servers ask all of the devices that previously belonged to the downed one to reassociate with another DHCP server, again, using their existing IP addresses. (If some of them are not contactable, but continue to be in contact with their DHCP server, this just becomes a separate network.) If necessary, the remaining DHCP servers then ask another device on the network to become a DHCP server, as described above, to replace the lost one. Also, for optimization, it might be good to have devices automatically reassociate with different DHCP servers if the network topology changes to bring them closer together. There should be some hysteresis, though, to keep them from switching back and forth quickly.

What about merging networks? Well, what triggers a merger? Obviously, two distinct networks coming into range of each other. There are two cases for this: case 1, where some IP addresses are allocated to a device on each network, and case 2, where the networks don’t have any allocated IP addresses that overlap. In case 2, the most obvious way to detect proximity of another network is to detect that the destination IP address on a received packet isn’t allocated on the current network. However, this won’t necessarily work for case 1, and it isn’t reliable even in case 2. An analogous detection method for case 1 is receiving a packet from one’s own IP address, or receiving replies from two other devices in response to only one message being sent. This, however, is also unreliable. Therefore, we can discount this detection method. In case 2, it might be possible for the networks to merge passively, using their other synchronization and conflict resolution methods to bring all of the DHCP servers into agreement. However, the situation could easily transition to case 1 during the merger, causing more difficult conflicts.

Therefore, I think it’s necessary for each network to have an ID of some sort, agreed upon and distributed to the other devices by the DHCP servers. This could be a UUID or a traditional SSID. This ID would facilitate reliable detection of two networks coming into range of each other.

In the case of using an SSID, any device receiving a packet with an SSID on it that doesn’t match that of the current network would notify its DHCP server, which would initiate a merger. However, if the SSID is the same, as would be the case if the network broke in two and then came back together, no such notification would be sent. In this case, there could be IP address conflicts, so passive merging might not be reliable. Therefore, an SSID alone is not sufficient to avoid conflicts. However, an SSID has the advantage of being human-readable.

The advantage of using a UUID is that there could not be a case where the two network[ fragment]s think they’re one, so there could be no passive mergers, and so no unnoticed IP address conflicts. With UUIDs, a breakaway network[ fragment]’s DHCP server(s) would create and propagate a new UUID for the new network fragment as soon as it notices the break. (Only a fragment composed of a majority of the previous network could keep its current UUID, because only it would be able to know that there was no larger fragment resulting from the break.) Therefore, whenever a network loses a DHCP server (without that DHCP server telling the others it’s about to go offline and telling its associated devices to reassociate), a new UUID might need to be created for the remainder of the network. This leads to the idea of using not a UUID but instead some kind of hash of the active DHCP servers’ MAC addresses. (Such a hash might also be useful to enable joining devices to authenticate the DHCP server that offers them an address. I haven’t really thought about that.)

Therefore, I think it’s necessary to use both types of ID. The SSID would be the human-readable network name, enabling users to choose a network to join, and enabling multiple distinct networks to operate in the same geographical area without attempting to merge. The UUID or DHCP server MAC address hash would identify every network fragment uniquely to facilitate reliable detection of the necessity to merge. With both types of ID being used together, networks would merge when their SSIDs are the same but their UUIDs/hashes are different.

Now we come to the actual process of merging. Once the two fragments discover that they share an SSID but not a UUID/hash, they will know that they need to merge. Their DHCP servers will set up provisional communications via whatever edge nodes happened to come into range of the other network. Once this is in place, their DHCP servers can negotiate which DHCP servers to deactivate and which to leave active, and then create and propagate a new UUID/hash for the new combined [network], and synchronize the DHCP leases and short lists. To resolve address conflicts, they will choose one device to keep its address and one to switch to a different address based on some factor such as relative traffic volumes. [Presumably I wrote that to minimize ARP traffic, though either way, all devices on the same fragment as whichever one gets a new address will have to learn their peer's new address and will be sending mis-addressed messages until that happens. This might require a 'push' version of ARP so the DHCP servers can propagate the new address association; this could probably be included in the heartbeat messages.] DHCP servers should probably get priority over other devices to keep their addresses. If there are too many devices to merge the fragments without address conflicts, they will not merge, or some kind of subnet thing will happen. [I now realize that this would require something like NAT, internal to the network. Of course, it's not a problem if using a sufficiently large pool of IP addresses.] If the UUID or hash of either merging fragment happens to change during the merger process (e.g. by one of the fragments breaking or merging with a third fragment), then the merger should be aborted and retried. In this way, all fragments in the area with the same SSID will eventually merge.
-- notexactly, Dec 04 2015

Project log post mentioned at the top https://hackaday.io...-address-allocation
[notexactly, Dec 04 2015]

I tried very hard to bake more-or-less this, with a few more tricks, about ten years ago.

Technically, it worked. We'd have covered Bombay and Rajkot with it in short order, if the pair of psychopaths I went into business with hadn't had other ideas.
-- Wrongfellow, Dec 10 2015


I'm thinking chicken wire. Just need a conductive bit on the mobile phone, then stick it against the chicken wire to make a callcall.
-- not_morrison_rm, Dec 11 2015



random, halfbakery