Window Concept - Sliding Window Protocol | OneNoughtOne

0/240

Computer NetworksSliding Window Protocol

Sliding Window Protocol

LevelIntermediate

Duration90 mins

TopicSliding Window Protocol

1 / 5

Window Concept

The Fundamental Bottleneck

In our study of Stop-and-Wait ARQ, we encountered a profound limitation: the sender must wait idle after transmitting each frame, unable to utilize the channel during the round-trip time. For high-bandwidth, high-latency links—such as satellite communications or transcontinental fiber connections—this protocol wastes the vast majority of available channel capacity.

Consider the mathematics: if a satellite link has a 500ms round-trip delay and we transmit 1000-bit frames at 1 Mbps, each frame takes 1ms to transmit but requires 500ms of waiting. The channel utilization is approximately 0.2%—meaning 99.8% of our expensive bandwidth goes unused.

This inefficiency motivated the development of a revolutionary concept: the sliding window.

What You Will Learn

By the end of this page, you will understand the window concept as the foundational abstraction enabling pipelined transmission. You'll grasp how windows allow multiple frames to be 'in flight' simultaneously, the relationship between window size and channel utilization, and the mathematical principles governing window-based protocols.

From Stop-and-Wait to Pipelining

To appreciate the window concept, we must first understand the core limitation of Stop-and-Wait at a deeper level.

The Stop-and-Wait Constraint:

In Stop-and-Wait ARQ, the sender operates under a strict invariant:

At most one unacknowledged frame exists at any time.

This invariant simplifies protocol design enormously—there's no ambiguity about which frame needs retransmission, and sequence numbers need only alternate between 0 and 1. However, it fundamentally couples the sender's transmission rate to the network's round-trip time (RTT).

Let's formalize this constraint mathematically:

Stop-and-Wait Timing Analysis
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
Stop-and-Wait Protocol Timing
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Time Components for Single Frame Transmission:
──────────────────────────────────────────────────────────────────────────────
Let:
  • T_tx = Frame transmission time = L / R
    where L = frame size (bits), R = link bandwidth (bps)
  
  • T_prop = Propagation delay (one-way) = d / v
    where d = link distance, v = propagation speed (~2×10⁸ m/s in fiber)
  
  • RTT = 2 × T_prop (Round-Trip Time, ignoring ACK transmission time)
 
Total Cycle Time per Frame:
──────────────────────────────────────────────────────────────────────────────
  T_cycle = T_tx + RTT = T_tx + 2×T_prop
 
Channel Utilization:
──────────────────────────────────────────────────────────────────────────────
  U = T_tx / T_cycle = T_tx / (T_tx + 2×T_prop)
 
Defining the Bandwidth-Delay Product 'a':
──────────────────────────────────────────────────────────────────────────────
  a = T_prop / T_tx = (R × d) / (L × v)
 
  This ratio 'a' represents the number of frames that could fit 
  "in the pipe" between sender and receiver.
 
Utilization in terms of 'a':
──────────────────────────────────────────────────────────────────────────────
  U = 1 / (1 + 2a)
 
Example Calculation (Satellite Link):
──────────────────────────────────────────────────────────────────────────────
  • Link bandwidth: R = 1 Mbps
  • Propagation delay: T_prop = 250 ms (geostationary satellite)
  • Frame size: L = 1000 bits
 
  T_tx = 1000 / 10⁶ = 1 ms
  a = 250 / 1 = 250
 
  U = 1 / (1 + 2×250) = 1 / 501 ≈ 0.00199 ≈ 0.2%
 
  Result: Only 0.2% of satellite bandwidth utilized!

The Bandwidth-Delay Product Problem

The parameter 'a' (bandwidth-delay product normalized by frame size) is the key to understanding Stop-and-Wait's inefficiency. When a >> 1, meaning the 'pipe' can hold many frames, Stop-and-Wait wastes most capacity. Modern networks—especially those spanning large distances or operating at high speeds—almost always have large 'a' values.

The Pipelining Insight:

The solution emerges from a simple observation: the channel is idle while waiting for acknowledgments, but nothing prevents us from sending additional frames during that time.

If the sender could transmit multiple frames before receiving any acknowledgments, it could 'fill the pipe' with data. Instead of one frame followed by idle waiting, we'd have continuous transmission.

This technique is called pipelining, and the mechanism that enables it is the sliding window.

The Window Abstraction

A window in the context of data link (and transport) protocols is a bounded range of sequence numbers representing frames that the sender is permitted to transmit without receiving acknowledgments.

This abstraction is remarkably powerful. Let's define it formally:

