EE555-Solutions-Spring-2012 1 University of Southern California EE555: Broadband Network Architecture Midterm, Solutions December 11, 2006 1. T, F, T, F, T, F, F, F, F, F, T, F, T, F, F, T, F, F, F, T 2. Case 1: FCFS 1 = 1/4, 2 = 1/15, 1 = 1/2, 1 = 1, 1 = 1/2, 2 = 1/15 Total = 1 + 2 = 17/30 Total = 1 + 2 = 19/60 E(S) = Average Service Time = / = 34/19 min/packet E(S2) = Mean Square Time = 4(15/19) + 2(4/19) = 68/19 E(R) = Average Residual Time = E(S2)/2 = 17/30 min E(T) = Average Time in system = E(W) + E(S) = E(R)/(1- ) + E(S) 3.1 min Case 2: Priority with non-preemption E(W1) = Average waiting time, Type 1 = E(R)/(1-1) = 1.132 min E(T1) = Average total time, Type 1 = E(W1) +E(S1) = 1.132 + 2 = 3.132 min E(W2) = Average waiting time, Type 2 = E(R)/(1-1)(1-1-2)= 2.612 min E(T2) = Average total time, Type 2 = E(W2) +E(S2) = 2.612 + 1 = 3.612 min E(N1) = Average # of packets, Type 1 = 1E(T1) = 0.783 packets E(N2) = Average # of packets, Type 2 = 2E(T2) = 0.241 packets E(N) = Average # of packets in system= E(N1) + E(N2) = 1.024 packets E(T) = Average Time in system = E(N)/ 3.23 minEE555-Solutions-Spring-2012 2 3. Solutions: Case 1: Fair Queuing Queue Tag Time Analysis Real Start Real Finish A F(A,1) = Max (0, 0) + 2 = 2 0 2 A F(A,2) = Max (F(A,1), 2.5) + 1 =3.5 5 6 B F(B,1) = Max (0, 1) + 3 = 4 2 5 B F(B,2) = Max (F(B,1), 1.5) + 1 = 5 6 7 C F(C,1) = Max (0, 2) + 5 = 7 7 12 Based on the GPS, the order of transmission is: A1,A2, B1, B2 and C1. The round time vs. time curve is shown. Now however consider the real FQ. The first Packet to be served is A1. It will start service at t = 0 and ends at t = 2. At t =2, B1 has been in the buffer and B2 just arrived but since the finishing number of B1 is less than B2, B1 get served first. He starts at t = 2 and finishes at t = 5. At t = 5, all other packets are already in buffer, hence next to be served is A2, followed by B2 and finally C1. The above table indicates the "real" start and finishing times. Note again, the FQ is NOT an exact simulation of GPS since it does NOT allow for the pre-emption of a packet already in service when a packet with a lower finishing time arrives. So the actual sequence based on FQ is A1, B1, A2, B2, and C1. 7 Slope = 1 Slope = 1/2 Slope = 1/3 Slope = 1/2 12 4 1 t R(t) 7 10 1EE555-Solutions-Spring-2012 3 Case 2: Weighted Fair Queuing (some times approximate) Queue Tag Time Analysis Real Start Real Finish A F(A,1) = Max (0, 0) + 2/2 = 1 0 2 A F(A,2) = Max (F(A,1), 1.1) + 1/2 1.6 5 6 B F(B,1) = Max (0, 0.5) + 3/3 = 1.5 2 5 B F(B,2) = Max (F(B,1), 0.7) + 1/3 = 1.83 6 7 C F(C,1) = Max (0, 1) + 5/5 2 7 12 Based on the weighted GPS, the order of transmission is: A1, B1, A2 , B2 and C1. 4. One way to solve this is to imagine that we start with an empty bucket but allow the bucket volume to become negative (while still providing packets). We then get the following table of bucket "indebtedness" for example at t = 0, we withdrew 8 tokens from the bucket and deposited 2 (the token rate) for a net deficit of -6. From the table below it is clear that we need an initial bucket depth of 9 tokens so as not to run out at t = 4. Because all the volumes below are negative, the bucket with depth 9 never overflows. Time (sec) 0 1 2 3 4 5 Bucket Volume -6 -8 -7 -5 -9 -8EE555-Solutions-Spring-2012 4 5. In case 1, we lose 900 ms: we wait 300ms initially to detect the third duplicate ACK, and then one full 600 ms RTT as the sender waits for the ACK of the Retransmitted segment. In case 2, we lose 900 − 200 = 700ms. As shown in the diagram, the elapsed time before we resume is again 900ms but we have had two extra chances to transmit during that interval Retransmission Case 1 Retransmission Window closed Window Open Lost 700 msec Window closed Window Open Case 2 Window closed Window Open Lost 900 msecEE555-Solutions-Spring-2012 5 6. P(Blocking) = [1-(1-(0.1)(128)/k)2]k = 0.002 from which k = 25 where k = # of time slots per space switch (remember space switch does not switch time slots). The switch is as shown below. # of cross points = N2 = 256 # of bits for Time Switches Data Memory = 2Nn(8) = 32,768 bits # of bits for Time Switches Control Memory = (2Nk)log(n)= 5600 bits # of bits for Space Switch Control Memory = (NK)log(N) = 1600 bits T1 nxk T2 nxk T16 nxk 16x16 Time- Shared Space Switch T1 kxn T2 kxn T2 kxn 16 TDM frames each 128 time slots 16 TDM frames each 128 time