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