# 第07講 Internetworking
計算機網路概論 黃能富教授

## Introduction
1. Internetwork -> 提供**host-to-host** 的封包傳輸服務
2. 甚麼是IP?
* 代表 **Internet Protocol**
* all nodes都需要可以運作Internet Protocol

### IP Service Model
* Packet Delivery Model
1. **Connectionless model** (無連線模式)來傳遞資料
2. **Best-effort delivery** (不可靠服務)
* 封包可能遺失、順序不對、重複傳遞、Delay很久

### How Layer 3 Routers Work
* 運用**store and forward** 的方式來轉送收到的IP packets (datagrams)
1. **IP Address Lookup(Forwarding Table)**
* Forwarding Table是透過routing protocol建立
2. **IP/MAC mapping table**
* store and forward的運作過程:
1. 先將封包存起來，並將destination IP取出
2. 拿destination IP到Forwarding Table查表，看是Directly還是透過Router間接連接
* Directly -> 到IP/MAC mapping table找到destination的MAC
* 透過Router間接連接 -> 到IP/MAC mapping table找到Router的MAC
* **若IP不在Forwarding Table中**，則將此IP forward 到 **default port**
* **不具Plug-and-Play的特色**(layer 2設備大部分為Plug-and-Play)

## IP
### IP Datagram Header Format
* IPv4中，Source IP Address 和 Destination IP Address 均為 32 bits
* Identification(ID)：
-> 在Fragmentation之後，要將所有的Fragment組合起來時，ID相同代表其隸屬於同個datagram
* Fragment Offset：
-> 在用ID判斷完後，需透過Fragment Offset來知道Fragment應該位於datagram的位置
* Protocol：紀錄上一層的Protocol
* Time to Live：封包在Internet存活的時間，避免封包持續待在Internet中
* Header Checksum：把Header的內容做成一個檢查碼

---
* Example - 將封包進行Fragmentation
* MF=1且offset=0，代表此封包為Fragment中的第一個
* offset為64，是因為前面的為512 bytes => 512/8=64

### Type of Service (ToS) of IP
* Precedence：表示封包的重要性
* 當Router要將封包丟棄時，可透過Delay、Throughput、Reliability來判斷，要先丟棄哪個封包
* 當datagram執行Fragmentation後，可以用**MF** 來判斷是否為此datagram中的最後一個Fragment
* 0 -> 只有最後一個Fragment的MF設為0，其餘Fragment的MF設為1

### IP Addresses
* 特性
1. 具全唯一性的32 bits address
2. Hierarchical結構：network + host
3. Class A type (1/2)
-> 網路數量不多，只有2^7^個，但Host(IP位置)可以有2^24^個
4. Class B type (1/4)
5. Class C type (1/8)
-> 網路數量很多，有2^21^個，但Host(IP)位置只有2^8^個
* “點” (dot) 標記法 => 8個bits一個dot

## Router
* Example：B -> Y (**Intra LAN -> 在同LAN**)
* 因為B和Y在同個LAN上，所以不經過Router，因此他們的frame如下圖
* IP(B) -> source IP
* IP(Y) -> destination IP
* MAC(B) -> source MAC
* MAC(Y) -> destination MAC

---
* Example：B -> A (**Inter-LAN -> 在不同LAN**)
* 因為B和Y不在同個網路上，所以需經過Router，因此用到MAC(R)
* IP(B) -> source IP
* IP(A) -> destination IP
* MAC(B) -> source MAC
* MAC(R) -> destination MAC
* 當封包送到Router後，透過IP(A)查Forwarding Table得知此傳輸方法是就由Directly，因此須知道A的MAC
* 接著透過IP(A)查IP/MAC mapping table找到A的MAC後，就可以直接傳送給A
* IP(B) -> source IP
* IP(A) -> destination IP
* MAC(R) -> source MAC
* MAC(A) -> destination MAC

### An Internet Routing Example
* 此為G的Routing Table
* 因為 20.0.0.0 和 30.0.0.0 皆與G相連，故為 Deliver Direct
* **Router因為平常就會根據Routing Protocol與其他Router交換情報** ，所以得知 10.0.0.0 需要透過F的 20.0.0.5 來傳輸和得知 40.0.0.0需要透過H的 30.0.0.7 來傳輸
* Router還須建立一個IP與MAC的對照表

IP Datagram Forwarding
---
* 策略
1. 每個封包皆含有**destination address**
2. 是否相連?
* **directly connected**
-> 直接發送給目的地Host
* **not directly connected**
-> 發送給某一個Router繼續轉送
3. **每個host皆需要有default router**
4. Router須維持forwarding table

IP Fragmentation and Reassembly
---
* **MTU (Maximum Transmission Unit)**
* 若MTU < datagram，則需Fragmentation
* Receiver負責將Fragmentation後的Fragment重新組裝

Router特色
---
1. Network Layer Routing
* Filter(過濾) MAC broadcast and multicast packets
* 支持不同的傳輸媒介
* 封包的fragmentation and reassembly
2. Routing Protocol
* 決定Routing table
* Dynamic routing protocol
* RIP：Routing Information Protocol
* OSPF：Open Shortest Path First
* reliability
* 偵錯功能

橋接器與路由器的差異
---

