Flow control (stop-and-wait, sliding window) in Computer Networks - Deep Dive

Overview - Flow control (stop-and-wait, sliding window)

What is it?

Flow control is a technique used in computer networks to manage the rate of data transmission between two devices. It ensures that the sender does not overwhelm the receiver with too much data at once. Two common methods are stop-and-wait, where the sender waits for an acknowledgment after each packet, and sliding window, which allows multiple packets to be sent before waiting for acknowledgments.

Why it matters

Without flow control, a fast sender could flood a slower receiver, causing data loss and network congestion. This would lead to poor communication quality, delays, and wasted resources. Flow control keeps data flowing smoothly and efficiently, making sure both sender and receiver work well together.

Where it fits

Before learning flow control, you should understand basic data transmission and acknowledgments in networking. After mastering flow control, you can explore error control, congestion control, and advanced protocols like TCP that use these techniques.

Mental Model

Core Idea

Flow control balances data sending speed so the receiver can handle incoming data without being overwhelmed.

Think of it like...

Imagine a water faucet filling a glass: stop-and-wait is like filling one glass at a time and waiting for it to be emptied before filling the next; sliding window is like filling several glasses at once before checking if they are emptied.

Sender Side                      Receiver Side
┌───────────────┐               ┌───────────────┐
│ Send Packet 1 │──────────────▶│ Receive Packet 1│
│ Wait for ACK  │◀─────────────│ Send ACK 1     │
└───────────────┘               └───────────────┘

Sliding Window Example:
[Packet 1][Packet 2][Packet 3][Packet 4]
  ↓        ↓        ↓        ↓
Receiver accepts multiple packets before sending ACKs.

Build-Up - 6 Steps

1

Foundation

Basic concept of flow control

Concept: Flow control prevents data loss by matching sender speed to receiver capacity.

When two devices communicate, the sender might send data faster than the receiver can process. Flow control is the method that makes the sender pause or slow down to avoid overwhelming the receiver.

Result

Data is transmitted without overwhelming the receiver, reducing errors and lost packets.

Understanding that uncontrolled data flow causes errors helps appreciate why flow control is essential for reliable communication.

2

Foundation

Stop-and-wait flow control basics

Concept: Stop-and-wait sends one packet and waits for acknowledgment before sending the next.

In stop-and-wait, the sender transmits a single data packet and then stops to wait for an acknowledgment from the receiver. Only after receiving this acknowledgment does the sender send the next packet.

Result

Simple and reliable, but can be slow because the sender waits after every packet.

Knowing this method's simplicity helps understand its limitations in high-speed or long-distance networks.

3

Intermediate

Sliding window flow control introduction

🤔Before reading on: do you think sliding window sends packets one-by-one or multiple at once? Commit to your answer.

Concept: Sliding window allows sending multiple packets before waiting for acknowledgments, improving efficiency.

Instead of waiting for each packet's acknowledgment, sliding window lets the sender send several packets up to a set window size. The receiver acknowledges received packets, and the sender slides the window forward to send more.

Result

Higher data throughput and better use of network capacity compared to stop-and-wait.

Understanding this method reveals how networks achieve faster data transfer without losing control.

4

Intermediate

Window size and its impact

🤔Before reading on: does increasing window size always improve performance? Commit to yes or no.

Concept: Window size controls how many packets can be sent before waiting; it affects speed and reliability.

A larger window size means more packets sent before waiting for acknowledgment, which can increase speed. However, if the window is too large, it may cause congestion or overwhelm the receiver.

Result

Choosing the right window size balances speed and network stability.

Knowing the trade-off helps optimize network performance and avoid bottlenecks.

5

Advanced

Handling lost or delayed packets

🤔Before reading on: do you think sliding window automatically recovers lost packets without extra steps? Commit to yes or no.

Concept: Flow control methods include mechanisms to detect and recover lost or delayed packets.

Both stop-and-wait and sliding window use timeouts and retransmissions. If an acknowledgment is not received in time, the sender resends the packet. Sliding window protocols often use sequence numbers to track packets and acknowledgments.

Result

Reliable data transfer even with network errors or delays.

Understanding error recovery within flow control shows how networks maintain data integrity.

6

Expert

Sliding window in real protocols like TCP

🤔Before reading on: do you think TCP uses fixed or dynamic window sizes? Commit to your answer.

Concept: TCP uses a dynamic sliding window that adjusts based on network conditions for optimal flow control.

TCP's sliding window size changes during communication depending on factors like network congestion and receiver capacity. This adaptive approach maximizes throughput while preventing overload.

Result

Efficient, reliable, and adaptive data transmission in real-world networks.

Knowing TCP's dynamic window management reveals how flow control adapts to complex network environments.

Under the Hood

Flow control works by coordinating sender and receiver states using acknowledgments and sequence numbers. The sender maintains a window of packets it can send without acknowledgment. The receiver tracks received packets and sends acknowledgments to inform the sender which packets arrived successfully. Timeouts trigger retransmissions if acknowledgments are missing. This coordination prevents buffer overflow at the receiver and manages network congestion.

