Chapter 4 Network Layer (網路層).

Presentation on theme: "Chapter 4 Network Layer (網路層)."— Presentation transcript:

1 Chapter 4 Network Layer (網路層)

2 Topic Overview 4.1 簡介 4.2 虛擬線路網路和資料包網路 4.3 路由器的內部
4.4 網際網路IP協定 網際網路的轉送(forward)及定址 4.5 路由演算法 (routing algorithms) 4.6 網際網路的路由 4.7 廣播與群播路由 (broadcast and multicast) R.-W. Hung 2011

3 Topic Overview (Cont.) 目標 (Goal) 了解網路層服務背後(隱藏)的原理： 網際網路上的例證、實作 網路層服務模型
轉送(forward) vs. 路由(route) 路由器(router)如何運作 路由演算法 (路徑的選擇) 進階課題： IPv6 網際網路上的例證、實作 應用層 傳輸層 網路層 連結層 實體層 R.-W. Hung 2011

4 第四章 導覽流程 4.1 簡介 4.2 虛擬線路網路和資料包網路 4.3 路由器的內部
4.4 網際網路IP協定 網際網路的轉送(forward)及定址 4.5 路由演算法 (routing algorithms) 4.6 網際網路的路由 4.7 廣播與群播路由 (broadcast and multicast) R.-W. Hung 2011

5 4.1 簡介 網路層 從傳送主機到接收主機傳輸的資料區段(segment) 在傳送端將資料區段封裝在資料包(datagram)中
4.1 簡介 網路層 從傳送主機到接收主機傳輸的資料區段(segment) 在傳送端將資料區段封裝在資料包(datagram)中 在接收端，將資料區段傳送到傳輸層 每一台主機、路由器中都有網路層協定 路由器會檢查經過它的所有IP資料段中的標頭欄位 應用層 傳輸層 網路層 連結層 實體層 R.-W. Hung 2011

6 網路層的通訊 圖4.1 網路層 4.1 簡介 (Cont.) R.-W. Hung 2011 應用層 傳輸層 網路層 資料連結層 實體層

7 兩個主要的網路層功能 轉送(forward)：將封包從路由器的輸入轉送到適當的路由器輸出
4.1 簡介 (Cont.) 兩個主要的網路層功能 轉送(forward)：將封包從路由器的輸入轉送到適當的路由器輸出 路由(繞送、route)：決定封包從來源端到目的端的路由(路徑) 路由演算法 (routing algorithm) 比喻： 路由：計畫從來源到目的旅行的過程 轉送：經過單一交流道的過程 R.-W. Hung 2011

8 兩個主要的網路層功能 (Cont.) 1 2 3 路由演算法
(routing algorithm) 每台router均儲存一份forward table，以決定進入的packet該轉送到哪一條輸出link 如何設定forward table: 由routing algorithm判斷要在router的forward table插入哪些值，亦即，由routing algorithm設定其轉送表 本機轉送表 (forward table) 標頭值 輸出連結 0100 0101 0111 1001 3 2 1 抵達封包 的標頭值 1 0111 2 3 圖4.2 路由演算法根據轉送表來轉送資料段 R.-W. Hung 2011

9 建立連線 (connection setup)
4.1 簡介 (Cont.) 建立連線 (connection setup) 在某些網路架構中網路層的第三個重要功能 ATM、訊框轉播(frame relay)、X.25 在網路層資料包傳送之前，兩個主機以及介於其間的所有路由器需先建立虛擬連線 (VC，Virtual connection) 路由器介入 此程序稱為「建立連線」 網路層以及傳輸層的連線服務： 網路層：兩個主機之間 (在VCs案例中也許可以介入路由器) 傳輸層：兩個行程之間 R.-W. Hung 2011

10 網路服務模型 (network service model)
4.1 簡介 (Cont.) 網路服務模型 (network service model) Q：有哪些服務模型提供給從傳送端到接收端傳輸資料段的通道? (網路層可能提供的服務) 個別資料區段的服務範例：(p. 4-7) 傳送保證 (guaranteed delivery) 小於 40 毫秒的傳送保證 (guaranteed delivery with bounded delay) 資料區段流量的服務範例：(p. 4-7) 依序封包傳送 (in-order packet delivery) 流量的最低頻寬保證 (guaranteed minimal bandwidth) 限制兩個封包之間間隔的改變 (guaranteed maximum jitter) 安全性服務 (security service) Internet的網路層只提供一種服務:盡力而為服務(不提供任何服務) R.-W. Hung 2011

11 網路服務模型 (Cont.) 表4.1 網際網路、ATM CBR、ATM ABR 服務模型 4.1 簡介 (Cont.)
R.-W. Hung 2011

12 第四章 導覽流程 4.1 簡介 4.2 虛擬線路網路和資料包網路 4.3 路由器的內部
4.4 網際網路IP協定 網際網路的轉送(forward)及定址 4.5 路由演算法 (routing algorithms) 4.6 網際網路的路由 4.7 廣播與群播路由 (broadcast and multicast) R.-W. Hung 2011

13 4.2 虛擬線路網路和資料包網路 傳輸層 網路層 可提供應用程式行程間的可靠連線服務(TCP)及 不可靠無連線服務(UDP)
4.2 虛擬線路網路和資料包網路 傳輸層 可提供應用程式行程間的可靠連線服務(TCP)及 不可靠無連線服務(UDP) 網路層 可提供給傳輸層來源端和目的端主機 可靠的連線服務  虛擬線路網路 (virtual-circuit network) ATM、frame relay 不可靠的無連線服務  資料包網路 (datagram network) Internet 與傳輸層服務的差異 服務：主機對主機 沒有選擇性：單一網路只提供其中一個 (如：Internet只提供不可靠的無連線服務而無可靠的連線服務) 實作：在核心(core- router)及終端系統(end system) 無連線 服務 連線 服務 應用層 傳輸層 網路層 連結層 實體層 handshaking non-handshaking R.-W. Hung 2011

