一種具有小世界性常數(shù)度的數(shù)據(jù)中心網(wǎng)*

李梅生 肖文俊 賴正文 張占英 韓冬

(1.華南理工大學(xué) 計算機科學(xué)與工程學(xué)院， 廣東 廣州 510006； 2.廣東金融學(xué)院 互聯(lián)網(wǎng)信息與金融工程系， 廣東 廣州 510520; 3.華南理工大學(xué) 軟件學(xué)院， 廣東 廣州 510006)

一種具有小世界性常數(shù)度的數(shù)據(jù)中心網(wǎng)*

李梅生1,2肖文俊3?賴正文1張占英1韓冬2

(1.華南理工大學(xué) 計算機科學(xué)與工程學(xué)院， 廣東 廣州 510006；
2.廣東金融學(xué)院 互聯(lián)網(wǎng)信息與金融工程系， 廣東 廣州 510520; 3.華南理工大學(xué) 軟件學(xué)院， 廣東 廣州 510006)

先義了一個常數(shù)度代數(shù)圖Gcoset，在此基礎(chǔ)上構(gòu)造了8度正則度、對稱性良好的數(shù)據(jù)中心網(wǎng)絡(luò)的虛擬化拓?fù)浣Y(jié)構(gòu)GDCN；然后詳細(xì)描述了GDCN的靜態(tài)模型以及Gcoset的路由算法，并給出了GDCN結(jié)構(gòu)以及一個具體實現(xiàn)；最后將GDCN與其他數(shù)據(jù)中心網(wǎng)絡(luò)模型進行了對比.結(jié)果表明：GDCN的直徑僅為O(logN)；Gcoset的路由算法較為簡單；GDCN結(jié)構(gòu)簡單、通信性能較高，可擴展性良好，且具有良好的路由容錯性.

常數(shù)度；數(shù)據(jù)中心網(wǎng)；小世界性；虛擬化；拓?fù)浣Y(jié)構(gòu)；路由算法

作為可用于存儲、計算等服務(wù)，同時又具有成本效益的基礎(chǔ)設(shè)施，數(shù)據(jù)中心受到了廣泛的關(guān)注.如今，亞馬遜、谷歌、臉譜網(wǎng)、雅虎等公司均已將數(shù)據(jù)中心用于數(shù)據(jù)存儲、網(wǎng)絡(luò)搜索和高性能計算等[1- 5].作為數(shù)據(jù)中心的核心，數(shù)據(jù)中心網(wǎng)絡(luò)需要將部署在數(shù)據(jù)中心的成千上萬臺服務(wù)器通過交換機等網(wǎng)絡(luò)設(shè)施連接起來，組成具有低成本、高帶寬、高可用性、高可靠性和負(fù)載均衡的服務(wù)網(wǎng)絡(luò)[6].

目前，數(shù)據(jù)中心網(wǎng)絡(luò)(DCN)主要分為以交換機為中心的結(jié)構(gòu)和以服務(wù)器為中心的結(jié)構(gòu)[7].在以交換機為中心的結(jié)構(gòu)中，數(shù)據(jù)轉(zhuǎn)發(fā)功能完全依靠交換設(shè)備(交換機)來完成，服務(wù)器的作用僅限于計算與存儲等；以服務(wù)器為中心的結(jié)構(gòu)中，服務(wù)器除了要完成計算與存儲功能外，還需要實現(xiàn)數(shù)據(jù)包的路由選擇與轉(zhuǎn)發(fā)功能.文獻[8- 9]提出了交換機和服務(wù)器都具有數(shù)據(jù)轉(zhuǎn)發(fā)和路由選擇功能的雙中心結(jié)構(gòu).隨著虛擬技術(shù)的廣泛應(yīng)用，文獻[10]提出了DCN虛擬化的解決方法，基于虛擬網(wǎng)絡(luò)的數(shù)據(jù)中心網(wǎng)絡(luò)結(jié)構(gòu)被提出.在數(shù)據(jù)中心網(wǎng)絡(luò)結(jié)構(gòu)中，包括有Fat-Tree[11],DCell[12],BCube[13]和FiConn[14]等.

