flow control

Flow Control

Overview

flow control at the data link level

assume direct dedicated line between sender and receiver

goal : assure that sender does not overwhelm receiver

receiver may operate at much lower speed than sender
receiver may have limited buffer space

consider protocols that assume error-free transmission

extend those protocols to handle erroneous transmission

error correction is implemented by retransmission

roles of sender and receiver fixed for this discussion

The Players

frame is unit of data transmission

sender has frames to transmit and transmits at will

receiver accepts the frames at will

acknowledgement (ACK) is transmitted from receiver back to sender upon receipt of error-free frame

negative acknowledgement (NAK) is transmitted from receiver back to sender upon receipt of erroneous frame

Simple flow control protocol: Stop-and-Wait

assume (for now) error-free delivery

This sequence is repeated for every frame:

sender reads data from its network layer
sender assembles frame
sender transmits frame
receiver accepts frame
receiver passes data to its network layer
receiver transmits ACK to sender
sender accepts ACK

Note that frame N+1 is not transmitted until ACK for frame N is received

What is maximum bandwidth utilization?

Stop-and-Wait with error control

called ARQ (automatic repeat request)

sender must be prepared to retransmit (buffer the data frame)

Here are the bad things that can happen:

data frame damaged during transmission
data frame lost during transmission
ACK lost during transmission
NAK lost during transmission

Damaged Data Frame

Receiver: detects erroneous frame, responds with NAK rather than ACK

Sender: upon receipt of NAK, it retransmits last frame

Lost Data Frame

Receiver: can do nothing!

Sender: set timer upon transmit, then retransmit if timer expires before ACK/NAK received

Lost ACK frame

Sender: timer will expire because ACK not received. It assumes data frame lost and retransmit.

Receiver: receives duplicate frame! It must discard, then retransmit ACK. How does it know frame is duplicate?

Solution: each frame has sequence number. Alternating 0 and 1 will do. Sender appends sequence number to frame. Receiver attaches that number to ACK.

Lost NAK frame

Sender: timer will expire because NAK not received. It assumes data frame lost and retransmits.

Receiver: receives new copy of last frame. This is the frame it expected (it does not know the NAK was lost), so it accepts it.

To summarize, solution requires:

Timer: set when data frame transmitted, reset when ACK/NAK received.
Sequence number on each data frame, alternate 0 and 1.
Sequence number on each ACK, value is data frame number received.
Associated error control logic.

Note: ACK sequence number not utilized here, but necessary for generalized sliding window protocol.

Flow control protocol : Sliding Window

makes better utilization of bandwidth
sender can send out multiple frames from "window" of consecutive sequence numbers, before ACK received
ACK can cover more than one frame
stop-and-wait is sliding window of size 1.
Sequence #s: vital. total number of sequence numbers (SEQUENCE) is power of 2 (fully utilize frame bits)
Window size : max number of unACKed frames (may have to retransmit); SEQUENCE minus one. This will prevent ambiguity about which frame a sequence number refers to (if duplicate received).
Sequence number on a data frame: its frame number mod SEQUENCE.
Sequence number on an ACK frame: sequence number of next frame expected
Sequence number on a NAK frame: sequence number of damaged frame
assume SEQUENCE = n (sequence numbers range 0 to n-1)

Sender Window

represents: # frames that can be sent before ACK required.
(there are other equivalent interpetations, e.g."sent frames that have not been ACKed")
initially: n-1 frames ready to send
upon frame send: move lower edge of window up by 1.
upon ACK receive: move upper edge of window up by # frames ACKed (current ACK # minus previous ACK #, with wraparound if necessary).
upon NAK receive: serves as ACK for all unACKed frames prior to NAKed frame so adjust window accordingly, then retransmit NAKed frame

Receiver Window

represents: # frames that can be received before ACK required to be sent.
initially: n-1 empty frame buffers ready to receive
upon frame receive: move lower edge of window up by 1.
upon ACK send: move upper edge of window up by # frames ACKed (current ACK # minus previous ACK #, with wraparound if necessary).
upon NAK send: serves as ACK for all unACKed frames prior to NAKed frame so adjust window accordingly

Basic error-free sliding window operation

Sender: Sender keeps buffer of n-1 consecutive frames. As sender sends each frame without receiving ACK, the window (but not buffer) grows smaller and smaller until it goes to size zero. At this point, it cannot send any more frames: none of the last n-1 frames has been ACKed and therefore all must be available for possible retransmission (not a factor, for error-free transmission). Once ACK is received, additional frames can be obtained from network layer for transmission.

Receiver: Receiver starts with empty buffer with capacity for n-1 consecutive frames. Window gets smaller and smaller as each frame received without ACK being sent (represents the number of available buffer space). If all n-1 buffer frames filled, window had size zero. At this point, it cannot receive any more frames until it sends an ACK. With error-free transmission, there is not much incentive to ACK until receiver buffer full. This changes when errors are introduced.

Sliding Window with Errors

Two basic strategies: Go-Back-N, and Selective-Reject (Selective-Repeat)

Essence of Go-Back-N: if a data frame is damaged/lost, all frames since previous ACK are retransmitted. Receiver has to discard all subsequent frames until it gets a new copy of the one it needed.

Essence of Selective-Repeat: if a data frame is damaged/lost, only the damaged/lost frame is retransmitted. Makes better use of bandwidth, but requires more complex logic. For instance, receiver must keep frames which it received correctly after the erroneous one, leaving a gap in the buffer. With Go-Back-N, it will discard these in the knowledge that the sender will retransmit them.