在接入节点的ATM交换设备中实现GFR业务的系统和方法

摘要

本发明公开了一种在ATM环境，例如接入节点的ATM交换设备中实现GFR业务的方案。根据采用的业务量监管器/整形器算法计算得到的时间戳，GRF流的调整在两种模式，保证速率模式和非保证速率模式之间切换。连接着监管块的调度器，在确定保证业务帧开始时，从保证流队列中调度信元，通过ATM交换设备以保证速率传输。该调度器还在以非保证速率传输的时间戳(TSNGF)早于以保证速率传输下一保证业务帧的时间戳(TSGF)时，切换到非保证速率模式，调度来自流队列的信元，以非保证速率传输。

说明书

相关申请

本申请公开的主题涉及下列共有的共同未决的美国专利申请所公开的主题：(i)James W.Dove等人的“Stackplane Architecture”，于1999年12月22日申请，申请号为09/469,897；(ii)Eric Friedrichs等人的“Scalable Architecture For An Access Node”，于2002年6月27申请，中请号为10/280,604；(代理卷号为：1285-0090US)；(iii)Thornton Collins等人的“Integrated Gateway Functionality In An Access Network Element”，于2001年11月2日申请，申请号为10/052,846；(iv)Mudhafar Hassan-Ali等人的“Multicasting System And Method For Use In An Access Node’sATM Switch Fabric”，于同一天申请的，美国申请号为10/280,959；(代理卷号为：1285-0100US)；(v)Mudhafar Hassan-Ali等人的“Virtual GroupConnection Scheme For ATM Architecture In An Access Node”，于同一天中请的，美国申请号为10/280,604；(代理卷号为：1285-0099US)；(vi)Mudhafar Hassan-Ali等人的“Calendar Heap System And Method ForEfficient Sorting，”，于同一天申请的，美国申请号为10/281,033；(代理卷号为：1285-0101US)；(vii)Mudhafar Hassan-Ali等人的“HierarchicalScheduler Architecture For Use With An Access Node，”，于同一天申请的，美国申请号为10/280,894；(代理卷号为：1285-0103US)；这些专利申请通过引用并入本发明。

技术领域

本发明总的来说涉及电信领域。确切地说，本发明涉及在接入节点的异步传输模式(ATM)交换设备中实现保证帧频业务(GFR)的一种系统和方法，但本发明并不局限于此。

背景技术

远程接入市场正在经历一个大的转变。三个因素促成了这种转变。第一是用户数量的增长，例如需要高性能因特网的和多媒体远程接入的小型办公/居家办公(SOHO)用户数量的增长。在电信方面自由化的政府行为是另一因素，各地通过消除本地市场规范来培育更为广泛的竞争。第三因素，也是最后一个因素，是公共电话交换网(PSTN)的拥塞，PSTN的设计和开发原本只是为了语音业务量。

电信技术的若干重大进展使得电信网络的骨干连接能够具备高吞吐量。例如，通过在同步光网(SONET)/同步数字体系(SDH)物理层上实现异步传输模式(ATM)网络技术，电信网络能够达到几百兆比特每秒(Mbps)的数据速率。但是，为满足远程接入的带宽需求所做出的努力受限于电信局中心局(CO)和用户的远端站点之间已有的双绞铜线基础设施(也就是接入网)，一般称作本地环路。在电信领域中，这些限制有时统一称作“最后一公里”问题。

为避免最后一公里问题所产生的瓶颈，当前接入网解决方案在本地环路中也采用光纤技术。与利用高速电信网一样，基于光纤的本地环路基础设施的体系结构一般采用SONET作为物理层技术。除了网络设计的改进，随着光部件和相关光电子的最近进展，使得宽带接入日趋普及。

此外，伴随着因特网用户数量的显著增长，产生了对用分组交换网(PSN)基础设施(例如，那些基于因特网协议(IP)进行寻址的基础设施)来替代当前电信网所采用的已有电路交换网络(CSN)基础设施的浓厚兴趣。从网络运营商角度来讲，分组交换基础设施中固有的业务总量使得每个最终用户的传输成本和基础设施成本得以降低。最终，这种成本的降低使得网络运营商能够将由此节省的成本转移到最终用户身上。

