doc: Add RFC documents

1 files changed, 332 insertions, 0 deletions

diff --git a/doc/rfc/rfc700.txt b/doc/rfc/rfc700.txt
new file mode 100644
index 0000000..3323548
--- /dev/null
+++ b/doc/rfc/rfc700.txt
@@ -0,0 +1,332 @@
+
+NWG/RFC 700                                                  August 1974
+NIC 31020
+INWG Experiments Note 1
+
+                   A Protocol Experiment
+
+
+                       Eric R. Mader
+                     William W. Plummer
+                    Raymond S. Tomlinson
+
+
+
+I.  Introduction
+
+In early February, 1974 the main line  printer  on  BBN's  TENEX  system
+failed and it was decided to use the PDP-11 line printer via the ARPANET
+both for the direct purpose of obtaining listings and also the  indirect
+purpose of studying network protocols.
+
+
+
+II.  The Basic Protocol
+
+The design was based on the protocol described by Cerf and Kahn in  INWG
+Note  #39.  Familiarity with that document is assumed.  The following is
+a brief sketch of the protocol.  Not  all  features  described  in  this
+section have been implemented.  See Section VI.
+
+At any instant, the sender has two pointers into the stream of bytes  to
+be  sent.   Bytes to the left of the LEFT pointer have already been sent
+and acknowledged.  Bytes in the "window"  between  the  LEFT  and  RIGHT
+pointers  have  been  sent  (zero  or  more times), but no indication of
+successful transmission has been received.  Bytes to the right of  RIGHT
+remain to be considered at some time in the future.
+
+In operation the sender is constantly sending bytes from the input  data
+stream   resulting   in   the   RIGHT   pointer   advancing.    Positive
+acknowledgements produced by the receiver cause the  LEFT  edge  of  the
+window to move towards the RIGHT edge.
+
+LEFT and RIGHT are actually numerical byte  positions  within  the  data
+stream.   The low order 16 bits of RIGHT are sent with each message as a
+sequence number so that the receiver can identify which part of the data
+stream  it  is  receiving  in case messages are not received in the same
+order they were transmitted.  The receiver has a finite amount of buffer
+space  available  in which it can reassemble an image of the data in the
+transmitter's window.  The receiver discards  any  messages  which  have
+sequence  numbers  outside of its buffer area.  However, messages to the
+left of LEFT must  be  acknowledged  even  though  they  are  discarded.
+Otherwise,  a  lost  ACK  would  cause the sender to retransmit (and the
+receiver ingore) the message indefinitely.  Messages received  with  bad
+checksums are also discarded.
+
+As "good" messages are received, the holes are filled in the  receiver's
+buffer  and  continuous  segments  at  the  left  edge are passed to the
+physical line printer (in our case).  The receiver informs the sender of
+
+                                                    Page   2
+
+
+
+this  action  by sending an ACK (acknowledgement) message.  This message
+specifies the sequence number of the byte it would like to receive  next
+(the  new  value of LEFT in the sender) and the current amount of buffer
+space it has available (new maximum window width in  the  sender).   The
+sender  ignores  ACK's  to  the  left of LEFT and to the right of RIGHT.
+Thus, both the sender and  receiver  are  prepared  to  handle  multiple
+copies of messages.
+
+Failures such as messages  with  bad  checksums,  messages  lost  during
+transmission  (data  and ACK's), and messages discarded due to sequences
+numbers which were apparently out of range, all manifest  themselves  to
+the sender as a dropped ACK.  A dropped ACK will cause the sender's LEFT
+edge to stop advancing, leaving the unacknowledged message at  the  left
+of the sender's window, and possibly a corresponding hole at the left of
+the receiver's image of the window.  Eventually, transmission will cease
+and   a  (10  second)  timeout  will  trigger  in  the  sender,  causing
+retransmission of all data within the window.  Note that at the  instant
+of  a  timeout,  there is no guarantee that the un-ACK'd message will be
+exactly at the  left  edge  of  the  window  or  that  it  is  the  only
+unacknowledged  message  in  the  window.  Retransmissions are likely to
+cause the receiver to see data that it has seen  before,  but  duplicate
+messages will be discarded due to sequence number considerations.
+
+
+
+III.  "Say Again"
+
+An extension to the INWN #39 protocol  which  was  implemented  was  the
+ability to let the receiver force retransmission of the entire window by
+turning on a flag in any message back to the sender.  This is useful  in
+cases  where  the receiver believes that a data message has been dropped
+and it wants to force retransmission rather than wait for a  timeout  in
+the sender.  Clearly, this relies on the network to preserve ordering of
+the messages.  Also, it is not useful if the error rate is high  because
+the  whole  window  is retransmitted in order to get retransmission of a
+single message or two.
+
+
+
+IV.  Establishing an Association
+
+In the experiment two flags were used to establish an association.  FRST
+(FiRST  flag)  was  the equivalent of SYN described in INWG Note #39 and
+served to identify the first message of an association.  This instructed
+the  receiver  to  accept  the  sequence  number  in  the  message  as a
+definition  of  the  starting  point  of  sequence   numbers   for   the
+association.
+
+The second flag is a receiver-to-sender  flag  called  HUH  which  is  a
+request  by the receiver for a definition of the sequence numbers.  Upon
+receipt of a message containing an HUH, the sender responds  by  turning
+on  FRST  in  the  next data message.  Normally, HUH is sent only if the
+receiver had been restarted, or if it is replying to messages on a  port
+
+                                                    Page   3
+
+
+
+that it knows is not part of an association.
+
+
+
+V.  A Problem
+
+A  severe  problem  uncovered  with  the  protocol  was  concerned  with
+establishing  an  association.   If  the  PDP-11 (receiver) was reloaded
+while the spooler (sender) was running, the first few pages of the  data
+stream  were  printed  about  six  times  before  normal  operation  was
+established.  The cause was traced to the following sequence of actions:
+
+
+          1.   The  sender  would  be  in  a  loop,   timing   out   and
+          retransmitting because the receiver had not responded.
+
+          2.  Upon being restarted,  the  receiver  would  see  a  whole
+          window's worth of messages, and respond to each with an HUH.
+
+          3.  For each HUH the sender would reset the window and include
+          a  FRST  flag  with  the  first  message  in each of the (six)
+          retransmissions.
+
+          4.  The receiver would see the  first  message  of  the  first
+          retransmission  containing a FRST, accept the sequence number,
+          and print the data  from  that  and  the  following  messages.
+          Then,  another  message  containing the FRST flag would appear
+          and the cycle would repeat (five more times).  Note  that  the
+          ACK's  generated in the repetitions were ignored by the sender
+          because they were to the left of the window.
+
+
+As a "cure" for the above the receiver  program  was  modified  so  that
+after  sending  an  HUH, messages are ignored until one with a FRST flag
+appears.  This solution is unacceptable in general because it leaves the
+receiver  port  useless  if either the message containing the HUH or the
+response gets lost in transmission.  Although  a  timeout  was  used  to
+guard against this, the timeout cannot be trusted because it might cause
+two messages with FRST flags to be received -- just the problem which is
+being avoided!
+
+An alternate cure which does not depend on the network  to  be  lossless
+would  be  to  modify  the  sender  to  respond to a HUH by ignoring all
+messages for at least  a  round  trip  delay  time  before  sending  its
+response  containing  the  FRST  flag.  This results in having to define
+what this time is.  In general this cannot be  done  when  messages  can
+become  trapped  for  indefinite  amounts of time in network partitions.
+This will be discussed more fully in a subsequent document.
+
+                                                    Page   4
+
+
+
+VI.  Features not Investigated
+
+None of the programs  to  date  have  supported  any  of  the  following
+features:
+
+
+          1.  Window size control.  The window size was a constant (2048
+          bytes).  In a future experiment the window size will be varied
+          not only by indications of buffer space in the  receiver,  but
+          also as a function of estimated transit time.  (see below).
+
+          2.  Reassembly.  Since reassembly is conceptually easy, it  is
+          likely to be one of the first extensions.  A message corrupter
+          will be included in the receiver to test  the  functioning  of
+          the reassembly mechanism.
+
+          3.  Expanded Internetwork Addresses
+
+          4.  Multiple Associations
+
+          5.  Reliable Making and Breaking of Associations
+
+
+
+VII.  Implementations Notes
+
+The sender involves approximately ten pages of  assembly  code  for  the
+network  message interface.  Two processes are involved: one which fills
+a buffer by reading the input data stream, and a  second  process  which
+sends  network  messages  from the buffer and processes replies from the
+receiver.  The two processes are joined by a coroutine mechanism, but in
+the future will be two parallel TENEX processes.
+
+The receiver program consists of approximately four pages of  BCPL  code
+in  addition  to IO device drivers and routines which implement queueing
+primitives.
+
+Each message contained between zero and 255 bytes of data arranged (as a
+coding  convenience) in a way which is directly compatible with the BCPL
+string handling routines.  Messages contained a single byte of  checksum
+which was the low eight bits of the twos complement negation of the twos
+complement sum of all other bytes in the  message.   We  recommend  that
+some  more  reliable  checksum  function be employed in the future; even
+using eight-bit ones complement arithmetic would be better.
+
+Source files for the various programs are available from the authors  at
+Bolt Beranek and Newman, 50 Moulton Street, Cambridge Mass., 02138.
+
+                                                    Page   5
+
+
+
+VIII.  Simple Rate Calculations
+
+If we assume that an active association has reached steady  state,  that
+processing delays are lumped into the transit time T, and that there are
+no errors, then the maximum data rate may be calculated as follows.
+
+Assume the sequence numbers being passed by the RIGHT pointer  are  some
+function  of  time, R(t).  Messages received by the receiver will be the
+same function of time but delayed T (a  transit  time)  seconds.   Since
+processing  time  is  zero,  the  acknowledgments  will  bear  this same
+function, R(t-T).  Acknowlegements received  by  the  sender  will  have
+sequence numbers R(t-2T).
+
+Acknowledgements at the sender determine the LEFT pointer, L(t).   Also,
+it  is known that R(t) is ahead of L(t) by the width of the window which
+is a constant in steady state.  Thus, we have the two relations:
+
+                    L(t) = R(t-2T)
+                    L(t) = R(t) - W
+
+Now, let R(t) = Bt, i.e., sequence numbers are increasing linearly  with
+time.  (Microscopically, short bursts will alternate with longer periods
+of inactivity, but the average bandwidth will be B.)  The  result  under
+the assumptions is that the bandwidth is:
+
+                    B = W/2T .
+
+That is, the bandwidth in bytes per second  is  just  the  steady  state
+window width divided by the round trip delay time.  Conversely, the aboe
+relation can be determine the buffer sized needed: in  oreder  for  thee
+receiver  to  guarantee  to  accept information that was transmitted, it
+must supply buffering equal to (or greater than) the window  size.   The
+window size must be equal to or greater than the desired bandwidth times
+the round-trip delay time, i.e.  equal to the number of  messages  in  a
+round-trip "pipeline".
+
+The bandwidth in the presence of a relatively  low  error  rate  may  be
+calculated.   Assume  that  B  and  W  are  expressed in terms of (full)
+messages rather than byte numbers.  Each error has two effects:  a  time
+out  delay  of D seconds and retransmission of W messages.  So, the time
+Q(M,N) required to transmit M messages burdened by N errors is  the  sum
+of  the  time  to transmit the data once, N*D seconds of time out delay,
+and the time to transmit the window N more times.
+
+                    Q(M,N) = (2T/W)*M + N*D + N*2T
+
+Dividing by M to get time per message and multiplying the last  term  by
+(W/W):
+
+                    Q(M,N)/M = (2T/W) + (N/M)*D + (2T/W)*(N/M)*W .
+
+But (M/N) is just the fraction of messages in error.  Call this E.
+
+                                                    Page   6
+
+
+
+                    Q(E) = (2T/W)*(1 + EW) + ED
+
+                    B(E) = 1/[(2T/W)(1+EW) + ED]
+
+The advantage to using the "say again" mechanism (Section III.) can  now
+be seen: it forces D to be zero, allowing a reasonable average data rate
+in the presence of errors.  Note the effect of a 10 second time out on a
+network  with  an  E  of 0.01, assuming W to be 20 messages and T of 0.5
+second.  B(D=10) is 6.7, but with forced retransmission, B(D=0) is 20.
+
+
+
+IX.  A Sequence Number Consideration
+
+In order to reject duplicate messages, sequence numbers must  contain  a
+sufficient  number  of  bits such that it is impossible to cycle through
+more than half the sequence  number  space  in  a  message  lifetime  at
+maximum transmission rate.  Assuming a 1 MegaByte per second network and
+a maximum lifetime of 500 seconds, the sequence  number  field  of  each
+message must be capable of holding the number 2*500*10**6 which is 10**9
+or about 2**30.  Thus,  a  32-bit  (4-byte)  sequence  number  field  is
+recommended.
+
+
+
+X.  Additional Control Functions
+
+In response to an attempt to establish an association (SYN) it  is  felt
+that the receiver should be able to deny the attempt (RELease) in one of
+the following three ways:
+
+          REJECT.  (I'm busy.  Try again later.)
+          ABORT.  (I don't understand what you are sending.
+                    (Bad port, etc.))
+          ABNORMAL (SYN arrived on a established connection.)
+                    (Receiver breaks connection and issues this REL.)
+
+During an established association, the sender should be able to  RELease
+the association in either of these ways:
+
+          DONE.  (I'm done sending to you.)
+          GAG.  (Stop.  You are sending garbage (ACK's).)
+
+These may be coded as combinations  of  bits  in  the  FLAGS  which  are
+convenient for programming.
+
+
+
+
\ No newline at end of file