聚合組播算法研究.pdf

1、近年來(lái)，隨著在Internet上流媒體、視頻點(diǎn)播等業(yè)務(wù)的相繼開(kāi)展，IP組播技術(shù)得到了快速的發(fā)展。組播是一種有效的支持多點(diǎn)通信的機(jī)制，它采用樹(shù)轉(zhuǎn)發(fā)結(jié)構(gòu)，每一個(gè)數(shù)據(jù)包只在節(jié)點(diǎn)處被復(fù)制，在每一條鏈路上只發(fā)送一次。這種方法使IP組播能有效的同時(shí)向組成員發(fā)送數(shù)據(jù)，并支持大量的組播組。IP組播是Internet上流媒體、視頻會(huì)議等高帶寬、共享型應(yīng)用的重要基礎(chǔ)。 然而，一棵組播分布樹(shù)要求所有樹(shù)節(jié)點(diǎn)保持每一個(gè)組的轉(zhuǎn)發(fā)狀態(tài)，因此，當(dāng)多個(gè)組播組并存

2、于網(wǎng)絡(luò)當(dāng)中的時(shí)候，IP組播遇到一系列問(wèn)題：隨著組播組個(gè)數(shù)的增加，組播轉(zhuǎn)發(fā)狀態(tài)增多，組播樹(shù)上路由器的內(nèi)存需求隨之增大；同時(shí)，由于每個(gè)數(shù)據(jù)包的轉(zhuǎn)發(fā)需要進(jìn)行地址查找，進(jìn)行組播轉(zhuǎn)發(fā)查詢的CPU開(kāi)銷也隨之增大，轉(zhuǎn)發(fā)過(guò)程也會(huì)變慢。當(dāng)網(wǎng)絡(luò)中的組播會(huì)話數(shù)很大時(shí)，需要大量的資源和控制開(kāi)銷來(lái)管理組播組。組播轉(zhuǎn)發(fā)狀態(tài)數(shù)是制約網(wǎng)絡(luò)中大規(guī)模組播應(yīng)用可擴(kuò)展性的瓶頸。 聚合組播技術(shù)就是針對(duì)大規(guī)模組播可擴(kuò)展性問(wèn)題、結(jié)合真實(shí)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特點(diǎn)提出來(lái)的。其主要思想是

3、適當(dāng)放寬對(duì)節(jié)約帶寬的要求，使能夠復(fù)合的組播組共享一棵組播分發(fā)樹(shù)。樹(shù)節(jié)點(diǎn)上保持的是這棵樹(shù)的狀態(tài)，而不是每一個(gè)組播組的狀態(tài)，這樣大大減少了組播轉(zhuǎn)發(fā)的狀態(tài)數(shù)，提高了網(wǎng)絡(luò)性能。聚合組播問(wèn)題的關(guān)鍵在于如何找到數(shù)目最小的組播樹(shù)，使之覆蓋所有的組播組。它的數(shù)學(xué)本質(zhì)是最小集合覆蓋問(wèn)題，是一個(gè)NP-C問(wèn)題。傳統(tǒng)的解決聚合組播的方法是貪婪算法。貪婪算法有一定的局限性，它每一次都選擇當(dāng)前情況下的最優(yōu)解，很容易陷入局部最優(yōu)解，所以得到全局最優(yōu)解的可能性很小，最

4、終的聚合效果并不理想。 針對(duì)于這個(gè)問(wèn)題，本文提出了拉格朗日松弛算法、遺傳算法和免疫算法來(lái)選擇聚合組播樹(shù)。 拉格朗日松弛的基本思想是，把造成問(wèn)題難的約束條件吸收到目標(biāo)函數(shù)中，并使得目標(biāo)函數(shù)仍保持線性，使得問(wèn)題容易求解。在傳統(tǒng)的拉格朗日松弛算法的基礎(chǔ)上，算法能夠動(dòng)態(tài)調(diào)整拉格朗日乘子，使找到的解盡量接近于全局最優(yōu)解。 遺傳算法是一類借鑒生物界“自然選擇、適者生存”機(jī)制的智能搜索算法。在生物進(jìn)化過(guò)程中，適應(yīng)性好的個(gè)體生存