The Data Link Layer
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.
Natural phenomena such as noises and interference are introduced into the
link causing errors in detecting the data.
There is a propagation delay in the link.
There is a finite data processing time required by the transmitting and
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:
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.
The identification of a frame (i.e. recognise the first and last bits of
The transmission of frames of any length up to a given maximum. Any bit
pattern is permitted in a frame.
The detection of transmission errors.
The retransmission of frames which were damaged by errors.
The assurance that no frames were lost.
In a multidrop configuration
mechanism must be used for preventing conflicts caused by simultaneous
transmission by many stations.
The detection of failure or abnormal situations for control and monitoring
We will first look at three elementary data link protocols of increasing
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
Data are transmitted in one direction only
The transmitting (Tx) and receiving (Rx) hosts are always ready
Processing time can be ignored
Infinite buffer space is available
No errors occur; i.e. no damaged frames and no lost frames (perfect channel)
/* protocol 1 */
S.info = buffer;
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.
Data are transmitted in one direction only
No errors occur (perfect channel)
The receiver can only process the received information at a finite rate
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 */
S.info = buffer;
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
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 */
NFTS = 0; /* NFTS = Next Frame To Send */
S.seq = NFTS;
S.info = buffer;
if(event == frame_arrival)
++NFTS; /* modulo 2 operation */
FE = 0; /* FE = Frame Expected */
if(event == frame_arrival)
if(R.seq == FE)
++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
Sliding Window Protocols
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
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.
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
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
-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
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 */
NFTS = 0;
FE = 0;
S.info = buffer;
S.seq = NFTS;
S.ack = 1-FE;
if(event == frame_arrival)
if(R.seq == FE)
if(R.ack == NFTS)
S.info = buffer;
S.seq = NFTS;
S.ack = 1-FE;
In many situations the long round-trip time can have important implications
for the efficiency of the bandwidth utilisation.
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.
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.
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
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
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 */
S.info = buffer[frame_number];
S.seq = frame_number;
S.ack = (FE+MaxSeq) % (MaxSeq+1);
NFTS = 0;
Ack_expected = 0;
Frame_expected = 0;
nbuffered = 0;
if(R.seq == Frame_expected)
if( (Ack_expected <= R.ack && R.ack < NFTS)
||(NFTS < Ack_expected && Ack_expected <= R.ack)
||(R.ack < NFTS &&NFTS < Ack_expected))
/* just ignore the bad frame */
NFTS = Ack_expected;
i = 0;
if(nbuffered < MaxSeq)
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
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:
Protocol 6 employs an auxiliary timer to prevent delay in piggybacking.
If no reverse traffic has presented itself before the timer goes off, a
separate acknowledgement is sent.
Whenever the receiver has reason to suspect that an error has occured it
sends a negative acknowledgement (NAK) frame back to the sender. Such a
frame is a request for retransmission of the frame specified in the NAK.
High-level Data Link Control Procedures: HDLC, SDLC
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:
The definitions of primary and secondary station responsibilities.
The design of information grouping for control and checking.
The design of the format for transfer of information and control data.
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
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
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.
bytes 1 and 2 - Frame Check Sequence:
The FCS field contains a 16-bit Cyclic Redundancy Check (CRC) error detecting
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
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.
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:
Before discussing in detail the functional aspects of these frames we will
look at the modes of operation.
Information frame. This type of frame carries user's data.
Supervisory frame: This is used for supervisory control functions such
as acknowledgements, requesting transmission and requesting a temporary
suspension of transmission.
Unnumbered frame or Unsequenced frame. This is used to provide additional
link control functions.
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
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.
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:
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.
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.
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.
commands which can initialise a station, change transmission modes, and
disconnect a station;
provide a mechanism for rejecting invalid commands or dealing with some
special error conditions.
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 Command Reject frame has an information field that contains details
of why the command was rejected.
the command is not implemented at the receiving station;
the I-field is too long to fit into the receiving station's buffers; or
The N(R) received is incongruous with the N(S) that was sent to it.
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
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
Having agreed upon the operational mode, both stations can now exchange
information. However, if the mode is normal response mode then
the primary can send data or command frames to the secondary station at
any time, but
the secondary station can only transmit if it is permitted to do so, i.e.
if it receives a frame with the poll bit set to one.
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 is achieved at this level by the following procedures:
FCS: Data, address and control bits in the frame are CRC coded so that
transmission errors can be detected effectively.
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.
The transmitter can time out and retransmit an unacknowledged frame or
the receiver can request the retransmission of a frame or group of frames.
The Poll and Final bits could also be used for error control purposes.
Flow control is achieved in various ways:
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
Go-back-N and selective reject requests by the receiver also improve the
The supervisory frames Receive Ready and Receive Not Ready are used to
regulate the flow.
speeds up the flow of information; i.e. it is more efficient; and
prevents the receiver from being flooded.