摘要
网络编码改变了传统网络节点上路由器交流和交流机对信息流“存储—转发”的形式，提出网络路由交流节点对输入的信息流编码后再发送，并在接纳器上进行解码，然后复原信息。跟着网络编码理论的日益展开和完善，其运用的研讨也越来越受到重视。
本文首要介绍网络编码理论的基本概念，回忆了近年来网络编码的研讨动态。接着指出研讨多信源网络编码组播通讯的重要性，在运用NetFPGA开发渠道的根底上，提出网络编码组播通讯系统及其全体设计计划。在计划中要点介绍了硬件系统中选用的编码战略—随机线性编码，解码战略、算法以及通讯协议，一起介绍了系统的软硬件接口和软件效果。最终，给出了编码路由器、转发路由器以及解码路由器三个系统的具体设计计划，计划中首要包含单元模块图，每个模块的首要功用与结构，数据处理流程及算法阐明，输入输出信号及阐明、要害时序或情况。
由于本系统的首要功用是由硬件完结，所以和传统组播通讯网络比较，具有时延小，没有了调度和排队时刻，使得网络中链路负载更均衡，表现出了网络编码的优势。
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。假定每个途径每秒可带着一个位元，并且只能顺着箭号所指的方向行进。假如路由器只传输其所接纳到的信息，那么中心链路将是个瓶颈，由于每秒一共接纳到二位元的材料，但其容量只要一位元，路由器每秒只能传送一位元材料给中心链路，这种瓶颈会构成可怕的塞车。相反，假如把一般的路由器换成编码器，它能够把两个信息经过异或或许线性组合运算成单一位元输送给中心链路，并且发送ai+bi (或许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比特。所以经过运用网络编码，流量负载能够涣散在整个网络上。
(a)链接容量 (b)单会话的IP组播
(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]，Microsoft公司现已选用网络编码作为其下一代网络内容发布渠道Avalanche的核心技能。
不只国外，近两年来国内学者也开端研讨网络编码。清华大学[15]，西安电子科大、及电子科技大学[16]，北京邮电大学[17]均投
