Online Procurement Auctions for Resource Pooling in Client-Assisted Cloud Storage Systems
This study explores the use of online procurement auctions in client-assisted cloud storage systems to improve resource pooling and manage cloud outages. It discusses the benefits of client assistance, cloud storage services, common cloud outages, and potential solutions like Cloud Federation and Client-Assisted Cloud Storage. Various examples in academia are also highlighted to demonstrate the advantages of client assistance in cloud storage systems.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Online Procurement Auctions for Resource Pooling in Client-Assisted Cloud Storage Systems IEEE INFOCOM 2015, HONG KONG Jian Zhao, Xiaowen Chu, Hai Liu, Yiu-Wing Leung Department of Computer Science Hong Kong Baptist University Zongpeng Li Department of Computer Science University of Calgary 1
Outline Motivation: why client-assisted? IEEE INFOCOM 2015, HONG KONG Background: auctions Model formulation Some technical details (without equations) 2 Conclusions
Cloud Storage Services IEEE INFOCOM 2015, HONG KONG 3
Most of the time, CSPs are IEEE INFOCOM 2015, HONG KONG Durability: Our data will be there without error forever. 4 Availability: Data can be accessed anywhere, anytime, from any device.
But occasionally, they become Cloud Outages! IEEE INFOCOM 2015, HONG KONG 5
Cloud Outages Cloud services could become unavailable because of IEEE INFOCOM 2015, HONG KONG 6
Evidence of Cloud Outages Inforworld.com has been tracing cloud outages since 2011 The worst cloud outages of 201X by J. R. Raphael IEEE INFOCOM 2015, HONG KONG Amazon Google Microsoft Apple Dropbox Facebook Adobe Big names on the list 7
What can we do? Plan A: Cloud Federation IEEE INFOCOM 2015, HONG KONG 8
Alternatively Plan B: Client-Assisted Cloud Storage IEEE INFOCOM 2015, HONG KONG 9
Client-Assisted Examples in Academia Leverage peer bandwidth to mitigate server bandwidth cost Improve availability and downloading performance FS2You IEEE INFOCOM 2015, HONG KONG Data is kept at a central cloud and replicated among distributed peers AmazingStore Peer-assisted architecture with a focus on data consistency Triton 10
A Counter Example: Wuala was designed to be client-assisted . Client users casual peers without contribution storage peers trading local storage for increased storage space Servers in datacenters IEEE INFOCOM 2015, HONG KONG Wuala abandoned the client-assisted design in 2012 Hybrid architecture is very complicated Bandwidth cost is dropping Contribution from peers are marginal More focus on business customers 11
Another Story: Symform IEEE INFOCOM 2015, HONG KONG Observation Goal Method cloud providers use extremely inefficient centralized infrastructure to store stuff. most users had tons of excess local storage just going to waste Creating the World s Largest Datacenter Without Building a Datacenter Users that contribute get 1 GB free for every 2 GB contributed Acquired by Quantum in 2014 12
Incentive makes a difference Total upload = Total download Private BitTorrent Public BitTorrent (or Darknet) Tit-for-Tat only Free-rider problem Stop seeding after downloading Limit the uploading bandwidth Sharing Ratio Enforcement Users fight to contribute as much as they can to survive Everyone in the community can get high downloading performance People are willing to pay to get into the community IEEE INFOCOM 2015, HONG KONG 13
Auctions Auctions are economical approaches for allocating resources or trading commodities IEEE INFOCOM 2015, HONG KONG Participants: auctioneer + bidders Auction mechanism: a set of institutions for the buying/selling of goods or services, such as allocation rules and pricing rules 14
Auctions as Incentive No need to predict users demand: users reveal their true information through bids IEEE INFOCOM 2015, HONG KONG Balance among supply and demand Allocate available resources efficiently Obtain higher revenue 15
Research Problem How to design the auction mechanism for resource pooling from clients? For clients: get reasonable monetary return by selling resources (storage space & bandwidth) IEEE INFOCOM 2015, HONG KONG For CSPs: save cost (and overcome cloud outages) Assumption: the cost of providing service by datacenter herself is expensive than procuring resources from clients 16
Our Approach: Online Procurement Auctions Online auctions Procurement auctions Different bidders arrive at different times Auctioneer makes decision about each bid as it is received Different from the traditional case that the auctioneer receives all the bids before determining the allocation In line with asynchronous arrivals of user bids and requests Ordinary auctions (or forward auctions): one seller, multiple buyers Buyers compete IEEE INFOCOM 2015, HONG KONG Procurement auctions: one buyer, multiple sellers Sellers compete reverse auctions 17
Our Auction Model (I) Storage & bandwidth are unified as conceptual resource Needs further study IEEE INFOCOM 2015, HONG KONG Clients (i.e., bidders) want to sell resources through bids Bid: (starting time, ending time, amount, unit price) Valuation: the true value of the resource, private to the bidder Utility = the received payment - the cost of offering the sold resource Target: maximize utility 18
Our Auction Model (II) CSP (i.e., auctioneer ) wants to buy resources from some clients Set a target S for time period [0, T] For each incoming bid, determine how much to procure (allocation rule) how much to pay (payment rule) IEEE INFOCOM 2015, HONG KONG 19
Design Objectives If ( truthful bidding always maximizes utility ) Then ( rational bidders will report their true valuations ) Truthful IEEE INFOCOM 2015, HONG KONG The CSP s total cost is bounded by times of the total cost of offline optimal auction Competitive 20
Our Results Truthfulness We derive price-based allocation rule and payment rule that result in truthful auction mechanism. IEEE INFOCOM 2015, HONG KONG Competitiveness We find a solution to guarantee a target competitive ratio against offline optimal auctions. 21
Our Methodology Design marginal pricing function for CSP to achieve a desired competitive ratio IEEE INFOCOM 2015, HONG KONG Extend to the case of online procurement auction for divisible goods We first study the conditions for truthfulness of an online auction We then derive allocation and payment equations such that the auction mechanism is truthful. Start from Myerson s Principles of Truthfulness (1981) Gives two conditions to satisfy the truthfulness property For one single indivisible good 22
Conclusions We consider client-assisted a promising approach to addressing cloud outages. IEEE INFOCOM 2015, HONG KONG We argue that auctions can be a good incentive mechanism. We propose an online procurement auction mechanism, and prove its truthfulness and competitiveness. 23
A IEEE INFOCOM 2015, HONG KONG and 24
Myersons Principle of Truthfulness Consider the auction of a single indivisible good IEEE INFOCOM 2015, HONG KONG The auction mechanism is truthful if and only if The probability of a bidder winning an auction is monotonically non-decreasing in its bid The payment charged to a bidder is independent of its bid 25
Extension to Online Procurement Auctions We first define allocation monotonicity for online procurement auctions. IEEE INFOCOM 2015, HONG KONG Better bids get more allocation If allocation rule is monotone, we can find a payment rule that results in truthful online procurement auction. We design a monotone allocation rule and the corresponding payment rule. 26
Competitive Analysis Our auction mechanism assumes a non-increasing marginal pricing function for the CSP to procure resources from clients. The marginal pricing function is a variable IEEE INFOCOM 2015, HONG KONG How to minimize the total cost by adjusting the marginal pricing function? An online algorithm design problem We find a solution of setting the marginal pricing function to achieve a target competitive ratio. 27
