Sliding Window Protocols

In this chapter, we study the Sliding Window Protocols and the implementation details of the applets designed to simulate their working.

Sliding Window Protocol Features

The data link protocols such as the simplex protocols discussed in the preceding chapter allow only simplex transmission. However, in most practical situations, there is a need for transmitting data in both directions. An efficient implementation of duplex transmission makes use of the same circuit for data in both directions, instead of having two separate physical circuits and use each one for simplex data traffic (in different directions). Though interleaving data and control frames on the same circuit is an improvement over the above stated separate physical circuits, yet another improvement is possible. When a data frame arrives at the data link layer of a communicating machine, instead of immediately sending a separate control frame, the receiver waits till the network layer passes it the next packet to be transmitted. The acknowledgement is attached to the outgoing data frame (using the ‘ack’ field in the frame header). Thus there is no need for transmitting a separate acknowledgement frame. This technique of temporarily delaying outgoing acknowledgements so that they can be attached onto the next outgoing data frame is known as piggybacking.

The main advantage of using piggybacking over having distinct acknowledgement frames is a better use of the available channel bandwidth. The ‘ack’ field in the frame header occupies only a few bits, whereas a separate frame would need a header, the acknowledgement, and a checksum (for error detection). In addition, fewer frames sent means fewer ‘frame arrived’ interrupts, and perhaps fewer buffers in the receiver, depending on how the receiver’s software is organised. In most of the sliding window protocols, the piggyback field rarely occupies more than a few bits.

Fig. 3-1 Sliding Window Protocol Frame Format

As shown, each outbound frame (the frame passed to the physical layer for transmission) contains a sequence number, ranging from 0 to some maximum. The maximum is usually 2n - 1, so the sequence number exactly occupies an n-bit field. The stop-and-wait sliding window protocol uses n = 1, but more sophisticated versions can use arbitrary n.

The main theory behind the sliding window protocols is that at any instant of time, the sender maintains a set of sequence numbers corresponding to frames it is permitted to send. These frames are said to fall within the sending window. Similarly, the receiver also maintains a receiving window corresponding to the set of frames it is permitted to accept. The sender’s window and the receiver’s window need not have the same lower and upper limits, or even have the same size. In some protocols they are of fixed size, but in others they can grow or shrink as frames are sent and received. It can be observed that the protocols give the data link layer more freedom about the order in which it may send and receive frames, and at the same time maintains the requirement that the protocol must deliver packets to the network layer of the destination machine in the same order that they were passed to the data link layer on the sending machine. Also, the requirement that all frames must be delivered in the order sent is not changed.

1 – Bit Sliding Window Protocol

Consider the following scenario with a sliding window size of 1, with a 1-bit sequence number.

1-bit Sliding Window Protocol

  1. This is the initial state. The sender has not commenced transmission. So its sending window is empty. The receiver, on the other hand, is ready to receive the 1st frame.
  2. This is the state after the first frame has been sent. The window in the sending process indicates that frame 0 has been sent.
  3. This is the state after the first frame has been received. The receiver’s window is advanced by 1 so that it is now ready to receive frame 1.
  4. This is the state after the first acknowledgement has been received. The sender’s window is now advanced by 1 so that it is ready to transmit frame 1.

The sequence numbers within the sender’s window represent frames sent but as yet not acknowledged. Whenever a new packet arrives from the network layer, it is given the next highest sequence number, and the upper edge of the window is advanced by one. When an acknowledgement comes in, the lower edge is advanced by one. In this way, the window continuously maintains a list of unacknowledged frames. Since frames currently within the sender’s window may ultimately be lost or damaged in transit, the sender must keep all these frames in its memory for possible retransmission. Thus if the maximum window size is n, the sender needs n buffers to hold the acknowledgement frames. If the window ever grows to its maximum size, the sending data link layer must forcibly shut off the network layer until another buffer becomes free.

