Review on Service Curves of Typical Scheduling Algorithms

doi:10.12142/ZTECOM.202402008

ZTE Communications ›› 2024, Vol. 22 ›› Issue (2): 55-70.DOI: 10.12142/ZTECOM.202402008

• Review • Previous Articles Next Articles

Review on Service Curves of Typical Scheduling Algorithms

GAO Yuehong¹(), NING Zhi¹, HE Jia¹, ZHOU Jinfei¹, GAO Chenqiang²^,³, TANG Qingkun²^,³, YU Jinghai²^,³

^1.Beijing University of Posts and Telecommunications, Beijing 100876, China
^2.ZTE Corporation, Shenzhen 518057, China
^3.State Key Laboratory of Mobile Network and Mobile Multimedia Technology, Shenzhen 518055, China

Received:2024-01-03 Online:2024-06-28 Published:2024-06-25
About author:GAO Yuehong (yhgao@bupt.edu.cn) received her PhD degree from Beijing University of Posts and Telecommunications (BUPT), China in 2010. She is an associate professor with the School of Information and Communication Engineering, BUPT. Her research interests include network calculus theory and application, quality of service guarantees in communication networks, simulation methodology, and digital twin networks.
NING Zhi received his BE degree in communication engineering from Beijing University of Posts and Telecommunications (BUPT), China in 2021. He is working towards his MS degree at BUPT. His research interests include wireless networks and deterministic networking.
HE Jia received his BE degree in communication engineering from Beijing University of Posts and Telecommunications (BUPT), China in 2022. He is working towards his MS degree in communication engineering at BUPT. His research interests include network calculus, 5G network architecture, and deterministic networking.
ZHOU Jinfei received his BE degree in communication engineering from Beijing University of Posts and Telecommunications (BUPT), China in 2023, where he is currently pursuing an MS degree. His research interests include wireless networks and deterministic networking.
GAO Chenqiang works at in the Data System Department of ZTE Corporation. His research interests include network calculus theory and application, DetNet, TSN, and SDN.
TANG Qingkun works at the Cable Software Platform Development Department of ZTE Corporation. His research interests include DetNet, TSN, and autonomous networks.
YU Jinghai works at the Data System Department of ZTE Corporation. He has more than 20 years of experience in the research and design of data network products including BIER, DetNet, TSN, Switch and Router, Data Center and SDN. He has won the 21st China Patent Silver Award and the first prize of the Science and Technology Award of the China Communications Society.
Supported by:
ZTE Industry?University-?Institute Cooperation Funds

Abstract

Abstract:

In recent years, various internet architectures, such as Integrated Services (IntServ), Differentiated Services (DiffServ), Time Sensitive Networking (TSN) and Deterministic Networking (DetNet), have been proposed to meet the quality-of-service (QoS) requirements of different network services. Concurrently, network calculus has found widespread application in network modeling and QoS analysis. Network calculus abstracts the details of how nodes or networks process data packets using the concept of service curves. This paper summarizes the service curves for typical scheduling algorithms, including Strict Priority (SP), Round Robin (RR), Cycling Queuing and Forwarding (CQF), Time Aware Shaper (TAS), Credit Based Shaper (CBS), and Asynchronous Traffic Shaper (ATS). It introduces the theory of network calculus and then provides an overview of various scheduling algorithms and their associated service curves. The delay bound analysis for different scheduling algorithms in specific scenarios is also conducted for more insights.

Key words: network calculus, service curve, scheduling algorithm, QoS

GAO Yuehong, NING Zhi, HE Jia, ZHOU Jinfei, GAO Chenqiang, TANG Qingkun, YU Jinghai. Review on Service Curves of Typical Scheduling Algorithms[J]. ZTE Communications, 2024, 22(2): 55-70.

Figures/Tables 18

Table 1 Latency bounds for Strict Priority (SP) scheduling

Flow ID	Priority	$τ i$ /ms	$σ i / B$	$d i$ /ms	Simulation Results/ms
1	High	1	256	0.409 6	0.256 0
2	Middle	1	256	0.579 5	0.406 8
3	Low	1	256	1.040 1	0.614 4

