CN1267441A

CN1267441A - 交换设备

Info

Publication number: CN1267441A
Application number: CN98808148A
Authority: CN
Inventors: 皮特里·海曼
Original assignee: Nokia Networks Oy
Current assignee: Nokia Oyj
Priority date: 1997-07-14
Filing date: 1998-07-14
Publication date: 2000-09-20
Also published as: WO1999007180A3; US6735203B1; DE69836969D1; WO1999007180A2; FI972979A0; EP1013132A2; FI972979A; EP1013132B1; AU8443198A; FI104672B; BR9810719A

Abstract

本发明涉及一种包交换电信网的交换装置。该交换装置包括多个输入端口和多个输出端口,交换设备(SWN),以及每个输出端口和交换设备之间的输出单元(OU_i),所述输出单元包括一个输出缓存器(OB),其中存储发出的包。在交换机中,使用虚连接进行包交换,属于每个虚连接的包中的序列号用于表示这些包的相对顺序。输出单元(OU_i)维护当前预期包的序列号的虚连接特定信息,属于给定虚连接的包按照包的序列号以正确次序排序。为了提供硬件配置上简单而有效的装置,包数据存储在存储区中单独的重新排序存储器(RST1,RST2)中,存储区至少根据包的序列号确定,以及利用重新排序存储器,在各种情况下从至少根据预期序列号确定的重新排序存储器的存储区中搜索包数据,将包传送给输出缓存器,从而在发现给定包数据时,所述包被传送到输出缓存器。当包被传送到输出缓存器时,更新预期包的序列号。

Description

交换设备

本发明一般涉及包交换电信网中实现的交换。更确切地讲，本发明涉及这种网络，尤其是ATM网络中使用的交换设备。

为了便于连接以下描述，首先定义后面将会用到的一些术语。

交换设备或交换矩阵(这两个术语都可以使用)包括多个交换元件，它们或者相同，或者不同，按照给定的拓扑互连。在本领域的(英语)文献中，这种交换矩阵也可以称为“交换网络”，因为这些交换元件形成了具有给定拓扑的网络。因此，如果交换矩阵的交换元件及其相互之间的连接已知，则认为交换矩阵具有确定的形式。

交换设备由交换元件组成，它通过将多个交换元件连接成包括并行或串接的交换元件的网络而形成。并行交换元件组成一个交换级。连续交换级的交换元件通过内部链路按照上述拓扑互连。

术语交换机用于表示配置成交换矩阵的实体。因此，交换机可以表示用于电信网中的信号交换的任何装置。在本申请中，交换机是包交换机，因为本发明涉及包交换电信网，尤其是ATM网中的交换。有时还可以将交换机称为交换系统。

ATM(异步传递模式)是面向连接的包交换技术，它由国际电信标准化组织ITU-T选作实现宽带多媒体网络(B-ISDN)的目标传递模式方案。在ATM网络中，常规包交换网(例如X.25网)的问题通过发送定长(53字节)的称为信元的短包来克服。每个信元包括48字节净荷部分和5字节消息头。该消息头包括的数据中有地址信息，在ATM网络中根据该地址信息进行信元的寻路。此处不再进行ATM网络的进一步讨论，因为它对理解本发明并不是必要的。如果需要，可以在本领域的国际标准和教科书中发现该课题的详细描述。

常规TDM网(时分复用，也称为STM，同步传递模式)中的交换机无法直接实现ATM网络中的交换处理。为常规包网络开发的交换方案通常也不适用于ATM网的交换。优化ATM交换体系结构的选择不仅受固定信元大小和信元消息头的有限功能的影响，而且还受信元流的统计行为和ATM交换机必须以非常高的速率工作(目前一般约150...600Mbit/s)的事实的影响。

