用于聚合速率通信业务的速率控制的系统

摘要

一种对通信网络中的端口组进行速率控制的方法。如果端口组的入口速率之和小于给定速率阈值，则对端口组的每个端口的允许速率进行斜升；并且如果端口组的入口速率之和大于或等于给定速率阈值，调节端口组的每个端口的允许速率，使得端口组的允许速率之和等于所述给定的速率阈值。

说明书

技术领域

本发明通常涉及网络通信技术，尤其涉及一种用于聚合速率通信业务的速率控制的多用系统。

背景技术

以太网是部署最为广泛的局域网(LAN)技术之一。用户为以太网业务的若干优点所吸引，包括使用方便、成本效益、灵活性和大范围的业务选择等。以太网业务已经扩展到城域及更远范围。

以太网业务可以在很多方面有所变化。城域以太网论坛(MEF)定义了两种类型的以太网业务：E-Line业务和E-LAN业务，其中E-Line业务是点到点业务，E-LAN业务是多点业务并且使得每个业务实例共享公共下层物理网络的使用。MEF指定了不同的1层和2层E-LAN业务。1层E-LAN业务被称为以太网LAN(ELAN)业务，2层E-LAN业务被称为以太网虚拟LAN(EVLAN)业务。EVLAN允许用户如同连接到共享媒体的LAN一样交换帧。

当前用于指定EVLAN业务的承诺速率的两种方法为端口到端口承诺和每端口承诺。端口到端口承诺为从特定端口到另一特定端口的流量指定明确的承诺带宽。这是一种在帧中继和专线业务中提供的常规承诺。当端口到端口的流量速率较为恒定时，这种方法可能更有效。

每端口承诺为源自每个端口的流量指定承诺带宽，而不考虑目的端口在哪里。这种承诺较容易维持，因为仅需要本地端口入口流量的信息。

发明内容

本发明提供了一种对通信网络中的端口组进行速率控制的方法。如果端口组的入口速率之和小于给定速率阈值，对端口组的每个端口的允许速率进行斜升；并且如果端口组的入口速率之和大于或等于给定速率阈值，调节端口组的每个端口的允许速率，使得端口组的允许速率之和等于所述给定的速率阈值。

在一个实施例中，对于共享承诺速率的一组端口而言，每个端口获得该组端口的所有端口的入口速率信息；如果所有端口的入口速率之和小于承诺速率，提高其允许速率；并且如果所有端口的入口速率之和大于或等于承诺速率，调节其允许速率，使得所有端口的入口速率之和小于或等于承诺速率。本发明还提供了用于实施上文概述的速率控制系统的其它实施例。

以下的说明和附图详细阐述了本发明的若干例示性实施例。这些实施例仅表示可以使用本发明的各种方式的若干种。

附图说明

为了更完整地理解本公开及其优点，现在结合附图参考以下描述，在附图中类似的附图标记表示类似的部件：

图1示出了根据本发明的聚合速率业务模型；

图2示出了根据本发明的速率控制算法的行为；

图3示出了根据本发明的速率控制算法的操作；

图4示出了根据本发明“理想”情况下使用的带宽，在“理想”情况下，端口的提供速率以相同方式(在锁定步骤中)变化且所有通信延迟时间都相同；

图5示出了根据本发明的真实情况下使用的带宽，在真实情况下，端口的提供速率是异步的，且两端口之间的所有通信等待时间独立于其它端口之间的延迟时间；以及

图6示出了根据本发明提供容量裕量的业务提供商的容量。

具体实施方式

提供以下论述，以使本领域的技术人员能够完成和使用本发明。可以在不脱离本文所定义的本发明的精神和范围的前提下，将本文所述的普遍原理应用于除了下文详述的实施例和应用之外的实施例和应用。本发明并非意在限于图示的实施例，而是要被解释为符合本文披露的原理和特征的最宽范围。

在本发明的以下描述中使用了如下术语：

调节：当测得的入口速率之和足够高，使得速率持续上升可能导致耗尽与聚合组相关的容量时，使用的允许速率分配的方法。

聚合组：共享承诺速率的端口集合。

入口：从业务用户到业务提供商的方向。

端口：用户访问业务提供商网络的业务的接口。范例为802.1adProvider Edge Bridge(PEB)端口或Metropolitan Ethernet Forum(MEF)User-Network Interface(UNI)。

贪婪端口：当a)当前的入口速率之和大于被允许值时；以及b)用于降低速率的对策是降低具有最高当前入口速率的端口(或多个端口)的允许速率时，入口速率被降低的端口。

