星上Clos交換網絡的分治調度算法

張茂森 邱智亮 高 雅 黎 軍

①(西安電子科技大學綜合業務網理論及關鍵技術國家重點實驗室 西安 710071)

②(空間微波技術國家重點實驗室 西安 710100)

1 引言

彎管式衛星在支持交互式通信和多方通信時存在兩個方面的限制：(1)在一個時間點只能從一個源接收信息；(2)為避免某源端向不同接收端發送多個相同的分組，需要在地面對數據進行復制和發送。這兩個限制使得彎管式衛星不可能用于交互式通信和多方通信[1]。具有星上處理(On-Board Processing,OBP)和星上交換(On-Board Switching, OBS)功能的再生式衛星可以在任意兩個或多個地面終端間建立全互聯網絡，因此會替代彎管式衛星，成為未來衛星通信的發展方向。

星上交換網絡決定了再生式衛星的容量、吞吐率、時延等關鍵屬性，是衛星通信中的核心組件。由于衛星信道容量有限，星上交換網絡應在任何業務模型下都能提供比較高的吞吐率，以減少因重傳而造成的帶寬浪費；其次由于衛星通信時延較大，應盡可能減少分組在衛星內部的排隊等待的時延[2]；最后，受限于宇航級芯片的容量，星上交換網絡無法像地面網絡設備一樣，通過使用大容量緩存和提高內部速率等方法解決丟包、時延等問題。

交換網絡的實現有多種方案。單級輸入排隊的Crossbar結構交換網絡能支持較高的接口速率，因此被廣泛用于Internet核心路由器。隨著衛星容量的增加，單級Crossbar結構由于受到器件工藝、調度算法等的限制，已逐漸接近性能極限，因此不適于衛星通信。CICQ(Combined Input-Crosspoint-Queued)結構交換網絡有非常好的吞吐率及時延性能，但是其交叉點緩存數目與交換網絡端口數的平方成正比，因此只適合于構建小規模的交換網絡。兩級負載均衡的Birkhoff-von Neumann交換結構的調度算法復雜度為O(1)[3]，適于構建高速交換網絡，但是由于其硬件實現是基于單級Crossbar結構，因此可擴展性也受到限制。光交換技術雖然能極大地提高交換容量，但是由于光隨機存取器件的缺乏，還不能滿足當前的需要[4]。

Clos交換網絡由于其模塊化的結構和無內部阻塞的特性而受到廣泛的重視，被認為是下一代大容量交換網絡的解決方案。而且隨著FSO(Free Space Optical)技術[5]的發展，衛星鏈路的數據速率可以達到數十 Gbps。根據地面網絡設備的設計經驗，Crossbar結構通常只適用于接口速率在10 Gbps或以下的路由器和交換機，更高接口速率的網絡設備一般采用Clos交換網絡。這是由于Clos交換網絡內部，每對輸入輸出端口間有多條鏈路可用，而Crossbar結構中只有一條鏈路，在相同條件下Clos交換網絡的內部阻塞更小，因此可以獲得更高的吞吐率以及更小的時延；其次由于宇航級芯片的資源和管腳數的限制，單顆芯片通常無法實現大容量交換網絡，而Clos交換網絡具有模塊化的結構和良好的可擴展性，因此可以使用多個小容量芯片構建大容量交換網絡。由以上原因可知，Clos交換網絡會成為未來大容量星上交換網絡的主要選擇。

為提高傳輸效率和簡化調度算法設計，現有高速交換網絡通常使用定長信元進行交換，變長分組在輸入端口處被分割為定長信元。在輸出端口處，定長信元被重組為變長分組，然后被發送到輸出鏈路上。傳輸一個定長信元的時間被定義為一個時隙。交換網絡內部的調度及信元傳輸都以時隙為單位。本文所述算法都基于定長信元交換。

下面首先介紹Clos交換網絡的結構及相關調度算法，然后介紹沖突域的概念和分治調度算法的執行過程，最后分析了分治調度算法的時間及硬件復雜度，并通過仿真驗證算法的時延及吞吐率性能。

