Online auction-based resource scheduling in grid computing networks

Abstract

The aim of this article is to introduce a novel auction-based algorithm for grid computing wireless networks and resolve some incompetence with dynamic mechanisms. We develop a reverse online auction method to allocate grid resources, where the grid resource providers arrive dynamically and user broker has to make a multi-attribute decision whether to sell tasks or not before the end of current round. In our approach, a trade-some-with-forecast algorithm is proposed to help the user broker to utilize his forecast ability to allocate the grid resource in an online setting. Furthermore, two reverse online auction-based protocols are presented to demonstrate the resource scheduling in grid computing wireless networks. Experiments show that the reverse online auction-based with forecast protocol has better performance in comparison with the reverse online auction-based protocol. It is efficient in terms of auction stages, user satisfaction, and successful forecast.

Keywords

Protocol multi-attribute auction satisfaction degree

Introduction

Grid computing wireless networks have already been seen as an ultimate important computing platform for solving large-scale problems in the fields of science and engineering. The grid computing refers to create the coordination of multiple, unutilized, or underutilized computing resources into a single virtual computing resource pool, where resource providers and users can trade off smoothly. The main aim of grid computing is to deliver computing resources such as central processing unit, cycles and storage (CPU) cycles and storage as utilities from resource providers to users.¹ Hence, building an optimal grid resource allocation protocol or mechanism is a major problem for the grid computing among these participants. In recent years, the usage of auction-based methods for grid computing has attracted much attention. It requires less global information, provides an incentive for resource providers to participate in the grid computing networks and motivates the users to trade off among deadline, budget, and the required level of service quality.²

For the grid computing problem, many types of auctions have been considered and elegant auction theories have evolved. English auction, Dutch auction, first-price sealed auction, second-price sealed auction, and double auction are broadly adopted. From an economic perspective, a key feature of these auctions is the presence of participant’s equilibrium strategies under the different auction rules. Nevertheless, a great deal of research concerning these auctions is usually based on a traditional assumption that the grid resource providers (GRPs) must receive all the bids before determining the allocation. Namely, the assumption implicitly assumes that all participants, that is, GRPs, user broker (UB), and grid resource users (GRUs), are willing to wait for some amount of time (until all bids are gathered) before performing any trade. In reality, at any moment, different GRPs with grid resources are often added to or removed from the grid computing networks. On the other hand, different GRUs with varying requirements can enter the networks freely. As a result, the grid environment is highly dynamic and uncontrollable, where resources are distributed across different administrative domains.³ However, the traditional auction protocols in grid computing networks ignore these complex and dynamic factors. It is necessary for GRPs, UB, and GRUs to adjust their winner determining and bidding behaviors dynamically according to the more realistically trading market situation. How to develop an effective auction protocol or mechanism adaptive to the complex and dynamic grid computing networks is one of the hot issues in recent years.

According to complex and dynamic characters in grid computing networks, we propose a reverse auction-based allocation mechanism, that is, reverse online auction-based with forecast (ROAWF) protocol, targeting on the effective grid resource allocation. It is based on a reverse online auction where the different GRPs arrive at different times and the GRUs or UB are required to make decisions about each bid as it is received. To be specific, an online algorithm named trade-some-with-forecast (TSWF) algorithm in ROAWF protocol is presented to solve the winner determination problem for dynamic grid computing, which is an online optimization problem to maximize the GRUs’ utility. To evaluate the performance of TSWF algorithm without knowing the future bidding sequences, we are motivated to use the competitive ratio to evaluate performance,⁴ where the performance of an online algorithm is compared to the performance of an optimal offline algorithm that knows the future.

Some interesting results are achieved and the major contributions are as follows: (1) we present a reverse online auction model to extend the traditional auction in an online setting. It can help the GRUs making decision without knowing the GRPs’ bidding sequences. (2) Based on the online auction model, the TSWF algorithm is presented, which extends the classical competitive analysis to allow the GRU having forecast ability. The less competitive ratio is proved that the TSWF algorithm has a better performance, showing that it is particularly well suited to the dynamic market for grid computing networks. (3) The multi-attribute feature is introduced into model to demonstrate the real grid computing networks better than traditional price only. The advantage is to help the GRUs having multiple attributes decision making in an auction market.

The rest of this article is organized as follows. In section “Related work,” we investigate the related work. In section “Problem formulation,” we formulate the problem and present detailed auction process of the reverse online auction mechanism. Section “Reverse online auction model and algorithms” shows the reverse online auction model and the TSWF algorithm. In section “Reverse online auction-based protocols,” two reverse online auction-based protocols are introduced. In section “Simulation and evaluation,” these two proposed protocols are extensively evaluated by experimental studies, and finally, section “Conclusion” concludes this work.

Related work

At present, grid computing based on economic models has been extensively investigated by researchers. In general, various economic models, ranging from commodity market to auction market, can be adopted for grid resource trading in grid computing networks.¹ However, because of the peculiar nature of grid resources, auctions are the most suitable paradigm. This vein is usually divided into two categories.

