University of California, IrvineEECS 1482013 Final Exam Solutions-QUESTIONS WITH VERIFIED ANSWERS-GRADED A+

Document Content and Description Below

Introduction to Computer Networks Fall 2013 CompSci 132/EECS148 Sample Final Exam - Solution Sketch (Friday, Dec. 13th, 2013, 1:30-3:30pm) Open books, open notes. Computers and cellphones should b ... e turned off. Student’s Last Name: Student’s First Name: Student ID: Email: Problem # Points Out of Total 1 20 2 20 3 30 3 30 Total 100 Academic Honesty Policy: I agree to abide by the UCI Academic Senate Policy on Academic Honesty (Appendix VIII.B), which specifies that students have responsibility for: 1. Refraining from cheating and plagiarism. 2. Refusing to aid or abet any form of academic dishonesty. 3. Notifying professors and/or appropriate administrative officials about observed incidents of academic misconduct. The anonymity of a student reporting an incident of academic dishonesty will be protected. Student’s Signature: GOOD LUCK! 11. (20 Points) TCP. Consider the following plot of TCP window size as a function of time (counted in # RTTs). The coordinate of each turning point has been marked in the plot. ! Answer: See figure below for an overview of the answer. 45 --. I I I I I I I I I I I I I I I I I I 40 ___i _L I L ____! I ___l I _j I I I I I I I I I I I I I I I I I I I (/) 35 I I I I I I I I I I (/) I I I (12, 32)1 I I I I I I I I I I I I I I ..._. =It 30 I I I I I I I I I I I I I I I I I Q) I I I I I I I I I N ·- I I I I I I I I I (/) 25 I I I I ---, I---, I - I I (4 .5, 25) I I I I I I I I 0 I I I I I I I I I I ""C c: 20 --r I I I II r--' I -I ·- I I I I I I I I I I s I I I I I I I I I I c: 15 ---t ---t- I I -t- --t t- --t I -I 0 I I I I I I I I I I ·- I I I I I I I I I I (f) Q) 10 -+ 4 I I +- ---4 ---4 I - I C) I I I I I I I I I c: I I I I I I I I I 0 0 5 -+- I I +--- ----4 I - I I I I I I I I I I (0, 1) I I (13, 1) I I I I I 0 2 4 6 8 10 12 14 16 20 22 24 26 Time (#RTT) ssthresh = 25 timeout ssthresh = 16 (17,16) (24,23) (26,25) SS(0, 4.5) CA(4.5, 12) SS(13, 17) CA(17, 26) More specifically: (a) (5) Identify the intervals of time when TCP slow start is operating. What is the respective SSThres (slow start threshold) in TCP congestion control? Answer: These are the periods of exponential increase: (0,4.5) and (13, 16). The SSThres are 25 and 16, respectively, i.e, the values at which the increase switches from exponential to linear. (b) (2 Points) Identify the interval(s) of time when TCP congestion avoidance is operating. What is the respective SSThres? Answer: It is the period of linear increase: (4,5, 12). The SSThresh is 25. (c) (3 Points) How many segments are lost from time 0 to 16? Answer: at least one 1 packet at time 12 triggered a timeout. There is no other time of loss on this diagram. (d) (10 Points) Assume that no packet is lost during time 16-26. Complete the TCP congestion window curve from time 16 to 26. Answer: The critical turning point is at (17,16) where the congestion window reaches the SSHThresh value (32 2 = 16 and switches from exponential to linear increase. 22. (20 Points) Random Access Protocols. Consider hosts A,B,C that transmit on a shared medium, using a random access protocol. Each host has exactly one frame to send, with transmission time = 14 time units. Host A wants to transmit at time t = 0. Hosts B,C both want to transmit at time t = 7, as shown in the figure below. Time is slotted and all hosts are synchronized to the clock. 4 Frame transmission: 14 time units 0 14 28 A B, C 7 Time Frames arriving from higher layers If needed to make randomized decisions, each host has access to the following sequence of random numbers, drawn uniformly at random between 0 and 1: • Station A draws numbers: 0.45, 0.11, 0.71.... • Station B draws numbers: 0.10, 0.65, 0.91.... • Station C draws numbers: 0.83, 0.41, 0.25 .... The numbers must be used in the sequence they are provided and each random number must be used only once. You can decide to use these random numbers to make randomize decisions as you like, as long as you state your rule. A commonly used rule is the following: given a random number r 2 [0; 1], if you want to choose among N points, the point chosen is the kth point (1 ≤ k ≤ N) where k = drNe. (Example 1: if you want to flip a fair coin you can use the random numbers as follows: r ≤ 0:5 means Heads, r > 0:5 means tails. Example 2: if you try to pick one slot randomly out of two slots total: same, as before. Example 3: if you try to pick one slot randomly out of four slots total, you can do the following: 0 ≤ r < 0:25, 0:25 ≤ r < 0:5, 0:5 ≤ r < 0:75, 0:75 ≤ r < 1 can correspond to the first, second, third or fourth timeslot.) You can use the same random numbers for both questions (a) and (b). (a) (9 Points) Consider that nodes run a Slotted Aloha protocol, where the time slot equals the fixed duration of each frame =14 time units; i.e., slots start at time 0; 14; 28; ::: etc. Show all transmissions that take place according to the Slotted Aloha Protocol, until all three frames are successful. Answer: B and C start transmitting in the beginning of the next time slot (at time 14). This will result in a collision in the second slot (tie 14 to 28). C flips a coin for transmitting in the next slide and succeeds (random number 0:83 > 0:5). B on the othe [Show More]

Last updated: 3 years ago

Preview 1 out of 15 pages