Data Link Control and Protocols

Introduction

 Protocol – set of rules governing communication

specific to one or more layers of the OSI model
 Data link protocols define the rules devices use to
implement data link layer functions
 Contain rules for line discipline, flow control, and
error control

University of South Alabama 2

Computer and Information Sciences
Flow Control

 Coordinates amount of data sent before receiving

acknowledgement
 Purpose: prevent overwhelming receiver
 Buffer overflow

University of South Alabama 3

Computer and Information Sciences
Error Control

 Error detection and error correction

 Receiver informs sender of any frames lost or
damaged and coordinates retransmission of
those frames by the sender
 Usually handled via automatic repeat request (ARQ)

University of South Alabama 4

Computer and Information Sciences
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

5
Data Link Layer
 Receives services from physical layer and provides
services to network layer

6
Data Link Layer functions
 Node-to-node delivery
 Local responsibility
 Ensures reliable delivery
 Defines frames
 Physical addressing
 Error control
 Flow control
 Medium access control
 Line discipline
 It determines which device can send and when it
can send.
 It oversees the establishment of links and the right
of a particular device to transmit at a given time.

8
Enquiry / Acknowledgment
ENQ/ACK

9
ENQ/ACK
It is used in systems where there is no question
of the wrong receiver getting the transmission
 i.e. when there is a dedicated link between two
devices so that the only device capable of
receiving data is the intended one.

10
ENQ/ACK

11
 Poll / Select
 It works with topologies where one device is
designated as a primary station and the other
devices are secondary stations and all are using a
single transmission line.
 All data communication must be made through the
primary device
 If the primary wants to receive data, it
asks the secondary's if they have anything to send;
this function is called polling.
 If the primary wants to send data, it tells
the target secondary to get ready to receive; this
function is called selecting
12
Multipoint Discipline

13
 Addresses
 We need addressing for multipoint transmission.
 Each secondary device has an address that
differentiates it from the others.
 If the transmission comes from the primary
device, The address indicates the recipient of
the data.
 If the transmission comes from a secondary
device, the address indicates the originator of
the data.

14
 Poll
 It is used by the primary device to solicit
transmissions from the secondary devices.
 There are two possibilities for terminating the exchange
 The secondary sends all its data and sends (EOT) frame
 The primary “Time’s up”

15
 Select
 It is used whenever the primary device has
something to send.
 Any frame on the link is available to every device.
 When a device recognizes its own address, it
opens the frame and reads the data.

16
Flow control

17
Stop-and-Wait

 Advantage: simplicity; each frame is checked and

ACK’d before next frame is sent
 Numbering of frames prevents duplication
 Disadvantage: inefficiency; slow
 Frame and ACKs use entire bandwidth
 If distance is long between devices, time spent
waiting can be significant

University of South Alabama 18

Computer and Information Sciences
Stop and Wait

19
Flow and Error Control Mechanisms

 Stop-and-Wait ARQ
 Go-back-N ARQ
 Selective-Repeat ARQ

University of South Alabama 20

Computer and Information Sciences
11.2 Stop-and-Wait ARQ

 Sender keeps copy of last frame sent and waits

for ACK for that frame
 Next frame cannot be sent until ACK has been
received
 Frames are numbered alternately 0 and 1
 Damaged or lost frames are resent
 Repeats until EOT is sent

University of South Alabama 21

Computer and Information Sciences
Stop-and-Wait Normal Operation

University of South Alabama 22

Computer and Information Sciences
Lost or Damaged Frame

University of South Alabama 23

Computer and Information Sciences
Lost Acknowledgement

University of South Alabama 24

Computer and Information Sciences
Delayed Acknowledgement

University of South Alabama 25

Computer and Information Sciences
Bidirectional Transmission

 Possible if two parties have separate channels for

full-duplex transmission or share same channel
for half-duplex transmission

University of South Alabama 26

Computer and Information Sciences
Piggybacking

 Method of combining data frame and

acknowledgement
 Saves bandwidth due to less overhead from
separate data frame and ACK frame into one
frame

University of South Alabama 27

Computer and Information Sciences
Piggybacking

University of South Alabama 28

Computer and Information Sciences
Sliding Window
 Sender may transmit several frames before
needing an ACK
 Much more efficient; receiver may use a single
ACK to confirm multiple frames
 Sliding window refers to upper and lower limit on
number of frames that may be transmitted before
ACK is required
 Frames must be numbered to allow receiver to
identify which frame is acknowledged

University of South Alabama 29

