Basics Of Data Communication: Part 5

Data Link Control

Data Link Control (DLC) is the service provided by the data link layer of function defined in the Open Systems Interconnection (OSI) model for network communication. The Data Link layer is responsible for providing reliable data transfer across one physical link within the network.

To see the need for data link control, we list some requirements and objectives for effective data communication between two directly connected transmitting-receiving stations. Here is the list of all

  1. Frame Synchronization

    Data are sent in blocks called frames. The beginning and end of each frame must be recognizable.

  2. Flow Control

    The sending station must not send frames at a rate faster than the receiving station can absorb them.

  3. Error Control

    Any bit errors introduced by the transmission system must be corrected.

  4. Addressing
    On a multipoint line, such as a local area network (LAN), the identity of the two stations involved in a transmission must be specified.

  5. Control and data on same link

    It is usually not desirable to have a physically separate communications path for control information. Accordingly, the receiver must be able to distinguish control information from the data being transmitted.

  6. Link Management

    The initiation, maintenance and termination of a sustained data exchange require a fair amount of coordination and cooperation among stations. Procedures for the management of this exchange are required.

Error Detection

While transmitting data from one station to another, care should be taken to ensure that the receiver receives the same data as sent by the sender without any error. The purpose of error-detection methods is to detect whether the data is error free or not. If not, then ascertain what type of error exists. Two types of error need to be detected: single-bit errors and burst errors. In single-bit errors, only one bit of data is corrupted while in burst errors two or more bits in the data are corrupted. Error detection methods are based on the concept of redundancy. A shorter group of bits is appended to the end of each data unit which serves to detect errors. It contains no data information as such and hence can be discarded after the accuracy of the transmission has been checked. The most common error detection techniques are:

  1. Single Parity checking

    The simplest code is the single parity check code that takes k information bits and appends a single check bit to form a codeword, which will be transmitted over the channel. The parity check at the receiver ensures that the total number of 1s in the receiver codeword is even; that is, the codeword has even parity. The check bit in this case is called a parity bit. Here the receiver codeword is valid if it has even number of 1s, otherwise it is invalid and there is some error in the received codeword. This error-detection code is used in ASCII where characters are represented by seven bit and the eight bit consists of a parity bit

    If a codeword undergoes a single error during transmission, then the corresponding binary block at the output of the channel will contain an odd number of 1s and the error will be detected. More generally, if the codeword undergoes an odd number of errors, the corresponding output block will also contain an odd number of 1s. Therefore, the single parity bit allows us to detect all error patterns that introduce an odd number of errors. On the other hand, the single parity bit will fail to detect any error patterns that introduce an even number of errors, since the resulting codeword will have even parity which is valid codeword.

    At the transmitter a checksum is calculated from the information bits and transmitted along with the information. At the receiver, the checksum is recalculated, based on the received information. The received and recalculated checksums are compared and the error alarm is set if they disagree.

    The simple example can be used to present two fundamental observations about error detection. The first observation is that error detection requires redundancy in that the amount of information that is transmitted is over and above the required minimum. For a single parity check code of length k+1, k bits are information bits and one bit is the parity bit.

  2. Cyclic Redundancy Code (CRC)

    One of the most common and most powerful, error-detecting code is the CRC which can be described as follows. Given a k bit block of bits or message, the transmitter generates an n bit sequence known as a Frame Check Sequence (FCS), so that the resulting frame, consisting of k+n bits, is exactly divisible by some predetermined number called CRC polynomial. The receiver then divides the incoming frame of k+n bits by the same CRC polynomial number and if there is no remainder, assumes there was no error. The CRC polynomial number by which the information frame bits are divided are selected such that distance between two valid codeword is high and with proper selection of CRC polynomial it is possible to detect errors with very high probability i.e. more than 99.9% of the errors can be detected. Even it is possible to find out which bits are in error when only few bits are corrupted in the information bit stream. So with CRC it is also possible to correct the error though it is not possible for all possible errors.

Flow Control

One major problem that occurs in data link layer is of handling the situation when frames are sent at a rate faster than the receiving rate of the receiver. This situation occurs when the sender is running on a fast computer and receiver is on a slow machine. The sender keeps pumping the frames at a higher rate until the receiver is completely flooded. Suppose the transmission is error-free, but still at some point in time the receiver will simply not be able to handle the frames as they arrive and will start to lose them. Some measures have to be taken to prevent such a situation.

The solution to this is to introduce a flow control mechanism. Flow control mechanisms are employed to ensure that the data link layer at the sending end does not transmit more frames than what the data link layer at receiving end is capable of handling. In this situation, the receiver is provided with a control to regulate the flow of the incoming frames in the form of acknowledgment (ACK). After receiving the frame, the receiver sends some acknowledgment so as to make the sender aware whether the receiver received the frame or not. The acknowledgment solves the dual purpose - of clearing the sending end to transmit the next data frame and to acknowledge receipt of all previous frames.

Sliding Window Protocol

In contrast to stop-and-wait, which can have only one frame to transmit at a time? Sliding window can have more than one frame (the exact number depending on the size of the window) at a time, i.e. sender can send a certain number of frames without waiting for the acknowledgment.

This overcomes the inefficient use of bandwidth (as one frame takes the whole bandwidth) in stop-and-wait. Sliding window refers to imaginary slots (each slot capable of holding one frame) at both the sender and receiver end.
At the sender's end initially all these slots contain data frames and at the receiver's end, available memory spaces are used to receive these frames. The window is called sliding because it decreases from the left when sending window sends a frame and increases to the right when sender receives acknowledgment.

For the receiving end, window decreases from left when a frame is received and moves to the right when an ACK is sent. The window has a size n-1 where frames are numbered modulo-n, i.e. from 0 to n-1 for identification purpose. The size of window is n-1 and not n so that there is no ambiguity in knowing which frames have been acknowledged.

Error Control Mechanisms

Error control means methods of errors detection and transmission. Error control methods, when incorporated with flow-control protocols are called Automatic Repeat Request (ARQ), i.e. whenever the receiver detects an error in data, it sends back a negative acknowledgment (NAK) and the specified frame is retransmitted. ARQ also retransmits in case of lost frames, lost acknowledgment or lost NAK.

ARQ is implemented in the following three variations:

  1. Stop-and-Wait ARQ

    A few modification or capabilities are added to the basic stop-and-wait flow control to implement it as an ARQ. These are keeping a copy of the last frame transmitted at the sender end and giving sequence numbers 0 and 1 alternatively to each frame to help in identification of which frame is received correctly. The acknowledgment frame holds the number of the frame the received next accepts to receive thus, sending an implicit message to the sender that the last frame has been received correctly. A negative acknowledgment contains no seque3nce number; the sender just retransmits the last frame sent. This number also helps in receiver identifying the duplicate transmissions in case of lost acknowledgments.
  2. Go-back-n ARQ

    The following additions are made to the basic sliding-window protocol to accommodate sliding-window ARQ. The sending end keeps the copies of all the frames it has sent but not received a positive acknowledgment as yet. In sliding-window, even the NAK is numbered to identify which frame(s) is to be resent. ACK frames carry the number of the next frame the receiver expects while NAK carries the number of the damaged frame.
  3. Selective-Reject ARQ

    In this mechanism, if a damaged frame is received then unlike Go-back-n, only that frame is retransmitted. This is requires a more complex logic for implementation as the receiver will receive frames out of sequence and must have the capability to arrange frames in order. Thus, if a sender receivers a NAK, it must resend the frame out of sequence of frames. The sender thus must contain a searching mechanism.

Note: Continue in Next Part.