基于優(yōu)先級的應(yīng)用層組播的分層結(jié)構(gòu)模型

摘要：在分層結(jié)構(gòu)的基礎(chǔ)上提出了一種基于優(yōu)先級的ALM管理模型PBHM。該模型以分層結(jié)構(gòu)為基礎(chǔ)，具有控制開銷小，高效、分布式的構(gòu)建，更好的擴(kuò)展性，以及無須任何底層拓?fù)湫畔⒌葍?yōu)點(diǎn)，且構(gòu)建了PRIORITY數(shù)學(xué)模型來確定每個組成員的優(yōu)先級。另外，通過仿真實(shí)驗測試了系統(tǒng)性能，驗證了相關(guān)結(jié)論。本模型能夠更好地對用戶進(jìn)行管理和提高應(yīng)用層組播的轉(zhuǎn)發(fā)效率。

關(guān)鍵詞：應(yīng)用層組播；優(yōu)先級；分層結(jié)構(gòu)；組播管理；效率

中圖分類號：TP309文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2008)05-1517-04

組播是一種同時發(fā)送數(shù)據(jù)到多個接收者的有效通信方式。應(yīng)用層組播ALM[1~3]是在端系統(tǒng)實(shí)現(xiàn)組播轉(zhuǎn)發(fā)的，端系統(tǒng)之間通過單播連接在應(yīng)用層建立一個虛擬的Overlay網(wǎng)絡(luò)，部分接收者收到數(shù)據(jù)后，通過單播連接轉(zhuǎn)發(fā)給其他接收者。ALM在文件分發(fā)、視頻點(diǎn)播、網(wǎng)絡(luò)直播、網(wǎng)絡(luò)會議等方面有著廣泛的應(yīng)用。ALM通過端系統(tǒng)之間的協(xié)作在端系統(tǒng)實(shí)現(xiàn)多播轉(zhuǎn)發(fā)，因此，不要求路由器必須支持組播，使得任何一個非組內(nèi)的客戶端主機(jī)只要通過適當(dāng)?shù)木W(wǎng)絡(luò)瀏覽器就可以瀏覽組內(nèi)的數(shù)據(jù)。另外，在ALM中數(shù)據(jù)是通過可信度不高的主機(jī)轉(zhuǎn)發(fā)的，所以應(yīng)用層組播的安全也非常重要。

在ALM的用戶管理方面，如果所有成員都在同一層，則每個成員都是對等的，當(dāng)有新成員加入或有成員離開時，要將申請信息發(fā)送給組內(nèi)的每個成員，這就增加了網(wǎng)絡(luò)負(fù)擔(dān)；而且在數(shù)據(jù)轉(zhuǎn)發(fā)過程中，每個成員都要首先解密，然后在轉(zhuǎn)發(fā)數(shù)據(jù)前再對數(shù)據(jù)加密，顯然增加了每個成員節(jié)點(diǎn)加/解密處理開銷；NICE[4，5]分層結(jié)果雖然具有較少的控制負(fù)荷，但當(dāng)leader節(jié)點(diǎn)失效后沒有對應(yīng)的處理方法，不能充分合理地利用連接資源，且高層節(jié)點(diǎn)的出度數(shù)較高。本文提出的基于優(yōu)先級的管理模型，對于每層中的分組，根據(jù)組內(nèi)成員的優(yōu)先級的高低，從分組中選舉出具有最高優(yōu)先級的組成員作為本組的leader，并使用合理的分層數(shù)，使得整個分層結(jié)構(gòu)達(dá)到優(yōu)化狀態(tài)。

1模型的設(shè)計

1．1體系結(jié)構(gòu) 

