Go-Back-N Protocol (GBN)

Introduction

The Stop-and-Wait Protocol allows only one packet to be transmitted before waiting for an acknowledgment. As a result, much of the available bandwidth remains unused, especially in networks with a large bandwidth-delay product.

To improve transmission efficiency, the sender should be able to send multiple packets before receiving acknowledgments.

This concept is called pipelining.

In the Go-Back-N (GBN) Protocol, several packets can be transmitted continuously without waiting for individual acknowledgments. However, the receiver can accept and buffer only one packet at a time. If any packet is lost or corrupted, the sender retransmits that packet and all subsequent outstanding packets.

---

Pipelining

What is Pipelining?

Pipelining is a transmission technique in which a sender starts transmitting multiple packets before receiving acknowledgments for earlier packets.

Instead of waiting after every packet, several packets are kept "in transit" simultaneously.

Stop-and-Wait

Packet 0 ----->

          Wait

ACK <------

Packet 1 ----->

Only one packet travels through the network.

---

Go-Back-N

Packet 0 ----->

Packet 1 ----->

Packet 2 ----->

Packet 3 ----->

Packet 4 ----->

Many packets travel simultaneously.

This keeps the communication channel busy and improves efficiency.

---

What is Go-Back-N Protocol?

Go-Back-N (GBN) is a connection-oriented sliding window protocol that allows the sender to transmit multiple packets continuously without waiting for acknowledgments.

The receiver accepts only the next expected packet. Any packet received out of order is discarded.

If a packet is lost, the sender goes back and retransmits the lost packet and all outstanding packets that follow it. This behavior gives the protocol its name Go-Back-N.

---

Characteristics of Go-Back-N

• Connection-oriented protocol
• Sliding window protocol
• Supports pipelining
• Provides flow control
• Provides error control
• Uses cumulative acknowledgments
• Sender window size = 2ᵐ − 1 (maximum)
• Receiver window size = 1
• Uses one timer (for the oldest outstanding packet)

---

Layout of Go-Back-N Protocol

Unlike Stop-and-Wait, several packets and acknowledgments can be present in the network simultaneously.

---

Sequence Numbers

As in Stop-and-Wait, every packet is assigned a sequence number.

The sequence numbers are represented using m bits.

Therefore,

Number of sequence numbers

$$0,1,2,\dots ,(2^{𝑚}-1)$$

The numbering follows modulo $2^{𝑚}$arithmetic.

Example

If m = 3

0 1 2 3 4 5 6 7 0 1 2 3 ...

---

Acknowledgment Numbers

In Go-Back-N, acknowledgments are cumulative.

This means that an acknowledgment confirms all correctly received packets up to a particular sequence number.

Instead of acknowledging every packet individually, the receiver acknowledges the next packet expected.

Example

Suppose the receiver has successfully received packets

0 1 2 3 4 5 6

It sends

ACK = 7

Meaning

Packets 0–6 received successfully.

Now send Packet 7.

Thus,

ACK = 7 acknowledges

0
1
2
3
4
5
6

simultaneously.

---

Send Window

The send window is an imaginary box that contains the sequence numbers of packets that can be transmitted.

The maximum size of the send window is

$$2^{𝑚}-1$$

For example,

If

m = 3

Maximum window size

2³−1=7

The sender can therefore transmit

Packet0
Packet1
Packet2
Packet3
Packet4
Packet5
Packet6

without waiting for acknowledgments.

---

Regions of the Send Window

The send window is divided into four regions.

Region 1 – Acknowledged Packets

Already acknowledged.

Copies are removed.

6 7

---

Region 2 – Outstanding Packets

Sent

But ACK not received.

0 1 2 3

---

Region 3 – Ready to Send

Inside the window

Not yet transmitted.

4 5 6

---

Region 4 – Cannot Be Sent

Outside the window.

Must wait until the window slides.

7 0 

Example

Acknowledged | Outstanding | Can Send | Cannot Send

Send Window Variables

The sender maintains three variables.

1. Sf (Send First)

Sequence number of the first outstanding packet.

---

2. Sn (Send Next)

Sequence number assigned to the next packet.

---

3. Ssize

Size of the sender window.

Example

Sf =0

Sn =4

Window Size =7

Outstanding packets

0 1 2 3 

Next packet

4

---

Sliding the Send Window

Whenever a valid cumulative ACK arrives,

the sender slides the window.

Example

Before ACK

Outstanding

4 5 6 7 

Receiver sends

ACK=6

Meaning

Packets

4
5


received.

Window slided and is shown below 

Outstanding

6 7

The sender can now transmit new packets.

---

Receive Window

Unlike the sender,

the receiver window size is

1

Receiver accepts

Only

Next expected packet.

Suppose

Receiver expects

Packet3

If Packet 4 arrives

Discard Packet4

Send ACK3

The receiver waits until Packet 3 arrives.

---

Receiver Variable

Only one variable

Rn

It stores

Next expected packet.

Example

Rn=5

Receiver expects

Packet5

---

Timers

Although multiple packets may be outstanding, Go-Back-N uses only one timer.

The timer is associated with the first outstanding packet (Sf) because it is the oldest unacknowledged packet and will expire first if an error occurs.

---

Resending Packets

If the timer expires,

the sender retransmits

• the lost packet
• all outstanding packets

Example

Outstanding packets

3 4 5 6

Timer expires.

Sender retransmits

3
4
5
6

Hence the name

Go Back N

The sender goes back to the oldest unacknowledged packet and sends all outstanding packets again.

---

Send Window Size

The sender window size must satisfy

$$\boxed{{\displaystyle \text{Window Size}\le 2^{𝑚}-1}}$$

If the window size becomes equal to $2^{𝑚}$, duplicate packets may be mistaken for new packets after sequence numbers wrap around, causing incorrect delivery. Therefore, the sender window must always be less than $2^{𝑚}$.

We can now show why the size of the send window must be less than 2^m. As an example, we choose m = 2, which means the size of the window can be 2^m − 1, or 3. Figure 3.28 compares a window size of 3 against a window size of 4. If the size of the window is 3 (less than 2^m) and all three acknowledgments are lost, the only timer expires and all three packets are resent. The receiver is now expecting packet 3, not packet 0, so the duplicate packet is correctly discarded. On the other hand, if the size of the window is 4 (equal to 2^2) and all acknowledgments are lost, the sender will send a duplicate of packet 0. However, this time the window of the receiver expects to receive packet 0 (in the next cycle), so it accepts packet 0, not as a duplicate, but as the first packet in the next cycle. This is an error. This shows that the size of the send window must be less than 2^m.

---

Advantages of Go-Back-N

• Higher throughput than Stop-and-Wait.
• Better utilization of bandwidth.
• Supports pipelining.
• Simple receiver design (receiver window size = 1).
• Cumulative acknowledgments reduce ACK traffic.

---

Disadvantages of Go-Back-N

• Retransmits many correctly received packets after a single loss.
• Wastes bandwidth when errors occur.
• Receiver cannot buffer out-of-order packets.
• Performance decreases on noisy communication links.

---

Summary

• Go-Back-N (GBN) is a connection-oriented sliding window protocol that improves efficiency by allowing multiple packets to be transmitted before acknowledgments are received.
• It uses pipelining, cumulative acknowledgments, and a single timer for the oldest outstanding packet.
• The sender window can have a maximum size of 
  $2^{𝑚}-1$
• If a packet is lost or corrupted, the sender goes back to the oldest unacknowledged packet and retransmits all outstanding packets, which is why the protocol is called Go-Back-N.