Data Link Layer

Data Link Control

MAC Sublayer
FRAMING

The data link layer needs to pack bits into

frames,,
frames so that each frame is
distinguishable from another. Our postal
system practices a type of framing. The
simple act of inserting a letter into an
envelope separates one piece of
information from another; the envelope
serves as the delimiter.
Topics discussed in this
Fixed-Size section:
Framing
Variable-Size Framing
 Figure 11.1 A frame in a character-
oriented protocol

11.3
11. 3
 Figure 11.2 Byte stuffing and
unstuffing

11.4
11. 4
 Not
e
Byte stuffing is the process of adding 1
extra byte whenever there is a flag or
escape character in the text.

11.5
11. 5
 Figure 11.3 A frame in a bit-oriented
protocol

11.6
11. 6
 Not
e
Bit stuffing is the process of adding one
extra 0 whenever five consecutive 1s
follow a 0 in the data, so that the
receiver does not mistake
the pattern 0111110 for a flag.

11.7
11. 7
 Figure 11.4 Bit stuffing and
unstuffing

11.8
11. 8
 FLOW AND ERROR CONTROL

The most important responsibilities of the

data link layer are flow control and error
control.. Collectively, these functions are
control
control.
known as data link control.

Topics discussed in this

section:
Flow Control
Error Control

11.9
11. 9
 Not
e
Flow control refers to a set of procedures
used to restrict the amount of data
that the sender can send before
waiting for acknowledgment.

11.10
11. 10
 Not
e
Error control in the data link layer is
based on automatic repeat request,
which is the retransmission of data.

11.11
11. 11
 PROTOCOLS
Now let us see how the data link layer can
combine framing, flow control, and error
control to achieve the delivery of data from
one node to another. The protocols are
normally implemented in software by using
one of the common programming
languages. To make our discussions
language-free, we have written in
pseudocode a version of each protocol that
concentrates mostly on the procedure
instead of delving into the details of
language rules.

11.12
11. 12
 Taxonomy of
protocols

11.13
11. 13
 NOISELESS CHANNELS

Let us first assume we have an ideal

channel in which no frames are lost,
duplicated, or corrupted. We introduce two
protocols for this type of channel.

Topics discussed in this

section:
Simplest Protocol
Stop-and-Wait Protocol

11.14
11. 14
The design of the simplest protocol with no flow or
error control
 Sender-site algorithm for the
simplest protocol

11.16
11. 16
 Receiver-site algorithm for the
simplest protocol

11.17
11. 17
 Example
1
Figure shows an example of communication
using this protocol. It is very simple. The
sender sends a sequence of frames without
even thinking about the receiver. To send
three frames, three events occur at the sender
site and three events at the receiver site. Note
that the data frames are shown by tilted
boxes; the height of the box defines the
transmission time difference between
the first bit and the last bit in the frame.

11.18
11. 18
 Flow diagram for
Example 1

11.19
11. 19
Stop-and-Wait
Protocol
 Design of Stop-and-Wait
Protocol

11.21
11. 21
 Sender-site algorithm for Stop-and-
Wait Protocol

11.22
11. 22
 Algorithm 11.4 Receiver-site algorithm for Stop-and-
Wait Protocol

11.23
11. 23
 Example
2
Figure shows an example of communication
using this protocol. It is still very simple. The
sender sends one frame and waits for
feedback from the receiver. When the ACK
arrives, the sender sends the next frame. Note
that sending two frames in the protocol
involves the sender in four events and the
receiver in two events.

11.24
11. 24
 Flow diagram for
Example 2

11.25
11. 25
 NOISY CHANNELS

Although the Stop-and-Wait Protocol gives

us an idea of how to add flow control to its
predecessor, noiseless channels are
nonexistent. We discuss three protocols in
this section that use error control.

Topics discussed in this

section:
Stop-and-Wait Automatic Repeat Request
Go-Back-N Automatic Repeat Request
Selective Repeat Automatic Repeat
Request

11.26
11. 26
 Stop and Wait ARQ

• Sequence Number

• Acknowledgement Number
 Stop and Wait ARQ

Error correction in Stop-and-Wait ARQ is done by

keeping a copy of the sent frame and retransmitting
of the frame when the timer expires.

11.28
11. 28
 Stop and Wait ARQ
Window size of this protocol is 1.
The possible number of sequence
numbers is given by
21
i.e only 2 SEQ_NO are possible: 0, 1

11.29
11. 29
 Not
e
In Stop-and-Wait ARQ, the
acknowledgment number always
announces the sequence number of the
next frame expected.

11.30
11. 30
 Design of the Stop-and-Wait ARQ
Protocol

11.31
11. 31
 Example