本模型中根據(jù)其角色的不同定義了三種執(zhí)行實(shí)體，即root、leader和組成員(group member，GM）。本模型的體系結(jié)構(gòu)如圖1所示。

Root是模型中具有最高優(yōu)先級的成員，位于分層結(jié)構(gòu)的最高層，是整個體系結(jié)構(gòu)的管理和控制中心。Root中保存著所有已接入的組成員的信息表以及惡意成員的黑名單，根據(jù)由下層發(fā)送的信息定期（每隔Δt時間）更新組成員信息表，負(fù)責(zé)新成員的認(rèn)證登錄控制并產(chǎn)生新成員初始化列表；root也負(fù)責(zé)管理成員加入和退出組。當(dāng)系統(tǒng)遭到巨大破壞，例如網(wǎng)絡(luò)中大量節(jié)點(diǎn)丟失，導(dǎo)致系統(tǒng)處于混亂狀態(tài)時，由root負(fù)責(zé)使系統(tǒng)恢復(fù)，讓系統(tǒng)始終處于平衡態(tài)。

Leader在本組內(nèi)具有最高優(yōu)先級，是每個分組的管理中心。為每個分組選擇leader，是為了確保一個新加入的組成員只要詢問很少的組成員就可以在分層結(jié)構(gòu)中找到適合自己的最佳位置。另外，layer(i)內(nèi)的所有分組的leader又是layer(i+1)的組成員。Leader中保存著本組所有成員的信息表，并根據(jù)本組內(nèi)所有成員的優(yōu)先級動態(tài)選舉出本組的leader；然后，將其管理的分組成員的信息及修改信息發(fā)送給root。

組成員是參與組播通信的客戶端，實(shí)現(xiàn)用戶組通信，并且保存著本組所有成員的信息表以及其leader所在的上一層的分組內(nèi)的所有成員的信息表。為了減輕root中心節(jié)點(diǎn)的負(fù)擔(dān)，每個組成員的優(yōu)先級由其自身根據(jù)PRIORITY數(shù)學(xué)模型計算再傳輸給其各自的leader。每個組成員不是同時計算自身的優(yōu)先級，而是從其加入系統(tǒng)后每隔Δt時間計算一次，并傳輸給其各自的leader。

1．2模型的基本思想

本模型是基于優(yōu)先級的分層管理模型，構(gòu)建PRIORITY數(shù)學(xué)模型來計算組成員的優(yōu)先級，對于可信任的組成員提高其優(yōu)先級；反之，降低其優(yōu)先級，并且當(dāng)優(yōu)先級降到零時，就將其列入root中保存的黑名單。根據(jù)每個分組內(nèi)所有成員的優(yōu)先級，動態(tài)地從分組中選舉出具有最高優(yōu)先級的組成員作為本組的leader。在本模型中，root是整個系統(tǒng)的管理中心，負(fù)責(zé)系統(tǒng)的統(tǒng)籌管理，并保存所有已接入的組成員的信息表。低層分組的組成員由其各自的leader來管理。Leader中保存本組所有成員的信息表。

1．3PRIORITY數(shù)學(xué)模型

在PRIORITY數(shù)學(xué)模型中，Num代表組成員移動的頻率，定義為Δt時間內(nèi)組成員移動的次數(shù)；Sour代表組成員已經(jīng)包含的文件資源占總資源的百分比；Priority(Num， Sour，ρ，Δt )代表組成員的優(yōu)先級。設(shè)L_G(i， j，k)表示該組成員是第i層的第j分組的第k個成員；設(shè)N(i， j)表示第i層的第j分組的組成員數(shù)目；t(rT0)表示第k個抽樣時刻，T0為抽樣間隔，r=1，2，3，4，5，…，Δt/T0。

當(dāng)有新成員申請加入，經(jīng)root認(rèn)證批準(zhǔn)后，產(chǎn)生該新成員的初始化列表。初始化列表的結(jié)構(gòu)如表1所示。Root保存初始化列表，然后Root啟動成員加入進(jìn)程，將以自己為leader的分組內(nèi)的成員的信息反饋給該新成員，該成員向下逐層詢問直到找到適合自己的最佳的分組L_G(i， j)。當(dāng)該組成員在其最佳位置加入分組后，該組成員定期（每隔Δt時間）主動向其leader發(fā)送自身的信息。穩(wěn)定狀態(tài)時，每個分組的leader通過heart－beat信息定期檢查本組成員的優(yōu)先級， 根據(jù)接收的組成員的更新信息動態(tài)地選舉出本組中優(yōu)先級最高的成員作為該分組的新leader。判斷分組是否需要更換leader，如果不更換，則原leader的狀態(tài)保持不變；如果更換，則該分組的原leader設(shè)置作為新leader的組成員的信息表中的“l(fā)eader=1，activity++”，然后，原leader將更新信息通知其在上一層的分組的leader以及本組的所有組成員。原leader在其上一層的分組的leader設(shè)置原leader信息表中的“l(fā)eader=0，activity--”。 

如果在一個分組中存在多個組成員都具有最高優(yōu)先級且相同，則選擇其中activity最大的組成員作為新leader；如果新選舉出的leader不愿作為leader，則該組成員通知原leader， 原leader設(shè)置該組成員信息表中的“activity--”，并從剩余的分組成員中再次進(jìn)行選舉，直到選舉成功。

1．5成員的管理

1）成員加入此時向發(fā)送root申請請求信息，root將收到的申請信息與自己保存的組成員信息表對照，判斷發(fā)出申請的成員身份是：a）(Sour=0，Num=0）從未加入過的全新成員；b)（Sour≠0，Num≠0）從一個分組轉(zhuǎn)移到另一個分組的成員；c)黑名單中的成員(Hostile=1)。其中：L_G(i， j，k)表示該組成員是第i層的第j分組的第k個成員。

