Risk Minimization Routing Against Geographically Correlated Failures

Abstract

Regional failures, such as natural disaster or malicious attack, have become a major threat to the construction of future reliable communication network. The regional failures usually cause a large number of disconnected nodes simultaneously and influence the network for a long time. However, a routing scheme that is resilient to such geographically correlated failures is still unexplored. In this paper, we provide a comprehensive study of the disaster resilient routing dealing with the regional failure in operational IP backbone networks. It is notable that the path with minimal risk (i.e., minimal failure probability) is not necessarily the shortest path. The main challenge of finding such paths is that regional failure is unpredictable in terms of time, location, and the affected area. To this end, in combination with the computational geometry tool, we develop effective algorithms to find the minimal risk path between end node pairs to tolerate random regional failures. We show that in contrast to the conventional shortest path, a little longer path can be more effective to the disasters. After selecting such a path as the primary path, we turn to find a secondary backup path. In contrast to the conventional single link/node failure, a regional failure disrupts a large number of network components, simultaneously. As a result, how to find backup paths for re-establishment of the corrupted paths will raise a novel fairness issue. Specifically, during the backup path allocation, we focus on routing fairness to bound the worst-case user experience. A metric is proposed based on which an ILP is formulated. The extensive simulations validate that such an issue is non-negligible in face of regional failure scenarios.

Keywords

• Network reliability
• network protection
• network recovery
• regional failure
• routing