网络多播路由的改进编码软件设计与实现

李新磊

摘 要： 传统网络多播路由编码方法采用多播分布树进行编码，但链路容量遭遇瓶颈，致使编码节点较多，导致浪费带宽资源的问题。在此提出基于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.