【大學(xué)課件】信息通信專業(yè)：應(yīng)用層組播方案舉例

1、 應(yīng)用層組播應(yīng)用層組播應(yīng)用層組播方案舉例編輯課件應(yīng)用層組播分類應(yīng)用層組播分類現(xiàn)有的應(yīng)用層組播主要可以分為4大類：1.分發(fā)算法 Mesh-first方法 Tree-first方法 Implicit方法2.集中算法應(yīng)用層組播的體系結(jié)構(gòu)(ALMI）3.基于優(yōu)先度的應(yīng)用層組播 4.基于空間坐標(biāo)的應(yīng)用層組播編輯課件應(yīng)用層組播算法舉例應(yīng)用層組播算法舉例1. TAG2. ALMI3. 基于優(yōu)先度的應(yīng)用層組播基于優(yōu)先度的應(yīng)用層組播4. 三維三維Delaunary三角網(wǎng)三角網(wǎng)5. 組播方案比較組播方案比較6. 總結(jié)總結(jié)編輯課件TAGlTopology Aware GroupingPurdue Universit

2、y提出Tree-first方法將延遲作為最重要的指標(biāo)，同時(shí)考慮帶寬編輯課件1.1 TAG：路徑匹配算法：路徑匹配算法(1) lComplete Path Matching Algorithmlfamily table (FT) 定義了當(dāng)前節(jié)點(diǎn)的父子關(guān)系 IPaddr（A）：指明節(jié)點(diǎn)A的IP地址 P（S，A）：節(jié)點(diǎn)S到A的最短路徑 len（P）：P所經(jīng)過(guò)的路由器數(shù)l 基于最小延時(shí)構(gòu)建算法，減少傳播過(guò)程中數(shù)據(jù)的復(fù)制次數(shù)l 主要思想是使新加入的節(jié)點(diǎn)和父節(jié)點(diǎn)能夠共用盡可能長(zhǎng)的網(wǎng)絡(luò)路徑。 編輯課件TAG：路徑匹配算法：路徑匹配算法(2)l 路由匹配算法 存在三種情況如下圖：（a）新成員D8將成為D4的子

3、節(jié)點(diǎn)（b）D8加入FT表。D4、D7將成為D8的子成員， 且從當(dāng)前FT表中退出。（c）D8加入FT表編輯課件1.2 TAG：組播：組播Tree構(gòu)建構(gòu)建l成員加入新節(jié)點(diǎn)N發(fā)送JOIN消息給根節(jié)點(diǎn)S，S收到后計(jì)算到N需經(jīng)過(guò)的路由器數(shù)（spath），執(zhí)行路徑匹配算法。會(huì)有兩種結(jié)果：1）N成為S的子節(jié)點(diǎn)，相應(yīng)的修改S的FT（family table）表2）發(fā)送FIND消息（包括N的IP地址， spath ）到子節(jié)點(diǎn)，子節(jié)點(diǎn)在執(zhí)行相應(yīng)的路由匹配算法，直到找到N的父節(jié)點(diǎn)。編輯課件TAG：組播：組播Tree構(gòu)建構(gòu)建節(jié)點(diǎn)加入的一個(gè)具體的實(shí)例1）D1的加入 D1發(fā)送JOIN消息給根節(jié)點(diǎn)S，D1成為 S的子節(jié)點(diǎn)，

4、且修改其FT表，見(jiàn)圖（a）2）D2的加入，圖（b）S根據(jù)spath的值（R1，R2，R4）執(zhí)行路徑匹配算法，發(fā)現(xiàn)D1作為D2的 父節(jié)點(diǎn)比其本身要好，于是S發(fā)送FIND消息給D13）D3的加入，圖（c）與D2類似，選擇D2為其父節(jié)點(diǎn)編輯課件TAG：組播：組播Tree構(gòu)建構(gòu)建4）D4的加入，圖（d） D4加入時(shí)，決定D1作為其父節(jié)點(diǎn)，D3成為D4的子節(jié)點(diǎn)。更新D1和D4的FT表。5）D5的加入與D2，D3的加入類似，選擇D4為其父節(jié)點(diǎn)。 圖（e）給出了整個(gè)的多播轉(zhuǎn)發(fā)樹(shù)每個(gè)節(jié)點(diǎn)的FT表編輯課件l成員離開(kāi) 通過(guò)發(fā)送LEAVE消息給其父節(jié)點(diǎn) 例如，如果D4要離開(kāi)，D4發(fā)送LEAVE給D1，其中消息中包括

5、D4的FT表。D1收到LEAVE消息后，D1把D4從其FT表中移走，并且把D4的子節(jié)點(diǎn)全部加入到自己的FT表中。右圖（a）（b）描述整個(gè)過(guò)程編輯課件l節(jié)點(diǎn)維護(hù) 節(jié)點(diǎn)之間定期交換可達(dá)消息，當(dāng)子節(jié)點(diǎn)不可達(dá)時(shí)，父節(jié)點(diǎn)將其從FT表中除去；當(dāng)父節(jié)點(diǎn)不可達(dá)時(shí)，各子節(jié)點(diǎn)必須重新發(fā)送JOIN消息加入。編輯課件1.3 TAG：性能：性能l 時(shí)間復(fù)雜度： k(logkN )2 假定有n個(gè)成員，每個(gè)成員有k個(gè)子節(jié)點(diǎn)l 成員退出復(fù)雜度：klogkN 編輯課件1.4 TAG：優(yōu)缺點(diǎn)：優(yōu)缺點(diǎn)lTAG 通過(guò)利用拓?fù)湫畔@得了性能上的提高，但是它破壞了網(wǎng)絡(luò)的分層結(jié)構(gòu)，使應(yīng)用層獲取網(wǎng)絡(luò)層的信息；另外拓?fù)涞臏y(cè)量和網(wǎng)絡(luò)性能的測(cè)量目

