可编程调度器研究综述

赵娅竹; 郭泽华; 窦松石; 符晓阳

doi:10.11999/JEIT250657

可编程调度器研究综述

doi: 10.11999/JEIT250657 cstr: 32379.14.JEIT250657

赵娅竹¹,
郭泽华^{1, 2, ,},
窦松石³,
符晓阳¹

1.
北京理工大学北京 100081
2.
北京理工大学郑州研究院郑州 450000
3.
香港大学香港

基金项目: 国家重点研发计划(2024YFB2907100)，河南省重点研发专项(241111211300), 中央高校基本科研业务费专项资金资助 (2025CX11033)，中原科技创新青年拔尖人才计划

详细信息

作者简介:
赵娅竹：女，博士生，研究方向为可编程网络

郭泽华：男，特别研究员，博士生导师，研究方向为可编程网络、机器学习以及网络安全

窦松石：男，博士生，研究方向为可编程网络

符晓阳：男，硕士生，研究方向为可编程网络

通讯作者:
郭泽华　guolizihao@hotmail.com

中图分类号: TN91;TP393
计量
- 文章访问数: 14
- HTML全文浏览量: 13
- PDF下载量: 0
- 被引次数: 0
出版历程
- 收稿日期: 2025-07-11
- 修回日期: 2025-09-08
- 网络出版日期: 2025-09-12

Recent Advances of Programmable Schedulers

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

摘要

摘要: 近年来，可编程调度器受到学术界与工业界的广泛关注，为提升网络服务质量提供了新的机会。针对实际应用中对低时延和低抖动的需求，可编程调度器通过采用先进先出(FIFO)或推入先出(PIFO)等设计，大幅提升了调度的准确性和可编程性，确保数据包按预定时间精准发送，从而优化了网络性能。该文对提升调度准确性和可编程性的可编程调度器研究进展进行了综述。首先，阐明了调度器在数据包调度流程中的作用和意义。随后，基于国内外相关文献，介绍了当前主流的可编程调度器设计方案。最后，总结了现有研究成果的提升空间，并展望了未来的发展方向和研究前景。
- 可编程调度器 /
- FIFO /
- PIFO
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)

HTML全文

图 1 数据包调度过程

下载: 全尺寸图片幻灯片

图 2 FIFO队列和PIFO队列的调度原理举例

下载: 全尺寸图片幻灯片

图 3 可编程调度器的分类

下载: 全尺寸图片幻灯片

表 1 可编程调度器的研究现状

基础调度原语	实现目标	实现方法	算法名称	调度框架组成	结构特点	表达能力	近似精度
FIFO	提升调度准确性	准入控制	AIFO^[17]	单FIFO队列、准入控制、跟踪Rank	限制入队数据包Rank	-	近似实现PIFO
			FAIFO^[18]	单FIFO队列、双队列、准入控制、缓存决策	限制入队数据包Rank、对数据包新鲜度排序	-	近似实现PIFO
			RIFO^[19]	单FIFO队列、准入控制、跟踪Rank	限制入队数据包Rank	-	近似实现PIFO
			SP-PIFO^[20]	多FIFO队列、数据包Rank通过准入条件映射至符合的队列、自适应更改准入条件、准入控制、严格优先级	限制入队数据包Rank、队列边界动态变化、自下而上扫描	<PIFO	近似实现PIFO
			PACKS^[21]	多FIFO队列、准入控制、数据包Rank通过准入条件映射至符合的队列、严格优先级、跟踪Rank	限制入队数据包Rank、最优队列边界、自上而下扫描	-	近似实现PIFO
			SW-PIFO^[22]	多FIFO队列、准入控制、数据包Rank通过准入条件映射至符合的队列、严格优先级、跟踪Rank	限制入队数据包Rank、滑动窗口跟踪优先级优化队列边界	-	近似实现PIFO
		调度算法改进	AFQ^[23]	日历队列、旋转优先级、每轮发送字节数	公平调度数据包并节省队列数量	-	近似实现PIFO
			EFQ^[24]	多FIFO队列、旋转优先级、自适应分配缓冲区	节省队列数量并公平调度数据包，调度更多数据包	-	近似实现PIFO
			PCQ^[25]	日历队列、旋转优先级	动态更改数据包优先级	-	近似实现PIFO
			Gearbox^[26]	日历队列、复合FIFO队列	不同粒度	-	近似实现PIFO
	提升可编程性	准出控制	AIAO^[27]	单FIFO队列、时间门机制	可控出队	>PIFO	按发送时间调度数据包
	提升可编程性	准出控制	CIPO^[28]	跟踪Rank和发送时间、多FIFO队列、约束Rank和发送时间	分类入队，可控出队	>PIFO	按发送时间调度数据包
PIFO	实现精确调度顺序	数据结构方式实现	PHeap^[29]	二叉堆、令牌数组	并行化操作出入队	-	精确实现PIFO
			Pipelined heap^[30]	二叉堆	存放在线性数组中	-	精确实现PIFO
			SIMD-PQ^[31]	数组、决策树	同时实现出入队、不同组可并行处理	-	精确实现PIFO
			SurgeProtector^[32]	分层首位查找HFFS、优先级桶	定位最高优先级非空桶、丢弃当前最大作业数据包	-	精确实现PIFO
			BMW-Tree^[33]	数据结构树	平衡、模块化	$ \approx $PIFO	精确实现PIFO
			BBQ^[34]	HFFS、优先级桶	数据包Rank入队至相应优先级桶中、最高优先级非空桶出队、位图树	$ \approx $PIFO	精确实现PIFO
			Clubheap^[35]	二叉堆、簇	消除操作间数据依赖性、不依赖逻辑PIFO数量	-	精确实现PIFO
		队列方式实现	PIFO^[36]	PIFO树	实现层次化调度	=PIFO	精确实现PIFO
			Sifter^[37]	Mini-PIFO、旋转日历队列(Rotating Calendar Queue, RCQ)	Mini-PIFO存较小Rank数据包、RCQ存较大Rank数据包	-	精确实现PIFO
			vPIFO^[38]	PIFO树	PIFO树结构自适应变化	$ \approx $PIFO	精确实现PIFO
	提升可编程性	准出控制	PIEO^[39]	单PIFO队列、多FIFO队列、约束Rank和发送时间	FIFO存数据包、PIFO存流的引用	>PIFO	按发送时间调度数据包
			PIPO^[40]	两个PIFO队列	时间触发流优先级最高、以数据包发送时间排序	>PIFO	按发送时间调度数据包
			DR-PIFO^[41]	单PIFO队列、多FIFO队列	PIFO存流的头数据包、FIFO存数据包、更改FIFO中数据包Rank	>PIFO	按发送时间调度数据包
注：“-” 表示该内容未作明确说

下载: 导出CSV

参考文献(41)

[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.