浅谈网络编码技术

摘要:传统的通信网络节点只对接收到的信息进行存储和转发,扮演着转发器的角色,但是根据网络信息流中的最大流最小割理论,没有理由仅让网络节点的功能局限于存储和转发。网络节点可以对多条输入链路上收到的数据信息进行一定的线性或非线性处理,然后再发送出去,在接收节点,通过相应的译码运算恢复出信源所发的信息。网络编码正是基于这种思想产生的。文中首先讲述了网络编码的基本原理,在此基础上介绍了目前网络编码在通信网络中的主要应用。在对网络编码有了初步认识的基础上,对于网络编码体现出的优缺点作了总结,并对未来的发展方向进行了分析和展望。

关键词:网络编码;吞吐量;P2P;网络安全

中图分类号:TP393文献标识码:A文章编号:1009-3044(2009)26-7383-02

1 网络编码概述

2000年,香港中文大学的R.W.Yeung和N.Cai首次提出了网络编码,其核心思想是在网络中参与传输的节点,其输出边上传输的数据可以通过该点多条输入边上传输的数据的某种线性或非线性变换得到,而参与传输的所有节点对数据的变换应保证最终所有接收节点可以正确恢复出信源所发送的信息。

网络编码的工作原理是把不同的信息转化成位数更小的“痕迹”,然后在目标节点进行演绎还原,这样就不必反复传输或者复制全部信息了。痕迹可以在多个中间节点间的多条路径上反复传递,然后再被送往最终的目的端点。它不需要额外的容量和路由―只需把信息的痕迹转换成位流即可,而这种转换现有的网络基础设施是可以支持的。

2 网络编码原理

网络信息流的最大流最小割定理:对于已知的网络流图,信源S到信宿T的流量的最大值w等于其最小割的容量[1],即max flow(S,T)=min C(S,T)。

对于只有一个信宿的网络,依靠路由就可以获得最大流。下面看一个具有两个信宿的多播网络,如何获得网络多播的最大流,通信网络如图1所示。

这是一个单信源两信宿的网络,假设每条链路无时延无差错,其中S是源节点,Y和Z是目的节点。图1(a)给出了每条边的信息速率均为1bit/每单位时间。由最大流最小割定理容易得出从信源到目的节点的最大流均为2。由此得到信源S可以同时发送2bit信息给t1和t2。图1(b)给出了一种编码方案,可以看出,为了从信源节点S同时传输2bit信息b1b2到目的节点,则在中间节点3处,必须采用网络编码,使输出边(3,4)传输比特的线性组合为b1+b2(模2加),那么在目的节点t1和t2处才可分别由b1和b1+(b1+b2),b2和b2+(b1+b2)恢复出所有信息b1b2。如果按照传统路由方式,在一个单位时间内将无法把b1b2传输给节点t1和t2,这就是网络编码的优势。

3 在通信网络中的应用

网络编码的应用潜力巨大,应用领域涉及无线网络、P2P系统、网络安全和分布式文件存储等网络的多个方面,本文在此作以归纳。

1) 无线网络

无线网络的物理层广播特性和业务流的双向性非常适合使用网络编码最新的热点集中于物理层网络编码、基于编码的协作方案设计以及实际编码协议性能评估等。相对于传统的合作方案,基于网络编码的方案在同等的频谱效率下可达到更高的分集增益。Katti 等人针对无线网状网提出了基于机会的网络编码协议COPE,并在20个节点的网络测试床上完成了协议实现。这是首个搭建测试床检验实际编码协议性能的研究,结果表明即使在网络连接动态变化甚至出现拥塞的情况下,COPE 协议仍能有效支持多路单播流[2]。

2) P2P系统

