在网络元件的芯片上缓冲存储器中实现周期性早期丢弃的系统和方法

摘要

根据本发明的原理对现有技术做出的一个发展是针对用于被称为周期性早期丢弃（PED）的缓冲器管理机制的系统和方法提出一种新方法。本发明建立在观察到针对TCP流量，可通过选择适当的分组丢弃频率稳定队列长度的基础上。对于TCP连接数量和各个RTT值分布的任意组合，存在一种防止队列上溢或下溢的理想分组丢弃频率。尽管理想的分组丢弃频率值可随时间的推移快速变化，对于受过去的丢包影响的TCP连接序列很敏感且多数不可以内联计算，但是可以根据某个误差幅度粗略估计该值，这个误差幅度允许在预定的延长时段范围内保持队列占用。PED机制旨在跟踪（未知的）理想的分组丢弃频率，根据队列占用的演变调整近似值，其中近似的分组丢失频率的校正在可与穿过队列的一组TCP连接的总时间常数比较的时标上发生。

说明书

政府支持确认

本发明根据美国能源部授予的Grant DE-EE0002887，在政府的支持 下做出。政府对本发明拥有一定的权限。

技术领域

本发明一般地涉及通信系统，更具体地说，涉及针对IP网络中网络元 件的分组缓冲器（packet buffer）的存储器分配。

背景技术

网络流是一系列数据分组，它们在网际协议（IP）分组头的源地址字 段、IP头的目标地址字段、可能地在IP头的其它字段中、以及在其它协 议头（例如，传输控制协议（TCP）头的源端口号字段和目标端口号字段） 中承载相同的值。网络的实例包括TCP连接的流量源（或发送方）产生的 分组序列。

许多网络部分中的分组交换机和路由器将单个队列分配给多个流，其 中的分组将通过同一输出链路进行分派。针对多个流使用单个队列的备选 方法是将不同流的分组分配给不同队列，但是对于容纳大量网络流（数百 个或更多）的链路而言，这样做不切实际。在使用单个队列容纳多个流的 分组的情况下，为队列分配的缓冲空间的大小通常根据需要而驱动，以避 免存在TCP流量时产生链路利用的损失。

TCP源的自适应行为利用TCP流量穿过的链路，该流量对于链路前 面的缓冲器在出现拥塞时所做的是否允许新的分组进入的决策策略非常敏 感。在缺乏分组丢失的情况下，TCP源一直增加它们产生的流量，从而导 致分组缓冲器进一步拥塞并且不断填充可用的缓冲器空间。相反，当分组 被丢弃时，相应的源减少其活动，这样在一段时间之后，减轻瓶颈链路前 面的拥塞。当缓冲器始终保持不空时，便可实现完全利用链路，这是识别 分组丢失的TCP源部分与被允许一直增加其流量产生率的TCP源部分之 间完美平衡的结果。

多年以来，IP网络研究和开发社区普通认为在容量为C的链路前面， 应该针对处理TCP流量的队列分配大小为的缓冲器空间，其中是针 对队列中的所有TCP流估计的平均分组往返时间（RTT）。该缓冲器分 配标准（在C.Villamizar和C.Song所著的“High-Performance TCP in  ANSNET（ANSNET中的高性能TCP，发表于ACM计算机通信评论， 24(5):45-60,1994[Villamizar,1994]）”中首次提出，一般被称为带宽时延 乘积）的目标是避免队列下溢状态，从而避免在流量拥塞时，因为队列发 生分组丢失而导致的链路利用率降低。在和C=40Gbps（它们是 2010核心网络链路的典型值）的情况下，链路前面所需的缓冲器空间为 10Gbit=1.25GB。这个相对较大的缓冲器大小基于下面的两个原因构成了网 络设备制造商和网络运营商的主要问题。第一，缓冲器大小使得无法实现 芯片上缓冲存储器，从而对系统密度、设计成本和能耗产生负面影响。第 二，根据BDP规则的缓冲器大小设置可以轻松将平均RTT添加到分组端 到端转发延迟上。这个分组可能在其网路流的数据路径上多次遇到的较大 增加延迟可能导致网络应用的最终用户感知降级。

在S.Floyd和V.Jacobson所著的“Random Early Detection Gateways  for Congestion Avoidance（避免拥塞的随机早期检测网关，发表于 IEEE/ACM Transactions on Networking，1(4):397-413，1993[Floyd, 1993]）”中，作者介绍了被称为随机早期检测（RED）的缓冲器管理机制， 其中分组可以在队列占用接近可用缓冲器空间之前的很久开始被丢弃。 RED的目标是尽可能公平地跨穿过队列的所有TCP流分散分组丢失，并 且避免全局同步状况，从而使大量TCP源在大量连续的分组丢失之后同时 停止发送分组，从而减低链路使用率。借助RED，丢弃分组的决策基于将 一小组缓冲器占用阈值（b_min和b_max）与在每次分组到达时更新的平均队列 长度（AQL）进行比较。与最大丢弃概率p_max一起，AQL当前相对于缓冲 器占用阈值的定位定义在分组到达队列时丢弃该分组的概率。虽然通常已 经确认RED的优点，但是该技术仅在实际网络设备中局部使用，因为该 机制的性能对于根据队列中的TCP流量的特征对机制参数所做的相应调 节十分敏感。

认识到RED性能对流量特征（主要通过活动TCP流以及通过按流分 布的RTT值限定）与所选的RED配置参数值（定义分组丢弃概率曲线轮 廓，以及平均权重w的参数，该平均权重近似地定义实现AQL的低通滤 波器的截止频率）之间的匹配度的敏感性之后，初始RED的两名作者在 接下来提出旨在提升算法性能的修改。

在V.Jacobson、K.Nichols和K.Poduri所著的“RED in a Different  Light（不同光线中的RED，未发表，1999， <http://www.cnaf.infn.it/～ferrari/papers/ispn/red_light_9_30.pdf> [Jacobson,1999]）”中，作者提供了实用的建议来提升RED性能并简化 其配置。这些建议包括：(a)通过以固定时间间隔收集的瞬时队列长度样 本更新AQL；(b)将定义AQL的低通滤波器的截止频率设为低得足以消 除在与RTT相同的时标上发生的所有队列长度动态量的值；以及(c)将其 中开始丢弃分组的缓冲器占用阈值设为其中如果RTT值的 实际分布未知，则尽管这些建议有助于提升RED的链路利用率， 但是它们不足以在多种流量情形下避免链路利用率损失。此外，与BDP 规则的命令相比，选择无法显著减少已分配的缓冲存储器。

