Page 1 Example Questions for Final Exam CS 162 I. Stoica Spring 2011 Store and Forward 1 Hosts A and B are connected to each other via router R. R is a store-and-forward router. The bandwidth from A to R is 10Mbps, and the bandwidth from R to B is 5Mbps. The one-way latency of each link is 22ms. Assume host A sends a 30KB file to host B. a) Assume the file is divided into two packets, p1 and p2, where p1 has a length of 10KB, and assume the packets are sent back-to-back. What is the difference between the arrival times of the first and the second packet at host B? b) What is the effective throughput between A and B in part (a)? (The transmission time is the time interval from the time the first bit is sent at A until the final bit is received at B). c) Does the throughput increase or decrease if we divide the file into smaller packets? Why? d) Now, assume each packet is acknowledged. The file is divided into 6 packets of the same size. How long would it take to send the entire file assuming that the sender cannot send a new packet before it receives an acknowledgment for the previous packet? (The transfer time is the time interval measure at source A from the time the first segment is sent until the acknowledgement of the last segment is received). Ignore the transmission time of the acknowledgements Solution: a) The difference is the transmission time of packet B over the second link time: size/bw= 8*20/5000 = 160/5000 = 32ms b) Total transfer-time: calculate how long the second packet takes and add the wait for the first packet over link A-R. A-R wait is: 8*10/10000 = 8ms Now time to send B is 8*20/10000 + 8*20/5000 + 44ms = 16ms + 32ms + 44ms=92ms Total time: 100ms THROUGHPUT: 30k/100ms = 0.3MBps or 2.4 Mbits/s c) The throughput will increase – because a smaller packet is received at R and can be forwarded immediately (don’t have to wait till the entire original packet is transmitted over the first link to start transmitting over the slower second link) d) Size of 1 packet = 5KB transmit time /packet= 44 + 44ms + 5*8/10000+5*8/5000= 44ms +44ms + 4ms + 8ms = 100ms so for 6 = 600msPage 2 Store and Forwarding 2 Consider two packets that are sent back to back (i.e., one right after another) along the path A-B-C-D, where A, B, C, and D are store-and-forward routers. Assume the capacity of link (A, B) is 10Mbps, the capacity of (B, C) is 1Mbps, and the capacity of (C, D) is 100Mbps. The propagation delay along each link is 10 ms. Assume the size of the first packet is 1000 bits, and that the size of the second packet is 500 bits. What is the inter-arrival time between the two packets at node D? The inter-arrival time is equal to the arrival time of the second packet minus the arrival time of the first packet at node D. Notes: Assume there is no cross-traffic; the two packets are the only ones in the network. The arrival time of a packet is the time when the last bit of the packet was received. With a store-and-forward router a packet is forwarded only after the last bit of the packet was received. Answer See the time diagram below bellow (l1 = 1000b, l2 = 500b, C1 = 10Mbps, C2 = 1Mbps, C3 = 100Mbps) The inter-arrival time between the two packets at D is l2/C2 – l1/C3 + l2/C3 = 500b/106Mbps - 1000b/108Mbps + 500b/108Mbps = 0.495 ms A B C D l1/C1 l2/C1 l1/C2 l2/C2 l1/C3 l2/C3 l2/C2 – l1/ C3 + l2/C3Page 3 Store and Forwarding 3 Consider the network in the figure below where two source nodes A and B are connected to a destination node D through a router C. Assume that node A starts to send a 600 bit packet at time 0 and node B start to send a 1000 bit packet at time T (see figure below). Plot the inter-arrival time, denoted I, between the two packets at node D versus the starting time of B’s packet, T for 0 <= T < 5. Notes: Ignore the processing time at C. The arrival time of a packet is the time when the last bit of the packet has arrived at node D. The inter-arrival time is I = (arrival time of packet sent by B at D) – (arrival time of the packet sent by A at D). Hint: Based on the value of T, there are three cases you might want to consider. The diagram in Figure (a) shows the first case and depicts the messages sent by A and B arriving at C. You can use these diagrams to solve the problem, i.e., finish diagram (a) and fill in the other two diagrams (b) and (c). Solution: Use the following coordinates to plot the inter-arrival time between the two packets at D (I) versus the starting time of B’s packet (T), for 0 <= T <= 5. 0 6 2 8 T T+5 T+1 T+6 T+6+d T+8+d T+9.2+d T+8 T+9.2 0 6 2 8 T T+5 T+1 8+d 9.2+d 11.2+d T+6 0 6 2 8 T T+5 T+1 8+d 9.2+d T+8+d T+6 I = T+8+d – (T+9.2+d) = -1.2ms I = 11.2+d – (9.2+d) = 2ms I = T+8+d – (9.2+d) = T-1.2 ms (a) T+6 <= 8 (b) 8 < T+6 <= 9.2 (c) 9.2 < T+6 9.2 A D C B 100Kbps, 2ms 200Kbps, 1ms 500Kbps 600 bits time = 0 1000 bits time = TPage 4 T (ms) I (ms) 0 1 2 3 4 5 -1 -2 1 2 4 5 -1.2 T -1.2 3.2Page 5 Store and Forward 4 (Measuring link capacities) Consider the network below where three hosts A, B, and C, respectively, are connected to router R. The capacity of the links are x Kbps, y Kbps, and z Kbps, respectively. Assume the users of hosts A, B, and C, respectively, want to measure the capacities of the three links. To achieve this, they send the following messages: • From A to B: Send two back-to-back 1Kbit packets; the interval between receiving the first and the second packet at B is 100ms; the time it takes B to receive each packet (i.e., the interval between receiving the first bit of the packet and the last bit of the packet) is 100ms. • From B to C: Send two back-to-back 1Kbit packets; the interval between receiving the first and the second packet at C is 200ms; the time it takes B to receive each packet is 200ms. • From C to A: Send two back-to-back 1Kbit packets; the interval between receiving the first and the
View Full Document
Unlocking...