計算機網絡第四章網絡層

1第四章網絡層Chapter4NetworkLayerComputerNetworking

ATop-DownApproach2本章要求重點掌握轉發(fā)和選路、虛電路和數據報網絡、路由器工作原理、網際協(xié)議：因特網中的轉發(fā)和編址、選路算法、因特網中的選路；一般掌握網絡服務模型、ICMP和IPv6；了解廣播和多播。3第四章:網絡層本章目標:

理解網絡層主要服務:選路(路徑選擇)路由器工作原理因特網上的實例及具體操作4

第四章:網絡層4.1概述4.2虛電路和數據報網絡4.3路由器工作原理4.4網際協(xié)議數據報格式IPv4編址ICMP協(xié)議IPv64.5選路算法鏈路狀態(tài)選路算法距離向量算法層次選路4.6因特網中的選路RIPOSPFBGP4.7廣播和多播選路5網絡層將分組從發(fā)送方主機傳送到接收方主機發(fā)送方將運輸層數據段封裝成分組接收方將分組解封裝后將數據段遞交給運輸層網絡層協(xié)議存在于每臺主機和路由器上路由器檢查所有經過它的IP分組的分組頭networkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalapplicationtransportnetworkdatalinkphysicalapplicationtransportnetworkdatalinkphysical6網絡層的重要功能轉發(fā)（Forwarding）

Whenapacketarrivesatarouter’sinputlink,theroutermustmovethepackettotheappropriateoutputlink選路（Routing）Determinetherouteorpathtakenbypacketsastheyflowfromasendertoareceiver選路算法（routingalgorithm）注意：轉發(fā)是路由器本地的鏈路端口選擇動作，選路是更廣的網絡范圍路徑選擇。71230111到達分組的首部中的值選路算法

本地轉發(fā)表首部值輸出鏈路010001010111100132214.1.1轉發(fā)和選路選路算法決定轉發(fā)表中的值8網絡層的第三種功能：連接建立連接建立只存在于某些網絡體系結構上，比如，ATM,幀中繼,X.25在網絡數據開始流動之前,在源和目的端需要建立虛連接路徑包括中間經過的路由器網絡層和運輸層提供的服務對比:網絡層：兩臺主機（host）之間運輸層：兩個進程（process）之間94.1.2網絡服務模型問題:網絡層應該提供哪些可能服務呢？一、網絡層為單個數據分組(apacket)提供的服務:確保交付：確保分組到達目的地具有時延上界的確保交付：比如100ms內到達二、網絡層為分組的流(aflowofpackets)提供的服務：有序分組遞交確保最小帶寬確保最大時延抖動安全性服務因特網只提供了盡力而為的服務（best-effortservice）（實際上就是沒有提供任何特定的服務）10網絡層服務模型比較：網絡體系結構InternetATMATM服務模型盡力而為CBRABR帶寬保證無恒定速率保證最小速率無丟包保證無是無排序任何可能順序有序有序定時不維持維持不維持擁塞指示無無擁塞提供擁塞指示服務質量CBR:恒定比特率ATM網絡服務ABR:可用比特率ATM網絡服務11第四章網絡層4.1概述4.2虛電路和數據報網絡4.3路由器工作原理4.4網際協(xié)議數據報格式IPv4編址ICMP協(xié)議IPv64.5選路算法鏈路狀態(tài)選路算法距離向量算法層次選路4.6因特網中的選路RIPOSPFBGP4.7廣播和多播選路12網絡層有連接服務和無連接服務數據報網絡在網絡層中提供無連接服務虛電路在網絡層中提供有連接服務與運輸層服務有相似之處，但也有很大不同：服務:主機到主機（運輸層：進程到進程）服務選擇:網絡層僅提供以上有連接或無連接服務中的一種（運輸層：可同時提供TCP和UDP）實現(xiàn):在端系統(tǒng)及網絡核心同時實現(xiàn)（運輸層：只在端系統(tǒng)中實現(xiàn)）134.2.1虛電路(VirtualCircuit)數據傳輸前建立虛電路，傳輸完畢后拆除虛電路每個分組攜帶VC標識(并非目的地址)在源-目的路徑上每個路由器要維護每個連結的狀態(tài)信息鏈路、路由器資源（帶寬、緩沖區(qū)）可能分配給VCVC是源端到目的端的路徑，正如普通電話線路性能可靠網絡行為沿網絡路徑發(fā)生14VC實現(xiàn)一條VC的組成:源和目的主機間的路徑VC號,沿著該路徑中的每段鏈路一個號碼沿著該路徑的每臺路由器中的轉發(fā)表項VC上傳送的分組攜帶有VC號每臺中間路由器用一個新的VC號取代原來的VC號新的VC號從轉發(fā)表中獲得15轉發(fā)表122232123VC號接口標號入接口入口VC#出接口出口VC#11232226311837217197387…………路由器的轉發(fā)表

路由器維護連接狀態(tài)信息16虛電路:信令協(xié)議用來建立，維護及拆除虛電路在ATM,幀中繼frame-relay,X.25中應用applicationtransportnetworkdatalinkphysicalapplicationtransportnetworkdatalinkphysical1.Initiatecall2.incomingcall3.Acceptcall4.Callconnected5.Dataflowbegins6.Receivedata174.2.2數據報網絡(Datagram)網絡層：沒有呼叫建立路由器：對于端到端的連接無需維護狀態(tài)信息分組使用目的主機地址進行轉發(fā)applicationtransportnetworkdatalinkphysicalapplicationtransportnetworkdatalinkphysical1.Senddata2.Receivedata查詢轉發(fā)表18轉發(fā)表有超過40億IP地址，轉發(fā)表就需要40億項嗎？目的地址范圍鏈路接口11001000000101110001000000000000到11001000000101110001011111111111011001000000101110001100000000000到11001000000101110001100011111111111001000000101110001100100000000到110010000001011100011111111111112其他3利用目的地址的前綴（prefix），轉發(fā)表只需要4個表項19最長前綴匹配