非贪婪端口：不贪婪的端口。

本地端口：在一些描述中用于指称聚合组端口集合中特定端口的术语。例如，可以将本地端口说成“所接收的速率值被保存在本地端口维护的数组R中”。

业务提供商网络(SPN)：为客户提供连接业务的网络，例如IEEE 802.1adProvider Bridged Network(PBN)或MEF Metropolitan Ethernet(MEN)。

斜升：一种分配允许速率的方法，为允许速率分配大于所测入口速率当前值的值。

速率消息：从与聚合组相关的端口周期地分发到与聚合组相关的其它所有端口的消息，携带着由该端口测量的(且可能经平滑化或滤波的)入口速率值。

业务实例：由业务提供商网络提供的连接业务的实例。仅在与相同业务实例相关的端口之间允许连接。范例为IEEE 802.1ad Service VirtualLocal Area network(SVLAN)或MEF Ethernet Virtual Connection(EVC)。

以下介绍本发明中所用的符号。为了表示方便，符号∑代表除非另行指定。I(i，t)表示在时段t末尾与端口i相关的I值。

其它标识符如下：

A_i(允许速率)：在聚合组的端口i处允许来自用户的流量进入业务提供商网络的最大速率。I_i总是≤A_i·O_i>A_i表示I_i＝A_i。

B：在执行允许速率的斜升时，用于下一时段的A_i值应当超出I_i的当前值的最小量。

C(额定容量)：业务提供商承诺的业务提供商网络之内的链路上供聚合组使用的容量。容量承诺C确保在任何时候都兑现指定的业务承诺。业务提供商可以承诺比C小的带宽，并承担不在所有时候兑现承诺的风险。

D_ij(延迟)：以秒测量的时间期间，在最近的时段端口i测量其入口速率I_i时开始，在端口j计算S时引用相应值R_i时结束。

D(延迟)：聚合组中所有端口对(i，j)的d_ij的最大值。

F(提供速率之和)：所有端口i的提供速率(O_i)值之和。

G(承诺速率)：当入口速率已达到稳定状态时，使∑I_i≥G的规定值。其为聚合组的承诺聚合速率。

I_i(入口速率)：由聚合组的端口i引入的流量实际(测量)速率。该速率可以是经过低通滤波的或经平滑化，以实现稳定性。

M_low(低裕量)：用于提供裕量或缓冲区以确保S≥G追随速率限制的值。

M_high(高裕量)：用于提供裕量或缓冲区以确保业务提供商容量承诺超过计算的容量需求的值。

O_i(提供的速率)：在聚合组的端口i处由用户提供给业务提供商的流量速率。

N(端口数)：与聚合组相关的端口数。

Q：聚合组中Ri超过计算的最大允许速率X的端口数。

R_i：本地端口在来自端口i的速率消息中最近接收到的I_i值。R_local被分配以I_local的当前值。

S：聚合组中所有端口i的R_i之和。

S_max：S获得的最大值。

t：过去的持续时间为T的时段的数量计数。

T：聚合组的端口i广播I_i值的固定时段。在该时间界限上还执行允许速率的重新计算。

X：在速率调节之后可以分配给聚合组中任意端口i的A_i最大值。

现在参考图1，示出了聚合速率业务模型(100)的范例。业务提供商网络(110)向客户(120)提供聚合速率通信业务。客户(120)与7个端口，即端口(131)-(137)相关，以访问业务提供商网络(110)。这7个端口共享一个承诺速率G，形成聚合组。可以使用速率控制算法控制聚合组之内每个端口的入口速率，以确保业务提供商网络(110)提供的聚合速率业务符合服务等级协议(SLA)。业务提供商网络(110)可以具有任意拓扑。聚合组中的端口公平地共享聚合组的容量。

聚合速率业务可以由承诺速率G、在每个时段T期间允许的聚合速率的增加量B以及时段长度T来表征。SLA可以指定聚合速率业务模型确保：

1)总的入口速率∑I_i大于或等于G；或

2)具有大于或等于当前入口速率I_i的提供速率O_i的任何端口在下一时段T期间可以将其入口速率增大至少为B的量。

在一个实施例中，每个端口在当前时段t期间测量I_i。在时段t结束时，端口i，例如端口(131)分发速率消息，该消息含有测得的(且可能经平滑化和/或滤波的)入口速率值I_i以及端口i的标识。可以利用广播、组播或单播的方式分发速率消息。

