CN1073316C - 信元交换设备和为信元寻找路由的方法 - Google Patents

Abstract

信元交换设备由多元交换端口(2.n)组成，每个口与一定数目的用户终端相连，用于发送和接收各个用户终端的信元，该信元包括消息负载和地址信息。交换中心(4)连接在各个交换端口之间，使它们能够彼此通信。在交换端口中提供有标记装置。它基于用户终端收到的信元(17)中心地址信息产生一个属于该信元的标记(14)，其中包含能够为信元找到通过交换中心路由a路由信号。提供了在标记对应的信元之前将标记发送给交换中心的装置，每个信元对应一个标记。在交换中心里的规划装置接收预先发送的标记。并基于其中包含的路由信息产生规划信息，该信息是关于每个信元从交换端口发送的时间，将其规划使得在这些发送时间内，信元可以在不与其它信元发生冲突的情况下被送到目的端口。规划信息被送到信元的发起交换端口，在交换端口中，信元一直被保存直到它们各自的规划发送时间到达。

Description

信元交换设备和为信元寻找路由的方法

本发明涉及由多元交换端口组成的信元交换设备，每个交换端口与一定数目的用户终端相连，用于发送和接收该用户终端的信元，该信元由消息有效负荷和地址信息组成；交换中心，连接在上述交换端口之间使得它们能够彼此通信；交换端口中的标记装置，用来基于上述从用户终端收到的信元中的地址信息产生一个属于信元的标记，其中包含能够使信元通过交换中心的路由信息。

本发明进一步涉及为信元寻找通过信元交换设备的路由的方法，交换设备由多元交换端口组成，每个交换端口与一定数目的用户终端相连，用于发送和接收该用户终端的信元，该信元由有效负荷和地址信息组成，交换中心，连接在上述交换端口之间，使得它们能够彼此通信。

在上面所指类型的一个交换设备中，需要设置信元缓冲区以避免信元同时到达交换设备并经过信元的公共资源，如输出端，时丢失信元。在已知的系统中，信元缓冲区需要安装在交换中心里来达到这一目的。为了取得高效率，在交换中心需要有大量的信元缓冲区。

将信元缓冲区只设置在交换端口中，可以减小交换中心的尺寸，相应地减小它的成本。这样的好处在于，交换中心的低成本可以减小规模可变和目前只配置了几个端口的系统的总成本。这样交换设备的成本会更加便宜。

然而，一个问题是，怎样在交换中心内避免冲突，从而在交换中心内对信元缓冲器的需求可以被消除。

在EP268,259中描述了一个交换设备，它在输入和输出之间有多级分组传送过程。由一个标记标识分组的目的地，可将分组送到适合的输出同时避免发送冲突。对那些由于冲突而不能立即发送的分组提供了缓冲区，同时设定了分组在分组传输网络中停留时间的上限。

分组经过若干步骤的处理，并且标记在不同步骤中被修改，但是没有为了规划从输入端口发送分组的时间而预先发送标记。

在US4,630,258中描述了一个具有多个输入和输出端口的分组传输结点。每个输入端口都连接有一个队列用于存储和传送到所有输出端口的分组。在到达不同端口的分组间可能会发生冲突。在输入和输出端口之间连接有多端口存储器。设置一控制逻辑，将分组按预定的优先级方案从存储器传送到相应的路由标记所指定的输出端口。由一个缓冲区逻辑来仲裁到达同一个输入端口并竞争同一个输出端口的多个标记。另外，实行了对到达同一输出端口的多个分组的随机选择，使得单个分组不必在一未定的时间段内等待。

在输入端口没有使用标记。已有的标记跟随被传输的分组，因此没有预先发送。

在US4,621,359中描述了分组传输，其中一个分组传输结点处理包含有表明输出目的端口的路由标记的多个分组。其目的是使到达每个输出端口的分组数目达到平衡。因此，产生了新的标记用于重新分配输出端口上的负载。新的标记被修改，目的是得到一个预定的输出优先级方案。

其中没有为了给随后的分组提供时控发送方案而预先发送标记。

