網絡多播路由的改進編碼軟件設計與實現

李新磊

摘 要： 傳統網絡多播路由編碼方法采用多播分布樹進行編碼，但鏈路容量遭遇瓶頸，致使編碼節點較多，導致浪費帶寬資源的問題。在此提出基于Koetter指數時間的網絡多播路由改進編碼算法對編碼軟件進行設計，分析多播路由的總體設計，通過數據包編碼轉發模塊在多播拓撲不相交路徑上進行編碼和轉發多播數據包，利用輸入模塊實現網絡多播路由和上游節點的信息交換，通過開關仲裁模塊判斷能夠向特定輸出端口傳輸信息的輸入端口，利用死鎖控制模塊對出現死鎖現象的路由節點進行檢測，一段時間后使多播路由恢復正常的數據交換，通過輸出模塊對數據的輸出進行管理。以降低帶寬資源為目的，采用Koetter指數時間算法實現網絡多播路由編碼，并給出編碼的詳細代碼。實驗結果表明，所提方法不僅節省網絡資源，而且顯著降低多播路由時延，增強網絡吞吐量。

關鍵詞： 網絡多播路由； 編碼軟件； 網絡吞吐量； 軟件設計

中圖分類號： TN915?34 文獻標識碼： A 文章編號： 1004?373X（2016）08?0051?04

Design and implementation of coding software to improve network multicast routing

LI Xinlei

（Henan Normal University， Xinxiang 453007， China）

Abstract： The traditional network multicast routing coding method uses multicast distribution tree to code， but it is easy for the link capacity to meet with bottleneck， which may result in more coding nodes and bandwidth resource waste. The improved coding algorithm of network multicast routing based on Koetter index time used to design the encoding software is proposed. The overall design of the multicast routing is analyzed， in which the data package coding transmitting module is used to code and transmit the multicast data package on the multicast topological disjoint paths， the input module is used to implement the information interchange between network multicast routing and upstream node， the switch arbitration module is used to judge the input port which can transport the information to the specific output port， and the deadlock control module is used to detect the routing nodes with deadlock phenomenon. After a period of time， the multicast routing can return to normal data exchange， and the data output is managed through the output module. In order to reduce the bandwidth resource waste， the Koetter index time algorithm is adopted to realize the network multicast routing coding. The detailed code of the coding is given. The experimental results show that the proposed method can save the network resources， greatly reduce the multicast routing delay， and increase the network throughput.

Keywords： network multicast routing； coding software； network throughput； software design

0 引 言

隨著計算機通信的發展，人們的生活方式逐漸趨于信息化，多播通信成為網絡的一項基礎通信服務，可大大減少網絡帶寬的使用，廣泛應用于很多領域[1?2]。網絡編碼和網絡多播技術的結合能夠有效提高網絡多播路由的性能，因此，對網絡多播路由的改進編碼軟件的研究具有重要意義，已經成為相關學者研究的重點課題[3?5]。

目前，有關網絡多播路由編碼軟件的研究有很多，其中，徐斌將網絡多播路由的費用問題引入編碼分組中，通過繪制最小費用子圖給出最小費用編碼算法，將傳統網絡編碼問題轉換成線性規劃問題進行解決，但該方法實現過程復雜，不適用于實際應用；沈小建提出一種基于約簡化網絡的最短路徑族編碼算法，在一個約簡化的網絡中查找最短路徑，從而獲取編碼方案，該方法計算復雜度較低，但對路徑長度均衡的網絡編碼時，其編碼路徑的組合狀態較為隨機，導致資源消耗高[6]；婁輝提出一種基于鏈路共享度的網絡多播路由編碼算法，通過鏈路共享度的大小可獲取編碼路徑最高的共享鏈路集，實現網絡編碼，但該方法不能保證每條路徑的長度盡可能短，浪費資源[7]；韓莉提出一種基于隨機線性的網絡多播路由編碼算法，該算法依據隨機線性規則對路由進行編碼，但無法適應隨機改變的拓撲環境[8]；徐斌提出一種基于代數學框架的網絡多播路由編碼算法，該算法通過代數研究使用線性編碼的網絡容量問題，依據容量大小完成編碼，但該方法運行時間長、效率低下。

針對上述方法的缺陷，提出一種基于Koetter指數時間的網絡多播路由改進編碼算法對編碼軟件進行設計，分析了多播路由的總體設計。以降低帶寬資源為目的，采用Koetter指數時間算法實現網絡多播路由編碼，給出了編碼的詳細代碼。實驗結果表明，所提方法不僅節省網絡資源，且顯著降低多播路由時延，增強網絡吞吐量。

1 網絡多播路由的改進編碼軟件設計與實現

1.1 網絡多播路由總體設計分析

網絡多播路由器為網絡的核心，完成網絡的主要協議和功能。和傳統單播路由相比，多播路由的結構更為復雜，包括數據包編碼轉發模塊、輸入模塊、開關仲裁模塊、死鎖控制模塊和輸出模塊，詳細結構如圖1所示。

圖1 網絡多播路由器總體結構

