FLOW CONTROL

★ Flow control is the mechanism that ensures the rate at which a

sender is transmitting data is in proportion with the receiver’s

receiving capabilities.

★ Flow control is utilized in data communications to manage the

flow of data/packets among two different nodes, especially in

cases where the sending device can send data much faster than

the receiver can digest. Too much data arriving before a device

can handle it causes data overflow, meaning the data is either

lost or must be retransmitted.

★ Flow control refers to set of procedures that tell the sender

how much data it can able to transmit before waiting for an

acknowledgement from receiver.

★ Therefore, the receiver is provided with a control to regulate

the flow of the incoming frames. This control is in the form of

 an acknowledgement which is sent by the receiver. The

acknowledgement serves two purposes:

 It clears the sender to transmit the next data frame.

 It acknowledges receipt of all previous frames.

Protocol for Flow control:

 Stop-and-Wait Protocol

 Sliding Window Protocol

STOP-AND WAIT PROTOCOL

 Sender sends a data packet to the receiver.

 Sender stops and waits for the acknowledgement for the sent

packet from the receiver.

 Receiver receives and processes the data packet.

 Receiver sends an acknowledgement to the sender.

 After receiving the acknowledgement, sender sends the next

data packet to the receiver.

 Fi

g.1 Operation with no loss

Analysis-

 Sender puts the data packet on the transmission link.

 Data packet propagates towards the receiver’s end.

 Data packet reaches the receiver and waits in its buffer.

 Receiver processes the data packet.

 Receiver puts the acknowledgement on the transmission link.

 Acknowledgement propagates towards the sender’s end.

 Acknowledgement reaches the sender and waits in its buffer.

 Sender processes the acknowledgement.

 Total Time:

Total time taken in sending one data packet

= (Transmission delay + Propagation delay + Queuing delay +

Processing delay) packet

(Transmission delay + Propagation delay + Queuing delay +

Processing delay) ACK

Assume-

 Queuing delay and processing delay to be zero at both sender and

receiver side.

 Transmission time for the acknowledgement to be zero since it’s

size is very small.

Under the above assumptions

Total time taken in sending one data packet

= (Transmission delay + Propagation delay)packet + (Propagation
delay)ACK
 We know,

 Propagation delay depends on the distance and speed.

 So, it would be same for both data packet and acknowledgement.

Total time taken in sending one data packet

= (Transmission delay) packet + 2 x Propagation delay

In the stop-and wait flow control mechanism, only one data frame is

sent at a time and each frame is individually acknowledged. The

data frame and acknowledged frame take a certain amount of

propagation time to travel across the link. Propagation time can be

as large as 270msec for a satellite communication link or a few msec

for terrestrial link. Large propagation time makes the stop-and-wait

mechanism very inefficient from the point of view of link utilization.

Link utilization Efficiency in stop-and-wait flow control

Efficiency of any flow control protocol is given by-

Efficiency (η) = Useful Time / Total Time

 Here-

 Useful time = Transmission delay of data packet = (Transmission

delay) packet

 Useless time = Time for which sender is forced to wait and do

nothing = 2 x Propagation delay

 Total time = Useful time + Useless time

Thus

Assuming
  the receiver sends back acknowledgement immediately on

receipt of a data frame.

 the size of the acknowledgement frame is very small

 there are no errors in the data frame or its acknowledgement.

Dividing numerator and denominator by (Transmission delay) packet ,

we get-

If the average size of the frame is L bits and the data rate is R,

sending end device (A) shall complete transmission of one frame in

time is given by
 Transmission delay of data packet= (Transmission delay) =L/
packet

From here, we can observe-

 Efficiency (η) ∝ 1 / Distance between sender and receiver

 Efficiency (η) ∝ 1 / Bandwidth

 Efficiency (η) ∝ Transmission speed

 Efficiency (η) ∝ Length of data packet

The link utilization can be improved by keeping large frame size(L).

But large frames are more prone to errors and therefore effective

link utilization is reduced.

In stop-and-wait protocol, the source sends a packet and only after

the acknowledgement is received from the destination is the next

packet sent. This is a simple protocol, but it results in lots of delay,

and the channel bandwidth is not used efficiently. The throughput

will be very poor.

 Number of bits that can be sent through the channel per second is

called as its throughput.

Round Trip Time-

Round Trip Time = 2 x Propagation delay

Advantages-

