高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)課件

高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)2023/10/121史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)內(nèi)容提要概述IP

多播協(xié)議多播路由擴(kuò)散技術(shù)跨越樹(shù)的多播路由算法約束Steiner

樹(shù)反向路徑廣播截?cái)嗟姆聪蚵窂綇V播反向路徑多播2023/10/122史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)內(nèi)容提要核心樹(shù)路由多播選擇算法KMB動(dòng)態(tài)多播路由選擇算法VTDM限界最短多播算法BSMA適用于光纖網(wǎng)絡(luò)的多播的MZQ算法多播的應(yīng)用2023/10/123史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)6.1

概述將分組同時(shí)發(fā)往所有目的地稱做廣播（broadcasting）。單源，多目的的通信方式稱之為多點(diǎn)通信（

multipointcommunication），通常只在分叉的時(shí)候復(fù)制信息，又稱為多播（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)行多播。2023/10/234史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)6.1

概述多信道IP包和單信道IP包的主要在于頭部目標(biāo)地址域的“組地址”，多播使用D類地址，也就是在244.0.0.0-239.255.255.255之間的地址。多播的特性：可靠性：對(duì)不同類型的應(yīng)用是否有不同的可靠性模型？允許動(dòng)態(tài)加入和離開(kāi)：每個(gè)對(duì)話過(guò)程必須是接受者可控制的。地址：在每層上如何對(duì)各組編址在IP層以上的各層是否需要標(biāo)識(shí)組，如果需要，怎樣標(biāo)識(shí)？方向性：一對(duì)多 或者 多對(duì)多轉(zhuǎn)送者是否是接受者的一個(gè)子集？2023/10/235史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)6.1

概述2023/10/236史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)6.1

概述2023/10/237史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)6.2

IP

多播協(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)始銷售支持多播的路由器和交換機(jī)，一年后依賴多播的應(yīng)用產(chǎn)品開(kāi)始上市。IP

多播的最 實(shí)施方案依賴于傳統(tǒng)的竭盡全力方法和UserDatagran

Protoco1，但它們不能保證多播數(shù)據(jù)流的可靠傳輸。2023/10/238史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)6.2

IP

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

Independent

Mu1ticast、Mu1ticast

Border

Gateway

ProtocolHierarchical DVMRP（

Distance

Vector

MulticastRouting

Protocol）2023/10/239史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)6.3多播路由共享樹(shù)（shared

tree）2023/10/2310史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)源根結(jié)點(diǎn)的最短路徑樹(shù)（SRSPT：

source

rooteshortest

path tree）。共享樹(shù)（shared

tree）共享樹(shù)方法中使用一個(gè)中央多播路由器，有時(shí)候又稱為核心路由器。需要進(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)傳遞信息包。2023/10/2311史忠植高級(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)相連，并被稱為“源根結(jié)點(diǎn)的最短路徑樹(shù)”。這些路徑并不需要通過(guò)一個(gè)特定的中央多播路由器。等到由協(xié)議將一棵這樣的樹(shù)建成后，這棵樹(shù)的源結(jié)點(diǎn)就可以沿著這棵樹(shù)上的路徑將所要傳遞的信息傳到它的每一個(gè)接收結(jié)點(diǎn)。2023/10/2312史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)SRSPT樹(shù)的優(yōu)點(diǎn)使用經(jīng)典的單信道路由表很容易計(jì)算SRSPT樹(shù)；可以有效的實(shí)現(xiàn)分布式處理不需要整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)；返回的路徑中不會(huì)存在回路。2023/10/2313史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)SRSPT樹(shù)的缺點(diǎn)沒(méi)有最小化整個(gè)分布式處理的代價(jià)；可伸縮性不好；（3）在每個(gè)路由器上都要保存每個(gè)組中每個(gè)源結(jié)點(diǎn)的SRSPT樹(shù)的信息；（

4

）如果下層的單信道路由是非對(duì)稱的則可能會(huì)導(dǎo)致失敗。2023/10/2314史忠植高級(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ò)擁塞2023/10/2315史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)多點(diǎn)路由算法的需求（

1