Computer and Information Sciences
11.3 Go-Back-N ARQ

 Allows for more efficient transmission – send

multiple frames before requiring an ACK
 Specify a window or range of sequence numbers
of frames that may be received

University of South Alabama 30

Computer and Information Sciences
Sliding Window

 Receiver includes number of next frame it

expects to receive in ACK
 Sender then knows all previous frames through
that number have been received

University of South Alabama 31

Computer and Information Sciences
Sender Window

 Window contains 0 to
2m -1 frames
 Window shrinks as
frames are sent out
 Once ACK arrives,
window expands
equal to number of
frames acknowledged
by ACK
University of South Alabama 32
Computer and Information Sciences
Receiver Window

 Receiver expects the next

ordered frame (must always be
in order)
 Any frame arriving out of order
is discarded

University of South Alabama 33

Computer and Information Sciences
Control Variables
 Sender : S – sequence number of recently sent frame; S
F
- sequence number of first frame in window; SL –
sequence number of last frame in window
 Window size is W = S - S + 1
L F
 Receiver : R – sequence number of next frame expected

University of South Alabama 34

Computer and Information Sciences
Go-Back-N Operation

 Timers: sender sets a timer for each frame (none

for receiver)
 Acknowledgement – receiver sends positive ACK;
silent on damaged or out of order frames
 Resending Frames – sender sends set of frames
from damaged up to last one sent and ACK’d

University of South Alabama 35

Computer and Information Sciences
11.4 Selective Repeat ARQ

 Go-Back-N less efficient since all out of order or

damaged frames must be resent in order
 Selective Repeat is a more efficient method, yet
required more processing

University of South Alabama 36

Computer and Information Sciences
Sender and Receiver Windows

 Sender window and control variables are same

as Go-Back-N
 Receiver window is same size; looks for range of
sequence numbers
 Requires two control variables to define window
boundaries: RF and RL
 Also defines a negative acknowledgement (NAK)
to report sequence number of damaged frame

University of South Alabama 37

Computer and Information Sciences
Selective Repeat ARQ

University of South Alabama 38

Computer and Information Sciences
Selective Repeat ARQ, Lost Frame

University of South Alabama 39

Computer and Information Sciences
Comparisons between Go-back-n
and Selective-Reject
 Sending only specific damaged or lost frames
requires complexity of sorting and more storage
is required in select-reject
 Go-back-n is typically used due to simplicity

University of South Alabama 40

Computer and Information Sciences
 Sliding Window

Sender Sliding
Window

Receiver Sliding Window

41
Sliding Window Example

42
Error Control

43
 Normal operation

In Stop-and-Wait ARQ, numbering frames prevents the retaining of

duplicate frames.

44
Stop-and-Wait ARQ, lost frame

45
Stop-and-Wait ARQ, lost ACK frame

46
Damaged Frame

47
Damaged Frame

48
Lost Frame

49
Figure 10-21
Lost ACK

50
WCB/McGraw-Hill  The McGraw-Hill Companies, Inc., 1998
Figure 10-22
Selective Reject

51
WCB/McGraw-Hill  The McGraw-Hill Companies, Inc., 1998
 Data Link Protocols

 Is a set of specifications used to implement

the data link layer
 Data link protocols differ by message , frame
length, and frame field structure.
 Another fundamental difference is between
asynchronous and synchronous transmission
data link protocols.

52
Asynchronous Protocols
 In asynchronous transmission (sometimes called start-stop
transmission),
each character is sent independently.
 The transmission sequence begins with
 a start bit
 next the character is sent
 then the parity bit
 and finally a stop bit are sent.
 The start bit is usually a 0 and the stop bit a 1.

 Between transmissions (called “idle time”), a series of

stop bits are sent.
 When a new character is sent, the start bit is used by
the receiver for synchronization.

53
Asynchronous Protocols
 Protocols that belong to asynchronous protocols
 XMODEM
 YMODEM
 ZMODEM
 BLAST
 Kermit

54
Synchronous Protocols
 In synchronous transmission
 data is sent in a large block called a frame
 Synchronous transmission is used on both
 point-to-point
 multipoint circuits
 In multipoint circuits, addressing information needs
to be included in the frame.
 Synchronous packets sometimes begin and end
with a series of synchronization (SYN) characters
that are used to help the receiver recognize
incoming data.

55
Synchronous Protocols
 Synchronous transmission protocols can be:
 character-oriented:
 Also known as byte-oriented protocols
 Interpret a transmission frame as a succession of
characters
 bit-oriented:
 Interpret a transmission frame as a succession of