Table 1 Latency bounds for Strict Priority (SP) scheduling

Flow ID	Priority	$τ i$ /ms	$σ i / B$	$d i$ /ms	Simulation Results/ms
1	High	1	256	0.409 6	0.256 0
2	Middle	1	256	0.579 5	0.406 8
3	Low	1	256	1.040 1	0.614 4

Table 2 Flow configurations for Weighted Fair Queuing (WFQ) scheduling

Flow ID	Weight	$τ i /$ ms	$σ i / B$
1	4	1	256
2	3	1	256
3	2	1	256

Table 2 Flow configurations for Weighted Fair Queuing (WFQ) scheduling

Flow ID	Weight	$τ i /$ ms	$σ i / B$
1	4	1	256
2	3	1	256
3	2	1	256

Table 3 Delay bounds for Weighted Fair Queuing (WFQ) scheduling

Method	$d 1 / m s$	$d 2 / m s$	$d 3 / m s$
$β i W F Q - 1$	0.576 0	0.768 0	1.152 0
$β i W F Q - 2$	0.576 0	0.631 5	0.665 6
$β i W F Q - 3$	0.576 0	0.631 5	0.665 6
Simulation results	0.406 8	0.512 0	0.614 4

Table 3 Delay bounds for Weighted Fair Queuing (WFQ) scheduling

Method	$d 1 / m s$	$d 2 / m s$	$d 3 / m s$
$β i W F Q - 1$	0.576 0	0.768 0	1.152 0
$β i W F Q - 2$	0.576 0	0.631 5	0.665 6
$β i W F Q - 3$	0.576 0	0.631 5	0.665 6
Simulation results	0.406 8	0.512 0	0.614 4

Table 4 Flow configurations for RR scheduling

Scheduling Algorithm	Flow ID	Weight	$τ i /$ ms	$σ i / B$
WRR	1	4	1	256
	2	3	1	256
	3	2	1	256
DRR	1	256	1	256
	2	192	1	256
	3	128	1	256

Table 4 Flow configurations for RR scheduling

Scheduling Algorithm	Flow ID	Weight	$τ i /$ ms	$σ i / B$
WRR	1	4	1	256
	2	3	1	256
	3	2	1	256
DRR	1	256	1	256
	2	192	1	256
	3	128	1	256

Table 5 Delay bounds for RR scheduling

Scheduling Algorithm	Method	$d 1 / m s$	$d 2 / m s$	$d 3 / m s$
WRR	$β i W R R - 1$	0.716 8	0.921 6	1.280 0
	$β i W R R - 2$	0.460 8	0.819 2	0.921 6
	$β i W R R - 3$	0.460 8	0.819 2	0.921 6
	$β i B S - W R R$	0.716 8	0.815 5	0.870 6
	Simulation	0.406 8	0.614 4	0.614 4
IWRR	$β i I W R R$	0.460 8	0.665 6	0.921 6
IWRR	simulation	0.460 8	0.563 2	0.614 4
DRR	$β i D R R - ε - 1$	0.716 8	0.921 6	1.280 0
	$β i B S - D R R$	0.460 8	0.614 4	0.921 6
	$β i D R R - ε - 2$	0.460 8	0.819 2	0.921 6
	Simulation	0.406 8	0.614 4	0.614 4

Table 5 Delay bounds for RR scheduling

Scheduling Algorithm	Method	$d 1 / m s$	$d 2 / m s$	$d 3 / m s$
WRR	$β i W R R - 1$	0.716 8	0.921 6	1.280 0
	$β i W R R - 2$	0.460 8	0.819 2	0.921 6
	$β i W R R - 3$	0.460 8	0.819 2	0.921 6
	$β i B S - W R R$	0.716 8	0.815 5	0.870 6
	Simulation	0.406 8	0.614 4	0.614 4
IWRR	$β i I W R R$	0.460 8	0.665 6	0.921 6
IWRR	simulation	0.460 8	0.563 2	0.614 4
DRR	$β i D R R - ε - 1$	0.716 8	0.921 6	1.280 0
	$β i B S - D R R$	0.460 8	0.614 4	0.921 6
	$β i D R R - ε - 2$	0.460 8	0.819 2	0.921 6
	Simulation	0.406 8	0.614 4	0.614 4

