Flow Control in Data Link Layer

We've established why flow control is necessary, analyzed sender-receiver speed dynamics, and explored buffer management strategies. Now we turn to the mechanisms—the specific protocols and procedures that implement flow control in practice.

Flow control mechanisms vary dramatically in complexity, efficiency, and applicability. From the simplest Stop-and-Wait protocol that restricts a sender to one outstanding frame, to sophisticated credit-based systems that can fully utilize multi-gigabit links, each mechanism represents a different point in the tradeoff space between simplicity, efficiency, and implementation cost.

In this page, we'll systematically examine each major flow control mechanism, understanding its operation, analyzing its efficiency, and identifying its appropriate use cases.

Stop-and-Wait is the simplest flow control mechanism: the sender transmits one frame, then waits for an acknowledgment (ACK) before transmitting the next. This fundamentally prevents overflow because the receiver has time to process each frame before the next arrives.

Protocol Operation

1. Sender transmits frame N
2. Sender waits (cannot send anything else)
3. Receiver processes frame N
4. Receiver sends ACK for frame N
5. Sender receives ACK
6. Sender transmits frame N+1
7. Repeat...

Why It Works for Flow Control

Stop-and-Wait inherently limits the sender's rate. The maximum transmission rate is:

$$R_{max} = \frac{L}{RTT + T_{proc}}$$

Where:

• L = Frame size in bits
• RTT = Round-trip time
• Tproc = Processing time at receiver

Even if the sender could transmit faster, it's blocked waiting for ACKs. This 'pacing' prevents receiver overflow.

Efficiency Analysis

The critical metric is link utilization—the fraction of time spent actually transmitting data versus waiting.

$$Utilization = \frac{T_{trans}}{T_{trans} + RTT}$$

Where:

• Ttrans = L/R = Transmission time for one frame
• RTT = Round-trip time (propagation + ACK transmission + processing)

Or, in terms of the propagation-bandwidth product:

$$U = \frac{1}{1 + 2a}$$

Where a = (propagation delay × bandwidth) / frame size = one-way BDP/frame size

This reveals the fundamental problem: as links get faster or longer, utilization plummets.

Sliding Window protocols solve Stop-and-Wait's efficiency problem by allowing multiple frames to be 'in flight' simultaneously. The sender maintains a window of sequence numbers it's allowed to transmit; the receiver controls flow by adjusting this window.

Core Concepts

Sender Window (Ws): Range of sequence numbers the sender may transmit without waiting for acknowledgment. As ACKs arrive, the window 'slides' forward.

Receiver Window (Wr): Range of sequence numbers the receiver will accept. Frames outside this range are discarded or cause errors.

Window Size: Maximum number of unacknowledged frames allowed. Larger window = more frames in flight = higher potential throughput.

Sequence Number Space: Typically 0 to 2^n - 1 for n-bit sequence numbers. Must be larger than window size to avoid ambiguity.

Flow Control via Window Adjustment

The receiver controls sending rate by adjusting the window it advertises:

• Large window advertised: Sender can have many frames in flight, high throughput
• Small window advertised: Sender is constrained, lower throughput
• Zero window: Sender must stop completely until window opens

Window Advertisement Process

1. Receiver includes window size in every ACK: 'I've received up to N, and you may have up to W frames outstanding'
2. Sender calculates usable window: min(advertised window, congestion window)
3. Sender transmits up to the usable window limit
4. As receiver processes frames and frees buffer space, it advertises larger window
5. As receiver's buffer fills, it advertises smaller window

Efficiency with Sliding Window

For window size W frames:

$$U = \begin{cases} 1 & \text{if } W \geq 1 + 2a \ \frac{W}{1 + 2a} & \text{if } W < 1 + 2a \end{cases}$$

Where a = propagation delay × bandwidth / frame size

This means: if the window is large enough to cover the BDP (plus one for the frame being sent), we achieve full utilization.

Ethernet PAUSE provides link-level flow control for full-duplex Ethernet. When a receiver's buffers approach exhaustion, it sends a PAUSE frame instructing the sender to stop transmission for a specified duration.

PAUSE Frame Structure

Pause Duration Calculation

Pause time is measured in 'quanta,' where 1 quantum = time to transmit 512 bits.

For 10 Gbps Ethernet:

• 1 quantum = 512 bits ÷ 10 Gbps = 51.2 ns
• Maximum pause (0xFFFF quanta) = 65,535 × 51.2 ns ≈ 3.36 ms

Protocol Operation

