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

郭彬 王長(zhǎng)山

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

0 引言

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

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

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

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

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

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

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

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

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

圖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é)點(diǎn)R0分別與路由R1、R2及R4互聯(lián)，這里我們對(duì)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行一些改進(jìn)，使之具有對(duì)稱(chēng)性和更多的路徑多樣性。如圖4所示即為改進(jìn)后的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)—BFC網(wǎng)絡(luò)結(jié)構(gòu)，這樣通過(guò)數(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)過(guò)改進(jìn)后的路由節(jié)點(diǎn)R0分別與路由節(jié)點(diǎn)R1、R2、R3、R4以及R5之間都存在了通路，大大增加了網(wǎng)絡(luò)的路徑多樣性，可以有效地降低網(wǎng)絡(luò)的擁塞程度；同時(shí)網(wǎng)絡(luò)也具有了對(duì)稱(chēng)性，更加便于擴(kuò)展。

2 路由算法

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

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

圖5 路由端口示意圖

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

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

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

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

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

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

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

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

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

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

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

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

3 算法仿真

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

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

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

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

4 結(jié)論

蝴蝶網(wǎng)絡(luò)的路徑多樣性，降低了網(wǎng)絡(luò)的傳輸延遲。在路由過(guò)程中，合理使用自適應(yīng)路由算法可以提供一個(gè)性能優(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ò)，由于提供了更多的路由通路，在路徑多樣性與時(shí)延方面有了提高。

[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.