Table 6 Configurations and delay bounds for Round Robin (RR) scheduling

	$τ i /$ ms	$σ i / B$	$d i /$ ms	Simulation Results/ms
$β C Q F - 1$	1	256	0.204 8	0.204 8
$β C Q F - 0$	1	256	4.204 8	4.204 8

Table 6 Configurations and delay bounds for Round Robin (RR) scheduling

	$τ i /$ ms	$σ i / B$	$d i /$ ms	Simulation Results/ms
$β C Q F - 1$	1	256	0.204 8	0.204 8
$β C Q F - 0$	1	256	4.204 8	4.204 8

Table 7 Configurations and delay bounds for TAS

Flow ID	GCL	$τ i /$ ms	$σ i / B$	$d i /$ ms	Simulation Results/ms
1	100000	6	512	0.409 6	0.409 6
2	010010	3	521	1.409 6	1.409 6
3	001001	3	521	2.409 6	2.409 6

Table 7 Configurations and delay bounds for TAS

Flow ID	GCL	$τ i /$ ms	$σ i / B$	$d i /$ ms	Simulation Results/ms
1	100000	6	512	0.409 6	0.409 6
2	010010	3	521	1.409 6	1.409 6
3	001001	3	521	2.409 6	2.409 6

Table 8 Configurations for CBS

Flow ID	$i d l e S l o p e$ /Mbit·s^-1	$s e n d S l o p e$ /(Mbit·s^-1)	$τ i /$ ms	$σ i / B$
SR-A	4	-6	1	256
SR-B	3	-7	1	256
BE	-	-	1	256
CDT	-	-	1	64
ST	-	-	10	64

Table 8 Configurations for CBS

Flow ID	$i d l e S l o p e$ /Mbit·s^-1	$s e n d S l o p e$ /(Mbit·s^-1)	$τ i /$ ms	$σ i / B$
SR-A	4	-6	1	256
SR-B	3	-7	1	256
BE	-	-	1	256
CDT	-	-	1	64
ST	-	-	10	64

Table 9 Delay bound for CBS

		$d S R - A / m s$	$d S R - B / m s$	Simulation Results/ms
		SR A	SR B
$β X C B S$		0.640 0	0.938 7	0.460 8	0.563 2
$β X C B S - C D T$		0.650 3	0.920 1	0.512 0	0.614 4
$β i C B S - S T - 1$	P	1.588 2	1.852 5	1.470 8	1.573 2
$β i C B S - S T - 1$	NP	1.614 4	1.870 4	1.512 0	1.614 4
$β i B S - S T - 2$	F	1.614 4	1.870 4	1.512 0	1.614 4
$β i B S - S T - 2$	NF	1.615 3	1.907 7	1.460 8	1.563 2

Table 9 Delay bound for CBS

		$d S R - A / m s$	$d S R - B / m s$	Simulation Results/ms
		SR A	SR B
$β X C B S$		0.640 0	0.938 7	0.460 8	0.563 2
$β X C B S - C D T$		0.650 3	0.920 1	0.512 0	0.614 4
$β i C B S - S T - 1$	P	1.588 2	1.852 5	1.470 8	1.573 2
$β i C B S - S T - 1$	NP	1.614 4	1.870 4	1.512 0	1.614 4
$β i B S - S T - 2$	F	1.614 4	1.870 4	1.512 0	1.614 4
$β i B S - S T - 2$	NF	1.615 3	1.907 7	1.460 8	1.563 2

Table 10 Configurations and delay bounds for ATS

Flow ID	Committed Transmission Rate/(Mbit·s^-1)	Burst Size/B	$τ i /$ ms	$σ i / B$	$d i /$ ms
1	4	128	1	256	0.256 0
2	3	128	1	256	0.597 3
3	2	128	1	256	1.563 0

Table 10 Configurations and delay bounds for ATS

Flow ID	Committed Transmission Rate/(Mbit·s^-1)	Burst Size/B	$τ i /$ ms	$σ i / B$	$d i /$ ms
1	4	128	1	256	0.256 0
2	3	128	1	256	0.597 3
3	2	128	1	256	1.563 0

