Go-Back-N Protocol | Baeldung中文网

1. Introduction

Go-Back-N and Selective Repeat protocols are fundamental sliding window protocols that help us better understand the key idea behind reliable data transfer in the transport layer of computer networks.

In this tutorial, we’ll describe how the Go-Back-N protocol works. Moreover, we’ll discuss the relationship between the window size and the sequence number space size as well as how the selection of affects the algorithm’s performance.

2. Go-Back-N

The sliding window (pipelined) protocols achieve utilization of network bandwidth by not requiring the sender to wait for an acknowledgment before sending another frame.

In Go-Back-N, the sender controls the flow of packets, meaning we’ve got a simple and dummy receiver. Therefore, we’ll start by discussing how the server handles data packets first.

2.1. The Sender

The sender has a sequence of frames to send. We assume a window size of . Furthermore, there exist two pointers to keep track of send base ( $send\_base$ ) and the next packet to send ( nextseqnum ).

GoBackN-4

3. Cumulative Acknowledgements and Sequence Numbers

The Go-Back-N protocol adopts the use of cumulative acknowledgments. That is, receiving acknowledgment for frame $\textbf{n}$ means the frames $\textbf{n-1}$ , $\textbf{n-2}$ , and so on are acknowledged as well. We denote such acknowledgments as ACK .

Let denote the maximum possible sequence number we use to mark the frames. Again assume we have a window size of .

Now, let’s imagine a simple scenario:

The sender sends the frames in the window, enumerating them from 0 to
As a response it receives ACK , marking frames , , and so on acknowledged
Then the sender sends the second set of frames, again enumerating them from 0 to
After that, the sender receives another ACK

In the sender’s perspective, what does the acknowledgment in the last step stand for? Did all the packets in the second batch got lost or sent successfully? If S = N , there is no way that the sender knows the real outcome. That’s why we must have strict inequality $\textbf{N}$ < $\textbf{S}$ .

4. Utilization and Window Size

As we stated before, pipelined protocols are an improvement over the stop-and-wait protocol. To achieve better network utilization, we have multiple frames “in-flight” between the sender and the receiver at a given time.

denotes the window size in Go-Back-N, which the sender is allowed to send before receiving an acknowledgment. Basically if N = 1 , we have a stop-and-wait implementation.

The maximum possible link utilization formula, disregarding any overheads is:

$[Utilization \leq \frac{N}{1 + 2 \times BD}]$

In the formula, is the bandwidth-delay product, representing how much data can be carried over the link at a given time. It’s calculated as the data link’s capacity multiplied by round-trip delay time.

Theoretically, we find the maximum possible $\textbf{N}$ by solving the equation above for $\textbf{Utilization = 1}$ . However, in practice, we need to use an even smaller $\textbf{N}$ value.

There are two main reasons for this.

First of all, we need to consider at which rate the receiver can process the packets arrived as well as having high network utilization.

If the receiver cannot cope up with processing the packets, it will drop them. In this case, the sender will be retransmitting the same packets over and over again, the successfully transmitted package rate will be inadequately low. Hence, achieving high utilization is meaningless.

The concept of preventing a fast sender from drowning a slow receiver in data is called flow control. Flow control enforces a smaller window size , concerning the receiver’s processing speed.

Second, though equally important is to limit the window size $\textbf{N}$ is congestion control. Too many packets being present in (a part of) the network cause packet delays and packet loss, which degrades performance. Indeed, a sender should respect each element in the network so that the overall network performance is utilized.

5. Conclusion

To sum up, the Go-Back-N protocol works for both the sender and the receiver side to ensure reliable data transfer.

We also discussed how the cumulative acknowledgments are enforcing us to use an value greater than and how to select a reasonable window size to achieve better utilization.

Persistence

REST