[Read
FitzGerald p185,194-195 in 5th Ed. and p147-154 in 6th Ed.]
The Data Link Layer’s primary function is to manage the Physical Layer. Its major concerns are:
connection management
error control
flow control.
Before data can be sent across a link there must be a circuit in place. The Data Link Protocol in use must be able to setup this link, control its operation, and then disconnect it when finished. Don’t confuse this function with the function of the Session Layer. At the Data Link Layer we are referring to the control of the physical layer, whereas the Session Layer is concerned with ‘logical’ concepts such as login, passwords, user-id, etc.
At the data link level control or supervisory frames are used to provide ‘handshaking’ between the Data Link peer layers, as well as frames that pass on data from higher layers (often called an I-frame); there may be frames that merely pass controlling information between the peer processes (eg an ACK/NAK frame, or a frame that asks if a secondary device has got any messages to send - called polling). RS232 handshaking (RTS/CTS) is a relevant example.
Ensuring that the frame passed across the link actually arrived, was error free, and was not duplicated, are functions of the Data Link Layer. Methods wasteful of transmission capacity (such as echo checking) are not normally appropriate - even if they do provide a high degree of protection. Sending redundant information in such a way that the receiving device can recover any errors is called forward error correction. This method (although very useful when using some types of media, for instance satellite transmission) is also inefficient. Another method (known as Automatic Repeat reQuest, or ARQ) is available. ARQ relies upon the receiver being able to detect a frame in error and then somehow (via a set of protocol rules) being able to request the sender to retransmit the frame. There are several types of ARQ, each of which provides a varying degree of efficiency.
The least efficient of the ARQs are the Idle RQ (or ’stop-and-wait’) protocols used with character/byte oriented protocols. These literally stop sending after each frame and wait for either an implicit or explicit request for a retransmission. Consequently these are known as half duplex protocols and have poor line utilisation (particularly on circuits with a long transmission delay, such as satellites), since for a good deal of the time the sender is paused awaiting confirmation of success before the next frame can be sent.
In implicit retransmission, only correctly received frames are ‘ACK’ed (acknowledged). Therefore the sender recognises error frames through the absence of an ACK. Unfortunately this can only occur after a timeout interval. The timer is set by the sender after sending and must be long enough to cater for all transmission, turnaround and processing delays. Obviously, this can be very inefficient on a circuit with a less than ideal bit error rate. The timeout period has to be very carefully considered. For these reasons it is rarely used.
Explicit retransmission has better utilisation because the receiver responds with a NAK (negative ACK) if an error is received - this short circuits the timeout problem. Note that a timer is still required though, because it is possible that the sent frame is not recognised/received by the receiver, and therefore a NAK will not be sent.
Either method can easily lead to duplicates (a duplicate frame) being sent (exercise: work out how this could happen). There must be a way of detecting duplicates. A sequence number (or flag) is normally used. Commonly, this appears within the header of each frame.
Any error is detected via the methods we discussed earlier; such as parity, LRC/BCC, checksum, CRC, etc. The appropriate character(s) are appended to each frame.
Idle RQ methods require that a retransmission buffer capable of storing one frame must be available to the sender.
A more efficient Continuous RQ error control scheme is possible. Here the sender sends continuously. This system is commonly used with bit-oriented full duplex protocols. For reasons of efficiency (sequence number size limitation and the number of send and receive buffers available) it is normal to limit the number of unacknowledged frames, ie the sender is only permitted to send a finite number of frames before having to ‘wait’ for an ACK. This is often referred to as a ‘window’ of frames and it is then referred to as a sliding window protocol. Note that a send window of size 1 is merely the Idle RQ protocol! The two error retransmission strategies of Continuous RQ are selective repeat and go-back-N.
With selective repeat either implicit or explicit retransmission requests of a particular frame are possible. An implied request is made when the sender receives an acknowledgment for a later frame. An explicit request is when a frame is NAKed (this is also known as selective reject). The downside of this method is that out of sequence frames must be buffered until missing frames are received - ie large buffering requirements, therefore go-back-N is more often implemented.
Go-back-N is where the receiver tells the sender to go back to frame N and start retransmitting from there. This strategy is simpler to implement (less buffering requirements) but is less efficient - since some good frames will be sent twice.
When designed and working properly with no errors, Continuous RQ strategies can keep a circuit fully utilised. Continuous RQ is particularly suitable with duplex transmission. In this case the acknowledgments can be piggybacked upon I-frames transmitted in the reverse direction.
The final requirement of the Data Link Layer is the ability to slow down or stop the sending of frames when the receiver is unable to store or process further frames. Hopefully this is a temporary requirement and so there needs to be a mechanism for restarting the transfers. Note that a simple method of providing flow control is to limit the speed of the transmission line (bps) below that of the minimum processing speed. The provision of a ‘huge’ buffer also reduces the need for flow control.
Flow control is implicitly present in half duplex echo checking and idle RQ since if the receiver is too busy or unable to echo/ACK/NAK frames the sender will just keep retransmitting the frame after a time interval. This can cause problems though because the arrival of frames at the busy receiver will cause some unnecessary overhead. Also the sender may eventually decide that the link is ‘down’ and hence close down communications.
Three other methods are X-ON/X-OFF, RTS/CTS handshaking, and use of the finite Sliding Window discussed earlier.
When the receiver’s buffers become full the receiver sends an X-OFF command to the sender. The sender interprets this as a request to wait and patiently does so until the receiver sends an X-ON command. Historically, this system has been used between computer and printer since the computer can fill the printer’s buffer much faster than the printer can print. It does require full duplex operation (or reverse channel ability).
‘Hard’ handshaking using the RS232 control lines RTS and CTS can be used in some instances - particularly DTE to DTE working.
Limiting the Continuous RQ’s number of unacknowledged frames also implies flow control. If the receiver doesn’t acknowledge then the sender must stop (eventually). This method requires that the receiver has the same number of buffers to ensure that all frames can be held awaiting processing (or else they would have to be resent).
The name sliding window comes
about because if there were no errors, the send window is a fixed size window
that moves (slides) over the complete set of frames being transmitted.