基于网络编码的多信源组播通信系统，包括源代码，原理图等(二)

　　2 多信源组播系统结构及整体设计方案

　　2.1项目研究需求、目标和内容

　　网络编码能够提高网络吞吐量，提升鲁棒性、安全性等网络性能。具有网络编码功能的路由器是未来网络发展的趋势。组播通信在网络通信中有重要的作用，事实上，任何一个网络都可以认为是组播网的一个特例。然而，目前在世界上研究网络编码在组播上的应用大多集中在单信源组播方面，例如，单信源多信宿网络如何达到最大传输速率问题[25]，基于网络编码的组播路由算法和性能评估[26], 基于网络编码的组播通信网络的拓扑设计[27], 多信源随机线性网络编码在组播通信的研究[28]以及单信源组播网中编码节点的研究[29]，以上研究都是以软件仿真为主，没有形成实际的硬件平台和系统。

　　多信源组播的应用非常广泛，如P2P内容分发网络等。事实上，任何一个网络都可以作为多信源组播的一个特例，因此研究多信源组播是有意义且必要的。

　　本项目的主要研究目标是基于网络编码的多信源组播系统的实现。在基于国内外网络编码理论在组播通信中的最新研究成果和技术，对网络编码理论进行深入学习和探讨，提出一种基于网络编码的多信源组播系统和网络，然后依据此系统设计出可实现组播的通信协议和相关算法，再利用开放式的网络设计硬件平台NetFPGA[30]，使提出的协议和算法在硬件上实现，最后在实际的环境中用若干电脑和NetFPGA组成一个小型组播通信网络进行系统测试和性能评估。

　　2.2 NetFPGA——新一代开放式网络研究平台简介

　　由斯坦福大学开发的NetFPGA是一个基于Linux操作系统的可重用开放性硬件平台，允许用户在实验室内搭建高性能的网络模型进行仿真和研究。它具有以下特点[31]：

　　(1)很好地支持模块化设计，它可以使研究人员在硬件上搭建Gb/s高性能网络系统模型。(2)NetFPGA是一个基于Linux系统的开放性平台，可以利用平台上现有的资源，在前人开发的基础上添加自己的模块和修改现有的系统，而不需要重复地搭建外围模块、开发驱动和GUI等，大大减轻了网络研究的任务。

　　NetFPGA的硬件主要包含了4个1Gb/s的以太网接口(GigE)，一个用户可编程的FPGA，以及两片SRAM和一片DRAM。NetFPGA开发板通过标准的PCI总线接口连接到PC机或服务器，模块框图如图2.2-1所示。

　　

 

　　图 2.2-1：NetFPGA平台的组成框图

　　在外部硬件接口方面，除了连接PC主机的PCI总线插口，一个Broadcom公司的物理层收发器(PHY)包含了四个千兆位以太网接口，板子上的两个SATA连接口使得系统内部的多个NetFPGA可以通过SATA数据线连接起来，互相之间直接以很高的速度交换数据，而不必再通过PCI总线。NetFPGA通过PCI总线与主机CPU连接，提供了硬件加速的数据通道，分担CPU的处理任务。主机CPU按照DMA方式读写NetFPGA上的寄存器和存储器来配置NetFPGA的工作模式，并对NetFPGA的工作状态进行监控。

　　NetFPGA平台的软件系统包括操作系统、作为软件接口的驱动程序、实现各种硬件功能的逻辑代码、执行控制功能的软件程序、系统测试的脚本程序，以及计算机辅助设计软件工具。

　　2.3 利用NetFPGA实现本设计的总体构想

　　基于网络编码的组播通信系统将充分运用NetFPGA上面的各种硬件和软件资源，实现系统的设计目标，具体是：(1)根据项目的需求，合理且充分利用NetFPGA卡上面的各种硬件资源，如FPGA、存储芯片和输入输出接口;(2)由于基于NetFPGA实现的IPv4原理性路由器是一个开源的系统，因此我们可以运用其提供的部分代码和已经设计好的底层硬件平台，来帮助我们实现设计目标。例如，我们的系统的编码、解码工作主要在网络层完成，因此我们可以利用NetFPGA中已有的物理层、MAC层硬件逻辑来实现数据的接收和发送;(3)在软件方面，由于NetFPGA平台选择了CentOS操作系统，并且开发了软硬件接口的驱动程序，基于Linux内核的设备驱动程序和Java程序开发的图形用户界面(Java GUI)等，因此我们可以对其应用、改进，使我们的系统更加完善，方便调试和后续的进一步研究。

