Grid Resource Discovery Mechanism Based On Resource Clustering

Grid Resource Discovery Mechanism Based on Resource Clustering Chen JIng Yanshan University Department of Computer, College of Information Science & Engineering, Yanshan Uni. Qinhungdao, 066004

[email protected] ABSTRACT GRDS (Grid Resource Discovery Service) is one of the basic services in grid system, it provides a main way to query and locate the interested information, and the QoS (Quality of Service) of GRDS decides whether users may use information efficiently. In order to improve resource discovery efficiency and distinguish users’ difference in dynamic and heterogeneous grid environment, a new GRDS based on resource clustering (GRDS-RC) is presented in this paper. Firstly, GRDS-RC is divided into some peer-to-peer virtual community (P2PVC), and every P2PVC may execute the discovery function parallel. Secondly, resource clustering is defined by introducing similarity measure method, and every P2PVC is constructed according to the results of resource clustering. Thirdly, to reduce the overhead of query, query router algorithm is proposed. The simulation results show that GRIS-CR can improve the performance of grid and satisfy users’ demand.

Keywords Grid resource discovery, resource clustering, peer-to-peer virtual community, similarity measure; router algorithm

1. INTRODUCTION Grid technology has been research hotspot in recent years. As a kind of advanced infrastructure, grid connects multiple regional and national dynamic and heterogeneous resources to provide pervasive, consistent and inexpensive access interface for users who use all kinds of resources, application and services [1]. To extend the degree of resource sharing and cooperation working, the grid architecture need support different services and resource discovery. Dynamic and distributed resources, virtual organization and the characteristic of resource sharing scheme, which make impossible pre-configure resources in grid environment, therefore, the tasks of resource discovery mechanism are obtaining available resource and service information. The precondition of grid computing is discovering available resources actively, registering and managing the resources. Therefore, resource discovery is key part of running any grid system, providing the support of job scheduling, and the realization mode and mechanism affect the Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. International Conference On Advanced Infocomm Technology’08, Jul 29–31, 2008, Shenzhen, China. Copyright 2008 ACM 978-1-60558-088-3…$5.00.

Liu Mingxin Yanshan University Department of Communication Engineering, College of Information Science & Engineering, Yanshan Uni. Qinhungdao, 066004

[email protected] whole grid system [2]. In present, there are several popular projects that make mention of the resource discovery problem, such as MDS (Monitoring and Discovery Service)[3], Matchmaker [4], and UDDI of Web Services [5]. All of them are based on a centralized architecture. In practical application, this architecture exists several shortages. Firstly, central server in centralized architecture may be poor scalability and has a single point of failure. Secondly, resources on the grid have several dynamic attributes, and the centralized scheme will bring the performance bottleneck. A quality performance resource discovery mechanism should satisfy some basic characteristic: robustness, scalability, efficiency and practicality. P2P (Peer-to-Peer) is a kind of distributed technology of realizing resource sharing. It doesn’t distinguish between server and client, and all nodes are not only resource providers but also resource customers. P2P technology may adapt the dynamic, scalable and the large-scale development of grid, which it exists some advantages in resource discovery of grid system. In addition, the research of P2P field shows that clustering resource nodes with same or similar interesting loosely will improve the performance of resource discovery [6]. In this paper, it introduces P2P virtual community to design grid resource discovery mechanism. According to the small world property and power law property of P2P network, grid system is divided into P2PVC, resources in each P2PVC has the similar attributed by defining resource clustering. Referring to the needed resource type, the resource requirement enters into the relevant virtual community at the beginning, and then the request is forwarded among P2PVC until the desired resource is found. The goal of resource clustering is to decreases the scale of search and cuts down the probability of hotspot. The whole paper is organized as follows. Section 2 discusses the related work in this field. Section 3 some basic concepts of P2PVC are defined, and grid system based on P2P virtual community is designed. In section 4, resource clustering according to similarity measure method is proposed and the process of resource discovery is described. In section 5, the performance of resource discovery mechanism is analyzed and draws the conclusion.

2. RELATIVE WORK According to the option of organizing, discovering and managing resource, the model of resource discovery is divided into several types: centralized model, distributed model, hierarchy model and multi-agent model. The typical centralized models are MDS and Matchmaker, which rely on centralized protocols to

