1、Internet拓撲結構與IP多播,程遠 2002.9,提綱,Internet 拓撲結構 Internet 的構成 網(wǎng)絡結構實例 隱藏的規(guī)律：power law IP多播 多播定義、概念及應用 多播協(xié)議 多播可擴展性的討論,Internet 拓撲結構？,Internet是研究對象。 ”You cant resolve the traffic jam problem of a city without looking at the street layout. ” 對網(wǎng)絡的感性認識，解答一些基本的問題： Internet的規(guī)模？ 中國網(wǎng)絡的基本情況？ Cernet的基本情況？ Internet拓

2、撲圖節(jié)點度數(shù)概率分布：power law,Internet : ASes + BGP,Internet由大約13000個自治系統(tǒng) (Autonomous System)構成 自治系統(tǒng)：處于一個機構管理之下的若干網(wǎng)絡和路由器構成了自治系統(tǒng)。每一個自治系統(tǒng)有一個16比特的自治系統(tǒng)號，全球唯一。其中1-32767可供分配，32768 64511暫時保留，64512 65534用于私有AS（類似于IP地址中的內(nèi)網(wǎng)地址） 邊界網(wǎng)關協(xié)議(Border Gateway Protocol，BGP)：自治系統(tǒng)之間的路由協(xié)議。該協(xié)議的基本功能是與其它自治系統(tǒng)交換網(wǎng)絡可達性信息,這種可達性信息包含了通往目標所要穿越

3、的自治系統(tǒng)記錄,利用這些信息,系統(tǒng)就可以構建一個無環(huán)的自治系統(tǒng)連接圖,并把形成的外部路由信息重發(fā)布給內(nèi)部網(wǎng)關協(xié)議(Internal Gateway Protocol , IGP) 。,AS內(nèi)部結構（以OSPF為例）,一個域內(nèi)路由協(xié)議為OSPF的AS被劃分成若干區(qū)域(area) 每個區(qū)域就是按同一OSPF路由協(xié)議組合在一起的一組路由器，區(qū)域中的路由器僅需備份本區(qū)域的拓撲結構數(shù)據(jù)庫即可。 每個區(qū)域都用一個數(shù)字來標識,其中0號區(qū)域為骨干區(qū)域。 骨干區(qū)域的主要工作是在其余區(qū)域間傳遞路由信息。當一個非骨干區(qū)域的路由信息對外廣播時,其路由信息是先傳遞至骨干區(qū)域,再由骨干區(qū)域?qū)⑵湫畔⑾蚱渌麉^(qū)域作廣播。,IN

4、TERNET,自治系統(tǒng)AS (ISP網(wǎng)絡),自治系統(tǒng)主干網(wǎng),地區(qū)級網(wǎng)絡,地區(qū)級網(wǎng)絡主干,校園網(wǎng),Internet交換中心 IX(Internet Exchange Point),2002年April 1-16 10,999 個 AS系統(tǒng) (大概是當前Internet所有AS系統(tǒng)總數(shù)的84%) 34,209 個 peering sessions,中國互聯(lián)網(wǎng)概況,至2002年6月， 全國IP網(wǎng)端口達到2618萬個。從APNIC獲得AS號103個，使用中的AS號？個。 中國九大互聯(lián)網(wǎng) 中國科技網(wǎng)（CSTNET） 中國公用計算機互聯(lián)網(wǎng)（CHINANET） 中國教育和科研計算機網(wǎng)（CERNET） 中國聯(lián)

5、通互聯(lián)網(wǎng)（UNINET） 中國網(wǎng)通公用互聯(lián)網(wǎng)(CNCNET) 中國國際經(jīng)濟貿(mào)易互聯(lián)網(wǎng)（CIETNET） 中國移動互聯(lián)網(wǎng)（CMNET） 中國長城互聯(lián)網(wǎng)（CGWNET） 中國衛(wèi)星集團互聯(lián)網(wǎng)（CSNET） 中國三大交換中心（IX） 北京、上海、廣州,Cernet,CERNET有相當于57個B類這么多的IP地址。 CERNET由一個主干網(wǎng)和八個地區(qū)網(wǎng)組成 主干網(wǎng)為一個自治系統(tǒng)，AS號4538。域內(nèi)路由協(xié)議為OSPF。 OSPF area 0 （主干）： 202.112.1.0/24 DDN 發(fā)送者向rp注冊。只有在樹上的路由器需要存儲狀態(tài)；更高效 CBT ，Core/RP，雙向樹，支持廠家少 PIM-