14 虛擬線路 (Virtual Circuit)
4.2.1 虛擬線路網路 (VC) 虛擬線路 (Virtual Circuit) 意義 來源端到目的端的路徑，如同電話線路 效能良好 沿著來源端到目的端路徑的網路行為 使用 在資料開始傳送前，必須為每個連結建立連線、拆除 每個封包會承載一個 VC 識別碼 (並非目的端主機位址) 在來源端到目的端的路徑上，每個路由器都必須維護每個經過的連線的「狀態」 連結(link)和路由器(router)的資源 (頻寬、緩衝區) 可能會配置給VC (專用資源= 預期的伺服器) R.-W. Hung 2011

15 虛擬線路VC (Cont.) VC 實作 一條 VC 包含了： 一個屬於虛擬線路的封包會載送一個 VC 編號
一條來源端至目的端間的路徑 VC 編號，路徑上的每一個連結都有一個編號 路徑上的每一個路由器轉送表中的紀錄 一個屬於虛擬線路的封包會載送一個 VC 編號 在每一個連結，VC 編號必須改變 新的 VC 編號從轉送表中得來 R.-W. Hung 2011

16 虛擬線路VC (Cont.) VC 編號 A B R1 22 12 32 1 3 2 介面號碼
R1路由器的轉送表 (forwarding table) 進入介面 進入VC編號 離開介面 離開VC編號 1 12 3 22 2 63 1 18 3 7 2 17 情境說明: 主機A要求網路在自己與主 機B間建立一條VC 網路選擇: VC路徑=A-R1-R2-B 連結的VC編號依序為12、 22、32 1 97 3 87 ... ... ... ... router中的forward table會隨VC建立及移除而有所變化 圖4.3 簡單的虛擬線路網路 R.-W. Hung 2011

17 虛擬線路  訊號協定 (signal protocol)
4.2.1 虛擬線路網路 (Cont.) 虛擬線路  訊號協定 (signal protocol) 用來設定、維護及拆除 VC 用在 ATM、訊框轉播 (frame relay)、X.25 並沒有用在現今的網際網路(internet)中 應用層 傳輸層 網路層 資料連結層 實體層 應用層 傳輸層 網路層 資料連結層 實體層 5. 開始傳送資料 6. 接受資料 4. 連線建立 3. 接受連線 1. 初始連線 2. 進入連線請求 圖4.4 建立虛擬線路 R.-W. Hung 2011

18 4.2.2 資料包網路 (Datagram network)
意義 在網路層不需要建立連線 路由器：沒有終端對終端的連線狀態 沒有網路層的「連線」觀念 使用目的端主機位址轉送封包 在同一對來源-目的端之間的封包可能會使用不同的路徑 應用層 傳輸層 網路層 資料連結層 實體層 應用層 傳輸層 網路層 資料連結層 實體層 1. 送出資料 2. 接收資料 圖4.5 資料包網路 R.-W. Hung 2011

19 4.2.2 資料包網路 (Datagram network)
資料包網路 (Cont.) 轉送表 (forwarding table) 40億個可能的紀錄 (32位元IP位址) 路由器不需儲存40億個項目 R.-W. Hung 2011

20 4.2.2 資料封包網路 (Datagram network)
資料包網路 (Cont.) 轉送表 (Cont.) 最長前置代碼對應 (longest prefix matching) 範例： DA =  選擇哪一個介面來forwarding ? DA =  選擇哪一個介面來forwarding ? R.-W. Hung 2011

21 虛擬線路網路 vs. 資料(封)包網路 資料包網路  網際網路
4.2 虛擬線路網路和資料包網路 虛擬線路網路 vs. 資料(封)包網路 資料包網路  網際網路 電腦之間的資料交換 “彈性的” 服務，沒有嚴格的時限要求 “聰明的” 終端系統 (電腦) 能夠適應、執行控制、錯誤復原 網路內部是簡單的、邊緣是複雜的 許多連結型態 不同的特質 統一的服務困難 虛擬線路網路  ATM (Asynchronous Transfer Mode) 來自電話系統 人類的對話： 嚴格的時限、可靠性的要求 保證服務的需求 “愚笨的” 終端系統 電話 網路內部是複雜的、邊緣是簡單的 R.-W. Hung 2011

22 第四章 導覽流程 4.1 簡介 4.2 虛擬線路網路和資料包網路 4.3 路由器的內部
4.4 網際網路IP協定 網際網路的轉送(forward)及定址 4.5 路由演算法 (routing algorithms) 4.6 網際網路的路由 4.7 廣播與群播路由 (broadcast and multicast) R.-W. Hung 2011

23 4.3 路由器的內部 (Router) 路由器架構綜觀 四項元件 輸入埠 (input port) 交換結構 (switch fabric)
輸出埠 (output port) 路由處理器 (routing processor) 圖4.6 路由器架構 R.-W. Hung 2011

24 路由器主要功能 執行路由演算法/協定 (RIP、OSPF、BGP)
4.3 路由器 (Cont.) 路由器主要功能 執行路由演算法/協定 (RIP、OSPF、BGP) 將資料封包從輸入轉送到輸出連結 (input link  output link) R.-W. Hung 2011

25 輸入埠功能 實體層： 位元層級的接收 非集中式的交換： 給定一個資料封包目的端，使用輸入埠記憶體中的轉送表來尋找輸出埠 資料連結層：
4.3 路由器 (Cont.) 輸入埠功能 實體層： 位元層級的接收 非集中式的交換： 給定一個資料封包目的端，使用輸入埠記憶體中的轉送表來尋找輸出埠 目標：以「連線速度」完成輸入埠的處理過程 排隊：假如資料封包的抵達速率快於轉送進入交換結構的速率 資料連結層： 例如，乙太網路 見第五章 輸入埠的功能： 執行實體層功能，以作為實體連結進入路由器的終端。 執行連結層功能，以和輸入連結遠端的連結層功能進行互動操作。 執行查詢和轉送的功能，以讓轉送進入路由器交換結構的封包，會出現在適當的輸出埠中。 圖4.7 路由器輸入埠處理 R.-W. Hung 2011

26 交換結構 (switch fabric)    將路由器的輸入埠連接到輸出埠 三種交換結構  透過記憶體匯流排互連網路進行交換
4.3 路由器 (Cont.) 交換結構 (switch fabric) 將路由器的輸入埠連接到輸出埠 三種交換結構  透過記憶體匯流排互連網路進行交換    圖4.8 三種路由器交換技術 R.-W. Hung 2011

