多维度防策略性云带宽预留拍卖机制设计

带宽预留正成为云计算中的增值服务.然而,不同于传统的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机制在社会福利、收益、满意度和带宽利用率上都能够达到更优的系统性能,并且在小规模的云带宽市场中接近最优解.该论文中所提出的拍卖机制也能够用于分配其他类型的云带宽资源,比如处理器运行时间和存储空间等.

On Designing Multi-Dimensional Strategy-Proof Auctions for Distributed Cloud Bandwidth Reservation

ZHENG Zhen-Zhe;Wu Fan;CHEN Gui-Hai(Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai 200240)