Increasing internet capacity using local search

被引:133
作者
Fortz, B [1 ]
Thorup, M
机构
[1] Catholic Univ Louvain, Inst Adm & Gest, B-1348 Louvain, Belgium
[2] AT&T Labs Res, Shannon Lab, Florham Pk, NJ 07932 USA
关键词
traffic engineering; shortest path routing; local search;
D O I
10.1023/B:COAP.0000039487.35027.02
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
Open Shortest Path First (OSPF) is one of the most commonly used intra-domain internet routing protocol. Traffic flow is routed along shortest paths, splitting flow evenly at nodes where several outgoing links are on shortest paths to the destination. The weights of the links, and thereby the shortest path routes, can be changed by the network operator. The weights could be set proportional to the physical lengths of the links, but often the main goal is to avoid congestion, i.e. overloading of links, and the standard heuristic recommended by Cisco ( a major router vendor) is to make the weight of a link inversely proportional to its capacity. We study the problem of optimizing OSPF weights for a given a set of projected demands so as to avoid congestion. We show this problem is NP-hard, even for approximation, and propose a local search heuristic to solve it. We also provide worst-case results about the performance of OSPF routing vs. an optimal multicommodity flow routing. Our numerical experiments compare the results obtained with our local search heuristic to the optimal multi-commodity flow routing, as well as simple and commonly used heuristics for setting the weights. Experiments were done with a proposed next-generation AT&T WorldNet backbone as well as synthetic internetworks.
引用
收藏
页码:13 / 48
页数:36
相关论文
共 40 条
[1]  
AARTS E, 1997, LOCAL SEARCH COMBINA
[2]  
[Anonymous], P 6 INFORMS TEL
[3]  
APPLEGATE D, 2003, IN PRESS P 22 IEEE C
[4]  
Battiti R., 1994, ORSA Journal on Computing, V6, P126, DOI 10.1287/ijoc.6.2.126
[5]  
BENAMEUR W, 2001, INTERNET ROUTING REL
[6]  
BENAMEUR W, 2001, TELEKTRONIKK MAGAZIN, V2, P145
[7]  
BLEY A, 1998, DIMACS SERIES DISCRE, V53, P1
[8]   Modeling Internet topology [J].
Calvert, KL ;
Doar, MB ;
Zegura, EW .
IEEE COMMUNICATIONS MAGAZINE, 1997, 35 (06) :160-163
[9]   A note on hashing functions and tabu search algorithms [J].
Carlton, WB ;
Barnes, JW .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1996, 95 (01) :237-239
[10]  
CARTER JL, 1979, J COMPUT SYST SCI, V18, P143, DOI 10.1016/0022-0000(79)90044-8