数据中心网络中处理同步优先级突发流的方法

摘要

本发明为数据中心网络中处理同步优先级突发流的方法，按紧迫因子pri值的大小确定数据流被分配的优先级的高低，被默认分配极小值的pri，优先级最低。交换机对于在相同链路内请求窗口值大于预期窗口值的M条优先级同步数据流，计算降速概率pj。对于该M条数据流随机选择MXpj条数据流，调整它们的紧迫因子prj为极小值，降低其发送速率，M条中有MX（1-pj）条数据流顺利地在最后期限前完成传输。本方法有效解决了数据中心网络中同步优先级突发流的问题，避免发生网络拥塞，同时降低了最后期限错过率。

说明书

技术领域

本发明涉及数据中心网络的数据流分配方法，具体为一种数据中心网络(DCN)中处理同步优先级突发流的方法，以解决高错过率问题。

背景技术

数据中心是云计算技术的重要组成部分，为各种网络服务提供平台。服务应用工作在分散汇聚模式下（Partition/Aggregate），而汇聚节点处链路带宽一直是影响数据中心性能的主要瓶颈。此外这些业务数据流具有服务水平协定(SLA)，用户请求需要在最后期限内响应。高突发和长短混合的业务流导致传统的TCP拥塞控制协议公平共享原则的不适用，例如，长短流混合在缓存队列中造成尾部延迟，交换机缓存处理能力有限导致丢包等。网络本身并不具有最后期限的感知能力，而应用程序业务流需要在时限内得到响应。总而言之，数据中心网络面临多重的全新挑战：短流追求更低的延迟、长流需要保持较高的吞吐量，同时要求链路具备对突发流的高容忍度。

已经有研究者提出了一些针对分散/汇聚工作模式的大型数据中心网络传输控制协议。从问题解决的方案上来看，大致分为两大类：第一类是以公平共享性为准则，旨在提高网络对突发并发流的容忍能力，例如DCTCP、ICTCP。第二类放弃公平性，优先服务短流和最后期限敏感流，以缩短这类数据流的传输完成时间为首要目的，例如D³、PDQ、D²TCP、L²DCT。然而现有的Deadline-Aware Data Center TCP存在一个现象，即当链路占用率较高时，具有相同优先级的数据流由于互相竞争会同时错过最后期限，此即同步优先级突发流问题。当相同的高优先级数据流增加时这个现象将更加严重，对此，目前未见解决方法。

发明内容

本发明的目的在于设计一种数据中心网络中处理同步优先级突发流的方法，在按优先级对数据流制定窗口资源分配方案的同时，根据自适应的概率对某些数据流降速，确保窗口资源紧张时抑制部分数据流，而使大部分数据流在最后期限完成传输。

本发明设计的数据中心网络中处理同步优先级突发流的方法，所述数据中心网络包括顶层的多个交换机，并有多个工作节点，各工作节点作为发送端和一个或多个交换机连接，用户经顶层的交换机与工作节点连接，根据主动拥塞控制方法，作为发送端的各工作节点已知该数据中心网络中瓶颈链路的带宽，工作节点数量的信息；当应用程序在初始化数据流时，获得各数据流的大小及最后期限相关信息，并根据网络瓶颈链路带宽估算出数据中心网络中链路的窗口资源总值W_sum。

各交换机计算进入该交换机的各数据流的紧迫因子，确定不同业务数据流的紧迫度，按照数据流的紧迫度为其分配窗口资源；

对紧迫因子的计算方法如下：

第i条数据流在最后期限之前完成传输的请求窗口值大小为W_i’，此窗口大小至少满足：式中B_i为该数据流剩余大小，MSS(MaximumSegment Size)为TCP协议中数据包每次能够传输的数据的最大分段大小，T_Di为该数据流剩余最后期限，RTT为发送端到接收端的数据往返时延。

第i条数据流的紧迫因子pr_i定义为其请求窗口值W_i’与常规TCP传输下平均窗口值的比，假设在满拥塞状态时第i条数据流的窗口大小为W，则本发明设定其平均窗口值为第i条数据流的紧迫因子第i条数据流的窗口退避函数为，α_t是本数据中心网络链路在t时刻的拥塞程度估测值。第i条数据流的拥塞窗口为：