在S.Floyd、R.Gummadi和S.Shenker所著的“Adaptive RED:An  Algorithm for Increasing the Robustness of RED’s Active Queue  Management（自适应RED：增加RED主动队列管理鲁棒性的算法，未 发表，2001<http://icir.org/floyd/papers/adaptiveRed.pdf>[Floyd,2001]）” 中，作者利用[Jacobson,1999]中的建议以及W.Feng、D.Kandlur、D.Saha 和K.Shin所著的“A Self-Configuring RED Gateway（自行配置RED网 关，发表于IEEE Infocom1999会议记录[Feng,1999]）”中新提出的概 念定义自适应RED（ARED）算法，其中丢弃概率函数的斜率根据AQL 的演变动态地调整，当AQL超过上限阈值b_u时，增加该斜率，当AQL低 于下限阈值b_l时，减少该斜率。与RED原始构想相比，ARED升级改善了 性能以及配置简易度，使网络管理员只能配置两个参数：预期值和所需 的平均排队延迟值d。控制分组丢弃概率斜率的算法未在[Floyd,2001]中针 对鲁棒性和收敛速度进行优化。此外，它仍依赖于AQL级别到分组丢弃 概率的映射：在稳定界限内保持分组缓冲器所需的丢弃率越高，设置该丢 弃率的AQL也越高，因此缓冲器对TCP流经历的整体RTT的影响也越 大。最后，分组丢弃概率对AQL的线性相关仍是ARED相对于RED的 原始构想而言不稳定的原因，并导致可能基本位于普通流量配置之下的链 路利用率损失。

最近，在G.Appenzeller、I.Keslassy和N.McKeown所著的“Sizing  Router Buffers（路由器缓冲器大小设置，发表于ACM SIGCOMM2004 的会议记录，波兰，OR，2004年8月[Appenzeller,2004]）”中，作者 研究了在高速网络链路之前容纳大量去同步TCP流的缓冲器的大小设置 要求，得出这样一个结论：量级大约为的缓冲器大小（其中N为 链路上去同步长期TCP流的数量）在整个时间的可控部分中，足以保持缓 冲器下溢状况发生的概率。在具有数千个去同步长期瓶颈化TCP流（当一 组TCP流中的流的传输窗口在不同时间达到其峰值时，对该组TCP流进 行去同步操作；长期TCP流是这样一种流：它的源至少一次离开慢起始状 态；瓶颈化的TCP流是这样一种流，对于该流而言，平均端到端吞吐量由 该流在所考虑的拥塞缓冲器上接收的公平分配设定）的网络链路中， [Appenzeller,2004]的作者认为它们的小缓冲器规则将减小足以使用芯片 上存储器实现的分组缓冲器的大小。但是，该缓冲器大小减小方法的鲁棒 性和范围已经在下面的许多文章中受到全面挑战，最终迫使做出提议的原 作者彻底改变了他们的结论。

需要一种缓冲器管理/分组准入机制，这种机制允许网络系统设计者减 小在网络接口前面缓冲分组所需的存储量，以便相同的存储器可以集成在 处理和转发分组的相同硬件组件中，而不需要单独的硬件组件来专门实现 此目标。

发明内容

根据本发明的原理对现有技术做出的一个发展是针对用于被称为周期 性早期丢弃（PED）的缓冲器管理机制的系统和方法提出一种新方法。本 发明建立在观察到针对TCP流量，可通过选择适当的分组丢弃频率稳定队 列长度的基础上。对于TCP连接数量和各个RTT值分布的任意组合，存 在一种防止队列上溢或下溢的理想分组丢弃频率。尽管理想的分组丢弃频 率值可随时间的推移快速变化，对于受过去的丢包影响的TCP连接序列很 敏感且多数不可以内联计算，但是可以根据某个误差幅度粗略估计该值， 这个误差幅度允许在预定的延长时段范围内保持队列占用。PED机制旨在 跟踪（未知的）理想的分组丢弃频率，根据队列占用的演变调整近似值， 其中近似的分组丢失频率的校正在可与穿过队列的一组TCP连接的总时 间常数比较的时标上发生。

在本发明的一个实施例中，提供一种在通信网络中操作分组缓冲器的 方法，其中所述分组缓冲器可通过操作接受多个分组流。所述方法包括以 下步骤：提供具有给定期间的丢弃定时器，其中所述给定期间到期触发对 所述分组缓冲器的瞬时队列长度（IQL）值和平均队列长度（AQL）值的 采样。如果所述IQL值大于所述分组缓冲器的最小队列阈值并且所述AQL 值大于所述分组缓冲器的门限队列阈值，标注下一到达所述分组缓冲器的 传入分组。如果所述IQL值小于所述分组缓冲器的所述最小队列阈值或者 所述AQL值小于所述分组缓冲器的所述门限队列阈值，不标注下一传入 分组和后续直到所述给定期间下次到期的分组。

在另一实施例中，被标注的传入分组立即被丢弃，不允许进入所述分 组缓冲器，并且未被标注的传入分组被视为有资格进入所述分组缓冲器。

在另一实施例中，被标注的传入分组在其一个或多个内部字段中进行 修改并且被视为有资格进入所述分组缓冲器。

本发明的另一实施例包括固定丢弃定时器，并且另一实施例包括按给 定校正间隔调整的可变丢弃定时器。

在另一实施例中，调整所述丢弃定时器的所述给定期间的所述给定校 正间隔具有固定时长。在本发明的一个实施例中，如果在所述给定校正间 隔之一到期时，所述AQL值介于所述最小队列阈值与最大队列阈值之间， 所述丢弃定时器的所述给定期间保持不变。如果在所述给定校正间隔之一 到期时，所述AQL值小于所述分组缓冲器的所述最小队列阈值，所述丢 弃定时器的所述给定期间增加。如果在所述给定校正间隔之一到期时，所 述AQL值大于所述分组缓冲器的所述最大队列阈值，所述丢弃定时器的 所述给定期间减小。当所述AQL值与所述分组缓冲器的所述最小队列阈 值之间的比率较小时，所述丢弃定时器的所述给定期间的所述增加较大， 以及当所述AQL值与所述最大队列阈值之间的比率较大时，所述丢弃定 时器的所述给定期间的所述减小较大。

