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

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

網(wǎng)絡(luò)層的服務(wù)模式：是指網(wǎng)絡(luò)在從源端到目的端轉(zhuǎn)發(fā)分組時，所提供信道的方式和服務(wù)模式的定義：

帶寬是否有保證？時延抖動是否限制？是否控制擁塞？是否保證有序傳輸？是否保證可靠傳輸？

IP采用盡力而為的服務(wù)模式

盡力而為的服務(wù)模式不保障

最大時延，重復(fù)，丟失，錯序。2022/4/34網(wǎng)絡(luò)層服務(wù)模式：比較

下表是Internet、電路交換，ATMABR服務(wù)模型的比較。網(wǎng)絡(luò)體系服務(wù)帶寬保丟失排序定時擁塞指示結(jié)構(gòu)Internet模型盡力而為CBR證無保證無無不維持維持無電路交換恒定速率最小速率是有無擁塞ATMABR是有維持提供擁塞指示2022/4/35二IPv4數(shù)據(jù)報的格式048121619242831versioHLenTOSTotalLengthnIdentifierFlagOffsetTTLProtocolHeaderChecksum20字節(jié)SourceAddressDestinationAddressOptions(ifany)Data采用無連接的數(shù)據(jù)報服務(wù)模式：每一個數(shù)據(jù)報都包含選路轉(zhuǎn)發(fā)需要的全部信息。2022/4/36參數(shù)的含義版本號：指明數(shù)據(jù)報的IP協(xié)議版本，典型值4。頭部長度：以32bit為單位的數(shù)據(jù)報頭部長度，通過它可知數(shù)據(jù)報中的數(shù)據(jù)部分從哪開始，典型值5。服務(wù)類型：提供優(yōu)先級信息（時延，可靠性）?？傞L度：以字節(jié)為單位的數(shù)據(jù)報總長度（含頭部）。實際很少超過1500字節(jié)，經(jīng)常被限制在576字節(jié)以內(nèi)。標(biāo)識符，標(biāo)志，分片偏移量主要用于分片標(biāo)識符：它是一個序號，與源地址，目的地址以及用戶協(xié)議一起唯一識別一個數(shù)據(jù)報。標(biāo)志：目前只定義了2個bit，DF（Don’tFragment）為真，則禁止分片；MF（morefragment)為假表示為原數(shù)據(jù)報中最后的一個數(shù)據(jù)報片。分片偏移量：以64bit為單位，指出該片在原數(shù)據(jù)報中的位置。DFMF2022/4/37參數(shù)的含義

生存期TTL：路由器每處理一個數(shù)據(jù)報，必須將其TTL值減1，當(dāng)TTL＝0時則丟棄分組。協(xié)議：指明目的端傳送層的協(xié)議類別。TCP=6,ICMP=1,UDP=17…頭部校驗和：該值在每一個路由器上都要進行從新計算和生成。源和目地地址：32bit的地址，指明主機和其所在網(wǎng)絡(luò)的位置?？蛇x項：允許IP頭部被擴展，但出于性能上的考慮，目前很少使用，IPV6中則完全取消。

2022/4/38三IP分組的分片:FragmentationMTU=2000hostrouterhostrouterMTU=1500MTU=4000

每個網(wǎng)絡(luò)都有自己的MTU（MaximumTransmissionUnit）。

IP解決方案：分片信源無法預(yù)先獲知所有中間網(wǎng)絡(luò)的MTU。

2022/4/39Reassembly

在哪兒重裝？

目的節(jié)點還是路由器？

目的節(jié)點

避免大分組被重復(fù)多次分片假如丟失了一片，則丟棄整個分組

中間節(jié)點重裝的潛在問題

很難確定需要多少重裝緩沖區(qū)數(shù)據(jù)報網(wǎng)絡(luò)路徑改變帶來的風(fēng)險

多條路徑的并存

網(wǎng)絡(luò)狀態(tài)的變化2022/4/310與分片相關(guān)的字段

