# Computer Networking

### Terminology

- ACK Acknowledgement 確認
- NAK Negative-Acknowledgment 否定
- WND Window
- FIN Finish
- RSV Reserved
- PSH Push
- RST Reset
- SYN Synchronous
- PTCL Protocol
- MSS Maximum Segment Size
- MTU Maximum Transfer Size
- PMTU Path MTU
- RWND Receiver Window Size
- CWND Congestion Window
- SSTHRESH Slow Start Threshold
- Overhead 開銷、代價
- Repeater 中繼器
- Coaxial Cable 同軸電纜
- HFC Hybrid Fiber Coaxial 混合光纖同軸網路
- TDMA Time Division Multiple Access 分時多工
- FDMA Frequency Division Multiple Access 分頻多工
- CDMA Code Division Multiple Access
- CSMA
- AP Access Point
- FTP File Transfer Protocol
- FQDN Fully Qualified Domain Name
- ADSL Asymmetric Digital Subscriber Line
- SDSL Symmetric Digital Subscriber Line
- ISP Internet Servier Providor
- ARP Address Resolution Protocol
- ICMP lnternet Control Message Protocol
- DSL Digital Subscriber Line
- PDU Protocol Data Unit
- TCP Transmission Control Protocol
- UDP User Datagram Protocol
- SMTP Simple Mail Transfer Protocol
- TLD Top Level Domain
- TTL Time To Live
- POP3 Post Office Protocol
- DHCP Dynamic Host Configuration Protocol
- DASH Dynamic, Adaptive Streaming over HTTP
- NAT Network Address Translation
- ARP Address Resolution Protocol
- RIP Routing Information Protocol
- OSPF Open Shortest Path First
- IGRP Interior Gateway Routing Protocol
- BGP Border Gateway Protocol
- Flooding 洪泛
- Carrier Wave 載波
- Simplex 單工
- Full Duplex 全雙工
- Half Duplex 半雙工
- CRC Cyclic Redundancy Check
- NIC Network Iterface Card 網路卡
- CIDR Classless Inter-Domain Routing 無等級（Classless） IP 劃分
- SNMP Simple Network Management Protocol
- AS Autonomous System

### Difference between Network Core and Network Edge

- Network Core：主要由路由器聚集在一起，功能在於實現高速傳輸和路由，處理大量的網路流量，負責將數據從 Src 傳到 Dest，具有高 Bandwidth、低延遲、高可用性的特性
- Network Edge：指網路的使用者，包含手機、PC、公司的 Server 等等，提供其他用戶相關的 Service

### Delay

- 網路 Delay 的組成：
- Nodal Processing Delay：Router 處理 Packet Header、檢查位元資料錯誤與尋找配送路徑等所花費的時間，相對於其他 Delay 相當短
- Queueing Delay：Packet 因為 Router 無法及時處理而被 Queue 住的時間
- Transmission Delay：網路卡將資料傳送到網路線上或從網路線上接收所花的時間，與網路設備的傳送速度有關
- Propagation Delay：封包在物理網路線上傳輸所花費的時間，與網路線上電子訊號跑的速度有關，這個時間就是距離除以訊號傳送速度所得到的數值，假設傳送距離為 d ，傳輸的速率為 s ，那麼 Propagation Delay 就是 d/s

Queueing Intensity 的計算：
定義流量與消化量的比值：La/R，L 代表平均封包的長度，a 代表平均單位時間有多少封包傳入，La 代表每秒進來的 bit 量，R 代表路由器平均能消化多少流量，根據排隊理論，對於一個路由器，每個封包傳送進來的間隔時間是個隨機變數，但這其中仍有個平均值，如果平均傳入的量除以能消化的量接近 1，代表等待延遲接近無限，反之越靠近 0 就越不會有 Queuing Delay

### Five Layer

- 應用層：使用者真正與電腦溝通的點，例如 FTP、HTTP、HTTPS、SSH 等等，目的是為了提供使用者多樣有用的服務
- 傳輸層：包含 TCP 以及 UDP，決定溝通的方式是傳了就不管還是會相互確認，目的在於可使資料可靠地傳到特定的 Port
- 網路層：決定 Packet 傳輸的路徑選擇，包含 IP 資訊，目的在於將 Source 的 Packet 傳到 Dest，但會因為各種原因可能沒傳成功
- 資料鏈結層：網路中相鄰網路節點間傳輸資料的協定層，目的在於提供流量控制、錯誤檢測等功能，以及對上層提供實體層抽象，隱藏實體層的複雜性
- 實體層：規定了實體線路的規格、電壓，或無線電波的頻率等等，目的在於確保資料可

### Difference between Throughput and Bandwith

- Bandwidth：指線路在單位時間下最大能夠傳輸的資料量
- Throughput：發送端到接收端之間在單位時間下實際能夠傳輸的量

一個是指實際上，一個是指理論上最大值，且還關乎以甚麼視角來看，例如你家有三個人同時在用電腦，家裡網路是 30 Mbps，這是頻寬，但因為同時有三個人在用，導致你實際使用只有 10 Mbps，對你個人來說，你的 Throughput 就是 10Mbps，因為這是"實際單位時間下能夠傳輸的量"

### Difference Between Packet Switching, Message Switching and Circuit Switching

- Packet Switching：先將要傳遞的訊息分成許多小 packet，再依照 packet 所指定的 Dest 位址來決定傳輸路徑，傳送到目的地後再重新組合
- 優點：頻寬得到最大的利用
- 缺點：封包只管傳遞給下一個節點，且各封包走的路徑可以不同，故不會按順序送達，接收端需花時間重整資料
- Message Switching：可視線路的忙碌狀況選擇不同的路徑來傳送資料，不用建立專用線路，其中傳遞的資料包含來源位址與目的地位址，網路中間裝置會將訊息先儲存再傳送出去
- 優點：每個節點都會檢查資料是否完整，可降低傳輸的錯誤率，整體線路的使用率提升
- 缺點：當傳輸的資料量龐大時，會長時間佔用所選擇的傳輸路徑，造成該段線路出現壅塞情形
- Circuit Switching：在 End-End 之間建立實體線路連線，一旦建立兩端之間的連線後，佔用線路並傳輸資料，因此占用期間其他人無法使用，直到通信結束之後，這條專用路徑才停止使用，並讓出供他人繼續使用，電話就是如此運作
- 優點：速度快、延遲小，不會產生線路衝突，錯誤率低
- 缺點：需等待傳輸完成才會釋放線路，容易佔線而浪費資源

### Persistent HTTP and Non-Persistent HTTP

- Persistent：多個 Object 可以在單一個 TCP 連線中傳輸
- Non-Persistent：一個 TCP 只能傳一個 Object，然後連線就中斷，如要多個 Object 就需要多次重新建立 TCP 連線

Example：
一個 HTML 檔案且內嵌 30 張圖片，則需要多少次 RTT?（每個 RTT 加上檔案傳輸可能彼此長度不同，但在此情況先忽視，僅單純看 RTT 的次數）

1. Non-Persistent Connection Without Parallel Connection
2. Non-persistent Connection With 10 Parallel Connection
3. Persistent Connection Without Pipelining
4. Persistent Connection With Pipelining

Solution：
1. 2RTT + 2 * 30RTT = 62RTT
2. 2RTT + 2 * (30/10)RTT = 8RTT
3. 2RTT + 1 * 30RTT = 32RTT
4. 2RTT + 1RTT = 3RTT

註：Pipelining 與 Parallel 的差異在於 Parallel 是利用多個 Thread 開多個 TCP Connection 連，Object 都走不同的 TCP Connection，而沒有改善 HTTP 1.0 規格本身的缺陷，但 Pipeling 則是從規格下手，讓所有人都允許在一個 TCP 中一次傳多個 Object

### What is PDU?
Network Protocol 由許多 Layer 組成，每一層所使用的資料結構則統稱為 PDU，其中包含了控制與位址資訊的 Header，與實際乘載的資料，以下是各層的 PDU 的名稱