網絡多播路由器各模塊詳細功能如下：

數據包編碼轉發模塊主要負責在多播拓撲的多條不相交路徑上編碼和轉發多播數據包，增強網絡吞吐率。在發送多播數據包的過程中，路由器依據多播路由表對數據包進行轉發，同時在多播路由器上構建數據包編碼算法，實現編碼操作。

輸入模塊主要用于實現網絡多播路由和上游節點的信息交換，為了從上游節點接收到的數據提供存儲空間，依據開關仲裁模塊的命令輸出數據至交叉開關。

開關仲裁模塊依據從每個輸入端口接收到的仲裁請求信號判斷能向特定輸出端口傳輸信息。

死鎖控制模塊主要具有以下三個功能：當本地路由節點出現死鎖現象時，通過死鎖控制模塊對其進行檢測；完成檢測后，將出現死鎖現象的輸入端口虛信道中的數據儲存于死鎖控制器中緩存空間中，一段時間后，正常發送數據；正常發送數據一段時間后使多播路由恢復正常的數據交換。

輸出模塊依據下游節點流對數據的輸出進行管理，并且將所輸出微片分配到合理的下一節點，同時對數據信息進行更新。

網絡多播路由總體設計分析為基于Koetter指數時間的網絡多播路由改進編碼算法提供依據。

1.2 基于Koetter指數時間的網絡多播路由改進編碼算法設計與實現

傳統網絡多播路由編碼方法采用多播分布樹進行編碼，鏈路容量遭遇瓶頸，編碼節點較多，導致浪費帶寬資源的問題。因此，采用基于Koetter指數時間的網絡多播路由改進編碼算法對編碼軟件進行設計，其基本思想如下：將網絡多播路由看作是一個系統，將傳輸數據看作是輸入和輸出，將網絡多播路由中各節點的局部編碼核看作是參數，則輸入與輸出之間的關系可通過一個矩陣進行描述。所以，編碼問題就轉換為從中間節點尋找合適的編碼系數問題。在網絡[NGV，E，s，T，ω]中，用[x=x1，x2，…，xω]描述信源節點要發出的消息向量，用[ye]描述信道[e]上發送的符號。則網絡中任意信道[e]發送的符號[ye]均為原始信息向量[x=x1，x2，…，xω]的函數。針對多播路由，需對網絡進行下述分析：在進行編碼的過程中，假設和原網絡圖[GV，E]相應的線圖[??，?]上的鄰接矩陣[F]為：

[Fi，j=ke，e， headei=tailej0， otherwise] （1）

在式（1）的基礎上，信源處[ω×E]轉移矩陣[A]可描述成：

[A=kei，ej， headei=tailej0， otherwise] （2）

式中，[ei]用于描述虛擬信道。由式（2）可描述輸出向量的[T×E]轉移矩陣[B]：

[Bi，j=kej，i， zi=yej0， otherwise] （3）

給出矩陣[A]，[B]和[F]的網絡[NGV，E，s，T，ω]，則其系統轉移矩陣可描述成：

[M=AI-FBT] （4）

式中，[I]用于描述[E×E]的單位矩陣。

在多播路由中，可將信源和各信宿節點[ti∈T]的通信當成單播通信，相應的存在一個轉移矩陣，用[Mi]進行描述。則[T]個信宿節點分別和[T]個轉移矩陣對應，即[MiTi=1]。如果所有信宿節點均可準確譯碼，則上述轉移矩陣必須全為非奇異。設[F]為全部[T]轉移矩陣的行列式的乘積，[δ]用于描述[F]中變量[kei，ej] （局部編碼核）的最高次數。則存在一個元素取值于[F2i] （[2i>δ]）的網絡編碼，使得[NGV，E，s，T，h]的信息傳輸能夠滿足網絡的多播容量。

建立網絡多播路由編碼的關鍵就是獲取合適的局部編碼核[kei，ej，headei=tailej]。建立過程如下：

（1） 輸入：一個關于參數[ξ1，ξ2，…，ξn]的多項式[F]；初始化整數[?=1]，[i=1]；

（2） 通過步驟（1）得到多項式[F]中參數[ξ?]的最高次數[δ]，用[i]描述能夠滿足[2i>δ]的最小整數，獲得有限域[F2i]；

（3） 在有限域[F2i]中獲取能夠使[Fξξ?=a?≠0]的元素[a?]，同時假設

[F←Fξξ?=a?] （5）

（4） 若[?=n]，則結束迭代；否則，令[?=?+1]，重新進行步驟（2）。

輸出：[a1，a2，…，an]。

通過輸出模塊對數據的輸出進行管理實現了基于Koetter指數時間的網絡多播路由改進編碼算法設計。除此之外，通過該算法建立編碼所在域的[F2m]值主要與網絡多播路由[NGV，E，s，T，h]的信宿節點個數和信源速率有關，也就是[m≤log2Th]。

2 代碼設計

采用上述算法進行網絡多播路由編碼的部分代碼可描述如下：

define DLY 1

timescale 1ns/1ns

module payload_router

