RFC 672

A Multi-Site Data Collection Facility 🦋

Okay bestie, the title block first 💅 This is RFC 672 by Richard Schantz (BBN-TENEX), filed in the Network Working Group under NIC #31440 and dated Dec 1974. The header doesn't list a category, and it doesn't say this RFC obsoletes or updates anything, so there's nothing else to chase up here 🌸

---

Preface 🎀

So this RFC is basically a working doc that got published, and it's giving real design-diary energy 📓 It reproduces most of a working document written while the protocols for the TIP-TENEX integrated system were being designed and built, the system that handles TIP accounting. Bernie Cosell (BBN-TIP) and Bob Thomas (BBN-TENEX) contributed to different parts of this work 🫶 The system had been partially operational for about a month on selected hosts. And the authors feel the techniques here have wide applicability way beyond TIP accounting ✨

---

Section I: Protocols for a Multi-site Data Collection Facility 🌸

Introduction 🧚

Okay so computer networks basically made distributed computation possible, which is when a job is made of pieces from different computer systems 🌈 On a single computer, if any piece of the job (a program, a file, a device, whatever) breaks or goes down, the whole job usually has to end 😭 With networks, you can now duplicate pieces that never could be duplicated before. (On one system it doesn't matter how many times a process gets duplicated, because if the system crashes, they're all gone.) That duplication is what lets us use the network for high reliability and load leveling 🔥 To actually unlock the potential of duplicated resources, you need protocols that let them be used in an orderly way.

In this doc, we first talk in general terms about a protocol problem for interacting with a resource that's defined in multiple places (a server) 💅 The problem is providing a highly reliable data collection facility by running it at lots of sites across the network. In the second section, we dig into one specific implementation of the protocol, which handles using several data collector processes to collect accounting data generated by the network TIPs. This also shows hosts specializing, doing the parts of a computation they're best equipped to handle. The big network hosts (TENEX systems) do the accounting for the small network access TIPs 🦋

The situation is this: a data generating process needs to use a data collection service that's duplicately provided by processes on a number of network machines. A request to a server involves sending the data to be collected 🍓

An Initial Approach 💖

The data generator could just pick a particular server and send its request there. It might also assume that if the message reaches the destination host (the communication subsystem will indicate this), the message will get properly processed to completion ✨ If the request message fails, it would pick another server, and keep going until the request succeeds or all servers have been tried.

Such a simple strategy is a poor one 💀 It makes sense to require that the servicing process send a positive acknowledgement to the requesting process. If nothing else, the reply shows the server process is still functioning. Waiting for that reply also implies there's a strategy for selecting another server if the reply isn't forthcoming 😭 Here's the catch. If the expected reply times out and a new request goes to another server, you run the risk of receiving the (delayed) original acknowledgement later. That could get the data entered into the collection system twice (data duplication) 😱 If the request is re-transmitted to the same server only, you face the possibility of not being able to access a collector at all (data loss). Plus, for load leveling, you may wish to send new requests to some (or all) servers, and use their reply (or lack of reply) as an indicator of load on that particular instance of the service 📊 Doing this without data duplication takes more than a simple request and acknowledgement protocol*.

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

Extension of the Protocol 🌟

The general protocol for handling multiple collection servers has the data generator send the data request to some (or all) data collectors. The ones willing to handle the request reply with an "I've got it" message. Then they await further notification before finalizing the processing of the data. The data generator sends a "go ahead" message to one of the replying collectors, and a "discard" message to all the other replying collectors 💅 The "go ahead" message is the signal to process the data (i.e. collect it permanently), while the "discard" message says the data is being collected elsewhere and should not be retained.

Now the question is whether the collector process should acknowledge receipt of the "go ahead" message with a reply of its own, and then whether the generator should acknowledge that acknowledgement, and so on 🤔 We'd like to send as few messages as possible to achieve reliable communication. So when a state is reached where further acknowledgements lead to a previously visited state, or when the cost of further acknowledgements outweighs the increase in reliability they bring, further acknowledgements become unnecessary.