3
How Stop-and-Wait ARQ reacts to

1. Lost Frame

2. Damaged Frame

3. Lost ACK

11.32
11. 32
Flow
diagram
Efficiency?..
 Exampl
e

Assume that, 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 frames are 1000 bits in
length, what is the utilization percentage of the link?

Solution
The bandwidth-delay product is
 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 percent. For this reason, for
a link with a high bandwidth or long delay,
the use of Stop-and-Wait ARQ wastes the
capacity of the link.

11.36
11. 36
Solution ?...
What if we can send multiple frames before
waiting for an ACK?

What is the utilization percentage of the

link in Example if we have a protocol that
can send up to 15 frames before stopping
and worrying about the acknowledgments?
Solution
The bandwidth-delay product is still 20,000 bits. The
system can send up to 15 frames or 15,000 bits during a
round trip. This means the utilization is 15,000/20,000,
or 75 percent.
Sliding Window Protocols
Go-Back-N
Not
e
In the Go-Back-N Protocol, the
sequence numbers are modulo 2m,
where m is the size of the sequence
number field in bits.
Send window for Go-Back-
N ARQ
Not
e
The send window is an abstract
concept defining an imaginary box of
size 2m − 1 with three variables: Sf, Sn,
and Ssize.
Not
e
The send window can slide one
or more slots when a valid
acknowledgment arrives.
Receive window for Go-Back-
N ARQ
Not
e
The receive window is an abstract
concept defining an imaginary box
of size 1 with one single variable Rn.
The window slides
when a correct frame has arrived;
sliding occurs one slot at a time.
Design of Go-Back-N
ARQ
Window size for Go-Back-
N ARQ
Not
e
In Go-Back-N ARQ, the size of the send
window must be less than 2m;
the size of the receiver window
is always 1.
 Flow diagram Example of Go-Back-N (Delayed and
Lost ACKs)

11.51
11. 51
Lost
Frame
Not
e
Stop-and-Wait ARQ is a special case of
Go-Back-N ARQ in which the size of the
send window is 1.
11.54
11. 54
11.55
11. 55
11.56
11. 56
11.57
11. 57
 Selective Repeat
■ In this ARQ
protocol, only damaged/lost frame is
retransmitted.
■ Out-of-order frames are stored in the buffer,
until it gets the ordered frame.
■ Sender and receiver window size is same,
coz of the need for storing the out-of-order
frames.
■ It is suited for noisy channel, where in more
number of retransmissions are expensive.
■ But the complexity is
■ Sender should have searching algorithm
Send window for Selective
Repeat ARQ
Receive window for Selective
Repeat ARQ
Design of Selective
Repeat ARQ
 Window
m =2
size=2m-1
Not
e
In Selective Repeat ARQ, the size of the
sender and receiver window
must be at most one-half of 2m.
Delivery of data in Selective
Repeat ARQ
Flow diagram-Lost
Frame
 Difference between Stop and Wait, Go Back N and
Selective Repeat

11.66
11. 66
11.67
11. 67
11.68
11. 68
 Piggybacki
ng
■ Normally, data flows in both directions. i.e
from node A to node B and node B to node A.
■ Piggybacking is used to improve the
efficiency of bi-directional protocol by
carrying control information (ACK) as well
as data .
Design of piggybacking in Go-Back-
N ARQ
 HDLC

High-level Data Link Control (HDLC) is a bit-

oriented protocol for communication over
point-to-point and multipoint links. It
implements the ARQ mechanisms.

Topics discussed in this

section:
Configurations and Transfer Modes
Frames
Control Field
 Configurations and Transfer
Modes
• Normal Response Mode (NRM)
• Primary sends-Commands
• Secondary sends-Response
• Can be point-to-point or point-to-
multipoint

• Asynchronous Balanced Mode (ABM)

• Each station can function as Primary/
Secondary
• Is always point-to-point
Normal response
mode
Asynchronous
balanced mode
 HDLC Frames

• Information Frame (I-Frame)

• Carry user data

• Supervisory frame (S-Frame)

• Carry control information

• Unnumbered frame (U-Frame)

• Carry system management information.
information.
HDLC
frames
Control field format for the different
frame types
 I-Frame

SEQ_NO ACK
 S - Frame

Code Meaning Purpose

00 Receive Ready (RR) ACK frame
10 Receive Not Ready (RNR) ACK + Congestion
control
01 Reject (REJ) NAK Frame(GBN)
11 Selective Reject (SREJ) NAK Frame(SR)
 U - Frame

5-bit codes can be used to create 32 different

types of U-frames
U-frame control command and
response
U-frames can be used for connection
establishment
and connection release
Exchange using piggybacking
(without error)
Example of piggybacking
with error
Questio
ns