用于在分组交换网络中提供随机早期检测的装置和方法

摘要

一种用于在分组交换网络中提供随机早期检测RED的装置(1)和方法，所述装置(1)包括：出队计数器(2)，每次数据包从队列Q出队时，其递增；每次数据包入队到所述队列Q时，其重置；系数存储表CMT，其存储了预定数目M个衰减系数C；以及计算单元(4)，用于每次数据包入队到所述队列Q时，根据衰减系数C计算所述队列Q的平均队列长度AQS，其中所述衰减系数从所述出队计数器(2)重置之前其指向的所述系数存储表CMT的存储地址中读取。

说明书

背景技术

随机早期检测RED是一种在分组交换网络中避免流量拥塞的机制。 传统随机早期检测机制，也称为随机早期丢弃(random early discard/ random early drop)机制，是一种主动队列管理算法。使用随机早期检测 机制，可以在拥塞发生之前随机丢弃数据。随着数据拥塞变高，数据包丢 弃的概率增加。随机早期检测机制可以监控平均队列长度AQS并基于统 计概率法丢弃数据包。例如，如果缓冲几乎为空，接受所有传入数据包。 当缓冲中的数据包的队列Q增长时，丢弃传入数据包的概率也增加。如果 缓冲已满，那么概率变为100％并且丢弃所有传入数据包。为每个接收的 数据包重新计算平均队列长度AQS。然而，在分组交换网络的传统随机早 期检测机制中，平均队列长度AQS的计算仅考虑接收到的数据的输入函 数，而没有考虑输出函数，即，传统随机早期检测机制仅考虑传入数据包 的入队到队列Q，而没有考虑数据包从各个队列出队。因此，在分组交换 网络中使用的传统随机早期检测方法确实只显示了预测数据拥塞和避免 网络中的这种数据拥塞的有限能力。

相应地，需要提供一种能够在分组交换网络中准确地预测数据拥塞并 提供更好地避免数据拥塞的装置和方法。

发明内容

本发明提供了一种用于在分组交换网络中提供随机早期检测的装置 作为第一方面，所述装置包括：

出队计数器，每次数据包从队列Q出队时，出队计数器递增；每次数 据包入队到所述队列Q时，出队计数器重置；

系数存储表CMT，存储了多个衰减系数C；以及

计算单元，用于每次数据包入队到所述队列Q时，根据衰减系数C 计算所述队列Q的平均队列长度AQS，其中所述衰减系数从所述出队计 数器重置之前所述出队计数器指向的所述系数存储表CMT的存储地址中 读取。

在根据本发明的第一方面的装置的第一可能实施方式中，所述计算单 元用于将计算得到的所述队列Q的平均队列长度AQS与最大阈值和最小 阈值比较。

在根据本发明的第一方面的装置的第一实施方式的第二实施方式中， 所述计算单元用于如果所述平均队列长度AQS超过所述最大阈值，丢弃 接收的数据包。

在根据本发明的第一方面的用于在分组交换网络中提供随机早期检 测的装置的第一或第二实施方式的第三实施方式中，所述计算单元用于如 果所述平均队列长度AQS小于所述最小阈值，将所述接收的数据包入队。

在根据本发明的第一方面的用于在分组交换网络中提供随机早期检 测的装置的第一至第三实施方式中任一者的第四实施方式中，所述计算单 元用于如果所述计算得到的平均队列长度AQS介于所述最小阈值和所述 最大阈值之间，随机丢弃所述接收的数据包。

在根据本发明的第一方面的用于在分组交换网络中提供随机早期检 测的装置的第四实施方式的第五实施方式中，如果所述计算得到的平均队 列长度AQS介于所述最小阈值和所述最大阈值之间，随机丢弃接收的数 据包，其中每个流量优先级的丢弃概率不同。

在根据本发明的第一方面的用于在分组交换网络中提供随机早期检 测的装置的第一至第五实施方式的第六实施方式中，所述计算单元用于如 下计算所述平均队列长度AQS：

[Curr AQS–Queue Size Diff]x C+Queue Size Diff,

其中Curr AQS是当前平均队列长度AQS，

Queue Size Diff是队列长度差，

Queue Size Diff＝(Prev Queue Size–Curr Queue Size)/2，

其中Prev Queue Size是先前计算得到的所述队列Q的队列长度，

