A self-adaptive Model based on Multi-Objective Programming for Grid Resource Management

Abstract:Abstract :The growing computational power requirements of grand challenge applications have positioned computational grid as promising next generation computing platform. However， resource management and application with varied requirements in grid environment continue to be a complex undertaking. In order to address complex resource management issues， we provide a self-adaptive model， which is based on multi-objective programming. The model make use of virtues of market mechanism efficiently， meanwhile， the shortcomings of market mechanism， such as too frequent fluctuations of price， are avoided by means of the method of changing prices after trading. Through using atom allocation of resource group， the cooperating allocation is improved， and some problems， such as deadlock of resource and inefficiently occupying resource， are solved. What’s more important， efficiently using various resources in grid system is guaranteed through importing multi-objective programming mechanism in our resource management solution. A frame of resource allocation is given at first， then， the mathematical model of the method is constructed. An algorithm is proposed to get the approximate solution in this paper.

Keywords: grid， self-adaptive， market mechanism， resource allocation

1Introduction

Computational grids comprise heterogeneous resources， policies and applications with varied requirements. Due to the complexity in constructing successful grid environments， it is impossible to define an acceptable system-wide performance matrix and common fabric management policy. Through using the virtues of market mechanisms， such as the lever of price， a method of self-adaptive resource managing is provided in this paper， which can solve the difficulties exists in resource allocation like resource autonomy of resource owner， distribution and parallel of decision-making of resource allocation as well. The idea of applying economics to resource management in grid has been explored in previous research [1][3][5] [7] to help understand the potential benefits of market-based systems. Unfortunately， most of them were implemented followed a monolithic architecture， which means they are hard to extend.

A method of changing price after trading is presented in this paper， which can be better seasoned with the uncertain market environment of supply and demand of resource. At the same time， it can alleviate the user’s burden made by too many consultations within one trade. Further， to address the issue of inefficiently resource occupying or resource applying deadlock， we provide a method of atomic resource allocation， which means to allocate all the resources a procedure need or none at one time. The rest of this paper explores the use of economic paradigm for resource managing with particular emphasis on providing the algorithm and its test that support dynamic and self-adaptive schedule.

2Architecture design

The framework of our grid resource management model is composed of four layers: user layer， application proxy layer， resource proxy layer and resource layer， shown in Fig.1. Among the four layers， application proxy layer and resource proxy layer will be stated in more detail.

2.1 application proxy layer

The main role of application proxy layer is to shield the differences of varied grid applications. The application proxy module has two main functions described as follows：

⑴ To deal with the abstract resource descriptions come from users， which is related to the problems of corresponding application field. The practical method adapted in this paper is to translate them into concrete resource description， which can be understood by corresponding resource proxies. Let’s take medicine molecule design as example. User provide standard description of an application as follows:

(num， para1，par2，…)

Where， num is the sequence number of medicine molecule design problem and parai (i=1，2， …) means the parameters needed by the problem. For example， the problem of resource distribution is: a ST molecule (protein molecule) and 2000 PT molecules (little molecules).

(1， “ 202.117.165.39\\information-database\\ ST.dat ”，7， “202.117.165.39\\information-database\\pt.dat”， [1，2000 ] )

The application broker translates the user-level description into concrete resource description， which can be translated into 2000 resource units as follows:

ω* resource(St_standard，Pt_average)

where，ω is a parameter presented by experts. It is used to illustrate the complex degree compared with standard protein molecule. St_standard is a standard protein molecule; Pt_average is a little molecule with average complex degree. The result of resource(St_standard，Pt_average) is a resource unit， which is needed by the matching process of St_standard and Pt_average. Fig 2(a) is standard resource unit and Fig2(b) is resource unit for a certain ST’ matching who’sωis 1.2.

⑵The second function of application proxy module is to check GIS(Grid Information Service) in the same domain for nodes， which can satisfy the constrains. Next， use API to send these resource requirements to the nodes， respectively.

2.2 Resource proxy layer

Similarly， resource proxy layer has two functions too. One is to shield the differences of kinds of resources. The other is to optimize resource allocation using price levers of market mechanism and atomic resource allocation.

