ISE03-6: An Intersection-Based Multipath Routing Scheme

We consider the problem of choosing multiple paths across an overlay network in order to provide applications with high-throughput data transfer. Approaches based on traditional (link state) routing algorithms involve a substantial (quadratic) overhead for exchange of state information in fully-connected overlays. Moreover, in the absence of coordination, an apparently "good" link may be selected by multiple sessions simultaneously, causing it to become congested. The simple solution-more frequent exchange of state information-only exacerbates the overhead problem. We present an alternative algorithm that uses a lazy approach to collect link state information, and computes paths by finding the intersection of sets of candidate intermediate hops. Results from experiments show that this intersection-based approach produces paths that provide better performance, has significantly lower overhead, and distributes load more evenly through the network than link-state alternatives.