RESEARCH ARTICLE

A self-adaptive key flow routing adjustment algorithm

  • Yujie PEI ,
  • Hongbo WANG ,
  • Shiduan CHENG
Expand
  • State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China

Received date: 11 Feb 2009

Accepted date: 01 Apr 2009

Published date: 05 Sep 2009

Copyright

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg

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.

Cite this article

Yujie PEI , Hongbo WANG , Shiduan CHENG . A self-adaptive key flow routing adjustment algorithm[J]. Frontiers of Electrical and Electronic Engineering, 2009 , 4(3) : 287 -294 . DOI: 10.1007/s11460-009-0048-4

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.
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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

Outlines

/