References 51

1	IETF. Integrated services in the internet architecture: an overview: RFC 1633 [S]. 1994
2	IETF. An architecture for differentiated services: RFC2475 [S]. 1998
3	DON W. The history of the IEEE 802 standard [J]. IEEE communications standards magazine, 2018, 2(2): 4. DOI: 10.1109/MCOMSTD.2018.8412452
4	IETF. Deterministic networking problem statement: RFC8557 [S]. 2019
5	HE F, ZHAO L, LI E S. Impact analysis of flow shaping in ethernet-AVB/TSN and AFDX from network calculus and simulation perspective [J]. Sensors, 2017, 17(5): 1181. DOI: 10.3390/s17051181
6	FINZI A, MIFDAOUI A, FRANCES F, et al. Incorporating TSN/BLS in AFDX for mixed-criticality applications: model and timing analysis [C]//Proc. 14th IEEE International Workshop on Factory Communication Systems (WFCS). IEEE, 2018: 1–10. DOI: 10.1109/WFCS.2018.8402346
7	ZHAO L X, POP P, STEINHORST S. Quantitative performance comparison of various traffic shapers in time-sensitive networking [J]. IEEE transactions on network and service management, 2022, 19(3): 2899–2928. DOI: 10.1109/TNSM.2022.3180160
8	SPECHT J, SAMII S. Urgency-based scheduler for time-sensitive switched Ethernet networks [C]//Proc. 28th Euromicro Conference on Real-Time Systems (ECRTS). IEEE, 2016: 75–85. DOI: 10.1109/ECRTS.2016.27
9	LE BOUDEC J Y. A theory of traffic regulators for deterministic networks with application to interleaved regulators [J]. IEEE/ACM transactions on networking, 2018, 26(6): 2721–2733. DOI: 10.1109/TNET.2018.2875191
10	MOHAMMADPOUR E, STAI E, MOHIUDDIN M, et al. Latency and backlog bounds in time-sensitive networking with credit based shapers and asynchronous traffic shaping [C]//Proc. 30th International Teletraffic Congress (ITC 30. IEEE, 2018: 1–6
11	JIANG Y M. Some properties of length rate quotient shapers [EB/OL]. (2021-07-11)[2023-10-13].
12	JIANG Y M. A basic result on the superposition of arrival processes in deterministic networks [C]//Proc. IEEE Global Communications Conference (GLOBECOM). IEEE, 2018: 1–6. DOI: 10.1109/GLOCOM.2018.8647202
13	CRUZ R L. A calculus for network delay. part I: network elements in isolation [J]. IEEE transactions on information theory, 1991, 37(1): 114–131. DOI: 10.1109/18.61109
14	CRUZ R L. A calculus for network delay, part II: network analysis [J]. IEEE transactions on information theory, 1991, 37(1): 132–141. DOI: 10.1109/18.61110
15	PAREKH A K, GALLAGER R G. A generalized processor sharing approach to flow control in integrated services networks: the single-node case [J]. IEEE/ACM transactions on networking, 1993, 1(3): 344–357. DOI: 10.1109/90.234856
16	PAREKH A K, GALLAGER R G. A generalized processor sharing approach to flow control in integrated services networks: the multiple node case [J]. IEEE/ACM transactions on networking, 1994, 2(2):137–150. DOI: 10.1109/90.234856
17	CRUZ R L. Quality of service guarantees in virtual circuit switched networks [J]. IEEE journal on selected areas in communications, 1995, 13(6): 1048–1056. DOI: 10.1109/49.400660
18	SARIOWAN H, CRUZ R L, POLYZOS G C. Scheduling for quality of service guarantees via service curves [C]//Proc. Fourth International Conference on Computer Communications and Networks. IEEE, 1995: 512–520. DOI: 10.1109/ICCCN.1995.540168
19	AGRAWAL R, RAJAN R. Performance bounds for guaranteed and adaptive services: IBM Technical Report RC 20649 [R]. 1996
20	CRUZ R L. SCED: efficient management of quality of service guarantees [C]//Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies. IEEE, 1998: 625–634. DOI: 10.1109/INFCOM.1998.665083
21	LE BOUDEC J Y. Application of network calculus to guaranteed service networks [J]. IEEE transactions on information theory, 1998, 44(3): 1087–1096. DOI: 10.1109/18.669170
22	CHANG C S. On deterministic traffic regulation and service guarantees: a systematic approach by filtering [J]. IEEE transactions on information theory, 1998, 44(3): 1097–1110. DOI: 10.1109/18.669173
23	AGRAWAL R, CRUZ R L, OKINO C, et al. Performance bounds for flow control protocols [J]. IEEE/ACM transactions on networking, 1999, 7(3): 310–323. DOI: 10.1109/90.779197
24	FIDLER M. Survey of deterministic and stochastic service curve models in the network calculus [J]. IEEE communications surveys & tutorials, 2010, 12(1): 59–86. DOI: 10.1109/SURV.2010.020110.00019
25	LE BOUDEC J Y, THIRAN P. Network calculus: a theory of deterministic queuing systems for the Internet [M]. Berlin: Springer, 2001
26	STILIADIS D, VARMA A. Latency-rate servers: a general model for analysis of traffic scheduling algorithms [J]. IEEE/ACM transactions on networking, 1998, 6(5): 611–624. DOI: 10.1109/90.731196
27	JIANG Y M, LIU Y. Stochastic network calculus [M]. London: Springer, 2008
28	BURCHARD A, LIEBEHERR J. A general per-flow service curve for GPS [C]//Proc. 30th International Teletraffic Congress (ITC 30. IEEE, 2018: 31–36
29	NAGLE J. On packet switches with infinite storage [J]. IEEE transactions on communications, 1987, 35(4): 435–438. DOI: 10.1109/TCOM.1987.1096782
30	KATEVENIS M, SIDIROPOULOS S, COURCOUBETIS C. Weighted round-robin cell multiplexing in a general-purpose ATM switch chip [J]. IEEE journal on selected areas in communications, 1991, 9(8): 1265–1279. DOI: 10.1109/49.105173
31	SHREEDHAR M, 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
32	BOUILLARD A, BOYER M, LE CORRONC E. Deterministic network calculus: from theory to practical implementation [M]. Hoboken: Wiley, 2018. DOI: 10.1002/9781119440284
33	TABATABAEE S M, LE BOUDEC J Y, BOYER M. Interleaved weighted round-robin: a network calculus analysis [J]. IEICE Transactions on Communications, 2021, 104(12): 1479–1493. 10.1587/TRANSCOM.2021ITI0001
34	KANHERE S S, SETHU H. On the latency bound of deficit round robin [C]//Proc. Eleventh International Conference on Computer Communications and Networks. IEEE, 2002: 548–553. DOI: 10.1109/ICCCN.2002.1043123 .
35	LENZINI L, MINGOZZI E, STEA G. Full exploitation of the deficit round Robin capabilities by efficient implementation and parameter tuning [R]. 2003
36	BOYER M, STEA G, MANGOUA SOFACK W. Deficit round robin with network calculus [C]//Proc. 6th International Conference on Performance Evaluation Methodologies and Tools. IEEE, 2012: 138–147. DOI: 10.4108/valuetools.2012.250202
37	BOUILLARD A. Individual service curves for bandwidth-sharing policies using network calculus [J]. IEEE networking letters, 2021, 3(2): 80–83. DOI: 10.1109/LNET.2021.3067766
38	TABATABAEE S M, LE BOUDEC J Y. Deficit round-robin: a second network calculus analysis [J]. IEEE/ACM transactions on networking, 2022, 30(5): 2216–2230. DOI: 10.1109/TNET.2022.3164772
39	CONSTANTIN V C, NIKOLAUS P, SCHMITT J. Improving performance bounds for weighted round-robin schedulers under constrained cross-traffic [C]//Proc. IFIP Networking Conference (IFIP Networking). IEEE, 2022: 1–9
40	IEEE. IEEE standard for local and metropolitan area networks: bridges and bridged networks: amendment 29: cyclic queuing and forwarding: 802.1Qch-2017 [S]. 2017
41	YIN S W, WANG S, HUANG T. Analysis and optimization of queues based on network calculus in time-sensitive networking [J]. ZTE technology journal, 2022, 28(1): 21–28. DOI:10.12142/ZTETJ.202201007
42	WANDELER E, THIELE L. Optimal TDMA time slot and cycle length allocation for hard real-time systems [C]//Proc. Asia and South Pacific Conference on Design Automation. IEEE, 2006: 479–484. DOI: 10.1109/ASPDAC.2006.1594731
43	IEEE. IEEE standard for local and metropolitan area networks: bridges and bridged networks: amendment 25: enhancements for scheduled traffic: 802.1Qbv-2015 [S]. 2015
44	IEEE. IEEE standard for local and metropolitan area networks: bridges and bridged networks: amendment 26: frame preemption: 802.1Qbu-2016 [S]. 2016
45	ZHAO L X, POP P, CRACIUNAS S S. Worst-case latency analysis for IEEE 802.1Qbv time sensitive networks using network calculus [J]. IEEE access, 2018, 6: 41803–41815. DOI: 10.1109/ACCESS.2018.2858767
46	IEEE. IEEE standard for local and metropolitan area networks: virtual bridged local area networks amendment 12: forwarding and queuing enhancements for time-sensitive streams: 802.1Qav [S]. 2009
47	DE AZUA J A R, BOYER M. Complete modelling of AVB in Network Calculus Framework [C]//Proc. 22nd International Conference on Real-Time Networks and Systems. ACM, 2014: 55–64. DOI: 10.1145/2659787.2659810
48	ZHAO L, HE F, LI E S, et al. Improving worst-case delay analysis for traffic of additional stream reservation class in ethernet-AVB network [J]. Sensors, 2018, 18(11): 3849. DOI: 10.3390/s18113849
49	ZHAO L X, POP P, ZHENG Z, et al. Timing analysis of AVB traffic in TSN networks using network calculus [C]//Proc. IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS). IEEE, 2018: 25–36. DOI: 10.1109/RTAS.2018.00009
50	ZHAO L X, POP P, ZHENG Z, et al. Latency analysis of multiple classes of AVB traffic in TSN with standard credit behavior using network calculus [J]. IEEE transactions on industrial electronics, 2020, 68(10): 10291–10302. DOI: 10.1109/TIE.2020.3021638
51	IEEE. IEEE standard for local and metropolitan area networks-bridges and bridged networks amendment 34: asynchronous traffic shaping: 802.1 Qcr-2020 [S]. 2020