　　2.4系统实现的整体设计方案说明

　　2.4.1 系统拓扑图及说明

　　如图2.4-1所示，是拟采用的组播通信网络的拓扑图：

　　

 

　　图2.4-1基于网络编码组播的网络拓扑图

　　说明：为了易于在工程上实现，将网络编码路由器分为编码路由器EC(Encoding router)和解码路由器DC(Decoding router)，分别专门负责编码和解码。具体讲，如图1所示，信源S1,S2,S3发送数据包，编码路由器EC0和EC1负责将接收到的数据包以随机的系数进行线性编码后发送给组播路由器R，注意，这里的组播路由器更准确地说是转发路由器，因为它的功能只是将收到的数据包转发到其三个输出端口，而没有IGMP(组播管理)和相应的组播路由功能。当然，我们也可以直接在EC上实现转发的功能，增加R的原因是考虑到NetFPGA端口数量的限制(每块NetFPGA只有4个端口)。解码路由器DC接收编码的数据并解码，并将它发送给下游的信宿主机，在这里，由于PC数量的限制，我们使用双口网卡可以将解码路由器和信宿放到同一台主机上，这对网络性能的测试和实现没有任何影响。

　　2.4.2编码策略与方案

　　作为一种编码结构的提出，我们将编码只限于不同信源数据包之间，暂不考虑信源包内部编码。相同信源的数据包之间分“代”，以便在解码时区分信息先后顺序[32]。不同信源的包之间不区分代的概念。

　　定义：为了讨论的方便性和简洁性，我们将信源S1的第1代记为S(1,1)，信源S2的第3代记为S(2,3),……依此类推。依据包头和缓存，每个信源的代的编号从0开始，至1023结束，即信源n的最大的代编号为S(n,1023)

　　在编码路由器EC上对不同信源的IP数据包进行编码，编码系数矢量随机选择，编码方法是线性编码。例如，在上图中的编码路由器EC0，设两个链路的输入的全局编码向量为：in(e)= 由于只有两个信源之间的编码有且只有一条边输出，则本地编码向量为(α β)，依据文章[33]的公式：

　　

 

　　则输出out(e)=(α β) =αS(1,x)+βS(2,y)。编码后的数据以NCP(network coding protocol)包头封装，然后再封装在IP数据报中，如图2.4-2所示：

 

　　

 

　　图2.4-2：编码后数据的封装格式

　　为减小相应的编码负担和提高编码效率，我们只对网络中的IP数据报中的有效载荷进行编码(已经编码过的数据包可以再进行编码)，不对ARP等其他数据包编码。在编码路由器中，我们为不同的输入通道开辟不同的FIFO以进行顺序存取和编码

　　2.4.3随机系数的选择

　　根据相关资料可知，随即编码系数矢量的选择可以从Galois Field中进行选择，依据论文[33][34]，我们选择域为GF256，即 ，此时可以解码的概率为1- =0.996，这个概率可以满足大多数的应用需求。

 

　　2.4.4 NCP数据包头的格式

　　为了能够在解码路由器上进行解码，我们需要在被编码的有效载荷前增加NCP数据包头[35]，根据我们的方案，其包头格式如图2.4-4：

版本 4位

首部长度 4位

总长度 16位）

标志 2位

保留 6位

第1个包信源号

第2个包信源号

……

……

第8个包信源号

第1个包的填充长度（10位）

编码系数矢量1 （8位）

代的编号（10位）

编码次数 （4位）

第2个包的填充长度

编码系数矢量2

代的编号

编码次数

………………

……

……

第n个包的填充长度

编码系数n

代的编号

编码次数

编码后的有效载荷

 

 

 

 

 

 

 

 

 

 

 

图2.4-4：NCP数据包的包头格式

