云计算环境下的自主调度技术研究

发布时间：2018-10-08 09:22

【摘要】：云计算是信息技术革命的产物,是一种大规模复杂计算系统。云计算系统时刻都在处理海量数据和应用任务,具有高度的动态性。由于云计算系统具有资源规模庞大且异构多样、用户群体广泛、应用任务类型各异且QoS目标约束各异等特性,系统需要频繁地对云平台中的各种资源与应用任务进行实时调度和动态管理。而云计算作为一种商业计算模式,其目的是实现资源共享与协同工作,并同时满足用户的服务请求和云服务提供商的服务收益。因此,如何对云资源进行合理的分配,对海量应用任务进行高效管理与实时调度,在确保云计算系统负载均衡和提高云资源利用率的前提下,降低用户的成本,提高云服务提供商的收益,是目前云计算环境下的研究热点之一。从本质上说,云计算环境下的任务调度是需要建立一种应用任务与计算资源之间合适的映射关系的调度策略,其目的是实现计算资源的合理分配与应用任务的高效执行。早期传统的分布式计算系统、网格计算系统等,通过系统吞吐量和任务完成时间等性能指标衡量调度管理的效果。但是在云计算环境下,任务调度问题往往更加复杂。首先,云计算环境下应用任务请求往往是非集中式的,而且规模巨大,传统的集中式的资源管理系统已经不再适用,云计算系统必须以一种分布式的并行模式对任务和资源进行调度与管理;其次,云资源通常来自不同的云服务提供商,各个机构的云资源往往是异构的,如何将各种异构资源组合成完整的服务提供给用户是非常复杂的;再者,由于云计算系统具有动态可扩展的性质,相应的任务调度也必须满足可扩展性与自适应性;然后,云计算作为一种商业模式,云服务提供商首先要考虑的是如何提高自身的资源利用率,提升共享使用率从而降低成本,获得尽可能多的服务收益,这就使得任务调度必须考虑云计算系统的整体负载均衡问题。最后,从用户的角度而言,云服务提供商所提供的服务是否满足用户任务调度的QoS多目标需求是任务调度策略必须考虑的问题。因此,针对上述目前云计算环境下任务调度存在的问题,本文对云环境下的任务调度技术做了详细而系统的研究,其主要内容包括四个方面:云环境下用户任务调度的QoS多目标优化问题、云资源利用率与云计算系统负载均衡问题、云计算系统任务调度策略执行效率问题、用户任务调度成本与云服务提供商服务收益问题。本文在对这些问题进行深入研究的基础上,设计了一套云计算环境下的自主调度体系架构,并对其中重要功能都给出了详细的算法与实验结果。论文的主要研究内容包括以下几个方面:1)在分析和研究了云计算环境下任务调度存在的问题及目标要求的基础上,提出了一种云计算环境下的自主调度体系架构。在自主调度体系架构中,系统为每个向云计算系统请求服务的用户创建一个云代理进行智能分析和决策,并为每个云代理设计了分析、评估、博弈等功能与算法。本文通过对云代理功能进行分类,设计了一个两层的自上而下的自主调度模型。其中,针对用户与云服务提供商之间的协商问题,设计了云代理协商模型。云代理通过一系列约束规则与目标规则选择符合用户QoS目标约束的SLA协议,并对SLA协议进行评估。其次,针对多个用户对关键资源的竞争而导致的资源冲突问题,设计了云代理博弈模型。云代理将系统全局收益函数引入到用户个体的收益函数中,在满足用户QoS多目标优化需求的前提下,云代理之间通过自主竞争博弈的模式,使整个系统达成全局利益最优。云代理通过协商、自主博弈的方式实现了用户任务的自主调度,提高了任务调度策略的执行效率,并且降低了用户的调度成本,也提高了云服务提供商的服务收益。2)针对在云计算环境下,用户如何判断云服务提供商在SLA中承诺的资源是否满足用户任务的QoS需求,本文提出了一种星型结构下的SLA任务调度评估算法。该算法通过云代理将云服务提供商SLA中承诺的资源抽象为标准的虚拟资源,并将用户任务与虚拟资源的映射关系抽象为星型拓扑结构的云计算系统。通过评估云计算系统的性能与可靠性,评估相应云服务提供商所承诺的资源的服务质量。用户将SLA中承诺的服务质量作为一种判断标准,判断云服务提供商提供的服务是否能够满足用户任务的QoS需求。3)针对用户任务调度的QoS多目标优化问题,提出了一种基于NSGA-II的多目标优化调度算法。云计算环境下,用户如何在一组有效的SLA集合中,选出符合其QoS多目标优化需求的调度策略依然是非常困难的问题。用户请求的任务集通常包含多个任务,每个任务都可以和不同的云服务提供商签订SLA协议,整个任务集的SLA协议由单个任务的SLA协议组合而成,组合过程往往呈现出指数级的复杂度。另一方面,用户的QoS目标之间往往是冲突的,例如,服务时间和服务成本之间是冲突的,要获得快速响应的服务,就需要计算能力较高的资源,而计算能力越高其成本就越高,必然无法同时满足两个目标。本文提出的算法为用户提供了一种高效快速的选择机制,通过NSGA-II算法对多个目标进行并行搜索,与传统的将多个目标转化为单目标问题相比,本文的算法能够在满足用户QoS多目标优化需求的前提下,高效地为其选择合理的最优的SLA任务调度策略。4)在已经签订了SLA协议的情况下,用户任务选择SLA中不同的云资源构成了不同的任务调度策略。针对如何判断哪些调度策略满足用户的QoS多目标优化需求,提出了一种虚拟树型结构下的调度评估算法。根据云资源的性质,将用户任务与云资源的映射关系建模为由网络连接起来的虚拟树型结构。在树型结构下,通常需要考虑共享传输通道失效引起的共因失效问题。针对此问题,本文利用最小生成树算法对云资源与传输通道进行数学建模。对于一个任务分配给多个资源节点冗余执行的情况,只要存在一个资源节点不失效,该任务就能成功完成;对于多个任务共享同一资源的情况,算法通过在云资源节点上增加新的分支和叶子节点,如果是并行任务就平均分配共享资源,如果是串行任务则独享资源。因此,在树型结构下,用户任务与云资源之间是一种动态灵活的映射模式。本文提出的算法能够对任意一个任务调度策略的服务质量进行快速且准确的评估,将其应用于云代理博弈模型的效用函数计算中,在提高每个用户的调度策略执行效率的同时,也提高了云服务提供商的资源利用率。5)针对大量用户同时提交任务调度请求的问题,以及多个用户之间对关键资源的竞争问题,本文在博弈论的基础上提出了一种基于囚徒困境博弈的多代理自主调度算法。该算法假设每个用户具有自己的偏好和自私性的特性,总是倾向最大化自己的利益,每个用户都只会选择对自己最有利的资源,不管是否对其他用户产生影响。由于用户的个体理性,形成了囚徒困境,导致了资源分配冲突,比如大多数用户都选择了同一个资源,使得系统负载不均衡。算法通过云代理之间的自主博弈过程,将云计算系统的全局效用目标融入到每个用户的局部效用目标中,通过设计云代理之间的博弈规则和对应的奖励因子,在每个云代理追求各自效用目标的前提下,使得整个云计算系统获得全局最优收益。通过本文提出的自主调度算法,不仅使竞争性环境下的每个用户都能找到最优的任务调度策略,同时也降低了用户的调度成本,提高了云服务提供商的整体收益。
[Abstract]:Cloud computing is the product of information technology revolution, it is a large-scale complex computing system. Cloud computing system is very dynamic in processing mass data and application tasks at all times. As the cloud computing system has the characteristics of large resource scale, diverse heterogeneity, wide user groups, different application task types and different QoS target constraints, the system needs to carry out real-time scheduling and dynamic management of various resources and application tasks in the cloud platform. As a kind of business computing model, cloud computing aims to realize resource sharing and cooperative work, and simultaneously meet user's service request and cloud service provider's service revenue. Therefore, how to allocate the cloud resources reasonably, carry out efficient management and real-time scheduling on the mass application tasks, reduce the user's cost on the premise of ensuring the load balance of the cloud computing system and improve the utilization rate of the cloud resources, improve the income of the cloud service provider, It is one of the research hot spots in the current cloud computing environment. In essence, task scheduling under cloud computing environment is a scheduling strategy that needs to establish a proper mapping relation between application task and computing resources, which aims to realize the efficient execution of the reasonable allocation and application task of computing resources. Early traditional distributed computing systems, grid computing systems, etc. measure the effect of scheduling management through performance metrics such as system throughput and task completion time. But in cloud computing environments, task scheduling problems are often more complex. firstly, the application task request in the cloud computing environment is often non-centralized, and the scale is huge; the traditional centralized resource management system is no longer applicable; the cloud computing system must schedule and manage the tasks and resources in a distributed parallel mode; secondly, cloud resources typically come from different cloud service providers, the cloud resources of each organization are often heterogeneous, how to combine heterogeneous resources into a complete service is very complex to the user; furthermore, since the cloud computing system has a dynamically expandable nature, The corresponding task scheduling must also meet scalability and adaptability; then, cloud computing as a business model, cloud service providers first consider how to improve their own resource utilization, increase share usage, reduce costs, and obtain as much service revenue as possible, This allows task scheduling to take into account the overall load balancing problem of the cloud computing system. Finally, from the perspective of the user, whether the service provided by the cloud service provider satisfies the QoS multi-target requirement of the user task scheduling is a problem that the task scheduling policy must consider. Therefore, aiming at the existing problem of task scheduling in cloud computing environment, this paper studies the task scheduling technology in cloud environment in detail, and its main content includes four aspects: multi-objective optimization problem of user task scheduling under cloud environment, Cloud resource utilization and cloud computing system load balancing problem, cloud computing system task scheduling policy implementation efficiency problem, user task scheduling cost and cloud service provider service revenue problem. On the basis of deeply studying these problems, this paper designs an architecture of autonomous scheduling system under a cloud computing environment, and gives detailed algorithm and experimental results for the important functions. The main research contents include the following aspects: 1) On the basis of analyzing and studying the problems and target requirements of task scheduling in cloud computing environment, a self-scheduling system architecture under cloud computing environment is proposed. In the architecture of autonomous scheduling system, the system creates a cloud agent for intelligent analysis and decision-making for each user requesting service to the cloud computing system, and designs the functions and algorithms such as analysis, evaluation, game, etc. for each cloud agent. In this paper, a two-tier top-down autonomous scheduling model is designed by classifying the functions of cloud agents. In this paper, a cloud broker negotiation model is designed for negotiation between users and cloud service providers. The cloud broker selects SLA agreements that conform to user QoS target constraints through a series of constraint rules and target rules, and evaluates SLA protocols. Secondly, a cloud agent game model is designed for resource conflict caused by competition of key resources by a plurality of users. The cloud agent introduces the global revenue function of the system into the income function of the user's individual, and under the premise of satisfying the multi-objective optimization requirement of the user's QoS, the cloud agent achieves the best global benefit through the mode of autonomous competition game between the cloud agents. the cloud agent realizes autonomous scheduling of the user task through negotiation and autonomous game mode, improves the execution efficiency of the task scheduling strategy, reduces the scheduling cost of the user and improves the service income of the cloud service provider. How users judge whether the resources committed by cloud service providers in SLA meet the QoS requirements of user's tasks. This paper presents an SLA task scheduling evaluation algorithm under star structure. The algorithm abstracted the resources promised in the cloud service provider SLA into the standard virtual resource through the cloud proxy, and abstracted the mapping relation between the user's task and the virtual resource into the cloud computing system of the star topology structure. By evaluating the performance and reliability of the cloud computing system, the quality of service of the resources committed by the respective cloud service providers is assessed. Based on NSGA-II, a multi-objective optimization scheduling algorithm based on NSGA-II is proposed. In a cloud computing environment, how users choose a scheduling strategy that fits their QoS multi-objective optimization needs in a set of valid SLA collections remains very difficult. The task set requested by the user usually contains a plurality of tasks, each task can enter into an SLA protocol with different cloud service providers, the SLA protocol of the whole task set is formed by the SLA protocol of a single task, and the combining process often presents the complexity of the exponential grade. On the other hand, the QoS target of the user is often conflict, for example, the service time and the service cost are conflicting, and a fast response service is obtained, resources with higher computing power are required, and the higher the computing power is, the higher the cost is, and the two targets cannot be simultaneously satisfied. The algorithm proposed in this paper provides a kind of efficient and fast selection mechanism, which can search multiple targets in parallel through the NSGA-II algorithm. Compared with the traditional single target problem, the algorithm can meet the requirement of user QoS multi-objective optimization. When SLA agreements have been signed, the user task selects different cloud resources in SLA to form different task scheduling strategies. Based on how to judge which scheduling strategies meet the QoS multi-objective optimization needs of users, a scheduling evaluation algorithm under virtual tree structure is proposed. according to the nature of the cloud resource, the mapping relationship between the user task and the cloud resource is modeled as a virtual tree type structure connected by a network. In tree-type structures, there is a general need to consider a CCF caused by a shared transmission channel failure. Aiming at this problem, this paper uses the minimum spanning tree algorithm to model the cloud resource and the transmission channel. for a case where a task is assigned to redundant execution of a plurality of resource nodes, the task can be successfully completed as long as there is a resource node which does not fail, and the algorithm increases the new branch and leaf nodes on the cloud resource node if the same resource is shared among a plurality of tasks, If it is a parallel task, the shared resource is evenly shared, and if it is a serial task, the resource is exclusive. Therefore, under the tree-type structure, the user task and the cloud resource are a dynamic and flexible mapping mode. The algorithm proposed in this paper can quickly and accurately evaluate the quality of service of any task scheduling policy, and apply it to the dynamic calculation of cloud proxy game model. At the same time, it can improve the execution efficiency of each user's scheduling policy. also improves the resource utilization rate of the cloud service provider (5) solves the problem that the task scheduling request is simultaneously submitted by a large number of users and the competition problem of the key resources among a plurality of users, Based on game theory, this paper proposes a multi-agent autonomous scheduling algorithm based on Prisoner's dilemma game. The algorithm assumes that each user has its own preferences and selfish characteristics, always tends to maximize his own interests, and each user will only choose the most favorable resource for himself, whether or not it has an impact on other users. Because of the individual reason of the user, the prisoner's dilemma is formed, resulting in resource allocation conflict, for example, most users choose the same resource, making the system load unbalanced. Through the autonomous game process between cloud agents, the global utility target of the cloud computing system is integrated into the local utility target of each user, so that the whole cloud computing system obtains the global optimal revenue. The autonomous scheduling algorithm proposed in this paper not only enables each user in a competitive environment to find the optimal task scheduling policy, but also reduces the scheduling cost of the user, and improves the overall revenue of the cloud service provider.
【学位授予单位】：电子科技大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：TP301.6

【参考文献】