27 交換結構 (Cont.) 三種交換結構  (Cont.) 經由記憶體的交換機制 (第一代的路由器)
傳統的電腦，在CPU的直接控制下完成交換動作 封包被複製到系統記憶體，CPU以決定該送往那個輸出埠 速度會被記憶體頻寬所限制 (一個資料段會經過兩次匯流排) 記憶體 CPU 系統匯流排 輸入埠 輸出埠 R.-W. Hung 2011

28 交換結構 (Cont.) 三種交換結構  (Cont.) 經由匯流排的交換機制 資料封包經由共享的匯流排從輸入埠記憶體送到輸出埠記憶體
匯流排的競爭：交換速度受限於匯流排頻寬 不需經由routing processor的介入 若bus忙碌，則封包需在輸入埠中排隊 32 Gbps 匯流排的Cisco 5600：對存取路由器及企業路由器是足夠的 R.-W. Hung 2011

29 交換結構 (Cont.) 三種交換結構  (Cont.) 經由互連網路的交換機制 克服單一共用匯流排頻寬限制的方法
Banyan網路、其他的互連網路初始的建立，是將處理器連接到多處裡器 更進一步的設計：將資料封包分割成固定長度的封包單位，並將封包單位送入交換結構中 Cisco 12000：經由互連網路可達 60Gbps 的交換速率 (棋盤式交換結構) R.-W. Hung 2011

30 輸出埠功能 概念 需要緩衝區  當資料封包抵達結構的速率大於傳送速率 排程原則選擇佇列中的資料封包加以傳送 處理過程與輸入埠相反
4.3 路由器 (Cont.) 輸出埠功能 概念 需要緩衝區  當資料封包抵達結構的速率大於傳送速率 排程原則選擇佇列中的資料封包加以傳送 處理過程與輸入埠相反 圖4.9 路由器輸出埠處理 R.-W. Hung 2011

31 輸出埠功能 (Cont.) 輸出埠佇列 (queuing) 當經由交換結構抵達的速率超過輸出連結的速度
佇列排隊 (延遲) 以及因為輸出埠的緩衝區溢出導致的遺失！ 圖4.10 路由器輸出埠佇列 R.-W. Hung 2011

32 輸入埠佇列 交換結構速度慢於輸入埠的加總  可能在輸入佇列發生排隊的情形
4.3 路由器 (Cont.) 輸入埠佇列 交換結構速度慢於輸入埠的加總  可能在輸入佇列發生排隊的情形 連線前端 (HOL) 阻塞：在佇列最前端排隊的資料封包會阻止佇列中的其它資料封包往前移動 佇列延遲以及導因於輸入緩衝區溢出的遺失！ 圖4.11 路由器輸入埠佇列交換結構的HOL攔阻 R.-W. Hung 2011

33 第四章 導覽流程 4.1 簡介 4.2 虛擬線路網路和資料包網路 4.3 路由器的內部
4.4 網際網路IP協定 網際網路的轉送(forward)及定址 4.5 路由演算法 (routing algorithms) 4.6 網際網路的路由 4.7 廣播與群播路由 (broadcast and multicast) R.-W. Hung 2011

34 4.4 網際網路IP協定 網際網路的網路層 主機、路由器的網路層功能：  路由協定 (routing protocol)
 IP協定 (InternetProtocol protocol)  ICMP協定 (ICMP protocol) 傳輸層  IP 協定 定址規則 資料包格式 封包處理規則  路由協定 路徑選擇 RIP, OSPF, BGP 轉送表 網路層  ICMP 協定 錯誤回報 路由器 “訊號” 連結層 實體層 圖4.12 網際網路中網路層的功能協定 R.-W. Hung 2011

35 4.4.1 IP 資料(封)包(datagram)格式
IPv4 資料包格式 (p.4-29) IP 協定版本號碼 32 位元 資料(封)包總長度 (位元組) 標頭長度 (位元組) 標頭 長度 服務 類型 版本 資料包長度 用來分割/重組 (IPv6 不允許router進行分割) 資料的“類型” 16位元的識別碼 旗標 分割偏移量 剩餘站數的最大數量 (每經過一個路由器時減1) 生存期 (TTL) 上層 協定 網際網路 檢查和 32 位元來源端IP位址 32 位元目的端IP位址 傳送資料部分時 所使用的上層協定 (當資料包到達目的地時， 才會使用此欄位來判斷 要交給傳輸層的 哪一個協定TCP/UDP?) 選項欄位 (如果有的話) 例如：時間戳記、 路由紀錄、拜訪 的路由器特定列表 資料 (不固定長度，通常是 TCP 或 UDP 資料區段) 圖4.13 IPv4 資料包格式 R.-W. Hung 2011

36 TCP/IP有多少資源負擔? UDP/IP有多少資源負擔? 20 位元組 TCP header 20 位元組 IP header (標頭)
4.4.1 IP 資料包格式 (Cont.) TCP/IP有多少資源負擔? 20 位元組 TCP header 20 位元組 IP header (標頭) = 40 位元組 + 應用層的訊息負擔 UDP/IP有多少資源負擔? R.-W. Hung 2011

37 IP 分割(fragmentation)與重組(reassembly)
4.4.1 IP 資料包格式 (Cont.) IP 分割(fragmentation)與重組(reassembly) 為何需要將IP資料包(datagram)分割成較小的資料分段(fragment) ？ 網路的連結(link  資料連結層)具有 MTU (maximum transfer units, 最大的可傳輸大小)  最大的連結層訊框 (frame) 不同的連結層型態，不同的MTU 過大的 IP 資料包在網路內將被切分(分割) 一個資料包(datagram)變成好幾個較小的資料分段 只在目的端被“重組” IP 標頭位元用來識別、排序相關的分割 eg., 乙太網路的MTU=1500 bytes R.-W. Hung 2011

38 IP Fragmentation Applet:
4.4.1 IP 資料包格式 (Cont.) IP 分割與重組 (Cont.) 分割： in = 1 個大的資料包 out = 3 個小的資料分段 重組(只在目的端進行) IP Fragmentation Applet: 圖4.14 IP資料包的分割與重組 R.-W. Hung 2011