$>\mathrm{cwnd}=\left(\begin{array}{c}\mathrm{cwnd}\times (1-\frac{b_i}{2}),b_i>0\\ \mathrm{cwnd}+1,b_i=1\end{array}\right)$>

b_i>0时拥塞发生。

当所有数据流的窗口大小均动态同步。各数据流的不同的紧迫度因子使不同的数据流得到不同的拥塞退避函数b_i，直接关系数据中心网络中链路的窗口资源分配。

本方法按紧迫因子值的大小确定数据流被分配的优先级的高低，即当拥塞发生时，最后期限紧迫的数据流谨慎退避，而最后期限相对宽松的数据流则大幅度的退避。没有最后期限限制的数据流的紧迫因子值较小，被默认分配极小值的pr_i，即优先级最低。紧迫因子值越大的数据流紧迫度越高，被分配的优先级越高。

已知为窗口从W₁增大到W₂(W₂>W₁)期间由发送端发出去的数据包数量，此期间经历（W₂-W₁）个RTT时长。为预期获得有效窗口值，即是当交换机缓存队列长度达到ECN（Explicit CongestionNotification-显式拥塞反馈机制）标记阈值K时第i条数据流的窗口大小。在下一个RTT内，发送端即将收到带有CE（Congestion Experienced-拥塞预警）字段的确认数据包（ACK包），并响应拥塞，与此同时，第i条数据流的窗口增加一个数据包，达到其拥塞程度函数α_i由下式确定：

$>{\alpha }_i=\frac{S(W_i^{*},W_i^{*}+1)}{S((W_i^{*}+1)(1-\frac{{{\alpha }_i}^{{\mathrm{pr}}_i}}{2}),W_i^{*}+1)}$>

当0＜α_i＜1，$>{\alpha }_i=\sqrt[{\mathrm{pr}}_i+1]{\frac{2}{W_i^{*}}}$>

计算第i条数据流的窗口振幅D_i：

$>D_i=(W_i^{*}+1)-(W_i^{*}+1)(1-\frac{{{\alpha }_i}^{{\mathrm{pr}}_i}}{2})$>

$>=\frac{{{\alpha }_i}^{{\mathrm{pr}}_i}}{2}(W_i^{*}+1)$>

当$>W_i^{*}>6$>时，

$>D_i={\left(\frac{2}{W_i^{*}}\right)}^{\frac{{\mathrm{pr}}_i}{{\mathrm{pr}}_i+1}}(W_i^{*}+1)=2\sqrt[{\mathrm{pr}}_i+1]{\frac{2}{W_i^{*}}}$>

当数据中心网络达到稳定状态时，

$>\left(\begin{array}{c}\sqrt[{\mathrm{pr}}_1+1]{\frac{2}{W_1^{*}}}=\sqrt[{\mathrm{pr}}_2+1]{\frac{2}{W_2^{*}}}=···=\sqrt[{\mathrm{pr}}_n+1]{\frac{2}{W_n^{*}}}\\ W_1^{*}+W_2^{*}+···W_n^{*}=W_{\mathrm{sum}}\end{array}\right)$>

据此估算达到稳定状态时各条数据流的预期获得有效窗口值W_i^*。W_sum为当前数据中心可提供的窗口资源总值。对于最后期限敏感的数据流，在窗口资源充沛的情况下，满足∑W_i^*≥∑W_i′,i=1,2,…,N，即此时数据流预期获得的有效窗口值总和不小于其请求的窗口值W_i′总和。供大于求的用户将窗口资源分配给供不应求的用户，此时所有的数据流都能够得到合理的窗口资源分配，不会出现因争夺窗口资源而造成的优先级同步现象。

但是当窗口资源紧缺时，出现∑W_i^*<∑W_i′,i=1,2,…,N，此时为供不应求的情形，预期获得的有效窗口值总和小于其请求的窗口值W_i′总和，有些数据流因为得不到足够量的窗口资源而错过最后期限，其中包括紧迫因子相似的高紧迫度数据流，造成争夺窗口资源的优先级同步现象。