The advantages of stop and wait protocol are-

 It is very simple to implement.

 The incoming packet from receiver is always an acknowledgement.

SLIDING WINDOW FLOW CONTROL PROTOCOL

In stop-and-wait flow control mechanism, link utilization efficiency

was poor when time to transmit a frame (tf) was significantly less

than the propagation time (tp). After transmitting a data frame, the

sending end remained idle until the acknowledgement was received

from the receiver. In sliding window flow control mechanism, the

sending end continues to transmit the next data frame without

waiting for the acknowledgement for the last frame (figure below).

In this case the sender sends two more data frames before it receives

acknowledgement for the first data frame. Therefore, the link does

not remain idle and link utilization is improved.

Fig. 3 Sliding Window Flow Control

Sliding window flow control is based on the following

acknowledgement mechanism:

 each data frame carries a sequence number for its

identification.

 the receiver acknowledges receipt of one or more data frames

by sending back a numbered acknowledgement. The

acknowledgement frame is written as RR-N (Receiver Ready-

N). N is the sequence number of the next data frame the

receiver expects to receive.

 All previous data frames are assumed acknowledged on receipt

of an acknowledgement.

Concept

Physically the window is defined in terms of three parameters

Lower window edge (LWE)

Upper window edge (UWE)

Window size (W)

  Sending Window

 copies of those data frames that have been transmitted

but their acknowledgements are yet to be received.

 the data frames which are next to be transmitted.

 Receiving Window

 It contains the sequence numbers of the data frames the

receiver is ready to accept.

 Any received data frame having sequence number which is

not in the window is discarded.

Flow Control Mechanism

Figure illustrates operation of the sliding window flow control

mechanism. Device A is sending frames to Device B. Let us assume

that the window size is seven and the window is initially located on

data frames D0 to D6. A initiate the transmission with its first frame
D0 followed by frames D1, D2 etc. A can send frames up to D6

without getting any acknowledgement from B.

While A is in the process of sending D2, it receives an

acknowledgement RR2 from B. A slide the window by two frames

deleting the copies of D0 and D1 from the window. Data frames D2

to D8 now occupy the window and frames up to D8 can be sent

without waiting for the acknowledgement.

At the receiving end B accepts D0 and D1 data frames. It releases

RR2 acknowledging receipt of D0 and D1, and removes these frames

from the window. The receive window that was at D0 to D6 slides to

D2 to D8. It next receives D2, D3 and D4 and releases RR5.

 Fig.4 Sliding Window Flow Control Mechanism

Error Control in Stop-and-Wait Protocol

 Adding a timer

 When data packet is lost

 The receiver would only send an ACK if the data were

correctly received
  After timeout, the sender sends the frame again.

 A lost data frame can be resent by using a timer.

 When an Acknowledgement is lost or delayed

 The sender’s timer eventually timeout

 The sender resends the same data frame

 After the data frame is received, the receiver sends

acknowledgment again.
Fig.5 Lost or damaged (Erroneous) Packet
Fig.6 Lost ACK
 Fig.7 timeout for ACK

Error Control in Sliding Window Protocol

In sliding window protocol, each frame is assigned a sequence

number and, therefore, an elaborate error control scheme is

feasible. The receiver keeps track of the sequence numbers of the

incoming data frames. If an out-of-sequence frame is received,

immediately, a request for retransmission of the missing frame is

sent. There are two choices for retransmission mechanism:

 Go-Back-N (GBN)

 Selective retransmission

Error Control Using Go-Back-N (GBN) Protocol

Go-Back-N Protocol is a Protocol, in which the sending process

continues to send a number of frames specified by a window size

even without receiving an ACK packet from the receiver. The

receiver process keeps track of sequence number of the next frame it

expects to receive, and sends that number with every ACK it sends.

The receiver will ignore any frame that does not have the exact

sequence number it expects -- whether that frame is a "past"

duplicate of a frame it has already ACK’ed or whether that frame is

a "future" frame past the lost packet it is waiting for. Once the

sender has sent all of the frames in its window, it will detect that all

of the frames since the first lost frame are outstanding, and will go
back to sequence number of the last ACK it received from the

receiver process and fill its window starting with that frame and

continue the process over again.

In GBN the receiver maintains a window of size 1. The receiver can,

therefore, accept only one data frame in sequence. Whenever it

notices a missing frame, it requests retransmission of the missing