Curr Queue Size是当前计算得到的所述队列Q的队列长度，

C是根据所述队列Q的所述出队计数器的所述指针值从所述系数存储 表CMT中读取的所述衰减系数。

在根据本发明的第一方面的用于在分组交换网络中提供随机早期检 测的装置的第六实施方式的第七实施方式中，所述衰减系数C是衰减系 数。

在根据本发明的第一方面的用于在分组交换网络中提供随机早期检 测的装置的第七实施方式的第八实施方式中，所述预先计算的衰减系数是 所述系数存储表CMT中存储的指数衰减函数的系数。

在根据本发明的第一方面的用于在分组交换网络中提供随机早期检 测的装置的第七或第八实施方式中任一者的第九可能实施方式中，所述计 算单元用于如下提前计算所述指数衰减函数的所述衰减函数C：

x[i+1]＝x[i]x(N–W)/N

C[i+1]＝(x[i+1]–x[0])/x[0]

其中x[0]是任意数，N和W是任意数(W<N)，i是变量。

在根据本发明的第一方面的用于在分组交换网络中提供随机早期检 测的装置的第九实施方式的第十可能实施方式中，

x[0]设置为100，

W设置为1，

N设置为256。

本发明进一步提供了一种用于在分组交换网络中提供随机早期检测 的方法作为第二方面，所述方法包括以下步骤：

每次数据包从队列Q出队时，递增出队计数器；每次数据包入队到所 述队列Q时，重置出队计数器；以及

每次数据包入队到所述队列Q时，根据衰减系数C计算所述队列Q 的平均队列长度AQS，所述衰减系数从所述出队计数器重置之前所述出队 计数器指向的系数存储表CMT的存储地址中读取。

在根据本发明的第二方面的用于在分组交换网络中提供随机早期检 测的方法的第一可能实施方式中，所述方法进一步包括将所述计算得到的 所述队列Q的平均队列长度AQS与最大阈值和最小阈值比较。

在根据本发明的第二方面的用于在分组交换网络中提供随机早期检 测的方法的第一实施方式的第二可能实施方式中，所述方法进一步包括如 果所述计算得到的平均队列长度AQS超过所述最大阈值，丢弃接收的数 据包。

在根据本发明的第二方面的用于在分组交换网络中提供随机早期检 测的方法的第一或第二实施方式的第三可能实施方式中，所述方法进一步 包括如果所述计算得到的平均队列长度AQS小于所述最小阈值，将所述 接收的数据包入队。

在根据本发明的第二方面的用于在分组交换网络中提供随机早期检 测的方法的第一至第三实施方式中任一者的第四可能实施方式中，所述方 法进一步包括如果所述计算得到的平均队列长度AQS介于所述最小阈值 和所述最大阈值之间，随机丢弃所述接收的数据包。

在根据本发明的第二方面的用于在分组交换网络中提供随机早期检 测的方法的第五可能实施方式中，随机丢弃(S10)所述接收的数据包包 括随机丢弃所述接收的数据包(S10)，其中每个流量优先级的丢弃概率 不同。

在根据本发明的第二方面的用于在分组交换网络中提供随机早期检 测的方法的第六可能实施方式中，所述方法进一步包括根据衰减系数C如 下计算所述队列Q的所述平均队列长度AQS：

[Curr AQS–Queue Size Diff]x C+Queue Size Diff,

其中Curr AQS是当前平均队列长度AQS，

Queue Size Diff是所述队列长度差，

Queue Size Diff＝(Prev Queue Size–Curr Queue Size)/2，

其中Prev Queue Size是先前计算得到的所述队列Q的队列长度，

Curr Queue Size是当前计算得到的队列长度，以及

C是根据所述队列Q的所述出队计数器的所述指针值从所述系数存储 表CMT中读取的衰减系数。

在根据本发明的第二方面的用于在分组交换网络中提供随机早期检 测的方法的第一至第六实施方式中任一者的第七可能实施方式中，所述衰 减系数C是预先计算的衰减系数。

在根据本发明的第二方面的用于在分组交换网络中提供随机早期检 测的方法的第七实施方式的第八可能实施方式中，所述预先计算的衰减系 数是所述系数存储表CMT中存储的指数衰减函数的系数。

在根据本发明的第二方面的用于在分组交换网络中提供随机早期检 测的方法的第九可能实施方式中，所述方法进一步包括如下提前计算所述 指数衰减函数的所述衰减系数C：