因此，正在开发一种新型的以业务为中心的网络(不同于已有的以话音为中心和数据为中心的网络)，用以实现众所周知的下一代网络(NGN)基础设施，在下一代网络基础设施中综合的话音/数据/视频应用可以利用端到端传输路径中PSN上的分组传输机制来提供。前面间接提到，人们相信，在接入网中采用分组网络基础设施能够提供更高的传输效率，更低的操作和运营成本，以及统一的接入。

传统接入系统允许接入数字本地话音交换机，例如第5类交换机，这通过延伸多根金属环路，并将它们集中成一束，从而高效传送时分复用(TDM)话音业务量来实现。一般情况下，这种接入网络的体系结构使用多种配置下的一个或多个接入节点，前述配置可以是例如点对点链、环等，其中接入节点自身可以包括多个信道组，后者提供的线路接口服务于大量用户。

但是，为了提供更好的功能和业务提供，要求当前的接入网支持先进的传输技术，例如SONET，对于节点的内部结构也是如此。在这些节点中，ATM用于承载除传统的TDM业务，如T1和TDM-DS3业务之外的大部分用户业务量。因此，接入节点设计需要支持TDM和ATM交换设备。

ATM论坛提供了一组规范，用以管理ATM交换设备的不同方面，包括业务监管/整形功能，这些功能是支持不同业务类别(CoS)，例如恒定比特率(CBR)、可变比特率(VBR)、保证帧频(GFR)和类似业务类别所必需的。虽然特定数据应用对提供GFR业务的需求尤为迫切，但标准ATM规范没有给出具体实现或设计细节。

另一方面，人们发现当前ATM应用中已知的GRF实现在特定重要问题方面有所欠缺。首先，已有的GRF方案通常需要使用大量存储器，因为它们使用的缓冲器结构为GFR流的保证和非保证部分共享。此外，结合这些方案不够多样，不足以匹配ATM规范中可应用的GFR业务属性。

发明内容

因此，本发明提供了一种在ATM环境(例如接入节点的ATM交换设备)中实现GFR业务的方案，该方案有效地克服了前述不足。根据采用的业务量监管器/整形器算法计算得到的时间戳，GRF流的调整在两种模式，保证速率模式和非保证速率模式之间切换，从而在带宽可用情况下，可以实现高于最小保证速率的速率。

一方面，本发明涉及一种在具有异步传输模式(ATM)交换设备的接入网元中实现保证帧频(GFR)业务的方法，包括步骤：将识别出的用于保证业务的入信元压入保证流队列中；在确定保证业务帧开始时，从所述保证流队列中调度信元，通过所述ATM交换设备以保证速率传输；确定调度下一保证业务帧的未来时间戳(TS_GF)；确定从所述保证流队列中以非保证速率调度信元的未来时间戳(TS_NGF)；当所述TS_NGF早于所述TS_GF，调度来自所述保证流队列的信元，以所述非保证速率传输；以及，在到达所述TS_GF时，调度下一保证业务帧的信元，以所述保证速率传输。

另一方面，本发明涉及一种在具有异步传输模式(ATM)交换设备的接入网元中实现保证帧频(GFR)业务的系统，包括：一个GFR监管块，用于将识别出的用于保证业务的入信元压入保证流队列中；一种调度装置，在确定保证业务帧开始时，从所述保证流队列中调度信元，通过所述ATM交换设备以保证速率传输；确定调度下一保证业务帧的未来时间戳(TS_GF)的装置；确定从所述保证流队列中以非保证速率调度信元的未来时间戳(TS_NGF)的装置；当所述TS_NGF早于所述TS_GF，调度来自所述保证流队列的信元，以非保证速率传输的装置；以及，在到达所述TS_GF时，调度下一保证帧的信元，以所述保证速率传输的装置。

附图说明

通过下面的详细描述，并结合附图，可以对本发明有更为全面的理解，在附图中：

图1给出了示例性的接入节点，该节点的ATM交换设备中可以有利地实现本发明的内容；

图2给出了多层多平面调度器的一种实施方式，它在图1所示ATM交换设备中实现GFR业务；

图3描述的高层功能框图说明了实现本发明内容的调度器漏桶模块和优先级队列模块；

图4的流程图描述了按照本发明的内容实现GFR业务的示例性方法中用到的各种操作；

图5给出了实现本发明GFR业务的系统；

图6是GFR监管方案的一种表示；

图7的流程图描述了GFR监管方案中用到的操作；

图8的流程图描述了按照本发明的内容的超时处理中用到的操作；以及

