Chapter 11

Data Link layer

Flow control
protocols

McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004

 11-1 FRAMING

The data link layer needs to pack bits into frames, so

that each frame is distinguishable from another.

Fixed-Size Framing
Variable-Size Framing

In variable-size framing, we need a way to define the

end of the frame and the beginning of the next.
• Character Oriented
• Bit oriented
11.2
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
 Figure 11.1 A frame in a character-oriented protocol

 In a character-oriented protocol, data to be carried are 8-bit

characters .
 The header,
 which normally carries the source and destination addresses
 and other control information,
 the trailer, which carries
 error detection or error correction redundant bits, are also
multiples of 8 bits.
 To separate one frame from the next, an 8-bit (I-byte) flag is
added at the beginning and the end of a frame.

11.3
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
 Figure 11.2 Byte stuffing and unstuffing

11.4
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
 Figure 11.3 A frame in a bit-oriented protocol

 in addition to headers (and possible

trailers), we still need a delimiter to
separate one frame from the other.
 Most protocols use a special 8-bit pattern
flag 01111110 as the delimiter to define the
beginning and the end of the frame,

McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004

 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.

11.6
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
 Figure 11.4 Bit stuffing and unstuffing

11.7
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
 11-2 FLOW AND ERROR CONTROL

The most important responsibilities of the data link

layer are flow control and error control.

11.8
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
 Figure 11.5 Taxonomy of protocols discussed in this chapter

11.9
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
 11-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.

Simplest Protocol
Stop-and-Wait Protocol

11.10
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
 Our first protocol, which we call the Simplest Protocol for
lack of any other name, is one that has no flow or error
control.

 It is a unidirectional protocol in which data frames are

traveling in only one direction-from the sender to receiver.

 We assume that the receiver can immediately handle any

frame it
receives with a processing time that is small enough to be
negligible.

 The data link layer of the receiver immediately removes the

header from the frame and hands the data packet to its
network layer, which can also accept the packet
immediately.

McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004

 Stop and Wait Flow control

 The simplest form of flow control.

 The source transmits a data frame
 After receiving the frame the destination
indicates its willingness to accept another
frame by sending back an ACK frame
acknowledging the frame just received.
 The source must wait until it receives the
ACK frame before sending the next data

McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004

 11.1 Normal operation

McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004

 11-5 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.15
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
 11.2 Stop-and-Wait ARQ, lost frame

McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004

 11.3 Stop-and-Wait ARQ, lost ACK frame

McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004

 Stop and Wait Flow control

 Major drawback of Stop-and-

Wait Flow Control is that only
one frame can be in
transmission at a time, this
leads to inefficiency if
propagation delay is much
longer than the transmission
delay.
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
 11.5 Piggybacking

McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004

 11-5 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.20
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
 11-5 NOISY CHANNELS

There exist three popular ARQ

techniques

11.21
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
 Stop-and-Wait ARQ
 Based on stop and wait flow control technique

 Sender transmits a frame and then waits till it receives

positive acknowledgement (ACK) or negative
acknowledgement (NACK) from the receiver .

 Receiver sends an ACK if the frame is received correctly,

otherwise it sends NACK.

 Transmitter sends a new frame after receiving ACK;

otherwise it retransmits the old frame, if it receives a NACK

11.22
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
 Figure 11.11 Flow diagram for Example 11.3

11.23
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
 Stop and wait ARQ
 To take care of lost and damaged frame
the stations are :
 Equipped with a timer, if no
recognizable ACK is received when the
timer expires at the end of the time out
interval, then same frame is sent again.

 Sender is required to maintain a copy

of a transmitted frame until an ACK is
received for it

11.24
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
 Sliding Window Protocol Go
Back -N
 Sliding Window protocol

 The stop-and-wait protocol does not perform well.

Only one frame at a time can be in transit.

 Efficiency can be greatly improved by allowing