在另一实施例中，进一步包括所述分组缓冲器的安全队列阈值，其中 当所述AQ值超过所述安全阈值时，可以在当前的一个所述给定校正间隔 到期之前，紧急校正所述丢弃定时器的所述给定期间。

在一个实施例中，所述丢弃定时器的所述给定期间的新值被计算为所 述给定期间的至少两个最新值的函数。在一个实施例中，其它做出准入决 策或标注下一传入分组的方法可以在同一时间上在所述分组缓冲器中执行 操作。

在另一实施例中，所述AQL和IQL值以子分组数据单位进行测量， 并且所述标记操作应用于可以包含在一个下一传入分组或多个下一传入分 组中的给定数量的所述子分组数据单位。在一个实施例中，所述子分组数 据单位为字节。在另一实施例中，所述子分组数据单位为存储字。

本发明还涉及一种具有存储器的通信设备，所述存储器中存储多个指 令，所述设备进一步包括分组缓冲器，所述分组缓冲器可通过操作接受多 个分组流，其中所述多个指令当被处理器执行时，使所述处理器执行上述 方法的步骤。

在本发明的另一实施例中，公开了一种在通信网络中操作数据链路前 面的分组缓冲器的方法，其中传入分组以设定频率进行标记。所述方法包 括以下步骤：将所述设定频率的值保留一段时间，该时间段基本长于在所 述数据链路上传输分组所需的时间，以及当所述分组缓冲器中的分组数量 达到预定阈值时，用新值替代所述设定频率的值。

附图说明

通过结合附图阅读下面详细的描述，可以轻松理解本发明的教导，其 中：

图1示出原始RED机制的丢弃概率；

图2示出自适应RED的可调分组丢弃概率曲线；

图3示出根据本发明的示例性丢弃周期更新的伪代码；

图4示出PED算法执行事件摘要；

图5示出示例性网络配置；

图6示出通过仿真第一示例性流量情形获取的PED缓冲器的平均和瞬 时队列长度的绘图；

图7示出通过仿真第一示例性流量情形获取的ARED缓冲器的平均和 瞬时队列长度的绘图；

图8示出带有从图7中的绘图中提取的0.5s时间间隔细节的绘图；

图9示出通过仿真第二示例性流量情形获取的PED缓冲器的平均和瞬 时队列长度的绘图；

图10a、10b和10c示出本发明的周期性早期丢弃（PED）方法的示例 性流程图；以及

图11示出实现本发明的方法的示例性通信设备的高级框图。

具体实施方式

现在参考附图描述本发明的示例性实施例，在下面的描述中，可以同 时参考这些附图中的多个。但是，在描述本发明之前，我们继续对现有技 术做出一些介绍，因为它涉及本发明的某些方面。

