第四章网路层和路由法课件

第四章:網路層和路由法章節目標:

了解網路層服務背後的原則:網路層服務模型轉送v.s.路由路由器如何運作路由(路徑選擇)有關擴充進階課題:IPv6,行動網際網路上的例證、實作第四章:網路層和路由法章節目標:第四章:網路層和路由法4.1簡介4.2虛擬線路和資料段網路4.3路由器的內部為何4.4IP:網際網路協定資料段格式IPv4的定址法網際網路控制訊息協定(ICMP)IPv64.5路由演算法連結狀態距離向量階層式路由4.6網際網路的路由RIPOSPFBGP4.7廣播與群播路由第四章:網路層和路由法4.1簡介4.5路由演算法網路層從傳送主機到接收主機傳輸的資料分段在傳送端將資料分段封裝在資料段中在接收端，將資料分段傳送到傳輸層每一台主機、路由器中都有網路層協定路由器會檢查經過它的所有IP資料段中的標頭欄位網路層資料連結層實體層網路層資料連結層實體層網路層資料連結層實體層網路層資料連結層實體層網路層資料連結層實體層網路層資料連結層實體層網路層資料連結層實體層網路層資料連結層實體層應用層傳輸層網路層資料連結層實體層應用層傳輸層網路層資料連結層實體層網路層從傳送主機到接收主機傳輸的資料分段應用層應用層主要的網路層功能轉送:

將封包從路由器的輸入轉送到適當的路由器輸出路由:

決定封包從來源端到目的端的路由路由演算法比方:路由:計畫從來源到目的旅行的過程轉送:

經過單一交流道的過程主要的網路層功能轉送:將封包從路由器的輸入轉送到適當的路由1230111到達封包的標頭值路由演算法本機演算法標頭值輸出連結01000101011110013221路由與轉送之間的交互作用1230111到達封包路由演算法本機演算法標頭值輸出連結01建立連線在某些網路架構中的第三個重要功能:ATM,framerelay,X.25在資料段傳送之前，兩個主機以及介於其間的路由器先建立虛擬連線路由器介入網路層以及傳輸層的連線服務:網路層:

兩個主機之間傳輸層:

兩個行程之間建立連線在某些網路架構中的第三個重要功能:網路服務模型Q:

有哪些服務模型提供給從傳送端到接收端傳輸資料段的通道?個別資料段的服務範例:傳送保證小於40毫秒的傳送保證資料段流量的服務範例:依序封包傳送流量的最低頻寬保證限制兩個封包之間間隔的改變網路服務模型Q:有哪些服務模型提供給從傳送端到接收端傳輸資網路層服務模型:網路架構網際網路ATMATMATMATM服務模型盡全力服務CBRVBRABRUBR頻寬無常數速率保證速率保證最小速率無遺失無有有無無排序無有有有有時序無有有無無壅塞指示無(藉由遺失來推論)不發生壅塞不發生壅塞有無保證?網路層服務模型:網路服務頻寬遺失排序時序壅塞保證?第四章:網路層和路由法4.1簡介4.2虛擬線路和資料段網路4.3路由器的內部為何4.4IP:網際網路協定資料段格式IPv4的定址法網際網路控制訊息協定(ICMP)IPv64.5路由演算法連結狀態距離向量階層式路由4.6網際網路的路由RIPOSPFBGP4.7廣播與群播路由第四章:網路層和路由法4.1簡介4.5路由演算法網路層連線以及非預接式服務資料段網路提供網路層的非預接式服務VC網路提供網路層的連線服務可與傳輸層服務類比，但是:服務:主機對主機沒有選擇性:網路只提供其中一個實作:在核心網路層連線以及非預接式服務資料段網路提供網路層的非預接式服務虛擬線路在資料開始傳送前，必須為每個連結建立連線，拆除每個封包會承載一個VC識別碼(並非目的端主機位址)在來源對目的的路徑上，每個路由器都必須維護每個經過的連線的「狀態」連結和路由器的資源(頻寬、緩衝區)可能會配置給VC“來源端到目的端的路徑，如同電話線路”效能良好沿著來源端到目的端路徑的網路行為虛擬線路在資料開始傳送前，必須為每個連結建立連線，拆除“來源VC實作一個VC包含了:一條來源端至目的端間的路徑VC編號，路徑上的每一個連結都有一個編號路徑上的每一個路由器轉送表中的紀錄一個屬於虛擬線路的封包會載送一個VC編號在每一個連結，VC編號必須改變新的VC編號從轉送表中得來VC實作一個VC包含了:轉送表122232123VC編號介面號碼進入介面進入VC編號離開介面

離開介面號碼11232226311837217197387…………美國西部路由器的轉送表:路由器維護連線狀態資訊!轉送表122232123VC編號介面號碼進入介面虛擬線路:訊號協定用來設定,維護及拆除VC用在ATM,frame-relay,X.25並沒有用在現今的網際網路中應用層傳輸層網路層資料連結層實體層應用層傳輸層網路層資料連結層實體層1.初始連線2.進入連線請求3.接受連線4.連線建立5.開始傳送資料6.接受資料虛擬線路:訊號協定用來設定,維護及拆除VC應用層應用層資料段網路在網路層不需要建立連線路由器:沒有終端對終端的連線狀態沒有網路層的「連線」觀念使用目的端主機位址傳送封包在同一對來源-目的端之間的封包可能會使用不同的路徑應用層傳輸層網路層資料連結層實體層應用層傳輸層網路層資料連結層實體層1.送出資料2.接收資料資料段網路在網路層不需要建立連線應用層應用層1.送出資料2轉送表

