HIGH LEVEL DATA LINK CONTROL

HIGH LEVEL DATA LINK CONTROL

The most important data link control protocol is HDLC (IS0 33009, IS0 4335). Not

only is HDLC widely used, but it is the basis for many other important data link

control protocols, which use the same or similar formats and the same mechanisms

as employed in HDLC. Accordingly, in this section we provide a detailed discussion

of HDLC. Section 6.5 surveys related protocols.

Basic Characteristics

To satisfy a variety of applications, HDLC defines three types of stations, two link

configurations, and three data-transfer modes of operation. The three station types

are

Primary station. Has the responsibility for controlling the operation of the

link. Frames issued by the primary are called commands.

Secondary station. Operates under the control of the primary station. Frames

issued by a secondary are called responses. The primary maintains a separate

logical link with each secondary station on the line.

Combined station. Combines the features of primary and secondary. A combined

station may issue both commands and responses.

The two link configurations are

Unbalanced configuration. Consists of one primary and one or more secondary

stations and supports both full-duplex and half-duplex transmission.

Balanced configuration. Consists of two combined stations and supports both

full-duplex and half-duplex transmission.

The three data transfer modes are

Normal response mode (NRM). Used with an unbalanced configuration. The

primary may initiate data transfer to a secondary, but a secondary may only

transmit data in response to a command from the primary.

Asynchronous balanced mode (ABM). Used with a balanced configuration.

Either combined station may initiate transmission without receiving permission

from the other combined station.

Asynchronous response mode (ARM). Used with an unbalanced configuration.

The secondary may initiate transmission without explicit permission of

the primary. The primary still retains responsibility for the line, including initialization,

error recovery, and logical disconnection.

NRM is used on mulitdrop lines, in which a number of terminals are connected

to a host computer. The computer polls each terminal for input. NRM is also

sometimes used on point-to-point links, particularly if the link connects a terminal

or other peripheral to a computer. ABM is the most widely used of the three modes;

it makes more efficient use of a full-duplex point-to-point link as there is no polling

overhead. ARM is rarely used; it is applicable to some special situations in which a

secondary may need to initiate transmission.

Frame Structure

HDLC uses synchronous transmission. All transmissions are in the form of frames,

and a single frame format suffices for all types of data and control exchanges.

Figure 6.10a depicts the structure of the HDLC frame. The flag, address, and

control fields that precede the information field are known as a header. The FCS

and flag fields following the data field are referred to as a trailer.

Flag Fields

Flag fields delimit the frame at both ends with the unique pattern 01111110. A single

flag may be used as the closing flag for one frame and the opening flag for the

next. On both sides of the user-network interface, receivers are continuously hunting

for the flag sequence to synchronize on the start of a frame. While receiving a

frame, a station continues to hunt for that sequence to determine the end of the

frame. However, it is possible that the pattern 01111110 will appear somewhere

inside the frame, thus destroying frame-level synchronization. To avoid this, a procedure

known as bit stuffing is used. Between the transmission of the starting and

ending flags, the transmitter will always insert an extra 0 bit after each occurrence

of five Is in the frame. After detecting a starting flag, the receiver monitors the bit

stream. When a pattern of five 1s appears, the sixth bit is examined. If this bit is 0,

it is deleted. If the sixth bit is a 1 and the seventh bit is a 0, the combination is

accepted as a flag. If the sixth and seventh bits are both 1, the sender is indicating

an abort condition.

With the use of bit stuffing, arbitrary bit patterns can be inserted into the data

field of the frame. This property is known as data transparency.

Figure 6.11a shows an example of bit stuffing. Note that in the first two cases,

the extra 0 is not strictly necessary for avoiding a flag pattern, but is necessary for

the operation of the algorithm. The pitfalls of bit stuffing are also illustrated in this

figure. When a flag is used as both an ending and a starting flag, a 1-bit error merges

two frames into one; conversely, a 1-bit error inside the frame could split it in two.

Address Field

The address field identifies the secondary station that transmitted or is to receive

the frame. This field is not needed for point-to-point links, but is always included

for the sake of uniformity. The address field is usually eight bits long but, by prior

agreement, an extended format may be used in which the actual address length is a

multiple of seven bits (Figure 6.10b). The least significant bit of each octet is 1 or 0,

