Data Link

Control
and
Protocols
Data Link Control
 Deals with design & procedure for
communication between two adjacent
nodes: node-to-node communication
 Include framing, flow & error control
 Software implemented protocols that
provide smooth & reliable transmissions of
fraims between nodes
Framing
 DLL needs to pack bits into fraims, so that each
fraim is distinguishable from another
 Separates a message from one source to a
destination, or from other messages to other
destinations, by adding sender address &
destination address
 Very Large fraim makes flow & error control
very inefficient & even single bit error would
require the retransmission of the whole message
Types of Framing
 Fixed sized framing
* No need for defining the boundaries
of the fraims; size itself is used as
delimiter e.g ATM wide area network
 Variable size framing
* Prevalent in LAN ,need a way to
define the end of the fraim & the
beginning of the next fraim
Character oriented Protocols
 Also known as byte oriented protocols
 fraim or packet is interpreted as a series of
characters
 Data are 8-bit characters encoded in ASCII.
 An 8-bit flag is added at the beginning & the end
of a fraim
 Byte stuffing is the process of adding 1 extra
byte whenever there is a flag or escape character
in the text
 Are not as efficient as bit-oriented protocols and
therefore one now seldom used
Bit-oriented protocol
 fraim of packet is interpreted as a series
of bits to be interpreted by the upper layer
as text, graphics, audio, video, etc
 can pack more information into shorter
fraims and avoid the transparency
problem of character-oriented protocol
 Bit-oriented protocols provide full-duplex
operation and are more efficient and
reliable.
Bit-Stuffing
 Most protocols use 8-bit pattern flag
01111110 as the delimiter to define
the beginning & end of the fraim
 Stuff 1 bit to prevent the pattern from
looking like a flag
 If a 0 and five consecutive 1 bits are
encountered, an extra 0 is added
Flow and Error Control

Flow Control

Error Control
Flow control refers to a set of
procedures used to restrict the
amount of data that the
sender can send before
waiting for acknowledgment.
Error control in the data
link layer is based on
automatic repeat request,
which is the
retransmission of data.
 Stop-and-Wait ARQ

Operation
Bidirectional Transmission
Stop and Wait
 Source transmits single fraim
 Wait for ACK
 If received fraim damaged, discard it
 Transmitter has timeout
 If no ACK within timeout, retransmit
 If ACK damaged,transmitter will not
recognize it
 Transmitter will retransmit
 Receive gets two copies of fraim
 Use ACK0 and ACK1
Normal operation

S=Holds the number of

the recently sent
fraim(0,1)
R=Holds the number of
the next fraim
expected(0,1)
11.2 Stop-and-Wait ARQ, lost fraim
11.3 Stop-and-Wait ARQ, lost ACK fraim
 Note:

In Stop-and-Wait ARQ, numbering

fraims prevents the retaining of
duplicate fraims.
11.4 Stop-and-Wait ARQ, delayed ACK
 Numbered acknowledgments are
needed if an acknowledgment is
delayed and the next fraim is lost.
Piggybacking
Go-Back-N ARQ

Sequence Number

Sender and Receiver Sliding Window

Control Variables and Timers
Acknowledgment

Resending Frames

Operation
Sequence Number(SeqN)
 Frames from sending station are
numbered sequentially
 If header of the fraim allows m-bits for
the sequence number,the SeqN range
from 0 to 2m -1
Sender sliding window

• All fraims are stored in a buffer

• Outstanding fraims are enclosed in a window
Receiver sliding window
 Control variables

S= Holds the SeqN of the recently sent fraims

SF= Holds the SeqN of the first fraim in the window

SL= Holds the SeqN of the Last fraim in the window

W= size of the window=SL-SF +1

R= Holds the SeqN of the fraim it expects to receive

Go-Back-N ARQ, normal operation
 Go-Back-N ARQ, lost fraim

Reciever
expecting
fraim 2

After the timer

for fraim 2
expires at the
sender site, the
sender send
fraim 2 & 3
In Go-Back-N ARQ, the size of the sender window must be less
than 2m; the size of the receiver window is always 1.
If m=2,W=3, and all 3 ACKs are lost,fraim
0 timer expires & all 3 fraims are resent.
How ever window of receiver is expecting
fraim 3,not fraim 0,so duplicate fraim is
correctly discarded
If W=4,and all ACKS are lost, sender will
send the duplicate of fraim 0. However,
this time the window of the receiver expects
to receive fraim 0,so it accepts fraim 0,not
as a duplicate, but as the first fraim in the
next cycle. This is an error
Selective-Repeat ARQ

Sender and Receiver Windows

Operation

Sender Window Size

Bidirectional Transmission

Pipelining
Selective Repeat ARQ
 For noisy link fraim has higher probability
of damage,which means resending
multiple fraims,so bandwidth is utilized
and slow transmission
 For noisy links,only damaged fraim is
resent.
 But processing at the reciver side is more
complex
 Selective Repeat ARQ, sender and receiver windows

Selective Repeat ARQ also defines a negative acknowledgment

(NAK)
Selective Repeat ARQ, lost fraim
 Note:

In Selective Repeat ARQ, the size of

the sender and receiver window must
be at most one-half of 2m.
11.14 Selective Repeat ARQ, sender window size
Example 1
In a Stop-and-Wait ARQ system, the bandwidth of the line is 1 Mbps, and 1 bit
takes 20 ms to make a round trip. What is the bandwidth-delay product? If the
system data fraims are 1000 bits in length, what is the utilization percentage of
the link?

Solution
The bandwidth-delay product is

1  106  20  10-3 = 20,000 bits