）支持可靠的傳輸。連接失敗不應(yīng)該增加延遲或者減少可用的資源對(duì)于得到最佳路由所需要的一些考慮。1：所需付出的代價(jià)（對(duì)帶寬的消耗）2：端到端的延遲（所需跨越的結(jié)點(diǎn)數(shù)）最小化對(duì)網(wǎng)絡(luò)的負(fù)擔(dān)。1：避免回路2：避免在一些連接或子網(wǎng)上出現(xiàn)網(wǎng)絡(luò)擁塞最小化在路由器中所需存儲(chǔ)的狀態(tài)數(shù)量。2023/10/2316史忠植高級(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ò)的路由器上。2023/10/2317史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)稀疏模式假設(shè)多播組的成員稀疏分布在網(wǎng)絡(luò)中，而且網(wǎng)絡(luò)可以提供的帶寬不是很寬裕。在稀疏模式下，用戶可能分散在Intent的各個(gè)部分，也可能是被ISDN專線連接起來(lái)的。這種模式下用戶不一定很少，只是它們分散的范圍很廣。2023/10/2318史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)6.4

擴(kuò)散技術(shù)．路由器接收到要發(fā)往多播組的一個(gè)報(bào)文。．路由器用協(xié)議機(jī)制決定這是不是第一次收到該報(bào)文。．如果它是第一次收到該報(bào)文，路由器將該報(bào)文發(fā)往Internet上除了它的來(lái)源的所有接口。這保證了多播報(bào)文將到達(dá)所有的路由器。．如果路由器以前曾收到該報(bào)文，就把它丟棄。2023/10/2319史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)擴(kuò)散技術(shù)局限性擴(kuò)散技術(shù)不適用于大規(guī)模網(wǎng)絡(luò)，如Internet。同樣不適用于廣域網(wǎng)，因?yàn)樗a(chǎn)生大量復(fù)制包。擴(kuò)散技術(shù)使用Internet網(wǎng)上的所有可用路徑，網(wǎng)絡(luò)上所有路徑的流量容易引起擁塞。因?yàn)槊總€(gè)路由器必須為最近接收的包維護(hù)一張表，所以并不是很有效的使用路由器的內(nèi)存。2023/10/2320史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)建立生成樹(shù)的步驟．選擇一轉(zhuǎn)送設(shè)備作為根：剛開(kāi)始所有的轉(zhuǎn)送設(shè)備先假設(shè)自身為根，告訴其他設(shè)備它作為根連接?？偟膩?lái)說(shuō)，優(yōu)先級(jí)低的設(shè)備設(shè)為根。如果優(yōu)先級(jí)相同，MAC地址低的設(shè)備設(shè)為根。．估計(jì)路徑成本：如果一轉(zhuǎn)送設(shè)備接到另一設(shè)備的包，認(rèn)為存在更好的路徑，就不再告訴別的設(shè)備自身是根，而是告訴別的設(shè)備更優(yōu)的根。．選擇根端口，并且在每個(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í)。2023/10/2321史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)建立生成樹(shù)的步驟2023/10/2322史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)建立生成樹(shù)的步驟2023/10/2323史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)6.7

反向路徑廣播無(wú)論是子網(wǎng)上哪一個(gè)源，反向路徑廣播（

reverse

pathbroadcasting, RPB）算法針對(duì)每一個(gè)組建立一棵生成樹(shù)，提供了源和組的成員之間的有效路徑。這樣的生成樹(shù)根植于直接和源連接的子網(wǎng)上，意味著每個(gè)活躍的源-組隊(duì)都有一棵生成樹(shù)。路由器利用逆向路徑廣播算法建立根植于源的樹(shù)2023/10/2324史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)反向路徑廣播轉(zhuǎn)送算法2023/10/2325史忠植高級(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)為該路由在到源的最短路徑上。2023/10/2326史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)反向路徑廣播的例子2023/10/2327史忠植高級(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)的。2023/10/2328史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)6.8

截?cái)嗟姆聪蚵窂綇V播截?cái)嗟姆聪蚵窂綇V播（

truncated

reversepath

broadcasting,

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ò)程稱為“截?cái)唷薄?023/10/2329史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)截?cái)嗟姆聪蚵窂綇V播算法的例子2023/10/2330史忠植高級(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)題。2023/10/2331史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)6.9

反向路徑多播反向路徑多播（

reverse

pathmulticasting,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)文202。3/10/23史忠植

高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)

32RPM2023/10/2333史忠植高級(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ò)程。2023/10/2334史忠植高級(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)題。2023/10/2335史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)6.10

核心樹(shù)核心樹(shù)（core-based

