劉曉鋒

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

?

Clos交換結(jié)構(gòu)的基于相異代表組的路由控制算法

劉曉鋒

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

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

分組交換;相異代表組;Clos網(wǎng)絡(luò);控制算法

0 引 言

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

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

1 分組控制算法相關(guān)研究

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

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

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

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

2 基于SDR的控制算法

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

2.1 基本定義

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

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

定義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]假設(shè)集合系S由集合M的n個子集合S1,S2,…,Sn構(gòu)成,即S={S1,S2,…,Sn}。這n個子集合的任意k (k=1,2,…,n)個子集合的并集至少包含M的k個不同元素,則集合系S存在一個相異代表組。

證明 可以對整數(shù)k用數(shù)學(xué)歸納法證明。詳細(xì)證明過程參見[11]。

下面給出兩個關(guān)于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}。一個指派中的任意請求有序?qū)Α碔Mi,OMj〉(1≤i,j≤r)可經(jīng)過任意CM來實現(xiàn)其交換目的。為了實現(xiàn)上述CM的分配目標(biāo),只需在集合CM_im(i)∩CM_om(j)(1≤i,j≤r)中為每個請求有序?qū)Ψ峙湟粋€CM,然后在集合CM_im(i)和CM_om(j)中刪除此CM,這樣可以有效避免各種類型的阻塞。

2.2 基于SDR的控制算法

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

為了實現(xiàn)在集合CM_im(i)∩CM_om(j) (1≤i,j≤r)中選擇CM,可對相應(yīng)串進行按位“與”,結(jié)果串中數(shù)字1所對應(yīng)的CM可用；然后修改兩個串的被選CM對應(yīng)的位為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。然后修改這兩個二進制串中對應(yīng)位為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”,說明當(dāng)前只有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”,結(jié)果表明只有CM3,CM4和CM5可用,所以將這3個CM分配給到OM(1)的分組。修改串為CM_im(3)=“11000”,CM_om(1)=“00000”。

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

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

3 基于SDR控制算法實現(xiàn)及可行性分析

3.1 算法可行性證明

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

如前所述,為請求集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)是否存在相異代表組是決定該算法可行性的根本。假設(shè)在某個時隙,來自IM(i)(1≤i≤r)的請求有s個。由于來自IM(i)(1≤i≤r)的請求最多有n個,所以s≤n。另外,可能存在多個請求到相同的輸出模塊,但不存在一個請求到多個不同的輸出模塊(不考慮多播),因此t,s,n三者存在不等關(guā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。因此當(dāng)t=s≤n≤m關(guān)系成立時,集合系的任意k(k≤t)個集合的并集至少含有k個不同元素,根據(jù)定理1,此集合系CM_om(o)(o=j1,j2,…,jt)一定存在相異代表組。

(2)t

條件t

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

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

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

3.2 算法的實現(xiàn)

假設(shè)集合系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的一個相異代表組,當(dāng)然一個集合系的相異代表組可能不唯一[11]。如果這個過程進行到某個集合Si,其中的所有元素都已成為其它集合Sj(j=1,2,…,i-1)的代表,導(dǎo)致在Si中找不到不同于aj(j=1,2,…,i-1)的元素作為自己的代表,此時需要調(diào)整Sj(j=1,2,…,i-1)的代表,以便在Si中能選出一個不同于aj(j=1,2,…,i-1)的代表。下面給出具體的調(diào)整過程。

為了在Si中能選出一個不同于aj(j=1,2,…,i-1)的代表ai,首先構(gòu)造輔助集合T,然后根據(jù)這個集合進行換元,直至找到Si的不同于aj(j=1,2,…,i-1)的代表ai。假設(shè)已經(jīng)得到的相異代表組SDR={a1,a2,…,ai-1},Si={b1,b2,…,bt},且br∈SDR(r=1,2,…,t)。T的初值設(shè)為Si,即T=Si={b1,b2,…,bt}?，F(xiàn)在逐個考察T的每個元素br(r=1,2,…) (假設(shè)T的元素有序的)。如果br是某個集合Sj(j=1,2,…,i-1)的代表,則將Sj中不屬于T的元素加入到T中;如果br不是任何集合的代表,而且br∈Sj,則用br作為Sj的新代表換出其原代表aj。如果aj∈Si,則用aj作為Si的代表加入到SDR中,調(diào)整過程結(jié)束,繼續(xù)尋找Si+1的代表,否則檢查貢獻aj的集合Su,用aj作為Su的新代表換出其原代表au,再檢查au是否屬于Si,如果屬于,則讓au作為Si的代表,終止調(diào)整過程,繼續(xù)尋找Si+1的代表,否則繼續(xù)換元直至找到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的兩個元素都已成為其它集合的代表,所以進入調(diào)整階段。整個調(diào)整階段分為輔助集合T的構(gòu)造及相異代表的替換。首先令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當(dāng)前不是任意集合的代表,終止T集合的構(gòu)造進入換元階段。T中元素4來自于S2,就讓4作為S2的新代表換出其當(dāng)前代表2,因為2∈S5,所以2作為S5的代表進入SDR中,得SDR={1(S1),4(S2),3(S3),5(S4),2(S5)}?，F(xiàn)在繼續(xù)找S6的代表。因為S6的所有元素也都成為其它集合的代表,所以也需要調(diào)整。令T=S6={1,2,3}。T中元素1是S1的代表,但S1中沒有不屬于T的元素,不執(zhí)行任何操作;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當(dāng)前不是任何集合的代表,但它是來自集合S4,所以讓7作為S4的新代表換出其原代表5,但5?S6,還需繼續(xù)換元。T中元素5是來自S3,讓5換出其原代表3,因3∈S6,所以讓3作S6的代表,得SDR={1(S1),4(S2),5(S3),7(S4),2(S5),3(S6)}。

下面給出此算法的形式化描述,為此先定義如表1所示的三個數(shù)據(jù)結(jié)構(gòu)

表1 算法1中所需數(shù)據(jù)結(jié)構(gòu)

算法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 結(jié) 論

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

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

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

[3] 劉曉鋒,吳亞娟．Clos交換網(wǎng)絡(luò)的一種基于矩陣分解的路由指派算法[J]．西華師范大學(xué)學(xué)報(自然版),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 基金項目：西華師范大學(xué)博士啟動基金項目(15E013，11B026)；四川省教育廳重點項目(16ZA0174) 作者簡介：劉曉鋒(1972—)，男，重慶石柱人，副教授，博士，主要從事計算機網(wǎng)絡(luò)體系條結(jié)構(gòu)、路由與交換等相關(guān)研究。 通訊作者：劉曉鋒，E-mail：xhxfliu@163.com

TP393

A

10.16246/j.issn.1673-5072.2016.03.022