Debunking some myths about structured and unstructured overlays Export

@inproceedings{citeulike:5892271, 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.}, address = {Berkeley, CA, USA}, author = {Castro, Miguel and Costa, Manuel and Rowstron, Antony}, booktitle = {NSDI'05: Proceedings of the 2nd conference on Symposium on Networked Systems Design \& Implementation}, citeulike-article-id = {5892271}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1251210}, keywords = {comparison, myths, p2p, structuredp2p, strucutured, unstructured, unstructuredp2p}, pages = {85--98}, posted-at = {2009-10-05 20:01:47}, priority = {0}, publisher = {USENIX Association}, title = {Debunking some myths about structured and unstructured overlays}, url = {http://portal.acm.org/citation.cfm?id=1251210}, year = {2005} }

TY - CONF ID - citeulike:5892271 L3 - citeulike-article-id:5892271 N2 - 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. AD - Berkeley, CA, USA EP - 98 TI - Debunking some myths about structured and unstructured overlays PB - USENIX Association T2 - NSDI'05: Proceedings of the 2nd conference on Symposium on Networked Systems Design \& Implementation SP - 85 KW - comparison KW - myths KW - p2p KW - structuredp2p KW - strucutured KW - unstructured KW - unstructuredp2p AU - Castro, Miguel AU - Costa, Manuel AU - Rowstron, Antony PY - 2005/// UR - http://portal.acm.org/citation.cfm?id=1251210 ER -