楊宜鎮(zhèn) 管紅光 周煒 吳致遠

摘 要：本文首先對CLOS網(wǎng)絡(luò)進行了簡單的介紹，然后結(jié)合CLOS網(wǎng)絡(luò)在路由算法中的應(yīng)用，詳細闡述了CLOS網(wǎng)絡(luò)的路由算法。

關(guān)鍵詞：CLOS 網(wǎng)絡(luò) 路由 擁塞 交換結(jié)構(gòu)

中圖分類號：TN915.07 文獻標(biāo)識碼：A 文章編號：1674-098X（2012）12（a）-000-03

1 CLOS網(wǎng)絡(luò)簡介

最初的Cols網(wǎng)絡(luò)是一種經(jīng)典的嚴(yán)格無阻塞的多級互連網(wǎng)絡(luò)。由Charles Clos于1953年提出。是在Benes網(wǎng)絡(luò)的基礎(chǔ)上演變而來，該網(wǎng)絡(luò)由于在通信網(wǎng)和多處理器計算機系統(tǒng)中被廣泛采用，因而受到廣泛重視，從CLOS的提出以來，人們對其拓撲結(jié)構(gòu)、連接特性和控制算法進行了較為深入的研究，并取得了不少成果。

1.1 CLOS網(wǎng)絡(luò)的定義

CLOS網(wǎng)絡(luò)是由多個集成單元（又稱交換單元）組成，每個集成單元包含n個輸入端口，m個輸出端口（m>1，n>1，如果m=n，即為對稱CLOS網(wǎng)絡(luò)）。任意的前級到任意中央級有且只有一個連接供使用，同樣任意的中央級到任意的后級有且只有一個連接。也就是說，從stage1的任意一個集成單元到stage2的任意一個集成單元，有且僅有一條連線（或者說一條路徑），同理，對stage2到stage3也是如此。但是我們可以發(fā)現(xiàn)，從stage1的任意一個集成單元到stage3中的任意一個集成單元有m條路徑。但是，這也并非指這個網(wǎng)絡(luò)完全沒有內(nèi)部競爭，要使它達到嚴(yán)格無阻塞，必須滿足一定的條件，這里的條件在三級COLS網(wǎng)路結(jié)構(gòu)中有更詳細的

討論。

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

1.2 CLOS網(wǎng)絡(luò)的設(shè)計

多級交換結(jié)構(gòu)之間的不同取決于各交換單元之間的互連形式， 在多級交換結(jié)構(gòu)中，級數(shù)越少，交換延遲也就越小，但交換通路也相應(yīng)減少，這導(dǎo)致碰撞阻塞的更容易產(chǎn)生，因此多級交換結(jié)構(gòu)拓撲的確定有一個各項性能之間的折中。各項性能包括：交換延時、交換通路數(shù)目、碰撞概率、輸入級與輸出級的規(guī)模、集成單元的規(guī)格（就是交換單元的輸入端n輸出端m，一般把m×n 稱為集成單元的規(guī)格），還有芯片的制造工藝能力限制以及具體使用的網(wǎng)路交換設(shè)備具體設(shè)計等諸多因素。三級CLOS網(wǎng)絡(luò)結(jié)構(gòu)是CLOS網(wǎng)絡(luò)最典型的一種結(jié)構(gòu)，后面出現(xiàn)的5級、7級、9級等結(jié)構(gòu)也是在3級CLOS網(wǎng)絡(luò)結(jié)構(gòu)的基礎(chǔ)上，加以改進而成。比如將3級CLOS網(wǎng)路結(jié)構(gòu)的第二級（stage2）換成一個3級的CLOS結(jié)構(gòu)，就形成了5級CLOS網(wǎng)絡(luò)結(jié)構(gòu)。

1.2.1 三級CLOS網(wǎng)絡(luò)結(jié)構(gòu)

Clos網(wǎng)絡(luò)使用非方形交換單元構(gòu)，典型的CLOS網(wǎng)絡(luò)是三級全互連對稱網(wǎng)絡(luò)，三級：stage1、stage2、stage3，對稱：入線數(shù)目=出線數(shù)目，三級對稱Clos網(wǎng)絡(luò)C（m，m，r）的輸入級有r個n×m交叉開關(guān)，中間級有m個r×r交叉開關(guān)，輸出級有r個m×n交叉開關(guān)，網(wǎng)絡(luò)共有N=n×r個輸入與輸出端，每個中間級開關(guān)與每個輸入和輸出開關(guān)有且僅有1條鏈路連接。