One is in the complete information environment where the final winner determination is made after receiving all bids. The most famous auction form is English auction, in which GRUs are free to increase their bids exceeding others for the grid resource that they are competing for. When no bidder is willing to increase their bids any more, the auction ends and the UB announces the last highest bid and determines the final winner. In the market, the English model is found to be suitable for increasing revenue by selecting the highest bidder. However, English auction, in a distributed grid resource environment, may produce network congestion due to its high communication demand. In nature, English auction is an iterative model and may cause too many messages to be exchanged during the auction process.⁵ Hence, some other auction forms are studied and presented, for example, Dutch auction, first-price sealed auction, second-price sealed auction, and double auction. A multi-unit combinatorial auction-based grid resource co-allocation approach was proposed in Schnizler et al.⁶ The mechanism is evaluated according to its economic and computational performance as well as its practical applicability by means of a simulation. Mirzayi and Khayyambashi⁷ modified the bidding stage using signcryption model. The results show that the new model has a good behavior in grid environment. The security and fairness increase in auction model with this method. In Sun et al.,⁸ an infinite horizon alternative-move model of the unique second-price sealed auction was developed to guarantee higher task’s victorious probabilities. Using the proposed model, the author explained two distinguishable bidding patterns called bidding war cycle and stable bid. Two types of hybrid genetic algorithms were proposed to improve the efficiency of genetic algorithm for solving the winner determination problem.⁹ They declared that the proposed algorithms had good efficiency and led to better answers. Recently, the double auction was developed to try to have the advantages of both the continuous double auction and the batch auction. Izakian et al.² developed an agent-oriented double auction model and proved that the model was good in maximizing profit for providers. A new imprecise computation (IC) application model was provided for flexible reward-based grid resource management in Kim.¹⁰ An application in the proposed model consists of multiple independent jobs, in which each job has two parts: mandatory part for the minimum quality and optional part for additional computations. This application model can be applied to quality-related grid applications and used in adaptive resource management.

The other is in the incomplete information environment where the GRPs or users’ decision making are affected by the dynamic situations, for example, emergency, hierarchy, future market, and bid sequences. In Huedo et al.,¹¹ the recursive architecture was provided to allow an arbitrary number of levels in the hierarchy. The grid resources can be arranged in different ways while hiding the access details, for example, following organizational boundaries or aggregating them by similarity. Furthermore, the hybrid market approach was given in which a low-latency spot market coexisted with a higher latency future market.¹² Based on simulated market scenarios, they showed how this combination could significantly increase the total value realized by the grid infrastructure. In Cai et al.,³ a linear approximation was used to analyze the network flow equations. They applied linear programming techniques that optimized the dispatching of generators and loaded in order to eliminate the network overloads associated with a damaged system. In Ding et al.,¹³ the authors proposed an online auction method to allocate grid resource, where the resource providers arrived dynamically and resource user had to make a multi-attribute decision whether to sell jobs or not before the end of current round. A trade-some-if-beneficial (TSIB) algorithm is designed to help resource users determine the final winners with incomplete information. This form of reverse auction is generally called online mechanism, and the GRUs are called the online buyer, originally described by Lavi and Nisan.⁴ They attempted to design truthful competitive mechanisms for the online limited-supply auction, in which selling goods to the current bidder meant it couldn’t be sold to a future bidder. The article shows that non-decreasing bid sequences can help online auction mechanisms to balance the revenue gained with lost potential revenue. They used the well-established technique of competitive analysis to evaluate online mechanisms. The main attraction in using this technique is that there is no need to reply on statistical model for possible price inputs and utilize the competitive ratio to measure performance of online algorithm designed by online seller (this is forward auction). Intuitively, the idea is to compare the profit obtained by an online algorithm with the profit obtained by an adversary who has known all future prices in advance. The author extended the work by considering the same auctions in an online setting and presented randomized auction strategies. Some explicit solutions were provided to some optimization problems for sellers.¹⁴ They observed some key differences between their models and Lavi and Nisan’s model. In Blum et al.,¹⁵ online learning algorithm was applied to online auctions and achieved a constant competitive ratio with respect to the optimal expected price revenue. They examined an online auction where the goal was to bridge the gap between truth-telling mechanism and online optimization problem. A schema was also proposed for converting a given limited-supply auction into an unlimited-supply auction. Goldberg et al.¹⁶ introduced competitive analysis to analyze a class of single-round, sealed-bid auctions in unlimited supply, which could achieve an upper bound of 4 and a lower bound of 2.42 on the competitive ratio. The following literature has achieved some better algorithmic designs for the online auction, but they neglected the importance of incentive compatible of their mechanisms. Buchbinder et al.¹⁷ designed a (1 − 1/e)-competitive (optimal) algorithm for the online ad-auction based on a clean primal-dual approach, which is useful for analyzing the other online problems such as ski rental and transmission control protocol (TCP)-acknowledgment problem. A generalized secretary algorithm framework was presented by Babaioff et al.¹⁸ for online auctions. They pointed out that the secretary framework is different from traditional online algorithms. It assumes that the bidders arrive in a uniformly random order. Chakraborty and Devanur¹⁹ gave a reduction from the online auction problem to the allocation problem when the bidders want multiple copies of items with decreasing marginal utilities for them.

However, most of the studies rarely take forecast behaviors of GRUs into account and lack the corresponding performance evaluation. In addition, they also rarely take the comprehensive aspects from multiple attributes decision making into consideration. In our opinion, the allocation mechanism should be efficient to auction market and be convenient to the buyer and seller. So, we propose multi-attribute reverse online auction, in which the GRUs’ forecast is introduced to improve the efficiency of reverse auction and multiple attributes are added to describe the GRUs’ satisfaction. Competitive analysis method is applied to evaluate the performance of TSWF algorithm, and then, the article uses the improved TSWF algorithm to find the optimal resource allocation solution based on the three criteria.

Problem formulation

This section gives a general overview of the resource scheduling in grid computing networks. There are three participants, that is, GRUs, GRPs, and UB. In Figure 1, we present the scheduling scheme based on the reverse online auction. A more detailed description of scheduling scheme is given as follows. The GRUs require some jobs and ask UB to be a broker. The UB presents a document about auction market description (e.g. starting price, type, mount, announcement date, and expired date). Furthermore, the qualified GRPs come into the auction market and put their bids on an auction server. The auction is conducted as a series of bidding rounds. Let n denote the auction stages. At each stage, there is only one GRP coming. Each GRP has private information about multiple attributes of jobs. The GRPs learn this information at a certain time and must make a bid at that time. The UB designs the auction mechanism to decide how many tasks are allocated, while the multi-attribute bid is received or before seeing future bids.

Figure 1.

Scheduling scheme in the proposed framework dimensions.