网络编码应用在P2P网络中主要有以下三个方面的好处:第一,减少了文件的下载时间。在一个大范围分布式的端到端系统中,找到最优的分组发送时间十分复杂,尤其是主机对于底层网络拓补知之甚少的情况下更是如此,而使用网络编码,网络拓补和发送先后对文件发送时间的影响将会大大减小。第二,由于编码后的分组具有多样性的特点,即使服务器在文件下载过程中离线,或某些网络节点下载结束后立刻离开,都不会产生太大影响,所以基于网络编码的方案与一般的方案相比具有更好的健壮性。第三,与基于转发的协议相比,基于网络编码的协议仅仅在刺激合作机制实现的时候,性能受到一点影响。

3) 网络安全

中继节点对编码数据的恶意修改可能会导致网络编码使用受限甚至不可用1 消除拜占庭敌手影响一直是网络编码安全应用研究中备受关注的问题。有人提出一种用散列函数检测拜占庭敌手的方法。Jaggi进一步给出了一种多项式复杂度的分布式算法,在可纠正敌手错误的前提下,同时达到最优组播速率,该方法无需对编码节点添加新的功能,对无线和有线网络均适用。Krohn 等人提出一种基于同态散列函数的方法用于检测被修改的编码分组,但该方法需要将计算好的散列值预先通过其他通道分发给所有节点,因此该方法具有一定的局限性。有人利用椭圆曲线算法给出了一种适用于网络编码的签名方案,除了可检测被修改的分组,还加入了对数据的身份认证功能[3]。

4) 分布式文件存储

分布式文件存储是网络编码又一个应用热点。Acedanski 等人研究了在多个存储资源受限的节点间进行分布式文件存储的问题,比较了无编码存储、基于纠删码存储和采用随机线性码存储3 种策略,仿真结果表明,基于随机线性码的分布式存储策略,在无需全局文件服务器的参与时,其性能接近集中式全局调度算法。

4 主要优缺点简述

网络编码最初是为使多播传输达到理论上的最大传输容量,从而能取得较路由多播更好的网络吞吐量。随着研究的深入,网络编码在均衡网络负载、提升带宽利用率等方面的优点逐渐凸现。

4.1 提升网络吞吐量

无论是均匀链路还是非均匀链路,网络编码均能够获得更高的多播容量,而且对于节点平均数越大,网络编码在网络吞吐量上的优势越明显。从理论上可证明:如果Ω为信源节点的符号空间,OVO为通信网络中的节点数目,则对于每条链路都是单位容量的通信网络,基于网络编码的多播的吞吐量是路由多播的Ω(SOVO)倍[4]。

4.2 均衡网络负载

网络编码多播可有效利用除多播树路径外其它的网络链路,可将网络流量分布于更广泛的网络上,从而均衡网络负载。图2(a)所示的通信网络,其各链路容量为2。图2(b)表示的是基于多播树的路由多播,为使各个信宿节点达到最大传输容量,该多播共使用SU、UX、UY、SW和WZ等共5条链路,且每条链路上传输的可行流为2;图2(c)表示的是基于网络编码的多播,假定信源节点S对发送至链路SV的信息进行模二加操作,则链路SV、VX和VZ上传输的信息均为ab,最终信宿X,Y和Z均能同时收到a和b。容易看出,图2(c)所示的网络编码多播所用的传输链路为9条,比图2(b)的多播树传输要多4条链路,即利用了更广泛的通信链路,因此均衡了网络负载。网络编码的这种特性,有助于解决网络拥塞等问题。

4.3 提高带宽利用率

在图2(b)中的路由多播中,为了使得信宿X,Y和Z能够同时收到2个单位的信息,共使用了5条通信链路,每条链路传输可行流为2,因此其消耗的总带宽为:5×2=10。在图2(c)表示的网络编码多播中,共使用了9条链路,每条链路传输可行流为1,其消耗总带宽为:9×1=9,因此带宽消耗节省了10%,提高了网络带宽利用率。

虽然网络编码优点突出,但运用网络编码增加了计算的复杂性,而且网路节点需要缓存足够的输入信息,因此编码操作增加了传输时延和节点的额外的I/O、CPU消耗。一些学者对网络编码的综合性能进行了初步的研究和探讨。统计数据表明,即使应用最有效的随机网络编码,其编码和译码的时间也不容忽视。此外,应用网络编码还存在同步问题,这主要是由于信宿节点必须等待收到足够的编码信息,才能开始译码.同步问题给在实时系统中应用网络编码提出了挑战[5]。