- Transport Layer：Segment For TCP, Datagram For UDP
- Network Layer：Packet
- Data Link Layer：Frame
- Physical Layer：Bit or More Generally, Symbol

### How to Calculate Delay
有 N 個封包，從 Src 到 Dest 中間經過 M 條線路，每個封包的長度為 L，傳輸速度r皆為 R，試問全部傳到最終的 Router 所需的 Delay 為何

$(M+1)\frac{L}{R}+(N-1)\frac{L}{R}$

$(M+1)\frac{L}{R}$ 代表第一個 Packet 傳到目的地所需的時間，$M+1$ 代表 Src 與 Dest 中間的線路的數量，而 $(N-1)\frac{L}{R}$ 的 $N-1$ 代表第一個 Packet 到達目的地後，後面會接著剩下的 Packet

### Why We Need Port and IP
IP 可以辨認主機是哪台，但主機上仍有多個 Process，例如有些是跑遊戲，有些跑影片，但這個 Packet 要傳給哪個 Process 我們無法得知，因此才需要 Port 來辨認、知道傳給哪個 Process

### Difference Between IMAP and POP3

- POP3：舉例來說，我們在電腦上安裝 Outlook，並設定 POP3 收信，當電腦連上網、Outlook 連上主機後，Outlook 會把 Server 上的信件下載到電腦上，如果 Outlook 沒有特別設定，Outlook 不會將 Server 上的郵件刪除，如果我們也用手機上的 Outlook App 收信，相同的郵件會再被下載一份到手機上，如果在電腦上刪除該信件，手機上的郵件仍不被刪除
- IMAP：IMAP 會同步電腦和 Server 上的郵件

POP3 和 IMAP 的優缺點比較：

- IMAP 適合同步不同手機電腦
- IMAP 較占佔 Server 空間
- POP3 較不占 Server 空間，但占 Local 空間

### Difference Between Recursive Query and Iterative Query about DNS


頂層的 DNS 採用 Iterative Query，否則只要數量一多，DNS Root Server 就要承受過大的流量

### DNS and Domain Name

www.google.com
- .com 稱作頂級域名
- google.com 稱作一級域名
- www.google.com 稱作二級域名

TLD 是由域名管理機構定義的，我們只能從中選一個使用，常用的包含：
- ccTLDs：Country Code Top-Level Domains，國家和地區頂級域名，例如 tw cn jp
- gTLDs：Generic Top-Level Domains，通域頂級域名，例如 com net org
- New gTLD：New General Top-Level Domains，新通用頂級域名，例如 top red men

而購買域名，實際上就是選中某個頂級域名以後，在這個頂級域名下面自定義一個一級域名的名稱，然後租用它

一級域名以下的二級域名，像是 www.google.com 甚至三級、四級域名的取名和指向的 IP，都是域名所有者透過域名管理中的 DNS 解析來自行設定

Root DNS Server：只儲存各個 TLD 的 DNS Server 的 IP，邏輯上全球只有十三台，用途就是把查詢細節委託分工給各個 Top-Level Server
TDL Server：　
Authoritative DNS Server：有被授權、實際上要去管理的 DNS Server，
Local DNS Server：嚴格來說不一定被算在 DNS Hierarchy 中，該機台每個 ISP 會在各個區域內放置一個，行為與 Proxy 一致，當有 DNS 查詢請求時，先看 Local DNS Server 有沒有，Hit 的話就回傳，Miss 的話再到真正的 DNS Hierarchy 中尋找

# Transport Layer

### RDT

實體傳輸時會遇到兩種情況：
- 傳輸時 Bit 發生翻轉，產生 Error
- 傳輸時封包在中途遺失
以下將使用遞進的方式增加約束條件，將 RDT 步步升級，不過 TCP 並不等於 RDT，但是有使用到 RDT 的概念，且 RDT 只能從 Sender 到 Receiver 單向傳輸，還不能雙向溝通

### RDT 1.0

假設實體通道是完全可靠的，在這種情況下只要傳輸就保證收到，也保證無誤，因此可以儘管丟即可，此時封包中不用有 Check Sum 的資訊

### RDT 2.0

假設實體通道可能會有 Error Bit，但仍保證不會丟失封包，在這種情況下 Sender 只要傳輸就保證收到，但可能有誤，因此 Receiver 也要回傳封包說明自己也無誤，如果 Receiver 收到封包後發現 Check Sum 不合法，代表中間有 Error，回傳 NAK，反之如果 Check Sum 合法，代表中間"可能有或沒有" Error，回傳 ACK

註：即使回傳 ACK 可能還是仍然有 Error，有極小的機率一次錯多個 Bit，但又加總仍是合法的 Check Sum，所以才會說"可能有或沒有" Error，重要的是：Check Sum 無法處理多個 Bit 都錯誤的情況，不過雖然說實際上是錯誤，但因為錯太多也分辨不出來，且這種情況發生的機率極低，所以我們會把 ACK 它當成 100% 正確，假設 Check Sum 會完美檢查傳輸中是否有 Error

以下機制是 Stop and Wait，即傳輸後就等待，直到有回應，才進行下一個動作


相比 RDT 1.0，我們要有 Check Sum 檢查是否有 Error，並且還要回傳 ACK、NAK 給 Sender，如此它才能知道我們之間的傳輸是成功的，但其實 Receiver 回傳的時候，回傳訊息也有可能在中途出錯，可能原本 ACK 變成 NAK、NAK 變成 ACK，注意此時封包還是不會掉的

### RDT 2.1

但 RDT 2.0 的情況仍是錯誤的，因為回傳的 ACK、NAK 訊息仍然有可能是 Corrupt 的，因為訊息的確有可能在線路上發生 Flip Bit

回傳訊息共有以下幾種情況，並且有各對應處理的方式：
- 回傳訊息 Corrupt，不論訊息為 ACK 或 NAK：重傳
- 回傳訊息 Not Corrupt，且訊息為 NAK：重傳
- 回傳訊息 Not Corrupt，且訊息為 ACK：傳輸成功，傳輸下一條訊息

判斷依據：
- 回傳訊息 Corrupt，則整個訊息都不可信，實際上是 NAK/ACK 都不知道，但為防止回傳 NAK 結果 Receiver 沒能夠得到重傳，因此只要 Corrupt 就一定要重傳，如果真實情況是有 Error，那麼回傳剛剛好，如果真實情況是 ACK，那麼回傳就導致一樣的資料被傳送兩次
- 回傳訊息 Not Corrupt，且訊息為 NAK，正確地告訴我們中間有錯，重傳一次即可
- 回傳訊息 Not Corrupt，且訊息為 ACK，正確地告訴我們傳輸成功，直接傳輸下一條訊息即可

由此可知，只要回傳訊息帶有 NAK，在封包必定能 100% 傳輸到的情況下，是一定能夠得到回傳的，但會發生一種情況：如果回傳訊息 Corrupt，就必須要重傳，但實際上我們前一次已經成功的傳輸過去，現在又重傳一次，Receiver 無從分辨是否是重傳還是已經是新的封包，該怎麼處理？

答案是用一個 Sequence Number 欄位去分辨它，Sender 如果發現需要回傳，Sequence Number 保持一樣，如果傳輸成功，要傳輸下一個的時候，則 Sequence 要增加，但因為目前是 Stop and Wait 模式，因此只需要 0, 1, 0, 1 切換即可（當然如果想要讓 Sequence Number 是累加的也是可以）

Sender：
Receiver：

### RDT 2.2

2.2 版是在 2.1 上的基礎之上做了改善，摒棄了 NAK，只需採用 ACK，現在假設 Sender 發送 0 號 Packet，如果 Receiver 成功接收到 0 號 Packet，就返回（ACK，0），代表 Receiver 已經成功收到 0 號 Pack，而後 Sender 就接著發送 1 號 Packet，如果 Receiver 接收到 0 號封包發生錯誤，回傳（ACK，1），Sender 則重傳 0 號 Packet，因為 Sequence Number 與送出的值不一樣

