# 大二下 - Computer Networking - 期末考題整理
###### tags: `大二下` `計算機網路`
---
quiz7~12來自大二包
***背到ㄎ一 ㄒㄧㄠˋ***

quiz7
===
1. What are the header fields to identify a UDP socket and a TCP socket?
>**UDP:** destination IP,destination port
>**TCP:** destination IP, destination port, source IP,source port
2. Please list the network applications of UDP.
>(1) streaming multimedia apps (loss tolerant, rate sensitive)
>(2) DNS
>(3) SNMP
3. Please describe all necessary mechanisms to recover the packets with bits errors.
>(1) ACKs, NAKs, sequence number, stop-and-wait
>(2)當 reciever 收到 pkt ,用 checksum check bit error
>**有錯:** return NAK sender 會重送 pkt
>**正確:** return ACK sender 傳送下一個封包
>如果沒有回傳 ACK or NAK 表示 pkt loss 重傳封包
4. Please explain why one-bit sequence number is enough for stop-and-wait protocol.
>確認 sender 和 receiver 是否在溝通同一個 pkt
>Checking whether sender and receiver are “talking” about same packet.
5. What is the function of sequence numbers in feedback segments?
>分別對 pkt0,pkt1 做出 ACK/NAK 的回應
>state indicates whether 0 or 1 is expected pkt seq #

quiz8
===
1. Please describe all necessary machanisms to recover packet loss.
>每送出一個 pkt 就會啟動 countdown timer ,當發生 timeout 就會重送 pkt
2. Please describe the problem caused by improper timeout value.
>(1) 太大:如果 pkt loss 需要花很多時間才能修復
>(2) 太小:會造成很多不必要的重送
3. 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.
>無需等待一個 pkt 被 ACK 就可以送出下一個 pkt
4. Please describe the difference between Go-back-N and Selective Repeat for packet retransmission, receiver window (buffer)size , and number of timers.
>**GBN** : 如果有 pkt loss 會重送所有 windows 內還未被 ACK 的所有封包,
>Window size<seq. num ,只有一個 timer
>**SR** : 如果發生 pkt loss 只會重送遺失的封包,window size<seq num/2
>每個封包都有獨立的 timer
5. How may sequence number are required for selective repeat?
>seq# >= 2W

quiz9
===
1. 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
2. Please describe the procedure of TCP delayed ACK in TCP receivers.
>花 500ms 等待下一個依序的 segment 到來,如果在這段期間內沒有送達,就送出 ACK.
3. Please describe the idea of TCP Fast Retransmit.
>當 receiver 收到三次重複的 ACK 就重送 segment 不用等到 timeout 才重送
4. TCP flow control can avoid receiver buffer overflows. Please describe its procedure.
>會先判斷中途的 buffer 有沒有 free space,有 free space 再傳送
5. Please describe the difference of reliable data transfer between TCP and Go-Back-N.
>**GBN**: 當封包遺失會重傳所有封包
>**TCP**: 使用 SR,只針對遺失的封包重傳
6. Please explain the values specified in fields of sequence number and acknowledge number in a TCP header.
>**Seq num** =byte stream number of first byte in segment’s data(每一個segment 的第一個 byte 編號)
>**ACK num** = 期望收到的下一個 seq. number

quiz10
===

1. Please describe the four-way handshake of closing a TCP connection.
>Client 送出 FIN=1 給 server, server return ACK,server 送出FIN=1,client return ACK 並關閉連線,server receive ACK 也關閉連線。
2. Please describe how TCP slowstart adjusts CWND.
>**初始化**: CWND=1MSS
>**Receive ACK**: CWND=CWND+1MSS
>**Timeout**: CWND=1MSS
3. Please describe the idea of AIMD (additive increase ; multiplicative decrease) for adjusting CWND.
>一個 RTT 只增加一個 MSS(累進增加),data loss 則減半(倍數遞減)
4. How does TCP congestion control adjust CWND and SSTHRESH when timeout occurs.
>CWND=1, SSTHRESH=CWND/2
5. How does TCP congestion control adjust CWND and SSTHRESH when triple duplicated ACKs occur.
>SSTHRESH=CWND/2,CWND=SSTHRESH+3*MSS
6. Please specify the increment value of CWND in TCP congestion-avoidance for receiving one new ACK.
>CWND=CWND+MSS(MSS/CWND)
7. Please describe the three-way handshake of TCP connection setup. (考古題非本屆小考題)
>1.TCP SYN segment
client 傳送 SYN = 1 seq = client isn(init seq num) 給 server
>2.SYNACK segment (告訴 client 已被 server 允許連線)
server 回傳 SYN = 1 ACK = client isn + 1 seq = server isn 給 client
>3.client 回傳 SYN = 0 ACK = server isn + 1 seq = client isn + 1 給 server

