計算機網路

tags: `大學必修-筆記`

Ch1-1

名詞解釋

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

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

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

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

cable

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

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

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

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 -> 利用時間來區分
  Image Not Showing Possible Reasons
  The image file may be corrupted
  The server hosting the image is unavailable
  The image path is incorrect
  The image format is not supported
  Learn More →

網路結構 network of network

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

CH1-4

Delay 延遲

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

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

Packet loss 封包遺失

Traffic Intensity 通訊密度 =
$\frac{L a}{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

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

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連線可以傳送多個檔案
HTTP message
- request
- response
HTTP 錯誤訊息
- 200 OK - 確定。用戶端要求成功
- 301 Moved Permanently - 要求的網頁已經永久改變網址。此狀態要求用戶端未來在連結此網址時應該導向至指定的 URI
- 400 Bad Request - 錯誤的要求
- 404 Not Found - 找不到
- 505 HTTP Version Not Supported - 不支援的 HTTP 版本

cookies

步驟
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 代理伺服器

解釋
- 在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
- 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 階級式資料庫
- 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 依次尋問
- Recursive Query 遞歸式查詢
  - 把問題丟到 root 去做
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
- 不管是 query reply 訊息格式都是一樣的
在DNS中新增紀錄

CH2-5 P2P

P2P 架構

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

File distribution time

Client-Server 主從式
- $d_{c s} = m a x {N F / u_{s}, F / m i n (d_{i})}$
P2P 點對點
- $d_{p 2 p} = m a x {F / u_{s}, F / m i n (d_{i}), N F / (u_{s} + \sum u_{i})}$
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)

jojo的奇妙比喻
12 個小孩傳送信件給12個小孩

行程
$\to$ 小孩
應用程式訊息
$\to$ 信封中的信
主機
$\to$ 房子
傳輸協定
$\to$ Ann 以及 Bill (?
網路層協定
$\to$ 郵政服務

網際網路傳輸層協定

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

CH3-2 Multiplexing & demultiplexing

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

傳送端主機的多工
- 收集多個socket的資料、用 transport header 標頭將每個資料片段封裝成資料分段(segment)
接收端主機的解多工
- 將收到的資料分段 (segment)傳送給正確的socket

jojo的奇妙比喻
解多工(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 的補數

CH3-4 reliable data transfer 原則

可靠的資料傳輸

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) -> 超過指定的時間後，將對傳送端發出中斷

會有以下四種狀況
- 沒有發生資料遺失
- 封包遺失
- 遺失ACK
- 過早發生逾時

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

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

Pipelined protocols 管線化

可以一次傳多個封包

Sliding-window protocol 滑動視窗協定

Go-Back-N GBN協定

base: 最久未被確認的封包的序列號碼
nextseqnum: 最小未被使用到的序列號碼
傳送端
- 來自上層的呼叫
  - 當收到上層呼叫 rdt_send() 時
  - 傳送端會檢查 window 是否已經滿了?
- ACK的接收
  - 累積式確認 (cumulative acknowledgement)
  - 確認小於或等於序號 n 的所有封包
- 逾時事件 (timeout event)
  - 傳送端會重新傳送所有先前已經傳送但尚未收到確認的封包
接收端
- 只為接收順序正確的封包傳送ACK
  - 一次傳送一個封包給上層
  - 可能會產生重複的ACK (因為捨棄掉未按順序到來的封包序號)
  - 只需要記住 expectedseqnum (下一個封包的序列號碼)
- 順序不正確的封包

傳送端：

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

接收端：

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

選擇性重複 (SR)

改善 GBN 的問題：
- 單一封包錯誤將可能導致 GBN 重新傳送大量的封包
- 但大部分不須重新傳送
SR 的改善方法：
- 傳送端只重新傳送未正確收到的封包

傳送端
- ACK
  - 將封包 n 標示為已收到的
  - 假如 n 為未確認的封包中最小的封包時，將視窗的base 往前移到下一個未回應ACK的序號
接收端
- 傳送 ACK(n)
  - 不正確的順序：暫存區
  - 正確順序： deliver 將視窗前進到下一個未接收的封包

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 倒底要多大

R T T 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、目的端埠號
前院長的中文時間

Please describe the mechanism of packet error detection using checksum.

傳送端傳送checksum 給接收端之後,接收端再經由計算所收到的segment做checksum,如果兩者相同則沒有錯誤,反之則有。

傳送端傳送檢查和給接收端之後，接收端再經由計算所收到的區段做檢查和，如果兩者相同則沒有錯誤，反之則有。
前院長的中文時間

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

串流媒體應用程式
域名系統
簡單網路管理協定
前院長的中文時間

第七次小考題目

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.

序列號用於追蹤已傳送的資料大小。
前院長的中文時間

Please describe all necessary mechanisms to recover packet loss.

發送端送出封包時會設定countdown timer，timeout發生直接重傳。

傳送端送出封包時會設定倒數計時器，若發生逾時直接重傳。
前院長的中文時間

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，只有一個計時器，綁定在最早送出且未經確認的封包。
選擇性重複：只重送遺失或損毀的封包，接收端暫存大小 = 傳送端暫存大小，每一個封包都有綁計時器。
前院長的中文時間

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

Please describe the problems caused by improper timeout values.

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

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

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。
前院長的中文時間

Please describe the idea of TCP Fast Retransmit.

如果接收了三個連續ACK，則重傳，不用等timeout

當接收到 3 個重複的 ACK，則立即重送該區段，而非等到重送計時器逾時。
前院長的中文時間

第九次小考題目

TCP flow control can avoid receiver buffer overflows. Please describe its procedure.

利用rwnd (reciever window size) 如果rwnd=0代表buffer full

偵測接收端窗格大小，若其為 0，代表暫存已滿。
前院長的中文時間

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

因為two way在packet loss 和delay 時會造成另一端以為建立新連線，導致一端終止一端開啟的情況。

因為雙向交握在封包延遲或遺失時，會造成另一端以為建立新連線，導致一端終止一端開啟的情況。
前院長的中文時間

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

Please describe how TCP slowstart phase adjusts CWND value.

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

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

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:決定封包在端點間的移動路徑

資料層：接收封包後決定要去哪個輸出端口。
控制層：決定封包在端點間的移動路徑。
前院長的中文時間

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

quening delay and loss due to buffer overflow

因為暫存溢出而導致封包佇列延遲或遺失。
前院長的中文時間

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=]

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

