{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T07:25:25Z","timestamp":1774077925617,"version":"3.50.1"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"CoNEXT3","funder":[{"DOI":"10.13039\/501100001659","name":"German Research Foundation","doi-asserted-by":"crossref","award":["SPP 2378 (project ReNO)"],"award-info":[{"award-number":["SPP 2378 (project ReNO)"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"name":"The Netherlands Organisation for Scientific Research (NWO) through Gravitation grant NETWORKS","award":["024.002.003"],"award-info":[{"award-number":["024.002.003"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Netw."],"published-print":{"date-parts":[[2025,9,3]]},"abstract":"<jats:p>Programmable packet schedulers provide great flexibility in the ordering of packet transmission. They allow network operators to optimize crucial performance metrics, such as Flow Completion Time (FCT), using strategies that adapt to changes in the characteristics of incoming traffic. A challenge in programming these devices is that they are severely limited in registers, memory, and control flow operations. The popular scheduling strategy Push-In First-Out (PIFO), for example, cannot be straightforwardly implemented because it relies on sorting packets, which is difficult to implement at line speed on current hardware. Fixed-priority approximations of PIFO, like SP-PIFO and AIFO, do have hardware implementations but generally still do not scale well in, for example, the number of memory cells being used. This paper introduces a new PIFO approximation strategy, Exp-PIFO, which prioritizes packets based on adaptive exponential prioritization criteria, called exponential bins. Exp-PIFO approximates the behavior of PIFO using only two memory cells to keep track of its state and uses a lookup table to avoid a complex control flow. We initially expected our improvement in memory and computation to come at a cost w.r.t. FCT performance compared to PIFO and its existing approximations. However, our empirical evaluation shows that Exp-PIFO sometimes even outperforms strict PIFO. We provide an explanation for this behavior and demonstrate the practical feasibility of Exp-PIFO through a proof-of-concept implementation on an Intel Tofino switch, which uses significantly less memory than comparable implementations of SP-PIFO and AIFO.<\/jats:p>","DOI":"10.1145\/3749217","type":"journal-article","created":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T13:42:01Z","timestamp":1756993321000},"page":"1-20","update-policy":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Exp-PIFO: Scalable and Efficient Programmable Packet Scheduling"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/orcid.org\/0000-0001-8282-1571","authenticated-orcid":false,"given":"Habib","family":"Mostafaei","sequence":"first","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, Netherlands"}]},{"ORCID":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/orcid.org\/0009-0003-2682-4403","authenticated-orcid":false,"given":"Mohammad","family":"Ezzati","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Berlin, Germany"}]},{"ORCID":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/orcid.org\/0000-0002-5487-4972","authenticated-orcid":false,"given":"Pieter J. L.","family":"Cuijpers","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, Netherlands and Radboud Universiteit, Nijmegen, Netherlands"}]},{"ORCID":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/orcid.org\/0000-0002-7798-1711","authenticated-orcid":false,"given":"Stefan","family":"Schmid","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Berlin, Germany and Fraunhofer SIT, Darmstadt, Germany"}]},{"ORCID":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/orcid.org\/0000-0002-5958-7817","authenticated-orcid":false,"given":"G\u00e1bor","family":"R\u00e9tv\u00e1ri","sequence":"additional","affiliation":[{"name":"Budapest University of Technology and Economics, Budapest, Hungary"}]},{"ORCID":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/orcid.org\/0000-0003-3306-6447","authenticated-orcid":false,"given":"Sem","family":"Borst","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, Netherlands"}]}],"member":"320","published-online":{"date-parts":[[2025,9,4]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2017. Netbench. https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/github.com\/ndal-eth\/netbench."},{"key":"e_1_2_1_2_1","unstructured":"2022. Intel Intelligent Fabric Processors. https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/www.intel.com\/content\/www\/us\/en\/products\/network-io\/ programmable-ethernet-switch.html."},{"key":"e_1_2_1_3_1","unstructured":"2023. Data Plane Development Kit. https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/dpdk.org."},{"key":"e_1_2_1_4_1","unstructured":"2023. Netberg Aurora 710. https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/netbergtw.com\/products\/aurora-710\/."},{"key":"e_1_2_1_5_1","volume-title":"17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20)","author":"Alcoz Albert Gran","year":"2020","unstructured":"Albert Gran Alcoz, Alexander Dietmuller, and Laurent Vanbever. 2020. SP-PIFO: Approximating Push-In First-Out Behaviors using Strict-Priority Queues. In 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20). 59--76."},{"key":"e_1_2_1_6_1","volume-title":"Everything Matters in Programmable Packet Scheduling. In 22nd USENIX Symposium on Networked Systems Design and Implementation (NSDI 25)","author":"Alcoz Albert Gran","year":"2025","unstructured":"Albert Gran Alcoz, Bal\u00e1zs Vass, Pooria Namyar, Behnaz Arzani, Gabor Retvari, and Laurent Vanbever. 2025. Everything Matters in Programmable Packet Scheduling. In 22nd USENIX Symposium on Networked Systems Design and Implementation (NSDI 25)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1851182.1851192"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486001.2486031"},{"key":"e_1_2_1_9_1","volume-title":"BBQ: A Fast and Scalable Integer Priority Queue for Hardware Packet Scheduling. In 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI 24)","author":"Atre Nirav","year":"2024","unstructured":"Nirav Atre, Hugo Sadok, and Justine Sherry. 2024. BBQ: A Fast and Scalable Integer Priority Queue for Hardware Packet Scheduling. In 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI 24). 455--475."},{"key":"e_1_2_1_10_1","volume-title":"Information-Agnostic Flow Scheduling for Commodity Data Centers. In 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI 15)","author":"Bai Wei","year":"2015","unstructured":"Wei Bai, Li Chen, Kai Chen, Dongsu Han, Chen Tian, and Hao Wang. 2015. Information-Agnostic Flow Scheduling for Commodity Data Centers. In 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI 15). 455--468."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3387514.3406221"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2656877.2656890"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication. 139--150","author":"Christiansen Mikkel","unstructured":"Mikkel Christiansen, Kevin Jeffay, David Ott, and F. Donelson Smith. 2000. Tuning RED for Web Traffic. In Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication. 139--150."},{"key":"e_1_2_1_14_1","volume-title":"Conference Proceedings on Communications Architectures & Protocols","author":"Clark David D.","year":"1992","unstructured":"David D. Clark, Scott Shenker, and Lixia Zhang. 1992. Supporting Real-Time Applications in an Integrated Services Packet Network: Architecture and Mechanism. In Conference Proceedings on Communications Architectures & Protocols (Baltimore, Maryland, USA) (SIGCOMM '92). 14--26."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111322.1111336"},{"key":"e_1_2_1_16_1","volume-title":"Gearbox: A Hierarchical Packet Scheduler for Approximate Weighted Fair Queuing. In 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22)","author":"Gao Peixuan","unstructured":"Peixuan Gao, Anthony Dalleggio, Yang Xu, and H. Jonathan Chao. 2022. Gearbox: A Hierarchical Packet Scheduler for Approximate Weighted Fair Queuing. In 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22). 551--565."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Pawan Goyal Harrick M. Vin and Haichen Chen. 1996. Start-Time Fair Queueing: A Scheduling Algorithm for Integrated Services Packet Switching Networks. In Conference Proceedings on Applications Technologies Architectures and Protocols for Computer Communications (Palo Alto California USA) (SIGCOMM '96). 157--168.","DOI":"10.1145\/248156.248171"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592568.1592576"},{"key":"e_1_2_1_19_1","volume-title":"Universal Packet Scheduling. In 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI 16)","author":"Mittal Radhika","year":"2016","unstructured":"Radhika Mittal, Rachit Agarwal, Sylvia Ratnasamy, and Scott Shenker. 2016. Universal Packet Scheduling. In 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI 16). 501--521."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3622845"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TON.2025.3531129"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication. 123--137","author":"Roy Arjun","unstructured":"Arjun Roy, Hongyi Zeng, Jasmeet Bagga, George Porter, and Alex C. Snoeren. 2015. Inside the Social Network's (Datacenter) Network. In Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication. 123--137."},{"key":"e_1_2_1_23_1","volume-title":"Eiffel: Efficient and Flexible Software Packet Scheduling. In 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19)","author":"Saeed Ahmed","year":"2019","unstructured":"Ahmed Saeed, Yimeng Zhao, Nandita Dukkipati, Ellen Zegura, Mostafa Ammar, Khaled Harras, and Amin Vahdat. 2019. Eiffel: Efficient and Flexible Software Packet Scheduling. In 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19)."},{"key":"e_1_2_1_24_1","volume-title":"Approximating Fair Queueing on Reconfigurable Switches. In 15th USENIX Symposium on Networked Systems Design and Implementation (NSDI 18)","author":"Sharma Naveen Kr.","year":"2018","unstructured":"Naveen Kr. Sharma, Ming Liu, Kishore Atreya, and Arvind Krishnamurthy. 2018. Approximating Fair Queueing on Reconfigurable Switches. In 15th USENIX Symposium on Networked Systems Design and Implementation (NSDI 18). 1--16."},{"key":"e_1_2_1_25_1","volume-title":"Programmable Calendar Queues for High-speed Packet Scheduling. In 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20)","author":"Sharma Naveen Kr.","year":"2020","unstructured":"Naveen Kr. Sharma, Chenxingyu Zhao, Ming Liu, Pravein G Kannan, Changhoon Kim, Arvind Krishnamurthy, and Anirudh Sivaraman. 2020. Programmable Calendar Queues for High-speed Packet Scheduling. In 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20). 685--699."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341302.3342090"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2934872.2934899"},{"key":"e_1_2_1_28_1","volume-title":"16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19)","author":"Stephens Brent","year":"2019","unstructured":"Brent Stephens, Aditya Akella, and Michael Swift. 2019. Loom: Flexible and efficient {NIC} packet scheduling. In 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19). 33--46."},{"key":"e_1_2_1_29_1","volume-title":"QCluster: Clustering Packets for Flow Scheduling (WWW '22)","author":"Yang Tong","year":"2022","unstructured":"Tong Yang, Jizhou Li, Yikai Zhao, Kaicheng Yang, Hao Wang, Jie Jiang, Yinda Zhang, and Nicholas Zhang. 2022. QCluster: Clustering Packets for Flow Scheduling (WWW '22). 1752--1763."},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the ACM SIGCOMM 2023 Conference. 208--219","author":"Yao Ruyi","unstructured":"Ruyi Yao, Zhiyu Zhang, Gaojian Fang, Peixuan Gao, Sen Liu, Yibo Fan, Yang Xu, and H. Jonathan Chao. 2023. BMW Tree: Large-scale, High-throughput and Modular PIFO Implementation using Balanced Multi-Way Sorting Tree. In Proceedings of the ACM SIGCOMM 2023 Conference. 208--219."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3452296.3472887"},{"key":"e_1_2_1_32_1","volume-title":"Twenty Years After: Hierarchical Core-Stateless Fair Queueing. In 18th USENIX Symposium on Networked Systems Design and Implementation (NSDI 21)","author":"Yu Zhuolong","year":"2021","unstructured":"Zhuolong Yu, Jingfeng Wu, Vladimir Braverman, Ion Stoica, and Xin Jin. 2021. Twenty Years After: Hierarchical Core-Stateless Fair Queueing. In 18th USENIX Symposium on Networked Systems Design and Implementation (NSDI 21). 29--45."}],"container-title":["Proceedings of the ACM on Networking"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/dl.acm.org\/doi\/pdf\/10.1145\/3749217","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T04:08:39Z","timestamp":1774066119000},"score":1,"resource":{"primary":{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/dl.acm.org\/doi\/10.1145\/3749217"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,3]]},"references-count":32,"journal-issue":{"issue":"CoNEXT3","published-print":{"date-parts":[[2025,9,3]]}},"alternative-id":["10.1145\/3749217"],"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.1145\/3749217","relation":{},"ISSN":["2834-5509"],"issn-type":[{"value":"2834-5509","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,3]]},"assertion":[{"value":"2025-09-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}