在发表[Appenzeller,2004](在A.Vishwanath、V.Sivaraman和M. Thottan所著的“Perspectives on router buffer sizing:Recent results and  open problems（路由器缓冲器大小设置观点：最近结果和开放问题，发表 于ACM SIGCOMM计算机通信评论，39(2):34-39，2009[Vishwanath, 2009]）”中全面总结）之后所做的大量研究工作并未产生直接的解决方案， 将[Appenzeller,2004]的结果扩展为带有更少和可能同步的长期流的更一 般设置，如在边缘和专用网络链路中那样，并且实际在Y.Ganjali和N. McKeown所著的“Update on buffer sizing in Internet routers（因特网路 由器中缓冲器大小设置更新，发表于ACM SIGCOMM计算机通信评论， 36(5):67-70，2006[Ganjali,2006]）”中导致连续修改小缓冲器规则，即使 针对核心网络链路：

依赖于拥塞早期检测以平滑地控制TCP源的活动，以避免缓冲器上溢 和缓冲器下溢事件的缓冲器管理机制承诺更有效地使链路利用率保持接近 理想的100%目标。在文献中提出的所有RED特征中，自适应RED （ARED）系列（如在[Feng,1999]和[Floyd,2001]中）将提供配置简易度 （仅配置两个参数，这两个参数之一依赖于性能目标，另一参数依赖于估 计的网络路径特征）和链路利用性能的最佳组合。一般而言，延迟性能越 严格，所需的总缓冲器空间就越小。估计网络路径特征的精确度（即，正 在发生的一组TCP连接的平均RTT）确定ARED闭环控制锁定到使缓冲 器脱离缓冲器上溢和缓冲器下溢事件所需的分组丢弃概率的最佳斜率的速 度。

尽管ARED对原始RED版本和简单尾部丢弃策略的逐步提升毋庸置 疑，但是最初定义的机制具有四个缺陷，可能在特定流量配置的情况下损 害其性能。第一，该机制不包括在未拥塞情况下避免闭环控制操作的功能。 因此，丢弃概率的斜率可能在可用范围的较低端以锁定结束，无法对快速 法阵的拥塞时间段的最终出现做出反应。第二，当分组丢弃事件的频率符 合拥塞避免状态下的TCP连接数量与其各个RTT值之间的比率所确定的 流量增长率时达到的缓冲器平衡条件与特定的AQL值关联，因此较高的 丢弃概率（在TCP连接数量较多，网络路径较短的情况下所需的丢弃概率） 伴随着较高的平均排队延迟。丢三，使用概率替代固定时间间隔来定义连 续丢弃事件之间的时间间隔增加了丢弃事件序列的不规则性，从而导致围 绕平衡点的更大范围的振荡。第四，分组丢弃决策基于对AQL的观察， 所述AQL增加对缓冲器占用增长采取正确操作（通过丢弃分组）的时间 与测量校正效果的时间（通过观察AQL）之间的距离。网络路径内在引入 了可与连接丢失分组的时间与分组丢失转换为源活动减少（可通过瞬时队 列长度（IQL）测量）的时间之间的RTT比较的延迟。使用AQL制定分 组丢弃决策引入了附加延迟，该延迟可与实现AQL计算的低通滤波器的 截止频率的倒数一样大。由于理想的情况下，滤波器的截止频率被设为 RTT值（如果不是较小）的倒数，因此使用AQL制定分组丢失决策导致 决策的时间不精确性翻倍。

尽管ARED的第一缺陷可通过简单地修改控制分组丢失概率斜率的 算法来校正，但是其它三个缺陷是RED定义的内在缺陷，因此它们的解 决方法要求一种完全不同的方法来对拥塞状况进行早期检测。

图1示出将AQL级别映射到分组丢弃概率的函数的典型曲线。对于 图1中的函数，只要AQL保持低于最小阈值b_min，RED便不丢弃任何分 组。当AQL介于最小阈值b_min与最大阈值b_max之间时，以线性依赖于两个阈 值之间的AQL的当前位置的概率（当时，概率为p_max）丢弃传入分 组。当另外当IQL超过定义总可用缓冲器空间的阈值Q_max>b_max时， RED丢弃每个传入分组。使用AQL替代IQL将分组丢弃决策与反映一般 TCP动态，而非拥塞状况开始的短期IQL波动进行了隔离，因此对分组 丢弃率没有影响。

[Floyd,2001]中指定的自适应RED（ARED）算法使p_max受一种控制算 法的支配，该控制算法在预定范围内设定其值。为了确保控制环路对流量 状况变化的缓慢反应不触发太稠密（可能导致带有灾难性链路利用率损失 的全局同步状况）的分组丢弃序列，ARED采用温和的丢弃概率曲线版本， 在曲线在(b_max,p_max)与(b_top=2b_max,1)之间线性增长，而非立即从跳到 （请参阅图2）。在保留同一p_max值至少T时间（500ms是[Floyd,2001] 中建议的值）之后，该控制算法在AQL超过阈值b_u时立即减小p_max，或者 在AQL降到阈值b_l以下时立即增加p_max，最终目标是使AQL稳定在b_d=C·d 周围，其中d是目标平均延迟（b_min<b_l<b_d<b_u<b_max）。[Floyd,2001]的作者 根据目标平均延迟d自动推导出所有缓冲器阈值，从而使用户不再对其以 下配置所有不确定：b_min=0.5b_d、b_l=0.9b_d、b_u=1.1b_d和b_max=1.5b_d。允许的p_max值的范围也是固定的：[0.01,0.5]。通过遵循所有默认值建议，为用户留下目 标平均延迟（或者缓冲器空间的所需总分配Q_max≥b_top）作为唯一的任意参数。 简单地说，ARED将原始RED与控制分组丢弃概率的两部分的斜率的机 制进行结合，该分组丢弃概率由将目标平均延迟的AQL映射到理想分组 丢弃概率p^*(t)（与理想丢弃率连续匹配）的最终目标推动。如作者指出 的那样，[Floyd,2001]中指定的控制算法不一定针对精确度和收敛速度优 化。

如上所述，尽管某些ARED缺陷可以通过简单地修改控制分组丢弃概 率斜率的算法来校正，但是其它缺陷是RED定义的内在缺陷，因此它们 的解决方法要求一种完全不同的方法来对拥塞状况进行早期检测。因此， 现在将描述本发明的某些方面。

周期性早期丢弃

本发明定义被称为周期性早期丢弃（PED）的缓冲器管理机制。与现 有技术的缓冲器管理技术相比，PED机制明显提升了诸如链路利用率（吞 吐量）和平均排队延迟之类的关键性能度量，而且还最大程度上减小了配 置复杂度（一旦可用存储大小由系统设计定义，所有参数便都有固定值， 或者可以根据特定性能目标定制）。

本发明提供了一种明显减少在网络元件中实现分组缓冲器所需的存储 量的方法，使得此类芯片上缓冲器的实现与当前的芯片外实现相反。该体 系结构演进的优点相对于能耗和系统可扩展性和集成尤其突出，因为现在 有更多分组处理组件可以装入更小的空间。芯片外存储器的消除简化了网 络系统设计，从而允许较高的集成并提高能效。较小的存储器还在不降低 网络链路利用率和不增加穿过缓冲器的TCP流的完成时间（TCP流的完 成时间是指将整个数据对象从TCP发送方发送到TCP接收方所需的时间） 的情况下，减小了网络缓冲器对网络应用分组经历的端到端延迟的影响。

本发明的基本理念基于观察到针对TCP流量，可通过选择适当的分组 丢弃频率稳定队列长度。对于TCP连接数量和各个RTT值分布的任意组 合，存在一种防止队列上溢或下溢的理想虚幻分组丢弃频率尽管理 想丢弃频率值可随时间的推移快速变化，对于受过去的丢包影响的TCP 连接序列很敏感且多数不可以内联计算，但是可以构想根据某个误差幅度 粗略估计该值，这个误差幅度允许在预定的延长时段范围内保持队列占用。 PED机制旨在跟踪（未知的）理想分组丢弃频率，根据队列占用的演变调 整近似值，其中丢失频率校正在可与穿过队列的一组TCP连接的总时间常 数比较的时标上发生。

PED建立在实验证据上，该证据证明稳定的RED实例是将固定分组 丢失概率与扩展的AQL值范围进行关联，以便AQL的一般增加（当它接 近IQL）不会转换为更高的分组丢失率和全局同步的实例。为了一致地执 行所需的分组丢弃率，我们还用执行间隔相等的分组丢弃事件的分组丢弃 周期替代分组丢弃概率概念（产生可变的丢弃间隔），同时激励本发明的 名称。

在其一般构想中，PED组合两个在不同的时标上执行操作的组件。在 较短（分组）时标上，当拥塞信号很明显时，PED以固定时间间隔丢弃分 组。在较长（RTT）的时标上，控制算法根据AQL的演变调整分组丢弃 周期。

应该指出本发明PED方法的以下特性，并且本领域的技术人员理解这 些特性的各方面：

1.更简单的PED实现可能不包括用于动态调整分组丢弃周期的控制 算法。这些实现通过恒定的分组丢弃周期执行操作，其值可由网络运营商 根据网络内的分组缓冲器位置设定。

2.PED可用于结合其它缓冲器管理机制或以隔离的方式控制是否准 许分组进入缓冲器。在其中使用PED的所有情况下，当缓冲器没有足够的 空间容纳新传入的分组时，丢弃一个或多个分组。

3.尽管本发明重点使用PED作为决定是否允许新分组进入缓冲器的 方法，但是本发明的方法本身不限制更一般的分组标注应用，其中分组头 中的字段通过修改通知下游缓冲器它们可以考虑丢弃概率高于其它分组的 分组，或者仅通知分组的最终接收方关联的流正在沿其数据路径经历网络 拥塞并且应该减少各个源的流量产生活动。

4.虽然在本发明中，PED执行结果适用于整个分组，但是可以等同地 实现应用于子分组数据单位（例如，字节和存储字）的PED版本。

PED使用可控时长的周期为τ_D的丢弃定时器触发对IQL q和AQL的 采样，并将它们与各个阈值和进行比较，本文将更详 细地进行介绍。如果在丢弃定时器到期时，并且则PED丢 弃（或标注）下一传入分组；否则，它将接受下一分组和直到下一丢弃周 期到期的所有分组进入队列。

PED根据AQL演变控制丢弃定时器的周期τ_D。当时间间隔优选地短 语时间常数T（大小足以包括多数TCP连接的RTT值，例如T=500ms） 时，PED将与最小PED阈值和最大PED阈值进行比较。如果 PED增加τ_D，如果PED减小τ_D。在这两种情况下，校正 事件m上的丢弃周期τ_D[m]的新值通过当前值τ_D[m-1]（在校正事件上m-1设 定）和上一值τ_D[m-2]（在校正事件上m-2设定）推导出。周期校正大小通 过AQL与相关阈值（适用于周期增加的和适用于周期减小的) 之间的比率调制。每当发现AQL位于两个阈值之间时，丢弃定时器的周 期保持不变。

