（計(jì)算機(jī)應(yīng)用技術(shù)專(zhuān)業(yè)論文）應(yīng)用層組播轉(zhuǎn)發(fā)樹(shù)重構(gòu)技術(shù)研究.pdf

鄭卅l 大學(xué)碩士學(xué)位論文 摘要 近年來(lái)，一對(duì)多、多對(duì)多通信的需求使得i p 組播和基于端系統(tǒng)的應(yīng)用層組播成為了 網(wǎng)絡(luò)研究的熱點(diǎn)課題。i p 組播目前面臨許多問(wèn)題，影響了其在i n t e m 戰(zhàn)上的部署，而應(yīng) 用層組播雖然易于部署，但端系統(tǒng)的不穩(wěn)定性導(dǎo)致了轉(zhuǎn)發(fā)樹(shù)的不穩(wěn)定。因此，在應(yīng)用層 組播中，轉(zhuǎn)發(fā)樹(shù)的重構(gòu)就尤為重要。目前針對(duì)轉(zhuǎn)發(fā)樹(shù)的重構(gòu)有兩種策略：一種是前向 式，另一種是后向式。由于前向式重構(gòu)是在父節(jié)點(diǎn)失效前預(yù)先計(jì)算備用節(jié)點(diǎn)，減少了重 構(gòu)時(shí)間，因而能更好的提高轉(zhuǎn)發(fā)樹(shù)的可靠性。 針對(duì)轉(zhuǎn)發(fā)樹(shù)的重構(gòu)問(wèn)題，本文進(jìn)行了兩部分工作：第一部分工作是對(duì)現(xiàn)有的幾種前 向式重構(gòu)算法進(jìn)行了對(duì)比實(shí)驗(yàn)研究。研究表明，p c p 算法在尋找備用節(jié)點(diǎn)的開(kāi)銷(xiāo)方面小 于r o t 算法，但是找到的備用節(jié)點(diǎn)的延遲特性不如r o t 算法。相對(duì)而言，r o t 算法 更適合于轉(zhuǎn)發(fā)樹(shù)結(jié)構(gòu)相對(duì)固定的應(yīng)用場(chǎng)合。第二部分工作，在對(duì)上述幾種前向式重構(gòu)算 法研究的基礎(chǔ)上，提出了新的重構(gòu)算法p l a 算法。該算法的核心思想是在“鏈路預(yù) 留”思想的基礎(chǔ)上，考慮了鏈路延遲約束。本文將該算法同其它前向式重構(gòu)算法進(jìn)行了 對(duì)比試驗(yàn)，結(jié)果表明：在平均加入開(kāi)銷(xiāo)與備份鏈路延遲這對(duì)矛盾中，p l a 算法作了比較 合適的調(diào)和。同p c p 算法相比較，p l a 算法雖然在平均加入開(kāi)銷(xiāo)上有所增加，但是重 構(gòu)的組播樹(shù)的備用鏈路延遲降低了；同i 的t 算法相比較，雖然p l a 算法的備份鏈路延 遲不如r o t 算法，但是p l a 算法的平均加入開(kāi)銷(xiāo)耗費(fèi)的較少。研究表明，p l a 算法更 適合于在節(jié)點(diǎn)相對(duì)不穩(wěn)定的h 峋n 甙中部署，尤其是那些既考慮通信質(zhì)量又要求連接開(kāi) 銷(xiāo)的應(yīng)用場(chǎng)合，譬如網(wǎng)絡(luò)電視，b t 下載以及大規(guī)模流媒體的實(shí)時(shí)應(yīng)用等。 關(guān)鍵詞：計(jì)算機(jī)網(wǎng)絡(luò)，應(yīng)用層組播，轉(zhuǎn)發(fā)樹(shù)重構(gòu)，前向式重構(gòu) 應(yīng)用層組插轉(zhuǎn)發(fā)樹(shù)重構(gòu)技術(shù)研究 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 嘲財(cái)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 礎(chǔ)，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 本人的學(xué)位論文是在導(dǎo)師指導(dǎo)下獨(dú)立撰寫(xiě)并完成的，學(xué)位論文沒(méi)有剽竊、抄襲等違 反學(xué)術(shù)道德、學(xué)術(shù)規(guī)范的侵權(quán)行為，否則，本人愿意承擔(dān)由此產(chǎn)生的一切法律責(zé)任和法 律后果，特此鄭重聲明。 學(xué)位論文作者( 簽名)：秘書(shū) l g 只乙日 年否妒 鄭州大學(xué)碩士學(xué)位論文 第1 章引言 1 1 課題背景及選題依據(jù) 近年來(lái)，隨著網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，f t p l 、h t l p 、s m t p 3 等傳統(tǒng)數(shù)據(jù)業(yè)務(wù)已經(jīng)難 以滿(mǎn)足人們對(duì)信息業(yè)務(wù)的需求，視頻點(diǎn)播、遠(yuǎn)程教學(xué)、新聞發(fā)布、視頻會(huì)議、股市行隋 發(fā)布、多媒體遠(yuǎn)程教育、c s c 咿協(xié)同計(jì)算等業(yè)務(wù)在應(yīng)用中變得日益重要。這類(lèi)業(yè)務(wù)的 特點(diǎn)是顯著的高帶寬的多媒體應(yīng)用，這些應(yīng)用需要比較大的網(wǎng)絡(luò)帶寬，會(huì)引發(fā)帶寬的急劇 消耗和網(wǎng)絡(luò)擁擠問(wèn)題，信息在一個(gè)組內(nèi)以一對(duì)多或者多對(duì)多的形式進(jìn)行傳輸。例如新聞 發(fā)布信息由一個(gè)服務(wù)器發(fā)布，大量不固定的接收端接收。如果采用單播方式來(lái)傳輸這 些信息，那么發(fā)送源就必須維護(hù)每個(gè)客戶(hù)信息。當(dāng)客戶(hù)數(shù)目很多時(shí)，對(duì)于發(fā)送源來(lái)說(shuō)還 需要很高的傳輸速率。另外，相同的數(shù)據(jù)可能在同一個(gè)鏈路上傳輸多次，消耗大量的網(wǎng) 絡(luò)帶寬。為了緩解網(wǎng)絡(luò)瓶頸，人們提出了組播口m u m c a 啪 1 技術(shù)方案。但是從因特網(wǎng)中 p 組播的應(yīng)用現(xiàn)狀看，i p 組播并沒(méi)有取得預(yù)期的成功。由于組播路由器需要為每個(gè)活動(dòng) 的組維護(hù)路由狀態(tài)信息，網(wǎng)絡(luò)中大量的活動(dòng)組將需要路由器巨大的存儲(chǔ)和處理開(kāi)銷(xiāo)；開(kāi) 放的口組播模型在開(kāi)放的i n t e m 融環(huán)境中難以支持有效的管理和控制機(jī)制。以上這些因 素都制約了p 組播的發(fā)展。于是，一些研究者提出將復(fù)雜的組播功能放在端系統(tǒng)( e 1 1 d _ s y s 衄n ) 2 3 實(shí)現(xiàn)的新思想，也就是使用應(yīng)用層組播( a p p l i c 鰣o nl a y e rm u l t i c a s t ) 技術(shù)來(lái) 替代傳統(tǒng)的m 組播技術(shù)，由于應(yīng)用層組播保持了互聯(lián)網(wǎng)的“單播、盡力發(fā)送”模型，并 且部署方便等優(yōu)點(diǎn)，得到了迅速的普及，成功地案例有香港理工大的c o o l s h a m ，華中 科大的p p l i v e 等。 應(yīng)用層組播和傳統(tǒng)的p 組播技術(shù)相比，可以避開(kāi)網(wǎng)絡(luò)層實(shí)現(xiàn)組播功能的許多難題： 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 血 應(yīng)用層組播轉(zhuǎn)發(fā)樹(shù)重構(gòu)技術(shù)研究 1 應(yīng)用層組播的狀態(tài)在主機(jī)系統(tǒng)中維護(hù)，不需要路由器保持組的狀態(tài)，解決了業(yè)務(wù) 的擴(kuò)展性問(wèn)題； 2 組播應(yīng)用可以隨時(shí)部署，不需要網(wǎng)絡(luò)設(shè)備的升級(jí)和功能擴(kuò)展； 3 可以簡(jiǎn)化組播的控制、可靠等功能的實(shí)現(xiàn)，建立在網(wǎng)絡(luò)連接之上的應(yīng)用層組播可 以使用傳輸層的t c p 、u d p 協(xié)議，如可以利用t c p 的可靠和擁塞控制簡(jiǎn)化組播 的可靠和擁塞控制。當(dāng)然應(yīng)用層組播對(duì)帶寬的節(jié)省不如m 組播；協(xié)議額外的 開(kāi)銷(xiāo)比較大。但是因?yàn)槠溟_(kāi)發(fā)方便，部署簡(jiǎn)單應(yīng)用層組播還是具有比較好的應(yīng) 用前景。 由于應(yīng)用層組播是基于端系統(tǒng)來(lái)構(gòu)造其轉(zhuǎn)發(fā)樹(shù)，因而端系統(tǒng)的穩(wěn)定性決定著應(yīng)用層 組播轉(zhuǎn)發(fā)樹(shù)的穩(wěn)定性。應(yīng)用層組播不像傳統(tǒng)的m 組播那樣，轉(zhuǎn)發(fā)樹(shù)中的葉節(jié)點(diǎn)通常是 端系統(tǒng)，這些節(jié)點(diǎn)潛在的比路由器更易失效或頻繁的退出轉(zhuǎn)發(fā)樹(shù)，一旦發(fā)生這種情況， 那么該節(jié)點(diǎn)下游的所有節(jié)點(diǎn)將受到影響。因此，在應(yīng)用層組播應(yīng)用中，一個(gè)很重要的問(wèn) 題就是如何迅速的恢復(fù)轉(zhuǎn)發(fā)樹(shù)，使得受影響的這些節(jié)點(diǎn)盡量縮短其服務(wù)中斷。 鑒于此，應(yīng)用層組播轉(zhuǎn)發(fā)樹(shù)的重構(gòu)問(wèn)題逐漸被提了出來(lái)，并成為熱點(diǎn)問(wèn)題。 1 2 國(guó)內(nèi)外研究現(xiàn)狀 目前，在樹(shù)的重構(gòu)問(wèn)題上，有兩種策略，一種稱(chēng)為后向式( r e a c 垃v ea p p r o a c h ) 策 略，該方法是在節(jié)點(diǎn)失效后，再進(jìn)行樹(shù)的重構(gòu)，代表的方法有( 4 5 】 6 】，這種事后補(bǔ)救 的方法會(huì)花去不少時(shí)間，用于在多個(gè)節(jié)點(diǎn)間選擇一個(gè)合適的加入點(diǎn)，來(lái)重新構(gòu)造轉(zhuǎn)發(fā) 樹(shù)。這樣就使得受到影響的節(jié)點(diǎn)會(huì)有一個(gè)比較長(zhǎng)的服務(wù)中斷；另一種方法稱(chēng)為前向式 ( 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 】，這種方法的特 點(diǎn)是在節(jié)點(diǎn)失效之前預(yù)先計(jì)算好節(jié)點(diǎn)的新的父母節(jié)點(diǎn)，一旦該節(jié)點(diǎn)的父母節(jié)點(diǎn)退出，就 可以根據(jù)預(yù)先計(jì)算的結(jié)果快速地找到新父母節(jié)點(diǎn)，避免花太多的時(shí)間用于尋找新加入 點(diǎn)，從而減少服務(wù)的中斷時(shí)間。 2 鄭卅l 大學(xué)碩士學(xué)位論文 1 3 課題所做的工作及論文結(jié)構(gòu) 1 3 1 本文主要工作 本文工作主要分為兩部分，前期工作是對(duì)現(xiàn)有幾種主要技術(shù)的實(shí)驗(yàn)、分析、比較幾 種前向式算法的優(yōu)缺點(diǎn)；后期針對(duì)上述算法的優(yōu)缺點(diǎn)提出了一種新的重構(gòu)算法p l a 算 法，這是一種結(jié)合了p c p 【8 和r o t 7 兩種典型前向式重構(gòu)策略的算法，其核心思想是 節(jié)點(diǎn)采用了“鏈路預(yù)留”的思想，為自身尋找備份鏈路，進(jìn)行樹(shù)的重構(gòu)。 本課題的研究目標(biāo)為：利用前向式重構(gòu)策略，在重構(gòu)應(yīng)用層組播轉(zhuǎn)發(fā)樹(shù)的過(guò)程中， 在控制節(jié)點(diǎn)加入轉(zhuǎn)發(fā)樹(shù)的花費(fèi)開(kāi)銷(xiāo)基礎(chǔ)上，盡量降低備份鏈路的延遲，減少數(shù)據(jù)丟失 率，使得流媒體等高帶寬應(yīng)用在h e n l e t 上的應(yīng)用更加流暢。 1 3 2 論文結(jié)構(gòu) 通過(guò)對(duì)現(xiàn)有應(yīng)用層組播轉(zhuǎn)發(fā)樹(shù)重構(gòu)技術(shù)的研究，實(shí)現(xiàn)了一個(gè)基于m 僅c a s t 1 0 應(yīng)用 層組播通信模型的組播轉(zhuǎn)發(fā)樹(shù)重構(gòu)算法，該算法在稍微增加了節(jié)點(diǎn)加入開(kāi)銷(xiāo)的基礎(chǔ)上， 大大降低了重構(gòu)后轉(zhuǎn)發(fā)樹(shù)的備份鏈路延遲，由于該算法的靈活性秘可擴(kuò)展性，因而比 r o t 算法更易于部署。 本文組織如下： 第二章“相關(guān)技術(shù)”，介紹了應(yīng)用層組播轉(zhuǎn)發(fā)樹(shù)重構(gòu)技術(shù)所涉及的相關(guān)技術(shù)。其 中包括組播、應(yīng)用層組播、m 黜等通信模型。 第三章“前向式重構(gòu)的相關(guān)解決方案及實(shí)驗(yàn)分析”，介紹了目前幾種前向式策略的 具體方案，繼而通過(guò)仿真實(shí)驗(yàn)、分析、驗(yàn)證了p c p 算法和r o t 算法在幾個(gè)重要衡量指 標(biāo)上的優(yōu)缺點(diǎn)。 第四章“基于p l a 算法的重構(gòu)解決方案”，通過(guò)對(duì)p c p 算法和r o t 算法的優(yōu)缺 點(diǎn)比較分析，提出了一個(gè)基于p c p 算法的p l a 算法，并通過(guò)仿真實(shí)驗(yàn)來(lái)分析驗(yàn)證了 p l a 算法對(duì)p c p 算法在重要衡量指標(biāo)上的改進(jìn)。 第五章“結(jié)束語(yǔ)”，給出本文的結(jié)論，同時(shí)根據(jù)存在的問(wèn)題，提出了下一步的研究 方向。 應(yīng)用層組播轉(zhuǎn)發(fā)樹(shù)重構(gòu)技術(shù)研究 第2 章相關(guān)技術(shù) 本章將介紹分析一些本課題所涉及到的相關(guān)技術(shù)，內(nèi)容組織如下：首先討論并比較 了目前可用的群組通信模型，包括；口組播、應(yīng)用層組播和m i 】【c a s t 1 0 。接著介紹在 m i ) 【c a s t 中所涉及到的一些相關(guān)技術(shù)。 2 1 組通信模型 組通信在分布式系統(tǒng)和并行計(jì)算機(jī)系統(tǒng)中有著非常廣泛的應(yīng)用。組是動(dòng)態(tài)的，可以 創(chuàng)建新的組，也可以注銷(xiāo)舊的組。參與者可以動(dòng)態(tài)的加入或退出組，因此需要一種機(jī)制 來(lái)管理組和組的成員。組通信模型的優(yōu)勢(shì)是避免了傳統(tǒng)點(diǎn)對(duì)點(diǎn)通信模型中，針對(duì)每個(gè)接 受者，發(fā)送者都要轉(zhuǎn)發(fā)次數(shù)據(jù)包，浪費(fèi)網(wǎng)絡(luò)資源的情況。組通信模型中，數(shù)據(jù)往往同 時(shí)傳遞給組內(nèi)多個(gè)接受者，一次傳輸，多點(diǎn)到達(dá)，節(jié)省了網(wǎng)絡(luò)資源。因而組通信成為網(wǎng) 絡(luò)研究中的熱點(diǎn)課題。 2 1 1 碑組播 早在1 9 8 8 年，斯坦福大學(xué)的博士生s e d e e r i n g 就提出了p 組播機(jī)制。它是最 早的、最有效的組播傳輸機(jī)制。主機(jī)之間一對(duì)一組的通訊模式，將坤數(shù)據(jù)報(bào)從一個(gè)源 傳送到多個(gè)目的地，將信息的拷貝發(fā)送到一組地址，到達(dá)所有想要接收它的接收者。也 就是加入了同一個(gè)組的主機(jī)可以接受到此組內(nèi)的所有數(shù)據(jù)，網(wǎng)絡(luò)中的交換機(jī)和路由器只 向有需求者復(fù)制并轉(zhuǎn)發(fā)其所需數(shù)據(jù)。群組的各個(gè)成員可以分布于各個(gè)獨(dú)立的物理網(wǎng)絡(luò) 上，主機(jī)根據(jù)組地址( g f o u p a d d r e s s ) 可以向路由器發(fā)送i g 口5 履m d 6 1 1 】 1 2 】請(qǐng)求，請(qǐng) 求加入或退出某個(gè)組，路由器收到用戶(hù)請(qǐng)求后，根據(jù)運(yùn)行的組播路由協(xié)議的不同，在路 由器間構(gòu)造共享樹(shù)( r p f 7 ) 或者源樹(shù)( s p r ) ，來(lái)保證組播數(shù)據(jù)自旨?jí)驈陌l(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 鄭州大學(xué)碩士學(xué)位論文 達(dá)接收者。網(wǎng)絡(luò)中的路由器和交換機(jī)有選擇的復(fù)制并傳輸數(shù)據(jù)，即只將組內(nèi)數(shù)據(jù)傳輸給 那些加入組的主機(jī)。這樣既能一次將數(shù)據(jù)傳輸給多個(gè)有需要( 加入組) 的主機(jī)，又能保 證不影響其他不需要( 未加入組) 的主機(jī)的其他通訊。 2 1 1 1p 組播協(xié)議 i p 組播協(xié)議主要分為組管理協(xié)議和路由協(xié)議兩類(lèi)。其中組管理協(xié)議負(fù)責(zé)主機(jī)和路由 器之間的交互，主機(jī)通過(guò)組管理協(xié)議來(lái)告知路由器加入或者離開(kāi)組播組；組播路由協(xié)議 負(fù)責(zé)在路由器之間構(gòu)造組播轉(zhuǎn)發(fā)樹(shù)，以完成組播數(shù)據(jù)的分發(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 國(guó)v 2 1 4 ，其中i g 棚p 1 ，2 和d v l 功能基本類(lèi)似，目前較為普 及。 在組播路由協(xié)議方面，早期的協(xié)議，例如d 、，】誑沖9 1 5 、m o s p f l 0 1 6 等，由于可 擴(kuò)展性較差，以及依賴(lài)于單播路由協(xié)議，因此逐步被淘汰。目前的組播路由協(xié)議主要分 為兩大類(lèi)，即域內(nèi)組播路由協(xié)議和域間組播路由協(xié)議。域內(nèi)協(xié)議主要有p - d m 17 、 p d 訌s m 1 8 】，其中p 正d m “采用洪泛加剪枝的工作模式，不適合較大規(guī)模的網(wǎng)絡(luò)； p 訂s m l 2 采用接收者發(fā)起構(gòu)建共享樹(shù)的工作模式，是目前使用較多的組播路由協(xié)議， 其主要缺點(diǎn)是協(xié)議比較復(fù)雜。 在域間協(xié)議中，目前較為成熟的方案是p d “一舒d 伍佃( m m s d p 三個(gè)協(xié)議結(jié)合起 來(lái)，由p m s m 協(xié)議負(fù)責(zé)域內(nèi)的組播轉(zhuǎn)發(fā)樹(shù)構(gòu)建，m b g p l 3 協(xié)議( i9 傳遞不同a s 間的組 播路由信息，m s d p 協(xié)議【2 0 傳遞不同域內(nèi)的組播源通告信息。m s d p 協(xié)議的主要缺點(diǎn) 是當(dāng)自治域數(shù)量較多時(shí)，該協(xié)議的可擴(kuò)展性不是太好，因此被看作是一種過(guò)渡方案，只 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 應(yīng)用層組播轉(zhuǎn)發(fā)樹(shù)重構(gòu)技術(shù)研究 是在v 4 環(huán)境下使用，在i p v 6 環(huán)境中沒(méi)有被采用。除了m s d p l 4 協(xié)議，肼還提出了 另一種域間組播解決方案，即m a s c l 5 b g 啪p 1 6 協(xié)議【2 1 ，但是由于協(xié)議本身過(guò)于復(fù) 雜，沒(méi)有得到廣泛的采用。 i p 組播工作模式如圖2 1 ： 口庸盤(pán)鞲+ h 蟪斌嘏措捧輸蟪掩 。接收董l 一一一散捌傳相溉向 毅掘秤童帆 圖2 1i p 組播 口組播的優(yōu)點(diǎn)： 1 需要相同數(shù)據(jù)流的客戶(hù)端加入相同的組共享一條數(shù)據(jù)流，節(jié)省了服務(wù)器的負(fù) 載。具備廣播所具備的優(yōu)點(diǎn)。 2 由于組播協(xié)議是根據(jù)接受者的需要對(duì)數(shù)據(jù)流進(jìn)行復(fù)制轉(zhuǎn)發(fā)，所以服務(wù)端的服務(wù) 總帶寬不受客戶(hù)接入端帶寬的限制。p 協(xié)議允許有2 億6 千多萬(wàn)個(gè)組播，所以 其提供的服務(wù)可以非常豐富【2 2 。 3 此協(xié)議和單播協(xié)議一樣允許在鋤e t 寬帶網(wǎng)上傳輸。 m 組播的缺點(diǎn)： 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 鄭州大學(xué)碩士學(xué)位論文 1 與單播協(xié)議相比沒(méi)有糾錯(cuò)機(jī)制，發(fā)生丟包錯(cuò)包后難以彌補(bǔ)，但可以通過(guò)一定的 容錯(cuò)機(jī)制和q o s 加以彌補(bǔ)。 2 訪問(wèn)控制較為困難，對(duì)于運(yùn)營(yíng)商而言，如果想在網(wǎng)絡(luò)中使用組播技術(shù)，就希望 能夠進(jìn)行流量統(tǒng)計(jì)，以便于計(jì)費(fèi)功能的實(shí)現(xiàn)，而傳統(tǒng)的組播難以實(shí)現(xiàn)這樣的功 能。 3 路由協(xié)議復(fù)雜。目前使用的組播路由協(xié)議，無(wú)論是域內(nèi)的還是域間的，都比較 復(fù)雜。在設(shè)計(jì)核心路由器的時(shí)候，一般需要用硬件來(lái)實(shí)現(xiàn)組播數(shù)據(jù)報(bào)文的轉(zhuǎn) 發(fā)，但是目前普遍采用的協(xié)議，有許多交互操作，致使協(xié)議實(shí)現(xiàn)較為復(fù)雜，且 不利于高端路由器使用硬件進(jìn)行加速。同時(shí)，這些協(xié)議的健壯性和百，擴(kuò)展性也 不夠理想。 4 加重了路由器的負(fù)載。為了使路由器支持組播通信機(jī)制，就必須在路由器中支 持各種組播路由協(xié)議和組管理協(xié)議，同時(shí)，路由器還要支持組播轉(zhuǎn)發(fā)表的構(gòu)造 以及完成組播數(shù)據(jù)報(bào)文的轉(zhuǎn)發(fā)。當(dāng)組播組數(shù)目比較多時(shí)，會(huì)給路由器增加不少 負(fù)載。 5 i p 組播要求所有路由器支持組播，而有些i s p 的路由器不愿意支持組播功能， 所以組播服務(wù)的部署、推廣變的很困難。 2 1 2 應(yīng)用層組播( a l m ：a p p l i c 甜o nl e v e lm u 城c 髂t ) 面對(duì)疋組播業(yè)務(wù)在因特網(wǎng)中的困境，一些研究者開(kāi)始反思疋組播體系結(jié)構(gòu)本身的 問(wèn)題，提出將復(fù)雜的組播功能放在端系統(tǒng)實(shí)現(xiàn)的新思想。端系統(tǒng)實(shí)現(xiàn)組播業(yè)務(wù)的思想是 將組播作為一種疊加的業(yè)務(wù)，實(shí)現(xiàn)為應(yīng)用層的服務(wù)，因此，端系統(tǒng)組播又稱(chēng)為應(yī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 。應(yīng)用層組播網(wǎng)的節(jié)點(diǎn)是組播成員主機(jī)，數(shù)據(jù)路由、 復(fù)制、轉(zhuǎn)發(fā)功能都由成員主機(jī)完成，成員主機(jī)之間建立一個(gè)疊加在p 網(wǎng)絡(luò)之上的、實(shí) 現(xiàn)組播業(yè)務(wù)邏輯的功能性網(wǎng)絡(luò)，稱(chēng)為疊加網(wǎng)( o v e r l a y n 酣 的r k ) 2 4 ，主機(jī)基于自組織 算法建立和維護(hù)疊加網(wǎng)。應(yīng)用層組播的數(shù)據(jù)在主機(jī)間實(shí)現(xiàn)復(fù)制和轉(zhuǎn)發(fā)，數(shù)據(jù)報(bào)沿著邏輯 鏈路轉(zhuǎn)發(fā)，多跳邏輯鏈路可能經(jīng)過(guò)同一條物理鏈路。應(yīng)用層組播的基本思想是保持互聯(lián) 應(yīng)用層組播轉(zhuǎn)發(fā)樹(shù)重構(gòu)技術(shù)研究 網(wǎng)原有的簡(jiǎn)單、不可靠、單播的轉(zhuǎn)發(fā)模型，由端系統(tǒng)實(shí)現(xiàn)組播轉(zhuǎn)發(fā)功能。工作模式如圖 2 2 ： 口路由器 熬拋積土機(jī) 。接收生機(jī)- ，澎捌瑤魁捂轉(zhuǎn)篾糾 圖2 _ 2 應(yīng)用層組播 應(yīng)用層組播與網(wǎng)絡(luò)層組播最大的區(qū)別在于，網(wǎng)絡(luò)層組播依賴(lài)路由器來(lái)構(gòu)造轉(zhuǎn)發(fā)樹(shù)； 而應(yīng)用層組播是在主機(jī)之間構(gòu)造轉(zhuǎn)發(fā)樹(shù)，處于網(wǎng)絡(luò)層的路由器只需支持單播就可以了， 這樣就大大簡(jiǎn)化了組播在網(wǎng)絡(luò)層的部署難題。圖2 3 所示為口層組播與應(yīng)用層組播的區(qū) 別：a 為數(shù)據(jù)源，b 、c 、d 為接收端。左圖采用網(wǎng)絡(luò)層組播技術(shù)，在路由器1 、2 、3 、 4 、5 之間構(gòu)造轉(zhuǎn)發(fā)樹(shù)，其中路由器l 為樹(shù)根。數(shù)據(jù)從數(shù)據(jù)源a 到達(dá)路由器1 后，數(shù)據(jù) 就沿著口層組播轉(zhuǎn)發(fā)樹(shù)轉(zhuǎn)發(fā)到各個(gè)路由器，然后再由路由器把數(shù)據(jù)轉(zhuǎn)發(fā)到各個(gè)接收 端。右圖采用應(yīng)用層組播技術(shù)，路由器1 、2 、3 、4 、5 就不需要做那些工作。數(shù)據(jù)由主 機(jī)a 傳遞到主機(jī)b 、d ，再由b 將數(shù)據(jù)傳遞到主機(jī)c ，這樣就完成了整個(gè)數(shù)據(jù)的分發(fā)與 接收。在這個(gè)過(guò)程中完全屏蔽了物理網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。實(shí)際上是在主機(jī)之間建立一個(gè)疊 加在p 網(wǎng)絡(luò)之上的、實(shí)現(xiàn)組播業(yè)務(wù)邏輯的疊加網(wǎng)。 鄭州大學(xué)碩士學(xué)位論文 口 蹄山器 艘朋豫封l 措轉(zhuǎn)粒櫥 o。i ：機(jī)料| 扮船維播轉(zhuǎn)笈樹(shù) 圖2 _ 3 口層組播與應(yīng)用層組播 但是，相對(duì)口組播而言，應(yīng)用層組播在節(jié)點(diǎn)的穩(wěn)定性、傳輸效率等方面面臨嚴(yán)峻 的挑戰(zhàn)。由于構(gòu)建者是普通的網(wǎng)絡(luò)主機(jī)，這些主機(jī)彼此不知在拓?fù)渲械南嗷ノ恢藐P(guān)系， 必須自己獲得一個(gè)拓?fù)?，并且在上面?gòu)建轉(zhuǎn)發(fā)樹(shù)。概括而言，影響應(yīng)用層組播傳輸效率 不高的主要因素有以下幾點(diǎn)： 1 擔(dān)當(dāng)復(fù)制轉(zhuǎn)發(fā)任務(wù)的普通終端主機(jī)的性能不高； 2 復(fù)制轉(zhuǎn)發(fā)工作在應(yīng)用層通過(guò)軟件實(shí)現(xiàn)； 3 通過(guò)主機(jī)自己測(cè)試產(chǎn)生的拓?fù)淇赡軙?huì)導(dǎo)致構(gòu)建出一個(gè)無(wú)法充分利用底層網(wǎng)絡(luò)設(shè) 施的轉(zhuǎn)發(fā)樹(shù)； 4 為了彌補(bǔ)口組播在安全可靠方面的缺憾，應(yīng)用層組播還要增加諸如安全可靠 之類(lèi)的服務(wù)，這將進(jìn)一步消耗主機(jī)的資源。 前三點(diǎn)就足以導(dǎo)致應(yīng)用層組播的性能相對(duì)口組播大打折扣，可能會(huì)導(dǎo)致整個(gè)服務(wù) 不可用。對(duì)于這個(gè)問(wèn)題，我們只能夠在第3 點(diǎn)上作一些研究工作，同時(shí)盡量開(kāi)發(fā)出效 率高的應(yīng)用層組播軟件。一些研究人員在致力于開(kāi)發(fā)更好的轉(zhuǎn)發(fā)樹(shù)構(gòu)建方法 2 5 】 2 6 。 無(wú)論如何，應(yīng)用層組播為我們提供了個(gè)解決組播問(wèn)題的途徑。 應(yīng)用層組播轉(zhuǎn)發(fā)樹(shù)重構(gòu)技術(shù)研究 2 1 3m i x c a s t m i x c a s t 1 0 】是一種混合了單播和組播的通信模型，其基本的出發(fā)點(diǎn)來(lái)源于h 】t e n l e t 核心簡(jiǎn)單化、邊緣復(fù)雜化的目標(biāo)。骨干網(wǎng)中的核心路由器承擔(dān)著大量的數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)， 應(yīng)當(dāng)盡量簡(jiǎn)化，一些復(fù)雜的控制功能應(yīng)當(dāng)盡量向邊緣轉(zhuǎn)移，m i ) ( c a s t 的思路就是在域間 采用單播通信，域內(nèi)采用組播通信。其工作模式如圖2 4 ： 口 瞎m 器戍剛聰昭撬傳輸線蘸 款攆游書(shū)機(jī)_ _ 耐熱瑤組撬傳輸縫路 。接收j 二桃( )m d p i m l x c 雌t 數(shù)荊代理) 圖2 4m i x c a s t 通信模型 域：在m i ) 【c a s t 通信模型中，域的概念是指一個(gè)可完全管理的接入網(wǎng)，比如個(gè)校 園網(wǎng)，或者一個(gè)企業(yè)網(wǎng)，或者一個(gè)小區(qū)寬帶網(wǎng)；例如圖2 4 中的域a 到域e 這5 個(gè)域。 m d p ：在每個(gè)域內(nèi)，都有一個(gè)設(shè)備充當(dāng)該域的m i ) 【c a s t 數(shù)據(jù)代理( m i x c a s td a _ i a p r o 珂) ，不同域之間的m d p 組成一個(gè)應(yīng)用層組播轉(zhuǎn)發(fā)樹(shù)，用于在域間轉(zhuǎn)發(fā)組播數(shù)據(jù)。 m d p 之間通過(guò)單播的方式進(jìn)行通信。 如圖2 _ 4 ，數(shù)據(jù)源位于域a 中，它首先把數(shù)據(jù)發(fā)送到所在域的姍d pa ，然后以該 m d p 為根，在所有接收端的啪) p 間構(gòu)造應(yīng)用層轉(zhuǎn)發(fā)樹(shù)，轉(zhuǎn)發(fā)樹(shù)之間采用單播通信，當(dāng) 數(shù)據(jù)到達(dá)m d p 后，在域內(nèi)采用m 組播通信，將數(shù)據(jù)分發(fā)給域內(nèi)的每個(gè)接收端。 】o 鄭州大學(xué)碩士學(xué)位論文 2 _ 2m i ) 【c a s t 通信模型中轉(zhuǎn)發(fā)樹(shù)的構(gòu)造 在m 政c a s t 通信模型中，轉(zhuǎn)發(fā)樹(shù)的構(gòu)造是基于m r p 協(xié)議 8 】 1 0 。在m r p 中，節(jié)點(diǎn) 加入算法的處理流程為：對(duì)于一個(gè)想加入樹(shù)的新節(jié)點(diǎn)n ，它首先向根結(jié)點(diǎn)發(fā)送一個(gè)j o n 請(qǐng)求，如果根節(jié)點(diǎn)還有剩余的出度，就會(huì)接受節(jié)點(diǎn)n 成為其子女，如果根結(jié)點(diǎn)的出度 已經(jīng)滿(mǎn)了，就會(huì)拒絕接受n 成為其子女，同時(shí)會(huì)把其子女節(jié)點(diǎn)的信息告訴n ；接下來(lái)， n 就在這些節(jié)點(diǎn)中，選擇個(gè)合適的節(jié)點(diǎn)進(jìn)行加入，如果這些節(jié)點(diǎn)的出度全部為o ，則 不在這一層進(jìn)行選擇，而是繼續(xù)往下走。 至于選取節(jié)點(diǎn)的原則，有兩個(gè)策略：( 1 ) 寬度+ 延遲優(yōu)先( m t p l ) 【8 。n 在有剩 余出度的節(jié)點(diǎn)中，選擇r r r 值最小的節(jié)點(diǎn)加入，如果所有節(jié)點(diǎn)的出度都為o ，則選擇 r 盯最小的節(jié)點(diǎn)往下遞歸尋找加入位置；( 2 ) 深度+ 延遲優(yōu)先( m t p 2 ) 【8 】。n 只選擇 f m 最小的節(jié)點(diǎn)，如果該節(jié)點(diǎn)有剩余出度，則n 成為該節(jié)點(diǎn)的子女，如果該節(jié)點(diǎn)沒(méi)有 剩余出度，則直接沿著這個(gè)節(jié)點(diǎn)往下尋找加入位置。 在下面的仿真試驗(yàn)中，m r p l 、m t p 2 算法，就是構(gòu)造轉(zhuǎn)發(fā)樹(shù)的兩種策略算法，我 們的實(shí)驗(yàn)分析，也是基于這兩種不同構(gòu)樹(shù)策略來(lái)進(jìn)行橫向比較的。 2 3 本章小結(jié) 本章主要介紹了網(wǎng)絡(luò)通信的幾種模型，并分析了其優(yōu)缺點(diǎn)，其中主要是m c a s t 模 型。它是一種結(jié)合了口組播和應(yīng)用層組播兩種技術(shù)的新的通信模型。本課題組播樹(shù)的 重構(gòu)實(shí)驗(yàn)就是基于該模型，通過(guò)該模型的組播樹(shù)構(gòu)造算法m 沖1 ( 廣度和延遲優(yōu)先) 和 m t p 2 ( 深度和延遲優(yōu)先) 分別來(lái)構(gòu)造兩棵轉(zhuǎn)發(fā)樹(shù)，進(jìn)而在這兩種轉(zhuǎn)發(fā)樹(shù)上分別運(yùn)行重構(gòu) 算法。 應(yīng)用層組播轉(zhuǎn)發(fā)樹(shù)重構(gòu)技術(shù)研究 第3 章前向式重構(gòu)技術(shù)研究和實(shí)驗(yàn)分析 本章研究的重點(diǎn)是應(yīng)用層組播轉(zhuǎn)發(fā)樹(shù)前向式重構(gòu)技術(shù)的研究和實(shí)驗(yàn)分析。首先描述 了現(xiàn)有的幾種前向式重構(gòu)算法，然后針對(duì)p c p 算法和r o t 算法進(jìn)行了仿真對(duì)比實(shí)驗(yàn)， 最后是對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行了分析和評(píng)價(jià)。 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 提出了一種隨機(jī)推進(jìn)的方法，每個(gè) 節(jié)點(diǎn)隨機(jī)選擇固定數(shù)目的其他節(jié)點(diǎn)，以小概率給每個(gè)選擇的結(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)。在節(jié)點(diǎn)失效 的情況下，該算法可以達(dá)到較高轉(zhuǎn)發(fā)率。另外，p r m 算法是一種數(shù)據(jù)層面的重構(gòu)策 略，它只是隨機(jī)向前推迸數(shù)據(jù)，沒(méi)有其他什么限制，具體算法示意圖如圖3 1 。 圇 繇三一 圖3 1p r m 算法 其中：o 代表節(jié)點(diǎn)，代表失效的節(jié)點(diǎn)或鏈路，一代表數(shù)據(jù)流向，曲線代表隨機(jī)推 進(jìn)的數(shù)據(jù)流向。 由于p r m 算法在數(shù)據(jù)層面上隨機(jī)轉(zhuǎn)發(fā)數(shù)據(jù)，因而會(huì)有一定的重復(fù)數(shù)據(jù)包，浪費(fèi)一 定的帶寬。而我們研究的重點(diǎn)則是下面兩種重構(gòu)策略，r o t 算法和p c p 算法，這兩種 算法是基于控制層面來(lái)進(jìn)行樹(shù)的重構(gòu)，p r m 算法則可以作為這兩種算法的很好補(bǔ)充。 3 1 2r o t 算法： r 0 r r 算法 7 中對(duì)于每一個(gè)非葉節(jié)點(diǎn)來(lái)說(shuō)，它必須為它的所有孩子節(jié)點(diǎn)找到一個(gè)備 用父母節(jié)點(diǎn)。一旦該節(jié)點(diǎn)失效，它的孩子節(jié)點(diǎn)能夠準(zhǔn)確知道誰(shuí)是它的新的父母節(jié)點(diǎn)。因 鄭州大學(xué)碩士學(xué)位論文 而，當(dāng)父母節(jié)點(diǎn)失效后，對(duì)于每一個(gè)孩子節(jié)點(diǎn)來(lái)說(shuō)能夠迅速地連接到它的備用父母節(jié) 點(diǎn)，能夠迅速地從失效中重新恢復(fù)中斷的服務(wù)。 具體算法描述： 對(duì)于節(jié)點(diǎn)n 來(lái)說(shuō)，節(jié)點(diǎn)n 為其孩子節(jié)點(diǎn)計(jì)算備用節(jié)點(diǎn)。首先節(jié)點(diǎn)n 從所用孩子節(jié)點(diǎn) 中選擇一個(gè)到節(jié)點(diǎn)n 的父母節(jié)點(diǎn)開(kāi)銷(xiāo)最小的節(jié)點(diǎn)c 1 ，把該節(jié)點(diǎn)的備用父母節(jié)點(diǎn)指向節(jié) 點(diǎn)n 的父母節(jié)點(diǎn)。然后把c l 節(jié)點(diǎn)及其孩子節(jié)點(diǎn)放入集合a 中，把節(jié)點(diǎn)n 剩余的孩子節(jié) 點(diǎn)放入集合b 中，然后從集合a 、b 中選擇連接開(kāi)銷(xiāo)最小的兩節(jié)點(diǎn)，把這兩個(gè)節(jié)點(diǎn)建立 起備用連接。同理直到集合b 中沒(méi)有節(jié)點(diǎn)。 其主要思想如圖3 2 ，預(yù)失效的節(jié)點(diǎn)( 5 ) 為孩子節(jié)點(diǎn)( 8 ，9 ，1 0 ) 計(jì)算備用父母節(jié)點(diǎn)。主要 考慮的是延遲優(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 】采用了“鏈路預(yù)留”的思想進(jìn)行樹(shù)的重構(gòu)，借鑒q o s 中采用的“資源 預(yù)留協(xié)議”( r s v p l 7 ) ，在轉(zhuǎn)發(fā)樹(shù)中預(yù)留些鏈路，用于樹(shù)的重構(gòu)。 7r c s m 礬e r e s 州甜徹p t 蝴l 應(yīng)用層組播轉(zhuǎn)發(fā)樹(shù)重構(gòu)技術(shù)研究 對(duì)于要計(jì)算預(yù)留鏈路的節(jié)點(diǎn)n 來(lái)說(shuō)，首先將指針指向n 的父母節(jié)點(diǎn)p ，如果p 沒(méi)有 兄弟節(jié)點(diǎn)，則沿著樹(shù)往上走，將p 指向原節(jié)點(diǎn)的父母節(jié)點(diǎn)。然后判斷節(jié)點(diǎn)p 是否有預(yù)留 鏈路，有預(yù)留鏈路則p 就是要找的節(jié)點(diǎn)，算法結(jié)束：如果p 沒(méi)有預(yù)留鏈路，但是p 有兄 弟節(jié)點(diǎn)，則循環(huán)結(jié)束；否則，繼續(xù)往上游走，如果一直沒(méi)有合適的節(jié)點(diǎn)，會(huì)一直到達(dá)根 節(jié)點(diǎn)，循環(huán)結(jié)束。如果找到了合適的p ，則將p 的兄弟節(jié)點(diǎn)信息，寫(xiě)入一個(gè)隊(duì)列q ，隊(duì) 列q 中存放著候選節(jié)點(diǎn)的列表，n 可以以先進(jìn)先出的次序從隊(duì)列q 中取出節(jié)點(diǎn)，進(jìn)行選 擇；從隊(duì)列q 中依次取出候選節(jié)點(diǎn)；將p 指向從隊(duì)列中取出的節(jié)點(diǎn)；如果節(jié)點(diǎn)p 的預(yù)留 鏈路還有，則p 就是要找的節(jié)點(diǎn)，跳出循環(huán)；否則，將節(jié)點(diǎn)p 的子女節(jié)點(diǎn)加入隊(duì)列q 中，繼續(xù)循環(huán)。 其主要思想是節(jié)點(diǎn)為自己尋找備份鏈路，具體算法示意圖如圖3 3 。 1 5l6l7 1 81 92 02 l2 2 圖3 0p c p 算法 3 2p c p 算法與r o t 算法實(shí)驗(yàn)分析： 評(píng)價(jià)標(biāo)準(zhǔn)： 實(shí)驗(yàn)中的評(píng)價(jià)指標(biāo)有以下幾種： 平均加入時(shí)間( a v e r a g ej o i l lt i m e ) ：節(jié)點(diǎn)尋找到備用父母節(jié)點(diǎn)所花的時(shí)間的 平均值，這個(gè)指標(biāo)說(shuō)明尋找備用節(jié)點(diǎn)的時(shí)間開(kāi)銷(xiāo)； 加入控制負(fù)載( j o i l l c o 呦1d ，酣1 e a d ) ：所有節(jié)點(diǎn)找到備用父母節(jié)點(diǎn)所用的控 制報(bào)文的個(gè)數(shù)，這個(gè)指標(biāo)說(shuō)明了尋找備用節(jié)點(diǎn)所占用的網(wǎng)絡(luò)資源； 鄭州大學(xué)碩士學(xué)位論文 各用鏈路平均延遲( b a c k u pl i n ka v e 豫g ed e l a y ) ：節(jié)點(diǎn)采用備用鏈路后的平 均延遲，這個(gè)指標(biāo)說(shuō)明了備用鏈路對(duì)轉(zhuǎn)發(fā)樹(shù)通信延遲的影響。 實(shí)驗(yàn)?zāi)康模?實(shí)驗(yàn)的主要目的，通過(guò)對(duì)p c p 算法和r o t 算法在基于m ，r p 協(xié)議構(gòu)造的轉(zhuǎn)發(fā)樹(shù)上 進(jìn)行轉(zhuǎn)發(fā)樹(shù)重構(gòu)的對(duì)比實(shí)驗(yàn)，獲得上述的幾種評(píng)價(jià)指標(biāo)的實(shí)驗(yàn)結(jié)果，從結(jié)果中比較這兩 種算法在傳輸性能、控制負(fù)載規(guī)模以及加入時(shí)間方面的優(yōu)劣及性能差別。 實(shí)驗(yàn)方法和內(nèi)容： 實(shí)驗(yàn)所需的網(wǎng)絡(luò)拓?fù)錁?gòu)造采用( * m 2 8 生成，實(shí)驗(yàn)中涉及的算法，使用c 群語(yǔ)言 在w i n d o w s2 0 0 3s e c r 上進(jìn)行了實(shí)現(xiàn)，實(shí)驗(yàn)主機(jī)配置為p e 以u(píng) m42 8 gc p u ，1 g b 內(nèi) 存，1 2 0 g bs a t a 硬盤(pán)，1 0 0 m 以太網(wǎng)接口。 針對(duì)上面的3 個(gè)評(píng)價(jià)指標(biāo)，在節(jié)點(diǎn)數(shù)目不同和節(jié)點(diǎn)出度后為5 的情況下，對(duì) p c p 算法和p l a 算法進(jìn)行了對(duì)比實(shí)驗(yàn)。 對(duì)于節(jié)點(diǎn)規(guī)模n ，分為小規(guī)模網(wǎng)絡(luò)、中等規(guī)模網(wǎng)絡(luò)、大規(guī)模網(wǎng)絡(luò)三種情況進(jìn)行實(shí) 驗(yàn)，節(jié)點(diǎn)規(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ī)模網(wǎng)絡(luò) ( 1 0 0 ，2 0 0 ，3 0 0 ，4 0 0 ，5 0 0 ，8 0 0 ，7 0 0 ，o中等規(guī)橫網(wǎng) ，9 0 0 ，1 0 0 0 ，絡(luò) 韃3 1 0 0 0 ，2 0 0 0 ，3 0 0 0 ，4 0 0 0 ，5 0 0 0 ，0 0 ，7犬覿模網(wǎng)絡(luò) 0 0 0 ，8 0 0 0 ，9 0 0 0 ，1 0 0 0 0 ) 表格3 。l 節(jié)點(diǎn)規(guī)模 測(cè)量指標(biāo)中，平均加入時(shí)間用a j 表示，備份鏈路延遲用b d 表示，加入控制負(fù)載 用j o 表示如表格3 。2 。 應(yīng)用層組播轉(zhuǎn)發(fā)樹(shù)重構(gòu)技術(shù)研究 溪黼黎鬟豢黧黧l 霧| | 瀵糍麟蘸麓闌黼 a j平均加入時(shí)問(wèn) b d備份鏈路延遲 j 0加入控制負(fù)載 表格3 2 測(cè)量指標(biāo) m t p 協(xié)議，m t p l 協(xié)議用p l 表示，m 邛2 協(xié)議用p 2 表示，如表格3 _ 3 。 表格3 - 3 m t p 協(xié)議 在實(shí)驗(yàn)中，髓n 1 郇t o 口l 就表示，出度為5 ，節(jié)點(diǎn)規(guī)模為小規(guī)模，采用m 仲l 協(xié) 議構(gòu)造的轉(zhuǎn)發(fā)樹(shù)上運(yùn)行r o t 算法得到的平均加入時(shí)間的值。 實(shí)驗(yàn)結(jié)果及其分析： 3 2 1 平均加入時(shí)間 圖3 - 4 平均加入時(shí)間_ n 1 鄭州大學(xué)碩士學(xué)位論文 圖3 _ 5 平均加入時(shí)間p 眩 圖3 6 平均加入時(shí)間予昭 從圖中可以看出，r o t 算法的平均加入時(shí)間總體上都大于p c p 算法的平均加入時(shí) 間，但是隨著節(jié)點(diǎn)規(guī)模的增加，基于m t p l 生成樹(shù)，r o t 算法與p c p 算法的差距增 大，而基于m r p 2 生成樹(shù)，r o t 算法與p c p 算法的差距較小。 結(jié)論： 1 、p c p 算法的平均加入時(shí)間優(yōu)于i 的t 算法； 2 、i t o t 算法與p c p 算法的差距，基于m t p l 樹(shù)相差較大，而基于m r p 2 樹(shù)相差 較小。 應(yīng)用層組播轉(zhuǎn)發(fā)樹(shù)重構(gòu)技術(shù)研究 3 2 2 備用鏈路延遲 圖3 7 備用鏈路延遲- n 1 圖3 8 備用鏈路延遲_ n 2 鄭州大學(xué)碩士學(xué)位論文 圖3 9 備用鏈路延遲- 量舊 從圖中不難看出，采用i t 算法的備用鏈路平均延遲均小于采用p c p 算法的結(jié) 果，這主要是因?yàn)樵趓 o t 算法中，主要是在節(jié)點(diǎn)的子樹(shù)中來(lái)構(gòu)造一棵新的轉(zhuǎn)發(fā)樹(shù)，這 些節(jié)點(diǎn)在物理上本身就相距較近；而在p c p 算法中，是在祖先節(jié)點(diǎn)的兄弟節(jié)點(diǎn)及其子 樹(shù)中尋找備用節(jié)點(diǎn)，因此，p c p 算法選擇的備用節(jié)點(diǎn)會(huì)比r o t 算法的備用節(jié)點(diǎn)的物理 距離要遠(yuǎn)一些，實(shí)驗(yàn)結(jié)果也說(shuō)明了這一點(diǎn)。 結(jié)論： 一般情況下，r o t 算法的備用鏈路平均延遲優(yōu)于p c p 算法；但是在大規(guī)模網(wǎng)絡(luò) 下，基于m r p 2 生成樹(shù)的p c p 算法優(yōu)于r o t 算法。 應(yīng)用層組播轉(zhuǎn)發(fā)樹(shù)重構(gòu)技術(shù)研究 3 2 3 加入控制負(fù)載 圖3 1 0 加入控制負(fù)載n 1 圖3 1 l 加入控制負(fù)載 鄭州大學(xué)碩士學(xué)位論文 圖3 1 2 加入控制負(fù)載n b 從圖中可以看出，無(wú)論節(jié)點(diǎn)規(guī)模如何增加，采用r o t 算法的控制負(fù)載總是略高于 p c p 算法。 結(jié)論：p c p 算法的加入控制負(fù)載優(yōu)于r o t 算法。 3 3 本章小結(jié) 通過(guò)前面的實(shí)驗(yàn)，可以得到兩種算法的比較結(jié)論。p c p 算法的平均加入時(shí)間和平均 加入負(fù)載優(yōu)于r o t 算法，但是備用節(jié)點(diǎn)鏈路平均延遲不如r o t 算法，這說(shuō)明p c p 算 法在尋找備用節(jié)點(diǎn)的開(kāi)銷(xiāo)方面小于r o t 算法，但是找到的備用節(jié)點(diǎn)的延遲特性不如 r o t 算法。相對(duì)而言，r o t 算法更適合于轉(zhuǎn)發(fā)樹(shù)結(jié)構(gòu)相對(duì)固定的應(yīng)用場(chǎng)合。 應(yīng)用層組播轉(zhuǎn)發(fā)樹(shù)重構(gòu)技術(shù)研究 第4 章基于p i a 算法的重構(gòu)解決方案 本章研究的重點(diǎn)是p l a 算法的實(shí)現(xiàn)和仿真實(shí)驗(yàn)分析。主要內(nèi)容為，首先是在p c p 算法的基礎(chǔ)上，針對(duì)p c p 算法的一些缺陷，提出并實(shí)現(xiàn)了p l a 算法。然后通過(guò)實(shí)驗(yàn)對(duì) p c p 、p l a 和r o t 算法進(jìn)行對(duì)比仿真實(shí)驗(yàn)，最后是實(shí)驗(yàn)結(jié)果分析。 4 1 具體算法： 該算法借鑒了r o t 算法和p c p 算法的思想，在p c p 算法的基礎(chǔ)上進(jìn)行了改進(jìn)。具 體思想： 1 采用了“鏈路預(yù)留”的思想進(jìn)行樹(shù)的重構(gòu) 2 節(jié)點(diǎn)為自己尋找備份鏈路 3 充分利用了預(yù)失效節(jié)點(diǎn)的父母節(jié)點(diǎn)的剩余出度 4 對(duì)節(jié)點(diǎn)間的連接開(kāi)銷(xiāo)進(jìn)行比較，優(yōu)先選擇延遲最低的建立連接 設(shè)對(duì)于節(jié)點(diǎn)f ，總出度為d ( f ) ，已經(jīng)使用的出度是吃( f ) ，未使用的出度為4 ( f ) ， 未使用的出度中，預(yù)留鏈路的出度為d 。( f ) ，則有： d ( f ) = 吒( f ) + 4 ( f ) + 以( f ) 4 1 1 算法描述： 設(shè)要選擇備用父母節(jié)點(diǎn)”的節(jié)點(diǎn)為甩，p 為指向某個(gè)節(jié)點(diǎn)的指針，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é)點(diǎn) 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 鄭州大學(xué)碩士學(xué)位論文 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預(yù)留鏈路 ( w m e p s i b l i i l 黔i sn u l l p 2 p _ p 嬲l(shuí) 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é)點(diǎn)加入到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 ) ) 應(yīng)用層組播轉(zhuǎn)發(fā)樹(shù)重構(gòu)技術(shù)研究 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) ，算法開(kāi)始，參數(shù)為節(jié)點(diǎn)玎，代表要計(jì)算的節(jié)點(diǎn) 行2 ，首先將指針指向”的父母節(jié)點(diǎn)p 行3 ，節(jié)點(diǎn)口計(jì)算最小延遲節(jié)點(diǎn)聊 行4 6 ，如果n = 聊，節(jié)點(diǎn)甩與p 的父母節(jié)點(diǎn)建立虛鏈路，算法結(jié)束 行7 - 8 ，如果p 的父母節(jié)點(diǎn)非根節(jié)點(diǎn)且有預(yù)留鏈路，則p 的父母節(jié)點(diǎn)就是要找的節(jié) 點(diǎn)，算法結(jié)束。 行9 ，如果非上述情況，則算法繼續(xù)。 行1 0 一1 6 ，如果p 有預(yù)留鏈路，則p 就是要找的節(jié)點(diǎn)，算法結(jié)束；如果p 沒(méi)有預(yù)留 鏈路，但是p 有兄弟節(jié)點(diǎn)，則循環(huán)結(jié)束：否則，繼續(xù)往上游走，如果一直沒(méi)有合適的節(jié) 點(diǎn)，會(huì)一直到達(dá)根節(jié)點(diǎn)，循環(huán)結(jié)束。 行1 7 1 9 ，如果一直找到根結(jié)點(diǎn)都找不到合適的p ，則結(jié)束尋找過(guò)程，返回o ； 行2 0 ，如果找到了合適的琺算法繼續(xù) 行2 1 。2 2 ，將p 的兄弟節(jié)點(diǎn)信息以及節(jié)點(diǎn)聊，寫(xiě)入一個(gè)集合b 中，集合b 中存放 著臨時(shí)候選節(jié)點(diǎn)的列表 行2