【正文】 摘 要隨著通信網(wǎng)絡(luò)技術(shù)的發(fā)展和多媒體技術(shù)的廣泛運用，網(wǎng)絡(luò)資源緊張和分配不合理的問題越來越突出。在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ù)進行運算操作(如線性運算)。利用網(wǎng)絡(luò)編碼，端系統(tǒng)對收到的數(shù)據(jù)進行組合編碼，從而有效地利用網(wǎng)絡(luò)帶寬，增加網(wǎng)絡(luò)容量。關(guān)鍵詞：應(yīng)用層組播、網(wǎng)絡(luò)編碼、分布式算法、最大效用、凸優(yōu)化AbstractWith the development of munication network and multimedia technology,the requirement of supporting large scale data distribution such as video streaming has e into being and soon gathers a great research interest．While currently the limitation of network resources as well as the inefficient network resource utilization renders a great challenge towards its further development．With the consideration of failing to implement IP multicast within a wide range of network,the end system based application layer multicast(ALM) has been proposed．Besides equipped with a11 the function of traditional routing node such as data forwarding,data duplicating，the mighty end system in ALM Can also carry out some operation(e．g．1inear bination)upon the traffic received．Specifically, we employ network coding，a brand new multicast technology in some end systems with the purpose of better utilizing bandwidth resources and improving network throughput．Keywords：Application level Multicast，Network Coding,DistributedAlgorithms，Max utility,Convex optimize目 錄第一章 緒論 1第一節(jié) 課題來源 1第二節(jié) 課題研究的目的和意義 1第三節(jié) 論文的主要研究內(nèi)容 2第二章 網(wǎng)絡(luò)編碼 3第一節(jié) 網(wǎng)絡(luò)編碼原理 3第二節(jié) 網(wǎng)絡(luò)編碼的優(yōu)點 5第三節(jié) 絡(luò)編碼的應(yīng)用 7第三章 一種基于網(wǎng)絡(luò)編碼的應(yīng)用層組播路由算法 9第一節(jié) 應(yīng)用層組播 9第二節(jié) 基于網(wǎng)絡(luò)編碼的應(yīng)用層組播路由算法 11第三節(jié) 實驗仿真和結(jié)果分析 17第四章 應(yīng)用層網(wǎng)絡(luò)編碼的網(wǎng)絡(luò)傳輸最優(yōu)化 23第一節(jié) 最優(yōu)化技術(shù)：凸優(yōu)化方法 23第二節(jié) 基于網(wǎng)絡(luò)編碼的應(yīng)用層組播最優(yōu)化 24第三節(jié) 基于網(wǎng)絡(luò)編碼的應(yīng)用層組播凈效用最優(yōu)化 24第四節(jié) 仿真結(jié)果與分析 28結(jié)論 33致 謝 34參考文獻 35第一章 緒論第一節(jié) 課題來源本課題來源于國家高技術(shù)研究發(fā)展計劃(863計劃)(2006AA012322)：視頻媒體基于信息可重用的分布式網(wǎng)絡(luò)化編碼及傳輸。第二節(jié) 課題研究的目的和意義隨著寬帶多媒體網(wǎng)絡(luò)的不斷發(fā)展，各種寬帶網(wǎng)絡(luò)應(yīng)用層出不窮，例如：數(shù)字電視、視頻會議、數(shù)據(jù)和資料分發(fā)、網(wǎng)絡(luò)音頻應(yīng)用、網(wǎng)絡(luò)視頻應(yīng)用、多媒體遠程教育等。這些寬帶多媒體應(yīng)用都對現(xiàn)有寬帶多媒體網(wǎng)絡(luò)的承載能力提出了挑戰(zhàn)。采用單播技術(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ù)丟失等等問題。于是，組播通信方式被提出，旨在改善現(xiàn)有網(wǎng)絡(luò)中存在的一些網(wǎng)絡(luò)資源緊張問題，提高網(wǎng)絡(luò)的服務(wù)質(zhì)量QoS[11。組播是現(xiàn)在網(wǎng)絡(luò)研究中的一個重要課題。組播通信的基本出發(fā)點是：在同時存在多個接收者時，通過合并重復(fù)信息的傳輸來達到減少帶寬浪費和降低服務(wù)器處理負擔(dān)的目的。其發(fā)展之一的IP組播模型是對Internct基本的“單播、盡力發(fā)送’’模型的一個重要擴充，它把組播的主要功能都放在路由器上實現(xiàn)。而由于口組播在傳輸技術(shù)和管理上存在嚴重的問題，主要是口組播需要路由器維護組播通信的狀態(tài)信息，增加了網(wǎng)絡(luò)的復(fù)雜性并嚴重約束網(wǎng)絡(luò)組播的擴展，其次網(wǎng)絡(luò)的可靠性、擁塞控制、流量控制、安全性無法得到保障，另外由于P地址空間有限，無法滿足眾多應(yīng)用的需求，因此目前IP組播沒有在Internet中得到普遍采用[21。研究人員反思口層組播體系存在的問題后，在2000年提出了應(yīng)用層組播。它的主要思想是：保持Intemet原有的模型，盡量不改變原來網(wǎng)絡(luò)的體系結(jié)構(gòu)，而主要通過增加端系統(tǒng)的功能來實現(xiàn)組播的功能。由于對網(wǎng)絡(luò)本身的改變很少，應(yīng)用層組播具有很好的靈活性。隨著Peel39。m．Peer Network和OverlayNetwork等技術(shù)的提出和發(fā)展對應(yīng)用層組播的研究也有很大的促進作用。但是，上海大學(xué)碩士學(xué)位論文端系統(tǒng)的穩(wěn)定性一般不如專用網(wǎng)絡(luò)設(shè)備，并且應(yīng)用層組播在帶寬利用效率及網(wǎng)絡(luò)延遲方面也無法和P組播相比。另外，應(yīng)用層組播中的系統(tǒng)框架和很多細節(jié)技術(shù)也還在研究當(dāng)中。這些問題的存在為應(yīng)用層組播的研究提供了廣闊的空間。網(wǎng)絡(luò)編碼的思想在2000年由R．Ahlswede首次提出，我們發(fā)現(xiàn)網(wǎng)絡(luò)編碼可以大大提高網(wǎng)絡(luò)的傳輸能力和傳輸可靠，其理論創(chuàng)新具有普遍意義，應(yīng)用前景十分廣闊?？紤]到應(yīng)用層組播是基于應(yīng)用層端系統(tǒng)之上的，端系統(tǒng)比傳統(tǒng)的IP路由器功能更為強大，可以在端系統(tǒng)上引入網(wǎng)絡(luò)編碼，將接受到的信息進行解碼和編碼可以提高網(wǎng)絡(luò)傳輸?shù)男?。第三?jié) 論文的主要研究內(nèi)容本論文是作者攻讀碩士學(xué)位期間承擔(dān)課題的工作總結(jié)。第一章中闡述了課題來源、研究目的和意義以及國內(nèi)外本課題研究的現(xiàn)狀。第二章闡述了課題研究的基本理論——網(wǎng)絡(luò)編碼的概念和基本原理，包括如何進行編碼和解碼，以及網(wǎng)絡(luò)編碼的優(yōu)點和使用范圍。第三章在對比其它傳統(tǒng)組播路由算法的基礎(chǔ)上，結(jié)合網(wǎng)絡(luò)編碼提出了新的基于網(wǎng)絡(luò)編碼的分布式應(yīng)用層組播路由算法。第四章中，考慮到第三章中提出啟發(fā)式算法本身作為NP．plete問題不能得到網(wǎng)絡(luò)最優(yōu)解的局限性，從凸優(yōu)化角度分布式考慮如何使得整個網(wǎng)絡(luò)的效用最大及網(wǎng)絡(luò)傳輸開銷最小，利用拉格朗日對偶和次梯度算法來求解，使得網(wǎng)絡(luò)源節(jié)點效用最大和鏈路中流量分配合理。最后第五章總結(jié)了全文以及碩士期間的研究工作，并以后工作提出了設(shè)想。35第二章 網(wǎng)絡(luò)編碼第一節(jié) 網(wǎng)絡(luò)編碼原理在現(xiàn)有的通信網(wǎng)絡(luò)中，信息傳輸都是由源節(jié)點經(jīng)過中間節(jié)點，以存儲轉(zhuǎn)發(fā)的方式傳送到目的節(jié)點的。除了數(shù)據(jù)復(fù)制以外，一般來說在網(wǎng)絡(luò)的中間節(jié)點并不需要做任何數(shù)據(jù)處理。在許多實際應(yīng)用中，人們?yōu)榱诵畔⒎治觥⑿畔踩约敖粨Q的目的，總是要在中間節(jié)點進行某種形式的數(shù)據(jù)處理。但是人們普遍認為，中間節(jié)點所進行的數(shù)據(jù)處理對數(shù)據(jù)傳輸過程本身并不會帶來任何好處。2000年，R．Ahlswcde首次提出了對信息進行網(wǎng)絡(luò)編碼的思想。所謂網(wǎng)絡(luò)編碼，就是指節(jié)點對輸入的多路信息流進行代數(shù)組合運算，生成一路或多路新的輸出信息流。在傳統(tǒng)的網(wǎng)絡(luò)中，大量存在的中間節(jié)點只能對接收到的數(shù)據(jù)進行路由、復(fù)制和轉(zhuǎn)發(fā)，這對于有限的網(wǎng)絡(luò)資源是嚴重浪費。由于網(wǎng)絡(luò)中被傳遞的信息本質(zhì)上就是連續(xù)的比特流，是一系列抽象的代數(shù)符號，因此信息除