UB

The UB helps GRUs decide auction discovery, auction analysis, and selection. Specifically, it sends user jobs to auction market, collects the results, and allocates the job in a reverse auction mechanism. First, it is in charge of dividing the job into a number of tasks and demonstrates the characters of job in such a way that multiple attribute constraints are satisfied. After the GRPs take bids, the UB is responsible for determining job sequencing, local resource allocation, and data transfer scheduling. In general, on receipt of a job request, the UB interrogates GRPs to ascertain whether the task can be executed on the available resources and meet the user-specified requirements. At each stage, the bid request is either rejected or passed to a scheduler according to the reverse online auction algorithm. The choice of specific reverse online auction algorithm defines a particular grid resource management system.

GRPs

Since we discuss the reverse online auction mechanism, the GRUs are auctioneers and GRPs are bidders. After receiving the invitation from the UB, the GRPs have to decide whether to participate in the auction. In this article, it assumes that there are many GRPs who would like to engage in the auction because the per-unit reservation prices of jobs are not greater than the minimal market prices. At each stage, the GRPs arrive dynamically and take their multi-attribute bids, which are their own private information. Namely, it assumes that at each stage the ith GRP presents his bid characterized by three-tuple $B_{i} = (p_{i}, v_{i}, s_{i})$ , where $p_{i}$ stands for the price for providing a service, $v_{i}$ is the computational speed of resource and is expressed in form of grid units per million instructions per second (MIPS), and $s_{i}$ is the memory size of resource. In this article, we allow GRPs to declare untruthful types. The cost of executing job must not exceed its allocated budget.

GRUs

The GRUs submit their jobs from any one of a number of entry points. Specifically, the GRUs submit a job, which consists of Q tasks in the grid resource allocation Internet. And the job request can be characterized by $JR = (J, T, JN, K, RP)$ , in which J is the computational workload requested, T represents the deadline of the job, JN is the number of tasks, and K represents the other resource attributes required by job except for price, such as CPU speed, memory size, and operating system. Also, the GRUs have a secret reservation price RP. These parameters are exogenously set and announced by the UB to the GRPs and GRUs. Here, $JN > 1$ is an important parameter in the reverse online auction market. It assumes that the job is not a single serial task and it can be divided into many tasks. This increases competition and revenue among the GRPs and GRUs. For example, when the job is the parameter about sweep job or a batch job composed of numerous independent tasks, many GRPs are needed to work together to finish the job in time. In this case, we assume that jobs are assumed to be independent and associated with distinct GRPs (bidders). In Bapna et al.,¹ the authors considered GRPs as price takers. That is, the GRPs in their model cannot differentiate their service from those of other providers through quality or other features and therefore cannot charge quality-based premiums. However, our article extends this assumption. The reason is that in the realistic grid computing Internets, there are many resources types including computer system, network subsystem, file system, and database system. Each resource type is associated with one or more attributes with specific values. Hence, the price is not the only factor to influence users and providers’ decision. The GRPs can utilize quality or other elements to influence the final selling price. Three attributes of grid resources, that is, price, memory, and speed, are considered in this article. For simplicity, we assume that there are three attributes, that is, the price $p_{i}$ , the speed $v_{i}$ , and the memory $s_{i}$ of the service. Different from Bapna et al.,¹ we introduce the satisfaction degree into the traditional value function for UB to decide the final winners. Thus, the satisfaction degree function $u_{i}$ of the ith GRP is obtained as follows

u_{i} = w_{1} \frac{R P - p_{i}}{R P} + w_{2} \frac{T - \frac{J}{v_{i}}}{T} + w_{3} \frac{s_{i} - S}{s_{i}}

(1)

where $w_{1}$ , $w_{2}$ , and $w_{3}$ are the weights of each attribute, and S is the minimum memory of service. It also assumes that $\underline{u} \leq u_{i} \leq \bar{u}$ , where $\underline{u}$ is the lower bound and $\bar{u}$ is the upper bound.

Reverse online auction model and algorithms

As mentioned in the previous section, the object of GRUs is to execute jobs within their corresponding deadlines and with the maximum satisfaction. Also the allocated budget for each job determines the maximum cost that a GRP is willing to pay for executing it. On the other hand, the GRPs aim at obtaining more profit. For this purpose, they try to take a multi-attribute bid at higher satisfaction degree and compete with each other for accepting more jobs. In this article, we propose an online algorithm for determining the winners by UB to achieve both objectives. We use competitive analysis to evaluate performance of an online algorithm. Competitive analysis is most easily justified when the auctioneer does not have a good model of the environment. For example, the UB has no information about future bid sequences of GRPs. Competitive analysis can help the UB to lead to auction mechanisms that enjoy good average case performance in practice, provide insight into how to design robust auction mechanisms, and produce useful “lower-bound” analysis. The competitive ratio for a reverse online auction problem makes a statement about the best possible performance that can be achieved by an online algorithm. Specifically, given the multi-attribute bid of $B_{i} = (p_{i}, v_{i}, s_{i})$ and the number of tasks of a job, if the UB knows all bid sequences, then he can obtain the optimal offline utility, denoted by optimal algorithm (OPT). On the contrary, the expected utility generated by an online algorithm for reverse online auction problem is denoted by online algorithm (ON). Then, the competitive ratio of the online algorithm is OPT/ON. It can be easily seen that the optimal competitive ratio of any online algorithm for the grid resource allocation problem in a reverse online auction is a lower bound. We present the following two algorithms to describe how to allocate resource based on auction.

TSIB algorithm