6、前仍是沒(méi)有很好解決的問(wèn)題。編輯課件2 ALMIl應(yīng)用層組播的體系結(jié)構(gòu)采用集中式對(duì)成員進(jìn)行管理主要針對(duì)成員數(shù)量較少的組播應(yīng)用 ALMI是美國(guó)華盛頓大學(xué)分校計(jì)算機(jī)系從2000年開(kāi)始進(jìn)行的研究項(xiàng)目，提出了將應(yīng)用層組播作為端系統(tǒng)基礎(chǔ)服務(wù)功能的體系結(jié)構(gòu)。ALMI設(shè)計(jì)了在操作系統(tǒng)的套接口(socket)之上，以中間件(middleware)的形式向上層應(yīng)用提供組播服務(wù)的結(jié)構(gòu)，中間件實(shí)現(xiàn)自組織組網(wǎng)、組播復(fù)制和轉(zhuǎn)發(fā)功能，在組播成員節(jié)點(diǎn)之間組成一個(gè)應(yīng)用層組播網(wǎng)。ALMI研究組以Java代碼實(shí)現(xiàn)了中間件的原型。ALMI的自組織協(xié)議在組成員節(jié)點(diǎn)之間建立和維護(hù)一棵共享的最小代價(jià)生成樹(shù)(minimum spanning

7、 tree)，支持組規(guī)模較小的多方通信。ALMI可以針對(duì)上層的應(yīng)用需求構(gòu)建不同性能的疊加網(wǎng)。編輯課件2.1 ALMI特點(diǎn)在成員之間維護(hù)最小生成樹(shù)減小了維護(hù)開(kāi)銷，但是維護(hù)開(kāi)銷仍然大無(wú)法單獨(dú)優(yōu)化從每個(gè)源出發(fā)的傳輸開(kāi)銷編輯課件2.2 ALMI主要思想l 在ALMI中，一個(gè)組播組由一個(gè)會(huì)話控制器和多個(gè)組播成員組成。利用控制器集中對(duì)成員的管理和組播樹(shù)的構(gòu)造，并可以提供基于Java的中間組件。l 會(huì)話控制器：是一個(gè)程序?qū)嶓w，它運(yùn)行在所有成員都能訪問(wèn)到的位置，它可以與某個(gè)成員運(yùn)行在同一臺(tái)計(jì)算機(jī)上，通常是與組的發(fā)起成員在一起，或者位于ISP提供的某個(gè)組播服務(wù)網(wǎng)關(guān)上。組播成員之間形成一棵組播樹(shù)。組播樹(shù)中的一條鏈