现在参考图3，其中示出丢弃周期更新的示例性实现的伪代码。该代 码概述自最后一个丢弃周期更新以来，经过至少时间T之后的分组丢弃周 期更新。在图3的方程中，α是AQL与最小PED阈值（适用于周期增加） 之间的比率，或最大PED阈值与AQL（适用于周期减小）之间的比率，K 是周期校正的最大大小（当α=0时，校正最大）。

PED使用同步的时间推动后台过程更新AQL。设定平均周期τ_q的标 准类似于RED同步版本的标准：周期应该大于具有队列输出容量典型大 小的分组的inter-departure time（间出发时间）（例如， τ_q≥1500B/40Gbps=0.3μs），但是不大于目标平均延迟的一小部分（例如， 5%）（例如，τ_q≤0.05·1ms=50μs）。如同往常那样，PED将AQL计算 为指数加权移动平均数（EWMA）：EWMA权 值w通过平均周期与通过EWMA实例化的低通滤波器的时间常数之间的 比率定义w=τ_q/T。

为了阻止一般TCP动态量将丢弃周期的控制从其匹配理想丢弃率的 目标转移，PED还包括提供：(a)在非最新分组丢弃事件结果的低负载状 况下，暂停校正丢弃周期τ_D；(b)将丢弃周期重置为当缓冲器占用在某一 时间（可与时间常数T比较的时间）内从空增长为满之后可用的最小值（例 如，某个事件指示当前分组丢弃周期太长，无法正确地处理当前流量结构）； 以及(c)允许在AQL超过安全阈值之后立即紧急校正丢弃周期， 即使时间常数T尚未到期。

PED在许多方面与RED不同。如上所述，PED使分组丢弃率在最少 时间T内保持固定，而不是连续随着AQL更改它。它通过用固定分组丢弃 周期替代分组丢弃概率，最大程度上减小了inter-drop time（间丢弃时间） 的变化。

PED的另一重要新颖元素是仔细考虑了数据路径和滤波延迟对缓冲 器管理机制与TCP源动态量之间交互的影响。它利用可与源的RTT比较 的时间来识别分组丢失，并且针对该识别产生对瓶颈队列的IQL的可见影 响。由于EWMA的时间常数为因此它采用了类似的附加时间以使 AQL更上IQL的变化。跟踪理想丢弃率的控制机制的准确度紧紧依赖于 TCP源的活动调整与推动这些调整的队列长度校正操作之间的时间距离。 尽管无法避免RTT引起的延迟，但是PED通过使IQL在定义分组丢弃 决策时发挥主要作用，排除了对EWMA的额外延迟影响。PED还检查 AQL以确认存在拥塞的早期信号，但是用于此目的的阈值的大小仅是 主阈值的一半，从而使EWMA延迟实际上对决策无任何影响。类似地， 在设定校正时间m上的分组丢弃周期时，我们让τ_D[m-2]额外影响τ_D[m]（除 了τ_D[m-1]中已经包括的之外），因为在事件m上观察到的队列状态（q(t_m), )可能对τ_D[m-2]的依赖远大于对τ_D[m-1]的依赖。实际上，在设定时间 τ_D[m]之前，受丢弃周期τ_D[m-1]触发的分组丢失影响的源甚至不可能开始对 这些丢失做出反应。

PED配置

如果新的算法也不容易配置，则卓越性能和低实现复杂度无法迫使在 网络设备中普遍部署该算法。在这部分中，我们列出推动PED操作的示例 性配置参数集。由于我们针对相关参数的值提供示例性建议，因此PED 配置很直接，并且一旦链路速率和可变存储量已知，则可以完全自动地执 行。可以理解，示例性配置参数只示出一个用于实现本发明的实施例并且 其它参数可以根据特定网络目标进行选择。

参数Q_max是总可用缓冲器空间；它的值通过硬件设计约束设定，例如 可用缓冲存储器大小（例如，Q_max=32MB用于我们的示例性流量情形中的 芯片上缓冲存储器实现，对于这些情形，仿真结果在图6、7、8和9中示 出）。

参数是最小PED阈值；它应该被设为总可用缓冲器空间（在我们 的实例中为)的固定部分（例如，20%）。

参数是最大PED阈值；它应该是最小PED阈值的两倍（但是不 禁止其它高于的值）：（例如，在我们的实例中，）。

