Research
Systems & Architecture
Bio & Medical
Networking
Processor architecture
|
|
Locality aware distributed object locating and routing (DOLR)
Distributed object locating and routing (DOLR) is the process of searching for an object in an open network without using a central server. DOLR can be used in large scale distributed services such as DNS, peer to peer file sharing, Voice over IP (VOIP), web caching, instant messaging, etc.
Locality aware DOLR is a class of DOR schemes whose searching cost takes into account of the distance between the source and destination in the search strategy design.
The most important two performance measures of a locality aware DOLR scheme are stretch of searching and space of search structure,
where stretch is the ratio between the actual travel distance divided by the shortest distance from a source to its destination.
Existing locality aware DOLR schemes, e.g., LLS[1], Stalk[3], MLS[4], PRR[5], Tapestry[7], Pastry[6], LAND[2], achieve constant stretch and logarithmic space.
In this research, we explore the relationship between the stretch and space of a DOLR scheme. Our preliminary result suggests that one can gain considerable flexibility in design tradeoffs by exploring an interesting relationship between the two parameters.
 preliminary result illustration
References
[1]. I. Abraham, D. Dolev, and D. Malkhi. LLS: a locality aware location service for mobile ad hoc networks. In DIALM-POMC '04: Proceedings of the 2004 joint workshop on Foundations of mobile computing, pages 75-84, New York, NY, USA, 2004. ACM Press.
[2]. I. Abraham, D. Malkhi, and O. Dobzinski. Land: stretch (1 + e) locality-aware networks for dhts. In SODA '04: Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages 550-559, Philadelphia, PA, USA, 2004. Society for Industrial and Applied Mathematics.
[3]. M. Demirbas, A. Arora, T. Nolte, and N. Lynch. Brief announcement: Stalk: a self-stabilizing hierarchical tracking service for sensor networks. In PODC '04: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, pages 78-378, New York, NY, USA, 2004. ACM Press.
[4]. R. Flury and R. Wattenhofer. Mls:: an efficient location service for mobile ad hoc networks. In MobiHoc '06: Proceedings of the seventh ACM international symposium on Mobile ad hoc networking and computing, pages 226_237, New York, NY, USA, 2006. ACM Press.
[5]. C. Plaxton, R. Rajaraman, and A. W. Richa. Accessing nearby copies of replicated objects in a distributed environment. In SPAA '97: Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, pages 311_320, New York, NY, SA, 1997. ACM Press.
[6]. A. Rowstron and P. Druschel. Pastry: Scalable, decentralized object location, and Routing for large-scale peer-to-peer systems. In IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), pages 329_350, 2001.
[7]. B. Y. Zhao, J. D. Kubiatowicz, and A. D. Joseph. Tapestry: An infrastructure for fault-tolerant wide-area location and. Technical report, Berkeley, CA, USA, 2001.
|