#（parameter DATAWIDTH = 64

parameter CTRLWIDTH = DATAWIDTH

//對參數進行初始化處理

//輸入有效載荷FIFO1端口

input [DATAWIDTH ? 1：0]

data_payloadfifo_router_1，

input [CTRLWIDTH ? 1：0]

ctrl_payloadfifo_router_1

input empty_payloadfifo_router_1

output reg

rd_en_payloadfifo_router_1

//輸入有效載荷FIFO2端口

input [DATAWIDTH ? 1：0]

data_payloadfifo_router_2

input [CTRLWIDTH ? 1：0]

ctrl_payloadfifo_router_2

input empty_payloadfifo_router_2

output reg

rd_en_payloadfifo_router_2

//通過數字生成器生成數據

output reg

rand_num_en，

//啟動隨機數發生器

input rand_num_val

//復位

if （rst_n == 0） begin

router_status <= JUDGE；

data_temp1 <= 64'h0；

ctrl_temp1 <= 8'h0；

data_temp2 <= 64'h0；

ctrl_temp2 <= 8'h0；

counter_getdata <= 2'b0；

end

else begin

case （router_status）

JUDGE： begin

first_dword_1 <= 0；

first_dword_2 <= 0；

rand_num_en <= 0；

val_router_multiplier_2 <= 0；

//明確信號，得到所需元素

if （！empty_packingfifo） begin

router_status <= JUDGE；

end

else begin

//輸出結果

if （empty_payloadfifo_router_1

&& empty_payloadfifo_router_2） begin

rd_en_payloadfifo_router_1 <= 0；

rd_en_payloadfifo_router_2 <= 0；

router_status <= JUDGE；

output a；

end

3 實驗結果與分析

為了證明本文方法的有效性，需要進行相關的實驗加以驗證。實驗將HO編碼方法作為對比進行分析。

3.1 兩種方法時延的比對

分別將本文方法和HO方法應用于多播路由中，對兩種方法下多播路由時延進行比對結果如圖2所示。

由圖2可知，采用本文方法和HO方法的多播路由時延均隨網絡負載的增加而增加。但本文方法的多播路由時延增加較慢，這是因為本文方法使多個數據分組同時被傳輸，降低了時延。

3.2 兩種方法下多播路由網絡吞吐量的比對

在本文方法和HO方法下，對多播路由網絡吞吐量進行比對，結果如圖3所示。由圖3可知，采用本文方法的網絡吞吐量明顯大于HO方法。因為本文方法能夠一次發送多個數據分組，增加了網絡的吞吐量。

3.3 兩種方法下多播路由網絡帶寬資源消耗總量比對

在本文方法和HO方法下，對多播路由網絡帶寬資源消耗總量進行比對如圖 4所示。由圖4可知，采用本文方法下的網絡帶寬資源消耗總量遠遠小于HO方法，并隨著網絡負載的逐漸增加，資源消耗總量的差異越來越大，以此說明本文方法的資源消耗量較少。

4 結 論

本文提出一種基于Koetter指數時間的網絡多播路由改進編碼算法對編碼軟件進行設計，分析了多播路由的總體設計，通過數據包編碼轉發模塊在多播拓撲多條不相交路徑上進行編碼和轉發多播數據包，利用輸入模塊實現網絡多播路由和上游節點的信息交換，通過開關仲裁模塊判斷能夠向特定輸出端口傳輸信息的輸入端口，利用死鎖控制模塊對出現死鎖現象的路由節點進行檢測，一段時間后使多播路由恢復正常的數據交換，通過輸出模塊對數據的輸出進行管理。以降低帶寬資源為目的，采用Koetter指數時間算法實現網絡多播路由編碼，給出了編碼的詳細代碼。實驗結果表明，所提方法不僅節省網絡資源，而且顯著降低多播路由時延，增強網絡吞吐量。

參考文獻

[1] 譚丹丹，譚晶晶.基于網絡編碼的多播車載網路由算法研究[J].時代報告（學術版），2013（1）：39.

[2] 尹吉星，任平安.一種改進負載均衡的網絡編碼多播路由算法[J].計算機工程與應用，2015（13）：81?85.

[3] 史媛芳，李潤豐.基于縱向優先多播路由算法的片上網絡路由器設計[J].新鄉學院學報，2015（3）：28?32.

[4] 蘇亞娟，束國偉.一種小型多播路由器的設計與實現[J].福建電腦，2013，29（7）：35?37.

[5] 尹吉星，任平安.基于網絡編碼的多播路由算法研究[J].計算機技術與發展，2014（5）：79?82.

[6] 沈小建，陳志剛，劉立.無線mesh網絡中編碼感知且負載均衡的多播路由[J].通信學報，2015，36（4）：89?95.

[7] 婁輝，肖燦文，董德尊，等.一種基于氣泡流控的改進多播路由算法[J].計算機工程與科學，2015，37（2）：191?198.

[8] 韓莉，錢煥延.基于網絡編碼的無線網絡多路徑機會路由算法[J].計算機科學，2014，41（5）：116?119.