DIMR: Disjoint Interdomain Multipath Routing

Interdomain Multipath Routing, which allows an AS to transport packets to the same destination via different paths, is a promising technique for achieving high bandwidth, high resiliency and fast reaction to failures. However, previous Interdomain Multipath Routing algorithms often produce overlapped paths, thus are vulnerable to the failure of bottlenecks, and are also inefficient to support interdomain traffic engineering or concurrent multipath transfer. In this paper, we propose Disjoint Interdomain Multipath Routing (DIMR), which helps more ASes to discover two disjoint paths for each destination AS. The core idea of DIMR is a novel concept named path pair, which combines two disjoint or partly disjoint paths. We design the rules of path pair selection and build a theoretical model to formally prove the convergence of a network running DIMR. To fully utilize the disjoint paths, we also propose two packet forwarding approaches, both of which are guaranteed to be loop-free. Our simulation results show thatDIMR enables about 90% of multi-connected ASes to install two disjoint paths.