【大學(xué)】信息通信專業(yè) 應(yīng)用層組播tree結(jié)構(gòu)的探討

應(yīng)用層組播tree結(jié)構(gòu)的探討編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討一、綜述1、組播算法組播算法的基本出發(fā)點(diǎn)是：在存在多個接收者的時，通過合并重復(fù)信息的傳輸來達(dá)到減少帶寬浪費(fèi)和降低服務(wù)器處理負(fù)擔(dān)的目的。編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討一、綜述2、應(yīng)用層組播的提出近年來，隨著Peer-to-PeerNetwork和OverlayNetwork等技術(shù)的提出，出現(xiàn)了“應(yīng)用層組播”（ALM:ApplicationLayerMulticast）這樣一個研究方向。編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討一、綜述3、應(yīng)用層組播的主要思想保持Internet原有的“單播、盡力發(fā)送”模型，盡量不改變原來網(wǎng)絡(luò)的體系結(jié)構(gòu)，而主要通過增加端系統(tǒng)的功能來實(shí)現(xiàn)組播的功能。由于對網(wǎng)絡(luò)本身的改變很少，應(yīng)用層組播具有很好的靈活性。但是，端系統(tǒng)的穩(wěn)定性一般不如專用網(wǎng)絡(luò)設(shè)備，應(yīng)用層組播在帶寬利用效率方面也無法和IP組播相比。另外，應(yīng)用層組播中的系統(tǒng)框架和很多細(xì)節(jié)技術(shù)也還在研究當(dāng)中。這些問題的存在為應(yīng)用層組播的研究提供了廣闊的空間。媒體編碼技術(shù)、Peer-to-Peer和OverlayNetwork等技術(shù)的發(fā)展對應(yīng)用層組播的研究也有很大的促進(jìn)作用編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討一、綜述4、應(yīng)用層組播和IP組播的不同和IP組播增加網(wǎng)絡(luò)機(jī)制的方法不同:應(yīng)用層組播的基本思想是保Internet原有的簡單、不可靠、單播的轉(zhuǎn)發(fā)模型，由端系統(tǒng)來實(shí)現(xiàn)組播轉(zhuǎn)發(fā)的功能。這也是著名的”end-to-endargument”所倡導(dǎo)的思想。編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討一、綜述5、應(yīng)用層組播算法的設(shè)計中的假設(shè)(1)網(wǎng)絡(luò)中的帶寬和轉(zhuǎn)發(fā)資源是相對豐富的，而服務(wù)器的能力是一個主要瓶頸。使用應(yīng)用層組播會比IP組播消耗更多的帶寬，但是和單播方案相比，它還是可以有效的降低服務(wù)器的負(fù)載和減少帶寬的使用。編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討一、綜述5、應(yīng)用層組播算法的設(shè)計中的假設(shè)(2)大多數(shù)參與組播的端系統(tǒng)可以貢獻(xiàn)出一部分資源用于組播的轉(zhuǎn)發(fā)。這個假設(shè)并不是針對所有的應(yīng)用層組播算法，但是不少的應(yīng)用層組播算法都有這個假設(shè)。編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討一、綜述5、應(yīng)用層組播算法的設(shè)計中的假設(shè)(3)上層應(yīng)用對性能的要求并不很苛刻，可以容忍報文的丟失和較大的延遲。Internet的可靠性本來就無法完全保證，參與組播的主機(jī)性能也無法保證。所以，應(yīng)用層組播并不針對所有的應(yīng)用，而主要針對那些對可靠性和性能要求較低的應(yīng)用。編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討一、綜述6、應(yīng)用層組播的主要優(yōu)勢（1）應(yīng)用層組播便于實(shí)現(xiàn)和推廣。它只需要改變端系統(tǒng)，而不需要對路由器進(jìn)行任何修改。（2）應(yīng)用層組播便于針對特定應(yīng)用進(jìn)行優(yōu)化，可以針對不同的應(yīng)用使用不同的實(shí)現(xiàn)方案，而不必象IP組播那樣必須統(tǒng)一到一個模型中。編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討一、綜述7、應(yīng)用層組播的主要缺點(diǎn)（1）一般會比IP組播使用更多的網(wǎng)絡(luò)資源。（2）由于參與轉(zhuǎn)發(fā)的端系統(tǒng)可能不穩(wěn)定，導(dǎo)致組播轉(zhuǎn)發(fā)的可靠性受到影響。（3）由于參與轉(zhuǎn)發(fā)的端系統(tǒng)的性能無法保證，可能導(dǎo)致延遲、轉(zhuǎn)發(fā)速率等性能的下降。編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討一、綜述8、應(yīng)用層組播的主要應(yīng)用基于這些特點(diǎn)，目前應(yīng)用層組播的研究主要集中于視頻會議系統(tǒng)、媒體流的分發(fā)系統(tǒng)（如視頻廣播）和訂閱/分發(fā)系統(tǒng)（Publish/SubscribeSystem）等。應(yīng)用層組播的主要應(yīng)用是實(shí)時的多媒體傳輸。一方面這利用了多媒體信息的性質(zhì)，即在傳輸鏈路質(zhì)量下降的情況下，用戶仍然可以利用收到的低速率的或者不完整的信息，這適用于同一組播組中的多個用戶可能接收能力不同的情況。而文件傳輸?shù)瓤煽總鬏攧t沒有這樣的性質(zhì)。另一方面也發(fā)揮了組播“時間上集中、空間上分布”的特點(diǎn)。編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討一、綜述

