基于獨(dú)立生成樹(shù)的網(wǎng)絡(luò)多路徑傳輸方法研究

劉靜　樊建席

摘要：將高性能并行計(jì)算中的獨(dú)立生成樹(shù)理論應(yīng)用到企業(yè)網(wǎng)絡(luò)傳輸中，首先將企業(yè)網(wǎng)絡(luò)拓?fù)涑橄鬄榛ミB網(wǎng)絡(luò)提出一種獨(dú)立生成樹(shù)可遞歸構(gòu)造算法，生成多棵獨(dú)立生成樹(shù)，進(jìn)而給出一種基于獨(dú)立生成樹(shù)的網(wǎng)絡(luò)多路徑傳輸方式并在傳輸時(shí)間、傳輸速度上進(jìn)行了網(wǎng)絡(luò)傳輸性能分析，指出其優(yōu)勢(shì)。

關(guān)鍵詞：互連圖；獨(dú)立生成樹(shù)；多路徑傳輸

中圖分類號(hào)：TP391.3 文獻(xiàn)標(biāo)識(shí)碼：A DOI：10.3969/j.issn.1003-6970.2016.04.007

0 引言

隨著兩化融合的深入，信息化與工業(yè)化的融合程度越來(lái)越高，信息化帶動(dòng)工業(yè)化的發(fā)展。隨著互聯(lián)網(wǎng)絡(luò)的普及，工業(yè)信息網(wǎng)絡(luò)逐漸覆蓋了各個(gè)領(lǐng)域。近年來(lái)國(guó)防、電網(wǎng)、城市軌交、天氣預(yù)報(bào)等領(lǐng)域均出現(xiàn)龐大計(jì)算量的應(yīng)用問(wèn)題，這些問(wèn)題對(duì)互連網(wǎng)絡(luò)中的各節(jié)點(diǎn)性能提出了更高要求。

而現(xiàn)實(shí)生活中的計(jì)算機(jī)網(wǎng)絡(luò)、移動(dòng)互聯(lián)網(wǎng)絡(luò)及通訊網(wǎng)絡(luò)等，常常會(huì)由于鏈路或節(jié)點(diǎn)故障而影響網(wǎng)絡(luò)功能降低甚至失效。目前常用的樹(shù)型結(jié)構(gòu)和多路徑結(jié)構(gòu)都是平面結(jié)構(gòu)，以獨(dú)立生成樹(shù)為基礎(chǔ)的網(wǎng)絡(luò)性能研究是高性能并行計(jì)算研究的熱點(diǎn)，這一研究通常應(yīng)用在立方體、超立方體、扭立方體等方面，以處理復(fù)雜計(jì)算問(wèn)題，在高性能并行計(jì)算方面表現(xiàn)良好。多路徑傳輸在網(wǎng)絡(luò)性能優(yōu)化方面被廣泛使用。此本文提出一種基于獨(dú)立生成樹(shù)的工業(yè)企業(yè)網(wǎng)絡(luò)多路徑傳輸機(jī)制。

1 互連網(wǎng)絡(luò)與獨(dú)立生成樹(shù)

1.1 互連網(wǎng)絡(luò)

并行計(jì)算機(jī)的內(nèi)部處理器或處理機(jī)，按照一定方式連接起來(lái)，形成的網(wǎng)絡(luò)稱為多處理器互連網(wǎng)絡(luò)，即互連網(wǎng)?；ミB網(wǎng)絡(luò)成為研究并行計(jì)算的核心，對(duì)互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及其性質(zhì)研究是并行計(jì)算機(jī)系統(tǒng)的一個(gè)重要課題。常用的互連網(wǎng)絡(luò)，如樹(shù)、圈、網(wǎng)格等結(jié)構(gòu)的構(gòu)造是國(guó)內(nèi)外網(wǎng)絡(luò)研究的焦點(diǎn)。國(guó)內(nèi)外研究者提出了多種不同的互連網(wǎng)絡(luò)結(jié)構(gòu)，如超立方體、樹(shù)型網(wǎng)絡(luò)、奇圖、偶圖、蝶形圖等。無(wú)論哪種網(wǎng)絡(luò)結(jié)構(gòu)，其網(wǎng)絡(luò)拓?fù)涠伎梢杂脠D來(lái)描述，在互連網(wǎng)研究中，網(wǎng)絡(luò)一般定義為一個(gè)圖，其中V為頂點(diǎn)集，E為邊集，I。

