Chapter 4 Network Layer (網路層)
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
Topic Overview (Cont.) 目標 (Goal) 了解網路層服務背後(隱藏)的原理： 網際網路上的例證、實作 網路層服務模型 轉送(forward) vs. 路由(route) 路由器(router)如何運作 路由演算法 (路徑的選擇) 進階課題： IPv6 網際網路上的例證、實作 應用層 傳輸層 網路層 連結層 實體層 R.-W. Hung 2011
第四章 導覽流程 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
4.1 簡介 網路層 從傳送主機到接收主機傳輸的資料區段(segment) 在傳送端將資料區段封裝在資料包(datagram)中 4.1 簡介 網路層 從傳送主機到接收主機傳輸的資料區段(segment) 在傳送端將資料區段封裝在資料包(datagram)中 在接收端，將資料區段傳送到傳輸層 每一台主機、路由器中都有網路層協定 路由器會檢查經過它的所有IP資料段中的標頭欄位 應用層 傳輸層 網路層 連結層 實體層 R.-W. Hung 2011
網路層的通訊 圖4.1 網路層 4.1 簡介 (Cont.) R.-W. Hung 2011 應用層 傳輸層 網路層 資料連結層 實體層
兩個主要的網路層功能 轉送(forward)：將封包從路由器的輸入轉送到適當的路由器輸出 4.1 簡介 (Cont.) 兩個主要的網路層功能 轉送(forward)：將封包從路由器的輸入轉送到適當的路由器輸出 路由(繞送、route)：決定封包從來源端到目的端的路由(路徑) 路由演算法 (routing algorithm) 比喻： 路由：計畫從來源到目的旅行的過程 轉送：經過單一交流道的過程 R.-W. Hung 2011
兩個主要的網路層功能 (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
建立連線 (connection setup) 4.1 簡介 (Cont.) 建立連線 (connection setup) 在某些網路架構中網路層的第三個重要功能 ATM、訊框轉播(frame relay)、X.25 在網路層資料包傳送之前，兩個主機以及介於其間的所有路由器需先建立虛擬連線 (VC，Virtual connection) 路由器介入 此程序稱為「建立連線」 網路層以及傳輸層的連線服務： 網路層：兩個主機之間 (在VCs案例中也許可以介入路由器) 傳輸層：兩個行程之間 R.-W. Hung 2011
網路服務模型 (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
網路服務模型 (Cont.) 表4.1 網際網路、ATM CBR、ATM ABR 服務模型 4.1 簡介 (Cont.) R.-W. Hung 2011
第四章 導覽流程 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
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
虛擬線路 (Virtual Circuit) 4.2.1 虛擬線路網路 (VC) 虛擬線路 (Virtual Circuit) 意義 來源端到目的端的路徑，如同電話線路 效能良好 沿著來源端到目的端路徑的網路行為 使用 在資料開始傳送前，必須為每個連結建立連線、拆除 每個封包會承載一個 VC 識別碼 (並非目的端主機位址) 在來源端到目的端的路徑上，每個路由器都必須維護每個經過的連線的「狀態」 連結(link)和路由器(router)的資源 (頻寬、緩衝區) 可能會配置給VC (專用資源= 預期的伺服器) R.-W. Hung 2011
虛擬線路VC (Cont.) VC 實作 一條 VC 包含了： 一個屬於虛擬線路的封包會載送一個 VC 編號 一條來源端至目的端間的路徑 VC 編號，路徑上的每一個連結都有一個編號 路徑上的每一個路由器轉送表中的紀錄 一個屬於虛擬線路的封包會載送一個 VC 編號 在每一個連結，VC 編號必須改變 新的 VC 編號從轉送表中得來 R.-W. Hung 2011
虛擬線路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
虛擬線路 訊號協定 (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
4.2.2 資料包網路 (Datagram network) 意義 在網路層不需要建立連線 路由器：沒有終端對終端的連線狀態 沒有網路層的「連線」觀念 使用目的端主機位址轉送封包 在同一對來源-目的端之間的封包可能會使用不同的路徑 應用層 傳輸層 網路層 資料連結層 實體層 應用層 傳輸層 網路層 資料連結層 實體層 1. 送出資料 2. 接收資料 圖4.5 資料包網路 R.-W. Hung 2011
4.2.2 資料包網路 (Datagram network) 資料包網路 (Cont.) 轉送表 (forwarding table) 40億個可能的紀錄 (32位元IP位址) 路由器不需儲存40億個項目 R.-W. Hung 2011
4.2.2 資料封包網路 (Datagram network) 資料包網路 (Cont.) 轉送表 (Cont.) 最長前置代碼對應 (longest prefix matching) 範例： DA = 11001000 00010111 00010110 10100001 選擇哪一個介面來forwarding ? DA = 11001000 00010111 00011000 10101010 選擇哪一個介面來forwarding ? R.-W. Hung 2011
虛擬線路網路 vs. 資料(封)包網路 資料包網路 網際網路 4.2 虛擬線路網路和資料包網路 虛擬線路網路 vs. 資料(封)包網路 資料包網路 網際網路 電腦之間的資料交換 “彈性的” 服務，沒有嚴格的時限要求 “聰明的” 終端系統 (電腦) 能夠適應、執行控制、錯誤復原 網路內部是簡單的、邊緣是複雜的 許多連結型態 不同的特質 統一的服務困難 虛擬線路網路 ATM (Asynchronous Transfer Mode) 來自電話系統 人類的對話： 嚴格的時限、可靠性的要求 保證服務的需求 “愚笨的” 終端系統 電話 網路內部是複雜的、邊緣是簡單的 R.-W. Hung 2011
第四章 導覽流程 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
4.3 路由器的內部 (Router) 路由器架構綜觀 四項元件 輸入埠 (input port) 交換結構 (switch fabric) 輸出埠 (output port) 路由處理器 (routing processor) 圖4.6 路由器架構 R.-W. Hung 2011
路由器主要功能 執行路由演算法/協定 (RIP、OSPF、BGP) 4.3 路由器 (Cont.) 路由器主要功能 執行路由演算法/協定 (RIP、OSPF、BGP) 將資料封包從輸入轉送到輸出連結 (input link output link) R.-W. Hung 2011
輸入埠功能 實體層： 位元層級的接收 非集中式的交換： 給定一個資料封包目的端，使用輸入埠記憶體中的轉送表來尋找輸出埠 資料連結層： 4.3 路由器 (Cont.) 輸入埠功能 實體層： 位元層級的接收 非集中式的交換： 給定一個資料封包目的端，使用輸入埠記憶體中的轉送表來尋找輸出埠 目標：以「連線速度」完成輸入埠的處理過程 排隊：假如資料封包的抵達速率快於轉送進入交換結構的速率 資料連結層： 例如，乙太網路 見第五章 輸入埠的功能： 執行實體層功能，以作為實體連結進入路由器的終端。 執行連結層功能，以和輸入連結遠端的連結層功能進行互動操作。 執行查詢和轉送的功能，以讓轉送進入路由器交換結構的封包，會出現在適當的輸出埠中。 圖4.7 路由器輸入埠處理 R.-W. Hung 2011
交換結構 (switch fabric) 將路由器的輸入埠連接到輸出埠 三種交換結構 透過記憶體匯流排互連網路進行交換 4.3 路由器 (Cont.) 交換結構 (switch fabric) 將路由器的輸入埠連接到輸出埠 三種交換結構 透過記憶體匯流排互連網路進行交換 圖4.8 三種路由器交換技術 R.-W. Hung 2011
交換結構 (Cont.) 三種交換結構 (Cont.) 經由記憶體的交換機制 (第一代的路由器) 傳統的電腦，在CPU的直接控制下完成交換動作 封包被複製到系統記憶體，CPU以決定該送往那個輸出埠 速度會被記憶體頻寬所限制 (一個資料段會經過兩次匯流排) 記憶體 CPU 系統匯流排 輸入埠 輸出埠 R.-W. Hung 2011
交換結構 (Cont.) 三種交換結構 (Cont.) 經由匯流排的交換機制 資料封包經由共享的匯流排從輸入埠記憶體送到輸出埠記憶體 匯流排的競爭：交換速度受限於匯流排頻寬 不需經由routing processor的介入 若bus忙碌，則封包需在輸入埠中排隊 32 Gbps 匯流排的Cisco 5600：對存取路由器及企業路由器是足夠的 R.-W. Hung 2011
交換結構 (Cont.) 三種交換結構 (Cont.) 經由互連網路的交換機制 克服單一共用匯流排頻寬限制的方法 Banyan網路、其他的互連網路初始的建立，是將處理器連接到多處裡器 更進一步的設計：將資料封包分割成固定長度的封包單位，並將封包單位送入交換結構中 Cisco 12000：經由互連網路可達 60Gbps 的交換速率 (棋盤式交換結構) R.-W. Hung 2011
輸出埠功能 概念 需要緩衝區 當資料封包抵達結構的速率大於傳送速率 排程原則選擇佇列中的資料封包加以傳送 處理過程與輸入埠相反 4.3 路由器 (Cont.) 輸出埠功能 概念 需要緩衝區 當資料封包抵達結構的速率大於傳送速率 排程原則選擇佇列中的資料封包加以傳送 處理過程與輸入埠相反 圖4.9 路由器輸出埠處理 R.-W. Hung 2011
輸出埠功能 (Cont.) 輸出埠佇列 (queuing) 當經由交換結構抵達的速率超過輸出連結的速度 佇列排隊 (延遲) 以及因為輸出埠的緩衝區溢出導致的遺失！ 圖4.10 路由器輸出埠佇列 R.-W. Hung 2011
輸入埠佇列 交換結構速度慢於輸入埠的加總 可能在輸入佇列發生排隊的情形 4.3 路由器 (Cont.) 輸入埠佇列 交換結構速度慢於輸入埠的加總 可能在輸入佇列發生排隊的情形 連線前端 (HOL) 阻塞：在佇列最前端排隊的資料封包會阻止佇列中的其它資料封包往前移動 佇列延遲以及導因於輸入緩衝區溢出的遺失！ 圖4.11 路由器輸入埠佇列交換結構的HOL攔阻 R.-W. Hung 2011
第四章 導覽流程 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
4.4 網際網路IP協定 網際網路的網路層 主機、路由器的網路層功能： 路由協定 (routing protocol) IP協定 (InternetProtocol protocol) ICMP協定 (ICMP protocol) 傳輸層 IP 協定 定址規則 資料包格式 封包處理規則 路由協定 路徑選擇 RIP, OSPF, BGP 轉送表 網路層 ICMP 協定 錯誤回報 路由器 “訊號” 連結層 實體層 圖4.12 網際網路中網路層的功能協定 R.-W. Hung 2011
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
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
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
IP Fragmentation Applet: 4.4.1 IP 資料包格式 (Cont.) IP 分割與重組 (Cont.) 分割： in = 1 個大的資料包 out = 3 個小的資料分段 重組(只在目的端進行) IP Fragmentation Applet: http://media.pearsoncmg.com/aw/aw_kurose_network_2/applets/ip/ipfragmentation.html 圖4.14 IP資料包的分割與重組 R.-W. Hung 2011
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
IPv4定址(addressing) 簡介 介面：在主機/路由器以及實體連結的交界處 路由器通常擁有多個介面 主機通常擁有一個介面 IP 位址代表每個介面 223.1.1.1 223.1.2.1 223.1.1.2 223.1.1.4 223.1.2.9 223.1.1.3 223.1.3.27 223.1.2.2 223.1.1.1 = 11011111 00000001 00000001 00000001 223.1.3.1 223.1.3.2 223 1 1 1 圖4.15(a) 介面位址 R.-W. Hung 2011
子網路 (Sub-net) IP 位址： 什麼是子網路 ? 子網路部分 (高階位元) 主機部分 (低階位元) IP具有相同子網路部分 4.4.2 IPv4 的定址 (Cont.) 子網路 (Sub-net) IP 位址： 子網路部分 (高階位元) 主機部分 (低階位元) 什麼是子網路 ? IP具有相同子網路部分 的裝置介面 可以在沒有路由器的狀 況下，實體地互相連結 223.1.1.1 223.1.2.1 223.1.1.2 223.1.1.4 223.1.2.9 223.1.1.3 223.1.3.27 223.1.2.2 子網路 223.1.3.1 223.1.3.2 圖4.15(b) 包含 3 個子網路的網路 R.-W. Hung 2011
子網路 (Cont.) 表示方法： 要決定子網路，將 每一個介面和它的 主機或路由器分開， 建立分離的網路。 每一個分離的網路稱為 4.4.2 IPv4 的定址 (Cont.) 子網路 (Cont.) 表示方法： 要決定子網路，將 每一個介面和它的 主機或路由器分開， 建立分離的網路。 每一個分離的網路稱為 一個子網路。 /24: 最左邊的24 bits 定義子網路的位址 223.1.1.0/24 223.1.2.0/24 223.1.3.0/24 子網路遮罩： /24 圖4.16 子網路位址 R.-W. Hung 2011
4.4.2 IPv4 的定址 (Cont.) 子網路 (Cont.) 有幾個子網路 ? 223.1.1.2 223.1.1.1 223.1.1.4 223.1.1.3 223.1.9.2 223.1.7.0 223.1.9.1 223.1.7.1 223.1.8.1 223.1.8.0 223.1.2.6 223.1.3.27 223.1.2.1 223.1.2.2 223.1.3.1 223.1.3.2 圖4.17 連接到6個子網路的三台路由器 R.-W. Hung 2011
IP 位址分配策略：CIDR CIDR：無分級跨領域路由法 (Classless InterDomain Routing) 4.4.2 IPv4 的定址 (Cont.) IP 位址分配策略：CIDR CIDR：無分級跨領域路由法 (Classless InterDomain Routing) 位址內任意長度的子網路部分 位址格式：a.b.c.d/x，其中 x 是位址的子網路部份的位元數 舊版分級法 classful addressing 8、16、24位元的A、B、C級子網路 C級子網路的網路遮罩= /8，共可容納282個IP位址 (0=net-id, broadcast=255) A、B級子網路，共可容納?個IP位址 廣播的IP位址(broadcasting) = 255.255.255.255 子網路部分 主機部分 11001000 00010111 00010000 00000000 0 00000000 is net-id 111111111 is broadcasting IP available IPs = 0 00000001 ~ 0 11111110 200.23.16.0/23 R.-W. Hung 2011
如何取得/設定主機IP 位址? 手動設定在系統管理的檔案中 4.4.2 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
DHCP (動態主機配置協定) 目標 DHCP 運作 當主機連接網際網路時，主機會從網際網路伺服器以動態方式獲得它的IP位址 4.4.2 IPv4 的定址 (Cont.) DHCP (動態主機配置協定) 目標 當主機連接網際網路時，主機會從網際網路伺服器以動態方式獲得它的IP位址 在使用時會更新它的IP位址 允許重複使用網路位址 (當連結“上”時會鎖住這個臨時網路位址) 提供使用者使用手機來連接網際網路 DHCP 運作 主機廣播 “DHCP搜尋訊息” (廣播的IP位址=255.255.255.255) DHCP 伺服器會回應 “ DHCP提供訊息” 主機請求IP位址：“DHCP請求訊息” DHCP 伺服器傳送位址：“DHCP ack” 訊息 R.-W. Hung 2011
DHCP (Cont.) DHCP 用戶端伺服端情境 223.1.2.1 A 223.1.1.1 DHCP 伺服器 4.4.2 IPv4 的定址 (Cont.) DHCP (Cont.) DHCP 用戶端伺服端情境 223.1.2.1 A 223.1.1.1 DHCP 伺服器 DHCP provides DHCP OK 223.1.1.2 新加入的 DHCP用戶端 223.1.1.4 223.1.2.9 broadcast B 223.1.2.2 223.1.1.3 223.1.3.27 E 223.1.3.1 223.1.3.2 圖4.20 DHCP用戶端伺服端的運作流程 R.-W. Hung 2011
DHCP (Cont.) DHCP 用戶端伺服端情境 (Cont.) DHCP 伺服端： 223.1.2.5 新到來的用戶端 Time 4.4.2 IPv4 的定址 (Cont.) DHCP (Cont.) DHCP 用戶端伺服端情境 (Cont.) DHCP 伺服端： 223.1.2.5 新到來的用戶端 DHCP 搜尋 (broadcasting) 來源端 ：0.0.0.0, 68 目的端 ：255.255.255.255, 67 yiaddr：0.0.0.0 處理行程：654 DHCP 提供 (broadcasting) 來源端 ：223.1.2.5, 67 目的端 ： 255.255.255.255, 68 yiaddrr：223.1.2.4 處理行程：654 生存期：3600 secs DHCP 請求(broadcasting) 來源端 ： 0.0.0.0, 68 目的端 ： 255.255.255.255, 67 yiaddrr： 223.1.2.4 處理行程：655 生存期：3600 secs DHCP ACK 來源端 ：223.1.2.5, 67 目的端 ：255.255.255.255, 68 yiaddrr：223.1.2.4 處理行程：655 生存期：3600 secs Time Time 圖4.21 DHCP用戶端伺服端的互動 R.-W. Hung 2011
NAT 網路位址轉譯 (Network Address Translation) 4.4.2 IPv4 的定址 (Cont.) NAT 網路位址轉譯 (Network Address Translation) 動機 整個區域網路對外界而言，通常只有一個 IP 位址 同一區域網路內的主機，可由router來設定其IP位址 所有區域網路內的主機送出的封包均為同一IP 位址 外界送入的封包也是同一IP位址 Router如何將外界送入的封包，正確傳送給區域網路內的主機？ NAT 192.168.0.1 區域網路的外面網路部份 區域網路 (例如，家庭網路) 192.168.0/24 192.168.0.254 192.168.0.2 138.76.29.7 router 所有離開區域網路的資料包都 具有相同的單一來源NAT IP 位址: 138.76.29.7, 不同的來源埠號 在這個網路中，來源端或 目的端傳送的資料包， 具有 192.168.0/24 的來源 及主機位址 (一般而言) 192.168.0.3 R.-W. Hung 2011
NAT (Cont.) 實作 NAT 路由器必須： 4.4.2 IPv4 的定址 (Cont.) NAT (Cont.) 實作 NAT 路由器必須： 送出資料(封)包時：更換每一個送出的資料包 (來源IP位址、埠號) 成為 (NAT IP 位址、新埠號) . . . 遠端的主機(區網外)會使用 (NAT IP 位址、新埠號) 做為目的端位址，來做回應 記憶 (在NAT 轉譯表中) 每一個 (來源端 IP 位址、埠號) 到 (NAT IP 位址、新埠號) 的轉譯對應 進入資料包時：更換每個進入資料封包目的欄位中的 (NAT IP 位址、新埠號) 為儲存在 NAT表中的對應 (來源端 IP 位址、埠號) 區域網路的外面網路部份 S=138.76.29.7, 5501 D=128.119.185.6, 80 S=192.168.0.1, 3345 D=128.119.185.6, 80 S=128.119.185.6, 80 D=138.76.29.7, 5501 S=128.119.185.6, 80 D=192.168.0.1, 3345 138.76.29.7 router 138.76.29.5, 5001 192.168.0.1, 3345 ... R.-W. Hung 2011
NAT 轉譯表 (translation table) 4.4.2 IPv4 的定址 (Cont.) NAT (Cont.) 實作 NAT 轉譯表 (translation table) WAN端 LAN端 138.76.29.7, 5001 192.168.01.1, 3345 ... ... 1： host 192.168.0.1 傳送資料(封)包到 128.119.40.186, 80 2： NAT 路由器將資料 包中的來源位址從 192.168.0.1, 3345轉成 138.76.29.7, 5001 並更新轉譯表 S： 192.168.0.1, 3345 D：128.119.40.186, 80 1 192.168.0.1 區域網路的外面網路部份 S： 128.119.40.186, 80 D：192.168.0.1, 3345 4 S： 138.76.29.7, 5001 D：128.119.40.186, 80 2 192.168.0.254 192.168.0.2 138.76.29.7 router S： 128.119.40.186, 80 D：138.76.29.7, 5001 3 4： NAT 路由器將資料包目的位址從138.76.29.7, 5001 轉成 192.168.0.1, 3345 192.168.0.3 3： 回應抵達 目的端位址： 138.76.29.7, 5001 圖4.22 NAT網路位址轉譯 R.-W. Hung 2011
NAT的穿越問題 (traversal) What ? ? 網外用戶端要連接到伺服器的 192.168.0.123位址 4.4.2 IPv4 的定址 (Cont.) NAT的穿越問題 (traversal) What ? 網外用戶端要連接到伺服器的 192.168.0.123位址 伺服器位址 192.168.0.123 區域連線到 LAN (用戶端不能使用它的目標位址) 只能有一個外部可見的NATted 位址： 138.76.29.7 192.168.0.123 用戶端 ? 192.168.0.254 138.76.29.7 NAT 路由器 R.-W. Hung 2011
NAT的穿越問題 (Cont.) How ? ? 解1： 靜態配置NAT給予埠號並請求連結向前進入到伺服器 4.4.2 IPv4 的定址 (Cont.) NAT的穿越問題 (Cont.) How ? 解1： 靜態配置NAT給予埠號並請求連結向前進入到伺服器 例如： (138.76.29.7、埠號2500) 永遠向前到 (192.168.0.123、埠號 25000) 192.168.0.123 用戶端 ? 192.168.0.254 138.76.29.7 NAT 路由器 R.-W. Hung 2011
NAT的穿越問題 (Cont.) How ? (Cont.) ? 解2：通用型隨插即用 (UPnP) 網際網路閘道裝置 (IGD) 協定 4.4.2 IPv4 的定址 (Cont.) NAT的穿越問題 (Cont.) How ? (Cont.) 解2：通用型隨插即用 (UPnP) 網際網路閘道裝置 (IGD) 協定 允許NATted 主機到： 學習公用IP位址(138.76.29.7) 列舉現有的對映埠號 增加/移除對映的埠號(租借時間) i.e.自動配置靜態NAT的對映埠號 192.168.0.123 用戶端 ? IGD 192.168.0.254 192.168.0.123, port = 3128 138.76.29.7, port = 80 138.76.29.7 具UPnP的 NAT 路由器 R.-W. Hung 2011
4.4.3 網際網路控制訊息協定(Internet Control Message Protocol, ICMP) 主機和路由器間互相交換網路層資訊的協定 錯誤回報：無法到達主機、網路、埠號、協定 回應請求/回覆 (由ping所使用) ICMP通常被視為IP的一部份 ICMP 訊息在IP封包中載送 ICMP 訊息 類型、 代碼、加上導致錯誤的 IP 資料封包的前八個位元組 圖4.23 ICMP 訊息類型 R.-W. Hung 2011
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
IPv6 第6版IP協定 動機 IPv6資料封包格式 32位元的位址空間 (IPv4) 很快就要使用殆盡了 標頭格式可以幫助處理/轉送更快速 標頭的改變可以幫助QoS (Quality of Service) IPv6資料封包格式 固定長度的40位元組標頭 不允許切割 (4.4.1節) 圖4.24 IPv6 資料包格式 R.-W. Hung 2011
從 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
從 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
第四章 導覽流程 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
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
路由和轉送的交互作用 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
抽象化圖形 (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
抽象化圖形 (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(xp1, xp) 問題：u 和 z 之間的最小成本路徑為何? 路由演算法：尋找最小成本路徑的演算法 u y x w v z 2 1 3 5 圖4.27 電腦網路的抽象化圖形模型 R.-W. Hung 2011
路由演算法的分類 整體或分散式資訊? (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
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
Dijkstra 演算法 (Cont.) // Initialization 1 S = {u}; //起始節點 u 2 for all nodes v do 3 if v adjacent to u then D(v) = c(u, v); 4 else D(v) = ; 5 Repeat 6 find w not in S such that D(w) is a minimum; 7 add w to S; 8 for all v adjacent to w and not in S do 9 update D(v) by the following: 10 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
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*) 2 1 4 2 Minimum D() x S = {u, x}; 2 x y 1 w* v x w y z D(w*) 2 1 4 2 Minimum D() v S = {u, x, v}; w* v x w y z D(w*) 2 1 3 2 4 Minimum D() w S = {u, x, v, y, w}; w* v x w y z D(w*) 2 1 3 2 4 Minimum D() y S = {u, x, v, y}; w* v x w y z D(w*) 2 1 3 2 4 Minimum D() z S = {u, x, v, y, w, z}; R.-W. Hung 2011
Dijkstra 演算法 (Cont.) 範例 (Cont.) 結果 從 u 開始的最短路徑樹： u 的轉送表： v w u z x y (u, x) 目的 連結 R.-W. Hung 2011
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
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
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
距離向量演算法 符號 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
距離向量演算法 (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
距離向量演算法 (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 0 2 7 y z 來源節點 目的節點 x y z x 0 y 2 0 1 z 7 1 0 來源節點 目的節點 x y z x 0 2 3 y 2 0 1 z 3 1 0 來源節點 目的節點 2 3 節點 y x y z x y 2 0 1 z 來源節點 目的節點 x y z x 0 2 7 y 2 0 1 z 7 1 0 來源節點 目的節點 x y z x 0 2 3 y 2 0 1 z 3 1 0 來源節點 目的節點 節點 z x y z x y z 7 1 0 來源節點 目的節點 x y z x 0 2 7 y 2 0 1 z 3 1 0 來源節點 目的節點 x y z x 0 2 3 y 2 0 1 z 3 1 0 來源節點 目的節點 R.-W. Hung 2011
距離向量演算法 (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
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
第四章 導覽流程 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
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 1 v 2 w 2 x 3 y 3 z 2 圖4.34 從來源路由器A到各個子網路的hop數(站數) R.-W. Hung 2011
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
RIP 範例 (Cont.) D 中的路由表 w A 2 目的端網路 下一個路由器 到目的端所需的轉送次數 y B 2 z B 7 目的端網路 下一個路由器 到目的端所需的轉送次數 w A 2 y B 2 z B 7 x -- 1 ... ... ... z w x y A D B C 圖4.35 RIP 範例 R.-W. Hung 2011
RIP 範例 (Cont.) D 中的路由表 w A 2 目的端網路 下一個路由器 到目的端所需的轉送次數 y B 2 z B 7 目的端網路 下一個路由器 到目的端所需的轉送次數 w A 2 y B 2 z B 7 x -- 1 ... ... ... A 5 從A到D的通告： z w x y A D B C 圖4.35 RIP 範例 R.-W. Hung 2011
第四章 導覽流程 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
4.7 廣播與群播路由 廣播路由(broadcasting) 從來源端傳送封包到所有其它的節點 廣播方式 來源端複製 網路中複製 R1 4.7 廣播與群播路由 廣播路由(broadcasting) 從來源端傳送封包到所有其它的節點 廣播方式 來源端複製 網路中複製 複製 建立/傳送 複製 R1 R1 複製 R2 R2 cycle ? 產生無止盡地broadcast storm 序號控制 reversed path forwarding (圖4.44) (p. 4-100) spanning tree broadcasting 來源端如何決定接收位址 ? R3 R4 R3 R4 來源端複製 網路中複製 圖4.43 來源端複製與網路中複製 R.-W. Hung 2011
4.7.1 擴張樹廣播 (spanning tree broadcasting) 節點沿著擴張樹轉送複本 A B G D E C F (a) 從A點開始廣播 (b) 從D點開始廣播 圖4.45 沿著擴張樹進行廣播 R.-W. Hung 2011
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
群播 What ? 群播路由的目標：找到一棵樹 (或是多棵樹) 將地區群播群組成員的路由器連結起來 將資料封包傳送到特定群組的節點(路由器) 4.7.2 群播 (multicasting) 群播 What ? 將資料封包傳送到特定群組的節點(路由器) 群播路由的目標：找到一棵樹 (或是多棵樹) 將地區群播群組成員的路由器連結起來 樹：不會使用到路由器間的所有路徑 以來源端為基礎：從每個來源端到接收端是一個不同的樹 分享樹：所有的群組成員都使用相同的樹 以來源為基礎的樹 分享樹 R.-W. Hung 2011
建立群播樹的方法 使用來源為基礎的樹：一棵樹一個來源端 群組分享樹：群組只使用一棵樹 最短路徑樹 反向路徑傳送 最小擴張 (Steiner) 4.7.2 群播 (Cont.) 建立群播樹的方法 使用來源為基礎的樹：一棵樹一個來源端 最短路徑樹 反向路徑傳送 群組分享樹：群組只使用一棵樹 最小擴張 (Steiner) 以中心為基礎的樹 R.-W. Hung 2011
建立群播樹的方法 (Cont.) 最短路徑樹： 群播轉送樹：從來源端到所有接收端的最短路徑路由所產生的樹 Dijkstra 演算法 說明 R1 2 R4 1 擁有附加群組成員的路由器 沒有附加群組成員的路由器 R2 5 3 4 用來轉送的連結 i 表示演算法將連結加入的順序 i R5 6 R3 R6 R7 R.-W. Hung 2011
建立群播樹的方法 (Cont.) 分享樹：Steiner 樹 Steiner 樹：最小成本樹、連接全部擁有群組成員的路由器 為NP完全問題 極佳的試探存在 實際不使用： 計算複雜度 需要整個網路的資訊 龐大的：每當有路由器加入/離開時需要重新執行 R.-W. Hung 2011
建立群播樹的方法 (Cont.) 以中心為基礎的樹 大家一起分享的單一傳遞樹 (ref. 圖4.46) 在樹中有一個路由器被標記為“中心” 加入： 邊緣路由器傳送單點傳播的加入訊息給中心路由器 加入訊息由中間的路由器「處理」並轉送到中心 加入訊息會觸碰到此中心現存樹的分枝、或是抵達中心 加入訊息所使用的路徑會變成這個路由器所使用的樹的分枝 假設我們選擇 R6 做為中心： 說明 R1 R4 擁有附加群組成員的路由器 3 沒有附加群組成員的路由器 R2 1 2 加入訊息所產生的路徑順序 R5 R3 1 R6 R7 R.-W. Hung 2011
End of Chapter 4 R.-W. Hung 2011