摘要
网络业务的快速增长对互联网服务质量提出更高的要求,而作为业务交换节点成为制约网络性能的“瓶颈”。由于互联网络复杂的动态特性可以通过网络所承载的流量来反映,同时网络流量又是网络的动态行为的主导因素,我们希望通过路由优化对网络流量进行合理调度进而改进网络性能。因此在提高网络管理的效率以改善网络环境的运行质量逐渐成为当前网络研究热点的背景下,研究路由优化及流量合理调度以平衡网络负载的意义就显得尤为重要。
本文主要基于网络负载平衡机制,以IP网络的流量调度技术作为解决问题的切入点,基于QoS路由的动态请求的应用背景提出了分区路由寻优的快速方法;在已有路由切割流量调度算法基础上设计一种多链路时延均衡的调度方案;同时对客户端流量控制提出了一定的解决方案以达到对以达到更好的控制进/出网络的流量,保证关键业务的服务质量,限制非关键业务的带宽,从而提高整个网络的运行质量。论文的主要贡献如下:
(1)有限节点的复杂路由寻优的快速分区方法
提出了采用预计算方法,预先对网络分几个区间,计算满足这几个区间的约束请求的可行路径,然后根据应用请求服务模式,选择合适的转发路由。即将路由问题分成与实际请求无关的可行路径计算和与实际请求相关的路由优化选择两部分。
(2)提出了一种基于时延差异目标迭代的变尺度算法
为了在原始的切割调度样本中更精确地二次调整碎片的大小和数量,使得网络在N个链路之间保持一个比较平衡的时延差异,本文提出一种基于时延差异目标迭代的变尺度求解优化方法。
(3)给出了宽带接入与流量管理系统的设计方案
本文给出了流量调度器的设计方案,其不仅起到边界网关或者边界路由器的作用,而且可以按照预定的调度算法将合适的流量分配给相应上联路出口,从而以减轻服务器压力,降低对服务器的硬件和软件要求。
(4)对基于流量控制技术客户端流量控制进行了探究并提出解决方案
结合某大学实际网络情况进行PPPoE专用拨号客户端的分析,并在此基础上实现流量过滤功能的研究和探讨并进行一定的设计,其可以检测客户端的一些异常流量,并起到流量过滤作用,保证局域网正常用户或同一用户中关键业务的应用得到应有得服务。
The rapid growth of the business on the internet leads to the requirement for more better performance of QoS (Quality of Service) on Internet. The links and nodes for transmitting data in the network has become the bottleneck of business development. Meanwhile that the dynamic characteristics can be reflected by the network traffic being taken into consideration, so we hope to improve the performance of the network by routing optimization and planning and scheduling for the network traffic, against the background of improving the quality of the environment that rely on the efficiency of network's management is extremely popular, we study routing optimization and the schedule for traffic based on the load balancing will be also impartment.
This paper focus on routing optimization and planning and scheduling for the network traffic based on the mechanism of load balancing and presents schemes for parallel routing computing based on routing optimizing and scaleable optimization based on Iterating for delay, also gives some strategy of client traffic control, which ensures that critical business quality of service and restrictions on non-critical operations of the bandwidth, so as to enhance the performance of the entire network. And the main contribution of papers are as follows:
(1) A scheme for parallel routing computing based on routing optimizing by partition has been proposed
The method of pre-computing for routing is proposed. The network will be partitioned into several sections and the feasible paths which satisfy the constrained requests of the partitions will be worked out, then the suitable routing for forwarding will be selected according to the service mode of applications requesting. That's the routing problem can be divided into two parts: feasible path computing unconcerned with practical routing request and route optimizing related to practical routing request.
(2) A scheme for scaleable optimization based on Iterating for delay is proposed
In order to more accurately achieve the size and the amount of the chips in the second adjusting among the samples of the original splitting scheduling , and keep the links of the networks be a balance state on delay variation. a scheme for scaleable optimization based on Iterating for delay variation will be proposed in this paper.
(3) the design and implementation of solutions to the system of broadband access and traffic management system has been proposed
This paper gives a design for traffic scheduler, which not only play a role of border gateway, but also border router. It can allocate the appropriate flow to the corresponding link exports according to the predetermined scheduling algorithm, which could reduce the pressure of servers, lower the standard of server hardware and software.
(4) Some solutions about flow control technology based on client traffic control as well as some reviews have been presented
Based on the actual network of a university, the paper gives some analysis on the protocol of dial-up PPPoE client, also proposed some valuable design about flow filtration, which can detect some abnormalities flow and ensure that business-critical application request can be serviced among the normal user or LAN users.
引文
[1]庞辽军,王力,李慧贤.基于集群技术的Linux虚拟服务器.计算机工程与应用,2003,39(14):161-163
[2]Huan-Yun Wei,Shih-Chiang Tsao,Ying-Dar Lin.Assessing and Improving TCP Rate Shaping over Edge Gateways.IEEE TRANSACTIONS ON COMPUTERS,VOL.53,NO.3,MARCH 2004
[3]James Aweya,Michel Ouellette,Delfin Y.Montuno,Zhonghui Yao.Enhancing Network Performance with TCP Rate Control.IEEE/ACM TRANSACTIONS ON NETWORKING,2000
[4]Anna Charny,An Algorithm for Rate Allocation in a Packet-Switching Network with Feedback.Massachusetts Institute of Technology,1994.5
[5]Dina Katabi,Mark Handley,Charlie Rohrs.Internet Congestion Control for Future High Bandwidth-Delay Product Environments.IEEE/ACM TRANSACTIONS ON NETWORKING,2001
[6]Sun B.L.,Yin X.H.,Li L.Y..Optimizing fuzzy controllers for QoS improvement in diffServ networks[A].In:Proceedings of the 7th Joint Conference on Information Sciences(JCIS2003)[C].Cary,North Carolina:2003,521-525
[7]林闯,单志广,任丰原.计算机网络的服务质量(QoS)[M].北京:清华大学出版社,2004:210-226
[8]程伟,卢泽新,王宏.一种新的服务器集群系统负载均衡技术[A].计算机工程与科学[J].2006,28(2):31-47
[9]张帆,袁道华,叶振,等.基于Linux的服务器集群系统设计及实现[A].计算机工程与应用[J].2006(14):127-131
[10]Tarek Saad,Tingzhou Yang,Dimitrios Makrakis,et.al.Inter-domain adaptive traffic engineering for IP differentiated services mpls-based networks[A].IN:Proceedings of the 2002 IEEE Canadian Conference on Electrical & Computer Engineering[C].2002:1527-1531
[11]华静.IP城域网数据流状念的检测和流量控制技术研究[D].上海交通大学硕士学位论文.27-41
[12]张卫东,王伟,韩维桓.网络流量测量与监控系统的设计与实现[A].计算机工程与应用[J].2005,(32):160-163
[13]http://www.ietf.org/rfc/rfc2001.txt
[14]Jack Drobisz,Kenneth J Christenesen.Adaptive Sampling.Methods to Determine Network Traffic Traffic Statistics including the Hurst Parameter[C].In:Proceedings of 23st Annual Conference on Local Computer Networks,1998
[15]V Paxson,G Almes,Mahdavi,et al.Framework for IP Performance Metrics[S].IETF RFC 2330.1998
[16]程光,龚俭.大规模高速网络流量测量研究[A].计算机工程与应用[J].2002(5):17-19
[17]聂荣,张兴兰,雷振明.关于实时网络流量测量的研究[A].电信科学[J].2004(9):71-75
[18]黄鑫,尹宝林.基于聚集流量分类的流量型DoS攻击防御方法[A].计算机工程[J].2005,31(18):132-134
[19]Palis M A.The granularity metric for fine-grain real-time scheduling[J].IEEE Trans on Computers,2005,54(12):1572-1583
[20]Kuo T W,Yang W R,Lin K J.A class of rate-based real-time scheduling algorithms[J].IEEE Trans on Computers,2002,51(6):708-720
[21]W Feng.D Kandlur,D Saha,K Shin.Techniques for eliminating packet Loss in Congested TCP/IP network[R].US:University Of Michigan,CSE-YR-349-97,1997
[22]STEVENS W.TCP slow start,congestion avoidance,fast retransmit and fast recovery algorithms[J].RFC,2001,1997,01
[23]Cisco Corp.Weighted Random early detection(WRED)on the Cisco 12000 series router [DB/OL].http://www.cisco.com/univercd/cc/td/doc/product/software/ios112p /gsr/wred_gs.pdf
[24]杨晓萍,陈虹,冷晶艳.WRED和RIO-C两种区分服务机制[A].计算机应用[J].2005,vol 25:1-3
[25]李典斌,刘星沙,夏明伟.QoS队列调度算法研究及应用[A].网络安全技术与应用[J].2007:69-71
[26]Greenberg A C,Madras N.How fair is fair queuing ?[J].The Journal of ACM,1992,(3):568-598.
[27]H.Zhang,D.Ferrari.Rate-controlled static-priority queueing.In:Proceedings.Annual Joint Conference of the IEEE Computer and Communications Societies.Networking:Foundation for the Future.IEEE,1993 Vol.1,Page(s):227-336
[28]Parekh A K,Gallagher R G.A Generalized processor sharing approach to flow-control in integrated services networks:The single node case.IEEE/ACMTrans on Networking,1994,2(2):137-150
[29]Zeng H X,Xu D Y,Dou J.On physical frame time2slot switching over DWDM[A].In:Proceedings of PACAT03[C].Chengdu:IEEE Press,2003.535-540.
[30]ShreedharM.Efficient fair queuing using deficit round2robin[J].IEEE/ACM Trans on Networking,.1996,4(3):375-385.
[31]陈展荣,徐娟,禹智涛.一种基于漏桶算法的模糊流量控制器的设计[A].广东工业大学学报[J].2003,20(1):18-52
[32]陈彪,姚庆栋.VBR流令牌桶流量整形的研究[A].浙江大学学报[J].2004,38(4):443-446
[33]聂荣.关于实时网络流量测量的研究[A].电信科学[J].2004,20(9):71-75.
[34]蔡伟祥,等.流量采集在网络性能监测与分析系统中的改进和实现[J].计算机工程,2003,29(15):58-59
[35]Shaikh A,Rexford J.,Shin K.G..Evaluating the impact of stale link state on quality-of-service routing[J].IEEE/ACM Transactions on Networking,2001,(9):162-176
[36]Ergun F.,Sinha R.,Zhang L..QoS routing with performance-dependent costs[A],In:Sidi,M.ed.Precedings of the IEEE INFOCOM'00[C].Israel:IEEE Communication Society,2000:137-46
[37]Fortz B.,Thorup M..Internet traffic engineering by optimizing OSPF weights[A].In:Sidi,M.ed.Precedings of the IEEE INFOCOM'00[C].Israel:IEEE Communication Society,2000:519-28
[38]Juttner A.,Szviatovski,Mecs B.I.,et al.Lagrange relaxation based method for the QoS routing problem[A].In:Sengupta,B.ed.Precedings of the IEEE INFOCOM'01.Piscataway,NJ:IEEE Communication Society,2001:859-868
[39]Nelakuditi S.,Zhang Z.,Tsang R.P..Adaptive proportional routing:a localized QoS routing approach[A].In:Sidi,M.ed.Precedings of the IEEE INFOCOM'00[C].Israel:IEEE Communication Society,2000:1566-1575
[40]Yuan X.,Liu X..Heuristic algorithms for multi-constrained quality of service routing [A].In:Proceedings of the IEEE INFOCOM 2001[C],Piscataway,NJ:IEEE Communication Society,2001:844-853
[41]Korkmaz T.,Krunz M..Multi-constrained optimal path selection[A].In:Proc of the IEEE INFOCOM 2001[C].Conference Proc.Anchorage,Alaska:IEEE Communication Society,2001:834-843
[42]Wang Z.,Crowcroft J..QoS routing for supporting resource reservation[J].IEEE J SAC,1996,14(7):1228-1234
[43]Cidon I.,Rom R.,Shavitt Y..Multi-path routing combined with resource reservation[A].In:Proceedings of IEEE INFOCOM'97[C],Japan,1997:92-100
[44]Shin K.G.,Chou C.C..A distributed route-selection scheme for establishing real-time channel[A].In:Proceedings of the 6th IFIP International Conference High Performation Networking[C],Ireland:1995:319-329
[45]Chen S.,Nahrstedt K..Distributed quality-of-service routing in High-speed networks based on selective probing[A].In:Proceedings of the 23rd Annual Conference on Local Area Networks(ICN'98)[C],Boston,MA,1998:80-89
[46]Van Mieghem P.,Kuipers F.A..Concepts of exact QoS routing algorithms[J].IEEE/ACM Transactions on Networking,2004,12(5):851-864
[47]冯径、周润芳、顾冠群.一种分类预计算QoS路由算法[J].软件学报,2002,13(4):591-600
[48]Zegura E.,Calvert K.L.,Bhattacharjee S..How to model an internetwork[A].In:Sohraby K,ed.Proceedings of the IEEE Infocom'96[C].San Francisco,CA:IEEE Computer Society Press,1996:594-602
[49]Devine Karen D.,Boman Erik G.,Heaphy,Robert T.,et al.New challenges in dynamic load balancing[J].Applied Numerical Mathematics.2005,(52):133-152
[50]Lu P.,Gao Q.Y.,Liu X.D.,et al.Routing and load balancing techniques for a content-based publish/subscribe system[J].Transaction of Beijing Institute of Technology,2006,26(11):969-973
[51]Dobber Menno.,Koole Ger.,Van Mei Rob Der..Dynamic load balancing experiments in a grid[A].In:Proceedings of CCGrid 2005[C].IEEE International Symposium on Cluster Computing and the Grid,2005,(2):1063-1070
[52]Elwalid A.,Jin C.,Low S.,et al.MATE:MPLS adaptive traffic engineering[A].In:Proceedings-IEEE INFOCOM[C].2001,(3):1300-1309
[53]Dinah E.,Awduche D.,Jabbari B..Analytical framework for dynamic traffic partitioning in MPLS networks[A].In:Proceedings of IEEE International Conference on Communications[C].2000,(3):1604-1608
[54]Dinan E.,Awduche D.,Jabbari B..Optimal Traffic Partitioning in MPLS[A].In:Networking 2000(Net2000)[C].Paris,France:Net2000,2000
[55]秦勇,多解空间N元非合作性流量切割调度算法研究[J],计算机工程,2006,5(32):86-88.
[56]Jain M.,Dovrolis C..End-to-end Available Bandwidth:Measurement Methodology,Dynamics,and Relation with TCP Throughput[A].In:Proceedings of the ACM SIGCOMM 2002 Conference-Applications,Technologies,Architectures,and Protocols for Computer Communications[C].Computer Communication Review,2002,32(4):295-308.
[57]Hu N.N.,Steenkiste P..Evaluation and Characterization of Available Bandwidth Probing Techniques[J].IEEE Journal on Selected Areas in Communications.2003,21(6):879-894.
[58]Papagiannaki K.,Moon S.,Fraleigh C..Measurement and analysis of single-hop delay on all IP backbone network[J].IEEE Journal on Selected Areas in Communications,2003,21(6):908-921.
[59]Gruber F.,Karrenberg D..Providing active measurements as a regular service for ISP'S [A].In:Proc.of the Passive and Active Measurement Workshop 2001(PAM 2001)[C]. Amsterdam:RIPE NCC,2001:51-62.
[60]Aashtiani H.Z.,Magnanti T.L..Equilibria on a congested transportation networks[J].SIAM Journal on Algebraic and Discrete Methods,1981,(2):213-226.
[61]Ramon Fabregat,Yezid Donoso,Yezid Donoso.Multi-objective optimization scheme for multi-cast flows:a survey,a model and a MOEA solution.ACM,2005,10:73-86
[62]吴云波,李志蜀,吴云海.支持Internet实时多媒体应用的Overlay技术研究.计算机科学2006,33(4):118-129
[63]庞辽军,王力,李慧贤.基于集群技术的Linux虚拟服务器.计算机工程与应用,2003,39(14):161-163
[64]郭建新,李冀,魏明亮.基于簇结构的分层调度器的设计和实现.计算机科学.2001,28(4):29-33
[65]Bert Hubert等.Linux的高级路由和流量控制HOWTO.2005:36-58
[66]Qie XH,Bavier A,Peterson L,Karlin S.Scheduling computations on a software-based router.ACM SIGMETRICS Performance Evaluation Review,2001,29(1):13-24
[67]Zhongiu Zhang,Weiguo Fan.Web server load balancing:A queuing analysis[J].European Journal of Operational Research.
[68]PPP over Ethernet:A Comparison of Alternatives for PC-to-xESL Modem Connectivity [EB/OL].
[69]RFC2516.http://www.faqs.org/rfcs/rfc2516.html
[70]J Juha Heinanen.Multi-protocol Encapsulation over ATM Adaptations Layer 5[s].RFC1483
[71]K Lidl,J Evarts,et al.A Method for Transmitting PPP Over Ethernet(PPPoE)[S].RFC 2516
[72]乐德广,郭东辉,吴伯僖.PPPoE技术及其在宽带接入系统中的应用[J].计算机应用研究.2003:130-136
