CN102763385B - 用于计算机网络中的拥塞控制的方法和设备 - Google Patents

Abstract

用于计算机网络中拥塞控制的方法和设备通过浅缓冲的交换机来实现高突发容忍度、低等待时间和高吞吐量。一种用于控制拥塞的方法包括：在网络连接上，将一组数据分组从第一计算设备传送到第二计算设备；识别该组数据分组中的在该网络连接上经历了拥塞的每个数据分组；由第二计算设备将代表该组数据分组中被识别为经历过拥塞的数据分组的数量的比特序列发送到第一计算设备；以及基于发送到第一计算设备的所述比特序列，调整在所述网络连接上传送数据分组的速率。

Description

用于计算机网络中的拥塞控制的方法和设备

技术领域

本发明涉及在计算机网络中的拥塞控制，以及更特别地，涉及用于在数据中心环境中控制拥塞的方法和设备。然而，本发明不限于在数据中心环境中使用。

背景技术

数据中心可以包括通过高速交换机互连的几百或几千个服务器。云数据中心宿有多种多样的应用，在同一网络中混合许多需要小的可预测的等待时间的工作流与其它需要大的持续的吞吐量的工作流。近些年，随着企业IT大规模地整合到数据中心枢纽（hub）中以及云计算服务提供者的出现，数据中心已经使计算发生转变。数据中心设计中一贯的主旨（theme）是使用低成本商品组件来构造高可用性的、高性能的计算和存储基础设施。特别地，低成本的交换机是常见的，其以低于$2000的价格提供多达48个1Gbps的端口。若干新近的研究提案设想使用在这样的商品交换机上构造的新颖的体系结构来创建经济的、易于管理的数据中心。

这些提案是否现实在很大程度上取决于这些商品交换机能多好地应付实际数据中心应用的通信量。已经发现，诸如web搜索、零售、广告和推荐系统这样的、已驱动许多数据中心建设的软实时应用生成短流和长流的多种多样的混合。这些应用要求来自数据中心网络的如下项：针对短流的低等待时间、高突发容忍度和针对长流的高利用率。

头两个要求源于这些应用中的许多应用所使用的分割/聚合（partition/aggregate）工作流模式（pattern）。针对最终结果的软实时截止时间转换为针对工作流中的一个个任务的等待时间目标。这些等待时间目标从大约10ms变化到大约100ms，并且在它们的截止时间前未完成的任务被取消，由此不利地影响了最终的结果。因此，针对低等待时间的应用要求直接地影响到返回的结果的质量并因此影响到了收益。降低网络等待时间允许应用开发者将更多的周期移转给用于改进相关性和最终用户体验的算法。

第三个要求（针对大流的高利用率）源于对连续不断地更新这些应用的内部数据结构的需要，因为该数据的新鲜度也影响到结果的质量。因此，针对更新数据的长流的高吞吐量与低等待时间和突发容忍度一样是必需的。

在这种环境中，今天的技术发展水平的TCP协议还达不到要求。因此，需要改进的方法和设备用于在诸如数据中心这样的计算机网络中进行有效的分组输送。

发明内容

本发明提供了用于拥塞控制的方法和设备，其通过浅缓冲的（shallow-buffered）交换机实现了高突发容忍度、低等待时间和高吞吐量。为了满足短流和长流的多种多样的混合的要求，交换机缓冲器被维持以小的队列占用，与此同时针对长流维持高的吞吐量。这些目标主要通过基于拥塞的程度对拥塞做出反应而实现。拥塞控制算法在交换机上使用标记方案，该标记方案是：只要缓冲器占用超过某个小的固定的门限，就在传送的数据分组中设置标记比特。发送器通过按取决于被标记分组的分率（fraction）的因子（factor）来降低传送数据分组的速率而进行响应。该分率越大，传输速率的减少越大。可以通过调整传输窗口的长度来控制传输速率。发送器从一组被传送分组的每个分组中的单比特的标记信息中导出多比特反馈。

按照本发明的第一方面，提供了一种用于控制在第一计算设备和第二计算设备间的网络连接上的拥塞的方法。所述方法包括：在网络连接上，将一组数据分组从第一计算设备传送到第二计算设备；识别该组数据分组中的在该网络连接上经历了拥塞的每个数据分组；由第二计算设备将代表该组数据分组中被识别为经历过拥塞的数据分组的数量的比特序列发送到第一计算设备；以及基于发送到第一计算设备的所述比特序列，调整在该网络连接上传送数据分组的速率。

