Question 3 of 6: Reliability of Request-Reply Protocols

Question 3: Reliability of Request-Reply Protocols

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

(a) Message count vs. total bytes, and a piggybacked-ack RRA variant. Much of the real cost of exchanging a message is a per-message fixed overhead — one round trip's worth of propagation delay, queuing delay, kernel/OS crossing and marshalling/unmarshalling — that is paid once per message regardless of how many bytes it carries, exactly as modelled in Q2(a) where the flat 5 ms per-packet latency dominated the data-rate term for messages of a few kilobytes or less (doubling a message's payload only adds a small, size-proportional increment, while sending one extra message adds a whole extra fixed latency). Consequently, halving the number of separate messages/round trips in a protocol tends to reduce perceived latency far more than halving the number of bytes sent, unless payloads are unusually large. This is exactly why designers look to eliminate stand-alone acknowledgement messages wherever a follow-up message is coming anyway.

The standard request-reply-acknowledge (RRA) protocol always sends the client's acknowledgement of a reply as its own separate message, immediately upon receipt. The piggybacked variant instead delays that acknowledgement briefly (using an extra client-side timer) to see whether the application is about to issue its next request to the same server anyway, and if so, folds the acknowledgement into that request as an extra field rather than sending it stand-alone:

on receive_reply(reply):
    deliver_to_application(reply)
    pending_ack = reply.seq
    start ack_timer (duration = T_piggyback)   // bounded wait, e.g. a few RTTs

on ack_timer_expires():
    if pending_ack is not None:
        send(standalone_ACK(pending_ack))      // fallback: no new request arrived in time
        pending_ack = None

on application_ready_to_send(next_request):
    if pending_ack is not None:
        next_request.piggyback_ack = pending_ack   // fold the ack into the new request
        pending_ack = None
        cancel(ack_timer)
    send(next_request)

Whenever the client's own workload naturally produces a follow-up request within the timer window, one message now serves double duty (new request + earlier ack), eliminating a whole round trip that would otherwise exist purely to carry the acknowledgement; the timer's bounded fallback guarantees the server is never left waiting indefinitely for an ack that piggybacking would otherwise delay past the server's own retention needs.

(b) A NACK-based reliable IP-multicast retransmission scheme. With multiple senders and (potentially many) recipients, a scheme built on positive acknowledgements would cause ACK implosion — every recipient acknowledging every message back to every sender does not scale with group size — so the design instead uses negative acknowledgements (NACKs), requested only when a gap is actually detected:

1. Per-sender sequencing. Each sender numbers its own messages with an independent, monotonically increasing sequence number. Because messages that are not dropped are given to arrive in sender ordering, a recipient can detect a loss from a specific sender purely by seeing a gap in that sender's sequence numbers (e.g. sender S's messages 4 and 6 arrive but 5 never does) — multiple senders are handled by keeping one such sequence-gap tracker per sender independently.
2. Gap detection triggers a NACK, not the sender's silence. Since recipients "may not necessarily send a message within any particular time," the scheme cannot rely on a fixed acknowledgement deadline from every recipient; instead, each recipient passively waits until it notices a gap (a later message from the same sender arrived, but an intervening sequence number did not), at which point it multicasts — not unicasts to the original sender — a NACK naming the missing (sender, sequence-number) pair.
3. NACK suppression via randomized, jittered timers. Multicasting the NACK lets every other recipient that is about to request the same retransmission see the request first and suppress its own (since a small proportion of drops are often correlated across nearby recipients on the same failing link). Each recipient that detects the same gap starts an independent, randomly jittered timer (e.g. proportional to its estimated round-trip time to the sender) before sending its own NACK; whichever recipient's timer fires first sends the single NACK, and every other recipient, on overhearing it, cancels its own pending timer. This keeps total NACK traffic roughly constant regardless of how many recipients are missing the same message.
4. Retransmission by whichever node already has the data. Any node that already holds the missing message — the original sender, or another recipient that received it and cached it — can multicast the retransmission, so a single retransmission repairs every recipient still missing that message at once, rather than the original sender alone having to answer one NACK per missing recipient. The retransmission itself is also multicast (using the same NACK-suppression discipline as step 3) so a second recipient who was about to retransmit the same data can cancel.

The scheme scales because both the request side (NACKs) and the repair side (retransmissions) are self-suppressing multicasts rather than a fixed sender fielding one message per lossy recipient, which is exactly what makes it workable when "only a small proportion of messages are dropped" but the group of senders and recipients may both be large.