🚀 Tutorial 5: Pipelined Protocols – Go‑Back‑N and Selective Repeat (Advanced)

University‑level treatment – COMP347 (TrustOpen University)

📘 1. Motivation for Pipelining

As we saw in Tutorial 4, stop‑and‑wait utilization is U = t_trans / (t_trans + 2*t_prop). For high‑bandwidth, long‑delay links, this ratio is extremely small. The solution is to allow multiple packets to be transmitted before waiting for acknowledgments. This is achieved by pipelining: the sender can send up to N packets without waiting for an ACK, where N is the window size.

Pipelining increases throughput by filling the network pipe. However, it introduces complexity in error recovery:

• How does the receiver handle out‑of‑order packets?
• How does the sender know which packets to retransmit when losses occur?
• How do we avoid ambiguity with sequence numbers?

Two main approaches emerged: Go‑Back‑N (simple receiver) and Selective Repeat (efficient retransmissions).

📘 2. General Pipelined Protocol Architecture

In a pipelined protocol, both sender and receiver maintain a window of sequence numbers. The sender window defines the range of packets that can be sent without waiting for ACKs. The receiver window defines which packets are acceptable to receive (and buffer).

• Sender window: typically bounded by N. Packets with sequence numbers in the window are either sent but unacknowledged, or ready to send. As ACKs arrive, the window slides forward.
• Receiver window: defines the sequence numbers that the receiver will accept. In GBN, the receiver window size is 1 (only expects the next in‑order packet). In SR, the receiver window size can be larger to buffer out‑of‑order packets.

Pipelining relies on sequence numbers of sufficient bits to uniquely identify packets in flight and avoid confusion after wraparound.

📘 3. Go‑Back‑N (GBN) – Detailed Analysis

3.1 Sender Operation

• Maintains a base (oldest unacknowledged packet) and a nextseqnum (next packet to send).
• Window size = N. Packets with seq numbers in [base, base+N-1] can be sent.
• When data arrives from application, if nextseqnum < base+N, send packet with seq = nextseqnum, increment nextseqnum; else block.
• On receipt of a cumulative ACK with acknowledgment number acknum: slide base to acknum (i.e., base = acknum). This acknowledges all packets up to acknum-1.
• On timeout: restart timer and retransmit all packets from base to nextseqnum-1 (i.e., the entire window).
• Typically uses a single timer for the oldest outstanding packet.

3.2 Receiver Operation

• Expects only the next in‑order packet (expectedseqnum).
• On arrival of packet with seq = expectedseqnum: deliver to application, send cumulative ACK (ack = expectedseqnum+1), increment expectedseqnum.
• On arrival of out‑of‑order packet (seq != expectedseqnum): discard the packet (no buffering) and resend ACK for the last in‑order packet (i.e., a duplicate ACK for expectedseqnum).
• Thus, the receiver window size is effectively 1.

3.3 Advantages and Disadvantages

• Advantages: Simple receiver (no buffering), simple sender (single timer).
• Disadvantages: Wastes bandwidth on retransmissions when a single packet is lost (must retransmit entire window).

+-----------------------------------+
|  Wait for call from above         |
|  (ready)                          |
+-----------------------------------+
   | event: rdt_send(data) if window not full
   | action: make_packet, send, if first packet start timer
   v
+-----------------------------------+
|  Wait for ACK / timeout           |
|  (window in flight)               |
+-----------------------------------+
   | event: rdt_rcv(ACK, acknum)
   | action: if acknum > base, slide base = acknum;
   |         if base == nextseqnum, stop timer; else restart timer
   | event: timeout
   | action: retransmit all from base to nextseqnum-1, restart timer
        

📘 4. Selective Repeat (SR) – Detailed Analysis

4.1 Sender Operation

• Maintains a window of size N.
• Packets in the window can be sent; each packet has its own timer (or a single timer can be used with a list of outstanding).
• On timeout for a specific packet: retransmit only that packet.
• On receipt of an individual ACK for a packet: mark that packet as acknowledged. If the ACK acknowledges the lowest unacknowledged packet (base), slide the window forward over all consecutively acknowledged packets.
• Thus, the sender can retransmit selectively.

4.2 Receiver Operation

• Maintains a receiver window of size N (or at least as large as sender window).
• Accepts packets with sequence numbers within the receiver window, even if out of order.
• Buffers out‑of‑order packets until missing ones arrive.
• Sends individual ACK for every correctly received packet (including duplicates).
• When a packet is received with seq = expected (the lowest missing), deliver all consecutive buffered packets, and slide the window forward.