按照本发明的第二方面，提供了一种用于控制在第一计算设备和第二计算设备间的网络连接上的拥塞的方法。该方法包括：在网络连接上，由第一计算设备将一组数据分组传送到第二计算设备；如果该网络连接上的设备中的队列大小超过预定的单值门限K，则标记该组被传送的数据分组中的数据分组；在第一计算设备上接收识别该组被传送的数据分组中的被标记数据分组的信息；在第一计算设备上基于该组数据分组中被识别为已标记的数据分组来估计网络连接上的拥塞的量度（measure）；以及由第一计算设备基于估计的拥塞的量度来调整在该网络连接上传送数据分组的速率。

按照本发明的第三方面，提供了一种用于控制在第一计算设备和第二计算设备间的网络连接上的拥塞的方法。该方法包括：在网络连接上，将一组数据分组从第一计算设备传送到第二计算设备；如果该网络连接上的设备中的队列大小超过预定的单值门限K，则标记该组被传送的数据分组中的数据分组；由第二计算设备将代表该组数据分组中被标记的数据分组的数量的比特序列发送到第一计算设备；通过基于所述比特序列确定该组被传送的数据分组中被标记数据分组的分率，来估计网络连接上的拥塞的量度；基于该组被传送的数据分组中被标记数据分组的分率来调整在该网络连接上传送数据分组的速率；以及针对每组被传送的数据分组来更新所估计的该网络连接上的拥塞的量度。

附图说明

在图中：

图1是图示分割/聚合工作流模式的示意图；

图2是图示在连接到聚合器的交换机上的incast（入播）拥塞的框图；

图3是依照本发明的实施例的、包括向接收器传送数据分组的发送器的计算机网络的框图；

图4图示了依照本发明的实施例的拥塞控制算法；

图5图示了由依照本发明的实施例的交换机进行的数据分组的标记；

图6是图示依照本发明的实施例的拥塞控制算法的操作的流程图；

图7是在延迟确认的情形下控制ACK分组中的拥塞比特的设置的状态图；

图8是使用依照本发明的实施例的拥塞控制算法和常规的TCP的、在交换机上作为时间的函数的即时队列长度的标绘图；

图9是图示依照本发明的实施例的拥塞控制算法的操作和常规TCP的操作的例子的表；和

图10是一般性地图示在其中可以实施本发明的计算机系统的例子的框图。

具体实施方式

图1中所示的分割/聚合工作流模式是在数据中心中执行的许多大型web应用的基础。所述分割/聚合工作流模式包括最高级别聚合器100、连接到最高级别聚合器100的较低级别聚合器110和连接到各自的较低级别聚合器110的工作者（worker）120。聚合器100和110、以及工作者120可各自被实施为服务器。工作流模式可以利用任意数量的级别。

由最高级别聚合器100接收请求。来自应用的较高层的请求被分成片断，并被分派给较低级别中的工作者。工作者的响应被聚合以产生结果。Web搜索、社交网络内容组成和广告选择可以是基于这种工作流模式的。对于诸如这些的交互式的软实时应用来说，等待时间是关键的度量（metric），总的可允许的等待时间例如由顾客影响研究来确定。在减去典型的因特网和再现延迟后，应用的后端部分典型地被分配在230-300ms之间。

许多应用具有多层分割/聚合工作流模式，在一层上的滞后延迟了其它层的启动。此外，对请求的响应可能要求迭代地调用该工作流模式，使某个聚合器对下面的工作者做出一系列请求以便准备响应。例如，在web搜索中，可以发送查询到许多聚合器和工作者，它们中的每个负责索引的不同部分。基于答复，聚合器可以提炼查询并发送所提炼的查询来改进结果的相关性。分割/聚合工作流的滞后实例因此会合起来危及查询的总的等待时间。

为了防止总的等待时间被违反，工作者节点典型地被分派严格的截止时间，通常大约为10-100ms。图1中显示了用于完成工作的截止时间的例子。当节点错过它的截止时间时，计算在没有那个响应的情况下继续进行，降低了结果的质量。

