A genetic algorithm for the weight setting problem in OSPF routing

被引:187
作者
Ericsson, M [1 ]
Resende, MGC
Pardalos, PM
机构
[1] Royal Inst Technol, Dept Math, Div Optimizat & Syst Theory, S-10044 Stockholm, Sweden
[2] AT&T Labs Res, Informat Sci Res, Florham Pk, NJ 07932 USA
[3] Univ Florida, Dept Ind & Syst Engn, Gainesville, FL 32611 USA
关键词
OSPF routing; Internet; metaheuristics; genetic algorithm; path relinking;
D O I
10.1023/A:1014852026591
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
With the growth of the Internet, Internet Service Providers (ISPs) try to meet the increasing traffic demand with new technology and improved utilization of existing resources. Routing of data packets can affect network utilization. Packets are sent along network paths from source to destination following a protocol. Open Shortest Path First (OSPF) is the most commonly used intra-domain Internet routing protocol (IRP). Traffic flow is routed along shortest paths, splitting flow at nodes with several outgoing links on a shortest path to the destination IP address. Link weights are assigned by the network operator. A path length is the sum of the weights of the links in the path. The OSPF weight setting (OSPFWS) problem seeks a set of weights that optimizes network performance. We study the problem of optimizing OSPF weights, given a set of projected demands, with the objective of minimizing network congestion. The weight assignment problem is NP-hard. We present a genetic algorithm (GA) to solve the OSPFWS problem. We compare our results with the best known and commonly used heuristics for OSPF weight setting, as well as with a lower bound of the optimal multi-commodity flow routing, which is a linear programming relaxation of the OSPFWS problem. Computational experiments are made on the AT&T Worldnet backbone with projected demands, and on twelve instances of synthetic networks.
引用
收藏
页码:299 / 333
页数:35
相关论文
共 29 条
[1]  
Ahuja RK, 1993, NETWORK FLOWS THEORY
[2]  
AWDUCHE DO, 1999, 2702 RFC NETW WORK G
[3]  
Bean J. C., 1994, ORSA Journal on Computing, V6, P154, DOI 10.1287/ijoc.6.2.154
[4]  
Black U., 2000, IP Routing Protocols: RIP, OSPF, BGP, PNNI and Cisco Routing Protocols
[5]  
BLEY A, 2000, DIMACS SERIES DISCRE, V53, P1
[6]   Modeling Internet topology [J].
Calvert, KL ;
Doar, MB ;
Zegura, EW .
IEEE COMMUNICATIONS MAGAZINE, 1997, 35 (06) :160-163
[7]  
Cisco, 1997, Technical report
[8]  
COFFMAN KG, 2001, HDB MASSIVE DATA SET, P47
[9]  
Dijikstra E. W., 1959, NUMER MATH, V1, P269, DOI DOI 10.1007/BF01386390
[10]   Deriving traffic demands for operational IP networks: Methodology and experience [J].
Feldmann, A ;
Greenberg, A ;
Lund, C ;
Reingold, N ;
Rexford, J ;
True, F .
IEEE-ACM TRANSACTIONS ON NETWORKING, 2001, 9 (03) :265-279