Microsoft PowerPoint - cha5-3 [相容模式]

Transcription

1 Outline Routing Protocol Router 的運作 Routing Protocol GGP EGP IGP Case Studies 1 2 路由器 (Router) Router 通訊協定架構 Router 用於連接 LLC 不同, 但 Network Layer 及上層都相同的網路 Host A Application Host B Application Internet 以 Routers 做為中繼站, 穿越各個網路轉送 Packet 企業內部以 Routers 做為子網路交換 Packet 的中心 Presentation Session Transport Network Data Link Router Function Network Data LinkData Link Presentation Session Transport Network Data Link Physical PHY PHY Physical 3 LAN 1 LAN 2 4

2 Routers 的運作 Router R2 路由表 讀取收到的 Packet 上的 IP 位址, 查詢路由表 (Routing Table), 以得知應從那一個 Port 將 Packet 送出 Router 必須了解兩個協定的 PHY Data Link Layers, 以便和兩個子網路溝通和進行封包的轉換 依據 Routing Table,Router 會選擇到 Destination 有最短路徑的網路介面, 將 Datagram 傳給 Next Hop 5 6 路由器 R2 的路由資訊 Core Gateway ( 核心閘道器 ) 與 Non-core Gateway ( 非核心閘道器 ) 早期 Internet 剛發展時, 各區域網路和廣域網路中的研究機構, 是以 ARPANET 為主幹, 並利用 Gateway 來連接 Internet Gateway 可分為兩種 : 一種是 core gateway, 另一種是 non-core gateway Core gateway 是由 Internet Network Operating Center ( 網路操作中心 ) 負責管理的, 它提供了所有目的地主機可靠而一致的網路路徑 對於每個 internet 網路上的主機位址,core gateway 都必須知道 而 core gateway 和 core gateway 間的資訊也必須隨時交流, 以保持網路路徑資訊的可靠性和一致性 7 8

3 Core Gateway and Non-core Gateway (Cont.) Non-core gateway 由個別群組或團體來管理和控制, 類似 地方自治 記錄的路徑表可以說是區域性的, 也就是其所管理的區域網路部分 區域性閘道器 核心閘道器 區域性閘道器 Backbone Network 區域性閘道器 核心閘道器 9 GGP (Gateway to Gateway Protocol) 核心閘道器間交換路徑資訊的協定 由於 core gateway 是由 Internet Network Operation Center 所負責監控, 因此外界其他的閘道器並不能干擾其路徑資訊的交換 新的 core gateway 要加入系統時, 它會分配數個與它相鄰的 core gateway, 用來互相交換資訊 新的 core gateway 只需告訴 neighbor core gateway 其所能達到的網路目的地路徑資訊, neighbor core gateway 便可廣播新的網路路徑資訊給其他的 core gateway 10 GGP (Cont.) Routing Table in a Core Gateway 使用 向量距離 (distance vector) 作為網路系統距離的量測 向量距離包括兩個基本元素 (N,D) N 表示閘道器的目的地, 可能是某網路或主機 D 表示與目的地的距離 我們是以 hop 的數目作為距離的單位 hop: 資料傳輸過程所經過的閘道器數目 若閘道器與某網路直接相連, 則距離為

4 Routing Table in a Core Gateway (Cont.) GGP 訊息 包括四種類型 : 路徑更新訊息 確認訊息 要求回應與回應答覆訊息 每一種類型的格式可以由 type 這個欄位來區分 GGP 路徑更新訊息 GGP 路徑更新訊息 (Cont.) Type=12, 表示此訊息是屬於路徑更新的訊息 SEQUENCE NUMBER: 傳送端與接收端此欄位必須相同, 用以檢查訊息的傳輸是否正確 UPDATE: 表示接收端是否要由傳送端更新路徑資訊 NUMBER DISTANCES: 此訊息中要更新的距離群組數目 (Ex: group=n) DISTANCE D1: 表示與傳送的核心閘道器距離為 D1 NUMBER NETS AT D1: 表示與傳送的核心閘道器距離數為 D1 的網路數目 15 16

5 GGP 路徑更新訊息 (Cont.) X NET AT DISTANCE D1: 表示第 X 個與傳送的核心閘道器距離數為 D1 的網路, 其網路的部分 IP address, 這個欄位的長度為 1~3 bytes, 是依照該網路是屬於 A 或 B 或 C Class 而定 GGP 確認訊息 當核心閘道器收到路徑更新訊息後, 會回傳一個 GGP 確認訊息給傳送訊息的閘道器 此訊息依判斷路徑更新訊息是否無誤而分成兩種 : TYPE 2:(Positive acknowledgement) 10:(Negative acknowledgement) UNUSED(0) SEQUENCE NUMBER GGP 確認訊息 (Cont.) 在肯定確認訊息的 SEQUENCE 欄位, 表示此次確認為正確的訊息序號 而否定確認訊息的 SEQUENCE 欄位, 表示上一次確認為正確的訊息序號 測試與回應訊息 GGP 中提共了一組訊息用來測試各核心閘道器的鄰近閘道器是否可正常回應訊息 TYPE 0: Echo Request 8: Echo Reply UNUSED(0) 19 20

