Efficient Lookup on Unstructured Topologies
Efficient Lookup on Unstructured Topologies
Files
Publication or External Link
Date
2006-03-02T17:22:28Z
Authors
Morselli, Ruggero
Bhattacharjee, Bobby
Marsh, Michael A.
Srinivasan, Aravind
Advisor
Citation
DRUM DOI
Abstract
We present LMS, a protocol for efficient lookup
on unstructured networks.
Our protocol uses a virtual namespace
without imposing specific
topologies. It is more efficient than existing lookup
protocols for unstructured networks, and thus is an attractive
alternative for applications in which the topology cannot be
structured as a Distributed Hash Table (DHT).
We present analytic bounds for the worst-case performance of our
protocol.
Through detailed simulations (with up to 100,000 nodes), we show that the
actual performance on realistic topologies is significantly better.
We also show in both simulations and a complete implementation (which
includes
over five hundred nodes) that our protocol is inherently robust against
multiple node failures and can adapt its replication strategy to optimize
searches according to a specific heuristic.
Moreover, the simulation demonstrates the resilience of LMS to high
node turnover rates, and that it can easily adapt to orders of magnitude
changes in network size.
The overhead incurred by LMS is small, and its performance approaches
that of DHTs on networks of similar size.