39 IP 分割與重組 (Cont.) 範例： 4000 位元組的資料包 MTU = 1500 位元組
表4.2 IP資料包的分段 (p. 4-33) ID =x offset =0 fragflag length =4000 1個大的資料包切割成3個小的資料分段 資料欄位中有1480 個位元組 (扣除20bytes header) 偏移量 = 185*8 = 1480 ID =x offset =0 fragflag =1 length =1500 ID =x offset =185 fragflag =1 length =1500 ID =x offset =370 fragflag =0 length =1040 R.-W. Hung 2011

40 IPv4定址(addressing) 簡介
介面：在主機/路由器以及實體連結的交界處 路由器通常擁有多個介面 主機通常擁有一個介面 IP 位址代表每個介面 = 223 1 1 1 圖4.15(a) 介面位址 R.-W. Hung 2011

41 子網路 (Sub-net) IP 位址： 什麼是子網路 ? 子網路部分 (高階位元) 主機部分 (低階位元) IP具有相同子網路部分
IPv4 的定址 (Cont.) 子網路 (Sub-net) IP 位址： 子網路部分 (高階位元) 主機部分 (低階位元) 什麼是子網路 ? IP具有相同子網路部分 的裝置介面 可以在沒有路由器的狀 況下，實體地互相連結 子網路 圖4.15(b) 包含 3 個子網路的網路 R.-W. Hung 2011

42 子網路 (Cont.) 表示方法： 要決定子網路，將 每一個介面和它的 主機或路由器分開， 建立分離的網路。 每一個分離的網路稱為
IPv4 的定址 (Cont.) 子網路 (Cont.) 表示方法： 要決定子網路，將 每一個介面和它的 主機或路由器分開， 建立分離的網路。 每一個分離的網路稱為 一個子網路。 /24: 最左邊的24 bits 定義子網路的位址 /24 /24 /24 子網路遮罩： /24 圖4.16 子網路位址 R.-W. Hung 2011

43 IPv4 的定址 (Cont.) 子網路 (Cont.) 有幾個子網路 ? 圖4.17 連接到6個子網路的三台路由器 R.-W. Hung 2011

44 IP 位址分配策略：CIDR CIDR：無分級跨領域路由法 (Classless InterDomain Routing)
IPv4 的定址 (Cont.) IP 位址分配策略：CIDR CIDR：無分級跨領域路由法 (Classless InterDomain Routing) 位址內任意長度的子網路部分 位址格式：a.b.c.d/x，其中 x 是位址的子網路部份的位元數 舊版分級法  classful addressing 8、16、24位元的A、B、C級子網路 C級子網路的網路遮罩= /8，共可容納282個IP位址 (0=net-id, broadcast=255) A、B級子網路，共可容納?個IP位址 廣播的IP位址(broadcasting) = 子網路部分 主機部分 is net-id is broadcasting IP available IPs = ~ /23 R.-W. Hung 2011

45 如何取得/設定主機IP 位址? 手動設定在系統管理的檔案中
IPv4 的定址 (Cont.) 如何取得/設定主機IP 位址? 手動設定在系統管理的檔案中 MS Windows：[控制台][網路連線][設定]tcp/ip[內容] UNIX： /etc/rc.config DHCP：動態主機配置協定 (Dynamic Host Configuration Protocol) 動態地由DHCP伺服器取得位址 “隨插即用” 的協定(plug-and-play protocol)  取得臨時IP位址 R.-W. Hung 2011

46 DHCP (動態主機配置協定) 目標 DHCP 運作 當主機連接網際網路時，主機會從網際網路伺服器以動態方式獲得它的IP位址
IPv4 的定址 (Cont.) DHCP (動態主機配置協定) 目標 當主機連接網際網路時，主機會從網際網路伺服器以動態方式獲得它的IP位址 在使用時會更新它的IP位址 允許重複使用網路位址 (當連結“上”時會鎖住這個臨時網路位址) 提供使用者使用手機來連接網際網路 DHCP 運作 主機廣播 “DHCP搜尋訊息” (廣播的IP位址= ) DHCP 伺服器會回應 “ DHCP提供訊息” 主機請求IP位址：“DHCP請求訊息” DHCP 伺服器傳送位址：“DHCP ack” 訊息 R.-W. Hung 2011

47 DHCP (Cont.) DHCP 用戶端伺服端情境 223.1.2.1 A 223.1.1.1 DHCP 伺服器
IPv4 的定址 (Cont.) DHCP (Cont.) DHCP 用戶端伺服端情境 A DHCP 伺服器 DHCP provides DHCP OK 新加入的 DHCP用戶端 broadcast B E 圖4.20 DHCP用戶端伺服端的運作流程 R.-W. Hung 2011

48 DHCP (Cont.) DHCP 用戶端伺服端情境 (Cont.) DHCP 伺服端： 223.1.2.5 新到來的用戶端 Time
IPv4 的定址 (Cont.) DHCP (Cont.) DHCP 用戶端伺服端情境 (Cont.) DHCP 伺服端： 新到來的用戶端  DHCP 搜尋 (broadcasting) 來源端 ： , 68 目的端 ： , 67 yiaddr： 處理行程：654  DHCP 提供 (broadcasting) 來源端 ： , 67 目的端 ： , 68 yiaddrr： 處理行程：654 生存期：3600 secs  DHCP 請求(broadcasting) 來源端 ： , 68 目的端 ： , 67 yiaddrr： 處理行程：655 生存期：3600 secs  DHCP ACK 來源端 ： , 67 目的端 ： , 68 yiaddrr： 處理行程：655 生存期：3600 secs Time Time 圖4.21 DHCP用戶端伺服端的互動 R.-W. Hung 2011

49 NAT  網路位址轉譯 (Network Address Translation)
IPv4 的定址 (Cont.) NAT  網路位址轉譯 (Network Address Translation) 動機 整個區域網路對外界而言，通常只有一個 IP 位址 同一區域網路內的主機，可由router來設定其IP位址 所有區域網路內的主機送出的封包均為同一IP 位址 外界送入的封包也是同一IP位址 Router如何將外界送入的封包，正確傳送給區域網路內的主機？  NAT 區域網路的外面網路部份 區域網路 (例如，家庭網路) /24 router 所有離開區域網路的資料包都 具有相同的單一來源NAT IP 位址: , 不同的來源埠號 在這個網路中，來源端或 目的端傳送的資料包， 具有 /24 的來源 及主機位址 (一般而言) R.-W. Hung 2011

