Clos交換網絡的一種基于矩陣分解的路由指派算法

劉曉鋒，吳亞娟

(西華師范大學 計算機學院，四川 南充 637009)

0 引 言

Clos 交換網絡［1］發展至今已有60 余年的研究歷史，最早是針對電話交換網絡，隨著IP 網絡的快速發展和Clos 網絡本身的良好可擴展性及優越的網絡性能，它被應用于IP 網絡的分組交換中，特別是用于高速、大容量交換機/路由器的設計中，如Juniper T1600/TX -Matrix Plus 系列． 另一方面，隨著數據中心網絡(data center networks，DCN)［2］的誕生和發展，Clos 交換網絡再次成為研究熱點．一個DCN 通常由成千上萬甚至上百萬的服務器和交換機/路由器組成，如何組織如此之多的服務器和交換機才能滿足DCN 的高可擴展性、低延遲及低能耗的本質需求是一個極其重要的研究課題．Clos 網絡或其擴展結構(如Folded -Clos 結構)作為DCN 的拓撲結構已被廣泛研究［3］［4］，但很少涉及底層交換節點的體系結構及路由算法．目前相應于Clos 交換網絡的迭代類路由指派算法因在線卡與調度器之間較長的往返時延而不能很好地適用于DCN 環境下的數據交換，另外矩陣分解類路由指派算法又因分解不完全致使該類算法在某些情況下不能正常工作．因此，本文旨在對Clos 交換網絡的經典指派算法的研究基礎上，給出適合于DCN 環境下的基于矩陣分解的路由指派算法．

1 基本網絡結構及條件假設

在宏觀上，Internet 由兩類硬件設施組成:通信鏈路(link)及交換節點(node)．通信鏈路只負責數據分組的傳輸，不負責分組的轉發;交換節點雖然也執行分組的傳輸，但其主要功能是負責分組的轉發，即根據IP地址在整個IP 網絡里轉發IP 分組．

為了分組的路由與轉發，路由器/交換機主要由三部分構成，即路由軟件(routing software)、線卡(line card)和交換結構(switch fabric)，如圖1 所示［5］．路由軟件即路由算法，它控制IP 分組從交換結構的某個輸入端口交換到某個合適的輸出端口以避免在交換結構里發生阻塞而丟包．這個過程是與特定的交換結構相關，本文討論的路由指派算法是針對可擴展性好、網絡性能優越的Clos 交換結構．因此本節首先討論Clos 交換結構的網絡模型及條件假設．

基本的Clos 交換網絡由輸入級、中間級和輸出級互連而組成，相應于每級的交換模塊可以是一個交換規模較低的Crossbar 結構，分別稱為輸入級交換模塊(input switching module，ISM)，中間級交換模塊(center switching module，CSM)及輸出級交換模塊(output switching module，OSM)，如圖2 所示．每個ISM 或OSM 是一個n×m 或m×n 的Crossbar 交換模塊，CSM 是一個r×r 的Crossbar 交換模塊．通常稱這樣的基本Clos 交換結構為對稱Clos 交換網絡，記為C(n，m，r)，其交換容量N = n×r．

圖1 交換機/路由器結構略圖[5]Fig.1 Architecture of a switch/an IP router

圖2 基本Clos 交換網絡Fig．2 A Clos switching network

Clos 網絡是具有阻塞特性的一種交換網絡，其阻塞特性可由參數n，m 和r 完全決定，即當m≥2n -1時，它是嚴格非阻塞(strickly non -blocking，SNB)［1］;當m≥n 時，它是可重排非阻塞(rearrangeable non -blocking，RNB)［6］．由此可見，一個SNB 的Clos 網絡較RNB 的Clos 網絡有更大的硬件代價，前者需要更多的CSM，至少是后者的(2n-1)/n 倍，因此RNB 的Clos 網絡更有吸引力，當然調度算法相對復雜．本文的研究是針對RNB 的Clos 交換網絡，而且假設m=n，但其結果同樣適用于m ＞n 的情況．

在Clos 交換網絡中，到達輸入端口的分組都帶有自己的目的地址，通常用如公式⑴的請求置換來表示分組的源端口與目的端口之間的對應關系．

公式(1)反映了Clos 網絡的輸入端口到輸出端口的映射，即輸入端口i (1≤i≤N)映射到輸出端口oi(1≤oi≤N)，表示到達輸入端口i 的分組的目的端口為oi．

2 路由指派算法相關研究

