Selective Repeat Lab

Matt Gorelik and Joe Jones

ECE department, Boston University, Boston MA
12/2003

Contents:

• Lab task
• Experiment Demo
• Software developed
• Short answers to Prelab questions

Goal: In this lab we will qualitatively look into the performance of one of the most sophisticated and widely implemented ARQ (automatic repeat request) protocol. You will see simulations of Selective Repeat in action and compare it to the performance of Go Back N.

Assumptions:

• a is a ratio of Propagation and Transmission times for the data packet.
  a=T_prop/T _trans
• Transmission time for acknowledgment is negligible.
• Acknowledgments never get lost. This is a valid assumption because in reality acknowledgements tend to be very small in comparison to actual packets, and the probability of their loss is substantially smaller.
• MaxSeqNum is chosen properly to avoid wrap around receiver confusion.
• Processing time at receiver is negligible (acknowledgment is sent immediately after receiving a packet)
• Sender knows T_prop exactly and adjusts time-out period to the optimal value assuming that no delay was introduced by the receiver.
• Sender resends packet(s) immediately after time-out.
• Propagation time for the link is equal in both directions.

Application problems:

Joe wants to send a file to Matt. Joe’s computer is directly connected to Matt’s computer by a link of capacity 1 Mb/s. The propagation delay of the link  is 2 ms. The file consists of 10 packets, each of size 980 bits with a header of 20 bits. Joe decides to send these packets using a reliable sliding-window protocol. Assume that the transmission delay of an ACK message is negligible.

1. What should be the length of the sequence number field (in bits) in each packet, for each of the following cases:

a. Stop and Wait.

b. Go-Back N with a sender window size equal to 5.

c. Selective Repeat with a sender window size equal to 5.

2. Assume no packet is lost. Draw a space-time diagram and compute how much time it will take until the GTF receives all the 10 packets, for each of the following cases:

a. Stop and Wait.

b. Go-Back N with a sender window size equal to 5.

c. Selective Repeat with a sender window size equal to 5.

3. Assume that the sixth packet is lost. Assume a time-out value of 10 ms. Draw a space-time diagram and compute how much time it will take until the GTF receives all the 10 packets, for each of the following cases:

a. Stop and Wait.

b. Go-Back N with a sender window size equal to 5.

c. Selective Repeat with a sender window size equal to 5.

Prelab Problems:

4. What is an optimal time-out given assumptions above ? 

5. Selective Repeat protocol. Assuming the perfect link (no packet or acknowledgment is lost) derive an expression for link utilization as a function U(a) . Link utilization is defined as a fraction of time used to transmit a data packet which is successfully accepted. If the packet is retransmitted it can be counted only once. Therefore for a long enough period of time T and total number of accepted packets N _a , U=N_a T_trans/T . Evaluate the expression that you obtained for 3 values of  a: 0.3, 1, 3

6. How do you expect Selective Repeat to be different from Go Back N in respect with the simulation?

Download the  lab_x.zip  into your directory dir_name and type unzip lab_x.zip
Add a directory  dir_name  into the matlab search path using
>> path(dir_name,path)

Lunch sw.m
>> sw

GUI interface is straightforward to use. Use upper set of controls for single experiment visualizations and lower set of controls for performance measurements.  You can obtain a simulated time diagram for a particular set of parameters or a performance estimate plot as function of a . You can perform several experiments (for different values of loss probability) in and compare resulting performances.

Question 1

Run Stop-and-Wait simulation for a=2 and P _loss =0. Print a segment of time diagram and show the time-out period on the diagram.

Question 2

Stop-and-Wait simulation. Plot simulated performance curve U(a) for P_loss=0, P_loss=0.05 and P_loss=0.1 . Print the resulting graph. Mark theoretical values obtained in prelab on the plot. Do they match the simulated values ? If not, explain the disagreement.
Explain what happens to link utilization when  P_loss is increasing. 

Question 3

Run Go-Back-N simulation for W=2,  a=2 and P_loss=0.2. Print obtained time diagram and show the time-out period on the diagram.

Question 4

Go-Back-N simulation. Obtain and print the simulated curve U(a) for W=5, P_loss=0, P_loss=0.05 and P_loss=0.1. Print the resulting graph. Mark theoretical values obtained in prelab on the plot. Do they match the simulated values ? Explain the disagreements if any.
When the loss of packets gives the most significant effect and why ?

Question 6

Run Selective Repeat  simulation. For P_loss =0.0 and a=2 plot and print the simulated time diagram. Mark the packets that are accepted by the receiver. Is the algorithm more efficient than Go Back N? Can anything else be done to improve performance of this algorithm?.

Experiment Demo

Question 1

Question 2,3

Question 4,5

Software developed

Short answers to Prelab questions

1. a. Stop and Wait, MaxSeqNum >= 2 = 21 : 1 bit.

   b. Go-Back N, MaxSeqNum >= 5+1 = 6 and 6 < 8 = 23 : 3 bit.

   c. Selective Repeat, MaxSeqNum >= 5+5 = 10 and 10 < 16 = 24 : 4 bit.

2. a. Stop and Wait: GTF will receive the packet after 48 ms.

   b. Go-Back N: GTF will receive the packet after 12 ms.

   c. Selective Repeat: GTF will receive the packet after 12 ms (same as Go-Back N).

3. a. Stop and Wait: GTF will receive the packet after 58 ms.

   b. Go-Back N: GTF will receive the packet after 22 ms.

   c. Selective Repeat: GTF will receive the packet after 18 ms.

4. Timeout=2T_prop +T_trans
5. U=1/(1+2a);       U=[0.625    0.3333    0.1429]
6. U=1/{(1+2a)(1+2P_loss )} Note that this is the same for Go Back N without any loss.