图1概要地示出了从外部看的ATM交换级。该交换机有n个输入线路I₁...I_n，m个输出线路O₁...O_m。信元流CS通过每根输入线到达ATM交换机11。信元流中单个信元的消息头由索引HD表示。在ATM交换机中，信元从输入线I_i交换到输出线O_j，同时信元消息头的值从入值转换成出值。为此，交换机包括转换表12，利用它完成所述转换。从该表中还可以看出，例如通过线I_i接收的，消息头的值为X的所有信元都被交换到输出端口O₁，从而它们的消息头值同时社置为值K。在不同输入线上出现的信元的消息头可以具有相同值；例如，在输入线I_n接收的，具有相同消息头值X的信元也被交换到输出线O₁，但在输出线上它们的消息头值为J。

下面将采用现有技术消息头转换方法描述本发明，这种转换方法按如下步骤转换消息头：使用交换机内部唯一的连接标识符，例如输入侧标识符ICI，输出侧标识符ECI。在这种情况下，消息头转换链是VPI_in/VCI_in→ICI→ECI→VPI_out/VCI_out。这种过程的优点在于，标识符ICI和ECI可以是直接的存储器地址，利用该地址可以快速地访问与连接相关的数据。

因此，交换机的主要任务是：从输入线向所需输出线传送信元(包)，以及消息头转换。但是，在该图中也很明显，两个信元可能会偶尔同时竞争对同一输出线的访问。为此，交换机必须具有缓存容量以避免在该情况下不得不丢弃信元。因此，交换机的第三个主要任务是提供缓存。这三个主要任务的完成方式以及在交换机的哪个部分处理实现的不同导致了不同的交换方案。

另一方面，根据装置中使用的交换元件是否被缓存，可以将ATM交换设备划分成两类。

在采用无缓存的交换元件的装置中，信元通过装置的路由寻址工作在信元层，使得可以为每个信元独立选择路由，而不管信元属于哪个虚信道。在简化的情况下，信元通过该装置的行动可以被认为包括两个步骤。在第一步骤中，信元从输入端口通过装置发送，在第二步中，交换元件或输出端口向输入端口指示哪些信元成功地通过了该装置。必须进行后一步，因为如果信元可能尝试使用装置的同一内部链路，则所有同时传输的信元只有一个得以继续，其余都需要丢弃，因为交换元件没有缓存器。这种交换设备的问题在于，它的所有元件的操作必须相互同步，即所有元件和输入和输出端口必须同时处于上述步骤。因为信元传输非常快，实际上除上上述两步之外，还可能需要若干其它的步骤，同步无法仅通过元件间的握手信号来实现，而是所有元件必须与公用的时钟源同步，如果交换设备非常宽，则难以将时钟信号分发给所有元件，必须将其划分成多个插入单元。还必须注意，即使具有无缓存交换元件的交换机也必须在该装置的输入或输出端口中具有缓存容量，以避免在信元同时竞争对交换机同一输出线的访问情况下不得不丢弃信元。

由缓存交换元件构成交换设备没有上述同步需求。信元通过交换设备的路由选择可以与虚拟信道相关。但是，为此通常必须维护一个交换设备内部链路的负载记录。缓存交换设备通常阻塞在连接层，因为将其构造成无阻塞装置通常需要过多的容量，使得它在经济上不可行。在阻塞装置中，连接路由的选择是尝试减少阻塞时需要考虑的相当重要的因素。

考虑前述因素，许多生产厂商希望从以下方法中寻求一种方案：在具有缓存交换元件的交换设备中也在信元层选择路由。为了避免维护装置内部链路负载记录的必要性，并使得负载的分布更均匀，通常随机选择信元路由。(该选择也可以按照适当的非随机算法完成)。在这种情况下，交换设备可以以合理的成本构造成无阻塞装置。

因为在这种随机路由选择过程中，信元的路由会发生变化，所以后发的信元可能会更快地通过交换设备，超过较早发送的信元。这是因为交换元件的负载及其缓冲器的填充速率不断变化，因此信元在该装置中的停留时间也随时间和不同路由而不同。要想恢复信元顺序，必须使用称为重新排序的特殊方案。

