在ATM交换系统中生成并传输串列分组的方法

摘要

本发明的实施例涉及生成一组数据(比如，分组)。这组数据包含来自第一队列和第二队列的信元。第一队列中的所有信元均相互独立。第二队列中至少有两个信元相互关联。

说明书

技术领域

本发明主要涉及通信学和/或电子学。

背景技术

通信是一个在日常生活中影响着很多人的日益发展的技术领域。通信的实例有电话系统、无线蜂窝电话系统、互联网、广播、电视和许多其他服务。所有这些示例性通信系统从一个地方向另一个地方传输信息(即数据)。通常，需要用到大量的设备来在异地间传输信息。这些设备有移动电话、移动电话无线发射塔和有线电话设备。

遗憾的是，许多用于通信的设备只有有限的信息传输容量。例如，铜线(或光缆)仅能传输给定数量的电话通话。然而，如果通信系统中的设备能更有效地运行，则对于给定的铜线(或光缆)就能够传输更多的电话通话。因此，对通信系统中设备的长远要求是使其更有效地运行来增加通信系统的通信容量。

发明内容

本发明的一个目标是至少消除现有技术中的局限。本发明的实施例涉及到生成一组数据(比如，分组)。这组数据可以包括来自第一队列和第二队列的信元。第一队列中的所有信元各自独立。第二队列中的至少两个信元相互关联。

一些通信系统包括交换机。交换机可用于从一个位置向另一个位置路由数据。在交换机中，需要把将要到达同一位置的数据进行打包，这样交换机就能有效运行。此外，有时信息需要被分割成小的部分，这样通信系统就可以适当地处理传输的信息。因此，当信息被分割为小的部分时，这样的信息(即信元)是相互关联的。因为关联的信息有相同的目的地，所以可以一起进行交换。通过同时交换关联信息，交换机可以有效地运行。然而，有时不存在足够多的关联信息来利用交换机的全部交换容量。因此，在本发明的实施例中，独立于关联信息的信息与关联信息一起被传输。在一些情况下，独立信息和关联信息有相同的目的地。此外，由于交换机的交换容量可以提高，所以这些

实施例是很有利的。

本发明的其它优点、目的和特征有一部分将在以下的说明书中进行阐述，有一部分则对于本领域的技术人员经过对以下内容的检验后会变得明了，或者通过本发明的实践而体验到。所附的权利要求书具体指出了本发明的目的和优点。

附图说明

图1显示的是采用SPTP方法的ATM交换系统的示意性结构图；

图2显示的是采用包含5级的SPTP方法的ATM交换系统的示意性结构图；

图3到图5显示的是生成L0和L1串列分组的方法的示意性流程图；

图6显示的是用于组合多播(multicast)业务的交换机中的路由过程的示意图；

图7显示的是用于普通多播业务的交换机中的路由过程的示意图；

图8(8a，8b)和图9(9a，9b)显示的是在ATM交换系统中生成串列分组的方法的示意性流程图；

图10显示的是用于组合多播业务的交换机中的路由过程的示意图；

图11显示的是用于普通多播业务的交换机中的路由过程的示意图。

具体实施方式

庞大的用户应用程序已经被开发出来以适应互联网的发展。交换机的交换容量已有所增加以支持这些用户应用程序。因为交换机端口已经提高了带宽并且单位交换机可以有很大的交换容量，所以硬件瓶颈效应(如存储器访问时间和/或交换处理时间)制约着交换机的有效性和/或效率。

在实施例中，顺序-并列串列分组(train packet)(SPTP)方法使得交换机更高效。SPTP方法可以对多个信元进行组合和交换，以降低交换机的交换处理频率。ATM交换系统可以采用SPTP方法来同时使用顺序串列分组技术(用于对多个信元进行组合和交换以降低交换处理频率)和位片(bit-slicing)技术(用于提高交换数据率)。

图1显示的是采用SPTP方法的ATM交换系统的示意性结构图。顺序-并列分组(SPP)映射器110和串列格式器120分别置于N交换平面140之前。映射器110和格式器120可用于组合多个具有相同交换平面路由标记的输入信元，以生成单个串列分组。通过SPP映射器110和串列格式器120生成的串列分组可以经切分单元130分为N个子串列分组。N个子串列分组可以输入到交换平面140中。在实施例中，当假定一个串列分组由M个信元组成，每个子串列分组可以包含M/N个信元。N个交换平面140按同步操作的位片方法运行。具有相同路由标记的N个子串列分组可以相同的相位输出到相同的交换平面目的端口。被输出到相同交换平面目的端口的N个子串列分组可以输入到位于交换平面140之后的合并单元150中。合并单元150可以组合来自N个交换平面140的子串列分组，以构成初始串列分组。串列解格式器160将串列分组分割为初始信元，并可以将这些信元输出到目的地端口。