Why designed this way?

Early networks had limited processing and memory capacity, so simple methods like stop-and-wait were used first. As networks grew faster and more complex, sliding window was designed to improve efficiency by allowing multiple packets in transit. The design balances simplicity, reliability, and performance, evolving to adapt to varying network conditions.

Sender Buffer
┌───────────────┐
│ Packet 1      │
│ Packet 2      │
│ Packet 3      │
│ Packet 4      │
└───────────────┘
      │
      ▼
[Window Size = 3]
Packets sent: 1, 2, 3
Waiting for ACKs...

Receiver Buffer
┌───────────────┐
│ Packet 1      │◀ ACK 1 sent
│ Packet 2      │◀ ACK 2 sent
│ Packet 3      │◀ ACK 3 sent
└───────────────┘

Sender slides window forward to send Packet 4.

Myth Busters - 4 Common Misconceptions

Quick: Does stop-and-wait send multiple packets before waiting for ACK? Commit yes or no.

Common Belief: Stop-and-wait can send several packets before waiting for acknowledgments.

Reality: Stop-and-wait sends only one packet at a time and waits for its acknowledgment before sending the next.

Why it matters: Believing otherwise leads to expecting high speed from stop-and-wait, causing confusion when performance is slow.

Quick: Does increasing sliding window size always improve network speed? Commit yes or no.

Common Belief: A bigger sliding window always means faster data transfer.

Reality: Too large a window can cause congestion and overwhelm the receiver, reducing performance.

Why it matters: Ignoring this can cause network slowdowns and packet loss, harming communication quality.

Quick: Does sliding window automatically fix all lost packets without retransmission? Commit yes or no.

Common Belief: Sliding window flow control alone guarantees no lost packets without extra mechanisms.

Reality: Sliding window requires timeouts and retransmissions to recover lost packets; flow control manages rate, not error correction alone.

Why it matters: Assuming flow control fixes all errors can lead to missing necessary error handling, causing data loss.

Quick: Is TCP's sliding window size fixed during a connection? Commit yes or no.

Common Belief: TCP uses a fixed sliding window size throughout the connection.

Reality: TCP dynamically adjusts its window size based on network conditions to optimize flow control.

Why it matters: Thinking the window is fixed prevents understanding TCP's adaptability and efficiency.

Expert Zone

1

Sliding window protocols often use cumulative acknowledgments, which acknowledge all packets up to a certain point, reducing overhead.

2

The choice of window size in sliding window protocols is influenced by the bandwidth-delay product, a measure of network capacity and latency.

3

TCP's flow control interacts closely with congestion control, making window size adjustments complex and dynamic.

When NOT to use

Stop-and-wait is inefficient for high-speed or long-distance networks due to waiting after each packet; sliding window is preferred. However, in very simple or low-resource systems, stop-and-wait may still be used. For networks with highly variable delays or errors, advanced protocols with selective acknowledgments or error correction may be better.

Production Patterns

In real networks, TCP uses sliding window with dynamic sizing and congestion control to optimize throughput. Protocols like HDLC and PPP implement sliding window for reliable link-layer communication. Stop-and-wait is sometimes used in simple embedded systems or initial protocol designs where simplicity is key.

Connections

Congestion control

Flow control manages sender-receiver speed, while congestion control manages overall network traffic load.

Understanding flow control helps grasp how networks prevent receiver overload, which complements congestion control's role in avoiding network-wide overload.

Producer-consumer problem (computer science)

Both involve managing the rate of production and consumption to avoid overflow or underflow.

Recognizing flow control as a producer-consumer synchronization problem clarifies its purpose in balancing data flow.

Traffic lights in road systems

Traffic lights control vehicle flow to prevent congestion, similar to how flow control regulates data packets.

Seeing flow control like traffic management reveals its role in orderly, efficient movement through a shared resource.

Common Pitfalls

#1 Sending packets continuously without waiting for acknowledgments in stop-and-wait.

Wrong approach:

Send Packet 1
Send Packet 2
Send Packet 3
// No waiting for ACKs

Correct approach:

Send Packet 1
Wait for ACK 1
Send Packet 2
Wait for ACK 2
Send Packet 3
Wait for ACK 3

Root cause:

Misunderstanding that stop-and-wait requires waiting after each packet to ensure reliable delivery.

#2 Setting sliding window size too large for the receiver's buffer.

Wrong approach:

Window size = 1000 packets
Sender floods receiver buffer

Correct approach:

Window size = receiver buffer capacity (e.g., 10 packets)
Sender respects receiver limits

Root cause:

Ignoring receiver capacity leads to buffer overflow and packet loss.

#3 Assuming acknowledgments arrive instantly and never get lost.

Wrong approach:

Sender never retransmits packets after sending once.

Correct approach:

Sender uses timeout to retransmit if ACK not received in time.

Root cause:

Overlooking network delays and losses causes unreliable communication.

Key Takeaways

Flow control ensures the sender does not overwhelm the receiver by managing data transmission speed.

