用于确保每流公平带宽共享的数据传输管理方法与流程

1.本发明大体上涉及数据传输，更具体地，本发明涉及一种计算机实现的管理数据传输的方法，用于在网络中进行带宽公平共享。此外，本发明涉及一种用于管理数据传输的计算设备。


背景技术：

2.数据传输是指在两个或两个以上设备之间传递数据的过程。在并发流之间公平共享带宽的重要性日益得到认识，尤其是在数据中心网络的背景下。数据中心网络中的数据流可能会导致链路带宽饱和，尤其是服务器与其架顶式(top-of-rack，tor)交换机之间的链路带宽。共享链路带宽的方式会显著影响并发流的性能。最近，带宽的公平共享在互联网核心中也越来越重要。在互联网核心中，在远程服务器之间高速传递大量内容的流越来越多地使用链路，例如，以填充互联网服务提供商(internet service provider，isp)存在点(point of presence，pop)中的内容提供商缓存。此类流的存在使得公平地共享带宽是可取的，从而保持要求低数据包延迟的并发流的性能。此外，由于瓶颈带宽和往返传播时间(bottleneck bandwidth and round-trip propagation time，bbr)等更积极的拥塞控制协议的引入，导致不能充分依赖终端系统在瓶颈带宽上进行公平共享。
3.五元组流之间的带宽公平共享是ip组网中的典型问题。已经提出了许多方法来实现本地级别和端到端级别的每流公平共享。在本地级别方法中，可使用亏空轮循(deficit round robin，drr)和开始时间公平队列(start time fair queuing，stfq)等典型的公平队列调度器来控制少量广泛定义的流量类别之间的共享，但这不适用于五元组流。此外，典型的公平队列调度器通常要求每个流一个物理队列，尚未在互联网或数据中心网络上实现每流公平带宽共享。在一种现有的实现本地级别的公平带宽共享的方法中，每个输出使用一小组先进先出(first in first out，fifo)队列。但是，fifo队列并不专用于流，而是用于根据数据包编程的出发时间对数据包进行分类。此外，实现这种方法是很复杂的，尤其是对于“旋转严格优先级调度器”和“轮数”的计算。在另一种现有的方法中，在使用远程直接存储器存取(remote direct memory access，rdma)的无损数据中心网络的背景下进行公平带宽共享。这种现有的方法实现了公平调度器，该公平调度器将活动流动态分配到少量输出队列，从而可以在流粒度上根据需要暂停传入流量。
4.此外，可以使用端到端传输协议实现的端到端拥塞控制实现公平带宽共享。在现有的方法中，使用高精度拥塞控制(high precision congestion control，hpcc)算法来解决无损数据中心网络带宽共享的问题。引入一种简单的切换算法，用于标记具有拥塞指示的数据包，包括当前队列长度和传输流量的数量。然而，hpcc需要复杂的终端系统算法来计算数据流速。在另一种现有的方法中，虚拟公平调度器用于跟踪作为字节计数器实现的每流虚拟队列的占用情况。然而，虚拟公平调度器存在限制，因为活动流的所有字节计数器都需要频繁地更新，以精确地分配信用，这在数据中心的当前交换机中是禁止的。这种精确的公平性方法已被用于进行公平带宽共享，但是它只适用于配备有强大cpu的软件路由器。该
精确的公平性方法过于复杂，无法应用于配备有匹配动作表的流水线的现代交换机，这些流水线的可行操作范围有限。
5.或者，流控制报头(rwnd，由接收端点在数据包报头中通告)可以用作控制非合作主机的发送速率(除cwnd外，由发送方计算)的手段，因为传输控制协议(transmission control protocol，tcp)源每次往返时间最多发送w＝min(cwnd,rwnd)个数据包。类似地，重写ack数据包的rwnd的方法可以缓解数据中心网络中的入播(incast)问题。现有的端到端拥塞控制方法都没有考虑多种类型流量的共存，因此对多种类型的数据流进行平等处理。
6.现有的方法需要复杂的计算，或者难以实现或无法在交换机体系结构中实现。现有的方法还可能需要更复杂的硬件。因此，需要解决现有技术中的上述技术缺陷，以确保每流公平带宽共享，实现数据拥塞控制。


技术实现要素：

