90B18 Communication networks [See also 68M10, 94A05]
Refine
Year of publication
Document Type
- ZIB-Report (32)
- Doctoral Thesis (3)
- Habilitation (1)
- Master's Thesis (1)
Language
- English (37) (remove)
Has Fulltext
- yes (37)
Is part of the Bibliography
- no (37)
Keywords
- integer programming (8)
- network design (6)
- optical networks (4)
- Integer Programming (3)
- Routing (3)
- UMTS (3)
- wavelength assignment (3)
- Network Performance (2)
- Operation Research (2)
- Resource Allocation (2)
Institute
- ZIB Allgemein (24)
- Mathematical Optimization (14)
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.
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.
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.
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.
Application of Multistage Stochastic Programming in Strategic Telecommunication Network Planning
(2010)
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.
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.
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.
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.
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.