5 未来发展方向

经过多年的快速发展,基于网络编码的新理论和新应用不断涌现,可以说,网络编码正给现有网络带来变革性的变化。但从研究的深度来看,仍处于探索阶段,还存在一些尚未解决的问题或者尚未探索的领域。网络编码未来的发展方向主要体现在以下几个方面:

1) 网络编码理论的进一步完善。现有的网络编码理论研究主要集中于单源组播网络的线性网络编码,针对多源组播网络和非组播网络的网络编码理论研究还远不够深入,如何利用非线性网络编码优化网络性能,也是未来一个重要的研究方向。

2) 网络编码与其他相关领域的技术的融合。包括网络编码和信源编码Slepian2Wolf 的联合设计与优化、网络编码与信道编码和调制技术的进一步结合以及网络编码与多描述分层编码的结合等,都是值得关注的方向。

3) 降低网络编码的复杂度。网络编码对网络性能的提升伴随着设计和实现复杂度的增加,综合考虑性能增益和网络开销,实现最小代价的网络编码是将来需要深入研究的问题[6]。

4) 网络编码在实际网络和复杂流量条件下的性能改进。网络编码在无线网络和P2P系统中具有广阔的应用前景。目前涉及实际网络编码系统的性能分析和评估的研究还较少。针对实际网络的拓补结构,结合IP路由技术、交叉层设计思想以及优化理论,实现编码感知的高效路由和调度算法将成为今后研究的重点问题。此外,在流量动态变化的真实网络中,具有可变速率的网络编码技术也将是值得关注的研究方向[7]。

6 结束语

网络编码理论是网络通信研究领域中的一项重要突破,自从首次提出以来,已迅速发展成一个重要的研究范畴,并对信息论、编码、通信网络、网络交换理论、无线通信、计算机科学、密码学、运筹学、矩阵理论等领域带来了深远影响。网络编码已成为现今世界各地一流大学及工业实验室最热门的研究领域之一,也是众多国际研讨会的热门议题。网络编码带给网络应用一场模式革命。几年前,微软以网络编码作为核心技术开发出“雪崩”(Avalanche)原型软件。“雪崩”对于P2P通信的大规模内容分发而言,传送速度可高出BT(BitTorrent)20%~30%。由于P2P通信占互联网带宽的60%以上,所以研究人员估计,未来十年,网络编码技术将会产生巨大影响,从计算机通信、无线通信到其他各类通信,都会广泛地采用网络编码。

参考文献:

[1] 杨行峻,郑君里.人工神经网络与盲信号处理[M].北京:清华大学出版社,2003.

[2] 陶少国,黄佳庆,杨宗凯,等.网络编码研究综述[J].小型微型计算机系统.2008,29(4):583-589.

[3] 杨林,郑刚,胡晓.网络编码的研究进展[J].计算机研究与发展,2008,45(3):400-407.

[4] Ho T,Karger D,Medard M,et al.The benefits of coding over routing in a randomized setting[C].Yokohama,Japan:IEEE International Symposium on Information Theory,2003:442.

[5] Tomislav Nad.Promblems with network coding in overlay networks[EB/OL].zoo.cs.yale.edu/class/cs490/04-05a.

[6] Lun D S, Ratnakar N, Medard M,et al.Minimum-cost multicast over coded packet networks[J].IEEE Trans on Information Theory,2006,52(6):2608-2623

[7] Fong S L, Yeung R W.Variable-rate linear nerwork coding[C].Chengdu:IEEE Information Theory Workshop,2006.

[8] 彭铁光.基于多播的网络编码研究[J].电脑与信息技术,2008,16(3):23-24.

[9] 崔凯,王丽.网络编码技术及其在通信网络中的应用[J].黑龙江科技信息,2007(4),46.

[10] 付琳,付志雄.网络编码研究[J].科技资讯,2007(7).