《現(xiàn)代通信網(wǎng)》第六章互聯(lián)網(wǎng)2

1、2022/9/81現(xiàn)代通信網(wǎng)2022/9/82第六章 Internet6.1 Internet概述6.2 協(xié)議與互連的原理6.3 IP層6.4 傳輸層 6.5 應(yīng)用層6.6 IPv62022/9/83 一 網(wǎng)絡(luò)層的服務(wù)和協(xié)議一般網(wǎng)絡(luò)層的主要功能是實現(xiàn)主機到主機間的邏輯通信：1）選路功能2）轉(zhuǎn)發(fā)功能3）差錯報告forwardingtableRouting protocols路徑選擇RIP, OSPF, BGP傳輸層: TCP, UDP數(shù)鏈層物理層網(wǎng)絡(luò)層ARP protocol 地址映射IP protocol地址格式數(shù)據(jù)報格式分組處理規(guī)則ICMP protocol差錯報告router “signa

2、ling”2022/9/84網(wǎng)絡(luò)層的服務(wù)模式：best effort網(wǎng)絡(luò)層的服務(wù)模式：是指網(wǎng)絡(luò)在從源端到目的端轉(zhuǎn)發(fā)分組時，所提供信道的方式和服務(wù)模式的定義：帶寬是否有保證？時延抖動是否限制？是否控制擁塞？是否保證有序傳輸？是否保證可靠傳輸？ IP采用盡力而為的服務(wù)模式 盡力而為的服務(wù)模式不保障最大時延，重復(fù)，丟失，錯序。2022/9/85網(wǎng)絡(luò)層服務(wù)模式：比較下表是Internet、電路交換，ATM ABR服務(wù)模型的比較。網(wǎng)絡(luò)體系結(jié)構(gòu)服務(wù)模型帶寬保證丟失保證排序定時擁塞指示Internet盡力而為無無無不維持無電路交換CBR恒定速率是有維持無擁塞ATMABR最小速率是有維持提供擁塞指示2022/

3、9/86二 IPv4數(shù)據(jù)報的格式048121619242831versionHLenTOSTotal LengthIdentifierFlagOffsetTTLProtocolHeader ChecksumSource AddressDestination AddressOptions (if any)Data20字節(jié) 采用無連接的數(shù)據(jù)報服務(wù)模式：每一個數(shù)據(jù)報都包含選路轉(zhuǎn)發(fā)需要的全部信息。2022/9/87版本號：指明數(shù)據(jù)報的IP協(xié)議版本，典型值4。頭部長度：以32bit為單位的數(shù)據(jù)報頭部長度，通過它可知數(shù)據(jù)報中的數(shù)據(jù)部分從哪開始，典型值5。服務(wù)類型：提供優(yōu)先級信息（時延，可靠性）。總長度：以

4、字節(jié)為單位的數(shù)據(jù)報總長度（含頭部）。實際很少超過1500字節(jié)，經(jīng)常被限制在576字節(jié)以內(nèi)。標識符，標志，分片偏移量主要用于分片標識符：它是一個序號，與源地址，目的地址以及用戶協(xié)議一起唯一識別一個數(shù)據(jù)報。標志：目前只定義了2個bit，DF（Dont Fragment）為真，則禁止分片；MF（more fragment)為假表示為原數(shù)據(jù)報中最后的一個數(shù)據(jù)報片。分片偏移量：以64bit為單位，指出該片在原數(shù)據(jù)報中的位置。DFMF參數(shù)的含義2022/9/88生存期TTL：路由器每處理一個數(shù)據(jù)報，必須將其TTL值減1，當TTL0時則丟棄分組。協(xié)議：指明目的端傳送層的協(xié)議類別。 TCP = 6, ICMP

5、 = 1, UDP = 17頭部校驗和：該值在每一個路由器上都要進行從新計算和生成。源和目地地址：32bit的地址，指明主機和其所在網(wǎng)絡(luò)的位置?？蛇x項：允許IP頭部被擴展，但出于性能上的考慮，目前很少使用，IPV6中則完全取消。參數(shù)的含義2022/9/89三 IP分組的分片:Fragmentation每個網(wǎng)絡(luò)都有自己的MTU（ Maximum Transmission Unit ）。信源無法預(yù)先獲知所有中間網(wǎng)絡(luò)的MTU。IP解決方案：分片hosthostrouterrouterMTU = 4000MTU = 1500MTU = 20002022/9/810 Reassembly在哪兒重裝？目的

