# Reverse Auction-Based Services Optimization in Cloud Computing Environments

Authors: Hongkun Zhang; Xinmin Liu
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Cloud-based services have been increasingly used to provide on-demand access to a large amount of computing requests, such as data, computing, resources, and so on, in which it is vitally important to correctly select and assign the right resources to a workload or application. This paper presents a novel online reverse auction scheme based on online algorithm for allocating the cloud computing services, which can help the cloud users and providers to build workflow applications in a cloud computing environment. The online reverse auction scheme consists of three parts: online algorithm design, competitive ratio calculation, and performance valuation. The online reverse auction-based algorithm is proposed for the cloud user agent to choose the final winners based on Vickrey–Clarke–Groves (VCG) mechanism and online algorithm (OA). The competitive analysis is applied to calculate the competitive ratio of the proposed algorithm compared with the offline algorithm. This analysis method is significant to measure the performance of proposed algorithm, without the assumption of the distribution of cloud providers’ bids. The results prove that the proposed online reverse auction-based algorithm is the appropriate mechanism because it allows the cloud user agent to make purchase decisions without knowing the future bids. The difference of auction rounds and transaction cost can impressively influence and improve the performance of the proposed reverse auction algorithm.


---

## Body

## 1. Introduction

Cloud computing, as a new computing paradigm, has rapidly emerged in recent years [1, 2], and it is able to solve the large-scale problems arising in industry, science, commerce, and engineering [3]. In recent years, there are some famous commercial cloud platforms, e.g., Amazon elastic compute cloud (EC2), Microsoft Azure, and Linode, which organize a shared resource pool for cloud users and providers to trade services [4, 5]. The basic idea of cloud computing is to deliver computational resources, such as central processing unit (CPU), random-access memory (RAM), and storage, as services across the Internet. The cloud users can purchase the cloud computing services on their dynamic and fluctuating demands. On the other hand, the cloud providers pack their resources into different types of virtual machines and design pricing mechanism. However, the highly dynamic, uncontrollable, and distributed features of grid environment cause the hindering of cloud providers to price the cloud computing services. Thus, how to better manage cloud resources becomes the important problem of cloud computing between the cloud providers and users.At present, the current literature often uses a fixed price method and auction-based method to allocate cloud computing services. For these two methods, the fixed price method is criticized for inherently lacking market efficiency and failing to rapidly adapt to real-time demand-supply relation changes [6]. The auction-based algorithm has been proved to have more advantages [7, 8]. Firstly, fixed price algorithm cannot reflect the change of supply-demand relationship in cloud resource market. Since the auction is a kind of flexible market mechanism, it is the preferred design for the cloud resource business. Secondly, auction-based method requires little global information and enables trade-off more easily to be implemented with decentralized structure [9]. There are a series of literature about auction-based algorithm design in cloud resource markets from different aspects, achieving some new results [10–12]. Although the researchers have achieved many good results using auction-based methods to allocate cloud computing services, there are the following problems. (1) The one-round auction-based method is often conducted, but the multiple round auctions are not considered. (2) The cloud providers should be in a complete information situation to use the above auction-based method, but not in the incomplete information cases. For example, a cloud provider will leave the auction platforms without the prompt reply from the cloud user. Then, the cloud user has to make decision before the coming of the next cloud provider.Therefore, it is quite essential to discover the novel pricing algorithm to satisfy the properties of cloud computing services’ trading. Because of the limitations of current literature, this paper proposes an online reverse auction-based algorithm to allocate cloud computing services using the online algorithm (OA).(1)
Construct an online reverse auction-based algorithm. Based on the reverse auction theory, after the cloud user has service demand requirement, the cloud providers take price to bid this service demand. In reality, the transactions for allocating cloud resources are in an online setting, where the cloud user has to make purchase decisions without knowing the future bids taken by other cloud providers. Thus, this paper constructs an online reverse auction-based algorithm by using the online algorithm proposed by Nisan and Ronen [13].(2)
Calculate the competitive ratio. Competitive analysis proposed by Goldberg et al. [14] is used to calculate the competitive ratio of the performance of online reverse auction-based algorithm. The advantage of competitive analysis is that it does not need any assumption of the distribution from the future events.(3)
valuate the performance. The competitive ratio calculated by the competitive analysis is used for measuring the performance of the online reverse auction-based algorithm by comparison with optimal offline auction algorithm.The main contributions of this paper are as follows. First, this paper introduces the multi-round time dimension into the traditional auction-based method to propose a novel online reverse auction-based algorithm to allocate cloud computing services. Second, the online reverse auction-based algorithm can help the cloud user make purchase decisions while he has no information about the future bid sequences of the cloud providers. Third, the transaction cost of auction service is introduced into the online reverse auction-based algorithm, in which the cloud user has to charge a fee to an agent for auction service. Numerous simulating experiments show that the proposed online reverse auction-based algorithm is effective in cloud service utilization and has better performance in user utility. The auction rounds and the transaction cost play an important role for the cloud user agent’s decision. The auction efficiency can be improved from these two factors.This paper is organized as follows. Section2 introduces the related work. Section 3 describes the reverse auction market. Section 4 presents the novel online reverse auction-based algorithm. Section 5 explains the trading strategies and competitive analysis. Section 6 introduces the simulation and summarizes the experimental results. Conclusions are given in Section 7.


## 2. Related Work