Length

IP分片的長度

Identification

與其它分片進行匹配

Flags

Don’tfragmentflag

Morefragmentsflag

Fragmentoffset

本分片在整個分組中的位置

以64bit為計數(shù)單位(13bit長)2022/4/311IP分片例1hostrouterMTU=4000Length=3820,M=0IPIPHeaderData2022/4/312IP分片例2MTU=2000routerrouterLength=1940,M=1,Offset=0Length=3820,M=0IPIPIPIPHeaderDataHeaderData1920bytes3800bytesLength=1900,M=0,Offset=240IPIPHeaderData1880bytes2022/4/313IP分片例3Length=1460,M=1,Offset=0routerhostIPIPMTU=1500HeaderDataLength=1940,M=1,Offset=01440bytesIPIPLength=480,M=1,Offset=180HeaderDataIPIPHeaderData1920bytesLength=1460,M=1,Offset=240Length=1900,M=0,Offset=240IPIP460bytesHeaderDataLength=460,M=0,Offset=420IPIPIPIPHeaderDataHeaderData1440bytes1880bytes440bytes2022/4/314IP重裝-目的端Length=1460,M=1,Offset=0IPIP由于分片到達的順序可能是亂的HeaderData

因此最后一個分片到達前，很難確分組的實際長度。Length=480,M=1,Offset=180有些分片可能重復(fù)IPIP

只保留一個拷貝HeaderData某些分片可能丟失Length=1460,M=1,Offset=240

丟棄整個分組IPIPHeaderDataLength=460,M=0,Offset=420IPIPHeaderDataIPIPIPIPDataDataDataData2022/4/315分片和重裝的背后

展示了許多Internet設(shè)計的基本原則

Decentralized

每個網(wǎng)絡(luò)獨立選擇MTU

Connectionless

每個(fragmentof)分組包含全部的選路信息。每個分片在網(wǎng)中獨立地選路和處理

Besteffort

目的地可以放棄重裝假如重裝失敗，無需通知發(fā)送方

Complexendpointsandsimplerouters

在目的地重裝。2022/4/316思考：

當(dāng)前Internet如何控制分片的有害性？2022/4/317四IPv4編址方式

IP地址在網(wǎng)絡(luò)層上屏蔽了異種網(wǎng)絡(luò)之間物理地址的差異，利于網(wǎng)間通信的實現(xiàn)。IP地址：32bit,由網(wǎng)絡(luò)部分和主機部分組成，其中高階bit標(biāo)識網(wǎng)絡(luò)部分（網(wǎng)絡(luò)前綴），低階bit標(biāo)識主機部分。接口（Interface）：主機/路由器與物理鏈路連接器。

典型的一個路由器有多個接口，主機通常有一個接口，而一個IP地址只能用來唯一地標(biāo)識一個接口?！叭?”代表“本”，“全1”代表“全部”。點分十進制表示法：

=110111110000000100000001000000012231112022/4/318IP子網(wǎng)Fei_1/20Fei_1/11218路由器每個端口連接一個IP子網(wǎng)，172.16.12.12同一個子網(wǎng)要求接口具備相同網(wǎng)絡(luò)前綴。NetworkHost2022/4/319IPv4分類編址NetworkIDHostID8162432ClassA0NetworkIDHostIDClassB10ClassC110ClassD1110MulticastAddressesClassE1111Reservedforexperiments?總共lIP地址空間:4billion?ClassA:128networks,16Mhosts，～55?ClassB:16Knetworks,64Khosts，～55?ClassC:2Mnetworks,256hosts，2022/4/3～5520特殊IP地址與專用IP地址地址用途網(wǎng)絡(luò)指本地節(jié)點(一般為)，用于測試網(wǎng)卡及TCP/IP軟件主機地址全0用于指定網(wǎng)絡(luò)本身，稱之為網(wǎng)絡(luò)地址或者網(wǎng)絡(luò)號主機地址全1用于廣播，也稱定向廣播，需要指定目標(biāo)網(wǎng)絡(luò)RFC1918中規(guī)定如下地址是私有地址：???一個A類地址，16個B類地址－，256個C類地址－2022/4/321如何獲取網(wǎng)絡(luò)地址？