6 GGP 介面狀態訊息 GGP 提供一種測試核心閘道器與各區域網路間介面是否通訊正常 其 TYPE=9 網路擴充的問題 使用非核心閘道器會發生額外 hops 的問題, 這會降低網路的效率 Ex: G2->G3 needs to go to G1 first 網路擴充的問題 (Cont.) Autonomous System 核心閘道器是不能隨便增加的, 隨意增加核心閘道器對網路效能有很大的影響 核心閘道器也無法容納網路數目的快速增加 對於不同的網路群組, 其管理的方式可能不同, 若是直接由一單一核心閘道器處理, 會使核心閘道器的管理更不易 因此必須有自主系統, 採分層負責的方式 23 自主系統 (Autonomous System AS): 由多個網路和閘道器所組成, 每個自主系統有其單一的管轄機構 在一定的範圍內使用單一的技術來管理一群路由器 Autonomous System 是自然形成, 自己管理自己的一個網路系統 or 子網路 各 Autonomous System 必須有和核心閘道器交換路經資訊的能力, 並自行決定自己的 Routing Paths 24

7 Autonomous System (Cont.) Autonomous System (Cont.) 自治系統藉由所謂的自治系統號碼 (AS Number) 來辨識是否在同一個自治系統內 自治系統號碼是由 IANA (Internet Assigned Number Authority) 單位負責管理, 它在全球各個大區域都有負責管理 AS 號碼的組織 例如負責管理亞太各國申請 AS 號碼的單位是 AP- NIC (Asia Pacific NIC) 組織 自治系統號碼是一個 16 bit 的位址 (0~65535), 是不可重覆的, 它是給一群 router 使用的 另外,IANA 保留 64512~65535 給私有的網路使用 Routing Protocol Routing Protocol (Cont.) Routers 之間使用 Routing Protocol 來交換網路的資訊 兩大類的 Routing Protocol: EGP(Exterior Gateway Protocol): 用於讓 Autonomous Systems 間互相交換 Routing Information 的 Protocol It allows various politics to be enforced in the interas traffic. A corporate AS might want the ability to send packets to any internet site and receive packets from any internet site. However, it might be unwilling to carry transit packets originating in a foreign AS and ending in a different foreign AS, even if its own AS was on the shortest path between two 27 foreign ASs. On the other hand, it might be willing to carry transit traffic for its neighbors, or even specific Ass that paid it for this service. For example, a telephone company might be happy to act as a carrier for their customers, but no for others. Typical policies: No transit traffic through certain ASes. Never put Iraq on a route starting at the Pentagon. Do not use the United States to get from British Columbia to Ontario ( 安大略 ). Traffic starting or ending at IBM should not transit Microsoft. 28

8 Routing Protocol (Cont.) BGP IGP(Interior Gateway Protocol): 用於 Autonomous System 內部交換路徑的 Protocol 目的是從 source 到 destination 盡量有效率的遞送封包 內部使用 IGP 1 Autonomous System 1 使用 EGP Autonomous System 2 內部使用 IGP 2 29 Exterior Gateway Protocol( 外部選徑協定 ), 目前使用最多的是 BGP (Border Gateway Protocol) 依據 BGP 處理過路封包 (transit traffic) 的特性, 網路可分為三類 : stub network: 與其他 AS 只有一個連接, 無法傳遞過路的封包 multi-connected network: 可用來傳遞過路的封包, 但也有權力拒絕 transit network: 通常是 backbone, 願意處理來自其他來源的封包, 但可能有些許的限制 30 IGP 九種 EGP 訊息 Interior Gateway Protocol( 內部選徑協定 ) IGP refers to any algorithm that interior routers use when they exchange network reachability an routing information. EGP 訊息 Acquisition Request Acquisition Confirm Acquisition Refuse Case Request 代表意義請求閘道器作為鄰機對 Acquisition 的肯定回應對 Acquisition 的否定回應請求終止和鄰機的關係 內部使用 IGP 1 使用 EGP Case Confirm Poll Request 確認終止的回應輪流詢問的請求 Autonomous System 1 Autonomous System 2 內部使用 IGP 2 Routing Update Request Hello I Heard You 路徑更新請求對鄰機發出 Hello 訊息鄰機對 Hello 訊息之回應 31 32

9 EGP 訊息格式 Version:EGP 訊息的版本 TYPE: 用來區分訊息的類型 CODE: 識別子類型的訊息 EGP 訊息格式 (Cont.) STATUS: 包含所依據訊息的型態其狀態的資訊 CHECKSUM: 驗證資訊的傳輸是否正確 演算法和 TCP 協定的類似 AUTONMOUS SYSTEM NUMBER: 用來識別訊息所屬的自治系統 SEQUENCE NUMBER: 識別不同的 EGP 訊息 EGP 查詢鄰機訊息 EGP 查詢鄰機訊息 (Cont.) Hello Interval:Hello 區間值 Poll Interval: 用來控制路徑資訊更新的頻率 包含 5 種子類型, 以 Code 0~4 區別 Code 0:Acquisition 請求,Code 1: Acquisition 確認 Code 2:Acquisition 拒絕,Code 3: 終止請求 Code 4: 終止確認 35 36

