基于网络编码的多信源组播通信系统.doc

基于网络编码的多信源组播通信系统
摘要
网络编码改变了传统网络节点上路由器交换和交换机对信息流“存储—转发”的模式，提出网络路由交换节点对输入的信息流编码后再发送，并在接收器上进行解码，从而还原信息。随着网络编码理论的日益发展和完善，其应用的研究也越来越受到重视。
本文首先介绍网络编码理论的基本概念，回顾了近年来网络编码的研究动态。接着指出研究多信源网络编码组播通信的重要性，在使用NetFPGA开发平台的基础上，提出网络编码组播通信系统及其整体设计方案。在方案中重点介绍了硬件系统中采用的编码策略—随机线性编码，解码策略、算法以及通信协议，同时介绍了系统的软硬件接口和软件作用。最后，给出了编码路由器、转发路由器以及解码路由器三个系统的详细设计方案，方案中主要包括单元模块图，每个模块的主要功能与结构，数据处理流程及算法说明，输入输出信号及说明、关键时序或状态。
由于本系统的主要功能是由硬件实现，所以和传统组播通信网络相比，具有时延小，没有了调度和排队时间，使得网络中链路负载更均衡，体现出了网络编码的优势。

目录
1 网络编码理论及相关研究应用背景 4
1.1网络编码理论产生背景和基本概念 4
1.2国内外研究动态与现状 8
2 多信源组播系统结构及整体设计方案 9
2.1项目研究需求、目标和内容 9
2.2 NetFPGA——新一代开放式网络研究平台简介 10
2.3 利用NetFPGA实现本设计的总体构想 11
2.4系统实现的整体设计方案说明 11
2.4.1 系统拓扑图及说明 11
2.4.2编码策略与方案 12
2.4.3随机系数的选择 14
2.4.4 NCP数据包头的格式 14
2.4.5 转发（组播）路由器R工作流程 17
2.4.6数据包的解码 18
2.5 系统软硬件接口及相关软件功能 26
3 系统的详细设计方案 28
3.1 概述 28
3.2 编码路由器详细设计方案 28
3.2.1编码系统整体模块如图3.2-1所示 28
3.2.2系统中各单元模块的功能与时序 29
3.3 转发路由器详细设计方案 44
3.3.1转发路由器系统整体模块图 44
3.3.2系统中各单元模块的功能与时序 46
3.4 解码路由器详细设计方案 51
3.4.1 解码路由器系统整体模块图 51
3.4.2系统中各单元模块的功能与时序 52
4 结论 74
5 参考文献 78
附录 81

1 网络编码理论及相关研究应用背景
1.1网络编码理论产生背景和基本概念
60年前C.E.Shannon发表“通信数学原理“解决了信道容量极限问题。2000年诞生的网络编码（Network Coding:NC）是继此后的一个全新突破，它解决了网络通信中单/多源对多接收点组/广播如何达到网络容量极限的问题。传统网络通信节点上的路由交换机只完成存储转发功能。NC指出如果允许路由交换机对输入信息流进行编码再发送，使得网络节点既实现路由功能又实现编码功能。在这种全新的体系结构下,网络性能可以达到最大流传输的理论极限[1][2]。
2000年，以香港中文大学信息工程系为主的研究人员针对通讯网络的瓶颈问题，提出了一种看似疯狂的想法，这种具有革命潜力的方法名为网络编码，以网络编码器取代路由器；原本只是单纯的传送信息的路由器，换成编码器之后，传送的却是有关信息的证据，而不是信息本身；当接收器收到证据时，即可结合各项线索，推导出原始信息。[3]
《科学美国人》杂志（Scientific American Magazine）2007年6月，以“Breaking Network Logjams”（打破网络僵局）为题刊登了MIT科学家详细介绍了7年前诞生于香港中文大学的网络编码理论[4]。其中指出，网络编码是继60年前C.E.Shannon发表“通信的数学原理”后，网络通信理论的一个全新突破。C.E.Shannon解决了点对点信道的容量极限问题，而NC解决了如何达到单源对多点及多源对多点的网络通信容量极限的问题[4]。传统网络通信理论把信息流当成管道中流动的水，是不可压缩的；故传统网络节点上的路由交换机只是完成存储转发功能。NC理论的划时代意义在于：提出网络路由交换节点对输入的信息流进行编码再发送，可进一步提升网络吞吐量！从而改变了比特不能再被压缩的经典结论，指出网络信息流可以被压缩。
网络编码最简单的概念来自‘蝴蝶网’，如图1.1-1所示：

