Recent Advances of Programmable Schedulers

ZHAO Yazhu; GUO Zehua; DOU Songshi; FU Xiaoyang

doi:10.11999/JEIT250657

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2025 >

ZHAO Yazhu, GUO Zehua, DOU Songshi, FU Xiaoyang. Recent Advances of Programmable Schedulers[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250657

Citation:

ZHAO Yazhu, GUO Zehua, DOU Songshi, FU Xiaoyang. Recent Advances of Programmable Schedulers[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250657

ZHAO Yazhu, GUO Zehua, DOU Songshi, FU Xiaoyang. Recent Advances of Programmable Schedulers[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250657

Citation:

ZHAO Yazhu, GUO Zehua, DOU Songshi, FU Xiaoyang. Recent Advances of Programmable Schedulers[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250657

PDF( 1257 KB)

Recent Advances of Programmable Schedulers

doi: 10.11999/JEIT250657 cstr: 32379.14.JEIT250657

1.
Beijing Institute of Technology, Beijing 100081, China
2.
Zhengzhou Research Institute, Beijing Institute of Technology, Zhengzhou 450000, China
3.
The University of Hong Kong, Hong Kong, China

Funds: National Key Research and Development Program of China (2024YFB2907100), Key Research and Development Project of Henan Province (241111211300), Fundamental Research Funds for the Central Universities (2025CX11033), and Central Plains Science and Technology Innovation Young Top Talent Program

Received Date: 2025-07-11
Rev Recd Date: 2025-09-08

Available Online: 2025-09-12

Abstract

Abstract

Objective In recent years, diversified user demands, dynamic application scenarios, and massive data transmissions have imposed increasingly stringent requirements on modern networks. Network schedulers play a critical role in ensuring efficient and reliable data delivery, enhancing overall performance and stability, and directly shaping user-perceived service quality. Traditional scheduling algorithms, however, rely largely on fixed hardware, with scheduling logic hardwired during chip design. These designs are inflexible, provide coarse and static scheduling granularity, and offer limited capability to represent complex policies. Therefore, they hinder rapid deployment, increase upgrade costs, and fail to meet the evolving requirements of heterogeneous and large-scale network environments. Programmable schedulers, in contrast, leverage flexible hardware architectures to support diverse strategies without hardware replacement. Scheduling granularity can be dynamically adjusted at the flow, queue, or packet level to meet varied application requirements with precision. Furthermore, they enable the deployment of customized logic through data plane programming languages, allowing rapid iteration and online updates. These capabilities significantly reduce maintenance costs while improving adaptability. The combination of high flexibility, cost-effectiveness, and engineering practicality positions programmable schedulers as a superior alternative to traditional designs. Therefore, the design and optimization of high-performance programmable schedulers have become a central focus of current research, particularly for data center networks and industrial Internet applications, where efficient, flexible, and controllable traffic scheduling is essential. Methods The primary objective of current research is to design universal, high-performance programmable schedulers. Achieving simultaneous improvements across multiple performance metrics, however, remains a major challenge. Hardware-based schedulers deliver high performance and stability but incur substantial costs and typically support only a limited range of scheduling algorithms, restricting their applicability in large-scale and heterogeneous network environments. In contrast, software-based schedulers provide flexibility in expressing diverse algorithms but suffer from inherent performance constraints. To integrate the high performance of hardware with the flexibility of software, recent designs of programmable schedulers commonly adopt First-In First-Out (FIFO) or Push-In First-Out (PIFO) queue architectures. These approaches emphasize two key performance metrics: scheduling accuracy and programmability. Scheduling accuracy is critical, as modern applications such as real-time communications, online gaming, telemedicine, and autonomous driving demand strict guarantees on packet timing and ordering. Even minor errors may result in increased latency, reduced throughput, or connection interruptions, compromising user experience and service reliability. Programmability, by contrast, enables network devices to adapt to diverse scenarios, supporting rapid deployment of new algorithms and flexible responses to application-specific requirements. Improvements in both accuracy and programmability are therefore essential for developing efficient, reliable, and adaptable network systems, forming the basis for future high-performance deployments. Results and Discussions The overall packet scheduling process is illustrated in (Fig. 1), where scheduling is composed of scheduling algorithms and schedulers. At the ingress or egress pipelines of end hosts or network devices, scheduling algorithms assign a Rank value to each packet, determining the transmission order based on relative differences in Rank. Upon arrival at the traffic manager, the scheduler sorts and forwards packets according to their Rank values. Through the joint operation of algorithms and schedulers, packet scheduling is executed while meeting quality-of-service requirements. A comparative analysis of the fundamental principles of FIFO and PIFO scheduling mechanisms (Fig. 2) highlights their differences in queue ordering and disorder control. At present, most studies on programmable schedulers build upon these two foundational architectures (Fig. 3), with extensions and optimizations primarily aimed at improving scheduling accuracy and programmability. Specific strategies include admission control, refinement of scheduling algorithms, egress control, and advancements in data structures and queue mechanisms. On this basis, the current research progress on programmable schedulers is reviewed and systematically analyzed. Existing studies are compared along three key dimensions: structural characteristics, expressive capability, and approximation accuracy (Table 1). Conclusions Programmable schedulers, as a key technology for next-generation networks, enable flexible traffic management and open new possibilities for efficient packet scheduling. This review has summarized recent progress in the design of programmable schedulers across diverse application scenarios. The background and significance of programmable schedulers within the broader packet scheduling process were first clarified. An analysis of domestic and international literature shows that most current studies focus on FIFO-based and PIFO-based architectures to improve scheduling accuracy and programmability. The design approaches of these two architectures were examined, the main technical methods for enhancing performance were summarized, and their structural characteristics, expressive capabilities, and approximation accuracy were compared, highlighting respective advantages and limitations. Potential improvements in existing research were also identified, and future development directions were discussed. Nevertheless, the design of a universal, high-performance programmable scheduler remains a critical challenge. Achieving optimal performance across multiple metrics while ensuring high-quality network services will require continued joint efforts from both academia and industry.
- Programmable scheduler,
- First-In First-Out (FIFO),
- Push-In First-Out (PIFO)

FullText(HTML)

References(41)

References

[1]	LI Ziyong, HU Yuxiang, TIAN Le, et al. Packet rank-aware active queue management for programmable flow scheduling[J]. Computer Networks, 2023, 225: 109632. doi: 10.1016/j.comnet.2023.109632.
[2]	SAEED A, ZHAO Yimeng, DUKKIPATI N, et al. Eiffel: Efficient and flexible software packet scheduling[C]. Proceedings of the 16th USENIX Conference on Networked Systems Design and Implementation, Boston, USA, 2019: 17–31.
[3]	MITTAL R, AGARWAL R, RATNASAMY S, et al. Universal packet scheduling[C]. Proceedings of the 14th ACM Workshop on Hot Topics in Networks, Philadelphia, USA, 2015: 24. doi: 10.1145/2834050.2834085.
[4]	SIVARAMAN A, SUBRAMANIAN S, AGRAWAL A, et al. Towards programmable packet scheduling[C]. Proceedings of the 14th ACM Workshop on Hot Topics in Networks, Philadelphia, USA, 2015: 23. doi: 10.1145/2834050.2834106.
[5]	HARKOUS H, PAPAGIANNI C, DE SCHEPPER K, et al. Virtual queues for P4: A poor man’s programmable traffic manager[J]. IEEE Transactions on Network and Service Management, 2021, 18(3): 2860–2872. doi: 10.1109/TNSM.2021.3077051.
[6]	MOHAN A, LIU Yunhe, FOSTER N, et al. Formal abstractions for packet scheduling[J]. Proceedings of the ACM on Programming Languages, 2023, 7(OOPSLA2): 269. doi: 10.1145/3622845.
[7]	DEMERS A, KESHAV S, and SHENKER S. Analysis and simulation of a fair queueing algorithm[J]. ACM SIGCOMM Computer Communication Review, 1989, 19(4): 1–12. doi: 10.1145/75247.75248.
[8]	SHREEDHAR M and VARGHESE G. Efficient fair queuing using deficit round-robin[J]. IEEE/ACM Transactions on Networking, 1996, 4(3): 375–385. doi: 10.1109/90.502236.
[9]	GOYAL P, VIN H M, and CHEN Haichen. Start-time fair queueing: A scheduling algorithm for integrated services packet switching networks[C]. Proceedings of Conference Proceedings on Applications, Technologies, Architectures, and Protocols for Computer Communications, Palo Alto, USA, 1996: 157–168. doi: 10.1145/248156.248171.
[10]	SCHRAGE L E and MILLER L W. The queue M/G/1 with the shortest remaining processing time discipline[J]. Operations Research, 1966, 14(4): 670–684. doi: 10.1287/opre.14.4.670.
[11]	SAEED A, DUKKIPATI N, VALANCIUS V, et al. Carousel: Scalable traffic shaping at end hosts[C]. Proceedings of Conference of the ACM Special Interest Group on Data Communication, Los Angeles, USA, 2017: 404–417. doi: 10.1145/3098822.3098852.
[12]	RADHAKRISHNAN S, GENG Yilong, JEYAKUMAR V, et al. SENIC: Scalable NIC for end-host rate limiting[C]. Proceedings of the 11th USENIX Conference on Networked Systems Design and Implementation, Seattle, USA, 2014: 475–488.
[13]	WIKIPEDIA. Token bucket[EB/OL]. https://en.wikipedia.org/wiki/Token_bucket, 2022.
[14]	IEEE. 802.1Qbv-2015 IEEE standard for local and metropolitan area networks -- bridges and bridged networks - amendment 25: Enhancements for scheduled traffic[S]. IEEE, 2016. (查阅网上资料, 未找到出版地信息, 请补充).
[15]	IEEE. 802.1Qch-2017 IEEE standard for local and metropolitan area networks -- bridges and bridged networks -- amendment 29: Cyclic queuing and forwarding[S]. IEEE, 2017. (查阅网上资料, 未找到出版地信息, 请补充).
[16]	IEEE. 802.1Qav-2009 IEEE standard for local and metropolitan area networks -- virtual bridged local area networks amendment 12: Forwarding and queuing enhancements for time-sensitive streams[S]. IEEE, 2010. (查阅网上资料, 未找到出版地信息, 请补充).
[17]	YU Zhuolong, HU Chuheng, WU Jingfeng, et al. Programmable packet scheduling with a single queue[C]. Proceedings of 2021 ACM SIGCOMM 2021 Conference, Virtual Event, USA, 2021: 179–193. doi: 10.1145/3452296.3472887.(查阅网上资料,未能确认出版地信息,请确认).
[18]	ZHU Mengyuan, CHEN Kefan, CHEN Zhuo, et al. FAIFO: UAV-assisted IoT programmable packet scheduling considering freshness[J]. Ad Hoc Networks, 2022, 134: 102912. doi: 10.1016/j.adhoc.2022.102912.
[19]	MOSTAFAEI H, PACUT M, and SCHMID S. RIFO: Pushing the efficiency of programmable packet schedulers[J]. IEEE Transactions on Networking, 2025, 33(3): 1295–71308. doi: 10.1109/ton.2025.3531129.
[20]	ALCOZ A G, DIETMÜLLER A, and VANBEVER L. SP-PIFO: Approximating push-in first-out behaviors using strict-priority queues[C]. Proceedings of the 17th USENIX Conference on Networked Systems Design and Implementation, Santa Clara, USA, 2020: 59–76.
[21]	ALCOZ A G, VASS B, NAMYAR P, et al. Everything matters in programmable packet scheduling[C]. Proceedings of the 22nd USENIX Symposium on Networked Systems Design and Implementation, Philadelphia, USA, 2025: 1467–1485.
[22]	HUANG Jiawei, WANG Qile, LI Zhaoyi, et al. Achieving efficient scheduling based on accurate measurement of small flows in data center[C]. Proceedings of the 53rd International Conference on Parallel Processing, Gotland, Sweden, 2024: 337–346. doi: 10.1145/3673038.3673086.
[23]	SHARMA N K, LIU Ming, ATREYA K, et al. Approximating fair queueing on reconfigurable switches[C]. Proceedings of the 15th USENIX Conference on Networked Systems Design and Implementation, Renton, USA, 2018: 1–16.
[24]	LIU Jingling, HUANG Jiawei, LI Zhaoyi, et al. Achieving per-flow fairness and high utilization with limited priority queues in data center[J]. IEEE/ACM Transactions on Networking, 2022, 30(5): 2374–2387. doi: 10.1109/TNET.2022.3172749.
[25]	SHARMA N K, ZHAO Chenxingyu, LIU Ming, et al. Programmable calendar queues for high-speed packet scheduling[C]. Proceedings of the 17th USENIX Conference on Networked Systems Design and Implementation, Santa Clara, USA, 2020: 685–699.
[26]	GAO Peixuan, DALLEGGIO A, XU Yang, et al. Gearbox: A hierarchical packet scheduler for approximate weighted fair queuing[C]. Proceedings of the 19th USENIX Symposium on Networked Systems Design and Implementation, Renton, USA, 2022: 551–565.
[27]	LV Qianru, JIANG Xuyan, and YANG Xiangrui. Making programmable packet scheduling time-sensitive with a FIFO queue[J]. Journal of Cloud Computing, 2023, 12(1): 141. doi: 10.1186/s13677-023-00518-3.
[28]	GUO Feng, SUN Shidong, HU Junjie, et al. CIPO: Efficient, lightweight and programmable packet scheduling[J]. Computer Networks, 2024, 245: 110355. doi: 10.1016/j.comnet.2024.110355.
[29]	BHAGWAN R and LIN B. Fast and scalable priority queue architecture for high-speed network switches[C]. Proceedings of Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies, Tel Aviv, Israel, 2000: 538–547. doi: 10.1109/INFCOM.2000.832227.
[30]	IOANNOU A and KATEVENIS M G H. Pipelined heap (priority queue) management for advanced scheduling in high-speed networks[J]. IEEE/ACM Transactions on Networking, 2007, 15(2): 450–461. doi: 10.1109/TNET.2007.892882.
[31]	BENACER I, BOYER F R, and SAVARIA Y. A fast, single-instruction–multiple-data, scalable priority queue[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2018, 26(10): 1939–1952. doi: 10.1109/tvlsi.2018.2838044.
[32]	ATRE N, SADOK H, CHIANG E, et al. SurgeProtector: Mitigating temporal algorithmic complexity attacks using adversarial scheduling[C]. Proceedings of ACM SIGCOMM 2022 Conference, Amsterdam, Netherlands, 2022: 723–738. doi: 10.1145/3544216.3544250.
[33]	YAO Ruyi, ZHANG Zhiyu, FANG Gaojian, et al. BMW tree: Large-scale, high-throughput and modular PIFO implementation using balanced multi-way sorting tree[C]. Proceedings of ACM SIGCOMM 2023 Conference, New York, USA, 2023: 208–219. doi: 10.1145/3603269.3604862.
[34]	ATRE N, SADOK H, and SHERRY J. BBQ: A fast and scalable integer priority queue for hardware packet scheduling[C]. Proceedings of the 21st USENIX Symposium on Networked Systems Design and Implementation, Santa Clara, USA, 2024: 26.
[35]	CHEN Zhikang, SONG Haoyu, ZHANG Zhiyu, et al. ClubHeap: A high-speed and scalable priority queue for programmable packet scheduling[C]. Proceedings of the 22nd USENIX Symposium on Networked Systems Design and Implementation, Philadelphia, USA, 2025: 1421–1436.
[36]	SIVARAMAN A, SUBRAMANIAN S, ALIZADEH M, et al. Programmable packet scheduling at line rate[C]. Proceedings of 2016 ACM SIGCOMM Conference, Florianopolis, Brazil, 2016: 44–57. doi: 10.1145/2934872.2934899.
[37]	GAO Peixuan, DALLEGGIO A, LIU Jiajin, et al. Sifter: An inversion-free and large-capacity programmable packet scheduler[C]. Proceedings of the 21st USENIX Symposium on Networked Systems Design and Implementation, Santa Clara, USA, 2024: 5.
[38]	ZHANG Zhiyu, CHEN Shili, YAO Ruyi, et al. vPIFO: Virtualized packet scheduler for programmable hierarchical scheduling in high-speed networks[C]. Proceedings of ACM SIGCOMM 2024 Conference, Sydney, NSW, Australia, 2024: 983–999. doi: 10.1145/3651890.3672270.
[39]	SHRIVASTAV V. Fast, scalable, and programmable packet scheduler in hardware[C]. Proceedings of ACM Special Interest Group on Data Communication, Beijing, China, 2019: 367–379. doi: 10.1145/3341302.3342090.
[40]	ZHANG Chuwen, CHEN Zhikang, SONG Haoyu, et al. PIPO: Efficient programmable scheduling for time sensitive networking[C]. Proceedings of the 2021 IEEE 29th International Conference on Network Protocols, Dallas, USA, 2021: 1–11. doi: 10.1109/ICNP52444.2021.9651944.
[41]	ELBEDIWY M, PONTIKAKIS B, GHAFFARI A, et al. DR-PIFO: A dynamic ranking packet scheduler using a push-in-first-out queue[J]. IEEE Transactions on Network and Service Management, 2024, 21(1): 355–371. doi: 10.1109/TNSM.2023.3304894.