Reliable data transfer mechanisms in Computer Networks - Time & Space Complexity

Time Complexity: Reliable data transfer mechanisms

O(n)

Understanding Time Complexity

When sending data over a network, reliable transfer ensures all pieces arrive correctly. Analyzing time complexity helps us see how the process scales as data size grows.

We want to know how the number of steps changes when more data is sent.

Scenario Under Consideration

Analyze the time complexity of the following reliable data transfer process.

for each packet in data:
    send(packet)
    wait for acknowledgment
    if acknowledgment lost or error:
        resend(packet)

This code sends each packet and waits for confirmation before moving on, resending if needed.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sending each packet and waiting for its acknowledgment.
• How many times: Once per packet, with possible repeats if errors occur.

How Execution Grows With Input

As the number of packets increases, the total steps grow roughly in proportion to the number of packets sent and acknowledged.

Input Size (n)	Approx. Operations
10	About 10 sends plus acknowledgments
100	About 100 sends plus acknowledgments
1000	About 1000 sends plus acknowledgments

Pattern observation: The work grows steadily as more packets are sent, roughly one step per packet.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete reliable transfer grows linearly with the number of packets.

Common Mistake

[X] Wrong: "Resending packets does not affect overall time much because errors are rare."

[OK] Correct: Even a few resends add extra steps, increasing total time. If errors happen often, time can grow more than expected.

Interview Connect

Understanding how reliable transfer scales helps you explain network behavior clearly. This skill shows you can think about real-world systems and their efficiency.

Self-Check

"What if we send multiple packets before waiting for acknowledgments? How would the time complexity change?"

Practice

1. What is the main purpose of reliable data transfer in computer networks?

easy

A. To reduce the size of data packets

B. To ensure data arrives complete and without errors

C. To encrypt data for security

D. To increase the speed of data transmission

Solution

1. Step 1: Understand the goal of reliable data transfer

   Reliable data transfer aims to make sure data sent from one point reaches the other point correctly and fully.

2. Step 2: Compare options with this goal

   Only To ensure data arrives complete and without errors matches this goal by focusing on completeness and error-free delivery.

3. Final Answer:

   To ensure data arrives complete and without errors -> Option B

4. Quick Check:

   Reliable data transfer = complete, error-free data [OK]

Hint: Reliable means complete and correct data delivery [OK]

Common Mistakes:

• Confusing reliability with speed
• Thinking encryption is part of reliability
• Assuming data size reduction is reliability

2. Which of the following is a key feature of the Stop-and-Wait protocol?

easy

A. Sender waits for acknowledgment before sending next packet

B. Sender sends all packets without waiting

C. Receiver sends data back to sender

D. Packets are sent in random order

Solution

1. Step 1: Recall Stop-and-Wait protocol behavior

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

2. Step 2: Match this behavior to options

   Sender waits for acknowledgment before sending next packet correctly describes this waiting for acknowledgment step.

3. Final Answer:

   Sender waits for acknowledgment before sending next packet -> Option A

4. Quick Check:

   Stop-and-Wait = wait for ACK before next send [OK]

Hint: Stop-and-Wait means wait for ACK before next send [OK]

Common Mistakes:

• Thinking sender sends all packets at once
• Confusing receiver's role with sender's
• Assuming packets are sent randomly

3. Consider a Sliding Window protocol with window size 3. If the sender has sent packets 1, 2, and 3, and receives an acknowledgment for packet 1, which packets can it send next?

medium

A. Packets 4 and 5

B. Packets 4 only

C. Packets 2 and 3 again

D. Packets 5 and 6

Solution

1. Step 1: Understand Sliding Window with size 3

   The sender can have up to 3 unacknowledged packets sent at once.

2. Step 2: Analyze acknowledgment for packet 1

   Receiving ACK for packet 1 means the window slides forward by one, freeing space to send one more packet. Since packets 2 and 3 are still unacknowledged, the sender can send packets 4 and 5 to fill the window.

3. Final Answer:

   Packets 4 and 5 -> Option A

4. Quick Check:

   Sliding window size 3 allows 3 unacknowledged packets; after ACK 1, packets 2 and 3 remain unacknowledged, so 2 new packets (4 and 5) can be sent [OK]

Hint: ACK moves window; send as many as window size allows [OK]

Common Mistakes:

• Sending two packets after one ACK
• Resending already acknowledged packets
• Sending packets beyond window size

4. A sender using Stop-and-Wait protocol never receives an acknowledgment. What is the most likely problem?

medium

A. The receiver is sending acknowledgments for wrong packets

B. The sender is sending packets too fast

C. The acknowledgment packets are lost or delayed

D. The sender window size is too large

Solution

1. Step 1: Understand Stop-and-Wait behavior on lost ACKs

   If acknowledgments are lost or delayed, the sender waits or resends the same packet repeatedly.

2. Step 2: Evaluate options for no ACK received

   The acknowledgment packets are lost or delayed correctly identifies lost or delayed ACKs as the cause; other options do not fit Stop-and-Wait protocol behavior.

3. Final Answer:

   The acknowledgment packets are lost or delayed -> Option C

4. Quick Check:

   No ACK = lost/delayed ACK packets [OK]

Hint: No ACK means lost or delayed acknowledgment packets [OK]

Common Mistakes:

• Blaming sender speed in Stop-and-Wait
• Confusing window size with Stop-and-Wait
• Assuming receiver sends wrong ACKs

5. In a network using Sliding Window protocol, if the window size is 4 and the sender receives duplicate acknowledgments for packet 3, what should the sender do to ensure reliable data transfer?

hard

A. Stop sending packets until timeout occurs

B. Ignore duplicates and continue sending new packets

C. Increase the window size to 6

D. Resend packet 4 immediately to recover from possible loss

Solution

1. Step 1: Understand duplicate ACKs in Sliding Window

   Duplicate ACKs usually indicate a lost packet after the acknowledged one.

2. Step 2: Identify sender's response to duplicate ACKs

   The sender should resend the next expected packet (packet 4) immediately to recover lost data.

3. Step 3: Evaluate other options

   Ignoring duplicates risks data loss; increasing window size or stopping sending are not correct immediate responses.

4. Final Answer:

   Resend packet 4 immediately to recover from possible loss -> Option D

5. Quick Check:

   Duplicate ACKs = resend missing packet [OK]

Hint: Duplicate ACKs signal lost packet; resend it immediately [OK]

Common Mistakes:

• Ignoring duplicate acknowledgments
• Changing window size unnecessarily
• Waiting for timeout instead of fast resend