（計算機應用技術專業(yè)論文）應用層組播轉發(fā)樹重構技術研究.pdf

鄭卅l 大學碩士學位論文 摘要 近年來，一對多、多對多通信的需求使得i p 組播和基于端系統(tǒng)的應用層組播成為了 網絡研究的熱點課題。i p 組播目前面臨許多問題，影響了其在i n t e m 戰(zhàn)上的部署，而應 用層組播雖然易于部署，但端系統(tǒng)的不穩(wěn)定性導致了轉發(fā)樹的不穩(wěn)定。因此，在應用層 組播中，轉發(fā)樹的重構就尤為重要。目前針對轉發(fā)樹的重構有兩種策略：一種是前向 式，另一種是后向式。由于前向式重構是在父節(jié)點失效前預先計算備用節(jié)點，減少了重 構時間，因而能更好的提高轉發(fā)樹的可靠性。 針對轉發(fā)樹的重構問題，本文進行了兩部分工作：第一部分工作是對現有的幾種前 向式重構算法進行了對比實驗研究。研究表明，p c p 算法在尋找備用節(jié)點的開銷方面小 于r o t 算法，但是找到的備用節(jié)點的延遲特性不如r o t 算法。相對而言，r o t 算法 更適合于轉發(fā)樹結構相對固定的應用場合。第二部分工作，在對上述幾種前向式重構算 法研究的基礎上，提出了新的重構算法p l a 算法。該算法的核心思想是在“鏈路預 留”思想的基礎上，考慮了鏈路延遲約束。本文將該算法同其它前向式重構算法進行了 對比試驗，結果表明：在平均加入開銷與備份鏈路延遲這對矛盾中，p l a 算法作了比較 合適的調和。同p c p 算法相比較，p l a 算法雖然在平均加入開銷上有所增加，但是重 構的組播樹的備用鏈路延遲降低了；同i 的t 算法相比較，雖然p l a 算法的備份鏈路延 遲不如r o t 算法，但是p l a 算法的平均加入開銷耗費的較少。研究表明，p l a 算法更 適合于在節(jié)點相對不穩(wěn)定的h 峋n 甙中部署，尤其是那些既考慮通信質量又要求連接開 銷的應用場合，譬如網絡電視，b t 下載以及大規(guī)模流媒體的實時應用等。 關鍵詞：計算機網絡，應用層組播，轉發(fā)樹重構，前向式重構 應用層組插轉發(fā)樹重構技術研究 a b 8 t 隋c t m 1 1 l d c a s t h a s k 髓1 t 1 1 e h o t t o p i c i l l l l l e r e s e 疵b o f c o m 咖n 咖r ka s t h e p o i n t - t o m l 帕p o i n td a 詛a n s f e ra p p l i c a l i o n s 撕s e h o w e v e r ，m o r e 血趾a d e c a d ea f t e ri t s “在a lp r o p o s a l ， d 印l q 【e mo f 艫c a s th 鵲b e e ni i m i t e d 趾l ds p a r s e 血l et os o m e r e a s o n s h lo r d e rt 0r e s 0 1 v e t h ep m b l e m s ，s o m er e s e a 圯h e r sp r o p o s e 印p l i a 狐o nl e v e lm i l l 廿c a s t ( a i j m ) t h en o n l e a f n o d e s i 1 1m e 廿e ea r en o r m a lc n dh o s t s ，w h i c ha r ep o 刪a l l ym o r es u s c 印廿b l et 0f h i l u r e s t h u sa i l i i l l p 刪p r o b l 鋤i 1 1a l m i sh o wt or e c o v e r 丘d mr 砌ed e p a m l r e s 0 nm eq u e 嘶o n ，t l l e r ea r e t w oa p p r o a c h e st om er e c o v e r ) ro f 也ea p p l i c a d o nl e v e lm 叭c a 眥n 七e o n ei s 也er e a c 缸v e a p p i | 0 a c h a n o t h e ri st 1 1 ep r o a c d v ea p p f o a c l l ，w 1 1 i c hp l 鋤sf o rd 印a r t l 鵬sb e f o r et h c yh a p p e n w m lt h ea i do f p r o a c 廿v ea p l 邶a c h ，an e wd e l i v e r y 心e ec a nb eq u i c h yr e g t o r e d t h er e s e a r c hw o r ki sc c i i t e r e do nr e c o i l s m 】c t i o no f f 0 刪i n g 訂c e 1 1 1m i s 也e s i s ，也e r ea r e 柵op a r 臼證t h em a i l lw o r k f i i 鈍b a s eo nt h ec o m p a r a t i v e 獅a l y s i so f a p p a c h e st ot 1 1 e r e c o v e r yo f t h eo v e r l a ym u m c a s 【廿_ e e ，w ec i l o o s et h ep m a c t i v ea p p m a c ha se f n p ：h a s e s h 1m e p a n ，曲e 硎i z a d o no f 幽刪m mi s 洳p o n a n t t h r o u 曲s 婦l l l 面o ne x p 矧婦e n 招，w eh a v e r e a l i z e ds e v e r a la l g o r i 廿l m so f p r o a c t i v ea p p r o a c ha n d 刪y z e dm ea d v a i l t a g e sa n d d i s a d v a n ：c a 嘻e so f 也e s ea l g 耐t l l r n s s e c o n 也b 勰eo nm ec o m p 趾咖e 砌y s i s ，w ep r o p o s e da n e wa l g 叭p l a ，t h ec o r eo f w 【l i c hi sap r e - p l a nm o d e lb a s e do nt 1 1 ep r o a c 血忙a p p r o a c h i n 吐l i sp a n ，e x 刪m e n t si sa 1 1i l n p o 脅tp 甜t h cs i m l l l a l i o n 嘲財i i l l e n 乜h a v eb e e nm a d eb 粥e d o nt 1 1 en e wa l g o r i 也ma n de 珥) e d m e n t a lr c s u l 乜a r e 刪y z e d t h r o u g he x p e r m l e n t 刮丘o na i l d r e s e 礎，m ef 0 1 1 0 w i n gc o n c l l l s i o 璐a r e 柵：p l aa l g 嘶也mc a nr e c o n c i l ct t l ec o n _ 婦d i c t i o no f 弘加一c d a n d 6 叩嘲礦加h 婦幻，；p l aa 1 9 0 痂h mc 觚r a i s e 缸p e r f 0 i l a i mo f n i u d 吐c a s c f o 腳m n g 訂c e k e y w o r d s ：c o m p u t e rn 咖o r k ；a p p l i c a t i o nl e v e lm u m c a s t ；r e c o n s 眥垃o no f f 刪j n g1 慨；p m a 蒯v er e c o n s n l 枷o n 鄭重聲明 工 3 ，& ， j 本人的學位論文是在導師指導下獨立撰寫并完成的，學位論文沒有剽竊、抄襲等違 反學術道德、學術規(guī)范的侵權行為，否則，本人愿意承擔由此產生的一切法律責任和法 律后果，特此鄭重聲明。 學位論文作者( 簽名)：秘書 l g 只乙日 年否妒 鄭州大學碩士學位論文 第1 章引言 1 1 課題背景及選題依據 近年來，隨著網絡技術的不斷發(fā)展，f t p l 、h t l p 、s m t p 3 等傳統(tǒng)數據業(yè)務已經難 以滿足人們對信息業(yè)務的需求，視頻點播、遠程教學、新聞發(fā)布、視頻會議、股市行隋 發(fā)布、多媒體遠程教育、c s c 咿協(xié)同計算等業(yè)務在應用中變得日益重要。這類業(yè)務的 特點是顯著的高帶寬的多媒體應用，這些應用需要比較大的網絡帶寬，會引發(fā)帶寬的急劇 消耗和網絡擁擠問題，信息在一個組內以一對多或者多對多的形式進行傳輸。例如新聞 發(fā)布信息由一個服務器發(fā)布，大量不固定的接收端接收。如果采用單播方式來傳輸這 些信息，那么發(fā)送源就必須維護每個客戶信息。當客戶數目很多時，對于發(fā)送源來說還 需要很高的傳輸速率。另外，相同的數據可能在同一個鏈路上傳輸多次，消耗大量的網 絡帶寬。為了緩解網絡瓶頸，人們提出了組播口m u m c a 啪 1 技術方案。但是從因特網中 p 組播的應用現狀看，i p 組播并沒有取得預期的成功。由于組播路由器需要為每個活動 的組維護路由狀態(tài)信息，網絡中大量的活動組將需要路由器巨大的存儲和處理開銷；開 放的口組播模型在開放的i n t e m 融環(huán)境中難以支持有效的管理和控制機制。以上這些因 素都制約了p 組播的發(fā)展。于是，一些研究者提出將復雜的組播功能放在端系統(tǒng)( e 1 1 d _ s y s 衄n ) 2 3 實現的新思想，也就是使用應用層組播( a p p l i c 鰣o nl a y e rm u l t i c a s t ) 技術來 替代傳統(tǒng)的m 組播技術，由于應用層組播保持了互聯(lián)網的“單播、盡力發(fā)送”模型，并 且部署方便等優(yōu)點，得到了迅速的普及，成功地案例有香港理工大的c o o l s h a m ，華中 科大的p p l i v e 等。 應用層組播和傳統(tǒng)的p 組播技術相比，可以避開網絡層實現組播功能的許多難題： 1f n e t m s r t 晰o c o l 2l 帥d 1 礬1 協(xié)s 斷p m l o c 0 1 3s 呻l em 日i l 撇p r o t o c o l 4c o “p u s 1 1 p p 0 刪c 0 a 呻稍v c w o 血 應用層組播轉發(fā)樹重構技術研究 1 應用層組播的狀態(tài)在主機系統(tǒng)中維護，不需要路由器保持組的狀態(tài)，解決了業(yè)務 的擴展性問題； 2 組播應用可以隨時部署，不需要網絡設備的升級和功能擴展； 3 可以簡化組播的控制、可靠等功能的實現，建立在網絡連接之上的應用層組播可 以使用傳輸層的t c p 、u d p 協(xié)議，如可以利用t c p 的可靠和擁塞控制簡化組播 的可靠和擁塞控制。當然應用層組播對帶寬的節(jié)省不如m 組播；協(xié)議額外的 開銷比較大。但是因為其開發(fā)方便，部署簡單應用層組播還是具有比較好的應 用前景。 由于應用層組播是基于端系統(tǒng)來構造其轉發(fā)樹，因而端系統(tǒng)的穩(wěn)定性決定著應用層 組播轉發(fā)樹的穩(wěn)定性。應用層組播不像傳統(tǒng)的m 組播那樣，轉發(fā)樹中的葉節(jié)點通常是 端系統(tǒng)，這些節(jié)點潛在的比路由器更易失效或頻繁的退出轉發(fā)樹，一旦發(fā)生這種情況， 那么該節(jié)點下游的所有節(jié)點將受到影響。因此，在應用層組播應用中，一個很重要的問 題就是如何迅速的恢復轉發(fā)樹，使得受影響的這些節(jié)點盡量縮短其服務中斷。 鑒于此，應用層組播轉發(fā)樹的重構問題逐漸被提了出來，并成為熱點問題。 1 2 國內外研究現狀 目前，在樹的重構問題上，有兩種策略，一種稱為后向式( r e a c 垃v ea p p r o a c h ) 策 略，該方法是在節(jié)點失效后，再進行樹的重構，代表的方法有( 4 5 】 6 】，這種事后補救 的方法會花去不少時間，用于在多個節(jié)點間選擇一個合適的加入點，來重新構造轉發(fā) 樹。這樣就使得受到影響的節(jié)點會有一個比較長的服務中斷；另一種方法稱為前向式 ( p r o a c t i v ea p p m a c h ) 策略，代表算法有r o t 7 】、p c p 8 】和p r m 9 】，這種方法的特 點是在節(jié)點失效之前預先計算好節(jié)點的新的父母節(jié)點，一旦該節(jié)點的父母節(jié)點退出，就 可以根據預先計算的結果快速地找到新父母節(jié)點，避免花太多的時間用于尋找新加入 點，從而減少服務的中斷時間。 2 鄭卅l 大學碩士學位論文 1 3 課題所做的工作及論文結構 1 3 1 本文主要工作 本文工作主要分為兩部分，前期工作是對現有幾種主要技術的實驗、分析、比較幾 種前向式算法的優(yōu)缺點；后期針對上述算法的優(yōu)缺點提出了一種新的重構算法p l a 算 法，這是一種結合了p c p 【8 和r o t 7 兩種典型前向式重構策略的算法，其核心思想是 節(jié)點采用了“鏈路預留”的思想，為自身尋找備份鏈路，進行樹的重構。 本課題的研究目標為：利用前向式重構策略，在重構應用層組播轉發(fā)樹的過程中， 在控制節(jié)點加入轉發(fā)樹的花費開銷基礎上，盡量降低備份鏈路的延遲，減少數據丟失 率，使得流媒體等高帶寬應用在h e n l e t 上的應用更加流暢。 1 3 2 論文結構 通過對現有應用層組播轉發(fā)樹重構技術的研究，實現了一個基于m 僅c a s t 1 0 應用 層組播通信模型的組播轉發(fā)樹重構算法，該算法在稍微增加了節(jié)點加入開銷的基礎上， 大大降低了重構后轉發(fā)樹的備份鏈路延遲，由于該算法的靈活性秘可擴展性，因而比 r o t 算法更易于部署。 本文組織如下： 第二章“相關技術”，介紹了應用層組播轉發(fā)樹重構技術所涉及的相關技術。其 中包括組播、應用層組播、m 黜等通信模型。 第三章“前向式重構的相關解決方案及實驗分析”，介紹了目前幾種前向式策略的 具體方案，繼而通過仿真實驗、分析、驗證了p c p 算法和r o t 算法在幾個重要衡量指 標上的優(yōu)缺點。 第四章“基于p l a 算法的重構解決方案”，通過對p c p 算法和r o t 算法的優(yōu)缺 點比較分析，提出了一個基于p c p 算法的p l a 算法，并通過仿真實驗來分析驗證了 p l a 算法對p c p 算法在重要衡量指標上的改進。 第五章“結束語”，給出本文的結論，同時根據存在的問題，提出了下一步的研究 方向。 應用層組播轉發(fā)樹重構技術研究 第2 章相關技術 本章將介紹分析一些本課題所涉及到的相關技術，內容組織如下：首先討論并比較 了目前可用的群組通信模型，包括；口組播、應用層組播和m i 】【c a s t 1 0 。接著介紹在 m i ) 【c a s t 中所涉及到的一些相關技術。 2 1 組通信模型 組通信在分布式系統(tǒng)和并行計算機系統(tǒng)中有著非常廣泛的應用。組是動態(tài)的，可以 創(chuàng)建新的組，也可以注銷舊的組。參與者可以動態(tài)的加入或退出組，因此需要一種機制 來管理組和組的成員。組通信模型的優(yōu)勢是避免了傳統(tǒng)點對點通信模型中，針對每個接 受者，發(fā)送者都要轉發(fā)次數據包，浪費網絡資源的情況。組通信模型中，數據往往同 時傳遞給組內多個接受者，一次傳輸，多點到達，節(jié)省了網絡資源。因而組通信成為網 絡研究中的熱點課題。 2 1 1 碑組播 早在1 9 8 8 年，斯坦福大學的博士生s e d e e r i n g 就提出了p 組播機制。它是最 早的、最有效的組播傳輸機制。主機之間一對一組的通訊模式，將坤數據報從一個源 傳送到多個目的地，將信息的拷貝發(fā)送到一組地址，到達所有想要接收它的接收者。也 就是加入了同一個組的主機可以接受到此組內的所有數據，網絡中的交換機和路由器只 向有需求者復制并轉發(fā)其所需數據。群組的各個成員可以分布于各個獨立的物理網絡 上，主機根據組地址( g f o u p a d d r e s s ) 可以向路由器發(fā)送i g 口5 履m d 6 1 1 】 1 2 】請求，請 求加入或退出某個組，路由器收到用戶請求后，根據運行的組播路由協(xié)議的不同，在路 由器間構造共享樹( r p f 7 ) 或者源樹( s p r ) ，來保證組播數據自旨夠從發(fā)送者正確到 5 i c l t e m e 亡( 抽u p m 柏a g 1 舶c p 忉幻c o l 6m u l 髓a s t l i s 【e 咐d i s c o v 哪 7r d c a p o h n t | 8s h o n e s t p 耐1 1 慨 4 鄭州大學碩士學位論文 達接收者。網絡中的路由器和交換機有選擇的復制并傳輸數據，即只將組內數據傳輸給 那些加入組的主機。這樣既能一次將數據傳輸給多個有需要( 加入組) 的主機，又能保 證不影響其他不需要( 未加入組) 的主機的其他通訊。 2 1 1 1p 組播協(xié)議 i p 組播協(xié)議主要分為組管理協(xié)議和路由協(xié)議兩類。其中組管理協(xié)議負責主機和路由 器之間的交互，主機通過組管理協(xié)議來告知路由器加入或者離開組播組；組播路由協(xié)議 負責在路由器之間構造組播轉發(fā)樹，以完成組播數據的分發(fā)。 組管理協(xié)議主要有m v 4 環(huán)境下的i g 咖p v l 【1 】、i g m p v 2 1 1 】和i g m p v 3 【1 2 ，m v 6 環(huán) 境下的m d v l 1 3 】和m 國v 2 1 4 ，其中i g 棚p 1 ，2 和d v l 功能基本類似，目前較為普 及。 在組播路由協(xié)議方面，早期的協(xié)議，例如d 、，】誑沖9 1 5 、m o s p f l 0 1 6 等，由于可 擴展性較差，以及依賴于單播路由協(xié)議，因此逐步被淘汰。目前的組播路由協(xié)議主要分 為兩大類，即域內組播路由協(xié)議和域間組播路由協(xié)議。域內協(xié)議主要有p - d m 17 、 p d 訌s m 1 8 】，其中p 正d m “采用洪泛加剪枝的工作模式，不適合較大規(guī)模的網絡； p 訂s m l 2 采用接收者發(fā)起構建共享樹的工作模式，是目前使用較多的組播路由協(xié)議， 其主要缺點是協(xié)議比較復雜。 在域間協(xié)議中，目前較為成熟的方案是p d “一舒d 伍佃( m m s d p 三個協(xié)議結合起 來，由p m s m 協(xié)議負責域內的組播轉發(fā)樹構建，m b g p l 3 協(xié)議( i9 傳遞不同a s 間的組 播路由信息，m s d p 協(xié)議【2 0 傳遞不同域內的組播源通告信息。m s d p 協(xié)議的主要缺點 是當自治域數量較多時，該協(xié)議的可擴展性不是太好，因此被看作是一種過渡方案，只 9d r p ：距離向量組播路由協(xié)議 m o s p f ：攝短路徑優(yōu)先組播 “p r a t o c o l i r l d c p 曲d 眥m u 惦c a s t 蛐m o d e up r a i o c 0 1 i f l d e p d 咖m u m c a s t s p a 瓶m o d e 1 3 m n 幣州o c o ib o r d e rg 鋤州a yp r o t o c o i 應用層組播轉發(fā)樹重構技術研究 是在v 4 環(huán)境下使用，在i p v 6 環(huán)境中沒有被采用。除了m s d p l 4 協(xié)議，肼還提出了 另一種域間組播解決方案，即m a s c l 5 b g 啪p 1 6 協(xié)議【2 1 ，但是由于協(xié)議本身過于復 雜，沒有得到廣泛的采用。 i p 組播工作模式如圖2 1 ： 口庸盤鞲+ h 蟪斌嘏措捧輸蟪掩 。接收董l 一一一散捌傳相溉向 毅掘秤童帆 圖2 1i p 組播 口組播的優(yōu)點： 1 需要相同數據流的客戶端加入相同的組共享一條數據流，節(jié)省了服務器的負 載。具備廣播所具備的優(yōu)點。 2 由于組播協(xié)議是根據接受者的需要對數據流進行復制轉發(fā)，所以服務端的服務 總帶寬不受客戶接入端帶寬的限制。p 協(xié)議允許有2 億6 千多萬個組播，所以 其提供的服務可以非常豐富【2 2 。 3 此協(xié)議和單播協(xié)議一樣允許在鋤e t 寬帶網上傳輸。 m 組播的缺點： 4m u m c a s t s o u r c e d i s 。o v e i yp r a 幻0 0 1 5 m u l c 囂t a d d f e 囂s 吐a a h n 6b o i d c r g a l c w a y m 山石鼬吐p 啪c o l 鄭州大學碩士學位論文 1 與單播協(xié)議相比沒有糾錯機制，發(fā)生丟包錯包后難以彌補，但可以通過一定的 容錯機制和q o s 加以彌補。 2 訪問控制較為困難，對于運營商而言，如果想在網絡中使用組播技術，就希望 能夠進行流量統(tǒng)計，以便于計費功能的實現，而傳統(tǒng)的組播難以實現這樣的功 能。 3 路由協(xié)議復雜。目前使用的組播路由協(xié)議，無論是域內的還是域間的，都比較 復雜。在設計核心路由器的時候，一般需要用硬件來實現組播數據報文的轉 發(fā)，但是目前普遍采用的協(xié)議，有許多交互操作，致使協(xié)議實現較為復雜，且 不利于高端路由器使用硬件進行加速。同時，這些協(xié)議的健壯性和百，擴展性也 不夠理想。 4 加重了路由器的負載。為了使路由器支持組播通信機制，就必須在路由器中支 持各種組播路由協(xié)議和組管理協(xié)議，同時，路由器還要支持組播轉發(fā)表的構造 以及完成組播數據報文的轉發(fā)。當組播組數目比較多時，會給路由器增加不少 負載。 5 i p 組播要求所有路由器支持組播，而有些i s p 的路由器不愿意支持組播功能， 所以組播服務的部署、推廣變的很困難。 2 1 2 應用層組播( a l m ：a p p l i c 甜o nl e v e lm u 城c 髂t ) 面對疋組播業(yè)務在因特網中的困境，一些研究者開始反思疋組播體系結構本身的 問題，提出將復雜的組播功能放在端系統(tǒng)實現的新思想。端系統(tǒng)實現組播業(yè)務的思想是 將組播作為一種疊加的業(yè)務，實現為應用層的服務，因此，端系統(tǒng)組播又稱為應用層組 播( a p p l i c a t i o nl e v e l m u m c a s o 2 3 。應用層組播網的節(jié)點是組播成員主機，數據路由、 復制、轉發(fā)功能都由成員主機完成，成員主機之間建立一個疊加在p 網絡之上的、實 現組播業(yè)務邏輯的功能性網絡，稱為疊加網( o v e r l a y n 酣 的r k ) 2 4 ，主機基于自組織 算法建立和維護疊加網。應用層組播的數據在主機間實現復制和轉發(fā)，數據報沿著邏輯 鏈路轉發(fā)，多跳邏輯鏈路可能經過同一條物理鏈路。應用層組播的基本思想是保持互聯(lián) 應用層組播轉發(fā)樹重構技術研究 網原有的簡單、不可靠、單播的轉發(fā)模型，由端系統(tǒng)實現組播轉發(fā)功能。工作模式如圖 2 2 ： 口路由器 熬拋積土機 。接收生機- ，澎捌瑤魁捂轉篾糾 圖2 _ 2 應用層組播 應用層組播與網絡層組播最大的區(qū)別在于，網絡層組播依賴路由器來構造轉發(fā)樹； 而應用層組播是在主機之間構造轉發(fā)樹，處于網絡層的路由器只需支持單播就可以了， 這樣就大大簡化了組播在網絡層的部署難題。圖2 3 所示為口層組播與應用層組播的區(qū) 別：a 為數據源，b 、c 、d 為接收端。左圖采用網絡層組播技術，在路由器1 、2 、3 、 4 、5 之間構造轉發(fā)樹，其中路由器l 為樹根。數據從數據源a 到達路由器1 后，數據 就沿著口層組播轉發(fā)樹轉發(fā)到各個路由器，然后再由路由器把數據轉發(fā)到各個接收 端。右圖采用應用層組播技術，路由器1 、2 、3 、4 、5 就不需要做那些工作。數據由主 機a 傳遞到主機b 、d ，再由b 將數據傳遞到主機c ，這樣就完成了整個數據的分發(fā)與 接收。在這個過程中完全屏蔽了物理網絡的拓撲結構。實際上是在主機之間建立一個疊 加在p 網絡之上的、實現組播業(yè)務邏輯的疊加網。 鄭州大學碩士學位論文 口 蹄山器 艘朋豫封l 措轉粒櫥 o。i ：機料| 扮船維播轉笈樹 圖2 _ 3 口層組播與應用層組播 但是，相對口組播而言，應用層組播在節(jié)點的穩(wěn)定性、傳輸效率等方面面臨嚴峻 的挑戰(zhàn)。由于構建者是普通的網絡主機，這些主機彼此不知在拓撲中的相互位置關系， 必須自己獲得一個拓撲，并且在上面構建轉發(fā)樹。概括而言，影響應用層組播傳輸效率 不高的主要因素有以下幾點： 1 擔當復制轉發(fā)任務的普通終端主機的性能不高； 2 復制轉發(fā)工作在應用層通過軟件實現； 3 通過主機自己測試產生的拓撲可能會導致構建出一個無法充分利用底層網絡設 施的轉發(fā)樹； 4 為了彌補口組播在安全可靠方面的缺憾，應用層組播還要增加諸如安全可靠 之類的服務，這將進一步消耗主機的資源。 前三點就足以導致應用層組播的性能相對口組播大打折扣，可能會導致整個服務 不可用。對于這個問題，我們只能夠在第3 點上作一些研究工作，同時盡量開發(fā)出效 率高的應用層組播軟件。一些研究人員在致力于開發(fā)更好的轉發(fā)樹構建方法 2 5 】 2 6 。 無論如何，應用層組播為我們提供了個解決組播問題的途徑。 應用層組播轉發(fā)樹重構技術研究 2 1 3m i x c a s t m i x c a s t 1 0 】是一種混合了單播和組播的通信模型，其基本的出發(fā)點來源于h 】t e n l e t 核心簡單化、邊緣復雜化的目標。骨干網中的核心路由器承擔著大量的數據轉發(fā)任務， 應當盡量簡化，一些復雜的控制功能應當盡量向邊緣轉移，m i ) ( c a s t 的思路就是在域間 采用單播通信，域內采用組播通信。其工作模式如圖2 4 ： 口 瞎m 器戍剛聰昭撬傳輸線蘸 款攆游書機_ _ 耐熱瑤組撬傳輸縫路 。接收j 二桃( )m d p i m l x c 雌t 數荊代理) 圖2 4m i x c a s t 通信模型 域：在m i ) 【c a s t 通信模型中，域的概念是指一個可完全管理的接入網，比如個校 園網，或者一個企業(yè)網，或者一個小區(qū)寬帶網；例如圖2 4 中的域a 到域e 這5 個域。 m d p ：在每個域內，都有一個設備充當該域的m i ) 【c a s t 數據代理( m i x c a s td a _ i a p r o 珂) ，不同域之間的m d p 組成一個應用層組播轉發(fā)樹，用于在域間轉發(fā)組播數據。 m d p 之間通過單播的方式進行通信。 如圖2 _ 4 ，數據源位于域a 中，它首先把數據發(fā)送到所在域的姍d pa ，然后以該 m d p 為根，在所有接收端的啪) p 間構造應用層轉發(fā)樹，轉發(fā)樹之間采用單播通信，當 數據到達m d p 后，在域內采用m 組播通信，將數據分發(fā)給域內的每個接收端。 】o 鄭州大學碩士學位論文 2 _ 2m i ) 【c a s t 通信模型中轉發(fā)樹的構造 在m 政c a s t 通信模型中，轉發(fā)樹的構造是基于m r p 協(xié)議 8 】 1 0 。在m r p 中，節(jié)點 加入算法的處理流程為：對于一個想加入樹的新節(jié)點n ，它首先向根結點發(fā)送一個j o n 請求，如果根節(jié)點還有剩余的出度，就會接受節(jié)點n 成為其子女，如果根結點的出度 已經滿了，就會拒絕接受n 成為其子女，同時會把其子女節(jié)點的信息告訴n ；接下來， n 就在這些節(jié)點中，選擇個合適的節(jié)點進行加入，如果這些節(jié)點的出度全部為o ，則 不在這一層進行選擇，而是繼續(xù)往下走。 至于選取節(jié)點的原則，有兩個策略：( 1 ) 寬度+ 延遲優(yōu)先( m t p l ) 【8 。n 在有剩 余出度的節(jié)點中，選擇r r r 值最小的節(jié)點加入，如果所有節(jié)點的出度都為o ，則選擇 r 盯最小的節(jié)點往下遞歸尋找加入位置；( 2 ) 深度+ 延遲優(yōu)先( m t p 2 ) 【8 】。n 只選擇 f m 最小的節(jié)點，如果該節(jié)點有剩余出度，則n 成為該節(jié)點的子女，如果該節(jié)點沒有 剩余出度，則直接沿著這個節(jié)點往下尋找加入位置。 在下面的仿真試驗中，m r p l 、m t p 2 算法，就是構造轉發(fā)樹的兩種策略算法，我 們的實驗分析，也是基于這兩種不同構樹策略來進行橫向比較的。 2 3 本章小結 本章主要介紹了網絡通信的幾種模型，并分析了其優(yōu)缺點，其中主要是m c a s t 模 型。它是一種結合了口組播和應用層組播兩種技術的新的通信模型。本課題組播樹的 重構實驗就是基于該模型，通過該模型的組播樹構造算法m 沖1 ( 廣度和延遲優(yōu)先) 和 m t p 2 ( 深度和延遲優(yōu)先) 分別來構造兩棵轉發(fā)樹，進而在這兩種轉發(fā)樹上分別運行重構 算法。 應用層組播轉發(fā)樹重構技術研究 第3 章前向式重構技術研究和實驗分析 本章研究的重點是應用層組播轉發(fā)樹前向式重構技術的研究和實驗分析。首先描述 了現有的幾種前向式重構算法，然后針對p c p 算法和r o t 算法進行了仿真對比實驗， 最后是對實驗結果進行了分析和評價。 3 1 前向式算法 3 1 1p r m 算法 p r o b a b i l i s t i cr e s i l i 鋤tm l l l t i c 勰t ( p r m ) 算法【2 7 提出了一種隨機推進的方法，每個 節(jié)點隨機選擇固定數目的其他節(jié)點，以小概率給每個選擇的結點轉發(fā)數據。在節(jié)點失效 的情況下，該算法可以達到較高轉發(fā)率。另外，p r m 算法是一種數據層面的重構策 略，它只是隨機向前推迸數據，沒有其他什么限制，具體算法示意圖如圖3 1 。 圇 繇三一 圖3 1p r m 算法 其中：o 代表節(jié)點，代表失效的節(jié)點或鏈路，一代表數據流向，曲線代表隨機推 進的數據流向。 由于p r m 算法在數據層面上隨機轉發(fā)數據，因而會有一定的重復數據包，浪費一 定的帶寬。而我們研究的重點則是下面兩種重構策略，r o t 算法和p c p 算法，這兩種 算法是基于控制層面來進行樹的重構，p r m 算法則可以作為這兩種算法的很好補充。 3 1 2r o t 算法： r 0 r r 算法 7 中對于每一個非葉節(jié)點來說，它必須為它的所有孩子節(jié)點找到一個備 用父母節(jié)點。一旦該節(jié)點失效，它的孩子節(jié)點能夠準確知道誰是它的新的父母節(jié)點。因 鄭州大學碩士學位論文 而，當父母節(jié)點失效后，對于每一個孩子節(jié)點來說能夠迅速地連接到它的備用父母節(jié) 點，能夠迅速地從失效中重新恢復中斷的服務。 具體算法描述： 對于節(jié)點n 來說，節(jié)點n 為其孩子節(jié)點計算備用節(jié)點。首先節(jié)點n 從所用孩子節(jié)點 中選擇一個到節(jié)點n 的父母節(jié)點開銷最小的節(jié)點c 1 ，把該節(jié)點的備用父母節(jié)點指向節(jié) 點n 的父母節(jié)點。然后把c l 節(jié)點及其孩子節(jié)點放入集合a 中，把節(jié)點n 剩余的孩子節(jié) 點放入集合b 中，然后從集合a 、b 中選擇連接開銷最小的兩節(jié)點，把這兩個節(jié)點建立 起備用連接。同理直到集合b 中沒有節(jié)點。 其主要思想如圖3 2 ，預失效的節(jié)點( 5 ) 為孩子節(jié)點( 8 ，9 ，1 0 ) 計算備用父母節(jié)點。主要 考慮的是延遲優(yōu)先。 4 瓜。氏 6 1 51 6 、j 71 81 9 ：2 02 l2 2 、一- _ # + ， 圖3 2r o t 算法 3 1 3p c p 算法 p c p 算法 8 】采用了“鏈路預留”的思想進行樹的重構，借鑒q o s 中采用的“資源 預留協(xié)議”( r s v p l 7 ) ，在轉發(fā)樹中預留些鏈路，用于樹的重構。 7r c s m 礬e r e s 州甜徹p t 蝴l 應用層組播轉發(fā)樹重構技術研究 對于要計算預留鏈路的節(jié)點n 來說，首先將指針指向n 的父母節(jié)點p ，如果p 沒有 兄弟節(jié)點，則沿著樹往上走，將p 指向原節(jié)點的父母節(jié)點。然后判斷節(jié)點p 是否有預留 鏈路，有預留鏈路則p 就是要找的節(jié)點，算法結束：如果p 沒有預留鏈路，但是p 有兄 弟節(jié)點，則循環(huán)結束；否則，繼續(xù)往上游走，如果一直沒有合適的節(jié)點，會一直到達根 節(jié)點，循環(huán)結束。如果找到了合適的p ，則將p 的兄弟節(jié)點信息，寫入一個隊列q ，隊 列q 中存放著候選節(jié)點的列表，n 可以以先進先出的次序從隊列q 中取出節(jié)點，進行選 擇；從隊列q 中依次取出候選節(jié)點；將p 指向從隊列中取出的節(jié)點；如果節(jié)點p 的預留 鏈路還有，則p 就是要找的節(jié)點，跳出循環(huán)；否則，將節(jié)點p 的子女節(jié)點加入隊列q 中，繼續(xù)循環(huán)。 其主要思想是節(jié)點為自己尋找備份鏈路，具體算法示意圖如圖3 3 。 1 5l6l7 1 81 92 02 l2 2 圖3 0p c p 算法 3 2p c p 算法與r o t 算法實驗分析： 評價標準： 實驗中的評價指標有以下幾種： 平均加入時間( a v e r a g ej o i l lt i m e ) ：節(jié)點尋找到備用父母節(jié)點所花的時間的 平均值，這個指標說明尋找備用節(jié)點的時間開銷； 加入控制負載( j o i l l c o 呦1d ，酣1 e a d ) ：所有節(jié)點找到備用父母節(jié)點所用的控 制報文的個數，這個指標說明了尋找備用節(jié)點所占用的網絡資源； 鄭州大學碩士學位論文 各用鏈路平均延遲( b a c k u pl i n ka v e 豫g ed e l a y ) ：節(jié)點采用備用鏈路后的平 均延遲，這個指標說明了備用鏈路對轉發(fā)樹通信延遲的影響。 實驗目的： 實驗的主要目的，通過對p c p 算法和r o t 算法在基于m ，r p 協(xié)議構造的轉發(fā)樹上 進行轉發(fā)樹重構的對比實驗，獲得上述的幾種評價指標的實驗結果，從結果中比較這兩 種算法在傳輸性能、控制負載規(guī)模以及加入時間方面的優(yōu)劣及性能差別。 實驗方法和內容： 實驗所需的網絡拓撲構造采用( * m 2 8 生成，實驗中涉及的算法，使用c 群語言 在w i n d o w s2 0 0 3s e c r 上進行了實現，實驗主機配置為p e 以u m42 8 gc p u ，1 g b 內 存，1 2 0 g bs a t a 硬盤，1 0 0 m 以太網接口。 針對上面的3 個評價指標，在節(jié)點數目不同和節(jié)點出度后為5 的情況下，對 p c p 算法和p l a 算法進行了對比實驗。 對于節(jié)點規(guī)模n ，分為小規(guī)模網絡、中等規(guī)模網絡、大規(guī)模網絡三種情況進行實 驗，節(jié)點規(guī)模的集合分別用m ， ，2 ，3 表示，如表格3 1 。 瓣淵溯湖黼嘲趲麟黼燃黼黛斕麓 啪 1 0 ，2 0 ，3 0 ，4 0 ，5 0 ，7 0 ，8 0 ，9 0 ，1 0 0 )小規(guī)模網絡 ( 1 0 0 ，2 0 0 ，3 0 0 ，4 0 0 ，5 0 0 ，8 0 0 ，7 0 0 ，o中等規(guī)橫網 ，9 0 0 ，1 0 0 0 ，絡 韃3 1 0 0 0 ，2 0 0 0 ，3 0 0 0 ，4 0 0 0 ，5 0 0 0 ，0 0 ，7犬覿模網絡 0 0 0 ，8 0 0 0 ，9 0 0 0 ，1 0 0 0 0 ) 表格3 。l 節(jié)點規(guī)模 測量指標中，平均加入時間用a j 表示，備份鏈路延遲用b d 表示，加入控制負載 用j o 表示如表格3 。2 。 應用層組播轉發(fā)樹重構技術研究 溪黼黎鬟豢黧黧l 霧| | 瀵糍麟蘸麓闌黼 a j平均加入時問 b d備份鏈路延遲 j 0加入控制負載 表格3 2 測量指標 m t p 協(xié)議，m t p l 協(xié)議用p l 表示，m 邛2 協(xié)議用p 2 表示，如表格3 _ 3 。 表格3 - 3 m t p 協(xié)議 在實驗中，髓n 1 郇t o 口l 就表示，出度為5 ，節(jié)點規(guī)模為小規(guī)模，采用m 仲l 協(xié) 議構造的轉發(fā)樹上運行r o t 算法得到的平均加入時間的值。 實驗結果及其分析： 3 2 1 平均加入時間 圖3 - 4 平均加入時間_ n 1 鄭州大學碩士學位論文 圖3 _ 5 平均加入時間p 眩 圖3 6 平均加入時間予昭 從圖中可以看出，r o t 算法的平均加入時間總體上都大于p c p 算法的平均加入時 間，但是隨著節(jié)點規(guī)模的增加，基于m t p l 生成樹，r o t 算法與p c p 算法的差距增 大，而基于m r p 2 生成樹，r o t 算法與p c p 算法的差距較小。 結論： 1 、p c p 算法的平均加入時間優(yōu)于i 的t 算法； 2 、i t o t 算法與p c p 算法的差距，基于m t p l 樹相差較大，而基于m r p 2 樹相差 較小。 應用層組播轉發(fā)樹重構技術研究 3 2 2 備用鏈路延遲 圖3 7 備用鏈路延遲- n 1 圖3 8 備用鏈路延遲_ n 2 鄭州大學碩士學位論文 圖3 9 備用鏈路延遲- 量舊 從圖中不難看出，采用i t 算法的備用鏈路平均延遲均小于采用p c p 算法的結 果，這主要是因為在r o t 算法中，主要是在節(jié)點的子樹中來構造一棵新的轉發(fā)樹，這 些節(jié)點在物理上本身就相距較近；而在p c p 算法中，是在祖先節(jié)點的兄弟節(jié)點及其子 樹中尋找備用節(jié)點，因此，p c p 算法選擇的備用節(jié)點會比r o t 算法的備用節(jié)點的物理 距離要遠一些，實驗結果也說明了這一點。 結論： 一般情況下，r o t 算法的備用鏈路平均延遲優(yōu)于p c p 算法；但是在大規(guī)模網絡 下，基于m r p 2 生成樹的p c p 算法優(yōu)于r o t 算法。 應用層組播轉發(fā)樹重構技術研究 3 2 3 加入控制負載 圖3 1 0 加入控制負載n 1 圖3 1 l 加入控制負載 鄭州大學碩士學位論文 圖3 1 2 加入控制負載n b 從圖中可以看出，無論節(jié)點規(guī)模如何增加，采用r o t 算法的控制負載總是略高于 p c p 算法。 結論：p c p 算法的加入控制負載優(yōu)于r o t 算法。 3 3 本章小結 通過前面的實驗，可以得到兩種算法的比較結論。p c p 算法的平均加入時間和平均 加入負載優(yōu)于r o t 算法，但是備用節(jié)點鏈路平均延遲不如r o t 算法，這說明p c p 算 法在尋找備用節(jié)點的開銷方面小于r o t 算法，但是找到的備用節(jié)點的延遲特性不如 r o t 算法。相對而言，r o t 算法更適合于轉發(fā)樹結構相對固定的應用場合。 應用層組播轉發(fā)樹重構技術研究 第4 章基于p i a 算法的重構解決方案 本章研究的重點是p l a 算法的實現和仿真實驗分析。主要內容為，首先是在p c p 算法的基礎上，針對p c p 算法的一些缺陷，提出并實現了p l a 算法。然后通過實驗對 p c p 、p l a 和r o t 算法進行對比仿真實驗，最后是實驗結果分析。 4 1 具體算法： 該算法借鑒了r o t 算法和p c p 算法的思想，在p c p 算法的基礎上進行了改進。具 體思想： 1 采用了“鏈路預留”的思想進行樹的重構 2 節(jié)點為自己尋找備份鏈路 3 充分利用了預失效節(jié)點的父母節(jié)點的剩余出度 4 對節(jié)點間的連接開銷進行比較，優(yōu)先選擇延遲最低的建立連接 設對于節(jié)點f ，總出度為d ( f ) ，已經使用的出度是吃( f ) ，未使用的出度為4 ( f ) ， 未使用的出度中，預留鏈路的出度為d 。( f ) ，則有： d ( f ) = 吒( f ) + 4 ( f ) + 以( f ) 4 1 1 算法描述： 設要選擇備用父母節(jié)點”的節(jié)點為甩，p 為指向某個節(jié)點的指針，p l a 算法的偽碼 描述如下： 1 p r o c e d u r ep l a 0 ) 2 p 2 n p a r e m 3 肝= m i l l d e l a y 0 ) 選擇最小延遲的節(jié)點 4 i f ，f m 5 h p a r c r l b b c 7 p 糊n ； ，虛鏈路 6 r e l 脅： 7 e l s e i 印p a r e n t n u l l 姐d p p a r e m d p o 鄭州大學碩士學位論文 8 9 e l s e 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 3 0 3 1 3 2 3 3 3 4 3 5 3 6 3 7 r e n m p p 黼t預留鏈路 ( w m e p s i b l i i l 黔i sn u l l p 2 p _ p 嬲l t ； i f p d p 0 r e t i 】r n p ) i f p s i b l i n g s = n u l l n ol i l l k p r o v i d e d e x i t e l s e a d dt 咖p p s i b h n g s & 叻 a d d ( a ，b ) 把d p 0 的節(jié)點加入到a 中 w k l ea = 1 1 u l la n db c n u l l 向r 翩c h ( r l o d e i n b ) ( r 肌o v e ( 1 1 0 d e ) a d dt e i l l 邸舯d e 枷l d r e n ) ) a d d ( 凡b ) ) w l l i l ea m m p = m i l l d d a y j r e l i n k ( a ，n ) 選擇最小延遲 r e t u m p ) ) 應用層組播轉發(fā)樹重構技術研究 3 8 1 3 9 r e t 哪o 4 0 e n dp r o c o d u r e 具體算法描述： 行l(wèi) ，算法開始，參數為節(jié)點玎，代表要計算的節(jié)點 行2 ，首先將指針指向”的父母節(jié)點p 行3 ，節(jié)點口計算最小延遲節(jié)點聊 行4 6 ，如果n = 聊，節(jié)點甩與p 的父母節(jié)點建立虛鏈路，算法結束 行7 - 8 ，如果p 的父母節(jié)點非根節(jié)點且有預留鏈路，則p 的父母節(jié)點就是要找的節(jié) 點，算法結束。 行9 ，如果非上述情況，則算法繼續(xù)。 行1 0 一1 6 ，如果p 有預留鏈路，則p 就是要找的節(jié)點，算法結束；如果p 沒有預留 鏈路，但是p 有兄弟節(jié)點，則循環(huán)結束：否則，繼續(xù)往上游走，如果一直沒有合適的節(jié) 點，會一直到達根節(jié)點，循環(huán)結束。 行1 7 1 9 ，如果一直找到根結點都找不到合適的p ，則結束尋找過程，返回o ； 行2 0 ，如果找到了合適的琺算法繼續(xù) 行2 1 。2 2 ，將p 的兄弟節(jié)點信息以及節(jié)點聊，寫入一個集合b 中，集合b 中存放 著臨時候選節(jié)點的列表 行2