在Fat-Tree中，n個端口的交換機被分成n個pod，每個pod包含2層，即邊緣層和聚合層，每層n/2臺交換機.邊緣層的交換機用一半數(shù)量的端口連接主機，剩余一半端口連接聚合層交換機.在Fat-Tree的核心層有(n/2)2臺n端口的核心交換機.核心交換機的每個端口分別連接不同的pod中的聚合層交換機.因此，F(xiàn)at-Tree可連接n3/4臺主機.

DCell采用層次結(jié)構(gòu)通過遞歸方式將較小的網(wǎng)絡(luò)單元通過互連方式形成更大的網(wǎng)絡(luò)結(jié)構(gòu).在DCell中，DCell0是最小的基本單元，由一臺n(n≤8)個端口的微型交換機和連接到交換機上的n臺服務(wù)器構(gòu)成.n+1個DCell0通過服務(wù)器之間的互連可獲得DCell1；其互連規(guī)則是：第i個DCell0中的第j-1臺服務(wù)器連接到第j個DCell0中的第i臺服務(wù)器上.

BCube是以服務(wù)器為中心的互連拓?fù)浣Y(jié)構(gòu)，是一種采用分層、遞歸方式構(gòu)造的數(shù)據(jù)中心網(wǎng)結(jié)構(gòu).一個BCube0是由一臺n端口交換機和連接到交換機上的n臺服務(wù)器構(gòu)成，BCube1是由n臺n個端口交換機將n個BCube0連接而構(gòu)成.更一般地，一個BCubem是由n臺n端口交換機將n個BCubem-1連接而構(gòu)成.因此，在BCubem中，每臺服務(wù)器有m+1個端口.

FiConn也是層次模型，與DCell相似采用遞歸方式形成網(wǎng)絡(luò)結(jié)構(gòu).然而，F(xiàn)iConn中的每臺服務(wù)器僅有2個網(wǎng)絡(luò)端口，即僅有2條鏈路，因而將遭受負(fù)載均衡問題.

近年來，對小世界網(wǎng)絡(luò)現(xiàn)象[15]的研究也對數(shù)據(jù)中心網(wǎng)絡(luò)產(chǎn)生了影響.小世界網(wǎng)絡(luò)具有兩個性質(zhì)：路徑長度短，聚集系數(shù)(Clustering Coefficient)較大.對于數(shù)據(jù)中心網(wǎng)絡(luò)而言，路徑長度短意味著隨機選擇的兩個節(jié)點之間的跳數(shù)較小，聚集系數(shù)較大意味著網(wǎng)絡(luò)有可能在高負(fù)載的條件下保持良好的性能.文獻[16]指出具有小世界網(wǎng)絡(luò)性質(zhì)的數(shù)據(jù)中心網(wǎng)絡(luò)具有較好的容錯性，對突發(fā)性的高負(fù)載具有一定的優(yōu)勢.

文中定義了一個常數(shù)度代數(shù)圖Gcoset，然后在此基礎(chǔ)上構(gòu)建了一個數(shù)據(jù)中心網(wǎng)絡(luò)的虛擬化拓?fù)浣Y(jié)構(gòu)GDCN，描述了GDCN的靜態(tài)模型和Gcoset的路由算法；并給出了GDCN結(jié)構(gòu)以及一個具體實現(xiàn)；最后將GDCN與其他DCN進行了對比.

1 GDCN的靜態(tài)模型

?(x1,y1),(x2,y2)∈G,有

(x1,y1)?(x2,y2)=(σy2(x1⊕x2),y1+y2).

其中：“⊕”是異或操作，“+”是模q加法操作,σy定義為