The auction-based algorithm has been applied to various fields, such as grid computing, wireless networks, and cloud computing. The purpose is to analyze how the users and providers behave in a competitive environment. The studies show that different classes of auctions have been considered in the design of the algorithms. An important achievement of auction design is the Vickrey–Clarke–Groves (VCG) mechanism, which is a general method for the construction of truthful mechanisms in an auction market. All reasonable approximations or heuristics for combinatorial auctions are VCG-based mechanisms and have truthful features, which are suitable for a wide class of cost minimization problems [13]. The results essentially indicate that the only truthful auction algorithm is efficient. Thus, for the cloud computing services market, the auction-based algorithm is also truthful if a cloud user or a cloud provider has no incentives to lie about their private information. The current studies have designed some auction-based algorithms to allocate the cloud resources. The most popular auction forms are the English auction, the combinatorial auction, and the double auction. For example, Fujiwara et al. [15] proposed a combinatorial auction to design marketplace mechanism for cloud computing services. The presented auction algorithm helps the cloud users build workflow applications in a cloud computing environment, where the cloud users need to compose multiple types of services at different timeslots. Wang et al. [16] studied an English auction-based algorithm for cloud computing service. They presented an auction framework for cloud computing. Different designs of auction-based algorithms were also discussed. Zaman and Grosu [17] presented two auction schemes to allocate virtual machines for cloud users. They argued that combinatorial auction-based algorithms were more efficient than the fixed price algorithms. The reason is that the virtual machines having the highest valuation are assigned to cloud users. Kang et al. [11] proposed the multi-unit Vickery auctions and one-sided VCG-combinatorial auctions to address cloud service allocation. They proved that these two auction-based algorithms were efficient methods. Lee et al. [18] proposed a new instantiation of the negotiation protocol between the cloud user and cloud provider by using a continuous double auction model. They analyzed and showed different scheduling strategies, which can be applied into the real cloud resource trading. Some studies introduced the double auction forms into combinatorial auction design. For example, Tafsiri and Yousefi [12] studied a combinatorial double auction-based algorithm where a broker performed the allocation of the providers’ virtual machines according to the users’ requests for the cloud computing. In fact, in the above auction mechanism the cloud providers sell the cloud resources and the cloud users take bids to make purchase decisions, which is called forward auction.In recent years, a new auction pattern, that is, the reverse auction, has attracted more attention. The reverse auction model has a high potential for cloud computing. It is different from the traditional auction forms, where the cloud user is an auctioneer and cloud provider is a bidder. Namely, in a reverse auction model, the cloud providers submit bids. The cloud users evaluate the bids by auctioning rules and determine the final winners. Roovers et al. [19] investigated the design of a reverse auction market. They pointed out that the reverse auction had the flexibility and the ability to model and integrate currently deployed pricing schemes of the real world. Prodan et al. [20] extended the continuous double auction problem and introduced a continuous reverse auction that was paired with a novel bidding language based on tag and constraint sets. Prasad and Rao [21] used reverse auction to design a cloud resource procurement approach and showed three possible reverse auction algorithms for cloud resource procurement.However, the above auction-based algorithm designs are considered in offline situations where the final winners are announced after collecting all bids. In fact, both the cloud service providers and users often make decisions under incomplete information [22]. For example, different cloud providers arrive at different times and the cloud users are required to decide whether to accept each bid as it is received without knowing the future bids. In 1999, an online auction algorithm was originally proposed to solve this kind of dynamic grid or cloud resource allocation problem, and the authors used the competitive analysis to calculate the competitive ratio to measure the performance of online auction algorithm [14]. The competitive analysis has gained much recognition in the areas of finance, economics, and operation researches. It is different from the traditional average-case analysis, which focuses on the assumption of the distribution from the future events according to some known probabilities and tries to achieve the good average-case performance. Many researchers extend Goldberg’s work from the following aspects. Hajiaghayi et al. [23] considered an online truth telling mechanism based on the offline Vickrey model. For the limited supply goods, Lavi and Nisan [24] presented an incentive compatible online auction and proved this auction had an optimal competitive ratio with respect to the revenue and the total social efficiency. Zhu et al. [25] studied a reverse online auction problem and designed online reverse auction algorithm based on multi-attribute bids, which achieved a better performance.In recent years, some studies began to design online auction algorithm to allocate the cloud computing service. For example, Zhang et al. [26] conducted a framework for truthful online auctions where the cloud users with heterogeneous demands could come and leave on the fly. They designed a novel bidding language, in which the cloud users’ heterogeneous demands were generalized to be regulated and kept in consistent forms. Based on this bidding language, they proposed an incentive compatible online cloud auction algorithm and got some new results. Shi et al. [6] gave the first online combinatorial auction algorithm for the cloud computing problem. The same results were shown where the auction systems were expressive enough to optimize system efficiency across the temporal domain instead of at an isolated time point. Ding et al. [7] introduced the online auction into the resource scheduling in grid computing networks and designed the online auction-based algorithm. They presented a new multi-attribute multi-round reverse auction, where the gird resource user’s satisfaction degree was introduced into the traditional grid resource allocation problem to help the grid resource broker make multi-attribute decisions under incomplete information.


## 3. The Reverse Auction Market Description