原则上，根据重新排序在交换设备的哪一部分中执行，有两种基本方案。信元可以在为此提供的重新排序(微)电路中的交换设备之后重新排序(方案1)，或者在交换设备内部的交换级之间已完成重新排序(方案2)。

通用于上述方案的因素是测量信元通过交换设备(方案1)或者发送到交换元件(方案2)所用的传输时间，这可以例如利用时间戳来实现，之后将信元延时一段时间，该时间足以超过预定的总传输时间。这确保了所有信元通过交换设备的延时相同。但是，这些方案的缺陷是，它们需要在交换设备的输出端口(方案1)，或者在交换元件(方案2)中采用非常复杂的并行处理电路。

与方案1相关的一种重新排序实现在美国专利第5,481,536中公开。该方案为信元采用序列号，利用它可以推断出通过同一连接的信元的相对顺序。信元被写入公用的存储器，从内容可寻址存储器(CAM)中搜索地址，利用这些地址可以从公用存储器中读出信元。

这种方案也具有复杂的实现，要求特殊的存储器(CAM)，该存储器在检索时间和成本上不等于常规(快速)存储器。

另一方面，美国专利第5,319,360和5,173,897公开了一种ATM结点，其中虚连接上的信元也具有序列号，利用它识别信元的相对顺序。在交换设备和结点的输出端口之间的输出单元中，信元存储在存储器中，在该存储器的首部提供了移位寄存器部分，之后是第一FIFO单元。从队列的头部将信元读入锁存器，信元进一步从该结点的锁存器读出。在从锁存器读出之前，比较锁存器上的信元的连接标识符和移位寄存器部分和FIFO单元的所有其它信元的连接标识符，对连接标识符与锁存器上的信元相同的所有信元进行附加比较，在该比较中，比较这两个信元的序列号。如果存储器中的信元较早，那么它替换锁存器上的信元，锁存器上的信元被传送回存储器，替换掉较早的信元。通过这种方式，在需要传送信元时，得到属于所述连接的最早存储的信元。

这种方案的缺陷在于，它包括非常复杂的存储器装置，并且它要求大量的比较处理来找到各种情况下最早存储的信元。

本发明的目的是消除上述缺陷并提供一种方法，利用该方法可以使用尽可能简单的设备实现包的重新排序，而不需要大量的比较处理。

该目的通过独立的权利要求所定义的方案实现。

本发明使用了上述基本方案，其中连接上的每个包(或信元)具有一个次序戳，它是一个序列号，通过它可以以正确的顺序对连接上的信元排序。此外，本发明采用了为预期包维护序列号的基本方案。其思想在于，将包或与其相关的信息(例如存储器指针)存储在存储区中，按照给定的预定联系，该存储区至少取决于该包的序列号。这种处理至少在每次根据预期序列号检测到包的顺序发生了改变时进行。如果到来的包的序列号等于预期包的序列号(即如果包的次序没有改变)，那么该包还可以直接传送给输出缓存器。通过在取决于包的序列号的存储区中存储，至少每次没有接收到包时，按照相同联系，可以从取决于当前预期序列号的存储区中搜索出需要传送给缓存器(或其存储器指针)的包。

在本发明的一种特定的优选实施例中，存储器中的存储在仅根据包的序列号确定的存储区中进行，并从仅根据预期序列号确定的存储区中读出存储器。通过这种方式，可以尽可能减小所需的存储器容量。

下面结合图2...6，通过附图的例子来详细描述本发明及其优选实施例，在附图中

图1说明了ATM交换的基本原理；

图2一般说明了按照本发明的交换机；

图3说明了在交换机边界进行的信元处理；

图4说明了通过交换设备的信元的结构；

图5示出了在交换设备的每个输出端口中包含的单元的框图，该单元按照本发明的第一实施例实现，以及

图6示出了在交换设备的每个输出端口中包含的单元的框图，该单元按照本发明的第二实施例实现。

为了说明按照本发明的方案，下面首先给出交换机构造的描述，该描述是从本发明的角度给出的一般描述。在这一层次上，这些方案仍然象已知的那样。

