Clos交換結構的基于相異代表組的路由控制算法

劉曉鋒

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

?

Clos交換結構的基于相異代表組的路由控制算法

劉曉鋒

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

Clos交換結構作為多級結構的典型代表在以大數據、數據中心網絡為特征的云計算時代再次受到業界的關注,但目前應用于Clos交換結構的分組控制算法(或調度算法)卻較難以適應大數據及數據中心網絡的低延遲,低能耗等的性能需求。因此,根據Clos交換結構中分組調度的本質,利用相異代表組(SDR)基本思想為每個分組分配不同中間級交換模塊,從而實現無阻塞交換,同時以示例和理論上證明了該算法的可行性及算法實現。由于該控制算法有效避免了大量的仲裁信息,因此能有效降低交換延遲,提高交換吞吐率。

分組交換;相異代表組;Clos網絡;控制算法

0 引 言

Clos網絡[1]作為電話交換網絡的產物,卻在分組交換中扮演了非常重要角色,特別是在以大數據、數據中心網絡為特征的云計算成為主流運維模式的背景下,它作為數據中心網絡的物理架構再次成為企業及學術界的研究焦點。一個Clos交換網絡是由輸入級、輸出級和中間級連接而成的3級結構,級與級之間由通信鏈路通過部分互連的方式連接而成,如圖1所示。輸入級的交換模塊稱為輸入模塊(input module,IM),輸出級的交換模塊稱為輸出模塊(output module,OM),中間級的交換模塊稱為中間模塊(center module,CM)。每個IM(OM)是一個n×m(m×n)的交換矩陣,每個CM是一個r×r的交換矩陣,而且每個IM(OM)模塊都有唯一鏈路連接一個CM模塊,因此一個Clos交換網絡的相關屬性完全由參數n,m,r來決定。當m≥2n-1,此網絡嚴格無阻塞[1]；當m≥n,為可重排無阻塞[2]。

交換網絡的一個指派(assignment)是所有輸入/輸出端口組成有序對<輸入端口,輸出端口>的集合,而且每個端口只能出現在一個有序對中。有序對<輸入端口,輸出端口>指明了分組在交換結構中的入口和出口。在交換結構內部如果存在不相交(即不產生沖突)的路由路徑來鏈接指派中的每個有序對,則稱此指派是可行的(realizable)。對Clos交換網絡來說,一個指派是否可行與CM的分配策略緊密相關。如果CM分配不合理,則其內部的路由路徑可能會產生沖突,最終致使分組丟失,交換吞吐率降低。為了確保一個指派是可行的,通常需要相應的路由控制算法來控制每個有序對<輸入端口,輸出端口>的路由路徑。在設計交換網絡內部的路由控制算法時,可將路由問題轉化矩陣分解(matrix decomposition)問題,二分圖匹配(bipartite matching)問題及邊著色(edge coloring)等問題[3]。本文根據CM的分配原則及分配目標,以相異代表組(system distinct representative, SDR)為基礎設計一款路由指派算法能有效避免大量的仲裁信息。

1 分組控制算法相關研究

交換結構的控制算法(或調度算法)主要完成在所有輸入-輸出間選擇一條沒有沖突的交換路徑,從而實現快速高效的分組交換,達到合理利用網絡資源,提高吞吐率和降低延遲,因此控制算法的性能直接影響交換結構的交換性能。

在交換結構的輸入-輸出間尋找無沖突匹配的數學模型就是二分圖的匹配問題。為了提高吞吐率,調度算法需要在二分圖的匹配中找到一個最大匹配(maximum size matching)。目前實現最大匹配的算法雖能達到100%的吞吐率,但其實現復雜度比較高(O(N2.5))[4],而且可能導致不穩定性及餓死現象[5],在實際應用中很少采用。通常采用一些近似手法通過多次迭代來逼近一個最大匹配,較為知名的控制算法如CRRD/CMSD[6],PIM[7],iSLIP[8]。雖然這些調度算法所針對的交換結構有一定的差異,但其采用的基本思想是一致的,均為請求-授權-接受(request-grant-accept,RGA)模式在輸入-輸出間建立匹配。基于RGA匹配模式的控制算法會在輸入端與輸出端之間產生大量的仲裁信息,這不僅會增加交換延遲,而且還會增加信息存儲的負擔,在高速環境中控制也比較復雜。