機構(gòu)通常從其ISP處獲取IP地址。ISP會從已分配給他的更大的地址塊中為用戶提供一塊地址空間.ISP本身則從全球型的權(quán)威地址管理機構(gòu)ICANN獲取地址（InternetCorporationforAssignNamesandNumbers).

RegionalInternetRegistries(RIRs)

ARIN(NorthAmerica,SouthernAfrica),APNIC(Asia-Pacific),RIPE(Europe,NorthernAfrica),LACNIC(SouthAmerica)

ICANN同時負(fù)責(zé)管理DNS根服務(wù)器，分配域名，解決域名紛爭問題。

主機如何獲取IP地址?

Hard-codedbysystemadmininafileDHCP:DynamicHostConfigurationProtocol

2022/4/322Subnet編址RFC917(1984)

原始分類地址優(yōu)缺點

地址的前綴部分說明的地址的類型，也就說明的地址的網(wǎng)絡(luò)部分長度。

選路只需要根據(jù)地址前綴部分進行即可。

例如3，代表一個B類地址，因此可確定網(wǎng)絡(luò)前綴為128.2，路由器只需要根據(jù)128.2選路轉(zhuǎn)發(fā)分組即可。

網(wǎng)絡(luò)前綴的長度固定（8/16/24).

路由表過大

C類地址有2百萬之多。2022/4/323Subnet編址RFC917(1984)

子網(wǎng)地址的需求背景

ClassA&B網(wǎng)太大

幾乎沒有一個LAN的主機數(shù)接近64k

原因既有物理電氣方面的約束，也有性能管理方面的約束。

地址分配不夠靈活，導(dǎo)致地址使用效率低，地址空間消耗速度快。

實際中需要一種簡單的方法將一個大的分類地址空間劃分為多個小的子網(wǎng)，提高地址使用效率，滿足單位的組網(wǎng)需要。2022/4/324子網(wǎng)編址

在原有的兩層地址結(jié)構(gòu)中增加了一個新層：子網(wǎng)ID。通過子網(wǎng)ID，可以將一個分類地址劃分成幾個子網(wǎng)。為識別網(wǎng)絡(luò)部分的實際長度，引入子網(wǎng)掩碼機制來確定主機和網(wǎng)絡(luò)部分的長度。子網(wǎng)掩碼的長度根據(jù)實際需要確定－意味著網(wǎng)絡(luò)前綴的長度此時已經(jīng)可變了。

NetworkHostNetworkSubnetHost11111111111111111111111100000000SubnetMask2022/4/325網(wǎng)絡(luò)Prefixes和Masks6與網(wǎng)絡(luò)前綴/15匹配610001100000001010000100100010000/15100011000000010000000000000000000000000000000000掩碼11111111111111106100011000000011100001001000100006與網(wǎng)絡(luò)前綴/15不匹配2022/4/326子網(wǎng)劃分的例子

假設(shè)某公司有一B類地址/16，有4個部門A，B，C，D，每個部門250臺機器。/24/16AInternet網(wǎng)關(guān)路由器/24B/24C/24D2022/4/327ClasslessInter-domainRouting(CIDR)

傳統(tǒng)分類IP地址的缺點不夠靈活，A，B類地址對大多數(shù)機構(gòu)太大，但C地址又太小。舉例如下：某機構(gòu)擁有約2000臺主機，要構(gòu)建一個網(wǎng)絡(luò)，采用分類地址方案，則一個C類網(wǎng)絡(luò)地址太小，而分配一個B可解決問題，但地址空間的利用率又太低。