交换机能够从功能上划分成3个部分，如图2所示：信元预处理单元PPU、分发部分RRS，以及路由寻址部分RS。只有后两部分包含交换元件，因此它们形成了实际交换设备(或交换矩阵)SWN。

本发明的出发点是单独考虑通过交换设备的每个连接(交换)。为此，在交换设备之前提供了信元预处理单元PPU，为每根输入线I_i(i＝1...n)包括一个预处理单元PPU_i。这些单元为每个连接上的信元指派序列号，使得每个连接具有唯一的信元序列号，该序列号独立于其它连接。在建立连接时，可以开始信元的序列编号，例如从0开始，增大到某个上限，例如到值N-1，之后，编号重新从0开始。但是，所有连接使用相同的序列号范围(0...N-1)，从该范围中连续分配序列号。

分发部分RRS随机或按照给定的预定算法为信元选择路由，使得在给定输入线到达的信元尽可能平均地发送给最好是分发部分的所有输出线。这使得信元流能够平均地分发给所有可用的路径，这又减少了交换机的内部阻塞。该部分的路由寻址部分RS基于包含在信元中的路由寻址标记将信元寻路到正确的输出端口。因此，路由寻址部分使得具有给定输出端口地址的所有信元都从分发部分寻路到所述输出端口，而不管它们发向路由寻址部分的哪个输入端口。

这样，在按照本发明的交换机中，信元所经过的路径由随机或按照给定算法选择的第一部分，以及基于路由寻址信息选择的第二部分组成，从而信元能够被发往正确的输出端口。这种结构是以前所知的。

交换设备的类型或详细结构对本发明并不重要，因为对本发明而言，信元的路由寻址如何实现并不重要。该路由寻址可以以任何已知的方式实现。但是，随机路由寻址交换设备的优点在于，该设备可以比较均匀地分发负载，在这种情况下，包的顺序被改变的可能性也较小。因此，最好是交换设备包括一个分发部分，可以建立从该分发部分的每根输入线(I_j，j＝1...n)到最好是分发部分的所有输出线(RO₁...RO_k)的路由，该交换设备包括这样一个路由寻址部分，其中可以(按照路由寻址信息)建立从每根输入线(RO_i，i＝1...k)到所需输出线(O_i)的至少一个路由。

图3示出了每个预处理单元PPU_i的结构。进入信元首先传送到第一转换单元ICU_i，根据包含在每个信元中的VPI/VCI标识符生成交换设备的输入侧使用的内部连接标识符ICI，并将其插入信元。这样，在输入侧，每个连接接收设备内部唯一的连接标识符，利用它在交换设备内部区分不同连接的信元。最好使用交换设备内部的连接标识符来进行区分，因为VPI/VCI标识符不使用单个连续值范围，这在另一方面通过内部连接标识符实现。

信元从第一转换单元传送到编号单元SNU_i，后者包括表T1，用以维护连接特定的一个顺序戳SN_i。该顺序戳是该连接上下一待发送信元的序列号(或者通过所述连接的上一信元的序列号，在该信元到达时增量1，给该信元正确的序列号)。在连接启动时，该编号初始化。在编号单元中，读出附在信元上的连接标识符ICI的值，根据读出的值，从表中搜索对应的序列号。采用预定数量的离散值作为序列号，例如从模计数器得到的整数值，使得计数器从连接开始时例如从0到(N-1)计数信元，之后它再次从0开始，以此类推。序列号被附在信元上。

在预处理单元中，还可以(以已知方式)将交换机内部的路由寻址标记插入信元；这在路由寻址标记插入单元RIU_i中进行。每个预处理单元中的最后一个元素是第二转换单元ICU2_i，其中输入侧的连接标识符ICI被转换成输出侧的连接标识符ECI。前面提过，最好在输入和输出侧使用唯一的内部连接标识符，从而能够快速访问连接相关数据(这两个标识符都使用相同的地址值范围)。

