CLOS網絡及其路由算法

楊宜鎮 管紅光 周煒 吳致遠

摘 要：本文首先對CLOS網絡進行了簡單的介紹，然后結合CLOS網絡在路由算法中的應用，詳細闡述了CLOS網絡的路由算法。

關鍵詞：CLOS 網絡 路由 擁塞 交換結構

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

1 CLOS網絡簡介

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

1.1 CLOS網絡的定義

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

討論。

圖1 CLOS網絡模型圖

1.2 CLOS網絡的設計

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

1.2.1 三級CLOS網絡結構

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

圖2 三級CLOS網絡結構示意圖

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

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

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

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

2 CLOS網絡結構的路由算法

前面提到過，設計CLOS網絡結構，其網絡機構的交換性能：包括伸縮性、交換時延、數據傳輸的自路由性與有序性，還有一個最重要的因素就是如何處理網絡交換的碰撞沖突，也稱為擁塞。

有的人可能會問，既然有嚴格無阻塞網絡，為什么不直接使用嚴格無阻塞技術呢？當然，無阻塞網絡當然是我們所追求的理想目標。但是，為了增加容量和降低阻塞，必須大量上調m和n的數量，會使實現交換單元的數量和交換網絡的技術成本大大增加。我們研究CLOS網絡結構，就是要研究使設計CLOS網絡結構的代價與網絡的交換性能的折中達到最優化設計。所以上面提到的完全無阻塞網絡結構不在本文的研究范圍。

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

2.1 優先級篩選中間模塊法

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

2.1.1 當前業務對后面業務造成的影響

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

圖3 三級CLOS網絡業務交換模擬圖

2.1.2 尋找最適合的中間模塊

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

ab：代表一條業務流，a為輸入單元的輸入端口，b為輸出單元的輸出端口，

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

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

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

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

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

Fout（V）：V內所有單元的空閑輸出口集合

Fin（W）：W內所有單元的空閑輸入口集合

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

首先從U中找出所有跟f，g的后序剩余端口業務相關的中間單元V和W：

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

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

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

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

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

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

例子說明：由于圖4中3～n之間的單元沒有畫出來，所以我們只對前3個單元進行分析，n個單元的分析思路是一樣的。假設output[i]是中間模塊V的所有輸出端口，Fout（V）是output[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都出現了重復， 說明他們有相同的空閑端口，且都出現了2次。說明分別都有2個單元上這些端口是空閑的，4只出現了一次，說明只有一個單元上4端口是空閑的，Fout（V）里不相同的元素為{0.1.2.4.5.6}，說明輸入單元f的剩余端口能到達6個輸出單元，如果我們令3單元的3號輸出端口也空閑，那么我們可以做如下比較：

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

Fout（V）={（0.2.4.5），（0.1.2.5.6）}，Fout（V）內的不同元素為{0.1.2.4.5.6}；

Fin（W）={（1.2.5），（1.2. 4.5.6）}，Fin（W）內的不同元素為{1.2.3.4.5.6}；

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

（2）同理，假設從a->b的業務流選擇中間模塊的3單元，結合圖4可以得出：

Fout（V）={（0.2.4.5），（1.6）}，Fout（V）內的不同元素為{0.1.2.4.5.6}；

Fin（W）={（1.2.5），（1.2.4）}，Fin（W）內的不同元素為{1.2.4.5}；

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

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

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

2.2 最優選路路由算法

2.2.1 傳統CLOS網絡路由選路算法思想

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

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

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

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

2.2.2 有阻塞網絡的最優選路路由算法思想

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

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

最優選路路由算法描述如下：如前所述，如果在建立第n條連接時，中間級有k個交換單元滿足通路要求，我們先選取第i（1≤i≤k）個建立連接。此時還剩下N-n個輸入和輸出，表明還可能有（N-n）×（N-n）條路徑需要連接，但有阻塞網絡不能保證所有的連接都能成功，接著計算下（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。這樣每次選路，都選取能使后續的可連接數最多的路徑，此為最優選路路由算法。

3 結語

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

參考文獻

[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型大規模ATM交換網絡的虛連接無阻塞特性研究[J].電子學報，1999，27（10）.