Posted price model based on GRS and its optimization for improving grid resource sharing efficiency

Grid resource allocation and management is very complicated and difficult problem because the resources are distributed, heterogeneous in nature, owned by different individuals or organizations each having their own resource management policies and different access-and-cost models. Thus, some resource allocation and management models based on market, or economic models in the grid have been proposed such as commodity market, posted price, tenders and auctions, negotiation price model, contract agreement, model of auctioning, employing exchange model of bid [1‐3]. Generally, based on these models, resource consumers make use of GRBs (Grid Resource Broker) to submit applications of the resource consumption. GRBs meet the requirements of these resource consumers via grid middleware services. It is obvious that the process of the sharing will cost much time at negotiating about the usage duration or time, the usage fee, QoS and some other items about sharing access. On the other hand, it is also clear that these models are only beneficial to the grid consumer, who can finish their work at the lower cost.

In this paper, we try to solve the efficiency bottleneck of grid resource sharing, which is combined by 3 aspects: one is GRS, the second one is posted price model based on GRS, the third one is optimization based on MOGAP. We also try to be on behalf of GRM (Grid Resource Manager) and propose the idea of GRS to meet the service of grid resource sharing. Supermarket is welcomed by people and fits the habit of people’s consumption. Constructing GRS by GRS user agent and GRS resource agent, serving grid consumer via GRS user agent, organizing the grid resource from their owner and negotiating about the time, the price and the QoS of resource sharing, we get a new idea of GRAM (Grid resource allocation and management) based on economic model. One important thing is that all the negotiating interaction between the resource provider and the GRS resource agent is finished in background instead of foreground before the resource sharing. After construction of GRS, the grid resources consumer shares the resource just as in the posted price model. Of course, the GRS is always changing because grid is dynamic. Furthermore, GRS managers can profit from price difference between the cost and sale price of the GRS resource. Generalized Assignment Problem (GAP) is used to allot the resource in GRS to optimize the allocation of resource.

The paper is organized as follows. In Sect. 2, the related work are presented. Section 3 introduces the posted price model. Section 4 presents the idea of GRS and its construction. In Sect. 5, the GRS-based posted price model is defined. Section 6 discusses the optimization of allocation of resource. There are some examples in Sect. 7. Finally, conclusions and future work are outlined in the last Sect. 8.

Our work is based on GRS built in virtual organization (VO). Foster clarifies the concept about VO in [4]. VO is a set of individuals and institutions defined by uniform sharing rules.

Classifying based on the economic model, our work falls into the category of posted price model. Posted price model is similarly to the commodity market [5], except that special offers are advertised for notifying consumers discounted prices [6, 7]. One recent work about the commodity market is presented by Gunther Stuer etc., where in order to find price equilibria in commodity market, some refinements of Smale’s method application are proposed [8]. Some other related economic models are bargaining, tendering/contract-net, auction, bid-based, bartering, monopoly and oligopoly, and other various forms.

In bargaining, providers and consumers negotiate each other. Providers commonly want to get higher prices but consumers want to get lower prices. This negotiation continues until both providers and consumers all agree a same price which is acceptable to them. When the price is difficult to define, bargaining is a well economic model to achieve a acceptable price [9]. Tendering /contract-net allows a customer announces requirements to potential producers for looking for the desirable provider [10]. Auction allows consumers to submit bids through an auctioneer until a single clearing price appears, this price is higher than the price other customers can accept [11]. A typical bid-based is the resources assigned are in direct proportion to the bids of the consumers [12]. Bartering supports sharing each others’ resources between providers and consumers, if consumers are also providers and thus both contribute and use resources [13]. Monopoly/oligopoly is non-competitive. There are only a single or a number of providers determines the price [14].

In the commodity market model, resource providers specify their service price and charge users according the amount of resource they consume. A provider uses a brokering system where each request is distributed until the accumulated brokerage cost is limited by the budget of the user [5]. The pricing policy can be derived from various parameters and can be flat or variable depending on the resource supply and demand. In general, services are priced in such a way that supply and demand equilibrium is maintained. Logic structure of commodity model is just shown in Fig. 1.

Some in-depth works on posted price model are presented in [15‐17]. Anastasiadi etc. present three routing algorithms which are related with expected completion time and required network bandwidth [28]. Based on it, they investigate the load balancing economy occasions in which providers can advertise prices and transaction requests at a bulletin board [15]. Ferguson etc. investigate the load balancing economy occasions in which First-price and Dutch auctions enable each provider to host its independent auction, and enable users to decide which auction they should participate according to last prices advertised in bulletin boards [16]. In [17], when advertising resource request and prices on a bulletin board, currency flow is used to restrict resource usage in order to control potential intrusion attacks and minimize the damages.

Posted price model is related on the commodity market model [1‐3]. Two key players driving the grid marketplace are GSPs (Grid Service Providers) and GRBs (Grid Resource Brokers). The posted price model is similar to the commodity market model except that it advertises special offers in order to attract (new) consumers to establish market share or motivate users to consider using cheaper slots. Logic structure of posted price model is given in Fig. 2. In this case, brokers need not negotiate directly with GSPs for flat fee, usage duration or time, QoS etc., but use posted prices as they are generally cheaper compared to regular prices. The posted-price offers will have usage conditions, but they might be attractive for some users.

In Figs. 1, 2, consumers interact with their own brokers for managing and scheduling their computations on the grid. The GSPs make their resource grid enabled by running software systems along with GTS (Grid Trading Services), which enables resource trading and execution of consumer requests directly through GRBs. The interaction between GRBs and GSPs during resource trading is mediated through a GMD (Grid Market Directory). They use various economy models or interaction protocol for deciding service access price. As there are much grid resource user and a great deal of resources in grid environment even in a VO (Virtual Organization), time and efficiency will be their problems.

