Open access peer-reviewed chapter

An Analysis of Data Link Control Protocols

Written By

Pinaki Mitra

Submitted: October 30th, 2014 Reviewed: June 3rd, 2015 Published: October 21st, 2015

DOI: 10.5772/60962

Chapter metrics overview

1,660 Chapter Downloads

View Full Metrics

Abstract

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.

Keywords

  • Stop ad Wait ARQ
  • Sliding Window Protocol
  • Selective Reject ARQ
  • Go-Back-N ARQ
  • Duplicate Error-Free Packet

1. Introduction

There are two types of Data Link Control Protocols:

  1. Stop and Wait

  2. Sliding Window

1.1. Stop and wait ARQ

In stop and wait flow control the sender sends the data frame whose transmission time is tfand 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.

Figure 1.

Illustration of Stop and Wait ARQ

The link utilization of this stop and wait protocol is given below:

U=tftf+2tp

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 tfand the propagation delay is tp, we can pack Adata frames in the time span tf+ 2tpwhere

A=tf+2tptf= 1 + 2tptf= 1 + 2awherea=tptf

If our window size WAthen link utilization U= 1 otherwise U= WA. The protocol is illustrated in Figure 2.

Figure 2.

Illustration of Sliding Window Protocol

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:

  1. Selective Reject ARQ

  2. Go-Back-N ARQ

In Selective Reject ARQ, sliding windows of same size at both sending and receiving ends are maintained. The receiver sends a RR-Nframe, that is, receive ready frame to the sender for the sending data frame N. If any data frame Nis in error the receiver sends back SREJ -N, that is, selective reject signal to the sender. It continues to receive frames with sequence number ≥ Nfrom the sender but it does not send any RRrequest 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-Nframe, that is, receive ready frame to the sender for the sending data frame N. If any data frame Nis in error, the receiver sends back Go-Back-Nsignal to the sender. It rejects all frames with sequence number ≥ Nfrom the sender and it does not send any RRrequest for frame ≥ N.

For both these protocols, let Nrbe the expected number of retransmissions. Then, the link utilization in the presence of error Uerror= UNr. The analysis of Nris usually carried out by assuming the ACK frame is error free. In this chapter, we try to analyze three situations:

  1. The delivered packet is delayed

  2. ACK frame is in error

  3. 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.

Advertisement

2. Existing analysis of link utilization of data link control protocols

Consider Pis the probability that the single frame is in error. Then link utilization for Stop-and-WaitARQis computed as follows:

Nr=i=1(iPi1(1P))= 1/(1P)Uerror=U/Nr= (1P)/A

Where

 A=tf+2tptf=1+2tptf= 1 + 2awherea=tptf

For Selective Reject ARQ the link utilization is as follows:

Uerror=U/Nr={1PWAW(1P)AW<A

For Go-Back-N ARQ each error generates a requirement to retransmit Kframes rather than a single frame.

Nr=i=1[1+(i1)KPi1(1P)]= 1 K+K/(1P) = (1P+KP)/(1P)
Uerror=U/Nr={1P1+2aPWAW(1P)A(1P+WP)W<A

Here, we assumed K= Afor WAand K= Wfor W< A.

A detailed discussion of the protocol and the above analysis can be found in authored books [1], [2], [3] and [4]. Reader can also refer to the published journal article [5].

Advertisement

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:

  1. The delivered packet is free from error. The corresponding probability is p1. Let us call this as event A1.

  2. 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.

  3. The ACK frame is in error and requires retransmission. The corresponding probability is (1-p3). Let us call this as event A3.

  4. 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:

P[A1(A2A3A4)] = P(A1) [P(A2) + P(A3) + P(A4) P(A2A3)  P(A3A4)  P(A4A2)  P(A2A3A4) ]=p1[(1p2) + (1p3) + (1p4) (1p2)(1p3)  (1p3)(1p4)  (1p4)(1p2) +(1p2)(1p3)(1p4)] =q

So the expected number of duplicate packets will be Nrq.

Advertisement

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:

#include <stdio.h> #include <math.h> #include <stdlib.h> #include <time.h> void main() { float p[4]; float S0, S1, S2; int i,j; float q, term, term_1, term_2; int n_r, dup; time_t t; srand((unsigned) time(&t)); randomize(); p[0]=(float)random(100)/100.; p[1]=(float)random(100)/100.; p[2]=(float)random(100)/100.; p[3]=(float)random(100)/100.; printf("p[0]=%f p[1]=%f p[2]=%f p[3]= %f\n\n", p[0], p[1], p[2], p[3]); S0 = 3-p[1]-p[2]-p[3]; S1 = 0; for (i= 1; i <4; i++) for (j=i+1; j < 4; j++) S1 += (1-p[i])*(1-p[j]); S2 = (1-p[1])*(1-p[2])*(1-p[3]); q = p[0]*(S0 - S1 + S2); term = p[0]*p[1]*p[2]*p[3]; term_1 = 1.0/term; n_r = (int)term_1; term_2 = q*n_r; dup = (int)term_2; printf (" n_r = %d dup = %d \n", n_r, dup); }

We have run several times the above mentioned program and obtained the following results:

p[0]p[1]p[2]p[3]n_rdup
0.820.930.640.2974
0.850.660.220.332419
0.380.710.240.56279
0.60.440.140.952815
0.130.740.240.54809
0.950.470.480.4116109
0.040.920.640.221926
0.210.440.480.0732266
0.120.120.370.161173139
0.520.240.420.011907990

Table 1.

Number of retransmissions and duplicate error-free packets with different probabilities

In the Table-1, P(A1) = p[0], P(A2) = 1 - p[1], P(A3) = 1 - p[2], P(A3) = 1 - p[3]. 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.

Figure 3.

Illustration of the interrelationship between the number of retransmissions and duplicate error-free packets

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.

Advertisement

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.

References

  1. 1. William Stallings,Data and Computer Communications, 8th Edition, Pearson.
  2. 2. Prakash C. Gupta,Data Communications and Network,Prentice Hall India.
  3. 3. Ajit Pal,Data Communications and Computer Networks,Prentice Hall India.
  4. 4. Dimitri Bertsekas and Robert Gallager,Data Networks, 2nd Edition, Prentice Hall India.
  5. 5. Lin, S., Costello, D., and Miller, M. “Automatic-Repeat-Request Error-Control Schemes.”IEEE Communication Magazine,December 1984.

Written By

Pinaki Mitra

Submitted: October 30th, 2014 Reviewed: June 3rd, 2015 Published: October 21st, 2015