一种基于令牌调度的拥塞控制方法及装置

摘要

本发明提供一种基于令牌调度的拥塞控制方法及装置，所述方法仅需在数据接收端运行，由数据接收端根据新增流的待传输流量和现有流的剩余流量确定各流的优先级，并在每个优先级内将新增流和现有流按照剩余字节从小到大的顺序排列；对于每个优先级内较短的一定数量的流，按照流量分布关系在设定发送速率区间内确定令牌包发送速率，并依次发送至相应的数据发送端，以实现全局调度上的最短剩余时间优先，极大降低了短流时延。

权利要求

1.一种基于令牌调度的拥塞控制方法，其特征在于，用于同时在多个数据接收端运行，在每一个数据接收端，所述方法包括：在每一个往返时间内，接收至少一个数据发送端发送的一个或多个连接请求包，各连接请求包包括相应新增流的待传输流量，根据所述待传输流量确定各新增流的优先级，所述待传输流量越小则相应新增流的优先级越高；

获取所述数据接收端维护的传输数据表和等待传输数据表中所有现有流的剩余流量，并根据各现有流的剩余流量确定各现有流的优先级，所述剩余流量越小则相应现有流的优先级越高；

将各新增流和各现有流按照优先级放置到相应优先级的传输数据优先级队列中，并按照所述待传输流量和所述剩余流量从小到大的顺序排列；

将每个传输数据优先级队列中的前第一数量个新增流或现有流保留并记载在所述传输数据表中，将其余的新增流或现有流记载在所述等待传输数据 表中；

获取每个传输数据优先级队列中各新增流的待传输流量和各现有流的剩余流量分布关系，在设定发送速率区间内按照相同的分布关系配置各新增流和现有流的令牌包发送速率，并对所述传输数据表中的各新增流和现有流生成令牌包；

依次将所述传输数据表中的各新增流和现有流对应的令牌包按照相应的令牌包发送速率发送至所述数据发送端，以发起数据传输。

2.根据权利要求1所述的基于令牌调度的拥塞控制方法，其特征在于，根据所述待传输流量确定各新增流的优先级，包括：在设定标准时段内接收多个标准连接请求包，并记录各标准连接请求包内标准流的流量；

将各标准流按照流量从小到大的顺序排列，并划分出第二设定数量个流量区间，每个流量区间对应一个优先级，所述标准流的流量越小优先级越高，每个流量区间内包含所述标准流的数量相同；

获取各新增流的待传输流量所属的流量区间，将相应流量区间的优先级作为对应新增流的优先级。

3.根据权利要求2所述的基于令牌调度的拥塞控制方法，其特征在于，获取所述数据接收端维护的传输数据表和等待传输数据表中所有现有流的剩余流量，并根据各现有流的剩余流量确定各现有流的优先级，包括：获取各现有流的剩余流量所属的流量区间，将相应流量区间的优先级作为对应现有流的优先级。

4.根据权利要求2所述的基于令牌调度的拥塞控制方法，其特征在于，根据所述待传输流量确定各新增流的优先级，还包括：在所述数据接收端的上一个工作周期内选取多个备选时间段，所述工作周期为1天或1周；

将所述备选时间段中的多个合并为所述设定标准时段。

5.根据权利要求4所述的基于令牌调度的拥塞控制方法，其特征在于，根据所述待传输流量确定各新增流的优先级，还包括：获取当前时间点，将所述工作周期中与当前时间点最接近的备选时间段作为所述设定标准时段。

6.根据权利要求1所述的基于令牌调度的拥塞控制方法，其特征在于，获取每个传输数据优先级队列中各新增流的待传输流量和各现有流的剩余流量分布关系，在设定发送速率区间内按照相同的分布关系配置各新增流和现有流的令牌包发送速率中，第i个传输数据优先级队列中流fi的令牌包发送速率 计算式为：其中，c为令牌发送速率的下限值， 为令牌发送速率的上限值，α>1；ti为第i个传输数据优先级队列对应的流量区间的上界，ti‑1为第i个传输数据优先级队列对应的流量区间的下界；δ为流fi的剩余流量。