實際建網(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/4/328CIDR型地址的特點

IETF在1993【rfc1519】將其標(biāo)準(zhǔn)化,對子網(wǎng)概念的進一步擴展。

CIDR型IP地址的網(wǎng)絡(luò)部分可以任意長：

不使用類型標(biāo)識來確定網(wǎng)絡(luò)部分的長度。使用地址塊的公共部分做為網(wǎng)絡(luò)前綴。

CIDR型的網(wǎng)絡(luò)地址必須采用形式a.b.c.d/x表示,其中x表示32bit的地址中，前xbit為網(wǎng)絡(luò)部分。

分配給同一機構(gòu)的地址空間必須保持連續(xù)（2的冪次）以實現(xiàn)地址聚集。2022/4/329C類地址的分區(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分則為11位，最多標(biāo)識2048臺，滿足設(shè)計要求。，這樣地址的公共部分為21位，主機部2022/4/330實例1例如：假設(shè)某機構(gòu)已分配了地址塊202.23.0.X～202.23.7.X(8個連續(xù)的C類地址）.其下有八個機構(gòu)，ISP可將該塊地址均分為八份，如下圖所示：ISP地址塊11001010000101110000000000000000/21機構(gòu)011001010000101110000000000000000/24機構(gòu)111001010000101110000000100000000/24機構(gòu)211001010000101110000001000000000/24...…..….….機構(gòu)711001010000101110000011100000000/24子網(wǎng)地址擴展占3bit,主機部分剩余8bit2022/4/331CIDR下的分層選路與地址聚集ISP…...…….routerInternet…...……./24/24/24ISP…...……./24/21Internetrouter使用和不使用CIDR的域間選路區(qū)別2022/4/332CIDR的最長前綴匹配Destination=6-------------------------------payloadPrefixNextHopInterfaceOK/03ATM5/0/9better/89ATM5/0/8/157Ethernet0/1/3best!/23attachedSerial1/0/7IPForwardingTable2022/4/333變長子網(wǎng)掩碼－VariableLengthSubnetMasking(VLSM)2/27A172.16.14.64/27Bcenter6/27C

當(dāng)一個網(wǎng)絡(luò)包含多個子網(wǎng)，且子網(wǎng)的大小不同，則可以使用VLSM。

這樣避免了IP地址的浪費，但需要路由協(xié)議支持2022/4/334五路由器的一般結(jié)構(gòu)－控制平面

路由功能：執(zhí)行路由協(xié)議，生成、更新和維護路由表。

其它功能：擁塞控制，QoSProtocolsControlForwarding等。Table

路由表的基本信息erfaceerface

目的網(wǎng)絡(luò)地址。路由信息的來源。下一跳的IP地址轉(zhuǎn)發(fā)端口

Inter-

connection

Medium(Backplane)2022/4/335控制平面：路由表GAR#showiprouteIPv4RoutingTable:DestMaskGwInterfaceOwnerprimetricfei_1/1bgp20005355fei_1/1ospf110145455fei_1/1ospf1101348gei_5/2.1direct0055gei_5/2.1address004486gei_5/2.4direct0052fei_1/1direct0055fei_1/1address002022/4/336五路由器的一般結(jié)構(gòu)-轉(zhuǎn)發(fā)平面

Ierfaces:Control

必須執(zhí)行分組轉(zhuǎn)發(fā)－確定轉(zhuǎn)發(fā)到哪一個出接口。執(zhí)行分組排隊，分類，標(biāo)記ProtocolsForwardingTable

erfaceerface

Oerfaces:

執(zhí)行分組排隊和分組調(diào)度。connectionInter-

Backplane：互連出口與Medium入口。(Backplane)2022/4/337源端主機IP分組轉(zhuǎn)發(fā)流程獲取目的IP地址判斷YES檢查YES做數(shù)據(jù)鏈路層封裝與目的端是否處于同一ARP表是否有目的端網(wǎng)段MAC地址（目的MACMAC地址為）目的端NONO通過ARP獲得通過物理層目的端MAC地址發(fā)送數(shù)據(jù)是否配置了缺省網(wǎng)關(guān)？YES檢查YES做數(shù)據(jù)鏈路層封裝ARP表是否有網(wǎng)關(guān)MAC地址（目的關(guān)MACMAC地址）為網(wǎng)NONOEnd發(fā)送錯誤信息通過ARP獲得網(wǎng)關(guān)MAC地址2022/4/338同一網(wǎng)段通信過程圖示AB網(wǎng)絡(luò)情況IP地址：MAC地址：00:20:AF:00:00:01IP地址：MAC地址：00:20:AF:00:00:02協(xié)議層次IP層包發(fā)往封裝IPIP包地址拆封IP包收到IP包IP層ARP以太網(wǎng)封裝MAC幀封裝MAC幀收到MAC幀以太網(wǎng)幀發(fā)往MAC地址00:20:AF:00:00:022022/4/339不同網(wǎng)段的通信過程網(wǎng)絡(luò)情況PPPEthernetEthernetHOSTAfei-1/1e1_2/1e1_2/1fei-1/1HOSTB協(xié)議層次IP層IP包IP包IP層IP包IP包IP層IP包IP包IP層以太網(wǎng)串行接口串行接口以太網(wǎng)以太網(wǎng)MAC幀接口PPP幀接口MAC幀以太網(wǎng)發(fā)送端路由器路由器接收端主機A主機BPPP分組2022/4/340ARP工作機制我需要IP地址為主機的物理地址IP:=???

作用：隱藏底層網(wǎng)絡(luò)物理地址，以允許給每臺主機分配任意IP地址

組成：1)發(fā)送數(shù)據(jù)時，實現(xiàn)IP地址向MAC地址的映射2)回答其它機器的ARP請求。2022/4/341ARP工作過程我需要IP地址為主機的物理地址我聽到廣播包了，這條消息是給我的這是我的物理地址.，IP:=???IP:Ethernet:0800.0020.11112022/4/342你發(fā)現(xiàn)了什么？回憶異構(gòu)網(wǎng)互聯(lián)的原理每個host/Router上兩張表報文路由表ARP表根據(jù)目的－IP確根據(jù)下一跳路由TCPUDP定：器IP地址確定：段Routing1）下一跳路由1）下一跳路由器TableIP器得IP地址。得數(shù)鏈層地址。數(shù)據(jù)報ARPTable2）輸出端口號EthernetDriverdatagraminDatagramout以太幀路由表ARP表節(jié)點2022/4/343IP地址與轉(zhuǎn)發(fā)的總結(jié)

IP地址

IP地址實際對應(yīng)的是一個網(wǎng)絡(luò)Interface。

分類IP地址(A,B,C)的地址分配效率很低，運營商和大型園區(qū)網(wǎng)都不使用。

CIDR(Supernet)主要用途是將一組連續(xù)的C類地址進行聚集，而子網(wǎng)的用途則是將一個分類地址進行細(xì)分。

轉(zhuǎn)發(fā)：

路由器總是基于IP地址選路，然后用物理地址完成封裝的轉(zhuǎn)發(fā)。

路由器和主機上總是運行了兩個網(wǎng)絡(luò)層協(xié)議，IP扮演邏輯網(wǎng)絡(luò)協(xié)議，物理網(wǎng)絡(luò)協(xié)議則扮演了數(shù)鏈層的角色。2022/4/344六選路算法：原理

關(guān)于Internet，我們已知…

IP地址的結(jié)構(gòu)反映了Internet的結(jié)構(gòu)

IP分組頭負(fù)責(zé)運載IP地址信息

當(dāng)分組到達路由器：Router

檢查頭部尋找分組中攜帶目的地IP地址

查路由表確定到目的地的下一跳地址

通過指定的端口轉(zhuǎn)發(fā)分組

問題：

路由器如何產(chǎn)生、維護路由表？

如何確保不同路由器上路由表數(shù)據(jù)的一致性？

運營商如何控制鏈路上的負(fù)載？2022/4/345原理：網(wǎng)絡(luò)的建模網(wǎng)絡(luò)中的每臺router用一個節(jié)點來表示。路由器之間的直連鏈路用邊表示。

Symmetriclinksundirectedgraph邊的“cost”c(x,y)表示鏈路的成本度量值

delay,$cost,orcongestion級別任務(wù)

計算每一個頂點到任意其它頂點的最小成本路徑

Pathcostd(x,y)=路徑上所有鏈路成本之和E31C2F161A43D2022/4/3B46節(jié)點A的路由表ForwardingTableforAE31CDestCostNext1Hop2FABCDEF046725ABEBEE61A43DB特點

最短路徑集合構(gòu)成了一棵樹

最短路徑生成樹

方案不唯一

E.g.,A-E-F-C-D的cost也是72022/4/3472計算最短路徑的方法選路算法要解決的主要問題包括：路由器之間交換哪那些信息？路由器之間如何交換信息，更新策略完成信息交換后，如何計算最佳路由？2022/4/348計算最短路徑的方法

Link-state

路由器之間交換鏈路狀態(tài)信息。鏈路狀態(tài)信息在網(wǎng)絡(luò)中Flooding每個節(jié)點搜集完整的網(wǎng)絡(luò)拓?fù)湫畔?，依?jù)該信息，每個節(jié)點獨立計算最短路徑，生成路由表。觸發(fā)更新。

