基于獨立生成樹的網絡多路徑傳輸方法研究

劉靜　樊建席

摘要：將高性能并行計算中的獨立生成樹理論應用到企業網絡傳輸中，首先將企業網絡拓撲抽象為互連網絡提出一種獨立生成樹可遞歸構造算法，生成多棵獨立生成樹，進而給出一種基于獨立生成樹的網絡多路徑傳輸方式并在傳輸時間、傳輸速度上進行了網絡傳輸性能分析，指出其優勢。

關鍵詞：互連圖；獨立生成樹；多路徑傳輸

中圖分類號：TP391.3 文獻標識碼：A DOI：10.3969/j.issn.1003-6970.2016.04.007

0 引言

隨著兩化融合的深入，信息化與工業化的融合程度越來越高，信息化帶動工業化的發展。隨著互聯網絡的普及，工業信息網絡逐漸覆蓋了各個領域。近年來國防、電網、城市軌交、天氣預報等領域均出現龐大計算量的應用問題，這些問題對互連網絡中的各節點性能提出了更高要求。

而現實生活中的計算機網絡、移動互聯網絡及通訊網絡等，常常會由于鏈路或節點故障而影響網絡功能降低甚至失效。目前常用的樹型結構和多路徑結構都是平面結構，以獨立生成樹為基礎的網絡性能研究是高性能并行計算研究的熱點，這一研究通常應用在立方體、超立方體、扭立方體等方面，以處理復雜計算問題，在高性能并行計算方面表現良好。多路徑傳輸在網絡性能優化方面被廣泛使用。此本文提出一種基于獨立生成樹的工業企業網絡多路徑傳輸機制。

1 互連網絡與獨立生成樹

1.1 互連網絡

并行計算機的內部處理器或處理機，按照一定方式連接起來，形成的網絡稱為多處理器互連網絡，即互連網。互連網絡成為研究并行計算的核心，對互連網絡拓撲結構及其性質研究是并行計算機系統的一個重要課題。常用的互連網絡，如樹、圈、網格等結構的構造是國內外網絡研究的焦點。國內外研究者提出了多種不同的互連網絡結構，如超立方體、樹型網絡、奇圖、偶圖、蝶形圖等。無論哪種網絡結構，其網絡拓撲都可以用圖來描述，在互連網研究中，網絡一般定義為一個圖，其中V為頂點集，E為邊集，I。

1.2 獨立生成樹

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

國內以FAN為代表的并行與分布式系統研究者針對超立方體等一類互連網絡，通過構建獨立生成樹（Independent Spanning Tree，簡稱IST）進行理論研究，認為超立方體及其變型具有兩個共性（一一對應連接和可遞歸構造性質），提出一一對應連接網絡（Biiective Connection Network，簡稱BC網絡）的概念，并在此基礎上系統化地論證了BC網絡中獨立生成樹的存在，給出獨立生成樹的可遞歸構造算法。

2 基于獨立生成樹的網絡多路徑傳輸機制

2.1 網絡拓撲構建

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

2.2 構建獨立生成樹

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

輸入維度，的頂點集合（）.

輸出一個圖.

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

else call，.

步驟2：將樹復制成樹：將的根節點進行轉換；

步驟3：構造、、…、、

for t（）do

對，；

對，，

end for

結束

通過獨立生成樹遞歸構造算法，構建4棵獨立生成樹IST，，， ，，其中如圖2所示：

2.3 構建基于IST的多路徑傳輸機制

2.3.1 基于IST的多路徑傳輸

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

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

n棵獨立生成樹產生n條不相交的路徑。假設網絡中傳輸的每個數據包d，利用n條頂點不相交的獨立生成樹來進行分組傳輸，進而提高信息傳輸速度，如上圖3所示。從單個數據包分包傳送角度考量，每個數據包d可以通過4個IST上進行數據包的傳送，每棵樹上只需傳送1/4個數據包s，就可實現從節點n₀到節點n₂的數據包的傳送，如圖4（a）所示。傳統傳送如圖4（b）所示。理想狀態下，在傳送數據包s相同的情況下，IST上傳輸的時間為t，普通傳輸的時間則為4*t，那么獨立生成樹上傳輸的速度比在普通網絡中傳輸的速度提高4倍。

3 結論

本文將高性能并行計算中的獨立生成樹理論運用到企業網絡傳輸中，使用IOT可遞歸構造算法生成獨立生成樹，利用獨立生成樹的不相交理論，實現網絡中任意兩節點圍繞獨立生成樹進行多路徑傳輸，同時分析了基于IST的數據傳輸與傳統傳輸在傳輸速度、時間方面的差異，顯示基于獨立生成樹的多路徑傳輸在傳輸速度、傳輸時間上的優勢，為企業網絡環境下的數據傳輸提供一種多路徑傳輸的方法。