因此，到达交换设备的每个信元如图4所示。众所周知，实际ATM信元包括48字节的净荷和5字节的消息头。最好有3个标识符字段，每个字段包含一个交换机内部的标识符，在交换机的输出端将其删除，该标识符被插入ATM信元。消息头字段不需要通过交换设备传送，它可以在交换矩阵的输入端口删除，在交换矩阵的输出端口插入带有新信息的消息头字段。路由寻址标记字段RI_F包括交换机内部的路由寻址标记，信元通过它在交换机(路由寻址部分)中以已知方式寻路到正确的输出端口。序列号字段SN_F包含编号单元所指派的序列号，或是表T1直接包含的值，或者利用该表所包含的值生成的值。连接标识符字段ECI_F包含第二转换单元所指派的连接标识符ECI。

分发部分所完成的信元分发可以例如以如下方式实现：随机或者按照给定算法生成路由寻址标记中对应于分发部分中的交换级的那些比特，因此在分发部分中随机或者按照所述算法为信元选择路由。整个路由寻址标记可以在交换矩阵的输入端口生成，或者可以留下对应于随机分发级的部分不生成，在这种情况下，所述级独立完成随机分发。但是，因为路由寻址可以以任何已知方式实现，所以信元中不一定需要路由寻址标记。

下面详细描述单个输出单元OU_i的结构和操作。

图5说明了在按照本发明的第一实施例实现输出单元时，单个输出单元的功能框图。输出单元的核心由重新排序表(或者一般是重新排序存储器)RST1构成，其中存储了一些到达的信元(或者这些信元的信息，例如存储器指针)。在该实施例中，重新排序表为每个连接包括一行，以及数量等于每个连接(连接的数量为K)的重新排序值的数量(N)的存储单元。这样，该表总共包括K行和N列。在行和列交叉处的表元构成一个存储位置，因此在重新排序表中共有K×N个存储单元。

在每个输出单元的输入端提供了检查单元CU，它从每个到来的信元读取连接标识符和序列号。序列号单元PSN包含每个连接的序列号值，该值是该连接上下一预期信元的序列号。为此，该单元包括表T2，它与预处理单元的表T1类似。在信元到达时，该检查单元从表T2中根据输出侧的连接标识符值读出该连接上预期的下一序列号值，将其与到达的信元的序列号值相比较。如果值相等，则检查单元将信元直接传送到FIFO类型的输出缓存器OB，将表T2中序列号的值增量1。如果这两个序列号不等，则检查单元在重新排序表中存储该信元，存储在对应于该信元的连接标识符的行中对应于该信元序列号的存储单元中。每当检查单元将信元存储在重新排序表中，它还将该信元所承载的连接标识符存储在FIFO类型的连接标识符缓存器ECI_B中。这样，当信元没有在由其序列号所指示的连接的信元队列点上出现，则存储在重新排序表和连接标识符缓存器中。在这种情况下，表T2中序列号的值也不增加。

输出单元还包括单独的读取单元SU，它连续扫描存储在重新排序表中的信元，将其移入输出缓存器，使得在输出缓存器中，每个连接的信元的顺序又变成正确顺序。读取单元可以与检查单元并行工作，或者，例如在没有信元到达输出端口时工作。读取单元首先从连接标识符缓存器ECI_B的头部中读取连接标识符，据此从序列号单元读出所述连接上预期的序列号。之后，读取单元在重新排序表的存储单元搜索对应于所述序列号和连接标识符的信元。如果该存储单元上有信元，则读取单元将其传送给输出缓存器，将预期序列号的值增量1。如果所述存储单元中没有信元，则读取单元将连接标识符返回给缓存器ECI_B，从缓存器的头部取出一个新的连接标识符，它对该连接标识符再次执行上述操作。这样，当信元被传送到输出缓存器时，仅更新预期的序列号。如果发现信元，可以确信它被传送到该连接的信元序列，传送到其序列号所指示的位置。

