Survivable multipath routing using link penalization

Most previous schemes for survivable routing assume that the maximum number of simultaneous link failures is known. In this paper, we take an alternative approach by introducing link failure probabilities to the routing problem, and allowing each link to be used for several channels. Based on these assumptions, we formulate a survivable multipath routing problem for point-to-point communications. We then develop two heuristic multipath routing schemes for this problem: CPMR (conditional-penalization multipath routing) and SPMR (successive-penalization multipath routing). To deal with the difficulty that link-sharing causes, our schemes use "link penalization" methods to control (but not prohibit) link-sharing. We show via simulation that our schemes have significantly higher routing success rates than a routing scheme that searches for disjoint paths.