在US4,623,996中描述了一个分组传输结点，它处理包含有表明输出目的端口的路由标记的多个分组。一组多元队列开关分别连接在多元输入端口和多元队列集合之间，队列集合包含许多个队列，用于存储应用分组并且做为输出目的端口的函数传输应用分组。每个队列集合中心多个队列连接到不同的输出仲裁器上，后者用于控制寻找到达一特定输出端口的路由。

其中没有为了得到后面分组的时控发送方案而预先发送标记。

本发明的一个目的是在上面介绍中说明的交换设备类型中，解决交换中心中冲突的问题，问题的解决要使得交换中心消除对信元缓冲区的需要。

依据本发明的交换机包括在发送相应的信元之前预先发送标记到交换中心的装置，每个标记对应一个信元；包括在交换中心里的规划装置，它接收上述预先发送的标记，并且基于标记中包含的路由信息产生有关各个信元从交换口发送时间的规划信息，从而在这些发送时间内信元能够在不与其它信元发生冲突的情况下被送到目的端口；包括发送上述规划信息到信元发起交换端口的装置，包括将信元保存在交换端口中，直到它们各自的规划发送时间到达的延迟装置，以及在信元各自的规划发送时间内将信元还到交换中心的装置。

依据本发明的方法包括如下步骤，基于收到的信元中的上述地址信息，为了每个收到的信元产生一个包含路由信息的各自的标记，该路由信息可为信元找到通过交换中心到达所想到达的目的端口的路由；在相应的信元之前预先发送上述标记到交换中心；基于上述预先发送的标记中所包含的路由信息，产生有关每个信元从各自端口发送时间的规划信息，该规划信息使得在这些发送时间内，各个信元可以在不与其它信元发生冲突的情况下送到目的地；发送上述规划信息到各个信元的发起端口；在各个端口保存信元，直到它们各自的规划发送时间到达；以及在信元的各自规划发送时间内，将信元送到中心。

依据本发明，由于事先提供路由信息给中心，于是避免了各个端口的冲突。通过端口可以得到的一合适的反馈信息，信元被提前发送，以避免多个信元同时通过公共资源。

信元借助于标记通过中心。标记是一个每个信元前面的路由信息。每个标记包含的路由信息和它之后立即到达的信元无关，而是和之后跟着到达的一些信元有关，这样，信元在端口中被延迟。在中心中完成对这些路由信息的处理，然后一个相应的规划信息被反馈回端口。

多个信元以相邻固定长度间隔被传输，该间隔被称为发送周期，并且信元使用包含内部信元目的地的标记被发送通过中心。可以以一种已知的方法提供信元的目的地，即比特图中比特的方式，在这里一个信元可以有几个目的地(群地址)。在端口中使用了标记方法。每个信元之前有一个标记。

标记在信元发送周期时间内从端口被发送到中心。在相反的方向上，即从中心到端口，在发送周期内，规划信息和表明一次有效信元发送的标志取代标记被发送给端口。

在入和出的发送周期之间存在一定的相位差异，因此在从端口到中心的发送周期内，信元有时间通过中心，然后不需要任何额外的时延被放置从中心到端口的发送周期内。

在相应的标记被发送到中心之后，信元在端口中被延迟确定的最小发送周期数，这样预留了处理的时间避免了冲突。

通过信元时间的分布避免了冲突。中心规划所有的信元并且通知各个端口，于是各个端口被强制在特定的发送周期内发送信元。竞争同一资源的信元在不同的发送周期内被发送。没有路由信息的标记告诉中心没有新的信元等待被规划。依据本发明的解决方案可以得到一个小中心，它与系统的规模无关，在一定的限制条件下可以有很经济的成本。另外，在开始的时候系统很小使得升级的时候不会损失原始投资。

在下面参照附图将给出本发明更详尽的描述。附图中

图1说明应用本发明的一例信元交换设备的拓扑结构；

图2说明一个标记和它的信元路由比特图；

图3说明规划信息的格式；

图4说明一个信元由标签和有用的消息负载组成；

图5说明端口到中心和中心到端口的发送周期之间的相位偏移，以及标

记和与标记相关的规划信息之间的关系；

图6给出一个标记和它对应的信元的位置，其中信元被延时两个发送周期；

图7给出一个模块，它是规划设备的一部分，控制规划序列和时间优先级；

图8给出一个状态机，它是规划设备的一部分，被包含在控制电路内；