顯然，運算“?”在G上是封閉的，但是“?”不滿足結(jié)合律，因此代數(shù)系統(tǒng)(G,?)是廣群.

廣群(G,?)有如下性質(zhì)：

(1)有右單位元(0q,0).

(2)有右逆元，元素(x,y)的右逆元為(x,-y).

(3)既不存在左零元，也不存在右零元.

(4)不滿足交換律.因此規(guī)定：(g1?g2)?g3簡寫為g1?g2?g3或者g1g2g3(?g1,g2,g3∈G).

(5)滿足右消去律，即

?(x1,y1),(x2,y2),(x,y)∈G,

如果(x1,y1)?(x,y)=(x2,y2)?(x,y),

則(x1,y1)=(x2,y2).

定義2 設(shè)(x,y),(x′,y′)∈G，如果對任意的g∈G，有g(shù)?(x,y)?(x′,y′)=g，則稱(x′,y′)是(x,y)在G上的單側(cè)逆元，簡稱為(x′,y′)是(x,y)的單側(cè)逆元，記為(x,y)T.

在(G,?)中，有?(x,y)∈G，其單側(cè)逆元(x,y)T=(σ-y(x),-y)，同時，(x,y)T的單側(cè)逆元為(x,y).因此，有下面結(jié)論.

結(jié)論1 元素(x,y)的單側(cè)逆元是唯一的.

為了后面討論方便，作如下標(biāo)記:設(shè)S?G，記ST={sT|s∈S}.

下面給出Gcoset(G,S)圖的定義，首先定義一個子集S：

S=Sc∪St∪Sr∪Sd.

定義3Γ=Gcoset(G,S)是由G和S確定的代數(shù)圖定義為

V(Γ)=G，E(Γ)={(g,gs)|g∈G,s∈S}.

對任意的邊(g,gs)∈E(Γ),有g(shù)∈G,s∈S；由S=ST可知，sT∈S，于是有g(shù)ssT=g，故(gs,g)∈E(Γ)，因此圖Γ是無向圖.圖1是結(jié)點(0q,0)及其鄰居的鄰接情況，實線為與結(jié)點(0q,0)直接相連的邊，而虛線為鄰居間的連接邊.

圖1 結(jié)點(0q,0)及其鄰居的鄰接情況

圖Γ有如下性質(zhì)：

(1)Γ是連通的無環(huán)圖;

(2)Γ是8度正則圖;

(3)Γ是點傳遞圖;

Γ的直徑可以在后面的路由算法中得到驗證.

對于給定的q值，圖Γ的結(jié)點數(shù)為N=2q×q，因此可得性質(zhì)(5).

(5)Γ的直徑為O(logN)；

由于Γ圖是點傳遞的，所有結(jié)點的聚集系數(shù)是相同的.這里考慮結(jié)點(0q,0)，由圖1可知，結(jié)點(0q,0)有8個鄰居，鄰居間有6條邊，因此，根據(jù)聚集系數(shù)的定義有性質(zhì)(6).

(6)Γ的聚集系數(shù)CC=2×6/(8×7)=0.214.

定義4 稱邊{(g,gs)|g∈G,s∈Sc}為c邊，完全由c邊構(gòu)成的圈稱為c圈，邊{(g,gs)|g∈G,s∈St}稱為t邊，完全由t邊構(gòu)成的圈稱為t圈，邊{(g,gs)|g∈G,s∈Sr}稱為r邊，完全由r邊構(gòu)成的圈稱為r圈，邊{(g,gs)|g∈G,s∈Sd}稱為d邊，完全由d邊構(gòu)成的圈稱為d圈.

在圖Γ中有如下結(jié)論.

結(jié)論2 在圖Γ中，c圈是存在的，Gcoset(G,S)共有2q個c圈，并且每個c圈有q個頂點.

結(jié)論3 在圖Γ中，當(dāng)q>4時，t圈是存在的，當(dāng)2|q=0時Γ中共有2q+1個t圈，并且每個t圈有q/2個頂點，否則Γ中共有2q個t圈，并且每個t圈有q個頂點.