6、節(jié)點還是路由器？目的節(jié)點避免大分組被重復(fù)多次分片假如丟失了一片，則丟棄整個分組中間節(jié)點重裝的潛在問題很難確定需要多少重裝緩沖區(qū)數(shù)據(jù)報網(wǎng)絡(luò)路徑改變帶來的風(fēng)險多條路徑的并存網(wǎng)絡(luò)狀態(tài)的變化2022/9/811與分片相關(guān)的字段LengthIP分片的長度Identification 與其它分片進行匹配FlagsDont fragment flagMore fragments flagFragment offset本分片在整個分組中的位置以64bit為計數(shù)單位 (13 bit長)2022/9/812IP分片 例1hostrouterMTU = 4000IPHeaderIPDataLength = 3820

7、, M=02022/9/813 IP 分片例2routerrouterMTU = 2000IPHeaderIPDataLength = 3820, M=03800 bytesIPHeaderIPDataLength =1940, M=1, Offset = 01920 bytesIPDataIPHeaderLength = 1900, M=0, Offset = 2401880 bytes2022/9/814IP分片例3IPHeaderIPDataLength = 1940, M=1, Offset = 01920 bytesIPDataIPHeaderLength = 1900, M=0,

8、Offset = 2401880 byteshostrouterMTU = 1500IPHeaderIPDataLength = 1460, M=1, Offset = 01440 bytesIPHeaderIPDataLength = 480, M=1, Offset = 180460 bytesIPHeaderIPDataLength = 1460, M=1, Offset = 2401440 bytesIPHeaderIPDataLength = 460, M=0, Offset = 420440 bytes2022/9/815IP 重裝-目的端由于分片到達的順序可能是亂的因此最后一個分

9、片到達前，很難確分組的實際長度。有些分片可能重復(fù)只保留一個拷貝某些分片可能丟失丟棄整個分組IPHeaderIPDataLength = 1460, M=1, Offset = 0IPHeaderIPDataLength = 480, M=1, Offset = 180IPHeaderIPDataLength = 1460, M=1, Offset = 240IPHeaderIPDataLength = 460, M=0, Offset = 420IPDataIPDataIPDataIPData2022/9/816分片和重裝的背后展示了許多Internet設(shè)計的基本原則Decentralized

10、每個網(wǎng)絡(luò)獨立選擇 MTUConnectionless每個 (fragment of) 分組包含 全部的選路信息。每個分片在網(wǎng)中獨立地選路和處理Best effort目的地可以放棄重裝假如重裝失敗，無需通知發(fā)送方Complex endpoints and simple routers在目的地重裝。2022/9/817思考：當前Internet如何控制分片的有害性？2022/9/818四 IPv4編址方式IP 地址在網(wǎng)絡(luò)層上屏蔽了異種網(wǎng)絡(luò)之間物理地址的差異，利于網(wǎng)間通信的實現(xiàn)。IP地址：32bit,由網(wǎng)絡(luò)部分和主機部分組成，其中高階bit標識網(wǎng)絡(luò)部分（網(wǎng)絡(luò)前綴），低階bit標識主機部分。接口（In

11、terface）：主機/路由器與物理鏈路連接器。 典型的一個路由器有多個接口，主機通常有一個接口，而一個IP地址只能用來唯一地標識一個接口。“全0”代表“本”， “全1”代表“全部”。點分十進制表示法： = 11011111 00000001 00000001 000000012231112022/9/819IP子網(wǎng)02118172.161212NetworkHost.Fei_1/1Fei_1/2路由器每個端口連接一個IP子網(wǎng)，同一個子網(wǎng)要求接口具備相同網(wǎng)絡(luò)前綴。2022/9/820IPv4分類編址Network IDHost IDNetwork IDHost ID816Class A320C