總之如果回傳的 Sequence Number 與原本 Sender 傳出去的不一樣，就代表失敗，所以要你重傳一次，反之代表成功，會把 Sequence Number 增加（Stop and Wait 下即 0, 1 翻轉）

### RDT 3.0

假設實體通道可能會有 Error Bit，且可能會丟失封包，此時封包可能根本不會回傳到，無從得知 Receiver 的任何訊息，因此只要隔一段時間沒有任何封包傳回，就再傳一次，但傳輸可能是有延遲的，甚至可能你以為封包 Loss 但只是卡住，結果又重傳一次，造成傳兩次的問題，但這問題 RDT 2.1 已經解決，所以沒問題

如果要求傳送訊息，則送出訊息，並且進入等待回復的狀態

如果回傳的訊息有壞掉，或沒壞掉但回傳 NAK，原則上是要回傳的，但此時從簡處理，選擇甚麼都不做，等到 time out 再執行回傳並重置時間，這麼做只是為了簡化難度，但效率極差

如果回傳的訊息沒壞掉且為 ACK，則停止 timer，並且進入等待下一個要送的 packet 的狀態

此外，由於可能傳出去的封包比較晚到，導致發送了多個同樣的 packet 出去，而 Receiver 收到多次後也回傳了多次 ACK，使 Sender 也可能收到多次的回傳，但在第一次 ACK 成功而轉換到下一個狀態以後，之後的回傳都要忽略，因此才有 Delayed ACKs Ignore Them 的部分


### Performance with Stop and Wait、Pipeline

如果用 Stop and Wait，效率會很低，假設 Link 速度為 1Gbps，Packet 大小為 1 Mb，且 end-end 傳輸的 delay 為 15ms，則使用率為：transmition time/(transmition time + idle time)= (1M/1G)/(0.03 + 1M/1G) = 0.001 / 0.031（此計算忽略回傳 ACK 所需回傳的資料量，假設為 0）

改用 Pipeline 以後，假設 Link 速度、Packet 大小、Delay 保持一樣，但同時有 3 個封包在傳，則結果變成 (3M/1G)/(0.03 + 1M/1G) =


另外，Pipeline 也不能無限制的瘋狂傳，因為 Receiver 接收到後會先放到 Buffer 內暫存，如果無限制的一直傳，很有可能導致 Receiver 的 Buffer 爆掉而要一直重傳

### GBN Go-Back-N

又稱做 Slide Window Protocol，N 代表 Window 的寬度，也代表 Pipeline 裡面最多同時有多少個封包，採用 Accumulative ACK，而 Receiver 回傳 (ACK, n) 的時候，回傳的 n 代表 Receiver 期望收到的封包編號



Sender：
如果上面要求傳送，先看是否超過 Window，即 nextseqnum < base + N，nextsequnum 代表已經傳出去但還沒收到 Ack 的封包序號，如果在範圍內就傳送，確定傳送以後，還要看是否是 base == nextseqnum，是的話代表要 start_timer

Sender 會有一個給最老（編號最小）、還沒 Acked 的 Packet Timer，如果 Time Out，則從 base 到 nextseqnum - 1 都再傳一次

如果收到回傳，是沒壞掉的，就更新 base，讓它移動一格，且如果 base 還未接觸到 nextseqnum，則代表 window 內仍有訊息送出但未獲得回覆，因此要重新計算 timer，但如果已經碰到 nextseqnum，則代表已經沒有要傳的訊息，則停止 timer

如果收到回傳，是已經壞掉，則不做任何事情，當作從來都沒收到，等到 timeout 再回傳

Receiver：
Sender 端有 Buffer，但 Receiver 端沒有，且 Packet 只按照順序收，如果順序不對則都丟棄，例如收到 Sequence Number 為 1, 2, 3, 7, 8，則 7, 8 丟棄，並且回傳目前最高的 Accumulate ACK 的值，而 Sender 收到回傳後，會把 Base 設為回傳的 ACK 的值 +1（相當於滑動了一次 Window），而下一輪重傳就會從這裡開始

如果 Receiver 端得到的 Packet 壞掉了，那麼就不回傳，當作沒看到、從來沒收到，使封包壞掉的問題與 Loss Packet 的問題同時以同樣的方式解決

實際上的運作圖：
註 1：圖中有畫錯，紅色的才是對的
註 2：在實際的 TCP 之中，(ACK, n) 的 n 則是代表期望的下一個的編號，也就是說代表 n - 1 之前的都已送達，會這麼做的原因在於如果 Send Pkt0 的連線斷掉，但 Send Pkt1 送達，如果是採用原本 GBN 的做法回傳不知道要送甚麼，但如果採用回傳"期望收到的編號"，就不會有問題，回傳 Ack0
註 3：Dulplcate ACK 表示收到回傳的封包的 ACK 編號連續一模一樣的次數，如果連續收到 ACK5 四次，那麼是 Duplicate ACK 發生三次

### Selective Repeat

GBN 的缺點是，如果某個封包沒送到，可能連帶後面的都會跟著要重送，即使已經確定送到了也一樣，而 Selective Repeat 則是其改進，只重送沒送到的，Receiver 會獨立地回傳各個封包是否 Acked，Sender 會給每個 Packet 各自的 Timer，當 Time Out 則只回傳特定的 Packet


Sender：
送出後回傳 ACK 且沒壞掉的話，會 Buffer 住 ACK 紀錄，代表說對方確實有收到這些 Packet，並且檢查是否是 base + 1 的 ACK，是的話就推進 Window

送出後回傳的 ACK 壞掉的話，就當作從來沒收到，直接無視

而如果 time out 到都沒回傳，就把這個 timer 所屬的 Packet 重傳、重新開始一次 timer

Receiver：
收到哪個，就 ACK 哪個封包的 Sequence Number，且如果傳過來的 Packet 是期望得到的（即未送達之中最小的 Sequence Number），便會直接往上傳、Window 移動一格，而如果不是期望的，則把該 Packet Buffer 住，直到中間跳過的 Packet 補上，此時 Window 會一次移動多格


### Dilemma

不論 GBN 還是 Selective Repeat 都會有以下問題：待補

Sequence Number 的數量至少要 Windows 的兩倍

### Difference Between Selective Repeat and GBN

- GBN 的 Receiver 不需要額外的 Buffer，但 Selective Repeat 需要，有 Buffer 的優點在於即使中間有跳號，已收到封包依然會暫存住，而不需要 Sender 重傳，因此 Selective Repeat 效率比 GBN 好
- GBN 的 Sender 只有一個 Timer，但是 Selective Repeat 的每個封包都有一個獨立的 Timer
- GBN 的 Base 隨著 ACK 的回傳，一次只會加 1，但 Selective Repeat 可能會有一次加很多的情況，也就是說它會跳

### How to Choose Time Out

如果 Time Out 太長：Segment Loss 以後反應太慢，使用效率低
如果 Time Out 太短：可能不小心重傳太多次，因為對方明明有收到，但因為 RTT 較長，而來不及傳回來

因此好的做法是：讓限制的 Time Out 隨著 RTT 變化，而這個參考的 RTT 值，就用歷史紀錄，以指數平滑法（Exponential Weighted Moving Average）的方式計算出來（假設 RTT 的時間是常態分布，並且在四個標準差以上的範圍都直接當成 Packet 真的 Loss）

預估的 RTT 平均值：
$\text{EstimatedRTT}_t = (1-\alpha)*\text{EstimatedRTT}_{t-1} + \alpha*\text{SampleRTT}$
預估的 RTT 標準差：
$\text{DeviationRTT}_t = (1-\beta)*\text{DeviationRTT}_{t-1} + \beta*|\text{SampledRTT}-\text{EstimatedRTT}_{t-1}|$
實際上設定的 Time Out：
$\text{Time Out Interval} = \text{EstimatedRTT} + 4 * \text{Deviation}$