There is a reverse auction market which maintains the requests and bids collected from cloud users and providers, respectively. After the cloud user agent receives instructions from the cloud user, it computes when and how to allocate funds to purchase the cloud computing services from which cloud providers. Figure1 is a flowchart of the reverse auction scheme and shows how the participants work in a market. The cloud user submits his request and private information to the cloud user agent (Label 1). In the reverse auction market, the cloud user agent searches the cloud providers that meet the user’s request and invites them to participate in the auction (Label 2). After the cloud providers take bids in an online manner (Label 5), the cloud user agent reports and announces to the users who are the winners/losers of the auction (Label 3). Once the charging and payment are completed (Label 4), the cloud users and providers establish the connection and complete the deal (Label 6).Figure 1
A flowchart of the proposed reverse auction market.In the reverse auction market, the cloud users and providers have different objectives, strategies, and supply-demand patterns. These participants are presented in the following with a brief explanation.


### 3.1. Cloud Users

In the reverse auction market, the cloud user’s task is to submit his demand constrained by budget, price preferences, and memory size to his agent. It supposes that the cloud user has a budget ofd0, which means the cloud user has total funds of d0 to purchase cloud services. Each service is denoted by a three-tuple Ji=Ti,RPi,Ei, where Ti is the deadline of the service, RPi represents the secret reservation price, and Ei is the minimum memory size. The goal of the cloud user is to spend his total funds to maximize the utility within his corresponding deadlines.


### 3.2. Cloud User’s Agent

Each cloud user has a cloud user agent or a broker. In the auction process, a cloud user agent represents the cloud user to announce the cloud resource requests. His job depends on the user’s request to search cloud providers which can meet user’s demand, and then invite the cloud provider to bid. At the end of game, he chooses the winner of the auction on behalf of the cloud user. In fact, the cloud user agent can be seen as the auctioneer of the reverse auction market. Different from the above literature, we assume that there is transaction cost when trading the cloud resource. Instead of one round, this paper assumes that there aren rounds with the expired time T>0. In each round i, the allocation quantity of the funds of cloud user is denoted by si(si≥0). And, there is a fixed transaction cost denoted by a for the cloud user to pay the agent.


### 3.3. Cloud Providers

In the reverse auction market, the cloud provider’s job is to decide whether to participate in the auction when receiving the invitation from the user agent according to his own capability. If he accepts the invitation, then he takes bid. It supposes that a cloud provideri submits a bid defined by Bi=ei,pi,ti⟶, where ei is the memory size of cloud and pi is the provider’s valuation as a bidding price, which indicates the maximum price that is acceptable for the provider to supply the requesting instances. ti⟶=tis,tie is a length of time during which the cloud provider i wants to reserve a bid between starting time tis and ending time tie. Here, the cloud providers arrive at different times in sequences, which is referred to as the online manner.


## 3.1. Cloud Users

In the reverse auction market, the cloud user’s task is to submit his demand constrained by budget, price preferences, and memory size to his agent. It supposes that the cloud user has a budget ofd0, which means the cloud user has total funds of d0 to purchase cloud services. Each service is denoted by a three-tuple Ji=Ti,RPi,Ei, where Ti is the deadline of the service, RPi represents the secret reservation price, and Ei is the minimum memory size. The goal of the cloud user is to spend his total funds to maximize the utility within his corresponding deadlines.


## 3.2. Cloud User’s Agent

Each cloud user has a cloud user agent or a broker. In the auction process, a cloud user agent represents the cloud user to announce the cloud resource requests. His job depends on the user’s request to search cloud providers which can meet user’s demand, and then invite the cloud provider to bid. At the end of game, he chooses the winner of the auction on behalf of the cloud user. In fact, the cloud user agent can be seen as the auctioneer of the reverse auction market. Different from the above literature, we assume that there is transaction cost when trading the cloud resource. Instead of one round, this paper assumes that there aren rounds with the expired time T>0. In each round i, the allocation quantity of the funds of cloud user is denoted by si(si≥0). And, there is a fixed transaction cost denoted by a for the cloud user to pay the agent.


## 3.3. Cloud Providers

In the reverse auction market, the cloud provider’s job is to decide whether to participate in the auction when receiving the invitation from the user agent according to his own capability. If he accepts the invitation, then he takes bid. It supposes that a cloud provideri submits a bid defined by Bi=ei,pi,ti⟶, where ei is the memory size of cloud and pi is the provider’s valuation as a bidding price, which indicates the maximum price that is acceptable for the provider to supply the requesting instances. ti⟶=tis,tie is a length of time during which the cloud provider i wants to reserve a bid between starting time tis and ending time tie. Here, the cloud providers arrive at different times in sequences, which is referred to as the online manner.


## 4. A Novel Online Reverse Auction-Based Algorithm

