基于优先排队论网络延迟云计算资源调度算法,目录,. 1、研究背景,1.1、基本概念 1.1.1、云计算的概念： 不是依赖本地计算机来做计算，是依赖第三方运营集中的计算机和存储资源，即将计算的任务分布在大量的物理计算机服务器和虚拟服务器构成的不同的数据中心，各种应用根据自己的需求来获取存储服务、存储空间以及信息服务。如何保持负载均衡成为一大难题。 1.1.2、云计算分类： 按照服务类型分为：基础设施云、平台服务云、应用软件云。 按照服务方式分类：公有云、私有云、混合云。 1.1.3、云计算资源调度算法： 随机算法：即把虚拟机的请求随机的分配到相应资源的物理机上。 轮转算法：将用户需求的请求轮流、有序的分配到相应地物理机上。 散列算法:把虚拟机请求的任务提前设置好散列函数，然后映射到物理器。,1.1.4、负载均衡： 是指所有的服务器的平均资源利用率达到平衡，它的优化目标是资源利用率的平衡，所有物理服务器(CPU、内存利用率、网络带宽等)的利用率基本一致。每当有资源被分配使用时，通过计算分配到资源利用率最低的资源上。 1.1.5、负载均衡的调度算法 云计算环境下资源调度是单一调度算法求解中具有局限性的一种NP-Hard难题。它分为静态调度和动态调度算法。 静态调度算法： 轮转调度算法：把新的链接请求按顺序轮流的分配到不同的服务器上，从而实现负载均衡 加权轮转调度算法：用全值表示服务器的处理能力，一段时间后，各服务器处理的请求分配到当前连接数最少的服务器上。 动态调度算法： 最小链接算法：记录服务器上链接数的负载均衡器把用户的请求分配到当前连链接数最少的服务器上。,加权最小链接算法：用权值来代表服务器的处理能力，将用户的请求分配给当前链接数和权值之比最小的服务器。 负载最轻综合均衡算法:通过对服务负载性能数据实时的采集和对轻负载服务器的周期性判决做到动态的负载均衡。 综合利用率乘积法：对服务器负载性能数据实时采集和对超载服务器进行动态迁徙实现。 1.1.5、网络延迟： 网络延迟是指数据在传输过程中，出现排长队的情况，从而使计算机接收到数据的时候会有一点的延迟，就是网络延迟。也可以理解为：虚拟机请求网络传输所用的时间。 1.1.6、NLBSA算法 是基于运筹学优先制M/M/1的排队模型的网络延迟均衡调度算法，它将网络延迟、物理机和虚拟机的CPU、内存等资源均加以考虑，可缩短虚拟机请求的调度时间。,1.2、Map-Reduce分布式编程模型 1.2.1、什么是Map-Reduce? MapReduce是一种编程模型，用于大规模数据集(大于1TB)的并行运算。概念“Map(映射)“和“Reduce(归约)“，和它们的主要思想，都是从函数式编程语言里借来的，还有从矢量编程语言里借来的特性。它极大地方便了编程人员在不会分布式并行编程的情况下，将自己的程序运行在分布式系统上。 当前的软件实现是指定一个Map(映射)函数，用来把一组键值对映射成一组新的键值对，指定并发的Reduce(归约)函数，用来保证所有映射的键值对中的每一个共享相同的键组。 1.2.2、Map-Reduce的工作原理： 、Map-Reduce将用户任务分解为N个子任务 、Master为空闲的Worker分配Map任务或是Reduce任务 、Mapworker读取对应的文件块的数据，解析出相应的键值对，然后传给Map函数，将产生的键值对分配给R个区缓存在磁盘上，在传给Master，然后Master以此为依据将信息发送给Reduce worker。,、Reduce worker读取其负责的相应中间键值对值后，此时如果分区较少，则会使不同的键值对映射到一个Reduce任务上，需要根据同键值对聚集在一起的原则进行排序。 、排序好的键值对由Reduce worker传递给Reduce函数，其产生的数据会自动添加到R个分区对应的输出的文件。 、Map和Reduce任务完成后，Map-Reduce会把放在R个分区的输出文件对应返还给用户程序。 1.2.2、Map-Reduce的调度模型图示 Fork Assign map read Local write Input Files Map phase Intermediate files Reduce phase Output Files On local disks,split0,split3,split1,split2,split4,worker,worker,worker,worker,worker,user Program,Master,output file1,output file2,. 2、模型概述及分析,2.1、模型概述 2.1.1、基于运筹学优先制的排队模型 它不再按照先来先服务的原则进行服务，而是按照优先权进行服务，级别较高的比级别较低的享有优先权，同一级的按照先来先服务的原则进行。 假设数据到达流具有不同的K个优先级，按照采集数据节点的跳数来决定任务节点处理数据的优先级，假设第1跳具有第1类分组流，优先级由1开始逐级递减！随着跳数的增加，后续节点需要处理的数据会增多，进而优先级的划分可以延迟前续节点采集的数据在后续过程中的传输效果。 2.1.2、M/M/1传统排队模型 到达和服务服从负指数分布，只有一个服务台。 2.1.3、具有优先制的M/M/1排队模型 每次系统中只可以有一组具有最高的数据流进行服务，同等级别传输等待，,其余优先级别的会被终断然后再次进行重新排队，任务节点(服务台)立即对最高优先级的进行处理。 此时的服务时间就是分组的传输时间：节点在忙时传输一个数据的时间间隔。 2.2、网络迟延分析 2.2.1、对于传统无优先级M/M/1模型 它的二阶矩即指平方的期望 假设系统中第i个数据抵达时，第j个正在传输。 由此可以看出第i组的传输时间，即是逗留时间，同时也是网络延时,只需要知道剩余服务时间X，用N来表示，就能求解出平均时延，服从负指数 分布，由它的(各态历经)遍历性可知有稳态解，则有： m(t)0,t区间内已服务的用户数 n(t)在时间数据流内的剩余传输(服务)时间 将上式的极限和求和用 ，代回到 得到无优先级的网络时延为,2.2.2、具有优先级M/M/1模型 除了到达进入节点需要根据优先级来进行服务，其余的和传统的一致，到达和服务均服从poisson分布，应用在MapReduce莫兴中 ，结合传统的网络时延可以得到： 排队的等待平均时间： 在节点传输的平均时延： 平均等待时间+平均传输(服务)时间 假设在节点中只有1和2两级的数据，那么他们 在节点中的平均时延为 ：,由上式整理可以得到： 理解：由负指数分布的性质，对于较高级别的到来而中断的服务，重新回到队伍中 的较低级别的顾客的服务时间，不会受到前一段的影响。因此对于 只需要将两个的输入率加和即可， 服从 的负指数分布，则： 根据数学归纳法可以得到 . 将和整合可以得到： 由 得到,当有第1第2第3优先级时有： 又由式可以得到： 依次类推： 得到： 由此推导出了优先制的M/M/1的平均网络迟延和等待时间,2.3、负载均衡调度算法的度量指标 1）PM资源： i为PM的编号， 是同一台PM提供的CPU值、内存值、存储数值。 2) VM 资源: j为VM的ID类型， 是虚拟机VM需要的的CPU值、内存值、存储数值。 3）时间跨度： 4）某段时间内 的平均CPU的利用率： 5） 的负载不均衡度：,一台PM提供资源的均值： CPU、内存、存储的平均利用率： DRS负载均衡的度量标准： 【注】DRS:分布式资源调度程序，根据对资源池资源负载的动态监控，合理触发均匀分配规则，最终实现资源池中的物理服务器之间重新分布虚拟机的目的 。当虚拟机遇到负载增大时，DRS将通过在资源池中的物理服务器之间重新分布虚拟机来自动为其分配更多资源。 6)容量完工总时间capacity-makespan(CM):,7)新的makespan调度时间NM：容量-完工总时间和网络时延之和。 8）makespan的负载效率shew：,