One-Shot Multiple Disjoint Path Discovery Protocol (1S-MDP)

Abstract

Multipath routing over disjoint paths is a classic solution to allow better resource allocation, resilience, and security. Current proposals rely on centralised computation or iterative distributed algorithms and exhibit large convergence times. We propose 1S-MDP, a distributed mechanism based on a single network exploration with concurrent path selection to discover multiple available paths among the target node and the remaining nodes in the network. The paper evaluates 1S-MDP in two different scenarios against previous solutions. We show how it reduces the convergence time by several orders of magnitude with a small decrease in the number of disjoint paths discovered.