1. Introduction

Controlling transmission errors is essential for data traffic between network nodes. Automatic Repeat reQuest (ARQ) protocols are implemented at Data Link Control (DLC) sublayer of Data Link Layer (DLL) of Open System Interconnection (OSI) network model to provide error control mechanism and enable reliability of data transmission between different network nodes. ARQ protocols are essential for peer-to-peer protocols that provide reliable data transmission. There are two categories of ARQ protocols: protocols for noisy channels and protocols for noiseless Channel. However, noiseless channels are not available in real life. Noiseless channels are ideal channels which assumes successful delivery for all data. So, there is more concentration on noisy channel protocols, which emphasis flow control and error control mechanisms.

Go-Back-N ARQ (GBN ARQ), Selective Repeat ARQ (SR ARQ) and Stop and Wait ARQ (SW ARQ) are different types of ARQ protocol. Each protocol has a different strategy and methodology for handling data transmission over unreliable channels.The basic algorithm modules used in ARQ protocols are: ACKnowledgments (ACK is a small frame that the receiver sends to the sender to notify successful delivery of a data frame), Negative AcKnowledgment (NAK is a small frame that the receiver sends to the sender to indicate unsuccessful transmission. It tells the sender that some type of error transmission has occurred and that retransmission is required) and time-outs (a period of time that a sender waits before retransmitting the frame). As long as the ACK is not received and time-out expired, the sender will retransmit the frame. This process is repeated until the sender receives the acknowledgment or number of retransmissions exceeds a predefined number. All ARQ protocols use sliding window concept (explained in next section) to tell the sender which (if any) frames need to be retransmitted. Many research articles handled and focused on studying different types of ARQ protocols.

In [1] “analysis and modelling of Automatic Retransmission reQuest (ARQ) protocols as part of a wireless communications system is presented. It considers systems in increasing complexity and is divided into two parts. The first discusses a single link communications and the second proposes point-to-multipoint systems assuming wireless communications. The first part presents a proper discussion and analysis of ARQ protocols communications. The second part investigates power control policies to maximize the amount of data being transferred at the downlink of a cellular communications system as well as at a network with per hop retransmissions”. While [2]: “proposes to analyze the performance of ARQ protocols with applying a Higher Order Logic theorem prover (HOL). The delay of ARQ protocols has been modelled formally as a function of geometric random variable in higher order logic. Actually, this reference develops the behavior of delay of the main ARQ protocols, i.e., SW ARQ, GBN ARQ and SR ARQ. A type of verification of the expected value of the delay formulas has been used in HOL.” “A simulation link for studying and analyzing GBN ARQ protocol” is applied in [3]. However, [4] “analyzed both GBN ARQ protocol together with SR ARQ with intra-block (GBN-SR) and Revised GBN-SR (Rev-GBN-SR) schemes. The presented (Rev-GBN-SR) mechanism has shown better performance with applying bigger range and when the traffic is moving from a low error rate regions to high error rate regions”.

Figure 1: ARQ Protocols

In [5]: “GBN ARQ is discussed with both reliable and unreliable feedback with focus on throughput. Probability measurements have been used to present the results in both cases. The obtained results can be considered as a basic building stone on which larger systems may be built and established.” While [6] used “a two dimensional Markov Chain to study the transmission delay of the GBN ARQ protocol on unreliable correlated channels. The Probability Generating Function (PGF) of the transmission delay of a frame is obtained considering decay factor of a Markov chain. Moreover, an expression of the throughput is obtained. It is shown how the decay factor has affected the protocol performance and the transmission delay.”

On the other hand, [7] studied: “intra block of GBN ARQ and  SR ARQ protocols but assuming limited retransmissions”. However, [8] ”proposed a strategy for controlling error transmissions with multiple parallel channels. It assumes that receiver has a buffer of fixed size (called re-sequencing buffer). This buffer stores out of order packets that are successfully received. Actually, the proposed model can be considered as a combination (hybrid ARQ) GBN ARQ and SR ARQ protocols”.

It is clear from previous review that the main performance measures (specially the system occupancy and the waiting time) of a communication system, when using ARQ protocols, have not been studied properly before. The basic contribution of this article is studying such systems. A new mathematical model for measuring and analyzing the performance of Go-Back-N ARQ protocol is presented. Moreover, the protocol is proposed to be used over noisy channels. Many performance measures of Go-Back-N ARQ protocol are focused on. Complete network evaluation metrics are analyzed when applying Go-Back-N ARQ protocol in data transmission. This work can be considered as a reference for most evaluation results related to Go-Back-N ARQ protocol. Add to this that the analysis results can be adopted and implemented in simulations of relevant communication systems or approximating other systems.

We study the distributions of the waiting time and system occupancy when implementing Go-Back-N ARQ protocol in data traffics. Results include: Probability Generating Functions (PGF) of system occupancy and waiting time. Also, mean values of previous system parameters are derived. Such analysis and results is important in networks analysis, communication systems, and simulation models of larger systems. The paper flows as follows, Next section explains and presents the main concept of sliding window protocols and sheds the light on different types of ARQ protocols. Section 3 introduces the assumptions of the mathematical model under study. In section 4 the PGF of system occupancy and the mean system occupancy are presented. PGF of waiting time and mean waiting time are derived in section 5. Conclusion is the last section.

