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 条
[11]  
Cisco, 1997, Technical report
[12]  
Cook S. A., 1971, P 3 ANN ACM S THEOR, P151, DOI DOI 10.1145/800157.805047
[13]  
Dietzfelbinger M., 1996, LECT NOTES COMPUTER, V1046, P569
[14]  
ERICSSON M, 2002, IN PRESS J COBINATOR
[15]   Optimizing OSPF/IS-IS weights in a changing world [J].
Fortz, B ;
Thorup, M .
IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 2002, 20 (04) :756-767
[16]  
Fortz B., 2000, Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No.00CH37064), P519, DOI 10.1109/INFCOM.2000.832225
[17]   Traffic engineering with traditional IP routing protocols [J].
Fortz, B ;
Rexford, J ;
Thorup, M .
IEEE COMMUNICATIONS MAGAZINE, 2002, 40 (10) :118-124
[18]  
FORTZ B, 2000, ISMG200021 U LIBR BR
[19]  
FRIGIONI D, 1998, ACM J EXPT ALGORITHM, V3
[20]   FUTURE PATHS FOR INTEGER PROGRAMMING AND LINKS TO ARTIFICIAL-INTELLIGENCE [J].
GLOVER, F .
COMPUTERS & OPERATIONS RESEARCH, 1986, 13 (05) :533-549