高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)教學(xué)教材

高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)2024/9/261史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)內(nèi)容提要6.1概述6.2IP多播協(xié)議6.3多播路由6.4擴(kuò)散技術(shù)6.5跨越樹(shù)的多播路由算法6.6

約束Steiner樹(shù)6.7反向路徑廣播6.8截?cái)嗟姆聪蚵窂綇V播6.9反向路徑多播

2024/9/262史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)內(nèi)容提要6.10核心樹(shù)6.11路由多播選擇算法KMB6.12動(dòng)態(tài)多播路由選擇算法VTDM

6.13限界最短多播算法BSMA6.14適用于光纖網(wǎng)絡(luò)的多播的MZQ算法

6.15多播的應(yīng)用

2024/9/263史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)6.1概述將分組同時(shí)發(fā)往所有目的地稱(chēng)做廣播（broadcasting）。

單源，多目的的通信方式稱(chēng)之為多點(diǎn)通信（multipointcommunication），通常只在分叉的時(shí)候復(fù)制信息，又稱(chēng)為多播（multicast）。在單播的環(huán)境下，每個(gè)結(jié)點(diǎn)一次只能給另一個(gè)結(jié)點(diǎn)發(fā)出信息。在多播的環(huán)境下，每個(gè)結(jié)點(diǎn)一次可以有效的把一個(gè)打包的信息同時(shí)發(fā)往多個(gè)目標(biāo)。必須有支持IP多播的結(jié)點(diǎn)處理系統(tǒng)和TCP/IP棧，網(wǎng)絡(luò)中的結(jié)點(diǎn)才能順利的進(jìn)行多播。2024/9/264史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)6.1概述2024/9/266史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)6.1概述2024/9/267史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)6.2IP多播協(xié)議80年代開(kāi)始研究，1988年Stanford大學(xué)實(shí)施了第一次多目通話，1992年Internet程特別小組（IETF）定義和發(fā)布了一個(gè)多播的網(wǎng)絡(luò)標(biāo)準(zhǔn)，用于建立多播主干網(wǎng)（MBONE），即在Internet上運(yùn)行的單路廣播和多播綜合網(wǎng)絡(luò)。MBONE于1993年剎那間名聲遠(yuǎn)揚(yáng)。1995年，Cisco公司和Lucent公司開(kāi)始銷(xiāo)售支持多播的路由器和交換機(jī)，一年后依賴(lài)多播的應(yīng)用產(chǎn)品開(kāi)始上市。IP多播的最早實(shí)施方案依賴(lài)于傳統(tǒng)的竭盡全力方法和UserDatagranProtoco1，但它們不能保證多播數(shù)據(jù)流的可靠傳輸。2024/9/268史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)6.2IP多播協(xié)議

HP的Internet群管JF協(xié)議（LGMP）

ProtocolIndependentMu1ticast、

Mu1ticastBorderGatewayProtocol

