1. Introduction

Reliable data transmission requires applying some error control mechanisms. ARQ (Automatic Repeat reQuest) protocols are error control protocols implemented at layer 2 (Data Link Layer) and Layer 4 (Transport layer) to provide reliable transmission of digital data over unreliable communication links, with correct order . To do so, ARQ protocols depend on ACKnowledgements (ACK) (or Negative AcKnowledgements (NAK)) and timeouts. Most likely, the receiver implements some error detection technique (ex. Cyclic Redundancy Check (CRC)) to check if the received packet is error free or not. Then, the receiver sends either an ACK or NAK to the sender to tell whether the packet is correctly received or not. On the other hand, the sender sets some timeout interval after sending each packet. If no ACK is received before the timeout, the sender usually re-transmits the packet. This process is repeated until either an ACK is received or number of re-transmissions attempts is exceeded. There are three basic types of ARQ protocols: Stop and Wait (SW) ARQ, Go Back N (GBN) ARQ, and Selective Repeat (SR) ARQ. All will be explained in the next section.

In [1], “The SW ARQ protocol adopted the idea of SR ARQ protocol considering different packet size depending on the link state. The proposed SW ARQ scheme proved better performance compared to traditional SW ARQ protocol considering either the simulation results or the obtained analytical results”. However, in [2], “SR ARQ protocol is applied within Adaptive Modulation System (AMS). It studied the throughput of SW ARQ protocol using different fading links. Moreover, It considered the link estimated transmission errors in the analysis of the throughput and conducted a type of comparison with the link throughput assuming perfect transmission link”.In [3], “a Reliable SR ARQ (RB-SR ARQ) protocol is suggested with parity check codes of low density. This spoils the reliability of the estimated bits at the decoder side to re-transmit these unreliable bits”. But in [4], “the link Round Trip Time (RTT), which specifies the receiving instant of the receiver feedback, is considered to be a fixed amount. It has been shown that, the changing of RTT has limited effect on delay analysis”. While [5] “modelled and analyzed the delay resulted from the packet resequencing of time division duplexing that applies SR ARQ error control scheme. Keeping in mind that link transmission errors may initiate and motivate the packet resequencing procedure at the receiver side, Markov Chains assumptions have been applied to give prediction for the effect of resequencing delay on the Quality of Service (QoS)”. Also,

“discussion of SR ARQ strategy for underwater acoustic networks

has been presented in [6]. It has been shown that, performance of a given size multiuser networks can be optimized through adjusting the point-to-point communication time”.

As ARQ protocols provide reliable data transmission over unreliable transmission links, they have wide range of applications. ARQ protocols are basically applied on shortwave radio to ensure reliable delivery of signals. Add to this, there are different applications for the same function of ARQ protocols such as Transmission Control Protocol (TCP), High-Level Data Link Control (HDLC) protocol, and Xmodem. The service time analysis of GBN ARQ protocol was presented in [8]. However, In [9], we started service time analysis of SR ARQ protocol for transmission of short messages over noisy channels and obtained the service time distribution for this special case. Moreover, the first and second moments of service time distribution were also calculated. The future research plan includes doing validation and simulations for all results obtained in [8, 9] accompanied by a wide comparison between all discussed ARQ protocols.

Obviously, the service time analysis of SR ARQ protocol has not been considered properly before. Service time can be considered as a type of QoS measurement and evaluation metric. No doubt, analyzing and studying the service time of ARQ protocols is essential because it sheds the light on factors affecting the service time. If such factors are handled properly, service time may be reduced. The main contribution of this article is studying and analyzing the service time of SR ARQ protocol based on a new mathematical model. This study depends on applying stochastic processes and Markov Chains in view of probability and statistics theories to obtain an analytical formula of Probability Generating Function (PGF) of service time distribution of SR ARQ protocol. Also, closed form expressions of first and second moments of obtained PGF are also derived. The rest of this article proceeds as follows: Next section demonstrates the basic ARQ protocol types showing the basic strategy of each and differences between them. Section 3 explains the used mathematical model assumptions. Then, the PGF of service time distribution is discussed and derived in section 4 for two different cases (short and long messages). Moreover, the first and second moments of service time distribution are calculated in each case. Conclusion is the last section.

2. Basic ARQ Protocols

In data transmission, reliable data transfer is an important issue. TCP protocol is responsible of this service. The major ARQ flow control schemes are: SW ARQ, GBN ARQ, and SR ARQ. Each

ARQ protocol has specific strategy for controlling transmission errors. Some ARQ protocols use the concept of sliding window, where the transmitter can send many packets before receiving any ACKs. Both GBN ARQ and SR ARQ protocols are sliding window protocols. The sliding window (also known as windowing) is an imaginary box to hold packets. In such protocols, both the sender and the receiver have buffers called the sending window and the receiving window respectively (Figure 1).

Figure 1: Sender Sliding Window

