具有时间片调度装置的高速异步传送方式包交换网络系统

摘要

异步传送方式的交换网络系统将存储在包缓冲装置(201到20n)的包传给由包指定的输出端口(241到24m)，而时间片调度装置(25)当包到达包缓冲装置时将时间片分配给存储于包缓冲装置的这些包以防在空分交换装置(23)中发生包冲突，每个包缓冲装置顺序地将新包写入各自存储单元中，但在由时间片调度装置分配的时间片中随机地读出这些新包，使空分交换装置吞吐量得以提高。

说明书

本发明涉及异步传送方式包交换网络系统，更准确地说，涉及装入异步传送方式的包交换网络系统中旨在提高包的吞吐量的时间片调度装置。

对各种数字数据例如数字声音数据及数字图象数据已形成的数据通信来说，异步传送方式的包交换网络系统颇有吸引力。异步传送方式包交换网络系统需防止包发生冲突，并且通常备有包缓冲器。已提出各种网络系统，并可按包缓冲器所处位置进行分类。以大规模高速数据通信观点来看，异步传送方式包交换网络在空分交换装置前提供包缓冲器是合乎要求的，图1示出在空分交换装置前装有包缓冲器类型的异步传送方式包交换网络的典型实例。

参考附图1，包缓冲器11到1n分别指定输入端口21到2n，一系列的包构成了分布在包缓冲器11到1n中的各个对列。包缓冲器11到1n并行地耦合到空分交换装置3，而输出端口41到4m和空分交换装置3相关连。包缓冲器11到1n按先进先出（FIFO）原则工作，对列首部的各个包通过各个内部输入链路51到5n从包缓冲器11到1n供给空分交换装置3。该空分交换装置3将这些包分配给输出端口41到4m。然而，如有多个包导入输出端口41到4m中任一个，则由竞争调解装置（contentionresolution  unit）6防止包发生冲突。

详细地说，在输出对列首部包之前，每个包缓冲器11到1n与竞争调解装置6进行通信以便决定是否允许该包的输出。因此，包缓冲器11到1n通过与各个允许信号线81到8n配对的询问信号线71到7n耦合到竞争调解装置6。如多个包被导向输出端口41到4m中任一个，则竞争调解装置6允许包缓冲器11到1n中的一个将该对列首部的包供给空分交换装置3，以响应同时通过询问信号线71到7n的询问请求，但其它的包缓冲器则等待直到竞争解调装置6允许。

该空分交换装置3是由诸如Batcher-Banyan交换网络的非阻塞自选路由的交换网络实现的，而竞争调解装置6用自选路由交换网络构成。

然而，这样构造的先有技术的异步传送方式网络系统吞吐量低。这是由于这样的事实，即，迫使与另一前端包冲突的前端包的后面的包也等待，虽然该包指定的输出端口并不忙。事实上，在例如以M/D/1模型表示随机到达的情况下，先有技术的异步传送方式网络系统达到大约58%的吞吐量。该问题称为“线头阻塞”（“head  of  line  blocking”）现象。

对线头阻塞现象已提出各种解决办法，顺序仲裁法可有效对付线头阻塞现象（参见Proceeding  of  the  1989  National  Spring  Conference  of  Communications，B-385中的文章“ATM交换系统的评价”）。即，将从各队列取出的一些包顺序地与另一队列的包进行比较并进行仲裁。这种顺序仲裁很容易找到不忙的输出端口并将该不忙输出端口分配给导向该端口的包。由于这个原因，顺序仲裁法提高了空分交换装置3的吞吐量并可在包缓冲器11到1n输出之前执行。如果按照与内部输出链路一起的保留表安排内部输入链路，那么可将包有效地分配给不忙的输入及输出链路。在“输入缓冲器的时间保留控制技术的分析”（Proceedings  of  the  1989  National  Spring  Conference  of  Comm.B-437）一文中提出这种保留表。