在实施例中，当对单播(unicast)业务或广播业务进行交换时，可以通过对出口解格式器和交换平面目的地端口进行分类来管理单播业务队列和广播业务队列。如果根据调度选择了单播业务队列或广播业务队列，则从相应的队列中读取M个信元以生成串列分组并且对其进行交换。当对多播业务进行交换时，可以根据交换平面140目的地端口的属性来管理多播队列。当多播信元的目的地端口具有单个交换平面目的地端口时，就不需要在交换平面140中复制多播信元。在实施例中，多播信元可以被归为组合多播业务，并且被排列在按各个交换平面目的地端口管理的队列中。当多播信元的目的地端口包含多个交换平面目的地端口时，需要在交换平面140中复制多播信元。多播信元可以被归为普通多播业务，并存储在一个队列中。

当被归为组合组合多播通信多播业务的多播单元信元被排列在按各个交换平面终点目的地端口管理的队列中时，就可从该队列中读取出具有相同交换平面目的地端口的M个多播信元来生成串列分组，随后对该串列分组进行交换。交换平面140可以按与单播业务或广播业务类似的方式来执行交换功能。合并单元150和串列解格式器160可以复制多播信元并将其输出到目的地端口。

当被归为普通多播业务的多播信元被存储在一个队列中时，各交换平面140就复制子串列分组。合并单元150和串列解格式器160复制多播信元并将其输出到目的地端口。在组合多播业务和/或普通多播业务的情况下，当排列在队列中的信元数目小于M时，可以通过填补空信元(dummy cell)来生成包含有M个信元的串列分组。所填补的信元可以在合并单元150和串列解格式器160中删除。当排列在队列中的信元数目小于M时，可以通过填补与不足的信元数目一致的空闲信元来生成包含有M个信元的串列分组。因此，当多播业务很小时，交换处理率将显著降低。

图2显示的是采用了包含5级的SPTP方法的ATM交换系统的示意性结构图。入口插入器210(0级交换机)可以作为SPP格式器和/或串列格式器。1级交换机(XeC(1)_^*)220可以作为切分单元。交换平面(XeC(2)_^*)230(2级交换机)可以作为采用位片方法运行的交换平面。3级交换机(XeC(3)_^*)240可以作为合并单元。出口插入器250(4级交换机)可以作为串列解格式器。符号^*表示通配符。

入口插入器210(0级交换机，网络处理器NpS有最多4个线路卡与其连接)将多个具有相同交换平面路由标记的输入信元组合起来，并/或生成一个串列分组。通过1级交换机(XeC(1)_^*)220，串列分组被分割为N个子串列分组。子串列分组(可以是由1级交换机220分割的)可以输入到交换平面(XeC(2)_^*)230中。交换平面230(从1级交换机中接收子串列分组)以相同的相位向同一交换平面目的地端口输出N个具有相同路由标记的子串列分组。从交换平面230输出的子串列分组在3级交换机(XeC(3)_^*)240中合并，并生成初始串列分组。出口插入器250将串列分组分割为初始信元。出口插入器250可以将这些信元输出到相应的目的地端口。

为了管理队列，可以根据目的地端口数目及其特性，将输入到采用了5级SPTP方法的ATM交换系统的信元划分为：单播业务、组合多播业务、普通多播业务和广播业务。存储在队列中的信元可以格式化为两级串列分组(如，L0串列分组和L1串列分组)，并且可以对串列分组进行交换。

根据信元的目的地端口特性，入口插入器210可以将信元存储在单播队列(如，64个队列；64个出口插入器)，组合多播队列(如，8个队列；8个交换平面目的地端口)，普通多播队列(如，1个队列)和广播队列(如，1个队列)中。根据L0串列分组生成算法，入口插入器210可以利用存储在队列中的信元来生成L0串列分组。一个L0串列分组可以包含两个信元。

