{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T21:05:11Z","timestamp":1780347911040,"version":"3.54.1"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"CoNEXT2","funder":[{"name":"German Federal Ministry for Economics and Climate Action","award":["13IK015B"],"award-info":[{"award-number":["13IK015B"]}]},{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"crossref","award":["101139048"],"award-info":[{"award-number":["101139048"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001659","name":"German Research Foundation","doi-asserted-by":"crossref","award":["565652476"],"award-info":[{"award-number":["565652476"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Netw."],"published-print":{"date-parts":[[2026,6,1]]},"abstract":"<jats:p>\n                    Efficient hardware-supported packet scheduling is a cornerstone of fine-grained packet prioritization in modern networking systems. Algorithms such as Weighted Fair Queuing and Shortest Job First offer theoretical guarantees for achieving flow fairness and minimal flow completion times; however, their underlying priority-queue operation is difficult to implement at line rate due to its complexity. In this paper, we propose Dancing-Q, a line-rate dynamic approximation of a priority queue that is supported by current hardware and provides optimality guarantees. Essentially, Dancing-Q mimics the packet-sorting operation of a priority queue by distributing packets according to their ranks across multiple dynamically assigned FIFO queues. Key to the optimality guarantee are\n                    <jats:italic toggle=\"yes\">dynamic queue bounds<\/jats:italic>\n                    that map ranges of packet ranks to the FIFO queues which are served using a strict priority scheduler. To minimize\n                    <jats:italic toggle=\"yes\">rank inversions,<\/jats:italic>\n                    i.e., out-of-order scheduling when compared with an ideal priority queue, we introduce a per-queue local optimization strategy that rapidly drives queue bounds to optimal values based on the empirically observed packet ranks. Owing to the per-queue locality and a low memory and computation overhead, this optimization strategy allows prototyping Dancing-Q on programmable switches and SmartNICs. We demonstrate the priority queue emulation of Dancing-Q on a Tofino-based ASIC and use large-scale ns-3 experiments to show that compared to standard methods such as SP-PIFO, Dancing-Q (i) attains the optimal rank inversions, (ii) mimics the queuing delays of a priority queue on a significantly larger rank range, and (iii) curbs large flow starvation. Empirical evaluations show that Dancing-Q minimizes the flow completion time within a 4.4% overhead of the ideal priority queue.\n                  <\/jats:p>","DOI":"10.1145\/3808663","type":"journal-article","created":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T20:45:46Z","timestamp":1780346746000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Dancing-Q: Line-Rate Dynamic Approximation of Priority Queuing with Optimality Guarantees"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-6826-2178","authenticated-orcid":false,"given":"Chengbo","family":"Zhou","sequence":"first","affiliation":[{"name":"Technical University of Darmstadt, Darmstadt, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1711-5990","authenticated-orcid":false,"given":"Ralf","family":"Kundel","sequence":"additional","affiliation":[{"name":"Darmstadt University of Applied Sciences, Darmstadt, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9385-7729","authenticated-orcid":false,"given":"Amr","family":"Rizk","sequence":"additional","affiliation":[{"name":"Leibniz University Hannover, L3S, Hannover, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1133-1775","authenticated-orcid":false,"given":"Bj\u00f6rn","family":"Scheuermann","sequence":"additional","affiliation":[{"name":"Technical University of Darmstadt, Darmstadt, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,1]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"59","volume-title":"17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20)","author":"Alcoz Albert Gran","year":"2020","unstructured":"Albert Gran Alcoz, Alexander Dietm\u00fcller, 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). USENIX Association, Santa Clara, CA, 59-76. https:\/\/www.usenix.org\/conference\/nsdi20\/presentation\/alcoz"},{"key":"e_1_2_1_2_1","first-page":"1467","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). USENIX Association, Philadelphia, PA, 1467-1485. https:\/\/www.usenix.org\/conference\/nsdi25\/presentation\/alcoz"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1851182.1851192"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486001.2486031"},{"key":"e_1_2_1_5_1","first-page":"455","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). USENIX Association, Santa Clara, CA, 455-475. https:\/\/www.usenix.org\/conference\/nsdi24\/presentation\/atre"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.1996.497885"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2000.832227"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2656877.2656890"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/63039.63045"},{"key":"e_1_2_1_10_1","unstructured":"Cisco. 2026. TRex Traffic Generator. https:\/\/trex-tgn.cisco.com\/."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/75246.75248"},{"key":"e_1_2_1_12_1","first-page":"551","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). USENIX Association, Renton, WA, 551-565. https:\/\/www.usenix.org\/conference\/nsdi22\/presentation\/gao-peixuan"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.1994.337677"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.649569"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1594977.1592576"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2377677.2377710"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICC.2001.936948"},{"key":"e_1_2_1_18_1","first-page":"501","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). USENIX Association, Santa Clara, CA, 501-521. https:\/\/www.usenix.org\/conference\/nsdi16\/technical-sessions\/presentation\/mittal"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3230543.3230564"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3749217"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.234856"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.298432"},{"key":"e_1_2_1_23_1","first-page":"685","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). USENIX Association, Santa Clara, CA, 685-699. https:\/\/www.usenix.org\/conference\/nsdi20\/presentation\/sharma"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/217391.217453"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341302.3342090"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2934872.2934899"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651890.3672235"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2377677.2377709"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043164.2018443"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3603269.3604862"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3452296.3472887"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/99517.99525"}],"container-title":["Proceedings of the ACM on Networking"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3808663","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T20:46:39Z","timestamp":1780346799000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3808663"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,1]]},"references-count":32,"journal-issue":{"issue":"CoNEXT2","published-print":{"date-parts":[[2026,6,1]]}},"alternative-id":["10.1145\/3808663"],"URL":"https:\/\/doi.org\/10.1145\/3808663","relation":{},"ISSN":["2834-5509"],"issn-type":[{"value":"2834-5509","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,1]]},"assertion":[{"value":"2026-06-01","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}