7.本发明的目的是提供一种管理数据传输的方法，以确保每流公平性，在网络中实现带宽拥塞控制。
8.这个目的是通过独立权利要求的特征来实现的。其它实现方式在从属权利要求、说明书和附图中是显而易见的。
9.本发明提供了一种管理数据传输的方法和一种执行所述管理数据传输的方法的计算设备。
10.根据第一方面，提供了一种计算机实现的管理数据传输的方法。所述方法包括：处理器接收属于多个数据流中的一个数据流的数据包。所述方法包括：所述处理器基于接收到的数据包所属的数据流从虚拟队列列表中识别虚拟队列。所述方法包括：所述处理器判断识别的虚拟队列大小是否超过阈值最大大小。所述方法包括：基于所述确定的结果：基于所述接收到的数据包的大小，增加识别的虚拟队列；转发所述接收到的数据包。所述方法包括：所述处理器将所述虚拟队列列表中的虚拟队列设置为目标队列。所述方法包括：所述处理器基于更新时间间隔确定业务容量，并基于确定的业务容量增加信用额度。所述方法包括：所述处理器基于信用额度大小将所述目标队列减少一个量，并将所述信用额度减少相同的量。
11.通过以下方式：(i)在数据包的每次到达时仅增加单个虚拟队列的状态(即流数据)，和(ii)在可能与数据包到达重合也可能不重合的带宽分配时刻序列中仅减少单个虚拟队列，本方法具有在不涉及复杂算法的情况下实现接近精确公平性的近似公平带宽共享的优势。所述方法使硬件/可编程交换机能够在输出中的数据流之间公平地共享网络带宽，而不考虑输入中的数据流需求。所述方法通过在每个分配时刻将所有可用带宽分配到单个虚拟队列，提供近似公平带宽共享。
12.所述方法采用简单的计算来确定识别的虚拟队列大小与阈值最大队列大小之间的差。所述方法有助于限制在每个数据包到达时需要修改的状态量，以实施公平带宽共享。所述方法可以在包括高速可编程交换机在内的一系列可编程交换机上实现，用于不同的应用领域(例如数据中心、互联网服务提供商(internet service provider，isp))。所述方法实现了网络设备中的近似公平带宽共享。所述方法通过将本地方法和端到端方法结合起来
来实现公平带宽共享。在端到端方法中，所述方法根据流量和应用场景的具体情况调整实施决策，当与本地方法结合时，能够组合一组实施规则，从而在不同类型的数据流混合存在时保持稳固性。
13.在第一方面的管理数据传输的方法的第一可能的实现方式中，如果确定所述虚拟队列大小超过所述阈值最大大小，则不转发所述接收到的数据包，且不基于所述接收到的数据包的所述大小增加所述识别的虚拟队列。所述方法可以通过不转发所述接收到的数据包来在本地级别实施近似公平带宽共享。在这种实现方式中，所述接收到的数据包被丢弃或丢包，而不是被转发。所述方法是可互操作的，因为所述方法可以与为具有隐式或显式信令的协作源或具有本地或远程实施的非协作源量身定制的端到端方法结合使用。
14.在所述第一方面的所述方法的第二可能的实现方式中，如果确定所述虚拟队列大小超过所述阈值最大大小，则在转发所述接收到的数据包之前，将网络拥塞的通知添加到所述接收到的数据包的报头中。
15.在所述第一方面本身或根据前述实现方式中的任一种的所述管理数据传输的方法的第三可能的实现方式中，如果所述虚拟队列列表不包括与所述接收到的数据包对应的所述数据流相对应的虚拟队列，则识别所述虚拟队列包括：将新的虚拟队列添加到所述虚拟队列列表中。
16.在所述第一方面本身或根据前述实现方式中的任一种的所述管理数据传输的方法的第四可能的实现方式中，转发所述接收到的数据包包括：将所述接收到的数据包转发到物理先进先出(first-in-first-out，fifo)队列进行传输。
17.在所述第一方面本身或根据前述实现方式中的任一种的所述管理数据传输的方法的第五可能的实现方式中，转发所述接收到的数据包包括：判断所述识别的虚拟队列大小是否超过阈值最小大小，如果所识别的虚拟队列大小不超过所述阈值最小大小，则将所述数据包转发到优先级fifo队列以进行传输。
18.在所述第一方面本身或根据所述第一方面的所述方法的所述第一可能的实现方式至所述第一方面的所述方法的所述第三可能的实现方式的所述管理数据传输的方法的第六可能的实现方式中，接收所述数据包包括：从物理fifo队列接收所述数据包，转发所述接收到的数据包包括：将所述接收到的数据包转发到输出端口进行传输。
19.所述方法使得能够在可编程/硬件交换机和路由器中实施每数据流公平带宽共享。
20.在所述第一方面的第六可能的实现方式的所述管理数据传输的方法的第七可能的实现方式中，所述更新时间间隔是前一个数据包的时间戳与所述数据包的时间戳之间经过的时间间隔。所述数据包的所述时间戳基于进入所述物理fifo队列的相应时间。
21.在所述第一方面的第六可能的实现方式或第七可能的实现方式的所述管理数据传输的方法的第八可能的实现方式中，所述方法还包括：估计公平传输速率，并将估计的公平传输速率发送到所述物理fifo队列的入口处理器。所述入口处理器用于通过将所述数据流的设定传输速率与所述估计的公平传输速率进行比较，对给定数据流的新到达数据包进行优先级排序。优先级排序的方法包括：将所述数据包转发到优先级fifo队列进行传输。
22.所述方法有助于估计终端系统可用于执行精确网络拥塞控制的公平传输速率。所述公平传输速率还可用于监测或实施公平共享或负载平衡，或作为资源分配程序的输入。
23.在所述第一方面的第四可能的实现方式或第五可能的实现方式的所述管理数据传输的方法的第九可能的实现方式中，所述更新时间间隔是前一个数据包的时间戳与所述数据包的时间戳之间经过的时间间隔。
24.在所述第一方面本身或根据前述实现方式中的任一种的所述管理数据传输的方法的第十可能的实现方式中，所述目标队列基于所述虚拟队列列表的固定顺序设置。
25.在所述第一方面本身或根据所述第一方面的所述方法的第一可能的实现方式至所述方法的第九可能的实现方式中的任一种的所述管理数据传输的方法的第十一可能的实现方式中，所述目标队列基于所述虚拟队列列表中的伪随机选择设置。
26.根据所述第一方面的所述管理数据传输的方法的第十可能的实现方式或第十一可能的实现方式的第十二可能的实现方式中，所述目标队列还基于所述虚拟队列列表中的每个虚拟队列的权重设置。所述方法通过为每个虚拟队列应用单独的流权重，在可编程/硬件交换机和路由器中实现加权公平带宽共享。
27.在所述第一方面本身或根据所述第一方面的前述实现方式中的任一种的第十三可能的实现方式中，减少所述目标队列包括：如果所述目标队列为空，则从所述虚拟队列列表中删除所述目标队列。
28.在所述第一方面本身或根据所述第一方面的前述实现方式中的任一种的第十四可能的实现方式中，减少所述信用额度包括：如果在减少所述目标队列之后所述目标队列为空，则存储所述信用额度的余值。
29.在所述第一方面本身或根据所述第一方面的前述实现方式中的任一种的第十五可能的实现方式中，所述方法还包括：估计公平传输速率，并通过以下至少一项输出所述公平传输速率：(i)将所述公平传输速率添加到所述接收到的数据包的报头中，或(ii)将所述公平传输速率值转发到外部设备。估计的公平传输速率可选地有助于确定来自数据源/外部设备的适当发送速率，以匹配公平传输速率，从而不会出现数据包丢失和可忽略不计的延迟。
30.根据第二方面，提供了一种计算设备，所述计算设备包括处理器并用于执行所述方法及其前述实现方式中的任一种。
31.根据第三方面，提供了一种计算机程序，当由处理器执行时，所述计算机程序使所述处理器执行所述方法及其前述实现方式中的任一种。
32.根据第四方面，提供了一种计算机可读介质，所述计算机可读介质包括指令，当由处理器执行时，所述指令使所述处理器执行所述方法及其前述实现方式中的任一种。
33.解决了现有技术中的技术问题，所述技术问题涉及需要多个每流队列、拥塞控制协议复杂、不适合交换机体系结构的流水线数据处理。
34.因此，相比之下，根据本发明中提供的方法、计算设备、计算机程序和计算机可读介质，具有最小数量的虚拟队列的简单计算足以通过跟踪实现为虚拟队列列表的每数据流虚拟队列的占用情况来在本地以及端到端数据传输中实施每流公平带宽共享。在接收到每个数据包时，虚拟队列列表中的虚拟队列将更新。首先，将自接收到前一个数据包以来累积的业务容量的量添加到信用额度中。然后，将接收到的数据包添加到接收到的数据包所属的虚拟队列中。单独地，在可能与数据包到达重合或可能不重合的适当时间时刻，信用额度用于减少一个或多个活动数据流的目标队列的占用。
35.本发明的这些和其它方面将从下面描述的实施例和中显而易见。
附图说明
36.现在将仅通过示例的方式参考以下附图描述本发明的实施例，其中：
37.图1是根据本发明的实施例的管理数据传输的计算设备的框图；
38.图2是根据本发明的实施例的图1的计算设备的分解图；
39.图3a是根据本发明的实施例的从虚拟队列列表更新虚拟队列中数据包的每次到达并通过fifo队列将接收到的数据包转发到图1的输出端口的方法的示例性说明；
40.图3b是根据本发明的实施例的从虚拟队列列表更新虚拟队列中数据包的每次到达并当虚拟队列大小大于阈值最小大小时不转发接收到的数据包的方法的示例性说明；
41.图4是示出根据本发明的实施例的平均流吞吐量和虚拟队列列表大小的99百分位数的图形表示；
42.图5a-5b是示出根据本发明的实施例的管理数据传输的方法的流程图；
43.图6是用于实现本发明的实施例的计算设备的图示。
具体实施方式
44.本发明的实施例提供了一种管理数据传输以确保每流公平性以实现网络中带宽的拥塞控制的系统和方法。用于测量、转发和实施每流公平性的系统和方法可以在(i)单个设备中的本地级别，(ii)端到端(即数据流)级别，或(iii)全局级别(即网络级别)实现。本地级别和端到端(数据流)级别是兼容的，可一起实施。
45.为了使本领域技术人员更容易理解本发明的解决方案，参考附图描述本发明的以下实施例。
46.本发明的发明内容、权利要求和附图中的例如“第一”、“第二”、“第三”和“第四”(如果有的话)之类的术语用于区分类似的对象，而不一定用于描述特定的顺序或次序。应理解，这样使用的术语在适当的情况下是可互换的，例如，使得本文描述的本发明的实施例能够以本文所示或描述的顺序以外的顺序实现。此外，术语“包括”和“具有”及其任何变体旨在涵盖非排他性包括。例如，包括一系列步骤或单元的过程、方法、系统、产品或设备不一定限于明确列出的步骤或单元，而是可以包括未明确列出的或此类过程、方法、产品或设备固有的其它步骤或单元。
47.数据流被定义为在时间和空间上本地出现的具有类似报头字段值的数据包序列。在ip组网中，数据包的报头字段可以包括源地址和目的地址、源端口和目的端口以及传输协议的五元组。
48.图1是根据本发明的实施例的管理数据传输的计算设备104的框图100。计算设备104包括处理器102。处理器102接收属于一个或多个数据流中的一个数据流的数据包。处理器102基于接收到的数据包所属的数据流从虚拟队列列表中识别虚拟队列。处理器102确定识别的虚拟队列大小是否超过阈值最大大小(θ)。基于确定的结果，处理器102基于接收到的数据包的大小增加识别的队列虚拟大小并转发接收到的数据包。处理器102将虚拟队列列表中的虚拟队列设置为目标队列。处理器102基于更新时间间隔确定业务容量，并基于确定的业务容量增加信用额度。在可能与数据包到达重合也可能不重合的时刻，处理器102基
于信用额度大小将目标队列减少一个量，并将信用额度减少相同的量。计算设备104可选地包括数据流输入端口106和输出端口108。处理器102从数据流输入端口106接收属于一个或多个数据流中的一个数据流的数据包。处理器102通过输出端口108转发接收到的数据包。
49.在实施例中，如果处理器102确定虚拟队列大小超过阈值最大大小，处理器102不转发接收到的数据包，并且不基于接收到的数据包的大小增加识别的虚拟队列。接收到的数据包可以被丢弃或丢包。
50.在实施例中，计算设备104不限于从路由器、包括高速可编程交换机的硬件/可编程交换机、平板电脑、计算机等中选择。
51.图2是根据本发明的实施例的图1的计算设备104的分解图。计算设备104包括数据包接收模块202、虚拟队列识别模块204、数据包转发模块206、目标队列设置模块208、业务容量确定模块210、目标队列和信用额度减少模块212。数据包接收模块202接收属于一个或多个数据流中的一个数据流的数据包。虚拟队列识别模块204基于接收到的数据包所属的数据流从虚拟队列列表中识别虚拟队列。数据包转发模块206确定识别的虚拟队列大小是否超过阈值最大大小。基于确定的结果，数据包转发模块206基于接收到的数据包的大小增加识别的虚拟队列并转发接收到的数据包。
52.业务容量确定模块210在数据包接收模块202接收到数据包时被激活，并基于更新时间间隔确定业务容量，并基于确定的业务容量增加信用额度。
53.在实施例中，如果数据包转发模块206确定虚拟队列大小超过阈值最大大小，则数据包转发模块206不转发接收到的数据包，并且不基于接收到的数据包的大小增加识别的虚拟队列。接收到的数据包可以被丢弃或丢包，而不是被转发。
54.目标队列设置模块208将虚拟队列列表中的虚拟队列设置为目标队列。目标队列和信用额度减少模块212基于信用额度大小将目标队列减少一个量，并将信用额度减少相同的量。目标队列在适当的时刻减少，所述适当的时刻可以至少与数据包到达一样频繁地发生，但可能与数据包到达重合也可能不重合。
55.图3a是根据本发明的实施例的从虚拟队列列表更新虚拟队列中数据包302的每次到达并通过fifo队列306将接收到的数据包302转发到图1的输出端口108的方法的示例性说明。首先，基于接收到的数据包302所属的数据流，从虚拟队列列表304a-n中识别虚拟队列。确定识别的虚拟队列大小是否超过阈值最大大小。基于确定的结果，基于接收到的数据包302的大小增加识别的虚拟队列。
56.如果识别的虚拟队列大小不超过阈值最小大小，则接收到的数据包302通过fifo队列306转发以进行传输。然后，将接收到的数据包302添加到接收到的数据包302所属的虚拟队列中。
57.基于更新时间间隔确定业务容量，并根据确定的业务容量增加信用额度。首先，将自接收到前一个数据包以来累积的业务容量的量添加到信用额度中。
58.单独地，在可能与数据包到达重合或可能不重合的适当时间时刻，信用额度用于减少一个或多个活动数据流的目标队列的占用。适当的时刻可以至少与数据包到达一样频繁地发生，但在其它方面是自由定义的，并且可能与数据包到达重合也可能不重合。
59.参考图3a，图3b是根据本发明的实施例的从虚拟队列列表更新虚拟队列中的数据包308的每次到达并当虚拟队列大小超过阈值最小大小时不通过fifo队列306转发接收到
的数据包308的方法的示例性说明。如果识别的虚拟队列304a大小超过阈值最小大小，则可选地丢弃接收到的数据包308。可选地，如果确定虚拟队列大小超过阈值最大大小，则可以在转发接收到的数据包308之前，将网络拥塞的通知添加到接收到的数据包308的报头中。
60.所述方法被实现用于在交换机和路由器中实施近似每流公平带宽共享，所述交换机和路由器可以每输出端口108使用单个物理队列。
61.所述方法在适当的时刻减少了一个虚拟队列，即目标队列的积压。适当的时刻可能与数据包到达重合，也可能不重合。如果目标队列的积压业务容量小于信用业务容量，则可以从虚拟队列列表304a-n中删除目标队列。剩余信用度可以保留，并可以在数据包的下一次到达时添加到新累积的业务容量中。所述方法分别使用用于管理数据传输的第一算法和第二算法在本地级别和端到端级别执行。
62.图4是示出根据本发明的实施例的平均流吞吐量和虚拟队列列表大小的99百分位数的图形表示。图形表示描述了近似公平性的平均流吞吐量和虚拟队列列表大小的99百分位数。负载在x轴上绘制，平均流吞吐量402或虚拟队列列表大小的99百分位数404在y轴上绘制。图形表示描述了本方法(+)和分析模型(线)的模拟结果。与例如亏空轮循(deficit round robin，drr)之类的典型调度器实现的公平性相比，本方法以粗粒度实施公平性。
63.图5a-b是示出根据本发明的实施例的管理数据传输的方法的流程图。在步骤502，处理器接收属于一个或多个数据流中的一个数据流的数据包。在步骤504，处理器基于接收到的数据包所属的数据流从虚拟队列列表中识别虚拟队列。在步骤506，处理器确定识别的虚拟队列大小是否超过阈值最大大小。在步骤508，基于确定的结果：基于接收到的数据包的大小，增加识别的虚拟队列；转发接收到的数据包。在步骤510，处理器基于更新时间间隔确定业务容量，并基于确定的业务容量增加信用额度。
64.在步骤512，处理器将虚拟队列列表中的虚拟队列设置为目标队列。在步骤514，处理器基于信用额度大小将目标队列减少一个量，并将信用额度减少相同的量。
65.根据第一实施例，如果确定虚拟队列大小超过阈值最大大小，则不转发接收到的数据包，且不基于接收到的数据包的大小增加识别的虚拟队列。第二算法处理接收到的数据包。如果第二算法确定虚拟队列大小超过阈值最大大小，则第二算法丢弃接收到的数据包。在实施例中，如果虚拟队列(virtual queue，vq)按接收到的数据包长度递增，则第二算法转发接收到的数据包。
66.根据第二实施例，如果确定虚拟队列大小超过阈值最大大小，则在转发接收到的数据包之前，将网络拥塞通知添加到接收到的数据包的报头中。可选地，如果虚拟队列列表中不包括与接收到的数据包对应的数据流相对应的虚拟队列，则通过将新的虚拟队列添加到虚拟队列列表中来识别虚拟队列。可选地将接收到的数据包转发到物理fifo队列以进行传输。可选地，通过确定识别的虚拟队列大小是否超过阈值最小大小，如果识别的虚拟队列大小不超过阈值最小大小，则将数据包转发到优先级fifo队列以进行传输，从而转发接收到的数据包。可选地从物理fifo队列接收数据包，可选地将接收到的数据包转发到输出端口以进行传输。
67.根据第三实施例，更新时间间隔是前一个数据包的时间戳与数据包的时间戳之间经过的时间间隔。数据包的时间戳基于在计算设备104之前进入物理fifo队列的相应时间。
68.可选地，所述方法包括：估计公平传输速率，并将估计的公平传输速率发送到物理
fifo队列的入口处理器。所述入口处理器用于通过将数据流的设定传输速率与估计的公平传输速率进行比较，对给定数据流的新到达数据包进行优先级排序，其中优先级排序包括：将数据包转发到优先级fifo队列以进行传输。
69.更新时间间隔可选地是接收前一个数据包与接收所述数据包之间经过的时间间隔。
70.根据第四实施例，目标队列基于虚拟队列列表的固定顺序设置。可选地，目标队列基于虚拟队列列表中的伪随机选择设置。可选地，目标队列还基于虚拟队列列表中的每个虚拟队列的权重设置。可选地，减少目标队列包括：如果目标队列为空，则从虚拟队列列表中删除目标队列。
71.根据第五实施例，如果在减少目标队列之后目标队列为空，则通过存储信用额度的余值来减少信用额度。
72.根据第六实施例，所述方法包括：估计公平传输速率，并通过以下至少一项输出公平传输速率：(i)将公平传输速率添加到接收到的数据包的报头中，或(ii)将公平传输速率值导出到外部设备。
73.所述方法可以在(i)(例如，单个设备中的)本地级别，(ii)端到端(即数据流)级别，或(iii)全局级别(即网络级别)实现。在实施例中，所述方法可以基于丢弃以超过其公平传输速率发送的数据流的数据包而在本地级别实现。在实施例中，所述方法可以通过改变数据流发送方的行为超过其公平传输速率来在端到端级别实现。在实施例中，所述方法可以在涉及改变网络配置以实现目标公平传输速率的全局级别上实现。
74.如果所述方法是在本地级别实现的，所述方法能够通过丢弃数据包来实施近似公平带宽共享，并且可以与为具有隐式或显式信令的协作源或具有本地或远程实施的非协作源量身定制的端到端方法互操作(即，可以结合使用)。在本地级别，所述方法限制在数据包的每个新到达时需要更新的数据流的量，以实施公平带宽共享。在本地级别，所述方法能够更新最小可能的状态量，即单个数据流。在本地级别，所述方法测量和实施在设备调度器上并置的公平传输速率。在本地级别，公平带宽共享的实施是使用主动队列管理(例如，数据包的丢弃)实现的。在本地级别，公平传输速率的信令可以使用显式拥塞通知(explicit congestion notification，ecn)字段或通过重置互联网协议(internet protocol，ip)的接收窗口(rwnd)字段或将公平传输速率估计添加到数据包报头(例如，对于远程直接存储器访问(remote direct memory access，rdma)数据中心网络)来执行。
75.在端到端级别，公平传输速率的测量在设备上执行。在实施例中，所述方法使用相同的算法(例如，第一算法和第二算法)来测量在本地级别使用的公平传输速率。在端到端级别，公平带宽共享的实施由以下至少一项执行：(i)用于协作源的情况的主机(例如，对数据包的ecn标记作出反应)或(ii)用于非协作源的设备(例如，重写确认(ack)数据包的数据包报头中的rwnd字段)。
76.在全局级别，公平传输速率的测量在多个设备上执行，并在中心点收集。在全局级别，公平带宽共享的实施是全局的，通过例如软件定义网络(software-defined networking，sdn)控制器之类的集中控制器或路径计算元件(path computation element，pce)实现。在全局级别，考虑数据的导出，因为公平传输速率统计信息被输入到控制器(例如，作为效用函数或约束)。所述方法可以通过全局管理资源利用率来减少问题，例如，通过
else)，然后采用比较(》阈值)或单个状态的增量(flow.vq)。
87.在实施例中，所述方法包括记录接收到的数据包的到达时间和数据包的大小的入口列表。可以基于数据流速率(＝最后到达的数据包大小/(当前时间-最后到达的数据包到达时间))与更新时间间隔的当前公平传输速率的比较来转发数据流。当数据包在fifo队列中排队等待转发时，入口流水线会对数据包使用时间戳。入口列表能减少延迟增强。如果接收到的数据包的数据流不在列表中，或者如果自上次到达以来的时间大于阈值时间，取决于当前估计的公平传输速率，则可以将接收到的数据包转发到优先级队列。
88.在端到端级别，所述方法使用第三算法和第四算法。在端到端级别，所述方法涵盖了(i)协作源中的隐式信令(显式拥塞通知标记)和显式信令(公平传输速率导出)的完整分类，和(ii)非协作源中的本地动作、远程实施(报头重写)以及本地动作和实施(调度器丢弃决定)。
89.在实施例中，如果协议重新设计是不可能的(例如tcp/ip互联网)，则利用显式拥塞通知(explicit congestion notification，ecn)进行有效操作。显式拥塞通知(explicit congestion notification，ecn)通过显式设置tcp/ip报头中的位(即携载数据流量上的信号)，在不丢弃数据包的情况下实现对网络拥塞进行端到端通知。当虚拟队列(virtual queue，vq)长度大于阈值最大大小时，所述方法不会丢弃接收到的数据包，而是将此类数据包的一个ecn位设置为1。这允许带内数据平面信令，而不需要显式公平传输速率导出，将实施委托给源。
90.在显式信令(公平传输速率导出)中，所述方法通过以下项转发用于能自由进行协议重新设计的围墙花园场景(例如数据中心/rdma)的公平传输速率信息：(a)本地设备，其向数据包报头添加字段，能够计算公平传输速率(即数据平面信令)，并发信号通知当前公平传输速率，或(b)专用控制协议，即控制平面信令，以可配置的时间间隔导出公平传输速率。
91.在具有远程实施(报头重写)的端到端方法中，可以通过重写配置文件外的流的rwnd报头字段来处理非协作源。rwnd报头字段设置为随公平传输速率而变化(即在数据平面中导出近似公平传输速率)。在实施(调度器丢弃决策)的本地方法中，应用第二较高阈值θ'》θ，以在存在数据流混合的情况下保持对无响应数据流的稳固性。如果属于数据流的虚拟队列的大小》θ，则数据包可以接收ecn标记。如果属于数据流的虚拟队列的大小》θ'，且θ《θ'，则将不转发或丢弃接收到的数据包，以在无响应流的情况下保持端到端级别的稳固性。
92.用于减少一个虚拟队列的第一算法如下：
93.使用的状态变量：c
–
业务速率。b
–
积压流集合，以head(b)开始的成员b的链表，credit
–
信用额度。
94.flow＝head(b)
95.如果credit《flow.vq，则
96.flow.vq-＝credit
97.credit＝0
98.否则，
99.credit-＝flow.vq
100.b＝b\flow
101.判断结束
102.如果|b|》0，则
103.head(b)＝next
104.判断结束
105.与数据包转发和丢弃相关的第二算法如下：
106.使用的状态变量：c
–
业务速率。b
–
积压流集合，成员b、θ
–
阈值的链表，tlast
–
上次更新时间，credit
–
信用额度。
107.time()
–
数据包到达时间。在实施例中，time(0)是当前处理器时钟时间。在另一实施例中，它是先前在数据包元数据中设置的时间戳的值。
108.输入pkt
109.credit+＝c
×
(time()—tlast)
110.tlast＝time()
111.如果flow(pkt)∈b，则
112.如果flow.vq》θ，则
113.丢弃packet
114.否则，
115.flow.vq+＝packet.length
116.判断结束
117.否则，
118.b＝b∪flow
119.flow.vq＝packet.length
120.向链表尾部添加flow
121.判断结束
122.如果导出，则
123.返回公平速率估计，例如c/|b|
124.判断结束
125.第三算法如下：
126.使用的状态变量：c
–
业务速率。b
–
积压数据流集合，成员b、θ、θ
′
–
阈值(θ《θ
′
)的链表，tlast
–
上次更新的时间，credit
–
信用额度，time()
–
数据包到达时间。
127.输入pkt
128.credit+＝c
×
(time()—tlast)
129.tlast＝time()
130.如果flow(pkt)∈b，则
131.如果flow.vq》θ
′
，则
132.丢弃packet
133.否则，
134.如果flow.vq》θ，则
135.设置报头中的ecn位
136.判断结束
137.flow.vq+＝packet.length
138.判断结束
139.否则，
140.b＝b∪flow
141.flow.vq＝packet.length
142.向链表尾部添加flow
143.判断结束
144.如果导出，则
145.返回公平速率估计，例如c/|b|
146.判断结束
147.在另一实施例中，基于数据包长度增加虚拟队列大小，然后将增加的虚拟队列大小与阈值进行比较，以确定是否丢弃数据包。
148.用ecn和rwnd重置实现数据包转发的第四算法如下：
149.使用的状态变量：c-业务速率。b
–
积压流集合，成员b、θ、θ
′
–
阈值(θ《θ
′
)的链表，tlast
–
上次更新的时间，credit
–
信用额度，time()
–
数据包到达时间，rtt
–
rtt估计。
150.输入pkt
151.credit+＝c
×
(time()
–
tlast)
152.tlast＝time()
153.如果flow(pkt)∈b，则
154.如果flow.vq》θ
′
，则
155.使用公平速率估计重置rwnd
156.例如，rwnd＝c/|b|
×
rtt
157.否则，
158.如果flow.vq》θ，则
159.设置报头中的ecn位
160.判断结束
161.flow.vq+＝packet.length
162.判断结束
163.否则，
164.b＝b∪flow
165.flow.vq＝packet.length
166.向链表尾部添加flow
167.判断结束
168.如果导出，则
169.返回公平速率估计，例如c/|b|
170.判断结束
171.当一些数据流以使带宽饱和的速率发出数据包时，所述方法可在互联网路由器中使用以实施公平共享。所述方法还可用于在数据中心网络中实施公平共享链路容量。这些算法特别可以在服务器到架顶(top of rack，tor)交换机方向的数据流的服务器中以及在
tor到服务器方向的数据流的tor交换机中实现。所述方法用于提高无损远程直接存储器存取(remote direct memory access，rdma)数据中心网络的性能。第二算法提供对当前公平传输速率的估计，并且这可用于确定适当的源传输速率(即公平速率)。如果源将数据包发射调整到公平传输速率，则不会出现数据包丢失和可忽略不计的延迟。
172.图6示出了示例性计算设备600，其中可以实现各种先前实施例的各种体系结构和/或功能。如图所示，计算设备600被提供为包括连接到总线602的至少一个处理器604，其中计算设备600可以使用任何合适的协议来实现，例如外围部件互连标准(peripheral component interconnect，pci)、pci-express、加速图像处理端口(accelerated graphics port，agp)、ht总线(hypertransport)，或任何其它总线或点对点通信协议。计算设备600还包括数据存储器606。
173.控制逻辑(软件)和数据存储在存储器606中，所述存储器可以采取随机存取存储器(random-access memory，ram)的形式。在本描述中，单个半导体平台可以指唯一的基于单一半导体的集成电路或芯片。应注意，术语单个半导体平台还可以指具有增加连接性的多芯片模块，所述多芯片模块模拟具有增加连接性的芯片上模块，所述芯片上模块模拟芯片上操作，并且与利用常规的中央处理器(central processing unit，cpu)和总线实现相比作出实质性改进。当然，根据用户的期望，各种模块也可以单独地放置或以半导体平台的各种组合放置。
174.计算设备600还可以包括辅助存储器610。辅助存储器610包括例如硬盘驱动器、表示软盘驱动器的可移动存储驱动器、磁带驱动器、压缩盘驱动器、数字多功能盘(digital versatile disk，dvd)驱动器、记录设备、通用串行总线(universal serial bus，usb)闪存。可移动存储驱动器以众所周知的方式进行以下至少一项：从可移动存储单元读取和写入可移动存储单元。
175.计算机程序或计算机控制逻辑算法可以存储在存储器606和/或辅助存储器610中。当执行这样的计算机程序时，使系统600能够执行各种功能。存储器606、辅助存储器610和/或任何其它存储器是计算机可读介质的可能示例。
176.在实施例中，各种先前附图的体系结构和功能可以在处理器604、耦合到通信接口612的图形处理器、能够具有处理器604和图形处理器两者的至少一部分能力的集成电路(未示出)、芯片组(即，一组集成电路，设计成作为执行相关功能等的单元工作和销售)，和/或与此相关的任何其它集成电路的上下文中实现。
177.然而，各种先前附图的体系结构和功能可以在一般计算机系统、电路板系统、专用于娱乐目的的游戏控制台系统、特定于应用的系统和/或任何其它所需系统的上下文中实现。例如，计算设备600可以采取台式计算机、笔记本电脑、服务器、工作站、游戏机、嵌入式系统和/或任何其它类型的逻辑的形式。
178.然而，计算设备600可以采取各种其它设备的形式，包括但不限于个人数字助理(personal digital assistant，pda)设备、移动电话设备、电视等。此外，虽然未示出，但计算设备600可以耦合到网络(例如，电信网络、局域网(local area network，lan)、无线网络，例如互联网、对等网络、电缆网络等广域网(wide area network，wan))以通过i/o接口608进行通信。
179.应理解，在所描述的附图中示出的部件的布置是示例性的，并且其它布置也是可
能的。还应理解，由权利要求定义的、下文描述的并在各种框图中示出的各种系统部件(和构件)表示根据本文公开的主题配置的一些系统中的部件。例如，这些系统部件(和构件)中的一个或多个可以全部或部分地通过在所描述的附图中所示的布置中所示的部件中的至少一些实现。
180.此外，虽然这些组件中的至少一个至少部分地实现为电子硬件组件，并因此构成机器，但其它组件可以在软件中实现，当所述软件包括在执行环境中时，构成机器、硬件或软件和硬件的组合。计算机程序可存储或分配到合适的介质上，例如与其它硬件一起或者作为其它硬件的部分提供的光存储介质或者固态介质，还可以以其它形式例如通过互联网或者其它有线或无线电信系统分配。
181.尽管已详细描述了本发明及其优点，但是应当理解，在不脱离所附权利要求书界定的本发明的精神和范围的情况下，可以作出各种改变、替代和更改。

