@misc{Bley, author = {Bley, Andreas}, title = {A Lagrangian Approach for Integrated Network Design and Routing in IP Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7515}, number = {03-29}, abstract = {We consider the problem of designing a network that employs a non-bifurcated shortest path routing protocol. The network's nodes and the set of potential links are given together with a set of forecasted end-to-end traffic demands. All relevant hardware components installable at links or nodes are considered. The goal is to simultaneously choose the network's topology, to decide which hardware components to install on which links and nodes, and to find appropriate routing weights such that the overall network cost is minimized. In this paper, we present a mathematical optimization model for this problem and an algorithmic solution approach based on a Lagrangian relaxation. Computational results achieved with this approach for several real-world network planning problems are reported.}, language = {en} } @misc{GruberKosterOrlowskietal., author = {Gruber, Claus G. and Koster, Arie M.C.A. and Orlowski, Sebastian and Wess{\"a}ly, Roland and Zymolka, Adrian}, title = {A new model and a computational study for Demand-wise Shared Protection}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8880}, number = {05-55}, abstract = {This report combines the contributions to INOC 2005 (Wess{\"a}lly et al., 2005) and DRCN 2005 (Gruber et al., 2005). A new integer linear programming model for the end-to-end survivability concept deman d-wise shared protection (DSP) is presented. DSP is based on the idea that backup capacity is dedicated to a particular demand, but shared within a demand. It combines advantages of dedicated and shared protection: It is more cost-efficient than dedicated protection and operationally easier than shared protection. In a previous model for DSP, the number of working and backup paths to be configured for a particular demand has been an input parameter; in the more general model for DSP investigated in this paper, this value is part of the decisions to take. To use the new DSP model algorithmically, we suggest a branch-and-cut approach which employs a column generation procedure to deal with the exponential number of routing variables. A computational study to compare the new resilience mechanism DSP with dedicated and shared path protection is performed. The results for five realistic network planning scenarios reveal that the best solutions for DSP are on average 15\\% percent better than the corresponding 1+1 dedicated path protection solutions, and only 15\\% percent worse than shared path protection.}, language = {en} } @misc{PossRaack, author = {Poss, Michael and Raack, Christian}, title = {Affine recourse for the robust network design problem: between static and dynamic routing}, doi = {10.1002/net.21482}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-12122}, number = {11-03}, abstract = {Affinely-Adjustable Robust Counterparts provide tractable alternatives to (two-stage) robust programs with arbitrary recourse. We apply them to robust network design with polyhedral demand uncertainty, introducing the affine routing principle. We compare the affine routing to the well-studied static and dynamic routing schemes for robust network design. All three schemes are embedded into the general framework of two-stage network design with recourse. It is shown that affine routing can be seen as a generalization of the widely used static routing still being tractable and providing cheaper solutions. We investigate properties on the demand polytope under which affine routings reduce to static routings and also develop conditions on the uncertainty set leading to dynamic routings being affine. We show however that affine routings suffer from the drawback that (even totally) dominated demand vectors are not necessarily supported by affine solutions. Uncertainty sets have to be designed accordingly. Finally, we present computational results on networks from SNDlib. We conclude that for these instances the optimal solutions based on affine routings tend to be as cheap as optimal network designs for dynamic routings. In this respect the affine routing principle can be used to approximate the cost for two-stage solutions with free recourse which are hard to compute.}, language = {en} } @misc{Bley, author = {Bley, Andreas}, title = {An Integer Programming Algorithm for Routing Optimization in IP Networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10814}, number = {08-30}, abstract = {Most data networks nowadays use shortest path protocols to route the traffic. Given administrative routing lengths for the links of the network, all data packets are sent along shortest paths with respect to these lengths from their source to their destination. In this paper, we present an integer programming algorithm for the minimum congestion unsplittable shortest path routing problem, which arises in the operational planning of such networks. Given a capacitated directed graph and a set of communication demands, the goal is to find routing lengths that define a unique shortest path for each demand and minimize the maximum congestion over all links in the resulting routing. We illustrate the general decomposition approach our algorithm is based on, present the integer and linear programming models used to solve the master and the client problem, and discuss the most important implementational aspects. Finally, we report computational results for various benchmark problems, which demonstrate the efficiency of our algorithm.}, language = {en} } @misc{Schweiger, type = {Master Thesis}, author = {Schweiger, Jonas}, title = {Application of Multistage Stochastic Programming in Strategic Telecommunication Network Planning}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-12206}, school = {Zuse Institute Berlin (ZIB)}, pages = {149}, abstract = {Telecommunication is fundamental for the information society. In both, the private and the professional sector, mobile communication is nowadays taken for granted. Starting primarily as a service for speech communication, data service and mobile Internet access are now driving the evolution of network infrastructure. In the year 2009, 19 million users generated over 33 million GB of traffic using mobile data services. The 3rd generation networks (3G or UMTS) in Germany comprises over 39,000 base stations with some 120,000 cells. From 1998 to 2008, the four network operators in Germany invested over 33 billion Euros in their infrastructure. A careful allocation of the resources is thus crucial for the profitability for a network operator: a network should be dimensioned to match customers demand. As this demand evolves over time, the infrastructure has to evolve accordingly. The demand evolution is hard to predict and thus constitutes a strong source of uncertainty. Strategic network planning has to take this uncertainty into account, and the planned network evolution should adapt to changing market conditions. The application of superior planning methods under the consideration of uncertainty can improve the profitability of the network and creates a competitive advantage. Multistage stochastic programming is a suitable framework to model strategic telecommunication network planning. We present mathematical models and effective optimization procedures for strategic cellular network design. The demand evolution is modeled as a continuous stochastic process which is approximated by a discrete scenario tree. A tree-stage approach is used for the construction of non-uniform scenario trees that serve as input of the stochastic program. The model is calibrated by historical traffic observations. A realistic system model of UMTS radio cells is used that determines coverage areas and cell capacities and takes signal propagation and interferences into account. The network design problem is formulated as a multistage stochastic mixed integer linear program, which is solved using state-of-the-art commercial MIP solvers. Problem specific presolving is proposed to reduce the problem size. Computational results on realistic data is presented. Optimization for the expected profit and the conditional value at risk are performed and compared.}, language = {en} } @misc{Bley, author = {Bley, Andreas}, title = {Approximability of Unsplittable Shortest Path Routing Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8968}, number = {06-02}, abstract = {In this paper, we discuss the relation of unsplittable shortest path routing (USPR) to other routing schemes and study the approximability of three USPR network planning problems. Given a digraph \$D=(V,A)\$ and a set \$K\$ of directed commodities, an USPR is a set of flow paths \$\Phi_{(s,t)}\$, \$(s,t)\in K\$, such that there exists a metric \$\lambda=(\lambda_a)\in \mathbb{Z}^A_+\$ with respect to which each \$\Phi_{(s,t)}\$ is the unique shortest \$(s,t)\$-path. In the \textsc{Min-Con-USPR} problem, we seek for an USPR that minimizes the maximum congestion over all arcs. We show that this problem is hard to approximate within a factor of \$\mathcal{O}(|V|^{1-\epsilon})\$, but easily approximable within min\$(|A|,|K|)\$ in general and within \$\mathcal{O}(1)\$ if the underlying graph is an undirected cycle or a bidirected ring. We also construct examples where the minimum congestion that can be obtained by USPR is a factor of \$\Omega(|V|^2)\$ larger than that achievable by unsplittable flow routing or by shortest multi-path routing, and a factor of \$\Omega(|V|)\$ larger than by unsplittable source-invariant routing. In the CAP-USPR problem, we seek for a minimum cost installation of integer arc capacities that admit an USPR of the given commodities. We prove that this problem is \$\mathcal{NP}\$-hard to approximate within \$2-\epsilon\$ (even in the undirected case), and we devise approximation algorithms for various special cases. The fixed charge network design problem \textsc{Cap-USPR}, where the task is to find a minimum cost subgraph of \$D\$ whose fixed arc capacities admit an USPR of the commodities, is shown to be \$\mathcal{NPO}\$-complete. All three problems are of great practical interest in the planning of telecommunication networks that are based on shortest path routing protocols. Our results indicate that they are harder than the corresponding unsplittable flow or shortest multi-path routing problems.}, language = {en} } @misc{Geerdes, author = {Geerdes, Hans-Florian}, title = {Assessing Capacity Improvements by Relaying in Cellular Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7651}, number = {03-43}, abstract = {Relaying -- allowing multiple wireless hops -- is a protocol extension for cellular networks conceived to improve data throughput. Its benefits have only been quantified for small example networks. For assessing its general potential, we define a complex resource allocation\slash{}scheduling problem. Several mathematical models are presented for this problem; while a time-expanded MIP approach turns out intractable, a sophisticated column generation scheme leads to good computational results. We thereby show that for selected cases relaying can increase data throughput by 30\\% on the average.}, language = {en} } @misc{HuelsermannJaegerKosteretal., author = {H{\"u}lsermann, Ralf and J{\"a}ger, Monika and Koster, Arie M.C.A. and Orlowski, Sebastian and Wess{\"a}ly, Roland and Zymolka, Adrian}, title = {Availability and Cost Based Evaluation of Demand-wise Shared Protection}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9080}, number = {06-15}, abstract = {In this paper, we investigate the connection availabilities for the new protection scheme Demand-wise Shared Protection (DSP) and describe an appropriate approach for their computation. The exemplary case study on two realistic network scenarios shows that in most cases the availabilities for DSP are comparable with that for 1+1 path protection and better than in case of shared path protection.}, language = {en} } @misc{RaackKosterOrlowskietal., author = {Raack, Christian and Koster, Arie M.C.A. and Orlowski, Sebastian and Wess{\"a}ly, Roland}, title = {Capacitated network design using general flow-cutset inequalities}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9576}, number = {07-14}, abstract = {This paper deals with directed, bidirected, and undirected capacitated network design problems. Using mixed integer rounding (MIR), we generalize flow-cutset inequalities to these three link types and to an arbitrary modular link capacity structure, and propose a generic separation algorithm. In an extensive computational study on 54 instances from the Survivable Network Design Library (SNDlib), we show that the performance of cplex can significantly be enhanced by this class of cutting planes. The computations reveal the particular importance of the subclass of cutset-inequalities.}, language = {en} } @misc{KosterZymolkaJaegeretal., author = {Koster, Arie M.C.A. and Zymolka, Adrian and J{\"a}ger, Monika and H{\"u}lsermann, Ralf and Gerlach, Christoph}, title = {Demand-wise Shared Protection for Meshed Optical Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7461}, number = {03-24}, abstract = {In this paper, a new shared protection mechanism for meshed optical networks is presented. Significant network design cost reductions can be achieved in comparison to the well-known 1+1 protection scheme. Demand-wise Shared Protection (DSP) bases on the diversification of demand routings and exploits the network connectivity to restrict the number of backup lightpaths needed to provide the desired level of prorection. Computational experiments approve the benefits of the concept DSP for cost efficient optical network designs.}, language = {en} } @phdthesis{Zymolka, author = {Zymolka, Adrian}, title = {Design of Survivable Optical Networks by Mathematical Optimization}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10408}, abstract = {Abstract The cost-efficient design of survivable optical telecommunication networks is the topic of this thesis. In cooperation with network operators, we have developed suitable concepts and mathematical optimization methods to solve this comprehensive planning task in practice. Optical technology is more and more employed in modern telecommunication networks. Digital information is thereby transmitted as short light pulses through glass fibers. Moreover, the optical medium allows for simultaneous transmissions on a single fiber by use of different wavelengths. Recent optical switches enable a direct forwarding of optical channels in the network nodes without the previously required signal retransformation to electronics. Their integration creates ongoing optical connections,which are called lightpaths. We study the problem of finding cost-efficient configurations of optical networks which meet specified communication requirements. A configuration comprises the determination of all lightpaths to establish as well as the detailed allocation of all required devices and systems. We use a flexible modeling framework for a realistic representation of the networks and their composition. For different network architectures, we formulate integer linear programs which model the design task in detail. Moreover, network survivability is an important issue due to the immense bandwidths offered by optical technology. Operators therefore request for designs which perpetuate protected connections and guarantee for a defined minimum throughput in case of malfunctions. In order to achieve an effective realization of scalable protection, we present a novel survivability concept tailored to optical networks and integrate several variants into the models. Our solution approach is based on a suitable model decomposition into two subtasks which separates two individually hard subproblems and enables this way to compute cost-efficient designs with approved quality guarantee. The first subtask consists of routing the connections with corresponding dimensioning of capacities and constitutes a common core task in the area of network planning. Sophisticated methods for such problems have already been developed and are deployed by appropriate integration. The second subtask is characteristic for optical networks and seeks for a conflict-free assignment of available wavelengths to the lightpaths using a minimum number of involved wavelength converters. For this coloring-like task, we derive particular models and study methods to estimate the number of unavoidable conversions. As constructive approach, we develop heuristics and an exact branch-and-price algorithm. Finally, we carry out an extensive computational study on realistic data, provided by our industrial partners. As twofold purpose, we demonstrate the potential of our approach for computing good solutions with quality guarantee, and we exemplify its flexibility for application to network design and analysis.}, language = {en} } @misc{HuelsermannJaegerKrumkeetal., author = {H{\"u}lsermann, Ralf and J{\"a}ger, Monika and Krumke, Sven and Poensgen, Diana and Rambau, J{\"o}rg and Tuchscherer, Andreas}, title = {Dynamic Routing Algorithms in Transparent Optical Networks An Experimental Study Based on Real Data}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7025}, number = {02-35}, abstract = {Today's telecommunication networks are configured statically. Whenever a connection is established, the customer has permanent access to it. However, it is observed that usually the connection is not used continuously. At this point, dynamic provisioning could increase the utilization of network resources. WDM based Optical Transport Networks (OTNs) will shortly allow for fast dynamic network reconfiguration. This enables optical broadband leased line services on demand. Since service requests competing for network resources may lead to service blocking, it is vital to use appropriate strategies for routing and wavelength assignment in transparent optical networks. We simulate the service blocking probabilities of various dynamic algorithms for this problem using a well-founded traffic model for two realistic networks. One of the algorithms using shortest path routings performs best on all instances. Surprisingly, the tie-breaking rule between equally short paths in different wavelengths decides between success or failure.}, language = {en} } @misc{IdzikowskiOrlowskiRaacketal., author = {Idzikowski, Filip and Orlowski, Sebastian and Raack, Christian and Woesner, Hagen and Wolisz, Adam}, title = {Dynamic routing at different layers in IP-over-WDM networks -- Maximizing energy savings}, organization = {Zuse Institute Berlin}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11692}, number = {10-07}, abstract = {We estimate potential energy savings in IP-over-WDM networks achieved by switching off router line cards in low-demand hours. We compare three approaches to react on dynamics in the IP traffic over time, FUFL, DUFL and DUDL. They provide different levels of freedom in adjusting the routing of lightpaths in the WDM layer and the routing of demands in the IP layer. Using MILP models based on three realistic network topologies as well as realistic demands, power, and cost values, we show that already a simple monitoring of the lightpath utilization in order to deactivate empty line cards (FUFL) brings substantial benefits. The most significant savings, however, are achieved by rerouting traffic in the IP layer (DUFL), which allows emptying and deactivating lightpaths together with the corresponding line cards. A sophisticated reoptimization of the virtual topologies and the routing in the optical domain for every demand scenario (DUDL) yields nearly no additional profits in the considered networks. These results are independent of the ratio between the demand and capacity granularities, the time scale and the network topology, and show little dependency on the demand structure.}, language = {en} } @misc{BetkerKosiankowskiLangeetal., author = {Betker, Andreas and Kosiankowski, Dirk and Lange, Christoph and Pfeuffer, Frank and Raack, Christian and Werner, Axel}, title = {Energy efficiency in extensive multilayer core and regional networks with protection}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17154}, abstract = {Energy-efficient operation of large telecommunication networks is an important issue today and in the near future. Given that the energy consumption rises with the ever increasing demand for capacity and network speed, there is a growing interest in strategies for a sustainable network management. It is a well-known fact that traffic demands vary significantly over time, most notably in day/night- and in weekly cycles. This provides the main potential for energy-saving strategies. We study the question of how much power is necessary to operate a network with state-of-the-art hardware during peak or low-traffic times. The study respects realistic side constraints, such as protection requirements and routing schemes, and takes the special structure of an extensive nation-wide optical network, including backbone and regional sections, into account. We formulate mixed integer programming models for the corresponding optimization problems using predictions for traffic matrices, as well as state-of-the-art hardware and power models. We address questions as the following: How much energy is spent in the core and in metro regions of the network and how big are the savings in low-demand scenarios if we always assume the system power-minimum in these situations? What is the influence of different hardware on the overall energy consumption? How much do different routing schemes or protection scenarios restrict potential energy savings?}, language = {en} } @misc{Groetschel, author = {Gr{\"o}tschel, Martin}, title = {Frequency Assignment in Mobile Phone Systems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6265}, number = {00-58}, abstract = {Wireless communication networks employ radio frequencies to establish communication links. The available radio spectrum is very limited. To meet today's radio communication demand, this resource has to be administered and reused carefully in order to control mutual interference. The reuse can be organized via separation in space, time, or frequency, for example. The problem, therefore, arises to distribute frequencies to links in a ``reasonable manner''. This is the basic form of the frequency assignment problem. What ``reasonable'' means, how to quantify this measure of quality, which technical side constraints to consider cannot be answered in general. The exact specification of this task and its mathematical model depend heavily on the particular application considered. In this paper we discuss this issue with respect to the GSM standard for mobile communication.}, language = {en} } @misc{Bley, author = {Bley, Andreas}, title = {Inapproximability Results for the Inverse Shortest Paths Problem with Integer Length and Unique Shortest Paths}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8388}, number = {05-04}, abstract = {We study the complexity of two Inverse Shortest Paths (ISP) problems with integer arc lengths and the requirement for uniquely determined shortest paths. Given a collection of paths in a directed graph, the task is to find positive integer arc lengths such that the given paths are uniquely determined shortest paths between their respective terminals. The first problem seeks for arc lengths that minimize the length of the longest of the prescribed paths. In the second problem, the length of the longest arc is to be minimized. We show that it is \$np-hard\$ to approximate the minimal longest path length within a factor less than \$8/7\$ or the minimal longest arc length within a factor less than \$9/8\$. This answers the (previously) open question whether these problems are \$np-hard\$ or not. We also present a simple algorithm that achieves an \$\mathcal{O}(|V|)\$-approximation guarantee for both variants. Both ISP problems arise in the planning of telecommunication networks with shortest path routing protocols. Our results imply that it is \$\mathcal{NP}\$-hard to decide whether a given path set can be realized with a real shortest path routing protocol such as OSPF, IS-IS, or RIP.}, language = {en} } @misc{BleyKoch, author = {Bley, Andreas and Koch, Thorsten}, title = {Integer programming approaches to access and backbone IP-network planning}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7081}, number = {02-41}, abstract = {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 has to satisfy certain survivability and 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.}, language = {en} } @misc{KosterZymolka, author = {Koster, Arie M.C.A. and Zymolka, Adrian}, title = {Linear Programming Lower Bounds for Minimum Converter Wavelength Assignment in Optical Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8160}, number = {04-41}, abstract = {In this paper, we study the conflict-free assignment of wavelengths to lightpaths in an optical network with the opportunity to place wavelength converters. To benchmark heuristics for the problem, we develop integer programming formulations and study their properties. Moreover, we study the computational performance of the column generation algorithm for solving the linear relaxation of the most promising formulation. In many cases, a non-zero lower bound on the number of required converters is generated this way. For several instances, we in fact prove optimality since the lower bound equals the best known solution value.}, language = {en} } @misc{EisenblaetterKosterWallbaumetal., author = {Eisenbl{\"a}tter, Andreas and Koster, Arie M.C.A. and Wallbaum, Randolf and Wess{\"a}ly, Roland}, title = {Load Balancing in Signaling Transfer Points}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7179}, number = {02-50}, abstract = {Signaling is crucial to the operation of modern telecommunication networks. A breakdown in the signaling infrastructure typically causes customer service failures, incurs revenue losses, and hampers the company image. Therefore, the signaling network has to be highest reliability and survivability. This in particular holds for the routers in such a network, called \textit{signaling transfer points\/} (STPs). The robustness of an STP can be improved by equally distributing the load over the internal processing units. Several constraints have to be taken into account. The load of the links connected to a processing unit changes over time introducing an imbalance of the load. In this paper, we show how integer linear programming can be applied to reduce the imbalance within an STP, while keeping the number of changes small. Two alternative models are presented. Computational experiments validate the integer programming approach in practice. The GSM network operator E-Plus saves substantial amounts of time and money by employing the proposed approach.}, language = {en} } @misc{KosterZymolka, author = {Koster, Arie M.C.A. and Zymolka, Adrian}, title = {Minimum Converter Wavelength Assignment in All-Optical Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7673}, number = {03-45}, abstract = {Finding conflict-free wavelength assignments with a minimum number of required conversions for a routing of the lightpaths is one of the important tasks within the design of all-optical networks. We consider this problem in multi-fiber networks with different types of WDM systems. We give a detailed description of the problem and derive its theoretical complexity. For practical application, we propose several sequential algorithms to compute appropriate wavelength assignments. We also perform computational experiments to evaluate their performance. For the iterative algorithms, we identify characteristic patterns of progression. Two of these algorithms qualify for application in practice.}, language = {en} }