10 EGP 鄰機可到達訊息 EGP 鄰機可到達訊息 (Cont.) EGP 提供兩種模式 : 主動模式和被動模式, 用來偵測鄰機是否在活動中 在主動模式下, 外部閘道器會週期性地傳送 Hello 與 Poll 訊息給鄰機, 偵測鄰機的狀況 被動模式下, 外部閘道器則等待鄰機傳送 Hello 與 Poll 訊息給它 當閘道器是被動模式時,Status 欄位的資訊可以用來判斷鄰機是否在活動中 Code=0 表示這是一個 Hello 的請求訊息, Code=1 表示一個 I Heard You 的回應訊息 由於 Hello 與 Poll 訊息在傳輸過程中可能遺失, 如何有效判斷鄰機仍在活動中或是當機了?? K/N 法則 : 當要宣告一個鄰機不在活動中時, 外部的閘道器會再發出 N 個 Hello 訊息給該鄰機, 此時至少要有 K 個 I Heard You 回應的訊息未收到, 才可正式宣告鄰機不再活動了 EGP 查詢請求與回應訊息 EGP 查詢請求與回應訊息 (Cont.) 透過請求與查詢回應訊息, 可以讓外部閘道器取得可到達的資訊 由於一個閘道器所連接的網路, 可能不只一個, 當閘道器接收到一個 EGP 請求訊息時, 可能無法判別這是由哪一個網路介面所發出的, 因此便需使用 IP source network 來判別 Code=0, 表示這是一個 Hello 請求訊息, Code=1 表示 I Heard You 的回應訊息 39 40

11 EGP 路徑更新訊息 EGP 路徑更新訊息 (Cont.) #INT. Gateways 和 #Ext. Gateways 分別表示在該自治系統中所包含的內部閘道器和外部閘道器的個數 Distance Number: 表示有幾種距離 Distance D11: 距離 D11 NET AT D11: 距離 D11 的網路數目 EGP 特性 對於距離的標準並未解釋, 基本上規定 255 代表此網路是不可到達的 其距離值必須在同一個自治系統下才有意義, 否則並無法用來作為最短路徑的參考 EGP 只廣播可到達的訊息, 使用 EGP 協定的網路, 從核心閘道器到任何網路所構成的路徑必須為唯一且不能形成迴圈 BGP BGP(Border Gateway Protocol) 在一般的中小型網路中並不常見, 因為中小型網路適用於內部路由協定 IGP BGP 適用於大型企業網路連接 ISP, 或 ISP 之間的連接或兩個自治系統的連接 BGP 不適用於 單一連線至網際網路 自治系統間頻寬太低 BGP 路由器的能力不足, 建議最好是 Cisco 7500 系列以上, 64MB 或 128M RAM 路徑處理上若只需要一般的路由方式即可處理的情形 43 44

12 BGP (Cont.) BGP (Cont.) 不適用 BGP 時, 可設定靜態路徑 BGP 間使用 TCP 來建立連接, 提供可靠的通訊服務, 預設的埠號是 179 (BGP 表頭 +data) 最大的訊息大小為 4096 bytes 最小 BGP header 不含資料位元, 為 19 bytes BGP (Cont.) Marker:16 個 byte 長度, 是接收者預期接收到的訊息 如果是 Open 的訊息型態, 或是所帶的訊息不帶有驗證的資訊, 則這 16 bytes 均為 1 接收端可使用驗證機制算出 Marker 欄位值應為多少, 一般用在預測對等的 BGP (peer BGP) 在同步時是否有遺失, 以及對收到的 BGP 訊息作驗證 Length:2 個 bytes, 代表總長度, 最大到 4096 bytes, 最少為 BGP 表頭長度 (19 bytes) Type:1 個 byte, 代表訊息的型態 BGP (Cont.) BGP 基本上是 distance vector 的 protocol, 由於使用了許多加強路由的方式, 所以使用的方式與 RIP 不同, 稱為 advanced distance vector 47 48

13 Features of BGP Inter-autonomous system communication Coordination among multiple BGP speakers Propagation of reachability Information Next-hop paradigm Policy support Reliable Transport Path Information Incremental Updates Features of BGP (Cont.) Support for classless addressing Route Aggregation Authentication Basic Functions of BGP 建立 2 BGP peers 間的 TCP 連線 包含做 Authentication 送出 Positive 和 Negative reachability Information 提供 Ongoing Verification, 以確保網路連結之資料正確 Types of BGP Messages 1 OPEN 2 UPDATE 3 NOTIFICATION 4 KEEPALIVE 51 52

14 OPEN Message BGP 在建立連線後第一個送出的訊息是 OPEN, 在 OPEN 訊息確認後, 才能交換 UPDATE NOTIFICATION 和 KEEPALIVE 訊息 My Autonomous Number:2 個 bytes, 代表送出者的 AS Number, 範圍由 0~65535 Hold Time:2 個 bytes, 代表著收到連續的 KEEPALIVE 和 UPDATE 訊息的最長有效時間,Hold Time=0 代表永久的連線, 一般則設為 3 秒或更大的值 BGP Identifier:4 個位元長, 代表 BGP 傳送者的辨識碼 有可能是路由器的辨識碼, 也就是路由器上最高的 IP address, 也有可能是路由器本機的介面位址 OPEN Message (Cont.) Option Parameters: 包含選項參數, 每個選項參數都有 parameter type,parameter length 和 parameter value Type =1 表示是驗證資訊, 用來驗證對等的 BGP 是否可以彼此交換 BGP 訊息 驗證碼代表驗證所使用的機制 OPEN Message (Cont.) UPDATE Message Initial exchange 32bit Marker Length Type: OPEN My Autonomous System Hold Time BGP Identifier Option Parameters (Auth. Code) Authentication Data Version BGP 路由器用來交換路由資訊的訊息 封包內資訊可以包含多個 AS 之間的關係, 以建立適當的路徑 可廣播傳送可行的路徑或取消多個不可行路徑 Update 除了包含 BGP 表頭外, 更使用了其他欄位 Unfeasible Route Length:2 個 bytes, 表是取消路徑的長度, 若等於 0, 則表示沒有取消路徑 也就不包含 Withdrawn Route 欄位 55 56

