李新磊

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

關(guān)鍵詞： 網(wǎng)絡(luò)多播路由； 編碼軟件； 網(wǎng)絡(luò)吞吐量； 軟件設(shè)計(jì)

中圖分類號(hào)： TN915?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

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

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

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

1 網(wǎng)絡(luò)多播路由的改進(jìn)編碼軟件設(shè)計(jì)與實(shí)現(xiàn)

1.1 網(wǎng)絡(luò)多播路由總體設(shè)計(jì)分析

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

圖1 網(wǎng)絡(luò)多播路由器總體結(jié)構(gòu)

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

數(shù)據(jù)包編碼轉(zhuǎn)發(fā)模塊主要負(fù)責(zé)在多播拓?fù)涞亩鄺l不相交路徑上編碼和轉(zhuǎn)發(fā)多播數(shù)據(jù)包，增強(qiáng)網(wǎng)絡(luò)吞吐率。在發(fā)送多播數(shù)據(jù)包的過(guò)程中，路由器依據(jù)多播路由表對(duì)數(shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā)，同時(shí)在多播路由器上構(gòu)建數(shù)據(jù)包編碼算法，實(shí)現(xiàn)編碼操作。

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

開(kāi)關(guān)仲裁模塊依據(jù)從每個(gè)輸入端口接收到的仲裁請(qǐng)求信號(hào)判斷能向特定輸出端口傳輸信息。

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

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

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

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

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

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

在式（1）的基礎(chǔ)上，信源處[ω×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)絡(luò)[NGV，E，s，T，ω]，則其系統(tǒng)轉(zhuǎn)移矩陣可描述成：

[M=AI-FBT] （4）

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

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

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

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

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

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

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

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

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

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

2 代碼設(shè)計(jì)

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

define DLY 1

timescale 1ns/1ns

module payload_router

#（parameter DATAWIDTH = 64

parameter CTRLWIDTH = DATAWIDTH

//對(duì)參數(shù)進(jìn)行初始化處理

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

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

output reg

rand_num_en，

//啟動(dòng)隨機(jī)數(shù)發(fā)生器

input rand_num_val

//復(fù)位

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；

//明確信號(hào)，得到所需元素

if （！empty_packingfifo） begin

router_status <= JUDGE；

end

else begin

//輸出結(jié)果

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 實(shí)驗(yàn)結(jié)果與分析

為了證明本文方法的有效性，需要進(jìn)行相關(guān)的實(shí)驗(yàn)加以驗(yàn)證。實(shí)驗(yàn)將HO編碼方法作為對(duì)比進(jìn)行分析。

3.1 兩種方法時(shí)延的比對(duì)

分別將本文方法和HO方法應(yīng)用于多播路由中，對(duì)兩種方法下多播路由時(shí)延進(jìn)行比對(duì)結(jié)果如圖2所示。

由圖2可知，采用本文方法和HO方法的多播路由時(shí)延均隨網(wǎng)絡(luò)負(fù)載的增加而增加。但本文方法的多播路由時(shí)延增加較慢，這是因?yàn)楸疚姆椒ㄊ苟鄠€(gè)數(shù)據(jù)分組同時(shí)被傳輸，降低了時(shí)延。

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

在本文方法和HO方法下，對(duì)多播路由網(wǎng)絡(luò)吞吐量進(jìn)行比對(duì)，結(jié)果如圖3所示。由圖3可知，采用本文方法的網(wǎng)絡(luò)吞吐量明顯大于HO方法。因?yàn)楸疚姆椒軌蛞淮伟l(fā)送多個(gè)數(shù)據(jù)分組，增加了網(wǎng)絡(luò)的吞吐量。

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

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

4 結(jié) 論

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

參考文獻(xiàn)

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

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

[3] 史媛芳，李潤(rùn)豐.基于縱向優(yōu)先多播路由算法的片上網(wǎng)絡(luò)路由器設(shè)計(jì)[J].新鄉(xiāng)學(xué)院學(xué)報(bào)，2015（3）：28?32.

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

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

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

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

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