Since 2006, the X-WiN is the national backbone of DFN ~ Germany`s National Research and Education Network. X-WiN connects over 400 German universities and research institutions and, being connected to the European Backbone GÉANT, it is an integral part of the worldwide community of research and education networks. The X-WiN network is implemented as a multilayer network: The IP service runs on top of a DFN-administrated network of light-paths in an underlying dark-fiber network. With a higher number of nodes in the network core and the high variability in the light-path configuration, X-WiN is more flexible than its predecessor network G-WiN and able to cope with the continuously increasing traffic volume and the special requirements of new multimedia and Grid/e-Science applications. The aim of this project is to develop mathematical models and algorithms to solve the optimization problems that arise in the planning of X-WiN or similar networks. This includes location planning and network dimensioning problems as well as traffic engineering and rounting planning tasks. With the help of these models and algorithms, we support the DFN-Verein computationally and analytically in building and operating the X-WiN.
Light-Path and Routing Planning
In the planning of the backbone network, we have to decide simultaneously
- the topology of the light-path network,
- the transmissions systems and capacities used on the light paths,
- node hardware, and
- the routing of the communication demands.
In any case, the network and and routing must be chosen such that the system is survivable against single nodes and single fiber failures. (Note that a fiber can carry many light-paths.) To ensure high quality of service, in the normal case and in each considered failure scenario the traffic flows on the (residual) links must not exceed a specified percentage of the available capacities.
In cooperation with project Integrated Planning of Multi-level / Multi-layer Networks we developed a solution approach that is tailored to the special situation of the X-WiN planning: In a first step, a set of good candidate light-paths is computed heuristically, based on the traffic forecasts and on the topology of the underlying fiber network. Then, in a second step, evolved optimization methods for single layer IP networks is used to compute a cost-efficient fault-tolerant network and a routing or, in the traffic engineering application, just to optimize the routing. Our computational experiments revealed that - for the specific instances arising in the X-WiN planning - the set of candidate light-paths is of high quality and the entire approach delivers very good solutions.
Recent Publications
- A. Bley. Inapproximability Results for the Inverse Shortest Paths Problem with Integer Lengths and Unique Shortest Paths. Technical Report ZR-05-04, Konrad-Zuse-Zentrum für Informationstechnik Berlin, 2005.
- A. Bley. Finding Small Administrative Lengths for Shortest Path Routing. In: Proceedings of the Second International Network Optimization Conference (INOC 2005), Lisbon, volume 1, pp. 121–128, 2005.
- A. Bley. On the Approximability of the Minimum Congestion Unsplittable Shortest Path Routing Problem. In: Proceedings of 11th Conference on Integer Programming and Combinatorial Optimization (IPCO 2005), Berlin, Germany, pp. 97–110, Berlin, 2005.
- A. Bley. Approximability of Unsplittable Shortest Path Routing Problems. Technical Report ZR-06-02, Konrad-Zuse-Zentrum für Informationstechnik Berlin, 2006.
- A. Bley, T. Koch, R. Wessäly. Large-scale Hierarchical Networks: How to Compute an Optimal Architecture?. In: Proceedings of Networks 2004, Vienna, 2004.
- A. Bley, M. Pattloch. Modellierung und Optimierung der X-WiN Plattform. DFN-Mitteilungen 67, (67):4–7, 2005.