15 UPDATE Message (Cont.) UPDATE Message (Cont.) Withdrawn Route: 可變長度欄位, 包含一系列不可行的路徑, 或是不提供服務的路徑, 以便從 BGP 路由表中刪除這些路徑 取消路徑的格式包含 (Length, Prefix),Length 代表 IP Prefix 長度,Prefix 代表 IP 的前置位元 Ex: (24, ) Total Path Attribute Length:2 個 bytes, 表示 Path Attribute 長度 Path Attribute: 可變長度欄位, 由 <attribute type, attribute length,attribute value> 代表 UPDATE Message (Cont.) Attribute type Code: Origin/AS_PATH/NEXT_HOT/MULTI_EXIT_DISC/LOCAL /PREF/ATOMIC/Aggregate/AGGREGATOR Network Layer Reachability Information:NLRI, 可變長度欄位, 包含一系列 IP Prfixes, 以提供 BGP 路由更新所需的資料 藉由 NLRI, 可告知鄰接之路由器有哪些目的地可以到達 <length, prefix>:<24, > Update 訊息最小長度 23 bytes (BGP header 19 bytes + Unfeasible Route Length 2 bytes + Total Path Attribute Path 2 bytes) UPDATE Message (Cont.) Transfer routing information 32bit Marker Length Type: UPDATE Path Attr - - Length Path Attributes Network 1 59 Network n 60

16 KEEPALIVE Message 用來通知和確認鄰接的路由器是否存活, 以判斷網路是否可到達 KeepAlive 傳送時間間隔最好是 Hold Time 1/3, 最好不要超過一秒的傳送頻率 KEEPALIVE Message (Cont.) Actively test peer connectivity 32bit Marker Length Type: KEEPALIVE NOTIFICATION Message NOTIFICATION Message (Cont.) 當路由器偵測到錯誤的訊息時就會送出此訊息, 接著連線關閉 Error Code:1 個 byte Error Code 代表的訊息 1 Message Header Error 2 Open Message Error 3 Update Message Error 4 Hold Time Expired 5 Finite State Machine Error Error Subcode:1 個 byte, 每個錯誤碼可能有很多錯誤子碼 Errorcode Error Subcode 1. Message Header Error 1. Connection Not Synchronized 2. Bad Message Length 3. Bad Message Type 6 Cease 63 64

17 NOTIFICATION Message (Cont.) Types of Routing Algorithms in IGP Report the error 32bit Marker IGP 以交換路徑資訊的方式, 將 Routing Algorithm 分類 : 距離向量 (Distance Vector) 連結狀態 (Link Status) 混合 (Hybrid) Length Type: NOTIFIC. Error Code Error subcode Data Distance Vector Algorithm 發現路徑 (Route Discovery) 指使用 Propagation 傳遞路由資訊的 Algorithms 路由資訊包含 : Distance: 到 Destination 的距離 Vector: 指 Destination 以 Routing Table 儲存到各 Destination Network 的 Distance 和 Next Hop 演算法會將收到的路徑距離疊加起來, 決定最佳的路徑 每一個 Router 都會定期告訴 Neighbors 自己 Routing Table 內所有的資訊 路由器在啟動時, 會廣播訊息以取得最新的路徑 啟動後若是使用 RIP 路由協定, 則每 30 sec 會廣播一次, 以取得最新路徑, 存放在路由表中 IP 介面 Metric 值 S S S S 0 2 Ex: RIP/RIGP A

18 發現路徑 (Cont.) Propagation S A 0 S 透過一層一層的傳送, 更新 Router 資訊 S S 1 0 S 0 S 1 B C D A IP 介面 metric 值 E E IP 介面 metric 值 IP 介面 metric 值 6. 更新 A,B 的 Routing Table 5. C 傳送更新後的 Routing Table 2. 更新 D 的 Routing Table S S E S S E 0 1 B C D S 0 S E 0 S E 0 E 更新 C 的 Routing Table 3. D 傳送更新後的 Routing Table 1. 新增一個 D 的網路介面 B C D Basic Operations Boot 後, 一開始只有直接相連的網路會列在 Routing Table 上 定期 Router 會送出一份 Routing Table 的 Copy 給 Neighbor 以收到 Neighbor Routers 送來的資料, 修正自己的 Routing Table 選擇路徑 (Route Selection) 路徑選擇主要是依賴 metric 值,metric 值越大, 代表路徑的距離越遠 RIP 和 IGRP 決定 metric 值的方式如下 RIP:hop 數 IGRP: 有五大參數可以決定 metric 值, 分別是 bandwidth delay load Reliability 和 MTU, 內定情形是使用 bandwidth 和 delay 決定 metric 值 71 72

19 選擇路徑 (Cont.) 選擇路徑 (Cont.) 在網際網路中, 常有多條路徑可以到達相同的目的地情形, 其中可能使用了多種路由協定 但路由器如何選擇路徑呢? 基本上各路由協定都有預設的管理距離 (administrative distance), 管理距離代表路由協定的可靠度, 路由器會選擇較可靠的路徑來傳送封包 路由器收到 RIP 和 IGRP 都可以經過特定的路徑到達目的地網路時, 會選擇 IGRP 的路徑, 加入路由表 因為 IGRP 的管理距離值較小 路由方式連接的介面靜態路徑 EIGP 總和路徑外部的 BGP 內部的 EIGRP IGRP OSPF IS-IS RIP EGP 外部的 EIGRP 預設的 administrative distance 值 內部的 BGP 未知的路徑 維護路徑 (Route Maintenance) 透過一層一層的傳送, 更新 Router 資訊 6. 更新 A,B 的 Routing Table A B C D 4. 更新 C 的 Routing Table 5. C 傳送更新後的 Routing Table 3. D 傳送更新後的 Routing Table 2. 更新 D 的 Routing Table 1. 新增一個 D 的網路介面 75 Examples of Distance Vector Hello SPREAD GGP(Gateway-to-Gateway Protocol) RIP(Routing Information Protocol) IGRP(Interior Gateway Routing Protocol) 76

