Fast and Flow-Controlled Multi-Stage Network Recovery from Large-Scale Physical Failures

Kouichi GENDA  Hiroshi YAMAMOTO  Shohei KAMAMURA  

Publication
IEICE TRANSACTIONS on Communications   Vol.E99-B   No.8   pp.1824-1834
Publication Date: 2016/08/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.2016EBP3009
Type of Manuscript: PAPER
Category: Network
Keyword: 
network recovery,  large-scale failure,  flow control,  bandwidth allocation,  linear programming,  

Full Text: PDF>>
Buy this Article



Summary: 
When a massive network disruption occurs, repair of the damaged network takes time, and the recovery process involves multiple stages. We propose a fast and flow-controlled multi-stage network recovery method for determining the pareto-optimal recovery order of failed physical components reflecting the balance requirement between maximizing the total amount of traffic on all logical paths, called total network flow, and providing adequate logical path flows. The pareto-optimal problem is formulated by mixed integer linear programming (MILP). A heuristic algorithm, called the grouped-stage recovery (GSR), is also introduced to solve the problem when the problem formulated by MILP is computationally intractable in a large-scale failure. The effectiveness of the proposed method was numerically evaluated. The results show that the pareto-optimal recovery order can be determined from the balance between total network flow and adequate logical path flows, the allocated minimum bandwidth of the logical path can be drastically improved while maximizing total network flow, and the proposed method with GSR is applicable to large-scale failures because a nearly optimal recovery order with less than 10% difference rate can be determined within practical computation time.