参数是安全PED阈值；它应该是最小PED阈值的三倍（但是不 禁止其它高于最大PED阈值的值）：（例如，）。

参数是门限PED阈值；只要AQL低于该阈值，就不会丢弃任何 分组；它的大小应该是的一半（例如，)。

参数τ_q是AQL的更新周期；它的大小应该足以避免在相同的分组在 队列之外传输时多次更新（例如，τ_q=10μs）。

参数T是由瓶颈链路和一组其分组穿过该链路的TCP发送方和接收方 构成的控制系统的时间常数；它也是实现计算的低通滤波器的截止频率 的倒数；为了确保包括多数TCP连接的RTT值，尤其是当它们的实际分 布未知时，T的值应该被设为500ms；当已知RTT分布集中于明显较小的 值时，不禁止较低的值。

参数w是用于将AQL计算为EWMA的权值；其值直接通过针对平均 周期τ_q和针对时间常数T选择的值直接推导出：w=τ_q/T（例如，w=0.00002）。

参数是在PED丢弃周期τ_D中允许的最小值；它应该至少像平均周 期τ_q一样大（例如，)。

参数是在PED丢弃周期τ_D中允许的最大值；它应该大于估计的值，但不大于T（例如，)。

参数K是用于更新分组丢弃周期τ_D的固定校正因子（例如K=2；较大 的值使得控制环路更快，但是稳定性较差）。

如上所述，示例性配置参数反映了本发明的一个示例性实施例。本领 域的技术人员将理解可以选择其它参数和参数值。

PED操作

以下变量包含在PED操作中。

变量q是IQL；它可以以分组或子分组数据单位（例如，字节或存储 字）进行测量。

变量是时间nτ_q与(n+1)τ_q之间的AQL，其中n是整数；它的测量单 位与变量q的测量单位相同。

变量τ_D是PED丢弃周期，其时长由的演变控制。

运行示例性算法实施例的辅助变量包括PED丢弃周期的最新更新的 时间t_U、当队列最后变空的时间t_Z、PED最后做出丢弃分组的时间t_D，以 及指示是否应该丢弃下一传入分组的丢弃标志f_D。

图4总结了在PED机制中使用阈值。在图中的每个部分，队列长度线 的实部指示其中应用所列操作的参考度量（IQL或AQL）的值范围。由针 对每个部分列出的事件触发所述测量与各个阈值的比较。如针对分组到达 事件10所示，当IQL q超过阈值Q_max时，采取两个操作。这些操作丢弃传 入分组并将PED周期重置为其最小值。下一操作是PED丢弃定时器20 到期。当IQL达到最小PED阈值并且AQL达到PED门限阈值时，设定丢弃标志。在下一事件（PED丢弃定时器和时间常数30到期） 上，如果尚未达到最小PED阈值PED周期增加。对于同一事件（PED 丢弃定时器和40中所示的时间常数到期），如果针对AQL达到最大PED 阈值则PED周期减小。如50中所示，在时间常数到期时，如果AQL 超过PED安全阈值则设定PED丢弃标志并且PED周期减小。

现在参考图10a，其中示出根据本发明实现整个PED方法的流程图 100。该流程从点A102开始。接下来，在第一步骤104，到达决策框并判 定AQL定时器是否到期。如果未到期，则流程继续到转换点B106。如果 AQL已到期，则流程继续到步骤107，其中更新AQL值。在步骤108， 重置AQL定时器，然后流程继续到决策框110，其中判定AQL定时器是 否大于安全阈值。如果是，则流程继续到另一决策框112，其中判定时间 常数是否到期。如果是，则流程继续到步骤114，其中设定丢弃标志。如 果决策框110或112到达“否”决策，则流程继续到转换步骤B106。在 步骤114设定丢弃标志之后，流程继续到步骤116，其中更新丢弃周期。 丢弃定时器接下来在步骤118重置，然后算法继续到转换步骤B106。

现在参考图10b，本发明方法的流程继续。在转换步骤B106之后， 到达决策框120，其中判定丢弃周期是否到期。如果未到期，则流程继续 到转换步骤C122。如果丢弃周期已到期，则在决策框124执行检查以判 定AQL是否大于门限阈值如果到达“是”据侧，则流程继续到下一 决策框126，其中判定IQL值是否大于最小阈值。如果IQL值是否大于最 小阈值，则在步骤128设定丢弃标志。如果决策框124或126到达“否” 决策，则流程直接继续到步骤130，其中重置丢弃定时器。

在步骤128设定丢弃标志之后，到达下一决策框132，其中判定时间 常数是否到期。如果时间常数到期，则继续到下一决策框134，其中判定 IQL在等于时间常数的上一时间间隔内是否已变为无效。如果IQL在等于 时间常数的上一时间间隔内已变为无效，则在步骤136更新丢弃周期。如 果决策框132到达“NO”决策或者决策框134到达“是”决策，则流程直 接继续到步骤130，其中重置丢弃定时器。在丢弃定时器重置之后，算法 流程继续到转换步骤C122。

在转换点C之后，我们到达决策框138，其中判定新的分组是否到达， 如果未到达，则流程再次继续到起始点A112。如果新的分组已到达，则 判定是否在决策框140设定丢弃标志。如果已设定丢弃标志，则在步骤142 标记分组，并且在步骤144重置丢弃标志。然后流程继续到起始点A122。 如果在决策框140到达“否”决策，并且未设定丢弃标志，则继续到决策 框146，其中判定缓冲器是否已满。如果缓冲器已满，则在决策框148执 行检查以查看AQL是否大于门限阈值。如果AQL大于门限阈值，则在步 骤150将丢弃周期设为最小值。接下来，在步骤152重置丢弃定时器，并 且流程继续到起始点A112。如果决策框146或148到达“否”决策，则 流程直接继续到起始点A112。

PED性能