結(jié)論4 在圖Γ中，r圈是存在的，Γ中共有2q個r圈，并且每個r圈有q個頂點.

結(jié)論5 在圖Γ中，d圈是存在的，Γ中共有2q個d圈，并且每個d圈有q個頂點.

2 Gcoset的路由算法

設(shè)源結(jié)點(cx,rx)=(x1,x2,…,xq,rx)、目的結(jié)點(cy,ry)=(y1,y2,…,yq,ry)，可以得到靜態(tài)拓?fù)涞暮唵温酚伤惴?記為算法1)，如下文所示.

輸入：源結(jié)點(x1,x2,…,xq,rx)和目的結(jié)點(y1,y2,…,yq,ry)

Step1:compute Δr=ry-rx

Step2:

if(|Δr|

fori=1 to|Δr| do

if(Δr>0)then

go to the node(x1,x2,…,xq,rx)?(0q,1);

else

go to the node(x1,x2,…,xq,rx)?(0q,-1);

else

fori=1 toq-|Δr| do

if(Δr>0)then

go to the node(x1,x2,…,xq,rx)?(0q,-1);

else

go to the node(x1,x2,…,xq,rx)?(0q,1);

Step3:

fori=1 to q do

if(x1≠yi)then

go to the node(x1,x2,…,xq,rx)?(10q-1,-1);

else

go to the node(x1,x2,…,xq,rx)?(0q,-1);

在算法1的路由選擇中，如果當(dāng)前結(jié)點為v，則選擇下一步的節(jié)點時只考慮了節(jié)點v的部分鄰居結(jié)點(即v?s，其中s∈Sc∪Sr).此外，算法1是單點源路由算法.下面給出Gcoset的分布式算法(記為算法2).

輸入：當(dāng)前結(jié)點(x1,x2,…,xq,rx)，目的結(jié)點(y1,y2,…,yq,ry)

輸出：下一跳的標(biāo)識符

if((x1,x2,…,xq)=(y1,y2,…,yq)andrx=ry)

the destination has been reached.

else{

Δr=(8+ry-rx)mod 8;

if((x1,x2,…,xq)=(y1,y2,…,yq)){

if(Δr=1)

return(x1,x2,…,xq,rx)?(0q,1);

else if(Δr<=4)

return(x1,x2,…,xq,rx)?(0q,2);

else if(Δr<7)

return(x1,x2,…,xq,rx)?(0q,-2);

else if(Δr=7)

return(x1,x2,…,xq,rx)?(0q,-1);

}

else{

∥(y1,y2,…,yq)循環(huán)左移Δr位

(z1,z2,…,zq)=(y1,y2,…,yq)<<<Δr;

if(x1=z1andx2=z2)

return(x1,x2,…,xq,rx)?(0q,-2);

else if(x1=z1)

return(x1,x2,…,xq,rx)?(0q,-1);

else if(x1≠z1andx2≠z2)

return(x1,x2,…,xq,rx)?(110q-2,-2);

else if(x1≠z1)

return(x1,x2,…,xq,rx)?(10q-1,-1);

}

}

在Gcoset的分布式路由算法中，假設(shè)當(dāng)前結(jié)點為v，如果它的下一步結(jié)點出現(xiàn)故障，隨機選擇結(jié)點v的其他鄰居作為下一步結(jié)點，由算法2繼續(xù)進行路由選擇，最終到達目標(biāo)結(jié)點.因此，Gcoset擁有度數(shù)較小、路由算法簡單、容錯性能良好的性質(zhì)，同時還具有路徑長度短和聚集系數(shù)較大的小世界網(wǎng)絡(luò)的特性.下文將基于Gcoset來構(gòu)造GDCN的拓?fù)?

3 Gcoset圖在DCN中的應(yīng)用

3.1 GDCN拓?fù)?/h3>

