Placing Relay Nodes for Intra-Domain Path Diversity

Abstract

To increase reliability and robustness of missioncritical services in the face of routing changes, it is often desirable and beneficial to take advantage of path diversity provided by the network topology. One way of achieving this inside a single Autonomous System (AS) is to use two paths between every Origin-Destination (OD) pair. One path is the default path defined by the intra-domain routing protocol; the other path is defined as an overlay path that passes through a strategically placed relay node. The key question then is how to place such relay nodes inside an AS, which is the focus of this paper. We propose two heuristic algorithms to find the positions of relay nodes such that every OD pair has an overlay path, going through a relay node, that is disjoint from the default path. When it is not possible to find completely disjoint overlay paths, we allow overlay paths to have overlapped links with default paths. Since overlapped links diminish the robustness of overlay paths against a single point of failure, we introduce the notion of penalty for partially disjoint paths. We apply our algorithms on three different types of topology data – real, inferred, and synthetic – and show that our algorithms find relay nodes of close-to-minimum penalty. Using daily topology snapshots and network event log, we also show that our choices for relay nodes are relatively insensitive to network dynamics; which is very important for a placement algorithm to be viable and practical. Meeyoung Cha and Sue Moon are supported by Korea Science and Engineering Foundation through Advanced Information Technology Research Center (AITrc). Chong-Dae Park is supported by Brain Korea 21 Project through the school of information technology in KAIST. Part of this work was done while Meeyoung Cha was visiting Center for Discrete Mathematics and Theoretical Computer Science (DIMACS).