一種改進(jìn)型的蝴蝶網(wǎng)絡(luò)在片上網(wǎng)絡(luò)中的應(yīng)用

郭彬 王長山

西安電子科技大學(xué)計算機學(xué)院 陜西 710071

0 引言

本文介紹一種改進(jìn)型的蝴蝶網(wǎng)絡(luò)—BFC網(wǎng)絡(luò)拓?fù)?，它將結(jié)合蝴蝶網(wǎng)絡(luò)與Clos網(wǎng)絡(luò)的優(yōu)點，克服它們的缺點，既擁有較高的傳輸速度，又具有豐富的路徑多樣性，解決擁塞能力優(yōu)于蝴蝶網(wǎng)絡(luò)。

1 拓?fù)浣Y(jié)構(gòu)介紹

蝶形網(wǎng)絡(luò)源于超立方體網(wǎng)絡(luò)，是超立方體網(wǎng)絡(luò)的一個變形網(wǎng)絡(luò)。

Clos網(wǎng)絡(luò)最早于1953年由Charles Clos提出。每個Clos網(wǎng)絡(luò)都如同是兩個蝴蝶網(wǎng)絡(luò)疊加起來形成的，其中一個的輸出級與另個輸入級疊加。

Clos網(wǎng)絡(luò)的路由過程必須經(jīng)過中間級模塊。由于中間級模塊的存在，使得每對節(jié)點間可以存在多條路徑，滿足了路徑多樣性的要求，但同時也引入了大量的電線以及額外的路由跳數(shù)，導(dǎo)致網(wǎng)絡(luò)的延遲與成本都大大增加。

蝶形網(wǎng)絡(luò)可以充分發(fā)揮高度數(shù)路由的優(yōu)勢，但由于不具有路徑多樣性，在處理擁塞方面性能表現(xiàn)不佳。而Clos網(wǎng)絡(luò)具有良好的路徑多樣性，它可以在每對節(jié)點之間提供多條數(shù)據(jù)鏈路，很好地解決了網(wǎng)絡(luò)擁塞問題。但由于在路由過程中必須使用中間級交換模塊，需要接入更多的線路，從而在路由時延方面較蝶形網(wǎng)絡(luò)要高很多，而且在網(wǎng)絡(luò)開銷方面也比蝶形網(wǎng)絡(luò)要大。

本節(jié)提出的 BFC網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)則綜合了以上兩種網(wǎng)絡(luò)的優(yōu)勢，同時又克服了它們的缺陷。它源自蝶形網(wǎng)絡(luò)，具有蝶形網(wǎng)絡(luò)優(yōu)良的網(wǎng)絡(luò)性能，路由時延較低，網(wǎng)絡(luò)開銷較小，同時又具有Clos網(wǎng)絡(luò)的路徑多樣性優(yōu)點。

BFC網(wǎng)絡(luò)是將蝶形網(wǎng)絡(luò)中同層不同維的數(shù)個節(jié)點模塊整合成一個新的模塊。原網(wǎng)絡(luò)中不同層間的信息交換在新網(wǎng)絡(luò)中統(tǒng)一使用一條雙向鏈路來完成。如圖1所示為一個三層蝶形網(wǎng)絡(luò)，每個節(jié)點都是一個路由節(jié)點，它們可以連接數(shù)個資源節(jié)點。將圖中最左邊的四個路由節(jié)點R0、R1、R2以及R3整合為一個路由節(jié)點，其余各節(jié)點用同樣的方法處理，便可以得到圖2所示的路由節(jié)點圖。這種變換形成的圖又被稱為平面蝴蝶網(wǎng)絡(luò)結(jié)構(gòu)。在新的網(wǎng)絡(luò)拓?fù)鋱D中，合并的四個路由節(jié)點間的信息傳輸在節(jié)點內(nèi)部直接完成，節(jié)點間的數(shù)據(jù)傳輸使用合并后的數(shù)據(jù)鏈路傳輸。該鏈路是雙向的，可同時滿足輸入和輸出。