HierarchicalDVMRP（DistanceVectorMulticastRoutingProtocol）2024/9/269史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)6.3多播路由共享樹(shù)（sharedtree）源根結(jié)點(diǎn)的最短路徑樹(shù)（SRSPT：sourcerootedshortestpathtree）。2024/9/2610史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)共享樹(shù)（sharedtree）共享樹(shù)方法中使用一個(gè)中央多播路由器，有時(shí)候又稱(chēng)為核心路由器。需要進(jìn)行多播的源結(jié)點(diǎn)將他們所要傳遞的信息包都傳給這個(gè)核心路由器，然后由這個(gè)核心路由器通過(guò)一棵共享樹(shù)將信息包一個(gè)一個(gè)的傳給組中的每一個(gè)接收結(jié)點(diǎn)。每個(gè)組中只要建立一棵共享樹(shù)就可以了，而不是象在SRSPT中需要為組中的每個(gè)源結(jié)點(diǎn)建立一棵樹(shù)。與SRSPT算法相比，共享樹(shù)對(duì)路由器和網(wǎng)絡(luò)帶寬（bandwidth）的需求更小。在CBT和PIM協(xié)議中使用共享樹(shù)的思想來(lái)傳遞信息包。2024/9/2611史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)源根結(jié)點(diǎn)的最短路徑樹(shù)這種源根結(jié)點(diǎn)的最短路徑樹(shù)只能建立在具有多播功能的路由器上。它為每個(gè)組中的每個(gè)源結(jié)點(diǎn)建立一棵樹(shù)，這棵樹(shù)以該傳送結(jié)點(diǎn)為根，使其與所有的接收結(jié)點(diǎn)相連。一般而言，該組中有多少個(gè)源結(jié)點(diǎn)，就需建立多少棵這樣的樹(shù)。一棵這種基于源結(jié)點(diǎn)的樹(shù)將一個(gè)特定的源結(jié)點(diǎn)與所有的接收結(jié)點(diǎn)相連，并被稱(chēng)為“源根結(jié)點(diǎn)的最短路徑樹(shù)”。這些路徑并不需要通過(guò)一個(gè)特定的中央多播路由器。等到由協(xié)議將一棵這樣的樹(shù)建成后，這棵樹(shù)的源結(jié)點(diǎn)就可以沿著這棵樹(shù)上的路徑將所要傳遞的信息傳到它的每一個(gè)接收結(jié)點(diǎn)。2024/9/2612史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)SRSPT樹(shù)的優(yōu)點(diǎn)

（1）使用經(jīng)典的單信道路由表很容易計(jì)算SRSPT樹(shù)；（2）可以有效的實(shí)現(xiàn)分布式處理不需要整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)；（3）返回的路徑中不會(huì)存在回路。

2024/9/2613史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)SRSPT樹(shù)的缺點(diǎn)（1）沒(méi)有最小化整個(gè)分布式處理的代價(jià)；（2）可伸縮性不好；

（3）在每個(gè)路由器上都要保存每個(gè)組中每個(gè)源結(jié)點(diǎn)的SRSPT樹(shù)的信息；（4）如果下層的單信道路由是非對(duì)稱(chēng)的則可能會(huì)導(dǎo)致失敗。2024/9/2614史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)性能指標(biāo)(1)低延遲。將源結(jié)點(diǎn)到目的結(jié)點(diǎn)的端到端的延遲與點(diǎn)到點(diǎn)的單信道最短路徑的延遲相比較；

（2）低代價(jià)。全部的帶寬消耗以及保存樹(shù)狀態(tài)信息所需的代價(jià)；

（3）輕的網(wǎng)絡(luò)擁塞2024/9/2615史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)多點(diǎn)路由算法的需求（1）支持可靠的傳輸。連接失敗不應(yīng)該增加延遲或者減少可用的資源（2）對(duì)于得到最佳路由所需要的一些考慮。1：所需付出的代價(jià)（對(duì)帶寬的消耗）2：端到端的延遲（所需跨越的結(jié)點(diǎn)數(shù)）（3）最小化對(duì)網(wǎng)絡(luò)的負(fù)擔(dān)。1：避免回路2：避免在一些連接或子網(wǎng)上出現(xiàn)網(wǎng)絡(luò)擁塞

（4）最小化在路由器中所需存儲(chǔ)的狀態(tài)數(shù)量。2024/9/2616史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)密集模式密集模式假設(shè)多播組的成員密集分布在網(wǎng)絡(luò)中，每個(gè)子網(wǎng)至少含一個(gè)成員。密集模式還需要充足的帶寬。DVMRP,MOSPF和PIM-DM都是密集模式路由選擇協(xié)議。密集模式路由選擇協(xié)議依靠擴(kuò)散（flooding）技術(shù)把信息傳播到整個(gè)網(wǎng)絡(luò)的路由器上。2024/9/2617史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)稀疏模式假設(shè)多播組的成員稀疏分布在網(wǎng)絡(luò)中，而且網(wǎng)絡(luò)可以提供的帶寬不是很寬裕。在稀疏模式下，用戶(hù)可能分散在Intent的各個(gè)部分，也可能是被ISDN專(zhuān)線連接起來(lái)的。這種模式下用戶(hù)不一定很少，只是它們分散的范圍很廣。2024/9/2618史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)6.4擴(kuò)散技術(shù)1．路由器接收到要發(fā)往多播組的一個(gè)報(bào)文。2．路由器用協(xié)議機(jī)制決定這是不是第一次收到該報(bào)文。3．如果它是第一次收到該報(bào)文，路由器將該報(bào)文發(fā)往Internet上除了它的來(lái)源的所有接口。這保證了多播報(bào)文將到達(dá)所有的路由器。