MAC[9]和Distro[10]是兩款以多級體系結構為硬件平臺的調度算法。Distro算法利用靜態輪轉的模式在多級間通過問-答方式來建立輸入-輸出端口間的匹配。此算法類似于CRRD/CMSD,不同的是Distro采用靜態輪轉,少了一次“接受”信息的傳送,其負面影響就是不能很好適用于任意的流量模式,同樣需要逐級傳送咨詢信息。MAC算法部署了一個類似于單級結構的調度器(如圖2(a)所示),去掉了逐級探測的匹配方式,但需要通過兩級匹配來完成輸入-輸出端口的匹配。首先是SIM與SOM的匹配(稱為1級匹配),然后在已配對的SIM-SOM所包含的輸入與輸出端口間進行匹配(稱為2級匹配)。1級匹配采用了預先確定的輪換方式(如圖2(b)所示);2級匹配就在已配對SIM-SOM所含的輸入-輸出端口間按RGA模式進行匹配。這樣就不需要在多級間傳遞仲裁信息。

本文提出的基于SDR思想的控制算法去掉基于RGA的詢問-應答模式,在匹配成功的輸入-輸出間直接分配路徑,從而提高傳輸效率,降低傳輸延遲。

2 基于SDR的控制算法

路由路徑指派的終極目標是在分組交換過程中不要產生任何阻塞,為了實現此終極目標,算法對CM的選擇必須滿足以下2點分配目標：(1)為來自相同IM的分組分配不同的CM；(2)為前往相同OM的分組分配不同的CM。為此先定義如下相關定義及基本定理。

2.1 基本定義

定義1 業務矩陣(traffic matrix)T表示輸入交換模塊到輸出交換模塊的請求情況,表示為

元素tij表示源輸入模塊為IMi,目的輸出模塊為OMj的分組數,即從IMi→OMj的分組數。

定義2 相異代表組[11]就是為一個集合系的每個集合尋找一個代表元素,而且要求所有的代表元素互不相同。如有集合系S={S1,S2,S3,S4,S5,S6},其中S1={1,2,3},S2={1,2,3,4},S3={2,3,4,5},S4={3,4,6},S5={1,2},S6={1,2,3}。此集合系的相異代表組SDR={3,4,5,6,1,2},即用元素3來代表S1,4代表S2,5代表S3,6代表S4,1代表S5,2代表S6。

定理1[11]假設集合系S由集合M的n個子集合S1,S2,…,Sn構成,即S={S1,S2,…,Sn}。這n個子集合的任意k (k=1,2,…,n)個子集合的并集至少包含M的k個不同元素,則集合系S存在一個相異代表組。

證明 可以對整數k用數學歸納法證明。詳細證明過程參見[11]。

下面給出兩個關于CM的集合系CM_im(i)和CM_om(j) (1≤i，j≤r)。

定義3CM_im(i)={CM| 源輸入模塊為IM(i)的分組能使用的CM}；CM_om(j) = {CM| 目的輸出模塊為OM(j)的分組可使用的CM},(1≤i≤r,1≤j≤r)。

這兩個集合系中每個集合的初值均為{CM1,CM2,…,CMm}。一個指派中的任意請求有序對〈IMi,OMj〉(1≤i,j≤r)可經過任意CM來實現其交換目的。為了實現上述CM的分配目標,只需在集合CM_im(i)∩CM_om(j)(1≤i,j≤r)中為每個請求有序對分配一個CM,然后在集合CM_im(i)和CM_om(j)中刪除此CM,這樣可以有效避免各種類型的阻塞。

2.2 基于SDR的控制算法

