Optimizing Flow Thinning Protection in Multicommodity Networks with Variable Link Capacity
Résumé
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.
Mots clés
robust optimization
multiple partial link failures
mixed-integer programming
multicommodity flows
path generation
survivable network design
and Networks
Information
programming: integer: algorithms: Benders/decomposition Area of review: Games
robust optimization Subject classifications: networks/graphs: multicommodity
Domaines
Recherche opérationnelle [math.OC]
Loading...