通常來說，$\alpha = 0.125, \beta = 0.25$，但實際上並沒有嚴格規定

# TCP

### TCP Overview


TCP 重傳的時機：
- Time Out
- Duplicated Acked
- 註 1：雙方都各自擁有一個 Timer，且只有在當 Sender 的時候才會有用
- 註 2：TCP 的算法其實類似 GBN 與 Selective Repeat 的融合體，像 GBN 的地方是TCP 使用 Cumulative Ack，像 Selective Repeat 的地方是 TCP Receiver 有用 Buffer 把亂序的封包先暫存，然後只重傳丟失的封包
- 註 3：TCP 的 Sequence Number 起始值是隨機決定的，但為甚麼呢？這是由於資安考量，因為如果 Seq 固定從 0 開始

### Fast Retransmit

如果多次收到的 ACK Number 都長得一樣，連續多次後就會馬上回傳，不用等到 Time Out

### Difference Between Flow Control and Congetion Control

- Flow Control：避免發送端癱瘓接收端，即發送端丟出太多東西導致接收端無法消化
- Congetion Control：避免發送端癱瘓網路，即發送出去結果路由器無法消化，導致 Queuing Delay 過高

註：TCP Header 中的 Windows Size 是指對方的 Buffer 剩餘大小，即 rwnd，以限制我方的傳輸量，避免把對方的 Buffer 撐爆，而不包含 cwnd 的資訊

### Window

TCP Window 是指無需等待 ACK 就可以持續發送 Data 的最大值，在 TCP 中規定最大值為 65535（可透過 Options 擴大的 1GB），而實際上 TCP Winodw 的大小由兩個數值決定：Flow Control 提供的 rwnd 以及 Congetion Control 提供的 cwnd，取兩者的最小值做為實際的 Window Size

### Flow Control


- RcvBuffer：Receiver OS 提供給該 TCP 連線的空間，默認提供是 4096 KB，但 OS 可能會自動調整大小
- Rwnd Receiver Window：Receiver Buffer 中剩下還能使用的 Buffer 量

TCP 的發送視窗大小，由接收端來決定，每次回報 ACK 時，皆會告知傳送端 Rwnd 剩下的大小，使傳送端在丟出資料時會控制丟出的資料量

Receiver 有一定大小的 Buffer，如果傳太多東西讓 Buffer 都塞不下，那等於是無用功，因為資料都溢出消失了，因此透過 Flow Control 可以告訴 Sender 傳輸量需要少一點

實際上 Flow Control 仍不能保證不會爆 Buffer，假設 Receiver 回送告訴 Sender 剩下 100 Byte 的空間，但回送通知要 0.1 秒後才會到，但 Sender 在這 0.1 的通知延遲時間內可能早就又已經送出 200 Byte 了

### Congestion Control

利用 Packet 是否 Time Out 或 Retransmission 來去預測是否網路中發生塞車了，通常 Time Out 就代表 Packet Loss 了，這可能就代表雍塞嚴重，而如果發生 Fast Retransmission 則代表輕度壅塞，因為只有其中一個 Packet Loss，後續的都還是有傳到並且 ACK

但事實上，Packet Loss 不代表一定是網路雍塞導致 Queueing 的時候 Overflow，也可能是傳輸的時候正好發生 Error，而實際上網路本身還是通暢的，這種 Loss Based 的方式是有假設"Packet Loss 與雍塞成正相關"

此外，Congestion Control 中，使用的單位不是 Byte，而是 MSS，實務上乙太網路的話，TCP 的 MSS 通常為 1460 Byte，但為何是這個值呢？MSS 的值通常是 MTU - 20（IP Header Length） - 20（TCP Header）得到的值，這麼做是為了防止在 Network Layer 做 IP Fragmentation

### AIMD

成長速度是線性

### Slow Start

每次送出後得到 ACK 就會將 Cwnd 增加 1，成長速度是指數級

### Timeout and Duplicate Ack

Cwnd 有 Slow Start 以及 AIMD 兩種成長方式，一種較激進，一種較平緩，我們希望一剛開始先激進些，直到一定量後再平緩地增加，因此我們定義了一個 ssthreshold 作為分界，ssthreshold 以下使用 Slow Start，超過則以 AIMD，這段 AIMD 的過程這又稱作做 Congestion Avoidance，而如果發生 Time Out，代表雍塞嚴重，因此 ssthreshold 減為當前 Cwnd 的一半，然後新的 Cwnd 回到 1

而如果是 3 Times Duplicate Ack，則又分為以下兩種算法：

- Tahoe：3 Times Duplicate Ack 發生後代表輕度雍塞，ssthreshold 減半， cwnd 回到 1 開始，重新回到 Slow Start 的階段
- Reno：Tahoe 的改進版，在 3 Times Duplicate Ack 發生後，ssthreshold 一樣砍半，但是 cwnd 設為從新的 ssthreshold 開始（也有的實作是 ssthreshold + 3），因此會直接進入線性成長的狀態，這叫做 Fast Recovery，直接進入線性增長的狀態而不是 Slow Start

註：Tahoe 與 Reno 源自於一座湖以及一座城市的名稱


### TCP Fairness

希望多個 TCP 能夠共享頻寬，不會有人貪心全占走



### Hand Shake

在傳輸之前，雙方要經過溝通，剛開始時，其中一方會 Request Conntection，而另一方收到後馬上變成 ESTAB 狀態，即已經建立完成，並且回傳給原本的那一方，並且附帶自己已經準備好的訊息，而原方也會回傳


為甚麼只有兩次揮手？如果只有兩次揮手，那麼原方送給另一方以後，另一方送回後，卻沒得到回傳，就無法確認原方是否也建立了連線

這會造成以下問題：
- 延遲太高導致重複開啟連線：

注意兩邊連線都進入 Establish 的時間都是在收到 ACK 的時候

### What is Piggy Back

Piggy Back 是一種延遲傳出 Ack，並將下一個要送的資料附加這個 Packet 的技術，當 Packet 到達 Peer 時，Peer 會等待並且不會立即 Ack，而是等待一小段時間，如果正好有資料 Peer 也要傳給我們，就會連帶 Ack 的資訊包成同一個 Packet 回送過來

Piggy Back 的優點：
- 有效利用 Bandwidth，總體來說因為共用同一個 Header 而減少了一些 Overhead，可把更多頻寬給其他需要人
- 資料傳輸延遲得到些許改善，因為所需傳出的資料量減少，那麼傳出的 Packet 也當然減少，可減少些許的 Queuing Delay

Piggy Back 的缺點：
- Ack 的傳輸可能會有延遲，太長的話可能導致重傳
- 實作上較複雜些
- 不適用於所有場景，如果只是單方面的傳輸，Piggyback 就顯得沒必要，因為 Peer 此時扮演的角色是 Receiver，不需要回傳 Data，只要保持回覆 Ack 即可

### TCP Delay Modeling

送出 Request 後，要多久才會收到從伺服器回來的資料？

以下 Delay Model 假設：
- Slow Start
- 考量 TCP Established
- 有 Transmission Delay
- 忽略 Retransmission（No Loss, No Corruption）
- 固定的 Congestion Window

符號：
- S：MSS size（Unit：bit）
- O：Object size（Unit：bit）
- W：Congestion Windos Size（Unit：MSS）
- R：Transmission Rate
- K：Window 分幾段傳送，這幾段傳送間會有 Idle
- Q：假設 O 無限大，會產生的 Idle 次數
- P：min{K-1, Q}

假設 W 固定，且 WS/R 大於等於 RTT + S/R，因為 W 沒有到達最高，所以一直持續傳送

假設 W 同樣固定，因為 W 有達到最高，導致有一小段時間要暫停傳送，所以中間會有 Idle Time


