个重要突破
其划时代意义在于:推翻了独立比特不能再被压缩经典结论指出网络信息流可以被压缩从而可进步提升网络吞吐量因此该理论也被称为网络信息流理论
至今网络编码理论已经应用于众多领域
如P2P、应用层多播、无线Ad hoc网络、无线传感器网络和无线Mesh网络等网络编码主要优缺点和关键理论问题研究可参见文献[2]限于篇幅不再赘述
本文主要阐述网络编码在P2P中
应用包括P2P文件下载和P2P流媒体中应用它们主要区别在于对P2P流媒体中应用有实时性要求因此网络编码应用于P2P流媒体中需额外考虑优先级问题下面首先介绍随机网络编码具有分布式特性目前应用非常广泛1随机网络编码
Ho等在文献[3]中提出了分布式网络编码
构造思路方法——随机网络编码(RNC)该思路方法基于种随机选择编码向量策略:对于除了信宿节点外所有中间节点只要在个足够大有限域上随机选择它们输入链路到输出链路映射且各节点映射关系选取是相互独立从而保证各信宿能以较高概率成功译码如图1所示
源节点S向目节点R1和R2发送消息X1和X2各链路上系数向量(全局编码向量)和信源发送信息进行同步传输各个系数向量ξ1,ξ2……ξn 在有限域中随机选取在通过编码节点时系数向量根据随机选取映射关系进行更新最终目节点R1和R2收到输入信息将包含输入链路对应全局编码向量和信源发送信息流例如R1收到ξ1X1+
ξ2X2和ξ5(ξ1X1+ξ2X2)+ξ6(ξ3X1+ξ4X2)
同时R2收到ξ5(ξ1X1+ξ2X2)+ξ6(ξ3X1+ξ4X2)和ξ3X1+ξ4X2然后采用高斯消元法(即解线性方程组)正确译码获得X1和X2文献[3]中给出了解码概率
定理当信源相互独立或线性相关所有节点全局编码向量都在有限域Fq上独立均匀选取则接收节点能以最小概率(1-d /q)η译出信源发送消息其中d 是信宿节点数目q(>d )为编码符号域大小η是随机选取编码系数链路数目该定理介绍说明只要当编码符号域q足够大总可保证接收节点以较高概率成功译出信源发送信息文献[4]指出当有限域大小|Fq |=216和链路数|E |=28时解码成功率可达0.996而且指出|F |=28就足够实际使用了RNC具有分布式特性
无需事先获知整个网络拓扑信息尤其适用于拓扑结构动态变化或者大规模网络微软提出P2P文件下载系统Avalanche[5]便是首先采用RNC典型P2P应用2网络编码在P2P文件下载中主要技术
P2P文件下载中主要有以下3种网络编码技术
2.1无分代随机网络编码技术
典型代表是微软公司开发
基于随机网络编码(RNC)P2P文件下载系统Avalanche[5]其原理(如图2)是:假设服务器需要传输文件给对等节点A则首先将服务器上文件分解成n 个文件块即B1,B2……Bn然后应用随机网络编码随机选择系数c 1c 2……cn将线性网络编码后组合块E1=c 1B1+c 2B2……cn Bn传送给对等节点A假设对等节点A又收到另外个编码后组合块E2=c 1'B1+c 2'B2……cn' Bn该组合块来自其它对等节点或者服务器然后对等节点A再随机选择编码系数c 1″、c 2″对E1和E2进行线性操作将操作结果E3=c 1″E1+c 2″E2发送给对等节点B如此则对等节点 B又传送给其它对等节点只要每个对等节点收到足够多线性无关组合就可以通过解线性方程组译出原始文件块
P2P文件下载中采用网络编码
优势是:分块随机组合后整个网络分块分布均衡化而且能够适应P2P系统动态变化例如某节点动态离开后相应分块也随的带走对BitTorrent而言节点离开可能带走稀有分块从而造成“死档”；而对Avalanche系统由于网络中存在所有分块组合只要收到足够多线性无关组合就可以通过解方程组得到所需分块因而可使下载“死档”概率大大降低2.2分代网络编码技术
当将网络编码应用于P2P网络中时
编码策略将会对网络性能产生至关重要影响原始编码策略是将个文件分成多个分块然后在所有分块的间进行编码传输该思路方法虽然可以提高网络传输效率但也存在两点不足:第由于编解码过程是在个文件所有分块的间进行导致系统计算开销过大；第 2解码出文件前提是收到编码过分块组合数目等于或大于文件原始分块数目因此当没有达到这样数目的前得到编码过分块组合是无法解码出文件原始分块这种编码方式对文件传输很不利尤其是对于流媒体而言因此可以考虑使用分代技术分代技术[6]是指将需要传输
文件分成多个代每代拥有固定数目分块编解码过程发生在代内分块的间图3所示是个拥有m 代网络编码示意图对每代内分块进行编码产生多个经过编码分块组合 E(gi)各代的间编码产生分块组合是相互独立分代网络编码技术也存在个问题即有时由于节点退出网络中已经不存在足够线性无关编码分块组合来解码出某代原始分块导致无法解码出完整文件为了解决该问题可以引入代间编码技术
2.3代间网络编码技术
代间编码技术集合相邻
多代组成个代集图4中所示是个拥有m 代、每代拥有k 个分块代集代集内每代编码包括了代集内这代以及的前所有代分块信息例如考虑某代gi(i≤m -1)编码分块它是由代g 0、g 1……gi中所有分块编码而来代集的间编码产生分块是相互独立同样要解码代gi总共需要获得代g 0、g 1……gi的中共(i+1)k个独立编码分块组合同时解码出代g 0、g 1……gi这样编码技术决定了它无法单独解码出某代但是同样它也有个好处即当代集中某代无法得到解码所需要足够多编码分块时缺少部分可以由其序号的后代来弥补例如当gi -1代无法解出可由后代gi代弥补虽然说在代规模都是k个分块情况下代间网络编码技术需要计算开销将大于分代技术但是当分代技术中代规模是mk个分块时分代技术计算开销将会比代间编码技术高多体现了代间网络编码技术优越性
3网络编码在P2P流媒体中主要技术
3.1
种基于网络编码P2P流媒体节点架构基于网络编码
P2P流媒体把数据流分为若干个数据段每个数据段再进步划分为大小均为k n 个数据块如图5所示
对等节点
系统构架[7]如图6所示对等节点从上流节点接收数据块后按照其所属数据段优先级进行收集经由解码器送入播放缓存Cache；编码器对解码后数据进行重新编码发送给下行对等节点
编码器:对每
数据段中数据块进行随机网络编码邻居节点随机选取编码系数[c 1,c 2……cm](m≤n)对当前数据段中拥有数据块进行编码当m /n =1时表明该节点已拥有这个数据段中所有n个数据块解码器:节点收到数据块后
用Gauss-Jordan消元法进行逐步解码解码过程中若发现线性相关数据段则及时剔除当个数据段收到n 个线性独立数据块的后则可以完全解码播放缓存Cache:如图7所示分为3部分
首先下载紧急模式中分块同时对等节点对自己拥有数据块进行重新编码发送给下行节点
3.2基于网络编码技术
P2P流媒体数据调度3.2.1分层网络编码
基于网络编码技术
P2P流媒体较P2P下载在数据调度上需要重点考虑数据中些紧急重要数据文献[8]提出了分层网络编码(HNC)可以解决P2P流媒体因实时性造成优先级问题HNC编码方案使得那些紧急重要数据包可以优先被解码HNC编码举例如下:假设
个信息流被分为多个数据包每个数据包属于A、B、C 3类中类其中A类数据包最重要B类次的C类最不重要假设这个信息流仅6个数据包分别为a1、a2、b1、b2、c1和c2则HNC编码构造方案如下:N1=f11a1+f21a2；
N2=f12a1+f22a2+f 32b1+f 42b2；
N3=f13a1+f23a2+f 33b1+f 43b2+f 53c1+f 63c2；
这样
当接收到6个线性独立编码过数据包后a1、a2定能被解码b1、b2仅在接收到6个为N 2或N 3类数据包时才能被解码c1、c2仅在接收到6个N 3类数据包时才能被解码这样A、B、C 3类包被优先解码概率为A>B>C这种思路方法从编码角度对具有优先级数据调度提供了种思路 3.2.2网络编码在P2P直播中
应用(1)Pull调度思路方法:
目前
Pull调度思路方法在P2P流媒体技术中广泛运用引入网络编码后对该数据调度思路方法提出了新要求:即需要决定对等节点应该从哪些邻居节点获取哪些数据块,以便每个数据块在播放的前都能被解码如果不能被全部及时解码,则使不能被及时解码数据块个数最少；和此同时还需考虑到节点间可用带宽约束文献[9]提出了
种数据调度算法,其主要思想:首先随机选取n 个上行节点作为邻居节点其次对等节点按每个数据段播放先后顺序对段内数据块发出请求；对每个数据段如果未能收到n 个相互独立数据块则从n 个源节点以外邻居节点请求数据块直到收到n 个相互独立数据块或邻居节点轮询完为止此外
为优化传输效果在当前节点随机选取完邻居节点后会向这n 个邻居节点以外待选邻居节点发送探测包若探测结果显示待测对等节点和当前节点间带宽和时延优于目前大部分邻居节点则剔除原邻居节点中性能最差那个节点把这个探测到待测节点加入到邻居节点列表中去(2)Push调度思路方法:
经网络编码组合后可使数据段内
数据块具有无序性所以Push调度思路方法可以更好地体现网络编码给P2P流媒体带来好处文献[10]中提出了种基于网络编码Push调度机制Push调度思路方法中
邻居节点随机选取某数据段编码后数据块Push给下行节Push时要优先考虑到马上就要播放数据段如图8设选取当前播放点t 秒后区域作为优先区域邻居节点采用均匀分布方式优先发送Push优先区域内数据段相关数据块当优先区域中某数据段仍缺失些数据块时则紧急方案启动在其带宽允许情况下其所有邻居节点向其发送该数据段数据块即要保证优先区域内所有数据段都需完整当优先区域内数据段都完成接收后对其后数据段采用特定概率分布
进行Push该概率分布只要能达到Push后越接近优先区域数据段越先收到n个数据块总效果即可如图9(a)
Push存在
问题:邻居节点Push时并不知道其Push当前数据块时接收节点是否已经收到了n 个相互独立数据块所以Push机制需要种预刹车方案[10]当接收节点快接收到n 个数据块时向其邻居节点发送信息表明其将要接收到n 个数据块逐步减少向其Push邻居节点个数从而减少不必要数据传输(3)Push调度思路方法和Pull调度思路方法(如图9(b))
比较:Push调度较Pull调度
优点:缩短播放缓存Cache
化时间:采用Pull
思路方法必须先交换媒体内容数据信息发送数据请求才能开始传输数据这将导致定程度播放延时积累Push调度思路方法采用同步播放机制通过Push调度思路方法新节点可以很快地获取所需数据段提高带宽利用率:
Pull调度思路方法中
缓存Cache映射(BM)需要周期性在节点间交换Push数据调度思路方法只在播放了个数据段或完成某数据段下载时才将BM嵌入到编码后数据块中3.2.3网络编码在P2P点播中
应用P2P点播系统相对于直播系统而言具有更强
异步时序性其核心问题是如何对用户异步播放操作进行快速响应网络编码引入使得对等节点可以更好利用其邻居节点资源从而缩短信息获取时间并缓解节点对服务器压力举例介绍说明如下:设服务器提供
信息流被分为A、B、C、D、E、F共6个数据包X、Y、Z互为邻居节点情况下X拥有数据包A、BY拥有数据包AZ没有任何数据包(1)基于网络编码(NC)
数据调度算法如图10(a)
T0时间片内:节点X、Y、Z分别从服务器请求得到随机编码后数据包C-FB-F和A-F；Y从X请求得到数据包B；Z从X请求得到编码后数据包A、B并从Y请求得到数据包A
如图10(b)
T1时间片内:节点X从服务器请求得到和T0 时间片中编码系数区别编码数据包C-F从YZ分别得到编码后数据包B-FA-F；Y从服务器请求得到编码后数据包B-F从XZ分别得到编码后数据包B-FA-F；Z从服务器得到编码后数据包A-F从X、Y分别请求得到编码后数据包A-F(以上编码后数据包均要求编码系数线性无关包括和T0时间片编码系数线性无关)如图10(c)所示
T1时间片结束后X、Y、Z各拥有6个线性无关数据包到T2时间片便可解码得到所有消息综上
NC算法仅花费2个时间片用于下载从服务器请求6次数据充分利用对等节点资源缩短了响应时间有效地减轻了对等节点对服务器压力但是NC算法也存在问题即对等节点需接收到6个数据包后才能被解码当遇到些立即就要播放数据包时NC算法反而会造成播放延时(2)基于具有截止时间意识
网络编码数据调度算法具有截止时间意识
网络编码(DNC)[11]是对NC种改进算法可有效解决由NC算法造成播放延时问题DNC提出了编码窗(CW)概念CW大小即参和编码数据包个数其值由“有效邻居节点”个数和距当前播放点时间片数目乘积决定“有效邻居节点”指拥有其所需数据包节点如图11(a)
T0时间片:设节点X、Y当前播放点分别为B、A节点X“有效邻居节点”个数为1(即仅能从服务器获取所需数据包)距当前播放点时间片为1即CW=1×1=1由服务器处得到数据包C节点Y“有效邻居节点”个数为2(服务器和节点X)CW=2×1=2分别由服务器和节点X处获得数据包B-C和BT0时间片结束后节点X拥有数据包A、B、CY拥有数据包A、B并可立即解码得到C
如图11(b)
T1时间片:X节点当前播放点变为C同理CW=1从服务器获得数据包DY节点当前播放点位B由于T0时间片结束后Y拥有数据包A、B、C所需数据包为D“有效邻居节点”个数为1(仅服务器)距当前播放点B时间片为2CW=1×2=2,从服务器获得数据包D-E如图11(c)
T2时间片中对等节点可以相互交换数据包而无需向服务器请求数据最终得到图11(d)综上
DNC算法花费3个时间片用于下载从服务器处请求6次数据尽管比NC算法多了个时间片但该算法解决了对等节点需接收到6个数据包后才能解码而造成些紧急片段播放延时问题5结束语
本文综述网络编码在非实时P2P文件下载和实时P2P流媒体中
主要应用技术思路方法尤其阐述网络编码在具有优先级要求P2P流媒体中应用最后讨论研究方向网络编码在P2PQoS/QoE中
应用利用网络编码来辅助提升QoS/QoE基于最小代价网络编码
P2P应用以降低网络编码引入编解码复杂性基于网络编码
P2P应用中安全问题是P2P可持续发展关键问题的基于网络编码
P2P软件Software原型系统开发和基于Plantlab等实际网络上仿真研究例如网络编码实现中同步问题；具有拓扑意识
网络编码在P2P中应用将拓扑意识加入到基于网络编码P2P应用中提升P2P传输效率；P2P流媒体中基于网络编码Pull和Push相互结合调度机制等
最新评论