IP Subnetting
---
* subnet masks => 規範子網路的大小
* 若後面8個bit為10000000 -> subnet大小為2^7^，此時最多有128 個hosts
* 若後面8個bit為11000000 -> subnet大小為2^6^，此時最多有64個hosts

---
* Forwarding Algorithm
* Example

Classless Addressing
---
* Classless Inter-Domain Routing(CIDR)
-> 處理有關規模問題的一種技術
* 使用**aggregate routes** (累積路由)，來減少 routing table size
* 因為當在同個網段時，這些IP Address會有**common prefix** (20個bits相同)，所以可以透過“/X”來代表common prefix有幾個bits -> X代表prefix長度

* Classless Addressing的問題
-> prefixes可能會發生重疊，則用**longest prefix match** 解決
* 例如：171.69 (16 bit prefix)、171.69.10(24 bit prefix)，而現在有封包IP Address為171.69.10.5
* 因為prefix皆為171.69，所以無法判斷，故採用longest prefix match，因此在這個例子中會選擇171.69.10

Address Resolution Protocol (ARP)
---
將IP addresses Map到一個physical (MAC) addresses
* 使用一個IP addresses 和 MAC addresses的table
* 若IP addresses不在table中，則用broadcast方式詢問，當target machine收到請求後，回覆其MAC addresses

Dynamic Host Configuration Protocol (DHCP)
---
可以**自動設定** IP information，因為人工設定較耗時
* DHCP server：
1. 需要提供**configuration information** (設置資訊)給主機
2. 器維護並管理可用的 IP 位址
* Example：
* 當電腦剛開機時，電腦會用**Broadcast** 傳送**DHCP DISCOVER** 封包到一個特別的IP address (**255.255.255.255**)
* 當DHCP relay收到DHCP DISCOVER封包後，會轉由**Unicast** 方式傳送給DHCP server，而DHCP server收到封包後，會回傳configuration information給電腦
* DHCP可使IP設定便方便

Internet Control Message Protocol (ICMP)
---
因為各種原因導致封包無法送達或被丟棄，而ICMP會告知Sender傳送的封包發生error
* 封包無法送達原因：
1. link /node故障
2. Reassembly失敗
3. Time To Live(TTL) 變成0
4. IP header checksum發現錯誤
* **ICMP-Redirect** -> 可能可以使封包走更好的路徑

Forwarding v.s Routing
---
* **Forwarding 和 Routing 的比較**
1. Forwarding
-> 根據destination address和routing table**選擇由哪個port傳輸**
2. Routing
-> **建立routing table**
* **Forwarding table 和 Routing table 的比較**
1. Forwarding table
* 用於封包傳輸
* network number與**outgoing interface** 對應關係，且含有一些MAC 資訊
2. Routing table
* 透過Routing protocols建立
* 內含network numbers與**next Hop** 對應關係

Routing protocols
---
1. 預先計算 all shortest paths 並載入所有node -> static approach
* static方法的問題
1. 當有node或link故障時會出錯
2. 無法動態新增或刪減node
3. **edge costs** 無法改變
* 解決static approach問題的方法
=> 使用**dynamic protocol** 且每個router自己算(**distributed**)
* 以下為兩種dynamic protocol：
1. **Distance Vector**
2. **Link State**

## Distance Vector
1. 建立一個**dimensional array (vector)** 來儲存與其他節點的距離(cost)，並將此Distance Vector與相鄰點分享
* Example：
* 假設每個邊cost皆為1，若無邊相連則為無限大
1. 此時A點的Distance Vector為下圖
2. 經過相鄰點的交換與找出各點的shortest paths之後，就變成下圖
2. Distance Vector問題：
1. 網路好(好消息) -> 訊息傳得快
2. 網路差 (壞消息)-> 訊息傳得慢

### Count-to-infinity problem
* Example：
1. 若A、E之間斷線，此時A會告知相鄰的node(F、B、C)與E的距離改為無限大
2. 但因為C有紀錄到E的路徑為2，並告知給B，導致B認為可以透過C到E，而且cost為2
3. 接著B又告知A到E的路徑為3，導致A認為可以透過B到E，而且cost為3
4. 接著A又告知C到E的路徑為4，導致C認為可以透過A到E，而且cost為4
5,6,7....會一直無限循環，而此問題即為Count-to-infinity problem
* 通常要經過**16個hops** 才會被制止
* 解決Count-to-infinity problem方法 => **split horizon**
* **split horizon**
-> 當一個node發送一個更新訊息給他的鄰居時，他不會將從某個鄰居學習到的資訊，重複回傳給該鄰居，這樣可以解決產生Loop的問題

Link State protocol
---
* 方法：把與他直接相連的link告訴所有node，且透過**Link State Packet (LSP)** 傳送
* LSP包含：
1. LSP的ID
2. SEQNO(序號)
3. TTL(Time To Leave) 值
4. Link的cost
* 如何做到**Reliable Flooding** (可靠的廣播)
* 儲存最新的 LSP，並增加此LSP的SEQNO後，將 LSP 轉送給其他節點
* 當系統重啟動時, SEQNO 會歸零

Shortest Path Routing
---
* **OSPF** (Open Shortest Path First)
* 此方法採用**Link State protocol**
* 運用**Dijkstra’s algorithm** 來找Shortest Path