時延受限低代價的組播路由算法研究.pdf

1、隨著網(wǎng)絡(luò)技術(shù)的發(fā)展及其滲透力加強(qiáng)，人們對計算機(jī)網(wǎng)絡(luò)的期望越來越高，越來越多。為滿足人們這些不同的需求，為推動網(wǎng)絡(luò)技術(shù)的發(fā)展，網(wǎng)絡(luò)全方位市場化勢在必行。網(wǎng)絡(luò)市場化要求網(wǎng)絡(luò)具備QoS能力，這和網(wǎng)絡(luò)“盡力而為”的初衷相矛盾。因此計算機(jī)網(wǎng)絡(luò)QoS的實(shí)現(xiàn)需要大量的科學(xué)家及網(wǎng)絡(luò)的研究者們不懈的努力。 計算機(jī)網(wǎng)絡(luò)的拓?fù)浜托畔R聚（集成）給網(wǎng)絡(luò)研究提出新的挑戰(zhàn)。眾多匯聚信息，多媒體信息是研究者們關(guān)注的焦點(diǎn)。多媒體信息傳輸中，除傳統(tǒng)的需求外，還有

2、異質(zhì)性需求，如：根據(jù)不同的費(fèi)用提供不同服務(wù)，不同的資源提供不同服務(wù)（物盡其用）。異質(zhì)性是組播路由研究者們的新的目標(biāo)。 網(wǎng)絡(luò)QoS問題的研究推動網(wǎng)絡(luò)市場化，具有重要的實(shí)用價值；同時，因?yàn)榫W(wǎng)絡(luò)的QoS的復(fù)雜性、挑戰(zhàn)性，其相關(guān)問題的解決也會帶來一定的理論價值。 在計算機(jī)網(wǎng)絡(luò)中，組播路由是目前研究較多、應(yīng)用較廣泛的連接方式。組播是指單個信源節(jié)點(diǎn)將信息通過組播樹傳送到多個信宿（但非網(wǎng)絡(luò)中的所有節(jié)點(diǎn)），它是點(diǎn)到點(diǎn)通信與廣播通信的擴(kuò)展

3、。 本文主要研究QoS組播路由相關(guān)的問題，取得了以下成果： 1）分析、比較了幾種典型的集中及分布式組播路由算法，凝煉出組播路由算法研究的一般方法，給出了組播路由算法研究的動態(tài)。 2）研究了Steiner樹問題，詳細(xì)討論了構(gòu)造Steiner樹的幾種算法，并分析了各種算法的計算時間復(fù)雜度、最壞情況下的性能比以及它們在不同網(wǎng)絡(luò)中建立組播樹的效率，抽象出構(gòu)造Steiner樹的基本思想。 3）采用Waxman模型，