C Program To Implement Go-back-n Arq
Prerequisite: The Stop and Wait ARQ offers error and flow control, but may cause big performance issues as sender always waits for acknowledgement even if it has next packet ready to send. Consider a situation where you have a high bandwidth connection and propagation delay is also high (you are connected to some server in some other country though a high speed connection), you can’t use this full speed due to limitations of stop and wait. Sliding Window protocol handles this efficiency issue by sending more than one packet at a time with a larger sequence numbers. The idea is same as pipelining in architectures. Few Terminologies: Transmission Delay (Tt) – Time to transmit the packet from host to the outgoing link.
If B is the Bandwidth of the link and D is the Data Size to transmit Tt = D/B Propagation Delay (Tp) – It is the time taken by the first bit transferred by the host onto the outgoing link to reach the destination. It depends on the distance d and the wave propagation speed s (depends on the characteristics of the medium). Tp = d/s Efficiency – It is defined as the ratio of total useful time to the total cycle time of a packet. For stop and wait protocol, Total cycle time = Tt(data) + Tp(data) + Tt(acknowledgement) + Tp(acknowledgement) = Tt(data) + Tp(data) + Tp(acknowledgement) = Tt + 2.Tp Since acknowledgements are very less in size, their transmission delay can be neglected. Efficiency = Useful Time / Total Cycle Time = Tt/(Tt + 2.Tp) (For Stop and Wait) = 1/(1+2a) Using a = Tp/Tt Effective Bandwidth(EB) or Throughput – Number of bits sent per second. EB = Data Size(L) / Total Cycle time(Tt + 2.Tp) Multiplying and dividing by Bandwidth (B), = (1/(1+2a)). B Using a = Tp/Tt = Efficiency.
Bandwidth Capacity of link – If a channel is Full Duplex, then bits can be transferred in both the directions and without any collisions. Number of bits a channel/Link can hold at maximum is its capacity. Capacity = Bandwidth(B). Propagation(Tp) For Full Duplex channels, Capacity = 2.Bandwidth(B).
Propagation(Tp) Concept Of Pipelining In Stop and Wait protocol, only 1 packet is transmitted onto the link and then sender waits for acknowledgement from the receiver. The problem in this setup is that efficiency is very less as we are not filling the channel with more packets after 1st packet has been put onto the link. Within the total cycle time of Tt + 2.Tp units, we will now calculate the maximum number of packets that sender can transmit on the link before getting an acknowledgement. In Tt units - 1 packet is Transmitted. In 1 units - 1/Tt packet can be Transmitted. In Tt + 2.Tp units - (Tt + 2.Tp)/Tt packets can be Transmitted - 1 + 2a Using a = Tp/Tt Maximum packets That can be Transmitted in total cycle time = 1+2.a Let me explain now with the help of an example. Consider Tt = 1ms, Tp = 1.5ms.
In the picture given below, after sender has transmitted packet 0, it will immediately transmit packets 1, 2, 3. Acknowledgement for 0 will arrive after 2.1.5 = 3ms. In Stop and Wait, in time 1 + 2.1.5 = 4ms, we were transferring one packet only. Here we keep a window of packets which we have transmitted but not yet acknowledged. After we have received the Ack for packet 0, window slides and the next packet can be assigned sequence number 0.
We reuse the sequence numbers which we have acknowledged so that header size can be kept minimum as shown in the diagram given below. Minimum Number Of Bits For Sender window (Very Important For GATE) As we have seen above, Maximum window size = 1 + 2.a where a = Tp/Tt Minimum sequence numbers required = 1 + 2.a. All the packets in the current window will be given a sequence number. Number of bits required to represent the sender window = ceil(log2(1+2.a)). But sometimes number of bits in the protocol headers is pre-defined. Size of sequence number field in header will also determine the maximum number of packets that we can send in total cycle time.
If N is the size of sequence number field in the header in bits, then we can have 2 N sequence numbers. Window Size ws = min(1+2.a, 2 N) If you want to calculate minimum bits required to represent sequence numbers/sender window, it will be ceil(log2(ws)). In this article, we have discussed sending window only.
For receiving window, there are 2 protocols namely Go Back N and Selective Repeat which are used to implement pipelining practically. We will be discussing receiving window in set 2.
This article has been contributed by Pranjul Ahuja. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
. Introduction This is a GO-BACK-N simulation writen in C# 2.0. Go-Back-N ARQ is a specific instance of the Automatic Repeat-reQuest (ARQ) Protocol, in which the sending process continues to send a number of frames specified by a window size without receiving an ACK packet from the receiver. The receiver process keeps track of the sequence number of the next frame it expects to receive, and sends that number with every ACK it sends. If a frame from the sender does not reach the receiver, the receiver will stop acknowledging received frames. Once the sender has sent all of the frames in its window, it will detect that all of the frames since the first lost frame are outstanding, and will go back to sequence number of the last ACK it received from the receiver process and fill its window starting with that frame and continue the process over again.
Work Structure The simulation includes two different programs. One of them does server operations and the other one does client operations. Firstly client accepts a 10240(40.256) Bytes long file. It splits these bytes into 40 segments. Then user selects the probability of corruption while client is sending segments to the server, the probability of corruption while server is sending acknowledges to the client side and window size which determines the number of segments that are sent in the same time.
C Program To Implement Go-back-n Arq
The client sends segments to the server with the probability of corruption that user has chosen. If packets are dropped, acknowledges are not sent back to client. If packets are received, server can not send acknowledges to client side. Because of the probability of corruption in acks, acks can be dropped.
C Code For Go Back N Arq
After all segments are sent, user can defrag all segments and get the file. Multi threads are used to send segments. Conclusion This simulation performs an unreliable channel using TCP!!! Packets and acknowledges are consciously dropped to show working structure of Go-Back-N.