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

劉曉鋒

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

?

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

劉曉鋒

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

Clos交換結(jié)構(gòu)作為多級(jí)結(jié)構(gòu)的典型代表在以大數(shù)據(jù)、數(shù)據(jù)中心網(wǎng)絡(luò)為特征的云計(jì)算時(shí)代再次受到業(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)基本思想為每個(gè)分組分配不同中間級(jí)交換模塊,從而實(shí)現(xiàn)無(wú)阻塞交換,同時(shí)以示例和理論上證明了該算法的可行性及算法實(shí)現(xiàn)。由于該控制算法有效避免了大量的仲裁信息,因此能有效降低交換延遲,提高交換吞吐率。

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

0 引 言

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

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

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

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

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

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

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

2 基于SDR的控制算法

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

2.1 基本定義

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

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

定義2 相異代表組[11]就是為一個(gè)集合系的每個(gè)集合尋找一個(gè)代表元素,而且要求所有的代表元素互不相同。如有集合系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來(lái)代表S1,4代表S2,5代表S3,6代表S4,1代表S5,2代表S6。

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

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

下面給出兩個(gè)關(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)。

這兩個(gè)集合系中每個(gè)集合的初值均為{CM1,CM2,…,CMm}。一個(gè)指派中的任意請(qǐng)求有序?qū)Α碔Mi,OMj〉(1≤i,j≤r)可經(jīng)過(guò)任意CM來(lái)實(shí)現(xiàn)其交換目的。為了實(shí)現(xiàn)上述CM的分配目標(biāo),只需在集合CM_im(i)∩CM_om(j)(1≤i,j≤r)中為每個(gè)請(qǐng)求有序?qū)Ψ峙湟粋€(gè)CM,然后在集合CM_im(i)和CM_om(j)中刪除此CM,這樣可以有效避免各種類(lèi)型的阻塞。

2.2 基于SDR的控制算法

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

為了實(shí)現(xiàn)在集合CM_im(i)∩CM_om(j) (1≤i,j≤r)中選擇CM,可對(duì)相應(yīng)串進(jìn)行按位“與”,結(jié)果串中數(shù)字1所對(duì)應(yīng)的CM可用；然后修改兩個(gè)串的被選CM對(duì)應(yīng)的位為0。

下面通過(guò)一個(gè)例子來(lái)闡述這種思想。

下面討論中均用二進(jìn)制串代表集合。

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

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

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

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

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

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

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

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

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

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

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

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

3.1 算法可行性證明

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

如前所述,為請(qǐng)求集IM(i)→OM(o)(o=j1,j2,…,jt)分配CM的過(guò)程,為了給來(lái)自IM(i)的所有請(qǐng)求分配不同的CM,等價(jià)于找集合系CM_om(o)(o=j1,j2,…,jt)的相異代表組。集合系CM_om(o)(o=j1,j2,…,jt)是否存在相異代表組是決定該算法可行性的根本。假設(shè)在某個(gè)時(shí)隙,來(lái)自IM(i)(1≤i≤r)的請(qǐng)求有s個(gè)。由于來(lái)自IM(i)(1≤i≤r)的請(qǐng)求最多有n個(gè),所以s≤n。另外,可能存在多個(gè)請(qǐng)求到相同的輸出模塊,但不存在一個(gè)請(qǐng)求到多個(gè)不同的輸出模塊(不考慮多播),因此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表示來(lái)自IM(i)的s個(gè)請(qǐng)求到s個(gè)不同的輸出模塊,而集合系CM_om(o)(o=j1,j2,…,jt)中的每個(gè)集合都含有m個(gè)不同的元素CM1,CM2,…,CMm。因此當(dāng)t=s≤n≤m關(guān)系成立時(shí),集合系的任意k(k≤t)個(gè)集合的并集至少含有k個(gè)不同元素,根據(jù)定理1,此集合系CM_om(o)(o=j1,j2,…,jt)一定存在相異代表組。

(2)t

條件t

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

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

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