本发明是基于对在数据中心中观察到的性能损害的理解。数据中心可以包括服务器的多个机架（rack）。每个机架可以包括连接到交换机的多个服务器，例如44个服务器。交换机可以是浅缓冲的、共享存储器的交换机，每一个交换机具有在以1Gbps操作的48个端口间和以10Gbps操作的两个端口间共享的4MB的缓冲器。交换机是共享存储器的交换机，其通过使用所有交换机端口可用的逻辑上公用的分组缓冲器来利用统计复用增益。到达接口的分组被存储在由所有接口共享的高速的、有多端口的存储器中。来自于共享池中的存储器被存储器管理单元（MMU）动态地分配给分组。MMU试图给予每个接口跟它所需要的一样多的存储器，与此同时通过动态地调整任何一个接口可以得到的存储器的最大量来防止不公平。如果对于某个外出的接口，分组必须被排队，但是该接口已经达到它的最大的存储器分配或者共享的存储器池已耗尽，则该分组被丢弃。大的、有多端口的存储器是昂贵的，所以大部分的低成本交换机是浅缓冲的，其中分组缓冲器是最稀缺的资源。

如果许多数据流在短的时间段内会聚于交换机的同一接口上，则分组可能耗尽交换机存储器或用于该接口的最大被允许的缓冲器，导致某些流的分组丢失。即使流较小，这也可能发生。导致分组丢失的通信量模式自然是由使用分割/聚合工作流模式而引发的，因为针对数据的请求使工作者的响应同步并且在连接到聚合器的交换机端口的队列上引起了incast。图2中所示的网络200的图图示了incast拥塞。客户机210经由交换机230向N个服务器220发送请求。网络200可以在图1中图示的分割/聚合工作流模型上操作，其中客户机210对应于聚合器100而服务器220对应于较低级别的聚合器110。服务器们220可以同时发送响应，导致在交换机230上发生incast拥塞。类似incast的问题使性能降级，以及更重要的是使用户体验降级。经历incast拥塞的响应很可能错过聚合器截止时间并且不被计入最后的结果。

长时间的TCP流导致瓶颈队列的长度增长直到分组被丢弃。当长流和短流经过同一队列时，发生两种损害。首先，在短流上的分组丢失可导致如上所述的incast问题。其次，有队列聚集（buildup）损害。即便在没有分组丢失时，短流也经历了增加的等待时间，因为在队列中它们处在大流的分组之后。每个工作者都在既操控队列通信量又操控后台通信量，所以这个通信量模式频繁地发生。因此，一个问题是由其它流（后台通信量）导致的队列的占用，当长流和短流刚好重合时发生丢失。因为等待时间是由排队导致的，所以解决方案是降低队列的大小。

假定在数据中心中有长流和短流的混合，则常见的是，在一个端口上的短流受到在许多其它端口的任意一个上的活动的影响。出人意料的是，在该通信量模式中短流的丢失率取决于经过其它端口的长流的数量。解释是：在不同端口上的活动通过共享的存储器池被耦联。长的TCP流在它们的各自的接口上构造队列。因为缓冲器空间是共享资源，所以队列构造降低了可用来吸收来自分割/聚合通信量的通信量突发的缓冲器空间的量。这种损害称作“缓冲器压力”。其结果是分组丢失和超时，如在incast中一样，但没有要求同步的流。

称为DCTCP算法的拥塞控制算法解决了以上所述的性能损害。DCTCP算法的目标是通过商品（commodity）浅缓冲交换机实现高突发容忍度、低等待时间和高吞吐量。为此目的，DCTCP被设计成以小的队列占用来操作而没有吞吐量的损失。

图3中显示了在DCTCP算法的操作中牵涉到的网络组件的简化框图。发送器300在包括交换机320和322的网络连接312上将数据分组302传送到接收器310。交换机320包括缓冲器330，而交换机322包括缓冲器332。缓冲器330和332的每一个可以具有等待传输的数据分组的队列。交换机320和322可以分别在一个或多个接口334和336上接收另外的数据流。当缓冲器332中的队列大小超过门限时，数据分组306可以由交换机322进行标记，正如以下描述的。标记数据分组306的示例性实现是设置显式拥塞通知码点CE，如在IETFRFC3168“TheAdditionofExplicitCongestionNotification(ECN)toIP”中定义的。接收器310可以通过向发送器300发送ACK分组304来确认数据分组302。每个ACK分组可以让ECN-Echo（ECN回送）标志被设置来指示相应的接收到的分组经历了拥塞。

