Open access peer-reviewed chapter

An Analysis of Data Link Control Protocols

By Pinaki Mitra

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

DOI: 10.5772/60962

Downloaded: 964

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

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 tf and the propagation delay is tp, we can pack A data frames in the time span tf + 2tp where

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

If our window size WA then 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-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 = UNr. 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:

  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.

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:

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 K frames 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 = A for WA and K = W for 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].

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

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

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.

© 2015 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Pinaki Mitra (October 21st 2015). An Analysis of Data Link Control Protocols, Cutting Edge Research in Technologies, Constantin Volosencu, IntechOpen, DOI: 10.5772/60962. Available from:

chapter statistics

964total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Weaving Complex Patterns — From Weaving Looms to Weaving Machines

By Stana Kovačević and Ivana Schwarz

Related Book

First chapter

Microassembly Using Water Drop

By Taksehi Mizuno

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us