Grid resource discovery based on semantic P2P communities

ABSTRACT

Grid technologies enable the sharing of a wide variety of resources. The full use of these resources requires effective resource discovery mechanisms. However, the complicated and dynamic characteristics of grid resources make sharing and discovering them a challenge. In this paper, we propose a semantic community approach to enable efficient resource discovery in grids. The system clusters nodes into communities according to their semantic properties. The community construction and maintenance is fully decentralized and self-organizing. This structure helps prune the searching space and reduce the cost of searching. The system exhibits many desirable properties: it supports complex queries and is fully decentralized, scalable, and efficient. Our simulation results show how searching the grids can take advantage of semantic communities to reduce searching costs and improve the quality of results.

REFERENCES

• 1: Yatin Chawathe , Sylvia Ratnasamy , Lee Breslau , Nick Lanham , Scott Shenker, Making gnutella-like P2P systems scalable, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.864000]
• 2: B. Yang, H. Garcia-Molina, "Efficient search in peer-to-peer networks," Proc. of CDCS'02, Vienna, Austria, July.
• 3: Farnoush Banaei-Kashani , Cyrus Shahabi, Criticality-based Analysis and Design of Unstructured Peer-to-Peer Networks as "Complex Systems", Proceedings of the 3st International Symposium on Cluster Computing and the Grid, p.351, May 12-15, 2003
• 4: Watts, D. J., Strogztz, S,: Collective dynamics of 'small-world' networks. Nature 393 (1998).
• 5: Adriana Iamnitchi , Ian Foster , Daniel C. Nurmi, A Peer-to-Peer Approach to Resource Location in Grid Environments, Proceedings of the 11 th IEEE International Symposium on High Performance Distributed Computing HPDC-11 20002 (HPDC'02), p.419, July 24-26, 2002
• 6: Globus Toolkit: http://www.globus.org/toolkit/.
• 7: T. R. Gruber, "Toward principles for the design of ontologies used for knowledge sharing," in Formal Ontology in Conceptual Analysis and Knowledge Representation, 1993.
• 8: Herbert A. Simon, The sciences of the artificial (3rd ed.), MIT Press, Cambridge, MA, 1996
• 9: N. J. A. Harvey, M. B. Jones, S. Saroiu, M. Theimer, and A. Wolman. "SkipNet:A Scalable Overlay Network with Practical Locality Properties". In Proc. of the Fourth USENIX USITS '03.
• 10: S. Shi, Y. Guanwen, D. Wang, J. Yu, S. Qu and M. Chen "Making Peer-to-Peer Keyword Searching Feasible Using Multi-level Partitioning". Proc. Of the 3rd International Workshop on Peer-to-Peer Systems.
• 11: Gnutella website. http://gnutella.wego.com/.
• 12: H. Lican, W. Zhaohui, and P. Yunhe. "A scalable and effective architecture for Grid Services discovery". In Proc. of the First Workshop on Semantics in Peer-to-Peer and Grid Computing. 2003.
• 13: B. Yang and H. Garcia-Molina, "Designing a Super-Peer Ntrwork," Proc. 19th Int'l Conf. Data Engineering, Los Alamitos, CA, March 2003.
• 14: Qin Lv , Pei Cao , Edith Cohen , Kai Li , Scott Shenker, Search and replication in unstructured peer-to-peer networks, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 15: Adriana Ioana Iamnitchi , Ian Foster, Resource discovery in large resource-sharing environments, 2003
• 16: Ben Y. Zhao , John D. Kubiatowicz , Anthony D. Joseph, Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and, University of California at Berkeley, Berkeley, CA, 2001
• 17: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 18: 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
• 19: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 20: Adamic, L., Huberman, B., Lukose, R., Puniyani, A.: "Search in power law networks". Physical Review (2001)
• 21: P. Reynolds and A. Vahdat. "Efficient Peer-to-Peer Keyword Searching". In Proceedings of ACM/IFIP/USENIX Middleware, June 2003.
• 22: Min Cai , Martin Frank , Jinbo Chen , Pedro Szekely, MAAN: A Multi-Attribute Addressable Network for Grid Information Services, Proceedings of the Fourth International Workshop on Grid Computing, p.184, November 17-17, 2003
• 23: C. Tang and S. Dwarkadas. "Hybrid Gloablal-Local Indexing for Efficient Peer-to-Peer Information Retrieval". In Proceedings of USENIX NSDI, March 2004.
• 24: Douglas B. Lenat , R. V. Guha, Building Large Knowledge-Based Systems; Representation and Inference in the Cyc Project, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 25: S. Deerwester, S. T. Dumais, G. W. Furnas, T. K. Landauer, and R. Harshman. Indexing by latent semantic indexing. Journal of the American Society for Information Science, 1990.
• 26: S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, S. R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. Hypersearching the web. Scientific American, 1999.
• 27: DMOZ website. http://www.dmoz.org.
• 28: K. Sripanidkulchai, B. Maggs, and H. Zhang. Efficient content location using interest-based locality in peer-to-peer systems, In INFOCOM'03.
• 29: Haase, P., Siebes, R.: Peer selection in peer-to-peer networks with semantic topologyies. In: Proc. WWW2003.
• 30: 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
• 31: JXTA website. http://www.jxta.org/.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.4 System Management
          Subjects: Centralization/decentralization

General Terms:
Algorithms, Design, Management, Performance