20 Link Status Algorithm 又稱為 Link State Shortest Path First(SPF) 每一 Router 都要有一份 Complete Topology Information 使用的是以連結速度為基礎的計算方式 Router 只送出自己與 Neighbors 間的 Link Status 給其他 Routers Link is Up:Neighbor 與 Link 都存在 Link is Down:Link 中斷 77 Tasks of Link Status Router 定期與 Neighbor 交換訊息, 以確認對方 Alive 或 Reachable 每一個 Router 定期送出它自己的 Link Status ( 不含 Route) 給所有其他 Router 時間由 30 分鐘到 2 小時不等, 依連結狀態的路由協定而定 其他 Router 收到並使用此資訊修改自己的 Map of Internet 並以 Dijkstra Shortest Path Algorithm 重新計算到每個 Destination 的 Shortest Path 78 Tasks of Link Status (Cont.) 當連結拓樸 (topology) 異動時, 路由器會用連結狀態廣播 (LSA,link-state advertisement) 通知鄰接的設備, 而且只會傳送更新的路徑, 而不是傳送所有的路徑資料 發現路徑 Link State 會用 Hello 訊息建立連結表 (link state table), 這格個連結表會包含整個網路 每個路由器都會建立自己的表, 記錄整個網路連結的關係與狀態 79 80

21 選擇路徑 維護路徑 使用最短路徑第一 (Shortest Path First,SPF) 演算法, 決定最佳路徑 Ex: R1->R2->R5->R6= R2 R 封包 100 封包 R1 50 R6 50 PC B PC A 20 R3 R 採取觸發更新, 也就是在網路上, 路由器學習到有異動時, 路由器會更新 link state table, 並且將異動的訊息再傳出去, 不會像 distance vector 一樣, 傳送整個 routing table Network A X down R1 R2 R3 R4 R5 R6 Network B 82 Advantages of Link Status Easy to debug Guarantee to converge Scaling Examples of Link Status OSPF(Open Shortest Path First) IS-IS(Intermediate System to Intermediate System) NLSP 83 84

22 RIP(Routing Information Protocol) Xerox 公司的 Palo Alto Research Center (PARC) 所開發出的網路協定 早先普及率不高, 後來 University of California at Berkeley 以此協定為基礎, 寫出 routed 程式做為內部區域網路間交換路徑資料與可到達性服務的資訊 配合當時廣泛使用的 4BSD Unix 系統, 因此被廣泛的使用 直到 1988,RIP 的 RFC 才出現 RIP(Cont.) 屬於 Distance Vector Protocol, 以所經過的閘道器數目作為距離的單位 內部的閘道器操作模式被分成兩類 主動模式 ( 稱為廣播閘道器 ): 對其他被動的閘道器廣播路徑訊息 被動模式 ( 稱為收聽閘道器 ): 依據廣播閘道器的廣播路徑訊息來改變自己的路徑表 同一時間只有一個閘道器是操作在主動模式下, 其餘的閘道器皆須在被動模式下, 以避免廣播風暴 RIP(Cont.) Initial Routing Table of RIP Update Routing table either at regular 30- second intervals or triggered RIP-2 support for CIDR, authentication and multicast transmission A Net 14 Net Net 78 F B Net 55 Net 92 C Net E Net 08 D

23 08 2 E B 66 3 E F A Final Routing Table of RIP Net 14 Net A A 66 2 D 78 2 A 92 3 A E 08 3 A A C 78 2 A 92 3 A Net 78 F B Net A 14 2 A 23 2 A 55 3 A 66 3 A Net 55 Net 92 D C Net E 23 2 E 55 2 C E 92 4 E 08 2 D 14 2 B 23 3 D B 92 4 B 89 Problem of RIP 使用向量距離並不能保證此路徑是最短的, 因 distance transmission time 允許人工方式增加慢速網路的 distance vector 值 Routing Loop RIP 使用的演算法, 並不能偵測出路徑迴圈的問題, 因此 RIP 必須使用另外的方法解決 90 Problem of RIP (Cont.) Slow Convergence Problem 路徑訊息在傳輸過程中可能發生錯誤 ( 遺失 受干擾或損毀 ), 因此需要有規則來辨識出這種情形 每當接收到廣播閘道器所廣播的路徑資訊時, 便開始記時, 若 180 秒內沒有再收到同樣的路徑資訊則視此路徑資訊無效 無法到達網路的表示 :RIP 中以 hops=16 來表示此網路無法到達, 視為無限長的路徑, 因此當發現 hops 到達 16 時,RIP 需採取其他的變通方法, 例如使用其他的協定 Slow Convergence ( 慢收斂 ) Problem 91 Initially Net 1 路徑中斷 Net 1 Net 1 16 X Net 1 1 G Net 1 G 1 3 G 1 G 2 G 3 G Net 1 G 1 2 G Net 1 G 1 3 G 1 G 2 G 3 G Net 1 G 2 4 G G 1 G G 2 92