7.根据权利要求1所述的基于令牌调度的拥塞控制方法，其特征在于，在瓶颈交换机限制令牌包发送总速率的条件下，各数据接收端通过对令牌包添加随机发送间隔以控制不同数据接收端之间令牌包发送速率的比值一定。

8.根据权利要求1所述的基于令牌调度的拥塞控制方法，其特征在于，发起数据传输之后，所述传输数据表中每个传输数据优先级队列在同一时刻仅有一个正在传输的流。

9.一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，其特征在于，所述处理器执行所述程序时实现如权利要求1至8任一项所述方法的步骤。

10.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，该程序被处理器执行时实现权利要求1至8任一项所述方法的步骤。

说明书

一种基于令牌调度的拥塞控制方法及装置

技术领域

[0001] 本发明涉及通信技术领域，尤其涉及一种基于令牌调度的拥塞控制方法及装置。

背景技术

[0002] 随着在线云服务的快速扩张，数据中心快速发展。与传统互联网以公平分配带宽给所有流量为目标不同，数据中心网络更注重降低云服务的响应时间。因此，在数据中心网
络中，本领域技术人员从不同的角度进行降低流量延迟的尝试。

[0003] 为了减少流完成时间(Flow Completion Time，FCT)，本领域技术人员提出了多种传输控制协议(TCP)，起初通过稍微改变书控制协议的拥塞窗口调整方法，利用一些主动队
列管理技术，如ECN机制，降低了队列时延，从而使流完成时间变得比传统TCP协议的流完成
时间小。部分传输控制协议在减少排队时延的同时扔保持公平分配各流的带宽，因此，由于
与其他长流的带宽争用，短流的时延仍然偏高。为了进一步降低流完成时间，实现最优的平
均或尾部流完成时间，一些传输协议为流分配优先级，并尝试使用一些调度策略，如最短任
务优先(Shortest Job First，SJF)，最少达到服务(Least Attained Service，LAS)或最短
剩余时间优先(Shortest Remaining Time First，SRTF)。

[0004] 在这些调度策略中，SRTF已被证明是最小化平均FCT的最优策略，而对于减少尾部FCT来说，SRTF是近乎最优的。因此，最好是能模拟SRTF来实现最佳的平均/尾部FCT。然而，
现有的一些旨在近似SRTF的传输控制协议需要一个集中式控制器来控制所有流量的发送
速率和传输顺序，这会极大的限制网络规模。至于分布式传输控制协议，要么不能在现有的
数据中心工作，要么只能实现局部最优的SRTF，如果数据中心的带宽超额认购率大于1:1，
则不能很好地工作。

[0005] 因此，亟需一种新的数据传输方法，以在现有的数据中心实现更优的SRTF。

发明内容

[0006] 本发明实施例提供了一种基于令牌调度的拥塞控制方法及装置，以消除或改善现有技术中存在的一个或更多个缺陷，解决现有的传输控制协议难以实现全局SRTF调度以及
难以在现有数据中心部署的问题。

[0007] 本发明的技术方案如下：

[0008] 一方面，本发明提供一种基于令牌调度的拥塞控制方法，用于同时在多个数据接收端运行，在每一个数据接收端，所述方法包括：

[0009] 在每一个往返时间内，接收至少一个数据发送端发送的一个或多个连接请求包，各连接请求包包括相应新增流的待传输流量，根据所述待传输流量确定各新增流的优先
级，所述待传输流量的越小则相应新增流的优先级越高；

[0010] 获取所述数据接收端维护的传输数据表和等待传输数据表中所有现有流的剩余流量，并根据各现有流的剩余流量确定各现有流的优先级，所述剩余流量越小则相应现有
流的优先级越高；

[0011] 将各新增流和各现有流按照优先级放置到相应优先级的传输数据优先级队列中，并按照所述待传输流量和所述剩余流量从小到大的顺序排列；

[0012] 将每个传输数据优先级队列中的前第一数量个新增流或现有流保留并记载在所述传输数据表中，将其余的新增流或现有流记载在所述等待传输表中；

[0013] 获取每个传输数据优先级队列中各新增流的待传输流量和各现有流的剩余流量分布关系，在设定发送速率区间内按照相同的分布关系配置各新增流和现有流的令牌包发
送速率，并对所述传输数据表中的各新增流和现有流生成令牌包；

