基于截止时间的最小化系统开销的Coflow调度方法

IPRDB

API 数据接口

专利申请

使用指引 chat嘟嘟

会员体验

联系我们

交流群

现在联系顾问~

基于截止时间的最小化系统开销的Coflow调度方法
申请号	CN201910177871.3	申请日	2019-03-10	公开(公告)号	CN110048966A	公开(公告)日	2019-07-23
申请人	天津大学;			发明人	李克秋; 王春晓; 周晓波; 徐仁海;
摘要	本发明涉及计算机网络技术领域和数据中心网络领域，为提出基于截止时间的最小化系统开销的Coflow调度方法，不仅尽可能使更多的Coflows在截止时间到达前完成，而且为错过时限的Coflows设计了专用的调度方法，最小化因Coflow错过时限而带来的系统开销。为此，本发明采取的技术方案是，基于截止时间的最小化系统开销的Coflow调度方法，包括满足截止时间Deadline的Coflow调度步骤和错过截止时间Coflow调度步骤，Coflow为并行计算的通信阶段一组存在相关性的并行的流量的集合。本发明主要应用于网络通信场合。
权利要求	1.一种基于截止时间的最小化系统开销的Coflow调度方法，其特征是，包括满足截止时间Deadline的Coflow调度步骤和错过截止时间Coflow调度步骤，Coflow为并行计算的通信阶段一组存在相关性的并行的流量的集合； (1)满足截止时间Coflow调度步骤获取网络中相关信息，首先采用动态的方法判断Coflow是否满足截止时间，若满足，则用最早截止时间优先EDF(Earliest-Deadline-First)的方法确定调度顺序，即距离deadline越近的Coflow越先被调度,确定调度顺序后，为每个flow分配尽可能小的带宽能保证其在截止时间之前完成； (2)错过截止时间Coflow调度步骤对于错过截止时间Coflow的调度是在满足截止时间Coflow调度过程中，网络中仍有剩余的带宽尚未使用，则利用这部分剩余带宽调度错过截止时间的Coflows，并最小化超出截止时间的Coflows带来的系统总开销。 2.如权利要求1所述的基于截止时间的最小化系统开销的Coflow调度方法，其特征是，步骤(1)是让所有flows都在截止时间那个时刻完成，具体步骤如下： 1)获取网络带宽信息，具体包括每个上行端口和下行端口的剩余带宽大小；获取到达的每一个Coflow的信息，具体包括Coflow的编号，截止时间，源端口数目及编号，目的端口数目及编号，Coflow里包含的每个flow的数据量； 2)对所有Coflow按照EDF顺序排序，即按截止时间从小到大的顺序进行排序并调度； 3)判断Coflow能否在截止时间之前完成，具体的判断方式为：利用该Coflow中每个flow的数据量大小除以deadline来求对应的期望带宽，然后判断每个flow在相应的出口和入口剩余可利用带宽是否满足期望带宽； 4)若Coflow的每个flow在相应的目的端口和源端口剩余可利用带宽均大于期望带宽,则该Coflow可以在截止时间之前完成，给其分配尽可能小的带宽，让所有的flow都与最晚完成的flow同时完成，分配的带宽应为flow的数据量大小除以Coflow的deadline； 5)若Coflow中只要存在一条flow在相应的出口或入口剩余可利用带宽小于期望带宽，则该Coflow不能满足在截止时间之前完成，将其放入错过截止时间集合中，等待后续的错过截止时间Coflow调度方法进行调度； 6)更新网络链路的剩余带宽大小，将在步骤(4)中已分配的带宽减去并进行下一个Coflow的调度。 3.如权利要求1所述的基于截止时间的最小化系统开销的Coflow调度方法，其特征是，步骤(2)中，具体用cost函数来量化系统开销和超出截止时间大小的关系，且cost函数设为关于t＝CCT-deadline的单调递增的线性函数，并采取如下具体步骤： 1)获取错过截止时间集合中所有Coflows的各自的cost函数系数即斜率； 2)获取错过截止时间集合中所有Coflows的各自的长度，Coflow的长度为Coflow包含的最大flow的数据量大小； 3)计算错过截止时间集合中Coflow的skew即Coflow的长度与cost函数系数之比，并按照skew进行从小到大的排序； 4)按照步骤(3)的顺序将网络剩余带宽依次分配。
说明书全文	基于截止时间的最小化系统开销的Coflow调度方法技术领域 [0001] 本发明涉及计算机网络技术领域和数据中心网络领域。具体是，在数据中心网络环境下，基于截止时间的Coflow流量调度技术的研究与开发。背景技术 [0002] 数据中心是计算、存储和数据传输的基础设施，集中了各种软硬件资源和关键业务系统。随着云计算、大数据、物联网和人工智能时代的到来，数据中心中的数据流量呈爆炸式增长，传统的数据处理技术不足以满足海量数据的处理要求，并行计算技术应运而生，目前主流的分布式计算平台为MapReduce、Spark、Dryad和TensorfLow等。大数据处理过程中并行计算的流量传输时间占比越来越大，比如在Facebook上分析工作在网络传输上花费了33％的运行时间。网络传输逐渐成为应用性能的瓶颈，因此，如何优化网络传输是数据中心网络的关键问题。 [0003] 传统的数据中心网络传输流量调度技术是基于单个流量(flow)的调度技术。传统调度技术试图将用户托管在数据中心上应用的需求瓜分给一个个flow，调度flows，决策出分配给flows带宽等资源的先后顺序并执行资源分配，以此，希望能将网络应用层的需求传递给网络传输层。然而，单个flow通常不能够承担整个应用的需求。往往，一个应用具有多条并行的flows，它们的需求不尽相同(例如，多个flows的deadlines需求具有差异)，因此，单个flow无法代表整个应用的需求。基于flow的调度结果可能是，一个应用的某一条flow极早被调度并完成，但该应用的其他flows完成的较晚，导致该应用最终较晚完成，没能满足用户的要求而留下极差的用户体验，甚至用户不再愿意将应用托管与数据中心。为了弥补flow调度无法将应用需求从应用层传达给传输层的这一缺憾，研究者提出了以flow集合为粒度的Coflow调度技术，在应用层需求表示和网络传输层之间架起了一座鹊桥。定义Coflow为并行计算的通信阶段一组存在相关性的并行的流量(flows)的集合。例如，Mapreduce框架的Map和Reduce之间的Shuffle过程是一个Coflow，Shuffle过程中的数据流是并行的，且只有等最后一个flow完成传输,即Map阶段完成之后才可以开始Reduce计算。Coflow的最主要特性是多个flows虽并行着，但却是作为一个整体，只有最后一个flow传输完成，整体(Coflow)才算真正完成，即Coflow的完成时间(Coflow Complete time,CCT)取决于最晚完成的flow。由于减小单个flow的完成时间并不一定能减小应用的完成时间，而减小Coflow的完成时间几乎能够减小应用的完成时间，因此，如何调度好Coflow已成为目前数据中心网络传输流量调度的核心问题。 [0004] 现有的Coflow调度方法可以分为两类，信息可感知的调度方法和信息不可感知的调度方法。Coflow的优化目标主要有两个，一个是减小Coflow的完成时间，另一个是使更多的Coflows在截止时间之前完成。在使更多的Coflows满足截止时间方面，现有的调度机制大致分为两种：一是使用接纳控制原则，在调度之前判断，对于能满足截止时间的Coflow，接纳调度并保证其不会被其他Coflow抢占资源，对于不能满足截止时间的Coflow放弃或者重传所有数据流；第二种做法是使用多路复用原则，将带宽分为两部分，一部分使用优先级序列方式来调度能满足截止时间的Coflows，另一部分用加权平均分配带宽的方式来调度不能满足截止时间的Coflows。以上的调度方案没有考虑到不同Coflows对截止时间的敏感程度，对于错过截止时间的Coflows没有有效的调度。目前，现有的技术研究表明网络时延每增加100ms，亚马逊的销售收入会下降1％，时延每增加400ms，谷歌的搜索量会下降0.6％，由此可知在现有技术背景下，超出截止时间的流量会带来额外的系统开销。如何调度错过截止时间的Coflows是Coflow调度问题中的一个至关重要的挑战。 [0005] 鉴于上述背景和动机，本文提出一种基于截止时间的Coflow流量调度的方法：一方面，在有限的数据中心网络资源(带宽)情况下，尽可能使更多的Coflows在截止时间到达前完成；另一方面，若仍有Coflows未能在截止时间之前完成，则考虑该类型Coflow超出Deadline后的系统开销，并最小化系统开销。发明内容 [0006] 为克服现有技术的不足，解决带截止时间需求的流量调度问题，本发明旨在提出基于截止时间的最小化系统开销的Coflow调度方法，不仅尽可能使更多的Coflows在截止时间到达前完成，而且为错过时限的Coflows设计了专用的调度方法，最小化因Coflow错过时限而带来的系统开销。为此，本发明采取的技术方案是，基于截止时间的最小化系统开销的Coflow调度方法，包括满足截止时间Deadline的Coflow调度步骤和错过截止时间Coflow调度步骤，Coflow为并行计算的通信阶段一组存在相关性的并行的流量的集合； [0007] (1)满足截止时间Coflow调度步骤 [0008] 获取网络中相关信息，首先采用动态的方法判断Coflow是否满足截止时间，若满足，则用最早截止时间优先EDF(Earliest-Deadline-First)的方法确定调度顺序，即距离deadline越近的Coflow越先被调度,确定调度顺序后，为每个flow分配尽可能小的带宽能保证其在截止时间之前完成； [0009] (2)错过截止时间Coflow调度步骤 [0010] 对于错过截止时间Coflow的调度是在满足截止时间Coflow调度过程中，网络中仍有剩余的带宽尚未使用，则利用这部分剩余带宽调度错过截止时间的Coflows，并最小化超出截止时间的Coflows带来的系统总开销。 [0011] 步骤(1)是让所有flows都在截止时间那个时刻完成，具体步骤如下： [0012] 1)获取网络带宽信息，具体包括每个上行端口和下行端口的剩余带宽大小；获取到达的每一个Coflow的信息，具体包括Coflow的编号，截止时间，源端口数目及编号，目的端口数目及编号，Coflow里包含的每个flow的数据量； [0013] 2)对所有Coflow按照EDF顺序排序，即按截止时间从小到大的顺序进行排序并调度； [0014] 3)判断Coflow能否在截止时间之前完成，具体的判断方式为：利用该Coflow中每个flow的数据量大小除以deadline来求对应的期望带宽，然后判断每个flow在相应的出口和入口剩余可利用带宽是否满足期望带宽； [0015] 4)若Coflow的每个flow在相应的目的端口和源端口剩余可利用带宽均大于期望带宽,则该Coflow可以在截止时间之前完成，给其分配尽可能小的带宽，让所有的flow都与最晚完成的flow同时完成，分配的带宽应为flow的数据量大小除以Coflow的deadline； [0016] 5)若Coflow中只要存在一条flow在相应的出口或入口剩余可利用带宽小于期望带宽，则该Coflow不能满足在截止时间之前完成，将其放入错过截止时间集合中，等待后续的错过截止时间Coflow调度方法进行调度； [0017] 6)更新网络链路的剩余带宽大小，将在步骤(4)中已分配的带宽减去并进行下一个Coflow的调度。 [0018] 步骤(2)中，具体用cost函数来量化系统开销和超出截止时间大小的关系，且cost函数设为关于t＝CCT-deadline的单调递增的线性函数，并采取如下具体步骤： [0019] 1)获取错过截止时间集合中所有Coflows的各自的cost函数系数即斜率； [0020] 2)获取错过截止时间集合中所有Coflows的各自的长度，Coflow的长度为Coflow包含的最大flow的数据量大小； [0021] 3)计算错过截止时间集合中Coflow的skew即Coflow的长度与cost函数系数之比，并按照skew进行从小到大的排序； [0022] 4)按照步骤(3)的顺序将网络剩余带宽依次分配。 [0023] 本发明的特点及有益效果是： [0024] 实现数据中心Coflow的高效调度，使更多的Coflows能在截止时间之前完成，对于错过截止时间的流量设计专用方法调度并最小化Coflows错过截止时间带来的系统总开销。附图说明： [0025] 图1为Coflow网络调度抽象模型和输入案例。 [0026] 图2为Cost函数示例图。 [0027] 图3为所有可能调度顺序下的调度结果(包含总CCT和系统总开销)。 [0028] 图4为本发明基于截止时间最小化系统开销的Coflow调度方法的流程图。具体实施方式 [0029] 本发明旨在解决带截止时间需求的流量调度问题。主要目标有两个：其一是，在有限的数据中心网络资源(带宽)情况下，尽可能使更多的Coflows在截止时间到达前完成；其二是，对于超出截止时间的Coflows设计专有的调度方案，最小化Coflows超出时限而带来的系统总开销。 [0030] 为了克服现有技术的不足，本发明提供一种基于截止时间的最小化系统开销的Coflow调度方法，不仅尽可能使更多的Coflows在截止时间到达前完成，而且为错过时限的Coflows设计了专用的调度方法，最小化因Coflow错过时限而带来的系统开销。本发明的调度方法由满足截止时间Coflow调度方法和错过截止时间Coflow调度方法组成。 [0031] 1满足截止时间Coflow调度方法 [0032] 获取网络中相关信息，首先采用动态的方法判断Coflow是否满足截止时间，若满足，则用最早截止时间优先(Earliest-Deadline-First，EDF)的方法确定调度顺序，即距离deadline越近的Coflow越先被调度。确定调度顺序后，我们为每个flow分配尽可能小的带宽能保证其在截止时间之前完成即可。单个flow传输的很快并不能缩短Coflow的完成时间，决定Coflow的完成时间的是最晚完成的那个flow，因此我们只要让Coflow的所有flows都与完成时间最晚的那个flow同时完成即可。对于本方法我们侧重使尽可能多的Coflows在截止时间完成，所以我们让所有flows都在截止时间那个时刻完成即可，这样给该Coflow分配的带宽是最小的，网络中剩余可利用带宽会尽可能的大，可以调度更多的Coflows使他们在各自截止时间之前完成。为了简便描述，本方法中的所有Coflows假设都是0时刻到达。具体步骤如下： [0033] 1)获取网络带宽信息，具体包括每个上行端口和下行端口的剩余带宽大小；获取到达的每一个Coflow的信息，具体包括Coflow的编号，截止时间，入口端口(源端口)数目及编号，出口端口(目的端口)数目及编号，Coflow里包含的每个flow的数据量。 [0034] 2)对所有Coflow按照EDF顺序排序，即按截止时间从小到大的顺序进行排序并调度。 [0035] 3)判断Coflow能否在截止时间之前完成，具体的判断方式为：利用该Coflow中每个flow的数据量大小除以deadline(截止时间)来求对应的期望带宽，然后判断每个flow在相应的出口和入口剩余可利用带宽是否满足期望带宽。 [0036] 4)若Coflow的每个flow在相应的出口和入口剩余可利用带宽均大于期望带宽,则该Coflow可以在截止时间之前完成，给其分配尽可能小的带宽，让所有的flow都与最晚完成的flow同时完成，分配的带宽应为flow的数据量大小除以Coflow的deadline。 [0037] 5)若Coflow中只要存在一条flow在相应的出口或入口剩余可利用带宽小于期望带宽，则该Coflow不能满足在截止时间之前完成，将其放入错过截止时间集合中，等待后续的错过截止时间Coflow调度方法进行调度。 [0038] 6)更新网络链路的剩余带宽大小，将在步骤(4)中已分配的带宽减去并进行下一个Coflow的调度。 [0039] 2错过截止时间Coflow调度模块 [0040] 错过截止时间Coflow调度模块旨在调度那些错过截止时间的Coflows，在满足截止时间Coflow调度过程中，网络中仍有剩余的带宽尚未使用，本模块利用这部分剩余带宽调度错过截止时间的Coflows，并最小化超出截止时间的Coflows带来的系统总开销。随着Coflow超出deadline时间的变大，带来的系统开销也会变大，在本方法中用cost函数来量化系统开销和超出截止时间大小的关系，为简单起见，在本方法中cost函数设为关于t＝CCT-deadline的单调递增的线性函数。具体步骤如下: [0041] 1)获取错过截止时间集合中所有Coflows的各自的cost函数系数(即斜率)。 [0042] 2)获取错过截止时间集合中所有Coflows的各自的长度，本方法中Coflow的长度为Coflow包含的最大flow的数据量大小。 [0043] 3)计算错过截止时间集合中Coflow的skew即Coflow的长度与cost函数系数之比，并按照skew进行从小到大的排序。 [0044] 4)按照步骤(3)的顺序将网络剩余带宽依次分配。 [0045] 以下结合附图对本发明的实例作进一步详细描述。 [0046] 图1为Coflow调度问题的数据中心网络抽象模型和一个多Coflows调度的例子。不失一般性，与其他国内外重要研究工作相似，我们把数据中心网络抽象为如图1所示的由一个非阻塞的大交换机互联着所有服务器的抽象网络。抽象网络内部的网络吞吐量100％且带宽容量无限，因此不会发生多Coflows因竞争带宽资源导致网络堵塞的情况，但是，每个服务器端口上带宽资源受限，包含与上行链路绑定的入口端口(Ingress port)和与下行链路绑定的出口端口(Egress port)，多Coflows同时到达且将在这些端口上激烈竞争带宽资源，因此在Coflow调度问题中我们只关注入口端口和出口端口上的带宽分配。在该模型中的多Coflows例子，每个入口端口有来自一个或多个Coflows的到各个出口端口的一些flows。为了便于说明，我们将它们放入在入口端口的虚拟队列中，通常假设各个端口的带宽容量为1个单位大小，如图所示，网络中有三个Coflows，它们详细信息为：Coflow1包含两个flows，数据量分别为6，2；Coflow2包含三个flows，数据量分别为2,3,3；Coflow3包含三个flows，数据量都为2。Coflow1的数据量为6的flow入口端口为2出口端口为1，其余每个流的详细入口端口和出口端口信息如图1所示。假设这三个Coflows的deadlines均是1个单位时间，通过计算，这三个Coflows都不能满足截止时间为1的要求，会带来相应的超出截止时间的系统开销(cost)，我们要进行合理调度并最小化系统开销。 [0047] 图2为每个Colfow的cost随超出截止时间的变化示意图，假设所有Coflow对应的Cost函数均为单调递增的线性函数，由图2可知超出截止时间的Coflow带来的系统开销会随着超出截止时间的变大而变大，而不同Coflow的cost函数系数不同，因此超出截止时间相等的两个Coflows带来的系统开销也不相同。结合图1和图2关于Coflow的长度和cost系数如下表所示： [0048]Coflow Cost系数(斜率) Coflow长度 Coflow1(C1) K1＝1 L1＝6 Coflow2(C2) K2＝2 L2＝3 Coflow3(C3) K3＝0.5 L3＝2 [0049] 图3为不同调度顺序下调度结果和系统开销图，图中列出了三个Coflows全部的六种调度顺序和对应的系统开销大小，举例图3(a)来介绍cost如何计算：图3(a)的调度顺序为C1，C2，C3，简单计算可得它们的完成时间分别为6，8，10。因此，Coflow1超出截止时间为5，Coflow2超出截止时间为7，Coflow3超出截止时间为9，将时间代入cost函数，求得每个错过截止时间的Coflow带来的系统开销进而求得总的系统开销。对于图3(a)总的系统开销为cost＝51+72+9*0.5＝23.5。其余调度顺序的系统开销计算结果如图3所示。其中图3(f)是最小化Coflow总的完成时间(CCT)启发式调度方案的调度结果图，对比图3中的其他子图可知，图3(f)虽然总的完成时间最小(CCT＝17)，但是对于已经错过截止时间的Coflow来说，过度追求小的完成时间反而会提高统开销(cost＝17.5)。图3(d)是按本文的错过截止时间Coflow调度模块提出的调度方案得到的调度结果，即按照所有Coflow的长度和cost函数系数之比(skew)从小到大进行排序C2,C3,C1(skew2 [0050] 图4为本发明基于deadline最小化系统开销的Coflow调度方法流程图，具体包括以下步骤： [0051] 1)获取网络带宽信息，具体包括每个上行端口和下行端口的剩余带宽大小；获取到达的每一个Coflow的信息，具体包括Coflow的编号，到达时间，截止时间，入口端口数目及编号，出口端口数目及编号，Coflow里包含的每个flow的数据量。 [0052] 2)对所有Coflow按照EDF顺序排序存入队列1，即按截止时间从小到大的顺序进行排序并调度。 [0053] 3)依次取队列1队首的Coflow，判断Coflow能否在截止时间之前完成。具体的判断方式为：利用该Coflow中每个flow的数据量大小除以截止时间(deadline)求得对应的期望带宽，然后判断每个flow在相应的出口和入口剩余可利用带宽是否大于期望带宽。 [0054] 4)若每个flow对应的入口端口和出口端口的剩余可利用带宽都大于期望带宽即Bandwidthremain>size/deadline,则该Coflow可以在截止时间之前完成，给该Coflow的每个flow分配尽可能小的带宽，即让Coflow的所有flow都在deadline那个时刻完成。在本方法中，举例使Coflow n的deadline为Tn，分配最少的带宽去调度Coflow n，使剩余带宽尽可能的大，使得能够调度更多的Coflow，对于Coflow n的某一条入口端口为i出口端口为j包含数据量大小为dij的flow，给它分配的带宽大小为dij/Tn，分配带宽后更新i和j端口上的剩余带宽信息。 [0055] 5)若Coflow中只要存在一条flow对应的入口端口或出口端口的剩余可利用带宽小于期望带宽即Bandwidthremain [0056] 6)将该已经调度的Coflow从队列1首部中移除。 [0057] 7)循环步骤(3)至(6)直到队列1中再无Coflow。此时所有满足截止时间的Coflows都已完成调度。 [0058] 8)获取集合S中所有Coflows的的cost函数系数，在本方法中所有Coflow的cost函数均为单调递增的线性函数，例如Coflow1的cost系数为K1。 [0059] 9)获取集合S中所有Coflows的长度，本方法中Coflow的长度为Coflow包含的最大flow的数据量大小，举例Coflow1的长度(Length)为L1。 [0060] 10)对错过截止时间集合S中的Coflow计算skew＝Length/K，并按照skew从小到大的顺序对Coflow排序存入队列2，并在之后的步骤按照这个排序给Coflow分配带宽，对于Coflow1，skew＝L1/K1。 [0061] 11)给队列2队首的Coflow分配带宽，分配时将当前网络所有剩余带宽都分配给该Coflow。 [0062] 12)将在上一步完成调度的Coflow移除。 [0063] 13)重复步骤(11)和(12)，直到错过截止时间集合中的Coflow都完成调度。