The Data Link Layer

Contents:

Introduction

In this section we will study the design of layer 2, the data link layer (also known as the physical link control layer).

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:

A data link protocol thus has to be designed to ensure an error-free transmission and also to achieve an efficiency of the data transfer as high as possible.

Simplified Model


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.

Functions and requirements of the Data Link Protocols

The basic function of the layer is to transmit frames over a physical communication link. Transmission may be half duplex or full duplex. To ensure that frames are delivered free of errors to the destination station (IMP) a number of requirements are placed on a data link protocol. The protocol (control mechanism) should be capable of performing:
  1. The identification of a frame (i.e. recognise the first and last bits of a frame).
  2. The transmission of frames of any length up to a given maximum. Any bit pattern is permitted in a frame.
  3. The detection of transmission errors.
  4. The retransmission of frames which were damaged by errors.
  5. The assurance that no frames were lost.
  6. In a multidrop configuration
    1. Some mechanism must be used for preventing conflicts caused by simultaneous transmission by many stations.
  7. The detection of failure or abnormal situations for control and monitoring purposes.
It should be noted that as far as layer 2 is concerned a host message is pure data, every single bit of which is to be delivered to the other host. The frame header pertains to layer 2 and is never given to the host.

We will first look at three elementary data link protocols of increasing complexity.

Elementary Data Link Protocols

An unrestricted simplex protocol

In order to appreciate the step by step development of efficient and complex protocols such as SDLC, HDLC etc., we will begin with a simple but unrealistic protocol. In this protocol: The protocol consists of two procedures, a sender and receiver as depicted below:
/* protocol 1 */

Sender()
{
        forever
        {
                from_host(buffer);
                S.info = buffer;
                sendf(S);
        }
}

Receiver()
{
        forever
        {
                wait(event);
                getf(R);
                to_host(R.info);
        }
}

A simplex stop-and-wait protocol

In this protocol we assume that These assumptions imply that the transmitter cannot send frames at a rate faster than the receiver can process them.

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);
        }
}

A simplex protocol for a noisy channel

In this protocol the unreal "error free" assumption in protocol 2 is dropped. Frames may be either damaged or lost completely. We assume that transmission errors in the frame are detected by the hardware checksum.

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.

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();
        }
}

Protocol 6

This protocol employs the selective reject technique. The protocol does not discard good frames because an earlier frame was damaged or lost provided that these good frames fall within the receiving window.

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:

High-level Data Link Control Procedures: HDLC, SDLC

Introduction

In this subsection we describe the International Standards Organisation data link protocol HDLC (High-level Data Link Control). CCITT Recommendation X.25 level 2 is one of the permissible options of HDLC. All these bit-oriented protocols grew out from the original IBM SDLC (Synchronous Data Link Control). All these protocols are based on the same protocols. They differ only in minor ways (see the appropriate protocol definition).

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:

Primary and secondary stations

A data link involves two or more participating stations. For control purposes one station on the link is designated a primary station, the others are secondary stations. The primary station is responsible for the organisation of data flow and for the link level error recovery procedures.

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.

Frame structure

In HDLC the input data string to be transmitted over the link is broken up into data frames which are then transmitted sequentially. The input data string could be command, response or information.

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).

The header

byte 1 - Flag (01111110):
A frame is identified by this beginning flag F and contains only non-F bit patterns. HDLC uses bit-stuffing to achieve data transparency. Whenever the transmitting hardware encounters five consecutive ones in the data, it automatically stuffs a zero bit into the outgoing bit stream. When the receiver sees five consecutive incoming one bits followed by a zero bit, it automatically deletes the zero bit. If the user data contained the flag pattern 01111110, it would be transmitted as 011111010 but stored in the receiver's memory as 01111110. Thus the pattern F can never occur by chance.
byte 2 - Address:
In command frames, the address identifies the station(s) for which the command is intended. In response frames, the address identifies the station from which the response originated. However, the address could also be a broadcast address so that a single frame is received by all stations on the link, or it could be the address of a group of stations.
byte 3 - Control:
The control field contains information for controlling the link, which we will examine later.

The trailer

bytes 1 and 2 - Frame Check Sequence:
The FCS field contains a 16-bit Cyclic Redundancy Check (CRC) error detecting code.
byte 3 - Flag:
This flag indicates the end of the frame. When this flag is detected the receiver examines the preceding two bytes and executes its error detection algorithm.

 

 
 
 

A flag may be followed by a frame, by another flag, or by an idle condition.

Data link channel states

Active channel state:
A channel is in an ACTIVE state when the primary or a secondary is actively transmitting a frame, a single abort sequence or interframe time fill. In this state the right to continue transmission is reserved.
Abort:
A station can abort a frame by transmitting at least seven contiguous ones. The receiving station will ignore the frame.
Interframe time fill:
In this state continuous flag bytes are sent between frames.
Idle channel state:
A channel is defined to be in an IDLE state when the transmission of 15 or more contiguous one bits is detected. In this state a primary must repoll a secondary before transmitting an I-frame to it.

Types of frames