Ding et al.¹³ proposed the TSIB algorithm and achieved a better competitive ratio of $r_{0}$ , where $r_{0} = \ln {[(\bar{u} / \underline{u}) - 1] / (r_{0} - 1)}$ . This online algorithm can help the UB to make decision when he has no information about the future multi-attribute bid sequences. Actually, how to calculate the multi-attribute bid is the most important issue for the reverse online auction-based grid computing problem. They take the reverse online auction as a scoring auction and introduce a novel satisfaction degree function. It can normalize the different attributes to achieve the final scores according to the cumulative rules. Hence, the reverse online auction-based grid computing problem can be transformed into a new problem in which the UB makes decision based on the satisfaction degree sequences. In this article, there is the same assumption. It assumes that satisfaction degree input sequences are bounded from $\underline{u}$ to $\bar{u} (0 < \underline{u} \leq \bar{u})$ and that the UB knows the bounds.

TSWF algorithm and competitive analysis

Different from the TSIB algorithm, we present a novel online algorithm for grid resource allocation problem. Before discussing our new online algorithm, we demonstrate a useful property for the GRUs and UB, who have an ability to forecast the future, denoted by $μ$ . Namely, the forecast is what the UB anticipates the multi-attribute bid sequence will do in the future. We define a forecast to be a subset of the possible satisfaction degree inputs. At the same time, we also depart from making stochastic assumptions and investigate the type of forecasts. Since the UB has partial information about what may happen, it can make a forecast that the satisfaction degree will increase to some level, that is, the forecast is that the satisfaction degree will be up to at least $(1 + β) \underline{u} (β > 0)$ at the stage of $λ$ . Then, during the period when the satisfaction degree is between $\underline{u}$ and $(1 + β) \underline{u}$ , the UB sells less tasks compared to TSIB algorithm. This allows the UB to hold more tasks to wait for the coming forecast (i.e. if the forecast is successful). After that, the UB can sell more tasks to the new winners, which gives him a better competitive ratio than that of TSIB algorithm. In this section, we will see how to use the forecast property which involves a single above-forecast to design an online algorithm. We consider the following online algorithm, thereafter called the TSWF algorithm. Let $r_{1}$ be the competitive ratio that can be attained by TSWF algorithm. For a start, assume that $r_{1}$ is known to the GRUs and UB.

TSWF algorithm

Given $\underline{u}$ , $\bar{u}$ , n, $μ$ , Q, and a forecast that the satisfaction degree will be up to $(1 + β) \underline{u}$ , the TSWF algorithm will trade according to the following rules:

Only trade when the satisfaction degree input sequences reach a new high, that is, $u_{i} > u_{i - 1}$ .

While the satisfaction degrees belong to $[\underline{u}, (1 + β) \underline{u})$ , the competitive ratio during the trading should not be greater than $μ r_{0} (1 < μ)$ , whenever the sequences drop to the minimum degree $\underline{u}$ .

When the satisfaction degree reaches $(1 + β) \underline{u}$ at the stage of $λ$ , successful forecast indicates to start a new game, that is, the UB allocates enough to guarantee that a competitive ratio of $r_{1}$ would be obtained even if the satisfaction degrees drop to $\underline{u}$ and remain there for the remainder of the auctioning periods.

When the satisfaction degrees are in $((1 + β) \underline{u}, \bar{u}]$ , the UB converts more tasks to the winning GRPs and achieves more utility, that is, the UB would like to allocate just enough tasks to ensure that a competitive ratio $r_{1}$ would be obtained. Even if an adversary drops the satisfaction degree to $(1 + β) \underline{u}$ , the competitive ratio would keep on $r_{1}$ throughout the remaining game.

In the end of auction, if the UB has the remaining jobs, he has to face the threat of trading with the minimum satisfaction degree.

Computing $q_{i}$

We can calculate the quantity $q_{i}$ of tasks at each stage when a new multi-attribute bid is given by the threat of the satisfaction degree down to $\underline{u}$ . If the TSWF algorithm wishes to achieve a competitive ratio of $r_{1}$ , then it must ensure that

\frac{u_{i} \cdot Q}{\sum_{j = 1}^{i} u_{j} \cdot q_{j} + (Q - \sum_{j = 1}^{i} q_{j}) \cdot \underline{u}} = r_{1}

(2)

where $u_{i} \cdot Q$ is the optimal offline utility and $\sum_{j = 1}^{i} u_{j} \cdot q_{j} + (Q - \sum_{j = 1}^{i} q_{j}) \cdot \underline{u}$ is the online utility so far. Achieving the quantity $q_{i}$ , we discuss the following three cases:

Case 1. If the satisfaction degrees belong to $[\underline{u}, (1 + β) \underline{u})$ , then by rule 2 the UB chooses the TSWF algorithm to keep the competitive ratio of $μ r_{0}$ . The total utilities are

\begin{array}{l} \sum_{j = 1}^{λ - 1} u_{j} \cdot q_{j} + \underline{u} (Q - \sum_{j = 1}^{λ - 1} q_{j}) = \sum_{j = 1}^{λ - 2} u_{j} \cdot q_{j} + u_{λ - 1} \cdot q_{λ - 1} \\ + \underline{u} (Q - \sum_{j = 1}^{λ - 2} q_{j}) - \underline{u} \cdot q_{λ - 1} \end{array}

(3)

Substituting equation (3) into equation (2), we get the selling amount of tasks. That is

q_{j} = \frac{Q}{μ \cdot r_{0}} \cdot \frac{u_{j} - u_{j - 1}}{u_{j} - \underline{u}}

(4)

Case 2. At the stage of $λ$ , the satisfaction degree is up to $(1 + β) \underline{u}$ . Based on equation (2), when $i = λ - 1$ , the UB uses $μ r_{0}$ as the competitive ratio. By rule 3, while $i = λ$ , the UB sets $r_{1}$ as the new competitive ratio (which must be better than $r_{0}$ ). Hence

\frac{Q \cdot u_{λ}}{r_{1}} = u_{λ} \cdot q_{λ} - \underline{u} \cdot q_{λ} + \frac{Q \cdot u_{λ - 1}}{μ \cdot r_{0}}

(5)

By solving equation (5), we can obtain the following equation