1. Receiver's buffer occupancy exceeds threshold
2. Receiver sends PAUSE frame with desired pause duration
3. Sender receives PAUSE, stops transmission
4. Sender waits specified duration or until PAUSE with 0 duration received
5. Sender resumes transmission

Advantages of PAUSE Frames

• Simple: Binary on/off control, easy to implement in hardware
• Fast: Operates at line speed, minimal processing delay
• Effective: Completely prevents overflow when properly configured
• Standard: Widely supported in networking equipment

Limitations of PAUSE Frames

• All-or-nothing: When PAUSE is asserted, ALL traffic stops—including latency-sensitive traffic that wasn't causing the problem
• Head-of-line blocking: High-priority traffic blocked because low-priority traffic filled buffers
• Congestion spreading: PAUSE can cascade backwards, spreading congestion through the network
• No prioritization: Cannot differentiate between traffic classes

When to Use PAUSE

• Point-to-point links between trusted devices
• Storage networks (iSCSI, NFS over Ethernet) where lossless operation is required
• FCoE (Fibre Channel over Ethernet) which mandates lossless Ethernet
• Situations where all traffic is equally important

Priority Flow Control (PFC) extends Ethernet PAUSE to support per-priority-class flow control. Instead of stopping all traffic, PFC can pause only specific priority classes while allowing others to continue.

The Problem PFC Solves

Consider a link carrying both storage traffic (must be lossless) and general data (can tolerate drops). With basic PAUSE:

• When storage traffic fills buffers, PAUSE stops everything
• Latency-sensitive data traffic is unnecessarily delayed
• When data traffic fills buffers, PAUSE stops everything
• Storage traffic performance degraded by unrelated congestion

PFC allows:

• Storage traffic: Priority 3, enabled for PFC (lossless)
• Data traffic: Priority 0, not enabled for PFC (lossy)
• Storage congestion triggers PAUSE only for priority 3
• Data traffic continues unaffected

PFC Frame Structure

PFC uses the same MAC Control frame type as PAUSE (0x8808) but with a different opcode:

Priority Enable Vector

An 8-bit bitmap indicating which priorities are being paused:

• Bit 0 = Priority 0
• Bit 1 = Priority 1
• ...
• Bit 7 = Priority 7

Each paused priority has its own timer, allowing independent control.

Data Center Bridging (DCB) Context

PFC is a key component of Data Center Bridging (DCB), a set of IEEE standards for lossless Ethernet in data centers:

• 802.1Qbb: Priority Flow Control (PFC)
• 802.1Qaz: Enhanced Transmission Selection (ETS) - bandwidth allocation
• 802.1Qau: Congestion Notification (QCN) - endpoint congestion management
• DCBX: Discovery and capability exchange protocol

Together, these enable 'converged' data center networks carrying storage, compute, and management traffic on shared Ethernet infrastructure.

PFC Best Practices

1. Limit PFC-enabled priorities: Enable only for traffic that truly requires lossless delivery (typically just 1-2 classes)
2. Configure headroom properly: Sufficient buffer for in-flight frames after PFC is sent
3. Monitor PFC statistics: High PFC pause counts may indicate congestion or misconfiguration
4. Avoid PFC deadlock: Circular buffer dependencies can cause permanent freezes (requires careful network design)

Credit-based flow control represents the most sophisticated approach to preventing receiver overflow. Instead of reactive PAUSE signals, the receiver proactively grants 'credits' representing permission to send a specific amount of data. The sender can only transmit when it has credits; credits are replenished as the receiver frees buffer space.

Core Mechanism

1. Receiver allocates buffer space for sender and issues initial credits
2. Credits represent bytes (or frames) the sender may transmit
3. Sender decrements credit counter with each transmission
4. When credits reach zero, sender must stop
5. Receiver issues new credits as it frees buffer space
6. Sender receives credits and can resume

Key Advantages

• Lossless by design: Sender cannot over-send if credits are properly managed
• Fine-grained control: Credits can be issued in precise amounts
• Works with long links: Credits account for BDP—receiver issues credits equal to buffer size plus BDP
• No head-of-line blocking: Can issue credits per-destination or per-class

Credit Sizing

For lossless operation, total credits issued must be:

$$Credits \geq Buffer_Size + BDP$$

Where BDP accounts for credits in transit from receiver to sender plus data in transit from sender to receiver.

Credit-Based in Practice: InfiniBand

InfiniBand High-Speed Interconnect uses credit-based flow control extensively:

Virtual Lanes (VLs):

