[ih] ARPAnet Type 3 packets (datagrams)

[Noel Chiappa]

    > From: Vint Cerf <vint at google.com>

    > noel, wrong on your analysis of the RFNM.

I think we are running into a problem which I _think_ is because the
network behavior changed over time, because if I'm understanding you
properly (and perhaps I'm not) I can't square this with what the 1822 spec
from the early TCP/IP period says?

Let me transcribe what the various documents say, as a background, to help
us sort this out. From the 1822 spec, pg. 3-6, 5/1978 edition:

  "The maximum number of messages which a Host is permitted to have 'in
  transit' on any connection [for others - 'connection' is not anything
  like a VC connection, but an 1822-specific term earlier defined
  as the combination of destination IMP, host-on-IMP, and something called
  the 'handling type', which included a priority bit - JNC]
  is eight. In other words, if a Host attempts to transmit nine
  messages on any connection, the interface will be blocked by the IMP
  during transmission of the ninth message until a RFNM (or Incomplete
  Transmission) is returned for the first message. However, this rule
  does not prohibit one Host from having eight messages in transit to
  Host 'A', eight more in transit to host 'B', etc., simultaneously."

I note from the famous Heart/Kahn/etc IFIPS paper (SJCC, 1970, pp. 551-567)
that this was not the original behaviour, and perhaps that is the source of
the confusion we are having; that paper says (pg. 553):

  "The subnet accepts only one message at a time on a given link. Ensuing
  messages on that link will be blocked from entering the subnet until
  the source IMP learns that the previous message has arrived at the
  destination Host. When a link becomes unblocked, the subnet notifies
  the source Host by sending it a special control message know as a []
  RFNM, which identifies the newly unblocked link. The source Host may
  utilize its connection into the subnet to transmit messages over other
  links, while waiting to send messages on the blocked links. Up to 63
  separate outgoing links [this was of course the limit in the 32-bit
  leader days - JNC] may exist at any Host site. ... Because the subnet
  allows only one message at a time on a given link, Hosts never receive
  messages out of order."

It seems that this rate-limiting mechanism was quickly changed, for a
variety of reasons. (Whether or not it was realized that the 'single
outstanding packet' model limited the maximum throughput to {packet-size /
RTT} I don't know - the documentation I have is not clear on this.)

The 1972 McQuillan/Crowther/etc paper (FJCC, 1972, pp. 741-754) say (pp.
743-744):

  "To replace the per-link sequence [and flow - JNC} control mechanism,
  we decided upon a sequence control mechanism based on a single logical
  'pipe' between each source and destination IMP. ... Hosts may, if they
  chose, have several messages oustanding simultaneously to a given
  destination.."

When exactly the 8 message limit came in I'm not sure; the 1972 paper doesn't
talk of it, so it must have been later. (I consulted the 'A History of the
ARPANET: The First Decade', but that is short on technical detail, and doesn't
say.)

    > RFNM refers to MESSAGE (that is what the host sends). the Host does
    > not get to send anything until it gets a RFNM (or Incomplete
    > Transmission I guess) from the last MESSAGE, no matter how long or
    > short the message was.
    > ...
    > The full MESSAGE is sent to the IMP from the Host and the Host is
    > blocked until it gets a RFNM or Incomplete. 

I read you as saying here that when a host sent a message, it didn't get
to send another message until it got a RFNM from the message it just sent.
Am I understanding you correctly? If so, this does not seem to square with
1822, which says you could send up to eight before you have to wait for
the "RFNM ... for the first message".

Of course, you _are_ correct about the behaviour earlier, but the
single-packet-per-link restriction had been removed by the time of even the
earliest TCP/IP work.


    > A single packet message served as an automatic "get a block"
    > request. A multipacket message does the "get a block" routine.

>From the 1972 FJCC paper, the original 1970 network did not have this
allocation mechanism; it was introduced after lockups appeared (the
destination IMP had frames from many different messages, but not enough
free buffers to reassmble a complete message and transmit it to the Host).

(Interestingly, it appears my memory is also buggy - I had thought that
for multi-frame messages, the buffer request was piggybacked on the first
frame, which was sent immediately, but that is not so. I must have
conflated the piggybacking that occurs elsewhere, together with the
'messages small than a frame are sent as their own request', to produce
that erroneous memory.)

More interestingly, single-frame messages _were_ acknowledged on an end-end
(i.e. source IMP - destination IMP) basis; this was because such messages
could be discarded by the destination IMP if it did not have sufficient
buffering to hold them until it could send then to the host. So only
multi-frame messages were not held at the source until the destination
acknowledged them - an interesting mix of end-end and hop-by-hop reliabilty!

	Noel