The aim of this project is the development of mathematical tools and software for the design of broadband virtual private networks. Currently, most of the internet providers run IP on top of ATM networks. Usually, these customer networks are virtual private networks embedded in digital cross connect networks or other broadband networks. These physical networks are owned by a few large network providers. The DFN Verein, which acts as internet provider for German universities and research institutes, rents the (virtual) links for its backbone network B-WiN from Deutsche Telekom. The B-WiN currently contains ten ``central service switches''. The DFN Verein can rent a line between any pair of these switches. The structure of the underlying ATM network is transparent to the DFN Verein. For each rented line, the capacity must be chosen from a given set of feasible capacities. The number of lines that can be rented is fixed. For each pair of switches, we are given the directed demand of IP traffic. The OSPF policy (Open Shortest Path First) must be used to route these demands in the network. For each link, the two directed flows must not exceed a certain percentage (load limit) of its capacity. The objective is to design a ``robust'' low-cost network. Robust has two meanings in this context. First, the network must be fault-tolerant (survivable), i.e., even in the case of a single link or a single node failure a certain percentage of the demands must be routable in the remaining network. The routing table must change according to the OSPF protocol in a failure situation. The second meaning of robustness is the stability of solutions. If there are small changes in the demand data or load limits, then the topology of the computed networks should not change. Usually, these changes are highly penalized by the network providers. In contrast to the topology, capacities and routing tables can be changed very easily. In the beginning of the project, we developed a mathematical model for the design and routing problem. Several primal heuristics and lower bounding techniques were designed. After prototyping, testing and tuning these algorithms with real-world data provided by the DFN Verein, several of the primal heuristics were implemented in a software tool. The mathematical methods and software tools developed during this project are in use at DFN for the network planning since December 1997. In regular intervals computations are undertaken, to reoptimize the B-WiN backbone network for changing traffic flows and hardware configurations.
04/1997 - 12/1997