data frame by sending Reject-N (REJ-N). If any other data frame,

other than frame N is received before frame N, the receiver discards

it. REJ-N indicates requests for retransmission of the all-data

frames starting with the frame N.

In this scheme missing frames are detected when out-of-sequence

frame is received. REJ are not sent on detection of content error in

the received data frame as the error could be in the sequence

number of the frame itself. The receiver waits for the next correct

frame and then declares the missing frame. REJ-N also

acknowledges receipt of data frames up to N-1.

Figure illustrates the GBN mechanism for window size of seven at

the sending end (A). The window size at the receiving end is always

one for GBN mechanism.

1. Loss of data frame

 A has its transmitted window at D0-D6. It sends D0.

 B has it’s received window at D0. It receives D0, replies with

RR1 and slides it’s received window to D1.

 A sends D1 which is lost in transit or is received with errors by

B.

 A receives RR1 and slides its window to data frames D1-D7. A

sends D2.

 On receipt of D2, B finds missing data frame D1. B discards D2

and sends REJ1.

 A sends D3. B discards D3.

 A receives REJ1. It sends D1.

 B accepts D1 and sends RR2.

  A sends D2. On receipt of RR2, A slides its window to D2-D8.

A sends D3.

 B accepts D2 and sends RR3.

A missing data frame is detected by the receiver when the next data

frame in sequence is received. If the lost frame was the last data

frame in the transmit window, the receiver will never respond with

REJ. Therefore, the sender maintains a timer. The timer is started

when the sender sends the last frame in the transmit window. After

timeout, it repeats all the frames in the window.

2. Loss of RR or REJ

If an RR is lost or delayed, the next RR released by the receiver

acknowledges all the previous data frames. To account for the

possibility of loss of REJ, the receiver maintains a timer and

retransmits the REJ after timeout.

 Fig. 8 GBN error control in sliding window protocol

Error Control Using Selective Retransmission

In selective retransmission, the receiver maintains a window of data

frames that it is ready to accept. The receive window size is usually

same as transmit window size. Whenever the receiver detects a

missing data frame, it requests retransmission of the missing data

frame by sending a Selective Reject (SREJ-N). N is the sequence

number of the missing data frame. On receipt of SREJ-N, the

sending end retransmits frame N and then it continues with the

outgoing transmission. The receiver accepts the succeeding data

frames meanwhile if they are received, When the data frame N is

received, it arranges all the frames in proper sequence, receives the

user data and hand it over to the next upper layer.

In this scheme missing frames are detected when out-of-sequence

frame is received. SREJ are not sent on detection of content error in

the received data frame as the error could be in the sequence

number of the frame itself. The receiver waits for the next correct

frame and then declares the missing frame. SREJ-N also

acknowledges receipt of data frames up to N-1.

1. Loss of a data frame

 A has its transmitted window at D0-D6. It sends D0.

 B has it’s received window at D0-D6. It receives D0,

replies with RR1, and slides it’s received window to D1-

D7.

 A sends D1 which is lost in transit or is received with

errors by B.

 A receives RR1 and it slides window to data frames D1-

D7. A sends D2.

 B accepts D2. But it finds missing data frame D1. It sends

SREJ1. After sending a SREJ1, B cannot send RR till it

receives the missing data frame D1 because sending RR3

means receipt of all earlier frames.

 A sends D3. B accepts it.

 A receive SREJ1. It sends D1.

 B accepts D1 and replies with RR4 acknowledging receipt

of D1, D2 and D3. B slides it’s received window to D4-

D10.
  After sending D1, A continues with sending next data

frame D4. A receives RR4 and slides its window to D4-

D10.

 B accepts D4, and release RR5 and slides its receive

window to D5-D11.

A missing data frame is detected by the receiver when the next data

frame in sequence is received. If the lost frame was the last data

frame in the transmit window, the receiver will never respond with

SREJ. Therefore, the sender maintains a timer. The timer is started

when the sender sends the last frame in the transmit window. After

timeout, it repeats all the frames in the window.

2. Loss of RR or SREJ

If an RR is lost or delayed, the next RR released by the

receiver acknowledges all the previous data frames. Therefore,

the operation is unaffected. To account for the possibility of

loss of REJ, the receiver maintains a timer. It is started as soon

as SREJ is released. If the required data frame is not received

within timeout, SREJ is again sent by the receiver.

Fig. 9 Selective retransmission error control in sliding window protocol