图3显示的是用于按单播业务来生成L0和L1串列分组的方法的示意性流程图。图4显示的是按组合多播业务来生成L0和L1串列分组的方法的示意性流程图。图5显示的是按普通多播业务来生成L0和L1串列分组的方法的示意性流程图。

如示意图3所示，是否生成了所有的K个L0串列分组(K表示交换平面数目，例如，包含在L1串列分组中的L0串列分组的数目)，可以按循环方法，从按交换平面目的地端口分类的单播组中选择一个单播组来得以确认(S101-S105)。当由所选择的单播组生成了K个L0串列分组时，可以结束L0和L1串列分组的生成过程。通过利用K个L0串列分组可以生成一个L1串列分组。作为S105的确认结果，如果K个L0串列分组没有全部生成，就可以确认在所选的单播组中是否存在待处理的单播队列(S106)。如果存在待处理的单播队列，则可以确认生成的L0串列分组的数目是否达到了K，并且当L0串列分组的数目没有达到K时，检查单播队列的状态(S107-S109)。如果队列非空，且存储的信元数目大于2，就可以利用两个信元生成一个L0串列分组(S111)。当存储的信元数目不大于2(即，仅存储了一个信元)，就可以通过从队列中读取一个分组和/或利用一个空信元来生成一个L0串列分组(S112)。在所选队列为空的情况下，可以利用两个空信元来生成一个L0串列分组(S114)。可以确认L0串列分组的数目是否达到K。重复这一过程直到生成K个L0串列分组。

K个L0串列分组(K表示交换平面数目，例如，包含在L1串列分组中的L0串列分组的数目)是否全部生成，可以按循环方法，选择一个组合多播队列来确认(S121-S125)。如果由所选的组合多播队列生成了K个L0串列分组，则结束L0和L1串列分组的生成过程。当没有全部生成K个L0串列分组时，检查组合多播队列的状态(S126)。当所选队列非空时，如果存在于该队列前端(HOL)的信元的报头的B比特信息(例如，用以表示队列的后续信元属于同一虚连接的比特)为“0”，则表示由与HOL信元相同的虚连接生成了后续信元。因此，从队列中读取两个信元来生成一个L0串列分组(S127和S128)。如果B比特为“1”，则表示由不同于HOL信元的虚连接生成了队列的后续信元，并且从该队列中只能读取HOL信元。从而，可以利用一个HOL信元和一个空信元来生成一个包含有两个信元的L0串列分组。当组合多播队列为空时，可以利用两个空信元来生成一个L0串列分组(S130)。重复这一过程直到生成K个L0串列分组(S131)。

如图5所示，可以通过查找单个普通多播队列来确认是否K个L0字节分组(K表示交换平面数目，例如，包含在L1串列分组中的L0串列分组的数目)已经全部生成(S141-S144)。当由普通多播队列生成了K个L0串列分组时，生成L0和L1串列分组的过程就可以结束。当K个L0串列分组没有全部生成时，检查普通多播队列的状态(S145)。当所选队列非空时，如果存在于队列前端(HOL)的信元的报头的B比特信息为“0”，则表示由同于HOL信元的虚连接生成了后续信元(S146)。因此，从队列中读取两个信元来生成一个L0串列分组(S147)。如果B比特为“1”，则表示由不同于HOL信元的虚连接生成了队列的后续信元，并且从该队列中只能读取HOL信元(S148)。从而，可以利用一个HOL信元和一个空信元来生成一个包含有两个信元的L0串列分组。当普通多播队列为空时，可以利用两个空信元来生成一个L0串列分组(S149)。重复这一过程直到生成K个L0串列分组。

为了生成普通多播业务的L1串列分组，当确定了2级交换机(交换平面)的2级路由标记(S2RT)时，可以对K个L0串列分组的S2RT进行逻辑“或”来生成新的S2RT。所生成的S2RT被更新和/或存储在K个L0串列分组的报头的S2RT字段中，来调整交换平面的L1串列分组同步。从入口插入器210接收L1串列分组的1级交换机(XeC(1)_^*)220将L1串列分组切割为K个子串列分组(K表示交换平面的数目，例如，包含在L1串列分组中的L0串列分组的数目)。1级交换机(XeC(1)_^*)220向交换平面(XeC(2)_^*)230并行传输K个子串列分组。交换平面(XeC(2)_^*)230可以相同的相位向3级交换机(XeC(3)_^*)240传输子串列分组。3级交换机(XeC(3)_^*)240利用K个子串列分组来生成一个初始L1串列分组。3级交换机(XeC(3)_^*)240把L0串列分组交换到L0串列分组的出口插入器250。出口插入器250向连接于L0串列分组的信元目的地端口的线路卡传输信元。