12、lass B10Class C110Multicast AddressesClass D1110Reserved for experimentsClass E111124總共l IP 地址空間: 4 billionClass A: 128 networks, 16M hosts， 55Class B: 16K networks, 64K hosts ， 55Class C: 2M networks, 256 hosts， 552022/9/821 特殊IP地址與專用IP地址用于廣播，也稱定向廣播，需要指定目標網(wǎng)絡(luò)主機地址全1用于指定網(wǎng)絡(luò)本身，稱之為網(wǎng)絡(luò)地址或者網(wǎng)絡(luò)號主機地址全0指本地節(jié)點(一般

13、為)，用于測試網(wǎng)卡及TCP/IP軟件網(wǎng)絡(luò)用途地址 RFC1918中規(guī)定如下地址是私有地址： 一個A類地址， 16個B類地址， 256個C類地址 2022/9/822如何獲取網(wǎng)絡(luò)地址？機構(gòu)通常從其ISP處獲取IP地址。ISP會從已分配給他的更大的地址塊中為用戶提供一塊地址空間.ISP本身則從全球型的權(quán)威地址管理機構(gòu)ICANN獲取地址（Internet Corporation for Assign Names and Numbers).Regional Internet Registries (RIRs) ARIN (North America, Southern Africa), APNIC (

14、Asia-Pacific), RIPE (Europe, Northern Africa), LACNIC (South America)ICANN同時負責(zé)管理DNS根服務(wù)器，分配域名，解決域名紛爭問題。主機如何獲取IP地址?Hard-coded by system admin in a fileDHCP: Dynamic Host Configuration Protocol2022/9/823Subnet 編址 RFC917 (1984)原始分類地址優(yōu)缺點地址的前綴部分說明的地址的類型，也就說明的地址的網(wǎng)絡(luò)部分長度。選路只需要根據(jù)地址前綴部分進行即可。例如3，代表一個B類地址，因此可確定網(wǎng)

15、絡(luò)前綴為128.2，路由器只需要根據(jù)128.2選路轉(zhuǎn)發(fā)分組即可。網(wǎng)絡(luò)前綴的長度固定（8/16/24).路由表過大C類地址有2百萬之多。2022/9/824Subnet 編址 RFC917 (1984)子網(wǎng)地址的需求背景Class A & B 網(wǎng)太大幾乎沒有一個LAN的主機數(shù)接近64k原因既有物理電氣方面的約束，也有性能管理方面的約束。地址分配不夠靈活，導(dǎo)致地址使用效率低，地址空間消耗速度快。實際中需要一種簡單的方法將一個大的分類地址空間劃分為多個小的子網(wǎng)，提高地址使用效率，滿足單位的組網(wǎng)需要。2022/9/825子網(wǎng)編址在原有的兩層地址結(jié)構(gòu)中增加了一個新層：子網(wǎng)ID。通過子網(wǎng)ID，可以將一個分

16、類地址劃分成幾個子網(wǎng)。為識別網(wǎng)絡(luò)部分的實際長度，引入子網(wǎng)掩碼機制來確定主機和網(wǎng)絡(luò)部分的長度。子網(wǎng)掩碼的長度根據(jù)實際需要確定意味著網(wǎng)絡(luò)前綴的長度此時已經(jīng)可變了。NetworkHostNetworkHostSubnet1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 0 0 0 0 0 0 0SubnetMask2022/9/826網(wǎng)絡(luò)Prefixes 和 Masks1000110000000100000000000000000011111111111111100000000000000000/1510001100000001010000100100

17、01000010001100000001110000100100010000666 與網(wǎng)絡(luò)前綴 /15匹配6 與網(wǎng)絡(luò)前綴 /15不匹配掩碼2022/9/827子網(wǎng)劃分的例子假設(shè)某公司有一B類地址/16，有4個部門A，B，C，D，每個部門250臺機器。Internet網(wǎng)關(guān)路由器/16ABCD/24/24/24/242022/9/828Classless Inter-domain Routing(CIDR)傳統(tǒng)分類IP地址的缺點 不夠靈活，A，B類地址對大多數(shù)機構(gòu)太大，但C地址又太小。舉例如下： 某機構(gòu)擁有約2000臺主機，要構(gòu)建一個網(wǎng)絡(luò)，采用分類地址方案，則一個C 類網(wǎng)絡(luò)地址太小，而分配一個B可