quiz11
===
1. Please describe the functions of data plane and control plane in each router.
>**Data plane:** forwarding function,決定進入 input port 的 pkt 應該到達哪個 output port
>**Control plane:** routing function,計算從 source 到 destination 的路徑
2. Please explain the operation of longest prefix matching.
>在 forwarding table 中可能有許多相符的 prefix,因此要找最長相符的字首
3. Please describe three types of switching fabrics.
>**Via memory**: 將 pkt 放到 routing processor 的記憶體中做交換
>**Via bus**: 使用單一匯流排做交換,會收到頻寬的限制
>**Crossbar** : 將 n 個 input port 連接到 n 個 output port 的網路(bus)
4. Please describe the purpose of input-port queueing.
>如果有一個 datagram 還在 switching fabric 內,到達 input port 的datagram 就必須在 input port queue 等待。
5. Please describe the problem of head-of-the-line (HOL) blocking.
>當有其中兩個 datagram 的 output port 相同,其中一個就須在 input port 等待,此時就會使的 input port queue 內的其他的 datagram 無法得到服務。

quiz12
===
1. Please describe the reasoning of IP fragmentation and the related header fields.
>因為每個 link layer 的 MTU 大小不同,因此需要做分割。
>Identifier,frag. flag ,offset.
2. Please describe the functions of Time to Live and Upper Layer fields in IPv4 header.
>**TTL**: 一個 datagram 可存活的時間,每經過一個 router TTL-1,當 TTL=0 router 就會丟棄此 datagram.
>**Upper layer:** link layer 使用的 protocol.
3. What is CIDR?
>將 IP address a.b.c.d/x 分成兩個部分,前 x bits 表 subnet address,後面的 32-x bits 表 host address(外部 routers 只需辨識前 x bits)
4. Please describe the information stored in a NAT translation table.
>WAN IP,WAN port,LAN IP,LAN port.
5. Please describe the idea of route aggregation.
>將多個 prefix 相同的 IP 視為一個網路
6. Why must routers perform longest prefix matching to ensure the correctness of packet routing?
>假設 IP A 本來屬於 ISP1 但後來更換服務為 ISP2,此時會發現在 ISP1 和 ISP2 都有相符的 prefix,因此要找 longest prefix matching 才能找到正確的 IP.

Homework
===

教授多出的作業 :cry:
善心人士免費提供+另3人合力尋找之解答
1. Please describe the operations of link-state routing algorithm.
>經過 k 次迭代，每次尋找不在 N’的 D(BV)，計算出 source 到所有共 k 節點的最短路徑，並經由 link state broadcast 所有節點有相同訊息。
2. Please use an example to explain why link-state routing algorithm would cause route oscillation
>
>

3. Please describe the operations of distance-vector routing algorithm.
>節點時不時向鄰居發送自己的 estimate DV, 當收到新 estimate DV，就用Bellman-Ford equation 更新自己的 DV，最終收斂到實際最小成本。
4. Please show how poisoned reverse solves the problem of count-to-infinity
>當某 router 偵測到 link cost change,傳遞目的地錯誤訊息回上一個 router,
上一個 router 更新 routing table 並且不再傳遞此目的地 route 給其他人,
阻止 count-to-infinity
5. Please compare link-state and distance-vector algorithms in terms of messagecomplexity, convergence speed and robustness.
>**message complexity**:
LS->n 個 routers, O(n^2) messages sent; DV->neighbors 之間的交換
**convergence speed:**
LS->O(n^2),可能有震盪; DV->可能有 routing loops 或 count-to-infinity
**robustness**:
LS->router 可以告知錯誤的 link cost,每個 router 只算自己的 table; DV->
告知錯誤 path cost,table 可被他人使用
6. Please explain how Internet uses intra-AS and inter-AS routing to achieve scalable routing.
>**Intra-AS**:在 AS 內 routing，同 AS 要用一樣 protocol，getway router 在自己 AS的 edge 連接其他 AS。
>**Inter-AS:** 在 AS 間 routing，gateways 執行 inter-domain routing 和 intradomain routing。
7. Please describe the concept and benefits of hierarchical OSPF.
>**Concept:** router 用 IP 向整個 AS 中其他 router 提供 OSPF link-state，可能有多個 link costs metrics，每個 router 有完整拓樸。
>**Benefits:** open(所有人都可使用), security(messages 授權)。
8. Please describe the functions of eBGP and iBGP sessions.
>**eBGP:** 從相鄰 AS 獲取子網路可達性訊息。
>**iBGP:** 向所有 AS 內 router 傳播可達訊息。
9. Please describe the generation of forwarding-table entries in a router with BGP and OSPF.
>Gateway router 用 import policy 接收其他 AS gateway 的 path，並 advertise path 到鄰近的 ASes。
10. Please describe how hot potato routing works.
>選擇區域內最近的出口點並走最短路徑，快速轉發，減少延遲和傳輸的時間
11. Please use examples to examine the operations of policy for BGP
>AS path prepending : 假設有兩個 AS 連到同一個 AS，將 AS 廣播到較不優先的連線，將自己的 AS 編號多次加到 AS 路徑屬性中，可改變連線的優先順