多维度防策略性云带宽预留拍卖机制设计
|
摘要
带宽预留正成为云计算中的增值服务.然而,不同于传统的CPU或存储资源,数据中心网络的带宽资源还没有被高效地分配与利用.现有云带宽资源大都采用现用现付(pay-as-you-go)的形式进行售卖,云带宽用户通过竞争来使用带宽资源,导致数据传输没有性能保证.带宽预留服务还未在现有云计算产业中得到部署.在该论文中,作者考虑在开放拍卖市场中,云服务提供商和云带宽用户之间的带宽交易问题.设计一个贴近实际的云带宽预留拍卖需要克服三大难点:理性(自私)用户的多维度策略行为、多样化云带需求模型和最优社会效益求解的复杂性.在云带宽市场中,云用户拥有多个维度私有信息,比如带宽资源估值、带宽资源需求量和感兴趣的数据中心.这使得云用户具有更强大的市场操控能力.在多样的云应用中,为了支持时延敏感的数据传输或是严格时限的数据传输,云带宽用户会有不同的带宽预留需求.云带宽预留分配问题可以建模成多种不同的组合优化问题.这些组合优化问题通常是NP-难的,因此无法在有效的时间内求得最优解.综合考虑这些设计难点,作者提出首个防策略性云带宽预留拍卖机制,称为SPAR(Strategy-Proof Auction mechanisms for cloud bandwidth Reservation)机制.SPAR机制包括三个拍卖机制SPAR-VCG,SPAR-APX和SPAR-GDY,以支持不同带宽需求模型下的带宽分配.当云带宽用户能够接受被分配到的部分带宽资源,可以采用作者提出SPAR-VCG机制来实现防策略性,并在多项式时间内达到最优社会福利.SPAR-VCG机制的设计结合了线性规划求解模型和传统的VCG机制设计方法.当云带宽用户对于每个感兴趣的数据中心有严格的带宽需求,考虑到最优带宽分配方法求解的复杂性,作者设计了SPAR-APX机制,同样能够实现防策略性并达到近似最优社会福利.理论分析指出SPAR-APX机制的近似比是■,其中B代表数据中心的总带宽.作者还证明了该近似比是所有贪心分配算法所能达到的最优近似比.针对于另外一个更普适的带宽需求场景:用户对于感兴趣数据中心有总的带宽需求但是对于每个感兴趣的数据中心却没有严格带宽需求,作者设计了基于贪心策略的带宽分配方案:SPAR-GDY机制.SPAR-GDY机制能够保证两个维度的防策略性,并且在实际环境中都能达到较好社会福利.作者同时还说明了在该灵活带宽需求模型下要保证三个维度的防策略性和近似比保证的困难性.作者实现了这三个带宽拍卖预留机制,并且用大规模仿真实验来衡量机制性能.相比于现有的工作,SPAR机制在社会福利、收益、满意度和带宽利用率上都能够达到更优的系统性能,并且在小规模的云带宽市场中接近最优解.该论文中所提出的拍卖机制也能够用于分配其他类型的云带宽资源,比如处理器运行时间和存储空间等.
Bandwidth reservation is becoming a value-added feature for cloud computing services.However,in contrast to CPU or storage resources,bandwidth resource in data-center networks has not been efficiently allocated.The current cloud bandwidth is sold in a pay-as-you-go way.The cloud tenants compete for using the bandwidth resources,resulting in the unpredictable performance in data transportation.The bandwidth reservation services have not been deployed in cloud computing industry.In this paper,we consider bandwidth resource trading between a cloud provider and multiple cloud tenants in an open auction-based market.Designing practical auction mechanisms for bandwidth reservation has to overcome three major challenges:i.e.,multidimensional strategic behaviors,flexible bandwidth demands,and high computational complexity.In cloud bandwidth markets,cloud tenants have multiple private parameters:bandwidth valuation,bandwidth demand and the preference on data centers,making the cloud tenants have much power to manipulate the market.In diverse cloud applications,tenants may have flexible bandwidth reservation demands,to support delay-sensitive transportation or strict deadline transportation.The cloud bandwidth allocation can be modeled as different types of combinatorial optimization problem,which is NP-Hard in general,and thus it is computationally intractable to derivate the optimal solution.Jointly considering these three challenges,we propose the first family of multi-dimensional Strategy-Proof Auction mechanisms for cloud bandwidth Reservation(SPAR).SPAR contains three auction mechanisms:SPAR-VCG,SPAR-APX and SPAR-GDY,to support different types of bandwidth demand models.First,we present SPAR-VCG that achieves both strategy-proofness and optimal social welfare in polynomial time,when tenants accept partially filled bandwidth demands.The SPAR-VCG mechanism is an integration of a linear programming solving module and the traditional VCG mechanism.Then,considering the computational intractability of the optimal solution for the general bandwidth demand model,we propose SPAR-APX that guarantees strategy-proofness and achieves approximate social welfare for the scenario that tenants have strict requirements on the amount of bandwidth reserved on each of data centers.Our theoretical analysis shows that the approximation ratio of SPAR-APX is ■,where Bis the total bandwidth capacity of all data centers.We also prove that this approximation ratio is tight for all greedy-based allocation algorithms.Furthermore,we propose a greedy-based auction mechanism SPAR-GDY for an important and general case,in which cloud tenants only have a strict requirement on the total bandwidth from their preferred data centers but do not have strict bandwidth requirement on each of preferred data centers.SPAR-GDY can guarantee the property of strategy-proofness in two private parameters and achieves good social welfare in most practical cases.We also demonstrate the hardness to achieve strategy-proofness for all the three private parameters,and good approximation ratio in this flexible bandwidth demand model.We implement these three auction mechanisms,and extensively evaluate the performance of them using network simulation.Our simulation results show that SPAR achieve good performance in terms of social welfare,tenant satisfaction ratio and bandwidth utilization,and approach to the optimal social welfare in the small-scale cloud market.The auction mechanisms proposed in this paper can also be applied to allocate other kinds of divisible cloud resources subjecting to specific constraints(e.g.,processor times and storage space).
Bandwidth reservation is becoming a value-added feature for cloud computing services.However,in contrast to CPU or storage resources,bandwidth resource in data-center networks has not been efficiently allocated.The current cloud bandwidth is sold in a pay-as-you-go way.The cloud tenants compete for using the bandwidth resources,resulting in the unpredictable performance in data transportation.The bandwidth reservation services have not been deployed in cloud computing industry.In this paper,we consider bandwidth resource trading between a cloud provider and multiple cloud tenants in an open auction-based market.Designing practical auction mechanisms for bandwidth reservation has to overcome three major challenges:i.e.,multidimensional strategic behaviors,flexible bandwidth demands,and high computational complexity.In cloud bandwidth markets,cloud tenants have multiple private parameters:bandwidth valuation,bandwidth demand and the preference on data centers,making the cloud tenants have much power to manipulate the market.In diverse cloud applications,tenants may have flexible bandwidth reservation demands,to support delay-sensitive transportation or strict deadline transportation.The cloud bandwidth allocation can be modeled as different types of combinatorial optimization problem,which is NP-Hard in general,and thus it is computationally intractable to derivate the optimal solution.Jointly considering these three challenges,we propose the first family of multi-dimensional Strategy-Proof Auction mechanisms for cloud bandwidth Reservation(SPAR).SPAR contains three auction mechanisms:SPAR-VCG,SPAR-APX and SPAR-GDY,to support different types of bandwidth demand models.First,we present SPAR-VCG that achieves both strategy-proofness and optimal social welfare in polynomial time,when tenants accept partially filled bandwidth demands.The SPAR-VCG mechanism is an integration of a linear programming solving module and the traditional VCG mechanism.Then,considering the computational intractability of the optimal solution for the general bandwidth demand model,we propose SPAR-APX that guarantees strategy-proofness and achieves approximate social welfare for the scenario that tenants have strict requirements on the amount of bandwidth reserved on each of data centers.Our theoretical analysis shows that the approximation ratio of SPAR-APX is ■,where Bis the total bandwidth capacity of all data centers.We also prove that this approximation ratio is tight for all greedy-based allocation algorithms.Furthermore,we propose a greedy-based auction mechanism SPAR-GDY for an important and general case,in which cloud tenants only have a strict requirement on the total bandwidth from their preferred data centers but do not have strict bandwidth requirement on each of preferred data centers.SPAR-GDY can guarantee the property of strategy-proofness in two private parameters and achieves good social welfare in most practical cases.We also demonstrate the hardness to achieve strategy-proofness for all the three private parameters,and good approximation ratio in this flexible bandwidth demand model.We implement these three auction mechanisms,and extensively evaluate the performance of them using network simulation.Our simulation results show that SPAR achieve good performance in terms of social welfare,tenant satisfaction ratio and bandwidth utilization,and approach to the optimal social welfare in the small-scale cloud market.The auction mechanisms proposed in this paper can also be applied to allocate other kinds of divisible cloud resources subjecting to specific constraints(e.g.,processor times and storage space).
引文
[1]Adhikari V K,Guo Y,Hao F,et al.Unreeling Netflix:Understanding and improving multi-CDN movie delivery//Proceedings of the 31st Annual IEEE International Conference on Computer Communications(INFOCOM).Orlando,USA,2012:1620-1628
[2]Ballani H,Costa P,Karagiannis T,et al.Towards predictable datacenter networks//Proceedings of the ACM SIGCOMMConference on Applications,Technologies,Architectures,and Protocols for Computer Communications(SIGCOMM).Toronto,Canada,2011:242-253
[3]Guo C,Lu G,Wang H J,et al.SecondNet:A data center network virtualization architecture with bandwidth guarantees//Proceedings of the 6th International Conference(Co-NEXT).Philadelphia,USA,2010:15:1-15:12
[4]Jalaparti V,Bliznets I,Kandula S,et al.Dynamic pricing and traffic engineering for timely inter-datacenter transfers//Proceedings of the ACM SIGCOMM Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications(SIGCOMM).Florianopolis,Brazil,2016:73-86
[5]Branco F.The design of multidimensional auctions.The RAND Journal of Economics,1997,28(1):63-81
[6]Cai Y,Daskalakis C,Weinberg S M.Optimal multidimensional mechanism design:Reducing revenue to welfare maximization//Proceedings of the 53rd Annual Symposium on Foundations of Computer Science(FOCS).New Brunswick,USA,2012:130-139
[7]Kellerer H,Pferschy U,Pisinger D.Knapsack Problems.New York,USA:Springer,2004
[8]Vickrey W.Counterspeculation,auctions,and competitive sealed tenders.The Journal of Finance,1961,16(1):8-37
[9]Clarke E H.Multipart pricing of public goods.Public choice,1971,11(1):17-33
[10]Groves T.Incentives in teams.Econometrica:Journal of the Econometric Society,1973,41(4):617-631
[11]Niu D,Feng C,Li B.Pricing cloud bandwidth reservations under demand uncertainty//Proceedings of the Joint International Conference on Measurement and Modeling of Computer Systems(SIGMETRICS).London,UK,2012:151-162
[12]Liu F,Guo J,Huang X,et al.eBA:Efficient bandwidth guarantee under traffic variability in datacenters.IEEE/ACM Transactions on Networking,2017,25(1):506-519
[13]Guo J,Liu F,Huang X,et al.On efficient bandwidth allocation for traffic variability in datacenters//Proceedings of the 33rd Annual IEEE International Conference on Computer Communications(INFOCOM).Toronto,Canada,2014:1572-1580
[14]Guo J,Liu F,Lui J C,et al.Fair network bandwidth allocation in IaaS datacenters via a cooperative game approach.IEEE/ACM Transactions on Networking,2016,24(2):873-886
[15]Guo J,Liu F,Tang H,et al.Falloc:Fair network bandwidth allocation in iaas datacenters via a bargaining game approach//Proceedings of the 21st IEEE International Conference on Network Protocols(ICNP).Goettingen,Germany,2013:1-10
[16]Wang W,Li B,Liang B.Towards optimal capacity segmentation with hybrid cloud pricing//Proceedings of the 33rd International Conference on Distributed Computing Systems(ICDCS).Philadelphia,USA,2012:425-434
[17]Wang Q,Ren K,Meng X.When cloud meets eBay:Towards effective pricing for cloud computing//Proceedings of the31st Annual IEEE International Conference on Computer Communications(INFOCOM).Orlando,USA,2012:936-944
[18]Zhou X,Gandhi S,Suri S,et al.Ebay in the sky:Strategyproof wireless spectrum auctions//Proceedings of the 14th International Conference on Mobile Computing and Networking(MobiCom).San Francisco,USA,2008:2-13
[19]Zhou X,Zheng H.TRUST:A general framework for truthful double spectrum auctions//Proceedings of the 28th Annual IEEE Conference on Computer Communications(INFOCOM).Rio de Janeiro,Brazil,2009:999-1007
[20]Kelly F P,Maulloo A K,Tan D K H.Rate control for communication networks:Shadow prices,proportional fairness and stability.Journal of the Operational Research Society,1998,49(3):237-252
[21]Srikant R.The mathematics of Internet congestion control.Cambridge,UK:Birkhauser,2004
[22]Acemoglu D,Ozdaglar A,Srikant R.The marginal user principle for resource allocation in wireless networks//Proceedings of the 43rd IEEE Conference on Decision and Control(CDC).Nassau,Bahamas,2004:1544-1549
[23]■ T,Srikant R.Revenue-maximizing pricing and capacity expansion in a many-users regime//Proceedings of the 21st Annual IEEE Conference on Computer Communications(INFOCOM).New York,USA,2002:294-301
[24]■ T,Srikant R.A Stackelberg network game with a large number of followers.Journal of Optimization Theory and Applications,2002,115(3):479-490
[25]Guo J,Liu F,Wang T,et al.Pricing intra-datacenter networks with over-committed bandwidth guarantee//Proceedings of the 2017USENIX Conference on USENIX Annual Technical Conference(ATC).Santa Clara,USA,2017:69-81
[26]Zheng Z,Srikant R,Chen G.Pricing for revenue maximization in inter-datacenter networks//Proceedings of the 37th Annual IEEE Conference on Computer Communications(INFOCOM).Honolulu,USA,2018:28-36
[27]Yuan S,Wang J,Zhao X.Real-time bidding for online advertising:Measurement and analysis//Proceedings of the Seventh International Workshop on Data Mining for Online Advertising.Chicago,USA,2013:1-8
[28]Zheng L,Joe-Wong C,Tan C W,et al.How to bid the cloud//Proceedings of the ACM SIGCOMM Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications(SIGCOMM).London,UK,2015:71-84
[29]Lam V T,Radhakrishnan S,Pan R,et al.NetShare and stochastic NetShare:Predictable bandwidth allocation for data centers.SIGCOMM Computer Communication Review,2012,42(3):5-11
[30]Popa L,Yalagandula P,Banerjee S,et al.Practical workconserving bandwidth guarantees for cloud computing//Proceedings of the ACM SIGCOMM Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications(SIGCOMM).Hong Kong,China,2013:351-362
[31]Li L,Liu K,Fu B,et al.Isolating bandwidth guarantees from work conservation in the cloud//Proceedings of the 21st IEEE Symposium on Computers and Communication(ISCC).Messina,Italy,2016:926-931
[32]Hu S,Bai W,Chen K,et al.Providing bandwidth guarantees,work conservation and low latency simultaneously in the cloud//Proceedings of the 35th Annual IEEE Conference on Computer Communications(INFOCOM).San Francisco,USA,2016:1-9
[33]Jain S,Kumar A,Mandal S,et al.B4:Experience with a globally-deployed software defined WAN//Proceedings of the ACM SIGCOMM Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications(SIGCOMM).Hong Kong,China,2013:3-14
[34]Hong C-Y,Kandula S,Mahajan R,et al.Achieving high utilization with software-driven WAN//Proceedings of the ACM SIGCOMM Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications(SIGCOMM).Hong Kong,China,2013:15-26
[35]Zhang H,Jiang H,Li B,et al.A framework for truthful online auctions in cloud computing with heterogeneous user demands.IEEE Transactions on Computers,2016,65(3):805-818
[36]Yi X,Liu F,Li Z,et al.Flexible instance:Meeting deadlines of delay tolerant jobs in the cloud with dynamic pricing//Proceedings of the 36th International Conference on Distributed Computing Systems(ICDCS).Nara,Japan,2016:415-424
[37]Yi X,Liu F,Niu D,et al.Cocoa:Dynamic container-based group buying strategies for cloud computing.ACM Transactions on Modeling and Performance Evaluation of Computing Systems,2017,2(2):8:1-8:31
[38]Wang M,Cui Y,Wang X,et al.Machine learning for networking:Workflow,advances and opportunities.IEEENetwork,2018,32(2):92-99
[39]Wang T,Liu F,Xu H.An efficient online algorithm for dynamic SDN controller assignment in data center networks.IEEE/ACM Transactions on Networking,2017,25(5):2788-2801
[40]Gui Y,Zheng Z,Wu F,et al.SOAR:Strategy-proof auction mechanisms for distributed cloud bandwidth reservation//Proceedings of the IEEE International Conference on Communication Systems(ICCS).Macau,China,2014:162-166
[41]Osborne M J,Rubenstein A.A Course in Game Theory.London,UK:MIT Press,1994
[42]Myerson R B.Optimal auction design.Mathematics of Operations Research,1981,6(1):58-73
[43]Puchinger J,Raidl G R,Pferschy U.The multidimensional knapsack problem:structure and algorithms.INFORMSJournal on Computing,2010,22(2):250-265
[44]Gens G,Levner E.Complexity of approximation algorithms for combinatorial problems:A survey.ACM Special Interest Group on Algorithms and Computation Theory(SIGACT)News,1980,12(3):52-65
(1)我们在SPAR名称后面添加后缀来表示三个不同模型下相应的机制.第一个机制是基于经济学经典机制VCG,故称为SPAR-VCG,第二个机制是基于近似算法(Approximation Algorithm),故称为SPAR-APX,第三个机制是基于贪心算法(Greedy Algorithm),所以记为SPAR-GDY.
(1)亚马逊云平台AWS运营着总共55个逻辑区域,分布于全球18个物理区域(regions):https://aws.amazon.com/aboutaws/global-infrastructure/.Google的GCP云平台运营着52个逻辑区域,分布于17个物理区域https://cloud.google.com/about/locations/#locations.微软Azure平台将数据中心部署在全球54个区域中https://azure.microsoft.com/en-us/global-infrastructure/regions/.
(1)亚马逊云数据中心全球位置分布:https://aws.amazon.com/about-aws/global-infrastructure/.
(2)Google云数据中心全球位置分布:https://cloud.google.com/about/l.
(3)微软云数据中心全球位置分布:https://azure.microsoft.com/en-us/global-infrastructure/regions/.
(4)我们的实验参数,包括数据中心的数目和用户数量等也可以取不同的数值.在不同的实验参数设定下,我们能够得到的实验结果具有类似的趋势,揭示了相同的实验规律.因此,我们这里仅展示这些特定参数下的实验结果来说明我们机制的性能.
[2]Ballani H,Costa P,Karagiannis T,et al.Towards predictable datacenter networks//Proceedings of the ACM SIGCOMMConference on Applications,Technologies,Architectures,and Protocols for Computer Communications(SIGCOMM).Toronto,Canada,2011:242-253
[3]Guo C,Lu G,Wang H J,et al.SecondNet:A data center network virtualization architecture with bandwidth guarantees//Proceedings of the 6th International Conference(Co-NEXT).Philadelphia,USA,2010:15:1-15:12
[4]Jalaparti V,Bliznets I,Kandula S,et al.Dynamic pricing and traffic engineering for timely inter-datacenter transfers//Proceedings of the ACM SIGCOMM Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications(SIGCOMM).Florianopolis,Brazil,2016:73-86
[5]Branco F.The design of multidimensional auctions.The RAND Journal of Economics,1997,28(1):63-81
[6]Cai Y,Daskalakis C,Weinberg S M.Optimal multidimensional mechanism design:Reducing revenue to welfare maximization//Proceedings of the 53rd Annual Symposium on Foundations of Computer Science(FOCS).New Brunswick,USA,2012:130-139
[7]Kellerer H,Pferschy U,Pisinger D.Knapsack Problems.New York,USA:Springer,2004
[8]Vickrey W.Counterspeculation,auctions,and competitive sealed tenders.The Journal of Finance,1961,16(1):8-37
[9]Clarke E H.Multipart pricing of public goods.Public choice,1971,11(1):17-33
[10]Groves T.Incentives in teams.Econometrica:Journal of the Econometric Society,1973,41(4):617-631
[11]Niu D,Feng C,Li B.Pricing cloud bandwidth reservations under demand uncertainty//Proceedings of the Joint International Conference on Measurement and Modeling of Computer Systems(SIGMETRICS).London,UK,2012:151-162
[12]Liu F,Guo J,Huang X,et al.eBA:Efficient bandwidth guarantee under traffic variability in datacenters.IEEE/ACM Transactions on Networking,2017,25(1):506-519
[13]Guo J,Liu F,Huang X,et al.On efficient bandwidth allocation for traffic variability in datacenters//Proceedings of the 33rd Annual IEEE International Conference on Computer Communications(INFOCOM).Toronto,Canada,2014:1572-1580
[14]Guo J,Liu F,Lui J C,et al.Fair network bandwidth allocation in IaaS datacenters via a cooperative game approach.IEEE/ACM Transactions on Networking,2016,24(2):873-886
[15]Guo J,Liu F,Tang H,et al.Falloc:Fair network bandwidth allocation in iaas datacenters via a bargaining game approach//Proceedings of the 21st IEEE International Conference on Network Protocols(ICNP).Goettingen,Germany,2013:1-10
[16]Wang W,Li B,Liang B.Towards optimal capacity segmentation with hybrid cloud pricing//Proceedings of the 33rd International Conference on Distributed Computing Systems(ICDCS).Philadelphia,USA,2012:425-434
[17]Wang Q,Ren K,Meng X.When cloud meets eBay:Towards effective pricing for cloud computing//Proceedings of the31st Annual IEEE International Conference on Computer Communications(INFOCOM).Orlando,USA,2012:936-944
[18]Zhou X,Gandhi S,Suri S,et al.Ebay in the sky:Strategyproof wireless spectrum auctions//Proceedings of the 14th International Conference on Mobile Computing and Networking(MobiCom).San Francisco,USA,2008:2-13
[19]Zhou X,Zheng H.TRUST:A general framework for truthful double spectrum auctions//Proceedings of the 28th Annual IEEE Conference on Computer Communications(INFOCOM).Rio de Janeiro,Brazil,2009:999-1007
[20]Kelly F P,Maulloo A K,Tan D K H.Rate control for communication networks:Shadow prices,proportional fairness and stability.Journal of the Operational Research Society,1998,49(3):237-252
[21]Srikant R.The mathematics of Internet congestion control.Cambridge,UK:Birkhauser,2004
[22]Acemoglu D,Ozdaglar A,Srikant R.The marginal user principle for resource allocation in wireless networks//Proceedings of the 43rd IEEE Conference on Decision and Control(CDC).Nassau,Bahamas,2004:1544-1549
[23]■ T,Srikant R.Revenue-maximizing pricing and capacity expansion in a many-users regime//Proceedings of the 21st Annual IEEE Conference on Computer Communications(INFOCOM).New York,USA,2002:294-301
[24]■ T,Srikant R.A Stackelberg network game with a large number of followers.Journal of Optimization Theory and Applications,2002,115(3):479-490
[25]Guo J,Liu F,Wang T,et al.Pricing intra-datacenter networks with over-committed bandwidth guarantee//Proceedings of the 2017USENIX Conference on USENIX Annual Technical Conference(ATC).Santa Clara,USA,2017:69-81
[26]Zheng Z,Srikant R,Chen G.Pricing for revenue maximization in inter-datacenter networks//Proceedings of the 37th Annual IEEE Conference on Computer Communications(INFOCOM).Honolulu,USA,2018:28-36
[27]Yuan S,Wang J,Zhao X.Real-time bidding for online advertising:Measurement and analysis//Proceedings of the Seventh International Workshop on Data Mining for Online Advertising.Chicago,USA,2013:1-8
[28]Zheng L,Joe-Wong C,Tan C W,et al.How to bid the cloud//Proceedings of the ACM SIGCOMM Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications(SIGCOMM).London,UK,2015:71-84
[29]Lam V T,Radhakrishnan S,Pan R,et al.NetShare and stochastic NetShare:Predictable bandwidth allocation for data centers.SIGCOMM Computer Communication Review,2012,42(3):5-11
[30]Popa L,Yalagandula P,Banerjee S,et al.Practical workconserving bandwidth guarantees for cloud computing//Proceedings of the ACM SIGCOMM Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications(SIGCOMM).Hong Kong,China,2013:351-362
[31]Li L,Liu K,Fu B,et al.Isolating bandwidth guarantees from work conservation in the cloud//Proceedings of the 21st IEEE Symposium on Computers and Communication(ISCC).Messina,Italy,2016:926-931
[32]Hu S,Bai W,Chen K,et al.Providing bandwidth guarantees,work conservation and low latency simultaneously in the cloud//Proceedings of the 35th Annual IEEE Conference on Computer Communications(INFOCOM).San Francisco,USA,2016:1-9
[33]Jain S,Kumar A,Mandal S,et al.B4:Experience with a globally-deployed software defined WAN//Proceedings of the ACM SIGCOMM Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications(SIGCOMM).Hong Kong,China,2013:3-14
[34]Hong C-Y,Kandula S,Mahajan R,et al.Achieving high utilization with software-driven WAN//Proceedings of the ACM SIGCOMM Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications(SIGCOMM).Hong Kong,China,2013:15-26
[35]Zhang H,Jiang H,Li B,et al.A framework for truthful online auctions in cloud computing with heterogeneous user demands.IEEE Transactions on Computers,2016,65(3):805-818
[36]Yi X,Liu F,Li Z,et al.Flexible instance:Meeting deadlines of delay tolerant jobs in the cloud with dynamic pricing//Proceedings of the 36th International Conference on Distributed Computing Systems(ICDCS).Nara,Japan,2016:415-424
[37]Yi X,Liu F,Niu D,et al.Cocoa:Dynamic container-based group buying strategies for cloud computing.ACM Transactions on Modeling and Performance Evaluation of Computing Systems,2017,2(2):8:1-8:31
[38]Wang M,Cui Y,Wang X,et al.Machine learning for networking:Workflow,advances and opportunities.IEEENetwork,2018,32(2):92-99
[39]Wang T,Liu F,Xu H.An efficient online algorithm for dynamic SDN controller assignment in data center networks.IEEE/ACM Transactions on Networking,2017,25(5):2788-2801
[40]Gui Y,Zheng Z,Wu F,et al.SOAR:Strategy-proof auction mechanisms for distributed cloud bandwidth reservation//Proceedings of the IEEE International Conference on Communication Systems(ICCS).Macau,China,2014:162-166
[41]Osborne M J,Rubenstein A.A Course in Game Theory.London,UK:MIT Press,1994
[42]Myerson R B.Optimal auction design.Mathematics of Operations Research,1981,6(1):58-73
[43]Puchinger J,Raidl G R,Pferschy U.The multidimensional knapsack problem:structure and algorithms.INFORMSJournal on Computing,2010,22(2):250-265
[44]Gens G,Levner E.Complexity of approximation algorithms for combinatorial problems:A survey.ACM Special Interest Group on Algorithms and Computation Theory(SIGACT)News,1980,12(3):52-65
(1)我们在SPAR名称后面添加后缀来表示三个不同模型下相应的机制.第一个机制是基于经济学经典机制VCG,故称为SPAR-VCG,第二个机制是基于近似算法(Approximation Algorithm),故称为SPAR-APX,第三个机制是基于贪心算法(Greedy Algorithm),所以记为SPAR-GDY.
(1)亚马逊云平台AWS运营着总共55个逻辑区域,分布于全球18个物理区域(regions):https://aws.amazon.com/aboutaws/global-infrastructure/.Google的GCP云平台运营着52个逻辑区域,分布于17个物理区域https://cloud.google.com/about/locations/#locations.微软Azure平台将数据中心部署在全球54个区域中https://azure.microsoft.com/en-us/global-infrastructure/regions/.
(1)亚马逊云数据中心全球位置分布:https://aws.amazon.com/about-aws/global-infrastructure/.
(2)Google云数据中心全球位置分布:https://cloud.google.com/about/l.
(3)微软云数据中心全球位置分布:https://azure.microsoft.com/en-us/global-infrastructure/regions/.
(4)我们的实验参数,包括数据中心的数目和用户数量等也可以取不同的数值.在不同的实验参数设定下,我们能够得到的实验结果具有类似的趋势,揭示了相同的实验规律.因此,我们这里仅展示这些特定参数下的实验结果来说明我们机制的性能.