Number of retransmissions and duplicate error-free packets with different probabilities
In this chapter we analyze the performance of data link protocols. We consider Stop and Wait ARQ and Sliding Window protocol. In Sliding window protocol, we consider Selective Reject ARQ and Go-Back-N ARQ. There are existing results that analyze the link utilization of these protocols in the presence of error. We have experimented in a somewhat more generalized framework. We have also analyzed and experimented with the number of duplicate error-free packets that will be transmitted.
- Stop ad Wait ARQ
- Sliding Window Protocol
- Selective Reject ARQ
- Go-Back-N ARQ
- Duplicate Error-Free Packet
There are two types of Data Link Control Protocols:
Stop and Wait
1.1. Stop and wait ARQ
In stop and wait flow control the sender sends the data frame whose transmission time is tf and it reaches the receiver after time tp, the propagation delay across the communication channel. The receiver sends the acknowledgment frame back to the sender whose transmission time is negligible and the propagation delay is tp. This is illustrated in Figure 1. The sender sends the next data frame after time (tf + 2tp) if ACK is positive, otherwise it resends the earlier frame.
The link utilization of this stop and wait protocol is given below:
1.2. Sliding window protocol
Here, the sender maintains a window of data frames of size W. In this protocol the sender continues sending packets before the receipt of the ACK (acknowledgment) frame. If the frame transmission time is tf and the propagation delay is tp, we can pack A data frames in the time span tf + 2tp where
If our window size W ≥ A then link utilization U = 1 otherwise U = . The protocol is illustrated in Figure 2.
This analysis holds for error free transmission. Now if there are transmission errors then in both the protocols the packet has to be resent. For sliding window protocols there are two types of ARQ, namely:
Selective Reject ARQ
In Selective Reject ARQ, sliding windows of same size at both sending and receiving ends are maintained. The receiver sends a RR-N frame, that is, receive ready frame to the sender for the sending data frame N. If any data frame N is in error the receiver sends back SREJ -N, that is, selective reject signal to the sender. It continues to receive frames with sequence number ≥ N from the sender but it does not send any RR request for frame ≥ N.
In contrast, in Go-Back-N ARQ, sliding windows of unequal size at sending and receiving ends are maintained. In the sending end sliding window size is usually > 1 but in the receiving end sliding window size is usually = 1. Here also the receiver sends a RR-N frame, that is, receive ready frame to the sender for the sending data frame N. If any data frame N is in error, the receiver sends back Go-Back-N signal to the sender. It rejects all frames with sequence number ≥ N from the sender and it does not send any RR request for frame ≥ N.
For both these protocols, let Nr be the expected number of retransmissions. Then, the link utilization in the presence of error Uerror = . The analysis of Nr is usually carried out by assuming the ACK frame is error free. In this chapter, we try to analyze three situations:
The delivered packet is delayed
ACK frame is in error
ACK frame is delayed
In all the three cases the receiver will receive duplicate error-free packets. We try to analyze the estimate of duplicate packets received by the receiver.
2. Existing analysis of link utilization of data link control protocols
Consider P is the probability that the single frame is in error. Then link utilization for Stop-and-Wait ARQ is computed as follows:
For Selective Reject ARQ the link utilization is as follows:
For Go-Back-N ARQ each error generates a requirement to retransmit K frames rather than a single frame.
Here, we assumed K = A for W ≥ A and K = W for W < A.
3. Modified analysis of link utilization of data link control protocols
We will assume that the probability of a frame not in error is p1. Also we will assume that the probability the frame is delivered within a time interval T is p2. The sender will resend the packet if ACK does not arrive after time interval 2T. Let p3 be the probability that the ACK frame is error free. Let p4 be the probability that the ACK arrives within time 2T. The probability that the packet is received correctly in one transmission is p1p2p3p4. So the expected number of retransmissions Nr = 1/ p1p2p3p4. So in the existing analysis we only need to substitute P = 1- p1p2p3p4 to get the link utilization.
To analyze the case of the receipt of duplicate error free packets we consider the following four events:
The delivered packet is free from error. The corresponding probability is p1. Let us call this as event A1.
The packet doesn’t reach within time T and the receiver asks to resend the packet. The corresponding probability is (1-p2). Let us call this as event A2.
The ACK frame is in error and requires retransmission. The corresponding probability is (1-p3). Let us call this as event A3.
The ACK frame doesn’t arrive within time 2T and the sender resends the packet. The corresponding probability is (1-p4). Let us call this as event A4.
The probability that there is duplicate frame transmitted will be:
So the expected number of duplicate packets will be Nr q.
4. Experimental results and discussions
We have experimented with the number of retransmission and the number of duplicate error-free packets transmitted with the following C code:
We have run several times the above mentioned program and obtained the following results:
In the Table-1, P(A1) = p, P(A2) = 1 - p, P(A3) = 1 - p, P(A3) = 1 - p. The number of retransmissions Nr = n_r and dup stands for the number of duplicate error-free packets. We have shown the table sorted on n_r. We also obtained the plot illustrated in Figure 3, which shows the interrelationship between n_r and dup.
We can clearly see that as n_r increases monotonically dup doesn’t show any such monotonic increasing property. This is apparent from Table 1 where we observe that for n_r = 116 dup = 109 and for n_r = 192 dup = 6.
5. Conclusion and future work
In this chapter we have analyzed and experimented with the number of retransmissions and the number of duplicate error-free packets transmitted in a generalized framework of data transmission model. As a future work we can consider some distribution on the probability of delayed transmission as a function of time.