圖2 三級CLOS網(wǎng)絡(luò)結(jié)構(gòu)示意圖

從直觀上看，相鄰兩列的交換單元為全連接是交換性能最好的一種，但全連接方式成本較為昂貴，相互連線眾多，需要更多時間調(diào)度相對多的輸入端口，影響了處理速度。因此非全連接形交換有著更為經(jīng)濟的應(yīng)用。CLOS網(wǎng)絡(luò)是得到廣泛研究的一種多級交換結(jié)構(gòu)，它的特點在于可伸縮性、固定交換時延、數(shù)據(jù)傳輸?shù)淖月酚尚耘c有序性。由于自路由性，其數(shù)據(jù)轉(zhuǎn)發(fā)過程非常簡單，數(shù)據(jù)信元能并行通過該結(jié)構(gòu)，但是在信元交換負荷接近網(wǎng)絡(luò)信元交換負荷的極限時，但如果超過一個信元在同一時刻到達一個交換單元的話，就會產(chǎn)生碰撞沖突。因此，在設(shè)計CLOS交換結(jié)構(gòu)時，如何處理好擁塞沖突，是考慮各項性能折中的一個重要因素之一。

在CLOS網(wǎng)絡(luò)交換結(jié)構(gòu)中，m、n值的選取是決定網(wǎng)絡(luò)的交換性能2個重要參數(shù)。結(jié)合上圖，做以下分析：⑴當(dāng)m=n的時候必須要重排才能達到完全無阻塞的目的，完全無阻塞就是指它所有輸入輸出級的端口都被業(yè)務(wù)占滿的情況，這種結(jié)構(gòu)就是我們后期需要研究的可重排無阻塞網(wǎng)絡(luò)，它消耗的資源是最小的。⑵m=2n-1的時候不需要任何重排，也就是說只要業(yè)務(wù)要求的輸入輸出口空閑，不管它怎樣路由都不會出現(xiàn)阻塞，這種結(jié)構(gòu)耗的資源是最多的。⑶n

無阻塞：就是指即任何一條輸入到任何一條輸出都必定能找到一條路由，而不會出現(xiàn)阻塞。

可重排：在超過一個信元同一時刻到達一個交換單元的，產(chǎn)生碰撞沖突的情況下，通過對已有的連接重新選路來建立一個連接，來解決碰撞沖突的方法。

2 CLOS網(wǎng)絡(luò)結(jié)構(gòu)的路由算法

前面提到過，設(shè)計CLOS網(wǎng)絡(luò)結(jié)構(gòu)，其網(wǎng)絡(luò)機構(gòu)的交換性能：包括伸縮性、交換時延、數(shù)據(jù)傳輸?shù)淖月酚尚耘c有序性，還有一個最重要的因素就是如何處理網(wǎng)絡(luò)交換的碰撞沖突，也稱為擁塞。

有的人可能會問，既然有嚴(yán)格無阻塞網(wǎng)絡(luò)，為什么不直接使用嚴(yán)格無阻塞技術(shù)呢？當(dāng)然，無阻塞網(wǎng)絡(luò)當(dāng)然是我們所追求的理想目標(biāo)。但是，為了增加容量和降低阻塞，必須大量上調(diào)m和n的數(shù)量，會使實現(xiàn)交換單元的數(shù)量和交換網(wǎng)絡(luò)的技術(shù)成本大大增加。我們研究CLOS網(wǎng)絡(luò)結(jié)構(gòu)，就是要研究使設(shè)計CLOS網(wǎng)絡(luò)結(jié)構(gòu)的代價與網(wǎng)絡(luò)的交換性能的折中達到最優(yōu)化設(shè)計。所以上面提到的完全無阻塞網(wǎng)絡(luò)結(jié)構(gòu)不在本文的研究范圍。

評價一種路由算法好不好，其實就是看其總體得到的阻塞概率大小，要達到最小阻塞概率，那么它的每一次業(yè)務(wù)所走路徑對后序業(yè)務(wù)的影響應(yīng)該盡可能的小，達到這個目的方法會有很多種，下面僅從兩個角度分別講述兩種路由的算法思想。

2.1 優(yōu)先級篩選中間模塊法

好的路由算法應(yīng)該是在隨機給定業(yè)務(wù)的情況下，通過該算法找到的路徑給后來的業(yè)務(wù)留下了最大的可用空間，當(dāng)我們每次都這樣選擇路徑的時候，也就是最大程度地降低了后來業(yè)務(wù)發(fā)生阻塞的可能性。對于每一個業(yè)務(wù)可能存在多條路徑，也就是有多個中間模塊可用，那么我們要做的就是極好地利用clos的結(jié)構(gòu)特點，用優(yōu)先級方式篩選出最適合的中間模塊。

