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.

Explain the concept of piggybacking?

- Piggybacking is a well known technique used in the transmission of data in the third layer of the OSI model i.e., the network layer. 

- It is employed in making a majority of the frames that are transmitted from receiver to the emitter. 

- It adds to the data frame, the confirmation that the sender sent on successful delivery of data frame. 

- This confirmation is called the ACK or acknowledge signal. 

- Practically, this ACK signal is piggybacked on the data frame rather than sending it individually by some other means. 

Principle behind Piggybacking

- The piggybacking technique should not be confused with the sliding window protocols that are also employed in the OSI model. 

- In piggybacking, an additional field for the ACK or the acknowledgement signal is incorporated in to the data frame itself. 

- There is only a difference of bit between the sliding window protocol and piggybacking.

- Whenever some data has to be sent from party to another, the data will be sent along with the field for ACK. 

The piggybacking data transfer is governed by the following three rules:

Ø  If both the data as well as the acknowledgement have to be sent by the party A, it has to include both the fields in the same frame.

Ø  If only the acknowledgement has to be sent by the party A, then it will have use a separate frame i.e., an ACK for that.

Ø  If only the data has to be by the party A, then the ACK field will be included within the data frame and thus transmitted along with it. This duplicate ACK frame is simply ignored by the receiving party B.

- The only advantage of using this technique is that it helps in improving efficiency. 

- The disadvantage is that is the service can be blocked or jammed by the receiving party if there is no data to be transmitted. 

- Enabling a receiver timeout by means of a counter the moment when the party receives the data frame can solve this problem to a great extent. 

- An ACK control frame will be sent by the receiver if the timeout occurs and still there is no data for transfer. 

- A counter called the emitter timeout is also set up by the sender which if ends without getting any confirmation from the receiver will make the sender assume that the data packet got lost in the way and therefore will have to re-transmitted.

- Piggybacking is also used in accessing the internet.

- It is used in establishment of a wireless internet connection by means of wireless internet access service of the subscriber without taking explicit permission from the subscriber. 

- However, according to the various jurisdiction laws around the world, this practice is under ethical and legal controversy. 

- In some places it is completely regulated or outlawed while at other places it is allowed.  

- A business customer who provides services related to hotspots, as of cafe and hotels, cannot be thought of using piggybacking technique via non – customers. - A number of such locations provide services for a fee.