1、第四章:網路層和路由法章節目標:r了解網路層服務背後的原則:m網路層服務模型m轉送 v.s.路由m路由器如何運作m路由(路徑選擇)m有關擴充m進階課題:IPv6,行動r網際網路上的例證、實作第四章:網路層和路由法r4.1 簡介r4.2 虛擬線路和資料段網路r4.3 路由器的內部為何r4.4 IP:網際網路協定m資料段格式mIPv4 的定址法m網際網路控制訊息協定(ICMP)mIPv6r4.5 路由演算法m連結狀態m距離向量m階層式路由r4.6 網際網路的路由mRIPmOSPFmBGPr4.7 廣播與群播路由網路層r從傳送主機到接收主機傳輸的資料分段r在傳送端將資料分段封裝在資料段中r在接收端，
2、將資料分段傳送到傳輸層r每一台主機、路由器中都有網路層協定r路由器會檢查經過它的所有IP資料段中的標頭欄位網路層資料連結層實體層網路層資料連結層實體層網路層資料連結層實體層網路層資料連結層實體層網路層資料連結層實體層網路層資料連結層實體層網路層資料連結層實體層網路層資料連結層實體層應用層傳輸層網路層資料連結層實體層應用層傳輸層網路層資料連結層實體層主要的網路層功能r轉送:將封包從路由器的輸入轉送到適當的路由器輸出r路由:決定封包從來源端到目的端的路由m路由演算法比方:r路由:計畫從來源到目的旅行的過程r轉送:經過單一交流道的過程1230111到達封包的標頭值路由演算法本機演算法標頭值輸出連結0
3、1000101011110013221路由與轉送之間的交互作用建立連線r在某些網路架構中的第三個重要功能:mATM,frame relay,X.25r在資料段傳送之前，兩個主機以及介於其間的路由器先建立虛擬連線m路由器介入r網路層以及傳輸層的連線服務:m網路層:兩個主機之間m傳輸層:兩個行程之間網路服務模型Q:有哪些服務模型提供給從傳送端到接收端傳輸資料段的通道?個別資料段的服務範例:r傳送保證r小於 40 毫秒的傳送保證資料段流量的服務範例:r依序封包傳送r流量的最低頻寬保證r限制兩個封包之間間隔的改變網路層服務模型:網路架構網際網路ATMATMATMATM服務模型盡全力服務CBRVBRAB
4、RUBR頻寬無常數速率保證速率保證最小速率無遺失無有有無無排序無有有有有時序無有有無無壅塞指示無(藉由遺失來推論)不發生壅塞不發生壅塞有無保證?第四章:網路層和路由法r4.1 簡介r4.2 虛擬線路和資料段網路r4.3 路由器的內部為何r4.4 IP:網際網路協定m資料段格式mIPv4 的定址法m網際網路控制訊息協定(ICMP)mIPv6r4.5 路由演算法m連結狀態m距離向量m階層式路由r4.6 網際網路的路由mRIPmOSPFmBGPr4.7 廣播與群播路由網路層連線以及非預接式服務r資料段網路提供網路層的非預接式服務rVC 網路提供網路層的連線服務r可與傳輸層服務類比，但是:m服務:主機
5、對主機m沒有選擇性:網路只提供其中一個m實作:在核心虛擬線路r在資料開始傳送前，必須為每個連結建立連線，拆除r每個封包會承載一個 VC 識別碼(並非目的端主機位址)r在來源對目的的路徑上，每個路由器都必須維護每個經過的連線的狀態r連結和路由器的資源(頻寬、緩衝區)可能會配置給VC“來源端到目的端的路徑，如同電話線路”m效能良好m沿著來源端到目的端路徑的網路行為VC 實作一個 VC 包含了:m一條來源端至目的端間的路徑mVC 編號，路徑上的每一個連結都有一個編號m路徑上的每一個路由器轉送表中的紀錄r一個屬於虛擬線路的封包會載送一個 VC 編號r在每一個連結，VC 編號必須改變1.新的 VC 編號
6、從轉送表中得來轉送表122232123VC 編號介面號碼進入介面 進入VC編號 離開介面 離開介面號碼1 12 3 222 63 1 18 3 7 2 171 97 3 87 美國西部路由器的轉送表:路由器維護連線狀態資訊!虛擬線路:訊號協定r用來設定,維護及拆除 VCr用在 ATM,frame-relay,X.25r並沒有用在現今的網際網路中應用層傳輸層網路層資料連結層實體層應用層傳輸層網路層資料連結層實體層 1.初始連線2.進入連線請求3.接受連線4.連線建立5.開始傳送資料6.接受資料資料段網路r在網路層不需要建立連線r路由器:沒有終端對終端的連線狀態m沒有網路層的連線觀念r使用目的端主
7、機位址傳送封包m在同一對來源-目的端之間的封包可能會使用不同的路徑應用層傳輸層網路層資料連結層實體層應用層傳輸層網路層資料連結層實體層1.送出資料2.接收資料轉送表 目的端位址區塊 連結介面 11001000 00010111 00010000 00000000 至 0 11001000 00010111 00010111 11111111 11001000 00010111 00011000 00000000 至 1 11001000 00010111 00011000 11111111 11001000 00010111 00011001 00000000 至 2 11001000 000
8、10111 00011111 11111111 其它 340億個可能的紀錄最長前置代碼對應 前置代碼對應 連結介面 11001000 00010111 00010 0 11001000 00010111 00011000 1 11001000 00010111 00011 2 其他 3DA:11001000 00010111 00011000 10101010 範例DA:11001000 00010111 00010110 10100001 哪一個介面?哪一個介面?資料段或 VC 網路:為什麼?網際網路r電腦之間的資料交換m“彈性的”服務,沒有嚴格的時限要求r“聰明的”終端系統(電腦)m能夠適
9、應、執行控制、錯誤復原m網路內部是簡單的，邊緣是複雜的r許多連結型態 m不同的特質m統一的服務困難ATMr來自電話系統r人類的對話:m嚴格的時限,可靠性的要求m保證服務的需求r“愚笨的”終端系統m電話m網路內部是複雜的第四章:網路層和路由法r4.1 簡介r4.2 虛擬線路和資料段網路r4.3 路由器的內部為何？r4.4 IP:網際網路協定m資料段格式mIPv4 的定址法m網際網路控制訊息協定(ICMP)mIPv6r4.5 路由演算法m連結狀態m距離向量m階層式路由r4.6 網際網路的路由mRIPmOSPFmBGPr4.7 廣播與群播路由路由器架構綜觀兩個主要的路由器功能:r執行路由演算法/協定
10、(RIP,OSPF,BGP)r將資料段從輸入轉送到輸出連結輸入埠功能非集中式的交換非集中式的交換:r給定一個資料段目的端，使用輸入埠記憶體中的轉送表來尋找輸出埠r目標:以連線速度完成輸入埠的處理過程r排隊:假如資料段的抵達速率快於轉送進入交換結構的速率實體層:位元層級的接收資料連結層:例如,乙太網路見第五章三種交換結構經由記憶體的交換機制第一代的路由器:r 傳統的電腦，在CPU的直接控制下完成交換動作r封包複製到系統記憶體r 速度會被記憶體頻寬所限制(一個資料段會經過兩次匯流排)輸入埠輸出埠記憶體系統匯流排經由匯流排的交換機制r資料段經由共享的匯流排從輸入埠記憶體送到輸出埠記憶體r匯流排的競爭
11、:交換速度受限於匯流排頻寬r1 Gbps 匯流排,Cisco 1900:對存取及企業路由器是足夠的(非地區的或骨幹的)經由互連網路的交換機制r克服匯流排的頻寬限制rBanyan網路，其他的互連網路初始的建立，是將處理器連接到多處裡器r更進一步的設計:將資料段分割成固定長度的封包單位，將封包單位送入交換結構中rCisco 12000:經由互連網路可達 Gbps 的交換速率輸出埠r需要緩衝區，當資料段抵達結構的速率大於傳送速率r排程原則選擇佇列中的資料段加以傳送輸出埠佇列r當經由交換器抵達的速率超過輸出連結的速度r佇列排隊(延遲)以及因為輸出埠的緩衝區溢出導致的遺失!輸入埠佇列r結構速度慢於輸入埠
12、的加總-可能在輸入佇列發生排隊的情形r連線前端(HOL)阻塞:在佇列最前端排隊的資料段會阻止佇列中的其他資料往前移動r佇列延遲以及導因於輸入緩衝區溢出的遺失!第四章:網路層和路由法r4.1 簡介r4.2 虛擬線路和資料段網路r4.3 路由器的內部為何r4.4 IP:網際網路協定m資料段格式mIPv4 的定址法m網際網路控制訊息協定(ICMP)mIPv6r4.5 路由演算法m連結狀態m距離向量m階層式路由r4.6 網際網路的路由mRIPmOSPFmBGPr4.7 廣播與群播路由網際網路的網路層NoImage轉送表主機，路由器的網路層功能:路由協定路徑選擇RIP,OSPF,BGPIP 協定定址原則
13、資料段格式封包處理原則ICMP 協定錯誤回報路由器“訊號”傳輸層:TCP,UDP連結層實體層網路層第四章:網路層和路由法r4.1 簡介r4.2 虛擬線路和資料段網路r4.3 路由器的內部為何r4.4 IP:網際網路協定m資料段格式mIPv4 的定址法m網際網路控制訊息協定(ICMP)mIPv6r4.5 路由演算法m連結狀態m距離向量m階層式路由r4.6 網際網路的路由mRIPmOSPFmBGPr4.7 廣播與群播路由IP 資料段格式版本資料段長度32 位元資料(不固定長度，通常是 TCP 或 UDP 資料分段)16位元的識別碼網際網路檢查和生存期32 位元來源端IP位址IP 協定版本號碼標頭長
14、度(位元組)剩餘站數的最大數量(經過每一個路由器時減1)用來分割/重組資料段總長度(位元組)傳送資料部分時所使用的上層協定標頭長度服務類型資料的“類型”旗標分割偏移量上層協定32 位元目的端IP位址選項欄位(如果有的話)例如.時間戳記,路由紀錄,拜訪的路由器特定列表TCP有多少資源負擔?r20 位元組 TCPr20 位元組 IPr=40 位元組+應用層的訊息負擔IP 分割與重組r網路連結層具有 MTU(最大的可傳輸大小)最大的連結層訊框m不同的連結層型態，不同的MTU r過大的 IP 資料段在網路內被切分(分割)m一個資料段變成好幾個資料段m只在終點被“重組”mIP 標頭位元用來識別，排序相關
15、的分割分割:in:1 個大的資料段out:3 個小的資料段重組IP分割與重組ID=xoffset=0fragflag=0length=4000ID=xoffset=0fragflag=1length=1500ID=xoffset=185fragflag=1length=1500ID=xoffset=370fragflag=0length=1040一個大的資料段變成數個小的資料段範例r4000 位元組的資料段rMTU=1500 位元組資料欄位中有1480 個位元組偏移量=1480/8 第四章:網路層和路由法r4.1 簡介r4.2 虛擬線路和資料段網路r4.3 路由器的內部為何r4.4 IP:網際
16、網路協定m資料段格式mIPv4 的定址法m網際網路控制訊息協定(ICMP)mIPv6r4.5 路由演算法m連結狀態m距離向量m階層式路由r4.6 網際網路的路由mRIPmOSPFmBGPr4.7 廣播與群播路由IP 定址法:簡介rIP 位址:32位元的識別碼，做為主機、路由器的介面r介面:在主機/路由器以及實體連結的交界處m路由器通常擁有多個介面m主機通常擁有一個介面mIP 位址代表每個介面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=11
17、011111 00000001 00000001 00000001223111子網路rIP 位址:m子網路部分(高階位元)m主機部分(低階位元)r什麼是子網路?mIP具有相同子網路部分的裝置介面m可以在沒有路由器的狀況下，實體地互相連結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.27包含 3 個子網路的網路子網路子網路223.1.1.0/24223.1.2.0/24223.1.3.0/24方法r要決定子網路,將每一個介面和它的主機或路由器分開，建立分離的網路。每
18、一個分離的網路稱為一個子網路。子網路遮罩:/24子網路有幾個?223.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.2IP 位址:CIDRCIDR:無分級領域間路由法 (Classless InterDomain Routing)m位址內任意長度的子網路部分m位址格式:a.b.c.d/x，其中 x 是位址的子網路部份的位元數量11001000 00010111 0
19、0010000 00000000子網路部分主機部分200.23.16.0/23IP 位址:如何取得?Q:主機要如何取得 IP 位址?r手動設定在系統管理的檔案中mWintel:控制台-網路-設定-tcp/ip-屬性mUNIX:/etc/rc.configrDHCP:動態主機配置協定(Dynamic Host Configuration Protocol):動態地由伺服器取得位址m“隨插即用”(在下一章介紹)IP 位址:如何取得?Q:網路要如何取得IP位址的子網路部分?A:從 ISP 的位址空間中取得分配的部分ISP區塊 11001000 00010111 00010000 00000000 2
20、00.23.16.0/20 組織 0 11001000 00010111 00010000 00000000 200.23.16.0/23 組織 1 11001000 00010111 00010010 00000000 200.23.18.0/23 組織 2 11001000 00010111 00010100 00000000 200.23.20.0/23 .組織 7 11001000 00010111 00011110 00000000 200.23.30.0/23 階層式定址法:路由集成“將任何位址開頭是200.23.16.0/20的訊息傳給我”200.23.16.0/23200.23
21、.18.0/23200.23.30.0/23Fly-By-Night-ISP組織 0組織 7網際網路組織 1ISPs-R-Us“將任何位址開頭是199.31.0.0/16的訊息傳給我”200.23.20.0/23組織 2.階層式定址允許有效率的路由資訊傳播:階層式定址法:更特定的路徑ISPs-R-Us 擁有更特定的路徑到達組織 1“將任何位址開頭是200.23.16.0/20的訊息傳給我”200.23.16.0/23200.23.18.0/23200.23.30.0/23Fly-By-Night-ISP組織 0組織 7Internet組織 1ISPs-R-Us“將任何位址開頭是 199.31.
22、0.0/16或 200.23.18.0/23 的訊息傳給我”200.23.20.0/23組織 2.IP 位址:最後.Q:ISP 如何取得一塊位址?A:ICANN:Internet Corporation for Assigned Names and Numbersm配置位址m管理 DNSm分派領域名稱，解決爭論NAT:網路位址轉譯10.0.0.110.0.0.210.0.0.310.0.0.4138.76.29.7區域網路(例如，家庭網路)10.0.0/24網路的其他部分在這個網路中，來源端或目的端傳送的資料段，具有 10.0.0/24 的來源及主機位址(一般而言)所有離開區域網路的資料段都具
23、有相同的單一來源NAT IP 位址：138.76.29.7，不同的來源埠號NAT:網路位址轉譯r動機:區域網路對外界而言，通常只有一個 IP 位址:m不需要從ISP取得一個範圍的位址：只需要一個位址即可應付所有裝置m不需要通知外界，即可改變區域網路中的裝置位址m不需要改變區域網路內的裝置位址，即可變更ISPm區域網路內的裝置不需要明顯地被外面的世界定址、見到(增加安全性)NAT:網路位址轉譯實作:NAT 路徑必須:m送出的資料段:更換每一個送出的資料段(來源IP位址,埠號)成為(NAT IP 位址,新埠號).遠端用戶端/主機會使用(NAT IP 位址,新埠號)做為目的端位址，來做回應m記憶(在
24、 NAT 轉譯表中)每一個(來源端 IP 位址,埠號)到(NAT IP 位址,新埠號)的轉譯對應m進入的資料段:更換每個進入資料段目的欄位中的(NAT IP 位址,新埠號)為儲存在 NAT表中的對應(來源端 IP 位址,埠號)NAT:網路位址轉譯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:host 10.0.0.1 傳送資料段到128.119.40.186,80NAT 轉譯表廣域網路端位址 區域網路端位址138.76.29.7,5001 10.0.0.1,3345 S:128.1
25、19.40.186,80 D: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,80 D:138.76.29.7,500133:回應抵達 目的端位址:138.76.29.7,50014:NAT 路由器將資料段目的位址從138.76.29.7,5001 轉成 10.0.0.1,3345 NAT:網路位址轉譯r16-位元的埠號欄位:m利用單一的區域端位址，可提供60,000 個同時連線!rNAT 是
26、具有爭議性的:m路由器只應處理到第三層m違反端點到端點的主張 NAT 可能會列入應用程式的設計考量，例如 P2P應用程式m位址不足的問題應該由IPv6來解決第四章:網路層和路由法r4.1 簡介r4.2 虛擬線路和資料段網路r4.3 路由器的內部為何r4.4 IP:網際網路協定m資料段格式mIPv4 的定址法m網際網路控制訊息協定(ICMP)mIPv6r4.5 路由演算法m連結狀態m距離向量m階層式路由r4.6 網際網路的路由mRIPmOSPFmBGPr4.7 廣播與群播路由ICMP:網際網路訊息控制協定r主機和路由器使用來互相傳送網路層資訊的協定m錯誤回報:無法到達主機,網路,埠號,協定m回應
27、請求/回覆(由ping所使用)r網路層，在IP“之上”:mICMP 訊息在IP封包中載送rICMP 訊息:類型,代碼，加上導致錯誤的 IP 資料段的前八個位元組類型 代碼 說明0 0 回應訊息(ping)3 0 目的端網路無法連上3 1 目的端主機無法連上3 2 目的端協定無法連上3 3 目的端埠無法連上3 6 目的端網路未知3 7 目的端主機未知 0 來源抑制訊息(壅塞控制 未使用)8 0 回應請求(ping)9 0 路由器通告10 0 路由器搜尋中11 0 TTL 過期12 0 IP標頭損毀Traceroute 與 ICMPr來源端傳送一系列的UDP資料分段給目的端m第一個具有 TTL=1
28、m第二個具有 TTL=2,依此類推m不可能的埠號r當第 n 個資料段抵達第 n 個路由器:m路由器刪除資料段m接著傳送一個 ICMP 訊息給來源端(類型 11,代碼 0)m訊息中包含了路由器名稱以及IP位址r當 ICMP 訊息抵達時，來源端會計算RTTrTraceroute 會重複這個步驟三次停止的標準rUDP 資料分段最終會到達目的主機r目的端會回傳 ICMP“主機無法到達”封包(類型 3,代碼 3)r當來源端收到這個ICMP時，則會停止第四章:網路層和路由法r4.1 簡介r4.2 虛擬線路和資料段網路r4.3 路由器的內部為何r4.4 IP:網際網路協定m資料段格式mIPv4 的定址法m網
29、際網路控制訊息協定(ICMP)mIPv6r4.5 路由演算法m連結狀態m距離向量m階層式路由r4.6 網際網路的路由mRIPmOSPFmBGPr4.7 廣播與群播路由IPv6r一開始的動機:32位元的位址空間很快就使用殆盡了r其他的動機:m標頭格式可以幫助處理/轉送更快速m標頭的改變可以幫助QOSIPv6 資料段格式:m固定長度的40位元組標頭m不允許切割IPv6 標頭(續)優先權:辨識資料流中，資料封包間的優先權資料流標記:辨識同一個資料流中的資料封包 (資料流的概念沒有良好的定義)下接標頭:辨識資料的上層協定與 IPv4 的不同r檢查和:完全地移除，減少每一站的處理時間r選項:允許，但在標
30、頭之外，由下接標頭指向rICMPv6:新版本的 ICMPm增加訊息類型,例如“封包太大”m群體廣播群組管理功能從 IPv4 轉換成 IPv6r並不是所有的路由器可以同時升級m無法使用“F 日”m假如網路的運作混和了IPv4和IPv6的路由器會如何？r建立通道:在 IPv4 資料段的承載資料中，封裝完整的IPv6資料段，送往 IPv4 路由器。建立通道ABEFIPv6IPv6IPv6IPv6通道邏輯面:實際面:ABEFIPv6IPv6IPv6IPv6IPv4IPv4建立通道ABEFIPv6IPv6IPv6IPv6通道邏輯面:實際面:ABEFIPv6IPv6IPv6IPv6CDIPv4IPv4資料
31、流:X來源端:A目的端:F資料資料流:X來源端:A目的端:F資料資料流:X來源端:A目的端:F資料來源端:B目的端:E資料流:X來源端:A目的端:F資料來源端:B目的端:EA-到-B:IPv6E-到-F:IPv6B-到-C:IPv6 封裝在IPv4裡面B-到-C:IPv6 封裝在IPv4 裡面第四章:網路層和路由法r4.1 簡介r4.2 虛擬線路和資料段網路r4.3 路由器的內部為何r4.4 IP:網際網路協定m資料段格式mIPv4 的定址法m網際網路控制訊息協定(ICMP)mIPv6r4.5 路由演算法m連結狀態m距離向量m階層式路由r4.6 網際網路的路由mRIPmOSPFmBGPr4.7
32、 廣播與群播路由1230111抵達封包的標頭值路由演算法區域轉送表標頭值輸出連結01000101011110013221路由和轉送的交互作用uyxwvz2213112535圖形:G=(N,E)N=一組路由器=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)抽象化圖形註:抽象化圖形在其它的網路應用上也是很有用的例如:P2P,其中 N 為對等點的集合，而 E 為TCP連線的集合抽象化圖形:成本uyxwvz2213112535 c(x,x)=連結(x,x)的成本 -例如，c(w,z)=5 成本可能永遠是
33、1，或是相反地 與頻寬相關，或是相反地與壅塞 程度相關路徑(x1,x2,x3,xp)的成本=c(x1,x2)+c(x2,x3)+c(xp-1,xp)問題:u和z之間的最小成本路徑為何?路由演算法:尋找最小成本路徑的演算法路由演算法的分類整體或分散式資訊?整體的:r所有的路由器都擁有完整的拓樸及連結成本資訊r“連結狀態”演算法分散式:r路由器知道實體連結的鄰居以及到鄰居的連結成本r反覆地計算，以及與鄰居交換資訊r“距離向量”演算法靜態的或動態的?靜態的:r路徑隨著時間緩慢地改變動態的:r較快速地改變路徑m周期性的更新m回應連結成本的改變第四章:網路層和路由法r4.1 簡介r4.2 虛擬線路和資料
34、段網路r4.3 路由器的內部為何r4.4 IP:網際網路協定m資料段格式mIPv4 的定址法m網際網路控制訊息協定(ICMP)mIPv6r4.5 路由演算法m連結狀態m距離向量m階層式路由r4.6 網際網路的路由mRIPmOSPFmBGPr4.7 廣播與群播路由連結狀態路由演算法Dijkstra 演算法r已知所有節點的網路拓樸，連結成本m經由連結狀態廣播完成 m每個節點都擁有一樣的資訊r從一個節點(來源端)開始，到所有其他節點，計算最小成本路徑m給定此節點的轉送表r迴圈的:在 k 次迴圈以後，會知道 k 個目的節點的最小成本路徑符號:rc(x,y):從節點x到y的連結成本;=假如不是直接的鄰居
35、rD(v):從來源端到目的端 v 目前的路徑成本值rp(v):沿著路徑上，從來源端到 v 的前一個節點rN:一組最小成本路徑已知的節點Dijsktra 演算法1 Initialization:2 N=u 3 for all nodes v 4 if v adjacent to u 5 then D(v)=c(u,v)6 else D(v)=7 8 Loop 9 find w not in N such that D(w)is a minimum 10 add w to N 11 update D(v)for all v adjacent to w and not in N:12 D(v)=mi
36、n(D(v),D(w)+c(w,v)13 /*new cost to v is either old cost to v or known 14 shortest path cost to w plus cost from w to v*/15 until all nodes in N Dijkstra 演算法:範例Step012345NuuxuxyuxyvuxyvwuxyvwzD(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,yuyxwvz2213112535Dijkstra 演算法
37、:範例(2)uyxwvz結果：從u開始的最短路徑樹:vxywz(u,v)(u,x)(u,x)(u,x)(u,x)目的連結結果：u的轉送表Dijkstra 演算法，討論演算法複雜度:n 個節點r每個迴圈:需要確認不在 N 中的每個節點 wrn(n+1)/2 個比較:O(n2)r可能更有效率的實作:O(nlogn)可能的擺動:r例如，連結成本=該連結的載送負荷ADCB11+ee0e1100ADCB2+e0001+e 1ADCB02+e1+e10 0ADCB2+e0e01+e 1初始 重新計算路由 重新計算 重新計算第四章:網路層和路由法r4.1 簡介r4.2 虛擬線路和資料段網路r4.3 路由器的
38、內部為何r4.4 IP:網際網路協定m資料段格式mIPv4 的定址法m網際網路控制訊息協定(ICMP)mIPv6r4.5 路由演算法m連結狀態m距離向量m階層式路由r4.6 網際網路的路由mRIPmOSPFmBGPr4.7 廣播與群播路由距離向量演算法 Bellman-Ford 方程式(動態程式)定義dx(y):=從 x 到 y 之最小成本路徑的成本則dx(y)=min c(x,v)+dv(y)其中 min 符號作用於 x 的所有相鄰節點vBellman-Ford 範例 uyxwvz2213112535清楚地,dv(z)=5,dx(z)=3,dw(z)=3du(z)=min c(u,v)+dv
39、(z),c(u,x)+dx(z),c(u,w)+dw(z)=min 2+5,1+3,5+3 =4可達成最小路徑的節點是最短路徑上的下一站 轉送表B-F 方程式說:距離向量演算法 rDx(y)=從 x 到 y 的預估最小成本r距離向量:Dx=Dx(y):y N r節點 x 知道到每一個鄰居 v 的成本:c(x,v)r節點 x 維護 Dx=Dx(y):y N r節點 x 也維護它的鄰居的距離向量m對每一個鄰居 v,x 維護 Dv=Dv(y):y N 距離向量演算法(4)基本想法:r每一個節點定期地傳送它自己的距離向量預估值給鄰居節點r當一個節點 x 收到來自鄰居的新 DV 預估值，它會使用B-F方
40、程式更新它自己的DV:Dx(y)minvc(x,v)+Dv(y)對每一個節點 y Nr在一般的自然狀況下，預估的 Dx(y)會涵蓋真正的最小成本 dx(y)距離向量演算法(5)反覆的,非同步的:每一個地區性的迴圈皆導因於：r地區連結的成本改變r來自鄰居的 DV 更新訊息分散的:r每個節點只在它的DV改變時，才會通知它的鄰居m假如必要，鄰居節點才會再通知它的鄰居等待(鄰居節點的地區連結成本改變訊息)重新計算預估值假如到任何一個目的端的 DV 改變了，通知鄰居節點每一個節點:x y zxyz0 2 7來源節點目的節點來源節點來源節點x y zxyz0 2 3來源節點目的節點x y zxyz0 2
41、3來源節點目的節點x y zxyz 目的節點x y zxyz0 2 7來源節點目的節點x y zxyz0 2 3來源節點目的節點x y zxyz0 2 3來源節點目的節點x y zxyz0 2 7來源節點目的節點x y zxyz7 10目的節點2 0 1 2 0 17 1 02 0 17 1 02 0 13 1 02 0 13 1 02 0 13 1 02 0 13 1 0時序xz127y節點節點 x 的表的表節點節點 y 的表的表節點節點 z 的表的表Dx(y)=minc(x,y)+Dy(y),c(x,z)+Dz(y)=min2+0,7+1=2Dx(z)=minc(x,y)+Dy(z),c(
42、x,z)+Dz(z)=min2+1,7+0=3距離向量:連結成本改變連結成本改變:r節點偵測到區域連結成本的改變r更新路由資訊，重新計算距離向量r假如 DV 改變，通知鄰居節點“好消息會以快速傳遞！”xz1450y1在時間點 t0，y 偵測到連結成本的變更，它會更新距離向量，並通知相鄰節點在時間點 t1，z 接收來自 y 的更新訊息，更新自己的表格。它會計算出到 x 的新最小成本，並傳送給相鄰節點在時間點 t2，y 會接收到 z 的更新訊息，並且更新自己的距離表格。因為 y 的最小成本並沒有改變，所以 y 不會傳送任何訊息給 z。距離向量:連結成本改變連結成本改變:r好消息會以快速傳遞！r壞消
43、息會以慢速傳遞-“計算到無限大”的問題!r在演算法穩定之前，需要44 次迴圈:見課文抑制反轉:r假如 Z 經由 Y 到達目的端 X:mZ 告訴 Y 它(Z)到達 X 的距離是無限大(因此 Y 不會試著經由 Z 到達 X)r這個方法是否能完全解決計算到無限大的問題呢？xz1450y60LS 與 DV 演算法的比較訊息複雜度rLS:n 個節點,E 條連結,O(nE)個傳送出去的訊息 rDV:只在鄰居之間交換m收斂時間不固定收斂速度rLS:O(n2)演算法需要 O(nE)個訊息m可能有擺動rDV:收斂速度不固定m可能產生路由迴圈m計算到無窮大的問題強健性:假如路由器故障會發生什麼問題?LS:m節點可
44、能會廣播不正確的連結成本m每個節點只計算它自己的轉送表DV:mDV 節點可能會廣播不正確的路徑成本m每個節點的轉送表也被其他人所使用 將錯誤傳播到網路中第四章:網路層和路由法r4.1 簡介r4.2 虛擬線路和資料段網路r4.3 路由器的內部為何r4.4 IP:網際網路協定m資料段格式mIPv4 的定址法m網際網路控制訊息協定(ICMP)mIPv6r4.5 路由演算法m連結狀態m距離向量m階層式路由r4.6 網際網路的路由mRIPmOSPFmBGPr4.7 廣播與群播路由階層式路由規模:具有兩億個目的端:r無法將所有的目的端都儲存在路由器轉送表內!r路由表的交換將會淹沒所有連結!自治管理權r網際
45、網路=網路的網路r每個網路的管理者也許會想要控制自己網路中的路由我們所研究的路由到目前為止 理想化 r所有的路由器都相同r網路是“平面的”在現實中並非如此階層式路由r將路由器聚集成區域,“自治系統”(AS)r同樣 AS 中的路由器會執行相同的路由協定m“自治系統內部”路由 協定m在不同AS間的路由器可以執行不同的自治系統內部路由協定閘道路由器r直接連結到另一個AS中的路由器3b1d3a1c2aAS3AS1AS21a2c2b1b自治系統內部路由演算法自治系統間路由演算法轉送表3c互相連結的 ASr轉送表由自治系統內部以及自治系統間的路由演算法兩者來設定m自治系統內部路由協定設定內部目的端的紀錄m
46、自治系統間以及自治系統內部路由協定設定外部目的端的紀錄3b1d3a1c2aAS3AS1AS21a2c2b1b3c自治系統間的任務r假設AS1中的路由器收到一個資料段，它的目的端在AS1外部m路由器應該要將封包轉送到其中一個閘道路由器，應該是哪一個？AS1 需要:r學習哪一個目的端可以經由AS2抵達，而哪一個可以經由AS3抵達r要傳播這個資訊到AS1中的所有路由器自治系統間路由器的工作!範例:設定路由器 1d 的轉送表r假設AS1從自治系統間的路由協定學習到子網路 x 可以經由AS3(閘道路由器 1c)抵達，但是不可由AS2抵達。r自治系統間路由協定將這個資訊傳播到所有的內部路由器。r路由器 1
47、d 由自治系統內部的路由資訊決定，它的介面 I 在通往 1c 的最小成本路徑上。r在轉送表中放入紀錄(x,I)。從自治系統間的路由協定得知子網路x可經由多個閘道到達使用自治系統內部的路由協定資訊以決定到達每個閘道之最小成本路徑的成本燙手山芋路由法：選擇最小成本為最低的閘道路由器。由轉送表決定連結到該最小成本閘道的介面I。在轉送表中輸入(x,I)。範例:由多個AS中做選擇r現在假設AS1從自治系統間路由協定得知，子網路 x 可以經由AS3以及AS2到達。r要設定轉送表，路由器1d必須決定它要經由哪一個閘道路由器轉送到目的 x 的封包。r這也是自治系統間路由協定的工作!r燙手山芋路由法:將封包經由
48、兩個路由器中較近的一個傳送。第四章:網路層和路由法r4.1 簡介r4.2 虛擬線路和資料段網路r4.3 路由器的內部為何r4.4 IP:網際網路協定m資料段格式mIPv4 的定址法m網際網路控制訊息協定(ICMP)mIPv6r4.5 路由演算法m連結狀態m距離向量m階層式路由r4.6 網際網路的路由mRIPmOSPFmBGPr4.7 廣播與群播路由自治系統內部路由法r也稱為內部閘道協定(IGP)r最常見的自治系統內部路由協定:mRIP:路由資訊協定mOSPF:開放最短路徑優先mIGRP:內部閘道路由協定(Cisco專利)第四章:網路層和路由法r4.1 簡介r4.2 虛擬線路和資料段網路r4.3
49、 路由器的內部為何r4.4 IP:網際網路協定m資料段格式mIPv4 的定址法m網際網路控制訊息協定(ICMP)mIPv6r4.5 路由演算法m連結狀態m距離向量m階層式路由r4.6 網際網路的路由mRIPmOSPFmBGPr4.7 廣播與群播路由RIP(路由資訊協定)r距離向量演算法r包含在1982年的 BSD-UNIX Distribution 中r距離計量:hop數目(最大=15 個 hop)DCBAuvwxyz目的端 轉送次數 u 1 v 2 w 2 x 3 y 3 z 2 從路由器A到不同的子網路:RIP 廣播r距離向量:每隔30秒使用回應訊息(也稱做通告)，在相鄰節點間交換r每個通
50、告:自治系統內最多達25個目的端子網路的清單RIP:範例 目的端網路目的端網路 下一個路由器下一個路由器 到目的端所需的轉送次數到目的端所需的轉送次數 wA2yB2 zB7x-1.wxyzACDBD中的路由表RIP:範例 目的端網路目的端網路 下一個路由器下一個路由器 到目的端所需的轉送次數到目的端所需的轉送次數 wA2yB2 zB A7 5x-1.D中的路由表wxyzACDB 目的端下一個目的端下一個 轉送次數轉送次數 w -1 x -1 z C 4 .從從A到到D的通告的通告RIP:連結失敗以及復原假如在180秒內沒有收到通告-相鄰節點/連結宣告死亡m經過相鄰節點的路由是無效的m新的通告會
