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

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

約束Steiner樹6.7反向路徑廣播6.8截斷的反向路徑廣播6.9反向路徑多播

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

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

6.15多播的應(yīng)用

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

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

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

ProtocolIndependentMu1ticast、

Mu1ticastBorderGatewayProtocol

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

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

2024/9/2613史忠植高級計算機網(wǎng)絡(luò)SRSPT樹的缺點（1）沒有最小化整個分布式處理的代價；（2）可伸縮性不好；

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

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

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

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

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

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

?

從路由器A收到報文，確認連接1是源-組對的父母鏈。

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

?從路由選擇信息交換中得知路由器C認為連接2是源-組對的父母鏈，于是不再將報文發(fā)往連接3。?路由器C將丟棄從連接3來的報文，因為是從源-組對的非父母鏈上來的。2024/9/2628史忠植高級計算機網(wǎng)絡(luò)6.8截斷的反向路徑廣播

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

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

因為接口2至少含有第一組的一個成員，路由器把報文發(fā)往接口2。?

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

接口4沒有目標組的成員，報文不發(fā)往接口4。

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

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

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

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

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

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

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

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

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

維護原始路由的特性。

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

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

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

Z0+(邊

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

2024/9/2643史忠植高級計算機網(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每個v的近鄰w,doifmember(w,U)distance(w)=min(distance(w),cost(w,v)+distance(v)); Stop.2024/9/2644史忠植高級計算機網(wǎng)絡(luò)Matsuyama最短成本路徑啟發(fā)式算法

BeginT1: 包含任選的i∈Z的G的子樹.

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

最近的i

Z-Zk

在Tk

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

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

Stop.

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

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

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

W(e,

i):邊e上波長為

i的成本。如果邊e上

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

p,

q):v結(jié)點上波長從

p變?yōu)?/p>

q的代價。如果v結(jié)點上波長不能從

p變?yōu)?/p>

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

p,

q)=0。C(T)=

v

Tw(p(v),v),

(v))+

v

T-{s}Cp(v)(

(p(v)),

(v))，其中p(v)是樹中v點的父母。2024/9/2650史忠植高級計算機網(wǎng)絡(luò)虛主干虛主干是基本圖中的一棵樹，用作建立多播樹的模板，也就是說，擴展為虛主干的結(jié)點具有最大可能性變?yōu)槎嗖渲械囊徊糠帧Ｈ绻粋€結(jié)點有越多的路徑穿過它，就有越大的可能成為多播樹的一部分。定義點vi

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

（1）找到圖

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

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

1.

建立虛主干。

2.

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

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

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

B)第一步:

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

第二步:

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

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

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

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

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

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

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

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

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

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

用Dijkstra最短路徑算法構(gòu)建最小延遲Steiner樹T0的方法在前面已經(jīng)介紹過了。怎樣在可行的區(qū)域內(nèi)不斷的優(yōu)化T0，使最后獲得的樹的成本最小呢。這里要用到路徑交換法，優(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史忠植高級計算機網(wǎng)絡(luò)超邊

首先從

Tj

獲得

Tj/，樹Tj/

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

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

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

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

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

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

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

替換

刪除所有的超邊的記號。

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

BSMA動態(tài)遞增的計算子樹Tj1

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

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

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

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

c=Tj

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

BSMATj