Advanced

Optimizing flow thinning protection in multicommodity networks with variable link capacity

Pióro, Michał; Fouquet, Yoann; Nace, Dritan and Poss, Michael (2016) In Operations Research 64(2). p.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.... (More)

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 NP-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.

(Less)
Please use this url to cite or link to this publication:
author
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Mixed-integer programming, Multicommodity flows, Multiple partial link failures, Path generation, Robust optimization, Survivable network design
in
Operations Research
volume
64
issue
2
pages
17 pages
publisher
Inst Operations Research Management Sciences
external identifiers
  • scopus:84964613552
  • wos:000375603700001
ISSN
0030-364X
DOI
10.1287/opre.2016.1486
language
English
LU publication?
no
id
cd429782-4086-4b8a-a497-c2250ba13912
date added to LUP
2016-10-06 14:09:40
date last changed
2017-01-01 08:36:09
@article{cd429782-4086-4b8a-a497-c2250ba13912,
  abstract     = {<p>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 NP-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.</p>},
  author       = {Pióro, Michał and Fouquet, Yoann and Nace, Dritan and Poss, Michael},
  issn         = {0030-364X},
  keyword      = {Mixed-integer programming,Multicommodity flows,Multiple partial link failures,Path generation,Robust optimization,Survivable network design},
  language     = {eng},
  month        = {03},
  number       = {2},
  pages        = {273--289},
  publisher    = {Inst Operations Research Management Sciences},
  series       = {Operations Research},
  title        = {Optimizing flow thinning protection in multicommodity networks with variable link capacity},
  url          = {http://dx.doi.org/10.1287/opre.2016.1486},
  volume       = {64},
  year         = {2016},
}