8、路代表兩個(gè)成員之間的一條單播連接。數(shù)據(jù)信息沿著組播樹(shù)進(jìn)行分發(fā)，而控制信息則通過(guò)會(huì)話控制器與各個(gè)成員之間的單播連接進(jìn)行傳輸。編輯課件會(huì)話控制器的主要功能會(huì)話控制器的主要功能l 主要功能：1. 對(duì)加入成員進(jìn)行注冊(cè)和維持組播樹(shù)。2. 通常放置于成員容易接人的地方。3. 它保證連接性： 當(dāng)成員加入、離開(kāi)會(huì)話或網(wǎng)絡(luò)或主機(jī)的失效時(shí)保證網(wǎng)絡(luò)的連接性 保證傳輸效率：定期從所有成員收集信息計(jì)算最小剪枝樹(shù)。l 結(jié)構(gòu)：編輯課件2.3 ALMI控制協(xié)議：1. 功能：ALMI利用控制協(xié)議在會(huì)話控制器和成員之間進(jìn)行通信。主要負(fù)責(zé)成員管理，性能監(jiān)控，路由等工作。2. 包頭格式：編輯課件2.4 控制協(xié)議包頭格式說(shuō)明l 標(biāo)志位

9、的作用為：連接請(qǐng)求和回應(yīng)；性能監(jiān)測(cè)信息；分發(fā)樹(shù)信息；鄰居監(jiān)測(cè)更新信息；分離信息。l 樹(shù)的表示域指明樹(shù)的版本數(shù)，可以用來(lái)防止組播樹(shù)的循環(huán)和分離。循環(huán)可能的原因，丟失樹(shù)的更新信息、成員間不同的響應(yīng)延遲。編輯課件2.5 ALMI中成員的操作l 當(dāng)有成員要加入組的時(shí)候首先成員定位到控制器，在組初始化的時(shí)候控制器已經(jīng)用不同的方式對(duì)會(huì)話ID和控制器地址及端口號(hào)進(jìn)行了聲明。接著成員就向控制器發(fā)送加入消息，并從控制器獲得它的ID和父節(jié)點(diǎn)的地址。然后該成員就發(fā)送嫁接消息給它的父節(jié)點(diǎn)，完成后就可以傳輸數(shù)據(jù)了。編輯課件2.6 ALMI組播樹(shù)的構(gòu)造l ALMI組播樹(shù)是一棵連接所有成員的虛擬最小剪枝樹(shù)。它是利用控制器與

10、所有成員用(父，子)表通信結(jié)果計(jì)算所得的?？梢愿鶕?jù)不同的性能指標(biāo)進(jìn)行分發(fā)樹(shù)的構(gòu)造，如帶寬、延遲等。l 組播樹(shù)的優(yōu)化，成員將它們的監(jiān)測(cè)報(bào)告發(fā)送給控制器，控制器就可以根據(jù)這些信息對(duì)分發(fā)樹(shù)進(jìn)行優(yōu)化。編輯課件3 基于優(yōu)先度的應(yīng)用層組播基于優(yōu)先度的應(yīng)用層組播 l 背景 ： （ALMI，ESM，YOID等）應(yīng)用層組播協(xié)議僅僅是利用網(wǎng)絡(luò)層參數(shù)作為建樹(shù)依據(jù)。在這些協(xié)議中，每個(gè)節(jié)點(diǎn)的優(yōu)先度是相同的。在一些應(yīng)用中的確存在這樣的情況，例如：視頻點(diǎn)播，視頻會(huì)議等。 但在其他一些應(yīng)用卻有不同的情況。如：大規(guī)模網(wǎng)絡(luò)游戲，大規(guī)模分布式仿真系統(tǒng)等。節(jié)點(diǎn)在這些系統(tǒng)中由于所處位置不同而具有不同的優(yōu)先度。優(yōu)先度越大的實(shí)體則它收到的

