滿足時延及時延差別約束的組播路由問題研究.pdf

1、組播是一種點到多點的網絡數據傳播技術，在視頻點播、電視會議、網絡游戲等方面具有很好的應用價值。組播路由算法的目標是尋找一棵連接源節(jié)點和多個目的節(jié)點的組播樹，同時滿足各種服務質量需求。在實時交互性組播應用中，時延和時延差別等服務質量因素顯得尤為重要。為此，本文研究受時延和時延差別約束的組播路由問題。 本文首先研究時延約束下的組播路由問題。該問題的目標是創(chuàng)建一棵覆蓋源節(jié)點和目的節(jié)點的代價最小樹，且滿足端到端時延要求。這個問題被證明是

2、NP完全問題。我們在研究已有算法的基礎上，提出一個新的啟發(fā)式算法，稱為STBMR算法。該算法在構造滿足時延約束的組播樹過程中，先構造最小生成樹作為初始樹，然后以時延最小路徑代替樹中的時延越界路徑，直至樹的根節(jié)點到所有目的節(jié)點的路徑滿足時延要求。該算法簡單、易實現，與經典的KPP算法相比，有較小的算法復雜性，但性能稍差。實驗表明，STBMR算法構造的組播樹費用比KPP算法構造的約大4％，算法執(zhí)行時間比KPP算法約少54％。 然后，