當(dāng)Cont=0，Number=0時，root對新成員認(rèn)證后，產(chǎn)生其初始化列表，并將以自己為leader的分組內(nèi)的成員信息反饋給該新成員；然后，該成員向下逐層詢問直到找到適合自己的最佳的分組L_G(i， j)，分組L_G(i， j)的leader將該新成員的信息發(fā)送給自己所在的第i+1層的分組以及本分組的所有成員后，分組L_G(i， j)的leader所在的第i+1層的分組以及本分組的所有成員將該自己的信息發(fā)送給新成員，所有涉及到的組成員都保存更新信息。

當(dāng)Sour≠0，Num≠0時，設(shè)該組成員由分組L_G(i， j)轉(zhuǎn)移到分組L_G(m，n)。首先，當(dāng)分組L_G(i， j)的leader根據(jù)heart－beat算法檢測到組成員L_G(i， j，p)離開多播組時，則該leader設(shè)置自己保存的組成員L_G(i， j，p)信息表中的 Num++，再根據(jù)Priority(Num， Sour，ρ，Δt )公式計算降低該組成員的優(yōu)先級，修改離開組成員的信息表中的Priority；然后，分組L_G(i， j)的leader將該組成員的信息發(fā)送給自己所在的第i+1層的分組以及本分組的所有成員，并依次通知到root，分組L_G(i， j)的leader刪除保存的該組成員信息。如果修改后的Priority<0，則root拒絕該成員的加入申請，并設(shè)置其信息表中的Hostile=1。

當(dāng)Hostile=1時，如果root首次收到在黑名單中的成員的加入申請，則拒絕讓其加入，設(shè)置該組成員信息表中的Num++；如果root再次收到該成員的加入申請，則允許其加入，設(shè)置其信息表中的Num++，并根據(jù)Priority(Num， Sour，ρ，Δt )公式計算降低該組成員的優(yōu)先級，修改其信息表中的Priority。

對于以上對成員申請加入的處理，如果新成員加入分組后，使得分組的規(guī)模過大（超過3k-1，其中：k是一常數(shù)），則原分組根據(jù)一定的標(biāo)準(zhǔn)進(jìn)行分裂，新產(chǎn)生的分組的leader由原分組的leader負(fù)責(zé)選舉產(chǎn)生，并且原分組的leader還要將分裂信息及新產(chǎn)生分組的leader的信息發(fā)送給自己所在的第i+1層的分組以及本分組的所有成員，并依次通知到root。如果分裂后，分組的規(guī)模仍過大，則繼續(xù)分裂，直到分組的規(guī)模適當(dāng)時為止。

2）成員離開設(shè)離開的組成員位于L_G(i， j)分組，組成員可能正常離開或異常離開。正常離開時，組成員向其leader發(fā)送退出申請，經(jīng)該leader轉(zhuǎn)發(fā)給root；異常離開時，采用heart－beat算法，如果leader沒有收到該組成員的響應(yīng)信息，則leader就通知自己所在的第i+1層的分組以及本分組的所有成員，并依次通知到root該組成員已離開。根據(jù)組成員在分組中的角色不同，可分為leader成員（leader=1）和非leader成員（leader=0）。