18、解決問題，但地址空間的利用率又太低。實際建網(wǎng)面臨的問題 Internet規(guī)模激增，A,B類IP地址資源緊張（如何有效使用現(xiàn)有IP地址的問題）允許一個機構(gòu)內(nèi)部網(wǎng)絡(luò)結(jié)構(gòu)任意復(fù)雜，但對外整個網(wǎng)絡(luò)能夠擁有一個共同的網(wǎng)絡(luò)號。（控制由于網(wǎng)絡(luò)規(guī)模和結(jié)構(gòu)的復(fù)雜對性能的影響） 2022/9/829CIDR型地址的特點IETF在1993【rfc1519】將其標準化,對子網(wǎng)概念的進一步擴展。CIDR型IP地址的網(wǎng)絡(luò)部分可以任意長：不使用類型標識來確定網(wǎng)絡(luò)部分的長度。使用地址塊的公共部分做為網(wǎng)絡(luò)前綴。CIDR型的網(wǎng)絡(luò)地址必須采用形式a.b.c.d/x表示,其中x表示32bit的地址中，前x bit為網(wǎng)絡(luò)部分。分配給同

19、一機構(gòu)的地址空間必須保持連續(xù)（2的冪次）以實現(xiàn)地址聚集。2022/9/830C類地址的分區(qū)55 歐洲55 北美55 中南美55 亞太示例：在某路由器中，去往歐洲地區(qū)的路由項 可聚集為一項/7,相應(yīng)的網(wǎng)絡(luò)掩碼可寫為 對于本節(jié)開頭的例子，我們可為該機構(gòu)分配一塊連續(xù)C類地址202.4.16 .X- 202.4.23.X ，這樣地址的公共部分為21位，主機部分則為11位，最多標識2048臺，滿足設(shè)計要求。2022/9/831實例1例如：假設(shè)某機構(gòu)已分配了地址塊202.23.0.X202.23.7.X(8個連續(xù)的C類地址）.其下有八個機構(gòu)，ISP可將該塊地址均分為八份，如下圖所示：ISP地址塊 1100

20、1010 00010111 00000000 00000000 /21 機構(gòu) 0 11001010 00010111 00000000 00000000 /24機構(gòu)1 11001010 00010111 00000001 00000000 /24 機構(gòu)2 11001010 00010111 00000010 00000000 /24 . . . .機構(gòu)7 11001010 00010111 00000111 00000000 /24 子網(wǎng)地址擴展占3bit,主機部分剩余8bit2022/9/832CIDR下的分層選路與地址聚集ISProuterInternet.ISProuterInterne

21、t/24/24/24/24./21使用和不使用CIDR 的域間選路區(qū)別2022/9/833CIDR的最長前綴匹配Destination =6- payload Prefix Interface Next Hop /8 9 ATM 5/0/8 /15 /23 attached Ethernet 0/1/3 Serial 1/0/7 7 IP Forwarding Table /0 3 ATM 5/0/9 OKbetterbest!2022/9/834變長子網(wǎng)掩碼Variable Length Subnet Masking (VLSM)當一個網(wǎng)絡(luò)包含多個子網(wǎng)，且子網(wǎng)的大小不同，則可以使用VLSM。

22、這樣避免了IP地址的浪費，但需要路由協(xié)議支持2/27172.16.14. 64/276/27CBA/24/24center36/3032/3040/302022/9/835五 路由器的一般結(jié)構(gòu)控制平面路由功能：執(zhí)行路由協(xié)議，生成、更新和維護路由表。其它功能：擁塞控制，QoS等。路由表的基本信息目的網(wǎng)絡(luò)地址。路由信息的來源。下一跳的IP地址轉(zhuǎn)發(fā)端口input interfaceoutput interfaceInter-connectionMedium(Backplane)ForwardingTableControlProtocols2022/9/836控制平面：路由表GAR#show ip r

23、outeIPv4 Routing Table:Dest Mask Gw Interface Owner pri metric fei_1/1 bgp 200 0 53 55 fei_1/1 ospf 110 14 54 55 fei_1/1 ospf 110 13 48 gei_5/2.1 direct 0 0 55 gei_5/2.1 address 0 0 4 48 6 gei_5/2.4 direct 0 0 52 fei_1/1 direct 0 0 55 fei_1/1 address 0 0 2022/9/837五 路由器的一般結(jié)構(gòu)-轉(zhuǎn)發(fā)平面input interfaceoutpu

24、t interfaceInter-connectionMedium(Backplane)ForwardingTableControlProtocolsInput interfaces:必須執(zhí)行分組轉(zhuǎn)發(fā)確定轉(zhuǎn)發(fā)到哪一個出接口。執(zhí)行分組排隊，分類，標記Output interfaces:執(zhí)行分組排隊和分組調(diào)度。Backplane：互連出口與入口。2022/9/838判斷與目的端是否處于同一網(wǎng)段檢查ARP表是否有目的端MAC地址做數(shù)據(jù)鏈路層封裝（目的MAC為目的端MAC地址）通過物理層發(fā)送數(shù)據(jù)通過ARP獲得目的端MAC地址YESNOYESNO是否配置了缺省網(wǎng)關(guān)？YES檢查ARP表是否有網(wǎng)關(guān)MAC地址

25、做數(shù)據(jù)鏈路層封裝（目的MAC為網(wǎng) 關(guān)MAC地址）通過ARP獲得網(wǎng)關(guān)MAC地址NO發(fā)送錯誤信息YESNOEnd 獲取目的IP地址源端主機IP分組轉(zhuǎn)發(fā)流程2022/9/839同一網(wǎng)段通信過程圖示IP地址：MAC地址：00:20:AF:00:00:02IP地址：MAC地址：00:20:AF:00:00:01以太網(wǎng)IP層封裝IP包包發(fā)往IP地址以太網(wǎng)IP層封裝MAC幀幀發(fā)往MAC地址00:20:AF:00:00:02封裝MAC幀收到MAC幀ARP拆封IP包收到IP包AB網(wǎng)絡(luò)情況協(xié)議層次2022/9/840以太網(wǎng)以太網(wǎng)接口不同網(wǎng)段的通信過程以太網(wǎng)IP層MAC幀IP層串行接口以太網(wǎng)接口IP層網(wǎng)絡(luò)情況協(xié)議層

26、次PPP分組IP包IP包發(fā)送端主機A接收端主機B路由器EthernetPPPHOST AHOST Bfei-1/1e1_2/1Ethernetfei-1/1e1_2/1IP層路由器PPP幀IP包IP包串行接口MAC幀IP包IP包2022/9/841ARP工作機制IP: = ?我需要IP地址為主機的物理地址作用：隱藏底層網(wǎng)絡(luò)物理地址，以允許給每臺主機分配 任意IP地址組成：1)發(fā)送數(shù)據(jù)時，實現(xiàn)IP地址向MAC地址的映射 2)回答其它機器的ARP請求。2022/9/842ARP工作過程IP: Ethernet: 0800.0020.1111 IP: = ?我聽到廣播包了，這條消息是給我的 ，這是我