The receiver’s window corresponds to the frames it may accept. Any frame falling outside the window (not bearing the requisite seq. no.) is discarded straightaway. When a frame whose sequence number is equal to the lower edge of the window is received, it is passed to the network layer, an acknowledgement is generated, and the window is rotated by one. The sender’s window may change in size, but the receiver’s window always remains at its initial size. This is clearly illustrated in the above example.

So, in case of the n-bit sliding window protocol, the maximum window size will be 2n - 1 (i.e., for a 2-bit sliding window protocol maximum window size is 3, for a 3-bit sliding window protocol it is 7 and so on). A window size of 1 means that the data link layer only accepts frames in order (by seq. no.), but for larger windows this is not the case i.e. the receiver can accept frames out of order if they bear sequence numbers within the receiving window. However, the network layer is always fed data in the proper order, irrespective of the data link layer’s window size.

Fig. 3-3 A sliding window of size 1 and 3-bit sequence no.

In Fig. 3-3 above, a sliding window of size 1 with a 3-bit sequence number has been depicted. The various stages are…

  1. Initial stage, when transmission has not commenced.
  2. After the first frame has been sent.
  3. After the first frame has been received.
  4. After the first acknowledgement has been received.
Error Control

Error control refers to the mechanisms to detect and correct errors that occur in the transmission of frames. The two common types of errors are :

  1. Lost frame : A frame fails to arrive at the other side. A noise burst may have damaged a frame to the extent that the receiver is not aware that a frame has been transmitted.
  2. Damaged frame : A recognisable frame does arrive but some of the bits are in error (have been altered during transmission).

The most common techniques for error control are :

Collectively, these mechanisms are all referred to as automatic repeat request (ARQ). The three popular versions of ARQ with respect to the Sliding Window Protocol, have been described below :

Stop-and-Wait ARQ

The frame transmitted by the source could suffer an error. If the error is detected by the destination, it discards the frame and sends a negative acknowledgement (NAK) back to the sender, causing the source to retransmit the damaged frame. On the other hand, if the transmitted frame is so corrupted by noise as not to be received, the destination will not respond. To account for this possibility, the source is equipped with a timer. After a frame is transmitted, the source waits for an acknowledgement (ACK or NAK). If no recognizable acknowledgement is received during the timeout period, then the frame is retransmitted. Hence, as can be seen the source station should maintain a copy of the transmitted frame until an ACK is received for that frame.

The principal advantage of the Stop-and-Wait ARQ is its simplicity. However, its disadvantage is that it is an inefficient protocol because of poor bandwidth utilization. This demerit clearly assumes substantial proportions, especially when the transmission time required for a frame to arrive at the receiver plus the transmission time for the acknowledgement to come back is very high.

Consider that station A is sending frames to station B. After each transmission, A sets an acknowledgement timer for the frame just transmitted. The go-back-N technique takes into account the following contingencies …

1. Damaged frame

    1. Station A transmits frame i. Station B detects an error and has previously successfully received frame (i-1). B sends a NAK i, indicating that frame i is rejected. When A receives this NAK, it must retransmit frame i and all subsequent frames that it has transmitted.
    2. Frame i is lost in transit. Station A subsequently transmits frame (i+1). Station B receives frame(i +1) out of order, and sends a NAK i.
    3. Frame i is lost in transit and station A does not soon send additional frames. Station B receives nothing and returns neither an ACK nor a NAK. Station A will timeout and retransmit frame i.

2. Damaged ACK

  1. Station B receives frame i and sends ACK(i+1), which is lost in transit. Since ACK’s are cumulative (e.g., ACK 6 means that all frames through 5 are acknowledged), it may be that Station A will receive a subsequent ACK to a subsequent frame that will do the job of the lost ACK before the associated time expires.

  2. If Station A’s timer expires, station A retransmits frame i and all subsequent frames.
3. Damaged NAK