图9给出一模块，它是规划设备的一部分，为规划数据存储器产生锁定脉冲；

图10表示接收到达标记的存储器；

图11表示一数据交换设备，它从接收到达标记的存储器行中选出一个，将其放到输出上；

图12给出一在规划数据存储器中许多地方用到的电路；

图13给出存储规划后数据的存储器的一个实例；

图14给出冲突控制电路的一个实例；

图15给出一个规划设备，它包含图7-14中的许多模块；

图16给出在端口中延迟信元并在规划的发送周期内将信元送到中心的延时装置；

图17给出延时装置中多处实例用到的一个模块；

图18表示一个状态机，它是各个端口中延时装置上如图7所示模块的组成成分；

图19给出应用本发明，信元通过所建议类型的交换设备进行连接的情形。

图1概略地给出一类能够应用本发明的信元交换设备。

交换设备包括一些2.n端口和一个有许多输入6.n与输出8.n的交换中心4。为了简单起见，图1中只给出4个端口2.1-2.4,4个输入6.1-6.4，和4个输出8.1-8.4。端口2.n组成交换设备的外部接口。多个用户终端可以连接到每个端口上。

每个端口2.n分别通过两个方向相反的传输信道10.n和12.n,连接到交换中心的对应输入6.n和输出8.n上。

作为例子，交换设备可以是协调型的交换机并且没有阻塞，即它可以同时连接输入和输出的任意组合。但是，本发明在交换设备的内部结构上没有任何特殊限制。

由于在输出端存在冲突，即当多个目的地为同一输出端口的信元被几乎同时发送到交换设备时，需要信元缓冲区用以避免信元损失。

依据本发明的一个重要特性，所有的信元缓冲区都分布在端口中。由于中心里没有信元缓冲区，必须采取特殊的措施避免信元的冲突。该措施为首先规划信元到达中心的时间，然后让它们进入，以此来避免在中心的输出上的冲突，以下将详细描述。

所有的端口都与信元同步工作，信元以相邻固定长间隔被发送，该间隔被称为发送周期。在信元等待它们各自的发送时间过程中，它们被保存在存储器单元中。在做为例子给出的系统中，假定信元具有某种形式的地址信息，该信息通过查找以比特图形式表示的内部路由信息表被收集和翻译，其中的比特的位置代表不同的输出端。这些从翻译表得到的图被称为标记，它是被大家所接受的概述。在已知的系统中，标记和它们对应的信元一起发送，而在依据本发明的系统中，标记和对应的信元是分开的。

图2大略地说明一个带有信元目的地比特图的标记14，它包括4个域14.1-14.4，它们在给出的很简单的例子中可被想做与交换中心的4个列一一对应。每个域中有一个比特，该比特在例如置为1时，表明对应的信元要到达该列。

如下面将给出的详细描述，在每个发送周期，从每个2.n端口发送一个标记和一个信元，它们并不彼此相对应。标记有两个功能，向交换中心4提供路由信息和为对应的信元申请一个发送周期。中心4处理该请求并指定一个发送周期，表明端口2.n的一个信元发送时间。端口等待该时间点，然后在指定的发送周期内将信元发送出去。在等待期间内，其它请求和信元可以(由中心)被处理。

当在一个发送周期内收到标记时，规划所有提出请求的信元的过程被启动。所有标记和相应的规划信息都被存储，直到信元被发送出去。做为规划过程的结果，规划信息(所指定的发送周期)，在上述的发送周期紧接的发送周期内从中心4被发送到端口2.n。

图3大略地说明规划信息的格式，一般被表达为15。表达方式为二进制形式。所示的4个域中的后三个对应为比特b0,b1和b2,分别与一个三比特字的第一、第二和第三比特一一对应。零状态(所有的比特置为零)表明允许在确定的最小数目的发送周期延时量之后向中心发送。所有其它数目表示进一步的等待周期。例如，5表示信元应再被延时5个发送周期。在这段时间内，到达其它输出口的信元可以被发送。所示4个域中的第一域为有效信元标志16。当从中心4发送到端口2.n的信元是有效的，且为非空信元时，该标志被设为激活。

图4给出一个由标签18和有效负载20组成的信元17。标签只在交换端口中被翻译并可能被一高层协议操作。没有执行直接基于标签的内部路由寻找。