Distance-vector

相鄰路由器之間直接交換整個路由表信息。每個節(jié)點采用迭代方式構(gòu)造自己的路由表。定期更新和觸發(fā)更新相結(jié)合。2022/4/349鏈路狀態(tài)選路算法（LS）

原理

每個節(jié)點必須知道完整的網(wǎng)絡(luò)拓?fù)浜玩溌焚M用

每個節(jié)點通過鏈路狀態(tài)廣播（Flooding）告知所有其它節(jié)點他的身份和與他相連的鏈路的費用。

每個節(jié)點根據(jù)接收到網(wǎng)絡(luò)拓?fù)浜玩溌焚M用，各自獨立計算到其它節(jié)點最小費用路由集

使用Dijkstra算法。

在初始態(tài)，每個節(jié)點僅需知道其直接相連的的鄰居身份和鏈路費用，即可進行鏈路狀態(tài)廣播，然后通過接收其它節(jié)點的鏈路狀態(tài)廣播，最終獲得全部的網(wǎng)絡(luò)拓?fù)洹?/p>

鏈路狀態(tài)變化時更新鏈路狀態(tài)信息2022/4/350Flooding：鏈路狀態(tài)的廣播X想發(fā)送信息XAXA

則向所有輸出鏈路發(fā)CBDCBD送(a)(b)Y收到來自Z的信息時