27、的物理地址.我需要IP地址為主機的物理地址2022/9/843你發(fā)現(xiàn)了什么？回憶異構(gòu)網(wǎng)互聯(lián)的原理每個host/Router上兩張表路由表根據(jù)目的IP確定：1）下一跳路由器得IP地址。2）輸出端口號ARP表根據(jù)下一跳路由器IP地址確定：1）下一跳路由器得數(shù)鏈層地址。datagram inDatagram out路由表ARP表節(jié)點TCPUDPIPEthernetDriverRoutingTableARPTable報文段數(shù)據(jù)報以太幀2022/9/844IP地址與轉(zhuǎn)發(fā)的總結(jié)IP地址IP 地址實際對應(yīng)的是一個網(wǎng)絡(luò)Interface。分類IP地址 (A,B,C) 的地址分配效率很低，運營商和大型園區(qū)網(wǎng)都不

28、使用。CIDR (Supernet) 主要用途是將一組連續(xù)的C類地址進行聚集，而子網(wǎng)的用途則是將一個分類地址進行細分。轉(zhuǎn)發(fā)：路由器總是基于IP地址選路，然后用物理地址完成封裝的轉(zhuǎn)發(fā)。路由器和主機上總是運行了兩個網(wǎng)絡(luò)層協(xié)議，IP扮演邏輯網(wǎng)絡(luò)協(xié)議，物理網(wǎng)絡(luò)協(xié)議則扮演了數(shù)鏈層的角色。2022/9/845六 選路算法：原理關(guān)于Internet，我們已知 IP 地址的結(jié)構(gòu)反映了Internet的結(jié)構(gòu)IP 分組頭負責(zé)運載IP地址信息當分組到達路由器：檢查頭部尋找分組中攜帶目的地IP地址查路由表確定到目的地的下一跳地址通過指定的端口轉(zhuǎn)發(fā)分組問題：路由器如何產(chǎn)生、維護路由表？如何確保不同路由器上路由表數(shù)據(jù)的一

