Routing on the Shortest Pairs of Disjoint Paths

Recent trends point towards communication networks will be multi-path in nature to increase failure resilience, support load-balancing and provide alternate paths for congestion avoidance. We argue that the transition from single-path to multi-path routing should be as seamless as possible in order to lower the deployability barrier for network operators. Therefore, in this paper we are focusing on the problem of routing along the shortest pairs of disjoint paths between each source-destination pair over the currently deployed link-state routing architecture. We show that the union of disjoint path-pairs towards a given destination has a special structure, and we propose an efficient tag encoding scheme which requires only one extra forwarding table entry per router per destination. Our numerical evaluations demonstrate that in real-world topologies usually only 4 bit tags are sufficient in the packet headers to route on the disjoint path-pairs. Finally, we show that our tags automatically encode additional paths beyond the shortest pair of disjoint paths, including the shortest paths themselves, which enables incremental deployment of the proposed method.