假設 W 會變化，


K 值的計算

# Network Layer

Network Layer 只有兩個功能：
- Forwarding：把 Packet 從 Router 的 Input 送到 Output，為 Data Plane
- Routing：決定封包的路徑，為 Control Plane

注意他們兩個是不一樣的，以開車旅遊來類比
- Forwarding：開車上交流道、下交流道
- Routing：規劃路線

常見的協定共有以下三種：
- IP Protocol：規定 Header 的規格、格式，以及 IP 地址的慣用法，例如 Host ID 都是 1 就代表廣播等規定
- ICMP Protocol：用於錯誤檢查
- Routing Protocols：規劃路徑的實作規定、演算法，常見的有 RIP、OSPF、BGP

### Router Architecture


- Input Ports：
- Physical Layer Function：終止路由器的傳入的物理連接
- Linker Layer Function：執行與傳入連接的另一側的鏈路層互操作所需的功能
- 查找功能：在 Input Port 的最右側方框中執行，藉此查詢轉發表以確定將抵達的數據包將通過交換結構轉發到哪個路由器輸出端口
- Switching Fabric：
- 連接 Input Port 和 Output Port
- Output ports：
- 儲存從 Switching Fabric 接收到的 Data，並通過執行必要的鏈路層和物理層功能將這些 Data 傳輸到傳出連接
- 當一個連接是雙向的（即在兩個方向上傳輸流量時），輸出端口通常會與同一線卡上的該連接的輸入端口配對
- Routing Processor：
- 執行 Control Plane 的功能
- 在傳統路由器中，Routing Processor 執行路由協議、維護路由表和附加的連接狀態信息，並計算路由器的轉發表
- 在 SDN 路由器中，Router Processor 負責與 SDN 的 Remote Controller 通信，以接收 Controller 經過運算後得到的 Routing Table，並將這 Table 安裝在 Router 中


Input Port 必須要接上一個 Buffer，防止 Switching Frabric 吃不消，假設每個 Input 每秒都輸入 10 單位的資料量，但 Switching Frabric 每秒只能處理 20 單位的資料量，而這 20 單位的效能要均分給以上三個 Port，因此 Input 需要 Buffer 等待 Switching Frabric 去接

而如果 Output Port 每秒也只能吃 10 單位，但剛剛 Input 的資料的目的地假設都是第二個 Output Port，因此 Input 的資料透過 Switching Frabric 每秒送出 20 單位的資料量給第二個 Output Port，Output Port 也吃不消，所以也要接上一個 Buffer

### HOL Head of the Line Blocking

有兩個 Input Queue 都打算到同個 Output Queue，但同一時間只能有一方先過去，假設是上方的先過去，那麼下方的紅綠 Packet 就受到 HOL 的影響，也就是說不會三個 Input Queue 都同時輸出到 Output Queue，可能會有短時間的 Idle


### Scheduling Policies

- FIFO：
- Prioiry：
- Round Robin：
- 


### IP and Special IP

IP 由兩部分組成：
- Network IP：高位元的部分
- Host IP：低位元的部分

如果要建立一個單一的 IP 網路，那麼就必須分配相同的 Network IP 給所有主機，而各主機的 Host ID 要是不同、唯一的

- Host ID are all 0：指這個網路本身的識別碼
- Host ID are all 1：指對指定網路廣播，只能用在 Dest IP
- Host ID and Network ID are all 1：指對自己所在的網路廣播，只能用在 Dest IP，且路由器不會轉發該 IP
- Host ID and Network ID are all 0：只要不清楚主機地址，就使用全為 0 的 IP，在你的電腦新加入一個網路時，在使用 DHCP 分配到 IP 以前，你的 IP 就是 0.0.0.0，你發送出去的封包的 Src IP 都是 0.0.0.0，且該 IP 只能用在 Src IP，不能是 Dest IP
- Class A's last Network ID：Class A 的最後一個 Network IP，即 127.X.X.X 全部都是保留作為 Loopback 地址，其中最常使用的是 127.0.0.1

### NAT

由於 IP 的不足，因此發展出了 NAT 技術，而 NAT 不只在 Network Layer，還甚至到了 Transport Layer，原理是用 Public IP + Port 映射到 Private IP + Port，對外來看都是 Public IP 來的

使用 NAT 的好處：
- 節省 IP
- 安全考量，可隱藏內部真實 IP

使用 NAT 的壞處：
- 影響 Router 轉發的性能，因為要做額外的 IP 修改及條件判斷
- 破壞 IP End to End 的特性，實際上你發送訊息到的那個 Server 的 IP 不是它真的 IP

### Difference Between Static NAT, Dynamic NAT and NAPT

- Static NAT：一個 Private IP 對應一個固定的合法 Public IP，且為一對一，該網路有十個 Private IP 就對應十個合法的 Public IP
- Dynamic IP：如果使用 Static NAT，由於不是所有人都同時上線，這會造成 Public IP 使用效率低下，因此改為使用動態分配的方式，但如果人太多導致 Public IP 不夠分配了，剩下的人就無法上網了
- NAPT：Dynamic IP 的優化版，通常我們所說的 NAT 其實是指 NAPT，也就是使用 IP + Port 來分辨、映射到 Private IP + Port

### DHCP

在網路中若要上網，每台電腦必須要有一個唯一的 IP，同時 IP 是有限的，我們不希望明明有人沒在使用網路卻占著 IP 不放，因此就有 DHCP 負責管理 IP，可自動動態地分配 IP 給網路內的電腦

有 DHCP 架構的網路主要有以下三個部分組成：
- DHCP Client：需要 IP 的每個使用者
- DHCP Server：負責動態地提供 IP 給網路中的每個 Client
- Scope：每台 DHCP 伺服器至少會管理一組 IP 位址，這組 IP 位址的範圍便稱為 Scope

取得 IP 的流程：
1. Client 廣播詢問誰是 DHCP Server
2. DHCP Server 單播回應，並且附帶 IP
3. Client 廣播告訴 DHCP Server 我已經取得到 IP，要求使用
4. DHCP Server Ack

註：由於向 DHCP 索取 IP 時要在網內廣播，因此向 DHCP 請求時 Dest Mac Address 必須是 ff:ff:ff:ff:ff:ff

### What is MTU

指 Link Layer 規定的 Frame 的大小，乙太網路的 MTU 為 1500 Byte，IEEE 802.3/802.2 是 1492 Byte，FDDI 則是 4352 Byte，依該設備所使用的連接方式決定，而整個路徑中不會只跑在同一種媒介上，因此原本 1500 Byte 的 MTU 可能在中間遇到了只允許 1400 Byte MTU 的媒介，導致再將 1500 拆成 1400 + 100，造成額外效能、使用率的損失，因此還需提到另一個重點，Path MTU，代表整條 Path 下最小的 MTU，使用 PMTU 可以讓整個傳輸過程中需要又再做多次 IP Fragmentation，因為此時封包已經足夠"瘦"到能夠不做任何事情就能穿越每條線路了

使用 MTU = 1500 Bytes，但中間又撞到 MTU = 1400 Bytes 的情況：

### How PMTU Discovery Work?

在 IP Header 有個 Dont Fragmentation 的 Flag，可利用它來尋找 PMTU（整條路徑中最小的 MTU），原理就是告訴所有路過的 Router 我不允許你切割此封包，既然不允許，那如果底下 MTU 更窄，那就沒辦法送了，因此只好回送一個 ICMP 給 Source

至於為何要找 PMTU 呢？好處在於能夠減少傳輸的碎片化，增加整理網路的效率，Router 也不需要再切割，節省 Router 的效能

原因在於，如果我送出的封包以 MTU=1500 切割，但中間卻出現 MTU=1400 的路徑，那麼封包就又要再被切成 1400、100，消耗效能外還要多加一個 IP Header，這導致實際網路的使用效率更低了

