Abstract
It is a challenge for the traditional centralized or hierarchical Grid architecture to manage the large-scale and dynamic resources, while providing scalability. The Peer-to-Peer (P2P) model offers a prospect of dynamicity, scalability, and availability of a large pool of resources. By integrating the P2P philosophy and techniques into a Grid architecture, P2P Grid system is emerging as a promising platform for executing large-scale, resource intensive applications. There are two typical resource discovery approaches for a large-scale P2P system. The first one is an unstructured approach which propagates the query messages to all nodes to locate the required resources. The method does not scale well because each individual query generates a large amount of traffic and the network quickly becomes overwhelmed by the messages. The second one is a structured approach which places resources at specified locations to make subsequent queries easier to satisfy. However, the method does not support multi-attribute range queries and may not work well in the network which has an extremely transient population. This paper proposes and designs a large-scale P2P Grid system which employs an Ant Colony Optimization (ACO) algorithm to locate the required resources. The ACO method avoids a large-scale flat flooding and supports multi-attribute range query. Multiple ants can be employed to improve the parallelism of the method. A simulator is developed to evaluate the proposed resource discovery mechanism. Comprehensive simulation results validate the effectiveness of the proposed method compared with the traditional unstructured and structured approaches.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Andrzejak A, Graupner S, Kotov V, Trinks H (2004) Algorithms for self-organization and adaptive service placement in dynamic distributed systems. Technical report HPL-2002-259. HP Laboratories Palo Alto
Arlitt M, Jin T (1999) Workload characterization of the 1998 world cup web site. Technical report HPL-1999-35 (R.1)
Basu S, Banerjee S, Sharma P, Lee S (2005) NodeWiz: peer-to-peer resource discovery for Grids. In: Proc of IEEE int symposium on domain computing and the Grid (CCGrid 2005), vol 1, pp 213–220
Barabási A, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509–512
Cai M, Frank M, Chen J, Szekely P (2003) MAAN: a multi-attribute addressable network for Grid information services. In: Proc 4th int workshop on Grid computing, pp 184–192
Cao J (2004) Self-organizing agents for Grid load balancing. In: Proc of the fifth IEEE/ACM international workshop on Grid computing, pp 388–395
Colorni A, Dorigo M, Maniezzo V (1992) Distributed optimization by ant colonies. In: Proc of the first European conference on artificial life, pp 134–142
Deng Y, Wang F (2007) Opportunities and challenges of storage Grid enabled by Grid service. ACM SIGOPS Oper Syst Rev 41(4):79–82
Deng Y, Wang F (2007) A heterogeneous storage Grid enabled by Grid service. ACM SIGOPS Oper Syst Rev 41(1):7–13. Special issue: File and storage systems
Deng Y, Wang F, Helian N, Wu S, Liao C (2008) Dynamic and scalable storage management architecture for Grid oriented storage devices. Parallel Comput 34(1):17–31
Foster I, Kesselman C, Tuecke S (2001) The anatomy of the Grid: enabling scalable virtual organizations. Int J High Perform Comput Appl 15(3):200–222
Iamnitchi A, Foster I, Nurmi D (2002) A peer-to-peer approach to resource discovery in Grid environments. In: Proc of the 11th symposium on high performance distributed computing, Edinburgh, UK, August 2002, pp 419–434
Kubiatowicz J, Bindel D, Chen Y et al (2000) OceanStore: an architecture for global-scale persistent storage. In: Proc of the 9th int conf on architectural support for programming languages and operating systems (ASPLOS 2000), pp 190–201
Lua E, Crowcroft J, Pias M, Sharma R, Lim S (2005) A survey and comparison of peer-to-peer overlay network schemes. IEEE Commun Surv Tutor 7(2):72–93
Lv Q, Cao P, Cohen E, Li K, Shenker S (2002) Search and replication in unstructured peer-to-peer networks. In: Proc of the 16th ACM int conf on supercomputing (ICS’02), New York, pp 84–95
Mastroianni C, Talia D, Verta O (2005) A P2P approach for membership management and resource discovery in Grids. In: Proc of the int conf on information technology (ITCC05), pp 168–174
Medina A, Lakhina A, Matta I, Byers J (2001) BRITE: an approach to universal topology generation. In: Proc of the international workshop on modeling, analysis and simulation of computer and telecommunications systems (MASCOTS’01), pp 346–353
Monitoring and discovery system. http://www.globus.org/toolkit/mds/
Montresor A, Meling H, Montresor A (2002) Messor: load-balancing through a swarm of autonomous agents. Technical report UBLCS-2002-11, Dept of Computer Science, University of Bologna
Ritchie G, Levine J (2004) A hybrid ant algorithm for scheduling independent jobs in heterogeneous computing environments. In: Proc of the 23rd workshop of the UK planning and scheduling special interest group
Rowstron A, Druschel P (2001) Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility. In: Proc of the 18th ACM symposium on operating systems principles (SOSP ’01), pp 188–201
Stoica I, Morris R, Karger D, Kaashoek F, Balakrishnan H (2001) Chord: a scalable peer-to-peer lookup service for internet applications. In: Proceedings of the 2001 ACM SIGCOMM conference, pp 149–160
Sylvia R, Scott S, Ion S (2002) Routing algorithms for DHTs: some open questions. In: Proc of the 1st int workshop on peer-to-peer systems (IPTPS’02). Springer, Heidelberg, pp 45–52
Talia D, Trunfio P (2003) Towards a synergy between P2P and Grids. IEEE Internet Comput 7(4):94–96
Waxman B (1998) Routing of multipoint connections. IEEE J Sel Areas Commun 6(9):1617–1622
Zhu C, Liu Z, Zhang W, Xiao W, Yang D (2003) Analysis on greedy-search based service location in P2P service Grid. In: Proc of peer-to-peer computing, pp 110–117
Author information
Authors and Affiliations
Corresponding author
Additional information
The initial work in this paper was conducted when Yuhui Deng was a research officer in Cranfield University. This paper was revised after Yuhui Deng joined EMC research China as a senior research scientist.
Rights and permissions
About this article
Cite this article
Deng, Y., Wang, F. & Ciura, A. Ant colony optimization inspired resource discovery in P2P Grid systems. J Supercomput 49, 4–21 (2009). https://doi.org/10.1007/s11227-008-0214-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11227-008-0214-0