50 NAT (Cont.)     實作  NAT 路由器必須：
IPv4 的定址 (Cont.) NAT (Cont.) 實作  NAT 路由器必須： 送出資料(封)包時：更換每一個送出的資料包 (來源IP位址、埠號) 成為 (NAT IP 位址、新埠號) . . . 遠端的主機(區網外)會使用 (NAT IP 位址、新埠號) 做為目的端位址，來做回應 記憶 (在NAT 轉譯表中) 每一個 (來源端 IP 位址、埠號) 到 (NAT IP 位址、新埠號) 的轉譯對應 進入資料包時：更換每個進入資料封包目的欄位中的 (NAT IP 位址、新埠號) 為儲存在 NAT表中的對應 (來源端 IP 位址、埠號) 區域網路的外面網路部份 S= , 5501 D= , 80  S= , 3345 D= , 80  S= , 80 D= , 5501  S= , 80 D= , 3345  router , 5001 , 3345 ... R.-W. Hung 2011

51 NAT 轉譯表 (translation table)
IPv4 的定址 (Cont.) NAT (Cont.) 實作 NAT 轉譯表 (translation table) WAN端 LAN端 , , 3345 1： host 傳送資料(封)包到 , 80 2： NAT 路由器將資料 包中的來源位址從 , 3345轉成 , 5001 並更新轉譯表 S： , 3345 D： , 80 1 區域網路的外面網路部份 S： , 80 D： , 3345 4 S： , 5001 D： , 80 2 router S： , 80 D： , 5001 3 4： NAT 路由器將資料包目的位址從 , 5001 轉成 , 3345 3： 回應抵達 目的端位址： , 5001 圖4.22 NAT網路位址轉譯 R.-W. Hung 2011

52 NAT的穿越問題 (traversal) What ? ? 網外用戶端要連接到伺服器的 192.168.0.123位址
IPv4 的定址 (Cont.) NAT的穿越問題 (traversal) What ? 網外用戶端要連接到伺服器的 位址 伺服器位址 區域連線到 LAN (用戶端不能使用它的目標位址) 只能有一個外部可見的NATted 位址： 用戶端 ? NAT 路由器 R.-W. Hung 2011

53 NAT的穿越問題 (Cont.) How ? ? 解1： 靜態配置NAT給予埠號並請求連結向前進入到伺服器
IPv4 的定址 (Cont.) NAT的穿越問題 (Cont.) How ? 解1： 靜態配置NAT給予埠號並請求連結向前進入到伺服器 例如： ( 、埠號2500) 永遠向前到 ( 、埠號 25000) 用戶端 ? NAT 路由器 R.-W. Hung 2011

54 NAT的穿越問題 (Cont.) How ? (Cont.) ? 解2：通用型隨插即用 (UPnP) 網際網路閘道裝置 (IGD) 協定
IPv4 的定址 (Cont.) NAT的穿越問題 (Cont.) How ? (Cont.) 解2：通用型隨插即用 (UPnP) 網際網路閘道裝置 (IGD) 協定 　允許NATted 主機到： 學習公用IP位址( ) 列舉現有的對映埠號 增加/移除對映的埠號(租借時間) i.e.自動配置靜態NAT的對映埠號 用戶端 ? IGD , port = 3128  , port = 80 具UPnP的 NAT 路由器 R.-W. Hung 2011

55 4.4.3 網際網路控制訊息協定(Internet Control Message Protocol, ICMP)
主機和路由器間互相交換網路層資訊的協定 錯誤回報：無法到達主機、網路、埠號、協定 回應請求/回覆 (由ping所使用) ICMP通常被視為IP的一部份 ICMP 訊息在IP封包中載送 ICMP 訊息 類型、 代碼、加上導致錯誤的 IP 資料封包的前八個位元組 圖4.23 ICMP 訊息類型 R.-W. Hung 2011

56 Traceroute 與 ICMP 來源端傳送一系列的UDP資料區段給目的端 當第 n 個資料段抵達第 n 個路由器：
4.4.3 網際網路控制訊息協定(Cont.) Traceroute 與 ICMP 來源端傳送一系列的UDP資料區段給目的端 第一個具有 TTL =1 第二個具有 TTL =2、依此類推 不可能的埠號 當第 n 個資料段抵達第 n 個路由器： 路由器刪除資料段 接著傳送一個 ICMP 訊息給來源端 (類型 11、代碼 0) 訊息中包含了路由器名稱以及IP位址 當 ICMP 訊息抵達時，來源端會計算RTT Traceroute 會重複這個步驟三次 停止的標準 UDP 資料區段最終會到達目的主機 目的端會回傳 ICMP “主機無法到達” 封包 (類型 3、代碼 3) 當來源端收到這個ICMP時，則會停止 R.-W. Hung 2011

57 IPv6 第6版IP協定 動機 IPv6資料封包格式 32位元的位址空間 (IPv4) 很快就要使用殆盡了 標頭格式可以幫助處理/轉送更快速
標頭的改變可以幫助QoS (Quality of Service) IPv6資料封包格式 固定長度的40位元組標頭 不允許切割 (4.4.1節) 圖4.24 IPv6 資料包格式 R.-W. Hung 2011

58 從 IPv4 轉換成 IPv6 動機 建立通道 並不是所有的路由器可以同時升級 無法使用 “揭旗日”的方式，將IPv4全部轉成IPv6
4.4.4 IPv6 (Cont.) 從 IPv4 轉換成 IPv6 動機 並不是所有的路由器可以同時升級 無法使用 “揭旗日”的方式，將IPv4全部轉成IPv6 假如網路的運作混和了IPv4和IPv6的路由器會如何？  混亂 建立通道 在 IPv4 資料包的承載資料中，封裝完整的IPv6資料包、送往 IPv6 路由器 A B E F 通道 邏輯面： IPv6 IPv6 IPv6 IPv6 A B E F 實際面： IPv6 IPv6 IPv4 IPv4 IPv6 IPv6 圖4.26 IPv6 融入IPv4 的通道建立 R.-W. Hung 2011

