doc: Add RFC documents

1 files changed, 608 insertions, 0 deletions

diff --git a/doc/rfc/rfc150.txt b/doc/rfc/rfc150.txt
new file mode 100644
index 0000000..40de7ba
--- /dev/null
+++ b/doc/rfc/rfc150.txt
@@ -0,0 +1,608 @@
+
+
+
+
+
+
+Richard Bl. Kalin                            Network Working Group
+MIT Lincoln Laboratory                       Request for Comments #150
+5 May 1971                                   NIC 6754
+
+
+THE USE OF IPC FACILITIES
+
+***A WORKING PAPER***
+
+This material has not been reviewed for public release and is intended
+only for use within the ARPA network. It should not be quoted or cited
+in any publication not related to the ARPA network.
+
+INTRODUCTION
+
+      It is our hypothesis that the goals of interprocess communication
+are more complex than commonly realized, and that until this complexity
+is more fully understood, there will be no satisfactory implementations.
+The objective of an IPC design must be more than that of providing a
+facility for moving bits between otherwise independent user programs, a
+variety of other constraints must also be satisfied.
+
+      These constraints are dictated by the eventual usage of the
+facility. Any design that will sustain this usage pattern can be a
+satisfactory one. If it does so efficiently, it will be said to be well
+designed. Furthermore, it is unimaginable that a large design effort,
+undertaken without a complete understanding of the usage it must serve,
+will ever be well designed or even satisfactorily designed.
+
+      This paper undertakes the exposition of the types of usage to
+which an IPC facility would be subjected, in hopes that such a
+discussion will clarify the goals being pursued and will provide a
+benchmark for gauging various implementation strategies. The difficulty
+of this task should not be underestimated. The only experience available
+for us to draw upon is from very primitive and overly constrained IPC
+implementations. Extrapolation from this limited usage environment to
+more general notions has as yet no basis in real experience. Such
+speculation is therefore subject to enormous oversight and misguided
+perspective.
+
+      In compiling this paper, it was necessary to imagine what services
+a process might want from an IPC facility. The areas recognized include:
+ 1) the exchange of bit encoded information via channels.
+ 2) the establishment, deletion, and reassignment of these channels.
+ 3) the ability to debug errors and suspected errors.
+ 4) the potential to improve running efficiency.
+ 5) the capacity to avoid storage allocation deadlocks.
+ 6) the aided recovery from transmission errors.
+
+
+
+                                                                [Page 1]
+
+RFC #150                 Use of IPC Facilities                5 May 1971
+
+
+This list is known to be incomplete. Some areas, such as understood to
+be intelligently discussed. In other cases, omissions should be blamed
+on simple oversight.
+
+      Because of these obvious problems, one should not consider any
+document of this kind as either authoritative or final. For this reason,
+this paper is being kept as a computer based textfile, and so will
+remain subject to editting and rerelease whenever new insights become
+understood. We hope that it can remain an accurate and up to date
+statement of the goals to which any group of IPC implementers can aspire
+and, as such, can be a guidebook to the problems that must be faced.
+
+      For several reasons no attempt shall be made here to design
+suitable solutions to the problems raised. To be useful, such solutions
+must be machine dependent. A so called 'general solution' would actually
+be too clumsy and inefficient to be of any value. Secondly, we take the
+point of view of the user, who need not be aware of the manner in which
+his demands are carried out, so long as they can be accomplished.
+Finally, we are trying to stay aloof from the eccentricities of present
+day machine organization.
+
+In our attempt to be implementation independent, we are admittedly
+treading a fuzzy line. Our characterization of usage patterns presumes
+both a system/process software organization and a computing milieu
+capable of supporting it. Although this does not appear to significantly
+affect the generality of the document, some care must be exercised in
+the selection of host machines.
+
+               *****
+
+      In the rest of this paper, we attempt to characterize the types of
+usage that should be anticipated by an IPC facility. The organization is
+into titled sections, each section discussing some aspect of the
+expected usage.
+
+ABILITY TO USE VARIOUS SOURCES OF WAKEUP INFORMATION
+
+      Most processes exhibit preferences toward certain quantities of
+input data. This preference is reflected in the amount of computing time
+that can be expended for a given amount of input. For example, a
+character translation routine might prefer eight bit quantities of
+input. With seven or less bits no processing is possible, but once a
+complete character is available an entire translation cycle can
+commence. This preference is independent of the function of the routine.
+Otherwise equivalent routines could be written that would accept one bit
+at a time. In other examples, a command interpreter might require a
+complete line of input, a linking loader a complete file.
+
+
+
+
+                                                                [Page 2]
+
+RFC #150                 Use of IPC Facilities                5 May 1971
+
+
+      Every executive system must face the problem of deciding at what
+times enough input is available for a given routine for it to run
+efficiently. This decision can not be taken lightly. Issuing a wakeup to
+a dormant process carries with it considerable overhead -- room in core
+storage must be made available, the program must be swapped into memory,
+tables must be updated, active registers exchanged, and the entire
+procedure done in reverse once the process has finished. To issue a
+wakeup when there is insufficient input for the program is inefficient
+and wasteful. The amount of computing that can be done does not justify
+the overhead that must be expended.
+
+      The problem of determining a priori the best time to issue a
+wakeup has no general solution. It depends critically upon the
+relationship between waiting costs and running costs. Attempts to make
+reasonable predictions must contend with the tradeoff between accuracy
+and overhead. The more system code that must be run, the more overhead
+incurred and the less the final prediction means.
+
+      Although there is no general solution, help is available to the
+scheduler in specific cases. A commonly found instance is that of using
+the receiving process to specify the number of bits that it is
+expecting. Thus, a process may inform the supervisor/scheduler that it
+requires fifty bits of input from some source before it is able to
+continue. The process can then go into the shade and it will be awakened
+when the required input is available.
+
+      In cases where input lengths are predetermined, this technique is
+quite satisfactory. Elsewhere, problems arise. In the case of unknown
+input sizes, too short a prediction will give rise to the inefficiencies
+of premature scheduling, and too long a prediction may produce input
+deadlocks.
+
+      Under these circumstances it is common to have the process tell
+the scheduler a simple criterion that can be applied to determine if
+there is sufficient input -- the appearance of a carriage return in the
+teletype input stream, for example. The criterion is tested either by
+system routines or by a low overhead user supplied routine (which in
+turn must have a criterion of its own for being awakened).  Once the
+criterion is met, the main routine is awakened and processing continues.
+
+      Sometimes the system and user criteria work in conjunction with
+one another. A user may specify an maximum character count,
+corresponding to available buffer size, and the system may look for line
+terminators. Wakeups to the user process may appear from either source.
+At other times the system may preempt the user's criterion. For example,
+if a process while trying to put a single character into a full buffer
+is forced into shade, it will typically not be awakened again until
+buffer has been almost emptied. Even though the user program only wished
+
+
+
+                                                                [Page 3]
+
+RFC #150                 Use of IPC Facilities                5 May 1971
+
+
+room for a single character, the system imposed a much stronger
+criterion, namely room for N characters, on the assumption other calls
+to output characters will follow. Thus the program is forced into
+outputting in bursts and, rather than going into the shade and being
+awakened N times, each time when there is only room to output one
+character, the program is awakened once and sends N characters. Program
+efficiency is appropriately improved.
+
+      A third source of criteria for deciding when to awaken the user
+process is the device or routine that is producing the input data. This
+source is frequently utilized in hardware design. Many computer
+peripherals have the ability to send an end of record indication. For
+variable length uninterpreted records this is an absolute necessity. For
+fixed length records it is a convenient double check. In the world of
+interprocess communication an analogous feature should be available. If
+the routine that is generating the data knows how much the receiving
+routine will require, then this information should be made available for
+scheduling purposes. Implementing this requires a standardized way of
+denoting logical boundaries on the stream of data flowing, through a
+communication channel. The markers must be recognizable by the
+scheduler/supervisor in the receiving host computer so that wakeups can
+be issued as desired. To simplify the task of input interpretation,
+marker pacement should also be visible to the receiving process.
+
+      The data between boundaries we shall call a logical message, since
+it is a natural unit of information exchange and since the markers
+travel with the data through the channel. The additional information the
+markers provide about data flow yield many useful consequences.
+Consider, for example, two processes that always exchange 100 bit long
+logical messages. If the receiving process is able to determine the
+length of each logical message that arrives, there is available a simple
+facility for error detection. If a 99 bit message arrives, it is obvious
+that a bit has been dropped somewhere.
+
+      It should be noted that it is not always possible for the
+receiving process to compute the positions of boundary markers in the
+input stream. there is no reason that the information implicit is marker
+position must also be found as part of the coded input data. Even in
+cases in which there is coding redundancy, it may be more difficult to
+extract boundary information from the rest of the input than it is to
+use the markers explicitly.
+
+ABILITY TO SEND PARTS OF LOGICAL MESSAGES
+
+      Any IPC facility, in which user storage is at all constrained, can
+not require a process to send an entire logical message at one time. The
+concept is only introduced to facilitate the issuing of wakeups to a
+receiving process. What are convenient input quanta for the receiving
+
+
+
+                                                                [Page 4]
+
+RFC #150                 Use of IPC Facilities                5 May 1971
+
+
+process may not be convenient output quanta for the sending one.
+consider the case of a process running on a small machine and sending
+messages to a process on a large task-multiplexed machine. For
+efficiency, the receiving process requires large quantities of input
+data at a time. Buffer space in the address space of the sending process
+can not hold much data. The only answer is to allow the sending process
+to dump its logical message in parts and with the last part to indicate
+that it is the end of a message.
+
+ABILITY TO RECEIVE A LOGICAL MESSAGE IN PARTS
+
+      In the reverse of the above situation, a receiving process may not
+have sufficient buffer space available to accept an entire message at
+once. It should be possible under these circumstances to elect to accept
+the message in parts. This is also necessary in the case of messages
+that are too long to be buffered by the system. Unless part of the
+message is accepted by the receiving process, the transmission can never
+be completed. This device also serves for the removal of very long
+messages that appear by error in the input stream.
+
+ABILITY TO FIND OUT IF A MESSAGE CAN BE SENT
+
+      If left unchecked, a routine can easily generate messages faster
+than they can be consumed. Since any given amount of buffer capacity can
+be quickly exhausted, there must be a way for the system to limit the
+rate at which a process produces messages. This implies that at times a
+process trying to send a message may be prevented from doing so because
+of buffer inavailability. If the process is forced into the shade, the
+pause should not come without warning. There should be a way for the
+process to learn in advance if the message can be sent. A program may
+have better things to do than wait for a buffer to become available.
+
+ABILITY TO GET A GUARANTEE OF OUTPUT BUFFER SPACE
+
+      A process should be able to get guarantee from the system that a
+message of a certain size can be sent. This allows the process to know
+before a computation is made that the results can be successfully
+output. This allocation should remain either until it is depleted or
+until it is changed by another allocation request.
+
+      This particular user option is sure to raise the wrath of legions
+of system programmers. From their point of view, the empty buffer space
+that is being preallocated is necessarily being wasted. For although it
+contains no messages, it is not available for other uses. The user, on
+the other hand, does not correlate 'empty' with 'wasteful' nor 'full'
+with 'efficient'. A process needs empty output buffers as much as it
+needs full input ones. Both are resources necessary to sustain
+processing.
+
+
+
+                                                                [Page 5]
+
+RFC #150                 Use of IPC Facilities                5 May 1971
+
+
+ABILITY TO FIND OUT ABOUT OUTSTANDING MESSAGES
+
+      A process that is sending messages over a channel should be able
+to find out how many of those messages have not yet been accepted by the
+user process at the far end and whether or not this number can decrease.
+Ideally, it should also be able to determine the number of bits left in
+any partially accepted message, but the overhead necessary to implement
+this on conventional systems may be too great to be tolerated.
+
+      The count returned can be useful both dynamically and for post
+mortems. Used in debugging a remote process, it allows inputs on
+normally concurrent channels to be presented one at a time and in any
+given order. In this way one could, for example, verify that the same
+results are produced regardless of the order in which the inputs arrive.
+
+      If there is a failure of a receiving process, this mechanism
+allows a sending process to determine the last input accepted before the
+process died. Even between operational processes it provides a user
+managed way for the transmitting process to slow down and let the
+receiver catch up with it. By pinpointing bottlenecks, it can be used to
+detect design mismatches.
+
+      Unless the channel has no outstanding messages or it is dead,
+there is the possibility that concurrently with the request the
+receiving process will accept another message. This being the case, the
+count returned can not be assumed to be exact but must be considered as
+only an upper bound.
+
+ABILITY TO GET WAKEUPS WHEN MESSAGES ARE ACCEPTED
+
+      In conjunction with the above it should be possible for a user
+process to be alerted when the number of messages that have been sent
+over a particular channel and not accepted at the far end falls below a
+specified threshold. Thus a process, upon discovering that twenty
+messages are still outstanding, can elect to enter the shade until this
+number has fallen to less than five. By doing so the process can run in
+'burst mode'. Rather than being swapped in and out of core fifteen times
+and each time being allowed to send one message, it is loaded once and
+sends fifteen messages. There is no penalty for doing this since the
+bottleneck on throughput is at the receiving process. If swapping costs
+for the local process are significant, there may be considerable
+economic advantage to this mode of operation.
+
+      If the remote process dies or issues a channel 'close', the count
+of undelivered messages becomes frozen. If the receiving process is
+expecting this type of wakeup, it should get one at this time even
+though the count has not reached the desired threshold. The process is
+thus alerted to do a postmortem on the channel.
+
+
+
+                                                                [Page 6]
+
+RFC #150                 Use of IPC Facilities                5 May 1971
+
+
+ABILITY TO LEARN ABOUT MESSAGES QUEUED FOR INPUT
+
+      A process should be able to learn of the status of the Nth logical
+message queued on a given input channel. It should a least be able to
+determine if it is available, whether or not it is complete, how long it
+is and what it contains.
+
+      This facility allows a program to make general preparations before
+accepting a message. It offers some escape from being put into the
+awkward position of having accepted input and not being able to dispose
+of it. If for example, it is known that processing the message will
+result in two more messages being sent, then it is advantageous to get
+guarantees that the output can be generated before the input is
+accepted.
+
+      Under circumstances in which one end of a channel is moved from
+one process to another, for example, moving a teletype connection
+between a user program and a debugging program, this ability to scan
+ahead in the input stream allows a process to check whether or not
+pending input is really meant for it. If it is, the input will then be
+accepted normally, otherwise, the end of the channel must be first moved
+to another receiving process.
+
+      Accepting input should be viewed as a grave responsibility, not to
+be undertaken unless there is reasonable assurance that the input can be
+processed. One of the first rules of asynchronous system design is to
+detect errors as soon as possible. If propagated, the tangled results
+may be hopeless to unravel.
+
+ABILITY TO LEARN HOW MANY MESSAGES ARE WAITING
+
+      A process should be able to determine how many messages are
+left to be processed on a given input channel. Two uses are readily
+thought of. Given pending inputs on several channels a process should be
+able to exercise preference. One decision might be to take input first
+from the channel with the most messages queued. This might have the
+effect of increasing throughput since by freeing message buffers the
+remote transmitting process might be allowed to run. Another possibility
+might be that the receiving process has some control over the sending
+process and, upon observing the backlog on inputs, it could tell that
+process to slow down.
+
+      Assuming that the remote process is still able to send messages,
+the number of inputs reported is only a lower bound. New inputs may be
+added concurrently. If the foreign process has died or has otherwise
+closed the connection then the bound can be made exact. The local
+process should be able to learn when it is exact.
+
+
+
+
+                                                                [Page 7]
+
+RFC #150                 Use of IPC Facilities                5 May 1971
+
+
+GUARANTEE THAT INPUT WILL STAY AVAILABLE
+
+      This requirement states that if a process has been told that it is
+able to receive N messages on a given channel, that those messages are
+really available and buffered within the host machine. If promised to a
+user process, messages should not mysteriously become unavailable. An
+example of how this might happen is illustrated in RFC60.  There, during
+a panic for buffer space, messages are destroyed and reported as being
+in error. They are later recovered from backup copies contained in the
+foreign host.
+
+ABILITY TO RECEIVE A WAKEUP WHEN INPUTS ARRIVE
+
+      A process should be able to enable a wakeup when the number of
+messages queued on an input channel exceeds a specified value or has
+reached its maximum value. This allows a program to process input in a
+burst mode fashion and to economize on swapping costs. It also permits
+inputs to be combined in a simple manner. If, for example, two inputs
+are needed before anything can be done, then the appropriate interrupt
+can be easily generated.
+
+      The same interrupt should be generated if the maximum number of
+inputs have been received. Two cases are distinguished. Either the
+foreign process has closed the channel and is therefore not sending more
+messages, or the system will not allocate more buffers until some input
+is accepted. In this way the process can be informed that there is no
+point in waiting for the condition it anticipates.
+
+ABILITY TO SPECIFY SPECIAL WAKEUPS
+
+      A process, when trying to run efficiently, should be able to
+specify arbitrarily complicated wakeup conditions. This allows a user
+managed way of minimizing the number of premature wakeups. This
+generality is perhaps most easily provided for by allowing the main
+process to designate a small low overhead interrupt driven routine that
+will check for the desired conditions and issue a wakeup to the main
+process whenever they are met.
+
+ABILITY TO MEASURE CHANNEL CAPACITY
+
+      There has been much discussion about the measure of a data stream
+and in the heat of committee, much confusion has been generated. It is
+our feeling that, within the present domain of discussion, there is no
+single measure of the capacity of a message channel. Two completely
+orthogonal concepts must be measured -- 1) the number of messages
+buffered and 2) the number of bits of encoded data represented. The
+system overhead associated with each is very much implementation
+dependent and hence no general equation can express the measure of one
+
+
+
+                                                                [Page 8]
+
+RFC #150                 Use of IPC Facilities                5 May 1971
+
+
+in terms of the other. By making an arbitrary assumption (eg. a message
+boundary equals 100 bits of buffer), a system runs the risk of excluding
+new nodes that are unable to meet the old criterion.
+
+ABILITY TO FIND OUT MAXIMUM CHANNEL CAPACITY
+
+      There should be provided a system call that enables a user process
+to learn of the maximum current capacity of any given channel. This
+should be reported as a pair of numbers, namely the maximum bit count
+and the maximum message count.
+
+ABILITY TO CONSTRAIN CHANNEL CAPACITY
+
+      A process using a channel should be able to set new bounds on the
+capacity of a given channel. If possible the system should try to meet
+this bound. It should be noted that the actual bounds imposed must meet
+the constraints of at least four different sources -- local and remote
+user process, local and remote system -- by setting a arbitrarily high
+bound, no guarantee is made that it can be met. Similarly, a low bound
+can not always be met until buffered messages are consumed.
+
+      Thus a receiving process, by setting the current message bound to
+zero, effectively disables the transmission of new messages. Thus,
+without the cooperation of the transmitting process, message generation
+can be temporarily disabled, while outstanding message buffers are
+flushed. Later the message allocation can be raised to its original
+limit and transmission can be resumed.
+
+ABILITY TO CLOSE A CHANNEL AT ANY TIME
+
+      A process should be able to close down a channel at any time. If
+the process has died, the system should be able to close all open
+channels for it. For channels over which the process was receiving data,
+pending input should be thrown away and indications returned to the
+transmitting system marking the channel as dead and identifying the last
+data item accepted. This identification will be in terms of the number
+of logical messages discarded and the number of bits left in the oldest
+message.
+
+      If a process closes a channel over which it had been sending,
+buffered output should be sent normally, and with it should be sent an
+indication that this is all of the input that will ever appear.
+
+
+
+
+
+
+
+
+                                                                [Page 9]
+
+RFC #150                 Use of IPC Facilities                5 May 1971
+
+ABILITY TO GIVE AWAY CHANNEL PRIVILEGES
+
+      The right to perform any of the operations discussed here is
+normally reserved by the process that established the channel. At times
+that process may wish to transfer some of its delegated power to another
+process, especially in an environment where one process may spawn
+another and resources must be passed to the newly created process.
+
+      Schemes for such reassignment can become arbitrarily complicated.
+One could, for example, assign each of the various aspects of usage
+individually and then separately assign the various rights of
+reassignment. Fortunately it is not always necessary that it become so
+elaborate, it is expected that in most cases the following simple
+strategy can suffice. The ability to close a channel is retained
+exclusively by the process that established the channel. If the channel
+is still open when the process dies, it is automatically closed by the
+system. All other uses of the channel remain outside system control. The
+channel is known by name and all processes to which the name has been
+given may make use of the channel. It is left to user level coordination
+to insure that only one process is actually making use of it at any one
+time.
+
+ABILITY TO INITIATE CHANNEL CREATION
+
+      For most cases channel establishment can be handled quite simply.
+A process announces to its local system that it listening on a 
+specified channel. It is connected to the first remote process that
+'dials' the right number. Identification of the caller takes place
+only after the channel has been established. In the event of a wrong
+number, the channel can be closed and the listening resumed. Callers
+trying to reach preestablished channels will get a 'busy signal'.
+
+      To 'dial' a remote process a process must specify a channel on
+which it is listening and a remote number. The system will then
+attempt to establish the connection. The channel will become 'busy'
+during this time.
+
+      For processes that prefer to avoid the complications of
+identifying remote callers, an additional feature can be added. By
+specifying both the local and remote channel identifiers a process can
+transfer to the system the responsibility for screening callers for
+the proper identification. The connection will only be accepted from
+the caller specified.
+
+
+                                                                [Page 10]
+
+RFC #150                 Use of IPC Facilities                5 May 1971
+
+
+ABILITY TO REPORT TRANSMISSION ERRORS
+
+      If after prescanning an input message a process should decide
+that it contains some sort of transmission error, it should be able to
+reject the message. The system should then invoke any internal error
+recovery mechanism that it may have implemented.
+
+POSTSCRIPT
+
+      The author welcomes any comments, questions, or corrections to
+this document. Even the most informal note or telephone call will be
+appreciated. Especially of interest are opinions about the usefulness
+of the discussion and wether or not there should be more papers
+directed at other of the basic questions of computer networking. If
+the consensus tends to the affirmative, then others are encouraged to
+contribute working papers on the problems of flow control, error
+handling, process ownership, accounting, resource control, and the
+like.
+
+
+RBK/TX2
+
+
+         [ This RFC was put into machine readable form for entry ]
+         [ into the online RFC archives by Michael Baudisch 9/97 ] 
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+                                                                [Page 11]
+
+