然而，先有技术的顺序仲裁并不能极大地提高空分交换装置的吞吐量。实际上，前者可达大约70%吞吐量，而后者可将吞吐量增到大约85%。如包以高于最大吞吐量的速率到达输入端口21到2n，在包缓冲器11到1n会发生溢出，相应地，其中有些数据信息会丢失。吞吐量饱和在70%-85%的原因是竞争调解装置6仅对队列前端位置的包间的冲突进行仲裁。如果前端位置的所有包都导向输出端口41到4m中的一个，则其它输出端口保持空闲，即使指向该端口的包就在处于前端位置的包之后。

如对包缓冲器11到1n的所有包进行仲裁，则输出端口41到4m可始终保持忙碌，因此，可极大地提高吞吐量。但是，异步传送方式的网络对150Mbps链路上各由53字节组成的包要达到高速包交换，因此，目前没有现成的技术可对包缓冲器中全部的包进行仲裁。

因此，本发明的重要目的是提供一种可提高安装其中的空分交换装置吞吐量的异步传送方式的交换网络系统。

为实现这些目的，本发明提供对包缓冲器的包指定各个时间片而不发生目的地冲突的方法。

按照本发明，提供了异步传送方式的交换网络系统，它包含：a）多个输入端口，每个端口供有一串包，每个包有一表征目的地的端口地址信息;b）分别与输入端口耦合的多个包缓冲器，每个包缓冲器有多个存储单元分别用于存储由相关输入端口馈给的包;c）各作为目的地的多个输出端口;d）耦合在包缓冲装置和输出端口之间的空分交换装置，该装置提供多个信号路径，每个路径将包缓冲装置中的一个耦合到由前述一个包缓冲装置馈给的各个包中所含端口地址信息所指定的一个输出端口;以及e）时间片调度装置，该调度装置当一个包达一个前述一个包缓冲装置时响应由一个包缓冲装置馈给的时间片请求信号，将一时间片指定信号供给前述一个包缓冲装置，该时间片指定信号指出为最早时间片指定的从到达开始的时间延迟量，而使得在前述一个包和由其它包缓冲装置在最早时间片提供给空分交换装置的包之间不会发生目的地冲突，其中，所述一个包缓冲装置将前述一个包在最早时间片内提供给空分交换装置。

结合附图和以下描述，本发明的异步传送方式的交换网络系统的特点及优点将更易理解，附图中：

图1是示出先有技术异步传送方式交换网络系统结构的框图;

图2是示出本发明的异步传送方式交换网络系统结构的框图;

图3是示出包格式的图;

图4是装在异步传送方式交换网络系统中包缓冲器一般结构的框图;

图5是示出包缓冲装置细节电路结构的框图;

图6是示出装在异步传送方式交换网络系统中的时间片调度装置电路结构的框图;

图7是示出装在时间片调度装置中调度存储器结构的电路图;

图8是示出装在时间片调度装置中时间片判决电路结构的电路图;

图9A和9B是示出本发明异步传送方式交换系统网络的总的电路性能的时序图;

图10是以平均时间延迟示出的异步传送方式交换网络系统吞吐量的图。

参考附图2，多个包缓冲装置201到20n并行耦合到输入端口211到21n，从各个输入端口211到21n将包顺序供给相关连包缓冲装置201，……或20n。以这样方式顺序馈给包缓冲装置201到20n中每一个的这些包分别形成至各装置的一个队列。包缓冲装置201到20n通过内部输入链路221到22n耦合到空分交换装置23，而在相关空分交换装置23中装有多个输出端口241到24m。将多达n×m个的多个分量交换元件装在空分交换装置中，这些交换元件是自寻路由的空间开关，例如Batchen-Banyan开关。将来自各个包缓冲装置201到20n的包通过内部输入链路221到22n供给空分交换装置23，而该空分交换装置23将包分配到输出端口241到24m，在目的地和指向的输出端口之间没发生竞争。