如图3中所示，发送器300可以包括希望向接收器310传送数据分组的应用340和用于按如下所述控制数据分组的传输速率的传输速率控制器342。为了控制拥塞，接收器310包括ECN回送器（ECN-Echoer），以控制ACK分组中的ECN-Echo标志的设置，正如以下所述的。除了或者替换ECN回送器350，接收器310可以包括如下所述的拥塞推断器352和拥塞标记器354。在数据中心的语境中，发送器300和接收器310可以是服务器，使得发送器300是第一计算设备，而接收器310是第二计算设备。应当理解，图3仅图示了多个连接中的一个连接以及数据中心环境中的多个服务器中的两个服务器。

DCTCP算法通过基于拥塞的程度对拥塞做出反应而实现高突发容忍度、低等待时间和高吞吐量的目标。该算法在交换机上使用标记方案，该标记方案是只要缓冲器占用超过固定的小门限就置位数据分组的经历了拥塞（CE）的码点。发送器通过以取决于被标记分组的分率的因子来降低数据传输速率而做出反应。被标记分组的分率越大，传输速率减少得越大。在一些实施例中，传输速率的减少可以和被标记分组的分率成比例。

该算法从一组数据分组中的每个数据分组的被标记或未标记的状态中所包含的单比特导出多比特反馈。该组数据分组可以是在传输窗口期间传送的数据分组，该窗口也被称为拥塞窗口cwnd。因为DCTCP算法要求网络仅提供单比特反馈，所以可以利用在现代TCP栈和交换机中已经可用的许多功能性。

在缺乏大规模统计复用时，特别强烈地需要基于拥塞的程度做出反应。标准TCP在它接收到ECN通知时，将它的窗口大小降低到二分之一，即TCP-ECN针对每个拥塞窗口的单个被标记的分组做出反应。实际上，TCP是对拥塞的出现，而不是对它的程度做出反应。将窗口减半导致了到链路的输入速率和可用容量间的大的失配。在其中仅有较少数量的流共享缓冲器的高速数据中心环境中，这导致了缓冲器下溢以及吞吐量的损失。

DCTCP算法具有三个主要的部分，如图4所概括的。第一部分400是在交换机320、322上标记数据分组。该算法采用主动队列管理方案，如图5所示。标记门限K是唯一的参数。如由标记特性500所指示的，如果分组到达后的队列占用大于门限K，则例如用CE码点来标记到达的分组。否则，不标记到达的分组。DCTCP标记方案由最小化队列聚集的需要来推动。当感测到队列过冲（overshoot）时，DCTCP算法积极地标记分组，因此允许发送器被尽可能快地通知队列过冲。

DCTCP算法的第二部分410是在接收器310上的ECN-Echo。DCTCP接收器与常规TCP接收器的区别在于将CE码点中的信息传达回发送器的方式。TCP接收器在一系列ACK分组中置位ECN-Echo标志，直到它接收到来自发送器的已经接收到拥塞通知的确认。如在RFC3168中所描述的，TCP接收器的显式目标是在每个往返时间（RTT）通知TCP发送器至多一个拥塞信号。然而，DCTCP接收器将被标记分组的准确序列精确地传达回发送器。实现这一点的一种方式是确认每个分组，当且仅当该分组具有被标记的CE码点时，置位ECN-Echo标志。

然而，因为各种各样的原因，延迟的确认是很重要的，所述原因包括降低发送器上的负荷。延迟的确认对每m个连续接收的分组使用一个累积的ACK分组。为了使用延迟的确认，DCTCP接收器使用图7中所示的两状态状态机来确定是否发送具有恰当的ECN-Echo比特的ACK分组。所述状态对应于上一个接收到的分组是否用CE码点进行了标记。因此，常规的延迟的ACK通过以下方式修改，即：每次当接收到的分组的标记比特改变状态时发送ACK分组。因为发送器知道每个ACK分组覆盖多少被传送的分组，所以它可以准确地重新构建由接收器接收的被标记的分组。

DCTCP算法的第三部分420是发送器300上的控制器。发送器维持对被标记分组的分率的被称为的连续的（running）估计，其如下地针对每个数据窗口（粗略地为一个RTT）更新一次：

（1）

其中，F是在上一个数据窗口中被标记的分组的分率，以及g是相对于先前的估计给予新样本的权重，其值在0-1的范围内。

可能要注意到是实数，其值为0到1之间。假定当队列长度大于K时，发送器对于每个分组均接收到标记，而当队列长度小于K时发送器没有接收到任何标记，等式（1）意味着是对队列大于K的概率的估计。因此，值接近于0指示低的拥塞水平，而值接近于1指示高的拥塞水平。

