1 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
Data Link Control inserting a letter into an envelope separates one piece of
information from another; the envelope serves as the
delimiter.
Topics discussed in this section:
Fixed-Size Framing
Variable-Size Framing
Lecture Notes - K N Jariwala Lecture Notes - K N Jariwala
Figure 1 A frame in a character-oriented protocol
Note
Byte stuffing is the process of adding 1
extra byte whenever there is a flag or
escape character in the text.
Lecture Notes - K N Jariwala Lecture Notes - K N Jariwala
Lecture Notes - K N Jariwala
Figure 3 A frame in a bit-oriented protocol
Note
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.
Lecture Notes - K N Jariwala Lecture Notes - K N Jariwala
2 FLOW AND ERROR CONTROL
The most important responsibilities of the data link layer
are flow control and error control.
control. Collectively, these Note
functions are known as data link control.
control.
Flow control refers to a set of procedures
used to restrict the amount of data
that the sender can send before
Topics discussed in this section: waiting for acknowledgment.
Flow Control
Error Control
Lecture Notes - K N Jariwala Lecture Notes - K N Jariwala
Lecture Notes - K N Jariwala
3 PROTOCOLS
Now let us see how the data link layer can combine
Note framing, flow control, and error control to achieve the
delivery of data from one node to another. The protocols
Error control in the data link layer is based are normally implemented in software by using one of the
common programming languages. To make our
on automatic repeat request, which is the
discussions language-
language-free, we have written in pseudo code
retransmission of data. a version of each protocol that concentrates mostly on the
procedure instead of delving into the details of language
rules.
Lecture Notes - K N Jariwala Lecture Notes - K N Jariwala
Figure 5 Taxonomy of protocols discussed in this chapter 4 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
Lecture Notes - K N Jariwala Lecture Notes - K N Jariwala
Lecture Notes - K N Jariwala
Figure 6 The design of the simplest protocol with no flow or error control Algorithm 1 Sender-site algorithm for the simplest protocol
Lecture Notes - K N Jariwala Lecture Notes - K N Jariwala
Figure 8 Design of Stop-and-Wait Protocol
Algorithm 2 Receiver-site algorithm for the simplest protocol
Lecture Notes - K N Jariwala Lecture Notes - K N Jariwala
Lecture Notes - K N Jariwala
Algorithm 3 Sender-site algorithm for Stop-and-Wait Protocol Algorithm 4 Receiver-site algorithm for Stop-and-Wait Protocol
Lecture Notes - K N Jariwala Lecture Notes - K N Jariwala
5 NOISY CHANNELS
Although the Stop-
Stop-and-
and-Wait Protocol gives us an idea of Note
how to add flow control to its predecessor, noiseless
channels are nonexistent. We discuss three protocols in Error correction in Stop-and-Wait ARQ is
this section that use error control. done by keeping a copy of the sent frame
and retransmitting of the frame when the
timer expires.
Topics discussed in this section:
Stop-and-Wait Automatic Repeat Request
Go-Back-N Automatic Repeat Request
Selective Repeat Automatic Repeat Request
Lecture Notes - K N Jariwala Lecture Notes - K N Jariwala
Lecture Notes - K N Jariwala
Note
Note
In Stop-and-Wait ARQ, we use sequence In Stop-and-Wait ARQ, the acknowledgment
numbers to number the frames. number always announces in modulo-2
The sequence numbers are based on arithmetic the sequence number of the next
modulo-2 arithmetic. frame expected.
Lecture Notes - K N Jariwala Lecture Notes - K N Jariwala
Figure 10 Design of the Stop-and-Wait ARQ Protocol Algorithm 5 Sender-site algorithm for Stop-and-Wait ARQ
(continued)
Lecture Notes - K N Jariwala Lecture Notes - K N Jariwala
Lecture Notes - K N Jariwala
Algorithm 5 Sender-site algorithm for Stop-and-Wait ARQ (continued)
Algorithm 6 Receiver-site algorithm for Stop-and-Wait ARQ Protocol
Lecture Notes - K N Jariwala Lecture Notes - K N Jariwala
Note
Note
In the Go-Back-N Protocol, the sequence
numbers are modulo 2m, The send window is an abstract concept
where m is the size of the sequence number defining an imaginary box of size 2m − 1
field in bits. with three variables: Sf, Sn, and Ssize.
Lecture Notes - K N Jariwala Lecture Notes - K N Jariwala
Lecture Notes - K N Jariwala
Note
Note
The receive window is an abstract concept
The send window can slide one defining an imaginary box
or more slots when a valid acknowledgment of size 1 with one single variable Rn.
arrives. The window slides
when a correct frame has arrived; sliding
occurs one slot at a time.
Lecture Notes - K N Jariwala Lecture Notes - K N Jariwala
Figure 14 Design of Go-Back-N ARQ
Note
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.
Lecture Notes - K N Jariwala Lecture Notes - K N Jariwala
Lecture Notes - K N Jariwala
Algorithm 7 Go-Back-N sender algorithm (continued)
Algorithm 7 Go-Back-N sender algorithm
(continued)
Lecture Notes - K N Jariwala Lecture Notes - K N Jariwala
Algorithm 8 Go-Back-N receiver algorithm
Note
Stop-and-Wait ARQ is a special case of Go-
Back-N ARQ in which the size of the send
window is 1.
Lecture Notes - K N Jariwala Lecture Notes - K N Jariwala
Lecture Notes - K N Jariwala
Figure 20 Design of Selective Repeat ARQ
Note
In Selective Repeat ARQ, the size of the
sender and receiver window
must be at most one-half of 2m.
Lecture Notes - K N Jariwala Lecture Notes - K N Jariwala
Algorithm 9 Sender-site Selective Repeat algorithm Algorithm 9 Sender-site Selective Repeat algorithm (continued)
(continued)
Lecture Notes - K N Jariwala Lecture Notes - K N Jariwala
(continued)
Lecture Notes - K N Jariwala
Algorithm 9 Sender-site Selective Repeat algorithm (continued) Algorithm 10 Receiver-site Selective Repeat algorithm
Lecture Notes - K N Jariwala Lecture Notes - K N Jariwala
Algorithm 10 Receiver-site Selective Repeat algorithm
Figure 24 Design of piggybacking in Go-Back-N ARQ
Lecture Notes - K N Jariwala Lecture Notes - K N Jariwala
Lecture Notes - K N Jariwala
6 HDLC Figure 27 HDLC frames
High-
High-level Data Link Control (HDLC) is a bit-
bit-oriented
protocol for communication over point-
point to point and
-to-
-
multipoint links. It implements the ARQ mechanisms we
discussed in this chapter.
Topics discussed in this section:
Configurations and Transfer Modes
Frames
Control Field
Lecture Notes - K N Jariwala Lecture Notes - K N Jariwala
Figure 28 Control field format for the different frame types
Table 1 U-frame control command and response
Lecture Notes - K N Jariwala Lecture Notes - K N Jariwala
Lecture Notes - K N Jariwala