现在参考图5，其中示出示例性网络拓扑200，该拓扑包括源汇聚节点 （SAN）202、瓶颈节点（BNN）204和汇分布节点（SDN）206。使用网 络仿真器平台研究本发明的周期性早期丢弃方法的链路利用率性能。通过 各个1Gbps链路210将N个TCP Reno源208连接到SAN。这些链路中每个 链路的传播延迟设定各个TCP流的RTT。所有其它链路的传播延迟可以 忽略。TCP汇211也通过1Gbps链路212连接到SDN。网络节点之间的所 有链路具有40Gbps的容量，但是从BNN到SDN的瓶颈链路214除外，它 的容量低于40Gbps（我们在不同的实验中设定不同的瓶颈速率值）。瓶颈 队列上的总可用缓冲器空间为32MB，恰好位于芯片上缓冲器实现的范围 内。我们通过前面给出的示例值配置PED参数：τ_q=10μs、T=500ms、 $b_{\mathrm{gate}}^{\mathrm{PED}}=3.2\mathrm{MB},b_{\min }^{\mathrm{PED}}=6.4\mathrm{MB},b_{\max }^{\mathrm{PED}}=12.8\mathrm{MB},b_{\mathrm{safe}}^{\mathrm{PED}}=19.2\mathrm{MB},$Q_max=32MB、${\tau }_D^{\left(l\right)}=100\mathrm{\mu s}$和${\tau }_D^{\left(u\right)}=T=500\mathrm{ms}.$

我们通过仿真图5的网络配置研究PED性能，其中情形1和2的流量 设置在下面进行描述。我们所给出的结果从非常大的集合中选出，在该集 合中，找不到我们将要展示的关键成果的例外。情形1具有N=1000个TCP 流，所有流都是流的数量和RTT值（均很大）挑战早期丢弃算 法适当分布分组丢失的能力。由于RTT对于所有流而言均相同，因此我 们有可能观察到一般TCP动态量导致的严重队列长度振荡。如果分组的丢 弃太稀疏，则队列很容易上溢。如果分组丢弃过于频繁，则会发生全局同 步。在情形2中，我们将TCP流数量缩小为N=100，以便增加早期丢弃机 制估计理想丢弃率（单个分组丢弃事件对整个流量负载的影响可变）的精 确度的压力，并且在10ms与290ms之间均匀分布RTT值，以 便根据给TCP流的次最优分组丢失分配测试机制的鲁棒性。

我们使用情形1执行第一示例性仿真实验。在图6中，我们绘制当瓶 颈速率为32Gbps时，30s内AQL和IQL的演变图形。测量的链路利用率 为100%。该图清晰地突显了稳定的分组丢弃周期（我们观察到它在20ms 周围的狭窄范围内波动）在保持队列长期稳定性时的重要作用，不考虑IQL 和AQL的自然振荡。

为了与图6比较，我们使用[Floyd,2001]中建议的配置参数，在图7 中绘制当ARED机制在瓶颈队列中使用时，AQL和IQL的演变。在绘图 所涵盖的100s周期内，我们测量链路利用率为79.6%。最大丢弃概率p_max在整个间隔期间不会从最小允许值（0.01）移动。图7借助全局同步状况 的周期性开始介绍了链路利用率损失。我们发现分组丢失始终是ARED决 策的结果，从来不是由缓冲器上溢造成（IQL始终远低于Q_max=32MB）。 我们现在参考图8中更精细的时间粒度以查找这样一个明显的证据：即， 正是ARED（更一般地为RED）的分组丢弃概率函数的单调特性导致全局 同步，从而导致早期检测算法不稳定。在图8中，IQL围绕时间t_p=848.77s 达到峰值。到该时间为止，全局同步事件的状况已通过过度的分组丢失设 定。我们知道过度的丢失在t_p之前发生，因为IQL在t_p之后迅速降为0。 这意味着当分组丢弃概率与可以稳定队列长度的理想丢弃速率值匹配（如 果持续一段延长的时间）时，存在平衡时间t_e<t_p。t_e的实际位置与我们的 论据无关：最重要是说明在IQL开始下降之前，一定满足均衡丢弃概率。 ARED用于推动分组丢弃决策的AQL在IQL增加时，系统地落后于IQL 一定的延迟，所述延迟取决于计算AQL（在图中，AQL落后IQL的时间 小于500ms）的低通滤波器的截止频率。AQL只要小于IQL，便一直增 加，因此也在均衡时间t_e之后（甚至在t_p之后）。只要AQL继续增加，受 丢弃概率函数单增曲线的影响，分组丢弃概率也会增加。通过这种方式， 分组丢弃概率保持高于超过t_p的时间的平衡值。在t_e与t_p之间发生的分组丢 失（超出理想丢弃率平衡所需的丢失量）导致开始全局同步事件。图7和 8所示的行为由任何RED实施例无法在达到平衡条件之后锁定在该条件上 导致，该条件最终通过丢弃概率函数的严格递增性质推导出。相反，本发 明的PED机制坚持近似地估计理想丢弃率，只要该估计证明能够使AQL 保持在两个阈值和限定的范围内。

我们使用情形2执行第二示例性实验。在图9中，我们绘制当瓶颈速 率为36Gbps时，10s内AQL和IQL的演变图形。测量的链路利用率为 99.947%。与情形1（图6）相比，IOL振荡宽度增加，但是PED仍设法 使链路利用率接近100%。假设PED丢弃周期的稳定状态永久地停留在最 大允许值500ms上很重要，该值指示如果较宽的范围可用，则PED控制环 路可能使值变大。但是，最大PED丢弃周期的值限制不影响吞吐量性能， 因为后续分组丢弃事件之间的正确时间分隔仍通过控制分组丢弃决策（通 过比较AQL与门限阈值）执行。

现在我们将介绍本发明的PED方法与其它现有技术方法之间的某些 差别，以及这些差别中部分差别的动机：

1.与原始RED和ARED相反，PED中的AQL维护是时间驱动过程， 而非事件驱动过程。AQL按照固定时间而非分组到达时间更新。通过这种 方式，可以建立定义AQL值的EWMA与EWMA实例化的低通滤波器的 截止频率之间的确定关系。这样防止被限定在RTT时标内的TCP动态量 不正确地影响丢弃周期τ_PED的控制。它还使得EWMA权值w的配置变得直 接（如果RTT分布未知，则该值可以固定，或者在可以合理地估计RTT 分布时，该值满足RTT分布）。