GDCN是用較小網(wǎng)絡(luò)替代Gcoset圖中的結(jié)點，構(gòu)建出的更大網(wǎng)絡(luò).在GDCN網(wǎng)絡(luò)中，用于替代Gcoset圖中的結(jié)點的網(wǎng)絡(luò)稱為因子網(wǎng)絡(luò)(也被稱為簇).由于Gcoset圖中有q×2q個結(jié)點，因此在GDCN中共有q×2q個簇，每個簇可以由一個交換器和若干服務(wù)器連接組成，也可以是數(shù)據(jù)中心中若干個交換器和若干服務(wù)器連接組成.下面介紹由GDCN構(gòu)成的一種具體的DCN.

(1)(ch,rh)=(cg,rg)?s，s∈S.

(2)若s=(0q,1)，則tg=000,th=001;

若s=(0q,-1)，則tg=001,th=000;

若s=(0q,2)，則tg=010,th=011;

若s=(0q,-2)，則tg=011,th=010;

若s=(0q-11,1)，則tg=100,th=101;

若s=(10q-1,-1)，則tg=101,th=100;

若s=(0q-211,2)，則tg=110,th=111;

若s=(110q-2,-2)，則tg=111,th=110.

圖2為結(jié)點(0q,0)中的服務(wù)器與簇外服務(wù)器的連接情況.為了描述方便，將與服務(wù)器g連接的簇外服務(wù)器h的條件簡記為h=g?s.

圖2 結(jié)點(0q,0)中的服務(wù)器與簇外服務(wù)器的連接情況

Fig.2 Servers’ link between vertex(0q,0)and other clusters

3.2 GDCN容錯路由

在數(shù)據(jù)中心網(wǎng)中，鏈路錯誤是不可避免的，因此必須通過路由算法保證在鏈路失效時仍然可以實現(xiàn)數(shù)據(jù)包的轉(zhuǎn)發(fā).在數(shù)據(jù)中心網(wǎng)中，有3種失效類型：鏈路失效、服務(wù)器故障和交換機故障.為了及時發(fā)現(xiàn)失效設(shè)備，服務(wù)器應(yīng)周期地向外發(fā)出查詢數(shù)據(jù)包以獲知相鄰服務(wù)器的狀態(tài).對于一臺服務(wù)器來說，鏈路失效的結(jié)果直接表現(xiàn)為無法收到相鄰服務(wù)器或所連接交換機的響應(yīng)數(shù)據(jù)包，因此，可以將鏈路錯誤根據(jù)情況視為服務(wù)器故障和交換機故障處理.考慮到失效頂點的問題，在選擇下一跳前，調(diào)用函數(shù)GetReachable()探測下一跳頂點是否可達，如果不可達，算法會選擇另一個正常的鄰居頂點，當(dāng)然，在這種情況下路由長度有一定的增長.GDCN的容錯路由算法(記為算法3)如下文所示.

輸入：當(dāng)前服務(wù)器g=(x1,x2,…,xq,rx,tx)，目的服務(wù)器h=(y1,y2,…,yq,ry,ty)

輸出：下一跳的標(biāo)識符

if((x1,x2,…,xq)=(y1,y2,…,yq)andrx=ryandtx=ty)

the destination has been reached.

else if((x1,x2,…,xq)=(y1,y2,…,yq) andrx=ry)

return GetReachable((x1,x2,…xq,rx,ty))

else{

Δr=(8+ry-rx)mod 8;

if((x1,x2,…,xq)=(y1,y2,…yq)){

if(Δr=1)

return GetReachable(g?(0q,1));

else if(Δr<=4)

return GetReachable(g?(0q,2),g?(0q,1));

else if(Δr<7)

return

GetReachable(g?(0q,-2),g?(0q,-1));

else if(Δr=7)

return GetReachable(g?(0q,-1));

}

else{

∥(y1,y2,…,yq)循環(huán)左移Δr位

(z1,z2,…,zq)=(y1,y2,…,yq)<<<Δr;

if(x1=z1andx2=z2)

return

GetReachable(g?(0q,-2),g?(0q,-1));

else if(x1=z1)

return GetReachable(g?(0q,-1));

else if(x1≠z1andx2≠z2)

return

GetReachable(g?(110q-2,-2),g?(10q-1,-1));

else if(x1≠z1)

return GetReachable(g?(10q-1,-1));

}

}