Actually, The sending window size is somehow dependent on the sequence number field of the packet header. If the size of the sequence number field of the packet header is n bits, then the sequence numbers of packets will range from 0 to 2ⁿ − 1. Consequently, the sending window size can not exceed 2ⁿ − 1 packets too. Thus, in order to accommodate a sending window size of 7 packets, the length of sequence number field should be 3 bits.

2.1. Stop and Wait (SW) ARQ Protocol

SW ARQ protocol is an error and flow control strategy used for unidirectional data traffics over unreliable communication links. It applies the ACKs and timeouts modules. The sender saves a copy of each sent packet. Then, it waits for a predefined time period (timeout) to receive an ACK from the receiver. If an ACK is received, the sender sends the next packet. On the other hand, The receiver checks each received packet and apply an error detection scheme (ex. CRC). After that, either ACK or NAK is sent to the sender. The packet is re-transmitted if the timer expired or a NAK is received. However, if the ACK is lost, and the packet is re-transmitted again, the receiver discards the duplicated frame (Figure 2).

2.2. Go Back N (GBN) ARQ Protocol

According to GBN ARQ protocol, the sender is able to send a block of packets (that depends on the size of the sending window) before receiving the ACK of any sent packets. After sending all packets of the sending window (2ⁿ − 1 packet, where n is the size of the sequence number field of the packet header), the sender stops and checks the received ACKs (if any). Receiving ACKs indicates that the window will slide down and more packets can be sent. However

Figure 2: Stop and Wait ARQ Protocol

Figure 3: Go Back N ARQ Protocol

Figure 4: Selective Repeat ARQ Protocolh

2.3. Selective Repeat (SR) ARQ Protocol

Implementation of SR ARQ protocol is much similar to GBN ARQ protocol. The sender sends a block of packets (that depends on the size of the sending window) without waiting for receiving the ACK of any sent packets. After that, the sender stops and checks the received ACKs (if any). By receiving ACKs, sending window slides down and more packets can be sent. However, in SR ARQ protocol, the receiver is programmed to hold and buffer the out of order packets (if correct). Actually, the receiver sends ACKs for all correctly received packets whether they are ordered or not. Typically, The receiver is able to put the received packets in correct order before sending to the upper layers. If a packet is lost (or damaged), the receiver sends a NAK for this packet. In such case, the sender re-transmits only the packet indicated by the NAK. Although both GBN ARQ and SR ARQ protocols are sliding window protocols, it can be noted that, SR ARQ protocol is more complex than GBN ARQ protocol as it requires application of extra logic, sorting and storage modules at both sender and receiver (Figure 4).

3. Model Assumptions

Since this work is an extension to our work done in [9], similar mathematical model assumptions are adopted here:

• The model includes a transmitter, a receiver, and a slotted communication link.
• Data is divided to packets of fixed size.
• At messages level, SW ARQ protocol is applied while SR ARQ protocol is applied at packets level.
• Service time interval is specified by the time between starting and completing transmission of each message.
• Time is considered to be of equal time slots.
• Service discipline is assumed to be FCFS.
• The RV A represents the number of messages arriving in each slot, with PGF denoted by A(z)

n=0

• The buffer of the transmitter is considered to be of infinite capacity.
• Messages are divided to packets where each packet fits one slot.
• The RV B represents the number of packets in each message

(message size), with PGF denoted by B(z)

n=1

• Transmission errors occur randomly and follow a Bernoulli process. That is, if p is the probability of damage in the transmitted packet, 1 − p is the probability of successful packet transmission, and ε represents the link bit error rate, then p can be written as

where N specifies the size of the transmitted packet in bits.

• The receiver uses a return communication link to send feedback regarding the received packet (ACK or NAK, depending on the status of the received packet).
• The RV R represents the number of packets transmitted during the RTT (duration, measured in milliseconds, from sending a packet till receiving a response from a receiver).
• No errors are assumed while sending on the return communication link.

4. PGF of Service Time In SR ARQ Protocol

In this section, the PGF S(z) of the service time distribution of a message in SR ARQ protocol is discussed and derived. We consider a message consisting of i packets and deal with two different cases.

4.1. Case 1 (Short messages): i ≤ R +1

We have analyzed and presented this case in detail in [9] and these are the main results obtained from that analysis

l=0 k=1 m=0 n=0 × (pl)m+n+1pmzk(zl)R+1.

But

                                    ∞ i           k−1 i−k

XXXX

1 − zR+1pm+n+1

Moreover, the first moment (mean) and the second moment of the service time were obtained, in the form

E[S _i] = (1 − p)

4.2. Case 2 (Long messages): i > R +1