59 從 IPv4 轉換成 IPv6 (Cont.) 建立通道 (Cont.) A B E F 通道 邏輯面： IPv6 IPv6 IPv6
D E F 實際面： IPv6 IPv6 IPv4 IPv4 IPv6 IPv6 資料流： X 來源端： A 目的端： F 資料 A-到-B： IPv6 B-到-C： IPv6 封裝在 IPv4裡面 來源端：B 目的端：E 資料流： X 來源端： A 目的端： F 資料 D-到-E： IPv6 封裝在 IPv4 裡面 來源端：B 目的端：E 資料流： X 來源端： A 目的端： F 資料 E-到-F： IPv6 資料流： X 來源端： A 目的端： F 資料 R.-W. Hung 2011

60 第四章 導覽流程 4.1 簡介 4.2 虛擬線路網路和資料包網路 4.3 路由器的內部
4.4 網際網路IP協定 網際網路的轉送(forward)及定址 4.5 路由演算法 (routing algorithms) 4.6 網際網路的路由 4.7 廣播與群播路由 (broadcast and multicast) R.-W. Hung 2011

61 4.5 路由演算法 (routing algorithms)
路由(routing) vs. 轉送(forward) 轉送 封包到達router時，router會查詢其轉送表(forwarding table)並決定將該封包送網哪一個連結介面(link interface) 路由(routing) 網路層必需決定封包從傳送端router到接收端router所採取的路徑 (path) routing(繞徑) 的工作在於判斷傳送端到接收端，通過路由器網路的良好路徑(path/route) 0111 source dest R.-W. Hung 2011

62 路由和轉送的交互作用 1 2 3 路由演算法 (routing algorithm) 標頭值 輸出連結 抵達封包 的標頭值
4.5 路由演算法 (Cont.) 路由和轉送的交互作用 路由演算法 (routing algorithm) 本機轉送表 (forward table) 標頭值 輸出連結 0100 0101 0111 1001 3 2 1 抵達封包 的標頭值 1 0111 2 3 圖4.2 路由演算法根據轉送表來轉送資料包 R.-W. Hung 2011

63 抽象化圖形 (abstract graph)
4.5 路由演算法 (Cont.) 抽象化圖形 (abstract graph) 圖形：G = (N, E) N = 一組路由器的集合 (node set) = { u, v, w, x, y, z } E = 一組連結的集合 (edge set) = { (u, v), (u, x), (v, x), (v, w), (x, w), (x, y), (w, y), (w, z), (y, z) } [註] 抽象化圖形在其它的網路應用上也是很有用的 例如：P2P中，N 為對等點的集合、而 E 為TCP連線的集合 u y x w v z 2 1 3 5 圖4.27 電腦網路的抽象化圖形模型 R.-W. Hung 2011

64 抽象化圖形 (Cont.) 成本 (cost, weight) 問題：u 和 z 之間的最小成本路徑為何?
c(x, y) = 連結 (x, y) 的成本(權重) 例如，c(w, z) = 5 成本可能永遠是 1、或是相反地與頻寬相關、或是相反地與壅塞 程度相關 路徑 (x1, x2, x3, ..., xp) 的成本 = c(x1, x2) + c(x2, x3) c(xp1, xp) 問題：u 和 z 之間的最小成本路徑為何? 路由演算法：尋找最小成本路徑的演算法 u y x w v z 2 1 3 5 圖4.27 電腦網路的抽象化圖形模型 R.-W. Hung 2011

65 路由演算法的分類 整體或分散式資訊? (global vs. distributed-decentralized)
4.5 路由演算法 (Cont.) 路由演算法的分類 整體或分散式資訊? (global vs. distributed-decentralized) 整體的 (global) 所有的路由器都擁有完整的拓樸(topology)及連結成本(link cost)資訊 “連結狀態” 演算法 (link-state, LS) 最短路徑計算在某台電腦或多台固定電腦中執行  centralized 分散式 (distributed) 路由器只知道實體連結的鄰居以及到鄰居的連結成本 最短路徑經由分散反覆地計算，以及與鄰居交換資訊 “距離向量” 演算法 (distance-vector, DV) 靜態的或動態的? (static vs. dynamic) 靜態的 (static) 路徑隨著時間緩慢地改變 動態的 (dynamic) 較快速地改變路徑 週期性的更新 回應連結成本的改變 R.-W. Hung 2011

66 4.5.1 連結狀態路由演算法 (LS algorithm)
Dijkstra 演算法 已知所有節點的網路拓樸、連結成本 經由「連結狀態廣播」完成 (broadcasting algorithm) 每個節點都擁有一樣的資訊 從一個節點(來源端)開始  到所有其它節點，計算最小成本路徑 (single source shortest paths) 給定此節點的轉送表 循環式的(iterative)：在 k 次循環以後，會知道 k 個目的節點的最小成本路徑 符號： c(x, y)：從節點x 到 y 的連結成本; =  假如不是直接連結(非鄰居) D(v)：目前從來源端到目的端 v 的最小成本路徑的成本值 S：一組已計算最小成本路徑的節點集合 R.-W. Hung 2011

67 Dijkstra 演算法 (Cont.) // Initialization 1 S = {u}; //起始節點 u
2 for all nodes v do if v adjacent to u then D(v) = c(u, v); else D(v) = ; 5 Repeat find w not in S such that D(w) is a minimum; add w to S; for all v adjacent to w and not in S do update D(v) by the following: D(v) = min( D(v), D(w) + c(w, v) ); // new cost to v is either old cost to v or known // shortest path cost to w plus cost from w to v 11 Until all nodes in S; R.-W. Hung 2011

68 Dijkstra 演算法 (Cont.) 範例 5 w* v x w y z D(w*) 2 1 5    Initially,
S = {u}; 3 v w 2 5 u 2 1 z 3 1 w* v x w y z D(w*)   Minimum D()  x S = {u, x}; 2 x y 1 w* v x w y z D(w*)   Minimum D()  v S = {u, x, v}; w* v x w y z D(w*)  Minimum D()  w S = {u, x, v, y, w}; w* v x w y z D(w*)  Minimum D()  y S = {u, x, v, y}; w* v x w y z D(w*)  Minimum D()  z S = {u, x, v, y, w, z}; R.-W. Hung 2011

