一種保證服務質量的大型CICQ交換結構

郭子榮 馮雪蓮 孟慶云 代秀珍

摘要：現代包交換機需要具有為不同的數據流提供不同的服務質量（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內的緩存容量就達到了RTTxN²。如果考慮基于流的服務質量問題，每個交叉點還需要更多的緩存，這在大型交換機中是很難實現的。

文獻[6][11]提出在交叉矩陣的邊緣或內部為每個輸入端口放置一個容量為RTT個信元的存儲模塊，在其中設置Ⅳ個虛擬交叉點隊列（VCQ），讓N個交叉點共享的這RTT個信元的緩存空間，從而使整個crossbar內的緩存空間從RTTxN²變成N²+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交換。