Overlay是一個應(yīng)用層組播解決方案的完整的部分，它是影響多點(diǎn)通信的基本機(jī)制。其節(jié)點(diǎn)可以邏輯地組織成兩種拓?fù)浣Y(jié)構(gòu)，即控制拓?fù)浜蛿?shù)據(jù)拓?fù)??？刂仆負(fù)鋽y帶控制信息，如heartbeat信息，更新信息，網(wǎng)絡(luò)探測和探測數(shù)據(jù)等。數(shù)據(jù)拓?fù)溆蓪?shí)際數(shù)據(jù)交付至多端的路徑組成?？刂仆?fù)涞墓?jié)點(diǎn)不必是多播組成員，因此控制拓?fù)涫菙?shù)據(jù)拓?fù)涞某?，他是大多?shù)采用tree結(jié)構(gòu)的數(shù)據(jù)拓?fù)涞臉?biāo)準(zhǔn)，而且是易于建立和有效的?？刂仆?fù)浼俣ㄒ粋€mesh形式的分離的物理結(jié)構(gòu)，在這個結(jié)構(gòu)中，拓?fù)淅锏墓?jié)點(diǎn)占用較高的連接，或者像數(shù)據(jù)拓?fù)湟粯臃窒硗唤Y(jié)構(gòu)。依據(jù)采用的途徑，overlay拓?fù)淇梢苑殖扇齻€部分：tree，Mesh-Tree，植入結(jié)構(gòu)。編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討二、關(guān)于tree的一些概念和分析1、幾種常見的tree結(jié)構(gòu)（1）應(yīng)用層組播體系

(ApplicationLayerMulticastArchetecutre,ALMA)早期的ALMA版本依據(jù)網(wǎng)絡(luò)距離如RTT(roundtriptime)，選擇離自己最近的節(jié)點(diǎn)作為自己的父節(jié)點(diǎn)。在新的版本中，ALMA依據(jù)丟失率和RTT的共同考慮來選擇父節(jié)點(diǎn)。組成員定期向DS提供它們的丟失率。通過端對端的測量方法收集成員至成員的RTT。Gossip-style算法用來在成員離開tree時的分割恢復(fù)。組成員通過定期地和一些gossipcandidates交換丟失率和RTT以選擇更好的父節(jié)點(diǎn)。編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討圖1ALMA結(jié)構(gòu)。

編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討二、關(guān)于tree的一些概念和分析1、幾種常見的tree結(jié)構(gòu)（2）香蕉tree協(xié)議（BananaTreeProtocal,BTP）

BTP利用基于接收的、自組織的途徑建立共享數(shù)據(jù)tree。它被設(shè)計用來分布式文件共享應(yīng)用。第一個加入組的主機(jī)成為tree的根，后加入的新成員學(xué)習(xí)根并加入到tree中。其算法是允許一個節(jié)點(diǎn)轉(zhuǎn)到一個同屬節(jié)點(diǎn)，如果該同屬節(jié)點(diǎn)比這個節(jié)點(diǎn)的父節(jié)點(diǎn)更接近該節(jié)點(diǎn)。同屬節(jié)點(diǎn)在每個節(jié)點(diǎn)內(nèi)維護(hù)的信息由節(jié)點(diǎn)的父節(jié)點(diǎn)更新。編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討圖2顯示同屬節(jié)點(diǎn)轉(zhuǎn)換可以降低tree開銷

。

