杭州电子科技大学研究生课程考试卷 P2. Please to fill in the blanks about the pseudocode for Dijkstra's algorithm with mirroring 考试课程 学 院 考生姓名 考试日期 年 月 日 专 业 学 号 （完 整） 任课教师 姓 名 成 绩 P1. Please to fill in the blanks about A typical sequence of TCP states visited by a client TCP (10 points) Python syntax. (10 points) function Dijkstra(Graph, source): dist[source] := 0 // Distance from source to source is set to 0 for each vertex v in Graph: // Initializations if v != source dist[v] := infinity // Unknown distance function from source to each node set to infinity add v to Q // All nodes initially in Q while (1) is not empty: // The main loop v := vertex in Q with min dist[v] // In the first run-through, this vertex is the source node remove v from Q for each neighbor u of (2): // where neighbor u has not yet been removed from Q. alt := (3) + length(v, u) if alt < (4) : // A shorter path to u has been found dist[u]:= (5) // Update distance of u return dist[] end function Q、V、dist[v] dist[u]、alt SYN、ACK、FIN、FIN_WAIT_1、FIN P3. Please to fill in the blanks about the Simplified TCP sender. (8 points) /* Assume sender is not constrained by TCP flow or congestion control, that than MSS in size, and that data transfer is in one direction only. */ NextSeqNum=InitialSeqNumber SendBase=InitialSeqNumber loop (forever) { switch(event) event: data received from application above create TCP segment with sequence number NextSeqNum if (timer currently not running) start timer 第 1 页 共 4 页 

pass segment to IP NextSeqNum= (1) break; event: (2) number of addresses for interface 2 = number of addresses for interface 3 = retransmit not-yet-acknowledged segment with smallest sequence number start timer break; event: ACK received, with ACK field value of y if (y > SendBase) { SendBase= (3) P5. Assuming TCP Reno is the protocol experiencing the behavior shown in the following figure, answer the following questions. In all cases, you should provide a short discussion if (there are currently any not-yet-acknowledged segments) justifying your answer. (12 points) (4) } break;
 } /* end of loop forever */ NextSeqNum+length(data), timer timeout, y, start timer P4. Consider a datagram network using 8-bit host addresses. Suppose a router uses longest prefix matching and has the following forwarding table: Prefix Match Interface 00 010 011 10 11 0 1 2 2 3 For each of the four interfaces, give the associated range of destination host addresses and the number of addresses in the range. Link Interface Destination Address Range 00000000 through 00111111 0 01000000 through 01011111 1 01100000 through 01111111 2 10000000 through 10111111 2 11000000 through 11111111 3 number of addresses for interface 0 = number of addresses for interface 1 = (1) Identify the intervals of time when TCP slow start is operating. 
 (2) After the 16th transmission round, is segment loss detected by a triple duplicate ACK or by a timeout? (3) Whatistheinitialvalueofssthreshatthefirsttransmissionround? 
 (4) Whatisthevalueofssthreshatthe24thtransmissionround? 
 (5) Assuming a packet loss is detected after the 26th round by the receipt of a triple duplicate ACK, what will be the values of the congestion window size and of ssthresh? (6) k. Again suppose TCP Tahoe is used, and there is a timeout event at 22nd round. How many packets have been sent out from 17th round till 22nd round, inclusive? a) TCP slowstart is operating in the intervals [1,6] and [23,26] b) After the 16th transmission round, packet loss is recognized by a triple duplicate ACK. If there was a timeout, the congestion window size would have dropped to 1. c) The threshold is initially 32, since it is at this window size that slow start stops and congestion avoidance begins. d) The threshold is set to half the value of the congestion window when packet loss is detected. When loss is detected during transmission round 22, the congestion windows size is 29. Hence the threshold is 14 (taking lower floor of 14.5) during the 24th transmission round. 第 2 页 共 4 页 6426=3225=9632642256=+=+6426=