24 Slow Convergence Problem (Cont.) G 1 和 Net 1 中斷時,G 1 到 Net 1 的向量距離由原本的 1 變成 16 若此時 G 2 剛好向 G 1 廣播, 則 G 1 和 Net 1 距離變為 3 G 2 資料由 2 變為 4 這樣一直循環下去, 當 G 1 的路徑向量距離變為 16 時, 依據 RIP 規定, 便成為無限長的路徑 Slow Convergence Problem (Cont.) 故障資訊比正確資訊傳送的慢 在廣播路徑時, 所有收聽閘道器會依此訊息中的最佳路徑更新本身的路徑資料, 但若是閘道器發現此路徑有問題, 並無法達到目的地, 在廣播時會用替代路徑繼續來廣播路徑資訊, 而這替代的路徑很可能包含剛才有問題的路徑 因此一個網路中斷的訊息會花很多時間在傳遞, 這對網路的整體效能影響頗大 慢收斂的解決方式 Split Horizon Update Split Horizon Update ( 水平分割更新法 ) Hold Down Timer Poison Reverse ( 毒性逆向法 ) 95 閘道器會記錄所接收到的路徑訊息是由哪一個介面而來, 同時不可以將此路徑訊息傳回給同樣的網路介面 當 G 1 和 Net 1 中斷時,G 2 收到 G 1 的路徑訊息, 發現 G 1 路徑是透過自己, 因此不會再對 G 1 廣播此路徑訊息, 並設定至 Net 1 為不可到達, 而 G 1 也將停止廣播至 Net 1 路徑的訊息 經過幾回合路徑更新後, 各閘道器均會發現 Net 1 為不可到達 可解決 slow convergence 問題, 但不是用所有網路的 topology 96

25 Hold Down Timer 原理是想辦法讓故障資訊有充足的時間傳送, 以免收到過時的訊息 當閘道器收到某個網路是不可到達的資訊時, 在一定的時間內, 該閘道器將不再接受關於那個網路的路徑資訊, 這個時間一般設定是 60 秒 缺點是網路路徑迴圈仍可存在, 一旦迴圈發生時, 故障的路徑資訊在 60 秒內仍會被保留 97 Poison Reverse 規定原本最先廣播該路徑的閘道器, 當路徑中斷時, 必須將路徑距離修改程無限長 ( 即 =16), 同時並將該資訊保留若干週期 若同時結合觸發更新的技術, 則可提高其效率 當閘道器一收到路徑故障訊息, 會立即廣播該消息, 而不會等到下一個路徑更新週期才廣播 98 分為兩種 : 要求路徑訊息 路徑回應訊息 RIP 訊息格式 兩者均包含兩個部分 : 固定的表頭及一個可選擇的路徑資訊表 99 RIP Message Formats Command(1) Version(1) Must be Zero(2) Address Family Identifier(2) Must be Zero(2) IP Address(4) Must be Zero(4) Must be Zero(4) Metric(4) RIP-1 Command(1) Version(1) Routing Domain(2) Address Family Identifier(2) Route Tag(2) IP Address(4) Subnet Mask(4) Next Hop(4) Metric(4) RIP-2 Routing Domain : group routers in domains which share routing information Route Tag : propagate the information acquired from an EGP Subnet Mask : subnet mask for CIDR implementation Next Hop : next hop addresses that allows for optimization routes 100

26 RIP 訊息格式 (Cont.) 命令 : 說明該訊息的類型,1 表示 要求路徑訊息,2 表示 路徑回應訊息 網路家族 Id:RIP 並非限定用於 TCP/IP 網路, 可以包含其他類型的網路, 因此必須辨識該網路使用的協定, 以便指定要翻譯成哪一種網路位址 網路位址 : 共 14 個 bytes, 但 Internet 所使用的 IP address 只需 4 個 bytes, 其餘設為 0 Metric: 記錄到所指定的網路間的向量距離, 即所經過的閘道器數目, 範圍 1~ Hello Original Core Network 使用的 IGP 目前已走入歷史 屬於 Distance Vector Protocol 以網路延遲取代所經過的閘道器數目, 做為 Metric 最早被用在 NFSNET 骨幹網路的 Fuzzball 閘道器上, 主要包含兩個功能 同步網路上 router 的時脈 允許每一個閘道器計算最新最短的延遲路徑 102 Hello (Cont.) 如何計算網路延遲? 當閘道器廣播傳送路徑訊息時, 會將當時的時間記錄下來, 稱為 時間標記 當閘道器接收到廣播的訊息後, 利用預測鄰機時脈所得到的值, 減去接收訊息中的時間標記值後, 即為網路延遲的時間 每個閘道器會週期性的詢問其鄰機, 以便得到最新的預測鄰機時脈值 Problem 路徑震盪 : 意指路徑資訊無法快速變化 假設到某目的地有 A B 兩條路徑, 一開始各閘道器以為路徑 A 的負擔最輕, 因此皆使用 A 路徑 但是大家都用 A 路徑, 結果使得 A 變成負擔最重,B 反而變得負擔最輕, 因此大家又改為選擇 B 路徑, 就這樣一直反反覆覆 Delay measurements are not fix values