tree,

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í)，都沿著相同的連接。2023/10/2336史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)CBT2023/10/2337史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)設(shè)計(jì)目的CBT是用于大規(guī)模網(wǎng)絡(luò)，處理過(guò)程中只需要少量的內(nèi)存和帶寬資源。因?yàn)镃BT不針對(duì)于源，尤其適合于多發(fā)送者的應(yīng)用程序。CBT時(shí)健壯的多播路由選擇算法。為了獲得健壯的多播傳送樹(shù)，核心將放置在最佳位置。和其他多播路由選擇協(xié)議比較而言，CBT協(xié)議比較簡(jiǎn)單。簡(jiǎn)單性能導(dǎo)致性能的提高。CBT路由選擇算法適度利于協(xié)議的。任何地方都可以安裝，并且支持域間多信道路由選擇。CBT與CBMRP有著良好的協(xié)同工作的機(jī)制，CBMRP是一種能夠普遍20連23/1接0/2不338同種類的多史播忠植域高的級(jí)計(jì)協(xié)算機(jī)議網(wǎng)絡(luò)。當(dāng)一主機(jī)成為多播組的成員將執(zhí)行以下步驟主機(jī)向所有連接廣播一IGMP主機(jī)成員報(bào)告。附近的一個(gè)具CBT算法的路由器喚醒加入樹(shù)的過(guò)程：產(chǎn)生JOIN_REQUEST信息將信息發(fā)往沿著導(dǎo)向組的核心路由器的路徑的下一個(gè)站點(diǎn)。核心路由或發(fā)送路由和核心路由之間的另一路由器確認(rèn)該信息。2023/10/2339史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)當(dāng)一主機(jī)成為多播組的成員將執(zhí)行以下步驟請(qǐng)求加入的信息在它穿過(guò)的路由器暫時(shí)建立加入狀態(tài)，包括組、進(jìn)入的接口和連出的接口。所有中間路由器處理加入請(qǐng)求：確認(rèn)加入請(qǐng)求是從那個(gè)接口接收的。告知信加入的主機(jī)CBT傳送樹(shù)。臨時(shí)狀態(tài)如果沒(méi)有接到從上游傳來(lái)的確認(rèn)信息，將最終超時(shí)。因?yàn)橛信R時(shí)加入狀態(tài)，加入確認(rèn)可以沿著加入請(qǐng)求來(lái)的路徑返回。一旦加入確認(rèn)到達(dá)產(chǎn)生加入請(qǐng)求的路由器，發(fā)向這個(gè)組的信息將同時(shí)發(fā)往這個(gè)新的接收者。2023/10/2340史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)CBT請(qǐng)求加入的信息在它穿過(guò)的路由器暫時(shí)建立加入狀態(tài)，包括組、進(jìn)入的接口和連出的接口。所有中間路由器處理加入請(qǐng)求：確認(rèn)加入請(qǐng)求是從那個(gè)接口接收的。告知信加入的主機(jī)CBT傳送樹(shù)。臨時(shí)狀態(tài)如果沒(méi)有接到從上游傳來(lái)的確認(rèn)信息，將最終超時(shí)。因?yàn)橛信R時(shí)加入狀態(tài)，加入確認(rèn)可以沿著加入請(qǐng)求來(lái)的路徑返回。一旦加入確認(rèn)到達(dá)產(chǎn)生加入請(qǐng)求的路由器，發(fā)向這個(gè)組的信息將同時(shí)發(fā)往這個(gè)新的接收者。2023/10/2341史忠植高級(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)的。2023/10/2342史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)問(wèn)題的形式化定義給定圖G=(V,E,c)V=頂點(diǎn)集E=邊集2023/10/2343史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)0c=

成本函數(shù)

c:

E?

Z

+(邊?非負(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ù)上邊Dijkstra最短路徑算法?

v∈V,將v加到集合U,Distance(v)=cost(s,

v)Distance(s)=0;從U中刪除s.while

U不為空do具有最小距離的任何G的成員v.U=U-{v}.For

每個(gè)v的近鄰w,doif

member(w,

U)Begin.??????????distance(w)

=

min(distance(w),

cost(w,

v)

+

distance(v)

);?2023S/1t0o/2p3

.44史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)Matsuyama最短成本路徑啟發(fā)式算法T1

:

包含任選的i∈Z的G的子樹(shù).k=1;2023/10/2345史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)Zk={i}.在Tk

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

到I的最短路徑建樹(shù)Tk+1k

=

k+1.If

k<p,轉(zhuǎn)T1.If

k=p,輸出結(jié)論TpBegin???找到離Tk

最近的i

∈Z-Zk????Stop.?KMB

算法輸入：圖G和頂點(diǎn)集Z輸出：Steiner樹(shù)Th步驟：由G和Z建立完全有向帶權(quán)圖G1=（V1，E1，c1）。找到G1的最小生成樹(shù)。用G中相應(yīng)的最短路徑替換T1中的一邊，建立G的子圖Gs。找到Gs的最小生成樹(shù)Ts。如必要的話刪去Ts

