Octopus: A Fault-Tolerant and Efficient Ad-hoc Routing Protocol.

Authors: Roie Melamed, Idit Keidar, and Yoav Barel.

In the 24th IEEE Symposium on Reliable Distributed Systems (SRDS 2005), pages 39-49, October 2005.
Full version accepted for publication in Wireless Networks (WINET), December 2006.


Mobile ad-hoc networks (MANETs) are failure-prone environments; it is common for mobile wireless nodes to intermittently disconnect from the network, e.g., due to signal blockage. This paper focuses on withstanding such failures in large MANETs: we present Octopus, a fault-tolerant and efficient position-based routing protocol. Fault-tolerance is achieved by employing redundancy, i.e., storing the location of each node at many other nodes, and by keeping frequently refreshed soft state. At the same time, Octopus achieves a low location update overhead by employing a novel aggregation technique, whereby a single packet updates the location of many nodes at many other nodes. Octopus is highly scalable: for a fixed node density, the number of location update packets sent does not grow with the network size. And when the density increases, the overhead drops. Thorough empirical evaluation using the ns2 simulator with up to 675 mobile nodes shows that Octopus achieves excellent fault-tolerance at a modest overhead: when all nodes intermittently disconnect and reconnect, Octopus achieves the same high reliability as when all nodes are constantly up.

Dowload SRDS 2005 paper: ps, ps.gz, pdf, pdf.gz.
Dowload WINET 2006 version: pdf, pdf.gz.

Talk slides: ppt.

Last modified: Thu Dec 14 15:48:42 IST 2006