27 Using Problem (Cont.) hold down Threshold 只有當路徑的延遲差異很大時, 才允許改變路徑 K-out-of-N rules Hello still has instable problem Check Sum Hello 的訊息格式 時間標記 時間 日期 區域資料項主機數目 (N) 延遲 1 差距 1 延遲 2 差距 2 ~ ~ 延遲 n 差距 n Hello 的訊息格式 (Cont.) 日期 : 記錄廣播路徑者的本地日期 時間 : 記錄廣播路徑者的本地時間 區域資料項 : 標示區域網路所使用的資料 主機數目 : 表示有幾項的延遲資料 (Ex: n) 延遲 : 表示訊息到達某台主機的延遲時間 差距 : 表示廣播路徑的閘道器與接收訊息主機之間的時脈差距 107 IGRP(Interior Gateway Routing Protocol) Cisco 於 1980 年代中期發展出的 Protocol 屬於 Distance Vector Protocol 只與鄰近的 Router 做路徑選擇資訊的交換 以 Delay Bandwidth Loading Reliability MTU 做為 Metric 預設是用到 Delay 和 Bandwidth Delay 是指來源主機到達目的主機時的延遲值 Bandwidth 是指來源主機到達目的主機的最小頻寬值 支援 Multi-path Routing 108

28 IGRP (Cont.) 與 RIP 不同處 IGRP 可以服務大型的網路 ( 不受限於 15 hops) IGRP 在網路異動時可以快速地反映和處理 IGRP 可以提供多個路徑 (4 條路徑 ), 以提高網路頻寬 IGRP 可以和 RIP USPF 和 EIGRP 共同使用和轉換使用 IGRP 每 90 秒廣播一次 IGRP (Cont.) IGRP 在穩定度 效能和降低路徑的迴路上都有不錯的表現 特點 Flash Updates: 使用 Flash updates 通知鄰近的 routers 有異動, 以加快收斂的時間 Hold Down Timer: 防止路徑的迴路 Split Horizon: 防止傳回不正確的資訊 Poison Reverse: 移除不正確的資訊 IGRP Example IGRP Example (Cont.) Poison Reverse R 3 R 2 Update route Flash Update R 1 Network III Fall X 當 R 1 的 Network III 失效後,R 1 會送 Flash Update 訊息給 R 2, 當 R 2 收到 Flash Update 時會啟動 Hold-Down Time, 並將 Network III 的路徑移除, 並產生 Split Horizon 以防止 R 2 傳送不正確的資訊給 R 1 R 4 Hold-Down Timer Split Horizon 當 R 3 送出 update route to Network III 給 R 2 時, R 2 會傳回 Poison Reverse 給 R 3 當 R 3 收到 Poisson Reverse 時, 會將通往 Network III 的路徑移除

29 OSPF(Open Shortest Path First) 由 1980 年代由 IETF(Internet Engineering Task Force) 發展出的 Protocol 當時發展的 OSPF 和 IGRP 的目的一樣, 因為 RIP 無法處理大型的網路, 於是才有 OSPF 和 IGRP 的出現 使用的是 SPF 演算法找尋最短路徑 屬於 Link Status Protocol 適用於大型網路 支援 VLSM ( 可變長度的子網路遮罩 ) OSPF v.s RIP 收斂速度 :OSPF 使用 flooded 方式和平行運算處理路徑問題, 比 RIP 的收斂速度快太多了 支援 VLSM:RIP version 1 不支援 VLSM, version 2 才支援 網路可到達的能力 :RIP 受限於 15 hops, 所以只適用於中小型網路,OSPF 則無此限制, 特別適用於大型網路 路徑的選擇方式 :RIP 根據 hop 數,OSPF 則是根據連線的速度決定 cost 高低 OSPF v.s RIP (Cont.) 頻寬的使用 :RIP 每 30 秒便廣播一次, 而且傳的是整個 routing table, 在廣域網路會用掉大量的頻寬 OSPF 只傳送更改的路徑部分, 而且是當網路有異動時才會傳送, 所以可以省下相當多的頻寬 OSPF 運作原理 區域 (Area): 由設備 (routers) 和主機 (hosts) 所組成 這些設備和許多段的網路都會有相同的區域辨識身份 (Area Identification)

30 Establish Router Adjacencies ( 建立路由器的相連 ) OSPF 運作是仰賴 Router 之間可以知道對方的 router, 進而互相交換訊息 這些都是透過 Hello 協定完成 Hello 藉由 IP multicast 位址方式傳送到各 routers Establish Router Adjacencies (Cont.) Hello 封包包含 Router ID Hello/Dead Intervals Neighbors Area ID Router Priority DR IP address BDR IP address Authentication Password Stub area flag Establish Router Adjacencies (Cont.) Router ID:Router 所使用的 IP address, 若 router 有多個 IP address, 以最高位元組的最高 IP address 為主 Hello/Dead intervals:hello intervals 是指 routers 經過多少秒傳送 Hello 封包一次, 預設為 10 秒 Dead intervals 是指 router 等待相鄰的 router 傳送訊息, 若是超過 dead intervals 的時間, 救代表鄰近的 router 可能 shut down 或故障 Neighbors: 已建立鄰近 routers 的資料 Area ID: 相同的 Area ID 的 routers 擁有相同的 linkstate database 119 Establish Router Adjacencies (Cont.) Router Priority: 當 OSPF 運作需要送 DR ( 設定的路由器 ) 和 BDR ( 備份設定的路由器 ) 時, 就需要 Router Priority 系統預設為 1, 最高值就是 DR 換句話說我們想指定哪一顆 router 當作 DR 時, 只要將該 router 的 router priority 值設為最高值就可以了 Authentication:router 需要相互驗證身份時會交換的密碼 Stub area flag: 在 Hello 的封包中,2 個 routers 屬於相同的 stub area, 就需要 stub area flag 做溝通 120

