FLOW CONTROL AND ERROR CONTROL

The two main features of data kink layer are flow control and error control.

.FLOW CONTROL
Flow control coordinates that amount of data that can be sent before receiving ACK It is one of the
most important duties of the data link layer.

ERROR CONTROL
 Error control in the data link layer is based on ARQ (automatic repeat request), which is the
retransmission of data.
 The term error control refers to methods of error detection and retransmission.
 Anytime an error is detected in an exchange, specified frames are retransmitted. This process is called
ARQ.

FLOW AND ERROR CONTROL MECHANISMS

1. STOP-AND WAIT ARQ.
2. GO-BACK-N ARQ.
3. SELECTIVE-REPEAT ARQ.

STOP-AND- WAIT ARQ

This is the simplest flow and error control mechanism. It has the following
features.
 The sending devise keeps the copy of the last frame transmitted until it receives an acknowledgement
for that frame. Keeping a copy allows the sender to re- transmit lost or damaged frames until they are
received correctly.
 Both data and acknowledgement frames are numbered alternately 0 and 1. A data frame 0 is
acknowledged by an ACK 1.
 A damaged or lost frame is treated in the same manner by the receiver. If the receiver detects an error in
the received frame, it simply discards the frame and sends no acknowledgement.
 The sender has a control variable, which we call S, that holds the number of recently sent frame. The
receiver has a control variable, which we call R that holds the number of the next frame expected.
 The sender starts a timer when it sends a frame. If an ACK is not received within an allotted time period
the sender assumes that the frame was lost or damaged and resends it.
 The receivers send only positive ACK for frames received safe and sound; it is silent about the frames
damaged or lost.

OPERATION:

The possible operations are

Normal operation
lost frame
ACK lost
delayed ACK.
The sender sends frame 0 and wait to receive ACK 1. when ACK 1 is received it sends frame 1 and
then waits to receive ACK 0, and so on.
The ACK must be received before the time out that is set expires. The following figure shows
successful frame transmission.
 Sender Receive
r

S=0 Frame 0
R=0
ACK 1
S=1 Frame 1
R=1
ACK 0
S=0





Time Time

Lost or damaged acknowledgement

o When the receiver receives the damaged frame it discards it, which essentially means the frame is lost.
The receiver remains silent about a lost frame and keeps its value of R.
o For example in the following figure the sender transmits frame 1, but it is lost. The receiver does nothing,
retaining the value of R (1). After the timer at the sender site expires, another copy of frame 1 is sent.

Sender Receive
r

S=0 Frame 0
R=0
ACK 1
S=1 Frame 1
R=1
Lost
S=1 Frame 1 R=1
Time-out
ACK0 R=0
S=0

Lost acknowledgement
o A lost or damaged ACK is handled in the same by the sender; if the sender receives a damaged ACK, it
discards it.
o The following figure shows a lost ACK 0.the waiting sender does not know if frame 1 has been received.
When the timer for frame 1 expires the sender retransmits frame 1.
o Note that the receiver has already received frame 1 and is expecting to receive frame 0. Therefore, its
silently discards the second copy of frame 1.
o The following figure shows a lost ACK 0.the waiting sender does not know if frame 1 has been received.
When the timer for frame 1 expires the sender retransmits frame 1.
o Note that the receiver has already received frame 1 and is expecting to receive frame 0. Therefore, its
silently discards the second copy of frame 1.

Sender Receive
r

S=0 Frame 0
R=0
ACK 1
S=1 Frame 1
R=1
ACK 0
Time-out S=1 Lost
Frame 1
R=0
ACK0
S=0 Expecting frame 0
Frame 1 is discarded

Time Time
 Delayed acknowledgement

o An ACK can be delayed at the receiver or by some problem with the link. The following figure shows
the delay of ACK 1; it ids received after the timer for frame 0 as already expired.
o The sender has already retransmitted a copy of frame 0. The receiver expects frame 1 so its simply
discards the duplicate frame 0.
o The sender has now received two ACK’s, one that was delayed and one that was sent after the duplicate
frame 0 arrived. The second ACK 1 is discarded.

Sender Receive
r
 S=0 Frame 0
R=0
Time-out ACK1
S=0 Frame0 R=1

S=1 Frame 1 Expecting frame 0

ACK1 Frame 1 is discarded
Discarded

S=1 Frame1
Time-out R=1
ACK0

Time Time

BIDIRECTIONAL TRANSMISSION
The stop – and – wait mechanism is unidirectional. We can have bi-directional transmission if the
two parties have two separate channels for full duplex communication or share the same channel for off
duplex transmission. In this case, each party needs both S and R variables to track frames sent and
expected.
PIGGYBACKING
It’s a method to combine a data frame with an ACK. In following figure both the sender and the
receiver have data to send. Instead of sending separate data and ACK frames. It can save bandwidth
because the overhead from a data frame and an ACK frame can be combined into just one frame.