記憶體：直接將封包複製到適當輸出埠記憶體中。
匯流排：透過共用匯流排直接將封包傳輸到輸出埠。
棋盤式交換器：封包會沿著連接到該輸入埠的水平匯流排移動，前往其目標輸出埠的垂直匯流排。
前院長的中文時間

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：區段位移，判斷區段屬於原始封包的哪一段資料。
前院長的中文時間

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) 上層協定：記錄封包在傳輸層所使用的網路協定為何。
前院長的中文時間

What is CIDR?

一個運用VLSM(variable-length subnet masking)分配IP位址以及在網路上有效路由IP封包的方法。

CIDR 無類別域間路由
VLSM 變動長度子網路遮罩
前院長的中文時間

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

去尾：丟棄到達封包。
優先度：根據優先偏好丟棄封包。
隨機：隨機丟棄封包。
前院長的中文時間

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

subnet part - high order bits
host part - low order bits

子網部分：高位元
主機部分：低位元
前院長的中文時間

第十二次小考題目

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

廣域網地址對應區域網地址。
前院長的中文時間

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

優點：

所有設備只需一個IP地址

可以在不通知外界的情況下更改本地網絡中設備的地址

可以在不更改本地網絡中設備地址的情況下更改ISP

本地網內的設備無法明確尋址，外界不可見

缺點：

增加路徑轉換的延遲

失去對IP來源的可追溯性

導致某些應用程式的通訊失敗

挑幾點寫應該就夠了……建議是只記第一和最後
前院長的中文時間

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

計算機網路

tags: 大學必修-筆記

Ch1-1

名詞解釋

設備

網路結構

protocol 協定

CH1-2

Access network

DSL - digital subscriber line

cable

wireless LANs 無線網路

wide-area wireless access 行動網路

Physical media 傳輸媒界

CH1-3

queuing and loss

packet switching -> 封包交換

circuit switching -> 線路交換

網路結構 network of network

CH1-4

Delay 延遲

Packet loss 封包遺失

Throuthput -> 傳輸量

CH1-5

protocol layers 協定層

TCP/IP model

CH1-6

網路安全

CH2-1

Application architecture

Processes Communicating 行程通訊

Sockets

Address Processing 行程定址

Application 需要的服務

Protocols services

CH2-2

HTTP 超文字傳輸協定

名詞解釋

HTTP介紹

cookies

Proxy server 代理伺服器

CH2-3

電子郵件

SMTP 簡單郵件傳輸協定

POP3 郵局協定第3版

IMAP 網際網路郵件存取協定

CH2-4 DNS domain name system

CH2-5 P2P

P2P 架構

File distribution time

CH2-6 Video Streming & CDN

Video

CDN Content distribution networks

CH3-1

傳輸層 Transport-layer 的服務

傳輸層 v.s. 網路層

網際網路傳輸層協定

CH3-2 Multiplexing & demultiplexing

解多工

無連線 UDP 解多工

連線導向TCP的解多工

CH3-3 無連線傳輸 -> UDP

CH3-4 reliable data transfer 原則

可靠的資料傳輸

rdt 1.0

rdt 2.0

rdt 2.1

rdt 2.2

rdt 3.0

Pipelined protocols 管線化

Sliding-window protocol 滑動視窗協定

Go-Back-N GBN協定

選擇性重複 (SR)

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

TCP 特色

分段結構

CH4-1

名詞解釋

網路層

CH4-2

tags: `大學必修-筆記`