Algorithm for Multi-Path Hop-By-Hop Routing

Jens O. Oberender
Diploma Thesis, University of Passau and Technical University of Munich, 08/2003

The next generation internet provides resilient wide area networking. Resilience is the ability to resist outer influences such as link failures. During routing protocols reorganize the communication paths after a topology change, data loss can occur. Using multiple paths, network operation can continue after failure detection.

This work examines Multi-Path Hop-by-Hop routing where any single link failure can be locally recovered. We produce acyclic routing graphs for destination-based routing. Our approach results in two edge sets: active and reserve links. Active edges provide an acyclic graph embedding a spanning tree. Any failure that is not covered by redundant active edges is recovered by inserting a reserve edge. We guarantee recovery of the first link failure event and then seamlessly restore a HammockSet for the new topology.

Two similar approaches have been published. The O2-algorithm derived out of the project ”Key Components for the Mobile Internet of Next Generation” [Sch01] and constructs thin Hammock-Sets but is restricted to certain topologies. The MPA-algorithm [Nar00] succeeds on any topology, yet it cannot provide redundancy to all nodes. We specify topologies that allow stand-by recovery to all nodes and destinations, while we construct edge-maximized HammockSets.

For evaluation we introduce link significance, a measure for the forwarding function of inner HammockSet nodes. A heuristic algorithm optimizes the HammockSet layout for traffic distribution. It restricts the number of HammockSets on one network edge, increasing the bandwidth fraction available to the participating HammockSets.

A prototype implementation has been part of this work. It constructs HammockSets for any
destination node of a topology. The final chapter discusses the feasibility of implementing our approach in real-world systems. Further, we point out possibilities for future work.

Algorithm for Multi-Path Hop-By-Hop Routing (PDF)

Dieser Beitrag wurde unter The Peer-to-Peer Paradigm, Publications veröffentlicht. Setze ein Lesezeichen auf den Permalink.