為了實現CM的分配目標,用一個m位的二進制串來表示定義3中的每個CM集合。串的每一位對應于相應的CM的使用情況。如果某位為1則表示對應的CM可用,否則此CM不可用。如果集合CM_im(i)的初始值為{CM1,CM2,CM3,CM4,CM5},用二進制“11111”表示,在經歷了幾次分配后此集合變成{CM2,CM5},則二進制為“01001”,因為CM1、CM3和CM4已被分配,對應的二進制串中相應位由1變為0。

為了實現在集合CM_im(i)∩CM_om(j) (1≤i,j≤r)中選擇CM,可對相應串進行按位“與”,結果串中數字1所對應的CM可用；然后修改兩個串的被選CM對應的位為0。

下面通過一個例子來闡述這種思想。

下面討論中均用二進制串代表集合。

第1步,分析T的第1行元素[2,2,1]。它表示來自IM(1)的5個分組,其中2個到OM(1),2個到OM(2),1個到OM(3)。

①計算CM_im(1)&CM_om(1)=“11111”,這說明5個CM均可用,任意選擇2個作為到OM(1)的分組使用,如CM1和CM2。然后修改這兩個二進制串中對應位為0,即CM_im(1)=“00111”,CM_om(1)=“00111”。

②計算CM_im(1)&CM_om(2)=“00111”&“11111”=“00111”,這表明只CM3,CM4和CM5可用,如選擇CM3和CM4。修改兩二進制串為CM_im(1)=“00001”,CM_om(2)=“11001”。

③計算CM_im(1)&CM_om(3)=“00001”&“11111”=“00001”,這表明只有CM5可用,因此只能選擇CM5。修改二進制為CM_im(1)=“00000”,CM_om(3)=“11110”。

第2步,分析T的第2行元素[0,3,2]。它表示來自IM(2)的5個分組,其中0個到OM(1),3個到OM(2),2個到OM(3)。

①計算CM_im(2)&CM_om(2)=“11111”&“11001”=“11001”,這表明只CM1,CM2和CM5可用,所以將這3個CM分配給到OM(2)的分組。修改串為CM_im(2)=“00110”,CM_om(2)=“00000”。

②計算CM_im(2)&CM_om(3)=“00110”&“11110”=“00110”,說明當前只有CM3和CM4可用,于是將這兩個CM分配給到OM(3)的分組。修改串為CM_im(2)=“00000”,CM_om(3)=“11000”。

第3步,分析T的第3行元素[3,0,2]。它表示來自IM(3)的5個分組,其中3個到OM(1),0個到OM(2),2個到OM(3)。

①計算CM_im(3)&CM_om(1)=“11111”&“00111”=“00111”,結果表明只有CM3,CM4和CM5可用,所以將這3個CM分配給到OM(1)的分組。修改串為CM_im(3)=“11000”,CM_om(1)=“00000”。

②計算CM_im(3)&CM_om(3)=“11000”&“11000”=“11000”,結果表明CM1和CM2可用,于是將這兩個CM分配給這兩個分組。修改串為CM_im(3)=“00000”,CM_om(3)=“00000”。

所有CM模塊按此分配算法不會產生任何阻塞,如圖3(b)所示。

3 基于SDR控制算法實現及可行性分析

3.1 算法可行性證明

Clos網絡C(n,m,r)在m≥2n-1成立時嚴格無阻塞,在m≥n成立時可重排無阻塞。本算法的討論是在m≥n的背景下進行。為討論的方便,我們進一步假設此網絡是對稱的,即m=n=r。對于非對稱的Clos網絡同樣可以證明。