4.3 Advantages and Disadvantages

• Advantages: More efficient use of bandwidth; only lost packets are retransmitted.
• Disadvantages: More complex; receiver needs to buffer out‑of‑order packets; multiple timers needed (or more complex timer management).

📘 5. Sequence Number Space and Window Size Constraints

With finite‑bit sequence numbers, the window size cannot be arbitrarily large; otherwise, ambiguous situations arise when sequence numbers wrap around. The constraints differ for GBN and SR.

5.1 GBN Constraint

For GBN, the receiver discards out‑of‑order packets and sends duplicate ACKs. The sender may receive duplicate ACKs, but it only slides the window on a new cumulative ACK. To avoid ambiguity when a packet is retransmitted, we need Window size ≤ (Sequence number space) – 1.

With k‑bit sequence numbers, max window size = 2^k – 1. For example, with 3 bits (0–7), max window = 7.

Why? If window size equals 2^k, the sender could have all sequence numbers outstanding, and a delayed ACK for the first packet could be mistaken for an ACK for the retransmitted packet with the same sequence number.

5.2 SR Constraint

For SR, the receiver buffers out‑of‑order packets and uses individual ACKs. To avoid ambiguity between new packets and retransmissions, the window size must be ≤ half the sequence number space.

With k‑bit sequence numbers, max window size = 2^k‑1. For example, with 3 bits, max window = 4.

Why? If window size > 2^k‑1, after a wraparound, a packet could be mistaken for a new packet when ACKs are lost. The half‑space ensures that the sender and receiver windows do not overlap in a way that causes ambiguity.

5.3 Practical Implications

In TCP, sequence numbers are 32 bits, so the window size is limited by the 16‑bit window field in the TCP header (up to 65535), but with window scaling (RFC 1323), the effective window can be larger. TCP uses a variant of Selective Repeat (with SACK) but historically used cumulative ACKs.

📘 6. Performance Comparison: GBN vs. SR

6.1 Throughput Models

Assume a loss probability p for each packet (independent), window size N, and RTT.

• GBN: When a packet is lost, all packets from that point in the window are retransmitted. The expected number of transmissions per successfully delivered packet is approximately 1 / (1 - p) but with additional overhead due to the "go‑back" effect. A common approximation for throughput (with large N) is Throughput ≈ (1 - p) * N * MSS / RTT when N is small enough to avoid timeouts, but more exact models account for the probability of multiple losses.
• SR: Only the lost packet is retransmitted. The expected number of transmissions per packet is 1 / (1 - p). Throughput is roughly Throughput ≈ N * MSS / (RTT * (1 + overhead)), but each packet's retransmission is independent.

For a given loss rate, SR yields higher throughput because it retransmits less. However, GBN is simpler to implement.

6.2 Impact of Window Size

Larger windows improve utilization but increase the cost of a loss in GBN (more retransmissions). In SR, larger windows improve throughput but require more buffering and timers.

6.3 Impact of Loss Pattern

If losses are bursty, GBN may suffer greatly because many packets need retransmission. SR performs better because only the lost packets are retransmitted, but it relies on accurate ACKs.

6.4 Complexity Comparison

📘 7. Advanced Topics: Dynamic Windows, SACK, and TCP Influences

7.1 Dynamic Window Sizing

In practice, the window size is often dynamic to adapt to network conditions (congestion control). TCP uses a congestion window (cwnd) that grows and shrinks based on loss signals. The concepts of GBN and SR are reflected in TCP's mechanisms: cumulative ACKs (GBN style) and fast retransmit (similar to SR's selective retransmission, especially with SACK).

7.2 Selective Acknowledgment (SACK)

TCP SACK (RFC 2018) allows the receiver to acknowledge non‑contiguous blocks of data, effectively enabling selective retransmission without the complexity of full SR at the transport layer. This bridges the gap between GBN and SR.

7.3 Impact of Out‑of‑Order Buffering

SR's receiver buffering requires memory and careful management to avoid head‑of‑line blocking. This is a key design consideration in high‑performance systems.

7.4 Relationship to TCP

TCP uses a sliding window with cumulative ACKs (like GBN) but also implements fast retransmit (which is SR‑like) when it receives 3 duplicate ACKs. This hybrid approach combines the simplicity of cumulative ACKs with the efficiency of selective retransmission for some losses.

📝 Quiz

Test your understanding with these 30 questions. Answers are hidden below each.

🛠️ Exercises

Apply your knowledge with these 15 exercises. Solutions are provided below each.

📚 Homework

These advanced problems require synthesis, quantitative analysis, and research. Sample answers are provided below.