Consider a message consisting of i packets such that i > R + 1. Let us define the continuous transfer phase to be the period between the beginning of transmission of first packet to the end of the first trial of the (R + 1)^th packet. After the end of the continuous transfer phase, the i−(R+1) packet are transmitted and also NAKed packets are retransmitted. Let us define the point of the beginning of slot R + 1 before ending the continuous transfer phase to be a critical point. Note that the i − (R + 1)^st ACKs are received before the end of the continuous transfer phase (at the last but one). Therefore, the i − (R + 1)^st transmission takes place at the last slot before the critical point. Let S1_i slots include transmission of i − (R + 1) packets. {explanation : The packets of the message are transmitted continuously as in the previous case (continuous transfer phase) until the slot number R + 1. This slot starts the reply for the previously transmitted message (ACK or NAK). So, this slot represents the beginning of the transmission of both new and NAKed packets. That is why we call it a critical point. After all the new packets have been transmitted, the retransmission tail, which includes the transmission of the NAKed packets only, starts. So S _i here is

where the message consists of i packets, and

S1_i : RV that represents the service time of the packets transmit-

ted before the critical point.

S2_i : RV that represents the service time of the packets transmitted after the critical point. S1_i can be defined as

where the message consists of i packets, and S1_i1 :Service time of the 1^st packet of the message.

S1_i2 :Service time of the 2^nd packet of the message.

S1_ii−(R+1) :Service time of the i − (R + 1)^th packet of the message. Let S1_i(z) be the PGF of S1_i, then

S1_i(z) = E[z^S1i ]

where S1_ik (z) denotes the PGF of the RV representing the service time of the i − (R + 1)^st packets of the message. Suppose that any of the i − (R + 1)^st is unsuccessfully transmitted for l times. So

Now, we proceed to find the distribution of S2_i, which represents the service time of the packets transmitted after the critical point. Actually, the rest of the message can be considered as a new mes-

sage consisting of R + 1 packets. Then, its transmission will be exactly as in case 1. Thus, the distribution of S2_i will be the same as that of S _R+1 considered in case 1, with PGF S _R+1(z). However, since both the RVs S1_i and S2_i are mutually independent, then, the PGF of S _i is given by

Now we are ready to get PGF S(z) of the service time of SR ARQ protocol from what we obtained in case 1 and case 2.

From which we can find the first moment (E[S]) and the second moment (E[S²]), as follows

Finding _dz^d ₂ S(z), substituting for z = 1, and after some manipulation, we get

5. Conclusion

ARQ protocols are applied at DLL and Transport Layer of OSI network model to control transmission errors at these layers. SW ARQ, GBN ARQ, and SR ARQ are the main ARQ protocol types. They use ACKs, timeouts, and the concept of sliding window to satisfy reliable data transmission over noisy channels. This paper studies and analyzes the service time distribution of SR ARQ protocol. The model is discussed with aid of stochastic processes and Markov Chains. The PGF of the service time distribution is calculated considering transmission of short and long messages. The

First and second moments of service time distribution are derived as well. Results of the analysis can be used either in simulation or approximations of relevant communication models.

1. C. Jin, W. Jinlong, “A novel selective repeat stop-wait ARQ for half-duplex channels,”in 2002 IEEE Region 10 Conference on Computers, Communications, Control and Power Engineering. TENCOM ’02. Proceedings. 28-31 Oct. 2002, Beijing, China, DOI: 10.1109/TENCON.2002.1180350.
2. J. Yun, W. Jeong, M. Kavehrad, “Throughput analysis of selective repeat ARQ combined with adaptive modulation for fading channels,”in MILCOM 2002. Proceedings. 7-10 Oct. 2002, Anaheim, CA, USA, DOI: 10.1109/MIL- COM.2002.1180532.
3. F. Huang, X. Yi, T. Wang, “Reliability-Based Selective Repeat Hybrid ARQ Protocol on Low Density Parity,”in 16th International Conference on Artifi- cial Reality and Telexistence–Workshops (ICAT’06). 29 Nov.-1 Dec. 2006, Hangzhou, China, DOI: 10.1109/ICAT.2006.104.
4. L. Badia, “A Markov Analysis of Selective Repeat ARQ with Variable Round Trip Time,”IEEE Communications Letters, 17(11) , 2184 – 2187, 2013, DoI: 10.1109/CEIT.2016.7929028.
5. F. Chiti, R. Fantacci, A. Tassi, “Evaluation of the Resequencing Delay for Se- lective Repeat ARQ in TDD-Based Wireless Communication Systems,”IEEE Transactions on Vehicular Technology, 63(5), 2450 – 2455, 2014, DOI: 10.1109/TVT.2013.2291432.
6. S. Azad, P. Casari, M. Zorzi, “The Underwater Selective Repeat Error Control Protocol for Multiuser Acoustic Networks: Design and Parameter Optimiza- tion,”IEEE Transactions on Wireless Communications, 12(10), 4866 – 4877, 2013, DOI: 10.1109/TWC.2013.090413.121306.
7. F. Nada, “Service Time Analysis of Go Back N ARQ Protocol,”in 7th Inter- national Conference on Advanced Machine Learning and Technologies and Applications (AMLTA2021), March 20-22, 2021, To appear.
8. F. Nada, “Service Time Distribution of Selective Repeat ARQ Protocol Used In Transmitting Short Messages Over Noisy Channels,”in 12th International Conference on Electrical Engineering (ICEENG), 7-9 July 2020, Cairo, Egypt, DOI: 10.1109/ICEENG45378.2020.9171772.

(Click Here)

(Click Here)