向除Z外的其它所有鏈XAXA路轉(zhuǎn)發(fā)CBDCBD(c)(d)2022/4/351Dijkstra’算法

初始條件

給定圖的源節(jié)點s和邊的費用costsc(u,v)

確定s到每一個點v的最短路徑

ShortestPathFirstAlgorithm

從s點開始遍歷整個圖，按照路徑長度增加的順序?qū)ふ业狡渌c的最短路徑，算法是迭代執(zhí)行的。經(jīng)過k步，找到源節(jié)點到所有k個節(jié)點的最短路徑。2022/4/352Dijkstra算法:原理2EC

3512紅色表示當(dāng)前Path費用2F6SourceNode01

A333DDoneBUnseenHorizon

Node集

Done

符號

最短路徑已經(jīng)計算出來的節(jié)點

d(v)=路徑費用

Horizon:

從s到v

從Done集中的節(jié)點可直達的節(jié)點

P（v）

Unseen:

記錄路徑上的最后一條鏈路

從Done集中不能直達的節(jié)點2022/4/353Dijkstra算法:初始步

EC

3

12紅色表示當(dāng)前Path費用2F6SourceNode01

A3

3DHorizonBDoneUnseen

Done集中無節(jié)點

源節(jié)點在horizon集2022/4/354Dijkstra’算法:初始步2EC