Stop-and-wait is simple but inefficient for fast or long-distance networks because it waits after every packet.

Sliding window improves efficiency by allowing multiple packets to be sent before waiting for acknowledgments.

Choosing the right window size balances speed and reliability, preventing congestion and data loss.

Real-world protocols like TCP use dynamic sliding windows to adapt flow control to changing network conditions.

Practice

1. Which flow control method sends one packet and waits for an acknowledgment before sending the next?

easy

A. Stop-and-Wait

B. Sliding Window

C. Multiplexing

D. Routing

Solution

1. Step 1: Understand Stop-and-Wait flow control

   Stop-and-Wait sends one packet and waits for an acknowledgment before sending the next packet.

2. Step 2: Compare with other methods

   Sliding Window sends multiple packets before waiting, while Multiplexing and Routing are unrelated to flow control.

3. Final Answer:

   Stop-and-Wait -> Option A

4. Quick Check:

   One packet at a time = Stop-and-Wait [OK]

Hint: One packet then wait means Stop-and-Wait [OK]

Common Mistakes:

• Confusing Sliding Window with Stop-and-Wait
• Thinking Multiplexing is a flow control method
• Mixing routing with flow control

2. Which of the following correctly describes the sliding window flow control method?

easy

A. Sends one packet and waits for acknowledgment

B. Sends multiple packets before waiting for acknowledgment

C. Sends packets without any acknowledgment

D. Sends packets only after a timeout

Solution

1. Step 1: Recall sliding window behavior

   Sliding Window sends multiple packets before waiting for acknowledgment to improve speed.

2. Step 2: Eliminate incorrect options

   Sends one packet and waits for acknowledgment describes Stop-and-Wait. The other options do not describe standard flow control methods.

3. Final Answer:

   Sends multiple packets before waiting for acknowledgment -> Option B

4. Quick Check:

   Multiple packets sent = Sliding Window [OK]

Hint: Multiple packets sent before wait means Sliding Window [OK]

Common Mistakes:

• Choosing Stop-and-Wait for sliding window question
• Thinking no acknowledgment is used
• Confusing timeout with acknowledgment wait

3. Consider a sliding window protocol with window size 4. If the sender has sent packets 1, 2, 3, and 4, but only packets 1 and 2 are acknowledged, which packets can the sender send next?

medium

A. Packets 5 and 6

B. Packets 3, 4, and 5

C. Packets 5, 6, 7, and 8

D. Packets 3, 4, 5, and 6

Solution

1. Step 1: Understand sliding window acknowledgments

   Packets 1 and 2 are acknowledged, so the window slides forward by 2 packets.

2. Step 2: Calculate new window range

   Window size is 4, so after acknowledging 1 and 2, sender can send packets 5 and 6 (next two packets).

3. Final Answer:

   Packets 5 and 6 -> Option A

4. Quick Check:

   Window slides by acknowledged packets = Packets 5 and 6 [OK]

Hint: Window slides by acknowledged packets count [OK]

Common Mistakes:

• Trying to resend unacknowledged packets
• Sending too many packets beyond window size
• Not sliding window after acknowledgments

4. A stop-and-wait protocol implementation is not receiving acknowledgments and keeps resending the same packet. What is the most likely cause?

medium

A. The sender is sending multiple packets at once

B. The sender window size is too large

C. The receiver is not sending acknowledgments

D. The network is using sliding window instead

Solution

1. Step 1: Analyze stop-and-wait behavior

   Stop-and-wait waits for acknowledgment before sending next packet; no acknowledgment causes resending.

2. Step 2: Identify cause of no acknowledgment

   If acknowledgments are missing, likely the receiver is not sending them or they are lost.

3. Final Answer:

   The receiver is not sending acknowledgments -> Option C

4. Quick Check:

   No acknowledgment = Resend same packet [OK]

Hint: No ack means receiver not responding [OK]

Common Mistakes:

• Blaming sender window size in stop-and-wait
• Confusing sliding window with stop-and-wait
• Assuming multiple packets sent in stop-and-wait

5. In a sliding window protocol with window size 5, the sender transmits packets 1 to 5. Packets 2 and 3 are lost, but packets 1, 4, and 5 are acknowledged. Which packets should the sender retransmit next to maintain correct flow control?

hard

A. Packets 6 and 7

B. Packets 2, 3, and 6

C. Packets 2, 3, 4, and 5

D. Packets 2 and 3 only

Solution

1. Step 1: Identify lost packets

   Packets 2 and 3 are lost, so they need retransmission.

2. Step 2: Understand acknowledgments impact

   Packets 1, 4, and 5 are acknowledged, so only lost packets 2 and 3 must be resent before sending new packets.

3. Final Answer:

   Packets 2 and 3 only -> Option D

4. Quick Check:

   Retransmit lost packets only = Packets 2 and 3 [OK]

Hint: Retransmit only lost packets, not acknowledged ones [OK]

Common Mistakes:

• Retransmitting already acknowledged packets
• Sending new packets before lost ones
• Confusing lost packets with acknowledged packets