2.1.1 當(dāng)前業(yè)務(wù)對后面業(yè)務(wù)造成的影響

假設(shè)當(dāng)前業(yè)務(wù)為（ab），a為輸入端口，b為輸出端口，f為a所在的輸入單元編號，g為b所在的輸出單元編號，中間可用的交換單元集合為V，V代表的是所有中間模塊中恰恰輸入口f和輸出口g都空閑的單元，那么此業(yè)務(wù)的路徑選擇也就是對中間交換單元的選擇，也就是選出僅僅對f，g的后序剩余端口有關(guān)的業(yè)務(wù)產(chǎn)生的影響最小的單元。因為每個輸入輸出級的單元都能與中間模塊相連，且對于每個中間單元來說只能連接一次，如果我們選中了V中的一個，那么與f，g單元的后續(xù)剩余端口有關(guān)的業(yè)務(wù)將不能再與此中間單元相連，而除f，g以外對后來其它單元上需要經(jīng)過此中間單元上的業(yè)務(wù)沒有任何影響，那么我們要做的就是找到最合適的中間單元，使f，g的后序剩余端口還能最大可能地連接到每一個輸出或輸入單元，如圖3所示：

圖3 三級CLOS網(wǎng)絡(luò)業(yè)務(wù)交換模擬圖

2.1.2 尋找最適合的中間模塊

在分析了當(dāng)前業(yè)務(wù)對后續(xù)業(yè)務(wù)造成的影響之后，要解決的問題就是建立一個算法模型，通過該模型的算法來尋找出最適合的中間模塊。為了讓大家更好的理解該算法的思想，先對描述該算法中用到的符號做一下說明：

ab：代表一條業(yè)務(wù)流，a為輸入單元的輸入端口，b為輸出單元的輸出端口，

f：a所在的輸入單元編號

g：b所在的輸出單元編號

U：能同時和f，g連通的中間單元的集合（圖4中顯示的中間2，3單元）

V：所有還能與f單元相連的中間單元的集合（圖4中顯示的中間前三個單元）

W：所有還能與g單元相連的中間單元的集合（圖4中顯示的中間后三個單元）

Fout（V）：V內(nèi)所有單元的空閑輸出口集合

Fin（W）：W內(nèi)所有單元的空閑輸入口集合

很顯然，，。我們尋找最適合的中間單元的原則就是：從U中選擇一個單元，使得除去這個單元后，f，g的后序剩余端口還能最大可能地連接到每一個輸出或輸入單元，整個過程可以按以下步驟進行：

首先從U中找出所有跟f，g的后序剩余端口業(yè)務(wù)相關(guān)的中間單元V和W：

對于V內(nèi)的每個單元，總能找到唯一的一條路徑與輸入單元f相連，所以我們只看是否能通過它的空閑輸出端口連接到任意的輸出單元，如圖4中顯示，記下它的空閑輸出端口output[i] ，集合Fout（V）（i為中間模塊的端口號，假設(shè)其規(guī)格為y×y，那么（0≤i≤y）；

對于W內(nèi)的每個單元，總能找到唯一的一條路徑與輸出單元g相連，所以我們也只看是否能通過它的空閑輸入端口連接到任意的輸入單元，記下它的空閑輸入端口號input[i]集合Fin（W）；

經(jīng)過步驟1之后，我們可以發(fā)現(xiàn)輸入單元f的剩余端口到任意輸出單元的所有能成功路由的個數(shù)就等于Fout（V）里不同元素的個數(shù)（如圖4中所示2.3單元的最后一個輸出端口都是白色圓圈，那么我們就說他們是相同元素），輸出單元g的剩余端口到任意輸入單元的所有能成功路由個數(shù)等于Fin（W）里不同元素的個數(shù)，相同元素就代表了相同的空閑端口，相同元素出現(xiàn)的次數(shù)就是空閑次數(shù)。

其次尋從U中尋找最適合的中間單元，使得f，g的后序剩余端口還能最大可能地連接到每一個輸出或輸入單元。假設(shè)=，當(dāng)F內(nèi)不同元素的個數(shù)最多的時候我們?nèi)ax，這時候，通過該算法找到的路徑給后來的業(yè)務(wù)留下了最大的可用空間。那么我們的目標(biāo)就是在U里找到一個最好的單元，使得除去這個單元后F=max（）。這就是該模型的最優(yōu)目標(biāo)。