4 GDCN與其他DCN模型的比較

數(shù)據(jù)中心的規(guī)模在不斷擴展， DCN模型的可擴展性也得到極大的關(guān)注.有些模型的可擴展性受服務(wù)器和交換機的端口數(shù)的限制.在DCN模型中，交換機數(shù)量對構(gòu)建數(shù)據(jù)中心網(wǎng)絡(luò)的影響比較大，不同的DCN模型，所需交換機數(shù)量差異也比較大.

從表1可以看出，GDCN的可擴展性不受服務(wù)器端口數(shù)目的限制，F(xiàn)at-Tree和FiConn也具有同樣的優(yōu)勢，但是服務(wù)器端口數(shù)目將影響Dcell和Bcube的可擴展性.與Dcell、Bcube和FiConn一樣，交換機端口數(shù)目對GDCN的可擴展性沒有影響，但是Fat-Tree受交換機端口數(shù)目的影響.在構(gòu)建GDCN時，所需要的交換機數(shù)據(jù)也是比較少的.綜上所述，GDCN結(jié)構(gòu)簡單，通信性能較高，可擴展性和容錯性也比較好，使得它適合于大規(guī)模數(shù)據(jù)中心網(wǎng)絡(luò)的構(gòu)建.

表1 Fat-Tree、DCell、BCube、FiConn和GDCN模型的比較

5 結(jié)語

文中基于代數(shù)圖方法構(gòu)造了一個數(shù)據(jù)中心網(wǎng)GDCN，網(wǎng)絡(luò)靜態(tài)拓?fù)淠Ｐ蜑?度正則度，從而具有更好的對稱性和簡單的結(jié)構(gòu)；此外，GDCN的網(wǎng)絡(luò)直徑僅為O(logN)，具有較簡單的路由算法和良好的路由容錯性,還具備了良好的小世界網(wǎng)絡(luò)特性.今后將對GDCN的小世界網(wǎng)絡(luò)特性和對稱性質(zhì)做進一步的研究,并利用這些性質(zhì)開發(fā)組播、負(fù)載均衡和內(nèi)容分發(fā)等應(yīng)用.

[1] AHMED F,MANNHEIM H.Amazon elastic compute cloud (Amazon EC2) [OL].(2008- 12- 10) [2016- 07- 12].http:∥aws.amazon.com/ec2/.

[2] CARR D.How Google works [OL].(2006- 07- 06) [2016- 07- 12].http:∥www.baselinemag.com/c/a/Infrastructure/ How-Google-Works-1.

[3] DEAN J，GHEMAWAT S.MapReduce:simplified data processing on large clusters [J].Communications of the ACM，2008，51(1):107- 113.

[4] HOFF T.Google architecture [OL].(2008- 11- 22) [2016- 07- 12].http:∥highscalability.com/google-architecture.

[5] RABBE L.Powering the Yahoo! network [OL]. (2006- 11- 27) [2016- 07- 12] .http:∥yodel.yahoo.com/2006/11/ 27/powering-the-yahoo-network.

[6] ZHANG Y，ANSARI N.On architecture design，congestion notification，TCP incast and power consumption in data centers [J].IEEE Communications Surveys & Tutorials，2013，15(1):39- 64.

[7] 魏祥麟，陳鳴,范建華,等.數(shù)據(jù)中心網(wǎng)絡(luò)的體系結(jié)構(gòu) [J].軟件學(xué)報，2013,24(2):295- 316.

