How does opportunistic networking move data?

In an ordinary network, a route exists before a message is sent. In an opportunistic network it usually does not. Vahdat and Becker’s paper on epidemic routing starts from exactly this case: a network where there may never be a connected path from source to destination, or where the network is split at the moment the message is created.

What exists instead are contacts: periods when two devices can talk. The delay-tolerant networking architecture (RFC 4838) separates scheduled contacts, agreed in advance for a particular time and duration, such as a link to a low-earth-orbit satellite, from opportunistic contacts, which are not scheduled but present themselves unexpectedly. Its example is a Bluetooth link between a handheld device and a kiosk, which begins when the device is brought near and lasts an undetermined time. Two phones meet in the same way, because their owners happen to walk past each other.

So data moves by store, carry and forward. A device stores the message, carries it while its owner moves, and forwards it when a contact appears. The delay-tolerant networking article covers the wider architecture. The interesting question here is what two devices do in the short time they are together.

Epidemic routing gives the basic exchange. Each device keeps a buffer of messages it originated and messages it carries for others, indexed by a unique message identifier. It also keeps a summary vector, a compact list of the messages it holds.

When two devices come into range, one starts an exchange the paper calls an anti-entropy session:

1. Each device sends its summary vector.
2. Each works out which messages the other holds that it has not seen.
3. Each requests those messages, and the other sends them.

A receiver is free to refuse, for example messages that are too large or destined for certain hosts. To avoid repeating the same exchange, each device remembers whom it spoke to recently and does not start a new session with them until a configurable time has passed.

Each message also carries a hop count that limits how many exchanges it can go through, similar to a TTL. A higher hop count spreads a message faster, at the cost of more copies.

Epidemic routing gives a copy to every device that does not have one. Copies spread through the network the way an infection spreads through a population. The authors show that, given enough buffer space and time, these pairwise exchanges deliver messages eventually.

The cost is resources. Every carrier spends storage, airtime and battery on other people’s messages, and the paper notes that a mobile device must weigh the energy cost of becoming a carrier. Duplicates multiply, so receivers need message deduplication. The paper also suggests delivery acknowledgments, so the sender and carriers can free their copies once the destination has the message.

Spray and Wait, from Spyropoulos, Psounis and Raghavendra, keeps most of epidemic routing’s speed while capping its cost. It has two phases:

• Spray. The source starts with a fixed number of copies, L, and hands them to distinct relays. In the binary version, a device holding more than one copy gives half to each device it meets that has none, and keeps half.
• Wait. A device left with one copy stops spreading and waits to meet the destination itself, a scheme called direct transmission.

The number of copies, and so the number of transmissions, no longer grows with the size of the network. The authors report that it beats the other practical schemes they compared on both delivery delay and transmissions in most of the scenarios they studied.

PRoPHET (RFC 6693), an Experimental RFC, starts from the observation that people and devices do not move at random, so past meetings help predict future ones. Each device keeps a delivery predictability between 0 and 1 for every destination it knows about. Meeting a device raises the predictability for it, the values decay with time between meetings, and they pass on transitively: if A often meets B, and B often meets C, then C is probably a good device to carry bundles for A.

When two PRoPHET devices meet, they first exchange their predictabilities, then information about the bundles they carry, and a device can forward a bundle when the other device has a higher delivery predictability for its destination, keeping its own copy while it has buffer space. The RFC describes this as pruning epidemic routing’s distribution tree to use fewer resources.

All three schemes trade the same things: how fast a message arrives, how many devices carry a copy, and how much storage, airtime and battery that takes. Whatever the routing rule, an app running on an opportunistic network also needs:

• bounded buffers and expiry times, so carried messages do not pile up indefinitely;
• deduplication at every device, because copies arrive by several routes;
• end-to-end encryption and authentication, because messages pass through devices nobody chose.

The epidemic routing paper makes the last point itself: a message may cross an arbitrary path of hosts, and receivers may want to know whether it was exposed, even in encrypted form, to hosts they do not trust.