【正文】 35 參考文獻(xiàn) [1] 陳波 .《應(yīng)用層組播的研究與算法實(shí)現(xiàn)》 .計(jì)算機(jī)工程與設(shè)計(jì)， 20xx． [2]．李瑁晟 .《應(yīng)用層組播綜述》 .計(jì)算機(jī)應(yīng)用研究， 20xx． [3]．徐恪 .《高等計(jì)算機(jī)網(wǎng)絡(luò) —— 體系結(jié)構(gòu)、協(xié)議機(jī)制、算法設(shè)計(jì)與路由器技術(shù)》，機(jī)械工業(yè)出版社， 20xx． [4]．謝政，李建平，《網(wǎng)絡(luò)算法與復(fù)雜性理論》，國(guó)防科技大學(xué)出版社， 1995． [5]．李偉，沈長(zhǎng)寧，應(yīng)用層組播協(xié)議的研究，計(jì)算機(jī)工程與應(yīng)用， 20xx． [6]．董慶陽(yáng)，李毓麟，《組播路由綜合優(yōu)化及其算法》，計(jì)算機(jī)學(xué)報(bào)， 20xx． [7]．甘應(yīng)愛 .《運(yùn)籌學(xué)》，清華大學(xué)出版社， 20xx． [8]．鄧先禮 .《最優(yōu)化技術(shù)》，重慶大學(xué)出版社， 1998． [9]．張忠楨 .《凸規(guī)劃》，武漢大學(xué)出版社， 20xx． 。她時(shí)常給我們指出錯(cuò)誤并指導(dǎo)我們改正。她的細(xì)心，耐心，關(guān)心是我 們完成畢業(yè)論文的基礎(chǔ)。 在這里我要衷心感謝所有在設(shè)計(jì)過(guò)程中給我提供幫助的老師和同學(xué) 首先要感謝鄭老師，在完成畢業(yè)論文的這段時(shí)間里鄭老師給出了許多寶貴的意見和幫助。應(yīng)用層組播中的節(jié)點(diǎn)和鏈路只需要根據(jù)自身信息和鄰接節(jié)點(diǎn)及鏈路的狀態(tài)信息進(jìn)行網(wǎng)絡(luò)狀態(tài)的更新從而實(shí)現(xiàn)網(wǎng)絡(luò)優(yōu)化。利用網(wǎng)絡(luò)編碼技術(shù)結(jié)合多路徑傳輸，從而提高了網(wǎng)絡(luò)端到端的吞吐量和帶寬利用； 2)考慮到在組播圖建立過(guò)程中，對(duì)于已經(jīng)存在組播圖的端系統(tǒng)，其能力不同于以為 IP組播路由器，在算法中，新申請(qǐng)加入的節(jié)點(diǎn)可以與組播圖中的端系統(tǒng)通信獲得數(shù)據(jù)，進(jìn)一步提高網(wǎng)絡(luò)資源利用，達(dá)到提高網(wǎng)絡(luò)容量的目的： 3)考慮到啟發(fā)式算法不能達(dá)到網(wǎng)絡(luò)使用的最優(yōu)，而傳統(tǒng)的優(yōu)化算法集中式的優(yōu)化方式達(dá)到網(wǎng)絡(luò)最優(yōu)的同時(shí)，需要掌握網(wǎng)絡(luò)的全局狀態(tài)信息，很難應(yīng)用于大規(guī)模 P2P的分布式網(wǎng)絡(luò)中。本文就是以分布式的應(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)用層組播路由算法。圖 4． 6和圖 4． 7分別給出了迭代步長(zhǎng)stepsizeO． 01和可變步長(zhǎng)下的各個(gè)組播源節(jié)點(diǎn)發(fā)送速率的變化。實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，當(dāng)步長(zhǎng)選擇越小，迭代速率越慢，越能接近最優(yōu)值，這也是符合梯 度算法本身特性的。 圖 44組播源節(jié)點(diǎn)速率變化圖 (固定步長(zhǎng) stepsize==O． 01) 圖 4． 5給出了迭代過(guò)程中目標(biāo)函數(shù)值的變化情況，在源節(jié)點(diǎn)速率穩(wěn)定以后，目標(biāo)函數(shù)值也隨之穩(wěn)定得到。從圖中可以看出，在迭代 50次以后，各個(gè)組播組的源節(jié)點(diǎn)可 以達(dá)到各自組播速率的穩(wěn)定值，即出度帶寬的上限?？梢詫D 4． 2所示的網(wǎng)絡(luò)拓?fù)湟暈閳D 4． 3中的三個(gè)組播組，每一個(gè)組播中有一個(gè)源節(jié)點(diǎn)以及若干中間節(jié)點(diǎn)和目的節(jié)點(diǎn) (組播子網(wǎng) )。 第四節(jié) 仿真結(jié)果與分析 我們以圖 4． 2所示的網(wǎng)絡(luò)結(jié)構(gòu)作為仿真模型，其中 S1． S3為網(wǎng)絡(luò)中的三個(gè)源節(jié)點(diǎn)， T1． T2為目的節(jié)點(diǎn)， N1N4為中間節(jié)點(diǎn)。 28 圖 41算法流程圖 在分布式網(wǎng)絡(luò)中，我們假設(shè)的節(jié)點(diǎn)和鏈路 processor則是按照以下方式對(duì)于接收的數(shù)據(jù)進(jìn)行處理和更新的： 從上面的算法，我們可以看出利用次梯度迭代算法對(duì)我們的目標(biāo)函數(shù)求解，是～個(gè)分布式的，不需要全局信息，能很好的使用與大型網(wǎng)絡(luò)，并且由于源節(jié)點(diǎn)可以提供可伸縮的數(shù)據(jù)流速率，可以應(yīng)用于大規(guī)模異構(gòu)網(wǎng)絡(luò)中。我們可以利用 primal— dual算法求解優(yōu)化問(wèn)題 Problem(4． 11). 我們假設(shè)在網(wǎng)絡(luò)節(jié)點(diǎn)和鏈路上均設(shè)置相應(yīng)的 processor。對(duì)于一個(gè)凸的目標(biāo)函 26 數(shù)在一個(gè)線性約束集下，根據(jù)凸函數(shù)最大化問(wèn)題我們可以知道該最優(yōu)化問(wèn)題存在唯一的最優(yōu)解。 二、解決方案 對(duì)上面提出來(lái)的優(yōu)化目標(biāo)，我們希望能尋找分布式的算法從而可以應(yīng)用于大規(guī)模分布式網(wǎng)絡(luò)中。網(wǎng)絡(luò)流平衡約束條件和鏈路帶寬容量約束條件分別由式 (4． 9． 2)和式 (4． 94)來(lái)表示。對(duì)于網(wǎng)絡(luò)中的任一組播組 m，這里用硝』表示在組播組 m中，鏈路 (f， j)上發(fā)送至目的節(jié)點(diǎn) t的信息流速率。 一、最優(yōu)化問(wèn)題闡述 在進(jìn)行信息流組播傳輸時(shí)，我們的目標(biāo)是希望最大化每一個(gè)組播組源節(jié)點(diǎn)的效用，但同時(shí)要以合理的速率傳輸盡可能多的信息。 第三節(jié) 基于網(wǎng)絡(luò)編碼的應(yīng)用層組播凈效用最優(yōu)化 在提高網(wǎng)絡(luò)端到端吞吐量時(shí)，為了克服應(yīng)用層組播中的帶寬瓶頸問(wèn)題，我們將網(wǎng)絡(luò)編碼技術(shù)引入到組播通信組里，在瓶頸鏈路使用網(wǎng)絡(luò)編碼解決數(shù)據(jù)碰撞問(wèn) 25 題，從而提出了第三章的應(yīng)用層組播路由算法。當(dāng)源節(jié)點(diǎn)以最小的最大流進(jìn)行數(shù)據(jù)傳輸?shù)脑?，?shì)必很多目的節(jié)點(diǎn)的資源會(huì)被浪費(fèi)。我們可以發(fā)現(xiàn)第三章并沒有考慮到多個(gè)源節(jié)點(diǎn)同時(shí)存在，并且網(wǎng)絡(luò)各個(gè)節(jié)點(diǎn)之間可能存在的差異性。但是由于網(wǎng)絡(luò)中節(jié)點(diǎn)之間存在的差異，以及分布式網(wǎng)絡(luò)中多個(gè)數(shù)據(jù)源節(jié)點(diǎn)的存在使得網(wǎng)絡(luò)鏈路速率的分配和網(wǎng)絡(luò)傳輸成本之間的矛盾越來(lái)越明顯?？梢酝ㄟ^(guò)求解對(duì)偶函數(shù)的方法來(lái)求解原始函數(shù)。于是，引入對(duì)偶變量允∈ R”和 y∈ R7釋放不等式約束和等式約束，可以得到下面的拉格朗日函數(shù)： 拉格朗日乘子五和匕被稱為對(duì)偶變量。 二 、格朗日對(duì)偶法 拉格朗日對(duì)偶法是凸優(yōu)化算法中一種被廣泛采用的方法。這是由于凸函數(shù)的極值點(diǎn)自身具有良好的性質(zhì)，即凸函數(shù)在其定義域上的任一極點(diǎn)都是其在定義域上的全局最優(yōu)點(diǎn)，且極值點(diǎn)的集合也是凸集。另外，如果優(yōu)化目標(biāo)是求凹函數(shù)的最大值，并且同樣滿足約束條件都是凸 集，這樣的問(wèn)題同樣也是凸優(yōu)化問(wèn)題。從圖 3． 8(a)和圖 3． 8(b)，同樣可以發(fā)現(xiàn)多路徑的方式在增加少量延時(shí)的代價(jià)下，大大提高了整個(gè)網(wǎng)絡(luò)的數(shù)據(jù)流量，從而提高了網(wǎng)絡(luò)服務(wù)質(zhì)量，增加了網(wǎng)絡(luò)帶寬。 圖 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ò)性能的影響。在傳輸大量數(shù)據(jù)的時(shí)候，每一個(gè)目的節(jié)點(diǎn)使用多路徑算法找出能逼近最大流的多 條路徑同時(shí)進(jìn)行傳輸，結(jié)合網(wǎng)絡(luò)編碼技術(shù)使得每一個(gè)目的節(jié)點(diǎn)可以獨(dú)立享用整個(gè)網(wǎng)絡(luò)資源，從而大大提高了網(wǎng)絡(luò)的吞吐量。下面分別比較有單路徑樹， 2．冗余路徑組播圖和多路徑圖的性能，還主 要是網(wǎng)絡(luò)端到端吞吐量和網(wǎng)絡(luò)延時(shí)： 圖 37（ a）網(wǎng)絡(luò)平均寬帶隨網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目變化 圖 37（ b）網(wǎng)絡(luò)端到端延時(shí)隨網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目變化 21 圖 3． 7(a)和圖 3． 7(b)主要是通過(guò)改變網(wǎng)絡(luò)的規(guī)模來(lái)比較路徑數(shù)量不同對(duì)網(wǎng)絡(luò)性能的影響。然而在建立多條傳輸路徑后，隨之而來(lái)的網(wǎng)絡(luò)延時(shí)問(wèn)題將會(huì)被擴(kuò)大，下面的仿真給出了目的節(jié)點(diǎn)在盡可能多建立到源節(jié)點(diǎn)的路徑情況下形成的組播圖與只建立兩條路傳輸路徑 (即冗余度為 2)的組播圖以及單路徑組播樹之間的性能比較。加入了網(wǎng)絡(luò)編碼的具有冗余度的組播圖同樣也獲得了較好的網(wǎng)絡(luò)帶寬，表現(xiàn)出了其優(yōu)越性?？紤]到網(wǎng)絡(luò)帶寬的有效增加，新增加的延時(shí)可以忽略。首先假設(shè)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目發(fā)生變化，圖 3． 5(a)和圖 3． 5(b)給出了兩者間網(wǎng)絡(luò)帶寬和平均延時(shí)方面的比較。 17 圖 具體圖例說(shuō)明 第三節(jié) 實(shí)驗(yàn)仿真和結(jié)果分析 考慮到 DDSP(目的驅(qū)動(dòng)的最短路徑樹算法 )[361作為一種基本的目的驅(qū)動(dòng)型組播路由樹算法，這里選它是被用來(lái)做算法比較。圖 3． 4(d)給出了目的節(jié)點(diǎn) U9和 UIO的兩條路徑，兩條細(xì)線表示的路徑是到目的節(jié)點(diǎn) U9，兩條粗線表示的是到目的節(jié)點(diǎn) UIO。因此，對(duì)于新申請(qǐng)加入的目的節(jié)點(diǎn)，它既可以通過(guò)共用組播圖中的其它目的節(jié)點(diǎn)，也可以通過(guò)接入與其鄰接的中間節(jié)點(diǎn)來(lái)加入組播拓?fù)鋱D。如圖 3． 4(b)所示的兩條路徑，其中 UIO是申請(qǐng)加入的目的節(jié)點(diǎn)。圖 3． 4(a)表示的是數(shù)據(jù)分組在源節(jié)點(diǎn)處被采集，初始化時(shí)，組播拓?fù)鋱D中只有源節(jié)點(diǎn)，其他目的節(jié)點(diǎ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)化更新新加入組播圖的所 有