Sliding Window Protocols? - Part 3

In the third part of this article we shall discuss about the types of sliding window protocols and how these protocols can be extended?

1. Stop and Wait: 

- This one is the simplest type among all the sliding window protocols. 

- Under this type, we have the stop–and–wait ARQ protocol as the simplest implementation.

- Both the transmit window and the receive window is 1 packet and the number of possible sequence numbers required is 2 i.e., 1+1 = 2. 

- The packets sent by the transmitter are marked alternatively as odd and even. 

- Therefore, the ACK packets are in the series of odd, even, odd, even and so on. 

- Now, suppose the transmitter sends an odd packet and immediately without waiting for an odd ACK sends the next even packet. 

- In such a case, it would receive an ACK saying that an odd packet is expected. 

- This leaves the transmitter in a state of ambiguity i.e., whether the receiver got both the packets or none of them.

2. Go-Back-N ARQ: 

- This sliding window protocol has a fixed w_r  (fixed at 1) and w_r  which is always greater than one. 

- Here, the receiver will not accept any packet other than the expected one from the sequence. 

- If the packet gets damaged or lost during the transmission, then the packets following the lost ne will not be accepted by the receiver until and unless it receives the lost one after re-transmission. 

- This ensures minimum loss of 1 RTT (round trip time). 

- This is why it results in inefficiency in using this protocol on the links where the packet loss is quite frequent. 

- Suppose a 3 bit sequence number is being used as in typical HDLC. 

- This means number of sequence numbers is 8 starting from 0 to 7. 

- This also means we have 8 possibilities. 

- Enough ACK information is required by the transmitter for distinguishing between those packets. 

- If 8 packets are sent back to back by the transmitter without stopping for ACK, then it will find itself in the same doubt as in the stop-and-wait case.

3. Selective repeat ARQ: 

- This one is the most general case of the sliding window protocols. 

- It works with a receiver that is more capable of accepting packets having the sequence numbers greater than what the current n_r is and storing them till the gap is filled. 

- The advantage is that discarding data before re-transmission is not necessary.

Ways to extend these protocols

1. The above types of the sliding window protocols don’t talk about reordering the packets after receiving them all. This will ensure that they don’t appear in wrong order. If the long distance can be bounded, the protocols can be extended to support this feature. The maximum mis- ordering distance can be used to expand the sequence number modulus N.
2. Not acknowledging every packet is also possible after the sending an ACK up on not receiving packets. For example, every 2^nd packet is acknowledged in TCP.
3. Informing the transmitter immediately about the presence of gap in the packet sequence is quite common and so HDLC uses a packet called REJ packet for this purpose.
4. During the communication, the window sizes may change if their sum remains in the limit defined by N. usually the transmit window size is reduced for slowing down the transmission in order to keep with the speed of the links and preventing congestion or saturation. 

Sliding Window Protocols? - Part 2

As discussed in part 1 of this article, the sliding window protocol is a type of the packet based data transmission protocol. The sliding window protocols are used in regulating the reliability factor of the data transmission. 

In this second part we discuss about the motivation behind this protocol and how it actually operates. 

- There are a number of communication protocols based up on the automatic repeat request for regulating the error control. 

- In such protocols, it becomes necessary for the receiver for acknowledging about the packets it received. 

- If the receiver does not send an ACK to the transmitter within a specified time period, then the transmitter assumes that the packet might have got lost, re-transmits it. 

- It is obvious that if a transmitter does not receives an ACK for the packet it had sent cannot actually know if the packet got delivered correctly. 

- If, suppose corruption is detected during error detection process on the receiver’s side; the receiver will simply ignore this packet and hence, will not send any ACK to the transmitter. 

- Now in the same way, the receiver also does not know whether the ACK it sent was received by the transmitter or it got lost or damaged during the transmission.

-  In such a case, the re-transmission must be acknowledged by the receiver in order to prevent the continuous re-sending of the data by the transmission. 

- In other cases it is simply ignored.

How the protocol operates?

- The current sequence numbers say n_t and n_r is assigned to transmitter and receiver respectively. 

- Both of them have their window sizes say w_t and w_r respectively.

- In simple implementations of the protocols these sizes are fixed however, they may vary when it comes to the larger and complex implementations. 

- For making any progress, it is necessary that the size of the window must be more than zero. 

- In a typical implementation, n_t denotes the packet to be transmitted. 

- Similarly n_r denotes the packet not received. 

- Both of these numbers increase with the time monotonically. 

- The receiver also has to keep an eye on the highest sequence number that has not been received yet. 

- We have another variable called n_s which is one number greater than the highest sequence number that has been received. 

- There are simple receivers which accept the packets only in the order of w_r = 1 which is nothing but same as the n_r. 

- But in some cases it can exceed 1. 

Now we can say that:

1.     Below n_r no packets have been received.

2.     Above n_s no packets have been received.

3.     It is only between n_r and n_s that some packets have been received.

- Whenever a packet is received, its variables are updated appropriately by the receiver and at the same time an ACK is transmitted with the updated value of n_r. 

- Similarly we have variable n_a used by the transmitter for tracking the highest ACK it has received. 

- Below n_a all the packets have been received but there is uncertainty about the packets between n_s and n_a i.e, the n_r. 

- There are certain rules that are always obeyed by the sequence numbers:

Ø  N_a ≤ n_r: The highest ACK the transmitter has received cannot exceed the highest n_r recorded by the receiver.

Ø  N_r ≤ n_s: The partially received packets’ end cannot be greater than the span of those fully received.

Ø  N_s ≤ n_t: The highest packet sent is always greater than the highest packet received.

Ø  N_t ≤ n_a + w_t: The highest ACK received and the window size set the limits for the highest packet sent.