Sender Window Definition:

The sender window is the set of sequence numbers for frames that are either:

Already transmitted but not yet acknowledged, OR

Available for transmission

The window has a fixed size (denoted W or Ws), which represents the maximum number of unacknowledged frames permitted at any time.

Window Boundaries:

Window Base (or Left Edge): The sequence number of the oldest unacknowledged frame
Window Top (or Right Edge): The sequence number of the next frame to transmit
Window Size: The maximum allowed distance between base and top

Converting Mermaid diagram...

Window State Categories:

At any moment, sequence numbers fall into distinct categories:

Before the window: Frames already acknowledged (can be discarded)
Inside the window, sent: Frames transmitted, awaiting ACKs (must be buffered for retransmission)
Inside the window, unsent: Frames available for immediate transmission
Beyond the window: Frames that cannot be sent until the window advances

The Sliding Mechanism:

When an acknowledgment arrives for the frame at the window base, the window slides forward:

The acknowledged frame moves from 'inside window' to 'before window'
A previously 'beyond window' frame becomes 'inside window, unsent'
The sender can now transmit one additional frame

This sliding behavior gives the protocol its name: Sliding Window Protocol.

The Window as a Credit System

Think of the window size as 'transmission credits.' The sender starts with W credits. Sending a frame consumes one credit. Receiving an ACK restores one credit. The window ensures the sender never 'overspends'—never has more than W unacknowledged frames outstanding. This credit metaphor will become crucial when we study TCP's flow and congestion control.

Mathematical Foundations of Window Size

The window concept raises an immediate question: How large should the window be?

The answer depends on the goal. If we want to maximize channel utilization—keeping the channel fully busy—we need the window size to be at least large enough to 'fill the pipe' during a round-trip time.

Derivation of Optimal Window Size:

For 100% utilization, the sender must be able to transmit continuously without waiting. This requires that the time to send W frames equals or exceeds the round-trip time:

Window Size Derivation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
Optimal Window Size Derivation
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Condition for Full Utilization:
──────────────────────────────────────────────────────────────────────────────
  Time to send W frames ≥ Round-trip time
  
  W × T_tx ≥ RTT = 2 × T_prop
  
  W ≥ 2 × T_prop / T_tx = 2a
 
  Therefore: W ≥ 2a for 100% utilization
 
General Utilization Formula:
──────────────────────────────────────────────────────────────────────────────
  If W < 2a + 1:
    U = W / (2a + 1)
  
  If W ≥ 2a + 1:
    U = 1 (100% utilization)
 
Example Calculations:
──────────────────────────────────────────────────────────────────────────────
 
Scenario 1: Satellite Link
  • T_prop = 250 ms, T_tx = 1 ms
  • a = 250
  • For 100% utilization: W ≥ 2×250 + 1 = 501 frames
  
  With W = 100: U = 100 / 501 ≈ 20%
  With W = 250: U = 250 / 501 ≈ 50%
  With W = 501: U = 100%
 
Scenario 2: Local Area Network (LAN)
  • T_prop = 0.005 ms, T_tx = 0.1 ms
  • a = 0.05
  • For 100% utilization: W ≥ 2×0.05 + 1 = 1.1 → W = 2 frames
  
  Even Stop-and-Wait (W=1) achieves:
  U = 1 / 1.1 ≈ 91%
 
Scenario 3: High-Speed Long-Haul Fiber
  • Distance: 2000 km, Bandwidth: 10 Gbps, Frame: 1500 bytes
  • T_prop = 2000 km / (2×10⁵ km/s) = 10 ms
  • T_tx = (1500×8) / 10⁹ = 1.2 μs = 0.0012 ms
  • a = 10 / 0.0012 ≈ 8333
  • For 100% utilization: W ≥ 16,667 frames!
  
  This is why modern protocols use large windows and
  why TCP window scaling was introduced.

Window Size Requirements for Various Network Scenarios
Network Type	Typical RTT	Typical Bandwidth	Frame Size	Min W for 100% U
Local Ethernet (100m)	~0.01 ms	1 Gbps	1500 B	~2
Campus Network (1 km)	~0.1 ms	1 Gbps	1500 B	~10
Metro Network (100 km)	~1 ms	10 Gbps	1500 B	~100
Cross-continent (5000 km)	~50 ms	10 Gbps	1500 B	~42,000
Geostationary Satellite	~500 ms	100 Mbps	1500 B	~4,200

The Bandwidth-Delay Product Revisited

