大容量星上交換網絡的設計與實現

鮑民權，邱智亮，張茂森，劉煥峰

（西安電子科技大學綜合業務網國家重點實驗室，陜西西安710071）

0 引言

隨著移動通信、多媒體廣播業務的發展，人們對衛星數據通信的要求更加迫切，這需要在衛星上實現分組交換。星上交換除需要完成與地面交換相同的功能外，還受到芯片容量、功率及實現復雜度等多方面的限制[1]。多級交換網絡允許使用小容量芯片構建大規模交換網絡，交換網絡的容量不再受到單芯片容量和引腳數目的限制。因此，當構建大容量星上交換網絡時，多級交換網絡結構更具有優勢[2]。現有大多數高速交換網絡內部都采用定長信元交換，由于變長分組在被切片成定長信元時，信元的利用率不可能達到100%，這就要求內部鏈路速率高于外部鏈路速率。

在分析定長信元長度與內部鏈路速率的關系的基礎上，給出了通過選取信元長度來降低內部鏈路速率的方法。交換網絡規模的擴大，使完成一次調度的時間相應增加，如果處理不當，會對交換網絡性能造成影響[3]。介紹了交換網絡中的多子調度器技術，通過多個子調度器并行計算，完成整個交換網絡的路由調度，以有效消除交換網絡規模增加對系統性能造成的影響。

1 Clos網絡模型

Clos網絡是一種常見的多級交換網絡，其模塊化結構和可擴展性很好地滿足了星上交換的要求。Clos網絡模塊化的結構允許通過多個小容量的芯片構建大規模的交換網絡，將中間級模塊用一個完整的3級Clos網絡替換，可以把3級Clos網絡擴展為5級Clos網絡，采用相同的方法繼續擴展下去，這樣可以使用相同的交換模塊，構建任意規模的交換網絡[4]。Clos網絡的結構可歸納為以下3點:①交換網絡中的交換模塊被排列為3級;②每一個交換模塊同相鄰級中任一交換模塊相連接;③每一個交換模塊都是無阻塞的。

Clos網絡的結構如圖1所示。其中，IM表示輸入級模塊，CM表示中間級模塊，OM表示輸出級模塊;VOQ表示輸入級模塊的虛擬輸出隊列，VIQ表示輸出級模塊中虛擬輸入隊列。

圖1 Clos網絡結構

通常，將Clos網絡輸入級模塊輸入端口數記為n，輸出端口數記為m，輸入級模塊數記為k，并把這樣的Clos網絡記為C（m，n，k）。Clos網絡被分為2種:中間級無緩存結構（MSM）和中間級有緩存結構（MMM）。中間級無緩存的Clos網絡（MSM）可以保證分組在交換網絡內部傳輸時的順序，但是需要合適的調度算法解決中間級輸出端口分組沖突問題[5]。目前，基于中間級無緩存的Clos網絡的調度算法已經成為研究的重點，文中所討論的也是這種網絡。

2 隊列管理技術

當交換網絡的輸入端口采用先進先出（FIFO）的排隊規則時，可能會出現隊頭分組競爭輸出端口失敗，而后續分組的目的端口即使空閑，也無法發送的現象，這種現象被稱為隊頭（HOL）阻塞，它嚴重制約了交換網絡的吞吐率。為消除隊頭阻塞帶來的影響，通常在IM模塊中使用虛擬輸出隊列（VOQ）來代替簡單的FIFO，每一個VOQ對應于交換網絡的一個輸出端口，因此每一個IM模塊中有n×k個VOQ。由于同一VOQ中的分組發往同一輸出端口，因此不會被發往其他端口的分組所阻塞。同時，VOQ按照分組到達的先后順序發送，分組之間不會亂序。

在實際的工程中，可以使用共享緩存和隊列管理實現VOQ技術[6]。采用共享緩存不需要為每一個VOQ隊列單獨分配緩存，節省了存儲資源。當有分組到達時，輸入端口向隊列管理模塊發出申請，隊列管理模塊將分組信息加入對應的VOQ中，同時在共享緩存中給當前分組分配一定的空間，這個過程被稱作分組的入隊;VOQ根據自己隊列情況向交換網絡的調度器發送請求，調度器根據所有VOQ的請求進行調度;當完成一次調度后，如果VOQ獲得在交換網絡內部發送數據的機會，分組內容會從共享緩存中被讀出，以定長信元的形式在交換網絡內部傳輸，同時VOQ修改隊列信息，這個過程被稱作分組的出隊。

交換網絡內部的定長信元需要在OM模塊的輸出端口處被組裝成變長分組。因此，每個輸出端口都要有相應的輸出緩存來存儲整個分組。對于OM模塊的每一個輸出端口，最多同時有k個IM模塊同時向該端口發送信元，這要求每個輸出端口至少要維護k個輸出隊列，被稱為VIQ，而每一個輸出級模塊需要維護的輸出隊列數目為n×k個，VIQ也可以使用共享緩存和隊列管理來實現。

