Reliable delivery and sliding windows
Goals and explicit conventions
Explain flow control, loss recovery and pipelining; trace stop-and-wait, Go-Back-N and Selective Repeat; calculate a window-limited rate. These are generic teaching protocols, not complete TCP specifications. Frames have equal length unless stated otherwise. Sequence numbers wrap modulo2^k. In our Go-Back-N examples ACK n means the next sequence number expected; many books use last-received numbering, so translate the convention before solving.
Flow control prevents overwhelming the receiver. Error control detects or recovers from loss/corruption. Congestion control limits load on the network. A mechanism can contribute to more than one goal, but these problems are not synonyms. A checksum can detect a damaged frame without recovering it; acknowledgments and retransmission add recovery.
1. Stop-and-wait and the alternating bit
Send one frame, retain a copy and start a timer. On a valid acknowledgment, advance; on timeout, retransmit. A receiver must recognize duplicates: if data was delivered but its ACK was lost, retransmission must not deliver the same application data twice. With one outstanding frame and suitably bounded packet lifetime, alternating sequence numbers0 and1 distinguish a new frame from a repeat. The receiver acknowledges a duplicate again but does not redeliver it. Sequence bits alone cannot distinguish arbitrarily ancient packets that survive indefinitely across repeated wraparound; protocol assumptions matter.
Worked trace: sender sends data0; receiver accepts it and ACKs it; ACK is lost. Sender times out and resends0. Receiver still expects1, so it recognizes0 as duplicate, repeats the acknowledgment and delivers no second copy. Sender then sends1. If data0 rather than its ACK was lost, retransmission would be the first accepted copy. A timeout indicates uncertainty, not proof that the data itself was lost.
2. Stop-and-wait utilization
Let a data frame take T_f=L/R to transmit. One-way propagation is T_p; ACK transmission time is T_a. Ignore processing, queuing, errors and turnaround overhead. A cycle from first data bit to returning last ACK bit is T_f+2T_p+T_a. Useful data-transmission utilization U=T_f/(T_f+2T_p+T_a). If ACK time is negligible and a=T_p/T_f, U=1/(1+2a). Goodput equals useful payload bits divided by cycle time, so headers must be excluded from useful payload if specified.
Example: a1000-byte all-payload teaching frame on10 Mb/s takes0.8 ms. One-way propagation4 ms and negligible ACK give cycle8.8 ms and U=0.8/8.8=1/11≈9.09%. Goodput=8000/0.0088≈0.909 Mb/s. Increasing link bandwidth alone shortens transmission time but does not remove the propagation wait.
3. Sliding windows and pipeline size
A sender window of W frames permits up to W outstanding frames before waiting for acknowledgments. In the ideal error-free model above with immediate ACKs and negligible ACK serialization, U=min(1,W×T_f/(T_f+2T_p))=min(1,W/(1+2a)). Continuous transmission requires W≥ceil(1+2a). In the preceding example W=11 suffices; W=5 gives5/11 utilization. This formula includes the time to serialize the first frame before its acknowledgment can return.
A byte-window approximation often uses rate≤window/RTT when RTT is defined as the relevant acknowledgment feedback interval and transmission overhead is already incorporated or negligible. Always define RTT: some questions mean propagation round trip only, others include data/ACK serialization. A bandwidth-delay product gives the amount of data needed in flight, with exact frame-count boundaries depending on those definitions. Receiver buffering, losses, ACK policy and congestion can lower real throughput.
4. Go-Back-N
With k sequence bits, the standard Go-Back-N sender window can be at most2^k−1 and the receiver window is1. The receiver accepts only the next expected frame, discards out-of-order frames and sends cumulative ACKs. On timeout for the oldest outstanding frame, the sender retransmits it and all later outstanding frames in the basic protocol. One timer for the oldest outstanding frame is sufficient in this model. The wasted transmissions after a loss grow with pipeline length.
Trace with window4, initially expecting0: sender emits0,1,2,3; frame1 is lost. Receiver accepts0 and sends ACK1; discards2 and3, also sending ACK1. The timeout causes retransmission1,2,3 if they remain outstanding. After accepting these in order, receiver can send ACK4. ACK4 covers all frames before4 under the stated convention. Why not window2^k? If an entire cycle were sent and all ACKs lost, the receiver could return to the same expected sequence value and mistake old retransmissions for new data.
5. Selective Repeat
Selective Repeat accepts and buffers in-window out-of-order frames, acknowledges individual received frames and retransmits only frames identified as missing by their timers or recovery rules. It needs more receiver state and may use logically separate timers. Data is delivered in order once the gap closes. With equal sender and receiver windows W and k-bit numbering, the classic safety bound is W≤2^(k−1); otherwise old and new receive windows can overlap ambiguously after wraparound. More generally the standard window-separation condition is W_s+W_r≤2^k under the model's lifetime assumptions.
Using window4 and sufficient sequence space, send0,1,2,3 with1 lost. Receiver accepts0 and buffers2,3, acknowledging them individually. Retransmission of1 closes the gap and allows delivery1,2,3. Only1 needs retransmission here. If an acknowledgment is lost, a duplicate may arrive; the receiver must acknowledge appropriate duplicates without delivering them again. Buffering does not mean application delivery can skip the missing data in an ordered service.
Worked bounds: k=3 gives8 values. Go-Back-N allows sender window7; equal-window Selective Repeat allows4. For a required Selective Repeat window5, need2^k≥10, so k≥4. Do not calculate k from W alone using2^k≥W.
6. Choosing the correct model
Stop-and-wait minimizes outstanding state but wastes long-delay bandwidth. Go-Back-N simplifies the receiver but repeats successfully received later frames after a gap. Selective Repeat saves retransmissions at the price of buffering and more state. Piggybacking places an ACK on reverse-direction data when available; an ACK timer may still be needed when reverse traffic is absent. Delayed acknowledgments alter feedback timing, so do not silently use immediate-ACK throughput formulas.
For any trace write sender base, next-to-send, receiver expectation, accepted/buffered frames, ACK meaning and timeout target. Check whether corruption is detected and treated as loss, whether ACKs can be lost and whether delivery is ordered. Numerical throughput questions require payload/frame sizes, rate, propagation, ACK time and error assumptions. TCP borrows sliding-window ideas but its byte numbering, cumulative ACKs, optional selective acknowledgment and congestion behavior require the next lesson's model.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. A receiver accepts frame0 but its ACK is lost in alternating-bit stop-and-wait. What should it do when frame0 is retransmitted?
A. Deliver it again B. Acknowledge again without delivering again C. Treat it as frame1 D. Erase all application data
Answer: B
A: This duplicates application delivery.
B: The duplicate must be acknowledged to restore progress without redelivery.
C: The sequence number remains0.
D: No such recovery action is required.
P02. For T_f=1 ms, one-way propagation4 ms and negligible ACK time, ideal stop-and-wait utilization is what?
A. 1/4 B. 1/5 C. 1/8 D. 1/9
Answer: D
A: This omits the return path and frame time.
B: This counts only one propagation interval.
C: The cycle also includes1 ms serialization.
D: Cycle=1+8=9 ms, so utilization1/9.
P03. Under the preceding ideal timing model, what is the smallest frame window for continuous transmission?
A. 4 B. 8 C. 9 D. 10
Answer: C
A: Four frames do not cover the9 ms feedback cycle.
B: Eight finish before the first ACK returns.
C: ceil((1+8)/1)=9.
D: Ten works but is not the minimum.
P04. With4-bit numbering, what is the standard maximum Go-Back-N sender window?
A. 7 B. 8 C. 15 D. 16
Answer: C
A: This corresponds to3-bit Go-Back-N.
B: 8 is the equal-window Selective Repeat limit.
C: 2^4−1=15.
D: Using all16 values can create wraparound ambiguity.
P05. Equal-window Selective Repeat needs a window of9 frames. What is the minimum sequence field width?
A. 3 B. 4 C. 5 D. 9
Answer: C
A: Eight total values cannot separate two windows of9.
B: Four bits permit equal windows only up to8.
C: Need2^k≥18, so k=5.
D: Nine bits work but are not minimal.
P06. In basic Go-Back-N, frames0–3 were sent,1 was lost, and2–3 arrived before timeout. What does the receiver do with2–3?
A. Buffers and delivers them before1 B. Discards them as out of order C. Changes their sequence numbers D. Automatically repairs frame1
Answer: B
A: Basic Go-Back-N has receiver window1 and no such out-of-order delivery.
B: It accepts only the expected frame1 and repeats a cumulative ACK.
C: The receiver does not renumber frames.
D: ARQ requests recovery through retransmission, not automatic reconstruction.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Computer Networks syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in