SC 98-13 Andreas Bley, Martin Grötschel, Roland Wessäly: Design of Broadband Virtual Private Networks: Model and
Heuristics for the B-WiN
Abstract: We investigate the problem of designing survivable broadband
virtual private
networks that employ the Open Shortest Path First (OSPF) routing protocol to
route the packages.
The capacities available for the links of the network are a minimal capacity
plus multiples of a unit capacity.
Given the directed communication demands between all pairs of nodes, we wish
to select the capacities in a such way, that even in case of a single node or
a single link failure a specified percentage of each demand can be satisfied
and the costs for these capacities are minimal.
We present a mixed-integer linear programming formulation of this problem
and several heuristics for its solution. Furthermore, we report on
computational results with real-world data.
Keywords: Telecommunication Network Design,
Survivable Networks,
Network Capacity Planning,
OSPF Routing,
Shortest Path Routing,
Heuristics
MSC: 90B12, 90C11, 90C27, 90C90