图9给出了验证过期时间值的多段定时窗口方案。

具体实施方式

下面根据Mudhafar Hassan-Ali等人同一天提交的题为“HierarchicalScheduler Architecture For Use With An Access Node”的美国专利申请，申请号为10/280,894(代理人卷号：1285-0103US)的共同拥有共同未决美国专利申请(此后称为分层调度器体系结构申请)的教导，给出本发明的一种实施方式，前述专利申请在此引用并入本发明。在该申请中详细描述到，接入网中的电信节点可以包括一种可调整的体系结构，其中提供TDM和ATM交换设备，用以支持性能水平的提高。

此外，与ATM交换设备关联的调度功能可以按照业务类别(也就是业务平面)，并且跨多种层次数据管道集(也就是子端口、总线级、架级、栈面级以及管道级等等，视为各种聚合层)进行划分，这对可调整硬件体系结构而言是必要的，这样，接入网络节点的ATM交换设备中能够有效实现业务量合同遵从，以及必要连接隔离和公平带宽分配。

下面参看本专利申请的附图，其中相同或类似的元件在几张图中标以相同的标号，给出的各种元件不一定按比例绘出，尤其是参看图1，该图描述了一种例示性的接入节点100，它具有ATM交换设备102的高层功能性表示，设备102可以有利地实现本发明的教导。在前面引用的分层调度器体系结构申请中解释了，交换设备102的总体功能包括：监管；运行、管理和维护(OAM)；信头转换；排队和许可控制；以及调度和业务量整形。可以很容易地看出，发往交换设备102的业务量通过多个接口提供。传输接口104用于将节点的设备连接到骨干网，例如ATM网络105。栈面接口106用于将业务量从辅架组链107(例如包括分层调度器体系结构申请的图5所示信道组506-1到506-4，以及信道组508-1到508-4)传送到交换设备102。通过线路单元(LU)107-1到107-N的多个用户接口举例说明了各种业务源，如xDSL，T1，ISDN，DS-3/OC-3等，这些业务源可以通过适当的总线级端口109-1到109-N，与交换设备102相连。线路单元接口中的一个接口可以连接到作为接入网(未在该图中示出)一部分的RT111。

针对内部ATM业务量可以定义两种类型ATM连接：虚信道连接(VCC)和虚通道连接(VPC)。VCC一般是ATM连接能有的最小单元，可以由包括一对物理接口上的标识符，也就是虚信道标识(VCI)和虚通道标识(VPI)的唯一值来表示。VPC则定义为共享同一VPI值和共同资源池(例如带宽等)的一组全部的流。因此，可以看出，VP是一束VC，这样，通过减少需要管理的部件数量，简化了ATM环境下的连接管理，其中每个连接由其唯一VPI/VCI对来标识。

从拓扑角度来看，VCC或VPC可以是以下两种类型之一：(i)点到点连接，其中建立双向连接，且每个方向中的信源可以不同，以及(ii)点到多点连接，它通常采用多个单向连接，在设备间实现组播传输。

此外，也可以在本发明中实现另一层ATM连接层次，称为虚拟组连接或VGC。有关VGC实现的细节在Mudhafar Hassan-Ali等人同一天提交的题为“Virtual Group Connection Scheme For ATMArchitecture In An Access Node”，美国专利申请号：10/280,604；(代理卷号为：1285-0099US)的共同拥有共同未决美国专利中给出，该专利通过引用并入。

因此，进入交换设备102(其功能可以以ATM交叉连接交换设备(XCF)卡形式实现)的流的入口业务量管理一般包括三个阶段：监管、VC队列/缓冲器分配和整形/调度。在一种实施方式中，与这些级相关的硬件可以整合到XCF卡中。监管器的主要功能是确保接收的信元与所应用的连接描述符一致。如果不一致，就可以通过清除/设置信元头中的信元丢弃优先级(CLP)来丢弃入信元或者打标记(也就是带标记)。一般来说，监管功能采用ITU-T1.371和ATM论坛ATMF-TM-121标准中描述的众所周知的算法来实现。实际上，这些算法(一般称为通用信元速率算法或GCRA)采用所谓的信贷计数器，称为桶(bucket)，以及信贷，称为令牌。在接收到信元时，如果计数器(也就是桶)有足够的信贷(也就是令牌)，那么接纳该信元；否则，该信元标记成低优先级信元或者被丢弃。此外，在分层调度器体系结构申请中解释了，基于GCRA的算法可以在所谓的漏桶模块(LBM)中实现，用以实现若干ATM业务类别(基于业务类别(CoS)排序，业务类别由类似于时间敏感性、峰值和持续带宽保证、突发性和交付保证等因素定义)的业务量监管和业务量整形(也就是调度)。