　　先将包头各个字段的含义说明如下：

　　①版本：NCP数据包格式的版本，为了后续开发研究和以前版本的区分，第一个版本为0001.

　　②首部长度和总长度：首部长度是指除了有效数据载荷以外的部分，共4位，单位是4字节，其最小值为2。当首部长度为3时，意味着该包的载荷没有被编码，只是加了包头。当其值大于3时，其值减去3为被编码的信源数。

　　总长度是之首部长度和有效载荷之和的长度，16位，单位为字节。

　　③标志：若进入编码路由器的只是一个没有编码过的IP数据包时，不进行编码，直接将包头前2行加在原IP数据包的有效载荷的前面即可。当仅有一个NCP数据包进入编码路由器时，我们不进行编码，直接进行转发，如图2.4-5所示：

有效载荷的数据包类型	标志位
没有编码的IP数据包	01
编码后的NCP数据包	10
保留	00
保留	11

                           图2.4-5：标志位的含义

　　④编码次数：即从原始数据包算起，被编码的次数，因为在一个实际的网络中，数据的编码可以是递归的，即可以多次被编码。有时，只有一个数据源时，直接在其前面加上NCP包头而不进行编码。增加编码次数是为了能够在多次编码后进行解码。若编码前数据包为IP数据包，其编码次数为0，若为NCP数据包，则次数≥1.当一个IP数据包和一个已编码的数据包编码时，利用编码次数，可以避免解码路由器将NCP数据包误以为IP数据包而交给主机。

　　⑤第一个包的填充长度：因为不同数据源的数据包的长度可能不一样，为了便于编码计算，将它们前位补0使得长度一致。由于一个典型的以太网数据包的长度在500~1500字节之间，所以填充长度不超过1000字节。另外，我们还要考虑MAC层的最大传送单元(MTU)的限制，即编码后的MAC帧的长度不能超过1518字节。由此可以计算出，被编码的数据包的最大长度是1499字节

　　⑥编码系数：即随机选择的编码矢量的系数，是在一个GF256的有限域中随机选择。

　　⑦代的编号：即被编码的数据包的代的编号，是按照顺序产生的编号，目的是方便解码。

　　⑧包的信源号：4位，对进入编码路由器的数据包的信源进行编号，其目的是为了方便解码，在我们目前的体系中，最多允许8个数据包同时被编码。注意：当信源数少于8个时，例如有3个，则分别将对应的数据包的信源号分别填为0000，0001，0010，其余的都填写为1111。

　　2.4.5 转发(组播)路由器R工作流程

　　在实际的应用中，R应该是具有组播功能的路由器，即可以运行网际组播管理协议IGMP和多播路由选择协议DVMRP等，从而它可以知道网络的局部的拓扑和满足组播成员的要求。为了初期容易实现，我们将其功能简化为转发功能(即广播功能)。

　　2.4.6数据包的解码

　　(1) 高速缓存和CAM的使用

　　数据包的解码由DC解码路由器完成。每个解码路由器DC有三个输入通道，分别连接到R0，R1，R2其解码的策略是：我们先在DC中开辟三块不同的高速缓存(DRAM)和与之分别对应的3个CAM，它们分别对应于R0、R1、R2，缓存和CAM的大小为代的编号的大小，即 =1024，在这三个缓存中存放按照顺序接收到的数据。根据前面的数据处理过程，显然，对应于每个缓存中的数据，虽然有的是真正编码后的数据包，有的只是在IP数据包前增加了一个包头，但我们都可以认为是NCP数据包。在将数据存入高速缓存的同时，提取NCP数据包头中的信源号和代的编号，将它们存入到内容可寻址存储器CAM(content addressable memory),则CAM的输出即为对应数据在高速缓存的地址。

 

　　使用CAM的原因是：由于经过编码，以及网络环境非理想，解码路由器收到的encoded packet可能是乱序的。因此考虑使用CAM做检索链接，以便快速寻址当前解码所需要的packet。[!--empirenews.page--]

　　(2) 解码顺序

　　根据实际情况的考虑，目前有两种解码的顺序，一种情况是按照信源号和代的编号的顺序进行解码，第二种情况是按照缓存及其缓存地址的顺序来解码。

