- Forward


Flow Control
An Introduction


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Introduction
Back SMYC Forward
  • Purpose:
    • Ensure that the transmitter does not overwhelm the receiver
  • Assumptions:
    • Perfect channel (i.e., no errors)
  • Approaches:
    • Stop-and-Wait
    • Fixed Window
    • Sliding Window
Stop-and-Wait Flow Control
Back SMYC Forward
  • Overview:
    • The receiver indicates its readiness to receive the next frame by acknowledging the current frame
  • Process:
    • Transmitter transmits a frame
    • Receiver receives the frame
    • Receiver transmits an acknowledgment (ACK)
Analysis of Stop-and-Wait
Back SMYC Forward

A UML Timing Diagram

flow-control_stop-and-wait

Note: The arrows from Receiver to Transmitter should be parallel but the UML drawing tool that was used to create this figure has a bug.

Analysis of Stop-and-Wait (cont.)
Back SMYC Forward
  • Notation:
    • \(L\) denotes the length of the frame
    • \(R\) denotes the transmission rate
    • \(d_{\text{trans}} = L/R\) denotes the frame transmission delay (i.e., the amount of time to "put the frame on the wire")
    • \(d_{\text{prop}}\) denotes the propagation delay (which is related to the speed of light; 186 mi/millisec)
    • \(RTT = 2 \cdot d_{\text{prop}}\) denotes the round-trip propagation
    • \(d_{\text{ack}}\) denotes the ACK transmission delay
    • \(d_{\text{proc}}\) denotes the processing time
    • \(d_{\text{total}} = d_{\text{trans}} + RTT + d_{\text{ack}} + 2 \cdot d_{\text{proc}}\)
  • Simplifying Assumptions:
    • \(d_{\text{ack}} = 0\)
    • \(d_{\text{proc}} = 0\)
  • Utilization:
    • \(U = \frac{d_{\text{trans}}}{d_{\text{total}}}\)
  • Solving:
    • \(U = \frac{d_{\text{trans}}} {d_{\text{total}}} = \frac{d_{\text{trans}}} {d_{\text{total}}} \frac{\frac{1}{d_{\text{trans}}}} {{\frac{1}{d_{\text{trans}}}}} = \frac{1}{1 + \left(\frac{RTT}{d_{\text{trans}}}\right)}\)
Analysis of Stop-and-Wait (cont.)
Back SMYC Forward
  • An Obvious Observation:
    • Only one frame can be in transmission at a time
  • An Implication:
    • This is inefficient if the propagation delay is longer than the transmission delay
Improving the Performance of Stop-and-Wait
Back SMYC Forward
  • An Observation:
    • The propagation delay won't be larger than the transmission delay if the frame is large enough
  • Unfortunately:
    • The frame size isn't under "our" control
  • However:
    • We can have the same effect by sending/acknowledging multiple frames at a time
Fixed Window Flow Control
Back SMYC Forward
  • Overview:
    • The receiver indicates its readiness to receive the next group of frames by acknowledging the previous \(w\) frames
  • Process:
    • Transmitter and receiver agree on an initial window size \(w\)
    • Transmitter transmits \(w\) frames
    • Receiver receives the \(w\) frames
    • Receiver transmits an acknowledgment of \(w\) frames
Analysis of Fixed Window Flow Control
Back SMYC Forward
  • Simplifying Assumptions:
    • \(d_{\text{ack}} = 0\)
    • \(d_{\text{proc}} = 0\)
  • Total Time and Utilization:
    • \(d_{\text{total}} = \frac{1}{w}(w \cdot d_{\text{trans}} + RTT) = d_{\text{trans}} + \left(\frac{RTT}{w}\right)\)
    • \(U = \frac{d_{\text{trans}}}{d_{\text{total}}} = \frac{w}{w + \left(\frac{RTT}{d_{\text{trans}}}\right)}\)
Analysis of Fixed Window Flow Control (cont.)
Back SMYC Forward
  • An Obvious Problem:
    • The window size may be too big
  • An Improvement:
    • Allow the receiver to send an ACK before all \(w\) frames have been received
    • The sender can then use this information to decrease the size of the window
Sliding Window Flow Control
Back SMYC Forward
  • Getting Started:
    • Frames have a \(k\)-bit sequence number (i.e., frames numbers are in \([0, \ldots, 2^k-1]\))
    • Transmitter has a window indicating which frames it can transmit
    • Receiver has a window indicating which frames it will receive
    • Both windows are always smaller than \(2^k-1\)
  • Controlling Flow:
    • Receiver can send an ACK N message at any time indicating that all frames up to and including number \(N-1\) have been received
    • The transmitter uses this ACK (and the previous ACK) to adjust the size of its window
An Example of Sliding Window Flow Control
Back SMYC Forward
  • Assume a 3-bit sequence number
  • Assume initial windows of size 7
An Example of Sliding Window Flow Control (cont.)
Back SMYC Forward

Using a UML Sequence Diagram

flow-control_sliding-window
Analysis of Sliding Window Flow Control
Back SMYC Forward
  • The Ideal Approach:
    • Use the distribution of windows sizes and find the expected value
  • A Common Approach:
    • Worst-case analysis (i.e., use the smallest value of \(w\))
There's Always More to Learn
Back -