圖1 三層蝶形網(wǎng)絡(luò)路由節(jié)點圖

圖2 平面蝴蝶網(wǎng)絡(luò)

將圖2所示的結(jié)構(gòu)圖進(jìn)行一定的拓?fù)湟?guī)劃可形成如圖3的平面蝴蝶網(wǎng)絡(luò)結(jié)構(gòu)。

圖3 變換拓?fù)浞植己蟮钠矫婧W(wǎng)絡(luò)

由圖3可知，路由節(jié)點R0分別與路由R1、R2及R4互聯(lián)，這里我們對網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行一些改進(jìn)，使之具有對稱性和更多的路徑多樣性。如圖4所示即為改進(jìn)后的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)—BFC網(wǎng)絡(luò)結(jié)構(gòu)，這樣通過數(shù)次變換將蝶形網(wǎng)絡(luò)逐漸地演變?yōu)锽FC網(wǎng)絡(luò)結(jié)構(gòu)。

圖4 BFC網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

從圖4中可以看出，經(jīng)過改進(jìn)后的路由節(jié)點R0分別與路由節(jié)點R1、R2、R3、R4以及R5之間都存在了通路，大大增加了網(wǎng)絡(luò)的路徑多樣性，可以有效地降低網(wǎng)絡(luò)的擁塞程度；同時網(wǎng)絡(luò)也具有了對稱性，更加便于擴展。

2 路由算法

本節(jié)為 BFC網(wǎng)絡(luò)拓?fù)湓O(shè)計了一種確定性無死鎖的路由算法，該算法通過比較當(dāng)前節(jié)點與目標(biāo)節(jié)點橫縱坐標(biāo)的大小來決定輸出的端口。

在路由數(shù)N=16的拓?fù)浣Y(jié)構(gòu)當(dāng)中，將網(wǎng)絡(luò)置于坐標(biāo)系當(dāng)中，則每個路由都具有對應(yīng)的坐標(biāo)值(x,y)。與節(jié)點相鄰的有4個對角線節(jié)點和4個橫縱節(jié)點，在這里規(guī)定，與路由器IP核相連的端口號為0；X軸方向節(jié)點對應(yīng)的端口為1，2，3；Y軸方向?qū)?yīng)的端口號為4，5，6；對角線節(jié)點從右上端口開始順時針旋轉(zhuǎn)的四個端口號為別為7，8，9，10，如圖5所示。

圖5 路由端口示意圖

設(shè)當(dāng)前節(jié)點坐標(biāo)為 C(cx,cy)，目標(biāo)節(jié)點坐標(biāo) D(dx,dy)，輸出端口為Outport。路由算法的描述為：

當(dāng)路由接收到一個數(shù)據(jù)包時，通過檢查數(shù)據(jù)包頭中包含的目標(biāo)節(jié)點信息，計算出目標(biāo)節(jié)點與當(dāng)前節(jié)點的坐標(biāo)差值：X= dx-cx，Y=dy-cy。

當(dāng) X==0且 Y==0，則表明數(shù)據(jù)包到達(dá)目標(biāo)節(jié)點，outport=0；

當(dāng)X==0且Y>0，則表明數(shù)據(jù)包的目標(biāo)節(jié)點在當(dāng)前節(jié)點的右方向，選擇右方向的端口進(jìn)行輸出；

當(dāng)X==0且Y＜0，則表明數(shù)據(jù)包的目標(biāo)節(jié)點在當(dāng)前節(jié)點的左方向，選擇左方向的端口進(jìn)行輸出；

當(dāng)X＜0且Y==0，則表明數(shù)據(jù)包的目標(biāo)節(jié)點在當(dāng)前節(jié)點的下方向，選擇下方向的端口進(jìn)行輸出；

當(dāng)X＜0且Y==0，則表明數(shù)據(jù)包的目標(biāo)節(jié)點在當(dāng)前節(jié)點的上方向，選擇上方向的端口進(jìn)行輸出；