query directory servers to discover entities and to obtain resource descriptions from their information nodes. With the development of P2P technology, distributed model is paid more attention. P2P grid is a kind of distributed model, which usually deals with resource retrieval by using DHT (Distributed Hash Table) [7]. Taila [8] discuss P2P architecture for resource discovery that is consonant with OGSA (Open Grid Services Architecture) standard. A P2P layer is defined to support resource discovery across different Virtual Organizations (VOs) in a P2P fashion. Message is routed among Grid Services in P2P layer by an improving Gnutella protocol. N.A.Al-Dmour [9] presents two P2P protocols for resource discovery. The Query Resource Discovery Mechanism is used to find volunteers for running developer application in a meta-computing environment. The Seeking Resource Discovery Mechanism is more suitable for finding resources with static attributes. In addition, Zhang [10] researches the architecture and performance of topic-driven resource discovery, which selects optimal search hosts by introducing the index methods with the characteristic of each file. Zhu [11] introduces a method based on resources classification, however, this kind of mechanism does not pay more attention to the grid scale of adjusting dynamic. The solution of this paper divides grid into different virtual community, each virtual community has the similar attribute of interested resource and service based on the results of resource clustering, the goal is to provide a new method of improving scalability or reducing hops.

3. GRID SYSTEM BASED ON P2PVC In grid system based on P2PVC, each node connects other node in grid. All the nodes and their links construct virtual grid system on the physical network. Among nodes in virtual grid system may communicate and exchange messages. In this paper, it references some attributes of P2P networking and some concepts of colony to define logical structure of grid system based on small world property and power law property of P2P network.

3.1 Definition of grid system based on P2P virtual community People like gregarious in society according to the basic principle of sociology. Because people society and person behavior have the colony characteristic, the regions of society behavior and person behavior is relative settled [12]. Mapping the phenomena of sociology and psychology into grid system, it may describe users’ demand to grid resource is difference. Therefore, research and design of grid system may adopt the ideas, divide grid system into some P2P virtual community, and choose some nodes that are interested in some resources and application to compose a virtual community. Therefore, it defines grid system based on P2P virtual community is followed: Definition 1: Grid  {VC1 , VC N } , and VC1 , VC N is P2P virtual community; Definition

2:

VC i  {Node1 ,  Node m }

,

and

Node1 ,  Node m has similar resource or application demand; Definition 3: Nodei  ( Id i , Id ci ) , it describes that any node is composed of two parts, one is node identifier Id i , and another is virtual community identifier of node Id ci ;

Definition 4: Subjection function f. It describes the probability that the resource belongs to one of certain resource classes. Let there is a fuzzy class set A which is a certain in filed U . f A (u )

is a probability that u subjects to A , where u  U and f A (u )  [0,1] . It can be represented by a mapping relationship

f A : U  [0,1], u  f A (u ) . Subjection function describes nodes possess some resource or application degree, and classifying nodes and storing classified results into corresponding community, according to the value of subjection function. In a word, nodes choose corresponding VC according to subjection function, and VC is composes of similar function nodes. Nodes in VC have some attributes just like people in society. There must exist some homology nodes in different VCs, which connect community, exchange information and compose interlinked grid system. Therefore, P2PVC has some attributes as follows: Attribute 1: VCi , VC j , if VCi  VC j  Φ (i  j ) ，then VCs that composing grid system exist some relation. Attribute 2: VCi , VC j , if VCi  VC j ＝Φ (i  j ) ，then VCs that composing grid system is isolated.

3.2 Design of grid system based on P2PVC P2PVC composing grid system includes primary node, cache node and relation nodes. Pnode (Primary node) stores router information and resource information of all nodes in this community. Cnode (cache node) stores router information of using frequently nodes, and the goal is to improve on resource query speed. Rnodes (Relation node) are composed of nodes comes from different physical region, and same physical nodes exist in different VC. Therefore, grid system is designed based on P2PVC is as follows: (1) Initialize: setting the resource demand set, application demand set and the value range of function according to the history monitoring data; (2) Classify: computing subjection function value of resource demand and application demand, and classify nodes into the relevant VC according to the subjection function value; (3) Building router information of Pnode and Cnode; (4) Modifying Pnode according to nodes enter or leave dynamically; (5) Mapping virtual grid system into physical nodes. The process of design is shown in figure 1. In figure 1, grid system is composed of m P2PVC, and any VC of including i ( i  3 ) nodes exist the following information: one is Pnode， one is Cnode and ( i -2) Rnode.

and denominator describes product of resource vector module. 3 Co m

4.2 Resource discovery algorithm In section 4.1, it computes the vector similarity and forms resource clustering for every P2PVC. Now it designs the resource discovery algorithm based on the forming resource clustering. The algorithm is described as following:

P2PVC 3 C om

3C o m

Cnode

Rnode

Pnode

Mapping

/* Input: CRTi , Id ck , R k */ ( CRTi is resource clustering

Router

3 Co m

Same node in different P2PVC

sets) VC2

VC1

VC3

… … PC

PC

… …

… … PC

PC

PC

PC

… … PC

PC

Physics layer

/* Output: If success the return a peer virtual community contains the resource, otherwise return failed */

PC

Var CRTi , Tmax ; (Tmax is the max response time)

Figure 1 Design Process of P2PVC

Routing ( CRTi Id ck , R k )

