Optimization Model for Backup Network Design with Primary and Backup Routing against Multiple Link Failures under Uncertain Traffic Demands

Eiji OKI

IEICE TRANSACTIONS on Communications   Vol.E104-B    No.4    pp.378-390
Publication Date: 2021/04/01
Publicized: 2020/10/06
Online ISSN: 1745-1345
DOI: 10.1587/transcom.2020EBP3084
Type of Manuscript: PAPER
Category: Network
link failure,  optimization problem,  backup capacity,  uncertain traffic demands,  

Full Text: PDF>>
Buy this Article

This paper proposes an optimization model under uncertain traffic demands to design the backup network to minimize the total capacity of a backup network to protect the primary network from multiple link failures, where the probability of link failure is specified. The hose uncertainty is adopted to express uncertain traffic demands. The probabilistic survivability guarantee is provided by determining both primary and backup network routing, simultaneously. Robust optimization is introduced to provide probabilistic survivability guarantees for different link capacities in the primary network model under the hose uncertainty. Robust optimization in the proposed model handles two uncertain items: uncertain failed primary link with different capacities and uncertain traffic demands. We formulate an optimization problem for the proposed model. Since it is difficult to directly solve it, we introduce a heuristic approach for the proposed model. By using the heuristic approach, we investigate how the probability of link failure affects both primary and backup network routing. Numerical results show that the proposed model yields a backup network with lower total capacity requirements than the conventional model for the link failure probabilities examined in this paper. The results indicate that the proposed model reduces the total capacity of the backup network compared to the conventional model under the hose uncertainty. The proposed model shares more effectively the backup resources to protect primary links by determining routing in both primary and backup networks.