层次调度功能通过优先级队列模块(PQM)(该图中未示出)实现，其中各层对条目实现调度功能，根据流集合，该条目可以是以下之一：子端口、总线、端口和管道。实际上，当交换设备接收到新流的信元时，该数据流由调度器中的一个条目如下表示。从LBM接收到流ID(也就是FID)，基于CoS/QoS，流数据(也就是FID和时间戳或TS)，存储在应用的第一层数据结构中。在第一层的所有的竞争子端口中(例如线路单元的不同流)，层仲裁器只会选择一个具有最小TS的子端口，然后将它转发给下一层的仲载机构，也就是第二层仲裁。第二层数据结构相应包含不同子端口的“优胜FID/TS”数据。同样，只有一个具有最小TS的条目被选出，转发给第三层。对其它的聚合层如此重复这种处理，最终得到每种业务优先级类的优胜提名(也就是优胜信元的FID/TS数据)。在分层调度器体系结构申请中还指出了，对每个业务类平面执行这种层基仲裁，从而得到每个平面的优胜提名，这样，考虑CoS的基于时间戳的仲裁器对各个业务平面的优胜者进行仲裁，选择最终的优胜者。

因此，应当认识到，各层的仲裁涉及管理与其相关的PQ结构，用于选择该层的优胜者。一般来说，PQ结构以树的形式实现，其中数据节点(代表例如接纳信元或低层选择的信元的TS/FID)按照特定插入/删除准则安置。图2给出了一种多层、多平面调度器200的实施方式，它在图1所示ATM交换设备中实现调度功能，为MC流提供服务。各个聚合层的调度器200的每一个PQ实体都以树结构示出，得到每个业务平面的总嵌套树方案。下面的表给出了各个示例性业务以及相关的参数信息：

表1

    业务类别    应用    参数    实时恒定比特率(CBR)，实时可变比特率(rt-VBR)    话音(单信道或中继线)，VBR视频，游戏    峰值信元率(PCR)，信元时延变化容限  (CDVT)    非实时可变比特率(nrt-VBR)    数据，多媒体，电邮，视频流    PCR，CDVT，可持续信元率(SCR)，最大突发流量大小(MBS)    保证帧频(GFR)    附加数据，浏览页面，因特网    PCR，CDVT，MBS，最大信元率(MCR)，最大帧大小(MFS)    尽力而为(未指定比特率或者UBR)    廉价数据，页面浏览和因特网    PCR，CDVT

与参数数据和QoS级别相关的其它细节可以参见分层调度器体系结构申请。继续图2，标号206-1到206-6分别指以下业务平面：rt[CBR/VBR]-高平面，rt[CBR/VBR]-中平面，rt[CBR/VBR]-低平面，nrt-VBR和GFR平面，GFR平面，以及UBR(也就是，可用最佳)平面。标号208是指对应于子端口仲裁器1305-i的PQ树，其中PQ树基于相应子端口所支持的VC连接生成。实际上，调度器的每个子端口采用(或者构造)一个PQ，它是存储所有活跃FID的数据结构(也就是与该FID相关的VC队列至少有一个信元)。所有子端口仲裁器的优胜者(例如，子端口仲裁器222-i和222-j)都被转发，填充与总线级仲裁器224-1相关联的下一级PQ树结构210。同样，总线级仲裁器224-1和224-k转发各个选择给架级PQ结构212。架级仲裁器214、栈面接口216、传输层接口218转发它们的选择给管道级仲裁器220，后者为特定业务平面选择一个优胜提名。

多种数据结构可以用于实现本专利申请所提出的层次调度中使用的树基PQ。在本发明的一种示例性实施方式中，PQ实体可以以堆结构实现。虽然堆实现通常在存储器使用方面表现优异，它受限于其算法复杂性，后者在高速设计中会使吞吐量受限。因此，在另一实现方式中，每一层特定的PQ实体作为综合“日历堆”结构实现，综合“日历堆”结构的详细描述由Mudhafar Hassan-Ali等人同一天提交的题为的“Calendar Heap System And Method For EfficientSorting，”，美国申请号为10/281,033；(代理卷号为：1285-0101US)，该专利通过引用并入。