q_{λ} = \frac{Q}{(u_{λ} - \underline{u})} (\frac{u_{λ}}{r_{1}} - \frac{u_{λ - 1}}{μ \cdot r_{0}})

(6)

Case 3. If the satisfaction degrees satisfy such sequences of $(1 + β) \underline{u} < u_{i} \leq \bar{u}$ , by rule 4, the quantity of tasks sold to GRPs is

q_{j} = \frac{Q}{r_{1}} \cdot \frac{u_{j} - u_{j - 1}}{u_{j} - u_{λ}}

(7)

Optimal competitive ratio

Based on the quantity $q_{i}$ , the competitive ratio $r_{1}$ of the TSWF algorithm is calculated as follows. According to the trading rules, the TSWF algorithm sells the less quantity of tasks before the forecast is unsuccessful. In essence, the TSWF algorithm is a two-stage TSIB algorithm. In the first stage, when the forecast has not yet come true, it attempts to achieve a competitive ratio of $μ \cdot r_{0}$ under the threat that the satisfaction degree falls to $\underline{u}$ . In the second stage, it attempts to achieve a competitive ratio of $r_{1}$ under the threat that the satisfaction degree drops to $(1 + β) \underline{u}$ . It is clear that TSWF algorithm cannot attain an arbitrarily small $r_{1}$ . For example, the UB converts all his tasks Q to the first GRP at the first multi-attribute bid. But, the UB may fail to achieve a competitive ratio of 1, if the adversary increases the satisfaction degree after the first auctioning period. According to the rules of TSWF algorithm, the smallest competitive ratio $r_{1}$ is obtained as follows.

Let u be a satisfaction degree sequences and $r_{1} > 1$ be any real. When the forecast is achieved at the stage of $λ$ , we know that

\begin{array}{l} \sum_{j = 1}^{n} q_{j} = \frac{Q}{μ \cdot r_{0}} \sum_{j = 1}^{λ - 1} \frac{u_{j} - u_{j - 1}}{u_{j} - \underline{u}} + \frac{Q}{(u_{λ} - \underline{u})} (\frac{u_{λ}}{r_{1}} - \frac{u_{λ - 1}}{μ \cdot r_{0}}) \\ + \frac{Q}{r_{1}} \sum_{j = λ + 1}^{n} \frac{u_{j} - u_{j - 1}}{u_{j} - u_{λ}} \end{array}

(8)

We divide equation (8) into two cases. One is the time sequences from 1 to $λ - 1$ . We take derivatives of $\sum_{j = 1}^{n} q_{j}$ with respect to $u_{λ - 1}$ , it shows that

\frac{\partial \sum_{j = 1}^{n} q_{j}}{\partial u_{λ - 1}} = \frac{Q}{μ \cdot r_{0}} \frac{(u_{λ - 2} - \underline{u}) (u_{λ} - \underline{u}) - (u_{λ - 1} - \underline{u})}{{(u_{λ - 1} - \underline{u})}^{2} (u_{λ} - \underline{u})}

(9)

Setting $\partial \sum_{j = 1}^{n} q_{j} / \partial u_{λ - 1} = 0$ , we have that

(u_{λ - 1} - \underline{u})^{2} = (u_{λ - 2} - \underline{u}) (u_{λ} - \underline{u})

(10)

For the case $j = λ$ , the derivative of $\partial \sum_{j = 1}^{n} q_{j} / \partial u_{λ}$ is

\frac{\partial \sum_{j = 1}^{n} q_{j}}{\partial u_{λ}} = \frac{Q}{r_{1}} \frac{u_{λ}}{u_{λ} - \underline{u}} + \frac{Q}{r_{1}} \frac{u_{λ + 1} - u_{λ}}{u_{λ + 1} - u_{λ}} = - \frac{Q}{r_{1}} \frac{\underline{u}}{(u_{λ} - \underline{u})}

(11)

Notice that $\partial \sum_{j = 1}^{n} q_{j} / \partial u_{λ} < 0$ . It means that the function of $\sum_{j = 1}^{n} q_{j}$ is monotonically decreasing. Hence, when the forecast comes true, the maximum $\sum_{j = 1}^{n} q_{j}$ is obtained by setting $u_{λ} = \underline{u} + β \underline{u}$ . Based on equation (8), we can calculate the competitive ratio of TSWF algorithm. Substituting equation (10) into equation (8), we find that

\begin{array}{l} \frac{λ - 1}{μ \cdot r_{0}} + \frac{n - λ}{r_{1}} - \frac{1}{μ \cdot r_{0}} \sum_{j = 1}^{λ - 1} \frac{u_{j - 1} - \underline{u}}{u_{j} - \underline{u}} \\ - \frac{1}{r_{1}} \sum_{j = λ + 1}^{n} \frac{u_{j - 1} - u_{λ}}{u_{j} - u_{λ}} + \frac{1}{(u_{λ} - \underline{u})} (\frac{u_{λ}}{r_{1}} - \frac{u_{λ - 1}}{μ \cdot r_{0}}) = 1 \end{array}

(12)

For simplicity, suppose that $1 / α = (u_{j - 1} - \underline{u}) / (u_{j} - \underline{u})$ and $1 / γ = (u_{j - 1} - u_{λ}) / (u_{j} - u_{λ})$ . Since $(u_{λ - 1} - \underline{u})^{2} = (u_{λ - 2} - \underline{u}) (u_{λ} - \underline{u})$ , it follows that $(1 / α) = (u_{j - 1} - \underline{u}) / (u_{j} - \underline{u}) = (u_{j} - \underline{u}) / (u_{j + 1} - \underline{u})$ . One can get

\frac{1}{α} = {(\frac{u_{0} - \underline{u}}{u_{λ} - \underline{u}})}^{\frac{1}{λ}} = {[\frac{\underline{u} (μ \cdot r_{0} - 1)}{β \underline{u}}]}^{\frac{1}{λ}} = {[\frac{(μ \cdot r_{0} - 1)}{β}]}^{\frac{1}{λ}}