图1.1-1 网络编码的基本原理
上图所示的网络中，源节点S1想把信息流ai传送给R1和R2。另一方面，源节点S2也希望在相同时间、以相同速度，把信息流bi传送给同样的接收节点R1和R2。假设每个路径每秒可携带一个位元，而且只能顺着箭号所指的方向前进。如果路由器只传输其所接收到的信息，那么中间链路将是个瓶颈，因为每秒总共接收到二位元的资料，但其容量只有一位元，路由器每秒只能传送一位元资料给中间链路，这种瓶颈会造成可怕的塞车。相反，如果把一般的路由器换成编码器，它可以把两个信息通过异或或者线性组合运算成单一位元输送给中间链路，并且发送aibi (或者ai和bi的任意线性组合)，这样就轻而易举地解决了塞车问题[3][5]。
网络编码另一个与路由系统不同之处在于，充分利用网络资源。图1中，S1透过路径S1R1把ai传给R1，S2透过路径S2R2把bi传给R2，这在路由系统中是不会使用到的。节点R1接收到ai，并且根据每次编码器运算结果，输入到与编码器使用的相同函数（异或或者线性组合）内，推导出bi。节点R2解出ai也是同样的道理。重复对每个位元字串进行相同的流程，最后就能得出两个原始信息。
可见，有了网络编码，网络的运作可望变得更有效率（不需要增加硬件设备或频宽，就可以提高网络吞吐量），可以改善网络的负载均衡，节省网络带宽消耗，节省无线网络的能量消耗，提高了网络的鲁棒性，同时对于具有链路时延的网络，相对于路由方式，通过网络编码进行多播传输时可以获得较小的传播时延[6][7]。
随后，李硕彦等在证明了在足够大的有限域内，通过节点内进行线性网络编码（Linear Network Coding： LNC）就可以达到网络组播，广播等的理论上限[8]。在线性范围内解决达到理论上界的问题为NC进入实际应用奠定了坚实的基础。随后，Yueng，李硕彦[9]等出版了国际上第一本网络编码理论专著“Network Coding Theory”。
Koetter等[10]于2003年提出将NC问题与多项式方程建立数学联系，使得讨论NC问题又多了一种有力的数学工具代数理论；LNC针对于已经了解整个网络拓扑状况的情况下，经过网络路由设定，通过确定的矩阵计算公式对报文进行编解码，实现简单，但适应性和容错性较差。论文[11]中提出随机网络编码概念（Random Network Coding：RNC），与线性编码结合在一起，使得分布式的、简单实用的网络编码体系形成。随机线性网络编码是一种分布式算法，编码在有限域上进行，系数随机选取，其灵活性远大于LNC。
下面给出一个不仅NC提高多播网络吞吐量，而且显著改善网络负载均衡的例子。图1.1-2(a)显示了网络的容量，所有的边的容量都是2。在这个例子中，最大流是4。图2(b), (c)和(d)分别显示了单会话IP组播，多会话IP组播和基于网络编码的组播的分配树。在图2(b)中，发送端通过一个组播分配树同时向接收端R1, R2和R3发送了两个比特a，b。在图2(c)中，组播会话1，2和3分别向接收者发送了比特a，b和c。需要指出的是多会话IP组播所有的会话不是拥有同一个分配树。在图2(d)中，发送端同时向接收端R1, R2和R3发送了四个比特a，b，c和d[12]。
所有的组播技术中网络编码可以达到最高的吞吐量，因为它可以最大流发送信息。我们看到在图2(b), (c)和(d)中在单位时间内接收端分别接收到2，3和4比特。因此在这个例子中，基于网络编码的组播的吞吐量是单会话IP组播的2倍，多会话IP组播的1.3倍。
通过比较基于网络编码的组播和现在的组播来研究负载均衡的影响。假定基于网络编码的组播使用图2(d)例子中的容量的一半。在这种情况下，单会话IP组播和网络编码都在单位时间内向所有的接收端发送了2比特。在图2（b）中，通过了网络中9条链路（总共发送10比特）中的5条来传输2比特，另外4条没有使用。另一方面，当网络编码使用时，2( d) 通过了9条链路（总共发送9比特）来传输2比特。于是通过应用网络编码，流量负载可以分散在整个网络上。
S
1
2
3
R1
R2
R3
2
2
2

2
2
2
2
2
2
S
1
2
3
R1
R2
R3
a,b
a,b

a,b

a,b
a,b

（a）链接容量 （b）单会话的IP组播
会话1：a
会话2：b
会话3：c

S
1
2
3
R1
R2
R3
S
1
2
3
R1
R2
R3
a,b
a+c,b+d
c,d
a+c,b+d

a,b

c,d

a,b

a+c,b+d

c,d