29、致性？運營商如何控制鏈路上的負載？Router2022/9/846原理：網(wǎng)絡(luò)的建模網(wǎng)絡(luò)中的每臺router用一個節(jié)點來表示。路由器之間的直連鏈路用邊表示。Symmetric links undirected graph邊的 “cost” c(x,y) 表示鏈路的成本度量值delay, $ cost, or congestion 級別任務(wù)計算每一個頂點到任意其它頂點的最小成本路徑 Path cost d(x,y) = 路徑上所有鏈路成本之和AEFCDB236411132022/9/847節(jié)點A的路由表特點最短路徑集合構(gòu)成了一棵樹最短路徑生成樹方案不唯一E.g., A-E-F-C-D 的 cost

30、也是 7AEFCDB23641113Forwarding Table for ADestCostNext HopA0AB4BC6ED7BE2EF5E2022/9/8482 計算最短路徑的方法選路算法要解決的主要問題包括：路由器之間交換哪那些信息？路由器之間如何交換信息，更新策略完成信息交換后，如何計算最佳路由？2022/9/849計算最短路徑的方法Link-state路由器之間交換鏈路狀態(tài)信息。鏈路狀態(tài)信息在網(wǎng)絡(luò)中Flooding每個節(jié)點搜集完整的網(wǎng)絡(luò)拓撲信息，依據(jù)該信息，每個節(jié)點獨立計算最短路徑，生成路由表。觸發(fā)更新。Distance-vector相鄰路由器之間直接交換整個路由表信息。每個節(jié)

31、點采用迭代方式構(gòu)造自己的路由表。定期更新和觸發(fā)更新相結(jié)合。2022/9/850鏈路狀態(tài)選路算法（LS）原理每個節(jié)點必須知道完整的網(wǎng)絡(luò)拓撲和鏈路費用每個節(jié)點通過鏈路狀態(tài)廣播（Flooding）告知所有其它節(jié)點他的身份和與他相連的鏈路的費用。每個節(jié)點根據(jù)接收到網(wǎng)絡(luò)拓撲和鏈路費用，各自獨立計算到其它節(jié)點最小費用路由集使用Dijkstra算法。在初始態(tài)，每個節(jié)點僅需知道其直接相連的的鄰居身份和鏈路費用，即可進行鏈路狀態(tài)廣播，然后通過接收其它節(jié)點的鏈路狀態(tài)廣播，最終獲得全部的網(wǎng)絡(luò)拓撲。鏈路狀態(tài)變化時更新鏈路狀態(tài)信息2022/9/851Flooding：鏈路狀態(tài)的廣播X 想發(fā)送信息則向所有輸出鏈路發(fā)送Y

32、收到來自Z的信息時向除 Z外的其它所有鏈路轉(zhuǎn)發(fā)XACBD(a)XACBD(b)XACBD(c)XACBD(d)2022/9/852Dijkstra算法初始條件給定圖的源節(jié)點s 和 邊的費用costs c(u,v)確定s到每一個點 v的最短路徑Shortest Path First Algorithm從s點開始遍歷整個圖，按照路徑長度增加的順序?qū)ふ业狡渌c的最短路徑，算法是迭代執(zhí)行的。經(jīng)過k步，找到源節(jié)點到所有k個節(jié)點的最短路徑。2022/9/853Dijkstra算法: 原理Node 集Done最短路徑已經(jīng)計算出來的節(jié)點Horizon:從Done集中的節(jié)點可直達的節(jié)點Unseen:從Done集

33、中不能直達的節(jié)點符號d(v) = 路徑費用從 s 到 vP（v）記錄路徑上的最后一條鏈路AEFCDB23631123SourceNodeDoneHorizonUnseen0253紅色表示當前 Path 費用2022/9/854Dijkstra算法: 初始步Done集中無節(jié)點源節(jié)點在 horizon集AEFCDB23631123SourceNodeDoneHorizonUnseen0紅色表示當前 Path 費用2022/9/855Dijkstra算法: 初始步d(v) ：到節(jié)點A 的d(v)用紅色標識只考慮從Done集中 節(jié)點出發(fā)的鏈路。AEFCDB23631123SourceNodeDoneH

