A Protocol Using Go-Back-N
In many communication scenarios, the assumption that the transmission time for a frame to reach the receiver, plus the time for the acknowledgment (ACK) to return, is negligible is often false. This is particularly true in high-latency environments, such as satellite communications. For instance, consider a 50-kbps satellite channel with a 500-millisecond round-trip propagation delay. If we attempt to send 1000-bit frames using a stop-and-wait protocol, the sender can be blocked for a significant portion of the time, leading to inefficient bandwidth utilization.
Example Scenario
In this example, at time ( t = 0 ), the sender starts transmitting the first frame. By ( t = 20 ) milliseconds, the frame has been completely sent. However, it does not arrive at the receiver until ( t = 270 ) milliseconds, and the acknowledgment does not return until ( t = 520 ) milliseconds. This results in the sender being blocked for approximately 96% of the time, utilizing only 4% of the available bandwidth.
To improve efficiency, we can relax the restriction that the sender must wait for an acknowledgment before sending another frame. By allowing the sender to transmit multiple frames before blocking, we can achieve better bandwidth utilization.
Bandwidth-Delay Product
To determine the appropriate number of frames (window size ( w )) that can be sent before blocking, we calculate the bandwidth-delay product (BD). This is given by:
[ BD = \text{Bandwidth (bits/sec)} \times \text{One-way transit time (sec)} ]
The window size ( w ) should be set to ( 2BD + 1 ). This allows the sender to continuously transmit frames, as acknowledgments for previous frames will arrive before the window becomes full.
For example, with a bandwidth of 50 kbps and a one-way transit time of 250 ms, the bandwidth-delay product is 12.5 kbits, or 12.5 frames of 1000 bits each. Thus, ( w = 2 \times 12.5 + 1 = 26 ) frames.
Utilization of the Link
The utilization of the link can be expressed as:
[ \text{Link Utilization} \leq \frac{w}{1 + 2BD} ]
This equation shows that a larger window size ( w ) is necessary when the bandwidth-delay product is large. If the delay is high, the sender will exhaust its window quickly, leading to inefficiencies.
Pipelining and Error Recovery
Pipelining allows multiple frames to be in transit simultaneously, but it introduces challenges in error recovery. If a frame is lost or damaged, the receiver must decide how to handle subsequent frames. Two primary strategies are available:
1.Go-Back-N Protocol: The receiver discards all subsequent frames after a lost or damaged frame and sends no acknowledgments for them. The sender must then retransmit all unacknowledged frames starting from the damaged one. This can lead to significant bandwidth wastage if errors are frequent.
2.Selective Repeat Protocol: The receiver buffers correctly received frames that follow a lost or damaged frame. When the sender times out, only the oldest unacknowledged frame is retransmitted. This approach is more efficient but requires more memory at the receiver.
illustrating the effect of an error when (a) the receiver’s window size is 1 and (b) the receiver’s window size is large.
Go-Back-N Protocol Implementation
The Go-Back-N protocol allows the sender to transmit multiple frames without waiting for an acknowledgment for each one. Below is a simplified implementation of the Go-Back-N protocol in C-like pseudocode: Click here
illustrating the simulation of multiple timers in software, showing the queued timeouts and the situation after the first timeout has expired.
Conclusion
The Go-Back-N protocol enhances the efficiency of data transmission over high-latency links by allowing multiple frames to be sent before requiring an acknowledgment. While it simplifies the sender’s operation, it also necessitates careful management of frame acknowledgments and retransmissions to handle errors effectively. This protocol is particularly useful in scenarios where the round-trip time is significant compared to the transmission time of frames.