If a NAK is lost, station A will eventually time out on the associated frame and retransmit that frame and all subsequent frames.

Go-back-N ARQ

The above figure shows the frame flow for go-back-N ARQ on a full duplex line, assuming a 3-bit sequence number. As is evident, from the explanation in the preceding paragraph, it is not required that each individual frame be acknowledged. For example, station A sends frames 0,1, 2 and 3. Station B responds with ACK1 after frame 0, but then does not respond to frames 1 and 2. After frame 3 is received, station B issues ACK4, indicating that frame 3 and all previous frames have been accepted.

As can be seen from the figure below depicting Selective Repeat, it is easily discernible that the Selective Repeat approach minimizes the amount of retransmissions. However, the receiver must also contain storage to save the post-NAK frames until the frame in error is retransmitted, and moreover this retransmitted frame must also be inserted in the correct sequence before the transmitted frames are passed on to the network layer. The transmitter, too, will require more complex logic to be able to send frames out of sequence. Due to such complications, the Selective Repeat (also known as Selective Reject) is seldom implemented.

Selective Repeat ARQ

The Go-back-N and the Selective Repeat approaches improve bandwidth utilisation by incorporating pipelining in their working. Both these approaches differ in the sense that the Go-back-N strategy is applicable to a window size of 1 (i.e., the receiving data link layer refuses to accept any frame except the next one it must give to the network layer). Also in go-back-N, a lot of bandwidth will be wasted if the error rate is high. On the other hand, the Selective Repeat strategy corresponds to a window size larger than 1 (i.e., any frame within the window may be accepted and buffered until all the preceding ones have been passed to the network layer). This approach can require larger amounts of data link layer memory if the window is large.

Thus, these two approaches are trade-offs between the bandwidth and data link layer buffer space. Depending on which resource is more valuable, one or the other can be implemented.

This section having dealt with the features and working of the Sliding Window Protocol, the remaining sections of this chapter explain the working and the class hierarchy of the Java applets designed as teaching tools, to study the behavior of this robust data-link protocol.

Applet Design

Since the simulator has been developed in Java, which is an Object-Oriented Language, the design entails the discussion of the classes (which represent the objects that a data link layer protocol implementing flow control using the sliding window protocol would contain) and their methods. These components have been listed below.

Review of Design

The foregoing discussion of the class structure suggests that the important objects essential for effective representation of the real-world sliding window protocol implementation have been identified and classes have been constructed for them.

The "Packet" class represents a data frame precisely. The sendPacket method of this class concentrates on the movement of the packet for the sliding window control and is a complete module in itself. It can be easily overloaded to simulate some other protocol while using the same class to represent the packet.

The "Canvas1" class contains most of the functionality of the applet, except that for handling the buttons and threads that control the simulation. Thread control is exercised completely by the main class i.e ‘Sliding’. This is essential as only the class at the top of the hierarchy should be trusted with the controlling of threads. The buttons are used for a very short time compared to the time the applet runs for, and since the action to be taken for handling the buttons is relatively straightforward, it can easily be handled by the main class itself. The various stages of simulation are drawn on the canvas thus making it very convenient to program and understand if most of the work is carried out in methods of this class.

A separate class is designed for displaying ‘help’ messages. This helps in achieving data and code abstraction, at the same time permitting code reusability. The contents of the ‘help’ can be easily changed without effecting rest of the design or the program. Similarly, a ‘help’ class developed for this applet can be conveniently reused for another applet by simply modifying the string that the help is supposed to display. Rest of the functionality is unchanged.

Thus the design appears to be well-structured and robust. The class ‘Containership’ mechanism is used effectively for passing of simulation parameters and for evenly distributing the complexity in the various classes. This helps in code maintainability and reusability. It is evident that the applet design is efficient and represents quite accurately the needs of the application.

In the next chapter we investigate the CSMA/CD protocol and its design in detail.

Home | Contents | Previous chapter | Return to top of document.