11、更新時(shí)間越短，也就意味著兩個(gè)節(jié)點(diǎn)之間的路徑越短。而當(dāng)節(jié)點(diǎn)的優(yōu)先度小時(shí)，兩個(gè)節(jié)點(diǎn)之間的路徑不是最優(yōu)，協(xié)議會(huì)根據(jù)優(yōu)先度選擇合適的路徑給這兩個(gè)節(jié)點(diǎn)。 編輯課件基于優(yōu)先度的應(yīng)用層組播協(xié)議 l 在結(jié)構(gòu)上被分為兩部分： 起始節(jié)點(diǎn)：在系統(tǒng)啟動(dòng)的初級(jí)階段，選定一個(gè)節(jié)點(diǎn)作為起始節(jié)點(diǎn)，它的IP地址通過(guò)廣播的方式通知所有別的系統(tǒng)成員。這個(gè)節(jié)點(diǎn)一方面記錄分布式虛擬環(huán)境中所有實(shí)體的位置，并不斷更新它們的位置，另一方面根據(jù)這些實(shí)體的位置采用HLA機(jī)制，為每個(gè)有狀態(tài)更新的實(shí)體確定組播組。并把組播成員信息發(fā)送給這個(gè)狀態(tài)更新實(shí)體所在的節(jié)點(diǎn)。它本身不參與數(shù)據(jù)發(fā)送，同時(shí)也不參與建樹(shù)過(guò)程。這樣做最大限度的保證了系統(tǒng)的穩(wěn)定性，一旦起始

12、節(jié)點(diǎn)出現(xiàn)異常，也不會(huì)影響到整個(gè)系統(tǒng)的工作。僅僅是新的節(jié)點(diǎn)無(wú)法加入到系統(tǒng)中。 發(fā)送節(jié)點(diǎn)：發(fā)送節(jié)點(diǎn)就是那些有狀態(tài)更新的實(shí)體所在的節(jié)點(diǎn)。這些節(jié)點(diǎn)負(fù)責(zé)組播樹(shù)的構(gòu)建，它們自身是樹(shù)的根節(jié)點(diǎn)。在建樹(shù)過(guò)程中，根據(jù)從起始節(jié)點(diǎn)收到的成員的優(yōu)先度來(lái)構(gòu)建組播樹(shù)。編輯課件建樹(shù)的過(guò)程 首先由起始節(jié)點(diǎn)計(jì)算出組播組中成員的優(yōu)先度。 當(dāng)每個(gè)發(fā)送實(shí)體所在節(jié)點(diǎn)接收到組播成員信息和優(yōu)先度信息時(shí)，若實(shí)體的優(yōu)先度等于1，則它進(jìn)入到隊(duì)列1中；若是小于1，則進(jìn)入到隊(duì)列2。采用兩個(gè)隊(duì)列的目的是為了方便的構(gòu)建出基于優(yōu)先度的組播樹(shù)。 若隊(duì)列1不為空，則所有隊(duì)列1中的實(shí)體所在節(jié)點(diǎn)直接連到發(fā)送節(jié)點(diǎn)上，而隊(duì)列2中的節(jié)點(diǎn)會(huì)選擇隊(duì)列1中的節(jié)點(diǎn)作為其父節(jié)點(diǎn)，