在 Windows 中可以使用 ping，以 -l 指定發送特定長度的封包，並且使用 -f 開啟 DF Flag

### Difference Between TCP Segmentation and IP Fragmentation

IP Fragmentation 由第三層切分，也在第三層重組，TCP Segmentation 則是在第四層切分，也是在第四層重組，並且會被避免在第三層切片，也就是說在 TCP 包裝完的 Packet 不用再分割，加上 IP Header 就可以直接送到 Link Layer 了，這是多巧妙的設計，所以 Congestion Window 才會默認以此為單位，因此才會有 MTU - 40（IP Header Length + TCP Header Length）= MSS 的公式，而 UDP 沒有第四層切分的機制，因此就依賴第三層切分，也因為 UDP 該層沒有切分重組功能，因此 UDP 的內容長度只能到 65535 - 28（UDP Header + IP Header）的長度，否則就超過 IP Packet 的邏輯大小

另外，由於一個 IP Packet 的最大長度是 65535，因此 Link Layer 規定的超高速通道的 MTU 就是 65535，因為再大下去也沒用，IPv4 Packet 也用不到這麼大


### ICMP

網路是一種不可靠的傳輸方式，傳送中的封包必須經過多個 Router 的轉送才能到達目的地，因此在發送封包之前，我們很難預測該封包是否可以安全到達目的地，而我們也很想知道目前網路的狀況，尤其在傳送失敗時，更想瞭解問題出在什麼地方，因此人們規範了一種協定：ICMP，用來偵測網路的狀況，在網路上，大部分 Host 或 Router 都支援 ICMP 協定，它們之間就可以利用 ICMP 來互相交換網路目前的狀況訊息，例如，主機不存在、網路斷線等等，它就是網路世界中的 Probe

當我們使用 ping、traceroute 的時候會使用 ICMP 協定的 Echo Request 進行請求，如果時間太久，會回送 TTL 逾時，如果成功送達則會回傳 Echo Reply

### Forward Table

### Longest Prefix Matching

Longest Prefix Matching 是指在 IP Forwarding 中，被路由器用於在路由表中進行選擇的一個算法，意思是尋找最長符合的 Pattern

例如：
- Interface 0：11001000 00010111 00010
- Interface 1：11001000 00010111 00011000
- Interface 2：11001000 00010111 00011
- Interface 3：Otherwise
則：
- 11001000 00010111 00010110 10100001 輸出到 Interface 0
- 11001000 00010111 00011000 10101010 輸出到 Interface 1，不是 Interface 2，因為 Interface 1 比較長，優先度高

### Generalized Forward Table

flow table：廣義的 forward table


### Routing

目的是為了將封包以最快的速度以 A 點送到 B 點，而怎麼走，由 Routing Protocol 決定

### What is Hop

指從 A 點傳到 B 點需要經過多少 Router

### Routing Algorithm Classification

- Global：每個 Router 都知道整個網路的拓樸狀態，代表性的演算法為 Link State Algorithm
- Decentralized：Router 只知道附近的 Router 是誰、Cost 多少，透過與鄰居的資訊互相交換來漸進地得到最短路徑，代表性的演算法為 Distance Vector Algorithm

### How to Determine Cost

可以使用當下到另一個 Router 的頻寬的倒數做為 Cost，因為如果傳輸速率越高，也就是說傳得越快、Cost 越低，如果傳輸速率超低，那就相當於 Cost 無限，此外，也可以多加上考慮物理距離等造成的傳輸時間差異

另外由於系統是動態的，傳輸速率雖然當下很充足，但如果封包因為此距離短都往這條路徑走，反而傳輸速率又因為封包太多而被占光了，也就是路徑的選擇又反向地影響 Cost，使其變高

### Dijkstra Algorithm

用於決定某點到其他所有任意節點的最短路徑

待補

### Distance Vector Algorithm

此為分散式的演算法，每個節點非同步地執行該算法，且只有附近節點的資訊，每個節點只要發現 Link Cost 改變，就會修正自己的 DV Table，並且送出自己的 DV Table 給鄰居，而鄰居接到這個 Table 也以同樣的方式，修正自己的 DV Table 給其他相鄰的節點

待補

### Hierarchical Routing

在以上的理論中，我們假設每個 Router 都是相同的協定，彼此同質，但實際上不是

現實世界中，Internet 是由多個小的 Network 構成，每個小的 Network 可能由各個 ISP 管理，其各自的 Network 都可使用不同的 Routing Algorithm，因此如何讓彼此使用不同的 Routing Algorithm 的網路合作，是個重要議題

如果不切分成多個小網路，那麼假設有 1000 萬個 Node，且 Router 間彼此又有許多連接，那麼 Routing Algorithm 計算過程所需的資訊（ex. DV Table）交換量龐大，會占用大量頻寬使網路使用效率差

### What is Autonomous System

自治系統，指的是所有處於同樣的管理網域（ex. ISP）下所有網路的集合，而一個管理網域指的是主機、路由器與內部連接網路的集合，而這個集合是歸屬於同樣的管理下運作的

有些 Routing Protocol 執行在同一個 AS 內，而某些 Routing Protoco 則運作在不同的 AS 之間，若以運作於 AS 內部與外部來區分 Routing Protocol 的話，可以分成Interior Gateway Protocol IGP 與 Exterior Gateway Protocol EGP，屬於 IGP 協定的包含 RIP、IGRP、EIGRP、OSPF，而屬於 EGP 的則有 BGP

Intra 在裡面 Inter 是外面

### Difference Between Inter and Intra

- Intra-AS：更注重效能
- Inter-AS：

### What is Daemon

有些 Routing Protocol 是運行在 Application Layer 的，也就是 Router 有個應用程式專門來決定 Routing Table，這種程式就稱做 Daemon，它只在後台運行，通常不與 User 直接交互，它在 OS 啟動時就跟著啟動，直到系統關閉，這類程式名稱通常以字母d結尾

常見的 Daemon 有：
- Database Server：提供 DB 服務
- Logger（Syslogd）： Logger 或 Syslogd 用於處理、紀錄系統的日誌
- HTTPd：用於提供網頁服務的 Daemon，常見的包括 Apache 和 Nginx
- crond：用於在預定時間執行任務的程式，例如可以設定定時執行某個程式，如備份、Log 清理
- sshd：讓遠端用戶能夠透過加密的方式登入到系統

### What is Best Effort

Best Effort 是一種服務模型，其提供的服務僅盡最大的可能性來發送 Packet，但對時延、可靠性等功能不提供任何保證，因此它也是最簡單的服務模型

### RIP

使用 Distance VectorAlgorithm，最多只支援 25 個主機，每隔 30 秒會與相鄰的 Router 使用 UDP 的方式交換訊息，如果超過 180 秒沒有收到鄰居 Router 的訊息，則當作鄰居已經消失，並且通知其他鄰居說這個鄰居消失了

此外 RIP 有自己的 Application Layer 的程式專門做 Routing Algorithm，這樣的程式稱做 Daemon

### OSPF

使用 Link State Algorithm，要廣播自己的 Table 給 AS 中的所有 Router，然後再執行 Dijkstra Algorithm，且不同於 RIP，它不須使用 UDP 傳送，僅需 IP Header 即可

此外 OSPF 還有一些先進的功能是 RIP 沒有的：
- Secuirty：所有的訊息都有認證的功能
- Multiple Cost Metrics：依據不同的 TOS Type of Service，使用不同的 Cost 計算方式，例如：已知衛星連線由於距離遠，其實傳輸延遲相當高，但對於只需要 Best Effort 要求的封包，這條 Cost 會被視為"低"，但對於 Real Time Service，則視為 Cost "高"

### BGP

