|
NSDI '05 — Abstract
Debunking Some Myths About Structured and Unstructured Overlays
Miguel Castro, Manuel Costa, and Antony Rowstron, Microsoft Research Cambridge
Abstract
We present a comparison of structured and unstructured overlays that decouples overlay topology maintenance from query mechanism. Structured overlays provide ef- ficient support for simple exact-match queries but they constrain overlay topology to achieve this. Unstructured overlays do not constrain overlay topology or query complexity because they use flooding or random walks to discover data. It is commonly believed that structured overlays are more expensive to maintain, that their topology constraints make it harder to exploit heterogeneity, and that they cannot support complex queries efficiently. We performed a detailed comparison study using simulations driven by real-world traces that debunks these widespread myths. We describe techniques that exploit structural constraints to achieve low maintenance overhead and we present a modified neighbour selection algorithm that can exploit heterogeneity effectively. We also describe techniques to perform floods and random walks on structured topologies. These techniques exploit structural constraints to support complex queries with better performance than unstructured overlays.
- View the full text of this paper in PDF.
Until May 2005, you will need your USENIX membership identification in order to access the full papers. The Proceedings are published as a collective work, © 2005 by the USENIX Association. All Rights Reserved. Rights to individual papers remain with the author or the author's employer. Permission is granted for the noncommercial reproduction of the complete work for educational or research purposes. USENIX acknowledges all trademarks within this paper.
- If you need the latest Adobe Acrobat Reader, you can download it from Adobe's site.
|
Need help? Use our Contacts page.
