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

劉靜　樊建席

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

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

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

0 引言

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

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

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

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

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

1.2 獨(dú)立生成樹

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

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

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

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

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

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

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

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

輸出一個圖.

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

else call，.

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

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

for t（）do

對，；

對，，

end for

結(jié)束

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

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

2.3.1 基于IST的多路徑傳輸

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

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

n棵獨(dú)立生成樹產(chǎn)生n條不相交的路徑。假設(shè)網(wǎng)絡(luò)中傳輸?shù)拿總€數(shù)據(jù)包d，利用n條頂點(diǎn)不相交的獨(dú)立生成樹來進(jìn)行分組傳輸，進(jìn)而提高信息傳輸速度，如上圖3所示。從單個數(shù)據(jù)包分包傳送角度考量，每個數(shù)據(jù)包d可以通過4個IST上進(jìn)行數(shù)據(jù)包的傳送，每棵樹上只需傳送1/4個數(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間為t，普通傳輸?shù)臅r間則為4*t，那么獨(dú)立生成樹上傳輸?shù)乃俣缺仍谄胀ňW(wǎng)絡(luò)中傳輸?shù)乃俣忍岣?倍。

3 結(jié)論

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