基于網絡編碼的應用層組波路由優化方案研究畢業設計(編輯修改稿)

　

【文章內容簡介】 衡以及數據分發路由設計等問題都是目前P2P內容分發所面臨的難題。而在 Peer之間傳輸經過網絡編碼的數據塊能夠有效解決甚至避免這些問題。 2)應用層組播。 P2P技術與覆蓋網絡 (overlay work)的發展，將組播功能從 P層擴展到了應用層，在 P2P應用層組播系統中， Peer節點對流經的數據除了進行存儲轉發外，如果 還可以進行額外的網絡編碼處理，將可以在很大程度上改善應用層組播性能，提高覆蓋網絡數據吞吐能力。 3)無線傳感器網絡數據獲取。在無線傳感器網絡中，傳感器節點的數據存儲能力十分有限，如何將這些節點采集的信息在最小代價、最小能耗、最大容量等約束下發送給存儲節點是當前網絡編 8 碼在無線通信領域的一個新課題。 4)網絡管理。對于鏈路被截斷等物理故障，傳統的解決辦法是啟用備份鏈路進行重新路由，而對于采用網絡編碼的節點，改變編碼規則就可以改變其傳遞給其它節點的信息內容，這同樣起到了重新路由的作用，而且這種網絡管理 方式的開銷非 常小。 5)信息安全。攻擊者惡意篡改網絡上傳輸的數據內容將直接影響接收端的信息接收，這是目前計算機通信網的一個潛在隱患。采用隨機網絡編碼技術，攻擊者對接收端收到的其它編碼數據無法進行預知和控制，數據篡改的影響可以降至最低。 9 第三章 一種基于網絡編碼的應用層組播路由算法 第一節 應用層組播 一、應用層組播的提出 互聯網上的大規模媒體存儲與發布普遍是基于傳統的客戶機／服務器 (C／ S)系統架構，這種集中式的分發模型容易造成中央服務器的過量負載，直接導致網絡吞吐量的下降，并且一旦中央服務器出現故障將直接導致整個傳 輸體系癱瘓。隨著視頻點播、網絡電視、遠程教育等多媒體服務飛速發展，中央服務器的帶寬瓶頸問題日益凸顯，以致集中式的分發模型逐步向基于 P2P覆蓋網絡 (overlay work)架構的分布式結構過渡。 IP層組播是面向組通信應用的，被認為是大規模數據分發的最佳方法。然而口組播增加了網絡層的復雜性，而且需要對現有網絡的底層設備進行巨大改動，因此至今口層組播仍然無法廣泛部署。疊加網 (Overlay Networks)是一個位于一個或多個己知網絡上的獨立的虛擬網絡。它的主要優點在于它的架構，它不需要改變底層網絡的 結構，可以快速部署所需的網絡功能。如果在疊加網的基礎上實現組播，可以把組播實現提高到應用層。端系統實現組播業務的思想是將組播作為一種疊加的業務，實現為應用層的服務，由此構成了應用層組播 (application layer multicast) 應用層組播是在疊加在 m層之上的用于實現組播業務邏輯的功能性網絡，應用層組播網絡中的節點是由組播中的成員主機構成的，并由它們完成數據路由、復制和轉發功能。因為不再依靠網絡層路由器來實現，所以不需要任何網絡底層架構的改變，只需改變端系統，便于實現和推廣。 圖 3． 1對 m組播 和應用層組播的數據傳輸方式進行了比較： 10 圖 3． 1 m組播和應用層組播的數據傳輸方式比較 圖 3． 1中假設 A、 B、 C、 D為四個端系統主機， R1， R2為路由器，箭頭方向代表數據包的發送方向。圖 3． 1(a)為 IP組播， A為網絡中的源節點，數據包從 A發到 R1，再由 R1轉發給 B和 R2， R2再將收到的數據包轉發給 C和 D。圖 3． 1(b)為應用層組播， A發送兩份相同的數據包分別給 B和 C，再由 C復制一份給 D。 從圖 3． 1(b)可以看到應用層組播有以下一些優點： 1．所有數據包都是通過單播傳輸的，無需路由器的支持，節點只需安 裝應用層軟件即可，操作方便、易于廣泛部署； ，而節點僅需要保存該組少量其它鄰近成員的信息，可擴展性好； 3．利用單播，可以有效地采取適合流媒體應用特點的錯誤恢復、流量控制、擁塞控制等策略，提供端到端的服務質量保證； 4．不但能跨越空間維，還能跨越時間維進行數據傳輸，可犧牲同步性能來獲得更好的服務質量保證； 5．地址可采用層次結構，可有效地擴大地址空間。但從圖 3． 1中可以看出應用層組播存在的一些固有問題，如效率不高，多條覆蓋網絡上的邏輯鏈路可能經過物理網絡的同一鏈路；延遲大，兩 個節點之間的通訊可能要通過其它節點：同步性能差，所有節點之間很難同步接收數據；可能跨越多個節點，丟包概率增大。應用層組播的效率比 P組播的效率要低，因為不可避免的會有組播路徑重復的經過同一條底層鏈路，也就必然帶來冗余的流量，例如在圖 3． 1(b)中 (A， R1)和 (R2， C)這兩條鏈路上有兩個相同的數據包重復經過同一條底層鏈路，而圖3． 1(a)的口組播則只有一次。另外，兩個端系統之間的通信，可能要通過中間 11 其他端系統的轉發來實現，這也不可避免的造成兩個通信節點之間延時的增加。 二 應用層組播路由協議 應用層組播協議 通常都按照兩個拓撲結構組織組成員，一個是控制拓撲，一個是數據拓撲，控制拓撲的組成員周期性地交互刷新消息以相互標識身份并從節點失效中恢復。而數據拓撲通常是控制拓撲的子集，它用于標識組播轉發時使用的數據路徑。數據拓撲作為應用層組播協議的重要組成部分，即組播中文件數據的如何路由是本文討論的重點。一般來說，組播組用于標識組播轉發時用的數據路徑通常是一棵組播樹。其中在組播中最基本兩種數據轉發方式是：建立最短路徑樹和最小生成樹，常見的路由算法為： Bellman— Ford最短路徑樹算法、 Dijstra 最短路徑樹算法和 Prim最小生成樹算法。最短路徑樹是從源節點到所有接收節點的每條路徑上鏈路權值之和最小的組播樹。如果所有的鏈路的權值都表 1，則為最小跳樹。如果權值代表鏈路延時，則為最小時延樹。最小生成樹是指覆蓋所有組成員且權值最小的組播樹。 此外，還有基于 Steiner樹的問題致力于使組播樹的總代價最小，這已經證明了是圖論中一個 NP． plete問題。如果組播樹包含了樹中所有節點， Stoner樹問題轉化為最小生成樹問題。一般通過啟發式算法求解，典型的啟發式算法有：MST、 RS、 KMB[31， 321。 Steiner樹問題可 以擴展到包括其它的鏈路約束。例如延時、延時抖動或者它們的組合。通常這些問題是 NP． Complete的，所以也需要采用啟發式算法解決。 第二節 基于網絡編碼的應用層組播路由算法 在日常生活中，我們經常要使用到比較大規模的通信網絡，我們都希望通信網絡能為我們提供更為安全、快速的網絡服務。于是我們提出了實現在已有通信網絡中達到最大數據流的目標。由前一章可知，網絡編碼可以實現網絡的最大流傳輸。網絡信息理論的研究指出：在組播通信中，每個接收節點可以以網絡拓撲中信源發送點與信宿接收點之間的最大流容量進行信息傳遞。然而， 從信源到不同信宿之間的最大流經過的傳輸路徑可能在網絡拓撲的鏈路上形成交叉共享鏈 12 路，因此采用傳統的存儲轉發模式即 P組播的方式，無法達到最大流最小割的理論上限。 網絡編碼，作為一種協同工作的理念，將原先分立于物理層和網絡層的兩個核心概念 —— 編碼和路由有機地融為一體，通過在中間節點中進行傳遞信息的編碼組合運算，建立起一種異于傳統存儲轉發的全新網絡信息傳輸模式。應用層組播是以端系統為基礎的邏輯覆蓋網 (overlay work)，不同與以往 m層組播中的路由器節點，端系統可以提供更為強大的功能，如能夠對數據進行編 碼組合運算，這為網絡編碼在覆蓋網絡上的應用提供了技術支撐。 本節的主要內容就是建立一種基于網絡編碼的啟發式應用層組播路由算法，目的在于利用網絡編碼技術在分布式網絡中建立數據分發拓撲使得網絡傳輸容量趨于組播容量上限。在分布式拓撲中運用隨機線性網絡編碼技術，即中間節點對發往不同目的節點的組播數據進行編碼組合后再轉發，以避開數據流對鏈路的競爭沖突，提高組播通信的吞吐量。 一、冗余路徑 考慮到網絡編碼在提高網絡的吞吐量方面的優點，為了進一步改善應用層組播的性能，從而我們引入了網絡編碼技術。但是網絡編碼不是萬能的，不 是所有的網絡組播拓撲都能使用。應用層組播要結合網絡編碼技術，在路由選擇方面必須滿足兩個條件： (1)網絡中存在冗余的路徑； (2)具有相同目的節點的路徑之間不能存在共用的路徑。 13 圖 不相交的冗余路徑 (對于 Tl而言， S． U1． T1和 SU2． U3U4T1分別是 S． T1的兩路不相交路徑 ) 圖 3． 2我們可以看到對于網絡中的目的節點 T1存在兩條不相交的路徑通向源節點 S，因此目的節點能同時收到多路獨立數據流。所謂不相交路徑是指對同～目的節點而言的不同路徑之間不存在共用的鏈路。不相交性保證了對于發送至同一個 目的節點的不同路徑的數據之間不會存在時間上的競爭，它們之間是線性無關的。此時，對于不同目的節點的路徑之間必然存在鏈路的公用問題而產生的瓶頸鏈路，網絡編碼的引入可以很好的解決瓶頸鏈路的問題。圖 3． 2中，鏈路 m3，U4)就是目的節點 T1和 T2之間的瓶頸鏈路，在節點 U3進行網絡編碼就可以實現網絡的最大流傳輸，達到網絡的最大容量 2。 (假設定義網絡中鏈路的帶寬均為 l，由最大流最小割定理可以算的圖 3． 2所示網絡結構的最大流為 2)。 14 這里，多條不相交的數據傳輸路徑的存在使得以往組播