图6显示的是利用包含5级SPTP方法的ATM交换系统进行组合多播业务交换的实例。在该实例中，在K个L0串列分组(图6中使用的是8个交换平面，则K＝8)中包含有效用户信元(非空信元)的L0串列分组可以由组合多播业务中生成。L0串列分组报头的B比特可以全部置“1”。因此，包含用户信元的四个L0串列分组具有一个有效信元。包含在L1串列分组中的四个信元可以组成伪L0串列分组。因此，在最多交换16个信元(8个L0串列分组×2个信元(或L0串列分组))的ATM交换系统中，仅仅可以交换4个信元。L0串列分组从3级交换机(XeC(3)_^*)240复制到出口插入器250。在组合多播业务的L0和L1串列分组中，在交换平面中使用的S2RT是相同的。然而，在3级交换机中使用的3级路由标记(S3RT)是不同的。

图7显示的是进行普通多播业务交换的实例。在该实例中，在K个L0串列分组(图7中使用的是8个交换平面，则K＝8)中包含有效用户信元的4个L0串列分组(非空信元)可以从普通多播业务中生成。L0串列分组报头的B比特可以全部置“1”。因此，包含用户信元的四个L0串列分组拥有一个有效信元。其余四个包含L1串列分组的信元可以包含伪L0串列分组。在最大交换16个信元(8个L0串列分组×2个信元(或L0串列分组))的ATM交换系统中，可以交换4个信元。L0串列分组从3级交换机(XeC(3)_^*)240复制到出口插入器250。在普通多播业务的L0和L1串列分组中，在交换平面中使用的S2RT是相同的(通过对K个L0串列分组的S2RT进行“或”操作新生成的S2RT)。然而，在3级交换机中使用的3级路由标记S3RT是不同的。

由于采用了5级SPTP方法的ATM交换系统中交换的有效性，可以利用两个信元生成L0串列分组。在多播业务(组合多播业务或普通多播业务)中，当信元不属于相同的连接ID时，从队列中读取出一个信元并利用一个空信元生成一个L0串列分组。当不能生成K个L0串列分组(K表示交换平面数目)时，通过填补伪L0串列分组来生成L1串列分组。

连续向交换机输入具有相同连接ID的多播信元的可能性很小。可能不会在每个L1串列分组生成周期中在所有多播队列中存储足够的多播信元(K)。不可避免的要使用空信元或伪L0串列分组。空信元常用于在采用了5级SPTP方法的ATM交换系统中生成L0串列分组或L1串列分组，从而降低交换处理率。

本发明的实施例涉及采用了生成串列分组方法的ATM交换系统，该系统类似于图2所示的包含5级SPTP方法的ATM交换系统的示意结构。一个L0串列分组最多由两个有效信元组成。这两个信元具有相同的路由标记S2RT和S3RT。一个L0串列分组可以由两个空信元，一个空信元与一个用户信元，或两个用户信元组成。当L0串列分组包括两个空信元或一个空信元时，可用单播队列来生成有效L0串列分组。

图8显示的是当组合多播队列被选定为服务队列时生成串列分组的方法的示意性流程图。图9显示的是当普通多播队列被选定为服务队列时生成串列分组的方法的示意性流程图。

如图8(8a，8b)所示，在多种队列(单播/多播业务，组合多播业务，普通多播业务，和广播业务)中选择一种特定的队列作为服务队列，这些队列是根据通过主调度器输入的信元的目的地端口数目及其特性来分类的(S200)。从队列中读取分组(或信元)来生成L0/L1串列分组。该过程包括为各个队列进行的循环调度。每个队列可根据其优先级划分为队列组。为每个队列选择服务之前，可以为队列组分配优先级。

可以确认所选服务队列是否为组合多播队列(S202)。当选择组合多播队列作为服务队列时，表示L0串列分组当前数目的参数(i)被置“0”(S204)。确认相应的队列是否为空(S205)。当相应队列为非空时，从组合多播队列中读取出一个新的前端(HOL)多播信元(S206)。