This paper studies the online reserve auction problem in the online setting. In each round, facing the historical bids and limited current information, the cloud user agent has to make decisions without knowing the future bids [16], or the distribution functions of bids [17]. This paper aims to design a novel online reverse auction-based algorithm to be carried out by the cloud user agent, which guides cloud resource allocation in the cloud computing service market. We use the competitive analysis to evaluate the performance of the online reverse auction-based algorithm.Definition 1.
The online reserve auction is defined as follows:(1)
In each round, the cloud provideri arrives and announces his bid Bi=ei,pi,ti⟶, where each pi is a real number in the interval of m,M.(2)
The cloud user agent determines whether to buy the cloud computing service from the cloud provideri and if so, at what price and quantity before opening the next bid.(3)
The game ends when the last cloud provider announces his bid during the time of0,T.Definition 2.
The competitive ratio of online reverse auction-based algorithm is defined as follows:(1)
LetOPTB be the optimal benefit by an offline algorithm denoted by OPT for any bid sequences B.(2)
LetALGB be the benefit generated by the online reverse auction-based algorithm denoted by ALG for any bid sequences B.(3)
The competitive ratior of the online reverse auction-based algorithm is calculated by r=OPTB/ALGB.Definition 3.
The competitive analysis of online reverse auction-based algorithm is defined as follows. It says an online reverse auction-based algorithm isr-competitive if the benefit of ALG satisfies OPTB≤r⋅ALGB.
In this definition,r is the competitive ratio of the online reverse auction-based algorithm ALG. That is, the infimum over all r is called the competitive ratio of the online reverse auction-based algorithm ALG. On the other hand, an online reverse auction-based algorithm is said to be best possible if there does not exist another online algorithm with a strictly smaller competitive ratio. The closer to 1 the competitive ratio, the more benefit the online reverse auction-based algorithm ALG can obtain.
Next, we design a novel online reverse auction-based algorithm, which extends the threat-based algorithm proposed by Lavi and Nisan [16] through taking the transaction cost into consideration. Although this paper considers the online reverse auction-based algorithm as VCG mechanism, it is different from the study of Lavi and Nisan [16], which studies the forward auction, relative to the reverse online auction. In the online reserve auction market for the cloud computing services, the cloud user agent has to consider a risk by assuming that bid sequences will increase to the highest price. Hence, the proposed online reverse auction-based algorithm helps the cloud user agent reserve enough funds to ensure a competitive ratio of r, even though the bid sequences stay at a higher price. Specially, even if the cloud user agent meets the worst case and has to buy services at the highest price at the end of the auction game, the competitive ratio is no more than r.
A novel online reverse auction-based algorithm is proposed as follows.
LetSP and NSP denote the sets of preferred and not-preferred bids, respectively. We design a novel online reverse auction-based algorithm for the cloud user agent to update his decisions. Given r, m, M, and a new bid pi, the cloud user agent makes a decision according to the following rules:Step 1. Set i=1 and SP=NSP=Φ.Step 2. In round i, one cloud provider comes and presents his bid, i.e.,Bi=ei,pi,ti⟶.Step 3. Before the end of round t, the cloud user agent decides whether to accept bids. If the bid value reaches a new low, that is, pi<mini>jpj, and the memory size of cloud satisfies ei>Ei, the cloud user agent places the accepted bid in set SP, and go to Step 4. Otherwise, place the refused bid in set NSP and go to Step 7.Step 4. The cloud user agent uses such a rule to allocate the cloud user’s original funds that is spend less money to buy service to keep the competitive ratio as a constant of r. That is, compute the trading funds of si based on the following rules:(1)s1=1r⋅d0−a1−rmp11−mp1+a1−p1mi=1,si=1r⋅d0−api−1−pipi−1−pipi−1m+a1−pim1<i.Step 5. Inform the winning cloud provider in set SP of the trading price and quantities between the time interval of tis,tie.Step 6. Set i=i+1. Go to Step 2. If i=n, go to Step 7.Step 7. Stop. The winning cloud providers are bids in SP. If there are remaining funds, then the cloud user agent has to purchase the job or service at the highest price of M. Even in this worst case, the competitive ratio is no more than r.


## 5. Competitive Analysis of the Online Reverse Auction-Based Algorithm

In this section, the competitive analysis is used to evaluate the performance of the online reverse auction-based algorithm. We divide the online reverse auction-based algorithm into two cases as follows. One is that the cloud user agent charges a fee for his auction service. The other is that the cloud user agent is free for auction service.


### 5.1. Case 1: The Cloud User Agent Charges a Fee

