Training AI models requires sending large amounts of data between machines. For that, having efficient communication is essential. A lot of research in machine learning and distributed systems goes into building faster networks and finding smarter ways to use them. In a recent paper, we tried a different kind of network: Carrier pigeons.
From the Internet to pigeon post #
The idea is older than you might think. On 1 April 1990, RFC 1149 described how to send IP packets by ‘avian carrier’. Although it was an April Fools joke, people have actually tried it, and in a few publicized races a pigeon carrying a memory card beat a slow broadband line.
But behind this unusual idea lies a fundamental networking problem. Modern data centres use optical switches to reconfigure their links based on the communication demand. This raises the question of how to do the reconfiguration efficiently. Another related area is temporal graphs, where connections are available only at certain times, so their order determines which messages can be delivered.
These questions also arise when designing a pigeon network. While RFC 1149 describes how to transmit data using pigeons, it does not explain how to organize their flights efficiently. So, in our work “The Carrier Pigeon Internet Protocol: An Algorithmic (and Lighthearted) Perspective”, we investigated how to design such a network using as few pigeons as possible.
A carrier pigeon is special because it flies home, to the location where it was bred and raised**.** Suppose we want to send a message from TU Berlin to Technion in Haifa. We would need a pigeon that was born at Technion, brought to TU Berlin, then released to fly home carrying our message. Then, once the pigeon arrives at Technion, it cannot simply be reused to carry another message from TU Berlin. We would need another pigeon. Unlike cables, a pigeon is used up every time it carries something. So we asked: If we actually ran a pigeon network, how many birds would we need and where would we raise them?
To study this question, we modeled the communication requirements as a directed graph, where nodes represented locations and edges represented messages that must be delivered. The task was to decide where pigeons should be raised, where they should be placed and how their flights should be scheduled, in order to minimize the total number of pigeons required. Messages at remote locations could be held as long as needed and combined for a later flight.
We looked at three versions of the problem:
- Single-hop. Every message flies directly from its source to its destination.
- Two-hop. A message can stop at one intermediate location, where it is combined with other messages before it is sent on.
- Multihop. A message can pass through any number of intermediate locations.
Allowing stopovers saves a lot of pigeons. On the other hand, this also made the problem much harder to solve.
Results #
In the single-hop case, we needed exactly one pigeon for every source-destination pair. While this is optimal, the number of pigeons quickly became very large. For example, if 20 locations want to communicate with each other, it would take 380 pigeons.
As soon as messages can have a stopover, finding the best solution is NP-hard. We provided reductions from 3SAT and Vertex Cover for both two-hop and multihop cases.
Fortunately, we still found good solutions efficiently. Our paper proposed the Coordinator algorithm, which chooses the location with the most links as a coordinator. Then, every source sends a message to the coordinator. The coordinator sorts them by destination and sends one pigeon to each destination. In the example with 20 locations, this reduced the number of pigeons from 380 to 38. We needed 19 pigeons to collect all messages at the coordinator and another 19 to distribute them to their destinations. We proved that the Coordinator algorithm never uses more than twice as many pigeons as the optimal solution and that it runs in polynomial time. For exact optimum on small instances, we also gave integer linear programs for the two-hop and multihop case.
Open problems #
To keep the model simple, our pigeons could carry unlimited amounts of data. A natural next step is to investigate what happens when pigeons have limited carrying capacity. We also only counted pigeons, not time. Fewer pigeons usually means more stopovers, and every stopover adds delay, so the network with the fewest pigeons may be a slow one. Moreover, one may consider the energy footprint of transporting pigeons to their remote nodes. That costs money and energy, and birds headed to the same place could share a ride. Finally, we assumed that all messages are known in advance. In practice, demands arrive over time, either according to a known process or adversarially.
Behind the paper #
While our research was light-hearted, it has applications to real-world problems. We mentioned predictable data centre network traffic, like AI training, with optical switches that rewire links to match expected traffic. In fact, many optimization problems in communication rely on demand matrices, including traffic engineering. Outside of networked communication, demand-aware graphs, like the one we used to optimize pigeon traffic, are used to figure out how to route vehicles and commodity flows. A lot can still be learned from the travels of the humble carrier pigeon.
Tijana Milentijević is a PhD student at TU Berlin. Her research lies at the intersection of machine learning and distributed systems, with a focus on robust federated learning and distributed algorithms.
This work was co-authored by Matthias Bentert, Shay Kutten, Darya Melnyk, Tijana Milentijević and Stefan Schmid at TU Berlin and the Technion.
The views expressed by the authors of this blog are their own and do not necessarily reflect the views of APNIC. Please note a Code of Conduct applies to this blog.