13、這一選擇是周期性的。在此不考慮節(jié)點(diǎn)的帶寬承受能力。若隊(duì)列1為空，則隊(duì)列2中的節(jié)點(diǎn)會(huì)直接連接到發(fā)送節(jié)點(diǎn)上。這樣即充分考慮到了實(shí)體優(yōu)先度的作用，同時(shí)也充分利用了帶寬。 隨著節(jié)點(diǎn)狀態(tài)的更新，以上算法會(huì)重復(fù)執(zhí)行，以保持組播樹(shù)的有效性。 編輯課件實(shí)例： l 圖1給出了虛擬環(huán)境中實(shí)體的位置情況。其中A是狀態(tài)更新實(shí)體，而B(niǎo)、C、D在實(shí)體A的碰撞區(qū)域中，而E、F、G中實(shí)體A的發(fā)現(xiàn)區(qū)域中，所以B、C、D進(jìn)入隊(duì)列1中，而E、F、G進(jìn)入隊(duì)列2中。根據(jù)圖1 而構(gòu)建的組播樹(shù)見(jiàn)圖2。圖1 實(shí)體在分布式虛擬環(huán)境中的位置圖2 實(shí)體A的組播樹(shù)HEFGDABCColisionRegionObservationN Region編輯

14、課件優(yōu)缺點(diǎn)： 那些具有較高優(yōu)先度的節(jié)點(diǎn)會(huì)進(jìn)入到隊(duì)列1中，因此在建樹(shù)中會(huì)直接連到發(fā)送節(jié)點(diǎn)上去。直連表示的路徑是最短的，也就是符合了依靠?jī)?yōu)先度建樹(shù)的思想。 組播樹(shù)不會(huì)超過(guò)3層，同時(shí)又是單步建樹(shù)，所以建樹(shù)的時(shí)間要短于最小生成樹(shù)。 同YOID一樣，這里采用的是單步建樹(shù)。但有一點(diǎn)與YOID不同，它不需要循環(huán)檢測(cè)機(jī)制，這是由于每個(gè)節(jié)點(diǎn)都有優(yōu)先值的原因。同時(shí)優(yōu)先值大的不會(huì)成為優(yōu)先值小的子節(jié)點(diǎn)，所以不可能產(chǎn)生循環(huán)的情況。編輯課件4 Delaunay三角網(wǎng)三角網(wǎng)二維二維DelaunayDelaunay三角網(wǎng)（三角網(wǎng)（DTDT）：）： 網(wǎng)中的任意三角形的外接圓內(nèi)不含任何網(wǎng)中的任意三角形的外接圓內(nèi)不含任何一個(gè)組內(nèi)其

15、它節(jié)點(diǎn)。一個(gè)組內(nèi)其它節(jié)點(diǎn)。編輯課件 Delaunay三角網(wǎng)三角網(wǎng)二維二維DelaunayDelaunay三角網(wǎng)（三角網(wǎng)（DTDT）特性：）特性：1.1.任意兩點(diǎn)間有一組可互換的無(wú)重復(fù)路徑；任意兩點(diǎn)間有一組可互換的無(wú)重復(fù)路徑；2.2.每個(gè)節(jié)點(diǎn)的棱數(shù)少于每個(gè)節(jié)點(diǎn)的棱數(shù)少于6 6條；條；3.3.只要拓?fù)浣Y(jié)構(gòu)建立，數(shù)據(jù)包傳輸信息就已只要拓?fù)浣Y(jié)構(gòu)建立，數(shù)據(jù)包傳輸信息就已包含在節(jié)點(diǎn)中包含在節(jié)點(diǎn)中，不需路由協(xié)議，不需路由協(xié)議。編輯課件 Delaunay三角網(wǎng)三角網(wǎng)Jorg Liebeherr和和Michael Nahas提出提出DT疊加：網(wǎng)中每個(gè)節(jié)點(diǎn)都對(duì)應(yīng)著一個(gè)參與疊加：網(wǎng)中每個(gè)節(jié)點(diǎn)都對(duì)應(yīng)著一個(gè)參與組播組的