34、orizonUnseen0263紅色表示當前 Path 費用2022/9/856Dijkstra集從horizon集中選擇一個節(jié)點 v，滿足 d(v)最小。將該節(jié)點最短路徑使用的最后一條鏈路加入到 SPT中。更新 d(v) 信息。AEFCDB23631123SourceNodeDoneHorizonUnseen023紅色表示當前 Path 費用652022/9/857Dijkstra算法重復(fù)AC23631123SourceNodeDoneHorizonUnseen0253紅色表示當前 Path 費用FBDE2022/9/858Dijkstra算法節(jié)點的增加會將新的節(jié)點加進 horizon集26

35、31123SourceNodeDoneHorizonUnseen02436紅色表示當前 Path 費用AC3DBEF2022/9/859Dijkstras Algorithm最終的SPT用綠色表示2631123SourceNode024356AC3DBEF2022/9/8604 分層選路：LS和DV算法的假設(shè)：網(wǎng)絡(luò)被抽象成一個互連路由器的集合，扁平化。所有的路由器地位平等，使用相同的選路算法。實際中的難題如何管理大規(guī)模的網(wǎng)絡(luò)？超過200百萬的目的地地址，很難管理路由表路由信息可能壓垮網(wǎng)絡(luò)如何實現(xiàn)各個網(wǎng)絡(luò)的管理上的獨立自治？Internet本身是一個網(wǎng)絡(luò)的網(wǎng)絡(luò)各機構(gòu)都希望能夠保持自己網(wǎng)絡(luò)的獨立性

36、2022/9/861Internet解決方案：分層選路Internet ： AS的集合.AS內(nèi)部使用Interior Gateway Protocols (IGPs). 路由器之間可以共享路由信息路由器使用相同的路由協(xié)議 Eg: RIP, OSPF，ISIS，PNNI等AS 之間使用 Exterior Gateway Protocols (EGPs)路由器之間不能共享全部的路由信息網(wǎng)絡(luò)之間可能配置不同的路由協(xié)議，相互之間有訪問限制等. Eg: EGP, BGP-4AS 之間通過網(wǎng)關(guān)路由器相連2022/9/862Intra-AS 選路的要求靈活適應(yīng)不同的AS規(guī)模. Low end: 10臺以下路

37、由器的網(wǎng)絡(luò) (小企業(yè))High end: 超過1000 路由器 (大型 ISP)網(wǎng)絡(luò)拓撲變化時路由的收斂速度 Low end: 能夠容忍某些連接的中斷High end: 要求盡可能快的路由收斂速度Operational/Admin/Management (OAM) ComplexityLow end: 簡單, 人工High end: 人工/自動配置.流量工程能力: 僅大型網(wǎng)絡(luò)需要2022/9/863 Inter-AS 選路的要求能夠適應(yīng)不同Internet的規(guī)模 強調(diào)可達性，而不是選路的最優(yōu)性采用地址聚集技術(shù)控制核心路由器的路由表規(guī)模，支持流量控制允許 AS之間使用policy-based 選

38、路Policy ：指可選項在選路中, 可選項包括優(yōu)先級、地址前綴，AS的級別可擴展：能夠滿足基于新策略的選路需求.2022/9/864Intra-AS 和 Inter-AS 選路網(wǎng)關(guān)A.c中的 inter-AS,和intra-AS選路 網(wǎng)絡(luò)層鏈路層物理層abbaaCABd網(wǎng)關(guān):執(zhí)行 inter-AS間的選路執(zhí)行 intra-AS 內(nèi)路由器間的選路A.cA.aC.bB.acbc2022/9/865Intra-AS 和 Inter-AS 選路: 實例主機h2abbaaCABdcA.aA.cC.bB.acb主機h1在AS A 內(nèi)Intra-AS選路A 和B 間Inter-AS選路 在AS B內(nèi)Int

