---
# System prepended metadata

title: 課程｜計算機網路
tags: [課程]

---

# 計算機網路

## 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。
    ![](https://i.imgur.com/bSyjGQS.png)
#### 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
    * ![](https://i.imgur.com/DOxzG34.png)
* 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 維護資料正確性
- ![](https://i.imgur.com/254AeYZ.png)

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

#### 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
    - ![](https://i.imgur.com/I9duVcp.png)
    - 把傳輸層的資料再加入 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 架構
        - 分層系統
        - 通訊協定具有無狀態性
        - 統一界面


