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

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

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

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

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

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