編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討二、關(guān)于tree的一些概念和分析1、幾種常見的tree結(jié)構(gòu)（2）香蕉tree協(xié)議（BananaTreeProtocal,BTP）滿足以下兩個條件：

其一，當(dāng)一個節(jié)點(diǎn)在自己轉(zhuǎn)換進(jìn)程中能夠拒絕其他所有的轉(zhuǎn)換嘗試；

其二，節(jié)點(diǎn)必須把當(dāng)前父節(jié)點(diǎn)的信息包含在轉(zhuǎn)換請求中以便潛在的父節(jié)點(diǎn)能確認(rèn)其為真正的同屬節(jié)點(diǎn)。

能防止如圖3中的同時轉(zhuǎn)換引起的循環(huán)和圖4中的過期信息引起的循環(huán)。編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討圖3同時轉(zhuǎn)換引起的循環(huán)編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討圖4過期信息引起的循環(huán)編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討二、關(guān)于tree的一些概念和分析1、幾種常見的tree結(jié)構(gòu)（3）主機(jī)多播（HostMulticast,HM）HM的目的是用以提供應(yīng)用中的高效的多播交付服務(wù)和能于ip多播在最大程度上的共容。它自動連接IP多播島并通過單播隧道提供多播給不能多播的端主機(jī)。經(jīng)由指定成員（DesignatedMember,DM）之間的UDP隧道，多播島就連接起來了，每一個島選擇一個DM。

編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討圖5HM結(jié)構(gòu)

編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討二、關(guān)于tree的一些概念和分析1、幾種常見的tree結(jié)構(gòu)（3）主機(jī)多播（HostMulticast,HM）數(shù)據(jù)分配tree是共享tree，任何成員都可以成為一個源。 HM利用分布式tree建立協(xié)議來度量組成員的數(shù)量。編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討圖6在共享樹上新成員H通過集合點(diǎn)（RendezvousPoint,RP）發(fā)現(xiàn)根A編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討二、關(guān)于tree的一些概念和分析1、幾種常見的tree結(jié)構(gòu)（3）主機(jī)多播（HostMulticast,HM）圖6顯示的是在共享樹上新成員H通過集合點(diǎn)（RendezvousPoint,RP）發(fā)現(xiàn)根A。H把A當(dāng)作潛在的父節(jié)點(diǎn)并請求A的子節(jié)點(diǎn)列表，沿著樹徑一路搜索下來，根據(jù)距離A最近的原則，H選擇F作為自己的父節(jié)點(diǎn)。HM中的每一個成員都維護(hù)其到根節(jié)點(diǎn)A的路徑信息。每一個成員都要定期通過阻止一些來自根路徑上的隨機(jī)成員的加入進(jìn)程來尋找跟近的父節(jié)點(diǎn)。HM利用循環(huán)探測機(jī)制代替循環(huán)避免機(jī)制。為了從樹分割中恢復(fù)，每一個成員都可以重新加入任何一個新成員在它的根路徑或者緩存上，緩存在成員沿著樹徑“走”下來的初始進(jìn)程中建立。編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討二、關(guān)于tree的一些概念和分析1、幾種常見的tree結(jié)構(gòu)(4)重疊網(wǎng)多播網(wǎng)絡(luò)結(jié)構(gòu)（OverlayMulticastNetworkInfrastructuer,OMNI）