确认在S206中读取的组合多播信元的B比特值是否被置“0”(S208)。当B比特值为“0”时，表示可认为所读取的多播信元和后续信元属于相同的连接，并且具有相同的路由标记(如，相同的S2RT，S3RT和S4RT)。当B比特值为“1”时，表示这两个信元具有不同的S3RT和S4RT。

作为S208的确认结果，当在S206中读取的组合多播信元的B比特值被置“1”时(如，后续信元具有不同的S3RT和S4RT)，两个信元不能组成一个L0串列分组。可以利用从组合多播队列中读取出的HOL信元的S2RT和S3RT检测出用于输出该组合多播信元的扇出端口(fan-out port)，其中的组合多播队列是在S200中选择的。从相应的单播队列中可以用循环方法选择出一个单播队列。从所选的单播队列中读取出一个单播信元(S210和S212)。

如图10所示，当从组合多播队列中读取出的组合多播信元的S2RT向01000000(Xe(3，6))输出，而S3RT向与01000001(Xe(3，6))连接的8个XeI中的XeI(4，0)和XeI(4，6)输出时，对应于出口插入器的、用于输出组合多播信元的单播队列是#48和#54。按循环方法可以由此选择出一个单播队列。从单播队列中读取出一个单播信元。可以用S206中读取出的组合多播信元生成一个有效L0串列分组。在S212(S214)中读取出单播信元。表示L0串列分组数目的参数(i)增加1(S216)。

与S214中生成的L0串列分组相同，当L0串列分组包含一个单播信元时，S2RT、S3RT和S4RT可以存储于一个交换路由字段中，该字段存储于L0串列分组的报头中。指定S2RT和S3RT使其与构成L0串列分组的组合多播信元的S2RT和S3RT相同。利用包含于L0串列分组中的单播信元的信元报头中存储的信元路由标记，可以指定S4RT。判定S216中增加的参数(i)与交换平面数目(K)是否相同(S218)。作为S218的结果，当参数(i)与交换平面数目(K)不同时，确认S200中所选择的组合多播队列是否为空(S220)。作为S220的确认结果，当组合多播队列非空时，流程回转到S206。从S200所选的组合多播队列中读取新的HOL多播信元，并利用来自单播队列的单播信元来生成串列分组的过程重复执行，直到不存在组合多播信元为止。确认L0串列分组的数目是否与交换平面的数目一致。

当组合多播队列被清空时，相应的多播队列就为空。从而，所选的多播队列就存储少于交换平面数目的信元。作为S220的判定结果，当所选组合多播队列为空时，确认在所生成的L0串列分组中是否存在有效的组合多播信元。当不存在组合多播信元时，生成L0串列分组(包括两个空信元)(S205a)。作为S205的确认结果，当相应队列为空时，生成包含两个空信元的L0串列分组。当包含两个空信元的L0串列分组的生成过程结束时，流程转到S206来为后续队列生成串列分组。当L0串列分组中存在有效组合多播信元时，确认与L0串列分组中包含的有效组合多播信元相对应的任何单播信元队中是否存储了有效单播信元(S222)。作为S222的确认结果，当没有存储有效单播信元时，流程转到S205a。作为S222的确认结果，当与L0串列分组中包含的有效组合多播信元相对应的任何单播信元队中存储了有效单播信元时，按循环方法从多个单播队列中选择单播队列。多个单播队列响应于最后的出口插入器250，依据从所选组合多播队列中读取的组合多播信元的S2RT和S3RT，输出组合多播信元(S223)。可以判定在所选的单播队列中是否存在两个有效的多播信元(S224)。

作为S223的判定结果，可以利用一个单播信元和一个空信元来生成一个L0串列分组。流程持续到S216(S227)。作为S224的判定结果，可以从两个所选的单播队列中读取单播信元(S225)。可以利用两个单播信元生成一个L0串列分组(S226)。流程在S226和S227后转到S216，使指示L0串列分组数目的参数(i)加1。

示意图10显示的是当从组合多播队列中读取的多播信元的S2RT为01000000并且S3RT为01000001(第一信元的S3RT)，00000010(第二信元的S3RT)，10000100(第三信元的S3RT)和00101000(第四信元的S3RT)时，如果生成一个仅由单播信元组成的L0串列分组来跟随最后一个信元(第四信元)，则对应于用于输出第四组合多播信元的出口插入器的单播队列为#50和#52。从而，按循环方法选择出两个单播队列。分别从这两个单播队列中读取出一个单播信元。可用在S224中读取出来的两个有效信元生成一个L0串列分组(S226)。流程回转到S216使指示L0串列分组数目的参数(i)加1。