The initial question was: should the collector process acknowledge the "go ahead" message? Let's assume for the moment that it should not send such an acknowledgement 🙈 The data generator could verify, through the communication subsystem, that the "go ahead" message was transmitted to the collector's host. If it didn't arrive correctly, the generator has the option of re-transmitting it, or sending a "go ahead" to another collector that has acknowledged receipt of the data. Either strategy involves no risk of duplication. But if the "go ahead" arrives correctly and a collector acknowledgement isn't required, we're vulnerable to a crash of the collector host from the moment the "go ahead" is accepted by the host until the data is totally processed. Call the data processing time P. Once the data generator has selected a particular collector (based on its "I've got it" message), we're also vulnerable to a malfunction of that collector process. The vulnerable period runs from the time the collector sends its "I've got it" message until the data is processed. This amounts to two network transit times (2N), plus IMP and host overhead for message delivery (0), plus data processing time (P). [Total time=2N+P+O] A malfunction (crash) in this period can cause the loss of data. There is no potential for duplication 💜

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

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

Data Dependent Aspects of the Protocol 🧠

As discussed above, a main issue is which process should be the last to respond (send an acknowledgement). If the data generator sends the last message (i.e. "go ahead"), we can only check on its 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 the other hand, the protocol specifies that the collector is to send the last message, with the timeout of such a message causing the data generator to use another collector, then the protocol is geared toward the best efforts of recording the data somewhere, at the expense of possible duplication ⚖️

So the nature of the problem dictates which protocol is appropriate for a given situation. The next section deals with the specifics of an implementation of a data collection protocol for collecting TIP accounting data, using the TENEX systems to run the collection server processes. It shows how the general protocol is optimized for accounting data collection 🎯

---

Section II: Protocol for TIP-TENEX Accounting Server Information Exchange 🎀

Overview of the Facility 🦋

When a user initially requests service from a TIP, the TIP will perform a broadcast ICP to find an available RSEXEC, which maintains an authentication data base. The user must then complete a login sequence to authenticate themselves 🔐 If they're successful, the RSEXEC will transmit their unique ID code to the TIP. Failure will cause the RSEXEC to close the connection, and the TIP to hang up on the user 💀 Once the user is authenticated, the TIP will accumulate accounting data for the user session. The data includes a count of messages sent on behalf of the user, and the connect time for the user ⏱️

From time to time, the TIP will transmit intermediate accounting data to Accounting Server (ACTSER) processes scattered throughout the network. These accounting servers maintain files containing intermediate raw accounting data. The raw accounting data is periodically collected and sorted to produce an accounting data base 📚 Having a number of accounting servers reduces the possibility of being unable to find a repository for the intermediate data, which otherwise would be lost due to buffering limitations in the TIPs. The multitude of accounting servers can also serve to reduce the load on the individual hosts providing this facility 🌈

From time to time the TIP sends its intermediate accounting data to Accounting Server (ACTSER) processes scattered all over the network 🌐. These accounting servers keep files full of intermediate raw accounting data 📁. That raw data gets collected and sorted every so often to build an accounting data base 🗂️. Having a bunch of accounting servers is lowkey genius 🧠, because it makes it less likely that a TIP can't find a repository for its intermediate data 😭. Otherwise that data would just get lost to buffering limits in the TIPs. The multitude of servers also takes some load off the individual hosts providing this facility 🫶.

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

Adapting the Protocol

Okay, the TIP to Accounting Server data exchange is giving main character energy 👑. It uses a protocol that lets the TIP pick one, some, or all server hosts for data transmission, either one after another or in parallel. Even so, it ensures that the data that ends up in the accounting file has no duplicate information 🙅‍♀️. The protocol also minimizes how much data buffering the limited capacity TIPs have to do 🔋. It's applicable to a wide class of data collection problems that use a number of data generators and collectors. Here's how it works for TIP accounting 💅.

Each TIP is responsible for keeping, in its memory, the cells that track the connect time and the number of messages sent for each of its current users ⏱️. The TIP increments these cells for every quantum of connect time and message sent, as the case may be. This is the data generation phase 🌸.

Periodically, the TIP scans all its active counters. Along with each user ID code, it packs the accumulated data into one network message (i.e. less than 8K bits) 📦. The TIP then transmits this data to a set of Accounting Server processes residing throughout the network. The data transfer happens over a specially designated host-host link 🔗. The accounting servers use the raw network message facility of TENEX 1.32 to directly access that link. When an ACTSER receives a data message from a TIP, it buffers the data and replies by returning the entire message to the originating TIP 🔁.

The TIP responds with a positive acknowledgement ("go ahead") to the first ACTSER that returns the data. It responds with a negative acknowledgement ("discard") to all subsequent ACTSER data return messages for this series of transfers 🙅. If the TIP doesn't get a reply from any ACTSER, it accumulates new data. (The TIP has been incrementing its local counters the whole time to reflect the increased connect time and message count, so the current values will make up the new data transfers 🧮.) Then it sends the new data to the Accounting Server processes 📤.