(13)

For $λ < j \leq n$ , it also has that

\frac{1}{γ} = \frac{u_{λ + 1} - (\underline{u} + β \underline{u})}{u_{n} - (\underline{u} + β \underline{u})} = {[\frac{(\underline{u} + β \underline{u}) (μ \cdot r_{1} - 1)}{\bar{u} - (\underline{u} + β \underline{u})}]}^{\frac{1}{n - λ - 1}}

(14)

By substituting equations (13) and (14) into equation (12), we can solve the competitive ratio of $r_{1}$ . Namely, the competitive ratio is the solution of following equation

\begin{array}{l} \frac{λ - 1}{μ \cdot r_{0}} + \frac{n - λ}{r_{1}} - \frac{λ - 1}{μ \cdot r_{0}} \cdot \frac{1}{α} - \frac{n - λ}{r_{1}} \cdot \frac{1}{γ} \\ + \frac{1}{(u_{λ} - \underline{u})} (\frac{u_{λ}}{r_{1}} - \frac{u_{λ - 1}}{μ \cdot r_{0}}) = 1 \end{array}

(15)

This implies that

r_{1} = \frac{μ \cdot α \cdot r_{0} [β (n - λ) (γ - 1) + (1 + β) γ]}{γ [μ \cdot α \cdot r_{0} \cdot β - β (λ - 1) (α - 1) + (α + β)]}

(16)

Reverse online auction-based protocols

Considering the multi-attribute characters of gird resources, we propose the following protocols to help the UB make the multi-attribute decisions. In nature, the difference between the TSWF algorithm and the TSIB algorithm is the UB’s forecast ability. Hence, in this section, two protocols based on these two online algorithms are designed as follows. The first one is the reverse online auction-based (ROA) protocol without any forecast about satisfaction degree inputs. The other one is the ROAWF protocol, where the UB makes use of partial information to forecast the future inputs of satisfaction degree sequences.

ROA protocol

Phase I: bidding

GRU requires Q tasks of a job to be finished with four attributes.

UB as a broker of GRU decides the auction winner determination rules based on TSIB algorithm.

$GR P_{i}$ , $i = 1, 2, \dots, n$ , sends multi-attribute bid $B_{i} = (p_{i}, v_{i}, s_{i})$ to UB.

Phase II: completion

At each stage i, the UB receives the bid of $GR P_{i}$ and takes the following steps:

1.1. Compute the satisfaction degree $u_{i}$ using equation (1) and make it public for all GRPs.

1.2. If $u_{i} \leq u_{i - 1}$ , then UB sends reject messages to $GR P_{i}$ .

1.3. If $u_{i} > u_{i - 1}$ , then UB notices $GR P_{i}$ that he is the temporary winner and allocates the quantity $q_{i}$ of tasks to $GR P_{i}$ according to TSIB algorithm as follows