depending on whether it is or is not the last octet of the address field. The remaining

seven bits of each octet form part of the address. The single-octet address of

11111111 is interpreted as the all-stations address in both basic and extended

formats. It is used to allow the primary to broadcast a frame for reception by all

secondaries.

Control Field

HDLC defines three types of frames, each with a different control field format.

Information frames (I-frames) carry the data to be transmitted for the user (the

logic above HDLC that is using HDLC). Additionally, flow- and error-control data,

using the ARQ mechanism, are piggybacked on an information frame. Supervisory

frames (S-frames) provide the ARQ mechanism when piggybacking is not used.

Unnumbered frames (U-frames) provide supplemental link control functions. The

first one or two bits of the control field serves to identify the frame type. The

remaining bit positions are organized into subfields as indicated in Figure 6.10~an d

d. Their use is explained below in the discussion of HDLC operation.

Note that the basic control field for S- and I-frames uses 3-bit sequence numbers.

With the appropriate set-mode command, an extended control field can be

used for S- and I-frames that employs 7-bit sequence numbers. U-frames always

contain an &bit control field.

Information Field

The information field is present only in I-frames and some U-frames. The field can

contain any sequence of bits but must consist of an integral number of octets. The

length of the information field is variable up to some system-defined maximum.

Frame Check Sequence Field

The frame check sequence (FCS) is an error-detecting code calculated from the

remaining bits of the frame, exclusive of flags. The normal code is the 16-bit CRCCCITT

defined in Section 6.2. An optional 32-bit FCS, using CRC-32, may be

employed if the frame length or the line reliability dictates this choice.

Operation

HDLC operation consists of the exchange of I-frames, S-frames, and U-frames

between two stations. The various commands and responses defined for these frame

types are listed in Table 6.1. In describing HDLC operation, we will discuss these

three types of frames.

The operation of HDLC involves three phases. First, one side or another initializes

the data link so that frames may be exchanged in an orderly fashion. During

this phase, the options that are to be used are agreed upon. After initialization, the

two sides exchange user data and the control information to exercise flow and error

control. Finally, one of the two sides signals the termination of the operation.

Initialization

Initialization may be requested by either side by issuing one of the six set-mode

commands. This command serves three purposes:

1. It signals the other side that initialization is requested.

2. It specifies which of the three modes (NRM, ABM, ARM) is requested.

3. It specifies whether 3- or 7-bit sequence numbers are to be used.

If the other side accepts this request, then the HDLC module on that end

transmits an unnumbered acknowledged (UA) frame back to the initiating side. If

the request is rejected, then a disconnected mode (DM) frame is sent.

Data Transfer

When the initialization has been requested and accepted, then a logical connection

is established. Both sides may begin to send user data in I-frames, starting with

sequence number 0. The N(S) and N(R) fields of the I-frame are sequence numbers

that support flow control and error control. An HDLC module sending a sequence

of I-frames will number them sequentially, modulo 8 or 128, depending on whether

3- or 7-bit sequence numbers are used, and place the sequence number in N(S).

N(R) is the acknowledgment for I-frames received; it enables the HDLC module to

indicate which number I-frame it expects to receive next.

S-frames are also used for flow control and error control. The receive-ready

(RR) frame is used to acknowledge the last I-frame received by indicating the next

I-frame expected. The RR is used when there is no reverse-user data traffic (Iframes)

to carry an acknowledgment. Receive-not-ready (RNR) acknowledges an

I-frame, as with RR, but also asks the peer entity to suspend transmission of Iframes.

When the entity that issued RNR is again ready, it sends an RR. REJ initiates

the go-back-N ARQ. It indicates that the last I-frame received has been

rejected and that retransmission of all I-frames beginning with number N(R) is

required. Selective reject (SREJ) is used to request retransmission of just a single

frame.

Disconnect

Either HDLC module can initiate a disconnect, either on its own initiative if there

is some sort of fault, or at the request of its higher-layer user. HDLC issues a disconnect

by sending a disconnect (DISC) frame. The other side must accept the disconnect

by replying with a UA.

Examples of Operation

In order to better understand HDLC operation, several examples are presented in

Figure 6.12. In the example diagrams, each arrow includes a legend that specifies

