RFC relevance of acknowledge

As per Relevance of the word acknowledge, we have this rfc below:

Network Working Group Richard Schantz (BBN-TENEX
Request for Comments: 672 Dec 1974
NIC #31440

A Multi-Site Data Collection

Preface

This RFC reproduces most of a working
prepared during the design and implementation of
protocols for the TIP-TENEX integrated system
handling TIP accounting. Bernie Cosell (BBN-TIP
and Bob Thomas (BBN-TENEX) have contributed
various aspects of this work. The system has
partially operational for about a month on
hosts. We feel that the techniques described
have wide applicability beyond TIP accounting.

Section

Protocols for a Multi-site Data Collection

The development of computer networks has provided
groundwork for distributed computation: one in which a job or
is comprised of components from various computer systems. In
single computer system, the unavailability or malfunction of any
the job components (e.g. program, file, device, etc.)
necessitates job termination. With computer networks, it
feasible to duplicate certain job components which previously had
basis for duplication. (In a single system, it does not matter
many times a process that performs a certain function is duplicated
a system crash makes all unavailable). It is such
duplication that enables us to utilize the network to achieve
reliability and load leveling. In order to realize the potential
resource duplication, it is necessary to have protocols
provide for the orderly use of these resources. In this document
we first discuss in general terms a problem of protocol
for interacting with a multiply defined resource (server).
problem deals with providing a highly reliable data
facility, by supporting it at many sites throughout the network.
the second section of this document, we describe in detail
particular implementation of the protocol which handles the
of utilizing multiple data collector processes for
accounting data generated by the network TIPs. This example
illustrates the specialization of hosts to perform parts of
computation they are best equipped to handle. The large
hosts (TENEX systems) perform the accounting function for the
network access TiPs

The situation to be discussed is the following: a
generating process needs to use a data collection service which
duplicately provided by processes on a number of network machines
A request to a server involves sending the data to be collected

An Initial

The data generator could proceed by selecting a
server and sending its request to that server. It might also
the attitude that if the message reaches the destination host (
communication subsystem will indicate this) the message will
properly processed to completion. Failure of the request
would then lead to selecting another server, until the
succeeds or all servers have been tried

-2-

Such a simple strategy is a poor one. It makes sense
require that the servicing process send a positive
to the requesting process. If nothing else, the reply
that the server process itself is still functioning. Waiting
such a reply also implies that there is a strategy for
another server if the reply is not forthcoming. Herein lies
problem. If the expected reply is timed out, and then a new
is sent to another server, we run the risk of receiving
(delayed) original acknowledgement at a later time. This
result in having the data entered into the collection system
(data duplication). If the request is re-transmitted to the
server only, we face the possibility of not being able to access
collector (data loss). In addition, for load leveling purposes,
may wish to send new requests to some (or all) servers. We can
use their reply (or lack of reply) as an indicator of load on
particular instance of the service. Doing this without
duplication requires more than a simple request and
protocol*.

Extension of the

The general protocol developed to handle multiple
servers involves having the data generator send the data request
some (or all) data collectors. Those willing to handle the
reply with an "I've got it" message. They then await
notification before finalizing the processing of the data. The
generator sends a "go ahead" message to one of the
collectors, and a "discard" message to all other
collectors. The "go ahead" message is the signal to process
data (i.e. collect permanently), while the "discard"
indicates that the data is being collected elsewhere and should
be retained

The question now arises as to whether or not the
process should acknowledge receipt of the "go ahead" message with
reply of its own, and then should the generator process
this acknowledgement, etc. We would like to send as few messages
possible to achieve reliable communication. Therefore, when a
--------------------

* If the servers are independent of each other to the extent that
two or more servers all act on the same request, the end result
the same as having a single server act on the request, then a
request/acknowledgement protocol is adequate. Such may be the case
for example, if we subject the totality of collected data (i.e.
data collected by all collectors for a certain period) to
duplicate detection scan. If we could store enough context in
entry to be able to determine duplicates, then having two or
servers act on the data would be functionally equivalent
processing by a single server

-3-

is reached for which further acknowledgements lead to a
visited state, or when the cost of further acknowledgements
the increase in reliability they bring, further
become unnecessary

The initial question was should the collector
acknowledge the "go ahead" message? Assume for the moment that
should not send such an acknowledgement. The data generator
verify, through the communication subsystem, the transmission of
"go ahead" message to the host of the collector. If this
did not arrive correctly, the generator has the option
re-transmitting it or sending a "go ahead" to another
which has acknowledged receipt of the data. Either
involves no risk of duplication. If the "go ahead" message
correctly, and a collector acknowledgement to the "go ahead"
is not required, then we incur a vulnerability to (collector host
system crash from the time the "go ahead" message is accepted by
host until the time the data is totally processed. Call the
processing time P. Once the data generator has selected
particular collector (on the basis of receiving its "I've got it
message), we also incur a vulnerability to malfunction of
collector process. The vulnerable period is from the time
collector sends its "i've got it" message until the time the data
processed. This amounts to two network transit times (2N) plus
and host overhead for message delivery (0) plus data processing
(P). [Total time=2N+P+O]. A malfunction (crash) in this period
cause the loss of data. There is no potential for duplication

Now, assume that the data collector process must
the "go ahead" message. The question then arises as to when such
acknowledgement should be sent. The reasonable choices are
immediately before final processing of the data (i.c. before
data is permanently recorded) or immediately after final processing
It can be argued that unless another acknowledgement is required (
the generator to the collector) to this acknowledgement BEFORE
actual data update, then the best time for the collector
acknowledge the "go ahead" is after final processing. This is
because receiving the acknowledgement conveys more information if
is sent after processing, while not receiving it (timeout),
either case, leaves us in an unknown state with respect to the
update. Depending on the relative speeds of various network
system components, the data may or may not be permanently entered
Therefore if we interpret the timeout as a signal to have the
processed at another site, we run the risk of duplication of data
To avoid data duplication, the timeout strategy must only
re-sending the "go ahead" message to the same collector. This
only help if the lack of reply is due to a lost network message
Our vulnerability intervals to system and process malfunction
as before

It is our conjecture (to be analyzed further) that any
acknowledgements to these acknowledgements will have virtually
effect on reducing the period of vulnerability outlined above.
such, the protocol with the fewest messages required is superior

-4-

Data Dependent Aspects of the

As discussed above, a main issue is which process should be
last to respond (send an acknowledgement). If the data
sends the last message (i.e. "go ahead"), we can only check on
correct arrival at the destination host. We must "take on faith
the ability of the collector to correctly complete the transaction
This strategy is geared toward avoiding data duplication. If on
other hand, the protocol specifies that the collector is to send
last message, with the timeout of such a message causing the
generator to use another collector, then the protocol is
toward the best efforts of recording the data somewhere, at
expense of possible duplication

Thus, the nature of the problem will dictate which of
protocols is appropriate for a given situation. The next
deals in the specifics of an implement;tion of a data
protocol to handle the problem of collecting TIP accounting data
using the TENEX systems for running the collection server processes
It is shown how the general protocol is optimized for the
data collection

Section

Protocol for TIP-TENEX Accounting Server Information

Overview of the

When a user initially requests service from a TIP, the TIP
perform a broadcast ICP to find an available RSEXEC which
an authentication data base. The user must then complete s
sequence in order to authenticate himself. If he is successful
RSEXEC will transmit his unique ID code to the TIP. Failure
cause the RSEXEC to close the connection and the TIP to hang up
the user. After the user is authenticated, the TIP will
accounting data for the user session. The data includes a count
messages sent on behalf of the user, and the connect time for
user. From time to time the TIP will transmit
accounting data to Accounting Server (ACTSER) processes
throughout the network. These accounting servers will
files containing intermediate raw accounting data. The
accounting data will periodically be collected and sorted to
an accounting data base. Providing a number of accounting
reduces the possibility of being unable to find a repository for
intermediate data, which otherwise would be lost due to
limitations in the TiPs. The multitude of accounting servers
also serve to reduce the load on the individual hosts providing
facility

-5-

The rest of this document details the protocol that has
developed to ensure delivery of TIP accounting data to one of
available accounting servers for storage in the
accounting files

Adapting the

The TIP to Accounting Server data exchange uses a protocol
allows the TIP to select for data transmission one, some, or
server hosts either sequentially or in parallel, yet insures
the data that becomes part of the accounting file does not
duplicate information. The protocol also minimizes the amount
data buffering that must be done by the limited capacity TiPs.
protocol is applicable to a wide class of data collection
which use a number of data generators and collectors. The
describes how the protocol works for TIP accounting

Each TIP is responsible for maintaining in its memory the
indicating the connect time and the number of messages sent for
of its current users. These cells are incremented by the TIP
every quantum of connect time and message sent, as the case may be
This is the data generation phase. Periodically, the TIP will
all its active counters, and along with each user ID code, pack
accumulated data into one network message (i.e. less than 8K bits).
The TIP then transmits this data to a set of Accounting
processes residing throughout the network. The data transfer
over a specially designated host-host link. The accounting
utilize the raw network message facility of TENEX 1.32 in order
directly access that link. When an ACTSER receives a data
from a TIP, it buffers the data and replies by returning the
message to the originating TIP. The TIP responds with a
acknowledgement ("go ahead") to the first ACTSER which returns
data, and responds with a negative acknowledgement ("discard")
all subsequent ACTSER data return messages for this series
transfers. If the TIP does not receive a reply from any ACTSER,
accumulates new data (i.e. the TIP has all the while
incrementing its local counters to reflect the increased
time and message count; the current values will comprise new
transfers) and sends the new data to the Accounting
processes. When an ACTSER receives a positive acknowledgement
a TIP (i.e. "go ahead"), it appends the appropriate parts of
buffered data to the locally maintained accounting information file
On receiving a negative acknowledgement from the TIP (i.e
"discard"), the ACTSER discards the data buffered for this TIP.
-addition, when the TIP responds with a "go ahead" to the
ACTSER which has accepted the data (acknowledged by returning
data along with the "I've got it"), the TIP decrements the
time and message counters for each user by the amount indicated
the data returned by the ACTSER. This data will already
accounted for in the intermediate accounting files

As an aid in determining which ACTSER replies are to
requests, and which are tardy replies to old requests, the

-6-
maintains a sequence number indicator, and appends this number
each data message sent to an ACTSER. On receiving a reply from
ACTSER, the TIP merely checks the returned sequence number to see
this is the first reply to the current set of TIP requests. If
returned sequence number is the same as the current sequence number
then this is the first reply; a positive acknowledgement is
off, the counters are decremented by the returned data, and
sequence number is incremented. If the returned sequence number
not the same as the current one (i.e. not the one we are
seeking a reply for) then a negative acknowledgement is sent to
replying ACTSER. After a positive acknowledgement to an ACTSER (
the implied incrementing of the sequence number), the TIP can
for more information to accumulate, and then start
again using the new sequence number

Further Clarification of the

There are a number of points concerning the protocol
should be noted

1. The data generator (TIP) can send different (i.e.
versions) data to different data collectors (accounting servers)
part of the same logical transmission sequence. This is
because the TIP does not account for the data sent until it
the acknowledgement of the data echo. This strategy relieves
TIP of any buffering in conjunction with re-transmission of
which hasn't been acknowledged

2. A new data request to an accounting server from a TIP
also serve as a negative acknowledgement concerning any data
buffered by the ACTSER for that TIP, but not yet acknowledged.
old data will be discarded, and the new data will be buffered
echoed as an acknowledgement. This allows the TIP the option of
sending a negative acknowledgement when it is not convenient to
so, without having to remember that it must be sent at a later time
There is one exception to this convention. If the new data
has the same sequence number as the old buffered message, then
new data must be discarded, and the old data kept and re-echoed
This is to prevent a slow acknowledgement to the old data from
accepted by the TIP, after the TIP has already sent the new data
the slow host. This caveat can be avoided if the TIP does
resend to a non-responding server within the time period that
message could possibly be stuck in the network, but could still
delivered. Ignoring this situation may result in some
data being counted twice. Because of the rule to keep old data
confronted with matching sequence numbers, on restarting after
crash, the TIP should send a "discard" message to all servers
order to clear any data which has been buffered for it prior to
crash. An alternative to this would be for the TIP to
its sequence number from a varying source such as time of day

3. The accounting server similarly need not acknowledge
of data (by echoing) if it finds itself otherwise occupied.
will mean that the ACTSER is not buffering the data, and hence
not a candidate for entering the data into the file. However,

-7-
TIP may try this ACTSER at a later time (even with the same data),
with no ill effects

4. Because of 2 and 3 above, the protocol is robust with
to lost or garbled transmissions of TIP data requests and
server echo replies. That is, in the event of loss of such
message, a re-transmission will occur as the normal procedure

5. There is no synchronization problem with respect to
sequence number used for duplicate detection, since this number
maintained only at the TIP site. The accounting server
echoes the sequence number it has received as part of the data

6. There are, however, some constraints on the size of
sequence number field. It must be large enough so that ALL
of the previous use of a given sequence number are totally
from the network before the number is re-used by the TIP.
sequence number is modulo the size of the largest number
by the number of bits allocated, and is cyclic. Problems
arise when a host proceeds from a service interruption while it
holding on to a reply. If during the service interruption, we
cycled through our sequence numbers exactly N times (where N is
integer), this VERY tardy reply could be mistaken for a reply to
new data, which has the same sequence number (i.e. N revolutions
sequence numbers later). By utilizing a sufficiently large
number field (16 bits), and by allowing sufficient time
instances of sending new data, we can effectively reduce
probability of such an error to zero

7. Since the data involved in this problem is the source
accounting information, care must be taken to avoid
entries. This must be done at the expense of potentially
data in certain instances. Other than the obvious TIP malfunction
there are two known ways of losing data. One is the situation
no accounting server responds to a TIP for an extended period
time causing the TIP counters to overflow (highly unlikely if
are sufficient Accounting Servers). In this case, the TIP can
the counters at their maximum value until a server comes up,
keeping the lost accounting data at its minimum. The
situation results from adapting the protocol to our insistence on
duplicate data in the incremental files. We are vulnerable to
loss with no recourse from the time the server receives the "
ahead" to update the file with the buffered data (i.e.
acknowledgement) until the time the update is completed and the
is closed. An accounting server crash during this period will
that accounting data to be lost. In our initial implementation,
have slightly extended this period of vulnerability in order to
the TIP from having to buffer the acknowledged data for a
period of time. By updating TIP counters from the returned data
parallel with sending the "go ahead" acknowledgement, we relieve
TIP of the burden of buffering this data until the Request for
Message (RFNM) from the accounting server IMP is received.
adds slightly to our period of vulnerability to malfunction,
the beginning of the period from the point when the ACTSER
receives the "go ahead", back to the point when the TIP sends

-8-

the "go ahead" (i.e. a period of one network transit time plus
IMP processing time). However, loss of data in this period
detectable through the Host Dead or Incomplete Transmission
in place of the RFNM. We intend to record such occurrences with

Network Control Center. If this data loss becomes intolerable,
TIP program will be modified to await the RFNM for the
acknowledgement before updating its counters. In such a case,
the RFNM does not come, the TIP can discard the buffered data
re-transmit new data to other servers

8. There is adequate protection against the entry of forged
into the intermediate accounting files. This is primarily due
the system enforced limited access to Host-Imp messages
Host-Host links. In addition, messages received on such
limited access links can be easily verified as coming from a TIP
The IMP subnet appends the signature (address) of the sending
to all of its messages, so there can be no forging. The
Server is in a position to check if the source of the message is
fact a TIP data generator

Current Parameters of the

In the initial implementation, the TIP sends its
accounting data about once every half hour. If it gets no
acknowledgement, it tries to send with greater frequency (
every 5 minutes) until it finally succeeds. It can then return
the normal waiting period. (A TIP user logout introduces
exception to this behavior. In order to re-use the TIP port and
associated counters as soon as possible, a user terminating his
session causes the accounting data to be sent immediately).
initially, our implementation calls for each TIP to remember
"favored" accounting server. At the wait period expiration, the
will try to deposit the data at its "favored" site. If
within a short timeout period, this site remains the favored site
and the wait interval is reset. If unsuccessful within the
timeout, the data can be sent to all servers*. The one
first will update its file with the data and also become
"favored" server for this TIP. With these parameters, a host
have to undergo a proceedable service interruption of more than
year in order for the potential sequence number problem outlined
(6) above to occur

Concluding

When the implementation is complete, we will have a
data accumulation and collection system which can be used to
a wide variety of information. The protocol as outlined is
to gathering data which is either independent of the
accumulated data items (e.g. recording names), or data
adheres to a commutative relationship (e.g. counting). This is

-9-

consequence of the policy of retransmission of different versions
the data to different potential collectors (to relieve TIP
problems).

In the specified version of the protocol, care was taken
avoid duplicate data entries, at the cost of possibly losing
data through collector malfunction. Data collection problems
require avoiding such loss (at the cost of possible duplication
some data items) can easily be accommodated with a slight
to the protocol. Collected data which does not adhere to
commutative relationship indicated above, can also be handled
utilizing more buffer space at the data generator sites

The sequence number can be incremented for this new set of
messages, and the new data can also be sent to the slow host.
this way we won't be giving the tardy response from the old
host unfair advantage in determining which server can respond
quickly. If there is no reply to this series of messages, the
can continue to resend the new data. However, the sequence
should not be incremented, since no reply was received, and
indiscriminate incrementing of the sequence number increases
chance of recycling during the lifetime of a message

-10-

if you see any problems within the linking, don't worry be happy,
this is version 0.1 of the Relevance System and you gotta expect some crappy subroutines sometimes,
just be content we did not write this in Java, which would have made this "bigger and better" HAHAHHA.

RFC documents can be found at I.E.T.F.

Relevance System Copyright © 2002 Spectrum WorldResearch
other technical nosh by ServerMasters Corporation
collaboration of BobX