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.