When an ACTSER receives a positive acknowledgement from a TIP (i.e. "go ahead"), it appends the appropriate parts of the buffered data to the locally maintained accounting information file 📝. When it gets a negative acknowledgement from the TIP (i.e. "discard"), the ACTSER discards the data buffered for this TIP 🗑️. In addition, when the TIP responds with a "go ahead" to the first ACTSER that has accepted the data (acknowledged by returning the data along with the "I've got it"), the TIP decrements the connect time and message counters for each user. It subtracts the amount indicated in the data returned by the ACTSER. This data is already accounted for in the intermediate accounting files 💖.

As an aid in figuring out which ACTSER replies are answers to current requests and which are tardy replies to old requests, the TIP keeps a sequence number indicator. It appends this number to each data message sent to an ACTSER 🔢. When a reply comes back from an ACTSER, the TIP just checks the returned sequence number to see if it's the first reply to the current set of TIP requests 👀. If the returned sequence number is the same as the current sequence number, then this is the first reply. The TIP sends off a positive acknowledgement, decrements the counters by the returned data, and increments the sequence number 🎉. If the returned sequence number is not the same as the current one (i.e. not the one it's currently seeking a reply for), then the TIP sends a negative acknowledgement to the replying ACTSER 🙅‍♀️. After a positive acknowledgement to an ACTSER (and the implied incrementing of the sequence number), the TIP can wait for more information to accumulate. Then it can start transmitting again using the new sequence number 🦋.

Further Clarification of the Protocol

There are a number of points about the protocol that should be noted 📌.

1. The data generator (TIP) can send different (i.e. updated versions) data to different data collectors (accounting servers) as part of the same logical transmission sequence. This works because the TIP doesn't account for the data it sent until it receives the acknowledgement of the data echo 🪞. This strategy spares the TIP from having to buffer anything for re-transmission of data that hasn't been acknowledged 🙌.
2. A new data request to an accounting server from a TIP also serves as a negative acknowledgement for any data already buffered by the ACTSER for that TIP that hasn't been acknowledged yet 🧹. The old data gets discarded, and the new data gets buffered and echoed as an acknowledgement. This gives the TIP the option of not sending a negative acknowledgement when it isn't convenient, without having to remember to send it later 😌. There is one exception to this convention. If the new data message has the same sequence number as the old buffered message, then the new data must be discarded, and the old data kept and re-echoed 🚫. This stops a slow acknowledgement to the old data from being accepted by the TIP after the TIP has already sent the new data to the slow host 🐢. This caveat can be avoided if the TIP doesn't resend to a non-responding server within the time period that a message could possibly be stuck in the network but could still be delivered ⏳. Ignoring this situation may result in some accounting data being counted twice 💀. Because of the rule to keep old data when confronted with matching sequence numbers, when the TIP restarts after a crash, it should send a "discard" message to all servers. That clears any data that was buffered for it before the crash 🧽. An alternative would be for the TIP to initialize its sequence number from a varying source, such as time of day ⏰.
3. The accounting server similarly doesn't need to acknowledge receipt of data (by echoing) if it finds itself otherwise occupied. This means the ACTSER isn't buffering the data, so it isn't a candidate for entering the data into the file. However, the TIP may try this ACTSER at a later time (even with the same data), with no ill effects 🌤️.
4. Because of points 2 and 3 above, the protocol is robust with respect to lost or garbled transmissions of TIP data requests and accounting server echo replies. That means that if such a message is lost, a re-transmission happens as the normal procedure 🔄.
5. There's no synchronization problem with respect to the sequence number used for duplicate detection, since this number is maintained only at the TIP site. The accounting server just echoes the sequence number it has received as part of the data 🧘‍♀️.
6. There are, however, some constraints on the size of the sequence number field 📏. It must be large enough so that ALL traces of the previous use of a given sequence number are totally removed from the network before the TIP reuses the number. The sequence number is modulo the size of the largest number the allocated bits can represent, and it's cyclic 🔁. Problems generally pop up when a host recovers from a service interruption while it was holding on to a reply 😱. If during the service interruption the sequence numbers have cycled through exactly N times (where N is any integer), this VERY tardy reply could be mistaken for a reply to the new data. That's because the new data has the same sequence number (i.e. N revolutions of sequence numbers later) 🌀. By using a sufficiently large sequence number field (16 bits) and allowing sufficient time between instances of sending new data, we can effectively reduce the probability of such an error to zero 💯.
7. Since the data involved in this problem is the source of accounting information, care must be taken to avoid duplicate entries 🧐. This has to be done at the expense of potentially losing data in certain instances. Apart from an obvious TIP malfunction, there are two known ways to lose data 📉. The first is when no accounting server responds to a TIP for an extended period of time, causing the TIP counters to overflow. This is highly unlikely if there are sufficient Accounting Servers 🤞. In this case, the TIP can hold the counters at their maximum value until a server comes up, which keeps the lost accounting data at its minimum 🧊. The second situation results from adapting the protocol to the insistence on no duplicate data in the incremental files 🙅. Data loss is possible with no recourse from the time the server receives the "go ahead" (i.e. positive acknowledgement) until the update is completed and the file is closed. If an accounting server crashes during this period, that accounting data will be lost 💔. In the initial implementation, this period of vulnerability was slightly extended to save the TIP from having to buffer the acknowledged data for a short time. By updating TIP counters from the returned data in parallel with sending the "go ahead" acknowledgement, the TIP doesn't have to buffer this data until the Request for Next Message (RFNM) arrives from the accounting server IMP 📬. This adds slightly to the period of vulnerability to malfunction. The beginning of the period moves from the point when the ACTSER host receives the "go ahead" back to the point when the TIP sends it off (i.e. a period of one network transit time plus some IMP processing time) 🚚. However, loss of data in this period is detectable through the Host Dead or Incomplete Transmission return in place of the RFNM 🚨. We intend to record such occurrences with the Network Control Center 🗒️. If this data loss becomes intolerable, the TIP program will be modified to wait for the RFNM before acknowledging positively and updating its counters. In that case, if the RFNM doesn't come, the TIP can discard the buffered data and re-transmit new data to other servers 🔄.
8. There's adequate protection against forged data entering the intermediate accounting files 🛡️. This is mainly thanks to the system-enforced limited access to Host-Imp messages and Host-Host links. Messages received on these designated limited access links can also be easily verified as coming from a TIP 🕵️‍♀️. The IMP subnet appends the signature (address) of the sending host to all of its messages, so there can be no forging 🚫. The Accounting Server is in a position to check whether the source of a message is in fact a TIP data generator ✅.