2 Clos交換網絡的結構

Clos交換網絡是一種由小規模交換單元組成的多級交換結構。交換單元被排列為三級，分別稱為輸入級、中間級和輸出級。每一級中的交換單元通過唯一的鏈路與相鄰級的交換單元相連接。輸入級有k個n×m的交換單元，被稱為輸入級單元(Input Module, IM)；中間級有m個k×k的交換單元，被稱為中間級單元(Central Module, CM)；輸出級有k個m×n的交換單元，被稱為輸出級單元(Output Module, OM)。交換網絡的輸入(輸出)端口數為N，其中N=n×k。Clos交換網絡用m,n,k3個參數可以表示，上述Clos交換網絡可被簡記為C(m,n,k)。

Clos交換網絡中的交換單元可以設置內部緩存，以用來存儲不能及時發送的信元。根據內部緩存位置的不同，Clos交換網絡可以分為多種不同的結構，常見的如下：所有交換單元中都沒有緩存(Space-Space-Space, SSS)，CM和OM中有緩存(Space-Memory-Memory, SMM)，所有交換單元中都有緩存(Memory-Memory-Memory, MMM)，IM和OM中有緩存(Memory-Space-Memory, MSM)。SSS型Clos交換網絡需要解決所有模塊輸出端口的沖突，調度算法復雜度較高[6]。SMM型Clos交換網絡調度算法[7]的思路類似于兩級負載均衡的Birkhoff-von Neumann交換機[3]，調度算法非常簡單，但是存在信元亂序的問題，需要大量緩存對信元進行重排。MMM型Clos交換網絡在所有交換單元內部緩存信元，為避免亂序，需要通過反饋控制信元的發送順序[8]，硬件復雜度較高。因此，本文中選定MSM型Clos交換網絡作為星上交換網絡的設計方案，一方面 MSM 結構不需要用緩存對信元進行排序；另一方面，與其它結構相比，基于 MSM結構的調度算法相對簡單，有較低的硬件復雜度，適于構建星上交換網絡。

本算法中所使用的Clos交換網絡如圖1所示。IM 內部將信元按照輸出端口排隊(Virtual Output Queue, VOQ), CM內部是無緩存的Crossbar結構，OM 內部在輸出端口處設置有緩存，以解決輸出端口沖突。將IM(i)的第s+1個輸入端口記作IP(i,s)，第r+1個輸出端口記作P(i,r)，將OM(j)的第h+1個輸出端口記作 OP(j,h)，而將 IM(i)內存儲去往OP(j,h)信元的VOQ記作VOQ(i,j,h)。

MSM 型 Clos交換網絡中常用調度算法是CRRD(Concurrent Round-Robin Dispatching)類算法(包括 CRRD、CMSD(Concurrent Master-Slave round-robin Dispatching)[9]和SRRD(Static Round-Robin Dispatching)[10]等)。此類算法都分為兩個階段。第 1階段是 IM 內部的匹配，分為請求-應答-接受(Request-Grant-Accept, RGA)3個步驟，完成VOQ與IM輸出端口的匹配；第2階段是IM與CM之間的匹配，由CM對來自不同IM模塊，但是去往同一OM模塊的信元請求進行仲裁，并選擇其中一個進行應答。CRRD類算法的核心思想是利用仲裁器指針的去同步化效應，減少沖突并提高吞吐率。但是當業務不均衡時，指針不會完全去同步化，因此仍無法避免IM內已完成的匹配在CM內部發生沖突，造成吞吐率下降。

圖1 三級Clos交換網絡

3 沖突域

根據Clos網絡的拓撲結構可知，每個信元有m條路徑可選，每條路徑對應于一個 CM。而信元在CM中的輸出端口只由其目的OM決定，因此不同IM中去往同一OM的信元有可能在CM輸出端口處發生沖突。

