大规模接入汇聚路由器复用分复用单元中的流量管理技术及实现
|
摘要
各种流媒体业务的不断涌现,使得传统IP网络“尽力而为”的服务模式越来越不能适应新型业务的传输需求,宽带流媒体业务对边缘网架构的演进提出了新要求,作为边缘网与骨干网接入点的路由器就成为保证用户端到端服务质量的关键单元。本文以ACR EMD中流量管理技术的研究与实现为课题目标,提出了一种支持区分优先级的流量管理机制并予以工程实现。该机制通过队列管理算法保证了不同优先级业务的区分丢包,通过队列调度算法保证了不同优先级业务的服务质量要求。单板测试结果表明该机制达到了ACR用户流量管理的要求。
本课题主要包含如下几方面工作;
1.通过对已有流量测量、队列管理及队列调度算法的分析比较,针对ACR的应用需求提出了一种具有良好可扩展性的区分优先级流量管理(DPTM)机制。DPTM机制由区分丢包随机早期丢弃fDDPRED)队列管理算法和基于优先级的并行分布式双调度加权轮询(PDDWRR)队列调度算法协同完成,不仅可为高优先级业务提供低时延服务,而且可为低优先级业务提供公平的输出带宽。
2.提出一种DDPRED队列管理算法,该算法为不同优先级业务设置不同的丢弃门限实现了区分优先级的包丢弃。通过对DDPRED算法数学模型的分析,给出了门限参数与丢包率及时延的函数关系,工程实现中可根据实际丢包率及时延要求灵活设置门限参数。
3.提出一种可支持变长包处理的PDDWRR队列调度算法,该算法采用双调度指针和两种优先级模式为不同优先级业务提供更细颗粒度的服务质量。通过对二维马尔可夫链典型模型的分析证明该算法可为低优先级业务提供公平的输出带宽保护,性能仿真表明PDDWRR算法的低优先级业务的丢包率及高优先级业务时延要优于DRR算法。
4.结合项目需求给出了ACR EMD中DPTM机制的硬件实现方案。DPTM机制的并行分布式虚拟优先级队列(VPQ)结构支持流水线调度,对于10Gbps的端口速率可实现数据包的线速处理。单板测试结果表明;DPTM机制完全满足ACR用户上、下行业务流量管理的要求。
Along with various Streaming Media business emerging, "Best Effort" mode of traditional IP network can not meet the demands of new businesses, and Broadband Streaming Media business will ask for the evolution of Edge network structure. Router must afford end-to-end QoS, as the access point of Backbone network and Edge network.This dissertation based on the research and implement of traffic management technology on ACR EMD, and brought forward a traffic management mechanism supported different priority. It is assured of different drop possibility of different priority business by queue management, and assured of different QoS demand for different business by queue schedule.
The main work and contributions in this dissertation are outlined as follows:
1. Analyzing and comparing some mature arithmetic such as traffic measurement, queue management and queue schedule, this thesis put forward a traffic management mechanism named DPTM with good scalability, which is aimed at application demand. This mechanism is composed of DDPRED queue management arithmetic and PDDWRR queue schedule arithmetic. It ensured low delay of high-priority business and fair output bandwidth of low-priority business.
2. Proposed DDPRED queue management arithmetic. It is used for different dropout rate of different business by setting different threshold. The function relations between threshold and dropout rate and delay is concluded, so we can set threshold flexibly in engineering according to the requirements of dropout rate and delay.
3. Proposed PDDWRR queue schedule arithmetic that can support variable-length packets. Based on double schedule guidelines and two priority modes, this arithmetic will provide fine-partical QoS for different businesses. The planar Markov chain analysis of PDDWRR proved that it is justice in output bandwidth distribution for low-priority business. The simulation results shows that low delay of high-priority business and fair output bandwidth of low-priority business of PDDWRR are better than DRR.
4. Aimed at project requirements, this dissertation presented hardware implement program of DPTM mechanism on ACR EMD. The structure of parallel distributed VPQ can support pipelining schedule, so DPTM mechanism can processed packet within wire speed for 10Gbps port. The test results of GE board shows that DPTM mechanism completely satisfied the demand for traffic management of uplink and downlink user's businesses on ACR.
本课题主要包含如下几方面工作;
1.通过对已有流量测量、队列管理及队列调度算法的分析比较,针对ACR的应用需求提出了一种具有良好可扩展性的区分优先级流量管理(DPTM)机制。DPTM机制由区分丢包随机早期丢弃fDDPRED)队列管理算法和基于优先级的并行分布式双调度加权轮询(PDDWRR)队列调度算法协同完成,不仅可为高优先级业务提供低时延服务,而且可为低优先级业务提供公平的输出带宽。
2.提出一种DDPRED队列管理算法,该算法为不同优先级业务设置不同的丢弃门限实现了区分优先级的包丢弃。通过对DDPRED算法数学模型的分析,给出了门限参数与丢包率及时延的函数关系,工程实现中可根据实际丢包率及时延要求灵活设置门限参数。
3.提出一种可支持变长包处理的PDDWRR队列调度算法,该算法采用双调度指针和两种优先级模式为不同优先级业务提供更细颗粒度的服务质量。通过对二维马尔可夫链典型模型的分析证明该算法可为低优先级业务提供公平的输出带宽保护,性能仿真表明PDDWRR算法的低优先级业务的丢包率及高优先级业务时延要优于DRR算法。
4.结合项目需求给出了ACR EMD中DPTM机制的硬件实现方案。DPTM机制的并行分布式虚拟优先级队列(VPQ)结构支持流水线调度,对于10Gbps的端口速率可实现数据包的线速处理。单板测试结果表明;DPTM机制完全满足ACR用户上、下行业务流量管理的要求。
Along with various Streaming Media business emerging, "Best Effort" mode of traditional IP network can not meet the demands of new businesses, and Broadband Streaming Media business will ask for the evolution of Edge network structure. Router must afford end-to-end QoS, as the access point of Backbone network and Edge network.This dissertation based on the research and implement of traffic management technology on ACR EMD, and brought forward a traffic management mechanism supported different priority. It is assured of different drop possibility of different priority business by queue management, and assured of different QoS demand for different business by queue schedule.
The main work and contributions in this dissertation are outlined as follows:
1. Analyzing and comparing some mature arithmetic such as traffic measurement, queue management and queue schedule, this thesis put forward a traffic management mechanism named DPTM with good scalability, which is aimed at application demand. This mechanism is composed of DDPRED queue management arithmetic and PDDWRR queue schedule arithmetic. It ensured low delay of high-priority business and fair output bandwidth of low-priority business.
2. Proposed DDPRED queue management arithmetic. It is used for different dropout rate of different business by setting different threshold. The function relations between threshold and dropout rate and delay is concluded, so we can set threshold flexibly in engineering according to the requirements of dropout rate and delay.
3. Proposed PDDWRR queue schedule arithmetic that can support variable-length packets. Based on double schedule guidelines and two priority modes, this arithmetic will provide fine-partical QoS for different businesses. The planar Markov chain analysis of PDDWRR proved that it is justice in output bandwidth distribution for low-priority business. The simulation results shows that low delay of high-priority business and fair output bandwidth of low-priority business of PDDWRR are better than DRR.
4. Aimed at project requirements, this dissertation presented hardware implement program of DPTM mechanism on ACR EMD. The structure of parallel distributed VPQ can support pipelining schedule, so DPTM mechanism can processed packet within wire speed for 10Gbps port. The test results of GE board shows that DPTM mechanism completely satisfied the demand for traffic management of uplink and downlink user's businesses on ACR.
引文
[1]张兴明.大规模接入汇聚路由器(ACR)总体技术规范[R].郑州:国家数字交换系统工程技术研究中心,2005:3-5.
[2]汪斌强,邬江兴.基于IPv6的大规模接入汇聚路由器的设想和实现[J].电信科学,2006,22(1):5-9.
[3]程光,龚俭.大规模高速网络流量测量研究[J].计算机工程与应用,2002,38(5):17-22.
[4]徐恪,徐明伟.IP分类技术研究综述[J].小型计算机系统,2002,123(7):773-779.
[5]ESTAN G,VARGHESE C,New directions in traffic measurement and accounting[A].Proceedings of ACM SIGCOMM 2002[C].Pittsburgh,Pennsylvania:2002:5-80.
[6]RFC2330.Framework for IP Performance Metrics[S].PAXSON V,ALMES G,1998.
[7]S Floyd,K Fall.Promoting the use of end-to-end congestion control in the Internet[J].IEEE/ACM Transactions on Networking,1999,7(4):458-472.
[8]W Feng,D Kandlur,D Saha,K Shin.BLUE:A new class of active queue management algorithms[R].US:University of Michigan,CSE2 TR2387299,1999.
[9]W Feng,D Kandlur,D Saha,KShin.Techniques for eliminating packet loss in congested TCP/IP networks[R].US:University of Michigan,CSE2TR2349297,1997.
[10]S Floyd,V Jacobson.Random early detection gateway for congestion avoidance[J].IEEE/ACM Transactions on Networking,1993,1(4):397-413.
[11]TJ Ott,TV Lakshman,L H Wong.SRED:Stabilized RED[A].DoshiB.Proceedings of IEEE INFOCOM[C].NewYork:IEEE Communications Society,1999:1346-1355.
[12]Wu-chang Feng,Dilip D Kandlur,Debanjan Saha.BLUE:A New Class of Active Queue Management Algorithms[R].Technical Report CSE-TR-387-99,University of Michigan,1999.
[13]Cisco Systems.Weighted Random Early Detection on the Cisco 12000 Series Router[M].2002.
[14]文宏,唐玉华,朱培栋.RED簇主动队列管理算法研究[J].计算机工程与科学,2006,28(5):66-68
[15]W Feng,D Kandlur,D Saha,K Shin.Stochastic fair blue:aqueue management algorithm for enforcing fairness[A].InProceedings of INFOCOM 2001[C].Alaska:April 2001.
[16]Chris Hollot,Vishal Misra,Don Towsley,et al.On Designing Improved Controllers for AQM Routers Supporting TCP Flows[A].Proc of IEEE INFOCOM[C].2001:1726-1734.
[17]Y.Jiang,C.K.Tham,C.C.Ko.A probabilistic priority scheduling discipline for multi-service networks[J].Proc.IEEE ISCC',2001:450-455.
[18]A.Ioannou,M.Katevenis.Pipelined heap(priority queue)management for advanced scheduling in high-speed networks[J].Proc.IEEE ICC',2001,vol.7:2043-2047.
[19]T.Y.Choe,C.Park,C.M.Park,B.S.Kim.An improved multi-priority preemptive scheduler for transputer-based real-time systems[J].Proc.the Eighth Euromicro Workshop on Real-Time Systems',1996:181-186.
[20]J.Liebeherr,D.E.Wrege.Priority queue schedulers with approximate sorting in output-buffered switches[J].IEEE Journal of Selected Areas on Communications,1999,17(6):1127-1144.
[21]A.K.Parekb,R.G.Gallager.A generalized processor sharing approach to flow control in integrated services networks:the single-node case[J].IEEE/ACM Trans.on Networking,1998:344-357.
[22]D.Still adiS,A.Varma.Efficient fair queuing algorithms for packet switched networks[J].IEEE/ACM Transactions on Networking,1998,6(2):175-185.
[23]D.C.Stephens,et al.Implimenting scheduling algorithms in high-speed networks[J].IEEE Journal on Selected Areas in Communications,1999,17(6):145-1159.
[24]王重钢,隆克平,龚向阳,程时端.分组交换网络中队列调度算法的研究及其展望[J].电子学报,2001.
[25]M.Katevenis,S.Sidiropoulos,C.Courcoubetis.Weighted round-robin cell multiplexing in a general-purpose ATM switch chip[J].IEEE Journal on Selected Areas in Communications,1997,9(8):1265-1279.
[26]M.Shreedhar,G.Varghese.Efficient fair queueing using deficit round-robin[J].IEEE/ACM Trans.on networking,1996,4(3):375-385.
[27]刘韵洁,张云勇,张智江.下一代网络服务质量技术[M].北京:电子工业出版社,2005:49-54.
[28]GOYAL,DURRESIA,JAIN LIUC.Performance Analysis of Assured Forwarding,Internet draft[S].Feb 2000.
[29]MAKKA R LAMBADARISI,HADI-SALIM J,SEDDIGH N,et al.Empirical Study of Bufer Management Schemes for DiffServ Assured Forwarding PHB[R].Nortel Copmuting Technology Lab(CTL)Technical Report,May 2000.
[30]向渝,雷维礼,黄顺吉.区分服务模型中的一种动态队列管理算法[J].通信学报,2003,24(10).
[31]RFC 2597.Assured Forwarding PHB Group[S].HEINANEN J,BAKER F,WEISS W,WROCLAWSKI J,Jun 1999.
[32]MAY M,BOLOT J-C,JEAN-MARIE A.Simple performance models for differentiated services schemes for the Internet[A].Proc INFOCOM'99[C].NY,1999:1385-1394.
[33]SAHU S,TOWSLEY D,KUROSE J.A quantitative study of differentiated services for the Internet[A].IEEE Globecom'99[C|.1999.
[34]荣恒,李建平.排队论基础[M].北京:科学出版社,2002.
[35]应辉,唐小我.排队论基础与应用[M].成都:电子科技大学出版社,2000.
[36]王敏强,刘勤让.ACR EMD千兆接口模块设计分析说明书[R].郑州:国家数字交换系统工程技术研究中心,2006:30-53.
[2]汪斌强,邬江兴.基于IPv6的大规模接入汇聚路由器的设想和实现[J].电信科学,2006,22(1):5-9.
[3]程光,龚俭.大规模高速网络流量测量研究[J].计算机工程与应用,2002,38(5):17-22.
[4]徐恪,徐明伟.IP分类技术研究综述[J].小型计算机系统,2002,123(7):773-779.
[5]ESTAN G,VARGHESE C,New directions in traffic measurement and accounting[A].Proceedings of ACM SIGCOMM 2002[C].Pittsburgh,Pennsylvania:2002:5-80.
[6]RFC2330.Framework for IP Performance Metrics[S].PAXSON V,ALMES G,1998.
[7]S Floyd,K Fall.Promoting the use of end-to-end congestion control in the Internet[J].IEEE/ACM Transactions on Networking,1999,7(4):458-472.
[8]W Feng,D Kandlur,D Saha,K Shin.BLUE:A new class of active queue management algorithms[R].US:University of Michigan,CSE2 TR2387299,1999.
[9]W Feng,D Kandlur,D Saha,KShin.Techniques for eliminating packet loss in congested TCP/IP networks[R].US:University of Michigan,CSE2TR2349297,1997.
[10]S Floyd,V Jacobson.Random early detection gateway for congestion avoidance[J].IEEE/ACM Transactions on Networking,1993,1(4):397-413.
[11]TJ Ott,TV Lakshman,L H Wong.SRED:Stabilized RED[A].DoshiB.Proceedings of IEEE INFOCOM[C].NewYork:IEEE Communications Society,1999:1346-1355.
[12]Wu-chang Feng,Dilip D Kandlur,Debanjan Saha.BLUE:A New Class of Active Queue Management Algorithms[R].Technical Report CSE-TR-387-99,University of Michigan,1999.
[13]Cisco Systems.Weighted Random Early Detection on the Cisco 12000 Series Router[M].2002.
[14]文宏,唐玉华,朱培栋.RED簇主动队列管理算法研究[J].计算机工程与科学,2006,28(5):66-68
[15]W Feng,D Kandlur,D Saha,K Shin.Stochastic fair blue:aqueue management algorithm for enforcing fairness[A].InProceedings of INFOCOM 2001[C].Alaska:April 2001.
[16]Chris Hollot,Vishal Misra,Don Towsley,et al.On Designing Improved Controllers for AQM Routers Supporting TCP Flows[A].Proc of IEEE INFOCOM[C].2001:1726-1734.
[17]Y.Jiang,C.K.Tham,C.C.Ko.A probabilistic priority scheduling discipline for multi-service networks[J].Proc.IEEE ISCC',2001:450-455.
[18]A.Ioannou,M.Katevenis.Pipelined heap(priority queue)management for advanced scheduling in high-speed networks[J].Proc.IEEE ICC',2001,vol.7:2043-2047.
[19]T.Y.Choe,C.Park,C.M.Park,B.S.Kim.An improved multi-priority preemptive scheduler for transputer-based real-time systems[J].Proc.the Eighth Euromicro Workshop on Real-Time Systems',1996:181-186.
[20]J.Liebeherr,D.E.Wrege.Priority queue schedulers with approximate sorting in output-buffered switches[J].IEEE Journal of Selected Areas on Communications,1999,17(6):1127-1144.
[21]A.K.Parekb,R.G.Gallager.A generalized processor sharing approach to flow control in integrated services networks:the single-node case[J].IEEE/ACM Trans.on Networking,1998:344-357.
[22]D.Still adiS,A.Varma.Efficient fair queuing algorithms for packet switched networks[J].IEEE/ACM Transactions on Networking,1998,6(2):175-185.
[23]D.C.Stephens,et al.Implimenting scheduling algorithms in high-speed networks[J].IEEE Journal on Selected Areas in Communications,1999,17(6):145-1159.
[24]王重钢,隆克平,龚向阳,程时端.分组交换网络中队列调度算法的研究及其展望[J].电子学报,2001.
[25]M.Katevenis,S.Sidiropoulos,C.Courcoubetis.Weighted round-robin cell multiplexing in a general-purpose ATM switch chip[J].IEEE Journal on Selected Areas in Communications,1997,9(8):1265-1279.
[26]M.Shreedhar,G.Varghese.Efficient fair queueing using deficit round-robin[J].IEEE/ACM Trans.on networking,1996,4(3):375-385.
[27]刘韵洁,张云勇,张智江.下一代网络服务质量技术[M].北京:电子工业出版社,2005:49-54.
[28]GOYAL,DURRESIA,JAIN LIUC.Performance Analysis of Assured Forwarding,Internet draft[S].Feb 2000.
[29]MAKKA R LAMBADARISI,HADI-SALIM J,SEDDIGH N,et al.Empirical Study of Bufer Management Schemes for DiffServ Assured Forwarding PHB[R].Nortel Copmuting Technology Lab(CTL)Technical Report,May 2000.
[30]向渝,雷维礼,黄顺吉.区分服务模型中的一种动态队列管理算法[J].通信学报,2003,24(10).
[31]RFC 2597.Assured Forwarding PHB Group[S].HEINANEN J,BAKER F,WEISS W,WROCLAWSKI J,Jun 1999.
[32]MAY M,BOLOT J-C,JEAN-MARIE A.Simple performance models for differentiated services schemes for the Internet[A].Proc INFOCOM'99[C].NY,1999:1385-1394.
[33]SAHU S,TOWSLEY D,KUROSE J.A quantitative study of differentiated services for the Internet[A].IEEE Globecom'99[C|.1999.
[34]荣恒,李建平.排队论基础[M].北京:科学出版社,2002.
[35]应辉,唐小我.排队论基础与应用[M].成都:电子科技大学出版社,2000.
[36]王敏强,刘勤让.ACR EMD千兆接口模块设计分析说明书[R].郑州:国家数字交换系统工程技术研究中心,2006:30-53.