当在与S200中选出的组合多播队列属于相同的组的8个单播队列中不存在信元时，可以利用两个空信元来生成一个L0串列分组。指示L0串列分注数目的参数(i)增加1。如图11所示，例如，当#48、#49、#50、#51、#53、#54和#55单播队列中不存在构成L0串列分组的单播信元时，可以利用两个空信元来生成4个L0串列分组。因此，可以生成8个L0串列分组。利用一个多播信元、一个单播信元和一个空信元可以生成一个L1串列分组。

当S208中读取出来的组合多播信元的B比特值被置“0”时，(比如，后续信元具有相同的S3RT和S4RT)，可以从所选的组合多播队列中读取出一个组合多播信元(S228)。利用S206中读取的一个组合多播信元可以生成一个L0串列分组。流程回转到S216，使指示L0串列分组数目的参数(i)加1。通过步骤S202和S230示意的过程，组合多播业务可以在入口插入器包括K个有效L0串列分组。在一个L1串列分组中可以包括K个L0串列分组。

在图10中示意说明了L1串列分组的交换操作。在入口插入器中生成的L1串列分组输出到1级交换机220。1级交换机220将L1串列分组分割为子串列分组，并将其传送到交换平面230。利用L0串列分组报头的S2RT，交换平面230将子串列分组传送到3级交换机240。

利用L0串列分组报头的S3RT，3级交换机240为相应的出口插入器250复制L0串列分组。出口插入器250将L0串列分组分割为两个信元。利用通过信元报头从交换终端传输来的连接ID，执行多播表查询操作，从而在相应的端口中复制组合多播信元。利用L0串列分组报头的S4RT，把单播信元传输到相应的端口。组合多播信元在每个交换机中保持着不同的路由标记。单播信元可以将到出口插入器的路由标记存储于L0串列分组报头中。当一个组合多播信元和一个单播信元组成一个L1串列分组时，单播信元可以将S2RT转化为与组合多播信元的S2RT一致，以和组合多播信元一起到达3级交换机。单播信元可以将S3RT转换为与组合多播信元的S3RT一致，以和组合多播信元一起到达出口插入器。因此，根据交换操作，被复制的组合多播信元和单播信元可以被传输到最终目的地端口。

图9和图11显示的实例涉及包括用于生成和传输普通多播队列的串列分组方法的实施例。如图9所示，选择一个服务队列。当服务队列为普通多播队列时，执行步骤S231和S232。作为S232的判定结果，当普通多播队列被选为服务队列，指示L0串列分组数目的参数(i)被置“0”(S234)。确认所选队列是否为空(S235)。当所选队列非空时，从普通多播队列中读取一个新的HOL多播信元(S236)。确认S236中读取的普通多播信元的B比特值是否被置“0”(比如，是否后续信元有相同的S2RT、S3RT和S4RT)(S238)。

作为S238的确认结果，当S236中读取的普通多播信元的B比特值不是“0”时，(比如，后续信元有不同的S2RT、S3RT和S4RT)，按循环方法从多个单播队列中选出一个单播队列。利用从S231中所选的普通多播队列中读取的普通单播信元的S2RT和S3RT，多个单播队列可响应用于输出普通多播信元的出口插入器。从所选的单播队列中读取出一个单播信元(S240和S242)。

示意图11显示的是，当从S231所选的普通多播队列中读取的普通多播信元的S3RT为00000000 10001000 00000000 0000000000000000 00000000 00000000 01000011时，与输出普通多播信元的出口插入器相对应的单播队列为#0、#1、#6、#51和#55。按循环方法从中选出一个单播队列。从单播队列中读取出一个单播信元。利用一个S236中读取的普通多播信元和一个S242中读取的单播信元可以生成一个L0串列分组(S244)。指示L0串列分组数目的参数(i)增加1。