圖4 尋找中間交換模塊示意圖

下面結(jié)合上圖，通過1個例子來說明該模型的決策過程。為了避免圖形不至于太混亂，上圖中有部分連線沒有畫出來。

例子說明：由于圖4中3～n之間的單元沒有畫出來，所以我們只對前3個單元進行分析，n個單元的分析思路是一樣的。假設(shè)output[i]是中間模塊V的所有輸出端口，F(xiàn)out（V）是output[i]中空閑端口的集合，也就是圖中所有中間單元輸出端的白色圓圈，這個集合內(nèi)的每個元素就是這些白色圓圈的編號，每個中間單元的端口編號都是從0開始，比如說中間模塊包含1.2.3單元，1單元的空閑輸出端也就是白色圓圈編號為{0.2.4.5}，2單元的為{1.6}，3單元的為{0.1.2.5.6}。那么Fout（V）的所有元素就為{（0.2.4.5），（1.6），（0.1.2.5.6） }，其中0.1.2.5.6都出現(xiàn)了重復(fù)， 說明他們有相同的空閑端口，且都出現(xiàn)了2次。說明分別都有2個單元上這些端口是空閑的，4只出現(xiàn)了一次，說明只有一個單元上4端口是空閑的，F(xiàn)out（V）里不相同的元素為{0.1.2.4.5.6}，說明輸入單元f的剩余端口能到達6個輸出單元，如果我們令3單元的3號輸出端口也空閑，那么我們可以做如下比較：

（1）假設(shè)從a->b的業(yè)務(wù)流選擇中間模塊的2單元，那么f和g單元剩下的端口業(yè)務(wù)將再也不能從2這個單元路由，我們在計算F的時候就必須忽略掉跟這個單元有關(guān)的所有空閑端口，那么結(jié)合上圖可以得出：

Fout（V）={（0.2.4.5），（0.1.2.5.6）}，F(xiàn)out（V）內(nèi)的不同元素為{0.1.2.4.5.6}；

Fin（W）={（1.2.5），（1.2. 4.5.6）}，F(xiàn)in（W）內(nèi)的不同元素為{1.2.3.4.5.6}；

F=max（）={（0.1.2.3.4.5.6）， （1.2.3.4.5.6）}，那么F的最大值就為不同元素個數(shù)13，也就是說當(dāng)選擇2單元的時候f單元的剩余端口還能到達7個輸出單元，而g單元的剩余端口還能到達6個輸入單元。

（2）同理，假設(shè)從a->b的業(yè)務(wù)流選擇中間模塊的3單元，結(jié)合圖4可以得出：

Fout（V）={（0.2.4.5），（1.6）}，F(xiàn)out（V）內(nèi)的不同元素為{0.1.2.4.5.6}；

Fin（W）={（1.2.5），（1.2.4）}，F(xiàn)in（W）內(nèi)的不同元素為{1.2.4.5}；

F=max（）={（0.1.2.4.5.6），（1.2.4.5）}，那么F的最大值就是不同元素的個數(shù)10，也就是說當(dāng)選擇3單元的時候f單元的剩余端口還能到達6個輸出單元，而g單元的剩余端口還能到達4個輸入單元。

通過上面的比較，我們應(yīng)該選選取F值較大的2單元。

如果上面2中情況得處的F的最大值相等，也就是在選擇不同的中間單元之后得到的F值最大的單元不止一個的時候，可以選取內(nèi)元素個數(shù)最多的單元，這樣的話，在f，g單元的剩余端口能最大可能地到達輸出/輸入端的時候，也給予了最多的路徑選擇。如果出現(xiàn)F的最大值相等，并且內(nèi)元素個數(shù)也相等的情況，可以隨機或者按照篩選的先后順序選取其中的一個單元也是可行的。這種情況，在業(yè)務(wù)交換負荷很低的情況，是可能出現(xiàn)的。

2.2 最優(yōu)選路路由算法

2.2.1 傳統(tǒng)CLOS網(wǎng)絡(luò)路由選路算法思想