There are three kinds of frames:
I-frame:
Information frame. This type of frame carries user's data.
S-frame:
Supervisory frame: This is used for supervisory control functions such as acknowledgements, requesting transmission and requesting a temporary suspension of transmission.
U-frame:
Unnumbered frame or Unsequenced frame. This is used to provide additional link control functions.

 
Before discussing in detail the functional aspects of these frames we will look at the modes of operation.

Modes of operation

For a secondary station two operational modes are defined: Normal response mode and Asynchronous response mode.
Normal response mode
In this mode a secondary station can transmit only in response to a command frame from the primary station. The response transmission may consist of one or more frames, the last of which must be explicitly indicated (using the Poll/Final bit). The secondary then cannot transmit again until it receives another command to do so.
Asynchronous response mode
In this mode the secondary station may initiate transmission of a frame or group of frames without receiving explicit permission from the primary. The frames may contain data or control information. The secondary station is responsible for time-out and retransmission if necessary.

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).

Asynchronous balanced mode (or simply Balanced mode)
In this mode the stations have identical protocols. They both can initiate transmission at any time. They can send both commands and responses.

Commands and responses

In this section we will describe the various information, supervisory and unnumbered frames. These types of frame are distinguished by their 8-bit control fields. Within each type, the frames are differentiated by the ways the bits in the C-field are configured. We will look closely at the C-field configurations, their associated functions and frames. When one of the frames is received by a secondary station, it is a command; when it is received by a primary station, it is a response.
I-frames


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)).

S-frames


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:

Receive Ready (RR)
An RR frame confirms receipt of frames numbered up to N(R)-1 and indicates that it is ready to receive frame number N(R). An RR frame with the poll bit set to 1 may be used by a primary station to poll a secondary station.
Reject (REJ)
An REJ frame is used by the primary or secondary station to request retransmission of information frame number N(R) and those that follow it. It implies that I-frames numbered N(R)-1 and below have been correctly received.

Only one reject condition may be established at any given time for a given direction of
 transmission over the link. The REJ condition is cleared by receipt of an I-frame with an
 N(S) equal to the N(R) of the REJ command/response frame.
 
Receive Not Ready (RNR)
An RNR frame indicates a temporary busy condition. The station which sends the RNR frame acknowledges I frames up to N(R)-1, expects I-frame number N(R), and indicates that it cannot accept any more I-frames. This busy condition is cleared upon the receipt of any other S-frame and of certain types of U-frame.
Selective Reject (SREJ)
An SREJ frame is used by the primary or secondary to request retransmission of the single I-frame numbered N(R). All frames up to N(R)-1 have been received correctly but N(R) has not. Once SREJ has been transmitted, the only I-frames accepted are the frame N(R) and those that follow it.
U-frames
The U-frames are identified by the first two bits sent of the control field. These bits are 11. The P/F bit is used as before. The other five "modifier" bits are available to encode up to 32 types of U-frame. However, not all 32 combinations are used yet. A U-frame has no sequence numbers. U-frames are used to provide additional link control functions such as The SNRM command allows a station that has just come back on line to announce its presence. The secondary station confirms acceptance of SNRM by transmitting a single UA response frame with the F bit set to one. The secondary station forces all the sequence numbers to zero. The SNRM contains no information field. The SARM and SABM commands function similarly.

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:

  1. the command is not implemented at the receiving station;
  2. the I-field is too long to fit into the receiving station's buffers; or
  3. The N(R) received is incongruous with the N(S) that was sent to it.
The Command Reject frame has an information field that contains details of why the command was rejected.

Information Exchange

In this section we will describe how information exchange between stations takes place using HDLC protocols. We will also describe methods employed for error recovery in some typical abnormal error conditions (not all possible situations).
Set-up
If a secondary station is off-line, the primary station must first send a command (e.g. SNRM) to the secondary station to set it up in some operational mode (e.g. NRM). The secondary station confirms the acceptance of the command by setting its N(R) and N(S) to zero and returns an unnumbered acknowledge (UA) frame to the primary. Both stations are then ready for information exchange.
Polling
Having agreed upon the operational mode, both stations can now exchange information. However, if the mode is normal response mode then
Normal Response
When a station receives enough data to build up a frame together with the address of the receiving station it will first compute the Frame Check Sequence (FCS). It will then start transmission by generating a flag, serialise the address bits, the control bits and data bits, followed by the FCS and the final flag.

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.

Error control
Error control is achieved at this level by the following procedures:
  1. FCS: Data, address and control bits in the frame are CRC coded so that transmission errors can be detected effectively.
  2. N(S) and N(R) are also used for error control. If the received frame whose send sequence number N(S) does not match the expected frame number N(R) the receiver knows that an error has occurred, i.e. some frame is missing or the received frame is a duplicate.
  3. The transmitter can time out and retransmit an unacknowledged frame or the receiver can request the retransmission of a frame or group of frames.
  4. The Poll and Final bits could also be used for error control purposes.
Flow control
Flow control is achieved in various ways:
  1. HDLC is a pipelining protocol. The transmitter is allowed to transmit a number of frames up to Nmax before an ACK is received. This is different from the stop-and-wait procedure in which every frame must be acknowledged before the next frame is allowed to be transmitted. The pipelining protocol thus
  2. Go-back-N and selective reject requests by the receiver also improve the flow.
  3. The supervisory frames Receive Ready and Receive Not Ready are used to regulate the flow.