[0014] 依次将所述传输数据表中的各新增流和现有流对应的令牌包按照相应的令牌包发送速率发送至所述数据发送端，以发起数据传输。

[0015] 在一些实施例中，根据所述待传输流量确定各新增流的优先级，包括：

[0016] 在设定标准时段内接收多个标准连接请求包，并记录各标准连接请求包内标准流的流量；

[0017] 将各标准流按照流量从小到大的顺序排列，并划分出第二设定数量个流量区间，每个流量区间对应一个优先级，所述标准流的流量越小优先级越高，每个流量区间内包含
所述标准流的数量相同；

[0018] 获取各新增流的待传输流量所属的流量区间，将相应流量区间的优先级作为对应新增流的优先级。

[0019] 在一些实施例中，获取所述数据接收端维护的传输数据表和等待传输数据表中所有现有流的剩余流量，并根据各现有流的剩余流量确定各现有流的优先级，包括：

[0020] 获取各现有流的剩余流量所属的流量区间，将相应流量区间的优先级作为对应现有流的优先级。

[0021] 在一些实施例中，根据所述待传输流量确定各新增流的优先级，还包括：

[0022] 在所述数据接收端的上一个工作周期内选取多个备选时间段，所述工作周期为1天或1周；

[0023] 将所述备选时间段中的多个合并为所述设定标准时段。

[0024] 在一些实施例中，根据所述待传输流量确定各新增流的优先级，还包括：

[0025] 获取当前时间点，将所述工作周期中与当前时间点最接近的备选时间段作为所述设定标准时段。

[0026] 在一些实施例中，获取每个传输数据优先级队列中各新增流的待传输流量和各现有流的剩余流量分布关系，在设定发送速率区间内按照相同的分布关系配置各新增流和现
有流的令牌包发送速率中，第i个传输数据优先级队列中流fi的令牌包发送速率 计算式
为：

[0027]

[0028] 其中，c为令牌发送速率的下限值， 为令牌发送速率的上限值，α>1；ti为第i个传输数据优先级队列对应的流量区间的上界，ti‑1为第i个传输数据优先级队列对应的流量区
间的下界；δ为流fi的剩余流量。

[0029] 在一些实施例中，在瓶颈交换机限制令牌包发送总速率的条件下，各数据接收端通过对令牌包添加随机发送间隔以控制不同数据接收端之间令牌包发送速率的比值一定。

[0030] 在一些实施例中，发起数据传输之后，所述传输数据表中每个传输数据优先级队列在同一时刻仅有一个正在传输的流。

[0031] 另一方面，本发明还提供一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现上述方法的步骤。

[0032] 另一方面，本发明还提供一种计算机可读存储介质，其上存储有计算机程序，其特征在于，该程序被处理器执行时实现上述方法的步骤。

[0033] 本发明的有益效果至少是：

[0034] 所述基于令牌调度的拥塞控制方法及装置中，所述方法仅需在数据接收端运行，由数据接收端根据新增流的待传输流量和现有流的剩余流量确定各流的优先级，并在每个
优先级内将新增流和现有流按照剩余字节从小到大的顺序排列；对于每个优先级内较短的
一定数量的流，按照流量分布关系在设定发送速率区间内确定令牌包发送速率，并依次发
送至相应的数据发送端，以实现全局调度上的最短剩余时间优先，极大降低了短流时延。

[0035] 本发明的附加优点、目的，以及特征将在下面的描述中将部分地加以阐述，且将对于本领域普通技术人员在研究下文后部分地变得明显，或者可以根据本发明的实践而获
知。本发明的目的和其它优点可以通过在书面说明及其权利要求书以及附图中具体指出的
结构实现到并获得。

[0036] 本领域技术人员将会理解的是，能够用本发明实现的目的和优点不限于以上具体所述，并且根据以下详细说明将更清楚地理解本发明能够实现的上述和其他目的。

附图说明

[0037] 此处所说明的附图用来提供对本发明的进一步理解，构成本申请的一部分，并不构成对本发明的限定。在附图中：

[0038] 图1为本发明一实施例所述基于令牌调度的拥塞控制方法的流程示意图；

[0039] 图2为本发明一实施例所述基于令牌调度的拥塞控制方法中设定标准时段内数据接收端所有流剩余字节分布图；