类似于S244中生成的L0串列分组，当一个L0串列分组包含一个单播信元时，就必须更新交换路由字段中的S2RT、S3RT和S4RT，其中交换路由字段存储在L0串列分组的报头中。S2RT和S3RT被指定为等同于与单播信元一起构成L0串列分组的普通多播信元的S2RT和S3RT。利用存储于单播信元的信元报头中的信元路由标记来指定S4RT。判定在S246中增加的参数(i)是否等于交换平面数目(K)(S248)。作为S248的判定结果，当参数(i)不等于交换平面数目(K)时，确认所选普通多播队列是否为空(S250)。作为S250的确认结果，当S231中选择的普通多播队列非空时，流程回到S236，从所选普通多播队列中读取一个新HOL多播信元。

作为S250的确认结果，当在S200中所选的普通多播队列为空时，确认在所生成的L0串列分组中是否存在有效的普通多播信元(S252)。当不存在这样的有效普通多播信元时，生成包含两个空信元的L0串列分组(S235a)。作为S252的确认结果，当对应队列为空时，生成包含两个空信元的L0串列分组(S235a)。当生成了包含两个空信元的L0串列分组时，流程转到S246，为后续队列生成串列分组。当在L0串列分组中存在有效普通多播信元时，确认在与L0串列分组中包含的有效普通多播信元相对应的任一单播队列中是否存储了有效的多播信元(S253)。作为S253的确认结果，当没有存储有效单播队列时，流程转到S235a。

作为S253的确认结果，当在与L0串列分组中包含的有效普通多播信元相对应的任一单播队列中存储了有效的多播信元时，按循环方法从对应于最终出口插入器250的多个单播队列中选择一个单播队列，以便按照从所选普通多播信元中读取的普通多播信元的S2RT和S3RT来输出普通多播信元(S253)。判定所选单播队列中是否存在有效多播信元(S254)。

作为S254的判定结果，当不存在两个有效多播信元时，利用一个单播信元和一个空信元来生成一个L0串列分组，并且流程转到S246(S259)。作为S254的判定结果，当存在两个有效多播信元时，从两个所选单播队列中读取出单播信元(S257)。利用两个单播信元生成一个L0串列分组(S258)。流程在S258和S259后转到S246，使指示L0串列分组数目的参数(i)加1。

如示意图9(9a，9b)所示，当从普通多播队列中读取的普通多播信元的S3RT为00000000 10001000 00000000 00000000 0000000000000000 00000000 01000011(第一信元的S3RT)，10010000 0000000000000000 00000000 00000000 00000000 00011100 00000000(第二信元的S3RT)，00101000 00000000 00000000 00000000 00000000 0100001100000000 00000000(第三信元的S3RT)和00000000 00000000 0100100100000000 11100011 00000000 00000000 00000000(第四信元的S3RT)时，如果生成一个仅由单播信元构成的L0串列分组来跟随最后一个信元(第四信元)，则对应于用于输出第四普通多播信元的出口插入器的单播队列为#24、#25、#29、#30、#31、#40、#43和#46。按循环方法从中选出两个单播队列。分别从这两个单播队列中读取出一个单播信元。用S256中读取出来的两个单播信元来生成一个L0串列分组(S258)。流程转到S246，使指示L0串列分组数目的参数(i)加1。

作为S238的确认结果，当S231中读取的普通多播信元的B比特值被置“0”时，(比如，后续信元具有相同的S2RT和S3RT)，从所选普通多播队列中读取一个普通多播信元(S260)。利用S236中读取的普通多播信元来生成L0串列分组。在S260中读取普通多播信元(S262)。流程转到S246，使指示L0串列分组数目的参数(i)加1。通过S232到S262的示例性处理，一个普通多播业务包括入口插入器中的K个有效L0串列分组。K个L0串列分组组成一个L1串列分组。如图11所示，在入口插入器中生成的一个L1串列分组被输入1级交换机220。

如图11所示，1级交换机220将L1串列分组分割为子串列分组。1级交换机220将其传输到交换平面230。利用L0串列分组报头的S2RT，交换平面230将子串列分组复制到3级交换机240中。利用L0串列分组报头的S3RT，3级交换机240将子串列分组复制到相应的出口插入器250中。出口插入器250将L0串列分组分割为两个子信元。通过由信元报头从交换终端传输来的连接ID，执行多播表查询操作，从而在相应的端口中复制普通多播信元。利用L0串列分组报头的S4RT可以把单播信元传输到相应的端口。因此，根据交换操作，复制的普通多播信元和单播信元可以传输到最终目的地端口(如，线路卡)。

