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

　　

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