[0040] 图3为根据图2剩余字节分布情况划分的到的流量区间图；

[0041] 图4为本发明一实施例所述基于令牌调度的拥塞控制方法中传输数据表和等待传输数据表图；

[0042] 图5为本发明一实施例所述基于令牌调度的拥塞控制方法中根据各流剩余字节分布关系确定令牌包发送速率的示意图。

具体实施方式

[0043] 为使本发明的目的、技术方案和优点更加清楚明白，下面结合实施方式和附图，对本发明做进一步详细说明。在此，本发明的示意性实施方式及其说明用于解释本发明，但并
不作为对本发明的限定。

[0044] 在此，还需要说明的是，为了避免因不必要的细节而模糊了本发明，在附图中仅仅示出了与根据本发明的方案密切相关的结构和/或处理步骤，而省略了与本发明关系不大
的其他细节。

[0045] 应该强调，术语“包括/包含”在本文使用时指特征、要素、步骤或组件的存在，但并不排除一个或更多个其它特征、要素、步骤或组件的存在或附加。

[0046] 由于数据中心网络中的业务需要超低的延迟，因此数据中心网络更倾向于使用能够最小化流完成时间的传输控制协议，而不是只追求流之间的公平性。然而，现有的传输控
制协议要么不能近似实现全局SRTF调度，要么难以在当前数据中心部署。

[0047] DCTCP(中心传输控制通讯协定)和ExpressPass等公平传输控制协议近似公平分享调度策略。PDQ和PIAS分别模拟SJF和LAS。pFabric通过提出一种优先级计算方法和队列
管理算法，近似于最佳的SRTF调度。然而，它需要特殊的交换机，无法部署在当今的数据中
心。Homa克服了pFabric的缺点，在接收端上将短流优先传输，并且在交换机上只需要有限
的优先级队列。然而，每个终端只能获得整个网络的部分流信息，只能实现本地最优的SRTF
调度。此外，它需要数据包粒度的负载均衡，在带宽非超额认购的数据中心网络中效果良
好。如果数据中心的带宽超额认购率大于1:1，则不能很好地工作。

[0048] 本发明提供一种基于令牌调度的拥塞控制方法及装置，可以在不修改数据中心网络交换机的情况下实现近似于全局最优的SRTF。为了实现近似全局SRTF，将动态优先级分
配和基于流量长度的速率控制算法在接收端上结合起来，以实现流量的无限优先级调度。
更具体地说，根据流量大小分布为每条流分配一个优先级。然后将该流的令牌包发送速率
设置为与剩余流量大小成反比。这样，即使有几个流处于同一个优先级队列中，也可以为较
短的流发送更多的令牌包。因此，剩余流量较短的流可以获得更多的带宽。

[0049] 需要预先说明的是，本发明主要基于数据接收端运行，在同一个数据中心网络中，包含多个连接交换机的数据发送端和数据接收端。各数据接收端按照相同的方法对待传输
的流进行调度。

[0050] 一方面，本发明提供一种基于令牌调度的拥塞控制方法，用于同时在多个数据接收端运行，在每一个数据接收端，如图1所示，所述方法包括如下步骤S101～S106，具体的步
骤S101～S106是在一个往返时间(RTT)内完成，并在每个往返时间内重复进行的。

[0051] 步骤S101：在每一个往返时间内，接收至少一个数据发送端发送的一个或多个连接请求包，各连接请求包包括相应新增流的待传输流量，根据待传输流量确定各新增流的
优先级，待传输流量的越小则相应新增流的优先级越高。

[0052] 步骤S102：获取数据接收端维护的传输数据表和等待传输数据表中所有现有流的剩余流量，并根据各现有流的剩余流量确定各现有流的优先级，剩余流量越小则相应现有
流的优先级越高。

[0053] 步骤S103：将各新增流和各现有流按照优先级放置到相应优先级的传输数据优先级队列中，并按照待传输流量和所述剩余流量从小到大的顺序排列。

[0054] 步骤S104：将每个传输数据优先级队列中的前第一数量个新增流或现有流保留并记载在传输数据表中，将其余的新增流或现有流记载在等待传输表中。

