Skip to main content

Technical Reports: CMU-CyLab-07-012

Title:Availability-Oriented Path Selection in Multi-Path Routing
Authors:Xin Zhang, Adrian Perrig, and Hui Zhang
Publication Date:August 25, 2007


Multi-path routing is effective to enhance network availability, by selecting multiple  failure-independent paths for reaching one destination in the hope to survive individual path failures. Researchers suggest to select IP-layer topologically disjoint paths, assuming that they are failure-independent and can hardly fail simultaneously. Unfortunately, failure correlations lurking behind the IP-layer topology can surreptitiously squash availability gained through multi-path routing, because selected paths can fail simultaneously. Spurred by this observation, we propose a new path metric and selection scheme resilient to failure correlations between topologically disjoint paths, by utilizing path availability history to reveal failure correlations. This paper presents a first stride towards the new direction of availability-oriented multi-path selection, with formal and systematic problem definition, modeling, algorithms, and evaluation of our scheme.

Full Report: CMU-CyLab-07-012