图5给出以下两个发送周期间的相位偏差dt，一个是有并不属于该信元的标记14的信元17的发送周期，方向为端口到中心，另一个是有对应于该标记的规划信息15的同一信元17的发送周期，以及参考图3中有效信元标志16，方向为中心到端口。

图6给出当信元被延时两个发送周期时的标记14和它的信元17的位置分布。在当前实施例中，这是确定的最小时延。

当各个信元依据规划信息15到达时，存储的标记14和规划信息用于建立信元和输出端口目的之间的对应关系。

通过一个无效标记向中心表示没有新的信元等待被规划。提供来自端口的每个标记，得到路由信息，该信息包含对指定一个发送周期的隐式请求。

规划设备在结构上由一些如图7-14所示的模块组成，它们依据图15相互连接。

规划设备由在图10中表示为21的输入端接收来自端口的标记，每个端口一个标记。这些标记包括路由信息和对发送周期的请求。

规划设备在一个发送周期期间处理来自各个端口的全部这样的请求。当请求一个接着一个地被处理时，想在一个发送周期期间找出不会发生冲突的多个输出发送周期变得越来越不可能。由于这个原因，改变了对每个发送周期处理请求的顺序，以在端口间达到公平。

规划设备处理对应于进入的第三到第六个发送周期内的全部标记。全部标记被存储在代表它们各自相对发送时间的存储器中。在每个发送周期过程中，全部标记被移入代表着更邻近的规划时间的存储器单元中。移出规划设备的标记被移入没有画出的FIFO(先入先出存储器)中，FIFO把标记延时两个发送周期，包括输出的第一和第二个发送周期。因此随时间的推移，存储器单元总能反映出当前的状态，并且相关的发送时间被改变。

存储器单元“串行输入”的输入值由属于最远发送周期的标记值组成，它被置为“未规划”(零)。上述FIFO的输出是一些交叉点之上的图，这些交叉点应在每个发送周期内被激活。

考虑到冲突的危险，每个到达的标记都要和前面已规划的标记进行核对。对于一个到达标记的全部处理操作同时进行。假定至少找到了一个不会发生冲突的输出发送周期，该标记被存到存储器单元中，这象征着最早的发送周期。

经过在一个入发送周期内对全部标记的完整处理过程之后，这些标记对应的一些或全部信元已经被规划好了。在处理过程中，它们各自的发送时间已被确定，并送到组织将这些规划信息(信元的发送时间)发送到端口的设备中去。

对一信元规划的失败可能会被表达为，例如告诉了一个比存储器单元可用数目大的相对发送时间，而不是一个正确的发送时间。

由一个控制电路做规划设备的输入电路，它如图7和15所示被一般以22表示。控制电路22包括一个状态机24，后者在图8中与附属的状态表26和状态图28一起给出详细表示。

控制电路22以下面将给出的详细描述的方式控制规划的过程和时间优先级。

参考状态表26，状态机24有4个空闲状态S05,S15,S25和S35，这时它对输入START上的到达初始信号是敏感的。当有到达标记时，每个发送周期内初始信号到达一次。然后状态机24执行计数操作(模4)，之后一个输出SH(用于移位)为激活的状态出现。随后下一个空闲状态出现。

在计数状态过程中，输出SC(用于规划)为激活。4个计数过程中的每一个有如状态表中所示的不同的初始值。

一个D触发器接收用于状态机24的初始信号，并在把信号送到状态机24的输入端START之前把它与一时钟信号K进行同步。时钟信号也输出到一个反相器32，产生一个反相时钟信号做为状态机24的时钟输入CLK。时钟信号同时送到一与门34的一个输入端上，与门的另一个输入端与到达的初始信号相连，这样门34的输出35为到达的标记提供一个同步锁定信号。

信号SH由一个反相器36(1比特解码器)进行解码。译码信号由信号SH和来自反相器36的输出组成。一个如所示方法连到状态机24的解码器38，在它的输入使能端出现激活信号时，激活它的4个输出Y0-Y3中的一个，在计数过程中就进行这样的动作。

优先级编码器40对在它的输入端P0-P3上激活的最高顺序输入信号进行编码。当它的输入端都没被激活时，它的输出使能端上的输出信号被置为0。一个如图中所示方式连到编码器40的解码器42与解码器38相同。优先级编码器40和解码器42一起组成一个只激活输出Y0-Y3中一个输出的模块，该唯一输出对应于被激活的最高级别输入。