与包括n个端口的聚合组相关联的端口接收聚合组内其它端口的每个发起的速率消息。端口i发送速率消息和另一端口j接收消息之间的时延最多为D秒。例如端口(137)的端口j维护n个元素的数组R，其包含最近从其它n-1个端口接收到的速率值。例如端口j(137)的端口不向其自身发送速率消息。相反，端口j(137)处数组R的元素j包含在端口j测量的最新入口速率。在此当指称特定端口，例如端口j(137)时，可以将该端口称为本地端口。本地端口可以利用在本地端口测得的入口速率以及从聚合组的其它端口接收到的速率信息为自己确定下一时段的允许速率。可以分别用A_local和I_local表示本地端口的允许速率和入口速率。

通过接收聚合组中所有其它端口分发的速率消息，每个端口都可以获得所有其它端口的入口速率信息，并使用速率控制方法控制其下一时段的允许速率。在每个时段t的末尾并在聚合组的每个端口i上计算最近接收的入口速率之和，如下式所示：

S＝∑R_i。

在时段t的末尾计算S之后，计算A_local。因此，聚合组内每个端口经由速率消息从聚合组之内的所有其它端口接收入口速率信息，然后计算允许速率。根据S和G的相对值可以使用两种计算方法之一。

如果(S<G)，进行斜升；否则，如果(S≥G)，进行调节。

在一个实施例中，在斜升时可以分两个阶段计算下一时段t的A_local值。第一个阶段为：

A_local＝I_local+B。

亦即，可以将在时段t期间以速率Ii发送的端口i在时段t+1期间限制为A_i＝I_i+B。可以在服务等级协议中定义B。在没有延迟的情况下，这种斜升方法确保在时段t+1期间(∑I_i<G+nB)，因为在时段t中∑I_i<G，n个端口的每个都可以将其入口速率增大不超过B。

第二阶段为：

If(S+nB<G){

 A_local＝A_local+(G-(S+nB))/(nD)；

}

(S+nB)为下一时段中S可以达到的最大值。如果该值小于G，那么可以进一步使A_local增大(G-(S+nB))/(nD)，这不会有下一延迟D期间流量超过C的风险。

本发明中斜升的可替换实施例省去了第二阶段的斜升。在这种情况下，以每个时段t固定的量B升高每个端口处的允许速率，而不考虑可能可用的额外容量。这种技术被称为“线性”斜升，以和“加速”斜升区别开，后者包括第一和第二阶段斜升两者。线性斜升比加速斜升更慢地靠近最大速率。然而，业务确认得到简化，因为在斜升期间的预期速率增加是恒定的。

对于调节而言，一个实施例是计算允许速率X的最大值，使得

G＝∑R_i(对于R_i<X)+∑X(对于R_i≥X)。

上面的表达式“∑X(for R_i≥X)”与“Q*X”具有相同含义，其中Q为聚合组中具有I_i≥X属性的端口数。

如果已经确定了X的值，那么

A_local＝MIN(I_local，X)+B。

用于计算X的方法的一个实施例按照降序(R1最大)对数组R的元素R1到Rn排序，其中数组R由聚合组之内所有n个端口的Ri构成。然后从最大元素到最小元素逐个通过数组R。在每个步骤中，将速率值大于当前元素的所有元素(即数组中具有较小索引值的元素)替换为当前元素的值。当数组R中的所有元素之和小于或等于聚合速率G时，中止该步进过程。当发生这种情况时，索引低于当前索引的元素代表允许速率已被降低的“贪婪”端口。

可以利用如下形式的伪代码实现上述算法的实施例：

按降序排列数组R的R1到Rn；

  i＝1；

while(i*Ri+∑Rj(for j＝(i+1)to n)>G){

  i++；

}

数组元素1到(i-1)的速率代表“贪婪”端口。贪婪端口均等地共享聚合速率G减去数组元素i到n的速率后剩余的带宽，且X被计算为：

X＝(G-∑R_j(j＝i到n))/(i-1)。

计算X的方法的第二实施例按降序(R1最大)排列数组R的元素R1到Rn；并对R的所有值求和。在接收到速率消息时可以渐进地执行上述两个操作(排序和求和)。然后从最大值元素(i＝1)到最小值元素(i＝n)逐个通过数组R。在每个步骤中，用当前元素的值(R_i)逻辑地替换索引小于i的所有元素(无需物理地更新这些数组元素)。元素1到(i-1)之和被计算为(i-1)*R_i。通过使当前sumAtOrAboveI递减R_i在每个步骤将元素i到n之和作为sumAtOrAboveI维护。当((i-1)*R_i+sumAtOrAboveI)的值小于或等于承诺速率G时中止步进过程。当发生这种情况时，索引低于当前索引的元素代表允许速率已被降低的“贪婪”端口。

