网络编码原理及应用v.ppt

网络编码迷蝴蝶,韦有富 史婷婷 李伟佳 巨鹏飞 杨明 张 楠 段鹏飞 祝凯捷 张奇龙 林恒,概要,背景 几个例子 主要应用 缺陷 发展前景,提到编码，你想到什么,二战时图灵捣鼓的密码机？ 还是喜欢玩独轮车的香农？ 还是实验课上怎么都稳定不下来的波形？ 总之，额的神哈,那网络编码，你又想到什么,网络上的编码？不对！ 那是什么？召唤我们的蝴蝶吧!,Figure adapted from Scientific American, Chinese 7/2007 edition,网络编码 与 蝴蝶,问题描述 A要将x、y传给B、C x = 0 or 1 y = 0 or 1 每条link一次只能传一个bit,5,？,Either x or y,Figure adapted from Scientific American, Chinese 7/2007 edition,Traffic jam,Store-and-forward,6,xy =,0 if x = y 1 if x y,Figure adapted from Scientific American, Chinese 7/2007 edition,Decode y,Decode x,Network coding (NC),7,网络编码巧妙的利用了网络的拓扑结构。背后的玄机是什么呢？ 插段故事！,乌龟过马路的故事,Mr.Red和Mr. Green要过马路,乌龟过马路的故事,Mr.Red成功过去,乌龟过马路的故事,Mr. Green Orz了怎么破？,乌龟过马路的故事,普通专家：TCP超时重传,乌龟过马路的故事,不愧是专家 文艺范的编码专家这个时候看不惯了,乌龟过马路的故事,他们表示超时重传什么的太不文艺了 我编码，编编编,乌龟过马路的故事,第二只又跪了不鸟它，继续发,乌龟过马路的故事,网络编码的本质是信息扩散！,“嘿，哥们，够了，能解码了！”,Prof. Rudolf Ahlswede 德国University of Bielefel 2010年已经去世，曾获 IEEE香农奖章,蔡宁 Ning Cai 西安电子科技大学,李硕彦Shuo-Yen Robert Li 香港中文大学 FIEEE “网络编码迷蝴蝶”就是他的口头禅。,杨伟豪Raymond W. Yeung 香港中文大学 FIEEE,大牛们的开山之作 2000 IEEE Transactions on Information Theory Network Information Flow,网络编码的理论内涵,点对点的最小割最大流定理: 对于已知的网络流图，从发点S到收点U的流量ru的最大值小于或等于任何一个割的容量，即 ru = mincut(S,u) 记 Cu = mincut(S,u) 网络编码在有些条件下可以比传统方法更加逼近这个最大流。刚才蝴蝶网络就是个例子。,网络编码带来的好处,使组播传输速率达到最小割最大流决定的网络容量的上限 节省网络带宽资源消耗 均衡网络负载 提高网络鲁棒性,几个例子,网络编码的种类非常多，每种有不同的设计目标和设计方式，我们只能从几个简单的例子，窥一斑而知全豹。,22,Communications on Mars（ANC or PNC）,A,B,A,B,2019/7/14,23,RAIDs A B AB,Single backup,= NC,Redundancy in Data Storage,2019/7/14,24,Data,Disks A B AB,A,Perform NC over an imaginary network,Data,Disks A B AB,A,B,Perform NC over an imaginary network,25,Data,Disks A B AB,A,B,AB,Perform NC over an imaginary network,26,容错的编码,如图AB、AC带宽为2，其余为1。任何一个link坏掉，source到destination总能保持2的最大流。,安全的编码,哪个方案更容易被窃听？,网络编码的主要应用,P2P编码 无线网络编码 分布式文件系统编码,网络编码在P2P中的应用,网络编码在 P2P文件共享中的应用 P2P文件共享软件BitTorrent使用网络编码后，可提高某些方面的性能； 微软公司提出Avalanche系统，可大幅度提高文件共享效率，减少因种子节点离开带来的“死档”现象。,网络编码在P2P中的应用,Network Coding解决P2P文件分发网络中的什么问题？ 对于目标节点而言，在组装还原原始文件的时需要确保其收到了组成该文件的所有的数据包，在没有网络编码的情况下，每个数据包都具有唯一性和不可替代性，导致的问题是，目标节点即使收到冗余重复包，也可能收不到特定的某个包。 网络编码使数据包可以被另外的数据包还原，使每个数据包具有平等性，减少重复冗余包的概率，每个数据包所包含的内容都有很大概率是有意义的。,C,B,A,Big File,A+B,B+C,网络编码P2P传输细节,对于每个数据大段，划分为若干小段，然后在大段内进行网络编码，请求方可以同时接收多个peer的小段，直到可以解码出原来的大段。,avalanche,Microsoft利用网络编码试验了文件的分发速度是直接分发的2-3倍。,流媒体P2P点播，比单纯的文件分发更加复杂，有着时间上、网络带宽上和控制上的更高要求，我们可以把上面的思路拿到这里面来。可以大大减轻P2P的协同控制的难度。 现在已经有了几种点播方案： DSL_NC：一种基于DSL（Dynamic Skip List，DSL）overlay的网络编码P2P流媒体点播方案； BAS_DNC：一种基于缓存协助搜索（buffer-assisted search，BAS）覆盖网络的网络编码P2P流媒体点播方案； SonicVOD：一种视频分割辅助的网络编码P2P视频点播系统。 UUSee视频点播系统是首个实际部署了网络编码的流媒体点播运营系统。（InfoCoMM10）,网络编码在流媒体点播中的应用,随机网络编码的点播方法,1.把一个媒体段分为若干块： 2.随机生产编码系数（其实就是一组随机全排列） 3.构造编码块 4.矩阵表示编解码,无线网络编码,由于无线链路的不可靠性和物理层广播特性, 应用网络编码, 可以解决传统路由、跨层设计等技术无法解决的问题.,November 5, 2013,Underwater WiFi will Have a Huge Impact with an Armenian in the team,underwater acoustic sensor network coding,wifi underwater,WUWNET13 CDMA+ANC,水下wifi采用限制：带宽小、延迟大。 为了解决这个问题，文章在CDMA的基础上，结合ANC编码实现了新的MAC层协议。文章传输问题的环境还是广播的环境。,分布式文件系统,E-MBR是追求修复带宽最小的“Raid”,E-MBR原理,把各个储存节点建立成全连接图，计算理论最小修复带宽。,传统raid和E-MBR的比较,网络编码的缺陷,我们刚才给出了一个安全编码的例子，网络编码真的更安全了么？ 在路由节点上可以编解码，会带来额外的安全隐患。 网络编码的复杂性让它在某些领域很难应用，至少现在很多编码方案还只停留在papers里。 但是 网络编码是什么？,再问网络编码,与其说网络编码是一类技术，倒不如说，网络编码代表了一种崭新的思维方式。 如果你一一细数网络编码在各个场合的编码方式，那么它更像一种千奇百怪的技术。 但是如果你把网络编码当成一种思维方式，那么这些技术不过是这种思维方式的具体表现。 网络编码是拓扑下合理的信息扩散；网络编码是在传输过程中编码。,网络编码展望,网络编码不单单是一类技术，它更是一种新的思维方式 网络编码赋予某些传统技术新的活力。 网络编码是数学和工程的对话 李硕彦,网络编码深入到各个领域,数,学,与,工,程,的,对,话,1. Linear network coding (NC) 2. Convolutional NC 3. NC theory via commutative algebra 4. Construction of NC over cyclic networks 5. Martingale of patterns 6. Computing by symmetry 7. Unified algebraic theory of sorting, routing, multicasting, & concentration networks 8. Cut-through coding 9. Algebraic transform of multistage interconnection networks 10. Scalable nonblocking switches and geometric intuition,All my 小把戏 i