图7所示控制电路的功能在下面对规划设备的描述及其与图9-15有关的功能中表现出来。

依据图10，在规划设备输入端43上到达的标记被保存在存储器44中。存储器的每行代表一特定端口2.n的一个标记，每一列代表到输出端口8.n之一的地址。标记被保存在D触发器存储器的行中并被锁定信号锁定，参照前面的描述该锁定信号由控制电路22中与门34的输出端35提供。存储器44的输出连接到一个数据交换设备的输入上，该设备在下面参考图11给出描述。

解码器38、42的输出信号被分别送到如图9所示的一个地址模块50的行导线46和列导线48，它用于为一存储器产生规划数据的锁定脉冲，这将在下面参照图12和13给出更详尽的描述。与门52的各个输入分别与行导线和列导线46和48相连，于是各个信号-分别对每个解码器38和42的激活信号-的组合就这样激活了这些与门之一的输出。模块50也包含或门54，其中它的一个输入连到对应的与门52的输出，另一个输入连到控制电路22的移位输出端。

当控制电路22的移位端被激活时，或门54的输出都被激活。任何像移信号或到一与门52的解码器信号为激活时，连到这个特定与门52的或门54的输出将因此被激活。或门54的输出被连到各个与门56的输入端。每个与门56的另一个输入被连接用于接收时钟信号K，它的输出组成地址模块50的输出58中的一个，因此地址模块上出现的信号是与时钟同步的。

地址模块50为标记存储器60的存储器单元或所有的存储器单元提供定时，前者在下面给出更详尽描述，它用于存储进行规划的请求(图13)，体现一特定的输入端口和输出发送周期。

图11中所示的数据交换设备，如上面所提到的，具有连接到存储器44输出端的输入64，并且它的控制输入端66、68、70、72连到解码器38的输出端。当附属的控制输入端66、68、70、72被激活时，数据交换设备62发送一个来自存储器44的标记到它的输出端73上。

图12给出具有一个触发器75和一个由与门76,77和或门78组成的输入交换设备的模块。控制输入端80和82和门76,77各自的一个输入端相连。当控制输入端80,82中的一个被激活并且触发器75被定时的时候，与被激活的控制输入端相对应的数据输入端上的数据被锁定并放到触发器75的输出端84上。

在图13所示的存储器60中包括了一组图12给出的这种模块74，该存储器用于存储规划请求。组中的每一行可以接收一个标记。

图14给出一个冲突控制电路的实例。冲突控制电路通过与已规划标记存储器中对应的实例相对比，每次检查一个到达标记存储器中的标记。

参考图14，图11所示的数据交换设备的输出被连接到4个冲突检查模块86中每一个的输入上。已被挑选出的标记的比特被送到每个冲突检查模块中与非门88,90,92,94的一个输入上。参考图13，每个冲突检查模块也和用于规划请求的4个标记存储器60中对应的那一个相连。存储器60的全部行与列输出96被行方向连接到或非门98,100,102,104，并且列方向连到或门106,108,110,112。或非门98,100,102,104在它们各自行上的任一比特置0时，会将它们的输出设置为0。其中一列通过与门114,116,118,120，连接到一个或门122，或门122的输出连到与门124的5个输入中的一个上。当或门106,108,110,112各自列上的任一比特置为1时，它们的输出置为1。与非门88,90,92,94各自的另一个输入端分别连到或门106,108,110和112各自的输出端上。因此，当与非门88,90,92,94各自从输入85上收到的标记值和从对应的或门106-112收到的列上的比特中的任一置为1时，与非门88,90,92,94的输出被置为0。与非门88,90,92,9488,90,92,94的输出形成与门124的其它输入中的每一个。因此，当连过来的行中没有比特被置1，并且在输入85上的标记比特在与标记存储器中比特置1的相同列上不为1时，与门124的输出被置为1。然后一个到达的标记有可能被放到用于规划请求的存储器60中，该过程见如下所述。