．如果路由器以前曾收到該報(bào)文，就把它丟棄。2024/9/2619史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)擴(kuò)散技術(shù)局限性1．?dāng)U散技術(shù)不適用于大規(guī)模網(wǎng)絡(luò)，如Internet。2．同樣不適用于廣域網(wǎng)，因?yàn)樗a(chǎn)生大量復(fù)制包。3．?dāng)U散技術(shù)使用Internet網(wǎng)上的所有可用路徑，網(wǎng)絡(luò)上所有路徑的流量容易引起擁塞。4．因?yàn)槊總€(gè)路由器必須為最近接收的包維護(hù)一張表，所以并不是很有效的使用路由器的內(nèi)存。2024/9/2620史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)建立生成樹(shù)的步驟

1．選擇一轉(zhuǎn)送設(shè)備作為根：剛開(kāi)始所有的轉(zhuǎn)送設(shè)備先假設(shè)自身為根，告訴其他設(shè)備它作為根連接?？偟膩?lái)說(shuō)，優(yōu)先級(jí)低的設(shè)備設(shè)為根。如果優(yōu)先級(jí)相同，MAC地址低的設(shè)備設(shè)為根。2．估計(jì)路徑成本：如果一轉(zhuǎn)送設(shè)備接到另一設(shè)備的包，認(rèn)為存在更好的路徑，就不再告訴別的設(shè)備自身是根，而是告訴別的設(shè)備更優(yōu)的根。3．選擇根端口，并且在每個(gè)局域網(wǎng)制定一個(gè)轉(zhuǎn)送設(shè)備：最終，每個(gè)設(shè)備都認(rèn)同了最佳轉(zhuǎn)送設(shè)備，該設(shè)備就成為根。設(shè)備的根端口提供了指向根轉(zhuǎn)送設(shè)備的最低成本路徑。路徑成本相同時(shí)，端口接頭優(yōu)先級(jí)低的成為根端口。如果接口優(yōu)先級(jí)再相同，具低優(yōu)先級(jí)的設(shè)備上的斷口為根端口。4.每個(gè)子網(wǎng)指定一個(gè)端口（路由器）：生成樹(shù)算法設(shè)指定連接轉(zhuǎn)送設(shè)備和局域網(wǎng)的端口位置頂端口。尤其當(dāng)子網(wǎng)上的設(shè)備靠近根時(shí)。2024/9/2621史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)建立生成樹(shù)的步驟2024/9/2622史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)建立生成樹(shù)的步驟2024/9/2623史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)6.7反向路徑廣播無(wú)論是子網(wǎng)上哪一個(gè)源，反向路徑廣播（reversepathbroadcasting,RPB）算法針對(duì)每一個(gè)組建立一棵生成樹(shù)，提供了源和組的成員之間的有效路徑。這樣的生成樹(shù)根植于直接和源連接的子網(wǎng)上，意味著每個(gè)活躍的源-組隊(duì)都有一棵生成樹(shù)。路由器利用逆向路徑廣播算法建立根植于源的樹(shù)2024/9/2624史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)反向路徑廣播轉(zhuǎn)送算法2024/9/2625史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)反向路徑廣播轉(zhuǎn)送算法鏈接狀態(tài)路由選擇協(xié)議使用拓?fù)鋽?shù)據(jù)庫(kù)來(lái)確認(rèn)相鄰的路由器是否在子鏈接上，也就是考慮該路由器是否在相鄰路由器回溯到源的最短路徑上。距離向量路由選擇協(xié)議使用鄰居發(fā)布的源-組對(duì)的前一站距，或者翻轉(zhuǎn)該路由來(lái)決定下一相鄰路由認(rèn)為該路由在到源的最短路徑上。2024/9/2626史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)反向路徑廣播的例子2024/9/2627史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)反向路徑廣播的例子