2. Sliding Window Protocols

Sliding window protocols are implemented at the data link layer (OSI layer 2) and at transport layer (OSI layer 4) for applying error control mechanisms on transmitted traffics. They ensure the reliability and sequential delivery of data transmitted between network nodes. According to the sliding window concept, the sender will be allowed to send multiple frames before waiting for any ACK from the receiver. So, sliding window is trying to enhance the network throughput and reduce traffic delay [9].

Figure 2: Sliding Window Protocol

Sliding window protocols assume that both the sender and the receiver are provided with buffers called sending and receiving window respectively. However, there is a type of dependency or correlation between the maximum size of sending window and the length of the frame sequence field at the frame header. If the length of the sequence number field at the frame header is n, then the frame number will range from 0 to 2ⁿ − 1. Consequently, the maximum size of the sending window can not exceed 2ⁿ − 1. Thus, in order to accommodate a sending window with maximum size of 2ⁿ − 1, the sequence number field should be of n-bit length. In such case the frames sequence numbers are numbered as modulo-n. For example, if the sending window size is 4, then the frame sequence number field should be of 2-bits length to represent the sequence numbers 00, 01, 10, 11 which is interpreted as 0, 1, 2, 3.

On the other hand the size of the receiving window specifies the maximum number of frames that the receiver can accept at a time. Although both Go-Back-N protocol and Selective Repeat protocol are sliding window protocols, there are many differences between them. In case of transmission errors, GBN ARQ protocol will retransmit all the frames after the damaged or lost frame (even if they are correctly received) while in SR ARQ, only damaged or lost frames will be retransmitted.

2.1        Go-Back-N ARQ Protocol

The following points show the GBN ARQ strategy:

• The sender starts by sending multiple frames according to the size of sending window which is 2ⁿ − 1, where n is the size of sequence number field in the frame header.
• The receiver sends an ACK for each correctly received frame.
• The receiver sends a NAK for each damaged or lost frame showing the number of expected frame.

Figure 3: Go-Back-N ARQ Protocol

• If the frame is out of sequence, The receiver discards that frame even if it is correct and sends a NAK for the expected frame.
• After sending a NAK, the receiver discards all the received frames even if the are correctly received (No ACKs are sent for those frames).
• The sender sets a timer for receiving an ACK. If the timer expired (ACK is lost or damaged), the sender will retransmit all non-acknowledged frames.
• After receiving a NAK, the sender will retransmit all the frames sent after the frame referred by the NAK.
• Both ACK number and NAK number indicate the number of the frame expected by the receiver.
• Applying GBN ARQ may lead to wasting bandwidth if the error rate is high.

2.2        Selective Repeat ARQ Protocol

The following points show the SR ARQ strategy:

• The sender starts by sending multiple frames according to the size of sending window which is 2ⁿ − 1, where n is the size of sequence number field in the frame header.
• The receiver sends an ACK for each correctly received frame.
• The receiver sends a NAK for each damaged or lost frame showing the number of expected frame.
• If the frame is out of sequence, the receiver accepts it (sends ACK). The new point is that the receiver is adapted to be able to sort the frames in a proper sequence before submitting to the higher OSI model (Network layer). However, the receiver must hold a buffer to save all the out of sequence received frames till the retransmission process is completed and frames are placed in the correct order.

Figure 4: Selective Repeat ARQ Protocol

• When receiving out of sequence frame, the receiver sends a NAK for the frame it expects.
• After sending a NAK, the receiver accepts all subsequent received frames (if they are correct) and send an ACK for each correct frame.
• The sender sets a timer for receiving an ACK. If the timer expired (ACK is lost or damaged), the sender will retransmit the non-acknowledged frames only.
• After receiving a NAK, the sender will retransmit the NAKed frame only.
• Both ACK number and NAK number indicate the number of the frame expected by the receiver.
• Compared to GBN ARQ, SR ARQ has better performance and needs less window size. Performance evaluation of selective repeat ARQ protocol has been presented in [10].

3. New Mathematical Model Assumptions

The system is modelled as a stochastic process with existence of a sender and a receiver under the following assumptions:

• Time axis is discretized and divided to equal units called slots.
• Messages are divided into fixed length packets which fits exactly one slot and are transmitted through a channel.
• Message transmission starts only after transmission of all packets of the previous message.
• The receiver is considered with a buffer with infinite capacity.
• At messages level the service is FCFS but GBN protocol is considered when transmitting packets of the same message.
• Messages arrive to the system just before the slot boundaries.
• Let the Random Variables (RV) A^k represent the sizes of the messages batches arriving in slot k. The RVs A^k are independent and have the same distribution, with common PGF denoted by A^k(z),

• Let the RV B represents the number of packets in each message,

• Bernoulli process is applied to the random channel transmission errors. If p is the probability of error occurrence in a packet and ε denotes the channel bit error rate, then p can be written as:

where N denotes the number of bits in a packet.