6、SM，RP（相會點），單向樹，每個group一個。,hosts,routers,多播轉(zhuǎn)發(fā)樹,源樹，也稱最短路徑樹（SPT） 以發(fā)送者為樹根，到每一個接收者的最短路徑構成一棵轉(zhuǎn)發(fā)樹。 可以用二元組（s, g)標示一棵源樹。 從發(fā)送者到接收者的路徑最優(yōu)，但需要維護較多狀態(tài)信息。 共享樹ST 以某個路由器為根（RP或Core）到所有接收者的樹。 可以用（*，g）標示一棵共享樹。 一棵樹被多個發(fā)送者共享，維護較少的狀態(tài)信息，但轉(zhuǎn)發(fā)路徑未必最優(yōu)。樹根的位置很重要。,RPF,在構造多播樹的過程中，路由器接收到一個數(shù)據(jù)包，要對它執(zhí)行RPF (Reverse Path Forwarding)檢查。具體過程為：

7、路由器r獲得該多播數(shù)據(jù)包的源地址s和進入路由器時的接口i，然后r執(zhí)行“逆向轉(zhuǎn)發(fā)檢查”：假想要把數(shù)據(jù)包用單播方式從r發(fā)送到s，查找路由表，看是不是會從接口i發(fā)送出去，若是，則RPF檢查通過，接收并轉(zhuǎn)發(fā)該數(shù)據(jù)包；否則RPF檢查失敗，丟棄該數(shù)據(jù)包。 這樣，路由器可以確保自己在多播樹中“入射”的路徑只有一條，并且是到發(fā)送者最優(yōu)的那一條。 從全局來看則保證了構造的結果沒有環(huán)路，是一棵樹。,DVMRP,Distance-Vector Multicast Routing Protocol 較早提出的多播協(xié)議，首先部署在MBone上，“密集模式”。 發(fā)送者的第一跳路由器開始向所有下行端口發(fā)送多播數(shù)據(jù)包。網(wǎng)絡中

8、間的路由器對接收到的數(shù)據(jù)進行RPF檢查。 最后一跳路由器根據(jù)IGMP信息返回修剪或嫁接一個分支。,DVMRP- Example Topology,g,g,s,g,DVMRP- Phase 1: Truncated Broadcast,g,g,s,g,DVMRP- Phase 2: Pruning,g,g,s,prune (s,g),prune (s,g),g,DVMRP- Steady State,g,g,s,g,g,graft (s,g),graft (s,g),DVMRP- Grafting on New Receivers,g,g,s,g,g,report (g),DVMRP- Stea

9、dy State after Grafting,g,g,s,g,g,PIM-SM,Protocol Independent Multicast-Sparse Mode“協(xié)議無關”的多播協(xié)議。 不用交換多播路由信息 利用單播路由表 接收者向RP發(fā)送“join”消息，發(fā)送者發(fā)送之前首先向RP注冊 “當前最好”的域內(nèi)協(xié)議 權衡效率和復雜性 得到最廣泛的支持和部署,RP,R1,R2,R3,R4,Join messagetoward RP,Shared tree after R1,R2,R3 join,Phase 1: Build Shared Tree,Join G,Phase 2: Sources

10、Send to RP,RP,R1,R2,R3,R4,S1,unicast encapsulated data packet to RP,RP decapsulates, forwards downShared tree,S2,Phase 3: Stop Encapsulation,RP,R1,R2,R3,R4,S1,Join G for S1,Join G for S2,S2,(S1,G),(S1,G) (S2,G),(*.G),Phase 4: Switch to Shortest Path Tree,RP,R1,R2,R3,R4,Join messagestoward S2,shared

11、tree,S1,S2,Phase 5: Prune (S2 off) Shared Tree,RP,R1,R2,R3,R4,S1,S2 distribution tree,Shared tree,Prune S2 off Shared tree where iif of S2 andRP entries differ,S2,可擴展性討論（二）,每對（發(fā)送者，組）需要一棵樹。 DVMRP：需要把信息Flood到全網(wǎng)，每一個路由器需要為每一對（發(fā)送者，組）保存狀態(tài)信息，自己構造路由。 PIM-DM：類似于DVMRP，利用單播路由表。 MOSPF：劃分為area，只需要把組員信息Flood到整個ar

12、ea。利用單播路由表。 每個（組）需要一棵共享樹。 PIM-SM：需要RP,顯式加入、退出消息，只有在多播樹上的路由器需要為每一（組）保存狀態(tài)信息，利用單播路由表。 CBT：類似于PIM-SM，需要Core。構造雙向共享樹。,可擴展性討論（三）,經(jīng)驗顯示單層的網(wǎng)絡結構不具有可擴展性 每一個路由器都需要知道其他所有的路由器/子網(wǎng)（需要保存大量的狀態(tài)信息）。 單層網(wǎng)絡規(guī)模增加時趨向于不穩(wěn)定，一個錯誤操作可能波及全網(wǎng)。 層次結構網(wǎng)絡中的多播需要解決的問題： 域內(nèi)多播路由協(xié)議 域間多播路由交換協(xié)議 連接不同域的多播樹的機制 多播地址分配問題,域間多播協(xié)議,域間協(xié)議 MBGP/PIM-SM/MSDP (

13、near-term) MBGP用來交換域間的multicast路由，PIM-SM 用于連接不同域的同一多播組成員，MSDP用于不同域間的RP交換活動的 multicast發(fā)送者信息。 MASC/BGMP (long-term) MASC為各個AS域分配層次結構的多播地址。 BGMP構造一個以根域(root domain)為根的雙向域間多播樹，這棵樹可以由多個多播組共享。,hosts,routers,MSDP的提出,域內(nèi)協(xié)議時：每一個多播組只有一個RP。當擴展到多個域時，每一個域內(nèi)對于每一個活動的多播組都至少有一個RP，從而從全局的觀點看，一個多播組有多個RP同時存在于不同的域中并且互不了解！

