A hybrid genetic
algorithm for the weight setting problem in OSPF/IS-IS routing

L.S. Buriol, M.G.C. Resende, C.C.
Ribeiro, and M. Thorup
**Networks**,
vol. 46, no. 1, pp. 36-56, 2005.

** ABSTRACT**

Intra-domain traffic engineering aims to make more efficient use
of network resources within an autonomous system. Interior
Gateway Protocols such as OSPF (Open Shortest Path First) and IS-IS
(Intermediate System-Intermediate System) are commonly used to select
the paths along which traffic is routed within an autonomous
system. These routing protocols direct traffic based on link
weights assigned by the network operator. Each router in the
autonomous system computes shortest paths and creates destination
tables used to direct each packet to the next router on the path to its
final destination. Given a set of traffic demands between
origin-destination pairs, the "OSPF weight setting problem" consists in
determining weights to be assigned to the links so as to optimize a
cost function, typically associated with a network congestion
measure. In this paper, we propose a genetic algorithm with a
local improvement procedure for the OSPF weight setting problem. The
local improvement procedure makes use of an efficient dynamic shortest
path algorithm to recompute shortest paths after the modification of
link weights. We test the algorithm on a set of real and
synthetic test problems and show that it produces near-optimal
solutions. We compare the hybrid algorithm with other algorithms
for this problem illustrating its efficiency and robustness.

PDF file of paper

DjVu file
of paper

Go back

Mauricio G.C.
Resende's Home Page

Last modified: *15 June 2005*
Copyright Notice