# 計算機網路

## 1.Introduction
#### 1.1 What's The Internet：
* Routers 路由器：有路由、轉送兩種功能。
* 路由: 可以決定封包( host to host ) 路徑
* 轉送: 將封包由輸入端移送至適當的輸出端
* Protocal：傳送、接收封包訊息所要遵守的協議。
* Internet Standard:
* RFC(徵求意見稿)
* IETF(網際網路工程任務組)。
* Internet Service Provider(**ISP**)：
* 網際網路服務提供者
* 提供撥號連線、ADSL、數據專線、光纖或行動網路等服務。
#### 1.2 Network edge 邊緣網路
* 由主機 (host) 和應用 (application) 組成
* `Client Server Model`
* 需要server一直把主機打開提供服務
* 如果server被攻擊會有reliability的問題
* 此外server能提供的服務有資源上限
* `Peer to Peer Model`
* 不需要server，每個節點都可以提供服務
* 但是沒有一個控管中心，有時會被自私的使用者 block 住
#### 1.3 Network core核心網路
* 由路由器(router)組成，將網路連結起來
* `Circuit-Switching`
* 事先 set up 一個專屬 的 call ，佔據起點到終點中的所要用到的資源
* 依照資源(頻寬)的切割，分成兩種
* `Frequency division Multiplexing(FDM)`：同時給多使用者使用，每使用者使用 1/n
* `Time division Multiplexing(TDM)`：每個使用者輪流使用，輪到時使用所有頻寬
* 特性
* 傳遞資料比較穩定
* 能建立的 call 有上限
* `Packet-Switching`
* 把資料切割成封包，資源只有在用到的時候才會被使用
* 當封包過多時，可能會發生 overflow 掉封包
* `statistical multiplexing`
* 不同 host 各自把資料切割成封包送出，可能交錯或順序不同
* router 負責處理封包
* `Store and Forward`
* 每個 router 會先等收到完整的 packet 之後，才往下一個節點傳遞
* 如果 packet 比頻寬還大的話，每個 router 都會 delay
* 特性
* 通常可以讓更多使用者使用網路服務
* 可能會有excessive congestion 造成 delay 或是 loss
* Network Structure
* ISP 呈現 hierachy 分布
* 可以分成 Tier 1, 2, 3 三層
#### 1.4 Delay, loss and throughput in packet-switched
* 四種 packet delay 的原因
* 1.Nodal Processing: check 有無 error 並決定output link
* 2.Queueing: 等待被 output link 傳遞出去
* 3.Transmission Delay: 傳遞所花時間，資料長度L/頻寬R
* 4.Propagation Delay: 線路傳遞所花時間，距離d/介質速率s
* **traffic intensity La/R**
* a 平均一秒來幾個封包
* L/R 平均一個封包要處理幾秒
* 當La/R<1時，路由器可以正常運作
* 當La/R>1時，路由器會永遠塞在 queue 中來不及處理
* **Traceroute program**
* 每個封包會有`存活時間（TTL）`
* 每經過一個路由器，TTL 就會減1
* 當 TTL 為 0 時，路由器會傳送一個 ICMP TTL 封包給發出者
* 依序發出 TTL = 1 , 2 , ... 的封包，分析經過路徑及 Delay
* Throughput
* 單位時間可以傳多少bit
* 兩個端點間的 end-end throughput 等於 min(Rc, Rs, R/n)
* 其中 Rc 表示client端throughput
* 其中 Rs 表示server端throughput
* 其中 R 表示網路中間提供throughput，假設有 n 人共用
* 通常 bottleneck 會是 Rc 或是 Rs