leader=0時，當(dāng)分組L_G(i， j)的leader檢測到組成員L_G(i， j， p)離開多播組時，則該leader設(shè)置自己保存的組成員L_G(i， j，p)信息表中的Num++，分組L_G(i， j)的leader根據(jù)Priority(Num， Sour，ρ，Δt )公式計算降低該組成員的優(yōu)先級。如果修改后Priority≤0，則設(shè)置該組成員信息表中的Hostile=1；然后啟動計時器，并將該信息告知root。如果一段時間T后，root仍沒有收到該組成員的加入申請，則root和所有保存著該組成員信息表的成員將刪除該組成員的信息表；如果收到該組成員的加入申請，則root設(shè)置自己保存的組成員L_G(i， j，p)信息表中的Num++，并根據(jù)Priority(Num， Sour，ρ，Δt )公式計算降低該組成員的優(yōu)先級，然后，root將其看做新成員加入作出相應(yīng)的處理。如果一個分組L_G(i， j)的組成員全部離開，那么本分組就退化為一個組成員節(jié)點(diǎn)，則該分組的leader所在的第i+1層的分組的leader設(shè)置分組L_G(i， j)的leader成員的信息表中的leader=0，并將其作為組成員加入到其他分組，但并不修改其優(yōu)先級。

當(dāng)leader=1時，leader成員失效后，就必須為該分組重新選擇leader，設(shè)分組L_G(i， j)的leader失效。如果分組L_G(i， j）的組成員先檢測到其leader失效，就向其leader所在的第i+1層的分組的leader發(fā)送重新選擇分組leader的請求，該第i+1層的分組的leader收到請求后，就啟動重新選擇分組leader的進(jìn)程。如果該失效leader成員位于第i+1層的分組的leader先檢測到該leader成員失效，則第i+1層的分組的leader就直接啟動重新選擇分組leader的進(jìn)程，遍歷分組L_G(i， j）所有組成員的信息表，從中選擇優(yōu)先級最高的組成員作為分組L_G(i， j）的新leader，設(shè)置作為新leader的組成員的信息表中的leader=1，activity++，并將新leader的信息發(fā)送給分組L_G(i， j)內(nèi)的所有組成員。該過程只是分組的新leader替換了原leader的位置，而整體的分層結(jié)構(gòu)并不變化。除了為分組選擇新leader外，該第i+1層的分組的leader也要對該離開的leader成員作像非leader成員離開時一樣的處理。

對于以上兩種情況，無論是leader成員還是非leader成員失效，當(dāng)組成員離開后，如果一個分組L_G(i， j）的規(guī)模過小，即小于常數(shù)k時，則該分組的leader就啟動分組合并進(jìn)程。分組L_G(i， j）的leader向其所屬的第i+1層的分組內(nèi)的兄弟成員L_G(i+!，m，n）發(fā)送分組合并請求信息cluster－merge－request；組成員L_G(i+!，m，n）收到請求信息后，檢驗如果允許分組合并，產(chǎn)生的新分組的規(guī)模是否過大。如果新分組的規(guī)模符合要求，則分組合并成功，分組L_G(i， j）的leader成員從第i+1層退出，并且分組L_G(i， j）的所有組成員都加入到以第i+1層的分組內(nèi)的組成員L_G(i+!，m，n）為leader的新分組；如果新分組的規(guī)模過大，則分組L_G(i， j）的leader繼續(xù)向其所屬的第i+1層的分組內(nèi)的其他兄弟成員發(fā)送分組合并請求信息cluster－merge－request，直到分組合并成功。

2仿真及結(jié)果分析

本文對本模型中的數(shù)據(jù)傳輸機(jī)制進(jìn)行了仿真模擬，建立了一個軟件環(huán)境來模擬PBHM，在一臺Linux主機(jī)上搭建了仿真平臺，由GT－ITM[6~8]拓?fù)洚a(chǎn)生器生成250個節(jié)點(diǎn)，隨機(jī)選擇組播成員，且組播成員的數(shù)目在20~160變化，所有組成員在仿真時間0~300 s隨機(jī)加入。當(dāng)拓?fù)浣Y(jié)構(gòu)穩(wěn)定后，隨機(jī)地選擇一個主機(jī)作為數(shù)據(jù)源產(chǎn)生數(shù)據(jù)分組。每次仿真結(jié)果都是在分層結(jié)構(gòu)穩(wěn)定后測量的，且每個仿真結(jié)果都是五次仿真的平均值。

圖4顯示了PBHM與NICE協(xié)議控制開銷的對比。用控制分組在分組發(fā)送或接收的所有分組中所占的比值來衡量控制開銷。PBHM的控制開銷比NICE的稍大些，是因為PBHM中引入了組成員的優(yōu)先級控制，root為每個新加入的組成員產(chǎn)生初始化列表；root和各個分組的leader還要根據(jù)每個組成員的轉(zhuǎn)移次數(shù)和該成員所包含的資源量計算組成員的優(yōu)先級，并且組成員的變動信息要在各個分組的leader與root之間進(jìn)行交互。PBHM的控制開銷有所增加，這是增加系統(tǒng)的穩(wěn)定性以及提供其轉(zhuǎn)發(fā)效率所作的犧牲。

考慮分組失效或離開對PBHM和NICE性能的影響時，仿真設(shè)定多播數(shù)據(jù)源以50 pakets/ms的恒定速率產(chǎn)生10 000個數(shù)據(jù)分組，40個分組同時突然地離開多播組，且分組在數(shù)據(jù)源發(fā)送15％的數(shù)據(jù)分組后突然離開；在仿真結(jié)束時，計算剩下的組成員的平均數(shù)據(jù)傳輸率。圖5顯示了PBHM與NICE平均數(shù)據(jù)傳輸率的對比情況。當(dāng)組成員數(shù)目相對較少時（如60～80個組成員），PBHM的平均數(shù)據(jù)傳輸率與NICE的相差不大，但是，當(dāng)組成員數(shù)目繼續(xù)增加時，PBHM的性能明顯地優(yōu)于NICE的性能。這是因為在NICE結(jié)構(gòu)中，節(jié)點(diǎn)的入度數(shù)和出度數(shù)都比較高，當(dāng)一個組成員失效或離開時，導(dǎo)致大量的組成員暫時地脫離數(shù)據(jù)傳輸路徑而接收不到數(shù)據(jù)；特別是當(dāng)組成員很多時，數(shù)據(jù)丟失比較嚴(yán)重，使得數(shù)據(jù)傳輸率下降，并且高層的組成員失效或離開，將會嚴(yán)重影響剩下的組成員恢復(fù)數(shù)據(jù)傳輸路徑的快慢。

3結(jié)束語

本文在分層結(jié)構(gòu)的基礎(chǔ)上提出了基于優(yōu)先級的ALM管理模型PBHM，介紹了計算組成員優(yōu)先級的PRIORITY數(shù)學(xué)模型，并詳細(xì)論述了本模型對成員加入和離開分組的處理。通過仿真試驗可知，該模型改善了僅僅對分組進(jìn)行分層管理的性能，具有更好的擴(kuò)展性和穩(wěn)定性；而且能夠充分合理地利用連接資源，其關(guān)鍵是引入了組成員優(yōu)先級為每個分組選擇lea-der，減少了處理時間，提高了數(shù)據(jù)的傳輸率，優(yōu)化了網(wǎng)絡(luò)的性能。給每個組成員確定優(yōu)先級，使分組選擇leader時更加合理化，即使leader頻繁失效，網(wǎng)絡(luò)也能快速收斂。

參考文獻(xiàn)：

［1］CHU Yang－h(huán)ua，RAO S G，SESHAN S，et al.A case for end system multicast[J].Proc of ACM SIGMETRICS，2002，20(8):1456－1471.

[2]PENDARAKIS D，SHI S，VERMA D，et al.ALMI:an application level multicast infrastructure[C]//Proc of the 3rd Usenix Symp on Internet Technologies and Sys.San Francisco，CA:IEEE Press，2001:49-60.

[3]YIU W P K，CHAN S H G.SOT:secure overlay tree for application layer multicast[C]//Proc of Communicationson IEEE International Conference.New Jersey:IEEE，2004:1451－1455.

[4]BANERJEE S，BHATTACHARJEE B，KOMMAREDDY C.Scalable application layer multicast[C]//Proc of ACM SIGCOMM.New York:ACM Press，2002：205-217.

[5]TRAN D A，HUA K A，DO Tai.ZIGZAG:an efficient peer－to－peer scheme for media streaming[C]//Proc of IEEE INFOCOM.New York:IEEE，2003:1283－1292.

[6]SOBEIH A，YURCIK W，HOU J C.VRing:a case for building application layer multicast rings[C]//Proc of IEEE(MASCOTS’04).Washington DC:IEEE Computer Society，2004:437-446.

[7]TIAN Rui－xiong，ZHANG Qian，XIANG Zhe，et al.Robust and efficient path diversity in application layer multicast for video streaming[J].IEEE Transactions in Circuits and Systems for Video Technology，2005，15（8）:961-972.

[8]ZHU Yan，SHU Wei，WU Min－you.Approaches to establishing multicast overlays[C]//Proc of IEEE International Conference on Services Computing.Washington DC:IEEE Computer Society，2005:268-269.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”