69 Dijkstra 演算法 (Cont.) 範例 (Cont.) 結果 從 u 開始的最短路徑樹： u 的轉送表： v w u z x y
(u, x) 目的 連結 R.-W. Hung 2011

70 Dijkstra 演算法 (Cont.) 討論 演算法複雜度：n 個節點 可能的問題  震盪現象 (圖4.29)
每個迴圈：需要確認不在 S 中的每個節點 w n(n+1)/2 個比較：O(n2) 可能更有效率的實作： O(n log n) 可能的問題  震盪現象 (圖4.29) 連結成本 = 該連結的載送負荷 連結的成本可能是不對稱的 (    ) A D C B 1 1+e e 2+e 初始 … 重新計算路由 … 重新計算 R.-W. Hung 2011

71 4.5.2 距離向量演算法 (DV algorithm)
距離向量演算法 (Distance-Vector) 概念 分散式 各個節點會從一個或多個直接相鄰的節點中取得一些資訊，進行運算，然後，將結果散佈給其相鄰節點 循環式 持續運作，直到沒有資訊可以交換 非同步 不需所有節點同時運作 Bellman-Ford 方程式 (動態程式規劃) dx(y) = minv {c(x, v) + dv(y) } dx(y) = 從 x 到 y 之最小成本路徑的成本 minv 符號作用於 x 的所有相鄰節點 v v1 x y v1 ... vk R.-W. Hung 2011

