基于空间博弈的数据中心网络带宽分配与流量最优化调度算法研究

项目名称： 基于空间博弈的数据中心网络带宽分配与流量最优化调度算法研究

项目编号： No.61472365

项目类型： 面上项目

立项/批准年度： 2015

项目学科： 自动化技术、计算机技术

项目作者： 魏贵义

作者单位： 浙江工商大学

项目金额： 82万元

中文摘要： 数据中心网络带宽分配的性能保证、带宽高效利用、带宽分配的公平性问题已成为云计算中一个迫切需要解决重要问题。这个问题直接影响云计算资源利用、租户应用的性能和租户的成本。已有的研究不能提供最小带宽保证、资源充分利用、可预测性和公平性保证。本项目基于数据中心网络租户网络流量的动态性，采用动态演化博弈方法设计带宽分配策略，研究具有动态最小带宽保证、资源充分利用、可预测性和公平性的数据中心网络带宽分配策略。设计带宽效用一致性和非一致性两种情况下的空间演化博弈模型，研究带宽效用一致性下带宽分配博弈的演化动力学规律、带宽效用一致性下的演化动力学规律与拥塞抑制。并在此基础上，设计一个VM数据传输最优化的FPTAS近似算法，实现VM网络流量平均延时最优化调度。

中文关键词： 云计算；数据中心网络；资源共享；资源调度；服务质量

英文摘要： Network performance guarantee, high utilization and fairness of in-network bandwidth allocation in cloud networks are an important problem for both cloud provider and tenant. Bandwidth allocation in cloud network largely affects the efficiency of cloud resource utilization, the performance of cloud applications and tenant's cost. The existed work in this area can't fulfill the four metrics both cloud provider and tenant concerned: minimum guarantee, high utilization, fairness and predictability, simultaneously. This project aimed to solve the problem by using spatial game model. Based on the temporal and spatial characteristic of VM's traffic, we design an evolutionary game model to feature the competition and cooperation in the process of dynamical bandwidth allocation. First, we design a spatial evolutionary game model to investigatethe dynamical process of bandwidth allocation with homogeneous bandwidth-utility. Second, we design another spatial evolutionary game model for bandwidth allocation with heterogeneous bandwidth-utility. In home- and heter- models, we study their evolution dynamics, convergence and convergent efficiency.By using proper parameter design, we discuss the network performance of the proposed models, including dynamical minimum bandwidth guarantee, high utilization, fairness and predictability. In addition, we also study the congestion constraint effect ofthe heter-model. Finally, we analyze the complexity of traffic scheduling in VM end with predictable bandwidth provision, prove the traffic scheduling is a NP-hard problem under specified constrains, and try to design an FPTAS approximate algorithm for the problem. The objective is to achieve the approximate optimum of average delay for VM's traffic.

英文关键词： Cloud Computing;Data Center Network;Network Bandwidth Sharing;Scheduling;Quality of Service