假設(shè)網(wǎng)絡(luò)是由規(guī)格為 n×m的集成單元組成（n代表集成單元輸入端口數(shù)目，m代表輸出端口數(shù)）。給定輸入端口X（因為整個網(wǎng)絡(luò)結(jié)構(gòu)對外是一個整體，所以這里的X與網(wǎng)絡(luò)結(jié)構(gòu)中某個具體集成單元的端口編號是有區(qū)別的，如果網(wǎng)絡(luò)輸入/輸出端有8個集成單元，那么X可以取 1～n×8之間的任何值，表示業(yè)務(wù)從X端口進入）；給定輸出端口Y（這里的Y，跟前面提到的X相同，表示業(yè)務(wù)要到達與Y端口相連的設(shè)備），路由算法描述如下：

對于給定的輸入端口X，由X/n向上取整得到i，將第i個交換單元的輸出端口中沒有被占用的端口放在一個集合{I}里（已經(jīng)被占用的端口視為無效端口），此時{I}集合里的端口號表示可以和第一級建立連接的第二級的交換單元編號。

同樣，對于給定的輸出端口Y，由Y/n向上取整得到p，再將第p個交換單元的輸入端口中沒有被占用的端口放在集合{P}里，此時集合{P}里出現(xiàn)的端口號表示可以和第三級建立連接的第二級的交換單元。

如果端口號Z同時出現(xiàn)在集合{I}和{P}里，表示第一級和第三級均能和第二級的第Z個交換單元建立連接。

2.2.2 有阻塞網(wǎng)絡(luò)的最優(yōu)選路路由算法思想

基于以上情況的考慮，我們對上面的選路算法進行改進，改進后的算法最有利于后續(xù)的選路，中間級交換單元的選擇也較平衡，這就是最優(yōu)選路路由算法。

算法思想：在每條連接線路選取中間級單元時，我們計算一下一旦此連接建立，對于后續(xù)的連接情況會產(chǎn)生多大的影響，即后續(xù)的所有的需要連接的線路中，不能連接成功的所占的比例。此比例越小，表明對后續(xù)的影響越小。在每次選擇中間級單元時，均選取此比例（影響）最小的單元，這樣就能確保每次選路最優(yōu)了。

最優(yōu)選路路由算法描述如下：如前所述，如果在建立第n條連接時，中間級有k個交換單元滿足通路要求，我們先選取第i（1≤i≤k）個建立連接。此時還剩下N-n個輸入和輸出，表明還可能有（N-n）×（N-n）條路徑需要連接，但有阻塞網(wǎng)絡(luò)不能保證所有的連接都能成功，接著計算下（N-n）×（N-n）條路徑中不能連通的路徑所占的比例，定義為組塞概率，f（n，i）。然后我們釋放第i個中間交換單元，選取第j（1≤j≤k，j≠i）個，再計算f（n，i）。我們將k個中間級的情況都計算一次組塞概率，最后選取組塞概率最小的那個中間級交換單元，即f（n，z）≤f（n，i），1≤i≤k。這樣每次選路，都選取能使后續(xù)的可連接數(shù)最多的路徑，此為最優(yōu)選路路由算法。

3 結(jié)語

CLOS網(wǎng)絡(luò)是科學(xué)家們在20世紀(jì)五、六十年代，為了解決電話系統(tǒng)里電路交換的問題，提出的解決方案，其中還包括 Banyan網(wǎng)絡(luò)、Omega網(wǎng)絡(luò)、Flip網(wǎng)絡(luò)和Benes網(wǎng)絡(luò)等等。其中許多交換網(wǎng)絡(luò)技術(shù)具有超常的前瞻性和強大的生命力，即使經(jīng)歷了50多年的洗禮，其間出現(xiàn)了大規(guī)模集成電路、光通信等重大的技術(shù)變革，其基本原理依然經(jīng)久不衰，依然為今人所用，實在是令人嘆服。近年來，隨著Internet，整個IP網(wǎng)絡(luò)的流量和規(guī)模在急劇膨脹，如何提高網(wǎng)絡(luò)關(guān)鍵設(shè)備—路由器系統(tǒng)的擴展能力是目前需要解決的關(guān)鍵問題，而尋求新的交換技術(shù)更是對網(wǎng)絡(luò)研究人員、科學(xué)家們的又一重大挑戰(zhàn)。

參考文獻

[1] Clos C.A study of nonblocking switching networks[J].Bell Syst Tech J，1953，32（2）：406-424.

[2] Gordon J，Srikanthan S.Novel algorithm for Clos-type networks[J].Electron Lett，1990，26（21）：1772-1774.

[3] 劉亞社，劉增基，胡征.Clos型大規(guī)模ATM交換網(wǎng)絡(luò)的虛連接無阻塞特性研究[J].電子學(xué)報，1999，27（10）.