individual bits
 Control information in a bit-oriented protocol can
be one or multiple bits depending on the
information embodied in the pattern

56
Bit-oriented protocols

57
 HDLC : High-level Data Link Control

It is a bit-oriented data link protocol

Designed to support both half duplex and full duplex
communication over point-to-point and multipoint links.
It implements the ARQ mechanisms.
The HDLC protocol embeds information in a data frame
that allows devices to control data flow and correct errors

58
 HDLC : High-level Data Link Control
 In 1979, the ISO made HDLC the standard as
a Bit-oriented control protocol
 The HDLC provides a transparent
transmission service at the data link layer of
the OSI
 The users of the HDLC service provides
PDUs which are encapsulated to form data
link layer frames. These frames are
separated by HDLC "flags" and are modified
by "zero bit insertion" to guarantee
transparency
59
 HDLC : High-level Data Link Control
 Each piece of data is encapsulated in an HDLC
frame by adding a trailer and a header.
 The header contains an HDLC address and an
HDLC control field.
 The trailer is found at the end of the frame, and
contains a (CRC) which detects any errors which
may occur during transmission.
 The frames are separated by HDLC flag
sequences which are transmitted between each
frame and whenever there is no data to be
transmitted.
60
 HDLC Frame Fields
Flag field
 is 8 bits of a fixed pattern (0111 1110).
 There is one flag at the beginning and one at the end frame.
 The ending flag of one Frame can be used as the beginning
flag of the next frame.
 To guarantee that the flag does not appear anywhere else in
the frame
 HDLC uses a process called Bit Stuffing.
 Every time a sender wants to transmit a bit sequence having
more than 6 consecutive 1’s, it inserts 1 redundant 0 after
the 5th 1
Exceptions:
 When the bit sequence is really a flag.
 when transmission is being aborted.
 when the channel is being61put into idle.
 Bit Stuffing
 the process of adding one extra zero whenever there
are 5 consecutive 1’s in the data, so that the receiver
doesn’t mistake the data for a flag.

A frame before bit stuffing:

01111110 01111100 101101111 110010

After
011111010 011111000 101101111 1010010

62
 How does the receiver identify a stuffed bit?

 Receiver reads incoming bits and counts 1’s.

 When number of consecutive 1s after a zero is 5,
it checks the next bit (7th bit).
 If 7th bit = zero  receiver recognizes it as a
stuffed bit, discard it and resets the counter.
 If the 7th bit = 1  then the receiver checks the 8 th
bit; If the 8th bit = 0, the sequence is recognized
as a flag.

01111010 011111000 101101111 1010010

63
How does the receiver identify a stuffed bit?

64
Address field
 Address field is one byte or more
 If the address is more than one byte, all bytes
will end with 0,except the last one

65
HDLC Control Field

66
 Control Field
 all three types contain a bit called (Poll/Final) P/F bit
I-Frame
 N(S) : sequence # of the sent frame
 N(R) : sequence # of frame expected in return
  N(R) is ACK field

 If last frame received is error free

N(R) number will be the next frame in sequence
 If the frame was not received correctly
 N( R) number will be the number of damaged frame indicating the
need for retransmission

67
I frame

68
 Poll/Final
 P/F = 1 POLL or Final
 Poll if frame is sent by the primary
 Final if frame is sent by the secondary

69
Information
Field

70
 Information Field

 Contains user data in I-frame and network

management information in a U-frame.
 It is possible to include flow and error control
information in an I-frame that also contains data.
 In 2-way exchange of data (1/2 or full-duplex), the
2nd station can ACK receipt of data from the 1 st
station in the control field of its own data frame
rather than sending a separate frame just for ACK.
 Combining data to be sent & ACK of the frame
received in one single frame is called
PIGGYBACKING.
71
HDLC FCS Field

72
S-frame control field in HDLC

73
74
 Receive Ready (RR)
 Positive ACK of a received I- frame
 POLL
 Negative response to poll
 Positive response to select

 Receive Not Ready (RNR)

 Primary uses it for for select with P=1
 It Ack the receipt of a frame and announces that
the receiver is busy
 Negative response to select with f=1

 Reject (REJ)
 This is a NAK frame that can be used in Go-back-n

 Selective reject (SREJ)

 This is a NAK frame used in Selective Repeat ARQ

75
 Example
 The figure shows an exchange using piggybacking
where is no error
 Station A begins the exchange of information
with an I-frame numbered 0 followed by another
I-frame numbered 1.
 Station B piggybacks its acknowledgment of
