網路層通訊協定 Network Layer Protocol

網路層通訊協定 Network Layer Protocol

第四章 : 網路層 4. 1 Introduction 4.2 Virtual circuit and datagram networks 4.3 What s inside a router 4.4 IP: Internet Protocol Datagram format IPv4 addressing ICMP IPv6 4.5 Routing algorithms Link state Distance Vector Hierarchical routing 4.6 Routing in the Internet RIP OSPF BGP 4.7 Broadcast and multicast routing 4-2 Network Layer

The OSI Reference Model 7 Application Application Protocol Application APDU 6 Presentation Presentation Protocol Presentation PPDU 5 Session Session Protocol Session SPDU 4 3 Transport Network Transport Protocol Internal Subnet Protocol Network Network Transport Network TPDU Packet 2 Data Link Data Link Data Link Data Link Frame 1 Physical Physical Physical Physical Bit Layer Host A Router Router Host B 4-3

Network Layer 在傳送端將 segments 包裝成 datagrams E2E Network Layer Data Link Layer 路由器會檢查所有經過它的 IP datagrams 標頭 (header) 在接收端將 segments 往上送給傳輸層 E2E Network Layer Data Link Layer Physical Layer Physical Layer Host A Router Router Host B 將 segment 由傳送端送到接收端 4-4

Example application transport network data link physical network data link physical network data link physical network data link physical network data link physical network data link physical network data link physical network data link physical network data link physical application transport network data link physical 4-5 Network Layer

Two important functions Forwarding 將路由器輸入端的封包移送到適當的路由器輸出端 Routing 決定封包從來源端到目的地端所經過的路由路徑. routing algorithms 4-6 Network Layer

Forwarding & Routing routing algorithm 計算傳輸路徑的演算法 local forwarding table header value output link 0100 0101 0111 1001 3 2 2 1 value in arriving packet s header 0111 1 3 2 4-7 Network Layer

Example From 高雄大學 To 家樂福 Routing 高雄大學路 藍田路 大學南路 大學東路 Forwarding 第一個路口左轉 過兩個紅綠燈後下一個路口右轉 4-8 Network Layer

Service Model 描述傳送端與接收端之間資料傳輸的特性 對單一 datagram 保證送到 (guaranteed delivery) Eq:DHL 保證在 40 msec 內送到 Eq: 限時掛號 對一串 datagram 的流量 依序的 datagram 傳遞, 保證流量的最小頻寬封包間傳送間隔變化量的限制 4-9 Network Layer

連線導向與非連線導向服務 VC Network 連線導向服務 Datagram Network 非連線導向服務 4-10 Network Layer

Virtual Circuit Network 每個封包都包含 VC identifier 而不是目的地位址 (Destination) Host A Application Transport Network Data Link Physical 5. Data flow begins 6. Receive data 4. Call connected 3. Accept call 1. Initiate call 2. incoming call Host B Application Transport Network Data Link Physical

Virtual Circuit Example 1 3 12 2 22 Interface Number VC Number Incoming interface Incoming VC # Outgoing interface Outgoing VC # 1 12 3 22 2 63 1 18 3 7 2 87 1 97 3 77 Routers maintain connection state information!

Datagram Network 每個封包傳送時都含有目的端的位址 (address), 不需要先行建立 path,router 查詢 routing table 決定出口埠 Routing table 可以動態改變 同一個資料流 (flow) 的封包不一定會依照相同路徑傳送 同一個資料流的封包不一定依照傳送順序到達 Application Transport Network Data Link Physical Host A 1. Send data 2. Receive data Application Transport Network Data Link Physical Host B

Datagram V.S. VC network Internet (datagram) 電腦間的資料交換 elastic( 有彈性 ) 服務, 沒有嚴格時序要求. smart( 智慧型 ) end systems (computers) 可以調整, 執行控制, 錯誤恢復 simple inside network, complexity at edge 有許多網路連線型態 有不同的特性 不易提供單一服務 ATM (VC) evolved from telephony human conversation: strict timing, reliability requirements need for guaranteed service dumb end systems telephones complexity inside network 4-14 Network Layer

Network Layer Protocols Transport layer: TCP, UDP Network layer Routing protocols path selection RIP, OSPF, BGP routing table IP protocol addressing conventions datagram format packet handling conventions ICMP protocol error reporting router signaling Link layer physical layer

Routing Algorithm Algorithm that finds least-cost path Good Path: 一般是指 cost 累加最小的路徑, 但是也有可能因為實際需求的不同而有不同的定義 如圖 : A, B, C, D, E, F 為 Router, 由實體連線互相連結 每條實體連線都會因為傳輸延遲 壅塞的情況賦予一個 cost 值 A 1 2 5 B D 2 3 1 3 C E 1 5 2 F