Clos 網絡是一種多路由路徑的交換網絡，在任意輸入/輸出之間均存在多條路由路徑，具體的路徑數目由CSM 模塊數決定，即每個CSM 模塊就是一條路由路徑，因此路由路徑的選擇等價于CSM 模塊的選擇．目前關于CSM 的典型的選擇策略有分布式的輪詢仲裁策略(round - robin arbitration)、二分圖邊著色策略(edge coloring)及矩陣分解策略(matrix decomposition)等．

由此可見，采用方法一與有限元的計算的排水量和剩余水頭高度的結果都十分接近，而采用方法二的排水量計算結果遠大于方法一和有限元的計算結果。說明采用方法一與有限元進行雙排水盲溝滲流計算時，可以得到較為合理的結果，其結果具有一定的參考價值。

2．1 輪詢仲裁策略

輪詢仲裁匹配策略就是在輸入端口與輸出端口之間進行反復詢問，最終形成一個匹配．具體地，每個輸入端口根據自己當前時隙分組的傳輸需求向相應的輸出端口發送傳輸“請求(request)”信號，每個輸出端口以某種方式(如周期輪換)送出“授權(grant)”信號以表示接受此請求，輸入端口收到輸出端口的授權信號后，再以某種方式(如周期輪換)“授受(accept)”某個授權，最后在輸入端口與輸出端口之間形成一個匹配．為了實現端口之間的匹配，需要在每個端口處設立一個仲裁器(arbitrator)，用于在多個信號中的選擇．這個輪詢過程如圖3 所示．

圖3 一個4×4 交換模塊的一個迭代周期Fig.3 An iteration cycle of a 4×4 switching module

從上述簡單描述中可以看出，輪詢仲裁匹配策略存在以下不足之處:第一是輸入/輸出端口在每個匹配周期都采用請求—授權—接受(request-grant-accetp，RGA)形式．這不僅會增加交換延遲，而且會產生大量需要維護的仲裁信息．第二，一個匹配周期很難得到輸入與輸出端口之間最大匹配，可能需要多個匹配周期，甚至永遠也得不到最大匹配．如圖3 中，一個匹配周期只得到了兩個成功匹配，其余兩個匹配(4→2 和3→4)只能在下一個匹配周期完成．第三，在Clos 網絡的每一級都需要進行這樣的輪詢迭代，那么后一級的輪詢匹配可能會阻塞上一級的部分匹配．圖4(a)表示請求置換的路由路徑的指派情況，因中間級的阻塞導致輸入級的四個成功匹配在這一級匹配失敗，這就降低了整個交換系統的吞吐率．因此，迭代類算法不適合DCN 環境下的分組交換．

2．2 二分圖邊著色策略

二分圖的匹配是解決交換結構中端口匹配問題的最直接的數學理論，為了提高交換結構的吞吐率，每個時隙都盡可能得到一個二分圖的最大匹配，但相應算法的復雜度較高．目前效率最高的匹配算法的時間復雜度也是O(n5/2)［7］，實用性并不強．在Clos 交換結構中，不僅需要解決端口的匹配，還必須解決交換路徑的指派．

根據每個時隙分組的到達情況，應用二分圖的邊著色理論實現交換路徑的指派．先將Clos 交換結構轉化為一張二分圖Gclos=(Vin，Vout，E)，其中Vin={ISMi| 1≤i≤r}，Vout={OSMj| 1≤j≤r}．如果當前時隙ISMi有到OSMj的請求任務，則邊e = ＜ISMi，OSMj＞是E 的一個元素．為二分圖Gclos中鄰接于同一頂點的不同邊著上不同的顏色，這不同顏色代表不同的CSM 交換模塊．圖5 就是針對圖4 的Clos 交換結構的二分圖邊著色情況，其中用不同的線型表示不同的顏色，同時表示經過不同的CSM 交換模塊．從圖5 可看出，鄰接于同一個頂點的不同形式的邊(表示不同的顏色)表示經歷不同的CSM 到達各自的目的端口，這樣可很好地解決阻塞問題．相應的交換路徑指派如圖4(b)所示．

圖4 中間級產生阻塞導致匹配不完全Fig.4 An incomplete matching caused by blocking in the central stage

基于二分圖的邊著色原理可以很好地解決Clos 交換網絡的交換路徑的指派問題，但必須先將Clos 交換結構轉化成一張二分圖，這不僅增加時間復雜度，而且也增加空間復雜度．這對于交換容量不是很大的交換結構而言并非是明智的選擇［8］，因此這類指派算法也不能很好地工作于DCN 中．

