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 the X-WiN, the IP traffic must be routed unsplit along shortest path. The routing planning part of the problem thus consist in finding routing weights for the light-paths such that all end-to-end shortest paths are unique (even in all considered failure scenarios) and the resulting traffic flows do not exceed the installed capacities. Depending on the planning horizon different objectives are considered. For initial X-WiN design and or expansion the goal is to minimize the overall network cost. In short term traffic engineering, the goal is to adapt the traffic flows to the existing capacities by changing the routing only.

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.

X-WiN lightpath planning
 

 

 

 

 

 

 

 

 Recent Publications

Publications

2006
Approximability of Unsplittable Shortest Path Routing Problems ZIB-Report 06-02 (A slightly modified version appeared in: Networks 54 (2009) 23-46) Andreas Bley PDF
BibTeX
URN
X-WiN Optimization of the German Research Network X-WiN
2005
Inapproximability Results for the Inverse Shortest Paths Problem with Integer Length and Unique Shortest Paths ZIB-Report 05-04 (Appeared in: Networks 50 (2007) 29-36. And also as : "Finding Small Administrative Lengths for Shortest Path Routing" in Proceedings of the Second International Network Optimization Conference vol(1) (INOC 2005) 121-128, Lisboa) Andreas Bley PDF
BibTeX
URN
X-WiN Optimization of the German Research Network X-WiN
Modellierung und Optimierung der X-WiN Plattform ZIB-Report 05-21 (Erschienen in: DFN-Mitteilungen 67 (2005) 4-7) Andreas Bley, Marcus Pattloch PDF
BibTeX
URN
X-WiN Optimization of the German Research Network X-WiN