[0055] 步骤S105：获取每个传输数据优先级队列中各新增流的待传输流量和各现有流的剩余流量分布关系，在设定发送速率区间内按照相同的分布关系配置各新增流和现有流的
令牌包发送速率，并对所述传输数据表中的各新增流和现有流生成令牌包。

[0056] 步骤S106：依次将传输数据表中的各新增流和现有流对应的令牌包按照相应的令牌包发送速率发送至数据发送端，以发起数据传输。

[0057] 在步骤S101中，由数据接收端接收数据发送端的连接请求包，该连接请求包是由数据发送端收到上层应用的一些数据后产生的，其中至少携带将要发送的数据流的流量大
小信息。数据发送端在发出连接请求包后，处于等待状态，只有收到数据接收端发送的令牌
包时才会进入正常传输状态。

[0058] 数据接收端将接收到的连接请求包对应的流定义为新增流，进一步，根据新增流的待传输流量确定其优先级，其中，待传输流量越小，优先级越高。相应的，为同一优先级内
越短的流分配越高的令牌包发送速率，使相应的流能够更快响应，更接近最短剩余时间优
先。

[0059] 在一些实施例中，步骤S101中，根据所述待传输流量确定各新增流的优先级，包括步骤S201～S203：

[0060] 步骤S201：在设定标准时段内接收多个标准连接请求包，并记录各标准连接请求包内标准流的流量。

[0061] 步骤S202：将各标准流按照流量从小到大的顺序排列，并划分出第二设定数量个流量区间，每个流量区间对应一个优先级，标准流的流量越小优先级越高，每个流量区间内
包含所述标准流的数量相同。

[0062] 步骤S203：获取各新增流的待传输流量所属的流量区间，将相应流量区间的优先级作为对应新增流的优先级。

[0063] 在本实施例中，以数据接收端在设定标准时段内接收到的标准连接请求包作为参考，分析待传输数据流的流量分布情况，按照相应流量分布，划分第二设定数量的流量区
间，并确定各流量区间的上界和下界，其中流越短的优先级越高。如图2所示，在设定标准时
间内，接收端设备共接收到A1～A15共15个标准连接请求包对应的流，各流的长度不同。按
照从小到大的顺序排列后如3图，根据其分布情况，划分为3个流量区间，每个流量区间包含
5个流，区间1的上界为t2、下界为t1，区间2的上界为t3、下界为t2，区间3的上界为t4、下界
为t3。其中，区间1的优先级最高，区间3的优先级最低。根据新增流对应的待传输流量将其
归属到相应的区间内，并将相应区间的优先级作为该新增流的优先级。

[0064] 在一些实施例中，对于步骤S201中的标准设定时间段，可以选取本数据接收端在当前时刻之前某一段时间段，以根据数据接收端在本数据中心网络内的实际工作状态，划
分流量区间，并获得与实际条件相匹配的优先级确定标准，具体的，可以在数据接收端的上
一个工作周期内选取多个备选时间段，工作周期可以为1天或1周，也可以根据实际应用需
求确定工作周期，例如可以将执行特定任务的时间作为一个周期；进一步的，将备选时间段
中的多个合并为设定标准时段，以更全面地反映数据接收端在工作过程中所接受到流的流
量分布情况。

[0065] 进一步的，对于一个工作周期内的多个备案时间段采集到的流，为了获得更精准的流量分布情况，可以获取当前时间点，将工作周期中与当前时间点最接近的备选时间段
作为设定标准时段。例如，在数据接受端工作的上一天的工作周期内，采集每一个整点时刻
附近2分钟的时段作为备选时间段，若当前时刻为14:20，则可以采用上一天工作周期内14:
00处的备选时间段作为设定标准时段，以获得更加匹配的流量分布情况，使为确定优先级
所划分的流量区间更加匹配当前的工作状态。

[0066] 在另一实施例中，也可以直接根据当前时刻之前某一时段内实际传输的流的流量分布划分流量区间用于确定优先级，实现动态变化。例如，当前时刻为14:00，则可以采用
13:58至14:00作为设定标准时段，根据该时间段内数据接收端实际接收到的连接请求包对
应的待接收流量，划分流量区间以确定优先级。

[0067] 在另一实施例中，用于划分流量区间的参考流量，不仅包括数据接收端接收到的连接请求包对应的新增流，还包括数据接收端没有接受完成的现有流，以更精确地确定优
先级。

