Relay Placement Problem
To increase reliability and robustness of mission-critical
services in the event of network failures, 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. The first path is defined by the
intra-domain routing protocol running within the AS; the second
path is defined as an overlay path that passes through a
strategically placed relay node inside the AS. The key
question then is how to place such relay nodes inside an AS, which
is the focus of our work.
Methodology
We take a graph-theoretic approach in viewing the network
and propose our algorithms for relay placement.
Even though completely disjoint paths are preferred,
we note that it is often not possible to find such
overlay paths in real networks.
Towards that end, we and formalize the intuitive notion of
penalty for partially disjoint paths
and calculate the the fraction of traffic that goes via the
overlapped links as the penalty of using partially disjoint paths.
The metric turns out to be very useful in measuring how two paths
are disjoint in general.
We propose two heuristic algorithms for relay placement:
Greedy and Local.
Key Results
We apply our algorithms on three different types of topology data
- real, inferred, and synthetic - and demonstrate that our method increases networkwide
resilience against a single point of failure. Using daily topology snapshots and network events log obtained from an operational tier-1 ISP and hypothetical traffic matrix, we obtained the following results.
|
Division of Computer Science Korea Advanced Institure of Science and Technology 373-1 Gusung-dong, Yusung-gu Daejeon 305-701, Republic of Korea |