當(dāng)X>0且Y>0，則表明數(shù)據(jù)包的目標(biāo)節(jié)點在當(dāng)前節(jié)點的右上方向，選擇右上方向的端口進(jìn)行輸出；

當(dāng)X>0且Y＜0，則表明數(shù)據(jù)包的目標(biāo)節(jié)點在當(dāng)前節(jié)點的左上方向，選擇左上方向的端口進(jìn)行輸出；

當(dāng)X＜0且Y>0，則表明數(shù)據(jù)包的目標(biāo)節(jié)點在當(dāng)前節(jié)點的右下方向，選擇右下方向的端口進(jìn)行輸出；

當(dāng)X＜0且Y＜0，則表明數(shù)據(jù)包的目標(biāo)節(jié)點在當(dāng)前節(jié)點的左下方向，選擇左下方向的端口進(jìn)行輸出。算法偽代碼如下：

該種算法限制了數(shù)據(jù)包路由的方向，數(shù)據(jù)包必須在當(dāng)前節(jié)點與目標(biāo)節(jié)點形成的方形區(qū)域內(nèi)路由，且方向必須始終是向著目標(biāo)節(jié)點的，這樣就限制了環(huán)的產(chǎn)生，從而破壞了死鎖形成的必要條件。故該路由算法是無死鎖的。

3 算法仿真

本文使用OPNET仿真軟件對改進(jìn)型的平面蝴蝶拓?fù)浣Y(jié)構(gòu)及其算法進(jìn)行了仿真，通過仿真來了解該拓?fù)浣Y(jié)構(gòu)的各方面性能。為了對比該拓?fù)浣Y(jié)構(gòu)的優(yōu)缺點，我們將它與傳統(tǒng)的蝴蝶拓?fù)浣Y(jié)構(gòu)在相同的網(wǎng)絡(luò)環(huán)境下進(jìn)行了仿真性能對比。

圖6是在均勻流量模式下兩種拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)性能的比較。

圖6 均勻流量模式下兩種網(wǎng)絡(luò)拓?fù)湫阅鼙容^

由圖可以看出，BFC的性能要優(yōu)于蝶形網(wǎng)絡(luò)。對于端到端時延，蝶形網(wǎng)絡(luò)在注入率到達(dá)0.2的時候就已經(jīng)開始上升，而BFC網(wǎng)絡(luò)則在注入率持續(xù)增加到0.35時才開始上升，BFC網(wǎng)絡(luò)鏈路數(shù)目多，路徑多樣性豐富的優(yōu)勢在此處體現(xiàn)了出來。吞吐性能與端到端時延類似，BFC網(wǎng)絡(luò)吞吐飽和時對應(yīng)的注入率要遠(yuǎn)高于蝶形網(wǎng)絡(luò)，可以達(dá)到的飽和度也高于蝶形網(wǎng)絡(luò)。

4 結(jié)論

蝴蝶網(wǎng)絡(luò)的路徑多樣性，降低了網(wǎng)絡(luò)的傳輸延遲。在路由過程中，合理使用自適應(yīng)路由算法可以提供一個性能優(yōu)良的傳輸網(wǎng)絡(luò)。相比于Clos網(wǎng)絡(luò)，BFC網(wǎng)絡(luò)具有更少的跳數(shù)，從而降低了網(wǎng)絡(luò)延遲與成本。相比于傳統(tǒng)的蝴蝶網(wǎng)絡(luò)，它提供了路徑多樣性，減少了網(wǎng)絡(luò)擁塞。而相比于平面蝴蝶網(wǎng)絡(luò)，由于提供了更多的路由通路，在路徑多樣性與時延方面有了提高。

[1] Frank K.Hwang and Wen-Dar Lin.The Number of Rearrangements in a 3-stage Clos Network Using an Auxiliary Switch,Springer-Verlag Berlin Heidelberg.1998.

[2] Kim, J.,W.J.Dally and D.Abts.Adaptive routing in high-radix clos network.in 2006.