電腦網路期末考
===
<contributors `25077667` >
:::success
Rules:
在題號後標注該答案完成度
❌ 尚未填寫
🔰 暫時有解或僅有部份解，且認證未達三次
✅ 三個人認證此答案是可行答案
---
誰可以認證答案？
> 所有人
如何認證？
> 於作答區後面放 :fleur_de_lis: 並附上你的名字
>> :fleur_de_lis: [name=楊志璿]
沒有人認證？
> 寫下你的意見，討論看看
這規則可不可以改？
> 可以，寫下你的想法
:::
## **108**
### 1. ✅ Please explain the below graph by your understandings to some details.
##### Per-router control (Traditional)
For all routers interact with each other in control plane to compute forwarding tables individually. The value in the header is used as an index to the forwarding table, which is generated by the routing algorithm and protocols in the control plane. Each router have its' own routing component.
##### SDN
A distinct central (typically remote) controller interacts with local control agents in routers to compute forwarding tables.
> :fleur_de_lis: [name=楊志璿] [name=ernestchu] [name=德伊科爾]
-------
### 2. ✅ Please draw a generic router architecture and explain its operations.
##### Rounting processor
###### Traditional
Execute the routing protocols, maintain routing tables.
###### SDN
Communicate with the remote controller
##### Input ports
First, terminate an incoming physical link, then interoperate with the link layer at the other side. Finally, consult the forwarding table to determine which output port to take. The special control packets are forwarded from an input port to routing processor
##### Output ports
Same procedures as the input port but in a reverse order. An input-output port pair for the link on the same line card.
##### Switching fabric
###### Switching via memory
Only one packet can be forwarded at a time because only one memory read/write can be done at a time over the shared system bus
###### Switching via a bus
A switch-internal label is added to each packet. All output ports receive the packet, but only the port that matches the label will keep the packet. Only one packet can cross the bus at a time.
###### Switching via an interconnection network
Each vertical and horizontal buses intersect at a crosspoint, which can be opened or closed at any time, a packet would not be blocked as long as no other packet is currently being forwarded to the same output port
> :fleur_de_lis: [name=楊志璿] [name=ernestchu] [name=德伊科爾]
-------
### 3. ✅ Please use an example to explain how largest prefix matching is in forwarding IP packets? Why do we need to search for the longest prefix matching for an IP address?
[最長前綴匹配](https://zh.wikipedia.org/wiki/%E6%9C%80%E9%95%BF%E5%89%8D%E7%BC%80%E5%8C%B9%E9%85%8D)
* Why ...?
* 因為若沒有longest prefix matching讓轉發表進行分類，想要讓每個地址在轉發表都有一個表項是不可行的(超過40億個可能的地址)
* [name=SCC] 假設存在 2 條或以上規則皆符合待轉發封包之 ip，必須要用最長前綴比對原則，否則無法區分優先級。
Suppose `ISPs-R-Us` was aquired by `Fly-By-Night-ISP`, and the latter want to has `Organization 1` connect to the Internet through the former, as present in **Figure 4.22**, a solution is to renumber all of the routers and hosts within `Organization 1`. However, it's impractical since it's costly and `Organization 1` might well be reassigned in the future.
A better choice is to make `ISPs-R-Us` not only advertised `199.31.0.0/16` but also `Oragnization 1`'s address, `200.23.16.0/23`. As a result, when other routers in the larger Internet want to route to an address with in `Organization 1`, both `200.23.16.0/20` and `200.23.18.0/23` are matched.
```
200.23.16.0/20 in binary:
11001000 00010111 0001xxxx xxxxxxxx
don't care
200.23.18.0/23 in binary:
11001000 00010111 0001001x xxxxxxxx
don't care
```
Even if the address matches to the `Fly-By-Night-ISP`'s entry. The router would continue to find the match with **the longest prefix** and finally finds `ISPs-R-Us`, where the desired `Organization 1` is located.
<!--
> @ernestchu Why do we need this rule? [name=楊志璿]
> 應該這樣說：為什麼我們「需要」，邏輯上不要也可以阿（暴力法）。我們需要的是：「一個可以找到轉發的方式」，沒有需要使用「最長前綴匹配原則」吧？
> 「最長前綴匹配原則」是這些轉發方式中，比較額...簡單？低成本？穩定？的方式。
> 那，還有一個問題：「最長前綴匹配原則」是「最」低成本、穩定的方式嗎？
>> 這是以 address 作為 forwading table 的 key 時用的方法，是不是最有效的我不知道，會使用 prefix 是因為 CIDR 把外網放在左邊。不過像後面 SDN 有這麼多的 field 來做 matching ，action 也不只有 fowarding 而已，所以你說的 `一個可以找到轉發的方式` 是需要考慮其他因素的 [name=ernestchu] -->
> :fleur_de_lis: [name=ernestchu] [name=SCC] [name=alice]
-------
### 4. 🔰 Again please draw a picture to show what is Head-of-the-Line (HOL) blocking? What is a hot spot problem?
If the switch chooses to forward the packet from the front of the upper-left queue, the packet from the front of the lower-left queue must wait. The latter packet in the lower-left queue must wait for the one in front of it as well. This is called head-of-the-line (HOL) blocking in which even if a packet's output port is free, it still need to wait for the head of the line (the packet from the front of the queue)
##### Hot spot problem
The hot-spot problem refers to sink node’s one-hop neighbours being required to forward a disproportionately higher volume of traffic compared to other nodes in the network. The sink’s one-hop neighbours - also known as the ‘hot-spot’ nodes - tend to exhaust their energy and ‘die’ earlier relative to other nodes. Unless adequately dealt with, through measures that reduce the load and prevent the failure of the sink’s one hop neighbours, the hot-spot problem can lead to a complete isolation of the sink node, resulting in the failure of the entire network.
###### Hot spot in HOL
A hot spot refers to an output port to which many packets are forwarded. This results in the growing of queues where there're packets to be forwarded to the hot spot.
> Reference: my understanding[name=ernestchu]
> [name=SCC] I am also not sure about this.
> [name=ernestchu] @德伊科爾 feel free to modify the answer above. Also, may I ask for the reference?
> [name=德伊科爾]I just google "hot spot problem in network" https://www.igi-global.com/dictionary/hot-spot-problem/13263
> [name=ernestchu] @德伊科爾 This is about wireless network... cannot tell the connection with the HOL problem.
> [name=德伊科爾]well, it does, but I don't find the keyword "hot spot" in the textbook, since "hot spot" is a problem in wireless network, or it just has no connection with HOL, I guess
> [name=SCC] 我猜 Hot spot 只是單純想說不同 queue 有不同活躍程度，有的比較頻繁利用，所以稱作「熱點」。
> [name=德伊科爾]那是合理的，單純只是挪用現有名詞，只是跟HOL沒有題目相連，或者看不出來
> :fleur_de_lis: [name=德伊科爾] [name=楊志璿]
-------
### 5. ✅ Please explain how does Weighted Fair Queuing (WFQ) operate?
* 到達的分組被分類並在合適的每個類的等待區域排隊
* 首先服務第一類，然後服務第二類，接著再服務第三類(假設有三個類別)，然後重複這種服務模式
* 在發現一個空的類佇列時，立即移向服務序列中的下一類
* 每一個類佇列可以賦予不同的權重，服務不同的數量
##### Round robin
Switch between the queues to serve in a circular manner. For example, supposed there're three queues marked as class 1, 2 and 3, respectively. If there're packets in all three queues, the switch serves Th the order of 1, 2, 3, 1, 2, 3, …. If one of the queue is empty, then check the next queue immediately.
##### WFQ
Inherited from round robin, but each queue, $i$, is assigned a weight, $w_i$. Assume an idealized case where packets are contiunous and transmission is preemptive. Each queue $i$ is guaranteed to be served with a fraction of service equal to $w_i/(\sum w_j)$ **for any queue $j$ that has packets queued for transmission**. That is to say, even if all the queues have packets to transmit, queue $i$ is still guaranteed to achieve a throughput of at least $R \cdot w_i/(\sum w_j)$, where $R$ is the transmission rate and $\sum w_j$ is the sum over all queues.
> :fleur_de_lis: [name=ernestchu] [name=TCat] [name=楊志璿][name=J]
-------
### 6. ✅ Please fill the missing pan of the below graph. The MTU is set to 1620 bytes.
| length | fragflag | offset |
| ------ | -------- | ------ |
| 1620 | 1 | 0 |
| 1620 | 1 | 200 |
| 800 | 0 | 400 |
length ---> MTU
4000 - 20 = (1620 - 20) + (1620 - 20) + (800 - 20)
offeset ---> data / 8 ---> data(MTU-header 20bytes) ---> 1600/8
>:fleur_de_lis: [name=宇一] [name=楊志璿] [name=TCat] [name=蔡東霖]
-------
### 7. 🔰 Please give four examples to demonstrate the applications of encapsulation methodology in networks.
#### HTTP
```HTTP
HTTP/1.1 200 OK
Date: Sat, 09 Oct 2010 14:28:02 GMT
Server: Nginx
Last-Modified: Tue, 01 Dec 2009 20:18:22 GMT
ETag: "51142bc1-7449-479b075b2891b"
Accept-Ranges: bytes
Content-Length: 29769
Content-Type: text/html
<!DOCTYPE html... (here comes the 29769 bytes of the requested web page)
```
The render of browser only takes care of the content **instead** of the HTTP header.
#### TCP
```
TCP Header
TCP data
```
The application layer only takes care of the payload in the segment **instead** of TCP header, TCP states....
#### UDP
```
UDP Header
UDP data
```
The application layer only takes care of the payload in the segment **instead** of UDP header...
#### IP
```
IP Header
IP data
```
The transport layer only takes care of the payload in the datagram **instead** of IP header, routing issues...
> [name=セシリアは俺の嫁]
> :fleur_de_lis: [name=楊志璿] [name=ernestchu]
-------
### 8. 🔰 Please draw a graph to explain the operations of NAT (network address translation). What are its advantages and disadvantages?
##### Advantages
* 提供 IPv4 用光的緩衝（也讓 v4 更有彈性）、有比較安全一點（減少接觸面積）。
> [name=ernestchu] 減少接觸面積？
>> My murmur...
>> 因為 IPs $\cdot$ ports $\sim$ 長 $\cdot$ 寬
>> 某種程度上也是一種面積
##### Disadvantages
* 無法從外部建立連線至內部（除非特殊設定），NAT 內部用戶沒有完整的 flexibility
* The port numbers are meant to be used for addressing processes, not for addressing hosts.
* Routers are meant to be layer 3. However, NAT violates this principle that hosts should be talking directly with each other, without interfering nodes modifying IP addresses, much less port numbers.
> [name=宇一]
>https://zh.wikipedia.org/wiki/%E7%BD%91%E7%BB%9C%E5%9C%B0%E5%9D%80%E8%BD%AC%E6%8D%A2
>照抄 阿不然還能怎樣
>> [name=SCC] Accepted
> :fleur_de_lis: [name=楊志璿] [name=ernestchu]
>請問"用光"是什麼意思，地址的space嗎 by TCat
>> 所有 IPv4 address 已分配給 ISP [name=SCC]
> [name=ernestchu] 問個問題，NAT 會改 datagram 的 src/dst adddress ，那 transport layer header 的 port 呢？
>> 覺得是直接改，像是一種映射 [name=SCC]
>>> 直接進到 datagram payload 去改？ [name=ernestchu]
>>>> 應該還是要解封裝，因為 IP header 長度不固定(v4) [name=SCC]
-------
### 9. ✅ Please list and compare IPv4 and IPv6. Please at least identify three major differences. Please also explain the considering points of making such changes.
> [name=德伊科爾]幫我畫個表格之類的
* IPv4 : 32 bits 地址空間、至少20 bytes的可變長度header
* IPv6 : 128 bits地址空間、40 bytes的header
1. 因為新的子網和IP節點以相當驚人的增長率成長，32 bits的地址空間已用盡，而將bits增加到128則使得全世界有用不盡地址
2. 許多IPv4的字段已被捨棄或作為選項，40字節定長的header允許路由器更快地處理IP數據報，新的選項編碼允許進行更靈活的選項處理
3. IPv6新增flow label可用於給特殊串流的分組加上標籤，以要求發送方進行特殊處理，例如實時服務的串流
| | IPv4 | IPv6 |
| ------ | -------- | -------- |
| addr | 32 bits | 128 bits |
| attr | 冗 | 簡 |
| Header | 20 bytes | 40 bytes |
刪除不常用或不必要之 attr.
* Several fields appearing in the IPv4 datagram are no longer present in the IPv6 datagram
1. IPv6 does not allow fragmentation and reassembly since it's a time-consuming operation. If the datagram is too large for the outgoing link, the router simply drops it and sends a **Packet Too Big** message back to the sender.
2. IPv6 does not contain checksum since both major protocols from transport-layer (TCP, UDP) and link-layer (Ethernet) perform checksumming.
3. An option field is no longer a part of the IPv6. The `next header` field in the header can not only be TCP or UDP but also be an options field, i.e., the options field is one of the possible `next header`.
> :fleur_de_lis: [name=ernestchu] [name=楊志璿] [name=lattalab]
-------
### 10. ✅ The following figure shows flow table entries of OpenFlow for SDN networks. Please use it to show the flexibilities of SDN networks compared to traditional routers.
|| Traditional | SDN |
|-|-|-|
|Rule|Use addresses as keys | Use one or more fields in three layers' headers as keys |
|Action| Forwarding, dropping | Forwarding, dropping, modifying fields |
|Application| Router(L3) | Router(L3), Switch(L2), NAT, Firewall, Load-balancer|
|Matching policy|Longest prefix matching|Priority in each entry|
* 在OpenFlow1.0 的匹配規則中，允許對來自三個層次(鏈路層、網路層、運輸層)的header進行動作匹配(和先前所學的分層原則違背)，其中可使用12個值進行動作匹配
* 每個flow table的項目都可能有零或多個動作列表，這些動作決定了這個packet的處理，其中最為重要的動作可能是 :
* 轉發
* 丟棄
* 修改header字段
* 透過匹配動作，可以注意到這些packet switch的行為能夠被安排(編程)，例如 :
* 簡單的轉發: 參考每個路由器當中flow table的值進行轉發
* 負載均衡 : 參考上圖考慮以下場景，其中來自主機h3發送往10.1.\*.\*的datagram將經由s1和s2之間的直接鏈路轉發，而來自主機h4發送往10.1.\*.\*的datagram將經由s2和s3的鏈路轉發，最後才轉發到s1，在這種情況下，其flow table將如下圖。注意到這種功能並不能通過基於IP目的地轉發實現
* 防火牆功能 : 參考上圖考慮以下場景，其中s2僅希望接收來自與s3相連的主機所發送的流量，在這種情況下，其flow table將如下圖。如果在s2的flow table中沒有其他項目，則僅有來自10.3.\*.\*的流量將被轉發到與s2相連的主機(其他的將可能被丟棄或其他動作，但不會被轉發到s2相連的主機)
> :fleur_de_lis: [name=德伊科爾] [name=ernestchu] [name=楊志璿]
> [name=德伊科爾]備註:flow table允許使用萬用字元"\*"，也就是只要前綴匹配，後面是多少都無所謂
> 在OpenFlow的flow table項目中，"Switch Port"用來表示某台接收到packet的switch，是從哪個輸入端口接收到該packet，所以在負載均衡中，可以用來辨識是來自何處的輸入端口，進而匹配動作，而動作中的Forward(?)，則是轉發到自身的某個輸出端口進行輸出
>> wildcards 沒有限制一定是用在 prefix matching 吧。而且在 OpenFlow 中每個 entry 都有自己的 priority ，當 match 到多個 entry 的時候會依照他們的 priority 來決定 [name=ernestchu]
> [name=德伊科爾]你是對的，只是在本題中我沒有打算全部說完，那很浪費時間，但是可以加在備註中，如果你想要做補充，歡迎自己增加
> [name=羅世瑋]Traditional router 的 action 是否應該包含 drop 而不是只有 forwarding?
>> [name=德伊科爾]我認為，是的，顯而易見的例子是當TTL超過的時候，他可能只是忘了填
-------
### 11. ✅ Please write the pseudo code for Dijsktra's algorithm.
```pseudo=
Initialization:
N^ = {u}
for all nodes v
if v is a neighbor of u
then D(v) = c(u,v)
else D(v) = infinite
loop:
find w not in N^ such that D(w) is a minimum
add w to N^
update D(v) for each neighbor v of W and not in N^:
D(v) = min(D(v), D(w)+c(w,v))
until N^ = N
```
> :fleur_de_lis: [name=楊志璿] [name=德伊科爾] [name=蔡東霖]
-------
### 12. ✅ Use the following figures to explain how Dijsktra algorithm works step by step.
>[name=宇一]
1. 在初始化步驟中，u到其直接連接的相鄰節點v、x、w，目前已知的最小成本路徑，分別被初始化為2、1、5。前往y、z的成本被設定為無限大。
2. 第一次循環中，檢視尚未加入N’的節點，並找出前一輪循環結束後擁有最小成本的節點。所以將節點x加入集合N’。然後更新所有節點v的D(v)，產生表格第二行的結果。
3. 第二次循環中，v、y都有最小成本2的路徑，隨機選中一條，將y加入N’中。對於尚未加入N’中的v、w、z，透過演算法更新成本，產生第三行結果。
4. 以此類推
執行完畢後，針對每一個節點，我們都會知道在從來源端前往此節點的最小成本路徑，此節點的前一個節點為何。依此方式我們可以知道來源端到所有目的端的完整路徑。
<!-- > [name=建瑋]第二張圖是第 13 題的
> 可參考 Chapter 5 的 ppt 第 28 頁 印象中這部分有說過會考
> fixed [name=楊志璿] -->
> :fleur_de_lis: [name=楊志璿][name=蔡東霖][name=alice]
-------
### 13. 🔰 Bad News travels slow for Bellman-Ford Algorithm. Please explain the slow convergence time of the following graph step-by-step. How many iterations are needed?
1. 在連接開銷變化之前，$D_y(x)=4, D_y(z)=1, D_z(y)=1, D_z(x)=5$。在$t_0$時刻，$y$檢測到與$x$的連接開銷變化 $4\rightarrow60$，$y$重新計算$y$到$x$新的最低開銷，其值$D_y(x) = min\{c(y,x)+D_x(x), \ c(y,z)+D_z(x)\} = min\{60+0, \ 1+5\} = 6$ (因為$y$還沒有收到來自$z$的開銷更新，$y$相信能透過$z$花費5到達$x$)
2. $y$已經計算完到$x$新的開銷，並在$t_1$時刻將該向量通知$z$
3. 在$t_1$後的某個時間，$z$收到$y$的新距離向量，指示了$y$到$x$的最低開銷為6，開始計算新的路徑開銷 $D_z(x) = min\{50+0, \ 1+6\} = 7$ ($z$理所當然知道自己與$x$的直接開銷為50，當收到來自$y$的提示指出$y$能以開銷6到達，而$z$能以開銷1到達$y$，故選擇從$y$送到$x$)
4. $z$第一次算出開銷7，那麼$y$第二次就會算出開銷8，以此類推直到開銷$min\{50, D_z(x)\} = 50$ =>第44次迭代
$t_0: D_z(x)=5$
$t_1: D_y(x)=6$ $\leftarrow$ 偶數是 $D_y(x)$
$t_2: D_z(x)=7$
$t_3: D_y(x)=8$
$\dots$
$t_k: D_y(x)=50$
$k=45-5=45$
> :fleur_de_lis: [name=宇一] [name=楊志璿]
>[name=ernestchu] 是直到
>$D_y(x) = 50$
>$D_z(x) = \min\{50, 1+D_y(x)\} = 50$
>在 z 那邊因為 no update 所以進入 quiescent state，才算 converge 吧？
>不過這樣答案會是 45 ... 不知道課本的 converge 是什麼
>課本 iterations 的定義：message exchanges between y and z
>> 投影片(5-28)寫 44，我是信了，反正這是 impl. def. 所以 44 45 應該都可
>> 意見太多還要跟助教反應，我累[name=楊志璿]
>>> 教授說是50-(5+1)= 44[name=R]
-------
### 14. 🔰 Please use a table to compare advantages and disadvantages of LS and DV algorithms.
> [name=德伊科爾]幫我畫個表格
* DV : 每個節點僅與它直接相連的鄰居交談、message複雜度=O(1)、算法收斂速度較慢，可能會遇到路由選擇環路，還會遭遇無窮計數問題、健壯性較弱
* LS : LS算法需要全域所有資訊、message複雜度=O(|N||E|)、算法收斂速度=O(|N^2|)、健壯性較強
| | DV | LS |
| ------------- | -------------------------------- | ------------- |
| | 每個節點僅與它直接相連的鄰居交談 | 需要全部資訊 |
| message複雜度 | exchange between neighbors only | $O(\|N\|\|E\|)$|
| 算法收斂速度 | 慢 | =O(\|N^2\|) |
| 健壯性 | 弱 | 強 |
* N=節點集合，E=鏈路集合，message=每個節點知道網路中每條鏈路的開銷，健壯性(Robustness)=對某些路由器發生故障、行為錯亂或遭受蓄意破壞時的情況反應
-------
### 15. 🔰 Please use the following graph to explain the functions of a boundary router, a backbone router, an area router, and an internal router, and the hierarchical OSPF.
* boundary router: An autonomous system boundary router is a router that is connected by using more than one routing protocol and that exchanges routing information with routers autonomous systems.
* backbone router: A backbone router has an interface to the backbone area. Backbone routers may also be area routers, but do not have to be.
* area router: An area border router is a router that connects one or more areas to the main backbone network.
* internal router: An internal router has all its interfaces belonging to the same area.
* Hierarchical OSPF:
* OSPF的自治系統可以階層式地設定為多個區域。每個區域都會執行自己的OSPF狀態連結繞送演算法，而區域內的每台路由器都會將自己的連結狀態廣播給區域內所有其他的路由器。每個區域中都會有一台或多台區域邊境路由器負責將封包繞送到區域之外。AS內會有唯一一個OSPF區域被設定為主幹區域，負責在AS的其他區域之間繞送資料。
-------
### 16. 🔰 Please use the following graph to explain how to emulate the bus architecture (logically) by the star architecture and describe how it works.
Each spoke run a seperated protocol to their port, just like the bus method but not collide with each other.
Take this graph as an example. Consider $A$ want to talk with $D$, $B$ want to talk with $C$.
Only one thing that $A$ has to do is to speak with $S_1$, just like the bus architecture. And $S_1$ speaks to $S_4$, $S_4$ speaks to $S_2$, $S_2$ speaks to $D$.
And if $B$ want to talk with $C$. $B$ will talk to $S_1$, just like $B$ would talk to bus.
-------
### 17. 🔰 Please explain the following graph of the SDN control/data plane interaction which consists of six steps.
* 假設switch s1和s2之間的鏈路斷開，因此除了s3外，s1,s2,s4的轉發表規則都受到影響
* 1.switch s1遭遇自身與s2之間的鏈路故障，使用OpenFlow"端口狀態"報文向SDN伺服器通報該鏈路狀態的更新
* 2.SDN控制器接收指示鏈路狀態更新的OpenFlow報文，並通知鏈路狀態管理器，由管理器更新鏈路狀態資料庫
* SDN controller receives OpenFlow message, updates link status info
* 3.實現Dijkstra算法的鏈路狀態路由選擇的網路控制應用程式在鏈路狀態更新時將獲得通告，應用程式接收該鏈路狀態更新的通告
* 4.該程式已得到更新的鏈路狀態，並參考狀態管理層的其他組件，然後計算新的最低開銷路徑
* 5.該程式與流量表管理器互動，流量表管理器更新流量表
* 6.流量表管理器則使用OpenFlow協議更新switch s1,s2,s4的流量表，其中s1將經由s4將分組目的地指向s2，s2將經由s4開始接受來自s1的分組，s4必須轉發來自s1且目的地為s2的分組
-------
### 18. 🔰 Please explain the following lines about CRC, and then use an example to explain it.
Assume there is a pre-shared key G, and a sequence of binary data D.
$D\cdot2^r \equiv nG \oplus R$
> :fleur_de_lis: [name=楊志璿]
-------
### 19. 🔰 What is CSMA/CD? (1) Please write a pseudo code for it. (2) Please draw a picture to show the early abort of transmission if a collision is detected along the time.
> [name=德伊科爾]整體步驟是這樣，若有更好的寫法請自行更新
```
1.adapter從網路層獲得 Datagram，封裝進連接層的幀，並放入adapter的cache中
2.若adapter偵聽到channel為閒置，開始傳輸幀，若channel繁忙，則等到偵聽到沒有訊號能量才開始傳輸
3.傳輸過程中，adapter仍在監視該渠道是否有來自其他adapter的訊號能量
4.若未偵聽到，則完成該幀的傳輸，否則終止傳輸
5.終止傳輸後，等待一個隨機的時間量，並返回步驟2
```
Draw a picture:
> :fleur_de_lis: [name=楊志璿]
-------
### 20. 🔰 Please explain the operations of data over cable service interface spec (DOCSIS) below.
每一個上傳通道會分割成一些時間區段，每一時段包含多個迷你槽，在迷你槽的期間中纜線數據機便可以傳訊匡給CMTS。CMTS透過送出MAP控制訊息到下傳通道上，來指定哪一台纜線數據機可以在該控制訊息所指定的時間區段中哪一個迷你時槽中傳資料。因為迷你槽被明確地分給纜線數據機，CMTS可以保證在一個迷你槽的期間中是不會發生碰撞。
有一段特別的迷你槽集合是專門讓纜線數據機傳送出迷你槽請求訊匡給CMTS。但這些迷你槽請求訊匡是隨機存取的方式傳出，故有可能會發生碰撞。當碰撞發生，纜線數據機使用二進制的指數倒退方式來延後他，把他的迷你槽請求訊匡重傳到一未來時槽的時間。
-------
### 21. 🔰 What is TDMA? What is FDMA? What is random access? Can you also give an example for all of these?
* TDMA: 將時間劃分為time frame，並進一步劃分每個frame為N個slot，然後將每個slot分配給N個節點中的一個，無論何時某個節點有segment要傳輸，它都將在循環的TDM frame中指派給它的slot進行傳輸。通常slot長度可傳輸完一個segment
* FDMA: 在單個較大的R bps渠道劃分為不同的頻段(R/N的頻寬)，並把每個頻率分配給N個節點中的一個
* random access:在隨機存取協議中，一個傳輸節點總是以渠道的全速R bps進行發送，當有碰撞時，涉及碰撞的節點反覆重發它的幀，直到該幀無碰撞通過為止，但並非立刻重發，而是重發前先等待一個隨機時延
-------
### 22. 🔰 Use two routers and ARPs to explain how to route a frame from a LAN to another LAN.
* ans: 
> :fleur_de_lis: [name=楊志璿]
-------
### 23. 🔰 Please explain how to implement IEEE 802.1Q VLANs across multiple switches and draw a graph to demonstrate it.
802.1Q訊框是由標準的乙太網路訊框加上標頭中加入四位元組的VLAN標籤所構成。VLAN會指出訊框所屬的VLAN為何。VLAN標籤會由交換記載VLAN幹線的傳送端加入到訊框中，然後在幹線的接收端由交換器所解析並予以移除。VLAN標籤本身是由2位元組的標籤協定識別代碼欄位，2位元組的標籤控制資訊所構成，後者包含了12位元的VLAN識別代碼欄位，3位元的優先權欄位。
> Fixed: 匡 -> 框[name=SCC]
- **trunk port**: carries frames between VLANS defined over multiple physical switches
- 802.1q protocol adds/removed additional header fields for frames forwarded between trunk ports
-------
### 24. 🔰 Please use the following format to explain the multiprotocol label switching (MPLS).
* MPLS目標 : 基於固定長度標籤和virtual circuit的技術，在不放棄基於目的地IP封包轉發的基礎設施的前提下，透過選擇性地標示封包並允許router基於固定長度的標籤(而非IP地址)轉發封包，更重要的是，這些技術與IP共同運作
* MPLS的header增加在鏈路層和網路層的header之間
* 該header具有label、預留3 bits的實驗片段、1bit的S片段用於指示一系列"stack"的MPLS header的結束(非本章討論範圍)和TTL壽命片段
* 能夠使用MPLS增強的幀的路由器稱為label-switched router(也只有這種router能用MPLS，否則會混淆)，它能通過在轉發表查找MPLS標籤，然後立即將該MPLS幀轉發給適當的端口來轉發，而不需要在網路層提取IP地址並在轉發表中執行最長前綴匹配
-------
### 25. 🔰 When you use a browser to make a HTTP request, please describe the process of the DHCP, DNS, ARP. and then finally the HTTP request and reply.
Step $[1,3]$: DHCP discover
Step $[4,5]$: DHCP offer
+Step $(5,6)$: DHCP request
Step $[6,7]$: DHCP ACK
Step $[9,10]$: ARP request
Step $\{11\}$: ARP response
Step $\{8,13\}$: DNS resolve request
Step $[14,15]$: Routing
Step $[16,17]$: DNS resolve response
Step $[18,21]$: TCP 3-way handshaking
Step $[22,23]$: HTTP GET request
Step $\{24\}$: HTTP GET reply
* **友情提示：本題的解答相當冗長，請自行斟酌填寫**
* 假設目標位址為 www.google.com
* 1.裝置的作業系統生成一個DHCP請求，並將請求放入具有目的port號和本地port號的UDP segment，該UDP segment則被放置在一個具有廣播IP目的地址(255.255.255.255)和本地IP地址(0.0.0.0)的IP datagram中，因為此裝置還沒有一個IP位址
* 2.該IP datagram被放置在乙太網路的幀中。該幀具有目的MAC地址FF:FF:FF:FF:FF:FF，使該幀能廣播到與switch連接的所有設備
* 3.switch將在其輸出port廣播該幀
* 4.DHCP伺服器端口收到該幀，上交至網路層，該datagram的廣播IP目的地址指示了該datagram應當由節點的上層協定處理，則從中抽取UDP segment上交至UDP，DHCP再被從UDP segment中取出。此時dhcpd取得該請求
* 5.dhcpd生成某IP地址以及DNS伺服器的IP,gateway router的IP和子網路遮罩的DHCP ACK segment，最終放入幀中，目的MAC是請求裝置的MAC地址
* 6.該DHCP ACK發送給switch。switch根據self-learning的特性(即 update switch table)，尋址到請求裝置並向該輸出端口轉發
* 7.請求裝置接收到DHCP ACK，最終提取出DHCP message。裝置紀錄下請求到的IP和DNS server的IP，並在IP轉發表中紀錄gateway router的地址 (至 /etc/resolv.conf, /etc/network/interfaces)
* 8.裝置的作業系統生成一個DNS查詢message，將字串" www.google.com "放入該message的問題段中，並最終打包成幀
* 9.該幀將轉發至gateway router。然而在上述的步驟裡，仍尚未取得gateway router的MAC地址，故需使用ARP
* 10.裝置生成一個具有目的IP地址的ARP查詢message，將該message放置在廣播目的地址(FF:FF:FF:FF:FF:FF)的乙太網路幀中，由switch發送該幀，switch廣播給其所有連接的設備，包含gateway router
* 11.gateway router收到該ARP查詢，並準備一個ARP reply向switch發送，並最後被請求裝置收到
* 12.裝置接收到該reply並提取gateway router的MAC地址
* 13.裝置向switch發送DNS查詢，並由switch轉交給gateway router
* 14.gateway router收到該DNS查詢datagram，查找該datagram的目的地址並根據轉發表決定轉發至何處的router
* 15.接收到該查詢的router檢查目的地址，並最將該請求轉發向DNS server，而轉發表已根據域內協定以及BGP所填寫
* 16.DNS server收到該查詢，在資料庫中查找" www.google.com "並找到該IP地址的紀錄，生成DNS reply並發送回去
* 17.裝置提取出 www.google.com 的IP地址，準備連線
* 18.裝置生成TCP socket用於向 www.google.com 發送HTTP GET，並首先和 www.google.com 中的TCP socket進行三手交握
* 19.該TCP SYN在router之間朝著 www.google.com 轉發，透過使用router之間的轉發表
* 20.TCP SYN到達 www.google.com 。該伺服器的TCP生成一個與請求裝置之間的TCP socket，產生一個TCP SYNACK並轉發出去
* 21.TCP SYNACK最終到達請求裝置，上交到該裝置的TCP socket，進入連線狀態
* 22.裝置瀏覽器生成包含獲取URL的HTTP GET message，並寫入TCP socket，然後交付到 www.google.com
* 23.www.google.com 的伺服器收到該message，並生成一個HTTP response message，將請求的web頁面內容置入，寫入TCP socket發送
* 24.裝置的瀏覽器從socket讀取HTTP response message，提取出網頁資源，並交付瀏覽器渲染web頁面
## Mixed
### 1. ❌ Please briefly describe how ATM networks classify and achieve different classes of services.
---
### 2. ❌ What is a virtual circuit network and what is a datagram network? Please draw diagrams to explain them.
---
### 3. ❌ What is longest prefix matching? Please also use an example to explain it.
---
### 4. ❌ Please draw diagrams to show input port functions and output port functions for a router and explain their functions briefly.
---
### 5. ❌ What is a subnet? What is CIDR (Classless InterDomain Routing)? Explain the meaning of 140.1.1.0/23 in IPv4 addressing. And what is DHCP?
---
### 6. ❌ Please explain what is NAT traversal problem? Please draw two possible solutions to resolve the NAT traversal problem.
---
### 7. ❌ Please list four major changes from IPv4 to IPv6 and explain the considering points of making such changes.
---
### 8. ❌ Please write pseudo codes for link state algorithm and Bellman-Ford algorithm, respectively.
---
### 9. ❌ Please explain the advantages and disadvantages of center-based tree reverse path forwarding in multicasting and write pseudo codes for them, respectively. Based on your pseudo codes above, please write pseudo codes for Protocol Independence Multicast (PIM).
---
### 10. ❌ What is TDMA? What is FDMA? And what is random access?
---
### 11. ❌ Please explain the operation of DOCSIS (data over cable service interface spec).
---
### 12. ❌ In the class we describe how to Google a web page in a day in the life of a web request. Please explain it as detailed as you remember.
---
### 13. ❌ What is CSMA/CD? What is CSMA/CA? Please use graph to demonstrate the advantage of using CD and CA, respectively. Please also describe how the backoff algorithm in CSMA/CD works?
---
### 14. ❌ What is hidden terminal problem and what is exposed terminal problem? Please draw pictures to explain them briefly.
---
### 15. ❌ Please explain how to handle mobility on mobile IP and cellular networks, respectively. Please use graphs and list the sequence of messages.
---
### 16. ❌ 111-11-1-1-1 and 1-1111-111 are two orthogonal codes or chipping sequences for CDMA. Please use those two codes and draw a graph to show we can transmit two data bits (streams) within the same frequency range and retrieve two data bits (streams) correctly at receivers.
---
### 17. ❌ A router consists of input ports, high-speed switching fabric, routing processor, and output ports. Please draw a block diagram for a router which include above mentioned modules and explain each module, respectively.
---
### 18. ❌ What is Head-of-the-line (HOL) blocking? Also explain what is hotspot in a network? And how does butterfly effect occur within a switching fabric?
---
### 19. ❌ Please fill the fields of the graph with the question mark.
---
### 20. ❌ From the following graph, please explain what is a subnet? And what is an interface?
---
### 21. ❌ Please fill the fields of the following graph with the question mark.
---
### 22. ❌ Please use the Dijkstra algorithm to construct the routing paths step by step.
---
### 23. ❌ Please list comparisons of LS algorithm and DV algorithm to some details.
---
### 24. ❌ Write a pseudo code for Reverse Path Forwarding (RPF) and use a graph example to explain it.
---
### 25. ❌ Please list four major changes from IPv4 to IPv6 and explain the considering points of making such changes.
---
### 26. ❌ What is a collision in the MAC layer? Please list four ways to avoid it.
---
### 27. ❌ Please draw a picture to explain why slotted Aloha is more efficient than unslotted Aloha (pure Aloha).
---
### 28. ❌ Please explain the operation of DOCSIS (data over cable service interface spec).
---
### 29. ❌ In the class we describe how to Google a web page in a day in the life of a web request. Please explain it as detailed as you remember.
---
### 30. ❌ What is MPLS? The speed of a router can be greatly increase by adopting the MPLS technique compared to the traditional router without adopting the MPLS technique. Why? Is it possible that by adopting the MPLS technique, the router can be as fast as the bridge using the same hardware technology?
---
### 31. ❌ What is hidden terminal problem and what is exposed terminal problem? Please draw pictures to explain them briefly. Draw a picture to show how RTS and CTS are used in CSMA/CA to avoid collisions.
---
### 32. ❌ Please briefly describe what is the difference about traditional routing algorithms and SDN?
---
### 33. ❌ memory vs bus vs interconnection network
---
### 34. ❌ three scheduling policies
Sign in with Wallet
Connect another wallet