（c）多会话的IP组播 （d）网络编码组播
图1.1-2 网络编码提高网络容量，同时均衡了网络流量
1.2国内外研究动态与现状
网络编码自诞生以来，普及性的急速增长就连其奠基者也始料未及。从2005年开始每年一次的NetCod workshop 得到了Microsoft, Qualcomm等机构的资助。短短几年，发表了几百篇学术论文。这个崭新的领域对许多相关学科产生了深远的影响，NC的理论研究范围包括信息论及通信的几乎每个领域，如线性编码，非线性编码，随机编码，静态码，卷积码，群码，Alphabet码，码构建，算法协议，有环网络，无向网络，链路失效及其网络管理，分离理论，错误检测和纠错码，密码学，多信源编码，多-单播编码, Cost Criteria, 非均匀需求,关联信源编码，最大流/刮集界，叠加编码，网络互连，路由寻找，无线及卫星网络，Ad hoc网络，传感网络，数据存储及分布，矩阵理论，复杂性理论，图论，随机图论，树装箱（Tree Packing），多种物流（Multicommodity flow），游戏理论，矩阵胚理论（Matriod theory），信息论不等式，排队论分析，率失真（rate-distortion）可逆网络，多用户信道，联合网络信道编码，P2P网络等[13]。
国外多所著名大学如普林斯顿大学、麻省理工、瑞士EPFL 学院等和多家IT 公司的研究中心,包括微软研究院、贝尔实验室、AT &T 的香农信息实验室等都在积极开展对网络编码理论和应用的研究。与此同时，网络编码的实际应用问题被提到技术研究的前线。从2005年第一届Net Cod国际会议上就明确将NC在现实通信中的应用作为研究的重点。微软公司是最早开展网络编码应用研究的公司[14]Error! Reference source not found.，Microsoft公司已经采用网络编码作为其下一代网络内容发布平台Avalanche的核心技术。
不仅国外，近两年来国内学者也开始研究网络编码。清华大学[15]，西安电子科大、及电子科技大学[16]，北京邮电大学[17]均投入了NC与无线网络方面的研究。NC在P2P网络传输，流媒体广播及内容分发方面的应用方面，上海大学[18]、湖南大学[19]和并行与分布处理国家重点实验室[20]，中国科学技术大学[21]等都进行了研究。最近几年中，网络编码在组播通信方面的应用成为了研究的热点，复旦大学研究了单信源组播并提出了一项关于在目前internet路由器上实现网络编码的专利[23]，西安电子科技大学提出了一种基于网络编码的组播路由算法，能够大大降低网络资源消耗，同时能改善负载均衡[24]。
以上网络编码在通信中的应用研究基本上都是处于理论和计算机软件仿真阶段，在用硬件平台搭建实际的组播网络，并在真实的网络环境中应用网络编码，进行其实现的复杂度和网络性能的评估等方面的研究尚处于起步阶段。
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所示：
MAC IP NCP 有效载荷

图2.4-2：编码后数据的封装格式
为减小相应的编码负担和提高编码效率，我们只对网络中的IP数据报中的有效载荷进行编码（已经编码过的数据包可以再进行编码），不对ARP等其他数据包编码。在编码路由器中，我们为不同的输入通道开辟不同的FIFO以进行顺序存取和编码，编码流程如图2.4-3所示:

接收数据并缓存于相应的FIFO中
取出数据，填塞成相同长度，编码
封装成NCP数据包
是否为IP数据包
将编码好的数据放入输出队列，发送

否

是

图2.4-3：数据包的编码流程
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
代的编号
编码次数
编码后的有效载荷
0 3 7 23 25 31
图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工作流程
接收数据包，并将其存入FIFO中

添加NCP包头前两行，并直接将原有IP包的载荷附加到后面

是否为IP数据包 ？
发送到输出端口

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

否

是

图2.4-6：转发路由器的工作流程
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。
(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：解码子任务流程
(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，解码过程如下：

高速缓存1
地址 数据
00 a S(1,x)+b S(2,y)
02 a S(1,p)+b S(2,k)
01 b S(1,y)+g S(2,m)
03
…… ……
高速缓存2
地址 数据
00 gS(2,m)+h S(3,n)
02 eS(2,y)+f S(3,z)
01 eS(2,k)+h S(3,s)
03
…… ……
高速缓存3
地址 数据
00 S(3,p)
02 S(3,q)
01 S(3,z)
03
…… ……

CAM3
包头 索引
S(3,p) 00
S(3,p) 00
S(3,z) 01
S(3,z) 01
S(3,q) 02
S(3,q) 02
03
03
…… ……

CAM2
包头 索引
S(2,m) 00
S(3,n) 00
S(2,k) 01
S(3,s) 01
S(3,z) 02
S(2,y) 02
03
03
…… ……
CAM1
包头 索引
S(1,x) 00
S(2,y) 00
S(1,y) 01
S(2,m) 01
S(2,k) 02
S(1,p) 02
…… 03
… 03
…… ……

图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所示：
（1） 分组到达，发往CPU队列；
（2） 中断程序通知驱动程序有分组到达；
（3） 驱动程序设置和初始化DMA传送器；
（4） NetFPGA通过DMA总线发送分组；
（5） 中断程序发送DMA结束信号；
（6） 驱动程序把分组传递到网络存储栈；