If the cloud user agent knows all the bid sequences, the optimal offline benefit can be achieved by the optimal offline algorithm. According to Definition2, in round i, the optimal offline benefit is OPTB=d0−a/pi. The benefit of online reverse auction-based algorithm is ALGB=∑i=1nsi/pi, where si is the trading funds. Hence, the competitive ratio denoted by r of the online reverse auction-based algorithm can be computed as follows:(2)r=minmaxd0−api∑j=1isj/pj,s.t.∀i,si≥0,∑i=1nsi=d0.In order to solve the optimal competitive ratio ofr, we assume that Di is the remaining funds owned by the cloud user agent after the round i. The accumulative quantities of cloud computing services bought by the cloud user agent before round i are Yi=∑j=1isj/pj. If i=n, then the total quantities of services are Yn=∑j=1nsj/pj. At the same time, it is shown that si=Di−1−Di with the range of si∈0,d0−∑j=1i−1sj. In Section 4, the online reverse auction-based algorithm implies us that the trading only occurs when the new bid is lower than the previous one. Hence, it assumes that some bid sequences keep declining to the lower bound of pmin until round k, and then the remaining bid sequences keep the upper bound of pmax. Namely, the bid sequences are pmin<pk<⋯<p2<p1 and pk+1=pk+2=⋯=pn=pmax. For simplicity, suppose that bi=1/pi, bmin=1/pmax=m, and bmax=1/pmin=M. Therefore, the cloud user agent has to encounter such a worse case that bid sequences are m<b1<b2<⋯<bk<M and bk+1=bk+2=⋯=bn=m.Based on (2), the competitive ratio also can be translated into the other form as follows:(3)r=d0−api∑j=1isj/pj=d0−abiYi+Di−am.From equation (3), we get(4)Yi+Di−am=d0−abir.It means that in roundi the accumulative quantities of cloud computing services Yi and the remaining funds Di have a linear relationship. Hence, we can decompose the formula about the accumulative quantities of services into the following forms:(5)Yi=Yi−1+si−api=Yi−1+si−abi.The function about remaining funds also can be divided into the new form:(6)Di=Di−1−si.According to equation (3), the competitive ratio also can be described as follows:(7)r=d0−abiYi+Di−am=d0−abi−1Yi−1+Di−1−am.Substituting equations (5) and (6) into equation (7), we solve equation (7) to achieve the trading funds in the round of i:(8)si=1r⋅d0−abi−bi−1bi−m+abibi−m.Takingbi=1/pi into equation (8), we achieve that(9)si=1r⋅d0−api−1−pipi−1−pipi−1m+a1−pim.Wheni=1, the cloud user agent makes a decision based on the first bid of p1 by using equation (9); we can get that(10)s1=1r⋅d0−a1−rmp11−mp1+a1−p1m.Competitive ratio of the online reverse auction-based algorithm in Case 1 is presented.When the cloud user agent chooses the online reverse auction-based algorithm to allocate funds, the adversary would present the bad bid sequences to make him in a worst case. For example, for anyk(0<k≤n), if the accumulative trading quantities are ∑i=1ksi≤d0, then the best for the cloud user agent is to spend all funds to buy services before the end of n. Hence, substituting (8) and (10) into ∑i=1ksi=d0, we obtain that(11)1r⋅d0−ab1−rmb1−m+ab1b1−m+∑i=2kd0−abi−bi−1rbi−m+∑i=2kabibi−m=d0,where bi=1/pi.Solving equation (11), we have that(12)r=rkb1,b2,…,bk=d0−ab1+∑i=2kd0−abi−bi−1/bi−mb1−md0−ab1/b1−m−∑i=2kabi/bi−mb1−m+d0−am=b1+∑i=2kbi−bi−1/bi−mb1−md0−∑i=1kabi/bi−m⋅b1−m/d0−a+m.Sincek<n and m≤b1<b2<⋯<bk≤M, we optimize rkb1,b2,...,bk to get the optimal competitive ratio of the online reverse auction-based algorithm. For equation (12), the difficulty is to solve the cumulative sum. Next, we solve and simplify these two cumulative sums. Hence, we have(13)∑i=2kbi−bi−1bi−m=∑i=2kbi−m−bi−1−mbi−m.Because the cumulative summation formula is larger than the cumulative multiplication formula for the same sequences ofxi−1/xi, that is, ∑i=2kxi−1/xi≥k−1x1/x2⋅x2/x3⋯⋅xk−1/xk1/k−1=k−1x1/xk1/k−1, we have the following relation between them:(14)∑i=2kbi−bi−1bi−m=k−1−∑i=2kbi−1−mbi−m.We take first-order derivation of (14) with respect to bi−m and find that(15)∂Σ∂bi−m=0⇒bi−mbi−1−m=bi+1−mbi−m.Hence, the cumulative summation formula can be described as follows:(16)∑i=2kbi−bi−1bi−m≥k−11−b1−mbk−m1/k−1.For the other cumulative summation formula of∑i=2kabi/bi−m, we have that(17)∑i=1kabibi−m=ak+am∑i=1k1bi−m.Sincebi−m/bi+1−m=b1−m/bk−m1/k−1, we set b1−m/bk−m1/k−1=q and obtain that(18)1bk−m=qk−1b1−m.Hence, we get(19)∑i=1k1bi−m=∑i=1kqi−1b1−m=1−qkb1−m1−q.We bring equation (19) into formula (17) and get that(20)∑i=1kabibi−m=ak+am1−b1−m/bk−mk/k−1b1−m1−b1−m/bk−m1/k−1.Substituting (16) and (20) into (12), the new competitive ratio formula is to maximize the function of rkb1,b2,…,bk as follows:(21)maxrkb1,b2,…,bk=b1+k−11−b1−m/bk−m1/k−1b1−md0−akb1−m/d0−a−am1−b1−m/bk−mk/k−1/1−b1−m/bk−m1/k−1+m.Taking the derivation ofrkb1,b2,…,bk with respect to bk, we get ∂r/∂bk>0. Therefore, it is shown that rkb1,b2,…,bk would go up with the increasing of bk. There is a positive relationship between them. Hence, while bk=M and k=n, the competitive ratio of rkb1,b2,…,bk is maximized. Because of the complexity of equation (21), we do not replace 1/p1 with b1. The simple function of competitive ratio can be described as the function of M,m,b1,n, and a.(22)r=rb1=b1+n−11−b1−m/M−m1/n−1b1−md0−ab1−m/M−m1/n−1−1d0−anb1−m+d0−amd0−ab1−m/M−m1/n−1−1−amb1−m/M−mn/n−1−1.From equation (22), it is shown that the first bid b1 is very important. If it is lower than rm, then the cloud user agent would not do any trading by the online reverse auction-based algorithm. Hence, the bid b1 should be more than rm. If we want to get the optimal competitive ratio, the first bid b1 should be given based on equation (22). The online reverse auction-based algorithm presents an idea that the adversary would like to take the worst bid sequences to make the cloud user agent be worst case. Then, we introduce the average idea into the online reverse auction-based algorithm to help the cloud user agent reduce risk in the worst case. Suppose that the cloud user agent divides the total funds into n; that is, s1=d0/n. Therefore, we have that(23)1r⋅d0−ab1−r1mb1−m+ab1b1−m=d0n.Solving equation (23), we obtain that(24)b1=d0−d0n+anrmr+a−ra−d0n.


### 5.2. Case 2: The Cloud User Agent Is Free