31 Example 新加入一個 router R 1,R 1 尚未運作, 處於 down state R 1 開始送出 Hello 封包 H e l l o R 1 R 2 R 4 Example (Cont.) Init state: 所有的 router 收到 R 1 的 Hello 封包後, 會將 R 1 的資訊加入自己的 adjacencies database, 再回應 Hello 封包 ( 含所有相鄰 router 資訊 ) 給 R 1 Two-way state: 當 R 1 收到相鄰的 routers 的 Hello 封包後, 也會對這些 Hello 封包包含的資訊加入 R 1 自己的 adjacencies database, 這時 R 1 和 R 2 R 1 和 R 3 R 1 和 R 4 都有雙方的資訊, 建立了雙方溝通的管道 R Example (Cont.) Elect the DR and BDR: 目的是在降低路徑更改的流量和維護連結狀態的同步 若是 R 2 擁有較高的 priority 值, 則被選為 DR; 若是 R 4 擁有次高的 priority 值, 則會被選為 BDR 選完 DR 和 BDR 後, 所有的 routers 都只和 DR 或 BDR 交換資訊 Example (Cont.) R 1 和 R 3 並不直接交換資訊, 都是透過 R 2 來運作 R 4 (BDR) 並不執行 R 2 的工作, 除非 R 2 故障了 R 1 R 2 (D R ) 123 R 3 R 4 (B D R ) 124

32 Example (Cont.) Hello updates: 選完 DR 和 BDR 後, routers 會透過 Hello updates ( 週期的 ) 來維持整個網路的運作 125 Discover Route 在建立好路由器的 adjacencies 後 (DR 和 BDR 都選好了 ), 路由器就開始準備交換 link-state 資訊和建立 link state database, 而這些資訊的交換都需先經過 discovery route 後才可達成 步驟 : Exstart state:dr 和 BDR 都選好後,routers 就進入 Exstart 狀態 一般的 router 往 DR 的 router 送出帶有 router ID 的 Hello 封包 126 Discover Route (Cont.) Exchange state: 本身是 DR 的 router 會回應給各個 router 我有較高的 router ID, 從我開始進行交換資訊, 緊接著送出 link-state database 給各個 router, 而各個 router 也回應自己的 link-state database 給 DR 的 router Loading state: 具有 DR 的 router 和一般的 router 再交換一次或更多次的 DBD (database description packet) 後, 都會回應 link-state acknowledgment (LSACK), 其中包含 sequence numbers 127 Discover Route (Cont.) L in k -s ta te D a t a b a s e R 1 R 2 (D R ) R 3 L i n k - s t a t e D a t a b a s e R 4 (B D R ) R 1 L S A C K R 2 (D R ) R 3 L S A C K L S A C K R 4 (B D R ) 128

33 Discover Route (Cont.) Full state ( 完全狀態 ): 所有的 routers 都會異動 link-state databases, 在所有的 router 都有相同的 link-state database 時, 就進入了 full state Maintain Routing Information 若 router 欲道路竟異動或故障時 Step 1: 偵測到發生變動的 router 會利用 Multicast 傳送 LSU (link state update) 封包給 DR 和 BDR router 異動 LSU R 1 R 2 (D R ) 129 R 3 R 4 (B D R ) 130 Maintain Routing Information (Cont.) Step 2:DR router 收到異動的訊息後, 會利用 multicast 位址 傳送給其他的 routers Step 3: 一般的 router 收到 DR router 傳送的 LSU 後, 若是有連接到其他網路的 router, 則會繼續往下送 異 動 Maintain Routing Information (Cont.) Step 4: 一般的 router 收到 DR router 送過來的 LSU 後, 若是 LSU 封包帶的是有異動的訊息, 則 router 會更新自己的 link-state database, 建立新的 routing table R 1 R 2 (D R ) L S U R 4 (B D R ) R 3 L S U

34 Goal of OSPF(1) Open standard OSPF includes type of service routing. OSPF provides load balancing. Network can be partitioned to subsets. Easy management Permit network growth Authentication Goal of OSPF(2) OSPF supports classless routes. OSPF minimize broadcasts on multi-access network. Virtual network topology OSPF allows routers to exchange routing information learned form external sites Classful Routing ( 分級的路由 ) Classful Routing (Cont.) Classful routing 會將網路內的遮罩視為一致, 使用分級的網路遮罩為預設的路由遮罩傳送出去 Class A 的網路遮罩是 ,class B 的網路遮罩是 , class C 的網路遮罩是 同一個網路內, 所有的子網路遮罩都要一樣 ISP 連到公司的網段需使用與公司相同大小的網段, IP 位址許多不用 RIP v1 和 IGRP 是屬於 classful routing R R ISP C 級網路路由器 / /28 R Magic 公司 136

35 Classless Routing 包括 RIP v2 EIGRP OSPF IS-IS 和 BGP 所有網段都會送出子網路遮罩 同一個網路內, 所有的子網路遮罩不需一樣, 因為 class routing 支援可便長度的子網路遮罩 (Variable-length subnet masking,vlsm) Class Routing 的路由是可以手動建立和控管的, 所以在 IP 位址的路徑上, 可以有效降低 routing table 大小, 加快傳送封包的速度 IS-IS(Intermediate System to Intermediate System) 一種 OSI 協定的 Protocol T1 NSFNET Backbone 使用 目前仍有大型的 ISP 採用 屬於 Link Status Protocol Homework 3 1. 說明各種設定 IP 的方法與適用的時機 2. 對於 IGP 而言, 你認為那些 Metric 適合用於計算到 Destination 的 Distance 請簡單說明理由 139