x[i+1]＝x[i]x(N–W)/N

C[i+1]＝(x[i+1]–x[0])/x[0]

其中x[0]是任意数，

N和W是任意数(W<N)，i是变量。

根据本发明的第三方面，提供了一种用于在分组交换网络中提供随机 早期检测的替代装置。所述装置包括用于执行根据第二方面或第二方面的 前述第一至第九实施形式中任一者的方法的处理器。

本发明进一步提供了包括根据本发明的第一方面、根据第一方面的前 述第一至第十实施形式中任一者、或根据本发明的第三方面的装置的分组 交换网络作为第四方面。

在根据本发明的第四方面的分组交换网络的可能实施方式中，所述网 络包括互联网。

根据第五方面，本发明可以在数字电子电路中或在计算机硬件、固件、 计算机软件中或在其组合中实施。所述计算机软件包括用于执行根据第二 方面或根据第二方面的前述第一至第九实施形式中任一者的方法的程序 代码。

本发明的这些和其他方面从以下所述的实施例中显而易见。

附图说明

以下将参考附图描述根据本发明的第一、第二、第三和第四方面的用 于在分组交换网络中提供随机早期检测的装置和方法的可能实施例。

图1所示为根据本发明的第一方面的随机早期检测装置的可能实施方 式的方框图；

图2所示为根据本发明的第二方面的用于在分组交换网络中提供随机 早期检测的方法的可能实施方式的流程图；

图3所示为示出了由传统随机早期检测机制对比根据本发明的装置和 方法提供的随机早期检测机制提供的在随机的数据流量下的队列的平均 队列长度AQS的图。

具体实施方式

图1所示为用于在分组交换网络中提供随机早期检测RED的装置1 的可能实施方式。在所示的实施方式中，装置1包括队列Q，数据包可以 入队(ENQ)到队列Q和从队列Q出队(DEQ)。用于在分组交换网络 中提供随机早期检测的装置1进一步包括出队计数器2，每次数据包从队 列Q出队时，出队计数器2递增；每次数据包入队到队列Q时，出队计 数器2重置。

队列是一种特定类型的抽象数据类型或一种集合，该集合中的实体按 序排列。以FIFO队列为例，对集合的主要(或唯一)操作是将实体增加 到后部末端位置，称为入队，以及将实体从前部末端位置移除，称为出队。 这使队列成为先入先出(FIFO)数据结构。

从图1可见，在所示的实施方式中，用于在分组交换网络中提供随机 早期检测的装置1包括存储器3中存储的系数存储表CMT，其中该系数 存储表CMT存储了预定数目M个衰减系数C，如图1所示。

用于在分组交换网络中提供随机早期检测RED的装置1进一步包括 计算单元4。计算单元4用于每次数据包入队到队列Q时，根据衰减系数 C计算各个队列Q的平均队列长度AQS，该衰减系数C从出队计数器2 重置之前出队计数器2指向的系数存储表CMT的存储地址中读取。队列 Q的存储大小，即可以入队到装置1的各个队列中的数据包数目可以根据 装置1的应用而变化。进一步地，装置1的队列Q中存储的数据包还可以 具有不同的数据包大小并且可以包括不同类型的数据包和/或数据协议。 用于在分组交换网络中提供随机早期检测RED的装置1可以形成一个更 复杂的装置或机器的部分，例如分组交换网络中的路由器。这种路由器的 每个端口可以具有不同的队列Q，其中在可能实施方式中，可以给每个队 列分配例如来自客户端的输入数据流。这种客户端可以通过链路连接到各 个路由器的端口，各个路由器包括图1所示的用于在分组交换网络中提供 随机早期检测RED的装置1。在可能实施方式中，每个客户端可以在装置 1中拥有自己的队列Q。在可能实施方式中，计算单元4可以输出计算得 到的各个队列Q的平均队列长度AQS用于进一步处理。