Current Parameters of the Protocol

In the initial implementation, the TIP sends its accumulated accounting data about once every half hour ⏰. If it gets no positive acknowledgement, it tries again more often (about every 5 minutes) until it finally succeeds. Then it can go back to the normal waiting period 💅. (A TIP user logout is an exception to this behavior. To re-use the TIP port and its associated counters as soon as possible, a user terminating their TIP session causes the accounting data to be sent immediately 🏃‍♀️.)

Initially, the implementation has each TIP remember a "favored" accounting server 💜. When the wait period expires, the TIP tries to deposit the data at its "favored" site. If that succeeds within a short timeout period, this site stays the favored site and the wait interval resets 🎀. If it's unsuccessful within the short timeout, the data can be sent to all servers. The one that replies first updates its file with the data and also becomes the "favored" server for this TIP 👑. With these parameters, a host would have to go through a proceedable service interruption of more than a year for the potential sequence number problem outlined in

(6) above to occur, and honestly that's giving main character energy for a bug 😭🫶 Anyway, let's get into the Concluding Remarks ✨

Concluding Remarks

Okay so when the implementation is finished, we'll have a general data accumulation and collection system 🎀 that can gather all kinds of information, which is so iconic. The protocol as outlined is built for two kinds of data: data that doesn't depend on anything already collected (like recording names 📝), and data with a commutative relationship (like counting 🔢). This is literally just a consequence of the policy of retransmitting different versions of the data to different potential collectors, which exists to relieve TIP buffering problems 🧚

-9-

In the specified version, care was taken to avoid duplicate data entries 💅, and the tradeoff is that some data might get lost if a collector malfunctions 💀. Data collection problems that need to avoid that loss (with the cost of possibly duplicating some data items) can be handled with a slight adjustment to the protocol 🌸. Collected data that does not follow the commutative relationship mentioned above can also be handled, by using more buffer space at the data generator sites 🍓

The sequence number can be incremented for this new set of data messages, and the new data can also be sent to the slow host 🦋. This way, the tardy response from the old favored host doesn't get an unfair advantage in deciding which server answers most quickly 👑. If there is no reply to this series of messages, the TIP can keep resending the new data ✨. However, the sequence number should not be incremented, since no reply was received, and since indiscriminate incrementing of the sequence number increases the chance of recycling during the lifetime of a message 🙈

-10-