Sliding Window Protocols

These protocols comes under the data link layer.data link layer. It provides services to the network layer. It’s a bidirectional protocol. It means sender deletes the frames when it gets the acknowledgment.

The essence of all 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.



The sequence numbers within the sender’s window represent frames that have
been sent or can be sent but are as yet not acknowledged. When new packet from network layer comes in to send, it is given highest no and the upper edge of window is advanced by 1. When the acknowledgment comes in, lower edge of the window is advanced by 1.

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. The receiving data link layer’s window corresponds to the frames it may accept. 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 acknowledgment is generated, and the window is rotated by one.

Types of sliding window protocols

- One-Bit sliding window protocols.
- Go Back N sliding window protocols.
- Selective Repeat sliding window.

Concept of Piggybacking

The data link layer provides service to the Network Layer above it:
* The network layer is interested in getting messages to the corresponding network layer module on an adjacent machine.
* The remote Network Layer peer should receive the identical message generated by the sender (e.g., if the data link layer adds control information, the header information must be removed before the message is passed to the Network Layer).
* The Network Layer wants to be sure that all messages it sends, will be delivered correctly (e.g., none lost, no corruption). Note that arbitrary errors may result in the loss of both data and control frames.
* The Network Layer wants messages to be delivered to the remote peer in the exact same order as they are sent.

Interleaving data and control frames on the same circuit is an improvement over having two separate physical circuits, yet another improvement is possible. When a data frame arrives, instead of immediately sending a separate control frame, the receiver restrains itself and waits until the network layer passes it the next packet. The acknowledgment is attached to the outgoing data frame. In effect, the acknowledgment gets a free ride on the next outgoing data frame.

The technique of temporarily delaying outgoing acknowledgments so that they can be hooked onto the next outgoing data frame is known as piggybacking.
Advantage : Better use of available channel bandwidth.
Disadvantage : If the data link layer waits longer than the sender’s timeout period, the frame will be retransmitted, defeating the whole purpose of having acknowledgments.

Concept of Bit stuffing

Bit stuffing is the insertion of one or more bits into a transmission unit as a way to provide signaling information to a receiver. The receiver knows how to detect and remove or disregard the stuffed bits.

Bit stuffing is required by many network and communications protocols for the following reasons:
- To prevent data being interpreted as control information. For example, many frame-based protocols, such as X.25, signal the beginning and end of a frame with six consecutive 1 bits. Therefore, if the actual data being transmitted has six 1 bits in a row, a zero is inserted after the first 5 so that the dat is not interpreted as a frame delimiter. Of course, on the receiving end, the stuffed bits must be discarded.
- For protocols that require a fixed-size frame, bits are sometimes inserted to make the frame size equal to this set size.
- For protocols that required a continuous stream of data, zero bits are sometimes inserted to ensure that the stream is not broken.



Each frame begins and ends with a special bit pattern, 01111110, called a flag byte. When the sender's data link layer encounters five consecutive ones in the data, it automatically stuffs a 0 bit in the outgoing bit stream. When the receiver sees five consecutive 1 bits, followed by 0 bit, it automatically destuffs the 0 bit. Bit stuffing is completely transparent to the network layer.
With bit stuffing, the boundary between two frames can be unambiguously recognized by the flag pattern. If the receiver loses track, all it has to do is scan the input for flag sequences.

Framing in Data Link Layer

The data link layer detects the number of bits transmitted by physical layer to be error free. The approach used is to break the bit stream up into discrete frames and compute the checksum for each frame. When a frame arrives at the destination, the checksum is recomputed. If this checksum is different from the one obtained in the frame, the data link layer knows that an error has occurred and takes steps to deal with.
There are three different types of framing, each of which provides a way for the sender to tell the receiver where the block of data begins and ends:
- Byte-oriented framing : Computer data is normally stored as alphanumeric characters that are encoded with a combination of 8 bits (1 byte). This type of framing differentiates one byte from another.
- Bit-oriented framing : This type of framing allows the sender to transmit a long string of bits at one time.
- Clock-based framing : In a clock-based system, a series of repetitive pulses are used to maintain a constant bit rate and keep the digital bits aligned in the data stream.

The following methods are commonly used for calculating the check sum :
- Character Count : It uses a field in the header to specify the number of characters in the frame. When data link layer at destination sees the character count, it knows how many characters follow, and hence where the end of frame is. The disadvantage with this method is that the count can be garbled by a transmission error.

- Character stuffing : This method gets around the problem of resynchronization after an error. Each frame starts with the ASCII character sequence DLE(Data Link Escape) STX(Start of Text) and end with the sequence DLE ETX(End of Text). If the destination loses track of frame boundaries, all it has to do is to look for DLE STX or DLE ETX. Problem occurs when binary data such as object programs or floating point numbers are transmitted. Solution to this problem is to have sender's data link layer insert an ASCII DLE character just before each accidental DLE character in the data. The data link layer on receiving end removes the DLE before the data is given to the network layer. This is called character stuffing. A disadvantage of using this framing method is that it is closely tied to 8-bit characters.
-