39、ra-AS選路問題：在一個AS中的路由器如何將分組轉(zhuǎn)發(fā)到位于另外一個AS中的路由器？2022/9/866總結(jié): Internet 選路結(jié)構(gòu)劃分 Autonomous Systems不同的AS由不同的機構(gòu)運行管理每個路由器和鏈路都屬于單一機構(gòu)Service provider, company, university, AS的層次大型 第一層ISP運行骨干網(wǎng)（backbone）中等規(guī)模的ISP運行地區(qū)級的Backbone小型網(wǎng)絡(luò)由大學(xué)、公司等運行AS間的交互AS間彼此不共享內(nèi)部網(wǎng)絡(luò)拓撲結(jié)構(gòu) 但是, 相鄰的AS間會交換路由信息協(xié)調(diào)選路。2022/9/867七 Internet的路由協(xié)議內(nèi)部路由協(xié)議I

40、ntra-domainRIP: Routing Information Protocol（DV)OSPFv2: Open Shortest Path First(LS)（RFC2328）IS-IS（ISO）PNNI（ATM Forum）域間路由協(xié)議Inter-domainBGP (Border Gateway Protocol):2022/9/8681 內(nèi)部路由協(xié)議：OSPFOSPF的構(gòu)成由基于Flooding的LSA協(xié)議和Dijkstra算法組成鏈路權(quán)值由管理員配置(面向費用最優(yōu)）主要特點路由器要向域內(nèi)所有的其它路由器廣播路由信息。廣播分：周期廣播（30分鐘）/鏈路狀態(tài)變更廣播兩種OSPF報

41、文直接由IP分組承載（協(xié)議號89）。支持分層選路。2022/9/869 OSPF Flooding 操作傳送 link state advertisements（LSA）Link ID由在鏈路另一端的路由器ID標識Metric鏈路費用鏈路狀態(tài)的年齡每秒遞增達到3600，OSPF分組過期順序號（sequence number）每發(fā)送一次新的LSA，遞增一次。2022/9/870OSPF Flooding 操作節(jié)點 X 收到 來自Y的 LSA信息該分組的 Sequence Number q在當前鏈路狀態(tài)數(shù)據(jù)庫中查找 有相同 origin/link ID的項。處理流程數(shù)據(jù)庫中沒有該信息增加一項, 將

42、該信息廣播到除 Y以外的其它鄰居。該項數(shù)據(jù)庫中有，但sequence number p q將該項發(fā)送給 Y通知Y信息過時該項數(shù)據(jù)庫中有，但sequence number p = q忽略2022/9/871OSPF的分層邊界路由器：負責(zé)連接其它AS。執(zhí)行OSPF主干部分的選路。支持兩層選路結(jié)構(gòu)區(qū)域邊界路由器：將本區(qū)域的選路信息告知其它區(qū)域邊界路由器。2022/9/8722 BGP Border Gateway ProtocolBGPv4（RFC1771）：跨越多個AS的源和目的之間如何選路。BGP為每個AS提供如下功能：從相鄰AS獲取子網(wǎng)可達性信息向AS內(nèi)所有路由器廣播這些可達性信息基于這些可達

43、性信息和AS路由策略，決定到達其它子網(wǎng)的路由。允許一個子網(wǎng)向Internet的其余部分通告它的存在： “I am here”.通過BGP，隔離的子網(wǎng)最終互聯(lián)在一起2022/9/873BGP基礎(chǔ)兩個BGP對等方路由器之間通過TCP連接179交換交換路由信息: BGP sessions假如AS2向 AS1廣播一個網(wǎng)絡(luò)前綴, 則AS2 一定會確保 轉(zhuǎn)發(fā)任何到該前綴的數(shù)據(jù)報.AS2 可以將前綴先聚集，再轉(zhuǎn)發(fā)給AS1。3b1d3a1c2aAS3AS1AS21a2c2b1b3ceBGP sessioniBGP session2022/9/874BGP基礎(chǔ)路由器3a 和1c通過eBGP session, AS3 將可達性信息傳給 AS1.然后，1c 使用 iBGP 對話，將可達性信息分配給AS1中所有的路由器。然后，1b 再將新的可達性信息，通過 eBGP session 發(fā)布給AS2。此過程中，路由器一旦學(xué)到一個新的網(wǎng)絡(luò)前綴，, 她就在路由表中為該目的網(wǎng)絡(luò)創(chuàng)建一條路由項.3b1d3a1c2aAS3AS1AS21a2c2b1b3ceBGP sessioniBGP session2022/9/875Path 屬性和 BGP 路由一條BGP路由廣播消息包含一個前綴, 和路徑attributes. prefix + attributes = “ro