多路径传输中乱序与负载均衡研究
详细信息    本馆镜像全文|  推荐本文 |  |   获取CNKI官网全文
摘要
多径传输使用多条连接流分割节点和流汇聚节点的路径进行传输。相对于传统的单径传输,多径传输具有充分利用网络资源、减少拥塞、提高传输可靠性和提高网络的安全性等优点,是近几年网络领域的一个研究热点。但是由于每条并行路径的传输延迟存在差别,因此从流分割节点按序发出的包到达流汇聚节点时可能是乱序的;此外,在多条并行的路径上传输数据包存在流量在各条路径间的负载均衡问题:而乱序和路径间的负载不均衡都会给传输速率、服务质量和网络资源的利用率等带来不利影响,因而对保证包有序和实现负载均衡的流量分割算法的研究具有重要的意义。
     目前多径流量分割算法的研究主要集中在包有序和路径间的负载均衡其中的一个点上,即使有少量的算法是两者都关注到,并且在保证包有序的基础上实现了一定程度的负载均衡,但由于流分割的粒度过于粗糙,其负载均衡性不是很好。本文首先分析了乱序对网络性能带来的不利影响,然后介绍了目前已经提出的几种多径流量分割算法,并分析了它们的优缺点。在此基础上,本文提出了一种新的流量分割算法,其在保证包有序的同时,尽可能细粒度地在路径间分割流从而很好地实现路径间的负载均衡。该算法主要通过构建用作可用路径延迟底线的游标来实现,游标主要取决于两个参数一当前路径传输延迟和相邻包到达流分割节点的时间间隔,它作为选取路径的延时基线来保证包到达的有序性;游标会随着每次选取的路径不同或相邻包到达流分割节点的时间间隔不同而动态地滑动,通过动态滑动游标使得尽可能多的路径可用来传输当前包,从而很好地实现负载均衡。通过对目前已经提出的流量分割算法和基于游标的流量分割算法进行跟踪驱动模拟,仿真结果表明,与已有的保证包有序的流量分割算法相比,本算法使负载更加均衡。
Multi-path transmission, using several paths between the diverging point and the converging point, is used to transmit packet. Compare to the traditional single path transmission, multi-path transmission can make the best of network resources, reduce the congestion, improve the transmission reliability and security, etc. Therefore, it is a research hotspot in network field. Because of the delay deference between the parallel paths, the packets reaching the converging point will be out of order while they are sent orderly at the diverging point; in addition, multi-path transmission will present some problems about load balancing among the paths; furthermore, reordering and unbalanced load have adverse effects upon transmission rate, quality of service, the utilization rate of resources, etc. So, it is be of great significance to do some research on traffic splitting algorithm, which can guarantee the order of packets and realize the load balancing.
     At present, the issue of researching on traffic splitting algorithm mainly focuses on one of the two points, guaranteeing the order of packets and load balancing, although little of them focus on them together, the performance of load balancing is not very good because of the coarse grain of traffic splitting. This paper first analyzes the adverse effects upon the network performance resulted from out of order, and then introduces several traffic splitting algorithms and analyzes their merits and flaws. On this basis, this paper proposes a new traffic splitting algorithm, which can achieve good load balancing by splitting traffic into flow slices as fine-grained as possible. The new algorithm is mainly carried out by constructing a nonius which can be used as a baseline of path latency. The nonius, which is used to guarantee the order of packets, mainly depends on two parameters, the path latency and the interval between two successive packets. The nonius can slide dynamically because of different path or the different interval between two successive packets. By sliding dynamically, the packet can be transmitted among as many paths as possible; as a result, the load balancing can be achieved. Through trace driven simulation of the traffic splitting algorithm based on nonius and other existed traffic splitting algorithms, the simulation results show that the proposed algorithm gains a prominent improvement in load balancing over previous algorithms, while without reordering is guaranteed.
