网络编码原理及应用v2-PPT精选课件.ppt

1、网络编码迷蝴蝶网络编码迷蝴蝶韦有富 史婷婷 李伟佳 巨鹏飞 杨明 张 楠 段鹏飞 祝凯捷 张奇龙 林恒概要概要背景几个例子主要应用缺陷发展前景提到编码，你想到什么提到编码，你想到什么二战时图灵捣鼓的密码机？还是喜欢玩独轮车的香农？还是实验课上怎么都稳定不下来的波形？总之，额的神哈那网络编码，你又想到什么那网络编码，你又想到什么网络上的专用编码？不对！那是什么？召唤我们的蝴蝶吧!Figure adapted from Scientific American,Chinese 7/2019 edition网络编码网络编码 与与 蝴蝶蝴蝶 问题描述A要将x、y传给B、C x=0 or 1 y=0 or

2、 1每条link一次只能传一个bit5？Either x or yFigure adapted from Scientific American,Chinese 7/2019 editionTraffic jam Store-and-forward6xy=0 if x=y1 if x yFigure adapted from Scientific American,Chinese 7/2019 editionDecode yDecode xNetwork coding(NC)7网络编码巧妙的利用了网络的拓扑结构。背后的玄机是什么呢？插段故事！乌龟过马路的故事Mr.Red和Mr.Green要过马

3、路乌龟过马路的故事Mr.Red成功过去乌龟过马路的故事Mr.Green Orz了怎么破？乌龟过马路的故事普通专家：TCP超时重传乌龟过马路的故事不愧是专家文艺范的编码专家这个时候看不惯了乌龟过马路的故事他们表示超时重传什么的太不文艺了我编码，编编编乌龟过马路的故事第二只又跪了不鸟它，继续发乌龟过马路的故事网络编码的本质是信息扩散！“嘿，哥们，够了，能解码了！”Prof.Rudolf Ahlswede德国德国University of Bielefel2019年已经去世，曾获年已经去世，曾获 IEEE香农奖章香农奖章蔡宁蔡宁 Ning Cai西安电子科技大学西安电子科技大学李硕彦李硕彦Shuo-

4、Yen Robert Li 香港中文大学香港中文大学 FIEEE“网络编码迷蝴蝶网络编码迷蝴蝶”从自此牛。从自此牛。杨伟豪杨伟豪Raymond W.Yeung香港中文大学香港中文大学 FIEEE大牛们的开山之作 2000 IEEE Transactions on Information TheoryNetwork Information Flow网络编码的理论内涵网络编码的理论内涵 点对点的最小割最大流定理点对点的最小割最大流定理:对于已知的网络流图，从发点S到收点U的流量ru的最大值小于或等于任何一个割的容量，即ru =mincut(S,u)记 Cu =mincut(S,u)网络编码在有些条

5、件下可以比传统方法更加逼近这个最大流。刚才蝴蝶网络就是个例子。网络编码带来的好处网络编码带来的好处使组播传输速率达到最小割最大流决定的网络容量的上限节省网络带宽资源消耗均衡网络负载提高网络鲁棒性几个例子几个例子网络编码的种类非常多，每种有不同的设计目标和设计方式，我们只能从几个简单的例子，窥一斑而知全豹。22Communications on Mars（ANC or PNC）ABABABA+B2022/7/2423RAIDs A B ABSingle backup=NCRedundancy in Data Storage2022/7/2424DataDisks A B ABAPerform N

6、C over an imaginary networkDataDisks A B ABABPerform NC over an imaginary network25DataDisks A B ABABABPerform NC over an imaginary network26容错的编码容错的编码如图AB、AC带宽为2，其余为1。任何一个link坏掉，source到destination总能保持2的最大流。安全的编码安全的编码哪个方案更容易被窃听？网络编码的主要应用网络编码的主要应用P2P编码无线网络编码分布式文件系统编码网络编码在网络编码在P2P中的应用中的应用网络编码在网络编码在 P2

7、PP2P文件共享中的应用文件共享中的应用P2P文件共享软件BitTorrent使用网络编码后，可提高某些方面的性能；微软公司提出Avalanche系统，可大幅度提高文件共享效率，减少因种子节点离开带来的“死档”现象。网络编码在网络编码在P2P中的应用中的应用Network Coding解决P2P文件分发网络中的什么问题？对于目标节点而言，在组装还原原始文件的时需要确保其收到了组成该文件的所有的数据包，在没有网络编码的情况下，每个数据包都具有唯一性和不可替代性，导致的问题是，目标节点即使收到冗余重复包，也可能收不到特定的某个包。网络编码使数据包可以被另外的数据包还原，使每个数据包具有平等性，减少

8、重复冗余包的概率，每个数据包所包含的内容都有很大概率是有意义的。CBABigFileA+BB+C网络编码网络编码P2P传输细节传输细节对于每个数据大段，划分为若干小段，然后在大段内进行网络编码，请求方可以同时接收多个peer的小段，直到可以解码出原来的大段。avalancheMicrosoft利用网络编码试验了文件的分发速度是直接分发的2-3倍。流媒体P2P点播，比单纯的文件分发更加复杂，有着时间上、网络带宽上和控制上的更高要求，我们可以把上面的思路拿到这里面来。可以大大减轻P2P的协同控制的难度。现在已经有了几种点播方案：DSL_NC：一种基于DSL（Dynamic Skip List，DS