Routing Algorithm classification Global or decentralized information? Global: 所有路由器需要完整網路連線圖與路由器間的連線成本資訊 link state algorithms Decentralized: 路由器只需知道實體連線的鄰近路由器及與鄰近路由器的連線成本資訊 需要重複地與鄰近路由器計算連線成本與資訊交換 distance vector algorithms Static or dynamic? Static: routes change slowly over time Dynamic: routes change more quickly periodic update in response to link cost changes 4-17 Network Layer

Link-State Algorithm (Global) Link-State Algorithm 的特色 : 每個 router 都擁有相同且完整網路拓樸及 cost 的資訊 Example: Dijkstra s Algorithm( 迪傑斯特拉 ) 初始條件 : 以本身為起始點, 設定相鄰的節點的 cost 值, 無直接連結的節點 cost 設定為無限大 替換條件 : 選擇最小 cost 的節點作為下一個起始點, 不斷更新 ( 比原來 cost 小 ) 鄰近的節點所具有的 cost 值 終結條件 : 執行替換條件到鄰近的節點所具有的 cost 值都不需要在更新時, 計算完成

Dijkstra s Algorithm Notation: C(i,j) 節點 i 到節點 j 的 cost, 若 i, j 不相鄰, 此值為無限大 D(v) 目前從起始點到 v 的最少 cost( 可能會被更新 ) p(v) N 從起始點到 v 的前一個點 (predecessor node) 已經確定與起始點最短路徑的所有點所成的集合 (set)

Dijkstra s Algorithm :Example Step 0 1 2 3 4 5 start N A AD ADE ADEB ADEBC ADEBCF D(B),p(B) 2,A 2,A 2,A D(C),p(C) 5,A 4,D 3,E 3,E D(D),p(D) 1,A D(E),p(E) infinity 2,D D(F),p(F) infinity infinity 4,E 4,E 4,E A E D C B F 2 2 1 3 1 1 2 5 3 5

Dijkstra s Algorithm: Example Resulting shortest-path tree from A: Resulting forwarding table in A: destination link A B C F B D E (A,B) (A,D) (A,D) D E C F (A,D) (A,D) 4-21 Network Layer

Distance Vector Algorithm Distance Vector Algorithm 的特色 : 反覆交換訊息 (iterative) 非對稱性 (asynchronous) 分散式 (distributed) Router 只需要知道最佳路徑的 next hop 即可傳送 Distance table 是用來計算 route 的主要資料結構 Table 中的每個 element 的定義如下 : X D (Y,Z) = = distance from X to Y, via Z as next hop Z c(x,z) + min {D (Y,w)} w

Distance Vector Algorithm: Distance Table A 1 7 E D (C,D) E D (A,D) E D (A,B) B E 8 1 2 C D D = c(e,d) + min {D (C,w)} w = 2+2 = 4 D = c(e,d) + min {D (A,w)} w = 2+3 = 5 2 loop! = c(e,b) + min {D (A,w)} w = 8+6 = 14 B E D () A B C D cost to destination via A 1 7 6 4 B 14 8 9 11 D Bellman-Ford Equation (dynamic programming) 5 5 4 2

Bellman-Ford example u 1 2 5 v x 2 3 1 3 w y 1 5 2 z Clearly, d v (z) = 5, d x (z) = 3, d w (z) = 3 B-F equation : d u (z) = min { c(u,v) + d v (z), c(u,x) + d x (z), c(u,w) + d w (z) } = min {2 + 5, 1 + 3, 5 + 3} = 4 Node that achieves minimum is next hop in shortest path forwarding table 4-24 Network Layer

Distance Vector Algorithm X 2 Y 7 1 Z X D (Y,Z) = c(x,z) + min {D (Y,w)} = 7+1 = 8 w Z X D (Z,Y) = c(x,y) + min {D (Z,w)} = 2+1 = 3 w Y

Distance Vector Algorithm X 2 Y 7 1 Z

Distance Vector: link cost changes Y 偵測到與 X 的連線 cost 減少 (Good news travel fast) Y 修改自己的 distance table 如果這條路徑在 least cost 上, 必須通知鄰近的 router 1 4 Y 1 algorithm terminates X 50 Z

Distance Vector: link cost changes Y 偵測到與 X 的連線 cost 增加 bad news travels slow: 防止 count to infinity 60 algorithm Y continues 4 1 on! X 50 Z

Distance Vector: Poison reverse Z 經過 Y 到達 X, 通知 Y 經過 Z 到達 X 的 cost 為無限大 ( 本身的 distance table 仍要紀錄真實的值 ) 當 X, Y 之間連線的 cost 值變大,Z 就不會再透過 Y 連到 X, 而是直接連結 此時 Z 告知 Y 到達 X 的 cost 為 50 可以避免 count to infinity algorithm terminates 60 X 4 Y 50 1 Z