3612紅色表示當(dāng)前Path費用2F6SourceNode01

A333DDoneBHorizonUnseen

d(v)：到節(jié)點A的d(v)用紅色標(biāo)識

只考慮從Done集中節(jié)點出發(fā)的鏈路。2022/4/355Dijkstra集2EC

35612紅色表示當(dāng)前Path費用2F6SourceNode01

A333DDoneBUnseenHorizon

從horizon集中選擇一個節(jié)點v，滿足d(v)最小。

將該節(jié)點最短路徑使用的最后一條鏈路加入到SPT中。

更新d(v)信息。2022/4/356Dijkstra算法2EHorizonC

3512紅色表示當(dāng)前Path費用2F6SourceNode01

A333DDoneBUnseen

重復(fù)……2022/4/357Dijkstra算法

Unseen2E341C2紅色表示當(dāng)前Path費用2F6SourceNode016A333DBHorizonDone

節(jié)點的增加會將新的節(jié)點加進horizon集2022/4/358Dijkstra’sAlgorithm2EC53412F26SourceNode016A333DB

最終的SPT用綠色表示2022/4/3594分層選路：

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ò)的獨立性2022/4/360Internet解決方案：分層選路

Internet：AS的集合.

AS內(nèi)部使用InteriorGatewayProtocols(IGPs).

路由器之間可以共享路由信息

路由器使用相同的路由協(xié)議Eg:RIP,OSPF，IS－IS，PNNI等

AS之間使用ExteriorGatewayProtocols(EGPs)

路由器之間不能共享全部的路由信息

網(wǎng)絡(luò)之間可能配置不同的路由協(xié)議，相互之間有訪問限制等.Eg:EGP,BGP-4

AS之間通過網(wǎng)關(guān)路由器相連2022/4/361Intra-AS選路的要求

靈活適應(yīng)不同的AS規(guī)模.

Lowend:10臺以下路由器的網(wǎng)絡(luò)(小企業(yè))Highend:超過1000路由器(大型ISP)

網(wǎng)絡(luò)拓?fù)渥兓瘯r路由的收斂速度Lowend:能夠容忍某些連接的中斷

Highend:要求盡可能快的路由收斂速度

Operational/Admin/Management(OAM)Complexity

Lowend:簡單,人工Highend:人工/自動配置.

流量工程能力:僅大型網(wǎng)絡(luò)需要2022/4/362Inter-AS選路的要求

能夠適應(yīng)不同Internet的規(guī)模

強調(diào)可達性，而不是選路的最優(yōu)性

采用地址聚集技術(shù)控制核心路由器的路由表規(guī)模，支持流量控制

允許AS之間使用policy-based選路

Policy：指可選項

在選路中,可選項包括優(yōu)先級、地址前綴，AS的級別

可擴展：能夠滿足基于新策略的選路需求.2022/4/363Intra-AS和Inter-AS選路C.b網(wǎng)關(guān):B.a?執(zhí)行inter-AS間的選路?執(zhí)行intra-AS內(nèi)路由器間的選路A.abA.ccaCabaBdcAb網(wǎng)絡(luò)層網(wǎng)關(guān)A.c中的inter-AS,和intra-AS選路鏈路層物理層2022/4/364Intra-AS和Inter-AS選路:實例A和B間C.bInter-AS選路B.aA.a主機h2bA.ccaCabaB主機h1dc在ASB內(nèi)Intra-AS選路Ab在ASA內(nèi)Intra-AS選路問題：在一個AS中的路由器如何將分組轉(zhuǎn)發(fā)到位于另外一個AS中的路由器？2022/4/365總結(jié):Internet選路結(jié)構(gòu)