前綴匹配

鏈路接口

110010000001011100010011001000000101110001100011100100000010111000112

其他3目的地址:11001000000101110001100010101010

Examples:目的地址:11001000000101110001011010100001哪個接口?哪個接口?204.2.3數據報和虛電路網絡的由來

數據報：Internet由互聯(lián)計算機的需求發(fā)展來數據在計算機中進行交換，沒有嚴格的時間限制

”智能“終端系統(tǒng)

(computers)具有適應性，性能控制，錯誤恢復網絡內部簡單，終端復雜多種鏈路類型（衛(wèi)星，以太網光纖，無線等）具有不同特性統(tǒng)一服務困難虛電路：ATM由電話系統(tǒng)演變而來人類會話:嚴格的時間和可靠性要求需要有保障的服務啞終端系統(tǒng)電話網絡內部復雜21

第四章:網絡層4.1概述4.2虛電路和數據報網絡4.3路由器工作原理4.4網際協(xié)議數據報格式IPv4編址ICMP協(xié)議IPv64.5選路算法鏈路狀態(tài)選路算法距離向量算法層次選路4.6因特網中的選路RIPOSPFBGP4.7廣播和多播選路22路由器結構概要主要功能:

選路：運行路由算法/協(xié)議(RIP,OSPF,BGP)轉發(fā)：將分組從輸入鏈路轉發(fā)到適當的輸出鏈路體系結構：234.3.1輸入端口功能分散式轉發(fā):

根據分組中的目的地址,在輸入端口的緩存中查找轉發(fā)表得出適當的輸出端口目標:輸入端口的處理速度（查詢轉發(fā)表時間）能夠達到線路速度（linespeed，接收分組速度）排隊:若其他輸入端口的分組正在使用交換結構，則分組會阻塞并排隊等待調度物理層:bit接收數據鏈路層：以太網24輸入端口排隊原因：當交換速度比所有輸入端口的組合速度慢時，輸入端口產生排隊線路前部（Head-of-the-Line，HOL）阻塞：隊列前面的分組阻止其后的分組的交換到輸出端口排隊延遲：輸入隊列排隊導致延遲，緩存溢出將引起分組丟失！254.3.2三種類型的交換結構(1)內存交換(2)總線交換(3)互聯(lián)網絡交換26（1）內存交換第一代路由器:

傳統(tǒng)的計算機，交換在CPU的直接控制下完成分組被拷貝到系統(tǒng)內存速度受內存帶寬限制

(每個分組需要兩次經過總線)InputPortOutputPortMemorySystemBus許多現(xiàn)代路由器也通過內存交換:

輸入端口處理器處理分組地址查找,拷貝到輸出端口的緩沖區(qū)，如同共享內存的多處理器例：CiscoCatalyst850027（2）總線交換分組從輸入端口緩存經過一根共享總線到達輸出端口緩存總線競爭:交換速率受總線帶寬限制例：Cisco5600，32Gbpsbus

對于接入和企業(yè)路由器來說速度足夠，但不用于地區(qū)和骨干網28（3）互聯(lián)網絡交換克服總線帶寬限制，使用更加復雜的互聯(lián)網絡交換由2n條總線組成的互聯(lián)網絡，將n個輸入端口與n個輸出端口連接例：Cisco12000:通過內部互連網絡,提供60Gbps的傳輸速率高級設計趨勢:IP數據報分割成固定長度信元,通過互連網絡來交換信元.可簡化并加快分組交換294.3.3輸出端口緩存：當分組從交換結構到達的速率快于輸出鏈路速率時,需要緩存調度：在等待傳輸的排隊分組中進行選擇發(fā)送，比如FCFS30輸出端口排隊原因：當分組從交換結構到達的速率快于輸出鏈路速率時,需要緩存排隊傳輸排隊延遲：排隊造成延遲，輸出端口緩沖區(qū)溢出時引起分組丟失31

第四章:網絡層4.1概述4.2虛電路和數據報網絡4.3路由器工作原理4.4網際協(xié)議數據報格式IPv4編址ICMP協(xié)議IPv64.5選路算法鏈路狀態(tài)選路算法距離向量算法層次選路4.6因特網中的選路RIPOSPFBGP4.7廣播和多播選路32Internet網絡層轉發(fā)表網絡層功能：路由協(xié)議路徑選擇RIP,OSPF,BGPIP協(xié)議地址轉換數據報格式包處理規(guī)則ICMP協(xié)議差錯報告路由器信令”Transportlayer:TCP,UDP鏈路層物理層網絡層33

第四章:網絡層4.1概述4.2虛電路和數據報網絡4.3路由器工作原理4.4網際協(xié)議數據報格式IPv4編址ICMP協(xié)議IPv64.5算法鏈路狀態(tài)選路算法距離向量算法層次選路4.6因特網中的選路RIPOSPFBGP4.7廣播和多播選路344.4.1IP數據報格式verlength32bitsdata(變長,典型地是一個TCP或者UDP數據段)16-bitidentifierHeaderInternetchecksumtimetolive32bit源IP地址IP協(xié)議版本號首部長度(bytes)TTL,余留跳數(在每個路由器上減一)標識、標志、片偏移，用于分片/重組總長度(bytes)傳輸負載的上層協(xié)議head.lentypeofservice服務類型flgsfragmentoffsetupperlayer32bit目的IP地址選項(如果需要的話)如時間戳,規(guī)定路由器列表等首部校驗和35IP數據報分片鏈路層協(xié)議能承載的網絡層分組長度是有限制的比如，以太網不超過1500字節(jié)，廣域網不超過576字節(jié)最大傳輸單元(MTU):網絡鏈路層能承載的最大數據量不同的鏈路類型有不同的MTUs若某鏈路的MTU比IP數據報的長度小該怎么辦呢？分片36IP分片&重組分片：大的IP數據報由路由器劃分成幾個小的數據報重組:小的分片數據報在端系統(tǒng)中重新組裝分片:in:大數據報out:3個更小的數據重組IP首部的標識、標志和片偏移實現(xiàn)數據報重組37例：ID=xoffset=0fragflag=0length=4000ID=xoffset=0fragflag=1length=1500ID=xoffset=185fragflag=1length=1500ID=xoffset=370fragflag=0length=1040（1）IP數據報：4000byte數據報