目的端位址區塊

連結介面11001000000101110001000000000000

至01100100000010111000101111111111111001000000101110001100000000000

至11100100000010111000110001111111111001000000101110001100100000000

至211001000000101110001111111111111

其它340億個可能的紀錄轉送表目的端位址區塊最長前置代碼對應

前置代碼對應

連結介面110010000001011100010011001000000101110001100011100100000010111000112

其他3DA:11001000000101110001100010101010範例DA:11001000000101110001011010100001哪一個介面?哪一個介面?最長前置代碼對應資料段或VC網路:為什麼?網際網路電腦之間的資料交換“彈性的”服務,沒有嚴格的時限要求“聰明的”終端系統(電腦)能夠適應、執行控制、錯誤復原網路內部是簡單的，邊緣是複雜的許多連結型態不同的特質統一的服務困難ATM來自電話系統人類的對話:嚴格的時限,可靠性的要求保證服務的需求“愚笨的”終端系統電話網路內部是複雜的資料段或VC網路:為什麼?網際網路ATM第四章:網路層和路由法4.1簡介4.2虛擬線路和資料段網路4.3路由器的內部為何？4.4IP:網際網路協定資料段格式IPv4的定址法網際網路控制訊息協定(ICMP)IPv64.5路由演算法連結狀態距離向量階層式路由4.6網際網路的路由RIPOSPFBGP4.7廣播與群播路由第四章:網路層和路由法4.1簡介4.5路由演算法路由器架構綜觀兩個主要的路由器功能:

執行路由演算法/協定(RIP,OSPF,BGP)將資料段從輸入轉送到輸出連結路由器架構綜觀兩個主要的路由器功能:輸入埠功能非集中式的交換:

給定一個資料段目的端，使用輸入埠記憶體中的轉送表來尋找輸出埠目標:以「連線速度」完成輸入埠的處理過程排隊:假如資料段的抵達速率快於轉送進入交換結構的速率實體層:位元層級的接收資料連結層:例如,乙太網路見第五章輸入埠功能非集中式的交換:實體層:資料連結層:三種交換結構三種交換結構經由記憶體的交換機制第一代的路由器:

傳統的電腦，在CPU的直接控制下完成交換動作封包複製到系統記憶體

速度會被記憶體頻寬所限制(一個資料段會經過兩次匯流排)輸入埠輸出埠記憶體系統匯流排經由記憶體的交換機制第一代的路由器:輸入埠輸出埠記憶體系統匯經由匯流排的交換機制資料段經由共享的匯流排從輸入埠記憶體送到輸出埠記憶體匯流排的競爭:

交換速度受限於匯流排頻寬1Gbps匯流排,Cisco1900:對存取及企業路由器是足夠的(非地區的或骨幹的)經由匯流排的交換機制資料段經由共享的匯流排從輸入埠記憶體送到經由互連網路的交換機制克服匯流排的頻寬限制Banyan網路，其他的互連網路初始的建立，是將處理器連接到多處裡器更進一步的設計:將資料段分割成固定長度的封包單位，將封包單位送入交換結構中Cisco12000:經由互連網路可達Gbps的交換速率經由互連網路的交換機制克服匯流排的頻寬限制輸出埠需要緩衝區，當資料段抵達結構的速率大於傳送速率排程原則選擇佇列中的資料段加以傳送輸出埠需要緩衝區，當資料段抵達結構的速率大於傳送速率輸出埠佇列當經由交換器抵達的速率超過輸出連結的速度佇列排隊(延遲)以及因為輸出埠的緩衝區溢出導致的遺失!輸出埠佇列當經由交換器抵達的速率超過輸出連結的速度輸入埠佇列結構速度慢於輸入埠的加總->可能在輸入佇列發生排隊的情形連線前端(HOL)阻塞:

在佇列最前端排隊的資料段會阻止佇列中的其他資料往前移動佇列延遲以及導因於輸入緩衝區溢出的遺失!輸入埠佇列結構速度慢於輸入埠的加總->可能在輸入佇列發生第四章:網路層和路由法4.1簡介4.2虛擬線路和資料段網路4.3路由器的內部為何4.4IP:網際網路協定資料段格式IPv4的定址法網際網路控制訊息協定(ICMP)IPv64.5路由演算法連結狀態距離向量階層式路由4.6網際網路的路由RIPOSPFBGP4.7廣播與群播路由第四章:網路層和路由法4.1簡介4.5路由演算法網際網路的網路層轉送表主機，路由器的網路層功能:路由協定路徑選擇RIP,OSPF,BGPIP協定定址原則資料段格式封包處理原則ICMP協定錯誤回報路由器“訊號”傳輸層:TCP,UDP連結層實體層網路層網際網路的網路層轉送表主機，路由器的網路層功能:路由協定IP第四章:網路層和路由法4.1簡介4.2虛擬線路和資料段網路4.3路由器的內部為何4.4IP:網際網路協定資料段格式IPv4的定址法網際網路控制訊息協定(ICMP)IPv64.5路由演算法連結狀態距離向量階層式路由4.6網際網路的路由RIPOSPFBGP4.7廣播與群播路由第四章:網路層和路由法4.1簡介4.5路由演算法IP資料段格式版本資料段長度32位元資料(不固定長度，通常是TCP或UDP資料分段)16位元的識別碼網際網路檢查和生存期32位元來源端IP位址IP協定版本號碼標頭長度(位元組)剩餘站數的最大數量(經過每一個路由器時減1)用來分割/重組資料段總長度(位元組)傳送資料部分時所使用的上層協定標頭長度服務類型資料的“類型”