1.2 獨(dú)立生成樹(shù)

運(yùn)用“圖”、“子圖”、“路和連通性”等圖論知識(shí)將企事業(yè)單位的局域網(wǎng)網(wǎng)絡(luò)構(gòu)建為基礎(chǔ)理論研究中的互連圖G，圖G上的兩棵生成樹(shù)，如果具有相同根，且由根到樹(shù)中任一頂點(diǎn)的兩條路徑（每棵生成樹(shù)各一條）為頂點(diǎn)（邊）不相交路徑，則稱這兩棵樹(shù)頂點(diǎn)（邊）互相獨(dú)立。若n棵生成樹(shù)兩兩頂點(diǎn)（邊）相互獨(dú)立，則稱之為n棵頂點(diǎn)（邊）獨(dú)立生成樹(shù)（Vertex-Independent Spanning Trees），簡(jiǎn)稱IST（Edge-Independent Spanning Trees，簡(jiǎn)稱EIST）。頂點(diǎn)獨(dú)立的生成樹(shù)一定是邊獨(dú)立的生成樹(shù)，因此在工程實(shí)踐的互連網(wǎng)絡(luò)圖上，構(gòu)建頂點(diǎn)獨(dú)立生成樹(shù)IST。

國(guó)內(nèi)以FAN為代表的并行與分布式系統(tǒng)研究者針對(duì)超立方體等一類互連網(wǎng)絡(luò)，通過(guò)構(gòu)建獨(dú)立生成樹(shù)（Independent Spanning Tree，簡(jiǎn)稱IST）進(jìn)行理論研究，認(rèn)為超立方體及其變型具有兩個(gè)共性（一一對(duì)應(yīng)連接和可遞歸構(gòu)造性質(zhì)），提出一一對(duì)應(yīng)連接網(wǎng)絡(luò)（Biiective Connection Network，簡(jiǎn)稱BC網(wǎng)絡(luò)）的概念，并在此基礎(chǔ)上系統(tǒng)化地論證了BC網(wǎng)絡(luò)中獨(dú)立生成樹(shù)的存在，給出獨(dú)立生成樹(shù)的可遞歸構(gòu)造算法。

2 基于獨(dú)立生成樹(shù)的網(wǎng)絡(luò)多路徑傳輸機(jī)制

2.1 網(wǎng)絡(luò)拓?fù)錁?gòu)建

無(wú)論是信息技術(shù)企業(yè)還是生產(chǎn)制造等非信息技術(shù)服務(wù)單位，其網(wǎng)絡(luò)信息化應(yīng)用程度比較高，都擁有一個(gè)比較復(fù)雜的企業(yè)局域網(wǎng)，通過(guò)分設(shè)不同的生產(chǎn)管理或服務(wù)部門，劃分不同的子網(wǎng)絡(luò)，這里既包括傳統(tǒng)的固定網(wǎng)絡(luò)，也包含新型的移動(dòng)互聯(lián)網(wǎng)絡(luò)、無(wú)線網(wǎng)絡(luò)等形式。根據(jù)企事業(yè)單位業(yè)務(wù)需求、規(guī)模大小，單位局域網(wǎng)的設(shè)計(jì)規(guī)劃也有所不同，但總體采用樹(shù)型結(jié)構(gòu)設(shè)計(jì)。運(yùn)用圖論中的“圖”、“子圖”、“路和連通性”等知識(shí)將企事業(yè)單位的局域網(wǎng)網(wǎng)絡(luò)構(gòu)建為基礎(chǔ)理論研究中的互連圖，效果如圖l所示。

2.2 構(gòu)建獨(dú)立生成樹(shù)

利用圖論中圖的連通度、獨(dú)立生成樹(shù)的相關(guān)理論，研究構(gòu)建的圖Gl（V，E）的連通度n，這里n=4，獨(dú)立生成樹(shù)遞歸構(gòu)造算法（uasual Independent Span-ning Tree）如下：

輸入維度，的頂點(diǎn)集合（）.

輸出一個(gè)圖.