引文
[1] P. P. Pham and S. Perreau. Performance Analysis of Reactive Shortest Path and Multi-Path Routing Mechanism with Load Balance. Proceedings of IEEE INFOCOM 2003, Vol. 1. San Francisco: IEEE Press, 2003: 251-259.
    [2] Changming Ma, Ka-Cheong Leung. Improving TCP Reordering Robustness in Multipath Networks. 29th Annual IEEE International Conference on Local Computer Networks. Texas: Texas Technology University, 2004: 409 - 410.
    [3] Lee P.P.C., Misra V., Rubenstein D. Distributed Algorithms for Secure Multipath Routing in Attack-Resistant Networks. IEEE/ACM Transactions on Networking(TON), 2007, 15(6): 1490-1501.
    [4] S. Savage, A. Collins, E. Hoffman, J. Snell, and T. Anderson. The end-to-end effects of internet path selection. SIGCOMM Computer Communication Review,1999,29(4):289-299.
    [5] Renata Teixeira, Keith Marzullo, et al., Characterizing and Measuring Path Diversity of Internet Topologies. Joint International Conference on Measurement and Modeling of Computer Systems. New York: ACM Press, 2003: 304-305.
    [6] Gernot Schmied. Integrated Cisco and UNIX Network Architectures. Cisco Press, September 2004
    [7] C. Hopps. Analysis of an Equal-Cost Multi-Path Algorithm. RFC2992,November 2000.
    [8] D. Thaler. Multipath Issues in Unicast and Multicast Next-Hop Selection.RFC2991, November 2000.
    [9] C. Villamizar. OSPF Optimized Multipath (OSPF-OMP). Internet Draft, October 1998.
    [10]C. Villamizar. IS-IS Optimized Multipath (ISIS-OMP). Internet Draft, February 1999.
    [11]C. Villamizar. MPLS Optimized Multipath MPLS-OMP). Internet Draft, February 1999.
    [12]Minlan Yu,Yung Yi,Jennifer Rexford,Mung Chiang.Rethinking virtual network embedding:substrate support for path splitting and migration.ACM SIGCOMM Computer Communication Review,2008,38(2):17-29.
    [13]汪斌强,邬江兴.下一代互联网的发展趋势及相应对策分析.信息工程大学学报,2009,10(1):1-6
    [14]王浩学,汪斌强,于婧,姜明.一体化承载网络体系架构研究.计算机学报,2009,32(3):371-376.
    [15]吴春明,张栋,姜明.面向服务提供的一体化承载网体系结构的探讨.信息工程大学学报,2009,10(1):23-27
    [16]Jeffrey C.Mogul.Observing TCP dynamics in real networks.Applications,Technologies,Architectures,and Protocols for Computer Communication.New York:ACM Press,1992:305-317.
    [17]K.-C.Leung,V.O.K.Li and D.Yang.An Overview of Packet Reordering in Transmission Control Protocol(TCP):Problems,Solutions,and Challenges.IEEE Transactions on Parallel and Distributed Systems.2007,18(4):522-535.
    [18]J.Bellardo,S.Savage.Measuring packet reordering.Internet Measurement Conference.New York:ACM Press,2002:97-105.
    [19]J.Bennett,C.Partridge,and N.Shectman.Packet Reordering is not a Pathological Network Behavior.IEEE/ACM Transactions on Networking(TON).1999,7(6):789-798.
    [20]V.Paxson.End-to-end Routing Behaviour in the Internet.Proceedings of ACM SIGCOMM'96.New York:ACM Press,1996:25-39.
    [21]Jim Duffy.Someone's having core router problems,but who is it?,November 2000.http://www.networkworld.com/edge/news/2000/1109routerprob.html
    [22]胡晓峰,孙志刚,苏金树.基于NewReno拥塞控制机制的TCP分组乱序影响分析.计算机工程与科学,2009,31(5):8-12.
    [23]Sharad Jaiswal,Gianluca Iannaccone.Measurement and Classification of Out-of-Sequence Packets in a Tier-1 IP Backbone.IEEE/ACM Transactions on Networking.2007,15(1):54-66.
    [24]Information Sciences Institute University of Southern California.Internet protocol.RFC791,September 1981.
    [25]S.Deering and R.Hinden.Internet protocol,version 6(IPv6) specification.RFC 2460,December 1998.
    [26]V.Paxson.End-to-end Internet packet dynamics.IEEE/ACM Transactions on N etworking(TON).1999,7(3):277-292.
    [27]Jie Feng,Zhipeng Ouyang,Lisong Xu,Byrav Ramamurthy.Packet reordering in high-speed networks and its impact on high-speed TCP variants.Computer Communications.2009,32(1):62-68.
    [28]Stephan Bohacek,Joao P.Hespanha,Junsoo Lee,et al.A new TCP for persistent packet reordering.IEEE/ACM Transactions on Networking(TON).2006,14(2):369-382.
    [29]A.Jayasumana,N.Piratla,T.Banka,et al.Improved Packet Reordering Metrics.RFC5236,June 2008.
    [30]S.Govind,R.Govindarajan and Joy Kuri.Packet Reordering in Network Processors.Parallel and Distributed Processing Symposium,2007.IPDPS 2007.IEEE International.Long Beach:IEEE Press,2007:1-10.
    [31]邵荣平.网络处理器并行处理技术研究[硕士学位论文].2003.
    [32]Ladan Gharai,Colin Perkins,Tom Lehman.Packet Reordering,High Speed Networks and Transport Protocol Performance.Computer Communications and Networks,2004.ICCCN 2004.Proceedings.13th International Conference on.Chicago:IEEE Press,2004:73-78.
    [33]W.Richard Stevens著,范建华等译.TCP/IP详解(卷1:协议).机械工业出版社.2000.
    [34]Ye Xia,David Tse.Analysis on Packet Resequencing for Reliable Network Protocols.Proc of IEEE INFOCOM'03.Chicago:IEEE Press,2003:990-1000.
    [35]S.Floyd.High Speed TCP for Large Congestion Windows.RFC 3649,December 2003.
    [36]L.Xu,K.Harfoush,and I.Rhee.Binary increase congestion control for fast long-distance networks. In Proceedings of IEEE INFOCOM. Hong Kong: IEEE Press, 2004: 2514-2524.
    [37] C. Semeria. Internet Processor II ASIC: Rate limiting and traffic policing features. White paper, Juniper Networks, 2000.http://www.juniper.net/solutions/literature/white_papers/200005.pdf.
    [38]Bare A.A., Jayasumana A.P. and Piratla N.M.. On Growth of Parallelism within Routers and Its Impact on Packet Reordering. 15th IEEE Workshop on Local & Metropolitan Area Networks. Princeton: IEEE Press, 2007: 145-150.
    [39] M. Laor and L. Gendel. The effect of packet reordering in a backbone link on application throughput. IEEE Network. 2002,16(5): 28-36.
    [40] Colin M. Arthur, Demessie Girma, et al. The Effects of Packet Reordering in a Wireless Multimedia Environment. 1st International Symposium on Wireless Communication Systems. UK:IEEE Press, 2004: 453-457.
    [41]Iain E. G. Richardson. Video Codec Design. Wiley. 2002.
    [42] M. Shreedhar and G. Varghese. Efficient fair queueing using deficit round robin. IEEE/ACM Transactions on Networking (TON). 1996,4(3): 375-385.
    [43] Chan K, Baker F, Babiarz J. Configuration Guidelines for DiffServ Service Classes. RFC4594,2006.
    [44]Jiayue He, Jennifer Rexford. Toward internet-wide multipath routing. IEEE Network, 2008,22(2): 16-21.
    
    [45]陈均华, 吴春明, 姜明. 互联网业务特性概述. 信息工程大学学报, 2009,10(1 ):41-44.
    
    [46]Zhiruo Cao, Zheng Wang, Ellen Zegura. Hashing-Based Traffic Splitting Algorithms for Internet Load Balancing. CC Technical Report,GIT-CC-99-14. Atlanta: Georgia Institute of Technology. 1999: 1-21.
    
    [47] L. Berger, I. Bryskin, A. Zinin. The OSPF Opaque LSA Option. RFC5250, July 2008.
    
    [48]Papagiannakit, K. Taft, N. Diot, C. Impact of flow dynamics on traffic engineering design principles. INFOCOM 2004, Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies. California: IEEE Press, 2004: 2295 - 2306.
    [49] Yin Zhang, Lee Breslau, Vern Paxson, Scott Shenker. On the characteristics and origins of internet flow rates. Applications, Technologies, Architectures, and Protocols for Computer Communication. New York: ACM Press. 2002: 309 -322.
    [50] Matthew Roughan, Albert Greenberg, Charles Kalmanek, et al. Experience in measuring backbone traffic variability: models, metrics, measurements and meaning. Internet Measurement Conference. New York: ACM Press. 2002:91-92.
    [51]Srikanth Kandula, Dina Katabi, Shantanu Sinha, Arthur Berger. Dynamic load balancing without packet reordering. ACM SIGCOMM Computer Communication Review. 2007, 37(2): 51-62.
    [52]Zhiruo Cao; Zheng Wang; Ellen Zegura. Performance of hashing-based schemes for Internet load balancing. INFOCOM 2000, Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings.San Francisco: IEEE Press, 2000: 332 - 341.
    [53] Thomas Voice. Stability of multi-path dual congestion control algorithms.IEEE/ACM Transactions on Networking (TON), 2007,15(6): 1231-1239.
    [54] S. Floyd and V. Paxson, Difficulties in Simulating the Internet, IEEE/ACM Transactions on Networking(TON). 2001, 9(4): 392-403.
    [55] Philippe OWEZARSKI, Nicolas LARRIEU. A trace based method for realistic simulation. 2004 IEEE International Conference on Communications. San Francisco: IEEE Press. 2004: 2236-2239.

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700