全部与门124的输出连到控制电路22的优先级编码器40上，因此，优先级编码器的那些输入P0-P3可被置为1，这对应于信元可以成功地被规划的发送周期。优先级编码器40将最高顺序输入编成一个二进制(2比特)字和一个使能信号。优先级编码器40的输出形成了最早的输出发送周期(如果有一个的话)，对于将被规划的信元不会导致信元冲突。优先级编码器40的全部输出连到编码器42的输入和没有画出的触发器，和一个安排发送规划信息到端口的设备上。编码器42的输出连接到地址模块50的列选择输入上，每个输出对应一列。地址模块的列因此代表输出发送周期。

被处理的一行中的到达标记被送到用于已规划请求的全部标记存储器60的输入端，但来自地址模块50的一个锁定脉冲只到达在标记存储器中的存储器单元，后者代表发出已处理的请求信息的端口和一个输出发送周期，在此周期内不会发生冲突，通过这种方法标记只被计入这个存储器单元。

在移位(Shift)被激活状态出现时，包含反相器36的解码器将使图12模块中所包括的输入选择器来选择其它数据输入。这些输入和输出84以这种方式连接，使得当触发器被计时对可以执行数据移位。

在每个端口2.n中有一个图16所示类型的延时装置。当等待来自规划设备的规划信息时，来自系统外的信元被暂时地存在端口中没画出的一个信元缓冲区里。这个信元被送到进一步延时信元的延时装置所包含的全部模块130中的“信元入”输入端上，但只保存在模块130中的D触发器152中，它的输入“存储”置为1。基于来自中心被看做输入“规划信息”的这一规划信息，该信元在输出端于发送时刻被显示为“信元出”，在该时刻内信元应被发送到端口，此过程在下面给出更详尽的描述。

上面提到种类的模块在图17中也给出了更详细的表示，其中包含状态机132和对应的一个状态图130，一个状态变化条件列表134和状态表135在图18中给出表示。

每个模块130有一个“空闲”输出端，当把它置为1时，表明对应的缓冲区可以存储一个新的信元。来自模块130的这些输出分别地提供给优先级编码器136的P0,P1和P2输入端。优先级编码器136有一个输出端EN(用于使能)，以图16中所示的方式连到一个与门138的输入端，而该与门的另一输入端用于接收一个标志-“有效源信元标志”。当置为1时，该标志表明从系统之外收到的信元不是一个空信元。与门138的输出连到解码器140的输入端EN(用于使能)。当与门的两个输入端置1，即当“有效源信元标志”和至少P0,P1或P2中的一个被置1时才这样，与门138的输出置为1。从而解码器140的输出Y0,Y1或Y2中的某几个也被置1，对应于被优先级编码器136的输入P0,P1和P2激活的最高顺序输入。这将导致输入“存储”端置为1的某个模块130的信元缓冲区141被装载该信元，并且在从同一模块所收到的规划信息的指导下，它在发送周期内出现在信元缓冲区的输出端“信元出”，在上述周期内信元应被送到端口。由于在同一时间内只有一个缓冲区的输出设为1，因此通过或门142，信元被送到延时装置的输出端144。

在每个模块130中，为把信元从信元缓冲区141中在正确的发送周期内发送出去所包括的装置是状态机132，它在输出“锁存”处提供了一个锁存信号，对规划信息中指出的发送周期的数目进行计数，它被在输入端“规划信息”上收到，状态机还在执行计数时，在输出“发送”端提供了一个读出信号。

图18中的状态图133给出了当状态机计数时出现的状态及状态迁移。状态S00是空闲状态，在该状态信元已被发出而且没有新的信元要存在信元缓冲区里。状态S10与在紧接的下一个发送周期内读出信元有关，而其中S20,S30和S40与在计数后向外读出操作有关。

包括状态变化条件的表134给出其它的状态迁移。对于空闲状态S00，状态机可从S00(相同的状态)，S10,S20,S30或S40处发出而到达它。对于S10,S21,S32和S43，状态机可以从其它状态或者本状态S10(相同的状态)，S20,S30或S40出发而到达它。如果信元将在紧接的发送周期内被发送出去，状态机到达S10状态；而当信元将被延时更多的发送周期时，状态机到达S21,S32和S43状态。

在状态表135中，输出的情形被表示成不同的状态。只有在S00状态，“空闲”被置为1。在S10,S21,S32和S43状态，“锁存”被置为1。在S10,S20,S30和S40状态，“发送”被置为1。