the frame name, the setting of the PIF bit, and, where appropriate, the values of

N(R) and N(S). The setting of the P or F bit is 1 if the designation is present and 0

if absent.

Figure 6.12a shows the frames involved in link setup and disconnect. The

HDLC protocol entity for one side issues an SABM command to the other side and

starts a timer. The other side, upon receiving the SABM, returns a UA response

and sets local variables and counters to their initial values. The initiating entity

receives the UA response, sets its variables and counters, and stops the timer. The

logical connection is now active, and both sides may begin transmitting frames.

Should the timer expire without a response, the originator will repeat the SABM,

as illustrated. This would be repeated until a UA or DM is received or until, after a

given number of tries, the entity attempting initiation gives up and reports failure to

a management entity. In such a case, higher-layer intervention is necessary. The

same figure (Figure 6.12a) shows the disconnect procedure. One side issues a DISC

command, and the other responds with a UA response.

Figure 6.12b illustrates the full-duplex exchange of I-frames. When an entity

sends a number of I-frames in a row with no incoming data, then the receive

sequence number is simply repeated (e.g., I, 1, 1; I, 2, 1 in the A-to-B direction).

When an entity receives a number of I-frames in a row with no outgoing frames,

then the receive sequence number in the next outgoing frame must reflect the

cumulative activity (e.g., I, 1, 3 in the B-to-A direction). Note that, in addition to

I-frames, data exchange may involve supervisory frames.

Figure 6.12~sh ows an operation involving a busy condition. Such a condition

may arise because an HDLC entity is not able to process I-frames as fast as they are

arriving, or the intended user is not able to accept data as fast as they arrive in 1-

frames. In either case, the entity's receive buffer fills up and it must halt the incoming

flow of I-frames, using an RNR command. In this example, A issues an RNR,

which requires B to halt transmission of I-frames. The station receiving the RNR

will usually poll the busy station at some periodic interval by sending an RR with

the P-bit set; this requires the other side to respond with either an RR or an RNR.

When the busy condition has cleared, A returns an RR, and I-frame transmission

from B can resume.

An example of error recovery using the REJ command is shown in Figure

6.12d. In this example, A transmits I-frames numbered 3,4, and 5. Number 4 suffers

an error and is lost. When B receives I-frame number 5, it discards this frame

because it is out of order and sends an REJ with an N(R) of 4. This causes A to initiate

retransmission of all I-frames sent, beginning with frame 4. It may continue to

send additional frames after the retransmitted frames.

An example of error recovery using a timeout is shown in Figure 6.12e. In this

example, A transmits I-frame number 3 as the last in a sequence of I-frames. The

frame suffers an error. B detects the error and discards it. However, B cannot send

an REJ; this is because there is no way to know if this was an I-frame. If an error is

detected in a frame, all of the bits of that frame are suspect, and the receiver has no

way to act upon it. A, however, would have started a timer as the frame was transmitted.

This timer has a duration long enough to span the expected response time.

When the timer expires, A initiates recovery action; this is usually done by polling

the other side with an RR command with the P bit set, to determine the status of

the other side. Because the poll demands a response, the entity will receive a frame

containing an N(R) field and be able to proceed. In this case, the response indicates

that frame 3 was lost, which A retransmits.

These examples are not exhaustive. However, they should give the reader a

good feel for the behavior of HDLC.

6.5 OTHER DATA LINK CONTROL PROTOCOLS

In addition to HDLC, there are a number of other important data link control protocols.

Figure 6.13 illustrates the frame formats, and this section provides a brief

overview.

LAPB

LAPB (Link Access Procedure, Balanced) was issued by ITU-T as part of its X.25

packet-switching network-interface standard. It is a subset of HDLC that provides

only the asynchronous balanced mode (ABM); it is designed for the point-to-point

link between a user system and a packet-switching network node. Its frame format

is the same as that of HDLC.

LAPD

LAPD (Link Access Procedure, D-Channel) was issued by ITU-T as part of its set

of recommendations on ISDN (Integrated Services Digital Network). LAPD provides

data link control over the D channel, which is a logical channel at the user-

ISDN interface.

There are several key differences between LAPD and HDLC. Like LAPB,

LAPD is restricted to ABM. LAPD always uses 7-bit sequence numbers; 3-bit

