鮑民權(quán)，邱智亮，張茂森，劉煥峰

（西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，陜西西安710071）

0 引言

隨著移動(dòng)通信、多媒體廣播業(yè)務(wù)的發(fā)展，人們對(duì)衛(wèi)星數(shù)據(jù)通信的要求更加迫切，這需要在衛(wèi)星上實(shí)現(xiàn)分組交換。星上交換除需要完成與地面交換相同的功能外，還受到芯片容量、功率及實(shí)現(xiàn)復(fù)雜度等多方面的限制[1]。多級(jí)交換網(wǎng)絡(luò)允許使用小容量芯片構(gòu)建大規(guī)模交換網(wǎng)絡(luò)，交換網(wǎng)絡(luò)的容量不再受到單芯片容量和引腳數(shù)目的限制。因此，當(dāng)構(gòu)建大容量星上交換網(wǎng)絡(luò)時(shí)，多級(jí)交換網(wǎng)絡(luò)結(jié)構(gòu)更具有優(yōu)勢(shì)[2]。現(xiàn)有大多數(shù)高速交換網(wǎng)絡(luò)內(nèi)部都采用定長(zhǎng)信元交換，由于變長(zhǎng)分組在被切片成定長(zhǎng)信元時(shí)，信元的利用率不可能達(dá)到100%，這就要求內(nèi)部鏈路速率高于外部鏈路速率。

在分析定長(zhǎng)信元長(zhǎng)度與內(nèi)部鏈路速率的關(guān)系的基礎(chǔ)上，給出了通過選取信元長(zhǎng)度來降低內(nèi)部鏈路速率的方法。交換網(wǎng)絡(luò)規(guī)模的擴(kuò)大，使完成一次調(diào)度的時(shí)間相應(yīng)增加，如果處理不當(dāng)，會(huì)對(duì)交換網(wǎng)絡(luò)性能造成影響[3]。介紹了交換網(wǎng)絡(luò)中的多子調(diào)度器技術(shù)，通過多個(gè)子調(diào)度器并行計(jì)算，完成整個(gè)交換網(wǎng)絡(luò)的路由調(diào)度，以有效消除交換網(wǎng)絡(luò)規(guī)模增加對(duì)系統(tǒng)性能造成的影響。

1 Clos網(wǎng)絡(luò)模型

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

Clos網(wǎng)絡(luò)的結(jié)構(gòu)如圖1所示。其中，IM表示輸入級(jí)模塊，CM表示中間級(jí)模塊，OM表示輸出級(jí)模塊;VOQ表示輸入級(jí)模塊的虛擬輸出隊(duì)列，VIQ表示輸出級(jí)模塊中虛擬輸入隊(duì)列。

圖1 Clos網(wǎng)絡(luò)結(jié)構(gòu)

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

2 隊(duì)列管理技術(shù)

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

在實(shí)際的工程中，可以使用共享緩存和隊(duì)列管理實(shí)現(xiàn)VOQ技術(shù)[6]。采用共享緩存不需要為每一個(gè)VOQ隊(duì)列單獨(dú)分配緩存，節(jié)省了存儲(chǔ)資源。當(dāng)有分組到達(dá)時(shí)，輸入端口向隊(duì)列管理模塊發(fā)出申請(qǐng)，隊(duì)列管理模塊將分組信息加入對(duì)應(yīng)的VOQ中，同時(shí)在共享緩存中給當(dāng)前分組分配一定的空間，這個(gè)過程被稱作分組的入隊(duì);VOQ根據(jù)自己隊(duì)列情況向交換網(wǎng)絡(luò)的調(diào)度器發(fā)送請(qǐng)求，調(diào)度器根據(jù)所有VOQ的請(qǐng)求進(jìn)行調(diào)度;當(dāng)完成一次調(diào)度后，如果VOQ獲得在交換網(wǎng)絡(luò)內(nèi)部發(fā)送數(shù)據(jù)的機(jī)會(huì)，分組內(nèi)容會(huì)從共享緩存中被讀出，以定長(zhǎng)信元的形式在交換網(wǎng)絡(luò)內(nèi)部傳輸，同時(shí)VOQ修改隊(duì)列信息，這個(gè)過程被稱作分組的出隊(duì)。