For this case, the cloud user agent is free for the auction and helps the cloud users to choose suitable cloud service price. Based on an adversary argument, we show that the online reverse auction-based algorithm without transaction cost can achieve a smaller competitive ratio.In this case, it means thata=0. Hence, we can achieve the trading funds si′ by similar derivation from Case 1 when the competitive ratio is r′. That is,(25)si′=1r′⋅d0pi−1−pipi−1−pipi−1m.Wheni=1, the cloud user agent can decide the trading funds based on the first bid of p1, the same as equation (10); we have that(26)s1′=1r′⋅d01−r′mp11−mp1.Competitive ratio of the online reverse auction-based algorithm in Case 2 is presented.In this case, the cloud user agent uses the same rules of the online reverse auction-based algorithm to price the cloud service. Substituting (25) and (26) into ∑i=1ksi=d0, for any k(0<k≤n) we obtain that(27)1r′⋅d01−r′mp11−mp1+∑i=2k1r′⋅d0pi−1−pipi−1−pipi−1m=d0.Setbi=1/pi. Then, we get(28)1r′⋅d0b1−r′mb1−m+∑i=2kd0bi−bi−1r′bi−m=d0.Comparing equation (11) with equation (28), it shows that equation (28) is the special case of equation (11) when a=0. Hence, we simplify the solving process of competitive ratio of the online reverse auction-based algorithm without transaction cost. Based on equation (22), the competitive ratio of the online reverse auction-based algorithm without transaction cost is achieved by the following equation:(29)r′=rb1=b1+n−11−b1−m/M−m1/n−1b1−md0b1.In the first round, the adversary presentsp1 to the cloud user agent. Maybe if the cloud user agent spends less than d0/n funds for this bid, then the adversary ends the game. Then, the cloud user agent may encounter the loss. Namely, the cloud user agent has to use his remaining funds to buy cloud computing services at the maximum price. Hence, the cloud user agent also can use the average strategy to guarantee the competitive ratio of r′. Substituting s1′=d0/n into equation (26), we have that(30)b1=d0n−1r′md0n−r′.For the competitive analysis of these two cases, the emphasis is to discuss how the transaction cost affects the performance of online reverse auction-based algorithm. Based on equations (22) and (29), we can compare them to discover the smaller competitive ratio. Also, the sensitivity analysis about the competitive ratios in these two cases is presented in Section 6.


## 5.1. Case 1: The Cloud User Agent Charges a Fee