According the theory of bucket， the number of resource units required should be decided by the relatively less resource. The available resource information of a certain node is shown in Fig.3.

Compared the kinds of values in Fig 2(b) and Fig.3， we can get their multiples， respectively. We can see easily that the multiple of Memory- Ram-freeMB is the least， 8， so 8 resource units can be allocated to execute matches between one ST molecule and eight PT molecules.

3Theory of DSRA Algorithm

Using price levers to express the relationship of supply and demand of resource， four main aspects character are as follows: First， making good use of kinds of resources; Second， taking both customer’s benefit and producer’s into account by adjusting prices; Third， avoiding to enhance the burden of user due to too much fluctuation of price; Four， improving the whole efficiency of implementation through avoiding inefficient resource occupancy or resource applying deadlock.

The self-adaptive mode of grid resource allocation is as follows：A={a1，a2，…，an}T is an n-dimensional resource requirement for application proxy；R={r1，r2，…，rm} T is a resource vector with m-dimension；C={c1，c2，…，cm} T is a resource capability vector；P={p1，p2，…，pm} T is a resource current price vector；B={b1，b2，…，bm} T is a resource cost vector.

The feasible solutions set can be written as follows: S={X ，pj | 0≤xij≤cj ，0≤∑xij≤cj，pj≥ bj }

The best solution of resource allocation has characters as follows:

⑴ The maximal benefit for the owner of resource：

⑵ The maximal satisfaction for users， which can be expressed by the following two points：

① The maximal quantity applied and received by user：，

② The minimum cost for users：.

To each rj from R={r1，r2，…，rm}， its best solution can be defined as:

s.t.…⑴

Definition 1: Suppose that X*， p*j∈S={X， pj | 0≤xij≤cj，0≤≤cj，pj≥bj， i=1，2，…，n}.If to X， pj∈S，there is fq(X*， p*j)≥fq(X， pj) (q=1，2，3)， then ( X*， p*j) is called absolutely optimal solution of formula (1).

We can see easily that the absolutely optimal solution of formula (1) is generally inexistent， so we turn to look for it’s non-inferior solution. Before we give the definition of non-inferior solution， a lemma has to be presented as follows:

Lemma: Given， toF(X， pj)={f1(X， pj)，f2(X， pj)，…，fq(X， pj)} and( X， pj) = {( X， pj)，( X， pj)， …，( X， pj)}，where F(X， pj)，( X， pj)∈Eq， if all fj(X， pj)≥( X， pj)，and j0(1≤j0≤q) makes fj0(X， pj)>( X， pj)，then F(X， pj) ≥ ( X， pj)，simply note F≥ 。

Definition2: Suppose that to X*， pj*∈R，ifX， pj∈R，which can make F(X， pj) ≥F(X*， p*j )，then we call (X*， p*j) Pareto solution or non-inferior solution.

Definition3：Suppose that X*， p*j∈R， ifX， pj∈R，which can satisfy F(X， pj) > F(X*， p*j)，then we call (X*， p*j) weak Pareto solution or weak non-inferior solution.

In practice， problem ⑴ can be transformed into a single-objective problem as follows:

Max F=α( (∑xij)×(pj/p0))+β(∑xij)﹣γ((∑xij)×(pj/p0 ))，