旗標分割偏移量上層協定32位元目的端IP位址選項欄位(如果有的話)例如.時間戳記,路由紀錄,拜訪的路由器特定列表TCP有多少資源負擔?20位元組TCP20位元組IP=40位元組+應用層的訊息負擔IP資料段格式版本資料段長度32位元資料16位元的識別碼IP分割與重組網路連結層具有MTU(最大的可傳輸大小)–最大的連結層訊框不同的連結層型態，不同的MTU過大的IP資料段在網路內被切分(分割)一個資料段變成好幾個資料段只在終點被“重組”IP標頭位元用來識別，排序相關的分割分割:in:1個大的資料段out:3個小的資料段重組IP分割與重組網路連結層具有MTU(最大的可傳輸大小)IP分割與重組ID=xoffset=0fragflag=0length=4000ID=xoffset=0fragflag=1length=1500ID=xoffset=185fragflag=1length=1500ID=xoffset=370fragflag=0length=1040一個大的資料段變成數個小的資料段範例4000位元組的資料段MTU=1500位元組資料欄位中有1480個位元組偏移量=1480/8IP分割與重組IDoffsetfragflaglengthI第四章:網路層和路由法4.1簡介4.2虛擬線路和資料段網路4.3路由器的內部為何4.4IP:網際網路協定資料段格式IPv4的定址法網際網路控制訊息協定(ICMP)IPv64.5路由演算法連結狀態距離向量階層式路由4.6網際網路的路由RIPOSPFBGP4.7廣播與群播路由第四章:網路層和路由法4.1簡介4.5路由演算法IP定址法:簡介IP位址:32位元的識別碼，做為主機、路由器的介面介面:

在主機/路由器以及實體連結的交界處路由器通常擁有多個介面主機通常擁有一個介面IP位址代表每個介面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=11011111000000010000000100000001223111IP定址法:簡介IP位址:32位元的識別碼，做為主機子網路IP位址:

子網路部分(高階位元)主機部分(低階位元)什麼是子網路?IP具有相同子網路部分的裝置介面可以在沒有路由器的狀況下，實體地互相連結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個子網路的網路子網路子網路IP位址:223.1.1.1223.1.1.222子網路223.1.1.0/24223.1.2.0/24223.1.3.0/24方法要決定子網路,將每一個介面和它的主機或路由器分開，建立分離的網路。每一個分離的網路稱為一個子網路。子網路遮罩:/24子網路223.1.1.0/24223.1.2.0/24223子網路有幾個?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.2子網路有幾個?223.1.1.1223.1.1.3223.1IP位址:CIDRCIDR:

無分級領域間路由法(ClasslessInterDomainRouting)位址內任意長度的子網路部分位址格式:a.b.c.d/x，其中x是位址的子網路部份的位元數量1100100000010111

0001000000000000子網路部分主機部分200.23.16.0/23IP位址:CIDRCIDR:無分級領域間路由法1100IP位址:如何取得?Q:

主機要如何取得IP位址?手動設定在系統管理的檔案中Wintel:控制台->網路->設定->tcp/ip->屬性UNIX:/etc/rc.configDHCP:

動態主機配置協定(DynamicHostConfigurationProtocol):動態地由伺服器取得位址“隨插即用”(在下一章介紹)IP位址:如何取得?Q:主機要如何取得IP位址?IP位址:如何取得?Q:

網路要如何取得IP位址的子網路部分?A:

從ISP的位址空間中取得分配的部分ISP區塊11001000000101110001000000000000200.23.16.0/20組織011001000000101110001000000000000200.23.16.0/23組織111001000000101110001001000000000200.23.18.0/23組織211001000000101110001010000000000200.23.20.0/23...…..….….組織711001000000101110001111000000000200.23.30.0/23

IP位址:如何取得?Q:網路要如何取得IP位址的子網路部階層式定址法:路由集成“將任何位址開頭是200.23.16.0/20的訊息傳給我”200.23.16.0/23200.23.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......階層式定址允許有效率的路由資訊傳播:階層式定址法:路由集成“將任何位址開頭是200.23.16階層式定址法:更特定的路徑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.0.0/16或200.23.18.0/23的訊息傳給我”200.23.20.0/23組織2......階層式定址法:更特定的路徑ISPs-R-Us擁有更特定的IP位址:最後...Q:ISP如何取得一塊位址?A:ICANN:InternetCorporationforAssigned

NamesandNumbers配置位址管理DNS分派領域名稱，解決爭論IP位址:最後...Q:ISP如何取得一塊位址?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的來源及主機位址(一般而言)所有離開區域網路的資料段都具有相同的單一來源NATIP位址：138.76.29.7，不同的來源埠號NAT:網路位址轉譯10.0.0.110.0.0.210.NAT:網路位址轉譯動機:

區域網路對外界而言，通常只有一個IP位址:不需要從ISP取得一個範圍的位址：只需要一個位址即可應付所有裝置不需要通知外界，即可改變區域網路中的裝置位址不需要改變區域網路內的裝置位址，即可變更ISP區域網路內的裝置不需要明顯地被外面的世界定址、見到(增加安全性)NAT:網路位址轉譯動機:區域網路對外界而言，通常只有一個NAT:網路位址轉譯實作:NAT路徑必須:

送出的資料段:更換每一個送出的資料段(來源IP位址,埠號)成為(NATIP位址,新埠號)...遠端用戶端/主機會使用(NATIP位址,新埠號)做為目的端位址，來做回應

記憶(在NAT轉譯表中)每一個(來源端IP位址,埠號)到(NATIP位址,新埠號)的轉譯對應

進入的資料段:更換每個進入資料段目的欄位中的(NATIP位址,新埠號)為儲存在NAT表中的對應(來源端IP位址,埠號)NAT:網路位址轉譯實作:NAT路徑必須:

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:host10.0.0.1傳送資料段到128.119.40.186,80NAT轉譯表廣域網路端位址

區域網路端位址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,3345

NAT:網路位址轉譯10.0.0.110.0.0.210.0NAT:網路位址轉譯16-位元的埠號欄位:利用單一的區域端位址，可提供60,000個同時連線!NAT是具有爭議性的:路由器只應處理到第三層違反端點到端點的主張NAT可能會列入應用程式的設計考量，例如P2P應用程式位址不足的問題應該由IPv6來解決NAT:網路位址轉譯16-位元的埠號欄位:第四章:網路層和路由法4.1簡介4.2虛擬線路和資料段網路4.3路由器的內部為何4.4IP:網際網路協定資料段格式IPv4的定址法網際網路控制訊息協定(ICMP)IPv64.5路由演算法連結狀態距離向量階層式路由4.6網際網路的路由RIPOSPFBGP4.7廣播與群播路由第四章:網路層和路由法4.1簡介4.5路由演算法ICMP:網際網路訊息控制協定主機和路由器使用來互相傳送網路層資訊的協定錯誤回報:無法到達主機,網路,埠號,協定回應請求/回覆(由ping所使用)網路層，在IP“之上”:ICMP訊息在IP封包中載送ICMP訊息:

類型,代碼，加上導致錯誤的IP資料段的前八個位元組類型

代碼

說明00回應訊息(ping)30目的端網路無法連上31目的端主機無法連上32目的端協定無法連上33目的端埠無法連上36目的端網路未知37目的端主機未知0來源抑制訊息(壅塞控制

–未使用)80回應請求(ping)90路由器通告100路由器搜尋中110TTL過期120IP標頭損毀ICMP:網際網路訊息控制協定主機和路由器使用來互相傳送網Traceroute與ICMP來源端傳送一系列的UDP資料分段給目的端第一個具有TTL=1第二個具有TTL=2,依此類推不可能的埠號當第n個資料段抵達第n個路由器:路由器刪除資料段接著傳送一個ICMP訊息給來源端(類型11,代碼0)訊息中包含了路由器名稱以及IP位址當ICMP訊息抵達時，來源端會計算RTTTraceroute會重複這個步驟三次停止的標準UDP資料分段最終會到達目的主機目的端會回傳ICMP“主機無法到達”封包(類型3,代碼3)當來源端收到這個ICMP時，則會停止Traceroute與ICMP來源端傳送一系列的UDP資第四章:網路層和路由法4.1簡介4.2虛擬線路和資料段網路4.3路由器的內部為何4.4IP:網際網路協定資料段格式IPv4的定址法網際網路控制訊息協定(ICMP)IPv64.5路由演算法連結狀態距離向量階層式路由4.6網際網路的路由RIPOSPFBGP4.7廣播與群播路由第四章:網路層和路由法4.1簡介4.5路由演算法IPv6一開始的動機:

32位元的位址空間很快就使用殆盡了其他的動機:標頭格式可以幫助處理/轉送更快速標頭的改變可以幫助QOSIPv6資料段格式:

固定長度的40位元組標頭不允許切割IPv6一開始的動機:32位元的位址空間很快就使用殆盡了IPv6標頭(續)優先權:

辨識資料流中，資料封包間的優先權資料流標記:

辨識同一個「資料流」中的資料封包(「資料流」的概念沒有良好的定義)下接標頭:

辨識資料的上層協定IPv6標頭(續)優先權:辨識資料流中，資料封包間的與IPv4的不同檢查和:

完全地移除，減少每一站的處理時間選項:

允許，但在標頭之外，由下接標頭指向ICMPv6:

新版本的ICMP增加訊息類型,例如“封包太大”群體廣播群組管理功能與IPv4的不同檢查和:完全地移除，減少每一站的處理時從IPv4轉換成IPv6並不是所有的路由器可以同時升級無法使用“F日”假如網路的運作混和了IPv4和IPv6的路由器會如何？建立通道:

在IPv4資料段的承載資料中，封裝完整的IPv6資料段，送往IPv4路由器。從IPv4轉換成IPv6並不是所有的路由器可以同時升級建立通道ABEFIPv6IPv6IPv6IPv6通道邏輯面:實際面:ABEFIPv6IPv6IPv6IPv6IPv4IPv4建立通道ABEFIPv6IPv6IPv6IPv6通道邏輯面:建立通道ABEFIPv6IPv6IPv6IPv6通道邏輯面:實際面:ABEFIPv6IPv6IPv6IPv6CDIPv4IPv4資料流: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裡面建立通道ABEFIPv6IPv6IPv6IPv6通道邏輯面:第四章:網路層和路由法4.1簡介4.2虛擬線路和資料段網路4.3路由器的內部為何4.4IP:網際網路協定資料段格式IPv4的定址法網際網路控制訊息協定(ICMP)IPv64.5路由演算法連結狀態距離向量階層式路由4.6網際網路的路由RIPOSPFBGP4.7廣播與群播路由第四章:網路層和路由法4.1簡介4.5路由演算法1230111抵達封包的標頭值路由演算法區域轉送表標頭值輸出連結01000101011110013221路由和轉送的交互作用1230111抵達封包的標頭值路由演算法區域轉送表標頭值輸出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圖形:G=(N,E)抽抽象化圖形:成本uyxwvz2213112535