当前数据流共为N条，第i条数据流在最后期限之前完成传输的请求窗口值大小为W_i′，当前数据中心网络可提供的窗口资源总值为W_sum，当前N条数据流请求窗口值超出预期获得的有效窗口值的总和W_o为：

$>W_o=\underset{i=1}{\overset{N}{\Sigma }}{W}_i^{\prime }-W_{\mathrm{sum}}.$>

对于在相同链路内的M条优先级同步数据流，其请求窗口值总和为：此M条数据流一旦形成同步优先级突发流，M条数据均无法在最后期限内完成传输。计算该M条数据流的降速概率，其中第j条数据流的降速概率p_j为某条数据流的窗口请求值与预期获得有效值比例相差越大的数据流降速概率p_j越高。

优先级同步数据流的最后期限相同，数据流大小相似，故M条优先级同步数据流计算所得的降速概率相近。对于该M条数据流以概率p_j将其降速。即随机选择MXp_j条数据流，调整它们的紧迫因子pr_j为极小值，降低其发送速率，被降速的数据流所让出的窗口资源总和将等于上述超出资源W_o，使M条中有MX（1-p_j）条数据流顺利地在最后期限前完成传输。

具体操作时，对每条数据流选择随机数P_temj，0＜P_temj＜1，当P_temj＜P_j,调整第j条数据流的紧迫因子pr_j为极小值，降低其发送速率；否则，即当P_temj≥P_j,，其紧迫因子pr_j保持不变。

本发明数据中心网络中处理同步优先级突发流的方法中发送端对各数据流发送速率进行调节，以避免产生同步优先级突发流。

为了保证可靠传输，对于发出但尚未得到确认发送完成的数据流，发送端保存着该数据流的包括估算往返时间和状态变量值。所述状态变量值包括发送端根据剩余最后期限和剩余数据流大小计算出该数据流的请求窗口值W_i′和紧迫因子pr_i，该数据流概率降速的标记位(Flag_i)初始值为0。发送端对各数据流发送速率进行调节的具体步骤如下：

Ⅰ-1、若W_i’＞W_sum，即第i条数据所请求窗口值超出链路的窗口资源总值，此类数据流占用全部窗口资源也无法在最后期限内完成传输，发送端直接将此类数据流的概率降速的标记位设为1，其紧迫因子pr_i设置为极小值，以让出窗口资源给其余的数据流，从而保证更多数据流在最后期限内完成传输；

Ⅰ-2、当[RTT*（B_i/MSS)]＜T_Di，式中T_Di为第i条数据流最后期限剩余时间，满足此式即该数据流即使每次数据往返RTT只传送最小单位分组的一段数据包，也依然能够在最后期限内完成数据传输。将该数据流的概率降速的标记位设为1，降速以让出窗口资源给更紧迫的数据流。

Ⅰ-3、当发送端收到反馈的确认报文时，根据确认报文信息更新相应数据流的概率降速的标记位，对于概率降速的标记位Flag_i=1的数据流，其pr_i被发送端调整为极小值。

发送端为发出的每个数据包附加上一个包含最新W_i’、pr_i和Flag_i位的调度报头。当第i条数据流完成传输时，发送端为该数据流发送一个ICMP报文协议（此代码为互联网控制报文协议，英文为Internet Control MessageProtocol）通告。

本发明数据中心网络中处理同步优先级突发流的方法交换机对各数据流发送速率进行调节的具体步骤如下：

交换机有其内所有数据流的状态列表，该状态列表中为其各数据流最近的状态变量W_i’和pr_i，Flag_i以及预期获得的有效窗口值W_i^*。

Ⅱ-1、每当进入交换机的数据包属于新的数据流，交换机将其状态变量Wi’和pri添加进状态列表，然后，交换机重新计算各数据流的预期窗口资源并将各添加进状态列表。

若进入交换机的数据包属于已存在于交换机状态列表中的数据流，首先，交换机将其状态列表中的Flagi位复制到该数据包的报头中；然后，交换机将该数据包报头中的状态变量Wi’和pri更新到状态列表中。

