Flow control (stop-and-wait, sliding window) in Computer Networks - Time & Space Complexity

Time Complexity: Flow control (stop-and-wait, sliding window)

O(n)

Understanding Time Complexity

When sending data over a network, flow control methods decide how fast data moves between sender and receiver.

We want to understand how the time to send many packets grows as the number of packets increases.

Scenario Under Consideration

Analyze the time complexity of sending packets using stop-and-wait and sliding window flow control.

// Stop-and-Wait flow control
for each packet in total_packets:
    send(packet)
    wait for acknowledgment

// Sliding Window flow control
window_size = W
while packets remain:
    send up to W packets without waiting
    wait for acknowledgments of sent packets
    slide window forward

This code shows two ways to send packets: one waits after each packet, the other sends many before waiting.

Identify Repeating Operations

Look at what repeats as we send packets.

• Primary operation: Sending packets and waiting for acknowledgments.
• How many times: Stop-and-wait waits after each packet, so it repeats send-and-wait for every packet. Sliding window sends multiple packets before waiting, repeating send-and-wait fewer times.

How Execution Grows With Input

As the number of packets grows, the total time to send them changes differently for each method.

Input Size (n)	Stop-and-Wait Approx. Operations	Sliding Window Approx. Operations
10	10 send-wait cycles	About 2-3 send-wait cycles (if window size ~4-5)
100	100 send-wait cycles	About 20-25 send-wait cycles
1000	1000 send-wait cycles	About 200-250 send-wait cycles

Pattern observation: Stop-and-wait grows linearly with packets. Sliding window reduces waiting by grouping packets, so it grows slower in practice.

Final Time Complexity

Time Complexity: O(n)

This means the total time to send packets grows roughly in direct proportion to the number of packets, but sliding window reduces waiting overhead.

Common Mistake

[X] Wrong: "Sliding window always sends packets instantly with no waiting, so it has zero delay regardless of packet count."

[OK] Correct: Even sliding window must wait for acknowledgments after sending a group of packets, so waiting still grows with total packets, just less often.

Interview Connect

Understanding how flow control affects sending time helps you explain network efficiency and design better communication protocols.

Self-Check

What if we increased the sliding window size to cover all packets at once? How would the time complexity change?

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