The Carrier Pigeon Internet Protocol: An Algorithmic (and Lighthearted) Perspective
This is a playful but rigorous theoretical contribution to network design, though its practical impact is limited due to the whimsical premise.
The paper formalizes the pigeon post as a network link layer and designs algorithms to minimize pigeon usage for communication demands. It shows singlehop is simple, while 2-hop and multihop are NP-hard, and provides a 2-approximation algorithm for the latter.
The theoretical model behind the pigeon post as a link layer in a communication network was introduced by Shannon (under the guise of studying One-Time Pads for cryptography). That is, to send a one-hop message to $v$, a node $u$ needs a mail pigeon bred and raised at $v$. When sending a message using a pigeon to $v$, node $u$ loses the pigeon. To send another message to $v$, node $u$ needs another pigeon of $v$. It has been demonstrated that the communication bandwidth achievable with pigeon post can exceed that of networks using other media. This has already motivated the introduction of Internet standards that allow the use of pigeons as Internet link-layer media. In this paper, we begin to fill in the missing piece: designing algorithms for breeding and scheduling pigeons to meet a given communication demand efficiently, minimizing the number of pigeons required. We consider singlehop, 2-hop, and multihop pigeon use. While the singlehop variant admits a simple characterization, both the 2-hop and the multihop variants are NP-hard. For the latter variants, we present a polynomial-time algorithm based on demand aggregation that achieves a 2-approximation for the number of pigeons used. We believe that this pigeon-based perspective offers both amusing and instructive insights into network design and hopefully, into ornithology.