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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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