[0068] 相应的，在步骤S102中，对于数据接收端已经存在的现有流，在同一个RTT内，按照与步骤S201～S203同样的方式确定各现有流的优先级。

[0069] 具体的，在一些实施例中，步骤S102中，获取数据接收端维护的传输数据表和等待传输数据表中所有现有流的剩余流量，并根据各现有流的剩余流量确定各现有流的优先
级，包括步骤S301：获取各现有流的剩余流量所属的流量区间，将相应流量区间的优先级作
为对应现有流的优先级。

[0070] 在步骤S103中，将每个优先级对应的新增流和现有流，按照剩余字节从小到大的顺序排列。这里需要明确的是，新增流对应的待传输流量是新增流的剩余字节，现有流的剩
余流量是现有流的剩余字节。这样，在各优先级队列中的各新增流和现有流进一步的形成
了优先级从高到低的顺序。

[0071] 在步骤S104中，由于发送速率的范围是有限的，如果一个传输数据优先级队列中的流数量太多，那么每条的令牌包速率差异就会很小。因此，需要进一步控制每一个传输数
据优先级队列中流的数量。设置每个传输数据优先级队列中流数量最多为第一数量，该第
一数量可以根据设备和数据中心网络的负载能力确定，负载能力越大，则第一数量的值大。
当某一个传输数据优先级队列中的流的数量高于第一数量时，则将其中流较长的一个或多
个转移至等待传输表中。对转移至等待传输表中的流，则在当前RTT内不参与传输，也不参
与令牌包传输速率的计算。

[0072] 示例性的，如图4所示，传输数据表T1中每个传输数据优先级队列内都有多个流(阴影部分表示流)，为了保证在速率控制过程中，不同长度的流速度存在差异，则可以控制
每一个数据优先级队列中最多只有4个流，当某个优先级对应流的数量多于4个时，则将较
长的流转移至等待传输数据表T2中，以保证传输数据表T1内每个优先级的流保持在4个以
内。后续步骤中，仅以传输数据表T1内每个传输数据优先级队列中记载的流作为参考进行
速率分配，使得同一优先级内不同长度流的令牌包发送速率存在较为显著的差异。

[0073] 在步骤S105中，每一个传输数据优先级中存在多个流，如果公平分享网络则会产生相互竞争，从而无法达到最优的SRTF，因此，需要一种速率控制机制来调度同一优先级队
列中的流量，以接近全局SRTF。具体的，在本实施例步骤S105中，在确定同一优先级的各流
的令牌包发送速率的时候，令牌包发送速率应该有一个合适的下限和上限。如果没有一个
合适的下限，当所有的流都相当大时，则会被分配到最低的令牌包发送速率，那么，瓶颈链
路的带宽利用率就会不足。如果没有一个合理的上界，当所有的流都相当小时，则被分配了
最高的令牌包发送速率，那么每个接收端和其连接的ToR交换机之间的很多带宽将被令牌
包占用，造成大量的带宽浪费。如图5所示，本实施例按照同一优先级中各流的剩余字节分
布关系，在一个设定发送速率区间内按照该分部关系配置各新增流和现有流的令牌包发送
速率。

[0074] 具体的，第i个传输数据优先级队列中流fi的令牌包发送速率 计算式为：

[0075]

[0076] 其中，c为令牌发送速率的下限值， 为令牌发送速率的上限值，α>1；ti为第i个传输数据优先级队列对应的流量区间的上界，ti‑1为第i个传输数据优先级队列对应的流量区
间的下界；δ为流fi的剩余流量。

[0077] 在步骤S106中，按照步骤S105中确定的各流的令牌包发送速率，依次将高优先级至低优先级的所有新增流和现有流的令牌包发送出去，以实现全局最优SRTF。

[0078] 在一些实施例中，在瓶颈交换机限制令牌包发送总速率的条件下，各数据接收端通过对令牌包添加随机发送间隔以控制不同数据接收端之间令牌包发送速率的比值一定。

[0079] 在一些实施例中，发起数据传输之后，传输数据表中每个传输数据优先级队列在同一时刻仅有一个正在传输的流。