用于在分组交换网络中提供随机早期检测的装置1的又一可能实施方 式中，计算单元4进一步用于将计算得到的各个队列Q的平均队列长度 AQS与预定最大阈值和预定最小阈值比较。在可能实施方式中，对于装置 1的不同应用而言，最大阈值以及最小阈值是可修改的。在可能实施方式 中，如果计算得到的平均队列长度AQS超过最大阈值，计算单元4可以 为各个队列Q丢弃接收的数据包。相反，如果计算得到的平均队列长度 AQS小于最小阈值，计算单元将接收的数据包入队到各个队列Q。在又一 可能实施方式中，计算单元用于如果计算得到的平均队列长度AQS介于 最小阈值和最大阈值之间，随机丢弃接收的数据包。在根据本发明的第一 方面的用于在分组交换网络中提供随机早期检测的装置1的可能特定实施 方式中，计算单元4用于如下计算平均队列长度AQS，也称为下一平均队 列长度NEXT AQS：

NEXT AQS＝[Curr AQS–Queue Size Diff]x C+Queue Size Diff,

其中Curr AQS是当前平均队列长度AQS，

Queue Size Diff是所述队列长度差，

Queue Size Diff＝(Prev Queue Size–Curr Queue Size)/2，

其中Prev Queue Size是先前计算得到的各个队列Q的队列长度，

Curr Queue Size是当前计算得到的各个队列Q的队列长度，

C是根据各个队列Q的出队计数器2的指针值从所述系数存储表CMT 中读取的衰减系数。

在可能实施方式中，存储器3中存储的衰减系数C可以是系数存储表 CMT中存储的指数衰减函数的预先计算的衰减系数。在可能实施方式中， 系数存储表CMT内存储器3中存储的衰减函数C是预先计算的并且是可 配置的。在可能实施例中，装置1的计算单元4用于如下提前计算装置1 的存储器3中存储的指数衰减函数的衰减系数C：

x[i+1]＝x[i]x(N–W)/N

C[i+1]＝(x[i+1]–x[0])/x[0]

其中x[0]是任意数，N和W是任意数(W<N)，i是变量。

在可能示例性实施方式中，值如下：

x[0]设置为100，

W设置为1，

N设置为256。

图2所示为根据本发明的第二方面的用于在分组交换网络中提供随机 早期检测RED的方法的可能实施方式的流程图。

从图2可见，在步骤S1，下一数据包将通过各个队列Q来处理。在 进一步的步骤S2，决定数据包是否需要入队到各个队列Q或需要从各个 队列Q出队。如果数据包被出队，RED装置1的出队计数器2在图2所 示的步骤S3中递增。另一方面，如果数据包入队到各个队列Q，根据图2 所示的步骤S4中的出队计数器值指示的地址从系数存储表CMT中读取衰 减系数(也称为衰减函数系数)C。在步骤4中从系数存储表CMT中读取 了衰减系数后，在步骤S5中重置装置1的出队计数器2。在步骤S6，计 算各个队列Q的平均队列长度AQS。进一步地，在可能实施方式中，计 算等式如下：

NEXT AQS＝[Curr AQS–Queue Size Diff]x C+Queue Size Diff,

其中NEXT AQS是当前正在计算的平均队列长度AQS，

Curr AQS是当前平均队列长度AQS，

Queue Size Diff是所述队列长度差，

Queue Size Diff＝(Prev Queue Size–Curr Queue Size)/2，

其中Prev Queue Size是先前计算得到的各个队列Q的队列长度，

Curr Queue Size是当前计算得到的队列长度，以及

C是步骤S4中根据各个队列Q的出队计数器2的指针值从系数存储 表CMT中读取的衰减系数。

步骤S5和S6的执行无次序要求，它们可以并行执行或先后执行。例 如，在图2中，在步骤S6之前执行步骤S5。

在进一步的步骤S7，比较计算得到的平均队列长度AQS和预定最大 阈值TH_MAX，如果平均队列长度AQS超过预定最大阈值，在步骤S8，丢 弃数据包。如果计算得到的各个队列Q的平均队列长度AQS小于最大阈 值TH_max，在步骤S9，比较计算得到的平均队列长度AQS和最小阈值 TH_min。如果计算得到的平均队列长度AQS超过最小阈值TH_min，即介于 最小阈值和最大阈值之间，在步骤S10，丢弃接收的数据包。相反，如果 计算得到的平均队列长度AQS也低于最小阈值TH_min，在图2所示的步骤 S11中，将数据包入队。

