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

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.

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

数据中心网络带宽分配的性能保证、带宽高效利用、带宽分配的公平性问题已成为云计算中一个迫切需要解决重要问题。这个问题直接影响云计算资源利用、租户应用的性能和租户的成本。已有的研究不能提供最小带宽保证、资源充分利用、可预测性和公平性保证。本项目基于数据中心网络租户网络流量的动态性，采用动态演化博弈方法设计带宽分配策略，研究具有动态最小带宽保证、资源充分利用、可预测性和公平性的数据中心网络带宽分配策略。设计带宽效用一致性和非一致性两种情况下的空间演化博弈模型，研究带宽效用一致性下带宽分配博弈的演化动力学规律、带宽效用一致性下的演化动力学规律。在此基础上进一步研究具有多完成时间窗指派的组依赖的网络带宽调度问题，以及数据中心涉及资源调度的信息安全与隐私机制中的高强度配对计算等问题。我们将上述调度问题抽象为一个具有多完成时间窗指派的组依赖调度问题，将可用时空概念上的带宽资源需求按照相似性划分多个组，同组的任务（带宽指派）按照时间序列进行分配，每个组具有多个组依赖的完成时间窗口。在给定的任务数（带宽需求），我们将优化目标定为最小化时间成本。我们设计优化算法时间复杂度只有$O(nlogn)$。更进一步，但每个组的任务数是不确定的时候，我们设计类复杂度只有$O(n_B\logn)$求解算法,其中$B=max\{h_i – 1\}$。这是目前该类问题的最优解决方案，即最小的时间复杂度算法。本项目计划要点均按照计划完成。本项目执行4年以来，共发表/录用论文12篇，SCI检索9篇，EI检索12篇，其中属于中国计算机协会推荐会议期刊A类的有1篇，B类的有2篇，C类的有4篇，已超额完成本项目预期研究成果SCI/EI检索论文8-10篇。