The purpose of the data link layer is to transfer blocks of data without error between two adjacent devices. Adjacent devices are physically connected by a communication channel such as telephone lines, coaxial cables, optical fibres, or satellites. The implication of such a physical link is that the data bits are delivered in exactly the same order in which they are sent. The physical link has no inherent storage capacity, therefore the delay involved is the propagation delay over the link.
Transmission of data over the link would be very simple indeed if no error ever occurred. Unfortunately, this is not so in a real physical link for a number of reasons:
At layer 2, user's messages are already broken up into segments.
Control information (headers and trailers) is added to each segment to
make up a frame. We are concerned only with the transmission of frames
between two adjacent IMPs.
We will first look at three elementary data link protocols of increasing complexity.
/* protocol 1 */
Sender()
{
forever
{
from_host(buffer);
S.info = buffer;
sendf(S);
}
}
Receiver()
{
forever
{
wait(event);
getf(R);
to_host(R.info);
}
}
The problem here is how to prevent the sender from flooding the receiver.
A general solution to this problem is to have the receiver provide some sort of feedback to the sender. The process could be as follows: The receiver send an acknowledge frame back to the sender telling the sender that the last received frame has been processed and passed to the host; permission to send the next frame is granted. The sender, after having sent a frame, must wait for the acknowledge frame from the receiver before sending another frame. This protocol is known as stop-and-wait.
The protocol is as follows:
/* protocol 2 */
Sender()
{
forever
{
from_host(buffer);
S.info = buffer;
sendf(S);
wait(event);
}
}
Receiver()
{
forever
{
wait(event);
getf(R);
to_host(R.info);
sendf(S);
}
}
One suggestion is that the sender would send a frame, the receiver would send an ACK frame only if the frame is received correctly. If the frame is in error the receiver simply ignores it; the transmitter would time out and would retransmit it.
One fatal flaw with the above scheme is that if the ACK frame is lost or damaged, duplicate frames are accepted at the receiver without the receiver knowing it.
Imagine a situation where the receiver has just sent an ACK frame back to the sender saying that it correctly received and already passed a frame to its host. However, the ACK frame gets lost completely, the sender times out and retransmits the frame. There is no way for the receiver to tell whether this frame is a retransmitted frame or a new frame, so the receiver accepts this duplicate happily and transfers it to the host. The protocol thus fails in this aspect.
To overcome this problem it is required that the receiver be able to distinguish a frame that it is seeing for the first time from a retransmission. One way to achieve this is to have the sender put a sequence number in the header of each frame it sends. The receiver then can check the sequence number of each arriving frame to see if it is a new frame or a duplicate to be discarded.
The receiver needs to distinguish only 2 possibilities: a new frame or a duplicate; a 1-bit sequence number is sufficient. At any instant the receiver expects a particular sequence number. Any wrong sequence numbered frame arriving at the receiver is rejected as a duplicate. A correctly numbered frame arriving at the receiver is accepted, passed to the host, and the expected sequence number is incremented by 1 (modulo 2).
The protocol is depicted below:
/* protocol 3 */
Sender()
{
NFTS = 0; /* NFTS = Next Frame To Send */
from_host(buffer);
forever
{
S.seq = NFTS;
S.info = buffer;
sendf(S);
start_timer(S.seq);
wait(event);
if(event == frame_arrival)
{
from_host(buffer);
++NFTS; /* modulo 2 operation */
}
}
}
Receiver()
{
FE = 0; /* FE = Frame Expected */
forever
{
wait(event);
if(event == frame_arrival)
{
getf(R);
if(R.seq == FE)
{
to_host(R.info);
++FE; /* modulo 2 operation */
}
sendf(S); /* ACK */
}
}
}
This protocol can handle lost frames by timing out. The timeout interval
has to be long enough to prevent premature timeouts which could cause a
"deadlock" situation.
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.
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.
/* 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);
}
}
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.
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();
}
}
Associated with each outstanding frame is a timer. When the timer goes off, (or when the transmitter is notified of any error), only that one frame is retransmitted, not all the outstanding frames, as in protocol 5.
In this protocol, the receiver's window size is fixed, the maximum of which is (MaxSeq+1)/2 . The maximum number is thus chosen to ensure that there will not be an overlapping between the new window and the previous window. The overlapping of windows means that the receiver would not be able to differentiate between a new frame and a retransmitted frame.
The receiver has a buffer reserved for each sequence number within its window. Whenever a frame arrives, its sequence number is checked to see if it falls within the receiver's window. If so, and if it has not already been received, it is accepted and stored regardless of whether or not it is the next frame expected by the host. Frames passed to the host must always be in order.
Protocol 6 is more efficient than protocol 5 in that:
HDLC is a discipline for the management of information transfer over a data communication channel.
HDLC has a basic structure that governs the function and the use of control procedures. The basic structure includes:
A frame sent from a primary station is referred to as a command
frame. A frame from a secondary to a primary is referred to as a response
frame. Normally when a command is sent, a response or a string of responses
is expected in reply.
On a point-to-point link either station could be the primary. On multidrop
links and where polling is employed, the station which polls the other
is the primary. A station may have several links connected to it. In some
configurations it may be assigned as a primary for some links and a secondary
for others. The station assignments are normally made when a system is
designed.
All frames start and end with the flag byte 01111110. There is a 3-byte header at the start of the frame and a 3-byte trailer at the end. Between the header and the trailer any number of bits can be carried (bit-oriented).
A flag may be followed by a frame, by another flag, or by an idle condition.
ARM is necessary for the control of loops of stations or multi-drop lines with hub polling. In these configurations a secondary may receive a "go-ahead" message from another secondary and transmit in response to it.
Unfortunately, the above two modes are unbalanced modes in which one end of the link is the master and the other end is the slave. To make the protocol more suitable when the two stations are equals (e.g. the nodes of mesh structured computer networks), HDLC has an additional mode: Asynchronous Balanced Mode (ABM).
The I-frames are identified by the first bit sent of the control
field. This bit is a 0.
The next three bits provide counts for numbering the frame being sent. It is called the send sequence number (N(S)).
The next bit is the Poll/Final bit. It is the send/receive control. A P bit is sent to a secondary station to authorise transmission. An F bit is sent by a secondary station in response to the P bit. Normally, only one P bit is outstanding on the data link.
The next three bits provide counts for numbering the frame expected to be received next. It is a piggybacked acknowledgement, and is called the receive sequence number (N(R)).
The S-frames are identified by the first two bits sent of the control
field. These are 10.
The next two bits are used for coding the commands and responses.
The Poll/final bit is as in the I-frame.
The next three bits form N(R), which indicates that all I-frames numbered up to N(R)-1 have been correctly received and the receiver is expecting the I-frame numbered N(R).
The S-frame does not contain an information field. Consequently it does not have N(S) and it is normally a six byte frame.
The four types of S-frame are described below:
The DISC command terminates an operational mode previously set by a command and places the receiving secondary station effectively off line. The expected response is a UA frame. DISC contains no information field.
The Unnumbered Acknowledge (UA) frame is used by the secondary station to acknowledge the receipt and acceptance of U-frame commands from the primary. The UA frame contains no information field.
The CMDR response is used by a secondary station when it receives a non-valid frame. A received frame may be non-valid for several reasons:
The receiving station constantly monitors the line and searches for a flag. When a flag is detected the receiver knows that a frame is on its way, and checks the address byte received to see whether the frame is destined for it or not. If it is, the receiver then continues to receive all the bits of the frame until another flag is seen. The receiver then computes the FCS and compares it with that received. If the frame is correctly and properly received, the receiving station will send an acknowledgement (ACK) message to the sender at the earliest opportunity. The ACK message could be a separate message or it could be piggybacked on an I-frame travelling to the original sender.