如上所述，就其对接收到具有被置位的ECN-Echo标记的ACK分组的反应而论，DCTCP发送器不同于TCP发送器。TCP的其他特征——诸如缓慢启动、拥塞避免中的加性增大以及分组丢失的恢复——保持不变。虽然TCP响应于被标记的ACK分组来将它的窗口大小缩减一半，但DCTCP算法却如下地使用来减小它的窗口cwnd：

(2)。

因此，当的值接近0时（低拥塞）时，所述窗口被稍微地减小。队列大小一旦超过K,DCTCP发送器就开始减小它们的窗口大小。DCTCP算法因此维持低的队列大小，与此同时保证高吞吐量。当的值接近于1（高拥塞）时，DCTCP算法将它的窗口减小一半，如在TCP中一样。

发送器已经被描述为基于一组数据分组中被标记的数据分组的分率来调整它的传输窗口或拥塞窗口。然而，本发明并不限于这个方面，在本发明的范围内可以利用其它的调整传输速率的方法。

DCTCP算法牵涉到门限K以及权重g的选择，门限K是交换机中触发标记的队列大小门限，权重g是相对于的先前估计而给予的新样本的权重。可以基于下面的指导方针来选择门限K和权重g的值。

（3）

（4）

其中，C是以分组/秒计的网络连接的容量，RTT是以秒计的往返时间，以及门限K是以分组计的。在选择门限K的值时，可以把分组突发考虑进去。例如，尽管等式（3）针对10Gbps可以建议低至20个分组的标记门限K，但是可以使用大于60个分组的更保守的标记门限来避免吞吐量的损失。该超额量与在10Gbps上观察到的30到40个分组的突发大小相一致。

基于在1Gbps和10Gbps上观察到的分组突发以及交换机中可用的缓冲的总量，可以利用针对1Gbps端口的20个分组的标记门限K和针对10Gbps端口的65个分组的标记门限K，并且权重g可设置为1/16。应当理解，这些值仅仅是作为例子给出的，并不限制本发明的范围。类似地，应当理解门限K可以以字节、或缓冲器空间的单元以及分组为单位来表示。

在接口上的队列长度一旦超过门限K，DCTCP发送器就开始做出反应。这降低了拥塞的交换机端口上的排队延迟，其使得长流对小流的完成时间的影响最小化。而且，更多的缓冲器空间可用作为动态余量（headroom）来吸收瞬时的微突发（microburst），从而极大地减轻了可能导致超时的、代价昂贵的分组丢失。

DCTCP算法也解决了缓冲器压力问题，因为拥塞的端口的队列长度并不会增长得过大。因此，在共享存储器的交换机中，少数拥塞的端口将不会耗尽缓冲器资源，从而损害通过其它端口的流。

其中有大量同步的小流抵达同一队列的incast情景是最难以处理的。如果小流的数量如此之高，使得在同步的突发上甚至来自每个流的一个分组都足以淹没缓冲器，则任何不试图调度通信量的拥塞控制方案对于避免分组丢失能做的都很少。

然而，在实践中，每个流都有几个分组要传送并且它们的窗口建立在多个RTT上。经常是随后的RTT中的突发导致分组丢失。因为DCTCP算法在早期且积极地基于即时队列长度开始进行标记，所以DCTCP发送器在头一或头二个RTT期间接收到足够的标记来降低后续突发的大小，从而防止了缓冲器上溢。

图6中显示了概括DCTCP算法的操作的流程图。图6的操作是参考图3的网络图描述的。在动作600中，发送器300在连接312上将一组分组302传送到发送器310。该组分组可以是在传输窗口期间被传送的数据分组。

在动作602，例如通过置位CE码点来标记经历了拥塞的被传送的数据分组。如上所述，如果在诸如交换机320和322的交换机中的队列大小超过门限K，则标记被传送的分组。否则，不标记数据分组。图3中显示了被标记的数据分组306。

在动作604，接收器310将由接收器310接收的该组数据分组中的每个被标记的分组通知给发送器300。在其中每个数据分组被单独确认的情形中，接收器310可以在ACK分组304中置位ECN-Echo比特来指示接收到了被标记的分组。未标记的数据分组被以不置位ECN-Echo比特的方式确认。因此，发送器300接收ACK分组，并且具有被置位的ECN-Echo比特的分组的数量是基于该组分组所经历的拥塞的程度。