3.2 算法的實(shí)現(xiàn)

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

為了在Si中能選出一個(gè)不同于aj(j=1,2,…,i-1)的代表ai,首先構(gòu)造輔助集合T,然后根據(jù)這個(gè)集合進(jìn)行換元,直至找到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)在逐個(gè)考察T的每個(gè)元素br(r=1,2,…) (假設(shè)T的元素有序的)。如果br是某個(gè)集合Sj(j=1,2,…,i-1)的代表,則將Sj中不屬于T的元素加入到T中;如果br不是任何集合的代表,而且br∈Sj,則用br作為Sj的新代表?yè)Q出其原代表aj。如果aj∈Si,則用aj作為Si的代表加入到SDR中,調(diào)整過(guò)程結(jié)束,繼續(xù)尋找Si+1的代表,否則檢查貢獻(xiàn)aj的集合Su,用aj作為Su的新代表?yè)Q出其原代表au,再檢查au是否屬于Si,如果屬于,則讓au作為Si的代表,終止調(diào)整過(guò)程,繼續(xù)尋找Si+1的代表,否則繼續(xù)換元直至找到Si的代表為止。下面通過(guò)一個(gè)例子來(lái)說(shuō)明這個(gè)尋找過(guò)程。

例2 有一個(gè)集合系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的兩個(gè)元素都已成為其它集合的代表,所以進(jìn)入調(diào)整階段。整個(gè)調(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來(lái)自集合S);因?yàn)門(mén)中元素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)造進(jìn)入換元階段。T中元素4來(lái)自于S2,就讓4作為S2的新代表?yè)Q出其當(dāng)前代表2,因?yàn)?∈S5,所以2作為S5的代表進(jìn)入SDR中,得SDR={1(S1),4(S2),3(S3),5(S4),2(S5)}?，F(xiàn)在繼續(xù)找S6的代表。因?yàn)镾6的所有元素也都成為其它集合的代表,所以也需要調(diào)整。令T=S6={1,2,3}。T中元素1是S1的代表,但S1中沒(méi)有不屬于T的元素,不執(zhí)行任何操作;T中元素2是S5的代表,S5中也沒(méi)有不屬于T的元素;T中元素3是S3的代表,將S3中不屬于T的元素4,5加入T中,得T={1,2,3,4(S3),5(S3)};T中元素4是S2的代表,但S2中沒(méi)有不屬于T的元素;T中元素5是S4的代表,將S4中不屬于T的元素7加入到T中,得T={1,2,3,4(S3),5(S3),7(S4)};T中元素7當(dāng)前不是任何集合的代表,但它是來(lái)自集合S4,所以讓7作為S4的新代表?yè)Q出其原代表5,但5?S6,還需繼續(xù)換元。T中元素5是來(lái)自S3,讓5換出其原代表3,因3∈S6,所以讓3作S6的代表,得SDR={1(S1),4(S2),5(S3),7(S4),2(S5),3(S6)}。

下面給出此算法的形式化描述,為此先定義如表1所示的三個(gè)數(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ò)的云計(jì)算模式的成熟,對(duì)交換結(jié)構(gòu)的端口數(shù)量、交換容量、交換延遲及能耗等的要求越來(lái)越高。這些性能需求不僅對(duì)硬件結(jié)構(gòu)帶來(lái)轉(zhuǎn)型的壓力,而且對(duì)分組交換的控制算法的有效性也提出了更高的要求。基于Clos網(wǎng)絡(luò)的多級(jí)交換結(jié)構(gòu)具有良好的模塊性及可擴(kuò)展性,因此在交換結(jié)構(gòu)面臨性能壓力時(shí)再次受到了業(yè)界的關(guān)注,但目前面向此結(jié)構(gòu)的分組控制算法由于自身的交換模式不能很好地滿(mǎn)足云計(jì)算所致的性能需求,而且它也只能在某些流量模式下效果顯著,如均勻流量模式。

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

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

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

TP393

A

10.16246/j.issn.1673-5072.2016.03.022