技术特征：
1.一种计算机实现的管理数据传输的方法，其特征在于，所述方法包括：处理器(102)接收属于多个数据流中的一个数据流的数据包；所述处理器(102)基于所述接收到的数据包所属的所述数据流从虚拟队列列表中识别虚拟队列；所述处理器(102)判断所述识别的虚拟队列大小是否超过阈值最大大小，并基于所述确定的结果：基于所述接收到的数据包的大小，增加所述识别的虚拟队列；转发所述接收到的数据包；所述处理器(102)将所述虚拟队列列表中的虚拟队列设置为目标队列；所述处理器(102)基于更新时间间隔确定业务容量，并基于所述确定的业务容量增加信用额度；所述处理器(102)基于信用额度大小将所述目标队列减少一个量，并将所述信用额度减少相同的量。2.根据权利要求1所述的计算机实现的方法，其特征在于，如果确定所述虚拟队列大小超过所述阈值最大大小，则不转发所述接收到的数据包，且不基于所述接收到的数据包的所述大小增加所述识别的虚拟队列。3.根据权利要求1所述的计算机实现的方法，其特征在于，如果确定所述虚拟队列大小超过所述阈值最大大小，则在转发所述接收到的数据包之前，将网络拥塞的通知添加到所述接收到的数据包的报头中。4.根据前述权利要求中任一项所述的计算机实现的方法，其特征在于，如果所述虚拟队列列表不包括与所述接收到的数据包对应的所述数据流相对应的虚拟队列，则识别所述虚拟队列包括：将新的虚拟队列添加到所述虚拟队列列表中。5.根据前述权利要求中任一项所述的计算机实现的方法，其特征在于，转发所述接收到的数据包包括：将所述接收到的数据包转发到物理先进先出(first-in-first-out，fifo)队列进行传输。6.根据前述权利要求中任一项所述的计算机实现的方法，其特征在于，转发所述接收到的数据包包括：判断所述识别的虚拟队列大小是否超过阈值最小大小，如果所述识别的虚拟队列大小不超过所述阈值最小大小，则将所述数据包转发到优先级fifo队列进行传输。7.根据权利要求1至4中任一项所述的计算机实现的方法，其特征在于，接收所述数据包包括：从物理fifo队列接收所述数据包，转发所述接收到的数据包包括：将所述接收到的数据包转发到输出端口进行传输。8.根据权利要求7所述的计算机实现的方法，其特征在于，所述更新时间间隔是前一个数据包的时间戳与所述数据包的时间戳之间经过的时间间隔，其中所述数据包的所述时间戳是基于进入所述物理fifo队列的相应时间的。9.根据权利要求7或8所述的计算机实现的方法，其特征在于，还包括：估计公平传输速率，并将所述估计的公平传输速率发送到所述物理fifo队列的入口处理器，其中所述入口处理器用于通过将所述数据流的设定传输速率与所述估计的公平传输速率进行比较，对给定数据流的新到达数据包进行优先级排序，其中优先级排序包括：将所述数据包转发到优
先级fifo队列进行传输。10.根据权利要求5或6所述的计算机实现的方法，其特征在于，所述更新时间间隔是接收前一个数据包与接收所述数据包之间经过的时间间隔。11.根据前述权利要求中任一项所述的计算机实现的方法，其特征在于，所述目标队列基于所述虚拟队列列表的固定顺序设置。12.根据权利要求1至10中任一项所述的计算机实现的方法，其特征在于，所述目标队列基于所述虚拟队列列表中的伪随机选择设置。13.根据权利要求11或权利要求12所述的计算机实现的方法，其特征在于，所述目标队列还基于所述虚拟队列列表中的每个虚拟队列的权重设置。14.根据前述权利要求中任一项所述的计算机实现的方法，其特征在于，减少所述目标队列包括：如果所述目标队列为空，则从所述虚拟队列列表中删除所述目标队列。15.根据前述权利要求中任一项所述的计算机实现的方法，其特征在于，减少所述信用额度包括：如果在减少所述目标队列之后所述目标队列为空，则存储所述信用额度的余值。16.根据前述权利要求中任一项所述的计算机实现的方法，其特征在于，还包括：估计公平传输速率，并通过以下至少一项输出所述公平传输速率：(i)将所述公平传输速率添加到所述接收到的数据包的报头中，或(ii)将所述公平传输速率值转发到外部设备。17.一种计算设备(104)，其特征在于，所述计算设备包括处理器(102)并用于执行前述权利要求中任一项所述的方法。18.一种计算机程序，其特征在于，当由处理器(102)执行时，所述计算机程序使所述处理器(102)执行权利要求1至16中任一项所述的方法。19.一种计算机可读介质，其特征在于，所述计算机可读介质包括指令，当由处理器(102)执行时，所述指令使所述处理器(102)执行权利要求1至16中任一项所述的方法。

技术总结
本发明提供了一种计算机实现的管理数据传输的方法，用于在网络中进行带宽公平共享。所述方法包括：接收数据包；从所述数据包所属的虚拟队列列表中识别虚拟队列。所述方法包括：判断所述识别的虚拟队列大小是否超过阈值最大大小，并基于确定的结果：基于所述数据包的大小增加所述识别的虚拟队列；转发所述数据包。所述方法包括：将所述虚拟队列列表中的虚拟队列设置为目标队列。所述方法包括：基于更新时间间隔确定业务容量，并基于所述业务容量增加信用额度；基于信用额度大小将所述目标队列减少一个量，并将所述信用额度减少相同的量。量。量。


技术研发人员：詹姆斯
受保护的技术使用者：华为技术有限公司
技术研发日：2020.10.26
技术公布日：2023/8/1