Sender Receive
r

R=0
S=0 Frame 0,ACK0 R=0
S=0
R=0 Frame0,ACK 1
S=1
Frame 1,ACK1 R=1
S=1
R=1 Frame1,ACK 0
S=0

Time Time
 GO-BACK-N ARQ
 As in Stop-and-wait protocol senders has to wait for every ACK then next frame is transmitted. But in
GO-BACK-N ARQ number of frames can be transmitted without waiting for ACK. A copy of each
transmitted frame is maintained until the respective ACK is received.

Features of GO-BACK-N ARQ

1.sequence numbers.
Sequence numbers of transmitted frames are maintained in the header of frame. If k is the number of
bits for sequence number, then the numbering can range from 0 to 2k-1. Example: if k=3 means
sequence numbers are 0 to 7.
2. sender sliding window:

 Window is a set of frames in a buffer waiting for ACK. This window keeps on sliding in forward
direction, the window size is fixed. As the ACK is received, the respective frame goes out of window
and new frame to sent come into window. Figure illustrates the sliding window.
 If Sender receives. ACK 4, then it knows Frames upto
and including Frame 3 were correctly received

Window size=7

3. Receiver sliding window:

In the receiver side size of the window is always one. The receiver is expecting to arrive frame in
specifies sequence. Any other frame is received which is out of order is discarded. The receiver slides
over after receiving the expected frame. The following figure shows the receiver side-sliding window.

6 7 0 1 2 3 4 5 6 7
4. Control variables:
Sender variables and Receiver variables:
Sender deals with three different variables
S -> sequence number of recently sent frame
SF -> sequence number of first frame in the window.
SL -> sequence number of last frame in the window.
The receiver deals with only one variable
 R -> sequence number of frame expected.
5. Timers
The sender has a timer for each transmitted frame. The receivers don’t have any timer.
6. Acknowledgement:
The receiver responds for frame arriving safely by positive ACK. For damaged or lost frames
receiver doesn’t reply, the sender has to retransmit it when timer of that frame elapsed. The receiver may
ACK once for several frames.
7. resending frames:
If the timer for any frame expires, the sender has to resend that frame and the subsequent frame
also, hence the protocol is called GO-BACK-N ARQ.
Operation

Normal operation: Following diagram shows this mechanism. The sender keeps track of the

outstanding frames and updates the variables and windows as acknowledgements arrive.

Sender Receive
SF SL r

0 1 2 3 0 1 Frame 0
0 1 2 3 0
111 1 111
S Frame 1
0 1 2 3 0
0 1 2 3 0 1 ACK 2 1 111
111
S Frame 2
0 1 2 3 0
0 1 2 3 0 1 1111 111
ACK3
111
S Frame 3 0 1 2 3 0
1 111
0 1 2 3 0 
111 1 111 
S
Time Time

Damaged or lost frame:

Figure shows that frame 2 is lost. Note that when the receiver receives frame 3, it is discarded because

the receiver is expecting frame 2, not frame3. after the timer for frame 2 expires at the sender site, the

sender sends frame 2 and 3.

 Sender Receive
SF SL r

0 1 2 3 0 1 Frame 0
0 1 2 3 0
111 1 111
S Frame 1
0 1 2 3 0
0 1 2 3 0 1 ACK 2 1 111
111
S Frame 2 lost
0 1 2 3 0
0 1 2 3 0 1 1111 111
111
Frame 3
0 1 2 3 0 1 Frame 3 is discarded, not
111 in the window
Timeout
resent Frame 2
0 1 2 3 0 1
111 0 1 2 3 0
Frame 3 1 111
resent

0 1 2 3 0  0 1 2 3 0
111 1 111  1 111
S R

Time Time
Damaged or lost acknowledgement:
If an ACK is lost, we can have two situations. If the next ACK arrives before the expiration of
timer, there is no need for retransmission of frames because ACK are cumulative in this protocol.. if the
next ACK arrives after the timeout, the frame and all the frames after that are resent. The receiver never
resends an ACK.
For diagrams refer your class work notes.

Delayed Acknowledgement:
A delayed ACK also triggers the resending of frames.

SELECTIVE REPEAT ARQ:

 The configuration and its control variables for this are same as those selective repeat ARQ.
 The size of the window should be one half of the value 2m.
 The receiver window size must also be the size. In this the receiver is looking for a range of sequence
numbers.
 The receiver has control variables RF and RL to denote the boundaries of the window.