=20字節(jié)IP頭+3980字節(jié)負載數據（2）某鏈路MTU=1500bytes其中數據域長度1480bytes偏移量=1480/8IP數據報：分片其中數據域長度1480bytes其中數據域長度1020bytes偏移量=2960/8最后一片38

第四章:網絡層4.1概述4.2虛電路和數據報網絡4.3路由器工作原理4.4網際協(xié)議數據報格式IPv4編址ICMP協(xié)議IPv64.5選路算法鏈路狀態(tài)選路算法距離向量算法層次選路4.6因特網中的選路RIPOSPFBGP4.7廣播和多播選路39IP地址IP地址有兩種IPV4和IPV6IPV4協(xié)議地址：32位二進制位長（四字節(jié)），常用點分十進制表示例：192.168.0.1IPV6協(xié)議地址：128位二進制位長（十六字節(jié)），常用冒號十六進制表示例：69DC:8864:FFFF:FFFF:0:1280:8C0A:FFFFIP協(xié)議劃分：第一部分指定網絡地址，第二部分指定主機地址網絡號主機號40接口接口:

主機/路由器與物理鏈路之間的邊界路由器常有多個接口主機通常有1個接口IP地址與接口相關聯(lián)223.1.1.1223.1.1.2223.1.1.3223.1.1.4223.1.2.9223.1.2.2223.1.2.1223.1.3.2223.1.3.1223.1.3.27223.1.1.1=1101111100000001000000010000000122311141互聯(lián)網中的IP地址同一局域網上的主機或路由器的IP地址中的網絡號必須相同交換機互連的網絡仍然是一個局域網，只能有一個網絡號路由器總是具有兩個或兩個以上IP地址。當兩個路由器直接相連時，在連線兩端的接口處，可以指明IP地址也可以不指明IP地址。42IP地址分類：早期0A類地址：網絡號8位主機號24位10B類地址：網絡號16位主機號16位110C類地址：網絡號24位主機號8位431110組播地址D類地址：E類地址：11110保留為今后使用44A類地址A類地址主要為大型網絡設計利用IP地址的第一個字節(jié)作為網絡地址，最高位為0，其余的三個字節(jié)作為主機地址地址范圍為1.0.0.1－127.255.255.254注:(1)全0表示網絡本地地址，全1表示在本地網絡中向所有主機廣播(2)127是個特殊的IP地址類，表示主機本身，用于本地機器上的測試和進程間的通信0網絡號8位主機號24位45B類地址B類地址利用IP地址的前兩個字節(jié)作為網絡地址，最高位為10，其余的兩個字節(jié)作為主機地址地址范圍為128.0.0.1－191.255.255.25410網絡號16位主機號16位46C類地址C類地址利用IP地址的前三個字節(jié)作為網絡地址，最高位為110，最后一個字節(jié)作為主機地址地址范圍為192.0.0.1－223.255.255.254

注：

192.168.0.0－192.168.255.254一般用于獨立的局域網，在Internet不能進行路由110網絡號24位主機號8位47劃分子網一個擁有多個物理網絡的單位可以劃分為若干子網劃分子網的方法是從主機號借用若干個比特作為子網號，剩下的主機位為主機號。網絡號子網號主機號48子網掩碼檢測IP地址前幾位可確定網絡號子網號字段長度是可變的為了確定子網地址，IP協(xié)議提供了子網掩碼的概念子網掩碼用來確定網絡地址（包括網絡號和子網號）和主機地址的長度子網掩碼中的1對應于IP地址中的網絡號和子網號，而子網掩碼中的0對應于主機號49子網及子網掩碼練習：現(xiàn)有一C類網202.115.1.1－202.115.1.254(1)請寫出怎樣將這個C類網劃分為2個、6個、14個子網；(2)現(xiàn)有一部門有30臺機器應該怎樣劃分子網？(3)如果有29臺機器又將怎樣劃分？50使用子網掩碼的分組轉發(fā)不劃分子網時，路由表只有兩項：（目的網絡地址，下一跳地址）使用子網劃分后，路由表中將包括三項：（目的網絡地址，子網掩碼，下一跳地址）51目的網絡地址子網掩碼下一跳128.30.33.0255.255.255.128接口0128.30.33.128255.255.255.128接口1128.30.36.0255.255.255.0R2R1路由表52223.1.1.1223.1.1.3223.1.1.4223.1.2.2223.1.2.1223.1.2.6223.1.3.2223.1.3.1223.1.3.27223.1.1.2223.1.7.0223.1.7.1223.1.8.0223.1.8.1223.1.9.1223.1.9.2由主機和網絡接口構成了一個個的子網，可看成是分離的網絡島例：6個子網或網絡島53IP地址分類：無分類編址CIDR早期：分類編址（classfuladdressing）-地址空間利用率地

A、B、C、D、E類網絡后來：子網（subnet）-可提高地址空間利用率最新：無類別域間選路(ClasslessInter-DomainRouting，CIDR)–