为了得到状态机132的反相时钟，时钟信号通过一个反相器146被送到“时钟”端。

与门148和D触发器150分别连接到状态机132的“锁存”和“发送”两个输出端上。时钟信号也连到与门148的另一个输入和D触发器150的时钟输入端，从而获得“锁存”和“发送”输出端信号与时钟的同步。与门148的输出连接到D触发器152.1-152.n的各个时钟输入端，这些D触发器组成了信元缓冲区141，且它们的数据输入端口D被连接到模块130的“信元入”输入端。

来自D触发器150的输出信号连接到与门154.1-154.n的一个输入上，与门的另一个输入连接到D触发器152.1-152.n的各个输出上。与门154的输出连接到模块130的“信元出”输出端。这样信元缓冲区141的定时通过与门148被“锁存”信号控制，把信元送到模块130的“信元出”输出端是通过D触发器150由信号“发送”控制。

时钟脉冲同步到达，并且和送出发送周期相位一致。对于信元在与规划信息相同的发送周期内的到达，它和“存储”端在状态机被计时的时刻上必须是稳定的。

图19中给出了一个用于演示本系统允许动作的连接情形举例。图中给出5个端口到中心和中心到端口完整的连续发送周期，并且在下面给予说明。

对于说明图19中的标记、信元和规划信息，这里使用的概念和说明符与图2-6中给出并进行描述的概念等相同。相互连接的标记、信元和规划信息的不同组一方面由附加的不同小写字母来区分，尽管小写字母对标记、信元和规划信息而言都一样，但它们被放在各自的说明符之后，另一方面可以通过图中不同的符号线来区分。

每个标记由一个具有4个同等大小矩形区域的序列来说明，各个区域对应于图2中的区域14.1-14.4，它表示一个比特。对于规划信息也是一样，它的几个域对应于图3中的域16,b2,b1,b0。每个信元照图5中的说明方法，用一个横向的斜切矩形表示。

行A1和A2分别代表端口到中心和中心到端口的一个发送周期，它们分别与第一个端口相关，可以被想象为与图1中的端口2.1相对应。行B1和B2,C1和C2,D1和D2也一样，它们分别与端口2.2,2.3和2.4相对应。

在第一个发送周期期间，如行A1上所见的，从端口1发送了标记14a到中心。和标记14a在一起同时发送了信元17，它如前所述并不属于标记14a。标记14a表示了一个发送信元到端口3的请求，这需要将它的第三个比特(14.3)置为1，被表达为该域内有符号线。由于其它发送信元到端口3的请求没有出现，属于标记14a的信元17a被规划为一确定的最小延时，如行A2中所见，通过在发送周期2内从中心到端口的规划信息15a表示(全部比特，b2,b1和b0都置为0)。在举例的系统中，最小确定延时为2个发送周期。如图行A1所示，端口1收到规划信息15a，对应地在发送周期3内发送信元17a到中心。在行C2中，中心在发送周期3内，在中心到端口3的方向上表明信元17a是有效的，如标志16a所示。在相同的发送周期内，中心以最小的进一步时延并且实际上无缓冲地发送信元17a到端口3。

在行B1,C1和C3上，三个标记14b,14c和14d分别地在发送周期1内被发送到中心，如各自的第一个域所示(图2中14.1)它们具有冲突的信元目的端口1。端口3的标记14c表明所隶属的信元有多个目的地，即除包括端口1还包括端口4(图2中的域14.1和14.4)。

中心内部的冲突处理算法已经给对应于标记14b,14c和14d，来自端口，3和4，共同到达端口1的各个信元指定了不同的发送时间。根据例子中的状态机24的状态，参看行C2中的规划信息15c，来自端口3的标记14b在中心中将被第一个处理，因此它拥有最早的发送时间，随后是端口4和端口2。参看到中心方向的行C1和到各个端口方向的行A2和D2，来自端口3的信元17c于是在发送周期3内被送到端口1和4。参看行D1，信元17d和并不属于它的标记从端口4被发送到中心，再参看行A2，从中心在发送周期4内发送到端口1。参看行B1，信元14b和并不属于它的标记从端口2被发送到中心，从那里在发送周期5内被发送到端口1。