14、對于域內(nèi)的情況：接收者可以向RP發(fā)送“join”消息加入多播樹，發(fā)送者可以向同一RP注冊，從而向位于同一域的接收者發(fā)送多播數(shù)據(jù)；而對于其他域的同組接收者就無能為力了。,MSDP,Multicast Source Discovery Protocol。每一個域向其他域宣告本域中活動著的發(fā)送者信息。 MSDP運行在路由器RP之中。 相鄰域的MSDP peer配置 MSDP sessions (TCP連接) 通訊 。 本域出現(xiàn)一個新的發(fā)送者時，該發(fā)送者向RP注冊。 本域的MSDP peer獲知該信息后，向所有鄰域的 MSDP peers 發(fā)送Source Active (SA)消息：包括（發(fā)送者，組

15、）信息。 MSDP peers收到 SA消息后作RPF檢查，以避免環(huán)路，檢查成功則所有其他鄰居發(fā)送該消息。 收到SA的MSDP peer (同樣是RP)會察看自己域內(nèi)是否有該多播組成員（即是否已經(jīng)構建了該多播組的轉(zhuǎn)發(fā)樹）。若是，則向該發(fā)送者發(fā)送一條PIM join消息以完成該組轉(zhuǎn)發(fā)樹的構建，或者通過轉(zhuǎn)發(fā)樹向域內(nèi)的接收者轉(zhuǎn)發(fā)數(shù)據(jù)。,MBGP,Multiprotocol Extensions to BGP4 / Multicast BGP / BGP4+，運行于自治系統(tǒng)邊界路由器。 MBGP用來提供域間的“下一跳”信息，類似于BGP為單播提供域間“下一跳”信息。 向相鄰的自治系統(tǒng)通告“從我這里可以

16、到達發(fā)送者s”。當RP或者多播組接收者試圖向位于其他AS的多播發(fā)送者s發(fā)送一個”join” 消息時，該消息需要沿著“逆向路徑”到達多播發(fā)送者s，有了MBGP提供的路由就可以做到這一點了。 MBGP并不負責域間多播樹的構造，用現(xiàn)有協(xié)議PIM-SM就可以勝任。,MBGP/PIM-SM/MSDP,RP,RP,RP,RP,MSDP peer,Physical link,A,B,C,D,Receiver,Source,PIM message,MSDP message,可擴展性討論（四）,Asia-Pacific Advanced Network (APAN) 和 Internet2 的主干網(wǎng)Abilen

17、e以及CERNET都部署了MBGP/PIM-SM/MSDP MSDP的SA需要定期散發(fā)（每60秒），模式類似于DVMRP。雖然在域這個層次，但是當多播廣泛部署后，若某個域同時存在成千上萬個活動的發(fā)送者，則該域向其他鄰域就要發(fā)送多條SA，并進一步散發(fā)出去。,可擴展性討論（五）,PIM-SM需要為每一個多播組構造一棵共享樹并保存狀態(tài)。在Internet 中，可能有數(shù)量巨大的多播樹通過主干網(wǎng)絡，這些樹的狀態(tài)維護需要大量的資源。 公認只適于作為近期的解決方案，需要進一步研究具有更好可擴展性的多播體系結構。,MASC/BGMP,MASC/BGMP (long-term) MASC ( Multicast

18、 Address-Set Claim)為各個AS域分配層次結構的多播地址。 從而多播的組地址也可以像單播地址那樣進行匯聚。 BGMP (Border Gateway Multicast Protocol) 構造一個以根域(root domain)為根的雙向域間多播樹，這棵樹可以由多個多播組共享，對比與PIM-SM協(xié)議每一個多播組需要一棵共享樹，從而進一步提高了可擴展性。,總結,“單播-域內(nèi)多播密集模式-域內(nèi)多播稀疏模式-域間多播-多播地址匯聚/多播樹共享” 多播的產(chǎn)生和發(fā)展的過程就是不斷追求可擴展性的過程。 AS級別的IP多播已經(jīng)得到部署并取得較好的應用效果，整個Internet范圍內(nèi)IP多播的體系結構仍需要進一步的研究。,部分參考文獻,1Kevin. Almeroth, The evolution of multicast: From the MBone to inter-domain multicast to Internet2 deployment, IEEE Network, January/February 2000. 2T. Wong and R