A self-adaptive key flow routing adjustment algorithm

doi:10.1007/s11460-009-0048-4

Front Elect Electr Eng Chin

2009, Vol. 4

Issue (3) : 287-294 https://doi.org/10.1007/s11460-009-0048-4

RESEARCH ARTICLE

A self-adaptive key flow routing adjustment algorithm

Yujie PEI(

), Hongbo WANG, Shiduan CHENG

State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China

Download: PDF(165 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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.

Keywords network management load balancing quality of service (QoS) routing adjustment

Corresponding Author(s): PEI Yujie,Email:yjpei51@gmail.com

Issue Date: 05 September 2009

Cite this article:

Yujie PEI,Hongbo WANG,Shiduan CHENG. A self-adaptive key flow routing adjustment algorithm[J]. Front Elect Electr Eng Chin, 2009, 4(3): 287-294.

URL:

https://academic.hep.com.cn/fee/EN/10.1007/s11460-009-0048-4
https://academic.hep.com.cn/fee/EN/Y2009/V4/I3/287

Tab.1 Symbolic table

Fig.1 Curve of cost function

Fig.2 Key flows routing

Fig.3 Topology of MIRA net

Fig.4 Optimality gap with 50 node topology

Fig.5 Optimality gap with 80 node topology

Fig.6 Optimality gap with 50 node topology (zoom in for proposed algorithm)

Fig.7 Optimality gap with 80 node topology (zoom in for proposed algorithm)

Fig.8 Mean path length with 50 node topology

Fig.9 Mean path length with 80 node topology

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: 10.1023/A:1014852026591
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: 10.1007/s00453-005-1167-9
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: 10.1109/TNET.2006.890117
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: 10.1137/0211027
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: 10.1364/JON.5.000320
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: 10.1109/90.929850
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: 10.1109/49.898737

Viewed

Full text

Abstract

Cited

Shared

Discussed