　　在已知网络拓扑的情况下，我们按照信源号和代的编号的顺序来进行解码，即对于信源采用轮询策略，对于内部代的编号采用小数优先策略。例如，在我们的拓扑图中，解码顺序是：S(1,1)，S(2,1)，S(3,1)→S(1,2)，S(2,2)，S(3,2)→……S(1,n),S(2,n),S(3,n)……。

　　在未知网络拓扑的情况下，我们按照高速缓存的地址顺序来进行解码，即先对高速缓存采用轮询策略，对每个缓存中，采用地址由小到大的顺序进行解码，如图2.4-7所示，进行解码的顺序是PZ1

　　→PX1→ PY1→ PZ2→ PX2→PY2→PZ3……

高速缓存1                高速缓存2              高速缓存3

地址   数据包           地址    数据包         地址    数据

01     PZ1              01      PX1             01      PY1

02     PZ2              02      PX2             02      PY2

03     PZ3              03      PX3             03      PY3

04     ……             04     ……            04       ……

……

图2.4-7 按照高速缓存的地址顺序来进行解码

　　上面的两种解码方式各有优点:在一般情况下，按照信源号和代的编号的顺序来进行解码可获得较高的解码速率，但在网络环境恶化的情况下，其丢包率(无法解码的概率)会比第2中方案高一些。由于在我们已有的网络环境一般较好，为了体现网络编码的传输的高效性，我们按照第1种顺序进行解码。

　　(3) 解码流程

　　为了避免高速缓存的写数据溢出，我们将设置二级缓存，二级缓存也有3个，可用SRAM构造，将SRAM分为3块地址上独立的区域，每个SRAM 大小为256×1800bytes，分别对应不同的信源，我们将解码后的数据，根据其代的编号，分别暂存在对应SRAM的对应地址上。例如，将S(1,1)存储在SRAM1的第1个地址空间，S(2,4)则存储在SRAM2的第4个地址空间。每个RAM各有1个读、写指针，可以同时按顺序读写数据，按照地址由小到大的顺序读出的数据被发送到输出队列中。

　　如图2.4-8所示为数据包的解码过程，每个告诉缓存各有1个读、写指针，在解码过程中，读取缓存是按照解码的顺序进行的，而在写缓存是按地址顺序写的。

　　

 

　　图2.4-8：数据包解码流程

　　(4) 解码策略与方法

　　我们按照信源号和代的编号的顺序来进行解码，即对于信源采用轮询策略，对于内部代的编号采用小数优先策略。例如，在我们的拓扑图中，解码顺序是：S(1,1)，S(2,1)，S(3,1)→S(1,2)，S(2,2)，S(3,2)→……S(1,n), S(2,n), S(3,n)……

　　假定我们按照上述顺序准备解码S(1,x)，解码程序如图9:

　　

 

　　图2.4-9 数据包S(1,x)的解码过程

　　无法求解一个数据包的原因可能是：该数据包由于延迟或者丢失，在CAM中搜寻不到，再有就是线性相关，无法解出来。在我们的系统中，由于其拓扑的特殊性，没有线性相关的情况，因此无法解码的情况只发生在解码因子丢失的情况下。

　　解码子任务：解码子任务的输入是包头信息，由调用它的程序给出，输出有两个变量：解码后的数据包和解码标志，解码标志告诉调用它的程序是否可以解码，我们假定现在要对S(i,j)解码，子任务流程如图2.4-10：

　　

 

　　图2.4-10：解码子任务流程[!--empirenews.page--]

　　(5) 解码后数据包暂存SRAM的读写策略

　　我们将解码后的数据包暂存在SRAM中等待发送，每个信源对应一个SRAM区域，同一个信源的解码后的人数据包存储在同一个RAM中，存储地址为该包的代的编号。每个RAM各有一个读指针，写数据按照RAM的地址大小顺序写入。读数据时按照信源编号和代的大小读取。由于发送速率一般会高于解码速率，因此RAM不用很大，暂定为256×1800。