3 基于矩陣分解的路由指派算法

圖5 邊著色指派圖Fig.5 An assignment graph based on the edge-coloring

矩陣分解亦是解決路由指派的一種非常重要的方法．這種方法不必將Clos 交換網絡轉化成二分圖，而是直接分解業務矩陣，可降低時間復雜度與空間復雜度．不幸的是，目前已有的矩陣分解算法存在不完全性，即算法在某些情況下不能正常工作．Jajszczyk 算法［9］是一款很優秀的矩陣分解算法，但Cardot［10］卻給出一個它不能正確分解的反例導致其正確性遭到質疑．Ramanujam 算法［11］也是通過矩陣分解來解決Clos 結構的路由問題，它不僅通過系列復雜的變換抽取出輸入與輸出之間的對應關系，而且Kubale［12］證明此算法也是不完全的．Gordon 等人提出的GS 分解算法［13］雖然是一款非常有效的分解算法，但其正確性也遭到了質疑［14］，而且Lee 等人［8］也給出一個此算法不能正確分解的反例．因此，目前已有的基于矩陣分解的路由指派算法不能應用于DCN 中．

本文給出一種基于逐行分解的矩陣分解算法，它可完全解決其它同類算法的不完全性，而且分解效率不低于這些算法．

3．1 基本概念及條件假設

其中，元素tij表示到達第i 個輸入交換模塊(ISMi)前往第j 個輸出交換模塊(OSMj)的分組數．在每個時隙到達每個輸入交換模塊的分組數不能超過其能接收的理論最大值，每個輸出交換模塊在每個時隙送出的分組數也不能超過其能送出的理論最大值，所以業務矩陣T 中的元素需滿足如下條件:

指派矩陣(assignment matrix)Ai(1≤i≤r)指示出所有到達第i 個輸入交換模塊(ISMi)的分組的路由路徑．Ai是一個n×r 的矩陣(akj)n×r，元素akj是一個示性變量，如果第k 個中間交換模塊(CSMk)被分配給請求到第j 個輸出交換(OSMj)的分組，則akj等于1，否則等于0．分解業務矩陣T 的第i 行得到指派矩陣Ai，分解T 得到的所有指派矩陣組成的集合稱為指派矩陣集，記為A．

在部分和矩陣中，含有元素e 的行或列，稱為e-行或e-列，并稱此元素為e-元．

3．2 矩陣分解算法

為了實現Clos 交換網絡的無阻塞路由，中間級交換模塊CSM 的分配必須滿足以下兩個分配目標:①為來自相同ISM 的請求分配不同的CSM;②為擁有相同OSM 的請求分配不同的CSM．任何路由指派算法只要具備這兩個分配目標，就一定可以避免路由阻塞．

為了實現上述CSM 的分配目標，本算法分兩個階段實現業務矩陣的分解，第1 階段為業務矩陣T 的初級分解，第2 階段為指派矩陣集A 的調整．

● T 的分解:對T 的第i(1≤i≤r)行(ti1，ti2，…，tir)中每個元素tij(1≤j≤r)執行如下兩步:

(1)如果tij≥1，則(0，0，…，1，…，0)作為Ai的一行加入其中;

(2)tij= tij-1，執行⑴．

● A 的調整:初始時，ps(1)= A1，然后重復執行如下步驟r-1 次(2≤i≤r)，直至ps(r)的所示元素均為1．

(1)查找ps(i)中的2 -行，用s 表示，則s 對應于Ai的一個調整行，如果ps(i)中沒有2 -元，則執行⑷;

(2)查找ps(i)中2 -列的0 -行，用t 表示，則t 對應于Ai的一個目標行;

(3)交換Ai的調整行與目標行，消除ps(i)中的一個2 -元;

(4)ps(i+1)= ps(i)+Ai+1，執行(1)．

3．3 算法的性能分析

矩陣分解算法分2 個階段，即業務矩陣的分解階段和指派矩陣集的調整階段．在分解階段，每行的分解操作至多執行n 次，而業務矩陣有r 行，所以總的計算時間為O (nr)．調整階段的時間效率涉及3 個因素，首先是部分和的計算，這是典型的兩個矩陣的求和運算，其復雜度為O (nr)，但需要計算r 次，所以總復雜度為O (nr2)．其次，部分和矩陣中2 -元和0 -元的查找，此操作需要遍歷整個部分和矩陣，其時間復雜度為O(nr)，共有r - 1 個部分和矩陣需要檢查，所以總時間代價亦為O (nr2)．最后，調整行與目標行的交換．由分解階段的分解算法決定了在任何時候部分和矩陣里至多有n 個2 -元，這說明指派矩陣在最壞情況下需要調整n-1 次，即整個過程需要調整的次數為O (nr)．綜合上述分析，此算法的時間復雜度為O(nr2)．與其它同類算法的計算時間復雜度比較如表1，從中可以看出本文提出的分解算法(表1 的最后一行)的時間復雜度不高于其它同類算法．

