Refine
Year of publication
Document Type
- ZIB-Report (13)
- In Proceedings (6)
- Article (2)
- Book chapter (2)
- Doctoral Thesis (1)
- Master's Thesis (1)
Is part of the Bibliography
- no (25)
Keywords
- routing (4)
- mixed-integer programming (3)
- network design (3)
- survivable network design (3)
- branch-and-cut algorithm (2)
- demand-wise shared protection (2)
- integer programming (2)
- multi-layer network design (2)
- Branch-and-cut-and-price (1)
- Dimensionierung (1)
- Mehrfachausfälle (1)
- Multi-layer-Netzen Ausfallsicherheit (1)
- Netzplanung (1)
- Optical access networks (1)
- Optimierung (1)
- Optimization (1)
- Optische Zugangsnetze (1)
- Praxisstudie (1)
- SNDlib (1)
- Spaltengenerierung (1)
- Steiner trees (1)
- Telekommunikationsnetze (1)
- branch-and-cut (1)
- branch-and-cut-and-price (1)
- capacitated network design (1)
- column generation (1)
- complexity (1)
- cutting planes (1)
- data library (1)
- energy efficiency (1)
- gemischt-ganzzahlige Optimierung (1)
- general flow-cutset inequalities (1)
- grooming (1)
- hardware configuration (1)
- heuristics (1)
- hop limits (1)
- integer linear programming (1)
- link and path restoration (1)
- mixed integer rounding (1)
- multi-hour (1)
- multi-layer (1)
- multi-layer networks (1)
- multi-period (1)
- network availability (1)
- network optimization (1)
- optimization (1)
- power consumption (1)
- pricing (1)
- resilience (1)
- restoration (1)
- survivable multi-layer network design (1)
- telecommunication network (1)
- telecommunication network design (1)
- telecommunication networks (1)
Institute
- Mathematical Optimization (18)
- ZIB Allgemein (7)
This report combines the contributions to INOC 2005 (Wessä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.
We present an integer linear programming model for the design of multi-layer telecommunication networks. The formulation integrates hardware, capacity, routing, and grooming decisions in \emph{any} n umber of network layers. Practical hardware restrictions and cost can accurately be taken into account for technologies based on connection-oriented routing protocols.
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.
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.
We investigate the impact of link and path restoration on the cost of telecommunication networks. The surprising result is the following: the cost of an optimal network configuration is almost independent of the restoration concept if (i) the installation of network elements (ADMs, DXCs, or routers) and interface cards, (ii) link capacities, and (iii) working and restoration routings are simultaneously optimized. We present a mixed-integer programming model which integrates all these decisions. Using a branch-and-cut algorithm (with column generation to deal with all potential routing paths), we solve structurally different real-world problem instances and show that the cost of optimal solutions is almost independent of the used restoration concept. In addition, we optimize spare capacities for given shortest working paths which are predetermined with respect to different link metrics. In comparison to simultaneous optimization of working and restoration routings, it turns out that this approach does not allow to obtain predictably good results.
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.
In this paper we assess to which extent trenching costs of an FTTx network are unavoidable, even if technical side constraints are neglected. For that purpose we present an extended Steiner tree model. Using a variety of realistic problem instances we demonstrate that the total trenching cost can only be reduced by about 5 percent in realistic scenarios. This work has been funded by BMBF (German Federal Ministry of Education and Research) within the program "KMU-innovativ".