Optimization Approach to Minimize Backup Capacity Considering Routing in Primary and Backup Networks for Random Multiple Link Failures

Soudalin KHOUANGVICHIT  Nattapong KITSUWAN  Eiji OKI  

Publication
IEICE TRANSACTIONS on Communications   Vol.E103-B   No.7   pp.726-735
Publication Date: 2020/07/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.2019EBP3173
Type of Manuscript: PAPER
Category: Network
Keyword: 
link failure,  optimization problem,  backup capacity,  probabilistic survivability guarantee,  

Full Text: PDF>>
Buy this Article




Summary: 
This paper proposes an optimization approach that designs the backup network with the minimum total capacity to protect the primary network from random multiple link failures with link failure probability. In the conventional approach, the routing in the primary network is not considered as a factor in minimizing the total capacity of the backup network. Considering primary routing as a variable when deciding the backup network can reduce the total capacity in the backup network compared to the conventional approach. The optimization problem examined here employs robust optimization to provide probabilistic survivability guarantees for different link capacities in the primary network. The proposed approach formulates the optimization problem as a mixed integer linear programming (MILP) problem with robust optimization. A heuristic implementation is introduced for the proposed approach as the MILP problem cannot be solved in practical time when the network size increases. Numerical results show that the proposed approach can achieve lower total capacity in the backup network than the conventional approach.