基于流量预测的RED拥塞控制算法研究
|
摘要
在网络迅速发展的当今社会,网络的使用者要求网络提供高速度、高质量的信息传输服务,与此同时,网络拥塞的现象却屡屡发生。因此,拥塞控制的研究也成为了研究者青睐的研究方向。
路由器缓存中存在过多的等待发送的数据包,网络的带宽容量却又不能承受如此之大的负荷,这就会造成拥塞现象。解决网络拥塞的核心就是队列管理和队列调度算法的实现,队列管理算法是解决路由器内部队列如何建立、如何维护、如何排队的过程,队列调度算法是用来决定谁先被调度的算法,以此来实现队列之间共享输出链路资源的过程。
本文是在RED拥塞控制算法的基础上进行研究的,RED算法是队列管理算法中的一个经典代表,属于主动队列管理算法的范畴。通过对RED算法优缺点进行详细分析,提出了一种基于流量预测的改进RED算法——2P-RED算法。
在研究思路上,首先针对网络流量的自相似性、长相关性、周期性等特性,利用数学公式对流量特性进行量化,为建立预测模型提供了基础；其次研究了各种智能算法,提出了把人工神经网络模型应用到数据流量的预测的想法,用Matlab工具进行仿真实验,为了提高BP算法的精确度和学习能力,BP神经网络中权值阈值的初始化利用模拟退火和粒子群算法进行了改进；然后,将流量预测代码添加到RED协议当中去,实现对RED算法的改进,添加协议的过程主要工作是对Edv结构体以及类REDQueue中drop_early函数进行修改,协议修改完毕,在NS2模拟软件中重新编译,即可投入到路由器队列管理算法的使用当中了。
文章最后建立了含有不同个数的TCP、UDP数据流的网络模型,数据包传送过程分别采用改进的RED和基本RED两种队列管理算法,由模拟得到的Trace文件可以进一步分析出不同算法的丢包率、吞吐量、时延来,实验结果验证了改进算法在解决拥塞控制上具有良好的效果。
With the rapid development of network times, network users request the network must provide high-speed, high-quality services. At the same time, the network congestion often occurs. Therefore, congestion control research has become a popular research area.
It will cause the congestion, because there are many packets waiting to be sent in the cache of router, but the network bandwidth capacity cannot bear such a large load. It is the queue management algorithm and the queue scheduling algorithm that to solve the congestion. The queue management is the process to solve how to create, maintain and line up queue, and the queue scheduling algorithm is to determine which should be scheduling algorithm, and in order to achieve sharing the link of resources between output queues.
The Random Early Detection (RED) algorithm is a classical representative of the active queue management, of which study on the basis. Through a detailed analysis about advantages and disadvantages of RED algorithms, this paper put forward the 2P-RED algorithm, which is an improved RED algorithms based on flow prediction.
In the study, first, put these characterisitics to formula according to the nature of self-similarity, long-range dependence, periodicity of the network traffic. It is the foundation for the establishment of forcasting model.Second, research the intelligent algorithms and put forward the idea of applying the artificial network model into the data flow prediction, then simulate with Matlab.The weight threshold initialized using SA and PSO algorithm, after that the accuracy and learning ability of the BP algorithm are improved. And then, it adds the flow prediction code to RED protocol to improve RED algorithm. The main task of adding the agreement is amending the function of drop-early in the RED Queue and Edv Structure. After amending this agreement, modified and re-compiled in the Network Simulator 2(NS2) simulation software, it can be put into the router queue management algorithm and used.
Finally, the paper establishes the network model which includes different number of TCP, UDP data flow. Comparing the basic RED algorithm and the improved RED algorithm, and get the packet loss rate, throughput and delay by analyzing the trace files, the results show the improved algorithm has a good effect in solving the congestion control.
路由器缓存中存在过多的等待发送的数据包,网络的带宽容量却又不能承受如此之大的负荷,这就会造成拥塞现象。解决网络拥塞的核心就是队列管理和队列调度算法的实现,队列管理算法是解决路由器内部队列如何建立、如何维护、如何排队的过程,队列调度算法是用来决定谁先被调度的算法,以此来实现队列之间共享输出链路资源的过程。
本文是在RED拥塞控制算法的基础上进行研究的,RED算法是队列管理算法中的一个经典代表,属于主动队列管理算法的范畴。通过对RED算法优缺点进行详细分析,提出了一种基于流量预测的改进RED算法——2P-RED算法。
在研究思路上,首先针对网络流量的自相似性、长相关性、周期性等特性,利用数学公式对流量特性进行量化,为建立预测模型提供了基础；其次研究了各种智能算法,提出了把人工神经网络模型应用到数据流量的预测的想法,用Matlab工具进行仿真实验,为了提高BP算法的精确度和学习能力,BP神经网络中权值阈值的初始化利用模拟退火和粒子群算法进行了改进；然后,将流量预测代码添加到RED协议当中去,实现对RED算法的改进,添加协议的过程主要工作是对Edv结构体以及类REDQueue中drop_early函数进行修改,协议修改完毕,在NS2模拟软件中重新编译,即可投入到路由器队列管理算法的使用当中了。
文章最后建立了含有不同个数的TCP、UDP数据流的网络模型,数据包传送过程分别采用改进的RED和基本RED两种队列管理算法,由模拟得到的Trace文件可以进一步分析出不同算法的丢包率、吞吐量、时延来,实验结果验证了改进算法在解决拥塞控制上具有良好的效果。
With the rapid development of network times, network users request the network must provide high-speed, high-quality services. At the same time, the network congestion often occurs. Therefore, congestion control research has become a popular research area.
It will cause the congestion, because there are many packets waiting to be sent in the cache of router, but the network bandwidth capacity cannot bear such a large load. It is the queue management algorithm and the queue scheduling algorithm that to solve the congestion. The queue management is the process to solve how to create, maintain and line up queue, and the queue scheduling algorithm is to determine which should be scheduling algorithm, and in order to achieve sharing the link of resources between output queues.
The Random Early Detection (RED) algorithm is a classical representative of the active queue management, of which study on the basis. Through a detailed analysis about advantages and disadvantages of RED algorithms, this paper put forward the 2P-RED algorithm, which is an improved RED algorithms based on flow prediction.
In the study, first, put these characterisitics to formula according to the nature of self-similarity, long-range dependence, periodicity of the network traffic. It is the foundation for the establishment of forcasting model.Second, research the intelligent algorithms and put forward the idea of applying the artificial network model into the data flow prediction, then simulate with Matlab.The weight threshold initialized using SA and PSO algorithm, after that the accuracy and learning ability of the BP algorithm are improved. And then, it adds the flow prediction code to RED protocol to improve RED algorithm. The main task of adding the agreement is amending the function of drop-early in the RED Queue and Edv Structure. After amending this agreement, modified and re-compiled in the Network Simulator 2(NS2) simulation software, it can be put into the router queue management algorithm and used.
Finally, the paper establishes the network model which includes different number of TCP, UDP data flow. Comparing the basic RED algorithm and the improved RED algorithm, and get the packet loss rate, throughput and delay by analyzing the trace files, the results show the improved algorithm has a good effect in solving the congestion control.
引文
[1]Hwangnam Kim, Jennifer C. Hou. Enabling network calculus-based simulation for TCP congestion control. Computer Networks,2009,53(1):1-24.
[2]Xing Fan, Magnus Jonsson, and Jan Jonsson. Guaranteed real-time communication in packet-switched networks with FCFS queuing. Computer Networks,2009,53(3):400-417.
[3]Jingyi He, and S.-H. Gary Chan. TCP and UDP performance for Internet over optical packet-switched networks. Computer Networks,2004,45(4):505-521.
[4]Walter Goralski. The Illstrated Network:How TCP/IP Works in a Modern Network. Publisher Elsevier.2009,321-344.
[5]Anunay Tiwari, Anirudha Sahoo. Providing QoS in OSPF based best effort network using load sensitive routing. Simulation Modelling Practice and Theory,2007, 15(4):426-428.
[6]http://image.cnki.net/bigImage.aspx?T=CNKIIMAGE&id=2864369.
[7]刘宴兵,刘蕾.基于ARED排队算法的定性探讨.计算机科学,2004,09.
[8]Chang-Kuo Chen, Hang-Hong Kuo, Jun-Juh Yan, Ten-Lu Liao. GA-based PID active queue management control design for a class of TCP communication networks. Expert Systems with Applications,2009,36(2):1903-1913.
[9]方远舟.对FRED算法的改进及其实现[硕士学位论文],成都：电子科技大学,2005.
[10]文宏,李仲宇,吴海波,唐玉华.一种基于路由器队列法则的增加SRED算法.计算机应用与软件,2007,11.
[11]朱国晖,张煜,赵季红.一种改进AVQ的主动队列算法.陕西科技大学学报,2006,24(6).
[12]Wang Hao, Ma Xuetao, Tian Zuohua. A Fuzzy Self-tuning Random Exponential Marking Algorithm Based on Enhanced Price. Computer Simulation,2009,08.
[13]孔金生,赵长伟,万百五.网络拥塞的智能化适应控制方法.系统工程与电子技术,2005,07.
[14]NB. Behsaz, P Gburzynski, M. MacGregor. Transport-independent fairness. Computer Networks,2009,53(14):2444-2457.
[15]Chen Liu, Qing-pu Zhang, Xue Zhang. Emergence and disappearance of traffic congestion in weight-evolving networks. Simulation Modelling Practice and Theory,2009, 17(10):1566-1574.
[16]Baochun Bai, Janelle Harms, Yuxi Li. Configurable active multicast congestion control. Computer Networks,2008,52(7):1410-1432.
[17]Yueping Zhang, Saurabh Jain, Dmitri Loguinov. Towards experimental evaluation of explicit congestion control.Computer Networks,2009,53(7):1027-1039.
[18]Hyun-Wook Jin, Chuck Yoo. Impact of protocol overheads on network throughput over high-speed interconnects:measurement, analysis, and improvement. Journal of Supercomputing,2007,42(1):17-40.
[19]R Jain, A Durresi, G Babic. Throughput Fairness Index:An Explanation, ATM Forum/99-0045
[20]M Jaffe, Bottleneck Flow Control. IEEE Transactions on Communication,1981,29 (7):954-62.
[21]Kounavis M E, Campbell A T, etl. The genesisi Kernel:Apropramming system for spawning network architectures. IEEE Jouranl on Selected Areas in Communications, 2001,19(3):511-526.
[22]蒋启明,乐光学,于述春.基于事件的主动队列管理研究,微型计算机信息.2010,12.
[23]A. Koubaa, Y. Q. Song. Evaluation and improvement of response time bounds for real-time applications under non-pre-emptive Fixed Priority Scheduling. Internaltional Journal of Production Research.2004,7.
[24]H. Y. K. Lau, S.O. Woo. An agent-based dynamic routing strategy for automated material handing systems. International Journal of Computer Integrated Manufacturing.2007,3.
[25]邹雪兰,刘伟彦,孙雁飞.一种基于速率的公平队列管理算法.计算机工程.2009,3.
[26]Yang C, Reddy A. Taxonomy for Congestion Control Algorithms in Packet Switching Networks. IEEE Network Magazine,1995,9:34-35.
[27]Thompson, K., Miller, G. J., Wilder, R. Wide-Area Internet Traffic Patterns and Characteristics. IEEE Nerwork,1997,11(6):10-23.
[28]E. C. Park, H. lim, K. J. Park, etc. Analysis and Design of the Virtual Rate Control Algorithm for Stabilizing Queues in TCP Networks. Computer Networks,2004,44(1):17-41.
[29]J. Aweya, M. Ouellette, and D. Y. Montuno. A Contrlo Theoretic Approach to Active Queue Management. Journal of Computer Networks,2001,36(2):203-235.
[30]Chennian Long, Bin Zhao, Xinping Guan, etc. The YELLOW Active Queue Management Algorithm. Journal of Computer Networks,2004.
[31]袁小坊,王东,谢高岗等.高速网络流量特性与流数据库设计.计算机工程与应用,2009年2月,45(13)：2627.
[32]K. Park, W Willinger. Self-similar network traffic and performance evaluation. Wiley Iner-science, NewYork,2000.
[33]Atilla Aslanargun, Marnmadagha Marnmadov, Bema Yazici, et al. Comparison of ARIMA, neural networks and hybrid models in time series:tourist arrival forecasting. Journal of Statistical Computation and Simulation.2007,1.
[34]Tine Lefebvre, Herman Bruyninckx, Joris De Schutter. Kalman filters for non-linear systems:a comparison of performance. Inernational of Control.2004,05.
[35]杨汉生,吕家云,李明等.一种拟合型的提升小波预测方法.系统仿真学报.2006,9.
[36]Hans-Jurgen Sebastian, Ralf Schleiffer. Using computational intelligence in fuzzy engineering design. Cybrnetics and Systerms,2004,7.
[37]He Xinggui. Fuzzy Computational Reasoning and Neural Networks. Proceedings of the Second International Conference on Tools for Artificial Intelligence, Herndon VA.1990:706-711.
[38]余有明,刘玉树.进化计算的理论与算法.计算机应用研究,2005,09.
[39]周春光,梁艳春.计算智能.吉林：吉林大学出版社(第二版),2008.
[40]De Castro, L. N.&Von Zuben, F. J. Immune and Neural Nerwork Models:Theoretical and Empirical Comparisons. International Journal of Computational Intelligence and Applications-IJCIA.2001,1(3):239-257.
[41]Marco Dorigo, Vittorio Maniezzo, Alberto Colorni. The Ant System:Optimization by a colony of cooperationg agents. IEEE Transactions on Systems, Man, and Cybermetics-Part B,1996,1-13.
[42]Hui Gao, Jianyu Zhao, Lei Jia. Short-term Traffic Flow Forecasting Model of Elman Neural Network Based on Dissimilation Particle Swarm Optimization,2008 IEEE International Conference on Networking, Sensing and Control, Sanya, 2008,4:1305-1309.
[43]孔金生,赵长伟,万百五.网络拥塞的智能化适应控制方法.系统工程与电子技术,2005,07.
[44]http://blog.sina.com.cn/s/blog_5fc3da040100luh3.html
[45]于斌,孙斌等.NS2与网络模拟.人民邮电出版社.2007年4月.
[2]Xing Fan, Magnus Jonsson, and Jan Jonsson. Guaranteed real-time communication in packet-switched networks with FCFS queuing. Computer Networks,2009,53(3):400-417.
[3]Jingyi He, and S.-H. Gary Chan. TCP and UDP performance for Internet over optical packet-switched networks. Computer Networks,2004,45(4):505-521.
[4]Walter Goralski. The Illstrated Network:How TCP/IP Works in a Modern Network. Publisher Elsevier.2009,321-344.
[5]Anunay Tiwari, Anirudha Sahoo. Providing QoS in OSPF based best effort network using load sensitive routing. Simulation Modelling Practice and Theory,2007, 15(4):426-428.
[6]http://image.cnki.net/bigImage.aspx?T=CNKIIMAGE&id=2864369.
[7]刘宴兵,刘蕾.基于ARED排队算法的定性探讨.计算机科学,2004,09.
[8]Chang-Kuo Chen, Hang-Hong Kuo, Jun-Juh Yan, Ten-Lu Liao. GA-based PID active queue management control design for a class of TCP communication networks. Expert Systems with Applications,2009,36(2):1903-1913.
[9]方远舟.对FRED算法的改进及其实现[硕士学位论文],成都：电子科技大学,2005.
[10]文宏,李仲宇,吴海波,唐玉华.一种基于路由器队列法则的增加SRED算法.计算机应用与软件,2007,11.
[11]朱国晖,张煜,赵季红.一种改进AVQ的主动队列算法.陕西科技大学学报,2006,24(6).
[12]Wang Hao, Ma Xuetao, Tian Zuohua. A Fuzzy Self-tuning Random Exponential Marking Algorithm Based on Enhanced Price. Computer Simulation,2009,08.
[13]孔金生,赵长伟,万百五.网络拥塞的智能化适应控制方法.系统工程与电子技术,2005,07.
[14]NB. Behsaz, P Gburzynski, M. MacGregor. Transport-independent fairness. Computer Networks,2009,53(14):2444-2457.
[15]Chen Liu, Qing-pu Zhang, Xue Zhang. Emergence and disappearance of traffic congestion in weight-evolving networks. Simulation Modelling Practice and Theory,2009, 17(10):1566-1574.
[16]Baochun Bai, Janelle Harms, Yuxi Li. Configurable active multicast congestion control. Computer Networks,2008,52(7):1410-1432.
[17]Yueping Zhang, Saurabh Jain, Dmitri Loguinov. Towards experimental evaluation of explicit congestion control.Computer Networks,2009,53(7):1027-1039.
[18]Hyun-Wook Jin, Chuck Yoo. Impact of protocol overheads on network throughput over high-speed interconnects:measurement, analysis, and improvement. Journal of Supercomputing,2007,42(1):17-40.
[19]R Jain, A Durresi, G Babic. Throughput Fairness Index:An Explanation, ATM Forum/99-0045
[20]M Jaffe, Bottleneck Flow Control. IEEE Transactions on Communication,1981,29 (7):954-62.
[21]Kounavis M E, Campbell A T, etl. The genesisi Kernel:Apropramming system for spawning network architectures. IEEE Jouranl on Selected Areas in Communications, 2001,19(3):511-526.
[22]蒋启明,乐光学,于述春.基于事件的主动队列管理研究,微型计算机信息.2010,12.
[23]A. Koubaa, Y. Q. Song. Evaluation and improvement of response time bounds for real-time applications under non-pre-emptive Fixed Priority Scheduling. Internaltional Journal of Production Research.2004,7.
[24]H. Y. K. Lau, S.O. Woo. An agent-based dynamic routing strategy for automated material handing systems. International Journal of Computer Integrated Manufacturing.2007,3.
[25]邹雪兰,刘伟彦,孙雁飞.一种基于速率的公平队列管理算法.计算机工程.2009,3.
[26]Yang C, Reddy A. Taxonomy for Congestion Control Algorithms in Packet Switching Networks. IEEE Network Magazine,1995,9:34-35.
[27]Thompson, K., Miller, G. J., Wilder, R. Wide-Area Internet Traffic Patterns and Characteristics. IEEE Nerwork,1997,11(6):10-23.
[28]E. C. Park, H. lim, K. J. Park, etc. Analysis and Design of the Virtual Rate Control Algorithm for Stabilizing Queues in TCP Networks. Computer Networks,2004,44(1):17-41.
[29]J. Aweya, M. Ouellette, and D. Y. Montuno. A Contrlo Theoretic Approach to Active Queue Management. Journal of Computer Networks,2001,36(2):203-235.
[30]Chennian Long, Bin Zhao, Xinping Guan, etc. The YELLOW Active Queue Management Algorithm. Journal of Computer Networks,2004.
[31]袁小坊,王东,谢高岗等.高速网络流量特性与流数据库设计.计算机工程与应用,2009年2月,45(13)：2627.
[32]K. Park, W Willinger. Self-similar network traffic and performance evaluation. Wiley Iner-science, NewYork,2000.
[33]Atilla Aslanargun, Marnmadagha Marnmadov, Bema Yazici, et al. Comparison of ARIMA, neural networks and hybrid models in time series:tourist arrival forecasting. Journal of Statistical Computation and Simulation.2007,1.
[34]Tine Lefebvre, Herman Bruyninckx, Joris De Schutter. Kalman filters for non-linear systems:a comparison of performance. Inernational of Control.2004,05.
[35]杨汉生,吕家云,李明等.一种拟合型的提升小波预测方法.系统仿真学报.2006,9.
[36]Hans-Jurgen Sebastian, Ralf Schleiffer. Using computational intelligence in fuzzy engineering design. Cybrnetics and Systerms,2004,7.
[37]He Xinggui. Fuzzy Computational Reasoning and Neural Networks. Proceedings of the Second International Conference on Tools for Artificial Intelligence, Herndon VA.1990:706-711.
[38]余有明,刘玉树.进化计算的理论与算法.计算机应用研究,2005,09.
[39]周春光,梁艳春.计算智能.吉林：吉林大学出版社(第二版),2008.
[40]De Castro, L. N.&Von Zuben, F. J. Immune and Neural Nerwork Models:Theoretical and Empirical Comparisons. International Journal of Computational Intelligence and Applications-IJCIA.2001,1(3):239-257.
[41]Marco Dorigo, Vittorio Maniezzo, Alberto Colorni. The Ant System:Optimization by a colony of cooperationg agents. IEEE Transactions on Systems, Man, and Cybermetics-Part B,1996,1-13.
[42]Hui Gao, Jianyu Zhao, Lei Jia. Short-term Traffic Flow Forecasting Model of Elman Neural Network Based on Dissimilation Particle Swarm Optimization,2008 IEEE International Conference on Networking, Sensing and Control, Sanya, 2008,4:1305-1309.
[43]孔金生,赵长伟,万百五.网络拥塞的智能化适应控制方法.系统工程与电子技术,2005,07.
[44]http://blog.sina.com.cn/s/blog_5fc3da040100luh3.html
[45]于斌,孙斌等.NS2与网络模拟.人民邮电出版社.2007年4月.