COMPUTER NETWORK　ＦＩＮＡＬ　ＴＥＳＴ　 ## 2018 1. Please explain the above graph by your understanding to some details. ------- 2. Please draw a generic router architecture and explain its operations. ------- 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? ------- 4. Again please draw a picture to show what is HEad-of-the-Line(HOL) blocking? what is a hot spot problem? ------- 5. Please explain how does Weighted Fair Queuing(WFQ) operate? ------- 6. Please fill the missing part of the above graph. the MTU is set to 1620 bytes. ------- 7. Pleae give four examples to demonstrate the applications of encapsulation methodology in networks. ------- 8. Plese draw a graph to explain the operations fo NAT (network address translation). hat are its advantages and disadvantages? ------- 9. Pleae list and compare IPv4 and IPv6. Pleae at least identify three major differences. Please also explain the considering points of makin gsuch changes. ------- 10. The following figure shows flow table entries of open flow for SDN networks. Pelase use it to show the flexibilities of SDN networks compared to tranditional routers. ------- 11. Please write the pseudo code for Dijsktra's algorithm. ------- 12. Use the below figure to explain how Dijsktra algorithm works step by step. ------- 13. Bad News travels slow for Bellman-For algorithm. Please explain the slow convergence time of the above graph step-by-step. How many iterations are needed? ------- 14. Please use a table to compare advantages and disadvantages of LS and DV algorithms. ------- 15. Please use the above graph to explain the functions fo a boundary router, a backbone router, an area router, and an internal router, and the hierarchical OSPF ``` App-layer can be seperated by session, presentation and application layers in OSI model. And the types, syntax, semantics, and rules of messages are the reponsibitity of the presentation layer. ``` -> how about this The **types** of message exchanged for example request message and receive message. The **syntax** of the various message types, such as the field in the message and how the fields are delineated. The **semantics** of the fields, that is, the meaning of the information in the fields. **Rules of message** for determining when and how a process sends message and responds to messages. > [name=楊志璿] 其實我覺得這頗細@@ 他想怎麼詮釋 Types, Syntax, Sematics 網路也管不著 >> 我 Tag 不到你 > For example: ```javascript= let val = '1234' // The typeof val === 'string' ``` So, what is the type? What is the syntax? What is the sematics? > [name=SCC] I would say this is a text. > Text is also a part of data(anything). ------- 7. Please use a table to compare TCP and UDP, two Internet transport-protocol services, to the point. | Fearures | TCP | UDP | | ------------------ | ---- | ----- | | Reliable | True | False | | Flow control | True | False | | Congestion control | True | False | ------- 8. Please demonstrate how the hot ratio (the data found within the cache) affects the performance of web caches (proxy servers). * 通常而言，當流量強度小於 0.8 時，對應的排隊延遲較小，約為十幾毫秒，假設為 0.01s * 假設從客戶端不經手代理人伺服器，直接連接到目的伺服器的固有網路延遲為 2s (不包含 queueing 時間) * 考慮以下情況 : * 假設 hot ratio 為0.4，代表有 40% 的 request 將幾乎立即被代理人伺服器的 cache 響應，只有 60% 的 request 仍需要由 origin server 提供，則平均延遲為 0.4 * (0.01s) + 0.6 * (2.01s) = 1.21s ------- 9. DNS is a distributed and hierarchical database. Please use the following picture to explain the operations of DNS and how it defenses against DDoS attacks. ![](https://i.imgur.com/Z31o5F3.png) Iterated query: ```sequence Client - LDNS: whois www.amazon.com LDNS - root: Ask root once root - LDNS: NS com LDNS - com: NS www.amazon.com com - LDNS: NS dns.amazon.com(A.B.C.D) LDNS - A.B.C.D: A www.amazon.com A.B.C.D - LDNS: www.amazon.com A E.F.G.H LDNS - Client: www.amazon.com A E.F.G.H ``` > [name=楊志璿] 這樣嗎？ for example,client wants for www.amazon.com * client queries local DNS server to find www.amazon.com * local DNS queries root server to find "com" DNS server(then root server return "com" DNS IP address) * local DNS queries ".com" DNS server to get amazon.com DNS server * local DNS queries amazon.com DNS server to get IP address for www.amazon.com * local DNS return the IP address of www.amazon.com to client * how to against DDoS attacks? * DNS root servers were protected by packet filters, configured to always block all ICMP ping messages directed at the root servers. Further more, most local DNS servers cache the IP address of top-level-domain servers, allowing the query process to often bypass the DNS root server. (參考自課本p.167) > [name=SCC] ![](https://i.imgur.com/oGLqgYI.png) > 根據我測試，只有 **g**.root-servers.net, **k**.root-servers.net 會擋 ping > 所以是：有些 root dns 有擋，有些沒有。全世界共 13 個 root dns. ------- 10. There are four types of DNS, which are type A, NS, CNAME, and MX. Assume www.yahoo.com's "canonical" name is www.server1.yahoo.com whose IP address is A.B.C.D. Then, please use the above picture to perform DNS operation for www.yahoo.com by using the first three types. > Assume you have a Local DNS which is called LDNS, and there is a TLD_DNS which have the resource record (RR) of www.yahoo.com. ```sequence Client - LDNS: whois www.yahoo.com LDNS - TLD_DNS: www.yahoo.com NS TLD_DNS TLD_DNS - TLD_DNS: www.yahoo.com CNAME www.server1.yahoo.com TLD_DNS - TLD_DNS: www.server1.yahoo.com A A.B.C.D TLD_DNS - LDNS: www.yahoo.com A A.B.C.D LDNS - Client: www.yahoo.com A A.B.C.D ``` ::: warning > [name=Ernie] TLD servers usually only have RRs for authoritative server. So the solution should look like this * TLD's RRs * (yahoo.com, dns.yahoo.com, NS) * (dns.yahoo.com, A.B.C.X, A) * dns.yahoo.com's RRs * (www.yahoo.com, www.server1.yahoo.com, CNAME) * (www.server1.yahoo.com, A.B.C.D, A) ::: @Ernie 所以...他是怎麼去問？ > [name=Ernie] > 研究中, try this > ```sh > dig www.nsysu.edu.tw +trace > ``` > 除了最後對 dns.nsysu.edu.tw 的 query 是 type A 外，其餘皆是 NS queries? >> [name=楊志璿] Not sure. The `dig` command is doing the "REAL" DNS query. >> However, this question ask us do some ... "query simulating(?)". I have no idea about this. ------- 11. In video coding. How to save coding rates for video images by spatial coding and temporal coding. * Spatial coding: picture size. * Temporal coding: frame rate ------- 12. Please explain the operations of the client-side and server-side of Dynamic, Adaptive Streaming over HTTP (DASH). Please include why we can watch videos of different qualities at the client's sides by adapting to network conditions. ![](https://i.imgur.com/WTZXWi2.jpg) ------- 13. Please draw a picture to explain the operations of content distribution networks(CDNs). * ![12](https://i.imgur.com/9Lo5uVV.jpg) * 範例中假設了內容供應商NetCinema雇用第三方CDN公司KingCDN來向客戶發送影片 * (1)客戶訪問位於NetCinema的Web網頁 * (2)當客戶點擊某影片連結時(eg. http://video.netcinema.com/6Y7B23V)，該主機向LDNS發出一個對video.netcinema.com的請求 * (3)LDNS將該DNS請求移交到一台用於NetCinema的authoritative DNS，為了將該DNS請求移交給KingCDN，NetCinema的authoritative DNS並不是返回一個IP address，而是返回一個KingCDN域的主機名 * (4)此時，LDNS向KingCDN的DNS發出請求，隨後該KingCDN的DNS指定了某個內容分發伺服器的IP address傳回給LDNS * (5)LDNS向客戶主機轉發該內容伺服器節點的IP address * (6)客戶端收到KingCDN的IP address，隨後向該IP的伺服器建立一條TCP連結，並發出該影片的HTTP GET request ------- 14. Please write a pseudo-code of UDP socket programming for simple client-server interactions. * 下列舉例 : 在python3中建立一個客戶端socket、一個伺服端socket，客戶端會傳送一個字串到伺服端，伺服端將字串全部變成大寫後再回傳給客戶端(使用UDP socket) * client端 ```python= from socket import * serverName = 'hostname' serverPort = 12000 clientSocket = socket(AF_INET, SOCK_DGRAM) message = raw_input('Input lowercase sentence:') clientSocket.sendto(message.encode(), (serverName,serverPort)) modifiedMessage, serverAddress = clientSocket.recvfrom(2048) print(modifiedMessage.decode()) clientSocket.close() ``` * server端 ```python= from socket import * serverPort = 12000 serverSocket = socket(AF_INET, SOCK_DGRAM) serverSocket.bind(('', serverPort)) print("The server is ready to receive") while True: message, clientAddress = serverSocket.recvfrom(2048) modifiedMessage = message.decode().upper() serverSocket.sendto(modifiedMessage.encode(), clientAddress) ``` ------- 15. Both TCP and UDP support multiplexing and de-multiplexing. Please draw pictures to show their difference. * UDP : 當兩個UDP segments具有不同的source IP或source port，卻具有相同destination IP和destination port時，則兩個segments將通過相同的socket抵達相同的process * TCP : 當兩個TCP segments具有不同的source IP或source port，卻具有相同destination IP和destination port時，則兩個segments將被指派到兩個不同的sockets，隨後才抵達相同的process ------- 16. Please fill in the missing parts of Fig. 1 (rdt 3.0) Fig. 1 and filled: ![](https://i.imgur.com/bEGi4CA.png) ![](https://i.imgur.com/3LfimP6.png) ------- 17. Please explain the GBN FSM of Fig. 2 with your words. The ranges should be included in your explanation. Fig. 2: ![](https://i.imgur.com/ASsI1NE.png) ------- 18. Briefly explain the operations of TCP congestion control by drawing a graph of congestion window size versus transmission round. Your explanation must include the slow start phase, the congestion avoidance phase, and the condition of experiencing losses. ------- 19. RFC 1122 and RFC 2581 are about TCP ACKs. For various events at receivers, different receiver actions are taken. Please explain when ACKs are sent immediately and when delayed ACKs are triggered. TCP ACK generation 3-70 in textbook event at receiver -> TCP receiver action 1) Arrival of in-order segement with expected seq#. All of the data up to expected seq# <font color='red'> already ACKed </font>. * Delayed ACK, wait up to 500ms for next segement. if no next segement send ACK. 2) Arrival of in-order segement with expected seq#. one of the data has <font color='red'>pending</font>. * immediately send cumulative ACK, ACKing both in-order segement. 3) Arrival of out-of-order segement higher-than-expected seq <font color='red'>gap detected </font> * immediately send **duplicate ACK**, indicating seq#. of next expected byte. 4) Arrival of segement that partially or completely <font color='red'>fills gap </font> * immediately send ACK, provided that segement start at lower end of gap. ------- 20. Please explain Fig. 3 in detail. Your explanation should include the design methodology behind it by your understanding. Fig. 3: ![](https://i.imgur.com/511EH4Y.png) please introduce for slow start, congestion avoidance and fast recovery. **Slow start** Initially, `cwnd=1`. And `cwnd++` upon receiving **1 ACK**. This results in a **exponential** growth. The below example assume no sequence is lost. (無極生太極，太極生兩儀，兩儀生四象，四象生八卦，八卦演萬物) | cwnd (sent) | ACK | Increment (= 1*ACK) | |-------------|-----|-------------------| | 1 | 1 | 1 | | 2 (1+1) | 2 | 2 | | 4 (2+2) | 4 | 4 | | 8 | 8 | 8 | | 16 | 16 | 16 | Until... - No loss - When `cwnd` reaches `ssth`, enter the **congestion avoidance** state. - Sequence lost - If **triple duplicate ACKs** (because of the lost sequence) are received, enter the **fast retransmit** state - If no ACK is received before **timeout**, enter the **retransmission timeout** state and reset `cwnd=1` **Congestion avoidance** `cwnd = cwnd + 1/cwnd` upon receiving **1 ACK**. This results in a **linear** growth. | cwnd (sent) | ACK | Increment (= (1/cwnd)*ACK) | |-------------|-----|----------------------------| | 16 | 16 | 1/16*16 = 1 | | 17 (16+1) | 17 | 1/17*17 = 1 | | 18 | 18 | 1 | | 19 | 19 | 1 | Until sequence lost and same as **slow start** state... - **triple duplicate ACKs**: enter the **fast retransmit** state - **timeout**: enter the **retransmission timeout** state and reset `cwnd=1` **Fast retransmit** Fast retransmit aims at sending the lost packet **immediately** without waiting for the timeout - Duplicate ACKs may be caused by 1. A lost packet 1. An out-of-order packet - The sender assumes that packet loss occurs upon receiving 3 or more duplicate ACKs - After successfully retransmitting the lost packet, set `ssth=cwnd/2` and reset `cwnd=1` then go back to **slow start** state. **Retransmission timeout** If a timeout occurs, the sender sets `ssth=cwnd/2` and return to the slow start state.