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

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

通信学报 ›› 2020, Vol. 41 ›› Issue (4): 182-189.doi: 10.11959/j.issn.1000-436x.2020066

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

魏德宾^1,^2,³,沈婷^2,³(),杨力^2,³,戚耀文¹

¹ 南京理工大学自动化学院，江苏南京 210094
² 大连大学信息工程学院，辽宁大连 116622
³ 大连大学通信与网络重点实验室，辽宁大连 116622

修回日期:2020-03-18 出版日期:2020-04-25 发布日期:2020-04-30
作者简介:魏德宾（1978- ），男，辽宁大连人，南京理工大学博士生、大连大学副教授，主要研究方向为空间信息网络传输技术、流量工程和网络优化|沈婷（1995- ），女，安徽滁州人，大连大学硕士生，主要研究方向为空间信息网络传输技术|杨力（1982- ），女，黑龙江哈尔滨人，博士，大连大学教授，主要研究方向为空间信息网络传输技术、无线通信网络协议理论与方法|戚耀文（1994- ），男，山东威海人，南京理工大学博士生，主要研究方向为空间信息网络传输技术、空间信息网络路由协议
基金资助:
国家自然科学基金资助项目(61722105);国家自然科学基金资助项目(61931004)

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

Debin WEI^1,^2,³,Ting SHEN^2,³(),Li YANG^2,³,Yaowen QI¹

¹ School of Automation,Nanjing University of Science and Technology,Nanjing 210094,China
² School of Information Engineering,Dalian University,Dalian 116622,China
³ Communication and Network Laboratory,Dalian University,Dalian 116622,China

Revised:2020-03-18 Online:2020-04-25 Published:2020-04-30
Supported by:
The National Natural Science Foundation of China(61722105);The National Natural Science Foundation of China(61931004)

摘要/Abstract

摘要：

网络流量的自相似特性会导致网络中数据的突发状态持续，为有效降低网络流量突发引起的队列排队时延和分组丢失率，提高不同优先级业务的传输能力，保障业务服务质量需求，提出了一种基于网络流量自相似特性的队列调度算法——P-DWRR。该算法设计了基于自相似流量水平分级预测结果的动态权值分配方法及服务量子更新方法，并根据业务优先级和队列等待时间确定队列的服务次序，以减小数据分组排队时延，降低分组丢失率。仿真结果表明，P-DWRR算法在满足网络不同业务优先级要求的基础上，降低了数据分组的排队时延、时延抖动和分组丢失率，性能优于DWRR和VDWRR。

关键词: 网络流量, 自相似性, 分级预测, 队列调度, 轮询

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

中图分类号:

TP393

魏德宾,沈婷,杨力,戚耀文. 基于自相似流量水平分级预测的网络队列调度算法[J]. 通信学报, 2020, 41(4): 182-189.

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.

图/表 11

图1

图2

图3

表1

α= 1.2时流量水平条件转移概率"

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

表1

表2

α= 1.4时流量水平条件转移概率"

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

表2

表3

α= 1.6时流量水平条件转移概率"

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

表3

图4

图5

图6

表4

表5

参考文献 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.

队列	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

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 16

相关文章 15

Metrics

推荐阅读 0

[1]	魏德宾, 潘成胜, 杨力, 颜佐任. 基于网络流量水平等级预测的自适应随机早期检测算法[J]. 通信学报, 2023, 44(6): 154-166.
[2]	王一丰, 郭渊博, 陈庆礼, 方晨, 林韧昊, 周永良, 马佳利. 基于对比增量学习的细粒度恶意流量分类方法[J]. 通信学报, 2023, 44(3): 1-11.
[3]	王一丰, 郭渊博, 陈庆礼, 方晨, 林韧昊. 基于对比学习的细粒度未知恶意流量分类方法[J]. 通信学报, 2022, 43(10): 12-25.
[4]	段雪源, 付钰, 王坤, 刘涛涛, 李彬. 基于多尺度特征的网络流量异常检测方法[J]. 通信学报, 2022, 43(10): 65-76.
[5]	李俊娥, 陆秋余, 刘剑, 袁凯, 田薇, 彭弼君. 智能变电站通信业务优先级及其队列调度方法[J]. 通信学报, 2021, 42(7): 25-40.
[6]	胡永进,郭渊博,马骏,张晗,毛秀青. 基于对抗样本的网络欺骗流量生成方法[J]. 通信学报, 2020, 41(9): 59-70.
[7]	汪洁,杨力立,杨珉. 基于集成分类器的恶意网络流量检测[J]. 通信学报, 2018, 39(10): 155-165.
[8]	谢显中,卢华兵,施赵媛. 基于轮询机制的公平高效机会干扰对齐算法[J]. 通信学报, 2017, 38(10): 1-9.
[9]	田中大,李树江,王艳红,王向东. 基于混沌理论与改进回声状态网络的网络流量多步预测[J]. 通信学报, 2016, 37(3): 55-70.
[10]	赵宇飞,熊刚,贺龙涛,李舟军. 面向网络环境的SQL注入行为检测方法[J]. 通信学报, 2016, 37(2): 89-98.
[11]	韩春静,葛敬国,谢高岗,李亮雄,李佟,刘韵洁. 基于匿名化流表的网络数据分组实时匿名方法[J]. 通信学报, 2016, 37(11): 11-22.
[12]	刘龙军,丁洪伟,柳虔林,刘正纲. 基于FPGA WSN轮询接入控制协议的研究[J]. 通信学报, 2016, 37(10): 181-187.
[13]	穆祥昆,王劲松,薛羽丰,黄玮. 基于活跃熵的网络异常流量检测方法[J]. 通信学报, 2013, 34(Z2): 51-57.
[14]	穆祥昆1,2，王劲松1,2，薛羽丰1,2，黄玮1,2. 基于活跃熵的网络异常流量检测方法[J]. 通信学报, 2013, 34(Z2): 11-57.
[15]	宋元章,何俊婷,张波,王俊杰,王安邦. 基于流角色检测P2P botnet[J]. 通信学报, 2012, 33(Z1): 262-269.