diff options
Diffstat (limited to 'doc/rfc/rfc62.txt')
| -rw-r--r-- | doc/rfc/rfc62.txt | 1122 |
1 files changed, 1122 insertions, 0 deletions
diff --git a/doc/rfc/rfc62.txt b/doc/rfc/rfc62.txt new file mode 100644 index 0000000..bb61d0c --- /dev/null +++ b/doc/rfc/rfc62.txt @@ -0,0 +1,1122 @@ + + + + + + +Network Working Group D. C. Walden +Request for Comments: 62 BBN Inc. +Supercedes NWG/RFC #61 3 August 1970 + + + A System for Interprocess Communication + in a + Resource Sharing Computer Network + +1. Introduction + + If you are working to develop methods of communications within a + computer network, you can engage in one of two activities. You can + work with others, actually constructing a computer network, being + influenced, perhaps influencing your colleagues. Or you can + construct an intellectual position of how things should be done in an + ideal network, one better than the one you are helping to construct, + and then present this position for the designers of future networks + to study. The author has spent the past two years engaged in the + first activity. This paper results from recent engagement in the + second activity. + + "A resource sharing computer network is defined to be a set of + autonomous, independent computer systems, interconnected so as to + permit each computer system to utilize all of the resources of the + other computer systems much as it would normally call a subroutine." + This definition of a network and the desirability of such a network + is expounded upon by Roberts and Wessler in [9]. + + The actual act of resource sharing can be performed in two ways: in + an ad hoc manner between all pairs of computer systems in the + network; or according to a systematic network-wide standard. This + paper develops one possible network-wide system for resource sharing. + + I believe it is natural to think of resources as being associated + with processes<1> and available only through communication with these + processes. Therefore, I view the fundamental problem of resource + sharing to be the problem of interprocess communication. I also + share with Carr, Crocker, and Cerf [2] the view that interprocess + communication over a network is a subcase of general interprocess + communication in a multi-programmed environment. + + These views have led me to perform a two-part study. First, a set of + operations enabling interprocess communication within a single time- + sharing system is constructed. This set of operations eschews many + of the interprocess communications techniques currently in use within + time-sharing systems -- such as communication through shared memory + -- and relies instead on techniques that can be easily generalized to + + + +Walden [Page 1] + +RFC 62 IPC for Resource Sharing 3 August 1970 + + + permit communication between remote processes. The second part of + the study presents such a generalization. The application of this + generalized system to the ARPA Computer Network [9] is also + discussed. + + The ideas enlarged upon in this paper came from many sources. + Particularly influential were -- 1) an early sketch of a Host + protocol for the ARPA Network by S. Crocker of UCLA and W. Crowther + of Bolt Beranek and Newman Inc. (BBN); 2) Ackerman and Plummer's + paper on the MIT PDP-1 time-sharing system [1]; and 3) discussions + with W. Crowther and R. Kahn of BBN about Host protocol, flow + control, and message routing for the ARPA Network. Hopefully, there + are also some original ideas in this note. I alone am responsible + for the collection of all of these ideas into the system described + herein, and I am therefore responsible for any inconsistencies or + bugs in the system. + + It must be emphasized that this paper does not represent an official + BBN position on Host protocol for the ARPA Computer Network. + + +2. A System for Interprocess Communication within a Time-Sharing System + + This section describes a set of operations enabling interprocess + communication within a time-sharing system. Following the notation + of [10], I call this interprocess communication facility an IPC. As + an aid to the presentation of this IPC, a model for a time-sharing + system is described; this model is then used to illustrate the use of + the interprocess communication operations. + + The model time-sharing has two pieces: the monitor and the processes. + The monitor performs such functions as switching control from one + process to another process when a process has used "enough" time, + fielding hardware interrupts, managing core and the swapping medium, + controlling the passing of control from one process to another (i.e., + protection mechanisms), creating processes,caring for sleeping + processes, and providing to the processes a set of machine extending + operations (often called Supervisor or Monitor Calls). The processes + perform the normal user functions (user processes) as well as the + functions usually thought of as being supervisor functions in a + time-sharing system (systems processes) but not performed by the + monitor in the current model. A typical system process is the disc + handler or the file system. System processes is the disc handler or + the file system. System processes are probably allowed to execute in + supervisor mode, and they actually execute I/O instructions and + perform other privileged operations that user processes are not + allowed to perform. In all other ways, user and system processes are + identical. For reasons of efficiency, it may be useful to think of + + + +Walden [Page 2] + +RFC 62 IPC for Resource Sharing 3 August 1970 + + + system processes as being locked in core. + + Although they will be of concern later in this study, protection + considerations are not my concern here: instead I will assume that + all of the processes are "good" processes which never made any + mistakes. If the reader needs a protection structure to keep in mind + while he reads this note, the capability system developed in + [1][3][7][8] should be satisfying. + + Of the operations a process can call on the monitor to perform, six + are of particular interest for providing a capability for + interprocess communication. + + RECEIVE. This operation allows a specified process to send a message + to the process executing the RECEIVE. The operation has four + parameters: the port (defined below) awaiting the message -- the + RECEIVE port; the port a message will be accepted from -- the SEND + port; a specification of the buffer available to receive the message; + and a location to transfer to when the transmission is complete -- + the restart location. + + SEND. This operation sends a message from the process executing the + SEND to a specified process. It has four parameters: a port to send + the message to -- the RECEIVE port; the port the message is being + sent from -- the SEND port; a specification of the buffer containing + the message to be sent; and the restart location. + + RECEIVE ANY. This operations allows any process to send a message to + the process executing the RECEIVE ANY. The operation has four + parameters: the port awaiting the message -- the RECEIVE port; a + specification of the buffer available to receive the message; a + restart location; and a location where the port which sent the + message may be noted. + + SEND FROM ANY. This operation allows a process to send a message to + a process able to receive a message from any process. It has the + same four parameters as SEND. (The necessity for this operation will + be explained much later). + + SLEEP. This operation allows the currently running process to put + itself to sleep pending the completion of an event. The operation + has one optional parameter, an event to be waited for. An example + event is the arrival of a hardware interrupt. The monitor never + unilaterally puts a process to sleep as a result of the process + executing one of the above four operations; however, if a process is + asleep when one of the above four operations is satisfied, the + process is awakened. + + + + +Walden [Page 3] + +RFC 62 IPC for Resource Sharing 3 August 1970 + + + UNIQUE. This operation obtains a unique number from the monitor. + + A port is a particular data path to a process (a RECEIVE port) or + from a process (a SEND port), and all ports have an associated unique + port number which is used to identify the port. Ports are used in + transmitting messages from one process to another in the following + manner. Consider two processes, A and B, that wish to communicate. + Process A executes a RECEIVE to port N from port M. Process B + executes a SEND to port N from port M. The monitor matches up the + port numbers and transfers the message from process B to process A. + As soon as the buffer has been fully transmitted out of process B, + process B is restarted at the location specified in the SEND + operation. As soon as the message is fully received at process A, + process A is restarted at the location specified in the RECEIVE + operation. Just how the processes come by the correct port numbers + with which to communicate with other processes is not the concern of + the monitor -- this problem is left to the processes. + + When a SEND is executed, nothing happens until a matching RECEIVE is + executed. Somewhere in the monitor there must be a table of port + numbers associated with processes and restart locations. The table + entries are cleared after each SEND/RECEIVE match is made. If a + proper RECEIVE is not executed for some time, the SEND is timed out + after a while and the SENDing process is notified. If a RECEIVE is + executed but the matching SEND does not happen for a long time, the + RECEIVE is timed out and the RECEIVing process is notified. + + The mechanism of timing out "unused" table entries is of little + fundamental importance, merely providing a convenient method of + garbage collecting the table. There is no problem if an entry is + timed out prematurely, because the process can always re-execute the + operation. However, the timeout interval should be long enough so + that continual re-execution of an operation will cause little + overhead. + + A RECEIVE ANY never times out, but may be taken back using a + supervisor call. A message resultant from a SEND FROM ANY is always + sent immediately and will be discarded if a proper receiver does not + exist. An error message is not returned and acknowledgment, if any, + is up to the processes. If the table where the SEND and RECEIVE are + matched up ever overflows, a process originating a further SEND and + RECEIVE is notified just as if the SEND or RECEIVE timed out. + + The restart location is an interrupt entrance associated with a + pseudo interrupt local to the process executing the operation + specifying the restart location. If the process is running when then + event causing the pseudo interrupt occurs (for example, a message + arrives satisfying a pending RECEIVE), the effect is exactly as if + + + +Walden [Page 4] + +RFC 62 IPC for Resource Sharing 3 August 1970 + + + the hardware interrupted the process and transferred control to the + restart location. Enough information is saved for the process to + continue execution at the point it was interrupted after the + interrupt is serviced. If the process is asleep, it is readied and + the pseudo interrupt is saved until the process runs again and the + interrupt is then allowed. Any RECEIVE or RECEIVE ANY message port + may thus be used to provide process interrupts, event channels, + process synchronization, message transfers, etc. The user programs + what he wants. + + It is left as an exercise to the reader to convince himself that the + monitor he is saddled with can be made to provide the six operations + described above -- most monitors can since these are only additional + supervisor calls. + + An example. Suppose that our model time-sharing system is + initialized to have several processes always running. Additionally, + these permanent processes have some universally known and permanently + assigned ports<2>. Suppose that two of the permanently running + processes are the logger-process and the teletype-scanner-process. + When the teletype-scanner-process first starts running, it puts + itself to sleep awaiting an interrupt from the hardware teletype + scanner. The logger-process initially puts itself to sleep awaiting + a message from the teletype-scanner-process via well-known permanent + SEND and RECEIVE ports. The teleype-scanner-process keeps a table + indexed by teletype number, containing in each entry a pair of port + numbers to use to send characters from that teletype to a process and + a pair of port numbers to use to receive characters for that teletype + from a process. If a character arrives (waking up the teletype- + scanner- process) and the process does not have any entry for that + teletype, it gets a pair of unique numbers from the monitor (via + UNIQUE) and sends a message containing this pair of numbers to the + logger-process using the ports for which the logger-process is known + to have a RECEIVE pending. The scanner-process also enters the pair + of numbers in the teletype table, and sends the character and all + future characters from this teletype to the port with the first + number from the port with the second number. The scanner-process + must also pass a second pair of unique numbers to the logger-process + for it to use for teletype output and do a RECEIVE using these port + numbers. When the logger-process receives the message from the + scanner-process, it starts up a copy of what SDS 940 TSS [6] users + call the executive<3>, and passes the port numbers to this copy of + the executive, so that this executive-process can also do its inputs + and outputs to the teletype using these ports. If the logger-process + wants to get a job number and password from the user, it can + temporarily use the port numbers to communicate with the user before + it passes them on to the executive. The scanner-process could always + use the same port numbers for a particular teletype as long as the + + + +Walden [Page 5] + +RFC 62 IPC for Resource Sharing 3 August 1970 + + + numbers were passed on to only one copy of the executive at a time. + + It is important to distinguish between the act of passing a port from + one process to another and the act of passing a port number from one + process to another. In the previous example, where characters from a + particular teletype are sent either to the logger-process or an + executive-process by the teletype-scanner-process, the SEND port + always remains in the teletype-scanner-process while the RECEIVE port + moves from the logger-process to the executive process. On the other + hand, the SEND port number is passed between the logger-process and + the executive-process to enable the RECEIVE process to do a RECEIVE + from the correct SEND port. It is crucial that, once a process + transfers a port to some other process, the first process no longer + use the port. We could add a mechanism that enforces this. The + protected object system of [9] is one such mechanism. Using this + mechanism, a process executing a SEND would need a capability for the + SEND port and only one capability for this SEND port would exist in + the system at any given time. A process executing a RECEIVE would be + required to have a capability for the RECEIVE port, and only one + capability for this RECEIVE port would exist at a given time. + Without such a protection mechanism, a port implicitly moves from one + process to another by the processes merely using the port at disjoint + times even if the port's number is never explicitly passed. + + Of course, if the protected object system is available to us, there + is really no need for two port numbers to be specified before a + transmission can take place. The fact that a process knows an + existing RECEIVE port number could be considered prima facie evidence + of the process' right to send to that port. The difference between + RECEIVE and RECEIVE ANY ports then depends solely on the number of + copies of a particular port number that have been passed out. A + system based on this approach would clearly be preferable to the one + described here if it was possible to assume that all autonomous + time-sharing systems in a network would adopt this protection + mechanism. If this assumption cannot be made, it seems more + practical to require both port numbers. + + Note that in the interprocess communication system (IPC) being + described here, when two processes wish to communicate they set up + the connection themselves, and they are free to do it in a mutually + convenient manner. For instance, they can exchange port numbers or + one process can pick all the port numbers and instruct the other + process which to use. However, in a particular implementation of a + time-sharing system, the builders of the system might choose to + restrict the processes' execution of SENDs and RECEIVEs and might + forbid arbitrary passing around of ports and port numbers, requiring + instead that the monitor be called (or some other special program) to + perform these functions. + + + +Walden [Page 6] + +RFC 62 IPC for Resource Sharing 3 August 1970 + + + Flow control is provided in this IPC by the simple method of never + starting data transmission resultant from a SEND from one process + until a RECEIVE is executed by the receiver. Of course, interprocess + messages may also be sent back and forth suggesting that a process + stop sending or that space be allocated. + + Generally, well-known permanently-assigned ports are used via RECEIVE + ANY and SEND FROM ANY. The permanent ports will most often be used + for starting processes and, consequently, little data will be sent + via them. If a process if running (perhaps asleep), and has a + RECEIVE ANY pending, then any process knowing the receive port number + can talk to that process without going through loggers. This is + obviously essential within a local time-sharing system and seems very + useful in a more general network if the ideal of resource sharing is + to be reached. For instance, in a resource sharing network, the + programs in the subroutine libraries at all sites might have RECEIVE + ANYs always pending over permanently assigned ports with well-known + port numbers. Thus, to use a particular network resource such as a + matrix manipulation hardware, a process running anywhere in the + network can send a message to the matrix inversion subroutine + containing the matrix to be inverted and the port numbers to be used + for returning the results. + + An additional example demonstrates the use of the FORTRAN compiler. + We have already explained how a user sits down at his teletype and + gets connected to an executive. We go on from there. The user is + typing in and out of the executive which is doing SENDs and RECEIVEs. + Eventually the user types RUN FORTRAN, and executive asks the monitor + to start up a copy of the FORTRAN compiler and passes to FORTRAN as + start up parameters the port numbers the executive was using to talk + to the teletype. (This, at least conceptually, FORTRAN is passed a + port at which to RECEIVE characters from the teletype and a port from + which to SEND characters to the teletype.) FORTRAN is, of course, + expecting these parameters and does SENDs and RECEIVEs via the + indicated ports to discover from the user what input and output files + the user wants to use. FORTRAN types INPUT FILE? to the user, who + responds F001. FORTRAN then sends a message to the file-system- + process, which is asleep waiting for something to do. The message is + sent via well-known ports and it asks the file system to open F001 + for input. The message also contains a pair of port numbers that the + file-system process can use to send its reply. The file-system looks + up F001, opens it for input, make some entries in its open file + tables, and sends back to FORTRAN a message containing the port + numbers that FORTRAN can use to read the file. The same procedure is + followed for the output file. When the compilation is complete, + FORTRAN returns the teletype port numbers (and the ports) back to the + executive that has been asleep waiting for a message from FORTRAN, + and then FORTRAN halts itself. The file-system-process goes back to + + + +Walden [Page 7] + +RFC 62 IPC for Resource Sharing 3 August 1970 + + + sleep when it has nothing else to do<4>. + + Again, the file-system process can keep a small collection of port + numbers which it uses over and over if it can get file system users + to return the port numbers when they have finished with them. Of + course, when this collection of port numbers has eventually dribbled + away, the file system can get some new unique numbers from the + monitor. + + +3. A System for Interprocess Communication Between Remote Processes + + The IPC described in the previous section easily generalizes to allow + interprocess communication between processes at geographically + different locations as, for example, within a computer network. + + Consider first a simple configuration of processes distributed around + the points of a star. At each point of the star there is an + autonomous operating system<5>. A rather large, smart computer + system, called the Network Controller, exists at the center of the + star. No processes can run in this center system, but rather it + should be thought of as an extension of the monitor of each of the + operating systems in the network. + + If the Network Controller is able to perform the operations SEND, + RECEIVE, SEND FROM ANY, RECEIVE ANY, and UNIQUE and if all of the + monitors in all of the time-sharing systems in the network do not + perform these operations themselves but rather ask the Network + Controller to perform these operations for them, then the problem of + interprocess communication between remote processes if solved. No + further changes are necessary since the Network Controller can keep + track of which RECEIVEs have been executed and which SENDs have been + executed and match them up just as the monitor did in the model + time-sharing system. A networkwide port numbering scheme is also + possible with the Network Controller knowing where (i.e., at which + site) a particular port is at a particular time. + + Next, consider a more complex network in which there is no common + center point, making it necessary to distribute the functions + performed by the Network Controller among the network nodes. In the + rest of this section I will show that it is possible to efficiently + and conveniently distribute the functions performed by the star + Network Controller among the many network sites and still enable + general interprocess communication between remote processes. + + Some changes must be made to each of the four SEND/RECEIVE operations + described above to adapt them for use in a distributed Network + Controller. To RECEIVE is added a parameter specifying a site to + + + +Walden [Page 8] + +RFC 62 IPC for Resource Sharing 3 August 1970 + + + which the RECEIVE is to be sent. To the SEND FROM ANY and SEND + messages is added a site to send the SEND to although this is + normally the local site. Both RECEIVE and RECEIVE ANY have added the + provision for obtaining the source site of any received message. + Thus, when a RECEIVE is executed, the RECEIVE is sent to the site + specified, possibly a remote site. Concurrently a SEND is sent to + the same site, normally the local site of the process executing the + SEND. At this site, called the rendezvous site, the RECEIVE is + matched with the proper SEND and the message transmission is allowed + to take place from the SEND site to the site from whence the RECEIVE + came. + + A RECEIVE ANY never leaves its originating site and therein lies the + necessity for SEND FROM ANY, since it must be possible to send a + message to a RECEIVE ANY port and not have the message blocked + waiting for a RECEIVE at the sending site. It is possible to + construct a system so the SEND/RECEIVE rendezvous takes place at the + RECEIVE site and eliminates the SEND FROM ANY operation, but in my + judgment the ability to block a normal SEND transmission at the + source site more than makes up for the added complexity. + + At each site a rendezvous table is kept. This table contains an + entry for each unmatched SEND or RECEIVE received at that site and + also an entry for all RECEIVE ANYs given at that site. A matching + SEND/RECEIVE pair is cleared from the table as soon as the match + takes place. As in the similar table kept in the model time-sharing, + SEND and RECEIVE entries are timed out if unmatched for too long and + the originator is notified. RECEIVE ANY entries are cleared from the + table when a fulfilling message arrives. + + The final change necessary to distribute the Network Controller + functions is to give each site a portion of the unique numbers to + distribute via its UNIQUE operation. I'll discuss this topic further + below. + + To make it clear to the reader how the distributed Network Controller + works, an example follows. The details of what process picks port + numbers, etc., are only exemplary and are not a standard specified as + part of the IPC. + + Suppose that, for two sites in the network, K and L, process A at + site K wishes to communicate with process B at site L. Process B has + a RECEIVE ANY pending at port M. + + + + + + + + +Walden [Page 9] + +RFC 62 IPC for Resource Sharing 3 August 1970 + + + SITE K SITE L + + ______ ______ + / \ / \ + / \ / \ + / \ / \ + / \ / \ + | | | | + | Process A | | Process B | + | | | | + \ / \ / + \ / RECEIVE--> port M / + \ / ANY \ / + \______/ \______/ + + + Process A, fortunately, knows of the existence of port M at site L and + sends a message using the SEND FROM ANY operation from port N to port + M. The message contains two port numbers and instructions for process + B to SEND messages for process A to port P from port Q. Site K's site + number is appended to this message along with the message's SEND port N. + + SITE K SITE L + + ______ ______ + / \ / \ + / \ / \ + / \ / \ + / \ / \ + | | | | + | Process A | | Process B | + | | | | + \ port N / \ port M / + \ /--->SEND FROM --->\ / + \ / ANY \ / + \______/ \______/ + + to port M, site L + + containing K,N,P, & Q + + Process A now executes a RECEIVE at port P from port Q. Process A + specifies the rendezvous site to be site L. + + + + + + + + +Walden [Page 10] + +RFC 62 IPC for Resource Sharing 3 August 1970 + + + SITE K SITE L + + ______ ______ + / \ / \ + / \ / \ + / \ Rendezvous/ \ + / \ table \ + | | | | + | Process A | ^ | Process B | + | | | | | + \ port P / | \ / + \ / | \ / + \ / <--RECEIVE __/ \ / + \______/ MESSAGE \______/ + + to site L + + containing P, Q, & K + + + A RECEIVE message is sent from site K to site L and is entered in the + rendezvous table at site L. At some other time, process B executes a + SEND to port P from port Q specifying site L as the rendezvous site. + + + SITE K SITE L + + ______ ______ + / \ / \ + / \ / \ + / \ Rendezvous/ \ + / \ table \ + | | | | + | Process A | | Process B | + | | | | + \ port P / <--------- port Q / + \ / \ / + \ / SEND \ / + \______/ \______/ + to site L + + containing P & Q + + A rendezvous is made, the rendezvous table is cleared, and the + transmission to port P at site K takes place. The SEND site number + (and conceivably the SEND port number) is appended to the messages of + the transmission for the edification of the receiving process. + + + + +Walden [Page 11] + +RFC 62 IPC for Resource Sharing 3 August 1970 + + + SITE K SITE L + + ______ ______ + / \ / \ + / \ / \ + / \ / \ + / \ / \ + | | | | + | Process A | | Process B | + | | | | + \ port P / \ port Q / + \ /<--transmission<--\ / + \ / \ / + \______/ to port P, site K \______/ + + containing data and L + + Process B may simultaneously wish to execute a RECEIVE from port N at + port M. + + Note that there is only one important control message in this system + which moves between sites, the type of message that is called a + Host/Host protocol message in [2]. This control message is the + RECEIVE message. There are two other possible intersite control + messages: an error message to the originating site when a RECEIVE or + SEND is timed out, and the SEND message in the rare case when the + rendezvous site is not the SEND site. There must also be a standard + format for messages between ports. For example, the following: + + + + + + + + + + + + + + + + + + + + + + + +Walden [Page 12] + +RFC 62 IPC for Resource Sharing 3 August 1970 + + + _________________ __________________ _____________ + | rendezvous site | <6> | destination site | | source site | + |-----------------| |------------------| |-------------| + | RECEIVE port | | RECEIVE port | | RECEIVE port| + |-----------------| |------------------| |-------------| + | SEND port | | SEND port | | SEND port | + |-----------------| |------------------| |-------------| + | | | source site | | | + | | |------------------| | | + | | | | | | + | | | | | | + | | | | | | + | | | | | | + | data | | data | | data | + | | | | | | + | | | | | | + | | | | | | + | | | | | | + |_________________| |__________________| |_____________| + transmitted transmitted received + by SEND by Network by RECEIVE + process Controller process + + In the model time-sharing system it was possible to pass a port form + process to process. This is still possible with a distributed Network + Controller. + + Remember that, for a message to be sent from one process to another, a + SEND to port M from port N and a RECEIVE at port M from port N must + rendezvous, normally at the SEND site. Both processes keep track of + where they think the rendezvous site is and supply this site as a + parameter of appropriate operations. The RECEIVE process thinks it is + the SEND site also. Since once a SEND and a RECEIVE rendezvous the + transmission is sent to the source of the RECEIVE and the entry in the + rendezvous table is cleared and must be set up again for each further + transmission from N to M, it is easy for a RECEIVE port to be moved. + If a process sends both the port numbers and the rendezvous site + number to a new process at some other site which executes a RECEIVE + using these same old port numbers and rendezvous site specification, + the SENDer never knows the RECEIVEr has moved. It is slightly harder + for a send port to move. However, if it does, the pair of port + numbers that has been being used for a SEND and the original + rendezvous site number are passed to the new site. The process at the + new SEND site specifies the old rendezvous site with the first SEND + from the new site. The RECEIVE process will also still think the + rendezvous site is the old site, so the SEND and RECEIVE will meet at + the old site. When they meet, the entry in the table at that site is + cleared, and both the SEND and RECEIVE messages are sent to the new + + + +Walden [Page 13] + +RFC 62 IPC for Resource Sharing 3 August 1970 + + + SEND site just as if they had been destined for there in the first + place. The SEND and RECEIVE then meet again at the new rendezvous + site and transmission may continue as if the port had never moved. + Since all transmissions contain the source site number, further + RECEIVEs will be sent to the new rendezvous site. It is possible to + discover that this special manipulation must take place because a SEND + message is received at a site that did not originate the SEND + message<7>. Note that the SEND port and the RECEIVE port can move + concurrently. + + Of course, all of this could have also been done if the processes had + sent messages back and forth announcing any potential moves and the + new site numbers. + + A problem that may have occurred to the reader is how the SEND and + RECEIVE buffers get matched for size. The easiest solution would be + to require that all buffers have a common size but this is + unacceptable since it does not easily extend to a situation where + processes in autonomous operating systems are attempting to + communicate. A second solution is for the processes to pass messages + specifying buffer sizes. If this solution is adopted, excessive data + sent from the SEND process and unable to fix into the RECEIVE buffer + is discarded and the RECEIVE process notified. The solution has great + appeal on account of its simplicity. A third solution would be for + the RECEIVE buffer size to be passed to the SEND site with RECEIVE + message and to notify the SEND process when too much data is sent or + even to pass the RECEIVE buffer size on to the SEND process. This + last method would also permit the Network Controller at the SEND site + to make two or more SENDs out of one, if that was necessary to match a + smaller RECEIVE buffer size. + + The maintenance of unique numbers is also a problem when the processes + are geographically distributed. Three solutions to this problem are + presented here. The first possibility is for the autonomous operating + systems to ask the Network Controller for the unique numbers + originally and then guarantee the integrity of any unique numbers + currently owned by local processes and programs using whatever means + are at the operating system's disposal. In this case, the Network + Controller would provide a method for a unique number to be sent from + one site to another and would vouch for the number's identity at the + new site. The second method is simply to give the unique numbers to + the processes that are using them, depending on the non-malicious + behavior of the processes to preserve the unique numbers, or if an + accident should happen, the two passwords (SEND and RECEIVE port + numbers) that are required to initiate a transmission. If the unique + numbers are given out in a non-sequential manner and are reasonably + long (say 32 bits), there is little danger. In the final method, a + user identification is included in the port numbers and the individual + + + +Walden [Page 14] + +RFC 62 IPC for Resource Sharing 3 August 1970 + + + operating systems guarantee the integrity of these identification + bits. Thus a process, while not able to be sure that the correct port + is transmitting to him, can be sure that some port of the correct user + is transmitting. This is the so-called virtual net concept suggested + by W. Crowther [2].<8> + + A third difficult problem arises when remote processes wish to + communicate, the problem of maintaining high bandwidth connections + between the remote processes. The solution to this problem lies in + allowing the processes considerable information about the state of an + on-going transmission. First, we examine a SEND process in detail. + When a process executes a SEND, the local portion of the Network + Controller passes the SEND on to the rendezvous site, normally the + local site. When a RECEIVE arrives matching a pending SEND, the + Network Controller notifies the SEND process by causing an interrupt + to the specified restart location. Simultaneously the Network + Controller starts shipping the SEND buffer to the RECEIVE site. When + transmission is complete, a flag is set which the SEND process can + test. While a transmission is taking place, the process may ask the + Network Controller to perform other operations, including other SENDs. + A second SEND over a pair of ports already in the act of transmission + is noted and the SEND becomes active as soon as the first transmission + is complete. A third identical SEND results in an error message to + the SENDing process. Next, we examine a RECEIVE process in detail. + When a process executes a RECEIVE, the RECEIVE is sent to the + rendezvous site. When data resultant from this RECEIVE starts to + arrive at the RECEIVE site, the RECEIVE process is notified via an + interrupt to the specified restart location. When the transmission is + complete, a flag is set which the RECEIVE process can test. A second + RECEIVE over the same port pair is allowed. A third results in an + error message to the RECEIVE process. Thus, there is sufficient + machinery to allow a pair of processes always to have both a + transmission in progress and the next one pending. Therefore, no + efficiency is lost. On the other hand, each transmission must be + preceded by a RECEIVE into a specified buffer, thus continuing to + provide complete flow control. + + +4. A Potential Application + + Only one resource sharing computer network currently exists, the + ARPA Computer Network. In this section, I discuss application of the + system described in this paper to the ARPA Network [2][5][9]. + + The ARPA Network currently incorporates ten sites spread across the + United States. Each site consists of one to three (potentially four) + independent computer systems called Hosts and one communications + computer system called an IMP. All of the Hosts at a site are + + + +Walden [Page 15] + +RFC 62 IPC for Resource Sharing 3 August 1970 + + + directly connected to the IMP. The IMPs themselves are connected + together by 50-kilobit phone lines (much higher rate lines are a + potential), although each IMP is connected to only one to five other + IMPs. The IMPs provide a communications subnet through which the + Hosts communicate. Data is sent through the communications subnet in + messages of arbitrary size (currently about 8000 bits) called network + messages. When a network message is received by the IMP at the + destination site, that IMP sends an acknowledgment, called a RFNM, to + the source site. + + A system for interprocess communication for the ARPA Network (let us + call this IPC for ARPA) is currently being designed by the Network + Working Group, under the chairmanship of S. Crocker of UCLA. Their + design is somewhat constrained by the communications subnet [5]<9>. + I would like to compare point-by-point IPC for ARPA with the one + developed in this paper; however, such a comparison would first + require description here, almost from scratch, of the current state + of IPC for ARPA since very little up-to-date information about IPC + for ARPA appears in the open literature [2]. Also, IPC for ARPA is + quite complex and the working documents describing it now run to many + hundred pages, making any description lengthy and inappropriate for + this paper.<10> Therefore, I shall make only a few scattered + comparisons of the two systems, the first of which are implicit in + this paragraph. + + The interprocess communication system being developed for the ARPA + Network comes in several almost distinct pieces: The Host/IMP + protocol, IMP/IMP protocol, and the Host/Host protocol. The IMPs + have sole responsibility for correctly transmitting bits from one + site to another. The Hosts have sole responsibility for making + interprocess connections. Both the Host and IMP are concerned and + take a little responsibility for flow control and message sequencing. + Applications of the interprocess communication system described in + this paper leads me to make a different allocation of responsibility. + The IMP still continues to move bits from on site to another + correctly but the Network Controller also resides in the IMP, and + flow control is completely in the hands of the processes running in + the Hosts, although using the mechanisms provided by the IMPs. + + The IMPs provide the SEND, RECEIVE, SEND FROM ANY, RECEIVE ANY, and + UNIQUE operations in slightly altered forms for the Hosts and also + maintain the rendezvous tables, including moving of SEND ports when + necessary. Putting these operations in the IMP requires the + Host/Host protocol program to be written only once, rather than many + times as is currently being done in the ARPA Network. It is perhaps + useful to step through the five operations again. + + SEND. The Host gives the IMP a SEND port number, a RECEIVE port + + + +Walden [Page 16] + +RFC 62 IPC for Resource Sharing 3 August 1970 + + + number, the rendezvous site, and a buffer specification (e.g., start + and end, or beginning and length). The SEND is sent to the + rendezvous site IMP, normally the local IMP. When a matching RECEIVE + arrives at the local IMP, the Host is notified of the RECEIVE port of + the just arrived message. This port number is sufficient to identify + the SENDing process, although a given operating system may have to + keep internal tables mapping this port number into a useful internal + process identifier. Simultaneously, the IMP begins to ask the Host + for specific pieces of the SEND buffer, sending these pieces as + network messages to the destination site. If a RFNM is not received + for too long, implying a network message has been lost in the + network, the Host is asked for the same data again and it is + retransmitted.<11> Except for the last piece of a buffer, the IMP + requests pieces from the Host which are common multiplies of the word + size of the source Host, IMP, and destination Host. This avoids + mid-transmission word alignment problems. + + RECEIVE. The Host gives the IMP a SEND port, a RECEIVE port, a + rendezvous site, and a buffer description. The RECEIVE message is + sent to the rendezvous site. As the network messages making up a + transmission arrive for the RECEIVE port, they are passed to the Host + along with RECEIVE port number (and perhaps the SEND port number), + and an indication to the Host where to put this data in its input + buffer. When the last network message of the SEND buffer is passed + into the Host, it is marked accordingly and the Host can then detect + this. (It is conceivable that the RECEIVE message could also + allocate a piece of network bandwidth while making its network + traverse to the rendezvous site.) + + RECEIVE ANY. The Host gives the IMP a RECEIVE port and a buffer + descriptor. This works the same as RECEIVE but assumes the local + site to be the rendezvous site. + + SEND FROM ANY. The Host gives the IMP RECEIVE and SEND ports, the + destination site, and a buffer descriptor. The IMP requests and + transmits the buffer as fast as possible. A SEND FROM ANY for a + non-existent port is discarded at the destination site. + + In the ARPA Network, the Hosts are required by the IMPs to physically + break their transmissions into network messages, and successive + messages of a single transmission must be delayed until the RFNM is + received for the previous message. In the system described here, + since RFNMs are tied to the transmission of a particular piece of + buffer and since the Hosts allow the IMPs to reassemble buffers in + the Hosts by the IMP telling the Host where to put each buffer piece + then pieces of a single buffer can be transmitted in parallel network + messages and several RFNMs can be outstanding simultaneously. This + enables The Hosts to deal with transmissions of more natural sizes + + + +Walden [Page 17] + +RFC 62 IPC for Resource Sharing 3 August 1970 + + + and higher bandwidth for a single transmission. + + For additional efficiency, the IMP might know the approximate time it + takes for a RECEIVE to get to a particular other site and warn the + Host to wake up a process shortly before the arrival of a message for + that process is imminent. + + + 5. Conclusion + + Since the system described in this paper has not been implemented, I + have no clearly demonstrable conclusions nor any performance reports. + Instead, I conclude with four openly subjective claims. + + 1) The interprocess communication system described in Section 2 is + simpler and more general than most existing systems of equivalent + power and is more powerful than most intra time-sharing system + communication systems currently available. + + 2) Time-sharing systems structured like the model in Section 2 should + be studied by designers of time-sharing systems who may see a + computer network in their future, as structure seems to enable + joining a computer network with a minimum of difficulty. + + 3) As computer networks become more common, remote interprocess + communication systems like the one described in Section 3 should be + studied. The system currently being developed for ARPA is a step in + the wrong direction, being addressed, in my opinion, more to + communication between monitors than to communication between + processes and consequently subverting convenient resource sharing. + + 4) The application of the system as described in Section 4 is much + simpler to implement and more powerful than the system currently + being constructed for the ARPA Network, and I suggest that + implementation of my method be seriously considered for adoption by + the ARPA Network. + + + <Footnotes> + + 1. Almost any of the common definitions of a process would suit the + needs of this paper. + + 2. Or perhaps there is only one permanently known port, which + belongs to a directory-process that keeps a table of + permanent-process/well-know-port associations. + + 3. That program which prints file directories, tells who is on other + + + +Walden [Page 18] + +RFC 62 IPC for Resource Sharing 3 August 1970 + + + teletypes, runs subsystems, etc. + + 4. The reader should have noticed by now that I do not like to think + of a new process (consisting of a new conceptual copy of a + program) being started up each time another user wishes to use + the program. Rather, I like to think of the program as a single + process which knows it is being used simultaneously by many other + processes and consciously multiplexes among the users or delays + service to users until it can get around to them. + + 5. I use operating system rather than time-sharing system in this + section to point up the fact that the autonomous systems at the + network nodes may be either full blown time-sharing systems in + their own right, and individual process in a larger + geographically distributed time-sharing system, or merely + autonomous sites wishing to communicate. + + 6. For a SEND FROM ANY message, the rendezvous site is the + destination site. + + 7. For readers familiar with the once-proposed re-connection scheme + for the ARPA Network, the above system is simple, comparatively, + because there are no permanent connections to break and move; + that is, connections only exist fleetingly in the system + described here and can therefore be remade between any pair of + processes which at any time happen to know each other's port + numbers and have some clue where they each are. + + 8. Crowther says this is not the virtual net concept. + + 9. As one of the builders of the ARPA communications subnet, I am + partially responsible for these constraints. + + 10. The reader having access to the ARPA working documents may want + to read Specifications for the Interconnection of a Host to + an IMP, BBN Report No. 1822; and ARPA Network Working Group + Notes #36, 37, 38, 39, 42, 44, 46, 47, 48, 49, 50, 54, 55, 56, + 57, 58, 59, 60. + + 11. This also allows messages to be completely thrown away by the IMP + subnet it that should ever be useful. + + + [REFERENCES] + + 1. Ackerman, W., and Plummer, W. An implementation of a + multi-processing computer system. Proc. ACM Symp. on + Operating System Principles, Gatlinsburg, Tenn., + + + +Walden [Page 19] + +RFC 62 IPC for Resource Sharing 3 August 1970 + + + Oct. 1-4, 1967. + + 2. Carr, C. Crocker, S., and Cerf, V. Host/Host communication + protocol in the ARPA network. Proc. AFIPS 1970 Spring + Joint Comput. Conf., Vol. 36, AFIPS Press, Montvale, N.J., + pp. 589-597. + + 3. Dennis, J., and VanHorn, E. Programming semantics for + multiprogrammed computations. Comm. ACM 9, 3 (March, + 1966), 143-155. + + 4. Hansen, P.B. The nucleus of a multiprogramming system. Comm. + ACM 13, 4 (April, 1970), 238-241, 250. + + 5. Heart, F., Kahn, R., Ornstein, S., Crowther, W., and Walden, D. + The interface message processor for the ARPA computer + network. Proc. AFIPS 1970 Spring Joint Comput. Conf., Vol. + 36, AFIPS Press, Montvale, N.J., pp. 551-567. + + 6. Lampson, B. SDS 940 Lectures, circulated informally. + + 7. _______. An overview of the CAL time-sharing system. Computer + Center, University of California, Berkeley, Calif. + + 8. _______. Dynamic protection structures. Proc. AFIPS 1969 Fall + Joint Comput. Conf., Vol. 35, AFIPS Press, Montvale, N.J., + pp. 27-38. + + 9. Roberts, L., and Wessler, B. Computer network development to + achive resource sharing. Proc. AFIPS 1970 Spring Joint + Comput. Conf., Vol. 36, AFIPS Press, Monvale, N.J., pp. + 543-549. + + 10. Spier, M., and Organick, E. The MULTICS interprocess + communication facility. Proc. ACM Second Symp. on Operating + Systems Principles, Princeton University, Oct. 20-22, 1969. + + + +Author's Address + + D. C. Walden + Bolt Bernakek and Newman, Inc. + Cambridge, Massachusetts + + + [ This RFC was put into machine readable form for entry ] + [ into the online RFC archives by Adam Costello 3/97 ] + + +Walden [Page 20] + |