在启动连接时，所述连接上的预期序列号被更新为0。如果例如编号为0的信元首先通过连接到达，则直接将它传送给输出缓存器。如果首先到达的信元的序列号例如是1，则将其存储在列1中，在对应于该连接标识符的存储单元。连接标识符也存储在缓存器ECI_B中。如果通过连接到达的下一信元的序列号例如是2，则再次将信元存储在重新排序表中，将连接标识符存储在缓存器中。在这种情况下，当读取单元在序列号0到达之前读取信元时，它发现重新排序表没有包含可以进一步传送的信元(因为在对应于0的存储区没有信元)。预期序列号保持为0，直至序列号为0的信元到达。当该信元到达时，它直接传送给输出缓存器，预期序列号被更新为1。之后，当读取单元从缓存器中取出所述连接的标识符，并从序列号单元PSN取出预期序列号时，它找到重新排序表中序列号为1的信元，并将其传送到输出缓存器。在传送后，预期序列号被更新为2，因此，读取单元在重新排序表中找到序列号为2的信元。

不是整个信元，而是仅有连接标识符和公用存储器的指针可以存储在重新排序表的一个存储区，前述公用存储器存储所有不能直接传送给输出缓存器的信元。该公用存储器由图中的索引CM表示，因为它是该结构的可选部分，所以以虚线表示。因此，重新排序表包含了信元或与信元相关的其它数据，据此可以找到该信元。特定的指针值(或比特)可指示该信元未存储在公用存储器中。

上述方案占用的存储器空间相当高。实际上，顺序戳N的数量的实际值是512。如果假定仅在重新排序表中存储指向公用存储器的指针，并且连接标识符由14比特表示，这种情况下每个端口有2¹⁴＝16384个连接，每个信元在重新排序表中占用的空间是4字节(连接标识符2字节，指针2字节)，则重新排序表所需的存储空间为512×16384×4字节＝32MB。

图6说明了从存储器空间占用角度来看更为有利的一种实施例。在这种情况下，重新排序表(或者一般是重新排序存储器)RST2包括数量等于序列号的列，但是选择值M作为行数，它是一个合适的限度，使得重新排序表中多于M个信元同时需要具有相同序列号的信元的可能性非常小。实际上，可以认为M小于连接的数量，后面将会看到。

