Frontiers of Electrical and Electronic Engineering >
A self-adaptive key flow routing adjustment algorithm
Received date: 11 Feb 2009
Accepted date: 01 Apr 2009
Published date: 05 Sep 2009
Copyright
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.
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
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
|
/
〈 | 〉 |