云化业务平台中基于博弈论的资源分配方法研究

发布时间：2018-07-03 20:00

本文选题：资源分配 + 价格比例　；参考：《北京邮电大学》2015年博士论文

【摘要】：互联网、尤其是移动互联网的普及,使得用户规模和应用种类急剧增加。在这种用户规模巨大以及衍生的高度动态情况下,传统服务平台无法满足用户的服务质量需求。这促使了云计算的出现和发展。云计算的高可靠性、高可用性以及弹性特点不仅保证了大规模用户的高质量服务,还降低了提供商的成本。另外,通过采用按需付费的方式,云计算降低了用户的成本。鉴于云计算的优势,科研机构和企业采用云计算技术改造现有的平台或应用。然而,云平台的资源分配问题是当前亟待解决的一个难题。不合理的资源分配方式不仅使得资源利用率低下,有时甚至难以满足应用的动态资源需求。已有的资源分配算法从系统或整体的角度最优化分配云计算资源。然而,云计算是一种基于效用的商业计算模式,提供商和用户之间及内部存在着复杂的竞争,提供商和用户根据竞争情况拥有各自的供给和需求策略。因此,基于博弈论的资源分配算法能够深入研究提供商和用户的策略,更加适合分析云计算资源的分配问题。虽然已有研究人员基于博弈论研究云计算资源分配问题,仍然存在着诸多挑战。需要一个不受用户数量限制的快速高效、可扩展的云计算资源分配算法；大规模的用户具有迥异的特征,使用多约束条件等方式无法准确描述用户的不同需求；大规模用户的随机加入和退出导致云环境高度动态变化,通过反复协商机制研究提供商和用户的均衡状态不可行；针对相互关联的复杂云服务,需要一个有效的服务部署策略。针对上述的局限性,本文基于博弈论研究了云计算资源的分配和服务的部署问题。主要包括：1.基于荷兰式拍卖的虚拟机分配算法。为了快速高效的分配虚拟机资源,提出了多实例荷兰式拍卖算法。该算法的拍卖时间与用户数量和虚拟机类型数目无关,更加适用于大规模的云计算虚拟机分配。另外,该算法中各个类型的虚拟机降价策略互不相干,使得该机制有着很好的可扩展性,易于分布式实现。提供商能够根据保留价格等因素决定拍卖的终止时间,实现社会总收益或自己收入的最大化。2.基于价格比例的计算型资源分配算法。为了实现CPU、内存等可分割资源的有效分配,我们采用基于SLA的效用函数描述不同经济能力用户申请的不同等级服务,并利用价格比例方法分配资源。这样,不仅实现了价值高的服务获得更多资源的价高者得方式的有效性,还保证了每个竞价者为单位资源支付相同的价格,保障了公平性。进一步的,考虑不同的使用场景,基于此算法提供了2种云资源分配机制。3.基于贪婪拍卖的带宽资源分配算法。分析传统的中心式和分布式网络资源分配机制的不足,基于贪婪拍卖提出了适用于任何需求类型(弹性、实时、阶梯式等)场景的多竞价贪婪拍卖机制,弥补了中心式和分布式机制的缺陷,适用于云计算网络资源分配。进一步的,考虑实际情况中用户需求类型基本为弹性需求的特点,提出了具有更少竞价通信消耗的多维度竞价贪婪拍卖机制。4.基于拥塞博弈的服务部署算法。考虑基于云的服务复杂且相互关联的特性,将云计算的服务部署问题转化为拥塞博弈问题。综合考虑服务的效率和成本,基于拥塞博弈模型实现云计算服务的优化部署。为了验证上述资源分配以及服务部署算法的有效性,本论文从分别从理论和实验的角度进行了分析。结果表明本文提出的资源分配以及服务部署算法具有很好的性能,能够快速高效的分配云计算资源,适用于大规模、高度动态、复杂的云环境中。
[Abstract]:The popularity of the Internet, especially the mobile Internet, has led to a sharp increase in the size and application of the user. In the large and highly dynamic conditions of the user, the traditional service platform is unable to meet the user's quality of service. This has prompted the emergence and development of cloud computing. The high reliability, high availability and bomb of the cloud computing. The characteristics not only guarantee high quality services for large users, but also reduce the cost of providers. In addition, cloud computing reduces the cost of users by paying on demand. In view of the advantages of cloud computing, research institutions and enterprises transform the existing platforms or applications by using cloud computing technology. However, the problem of resource allocation in cloud platforms. It is a difficult problem to be solved at present. The irrational allocation of resources not only makes the utilization of resources low, but sometimes even hard to meet the dynamic resource requirements of the application. The existing resource allocation algorithm optimally distributies cloud computing resources from the perspective of the system or the whole. However, the cloud computing is a utility based business computing model. There is a complex competition between providers and users. Providers and users have their own supply and demand strategies based on competition. Therefore, the game theory based resource allocation algorithm is able to study the strategy of providers and users, and is more suitable for the analysis of the distribution of cloud computing resources. There are still many challenges in the study of the distribution of cloud computing resources by game theory. It needs a fast, efficient and scalable algorithm of cloud computing resource allocation without the limit of the number of users; large users have different characteristics and can not accurately describe the different needs of the users by using multi constraint conditions. It is infeasible to study the equilibrium state of the providers and users through repeated negotiation mechanism, and it is not feasible to study the equilibrium state of the providers and users through repeated negotiation mechanism. For the interrelated complex cloud services, an effective service deployment strategy is needed. Based on the above limitations, this paper studies the Division of cloud computing resources allocation and service based on game theory. The main issues include: 1. virtual machine allocation algorithm based on Holland auction. In order to quickly and efficiently allocate virtual machine resources, a multi instance Holland auction algorithm is proposed. The auction time is independent of the number of users and the number of virtual machines, and it is more suitable for the large-scale cloud computing virtual machine allocation. In addition, the algorithm is used in the algorithm. Each type of virtual machine reduction strategy is not coherent, making the mechanism well extensible and easy to distribute. The provider can determine the termination time of the auction according to the factors such as the reservation price and realize the total social income or the maximum.2. based on the price ratio based computing resource allocation algorithm. In order to realize the CPU We use the utility function based on SLA to describe different levels of service with different economic capabilities and use the price ratio method to allocate resources. Unit resources pay the same price, ensuring fairness. Further, considering different usage scenarios, based on this algorithm, 2 kinds of cloud resource allocation mechanism.3. based on the greedy auction based bandwidth allocation algorithm are provided. The shortcomings of the traditional central and distributed network resource allocation system are analyzed, based on the greedy auction, the application of the algorithm is proposed. The multi bidding greedy auction mechanism of any demand type (elastic, real-time, staircase, etc.) makes up for the defects of the central and distributed mechanism, and is suitable for the allocation of cloud computing network resources. Further, considering the characteristics of the user demand type in the actual situation is basically elastic demand, the multidimensional consumption of less competitive communication is proposed. .4. based on congestion game based service deployment algorithm. Considering the complex and interrelated characteristics of cloud based services, the service deployment problem of cloud computing is transformed into a congestion game problem. The efficiency and cost of services are considered, and the optimal deployment of cloud computing service based on congestion game model is presented. The effectiveness of resource allocation and service deployment algorithm is discussed. This paper is analyzed from the theoretical and experimental points of view. The results show that the resource allocation and service deployment algorithm proposed in this paper have good performance, and can quickly and efficiently allocate cloud computing resources. It is suitable for large-scale, highly dynamic and complex cloud environments.
【学位授予单位】：北京邮电大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP393.09

【参考文献】