【正文】 數(shù)據(jù)路由拓?fù)涞慕栴}，而源節(jié)點是以固定單一速率不間斷發(fā)送數(shù)據(jù)塊。因此如果凸優(yōu)化問題的目標(biāo)函數(shù)是一個嚴(yán)格凸函數(shù)，且存在極小點，那么它的極小點就是最小點，并且這個點是唯一的。與此同時，對于每一個目的節(jié)點而言，其網(wǎng)絡(luò)延時則是全部路經(jīng)延時的最大值，而通過仿真可以看到，對于多條路徑帶來的延時增加相對與網(wǎng)絡(luò)流量的成倍增加是較小的。 18 圖 （ a）網(wǎng)絡(luò)端到端吞吐量 圖 35（ b）網(wǎng)絡(luò)端到端延時隨網(wǎng)絡(luò)中節(jié)點數(shù)目變化 另一方面，假設(shè)在固定的網(wǎng)絡(luò)規(guī)模中，目的節(jié)點的數(shù)目發(fā)生改變，兩者間的網(wǎng)絡(luò)吞吐量和平均延時的比較于圖 3． 6(a)和圖 3． 60)給出。圖3． 4(c)所示的就是目的節(jié)點 Ull通過共用目的節(jié)點 UIO的路徑建立一條傳輸路徑，通過接入中間節(jié)點 U6建立另一條路徑。 這里建立組播拓?fù)鋱D是以在源節(jié)點和目的節(jié)點之間建立兩條傳輸路徑為例展開說明，并且兩條路徑在建立過程中分別遵循最大接入帶寬和最小傳輸時延原則。所謂不相交路徑是指對同～目的節(jié)點而言的不同路徑之間不存在共用的鏈路。 網(wǎng)絡(luò)編碼，作為一種協(xié)同工作的理念，將原先分立于物理層和網(wǎng)絡(luò)層的兩個核心概念 —— 編碼和路由有機(jī)地融為一體，通過在中間節(jié)點中進(jìn)行傳遞信息的編碼組合運算，建立起一種異于傳統(tǒng)存儲轉(zhuǎn)發(fā)的全新網(wǎng)絡(luò)信息傳輸模式。 Steiner樹問題可 以擴(kuò)展到包括其它的鏈路約束。其中在組播中最基本兩種數(shù)據(jù)轉(zhuǎn)發(fā)方式是：建立最短路徑樹和最小生成樹，常見的路由算法為： Bellman— Ford最短路徑樹算法、 Dijstra 最短路徑樹算法和 Prim最小生成樹算法。 從圖 3． 1(b)可以看到應(yīng)用層組播有以下一些優(yōu)點： 1．所有數(shù)據(jù)包都是通過單播傳輸?shù)?，無需路由器的支持，節(jié)點只需安 裝應(yīng)用層軟件即可，操作方便、易于廣泛部署； ，而節(jié)點僅需要保存該組少量其它鄰近成員的信息，可擴(kuò)展性好； 3．利用單播，可以有效地采取適合流媒體應(yīng)用特點的錯誤恢復(fù)、流量控制、擁塞控制等策略，提供端到端的服務(wù)質(zhì)量保證； 4．不但能跨越空間維，還能跨越時間維進(jìn)行數(shù)據(jù)傳輸，可犧牲同步性能來獲得更好的服務(wù)質(zhì)量保證； 5．地址可采用層次結(jié)構(gòu)，可有效地擴(kuò)大地址空間。疊加網(wǎng) (Overlay Networks)是一個位于一個或多個己知網(wǎng)絡(luò)上的獨立的虛擬網(wǎng)絡(luò)。對于鏈路被截斷等物理故障，傳統(tǒng)的解決辦法是啟用備份鏈路進(jìn)行重新路由，而對于采用網(wǎng)絡(luò)編碼的節(jié)點，改變編碼規(guī)則就可以改變其傳遞給其它節(jié)點的信息內(nèi)容，這同樣起到了重新路由的作用，而且這種網(wǎng)絡(luò)管理 方式的開銷非 常小。 1)分布式內(nèi)容存儲與分發(fā)。 采用圖 2 的存儲轉(zhuǎn)發(fā)方式，同時傳輸 2bR信息占有的鏈路帶寬總量為 10；而采用圖 2 1(d)的網(wǎng)絡(luò)編碼方式，同時傳輸 2bit信息所占有的鏈路帶寬總量為 9。如果用 max表示從源點 s到匯點f，的最大流值。我們知道，只有當(dāng)線性方程組的方程個數(shù)大于或等于未知數(shù)個數(shù) (即 m≥ n)時線性方程組才有唯一解。由于編碼運算在有限域中進(jìn)行，因而 x所占據(jù)的存儲空間大小與膨 7所占大小完全相同。但相比非線性編碼，線性網(wǎng)絡(luò)編碼的編碼和解碼都相對簡單，這里以目前被普遍采用 的隨機(jī)線性網(wǎng)絡(luò)編碼為例，來說明網(wǎng)絡(luò)編碼的原理。在許多實際應(yīng)用中，人們?yōu)榱诵畔⒎治?、信息安全以及交換的目的，總是要在 中間節(jié)點進(jìn)行某種形式的數(shù)據(jù)處理。 第三節(jié) 論文的主要研究內(nèi)容 本論文是作者攻讀碩士學(xué)位期間承擔(dān)課題的工作總結(jié)。由于對網(wǎng)絡(luò)本身的改變很少，應(yīng)用層組播具有很好的靈活性。采用單播技術(shù)構(gòu)建的傳統(tǒng)網(wǎng)絡(luò)已經(jīng)無法滿足新興寬帶網(wǎng)絡(luò)應(yīng)用在帶寬和網(wǎng)絡(luò)服務(wù)質(zhì)量方面的要求，隨之而來的是網(wǎng)絡(luò)延時增加、數(shù)據(jù)丟失 等等問題。 摘 要 隨著通信網(wǎng)絡(luò)技術(shù)的發(fā)展和多媒體技術(shù)的廣泛運用，網(wǎng)絡(luò)資源緊張和分配不合理的問題越來越突出。 于是，組播通信方式被提出，旨在改善現(xiàn)有網(wǎng)絡(luò)中存在的一些網(wǎng)絡(luò)資源緊張問題，提高網(wǎng)絡(luò)的服務(wù)質(zhì)量 QoS[11。隨著 Peel39。第一章中闡述了課題來源、研究目的和意義以及國內(nèi)外本課題研究的現(xiàn)狀。但是人們普遍認(rèn)為，中間節(jié)點所進(jìn)行的數(shù)據(jù)處理對數(shù)據(jù)傳輸過程本身并不會帶來任何好處。 假定流入節(jié)點的每個數(shù)據(jù)包的包長度均為￡比特 (較短的數(shù)據(jù)包位數(shù)不夠，在末尾添零補(bǔ)齊 )，如果把這工比特中每連續(xù)的 s比特映射為有限域聰中的一個元素，那么就可以把這個數(shù)據(jù)包看成一個包含∥個元素的向量。組合運算的系數(shù) g=(gl，．．．， gn)稱為編碼向量，石稱為信息向量。當(dāng)然 m≥刀并不是充分條件，因為方程之間有可能出現(xiàn)線性相關(guān)的現(xiàn)象，即編碼向 5 量之間線性相關(guān)。 二、網(wǎng)絡(luò)編碼的優(yōu)勢 在傳統(tǒng)的組播通信中，網(wǎng)絡(luò)中的節(jié)點只能存儲轉(zhuǎn)發(fā)所收的數(shù)據(jù)包，當(dāng)信源 s到不同信宿厶之間的最大流經(jīng)過的路徑可能在 G的某些鏈路上形成交叉共享鏈路，進(jìn)而影響共享鏈路之間節(jié)點的數(shù)據(jù)傳輸率，因此采用傳統(tǒng)的存儲轉(zhuǎn)發(fā)模式一般是 不可能達(dá)到最大流最小割定理規(guī)定的組播信息容量上限的。相比之下，后者可以節(jié)約 10％的系統(tǒng)帶寬。傳統(tǒng)的分布式內(nèi)容分發(fā)或 P2P對等通信時， Peer之間傳送的是未編碼的原始數(shù)據(jù)塊 (block)，諸如 Peer節(jié)點的搜索定位方法、資源分發(fā)與調(diào)度算法優(yōu)化、網(wǎng)絡(luò)負(fù)載平衡以及數(shù)據(jù)分發(fā)路由設(shè)計等問題都是目前P2P內(nèi)容分發(fā)所面臨的難題。 5)信息安全。它的主要優(yōu)點在于它的架構(gòu)，它不需要改變底層網(wǎng)絡(luò)的 結(jié)構(gòu)，可以快速部署所需的網(wǎng)絡(luò)功能。但從圖 3． 1中可以看出應(yīng)用層組播存在的一些固有問題，如效率不高，多條覆蓋網(wǎng)絡(luò)上的邏輯鏈路可能經(jīng)過物理網(wǎng)絡(luò)的同一鏈路；延遲大，兩 個節(jié)點之間的通訊可能要通過其它節(jié)點：同步性能差，所有節(jié)點之間很難同步接收數(shù)據(jù)；可能跨越多個節(jié)點，丟包概率增大。最短路徑樹是從源節(jié)點到所有接收節(jié)點的每條路徑上鏈路權(quán)值之和最小的組播樹。例如延時、延時抖動或者它們的組合。應(yīng)用層組播是以端系統(tǒng)為基礎(chǔ)的邏輯覆蓋網(wǎng) (overlay work)，不同與以往 m層組播中的路由器節(jié)點，端系統(tǒng)可以提供更為強(qiáng)大的功能，如能夠?qū)?shù)據(jù)進(jìn)行編 碼組合運算，這為網(wǎng)絡(luò)編碼在覆蓋網(wǎng)絡(luò)上的應(yīng)用提供了技術(shù)支撐。不相交性保證了對于發(fā)送至同一個 目的節(jié)點的不同路徑的數(shù)據(jù)之間不會存在時間上的競爭，它們之間是線性無關(guān)的。兩條傳輸路徑的組播拓?fù)鋱D是按以下步驟完成的： (圖 3． 3為算法流程圖 ) 步驟 1：目的節(jié)點申請加入組播組，首先從與其鄰接的節(jié)點獲取相應(yīng)的鏈路狀態(tài)信息； 步驟 2：根據(jù)鏈路的當(dāng)前狀態(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ā)路徑，選擇鏈路不在第一條路徑上，并且能夠使傳輸時延達(dá)到最小的鄰接節(jié)點作為其父節(jié)點； 步驟 6：所選定的父節(jié)點如果是組播圖中的源節(jié)點，則執(zhí)行步驟 7，否則繼續(xù)執(zhí)行步驟 5，直至完整建立好一條通往源節(jié)點的傳輸路徑； 15 步驟 7：第二條傳輸路徑建立完成后，優(yōu)化更新新加入組播圖的所 有路徑的鏈路狀態(tài)，包括衰減鏈路成本參數(shù)和鏈路延時參數(shù)，使得鏈路為更多的目的節(jié)點所共用。圖 3． 4(d)給出了目的節(jié)點 U9和 UIO的兩條路徑，兩條細(xì)線表示的路徑是到目的節(jié)點 U9，兩條粗線表示的是到目的節(jié)點 UIO。加入了網(wǎng)絡(luò)編碼的具有冗余度的組播圖同樣也獲得了較好的網(wǎng)絡(luò)帶寬，表現(xiàn)出了其優(yōu)越性。 圖 38（ a）網(wǎng)絡(luò)平均寬帶隨網(wǎng)絡(luò)中目的節(jié)點數(shù)目變化 22 圖 38(b)網(wǎng)絡(luò)端到端延時隨目的節(jié)點數(shù)目變化 同樣，考察在相同的網(wǎng)絡(luò)拓?fù)湟?guī)模下，目的節(jié)點加入組播所占比例不一樣對與網(wǎng)絡(luò)性能的影響。 二 、格朗日對偶法 拉格朗日對偶法是凸優(yōu)化算法中一種被廣泛采用的方法。我們可以發(fā)現(xiàn)第三章并沒有考慮到多個源節(jié)點同時存在，并且網(wǎng)絡(luò)各個節(jié)點之間可能存在的差異性。對于網(wǎng)絡(luò)中的任一組播組 m，這里用硝』表示在組播組 m中，鏈路 (f， j)上發(fā)送至目的節(jié)點 t的信息流速率。我們可以利用 primal— dual算法求解優(yōu)化問題 Problem(4． 11). 我們假設(shè)在網(wǎng)絡(luò)節(jié)點和鏈路上均設(shè)置相應(yīng)的 processor。從圖中可以看出，在迭代 50次以后，各個組播組的源節(jié)點可 以達(dá)到各自組播速率的穩(wěn)定值，即出度帶寬的上限。本文就是以分布式的應(yīng)用層組播的傳輸體系為研究對象，從路由算法和網(wǎng)絡(luò)優(yōu)化等內(nèi)容進(jìn)行了深入的研究，主要取得了如下成果： 1)本文在分析了以往傳統(tǒng)路由算法的基礎(chǔ)上，提出了一種不同于傳統(tǒng)算法的基于網(wǎng)絡(luò)編碼的使用于分布式網(wǎng)絡(luò)應(yīng)用層組播路由算法。她的細(xì)心，耐心，關(guān)心是我 們完成畢業(yè)論文的基礎(chǔ)。她時常給我們指出錯誤并指導(dǎo)我們改正。利用網(wǎng)絡(luò)編碼技術(shù)結(jié)合多路徑傳輸，從而提高了網(wǎng)絡(luò)端到端的吞吐量和帶寬利用； 2)考慮到在組播圖建立過程中，對于已經(jīng)存在組播圖的端系統(tǒng)，其能力不同于以為 IP組播路由器，在算法中，新申請加入的節(jié)點可以與組播圖中的端系統(tǒng)通