如前所述,為請求集IM(i)→OM(o)(o=j1,j2,…,jt)分配CM的過程,為了給來自IM(i)的所有請求分配不同的CM,等價于找集合系CM_om(o)(o=j1,j2,…,jt)的相異代表組。集合系CM_om(o)(o=j1,j2,…,jt)是否存在相異代表組是決定該算法可行性的根本。假設在某個時隙,來自IM(i)(1≤i≤r)的請求有s個。由于來自IM(i)(1≤i≤r)的請求最多有n個,所以s≤n。另外,可能存在多個請求到相同的輸出模塊,但不存在一個請求到多個不同的輸出模塊(不考慮多播),因此t,s,n三者存在不等關系：t≤s≤n。下面分兩種情況證明集合系CM_om(o)(o=j1,j2,…,jt)存在相異代表組:(1)t=s;(2)t

(1)t=s

條件t=s表示來自IM(i)的s個請求到s個不同的輸出模塊,而集合系CM_om(o)(o=j1,j2,…,jt)中的每個集合都含有m個不同的元素CM1,CM2,…,CMm。因此當t=s≤n≤m關系成立時,集合系的任意k(k≤t)個集合的并集至少含有k個不同元素,根據定理1,此集合系CM_om(o)(o=j1,j2,…,jt)一定存在相異代表組。

(2)t

條件t

假設有來自IM(i)的rh個分組請求到OM(jh) (1≤h≤t),而且滿足r1+r2+…+rt=s。現在需要在集合CM_om(jh)中為這rh個分組選出不同元素。為了實現這樣的分配目標,現將集合CM_om(jh)映射成一個子集合系(1≤h≤t)。在集合CM_om(jh)中選出rh個不同元素,相當于為子集合系選出一個相異代表組。如例1中,將CM_om(1)映射成兩個集合CM_om(l1)和CM_om(l2),在這兩個集合中選出相異代表給所包含的兩個請求。

經這樣映射得到的新集合系共含有s個集合,且每個集合都含有m個不同元素CM1,CM2,…,CMm。根據定理1,當t

綜上所述,對可重排非阻塞Clos網絡,對任意請求集IM(i)→OM(o)(o=j1,j2,…,jt),集合系CM_om(o)(o=j1,j2,…,jt)一定存在其相異代表組,只要請求集通過這個相異代表組就可完全實現分組的無阻塞交換。

3.2 算法的實現

假設集合系S={S1,S2,…,Sn},且S存在相異代表組。下面基于換元的思想[12]來尋找集合系S的相異代表組。尋找相異代表組的過程如下:從S1中選一個元素a1;從S2從選一個元素a2,但要求a2≠a1,……,從Si中選一個元素ai,確保ai≠aj(j=1,2,…,i-1)。如果這個過程能夠進行到最后一個集合Sn,則SDR={a1,a2,…,an}就是集合系S的一個相異代表組,當然一個集合系的相異代表組可能不唯一[11]。如果這個過程進行到某個集合Si,其中的所有元素都已成為其它集合Sj(j=1,2,…,i-1)的代表,導致在Si中找不到不同于aj(j=1,2,…,i-1)的元素作為自己的代表,此時需要調整Sj(j=1,2,…,i-1)的代表,以便在Si中能選出一個不同于aj(j=1,2,…,i-1)的代表。下面給出具體的調整過程。

為了在Si中能選出一個不同于aj(j=1,2,…,i-1)的代表ai,首先構造輔助集合T,然后根據這個集合進行換元,直至找到Si的不同于aj(j=1,2,…,i-1)的代表ai。假設已經得到的相異代表組SDR={a1,a2,…,ai-1},Si={b1,b2,…,bt},且br∈SDR(r=1,2,…,t)。T的初值設為Si,即T=Si={b1,b2,…,bt}。現在逐個考察T的每個元素br(r=1,2,…) (假設T的元素有序的)。如果br是某個集合Sj(j=1,2,…,i-1)的代表,則將Sj中不屬于T的元素加入到T中;如果br不是任何集合的代表,而且br∈Sj,則用br作為Sj的新代表換出其原代表aj。如果aj∈Si,則用aj作為Si的代表加入到SDR中,調整過程結束,繼續尋找Si+1的代表,否則檢查貢獻aj的集合Su,用aj作為Su的新代表換出其原代表au,再檢查au是否屬于Si,如果屬于,則讓au作為Si的代表,終止調整過程,繼續尋找Si+1的代表,否則繼續換元直至找到Si的代表為止。下面通過一個例子來說明這個尋找過程。

