Lost message detection and recovery protocol
RFC 663

Document Type RFC - Unknown (November 1974; No errata)
Last updated 2013-03-02
Stream Legacy
Formats plain text html pdf htmlized bibtex
Stream Legacy state (None)
Consensus Boilerplate Unknown
RFC Editor Note (None)
IESG IESG state RFC 663 (Unknown)
Telechat date
Responsible AD (None)
Send notices to (None)
Network Working Group                         Rajendra K. Kanodia
Request for Comments #663                        MIT, Project MAC
NIC #31387                                      November 29, 1974

        A LOST MESSAGE DETECTION AND RECOVERY PROTOCOL

1.0 INTRODUCTION

The current  Host-to-Host  protocol  does  not  provide  for  the
following three aspects of network communication:

     1. detection of messages lost in the transmission path
     2. detection of errors in the data
     3. procedures for recovery in the event of lost messages or
        data errors.

In this memo we propose an extension to the Host-to-Host protocol
that  will  allow  detection  of  lost  messages  and  an orderly
recovery from this situation.  If Host-to-Host protocol  were  to
be  amended  to  allow for detection of errors in the data, it is
expected that the recovery procedures proposed here  will  apply.

With  the  present  protocol,  it  may  some times be possible to
detect loss of messages in the transmission path.  However, often
a lost message (especially one on a control link) simply  results
in  an  inconsistent state of a network connection.  One frequent
(and frustrating) symptom of a message loss on a control link has
been the "lost allocate" problem which results in  a  "paralyzed"
connection.   The  NCP (Network Control Program) at the receiving
site  believes  that  sender  has  sufficient  allocation  for  a
connection,  whereas the NCP of the sending host believes that it
has no allocation (due to either loss of or error  in  a  message
that  contained  the  allocate  command).  The result is that the
sending  site  can  not  transmit  any  more  messages  over  the
connection.   This  problem  was  reported in the NWG-RFC #467 by
Burchfiel and Tomlinson.  They also proposed an extension to  the
Host-to-Host  protocol  which allows for resynchronization of the
connection status.  Their proposed solution was opposed by  Edwin
Meyer  (NWG-RFC  #492)  and  Wayne Hathaway (NWG-RFC #512) on the
grounds that it tended to mask  the  basic  problem  of  loss  of
messages  and  they  suggested  that  the  fundamental problem of
message loss should be solved rather than its  symptoms.   As  an
alternative  to  the  solution  proposed  in  NWG-RFC #467, Wayne
Hathaway suggested that Host-to-Host  protocol  header  could  be
extended  to include a "Sequence Control Byte" to allow detection
of lost messages.  At about the same time Jon Postel suggested  a
similar  scheme  using  message numbers (NWG-RFC #516).  A little
later David Walden proposed that four unused bits of the  message
sequence  number  (in  the IMP leader) be utilized for sequencing

                    - 1 -

messages (NWG-RFC #534).  His scheme is similar to those proposed
by Postel and  Hathaway;   however  it  has  the  advantage  that
Host-to-Host protocol mechanisms can be tied into the IMP-to-Host
protocol mechanisms.

The  protocol  extension  proposed here uses the four bits of the
message sequence number in the message leader  for  detection  of
lost  messages.  However, to facilitate recovery, it uses another
eight bit field (presently unused) in the 72 bit  header  of  the
regular  messages.   In the next section of this paper we discuss
some of the basic ideas underlying our protocol.  In  section  3,
we  provide  a  description of the protocol.  It is our intention
that section 3 be a self-contained and  complete  description  of
the protocol.

2.0 BASIC IDEAS

The  purpose  of this section is to provide a gentle introduction
to the central ideas on which this protocol  is  based.   Roughly
speaking,   our   protocol   can  be  divided  into  three  major
components.   First  is  the  mechanism  for  detecting  loss  of
messages.   Second  is  the  exchange  of information between the
sender and the receiver in the event  of  a  message  loss.   For
reasons  that  will soon become obvious, we have termed this area
as "Exchange of Control Messages".  The third  component  of  our
protocol  is  the  method of retransmission of lost messages.  In
this section, we have reversed the order of  discussion  for  the
second  and third components, because the mechanisms for exchange
of  control  messages  depend  heavily  upon  the  retransmission
methods.

A  careful  reader  will find that several minor issues have been
left unresolved in this section.  He (or  she)  should   remember
that this section is not intended to be a complete description of
the  protocol.   Hopefully, we have resolved most of these issues
in the formal description of the protocol provided in the section
3.

2.1 DETECTION OF LOSS OF MESSAGES

The 32 bit Host-to-IMP and IMP-to-Host leaders contain a  12  bit
message-id  in  bit  positions  17 to 28 (BBN Report #1822).  The
Host-to-Host protocol (NIC 8246) uses 8 bits  of  the  message-id
(bit  positions 17 to 24) as a link number.  The remaining 4 bits
of the message-id (bits 25 to 28) are presently unused.  For  the
Show full document text