2.在具有长期瓶颈化TCP连接的队列中，当分组丢弃频率使处于拥 塞状态的源的流量产生率增长平衡时，实现稳定性。对于每N个长期连接 以及对于它们的RTT值的每个分布，存在理想的分组丢弃频率以便 源活动的最终减少完全匹配不受分组丢失影响的源的源活动增加。频率的 确切值很难通过分析在实际系统中获取，因为具有多个硬性量化因素影响 其判定（例如，受后续分组丢弃影响的连接始终不同，还是每个连接的多 个丢弃在短时间内发生）。但是，我们仍然认为此类值在任意时刻针对系 统的任何可能的状态存在。如果当该值的估计错误位于合理的误差范围内 时，队列的稳定性在特定时间内得到保证，则可以在其多数拥塞时间内保 持不完全平衡，只要分组丢弃频率在有界限的误差范围内一直跟踪理想的 参考值。使用PED，一旦确定近似的频率值，便可在丢弃定时器到期之前 确定的执行该值。相反，使用RED和ARED，仍然可以观察到围绕通过 目标丢弃概率设定的平均频率值存在大范围的波动。另外，每个传入分组 可以找到不同的AQL，从而找到不同的丢弃概率，进一步增加控制的不准 确性。

3.在控制理论方面，RED和ARED使用AQL控制丢弃概率，以便 平衡队列所需的丢弃频率的每个值首先转换为丢弃概率值，然后转换为特 定的AQL值。所需的丢弃频率越高，建立平衡的AQL就越高（ARED通 过根据当前流量状况调整丢弃概率值的范围，至少在名义上优于RED）。 相反，PED机制单独控制丢弃频率和AQL，以便不同的丢弃频率可以通 过相同的AQL（以及对应的平均排队延迟）执行。

4.RED和ARED在比较AQL与缓冲器占用阈值之后丢弃分组。PED 相反地比较IQL。不使用AQL（在PED，它仍可用于控制丢弃周期τ_PED） 的原因是AQL增加了可与控制TCP源活动的T（以及）比较的延迟成 分。可与比较的延迟已经存在，因为TCP源使用超时检测分组丢失事件。 因此，任何分组丢弃决策的制定都不考虑某些TCP源可能正在对上一分组 丢失做出反应（这是导致分组丢弃决策不准确的一个原因）。将分组丢弃 决策基于AQL（它比IQL演变落后延迟T）使得使用瓶颈队列上的分组丢 失调节TCP源活动控制环路的总延迟又增加了时间T。因此，在RED和 ARED中，分组丢弃决策的不准确性进一步增加。

5.当队列变空并且因为此空置状态导致PED机制取消时，PED机制 暂停控制丢弃周期τ_PED的算法。根据系统参数（长期TCP连接的数量N和 各个RTT值的分布），在源活动暂停之后，可能需要很长一段时间队列 才会再次发生拥塞。由于PED机制不会定义该低负载时间段的时长，因此 在该时间内，不应修改丢弃周期τ_PED。

6.当在AQL甚至可以超过门限阈值之前队列发生上溢时，PED机制 将丢弃周期τ_PED重置为最小允许值此类上溢事件指示PED机制无法 消除队列占用中的快速振荡，最有可能是因为丢弃周期τ_PED太高，AQL仍 处于低位。低负载的长周期与短期上溢事件之间的振荡不支持退出此状态。 因此，为了创建新的机会使算法再次锁定在理想分组丢弃频率周围的近距 离内，PED机制强制返回到可能的最高丢弃频率状态，该状态最可能避免 下一上溢事件。

7.PED机制还允许在AQL超过安全阈值时早期中断丢弃间 隔，并且向下校正丢弃周期τ_PED。这样有助于在AQL处于高位，但是丢弃 周期τ_PED仍然也很高时避免缓冲器上溢事件，从而允许正确地牵制IQL增 长。

现在参考图11，其中示出能够实现本发明的方法的通信节点300的一 个示例性实施例。可以看出，节点300包括至少一个处理器302，该处理 器与系统存储器304（例如，任何形式的随机存取存储器（RAM）和只读 存储器（ROM））相连。该通信节点还包括多个输入和输出端口305、306。 使用一个或多个存储缓冲器308缓冲在通信节点300上接收的通信流量以 及从通信节点300发送的通信流量。将理解，所述处理器执行存储在存储 器中的程序代码，以便执行该通信节点的规定功能。用于执行所述的本发 明方法的程序代码可以存储在系统存储器304中并由处理器302执行。

总结

随着网络链路的传输速率不断增长，分组缓冲存储器的芯片上实现是 下一代路由器和交换机的可扩展性与能效的主要必备条件。诸如Tail Drop 和RED之类的现有缓冲器管理方法不能必要地减少缓冲器空间，因为它 们在常见流量情形中无法避免TCP源的全局同步。RED受制于缺乏在不 考虑流量结构的情况下保证高端性能的配置策略。

我们已经提供了强有力的证明来证实RED缺点的主要原因是通过队 列长度推导分组丢弃事件频率的控制法则具有单一的非递减曲线。因此， 我们定义了新的周期性早期丢弃（PED）机制，其中控制法则为平形，处 于可在RTT时标上调整的水平上。我们还收集了坚持PED一致地执行 100%链路利用率（其中在当前设计中，长期TCP流处于稳定状态下，使 用小于3%的存储空间）的仿真结果。

上面的描述仅示出本发明的原理。因此将理解，本领域的技术人员能 够构想各种配置，这些配置尽管在此未明确描述或示出，但是采用了本发 明的原理，并且包括在本发明的精神和范围内。此外，所引用的所有实例 和条件语言主要明确地旨在仅作为教导性说明，从而帮助读者理解本发明 的原理以及发明者提供的促进本技术领域的概念，并且不受限制地被视为 这些专门介绍的实例和条件。而且，在此引用本发明的原理、各方面和实 施例以及本发明的特定实例的所有声明旨在包含本发明的结构上以及功能 上的等价物。此外，此类等价物旨在包括当前公知的等价物以及未来开发 的等价物，即，所开发的执行相同功能的任何元件，不考虑结构。本发明 原理的许多其它修改和应用对于本领域的技术人员而言是显而易见的并且 通过此处的教导构想。因此，本发明的范围仅通过权利要求限定。