c(x,x’)=連結(x,x’)的成本-例如，c(w,z)=5

成本可能永遠是1，或是相反地與頻寬相關，或是相反地與壅塞程度相關路徑(x1,x2,x3,…,xp)的成本=c(x1,x2)+c(x2,x3)+…+c(xp-1,xp)問題:u和z之間的最小成本路徑為何?路由演算法:尋找最小成本路徑的演算法抽象化圖形:成本uyxwvz2213112535c(x,路由演算法的分類整體或分散式資訊?整體的:所有的路由器都擁有完整的拓樸及連結成本資訊“連結狀態”演算法分散式:

路由器知道實體連結的鄰居以及到鄰居的連結成本反覆地計算，以及與鄰居交換資訊“距離向量”演算法靜態的或動態的?靜態的:

路徑隨著時間緩慢地改變動態的:

較快速地改變路徑周期性的更新回應連結成本的改變路由演算法的分類整體或分散式資訊?靜態的或動態的?第四章:網路層和路由法4.1簡介4.2虛擬線路和資料段網路4.3路由器的內部為何4.4IP:網際網路協定資料段格式IPv4的定址法網際網路控制訊息協定(ICMP)IPv64.5路由演算法連結狀態距離向量階層式路由4.6網際網路的路由RIPOSPFBGP4.7廣播與群播路由第四章:網路層和路由法4.1簡介4.5路由演算法連結狀態路由演算法Dijkstra演算法已知所有節點的網路拓樸，連結成本經由「連結狀態廣播」完成每個節點都擁有一樣的資訊從一個節點(來源端)開始，到所有其他節點，計算最小成本路徑給定此節點的轉送表迴圈的:在k次迴圈以後，會知道k個目的節點的最小成本路徑符號:c(x,y):

從節點x到y的連結成本;=∞假如不是直接的鄰居D(v):

從來源端到目的端v目前的路徑成本值p(v):

沿著路徑上，從來源端到v的前一個節點N‘:

一組最小成本路徑已知的節點連結狀態路由演算法Dijkstra演算法符號:Dijsktra演算法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/*newcosttoviseitheroldcosttovorknown14shortestpathcosttowpluscostfromwtov*/15untilallnodesinN'

Dijsktra演算法1Initialization:Dijkstra演算法:範例Step012345N'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,yuyxwvz2213112535Dijkstra演算法:範例StepN'D(v),p(vDijkstra演算法:範例(2)uyxwvz結果：從u開始的最短路徑樹:vxywz(u,v)(u,x)(u,x)(u,x)(u,x)目的連結結果：u的轉送表Dijkstra演算法:範例(2)uyxwvz結果：Dijkstra演算法，討論演算法複雜度:n個節點每個迴圈:需要確認不在N中的每個節點wn(n+1)/2個比較:O(n2)可能更有效率的實作:O(nlogn)可能的擺動:例如，連結成本=該連結的載送負荷ADCB11+ee0e1100ADCB2+e0001+e1ADCB02+e1+e100ADCB2+e0e01+e1初始…重新計算路由…重新計算…重新計算Dijkstra演算法，討論演算法複雜度:n個節點AD第四章:網路層和路由法4.1簡介4.2虛擬線路和資料段網路4.3路由器的內部為何4.4IP:網際網路協定資料段格式IPv4的定址法網際網路控制訊息協定(ICMP)IPv64.5路由演算法連結狀態距離向量階層式路由4.6網際網路的路由RIPOSPFBGP4.7廣播與群播路由第四章:網路層和路由法4.1簡介4.5路由演算法距離向量演算法Bellman-Ford方程式(動態程式)定義dx(y):=從x到y之最小成本路徑的成本則dx(y)=min{c(x,v)+dv(y)}其中min符號作用於x的所有相鄰節點v距離向量演算法Bellman-Ford方程式(動態程式Bellman-Ford範例uyxwvz2213112535清楚地,dv(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方程式說:Bellman-Ford範例uyxwvz22131125距離向量演算法Dx(y)=從x到y的預估最小成本距離向量:Dx=[Dx(y):yєN]節點x知道到每一個鄰居v的成本:c(x,v)節點x維護Dx=[Dx(y):yєN]節點x也維護它的鄰居的距離向量對每一個鄰居v,x維護

Dv=[Dv(y):yєN]距離向量演算法Dx(y)=從x到y的預估最小成距離向量演算法(4)基本想法:

每一個節點定期地傳送它自己的距離向量預估值給鄰居節點當一個節點x收到來自鄰居的新DV預估值，它會使用B-F方程式更新它自己的DV:Dx(y)←minv{c(x,v)+Dv(y)}對每一個節點

y∊N在一般的自然狀況下，預估的Dx(y)會涵蓋真正的最小成本

dx(y)距離向量演算法(4)基本想法:Dx(y)←minv{距離向量演算法(5)反覆的,非同步的:每一個地區性的迴圈皆導因於：地區連結的成本改變來自鄰居的DV更新訊息分散的:每個節點只在它的DV改變時，才會通知它的鄰居假如必要，鄰居節點才會再通知它的鄰居等待(鄰居節點的地區連結成本改變訊息)重新計算預估值假如到任何一個目的端的DV改變了，通知鄰居節點每一個節點:距離向量演算法(5)反覆的,非同步的:每一個地區性的迴xyzxyz027∞∞∞∞∞∞來源節點目的節點來源節點來源節點xyzxyz023來源節點目的節點xyzxyz023來源節點目的節點xyzxyz∞∞∞∞∞目的節點xyzxyz027來源節點目的節點xyzxyz023來源節點目的節點xyzxyz023來源節點目的節點xyzxyz027來源節點目的節點xyzxyz∞∞∞710目的節點∞201∞∞∞201710201710201310201310201310201310時序xz127y節點x的表節點y的表節點z的表Dx(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}=3xyzxyz027∞∞∞∞∞∞來源節點距離向量:連結成本改變連結成本改變:節點偵測到區域連結成本的改變更新路由資訊，重新計算距離向量假如DV改變，通知鄰居節點“好消息會以快速傳遞！”xz1450y1在時間點t0，y偵測到連結成本的變更，它會更新距離向量，並通知相鄰節點在時間點t1，z接收來自y的更新訊息，更新自己的表格。它會計算出到x的新最小成本，並傳送給相鄰節點在時間點t2，y會接收到z的更新訊息，並且更新自己的距離表格。因為y的最小成本並沒有改變，所以y不會傳送任何訊息給z。距離向量:連結成本改變連結成本改變:“好消息會xz1450距離向量:連結成本改變連結成本改變:好消息會以快速傳遞！壞消息會以慢速傳遞-“計算到無限大”的問題!在演算法穩定之前，需要44次迴圈:見課文抑制反轉:

假如Z經由Y到達目的端X:Z告訴Y它(Z)到達X的距離是無限大(因此Y不會試著經由Z到達X)這個方法是否能完全解決「計算到無限大」的問題呢？xz1450y60距離向量:連結成本改變連結成本改變:xz1450y60LS與DV演算法的比較訊息複雜度LS:n個節點,E條連結,O(nE)個傳送出去的訊息DV:只在鄰居之間交換收斂時間不固定收斂速度LS:O(n2)演算法需要O(nE)個訊息可能有擺動DV:收斂速度不固定可能產生路由迴圈計算到無窮大的問題強健性:

假如路由器故障會發生什麼問題?LS:

節點可能會廣播不正確的連結成本每個節點只計算它自己的轉送表DV:DV節點可能會廣播不正確的路徑成本每個節點的轉送表也被其他人所使用將錯誤傳播到網路中LS與DV演算法的比較訊息複雜度強健性:假如路由器故第四章:網路層和路由法4.1簡介4.2虛擬線路和資料段網路4.3路由器的內部為何4.4IP:網際網路協定資料段格式IPv4的定址法網際網路控制訊息協定(ICMP)IPv64.5路由演算法連結狀態距離向量階層式路由4.6網際網路的路由RIPOSPFBGP4.7廣播與群播路由第四章:網路層和路由法4.1簡介4.5路由演算法階層式路由規模:

具有兩億個目的端:無法將所有的目的端都儲存在路由器轉送表內!路由表的交換將會淹沒所有連結!

自治管理權網際網路=網路的網路每個網路的管理者也許會想要控制自己網路中的路由我們所研究的路由到目前為止–理想化所有的路由器都相同網路是“平面的”…在現實中並非如此階層式路由規模:具有兩億個目的端:自治管理權我們所研究的路階層式路由將路由器聚集成區域,“自治系統”(AS)同樣AS中的路由器會執行相同的路由協定“自治系統內部”路由協定在不同AS間的路由器可以執行不同的自治系統內部路由協定閘道路由器直接連結到另一個AS中的路由器階層式路由將路由器聚集成區域,“自治系統”(AS)閘道路3b1d3a1c2aAS3AS1AS21a2c2b1b自治系統內部路由演算法自治系統間路由演算法轉送表3c互相連結的AS轉送表由自治系統內部以及自治系統間的路由演算法兩者來設定自治系統內部路由協定設定內部目的端的紀錄自治系統間以及自治系統內部路由協定設定外部目的端的紀錄3b1d3a1c2aAS3AS1AS21a2c2b1b自治系3b1d3a1c2aAS3AS1AS21a2c2b1b3c自治系統間的任務假設AS1中的路由器收到一個資料段，它的目的端在AS1外部路由器應該要將封包轉送到其中一個閘道路由器，應該是哪一個？AS1需要:學習哪一個目的端可以經由AS2抵達，而哪一個可以經由AS3抵達要傳播這個資訊到AS1中的所有路由器自治系統間路由器的工作!3b1d3a1c2aAS3AS1AS21a2c2b1b3c自範例:設定路由器1d的轉送表假設AS1從自治系統間的路由協定學習到子網路

x

可以經由AS3(閘道路由器1c)抵達，但是不可由AS2抵達。自治系統間路由協定將這個資訊傳播到所有的內部路由器。路由器1d由自治系統內部的路由資訊決定，它的介面

I

在通往1c的最小成本路徑上。在轉送表中放入紀錄(x,I)。範例:設定路由器1d的轉送表假設AS1從自治系統間的路從自治系統間的路由協定得知子網路x可經由多個閘道到達使用自治系統內部的路由協定資訊以決定到達每個閘道之最小成本路徑的成本燙手山芋路由法：選擇最小成本為最低的閘道路由器。由轉送表決定連結到該最小成本閘道的介面I。在轉送表中輸入(x,I)。範例:由多個AS中做選擇現在假設AS1從自治系統間路由協定得知，子網路x

可以經由AS3以及AS2到達。要設定轉送表，路由器1d必須決定它要經由哪一個閘道路由器轉送到目的

x的封包。這也是自治系統間路由協定的工作!燙手山芋路由法:

將封包經由兩個路由器中較近的一個傳送。從自治系統間的路使用自治系統內部的路由協定資訊以決定到達每個第四章:網路層和路由法4.1簡介4.2虛擬線路和資料段網路4.3路由器的內部為何4.4IP:網際網路協定資料段格式IPv4的定址法網際網路控制訊息協定(ICMP)IPv64.5路由演算法連結狀態距離向量階層式路由4.6網際網路的路由RIPOSPFBGP4.7廣播與群播路由第四章:網路層和路由法4.1簡介4.5路由演算法自治系統內部路由法也稱為內部閘道協定

(IGP)最常見的自治系統內部路由協定:RIP:路由資訊協定OSPF:開放最短路徑優先IGRP:內部閘道路由協定(Cisco專利)自治系統內部路由法也稱為內部閘道協定(IGP)第四章:網路層和路由法4.1簡介4.2虛擬線路和資料段網路4.3路由器的內部為何4.4IP:網際網路協定資料段格式IPv4的定址法網際網路控制訊息協定(ICMP)IPv64.5路由演算法連結狀態距離向量階層式路由4.6網際網路的路由RIPOSPFBGP4.7廣播與群播路由第四章:網路層和路由法4.1簡介4.5路由演算法RIP(路由資訊協定)距離向量演算法包含在1982年的BSD-UNIXDistribution中距離計量:hop數目(最大=15個hop)DCBAuvwxyz目的端

轉送次數u1v2w2x3y3z2

從路由器A到不同的子網路:RIP(路由資訊協定)距離向量演算法DCBAuvwxyz目RIP廣播距離向量:每隔30秒使用回應訊息(也稱做通告)，在相鄰節點間交換每個通告:自治系統內最多達25個目的端子網路的清單RIP廣播距離向量:每隔30秒使用回應訊息(也稱做通告)，RIP:範例

目的端網路下一個路由器到目的端所需的轉送次數

w A 2

y B 2

z B 7

x -- 1 …. …. ....wxyzACDBD中的路由表RIP:範例目的端網路下一RIP:範例

目的端網路 下一個路由器

到目的端所需的轉送次數

w A 2

y B 2

z BA 75

x -- 1 …. …. ....D中的路由表wxyzACDB目的端下一個轉送次數

w -1

x -1z C4…. …...從A到D的通告RIP:範例目的端網路 下一個路由器RIP:連結失敗以及復原假如在180秒內沒有收到通告-->相鄰節點/連結宣告死亡經過相鄰節點的路由是無效的新的通告會被傳送給相鄰節點相鄰節點依序將新的通告傳送出去(假如路由表改變)連結失敗的訊息會很快地傳送到整個網路抑制反轉會用來防止來回反彈的迴圈(無限距離=16hops)RIP:連結失敗以及復原假如在180秒內沒有收到通告--RIP路由表的處理利用應用層行程來管理的RIP路由表稱為route-d(背景程式)通告以UDP封包傳送，會定期重複實體層l連結層網路層轉送表(IP)傳輸層(UDP)routed實體層連結層網路層(IP)傳輸層(UDP)routed轉送表RIP路由表的處理利用應用層行程來管理的RIP路由表稱為第四章:網路層和路由法4.1簡介4.2虛擬線路和資料段網路4.3路由器的內部為何4.4IP:網際網路協定資料段格式IPv4的定址法網際網路控制訊息協定(ICMP)IPv64.5路由演算法連結狀態距離向量階層式路由4.6網際網路的路由RIPOSPFBGP4.7廣播與群播路由第四章:網路層和路由法4.1簡介4.5路由演算法OSPF(開放最短路徑優先)“開放”:可公開取得使用連結狀態協定LS封包散佈每一個節點的拓樸圖使用Dijkstra演算法計算路由OSPF通告為每一個相鄰路由器載送一個紀錄通告散佈到整個

AS(藉著洪流法)直接經由IP載送OSPF訊息(而非TCP或UDP)OSPF(開放最短路徑優先)“開放”:可公開取得OSPF“進階”功能(不含在RIP中)安全性:

所有的OSPF訊息都需要認證(防止惡意入侵)允許多條相同成本路徑

(在RIP中只允許一條)對每一條連結，對不同的TOS允許多個成本計量

(例如，將衛星連結的成本設為「低」適用於盡全力服務；高適用於即時服務)整合支援單點廣播和群播路由:群播OSPF(MOSPF)使用與OSPF同樣的拓樸資料庫大領域中的階層式OSPFOSPF“進階”功能(不含在RIP中)安全性:所階層式OSPF階層式OSPF階層式OSPF兩個層級的階層:

區域，主幹連結狀態的廣播只在區域中每個節點都擁有區域的拓樸細節；對其他區域的網路只知道方向區域邊界路由器:

「總結」本身區域中到各網路的距離，通告到其他的區域邊界路由器主幹路由器:

執行限制在主幹區域內的OSPF路由自治系統邊界路由器:

連接到其它的AS階層式OSPF兩個層級的階層:區域，主幹第四章:網路層和路由法4.1簡介4.2虛擬線路和資料段網路4.3路由器的內部為何4.4IP:網際網路協定資料段格式IPv4的定址法網際網路控制訊息協定(ICMP)IPv64.5路由演算法連結狀態距離向量階層式路由4.6網際網路的路由RIPOSPFBGP4.7廣播與群播路由第四章:網路層和路由法4.1簡介4.5路由演算法網際網路自治系統間路由:BGPBGP(邊界閘道協定):

現存的標準BGP為每個AS提供以下功用:從相鄰的AS得到子網路的可到達資訊傳播可到達資訊給AS內部的所有路由器根據其可到達資訊以及AS策略決定一個到達子網路的「好」路徑允許一個子網路向網際網路的其餘部分通告它的存在:“我在這裡”網際網路自治系統間路由:BGPBGP(邊界閘道協定):BGP的基礎成對的路由器(BGP對等點)經由半永久性的TCP連結來交換路由資訊:BGP會談注意BGP會談並不一定相等於實體連線當AS2通告了一個前置代碼給AS1，AS2保證它會轉送任何想要到達該前置代碼位址的資料段至前往該位址的路徑上AS2可以整合它的通告中的前置代碼3b1d3a1c2aAS3AS1AS21a2c2b1b3c外部eBGP會談內部iBGP會談BGP的基礎成對的路由器(BGP對等點)經由半永久性散佈可達性的資訊經由閘道路由器3a和1c間的eBGP會談，AS3會傳送其可到達的前置代碼清單給AS11c接著可以使用iBGP將這個新的前置代碼的可到達資訊散佈到AS1的所有路由器中1b接著會經由1b到2a的eBGP會談，再通告這個新的可到達資訊給AS2當路由器學到一個新的前置代碼，它會在它的轉送表中為這個前置碼建立一個紀錄3b1d3a1c2aAS3AS1AS21a2c2b1b3ceBGP會談iBGP會談散佈可達性的資訊經由閘道路由器3a和1c間的eBG路徑屬性和BGP路由當通告一個前置代碼時，通告中會包含BGP屬性前置碼+屬性=“路由”兩個重要的屬性:AS-PATH:

包含了該前置碼通告已經通過的AS:AS67AS17NEXT-HOP:

指定到達下一個AS的特定自治系統間路由器(可能有數條實體連線從目前的AS到下一個AS)當閘道路由器接收到路由通告時，使用進口策略來決定接收/拒絕路徑屬性和BGP路由當通告一個前置代碼時，通告中會包含BGP路由選擇路由器可能得知到達某一前置代碼將有多於一條的路由。路由器必須選擇一個路由。消去法:區域偏好值屬性:策略決定最短AS路徑最近的下一站路由器:燙手山芋路由法其他的原則BGP路由選擇路由器可能得知到達某一前置代碼將有多於一條的BGP訊息BGP使用TCP交換訊息BGP訊息:OPEN:

開啟與對等點與認證傳送端的TCP連線UPDATE:

通告新的路徑(或抽掉舊的)KEEPALIVE

在缺少UPDATE的情況下，保持連線的存活；也用來確認OPEN訊息NOTIFICATION:

回報前一個訊息中的錯誤;也用來關閉連線BGP訊息BGP使用TCP交換訊息BGP路由策略A,B,C為提供者網路X,W,Y為用戶網路(提供者網路的)X為雙位址:

連接到兩個網路X不想讓B知道經由X到C的路徑..因此X不會通知B有到C的路徑BGP路由策略A,B,C為提供者網路BGP路由策略(2)A通告B路徑AWB通告X路徑BAWB應該要通告C路徑BAW嗎?當然不!B沒有任何的收入來自路由CBAW，因為W和C都不是B的客戶。B想要強制C經由A來路由B想要只到/從它的客戶來路由!BGP路由策略(2)A通告B路徑AW為什麼會有不同的AS之間和AS內部路由協定?

策略:

在AS之間:管理者希望控制它的資料流路由的方式，以及哪些資料流經它的網路路由。在AS內部:單一的管理,因此不需要策略決定規模:階層式的路由能節省路由表大小，減少更新訊息的資料量效能:

在AS內部:能夠集中在效能的考量上在AS之間:策略的考量在效能之上為什麼會有不同的AS之間和AS內部路由協定?策略:第四章:網路層和路由法4.1簡介4.2虛擬線路和資料段網路4.3路由器的內部為何4.4IP:網際網路協定資料段格式IPv4的定址法網際網路控制訊息協定(ICMP)IPv64.5路由演算法連結狀態距離向量階層式路由4.6網際網路的路由RIPOSPFBGP4.7廣播與群播路由第四章:網路層和路由法4.1簡介4.5路由演算法R1R2R3R4來源端複製R1R2R3R4網路中複製複製建立/傳送複製複製廣播路由從來源端傳送封包到所有其他的節點來源端複製是不足的:來源端複製:來源端要如何決定接收位址?R1R2R3R4來源端複製R1R2R3R4網路中複製複製複製網路中複製洪流法:當節點收到廣播封包時，會複製給它所有的鄰居問題:循環以及廣播風暴受控制的洪流