Elementary Data Link Protocols-Sliding Window Protocols
Sliding Window Protocols
Piggybacking technique
In most practical situations there is a need for transmitting data in both directions (i.e. between 2 computers). A full duplex circuit is required for the operation.
If protocol 2 or 3 is used in these situations the data frames and ACK (control) frames in the reverse direction have to be interleaved. This method is acceptable but not efficient. An efficient method is to absorb the ACK frame into the header of the data frame going in the same direction. This technique is known as piggybacking.
When a data frame arrives at an IMP (receiver or station), instead of immediately sending a separate ACK frame, the IMP restrains itself and waits until the host passes it the next message. The acknowledgement is then attached to the outgoing data frame using the ACK field in the frame header. In effect, the acknowledgement gets a free ride in the next outgoing data frame.
This technique makes better use of the channel bandwidth. The ACK field costs only a few bits, whereas a separate frame would need a header, the acknowledgement, and a checksum.
An issue arising here is the time period that the IMP waits for a message onto which to piggyback the ACK. Obviously the IMP cannot wait forever and there is no way to tell exactly when the next message is available. For these reasons the waiting period is usually a fixed period. If a new host packet arrives quickly the acknowledgement is piggybacked onto it; otherwise, the IMP just sends a separate ACK frame.
Sliding window
When one host sends traffic to another it is desirable that the traffic should arrive in the same sequence as that in which it is dispatched. It is also desirable that a data link should deliver frames in the order sent.
A flexible concept of sequencing is referred to as the sliding window concept and the next three protocols are all sliding window protocols.
In all sliding window protocols, each outgoing frame contains a sequence number SN ranging from 0 to 2^(n -1)(where n is the number of bits reserved for the sequence number field).
At any instant of time the sender maintains a list of consecutive sequence numbers corresponding to frames it is permitted to send. These frames are said to fall within the sending window. Similarly, the receiver maintains a receiving window corresponding to frames it is permitted to accept.
The size of the window relates to the available buffers of a receiving or sending node at which frames may be arranged into sequence.
At the receiving node, any frame falling outside the window is discarded. Frames falling within the receiving window are accepted and arranged into sequence. Once sequenced, the frames at the left of the window are delivered to the host and an acknowledgement of the delivered frames is transmitted to their sender. The window is then rotated to the position where the left edge corresponds to the next expected frame, RN.
Whenever a new frame arrives from the host, it is given the next highest sequence number, and the upper edge of the sending window is advanced by one. The sequence numbers within the sender's window represent frames sent but as yet not acknowledged. When an acknowledgement comes in, it gives the position of the receiving left window edge which indicates what frame the receiver expects to receive next. The sender then rotates its window to this position, thus making buffers available for continuous transmission.
A one bit sliding window protocol: protocol 4
The sliding window protocol with a maximum window size 1 uses stop-and-wait since the sender transmits a frame and waits for its acknowledgement before sending the next one.
/* protocol 4 */
Send_and_receive()
{
NFTS = 0;
FE = 0;
from_host(buffer);
S.info = buffer;
S.seq = NFTS;
S.ack = 1-FE;
sendf(S);
start_timer(S.seq);
forever
{
wait(event);
if(event == frame_arrival)
{
getf(R);
if(R.seq == FE)
{
to_host(R.info);
++FE;
}
if(R.ack == NFTS)
{
from_host(buffer);
++NFTS;
}
}
S.info = buffer;
S.seq = NFTS;
S.ack = 1-FE;
sendf(S);
start_timer(S.seq);
}
}
Pipelining
In many situations the long round-trip time can have important implications for the efficiency of the bandwidth utilisation.
As an example, consider a satellite channel with a 500ms round-trip propagation delay. At time t~~=0 the sender starts sending the first frame. Not until at least t~>=~500 ms has the acknowledgement arrived back at the sender. This means that the sender was blocked most of the time causing a reduction in efficiency.
As another example, if the link is operated in a two-way alternating mode (half-duplex), the line might have to be "turned around" for each frame in order to receive an acknowledgement. This acknowledgement delay could severely impact the effective data transfer rate.
The effects of these problems can be overcome by allowing the sender to transmit multiple contiguous frames (say up to w frames) before it receives an acknowledgement. This technique is known as pipelining.
In the satellite example, with a channel capacity of 50kbps and 1000-bit frames, by the time the sender has finished sending 26 frames, t~=~520 ms, the acknowledgement for frame 0 will have just arrived, allowing the sender to continue sending frames. At all times, 25 or 26 unacknowledged frames will be outstanding, and the sender's window size needs to be at least 26.
Pipelining frames over an unreliable communication channel raises some serious issues. What happens if a frame in the middle of a long stream is damaged or lost? What should the receiver do with all the correct frames following the bad one?
The are two basic Automatic Request for Repeat (ARQ) methods for dealing with errors in the presence of pipelining.
One method, the normal mode of ARQ is called Go-back-N. If the receiver detects any error in frame N, it signals the sender and then discards any subsequent frame.
The sender, which may currently be sending frame N+X when the error signal is detected, initiates retransmission of frame N and all subsequent frames.
The other method is called selective reject. In this method the receiver stores all the correct frames following the bad one. When the sender finally notices what was wrong, it just retransmits the one bad frame, not all its successors.
Protocol 5: Pipelining, Multiple outstanding frames (MaxSeq)
In this protocol, the sender may transmit up to MaxSeq frames without waiting for an acknowledgement. In addition, unlike the previous protocols, the host is not assumed to have a new message all the time. Instead, the host causes host ready events when there is a message to send.
This protocol employs the Go-back-N technique. In the example below, the window size of the receiver is equal to 1, and a maximum of MaxSeq frames may be outstanding at any instant.
/* protocol 5 */
send_data(frame_number)
{
S.info = buffer[frame_number];
S.seq = frame_number;
S.ack = (FE+MaxSeq) % (MaxSeq+1);
sendf(S);
start_timer(frame_number);
}
send_receive()
{
enable_host();
NFTS = 0;
Ack_expected = 0;
Frame_expected = 0;
nbuffered = 0;
forever
{
wait(event);
switch(event)
{
case host_ready:
from_host(buffer[NFTS]);
++nbuffered;
send_data(NFTS);
++NFTS;
break;
case frame_arrival:
getf(R);
if(R.seq == Frame_expected)
{
to_host(R.info);
++Frame_expected;
}
if( (Ack_expected <= R.ack && R.ack < NFTS)
||(NFTS < Ack_expected && Ack_expected <= R.ack)
||(R.ack < NFTS &&NFTS < Ack_expected))
{
--nbuffered;
stop_timer(Ack_expected);
++Ack_expected;
}
break;
case checksum_error:
/* just ignore the bad frame */
break;
case timeout:
NFTS = Ack_expected;
i = 0;
do
{
send_data(NFTS);
++NFTS;
++i;
} while(i<=nbuffered);
break;
}
if(nbuffered < MaxSeq)
enable_host();
else
disable_host();
}
}