?

從路由器A收到報(bào)文，確認(rèn)連接1是源-組對(duì)的父母鏈。

?把報(bào)文發(fā)往任何含有小組成員的葉子子網(wǎng)，如發(fā)往連接4、連接5。

?從路由選擇信息交換中得知路由器C認(rèn)為連接2是源-組對(duì)的父母鏈，于是不再將報(bào)文發(fā)往連接3。?路由器C將丟棄從連接3來(lái)的報(bào)文，因?yàn)槭菑脑?組對(duì)的非父母鏈上來(lái)的。2024/9/2628史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)6.8截?cái)嗟姆聪蚵窂綇V播

截?cái)嗟姆聪蚵窂綇V播（truncatedreversepathbroadcasting,TRPB）改進(jìn)了上一個(gè)算法中不考慮多播組的成員限制的問(wèn)題。它使用了IGMP來(lái)決定某個(gè)子網(wǎng)上是否存在該廣播組的成員，并以此為依據(jù)截?cái)嘣瓉?lái)構(gòu)造的跨越樹(shù)上的一些枝葉。一旦弄清楚這一點(diǎn)，TRPB不再往不含組成員的葉子網(wǎng)上發(fā)送報(bào)文。路由器從擴(kuò)展傳送樹(shù)上剪除不含組成員的葉子網(wǎng)，這一排除不在最短路徑上的接口的過(guò)程稱(chēng)為“截?cái)唷薄?024/9/2629史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)截?cái)嗟姆聪蚵窂綇V播算法的例子2024/9/2630史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)TRPB源通過(guò)父路由器連接入路由器，多播組的成員第一組用G1表示、第二組G2、第三組G3與路由器下屬的轉(zhuǎn)送裝置相連。

當(dāng)路由器接收了源-G1對(duì)的一多播報(bào)文，它將：

因?yàn)榻涌?至少含有第一組的一個(gè)成員，路由器把報(bào)文發(fā)往接口2。?

當(dāng)且僅當(dāng)該路由器的一個(gè)下屬路由器認(rèn)為接口3是它的源-G1對(duì)的父母鏈的一部分，該路由器才把報(bào)文發(fā)往接口3。?

接口4沒(méi)有目標(biāo)組的成員，報(bào)文不發(fā)往接口4。

TRPB雖然避免了葉子網(wǎng)中的不必要的流量，但是在建立分配樹(shù)的枝干的時(shí)候沒(méi)有考慮是否含組成員的問(wèn)題。