为防止包冲突，提供了与包缓冲装置201到20n相关连的时间片调度装置25，而包缓冲装置201到20n和时间片调度装置25通过第一多位总线系统26和第二多位总线系统27进行耦合。通过同步信号线SYNC将同步信号供给所有部分装置，即包缓冲装置201到20n，空分交换装置23和时间片调度装置25，而系统时钟信号线CLK将系统时钟信号传给所有部分装置201到20n，23和25。同步信号及系统时钟形成了全部部件装置201到20n、23和25之间的同步控制。

包格式如图3所示，每个包有三个域FH、PH和DF。第一域VF包含用于指出包有效性标志的最高位MSB。第二域PF分配有指出输出端口241到24m中之一的一个为该包所指向的端口的地址位，而第三域DF用于指出例如一个声音信息、一个图象信息或一二进制数的数据位。下文将第一和第二域称为“包首部PH”。尽管包首部PH通常包含指示逻辑地址的地址位、优先级位等等，但这些位和本发明的要领不直接相关，因此，下文不再给出其进一步说明。

周期地将同步信号供给部件装置201到20n、23和25，该同步信号确定了时间片。将一串时间片分别分配给包缓冲装置201到20n，而各个包缓冲装置201到20n一旦有新包到达时就通过第一总线系统26发送时间片请求信号。该多位时间片请求信号表示新包的包首部PH中所存储的信息，而时间片调度装置25通过第二总线系统27将指示从当前时刻开始的时间延迟量的时间片分配信号提供给包缓冲装置。该时间延迟量将该包分配到可防止该包产生不希望冲突的最早时间片中。利用由时间片调度装置25馈给的时间片指定信号，包缓冲装置推迟包的输出直到调度装置25指定的时间片到来，然后将该包发送到空分交换装置3。该空分交换装置3构成了内部输入链路与按照该包中第二域PF与指定输出端口耦合的一个输出链路之间的信号路径，然后，该包发送到指定的输出端口。

1.包缓冲装置

所有包缓冲装置201到20n电路结构彼此相同，该包缓冲装置201的电路结构示如图4。该包缓冲装置201的电路结构示如图4。该包缓冲装置201大致包含包存储器201a，和包存储器201a关连的第一和第二计数电路201b和201c，控制存储器201d，和该控制存储器201d关连的第三计数电路201e，而加法器201f也与控制存储器201d相连。将由输入端口211供给的包按照存储第一写入地址的顺序递增的第一计数电路201b顺序写入包存储器201a，该第一写入地址便包存储器201a顺序存储例如从最左块到最右块的包。包存储器201a的每个块代表指定一地址的存储单元，该地址在写入操作中称为“第一写入地址”而在读出操作时称为“第一读出地址”。当一个包到达时只将其包首部PH传送给第一总线系统26，请求时间片调度装置25（如以下“时间片调度装置”一节中详细说明那样）分配一时间片。

将这样顺序存储在包存储器201a中的包按照存储有第一读出地址的第二计数电路201c以随机方式读出到内部输入链路221。从控制存储器201d将第一读出地址供给第二计数电路201c，而第一读出地址寻址存储在包存储器201a中的任一包。第一读出地址按由加法器201f馈给的第二写入地址以随机方式存储在控制存储器201d中，例如，按照指定控制存储器201d中的一块的第三计数器201e，从最左块到最右块顺序读出所述第一读出地址。控制存储器201d中的每一块代表指定一地址的存储单元，与包存储器201a相同。控制存储器201d中的每一块的地址在写入操作时称为“第二写入地址，在读出操作时称为“第二读出地址”。第二读出地址由加法器201f根据第三计数电路201e中的第二写入地址和指示延迟时间量或从第二写入地址偏移量的时间片分配信号产生。这样构造的包存储器201a和控制存储器201d的组合，由于时间片调度装置25在决定时间延迟量和偏移量之前已考虑过先供给包缓冲装置201到20n的所有包，所以可对存储在包缓冲装置201到20n存储的所有包进行全局仲裁。

