论文部分内容阅读
云计算在当下已经成为信息社会的公共资源,而数据中心则是支撑云计算服务的基础设施。在高度虚拟化的云数据中心网络中,如何对服务器上的多种资源类型进行分配和调度已经成为了一个重要的研究方向。本文围绕云计算数据中心网络中资源的分配和调度问题展开。第二章研究云计算数据中心网络中单个服务器或者中间设备(middlebox)上多种资源类型数据流的公平排队问题;第三章研究云计算数据中心网络中服务器集群上的多种资源类型的公平分配问题;第四章研究云计算数据中心网络中带有放置约束的工作负载的在线均衡部署问题;第五章研究云计算数据中心网络中为了社会福利最大化(Social Welfare Maximization,SWM)进行在线的、非抢占式的多资源分配问题。主要研究内容具体如下:(1)云数据中心服务器上多资源的公平排队第二章研究在网络功能虚拟化(Network Function Virtulization,NFV)的背景下,在单个服务器或者中间设备上对分层级的流量负载进行多资源公平性调度,其实质是分层级数据流的多资源公平排队问题。当前的多资源公平排队方案通常将通过一台中间设备的每条流都当作一个独立的个体,而现实中这些流往往是被分了组的。分组的流通常来自于数据中心的不同租户(tenant)或者代表不同的服务类型(比如实时服务和尽力而为服务),并且使用分层级的调度算法进行调度。为了对分组的流进行调度,本文提出了两种分层级的多资源公平排队机制,倒塌式分层级支配性资源公平排队(Collapsed Hierarchical Dominant Resource Fair Queueing,Collapsed H-DRFQ)和互补式分层级支配性资源公平排队(Dove-tailing H-DRFQ)。原型实现和仿真结果表明,两种H-DRFQ算法都能够快速地应对动态性的变化并且提供正确有效的分层级资源保障,同时两种算法在数据包时延的表现上各有各的优势。(2)云数据中心网络中多资源的公平分配第三章研究如何将云数据中心网络中服务器集群上的多种资源按照分组/分类的用户需求进行高速的公平分配。在云数据中心中,面对海量的用户请求,资源管理器每秒钟需要做出成千上万个资源分配决策。因此,低复杂度的分配算法是数据中心高速运行的必要条件。在这部分工作发表前,已知的在数据中心服务器集群上进行分层级多资源公平分配方案具有多项式复杂度,更确切地说,算法的复杂度为服务器数量的平方。为了减少分配算法的运行时间,本文提出一个新的低复杂度的分层级多资源公平分配算法,多资源倒塌式分层级资源分配(Multiresource Collapsed Hierarchies,MCH),将算法的复杂度从已有算法的服务器数量的平方的形式降为线性形式。更进一步,根据实际用户请求的特点,可以将MCH的复杂度简化至部分用户数量的对数形式。实验表明,MCH能够提供正确的分层级资源保障,并且有效地降低实际动态环境中的算法运行时间。(3)云数据中心网络中VNFs的负载均衡部署第四章研究在云数据中心网络中对具有放置限制的VNFs进行在线的负载均衡的部署。负载均衡是对虚拟网络功能(Virtual Network Functions,VNFs)或者是虚拟机(Virtual Machines,VMs)进行部署时的常见优化目标。在对VNFs进行部署时,由于VNFs需求的异构性,导致VNFs对可部署节点的位置有放置限制,即仅仅只能放置在部分服务器之上。在云数据中心中,为了对带有放置限制的VNFs进行高速负载均衡的部署,本文提出在线算法CMMP(Constrained Minmax Placement),能够对动态到达的VNFs进行在线的部署从而实现负载均衡。CMMP的主要贡献在于严格量化了带有放置限制的负载均衡问题与最大最小公平(Max-min Fairness)算法的解决方案之间的等价关系。实验结果表明,在线CMMP算法比起已有的算法可以节省两个数量级的运行时间。(4)云数据中心网络中社会福利最大化的多资源分配第五章研究利用公平性的多资源分配方案,为数据中心中在线到达和离开的任务进行非抢占式(non-preemptive)的资源分配,从而使得数据中心整体社会福利尽可能最大化。SWM是在数据中心中进行多资源分配时的一种常见优化目标。传统的SWM解决方案是离线的,使得资源管理器以一种抢占式的方式为用户任务分配资源。在系统状态变化时,SWM需要重新计算资源分配方案,用户任务有可能由于资源的重配置而不得不中断,使得资源被抢占,这在实际应用中并不合理。为了克服这种缺陷,本文研究服务器集群中多资源的公平性分配与服务器集群整体的社会福利之间的关系,提出了一个能提供近似最优社会福利的在线算法,累积式自适应支配性资源公平分配(Cumulative Adaptive Dominant Resource Fairness,C-ADRF),使得资源管理器能够以一种贪婪的方式进行在线的近似最大化社会福利的多资源分配。实验结果表明,C-ADRF牺牲了少部分社会福利以换取非抢占式的资源分配优势,在Google数据集中与最优社会福利之间仅有3%的差异,在Facebook数据集中与最优社会福利之间仅有2%的差异。