• The receiver uses a return channel for sending ACK or NAK to the sender (to specify the situation of the received packet).
• The RV R represents how many packets can be sent during the time of a round trip propagation delay.
• No transmission errors are considered on the return channel.

4. System Occupancy and Mean System Occupancy

The discussed system is considered as a discrete time queueing system with one server. Let the RV S denotes the transmission (service) time of any transmitted message, with PGF S(z). And the RV S _i represents the transmission time of a message where i represents the number of packets in the message, with PGF S _i(z),

For stability condition of the discussed discrete time queueing system we should have

Arrival rate < departure rate,

But if E[D] is the mean departure rate, then 1/E[D] represents the mean service time E[S]. So we get the stability condition

To determine the average queue length, we have

which represents the mean system occupancy.

5. Waiting Time and Mean Waiting Time

The waiting time is defined as the time between arrival point and the beginning of message transmission. Waiting time distribution has been studied in [12] and we have proved that the PGF of the waiting time (including the service time) is given by

which represents the mean waiting time.

6. Conclusion

GBN ARQ protocol is a sliding window protocol applied at the DLC sublayer of DLL layer of OSI model to provide error and flow control for data transmission at this level. The main work in this article is analyzing and studying the performance of GBN ARQ protocol. Stochastic process has been used to model the discussed system. Many system parameters have been analyzed and calculated. The main results obtained in this paper are: PGF of system occupancy and waiting time. The mean values of previous system parameters are also derived. The analysis results can be used and implemented in simulations of similar communication systems or approximating other related systems.

1. A. Giovanidis, ARQ Protocols in Wireless Communications: Modeling, Analy- sis and Optimization (German Edition), ISBN-13: 978-3838120553.
2. O. Hasan, S. Tahar, “Performance Analysis of ARQ Protocols using a Theorem Prover” in 2008 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), 20-22 April 2008, Austin, TX, USA, DOI: 10.1109/ISPASS.2008.4510741.
3. H. Saleh, M. Elfituri, “Packet communication within a Go-Back-N ARQ system using Simulink” in 2016 4th International Conference on Control Engineering & Information Technology (CEIT). 16-18 Dec. 2016, Hammamet, Tunisia, DOI: 10.1109/CEIT.2016.7929028.
4. Y. Hayashida, A. Maeda, N. Sugimachi, S. Fujii, “Performance analysis of Go- Back-N ARQ scheme with selective repeat in intra-block” IEEE Transactions on Communications, 50(3) , 391 – 395, 2002, DOI: 10.1109/26.9909006.
5. K. Ausavapattanakun, A. Nosratinia, “Analysis of Go-Back-N ARQ in block fading channels” IEEE Transactions on Wireless Communications, 6(8), 2793 – 2797, 2007, DOI: 10.1109/TWC.2007.06062.
6. Y. Hayashida, M. Komatsu, “Delay performance of Go-back-N ARQ scheme with Markovian error channel” in 1993 2nd IEEE International Conference on Universal Personal Communications, 12-15 Oct. 1993, Ottawa, Ontario, Canada, DOI: 10.1109/ICUPC.1993.528425.
7. S. Fujii, T. Kaneko, Y. Hayashida, “Effectiveness of copy-transmission in Go-Back-N ARQ system with selective repeat in intra-block and with limited retransmissions” in 2010 2nd International Conference on COMmunication Systems and NETworks (COMSNETS 2010), 5-9 Jan. 2010, Bangalore, India, DOI: 10.1109/COMSNETS.2010.5432007.
8. Q. Li, C. Chen, “A Hybrid ARQ Protocol for the Communication System with Multiple Channels” in 2018 International Conference on Information and Communication Technology Convergence (ICTC), 17-19 Oct. 2018, Jeju, South Korea, DOI: 10.1109/ICTC.2018.8539714.
9. H. D. Le, V. Mai, C. T. Nguyen, A. T. Pham, “Design and analysis of slid- ing window ARQ protocols with rate adaptation for burst transmission over FSO turbulence channels” IEEE/OSA Journal of Optical Communications and Networking, 11(5) , 151 – 163, 2019, DOI: 10.1364/JOCN.11.000151.
10. F. A. Nada, “Service Time Distribution of Selective Repeat ARQ Protocol Used In Transmitting Short Messages Over Noisy Channels” in 2020 12th IEEE International Conference On Electrical Engineering (ICEENG-12), 7-9 Jul. 2020, Cairo, Egypt, .
11. F. A. Nada, “Steady State Analysis of Buffer Contents in a General Communi- cation System” in 2019 9th International Conference on Intelligent Comput- ing and Information Systems (ICICIS), 8-10 Dec. 2019, Cairo, Egypt. DOI: 10.1109/ICICIS46948.2019.9014737.
12. F. A. Nada, “Unfinished Work & Waiting Time of General Discrete-Time Com- munication System” in 2020 International Conference on Innovative Trends in Communication and Computer Engineering (ITCE), 8-9 Feb. 2020, Aswan, Egypt. DOI: 10.1109/ITCE48509.2020.9047804.

(Click Here)

(Click Here)