【正文】 Inter中得到普遍采用 [21。隨著 Peel39。這些問題的存在為應用層組播的研究提供了廣闊的空間。第一章中闡述了課題來源、研究目的和意義以及國內外本課題研究的現(xiàn)狀。最后第五章總結了全文以及碩士期間的研究工作，并以后工作提出了設想。但是人們普遍認為，中間節(jié)點所進行的數(shù)據(jù)處理對數(shù)據(jù)傳輸過程本身并不會帶來任何好處。由于網(wǎng)絡中被傳遞的信息本質上就是連續(xù)的比特流，是一系列抽象的代數(shù)符號，因此信息除了可以被轉發(fā)和復制之外，應該還可以進行代數(shù)運算，網(wǎng)絡編 碼技術打破了中間節(jié)點不對數(shù)據(jù)處理的限制。 假定流入節(jié)點的每個數(shù)據(jù)包的包長度均為￡比特 (較短的數(shù)據(jù)包位數(shù)不夠，在末尾添零補齊 )，如果把這工比特中每連續(xù)的 s比特映射為有限域聰中的一個元素，那么就可以把這個數(shù)據(jù)包看成一個包含∥個元素的向量。 一、編碼過程 假設一個或多個原始信源所發(fā)送的信息由療個數(shù)據(jù)包 M1，．．．， M^組成，中間節(jié)點可以對流入其中 的 n個數(shù)據(jù)包進行網(wǎng)絡編碼，生成 1個新的數(shù)據(jù)包 x=Σ：。組合運算的系數(shù) g=(gl，．．．， gn)稱為編碼向量，石稱為信息向量。假定節(jié)點收到了 m個信息向量 它對聊個信息向量再次編碼 ，生成新的信息向量。當然 m≥刀并不是充分條件，因為方程之間有可能出現(xiàn)線性相關的現(xiàn)象，即編碼向 5 量之間線性相關。對于包含一個源節(jié)點 s和￡個匯節(jié)點， V代表頂點 (Vcrticc)集合， E代表有向邊 (Edge)集合，用嘞表示邊 (f， j)∈ E的 容量 , ， F表示流經邊 (的流量，顯然對所有。 二、網(wǎng)絡編碼的優(yōu)勢 在傳統(tǒng)的組播通信中，網(wǎng)絡中的節(jié)點只能存儲轉發(fā)所收的數(shù)據(jù)包，當信源 s到不同信宿厶之間的最大流經過的路徑可能在 G的某些鏈路上形成交叉共享鏈路，進而影響共享鏈路之間節(jié)點的數(shù)據(jù)傳輸率，因此采用傳統(tǒng)的存儲轉發(fā)模式一般是 不可能達到最大流最小割定理規(guī)定的組播信息容量上限的。顯然，從 S到 RO=l， 2， 3)的最大流均為4，所以將信息從 S同時發(fā)送給羈、島和馬時的最大組播容量也是 4。相比之下，后者可以節(jié)約 10％的系統(tǒng)帶寬。圖 2． 2(a)中的每個節(jié)點均以原始格式對數(shù)據(jù)進行存儲，圖 2． 2∞中的每個節(jié)點均以網(wǎng)絡編碼后的格式對數(shù)據(jù)進行存儲，可以看出，圖 (a)中只能容忍節(jié)點 2或 3中一個失效或離開，否則系統(tǒng)中的其它節(jié)點就不能剩余節(jié)點中完整地獲取數(shù)據(jù) a、 b、 c、 d；而圈 2． 2(b)中允許任一節(jié)點失效或離 開，其它節(jié)點都能夠自適應地做出調整，重新路由，從剩余的三個節(jié)點完整地獲取數(shù)據(jù) a、 b、“ d。傳統(tǒng)的分布式內容分發(fā)或 P2P對等通信時， Peer之間傳送的是未編碼的原始數(shù)據(jù)塊 (block)，諸如 Peer節(jié)點的搜索定位方法、資源分發(fā)與調度算法優(yōu)化、網(wǎng)絡負載平衡以及數(shù)據(jù)分發(fā)路由設計等問題都是目前P2P內容分發(fā)所面臨的難題。 3)無線傳感器網(wǎng)絡數(shù)據(jù)獲取。 5)信息安全。隨著視頻點播、網(wǎng)絡電視、遠程教育等多媒體服務飛速發(fā)展，中央服務器的帶寬瓶頸問題日益凸顯，以致集中式的分發(fā)模型逐步向基于 P2P覆蓋網(wǎng)絡 (overlay work)架構的分布式結構過渡。它的主要優(yōu)點在于它的架構，它不需要改變底層網(wǎng)絡的 結構，可以快速部署所需的網(wǎng)絡功能。 圖 3． 1對 m組播 和應用層組播的數(shù)據(jù)傳輸方式進行了比較： 10 圖 3． 1 m組播和應用層組播的數(shù)據(jù)傳輸方式比較 圖 3． 1中假設 A、 B、 C、 D為四個端系統(tǒng)主機， R1， R2為路由器，箭頭方向代表數(shù)據(jù)包的發(fā)送方向。但從圖 3． 1中可以看出應用層組播存在的一些固有問題，如效率不高，多條覆蓋網(wǎng)絡上的邏輯鏈路可能經過物理網(wǎng)絡的同一鏈路；延遲大，兩 個節(jié)點之間的通訊可能要通過其它節(jié)點：同步性能差，所有節(jié)點之間很難同步接收數(shù)據(jù)；可能跨越多個節(jié)點，丟包概率增大。而數(shù)據(jù)拓撲通常是控制拓撲的子集，它用于標識組播轉發(fā)時使用的數(shù)據(jù)路徑。最短路徑樹是從源節(jié)點到所有接收節(jié)點的每條路徑上鏈路權值之和最小的組播樹。 此外，還有基于 Steiner樹的問題致力于使組播樹的總代價最小，這已經證明了是圖論中一個 NP． plete問題。例如延時、延時抖動或者它們的組合。由前一章可知，網(wǎng)絡編碼可以實現(xiàn)網(wǎng)絡的最大流傳輸。應用層組播是以端系統(tǒng)為基礎的邏輯覆蓋網(wǎng) (overlay work)，不同與以往 m層組播中的路由器節(jié)點，端系統(tǒng)可以提供更為強大的功能，如能夠對數(shù)據(jù)進行編 碼組合運算，這為網(wǎng)絡編碼在覆蓋網(wǎng)絡上的應用提供了技術支撐。但是網(wǎng)絡編碼不是萬能的，不 是所有的網(wǎng)絡組播拓撲都能使用。不相交性保證了對于發(fā)送至同一個 目的節(jié)點的不同路徑的數(shù)據(jù)之間不會存在時間上的競爭，它們之間是線性無關的。 14 這里，多條不相交的數(shù)據(jù)傳輸路徑的存在使得以往組播進行數(shù)據(jù)通信的組播樹演變成組播圖，即由多 棵組播樹的疊加而成。兩條傳輸路徑的組播拓撲圖是按以下步驟完成的： (圖 3． 3為算法流程圖 ) 步驟 1：目的節(jié)點申請加入組播組，首先從與其鄰接的節(jié)點獲取相應的鏈路狀態(tài)信息； 步驟 2：根據(jù)鏈路的當前狀態(tài)，在建立第一條數(shù)據(jù)分發(fā)路徑時，選擇能夠提供最大接入帶寬的鄰接節(jié)點作為其父節(jié)點； 步驟 3：所選定的父節(jié)點如果是組播圖中的源節(jié)點，則執(zhí)行步驟 4，否則繼續(xù)執(zhí)行步驟 2，直至完整建立 好一條通往源節(jié)點的傳輸路徑； 步驟 4：目的節(jié)點和源節(jié)點之間的傳輸路徑建立完成后，優(yōu)化更新新加入組播圖的所有路徑的鏈路狀態(tài)，包括衰減鏈路成本參數(shù)和鏈路延時參數(shù)，使得鏈路為更多的目的節(jié)點所共用： 步驟 5：根據(jù)鏈路的狀態(tài)，為同一目的節(jié)點建立第二條數(shù)據(jù)分發(fā)路徑，選擇鏈路不在第一條路徑上，并且能夠使傳輸時延達到最小的鄰接節(jié)點作為其父節(jié)點； 步驟 6：所選定的父節(jié)點如果是組播圖中的源節(jié)點，則執(zhí)行步驟 7，否則繼續(xù)執(zhí)行步驟 5，直至完整建立好一條通往源節(jié)點的傳輸路徑； 15 步驟 7：第二條傳輸路徑建立完成后，優(yōu)化更新新加入組播圖的所 有路徑的鏈路狀態(tài)，包括衰減鏈路成本參數(shù)和鏈路延時參數(shù)，使得鏈路為更多的目的節(jié)點所共用。如圖 3． 4(b)所示的兩條路徑，其中 UIO是申請加入的目的節(jié)點。圖 3． 4(d)給出了目的節(jié)點 U9和 UIO的兩條路徑，兩條細線表示的路徑是到目的節(jié)點 U9，兩條粗線表示的是到目的節(jié)點 UIO。首先假設網(wǎng)絡中節(jié)點數(shù)目發(fā)生變化，圖 3． 5(a)和圖 3． 5(b)給出了兩者間網(wǎng)絡帶寬和平均延時方面的比較。加入了網(wǎng)絡編碼的具有冗余度的組播圖同樣也獲得了較好的網(wǎng)絡帶寬，表現(xiàn)出了其優(yōu)越性。下面分別比較有單路徑樹， 2．冗余路徑組播圖和多路徑圖的性能，還主 要是網(wǎng)絡端到端吞吐量和網(wǎng)絡延時： 圖 37（ a）網(wǎng)絡平均寬帶隨網(wǎng)絡中節(jié)點數(shù)目變化 圖 37（ b）網(wǎng)絡端到端延時隨網(wǎng)絡中節(jié)點數(shù)目變化 21 圖 3． 7(a)和圖 3． 7(b)主要是通過改變網(wǎng)絡的規(guī)模來比較路徑數(shù)量不同對網(wǎng)絡性能的影響。 圖 38（ a）網(wǎng)絡平均寬帶隨網(wǎng)絡中目的節(jié)點數(shù)目變化 22 圖 38(b)網(wǎng)絡端到端延時隨目的節(jié)點數(shù)目變化 同樣，考察在相同的網(wǎng)絡拓撲規(guī)模下，目的節(jié)點加入組播所占比例不一樣對與網(wǎng)絡性能的影響。另外，如果優(yōu)化目標是求凹函數(shù)的最大值，并且同樣滿足約束條件都是凸 集，這樣的問題同樣也是凸優(yōu)化問題。 二 、格朗日對偶法 拉格朗日對偶法是凸優(yōu)化算法中一種被廣泛采用的方法?？梢酝ㄟ^求解對偶函數(shù)的方法來求解原始函數(shù)。我們可以發(fā)現(xiàn)第三章并沒有考慮到多個源節(jié)點同時存在，并且網(wǎng)絡各個節(jié)點之間可能存在的差異性。 第三節(jié) 基于網(wǎng)絡編碼的應用層組播凈效用最優(yōu)化 在提高網(wǎng)絡端到端吞吐量時，為了克服應用層組播中的帶寬瓶頸問題，我們將網(wǎng)絡編碼技術引入到組播通信組里，在瓶頸鏈路使用網(wǎng)絡編碼解決數(shù)據(jù)碰撞問 25 題，從而提出了第三章的應用層組播路由算法。對于網(wǎng)絡中的任一組播組 m，這里用硝』表示在組播組 m中，鏈路 (f， j)上發(fā)送至目的節(jié)點 t的信息流速率。 二、解決方案 對上面提出來的優(yōu)化目標，我們希望能尋找分布式的算法從而可以應用于大規(guī)模分布式網(wǎng)絡中。我們可以利用 primal— dual算法求解優(yōu)化問題 Problem(4． 11). 我們假設在網(wǎng)絡節(jié)點和鏈路上均設置相應的 processor。 第四節(jié) 仿真結果與分析 我們以圖 4． 2所示的網(wǎng)絡結構作為仿真模型，其中 S1． S3為網(wǎng)絡中的三個源節(jié)點， T1． T2為目的節(jié)點， N1N4為中間節(jié)點。從圖中可以看出，在迭代 50次以后，各個組播組的源節(jié)點可 以達到各自組播速率的穩(wěn)定值，即出度帶寬的上限。實驗結果發(fā)現(xiàn)，當步長選擇越小，迭代速率越慢，越能接近最優(yōu)值，這也是符合梯 度算法本身特性的。本文就是以分布式的應用層組播的傳輸體系為研究對象，從路由算法和網(wǎng)絡優(yōu)化等內容進行了深入的研究，主要取得了如下成果： 1)本文在分析了以往傳統(tǒng)路由算法的基礎上，提出了一種不同于傳統(tǒng)算法的基于網(wǎng)絡編碼的使用于分布式網(wǎng)絡應用層組播路由算法。應用層組播中的節(jié)點和鏈路只需要根據(jù)自身信息和鄰接節(jié)點及鏈路的狀態(tài)信息進行網(wǎng)絡狀態(tài)的更新從而實現(xiàn)網(wǎng)絡優(yōu)化。她的細心，耐心，關心是我 們完成畢業(yè)論文的基礎。 35