例2 有一個集合系S1={1,2,3},S2={2,3,4},S3={2,3,4,5},S4={3,5,7},S5={1,2},S6={1,2,3}。首先選出S1,S2,S3和S4的相異代表SDR={1(S1),2(S2),3(S3),5(S4)} (SDR集合中元素a(S)表示a為集合S的代表)。S5的兩個元素都已成為其它集合的代表,所以進入調整階段。整個調整階段分為輔助集合T的構造及相異代表的替換。首先令T=S5={1,2}。T中元素1是S1的代表,將S1中不屬于T的元素3加入T中,得T={1,2,3(S1)} (T集合中元素b(S)表示b來自集合S);因為T中元素2是S2的代表,所以將S2中不屬于T的元素4加入T中,得T={1,2,3(S1),4(S2)};T中元素3是S3的代表,將S3中不屬于T的元素5加入T中,得T={1,2,3(S1),4(S2),5(S3)};T中元素4當前不是任意集合的代表,終止T集合的構造進入換元階段。T中元素4來自于S2,就讓4作為S2的新代表換出其當前代表2,因為2∈S5,所以2作為S5的代表進入SDR中,得SDR={1(S1),4(S2),3(S3),5(S4),2(S5)}。現在繼續找S6的代表。因為S6的所有元素也都成為其它集合的代表,所以也需要調整。令T=S6={1,2,3}。T中元素1是S1的代表,但S1中沒有不屬于T的元素,不執行任何操作;T中元素2是S5的代表,S5中也沒有不屬于T的元素;T中元素3是S3的代表,將S3中不屬于T的元素4,5加入T中,得T={1,2,3,4(S3),5(S3)};T中元素4是S2的代表,但S2中沒有不屬于T的元素;T中元素5是S4的代表,將S4中不屬于T的元素7加入到T中,得T={1,2,3,4(S3),5(S3),7(S4)};T中元素7當前不是任何集合的代表,但它是來自集合S4,所以讓7作為S4的新代表換出其原代表5,但5?S6,還需繼續換元。T中元素5是來自S3,讓5換出其原代表3,因3∈S6,所以讓3作S6的代表,得SDR={1(S1),4(S2),5(S3),7(S4),2(S5),3(S6)}。

下面給出此算法的形式化描述,為此先定義如表1所示的三個數據結構

表1 算法1中所需數據結構

算法1 尋找集合系S1,S2,…的相異代表組

SDR(S1,S2,…)

輸入:集合系S1,S2,…

輸出:此集合系的相異代表組sdrep。

1.IFai∈Si&& ai≠aj(i=1,2,…;j=1,2,…,i-1)

2.sdrep(i)←ai;

3.ELSEsdrep(i)=Rep_exch(Si);

FunctionRep_exch(St)

輸入:St

輸出:找出St的代表

1.T←St;∥SupposethattheTisasequentialset。

2.FOReachelementbiinT

3.IFbi∈sdrep

4.findoutthesetSiwhoserepresentativeisbi

5.T←Si-T;

6.ELSE

7.IFbi∈St

8.RETURNbi;

9.ELSE

10.findoutthesourceset,saySj,ofbi;

11.findouttherepresentative,saybu,ofSjfromsdrep;

12. bi∈bu;GOTO3。

13.END

14.END

15.END

4 結 論

隨著基于大數據、數據中心網絡的云計算模式的成熟,對交換結構的端口數量、交換容量、交換延遲及能耗等的要求越來越高。這些性能需求不僅對硬件結構帶來轉型的壓力,而且對分組交換的控制算法的有效性也提出了更高的要求。基于Clos網絡的多級交換結構具有良好的模塊性及可擴展性,因此在交換結構面臨性能壓力時再次受到了業界的關注,但目前面向此結構的分組控制算法由于自身的交換模式不能很好地滿足云計算所致的性能需求,而且它也只能在某些流量模式下效果顯著,如均勻流量模式。

