基于自相似流量水平分级预测的网络队列调度算法

doi:10.11959/j.issn.1000-436x.2020066

Abstract

Abstract:

Self-similarity characteristic of network traffic will lead to the continuous burstness of data in the network.In order to effectively reduce the queue delay and packet loss rate caused by network traffic burst,improve the transmission capacity of different priority services,and guarantee the service quality requirements,a queue scheduling algorithm P-DWRR based on the self-similarity of network traffic was proposed.A dynamic weight allocation method and a service quantum update method based on the self-similar traffic level grading prediction results were designed,and the service order of the queue according was determined to the service priority and queue waiting time,so as to reduce the queuing delay and packet loss rate.The simulation results show that the P-DWRR algorithm can reduce the queueing delay,delay jitter and packet loss rate on the basis of satisfying the different service priority requirements of the network,and its performance is better than that of DWRR and VDWRR.

Key words: network traffic, self-similarity, grading prediction, queue scheduling, round robin

CLC Number:

TP393

Debin WEI,Ting SHEN,Li YANG,Yaowen QI. Network queue scheduling algorithm based on self-similar traffic level grading prediction[J]. Journal on Communications, 2020, 41(4): 182-189.

Figures/Tables 11

L₂				L₁			$\bar{l^{'}}$
L₂	1	2	3	4	5	6	$\bar{l^{'}}$
1	0.614	0.312	0.074	0	0	0	1.5
2	0.006	0.512	0.297	0.185	0	0	2.7
3	0.002	0.153	0.340	0.301	0.204	0	3.6
4	0	0.003	0.327	0.394	0.284	0.002	4.0
5	0	0.002	0.235	0.422	0.337	0.004	4.1
6	0	0	0.002	0.356	0.500	0.142	4.8

L₂				L₁			$\bar{l^{'}}$
L₂	1	2	3	4	5	6	$\bar{l^{'}}$
1	0.553	0.263	0.122	0.062	0	0	1.6
2	0.048	0.462	0.285	0.174	0.031	0	2.7
3	0.007	0.196	0.338	0.291	0.164	0.004	3.4
4	0.004	0.075	0.285	0.357	0.271	0.008	3.8
5	0	0.023	0.260	0.386	0.325	0.006	4.0
6	0	0	0.013	0.387	0.487	0.113	4.7

L₂				L₁			$\bar{l^{'}}$
L₂	1	2	3	4	5	6	$\bar{l^{'}}$
1	0.457	0.217	0.197	0.118	0.011	0	2.0
2	0.063	0.381	0.266	0.157	0.128	0.005	2.9
3	0.017	0.227	0.326	0.241	0.182	0.007	3.4
4	0.011	0.143	0.295	0.313	0.223	0.015	3.6
5	0.005	0.046	0.319	0.372	0.247	0.011	3.8
6	0	0.002	0.083	0.406	0.424	0.085	4.5

References 16

[1]	PAREKH A K , GALLAGER R G . A generalized processor sharing approach to flow control in integrated services networks-the single node case[C]// Proceedings of INFOCOM’92. Piscataway:IEEE Press, 1992: 915-924.
[2]	SHREEDHAR M , VARGHESE G . Efficient fair queuing using deficit round robin[J]. IEEE/ACM Transactions on Networking, 1996,4(3): 375-385.
[3]	王胜灵, 侯义斌, 黄建辉 ,等. PFWRR:能实现比例公平的增强型WRR[J]. 计算机学报, 2008,31(5): 775-782.
	WANG S L , HOU Y B , HUANG J H ,et al. PFWRR:an enhanced WRR scheduling realizing the proportion fairness principle[J]. Chinese Journal of Computers, 2008,31(5): 775-782.
[4]	刘桂开 . 用逐次最小权值轮询算法实现公平和低时延分组调度[J]. 系统科学与数学, 2014,34(9) 1080-1099.
	LIU G K . Fair and low-latency packet scheduling using successive minimal-weight round robin[J]. Journal of Systems Science and Mathematical Sciences, 2014,34(9) 1080-1099.
[5]	李秉权, 张松, 王兆伟 ,等. WFQ与WRR调度算法的性能分析与改进[J]. 北京理工大学学报, 2015,35(3): 316-320.
	LI B Q , ZHAN H S , WANG Z W ,et al. Performance analysis and improvement about WFQ and WRR scheduling algorithm[J]. Transactions of Beijing Institute of Technology, 2015,35(3): 316-320.
[6]	江文静, 蔡祥宝 . DiffServ 队列调度算法研究[J]. 计算机技术与发展, 2015,25(4): 85-88.
	JIANG W J , CAI X B . Research on queue scheduling algorithm based on diffserv[J]. Computer Technology and Development, 2015,25(4): 85-88.
[7]	BOK P , KOHLS K , TUCHELMANN Y ,et al. I-DWRR-an insolvency enabled scheduling scheme extending Deficit Weighted Round Robin[C]// The 3rd IEEE International Workshop on Management of Emerging Networks and Services. Piscataway:IEEE Press, 2011: 695-700.
[8]	OUNI R , BHAR J; TORKI K . A new scheduling protocol design based on deficit weighted round robin for QoS support in IP networks[J]. Journal of Circuits,Systems,and Computers, 2013,22(3): 1-21.
[9]	LI C C , WANG K . An SLA-aware load balancing scheme for cloud datacenters[C]// 2014 International Conference on Information Networking (ICOIN). Piscataway:IEEE Press, 2014: 58-63.
[10]	LELAND W E , TAQQU M S , WILLINGER W ,et al. On the self-similar nature of Ethernet traffic (extended version)[J]. IEEE/ACM Transactions on Networking, 1994,2(1): 1-15.
[11]	CROVELLA M E , BESTAVROS A . Self-similarity in world wide web traffic:evidence and possible causes[J]. IEEE/ACM Transactions on Networking, 1997,5(6): 835-846.
[12]	WILLINGER W , TAQQU M S , SHERMAN R ,et al. Self-similarity through high-variability:statistical analysis of Ethernet LAN traffic at the source level[J]. IEEE/ACM Transactions on Networking, 1997,5: 71-86.
[13]	王晖, 季振洲, 孙彦东 ,等. 基于时间槽的自相似流量随机早检测算法——SFRED[J]. 通信学报, 2010,31(10): 115-120.
	WANG H , JI Z Z , SUN Y D ,et al. Time slot-based RED algorithm on self-similar flows:SFRED[J]. Journal on Communications, 2010,31(10): 115-120.
[14]	别玉霞, 潘成胜, 刘海燕 ,等. 基于 AOS 的 Hurst-优先级自适应RED与动态调度算法[J]. 通信学报, 2012,33(10): 156-165.
	BIE Y X , PAN C S , LIU H Y ,et al. Hurst-priority adaptive RED and dynamic scheduling algorithm based on AOS[J]. Journal on Communications, 2012,33(10): 156-165.
[15]	DOMA?SKI A , DOMA?SKA J , CZACHóRSKI T . Self- similarity traffic and AQM mechanism based on non-integer order PI^αD^β controller[J]. Computer Networks, 2017,718: 336-350.
[16]	TAQQU M S , WILLINGER W , SHERMAN R . Proof of a fundamental result in self-similar traffic modeling[J]. ACM SIGCOMM Computer Communication Review, 1998,27(2): 5-23.

Metrics

Recommended 0

No Suggested Reading articles found!

队列	DWRR算法/ms	VDWRR算法/ms	P-DWRR算法/ms
队列1	13.5	12.5	9.8
队列2	16.9	15.7	13.7
队列3	38.2	33.2	28.8

队列	DWRR算法	VDWRR算法	P-DWRR算法
队列1	8.4	7.8	5.8
队列2	9.8	9.3	7.9
队列3	19.7	16.3	13.6

Network queue scheduling algorithm based on self-similar traffic level grading prediction

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 11

References 16

Related Articles 15

Metrics

Recommended 0

[1]	Debin WEI, Chengsheng PAN, Li YANG, Zuoren YAN. Adaptive random early detection algorithm based on network traffic level grade prediction [J]. Journal on Communications, 2023, 44(6): 154-166.
[2]	Yifeng WANG, Yuanbo GUO, Qingli CHEN, Chen FANG, Renhao LIN, Yongliang ZHOU, Jiali MA. Method based on contrastive incremental learning for fine-grained malicious traffic classification [J]. Journal on Communications, 2023, 44(3): 1-11.
[3]	Xueyuan DUAN, Yu FU, Kun WANG, Taotao LIU, Bin LI. Network traffic anomaly detection method based on multi-scale characteristic [J]. Journal on Communications, 2022, 43(10): 65-76.
[4]	Jun’e LI, Qiuyu LU, Jian LIU, Kai YUAN, Wei TIAN, Bijun PENG. Communication service priority in smart substation and its queue scheduling method [J]. Journal on Communications, 2021, 42(7): 25-40.
[5]	Yongjin HU,Yuanbo GUO,Jun MA,Han ZHANG,Xiuqing MAO. Method to generate cyber deception traffic based on adversarial sample [J]. Journal on Communications, 2020, 41(9): 59-70.
[6]	Jie WANG,Lili YANG,Min YANG. Multitier ensemble classifiers for malicious network traffic detection [J]. Journal on Communications, 2018, 39(10): 155-165.
[7]	Yong WANG,Huiyi ZHOU,Hao FENG,Miao YE,Wenlong KE. Network traffic classification method basing on CNN [J]. Journal on Communications, 2018, 39(1): 14-23.
[8]	Cai-xia SONG,Guo-zhen TAN,Nan DING,Jun-ling BU,Fu-xin ZHANG,Ming-jian LIU. Application oriented cross-layer multi-channel MAC protocol for VANET [J]. Journal on Communications, 2016, 37(5): 95-105.
[9]	Zhong-da TIAN,Shu-jiang LI,Yan-hong WANG,Xiang-dong WANG. Network traffic multi-step prediction based on chaos theory and improved echo state network [J]. Journal on Communications, 2016, 37(3): 55-70.
[10]	Yu-fei ZHAO,Gang XIONG,Long-tao HE,Zhou-jun LI. Approach to detecting SQL injection behaviors in network environment [J]. Journal on Communications, 2016, 37(2): 89-98.
[11]	Xiang-kun MU,Jin-song WANG,Yu-feng XUE,Wei HUANG. Abnormal network traffic detection approach based on alive entropy [J]. Journal on Communications, 2013, 34(Z2): 51-57.
[12]	. Abnormal network traffic detection approach based on alive entropy [J]. Journal on Communications, 2013, 34(Z2): 11-57.
[13]	Lei FENG,Wen-jing LI,Xue-song QIU. Self-organized CAC mechanism adopting for self-similarity service in wireless network [J]. Journal on Communications, 2013, 34(8): 27-34.
[14]	. Self-organized CAC mechanism adopting for self-similarity service in wireless network [J]. Journal on Communications, 2013, 34(8): 4-34.
[15]	Tong GUO,Ju-long LAN,Wan-wei HUANG,Zhen ZHANG. Analysis the self-similarity of network traffic in fractional Fourier transform domain [J]. Journal on Communications, 2013, 34(6): 38-48.