2024/9/2631史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)6.9反向路徑多播反向路徑多播（reversepathmulticasting,RPM）是對(duì)于RPB和TRPB的改進(jìn)。具體而言，如果一個(gè)接收接口可以用于向多播報(bào)文的源發(fā)送單信道廣播報(bào)文，路由器向除了接收接口以外的所有接口發(fā)送多播報(bào)文。換句話說(shuō)，RPM建立的傳送樹(shù)只覆蓋了廣播組成員和到含廣播組成員子網(wǎng)最短路徑沿途徑過(guò)的路由器和子網(wǎng)。RPM截?cái)嗔烁灿谠吹纳蓸?shù)，路由選擇協(xié)議只向通往目標(biāo)組成員的枝干發(fā)送報(bào)文。2024/9/2632史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)RPM2024/9/2633史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)工作原理上級(jí)路由器收到截?cái)嘈畔⒑髢?chǔ)存起來(lái)。如果從所有的子鏈?zhǔn)盏浇財(cái)嘈畔?，該路由器也往它的上?jí)路由器發(fā)送截?cái)嘈畔?。這個(gè)過(guò)程產(chǎn)生的多播樹(shù)只含有通向活躍組成員的枝干。協(xié)議不時(shí)的更新多播樹(shù)，更新后每個(gè)路由器清除內(nèi)存中的所有剪除信息，并且將受到的下一個(gè)多播報(bào)文送往所有的子鏈。這樣又重新開(kāi)始了定義多播樹(shù)的新一輪過(guò)程。2024/9/2634史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)工作原理組成員的動(dòng)態(tài)特征意味著樹(shù)需要定期的更新。也就是說(shuō)，多播報(bào)文必須定期的發(fā)往Internet網(wǎng)絡(luò)中的每個(gè)路由器。這就使得在大規(guī)模傳送服務(wù)如在Internet上的傳送問(wèn)題不容忽視，而且，每個(gè)路由器必須保留關(guān)于源和組的所有狀態(tài)信息。盡管這對(duì)于小網(wǎng)絡(luò)來(lái)說(shuō)不構(gòu)成威脅，但是當(dāng)源的數(shù)目和多播組成員大幅增加時(shí)就是一個(gè)嚴(yán)重的問(wèn)題。2024/9/2635史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)6.10核心樹(shù)核心樹(shù)（core-basedtree,CBT）算法將建立一棵被小組中所有的發(fā)送者和接收者共享的傳送樹(shù)(圖6.10)，而不是為每一個(gè)源-組對(duì)建立一棵樹(shù)。使用CBT算法時(shí)，無(wú)論報(bào)文是從那個(gè)源發(fā)出的，路由器將多信道信息沿著相同的傳送樹(shù)來(lái)傳遞。共享樹(shù)途徑最顯著的優(yōu)勢(shì)是能夠很好的適應(yīng)大規(guī)模網(wǎng)絡(luò)。然而，CBT可能導(dǎo)致在核心路由器附近的流量集中和瓶頸問(wèn)題。這是因?yàn)閺娜我庠唇Y(jié)點(diǎn)發(fā)出的信息在接近核心時(shí)，都沿著相同的連接。2024/9/2636史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)CBT2024/9/2637史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)設(shè)計(jì)目的(1)CBT是用于大規(guī)模網(wǎng)絡(luò)，處理過(guò)程中只需要少量的內(nèi)存和帶寬資源。因?yàn)镃BT不針對(duì)于源，尤其適合于多發(fā)送者的應(yīng)用程序。(2)CBT時(shí)健壯的多播路由選擇算法。為了獲得健壯的多播傳送樹(shù)，核心將放置在最佳位置。(3)和其他多播路由選擇協(xié)議比較而言，CBT協(xié)議比較簡(jiǎn)單。簡(jiǎn)單性能導(dǎo)致性能的提高。(4)CBT路由選擇算法適度利于協(xié)議的。任何地方都可以安裝，并且支持域間多信道路由選擇。CBT與CBMRP有著良好的協(xié)同工作的機(jī)制，CBMRP是一種能夠普遍連接不同種類(lèi)的多播域的協(xié)議。2024/9/2638史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)當(dāng)一主機(jī)成為多播組的成員將執(zhí)行以下步驟

(1)主機(jī)向所有連接廣播一IGMP主機(jī)成員報(bào)告。(2)附近的一個(gè)具CBT算法的路由器喚醒加入樹(shù)的過(guò)程：?產(chǎn)生JOIN_REQUEST信息?將信息發(fā)往沿著導(dǎo)向組的核心路由器的路徑的下一個(gè)站點(diǎn)。(3)核心路由或發(fā)送路由和核心路由之間的另一路由器確認(rèn)該信息。2024/9/2639史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)當(dāng)一主機(jī)成為多播組的成員將執(zhí)行以下步驟

(4)請(qǐng)求加入的信息在它穿過(guò)的路由器暫時(shí)建立加入狀態(tài)，包括組、進(jìn)入的接口和連出的接口。所有中間路由器處理加入請(qǐng)求：?確認(rèn)加入請(qǐng)求是從那個(gè)接口接收的。?告知信加入的主機(jī)CBT傳送樹(shù)。(5)臨時(shí)狀態(tài)如果沒(méi)有接到從上游傳來(lái)的確認(rèn)信息，將最終超時(shí)。因?yàn)橛信R時(shí)加入狀態(tài)，加入確認(rèn)可以沿著加入請(qǐng)求來(lái)的路徑返回。(6)一旦加入確認(rèn)到達(dá)產(chǎn)生加入請(qǐng)求的路由器，發(fā)向這個(gè)組的信息將同時(shí)發(fā)往這個(gè)新的接收者。