交換網(wǎng)絡(luò)內(nèi)部的定長(zhǎng)信元需要在OM模塊的輸出端口處被組裝成變長(zhǎng)分組。因此，每個(gè)輸出端口都要有相應(yīng)的輸出緩存來存儲(chǔ)整個(gè)分組。對(duì)于OM模塊的每一個(gè)輸出端口，最多同時(shí)有k個(gè)IM模塊同時(shí)向該端口發(fā)送信元，這要求每個(gè)輸出端口至少要維護(hù)k個(gè)輸出隊(duì)列，被稱為VIQ，而每一個(gè)輸出級(jí)模塊需要維護(hù)的輸出隊(duì)列數(shù)目為n×k個(gè)，VIQ也可以使用共享緩存和隊(duì)列管理來實(shí)現(xiàn)。

3 信元長(zhǎng)度和鏈路加速比的關(guān)系

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

當(dāng)交換網(wǎng)絡(luò)內(nèi)部采用定長(zhǎng)信元交換時(shí)，實(shí)際傳送的內(nèi)容總是大于分組的實(shí)際長(zhǎng)度，在設(shè)計(jì)交換網(wǎng)絡(luò)時(shí)，內(nèi)部鏈路速率要高于外部端口速率。內(nèi)部鏈路速率越高，硬件實(shí)現(xiàn)的難度就越大。因此，在滿足無阻塞交換的前提下，需要盡可能地降低內(nèi)部鏈路速率。通過分析發(fā)現(xiàn)，當(dāng)外部端口速率固定時(shí)，影響內(nèi)部鏈路速率的關(guān)鍵因素是定長(zhǎng)信元的長(zhǎng)度，信元長(zhǎng)度決定了傳輸同樣長(zhǎng)度分組時(shí)信元的利用率，也就決定了內(nèi)部鏈路的加速。

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

式（1）左邊是交換網(wǎng)絡(luò)內(nèi)部傳輸一個(gè)分組所需最小時(shí)間，右邊是端口處接收對(duì)應(yīng)長(zhǎng)度分組所需的時(shí)間。為保證無阻塞傳輸，內(nèi)部傳輸時(shí)間應(yīng)小于等于端口處傳輸所用時(shí)間。式（1）可轉(zhuǎn)化為式（2）:

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

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

式中，Tslot=Lc/Cc表示一個(gè)時(shí)隙的長(zhǎng)度，則共享緩存讀取端口的位寬Bout_buffer滿足式（4）:

式中，F(xiàn)表示共享緩存讀取時(shí)鐘的頻率，現(xiàn)有數(shù)字系統(tǒng)數(shù)據(jù)位寬一般都是2的整數(shù)次冪，因此不等式右端的計(jì)算結(jié)果需要向上對(duì)2的整數(shù)次冪取整。

4 子調(diào)度器技術(shù)

當(dāng)交換網(wǎng)絡(luò)中只有一個(gè)調(diào)度器時(shí)，必須在一個(gè)時(shí)隙內(nèi)完成一次調(diào)度，否則系統(tǒng)吞吐率會(huì)下降。如果交換網(wǎng)絡(luò)端口數(shù)目非常大，則完成一次調(diào)度所需的時(shí)間也會(huì)很長(zhǎng)，時(shí)隙長(zhǎng)度也會(huì)隨之增大，交換網(wǎng)絡(luò)不得不使用較長(zhǎng)的信元。為消除端口數(shù)目增加對(duì)時(shí)隙長(zhǎng)度帶來的影響，可以在交換網(wǎng)絡(luò)中增加多個(gè)調(diào)度器，每一個(gè)調(diào)度器的結(jié)構(gòu)與原調(diào)度器類似，稱之為子調(diào)度器[7]。當(dāng)多個(gè)子調(diào)度器并行工作時(shí)，允許每個(gè)子調(diào)度器用多個(gè)時(shí)隙完成一次調(diào)度。