16、網(wǎng)絡(luò)終端。即由疊加網(wǎng)所有節(jié)組播組的網(wǎng)絡(luò)終端。即由疊加網(wǎng)所有節(jié)點(diǎn)組成的點(diǎn)組成的Delaunay三角網(wǎng)中，如果兩個(gè)三角網(wǎng)中，如果兩個(gè)節(jié)點(diǎn)相連，它們對(duì)應(yīng)的兩個(gè)實(shí)際節(jié)點(diǎn)在節(jié)點(diǎn)相連，它們對(duì)應(yīng)的兩個(gè)實(shí)際節(jié)點(diǎn)在DT疊加網(wǎng)中就有邏輯鏈接，互為鄰居疊加網(wǎng)中就有邏輯鏈接，互為鄰居編輯課件Delaunay三角網(wǎng)三角網(wǎng)DT應(yīng)用層組播協(xié)議的實(shí)現(xiàn)：應(yīng)用層組播協(xié)議的實(shí)現(xiàn)： 坐標(biāo)映射坐標(biāo)映射 組織拓?fù)浣M織拓?fù)?實(shí)現(xiàn)路由實(shí)現(xiàn)路由編輯課件 Delaunay三角網(wǎng)三角網(wǎng)三維三維DelaunayDelaunay三角網(wǎng)（三角網(wǎng)（DTDT）：）：1.1.二維的擴(kuò)展，有類似性質(zhì)，適于應(yīng)用層二維的擴(kuò)展，有類似性質(zhì)，適于應(yīng)用層組播疊加網(wǎng)的構(gòu)建

17、組播疊加網(wǎng)的構(gòu)建2.2.節(jié)點(diǎn)間的傳輸時(shí)延與距離相關(guān)，而節(jié)點(diǎn)節(jié)點(diǎn)間的傳輸時(shí)延與距離相關(guān)，而節(jié)點(diǎn)存在于三維物理空間存在于三維物理空間編輯課件 Delaunay三角網(wǎng)三角網(wǎng)三維三維DelaunayDelaunay三角網(wǎng)（三角網(wǎng)（DTDT）：）：特定源節(jié)點(diǎn)的組播樹(shù)由特定源節(jié)點(diǎn)的組播樹(shù)由DTDT網(wǎng)唯一確定；網(wǎng)唯一確定；組播和單播在組播和單播在DTDT網(wǎng)生成樹(shù)的棱上進(jìn)行，發(fā)網(wǎng)生成樹(shù)的棱上進(jìn)行，發(fā)送者是樹(shù)的根節(jié)點(diǎn)；送者是樹(shù)的根節(jié)點(diǎn)；節(jié)點(diǎn)根據(jù)旋轉(zhuǎn)路由做出局部傳輸決定。節(jié)點(diǎn)根據(jù)旋轉(zhuǎn)路由做出局部傳輸決定。編輯課件 Delaunay三角網(wǎng)三角網(wǎng)三維三維DelaunayDelaunay三角網(wǎng)（三角網(wǎng)（DTDT）：）：

18、旋轉(zhuǎn)路由用于確定組播的路由樹(shù)，以分布方旋轉(zhuǎn)路由用于確定組播的路由樹(shù)，以分布方式計(jì)算它們的孩子節(jié)點(diǎn)。式計(jì)算它們的孩子節(jié)點(diǎn)。編輯課件 Delaunay三角網(wǎng)三角網(wǎng)具體而言：對(duì)于以具體而言：對(duì)于以R R為根節(jié)點(diǎn)的生成樹(shù)，如果棱是和為根節(jié)點(diǎn)的生成樹(shù)，如果棱是和的分界邊，如果節(jié)點(diǎn)的分界邊，如果節(jié)點(diǎn)C C基于節(jié)點(diǎn)基于節(jié)點(diǎn)A A到根節(jié)點(diǎn)到根節(jié)點(diǎn)R R的角度比的角度比節(jié)點(diǎn)節(jié)點(diǎn)B,DB,D小，那么節(jié)點(diǎn)小，那么節(jié)點(diǎn)C C就是節(jié)點(diǎn)就是節(jié)點(diǎn)A A的孩子節(jié)點(diǎn)。每個(gè)的孩子節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)按如上步驟進(jìn)行，就生成了以節(jié)點(diǎn)按如上步驟進(jìn)行，就生成了以R R為根節(jié)點(diǎn)的樹(shù)為根節(jié)點(diǎn)的樹(shù)編輯課件 Delaunay三角網(wǎng)三角網(wǎng)三維三維Delau