2024/9/2640史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)CBT

(4)請(qǐng)求加入的信息在它穿過(guò)的路由器暫時(shí)建立加入狀態(tài)，包括組、進(jìn)入的接口和連出的接口。所有中間路由器處理加入請(qǐng)求：?確認(rèn)加入請(qǐng)求是從那個(gè)接口接收的。?告知信加入的主機(jī)CBT傳送樹(shù)。(5)臨時(shí)狀態(tài)如果沒(méi)有接到從上游傳來(lái)的確認(rèn)信息，將最終超時(shí)。因?yàn)橛信R時(shí)加入狀態(tài)，加入確認(rèn)可以沿著加入請(qǐng)求來(lái)的路徑返回。(6)一旦加入確認(rèn)到達(dá)產(chǎn)生加入請(qǐng)求的路由器，發(fā)向這個(gè)組的信息將同時(shí)發(fā)往這個(gè)新的接收者。

2024/9/2641史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)6.11路由多播選擇算法KMB理想化的多播路由選擇算法應(yīng)該是：

構(gòu)建樹(shù)時(shí)具有所想要的成本和延遲特征。

算法可以適用于廣播組的成員增加的情況（如CBT），而不是每次成員增加都需要更新（如SMT）。

維護(hù)原始路由的特性。

不干擾正在進(jìn)行的數(shù)據(jù)傳送。

是由接收者驅(qū)動(dòng)的。

2024/9/2642史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)問(wèn)題的形式化定義給定圖G=(V,E,c)V=頂點(diǎn)集E=邊集c=成本函數(shù)c:E

Z0+(邊

非負(fù)整數(shù))Z-頂點(diǎn)集:終結(jié)集合(有時(shí)用M表示)S-點(diǎn)集:非終結(jié)集合TO:初始樹(shù)={s}.Q:樹(shù)上頂點(diǎn)的優(yōu)先級(jí)隊(duì)列Vt:樹(shù)上頂點(diǎn)At:樹(shù)上邊

2024/9/2643史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)Dijkstra最短路徑算法

Begin.

v

V,將v加到集合U,Distance(v)=cost(s,v)Distance(s)=0;從U中刪除s.whileU不為空do具有最小距離的任何G的成員v.U=U-{v}.For每個(gè)v的近鄰w,doifmember(w,U)distance(w)=min(distance(w),cost(w,v)+distance(v)); Stop.2024/9/2644史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)Matsuyama最短成本路徑啟發(fā)式算法

BeginT1: 包含任選的i∈Z的G的子樹(shù).

k=1; Zk={i}.找到離Tk

最近的i

Z-Zk

在Tk

的基礎(chǔ)上加入從Tk

到I的最短路徑建樹(shù)Tk+1 k=k+1.Ifk<p,轉(zhuǎn)T1.Ifk=p,輸出結(jié)論Tp

Stop.

2024/9/2645史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)KMB算法

輸入：圖G和頂點(diǎn)集Z輸出：Steiner樹(shù)Th步驟：1．由G和Z建立完全有向帶權(quán)圖G1=（V1，E1，c1）。2．找到G1的最小生成樹(shù)。3．用G中相應(yīng)的最短路徑替換T1中的一邊，建立G的子圖Gs。4．找到Gs的最小生成樹(shù)Ts。5.如必要的話刪去Ts中的邊，構(gòu)建Steiner樹(shù)Th，使得Th中所有的葉子為Steiner點(diǎn)。2024/9/2646史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)KMB算法KMB算法最壞時(shí)間復(fù)雜度

O（|S||V|2）。成本不大于2（1-1/l）×最優(yōu)成本，其中l(wèi)=Steiner樹(shù)的葉結(jié)點(diǎn)數(shù)。2024/9/2647史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)KMB算法的工作過(guò)程2024/9/2648史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)KMB算法的工作過(guò)程2024/9/2649史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)成本建模

W(e,

i):邊e上波長(zhǎng)為

i的成本。如果邊e上

i值不確定w值為無(wú)窮。cv(

p,

q):v結(jié)點(diǎn)上波長(zhǎng)從