• Up to 16 virtual lanes per link
• Each VL has independent credit pool
• Enables quality-of-service without head-of-line blocking

Credit Exchange:

• Receiver hardware tracks buffer availability
• Credits sent in 'Credit ACK' packets
• Sender maintains per-VL credit counters
• Hardware automatically stops transmission when credits exhausted

Guaranteed Lossless:

• Properly configured InfiniBand never drops frames due to congestion
• Critical for RDMA operations that bypass error recovery
• Enables 'cut-through' message passing without buffering

Credit-Based in Fibre Channel

Fibre Channel, the storage networking standard, uses Buffer-to-Buffer (BB) credits:

• Each port has BB credit count representing receive buffer frames
• Sender consumes credit with each frame sent
• Receiver returns credit with R_RDY primitive signal
• Link goes idle when credits exhausted
• Buffer space calculated for distance: longer links need more credits

Rate-based flow control takes a fundamentally different approach: instead of controlling how much data is outstanding, it controls the rate at which data is transmitted. The sender is limited to a specific transmission rate that the receiver can sustain.

Approach

1. Sender and receiver negotiate a transmission rate
2. Sender transmits at exactly that rate (using token bucket, leaky bucket, or similar)
3. Receiver can keep up because rate matches its capacity
4. No buffer overflow occurs (in steady state)

Rate Limiting Mechanisms

Token Bucket:

• Bucket holds 'tokens' representing permission to transmit
• Tokens arrive at fixed rate r
• Each byte/frame transmitted consumes a token
• Bucket has maximum capacity b (burst size)
• When bucket empty, transmission waits
• Allows short bursts up to b, sustained rate r

Leaky Bucket:

• Data enters bucket at variable rate
• Data leaves bucket at fixed rate r
• Bucket has maximum capacity b
• Smooths traffic to constant rate
• Excess data dropped (or queued) when bucket full

Rate Negotiation

For rate-based flow control to work, both parties must agree on the rate:

Explicit Negotiation:

• During connection setup, exchange rate capabilities
• Agree on rate = min(sender capability, receiver capability, link capacity)
• Used in ATM, MPLS with traffic engineering

Dynamic Adjustment:

• Start with initial rate
• Monitor for overflow signals or ACK patterns
• Increase rate when no congestion, decrease when detected
• Similar to TCP congestion control but at Layer 2

Quantized Congestion Notification (QCN)

IEEE 802.1Qau QCN implements rate-based flow control for Ethernet:

1. Congested switch generates Congestion Notification Messages (CNMs)
2. CNM sent to original traffic source (traced via MAC)
3. Source reduces transmission rate based on feedback intensity
4. Rate gradually increased when no further CNMs received
5. Provides proportional response—heavier congestion = larger rate reduction

Selecting the appropriate flow control mechanism requires understanding your specific requirements and constraints. Here's a systematic decision framework:

Decision Factors

1. Link characteristics: Speed, distance, error rate
2. Traffic type: Latency-sensitive, bulk, mixed
3. Loss tolerance: Lossless required or acceptable drops
4. Implementation complexity: Hardware vs. software, development cost
5. Interoperability: Standard protocols vs. proprietary
6. Multi-traffic-class: Need to differentiate traffic types

Common Combinations

Real-world systems often combine multiple mechanisms:

Enterprise Network (edges):

• Edge ports: No DLL flow control (rely on TCP)
• Storage ports: PFC for storage priority class
• Uplinks: PFC or no control depending on oversubscription

Data Center Spine-Leaf:

• Leaf-to-server: PFC for RoCE/iSCSI traffic
• Leaf-to-spine: Often no flow control (large buffers + ECN)
• Spine-to-spine: ECN-based congestion control

Storage Array Backend:

• InfiniBand fabric: Credit-based flow control
• FC connections: BB credit flow control
• Ethernet front-end: Standard TCP/IP or iSER with PFC

High-Frequency Trading:

• Kernel bypass NICs: Hardware flow control
• Ultra-low-latency switches: Cut-through with minimal buffering
• Often disable flow control entirely, rely on over-provisioning

We've examined the major flow control mechanisms used at the Data Link Layer, from simple Stop-and-Wait to sophisticated credit-based systems. Let's consolidate the key takeaways:

What's Next

The final page in this module examines feedback-based control in depth—how receivers communicate their state to senders, the design of feedback loops, and the stability considerations that determine whether flow control oscillates or converges smoothly. This completes our study of flow control at the Data Link Layer.