Routing in the Internet Internet 由數個 AS (Autonomous System) 互相連結所組成 Eq: 高大 (AS), 中山 (AS) 考慮 AS 的 routing: Intra AS: 管理者可以自由選擇在所屬 AS 內的 Routing Protocol Inter AS: 必須與外界跑相同的 Routing Protocol

Internet AS Hierarchy Intra-AS 圖資 Inter-AS 工學院 高大 中山 國高

Intra-AS Routing IGP: Interior Gateway Protocols 一般常見的 IGP: RIP: Routing Information Protocol. OSPF: Open Shortest Path First. IGRP: Interior Gateway Routing Protocol (Cisco proprietary)

RIP (Routing Information Protocol) 採用 Distance Vector Algorithm RFC 1058(version 1), RFC 1723(version 2) 所紀錄的路徑長度最多通過 15 個 hop 透過每三十秒傳送的 RIP response message 與相鄰的 router 交換 routing table, 也稱作 RIP advertisement 每次利用 RIP advertisement 交換 routing table 最多可包含 25 個 destination network.

RIP (Routing Information Protocol) z w x y A D B C Destination Network Next Router Num. of hops to dest. w A 2 y B 2 z B 7 x -- 1..... Routing table in D

RIP Table 的範例 Destination Gateway Flags Ref Use Interface -------------------- -------------------- ----- ----- ------ --------- 127.0.0.1 127.0.0.1 UH 0 26492 lo0 192.168.2. 192.168.2.5 U 2 13 fa0 193.55.114. 193.55.114.6 U 3 58503 le0 192.168.3. 192.168.3.5 U 2 25 qaa0 224.0.0.0 193.55.114.6 U 3 0 le0 default 193.55.114.129 UG 0 143454 第一行為 Loop-Back 具有三個介面 192.168.2.5 193.55.114.6 192.168.3.5 第五行為 IP multicast 最後一行表示在表中查詢不到的 IP 就送往 193.55.114.129

RIP 處理連結 (Link) 變化的方式 如果超過 180 秒沒有聽到定期的廣播, 則 RIP 就會認為此條路徑已經不復存在 ( 與 Neighbor 斷線 ) 經過這個 neighbor 的路徑已經不在 傳送新的 advertisement 給其他 neighbor 如果 neighbor 的 routing table 有所更動, 就會再度傳送出去 可以透過這種方式將連結變化傳送到整個網路 設定 Max Hop=15 的目的是避免 Count-To-Infinity

OSPF (Open Shortest Path First) OSPF: RFC 2178 (Version 2) OSPF 是一種 Link-State Algorithm, 每個 router 都知道整個 AS 的拓樸 (Topology) 狀況 Flooding: 每個 router 必須要將本身與哪些 neighbor 相鄰的訊息傳送到整個 AS Security: 所有 router 間交換的訊息需要被認可 (authenticated), 防止錯誤的訊息影響到正常的 routing table Multiple same-cost paths: 到達某目的地可能有多重路徑 ( 相同 cost) 可以選擇

OSPF (Open Shortest Path First) 可以依照 IP Header 中不同的 TOS 計算出不同的路徑 Multicast OSPF (MOSPF, RFC 1584): 利用原有的 OSPF 資料再加上新的 link-state advertisement Hierarchical OSPF: 分成兩層 :Local area, backbone Area border routers: 收集本身所在 area 內的資訊, 並告知其他 Area border routers Backbone routers: 採用 OSPF, 僅收集 backbone 的資訊 Boundary routers: 連結其他 AS 的 router

Hierarchical OSPF

IGRP (Interior Gateway Routing Protocol) EIGRP (Enhanced Interior Gateway Routing Protocol): 一種改進 RIP 的 Distance Vector Algorithm 計算 path cost 時不僅以 hop 數為 cost, 也考量 : 延遲 (Delay) 頻寬 (Bandwidth) 可靠度 (Reliability) 負載 (load)

Inter-AS routing

Internet inter-as routing: BGP BGP: Border Gateway Protocol. Path Vector Protocol: 與 Distance Vector 相似 Mechanism: router 告知 neighbor 通往某個目的地的 path (sequence of ASs) Policy: 管理者決定是否將這個 path 加入 routing table Ex:Gateway X 告知 neighbor 從 X 到達 Z 的路徑如下 : Path (X,Z) = X, Y1, Y2, Y3,,Z

Internet inter-as routing: BGP 考慮 X 將到 Z 的 path 告知 W 的各種情況 : W 可能因為下列原因不採用 X 所提供的路徑 : Cost 較高 不欲通過競爭性的 AS 避免產生 Loop 如果 W 採用了 X 所提供的路徑 : Path (W,Z) = W, Path (X,Z) X 本身也可以透過控制 advertisement 的方式做出一些管理的決策 : X 不希望別的封包透過 X 到達 Z 不廣播有關於 Z 的 Path

