時槽

Crossbar是一種無阻塞的交換結構，以時隙同步方式運作，在一個服務時隙內受限於每個入口(或出口)最多與一條出口(或入口)連通的條件，Crossbar最多可以在N對輸入輸出、端口之間同時建立連接(N 為交換機規模)，也即一個服務時隙內每個入口(或出口)最多發送(或接收)一個信元，同一個服務時隙內最多有N 個信元被交換，在輸入單元內部其他已接收信元則進入緩存等待調度，作如下假定：

(1) 交換機端口數量為N，且各端口線速率相同；

(2) 交換機內部以定長信元的方式交換數據；

(3) 交換結構加速比S=1，即交換結構的服務時隙等於交換機端口發送或接收一個信元的時延；

(4) 各輸入單元上的緩存按VOQ(virtual output queueing)方式存儲等待信元 ^[1]  。

一種新的基於單級Crossbar的輸入排隊調度策略，該調度策略綜合了以上兩類調度策略的優點，通過對EPFTS交換機不同端口對上的聚集業務流進行區分，保障各聚集業務流上已預定的傳輸時槽數量。

在EPFTS 交換環境下，各端口最大吞吐速率以單位時間內可傳輸的定長物理幀數量(即物理幀時槽數量)來表示。由於允許進入SUPANET的業務流在虛通路建立過程中，其速率需求映射為適當的時槽數，並在沿途所有EPFTS交換節點上預定，虛通路建立成功後，其在各交換節點上輸入、輸出端口以及預定時槽數等信息均保存於本地信息庫中。EPFTS 交換機各端口對上聚集業務流的速率需求可通過查詢本地信息庫得知。由於EPF 幀本身為定長的數據塊，為簡便起見，我們假設EPFTS交換機即以EPF 幀作為內部交換用的定長信元，各輸入端上指向同一輸出端j的VOQ子隊列構成輸出端j的虛擬輸入隊列(virtual input queueing，簡稱VIQ)。

為了確保 EPFTS交換機輸入、輸出端口對上預定的時槽數量能夠得到滿足，需要控制各端口對實際獲得的系統服務速率，為此，我們在交換結構每個端口上維護一張端口(輸入端口或輸出端口，簡稱入口/出口)清單，根據各端口對上已預定時槽數量控制各端口發送或接受請求.下面分析在各端口上維護端口清單的機制和方法:

類似於WRR(weighted round robin)調度算法，輸入端i視所有的VOQij為其服務對象，以(i→j)上預定的時槽數sij作為隊列VOQij的權值；假設端口i上的服務週期長為Mi個服務時隙，則每個服務週期內VOQij應獲得的服務次數為Mi×sij/fi，即平均每隔fi/sij個時隙，隊列VOQij即應得到一次服務.但由於端口發生衝突，VOQij上的服務並不總是及時得到滿足，為此，以sij為子隊列VOQij和VIQji在每個服務時隙上的步進權值，並引入變量vij和變量cij用於記錄VOQij上應服務但尚未服務的時隙個數，分別稱為累積信用和冗餘信用；所有vij=0的子隊列都將被拒絕服務。同樣，輸出端j視所有虛擬子隊列VIQ為其服務對象，實施相同的控制機制。這樣，各端口將為本地每個子隊列新增兩個變量vij，cij，用來記錄該子隊列當前的有效信用(有效信用定義為冗餘信用+累積信用×端口預定時槽總數)。各端口根據本地子隊列的有效信用維護相應的端口清單。最終，TRWFS調度策略中每個服務時隙的仲裁 ^[2]  。

為了保障業務流的端到端的傳輸服務質量，要求終端應用在數據傳輸開始之前需先通過控制信令建立起端到端的虛通路，當虛通路建立時，對應於其業務傳輸速率需求的時槽數在沿途各EPFTS交換節點都得到了預定並在本地的業務速率需求矩陣中保存，因此，各端口對上當前活動業務流時槽需求總數是已知的。總之，TRWFS 的基本策略就在於通過各端口對上的預定時槽數量來控制二相迭代的匹配過程。TRWFS的3種實現形式，用於探索該調度策略的複雜性和有效性.最終的實驗結果表明，TRWFS策略結合一般輪詢迭代的實現方式，具有系統吞吐率高、業務流需求速率保障能力強的特點，並且在時間和空間上的實現複雜度與一般輪詢算法接近，即使當業務負載發生變化時，相關參數的更新過程也比較簡單，因此比較適合在高速EPFTS交換節點中實現 ^[3]  。