{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T18:32:20Z","timestamp":1786991540410,"version":"build-2736575974"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/publication-rights-and-licensing-policy"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGCOMM Comput. Commun. Rev."],"published-print":{"date-parts":[[2026,7,1]]},"abstract":"<jats:p>\n                    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\n                    <jats:italic toggle=\"yes\">v<\/jats:italic>\n                    , a node\n                    <jats:italic toggle=\"yes\">u<\/jats:italic>\n                    needs a mail pigeon bred and raised at\n                    <jats:italic toggle=\"yes\">v.<\/jats:italic>\n                    When sending a message using a pigeon to\n                    <jats:italic toggle=\"yes\">v<\/jats:italic>\n                    , node\n                    <jats:italic toggle=\"yes\">u<\/jats:italic>\n                    loses the pigeon. To send another message to\n                    <jats:italic toggle=\"yes\">v<\/jats:italic>\n                    , node\n                    <jats:italic toggle=\"yes\">u<\/jats:italic>\n                    needs another pigeon of\n                    <jats:italic toggle=\"yes\">v.<\/jats:italic>\n                    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.\n                  <\/jats:p>\n                  <jats:p>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.<\/jats:p>","DOI":"10.1145\/3831956.3831958","type":"journal-article","created":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T18:20:36Z","timestamp":1786990836000},"page":"2-9","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["The Carrier Pigeon Internet Protocol: An Algorithmic (and Lighthearted) Perspective"],"prefix":"10.1145","volume":"56","author":[{"given":"Matthias","family":"Bentert","sequence":"first","affiliation":[{"name":"TU Berlin, Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shay","family":"Kutten","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Darya","family":"Melnyk","sequence":"additional","affiliation":[{"name":"TU Berlin, Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tijana","family":"Milentijevi\u0107","sequence":"additional","affiliation":[{"name":"TU Berlin, Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefan","family":"Schmid","sequence":"additional","affiliation":[{"name":"TU Berlin, Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,8,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01302964"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3379486"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-019-00351-5"},{"key":"e_1_2_1_4_1","first-page":"44","article-title":"Revolutionizing Datacenter Networks via Reconfigurable","volume":"68","author":"Avin Chen","year":"2025","unstructured":"Chen Avin and Stefan Schmid. 2025. Revolutionizing Datacenter Networks via Reconfigurable Topologies. Commun. ACM 68, 6 (2025), 44\u201353.","journal-title":"Topologies. Commun. ACM"},{"key":"e_1_2_1_5_1","unstructured":"BBC. 2011. SA pigeon 'faster than broadband'. (2011). https:\/\/web.archive.org\/web\/20110414225332\/http:\/\/news.bbc.co.uk\/2\/hi\/africa\/8248056.stm Accessed: 24\/12\/2025."},{"key":"e_1_2_1_6_1","volume-title":"Winsten","author":"Beckmann Martin J.","year":"1956","unstructured":"Martin J. Beckmann, C. B. McGuire, and Christopher B. Winsten. 1956. Studies in the Economics of Transportation. Yale University Press."},{"key":"e_1_2_1_7_1","unstructured":"Yossi Ben-Bassat. 2025. A New Israeli test confirms: PEI (Pigeon Enabled Internet) is FASTER than ADSL. (2025). https:\/\/web.archive.org\/web\/20080713090722\/http:\/\/www.notes.co.il\/benbasat\/5240.asp Accessed: 24\/12\/2025."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214041"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"370","DOI":"10.1038\/s41893-022-00869-w","article-title":"Material efficiency to tackle the sand crisis","volume":"5","author":"Cao Zhi","year":"2022","unstructured":"Zhi Cao and Eric Masanet. 2022. Material efficiency to tackle the sand crisis. Nature Sustainability 5, 5 (2022), 370\u2013371.","journal-title":"Nature Sustainability"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","unstructured":"B. Carpenter and R. Hinden. [n. d.]. Adaptation of RFC 1149 for IPv6. RFC 6249. RFC Editor. 10.17487\/RFC2549","DOI":"10.17487\/RFC2549"},{"key":"e_1_2_1_11_1","volume-title":"The multidepot vehicle routing problem with inter-depot routes. European journal of operational research 176, 2","author":"Crevier Benoit","year":"2007","unstructured":"Benoit Crevier, Jean-Fran\u00e7ois Cordeau, and Gilbert Laporte. 2007. The multidepot vehicle routing problem with inter-depot routes. European journal of operational research 176, 2 (2007), 756\u2013773."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447347"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/568522.568523"},{"key":"e_1_2_1_14_1","unstructured":"United Nations Environment Programme Edgar E. Guti\u00e9rrez-Espeleta Nyovani Madise Ying Wang Robert Watson Tamiru A. Abiye Ana Paula Aguiar Peter Alexander Barbara Amon Apoorva Arya Ghassem Asrar Lindsay Beevers Medani Bhandari Meena Bohara Gillian Bowser David Broadstock Monday Businge Donovan Campbell Kate\u0159ina \u010cern\u00fd Pixov\u00e1 Lynette Cheah Leila Dagher Vassilis Daioglou Jonathan Davies Mark Elder Parfait M. Eloundou-Enyegue et al. 2025. Global Environment Outlook 7: A future we choose - Why investing in Earth now can lead to a trillion-dollar benefit for all. (2025)."},{"key":"e_1_2_1_15_1","volume-title":"16th annual symposium on foundations of computer science (FOCS)","author":"Even Shimon","unstructured":"Shimon Even, Alon Itai, and Adi Shamir. 1975. On the complexity of time table and multi-commodity flow problems. In 16th annual symposium on foundations of computer science (FOCS). IEEE, 184\u2013193."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1851182.1851223"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings IEEE INFOCOM 2000. conference on computer communications. Nineteenth annual joint conference of the IEEE computer and communications societies (Cat. No. 00CH37064)","volume":"2","author":"Fortz Bernard","year":"2000","unstructured":"Bernard Fortz and Mikkel Thorup. 2000. Internet trafic engineering by optimizing OSPF weights. In Proceedings IEEE INFOCOM 2000. conference on computer communications. Nineteenth annual joint conference of the IEEE computer and communications societies (Cat. No. 00CH37064), Vol. 2. IEEE, 519\u2013528."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2934872.2934911"},{"key":"e_1_2_1_19_1","unstructured":"Graham Greene. 1958. Our Man in Havana. Heinemann."},{"key":"e_1_2_1_20_1","volume-title":"Strengthening Dual Bounds for Multicommodity Capacitated Network Design with Unsplittable Flow Constraints. arXiv preprint arXiv:2512.25018","author":"Greening Lacy M","year":"2025","unstructured":"Lacy M Greening, Santanu S Dey, and Alan L Erera. 2025. Strengthening Dual Bounds for Multicommodity Capacitated Network Design with Unsplittable Flow Constraints. arXiv preprint arXiv:2512.25018 (2025)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060619"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1016\/0016-0032(74)90126-4","article-title":"The Communication Problem on Graphs and Digraphs","volume":"297","author":"Harary Frank","year":"1974","unstructured":"Frank Harary and Allen J. Schwenk. 1974. The Communication Problem on Graphs and Digraphs. Journal of the Franklin Institute 297, 6 (1974), 491\u2013495.","journal-title":"Journal of the Franklin Institute"},{"key":"e_1_2_1_23_1","unstructured":"The highly unofficial CPIP WG. 2001. The highly unofficial CPIP WG. Technical Report. University of Bergen. https:\/\/web.archive.org\/web\/20140215072548\/http:\/\/www.blug.linux.no\/rfc1149\/ Retrieved 24\/12\/2025."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/sapm1941201224"},{"key":"e_1_2_1_25_1","volume-title":"Gpipe: Efficient training of giant neural networks using pipeline parallelism. Advances in neural information processing systems 32","author":"Huang Yanping","year":"2019","unstructured":"Yanping Huang, Youlong Cheng, Ankur Bapna, Orhan Firat, Dehao Chen, Mia Chen, HyoukJoong Lee, Jiquan Ngiam, Quoc V Le, Yonghui Wu, et al. 2019. Gpipe: Efficient training of giant neural networks using pipeline parallelism. Advances in neural information processing systems 32 (2019)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/JRPROC.1952.273898"},{"key":"e_1_2_1_27_1","unstructured":"UNICEF IFAD et al. 2017. The state of food security and nutrition in the world 2017. FAO;."},{"key":"e_1_2_1_28_1","volume-title":"Queueing Systems, Volume II: Computer Applications","author":"Kleinrock Leonard","unstructured":"Leonard Kleinrock. 1976. Queueing Systems, Volume II: Computer Applications. John Wiley & Sons."},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","first-page":"101282","DOI":"10.1016\/j.exis.2023.101282","article-title":"Constructing the global sand crisis: Four reasons to interrogate crisis and scarcity in narrating extraction","volume":"15","author":"Lamb Vanessa","year":"2023","unstructured":"Vanessa Lamb. 2023. Constructing the global sand crisis: Four reasons to interrogate crisis and scarcity in narrating extraction. The Extractive Industries and Society 15 (2023), 101282.","journal-title":"The Extractive Industries and Society"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.3390\/universe7010012"},{"key":"e_1_2_1_31_1","volume-title":"Cristina Susana Zalazar, and Maria Emilia Fernandez","author":"Masin Carolina Elisabet","year":"2024","unstructured":"Carolina Elisabet Masin, Alejandra Duran, Cristina Susana Zalazar, and Maria Emilia Fernandez. 2024. Composting-vermicomposting of pigeon dropping waste: A contribution to the reduction of urban contamination. (2024)."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/633025.633041"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3458817.3476209"},{"key":"e_1_2_1_34_1","volume-title":"Josefine Reimer Lynggaard, and Stephanie Chuah","author":"Peduzzi Pascal","year":"2022","unstructured":"Pascal Peduzzi, Josefine Reimer Lynggaard, and Stephanie Chuah. 2022. Sand and sustainability: 10 strategic recommendations to avert a crisis. (2022)."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3544216.3544265"},{"key":"e_1_2_1_36_1","unstructured":"Hungry Beast Real Human Stories. 2010. Pigeons vs. Australian Internet. url: https:\/\/www.youtube.com\/watch?v=ci2bFFGM8T8. (2010). Accessed: 24\/12\/2025."},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Gr\u00e9gory Salle. 2022. On the 'global sand crisis': From capital accumulation to ecological planning. (2022).","DOI":"10.31389\/jied.123"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2015.2410313"},{"key":"e_1_2_1_39_1","volume-title":"Communication theory of secrecy systems. The Bell system technical journal 28, 4","author":"Shannon Claude E","year":"1949","unstructured":"Claude E Shannon. 1949. Communication theory of secrecy systems. The Bell system technical journal 28, 4 (1949), 656\u2013715."},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","first-page":"100126","DOI":"10.1016\/j.scp.2019.01.003","article-title":"Nutrient recovery from pigeon dropping by using exotic earthworm Eisenia fetida","volume":"12","author":"Singh Sharanpreet","year":"2019","unstructured":"Sharanpreet Singh, Jaswinder Singh, Amandeep Kaur, Jagroop Kaur, Adarsh Pal Vig, and Sartaj Ahmad Bhat. 2019. Nutrient recovery from pigeon dropping by using exotic earthworm Eisenia fetida. Sustainable Chemistry and Pharmacy 12 (2019), 100126.","journal-title":"Sustainable Chemistry and Pharmacy"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"key":"e_1_2_1_42_1","unstructured":"Neal Stephenson. 1999. Criptonomicon. Avon."},{"key":"e_1_2_1_43_1","unstructured":"Google team. 2002. Google PigeonRank. url: http:\/\/www.google.com\/technology\/pigeonrank.html. (2002). Accessed: 24\/12\/2025."},{"key":"e_1_2_1_44_1","unstructured":"BBC News Technology. 2016. Pigeons vs. Australian Internet. url: Pigeon flies past broadband in data speed race. (2016). Accessed: 24\/12\/2025."},{"key":"e_1_2_1_45_1","unstructured":"Niren Tolsi. 2009. Winston the homing pigeon draws tweets of support. url: https:\/\/mg.co.za\/article\/2009-09-10-winston-the-homing-pigeon-draws-tweets-of-support\/. (2009). Accessed: 24\/12\/2025."},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","unstructured":"Paolo Toth and Daniele Vigo. 2002. The vehicle routing problem. SIAM.","DOI":"10.1137\/1.9780898718515"},{"key":"e_1_2_1_47_1","first-page":"109","article-title":"Cipher printing telegraph systems: For secret wire and radio telegraphic communications","volume":"45","author":"Vernam Gilbert S","year":"1926","unstructured":"Gilbert S Vernam. 1926. Cipher printing telegraph systems: For secret wire and radio telegraphic communications. Journal of the AIEE 45, 2 (1926), 109\u2013115.","journal-title":"Journal of the AIEE"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","unstructured":"D. Waitzman. 1990. A Standard for the Transmission of IP Datagrams on Avian Carriers. RFC 1149. RFC Editor. 10.17487\/RFC1149","DOI":"10.17487\/RFC1149"},{"key":"e_1_2_1_49_1","volume-title":"Google Pigeon Protocol. (2014). https:\/\/en.wikipedia.org\/wiki\/Google_Pigeon#:~:text=Google%20Pigeon%20is%20the%20code,local%20listings%20in%20a%20search. [Online","author":"Wikipedia","year":"2025","unstructured":"Wikipedia contributors. 2014. Google Pigeon Protocol. (2014). https:\/\/en.wikipedia.org\/wiki\/Google_Pigeon#:~:text=Google%20Pigeon%20is%20the%20code,local%20listings%20in%20a%20search. [Online; accessed 24-December-2025]."},{"key":"e_1_2_1_50_1","volume-title":"Pigeon post. (2025). https:\/\/en.wikipedia.org\/wiki\/Pigeon_post?utm_source=chatgpt.com [Online","author":"Wikipedia","year":"2025","unstructured":"Wikipedia contributors. 2025. Pigeon post. (2025). https:\/\/en.wikipedia.org\/wiki\/Pigeon_post?utm_source=chatgpt.com [Online; accessed 24-December-2025]."}],"container-title":["ACM SIGCOMM Computer Communication Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3831956.3831958","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T18:20:59Z","timestamp":1786990859000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3831956.3831958"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,1]]},"references-count":50,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,7,1]]}},"alternative-id":["10.1145\/3831956.3831958"],"URL":"https:\/\/doi.org\/10.1145\/3831956.3831958","relation":{},"ISSN":["0146-4833"],"issn-type":[{"value":"0146-4833","type":"print"}],"subject":[],"published":{"date-parts":[[2026,7,1]]},"assertion":[{"value":"2026-08-17","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}