图2的实施方式中所示的计算机制不仅执行入队的迭代，即输入数据 包，还考虑数据包的出队(输出数据包)。相应地，图2所示的计算机制 不是简单地增加出队的迭代，从而加倍计算数目以及读取当前平均队列长 度和队列长度值所需的带宽。为了避免这种不利，图2的实施方式中所示 的计算方法仅对入队进行计算，但是可以使用系数存储表CMT估算出队 数目的影响。根据本发明的方法使用出队计数器2，出队计数器2在每次 出队时递增；当遇到入队时，在步骤S5中重置出队计数器2。出队计数器 2表示数据包最后一次入队到队列Q之后的出队数目。如果遇到出队，从 系数存储表CMT中读取系数C。系数存储表CMT可以基于指数衰减函数， 其中衰减系数C为预先计算的，即曾经提前计算。每个衰减系数C存储在 存储器3的存储地址处，如图1所示。出队计数器2的值作为选择存储了 衰减函数系数的存储地址的指针。存储器3中存储的衰减系数C的数目M 可变。例如，存储器3中存储的衰减系数C的数目M可以包括1000个指 数衰减系数C。在步骤5中每次进行出队计数器2重置时，出队计数器2 设置回存储器3的系数存储表CMT中存储的第一系数C1。每次数据包从 各个队列Q出队时，在步骤S3中出队计数器2递增且指向存储了下一系 数C的下一存储地址。例如，如果行中遇到10个出队操作，出队计数器 2以10倍递增并指向系数存储表CMT中存储的第10个系数C₁₀。使用图 2所示的方法，进行随机早期检测RED来避免流量数据拥塞。根据本发明 的方法的平均队列长度AQS的计算，如图2的实施方式中所示，考虑了 数据的输入函数以及输出函数。当考虑输入和输出函数时，总的来说，根 据本发明的方法产生更好的平均队列长度。保持低计算开销以及通过继续 仅在接收的数据包上进行计算可以实现这点。确定的平均队列长度AQS 确实提高了装置1的预测数据拥塞的能力，并在分组交换网络中更好地避 免了数据拥塞。

根据另一实施例，图2所示的方法可以在数字电子电路中或在计算机 硬件、固件、计算机软件中或在其组合中实施。计算机软件包括用于执行 图2所示的方法的程序代码。

根据本发明的另一实施例，提供了一种用于在分组交换网络中提供随 机早期检测的替代装置。该装置包括用于执行图2所示的方法的处理器。

图3示出了随着时间的变化在随机的数据流量下计算得到的平均队列 长度AQS的图。从图3可见，根据本发明的用于在分组交换网络中提供 随机早期检测的方法确实显示了平均队列长度AQS的更高的准确度以及 更好的跟踪。曲线I示出了传统RED机制，其中仅为入队计算平均队列长 度AQS。第二曲线II是根据本发明的方法计算得到的平均队列长度AQS。 该方法计算了入队的平均队列长度和出队的近似值。第三曲线III示出了 数据包的入队和出队的最佳计算。从图3可见，由本发明(曲线II)进行 的平均队列长度的计算比使用用于随机早期检测的传统方法(曲线I)进 行的平均队列长度的计算更加准确，因为曲线II更接近最佳曲线III。

水平线表示没有入队的时间段，因此平均队列长度AQS保持上一个 入队值。甚至在只有出队的周期期间，平均队列长度AQS值可继续上升， 因为队列长度大于平均队列长度AQS。甚至在只有入队的周期期间，平均 队列长度AQS可继续下降，因为队列长度小于平均队列长度AQS。

在根据本发明的方法的可能实施方式中，如果计算得到的平均队列长 度AQS介于最小阈值和最大阈值之间，随机丢弃接收的数据包，其中每 个流量优先级的丢弃概率不同。在该实施方式中，进行加权随机早期检测 WRED。对于将由该机制丢弃的数据包而言，具有较高流量优先级的数据 流量的概率更小。

在又一可能实施方式中，对于数据包丢弃的响应，协议，例如TCP协议 可以增加传输率，这样避免了流量拥堵。用于在分组交换网络中提供随机早 期检测RED的方法可以在多种应用和网络中使用，尤其在结合TCP协议的 互联网中。根据本发明的用于在分组交换网络中提供随机早期检测的改进方 法可以通过保持避免拥塞的属性来增加网络的带宽效率。用于在分组交换网 络中提供随机早期检测的方法可以由任意路由器或使用随机早期检测的其他 通信设备使用来提高各个路由器或通信设备的性能。