包存储器201a、控制存储器201d和计数电路201b、201c和201e构造如图5所示。包存储器201a具有耦合在相连输入端口211和第一总线系统26之间的双端口接口201g，而双端口随机存取存储器201h其数据输入端口DI耦合到相连输入端口211。该数据输入端口DI与写入地址端口WA相连，而该写入地址端口WA耦合到第一计数电路201b的计数器201i。该双端口随机存取存储器201h还有一与读出地址端口RA相连的数据输出端口DO，提供有系统时钟信号的选通端口STB。该读出地址端口RA耦合到第二计数电路201c，该随机存取存储器201h同时执行写入操作和读出操作。双端口接口201g响应同步信号并在对系统时钟的预定数进行计数时将包首部供给第一总线系统26。装在各个包缓冲装置中的接口201g指定一不同于其它接口的预定的数，因此在第一总线系统上不会发生冲突。

控制存储器201d也包含耦合到第二总线系统27的接口201j，而双端口随机存取存储器201k有一与写入地址端口WA相连的数据输入端口DI，而该数据输入端口DI耦合到第一计数电路201b的寄存器201l，该计数电路201b接着耦合到计数器201i。寄存器201l响应同步信号并锁存其中的第一写入地址。这样，第一写入地址存储在寄存器201l中，然后作为存储其中的第一读出地址提供给随机存取存储器201k的数据输入端口DI。第三计数电路201e记录第二读出地址并由同步信号递增i，因此，该第二读出地址允许随机存取存储器201k顺序将第一读出地址提供给第二计数电路201c。该第二计数电路201c响应系统时钟信号并递增第一读出信号直至同步信号允许下一个第一读出地址从第三计数电路201e指定的随机存取存储器201k的下一块中送出。然后，将一个包中各位顺序从随机存取存储器201h读出到内部输入链路221。如前文所述，第一写入地址作为第一读出地址存储在随机存取存储器201k中由加法器指定一个块存放从寄存器201l送来的第一读出地址。即，加法器201f有两输入端口，其中之一耦合到第三计数器201e而另一个耦合到接口201j。接口201j作用类似接口201g，对同步信号和系统时钟信号响应以便确定时间片指定信号抵达目的地而无任何混乱。接口201j将时间片指定信号传送给加法器201f中的一个输入端口，而该时间片指定信号代表时间延迟量或距离第二读出地址的偏移量。时间延迟量或偏离量等效于若干时间片，在这些时间片之后包可从随机存取存储器件201h中无冲突地读出。然后，加法器201f通过将偏离量加到第二读出地址来产生第二写入地址。由于第三计数电路201e允许在过了延迟时间周期时将第一读出地址从随机存取存储器201K中读出到第二计数电路201c，所以从随机存取存储器201k在设有任何冲突的最早时间片内将包送到内部输入链路221。由于时间片分配信号指出包到达包缓冲电路到交付该包之间的时间片个数，包存储器201a和控制存储器201d中每一个都需要具有和当前时间片与具有最大时间延迟的时间片之间的时间片同样多的存储单元。

2.时间片调度装置

参见附图6，详细示出了时间片调度装置25。该时间片调度装置25包含调度存储器25，译码电路25b和25c，计数电路25d和25e，反相电路25f、时间片判决电路25g、编码电路25h和减法器25i。在该例中，计数电路25d和译码电路25b作为一整体构成包缓冲器识别装置，而编码电路25h和减法器25i组合构成时间片分配装置。计数电路25e用作标准时间信号产生装置，而译码电路25c作为输出端口识别装置。

计数电路25d有一耦合到同步信号线SYNC的复位结点RST，该计数电路由系统时钟信号递增。该计数电路25d的输出信号从其输出端口Q馈给译码电路25b，该译码电路在最高位MSB出现逻辑“1”电平时产生指出包缓冲装置201到20n中一个的输入位映象信号B1到Bn。由于包缓冲装置顺序将各自时间片请求信号与系统时钟信号同步地供给第一总线系统26，该译码电路25b也顺序指定包缓冲电路201到20n，而译码电路25c在最高位MSB存在逻辑“1”电平时产生输出位映象信号Bn+1到Bn+m。例如，如果包缓冲装置201接收到一个其包首部PH指向输出端口241的包，则译码电路25b产生位串为（100……0）的输入位映象信号B1到Bn，而译码电路25c对包首部PH译码产生位串（100……0）的输出位映象信号。然而，如最高位MSB为逻辑“0”电平，输入位映象信号和输出位映象信号有一由“0”位组成的位串。将输入位映象信号和输出位映象信号供给调度存储器25a，该调度存储器25a的电路结构详细如图7所示。计数电路25e响应递增指示当前时间或当前产生的时间片的计数值的同步信号。将该计数值供给时间片判决电路25g、以及减法器25i、而标准时间信号TS表示计数电路25e的计数值。参考图8，下文作详细说明。

