广义的支配资源公平分配机制及其组合算法

Multidimensional resource fair allocation is a hot topic in recent years, as it has comprehensive applications in cloud computing. We will study several generalized versions of the dominant resource fairness mechanism, which is proposed by Ghodsi et al., from a theoretical perspective. Our first objective to generalize the dominant resource fairness mechanism to more general cases, including multiple servers, indivisible tasks, and dynamic setting. Our second objective is to design faster polynomial time combinatorial algorithms for the generalized dominant resource fairness mechanisms, by using the algorithm design techniques based on graph theory, network flow and mathematical programming, which are very different from the previous algorithms based on water-filling algorithm and linear programming. Our third objective is to analysis the approximation ratios of the generalized dominant resource fairness mechanisms or algorithms, using the .definition proposed recently. Finally, we will verify our theoretical results on YARN by using the google trace data.. We will publish at least 8 research papers with high quality on important publications, present theoretical foundation for mechanism design of multidimensional resource fair allocation, and cultivate at least 3 graduate students on algorithm and complexity or mechanism design.

因在云计算中的广泛应用，多维资源公平分配问题成为近年来的热点问题之一。 本项目拟针对Ghodsi教授等人提出的支配资源公平机制的广义形式进行理论分析。在机制设计方面，将重点分析设计多服务器、任务不可分或动态情形下广义的支配资源公平机制；在算法设计方面，不同于之前的water-filling算法和线性规划算法，将综合利用图论、网络流和数学规划理论等工具设计时间复杂性更低的多项式时间组合算法；在近似比分析方面，根据最近提出的机制近似比的定义，分析广义的支配资源公平机制或算法的近似比；在算法实现方面，在YARN平台上利用谷歌公司发布的实际数据进行仿真实验，验证理论分析的结果。. 预期在国内外重要刊物上发表8篇以上高质量的研究论文，为多维资源公平分配问题的机制设计提供理论基础，并培养算法及其复杂性或机制设计方面的研究生3 名以上。

广义的支配资源公平分配机制在Yarn平台和Mesos平台等资源管理平台得到了相对成熟的应用，但是现有机制在最坏情形下的性能分析是一个亟待解决的问题。同时现有算法绝大多数是基于注水思想，并非多项式时间算法。.. 经过四年的研究，本项目对支配资源公平分配机制最坏情形下的性能进行了严格的理论分析。当目标函数为资源利用率最大化时，证明了静态支配资源公平分配机制的近似比和动态支配资源公平分配机制的竞争比均为用户个数；当目标函数为社会福利最大化时，证明了静态支配资源公平分配机制的近似比为用户个数，且动态支配资源公平分配机制的竞争比为资源个数；当目标函数为最大化最小支配资源份额时，证明了动态支配资源公平分配机制的竞争比为资源个数。这意味着绝大多数广义的支配资源公平分配机制的近似比为竞争比为用户个数或资源个数，与其在不同数据集上的优异表现并不吻合。因此，提出新的衡量标准将是未来值得进一步研究的问题之一。.. 基于公开数据集的特点，提出了新的公平分配问题，设计了广义的支配资源公平机制，分析其公平性质。通过分析相应的数学规划形式得到若干重要的特性，采用二分法、阈值法和合并用户等技巧，提出了一些广义的支配资源公平分配机制的多项式时间组合算法，为相关机制的实现提供了更加有效的工具。将支配资源公平分配机制的算法思想融入以社会福利最大化为目标或以能效最大化为目标的资源分配模型，利用实验仿真的方式验证了该算法思想的优越性。同时，研究了多个相关的公平分配问题，提供了多项式时间近似算法或在线算法，丰富了理论计算机科学的内容。 .. 在本项目的资助下，研究论文在TPDS、《计算机研究与发展》、JPDC等国内外重要期刊或会议上发表。申请8项国家发明专利，并获授权1项。获省级自然科学奖励1项。两名学生获博士学位，并获省级优秀学位论文1项。