Movatterモバイル変換

Network Working Group                         Rajendra K. KanodiaRequest for Comments #663                        MIT, Project MACNIC #31387                                      November 29, 1974A LOST MESSAGE DETECTION AND RECOVERY PROTOCOL1.0 INTRODUCTIONThe current  Host-to-Host  protocol  does  not  provide  for  thefollowing 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 protocolthat  will  allow  detection  of  lost  messages  and  an orderlyrecovery from this situation.  If Host-to-Host protocol  were  tobe  amended  to  allow for detection of errors in the data, it isexpected that the recovery procedures proposed here  will  apply.With  the  present  protocol,  it  may  some times be possible todetect loss of messages in the transmission path.  However, oftena lost message (especially one on a control link) simply  resultsin  an  inconsistent state of a network connection.  One frequent(and frustrating) symptom of a message loss on a control link hasbeen the "lost allocate" problem which results in  a  "paralyzed"connection.   The  NCP (Network Control Program) at the receivingsite  believes  that  sender  has  sufficient  allocation  for  aconnection,  whereas the NCP of the sending host believes that ithas no allocation (due to either loss of or error  in  a  messagethat  contained  the  allocate  command).  The result is that thesending  site  can  not  transmit  any  more  messages  over  theconnection.   This  problem  was  reported in the NWG-RFC #467 byBurchfiel and Tomlinson.  They also proposed an extension to  theHost-to-Host  protocol  which allows for resynchronization of theconnection status.  Their proposed solution was opposed by  EdwinMeyer  (NWG-RFC  #492)  and  Wayne Hathaway (NWG-RFC #512) on thegrounds that it tended to mask  the  basic  problem  of  loss  ofmessages  and  they  suggested  that  the  fundamental problem ofmessage loss should be solved rather than its  symptoms.   As  analternative  to  the  solution  proposed  in  NWG-RFC #467, WayneHathaway suggested that Host-to-Host  protocol  header  could  beextended  to include a "Sequence Control Byte" to allow detectionof lost messages.  At about the same time Jon Postel suggested  asimilar  scheme  using  message numbers (NWG-RFC #516).  A littlelater David Walden proposed that four unused bits of the  messagesequence  number  (in  the IMP leader) be utilized for sequencing                    - 1 -messages (NWG-RFC #534).  His scheme is similar to those proposedby Postel and  Hathaway;   however  it  has  the  advantage  thatHost-to-Host protocol mechanisms can be tied into the IMP-to-Hostprotocol mechanisms.The  protocol  extension  proposed here uses the four bits of themessage sequence number in the message leader  for  detection  oflost  messages.  However, to facilitate recovery, it uses anothereight bit field (presently unused) in the 72 bit  header  of  theregular  messages.   In the next section of this paper we discusssome of the basic ideas underlying our protocol.  In  section  3,we  provide  a  description of the protocol.  It is our intentionthatsection 3 be a self-contained and  complete  description  ofthe protocol.2.0 BASIC IDEASThe  purpose  of this section is to provide a gentle introductionto the central ideas on which this protocol  is  based.   Roughlyspeaking,   our   protocol   can  be  divided  into  three  majorcomponents.   First  is  the  mechanism  for  detecting  loss  ofmessages.   Second  is  the  exchange  of information between thesender and the receiver in the event  of  a  message  loss.   Forreasons  that  will soon become obvious, we have termed this areaas "Exchange of Control Messages".  The third  component  of  ourprotocol  is  the  method of retransmission of lost messages.  Inthis section, we have reversed the order of  discussion  for  thesecond  and third components, because the mechanisms for exchangeof  control  messages  depend  heavily  upon  the  retransmissionmethods.A  careful  reader  will find that several minor issues have beenleft unresolved in this section.  He (or  she)  should   rememberthat this section is not intended to be a complete description ofthe  protocol.   Hopefully, we have resolved most of these issuesin the formal description of the protocol provided in thesection3.2.1 DETECTION OF LOSS OF MESSAGESThe 32 bit Host-to-IMP and IMP-to-Host leaders contain a  12  bitmessage-id  in  bit  positions  17 to 28 (BBN Report #1822).  TheHost-to-Host protocol (NIC 8246) uses 8 bits  of  the  message-id(bit  positions 17 to 24) as a link number.  The remaining 4 bitsof the message-id (bits 25 to 28) are presently unused.  For  thepurposes  of  the  protocol to be presented here, we define these                    - 2 -four bits to be  the  message  sequence  number  (MSN  in  short)associated  with  the link.  Thus message-id consists of an eightbit link number and a four bit message sequence number.  The fourbit MSN provides a sixteen element sequence number for each link.A network connection has a sending host (referred to as  "sender"henceforth),   a   receiving   host   (referred  to  as  receiverhenceforth), and a link on which messages  are  transmitted.   Inour  protocol  the  sender starts communication with the value ofMSN set to one (i.e. the first message on any link has one in itsMSN field.)  For the next message on the same link the  value  ofMSN  is  increased  by one.  When the value of MSN becomes 15 thenext value chosen is one.  This results in the following sequence1, 2, ...., 13, 14, 15, 1, 2, ...., etc.  The receiver can detectloss  of  messages  by  examining  this  sequence.    Each   holecorresponds  to  a  lost  message.   Notice  that  the  detectionmechanism will fail if a sequence of exactly 15 messages were  tobe   lost.   For  the  time  being,  we  shall  assume  that  theprobability of loosing a  sequence  of  exactly  15  messages  isnegligible.   However,  we  shall later provide a status exchangemechanism (Section 2.6) that can be used to prevent this failure.Notice that in the sequence described above we have  omitted  thevalue  zero.   Following  a  suggestion made by Hathaway (NWG-RFC#512) and Walden (NWG-RFC #534) the new protocol uses  the  valuezero  to  indicate to the receiving host that the sending host isnot using message sequence numbers.   We,  in  fact,  extend  themeaning  associated  with  the  MSN  value zero to imply that thesending host has not implemented the detection and error recoveryprotocol being proposed here.2.2 COMPATIBILITYThe discussion above brings us  to  the  issue  of  compatibilitybetween  the  present  and  the new protocols.  Let us define thehosts with the present protocol to be type A and the  hosts  withthe new protocol to be type B.  We have three situations:     1. Type  A  communicating  with  type  A:   there   is   no        difference from the present situation.     2. Type A communicating with type B: from  the  zero  value        MSNs  in  messages  sent  by the type A host, the type B        host can detect the fact that the other host is a type A        host.  Therefore  the  type  B  host  can  simulate  the        behaviour of a type A host in its communication with the        other  host,  and  the type A host will not be confused.        As we will see later  that  this  simulation  is  really        simple and can be easily applied selectively.     3. Type B host communicating with type B:  Both  hosts  can        detect the fact that the other host is a type B host and                    - 3 -        use  the  message detection and error recovery protocol.There is one difficulty here that we have not yet resolved.  Whenstarting communication how does a type B host  know  whether  theother  host is type A or type B?  This difficulty can be resolvedby assuming that a type A host will not be confused by a non-zeroMSN in the messages that it receives.   This  assumption  is  notunreasonable   because  a  type  A  host  can  easily  meet  thisrequirement by making a  very  simple  change  to  its  NCP  (theNetwork  Control  Program),  if  it does not already satisfy thisrequirement.  Another assumption that is crucial to our protocol,is that the type A hosts always set the  MSN  field  of  messages(they send out) to zero.  As of this writing, the author believesthat   no  hosts  are  using  the  MSN  field  and  therefore  nocompatibility problem should arise.2.3 RETRANSMISSION OF MESSAGESBefore getting down to the details of  the  actual  protocol,  wewill  attempt here to explain the essential ideas underlying thisprotocol  by  considering  a   somewhat   simplified   situation.Consider  a  logical  communication  channel  X, which has at itsdisposal  an  inexhaustible  supply  of  physical   communicationchannels  C(1),  C(2),  C(3),  ........,  etc.  (See footnote #1)Channel X is  to  be  used  for  transmission  of  messages.   Inaddition  to  carrying  the  data, these messages contain (1) thechannel name X, and (2) a Message Sequence Number (MSN).  Let  usdenote  the  sender  on  this channel by S and the receiver by R.Let us also assume that at the start of the communication, R  andS  are  synchronized  such that R is prepared to receive messagesfor logical channel X  on the physical  channel  C(1)  and  S  isprepared for sending these messages on C(1).  S starts by pumpinga  sequence  of  messages  M(1),  M(2), M(3), ........, M(n) intochannel C(1).  Since these messages contain sequence  numbers,  Ris  able to detect loss of messages on the channel C(1).  Supposenow that R discovers that message number K (where K <n) was  lostin  the  transmission  path.   Let  us further assume that having_________________________________________________________________(1) One method of recovery may be to let the  receiver  save  allproperly  received  messages and require the sender to retransmitonly those messages that were lost.   This  method  requires  thereceiver  to have the ability to reassemble the messages to buildthe data stream.  A second method of recovery may be to abort andrestart  the  transmission  at  the  error  point.   This  methodrequires  that  the receiving host be able to distinguish betweenlegitimate messages and messages to be ignored.   For  simplicitywe  have  chosen the second method and an inexhaustible supply ofphysical  channels  serves  to  provide  the  distinction   amongmessages.                    - 4 -discovered loss of a message, R can communicate this fact to S bysending an appropriate control message on another logical channelthat is explicitly reserved for transmission of control  messagesfrom  R to S.  This channel, named Y, is assumed to be completelyreliable.We now provide a rather  simplistic  recovery  protocol  for  thescenario sketched above. Having detected the loss of message M(K)on channel X, R takes the following series of actions:      1- R stops reading messages on C(1),      2- R discards those messages that were received on C1  andare  placed after M(K) in the logical message sequence,      3- R prepares itself to read messages M(K), M(K+1), .....,etc.  on the physical channel C(2),  and 4- R sends a control message to S on  control  channel  Y,which  will  inform  S  to the effect that there was anerror on logical channel X while using physical channelC(1) in message number K.When S receives this control message on Y, it takes the followingaction:      1- S stops sending messages on C(1),  and 2- begins  transmission  of  messages  starting  with  thesequence number K, on the physical channel C(2).This  resynchronization protocol is executed every time R detectsan error.  If physical channel C(CN) was being used at  the  timeof  the  error,  then the next channel to be used is C(CN+1).  Wecan define a "receiver synchronization state"  for the channel X,as the triplet R(C, CN, MSN), where C is the name of the group ofphysical channels, CN is the number of the  physical  channel  inuse, and MSN is the number of message expected. (See footnote #1)We can specify a message received on a given C-channel as M(MSN).When R receives the message M(R.MSN) on the channel C(R.CN),  thesynch-state  changes  from  R(C,  CN,  MSN)  to  R(C, CN, MSN+1).However if M.MSN for the message received is greater  than  R.MSNthen  a  message  has been lost, and R changes the synch-state toR(C, CN+1,  MSN).   What  really  happens  may  be  described  asfollows:  upon  detection  of  error  in  a logical channel X, wemerely discard the physical channel that was in use at  the  timeof  error, and restart communication on a new physical channel atthe point where break occurred._________________________________________________________________(1) Notice that we have prefixed this triplet  by  the  letter  R(for  the  receiver.)   We  will  prefix  other similarly definedquantities by different letters.  For example M can be  used  formessages.   This  notation  permits  us to write expressions likeM.MSN = R.MSN, where M.MSN stands for the message sequence numberof the message.                    - 5 -This scheme provides a reliable transmission path X, even  thoughthe physical channels involved are unreliable.  In this scheme wehave  assumed  that  (1)  a  completely  reliable  channel  Y  isavailable for exchange of control messages, and (2) that there isa large supply of physical channels  available for use of X.   Inthe  paragraphs that follow we shall revise our protocol to use asingle physical channel and  then  apply  this  protocol  to  thechannel Y in such a way that Y would become "self-correcting."Now  suppose  that channel X has only one physical channel (namedX') available for its use rather than the inexhaustible supply ofphysical channels.  Our protocol would still work,  if  we  couldsomehow simulate the effect of a large number of C-channels usingthe  single  channel X'.  One method of providing this simulationis to include in each message the name of the C-channel on  whichit  is  being  sent,  and  send  it on X'.  Now the receiver mustexamine each message received on X' to determine the C-channel onwhich this message was sent.  Our protocol still works except forone minor difference,  namely,  the  receiver  must  now  discardmessages  corresponding  to C-channels that are no longer in use,whereas in the previous system the  C-channels  no  longer  beingused  were  simply  discarded.  To be sure, X' can be multiplexedamong only a finite number of C-channels; however, we can providea sufficiently large number of C-channels so that during the lifetime of the logical channel X, the probability of exhausting  thesupply  of  C-channels would be very low.  And even if we were toexhaust the supply of C-channels, we could recycle them  just  aswe recycle the message sequence numbers.A  physical  message received on X' can now be characterized by apair of C-channel number and a message sequence number, as  M(CN,MSN).  The receiver synchronization state becomes a triplet R(X',CN,  MSN).   This  state  tells  us  that R is ready to receive amessage for X on the physical channel X'  and  for  this  messageM.CN  should be equal to R.CN and M.MSN should be equal to R.MSN.All messages with M.CN less than R.CN will be  ignored.   If  forthe  next  message received on X', M.CN = R.CN and M.MSN = R.MSN,then R changes the synch state to R(X', CN, MSN+1).   If  M.CN  =R.CN  but  M.MSN  >  R.MSN  then a message has been lost and  thesynch-state R(X', CN, MSN) changes to R(X', CN+1,  MSN).   Noticethat  we  have  not  yet said anything about the situation M.CN >R.CN.  We will later describe a scheme for  using  this  case  toprovide for error correction on the control channel itself.2.4 EXCHANGE OF CONTROL INFORMATIONSo  far  we  have  discussed  two  schemes  for the detection andretransmission aspects of  the  lost-message  problem.   In  this                    - 6 -section, we discuss methods by which the receiver communicates tothe sender the fact of loss of messages.We continue with the scenario developed in the above section witha small change.  For the purposes of the discussion that is aboutto  follow  we  shall  assume that there are actually two perfectchannels available for exchange of control messages.  One channelfrom S to R named S->R, and the other from R  to  S  named  R->S.The  purpose  of S->R will become clear in a moment.  In order tolet R communicate the fact of loss of messages to S, We provide acontrol message called L_ost_Message_from_Receiver (LMR) which  isof  the  following  form: LMR(X, CN, MSN), where X is the name ofthe channel, CN is the new  C-channel  number,  and  MSN  is  themessage  sequence  number  of the lost message.  If more than onemessage has been lost, then R uses the MSN of the  first  messageonly.  When S receives this message, it can restart communicationat  the  point  where  the  break  occurred  using  the C-channelspecified  by  the  LMR   message.    This   will   restore   thecommunication  path  X.   What  happens  if  S  can  not  restorecommunication at the break point because it  does  not  have  therelevant  messages  any more?  This issue can be solved in one ofthe two ways: either let the protocol specify a fixed rule that Swill be required to close the connection, or the  protocol  couldallow  S  and R (and may be the users on whose behalf S and R arecommunicating on X) to negotiate the action to be taken.  For theprotocol to be presented here, we have taken the approach that  Smay, at its option, either close the connection or negotiate withR.   What  action  a specific host takes can either be built intoits NCP or determined dynamically.  Those hosts that do not  havevery  powerful  machines will probably chose the static option ofclosing the  connection;   other  hosts  may  make  the  decisiondepending upon the circumstances.  For example, a host may decidethat  loss  of  messages  is not acceptable during file transferswhereas  loss of a single message can  be  ignored  for  terminaloutput  to  interactive  users.   A  host might even let the userprocesses decide  the  course  of  action  to  be  taken.   If  Sdetermines  that it can not retransmit lost messages, it may wantto let R decide what action is to be taken.   If  S  so  decides,then  it  may  communicate  this  fact  to  R  by  transmitting aLost_Message_from_Sender  (LMS)  control  message  to  R  on  thechannel  S->R.   An LMS message is of the following form:  LMS(X,CN, MSN, COUNT), where X is the name of the channel,  CN  is  thename  of  the C-channel obtained from the LMR message, MSN is themessage sequence number of the first message in the  sequence  oflost  messages,  and  COUNT  is  the  number  of  messages in thesequence.  S resets its own synch-state for connection X to  S(X,CN,  MSN+COUNT).   When  S  has  informed  R  of its inability toretransmit lost messages, the burden of the decision falls on  R,and  S  simply  awaits R's reply before taking any action for thechannel X.  When R receives the LMS, it may  either  decide  thatloss  is  unacceptable and close the connection, or it may decideto let S continue.  In the later case R informs S of its decision                    - 7 -to continue by transmitting  a  L_oss_of_Message_Acceptable  (LMA)control  message to S.  Upon receiving the LMA control message, Sresumes transmission on X.  To avoid the possibility of errors inexchange  of  control  messages,  the  LMA  control  message   isspecified  to  be  an  exact  replica of the LMS control message,except for the message code which determines  whether  a  controlmessage is LMA or LMS or something else.In  general,  a  sending host has only a limited amount of memoryavailable for storing messages for possible retransmission later.Insection 2.6 we provide a status exchange mechanism that can beused to determine when to discard these messages.2.5 RECOVERY ON CONTROL LINKSWe continue our discussion with the  scenario  developed  in  theprevious  section.  The receiver R may detect loss of messages oncontrol channels by examining the message sequence numbers on themessages.  When R detects that a message has  been  lost  on  thechannel   S->R,  it  (R)  may  transmit  an  LMR  to  S  on  R->Scommunicating the fact of loss of messages.  When S receives  theLMR  for  the  control  link,  it must either retransmit the lostmessages,  or  "close"  the  connection.  (In  the   context   ofHost-to-Host protocol, closing the network connection for controllink  implies exchange of reset commands, which has the effect ofreinitializing all communication between R and S.)   For  controllinks,  S  does  not  have  the  option  of sending an LMS to thereceiver.  If S can not retransmit  the  lost  messages  then  itaborts  the  output  queue  (if  any)  for  the channel S->R, andinserts a Reset command at the break point.  Essentially, we  arespecifying  that  if  S  can not retransmit lost control messagesthen the error would be considered irrecoverable and fatal.   Alluser  communication  between  S  and  R  is  broken  and  must berestarted from the beginning.In the above paragraph, we considered the situation  in  which  Rwas  able to detect the loss of messages.  It is however possiblethat it is the last message transmitted on S->R that is lost.  Inthis  case,  R will not be aware of the loss.  In this situation,recovery can  be  initiated  only  if  S  can  either  positivelydetermine  or  simply  suspect  that a message has been lost.  Ingeneral, after having transmitted a control message, S  would  beexpecting  some  sort  of  response  from  R.  For  example, if Stransmits a Request-for-Connection (RFC) control message to R,  Sexpects  R  to reply either with a Close (CLS) command or anotherRFC.  If, after an appropriate time  interval has elapsed  and  Shas  received  no reply from R, our protocol specifies that S mayretransmit the control message.  In retransmitting,  S  must  use                    - 8 -the same C-channel and MSN values that were used for the originalmessage.    Since  R  can,  now,  receive  duplicate  copies,  westipulate that if R receives a duplicate of the message  that  ithas already received, it may simply ignore the duplicate.2.6 SOME OTHER PROBLEMSThere  are  two problems that have not yet been solved.  First, asending host will usually have only a limited  amount  of  bufferspace   in   which  it  can  save  messages  for  possible  laterretransmission.  So far, we have not provided any method by whicha  host  may  positively  determine  whether  the  receiver   hascorrectly received a certain message or not.  Thus it has no firmbasis  on  which  it  may  decide to release the space used up bymessages that have been already transmitted.  The second  problemis  created  by  our recycling the message sequence numbers.  Forthe MSN mechanism to work correctly, it is essential that at  anygiven  instant  of  time there be no more than 15 messages in thetransmission path.  If there were more than 15 messages, some  ofthese  messages  would have same MSN and LRN, and if one of thesemessages were to be lost, it would be impossible to identify  thelost  message.   However,  the second problem should not arise inthe ARPA Network, since the IMP sub-network will not  allow  morethan  eight  outstanding  messages between any host pair (NWG-RFC#660).We can solve both these problems by a simple yet highly  flexiblescheme.  In this scheme, there are two new control messages.  Oneof these, called R_equest S_tatusfrom S_ender (RSS), can be used bythe  sending  host to query the receiver regarding the receiver'ssynch-state.  The receiver can supply  its  copies  of  C-channelnumber  and  MSN for a transmission path by sending a S_tatusfromR_eceiver (SFR) control message over the control channel.  An  SFRprovides  positive  acknowledgement;  differing  with  the  usualacknowledgement schemes in  only  that  here  acknowledgement  isprovided  only upon demand.  Upon receiving SFR, the sender knowsexactly which messages have been properly delivered, and  it  mayfree  the  buffer  space used by these messages.  The RSS and SFRscheme can also be used to ensure that there  are  no  more  thanfifteen messages in the transmission path at any given time.                    - 9 -3.0 LOST MESSAGE DETECTION AND RECOVERY PROTOCOLThis  protocol  is  proposed  as an amendment to the Host-to-HostProtocol for the purpose of letting  hosts  detect  the  loss  ofmessages  in  the  network. It also provides  recovery proceduresfrom such losses.  This protocol is divided into two parts.  Part1 states the compatibility requirements.Part 2 states  the  newprotocol and must be implemented by hosts that desire to have theability  to  recover  from  loss of messages in the network.  Thereader  will  find  many  comments  interspersed  throughout  thedescription of this protocol.  These comments are not part of theprotocol and are provided solely for the purpose of improving thereader's understanding of this protocol.The  terminology used in this protocol is similar to that used inthe Host-to-Host protocol.  We speak of  a  "network  connection"between  a pair of hosts, called the "receiver" and the "sender."A network connection is described by a pair  of  socket  numbers,and  once  established, a network connection is associated with alink (which is described by a link number.)  A network connectionis a logical communication path and the link assigned to it is  aphysical  communication  path.   In  addition to links associatedwith the network connections, there are "control-links"  for  thetransmission  of  "control  commands."   When  we  use  the  term"connection" it may refer to either a network connection  or  thelink  assigned  to  it;  the context decides which one.  The term"links" encompasses the connection-associated-links  as  well  ascontrol-links.   Notice  that  a  receiver  of  a  connection maytransmit control commands regarding this connection.3.1 DEFINTIONS3.1.1 HOST TYPE "A"Those hosts that have not adopted the part  2  of  this  protocolamendment will be known as type A hosts.(Comment: All existing hosts are type A hosts.)3.1.2 HOST TYPE "B"Those  hosts,  that  adopt  the part 2 of this protocol amendmentwill be known as type B hosts.                   - 10 -3.1.3 MESSAGE SEQUENCE NUMBER (MSN)A four bit number associated with regular messages and  containedin  the  bits  25  through  28 of the Host-to-IMP and IMP-to-Hostleaders for regular messages [BBN Report No. 1822].  This  numberis  used  by  the  type  B hosts to detect loss of messages  on agiven link.  Type A hosts always set the MSN  (for  the  messagesthey  send out) to zero.  When in use by a type B host, the firstmessage on a link (after the connection has been established) hasthe MSN value of one.  For each successive message on this  link,the MSN value is increased by one until it reaches a value of 15.The next message has the MSN value of one.(Comments:  Type  B  hosts  will  use the MSN mechanism only whencommunicating with other type B  hosts.  If  a  type  B  host  iscommunicating   with  a  type  A  host,  the  type  B  host  willessentially simulate the behaviour of a type A host and use  zeroMSN values for this communication.)3.1.4 LINK RESYNCH NUMBER (LRN)The  Link Resynch Number is an eight bit number associated with alink and used for resynchronizing the communication.   For  linksassociated  with  a  network  connection (i.e. user links), it isintially set to zero.  For control links, it is set  to  zero  atthe  time  of  the  Network Control Program (NCP) initialization.For a given link, its current LRN value is copied  into  the  LRNfield  of  all messages sent out on the link.  The LRN values maybe manipulated by type B hosts in accordance  with  the  protocoldescribed later.(Comments:   Our  protocol  specifies  that for all communicationinvolving a type A host, the LRN value  will  never  change  fromzero.   Since the LRN field is presently unused, all hosts set itto zero even though they do not explicitly recognize  this  fieldas an LRN field.  This guarantees compatibility.)3.1.5 LRN FIELDAn  eight bit field in the bits 33 through 40 of the Host-to-Hostmessage header.                   - 11 -3.2 NEW CONTROL COMMANDS3.2.1 LMR - LOST MESSAGE FROM RECEIVER___8______8_______8_______8____|     I      I      I     II LMR | link | LRN  | MSN II______I_______I_______I______I_The LMR command is sent by a receiving host to  let  the  sendinghost  know  that  one  or  more messages have been lost.  The MSNfield specifies the message sequence number of the first  messagelost.   The  LRN  field  specifies the new LRN value that must beused if and when communication is restored.(Comments:  As will be seen later, the LMR command also  has  theeffect of resetting the bit and message allocation in the sendinghost   to   zero.   In  order  to  permit  a  sender  to  restorecommunication, an LMR command will be usually accompanied with anallocate command.  However notice  that  these  comments  do  notapply  to  the  control  links  because  there  is  no allocationmechanism for the control links.)3.2.2 LMS - LOST MESSAGE FROM SENDER____8_________8________8__________8_________8_____I        I       I        I         I       II  LMS   I Link  I  LRN   I  MSN    I COUNT II_________I________I_________I__________I________I_This command is sent by a sender host in reply to an LMR  commandif it (the sender) can not retransmit the lost messages specifiedby  the LMR command.  The purpose of this command is to query thereceiver whether or not  the  loss  of  messages  is  acceptable.After  sending  this command, the sender waits for a reply beforetransmitting any messages over the link involved.   This  commandmay  not  be  sent for control links.  The LRN and MSN values aresame as those specified by the LMR command.  COUNT specifies  thenumber of messages lost.3.2.3  LMA - LOSS OF MESSAGES ACCEPTABLEThis  command  is  identical  to  the  LMS command accept for thecommand code.  Upon receipt of an LMS  command,  a  receiver  may                   - 12 -send  this command to the sender to let the sender know that lossof messages is acceptable.  All fields in this command are set tocorresponding values in the LMS command.3.2.4  CLS2 - CLOSE2____8___________3_2_______________3_2_____________8_______8_____I       I              I                 I       I      II CLS2  I  my socket   I your socket     I  LRN  I MSN  II________I_______________I__________________I________I_______I_The CLS2 command is similar to the current CLS command except forthe LRN and MSN fields included in the  new  command.   Both  thereceiving and sending hosts copy their values of LRN and MSN intothe CLS2 command.  Upon receiving a CLS2 command, a host comparesthe LRN and MSN values contained in the CLS2 command with its ownvalues  for  the  connection  involved.   If  these values do notmatch, then an  error  has  occurred  and  a  host  may  initiaterecovery procedures.(Comments:   The  purpose  of  this command is to ensure that thelast message  transmitted  on  a  connection  has  been  receivedsuccesfully.)3.2.5 ECLS - ERROR CLOSE_____8___________3_2___________3_2_________I        I             I             II  ECLS  I my socket   I  your socketII_________I______________I______________I_The  ECLS  command  is similar to the current CLS command.  It isused  for   closing   connections   which   have   sufferred   anirrecoverable loss of messages.(Comments: A connection may be closed in any one of the followingthree ways:      1. A connection which has not yet been opened  succesfullymay  be  closed  by  the  CLS command.  All connectionsinvolving type A hosts must be  closed  using  the  CLScommand.      2. Connections between type B hosts may  be  closed  usingCLS2  command.   A connection is considered closed onlyif matching CLS2 commands have been  exchanged  between                   - 13 -the sender and the receiver.      3. Those connections  between  type  B  hosts,  that  havesufferred  an  irrecoverable  loss of messages, must beclosed by the ECLS command.)3.2.6 RSS - REQUEST STATUS FROM SENDER____8_______8______I      I        II RSS  I LINK   II_______I_________I_A sending host may issue an RSS command to  find  out  about  thestatus  of transmission on a particular connection or the controllink.3.2.7  RSR - REQUEST STATUS FROM RECEIVER____8_________8_____I       I        II RSR   I LINK   |I________I_________I_A receiver can issue an RSR command to find out about the  statusof  transmission  on a particular connection or the control link.3.2.8 SFR - STATUS FROM RECEIVER____8_________8_________8_________8____I        I        I        I       II SFR    I  LINK  I  LRN   I MSN   II_________I_________I_________I________I_A receiving host may issue this  command  to  inform  the  senderabout  the  state of a particular connection or the control link.3.2.9 SFS - STATUS FROM SENDER                   - 14 -____8_________8_________8_________8____I        I        I        I       II SFS    I  LINK  I  LRN   I MSN   II_________I_________I_________I________I_A sending host may issue this  command  to  inform  the  receiverabout  the  state of a particular connection or the control link.3.3  THE PROTOCOL3.3.1 PART ONEAll type A hosts must use zero MSN and LRN values on the messagessent out by them.  When communicating with a host of  type  A,  atype B host must simulate the behaviour of type A host.(Comments:   Notice  that  this  simulation is not complicated atall.  All that  is  required  is  that   hosts  that  adopt  thisprotocol  must  not use it when communicating with the hosts thathave not adopted it.)3.3.2 PART TWOThis part of the protocol is stated as a set of rules which  mustbe  observed  by  all  type B hosts when communicating with othertype B hosts.3.3.2.1 RESPONSIBILITIES OF HOSTS AS SENDERS    (1). A type B sending host must use message sequence numberson all regular messages that it sends to other  type  Bhosts  as  specified  in  the definition of the messagesequence numbers (Section 3.1.3).    (2). A type B sending host must use link resynch numbers  onall  regular  messages  that  it  sends to other type Bhosts as specified in the definition  of  link  resynchnumber (Section 3.1.4).    (3). A sending host may retransmit a message if it  suspectsthat  the  message  may  have  been lost in the networkduring previous transmission.    (4). A sending host may issue an RSS command to the receiverto determine the state of transmission on any link.    (5). A sending host must use the ECLS  command  to  close  aconnection, if the connection is being closed due to an                   - 15 -irrecoverable  transmission  error.  Otherwise, it mustthe CLS2 command.3.3.2.2 RESPONSIBILITIES OF HOSTS AS RECEIVERS    (1). A receiver host will maintain LRN and  MSN  values  foreach link on which it receives messages.  Initial valueof  LRN  will be zero, and initial value of MSN will beone.   For  each  receive  link,  the  host  should  beprepared  to  receive a message with LRN and MSN valuesspecified by its tables.  When the  host  has  receivedthe  expected  message  on a given link, it will changeits table MSN value as specified in the  definition  ofMSN.    (2). On a given link, if a host receives a message  with  anLRN  value  smaller than the one in use, it will ignorethe message.    (3). If a host receives a duplicate message  (same  LRN  andMSN values), it will ignore the duplicate.    (4). A host will examine  the  MSN  values  on  all  regularmessages  that  it receives to detect loss of messages.If on any link, one or more messages are found missing,it will concern itself with only the first message lostand take the following series of action:       1. Increase its own LRN value for this  link  by          one.       2. Send an LMR command to the sending host  with          LRN  field set to the new value and MSN field          set to  the  sequence  number  of  the  first          message lost.       3. Realizing that LMR  command  will  cause  the          allocation  to be reset to zero, it will send          more allocation. This is  not  applicable  to          the control links.However,  if  a  host  does  not  want  to initiate therecovery procedures, it may simply close the connectionby an ECLS command.    (5). A receiver host may  issue the RSR command to determinethe state of transmission on any link.    (6). If a connection is being closed due to an irrecoverableerror, a receiving host  must  use  the  ECLS  command.Otherwise it must use the CLS2 command.                   - 16 -3.3.2.3  SENDING HOST'S RESPONSE TO CONTROL MESSAGES    (1). RSR command: the sender must transmit a SFS command  tothe receiver for the link involved.    (2). ECLS command: The sender must cease transmission, if ithas  not  already done so, and issue an ECLS command ifit has  not  already  issues  either  a  ECLS  or  CLS2command.    (3) CLS2 command: The sender must compare the  LRN  and  MSNvalues  of  the CLS2 command with its own values of theLRN and MSN for the connection involved.  If  an  erroris  indicated,  it may either close the connection withan ECLS, or initiate recovery action  as  specified  inthesection 3.3.2.1.    (4). LMR command for  a  connection  (i.e.,  not  a  controllink):  The  sender may follow any one of the followingthree courses of action:       1. Close the connection with an ECLS command.       2. Set the allocations for the link involved  to          zero,  set  LRN  to that specified in the LMR          command, and  restart  communication  at  the          point of break.       3. Set the allocations for the link involved  to          zero,  set  the  LRN to that specified in the          LMR command, and send an LMS command  to  the          receiver  host informing him that one or more          of   the   lost   messages   can    not    be          retransmitted.  After sending an LMS command,          a  sending  host  must  not transmit any more          messages  on  the  link  involved  until  and          unless  it  receives  an LMA command from the          receiver host.(Comments:  As  we  have  mentioned  before  (Section  2.3),  thedecision  regarding which course of action to follow depends upona number of factors.  For example, if a host has implemented onlythe detection of lost messages aspect of  our  protocol  (and  norecovery),  then  it  will  chose the first option of closing theconnection.)    (5). LMR for a control link: The sender may take one of  thefollowing two actions:       1. Set the LRN to  that  specified  in  the  LMR          command  and  begin  retransmission  of  lost          messages       2. Set the LRN to  that  specified  by  the  LMR          command,  and  insert  a Reset command at the          break point.                   - 17 -(Comment:  If a sending host can not retransmit messages lost  ona   control   link,   then   this   protocol  requires  that  allcommunication between the two host be broken, and  reinitialized.We do not explicitly specify the actions that are associated withthe  exchange  of Reset commands.  These actions are specified bythe Host-to-Host protocol.)    (6). LMA command:  When  a  sending  host  receives  an  LMAcommand  matching  an  LMS command previously issued byit, it may resume transmission.(Comments: The protocol does not require the sending host to takeany specific action with regard to a SFR. However, a sending hostmay use the information contained in the  SFR  command  regardingthe  state of transmission.  From a SFR command a sender host maydetermine what messages have been received properly.  The  sendermay   use  this  information  to  cleanup  its  buffer  space  orretransmit messages that it might suspect are lost.)3.3.2.4 RECEIVING HOST'S RESPONSE TO CONTROL MESSAGES    (1). RSS command: A receiver is obligated to transmit a  SFRto the sender for the link involved.    (2). ECLS command:  The receiver must close  the  connectionby  issuing  an ECLS command if it has not already doneso.    (3). CLS2 command: A receiver must compare the LRN  and  MSNvalues  of  the  command  with  its  own values for theconnection involved.  If an error is indicated, it  mayeither  close  the  connection  by  an  ECLS command orinitiate recovery procedures as  specified  insection3.3.2.2.    (4). LMS command: The receiver may take one of the followingtwo courses of action:     (1). Close the connection  specified  by  the  LMS          command, by issuing an ECLS command.     (2). Set the  link  involved  to  be  prepared  to          receive  messages  starting with the sequence          number MSN + COUNT, where MSN and  COUNT  are          those   specified   by   the   LMS   command.          (Comment: This action implies  that  receiver          is  willing  to  accept  the loss of messages          specified by the LMS command.)(Comments: The protocol does not require the receiver to take anyspecific action with regard to a SFS command. However a  receiver                   - 18 -host may use the information  contained in it.)4.0 CONCLUDING REMARKSThe  design  of  this  protocol  has been governed by three majorprinciples.  First, we believe that to be useful within the  ARPANetwork,  any  new  protocol must be compatible with the existingprotocols, so that each host can make the transition to  the  newprotocol at its own pace and without large investment.  Secondly,the  protocol  should  tie  into  the  recovery  mechanism of theIMP-to-Host Protocol.  The price we pay for this is the small MSNfield and a   message oriented protocol rather than a byte streamoriented protocol.  The third consideration has been flexibility.While this protocol guarantees detection of  lost  messages,  thephilosophy  behind  the recovery procedures is that a host shouldhave several options, each option providing a different degree ofsophistication.  A host can implement a recovery  procedure  thatis  most  suitable  for  its  needs  and  the capabilities of itsmachine.  Even though two hosts may  have  implemented  differentrecovery  procedures,  they  can communicate with each other in acompatible way.  In a network of independent machines  of  widelyvarying  capabilities and requirements, this seems to be the onlyway of implementing such a protocol.  Even though  this  protocolprovides  a  variety  of  options in a given error situation, thechoice of a specific action must be  consistent  with  the  basicrequirements  of  the  communication  path.  For example, partialrecovery is not  acceptable  during  file  transfers.   We  fullyexpect   the  File  Transfer  Protocol  to  specify  that  if  anirrecoverable error occurs, the file transfer must be aborted.                   - 19 -