FSMs (Finite State Machines) for the Go-Back-N (GBN) Protocol

The Finite State Machine (FSM) describes the behavior of the sender and receiver in the Go-Back-N (GBN) Protocol. Since GBN is a connection-oriented protocol, the sender and receiver are assumed to be in the established state before data transfer begins. The sender can be in either the Ready state or the Blocking state, whereas the receiver always remains in the Ready state.

---

Sender FSM

The sender starts in the Ready state, but thereafter it can be in one of the two states:

• Ready State
• Blocking State

The two sender variables are normally initialized as:

Sf = 0
Sn = 0

where:

• Sf = Sequence number of the first outstanding packet
• Sn = Sequence number of the next packet to be sent

---

1. Ready State

When the sender is in the Ready State, four events may occur.

(a) Request comes from the Application Layer

If a request comes from the application layer,

• The sender creates a packet with the sequence number set to Sn.
• A copy of the packet is stored.
• The packet is transmitted.
• The sender starts the only timer, if it is not already running.
• The value of Sn is incremented.

$$Sn=(Sn+1)\; \text{modulo }2^m$$

If the send window becomes full,

$$Sn=(Sf+Ssize)\; \text{modulo }2^m$$

the sender moves to the Blocking State.

---

(b) An Error-Free ACK Arrives

If an error-free ACK arrives with an ackNo corresponding to one of the outstanding packets,

• The sender slides the send window by setting

$$Sf=ackNo$$

• If all outstanding packets are acknowledged

$$ackNo=Sn$$

the timer is stopped.

• If some packets are still outstanding,

the timer is restarted.

---

(c) Corrupted ACK or Invalid ACK Arrives

If

• a corrupted ACK arrives, or
• an error-free ACK arrives whose ackNo is not related to any outstanding packet,

the ACK is simply discarded.

---

(d) Time-Out Occurs

If the timer expires,

• the sender resends all outstanding packets, and
• restarts the timer.

---

2. Blocking State

The sender enters the Blocking State when the send window becomes full.

In this state, the sender cannot send any new packets until acknowledgments are received.

Three events may occur.

---

(a) An Error-Free ACK Arrives

If an error-free ACK arrives with an ackNo corresponding to one of the outstanding packets,

• the sender slides the send window by setting

$$Sf=ackNo$$

• If all outstanding packets have been acknowledged

$$ackNo=Sn$$

the timer is stopped.

• Otherwise,

the timer is restarted.

After sliding the window, the sender moves back to the Ready State because space is now available in the send window.

---

(b) Corrupted ACK or Invalid ACK Arrives

If

• a corrupted ACK arrives, or
• an ACK whose ackNo does not correspond to any outstanding packet arrives,

the ACK is discarded.

---

(c) Time-Out Occurs

If the timer expires,

• the sender retransmits all outstanding packets, and
• restarts the timer.

---

Receiver FSM

The receiver is always in the Ready State.

The receiver uses only one variable:

Rn = 0

where Rn represents the sequence number of the next packet expected.

Three events may occur.

---

(a) Correct Packet Arrives

If an error-free packet with

seqNo = Rn

arrives,

• the message is delivered to the application layer.
• the receive window slides

$$Rn=(Rn+1)\; \text{modulo }2^m$$

• an acknowledgment is sent with

ackNo = Rn

This acknowledgment informs the sender about the next packet expected.

---

(b) Packet Outside the Window Arrives

If an error-free packet with a sequence number outside the receive window arrives,

• the packet is discarded, and
• an ACK with

ackNo = Rn

is sent again.

This tells the sender that the receiver is still waiting for the expected packet.

---

(c) Corrupted Packet Arrives

If a corrupted packet arrives,

• the receiver simply discards the packet.

No data is delivered to the application layer.

---

Summary of Sender FSM

State	Event	Action
Ready	Request from   application	Create packet, assign sequence number Sn, store a copy, send packet, start timer (if not running), increment Sn
Ready	Valid ACK arrives	Slide window (Sf = ackNo), stop or restart timer depending on outstanding packets
Ready	Corrupted/Invalid       ACK	Discard ACK
Ready	Timeout	Resend all outstanding packets and restart timer
Blocking	Valid ACK arrives	Slide window, stop/restart timer, move to Ready State
Blocking	Corrupted/Invalid   ACK	Discard ACK
Blocking	Timeout	Resend all outstanding packets and restart timer

---

Summary of Receiver FSM

State	Event	Action
Ready	Correct packet (seqNo = Rn)	Deliver message, slide receive window, send ACK (ackNo = Rn)
Ready	Packet outside receive                  window	Discard packet, resend ACK (ackNo = Rn)
Ready	Corrupted packet	Discard packet

---

Key Points to Remember

• The sender has two states: Ready and Blocking.
• The receiver has only one state: Ready.
• The sender maintains two variables: Sf (first outstanding packet) and Sn (next packet to send).
• The receiver maintains one variable: Rn (next expected packet).
• Only one timer is used, associated with the oldest outstanding packet.
• On a timeout, the sender goes back to the oldest unacknowledged packet and retransmits all outstanding packets, which is the defining characteristic of the Go-Back-N Protocol.