為標記發生沖突的范圍，本文中將存儲去往同一OM信元的所有VOQ稱為一個沖突域。由沖突域的定義可知，競爭CM同一輸出端口的信元一定來自于同一沖突域。同時將IM(i)內存儲去往OM(j)信元的VOQ稱為一個子沖突域，記作VOQG(i,j)。C(3,3,3)中的沖突域和子沖突域如圖2所示，其中屬于同一沖突域的 VOQ用一種顏色標記，它們的信元會競爭標記有相同顏色的CM輸出端口。

MSM型Clos交換網絡調度算法的難點在于如何解決來自不同IM的信元在CM輸出端口的沖突。在引入了沖突域的概念后，CM 輸出端口發生沖突的范圍就被局限于對應的沖突域中。只要在沖突域內依次為每個CM分別選擇一個信元，就可以避免CM輸出端口處的沖突。Clos交換網絡的匹配問題被簡化為沖突域內如何為各CM選擇信元的問題。該思路類似于算法設計中的分治思想，因此本文中提出的調度算法被稱為分治調度算法。

4 分治調度算法

圖2 C(3,3,3)網絡中的沖突域

分治調度算法采用請求-應答模式進行沖突域內的信元選擇。請求包括VOQ向子沖突域的請求，以及子沖突域向CM的請求。相應地，應答包括CM向子沖突域的應答和子沖突域向 VOQ的應答。為實現對信元的選擇，首先需要為每一個子沖突域增加一個n輸入或門和一個仲裁器，其輸入均為子沖突域內VOQ請求信號(1=VOQ有效，0=VOQ無效)。或門用于產生子沖突域的請求信號(1=請求有效，0=請求無效)，仲裁器用于在子沖突域內對非空VOQ進行選擇和應答；其次，在IM每一個輸出端口處設置一個狀態位，記錄該端口是否可用(1=可用，0=已被占用)，只有當端口可用時，才會向對應CM 轉發子沖突域的請求；最后，還需要在每一個CM 內增加一個仲裁器，用于對子沖突域的請求進行選擇和應答。圖3所示為 C(3,3,3)網絡內，一個沖突域一次請求及應答的過程，其中虛線方框表示一個子沖突域，箭頭分別表示有效的請求和應答。

根據k和m的大小關系不同，分治調度算法的執行過程略有不同。當k≤m時，一個時隙被分為m個子時隙，每個子時隙內請求和應答的過程如下：

(1)請求

(a)在每個子時隙開始時，若子沖突域內存在非空且未被匹配的 VOQ(稱為有效 VOQ)時，或門的輸出為 1，表示子沖突域內請求有效，反之請求無效；

圖3 一個子時隙內請求和應答的操作

(b)第t+1(0≤t＜m)個子時隙內，VOQG(i,j)將對應或門的輸出信號發送給P(i,(j+t)modm)。如果該端口可用，則向CM((j+t)modm)對應的仲裁器轉發請求。

(2)應答

(a)CM內部的調度器從接收到的請求中選擇一個作為競爭的勝者，并向對應端口返回 1，同時向其它端口返回0；

(b)VOQG(i,j)接收來自CM((j+t)modm)的選擇結果。如果返回的選擇結果為 1，表示其請求獲得允許，VOQG(i,j)對應的仲裁器在其包含的有效VOQ中選擇一個，并在下一時隙通過CM((j+t)modm)發送其隊頭信元，同時標記 P(i,(j+t)modm)已被占用；如果返回為0，則VOQG(i,j)內的VOQ繼續參與后續匹配過程。

每個時隙開始時，所有 IM 輸出端口都是可用的。當端口被分配給某信元后，就不會再分配給其它信元，避免發生沖突。當 IM 輸出端口轉發請求時，只需將子沖突域的請求信號與輸出端口標志位做與運算即可。一個子時隙內，每個沖突域中只有一個 VOQ獲得應答，相當于每個沖突域為當前與之匹配的CM選擇了唯一信元。