劃分AutonomousSystems

不同的AS由不同的機構(gòu)運行管理每個路由器和鏈路都屬于單一機構(gòu)Svider,company,university,…

AS的層次

大型第一層ISP運行骨干網(wǎng)（backbone）中等規(guī)模的ISP運行地區(qū)級的Backbone小型網(wǎng)絡(luò)由大學(xué)、公司等運行

AS間的交互

AS間彼此不共享內(nèi)部網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)…但是,相鄰的AS間會交換路由信息協(xié)調(diào)選路。

2022/4/366七Internet的路由協(xié)議

內(nèi)部路由協(xié)議Intra-domain

RIP:RoutingInformationProtocol（DV)OSPFv2:OpenShortestPathFirst(LS)（RFC2328）

IS-IS（ISO）PNNI（ATMForum）

域間路由協(xié)議Inter-domain

BGP(BorderGatewayProtocol):2022/4/3671內(nèi)部路由協(xié)議：OSPF

OSPF的構(gòu)成

由基于Flooding的LSA協(xié)議和Dijkstra算法組成

鏈路權(quán)值由管理員配置(面向費用最優(yōu)）

主要特點

路由器要向域內(nèi)所有的其它路由器廣播路由信息。

廣播分：周期廣播（30分鐘）/鏈路狀態(tài)變更廣播兩種

OSPF報文直接由IP分組承載（協(xié)議號＝89）。

支持分層選路。2022/4/368OSPFFlooding操作傳送linkstateadvertisements（LSA）

LinkID

由在鏈路另一端的路由器ID標(biāo)識

Metric

鏈路費用

鏈路狀態(tài)的年齡

每秒遞增

達到3600，OSPF分組過期

順序號（sequencenumber）

每發(fā)送一次新的LSA，遞增一次。2022/4/369OSPFFlooding操作節(jié)點X收到來自Y的LSA信息

該分組的SequenceNumber＝q在當(dāng)前鏈路狀態(tài)數(shù)據(jù)庫中查找有相同origin/linkID的項。

處理流程

數(shù)據(jù)庫中沒有該信息

增加一項,將該信息廣播到除Y以外的其它鄰居。

該項數(shù)據(jù)庫中有，但sequencenumberp<q

更新項,將該信息廣播到除Y以外的其它鄰居。

該項數(shù)據(jù)庫中有，但sequencenumberp>q

將該項發(fā)送給Y

通知Y信息過時

該項數(shù)據(jù)庫中有，但sequencenumberp=q

忽略2022/4/370OSPF的分層

支持兩層選路結(jié)構(gòu)區(qū)域邊界路由器：將本區(qū)域的選路信息告知其它區(qū)域邊界路由器。

邊界路由器：負(fù)責(zé)連接其它AS。執(zhí)行OSPF主干部分的選路。

2022/4/3712BGPBorderGatewayProtocol

BGPv4（RFC1771）：跨越多個AS的源和目的之間如何選路。

BGP為每個AS提供如下功能：

從相鄰AS獲取子網(wǎng)可達性信息向AS內(nèi)所有路由器廣播這些可達性信息基于這些可達性信息和AS路由策略，決定到達其它子網(wǎng)的路由。

允許一個子網(wǎng)向Internet的其余部分通告它的存在：“Iamhere”.

通過BGP，隔離的子網(wǎng)最終互聯(lián)在一起2022/4/372BGP基礎(chǔ)

兩個BGP對等方路由器之間通過TCP連接179交換交換路由信息:BGPsessions

假如AS2向AS1廣播一個網(wǎng)絡(luò)前綴,則AS2一定會確保轉(zhuǎn)發(fā)任何到該前綴的數(shù)據(jù)報.

AS2可以將前綴先聚集，再轉(zhuǎn)發(fā)給AS1。3c3a2c3bAS32a2b1cAS21a1bAS11deBGPsession2022/4/3iBGPsession73BGP基礎(chǔ)

路由器