sequence numbers are not allowed. The FCS for LAPD is always the 16-bit CRC.

Finally, the address field for LAPD is a 16-bit field that actually contains two subaddresses:

one is used to identify one of possibly multiple devices on the user side

of the interface, and the other is used to identify one of possibly multiple logical

users of LAPD on the user side of the interface.

Logical Link Control (LLC)

LLC is part of the IEEE 802 family of standards for controlling operation over a

local area network (LAN). LLC is lacking some features found in HDLC and also

has some features not found in HDLC.

The most obvious difference between LLC and HDLC is the difference in

frame format. Link control functions in the case of LLC are actually divided

between two layers: a medium access control (MAC) layer, and the LLC layer,

which operates on top of the MAC layer.

Figure 6 . 1 3~sh ows the structure of the combined MACILLC frame; the

shaded portion corresponds to the fields produced at the LLC layer, and the

unshaded portions are the header and trailer of the MAC frame. The MAC layer

includes source and destination addresses for devices attached to the LAN. Two

addresses are needed as there is no concept of primary and secondary in the LAN

environment; therefore, both the sender and receiver must be identified. Error

detection is done at the MAC level, using a 32-bit CRC. Finally, there are some con

trol functions peculiar to medium-access control that may be included in a MAC

control field.

At the LLC layer, there are four fields. The destination and source service

access points (DSAP and SSAP), identify the logical user of LLC at the source and

destination systems. The LLC control field has the same format as that of HDLC,

limited to 7-bit sequence numbers.

Operationally, LLC offers three forms of service. The connection-mode service

is the same as the ABM of HDLC. The other two services, unacknowledged

connectionless and acknowledged connectionless, are described in Part 11.

Frame Relay

Frame relay is a data link control facility designed to provide a streamlined capability

for use over high-speed packet-switched networks. It is used in place of X.25,

which consists of both a data link control protocol (LAPB) and a network-layer

protocol (called X.25 packet layer). Frame relay is examined in detail in Part 11.

The data link control protocol defined for frame relay is LAPF (Link Access

Procedure for Frame-Mode Bearer Services). There are actually two protocols: a

control protocol, which has similar features to HDLC, and a core protocol, which is

a subset of the control pyotocol.

There are several key differences between the LAPF control protocol and

HDLC. Like LAPB, LAPF control is restricted to ABM. LAPF control always uses

7-bit sequence numbers; 3-bit sequence numbers are not allowed. The FCS for

LAPF control is always the 16-bit CRC. Finally, the address field for LAPF control

is two, three, or four octets long, containing a 10-bit, 16-bit, or 23-bit DLCI (data

link connection identifier). The DLCI identifies a logical connection between a

source and destination system. In addition, the address field contains some control

bits that are useful for flow control purposes.

The LAPF core consists of the same flag, address, information, and FCS fields

as LAPF control. The difference is that there is no control field for LAPF core.

Thus, there is no means of doing flow and error control, which results in a more

streamlined operation.

Asynchronous Transfer Mode (ATM)

Like frame relay, ATM is designed to provide a streamlined data-transfer capability

across high-speed networks. Unlike frame relay, ATM is not based on HDLC.

Instead, ATM is based on a completely new frame format, known as a cell, that provides

minimum processing overhead.

The cell has a fixed length of 53 octets, or 424 bits.

PERFORMANCE ISSUE

Stop and wait Flow Control

Sliding-'Window Control

For sliding-window flow control, the efficiency of the line depends on both the window size,

N, and the value of a. For convenience, let us again normalize frame transmission time to a

value of 1; thus, the propagation time is a. Figure 6.15 illustrates the efficiency of a full-duplex

point-to-point line. Station A begins to emit a sequence of frames at time to. The leading edge

We have seen that sliding-window flow control is more efficient than stop-and-wait flow control.

We would expect that when error-control functions are added, this would still be truethat

is, that go-back-N and selective-reject ARQ are more efficient than stop-and-wait ARQ.

Let us develop some approximations to determine the degree of improvement to be

expected.

First, consider stop-and-wait ARQ. With no errors, the maximum utilization is 1/(1 +

2a) as shown in Equation (6.2). We want to account for the possibility that some frames are

repeated because of bit errors. To start, note that the utilization U can be defined as