網(wǎng)絡(luò)編碼原理及應(yīng)用v1.ppt

網(wǎng)絡(luò)編碼迷蝴蝶,韋有富 史婷婷 李偉佳 巨鵬飛 楊明 張 楠 段鵬飛 祝凱捷 張奇龍 林恒,概要,背景 幾個例子 主要應(yīng)用 缺陷 發(fā)展前景,提到編碼，你想到什么,二戰(zhàn)時圖靈搗鼓的密碼機？ 還是喜歡玩獨輪車的香農(nóng)？ 還是實驗課上怎么都穩(wěn)定不下來的波形？ 總之，額的神哈,那網(wǎng)絡(luò)編碼，你又想到什么,網(wǎng)絡(luò)上的專用編碼？不對！ 那是什么？召喚我們的蝴蝶吧!,Figure adapted from Scientific American, Chinese 7/2007 edition,網(wǎng)絡(luò)編碼 與 蝴蝶,問題描述 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,網(wǎng)絡(luò)編碼巧妙的利用了網(wǎng)絡(luò)的拓撲結(jié)構(gòu)。背后的玄機是什么呢？ 插段故事！,烏龜過馬路的故事,Mr.Red和Mr. Green要過馬路,烏龜過馬路的故事,Mr.Red成功過去,烏龜過馬路的故事,Mr. Green Orz了怎么破？,烏龜過馬路的故事,普通專家：TCP超時重傳,烏龜過馬路的故事,不愧是專家 文藝范的編碼專家這個時候看不慣了,烏龜過馬路的故事,他們表示超時重傳什么的太不文藝了 我編碼，編編編,烏龜過馬路的故事,第二只又跪了不鳥它，繼續(xù)發(fā),烏龜過馬路的故事,網(wǎng)絡(luò)編碼的本質(zhì)是信息擴散！,“嘿，哥們，夠了，能解碼了！”,Prof. Rudolf Ahlswede 德國University of Bielefel 2010年已經(jīng)去世，曾獲 IEEE香農(nóng)獎?wù)?蔡寧 Ning Cai 西安電子科技大學(xué),李碩彥Shuo-Yen Robert Li 香港中文大學(xué) FIEEE “網(wǎng)絡(luò)編碼迷蝴蝶”從自此牛。,楊偉豪Raymond W. Yeung 香港中文大學(xué) FIEEE,大牛們的開山之作 2000 IEEE Transactions on Information Theory Network Information Flow,網(wǎng)絡(luò)編碼的理論內(nèi)涵,點對點的最小割最大流定理: 對于已知的網(wǎng)絡(luò)流圖，從發(fā)點S到收點U的流量ru的最大值小于或等于任何一個割的容量，即 ru = mincut(S,u) 記 Cu = mincut(S,u) 網(wǎng)絡(luò)編碼在有些條件下可以比傳統(tǒng)方法更加逼近這個最大流。剛才蝴蝶網(wǎng)絡(luò)就是個例子。,網(wǎng)絡(luò)編碼帶來的好處,使組播傳輸速率達到最小割最大流決定的網(wǎng)絡(luò)容量的上限 節(jié)省網(wǎng)絡(luò)帶寬資源消耗 均衡網(wǎng)絡(luò)負載 提高網(wǎng)絡(luò)魯棒性,幾個例子,網(wǎng)絡(luò)編碼的種類非常多，每種有不同的設(shè)計目標和設(shè)計方式，我們只能從幾個簡單的例子，窺一斑而知全豹。,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的最大流。,安全的編碼,哪個方案更容易被竊聽？,網(wǎng)絡(luò)編碼的主要應(yīng)用,P2P編碼 無線網(wǎng)絡(luò)編碼 分布式文件系統(tǒng)編碼,網(wǎng)絡(luò)編碼在P2P中的應(yīng)用,網(wǎng)絡(luò)編碼在 P2P文件共享中的應(yīng)用 P2P文件共享軟件BitTorrent使用網(wǎng)絡(luò)編碼后，可提高某些方面的性能； 微軟公司提出Avalanche系統(tǒng)，可大幅度提高文件共享效率，減少因種子節(jié)點離開帶來的“死檔”現(xiàn)象。,網(wǎng)絡(luò)編碼在P2P中的應(yīng)用,Network Coding解決P2P文件分發(fā)網(wǎng)絡(luò)中的什么問題？ 對于目標節(jié)點而言，在組裝還原原始文件的時需要確保其收到了組成該文件的所有的數(shù)據(jù)包，在沒有網(wǎng)絡(luò)編碼的情況下，每個數(shù)據(jù)包都具有唯一性和不可替代性，導(dǎo)致的問題是，目標節(jié)點即使收到冗余重復(fù)包，也可能收不到特定的某個包。 網(wǎng)絡(luò)編碼使數(shù)據(jù)包可以被另外的數(shù)據(jù)包還原，使每個數(shù)據(jù)包具有平等性，減少重復(fù)冗余包的概率，每個數(shù)據(jù)包所包含的內(nèi)容都有很大概率是有意義的。,C,B,A,Big File,A+B,B+C,網(wǎng)絡(luò)編碼P2P傳輸細節(jié),對于每個數(shù)據(jù)大段，劃分為若干小段，然后在大段內(nèi)進行網(wǎng)絡(luò)編碼，請求方可以同時接收多個peer的小段，直到可以解碼出原來的大段。,avalanche,Microsoft利用網(wǎng)絡(luò)編碼試驗了文件的分發(fā)速度是直接分發(fā)的2-3倍。,流媒體P2P點播，比單純的文件分發(fā)更加復(fù)雜，有著時間上、網(wǎng)絡(luò)帶寬上和控制上的更高要求，我們可以把上面的思路拿到這里面來?？梢源蟠鬁p輕P2P的協(xié)同控制的難度。 現(xiàn)在已經(jīng)有了幾種點播方案： DSL_NC：一種基于DSL（Dynamic Skip List，DSL）overlay的網(wǎng)絡(luò)編碼P2P流媒體點播方案； BAS_DNC：一種基于緩存協(xié)助搜索（buffer-assisted search，BAS）覆蓋網(wǎng)絡(luò)的網(wǎng)絡(luò)編碼P2P流媒體點播方案； SonicVOD：一種視頻分割輔助的網(wǎng)絡(luò)編碼P2P視頻點播系統(tǒng)。 UUSee視頻點播系統(tǒng)是首個實際部署了網(wǎng)絡(luò)編碼的流媒體點播運營系統(tǒng)。（InfoCom10）,網(wǎng)絡(luò)編碼在流媒體點播中的應(yīng)用,隨機網(wǎng)絡(luò)編碼的點播方法,1.把一個媒體段分為若干塊： 2.隨機生產(chǎn)編碼系數(shù)（其實就是一組隨機全排列） 3.構(gòu)造編碼塊 4.矩陣表示編解碼,無線網(wǎng)絡(luò)編碼,由于無線鏈路的不可靠性和物理層廣播特性, 應(yīng)用網(wǎng)絡(luò)編碼, 可以解決傳統(tǒng)路由、跨層設(shè)計等技術(shù)無法解決的問題.,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的基礎(chǔ)上，結(jié)合ANC編碼實現(xiàn)了新的MAC層協(xié)議。文章傳輸問題的環(huán)境還是廣播的環(huán)境。,分布式文件系統(tǒng),E-MBR是追求修復(fù)帶寬最小的“Raid”,E-MBR原理,把各個儲存節(jié)點建立成全連接圖，計算理論最小修復(fù)帶寬。,傳統(tǒng)raid和E-MBR的比較,網(wǎng)絡(luò)編碼的缺陷,我們剛才給出了一個安全編碼的例子，網(wǎng)絡(luò)編碼真的更安全了么？ 在路由節(jié)點上可以編解碼，會帶來額外的安全隱患。 網(wǎng)絡(luò)編碼的復(fù)雜性讓它在某些領(lǐng)域很難應(yīng)用，至少現(xiàn)在很多編碼方案還只停留在papers里。,網(wǎng)絡(luò)編碼的缺陷,有人寫了篇論文專門challenge network coding： How Practical is Network Coding? 文章詬病了網(wǎng)絡(luò)編碼用于P2P文件傳輸費力不討好。 但是 網(wǎng)絡(luò)編碼是什么？,再問網(wǎng)絡(luò)編碼,與其說網(wǎng)絡(luò)編碼是一類技術(shù)，倒不如說，網(wǎng)絡(luò)編碼代表了一種嶄新的思維方式。 如果你一一細數(shù)網(wǎng)絡(luò)編碼在各個場合的編碼方式，那么它更像一種千奇百怪的技術(shù)。 但是如果你把網(wǎng)絡(luò)編碼當(dāng)成一種思維方式，那么這些技術(shù)不過是這種思維方式的具體表現(xiàn)。 網(wǎng)絡(luò)編碼是拓撲下某種形式的信息擴散；網(wǎng)絡(luò)編碼是在傳輸過程中編碼。,網(wǎng)絡(luò)編碼展望trends,網(wǎng)絡(luò)編碼展望trends,網(wǎng)絡(luò)編碼展望,網(wǎng)絡(luò)編碼不單單是一類技術(shù)，它更是一種新的思維方式 網(wǎng)絡(luò)編碼賦予某些傳統(tǒng)技術(shù)新的活力。 網(wǎng)絡(luò)編碼是數(shù)學(xué)和工程的對話 李碩彥,網(wǎng)絡(luò)編碼深入到各個領(lǐng)域,數(shù),學(xué),與,工,程,的,對,話,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 小把戲 in making a living are under this theme. 李碩彥,試問: “禪師, what is NC?” 神秀答: “Read this & that papers If necessary, more papers 慢慢讀、慢慢想 ,NC 禪說 from 李碩彥,漸漸就會懂.” 惠能答: “Look at Butterfly network.” 當(dāng)場就頓悟！,參考文獻,基礎(chǔ)論文： 1 Network Information Flow， 2 Network Coding: An Instant Primer, Christina Fragouli etc., ACM SIGCOMM Computer Communication Review, Vol. 36, No. 1, January 2006 3 網(wǎng)絡(luò)編碼迷蝴蝶，Bob Li, 科學(xué)人雜誌 (Scientific American, Chinese edition)，7/2007 網(wǎng)絡(luò)編碼在分布式文件系統(tǒng)上的應(yīng)用： 4 Network Coding for Distributed Storage Systems, Alexandros G. Dimakis etc. IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 56, NO. 9, 9/2010 5 NCFS: On the Practicality and Extensibility of a Network-Coding-Based Distributed File System, Yuchong Hu etc., NetCod11 6 Explicit Construction of Optimal Exact Regenerating Codes for Distributed Storage, K. V. Rashmi etc., Forty-Seventh Annual Allerton Conference, 9/2009 7 Enabling Data Integrity Protection in Regenerating-Coding-Based Cloud Storage, Henry C. H. Chen 網(wǎng)絡(luò)編碼在糾錯碼中的應(yīng)用： 8 Network Coding and Error Correction, Ning Cai, ITW 2002,參考文獻,網(wǎng)絡(luò)編碼在無線網(wǎng)絡(luò)中的應(yīng)用： 9 A Hybrid MAC Protocol with Channel-dependent Optimized Scheduling for Clustered Underwater Acoustic Sensor Networks, Jithin Jagannath, WUWNet13 網(wǎng)路編碼在P2P中的應(yīng)用： 10 網(wǎng)絡(luò)編碼技術(shù)在P2P 視頻點播系統(tǒng)中的應(yīng)用，彭振聲 等 11 Network Coding for Large Scale Content Distribution, Christos Gkantsidis, etc., Infocom05 12 Anatomy of a P2P Content Distribution System with Network Coding, C. Gkantsidis, John Miller, and P. Rodriguez, IPTPS06 13 UUSee: Large-Scale Operational On-Demand Streaming with Random Network Coding, Zimu Liu etc., Infocom10 網(wǎng)絡(luò)編碼的缺陷： 14 How Practical is Network Coding?, Mea Wang,