一种保证服务质量的大型CICQ交换结构
2020-06-08郭子荣冯雪莲孟庆云代秀珍
郭子荣 冯雪莲 孟庆云 代秀珍
摘要：现代包交换机需要具有为不同的数据流提供不同的服务质量（QOS）的能力，同时随着网络规模和业务的增长，交换机的线卡数目会大量增加，线卡和交换矩阵需要分布在多个线柜中，它们之间的距离可能达到数十米，因此在设计交换机时不能忽视交换机内部的往返时延（RTT）。该文从这两个方面来讨论支持大RTT的组合输入和交叉点缓存排队（CICQ）交换结构实现服务质量保证问题，提出了基于扩展交叉点缓存的支持大RTT并提供基于流的性能保证的CICQ（CICQ-ECBs）交换结构，给出解除扩展交叉点缓存（ECB）阻塞机制，并用Counting方法证明了2倍加速的CICQ-ECBs交换结构能够实现PIFO-OQ仿效。
关键词：往返时间（RTT）;CICQ交换结构;输出排队交换仿效;推入先出（PIFO）;counting方法
中图分类号：TN915 文献标识码：A
文章编号：1009-3044（2020）10-0022-05
1概述
随着近几年宽带网络的发展，各种基于多媒体应用的网络服务，如远程会议、远程教育、视频点播等相继出现，这些网络业务通常有不同的QoS需求。交换机和路由器控制不同数据流的包的离开顺序，因此设计现代包交换机和路由器必须要考虑QoS的支持能力。另一方面，为适应网络业务的增长，交换机需要有大量的线卡支持大的端口数目，这种趋势导致物理空间和功耗的增加，迫使交换机变成分布式的结构，线卡和交换矩阵分布在多个线柜中，线卡和交换矩阵之间的连线达到数十米，因此交换机内部的往返时延（RTT）不能忽视。
随着现代VLSI技术的发展，已有可能在crossbar的交叉点上集成少量的存储器，构成组合的输入一交叉点排队（CombinedInput-Crosspoint Queued，CICQ）的交换机。由于在每个交叉点放置了少量缓存，CICQ交换去除了输入排队交换中输入输出端口必须同步的问题，使输入端口的调度和各个输出端口对交叉点的调度可独立、并行地进行，因此极大地简化了调度算法。对于一个采用基于信用（credit-based）流控的CICQ交换机而言，RTT为一个信用流控信息从crossbar内离开到达输入端口及一个信元从输入端口进入交叉点缓存的时间，如果以传输一个信元所需的时间（通常称为一个时隙）为单位表示RTT，则在最坏情况下每个交叉点需要RTT个信元的缓存空间，才能使交换机处于工作持续（Work-Conserving）状态，整个crossbar内的缓存容量就达到了RTTxN2。如果考虑基于流的服务质量问题，每个交叉点还需要更多的缓存，这在大型交换机中是很难实现的。
文献[6][11]提出在交叉矩阵的边缘或内部为每个输入端口放置一个容量为RTT个信元的存储模块，在其中设置Ⅳ个虚拟交叉点队列（VCQ），让N个交叉点共享的这RTT个信元的缓存空间，从而使整个crossbar内的缓存空间从RTTxN2变成N2+RTTxN。
交换机若要提供基于流的性能保证，就要按流来分配资源，每个流都可以获得它保证的带宽、时延或抖动性能。在0Q交换中，所有到达的信元都直接在输出端排队，按流组织队列，每个队列有一个相应的权值（给每个流分配的带宽），当一个信元到达时，输出调度器根据调度算法和队列权值来计算这个信元的离开时间[8-9]，并将信元插入到按离开时间排序的一个优先列表中，调度器按这个优先列表的顺序调度信元离开交换机，从而保证每个流的性能，这样的0Q交换机被称为PIFO（Push-In-Fist-Out）OQ交换机。
在CICQ中实现基于流的调度时，有可能出现这样的情况，交叉点中已有一个信元，一个新到达的信元有比交叉点信元有更早的离开时间，因为新信元赶不上交叉点中的信元，导致了“交叉点”阻塞问题。很多文献提出了去除交叉点阻塞的方法，文献[10]提出在输入端暂存已经传输到交叉点的信元的副本，当一个新到达信元的离开时间早于交叉点信元时，直接将信元传送到它的交叉点中，而将原交叉点信元的副本重新插入到队列中，由此解决交叉点阻塞问题，并证明了2倍加速、交叉点只有一个信元缓存的CICQ交换，使用这种解除阻塞机制，可以仿效PIFO-OQ交换。本文将这种解除阻塞机制扩展到支持大RTT的分布式CICQ交换中，并证明了我们提出的结构也可以仿效PIFO-OQ交换的性能。
本文首先提出一种能够提供基于流的性能保证、支持大RTT的CICQ交换结构，称之为扩展交叉点缓存的CICQ（cICQ-ECBs）交换结构;之后将文献中常用于OQ仿效证明的Counting方法擴展到CICQ-ECBs交换结构中，针对CICQ-ECBs交换结构提出了Counting方法的相关定义和OQ仿效的充分条件，最后给出CICQ-ECBs交换结构为满足OQ仿效所采用的调度算法和解除阻塞机制，证明了2倍加速的CICQ-ECBs交换机可以仿效一个PIFO-OQ交换的性能。
本文其余部分组织如下，第2节给出CICQ-ECBs交换结构，第3用Counting方法证明所提出的交换结构和调度策略能够提供0Q性能仿效。第4节为结束语。
2支持大RTT的CICQ-ECBs交换结构
为了使具有较大RTF的CICQ交换机能够提供基于流的性能保证，使用扩展交叉点缓存支持大RTT的CICQ交换结构The CICQ Switch with Extended CrosspointBuffers for Large RTF-CICQ-ECBs），如图1所示。
在一个NxN的CICQ-ECBs交换中，输人端对到达的信元按流组织虚拟队列，以避免队头阻塞，每个队列按预订的速率被分配一个权值。
为了达到OQ交换的性能，交换矩阵需要以2倍于端口的速率运行，因此在输出端也设置缓存，在输出缓存中信元也按流排队，以便提供基于流的性能保证。
带缓存crossbar的每个交叉点只有一个信元的缓存空间。在crossbar的边缘或内部为每个输入端口放置一个扩展交叉点缓存模块（ECB），在ECB中也按流组织虚拟队列。在本文中，将一个信元从输入端口i传输到EcB。和相应的流控信息从ECB;返回到输入端i所经历的时间用RTT个信元时隙表示。在2倍内部加速的情况下（输人端口到它的ECB之间以端口速率通信，不加速），为使交换机处于工作保持（Work-Conserving）状态，并且能够区分不同的数据流，每个输入-输出对（相应于每个交叉点）最坏情况下需要至少2xRTT个信元的缓存空间，按流组织虚拟队列，这样在每个ECB上需要2xRTTxN个信元的缓存空间，不依赖于流的数目。
带缓存的crossbar与每个ECB之间使用基于信用（Credit-based）的流控机制，当一个交叉点CP（i，j）有信元占用时，向相应的ECBi发送可用信用CPC（i，j）=0，当交叉点信元被传送到输出端后，可用信用变为CPC（i，j）=1。每个ECBi和它的输入端口之间也采用基于信用的流控，对每个交叉点提供2xRTT个信用，由去往这个交叉点的多个数据流共享，如果在ECBi中已有2xRTT个去往输出j的信元，则向输人端口i发送信用ECBC（i，j）=O，每当有一个信元被传输到交叉点后，向输入端口i发送可用的信用數目ECBC（i，j）。
分别在输入端和ECB上保存已发送到扩展交叉点缓存和交叉点上的信元的副本，用于解除ECB阻塞和交叉点阻塞。
采用“按虚拟流队列分组（Group-By-Virtual-Flow-Queue，简称GBVFQ）”插入策略，分别在输入端维持一个输入优先列表（Input Priority List，简称IPL）、在ECB上维持一个扩展交叉点优先级列表（ECB Priority List）列表，其中优先列表中的信元按流分组。
GBVFQ算法为：在输人端到达的信元按流排队，当一个信元到达一个非空的流队列时，信元被插入到输入优先列表中属于同一个流的上一个信元之后，这确保同一数据流的信元是按离开顺序排序的;当一个信元到达一个空的流队列时，信元被插入到输入优先列表IPL的头部。
在ECB中，从输入端到达的信元也按流排队，同样使用GBVFQ算法将到达的信元插入到EPL中。
3CICQ-ECBs交换以2倍加速实现PIFO-OQ仿效
文献[1]使用counting方法证明一个加速2倍的无缓存crossbar的CIOQ交换可以仿效一个OQ交换。为达到仿效OQ的目的，在CIOQ中的每个信元必须在要仿效的OQ（称为投影0Q）交换中对应的信元离开OQ之前的时间被传送到CIOQ的输出端。我们将这种Counting方法用于CICQ交换的OQ仿效的证明。
3.1Counting方法的相关定义
首先，根据CICQ-ECBs交换结构的特点给出Counting方法的相关定义。
投影OQ交换机：要仿效的OQ交换机，它确定了CICQ-ECBs交换机中每个信元的离开时隙，与CICQ-ECBs交换有相同的到达。
离开时间（Time-to-Leave，TTL）：TTL（c）等于信元c的离开时隙，由投影OQ指定。在CICQ-ECBs交换机中，因为采用分布式调度，信元只有在到达交叉点缓存后才能计算它的TTL，不会有去往同一输出端的两个信元有相同的TTL。
输出优先列表（Output Priority List，简称OPL）：每个输出端基于信元的TTL顺序对在输出端和它的交叉点中排队的信元建立输出优先列表，有最小TTL值的信元最先离开。
输入优先列表（IPL）：每个输入端对所有在此排队的信元维持一个有序列表。在信元到达输入端口时，因为没有这个信元要去往的输出端口的所有流的信息，所以在输入端还不能计算出它的TTL值，使用GBVFQ插入策略来维持输入优先列表中信元的顺序。在同一输入端口中的两个信元，如果都有ECB信用可用，则有较高的输人优先权的信元先被发送到ECB。
ECB优先列表（EPL）：信元从输入端口到达ECB后按流排队，每个ECB上有一个ECB调度器，负责将在此排队的信元传输到相应的交叉点缓存中，因此也需要维护一个优先列表。仍然采用GBVFQ插入策略来维持ECB优先列表中的信元顺序，在同一ECB上的两个信元，如果它们的交叉点都为空，则有较高ECB优先权的信元被传送到交叉点。
输出缓冲（Output Cushioll）：一个信元c的输出缓冲OC（c）为在c的输出优先列表中TTL值小于c的信元数目。
输入排头（Input Thread）：一个信元c的输入排头IT（c）为在c的输入缓存中有比c更高的输入优先权的信元数目。正处于从输入端到ECB传输途中的信元、ECB中的信元和交叉点中的信元，它们的IT为O。
ECB排头（ECB Thread）：一个信元c的ECB排头ET（c）为在c的扩展交叉点缓存中比c有更高的ECB优先权的信元数目。在交叉点中排队的信元的ET为O。
松弛度（Slackness）：在CICQ-ECBs交换机中，定义信元c的松弛度，L（c）为它的输出缓冲减去它的输入排头与ECB排头的和，即
L（c）=OC（c）-IT（c）-ET（c）
对于一个已在ECB中或在交叉点中等待的信元c，因为它的IT（c）=O，因此它的Uc）等价于
L（c）=OC（c）-ET（c）
3.2CICQ-ECBs实现oQ仿效的充分条件
在图l所示的CICQ-ECBs交换机中，一个信元时隙内最多有一个信元到达一个输入端口，最多有一个信元离开一个输出端口。带缓存的crossbar有2倍加速，因此在一个外部信元时隙内可能有两个信元从一个ECB离开进入相应的交叉点，以及可能有两个信元离开交叉点到输出队列。为便于分析，将每个外部时隙分为六个阶段：
到达阶段：一个新信元到达输入端口，被放置到它的虚拟流队列中，并将它的存储指针按GBVFQ规则插入到输人优先列表IPL中。
輸入调度阶段：输入调度器按照输入优先列表的顺序，从各个流队列中选择ECB上有空闲空间（ECBC（i，j）>O）的头部信元传送到ECB中。
ECB到达阶段：一个信元从输入端口到达ECB缓存，被放置到它的虚拟流队列中，并将它的存储指针按GBVFQ规则插入到ECB优先列表EPL中。
第一个内部调度阶段：有两个子阶段，ECB调度和交叉点调度。其中ECB调度按ECB优先列表的顺序选择交叉点为空的信元发送到交叉点缓存中;每个输出端的交叉点调度器，从非空的交叉点中选择最小TTL的信元传输到输出缓存中。
第二个内部调度阶段：带缓存的crossbar加速2倍，在一个时隙内第二次执行ECB调度和交叉点调度。
离开阶段：从每个输出端移出一个信元发送到输出线上。
如果在当前时隙和TTL（c）之间的调度阶段的数目大于或等于服务c和可能阻塞c的信元所需的调度阶段数目，则OQ仿效成立。L（c）就是追踪可用的调度阶段与阻塞信元c的信元数之间的差。IT（c）或ET（c）的减少或OC（c）的增加都意味着c更有可能在它的TTL（c）时隙到达它的输出端，按时被发送。
对于在输入端排队的信元c而言，如果在它到达输入端时保证以非负的松弛度插人到输入优先列表中，并且在它开始被发送到ECB之前的所经历的每个时隙，都保证它的，L（c）不减少，则它会被按时传送到ECB中。
当信元从输入端传输到ECB后，再按GBVFQ插入策略插入到ECB优先列表中，此时可以按，L（c）=OC（c）-ET（c）重新计算它的松弛度。同样，如果保证它以非负的，L（c）值插入到ECB优先列表中，并且在此后的每个内部调度阶段保证它的松弛度至少增加l，则在2倍加速的交换机中可以保证从一个时隙到下一个时隙信元的松弛度一直为非负，这样可确保当一个信元到达它的输出端时，它的OC是非负的，才能确保一个信元能按时从它的输出端口离开。
文献[2]给出了CICQ交换仿效OQ交换的三个充分属性，而CICQ-ECBs交换要仿效OQ交换需要满足下面4个属性。
属性1：（LTTL交叉点调度）在输出优先列表OPL中，信元按最小TTL（Lowest TTL，LTYL）优先的顺序排列。
属性2：（LTTL交叉点阻塞）对于一个在ECB中排队的任意信元c，如果在一个调度阶段信元c被交叉点流控所阻塞，则在它的交叉点中一定存在一个信元其TTL
由属性1和2可得到下面的引理。
引理1.对于一个服从LTTL交叉点调度和LTTL交叉点阻塞的CICQ-ECBs交换机，在一个内部调度阶段开始时已在ECB中或在交叉点中的任意一个信元c，在这个内部调度阶段结束后它的松弛度，L（c）至少增加1。
引理1的证明与文献[2][3][4][5][10]中普通CICQ交换机中相应的引理证明基本一致，这里不再复述。
属性3：（LTYL ECB阻塞）对于在输入端排队的任意一个信元c，如果在一个调度阶段信元c被ECB流控阻塞，则在它的ECB中一定有2xRTT个信元去往c的输出端、且它们的TTL都小于TTL（c）。
这里的TTL是同一输入一输出对的信元的相对离开时间，虽然在输入端不能计算每个信元最终离开交换机的时间，但在它们到达输入端口时，可以根据当前活动流的权值确定去往相同的输出端口的信元的离开顺序。属性3管理输入调度和ECB流控的关系。由属性1、2和3可以得出下面引理。
引理2.对一个服从LTTL交叉点调度、LTTL交叉点阻塞和LTTL ECB阻塞的CICQ-ECBs交换机，任何一个在输入调度结束时还在输入端排队的信元，在经过两个内部调度阶段之后，它的松弛度至少增加2。
证明：考虑一个在输入端排队的信元c，在输入调度阶段的开始，信元c或者被ECB流控阻塞或者c有信用可用。
第一种情况，c有信用可用，则输人调度器可调度c或者是IPL中c前面的另一个信元传输到ECB中。如果c被调度，它将在RTT2时隙之后到达ECB，以非负松弛度插入到ECB优先列表中;如果是排在c前面的另一个信元d被传送，则IT（c）减1，在这种情况下，继续考虑本时隙的内部调度阶段。在通常情况下，当输入端有信元到达时，如果没有ECB阻塞，则到达的信元会在当前时隙就被传送到ECB缓存中，而现在在c的前面有信元d排队，说明ECB中至少有RTT个信元，才能使信元d在经过RTT/2时隙后到达ECB时，使交换机持续工作。这样，在d开始被传输的时隙，ECB调度和交叉点调度或者使OC（c）增加l，或者Er（c，）减1，即经过2个内部调度阶段，L（e）至少增加2。
第二种情况，信元c被ECB流控阻塞。由属性3可知，在它的ECB缓存中一定有2xRTT个与c去往同一输出端的信元，且它们的TTL小于TTL（c），这样在LTTL交叉点调度中或者选择c的交叉点中的信元或者选择同一输出端的另一个交叉点信元传送到输出端，这两种情况都使OC（c）增加1，则经过2个内部调度阶段，L（c）至少增加2。
引理2证毕。
引理3.一个2倍加速的CICQ-ECBs交换机满足LTTL矩阵调度、LTFL交叉点阻塞和LTTL ECB阻塞属性，则对于任一个还未到达它的输出端的信元c，从一个时隙的某个时间点到下一个时隙的相同时间点，L（c）不会减少。
证明：考虑在时隙t的某个时间点，一个信元c可能处于下面四个位置之一：在输入端，在从输入端到ECB的传输途中，在ECB中，在交叉点缓存中。如果c没有被传输到输出端，将给出在时隙t+1的这个时间点，L（c）不会减少。
如果c在输入端，由引理2可知，c或者在输人调度阶段以非负的，L（c）被传送到ECB中，或者在两个内部调度阶段之后，J（c）至少增加2。对前一种情况，信元c将保持非负的L（c）到达ECB。对后一种情况，因为在一个时隙周期的到达阶段IT（c）最多增加1，且OC（e）和ET（c）不变;在离开阶段OC（c）最多减1，且IT（c）和ET（c）不变，因此从时隙t到时隙t+l信元c的L（c）不会减少。
如果c在从输入端到ECB的传输途中，此时IT（c）=0，因此，L（c）=OC（c）-ET（c）。从时隙t到时隙t+l，到达阶段和输入调度阶段都不影响L（c），如果此时在各个ECBs上有去往c的输出端的信元，则在两个内部调度阶段或者OC（c）增加1，或者ET（c）减1，而离开阶段OC（c）减1，因此时隙t到时隙t+1不会减少;如果此时在各个ECB上没有去往c的输出端的信元，则根据GBVFQ插入策略，在c到达ECB后会立即被传输到它的输出端。
如果c在ECB中或交叉点缓存中，则由引理1可知在每个内部调度阶段之后L（c）至少增加1，到达过程不影響，L（c），但ECB到达阶段有可能使ET（c）增加1，离开过程OC（c）最多减1，因此在一个时隙周期内ECB或交叉点中的信元的松弛度不会减少。
综上所述，引理3成立，证毕。
下面的属性是确定输人端和ECB对到达信元的插入原则。
属性4：（NNS插入）在输入端，一个到达的信元以非负的松弛度（N0n Negative Slackness，NNL）插入到输入优先列表IPL中;在ECB中，一个从输人端到达的信元以非负的松弛度插入到ECB优先列表EPL中。
定理1.一个2倍加速的NxN的CICQ-ECBs交换机满足NNS输入端插入和NNS ECB插入、LTTLECB阻塞、LTTL交叉点阻塞和LTTL交叉点调度，可以准确地仿效一个使用PIFO调度策略的OQ交换机。
证明：用归纳法证明。
假定到时隙t-1的离开阶段CICQ-ECBs一直可以仿效一个PIFO调度策略的OQ交换机，这意味着所有TTL
如果c在输出队列中，则c可立即被发送。
如果c在交叉点缓存中，因为TTLc）=t，则c是交叉点中TTL值最小的信元，LTTL交叉点调度器会在第一个内部调度阶段将c传输到输出队列中。
如果c在ECB中排队，因为c以NNS插入到EPL中，引理3表明在时隙t的第一个内部调度之前，L（e）≥O，因为在c的输出端没有TTL
下面证明不会有离开时间为TTL=t的信元在时隙t时还未到达ECB中。
用反证法证明。假设一个TTL=t的信元c在时隙t时还未到达ECB，则表明在t-RTT/2时隙时信元c还在输人端未被传输。因为输入端与ECB之间的传输速率与外部端口速率相同，因此在通常情况下一个信元在到达后能立即被传输到ECB中，除非被ECB流控阻塞。如果c被阻塞，则由属性3可知，ECB中一定有2xRTT个信元去往c的输出端，且它们的TTL都小于TTL（c），而c的输出端发送这2xRTT个信元需要2xRTT个时隙（自流控信息从ECB向输入端开始传输的时隙计算），则当信元c在t-RTT/2时隙得知被阻塞时，它离开交换机的时间最早要在t+RTT时隙之后，这与信元c的TTL=t的假设矛盾，因此假设不成立，表明在时隙t所有TTL=t的信元都至少已到达ECB中。
综上所述，一个TTL=t的信元c在时隙t的离开阶段之前一定能到达它的输出端，因此OQ仿效成立，定理1证毕。
3.3 CICQ-ECBs交换机实现PIFO-OQ仿效
上一小节给出了带有扩展交叉点缓存的CICQ交换结构仿效PIFO-OQ需要具备的四个属性，本节给出CICQ-ECBs交换机如何满足这些属性。
首先满足LTTL交叉点调度属性。当信元到达交叉点时，足可以根据各个数据流的权值计算出信元在投影0Q交换机中的离开时间，因此可以将输出优先列表中的信元按最小离开时间（LTTL）优先的顺序排列。
第二，满足LTFL交叉点非阻塞属性。当一个信元c从输入端到达ECB时，它属于一个新流，有最高的EPL优先权，这时可能会出现下面的情况，在它的交叉点中已有一个信元d，但新到达的信元c的离开时间早于d，即TTL（c）
当交叉点中的信元被选中传输到输出端后，交叉点向ECB发送交叉点可用的流控信息，ECB在接收到流控信息后，清除这个交叉点信元的副本和它的存储指针。
第三，满足LTTL ECB非阻塞属性。在CICQ-ECBs交换机中，不仅存在交叉点阻塞问题，也存在扩展交叉点阻塞。当一个信元c到达输人端时，它属于一个新流，有最高的输入优先级。可能会出现下面的情况，在输人调度阶段它被ECB流控信息阻塞，因为在ECB上已有2×RTT个信元与c属于同一输入一输出对，但信元c的相对TTL低于这2xRTT个信元中的一个或多个信元的TTL，致使属性3不满足。同样采用在输入端暂时保存所有当前在ECB上的信元的副本的方法接触ECB阻塞。
第四，满足NNS插入属性。
引理4.一个2倍加速的、满足LTFL矩阵调度、LTTL交叉点阻塞和LTFL ECB阻塞属性的CICQ-ECBs交换机，在输入端和ECB上使用GBVFQ算法满足PIFO-OQ仿效的NNS插入属性。
下面用归纳法证明在输入端满足NNS插入。
证明：首先在初始情况下，系统为空，一个信元c到达输入端，此时OC（c）=O，IT（c）=O，ET（c）=O，因此L（c）=OC（c）-IT（c）-ET（e）=O，满足NNS插入。
假设到时隙t的到达阶段都满足NNS插人，给出到时隙t+1的到达阶段仍满足NNS插入。
设在时隙t+1信元c到达输入端，c到达一个空的或者非空的流队列。
如果c到达一个空的流队列，则c被放置到IPL的头部，IT（e）=0，此时还要考虑下面两种情况：如果在ECB上和到ECB的传输途中都没有与c属于同一数据流的信元，则ET（c）=O，而OC（e）≥o，因此，L（c）=OC（c）-IT（c）-ET（c）≥O，满足NNS插人;如果在ECB上或到ECB的传输途中有与c属于同一数据流的信元，用c1表示这些信元中的最后一个信元，则ET（c）=ET（c1）+1，OC（c）≥OC（c1）。因为到时隙t时都满足NNS插入，则在时隙t时，L（c1）≥O。由引理1可知，在时隙t的两个内部调度阶段，L（c1）至少增加2，在离开阶段L（c1）减1，在时隙t+1的到达阶段，L（c1）不变，因此在时隙t+1的到达阶段之后，L（c1）≥I，则有
L（c）=OC（c）-ET（c）≥
OC（c1）-（ET（C1）+I）=L（c1）-I≥1-1=0
满足NNS插入。
如果c到达一个非空的流队列，因为到时隙t的到达阶段都满足NNS插入，因此c的虚拟队列中它前面的信元都以NNS插入。设c1为c的虚拟队列中c之前的最后一个信元。则根据引理3，一个还未到达它的输出端的信元，从一个时隙的某个时间点到下一个时隙的相同时间点，它的松弛度不会减少，因此在时隙t的到达阶段之后，L（C1）≥0。而由引理2可知，在时隙t的两个内部调度阶段，L（c1）至少增加2，在离开阶段，L（c1）减1，在时隙t+l的到达阶段，到达的信元c插在c.之后，L（c1）不变，因此在时隙t+l的到达阶段之后，L（c1）≥1。又因为TTL（c）>TTL（c1），所以有OC（c）≥OC（c1），而c被插在IPL中c1之后的位置，则有IT（c）=IT（c1）+I，ET（c）=ET（c1），因此在时隙t+l的到达阶段，
L（c）=OC（c）-IT（c）-ET（c）≥OC（c1）-（IT（c1）+I）-ET（c1）L（c1）-I≥1-1=0
表明信元c以NNS插入到IPL列表中。
用同样的方法可以证明使用GBVFQ算法的EPL插入也满足NNS插入属性，这里不再重复。
综上所述，GBVFQ算法满足NNS插入属性。
因此，由定理l可以得出，一个两倍加速的NxN的CICQ-ECBs交换机，使用GBVFQ插入算法、通过暂存信元副本来解除ECB阻塞和交叉点阻塞的机制以及LTFL交叉点调度算法，可以准确地仿效一个使用PIFO调度策略的0Q交换机。
4结束语
本文针對支持大RTT的CICQ交换结构研究了OQ交换仿效的问题，首先给出了使用扩展交叉点缓存支持大RTI的CICQ交换结构（CICQ-ECBs），分析了CICQ-ECBs交换要实现OQ仿效，不仅存在交叉点阻塞，也存在ECB阻塞问题，之后基于Counting方法给出了CICQ-ECBs交换仿效PIFO-OQ交换应具备的四个充分条件，最后证明2倍加速的CICQ-ECBs交换采用GBVFQ插入算法以及解除ECB阻塞和交叉点阻塞的机制，可以仿效PIFO-OQ交换。
