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

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

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

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

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