教育部顧問室通訊科技教育改進計畫專案獎助 第五章 網路路由基本概念 2003-2004 All rights reserved. No part of this publication and file may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, without prior written permission.
區域網路與廣域網路 與區域網路比較, 廣域網路通常涵蓋較大的地理區域, 而其主要的目的是要做為區域網路與區域網路間互連的橋樑 在廣域網路的架構中, 我們可將經由網路閘道器 (Gateway) 所接上來的各個區域網路視為子網路 (Sub networks ) CH -3 2
區域網路與廣域網路 區域網路 區域網路 閘道器 閘道器 閘道器 廣域網路 區域網路 閘道器 區域網路 CH -3 3
區域網路與廣域網路 區域網路互連 區域網路有一項很重要的特性, 便是在實體層 (Physical Layer) 的技術上具備廣播的特性, 不管是環狀 無線 或匯流排狀的區域網路拓撲, 基本上, 網路上的任一台電腦或終端設備所送出之資料, 在同一網段範圍內的設備均可收到 區域網路較屬於鏈路間 (Link by link) 的問題 ; 而廣域網路已將許多區域網路互連在一起, 因此所需解決之問題較屬於選擇好的路由 (routing), 將資料封包由起始點到終點 (End-to-End) 的網路層問題 CH -3 4
鏈結層架構 邏輯鏈結控制 (LLC) 資料鏈結層 802.3 802.4 802.11 傳輸控制 (Transmission Control) 實體層 CH -3 5
Layer 2 v.s. Layer 3 End to end Routing Routing Routing Routing Link by link LAN R R R R LAN LAN R R CH -3 6
網路網路 4- 層協定堆疊 CH -3 7
RFC 的標準 CH -3 8
路由選擇功能 網際網路是由許多網路所構成的互連網路, 從某一起始點到某一終點的路徑可以有很多選擇 路由選擇的主要任務就是要從中選擇一條最恰當的路徑 選擇最佳路由路徑 (optimal routing paths) 能力 有效的封包傳送能力 CH -3 9
What is routing Which path?? source destination CH -3 10
路由選擇功能 網路上的路由器 (Router) 利用選徑演算法得到其到各節點之最短路徑後, 這些資訊通常會存放在路由表 (Routing Table) 中 在實務上, 要瞭解資料封包的傳送路徑, 一般使用者可以在 Windows 系統中, 下 route print 顯示出其路由表 CH -3 11
路由選擇功能 路由演算法常見的衡量標準有 : 頻寬 : 鏈結的資料容納量 延遲 : 將封包沿各連結來源移動到目的地所需的時間 Load: 路由器忙碌與否 可靠度 : 通常是指各網路連結的錯誤率 hop count: 封包在送達目的地之前, 需經過的路由器數目 時脈數 : 使用 IBM PC 時脈頻率 ( 約為 55 毫秒 ) 計算之資料連結上的延遲 成本 ( 距離 ): 由網路管理員指定, 通常是根據線路成本或其他估算而定 CH -3 12
路由演算法的好壞考量因素 最佳化 : 根據指標的權值來計算最佳路徑的能力 簡單 : 如果路由演算法的設計越簡單, 則執行效能通常越好, 而且不管是硬體或是軟體的成本與製作上都會容易許多 穩定 : 在出現不正常或不可預測的事件時, 仍然能保持繼續正常運作 收斂快 : 路由演算法收斂速度要盡量快, convergence 是所有網路設備達到具有相同的網路資訊所需的時間 CH -3 13
距離向量 (Distance) 與鏈結狀態 (Link state) 路由演算法 距離向量與鏈結狀態演算法最主要的差別 : 距離向量演算法需藉由其鄰近節點所告知之 距離 資訊做為其是否選擇該節點為路徑的依據 鏈結狀態演算法則是每一節點經由鄰近節點的告知, 獲得所有網路 鏈結狀態 的資訊 ( 亦即擁有網路的全貌 ) 後, 再做為選徑的依據 CH -3 14
距離向量演算法 使用距離向量的路由器都會自行維護一個路由表, 他會記錄到每一個已知目的地的最佳距離到自己的路由表中 最典型的代表就是 Bellman-Ford Routing Algorithm 當機器開機時, 路由器中只有自己本身的路由資訊, 然後會和鄰近的路由器以廣播的方式, 彼此交換自己的路由表內的資訊, 藉由這樣的交換訊息, 很快的就可以得知整個網路的連結狀態 CH -3 15
Example CH -3 16
Example From A to Interface Metric From B to Interface Metric A local 0 B local 0 From C to Interface Metric From D to Interface Metric C local 0 D local 0 From E to Interface Metric From F to Interface Metric E local 0 F local 0 From G to Interface Metric G local 0 CH -3 17
From A to Interface Metric From B to Interface Metric A local 0 B local 0 B S0 1 A S0 1 D S1 1 C S1 1 F S2 1 From C to Interface Metric From D to Interface Metric C local 0 D local 0 B S0 1 A S0 1 E S1 1 E S2 1 G S1 1 From E to Interface Metric From F to Interface Metric E local 0 F local 0 C S0 1 A S0 1 D S1 1 G S1 1 From G to Interface Metric G local 0 CH -3 D S0 1 18 F S1 1
From A to Interface Metric From B to Interface Metric A local 0 B local 0 B S0 1 A S0 1 D S1 1 C S1 1 F S2 1 D S0 2 C S0 2 F S0 2 E S1 2 E S1 2 G S1 2 From C to Interface Metric From D to Interface Metric C local 0 D local 0 B S0 1 A S0 1 E S1 1 E S2 1 A S0 2 G S1 1 D S1 2 B S0 2 F S0 2 C S2 2 From E to Interface Metric From F to Interface Metric E local 0 F local 0 C S0 1 A S0 1 D S1 1 G S1 1 B S0 2 B S0 2 A S1 2 D S0 2 G S1 2 From G to Interface Metric G local 0 D S0 1 F S1 1 A S0 2 E S0 2 CH -3 19
From A to Interface Metric From B to Interface Metric A local 0 B local 0 B S0 1 A S0 1 D S1 1 C S1 1 F S2 1 D S0 2 C S0 2 F S0 2 E S1 2 E S1 2 G S1 2 G S0 3 From C to Interface Metric From D to Interface Metric C local 0 D local 0 B S0 1 A S0 1 E S1 1 E S2 1 A S0 2 G S1 1 D S1 2 B S0 2 F S0 3 F S0 2 G S0 3 C S2 2 From E to Interface Metric From F to Interface Metric E local 0 F local 0 C S0 1 A S0 1 D S1 1 G S1 1 B S0 2 B S0 2 A S1 2 D S0 2 G S1 2 C S0 3 F S1 3 E S1 3 From G to Interface Metric G local 0 D S0 1 F S1 1 A S0 2 E S0 2 B S0 3 C S0 3 CH -3 20
距離向量演算法 - 無限計數 因為每一網路節點不需掌握網路整體拓撲, 因此在選徑時就有可能會有形成迴圈的現象, 甚至有可能會使得路徑的選擇產生無限計數 (Count to infinity) 的問題 CH -3 21
經一段時間後, 路由器各自之完整的路由表如下 : A B C D E S0 S0 S1 S0 S1 S0 S1 S0 From A to Interface Metric From B to Interface Metric A local 0 A S0 1 B S0 1 B local 0 C S0 2 C S1 1 D S0 3 D S1 2 E S0 4 E S1 3 From C to Interface Metric From D to Interface Metric A S0 2 A S0 3 B S0 1 B S0 2 C local 0 C S0 1 D S1 1 D local 0 E S1 2 E S1 1 From E to Interface Metric A S0 4 B S0 3 C S0 2 D S0 1 E local 0 CH -3 22
假設 A-B 之間的鏈路斷了,B 無法到達 A, 但是 B 卻從 C 得知有一條到 A 的路徑, 於是 B 就更新自己的路由表, 如下表 From B to Interface Metric A S1 3 B local 0 C S1 1 D S1 2 E S1 3 然而過一段時間,C 必須再次跟鄰居交換訊息, 發現到 A 這個 entry 必須更新, 於是 C 就更新自己的路由表, 如下表 From C to Interface Metric A S0 4 B S0 1 C local 0 D S1 1 CH -3 23 E S1 2
距離向量演算法 解決無限計數的方法 : Maximum hop count: 限制其跳躍數 Split horizon: 這個方法的原則是不回送資料, 所以當 A-B 之間斷了,C 不會再把 A 的訊息告訴 B, 因為到 A 的訊息是由 B 告訴 C 的 Hold Down: 利用 Hold down timer, 若 hold down timer 過期前的任何時間裡, 從不同的路由器接到更新資訊, 但指標較差, 則不理會更新資訊 在 hold down timer 時效範圍內, 不理會指標較差的更新資訊, 則能有更多時間將中斷的改變資訊傳播到整個網路上 CH -3 24
Split horizon Network 1 Router1 Router2 Router2 不能告訴 Router1 有關 Network 1 的資訊, 因為那是 Router 1 告訴 Router 2 的 CH -3 25
鏈結狀態路由演算法 鏈結狀態演算法在一般圖形理論中也稱為最短路徑 (Shortest Path First, SPF) 演算法, 它保持一份網路整體拓撲的資料庫 再利用圖形理論中的最短路徑演算法找出該節點到各點之最短路徑 圖形理論中, 最短路徑的演算法有許多種, 但其中以 Dijkstra 演算法最有名, 而 Dijkstra 演算法也被引用為 OSPF (Open Shortest Path First) 演算法中 CH -3 26
鏈結狀態路由演算法 鏈結狀態演算法有下列優點 : 無迴圈 (Loopless): 路徑的決定是在擁有整個網路資訊後才決定, 因此不會找出有迴圈的路徑 多路徑 (Multiple paths) 到目的地 : 既然每一節點能獲知網路全貌, 因此每一節點可依需要找出到目的地且不共用鏈結之多條路徑, 而找出多條路徑的目的, 可以是為了做路徑保護 ( 備用路徑 ), 或是分擔訊務使用 CH -3 27
其他路由演算法 Optimal routing Traffic may be splitted at some strategic points to smooth delay and to increase network throughput Hot potato (deflection) routing To minimize buffer overflow and to reduce the packet loss CH -3 28
內部與外部路由 Routing 時, 每一節點都需要將其所獲得的資訊以氾濫 (Flooding) 的方式傳送出去, 而傳送出去後到每一節點都獲得此訊息時, 該筆訊息便不會在網路上繼續漫延, 稱為收斂 若網路的規模太大, 則將影響收斂的時間, 且非常沒有效率 分層次 ( 內部 / 外部 ) 選擇路由 CH -3 29
內部與外部路由 將網路分割成較小規模的網路, 稱為自治系統 (Autonomous System, 簡稱 AS) AS 為受同一個權責單位管理的網路, 包含一個或多個路由器, 路由資訊可以在同一個或不同的自治系統間散播 ; 一個自治系統可以是一個校園網路, 也可以是 ISP 業者的網路, 而且一自治系統也可以被另一自治系統所涵蓋 單一自治系統內部所散播路由資訊的協定稱為內部路由協定 (Interior Gateway Protocol, 簡稱 IGP) 跨自治系統散播路由資訊的協定稱為外部路由協定 (Exterior Gateway Protocol, 簡稱 EGP) CH -3 30
內部與外部路由 內部路由協定主要是以最短路徑為主要訴求 外部路由協定雖然也考慮最短路徑的原則, 但也需要有策略方面的考慮 CH -3 31
內部與外部路由 國外 X AS Hinet G G G AS Seednet G AS TANET G G X CH -3 32