由于以上過程共迭代m次，VOQG(i,j)會向每一個CM發送請求。當k≤m時，上述子沖突域與輸出端口的連接方式可以保證 IM(i)的每個輸出端口在一個子時隙內只會接收到一個子沖突域的請求，如圖4所示。而當k＞m時，如果仍采用上述連接方式，則在一個子時隙內，IM輸出端口會接收到多個子沖突域的請求，造成內部沖突。因此當k＞m時，一個時隙要分為k個子時隙，第t+1(0≤t＜k)個子時隙內 IM 內部的子沖突域與輸出端口的連接方式需要改為：P(i,r)接收來自VOQG(i,(r+t)modk)請求，并且向 VOQG(i,(r+t)modk)轉發來自CM(r)的選擇結果。其它操作與k≤m相同。

由于 IM 內的配置完全相同，因此在任意一個子時隙內，CM接收到的請求是來自同一沖突域的。這樣既避免了對不同 IM 分別進行配置，也極大地簡化了CM內部的硬件實現。經過多次迭代后，每個沖突域內會有多個信元被分配路由，而且信元間的路由不會發生沖突。

5 算法復雜度及性能分析

分治調度算法的復雜度分析分為時間復雜度和硬件復雜度兩部分。

(1)時間復雜度 分治調度算法的執行過程中，子沖突域內部選擇非空VOQ和CM對請求進行的選擇的過程可以并行完成，因此一次迭代的時間復雜度為max{lg(n),lg(k)}，整個算法所需要的迭代次數為max{m,k}，因此分治調度算法的時間復雜度為O(m ax{m,k}·max{lg(n),lg(k)})，當n=m=k時，分治調度算法的時間復雜度為O(nl g(N))。而相同條件下 CRRD類算法的時間復雜度為O(il g(N))，兩者基本相當。

(2)硬件復雜度 分治調度算法中仲裁器的硬件復雜度及數目決定了完成調度所需硬件資源的多少。每一個仲裁器的硬件復雜度與仲裁器的請求端口的數目成正比。分治調度算法中，每個 IM 的硬件復雜度為O(kn)=O(N)；在CM內部，分治調度算法只需要一個輸入端口數目為k的仲裁器，硬件復雜度為O(k)。而在CRRD類算法中每一個IM內部的硬件復雜度為O(mN)[9], CM 的硬件復雜度為O(k2)。因此，分治調度算法的硬件復雜度遠小于CRRD類算法。而且分治調度算法中的請求和應答信號都只有1位，而CRRD類算法中請求信息至少需要lg(k)位，因此分治調度算法極大地簡化了交換網絡的硬件實現。

分治調度算法的性能通過仿真進行驗證。仿真環境為C(8,8,8)網絡，并分別采用Bernoulli過程下的均勻業務和不均勻業務，以及突發業務對其進行驗證。CRRD類算法中，IM內部匹配迭代8次，以達到最佳性能。

(1)均勻業務 圖 5顯示了均勻業務下采用Bernoulli到達過程時各種算法的時延性能。幾種算法都可以達到100%的吞吐率，從圖5中可以看出，分治調度算法的時延比其它算法更低。

(2)非均勻業務 圖6顯示了非均勻業務下采用不同算法的吞吐率。業務的不均勻程度由不均衡因子ω確定。令λ為IP(i,s)的輸入業務，ρ為從IP(i,s)到OP(j,h)的業務，則

圖4 k≤m時，不同子時隙IM內部的連接方式

從圖6中可以看出，分治調度算法在所有非均衡因子下都可以達到至少 96.7%的吞吐率，而其它算法最低吞吐率則均不足75%，因此分治算法可以很好地滿足衛星通信中對丟包率的要求。

(3)突發業務 由于衛星通信往返時延較大，因此在 BTDAMA[11]、光 STDMA[12]等接入方式中，都采用了突發方式傳送用戶業務，以減少請求和分配鏈路資源時所占用的時間和鏈路資源。突發長度一般滿足指數分布，圖7中顯示了分治調度算法以及 CRRD類算法在突發業務模型(平均突發長度分別為8和16)下的時延性能。

從圖7中可以看出，突發業務下分治調度算法依然能夠獲得比其它算法更好的時延性能。分治調度算法能夠在各種業務模型下達到較低的時延和較高的吞吐率的原因有以下兩個方面：

