【導(dǎo)讀】合理的問(wèn)題越來(lái)越突出。在P組播無(wú)法被全網(wǎng)范圍內(nèi)部署利用的情況下，基于端。系統(tǒng)的應(yīng)用層組播應(yīng)運(yùn)而生。與傳統(tǒng)路由節(jié)點(diǎn)只能對(duì)數(shù)據(jù)進(jìn)行復(fù)制和轉(zhuǎn)發(fā)不同，應(yīng)用層組播中的端系統(tǒng)可以對(duì)接收到的數(shù)據(jù)進(jìn)行運(yùn)算操作。

　　

【正文】 大流根據(jù)網(wǎng)絡(luò)流理論可知是網(wǎng)絡(luò)中各目的節(jié)點(diǎn)最大流的最小值。當(dāng)源節(jié)點(diǎn)以最小的最大流進(jìn)行數(shù)據(jù)傳輸?shù)脑挘瑒?shì)必很多目的節(jié)點(diǎn)的資源會(huì)被浪費(fèi)。如何合理分配多個(gè)源節(jié)點(diǎn)發(fā)送速率以及每條鏈路上的具體流量是本節(jié)討論的重點(diǎn)。 第三節(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)用層組播路由算法。本節(jié)在此基礎(chǔ)上 考慮如何網(wǎng)絡(luò)優(yōu)化，即在網(wǎng)絡(luò)容量的約束下確定各源節(jié)點(diǎn)的發(fā)送速率和每條鏈路上的流量大小，使得整個(gè)網(wǎng)絡(luò)的源節(jié)點(diǎn)效用最大而流量代價(jià)達(dá)到最優(yōu)。 一、最優(yōu)化問(wèn)題闡述 在進(jìn)行信息流組播傳輸時(shí)，我們的目標(biāo)是希望最大化每一個(gè)組播組源節(jié)點(diǎn)的效用，但同時(shí)要以合理的速率傳輸盡可能多的信息。所謂合理即是要考慮整個(gè)網(wǎng)絡(luò)中所有目的節(jié)點(diǎn)的接收能力，并且整個(gè)網(wǎng)絡(luò)的傳輸代價(jià)要盡可能的小。對(duì)于網(wǎng)絡(luò)中的任一組播組 m，這里用硝』表示在組播組 m中，鏈路 (f， j)上發(fā)送至目的節(jié)點(diǎn) t的信息流速率。于是，我們得到下面的最優(yōu)化目標(biāo)及其約束條件 problem()為： 我們的目標(biāo)就是要最大化網(wǎng)絡(luò)源節(jié)點(diǎn)的效用同時(shí)最小整個(gè)網(wǎng)絡(luò)的傳輸代價(jià)。網(wǎng)絡(luò)流平衡約束條件和鏈路帶寬容量約束條件分別由式 (4． 9． 2)和式 (4． 94)來(lái)表示。約束條件 (4． 9． 3)表示，對(duì)于任一條鏈路 O，力上流向任一目的節(jié)點(diǎn)的信息流應(yīng)該小于該條鏈路實(shí)際流量，這是由于 (f， jf)上可能被多個(gè)組播組和目的節(jié)點(diǎn)所共用。 二、解決方案 對(duì)上面提出來(lái)的優(yōu)化目標(biāo)，我們希望能尋找分布式的算法從而可以應(yīng)用于大規(guī)模分布式網(wǎng)絡(luò)中。考慮到這里假設(shè)的代價(jià)函數(shù)是凸的且連續(xù)遞增的，對(duì)應(yīng)的每一條鏈路單位流量通過(guò)產(chǎn)生的代價(jià)， 同時(shí)也為一個(gè)凹函數(shù)。對(duì)于一個(gè)凸的目標(biāo)函 26 數(shù)在一個(gè)線性約束集下，根據(jù)凸函數(shù)最大化問(wèn)題我們可以知道該最優(yōu)化問(wèn)題存在唯一的最優(yōu)解。 為了尋找一個(gè)分布式的算法來(lái)求解，首先考慮上述問(wèn)題的對(duì)偶，并釋放流 平衡約束和鏈路容量約束，于是上式的拉格朗日對(duì)偶函數(shù)可表示為： 負(fù)數(shù)也是凹函數(shù)，它們的線性組合亦為凹函數(shù) )上式存在唯一的最優(yōu)解，則對(duì)應(yīng)于變量寶和聲、以及拉格朗日乘子多和互應(yīng)該滿足條件： 27 Problem(411)為 Problem(49)在加入網(wǎng)絡(luò)編碼后的變形， Problem(411)1拘對(duì)偶問(wèn)題 Dual： 利用分布式的次梯度算法來(lái)求解我們優(yōu)化問(wèn)題，可以知道，使用迭代算法求解非線性最優(yōu)化問(wèn)題的關(guān)鍵在于，如何構(gòu)造每一次的搜索方向和確定適當(dāng)?shù)牟介L(zhǎng)。我們可以利用 primal— dual算法求解優(yōu)化問(wèn)題 Problem(4． 11). 我們假設(shè)在網(wǎng)絡(luò)節(jié)點(diǎn)和鏈路上均設(shè)置相應(yīng)的 processor。對(duì)于 node processor而言，在其中記錄每次循環(huá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ò)中。如果在這里我們加入了網(wǎng)絡(luò)編碼，又可以在一定程度上提高網(wǎng)絡(luò)的吞吐量。 第四節(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)。對(duì)于網(wǎng)絡(luò)的任意兩節(jié)點(diǎn)間的鏈路都有單位流量成本和鏈路容量?jī)蓚€(gè)網(wǎng)絡(luò)參數(shù) (前面一個(gè)參數(shù)為單位代價(jià)，后面一 29 個(gè)參數(shù)為為鏈路容量 )。可以將圖 4． 2所示的網(wǎng)絡(luò)拓?fù)湟暈閳D 4． 3中的三個(gè)組播組，每一個(gè)組播中有一個(gè)源節(jié)點(diǎn)以及若干中間節(jié)點(diǎn)和目的節(jié)點(diǎn) (組播子網(wǎng) )。 圖 42 網(wǎng)絡(luò)拓?fù)鋱D 圖 43 三個(gè)組播子圖 30 圖 4． 4給出了用次梯度迭代算法計(jì)算出來(lái)的每個(gè)組播組源節(jié)點(diǎn)發(fā)送速率 (圖4． 3所示的三個(gè)組播組 )。從圖中可以看出，在迭代 50次以后，各個(gè)組播組的源節(jié)點(diǎn)可 以達(dá)到各自組播速率的穩(wěn)定值，即出度帶寬的上限。這里設(shè)置迭代步長(zhǎng)stepsize=O． 01。 圖 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)定得到。 31 圖 45仿真結(jié)果 (固定步長(zhǎng) stepsize=O． 01) 為了分析步長(zhǎng)選擇對(duì)我們算法收斂性的影響，我們還選擇了其他步長(zhǎng)進(jìn)行比較。實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，當(dāng)步長(zhǎng)選擇越小，迭代速率越慢，越能接近最優(yōu)值，這也是符合梯 度算法本身特性的。在實(shí)際網(wǎng)絡(luò)中，端系統(tǒng)用戶可以根據(jù)自身情況隨時(shí)調(diào)整迭代計(jì)算的步長(zhǎng)，在計(jì)算初可以選擇大的步長(zhǎng)值快速逼近最優(yōu)值，此后可以使用遞減的步長(zhǎng)進(jìn)行計(jì)算以求達(dá)到最優(yōu)值。圖 4． 6和圖 4． 7分別給出了迭代步長(zhǎng)stepsizeO． 01和可變步長(zhǎng)下的各個(gè)組播源節(jié)點(diǎn)發(fā)送速率的變化。 圖 46組播源節(jié)點(diǎn)速率變化圖 (同定步長(zhǎng) stcpsize=O． 005) 32 圖 47組播源節(jié)點(diǎn)速率變化圖 (不固定步長(zhǎng) stepsize=O． 01／ k) 33 結(jié)論 隨著互聯(lián)網(wǎng)上的大規(guī)模媒體存儲(chǔ) 與發(fā)布的不斷發(fā)展，多媒體技術(shù)的廣泛使用，如遠(yuǎn)程會(huì)議、網(wǎng)絡(luò)視頻和音頻廣播，這些新媒體服務(wù)對(duì)網(wǎng)絡(luò)帶寬要求很高，傳統(tǒng)集中式分發(fā)模型不再適用，人們希望通過(guò)建立新的分布式傳輸模式來(lái)解決大規(guī)模數(shù)據(jù)分發(fā)問(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)用層組播路由算法。根據(jù)網(wǎng)絡(luò)編碼的特點(diǎn)，在組播源節(jié)點(diǎn)和網(wǎng)絡(luò)中的每一個(gè)目的節(jié)點(diǎn)之間建立多條不相交的數(shù)據(jù)通信 路徑形成組播圖。利用網(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ōu)化理論，建立網(wǎng)絡(luò)優(yōu)化目標(biāo)函數(shù)，即網(wǎng)絡(luò)效用 最大，以及相應(yīng)的約束條件，利用拉格朗日乘子釋放約束條件，并利用梯度算法求解目標(biāo)函數(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)化。 34 致 謝 經(jīng)過(guò)近兩個(gè)月的努力，終于順利完成了畢業(yè)設(shè)計(jì)。 在這里我要衷心感謝所有在設(shè)計(jì)過(guò)程中給我提供幫助的老師和同學(xué) 首先要感謝鄭老師，在完成畢業(yè)論文的這段時(shí)間里鄭老師給出了許多寶貴的意見(jiàn)和幫助。從畢業(yè)論文的介紹講解，然后到畢業(yè)論文的選題，到交初稿，到完成整個(gè)的畢業(yè)論文，這些都是在老師的幫助下完成的。她的細(xì)心，耐心，關(guān)心是我 們完成畢業(yè)論文的基礎(chǔ)。她的寶貴意見(jiàn)和幫助我們都非常受用。她時(shí)常給我們指出錯(cuò)誤并指導(dǎo)我們改正。所以再次感謝老師。 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)愛(ài) .《運(yùn)籌學(xué)》，清華大學(xué)出版社， 20xx． [8]．鄧先禮 .《最優(yōu)化技術(shù)》，重慶大學(xué)出版社， 1998． [9]．張忠楨 .《凸規(guī)劃》，武漢大學(xué)出版社， 20xx．