参见附图7，调度存储器25a包含：多个存储单元M11，M1（n+m），M11和M1（n+m）形成多个（n+m）行1列的阵列耦合到存储单元M11到M1

（n+m）的多个位线对BL1到BL（n+m），多个分别耦合到位线对BL1到BLn+m的预充电电路和列选择器组合电路PR1到PRn+m，以各自两反相端分别耦合到位线对BL1到BLn+m的多个写入电路WR1到WRn  m，耦合到系统时钟线CLK以产生互衬的系统时钟信号的反相电路INV70，耦合到存储单元M11到M1（n+m）的各行的多条字线W1到W1，多个字线驱动电路DRV1到DRV1，与存储单元M11到M1（n+m）各行相连的多个状态传感电路SS1到SS1。存储单元M11到M1（n+m）的行耦合到各报告线RPT1到RPT1，而报告线RPT1到RPT1分别将存储单元中存储的数据位传播到状态传感电路SS1到SS1。每个预充电电路和列选择器的组合电路下文简单称为“组合电路”。所有存储单元M11到M1（n+m）彼此类似，而预充电电路PR1和写入电路WR1分别类似于其余的预充电电路和其余的写入电路的电路结构。因此，为避免重复只说明预充电电路PR1、存储单元M11和写入电路MR1。

组合电路PR1包含一串耦合在相连位线对BL1的各位线之间的平衡晶体管BLN71和BLN72以平衡其间电压电平，用于在逻辑“1”电平的位B1与逻辑“1”电平的系统时钟信号共同出现时产生选择信号的“与”门AD71。存储单元M11包含反相器电路INV71和INV72构成的存储器回路，耦合在位线对BL1和反相电路INV71和INV72构成的存储回路之间并由字线W1选通的开关晶体管SW71和SW72，以及一串耦合在相连报告RPT1和负电压电平源之间的场效应晶体管FET71和FET72的串联组合。场效应晶体管其栅极耦合到存储回路的存储结点N71，在存储结点N71出现逻辑“1”位时导通。组合电路PR1到PRn+m分别耦合到列选择线SE1到SEn+m，而列选择线SE1到SEn+m传送这些选择信号。列选择线SE1耦合到场效应晶体管FET72，因此，场效应晶体管FET72在选择信号线SE1上出现选择信号时导通。状态传感电路SS1有一耦合在正电压电平Vdd源与报告线RPT1及反相电路INV731之间的充电晶体管CH711。该充电晶体管CH711由系统时钟信号线CLK选通并对报告线RPT1充电。如存储结点N71存储逻辑“1”位，那么当选择信号线SE1上出现选择信号时，报告线RPT1通过场效应晶体管FET71和FET72的串联组合进行放电。但是，存储器结点N71的逻辑“0”电位允许报告线RPT1保持充电状态。在该例中，存储器结点的逻辑“1”的位表示一保留状态，逻辑“0”位表示非保留状态。如前文所述，当包缓冲装置201到20n中的一个将一包的包首部PH发送给时间片调度装置25时，译码电路25b和25c产生输入位映象信号和输出位映象信号，这些位映象信号分别具有指出包缓冲装置和输出端口241到24n中之一的逻辑“1”的位。包含在位映象信号中的逻辑“1”位使两个组合电路的“与”门在系统时钟信号为逻辑“1”电平时导出选择线SE1到SEn+m上的选择信号。仅当未保留状态同时存储在对应于请求时间片的包缓冲装置和该包首部PH指定的输入端口的两个存储单元中时，该报告线保持在预充电状态。相连反相电路INV731、……或INV731根据报告线的已充电状态，产生有效逻辑“0”电平的命中信号HIT1，……或HIT1。如果包缓冲装置和输出端口的组合未存储在多于一行的存储单元M11到M1（n+m）中，则有一个以上的状态传感电路SS1到SS1产生出命出信号。

