---
# System prepended metadata

title: 計算機網路
tags: [大學必修-筆記]

---

計算機網路
===
###### tags: `大學必修-筆記`
Ch1-1
===
## 名詞解釋

:100::100::100:
===

* host -> 主機
* bandwidth -> 頻寬
* Internet Standard -> 網際網路標準 
    * 指關於網際網路相關的技術與方法論的技術規範。ex：RFC
* guide medium -> 有指向性的傳輸媒介 ex：各種線…
* unguide medium -> 沒指向性 ex：無線
* twisted pair -> TP -> 雙絞線
## 設備

* PC server phone -> hosts = end systems
* router 路由器 -> packet switches

## 網路結構

* network edge 網路邊緣 -> 主機host、應用程式application
* network core 網路核心 -> 路由器、網路中的網路
* packet transmission delay  = $\frac{L}{R}$  
    * packets of length -> L
    * transmission rate -> R

## protocol 協定

* 網路的標準
* 所有程式以協定標準來開發
* protocols define *format*, *order of messages sent* and *received among network entities*, and actions taken on message transmission, receipt

CH1-2
===
## Access network

### DSL - digital subscriber line 
![](https://i.imgur.com/sbhMOm4.png)

* 利用電話線網來傳輸
* 電話和上網都在同一條電話線裡傳輸
* 電話公司會用頻率來分開
* ADSL 非對稱式數位用戶專線 -> 下載流量大於上傳流量

### cable

![](https://i.imgur.com/IzHaQ6h.png)

* 利用第四台的線來傳輸
* 只有一條cable線，大家共用

![](https://i.imgur.com/98EIS5H.png)

* FDM - frequency division multiplexing
* 不同的資料利用不同頻率來作為區別

### wireless LANs 無線網路

* 距離短，速度快
* ex：802.11n 、802.11ac
### wide-area wireless access 行動網路

* 距離長，速度慢
* ex：4G、5G

## Physical media 傳輸媒界

* twisted pair (TP) - 雙絞線
    * ex：CAT-5、CAT-5e、CAT-6
* coaxial cable - 同軸電鑬
* fiber optic cable - 光纖

CH1-3
===
## queuing and loss
* 如果 arrival rate 超過 transmission rate 的話
    
    * 封包會進入 queue，等待被傳送
    * 如果 queue 滿的話，封包有可能會 dropped (lost) 
## packet switching -> 封包交換

* store-and-forward 儲存並轉發
    * 路由器先把封包存起來，等封包傳完後，才會再往下傳。
* queue and loss 封包延遲與遺失
    * 如果路由器裡的封包queue滿了會
    * (1) 會有delay
    * (2) 如果queue滿了，封包可能會 lost(dropped)
* routing & forwarding
    * routing -> 路由器對表，規劃路徑
    * forwarding -> 用規劃好的路徑，把封包傳下去

## circuit switching -> 線路交換

* 特性
    * 在連線之前會先 **call** ，進行路線尋找及線路保留
    * 優點：連線時就不會有封包塞車問題
    * 缺點：線路一旦預留，資源無法共享，浪費線路
* FDM 分頻多工 & TDM 分時多工
    * FDM -> 利用頻率來區分
    * TDM -> 利用時間來區分
![](https://i.imgur.com/Qjbd6PM.png)

## 網路結構 network of network

* ISP -> 網際網路服務供應商
    * host才能連到Internet
* peering link -> 各ISP之間的對等連結
* IXP -> internet exchange point 

CH1-4
===

## Delay 延遲

![](https://i.imgur.com/1OAM50s.png)

* $d_{nodal} = d_{proc} + d_{queue} + d_{trans} + d_{prop}$

* nodal processing delay 節點處理延遲
    * 路由器處理Header與找路徑等所花費的時間
        * 檢查錯誤
        * 查表時的delay   
* queue delay 排隊延遲
    * 路由器無法立刻將傳送封包到網路上造成封包停留在buffer上所花的時間
* trasmition delay 傳輸延遲
    * 將封包傳至link的時間 -> 從路由器丟出去的時間
        * $d_{tran} = \frac{L}{R}$
* propagation delay 傳播延遲
    * 在網路線上傳輸所花費的時間，路由器之間的時間
        * $d_{prop} = \frac{d}{s}$

## Packet loss 封包遺失

* Traffic Intensity 通訊密度 = $\frac{La}{R}$
    * R -> Link Bandwidth 連結頻寬
    * L -> Packet Length 封包大小
    * a -> Avg. arrival rate of packet 平均封包抵達率

* 解決方法
    * 要求上一個路由器重傳
    * 要求來源端重傳
    * 不理它

## Throuthput -> 傳輸量

* 單位時間能成功傳遞的平均資料量
* bottleneck link -> 傳輸瓶頸點

CH1-5
===
## protocol layers 協定層

* 降低複雜度，模組化，好管理
* 但可能同個事情做兩次，沒效率
* reference model -> 參考模形
* ~~降低複雜度、標準化介面、模組化工程、溝通化技術~~

## TCP/IP model
![](https://i.imgur.com/2XBTbAL.png)
* **Application 應用層**
    * ex：FTP, SMTP, HTTP
* **Transport   傳輸層**
    * ex：TCP, UDP
* **Network 網路層**
    * ex：IP, 路由器協定
* **Link 資料連結層**
    * ex：乙太網路, 802.11
* **Physical 實體層**
    * 把訊號轉成bit



CH1-6
===

## 網路安全

* Torjan Horse
* Virus
* Worm
* DDoS -> 分散式阻斷攻擊
    * 攻擊者透過大量假的流量，來使伺服器癱瘓，造成一般流量無法正常使用
* Packet Sniffing

CH2-1
===

## Application architecture

* Client-Server architecture 主從式架構
    * server
        * 固定IP
        * 永遠在線上
    * clients
        * 動態IP
        * client 和 client 之間不會連線
* Pure P2P architecture 點對點架構
    * 不用一直在線上
    * 都可以直接互相連線
    * 每個主機都可以是提供資料的伺服器
    
* Hybird Client-Server(P2P)
    * 主從式，點對點混合架構

## Processes Communicating  行程通訊

* 同一個主機
    * Inter Process Comunication(由OS定義) 行程間通訊
* 不同主機
    * Message 訊息

* Process -> 在主機內執行的程式
    * Client Process：初始產生通訊的行程
    * Server Process：等待被連接的行程
* P2P 的話是 Client Process Server Process 同時並行

## Sockets
![](https://i.imgur.com/3bTVVS9.png)
* Process 傳送 Message 給 socket
* Process 接收 Message 從它的 socket
* Socket 位於應用層(Application)與傳輸層(Transprotarion)之間的介面
* Socket 就像「門」一樣

## Address Processing 行程定址

* 一個 Identifier 包括
    * IP address -> IP 地址
    * port number -> 埠號

## Application 需要的服務

* 應用程式需要什麼傳輸服務

    * data integrity 資料完整性
    * timing 時序
    * throughput 頻寬
    * security 安全

## Protocols services

* SSL (只用於TCP) 傳輸層安全性協定
    * provides encrypted TCP connection
        * http -> https
    * data integrity
    * end-point authentication
* TCP 傳輸控制協定
    * reliable transport 可靠的傳輸服務 
        * 如果封包遺失，TCP會要求重傳
    * flow control 流量控制 
    * congestion control 壅塞控制 
    * connection-oriented 連線導向服務 
    * 沒有提供 
        * 時序
        * 最小頻寬的保證
* UDP 用戶資料包協定
    * 不會做 reliable transport
    * 因此有低延遲，高頻寬的特色

CH2-2
===

## HTTP 超文字傳輸協定

### 名詞解釋
* RTT (Round-Trip Time) -> packet 來回 client server 所花的時間

### HTTP介紹
* Overviwe
    * 使用TCP做為傳輸
    * port掛在80
    * **stateless** -> 無狀態協定
        * server 不會儲存用戶端過去的請求資訊
        * client 跟 server 要什麼，就給什麼
* HTTP connections
    * Nonpersistent HTTP　非持久連接
        * 每下載完一個文件，TCP連線就會被關掉
        * 一個TCP連線只能傳送一個檔案
    * Persistent HTTP　持久連接
        * TCP連線會等一下，不會馬上關掉
        * 一個TCP連線可以傳送多個檔案
    
    ![](https://i.imgur.com/kqlTsRq.png)

* HTTP message
    * request![](https://i.imgur.com/QODqQBA.png)
    * response![](https://i.imgur.com/waIaZS5.png)

* HTTP 錯誤訊息
    * 200 OK - 確定。用戶端要求成功
    * 301 Moved Permanently - 要求的網頁已經永久改變網址。此狀態要求用戶端未來在連結此網址時應該導向至指定的 URI
    * 400 Bad Request - 錯誤的要求
    * 404 Not Found - 找不到
    * 505 HTTP Version Not Supported - 不支援的 HTTP 版本

    
## cookies
![](https://i.imgur.com/9Qtlqah.png)

* 步驟
    1. HTTP 回應訊息的 cookie標頭列
    2. HTTP 請求訊息的 cookie標頭列
    3. 保留於使用者終端系統上的一份cookie檔案，並且由使用者瀏覽器管理
    4. Web網站的後端資料庫 

* cookies 運作方式
    * 在User瀏覽線頁後，WEB server會送cookies記錄User在網站上使用的足跡
    * 下次再去這個網站時，就可以利用cookies判斷user，傳送特別定網頁內容給user

* cookies 能做
    * authorization
    * shpooing carts
    * recommendations
    * user session state

## Proxy server 代理伺服器

![](https://i.imgur.com/QO75GDy.png)
* 解釋
    * 在server 和 client 中間加一個server
    * 如果中間 server 已經有資料的話 -> 變成server提供資料
    * 如果中間server 沒有資料 -> 向原本的 server 要求資料 
* 優點
    * 減少client request的回應時間
    * 塞車機率下降
* 缺點
    * 資料有可能沒有更新 
* Conditional GET -> 條件式 GET
    * proxy server 向來源 server 確認資料最後更新時間
    * 如果時間相同 -> proxy 傳送 data
    * 如果時間不同 -> 向原 server 傳 request

CH2-3
===

## 電子郵件
* User Agent 使用者代理
* Mail Server 郵件伺服器
    * mailbox
    * message queue
    * SMTP protocol
## SMTP 簡單郵件傳輸協定

* 解釋
    * 使用TCP
    * 埠號為 25
    * direct transfer 直接傳輸 -> 不會有第三者看到
    * 訊息一定要是 7-bit ASCII
    * 使用 persistant connections -> 一個連線可以傳送多封郵件
    * SMTP是一個「送出」的協議，它不允許根據請求從服務器上「取回」來消息
    * SMTP 因為沒有身份驗證，導致垃圾郵件盛行

* Mail Format
 ![](https://i.imgur.com/PKUyLkj.png)
    * header -> 收件者、標題…
    * body -> 信件內容

## POP3 郵局協定第3版

* 跟 SMTP 比多了身份的驗證
* 下載所有未讀信件
* 下載後電子郵件服務就會將它們刪除
* 之後只能使用同一台電腦來存取該郵件

## IMAP 網際網路郵件存取協定

* 不會主動下載郵件，除非使用者點開信件

CH2-4 DNS domain name system
===

* 領域名稱系統

* 用 UDP 實做

* distributed database 分散資料庫
    * 為何使用分散
    
        * 單點故障 -> 如果有一個點壞了，仍然可為其他人服務
        * 通訊流量過載 -> 如果使用集中式，資料量會太大
        * 遠距離集中式資料庫 -> 如果使用集中式，有些人的距離會太遠
        * 維護
* application-layer protocol 在應用層執行
    * 優點 -> 保持網路的簡單

* DNS service
    * 主機名稱到IP位址的轉換
    * host aliasing 主機別名
    * mail server aliasing ( 郵件伺服器別名 )
        > 將電子信件地址轉成位置
    * load distribution ( 負載分配 )
        > 一個網站可能有多台伺服器 每個伺服器的ip和主機名稱不同 有要求傳送過來時 dns會一直改變回傳的伺服器的主機名稱及ip 

* Hierarchical Database 階級式資料庫

* ![](https://i.imgur.com/gbBlzsB.png)

    * root 根伺服器
        * 提供 TLD 的 IP address
    * top-level domain(TLD) 高階網域伺服器
        * 尋找這個網站是什麼類型的
        * ex：com、edu、org…
    * authoritative server 官方 DNS 伺服器
        * 組織公司的 DNS 伺服器
        * 替組織內的伺服器提供管控的==主機名稱==到==IP==的對應 
    * Local Name Server 區域 DNS 伺服器
        * 不在以上三個架構裡面
        * 像 proxy 一樣
        * 先看 cache (快取)
        * 如果沒有就向 root 尋問
        * 負責查訊用的

* Local Name Server 查訊方式
    * Iterated Query 循環式查詢
        * 把問題丟給 local DNS
        * 向不同的 server 依次尋問
![](https://i.imgur.com/HHYopwH.png)
    * Recursive Query 遞歸式查詢
        * 把問題丟到 root 去做
![](https://i.imgur.com/Im8DXPL.png)

* cache 快取
    * 為省 root 的負擔，有些 lns 會直接向 TLD 要位置，存在 cache 裡
    * 為解決 cache 有可能資料過舊的問題
    * 加入 TTL -> 存活時間
    * 要求 lns 重新要求新的 cache

* DNS records
    * resoruce records -> RR 資源紀錄
        * name
        * value
        * type
        * TTL
    * type = A
        * name = hostname
        * value = IP address
    * type = NS
        * name 為網域名稱
        * value 為 authoritative name 名稱
        * 不會單獨存在
        * 會和 type = A 一起存在
        * 放在 TLD 裡面
    * type = CNAME
        * name 為別名
        * value 為別名 
        * 不會單獨存在
        * 會和 type = A 一起存在
    * type = MX
        * value 為 mail server 的名稱
        * 不會單獨存在
        * 會和 type = A 一起存在

* DNS messages
* ![](https://i.imgur.com/ez0dVIG.png)
    * 不管是 query reply 訊息格式都是一樣的

* 在DNS中新增紀錄

CH2-5 P2P
===

## P2P 架構

* 點對點式架構
* server不需一直在線上

## File distribution time

![](https://i.imgur.com/Mq90yts.png)

* Client-Server 主從式
    * $d_{cs} = max \left \{ NF/u_s, F/min(d_i) \right \}$
* P2P 點對點
    * $d_{p2p} = max \left \{ F/u_s, F/min(d_i) , NF/(u_s + \sum u_i) \right \}$

* BitTorrent 位元洪流
    * 為了解決有人關機後，資源就無法再上傳的問題
    * requesting chunk
    * sending chunk 資料片段 -> rarest first 稀有優先
    * Tit-for-Tat -> 獎勵頻寬留很多的人

CH2-6 Video Streming & CDN
===

## Video 
* 為了確保在網路頻寬使用越來越大
* 影片的流暢度不受影響

* spatial coding 空間編碼
    * 一張影片有一樣的地方時
    * 可以只記錄那個地方來壓縮
* temporal coding 時間編碼
    * 當有兩張差不多的影片時
    * 只傳送第兩張有變更的部分

* DASH over HTTP 基於超文字協定的動態自適應流
    * manifest file 清單文件
    * 在server端 ->
        * 將影片分成多個 chunks
        * 用不同的 rate encode 來儲存chunks
        * 跟據 menifest file 給不同的 URLs
        
    * 在client端 ->
        * 週期性的確認 server-client 的頻寬為多少
        * 生成 menifest file
            * 決定什麼時候開始影片片段下載
            * 決定下載的是什麼畫值的版本
            * 決定要去那裡去下載影片的片段

## CDN Content distribution networks
* 內容傳遞網路
* 利用最接近 user 的 server，更快更可靠的把影片傳送給 user
* 可以解決日漸增加的頻寬使用量
* 使用 DNS 實作 -> 可以找到離 user 最近的 server 及 使用的線路
* enter deep
    * 影片內容server 離clinet端越近越好
* bring home
    * 把設備放在接近 POP 的地方，離client比較遠，但存放的影片比較多

CH3-1
===

## 傳輸層 Transport-layer 的服務
* 提供提供不同主機上 application 之間的邏輯通訊 logical communication

* send side 傳送端
    * 將應用程式的訊息分割成資料區段 (segments)+傳輸層標頭、傳送到網路層
* rcv side 接受端
    * 接收端： 將 segments 重組成訊息、傳給應用層

## 傳輸層 v.s. 網路層

* 網路層 
    * ==主機 host== 之間的邏輯通訊 (logical communication)

* 傳輸層
    * ==行程 process== 之間的邏輯通訊 (logical communication)

> [name=jojo的奇妙比喻][color=#ffcc00]
> 12 個小孩傳送信件給12個小孩
>
> 行程 $\rightarrow$ 小孩
> 應用程式訊息 $\rightarrow$ 信封中的信
> 主機 $\rightarrow$ 房子
> 傳輸協定 $\rightarrow$ Ann 以及 Bill (?
> 網路層協定 $\rightarrow$ 郵政服務

## 網際網路傳輸層協定

* TCP (Transmission Control Protocol 傳輸控制協定)
* UDP (User Datagram Protocol 使用者資料封包協定)


CH3-2 Multiplexing & demultiplexing
===
* 多工 & 解多工的目的
    * 將網路層所提供的 host-to-host 延伸為讓主機上所執行的**應用程式**
    * 提供 process-to-process 的傳送服務

## 
* 傳送端主機的多工
    * 收集多個socket的資料、用 transport header 標頭 將每個資料片段封裝成資料分段(segment)

* 接收端主機的解多工
    * 將收到的資料分段 (segment)傳送給正確的socket
![](https://i.imgur.com/pnqiBM8.png)

> [name=jojo的奇妙比喻][color=#ffcc00]
> 解多工(demultiplexing)操作
> 當Bill從郵差收到一批信件時
> 分出信的收件人是誰，然後將信交給收件人
>
> 多工(multiplexing)操作
> 當Ann從兄弟姊妹處收集完信件
> 並將信件交給郵差

## 解多工

* 流程
    1. 當segments到達該主機時
    2. 傳輸層會檢查該區段中的目的端port number
    3. 並將該區段傳給相對應的 socket
    4. 該區對的資料會透過該 socket 傳給相對應的process

* 主機的每個socket都可以指定一個port number

### 無連線 UDP 解多工
* 以==埠號==產生 UDP socket
* 以兩組資料識別 UDP socket

    * 目的 IP 位址
    * 目的埠號
* 當主機收到 UDP segments時

    * 確認資料分段中的來源端埠號
    * 以此埠號將UDP資料分段傳送到socket
### 連線導向TCP的解多工

* 以四組資料識別
    
    * 來源端 IP 位址
    * 來源端埠號 
    * 目的端 IP 位址
    * 目的端埠號


CH3-3 無連線傳輸 -> UDP
===

* 無連線傳輸

    * 在 UDP 傳送端和接收單之間沒有==交握程序==
    * 每一個 UDP 資料分段的處理和其它資料分段是==獨立==的

* UDP 的功能

    * streaming multimedia apps
    * DNS
    * SNMP

* checksum

    * 把資料分段內容的兩段互做==加法==
    * 當數字加總時，最高位元的進位必須被加回結果中
    * 把結果換成 ==1 的補數==

![](https://i.imgur.com/cIqkzgZ.png)


CH3-4 reliable data transfer 原則
===

## 可靠的資料傳輸

![](https://i.imgur.com/RKtPSZC.png)

* rdt -> 可靠的資料傳輸
* udt -> 不可靠的資料傳輸
---
* 一共有兩種狀態 ->  send side, receive side
* 傳送端
    * rdt_send()
    * utd_send()
* 接收端
    * rdt_rcv()
    * delever_data()
* 中間經過了一道不可靠的通道
* 我們為了要解決封包完整的問題
* 提出了以下機種解決辨法

## rdt 1.0

* 假設不可靠通道是

    * ==沒有位元錯誤==
    * ==沒有資料遺失==

* 傳送端、接收端分別只做
* rdt的傳送端

    * 從上層接收資料
    * 建立包含該資料的封包(透過 packet = make_pkt(data))
    * 並將該封包送入通道中 udt_send(packet)

* rdt的接收端

    * 透過 rdt_rcv(packet) 事件接收來自下層通道的封包
    * 透過 extract(packet, data) 的動作從封包中取出資料
    * 將資料往上交給上層 (透過 deliver_data(data))

* 簡單來說傳送方和接收方只要能正確接收資料就可以了
* 因為發過來的資料保證一定是正確的

## rdt 2.0

* 假設不可靠通道是

    * ==有位元錯誤==
    * ==沒有資料遺失==

* 為了解決位元錯誤的問題，加入了

    * 偵測位元錯誤的檢查和 (checksum)
    * 接收端回覆 (ACK、NAK)

---

* 如果位元沒有發生錯誤

    * 接收端會回傳 ACK

* 如果位元發生錯誤

    * 接收端會回傳 NAK
    * 傳送端收到 NAK 後重傳封包

---

* 以上做法叫做 ==stop and wait==
* 傳送端傳送一個封包、並等待接收端的回應

---

* rdt 2.0 有個大問題
* 如果今天連 ACK NAK 都有問題怎麼辨？
* 傳送端不知道接收端發生了什麼事
* 傳送端也沒辦法直接重傳
* 可能會產生**重複封包**的現象


## rdt 2.1

* 解決 ACK/NAK 錯誤的問題
---
* 假如 ACK/NAK損壞了、傳送端會重新傳送目前的封包
* 傳送端會在每個封包加上序號 -> 0 or 1 一位元就可以
* 接收端刪掉重複的封包
---

* 傳送端

    * 在封包加入序號
        * 兩個序號 (0、1) 就足夠了
        * 先前傳送過的封包
        * 新傳送的封包
        > 接收方如果收到0
        > 就知道這次不是新的報文段
        > 可能是上次ack出錯了
        > 傳送方無法確認就重傳了上次的報文段
        > 所以接收方需要丟掉這個報文段
        > 然後再次傳一次ack確認訊號
        > 
        > 如果收到的是序號為1的報文段
        > 則接收方直接接受就可以了。
    * 檢查收到的 ACK/NAK 是否損毀
    * 兩倍數量的狀態
    * 狀態必須「記得」「目前的」封包序號為 0 或是 1

* 接收端

    * 必須確認接收端封包是否重複

        * 如果序號重複 -> 代表 ACK/NAK 有誤 -> 接收端重傳 ACK/NAK
        * 如果序號不同 -> 接收方接收

    * 接收端無法得知最後一個 ACK/NAK 是否在傳送端被接收無誤

## rdt 2.2

* 其實我們不太需要 ACK/NAK
* 把兩個統一變成 ACK ==加序號==
* 與 rdt 2.1 同樣的功能、但只使用ACK
---
* 利用 ACK, 0 及 ACK, 1 
* 來分別表達接收端的回應

## rdt 3.0

* 假設不可靠通道是

    * ==有位元錯誤==
    * ==有資料遺失==

* 為了資料遺失錯誤的問題，加入了

    * 倒數計時器 (countdown timer) -> 超過指定的時間後，將對傳送端發出中斷
---

* 會有以下四種狀況

    * 沒有發生資料遺失
    ![](https://i.imgur.com/F2Js7Kd.png)
    * 封包遺失
    ![](https://i.imgur.com/Q8qPajo.png)
    * 遺失ACK
    ![](https://i.imgur.com/vzX2sHx.png)
    * 過早發生逾時
    ![](https://i.imgur.com/NUkYA1c.png)
    
---

* rdt 3.0 解決了大部份的問題
* 但是因為它是使用 ==stop and wait== -> 效能很糟！

![](https://i.imgur.com/028Cona.png)

* 改採用 ==管線化 (pipelining)== -> 改採允許同時送出多個封包，不需要等待確認

## Pipelined protocols 管線化

* 可以一次傳多個封包

![](https://i.imgur.com/dkLtBZ2.png)

### Sliding-window protocol 滑動視窗協定

### Go-Back-N GBN協定

![](https://i.imgur.com/g1JL9t9.png)

* base: 最久未被確認的封包的序列號碼
* nextseqnum: 最小未被使用到的序列號碼

* 傳送端

    * 來自上層的呼叫
        * 當收到上層呼叫 rdt_send() 時
        * 傳送端會檢查 window 是否已經滿了?
    * ACK的接收
        * 累積式確認 (cumulative acknowledgement)
        * 確認小於或等於序號 n 的所有封包
    * 逾時事件 (timeout event)
        * 傳送端會重新傳送所有先前已經傳送但尚未收到確認的封包

* 接收端

    * 只為==接收順序正確==的封包傳送ACK
        * 一次傳送一個封包給上層
        * 可能會產生重複的ACK (因為捨棄掉未按順序到來的封包序號)
        * 只需要記住 ==expectedseqnum== (下一個封包的序列號碼)
    * 順序不正確的封包

![](https://i.imgur.com/XtiJtjj.png)

> 傳送端：
>> 收到連續的ACK之後
>> Window會往前滑動
>> 傳送端可以繼續傳送新的封包

> 接收端：
>> 因封包2遺失了
>> 所以已接收的封包 3, 4, 5都丟棄掉

### 選擇性重複 (SR)

* 改善 GBN 的問題：
    * 單一封包錯誤將可能導致 GBN 重新傳送大量的封包
    * 但大部分不須重新傳送

* SR 的改善方法：
    * 傳送端只重新傳送未正確收到的封包

![](https://i.imgur.com/GBwLfZf.png)

* 傳送端

    * ACK
        * 將封包 n 標示為已收到的
        * 假如 n 為未確認的封包中最小的封包時，將視窗的base 往前移到下一個未回應ACK的序號
* 接收端

    * 傳送 ACK(n)
        * 不正確的順序： 暫存區
        * 正確順序： deliver 將視窗前進到下一個未接收的封包

![](https://i.imgur.com/b5P5QcS.png)

> Window size = 4 個封包
> 傳送端會送出序號0到3的封包
> 每個封包都有其邏輯的計時器

* 參考資料
    * https://www.itread01.com/p/14788.html

CH3-5 連線導向傳輸 -> TCP
===

## TCP 特色

* point-to-point 點對點
    * 一個傳送端、 一個接收端
* reliable 可靠的
* pipelined 管線化
* full duplex data 全雙工資料傳輸
* connection-oriented 連線導向
* flow controlled 流量控制

### 分段結構

CH4-1
===

### 名詞解釋
* Forwarding 轉送
    * 封包從 路由器的輸入 → 路由器的輸出
* Routing 路由
    * 決定封包從 來源端 → 目的端 的路由

### 網路層
* Data plane 資料層
    * 轉送功能，每個路由器收到封包後，決定該封包要往哪個路由輸出端口送出
* Control plane 控制層
    * 路由功能，決定一個封包要從 一個端點 傳送到 另一個端點 的路徑



CH4-2
===

* Destination-based forwarding
* Generalized forwarding -> 可以跟據封包的內容來決定 forwarding

* Longest prefix matching 最長前綴匹配
    * 找到子網掩碼長度最長的封包
    * 路由表中，與目的地址的高位匹配得最多的表項。

* Switching Fabric 
    * memory 透過記憶體的頻寬傳輸
    * bus 直接互連
    * crossbar 棋盤式交換器

* Head-of-the-Line 佇列前端攔阻
    * 佇列中的封包必須等待，因為它被位於佇列前端的其它封包所攔阻。
    * HOL阻攔發生，佇列長度便會不停增長，而發生封包遺失。

* output ports -> router 結構與上一個相反

    * buffering
        * 雍塞會發生在 buffe queueing 
    * scheduling discipline
        * 每一個封包的重要性都不同
        * 把最重要的封包得到最好的效能 -> gets best performance
        * network neutrality

* buffer 倒底要多大

$$
RTT C
$$

* scheduling mechanisms
    * 排程
    * FIFO
        * discard policy -> 
        * tail drop -> 滿了後誰來，誰就 drop
        * priority -> buffer 快滿後，只 drop 優先權最低的封包
        * random -> buffer 快滿後，隨機 drop 封包，有可能 drop 到大封包(cwnd 一次傳超多)

    * priority scheduling
        * 給每一個封包一個優先權
        * 高優先權的封包先送
        * 怎麼判斷優先權？ -> 看 header info

    * Round Robin (RR)
        * 輪流看兩個 queue (高、慢)
        * 也輪流傳送封包

    * Weighted Fair Queuing (WFQ)
        * 每一個封包分配到的頻寬都不一樣
        * 改善 RR 的每一個封包的頻寬都一樣

CH4-3
===

MTU max transfer size

CH4-4
===

* subnet 子網
    * 沒有經過路由器算一個subnet

* IP address 
    * subnet part
        * 不需要經過路由器
    * host part

* CIDR -> Classless InterDoman Routing 無類別域間路由
    * 是一個用於給用戶分配IP位址以及在互聯網上有效地路由IP封包的對IP位址進行歸類的方法。

* DHCP -> Dynamic Host Configuration Protocol 動態主機設定協定
    * 幫忙把 網址 轉成 IP 地址
    * 不能跨網段
    
    * DHCP Discover : 客戶端發出**廣播**要求IP ( 0.0.0.0 -> 255.255.255.255 )
    * DHCP Offer : _多個_ DHCP 伺服器收到，回應未租約 IP
    * DHCP Request : 客戶端收到多個IP，再度廣播自己選擇了哪一個IP
    * DHCK Ack : _被選的_ DHCP 伺服器回應，確認此IP租約。

* Hierarchical addressing
    * 在 CIDR 架構下
    * 減少 router 廣播路徑的數量

* NAT
    * replace -> 將送出去的封包 ip 換成
    * remember -> 把新 ip 和 舊 ip 的對應表記起來
    * replace -> 

CH4-5 IPv6
===
* 不夠啦
* 與 IPv4 不相容

* header 協定內容
    * priority -> 新增了優先順序
    * header length 固定為 40 bytes
    * TTL 改成 -> hop limit
    * next header -> 放 option
    * 沒有 checksum

* tunneling
    * 通過 IPv4 的 router 來傳送封包

CH4-6
===

### Generalized Forwarding

### SDN
* 新型網路架構
* 利用 OpenFlow 協定將路由器的控制平面（control plane）從資料平面（data plane）中分離
* 改以軟體方式實作

* OpenFlow
    * 

Quiz Answer
===
### 第六次小考題目 
**What are the header fields to identify a UDP socket and a TCP socket?**

UDP : destination IP、destination port
TCP : source IP、source port 、destination IP、destination port
>UDP：目的端IP、目的端埠號
TCP：來源端IP、來源端埠號、目的端IP、目的端埠號
>[name=前院長的中文時間][color=#f34344]

**Please describe the mechanism of packet error detection using checksum.**

傳送端傳送checksum 給接收端之後,接收端再經由計算所收到的segment做checksum,如果兩者相同則沒有錯誤,反之則有。
>傳送端傳送檢查和給接收端之後，接收端再經由計算所收到的區段做檢查和，如果兩者相同則沒有錯誤，反之則有。
>[name=前院長的中文時間][color=#f34344]

**Please calculate the checksum of the following two 16-bit binary integers: 
1110011001100110 & 1101010101010101.**
```
         1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0
         1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
=      1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1
                                      +1
=        1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0
checksum 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1
```
**Please list the network applications of UDP.**
Streaming multimedia app ( loss tolerant , rate sensitive )
DNS
SNMP
>串流媒體應用程式
>域名系統
>簡單網路管理協定
>[name=前院長的中文時間][color=#f34344]


### 第七次小考題目 
**Please describe all necessary mechanisms to recover the packets with bit errors.**

接收端收到封包,用checksum檢查bit error(位元錯誤),
若正確:回傳ACK，發送端送下一個封包
若錯誤:回傳NAK，發送端重送封包
ACK、NAK若有bit error，則直接重傳

**Please explain why one-bit sequence number is enough for a stop-and-wait protocol.** 

假設傳送端傳送出0的封包，則接收端收到此封包後只需回送序列號 1，表示下一個要接收的封包，也就是不同的封包。
而識別連續的封包是否相同，只需要0、1即可。

**What is the function of sequence numbers in feedback segments?** 

sequence number it uses to keep track of how much data it has sent.
>序列號用於追蹤已傳送的資料大小。
>[name=前院長的中文時間][color=#f34344]

**Please describe all necessary mechanisms to recover packet loss.**

發送端送出封包時會設定countdown timer，timeout發生直接重傳。
>傳送端送出封包時會設定倒數計時器，若發生逾時直接重傳。
>[name=前院長的中文時間][color=#f34344]

**The performance of the stop-and-wait protocol is poor and can be improved by a pipelining protocol. Please describe the idea of the pipelining protocol.**

允許傳送端同時傳送多個未確認封包。


### 第八次小考題目 
**Please describe the difference between Go-Back-N and Selective Repeat for packet retransmission, receiver window size, and number of timers**

Go-Back-N：重送所有未經確認的封包,buffer size = 1,只有一個timer,綁定在最早送出且未經確認的封包,即base。

Selective Repeat:只重送遺失或損毀的封包,buffer size = sender’s buffer size,每一個封包都有綁timer。

>回溯 N：重送所有未經確認的封包，接收端暫存大小 = 1，只有一個計時器，綁定在最早送出且未經確認的封包。
>選擇性重複：只重送遺失或損毀的封包，接收端暫存大小 = 傳送端暫存大小，每一個封包都有綁計時器。
>[name=前院長的中文時間][color=#f34344]

**How many sequence numbers are required for selective repeat? (window size=W)**

2W

**Please describe the problems caused by improper timeout values.**

timeout values設定太大時,當檔案遺失真的發生,會花較久的時間修復。
若設定太小,容易使延遲被判斷為timeout,而有許多不必要之重傳。

>逾時數值設定太大時，當檔案遺失真的發生，會花較久的時間修復。
若設定太小，容易使延遲被判斷為逾時，而有許多不必要之重傳。
>[name=前院長的中文時間][color=#f34344]

**Please introduce the basic idea of calculating TCP timeout value.**

EstimatedRTT = (1-α)*EstimatedRTT + α*SampleRTT 
α=0.125

DevRTT = (1-β)*DevRTT + β*|SampleRTT-EstimatedRTT| 
β=0.25

TimeoutInterval = EstimatedRTT + 4*DevRTT

**Please describe the procedure of TCP delayed ACK in TCP receivers.**

Wait up to 500ms for next segment. If no next segment, send ACK

>於下個區段前等待500ms，若未收到新的區段，重傳ACK。
>[name=前院長的中文時間][color=#f34344]


**Please describe the idea of TCP Fast Retransmit.**

如果接收了三個連續ACK，則重傳，不用等timeout
>當接收到 3 個 重複的 ACK，則立即重送該區段，而非等到重送計時器逾時。
>[name=前院長的中文時間][color=#f34344]


### 第九次小考題目 
**TCP flow control can avoid receiver buffer overflows. Please describe its procedure.**

利用rwnd (reciever window size) 如果rwnd=0代表buffer full
>偵測接收端窗格大小，若其為 0，代表暫存已滿。
>[name=前院長的中文時間][color=#f34344]

**TCP uses three-way handshake for connection setup. Why is two-way handshake not used?** 

因為two way在packet loss 和delay 時會造成另一端以為建立新連線，導致一端終止一端開啟的情況。
>因為雙向交握在封包延遲或遺失時，會造成另一端以為建立新連線，導致一端終止一端開啟的情況。
>[name=前院長的中文時間][color=#f34344]

**Please describe the four-way handshake of closing a TCP connection.** 

FINbit=1, seq=x
ACKbit=1; ACKnum=x+1
FINbit=1, seq=y
ACKbit=1; ACKnum=y+1
![](https://i.imgur.com/b26eun4.png)

**Please describe how TCP slowstart phase adjusts CWND value.** 

初始CWND=1MSS,之後都將CWND加倍, done by incrementing cwnd for every ACK received

>初始CWND(壅塞視窗)為1MSS，接著在每次收到ACK時將CWND加倍。
>[name=前院長的中文時間][color=#f34344]

**Please describe the idea of AIMD (additive increase; multiplicative decrease)in TCP for adjusting CWND.**

若有正確收到封包，CWND在每個 RTT 的時間內都呈線性成長，即CWND = CWND + 1MSS。
若有封包遺失疑慮，將CWND調整成一半。


### 第十次小考題目 
**Please describe the functions of data plane and control plane in each router.** 

Data plane:接收封包後 決定要去哪個output port
Control plane:決定封包在端點間的移動路徑
>資料層：接收封包後決定要去哪個輸出端口。
控制層：決定封包在端點間的移動路徑。
>[name=前院長的中文時間][color=#f34344]

**Please describe the problem of Head-of-the-line (HOL) blocking.** 

quening delay and loss due to buffer overflow
>因為暫存溢出而導致封包佇列延遲或遺失。
>[name=前院長的中文時間][color=#f34344]

**Please explain longest prefix matching.** 

find the longest matching entry in the table and forwards the packet to link associated with longest prefix number
>找到子網掩碼長度最長的封包－路由表中，與目的地址的高位匹配得最多的表項。
>[name=前院長的中文時間][color=#f34344]
>子網掩碼 = 子網路遮罩
>[name=]

**Please describe three types of switching fabrics.** 

memory : packet copied to system's memory
bus : datagram from input port memory to output port memory via a shared bus
crossbar : banyan networks, crossbar, other interconnection nets initially developed to connect processors in multiprocessor 
>記憶體：直接將封包複製到適當輸出埠記憶體中。
匯流排：透過共用匯流排直接將封包傳輸到輸出埠。
棋盤式交換器：封包會沿著連接到該輸入埠的水平匯流排移動，前往其目標輸出埠的垂直匯流排。
>[name=前院長的中文時間][color=#f34344]

**Please describe the purpose of input-port queueing.**

如果交換機構有 input port 封包，被攔截的封包放入quene中等待
>

### 第十一次小考題目 
**Please describe the reasoning of IP fragmentation and the related header fields.**

因為在network裡有HTU限制
Id : 辨別是否屬於同一封包
Flags : 是否最後的fragment 
Fragments offset : 記錄該區段屬於原始的哪段資源
>因為每個網路連結有最大傳輸單位(MTU)限制封包長度
>ID：識別碼，判斷各區段是否為同一封包。
>Flags：封包切割旗標，判斷本封包可否切割、本區段是否為末尾。
>Fragments offset：區段位移，判斷區段屬於原始封包的哪一段資料。
>[name=前院長的中文時間][color=#f34344]

**Please describe the functions of Time to Live and Upper Layer fields in IPv4 header.**

(1) Time to Live：表示一個封包的存活時間，當資料每經過一個路由器時都會減一，當TTL歸零時則丟棄此封包，並回送ICMP Exceeded message 給發送端。

(2) Upper Layer(Protocol)：定義在data portion中IP datagram使用的協議
>(1) 存活時間：表示一個封包的存活時間，當資料每經過一個路由器時都會減一，當TTL歸零時則丟棄此封包(並回送溢時傳輸給傳送端)。
>
>(2) 上層協定：記錄封包在傳輸層所使用的網路協定為何。
>[name=前院長的中文時間][color=#f34344]

**What is CIDR?**

一個運用VLSM(variable-length subnet masking)分配IP位址以及在網路上有效路由IP封包的方法。
>CIDR 無類別域間路由
>VLSM 變動長度子網路遮罩
>[name=前院長的中文時間][color=#f34344]

**Please describe several scheduling mechanisms for output ports of a router.** 

- tail drop: drop arriving packet
- priority: drop/remove on priority basis 
- random: drop/remove randomly
>去尾：丟棄到達封包。
>優先度：根據優先偏好丟棄封包。
>隨機：隨機丟棄封包。
>[name=前院長的中文時間][color=#f34344]

**Each IP address is comprised of two parts. Please name them.**

- subnet part - high order bits 
- host part - low order bits 
>子網部分：高位元
>主機部分：低位元
>[name=前院長的中文時間][color=#f34344]

### 第十二次小考題目 
**NAT modifies the headers of both outgoing and incoming packets. Please list 
these headers.** 

Outgoing：來源端地址
Incoming：目的端地址

**Please describe the information stored in a NAT translation table.**

WAN address 與LAN address 的mapping
>廣域網地址對應區域網地址。
>[name=前院長的中文時間][color=#f34344]

**Please list the benefits and drawbacks of using NATs.** 

- range of addresses not needed from ISP: just one IP address for all devices 
- can change addresses of devices in local network without notifying outside world
- can change ISP without changing addresses of devices in local network 
- devices inside local net not explicitly addressable, visible by outside world
>優點：
>1. 所有設備只需一個IP地址
>2. 可以在不通知外界的情況下更改本地網絡中設備的地址
>3. 可以在不更改本地網絡中設備地址的情況下更改ISP
>4. 本地網內的設備無法明確尋址，外界不可見
>
>缺點：
>1. 增加路徑轉換的延遲
>2. 失去對IP來源的可追溯性
>3. 導致某些應用程式的通訊失敗
>
>挑幾點寫應該就夠了……建議是只記第一和最後
>[name=前院長的中文時間][color=#f34344]

**Please describe the idea of route aggregation**. 

Route aggregation（路由匯總）的主要想法便是要將多筆路由資訊匯總成比較簡單的單筆路由資訊。

**Why must routers perform longest prefix matching to ensure the correctness of packet routing?** 

使用這個法則才能正確回復新的ISP而不會回復到舊的
##### From 李平一

Reference
===

- 宅學習：https://sls.weco.net/CollectiveNote20/Network
- NotFalse 技術客：https://notfalse.net/category/tcp-ip
- Oblivion：http://pollucite.blog126.fc2.com/blog-category-9.html
- IP 實驗：http://opencourse.ndhu.edu.tw/pluginfile.php/806/mod_resource/content/0/course_files/Exp3_IP.pdf