• 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

• 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)

A UML Timing Diagram

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.

• 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)}\)

• 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

• 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

• 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

• 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)}\)

• 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

• 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

• Assume a 3-bit sequence number
• Assume initial windows of size 7

• 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\))