The product Bandwidth × RTT is called the bandwidth-delay product (BDP). It represents the maximum amount of data 'in flight' at any time. The optimal window size (in bytes) should equal or exceed the BDP. For a 10 Gbps link with 50ms RTT: BDP = 10⁹ × 0.05 = 62.5 MB. This is why high-speed networks require sophisticated buffer management.

Window Mechanics in Detail

Let's trace through the detailed mechanics of how a sliding window operates during normal data transfer. Understanding these mechanics is essential for grasping the more complex Go-Back-N and Selective Repeat protocols.

Sender Variables:

The sender maintains several critical state variables:

SND.WND (Send Window Size): The maximum number of unacknowledged frames
SND.BASE (Send Base): Sequence number of the oldest unacknowledged frame
SND.NEXT (Send Next): Sequence number of the next frame to send

Invariants the sender must maintain:

SND.BASE ≤ SND.NEXT ≤ SND.BASE + SND.WND

This invariant ensures that:

SND.NEXT is never behind SND.BASE (can't send already-acknowledged frames)
SND.NEXT never exceeds SND.BASE + SND.WND (can't overshoot the window)

Sender Window State Machine
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
Sender Window State Machine
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Initial State:
  SND.BASE = 0
  SND.NEXT = 0
  SND.WND  = W (window size)
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Event: Data Available to Send
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
  
  if SND.NEXT < SND.BASE + SND.WND:           // Window has space
      frame = create_frame(data, seq=SND.NEXT)
      buffer_for_retransmission(frame)        // Save copy
      transmit(frame)
      if SND.NEXT == SND.BASE:                // First unACKed frame
          start_timer()                       // Start retransmission timer
      SND.NEXT = SND.NEXT + 1
  else:
      buffer_data()                           // Wait for window to slide
      // Sender is blocked until ACK received
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Event: ACK Received for Sequence Number 'ack_num'
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
  // Interpretation depends on ACK semantics (cumulative vs. selective)
  
  For Cumulative ACK (acknowledges all frames up to ack_num - 1):
      if ack_num > SND.BASE:                  // Valid ACK
          old_base = SND.BASE
          SND.BASE = ack_num                  // Slide window forward
          release_buffers(old_base to ack_num - 1)  // Free memory
          
          if SND.BASE == SND.NEXT:            // All frames acknowledged
              stop_timer()
          else:
              restart_timer()                 // Reset for oldest unACKed
          
          // Window may now have space for new transmissions
          // Signal upper layer that new data can be accepted
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Event: Timeout (oldest unACKed frame)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
  // Retransmission strategy depends on protocol variant
  // Go-Back-N: Retransmit ALL frames from SND.BASE to SND.NEXT-1
  // Selective Repeat: Retransmit ONLY the timed-out frame

Visual Trace of Window Sliding:

Let's trace a sender with window size W=4, sending frames 0 through 7:

Window State Evolution (W=4)
Time	Event	SND.BASE	SND.NEXT	Window [BASE, BASE+W)	In-Flight Frames
T0	Initial	0	0	[0, 4)	None
T1	Send Frame 0	0	1	[0, 4)	{0}
T2	Send Frame 1	0	2	[0, 4)	{0, 1}
T3	Send Frame 2	0	3	[0, 4)	{0, 1, 2}
T4	Send Frame 3	0	4	[0, 4)	{0, 1, 2, 3}
T5	Blocked! Window full	0	4	[0, 4)	{0, 1, 2, 3}
T6	ACK 1 arrives	1	4	[1, 5)	{1, 2, 3}
T7	Send Frame 4	1	5	[1, 5)	{1, 2, 3, 4}
T8	ACK 3 arrives (cumulative)	3	5	[3, 7)	{3, 4}
T9	Send Frame 5	3	6	[3, 7)	{3, 4, 5}
T10	Send Frame 6	3	7	[3, 7)	{3, 4, 5, 6}

Window as a Pipeline

The window creates a continuous pipeline of frames. At T5, the sender is blocked because 4 frames are in-flight—the maximum allowed. When ACK arrives at T6, one 'slot' opens up, and the sender immediately fills it. The ideal state is having exactly W frames in-flight at all times.

Conceptual Significance of Windows

The window concept is more than a performance optimization—it represents a fundamental shift in how we think about reliable data transfer.

Decoupling Transmission from Acknowledgment:

Stop-and-Wait tightly couples these two activities: transmit → wait for ACK → transmit. The window decouples them, allowing the sender to work asynchronously:

Transmissions happen as fast as data is available (up to window size)
Acknowledgments are processed as they arrive
The two activities proceed in parallel

This decoupling is essential for any high-performance protocol.

Credit-Based Resource Management:

The window acts as a credit or permit system. The receiver, by advertising a certain window size, effectively says: "You may send me up to W frames before I tell you anything." This:

Limits the sender's burst size (preventing receiver buffer overflow)
Controls the amount of data in-transit (enabling resource planning)
Provides natural back-pressure (if receiver slows, window fills, sender blocks)

Key Properties Enabled by Windows

•High Utilization: Fill the bandwidth-delay product with data, achieving near-100% channel efficiency regardless of distance or latency.
•Flow Control: Window size can be set by the receiver to match its buffer capacity, preventing overwhelming slow receivers.
•Controlled Buffering: Both sender and receiver know the maximum memory required—sender buffers up to W frames for retransmission.
•Smooth Data Delivery: Continuous transmission leads to smoother, more predictable data arrival at the receiver.
•Scalability: The window abstraction scales from tiny embedded systems (W=1) to global networks (W=millions).
•Foundation for Higher Layers: TCP's sliding window extends this concept with dynamic sizing, selective acknowledgments, and congestion control.

Windows Everywhere

The sliding window concept appears throughout networking: HDLC, LAPB, and other data link protocols; TCP at the transport layer; even application protocols like HTTP/2 use flow control windows. Understanding this concept deeply at Layer 2 prepares you for its more complex manifestations higher in the stack.

Design Considerations and Trade-offs

Choosing an appropriate window size involves balancing multiple factors:

Memory Requirements:

Larger windows require more buffer memory:

Sender buffers up to W frames awaiting acknowledgment
Receiver may need to buffer out-of-order frames (Selective Repeat)

For a window of 16,000 frames × 1500 bytes = 24 MB per connection. High-speed servers handling thousands of connections face significant memory pressure.

Sequence Number Space:

Sequence numbers must distinguish all possible in-flight frames plus allow for wrap-around detection. The relationship between window size and sequence number bits differs by protocol:

Go-Back-N: Need 2^n ≥ W + 1 (sequence space > window size)
Selective Repeat: Need 2^n ≥ 2W (sequence space ≥ twice window size)

We'll explore these constraints in detail when studying each protocol variant.

Window Size Trade-offs
Consideration	Small Window	Large Window
Channel Utilization	Low (potentially)	High (up to 100%)
Sender Buffer Memory	Low	High
Receiver Buffer Memory	Low (GBN) / Medium (SR)	Medium (GBN) / High (SR)
Recovery from Loss	Fast (less to retransmit)	Slow (more to retransmit in GBN)
Latency Tolerance	Poor	Excellent
Sequence Number Bits	Fewer required	More required
Timer Management	Simple	More complex

Practical Window Sizing:

In practice, window sizes are typically:

Statically configured in simple data link protocols (HDLC window sizes of 7 or 127)
Dynamically negotiated in modern protocols (TCP window scaling)
Adaptively controlled based on congestion feedback (TCP congestion window)

The interplay between receive window (flow control), congestion window (congestion control), and available sequence number space creates rich protocol dynamics that we'll explore throughout this chapter.

Window Size Is Not Just Performance

While larger windows improve utilization, they also affect fairness (greedy senders can monopolize links), buffer requirements, and worst-case recovery time after failures. Protocol designers must balance raw throughput against these concerns.

Summary: The Window Concept

We've established the foundational understanding of windows in sliding window protocols. Let's consolidate the key insights:

Key Takeaways

•Stop-and-Wait is inefficient for high bandwidth-delay product networks — When 'a' (propagation delay / transmission time) is large, utilization drops dramatically.
•The window is a bounded set of sequence numbers the sender may use without waiting — It enables pipelining multiple frames through the network.
•Optimal window size equals the bandwidth-delay product — W ≥ 2a + 1 achieves 100% utilization.
•Windows slide forward as acknowledgments arrive — Each ACK opens space for one more transmission.
•The window provides flow control — The receiver can limit the sender's transmission rate by controlling window size.
•Buffer memory scales with window size — Larger windows require more memory at sender (and possibly receiver).
•Sequence number space must accommodate the window — Specific constraints depend on the protocol variant (Go-Back-N vs. Selective Repeat).

What's Next:

With the window concept established, we'll now examine the sender window in detail—its state variables, operations, and the algorithms that govern frame transmission. Understanding the sender perspective is crucial before examining how the receiver coordinates with it.

Page Complete

You now understand the window concept—the fundamental abstraction enabling efficient pipelined transmission in sliding window protocols. This concept underpins all modern reliable data transfer protocols, from HDLC to TCP. Next, we'll deep-dive into the sender window mechanics.