[0080] 另一方面，本发明还提供一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现上述方法的步骤。

[0081] 另一方面，本发明还提供一种计算机可读存储介质，其上存储有计算机程序，其特征在于，该程序被处理器执行时实现上述方法的步骤。

[0082] 下面结合一具体实施例对本发明进行说明：

[0083] 本实施例所述基于令牌调度的拥塞控制方法，用于在数据接收端运行，在同一个数据中心网络中，有通过交换机连接的多个数据发送端和数据接收端。

[0084] 数据发送端执行的工作包括如下内容：数据发送端在收到上层应用的一些数据后，首先向数据接收端发送一个连接请求包，包中携带流量大小信息。发送连接请求包后，
数据发送端进入连接等待状态。然后，数据发送端根据收到的数据包类型进入不同的阶段。
如果数据发送端收到等待数据包，则进入传输等待状态。如果收到令牌包，则进入正常传输
状态。每次收到令牌包，都会发送相应的数据包，直到流传输结束。处于等待状态的流在收
到令牌包后，将转入正常传输状态。在整个传输过程中，数据发送端不需要进行其他计算操
作，只需要在数据接收端的驱动下发送数据包。

[0085] 数据接收端执行的工作包括如下内容：数据接收端在传输过程中起着重要的作用，为每条流分配优先级和并进行速率控制。每个接收端维护两个连接信息表，一张表T1维
护当前正在传输的流的信息，即传输数据表。其中，每个优先级只有一个当前正在传输的
流。另一个表T2维护等待传输的流的信息，即等待传输表。当数据接收端接收到一个新流的
连接请求包时，首先根据连接请求包中携带的流长确定该流的优先级值P。流量优先级确定
后，数据接收端将检查表T1中优先级为P的流数是否超过设定数量。如果超过，那么表T1中
优先级为P的剩余字节数最大的流将被移到表T2。最后，调度器计算表T1中所有流的对应令
牌包发送速率。在每一个RTT中，接收端更新表T1、T2中的流剩余字节和优先级，将每个优先
级中的流数保持在阈值内，并根据速率控制机制重新计算令牌发送速率。

[0086] 其中，对于优先级值P的确定方法，可以参照上述步骤S201～S203，不同优先级队列所对应流量区间的上界和下界需要根据流量大小分布计算出来。令i＝1,2,...N表示数
据传输优先级的序数，ti代表不同数据传输优先级队列对应流量范围的上界，F(·)为流量
分布函数，F(ti)表示流量小于ti的流的占比，则存在如下计算式：

[0087]

[0088] 通过计算式2，可以得到各优先级对应的流量区间的边界，用于确定流进行优先级。这里需要强调的是，在数据中心网络中，多个数据接收端应该按照同一标准确定优先
级，也即不同数据接收端内各优先级对应的流量区间应该是一致的。

[0089] 而在T1表中各传输数据优先级队列确定了流之后，则需要对每个流的令牌包分配发送速率。如果具有相同优先级值的流之间相互竞争，公平分享网络带宽，会使得流量调度
性能更接近于PS而不是SRTF。为了接近全局SRTF，一个直观的方法是为剩余字节较小的流
发送更多的令牌包。因此，这些流可以比其他具有相同优先级值的流发送更多的数据包。为
了达到这个效果，速率控制方法应遵循一些基本原则。首先，所有数据接收端主机应采用相
同的优先级确定方法。否则，可能在数据接收端主机R1处，剩余字节较大的流被分配一个较
高的优先级值，而在数据接收端主机R2处，流量剩余字节较小的流会被分配一个较低的优
先级值。因此，根据SRTF策略，带宽不能共享。其次，令牌包发送速率应该有一个合适的下限
和上限。如果没有一个合适的下限，当所有的流都相当大时，则会被分配到最低的令牌包发
送速率，那么，瓶颈链路的带宽利用率就会不足。如果没有一个合理的上界，当所有的流都
相当小时，则被分配了最高的令牌包发送速率，那么每个接收端和其连接的ToR交换机之间
的很多带宽将被令牌包占用，造成大量的带宽浪费。因此，根据流量剩余字节设置适当的令
牌发送速率，可以近似地实现SRTF，从而降低流完成时间。

