基于組播轉(zhuǎn)發(fā)狀態(tài)的聚合模型研究與算法分析.pdf

1、IP組播在IP網(wǎng)絡(luò)中實現(xiàn)了多點(diǎn)通信模型，促進(jìn)了視頻點(diǎn)播、音視頻會議和數(shù)據(jù)分發(fā)等多點(diǎn)通信業(yè)務(wù)在互聯(lián)網(wǎng)上的發(fā)展。同時，新興的IPv6技術(shù)更增強(qiáng)了對組播的支持；再加上組播技術(shù)相對于單播與廣播技術(shù)的巨大優(yōu)勢，組播技術(shù)的應(yīng)用越來越廣泛，網(wǎng)絡(luò)應(yīng)用的要求也越來越強(qiáng)烈，人們?nèi)找嬲J(rèn)識到組播技術(shù)所帶來的優(yōu)點(diǎn)與好處，其研究價值也越來越凸現(xiàn)出來。 組播采用樹型轉(zhuǎn)發(fā)結(jié)構(gòu)實現(xiàn)單點(diǎn)對多點(diǎn)通信的支持，每一個數(shù)據(jù)包只在分叉節(jié)點(diǎn)處被復(fù)制，每一條鏈路只轉(zhuǎn)發(fā)一次。這種

2、方法使得IP組播能有效的同時向多個組成員發(fā)送數(shù)據(jù)，并且能夠同時支持多個組播組。IP組播這種多點(diǎn)通信機(jī)制使之成為互聯(lián)網(wǎng)中視頻會議等高帶寬、共享性應(yīng)用的重要基礎(chǔ)。 然而，組播共享樹要求所有樹上節(jié)點(diǎn)處的路由器均保持每一個組的轉(zhuǎn)發(fā)狀態(tài)。因此，當(dāng)多個組播組并存時，IP組播遇到一系列問題：路由器的轉(zhuǎn)發(fā)狀態(tài)數(shù)會隨網(wǎng)絡(luò)中的組播組數(shù)量線性增長，不但增加了路由器額外的存儲和CPU處理開銷，而且導(dǎo)致了更加緩慢的轉(zhuǎn)發(fā)過程，當(dāng)組播會話數(shù)很多時，會耗費(fèi)大量

3、的資源和控制開銷來管理組播組，制約了組播會話的可擴(kuò)展性。也就是說，組播轉(zhuǎn)發(fā)狀態(tài)問題成為影響IP組播大規(guī)模擴(kuò)展應(yīng)用的一個瓶頸。 組播聚合模型是針對大規(guī)模組播擴(kuò)展性問題，結(jié)合當(dāng)前網(wǎng)絡(luò)拓?fù)涮攸c(diǎn)提出來的新思想，最早由UCLA網(wǎng)絡(luò)實驗室提出，并給出了基于該種模型的貪婪算法。其主要思想是：適當(dāng)犧牲帶寬，使能夠復(fù)合的組播組共享一棵組播分發(fā)樹，通過這種方式，網(wǎng)絡(luò)中組播樹的數(shù)目會大大減少，組播轉(zhuǎn)發(fā)狀態(tài)也隨之減少，最終提高了網(wǎng)絡(luò)性能。 本文

4、在對傳統(tǒng)組播聚合模型深入研究的基礎(chǔ)上，提出了優(yōu)化組播轉(zhuǎn)發(fā)狀態(tài)問題的兩個方案：基于疊加樹算法的優(yōu)化方案和基于遺傳模擬退火算法的優(yōu)化方案。 1.基于疊加樹的聚合算法借鑒了圖論中“相似”的概念，將符合特定QoS要求的原始組播樹進(jìn)行疊加合并，然后按照樹的定義對疊加樹進(jìn)行剪枝，去環(huán)等操作以獲取聚合樹集合。 仿真實驗表明，疊加樹算法在時間、聚合度及轉(zhuǎn)發(fā)狀態(tài)降低率方面均優(yōu)于傳統(tǒng)的貪婪聚合算法。 2.基于遺傳模擬算法的優(yōu)化方案中

5、，模擬退火算法在理論上，經(jīng)過足夠長的時間會收斂到全局最優(yōu)解；而遺傳思想強(qiáng)調(diào)的是兩代之間的進(jìn)化關(guān)系，但其交配有可能使最優(yōu)解遺失而陷入局部最優(yōu)解；由此，本文給出了遺傳模擬退火算法的設(shè)計方案。 組播聚合問題的數(shù)學(xué)本質(zhì)是最小集合覆蓋問題（MSCP），這是一個NPC問題。本文將遺傳模擬退火算法應(yīng)用到求解MSCP，進(jìn)而對組播聚合問題尋優(yōu)，最終獲得近似于全局最優(yōu)的準(zhǔn)最優(yōu)解。 仿真實驗通過與貪婪算法、拉格朗日松弛算法進(jìn)行比較來表明該算法