Inter-AS Routing Protocol，處理的是跨 AS 的路由，AS 能夠透過相鄰的 AS 得到到其他 AS 需要經過哪些 AS 的資訊，然後從相鄰的 AS 得到這些資訊後再用廣播傳給 AS 內的其他 Router，綜上所述，BGP 的做法就是告訴鄰近的 AS "我在這，把這訊息廣播給你 AS 內的所有人"

BGP 重點只在於讓各個 AS 之間知道如何到其他的 AS，但對各個 AS 的內部 Router Topology 並不清楚，只能知道中間路過的 AS 確實有能力轉送到目的 AS，內部走很長或很短並不清楚，因此 BGP 的目的在於"能夠送達"，而非"最短路徑"

- eBGP（External）：
- iBGP（Internal）：


以 prefix 的方式用一個紀錄表示一堆 IP（待修正），例如用 125.202.xxx.xxx 的方式

接收到的訊息的格式：Prefix + Attribute，Attribute 有兩種：
- AS-PATH：廣播到各個 AS 時，這個 Packet 路過了哪些 AS
- NEXT-HOP：表明哪個 Router 負責轉發封包到其他 AS
-

### How Network Layer Broadcast


### Difference Between Traditional and Modern Control Plane

### SDN


# Link Layer

有兩個子層級：
- LLC：錯誤檢查、糾正、流量控制、可靠傳輸
- MAC：避免多台主機在同個媒介上傳遞資料

Link 共有兩種：
- Point to Point
- Broadcast：在同一介質、線路上共享，會遇到 Collision 問題，也就是"同時有多個人說話"

### Multiple Access Protocol

同一線路只能有一人講話的情境下，如何避馬大家同時說話？這就是 Multiple Acces Protocol 所要處理的，Multiple Access Protocol 通常會有以下需求：

- 分散式的演算法，該演算法要跑在多個 Node 上
- 沒有切割出 Out of Band 的線路做控制，一切資訊邏輯上都在同一條線路上傳輸

理想的 Multiple Access Protocol 希望能夠達到：
- 線路的傳輸速率是 R，那麼只有一個 Node 要傳送時，傳輸速度就盡量是 R，不希望為了管理、解決碰撞而有太多的 Overhead
- 公平的線路，也就是說多個人想傳送一堆資料的話，時間拉長看大家的使用率都要一致，即使用率 R 要盡量平等地被切割
- 簡單

目前主要有三種作法：
- Channel Partition：利用時間、頻率去切
- Random Access：讓大家自由傳送，會發生 Collision，但發生時再做額外處理
- Taking Turns：Node 之間輪流使用

### Channel Partition

主要有以下三種常用的作法：
- TDMA：依時間切割，
- FDMA：依頻率切割，
- CDMA：使用 Code（未知）

### Random Access

常用的協定:

Slotted ALOHA：將傳輸時間切成多個 Slot，每個時間段都能夠傳一個 Frame，且假設所有 Frame 的大小要一樣，由於沒有限制誰傳送，因此可能兩人同時傳而造成 Collision，而如果發生 Collision，則從下個 Slot 開始每次以機率 p，嘗試重傳

如果該網路有 N 個 Node 碰撞了，則開始 N 個人的抽籤，正好只有 1 個人抽到，開始使用的機率為 $Np(1-p)^{n-1}$，那麼 p 的值就很重要，p 的值在某個值的時候會使 $Np(1-p)^{n-1}$ 最大，因此要最大化，只要將其微分後等於 0 就是解，答案是 $p = \frac{1}{N}$ 時最大

公式：N 為碰撞的 Node 數量，$(1-\frac{1}{N})^{N-1}$ 所計算出的值代表線路的效率，N = 1 時為 100%，N = 2 時為 50%，N = 3 時為 4/9，N 接近無限時則為 0.37%

ALOHA：
- CSMA, CSMA/CD, CSMA/CA

Pure Aloha Maximum Efficiency

### CSMA/CD Algorithm

1. NIC receives datagram from network layer, creates frame
2. If NIC senses channel idle, starts frame transmission. If NIC senses channel busy, waits until channel idle, then transmits.
3. If NIC transmits entire frame without detecting another transmission, NIC is done with frame !
4. If NIC detects another transmission while transmitting, aborts and sends jam signal
5. After aborting, NIC enters binary (exponential) backoff:
after mth collision, NIC chooses K at random from {0,1,2, …, 2m-1}. NIC waits K·512 bit times, returns to Step 2
longer backoff interval with more collisions

### MAC Address

目的位址可分為單播、群播和廣播，只要最高 Byte 的 LSB 為 0 就代表該地址是單播位址，為 1 就是群播位址，而如果整個 MAC 全部都是 1，即 ff:ff:ff:ff:ff:ff 就是廣播位址

原廠出來的網路卡所附的 MAC Address，前 24 bits 代表各組織、廠商的 ID，後 24 bit 則由製造商分配

### ARP

若要將資料透過 Router 傳出去，但這依賴於底下的 MAC 層，因此 Switch 必須要知道 Router 的 MAC 地址，才能透過 Switch 把資料從電腦傳到 Router，而 Router 與 Router 之間的傳輸也是如此，如此一來我們才能以 IP 視角的觀點理解網路，但我們該如何得到路由器的 MAC 呢？答案就是使用 ARP

ARP Table 用來記錄哪個 MAC 對應到哪個 IP 地址，如果沒有 ARP Table，例如說路由器收到 IP Packet 以後，就不知道要轉送給哪台電腦了，但有了 ARP Table 以後，就能從 ARP Table 進行查詢，找到這個 IP 對應的 MAC 地址，而傳輸的過程中 IP 都不會變（忽略 NAT）並且根據路途中所有經過的 Router 的 ARP Table 去查詢下一個 Router 要怎麼走到

註：ARP Table 只會存在於 Router、PC 等第三層以上的設備，Switch 不會擁有 ARP Table

路由器的預設網關 IP 其實不重要，其存在目的是要給 ARP 取得回應的 MAC 地址

- ARP Request：對底下的 Switch 網路廣播，問某個 IP 的 MAC 是誰？
- ARP Reply：單播回應，我是這個 IP，然後附上自己的 MAC

### CRC

https://www.youtube.com/watch?v=w1y9f_Wnyqk&t=1084s&ab_channel=%E7%A0%94%E9%81%93%E9%9A%BE

常見的 CRC Polynomial Generator

### 將IPv4 與 IPv6 相容的方法


### Difference Between Switch and Router

Switch：
- Switch Table 透過自學習得
Router：
- Routing Table 透過 Routing Algorithm

### A day in the life

透過網路層廣播（使用 255.255.255.255）做 DHCP，而回傳的時候通常也會附帶 Router 的 IP 以及 DNS 的 IP

# Note