If the cloud user agent knows all the bid sequences, the optimal offline benefit can be achieved by the optimal offline algorithm. According to Definition2, in round i, the optimal offline benefit is OPTB=d0−a/pi. The benefit of online reverse auction-based algorithm is ALGB=∑i=1nsi/pi, where si is the trading funds. Hence, the competitive ratio denoted by r of the online reverse auction-based algorithm can be computed as follows:(2)r=minmaxd0−api∑j=1isj/pj,s.t.∀i,si≥0,∑i=1nsi=d0.In order to solve the optimal competitive ratio ofr, we assume that Di is the remaining funds owned by the cloud user agent after the round i. The accumulative quantities of cloud computing services bought by the cloud user agent before round i are Yi=∑j=1isj/pj. If i=n, then the total quantities of services are Yn=∑j=1nsj/pj. At the same time, it is shown that si=Di−1−Di with the range of si∈0,d0−∑j=1i−1sj. In Section 4, the online reverse auction-based algorithm implies us that the trading only occurs when the new bid is lower than the previous one. Hence, it assumes that some bid sequences keep declining to the lower bound of pmin until round k, and then the remaining bid sequences keep the upper bound of pmax. Namely, the bid sequences are pmin<pk<⋯<p2<p1 and pk+1=pk+2=⋯=pn=pmax. For simplicity, suppose that bi=1/pi, bmin=1/pmax=m, and bmax=1/pmin=M. Therefore, the cloud user agent has to encounter such a worse case that bid sequences are m<b1<b2<⋯<bk<M and bk+1=bk+2=⋯=bn=m.Based on (2), the competitive ratio also can be translated into the other form as follows:(3)r=d0−api∑j=1isj/pj=d0−abiYi+Di−am.From equation (3), we get(4)Yi+Di−am=d0−abir.It means that in roundi the accumulative quantities of cloud computing services Yi and the remaining funds Di have a linear relationship. Hence, we can decompose the formula about the accumulative quantities of services into the following forms:(5)Yi=Yi−1+si−api=Yi−1+si−abi.The function about remaining funds also can be divided into the new form:(6)Di=Di−1−si.According to equation (3), the competitive ratio also can be described as follows:(7)r=d0−abiYi+Di−am=d0−abi−1Yi−1+Di−1−am.Substituting equations (5) and (6) into equation (7), we solve equation (7) to achieve the trading funds in the round of i:(8)si=1r⋅d0−abi−bi−1bi−m+abibi−m.Takingbi=1/pi into equation (8), we achieve that(9)si=1r⋅d0−api−1−pipi−1−pipi−1m+a1−pim.Wheni=1, the cloud user agent makes a decision based on the first bid of p1 by using equation (9); we can get that(10)s1=1r⋅d0−a1−rmp11−mp1+a1−p1m.Competitive ratio of the online reverse auction-based algorithm in Case 1 is presented.When the cloud user agent chooses the online reverse auction-based algorithm to allocate funds, the adversary would present the bad bid sequences to make him in a worst case. For example, for anyk(0<k≤n), if the accumulative trading quantities are ∑i=1ksi≤d0, then the best for the cloud user agent is to spend all funds to buy services before the end of n. Hence, substituting (8) and (10) into ∑i=1ksi=d0, we obtain that(11)1r⋅d0−ab1−rmb1−m+ab1b1−m+∑i=2kd0−abi−bi−1rbi−m+∑i=2kabibi−m=d0,where bi=1/pi.Solving equation (11), we have that(12)r=rkb1,b2,…,bk=d0−ab1+∑i=2kd0−abi−bi−1/bi−mb1−md0−ab1/b1−m−∑i=2kabi/bi−mb1−m+d0−am=b1+∑i=2kbi−bi−1/bi−mb1−md0−∑i=1kabi/bi−m⋅b1−m/d0−a+m.Sincek<n and m≤b1<b2<⋯<bk≤M, we optimize rkb1,b2,...,bk to get the optimal competitive ratio of the online reverse auction-based algorithm. For equation (12), the difficulty is to solve the cumulative sum. Next, we solve and simplify these two cumulative sums. Hence, we have(13)∑i=2kbi−bi−1bi−m=∑i=2kbi−m−bi−1−mbi−m.Because the cumulative summation formula is larger than the cumulative multiplication formula for the same sequences ofxi−1/xi, that is, ∑i=2kxi−1/xi≥k−1x1/x2⋅x2/x3⋯⋅xk−1/xk1/k−1=k−1x1/xk1/k−1, we have the following relation between them:(14)∑i=2kbi−bi−1bi−m=k−1−∑i=2kbi−1−mbi−m.We take first-order derivation of (14) with respect to bi−m and find that(15)∂Σ∂bi−m=0⇒bi−mbi−1−m=bi+1−mbi−m.Hence, the cumulative summation formula can be described as follows:(16)∑i=2kbi−bi−1bi−m≥k−11−b1−mbk−m1/k−1.For the other cumulative summation formula of∑i=2kabi/bi−m, we have that(17)∑i=1kabibi−m=ak+am∑i=1k1bi−m.Sincebi−m/bi+1−m=b1−m/bk−m1/k−1, we set b1−m/bk−m1/k−1=q and obtain that(18)1bk−m=qk−1b1−m.Hence, we get(19)∑i=1k1bi−m=∑i=1kqi−1b1−m=1−qkb1−m1−q.We bring equation (19) into formula (17) and get that(20)∑i=1kabibi−m=ak+am1−b1−m/bk−mk/k−1b1−m1−b1−m/bk−m1/k−1.Substituting (16) and (20) into (12), the new competitive ratio formula is to maximize the function of rkb1,b2,…,bk as follows:(21)maxrkb1,b2,…,bk=b1+k−11−b1−m/bk−m1/k−1b1−md0−akb1−m/d0−a−am1−b1−m/bk−mk/k−1/1−b1−m/bk−m1/k−1+m.Taking the derivation ofrkb1,b2,…,bk with respect to bk, we get ∂r/∂bk>0. Therefore, it is shown that rkb1,b2,…,bk would go up with the increasing of bk. There is a positive relationship between them. Hence, while bk=M and k=n, the competitive ratio of rkb1,b2,…,bk is maximized. Because of the complexity of equation (21), we do not replace 1/p1 with b1. The simple function of competitive ratio can be described as the function of M,m,b1,n, and a.(22)r=rb1=b1+n−11−b1−m/M−m1/n−1b1−md0−ab1−m/M−m1/n−1−1d0−anb1−m+d0−amd0−ab1−m/M−m1/n−1−1−amb1−m/M−mn/n−1−1.From equation (22), it is shown that the first bid b1 is very important. If it is lower than rm, then the cloud user agent would not do any trading by the online reverse auction-based algorithm. Hence, the bid b1 should be more than rm. If we want to get the optimal competitive ratio, the first bid b1 should be given based on equation (22). The online reverse auction-based algorithm presents an idea that the adversary would like to take the worst bid sequences to make the cloud user agent be worst case. Then, we introduce the average idea into the online reverse auction-based algorithm to help the cloud user agent reduce risk in the worst case. Suppose that the cloud user agent divides the total funds into n; that is, s1=d0/n. Therefore, we have that(23)1r⋅d0−ab1−r1mb1−m+ab1b1−m=d0n.Solving equation (23), we obtain that(24)b1=d0−d0n+anrmr+a−ra−d0n.


## 5.2. Case 2: The Cloud User Agent Is Free