中的邊，構(gòu)建Steiner

樹(shù)Th

，使得Th

中所的葉子為Steiner點(diǎn)。2023/10/2346史忠植高級(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ù)。2023/10/2347史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)KMB算法的工作過(guò)程2023/10/2348史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)KMB算法的工作過(guò)程2023/10/2349史忠植高級(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)棣藂的代價(jià)。如果v結(jié)點(diǎn)上波長(zhǎng)不能從λp變?yōu)棣藂

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

)=0。C(T)=

Σv∈T

w(p(v),v),λ(v))+Σv∈T-{s}

Cp(v)(λ

(p(v)),λ(v))，其中p(v)是樹(shù)中v點(diǎn)的父母。2023/10/2350史忠植高級(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)2023/10/2351史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)= 穿越

vi的最短路徑的數(shù)目，以權(quán)重作為是否吸收一結(jié)點(diǎn)為虛主干的重要標(biāo)準(zhǔn)建立虛主干的步驟找到圖

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

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

路由選擇算法建立虛主干。往多播組中加入一結(jié)點(diǎn)：建立該結(jié)點(diǎn)到已建立的虛主干之間的最短路由。虛主干到源的路由已經(jīng)建立起來(lái)了。把結(jié)點(diǎn)加入多播組。從多播組中去除一結(jié)點(diǎn)：先從多播組中移出該結(jié)點(diǎn)。如果是葉子結(jié)點(diǎn)，從多播樹(shù)中去掉該葉子。

如果該結(jié)點(diǎn)沒(méi)有下屬結(jié)點(diǎn)，剪除多余的枝干。2023/10/2353史忠植高級(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ù)中。2023/10/2354史忠植高級(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

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

SP

， 優(yōu)于DG。對(duì)于多播樹(shù)中結(jié)點(diǎn)最大度

(

也就是數(shù)據(jù)復(fù)制的份數(shù)

)

，

VTDM

大大小于

S小于DG。2023/10/2355史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)6.13

限界最短多播算法BSMABSMA算法使多播樹(shù)的成本最小化，并且保證所有的延遲小于預(yù)先設(shè)定的界限。BSMA的可行領(lǐng)域是所有延遲受限的Steiner樹(shù)。先簡(jiǎn)要的描述一下BSMA的步驟：首先用Dijkstra最短路

徑算法構(gòu)建最小延遲

Steiner

樹(shù)

T

0

，

在可行的區(qū)域內(nèi)不斷的重復(fù)更新T0以獲的更低的代價(jià)。2023/10/2356史忠植高級(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)沿途的延遲的上界。2023/10/2357史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)優(yōu)化Steiner樹(shù)的方法用Dijkstra

最短路徑算法構(gòu)建最小延遲Steiner

樹(shù)T

0法在前面已經(jīng)介紹過(guò)了。怎樣在可行的區(qū)域內(nèi)不斷的優(yōu)化

T0，使最后獲得的樹(shù)的成本最小呢。這里要用到路徑交換法，優(yōu)化Tj

獲得Tj+1步驟如下：從Tj中選擇路徑p2023/10/2358史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)jTj

=

Tj1

+

T

2

∪

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

j

s

j+1Tj+1

=T

1

+T

2

∪p.T

滿足延遲受限。超邊首先從

T

j

獲得

T

j

/

，

樹(shù)T

j

/

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

2

的中繼結(jié)點(diǎn)。

T

j

/

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

條超邊都是

Tj

中交換的候選路徑2023/10/2359史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)BSMA具體算法初始化所有超邊為無(wú)標(biāo)記。第一步:在所有無(wú)標(biāo)記邊中，BSMA選中最高成本的超邊Ph

。將Ph

和另一條成本低一些的超邊交換，得到的樹(shù)延遲受限。以下兩種情況必有一種發(fā)生：延遲限界的最短路徑與Ph相同。標(biāo)記超邊，轉(zhuǎn)第一步。延遲限界的最短路徑不同于Ph.替換刪除所有的超邊的記號(hào)。轉(zhuǎn)到第一步。當(dāng)所有超邊都被標(biāo)記后算法停止。2023/10/2360史忠植高級(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)建停止：新發(fā)現(xiàn)的最短路徑和剛刪除的等長(zhǎng)。新發(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。2023/10/2361史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)貪心路徑交換增益=進(jìn)行了一輪路徑交換以后