9、L）overlay的网络编码P2P流媒体点播方案；BAS_DNC：一种基于缓存协助搜索（buffer-assisted search，BAS）覆盖网络的网络编码P2P流媒体点播方案；SonicVOD：一种视频分割辅助的网络编码P2P视频点播系统。UUSee视频点播系统是首个实际部署了网络编码的流媒体点播运营系统。（InfoCom10）网络编码在流媒体点播中的应用网络编码在流媒体点播中的应用随机网络编码的点播方法1.把一个媒体段分为若干块：2.随机生产编码系数（其实就是一组随机全排列）3.构造编码块4.矩阵表示编解码无线网络编码无线网络编码由于无线链路的不可靠性和物理层广播特性,应用网络编码,可

10、以解决传统路由、跨层设计等技术无法解决的问题.November 5,2019Underwater WiFi will Have a Huge Impact with an Armenian in the teamunderwater acoustic sensor network codingwifi underwaterWUWNET13 CDMA+ANC水下wifi采用限制：带宽小、延迟大。为了解决这个问题，文章在CDMA的基础上，结合ANC编码实现了新的MAC层协议。文章传输问题的环境还是广播的环境。分布式文件系统分布式文件系统E-MBR是追求修复带宽最小的“Raid”E-MBR原理原理把

11、各个储存节点建立成全连接图，计算理论最小修复带宽。传统raid和E-MBR的比较网络编码的缺陷我们刚才给出了一个安全编码的例子，网络编码真的更安全了么？在路由节点上可以编解码，会带来额外的安全隐患。网络编码的复杂性让它在某些领域很难应用，至少现在很多编码方案还只停留在papers里。网络编码的缺陷有人写了篇论文专门challenge network coding：How Practical is Network Coding?文章诟病了网络编码用于P2P文件传输费力不讨好。但是网络编码是什么？再问网络编码与其说网络编码是一类技术，倒不如说，网络编码代表了一种崭新的思维方式。如果你一一细数网络编

12、码在各个场合的编码方式，那么它更像一种千奇百怪的技术。但是如果你把网络编码当成一种思维方式，那么这些技术不过是这种思维方式的具体表现。网络编码是拓扑下某种形式的信息扩散；网络编码是在传输过程中编码。网络编码展望trends网络编码展望trends网络编码展望网络编码不单单是一类技术，它更是一种新的思维方式网络编码赋予某些传统技术新的活力。网络编码是数学和工程的对话李硕彦李硕彦网络编码深入到各个领域数学学与与工工程程的的对对话话1.Linear network coding(NC)2.Convolutional NC 3.NC theory via commutative algebra 4.C

13、onstruction of NC over cyclic networks5.Martingale of patterns 6.Computing by symmetry7.Unified algebraic theory of sorting,routing,multicasting,&concentration networks 8.Cut-through coding 9.Algebraic transform of multistage interconnection networks10.Scalable nonblocking switches and geometric int

14、uition All my 小把戏 in making a living are under this theme.李硕彦李硕彦xy=0 if x=y1 if x y试问试问:“禅师,what is NC?”神秀神秀答答:“Read this&that papers If necessary,more papers 慢慢读、慢慢想 NC 禅说from 李硕彦 渐渐渐渐就会懂.”惠能惠能答答:“Look at Butterfly network.”当场就顿悟！参考文献基础论文：基础论文：1 Network Information Flow，2 Network Coding:An Instant

15、Primer,Christina Fragouli etc.,ACM SIGCOMM Computer Communication Review,Vol.36,No.1,January 20193 网络编码迷蝴蝶，Bob Li,科學人雜誌(Scientific American,Chinese edition)，7/2019网络编码在分布式文件系统上的应用：网络编码在分布式文件系统上的应用：4 Network Coding for Distributed Storage Systems,Alexandros G.Dimakis etc.IEEE TRANSACTIONS ON INFORMAT

16、ION THEORY,VOL.56,NO.9,9/20195 NCFS:On the Practicality and Extensibility of a Network-Coding-Based Distributed File System,Yuchong Hu etc.,NetCod116 Explicit Construction of Optimal Exact Regenerating Codes for Distributed Storage,K.V.Rashmi etc.,Forty-Seventh Annual Allerton Conference,9/20097 Ena

17、bling Data Integrity Protection in Regenerating-Coding-Based Cloud Storage,Henry C.H.Chen网络编码在纠错码中的应用：网络编码在纠错码中的应用：8 Network Coding and Error Correction,Ning Cai,ITW 2019参考文献网络编码在无线网络中的应用：网络编码在无线网络中的应用：9 A Hybrid MAC Protocol with Channel-dependent Optimized Scheduling for Clustered Underwater Acous

18、tic Sensor Networks,Jithin Jagannath,WUWNet13网路编码在网路编码在P2P中的应用：中的应用：10 网络编码技术在P2P 视频点播系统中的应用，彭振声 等11 Network Coding for Large Scale Content Distribution,Christos Gkantsidis,etc.,Infocom0512 Anatomy of a P2P Content Distribution System with Network Coding,C.Gkantsidis,John Miller,and P.Rodriguez,IPTP

19、S0613 UUSee:Large-Scale Operational On-Demand Streaming with Random Network Coding,Zimu Liu etc.,Infocom10网络编码的缺陷：网络编码的缺陷：14 How Practical is Network Coding?,Mea Wang,Baochun Li,IWQoS06整体综述性资料：整体综述性资料：15 Network Coding Applications,Christina Fragouli,Emina Soljanin,Foundations and Trends in Networking Vol.2,No.2(2019)16 Network Coding:An Overview,Raymond W.Yeungs keynotes in Shenzhen 8/201917唐詩的聯想：網絡編碼及三大應用，Bob Lis keynotes in Shenzhen 8/2019