Internet inter-as routing: BGP BGP 的透過 TCP 作訊息交換 BGP message 的種類 : OPEN: 與對方建立 TCP 連線並且確認 Sender UPDATE: 廣播新的 path, 或是取消舊的 path KEEPALIVE: 目的是維持 TCP 連線 ( 可能一段時間沒有 UPDATE 訊息 ), 也用來產生 OPEN 的 ACKs NOTIFICATION: 回報上述的訊息所產生的錯誤或是關閉連線

Intra- 與 Inter-AS routing 的不同 Policy: Inter-AS: AS 的管理者需要 Policy 來控制是否讓其他 AS 的封包通過 Intra-AS: 單一管理者 Scale: 利用 Hierarchy 的方式可以減少 routing table 的大小, 也減少 update 的流量 Performance: Intra-AS: 在乎 performance Inter-AS: policy 的重要性勝於 performance 的重要性

Router Architecture Router 的主要兩個功能 : 與其他 router 溝通 (routing protocol) 交換封包到適當的出口 (outgoing link)

Input Port Physical layer: bit-level reception Data link layer: e.g., Ethernet Decentralized Switching 依照封包的 dest 欄位決定要往哪個 output port 傳送 當封包流入的速度比處理的速度快, 就儲存在 queue 中等待處理

Input Port Queuing 當封包流入的總和比交換 switch 的速度快 封包會被儲存在 input queue 等待交換 Head-of-the-Line (HOL) blocking: 在等待交換的封包影響後來的封包進行交換 (queue 的特性 )

Output Ports 當封包處理的速率大於 output port 的傳輸速率時, 必須將封包儲存在 output buffer 中 Scheduling discipline: 從 queue 中選擇封包傳送

Output port queuing 當封包進入 output buffer 的速率大於 link 傳輸的速率時 Output buffer overflow 會造成封包遺失

IP addressing IP address: 由 32bits 所組成, 用來辨識在網際網路上主機 (Host) 或介面 (Interface) 的數值 Router 上通常有多個介面, 一個主機上也允許有多個介面, 每個介面具有各自的 IP address 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.1 223.1.2.2 223.1.3.27 LAN 223.1.3.2 223.1.1.1 = 11011111 00000001 00000001 00000001 223 1 1 1

IP addressing IP address 由兩個部分組成 : Network part: 較高位 (High order part) 的位元用來辨識網域 Host Part (Interface part): 較低位 (Low order part) 的位元用來辨識主機 何謂一個網域 (Network)? IP address 具有相同高位位元 (Network Part) 的介面所成的統稱 這些介面彼此互相連接而不透過 router (Layer-3 Device)

IP addressing 如何取得一個 IP? 經過人工設定, 將 IP 位址寫入設定檔中 Dynamic Host Configuration Protocol (DHCP): 啟動後與鄰近的 DHCP 伺服器取得 IP 利用 DHCP 取得 IP 的步驟 : 客戶端廣播 (broadcast) DHCP Discovery 的訊息 DHCP 伺服器用 DHCP Offer 訊息告知客戶端有伺服器存在 客戶端送出 DHCP Request 的訊息要求取得 IP DHCP 伺服器送回 DHCP Ack 的訊息夾帶派發的 IP 位址

DHCP client-server scenario A 223.1.1.1 DHCP server 223.1.2.1 B 223.1.1.2 223.1.1.4 223.1.2.9 223.1.2.2 223.1.1.3 223.1.3.27 223.1.3.1 223.1.3.2 E arriving DHCP client needs address in this network 4-54 Network Layer

DHCP 用戶端 - 伺服端情境 DHCP 伺服端 : 223.1.2.5 DHCP 搜尋 新到來的用戶端 來源端 : 0.0.0.0,68 目的端 :255.255.255.255, 67 yiaddr: 0.0.0.0 處理行程 : 654 時間 DHCP 請求 DHCP 提供 來源端 : 0.0.0.0, 68 目的端 : 255.255.255.255, 67 yiaddrr: 223.1.2.4 處理行程 : 655 生存期 : 3600 secs 來源端 : 223.1.2.5, 67 目的端 : 255.255.255.255, 68 yiaddrr: 223.1.2.4 處理行程 : 654 生存期 : 3600 secs yiaddr: 你的網際網路位址將要分配給新出現的用戶端的位址 4-55 DHCP ACK 來源端 : 223.1.2.5, 67 目的端 : 255.255.255.255, 68 yiaddrr: 223.1.2.4 處理行程 : 655 生存期 : 3600 secs 網路層和路由法