可以利用如下形式的伪代码实现该算法的实施例：

按降序排列数组R的R1到Rn；

  sum＝数组R中的值之和；

  i＝1；

//sumAtOrAboveI表示索引大于或等于当前索引i的数组元素值之和。

sumAtOrAboveI＝sum；

while(((i-1)*Ri+sumAtOrAboveI)>G){

 i++；

 sumAtOrAboveI＝sumAtOrAboveI-Ri；

}

数组元素1到(i-1)的速率代表“贪婪”端口。贪婪端口均等地共享承诺速率G减去数组元素i到n的速率后剩余的带宽，且X被计算为：

X＝(G-sumAtOrAboveI)/(i-1)。

计算X的方法的第三实施例将X的可能值空间划分为均等的部分，并判断X的期望值是位于上部分还是下部分。在选定部分上递归地进行该程序，直到利用X的当前值获得的速率之和大致等于G为止。该算法以类似于折半查找法的方式运行。

实施该算法的伪代码可以如下所示：

interval＝G/2；

  X＝G/2；

temp＝∑R_i(for R_i<X)+∑X(for R_i≥X)；

while(temp！≈G){

  interval＝interval/2；

  if(temp>G){

   X＝X-interval；

  }else{

   X＝X+interval；

  }

  temp＝∑R_i(for R_i<X)+∑X(for R_i≥X)；

}

//确定代表不贪婪端口的第一数组元素的索引。

while(R_j>X){

 j++；

}

//确定贪婪端口的数量：

Q＝j-1；

贪婪端口共享聚合速率减去非贪婪端口速率剩余的带宽，X被计算为：

X＝(G-∑R_i(for R_i<X))/Q。

由以下伪代码例示了计算X的方法的第四实施例。本实施例不需要对数组值排序。

//Q为“贪婪”端口的数量

  Q＝1；

  temp＝∑R_i；

//非贪婪端口当前的速率之和

temp＝temp-max(R_i)；

 j＝index(max(R_i))；

//用0取代数组中的最大值

R_i＝0；

//X曾是数组中的第二大速率值，现在为最大值

  X＝max(R_i)；

//当贪婪端口给出比非贪婪端口更高的速率时退出循环：

loop until((G-temp)/Q>X)

{

  //数组中最大的剩余值

  j＝index(max(R_i))；

  //用0取代最大剩余值

  R_j＝0；

  //非贪婪端口的当前速率之和

  temp＝temp-X；

  the number of“greedy”ports

  Q++；

//X曾为数组中的第二大值，现在为最大的

  X＝max(R_i)；

}

//分配给贪婪端口的速率

X＝(G-temp)/Q；

上述速率控制算法包括评估X值的准则：

G＝∑R_i(对于R_i<X)+∑X(对于R_i≥X)；

或

G≈∑R_i(对于R_i<X)+∑X(对于R_i≥X)；

该速率控制算法包括上述具体算法和体现出算法实质原理的这些算法的变型。

针对下述情形在图2中例示了速率控制算法的行为：客户具有十个端口的聚合组，端口之间的最大路径距离为1000km，承诺速率为1Gbps。每10ms进行一次速率广播和允许速率计算。允许每个端口的入口速率每10ms间隔增加10Mbps。满足速率承诺所需的总容量为1.3Gbps。如果同时在每个端口确保1Gbps速率，则至少需要5Gbps的承诺，可以将此与这种情况相比。在图2中，曲线(210)示出了从第一端口传输的第一文件的入口流量，曲线(220)示出了从第二端口传输的第二文件的入口流量。入口流量的实际和由曲线(230)示出。曲线(240)为从延迟的速率消息获悉的入口流量之和。

图3所示的模拟结果示出了简单情况下的速率控制算法的操作，在该情况下聚合组包含十个成员端口。在该范例中，端口2，即曲线(310)开始发送文件，过一些时间之后，端口9，即曲线(320)开始发送文件，再过一些时间之后，端口2完成文件的发送。曲线(330)示出了端口2和9的入口流量之和。曲线(330)的最大值表示支持承诺速率G所需的容量C。当仅有单个端口在发送时，曲线(330)与单个发送端口的速率一致。当一次有两个端口发送时，由于端口在从其它端口接收速率信息时经历的延迟，入口流量曲线(330)之和超过承诺速率。

