Refine
Language
- English (12)
Keywords
- Circuit switching (1)
- Computational Study (1)
- IP-over-WDM (1)
- Mathematical Programming (1)
- Multi-layer Networks (1)
- Multi-layer networks (1)
- SNDlib (1)
- branch-and-cut (1)
- capacitated network design (1)
- cutset-polyhedra (1)
Project
- B3 (10)
Application Area
- B (10)
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 investigate the impact of hop-limited routing
paths on the total cost of a telecommunication network. For
different survivability settings (no survivability, link and path
restoration), the optimal network cost without restrictions on
the admissible path set is compared to the results obtained with
two strategies to impose hop limits on routing paths.
Based on optimal solutions for 10 real-world based problem
instances, we show that hop limits may lead to an unpredictable
raise in total network cost - even with large hop limits. The total
network cost with a hop limit of 7 hops for all demands can be up
to 25% higher than without restrictions on the admissible path
set. With our second strategy, which imposes demand-dependent
hop limits based on the shortest hop count, we obtain similar
results. This indicates that column generation techniques should
be applied to deal with all admissible paths.
We suggest a new model for the design of telecommunication networks which integrates
decisions about the topology, configuration of the switching hardware, link dimensioning,
and protected routing of communication demands. Applying the branch-andcut-
algorithm implemented in our network planning and optimization tool discnet, we
demonstrate that real-world based network planning instances of such an enhanced model
can be solved.
In this article, we present a mathematical model and an algorithm to support one of the central
strategic planning decisions of network operators: How to organize a large number of locations into
an hierarchy of network levels? We propose a mixed-integer program and a Lagrangian relaxation
based algorithm to model and solve this planning task. As one big advantage of this approach, not
only solutions but also worst-case quality gurarantees can be provided. We present a solution for
a G-WiN planning instance of DFN with 759 locations which has been computed in less than 30
minutes and which is (provably) less than 0.5 percent away from optimality.
Der scharfeWettbewerb innerhalb der Telekommunikationsbranche zwingt die Netzbetreiber dazu,
ihre Investitionen genau zu planen und immer wieder Einsparungsmaßnahmen durchzuführen.
Gleichzeitig ist es jedoch wichtig, die Qualität der angebotenen Dienste zu verbessern, um neue
Kunden zu gewinnen und langfristig an sich zu binden.
Die mathematische Optimierung bietet sich für viele solcher Aufgabenstellungen als hervorragend
geeignetes Planungswerkzeug an. Ziel dieses Artikels ist es, ihre Methodik und ihre Anwendung
speziell zur Kosten- und Qualitätsoptimierung in Kommunikationsnetzen vorzustellen. Anhand
von vier konkreten Planungsaufgaben aus dem Bereich der Festnetzplanung wird aufgezeigt, wie
sich komplexe Zusammenhänge in flexiblen mathematischen Modellen abbilden lassen und welche
Verfahren zur automatisierten Bearbeitung der Probleme eingesetzt werden können. Die hier vorgestellten
Methoden zeichnen sich insbesondere dadurch aus, dass sie neben hochwertigen Lösungen
auch eine Qualitätsgarantie liefern, mit der sich die Lösungen fundiert bewerten lassen. Die dokumentierten
Ergebnisse aus verschiedenen Industrieprojekten belegen die Eignung und Güte der
mathematischen Optimierung für die Praxis.
We consider the design of a logical network topology, together with node hardware, link capacities, and a survivable routing of demands. In addition to all single node failures, the routing must also survive multiple logical link failures caused by single failures in the underlying physical network. Furthermore, the number of logical links supported by a physical link is bounded. We propose an integer linear programming model for this design problem, together with a branch-and-cut based solution approach combined with column generation. The model and algorithm are tested on three real-world test instances, and preliminary results are given.
This paper deals with MIP-based primal heuristics to be used within a branch-and-cut approach for solving multi-layer telecommunication network design problems. Based on a mixed-integer programming formulation for two network layers, we present three heuristics for solving important subproblems, two of which solve a sub-MIP. On multi-layer planning instances with many parallel logical links, we show the effectiveness of our heuristics in finding good solutions early in the branch-and-cut search tree.
In this article we study capacitated network design problems. We unify and extend polyhedral results for directed, bidirected and undirected link capacity models. Based on valid inequalities for a network cut we show that regardless of the link capacity model, facets of the polyhedra associated with such a cut translate to facets of the original network design polyhedra if the two subgraphs defined by the network cut are (strongly) connected. Our investigation of the facial structure of the cutset polyhedra allows to complement existing polyhedral results for the three variants by presenting facet-defining flow-cutset inequalities in a unifying way. In addition, we present a new class of facet-defining inequalities, showing as well that flow-cutset inequalities alone do not suffice to give a complete description for single-commodity, single-module cutset polyhedra in the bidirected and undirected case – in contrast to a known result for the directed case. The practical importance of the theoretical investigations is highlighted in an extensive computational study on 27 instances from the Survivable Network Design Library (SNDlib).
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
We present an integer linear programming model for the design of multi-layer telecommunication
networks which are based on connection-oriented routing protocols. The formulation integrates hardware,
capacity, routing, and grooming decisions in any number of network layers. Practical hardware
restrictions and cost can accurately be taken into account.
In this article, we present a mathematical model and an algorithm to support one of the central
strategic planning decisions of network operators: How to organize a large number of locations into a
hierarchical network? We propose a solution approach that is based on mixed-integer programming and
Lagrangian relaxation techniques. As major advantage, our approach provides not only solutions but
also worst-case quality guarantees. Real-world scenarios with more than 750 locations have been solved
within 30 minutes to less than 1% off optimality.
In this paper, we present a model-based optimization approach for the design of multi-layer networks. The proposed framework is based on a series of increasingly abstract models – from a general technical system model to a problem specific mathematical model – which are used in a planning cycle to optimize the multi-layer networks. In a case study we show how central design questions for an IP-over-WDM network architecture can be answered
using this approach. Based on reference networks from the German research project EIBONE, we investigate the influence of various planning parameters on the total design cost. This includes a comparison of point-to-point vs. transparent optical layer architectures, different traffic distributions, and the use of PoS vs. Ethernet interfaces.