Proceedings of the Eighth INFORMS Telecommunications Conference, Dallas, Texas, April 2006.
OSPF, or Open Shortest Path First, is a commonly used interior
gateway protocol. Given a network topology, a set of link types
to be deployed, each having a different capacity, and predicted traffic
demands, the problem considered in this paper is to find a set of OSPF
weights that minimizes network cost subject to single arc failures. We
propose a genetic algorithm to find near-optimal or optimal solutions
for this problem. At each iteration (or generation) of the
algorithm, OSPF weights are assigned to the arcs of each member of the
population and an external procedure determines which links are to be
deployed and the corresponding cost associated with the deployment.
Four heuristics used to implement this external procedure are the main
topic of this paper. They are designed to minimize the overall
cost of the network, but some have additional constraints imposed by
specific applications. We show the results of an experiment with the
four heuristics on a real network with 54 routers and 278 arcs.
PDF file of full paper
Mauricio G.C. Resende's Home PageLast modified: 7 July 2006