　　每读取一个数据后，指针加1，若读取某个SRAM时无数据(可能是延迟或丢失造成)，则不用等待，直接进行下一个SRAM的读取，3次轮询之后还没有到达，则强行加读指针加1，读取下一个数据包。如图2.4-11所示为SRAM的读写操作。

　　

 

　　图2.4-11 二级缓存SRAM的读写操作

　　(6)举例说明

　　为了更清楚地显示整个解码的操作过程，我们以DC3为例，图2.4-12显示的是DC3的3个高速缓存和CAM，解码过程如下

　　

 

　　

 

　　图2.4-12 数据包S(1,x)解码过程

　　数据包S(1,x)解码过程如下：

　　先将S(1,x)的包头3个CAM中搜索，在CAM1中得到索引为00，我们利用该索引得到S(1,x)在高速缓存1的地址为00，从高速缓存1读取数据，得到a S(1,x)+b S(2,y)，为了求解S(1,x)我们调用解码子任务先求解S(2,y)，为了防止出现死循环，解码子任务只在CAM2和CAM3中搜寻S(2,y)，在CAM2中得到地址为02，于是读取高速缓存2的02地址数据，得到eS(2,y)+f S(3,z)，于是再调用子任务求解S(3,z)，在CAM3中搜索S(3,z)后解出S(3,z)， 于是可以解出S(2,y)，最后再解出S(1,x)，同时，分别将S(3,z)、 S(2,y) 、S(1,x)存入SRAM3，SRAM2，SRAM1相应的地址中。

　　2.5 系统软硬件接口及相关软件功能

　　在系统中，并非只有硬件逻辑在不同的模块之间处理数据包，而且还有相应的软件和控制程序。如图2.5-1所示，是数据包在系统中的通道与处理流程。数据在系统中的通道分为data bus和register bus，data bus主要进行数据的硬件处理，register bus则是软硬件的接口。在数据传输的每个阶段对软件应该是可控的、透明的，这些软件在更高层次上执行更复杂的算法和协议，或者处理一些异常情况，同时，对于系统开发人员，也应该是可控的，因为开发人员往往需要配置和调试硬件。使用通用的寄存器接口就可以使数据处理对软件透明化，这是靠映射内部的硬件寄存器来完成的，即所谓的存储映射技术。对于软件来讲，映射寄存器相当于一个I/O接口，它可以由软件访问和修改。

　　

 

　　图2.5-1：系统中的register bus 和data bus

　　Register bus中每个模块的register连接在一起，组成一个信息环路。这些register块中存储了数据处理在每个模块中的状态和阶段，任何一个模块都可以响应来自PCI总线寄存器的访问和控制要求，而PCI总线寄存器可以通过软件来控制。也就是说，硬件和软件的通信是通过PCI总线完成的。

　　数据以及控信息在硬件和主机系统之间是通过PCI总线传输的，以Linux网络存储栈作为接口的。NetFPGA向主机发送分组数据的过程如图2.5-2a所示：

　　分组到达，发往CPU队列;

　　中断程序通知驱动程序有分组到达;

　　驱动程序设置和初始化DMA传送器;

　　NetFPGA通过DMA总线发送分组;

　　中断程序发送DMA结束信号;

　　驱动程序把分组传递到网络存储栈;

　　

 

　　图2.5-2a：NetFPGA向主机发送数据 图2.5-2b：主机向NetFPGA发送数据

　　主机向NetFPGA发送分组数据的过程如图2.5-2b所示：

　　控制软件通过网络socket发送分组，分组被递交给驱动程序;

　　驱动程序设置和初始化DMA传送器;

　　中断程序发送DMA结束信号;

　　主机访问寄存器是通过系统调用系统内核的ioctl( )函数作为接口的。读写寄存器的操作函数如下，这两个函数内部调用了ioctl( )函数。

　　readReg(nf2device *dev, int address, unsigned *rd_data)

　　writeReg(nf2device *dev, int address, unsigned *wr_data)

　　例如： readReg(&nf2, OQ_NUM_PKTS_STORED_0, &val);

　　主机访问NetFPGA寄存器的过程如下：

　　(1)控制软件调用ioctl( )函数操作网络socket，由函数ioctl传递给驱动程序;

　　(2)驱动程序完成PCI寄存器的读写