#### 1.5 Protocol layers, service models
* 五層架構
* 應用層application
* 傳輸層transport：不同 process 間的資料傳輸
* 網路層network：路由
* 連結層link：相鄰的網路裝置傳送資料
* 實體層physical：實體線路傳送資料
* OSI 七層模型(由ISO 提出)
* 表達層(Presentation Layer)：解釋資料的方法
* encryption, compression
* 會議層(Session Layer)：確認資料在不同 host 的一致性
* synchronization, checkpoint, recovery
* 實務上不用這個模型，這兩層可以被包含在五層架構中
* Encapsulation封裝
* 封包會在每一層進行封裝，記錄一些該層所處理的訊息，把這些訊息加入封包的開頭為header。
#### 1.6 Networks under attack: security
* 網路原本的設計為讓使用者互相建立連線，並沒有考慮到security的問題
* 惡應程式種類
* Trojan horse: 透過無害的應用程式進入，帶有隱藏自身和惡意行為的程式碼
* Virus: 會自我複製、可以快速蔓延的程式
* Worm: 一個自行運作的程式，不用使用者介入操作也能自我複製或執行，可能會執行垃圾程式碼以發動分散式阻斷服務攻擊
* 攻擊形式
* Denial of service (DoS): 透過不斷向某伺服器傳送垃圾資訊，使其癱瘓
* Packet sniffing：偷聽封包
* IP spoofing：製造假的封包，假冒使用者的身分傳訊息給其他人
* record-and-playback：偷聽重要的訊息(如password)，然後記錄下來做攻擊
#### 1.7 History
* 1961-1972: 提出 packet-switching ，認為其效能不錯
* 1972-1980: 建立 `Cerf and Kahn’s internetworking` 原則，奠定基礎
* 1980-1990: 出現 TCP/IP, FTP 等 protocol
* 1990, 2000: 開始商業化，慢慢發展成巨大模式
* 2007: 朝向wireless, mobility發展
## 2.Application Layer
#### HTTP 超文本傳輸協定
- Hypertext transfer protocol 超文本傳輸協定
* 使用 TCP 連線
* 預設 port 為 80
* stateless
* 用 ASCII 來encode，分成 request 和 response 兩種
* 分成 GET, POST, HEAD 三種方法
- Nonpersistent HTTP：
* 每一個 object，server 要幫他建立一個TCP連線
* **Response Time = 2\*`RTT`+transmission time**
* 瀏覽器也可以透過平行建立 TCP connection 降低 response time
* HTTP 1.0
* Persistent HTTP：
* 一個 TCP 連線可以傳送多個 objects
* 建立連線要花一個 RTT，之後只要接近一個 RTT 就能傳送所有的object
* 可能會被 DDOS 攻擊
* HTTP 1.1
* `Cookies 餅乾`
* 提供 state 的方法
* 第一次連進 server 時，server response 包含一個 cookie ID
* Client 端第二次之後的 request，再前面加入cookie ID 讓server 辨認
* Server 端在 backend database 處理
* Client 端儲存每個網站的 cookie ID 於 cookie file 中
* Cookie 讓 server 能分析 client 行為，但可能會有private issue
* `Proxy 快取網頁`
* Proxy 通常是由 ISP(學校、公司) 提供
* Proxy server 預先 cache 原本 server，使得存取資料可以更快
* Proxy 的角色同時為 client 及 server
* 優點
* 減少 response time
* 減少 link 的 traffic
* 很多備份，讓 server 可以服務更多使用者
* `Conditional get`
* proxy 定期向 server 檢查檔案是否有更動
* GET 請求，並且 header line 夾帶 IF-modified-since
* 無更動，回傳 `HTTP/1.0 304 Not Modified`
* 有更動，回傳 `HTTP/1.0 200 OK` 及更動後的檔案
#### FTP 檔案傳輸協定
* File Transfer Protocol
* 使用 TCP 連線
* 用來傳輸檔案
* 預設 port 20, 21
* 20 用於傳送資料
* 21 用於控制、身分認證及瀏覽檔案夾等
* FTP command
* USER XX
* PASS XX
* LIST XX
* RETR XX
* STOR XX
#### SMTP 簡單郵件傳輸協定
* Simple Mail Transfer Protocol 簡單郵件傳輸協定
* 使用 TCP 建立連線
* 預設 port 25
* 3個階段
* `handshaking`
* transfer message
* closure
* Mail server 本身是 client 也是 server
* Persistent Connection
* SMTP 規範 mail server 之間互通 Mail 的標準，而 client 去存取 mail server 則有其他 Mail access protocol
* `POP3`：Post Office Protocol
* `IMAP`：Internet Mail Access Protocol
* `HTTP`: Gmail, Hotmail, Yahoo
#### DNS 域名服務系統
* Domain Name System
* 將 IP Address 以及 Domain Name 相互轉換
* 去中心化，分散式資料庫
* 可以分成三層
* `Root name servers`
* `Top-level domain (TLD) servers`
* `Authoritative DNS servers`
* `Local Name Server`
* 自己在 local 建的 proxy，會先來這裡查並 cache 查過的DNS
* 
* DNS Record
* 實際上在DNS上儲存的資料長的樣子。
* `RR format: (name, value, type, ttl)`
* `A`：name 對應到 IP
* `NS`：domain 對應到 authoritative name server
* `CNAME`：alias name 對應到 real name
* `MX`：domain 對應到 mail server
* 申請 DNS 服務
* 向 `registrar` 註冊，確認 domain name 是唯一的
* 提供兩台 Authoritative DNS servers 的名字及 IP
* TLD server 加入兩行 record
* (xxx.com, dns1.xxx.com, NS)
* (dns1.xxx.com, 99.99.99.1, A)
* (xxx.com, dns2.xxx.com, NS)
* (dns2.xxx.com, 99.99.99.1, A)
* 而本身公司的 Authoritative DNS servers 也要有 record
* (www.xxx.com, 99.99.99.4, A)
* (mail.xxx.com, 99.99.99.5, A)
* (xxx.com, 10 mail.xxx.com, MX)
#### P2P
* BitTorrent (BT 協定)
* Tracker：提供有檔案的client清單
* Torrent：有檔案的client，彼此分享
* Distributed Hash Table (DHT)
* 存 (key,value) 的分散式資料庫
* 假設每個 peer 有自己的 ID
* Circular DHT
* 把 (key,value) 分配給 ID 最靠近 key 的 peer
* 用一個環狀結構維持 peer 的話，平均要走 n/2 步
* Circular DHT with Shortcuts
* Peer churn
* 如果 DHT 中，有人要離開，不行讓某些 (key,pair) 資訊不見
* 每個 peer 記住第一和第二後繼，定期檢查是否 alive 並更新
* 有人要離開時可以直接更新資訊
* 下載策略: rarest first (最稀有優先)
* 上傳策略: Tit-for-Tat 只會將 chunk 上傳給 5 個相鄰 peer
* 每十秒 Top 4 傳給自己速度最快的人
* Optimistic 每三十秒隨機傳給相鄰的人
#### SSH 安全外殼協定
- Secure Shell 安全外殼協定
- 提供加密的安全傳輸環境
- 遠端的機器必須跑一個 SSH daemon
- 本地機器則要有一個 SSH client
- `OpenSSH` 是一個 SSH 協定的開源實作，也可以說是遵守 SSH 的一組工具
- 相對於 `Telnet 協定` ，其所傳輸的資料並未加密較不安全
## 3.Transport Layer
#### Multiplexing and demultiplexing
- multiplexing：從不同 socket 收集資料，加入 header 後交給網路層向外傳出
- demultiplexing: 將傳進來的資料，傳送給正確的 socket 工作
#### UDP 用戶資料報協定
- Unreliable
- 不保證被接收
- 不保證順序
- 不重新傳送遺失資料
- 不控制流量
- 非連線型
- 傳送資料前不會先通知對方
- 適合用於影音或影像等可以容忍 packet loss 的應用
- 也可以自己練習用 UDP 維護資料正確性
- 

