TY - GEN A1 - Betker, Andreas A1 - Kosiankowski, Dirk A1 - Lange, Christoph A1 - Pfeuffer, Frank A1 - Raack, Christian A1 - Werner, Axel T1 - Energy efficiency in extensive multilayer core and regional networks with protection N2 - 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? T3 - ZIB-Report - 12-45 KW - telecommunications KW - network design KW - routing KW - energy efficiency Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17154 SN - 1438-0064 ER - TY - GEN A1 - Menne, Ulrich A1 - Raack, Christian A1 - Wessäly, Roland A1 - Kharitonov, Daniel T1 - Optimal Degree of Optical Circuit Switching in IP-over-WDM Networks N2 - In this paper, we study the influence of technology, traffic properties and price trends on optimized design of a reference IP-over-WDM network with rich underlying fiber topology. In each network node, we investigate the optimal degree of traffic switching in an optical (lambda) domain versus an electrical (packet) domain, also known as measure of \emph{node transparency}. This measure is studied in connection to changes in traffic volume, demand affinity, optical circuit speeds and equipment cost. By applying variable design constraints, we assess the relative roles of the two distinct equipment groups, IP routers and optical cross-connects, with respect to resulting changes in cost-sensitive network architectures. T3 - ZIB-Report - 11-50 KW - IP-over-WDM KW - Circuit Switching KW - Opacity Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14843 SN - 1438-0064 ER - TY - GEN A1 - Poss, Michael A1 - Raack, Christian T1 - Affine recourse for the robust network design problem: between static and dynamic routing N2 - 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. T3 - ZIB-Report - 11-03 KW - robust optimization KW - network design KW - recourse KW - affine adjustable robust counterparts KW - affine routing Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-12122 ER - TY - GEN A1 - Eisenblätter, Andreas A1 - Schweiger, Jonas T1 - Multistage Stochastic Programming in Strategic Telecommunication Network Planning N2 - Mobile communication is nowadays taken for granted. Having started primarily as a service for speech communication, data service and mobile Internet access are now driving the evolution of network infrastructure. Operators are facing the challenge to match the demand by continuously expanding and upgrading the network infrastructure. However, the evolution of the customer's demand is uncertain. We introduce a novel (long-term) network planning approach based on multistage stochastic programming, where demand evolution is considered as a stochastic process and the network is extended as to maximize the expected profit. The approach proves capable of designing large-scale realistic UMTS networks with a time-horizon of several years. Our mathematical optimization model, the solution approach, and computational results are presented in this paper. T3 - ZIB-Report - 11-06 KW - UMTS KW - Network Evolution KW - Multistage KW - Stochastic Programming Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-12232 ER - TY - GEN A1 - Koster, Arie M.C.A. A1 - Kutschka, Manuel A1 - Raack, Christian T1 - Robust Network Design: Formulations, Valid Inequalities, and Computations N2 - Traffic in communication networks fluctuates heavily over time. Thus, to avoid capacity bottlenecks, operators highly overestimate the traffic volume during network planning. In this paper we consider telecommunication network design under traffic uncertainty, adapting the robust optimization approach of Bertsimas and Sim [2004]. We present three different mathematical formulations for this problem, provide valid inequalities, study the computational implications, and evaluate the realized robustness. To enhance the performance of the mixed-integer programming solver we derive robust cutset inequalities generalizing their deterministic counterparts. Instead of a single cutset inequality for every network cut, we derive multiple valid inequalities by exploiting the extra variables available in the robust formulations. We show that these inequalities define facets under certain conditions and that they completely describe a projection of the robust cutset polyhedron if the cutset consists of a single edge. For realistic networks and live traffic measurements we compare the formulations and report on the speed up by the valid inequalities. We study the "price of robustness" and evaluate the approach by analyzing the real network load. The results show that the robust optimization approach has the potential to support network planners better than present methods. T3 - ZIB-Report - 11-34 KW - robust network design KW - cutset inequalities Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-13890 SN - 1438-0064 ER - TY - GEN A1 - Idzikowski, Filip A1 - Orlowski, Sebastian A1 - Raack, Christian A1 - Woesner, Hagen A1 - Wolisz, Adam T1 - Dynamic routing at different layers in IP-over-WDM networks -- Maximizing energy savings N2 - 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. T3 - ZIB-Report - 10-07 KW - network design KW - energy efficiency KW - power consumption KW - multi-layer KW - multi-hour KW - multi-period Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11692 SN - 1438-0064 ER - TY - THES A1 - Schweiger, Jonas T1 - Application of Multistage Stochastic Programming in Strategic Telecommunication Network Planning N2 - 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. Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-12206 ER - TY - GEN A1 - Bley, Andreas T1 - On the Hardness of Finding Small Shortest Path Routing Conflicts N2 - Nowadays most data networks use shortest path protocols such as OSPF or IS-IS to route traffic. Given administrative routing lengths for the links of a network, all data packets are sent along shortest paths with respect to these lengths from their source to their destination. One of the most fundamental problems in planning shortest path networks is to decide whether a given set of routing paths forms a valid routing and, if this is not the case, to find a small subset of the given paths that cannot be shortest paths simultaneously for any routing lengths. In this paper we show that it is NP-hard to approximate the size of the smallest shortest path conflict by a factor less than 7/6. T3 - ZIB-Report - 09-15 KW - shortest path routing KW - computational complexity Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11276 SN - 1438-0064 ER - TY - GEN A1 - Bley, Andreas T1 - An Integer Programming Algorithm for Routing Optimization in IP Networks N2 - 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. T3 - ZIB-Report - 08-30 KW - Shortest Path Routing KW - Integer Programming Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10814 SN - 1438-0064 ER - TY - GEN A1 - Raack, Christian A1 - Koster, Arie M.C.A. A1 - Wessäly, Roland T1 - On the strength of cut-based inequalities for capacitated network design polyhedra N2 - In this paper we study capacitated network design problems, differentiating directed, bidirected and undirected link capacity models. We complement existing polyhedral results for the three variants by new classes of facet-defining valid inequalities and unified lifting results. For this, we study the restriction of the problems to a cut of the network. First, we show that facets of the resulting cutset polyhedra translate into facets of the original network design polyhedra if the two subgraphs defined by the network cut are (strongly) connected. Second, we provide an analysis of the facial structure of cutset polyhedra, elaborating the differences caused by the three different types of capacity constraints. We present flow-cutset inequalities for all three models and show under which conditions these are facet-defining. We also state a new class of facets for the bidirected and undirected case and it is shown how to handle multiple capacity modules by Mixed Integer Rounding (MIR). T3 - ZIB-Report - 07-08 KW - cutset-polyhedra KW - flow-cutset inequalities KW - network design KW - mixed integer programming Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9512 ER -