[碩士論文精品]面向仿真的應(yīng)用層組播協(xié)議研究

摘要摘要隨著計(jì)算機(jī)網(wǎng)絡(luò)的不斷發(fā)展，互聯(lián)網(wǎng)已經(jīng)成為了人類社會(huì)主流的一個(gè)重要組成部分。人們希望互聯(lián)網(wǎng)能夠不斷地提供應(yīng)用所需的各種網(wǎng)絡(luò)服務(wù)。特別是，以視頻會(huì)議、視頻點(diǎn)播、遠(yuǎn)程教育等為代表的新型多媒體組播應(yīng)用的大量涌現(xiàn)，對(duì)組播通信服務(wù)提出了迫切的需求。近年來P2P技術(shù)的快速發(fā)展，基于應(yīng)用層組播P2P流媒體傳輸，引起了許多大學(xué)和公司的重視并紛紛開展研究。與組播相比，應(yīng)用層組播具有靈活和易實(shí)施的特點(diǎn)，但是因?yàn)榻K端主機(jī)可以自由地退出組播樹，應(yīng)用層組播也存在數(shù)據(jù)傳遞易中斷的缺點(diǎn)，這對(duì)實(shí)時(shí)性要求嚴(yán)格的視頻直播應(yīng)用的影響尤為嚴(yán)重。本論文在對(duì)現(xiàn)有應(yīng)用層組播協(xié)議進(jìn)行詳細(xì)研究的基礎(chǔ)上，針對(duì)現(xiàn)有系統(tǒng)中存在的缺陷提出一種具有多層次應(yīng)用層結(jié)構(gòu)的應(yīng)用層組播協(xié)議。該協(xié)議具有較高的效率和良好的可擴(kuò)展性，主要面向?qū)崟r(shí)的多媒體應(yīng)用，減少分組延遲，保證流媒體數(shù)據(jù)傳輸?shù)膶?shí)時(shí)性。論文的具體研究和實(shí)現(xiàn)工作主要包括以下幾個(gè)方面應(yīng)用層組播系統(tǒng)結(jié)構(gòu)的研究。對(duì)對(duì)等型，代理型，服務(wù)型三種應(yīng)用層組播系統(tǒng)結(jié)構(gòu)進(jìn)行分析總結(jié)，提出了一種適用的應(yīng)用層組播系統(tǒng)協(xié)議棧模型。應(yīng)用層組播協(xié)議的研究。仔細(xì)分析現(xiàn)有的應(yīng)用層組播系統(tǒng)的優(yōu)勢(shì)和不足，、設(shè)計(jì)新的組播協(xié)議。協(xié)議考慮到底層網(wǎng)絡(luò)拓?fù)涮卣鳎苊鈹?shù)據(jù)包在代價(jià)昂貴的鏈路上傳輸，從而減少延遲。同時(shí)采用基于斐波那契序列的組播算法進(jìn)行群內(nèi)組播。另一方面引入動(dòng)態(tài)組管理策略，具有較高的擴(kuò)展性。對(duì)所設(shè)計(jì)的協(xié)議進(jìn)行仿真，通過兩個(gè)不同的仿真實(shí)驗(yàn)來分析該協(xié)議在AED，ALS和ACS性能上的優(yōu)劣。第一個(gè)仿真實(shí)驗(yàn)考察的是單源情況，第二個(gè)仿真實(shí)驗(yàn)考察的是多源情況，在每種情形下變化組播組的成員數(shù)目。關(guān)鍵詞應(yīng)用層組播；覆蓋網(wǎng)；仿真；NS2ABSTRACTABSTRACTWITHTHEDEVELOPMENTOFCOMPUTERNETWORK,INTERACTHASBEENBECOMINGALLIMPORTANTPARTOFTHEMEANSTREAMINGOFHUMANBEINGPEOPLEHOPEINTERNETCOULDPROVIDEALLKINDSOFNETWORKSERVICESTHEAPPLICATIONSNEEDESPECIALLY,THEEMERGENCEOFMANYNEWMULTIMEDIAGROUPAPPLICATIONS，SUCHASVIDEOCONFERENCING，VIDEOONDEMANDANDDISTANCELEAMING，REQUIREMULTICASTCOMMUNICATIONSERVICEIMMINENTLYRECENTLYASTHEDEVELOPMENTOFP2PTECHNIQUES，APPLICATIONLEVELMULTICASTALMBASEDONP2PALSOKNOWNASENDSYSTEMMULTICASTOROVERLAYMULTICASTHASBECOMEAVERYPOPULARRESEARCHINMANYCOLLEGEANDCORPORATIONCOMPAREDWITHIPMULTICAST，ALMISMOREFLEXIBLEANDDEPLOYABLEBUTDATADELIVERYINALMTREECANBEEASILYINTERRUPTEDBYDEPARTUREOFENDHOSTS，WHICHMAYLEADTODEGRADATIONOFQOSINTIMESENSITIVEAPPLICATIONSSUCHASLIVESTREAMINGONTHEBASISOFTHESERIOUSSTUDYONTHEEXISTINGAPPLICATIONLAYERMULTICASTPROTOCOL，THISPAPERPROPOSEDAMULTILEVELSTRUCTUREOFTHEAPPLICATIONLAYERMULTICASTPROTOCOLASFORTHEDEFICIENCIESINCURRENTLYSYSTEMSSUCHPROTOCOLHASAHIGHEFFICIENCYANDEXCELLENTSCALABILITY,MAINLYFORREALTIMEMULTIMEDIAAPPLICATIONS，TOREDUCETHEPACKETDELAY,ENSUNNGTHATREALTIMEDATATRANSMISSIONOFSTREAMINGMEDIATHEEXACTLYRESEARCHANDSPECIFICWORKOFTHESISINCLUDETHEFOLLOWINGETHESTUDIESOFAPPLICATIONLAYERMULTICASTSYSTEMARCHITECTUREANALYZEDANDSUMMARIZEDOFTHREEPOPULARAPPLICATIONLAYERMULTICASTSYSTEMARCHITECTURE，ASTACKMODELOFAPPLICATIONLAYERMULTICASTSYSTEMISPROPOSEDTHERESEARCHOFAPPLICATIONLAYERMULTICASTPROTOC01WEDESIGNEDANEWMULTICASTPROTOCOLUNDERCAREFULANALYSISOFTHEEXISTINGAPPLICATIONLAYERMULTICASTSYSTEMSSTRENGTHSANDWEAKNESSESTHEPROTOCOLCONSIDERATETHECHARACTERISTICSOFTHEUNDERLYINGNETWORKTOPOLOGYTOAVOIDCOSTLYPACKETSINTHETRANSMISSIONLINK,THEREBYREDUCINGTHEDELAYATTHESAMETIME，ITADOPTSTHEMULTICASTALGORITHMBASEDIII面向仿真的應(yīng)用層組播協(xié)議研究ONTHEFIBONACCISEQUENCETOREALIZEGROUPMULTICASTONTHEOTHERHANDADYNAMICGROUPMANAGEMENTSTRATEGYISINTRODUCED，WITHAHIGHERSCALABILITYOTHESIMULATIONOFTHEPROTOC01ANALYZETHEADVANTAGESOFAED，ALS，ACSPERFORMANCETHROUGHTHETWODIFFERENTSIMULATIONEXPERIMENTSTHEFIRSTSIMULATIONISABOUTSINGLESOURCECASETHESECONDSIMULATIONISABOUTMULTISOURCESITUATION，INEACHCASECHANGESTHENUMBEROFMULTICASTGROUPMEMBERSKEYWORDSAPPLICATIONLAYERMULTICAST；OVERLAYNETWORK；SIMULATION；NS2IV廈門大學(xué)學(xué)位論文原創(chuàng)性聲明本人呈交的學(xué)位論文是本人在導(dǎo)師指導(dǎo)下，獨(dú)立完成的研究成果。本人在論文寫作中參考其他個(gè)人或集體已經(jīng)發(fā)表的研究成果，均在文中以適當(dāng)方式明確標(biāo)明，并符合法律規(guī)范和廈門大學(xué)研究生學(xué)術(shù)活動(dòng)規(guī)范試行。另外，該學(xué)位論文為課題組的研究成果，獲得課題組經(jīng)費(fèi)或?qū)嶒?yàn)室的資助，在實(shí)驗(yàn)室完成。請(qǐng)?jiān)谝陨侠ㄌ?hào)內(nèi)填寫課題或課題組負(fù)責(zé)人或?qū)嶒?yàn)室名稱，未有此項(xiàng)聲明內(nèi)容的，可以不作特別聲明。聲明人簽名研锫護(hù)7年石月歲日廈門大學(xué)學(xué)位論文著作權(quán)使用聲明本人同意廈門大學(xué)根據(jù)中華人民共和國學(xué)位條例暫行實(shí)施辦法等規(guī)定保留和使用此學(xué)位論文，并向主管部門或其指定機(jī)構(gòu)送交學(xué)位論文包括紙質(zhì)版和電子版，允許學(xué)位論文進(jìn)入廈門大學(xué)圖書館及其數(shù)據(jù)庫被查閱、借閱。本人同意廈門大學(xué)將學(xué)位論文加入全國博士、碩士學(xué)位論文共建單位數(shù)據(jù)庫進(jìn)行檢索，將學(xué)位論文的標(biāo)題和摘要匯編出版，采用影印、縮印或者其它方式合理復(fù)制學(xué)位論文。本學(xué)位論文屬于1經(jīng)廈門大學(xué)保密委員會(huì)審查核定的保密學(xué)位論文，于年月日解密，解密后適用上述授權(quán)。2不保密，適用上述授權(quán)。請(qǐng)?jiān)谝陨舷鄳?yīng)括號(hào)內(nèi)打“或填上相應(yīng)內(nèi)容。保密學(xué)位論文應(yīng)是已經(jīng)廈門大學(xué)保密委員會(huì)審定過的學(xué)位論文，未經(jīng)廈門大學(xué)保密委員會(huì)審定的學(xué)位論文均為公開學(xué)位論文。此聲明欄不填寫的，默認(rèn)為公開學(xué)位論文，均適用上述授權(quán)。磊何日名劍擄月人多明年聲N沙第一章緒論11組播第一章緒論在INTEMET上，流媒體技術(shù)如視頻會(huì)議和視頻點(diǎn)播等應(yīng)用日益廣泛。點(diǎn)對(duì)點(diǎn)傳輸?shù)膯尾シ绞揭呀?jīng)不能適應(yīng)這一類業(yè)務(wù)的傳輸特性一單點(diǎn)發(fā)送，多點(diǎn)接收“，因?yàn)榉?wù)器必須為每一個(gè)接收者提供一份相同內(nèi)容的M報(bào)文拷貝，使得網(wǎng)絡(luò)上重復(fù)傳輸大量相同內(nèi)容的報(bào)文，占用了大量資源。在這種情況下組播【LLMULTICAST應(yīng)運(yùn)而生，它的出現(xiàn)解決了網(wǎng)絡(luò)數(shù)據(jù)冗余的問題，尤其對(duì)于音頻，視頻數(shù)據(jù)，可以節(jié)省大量網(wǎng)絡(luò)資源，解決一個(gè)主機(jī)向多個(gè)接收者發(fā)送數(shù)據(jù)的問題。組播是指同時(shí)將數(shù)據(jù)分組高效地發(fā)送給網(wǎng)絡(luò)上的一組目標(biāo)主機(jī)，而不關(guān)心這些主機(jī)位于網(wǎng)絡(luò)的什么位置。在真正的組播技術(shù)產(chǎn)生以前，可以使用兩種不同的方式來實(shí)現(xiàn)組播功能。第一種是采用廣播方式，將分組廣播給網(wǎng)絡(luò)上的所有主機(jī)，所有的目標(biāo)主機(jī)都能收到分組；第二種方式是假設(shè)源節(jié)點(diǎn)知道所有目標(biāo)主機(jī)，通過順序單播的方式將分組依次發(fā)送給目標(biāo)主機(jī)。這兩種方式效率都比較低。在現(xiàn)有的網(wǎng)絡(luò)服務(wù)中，組播MULTICAST通信服務(wù)一直占有重要的地位。不同于單播UNICAST通信發(fā)送者需要向各個(gè)接收者單獨(dú)發(fā)送數(shù)據(jù)報(bào)文，在組播通信中發(fā)送者只需要向所有接受者發(fā)送一個(gè)原始數(shù)據(jù)報(bào)文，該報(bào)文的拷貝由具有組播功能的中間系統(tǒng)完成，并最終轉(zhuǎn)發(fā)給各個(gè)接收者。因此，組播通信能節(jié)省大量的網(wǎng)絡(luò)通信資源，并提高通信效率，這使其成為了支持以實(shí)時(shí)多媒體應(yīng)用為代表的下一代新型組播應(yīng)用如視頻會(huì)議、視頻點(diǎn)播、遠(yuǎn)程教育、網(wǎng)絡(luò)電視等的關(guān)鍵技術(shù)之一。然而，新型組播應(yīng)用的種類非常之多，它們?cè)诮M播組的規(guī)模、組內(nèi)數(shù)據(jù)發(fā)送源的數(shù)量、組成員的動(dòng)態(tài)性、以及對(duì)帶寬和延時(shí)要求等方面存在著很大的差異。表11給出了幾種典型組播應(yīng)用的特點(diǎn)比較【2】【31。由此可見，如何適應(yīng)不同應(yīng)用的差異，滿足它們的需求，是組播通信面臨的新課題。面向仿真的應(yīng)用層組播協(xié)議研究表11幾種典型組播應(yīng)用的特點(diǎn)與比較應(yīng)用組播數(shù)據(jù)源組規(guī)模帶寬延時(shí)組成員動(dòng)態(tài)性視頻會(huì)議多小中小低遠(yuǎn)程教育單，少中中小低網(wǎng)絡(luò)電視IPTV單大大小局視頻點(diǎn)播VOD單大大小高多方游戲多中、大中小高在線股票新聞單大小小高分布式仿真單，少中大視情況低分布式WEB緩存更新單，少中大大低12IP組播在INTERNET體系結(jié)構(gòu)中，DEERING首先提出口組播體系結(jié)構(gòu)【41，組播功能在網(wǎng)絡(luò)層實(shí)現(xiàn)，組播分組的復(fù)制和轉(zhuǎn)發(fā)都在網(wǎng)絡(luò)的路由器上進(jìn)行。P組播是實(shí)現(xiàn)組播分組轉(zhuǎn)發(fā)的有效方式，因?yàn)樗梢允乖谌W(wǎng)范圍內(nèi)分組復(fù)制的數(shù)量達(dá)到最少。121IP組播地址口組播通信必須依賴于組播地址，在DV4中它是一個(gè)D類D地址，范圍從224000到239255255255，并被劃分為局部鏈接組播地址、預(yù)留組播地址和管理權(quán)限組播地址三類。其中，局部鏈接組播地址范圍在22400O一22400255，這是為路由協(xié)議和其它用途保留的地址，路由器并不轉(zhuǎn)發(fā)屬于此范圍的M包；預(yù)留組播地址為22401O_238255255255，可用于全球范圍如INTERNET或網(wǎng)絡(luò)協(xié)議；管理權(quán)限組播地址為23900O_239255255255，可供組織內(nèi)部使用，類似于私有P地址不能用予INTEMET，可限制組播范圍。2第一章緒論122IP組播的標(biāo)準(zhǔn)模型STEPHENDEERING在文獻(xiàn)【4】中描述了P網(wǎng)絡(luò)中標(biāo)準(zhǔn)的組播模型。P組播是一種開放的服務(wù)模型，模型中具有發(fā)送者和接收者兩個(gè)概念。主機(jī)通過IGMPT5】報(bào)文與本地路由器交互，成為接收者。發(fā)送者只需將報(bào)文的目的地址指定為組播組地址就可實(shí)現(xiàn)發(fā)送。P組播使用D類P地址作為組播組地址。P組播沒有提供技術(shù)用來限制用戶創(chuàng)建一個(gè)組播組，接收組播組的數(shù)據(jù)，和向組播組發(fā)送數(shù)據(jù)。組成員身份只是實(shí)現(xiàn)了接收者可以收到數(shù)據(jù)，不提供任何訪問控制的功能。為了收到一個(gè)組播組的數(shù)據(jù)，用戶只需用IA舊協(xié)議與本地路由器聯(lián)系。當(dāng)一個(gè)主機(jī)變成組播組的接收者之后，它可以收到組播組的所有數(shù)據(jù)報(bào)文，而不管數(shù)據(jù)報(bào)文的發(fā)送者是誰，是否是惡意的發(fā)送者。發(fā)送者不需要成為組的接收者，只需將報(bào)文的目的地址指定成組播組地址，就可以實(shí)現(xiàn)向組播組發(fā)送報(bào)文。發(fā)送者不能對(duì)自己使用的組地址進(jìn)行保留，限制別的用戶使用與自己相同的組地址。總之，口組播的服務(wù)模型沒有提供組的管理。P組播數(shù)據(jù)報(bào)文與所有的P數(shù)據(jù)報(bào)一樣，提供盡力而為服務(wù)，沒有可靠性保證。P組播傳送功能是通過在P網(wǎng)絡(luò)設(shè)備上運(yùn)行相應(yīng)的組播路由協(xié)議來實(shí)現(xiàn)的。123IP組播路由協(xié)議組播數(shù)據(jù)沿一個(gè)連接所有組播組成員的樹型結(jié)構(gòu)發(fā)送，這個(gè)樹型結(jié)構(gòu)稱為組播樹。組成員可以動(dòng)態(tài)的加入和退出，組播樹也必須同時(shí)動(dòng)態(tài)更新。根據(jù)構(gòu)造方法的不同，組播樹可以分為源點(diǎn)樹SOURCEBASEDTREE和共享樹SHAREDTREE。源點(diǎn)樹以組播源點(diǎn)為根構(gòu)造到所有組播組成員的生成樹，通常也稱為最短路徑樹SPT，SHORTESTPATHTREE。共享樹也稱為RP匯聚點(diǎn)樹或基于核心的樹CBT，COREBASEDTREE，它的構(gòu)造方法是以網(wǎng)絡(luò)中的某一個(gè)指定的路由器為根節(jié)點(diǎn)，該路由器稱為RP，由此節(jié)點(diǎn)生成包含所有組成員的樹。使用共享樹時(shí)，組播源需要首先把組播數(shù)據(jù)發(fā)送到RP路由器，再由RP轉(zhuǎn)發(fā)給其他的組成員。組播路由協(xié)議的任務(wù)就是構(gòu)造組播樹，根據(jù)對(duì)網(wǎng)絡(luò)中的組播成員的分布和3面向仿真的應(yīng)用層組播協(xié)議研究使用的不同，組播路由協(xié)議分為兩類密集模式DM，DENSEMODEL路由協(xié)議和稀疏模式SM，SPARSEMODEL路由協(xié)議。ODM路由協(xié)議通常用于組播成員較為集中，數(shù)量較多，網(wǎng)絡(luò)中有少數(shù)發(fā)送者和大量的接收者，并且有足夠帶寬的鏈路環(huán)境，比如公司或園區(qū)的局域網(wǎng)。DM路由協(xié)議有距離向量組播路由協(xié)議DVMRP、組播OSPF協(xié)議MOSPF和協(xié)議無關(guān)組播協(xié)議一密集模式PIMDM等。這些協(xié)議構(gòu)造從發(fā)送者到接收者的最短路徑。SM路由協(xié)議適用于組成員稀疏分布，接收者比較少，發(fā)送者接收者位于分散地域，大型異構(gòu)的互聯(lián)網(wǎng)絡(luò)環(huán)境。SM路由協(xié)議有基于中心的分布樹協(xié)議CBT和協(xié)議無關(guān)組播協(xié)議一稀疏模式PIMSM等。這類協(xié)議構(gòu)造從RP或CORE到接收者的最短路徑。UNICASTMULTICASTRTP，RELIABLEMADGPI攀ALP一ISDPRRCPD州HCAPIDNSMUITICASTIANAIS箋吾再毀。TCP協(xié)UDPICMP薹季IGMPOSPF，RIPPIM,SM,PIMDML舊SPFDVMRPEIGRPETC基R鴦I著蠶爭RIPEIGRPOSPFMSDP。BGMPBGP辮MBGPBGP4圖11IP組播的體系結(jié)構(gòu)P組播的體系結(jié)構(gòu)如圖11所示。圖中左邊是單播協(xié)議，右邊是組播協(xié)議。組播協(xié)議從下而上，最底層是域間和域內(nèi)的組播路由，它們之上是主機(jī)路由器接口IGMP，最上層是如RTPRTCP等的一些主機(jī)服務(wù)。124LP組播存在的問題目前口組播的服務(wù)模型和協(xié)議存在著一些問題，使得口組播至今沒有能4第一章緒論在INTEMET上得到廣泛部署【6】。這些問題既有技術(shù)上的缺陷又有商業(yè)原因，文獻(xiàn)61對(duì)其進(jìn)行了詳細(xì)的討論。ISP不愿意部署P組播的主要原因是路由器換代，為了實(shí)現(xiàn)組播部署，ISP需要對(duì)路由器進(jìn)行換代，提早結(jié)束目前尚在使用的路由器的工作周期，增加了ISP的營運(yùn)成本?？缬虻慕M播管理，每個(gè)ISP都對(duì)域內(nèi)的組播進(jìn)行獨(dú)立的管理。當(dāng)需要跨域的組播服務(wù)時(shí)，ISP之間如何進(jìn)行協(xié)調(diào)策略。域內(nèi)組播的管理，D組播服務(wù)模型及協(xié)議實(shí)現(xiàn)沒有提供組播管理的技術(shù)，ISP如何對(duì)組播進(jìn)行管理組播與單播相比，節(jié)省帶寬，降低延時(shí)，提高效率。然而部署組播的代價(jià)比單播要昂貴的多，ISP是否有利可圖。當(dāng)前P組播還存在很多待解決的技術(shù)問題，這些技術(shù)問題也影響到P組播被廣泛的應(yīng)用?？诮M播主要存在的技術(shù)問題有組播組的管理問題，目前的P組播服務(wù)模型及協(xié)議沒有提供組播組管理的技術(shù)，對(duì)組的發(fā)送者和接收者沒有進(jìn)行訪問控制，這將導(dǎo)致很多問題，如惡意發(fā)送者的泛洪攻擊，組播地址沖突，未經(jīng)授權(quán)的接收者和發(fā)送者。組播的安全問題，P組播使用無連接的協(xié)議UDP來避免響應(yīng)風(fēng)暴。由于UDP是一個(gè)無連接的協(xié)議，它不使用ACK或NACK來確?？煽總魉?，組播也不能被防火墻檢測到，因此，最普通的防火墻類型應(yīng)用程序網(wǎng)關(guān)不能對(duì)組播進(jìn)行安全認(rèn)證。當(dāng)前的口組播服務(wù)和體系結(jié)構(gòu)并不執(zhí)行任何認(rèn)證。組播服務(wù)質(zhì)量問題，P組播是一種盡力而為的服務(wù)，要想在它之上實(shí)現(xiàn)更高質(zhì)量的服務(wù)，例如可靠性，擁塞控制，流控制等這些功能，比在P單播上實(shí)現(xiàn)要困難很多。組播地址分配問題，口組播要求每個(gè)組能夠動(dòng)態(tài)的從組播地址空間中得到一個(gè)全局唯一的組播地址。但是在可擴(kuò)展，分布式，相容的網(wǎng)絡(luò)環(huán)境中，這一點(diǎn)很難得到保證。D組播這些社會(huì)因素和技術(shù)上的問題使其沒有成功在INTEMET上部署起來，有學(xué)者甚至預(yù)言如果母組播繼續(xù)保持復(fù)雜性和管理的困難性，它將很難實(shí)現(xiàn)廣域范圍的部署。在應(yīng)用需要組播服務(wù)支持，而M組播又沒有實(shí)現(xiàn)部署的情況下，研究者提面向仿真的應(yīng)用層紐播協(xié)議研究出了“應(yīng)用層組播”的概念。13應(yīng)用層組播在最初的提議經(jīng)過十多年后，研究學(xué)者們開始考慮在網(wǎng)絡(luò)層實(shí)現(xiàn)組播功能是否最為合適，并提出了很多P組播的替代方案。很多組織提議在應(yīng)用層實(shí)現(xiàn)組播特征，這樣一種模型稱之為應(yīng)用層組播ALM，現(xiàn)在被廣泛認(rèn)為是替代組播的合理方案。應(yīng)用層組播又稱為覆蓋網(wǎng)絡(luò)組播、端系統(tǒng)組播和基于主機(jī)的組播。131應(yīng)用層組播基本思想和性能評(píng)價(jià)指標(biāo)應(yīng)用層組播使用傳統(tǒng)單播提供的服務(wù)，在終端主機(jī)的應(yīng)用層上實(shí)現(xiàn)組播的特征例如組關(guān)系、尋址、組播路由和報(bào)文復(fù)制，網(wǎng)絡(luò)只需要提供盡力傳輸?shù)膯尾スδ堋?yīng)用層組播的基本思想入圖12所示。圖12A是網(wǎng)絡(luò)層組播的實(shí)現(xiàn)示意圖，分組由網(wǎng)絡(luò)中的路由器進(jìn)行復(fù)制，如果主機(jī)A需要向主機(jī)B、C、D發(fā)送分組，則分組在路由器1處進(jìn)行復(fù)制，而在應(yīng)用層組播中，分組在端系統(tǒng)處進(jìn)行復(fù)制。端系統(tǒng)構(gòu)成邏輯上的覆蓋網(wǎng)絡(luò)，應(yīng)用層組播的目標(biāo)就是便于進(jìn)行數(shù)據(jù)傳輸，構(gòu)造并維護(hù)高效的覆蓋網(wǎng)絡(luò)。評(píng)價(jià)應(yīng)用層組播協(xié)議的性能通常采用下面的指標(biāo)。1數(shù)據(jù)路徑的質(zhì)量。數(shù)據(jù)路徑的質(zhì)量一般采用兩個(gè)參數(shù)來衡量強(qiáng)度STRESS、伸展度STRETCHT241。強(qiáng)度定義為每條鏈路或者每個(gè)路由器在傳輸組播分組時(shí)發(fā)送相同分組的次數(shù)。對(duì)于口組播來說鏈路上沒有多余的數(shù)據(jù)報(bào)文復(fù)制，因此對(duì)于網(wǎng)絡(luò)中的每條鏈路或節(jié)點(diǎn)來說，STRESS尺度值均為1。伸展度定義為數(shù)據(jù)分組從源沿著覆蓋網(wǎng)絡(luò)中路徑到達(dá)組成員的路徑長度和直接的從源到組成員的單播路徑長度的比值，這是為每個(gè)組成員定義的尺度。顯然，采用12B中的應(yīng)用層組播方案，由于每條路徑就是單播路徑，每個(gè)成員的伸展度均為1。在圖12C中，AB之間的伸展度為L，AC之間的伸展度為15，AD之間的伸展度為3，平均伸展度等于11533183。2控制信息負(fù)擔(dān)。在覆蓋網(wǎng)絡(luò)中，每一個(gè)成員都要和它們的對(duì)等體周期性地交換刷新信息。這些信息在組中不同的路由器、鏈路和組成員中構(gòu)成控制信6第一章緒論息負(fù)擔(dān)?？刂菩畔⒇?fù)擔(dān)是衡量應(yīng)用層組播可擴(kuò)展性一個(gè)非常重要的度量尺度。圖12網(wǎng)絡(luò)層組播和應(yīng)用層組播除了這些指標(biāo)，還有其它一些衡量應(yīng)用層組播的性能指標(biāo)，包括數(shù)據(jù)生成樹中成員的度的分布，數(shù)據(jù)傳輸延遲等等。不同的應(yīng)用層組播協(xié)議對(duì)這些性能指標(biāo)有不同的考慮，因此不同的協(xié)議將使用不同的方法構(gòu)造覆蓋網(wǎng)絡(luò)。圖12給出了在相同的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下，用不同的應(yīng)用層組播協(xié)議構(gòu)造不同覆蓋網(wǎng)絡(luò)的例子。假定圖中每條鏈路都具有單位長度。圖12B直接采用源節(jié)點(diǎn)A到其它節(jié)點(diǎn)的單播路徑進(jìn)行組播分組轉(zhuǎn)發(fā)，其伸展度為1，A和路由器之間的鏈路強(qiáng)度為3，其它鏈路強(qiáng)度均為1。一般來說，在N個(gè)節(jié)點(diǎn)的組中如果全部采用單播路徑進(jìn)行組播轉(zhuǎn)發(fā)，那么可能出現(xiàn)的最大強(qiáng)度為口因，出現(xiàn)在源節(jié)點(diǎn)的某條鏈路上，而組成員的伸展度為1。另外由于數(shù)據(jù)源節(jié)點(diǎn)和組播組中所有其它節(jié)點(diǎn)交換更新消息，因此最壞情況下負(fù)載為O的。圖12C采用環(huán)形組播方案，其鏈路最大強(qiáng)度為2，平均伸展度為O。圖12D是上述兩種方案的折衷，最大強(qiáng)度和平均伸展度都位于兩者之間。132應(yīng)用層組播的優(yōu)勢(shì)和局限性優(yōu)勢(shì)1應(yīng)用層組播最明顯的優(yōu)勢(shì)是不需要底層網(wǎng)絡(luò)結(jié)構(gòu)，對(duì)路由器沒有多余的要求；2不需要維護(hù)網(wǎng)絡(luò)的狀態(tài)信息，與當(dāng)初設(shè)計(jì)無狀態(tài)網(wǎng)絡(luò)的初衷相符，可擴(kuò)展性問題得到了解決ALM的可擴(kuò)展性僅限于提供ALM的技術(shù)和實(shí)現(xiàn)74面向仿真的應(yīng)用層組播協(xié)議研究方法；3不再需要D類P地址，因?yàn)锳LM方案可以指定自己的尋址方案4單播方案能夠被運(yùn)用到組播應(yīng)用中5應(yīng)用層比網(wǎng)絡(luò)層具有更大的靈活性，應(yīng)用層組播可以根據(jù)應(yīng)用的需求采取更多的手段來提高服務(wù)質(zhì)量。局限性端系統(tǒng)的負(fù)載明顯增加使得ALM不能像D組播那樣高效。這是因?yàn)樵赑組播中分組的復(fù)制是在分支路由器處進(jìn)行的，由于在ALM中路由器不提供任何特殊的服務(wù)，這樣就不可避免分組在同一條單播鏈路上重復(fù)分發(fā)。ALM的一個(gè)主要目標(biāo)是組織的覆蓋網(wǎng)絡(luò)結(jié)構(gòu)盡可能減少分組的重復(fù)分發(fā)，然而在應(yīng)用層上要準(zhǔn)確判斷底層網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是相當(dāng)復(fù)雜和困難，所以這將導(dǎo)致覆蓋網(wǎng)結(jié)構(gòu)沒有P組播分發(fā)樹那樣高效。另外由于應(yīng)用層組播通過端節(jié)點(diǎn)來復(fù)制和轉(zhuǎn)發(fā)數(shù)據(jù)，應(yīng)用層組播和網(wǎng)絡(luò)層組播相比通常延時(shí)較大。133一個(gè)稍微復(fù)雜點(diǎn)的例子圖13應(yīng)用層組播圖13是應(yīng)用層組播的一個(gè)稍微復(fù)雜一點(diǎn)的例子，通過該圖進(jìn)一步說明了應(yīng)用層組播的特點(diǎn)。圖13A展示了從應(yīng)用層上看到的端節(jié)點(diǎn)的邏輯生成樹的拓?fù)浣Y(jié)構(gòu)，圖13B顯示了實(shí)際的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。從源S發(fā)送分組到所有的接收節(jié)點(diǎn)，如果只考慮物理鏈路上分組的數(shù)目，可以發(fā)現(xiàn)在單播組播、應(yīng)用層組播和P組播情況下物理鏈路上分組的數(shù)目分別是33，23，16；與單播組播相比，P組播可以減少52的資源而應(yīng)用層組播可以減少33。8第一章緒論14研究內(nèi)容和論文結(jié)構(gòu)141研究內(nèi)容本論文在對(duì)現(xiàn)有應(yīng)用層組播協(xié)議進(jìn)行詳細(xì)研究的基礎(chǔ)上，針對(duì)現(xiàn)有系統(tǒng)中存在的缺陷提出種具有多層次應(yīng)用層結(jié)構(gòu)的應(yīng)用層組播協(xié)議。該協(xié)議具有較高的效率和良好的可擴(kuò)展性，主要面向?qū)崟r(shí)的多媒體應(yīng)用，減少分組延遲，保證流媒體數(shù)據(jù)傳輸?shù)膶?shí)時(shí)性。論文的具體研究和實(shí)現(xiàn)工作主要包括以下幾個(gè)方面應(yīng)用層組播系統(tǒng)結(jié)構(gòu)的研究。對(duì)對(duì)等型，代理型，服務(wù)型三種應(yīng)用層組播系統(tǒng)結(jié)構(gòu)進(jìn)行分析總結(jié)，提出了一種應(yīng)用層組播系統(tǒng)的協(xié)議棧模型。應(yīng)用層組播協(xié)議的研究。仔細(xì)分析現(xiàn)有的應(yīng)用層組播系統(tǒng)的優(yōu)勢(shì)和不足，設(shè)計(jì)新的組播協(xié)議。協(xié)議考慮到底層網(wǎng)絡(luò)拓?fù)涮卣?，避免?shù)據(jù)包在代價(jià)昂貴的鏈路上傳輸，從而減少延遲。同時(shí)采用基于斐波那契序列的組播算法進(jìn)行群內(nèi)組播。另一方面引入動(dòng)態(tài)組管理策略，具有較高的擴(kuò)展性。對(duì)所設(shè)計(jì)的協(xié)議進(jìn)行仿真，通過兩個(gè)不同的仿真實(shí)驗(yàn)來分析該協(xié)議在AED，ALS和ACS性能上的優(yōu)劣。第一個(gè)仿真實(shí)驗(yàn)考察的是單源情況，第二個(gè)仿真實(shí)驗(yàn)考察的是多源情況，在每種情形下變化組播組的成員數(shù)目。論文的總結(jié)和展望。142論文結(jié)構(gòu)本文分五章，各章節(jié)的內(nèi)容安排如下第一章為緒論，簡單介紹了P組播極其存在的問題，并對(duì)此提出了應(yīng)用層組播，概述了應(yīng)用層組播的基本思想，性能評(píng)價(jià)，并對(duì)比P組播闡述了應(yīng)用層組播的優(yōu)勢(shì)和局限性，通過一個(gè)稍微復(fù)雜一點(diǎn)的例子說明了應(yīng)用層組播的特點(diǎn)。最后給出了本論文的研究內(nèi)容以及組織結(jié)構(gòu)。第二章介紹了應(yīng)用層組播的相關(guān)研究工作。首先概述了OVERLAY網(wǎng)絡(luò)的定義，抽象模型以及基于OVERLAY網(wǎng)絡(luò)的應(yīng)用層組播路由的問題描述。隨后分析現(xiàn)有的應(yīng)用層組播方案，并在此基礎(chǔ)上總結(jié)出三中應(yīng)用層組播系統(tǒng)結(jié)構(gòu)，提出了一種應(yīng)用組播系統(tǒng)的協(xié)議棧模型。9面向仿真的應(yīng)用層組播協(xié)議研究第三章研究了基于樹型拓?fù)浣Y(jié)構(gòu)的應(yīng)用層組播協(xié)議，給出了一種延遲較小的應(yīng)用層組播設(shè)計(jì)方案HFTM。首先分析了要獲得較小組播延遲所需要考慮的問題，在此基礎(chǔ)上，給出了一種考慮主機(jī)位置，分層分群的層次化結(jié)構(gòu)，另外提供了種動(dòng)態(tài)的組管理方法，可以在組成員變化時(shí)以較低的通訊代價(jià)維持正常的組播通訊。第四章通過模擬實(shí)驗(yàn)表明HFTM協(xié)議與其他經(jīng)典應(yīng)用層組播協(xié)議相比具有更好的組播延遲性能第五章是結(jié)束語，總結(jié)了本文的主要工作，貢獻(xiàn)和創(chuàng)新點(diǎn)，并展望了下一步的研究工作。10第二章基于OVERLAY網(wǎng)絡(luò)的應(yīng)用層組播路由協(xié)議的研究第二章基于OVERLAY網(wǎng)絡(luò)的應(yīng)用層組播路由協(xié)議的研究應(yīng)用層組播的基本思想是在不改變網(wǎng)絡(luò)設(shè)施，不依賴于網(wǎng)絡(luò)層是否提供組播服務(wù)支持的情況下，利用網(wǎng)絡(luò)邊緣的端用戶或是專門架設(shè)的服務(wù)器處理資源和網(wǎng)絡(luò)資源，在應(yīng)用層實(shí)現(xiàn)組播服務(wù)。本章首先是OVERLAY網(wǎng)絡(luò)的概述，包括它的定義，技術(shù)優(yōu)勢(shì)和抽象模型；接著介紹應(yīng)用層組播路由的問題描述，包括組播服務(wù)質(zhì)量抽象描述和問題定義。21OVERLAY網(wǎng)絡(luò)概述目前實(shí)現(xiàn)應(yīng)用層組播的基本技術(shù)是將組播組的所有端用戶組成一個(gè)應(yīng)用層的邏輯OVERLAYNETWORK覆蓋網(wǎng)絡(luò)，利用覆蓋網(wǎng)絡(luò)實(shí)現(xiàn)組播組管理、組播管理、組播數(shù)據(jù)分發(fā)等一系列組播相關(guān)的功能。211OVERIAY網(wǎng)絡(luò)的定義覆蓋網(wǎng)絡(luò)7】是在真實(shí)的網(wǎng)絡(luò)拓?fù)渲辖⒌倪壿嬀W(wǎng)絡(luò)，如圖21給出了一個(gè)覆蓋網(wǎng)絡(luò)的模型。ROUTERLINK圈ENDSYSTEMVLINK圖21覆蓋網(wǎng)絡(luò)示意圖圖21中圓形為路由器，方形為端用戶，黑色實(shí)線表示物理鏈路。端用戶、路由器、以及連接它們的物理鏈路構(gòu)成了真實(shí)的物理拓?fù)?。端用戶之間的虛線表示端用戶之間建立的一條網(wǎng)絡(luò)連接，TCP連接或是UDP連接。端用戶和連接他們之間的虛線構(gòu)成了一個(gè)覆蓋網(wǎng)絡(luò)。面向仿真的應(yīng)用層組播協(xié)議研究覆蓋網(wǎng)絡(luò)是一個(gè)邏輯的“網(wǎng)絡(luò)”，它具有虛擬的拓?fù)?，拓?fù)渲械摹肮?jié)點(diǎn)“是端用戶，“邊“是“節(jié)點(diǎn)“之間的連線，“邊“也可以具有參數(shù)。覆蓋網(wǎng)絡(luò)中邊的參數(shù)是對(duì)應(yīng)真實(shí)物理拓?fù)渲械穆窂絽?shù)的代數(shù)疊加。在覆蓋網(wǎng)絡(luò)中，將建立了邊關(guān)系的兩個(gè)端用戶互稱為覆蓋網(wǎng)絡(luò)中的“鄰居”。假定A與B之間的P單播路徑是AR1一R3一B?？蔀楦采w網(wǎng)絡(luò)中的邊AB定義代價(jià)函數(shù)COST。COSTA，BCOSTA，R1COSTR1，R3COSTR3，B也可為覆蓋網(wǎng)絡(luò)的邊AB定義延時(shí)函數(shù)DELAY。DELAYA，BDELAYA，R1DELAYR1，R3DELAYR3，B22同理，可為覆蓋網(wǎng)絡(luò)的每一條邊定義代價(jià)和延時(shí)函數(shù)。覆蓋網(wǎng)絡(luò)利用端用戶和端用戶之間建立的連接來實(shí)現(xiàn)組播服務(wù)，如圖22所示。假定A、B、C、D構(gòu)成了一個(gè)應(yīng)用層組播的覆蓋網(wǎng)絡(luò)。A作為發(fā)送者，B、C、D作為接收者時(shí)的情況。應(yīng)用層組播利用覆蓋網(wǎng)絡(luò)中的邊，即主機(jī)之間建立的鄰居關(guān)系來實(shí)現(xiàn)應(yīng)用層組播的轉(zhuǎn)發(fā)路徑。A將數(shù)據(jù)發(fā)送到B和C，B將數(shù)據(jù)轉(zhuǎn)發(fā)到D。圖22應(yīng)用層組播示意圖應(yīng)用層組播與組播的本質(zhì)區(qū)別在于在口組播中，組播數(shù)據(jù)包的復(fù)制與轉(zhuǎn)發(fā)由路由器完成；在應(yīng)用層組播中，數(shù)據(jù)包的復(fù)制與轉(zhuǎn)發(fā)可以由端用戶，專門的服務(wù)器，或是邊界路由器完成。在應(yīng)用層組播中，端用戶看見的是覆蓋網(wǎng)絡(luò)的拓?fù)洌讓游锢硗負(fù)浔浑[藏了。12第二章基于OVERLAY網(wǎng)絡(luò)的應(yīng)用層組播路由協(xié)議的研究在口組播中，組成員關(guān)系分布在路由器上；在應(yīng)用層組播中，組成員關(guān)系可以保留在RP匯聚點(diǎn)上，源上，每個(gè)組成員上，或者是分散在成員間。覆蓋網(wǎng)絡(luò)的拓?fù)淇梢杂蓱?yīng)用實(shí)現(xiàn)完全的控制。應(yīng)用層組播的目標(biāo)是建立和維護(hù)一個(gè)高效的用于組播數(shù)據(jù)分發(fā)的覆蓋網(wǎng)絡(luò)，在當(dāng)前P組播仍然沒有在INTEMET上實(shí)現(xiàn)廣泛部署的情況下，應(yīng)用層組播服務(wù)可以代替D組播，來實(shí)現(xiàn)群組通信以及其它具有一對(duì)多的通信模型的應(yīng)用。212OVERIAY網(wǎng)絡(luò)的技術(shù)優(yōu)勢(shì)OVERLAY網(wǎng)絡(luò)的特點(diǎn)決定了它的技術(shù)優(yōu)勢(shì)，應(yīng)用層組播基于OVERLAY網(wǎng)絡(luò)實(shí)現(xiàn)是因?yàn)橐韵逻@些原因覆蓋網(wǎng)的實(shí)現(xiàn)無需改變?cè)械挠?、軟件，具有較好的可操作性。在覆蓋網(wǎng)絡(luò)中部署新的功能，無需在每個(gè)節(jié)點(diǎn)上實(shí)施部署，只要在需要該功能的節(jié)點(diǎn)上部署。覆蓋網(wǎng)絡(luò)上的應(yīng)用無需了解下層網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。覆蓋網(wǎng)絡(luò)中的節(jié)點(diǎn)可以根據(jù)自己的需求選擇最合適的鏈路，具有較好的適應(yīng)性。可以在OVERLAY節(jié)點(diǎn)上部署附加的控制機(jī)制，使OVERLAY網(wǎng)絡(luò)具有更好的健壯性。例如在兩個(gè)OVERLAY節(jié)點(diǎn)之間完全可能存在兩條互相獨(dú)立的虛擬鏈路，如果其中之一發(fā)生錯(cuò)誤而失效，還可以通過備用鏈路繼續(xù)節(jié)點(diǎn)之間的通信。由于OVERLAY節(jié)點(diǎn)可以是完成不同任務(wù)的計(jì)算機(jī)，比較容易實(shí)現(xiàn)服務(wù)定制功能。SOVERLAY報(bào)文可以像TCPIP報(bào)文一樣處理，而無需其它特殊的處理機(jī)制。213OVERIAY網(wǎng)絡(luò)的抽象模型覆蓋網(wǎng)絡(luò)的抽象模型可以表示成一個(gè)簡單無向連通圖GY，E。其中V是結(jié)點(diǎn)的集合，表示端用戶。EVV是邊的集合，表示任意兩個(gè)端用戶之間的虛擬連接。對(duì)于1，V和EE可分別定義相應(yīng)的屬性函數(shù)表示網(wǎng)絡(luò)狀態(tài)。13面向仿真的應(yīng)用層組播協(xié)議研究設(shè)尺為正實(shí)數(shù)集合，對(duì)于任意的YV，可以定義D。O屬性函數(shù)。D。OI，IRDO映射到一個(gè)正整數(shù)。DPI表示，節(jié)點(diǎn)的帶寬最多可以支持1，節(jié)點(diǎn)向F個(gè)鄰居轉(zhuǎn)發(fā)組播數(shù)據(jù)。假定節(jié)點(diǎn)1，的輸出帶寬為B洲P，組播流的速率為B。那么D一0P。，V6J圖21的覆蓋網(wǎng)絡(luò)可表示成GV，E礦缸，B，C，DEAB，AC，AD，BC，BD，CD對(duì)于任意的EE，可定義屬性函數(shù)，如212中定義的代價(jià)函數(shù)和延時(shí)函數(shù)。根據(jù)E中的邊，可以求出每個(gè)頂點(diǎn)的鄰居。對(duì)于任意的1，YNEIGHBOR0函甜E對(duì)于圖22，可以求出NEIGHBORAP，C，D。22基于OVERIAY網(wǎng)絡(luò)的應(yīng)用層組播路由的問題描述因?yàn)閼?yīng)用層網(wǎng)絡(luò)是建立在傳統(tǒng)的INTEMET單播結(jié)構(gòu)之上而不是點(diǎn)到點(diǎn)的鏈路之上的虛擬邏輯網(wǎng)絡(luò)。這導(dǎo)致了在資源的配置和操作上同擁有鏈路的網(wǎng)絡(luò)層組播有很大不同。主要體現(xiàn)在以下幾個(gè)方面1網(wǎng)絡(luò)可達(dá)性應(yīng)用層網(wǎng)絡(luò)是全MESH網(wǎng)，每個(gè)節(jié)點(diǎn)通過單播連接都能到達(dá)其它任何節(jié)點(diǎn)。因此，和路由器之間的路徑被定義為物理連接的P組播不同，在應(yīng)用層網(wǎng)絡(luò)中N個(gè)節(jié)點(diǎn)的組播會(huì)話可能有刀”2個(gè)不同的生成樹F81。這就導(dǎo)致了更大的設(shè)計(jì)空間和更高的設(shè)計(jì)復(fù)雜度。2網(wǎng)絡(luò)開銷通常的網(wǎng)絡(luò)開銷主要被定義為圖中所有鏈路開銷的總和。14第一二章基于OVERLAY網(wǎng)絡(luò)的應(yīng)用層組播路由協(xié)議的研究這對(duì)于網(wǎng)絡(luò)提供者來說是合理的，但是從應(yīng)用服務(wù)提供者角度看，應(yīng)用層網(wǎng)絡(luò)開銷包括從服務(wù)站點(diǎn)獲得帶寬的開銷和從主干網(wǎng)上獲得訪問帶寬的開銷。網(wǎng)絡(luò)開銷定義的不同直接影響路由的設(shè)計(jì)和路由的策略。3路由限制傳統(tǒng)的口組播通過最短路徑樹最小化源到全部接收者的時(shí)延，也就是減少需要承載會(huì)話流的鏈路數(shù)。應(yīng)用層組播能夠根據(jù)應(yīng)用需求更靈活的配置不同的路由策略，提供更高質(zhì)量的服務(wù)。221應(yīng)用需要的組播服務(wù)質(zhì)量的抽象描述在應(yīng)用層組播傳輸過程中，端系統(tǒng)需要復(fù)制、轉(zhuǎn)發(fā)數(shù)據(jù)包，直到所有結(jié)點(diǎn)都收到數(shù)據(jù)包為止。由于這些結(jié)點(diǎn)通常是普通的主機(jī)，不能進(jìn)行線速轉(zhuǎn)發(fā)，所以復(fù)制轉(zhuǎn)發(fā)工作消耗的時(shí)間比較大。消耗的時(shí)間與主機(jī)本身的處理能力和執(zhí)行的任務(wù)數(shù)量有關(guān)。如果某個(gè)主機(jī)結(jié)點(diǎn)的下行用戶數(shù)目太多即結(jié)點(diǎn)度大，那么它的工作負(fù)載會(huì)相當(dāng)重，這個(gè)主機(jī)處理消耗的時(shí)間會(huì)較長，或者部分任務(wù)得不到處理。而且樹的時(shí)延還受結(jié)點(diǎn)度的影響。結(jié)點(diǎn)度越小，樹的深度越大，樹的時(shí)延也越大。所以樹的時(shí)延和結(jié)點(diǎn)度分配是相互矛盾的問題。鑒于此，應(yīng)用層組播路由中要考慮節(jié)點(diǎn)度和時(shí)延的平衡問題。對(duì)于不同類型的組播服務(wù)有不同的需求。例如對(duì)于文件傳送應(yīng)用，需要高吞吐率，而不太注重延時(shí)性能。對(duì)于音視頻相關(guān)的應(yīng)用，有實(shí)時(shí)性的要求，就要對(duì)組播樹的延時(shí)進(jìn)行優(yōu)化。將應(yīng)用的這些需求抽象成約束條件和優(yōu)化目標(biāo)。約束條件是指組播樹必須滿足的條件，優(yōu)化目標(biāo)是指組播樹可利用各種算法，如貪婪算法，禁忌算法等盡可能找到滿足約束條件的最優(yōu)解，因?yàn)樵诩s束條件下，可能找不到多項(xiàng)式時(shí)間的最優(yōu)解。定義1樹的直徑DIAMETE對(duì)于樹T中任意節(jié)點(diǎn)VVV，VRV，1，PR，Y為從，到1，沿T上的路徑的所有邊的集合。萬CG為樹T上經(jīng)過YREPR，J的最長的距離，則樹的直徑定義為DIAMETEMAXA1，1，V。定義2剩余度RESIDUALDEGREE對(duì)于樹T中節(jié)點(diǎn)VVY，RESRVVDRV，露Y是樹T中節(jié)點(diǎn)Y的度。由于每個(gè)終端節(jié)點(diǎn)可能不只加入一個(gè)組播會(huì)話，如果某些組播會(huì)話過多地占用了那個(gè)節(jié)點(diǎn)的接口帶寬，15面向仿真的應(yīng)用層組播協(xié)議研究那么有可能出現(xiàn)后續(xù)組播會(huì)話無法建立的現(xiàn)象。為了減少阻止將來組播會(huì)話需求的可能性，我們選擇最大化樹的最小剩余度約束條件通常包括節(jié)點(diǎn)的度約束條件在應(yīng)用層組播中擔(dān)任轉(zhuǎn)發(fā)節(jié)點(diǎn)的是端用戶，端用戶的網(wǎng)絡(luò)資源是有限的，因此端用戶擔(dān)任轉(zhuǎn)發(fā)的負(fù)載應(yīng)該是有限的。節(jié)點(diǎn)的虛擬連接的數(shù)目節(jié)點(diǎn)的鄰居數(shù)目的限制，稱為節(jié)點(diǎn)的度約束條件。節(jié)點(diǎn)的度約束條件用節(jié)點(diǎn)屬性函數(shù)V表示。樹的約束條件是指對(duì)組播樹的直徑、半徑進(jìn)行約束。限制樹上節(jié)點(diǎn)之間的最長路徑。也可對(duì)全樹的代價(jià)進(jìn)行約束。優(yōu)化目標(biāo)可以分為節(jié)點(diǎn)優(yōu)化目標(biāo)和組播樹的優(yōu)化目標(biāo)，通常包括節(jié)點(diǎn)的最大帶寬在節(jié)點(diǎn)支持的范圍內(nèi)最大利用每個(gè)節(jié)點(diǎn)的帶寬。節(jié)點(diǎn)的最大平衡剩余度【14J每個(gè)節(jié)點(diǎn)的剩余度盡可能達(dá)到平衡，這樣可提供較高的接納率【151。樹的優(yōu)化目標(biāo)包括最短路徑樹，最小代價(jià)樹等。222組播路由問題定義假設(shè)下層P網(wǎng)絡(luò)能向端系統(tǒng)提供透明的端到端單播路由，則覆蓋組播的網(wǎng)絡(luò)模型可用一個(gè)完全有向圖GY，E來描述，其中，Y是節(jié)點(diǎn)的集合，表示端系統(tǒng)，EYV是邊的集合，表示虛擬鏈路，每一虛擬鏈路對(duì)應(yīng)于一條下層口網(wǎng)絡(luò)的物理路徑。設(shè)R為正實(shí)數(shù)集合，R為非負(fù)實(shí)數(shù)集合，則VVV，可定義下列屬性參數(shù)輸入帶寬能力函數(shù)既Y專R，表示節(jié)點(diǎn)最大的接收帶寬；輸出帶寬能力函數(shù)既，0Y專R，表示節(jié)點(diǎn)最大的轉(zhuǎn)發(fā)帶寬；代價(jià)函數(shù)CYY哼R，表示節(jié)點(diǎn)的代價(jià)，如端系統(tǒng)設(shè)備的費(fèi)用等。VEE，可定義如下屬性參數(shù)帶寬容量函數(shù)B。0E專R，表示邊上兩節(jié)點(diǎn)之間可獲得的最大帶寬，它由該邊上的端系統(tǒng)節(jié)點(diǎn)的輸入、輸出帶寬能力及其對(duì)應(yīng)的下層物理路徑的瓶頸帶寬決定，即VEG，V，有B。GMINB。，V，砌0，V，既O，其中16第一二章基于OVERLAY網(wǎng)絡(luò)的應(yīng)用層組播路由協(xié)議的研究鈿0，V為邊，Y對(duì)應(yīng)的物理路徑的瓶頸帶寬；延時(shí)函數(shù)見GER，表示邊上兩節(jié)點(diǎn)之間的端到端分組傳輸延時(shí)；抖動(dòng)函數(shù)以GE專R，表示邊上兩節(jié)點(diǎn)之間的端到端分組傳輸延時(shí)抖動(dòng)；分組丟失率函數(shù)GE專R，G【O，1，表示邊上兩節(jié)點(diǎn)之間的端到端分組傳輸丟失率；代價(jià)函數(shù)EGE專R，表示邊的代價(jià)，如網(wǎng)絡(luò)資源占用量等。OVVP西既，P，COP江G，見G，以G，EG，EG圖23覆蓋組播網(wǎng)絡(luò)模型示意圖圖23給出了覆蓋組播網(wǎng)絡(luò)模型的示意圖，該網(wǎng)絡(luò)模型有4個(gè)端系統(tǒng)節(jié)點(diǎn)組成，它們之間通過12條有向邊虛擬鏈路構(gòu)成一完全有向圖，對(duì)于每個(gè)端系統(tǒng)節(jié)點(diǎn)和每條虛擬鏈路分別定義相應(yīng)的屬性參數(shù)。與口組播網(wǎng)絡(luò)模型不同【9】，覆蓋組播網(wǎng)絡(luò)模型中的邊是虛擬鏈路，它可能與其他邊共享端系統(tǒng)節(jié)點(diǎn)和下層物理鏈路的帶寬，這將增加覆蓋組播網(wǎng)絡(luò)中帶寬資源管理的復(fù)雜性。但是，考慮到端系統(tǒng)的接入帶寬和CPU處理能力的限制，當(dāng)端系統(tǒng)成為虛擬鏈路的帶寬瓶頸時(shí)，統(tǒng)P將由端系統(tǒng)的帶寬能力屬性決定，這將簡化上述模型。進(jìn)一步，對(duì)于媒體流的平均帶寬為B的組播組，若VVV，B既，則節(jié)點(diǎn)V的輸出能力帶寬可用“度“來表示，定義度約束屬性D一K，VBJ，即節(jié)點(diǎn)1，最多只能同時(shí)向DO個(gè)下游節(jié)點(diǎn)轉(zhuǎn)發(fā)分組。此時(shí)，覆蓋組播網(wǎng)絡(luò)就可用度約束模型來描述。但是，在上述簡化條件不成立時(shí)，組播應(yīng)用通常采用端到端的測量來估計(jì)虛擬鏈路的可用帶寬。因此，本章下面將從端系統(tǒng)的角度來討論和描述17面向仿真的應(yīng)用層組播協(xié)議研究帶寬參數(shù)。覆蓋組播路由問題的一般形式描述如下給定一個(gè)完全有向圖GV，E，一個(gè)源或根節(jié)點(diǎn)SV，以及目的節(jié)點(diǎn)的集合Y一。對(duì)于一組約束條件C和一個(gè)可能優(yōu)化目標(biāo)D，構(gòu)造一棵G的最優(yōu)生成樹，使其滿足C。根據(jù)上述模型，我們發(fā)現(xiàn)覆蓋組播路由問題的優(yōu)化目標(biāo)和約束條件均可分為二類節(jié)點(diǎn)優(yōu)化和樹優(yōu)化；節(jié)點(diǎn)約束和樹約束。其中，節(jié)點(diǎn)優(yōu)化約束針對(duì)節(jié)點(diǎn)相關(guān)的屬性參數(shù)，如節(jié)點(diǎn)的帶寬或度、節(jié)點(diǎn)的代價(jià)等；樹優(yōu)化約束針對(duì)與組播樹相關(guān)的性能參數(shù)，如樹的延時(shí)直徑或半徑、樹的平均延時(shí)、樹的代價(jià)等。將這些約束條件和優(yōu)化目標(biāo)進(jìn)行組合，可形成下面各種覆蓋組播路由問題1節(jié)點(diǎn)約束具有節(jié)點(diǎn)屬性約束的組播路由問題，如度帶寬約束的組播樹等。2樹約束具有樹性能參數(shù)約束的組播路由問題，如延時(shí)約束的組播樹等。3多樹約束具有多個(gè)樹約束的組播路由問題，如延時(shí)和代價(jià)約束的組播樹等。4節(jié)點(diǎn)和樹約束具有節(jié)點(diǎn)和樹約束的組播路由問題，如度帶寬和延時(shí)約束組播樹等。5節(jié)點(diǎn)優(yōu)化節(jié)點(diǎn)屬性優(yōu)化的組播路由問題，如最小或平均帶寬最大組播樹等。6樹約束節(jié)點(diǎn)優(yōu)化具有樹約束且節(jié)點(diǎn)屬性優(yōu)化的組播路由問題，如延時(shí)約束的剩余度帶寬平衡組播樹等。7樹優(yōu)化樹性能參數(shù)優(yōu)化的組播路由問題，如延時(shí)或代價(jià)最小組播樹等。8節(jié)點(diǎn)約束樹優(yōu)化具有節(jié)點(diǎn)約束且樹優(yōu)化的組播路由問題，如度帶寬約束的延時(shí)或代價(jià)最小組播樹等。9樹約束樹優(yōu)化具有樹約束且樹優(yōu)化的組播路由問題，如延時(shí)約束的代價(jià)最小組播樹等。10節(jié)點(diǎn)和樹約束樹優(yōu)化具有節(jié)點(diǎn)和樹約束且樹優(yōu)化的組播路由問題，第二章基于OVERLAY網(wǎng)絡(luò)的應(yīng)用層組播路由協(xié)議的研究如度帶寬和延時(shí)約束的代價(jià)最小組播樹等。表21覆蓋組播路由問題分類表無優(yōu)化節(jié)點(diǎn)優(yōu)化樹優(yōu)化無約束5節(jié)點(diǎn)優(yōu)化7樹優(yōu)化NP完全”復(fù)雜度多項(xiàng)式復(fù)雜度節(jié)點(diǎn)約束1節(jié)點(diǎn)約束8節(jié)點(diǎn)約束樹優(yōu)化多項(xiàng)式復(fù)雜度2QP完全”復(fù)雜度樹約束2樹約束6樹約束節(jié)點(diǎn)優(yōu)化9樹約束樹優(yōu)化多項(xiàng)式復(fù)雜度NP完全”復(fù)雜度NP完全”復(fù)雜度3多樹約束NP完全”復(fù)雜度節(jié)點(diǎn)和樹約束4節(jié)點(diǎn)和樹約束10節(jié)點(diǎn)和樹約束樹NP完全”復(fù)雜度優(yōu)化NP完全”復(fù)雜度問題1容易在多項(xiàng)式時(shí)間內(nèi)解決，如對(duì)于度約束組播樹的構(gòu)造，可從源節(jié)點(diǎn)開始，每次選擇任一未成樹的節(jié)點(diǎn)加入到樹上任意有剩余度的節(jié)點(diǎn)，直到所有節(jié)點(diǎn)都加入樹為止。問題7可分為延時(shí)半徑源到最遠(yuǎn)節(jié)點(diǎn)的延時(shí)最小樹、延時(shí)直徑最遠(yuǎn)兩節(jié)點(diǎn)之間延時(shí)最小樹、代價(jià)最小樹等問題。不難發(fā)現(xiàn)，從源節(jié)點(diǎn)到所有目的節(jié)點(diǎn)構(gòu)成的星型STAR樹，其延時(shí)半徑最??；HASSIN等【10】貝LJ提出了在多項(xiàng)式時(shí)間內(nèi)尋找延時(shí)直徑最小樹的算法；而代價(jià)最小生成樹可以采用PRIM算法解決。另外，問題7的算法可用于解決問題2。所以，問題2和7都是多項(xiàng)式問題。根據(jù)WANG等的結(jié)論【11】，問題3屬于多個(gè)“相加型“約束組合問題，是“NP完全“的【12】。問題9中的延時(shí)約束的代價(jià)最小生成樹問題也是“NP難NPHARD問題【131。GARG掣14】證明了問題5中的最小帶寬最大樹的構(gòu)造是“NP難“的，則平均帶寬最大樹也是“NP難“的。現(xiàn)已證明，度約束的延時(shí)平均延時(shí)、半徑、直徑最小以及代價(jià)最小生成樹問題都是“套IP難“【15】或“NP完全”的【16】【17】【18】。SIFT等【16】還證明了延時(shí)約束度平衡生成樹問題是“NP完全“問題。由此易知，問題4、6、8、19面向仿真的應(yīng)用層組播協(xié)議研究10都具有“NP完全”復(fù)雜度。覆蓋組播路由問題的分類匯總，如表21所示。在上述問題中，問題1過于簡單，沒有單獨(dú)研究的價(jià)值。問題2、3、7、9與節(jié)點(diǎn)的屬性無關(guān)，可以歸結(jié)為IP組播路由問題的特例，不是覆蓋組播路由研究的重點(diǎn)。因此，當(dāng)前覆蓋組播路由協(xié)議和算法重點(diǎn)解決的問題在于4、5、6、8、10。23現(xiàn)有的應(yīng)用層組播方案圖24給出了目前主要的應(yīng)用層組播方案分類及每種分類的代表【191。方案主要分為集中式算法和分布式算法兩大類，其中每類又包含幾種類型。ALMIHBM分布式算法I曲自由NE【FADAYOLD0VERCATSCRIBECATLERC丑畦TBCPHMTPPROMISEB哆呲NICEZIG瑚鬻PRE齜ADIT眥圖24當(dāng)前的應(yīng)用層組播方案集中式系統(tǒng)中通常由一個(gè)節(jié)點(diǎn)來集中控制和處理節(jié)點(diǎn)的加入、離開和失效，因此效率較高，但同時(shí)也限制了系統(tǒng)的可擴(kuò)展性，現(xiàn)有的系統(tǒng)有ALMI和HBM；分布式系統(tǒng)可以接納較多用戶，具有較好的可擴(kuò)展性，但是對(duì)節(jié)點(diǎn)的加入、離開和失效的處理效率較低。分布式系統(tǒng)按組播樹構(gòu)建的順序，又可以分為樹優(yōu)先TREEFIRST，轉(zhuǎn)發(fā)網(wǎng)優(yōu)先MESHFIRST和隱式構(gòu)建組播樹IMPLICIT種。應(yīng)用層組播協(xié)議中一般定義兩種拓?fù)浣Y(jié)構(gòu)，控制拓?fù)浜蛿?shù)據(jù)轉(zhuǎn)發(fā)拓?fù)洹＝M成員通過控制拓?fù)鋫鬟f和更新信息，互相之間辨別是否仍然“活躍“，還是已經(jīng)失效或離開，控制拓?fù)淇赡艽嬖诨芈?，又稱為轉(zhuǎn)發(fā)網(wǎng)MESH；而數(shù)據(jù)轉(zhuǎn)發(fā)拓?fù)渫ǔＪ强刂仆負(fù)涞膫€(gè)子集，組播數(shù)據(jù)第二章基于OVERLAY網(wǎng)絡(luò)的應(yīng)用層組播路由協(xié)議的研究沿轉(zhuǎn)發(fā)拓?fù)鋫鬟f，因此它不能存在回路，也稱為組播樹TREE。樹優(yōu)先方式先生成組播樹，再生成轉(zhuǎn)發(fā)網(wǎng)，適合對(duì)延時(shí)敏感的應(yīng)用，如實(shí)時(shí)應(yīng)用，現(xiàn)有的系統(tǒng)如YOID、OVERCAST、TBCP、HMTP、NICE、ZIGZAG等；轉(zhuǎn)發(fā)網(wǎng)優(yōu)先方式先構(gòu)造一個(gè)有冗余鏈路的轉(zhuǎn)發(fā)網(wǎng)，再使用如DVMRP這樣的路由協(xié)議在轉(zhuǎn)發(fā)網(wǎng)的基礎(chǔ)上構(gòu)建組播樹。這種方式可以檢測到組播樹節(jié)點(diǎn)的失效和組播樹的斷裂，并進(jìn)行高效的恢復(fù)和處理，適用于底層網(wǎng)絡(luò)性能不好或可靠性較差的情況。由于它的可擴(kuò)展性較差，適用于規(guī)模較小的組，比較著名的有NARADA、SCATTERCAST、BAYEUX等；隱式方式是基于某種特性隱式地構(gòu)建控制拓?fù)?，同時(shí)構(gòu)建轉(zhuǎn)發(fā)網(wǎng)和樹，兩種拓?fù)涞霓D(zhuǎn)化不需要額外的成員之間的交互，適合規(guī)模較大的組播組，現(xiàn)有的系統(tǒng)如SCRIBE、PROMISE、SPREADLT、SPLITSTREAM等。231集中式算法集中式算法如ALMI201、HBM211。集中式算法中存在一個(gè)總控模塊，總控模塊是一個(gè)獨(dú)立的運(yùn)行實(shí)體，總控模塊需要被所有的成員訪問?？偪啬K可以放在一個(gè)組成員通常是組播組的發(fā)起者所在的主機(jī)，也可以放在一個(gè)專門的服務(wù)器上，或是向ISP租用的組播代理服務(wù)器上。如ALMI中的會(huì)話控制器SESSIONCONTROLLER201，HBM中的RP21】模塊。集中式算法內(nèi)又細(xì)分為兩種，差別是成員節(jié)點(diǎn)對(duì)應(yīng)用層組播的組播組成員關(guān)系了解的程度，分為部分了解和完全了解兩種。1集中式算法的思想是1總控模塊與組成員之間、組成員之間通過單點(diǎn)投遞路徑交換控制信息。2總控模塊負(fù)責(zé)處理成員加入、根據(jù)搜集的控制信息計(jì)算組播樹和維護(hù)組播樹。3總控模塊向每個(gè)組成員發(fā)出指示，需要監(jiān)控與哪些其它組成員之間的“距離“參數(shù)，“距離是組成員之間的單點(diǎn)投遞路徑的度量參數(shù)，在ALMI和HBM中“距離“是組成員之間的延時(shí)。4組成員根據(jù)總控模塊的指示，實(shí)行監(jiān)測，周期性的向總控模塊報(bào)告。5總控模塊根據(jù)所有成員的監(jiān)測信息，根據(jù)組播樹算法計(jì)算組播樹。在ALMI中，采用了度約束的最小代價(jià)樹；在HBM中，采用將低帶寬、不穩(wěn)定的21面向仿真的應(yīng)用層組播協(xié)議研究節(jié)點(diǎn)逐漸推向組播樹的葉的算法。6總控模塊將計(jì)算的結(jié)果中與每個(gè)成員相關(guān)的部分告訴每個(gè)成員，計(jì)算結(jié)果通常是P口地玎F，CHIM對(duì)，這樣每個(gè)成員可得知其在組播樹上的父節(jié)點(diǎn)和子節(jié)點(diǎn)。7成員通過組播樹負(fù)責(zé)對(duì)組播數(shù)據(jù)進(jìn)行轉(zhuǎn)發(fā)，不需要總控模塊干預(yù)。8總控模塊負(fù)責(zé)在新成員加入和成員離開、網(wǎng)絡(luò)失效、成員失效時(shí)，維護(hù)組播樹的連通。2集中式算法的優(yōu)勢(shì)可以提供較好的可靠性，減少組成員處理組成員管理和維護(hù)組播樹的開銷?？偪啬K與組成員之間只使用單點(diǎn)投遞路徑交換控制信息，不會(huì)造成較大的數(shù)據(jù)流量。3集中式算法的缺陷在于擴(kuò)展性較差，適用于組播組的組成員數(shù)目較小的情況。并且因?yàn)橐蕾囉诳偪啬K計(jì)算組播樹、維護(hù)、處理新成員加入，因此總控模塊容易成為系統(tǒng)的瓶頸，也會(huì)造成單點(diǎn)失效的情況。ALMI屬于節(jié)點(diǎn)約束下的樹優(yōu)化算法，集中式算法還有CT221算法一度約束的最小直徑生成樹MDDLT221，CT同屬于節(jié)點(diǎn)約束下的樹優(yōu)化。BCTT23