由状态传感电路SS1到SS1将命中信号（一个或多个）送到时间片判定电路25g，如图6所见，参考图8下面将对时间片判定电路25g作详细说明。存储单元M11到M1（n+m）各行分别对应于一串时间片，而一个以上的命中信号意指多于一个的时间片可利用。但是，只有存储单元M11到M1（n+m）中的一行由相连字线驱动电路DRV1…或DRV1所激活，而该激活行的存储单元通过与对应于请求时间片的包缓冲装置和包首部PH指定的输出端口的列相连的写入电路存储该保留状态。这意味着一个时间片为到达包缓冲装置的新包所保留。该保留将在下文详细描述。

参见附图8，时间片判定电路25g包含译码电路DEC81、多个互斥电路Ex1、Ex2，……Exh……和Ex1。将标准时间信号TS供给译码电路DEC81，该电路用指定信号TOP1到TOP1指定互斥电路Ex1到Ex1中的一个，而指定信号TOP1到TOP1中的一位降至有效指定的逻辑“0”电平。

所有互斥电路Ex1到Ex1在电路结构上彼此相同，只对互斥电路Ex1加以说明。互斥电路Ex1包含两个“与非”门ND81和ND82，两个反相电路INV81和INV82，3个“与”门AD81、AD82和AD83以及一个锁存电路LT81。“与非”门ND81和ND82、“与”门AD81到AD83及反相电路INV81和INV82作为一整体构成一控制电路，而锁存电路LT81用作存储电路。

假设现在标准时间信号TS及相应指定信号指出存储单元M11到M1（n+m）的行对应于当前时间片，位TOP1为有效逻辑“0”电平，而“与非”门ND81给出逻辑“1”电平的输出信号而与其它输入位无关。如命中信号HIT1为有效逻辑“0”电平，反相电路INV81提供逻辑“1”电平的输出信号，而“与”门AD81写出一个分配信息指出刚提出请求的包被分配以当前时间片。在这种情形下，“与非”门ND82给出逻辑“0”电平的输出信号，并且，由此原因，其它互斥电路Ex2到Ex1不再响应命中信号，即使命中信号为有效逻辑“0”电平。但是，如果命中信号HIT1为无效逻辑“1”电平，则“与”门AD81不把分配信息写入锁存电路LT81，但“与非”门ND82将逻辑“1”电平的输出信号提供给下一互斥电路Ex2。如命中信号HIT2为有效低电压电平，则将分配信息存储在互斥电路Ex2中，而没有逻辑“1”电平的输出信号送至下一互斥电路。这样，将机会从一个互斥电路顺次转到下一互斥电路直至找到最早时间片。在互斥电路Ex1到Ex1中任一个中存储的分配信号允许输出信号GET1，GET2，……GETh……或GET1达到逻辑“1”电平，而其它保持逻辑“0”电平。由编码电路25h对逻辑“1”电平的输出信号编码，而将编码电路25h的输出信号供给减法器25i（见图6）以产生时间片分配信号。该分配信号仅给出所指定行的绝对位置，而减法器25i的减法导出所指定行相对于与当前时间片对应的行的相对位置。因此，该时间片分配信号指出从当前时刻的时间延迟量或从当前时间片的偏离量。

转回附图7，写入电路WR1包含耦合到选择线SE的寄存器RG71、4个“与”门AD72、AD73、AD74和AD75及一个写入缓冲电路BF。调度存储器25a与控制装置25j和位映象装置25k相连。控制装置25j产生包括刷新信号UPDATE的各种控制信号，而位映象装置将位映象信号D1到Dn+m提供给写入电路WR1到WRn+m。该位映象信号D1到Dn+m通常有一（0000……000）的位串，但也可能有用于将包限制到具体输出端口的另一种位串。