當(dāng)使用3個(gè)子調(diào)度器時(shí)，工作過程如圖2所示，每個(gè)子調(diào)度器允許使用3個(gè)時(shí)隙完成一次調(diào)度。每個(gè)時(shí)隙開始時(shí)，請(qǐng)求被發(fā)往某一子調(diào)度器;該調(diào)度器可以使用3個(gè)時(shí)隙完成一次調(diào)度，在完成該次調(diào)度過程中產(chǎn)生的請(qǐng)求由其他子調(diào)度器進(jìn)行處理;每個(gè)時(shí)隙結(jié)束后，都有相應(yīng)的子調(diào)度器返回調(diào)度結(jié)果，指導(dǎo)下一時(shí)隙內(nèi)交換網(wǎng)絡(luò)中信元的傳輸，因此交換網(wǎng)絡(luò)的吞吐率不會(huì)因?yàn)檎{(diào)度時(shí)間的增加而下降。

圖2 有3個(gè)子調(diào)度器時(shí)的工作流程

當(dāng)使用多子調(diào)度器時(shí)，IM模塊和調(diào)度器需要有相應(yīng)的改變。IM模塊需要為每一個(gè)VOQ添加一個(gè)計(jì)數(shù)（VC），表示對(duì)應(yīng)VOQ中未發(fā)送匹配請(qǐng)求的信元數(shù)目;當(dāng)有新分組到達(dá)時(shí)，根據(jù)分組長(zhǎng)度，VC增加相應(yīng)數(shù)目。當(dāng)發(fā)送一個(gè)匹配請(qǐng)求時(shí)，VC減1。同時(shí)在子調(diào)度器中添加VOQ標(biāo)志位（VF）和調(diào)度結(jié)果寄存器（VR）。子調(diào)度器結(jié)構(gòu)如圖3所示。

圖3 子調(diào)度器結(jié)構(gòu)

圖3中調(diào)度器模塊實(shí)現(xiàn)預(yù)定的調(diào)度算法。VF和VR與IM模塊中的VOQ相對(duì)應(yīng)。VF的值為0或1，1表示該子調(diào)度器收到了對(duì)應(yīng)VOQ發(fā)送的調(diào)度請(qǐng)求，0表示沒有收到請(qǐng)求;VR表示對(duì)一個(gè)調(diào)度請(qǐng)求的結(jié)果，它包含2部分:①對(duì)應(yīng)VOQ的請(qǐng)求是否獲得匹配;②獲得匹配后該信元所需的路由信息。當(dāng)使用P個(gè)子調(diào)度器時(shí)，調(diào)度器工作流程如下:

①在時(shí)隙t的起始時(shí)刻，如果某VOQ的計(jì)數(shù)值VC＞0，且第p（=tmodP）個(gè)子調(diào)度器中對(duì)應(yīng)VF位為0，則VF置1，VC減1，否則保持不變;

②在時(shí)隙t～t+P-1內(nèi)，該子調(diào)度器按照預(yù)定的調(diào)度算法完成一次調(diào)度，并在時(shí)隙t+P-1結(jié)束前，將調(diào)度結(jié)果寫入VR寄存器，如果某VOQ獲得匹配，則將對(duì)應(yīng)VF位清0，否則不變;

③調(diào)度器向IM模塊返回VR寄存器的結(jié)果;

④在時(shí)隙t+P起始時(shí)刻，該子調(diào)度器接收新的匹配請(qǐng)求，并與上一次調(diào)度中未獲得匹配的請(qǐng)求一起參與到新一輪的匹配過程;同時(shí)，在時(shí)隙t+P內(nèi)，根據(jù)上一次匹配的結(jié)果，獲得匹配的VOQ將隊(duì)頭信元發(fā)送到OM模塊。

根據(jù)調(diào)度器的工作流程，可以得出完成一次調(diào)度的時(shí)間Tsch和子調(diào)度器數(shù)目P之間的關(guān)系:

從式（5）中可以看出，信元長(zhǎng)度減少會(huì)增加子調(diào)度器數(shù)目，進(jìn)而增加系統(tǒng)占用的資源。但是當(dāng)端口數(shù)達(dá)到一定程度，采用長(zhǎng)信元所需要的鏈路速率已經(jīng)超出器件能承受的極限時(shí)，必須適當(dāng)減少信元長(zhǎng)度，以降低內(nèi)部加速，這時(shí)，多子調(diào)度器技術(shù)是必須的。

5 實(shí)驗(yàn)結(jié)果與分析

搭建一個(gè)C（8，4，6）Clos網(wǎng)絡(luò)為實(shí)驗(yàn)平臺(tái)，端口速率為1Gbps，在不影響吞吐率的前提下，對(duì)所需的內(nèi)部鏈路速率進(jìn)行對(duì)比。這里采用了一種簡(jiǎn)單實(shí)用的集中式正交匹配調(diào)度算法[8]。參照Gbit以太網(wǎng)的參數(shù)，式（2）中各變量取值如下:Cf=1Gbps，Lf=64～1518B，LI=20B，Ltag=4B。

當(dāng)Ld取不同值時(shí)，在Lf的取值范圍內(nèi)，對(duì)式（2）不等式右端求最大值，可以求出加速比和信元數(shù)據(jù)部分長(zhǎng)度的關(guān)系如圖4所示。將圖4中所示曲線記為函數(shù)f（Ld），式（2）等價(jià)于S≥f（Ld）。

在實(shí)驗(yàn)中，取F=125MHz，Bout_buffer=128bit，根據(jù)實(shí)際測(cè)試，調(diào)度算法完成一次匹配需要約48個(gè)時(shí)鐘周期。當(dāng)使用單個(gè)調(diào)度器時(shí)，可以求得S=1.65，即內(nèi)部鏈路速率為1.65Gbps。

圖4 信元數(shù)據(jù)部分長(zhǎng)度與所需加速比的關(guān)系

當(dāng)使用多子調(diào)度器技術(shù)時(shí)，時(shí)隙的長(zhǎng)度不受調(diào)度算法的限制，因此信元長(zhǎng)度也是任意的，只要16B的整數(shù)倍即可。將式（5）展開，可以得到式（6）。

根據(jù)式（6）可以得到在上述參數(shù)下，信元數(shù)據(jù)部分長(zhǎng)度與所需子調(diào)度器數(shù)目的關(guān)系如圖5所示。

圖5 信元數(shù)據(jù)部分長(zhǎng)度與所需子調(diào)度器數(shù)目的關(guān)系

可以根據(jù)圖4與圖5，結(jié)合鏈路速率和資源等限制，選取合適的信元長(zhǎng)度。在實(shí)際的測(cè)試中，使用了Ld=32B，這時(shí)子調(diào)度器數(shù)目為2，內(nèi)部鏈路速率為1.27Gbps。所需鏈路速率降低了約23%，這為系統(tǒng)的實(shí)現(xiàn)帶來好處，不但降低了系統(tǒng)功耗，而且擴(kuò)大了芯片選型的范圍。

6 結(jié)束語

Clos交換網(wǎng)絡(luò)由于其模塊化結(jié)構(gòu)和良好的可擴(kuò)展性獲得了廣泛的關(guān)注，被看作是未來構(gòu)建大容量交換網(wǎng)絡(luò)的基礎(chǔ)。然而，由于Clos網(wǎng)絡(luò)多路徑的特性，調(diào)度算法往往比較復(fù)雜，尤其是在端口數(shù)目較大情況下，問題更為突出。為解決這個(gè)問題，可以在交換網(wǎng)絡(luò)中增加多個(gè)子調(diào)度器，通過多個(gè)子調(diào)度器之間的并行計(jì)算，從而縮短時(shí)隙的長(zhǎng)度。時(shí)隙長(zhǎng)度直接影響到內(nèi)部鏈路的加速，選擇合適的時(shí)隙長(zhǎng)度，有利于降低內(nèi)部鏈路加速。

在工程應(yīng)用中，可先按照文中提供的算法計(jì)算出交換網(wǎng)絡(luò)所需的最低加速比，再根據(jù)系統(tǒng)參數(shù)來選擇合適的信元長(zhǎng)度，結(jié)合實(shí)際中交換算法所需的時(shí)鐘周期數(shù)，計(jì)算出交換網(wǎng)絡(luò)所需的子調(diào)度器數(shù)目。這樣可以在端口數(shù)目增加的情況下，保證系統(tǒng)性能不受影響。

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

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

[3]楊君剛，劉增基.混合交換機(jī)制三級(jí)Clos網(wǎng)絡(luò)分布式調(diào)度算法[J]，西安電子科技大學(xué)學(xué)報(bào)，2008，35（4）:581-585.

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

[5]楊君剛.高速多級(jí)分組交換網(wǎng)絡(luò)若干關(guān)鍵技術(shù)的研究[D].西安:西安電子科技大學(xué)，2008.

[6]張樹旗，賈樹恒.一種支持變長(zhǎng)分組的CIOQ交換結(jié)構(gòu)[J].計(jì)算機(jī)應(yīng)用，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.