重新排序表的这种大幅度压缩可以通过以下考虑来证实。在低速系统中，连接上信元的顺序几乎很难变化(在这种情况下，也不需要较大的重新排序表)，因为在它们中，甚至在下一信元到达交换设备的输入端口之前，前一信元就已通过交换设备。按照国际标准化组织ITU-T的标准I.371，交换设备的信元延时最大可以是300毫秒。信元以300毫秒间隔到达的连接的速度是1.4Mbit/s(＝1/0.0003×54(信元中的字节)×8(字节中的比特)。因此，连接上速率小于1.4Mbit/s的信元序列从不需改变。因为上述随机路由选择部分相当均匀地分发负载，所以交换设备中一个路由远比较快的另一路由要快的可能性非常小。让我们假定一种赶超情况，其中后一信元通过询问发现比设备中传送前一信元的路由少例如50个信元(这几乎不可能)。在这种情况下，假定到设备的链路是STM-4级(620Mbit/s)，为了使信元的顺序能够改变，连接速率应当至少是12.4Mbit/s(620/50Mbit/s)。这样，链路上可以容纳较大数量的低速连接，几乎不会因信元顺序变化而引起问题。另一方面，对较快的连接而言，其带宽消耗越大，问题就越多，但同时链路上可容纳的连接数量较少(在上述情况下最多为50)。因此，可以大幅度减少重新排序表中的行数。

图6的实施例中，如果检查单元检测到序列号不等于预期序列号时，它将该信元存储在对应于它的序列号的列中，在第一空存储单元。检查单元从行0开始，在顺序戳所指示的列中，简单地遍历最多M行，在缓存器ECI_B中存储第一空存储单元和连接标识符。

如果另一方面，在给定时刻没有信元到达输出单元，否则读取单元会有空闲时间，它检查重新排序表是否包含适于发送的信元。在这种情况下，读取单元在连接标识符缓存器中搜索输出侧的连接标识符值，并在序列号单元中搜索预期序列号(象图5的实施例那样)。之后，它从对应于该序列号的列的开始处搜索(从行0开始)所述列是否包括同一连接标识符值。一旦发现正确的连接标识符，读取单元将所述信元传送给输出缓存器，将预期连接标识符增量1。如果该列并不包含正确的连接标识符，则读取单元将连接标识符返回给缓冲器ECI_B中队尾，从对头取出新的连接标识符，对其进行相同的操作。

在图5和6中，传送的信元(或者与信元相关的信息)由细箭头标记，序列号的传送由粗箭头表示，连接标识符的传送由虚线箭头表示，行号的传送由虚线小箭头表示，存储单元占用状态信息由小箭头表示。在图5中，箭头A1和A2说明了以下指针(坐标)的传送，该指针指示按照箭头A3将信元传送到其中的重新排序存储器的存储单元。箭头A4和A5分别说明了以下指针(坐标)的传送，该指针指示按照箭头A6将信元从中读出的重新排序存储器的存储单元。类似地，图6中箭头A1和A2说明了说明了以下指针(坐标)的传送，该指针指示按照箭头A3将信元传送到其中的重新排序存储器的存储单元。箭头A4和A5分别说明了以下指针(坐标)的传送，该指针指示按照箭头A6将信元从中读出的重新排序存储器的存储单元。另一方面，箭头A7和A8说明了在空存储单元的搜索和管理中需要传送的信息。此外，这些图并没有示出实现以上转换ECI→VPI_out/VCI_out。的装置，因为所述装置与实际的发明无关。

就以下意义而言，上述读出原则实现了不同连接之间的公平性：重新排序表中连接具有的信元越多，从该连接标识符缓存器中读出该连接的标识符的次数也就越多。

图6的重新排序表中行的数量和必要的存储容量可以例如通过以下方式大致估计。如果图6的重新排序表RST2由快速存储器，例如SSRAM(静态同步RAM)实现，SSRAM目前的检索时间低于20ns，并且信元以例如STM-4速率(即以0.68μs的间隔)到达重新排序表，在每个信元期间该单元有时间读或写存储器至少34(＝680/20)次。如果实现如上所述，那么如果希望确保有时间让至少一个信元搜索到达输出端的每个信元，则M的值应小于34。如果M的值是例如32，顺序戳的数量例如是512，那么重新排序表仅在共享存储器中存储连接标识符(2字节)和指针(2字节)，重新排序表的存储空间需求是512×32×4字节＝64kB。因此，实际上甚至可能增加N的值，使得连接信元在重新排序表中有更好的分布。

公用存储器的大小不需要很大；实际上约100-200信元的存储器便已足够。

以上描述的简单过程中，信元直接位于表中该顺序戳所指示的位置，即以增序排列。信元的位置也可以由已知的散列函数确定，该函数的值通过顺序戳和另一常量，例如连接特定常量计算，这种情况下，所有连接上的信元均匀分布在重新排序表中。

也可以改变上述第一实施例，使得检查单元不进行比较，而是直接将所有信元(或指针)存储在重新排序表中该连接标识符和序列号所指示的存储单元中。读取单元从缓存器ECI_B中读出连接标识符，从序列号单元中读出预期的序列号。之后，读取单元直接在该连接标识符值和序列号值所指示的存储单元中搜索信元。如果发现了信元，则读取单元将其传送给输出缓存器，更新所述连接的预期序列号。如果没有发现信元，则读取单元将连接标识符返回给缓存器(ECI_B)，从缓存器的头部取出新的标识符进行处理。因此，该过程是类似的，只是在这种情况下，接收信元时不进行顺序戳的比较，而是将到来的所有信元(或其存储器指针)存储在重新排序表中，将连接标识符存储在FIFO缓存器ECI_B中。这种实施例的功能框图对应于图5和6，但是在这种情况下，检查单元和序列号单元之间，或者检查单元和输出缓存器之间不提供连接。读取单元每次从重新排序表中将一个信元移到输出缓存器时，更新预期序列号。

公开的第一实施例在延时方面较为有利，因为其中大多数包可以直接传送给输出队列。

尽管以上结合附图的例子解释了本发明，但显然本发明并不局限于此，它可以在后附权利要求书所提出的创新思想范围内有所变化。例如，可以在图5和6的输出单元中增加连接特定信元或时间计数器，用于指示多于给定数量的信元到达了重新排序表，并且正在等待，或者重新排序表中的信元已等待了足够长的时间，在这种情况下，可以假定其间已丢失了至少一个信元，预期序列号可以增量1。只有存储器指针作为包相关数据存储在重新排序表中，连接标识符可以从公用存储器中搜索，尽管这种方案需要附加的存储器搜索。这样，当后附权利要求提到包数据时，这应当理解成是指包或包的一部分，或者利用它可以发现包或包的一部分的任何信息。输出单元也可以包括不同业务量类别的多个连接标识符缓存器(ECI_B)和其它连接特定信息，读取单元可以利用这些连接特定信息来例如促成对延时敏感的业务量。

Claims

1.一种包交换电信网的交换装置，该交换装置包括：

-多个输入端口和多个输出端口，

-交换设备(SWN)，

-每个输出端口和交换设备之间的输出单元(OU_i)，所述输出单元包括一个输出缓存器(OB)，其中存储发出的包，每个包在离开交换设备之后，存储在相应的输出端口的输出缓存器中，

按照该交换装置，

-使用虚连接进行包交换，属于每个虚连接的包中的序列号用于表示这些包的相对顺序，每个虚连接具有位置的连接标识符，以及

-输出单元(OU_i)维护当前预期包的序列号的虚连接特定信息，属于给定虚连接的包按照包的序列号以正确次序排序，

其特征在于，

-包数据存储在存储区中单独的重新排序存储器(RST1，RST2)中，存储区至少根据包的序列号确定，以及

-利用重新排序存储器，在各种情况下从至少根据预期序列号确定的重新排序存储器的存储区中搜索包数据，将包传送给输出缓存器，从而在发现给定包数据时，所述包被传送到输出缓存器，以及

-当包被传送到输出缓存器时，更新预期包的序列号。

2.根据权利要求1的交换装置，其中比较到达输出单元的信元的序列号和预期包的序列号，其特征在于，当序列号和预期包的序列号相等时，每个包被直接传送给输出缓存器，当包的序列号和预期包的序列号不等时，每个包被传送给重新排序存储器。

3.根据权利要求2的交换装置，其特征在于，

-包数据被存储在仅根据包的序列号确定的存储区，在从所述存储区开始处开始的第一空闲存储单元中实现存储，以及

-从仅根据预期序列号确定的存储区的重新排序存储器搜索包数据，该搜索通过连续遍历所述存储区的存储单元来实现。

4.根据权利要求3的交换装置，其特征在于，重新排序存储器是两维表，包数据存储在其中，并从该表的存储区搜索，该表由各种情况下的序列号所指示的行或列构成。

5.根据权利要求3的交换装置，其特征在于，所述存储区中单独可寻址的存储单元的数量小于支持的连接的数量。

6.根据权利要求3的交换装置，其特征在于，至少将与包相关的连接标识符存储在存储单元中。

7.根据权利要求2的交换装置，其特征在于，根据包的序列号以及与包相关联的连接标识符确定存储单元。

8.根据权利要求7的交换装置，其特征在于，重新排序存储器是两维表，包数据存储在其中，并从该表的存储区搜索，该存储区由包的序列号所指示的第一维坐标和与包相关联的连接标识符所指示的第二维坐标的交叉点上的表元确定。

9.根据权利要求1的交换装置，其特征在于，到达输入端口的包所承载的连接标识符形成交换机内部的连接标识符，它被插入需要传送通过交换设备的包中。

10.根据权利要求1的交换装置，其特征在于，包被存储在公用存储器(CM)中，包数据包括一个指向公用存储器中存储该包的区域的指针。