Question

Draw a timeline diagram for the sliding window algorithm with SWS = RWS = 4 frames for the following two situations. Assume the receiver sends a duplicate acknowledgement if it does not receive the expected frame. For example, it sends DUPACK[2] when it expects to see FRAME[2] but receives FRAME[3] instead. Also, the receiver sends a cumulative acknowledgment after it receives all the outstanding frames. For example, it sends ACK[5] when it receives the lost frame FRAME[2] after it already received FRAME[3], FRAME[4], and FRAME[5]. Use a timeout interval of about \(2 \times\) RTT. (a) Frame 2 is lost. Retransmission takes place upon timeout (as usual). (b) Frame 2 is lost. Retransmission takes place either upon receipt of the first DUPACK or upon timeout. Does this scheme reduce the transaction time? Note that some end-to-end protocols (e.g., variants of TCP) use a similar scheme for fast retransmission.

Short answer

In part (b), retransmission upon receiving the first DUPACK reduces transaction time compared to waiting for a timeout as in part (a).

Step-by-step solution

Understand Sliding Window Protocol Basics

In the sliding window algorithm, the sender can send multiple frames before needing an acknowledgment, up to the Sliding Window Size (SWS) limit. The Receive Window Size (RWS) dictates how many frames the receiver can buffer. Here, SWS and RWS are both set to 4.

Understand Cumulative Acknowledgement and DUPACK

The receiver sends cumulative acknowledgments for consecutive frames received without any loss. If a frame is lost but subsequent frames are received, the receiver sends duplicate acknowledgments (DUPACK) to indicate the expected next frame.

Draw Timeline Diagram for Part (a)

Frame 2 is lost. Retransmission occurs upon timeout. The sender sends FRAME[0], FRAME[1], FRAME[2], and FRAME[3]. Since FRAME[2] is lost, the receiver sends DUPACK[2] after receiving FRAME[3, 4]. After a timeout, the sender retransmits FRAME[2], and the receiver sends ACK[5] upon receiving it.Timeline:1. Sender sends FRAME[0], FRAME[1], FRAME[2], FRAME[3]2. Receiver sends ACK[0], ACK[1], DUPACK[2], DUPACK[2] (on receiving FRAME[3, 4])3. Timeout occurs, Sender retransmits FRAME[2]4. Receiver sends ACK[5] after receiving FRAME[2]

Draw Timeline Diagram for Part (b)

Frame 2 is lost. Retransmission occurs either upon receipt of the first DUPACK or timeout. The sender sends FRAME[0], FRAME[1], FRAME[2], and FRAME[3]. The receiver sends DUPACK[2] upon receiving FRAME[3]. The sender retransmits FRAME[2] immediately upon getting the first DUPACK.Timeline:1. Sender sends FRAME[0], FRAME[1], FRAME[2], FRAME[3]2. Receiver sends ACK[0], ACK[1], DUPACK[2]3. Sender retransmits FRAME[2] upon receiving first DUPACK4. Receiver sends ACK[5] upon receiving FRAME[2]

Analyze Retransmission Schemes

In part (b), retransmission occurs faster with the arrival of the first DUPACK[2], before waiting for a timeout, which significantly reduces the overall transaction time.

Key concepts

Cumulative Acknowledgement

Cumulative Acknowledgement, often referred to as Cumulative ACK, is a technique used in reliable communication protocols.
It ensures that a series of frames are acknowledged up to the highest received frame without any gaps.
This method simplifies the communication between the sender and receiver by reducing the number of ACKs.
For example, if the sender transmits FRAME[0], FRAME[1], FRAME[2], and FRAME[3], and they are all received successfully,
the receiver can send a single ACK[3] to indicate that all frames up to and including FRAME[3] have been received.
This prevents the sender from needing to get individual acknowledgments for each frame, making the communication process more efficient.

Benefits of Cumulative ACK:

• Reduces the amount of acknowledgment traffic between sender and receiver.


• Simplifies the sender’s job of keeping track of which frames have been received.


• Can lead to faster recovery if a single ACK can confirm the receipt of multiple frames.

In the sliding window algorithm described in this exercise, the receiver waits until it receives all sequential frames before sending a cumulative ACK.
If FRAME[0], FRAME[1], FRAME[2], and FRAME[3] are sent, and FRAME[2] is lost,
the receiver will wait until receiving FRAME[2] again to send a cumulative ACK for all frames up to FRAME[3].

DUPACK

In a reliable transmission protocol, a Duplicate Acknowledgment (DUPACK) is sent by the receiver when it receives an out-of-order frame.
This indicates to the sender that a frame was lost and needs to be retransmitted.
Duplication of acknowledgments serves as a signal that the receiver has received new data frames beyond the missing one but is still waiting for the expected frame.

How DUPACK Works:

• The receiver sends a DUPACK when it receives a later frame than what it expected.


• If FRAME[2] is lost, the receiver will send DUPACK[2] on receiving FRAME[3] or any subsequent frames.


• The sender, upon receiving DUPACK, can decide whether to retransmit the missing frame immediately.

For instance, if FRAME[0], FRAME[1], FRAME[2], and FRAME[3] are sent and FRAME[2] is lost,
on receiving the next frame (FRAME[3]), the receiver will send DUPACK[2] to indicate that it missed FRAME[2].
If fast retransmission is configured (as in part (b) of the exercise), the sender will retransmit FRAME[2] upon receiving the first DUPACK,
which can significantly reduce the time needed for recovery from packet loss compared to waiting for a timeout.

Timeout Interval

The timeout interval is a critical concept in reliable transmission protocols.
It's the duration that the sender waits for an acknowledgment from the receiver before resending a frame.
The timeout interval is often set to slightly more than twice the estimated Round-Trip Time (RTT) to account for potential delays in the network.
Setting an appropriate timeout interval is crucial for performance and reliability.

Importance of Timeout Interval:

• A very short timeout interval can lead to unnecessary retransmissions, causing network congestion.


• An overly long timeout interval can delay the recovery from lost frames, affecting the overall throughput.

In the exercise, the timeout interval is about twice the RTT.
This means if the sender does not receive an acknowledgment within this period, it will retransmit the lost frame.
For instance, if FRAME[2] is lost, the sender waits for a timeout period before retransmitting FRAME[2] (as seen in part (a) of the exercise).
In advanced retransmission schemes (like part (b)), receiving a DUPACK can trigger immediate retransmission, which helps optimize the timeout mechanism and improve performance.