现在参看图3，给出的高层框图说明了一种交换设备卡300，它包括调度器块310，用于按照本发明的内容实现接入节点中的GFR业务。调度器块310包括PQM302和LBM308，两者之间的多个接口实现与调度器操作相关的消息/数据通信。这些接口包括过期接口314，优胜者流接口316，堆/流重连接接口318，以及堆/流插入接口320。PQM块302还与多个存储器块304-1到304-4接口，用以存储与上述分层调度器体系结构相关的各个PQ数据结构。连接到PQM块302的控制存储器306存储与PQM操作相关的控制程序代码。

LBM块308也与一个或多个存储器块，例如存储器312接口，用以存储与LBM实现的监管和整形算法处理相关的信息。在一种实现中，LBM用漏桶计算器作为状态机，它按照业务量合同和它所属连接的历史决定信元是否合格。在用于监管时，该状态机决定入信元是否符合要求，而用于整形时，它决定信元符合业务要求的时刻。根据业务类别的不同，提供了带有特定参数(也就是业务量描述符、漏桶参数(理论到达时间或TAT、TS值、信元到达时间等)的一个或多个特定算法处理，用以实现LBM的监管和整形操作。下面将会详细描述，本发明的GFR业务采用两种不同的算法LB处理来实现，每种算法具有不同的参数集，可分别用于调整保证流部分和非保证流部分。

LBM块308还与上下文存储器模块(CMM)332和队列核心模块(QCM)332接口，用以实现其整体功能，为该ATM交换设备服务的所有流维护漏桶信息。与CMM块332关联的信元到达接口348充当入信元的进入点。与CMM模块332相关联的上下文存储器334用于存储基于流的信息，例如QoS、FID、漏桶参数、目的路径标记(DPT)信息等。此外，可以提供统计存储器块336，用以收集与该ATM交换设备卡300所服务的连接相关的性能监控数据。入口流上下文信息和出口流上下文信息分别通过接口338和340提供给QCM块322。头/尾指针存储器352和统计存储器354连接到QCM块322。与其相关联的信元指针接口356基于调度操作指向符合业务条件的信元。

QCM块322和LBM块308之间的接口包括以下接口：流激活接口324、流重连接和去活接口326、关闭连接接口328和超时接口330。LBM块308和CMM块332之间提供的优胜信元接口342用于发送优胜信元的相关信息。此外，还提供了时钟管理块344和具有一个处理器接口350的处理器接口模块346。

考虑到上述各种结构块，LBM块308的总体功能包括以下各项：

流激活：当信元到达或与其FID相关的信元缓冲器以前是空的时，QCM发送流激活消息给LBM。该接口包含了与流相关的上下文存储器中发现的信息。

优胜流和流重连接/去活：当PQM选择某个流作为优胜者时，将该流从它所属的不同堆中删除(例如根据聚合层)。如果特定流的信元缓冲中还有剩余的信元，那么LBM重新计算TS值，在PQ数据结构中重新连接该流。如果没有剩余的信元，LBM计算该流的TS值，将其存储在漏桶中，直至该流的另一信元到达。

关闭连接：如果CAC抑制某个流，信元缓冲器会清除，FID可以重用于其它连接。为了防止将旧的参数用于新连接，必须通知LBM该流已不再有效。

超时：检查漏桶存储器，最好定期检查，以防止存储过期时间。

图4的流程图描述了按照本发明的内容在ATM设备中实现GFR业务的示例性方法中用到的各种操作。在信元到达时(框402)，GFR监管机制执行业务量监管，使得符合条件的信元正确地进入保证流队列(框402)。在一种实现中，监管器可以利用CLP比特，在不符合情况下标记信元；之后，信元可以在具有一个阈值GFR_TH的缓冲器中排队。此时，可以采用适当的信元丢弃机制，这在分层调度器体系结构申请中详细描述。

实际上，GFR流的整形使得两个独立子流得以实现，其中一个流生成利用了具有业务量描述符参数峰值信元速率(PCR)和信元时延变化容忍度(CDVT)的GCRA处理，另一个流生成利用了称为帧GCRA或F-GCRA的处理，除了PCR和CDVT参数之外，它还有最大信元速率(MCR)和最大突发大小(MBS)参数。在确定了帧的开始是保证的(也就是保证业务帧开始)，利用GCRA处理，调整包括该帧的保证流队列的信元，以保证速率传输(框404)。如其他地方提到，保证速率可以按照采用的业务量合同预先确定。在保证业务帧调整结束时(也就是调度该帧的最后一个信元)，利用F-GCRA处理，确定下一保证业务帧的未来时间戳(TS_GF)(框406)。将TS_GF插入与保证业务子流相关联的适当的PQ缓冲器中。另一时间戳，记为TS_NGF，也利用LBM中的GCRA处理确定，用于调度来自保证流队列的信元，以非保证速率进行传输(框408)。将TS_NGF插入PQ缓冲器，后者可用于非保证业务速率，例如最佳可用业务或UBR业务。

从调度的保证模式(也就是GFR模式)到非保证模式(也就是“GFR-”模式，可以基于UBR)的切换基于两个未来时间戳，也就是前面提出的计算得到的TS_GF和TS_NGF值。做出决定来验证TS_NGF值是否小于TS_GF值；换句话说，TS_NGF是否早于TS_GF发生。如果是，将该流切换到非保证模式，也就是调度来自队列的信元，以非保证速率发送(框410)，其中GCRA处理整形UBR/BE业务量流。当TS_GF时间到时，流模式切换回GFR模式，其中调度下一保证业务帧的信元，以预定保证速率发送(412)。此外，如果在切换到GFR模式时，通过UBR模式调度了任何未完成帧的信元，这些为完成帧被丢弃。

现在参看图5，该图给出了实现本发明GFR业务的示例性系统500。前面间接提到，提供了GFR监管块502，利用基于CLP的标记，确保遵从业务量合同。采用具有适当阈值的保证流队列504，将入标记信元压入队列。算法处理机制506形成了上述LBM块的一部分，它计算在GFR和UBR模式之间切换所需的两种类型时间戳。很明显，算法处理机制506的功能可以通过硬件、软件或者两者的任意组合实现。标号508A代表了用于发送GFR信元的与GFR调度模式相关联的PQ结构(也就是堆)，前述GFR信元可以认为是从涉及保证业务帧的子流队列510A发送。同样，标号508B代表了用于发送UBR/BE信元的与非保证速率模式相关联的PQ结构，前述UBR/BE信元可以认为是从子流队列510B发送。前面解释过，算法处理器块506在保证业务帧结束时，基于GCRA和F-GCRA处理计算未来时间戳，根据TS值在保证和非保证模式之间切换。

图6是GFR监管方案的一种图形表示，该方案可以针对本发明实现。GRF监管方案包括两个阶段，这两个阶段都涉及漏桶实现。第一阶段是确定分组(或帧)是否符合条件。这通过测试以下条件来完成：(i)信元到达与具有PCR和CDVT描述符的可用GCRA功能一致；(ii)帧中的所有信元具有相同CLP值；以及(iii)帧大小没有超过MFS值。标号602代表了GCRA处理所检查的信元流部分。第二阶段(也是漏桶实现)工作在帧级，利用具有适当业务量描述符参数的F-GCRA处理。标号604代表了F-GCRA处理所检查的信元流部分。应当理解，执行GFR监管的最终结果是区分MCR保证发送的符合条件帧和可以考虑采用UBR/BE类型业务的不符合条件帧。图7的流程图描述了GFR监管方法的附加细节。在t_a信元到达时(框702)，判断该信元是否是帧的第一信元(框704)。如果是，执行涉及漏桶参数的特定计算和比较，如框706和708所示，其中X表示了漏桶计数器的值，LPT是最后通过时间，X’是辅助变量。如果X’大于L或者信元设置了它的CLP(也就是CLP＝1)，那么该帧就被认为是不符合条件。因此，或者实现可用最佳调度或者实现适当的丢弃策略(框710)。否则，该帧被认为是符合条件的，按照框712所示那样计算桶计数器和LPT参数。这样，以保证速率调度符合条件的帧(框714)。

如果信元不是该帧的第一信元，则作出另一判断，确定该信元是否属于一个符合条件的帧(判断框716)。如果是，框720中计算特定LB参数，其中LPT设置成等于t_a。之后，对符合条件帧实施保证速率调度(框722)。另一方面，如果该信元不属于保证帧，则实现可用最佳调度或者实现适当的丢弃策略(框718)。

本领域技术人员应认识到，利用前面针对GFR实现提出的算法处理计算LB参数(TS、TAT等)的问题之一，是表示参数和系统时钟的可用字大小是有限的。因此，一旦LB计算中采用的所有计数器和时钟到达其各自的限度，它们翻转回0。当然，这种限制并不局限于GRF业务；任何涉及基于LB的计算的CoS实现都存在相同问题。因为这种硬件限制，在执行LB参数更新之后，可能会出现潜在问题，连接的流队列变成空。一种方案是存储更新结果并将它们与空的流队列关联起来。之后，当流再次变得活跃，并且流的第一信元到达时，可以使用存储的LB数据。但是，没有机制能够指示该时钟是否已翻转，从而存储的值已不再有效(因为它们已经“失效”)。这样，需要某种改进来跟踪和维护参数数据，而不会有失效的风险。此外，希望有类似于后台进程的方案，尽量减小对吞吐量的影响。

本发明有利地提供了一种方案，它解决了前面讨论中提出的问题。实际上，算法处理用于确定各种CoS实现中涉及的LB参数的超时条件。在检测到超时条件时，新的值被替代，再次活跃的流可以在适当的时候参与调度。图8的流程图描述了按照本发明的内容的超时处理中用到的操作。时间更新处理802最好作为后台进程实现。前面间接提到过，基于业务类别计算LB参数；因此，针对涉及的CoS做出判断(框804)。对CBR/UBR类型，检查TAT1(单桶TAT)和TS(框806A)。对VBR业务，检查TAT1、TAT2(双桶TAT值)和TS。同样，对GFR/UBT+业务，除了TAT1和TAT2值之外，还检查两个时间戳(TS＝TS_NGF和tf/TS+＝TS_GF)(框806C)。然后，判断这些值中是否有过期值(判断框808)。如果没有，处理就继续，进入循环(框822)。判断框810判断PQ树中是否存储了任何过期时间值。如果是，针对组播连接作出另一判断(判断框812)。如果时间值与组播连接相关，LBM和PQM之间的过期接口(图3中示出)用于删除过期树，插入新的时间值。新值也提供给LBM。这些操作固定为框814。如果连接不是组播，LBM和QCM之间的超时接口用于清除信元缓冲器。之后，利用过期接口，从树中删除流。然后，在LBM中将FC参数设置成0。框816在流程图中合并了这些操作。如果PQ树中没有存储过期时间值(判断框810)，只向LBM提供新值；没有过期或超时接口可用于删除或清除(框820)。

图9给出了按照本发明的内容，验证时间相关参数值过期的多段定时窗口900。定时窗口900由预定时长的4个段902A-D组成，形成了两棵树904A和904B，每一颗由两段组成。过期验证在窗口900中执行两次；一次在第一段902A中，用于验证第二树904 B中使用的时间是否过期，第二次是在第三段902C中，用于验证第一树904A中使用的时间是否过期。当实际时间到达了适当时间段的预定值时，开始检查。如果PQM允许过期处理(也就是说，处理有足够时间来处理过期命令)，那么在每个信元时段，过期块检查与一个流相关的定时参数。前面可以看出，根据CoS的不同，需要检查多达4个时间值。当时间值的最重要比特(MSB)不同于实际时间的MSB时，该时间值被认为是过期的。此外，如果检查到与连接相关的一个时间值已经过期，那么该连接被认为是过期的。之后，象前面描述的那样，提供适当的处理来更新新的时间值。

基于前面的讨论，应当理解，本发明提供了一种在ATM环境中实现GFR业务的创新方案，该方案有效地克服了当前GFR实现的缺陷和不足，前述ATM环境可以是接入节点中的交换设备，也可以是区域范围内的传输网。通过将信元流的保证和非保证部分处理成两个不同的子流，具有相关的业务量整形规则，不仅能使总体存储器需求达到减小，而且还改进了吞吐量。另外，本领域技术人员很容易理解，尽管针对接入节点的ATM交换设备的分层调度器提出了本发明的组播方案，但这里包含的技术并不局限于该环境；它们也可以在其它ATM应用中实现。

通过前面的详细描述，相信本发明的操作和构造已经很清楚。示出和描述的本发明实施方式是示例性的，应当理解在不偏离后附权利要求书所提出的本发明范围的前提下，可以作出各种变化和改进。