Optimizing Flow Thinning Protection in Multicommodity Networks with Variable Link Capacity

Michał Pióro (), Yoann Fouquet (), Dritan Nace () and Michael Poss ()
Additional contact information
Michał Pióro: Institute of Telecommunications, Warsaw University of Technology, 00-665 Warsaw, Poland; and Department of Electrical and Information Technology, Lund University, 221 00 Lund, Sweden
Yoann Fouquet: Sorbonne universités, Université de technologie de Compiègne, UMR CNRS 7253 Heudiasyc, 60203 Compiègne cedex, France
Dritan Nace: Sorbonne universités, Université de technologie de Compiègne, UMR CNRS 7253 Heudiasyc, 60203 Compiègne cedex, France
Michael Poss: UMR CNRS 5506 LIRMM, Université de Montpellier, 161 rue Ada, 34392 Montpellier Cedex 5, France

Operations Research, 2016, vol. 64, issue 2, 273-289

Abstract: Flow thinning (FT) is a concept of a traffic routing and protection strategy applicable to communication networks with variable capacity of links. In such networks, the links do not attain their nominal (maximum) capacity simultaneously, so in a typical network state only some links are fully available whereas on each of the remaining links only a fraction of its maximum capacity is usable. Every end-to-end traffic demand is assigned a set of logical tunnels whose total capacity is dedicated to carry the demand’s traffic. The nominal (i.e., maximum) capacity of the tunnels, supported by the nominal (maximum) link capacity, is subject to state-dependent thinning to account for variable capacity of the links fluctuating below the maximum. Accordingly, the capacity available on the tunnels is also fluctuating below their nominal levels and hence the instantaneous traffic sent between the demand’s end nodes must accommodate to the current total capacity available on its dedicated tunnels. The related multi-commodity flow optimization problem is (N-script)(P-script) -hard and its noncompact linear programming formulation requires path generation. For that, we formulate an integer programming pricing problem, at the same time showing the cases when the pricing is polynomial. We also consider an important variant of FT, affine thinning, that may lead to practical FT implementations. We present a numerical study illustrating traffic efficiency of FT and computational efficiency of its optimization models. Our considerations are relevant, among others, for wireless mesh networks utilizing multiprotocol label switching tunnels.

Keywords: survivable network design; multiple partial link failures; mixed-integer programming; multicommodity flows; path generation; robust optimization (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2016.1486 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:64:y:2016:i:2:p:273-289

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().