在目的为端口1，来自端口4被规划的信元17d等待着被进一步发送时，来自端口4目的为端口3的一个新信元17e被规划。参看行D1和C2，由于早先来自端口4已被规划的信元将在发送周期4内被再发送，信元17e被指定了发送周期5。在目的为端口1来自端口2已被规划的信元17b等待着再被发送时，参看行B1和C2，从端口2到端口3规划并再发送了另一个信元17f。

Claims (13)

1．信元交换设备包括多元交换端口(2.n)，每个端口连接着许多用户终端，用于发送和接收上述用户终端的信元，该信元包括有效负载和地址信息；一个交换中心(4)，和上述交换端相互连接使得它们之间能够通信；交换端口中的标记装置，它基于从用户终端收到的信元(17)中包含的上述地址信息，产生属于该信元的标记，该标记中包括能使信元通过交换中心的路由信息；

另外还包括在对应的信元之前，把标记送到交换中心的装置，信元与标记一一对应；

交换中心里的规划装置，它用于接收上述预先发送的标记，并基于其中包含的上述路由信息，产生有关来自交换端口各个信元的发送时间的规划信息，规划结果使得在这些发送时间内，信元可以在不与其它信元发生冲突的情况下被送到目的端口；

发送上述规划信息到信元发起交换端口的装置；

在交换端口中保存信元的装置，一直保存到信元各自的发送时间到达；

以及在信元各自的规划的发送时间内，将信元送到交换中心的装置。

2．为信元寻找通过信元交换设备的路由的方法包括：通过每个都连接到许多用户终端的多元交换端口，发送和接收上述用户终端的包括有效负载和地址信息信元；

将一个交换中心与上述交换端口相互连接，使得它们之间可以通信；

上述方法包括以下步骤：基于收到信元的上述地址信息，为每个收到的信元产生各自的标记，标记中包含能使信元通过中心到达所希望的目的端口的路由信息；

在对应的信元之前将上述标记发送到交换中心；

基于上述预先发送的标记中所包含的上述路由信息，产生有关来自端口各个信元的发送时间的规划信息，规划结果使得在这些发送时间内，信元能够在不与其它信元发生冲突的情况下被发送到目的端口；

通过发起端口发送上述规划信息；

在端口中保存信元直到它们各自的发送时间到达；以及在信元各自的规划发送时间内将信元送到中心。

3．按照权利要求2的方法，包括以下步骤，即在不同的发送周期内，将标记和对应的信元从相应的端口发送到中心。

4．按照权利要求3的方法，包括以下步骤，即在发送标记的发送周期和发送对应信元的发送周期之间提供一发送周期最小倍数的时间延时，该延时为避免冲突的处理过程所必须。

5．按照权利要求3或4的方法，包括以下步骤，即在每个发送周期内，将一个已规划的信元和一个尚未规划信元的标记一起从端口发送到中心。

6．按照权利要求2-4中任一个的方法，包括以下步骤，将一个信元和它后面信元的规划信息及有效信元标志一起从中心送到端口。

7．按照权利要求6的方法，包括以下步骤，即通过一个无效标记向中心表示没有新的信元等待被规划。

8．按照权利要求7中任一个的方法，包括以下步骤，即提供来自端口的每个标记，得到路由信息，该信息包含对指定一个发送周期的隐式请求。

9．按照权利要求8的方法，包括以下步骤，在一个发送周期期间处理所有上述请求，每次处理一个，对每个发送周期改变这种处理的次序，以在端口之间达到公平。

10．按照权利要求8或9的方法，包括以下步骤，即保存所有属于已规划信元的标记。

11．按照权利要求10的方法，包括以下各步骤，将所有标记存贮在能够隐含表明它们对应信元的相对发送时间的存储器单元中，对于每个新的发送周期，将所有标记移到新的存储器单元中，该单元代表更近的发送时间，从而标志一直被保存在能够反映相对发送时间的存储器单元中。

12．按照权利要求2-4,7,8,11的方法，包括以下步骤，即考虑到冲突的危险，将每个到达中心的标记与早先已规划的信元的标记并行进行检查。

13．按照权利要求12的方法，包括以下步骤，即通过说明比存储单元现有数目大的相对的信元发送时间来表示一次失败的信元规划。

Images