Selective-Repeat (SR) Protocol

Introduction

The Go-Back-N (GBN) Protocol simplifies the receiver because it keeps track of only one variable and does not buffer out-of-order packets. Any packet that arrives out of order is simply discarded. However, this approach becomes inefficient when the network loses many packets. Whenever a single packet is lost or corrupted, the sender retransmits all outstanding packets, even though some of them may have already been received correctly but out of order.

If packet losses are caused by network congestion, retransmitting all outstanding packets further increases congestion, resulting in even more packet losses. This creates an avalanche effect, which may eventually lead to the collapse of the network.

To overcome this problem, another protocol called the Selective-Repeat (SR) Protocol was developed. As the name suggests, the sender retransmits only the packets that are actually lost or corrupted, rather than all outstanding packets.

Why Selective-Repeat Protocol?

Consider the following example.

The sender transmits six packets.


Packet 0
Packet 1
Packet 2
Packet 3
Packet 4
Packet 5

Suppose Packet 2 is lost.

In Go-Back-N

Even though Packets 3, 4, and 5 have reached the receiver correctly, they are discarded because Packet 2 is missing.

After timeout, the sender retransmits


Packet 2
Packet 3
Packet 4
Packet 5

This wastes bandwidth.

In Selective Repeat

The receiver stores Packets 3, 4, and 5 in its buffer.

The sender retransmits only


Packet 2

Once Packet 2 arrives,

the receiver delivers


Packet 2
Packet 3
Packet 4
Packet 5

to the application layer in the correct order.

Thus, Selective Repeat greatly improves transmission efficiency.

Characteristics of Selective-Repeat Protocol

Connection-oriented protocol
Sliding window protocol
Supports pipelining
Provides flow control
Provides error control
Retransmits only lost or corrupted packets
Receiver buffers out-of-order packets
Sender and receiver windows are of equal size
Uses individual acknowledgments
Higher efficiency than Go-Back-N

Outline of Selective-Repeat Protocol

Unlike Go-Back-N,

the sender retransmits only the missing packets.
the receiver stores packets that arrive out of order until the missing packets are received.

Windows

Like Go-Back-N, the Selective-Repeat protocol also uses two windows:

Send Window
Receive Window

However, these windows differ significantly from those used in Go-Back-N.

Send Window

The send window controls the packets that the sender is allowed to transmit.

Unlike Go-Back-N,

the maximum send window size is

2^{𝑚 - 1}

where

m = number of bits used for the sequence number.

For example,


m = 4

Sequence numbers are


0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Total sequence numbers

Maximum sender window


2^(4−1)=8

Thus,

only 8 packets can remain outstanding at a time.

Send Window Layout

The sender window contains several types of packets.

Receive Window

The receive window in Selective Repeat is completely different from that of Go-Back-N.

The size of the receive window is

2^{𝑚 - 1}

which is equal to the send window size.

Example


Sender Window = 8

Receiver Window = 8

This means that the receiver can accept multiple packets out of order and store them until the missing packets arrive.

Out-of-Order Reception

Suppose the receiver expects


Packet 2

Instead it receives


Packet 3

Packet 4

Packet 5

In Go-Back-N


Discard Packet 3

Discard Packet 4

Discard Packet 5

In Selective Repeat


Store Packet 3

Store Packet 4

Store Packet 5

Later,

when Packet 2 arrives,

the receiver delivers


Packet 2

Packet 3

Packet 4

Packet 5

to the application layer in order.

Important Point

Although the receiver stores packets out of order,

it never delivers them out of order to the application layer.

Packets are delivered only after all earlier packets have been received successfully.

Timer

In theory,

Selective Repeat uses

one timer for every outstanding packet.

Example


Packet 0 → Timer 0

Packet 1 → Timer 1

Packet 2 → Timer 2

Packet 3 → Timer 3

If Timer 2 expires,

only


Packet 2

is retransmitted.

Unlike Go-Back-N,

other packets are not retransmitted.

However, many practical transport-layer implementations use a single timer instead of multiple timers for simplicity.

Acknowledgments

Acknowledgments in Selective Repeat are individual acknowledgments.

Each ACK confirms the successful reception of only one packet.

Unlike Go-Back-N,

ACKs are not cumulative.

Example

Suppose the sender transmits


Packet 0

Packet 1

Packet 2

Packet 3

Packet 4

Packet 5

Receiver sends


ACK 3

This means


Packet 3

received successfully.

It gives no information about Packets 0, 1, 2, 4, or 5.

Example 3.9

Problem

Assume a sender sends six packets:


Packet 0

Packet 1

Packet 2

Packet 3

Packet 4

Packet 5

The sender receives


ACK = 3

Interpret this ACK if the protocol is

Go-Back-N
Selective Repeat

Solution

Go-Back-N


ACK = 3

means


Packets

0

1

2

received correctly.

Receiver expects Packet 3.