FSMs (Finite State Machines) for the Selective-Repeat (SR) Protocol
FSMs (Finite State Machines) for the Selective-Repeat (SR) Protocol
The Finite State Machine (FSM) describes the behavior of the sender and the receiver in the Selective-Repeat (SR) Protocol. The FSM of Selective Repeat is similar to that of Go-Back-N (GBN), but there are important differences.
The sender can be in one of two states:
- Ready State
- Blocking State
The receiver is always in the Ready State. The main difference from GBN is that the receiver can store out-of-order packets, and the sender acknowledges packets individually instead of using cumulative acknowledgments.
Sender FSM
The sender starts in the Ready State, but later it can be in one of the two states:
- Ready State
- Blocking State
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 Sn.
- A copy of the packet is stored.
- The packet is transmitted.
- If the timer is not running, the sender starts the timer.
- The value of Sn is incremented.
If the send window becomes full,
the sender moves to the Blocking State.
(b) Error-Free ACK Arrives
If an error-free ACK arrives with an ackNo corresponding to one of the outstanding packets,
- that packet is marked as acknowledged.
Unlike Go-Back-N,
the sender does not assume that previous packets are also acknowledged.
If
ackNo = Sf
the sender slides the window to the right until Sf points to the first unacknowledged packet.
This means that all consecutive acknowledged packets are removed from the sender window.
If there are still outstanding packets,
the timer is restarted.
Otherwise,
the timer is stopped.
(c) Corrupted ACK or Invalid ACK Arrives
If
- a corrupted ACK arrives, or
- an ACK that does not correspond to any outstanding packet arrives,
the ACK is simply discarded.
(d) Time-Out Occurs
If the timer expires,
the sender resends all unacknowledged packets currently present in the sender window and restarts the timer.
2. Blocking State
The sender enters the Blocking State when the sender window becomes full.
In this state, no new packets can be transmitted until space becomes available in the sender window.
Three events may occur.
(a) Error-Free ACK Arrives
If an error-free ACK corresponding to one of the outstanding packets arrives,
- the corresponding packet is marked as acknowledged.
If
ackNo = Sf
the sender slides the window to the right until Sf points to the first unacknowledged packet.
If the sender window slides,
the sender returns to the Ready State, because space is now available for transmitting new packets.
(b) Corrupted ACK or Invalid ACK Arrives
If
- a corrupted ACK arrives, or
- an ACK that does not correspond to any outstanding packet arrives,
the ACK is discarded.
(c) Time-Out Occurs
If the timer expires,
the sender retransmits all unacknowledged packets currently present in the sender window and restarts the timer.
Receiver FSM
The receiver in the Selective-Repeat Protocol is always in the Ready State.
Unlike Go-Back-N,
the receiver can accept packets that arrive out of order.
Instead of discarding them,
it stores them in its receive buffer until the missing packets arrive.
Three events may occur.
(a) Error-Free Packet Arrives Inside the Receive Window
If an error-free packet whose sequence number lies inside the receive window arrives,
the receiver performs the following operations.
Step 1
The packet is stored.
If it is a duplicate,
it is discarded.
Step 2
The receiver sends an acknowledgment
ACK = seqNo
Notice that
the ACK contains the sequence number of the packet received, not the next expected packet.
Step 3
If
seqNo = Rn
the receiver delivers
- that packet, and
- all previously received consecutive packets stored in the buffer
to the application layer.
Finally,
the receive window slides so that Rn points to the first empty position.
Example
Suppose
Receiver expects
Packet 2
Instead,
it receives
Packet 3
The receiver
Stores Packet 3 Sends ACK 3
Later,
Packet 2 arrives.
The receiver now delivers
Packet 2 Packet 3
to the application layer,
and then slides the receive window.
This is the major advantage of Selective Repeat.
(b) Packet Arrives Outside the Receive Window
If an error-free packet arrives whose sequence number lies outside the receive window,
the receiver
- discards the packet,
- sends an ACK with
ackNo = Rn
This ACK allows the sender to slide its window if some earlier acknowledgments were lost.
(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, store a copy, send packet, start timer, increment Sn |
| Ready | Valid ACK | Mark packet as acknowledged; if ackNo = Sf, slide window over all consecutive acknowledged packets; restart or stop timer |
| Ready | Corrupted/Invalid ACK | Discard ACK |
| Ready | Timeout | Resend all unacknowledged packets in the sender window and restart timer |
| Blocking | Valid ACK | Mark packet as acknowledged; slide window if possible; move to Ready State when the window slides |
| Blocking | Corrupted/Invalid ACK | Discard ACK |
| Blocking | Timeout | Resend all unacknowledged packets in the sender window and restart timer |
Summary of Receiver FSM
| State | Event | Action |
|---|---|---|
| Ready | Correct packet inside receive window | Store packet, send ACK (ackNo = seqNo); if seqNo = Rn, deliver this packet and all consecutive buffered packets, then slide the receive window |
| Ready | Packet outside receive window | Discard packet and send ACK = Rn |
| Ready | Corrupted packet | Discard packet |
Differences Between the FSMs of Go-Back-N and Selective Repeat
| Feature | Go-Back-N | Selective Repeat |
|---|---|---|
| ACK type | Cumulative ACK | Individual ACK |
| Receiver behavior | Discards out-of-order packets | Stores out-of-order packets |
| Packet acknowledgment | All previous packets assumed acknowledged | Only the acknowledged packet is marked |
| Window sliding | Slides based on cumulative ACK | Slides over all consecutive acknowledged packets starting from Sf |
| Receiver buffering | Not required | Required |
| Retransmission | All outstanding packets | Unacknowledged packets in the sender window |
Key Points to Remember
- The sender has two states: Ready and Blocking, while the receiver is always in the Ready State.
- Unlike Go-Back-N, the sender marks individual packets as acknowledged and slides the sender window only when the first outstanding packet (Sf) is acknowledged.
- The receiver stores out-of-order packets, acknowledges each packet individually using ACK = seqNo, and delivers packets to the application layer only when all preceding packets have been received.
- On a timeout, the sender retransmits all unacknowledged packets currently present in the sender window, ensuring reliable delivery while avoiding unnecessary retransmission of already acknowledged packets.
Comments
Post a Comment