Network Congestion Minimization Models Based on Robust Optimization

Bimal CHANDRA DAS  Satoshi TAKAHASHI  Eiji OKI  Masakazu MURAMATSU  

Publication
IEICE TRANSACTIONS on Communications   Vol.E101-B   No.3   pp.772-784
Publication Date: 2018/03/01
Publicized: 2017/09/14
Online ISSN: 1745-1345
DOI: 10.1587/transcom.2017EBP3193
Type of Manuscript: PAPER
Category: Network
Keyword: 
backbone network,  second-order cone programming,  pipe model,  hose model,  network congestion ratio,  robust optimization,  ellipsoidal uncertainty set,  

Full Text: PDF>>
Buy this Article



Summary: 
This paper introduces robust optimization models for minimization of the network congestion ratio that can handle the fluctuation in traffic demands between nodes. The simplest and widely used model to minimize the congestion ratio, called the pipe model, is based on precisely specified traffic demands. However, in practice, network operators are often unable to estimate exact traffic demands as they can fluctuate due to unpredictable factors. To overcome this weakness, we apply robust optimization to the problem of minimizing the network congestion ratio. First, we review existing models as robust counterparts of certain uncertainty sets. Then we consider robust optimization assuming ellipsoidal uncertainty sets, and derive a tractable optimization problem in the form of second-order cone programming (SOCP). Furthermore, we take uncertainty sets to be the intersection of ellipsoid and polyhedral sets, and considering the mirror subproblems inherent in the models, obtain tractable optimization problems, again in SOCP form. Compared to the previous model that assumes an error interval on each coordinate, our models have the advantage of being able to cope with the total amount of errors by setting a parameter that determines the volume of the ellipsoid. We perform numerical experiments to compare our SOCP models with the existing models which are formulated as linear programming problems. The results demonstrate the relevance of our models in terms of congestion ratio and computation time.