当确定多播队列(组合多播队列或普通多播队列)要用于信元时隙时，为了生成L1串列分组，从所选多播队列中读取信元。在本发明的实施例中，当对所有读取的多播信元(小于K)的目的地交换端口信息进行逻辑“或”时，从对应于最新修正的多播路由交换端口的一个单播队列中读取一个信元，从而生成一个L1串列分组。

例如，当多播队列的数目小于交换平面的数目并且目的地交换端口信息被逻辑“或”时，对指示从队列中读取的两个多播信元是要输出到交换端口#1和#2和交换端口#5、#6和#8的信元的信息进行“或”操作。多播信元路由标记被修正，以将交换端口#1、#2、#5、#6和#8转化为目的地交换端口。根据本发明的实施例，利用从单播队列#1、#2、#5、#6和#8中读取的信元来生成有效L0串列分组。

本发明实施例的一个目标是，在为多播业务生成串列分组时，提供一种用以在ATM交换系统中生成和传输串列分组的方法，该方法在缺少空信元的情况下利用从单播队列中读取的有效信元来生成串列分组。

本发明的实施例涉及一种用于在ATM交换系统中生成串列分组的方法，包括：为根据输入信元的目的地端口数目及其特性而划分的多种业务类型选择一种服务队列的第一调度步骤；当第一调度步骤选择了多播队列作为服务队列时，从对应于多播队列的单播队列中读取生成串列分组所需的单播信元，并在没有用所选多播队列的多播信元生成有效串列分组时，生成包含有效信元的串列分组的第二调度步骤。

在实施例中，第一调度步骤从根据输入信元的目的地端口数目及其特性划分的单播队列、普通多播队列、组合多播队列和广播队列中选择一个服务队列用于当前信元时隙。在实施例中，第二调度步骤从标识了作为所选多播队列中存储的多播信元的目的地的第3级交换机的单播队列中读取生成串列分组所需的单播信元。

在实施例中，第二调度步骤包括：第一步骤，从标识了作为所选多播队列中存储的多播信元的目的地的第3级交换机的单播队列中读取所需的单播信元，随后生成一个包含两个有效信元的L0串列分组；以及第二步骤，在没有利用多播队列生成与交换平面数目一致的L0串列分组时，从对应于多播队列的单播队列中读取单播信元，随后生成与交换平面数目一样多的有效L0串列分组。

在实施例中，当组合多播队列被第一调度步骤选定为服务队列时，第二调度步骤从一个标识了所选组合多播队列(其指出了作为该组合多播队列中的多播信元的目的地的第3级交换机)的单播队列中读取单播信元，并生成包含该单播信元和组合多播信元的L0串列分组。

在实施例中，为了把单播信元与组合多播信元一起传输，存储于L0串列分组的报头中的交换路由标记包含用于向交换平面传输的第二交换路由标记，用于向合并信元传输的第三交换路由标记，以及用于向出口插入器传输的第四交换路由标记。

在实施例中，当普通多播队列被选作为服务队列时，第二调度步骤从对应于出口插入器之一(其作为从普通多播队列中读取的信元的目的地)的单播队列中读取单播信元，并生成包含该单播信元和普通多播信元的L0串列分组。

在本发明实施例的另一方面，提供了一种用以在ATM交换系统中传输串列分组的方法，该方法包括：在根据输入信元的目的地端口数目及其特性划分的多播业务中选择一个作为服务队列；选择性地读取所选多播队列的多播信元和对应于该多播队列的单播队列的单播信元，并生成串列分组；由第一交换机将该串列分组分割为与交换平面数目一致的子串列分组，并传输这些子串列分组；根据串列分组报头的路由标记，由交换平面把这些子串列分组传输到第三交换机；根据串列分组报头中包含的第三交换路由标记，由第三交换机复制L0串列分组，并向对应的出口插入器传输这些被复制的分组；通过出口插入器将L0串列分组分割为两个信元，通过连接ID复制多播信元，并向相应的端口传输这些被复制的信元。

根据本发明的实施例，当生成串列分组以处理多播业务时，通过第二调度器从所选的单播队列中读取有效信元，而非空信元。其结果是，利用有效信元而非空信元来生成串列分组，从而改善了交换处理率。

上述的实施例和优点仅仅是示例性的，并不对本发明构成限制。本发明可以容易地应用于其它类型的装置。本发明的说明书是用于进行说明，不限制权利要求的范围，对于本领域的技术人员，很显然可以有很多替换、改进和变化。