若交换机收到ICMP报文协议，即某数据流已经完成传输。首先，交换机将该数据流在状态列表中所保留的状态变量删除；然后，交换机根据状态列表中的状态变量Wi’和pri，重新计算各数据流的预期窗口资源并将各更新进状态列表。

Ⅱ-2、根据Ⅱ-1的状态列表，判断的M条优先级同步数据流，计算各优先级同步数据流降速概率p_j，选择随机数P_temj，0＜P_temj＜1，当P_temj＜p_j,，将状态列表中数据流j的概率降速的标记位Flag_j改为1，其紧迫因子pr_j调整为极小值；否则，其数据流j的概率降速的标记位Flag_j保持为0，其紧迫因子pr_j保持不变。在状态列表中M条优先级同步数据流中有MXp_j条数据流的Flag_j位被置1，即降速。

本发明数据中心网络中处理同步优先级突发流的方法中作为接收端的工作节点复制所接收的数据流调度报头中的信息到相应的确认报文中返回发送端工作节点。

与现有技术相比，本发明数据中心网络中处理同步优先级突发流的方法的优点为：1、本方法提出了解决数据中心网络中同步优先级突发流的有效且可行的方法，避免发生网络的拥塞；2、对网络链路中的同步优先级突发流进行处理的最后期限错过率DM明显优于现有的TCP、DCTCP以及D²TCP协议的处理。

附图说明

图1是本数据中心网络中处理同步优先级突发流的方法实施例中数据中心网络示意图。

图2是本数据中心网络中处理同步优先级突发流的方法实施例发送端数据流速率调节的流程图。

图3是本数据中心网络中处理同步优先级突发流的方法实施例交换机数据流速率调节的流程图。

图4是本数据中心网络中处理同步优先级突发流的方法实施例与TCP、DCTCP以及D²TCP协议处理同步优先级突发流的最后期限错过率对比图。

具体实施方式

下面结合附图和实施例详细描述本发明。

图1所示为本数据中心网络中处理同步优先级突发流的方法实施例中数据中心网络的示意图，用户经顶层的2个交换机和多个工作节点连接，构成搜索应用拓扑网络。用户发送带有搜索关键字的查询流给网络上的各工作节点，顶层的交换机将用户的查询流分散给底层各工作节点，各个工作节点的响应可能会同时返回作为接收端的工作节点，接收端将包含搜索结果的数据流汇聚之后反馈给用户。作为发送端的各工作节点，回答用户的查询流的数据流有着相近的大小与相同的最后期限，容易发生同步优先级突发流。图中实线表示网络连接链路，细虚线表示查询数据流，粗虚线表示包含搜索结果的响应数据流，箭头上标有数据流大小（单位为MB或KB）和最后期限剩余时间T_Di。

本例各工作节点已知该数据中心网络中链路的窗口资源总值W_sum和工作节点数量；当应用程序在初始化数据流时，获得各数据流的大小及最后期限相关信息，并根据网络瓶颈链路带宽估算出数据中心网络中链路的窗口资源总值W_sum。

Ⅰ、发送端对数据流发送速率的调节

各工作节点作为发送端,对于发出但尚未得到确认发送完成的数据流，本方法的发送端保存着该数据流的包括估算往返时间和状态变量值。所述状态变量值包括发送端根据剩余最后期限和剩余数据流大小计算出该数据流的请求窗口值W_i′和紧迫因子pr_i，该数据流概率降速的标记位Flag_i初始值为0。

第i条数据流的紧迫因子

式中W为在满拥塞状态时第i条数据流的窗口大小。

发送端发送速率调节的流程如图2所示，具体步骤如下：

Ⅰ-1、若W_i'＞W_sum，即第i条数据所请求窗口值超出链路的窗口资源总值，发送端直接将该数据流的概率降速的标记位Flag_i设为1，其紧迫因子pr_i设置为极小值，以让出窗口资源给其余的数据流；

Ⅰ-2、当[RTT*（B_i/MSS)]＜T_Di，式中T_Di为第i条数据流最后期限剩余时间，将其将该数据流的概率降速的标记位设为1，降速以让出窗口资源给紧迫流。