p變?yōu)?/p>

q的代價(jià)。如果v結(jié)點(diǎn)上波長(zhǎng)不能從

p變?yōu)?/p>

qcv值為無(wú)窮。Ifp=q,cv(

p,

q)=0。C(T)=

v

Tw(p(v),v),

(v))+

v

T-{s}Cp(v)(

(p(v)),

(v))，其中p(v)是樹(shù)中v點(diǎn)的父母。2024/9/2650史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)虛主干虛主干是基本圖中的一棵樹(shù)，用作建立多播樹(shù)的模板，也就是說(shuō)，擴(kuò)展為虛主干的結(jié)點(diǎn)具有最大可能性變?yōu)槎嗖?shù)中的一部分。如果一個(gè)結(jié)點(diǎn)有越多的路徑穿過(guò)它，就有越大的可能成為多播樹(shù)的一部分。定義點(diǎn)vi

的權(quán)重W(vi)=穿越vi的最短路徑的數(shù)目，以權(quán)重作為是否吸收一個(gè)結(jié)點(diǎn)為虛主干的重要標(biāo)準(zhǔn)2024/9/2651史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)建立虛主干的步驟

（1）找到圖

G中所有結(jié)點(diǎn)對(duì)的最短路徑。（2）給圖

G中的所有結(jié)點(diǎn)賦權(quán)值。（3）找到主干結(jié)點(diǎn)集合F。（4）為主干結(jié)點(diǎn)集合建立完全圖。（5）在完全圖上找到最小生成樹(shù)。（6）把最小生成樹(shù)上的邊轉(zhuǎn)化為圖G上相應(yīng)的最短路徑。（7）執(zhí)行最小生成樹(shù)算法，去除不必要的結(jié)點(diǎn)和連接，獲得虛主干。2024/9/2652史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)VTDM路由選擇算法

1.

建立虛主干。

2.

往多播組中加入一結(jié)點(diǎn)：建立該結(jié)點(diǎn)到已建立的虛主干之間的最短路由。

虛主干到源的路由已經(jīng)建立起來(lái)了。把結(jié)點(diǎn)加入多播組。

3.從多播組中去除一結(jié)點(diǎn)：先從多播組中移出該結(jié)點(diǎn)。如果是葉子結(jié)點(diǎn)，從多播樹(shù)中去掉該葉子。如果該結(jié)點(diǎn)沒(méi)有下屬結(jié)點(diǎn)，剪除多余的枝干。2024/9/2653史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)增加結(jié)點(diǎn)(加入結(jié)點(diǎn)

B)第一步:

如果結(jié)點(diǎn)B在虛主干上，指定它為結(jié)點(diǎn)A，轉(zhuǎn)到第二步。否則找到B到虛主干的最短路由，把最短路由中不屬于多播樹(shù)的那部分加入多播樹(shù)中。設(shè)虛主干上沿最短路徑離B最近的點(diǎn)為A。

第二步:

如果A已經(jīng)在多播樹(shù)上，轉(zhuǎn)到第三步。否則，把從A到源結(jié)點(diǎn)的路由不在多播樹(shù)上的那部分加入多播樹(shù)中。第三步:

把結(jié)點(diǎn)B加入多播樹(shù)中。2024/9/2654史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)模擬結(jié)果

定義平均失效率=使用算法A的樹(shù)成本/使用算法B的樹(shù)成本。將VTDM與動(dòng)態(tài)貪心法(DG)，

最短路徑法(SP)比較。對(duì)于結(jié)點(diǎn)數(shù)增加的平均失效率，VTDM大大優(yōu)于SP，

優(yōu)于DG。對(duì)于多播組的規(guī)模增大的平均失效率，VTDM在大規(guī)模組中大大優(yōu)于SP，

優(yōu)于DG。對(duì)于多播樹(shù)中結(jié)點(diǎn)的最大度(也就是數(shù)據(jù)復(fù)制的份數(shù))，VTDM大大小于

SP，小于DG。2024/9/2655史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)6.13限界最短多播算法BSMA