將子網尋址一般化CIDR的地址格式為：網絡前綴主機號54使用斜線記法，又稱為CIDR記法在IP地址后面加上一個斜線“/”，斜線后面用一個數字指定網絡前綴的長度，形式：a.b.c.d/xCIDR消除了傳統(tǒng)的A類、B類和C類地址以及劃分子網的概念CIDR11001000000101110001000000000000subnetparthostpart200.23.16.0/2355IP地址:怎樣獲取?問:

主機如何得到IP地址?組織外：因特網名字與號碼分配機構（InternetCoirporationforAssignedNamesandNumbers,ICANN）其工作包括分配IP地址，管理DNS根服務器，分配域名和解決域名紛爭等組織內：（1）由系統(tǒng)管理員手動分配（保存在一個配置文件中）Windows:控制面板->網絡->配置->tcp/ip->屬性UNIX:/etc/rc.config（2）DHCP:DynamicHostConfigurationProtocol:

自動從一個DHCP服務器得到IP地址56IP地址:如何獲取?Q:

采用CIDR該怎樣獲取IP地址中的網絡號部分？A:

從ISP的地址空間中劃分一塊給申請者ISP'sblock11001000000101110001000000000000200.23.16.0/20Organization011001000000101110001000000000000200.23.16.0/23Organization111001000000101110001001000000000200.23.18.0/23Organization211001000000101110001010000000000200.23.20.0/23...…..….….Organization711001000000101110001111000000000200.23.30.0/23

57CIDR地址塊劃分舉例因特網206.0.68.0/22206.0.64.0/18ISP大學X一系二系三系四系206.0.71.128/26206.0.71.192/26206.0.68.0/25206.0.68.128/25206.0.69.0/25206.0.69.128/25206.0.70.0/26206.0.70.64/26206.0.70.128/26206.0.70.192/26206.0.70.0/24206.0.71.0/25206.0.71.0/26206.0.71.64/26206.0.71.128/25206.0.68.0/23

單位地址塊二進制表示地址數

ISP206.0.64.0/1811001110.00000000.01*16384

大學206.0.68.0/2211001110.00000000.010001*1024

一系206.0.68.0/2311001110.00000000.0100010*512

二系206.0.70.0/2411001110.00000000.01000110.*256

三系206.0.71.0/2511001110.00000000.01000111.0*128

四系206.0.71.128/2511001110.00000000.01000111.1*128ICANN超網58網絡地址分配練習

現(xiàn)有一公司已獲得網絡號為202.1.1.0/24，二進制表示為：11001010.00000001.00000001.00000000

如果該公司有3個部門如果第1個部門有120臺計算機,第2個部門有60臺計算機,第3個部門有60臺計算機,使用分類IP的方法可以分配地址?（1）202.1.1.128，掩碼255.255.255.128；（2）202.1.1.0，掩碼255.255.255.192；（3）202.1.1.64，掩碼255.255.255.192；使用CIDR方法如何分配地址?（1）202.1.1.128/25；（2）202.1.1.0/26；（3）202.1.1.64/265910.0.0.110.0.0.210.0.0.310.0.0.4本地網絡(如家庭網絡)138.76.29.7其余Internet所有本地網絡離開分組有同樣的IP地址:138.76.29.7希望訪問Internet,但只分配到一個IP：138.76.29.7,該怎么辦呢？NAT:網絡地址轉換所有本地網絡分組在網絡內傳輸有不同的IP地址60NAT:網絡地址轉換對外部網絡來講，本地網絡只有一個IP地址一個IP地址用于網內所有設備在本地網絡改變設備的IP地址不用通知網絡外部可以變更ISP和外部地址，不用改變本地網絡設備的地址外部世界不能對網絡內部直接尋址，也就是不可見

(增加了安全性)NAT路由器61NAT:網絡地址轉換NAT路由器實現(xiàn)：NAT轉換表轉發(fā)表記錄每個(源IP地址,端口號)到(NATIP地址,新端口號)

的映射記錄項替換每個外出的分組(源IP地址,端口號)

==》

(NATIP地址,新端口號)

遠程客戶/服務器用(NATIP地址,新端口號)作為目的地址來響應替換每個進來的分組 對每個進來的分組，用保存在NAT表中的對應的(源IP地址,端口號)