Ⅰ-3、当发送端收到某数据流反馈的确认报文时，根据确认报文信息更新该数据流的概率降速的标记位，对于概率降速的标记位Flag_i=1的数据流，其pr_i将会被发送端调整为极小值。

发送端为发出的每个数据包附加上一个包含最新W_i’、pr_i和Flag_i位的调度报头。当第i条数据流完成传输时，发送端为该数据流发送一个ICMP报文协议通告。

Ⅱ、交换机对数据流发送速率的调节

交换机有其内所有数据流的状态列表，该状态列表中为其各数据流最近的状态变量W_i’和pr_i，Flag_i以及预期获得的有效窗口值W_i^*。

交换机调节流程如图3所示，具体步骤如下：

Ⅱ-1、每当进入交换机的数据包属于新的数据流，交换机将其状态变量W_i’和pr_i添加进状态列表，然后，交换机重新计算各数据流的预期窗口资源并将各添加进状态列表。

W_i^*计算公式为：

$>\left(\begin{array}{c}\sqrt[{\mathrm{pr}}_1+1]{\frac{2}{W_1^{*}}}=\sqrt[{\mathrm{pr}}_2+1]{\frac{2}{W_2^{*}}}=···=\sqrt[{\mathrm{pr}}_n+1]{\frac{2}{W_n^{*}}}\\ W_1^{*}+W_2^{*}+···W_n^{*}=W_{\mathrm{sum}}\end{array}\right)$>

$>{\mathrm{pr}}_i=\frac{W_i^{\prime }}{\frac{3}{4}W}$>

若进入交换机的数据包属于已存在于交换机状态列表中的数据流，首先，交换机将其状态列表中的Flag_i位复制到该数据包的报头中；然后，交换机将该数据包报头中的状态变量W_i’和pr_i更新到状态列表中。

若交换机收到ICMP报文协议，即某数据流已经完成传输。首先，交换机将该数据流在状态列表中所保留的状态变量删除；然后，交换机根据状态列表中的状态变量W_i’和pr_i，重新计算各数据流的预期窗口资源并将各更新进状态列表。

Ⅱ-2、根据Ⅱ-1所得的状态列表，判断的M条优先级同步数据流，计算各优先级同步数据流降速概率，其中第j条数据流的降速概率p_j，

$>p_j=\frac{W_i^{\prime }}{W_i^{*}}\times \frac{W_o}{W_p}$>

W_o为当前N条数据流请求窗口值超出预期获得的有效窗口值的总和，

$>W_o=\underset{i=1}{\overset{N}{\Sigma }}{W}_i^{\prime }-W_{\mathrm{sum}}.$>

W_p为W_i′>W_i^*的M条优先级同步数据流请求窗口值总和

$>W_p=\underset{j=1}{\overset{M}{\Sigma }}{W}_j^{\prime }.$>

选择随机数P_temj，0＜P_temj＜1，当P_temj＜p_j,，将其数据报头中的概率降速的标记位改为1，其紧迫因子pr_j调整为极小值；否则，其数据报头中的概率降速的标记位保持为0，其紧迫因子pr_j保持不变。

Ⅲ、接收端

接收端复制所接收的数据流调度报头中的信息到相应的确认报文中返回发送端。

借助于仿真软件，建立如图1的数据中心网络拓朴结构，本方法实施例标为P²D，与现有TCP、DCTCP以及D²TCP协议对网络链路中的同步优先级突发流进行处理，四种处理方法的最后期限错过率的对比，如图4所示。图4的纵坐标为最后期限错过率DM、单位为%，横坐标为数据流的数量N、单位为条，图内的4个柱形分别代表四种处理方法的最后期限错过率DM。由图中可看出，在数据流为20、30和40的情况下本方法实施例P²D的最后期限错过率DM均明显优于现有三种协议。

上述实施例，仅为对本发明的目的、技术方案和有益效果进一步详细说明的具体个例，本发明并非限定于此。凡在本发明的公开的范围之内所做的任何修改、等同替换、改进等，均包含在本发明的保护范围之内。