OMNI從一組多播服務(wù)節(jié)點(diǎn)（multicastservicenodes,MSN）建立一個單一源節(jié)點(diǎn)樹結(jié)構(gòu),如圖7所示。重疊網(wǎng)tree的建立過程包括一個在數(shù)據(jù)交付開始前的離線初始化階段和數(shù)據(jù)交付過程中的動態(tài)的自組織進(jìn)程。OMNI的關(guān)鍵特性是關(guān)鍵基于服務(wù)組大小（所服務(wù)的客戶機(jī)數(shù)量）的不同的MSN的動態(tài)優(yōu)先級來迭代優(yōu)化重疊網(wǎng)tree，動態(tài)自組織進(jìn)程如圖8所示。編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討圖7OMNI從一組多播服務(wù)節(jié)點(diǎn)（multicastservicenodes,MSN）建立一個單一源節(jié)點(diǎn)樹結(jié)構(gòu),編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討圖8動態(tài)自組織進(jìn)程編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討二、關(guān)于tree的一些概念和分析1、幾種常見的tree結(jié)構(gòu)(4)重疊網(wǎng)多播網(wǎng)絡(luò)結(jié)構(gòu)（OverlayMulticastNetworkInfrastructuer,OMNI）在開始的結(jié)構(gòu)MSN0到MSNx的時延是59ms，客戶機(jī)增加，MSN的重要性也相應(yīng)地增加，它首先把父節(jié)點(diǎn)改到MSN6上將時延降為54ms，然后改到MSN0上降為51ms。隨后其客戶減少，x也就從樹上往下移動，同時有其他MSN的客戶的增加引起其上移，為了協(xié)調(diào)時延，每個MSN之間定期交換，在交換能減少當(dāng)前平均時延的情況下，交換僅限于兩層之間的交換。編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討二、關(guān)于tree的一些概念和分析1、幾種常見的tree結(jié)構(gòu)（5）TreeBuildingControlProtocal(TBCP)TBCP的目的是提供高效和分布式的協(xié)議來為應(yīng)用層多播建立控制數(shù)據(jù)交付tree。如圖9所示，新成員M像C1，C2，C3一樣要加入到P上，如果最新的結(jié)構(gòu)是最優(yōu)的，M加入到P，而C3則要重新開始加入過程最后加入到M上。編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討圖9編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討二、關(guān)于tree的一些概念和分析1、幾種常見的tree結(jié)構(gòu)另外還有ApplicationLevelMulticastInfrastructure，Overcast’s等樹結(jié)構(gòu)。編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討三、Tree結(jié)構(gòu)發(fā)展的一種新型算法1、利用分層編碼主要存在的問題其一，是由于流技術(shù)的特性限制，子節(jié)點(diǎn)的接收率是不能超過父節(jié)點(diǎn)的接收率，如圖1所示，主機(jī)B是主機(jī)A的子節(jié)點(diǎn)，即便B有更高的下載帶寬也不能獲得更高的數(shù)據(jù)速率，因?yàn)锳的速率不高。在這種情況下，分層編碼不能充分利用而且每臺主機(jī)在選擇父節(jié)點(diǎn)時必須謹(jǐn)慎。編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討三、Tree結(jié)構(gòu)發(fā)展的一種新型算法1、利用分層編碼主要存在的問題編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討三、Tree結(jié)構(gòu)發(fā)展的一種新型算法1、利用分層編碼主要存在的問題其二，尋找一個適當(dāng)?shù)母钢鳈C(jī)是很復(fù)雜的，通常，新加入ALMtree的主機(jī)都是葉子主機(jī)，它通過交換帶寬信息搜尋鄰居主機(jī)，并找到擁有自己需要的前向數(shù)據(jù)速率的主機(jī)。然而，這種進(jìn)程是復(fù)雜而費(fèi)時的。而且因?yàn)槠浼尤雝ree中只能獲得重疊網(wǎng)的本地信息的緣故，它將很難通過適當(dāng)?shù)姆绞降玫蕉酥鳈C(jī)。編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討三、Tree結(jié)構(gòu)發(fā)展的一種新型算法2、“degree”的參數(shù)它原本是描述一臺父主機(jī)能維護(hù)多少臺主機(jī)。其數(shù)值取決于父主機(jī)的前向吞吐量。一臺主機(jī)i的前向吞吐量是Fi，單一流數(shù)據(jù)率是R，degree值Di的表達(dá)式為

Di＝Fi/R（1）編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討三、Tree結(jié)構(gòu)發(fā)展的一種新型算法3、解決分層編碼存在的問題為了解決利用分層編碼主要存在的問題，這里重定義“degree”的參數(shù)。以使每臺主機(jī)能夠恰當(dāng)?shù)貨Q定自己的父主機(jī)，利用這個方法的一個好處就是這個值是事先知道的，因此每個新成員加入ALMtree時不必再搜索父主機(jī)，顯而易見地，通過這種參數(shù)方法，當(dāng)父主機(jī)離開tree時，不是所有的后代主機(jī)決定他們的父主機(jī)。圖2，顯示的是所有主機(jī)的degree是2，主機(jī)B（或A）將不能再連到G上因?yàn)楦腹?jié)點(diǎn)P的離開，它必須搜尋另一臺有未使用degree的主機(jī)。最簡單的方法是向新加入成員那樣，重新加入tree中，但是這會消耗很多恢復(fù)時間和overhead。

