基于拉格朗日松弛法的受限低代價(jià)組播路由算法.pdf

1、目前Internet中現(xiàn)有的傳輸模式仍為單一的盡力而為(best-effort)型服務(wù)，無(wú)法滿足飛速發(fā)展的多媒體應(yīng)用和用戶對(duì)網(wǎng)絡(luò)傳輸質(zhì)量的更高要求。在這種情況下，以提高網(wǎng)絡(luò)資源的利用率、為用戶提供更高服務(wù)質(zhì)量為目標(biāo)的QoS控制技術(shù)應(yīng)運(yùn)而生，QoS組播路由技術(shù)則是網(wǎng)絡(luò)多媒體信息傳輸?shù)年P(guān)鍵技術(shù)之一。 組播是將單一的數(shù)據(jù)拷貝從源節(jié)點(diǎn)傳送到多個(gè)目的節(jié)點(diǎn)的網(wǎng)絡(luò)通信方式。實(shí)現(xiàn)組播通信的方法一般是建立網(wǎng)絡(luò)的組播樹，而QoS組播路由算法就是建立

2、一棵性能良好的滿足服務(wù)質(zhì)量要求的組播樹。因此，建立性能良好的組播樹的QoS組播路由算法就成了本文研究的重點(diǎn)。 本文首先分析了組播技術(shù)的基礎(chǔ)理論，隨后介紹了拉格朗日松弛算法的基本原理。通過對(duì)現(xiàn)有的幾種典型的受QoS限制的組播路由算法分析后，指出了它們存在的不足，并提出了一種基于拉格朗日松弛法的受限低代價(jià)組播路由算法LR-DLMR。該算法具有以下主要特點(diǎn)： (1)算法并未對(duì)原網(wǎng)絡(luò)拓?fù)鋱D創(chuàng)建封閉圖，從而有效利用了鏈路中間節(jié)點(diǎn)信

3、息，也避免了封閉圖對(duì)原圖的多播不可達(dá)的問題； (2)算法具有比較強(qiáng)的擴(kuò)展性，為了便于和其它延遲受限的組播路由算法進(jìn)行性能對(duì)比，算法僅將延遲限制條件吸收到線性函數(shù)中進(jìn)行拉格朗日松弛，同樣對(duì)于帶寬，丟包率等限制條件也可以吸收到線性函數(shù)中進(jìn)行求解； (3)算法的效率取決于所采用的最小代價(jià)組播樹生成算法，這點(diǎn)保證了該算法具有長(zhǎng)遠(yuǎn)的生命力，只要有新的更優(yōu)的最小代價(jià)組播樹生成算法的誕生，就可以套用到該算法中進(jìn)一步求解滿足延遲限制條件

4、的組播樹； (4)算法具有可調(diào)節(jié)性，可以根據(jù)用戶需求給算法設(shè)定松弛次數(shù)，要求在限定的次數(shù)內(nèi)返回一棵組播樹；也可以設(shè)定一個(gè)大于零的誤差參數(shù)ε，要求在前后求得組播樹代價(jià)差值只要小于該參數(shù)，算法就返回一棵組播樹。 通過嚴(yán)格的理論分析，對(duì)LR-DLMR算法的正確性進(jìn)行了證明，并且推理出算法的最壞時(shí)間復(fù)雜度僅為O(P(M+3/2)n<'2>-pm<'2>n)，n為網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)，m為目的節(jié)點(diǎn)數(shù)，p為松弛次數(shù)。最后，本文通過仿真實(shí)驗(yàn)的