在动作606，发送器300估计在该组被传送的数据分组中被标记分组的分率。该信息从由接收器310返回的每个ACK分组中的ECN-Echo比特导出。因此，发送器300从每个ACK分组中包含的单比特信息（ECN-Echo比特）导出多比特信息。

在动作608，被标记分组的分率的连续估计由发送器300使用上述等式（1）进行更新。在动作610，随后的多组的数据分组的传输速率基于在动作608中确定的被更新的连续估计进行调整。如以上讨论的，所述传输速率可以基于被标记分组的分率而减小，所述分率代表网络连接312上的拥塞的程度。

在以上的DCTCP算法的描述中，当网络连接中的交换机上的队列大小超过门限K时，在该交换机上标记被传送的数据分组。该组被标记和未被标记的分组被使用来估计网络连接上的拥塞的程度。在其他的实施例中，图3中所示的拥塞推断器352和拥塞标记器354被用作为对于在交换机上标记分组的替换。

拥塞推断器352观察由接收器310接收的分组。其通过记录每个分组或分组群被接收的时间以及接收到的分组的数量来估计将接收器310连接到最后一跳交换机322的链路的利用率。以比特/秒计的链路容量是已知的，所以拥塞推断器352通过将在持续时间期间接收的比特除以容量与持续时间的乘积而获得链路利用率的估计。典型的持续时间可以是10毫秒、100毫秒或500毫秒。如果链路利用率高于门限（典型地为90%到95%），则拥塞推断器352确定在最后一跳交换机322上一定有足够长的队列以至于在该交换机上存在拥塞。所述系统然后就如同在该持续时间以及下一个持续时间内接收到的所有分组均是以CE拥塞比特置位的方式被接收的那样继续进行。拥塞标记器354将ACK分组以ECN-Echo比特被置位的方式返回给发送器300。当估计的利用率高于门限值时，发送器300基于被标记分组的分率估计拥塞的程度，并如上所述地调整传输速率。

图8图示了与TCP相比较的、DCTCP算法在实现完全吞吐量而同时占用一小部分交换机分组缓冲器中的有效性。图8中，曲线800代表对于DCTCP算法的作为时间的函数的即时队列长度，以及曲线810代表对于常规TCP的即时队列长度。该队列长度是在BroadcomTriumph交换机上被测量的。两个长流从不同的1Gbps端口送出到公用的1Gbps端口。所述交换机已使能动态存储器管理，允许到公用的接收器的流动态地占用高达缓冲器的700Kb。

图9显示了DCTCP算法和常规TCP的性能的比较。在第一个例子中，一组10个分组中的8个分组有ECN-Echo比特置位。DCTCP算法将传输窗口缩减40%，而TCP将传输窗口缩减50%。在第二个例子中，一组10个分组中的一个分组有ECN-Echo比特置位。DCTCP算法将传输窗口缩减5%，而TCP将传输窗口缩减50%。这些例子说明了DCTCP算法适应于由被标记分组的分率所指示的拥塞的程度，而TCP在任何拥塞面前都将传输窗口缩减50%。

在一个实施例中，传输速率控制器342、拥塞推断器352、拥塞标记器354和ECN回送器350被合并到传输控制协议中，并在服务器300和接收器310的网络栈中实施。这个实施例具有的优点在于，任何使用TCP连接的应用340将得到本发明的好处。在另一个实施例中，这些单元被合并到由应用340所使用的库中。在这个实施例中，接收器310上的应用或所述库负责将拥塞信息304发送给发送器300。所述反馈可以正好是经历的拥塞的量，并可按所希望的那样频繁地被发送，每个RTT发送一次会是最佳的。该实施例具有的优点在于，使用TCP连接以外的某种东西（例如，数据的UDP流）进行通信的应用340可以得到本发明的好处。其它的实施例也是可能的，比如将传输速率控制器342合并到应用340中，以及将拥塞推断器352、拥塞标记器354和ECN回送器350合并到接收器310的网络栈中。

在另一个实施例中，传输速率控制器342被合并到接收器310的网络栈或TCP代码中，并且该接收器通过在它发送到发送器300的确认分组304中设置TCP接收器通告窗口来控制发送器300发送数据的速率。通过增大通告的接收器窗口来增大发送速率，以及通过减小通告的接收器窗口来减小发送速率。