表1 算法的時間復雜度比較Tab．1 Comparisons of time complexity of decomposition algorithms

4 結 論

Clos 交換網絡在構建高速大容量交換系統時具有單級結構無法比擬的成本和可擴展優勢，而且隨著DCNs 的廣泛應用，對交換節點提出更為嚴格的需求．而目前相應的路由指派算法不能很好地滿足如此嚴格的性能需求，不是延遲較大，就是過于復雜或矩陣分解不完全等．本文提出的基于矩陣分解的路由指派算法，采用與其它同類算法不一樣的逐行分解策略，能以串行時間O (nr2)正確分解滿足條件⑶的任意請求矩陣，有效解決以前分解算法的不完全性，并且不會在調度器與線卡之間產生較大的往返時間(RTT)，簡單易實現于Clos 交換網絡的路由指派．

另外，分解算法的分解步驟之間的數據依賴較弱，非常容易并行化，可在線性時間復雜度O(nr)內完成業務矩陣的分解，較其它算法更適用于DCN 中的分組交換．

［1］ CLOS C． A Study of Non-blocking Switching Networks［J］，Bell Systems Technical Journal，1953，32(2):406 -424．

［2］ LIU Y，MUPPALA J K，VEERARAGHAVAN M，et al． Data Center Networks -topologies，Architectures and Fault-tolerance Characteristics［M］． New York:Springer，2013:1 -5．

［3］ AL-FARES M，LOUKISSAS A，VAHDAT A． A Scalable，Commodity Data Center Network Architecture［C］//Proc． of the ACM SIGCOMM，Seattle，USA，2008:63 -74．

［4］ GREENBEG A，HAMILTON J R，JAIN N，et al． VL2:A Scalable and FlexibleData Center Network［J］． Communications of The ACM，2011，54(3):95 -104．

［5］ CHANG C S，LEE D S． Principles，Architectures and Mathematical Theory of High Performance Packet Switches［M］． National Tsinghua University Press，Taiwan，2008:3 -4．

［6］ BENE? V E． On rearrangeable three-stage Connecting Networking［J］． Bell Systems Technical Journal，1962，41(5):1481 -1492．

［7］ HOOPCROFT J E，KARP R M． An n5/2Algorithm for Maximum Matching in Bipartite Graph［J］．SIAM Journal on Computing，1973，2(4):225 -231．

［8］ LEE H Y，HWANG F K，CARPINELI J D． A New Decomposition Algorithms for Rearrangeable Clos Interconnection Networks［J］． IEEE Transactions on Communications，1996，44(11):1572 -1578．

［9］ JAJSZCZYK A． A Simple Algorithm for the Control of Rearrangeable Switching Network［J］． IEEE Transactions on Communications，1985，COM-33(2):169 -171．

［10］ CARDOT C． Comments on“A Simple Algorithm for the Control of Rearrangeable Switching Networks”［J］． IEEE Transactions on Communications，1986，COM-34(4):395．

［11］ RAMANUJAM H R． Decomposition of Permutation Networks［J］． IEEE Transactions on Computers，1973，C-22(7):639 -643．

［12］ KUBALE M． Comments on“Decomposition of Permutation Networks”［J］． IEEE Transactions on Computers，1982，C -31(3):256．

［13］ GORDON J，SRIKANTHAN S． Novel Algorithm for Clos-type Networks［J］． Electronics Letters，1990，26(21):1772 -1774．

［14］ CHIU Y K，SIU W C． Comment“Novel algorithm for Clos-type Networks”［J］． Electronics Letters，1991，27(6):524 -526．［15］ TSAO-WU N T． On neiman's Algorithm for the Control of Rearrangeable Switchicng Networks［J］． IEEE Transactions on Communications，1974，COM-22(6):737 -742．

［16］ HWANG F K． A modification to a Decomposition Algorithm of Gordon and Srikanthan［J］． IEEE Transactions on Computers，1997，46(8):958 -960．