步驟1：if，then return=path<0，1，12，13>and=path<0，13，12，1>

else call，.

步驟2：將樹(shù)復(fù)制成樹(shù)：將的根節(jié)點(diǎn)進(jìn)行轉(zhuǎn)換；

步驟3：構(gòu)造、、…、、

for t（）do

對(duì)，；

對(duì)，，

end for

結(jié)束

通過(guò)獨(dú)立生成樹(shù)遞歸構(gòu)造算法，構(gòu)建4棵獨(dú)立生成樹(shù)IST，，， ，，其中如圖2所示：

2.3 構(gòu)建基于IST的多路徑傳輸機(jī)制

2.3.1 基于IST的多路徑傳輸

任意兩節(jié)點(diǎn)之間傳輸路徑研究。以互連圖Gl中任意2個(gè)節(jié)點(diǎn)間的數(shù)據(jù)傳輸為例，這里選擇節(jié)點(diǎn)0和節(jié)點(diǎn)2，通過(guò)獨(dú)立生成樹(shù)進(jìn)行數(shù)據(jù)包的傳送，網(wǎng)絡(luò)中有4棵獨(dú)立生成樹(shù)，那么數(shù)據(jù)包從節(jié)點(diǎn)n₀到節(jié)點(diǎn)n₂就可以通過(guò)4棵獨(dú)立生成樹(shù)進(jìn)行傳遞，如圖3所示，數(shù)據(jù)包沿著四條不相交的路徑從n₀節(jié)點(diǎn)傳送到n₂節(jié)點(diǎn)，與傳統(tǒng)網(wǎng)絡(luò)傳輸數(shù)據(jù)包相比，每個(gè)節(jié)點(diǎn)的數(shù)據(jù)包接受為原來(lái)的4倍，可有效解決丟包、數(shù)據(jù)失真問(wèn)題。

2.3.2 基于IST的多路徑傳輸速度比較

n棵獨(dú)立生成樹(shù)產(chǎn)生n條不相交的路徑。假設(shè)網(wǎng)絡(luò)中傳輸?shù)拿總€(gè)數(shù)據(jù)包d，利用n條頂點(diǎn)不相交的獨(dú)立生成樹(shù)來(lái)進(jìn)行分組傳輸，進(jìn)而提高信息傳輸速度，如上圖3所示。從單個(gè)數(shù)據(jù)包分包傳送角度考量，每個(gè)數(shù)據(jù)包d可以通過(guò)4個(gè)IST上進(jìn)行數(shù)據(jù)包的傳送，每棵樹(shù)上只需傳送1/4個(gè)數(shù)據(jù)包s，就可實(shí)現(xiàn)從節(jié)點(diǎn)n₀到節(jié)點(diǎn)n₂的數(shù)據(jù)包的傳送，如圖4（a）所示。傳統(tǒng)傳送如圖4（b）所示。理想狀態(tài)下，在傳送數(shù)據(jù)包s相同的情況下，IST上傳輸?shù)臅r(shí)間為t，普通傳輸?shù)臅r(shí)間則為4*t，那么獨(dú)立生成樹(shù)上傳輸?shù)乃俣缺仍谄胀ňW(wǎng)絡(luò)中傳輸?shù)乃俣忍岣?倍。

3 結(jié)論

本文將高性能并行計(jì)算中的獨(dú)立生成樹(shù)理論運(yùn)用到企業(yè)網(wǎng)絡(luò)傳輸中，使用IOT可遞歸構(gòu)造算法生成獨(dú)立生成樹(shù)，利用獨(dú)立生成樹(shù)的不相交理論，實(shí)現(xiàn)網(wǎng)絡(luò)中任意兩節(jié)點(diǎn)圍繞獨(dú)立生成樹(shù)進(jìn)行多路徑傳輸，同時(shí)分析了基于IST的數(shù)據(jù)傳輸與傳統(tǒng)傳輸在傳輸速度、時(shí)間方面的差異，顯示基于獨(dú)立生成樹(shù)的多路徑傳輸在傳輸速度、傳輸時(shí)間上的優(yōu)勢(shì)，為企業(yè)網(wǎng)絡(luò)環(huán)境下的數(shù)據(jù)傳輸提供一種多路徑傳輸?shù)姆椒ā?