3 信元長度和鏈路加速比的關系

在實際應用中，變長分組在進入交換網絡前被切片為定長信元，然后在交換網絡中完成交換過程，在輸出端口處重組為變長分組。相比變長分組交換，采用定長信元交換有以下優點:①不需要為變長分組維護中間級鏈路，簡化調度算法;②避免長分組阻塞短分組的現象，有利于減少交換網絡的時延抖動;③減少中間級模塊的數目，如果在Clos網絡中使用變長分組交換，按照嚴格無阻塞的條件，CM模塊數m與IM模塊輸入端口數n之間的關系需要滿足m≥2n-1，而如果采用定長信元交換，則只需要滿足可重排無阻塞，即m≥n。

當交換網絡內部采用定長信元交換時，實際傳送的內容總是大于分組的實際長度，在設計交換網絡時，內部鏈路速率要高于外部端口速率。內部鏈路速率越高，硬件實現的難度就越大。因此，在滿足無阻塞交換的前提下，需要盡可能地降低內部鏈路速率。通過分析發現，當外部端口速率固定時，影響內部鏈路速率的關鍵因素是定長信元的長度，信元長度決定了傳輸同樣長度分組時信元的利用率，也就決定了內部鏈路的加速。

為計算內部鏈路速率與信元長度的關系，首先定義如下變量:幀長度Lf，幀間隔LI，信元數據部分長度Ld，信元頭部長度Ltag，信元長度Lc（=Ld+Ltag），端口數據速率Cf，內部鏈路數據速率Cc，加速比S（=Cc/Cf）。其中，LI表示物理鏈路上2分組間的最小幀間隔;Ltag包含信元在交換網絡內部路由和分組重組時所需的信息。上述變量滿足式（1），式中符號「?表示向上取整。

式（1）左邊是交換網絡內部傳輸一個分組所需最小時間，右邊是端口處接收對應長度分組所需的時間。為保證無阻塞傳輸，內部傳輸時間應小于等于端口處傳輸所用時間。式（1）可轉化為式（2）:

式中，S表示內部鏈路速率與端口速率的比值，也就是加速比，不等式右端是同樣分組長度下交換網絡內部傳輸數據總長度（即所有定長信元長度總和）和外部傳輸數據總長度（包括分組內容和幀間隔）的比值。根據式（2）確定的關系，可以選擇當不等式右端值最小時的Ld作為交換網絡內部信元數據部分的長度，此時所需加速比最小。

由于IM內部采用共享緩存來存儲分組，因此Ld還受限于共享緩存的讀取速率和位寬。用Cout_buffer表示共享緩存的讀取速率，Cout_buffer應滿足式（3）。

式中，Tslot=Lc/Cc表示一個時隙的長度，則共享緩存讀取端口的位寬Bout_buffer滿足式（4）:

式中，F表示共享緩存讀取時鐘的頻率，現有數字系統數據位寬一般都是2的整數次冪，因此不等式右端的計算結果需要向上對2的整數次冪取整。

4 子調度器技術

當交換網絡中只有一個調度器時，必須在一個時隙內完成一次調度，否則系統吞吐率會下降。如果交換網絡端口數目非常大，則完成一次調度所需的時間也會很長，時隙長度也會隨之增大，交換網絡不得不使用較長的信元。為消除端口數目增加對時隙長度帶來的影響，可以在交換網絡中增加多個調度器，每一個調度器的結構與原調度器類似，稱之為子調度器[7]。當多個子調度器并行工作時，允許每個子調度器用多個時隙完成一次調度。

當使用3個子調度器時，工作過程如圖2所示，每個子調度器允許使用3個時隙完成一次調度。每個時隙開始時，請求被發往某一子調度器;該調度器可以使用3個時隙完成一次調度，在完成該次調度過程中產生的請求由其他子調度器進行處理;每個時隙結束后，都有相應的子調度器返回調度結果，指導下一時隙內交換網絡中信元的傳輸，因此交換網絡的吞吐率不會因為調度時間的增加而下降。

圖2 有3個子調度器時的工作流程

當使用多子調度器時，IM模塊和調度器需要有相應的改變。IM模塊需要為每一個VOQ添加一個計數（VC），表示對應VOQ中未發送匹配請求的信元數目;當有新分組到達時，根據分組長度，VC增加相應數目。當發送一個匹配請求時，VC減1。同時在子調度器中添加VOQ標志位（VF）和調度結果寄存器（VR）。子調度器結構如圖3所示。

圖3 子調度器結構

圖3中調度器模塊實現預定的調度算法。VF和VR與IM模塊中的VOQ相對應。VF的值為0或1，1表示該子調度器收到了對應VOQ發送的調度請求，0表示沒有收到請求;VR表示對一個調度請求的結果，它包含2部分:①對應VOQ的請求是否獲得匹配;②獲得匹配后該信元所需的路由信息。當使用P個子調度器時，調度器工作流程如下:

