Stop-and-wait and alternating-bit allow only one packet to be in transit at a time, so we use only a fraction of the channel's capacity (a very small fraction for high data rates, long propagation delays, and/or short packets). We need pipelining: send more packets while waiting for acknowledgements. The range of packets that can be in the pipe is called the window, and pipelined retransmission protocols are called sliding window protocols. Go-back-N: Works only for FIFO links. The semantics of acks are strange--they mean the message was received, not necessarily stored. So reordering acks could cause some acks that should have been ignored to be counted. Assume incoming acks are queued if they are not fetched right away. Modulus Z = W+1. Invariants: message[S..S+W-1] are not null, all others are null timer[seq] is set iff message[seq] is not null source: procedure sendmessage(seq) if message[seq] == null then message[seq] = next message send seq,message[seq] set timer[seq] to expire T from now endprocedure S = 0 while true for i = 0 to W-1 sendmessage((S+i) mod Z) while true wait for S,ack or a timer expiration if a timer expired then break cancel timer[S] message[S] = null sendmessage((S+W) mod Z) increment S modulo Z endwhile cancel all timers endwhile sink: R = 0 while true wait for any seq,message send seq,ack if seq = R then deliver message increment R modulo Z endif endwhile Intuitively: Source sends a batch of W packets, then sends one more whenever an ack comes in, so there are always W outstanding packets. But whenever an ack fails to come in, the sender stalls, times out, the starts all over with a batch of W packets starting with the first unacknowledged. The receiver accepts messages strictly in order, as in stop-and-wait and alternating-bit. In the absence of errors, we can send W packets per round-trip, so the efficiency is (W/r)/(1/tau) = W*tau/r. Of course, if r < W*tau the efficiency is not greater than 100%--acks come back early and are queued. Every error causes a whole window (or round-trip) worth of stuff to be retransmitted. If the receiver could buffer things received out of order... Selective-repeat: Modulus Z = 2W for FIFO links, or large enough for non-FIFO links with finite capacity. Invariants: only message[L+1..L+W] may be non-null message[L+W] is not null timer[seq] is set iff message[seq] is not null source: procedure sendmessage(seq) if message[seq] == null then message[seq] = next message send seq,message[seq] set timer[seq] to expire T from now endprocedure L = Z-1 for i = 1 to W sendmessage((L+i) mod Z) while true wait for any seq,ack or a timer expiration if timer[seq] expired sendmessage(seq) else seq,ack arrived cancel timer[seq] message[seq] = null while message[L+1] == null increment L modulo Z sendmessage((L+W) mod Z) endwhile endif endwhile sink: R = 0 while true wait for any seq,message send seq,ack if seq in R..R+W-1 (modulo Z) then message[seq] = message while message[R] is not null deliver message[R] message[R] = null increment R modulo Z endwhile endif endwhile Intuitively: Source keeps track of which messages have been acked, and in case of a timeout, retransmits only the message that timed out. When the packet at the lower end of the window gets acked, the sender advances the window as far as possible, sending new messages at the upper end. The receiver accepts messages out of order and buffers them so they can be delivered in order. In the absence of errors, the efficiency is the same as go-back-n.