Invited Session Fri.1.H 3002

Friday, 10:30 - 12:00 h, Room: H 3002

Cluster 23: Telecommunications & networks [...]

Optimization modeling of communication networks


Chair: Michal Pioro and Deep Medhi



Friday, 10:30 - 10:55 h, Room: H 3002, Talk 1

Michal Pioro
On a survivable network design problem with one or two failing links and elementary path-flows

Coauthors: Dritan Nace, Artur Tomaszewski, Mateusz Zotkiewicz


A well known problem in survivable network design consists in minimizing the cost of links under a single link failure scenario (any link can fail but only one at a time) assuming flow restoration. The problem, denoted by FR, assumes bifurcated primary and restoration flows, and stub release (the capacity of links released by failing flows is used for restoration). FR can be expressed as a linear program but only in a non-compact formulation with NP-hard separation. Because of that, FR is regarded as NP-hard itself although this has not been proved.
The paper considers a version of FR when only one predefined link or only two predefined links can fail. We assume that the primary paths cannot contain loops - an assumption commonly neglected. We show that the case with one failing link is polynomial while the case with two failing links is NP-hard. This is a new result that sheds light on FR also for the single link failure scenario. As a byproduct of the one-failing link case, we obtain an example of a non-compact LP formulation with NP-hard separation which actually describes a polynomial problem. Such an example has not been commonly known to the network design community before.



Friday, 11:00 - 11:25 h, Room: H 3002, Talk 2

Giuliana Carello
A network loading problem with shared protection and SRG: Formulations and ILP based hybrid heuristics

Coauthors: Bernardetta Addis, Federico Malucelli


Failure resiliency is an important issue in telecommunication networks. In real networks different links may share physical structures and therefore may be affected by the same physical fault. This complexity is captured by Shared Risk Groups (SRGs), which represent sets of links affected by the same fault. We focus on a shared protection scheme, according to which the backup capacity can be shared among different demands, provided that they are not affected by the same faults. We address a network loading problem where SRG and shared protection are considered. We propose a couple of mathematical models. As the problem seems extremely challenging from the computational point of view, we explore the possibility of adding some valid inequalities that have been successful in standard network design problem. Besides, we present some ILP based hybrid heuristic approaches. One approach considers the dynamic addition of constraints, while the other approach is based on a combination of greedy and local search. We report an extensive experimental comparison of all the proposed approaches.



Friday, 11:30 - 11:55 h, Room: H 3002, Talk 3

Uwe Steglich
Robust multi-layer network design under traffic demand uncertainty

Coauthor: Thomas Bauschert


We present an mixed-integer linear programming approach for a multi-layer network design problem under traffic demand uncertainty. This problem arises in the planning of IP (Internet Protocol) based networks, where the IP routers are interconnected by logical links that are paths in an underlying transport network. The transport network in turn might consist of different layers and technologies, e.g., an OTN layer (with electrical switching capability on ODU granularity) and a DWDM layer (with pure optical switching capability on wavelength granularity) which allows for optimum grooming and layer bypassing. Demand uncertainty results from daytime usage fluctuations, user behavior and external effects like BGP route flapping or server load balancing mechanisms and is regarded as big challenge for network operators. Our work is based on modifications of the \Gamma-robust design approach and the "Path over Path'' concept for multi-layer planning. Contrary to existing approaches our model considers multi-path routing, traffic grooming and layer skipping in parallel. We report computational results and limitations for realistic network scenarios and different transport network realizations.


  In particular, Texas Loans Online can cater to the needs of its residents. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis was obtained in Europe, Australia, New Zealand.