被称为ECN-hat的在前的工作对在某个时间段内接收的ECN通知的平均数量做出反应。在ECN-hat中，TCP发送器保存它已经接收到的ECN通知的数量的连续平均。当TCP发送器接收到第一个ECN通知时，它基于当前的平均来降低拥塞窗口。直到至少数据的拥塞窗口已经被发送，它才将再一次调整拥塞窗口。在数据的拥塞窗口已经被发送之前接收到的任何另外的ECN通知被累积到ECN通知的连续平均中，但不导致对拥塞窗口的进一步调整。本发明通过引入新的ECN-回送器350、可选的拥塞推断器352和拥塞标记器354以及在传输速率控制器342中使用如等式（1）和（2）所示的不同的规则而不同于ECN-hat。DCTCP算法还规定每当即时队列长度大于门限K时可以在网络交换机320、322中标记分组，以及应当如何确定门限值K（例如，等式（3）和（4））。本发明还解释了可以如何把传输速率控制器342合并到应用340或由该应用使用的通信库中。

被称为随机早期丢弃（RED）或随机早期标记（REM）的在前的工作通过由网络交换机计算分组队列的长度的平滑估计来操作。当经平滑的队列长度大于值最小的门限且小于值最大的门限并且有分组到达该队列时，以某个概率丢弃（在RED中）或标记（在REM中）该分组，所述概率是按照最大丢弃率乘以（最大门限-当前经平滑的队列长度-最小门限）除以（最大门限-最小门限）计算的，其中最大丢弃率、最小门限和最大门限是必须提供给交换机的参数。RED、REM及其变体（例如，PI和其它形式的主动队列管理）间的主要不同在于：在那些系统中，确定应该何时缩减发送器的拥塞窗口的速率控制器的必要部分是位于交换机上，在那里它不具有任何的按每个流的信息并因此必须使用类似于本段中的那些的概率公式（当发送器缩减它的拥塞窗口时，它总是缩减到二分之一）。因此，控制器在实际上是基本无效的。在本发明中，传输速率控制器342位于发送器310或接收器310上，在那里它可以将拥塞通知与特定的流相关联，并且随时间的推移跟踪针对每个流的拥塞信息。

本发明已经联系数据中心应用予以显示和描述。然而，本发明并不局限于数据中心应用，而是可被利用在其它的计算机网络中，比如广域网（WAN）。尽管发送器300被描述为估计和更新网络连接上的拥塞的量度，但应当理解这些操作可以由接收器310执行，使结果被发送到发送器300用于调整传输速率。

参考图10，用于实施本发明的示范性系统包括计算设备，比如计算设备1000。在它的最基本的配置中，计算设备1000典型地包括至少一个处理单元1002和存储器1004。取决于计算设备的确切配置和类型，存储器1004可以是易失性的（比如，RAM）、非易失性的（比如，ROM、闪存等）或者这两者的某种组合。在图10中以虚线1006图示这个最基本的配置。另外，设备1000还可以具有附加的特征/功能性。例如，设备1000还可以包括附加的存储装置（可拆卸的和/或不可拆卸的），包括但不限于磁盘或光盘或磁带。在图10中这样的附加的存储装置是由可拆卸存储装置1008和不可拆卸存储装置1010图示的。计算机存储媒体包括以任何方法或技术实施的、用于存储诸如计算机可读指令、数据结构、程序模块或其它数据这样的信息的易失性和非易失性的、可拆卸和不可拆卸的媒体。存储器1004、可拆卸存储装置1008和不可拆卸存储装置1010都是计算机存储媒体的例子。计算机存储媒体包括但不限于RAM、ROM、EEPROM、闪存或其它的存储技术、CD-ROM、数字多功能盘（DVD）或其它的光学存储装置、盒式磁带、磁带、磁盘存储装置或其它的磁存储设备、或可被使用来存储想要的信息并可由设备1000访问的任何其它的介质。任何这样的计算机存储媒体可以是设备1000的一部分。

设备1000还可以包含允许该设备与其它设备进行通信的通信连接1012。设备1000还可以包括输入设备1014，诸如键盘、鼠标、笔、话音输入设备、触摸输入设备等等。还可以包括输出设备1016，诸如显示器、扬声器、打印机等等。所有这些设备在本领域是众所周知的，不需要详细地讨论。

这样，已描述了本发明的至少一个实施例的若干方面，应意识到，本领域的技术人员很容易想到各种替换、修改和改进。这样的替换、修改和改进都被确定为本公开内容的一部分，并且被确定为在本发明的精神和范围内。因此，以上的描述和附图仅仅是作为例子。

Claims (15)

1.一种用于控制在第一计算设备和第二计算设备间的网络连接上的拥塞的方法，包括：

