Location based placement of whole distributed systems

ABSTRACT

The high bandwidth and low latency of the modern internet has made possible the deployment of distributed computing platforms. The XenoServe platform provides a distributed computing platform open to all and presents three major new challenges for resource discovery: Firstly, network location is key for effectively provisioning services, to mitigate against high-latency, high-load or component failure. Secondly, many services require a presence on several servers, with inter-related requirements. Finally, as the platform is open with respect to users and servers, large numbers of queries and updates are expected.To address these requirements we introduce and evaluate XenoSearch, a new distributed service for selecting the machines to host components of multi-node distributed systems and which is uniquely able to express and efficiently answer complex queries with inter-related location constraints. We demonstrate that XenoSearch represents a trade-off between accuracy and query time which avoids exhaustive search and supports multiple resources. In addition the performance of the algorithm and the quality of its server selections is investigated and the performance of the distributed service shown to be invariant as the number of nodes or items indexed increases.

REFERENCES

• 1: Larry Peterson, Tom Anderson, David Culler, and Timothy Roscoe. A blueprint for introducing disruptive technology into the internet. In Proc. 1st ACM HotNets Workshop, October 2002.
• 2: Controlling the XenoServer Open Platform. In Proc. 6th Int. Conf. Open Arch. and Network Programming (OPENARCH), April 2003.
• 3: I. Foster and C. Kesselman. Globus: A Metacomputing Infrastructure Toolkit. The Int. Journal of Supercomputer Application and High Performance Computing, 11(2):115--128, 1997.
• 4: F. Kelly. Models for a self-managed internet. Philisohical Transactions: Mathematical, Physical and Engineering Sciences, The Royal Society, London, 358(1773):2335--2348, August 2000.
• 5: D. Oppenheimer, J. Albrecht, D. Patterson, and A. Vahdat. Scalable wide-area resource discovery. Technical Report UCB//CSD-04-1334, UC Berkeley, July 2004.
• 6: Ashwin R. Bharambe , Mukesh Agrawal , Srinivasan Seshan, Mercury: supporting scalable multi-attribute range queries, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 7: A. Andrzejak and Z. Xu. Scalable, Efficient Range Queries for Grid Information Services. Technical Report HPL-2002-209, Hewlett-Packard Laboratories, Palo Alto, 2002.
• 8: Adriana Iamnitchi , Ian T. Foster, On Fully Decentralized Resource Discovery in Grid Environments, Proceedings of the Second International Workshop on Grid Computing, p.51-62, November 12, 2001
• 9: G. Hjaltason and H. Samet. Speeding up construction of quadtrees for spatial indexing. Technical Report TR-4033, Computer Science Department, University of Maryland, July 1999.
• 10: S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, Number 4598, 13 May 1983, 220, 4598:671--680, 1983.
• 11: David Spence. An implementation of a coordinate based location system. Technical Report UCAM-CL-TR-576, University of Cambridge, Computer Laboratory, November 2003.
• 12: Bongki Moon , H. v. Jagadish , Christos Faloutsos , Joel H. Saltz, Analysis of the Clustering Properties of the Hilbert Space-Filling Curve, IEEE Transactions on Knowledge and Data Engineering, v.13 n.1, p.124-141, January 2001 [doi>10.1109/69.908985]
• 13: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 14: J. Veizades, E. Guttman, C. Perkins, and S. Kaplin. Service location protocal, June 1997. Request for Comments RFC 2165.
• 15: Todd D. Hodes , Steven E. Czerwinski , Ben Y. Zhao , Anthony D. Joseph , Randy H. Katz, An architecture for secure wide-area service discovery, Wireless Networks, v.8 n.2/3, p.213-230, March-May 2002 [doi>10.1023/A:1013772027164]
• 16: P. Mockapetris. Domain names -- concepts and facilities, November 1987. RFC 1034.
• 17: C. Partridge, T. Mendez, and W. Milliken. Host Anycasting Service, November 1993. RFC1546.
• 18: James D. Guyton , Michael F. Schwartz, Locating nearby copies of replicated Internet servers, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.288-298, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• 19: Robbert Van Renesse , Kenneth P. Birman , Werner Vogels, Astrolabe: A robust and scalable technology for distributed system monitoring, management, and data mining, ACM Transactions on Computer Systems (TOCS), v.21 n.2, p.164-206, May 2003 [doi>10.1145/762483.762485]
• 20: Praveen Yalagandula , Mike Dahlin, A scalable distributed information management system, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 21: R. van Renesse and A. Bozdog. Willow: Dht, aggregation, and publish/subscribe in one protocol. In Proc. 3rd Int. Workshop on Peer-to-Peer Systems (IPTPS 2004), February 2004.
• 22: N. Coleman, R. Raman, M. Livny, and M. Solomon. Distributed policy management and comprehension with classified advertisements. Technical Report TR 1481, University of Wisconsin, Computer Science Department, April 2003.
• 23: Rajesh Raman , Miron Livny , Marvin Solomon, Policy Driven Heterogeneous Resource Co-Allocation with Gangmatching, Proceedings of the 12th IEEE International Symposium on High Performance Distributed Computing (HPDC'03), p.80, June 22-24, 2003
• 24: C. Liu and I. Foster. A constraint language approach to grid resource selection. Technical Report TR-2003-07, Department of Computer Science, University of Chicago, March 2003.
• 25: David Spence , Tim Harris, XenoSearch: Distributed Resource Discovery in the XenoServer Open Platform, Proceedings of the 12th IEEE International Symposium on High Performance Distributed Computing (HPDC'03), p.216, June 22-24, 2003
• 26: Cristina Schmidt , Manish Parashar, Flexible Information Discovery in Decentralized Distributed Systems, Proceedings of the 12th IEEE International Symposium on High Performance Distributed Computing (HPDC'03), p.226, June 22-24, 2003
• 27: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 28: S. Ratnasamy, J. Hellerstein, and S. Shenker. Range queries over DHTs. Technical Report IRB-TR-03-009, Intel Research Berkeley, June 2003.
• 29: King Lum Cheung , Ada Wai-Chee Fu, Enhanced nearest neighbour search on the R-tree, ACM SIGMOD Record, v.27 n.3, p.16-21, Sept. 1, 1998 [doi>10.1145/290593.290596]
• 30: J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984 [doi>10.1145/348.318586]
• 31: Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998
• 32: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
• 33: A. Gupta, D. Agrawal, and A. El Abbadi. Approximate range selection queries in Peer-to-Peer systems. Technical Report UCSB-CS-2002-23, Department of Computer Science, University of California at Santa Barbara, October 2002.
• 34: O.D. Sahin, A. Gupta, D. Agrawal, and A. El Abbadi. Query processing over Peer-To-Peer data sharing systems. Technical Report UCSB-CS-2002-28, Department of Computer Science, UC Santa Barbara, October 2002.
• 35: Amol Deshpande , Suman Nath , Phillip B. Gibbons , Srinivasan Seshan, Cache-and-query for wide area sensor databases, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872818]
• 36: L. Peterson, T. Anderson, D. Culler, and T. Roscoe. Sophia: An Information Plane for Networked Systems. In Proc. 2nd Workshop on Hot Topics in Networks (HotNets-II), November 2003.
• 37: R. Huebsch, J. Hellerstein, N. Lanham, B. Loo, S. Shenker, and I. Stoica. Querying the internet with pier. In Proc. VLDB, 2003.
• 38: Matthew Harren , Joseph M. Hellerstein , Ryan Huebsch , Boon Thau Loo , Scott Shenker , Ion Stoica, Complex Queries in DHT-based Peer-to-Peer Networks, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.242-259, March 07-08, 2002
• 39: M. Annamalai. Designing an Efficient Distributed Digital Library Database for Image Data, 1997.
• 40: Michael Stonebraker , Paul M. Aoki , Witold Litwin , Avi Pfeffer , Adam Sah , Jeff Sidell , Carl Staelin , Andrew Yu, Mariposa: a wide-area distributed database system, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.1, p.048-063, January 1996 [doi>10.1007/s007780050015]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed databases

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Distributed data structures

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems

General Terms:
Algorithms

Keywords:
location systems, peer-to-peer, resource discovery