- 一個網路有兩個 Switch，各自接上 ABC 以及 DEF 六台電腦，各個 Switch 仍然知道每個 Mac 該對應哪個輸出 Port，MAC 表中存在六個完整的對應
- MAC 學習，Switch 開機後，並沒有各個接口對應到 Mac，而是透過學習建立表，算法如下，當一個接口有 frame 傳進來後，就能夠過其 header 得到 Mac，而這個封包要送到 B，但不知道 B 在哪，這時候就只能廣播，讓他們自己接，但一但 B 向 switch 傳過一次訊息，接口對應 B 的 Mac 的關係就會立刻建立
- Router 本身有 MAC 地址，並且除了擁有 IP 外(switch 沒有 IP)，與 switch 另一個重大差別是：Router 收到 Mac 廣播訊息後不會繼續廣播，會把廣播訊息當作空氣，因此 Router 會與外界隔離，因此各個 Router 底下的子網路的廣播都是隔離的，互相不得而知，而要連出去只能透過 IP
- Mac 和 Switch 的端口不是一對一關係，而是多對一關係，如果一個 MAC 可以對應多個端口，那麼收訊息的時候就不知道要傳到哪個特定的端口
- 默認網關，就是在自己電腦裡設定一個 IP 地址，將要用 IP 傳輸的資訊都直接往這個 IP 丟
- 同樣 路由器從外界收到訊息後，要透過 MAC 轉到真正要給的電腦上，這也要透過 ARP 廣播，問這個 IP 對應到哪個電腦的 MAC
- 理論上來說可以用 SW 小範圍內互傳而不用 SW 對外，但由於 SOCKET PROGRAMMING 太方便，我們還是會用 IP 傳到路由器再傳回來
- 含有 Layer3 層級的設備都會擁有 ARP Table
- Ethernet 是 IEEE 802.3，定義了物理層和數據鏈結層，實際上它是一堆 Protocol 的集合，並且隨著技術的革新一直在擴大，各種線材以及線材材料的演進，都各自有對應的 Ethernet Protocal，例如 Cat5e 雙絞線和 Cat6 就有訂定 802.3bz
- FQDN 是指完整的網域名稱，例如 www.google.com，www 代表主機名稱，通常以伺服器的用途命名，例如信箱的 server 會用 mail，新聞 server 會用 news
- Switch 依據收到的 mac 地址分配給其他電腦，本身不需要 mac 地址，並且每個有接上電腦的接口都會對應一個 mac 地址
- traceroute 原理：舉例說傳到 www.google.com，會把三個封包傳到第一個 router，然後回傳，然後再傳三個到第二個 router，然後再回傳
- 
- 最後一哩路是路由器接到家裡
- Rdt 3.0 仍有問題，假設一個封包一直在網路裡面打轉，直到 seq number 又 overflow 繞回來才到接收端，可能就會判定錯誤，但實務上這件事情不可能發生，因為 TTL 沒辦法讓他跑這麼多次
- 沒連上網路仍能連上 127.X.X.X，NIC 看到此地址後不會丟出去，而是 Loopback，此外，::1 就是 IPv6 版本的 127.0.0.1
- Ethernet 沒做 reliable delivery 因為本身錯誤率就很低 但 無線的就一定要做
- 無線網路常常使 TCP 丟包 因此會讓 TCP 誤以為 congetion 可能會降一堆流量
- 交換器只是轉發的設備 所以本身不需要MAC地址
- Network 是 big endian，且 header 中間也沒有 padding，可以使用 Pragma pack 強制取消記憶體對齊
- link layer 使用 preamble 去區分 frame，但傳輸的過程中，data 可能會有一樣的資料與 preamble 一致，因此要利用跳脫字元的方式
- 
- 
- Linklayer 的 frame data 一定要超過 46 bytes 為甚麼?
- Link layer 有標尾 是因為 crc
- gateway 預設閘道 通常IP是 192.168.10.254, 172.30.10.254
- Switch 可以切開 Collision Doamin，但 Hub 只是瘋狂廣播，所以沒辦法
- Hub 所接出去的線速度都必須要一樣，但 Switch 則可以不同，可以一條 100 Mbps，一條 200 Mbps
- Router 要手動設定彼此之間的 IP，否則沒辦法知道 ARP 所需的 Dest IP
https://draveness.me/whys-the-design-non-unique-mac-address/
https://www.bilibili.com/video/BV1CW4y1k7eA/?p=2&spm_id_from=pageDriverone

### UDP Header


UDP Header：固定長度為 8 Bytes，組成如下：
- Source Port
- Destination Port
- Length：包含 Data，整個 Datagram 的長度（單位：Byte），因此該欄位最小值為 8
- Check Sum：將 Header、Data 以及 Pseudo Header 以每 16-bits 的字組全部加起來（Check Sum 計算前要歸 0），並且 Overflow 的 Bit 要加回 MSB，最後再做 1's Complement，這就是 Check Sum 的值，而在接收端會將整個 16-bits 全部加起來，總和應要是 1111111111111111，如果有 0 就代表傳輸發生了錯誤
- Pseudo Header 的組成：

### TCP Header

TCP Header：可變長度，不包含 Data，整個 Header 最小為 20 Byte，最大為 60 Byte，組成如下：
- Source Port
- Destination Port
- Sequence Number：以 Byte 為單位計算，代表要傳出資料中的第一個 Byte 的數值
- Acknowledgment Number：以 Byte 為單位計算，代表接收端期望另一方送來的 Byte 是原資料的第幾個 Byte，是 Accumulative 的，需 ACK Bit = 1 的時候才有意義
- DO：Data Offset，Data 起點的偏移量（單位：4 Byte），等同於該 Header 的長度，最小值為 5 Byte，最大值為 15 Byte
- RSV：Reserved，保留 6 bit，必定為 0
- Flags：
- SYN：建立連線時使用
- FIN：關閉連線時使用
- ACK：告知已經收到資料時使用
- RST：
- Receive Window：告訴對方我有多大的 Buffer 可使用，以免灌爆
- Check Sum：同 UDP，需要額外加上 Pseudo Header
- Urgent Pointer：當 URG = 1 時，其代表緊急資料是在資料區的什麼位址

### IPv4 Header

- Version：表示版本，0100 代表 IPv4，0110 代表 IPv6
- IHL Internet Header Length：表示 IP Header 的長度，（單位：4 Byte）範圍值介於 5~16 之間，沒有 Options 的話就會是 5
- Type of Service：一般的情況下都不使用這個欄位，只有在使用VoIP時才會被指用，預設值為 0
- Total Length：用來表示整個 Packet 的長度，包含 Header + Data，範圍為 576 ~ 65535，單位為 Byte
- Identification：如果一個 IP Packet 被 Fragmented，那麼每個被切出來的封包都會用同樣的 16 bit Identification 代表它們原本屬於同個 IP Packet
- Flags：若封包過大時，則會定義該封包可否被切格為等量的小封包進行傳送
- 第一個 bit 必為 0
- 第二個 bit 稱做 DF Don’t Fragment，代表這個 Packet 不該被 Fragmented
- 第三個 bit 稱做 MF More Fragments，所有被 Fragmented 的封包都應設為 1，除了最後一個
- Fragment Offset：13 個 bit 用來描述這 Fragment 屬於原本 IP Packet 中的哪個起始點，但單位是 8 Byte
- TTL：為了避免封包在網路中永遠存在（例如陷入路由環路），封包經過的每個路由器都將此欄位減 1，當此欄位為 0 時，封包便會被丟棄
- Protocol：用來定義了該 Data 區所使用的協定，對應的協定表：https://en.wikipedia.org/wiki/List_of_IP_protocol_numbers
- Header Checksum：https://zhuanlan.zhihu.com/p/378533002?utm_id=0
- Source Address
- Destination Address
- 註：兩個Flags和Fragment Offset結合使用，進行分片時，如果MF的值為1，則表示目前IP封包是一個IP套件的其中一段分片，且不是最後一個分片，這時結合Fragment Offset域繼續判斷；如果MF為1而Fragment Offset = 0，表示該IP報文為第一個分片，而且後續有分片；如果MF為1而Fragment Offset不是0，表示該IP封包為中間的一個分片；如果MF為0而Fragment Offset不是0，表示該封包是最後一個分片

### ICMPv4 Header


長 12 Byte

### Link Layer Header

Data Link Layer：固定長度為 14 Byte，前 6 Byte 是 Src MAC，後 6 Byte 是 Dest MAC，最後 2 Byte 則是定義採用哪一種 Network Layer 協定，例如 IPv4 or IPv6

### Reference

https://www.bilibili.com/video/BV1oY4y1g7X1/?spm_id_from=333.788&vd_source=fe0a19eb825da1e240222c106c8ac793

https://www.youtube.com/watch?v=F8Ll9U6Yzd8&list=PLER5irn79DZqSxB6DCn5Y6zs1KoOAIjQe&ab_channel=HarryLi

Cisco Packet Tracer

### NFV

https://medium.com/@RiverChan/sdn%E8%88%87nfv%E7%9A%84%E5%8D%80%E5%88%A5%E5%92%8C%E9%97%9C%E4%BF%82-3a15692bb3f6