張茂森 邱智亮 高 雅 黎 軍

①(西安電子科技大學綜合業(yè)務網(wǎng)理論及關(guān)鍵技術(shù)國家重點實驗室 西安 710071)

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

1 引言

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

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

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

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

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

下面首先介紹Clos交換網(wǎng)絡的結(jié)構(gòu)及相關(guān)調(diào)度算法，然后介紹沖突域的概念和分治調(diào)度算法的執(zhí)行過程，最后分析了分治調(diào)度算法的時間及硬件復雜度，并通過仿真驗證算法的時延及吞吐率性能。

2 Clos交換網(wǎng)絡的結(jié)構(gòu)

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

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

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

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

圖1 三級Clos交換網(wǎng)絡

3 沖突域

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

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

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

4 分治調(diào)度算法

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

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

根據(jù)k和m的大小關(guān)系不同，分治調(diào)度算法的執(zhí)行過程略有不同。當k≤m時，一個時隙被分為m個子時隙，每個子時隙內(nèi)請求和應答的過程如下：

(1)請求

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

圖3 一個子時隙內(nèi)請求和應答的操作

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

(2)應答

(a)CM內(nèi)部的調(diào)度器從接收到的請求中選擇一個作為競爭的勝者，并向?qū)丝诜祷?1，同時向其它端口返回0；

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

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

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

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

5 算法復雜度及性能分析

分治調(diào)度算法的復雜度分析分為時間復雜度和硬件復雜度兩部分。

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

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

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

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

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

圖4 k≤m時，不同子時隙IM內(nèi)部的連接方式

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

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

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

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

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

6 結(jié)束語

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

圖5 均勻業(yè)務下的時延性能

圖6 不均衡業(yè)務下的吞吐率性能

圖7 突發(fā)業(yè)務(突發(fā)平均長度分別為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]張怡, 周詮, 黎軍, 等. 星上交換系統(tǒng)輸入緩存調(diào)度算法[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.