72 Bellman-Ford 方程式 範例 dv(z) = 5、dx(z) = 3、dw(z) = 3
4.5.2 距離向量演算法 (Cont.) Bellman-Ford 方程式 範例 dv(z) = 5、dx(z) = 3、dw(z) = 3 du(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 可達成最小路徑的節點是最短路徑上的下一站  轉送表 5 3 v w 2 5 u 2 1 z 3 1 2 x y 1 R.-W. Hung 2011

73 距離向量演算法 符號 Dx(y) = 從 x 到 y 的預估最小成本 節點 x 知道到每一個鄰居 v 的成本： c(x, v)
4.5.2 距離向量演算法 (Cont.) 距離向量演算法 符號 Dx(y) = 從 x 到 y 的預估最小成本 節點 x 知道到每一個鄰居 v 的成本： c(x, v) 節點 x 維護 距離向量：Dx = [Dx(y)：y  N ] 節點 x 也維護它的鄰居的距離向量 對每一個鄰居 v， x 維護 Dv = [Dv(y)：y  N ] R.-W. Hung 2011

74 距離向量演算法 (Cont.) 基本想法 DV演算法 每一個節點定期地傳送它自己的距離向量預估值給鄰居節點
當一個節點 x 收到來自鄰居的新 Dv預估值，它會使用Bellman-Ford方程式更新它自己的Dv向量： Dx(y) = minv {c(x, v) + Dv(y) },  y  N 在一般的自然狀況下，預估的 Dx(y) 會涵蓋真正的最小成本 dx(y) 每一個節點的運作： DV演算法 R.-W. Hung 2011

75 距離向量演算法 (Cont.) 範例 y 2 1 x z 7 節點 x x y z x 0 2 7 y    z   
Dx(z) = min{c(x, z) + Dz(z), c(x, y) + Dy(z)} = min{7+0, 2+1} = 3 距離向量演算法 (Cont.) 範例 x z 1 2 7 y Dx(y) = min{c(x, y) + Dy(y), c(x, z) + Dz(y)} = min{2+0, 7+1} = 2 節點 x x y z x y    z    來源節點 目的節點 x y z x 0 y z 來源節點 目的節點 x y z x y z 來源節點 目的節點 節點 y x y z x    y z    來源節點 目的節點 x y z x y z 來源節點 目的節點 x y z x y z 來源節點 目的節點 節點 z x y z x    y    z 來源節點 目的節點 x y z x y z 來源節點 目的節點 x y z x y z 來源節點 目的節點 R.-W. Hung 2011

76 距離向量演算法 (Cont.) 連結成本改變 節點偵測到區域連結成本的改變 更新路由資訊，重新計算距離向量 假如 DV 改變，通知鄰居節點
連結成本改變情境 在時間點 t0， y 偵測到連結成本的變更，它會更新距離向量，並通知相鄰節點 在時間點 t1，z 接收來自y 的更新訊息，更新自己的表格。它會計算出到 x 的新最小成本，並傳送給相鄰節點 在時間點 t2，y 會接收到 z 的更新訊息，並且更新自己的距離表格。因為 y 的最小成本並沒有改變，所以 y 不會傳送任何訊息給 z x z 1 2 7 y 1 R.-W. Hung 2011

77 LS 與 DV 演算法的比較 訊息複雜度 收斂速度 強韌性：假如路由器故障會發生什麼問題? 目前唯二被實際使用在網際網路中的路由演算法
4.5.2 LS vs. DV LS 與 DV 演算法的比較 訊息複雜度 LS： n個節點、 E條連結  O(nE) 個傳送出去的訊息 DV：只在鄰居之間交換  收斂時間不固定 收斂速度 LS：O(n2) 演算法需要 O(nE) 個訊息  可能有擺動 DV： 收斂速度不固定  可能產生路由迴圈、計算到無窮大的問題 強韌性：假如路由器故障會發生什麼問題? LS： 節點可能會廣播不正確的連結成本 每個節點只計算它自己的轉送表 DV： DV 節點可能會廣播不正確的路徑成本 每個節點的轉送表也被其他人所使用  將錯誤傳播到網路中 目前唯二被實際使用在網際網路中的路由演算法 R.-W. Hung 2011

78 第四章 導覽流程 4.1 簡介 4.2 虛擬線路網路和資料包網路 4.3 路由器的內部
4.4 網際網路IP協定 網際網路的轉送(forward)及定址 4.5 路由演算法 (routing algorithms) 4.6 網際網路的路由 4.7 廣播與群播路由 (broadcast and multicast) R.-W. Hung 2011

79 4.6 網際網路的路由 路由資訊協定 (Routing Information Protocol, RIP) 距離向量演算法
4.6 網際網路的路由 路由資訊協定 (Routing Information Protocol, RIP) 距離向量演算法 包含在1982年的 BSD-UNIX Distribution 中 距離計量：hop數目 (最大 = 15 個 hops) hop count = cost D C B A u v w x y z 目的端 轉送次數 u v w x y z 圖4.34 從來源路由器A到各個子網路的hop數(站數) R.-W. Hung 2011

80 RIP 廣播 RIP 範例 距離向量：每隔30秒使用回應訊息(也稱做通告)、在相鄰節點間交換
4.6.1 RIP (Cont.) RIP 廣播 距離向量：每隔30秒使用回應訊息(也稱做通告)、在相鄰節點間交換 每個通告：自治網路系統內最多達25個目的端子網路的清單 RIP 範例 z w x y A D B C 圖4.35 RIP 範例 R.-W. Hung 2011

81 RIP 範例 (Cont.) D 中的路由表 w A 2 目的端網路 下一個路由器 到目的端所需的轉送次數 y B 2 z B 7
目的端網路 下一個路由器 到目的端所需的轉送次數 w A 2 y B 2 z B 7 x z w x y A D B C 圖4.35 RIP 範例 R.-W. Hung 2011

82 RIP 範例 (Cont.) D 中的路由表 w A 2 目的端網路 下一個路由器 到目的端所需的轉送次數 y B 2 z B 7
目的端網路 下一個路由器 到目的端所需的轉送次數 w A 2 y B 2 z B 7 x A 5 從A到D的通告： z w x y A D B C 圖4.35 RIP 範例 R.-W. Hung 2011

83 第四章 導覽流程 4.1 簡介 4.2 虛擬線路網路和資料包網路 4.3 路由器的內部
4.4 網際網路IP協定 網際網路的轉送(forward)及定址 4.5 路由演算法 (routing algorithms) 4.6 網際網路的路由 4.7 廣播與群播路由 (broadcast and multicast) R.-W. Hung 2011

84 4.7 廣播與群播路由 廣播路由(broadcasting) 從來源端傳送封包到所有其它的節點 廣播方式 來源端複製 網路中複製  R1
4.7 廣播與群播路由 廣播路由(broadcasting) 從來源端傳送封包到所有其它的節點 廣播方式 來源端複製 網路中複製  複製 建立/傳送 複製 R1 R1 複製 R2 R2 cycle ? 產生無止盡地broadcast storm  序號控制  reversed path forwarding (圖4.44) (p )  spanning tree broadcasting 來源端如何決定接收位址 ? R3 R4 R3 R4 來源端複製 網路中複製 圖4.43 來源端複製與網路中複製 R.-W. Hung 2011

85 4.7.1 擴張樹廣播 (spanning tree broadcasting)
節點沿著擴張樹轉送複本 A B G D E C F (a) 從A點開始廣播 (b) 從D點開始廣播 圖4.45 沿著擴張樹進行廣播 R.-W. Hung 2011

86 4.7.1 擴張樹廣播 (spanning tree broadcasting)
中心式擴張樹的建構 選擇中心節點 每個節點會將加入訊息以單點傳播方式傳給中心節點 訊息會被轉送，直到它抵達一個已經屬於擴張樹的節點 節點沿著擴張樹轉送複本 A A 3 B B C C 4 2 D D F E F E 1 5 G G (a) 擴展樹建立步驟 (b) 建立的擴展樹 圖4.46 擴張樹的中心式建構 (E為中心節點) R.-W. Hung 2011

87 群播 What ? 群播路由的目標：找到一棵樹 (或是多棵樹) 將地區群播群組成員的路由器連結起來 將資料封包傳送到特定群組的節點(路由器)
4.7.2 群播 (multicasting) 群播 What ? 將資料封包傳送到特定群組的節點(路由器) 群播路由的目標：找到一棵樹 (或是多棵樹) 將地區群播群組成員的路由器連結起來 樹：不會使用到路由器間的所有路徑 以來源端為基礎：從每個來源端到接收端是一個不同的樹 分享樹：所有的群組成員都使用相同的樹 以來源為基礎的樹 分享樹 R.-W. Hung 2011

88 建立群播樹的方法 使用來源為基礎的樹：一棵樹一個來源端 群組分享樹：群組只使用一棵樹 最短路徑樹 反向路徑傳送 最小擴張 (Steiner)
4.7.2 群播 (Cont.) 建立群播樹的方法 使用來源為基礎的樹：一棵樹一個來源端 最短路徑樹 反向路徑傳送 群組分享樹：群組只使用一棵樹 最小擴張 (Steiner) 以中心為基礎的樹 R.-W. Hung 2011

89 建立群播樹的方法 (Cont.) 最短路徑樹： 群播轉送樹：從來源端到所有接收端的最短路徑路由所產生的樹 Dijkstra 演算法
說明 R1 2 R4 1 擁有附加群組成員的路由器 沒有附加群組成員的路由器 R2 5 3 4 用來轉送的連結 i 表示演算法將連結加入的順序 i R5 6 R3 R6 R7 R.-W. Hung 2011

90 建立群播樹的方法 (Cont.) 分享樹：Steiner 樹 Steiner 樹：最小成本樹、連接全部擁有群組成員的路由器 為NP完全問題
極佳的試探存在 實際不使用： 計算複雜度 需要整個網路的資訊 龐大的：每當有路由器加入/離開時需要重新執行 R.-W. Hung 2011

91 建立群播樹的方法 (Cont.) 以中心為基礎的樹 大家一起分享的單一傳遞樹 (ref. 圖4.46) 在樹中有一個路由器被標記為“中心”
加入： 邊緣路由器傳送單點傳播的加入訊息給中心路由器 加入訊息由中間的路由器「處理」並轉送到中心 加入訊息會觸碰到此中心現存樹的分枝、或是抵達中心 加入訊息所使用的路徑會變成這個路由器所使用的樹的分枝 假設我們選擇 R6 做為中心： 說明 R1 R4 擁有附加群組成員的路由器 3 沒有附加群組成員的路由器 R2 1 2 加入訊息所產生的路徑順序 R5 R3 1 R6 R7 R.-W. Hung 2011

92 End of Chapter 4 R.-W. Hung 2011