Lost message detection
How the message-id bits could help hosts detect lost messages and retransmit them.
Walden, D.C., "Lost message detection", RFC 534, DOI 10.17487/RFC0534, July 1973, <https://www.rfc-editor.org/info/rfc534>.
@misc{rfc534,
series = {Request for Comments},
number = 534,
howpublished = {RFC 534},
publisher = {RFC Editor},
doi = {10.17487/RFC0534},
url = {https://www.rfc-editor.org/info/rfc534},
author = {D.C. Walden},
title = {{Lost message detection}},
pagetotal = 2,
year = 1973,
month = jul,
} RFC text
Network Working Group David Walden
Request for Comments: 534 BBN-NET
NIC: 17453 17 July 1973
References: 512, 516, 533
Lost Message Detection
As an aside to RFC 533, note that if sending Hosts do uniquely
identify messages on a given link using the extra four bits and
receiving Hosts do look at these bits, a lost message detection
system such as those suggested in RFCs 512 and 516 drops right out of
using of the unique message-id. These extra four bits can be treated
as Hathaway's SCB of RFC 512 providing a 16 element sequence number
on a per connection basis. A 16 element sequence is sufficient as
the IMPs never allow more than four outstanding messages at one time
between a given pair of Hosts. As Hathaway also suggests, the 0
element in the sequence can be used to indicate to the receiving Host
that sequence numbers are not being used.
To summarize, there appear to be three modes of using the message-id
number under Host/Host protocol:
1. The sender can always set the extra four bits to 0 and only
transmit one message over a given link at a time -- this is slow
but it allows orderly retransmission of messages without any help
from the receiver.
2. The receiver can give no help to the sender. In this case it
doesn't matter whether the sender uses the extra four bits to
uniquely identify the messages or not -- the sender has no method
of orderly retransmission, although the sender can accurately
identify which message was lost if the sender has uniquely
identified the messages.
3. The sender can have multiple messages outstanding (i.e., RFNMs not
received) on a given link and the receiver can help the sender.
In this case, if the sender uses the extra four bits to uniquely
identify the messages in a way which can be synchronized with the
receiver (e.g., sequential id numbers), the receiver can reliably
detect lost messages.
Although it probably will seem insufficient to some, if the sender
and receiver use synchronized unique message-id numbers, very
reliable retransmission schemes are readily available. For instance,
the sender can retransmit the appropriate messages in response to
incomplete transmissions and the receiver can use the unique
message-ids to sort the retransmitted messages into the proper order
with the other received messages. Alternatively, the receiver can
discard all messages received out of order and the sender can back up
and retransmit a message for which an incomplete transmission was
received and all subsequent messages.
[ This RFC was put into machine readable form for entry ]
[ into the online RFC archives by Alex McKenzie with 10/99 ]
ISO Plain Language
On this page
§1Message IDs as Sequence Numbers
RFC 534 says the four added message-id bits can act as a sequence number for each connection if sending hosts use unique values and receiving hosts examine them. The resulting sequence has 16 elements. The RFC says this is enough because the IMPs allow no more than four outstanding messages at a time between a pair of hosts.
Sequence element zero can signal that the hosts are not using sequence numbers. This idea builds on lost-message detection approaches cited in RFCs 512 and 516.
Numbering messages lets a receiver notice when an expected number is missing. The receiver can do this only if it also looks at the numbers and the sender uses them consistently.
§2Three Ways to Use the Field
The RFC describes three modes. A sender can set the extra bits to zero and send only one message at a time on a link, allowing orderly retransmission without receiver help but reducing speed. If the receiver gives no help, unique IDs can identify which message was lost, but the sender has no method for orderly retransmission.
In the third mode, the sender may have several messages outstanding and the receiver helps. If both sides use synchronized unique IDs, such as sequential numbers, the receiver can reliably detect lost messages.
With no receiver help, a sender can wait after each message or merely identify which message was lost. When the receiver helps and both sides synchronize IDs, it can detect a missing message.
§3Possible Retransmission Strategies
The RFC gives two examples of how synchronized message IDs can support retransmission. The sender can resend the appropriate messages after an incomplete transmission, while the receiver uses the IDs to place them in the right order.
Alternatively, the receiver can discard messages that arrive out of order. The sender then backs up and retransmits the message associated with the incomplete transmission and all later messages.
A receiver can put retransmitted messages back in sequence, or discard out-of-order messages and ask the sender to start again from the gap.