李新磊

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

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

中圖分類號： 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 引 言

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

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

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

1 網(wǎng)絡多播路由的改進編碼軟件設計與實現(xiàn)

1.1 網(wǎng)絡多播路由總體設計分析

網(wǎng)絡多播路由器為網(wǎng)絡的核心，完成網(wǎng)絡的主要協(xié)議和功能。和傳統(tǒng)單播路由相比，多播路由的結構更為復雜，包括數(shù)據(jù)包編碼轉(zhuǎn)發(fā)模塊、輸入模塊、開關仲裁模塊、死鎖控制模塊和輸出模塊，詳細結構如圖1所示。

圖1 網(wǎng)絡多播路由器總體結構

網(wǎng)絡多播路由器各模塊詳細功能如下：

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

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

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

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

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

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

1.2 基于Koetter指數(shù)時間的網(wǎng)絡多播路由改進編碼算法設計與實現(xiàn)

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

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

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

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

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

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

給出矩陣[A]，[B]和[F]的網(wǎng)絡[NGV，E，s，T，ω]，則其系統(tǒng)轉(zhuǎn)移矩陣可描述成：

[M=AI-FBT] （4）

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

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

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

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

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

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

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

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

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

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

2 代碼設計

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

define DLY 1

timescale 1ns/1ns

module payload_router

#（parameter DATAWIDTH = 64

parameter CTRLWIDTH = DATAWIDTH

//對參數(shù)進行初始化處理

//輸入有效載荷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

//通過數(shù)字生成器生成數(shù)據(jù)

output reg

rand_num_en，

//啟動隨機數(shù)發(fā)生器

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方法的多播路由時延均隨網(wǎng)絡負載的增加而增加。但本文方法的多播路由時延增加較慢，這是因為本文方法使多個數(shù)據(jù)分組同時被傳輸，降低了時延。

3.2 兩種方法下多播路由網(wǎng)絡吞吐量的比對

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

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

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

4 結 論

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

參考文獻

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

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

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

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

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

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

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

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