編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討三、Tree結(jié)構(gòu)發(fā)展的一種新型算法編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討三、Tree結(jié)構(gòu)發(fā)展的一種新型算法4、“degree”的參數(shù)的重定義在互聯(lián)網(wǎng)上，一個邊緣路由器和每臺主機(jī)之間的訪問連接特別是上行連接的帶寬通常比干線連接窄。因此，一般考慮發(fā)送端主機(jī)連接是P2P網(wǎng)絡(luò)的瓶頸，基于這一點(diǎn)，degree限制參數(shù)描述的是如（1）式所述的父主機(jī)擁有多少主機(jī)。這樣就很容易參考這個參數(shù)來決定一個新成員是否加入父主機(jī)，在ALM的分層編碼的應(yīng)用中，流速率R不是固定不變的，需要重新定義。編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討三、Tree結(jié)構(gòu)發(fā)展的一種新型算法4、“degree”的參數(shù)的重定義

首先，用R1代替R，R1為基層速率Di=Fi/R1(2)

編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討三、Tree結(jié)構(gòu)發(fā)展的一種新型算法4、“degree”的參數(shù)的重定義其次，R1假定為1，實(shí)時數(shù)值比例提供的每一層“積累”速率賦予R1，新的degree描述父主機(jī)擁有的流的數(shù)量，例如，多播流速率為{50,50,100}kbps,主機(jī)I的發(fā)送吞吐量為300kbps,根據(jù)（2）式，主機(jī)的degree為6，積累速率的比率為1：2：4，這樣，主機(jī)I有4個基層流和1個第二層流（1×4＋2×1＝6）或1個第二層流和一個第三層流（2×1＋4×1＝6），這個degree稱為outdegree，在接收端描述的叫indegree。

編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討三、Tree結(jié)構(gòu)發(fā)展的一種新型算法4、“degree”的參數(shù)的重定義

最后確定indegree和outdegree之間的關(guān)系，在ALM視頻流系統(tǒng)中，每臺主機(jī)為交換接收服務(wù)都要貢獻(xiàn)一部分帶寬，提供不了多少前向速率的接收就少，因此，主機(jī)的indegree限制在小于或等于outdegree：indegree<=outdegree(3)編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討三、Tree結(jié)構(gòu)發(fā)展的一種新型算法5、Tree結(jié)構(gòu)的建立編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討三、Tree結(jié)構(gòu)發(fā)展的一種新型算法5、Tree結(jié)構(gòu)的建立Step.1:Sendajoin-requestmassagetothesource

NewparticipanthostNsendsajoin-requestmassagetothesourcewithitsinandoutdegreesinformation.Thesourceaddressanddegreeinformationarealreadyknown.編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討三、Tree結(jié)構(gòu)發(fā)展的一種新型算法5、Tree結(jié)構(gòu)的建立Step.2:Searchforcandidatesoftheparenthost

Allhostsmaintainthedegreeinformationofitselfanditschildrenandgrand-children.Thehostreceivingthejoin-request(atfirst,thesource)referstoitsdegreeinformationandN.sone,itbecomestheparentcandidateofhostNwheneachofthefollowingtwoconditionsissatisfiedatleast.Otherwise,itforwardstherequestmessagetoitschildrenandthisprocessmightberepeated.編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討三、Tree結(jié)構(gòu)發(fā)展的一種新型算法5、Tree結(jié)構(gòu)的建立Step.2:Searchforcandidatesoftheparenthost

_N’sin-degree≦its(remaining)out-degree_N’sout-degree≧maximumofitschildrenhosts.outdegreesThesecondconditionisbasedontheconceptthathostswhichhavebigout-degreesshouldbeinhigher-positionofthetree.ThisistheincentiveideaasdescribedpreviouslyinSection4.1.WhenN.sout-degreeisbiggerthanthoseofthechildrenhosts,Nisinhigher-positionofthetreeandcantakemoreadvantageofvariouspointsthanotherhosts.編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討三、Tree結(jié)構(gòu)發(fā)展的一種新型算法5、Tree結(jié)構(gòu)的建立Step.3:Decidetheparent

TheparentcandidatessendtheirresponsemessagestohostNandhostNmeasuresRTTsrespectively.Then,hostPwhichhastheminimumRTTisdecidedtobetheparenthostofN.編輯ppt應(yīng)用層組播tree結(jié)構(gòu)的探討三、Tree結(jié)構(gòu)發(fā)展的一種新型算法5、Tree結(jié)構(gòu)的建立Step.4:Exchangelinkconnectionslocally

Underthecondition①atStep2,hostNisconnectedtohostPsimplyandNbecomesa