这样存储在互斥电路Ex1到Ex1中之一的锁存电路中的该分配信息还用于将选择信号线上的位组合存储到存储单元M11到M1（n+m）中的一行中。如前文所述，将该分配信息锁存在对应于当前时间片或最早时间片的互斥电路中，本描述假设该分配信息存储在互斥电路Ex1中。

当译码电路25b和25c中每一个将位B1到Bn或Bn+1到Bn+m中任一位移位到逻辑“1”电平，则这些逻辑“1”电平位使组合电路PR1到PRn+m中之一的“与”门AD71如前文所述产生逻辑“1”电平的选择信号。在以下描述中，假定译码电路25b和25c将位B₁和Bn+m移位到逻辑“1”电平。选择线SE1和SEn+m上的逻辑“1”信号存储在写入电路WR1和WRn+m的寄存器RG71中。在保留存储单元后，在每个时钟处通过驱动字线来执行刷新操作。但是，当存在与同步信号SYNC同步的刷新信号UPDATE时，对由位TOP1到TOP1之一指出的存储单元还执行重写操作。如刷新信号UPDATE升到逻辑“1”电平，互斥电路Ex1的锁存电路LT81的输出信号在指定信号的位TOP1为有效逻辑“0”电平时，被传送到相连的重写控制信号线WD1、WD2、WDh和WD1之一。然后，从互斥电路Ex1的锁存电路LT81将逻辑“1”电平的输出信号通过“与”门AD83送到相连的重写控制线WD1。逻辑“1”电平的重写控制信号使相连驱动器DRV1将相连字线W1移位成有效电平，在逻辑“1”电平的互补的系统时钟信号出现时在位线对BL1到BLn+m和存储单元M11和M1（n+m）之间产生导通路径。

为简单起见，假定由位映象装置25k馈给的位映象信号具有由逻辑“1”位组成的位串，而写入电路WR1和WRn+m的“与”门AD72在当逻辑“1”电平的刷新信号UPDATE出现时产生逻辑“1”电平的各个输出信号，装在写入电路WR1和WRn+m中的寄存器RG71的输出信号允许“与”门AD73和AD75产生各个逻辑“1”电平的输出信号。由于“与”门AD74将逻辑“1”电平的各个输出信号在出现逻辑“1”电平的互补的系统时钟信号时送到写入电路WR1和WRn+m的写入缓冲电路BF的允许结点上，从而将启动写入缓冲电路BF并将逻辑“1”位写入激活的存储单元M11和M1（n+m）的存储结点N71中。这样位组合B1和Bn+m的分配信号便存储在存储单元M11和M1（n+m）的存储结点N71中，并且一直保持到译码电路DEC81再次指定存储单元M11到M1（n+m）的各行，并使场效应晶体管FET71对相连报告线RPT1放电。这样，一串位组合，每个组合由从输入位映象信号B1到Bn中先出的一位和从输出位映象信号中选出的一位组成，借助于时间片判决电路25g，分别存储到存储单元M11到M1（n+m）的各行中，该位组合将状态报告信号提供给时间片判决电路25g以分配给新包一个最早时间片。

3.总的电路功能

参考附图9A和9B，做定包缓冲装置201在时刻to接收具有指定输出端口24n的包首部PH1的新包PCK1，就此说明图2到图8所示异步传送方式交换网络系统的总的电路功能。包PCK0已存储于包存储器201a中，并等待由时间片调度装置25将时间片SL1分配给包PCK0。在时刻t10由同步信号启始时间片SL1。

在时刻t10，当包PCK1一到达，第一计数电路201b在计数器201i中有第一写入地址，而寄存器2011在时刻t10与同步信号同步地取出第一写入地址。然后，计数器201i将第一写入地址提供给随机存取存储器20h的写入地址端口WA，而由系统时钟信号顺序递增该第一写入地址。借助于这样顺序递增的第一写入地址，随机存取存储器201h在其中写入第一包PCK1的各位。当接口201g完成系统时钟信号的计数操作时，在时刻t20将表征包首部PH1的时间片请求信号RQT1送到第一总线系统26。