BSMA算法使多播樹(shù)的成本最小化，并且保證所有的延遲小于預(yù)先設(shè)定的界限。BSMA的可行領(lǐng)域是所有延遲受限的Steiner樹(shù)。先簡(jiǎn)要的描述一下BSMA的步驟：首先用Dijkstra最短路徑算法構(gòu)建最小延遲Steiner樹(shù)T0，在可行的區(qū)域內(nèi)不斷的重復(fù)更新T0以獲的更低的代價(jià)。2024/9/2656史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)BSMA成本函數(shù)的定義

使用驅(qū)動(dòng)成本 沿路徑的連接成本的總和最小化。擁塞驅(qū)動(dòng)成本 沿路徑的最大連接成本最小化。連接成本函數(shù) 將連接的成本和連接的使用聯(lián)系起來(lái)。連接延遲函數(shù) 連接上排隊(duì)、傳輸、散播的延遲。目標(biāo)延遲限界函數(shù)(DDF)

從源到每個(gè)目的站點(diǎn)沿途的延遲的上界。2024/9/2657史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)優(yōu)化Steiner樹(shù)的方法

用Dijkstra最短路徑算法構(gòu)建最小延遲Steiner樹(shù)T0的方法在前面已經(jīng)介紹過(guò)了。怎樣在可行的區(qū)域內(nèi)不斷的優(yōu)化T0，使最后獲得的樹(shù)的成本最小呢。這里要用到路徑交換法，優(yōu)化Tj獲得Tj+1步驟如下：

從Tj中選擇路徑p

Tj=Tj1+Tj2

p

從圖G中選取不在Tj中的新路徑ps替代從Tj中刪除的路徑。

Tj+1=Tj1+Tj2

ps.Tj+1

滿足延遲受限。2024/9/2658史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)超邊

首先從

Tj

獲得

Tj/，樹(shù)Tj/

含源結(jié)點(diǎn)，所有的目標(biāo)結(jié)點(diǎn)和所有度大于2的中繼結(jié)點(diǎn)。Tj/

的邊稱(chēng)為超邊，在超邊的兩個(gè)端結(jié)點(diǎn)之間的所有結(jié)點(diǎn)，都是度為2的轉(zhuǎn)送結(jié)點(diǎn)。每條超邊都是

Tj中交換的候選路徑2024/9/2659史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)BSMA具體算法

初始化所有超邊為無(wú)標(biāo)記。第一步:在所有無(wú)標(biāo)記邊中，BSMA選中最高成本的超邊Ph。將Ph

和另一條成本低一些的超邊交換，得到的樹(shù)延遲受限。以下兩種情況必有一種發(fā)生：

1.延遲限界的最短路徑與Ph相同。標(biāo)記超邊，轉(zhuǎn)第一步。

2.延遲限界的最短路徑不同于Ph.

替換

刪除所有的超邊的記號(hào)。

轉(zhuǎn)到第一步。當(dāng)所有超邊都被標(biāo)記后算法停止。2024/9/2660史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)BSMA動(dòng)態(tài)遞增

BSMA動(dòng)態(tài)遞增的計(jì)算子樹(shù)Tj1

和Tj2之間的k條最短路徑。當(dāng)構(gòu)成延遲限界樹(shù)的最短路徑找到后決定K，以下兩個(gè)條件滿足的時(shí)候，最短路徑遞增構(gòu)建停止：1.

新發(fā)現(xiàn)的最短路徑和剛刪除的等長(zhǎng)。2.

新發(fā)現(xiàn)的最短路徑使新樹(shù)不超過(guò)延遲限界。擴(kuò)展的Dijkstra算法用于構(gòu)建兩子樹(shù)間的最短路徑，而不是兩點(diǎn)之間的最短路徑。在Tj1中，一個(gè)偽源結(jié)點(diǎn)s與所有結(jié)點(diǎn)相連。在Tj2中，一個(gè)偽目標(biāo)d所有結(jié)點(diǎn)相連。最短路徑算法始于s終止于d。2024/9/2661史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)貪心路徑交換

增益=進(jìn)行了一輪路徑交換以后所減少的成本。

c=Tj

的成本，c_prime=Tj+1的成本，增益=c-c_prime。

BSMATj