Go-Back-N (GBN)

In a Go-Back-N (GBN) protocol, the sender is allowed to transmit several packets (when available)

without waiting for an acknowledgment, but is constrained to have no more than some maximum

allowable number, N, of unacknowledged packets in the pipeline. We describe the GBN protocol in

some detail in this section. Figure 2 shows the sender's view of the range of sequence numbers in a

GBN protocol. If we describe base to be the sequence number of the oldest unacknowledged packet

and nextseqnum to be the smallest unused sequence number (that is, the sequence number of the

currently in the pipeline (particularly, the packet with sequence number base) has been acknowledge.

As suggested by Figure 2, the range of permissible sequence numbers for transmitted but not yet

acknowledged packets can be viewed as a window of size N over the range of sequence numbers. As

the protocol operates, this window slides forward over the sequence number space. Therefore, N is

often referred to as the window size and the GBN protocol itself as a sliding-window protocol. You

might be wondering why we would even limit the number of outstanding, unacknowledged packets to

In fact, a packets sequence number is carried in a fixed-length field in the packet header. If k is the

number of bits in the packet sequence number field, the range of sequence numbers is thus [0,2k-1].

With a finite range of sequence numbers, all arithmetic involving sequence numbers must then be

done using modulo 2karithmetic. (That is, the sequence number space can be thought of as ring of size

2k, where sequence number 2k-1 is immediately followed by sequence number 0.) Recall that rdt3.0

had a 1-bit sequence number and a range of sequence numbers of [0,1]. We will see in "Connection-

Oriented Transport: TCP" that TCP has a 32-bit sequence number field, where TCP sequence numbers

count bytes in the byte stream rather than packets.

programming-language-based techniques for specifying protocols.

 Invocation from above. When rdt_send ( ) is called from above, the sender first checks to see

if the window is full, that is, whether there are N outstanding, unacknowledged packets. If the

window is not full, a packet is created and sent, and variables are appropriately updated. If the

window is full, the sender simply returns the data back to the upper layer, an implicit indication

that the window is full. The upper layer would most likely then have to try again later. In a real

implementation, the sender would presumably have either buffered (but not immediately

sent) this data, or would have a synchronization mechanism (for instance, a semaphore or a

flag) that would allow the upper layer to call rdt_send ( ) only when the window is not full.

 Receipt of an ACK. In our GBN protocol, an acknowledgment for a packet with sequence

number n will be taken to be a cumulative acknowledgment, indicating that all packets with a

acknowledged. Our sender in Figure 3 uses only a single timer, which can be thought of as a

timer for the oldest transmitted but not yet acknowledged packet. If an ACK is received but

there are still additional transmitted but not yet acknowledged packets, the timer is restarted.

If there are no outstanding, unacknowledged packets, the timer is stopped.

The receiver's actions in GBN are also simple. If a packet with sequence number n is received correctly

and is in order (that is, the data last delivered to the upper layer came from a packet with sequence

number n -1), the receiver sends an ACK for packet n and delivers the data portion of the packet to the

upper layer. In all other cases, the receiver discards the packet and resends an ACK for the most

recently received in-order packet. Note that since packets are delivered one at a time to the upper

layer, if packet k has been received and delivered, then all packets with a sequence number lower than

expected, but packet n + 1 arrives. Because data must be delivered in order, the receiver could buffer

(save) packet n + 1 and then deliver this packet to the upper layer after it had later received and

delivered packet n. However, if packet n is lost, both it and packet n + 1 will finally be retransmitted as

a result of the GBN retransmission rule at the sender. Therefore, the receiver can simply discard packet

n + 1. The advantage of this approach is the simplicity of receiver buffering - the receiver need not

buffer any out-of-order packets. Therefore, while the sender must maintain the upper and lower

bounds of its window and the position of nextseqnum within this window, the only piece of

information the receiver need maintain is the sequence number of the next in-order packet. This value

is held in the variable expectedseqnum, shown in the receiver FSM in Figure 4. Of course, the

disadvantage of throwing away a correctly received packet is that the subsequent retransmission of

Before closing our discussion of GBN, it is worth noting that an implementation of this protocol in a

protocol stack would likely have a structure similar to that of the extended FSM in Figure 3. The

implementation would also likely be in the form of various procedures that implement the actions to

be taken in response to the various events that can occur. In such event-based programming, the

various procedures are called (invoked) either by other procedures in the protocol stack, or as the

result of an interrupt. In the sender, these events would be (1) a call from the upper-layer entity to

invoke rdt_send( ), (2) a timer interrupt, and (3) a call from the lower layer to invoke rdt_rcv( ) when a

packet arrives.

We note here that the GBN protocol integrates almost all of the techniques that we will encounter

when we learn the reliable data transfer components of TCP in "Connection-Oriented Transport: TCP".