本文提出基于相異代表組的分組控制算法是針對無緩存Clos交換結構。該算法將分組的交換分成兩步完成,第一步實現輸入端口與輸出端口間的配對;第二步實現為配對成功的輸入-輸出對尋找合理的路由路徑。這樣能有效避免在多級之間來回產生大量的仲裁信息,從而提高吞吐率降低延遲。

[1]CLOSC．Astudyofnon-blockingswitchingnetworks[J]．Bellsystemstechnicaljournal,1953,32(3):406-424．

[3] 劉曉鋒,吳亞娟．Clos交換網絡的一種基于矩陣分解的路由指派算法[J]．西華師范大學學報(自然版),2015,36(4)：404-410．

[4] HOPCROFT J E, KARP R M． An n5/2algorithm for maximum matching in bipartite graph[J]． SIAM Journal on Computing,1973,2(4):225-231．

[5] MCKEOWN N,MEKKITTIKUL A,ANANTHARAM V,et al．Achieving 100% throughput in an input-queued switch[J]．IEEE Transactions on Communications,1999,47(8):1260-1267．

[6] OKI E,JING Z G,CESSA-R R,et al．Concurrent round-robin-based dispatching schemes for Clos-network switches[J]．IEEE/ACM Transactions On Networking,2002,10(6):830-844．

[7] ANDERSON T E,OWICKI S S,SAXE J B,et al．High-speed switch scheduling for local-area networks[J]． ACM Transactions on Computer Systems,1993,11(4):319-352．

[8] MCKEOWN N．The iSLIP scheduling algorithm for input-queued switches[J]．IEEE/ACM Transactions on Networking,1999,7(2):188-201．

[9] BCHAO H J,JING Z G,LIEW S Y．Matching algorithms for three-stage bufferless Clos network switches[J]．IEEE Communications Magazine,2003,41(10):46-54．

[10] PUN K,HAMDI M．Distro:a distributed static round-robin scheduling algorithm for bufferless Clos-network switches[C]//Proc．of IEEE Globecom,Taipei:2002,3:2298-2302．

[11] MANN H B,RYSER H J． Systems of distinct representatives[J]．The American Mathematical Monthly,1953,60(6):397-401．

[12] HALL M． An algorithm for distinct representatives[J]．The American Mathematical Monthly,1956,63(10):716-717．

A Routing Control Algorithm Based on SDR for Unbuffered Clos-network Switches

LIU XiaoFeng

(College of Computer Science,China West Normal University,Nanchong Sichuan 637009,China)

The Clos-network switch,as a typical representative of multi-stage switching architectures,is gaining considerable research interest and momentum again both from academia and industry in cloud-computing era with the characteristics of big data and data center networks.However, most existing control algorithms (or scheduling algorithms) applied to Clos-switches cannot well satisfy the performance requirements of low latency and low power consumption in big data and data center networks.Therefore, according to the scheduling process of packets in Clos-switches,a control algorithm based on system distinct representative (SDR) is proposed in this paper to dispatch deferent central switching module (CM) for each arrived packet so as to realize non-broking switching.Moreover, the theoretical proof and an example are provided on the validity of the proposed control algorithm.Since the control algorithm does not need to exchange much arbitration information,it can effectively reduce the switching delay and improve the throughput．

packet switching;system distinct representative (SDR);Clos-network;control algorithm

1673-5072(2016)03-0354-07

2016-01-18 基金項目：西華師范大學博士啟動基金項目(15E013，11B026)；四川省教育廳重點項目(16ZA0174) 作者簡介：劉曉鋒(1972—)，男，重慶石柱人，副教授，博士，主要從事計算機網絡體系條結構、路由與交換等相關研究。 通訊作者：劉曉鋒，E-mail：xhxfliu@163.com

TP393

A

10.16246/j.issn.1673-5072.2016.03.022