M. Ericsson, M. G. C. Resende and P.M. Pardalos
J. of Combinatorial Optimization, vol. 6, pp. 299-333, 2002
ABSTRACT
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.
PDF file
of full paper