Abstract | ||
---|---|---|
We present a comparison of structured and unstructured overlays that decouples overlay topology maintenance from query mechanism. Structured overlays provide efficient 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. |
Year | Venue | Keywords |
---|---|---|
2005 | NSDI | efficient support,random walk,structured overlay,structural constraint,overlay topology,unstructured overlay,topology constraint,structured topology,decouples overlay topology maintenance,complex query |
Field | DocType | Citations |
Overlay topology,Computer science,Random walk,Selection algorithm,Network topology,Theoretical computer science,Exploit,Overlay,Distributed computing | Conference | 65 |
PageRank | References | Authors |
3.50 | 19 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Miguel Castro | 1 | 5088 | 328.69 |
Manuel Costa | 2 | 1589 | 88.62 |
Antony Rowstron | 3 | 6605 | 542.43 |