= (∑xij)×( (α×(pj/p0)+ β-γ×(pj/p0 ) ) =(∑xij)×(β-（γ-α）×(pj/p0))s.t.

…⑵

In the equation ⑵， α means the importance of resource owner’s benefit; β means the the importance of resource quantity acquired by user; γ means the importance of user’s benefit. The meaning of equation ⑵ is illustrated as follows：

⑴ if γ>α， then ，when pj is decreased ， the value of F increase. That is to say， when the user’s benefit is more important than the resource owner’s， the price pj should be decreased；

⑵ if γ<α， then ，when pj is increased ， the value of F increase. That is to say， when the resource owner’s benefit is more important than the user’s， the price pj should be increased；

⑶ if γ=α，the change of pj doesn’t effect the value of F， so pj keeps the old value；

⑷ when β is increased ， the value of F increase; when β is decreased ， the value of F decrease too. That is to say， the requirement of resource quantity is the drive of obtaining the best benefit of the whole resource management.

4Iterative algorithm of resource proxy

The question described by ⑵ belongs to non-linear questions， which are， as we all know， very difficult to be solved directly. We present an algorithm of approximate solution on the base of theory of ⑵ to alleviate the complex. It is described as follows：

rj from R={r1，…，rm}

Initialization：α、β、γ，pj，bj，μ；

step 1 listen()；

step 2 accept(queue)；

step 3 if （pj>bj）then { pj = pj+ δ（α，β，γ）；send(pj) to GIS；}

step 4 while (∑xij >cj ) {for all ai∈Ajxij=xij -μ×(xij-xij1)；}

step 5 distribute(xij)；

step 6 adjust(α，β，γ)； gotostep 2。

The change of supply and demand of resource can be reflected by adjusting α，β，γ.

5DSRA Algorithm test

In order to evaluate the efficiency of this algorithm， we developed a simulator. On the assumption that rj indicates resource of bandwidth and its cj is 100(Mbps)， the related functions are defined as follows:

δ（α，β，γ）: (（α-γ）×β)× p0；

adjust (α，β，γ)：

{ if ((queue(∑xij)> cj ) (0≤α，β≤0.95 0≤γ≤1))

{α=α+0.05；β=β+0.05；γ=γ-0.1；}

elseif ((queue(∑xij) < cj/2)

(0≤α，β≤1 0≤γ≤0.9))

{α=α-0.05；β=β-0.05；γ=γ+0.1；}

else{α=1/3；β=1/3；γ=1/3；} }

Initialize：α=β=γ=1/3，pj=1 yuan，bj=0.2 yuan，μ=0.1；

Table item illustration：aj(xij，xij1)

6conclusion and future work

In this paper， a self-adaptive method of grid resource management is presented to solve kinds of problems related to grid dynamic environment. At the beginning of this paper， a frame of resource management is presented， then， the market model of resource allocation is described concretely. Next is the mathematical model of DRSA， which is explained with multi-object optimization. In order to verify its practicability， an algorithm and its instance are presented in the section 4 and section 5. A method， changing price after trading， is provided to avoid too much fluctuation. At the same time resource unit allocation assure the efficiency of resource using and avoid the deadlock of resource.

Several future directions are identified: enhancing the robust of the algorithm; introducing macro control into resource management and optimizing resource allocation from local to all areas. Through the above measures， we can get better solution in the future.

References

[1]B.Chun and D.Culler，Market-based proportional resource sharing for clusters， Technical Report CSD-1092， University of California， Berkeley， USA， January 2000.

[2]Rajkumar Buyya，Economic-based Distributed Resource Management and Scheduling for Grid Coputing B.E.(Mysore Univ.) and M.E.(Bangalore Univ.) http://www.buyya.com

[3]Y.Amir，B.Awerbuch.， A.Barak A.，S. Borgstrom， and A. Keren， An Opportunity Cost Approach for Job Assignment in a Scalable Computing Cluster， IEEE Transactions on Parallel and Distributed Systems， Vol.11， No. 7， pp. 760-768， IEEE CS Press， USA， july 2000.

[4]ZhangJinshui， Mathematical Economics- principle and practice. Beijing: Tsinghua University press， 1998

[5]D.Reed， I.Pratt， P. Menage， S. Early， and N.Stratford， Xenoservers; Accounted execution of untrusted code， Proceedings of the 7th Workshop on Hot Topics in Operating Systems (HotOS-VII)， Rio Rico， Arizona， USA， March 28-30， 1999， IEEE CS Press， USA， 1999.

[6]CAO Hong-Qiang， A Market-Based Approach to allocate resources for Computational Grids， journal of computer research development Vol.39， No.8 Aug， 2002 P13-916

[7]N. Nisan， S. London， O. Regev， and N. Camiel， Globally Distributed computation over the Internet: The POPCORN project， International Conference on Distribued Computing Systems (ICDCS’98)， May 26-29， 1998， Amsterdam， The Netherlands， IEEE CS Press， USA， 1998.