時(shí)延受限低代價(jià)的組播路由算法研究.pdf

1、隨著網(wǎng)絡(luò)技術(shù)的發(fā)展及其滲透力加強(qiáng)，人們對(duì)計(jì)算機(jī)網(wǎng)絡(luò)的期望越來(lái)越高，越來(lái)越多。為滿足人們這些不同的需求，為推動(dòng)網(wǎng)絡(luò)技術(shù)的發(fā)展，網(wǎng)絡(luò)全方位市場(chǎng)化勢(shì)在必行。網(wǎng)絡(luò)市場(chǎng)化要求網(wǎng)絡(luò)具備QoS能力，這和網(wǎng)絡(luò)“盡力而為”的初衷相矛盾。因此計(jì)算機(jī)網(wǎng)絡(luò)QoS的實(shí)現(xiàn)需要大量的科學(xué)家及網(wǎng)絡(luò)的研究者們不懈的努力。 計(jì)算機(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èn)題的研究推動(dòng)網(wǎng)絡(luò)市場(chǎng)化，具有重要的實(shí)用價(jià)值；同時(shí)，因?yàn)榫W(wǎng)絡(luò)的QoS的復(fù)雜性、挑戰(zhàn)性，其相關(guān)問(wèn)題的解決也會(huì)帶來(lái)一定的理論價(jià)值。 在計(jì)算機(jī)網(wǎng)絡(luò)中，組播路由是目前研究較多、應(yīng)用較廣泛的連接方式。組播是指單個(gè)信源節(jié)點(diǎn)將信息通過(guò)組播樹(shù)傳送到多個(gè)信宿（但非網(wǎng)絡(luò)中的所有節(jié)點(diǎn)），它是點(diǎn)到點(diǎn)通信與廣播通信的擴(kuò)展

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