在所述网络连接上，将一组数据分组从第一计算设备传送到第二计算设备；

识别该组数据分组中的在该网络连接上经历了拥塞的每个数据分组；

由第二计算设备通过发送针对以下项的标记信息来将该组数据分组中被识别为经历过拥塞的数据分组的准确序列传达到第一计算设备，即：

每M个连续接收的未被识别为经历过拥塞的分组的系列，其中M大于1；

每N个连续接收的被识别为经历过拥塞的分组的系列，其中N大于1；

每个在接收到被识别为未经历过拥塞的分组之后接收到的被识别为经历过拥塞的分组；和

每个在接收到被识别为经历过拥塞的分组之后接收到的被识别为未经历过拥塞的分组；和

基于发送到第一计算设备的所述标记信息，调整在所述网络连接上传送数据分组的速率。

2.权利要求1中定义的方法，其中发送包括：每当在接收到被识别为没有经历拥塞的分组之后第二计算设备接收到被识别为经历过拥塞的分组时发送ACK分组。

3.权利要求1中定义的方法，其中识别该组数据分组中的经历了拥塞的每个数据分组包括：第二计算设备估计在第二计算设备前的最后一跳网络设备上的队列长度，以及当一段时间内所述队列长度大于门限值时将数据分组识别为经历过拥塞。

4.权利要求3中定义的方法，其中估计队列长度包括：确定一段时间内到第二计算设备的链路的利用率，以及当所确定的利用率高于门限达一段时间时将数据分组识别为经历过拥塞。

5.权利要求1中定义的方法，其中识别包括：如果网络连接上设备中的队列大小超过预定的单值门限K，则标记被传送的数据分组，并且通知第一计算设备每个被标记的数据分组。

6.权利要求5中定义的方法，还包括：基于在该组被传送的数据分组中被标记的数据分组来估计所述网络连接上拥塞的量度，以及其中调整包括：基于在该组被传送的数据分组中被标记的数据分组的分率来调整传送分组的速率。

7.权利要求6中定义的方法，其中调整包括：与在该组被传送的数据分组中被标记的数据分组的分率成比例地来调整传送分组的速率。

8.权利要求6中定义的方法，其中估计包括：每一个往返时间更新该拥塞的量度一次。

9.权利要求6中定义的方法，其中调整包括：将数据分组传输窗口的长度按（）的因子来降低，其中是被标记数据分组的分率的经平滑的估计。

10.权利要求6中定义的方法，其中调整包括：第二计算设备通过调整接收器通告的窗口的大小来控制它接收的数据的量。

11.权利要求6中定义的方法，其中估计包括：针对每个数据分组传输窗口来更新在数据分组传输窗口中被标记分组的估计的分率。

12.权利要求6中定义的方法，其中估计包括按照下式来更新估计的拥塞的量度：

其中，是对被标记数据分组的分率的经平滑的估计，F是在上一组数据分组中的被标记数据分组的分率，以及g是相对于估计时的过去的样本而赋予新样本的权重。

13.权利要求5中定义的方法，还包括把门限K确定为支持网络连接的完全利用所要求的缓冲器空间的量加上容纳第一计算设备发送的最大突发大小所要求的缓冲器空间的量。

14.权利要求13定义的方法，其中支持网络连接的完全利用所要求的缓冲器空间的量被确定为C·RTT/7，其中C是以分组/秒计的网络连接的容量，RTT是以秒计的往返时间，以及门限K是以分组计。

15.一种用于控制在第一计算设备和第二计算设备间的网络连接上的拥塞的设备，包括：

用于在所述网络连接上将一组数据分组从第一计算设备传送到第二计算设备的装置；

用于识别该组数据分组中的在该网络连接上经历了拥塞的每个数据分组的装置；

用于在第二计算设备处通过发送针对以下项的标记信息来将该组数据分组中被识别为经历过拥塞的数据分组的准确序列传达到第一计算设备的装置：

每M个连续接收的未被识别为经历过拥塞的分组的系列，其中M大于1；

每N个连续接收的被识别为经历过拥塞的分组的系列，其中N大于1；和

每个在接收到被识别未为经历过拥塞的分组之后接收到的被识别为经历过拥塞的分组；

每个在接收到被识别为经历过拥塞的分组之后接收到的被识别为未经历过拥塞的分组；和

用于基于发送到第一计算设备的所述标记信息而调整在所述网络连接上传送数据分组的速率的装置。