EUVIMEDEUVIMED entdecken
Studienprotokoll

The Carrier Pigeon Internet Protocol: An Algorithmic (and Lighthearted) Perspective

Matthias Bentert, Shay Kutten, Darya Melnyk, Tijana Milentijević, Stefan Schmid

ACM SIGCOMM Computer Communication Review · 01.07.2026 · 56 (2) · 2-9

DOI: 10.1145/3831956.3831958 ↗

Kurz gefasst

Studienprotokoll in der Zeitschrift ACM SIGCOMM Computer Communication Review, online erschienen am 17.08.2026. Verfasst von Matthias Bentert und 4 weiteren Autor:innen. Die Arbeit nennt 50 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Bentert, M., Kutten, S., Melnyk, D., Milentijević, T., & Schmid, S. (2026). The Carrier Pigeon Internet Protocol: An Algorithmic (and Lighthearted) Perspective. ACM SIGCOMM Computer Communication Review, 56(2), 2-9. https://doi.org/10.1145/3831956.3831958

Vancouver

Bentert M, Kutten S, Melnyk D, Milentijević T, Schmid S. The Carrier Pigeon Internet Protocol: An Algorithmic (and Lighthearted) Perspective. ACM SIGCOMM Computer Communication Review. 2026;56(2):2-9. doi:10.1145/3831956.3831958

BibTeX
@article{Bentert2026,
  author = {Bentert, Matthias and Kutten, Shay and Melnyk, Darya and Milentijević, Tijana and Schmid, Stefan},
  title = {The Carrier Pigeon Internet Protocol: An Algorithmic (and Lighthearted) Perspective},
  journal = {ACM SIGCOMM Computer Communication Review},
  year = {2026},
  volume = {56},
  number = {2},
  pages = {2--9},
  doi = {10.1145/3831956.3831958}
}
Kostenlos starten →