#### TCP 傳輸控制協定
- Reliable，連線型
- [Three way handshake](https://notfalse.net/7/three-way-handshake)
- client 端傳送 SYN
- server 端傳送 SYNACK
- client 端傳送 ACK
- 

#### Pipelining Protocols
- https://www2.tkn.tu-berlin.de/teaching/rn/animations/gbn_sr/
- Go Back N
- 傳送端
- `共用一個 Timer` 紀錄尚未收到新 ACK 的時間
- Timeout: 重送所有 window 內的封包
- 收到 window 外的 ACK：不做任何事情
- 收到 window 內的 ACK
- 更新 window
- 傳送 1 個或多個還未送過的新封包
- 重設 Timer
- 接收端
- 正確順序：回傳該封包序號的 ACK 給傳送端
- 錯誤順序：回傳最後一次收到正確序號的 ACK 給傳送端
- Selective Repeat
- 傳送端
- `每個封包有自己的 timer`
- Timeout: 重新傳送該封包
- 收到 ACK，把該封包標為已收到
- 若該封包恰好為 window 的開端
- 更新 window
- 傳送 1 個或多個還未送過的新封包
- 接收端
- 已經 ACK 過的封包：再 ACK 一次
- window 開端：回傳 ACK 並移動 window
- window 其他：回傳 ACK 將錯誤順序的封包暫存
## 4.Network Layer
#### IPv4 addressing
- IP datagram
- 
- 把傳輸層的資料再加入 IP 資訊封裝
- TCP/IP overhead = `20 bytes` of TCP + `20 bytes` of IP + `app layer overhead`
- Subnet
- 內網可以有自己的內網 IP
- 內網互相傳遞資料不避經由 router
- 對外的連線由 router 負責維護
- IP 可以拆成 `子網路` + `主機位址`
- `Classless InterDomain Routing (CIDR 表示法)`
- 用 a.b.c.d/x 來標記 IP 中的子網路部分
- 表示 IP `a, b, c, d` 的前 x 個 bits
- 透過可變長度子網路遮罩（VLSM）來辨別子網路
- 如果我們指定一個 CIDR 塊為 10.10.1.32/27，則 10.10.1.44 屬於該塊，但 10.10.1.90 不是
- `Dynamic Host Configuration Protocol(DHCP) 動態主機設定協定`
- DHCP server 動態發放內網 IP
- `Network Address Translation`
- NAT router 維護內網 IP 和外網 IP 間的轉換
- NAT translation table: 儲存 `(source IP, port #) 到 (NAT IP, NAT port #)` 對應關係
- 為了解決 IP 不夠用的問題
- NAT traversal problem 外網要如何連線到特定內網 IP 的機器
- 解法一: 主動去 NAT 配置，把某個 port 的請求都丟給內網那台機器
- 解法二: 透過 IGD 協議，讓內網去配置 NAT
- 解法三: 內網把服務中繼在外網的中繼站(relay)，client 連線到中繼站
#### Internet Control Message Protocol (ICMP) 網際網路控制訊息協定
- 用來偵測網路的狀況
- 流量控制
- 偵測無法到達的目的地
- 重導路徑
- 偵測遠端主機
- 很多常用的工具是基於ICMP訊息
- `traceroute` 通過發送含有 TTL 的封包，然後接收 ICMP 超時訊息和目標不可達訊息來實現
- `ping` 用 ICM P的 "Echo request" 和 "Echo reply"訊息來實現
#### Routing algorithms
- Forwarding table
- 放在 router 中
- 根據封包的目的地，決定要對應到哪一個鄰近的 router
- 使用 Longest prefix matching
- 假設知道網路的分布，則決定 a 到 b 要走哪一條路最近
- Link state
- 定期測試到 neighbor router 時間
- 定期 broadcast 給其他『所有』路由器
- 利用 `Dijkstra Algorithm` 可得知到所有路由器所需時間
- Distance Vector
- 每個 router 維護一張到所有 distance matrix
- `Bellman-Ford Algorithm` 利用相鄰 router 分享不斷更新distance matrix
- Hierarchical Routing
- 實務上，host 可能的數量達到 million
- 相鄰的 router 組成 `Autonomous system, AS`
- 區分成 inter AS 及 inner AS 做 routing
#### Routing Protocols
- RIP ( Routing Information Protocol)
- OSPF (Open Shortest Path First)
- BGP (Border Gateway Protocol)
## 其他
- RESTful API 表現層狀態轉換 API
- 一種網路架構風格
- 善用 HTTP protocol (GET/POST/PUT/DELETE) 對資源進行操作
- 優點
- 瀏覽器即可作為 client 端
- 可以更高效地利用 cache 來達到更快的回應速度
- 界面與資料分離
- 節省伺服器的計算資源
- 可重用 web/android/ios 都可以用, 無痛轉換
- 要求
- client - server 架構
- 分層系統
- 通訊協定具有無狀態性
- 統一界面