4. RESOURCE CLUSTERING and RESOURCE DISCOVERY ALOGOTITHM In section 4, resource clustering according to similarity measure method is proposed and the process of resource discovery based on resource clustering is discussed.

Begin /* query node Id i in the Cache

Query the Cnode; nodes sets in P2PVC */

If Ri does not exist the Cnode then Id i query the CRTi

4.1 Presentation of users choose resource information

N=selectCRT( CRTi , Id ck ) If not isnull(N) then

Users choose resource information can be represented by matrix Am,n (m  n) , users are represented by m , and resource

Send (request)

information is represented by n . Therefore, any matrix element Ri , j represents that resource information j is chosen by user i .

If R k

The matrix which users choose resource information is shown in table 1.

Else

N Return (N) Pass request

Table 1 Users choose resource information matrix R U

Routing ( CRTi , Id ck , R k ) R1

…

Rj

…

Rn

U1

R1,1

…

R1,i

…

R1,n

…

…

…

…

…

…

Ui

Ri,j

End if Else Query Pnode End if

Ri,n

…

…

…

…

…

…

Um

Rm,1

…

Rm,j

…

Rm,n

End if If time> Tmax

In this paper, it adopts Cosine method to define the similarity of resource information Ri and R j , and forms the resource clustering by the value of similarity. Cosine is defined in formulation 1.

sim( Ri , R j )  cos( Ri , R j ) 

Ri  R j Ri  R j

(1)

Cosine method is described as following: users choose resource information is n dimension vector, if user does not choose correlative resource, then value in matrix is 0. The similarity is measured by vector cosine angle. Supposing resource information Ri , R j is chosen by users in the n dimension vector and represented vector Ri , R j . In formulation 1, molecular describes the vector inner product that user chooses,

Return null End In this paper, it generates the topology structure of grid system by NS in the experiment environment, and tests the relation between router retransmission times and the scale of P2PVC, which forms by adopting the method of resource clustering. The experiment result is shown in figure 2.

5. CONCLUSION In this paper, it provides the concept P2PVC for managing the grid resource, and discusses the attributes of P2PVC, then, it refers the ideas resource clustering based on similarity matrix to improving the efficiency of resource discovery. Finally, it verifies the results the resource discovery algorithm.

retransmission times

[4] Ludwig Simone A, Reyhani, S.M.S. Introduction of semantic matchmaking to Grid computing, Journal of Parallel and Distributed Computing, 2005,65(12):1533-1541

15 10

12

5

20

0

40 100

200

400

node number

Figure.2 The relation between retransmission times and node number

6. CONCLUSION In this paper, it provides the concept P2PVC for managing the grid resource, and discusses the attributes of P2PVC, then, it refers the ideas resource clustering based on similarity matrix to improving the efficiency of resource discovery. Finally, it verifies the results the resource discovery algorithm.

7. ACKNOWLEDGMENTS The research work is supported by the Natural Science Foundation of Hebei Province (Grant No.F2008000864); the Research and Development Program of Hebei Province (Grant No.062135127).

8. REFERENCE [1] Foster I. and Kesselman C. The grid: blueprint for a new computing infrastructure. Morgan Kaufmann, San Fransisco, CA,1999. [2] Li, Chunlin. Resource discovery and economic scheduling policy in computational grid. Journal of Wuhan University of Technology,2006,30(5): 763-766 [3] Globus.http://www.globus.org. 2004.

[5] Benson Edward, Wasson Glenn, Humphrey Marty. Evaluation of UDDI as a provider of resource discovery services for OGSA-based grids. The 20th International Parallel and Distributed Processing Symposium, 2006,163171 [6] Sripanidkulchai K., Maggs B., and Zhang H. Efficient content location using Interest-based locality in Peer-to-Peer systems. Proceeding of INFOCOM2003, San Francisco, 2003: 175-186 [7] Louati Wassef, Zeghlache Djamai. SPSD: A Scalable P2Pbased Service Discovery architecture. IEEE Wireless Communications and Networking Conference, 2007:25882593 [8] Talia D, Trunfio P. Toward a synergy between P2P and Grids. IEEE Internet Computing, 2003,l.7(6):94-96 [9] Al-Dmour N.A., and Teahan W.J. Peer-to-Peer protocols for resource discovery in the grid. Proceeding of the Parallel and Distributed Computing and Networks, Innsbruck, 2005:456461 [10] Zhang, Huaxiang, Huang, Shangteng. An incremental approach to link evaluation in topic-driven web resource discovery. The 1st of International Conference, 2005:301-310 [11] Cheng Z., Wei-ming Zh., Zhong L, Zhen-ning X. A Grid resource discovery scheme based on resource classification. Journal of Computer Research and Development, 2004,.41(12): 2156-2163 [12] Lu Qingling, Ceng Guangping, ZhangWei. Autonomous decentralized organization model and coordination control of softMan crowd. Control and Decision, 2006,21(1):56~60