高級計算機網絡教學教材

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

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

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

6.13限界最短多播算法BSMA6.14適用于光纖網絡的多播的MZQ算法

6.15多播的應用

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

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

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

ProtocolIndependentMu1ticast、

Mu1ticastBorderGatewayProtocol

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

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

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

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

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

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

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

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

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

?

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

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

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

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

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

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

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

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

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

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

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

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

2024/9/2640史忠植高級計算機網絡CBT

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

2024/9/2641史忠植高級計算機網絡6.11路由多播選擇算法KMB理想化的多播路由選擇算法應該是：

構建樹時具有所想要的成本和延遲特征。

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

維護原始路由的特性。

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

是由接收者驅動的。

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

Z0+(邊

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

2024/9/2643史忠植高級計算機網絡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史忠植高級計算機網絡Matsuyama最短成本路徑啟發(fā)式算法

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

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

最近的i

Z-Zk

在Tk

的基礎上加入從Tk

到I的最短路徑建樹Tk+1 k=k+1.Ifk<p,轉T1.Ifk=p,輸出結論Tp

Stop.

2024/9/2645史忠植高級計算機網絡KMB算法

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

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

W(e,

i):邊e上波長為

i的成本。如果邊e上

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

p,

q):v結點上波長從

p變?yōu)?/p>

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

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史忠植高級計算機網絡虛主干虛主干是基本圖中的一棵樹，用作建立多播樹的模板，也就是說，擴展為虛主干的結點具有最大可能性變?yōu)槎嗖渲械囊徊糠?。如果一個結點有越多的路徑穿過它，就有越大的可能成為多播樹的一部分。定義點vi

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

（1）找到圖

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

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

1.

建立虛主干。

2.

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

虛主干到源的路由已經建立起來了。把結點加入多播組。

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

B)第一步:

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

第二步:

如果A已經在多播樹上，轉到第三步。否則，把從A到源結點的路由不在多播樹上的那部分加入多播樹中。第三步:

把結點B加入多播樹中。2024/9/2654史忠植高級計算機網絡模擬結果

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

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

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

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

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

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

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

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

用Dijkstra最短路徑算法構建最小延遲Steiner樹T0的方法在前面已經介紹過了。怎樣在可行的區(qū)域內不斷的優(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史忠植高級計算機網絡超邊

首先從

Tj

獲得

Tj/，樹Tj/

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

的邊稱為超邊，在超邊的兩個端結點之間的所有結點，都是度為2的轉送結點。每條超邊都是

Tj中交換的候選路徑2024/9/2659史忠植高級計算機網絡BSMA具體算法

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

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

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

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

替換

刪除所有的超邊的記號。

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

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

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

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

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

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

c=Tj

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

BSMATj