替換分組中的目的域(NATIP地址,新端口號）62NAT:網絡地址轉換10.0.0.110.0.0.210.0.0.3S:10.0.0.1,3345D:128.119.40.186,80110.0.0.4138.76.29.71:

主機10.0.0.1發(fā)送數據報到128.119.40,80NAT轉換表WAN外部地址LAN地址138.76.29.7:500110.0.0.1:3345…………S:128.119.40.186,80D:10.0.0.1,33454S:138.76.29.7,5001D:128.119.40.186,8022:NAT路由器改變數據報源地址從10.0.0.1,3345到138.76.29.7,5001,更新表S:128.119.40.186,80D:138.76.29.7,500133:

響應到達目的地址:138.76.29.7,50014:NAT路由器改變數據報目的地址從138.76.29.7,5001

到10.0.0.1,334563NAT:網絡地址轉換16-bit端口號，使得一個局域網地址可以同時支持60,000個并發(fā)連接!NAT存在爭議路由器只應該處理到第三層，但端口編址主機違反了端到端主張，路由節(jié)點介入IP和端口號,促使應用程序設計者在設計時不得不將NAT加以考慮，如P2P應用程序應使用IPv6來解決地址短缺問題NAT已成為Internet一個重要部分64

第四章:網絡層4.1概述4.2虛電路和數據報網絡4.3路由器工作原理4.4網際協(xié)議數據報格式IPv4編址ICMP協(xié)議IPv64.5選路算法鏈路狀態(tài)選路算法距離向量算法層次選路4.6因特網中的選路RIPOSPFBGP4.7廣播和多播選路654.4.3ICMP:InternetControlMessageProtocol因特網控制報文協(xié)議用于主機路由器之間彼此交流網絡層信息差錯報告:不可到達的主機,網絡,端口,協(xié)議請求/應答:比如用于ping，traceroute等ICMP是IP的一部分，但位于IP之上因為ICMP消息是裝載在IP分組里的66ICMP報文格式及其封裝ICMP報文0檢驗和類型代碼（這4個字節(jié)取決于ICMP報文的類型）81631前4個字節(jié)是統(tǒng)一的格式ICMP的數據部分（長度取決于類型）ICMP報頭ICMP數據IP報頭IP數據674.4.3ICMP:InternetControlMessageProtocol因特網控制報文協(xié)議類型

代碼

描述00ping應答(ping)30目的網絡不可到達31目的主機不可到達32目的協(xié)議不可到達33目的端口不可達到36不知道的目的網絡37不知道的目的主機40源端抑制(擁塞控制–不用)80ping請求(ping)90路由器公告100路由器發(fā)現(xiàn)110TTL過期120IP首部損壞68Traceroute和ICMPTraceroute跟蹤路由器過程源主機發(fā)送一系列的IP分組給目的主機，第一個分組TTL=1，第二個TTL=2,……,等當第n個分組到達第n個路由器時（1）由于TTL=0，此路由器丟棄該分組（2）給源主機發(fā)送一個ICMP報文

(type11,code0），此報文包含了路由器的名稱和IP地址（3）當源主機收到ICMP報文時，計算傳輸往返時間RTT對每個TTL發(fā)送三次，得到3個結果停止發(fā)送（1）IP報文最終到達目的端（2）目的端返回應答的ICMP報文(type0,code0)（3）源端收到此報文，停止發(fā)送69

第四章:網絡層4.1概述4.2虛電路和數據報網絡4.3路由器工作原理4.4網際協(xié)議數據報格式IPv4編址ICMP協(xié)議IPv64.5選路算法鏈路狀態(tài)選路算法距離向量算法層次選路4.6因特網中的選路RIPOSPFBGP4.7廣播和多播選路704.4.4IPv6初始動機:

32-bit地址空間即將用盡其他動機:首部格式可幫助加速路由器處理/轉發(fā)改變首部利于QoS要求IPv6數據報格式

固定長度的40字節(jié)首部不允許分片71IPv6首部格式版本號（ver）：IPv6設為6優(yōu)先級（pri）:表示流中分組的優(yōu)先級流標識(flowlabel):表示分組在同一個“流”中(區(qū)分流)有效載荷長度（payloadlen）:跟在首部后的數據長度下一個首部（nexthdr）:

表示數據的上層協(xié)議(如UDP或TCP)跳限制（hoplimit）:分組經過路由器的最大數72IPv6與IPv4比較校驗和:

去掉，減少每一跳的處理時間選項:

允許,但是不是標準首部的一部分，而是用下一個首部域指出分片/重新組裝：去掉，若分組太多會產生“分組太大”ICMP報文首部長度：去掉，采用固定40字節(jié)首部ICMPv6:新版本的ICMP增加消息類型,例如，“分組太大”多播組管理功能73IPv6地址表示點號十進制表示法105.220.136.100.255.255.255.255.0.0.18.128.140.10.255.255

冒號十六進制表示為：69DC:8864:FFFF:FFFF:0:1280:8C0A:FFFF零壓縮表示法

FF0C:0:0:0:0:0:B1

零壓縮表示為：

FF0C::B174從IPv4到IPv6過渡問題：現(xiàn)有IPv4網絡大量存在，無法同時升級所有系統(tǒng)和設備解決辦法：

IPv4和IPv6共存兩種推薦方法:雙棧：一些路由器具有雙重棧(v6,v4)能夠在兩種格式中轉換隧道:

在穿過IPv4路由器時，IPv6分組作為IPv4分組的負載75雙棧方法ABEFIPv6IPv6IPv6IPv6CDIPv4IPv4Flow:XSrc:ADest:FdataFlow:??Src:ADest:FdataSrc:ADest:FdataA-to-B:IPv6Src:ADest:FdataB-to-C:IPv4D-to-E:IPv4E-to-F:IPv6流標簽信息會丟失76隧道ABEFIPv6IPv6IPv6IPv6tunnel邏輯觀點:物理觀點:ABEFIPv6IPv6IPv6IPv6CDIPv4IPv4Flow:XSrc:ADest:FdataFlow:XSrc:ADest:FdataFlow:XSrc:ADest:FdataSrc:BDest:EFlow:XSrc:ADest:FdataSrc:BDest:EA-to-B:IPv6E-to-F:IPv6B-to-C:IPv6insideIPv4D-to-E:IPv6insideIPv477

第四章:網絡層4.1概述4.2虛電路和數據報網絡4.3路由器工作原理4.4網際協(xié)議數據報格式IPv4編址ICMP協(xié)議IPv64.5選路算法鏈路狀態(tài)選路算法距離向量算法層次選路4.6因特網中的選路RIPOSPFBGP4.7廣播和多播選路781230111到達分組的首部中的值選路算法

本地轉發(fā)表首部值輸出鏈路01000101011110013221回顧：轉發(fā)和選路選路算法決定轉發(fā)表中的值79uyxwvz2213112535網絡圖定義：圖:G=(N,E)N=所有路由器節(jié)點的集合

={u,v,w,x,y,z}E=所有鏈路的集合

={(u,v),(u,x),(v,x),(v,w),(x,w),(x,y),(w,y),(w,z),(y,z)}網絡的圖形抽象注意:圖形抽象表示在其他網絡環(huán)境中非常有用Example:P2P,N是對等端的集合，而E是TCP連接的集合80圖形抽象:開銷（費用）uyxwvz2213112535鏈路開銷表示：

c(x,x′)=鏈路(x,x′)的開銷

例：c(w,z)=5路徑(x1,x2,x3,…,xp)的開銷=c(x1,x2)+c(x2,x3)+…+c(xp-1,xp)Question:U和Z之間的最小開銷是多少?選路算法:發(fā)現(xiàn)最小開銷路徑的算法81路由選擇算法分類一、全局的還是分散的信息?全局的:所有的路由器都有完整的網絡拓撲結構、鏈路開銷信息常稱為“鏈路狀態(tài)”算法分散的:路由器只知道物理相連的鄰居,以及到鄰居的鏈路開銷。鄰居間反復進行計算處理，交換信息常稱為“距離矢量”算法二、靜態(tài)的還是動態(tài)的?靜態(tài)的:路由變化很慢,通常由人工進行設置,如手工編輯路由轉發(fā)表動態(tài)的:路由變化很快周期性更新直接響應鏈路開銷的變化82

第四章:網絡層4.1概述4.2虛電路和數據報網絡4.3路由器工作原理4.4網際協(xié)議數據報格式IPv4編址ICMP協(xié)議IPv64.5選路算法鏈路狀態(tài)選路算法距離向量算法層次選路4.6因特網中的選路RIPOSPFBGP4.7廣播和多播選路834.5.1鏈路狀態(tài)選路算法前提：所有節(jié)點必須知道網絡拓撲結構和鏈路開銷所有節(jié)點通過“鏈路狀態(tài)廣播”算法廣播其鏈路特征和費用其結果是所有節(jié)點具有網絡完整的結構視圖計算：從一個節(jié)點到其他所有節(jié)點的計算最小開銷（最低費用）路徑，從而得到這個節(jié)點的路由表核心算法：Dijkstra算法迭代尋找最小費用經過K次迭代以后,可得知到其它K個目的地的最小費用路徑84符號定義c(x,y):

從節(jié)點x到y(tǒng)的鏈路開銷.如果沒有直接相鄰，開銷是無窮大（∞）D(v):

從源節(jié)點到目的節(jié)點v的最低費用路徑的當前值p(v):

從源節(jié)點到節(jié)點v的當前最低費用路徑上的前一個節(jié)點（v的鄰接點）N’:

已經明確的具有最低費用路徑的節(jié)點集；比如從源節(jié)點到目的節(jié)點v的最低費用路徑已確認，則v在N’中uxwv2213385Dijsktra’s算法1Initialization:

2N'={u}3forallnodesv4ifvadjacenttou5thenD(v)=c(u,v)6elseD(v)=∞

78Loop

9findwnotinN'suchthatD(w)isaminimum10addwtoN'

11updateD(v)forallvadjacenttowandnotinN':12D(v)=min(D(v),D(w)+c(w,v))13/*newcosttoviseitheroldcosttov(D(v))orknown14shortestpathcosttowpluscostfromwtov(D(w)+c(w,v))*/15untilallnodesinN'

初始化u到鄰居的最低費用u到非鄰居的最低費用為無窮大循環(huán)迭代=N-N'

86Dijkstra算法:舉例步驟012345N'uuxuxyuxyvuxyvwuxyvwzD(v),p(v)2,u2,u2,uD(w),p(w)5,u4,x3,y3,yD(x),p(x)1,uD(y),p(y)∞2,xD(z),p(z)∞∞4,y4,y4,yuyxwvz2213112535計算源節(jié)點u到各節(jié)點的最小費用87構造轉發(fā)表uyxwvz節(jié)點u的最短路徑樹vxywz(u,v)(u,x)(u,x)(u,x)(u,x)目的地鏈路節(jié)點u的轉發(fā)表88Dijkstra算法,討論算法復雜性:n節(jié)點每次迭代:需要檢查所有不在N’中的節(jié)點,找出w節(jié)點，具有最低路徑消耗n(n+1)/2次比較搜索因此，復雜性為O(n2)使用堆數據結構，更有效的執(zhí)行可能:O(nlogn)Dijkstra算法可能產生振蕩:wzyx11+ee0e1100wzyx2+e0001+e1wzyx02+e1+e100wzyx2+e0e01+e1initially…recomputerouting…recompute…recompute89

第四章:網絡層4.1概述4.2虛電路和數據報網絡4.3路由器工作原理4.4網際協(xié)議數據報格式IPv4編址ICMP協(xié)議IPv64.5選路算法鏈路狀態(tài)選路算法距離向量算法層次選路4.6因特網中的選路RIPOSPFBGP4.7廣播和多播選路904.5.2距離向量選路算法Bellman-Ford方程(動態(tài)計算)定義dx(y):=從x到y(tǒng)的具有最低費用路徑的費用值則dx(y)=minv{c(x,v)+dv(y)}v是x的相鄰節(jié)點,minv是對于與x相連的所有鄰居而言91Bellman-Ford方程舉例uyxwvz2213112535dv(z)=5,dx(z)=3,dw(z)=3du(z)=min{c(u,v)+dv(z),c(u,x)+dx(z),c(u,w)+dw(z)}=min{2+5,1+3,5+3}=4應用B-F方程，即:92符號定義Dx(y)=從x到y(tǒng)的最小費用值距離向量:Dx=[Dx(y):y∈N]節(jié)點x到直接相連的鄰居v的開銷:c(x,v)節(jié)點x維護自己的距離向量

Dx=[Dx(y):y∈N]節(jié)點x同時還維護相鄰節(jié)點的距離向量對每個鄰居v,x維護著Dv=[Dv(y):y∈N]93距離向量算法基本思想:

每個節(jié)點周期性的給相鄰節(jié)點發(fā)送自己的距離向量值當節(jié)點x從它的任何一個鄰居v收到一個新的距離向量值，就使用B-F方程更新自己的距離向量值Dx(y)←minv{c(x,v)+Dv(y)}foreachnodey∈

N距離向量估值Dx(y)收斂到實際的最小路徑開銷dx(y)

94距離向量算法迭代的,異步的

迭代的產生是由于：本地鏈路開銷變化鄰居發(fā)送來的最小路徑開銷變化分布的每個節(jié)點只是在它的距離向量發(fā)生變化時通知相鄰節(jié)點在必要時鄰居再通知它們的鄰居等待

(鄰居送來本地鏈路開銷變化的消息)每個節(jié)點執(zhí)行過程：重新計算距離向量若發(fā)現(xiàn)到任何目的節(jié)點的距離向量發(fā)生變化,通知鄰居95Initialization: foralldestinationsyinN:

Dx(y)=c(x,y)/*ifyisnotaneighborthenc(x,y)=∞*/ foreachneighborw

Dw(y)=∞foralldestinationsyinN foreachneighborw senddistancevectorDx=[Dx(y):yinN]towLoop wait(untilIseealinkcostchangetosomeneighborworuntilIreceiveadistancevectorfromsomeneighborw) foreachyinN:

Dx(y)=minv{c(x,v)+Dv(y)} ifDx(y)changedforanydestinationy senddistancevectorDx=[Dx(y):yinN]toallneighborsforever96xyzxyz027∞∞∞∞∞∞fromcosttofromfromxyzxyz027fromcosttoxyzxyz∞∞∞∞∞costtoxyzxyz∞∞∞costto∞∞∞201710timexz127ynodextablenodeytablenodeztable201710Dx(y)=min{c(x,y)+Dy(y),c(x,z)+Dz(y)}

=min{2+0,7+1}=2Dx(z)=min{c(x,y)+

Dy(z),c(x,z)+Dz(z)}=min{2+1,7+0}=3∞3710027fromxyzxyz201costtofromxyzxyzcostto7100272013xyzxyz023fromxyzxyz023fromcosttoxyzxyz023fromcosttostto97距離向量:鏈路費用變化鏈路費用變化時:節(jié)點探測到本地鏈路費用變化，更新路由選擇信息，重新計算距離向量。如果DV變了，通知鄰居好消息傳遞快xz1450y1(1)在t0時刻,y

探測到鏈路開銷變了（4->1）,就更新它的DV,并通知鄰居節(jié)點(2)在t1時刻,z

接收到從y發(fā)來的更新信息，并更新自己的DV.它計算得到一個到達x最短路徑（5->2），然后向它的鄰居發(fā)送自己的DV(3)在t2時刻,y接收到z的更新消息，更新自己的距離向量表，y的最短路徑沒有變化，因此y不發(fā)送任何消息給z98距離向量:鏈路開銷變化壞消息傳得慢

-“計數到無窮”問題!xz1450y60計數到無窮的解決辦法：毒性逆轉假如Z通過Y到達X，則Z告訴Y它到X的距離是無窮大，Y將不會再經過Z到X99xyzxyz045fromcosttonodeYtable401510xyzxyz045fromcosttonodeZtable401510y檢測到鏈路費用變化，則計算：Dy(x)=min{c(y,x)+Dx(X),

c(y,z)+Dz(x)}

=min{60+0,1+5}=6xz1450y60xyzxyz045fromcosttonodextable401510xyzxyz045fromcosttonodeYtable601510100xyzxyz04∞fromcosttonodeYtable401∞10xyzxyz045fromcosttonodeZtable401510xz1450y60xyzxyz045fromcosttonodextable401510Dy(x)=min{c(y,x)+Dx(x),c(y,z)+Dz(x)}

=min{60+0,1+∞}=60xyzxyz04∞fromcosttonodeYtable6001∞10Dz(x)=min{c(z,x)+Dx(x),

c(z,y)+Dy(x)}

=min{50+0,1+60}=50xyzxyz045fromcosttonodeZtable6001?10毒性逆轉1010121？xz113y60A1xyzAxyzfromcosttonodextable101∞2103xyzAxyz0121fromcosttonodeYtable1012210∞xyzAxyz0121fromcosttonodeZtable10122103Dx(A)=min{c(x,A)+DA(A),

c(x,y)+Dy(A),c(x,z)+Dz(A)}

=min{60+0,1+∞,3+3}=6三個或更多節(jié)點環(huán)路將不能被毒性逆轉檢測到102LS算法和DV算法的比較（1）報文復雜性LS:

具有n個節(jié)點，E個鏈路情況,每次發(fā)送O(nE)個報文DV:只是在鄰居間交換信息收斂時間是變化的（2）收斂速度LS:O(n2)算法要求發(fā)送O(nE)個消息可能導致振蕩DV:收斂較慢可能產生循環(huán)路由計數到無限的問題（3）健壯性LS:

節(jié)點可能會廣告錯誤的鏈路開銷每個節(jié)點只計算自己的轉發(fā)表(提供了一定程度的健壯性)DV:DV節(jié)點也可能會通告錯誤的路徑開銷每個節(jié)點的轉發(fā)表可被其他節(jié)點使用，錯誤會擴散到整個網絡103

第四章:網絡層4.1概述4.2虛電路和數據報網絡4.3路由器工作原理4.4網際協(xié)議數據報格式IPv4編址ICMP協(xié)議IPv64.5選路算法鏈路狀態(tài)選路算法距離向量算法層次選路4.6因特網中的選路RIPOSPFBGP4.7廣播和多播選路1044.5.3層次選路規(guī)模:Internet具有數億個路由節(jié)點路由表中不可能存儲所有的節(jié)點!路由表的信息交換將淹沒數據鏈路!

管理自治:某些組織希望按自己意愿運行和管理其網絡internet=眾多網絡組成的網絡每個網絡管理者管理自己網絡的路由選擇迄今為止，我們的路由研究都是理想化的所有路由器一樣的網絡是“平面的”…實際中并不是這樣的自治系統(tǒng)AutonomousSystem,AS105自治系統(tǒng)一個區(qū)域內的路由器組成集合--自治系統(tǒng)

(AS)AS內的路由器運行相同的路由選擇算法（LS或DV），稱為自治系統(tǒng)內部選路協(xié)議不同自治系統(tǒng)內的路由器可以運行不同的AS內部選路協(xié)議網關路由器：與其他自治系統(tǒng)內的路由器直接相連的路由器運行自治系統(tǒng)間選路協(xié)議，與其他網關路由器交互同自治系統(tǒng)內的所有其他路由器一樣也運行域內路由協(xié)議1063b1d3a1c2aAS3AS1AS21a2c2b1bAS內選路算法AS間路由選擇算法轉發(fā)表3cAS互連轉發(fā)表根據AS內和AS間選路算法而配置AS域內的選路項用于目的地址在域內的選路AS域內和AS域間的選路項用于目的地址在域外的選路網關路由器1073b1d3a1c2aAS3AS1AS21a2c2b1b3cAS域間任務假設AS1中的路由器接收到目的地址是AS1外的分組,路由器將把這個分組轉發(fā)到哪個網關路由器呢？1c還是1b呢？為解決此問題：（1）AS1需要知道通過AS2和AS3可以到達哪些目的主機（2）將這些可達信息傳播給AS1內的所有路由器這就是域間選路的任務！108設置轉發(fā)表:只有一個AS可達假設AS1運行域間路由協(xié)議知道網絡x通過網關1c從AS3(而不是AS2)是可達的通過域內路由協(xié)議將可達信息傳播給所有域內路由器Router1d由域內路由信息判斷自己的接口I在到達1c的最小開銷路徑上在轉發(fā)表里添加一項(x,I)3b1d3a1c2aAS3AS1AS21a2c2b1b3cx109從AS間協(xié)議知道經過多個網關可到達子網x從AS內部協(xié)議的選路信息決定到每個網關的最低費用路徑的費用熱土豆選路:選擇具有最小費用的網關從轉發(fā)表決定通向最低費用網關的接口I,添加轉發(fā)表中的(x,I)項設置路由表：多個AS都可達假設AS1通過域間選路協(xié)議知道子網x從AS3和AS2都可以到達路由器1d必須決定通過哪個網關路由器轉發(fā)分組到目的子網x熱土豆選路:把分組送到兩個路由器中最近的一個3b1d3a1c2aAS3AS1AS21a2c2b1b3cx110

第四章:網絡層4.1概述4.2虛電路和數據報網絡4.3路由器工作原理4.4網際協(xié)議數據報格式IPv4編址ICMP協(xié)議IPv64.5選路算法鏈路狀態(tài)選路算法距離向量算法層次選路4.6因特網中的選路RIPOSPFBGP4.7廣播和多播選路111因特網中的選路AS內部選路協(xié)議，也稱內部網關協(xié)議(IGP)RIP:

路由信息協(xié)議OSPF:

開放最短路徑優(yōu)先AS間選路協(xié)議，也稱外部網關協(xié)議（EGP）BGP:邊界網關協(xié)議112

第四章:網絡層4.1概述4.2虛電路和數據報網絡4.3路由器工作原理4.4網際協(xié)議數據報格式IPv4編址ICMP協(xié)議IPv64.5選路算法鏈路狀態(tài)選路算法距離向量算法層次選路4.6因特網中的選路RIPOSPFBGP4.7廣播和多播選路1134.6.1RIP(RoutingInformationProtocol)距離向量算法包含在1982年發(fā)布的BSD-UNIX

版本中。費用采用距離衡量:跳數

(max=15hops)DCBAuvwxyzdestination

hopsu1v2w2x3y3z2

從A到所有葉子子網的跳數114RIP通告距離向量:每隔30秒,通過響應報文在鄰居間進行交換(也被稱為RIP通告,advertisement)每個通告:包含了多達25個AS內的目的子網的列表，以及到每個子網的距離115RIP:Example

目的子網 下一跳路由器到目的地的跳數

w A 2 y B 2 z B 7 x -- 1 …. …. ....wxyzACDBD的轉發(fā)表……116RIP:Example

目的子網 下一跳路由器到目的地的跳數

w A 2 y B 2 z BA 75 x - 1 …. …. ....D收到上述通告后的轉發(fā)表wxyzACDB

目的下一跳路由器跳數

w --x --z C4…. …...從A到D的一個通告117RIP:鏈路失敗及恢復

若180秒后沒有收到通告，則認為鄰居死機或鏈路中斷修改本地選路表向鄰居發(fā)送此信息公告如果轉發(fā)表發(fā)生變化，鄰居再發(fā)送新的公告鏈路故障信息快速傳播到整個網絡毒性逆轉用于防止無限計數(無限距離=16跳)118RIP轉發(fā)表處理UNIX系統(tǒng)中，RIP轉發(fā)表（路由表）是由應用級的進程稱為routed(后臺程序)管理的通告通過UDP報文進行發(fā)送,周期性重復physicallinknetworkforwarding(IP)tableTransprt(UDP)routedphysicallinknetwork(IP)Transprt(UDP)routedforwardingtable119