①在時隙t的起始時刻，如果某VOQ的計數值VC＞0，且第p（=tmodP）個子調度器中對應VF位為0，則VF置1，VC減1，否則保持不變;

②在時隙t～t+P-1內，該子調度器按照預定的調度算法完成一次調度，并在時隙t+P-1結束前，將調度結果寫入VR寄存器，如果某VOQ獲得匹配，則將對應VF位清0，否則不變;

③調度器向IM模塊返回VR寄存器的結果;

④在時隙t+P起始時刻，該子調度器接收新的匹配請求，并與上一次調度中未獲得匹配的請求一起參與到新一輪的匹配過程;同時，在時隙t+P內，根據上一次匹配的結果，獲得匹配的VOQ將隊頭信元發送到OM模塊。

根據調度器的工作流程，可以得出完成一次調度的時間Tsch和子調度器數目P之間的關系:

從式（5）中可以看出，信元長度減少會增加子調度器數目，進而增加系統占用的資源。但是當端口數達到一定程度，采用長信元所需要的鏈路速率已經超出器件能承受的極限時，必須適當減少信元長度，以降低內部加速，這時，多子調度器技術是必須的。

5 實驗結果與分析

搭建一個C（8，4，6）Clos網絡為實驗平臺，端口速率為1Gbps，在不影響吞吐率的前提下，對所需的內部鏈路速率進行對比。這里采用了一種簡單實用的集中式正交匹配調度算法[8]。參照Gbit以太網的參數，式（2）中各變量取值如下:Cf=1Gbps，Lf=64～1518B，LI=20B，Ltag=4B。

當Ld取不同值時，在Lf的取值范圍內，對式（2）不等式右端求最大值，可以求出加速比和信元數據部分長度的關系如圖4所示。將圖4中所示曲線記為函數f（Ld），式（2）等價于S≥f（Ld）。

在實驗中，取F=125MHz，Bout_buffer=128bit，根據實際測試，調度算法完成一次匹配需要約48個時鐘周期。當使用單個調度器時，可以求得S=1.65，即內部鏈路速率為1.65Gbps。

圖4 信元數據部分長度與所需加速比的關系

當使用多子調度器技術時，時隙的長度不受調度算法的限制，因此信元長度也是任意的，只要16B的整數倍即可。將式（5）展開，可以得到式（6）。

根據式（6）可以得到在上述參數下，信元數據部分長度與所需子調度器數目的關系如圖5所示。

圖5 信元數據部分長度與所需子調度器數目的關系

可以根據圖4與圖5，結合鏈路速率和資源等限制，選取合適的信元長度。在實際的測試中，使用了Ld=32B，這時子調度器數目為2，內部鏈路速率為1.27Gbps。所需鏈路速率降低了約23%，這為系統的實現帶來好處，不但降低了系統功耗，而且擴大了芯片選型的范圍。

6 結束語

Clos交換網絡由于其模塊化結構和良好的可擴展性獲得了廣泛的關注，被看作是未來構建大容量交換網絡的基礎。然而，由于Clos網絡多路徑的特性，調度算法往往比較復雜，尤其是在端口數目較大情況下，問題更為突出。為解決這個問題，可以在交換網絡中增加多個子調度器，通過多個子調度器之間的并行計算，從而縮短時隙的長度。時隙長度直接影響到內部鏈路的加速，選擇合適的時隙長度，有利于降低內部鏈路加速。

在工程應用中，可先按照文中提供的算法計算出交換網絡所需的最低加速比，再根據系統參數來選擇合適的信元長度，結合實際中交換算法所需的時鐘周期數，計算出交換網絡所需的子調度器數目。這樣可以在端口數目增加的情況下，保證系統性能不受影響。

[1]史芳.一種新的星上交換連接控制實現方案[J].無線電通信技術，2007，33（1）:6-8.

[2]劉增基.交換原理與技術[M].北京:人民郵電出版社，2007:41-44.

[3]楊君剛，劉增基.混合交換機制三級Clos網絡分布式調度算法[J]，西安電子科技大學學報，2008，35（4）:581-585.

[4]CLOS C.A Study of Nonblocking Switching Networks[J].Bell System Technical Journal，1953，32:406-424.

[5]楊君剛.高速多級分組交換網絡若干關鍵技術的研究[D].西安:西安電子科技大學，2008.

[6]張樹旗，賈樹恒.一種支持變長分組的CIOQ交換結構[J].計算機應用，2005，25（7）:1491-1493.

[7]OKI E，Rojas-Cessa R，CHAO H J.A Pipeline-based Concurrent Round-robin Dispatching Scheme for Closnetwork Switches[C]//Communications，ICC 2002.IEEE International Conference on，2002，4:2121-2125.

[8]ENG K Y，KAROL M J，YEH Y S.A Growable Packet（ATM）SwitchArchitecture:DesignPrinciplesand Application[J].Communications，IEEE Transactions on，1992，40:423-430.