[0090] 具体的，速率控制算法可以参照步骤S105的说明，第i个传输数据优先级队列中流fi的令牌包发送速率 计算式为：

[0091]

[0092] 其中，c为令牌发送速率的下限值， 为令牌发送速率的上限值，α>1；ti为第i个传输数据优先级队列对应的流量区间的上界，ti‑1为第i个传输数据优先级队列对应的流量区
间的下界；δ为流fi的剩余流量。

[0093] 交换机执行的工作包括如下内容：交换机在传输过程中需要保证令牌包的速率不超过一定的限制。用最小的以太网帧大小作为令牌包的大小，即64字节。因此，在实际传输
中，令牌包的最小长度等于(64+8)字节的前导码再加上12字节的以太网帧间隙之和，即84
字节。由于最大的以太网帧是1538字节，所以每个交换机应将令牌包的总体速率限制为
其中L代表链路容量，以保证链路的高利用率以及接近零的排队时延。实际操
作过程中，可以利用当前交换机支持的队列控制机制，将令牌包的总数限制在一个阈值内。

[0094] 此外，交换机还需要保证不同流对应的令牌包的公平性和随机性。例如，如果在瓶颈交换机上，令牌包的发送速率被限制在c，两个数据接收端分别以2c和c的发送速率向瓶
颈交换机发送令牌包，那么交换机应该丢弃每条流相同比例的令牌包。具体来说，第一个流
的令牌包发送速率应降低到 第二条流的令牌包发送速率应降低到 这样，仍然
可以保证两条流的令牌包的比值与之前相同。这可以通过接收端的添加随机数据包发送间
隔以及配合交换机的流量整形来实现。通过这两种方法，可以避免一条流的若干令牌包在
短时间内连续到达交换机的同一端口，进而占用全部带宽。另外，本实施例中交换机需要采
用对称哈希来保证路由的对称性，即一条流的正向路径和反向路径是相同的。

[0095] 综上所述，所述基于令牌调度的拥塞控制方法及装置中，所述方法仅需在数据接收端运行，由数据接收端根据新增流的待传输流量和现有流的剩余流量确定各流的优先
级，并在每个优先级内将新增流和现有流按照剩余字节从小到大的顺序排列；对于每个优
先级内较短的一定数量的流，按照流量分布关系在设定发送速率区间内确定令牌包发送速
率，并依次发送至相应的数据发送端，以实现全局调度上的最短剩余时间优先，极大降低了
短流时延。

[0096] 本领域普通技术人员应该可以明白，结合本文中所公开的实施方式描述的各示例性的组成部分、系统和方法，能够以硬件、软件或者二者的结合来实现。具体究竟以硬件还
是软件方式来执行，取决于技术方案的特定应用和设计约束条件。专业技术人员可以对每
个特定的应用来使用不同方法来实现所描述的功能，但是这种实现不应认为超出本发明的
范围。当以硬件方式实现时，其可以例如是电子电路、专用集成电路(ASIC)、适当的固件、插
件、功能卡等等。当以软件方式实现时，本发明的元素是被用于执行所需任务的程序或者代
码段。程序或者代码段可以存储在机器可读介质中，或者通过载波中携带的数据信号在传
输介质或者通信链路上传送。“机器可读介质”可以包括能够存储或传输信息的任何介质。
机器可读介质的例子包括电子电路、半导体存储器设备、ROM、闪存、可擦除ROM(EROM)、软
盘、CD‑ROM、光盘、硬盘、光纤介质、射频(RF)链路，等等。代码段可以经由诸如因特网、内联
网等的计算机网络被下载。

[0097] 还需要说明的是，本发明中提及的示例性实施例，基于一系列的步骤或者装置描述一些方法或系统。但是，本发明不局限于上述步骤的顺序，也就是说，可以按照实施例中
提及的顺序执行步骤，也可以不同于实施例中的顺序，或者若干步骤同时执行。

[0098] 本发明中，针对一个实施方式描述和/或例示的特征，可以在一个或更多个其它实施方式中以相同方式或以类似方式使用，和/或与其他实施方式的特征相结合或代替其他
实施方式的特征。

[0099] 以上所述仅为本发明的优选实施例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明实施例可以有各种更改和变化。凡在本发明的精神和原则之内，所作的
任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。