Some researchers have focused on the job scheduling part of a grid management infrastructure [18]. They either proposed a framework for price-based resource allocation and resources pricing algorithm to achieve maximized utilization of grid resources [19], or formalized the resource allocation problem for Service Level Agreement (SLA)-constrained grid applications [20].

The GRS is a virtual, logic entity. It consists of information of a great deal of GSPs (Grid Service providers) and grid resources including traditional resources: computer, network, storage system, and highly generic sense resources that means any capability that may be shared and exploited in a networked environment: database, data transfer, simulation [21]. Obviously, the principle of constructing GRS is to serve the grid users whether they are grid resource providers or consumers, and make the managers of GRS get more profits. In other words, GRS gets the permission of grid resource from the providers or owners of resource in lower price and sell it at higher price to the grid consumers. GRS resource agent and GRS user agent play an important role in GRS management. The model of constructing GRS is as Fig. 3. GRS resource agents take charge of collecting the information of grid resource that can be shared by any others, negotiating about the price and the other items with the resource provider. GRS user agents take charge of responding the grid consumers and leading to the consumers sharing the resources in two modes that we will introduce at the next paragraph.

The grid consumer GRS is built in a VO (Virtual Organization) [22]. Of course, there maybe server GRS in some VO. GRS is a dynamic virtual entity while the resource in it can login or logout dynamic.

For ease of understanding, let’s firstly introduce the concept about VO (Virtual Organization). In grid environment, sharing resource coordinately and solving problems in VO mode are two key functions which should be provided. VO is a set of individuals and institutions defined by uniform sharing rules. This sharing is, necessarily, highly controlled, with resource providers and consumers defining clearly and carefully just what is shared, who is allowed to share, and the conditions under which sharing occurs [4]. Most solving and brokering strategies in grid environment are closely related with this sharing.

The pricing strategy of GRS is a key problem for their manager. It includes two parts in this paper. One is posted price based GRS model. The other is grid resource optimization based Assignment Problem (AP).

In the posted price model based on GRS, price is negotiated back the stage by GRS resource agent and grid resource provider. Of course, it is different from the model of posted price which the price is negotiated on the stage.

This is a simplified resource mode based on economy. In this model, grid resource consumers share the GRS resource at posted price. It would not spend time to negotiating about the time, the price, the QoS etc. each other. The manager of GRS gains the profits by serving the grid resource provider and grid resource consumer. The grid resource consumers share the resource at posted price according to their plans and pocketbooks. The grid resource provider gains his income for his resource being shared. The description of this mode is as follows. We might as well suppose that our GRS has n pieces of resources, each resource has his ID, resource name, bank account of owner, access time for sharing, resource amount, price etc., which can be formalized as GRS−R _i =(R _i -ID,R _i -name,R _i -account,time,amount,R _i-price-in ,…,R _i -IP) i=1,2,…,n. We also might as well suppose that GRS-Ri is shared by some grid consumers. The homologous item’s formula is \(\mathit{Sell}\mbox{-}\mathit{R_{i}} =( R_{i}\mbox{-}\mathit{ID}, R_{i}\mbox{-}\mathit{name}, R_{i}\mbox{-}\mathit{account}, \mathit{time}, \mathit{amount}, R_{i\mbox{\scriptsize-}\mathit{price}\mbox{\scriptsize-}\mathit{out}}, \dots,R_{i}\mbox{-}\mathit{IP} )~i=1,2, \dots,n\). Therefore, the manager of GRS gains the profits according to the followings:

In general, R _i-price-in is bigger than R _i-price-out , thus the manager of GRS can get profits.

There are obvious differences between conventional posted price model and GRS-based posted price model. The main difference is that, all the details about resource sharing such as cost fee, usage duration or time, QoS and other items in our approach are negotiated about while the GRS is constructed. That means a foreground task is changed into background task, and an instant task is changed into preparatory one. Time for negotiating is not necessary any more. It is just the advantage of our approach.

The scheme includes two parts. One is the posted price model based on GRS. The other is grid resource optimization based on GAP (Generalized Assignment Problem) in order to maximize the profits for the GRS manager, which will be presented in this section.

The GRS-based posted price model is fit to the sporadic grid consumers. For the group consumers, a optimized approach is proposed as follows.

Generally, assignment problem can be defined as: There are n persons and n pieces of jobs. Any person can be assigned to perform any job, incurring profits that may vary depending on the person-job assignment. If person j finished the job i by efficiency e _ij , it is required to perform all tasks by assigning exactly one person to each job in such a way that the total profits of the assignment is maximized. Furthermore, if there are m persons and n pieces of jobs, and m≥n, which means some job can be done by more than one person. The problem is changed into GAP (General Assignment Problem) [22, 23]. Obviously, the two cases are single object and not adapt to allocation of GRS. Thus, for making it fit to our problems, we need to reconstruct GAP and change it into multi-object GAP. The problems are merely divided into the following two cases [24].

Case 1 There are n pieces of resources and m jobs (m≥n). It is required to perform all jobs by assigning one piece of resource to b _j (b _j ≥1 one or more than one) job(s) in such a way that the total profits of the assignment is maximized. Here b _j is an unknown number, and We might as well suppose that allocation should think about p factor such as router, bandwidth, price, etc. Assume factor k (k=1,2,…,p) that resource j arranged to job i can make GRS economy efficiency e _ij (i=1,2,…,m;j=1,2,…,n), the problem is how to allocate the assignment and make the manager of GRS get the maximum profits.

Model 1 & Model 2 is a general model of allocation of GRS. The solution of these two models has been finished. According to the procedure of multi-object GAP1& multi-object GAP2 [23, 24], we can make a program to simulate test with C++. We give three examples to show the feasibility of our scheme.