[1]	CHEN Jinling, XU Yiwen, LIU Yisang, HUANG Huiwen, ZHUANG Zhongwen. Quality of Experience Effects in Video Delivery [J]. ZTE Communications, 2019, 17(1): 25-30.
[2]	JIN Yaqi, XU Xiaodong, TAO Xiaofeng. Multi-QoS Guaranteed Resource Allocation for Multi-Services Based on Opportunity Costs [J]. ZTE Communications, 2018, 16(2): 9-15.
[3]	Ye Miao, Zhili Sun, Ning Wang. Gateway Selection in MANET Based Integrated System: A Survey [J]. ZTE Communications, 2015, 13(4): 45-52.
[4]	Borui Ren, Gang Liu, Bin Hou. Utility-Based Joint Scheduling Approach Supporting Multiple Services for CoMP-SU-MIMO in LTE-A System [J]. ZTE Communications, 2015, 13(1): 60-66.
[5]	Lianming Zhang, Jia Liu, and Kun Yang. VirtualizedWireless SDNs: Modelling Delay Through the Use of Stochastic Network Calculus [J]. ZTE Communications, 2014, 12(2): 50-56.
[6]	Chengjie Gu, Shunyi Zhang, and Yanfei Sun. Self-Adaptive QoS Control in Cognitive Networks That Is Based on Service Awareness [J]. ZTE Communications, 2011, 9(2): 44-48.

Review on Service Curves of Typical Scheduling Algorithms

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 18

References 51

Related Articles 6

Recommended Articles

Metrics