both frames onto an I-frame of its own.
 Station B’s first I-frame is also numbered 0 [N(S)
field] and contains a 2 in its N(R) field,
acknowledging the receipt of A’s frames 1 and 0
and indicating that it expects frame 2 to arrive
next.
 Station B transmits its second and third I-frames
(numbered 1 and 2) before accepting further
frames from station A.
 Its N(R) information, therefore, has not changed:
B frames 1 and 2 indicate that station B is still
expecting A frame 2 to arrive next.
76
 Example
 In the previous Example,
suppose frame 1 sent from
station B to station A has an
error.
 Station A informs station B to
resend frames 1 and 2 (the
system is using the Go-Back-N
mechanism)
 Station A sends a reject
supervisory frame to announce
the error in frame 1

77
 Polling Example
asking the secondary if it has anything to send

78
 Selecting Example
A primary wishes to send data to secondary

79
U-frame control field in HDLC

80
 Table 11.1 U-frame control command and response

Command/response Meaning
SNRM Set normal response mode
SNRME Set normal response mode (extended)– control field 2 bytes
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
81
U-frame Mode setting
 Mode-setting commands sent by the primary or
combined station wishing to control an exchange
 If a combined station wishes to establish a
temporary primary-to-secondary relationship with
another station it sends a U-frame containing code
00-001 (Normal Response Mode)

82
U-frame Disconnection
 There are three disconnection codes
 One command from acting primary or combined
station
 disconnection (DISC 00 010) is sent by the 1 st station to
the 2nd station to terminate the connection
 Two responses from the receiving station
 request disconnect (RD 00 010) is a request by the 2 nd
station to the 1st that a DISC be issued.
 disconnect mode (DM 11 000) is transmitted by the
addressed station as a negative response to mode-
setting command

83
 Peer-to-Peer Example

Set asynchronous balanced mode

84
Continued Peer-to-Peer Example

85
 Example
The following HDLC frame is sent from the secondary to primary
(0111 1110 00001111 10001011 FCS 0111 1110)
0111 1110 00001111 10001011 0111 1110
FCS
Flag Address Control Flag

a) What is the address of the secondary?

Answer: Address = 0000111 = 7
since Last bit of the address ends is 1 this byte is last one in address field
Note: If the address is more than one byte, all bytes will end with 0, except the last one.

b) What is the type of the frame?

Answer: 10 in control field indicates, that this is a supervisory  S-Frame
c) What is the sender sequence ?
Answer : N/A since this is an S-frame, the 1 st two bits are 10  S-Frame

d) What is ACK # ? 011 = 3

e) Does the frame carry user data ? No 86

f) Does the frame carry management data? No, only the U-frame carry management data.
 Question
The following HDLC frame is sent from the secondary to primary
(0111 1110 00000111 10101011 FCS 0111 1110)

0111 1110 0000 0111 1010 1011 0111 1110

FCS
Flag Address Control Flag

a) What is the address of the secondary? 0000 011 = 3

since Last bit of the address ends is 1 this byte is last one in address field
Note: If the address is more than one byte, all bytes will end with 0, except the last one.

b) What is the type of the frame? 10 in control field indicates, that this is a supervisory  S-Frame
c) What is the sender sequence ? N/A since this is an S-frame, the 1st 2 bits are 10  S-Frame

d) What is ACK # ? 011 = 3

e) Does the frame carry user data ? No
f) Does the frame carry management data? No, only the U-frame carry management data.
 receive not ready  Negative response to
g) What is the purpose of the frame? code = 10 87
select
Example

The following HDLC frame is sent from the secondary to primary

0111 1110 0000 0111 00101011 00111110010111100100001011 0111 1110

FCS
Flag Address Control information Flag

a) What is the address of the secondary? Address = 0000 011 = 3

since Last bit of the address ends is 1this byte is last one in address field

b) What is the type of the frame? 0 in control field indicates, I-Frame

c) What is the sender sequence ? the 1st bit is zero  I-Frame N( S)= 010 = 2

d) What is ACK # ? 011 = 3

e) Does the frame carry user data ? 001111101011110010100001011
f) Does the frame carry management data?
88
No, only the U-frame carry management data.
Other Data Link Control Protocols
 Link access procedure, balanced (LAPB)
 Full-duplex, point-to-point mode
 For X.25 DTE and packet switching network

 Link access procedure, D-channel (LAPD)

 ISDN network
 Link access procedure for frame –mode
bearer service (LAPF)
 High-speed packet switching network on low error
rate digital circuits
 Asynchronous transfer mode
 Data transfer on high s-speed, digital, error free
network