图4和5示出，端口工作在“步伐一致”状态(即它们的活动彼此同步)的假设提供了D值结果的保守情况或最坏情况。放松该假设并将端口活动视为异步，仅可以减小D的值。图4示出了“理想”情形，其中在每个端口在相同时刻发生允许速率的变化，且端口之间的所有通信延迟都是相同的。有四个被称为A(410)、B(420)、C(430)和D(440)的端口。仅从A(410)到其它端口示出了速率消息，其包括速率消息(460)、(470)和(480)。参数如下：G＝12，B＝2，n＝4，nB＝8，D＝2，(n-1)BD＝12，G+nB+(n-1)BD＝32。图4示出了每个端口具有最大入口速率8和入口速率和32。

但实际上，如图5所示，端口是异步的，且在端口对之间的所有通信延迟是不同的。在图5中，还有四个被称为A(510)、B(520)、C(530)和D(540)的端口。仅从A到其它端口示出了速率消息，包括速率消息(560)、(570)和(580)。图5示出了三个端口具有入口速率8，一个端口具有入口速率6。在这种情况下，降低了所需的容量C。这比图4所示的最坏情况方案要好(即，需要更少容量)。

可以使用速率控制算法和SLA确定在提供聚合速率业务的系统中支持承诺速率所需的最坏情况容量。

在没有延迟的情况下，使用上述速率控制算法之一确保了在每个端口分配下一时段的允许速率值，使得∑A_i≤S+nB，其中S为与当前时段相关的∑R_i的值。可以不允许S的值增大到超过G的值。因此，在没有延迟的情况下(即D＝0)，网络内处于组成员之间的所有通信的数据路径上的链路上所需的容量(即网络曲线图中的割点)不超过G+nB。

在存在延迟的情况下(D>O)，n-1个端口的速率消息被延迟。本地端口(计算速率的地点)处的速率消息未被延迟，因为未发送物理消息。对于每个远程端口而言，在每个时段T中入口速率可以升高B。在延迟D期间有D/T个持续时间为T的时段。可以将D计算为两个端口之间的往返延迟的一半。在延迟D期间，远程端口的速率可以升高BD/T。因此，S的值(基于所接收的速率)将的∑Ii值低估了(n-1)BD/T。可以推知该链路上所需的容量为G+nB+(n-1)BD/T。

重要的是要指出，该容量是针对所有流量都经过受检链路的最坏情况计算的。如果在不同路径上传输流量，根据对经过不同路径的流量分发的了解，可以减小上面计算的容量需求。

可能会担心瞬态网络状况(例如D值中未反映出来的端口物理位置的变化)可能会导致无法提供协议承诺的聚合速率。

现在参考图6，C表示有延迟D的情况下的总容量需求，(n-1)BD/T表示有延迟的情况下具体需要的容量。Smax表示延迟为零时的容量需求，nB为当前时段期间允许的入口速率增加。G表示承诺速率。为了减小业务提供商网络的瞬态变化导致因所需容量波动而超出容量的可能性，业务提供商可以划拨额外的容量M_low和/或M_high，以在客户协议中指定的标称承诺速率和业务提供商实际实施的承诺之间提供缓冲区。如果M_low>0，可以修改速率控制算法，使得G的所有实例变为(G+M_low)。容量需求可以改变为(G+M_low)+nB+(n-1)BD/T+M_high。

可以以完全独立于聚合速率业务模型或任何特定承诺速率的方式应用本发明的速率控制方法。端口可以通过某些非特定的手段(例如拥塞通知)了解到最好减小(或增大)网络入口流量的聚合量。可以将速率控制算法中的G值设置成比当前入口速率之和或以前使用的G值更低(或更高)的值。效果是公平地减小(或增大)入口速率，使得(例如)以低速率发送的端口不会因拥塞而发生速率降低，因为这种端口不可能对拥塞负责。

提供了所公开的实施例的前述描述，以使本领域的技术人员能够完成或使用本发明。在不脱离本发明的精神或范围的前提下，本领域的技术人员将很容易想到对这些实施例的各种修改，并且可以将本文定义的一般原理应用于其它实施例。因此，本发明并非意在限于图示的实施例，而是要被解释为符合本文披露的原理和新颖特征的最宽范围。