在时刻t20之前，将已写入包存储器201a的包PCK0从包存储器201a读到相连内部输入链路221。即，第三计数电路201e中的第二读出地址达到表示在时刻t10存储有第一读出地址的存储单元的某个值，并且在时刻t11将第一读出地址从控制存储器201d送到第二计数电路201c。由系统时钟信号递增第一读出地址，从随机存取存储器201h中将包PCK0各位顺序读出到相连内部输入链路221中。

由于时间片请求信号RQT1在时刻t20送到时间片调度装置25，译码电路25b将位B1移到逻辑“1”电平，而译码电路25c允许位Bn+m为逻辑“1”电平。然后列选择线SE1和SEn+m升到逻辑“1”电平。在时刻t20之前已对所有状态报告线RPT1到RPT1预充电，星号（＊）表示预充电操作。假定存储单元M11和M1（n+m）并未存储逻辑“1”电平的数据，而且，相应地为未保留状态。状态传感电路SS1在时刻t21产生命中信号GET1，而将列选择线SE1和SEn+m上的选择信号分别存储在写入电路WR1和WRn+m的寄存器RG71中。如果标准时间信号TS指定存储单元M11到M1（n+m）中的行，则位TOP1为逻辑“0”电平，而反相电路INV82将位TOP1反相为逻辑“1”电平。如设有任何命中信号GET1供给互斥电路Ex1，则互斥电路Ex1激活与存储单元M11到M1（n+m）相连的对应于下一时间片SL2的互斥电路Ex1。然后，将命中信号GET1反相为逻辑“1”电平，“与”门ND81允许“与”门AD81将命中信号作为分配信息存储在锁存电路LT81中。锁存电路LT81借助于减法器25i使编码电路25产生表示下一时间片SL2的时间片分配信号ASG1，该时间片分配信号ASG1被送到控制存储器201d。

在时刻t30，将第二总线系统27上的时间片分配信号ASG1锁存在接口201j中，加法器201f通过时间片分配信号ASG1和由第三计数电路201e馈给的第二写入地址之间的加法而检索绝对的第一写入地址。用同样方式检索的第二写入地址，随机存取存储器201k对存储在寄存器2011中的第一写入地址进行写操作，并将之作为第一读出地址加以存储。虽然附图中未予示出，在下一时间片SL2中将该第一读出地址从随机存取存储器201k读出到第二计数电路201c，类似于包PCK0的读出，用于对包PCK1的读出操作。

如在时刻t40，刷新信号UPDATE升到逻辑“1”电平，译码电路DEC81将位TOP1移位成有效逻辑“0”电平，从锁存电路LT80读出该分配信息，“与”门AD83将重写控制线WD1移位到逻辑“1”电平。以由（＊）指出的时序对位线对BL1到BLn+m预充电，当出现重写控制信号WD1时，字线驱动电路DRV1允许字线W1升到逻辑“1”电平。用已存入其中的选择信号，写入电路WR1到WRn+m中的寄存器RG71使写入缓冲电路BF驱动位线对BL1和BLn+m，从而将逻辑“1”的数据位在时刻t41写入存储单元M11和M1（n+m）之中。该写入操作用（＊＊）表示。

从前面描述可理解，本发明的异步传送方式的交换网络系统将所有包在其一到达包缓冲装置时就分配到各个时间片，从而提高吞吐量。事实上，如果本发明的异步传送方式的交换网络系统有与输出端口同样多的n个缓冲装置，可提高吞吐量如图10所示。而且，可用以1.2微米设计规则制造的互补MOS反相器来实现该异步传送方式的交换网络系统，该系统能很好响应20MHz的系统时钟信号。

虽然图示并说明了本发明的具体实施例，对本领域技术人员显而易见的是可作各种改变和修改而不偏离本发明的精神和范围。