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

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