For this case, the cloud user agent is free for the auction and helps the cloud users to choose suitable cloud service price. Based on an adversary argument, we show that the online reverse auction-based algorithm without transaction cost can achieve a smaller competitive ratio.In this case, it means thata=0. Hence, we can achieve the trading funds si′ by similar derivation from Case 1 when the competitive ratio is r′. That is,(25)si′=1r′⋅d0pi−1−pipi−1−pipi−1m.Wheni=1, the cloud user agent can decide the trading funds based on the first bid of p1, the same as equation (10); we have that(26)s1′=1r′⋅d01−r′mp11−mp1.Competitive ratio of the online reverse auction-based algorithm in Case 2 is presented.In this case, the cloud user agent uses the same rules of the online reverse auction-based algorithm to price the cloud service. Substituting (25) and (26) into ∑i=1ksi=d0, for any k(0<k≤n) we obtain that(27)1r′⋅d01−r′mp11−mp1+∑i=2k1r′⋅d0pi−1−pipi−1−pipi−1m=d0.Setbi=1/pi. Then, we get(28)1r′⋅d0b1−r′mb1−m+∑i=2kd0bi−bi−1r′bi−m=d0.Comparing equation (11) with equation (28), it shows that equation (28) is the special case of equation (11) when a=0. Hence, we simplify the solving process of competitive ratio of the online reverse auction-based algorithm without transaction cost. Based on equation (22), the competitive ratio of the online reverse auction-based algorithm without transaction cost is achieved by the following equation:(29)r′=rb1=b1+n−11−b1−m/M−m1/n−1b1−md0b1.In the first round, the adversary presentsp1 to the cloud user agent. Maybe if the cloud user agent spends less than d0/n funds for this bid, then the adversary ends the game. Then, the cloud user agent may encounter the loss. Namely, the cloud user agent has to use his remaining funds to buy cloud computing services at the maximum price. Hence, the cloud user agent also can use the average strategy to guarantee the competitive ratio of r′. Substituting s1′=d0/n into equation (26), we have that(30)b1=d0n−1r′md0n−r′.For the competitive analysis of these two cases, the emphasis is to discuss how the transaction cost affects the performance of online reverse auction-based algorithm. Based on equations (22) and (29), we can compare them to discover the smaller competitive ratio. Also, the sensitivity analysis about the competitive ratios in these two cases is presented in Section 6.


## 6. Simulation and Experimental Results

In this section, we provide some experimental results of competitive ratios attained by the online reverse auction-based algorithm discussed in two cases. For simplicity, we assume that competitive ratio isr1 and r2, respectively, for free case and chargeable case. Consider Figure 2. Clearly, when we set M=290, d0=200, n=50, and a=0.1, the competitive ratios of r1 and r2 are all decreasing with the increasing of m, which means that these online reverse auction-based algorithms are always significantly better than all other algorithms. Notice that the competitive ratio of online reverse auction-based algorithm for chargeable case is worse than the one for free case. The reason is that the transaction cost increases the cloud user burden and reduces his utility. In general, it is not hard to show that the limits of the competitive ratios of r1 and r2 for free case and chargeable case are all 1.55.Figure 2
The comparison betweenr1 and r2.Figure3 shows that the online reverse auction-based algorithm enables the cloud user to manage his funds and utilize the transaction cost to achieve better performance. In Figure 3, the curve indicates the competitive ratio of r2 is strictly less than 1.52. That is, the performance curve of online reverse auction-based algorithm expresses the behavior of competitive ratio, where lower bound m serves as the independent, and the competitive ratios serve as the dependent. Across these axes, the performance curves slope downward, which represents a negative relationship between the lower bound and the competitive ratios.Figure 3
The performance of online reverse auction-based algorithm withn.From Figure3, we find that increasing the auction rounds will result in worse performance of the online reverse auction-based algorithm. Specifically, we compare the performance of online reverse auction-based algorithm for different n. It can be seen that when M=290, d0=200, and a=0.1, and the auction round is 15, 50, and 100, the competitive ratio of online reverse auction-based algorithm decreases from 1.52 to 1.48. In nature, the auction rounds increase the competition between the cloud providers. But, it is lower efficiency for the cloud user to make a decision when he is in an incomplete environment.Figure4 shows the results about the performance of online reverse auction-based algorithm with a. It finds that the competitive ratio function is represented by transaction cost. That is, there is a negative relationship between the competitive ratio and the transaction cost. When increasing the transaction cost from 0.1 to 0.3, the competitive ratio of r2 gradually decreases from 1.75 to 1.5. Many studies take no account of the transaction cost. This is usually contrary to the facts. However, this kind of cost would offset the benefit with a corresponding auction trading. Hence, it is necessary to introduce transaction cost into the design of auction system for cloud computing services, which is suitable for all participants in the auction market.Figure 4
The performance of online reverse auction-based algorithm witha.We simulate the process of online reverse auction-based algorithm (see Figure5) and then show the difference of cloud user agent’s decision with different transaction cost. If the cloud user agent has known all bid sequences, he could make an optimal offline strategy and get the maximum benefit. However, in the online manner, the cloud user agent has no idea about the future bid of cloud providers. We present the online reverse auction-based algorithm to help the cloud user agent to purchase service. That is, the cloud user agent chooses the winning cloud providers according to the online reverse auction-based algorithm, while a bidder’s bid meets the request of online reverse auction-based algorithm. In Figure 5, the blue bar, green bar, and brown bar represent the trading funds, respectively, while a=0.1, a=2, and a=5. It is shown that when b1=133, the trading funds are the highest among all si. This accords with the risk ideas. Since the adversary would make the cloud user agent in worst case, the cloud user agent would purchase more services when the first bid satisfies the trading rules based on a-threat based algorithm. Furthermore, compared with Ding et al. [7], the results are more instructive and meaningful for taking into account transaction cost and transaction price in this paper.Figure 5
The efficiency of online reverse auction-based algorithm witha.


## 7. Conclusions

This paper proposes a novel online reverse auction method for allocating the cloud computing services, which can help the cloud users and providers to build workflow applications in a cloud computing environment. The proposed online reverse auction-based algorithm is evaluated by the competitive analysis from the free case and chargeable case. The results prove that the proposed reverse auction algorithm is an appropriate mechanism, because it allows the cloud user agent to make purchase decisions without knowing the future bids. The difference of auction rounds and transaction cost can impressively influence and improve the performance of the proposed reverse auction algorithm. In the future, except for the price of cloud services, some other factors, e.g., cloud service efficiency and cloud service quality, can be introduced into the averse auction market.



---

*Source: 6666628-2021-03-18.xml*