multiple frames to be in transit at the same time.

 Efficiency can also be improved by making use of

the full-duplex line.

McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004

 11.6 Sender sliding window

Size of window at sender side

if we decide that the field is m bits
long, the sequence numbers start from
0, go to 2m - 1, and then are repeated.

McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004

 11.7 Receiver sliding window

Size of window at receiver side is 1

McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004

 Go back n ARQ

 Based on sliding window protocol

 Basic Concept:

 A station sends a series of frames sequentially up

to a maximum number
 The number of unacknowledged frames outstanding
is determined by window size, using the sliding
window flow control technique.
 In case of no error, the destination will acknowledge
incoming frames as usual.
11.28
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
 Figure 11.12 Send window for Go-Back-N ARQ

11.29
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
 Figure 11.13 Receive window for Go-Back-N ARQ

11.30
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
 Selective Repeat ARQ
 In this case only those frames are
retransmitted for which negative
acknowledgement has been received, in this
case called SREJ, or time out has occurred
 It is more efficient than go back N
 Receiver requires storage buffers to contain
out of order frames until the frame in error is
correctly received.
 Transmitter is also more complex because it must be
capable of sending frames out of sequence

11.31
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
 Figure 11.18 Send window for Selective Repeat ARQ

11.32
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
 Figure 11.19 Receive window for Selective Repeat ARQ

11.33
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
 Figure 11.21 Selective Repeat ARQ, window size

11.34
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
 Figure 11.22 Delivery of data in Selective Repeat ARQ

11.35
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
 Review Questions

11.36
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
 Multiple Choice Questions
In a Go-Back-N ARQ, if the window size is 63, what is the
range of sequence numbers?
a. 0 to 63
b. 0 to 64
c. 1 to 63
d. 1 to 64

In Go-Back-N ARQ, if frames 4, 5, and 6 are received

successfully, the receiver may send an ACK _______ to the
sender.
a. 5
b. 6
c. 7
d. 4

For Stop-and-Wait ARQ, for 10 data packets sent, _______

acknowledgments are needed.
a. exactly 10
b. less than 10
c. more
11.37 than 10
©
McGraw-Hill The McGraw-Hill Companies, Inc., 2004
 Multiple Choice Questions
In a Go-Back-N ARQ, if the window size is 63, what is the
range of sequence numbers?
a. 0 to 63
b. 0 to 64
c. 1 to 63
d. 1 to 64

In Go-Back-N ARQ, if frames 4, 5, and 6 are received

successfully, the receiver may send an ACK _______ to the
sender.
a. 5
b. 6
c. 7
d. 4

For Stop-and-Wait ARQ, for 10 data packets sent, _______

acknowledgments are needed.
a. exactly 10
b. less than 10
c. more
11.38 than 10
©
McGraw-Hill The McGraw-Hill Companies, Inc., 2004
 Multiple Choice Questions
In _______ the data link layer separates a message from one
source to a destination, or from other messages going from
other sources to other destinations.
a. Digitizing
b. Controlling
c. Framing
d. none of the above
In a ________ protocol, the data section of a frame is a
sequence of characters.
a. bit-oriented
b. character-oriented
c. either (a) or (b)
d. none of the above

In a _________ protocol, the data section of a frame is a

sequence of bits.
a. byte-oriented
b. bit-oriented
c. either (a) or (b)
d. none of the above
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004
 Multiple Choice Questions
In _______ the data link layer separates a message from one
source to a destination, or from other messages going from
other sources to other destinations.
a. Digitizing
b. Controlling
c. Framing
d. none of the above
In a ________ protocol, the data section of a frame is a
sequence of characters.
a. bit-oriented
b. character-oriented
c. either (a) or (b)
d. none of the above

In a _________ protocol, the data section of a frame is a

sequence of bits.
a. byte-oriented
b. bit-oriented
c. either (a) or (b)
d. none of the above
McGraw-Hill ©The McGraw-Hill Companies, Inc., 2004