network design with OSPF routing
L.S. Buriol, M.G.C. Resende, and M.
vol. 49, pp. 51-64, 2007
.Shortest path based protocols, such as Open Shortest Path First
(OSPF), direct traffic based on arc weights assigned by the network
operator. Each router computes shortest paths and creates
destination tables used for routing flow on the shortest paths.
If a router has multiple outgoing links on shortest paths to a given
destination, it splits traffic evenly over these links. It is also the
role of the routing protocol to specify how the network should react to
changes in the network topology, such as arc
or router failures. In such situations, IP traffic is re-routed
through the shortest paths not traversing the affected part of the
network. This paper addresses the issue of assigning OSPF weights and
multiplicities to each arc, aiming to design efficient OSPF-routed
networks with minimum total weighted multiplicity (multiplicity
multiplied by the arc length) needed to route the required demand and
handle any single arc or router failure. The multiplicities are
limited to a discrete set of values and we assume that the topology is
given. We propose an evolutionary algorithm for this problem, and
present results applying it to several real-world problem instances.
PDF file of paper
Resende's Home Page
Last modified: 6 October 2006