A self-adaptive key flow routing adjustment algorithm

Abstract

Congestion may decrease throughput and transfer efficiency of network, and lead to serious degradation of quality of service (QoS) acquired by end users. Present routing adjustment methods against congestion mostly consider single-point congestion. They cannot deal with multi-point congestion. This paper presents a probability-based routing adjustment algorithm, which solves the interference problem when several flows are adjusted simultaneously. While multiple points in the network are being or about to be congested, several key flows are rerouted by this algorithm at the same time to make traffic distribution more reasonable so as to avoid congestion. Meanwhile, the algorithm in this paper confines the path length of key flows to avoid QoS reduction due to overlength of key flows. Simulation shows that this method, compared with present algorithms, maintains better load balance and path length. Therefore it effectively increases the throughput of the network.

Key words： network management; load balancing; quality of service (QoS); routing adjustment

Acknowledgements

This work was supported by the National Natural Science Foundation of China (Grant Nos. 90604019 and 60502037), and the National High Technology Research and Development Program of China (Nos. 2006AA01Z235 and 2007AA01Z206), the Specialized Research Fund for the Doctoral Program of Higher Education of China (No. 200800131019), and Program for New Century Excellent Talents in University.

References

1 Broido A, Hyun Y, Gao R, Claffy K C. Their share: diversity and disparity in IP traffic. In: Proceedings of Passive and Active Network Measurement. Lecture Notes in Computer Science. Berlin: Springer, 2004, 3015: 113-125

2 Willinger W, Alderson D, Li L. A pragmatic approach to dealing with high-variability in network measurements. In: Proceedings of the 4th ACM SIGCOMM Conference on Internet Measurement. New York: ACM, 2004, 88-100

3 Markopoulou A, Iannaccone G, Bhattacharyya S, Chuah C N, Diot C. Characterization of failures in an IP backbone. In: Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies. Hong Kong: IEEE, 2004, 4: 2307-2317

4 Kvalbein A, Hansen A F, Cicic T, Gjessing S, Lysne O. Fast IP network recovery using multiple routing configurations. In: Proceedings of the 25th Annual Joint Conference of the IEEE Computer and Communications Societies. Barcelona: IEEE, 2006, 1-11

5 Hu N, Li L, Mao Z M, Steenkiste P, Wang J. A measurement study of Internet bottlenecks. In: Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Barcelona: IEEE, 2005, 3: 1689-1700

6 Teixeira R, Duffield N, Rexford J, Roughan M. Traffic matrix reloaded: impact of routing changes. In: Proceedings of Passive and Active Network Measurement. Lecture Notes in Computer Science. Berlin: Springer, 2005, 3431: 251-264

7 Yang X, Wetherall D. Source selectable path diversity via routing deflections. In: Proceedings of the 2006 SIGCOMM Conference. New York: ACM, 2006, 159-170

8 Iyer S, Bhattacharyya S, Taft N, Diot C. An approach to alleviate link overload as observed on an IP backbone. In: Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies. San Francisco: IEEE, 2003, 1: 406-416

9 Fortz B, Thorup M. Internet traffic engineering by optimizing OSPF weights. In: Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies. Tel-Aviv: IEEE, 2000, 2: 519-528

10 Ericsson M, Resende M G C, Pardalos P M. A genetic algorithm for the weight setting problem in OSPF routing. Journal of Combinatorial Optimization, 2002, 6(3): 299-333

11 Xu D, Chen Y, Xiong Y, Qiao C, He X. On finding disjoint paths in single and dual link cost networks. In: Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies. Hong Kong: IEEE, 2004, 1: 705-715

12 Orda A, Spronston A. Efficient algorithms for computing disjoint QoS paths. In: Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies. Hong Kong: IEEE, 2004, 1: 727-738

13 Baier G, Köhler E, Skutella M. The k-splittable flow problem. Algorithmica, 2005, 42(3-4): 231-248

14 Benko P, Veres A. A passive method for estimating end-to-end TCP packet loss. In: Proceedings of IEEE Global Telecommunications Conference 2002. Taipei: IEEE, 2002, 3: 2609-2613

15 Jaiswal S, Iannaccone G, Diot C, Kurose J, Towsley D. Measurement and classification of out-of-sequence packets in a Tier-1 IP backbone. IEEE/ACM Transactions on Networking, 2007, 15(1): 54-66

16 Zhou X, Van Mieghem P. Reordering of IP packets in Internet. In: Proceedings of Passive and Active Network Measurement. Lecture Notes in Computer Science. Berlin: Springer, 2004, 3015: 237-246

17 Karp R M. Reducibility among combinatorial problems. In: Miller R E, Thatcher J W, eds. Complexity of Computer Computations. New York: Plenum Press, 1972

18 Azar Y, Regev O. Strongly polynomial algorithms for the unsplittable flow problem. In: Proceedings of Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science. Berlin: Springer, 2001, 2081: 15-29

19 Valiant L G. A scheme for fast parallel communication. SIAM Journal on Computing, 1982, 11(2): 350-361

20 Shepherd F B, Winzer P J. Selective randomized load balancing and mesh networks with changing demands. Journal of Optical Networking, 2006, 5(5): 320-339

21 Fang W, Peterson L. Inter-AS traffic patterns and their implications. In: Proceedings of Global Telecommunications Conference 1999. Rio de Janeiro: IEEE, 1999, 3: 1859-1868

22 Feldmann A, Greenberg A, Lund C, Reingold N, Rexford J, True F. Deriving traffic demands for operational IP networks: methodology and experience. IEEE/ACM Transactions on Networking, 2001, 9(3): 265-279

23 Zhang Y, Breslau L, Paxson V, Shenker S. On the characteristics and origins of Internet flow rates. In: Proceedings of the 2002 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. New York: ACM, 2002, 309-322

24 Estan C, Varghese G. New directions in traffic measurement and accounting. In: Proceedings of the 2002 SIGCOMM Conference. New York: ACM, 2002, 323-336

25 Smitha, Kim I, Narasimha Reddy A L. Identifying long-term high-bandwidth flows at a router. In: Proceedings of High Performance Computing (HiPC 2001). Lecture Notes in Computer Science. Berlin: Springer, 2001, 2228: 361-371

26 Mori T, Uchida M, Kawahara R, Pan J, Goto S. Identifying elephant flows through periodically sampled packets. In: Proceedings of the 4th ACM SIGCOMM Conference on Internet Measurement. New York: ACM, 2004: 115-120

27 Kar K, Kodialam M, Lakshman T V. Minimum Interference routing of bandwidth guaranteed tunnels with MPLS traffic engineering applications. IEEE Journal on Selected Areas in Communications, 2000, 18(12): 2566-2579