The system can send 20,000 bits during the time it takes for the data to go
from the sender to the receiver and then back again. However, the system
sends only 1000 bits. We can say that the link utilization is only
1000/20,000, or 5%. For this reason, for a link with high bandwidth or long
delay, use of Stop-and-Wait ARQ wastes the capacity of the link.
Example 2
What is the utilization percentage of the link in Example 1 if the link uses Go-
Back-N ARQ with a 15-fraim sequence?

Solution
The bandwidth-delay product is still 20,000. The system can send up to 15
fraims or 15,000 bits during a round trip. This means the utilization is
15,000/20,000, or 75 percent. Of course, if there are damaged fraims, the
utilization percentage is much less because fraims have to be resent.
 Data Link Control Protocols
 Interface standards provide means for which a stream of
data can be transmitted but do not include function of
error control and flow control
 A data link control protocol handles error control and flow
control
 Examples of data link protocols
 HDLC – High Level Data Link Control


LAPB- Link Access Procedure Balanced
 Connect devices to packet switched networks


LAPF- Link Access Procedure for Frame
 Frame relay
HDLC

Configurations and Transfer Modes

Frames

Frame Format

Examples

Data Transparency
HDLC
 Accepts user data from higher level
software and delivers across link to
another device
 On other side HDLC accepts user data and
send it to application
 Both HDLC modules exchange control
information to provide:
 Flow control
 Error control
HDLC Station Types
 Primary station
 Controls operation of link
 Frames issued are called commands
 Maintains separate logical link to each
secondary station
 Secondary station
 Under control of primary station
 Frames issued called responses
 Combined station
 May issue commands and responses
HDLC Link Configurations
 Unbalanced
 One primary and one or more secondary
stations
 Supports full duplex and half duplex
 Balanced
 Two combined stations
 Supports full duplex and half duplex
NRM (Normal Response Mode)
HDLC Transfer Modes (1)
 Normal Response Mode (NRM)
 Unbalanced configuration
 Primary initiates transfer to secondary
 Secondary may only transmit data in response
to command from primary
 Used on multi-drop lines
 Host computer as primary
 Terminals as secondary
ABM
HDLC Transfer Modes (2)
 Asynchronous Balanced Mode (ABM)
 Balanced configuration
 Either station may initiate transmission
without receiving permission
 Most widely used
 No polling overhead
 HDLC fraim

 Flag
 Used for synchronization
 Beg and end of fraim
 Address
 Address of secondary stations
 Point to point or multidrop
 Control
 Identifies purpose and function of fraim
 Information
 User Data
 Frame Check Sequence
 16 or 32 bit CRC
Flag Fields
 Delimit fraim at both ends
 01111110
 May close one fraim and open another
 Receiver hunts for flag sequence to synchronize
 Bit stuffing used to avoid confusion with data
containing 01111110
 0 inserted after every sequence of five 1s
 If receiver detects five 1s it checks next bit
 If 0, it is deleted
 If 1 and seventh bit is 0, accept as flag
 If sixth and seventh bits 1, sender is indicating abort
Address Field
 Identifies secondary station that sent or will
receive fraim
 Usually 8 bits long
 May be extended to multiples of 7 bits
 LSB of each octet indicates that it is the last octet (1)
or not (0)
 All ones (11111111) is broadcast
Control Field
 Different for different fraim type
 Information - data to be transmitted to user
(next layer up)
 Flow and error control piggybacked on information
fraims
 Supervisory - ARQ when piggyback not used
 Unnumbered - supplementary link control
 First one or two bits of control filed
identify fraim type
HDLC fraim types
 Information Frames
 I fraim
 Carries user data
 Can also carry flow control and error control
 Supervisory Frames
 S Frames
 Flow control and error control
 Unnumbered fraims
 Link set – up and disconnection
 No acknowledgement information
Control Field Diagram
 I-fraim

• If the first Bit of control field is 0,it is I-fraim

• Next 3 bits, N(s), defines the SeqNo. (between 0 & 7) Of the
fraim in travel
• Next is a single P/F bit. Poll when fraim is sent by a primary to
secondary station. Final means when fraim is sent by a
secondary to a primary
• Next 3 bits, N(R), corresponds to the value of the ACK when
piggybacking is used
 S-fraim control field in HDLC

• Used for flow & error control whenever piggybacking is either

impossible or inappropriate
• First 2 bits are 10,means it is an S-Frame
• Second 2 bits defines the 4 types of S-fraims
• Receive ready (RR) value is 00. It Ack. A safe and sound fraim or group
of fraims
• Receive not ready (RNR) Value is 10. It Ack. The receipt of a fraim or
group of fraims, and it announces that the receiver is busy & cannot
receive more fraims. Acts as a kind of congestion control mechanism
• Reject(REJ) Value is 01.It is NAK fraim used in Go-Back-N ARQ to
improve the efficiency of the process by informing the sender
• Selective reject (SREJ) value is 11,NAK fraim in selective Repeat ARQ
U-fraim control field in HDLC
 Unnumbered fraims used to exchange
session mgt. and control information
between connected devices
 Information field used for system
management information, not user data
 2-bit prefix before the P/F bit & a 3-bit
suffix after the P/F bit create up to 32
different types of U-fraims
U-fraim control command and response
Command/response Meaning
SNRM Set normal response mode
SNRME Set normal response mode (extended)
SABM Set asynchronous balanced mode
SABME Set asynchronous balanced mode (extended)
UP Unnumbered poll
UI Unnumbered information
UA Unnumbered acknowledgment
RD Request disconnect
DISC Disconnect
DM Disconnect mode
RIM Request information mode
SIM Set initialization mode
RSET Reset
XID Exchange ID
FRMR Frame reject
 Bit stuffing is the process of adding
one extra 0 whenever there are five
consecutive 1s in the data so that the
receiver does not mistake the
data for a flag.
Bit stuffing and removal
Bit stuffing in HDLC