摘要
带宽预留正成为云计算中的增值服务.然而,不同于传统的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代表�
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., multi- dimensional 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 computation
作者
郑臻哲
吴帆
陈贵海
ZHENG Zhen-Zhe;Wu Fan;CHEN Gui-Hai(Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai 200240)
出处
《计算机学报》
EI
CSCD
北大核心
2019年第4期701-720,共20页
Chinese Journal of Computers
基金
国家"九七三"重点基础研究发展计划基金项目(2014CB340303)
国家自然科学基金项目(61672348
61672353
61472252)
上海市科学技术委员会基金项目(15220721300)资助~~
关键词
数据中心网络
云带宽预留
分布式系统
博弈论
拍卖理论
机制设计
data center networking
cloud bandwidth reservation
distributed system
game theory
auction theory
mechanism design