WEI Xiang-lin,CHEN Ming,FAN Jian-hua,et al.Architecture of the data center network [J].Journal of Sofware,2013,24(2):295- 316.

[8] LI D，WU J.FCell:towards the tradeoffs in designing data center network architectures [C] ∥Proceedings of the 24th International Conference on Computer Communication and Networks (ICCCN).Las Vegas:IEEE，2015:1- 8.

[9] LI D，WU J.Dual-centric data center network architectures [C]∥Proceedings of the 44th International Confe-rence on Parallel Processing.Piscataway:IEEE Communications Society，2015:679- 688.

[10] BARI M F，BOUTABA R，ESTEVES R，et al.Data center network virtualization:a survey [J].IEEE Communi-cations Surveys & Tutorials，2013，15(2):909- 928.

[11] AL-FARES M，LOUKISSAS A，VAHDAT A.A scalable，commodity data center network architecture [J].ACM SIGCOMM Computer Communication Review，2008，38(4):63- 74.

[12] GUO C，WU H，TAN K，et al.Dcell:a scalable and fault-tolerant network structure for data centers [J].ACM SIGCOMM Computer Communication Review，2008，38(4):75- 86.

[13] GUO C，LU G，LI D，et al.BCube:a high performance，server-centric network architecture for modular data centers [J].ACM SIGCOMM Computer Communication Review，2009，39(4):63- 74.

[14] LI D，GUO C，WU H，et al.FiConn:using backup port for server interconnection in data centers [C]∥Pro-ceedings of the INFOCOM 2009.Piscataway:IEEE，2009:2276- 2285.

[15] WATTS D J，STROGATZ S H.Collective dynamics of ‘small-world’networks [J].Nature，1998，393(6684):440- 442.

[16] SHIN J Y，WONG B，SIRER E G.Small-world datacen-ters [C]∥Proceedings of the 2nd ACM Symposium on Cloud Computing.New York:ACM，2011:1- 13.

ANovelStructuredDataCenterNetworkwithConstantDegreeandSmall-WorldCharacteristics

LIMei-sheng1,2XIAOWen-jun3LAIZheng-wen1ZHANGZhan-ying1HANDong2

(1. School of Computer Science and Engineering, South China University of Technology, Guangzhou 510006, Guangdong, China;2. Department of Internet Finance and Information Engineering, Guangdong University of Finance, Guangzhou 510520, Guangdong,China;3. School of Software Engineering, South China University of Technology, Guangzhou 510006, Guangdong, China)

Firstly, Gcoset, an algebraic graph with constant degree, is defined. Secondly, on the basis of Gcoset, a virtualized topology structure named GDCN, which is of eight-degree regularity and symmetry for data center network, is proposed. Then, the static model of GDCN and the routing algorithm of GCoset are both described in detail, and a concrete implementation of GDCN is presented. Finally, a comparison between GDCN and other data center network models is made. The results show that GDCD is of a network diameter of onlyO(logN) and needs relatively simple routing algorithm, and that it possesses simple structure, high communication performance, good scalability and excellent fault tolerance.

constant degree; data center network; small-world characteristic; virtualization; topology structure; routing algorithm

2017- 01- 16

國家自然科學(xué)基金資助項目(61170313，61103037,61370003)

*Foundationitems: Supported by the National Natural Science Foundation of China(61170313,61103037,61370003)

李梅生(1975-),男,博士生,講師，主要從事數(shù)據(jù)中心網(wǎng)絡(luò)、復(fù)雜網(wǎng)絡(luò)研究.E-mail:meisen04@163.com

?通信作者: 肖文俊(1950-),男,教授,博士生導(dǎo)師,主要從事互連網(wǎng)絡(luò)、網(wǎng)絡(luò)虛擬化研究.E-mail:2259975946@qq.com

1000- 565X(2017)07- 0063- 06

TP 393

10.3969/j.issn.1000-565X.2017.07.009