Integer Programming Approaches to Access and Backbone IP Network Planning
In this article we study the problem of designing a nation-wide communication network. Such networks usually consist of an access layer, a backbone layer, and maybe several intermediate layers. The nodes of each layer must be connected to those of the nex
- PDF / 1,009,146 Bytes
- 24 Pages / 439.324 x 666.21 pts Page_size
- 7 Downloads / 197 Views
bstract In this article we study the problem of designing a nation-wide communication network. Such networks usually consist of an access layer, a backbone layer, and maybe several intermediate layers. The nodes of each layer must be connected to those of the next layer in a tree-like fashion. The backbone layer must satisfy survivability and IP-routing constraints. Given the node locations, the demands between them, the possible connections and hardware configurations, and various other technical and administrational constraints, the goal is to decide, which node is assigned to which network level, how the nodes are connected, what hardware must be installed, and how traffic is routed in the backbone. Mixed integer linear programming models and solution methods are presented for both the access and the backbone network design problem. The focus is on the design of IP-over-SDH networks, but the access network design model and large parts of the backbone network design models are general and also applicable for other types of communication networks. Results obtained with these methods in the planning of the German research network are presented.
1 Introduction The German gigabit research network G-WiN, operated by the DFN-Verein e.V., is the largest IP network in Germany. In this article we describe the mathematical models and tools used to plan the layout and dimensioning of the access and backbone network [BK00, BKW04]. Since these models are general in nature, they were used also in two other projects. One was the placement of switching centers in circuit switched networks, a cooperation
∗
This work was partially funded by the Bundesministerium f¨ ur Bildung, Wissenschaft, Forschung und Technologie (BMBF).
88
A. Bley and T. Koch
with Telekom Austria. In the other project, studies about MSC planning in mobile phone networks were conducted together with E-Plus. Unfortunately, the data from the later projects cannot be published. For this reason, we focus throughout this article on the G-WiN IP network as an example, but show the generalized models that were developed. The problem we were faced with, roughly can be stated as follows: Given the node locations, the demands between them, the possible node layers, connections, and hardware configurations, and various other technical and administrational constraints, the goal is to decide, which node is assigned to which network layer, how the nodes are connected, what hardware must be installed, and how traffic is routed in the backbone network. In this article we present a two-phase approach that splits between access and backbone network planning. In a first step, we only consider the access network. Then, in the second phase, the backbone dimensioning and routing problem is addressed. Both problems are solved by integer linear programming techniques. The problems encountered in the access network planning can be viewed as capacitated two-level facility location problems. There is a huge amount of literature on various aspects of this kind of problems. See for example [
Data Loading...