{\begin{matrix} q_{i} = \frac{Q}{r_{0}} \cdot \frac{u_{i} - r_{0} \underline{u}}{u_{i} - \underline{u}} i = 1 \\ q_{i} = \frac{Q}{r} \cdot \frac{u_{i} - u_{i - 1}}{u_{i} - \underline{u}} i \neq 1 \end{matrix}

If $GR P_{i}$ is the last one or $i = n$ , then UB terminates the auction.

Determine the trading price and quantity for all winners denoted by $GRP s^{*}$ from the set of temporary winners.

UB sends the tasks to $GRP s^{*}$ and $GRP s^{*}$ execute them.

UB sends payments to $GRP s^{*}$ .

ROAWF protocol

Phase I: bidding

GRU requires Q tasks of a job to be finished with four attributes.

UB as a broker of GRU makes a forecast that the satisfaction degree will be up to $(1 + β) \underline{u}$ based on its forecast ability, denoted by $μ$ . Also, it decides the auction winner determination rules based on TSWF algorithm.

$GR P_{i}$ , $i = 1, 2, \dots, n$ , sends multi-attribute bid $B_{i} = (p_{i}, v_{i}, s_{i})$ to UB.

Phase II: completion

At each stage i, the UB receives the bid of $GR P_{i}$ and takes the following steps:

1.1. Compute the satisfaction degree $u_{i}$ using equation (1) and make it public for all GRPs.

1.2. If $u_{i} \leq u_{i - 1}$ , then UB sends reject messages to $GR P_{i}$ .

1.3. If $u_{i - 1} < u_{i} < (1 + β) \underline{u}$ , then UB notices $GR P_{i}$ that he is the temporary winner and allocates the quantity $q_{i}$ of tasks to $GR P_{i}$ according to TSWF algorithm. Here

q_{i} = \frac{Q}{μ \cdot r_{0}} \cdot \frac{u_{i} - u_{i - 1}}{u_{i} - \underline{u}}

1.4. If $u_{i} = (1 + β) \underline{u}$ , then the forecast comes true and the $GR P_{i}$ is the temporary winner. UB allocates the quantity $q_{i}$ of tasks to $GR P_{i}$ according to the following equation

q_{i} = \frac{Q}{(u_{i} - \underline{u})} (\frac{u_{i}}{r_{1}} - \frac{u_{i - 1}}{μ \cdot r_{0}})

1.5. If $(1 + β) \underline{u} < u_{i}$ , then UB notices $GR P_{i}$ that he is the temporary winner and uses the TSWF algorithm to sell the quantity $q_{i}$ of tasks to $GR P_{i}$ as follows

q_{i} = \frac{Q}{r_{1}} \cdot \frac{u_{i} - u_{i - 1}}{u_{i} - (1 + β) \underline{u}}

If $GR P_{i}$ is the last one or $i = n$ , then UB terminates the auction.

Determine the trading price and quantity for all winners denoted by $GRP s^{*}$ from the set of temporary winners.

UB sends the tasks to $GRP s^{*}$ and $GRP s^{*}$ execute them.

UB sends payments to $GRP s^{*}$ .

Simulation and evaluation

The ROA protocol and the ROAWF protocol are implemented and evaluated based on our simulation. We develop a grid simulator, which facilitates the evaluation of reverse online auction-based allocation protocols in terms of their auction process, user’s satisfaction level, and auction efficiency. We simulate a grid environment consisting of 1000 tasks to be allocated within 20 rounds. It assumes that the reverse price is 200G$, the longest execution time is 150 s, the minimum of the request for memory is 1G. The length of the task is [5000, 15,000] MZ, the speed of the computer that the GRP present is [100, 500] MZ/S, memory distribute over [1, 8]G, bidder’s price distribute over [100, 200] G$, and GRU’s preferences are $w_{1} = 0.3$ , $w_{2} = 0.4$ , and $w_{3} = 0.3$ , respectively.

We compare TSWF algorithm in ROAWF protocol with TSIB algorithm in ROA in Figure 2. The difference between these two protocols is the forecast ability of UB, which can help the UB make use of partial information to forecast the future inputs of satisfaction degree sequence. The competitive ratios of TSIB algorithm and TSWF algorithm are often taken to evaluate the performance. Hence, we analyze the competitive ratio of $r_{0}$ and $r_{1}$ in some cases. The competitive ratio of TSIB algorithm is $r_{0} = 1.632$ . Furthermore, it assumes that $1.2 \leq μ \leq 2$ . The adopted variables are $λ = 5$ and $β = 4$ . The experiment results are illustrated in Figure 2. It finds that when the value of forecast ability changes from 1.2 to 2, under the ROAWF protocol, the competitive ratio of $r_{1}$ decreases from 1.47 to 1.43. This is easy to understand that with the higher forecast ability, the UB has a better performance to sell tasks in contrast to the offline case. The competitive ratio of TSWF algorithm in ROAWF protocol decreases by 3% compared to the increasing of forecast ability by 54%. The above results are based on the same stages. In fact, the trading stages are also influencing the performance of TSWF algorithm, in which the UB can take advantage of competition to gain more utilities. When n increases from 15 to 30, we can draw a similar conclusion that there is a gradual decline in the competitive ratio of the TSWF algorithm. We also find that there is merely a slight difference between the results under $n = 25$ and $n = 30$ in terms of competitive ratio and forecast ability, so we can randomly select auction rounds when the numbers are much closer for simplicity.

Figure 2.

The performance of TSWF algorithm in ROAWF protocol.

In Figure 3, we provide numerical results exploring the relationship between the forecast ability, the forecast, and the competitive ratio. We set $λ = 5$ and $n = 25$ and calculate the competitive ratio of $r_{1}$ for various values of $μ$ and $β$ . According to the original grid simulator, the satisfaction degree sequences are generated. Notice that since the TSWF algorithm dose not trade in some cases, it can make sense when $μ < [u_{i} / r_{1} \underline{u}]$ . When the forecast comes true, the future satisfaction degree sequences are subjected to $β > [1 - (u_{i} / μ r_{1} \underline{u})]$ . As shown in Figure 3, the competitive ratio of $r_{1}$ has the same relationship with the forecast $β$ . Namely, with the increasing of $β$ , the competitive ratio of $r_{1}$ decreases. It means that if the UB forecasts that the satisfaction degree will reach at least three-fifth of the lower bound $\underline{u}$ and achieve a competitive ratio of 1.37%, then he can get a performance “improvement” of about 24% (if his forecast is correct). If we have the double forecast, that is, the satisfaction degree will reach at least 1.2 times the lower bound, then we can get a performance “improvement” of about 37%. Furthermore, the performance of TSWF algorithm in ROAWF protocol can also be evaluated by the combination of $β$ and $μ$ . The higher the $β$ and $μ$ , the lower the competitive ratio. These results highlight how, for reasonable values of $β$ , $μ$ , $λ$ and n, the UB can improve TSWF algorithm’s performance significantly.

Figure 3.

The evaluation of ROAWF protocol for different combinations of $μ$ and $β$ .

As shown in Figure 4, we simulate the process of the reverse online auction, in which each point has two axes, that is, x label denotes the auction stage where each GRP comes and provides multi-attribute bid and y label denotes the satisfaction degrees based on the multi-attribute bid computed by the UB using equation (1). We set $n = 100$ , $λ = 5$ , and $β = 0.6$ . The first rule of TSWF algorithm tells us that when the GRPs take a higher multi-attribute and satisfaction degree than the previous GRP, he could be a temporary winner. This means the ROAWF protocol can achieve more efficiency by these screening rules. In the simulation, the value of satisfaction degree is randomly generated in the case of $n = 100$ . From the figure, it shows that there are only 30 valid stages, that is, in the 70% stages, the multi-attribute bids are invalid and the corresponding satisfaction degree is lower than the previous one. Hence, these stages are not included in the target utility here and in the comparison of ROA protocol and ROAWF protocol to be discussed. In Figure 4, the stochastic outcomes show that the lower bound is 0.18 and the upper bound is 0.88. According to the forecast definition, we have that $(1 + β) \underline{u} = 0.288$ . Thus, the satisfaction degree sequences can be divided into three cases. In case 1, from stage 1 to stage 7, the forecast is not coming, the UB utilizes the ROA protocol to decide the trading numbers for the six temporary winning GRPs. It finds that the satisfaction degree of the fourth GRP is lower than the third GRP. Thus, the fourth GRP fails. In case 2, at stage of 7, the forecast comes true, the UB begins to use ROAWF protocol to sell tasks for the improving performance. From this moment on, the UB will auction more tasks to the GRPs. In case 3, from stage 8 to stage 100, the UB can obtain more performance by ROAWF protocol than ROA protocol. In fact, at the stage of 97, the maximum satisfaction degree, that is, $\bar{u} = 0.88$ appears. After that, all the multi-attribute bids are invalid.

Figure 4.

The bidding process of GRPs in ROAWF protocol.

In Figure 5, we simulate the performance and evaluation of the ROA protocol and the ROAWF protocol. Based on the multi-attribute bidding description in Figure 4, we set the same assumption that $n = 30$ , $λ = 5$ , $β = 0.6$ , $\bar{u} = 0.88$ , and $μ = 1.5$ . The first curve is the competitive ratio of TSIB algorithm in ROA protocol compared with the second curve, which is the competitive ratio of TSWF algorithm in ROAWF protocol. Results of this experiment show that the competitive ratio of $r_{1}$ is strictly smaller than the competitive ratio of $r_{0}$ . The successful forecast of stage 7 makes the UB sell more tasks in the new satisfaction degree sequences and achieve more utilities as shown in Figure 4. It finds that when the lower bound changes from 0.18 to 0.3, under each of these two protocols corresponding competitive ratio decreases. That is, when the lower bound increases, both $r_{1}$ and $r_{0}$ decrease. It means that the smaller interval between the lower bound and the upper bound helps the UB get more chance to be closed to the offline cases. This is easy to understand that the ROAWF protocol using TSWF algorithm in the reverse online auction is superior to ROA protocol in both market efficiency and user satisfaction. It can be mainly explained that, in reverse online auction, the forecast ability help the UB change resource allocation schedule to gain more utilities and better performance. That is to say, in the reverse online auction, when the UB would like to utilize his own forecast ability, the risk to forecast the future will bring about more reward.

Figure 5.

Competitive ratios of TSIB algorithm and TSWF algorithm.

Conclusion

To summarize, the grid environment is ripe for a transformation into a price-driven clearing market, but such a clearing market introduces new theoretical and computational challenges. In this article, we propose a reverse online auction method for grid resource scheduling. We develop the multi-attribute bids for the GRPs to overcome the shortcoming of only-price bidding. Each GRP determines its bid value based on price, memory, and speed. And, the GRUs combine these dimensions into user’s satisfaction degree. Furthermore, the TSWF algorithm is presented for the UB who has a kind of forecast ability, to make decision in the reverse online auction. Then, both ROA protocol and ROAWF protocol based on online algorithms are designed. Experimental results clearly illustrate that the proposed TSWF algorithm and ROAWF protocol have better market efficiency and better performance of competitive ratio.

Footnotes

Academic Editor: Shancang Li

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Science Foundation of China (No. 71471105, 71371111, and 71373247), Research Fund (No. 15ZDB171 and 2015TDJH103), and Taishan Scholar Special Funds.

References

Bapna

Das

Day

. A clock-and-offer auction market for grid resources when bidders face stochastic computational needs. INFORMS J Comput 2011; 23(4): 630–647.

Izakian

Abraham

Ladani

BT.

An auction method for resource allocation in computational grids. Future Gener Comp Sy 2010; 26(2): 228–235.

Cai

Judd

Thain

. Solving dynamic programming problems on a computational grid. Comput Econ 2015; 45(2): 261–284.

Lavi

Nisan

Competitive analysis of incentive compatible online auctions. Theor Comput Sci 2004; 310: 159–180.

Haque

Alhashmi

Parthiban

A survey of economic models in grid computing. Future Gener Comp Sy 2011; 27(8): 1056–1069.

Schnizler

Neumann

Veit

. Trading grid services—a multi-attribute combinatorial approach. Eur J Oper Res 2008; 187(3): 943–961.

Mirzayi

Khayyambashi

MR.

First-price sealed auction model with increased fairness for resource allocation in grids. Inform Tech J 2009; 8(8): 1221–1227.

Sun

Xia

. A game theoretic resource allocation model based on extended second price sealed auction in grid computing. J Comput 2012; 7(1): 65–75.

Kang

Wang

WC.

Multi-attribute double auction models for resource allocation in computational grids. Open Cybern Syst J 2014; 8(1): 357–362.

10.

Kim

KH.

Reward-based allocation of cluster and grid resources for imprecise computation model-based applications. Int J Web Grid Serv 2013; 9(2): 146–171.

11.

Huedo

Montero

Llorente

IM.

A recursive architecture for hierarchical grid resource management. Future Gener Comp Sy 2009; 25(4): 401–405.

12.

Vanmechelen

Depoorter

Broeckhove

Combining futures and spot markets: a hybrid market approach to economic grid resource management. J Grid Comput 2011; 9(1): 81–94.

13.

Ding

Kang

Wang

An on-line auction method for resource allocation in computational grids. J Chem Pharmaceut Res 2013; 5(9): 241–247.

14.

Bar-Yossef

Hilddrum

. Incentive-compatible online auctions for digital goods. In: Proceedings of the 13th symposium on discrete algorithms, San Francisco, CA, 11–13 January 2002, pp.964–970. New York: ACM.

15.

Blum

Kumar

Rudra

. Online learning in online auctions. Theor Comput Sci 2004; 324(2–3): 137–146.

16.

Goldberg

Hartline

Karlin

. Competitive auction. Game Econ Behav 2006; 55: 242–269.

17.

Buchbinder

Jain

Naor

. Online primal-dual algorithms for maximizing ad-auctions revenue. In: Proceedings of the 15th annual European symposium on algorithms, Eilat, Israel, 8–10 October 2007, pp.253–264. Berlin, Heidelberg: Springer.

18.

Babaioff

Immorlica

Kempe

. Online auctions and generalized secretary problem. ACM SIGecom Exch 2008; 7(2): 1–11.

19.

Chakraborty

Devanur

NR.

An online multi-unit auction with improved competitive ratio. In: Proceedings of 6th international workshop of internet and network economics, Stanford, CA, 13–17 December 2010, pp.327–338. Berlin, Heidelberg: Springer.