e) The threshold will be set to half the current value of the congestion window (8) when the loss occurred and congestion window will be set to the new threshold value + 3 MSS . Thus the new values of the threshold and window will be 4 and 7 respectively. f) round 17, 1 packet; round 18, 2 packets; round 19, 4 packets; round 20, 8 packets; round 21, 16 packets; round 22, 21 packets. So, the total number is 52. P6. Suppose N packets arrive simultaneously to a link at which no packets are currently being transmitted or queued. Each packet is of length L and the link has transmission rate R. What is the average queuing delay for the N packets? (10 points) The queuing delay is 0 for the first transmitted packet, L/R for the second transmitted packet, and generally, (n-1)L/R for the nth transmitted packet. Thus, the average delay for the N packets is: (L/R + 2L/R + ....... + (N-1)L/R)/N = L/(RN) * (1 + 2 + ..... + (N-1)) = L/(RN) * N(N-1)/2 = LN(N-1)/(2RN) = (N-1)L/(2R) P7. What are the SNAT(source network address translation) and DNAT(destination network address translation) (10 points) SNAT changes the source address of the packets passing through the Brocade vRouter. SNAT is typically used when an internal (private) host needs to initiate a session to an external (public) host; in this case, the device that is performing NAT changes the private IP address of the source host to some public IP address, as shown in the following figure. In “masquerade” NAT (a common type of SNAT), the source address of the outgoing packet is replaced with the primary IP address of the outbound interface. The destination address of return packets is automatically translated back to the IP address of the source host. Destination network address translation (DNAT) is a technique for transparently changing the destination IP address of an end route packet and performing the inverse function for any replies. Any router situated between two endpoints can perform this transformation of the packet. DNAT is commonly used to publish a service located in a private network on a publicly accessible IP address. This use of DNAT is also called port forwarding, or DMZ when used on an entire server, which becomes exposed to the WAN, becoming analogous to an undefended military demilitarised zone (DMZ). P8. Consider a DHT with a mesh overlay topology (that is, every peer tracks all peers in the system). What are the advantages and disadvantages of such a design? What are the advantages and disadvantages of a circular DHT (with no shortcuts)? 
 Mesh DHT: The advantage is in order to a route a message to the peer (with ID) that is closest to the key, only one hop is required; the disadvantage is that each peer must track all other peers in the DHT. Circular DHT: the advantage is that each peer needs to track only a few other peers; the disadvantage is that O(N) hops are needed to route a message to the peer that is closest to the key. P9. Please to compare the IPV4 and IPv6 ➢ Larger address space ➢ Multicasting ➢ Stateless address autoconfiguration ➢ Network-layer security ➢ Simplified processing by routers ➢ Mobility ➢ Options extensibility ➢ Jumbograms ➢ Privacy P10. What is programmable network? What are benefits of Programmable networking over traditional networking? independently from operates by software that A programmable network is one in which the behavior of network devices and flow control is handled network hardware. A truly programmable network will allow a network engineer to re-program a network infrastructure instead of having to re-build it manually. Programmable networking has several benefits over traditional networking: ➢ Reduced long-term costs. ➢ Ability for applications to maintain information about device capabilities. ➢ Ability for networks to respond to application status and resource requirements. P11. (Additional Questions) Design and describe an application-level protocol to be used between an automatic teller machine and a bank’s centralized computer. Your protocol should allow a user’s card and password to be verified, the account balance 第 3 页 共 4 页 

(which is maintained at the centralized computer) to be queried, and an account withdrawal to be made (that is, money disbursed to the user). Your protocol entities should be able to handle the all-too-common case in which there is not enough money in the account to cover the withdrawal. Specify your protocol by listing the messages exchanged and the action taken by the automatic teller machine or the bank’s centralized computer on transmission and receipt of messages. Sketch the operation of your protocol for the case of a simple withdrawal with no errors, using a diagram Explicitly state the assumptions made by your protocol about the underlying end-to-end transport service. (10 points) There is no single right answer to this question. Many protocols would do the trick. Here's a simple answer below: Messages from ATM machine to Server Msg name purpose -------- ------- HELO Let server know that there is a card in the ATM machine ATM card transmits user ID to Server PASSWD User enters PIN, which is sent to server BALANCE User requests balance WITHDRAWL User asks to withdraw money BYE user all done Messages from Server to ATM machine (display) Msg name purpose -------- PASSWD OK ERR ------- Ask user for PIN (password) last requested operation (PASSWD, WITHDRAWL) OK last requested operation (PASSWD, WITHDRAWL) in ERROR AMOUNT sent in response to BALANCE request BYE user done, display welcome screen at ATM Correct operation: client server HELO (userid) --------------> (check if valid userid) <------------- PASSWD PASSWD --------------> (check password) <------------- OK (password is OK) BALANCE --------------> <------------- AMOUNT WITHDRAWL --------------> check if enough $ to cover withdrawl <------------- OK ATM dispenses $ BYE --------------> <------------- BYE In situation when there's not enough money: HELO (userid) --------------> (check if valid userid) <------------- PASSWD PASSWD --------------> (check password) <------------- OK (password is OK) BALANCE --------------> <------------- AMOUNT WITHDRAWL --------------> check if enough $ to cover withdrawl <------------- ERR (not enough funds) error msg displayed no $ given out BYE --------------> <------------- BYE 第 4 页 共 4 页