(1)將 Clos網絡的匹配問題分解為沖突域內的信元選擇問題，限制了沖突發生的范圍，減少了沖突發生的可能，同時避免了IM內完成的匹配在CM輸出端口沖突而造成的性能損失。

(2)子沖突域依次向每一個CM發送請求，因此會獲得盡可能多的應答，增加了每時隙內信元發送的數目。

6 結束語

隨著衛星技術的發展，再生式衛星將替代傳統的彎管式衛星，成為未來衛星通信的發展方向。星上交換網絡是再生式衛星的核心組件之一。針對衛星通信對時延、丟包率、硬件復雜度等方面的要求，本文提出了基于 MSM 型 Clos網絡的分治調度算法。該算法通過引入沖突域的概念，將Clos網絡的匹配問題分解成沖突域為每個中間級模塊選擇信元的問題，降低了調度算法的硬件復雜度，提高了交換網絡的吞吐率。通過仿真驗證，該算法在各種業務模型下時延和吞吐率等方面的性能優于其它算法，很好地滿足了衛星環境的要求。

圖5 均勻業務下的時延性能

圖6 不均衡業務下的吞吐率性能

圖7 突發業務(突發平均長度分別為8和16)下的時延性能

[1]Gopal R, Arnold S,et al.. Regenerative satellite mesh system for realtime multi-party multimedia traffic[C]. 27th IET and AIAA International Communications Satellite Systems Conference(ICSSC), Edinburgh, United Kingdom, June 1-4,2009: 121-129.

[2]張怡, 周詮, 黎軍, 等. 星上交換系統輸入緩存調度算法[J].電子與信息學報, 2009, 31(6): 1429-1432.

Zhang Yi, Zhou Quan, Li Jun,et al.. An input-buffer scheduling algorithm in satellite switching system[J].Journal of Electronics&Information Technology, 2009, 31(6):1429-1432.for three-stage bufferless Clos network switches[J].IEEE Communications Magazine, 2003, 41(10): 46-54.

[3]Bing Hu, Yeung K L,et al.. Feedback-based scheduling for load-balanced two-stage switches[J].IEEE/ACM Transactions on Networking, 2010, 18(4): 1077-1090.

[4]Glick M. Optical interconnects in next generation data centers: an end to end view[C]. 16th IEEE Symposium on High Performance Interconnects, Stanford, CA, United States, Aug. 6-28, 2008: 178-181.

[5]Arimoto Y. Multi-gigabit free-space laser communications using compact optical terminal with bidirectional beacon tracking[C]. 2011 IEEE International Conference on Communications, Kyoto, Japan, June 5-9, 2011: 1-5.

[6]Chao H J, Zhigang J, Liew S Y,et al.. Matching algorithms

[7]Ruepp S, Rytlig A, Manolova A V,et al.. Performance evaluation of 100 gigabit ethernet switches under bursty traffic[C]. 15th International Conference on Optical Network Design and Modeling(ONDM), Bologna, Italy, Feb. 8-10,2011: 1-6.

[8]Dong Zi-qian, Roberto R C, Eiji O,et al.. Memory-memorymemory Clos-network packet switches with in-sequence service[C]. IEEE 12th International Conference on High Performance Switching and Routing(HPSR), Cartagena,Spain, July 4-6, 2011: 121-125.

[9]Eiji O, Jing Zhi-gang, Roberto R C,et al.. Concurrent round-robin-based dispatching schemes for Clos-network switches[J].IEEE/ACM Transactions on Networking, 2002,10(6): 830-844.

[10]Pun Kong-hong, Mounir H,et al.. Dispatching schemes for Clos-network switches[J].Computer Networks, 2004, 44(5):667-679.

[11]Xin Y, Zhou X, She Y,et al.. Improved burst target demand assignment multiple access(BTDAMA)for GEO satellite networks[C]. 2011 International Conference on Network Computing and Information Security(NCIS), Guilin, China,May 14-15, 2011: 173-176.

[12]Miniscalco W J, Lane S A,et al.. Optical space-time division multiple access[J].Journal of Lightwave Technology, 2012,30(11): 1771-1785.