summaryrefslogtreecommitdiff
path: root/doc/rfc/rfc61.txt
diff options
context:
space:
mode:
Diffstat (limited to 'doc/rfc/rfc61.txt')
-rw-r--r--doc/rfc/rfc61.txt1011
1 files changed, 1011 insertions, 0 deletions
diff --git a/doc/rfc/rfc61.txt b/doc/rfc/rfc61.txt
new file mode 100644
index 0000000..8f7ccb3
--- /dev/null
+++ b/doc/rfc/rfc61.txt
@@ -0,0 +1,1011 @@
+
+
+
+
+
+
+Network Working Group Dave Walden
+Request for Comments: 61 Bolt Beranek and Newman
+ July 17, 1970
+
+ A Note on Interprocess Communication
+ in a Resource Sharing Computer Network
+
+
+ The attached note is a draft of a study I am still working on. It
+ may be of general interest to network participants.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Walden [Page 1]
+
+RFC 61 Interprocess Communication in a Computer Network July 1970
+
+
+ Interprocess Communication
+ in a
+ Resource Sharing Computer Network
+
+INTRODUCTION
+
+ "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 each
+ other computer system. That is, a program running in one computer
+ system should be able to call on 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 [1].
+
+ The actual act of resource sharing can be performed in two ways: in a
+ pairwise 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 [2] and therefore view the fundamental problem of
+ resource sharing to be the problem of interprocess communication. I
+ also share with Carr, Crocker, and Cerf [3] the view that
+ interprocess communication over a network is a subcase of general
+ interprocess communication in a multiprogrammed environment.
+
+ These views pervade this study and have led to a two part study.
+ First, a model for a time-sharing system having capabilities
+ particularly suitable for enabling interprocess communication is
+ constructed. Next, it is shown that these capabilities can be easily
+ used in a generalized manner which permits interprocess communication
+ between processes distributed over a computer network.
+
+ This note contains ideas based on many sources. Particularly
+ influential were -- 1) an early sketch of a Host protocol for the
+ ARPA Network [1][3][4] by W. Crowther of Bolt Beranek and Newman Inc.
+ (BBN) and S. Crocker of UCLA; 2) Ackerman and Plummer's paper on the
+ MIT PDP-1 time sharing system [5]; and 3) discussion with R. Kahn of
+ BBN about Host protocol, message control, and 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 this system.
+
+ It must be emphasized that this note does not represent an official
+ BBN position on Host protocol for the ARPA Computer Network.
+
+
+
+
+Walden [Page 2]
+
+RFC 61 Interprocess Communication in a Computer Network July 1970
+
+
+A MODEL FOR A TIME-SHARING SYSTEM
+
+ This section describes a model time-sharing system which I think is
+ particularly suitable for performing interprocess communication. The
+ basic structure of this model time-sharing system is not original
+ [5][9].
+
+ The model time-sharing system has two pieces: the monitor and the
+ processes. The monitor performs several functions, including
+ switching control from process to process as appropriate (e.g., when
+ a process has used "enough" time or when an interrupt occurs),
+ 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, etc.
+
+ The processes perform most of the functions normally thought of as
+ being supervisor functions in a time-sharing system (system
+ processes) as well as the normal user functions (user processes). A
+ typical system process is the disc handler or the file system. For
+ efficiency reasons it may be useful to think of system processes as
+ being locked in core.
+
+ A process can call on the monitor to perform several functions: start
+ another, equal, autonomous process (i.e., load a program or find a
+ copy of a program somewhere that can be shared, start it, and pass it
+ some initial parameters); halt the running process; put the current
+ process to sleep pending a specified event; send a message to a
+ specified process; become available to receive a message from a
+ specified process; become available to receive a message from any
+ process; send a message to a process able to receive from any
+ process; and request a unique number. There undoubtedly should also
+ be other monitor functions. It is left as an exercise to the reader
+ to convince himself that the monitor he is saddled with can be made
+ to provide these functions -- most can.
+
+ I will not concern myself with protection considerations here, but
+ instead will assume all of the processes are "good" processes which
+ never make any mistakes. If the reader needs a protection structure
+ to keep in mind while he reads this note, the _capability_ system
+ described in [5][6][7][8] should be satisfying.
+
+ We now look a little closer at the eight operations listed above that
+ a process can ask the monitor to perform.
+
+
+
+
+
+
+
+
+Walden [Page 3]
+
+RFC 61 Interprocess Communication in a Computer Network July 1970
+
+
+ START. This operation starts another process. It has two
+ parameters -- some kind of identification for the program that is to
+ be loaded and a parameter list for that program. Once the program
+ is loaded, it is started at its given entry point and passed its
+ parameter list in some well known manner. The process will continue
+ to exist until it halts itself.
+
+ HALT. This operation puts the currently running process to sleep
+ pending the completion of some event. The operation has one
+ parameter, the event to be waited for. Sample events are arrival of
+ a hardware interrupt, arrival of a message from another process, etc.
+ The process is restarted at the instruction after the SLEEP command.
+ The monitor never unilaterally puts a process to sleep except when
+ the process overflows its quantum.
+
+ RECEIVE. This operation allows another process to send a message to
+ this process. The operation has four parameters: the port (defined
+ below) awaiting the message, the port a message will be accepted
+ from, a specification of the buffer available to receive the message,
+ and a location of transfer to when the transmission is complete. [In
+ other words, an interrupt location. Any message port may be used to
+ allow interrupts, event channels, etc. The user programs what he
+ wants.]
+
+ SEND. This operation sends a message to some other process. [I
+ suppose a process could also send a message to itself.] It has four
+ parameters: a port to send the message to, the port the message is
+ being sent from, the message, and a location to transfer to when the
+ transmission is complete.
+
+ RECEIVE ANY. This operation allows any process to send a message to
+ this process. The operation has four parameters: the port awaiting
+ the message, the buffer available to receive the message, a location
+ to transfer to when the message is received, 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 discussed below.
+
+ UNIQUE. This operation obtains a unique number from the monitor.
+
+ A _port_ is a particular data path to or from a process. All ports
+ have an associated unique number which is used to identify the port.
+ Ports are used in transmitting messages from one process to another
+ in the following fashion. Consider two processes, A and B, wishing
+ to communicate. Process A executes a RECEIVE at port N from port M.
+
+
+
+Walden [Page 4]
+
+RFC 61 Interprocess Communication in a Computer Network July 1970
+
+
+ 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.
+
+ 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. [Or perhaps there is only one permanently known port
+ which belongs to a directory-process which keeps a table of
+ permanent-process/well-known-port associations.] 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 teletype-
+ scanner-process keeps a table indexed by teletype number containing
+ in each entry a port to send characters from that teletype to, and a
+ port at which to receive characters for that teletype. 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
+ that the logger-process is known to have a RECEIVE pending for.
+ [Actually, the scanner process could always use the same pair of port
+ numbers for a particular teletype as long as they were passed on to
+ only one copy of the executive at a time.] The scanner-process also
+ enters the pair of numbers in the teletype table, and sends the
+ characters and all future characters from this teletype to the port
+ with the first number from the port with the second number. The
+ scanner-process probably also passes a second pair of unique numbers
+ to the logger-process for it to use for teletype output and does a
+ RECEIVE using these numbers. The logger-process when it receives the
+ message from the scanner-process, starts up a copy of what SDS 940
+ TSS [12] users call the executive (that program which prints file
+ directories, tells who is on other teletypes, runs subsystems, etc.)
+ and passes this copy of the executive, the port numbers so this
+ executive-process can also do its in's and out's 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.
+
+
+
+Walden [Page 5]
+
+RFC 61 Interprocess Communication in a Computer Network July 1970
+
+
+ _Port numbers_ are often passed among processes. More rarely, a port
+ is transferred to another process. It is crucial that once a process
+ transfers a _port_ to some other process that the first process no
+ longer use the port. We could add a mechanism that enforces this.
+ The protected object system of [8] is one such mechanism. [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 is 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 all of the autonomous time-sharing
+ system 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 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. Also note
+ that if a process is running (perhaps asleep), and has RECEIVE ANY
+ pending, then any process knowing the receive port number can talk to
+ that process without going through loggers or any of that. 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.
+
+ When a SEND is executed, nothing happens until a matching RECEIVE is
+ executed. 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.
+
+ A RECEIVE ANY never times out, but may be taken back. A SEND FROM
+ ANY message 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 or RECEIVE is notified just as if the SEND
+ or RECEIVE timed out.
+
+ 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 going and consequently little data
+ will be sent via them.
+
+
+
+
+
+Walden [Page 6]
+
+RFC 61 Interprocess Communication in a Computer Network July 1970
+
+
+ Still another example, this time a demonstration of 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 the
+ executive asks the monitor to start up a copy of the FORTRAN compiler
+ and passes to FORTRAN as start up parameters the two ports the
+ executive was using to talk to the teletype. FORTRAN is of course
+ expecting these parameters and does SENDs and RECEIVEs to these ports
+ to discover 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 ports that the file-system-process
+ can use to send its reply. The file-system looks up F001, opens it
+ for input, makes some entries in its open file tables, and sends a
+ message back to FORTRAN which contains the ports which 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 back to the executive which has been asleep waiting for
+ a message from FORTRAN, and then FORTRAN halts itself. The file-
+ system-process goes back to sleep when it has nothing else to do.
+
+ [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.]
+
+ 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 are done 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.
+
+ Note that 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. Of course, 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 port numbers, requiring instead
+ that the monitor be called (or some other special program) to perform
+ these functions.
+
+
+
+Walden [Page 7]
+
+RFC 61 Interprocess Communication in a Computer Network July 1970
+
+
+ Flow control is provided in this system by the simple method of never
+ starting a SEND from one process until a RECEIVE is executed by the
+ receiver. Of course, interprocess messages may be sent back and
+ forth suggesting that a process stop sending or that space be
+ allocated, etc.
+
+INTERPROCESS COMMUNICATION BETWEEN REMOTE PROCESS
+
+ The system 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 time-sharing system. 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 time-
+ sharing system in the network.
+
+ It should be obvious to the reader that if the Network Controller is
+ able to perform the operations SEND, RECEIVE, SEND FROM ANY, RECEIVE
+ ANY, and UNIQUE and that 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 we have solved the problem of interprocess
+ communication between remote processes. We have no further change to
+ make.
+
+ The reason everything continues to work when we postulate the
+ existence of the Network Controller is that 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. To
+ RECEIVE is added a parameter specifying a site to which the RECEIVE
+
+
+
+Walden [Page 8]
+
+RFC 61 Interprocess Communication in a Computer Network July 1970
+
+
+ is to be sent. To SEND FROM ANY and SEND 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 obtain 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 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. It must be possible to send a message
+ to a RECEIVE ANY port and not have the message blocked waiting for
+ RECEIVE at the sending site. Of course, it would be possible to
+ construct the system so the SEND/RECEIVE rendezvous takes place at
+ the RECEIVE site and eliminate 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.
+
+ Somewhere 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 or perhaps when the transmission is complete. As
+ in the similar table kept in the model time-sharing system, 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 system.
+
+ Suppose there are 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 61 Interprocess Communication in a Computer Network July 1970
+
+
+ SITE K SITE L
+ ________ ________
+ / \ / \
+ / \ / \
+ / \ / \
+ | Process A | | Process B |
+ | | | |
+ | | | |
+ \ / \ /
+ \ / \ port M /
+ \________/ \____^___/
+ |
+ RECEIVE ANY
+
+ Process A, fortunately, knows of the existence of port M at site L
+ and sends messages 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 to 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 /--->SEND FROM --->\ port M /
+ \________/ 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 61 Interprocess Communication in a Computer Network July 1970
+
+
+ SITE K SITE L
+ ________ R ________
+ / \ e / \
+ / \ n T/ \
+ / \ d a \
+ | | e b Process B |
+ | Process A | z l |
+ | | v e |
+ \ / o \ /
+ \ port P / RECEIVE ---> u \ /
+ \________/ MESSAGE s \________/
+
+ 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
+ ________ R ________
+ / \ e / \
+ / \ n T/ \
+ / \ d a \
+ | | e b Process B |
+ | Process A | z l |
+ | | v e |
+ \ / o \ /
+ \ port P / u <--- port Q /
+ \________/ SEND s \________/
+ to site L
+ containing P & Q
+
+
+ A rendezvous is made, the rendezvous table entry is cleared, and the
+ transmission to port P at site K takes place. The SEND site number
+ (and conceivably the SEND port number) are appended to the messages
+ of the transmission for the edification of the receiving process.
+
+
+
+
+
+
+
+
+
+
+
+Walden [Page 11]
+
+RFC 61 Interprocess Communication in a Computer Network July 1970
+
+
+ SITE K SITE L
+ ________ ________
+ / \ / \
+ / \ / \
+ / \ / \
+ | Process A | | Process B |
+ | | | |
+ | | | |
+ \ port P / \ port Q /
+ \ / <---- transmission <---- \ /
+ \________/ to port T, 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 [3]. 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.
+
+ Of course there must also be a standard format for messages between
+ ports. For example, the following:
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Walden [Page 12]
+
+RFC 61 Interprocess Communication in a Computer Network July 1970
+
+
+ +-----------------+ +-----------------+ +-----------------+
+ | rendezvous site | | destination site| | source site |
+ +-----------------+ +-----------------+ +-----------------+
+ | RECEIVE port | | RECEIVE port | | RECEIVE port |
+ +-----------------+ +-----------------+ +-----------------+
+ | SEND port | | SEND port | | SEND port |
+ +-----------------+ +-----------------+ +-----------------+
+ | | | source port | | |
+ | | +-----------------+ | |
+ | | | | | |
+ | | | | | |
+ | | | | | |
+ | | | | | |
+ | | | | | |
+ | data | | data | | data |
+ | | | | | |
+ | | | | | |
+ | | | | | |
+ | | | | | |
+ | | | | | |
+ | | | | | |
+ +-----------------+ +-----------------+ +-----------------+
+ transmitted transmitted received
+ by SEND by Network by RECEIVE
+ process Controller process
+
+ Note: for a SEND FROM ANY message, the rendezvous site is the
+ destination site.
+
+ In the model time-sharing system it was possible to pass a port from
+ process to process. This is still possible with a distributed
+ Network Controller. [The reader unconvinced of the utility of port
+ passing is directed to read the section on reconnection in [11].]
+
+ 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 and the SEND process normally 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
+
+
+
+Walden [Page 13]
+
+RFC 61 Interprocess Communication in a Computer Network July 1970
+
+
+ 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, the rendezvous site number for the
+ SEND message is changed to the site which originated the SEND message
+ and both the SEND and RECEIVE messages are sent to the new 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 which did not originate the SEND message.
+ Everything is so easily changed because there are no permanent
+ connections to break and move as in the once proposed reconnection
+ scheme for the ARPA network [10][11] 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.
+
+ Of course, all of this could have been done by the processes sending
+ messages back and forth announcing any potential moves and the new
+ site numbers.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Walden [Page 14]
+
+RFC 61 Interprocess Communication in a Computer Network July 1970
+
+
+REFERENCES
+
+ [1] L. Roberts and B. Wessler, Computer Network Development to
+ achieve Resource Sharing, Proceedings 1970 SJCC.
+
+ [2] V. Vyssotsky, F. F. Corbato, and R. Graham, Structure of the
+ MULTICS Supervisor, Proceedings 1965 FJCC.
+
+ [3] C. Carr, S. Crocker, and V. Cerf, Host/Host Communication
+ Protocol in the ARPA Network, Proceedings 1970 SJCC.
+
+ [4] F. Heart, et al, The Interface Message Processor for the ARPA
+ Computer Network, Proceedings 1970 SJCC.
+
+ [5] W. Ackerman and W. Plummer, An Implementation of Multi-
+ processing Computer System, Proceedings Gatlinburg Symposium on
+ Operating System Principles.
+
+ [6] J. Dennis and E. Van Horn, Programming Semantics for
+ Multiprogramming Computation, Proceedings of the San Dimes
+ Conference on Programming Language and Pragmatics.
+
+ [7] B. Lampson, Dynamic Protection Structures, Proceedings FJCC
+ 1969.
+
+ [8] B. Lampson, An Overview of the CAL Time-Sharing System, Computer
+ Center, University of Calif., Berkeley.
+
+ [9] P. Hansen, The Nucleus of a Multiprogramming System, CACM, April
+ 1970.
+
+ [10] S. Crocker, ARPA Network Working Group Note #36.
+
+ [11] J. Postel and S. Crocker, ARPA Network Working Group Note #48.
+
+ [12] B. Lampson, 940 Lectures.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Walden [Page 15]
+
+RFC 61 Interprocess Communication in a Computer Network July 1970
+
+
+APPENDIX: AN APPLICATION
+
+ Only one resource sharing computer network currently exists, the
+ aforementioned ARPA network. In this Appendix, I hope to show that
+ the system that was described in this note can be applied to the ARPA
+ network. A significant body of work exists on interprocess
+ communication within the ARPA network. This work comes in several
+ almost distinct pieces: the Host/IMP protocol, IMP/IMP protocol, and
+ the Host/Host protocol. I assume familiarity with this work in the
+ subsequent discussion. [See references [1][3][4][10][11];
+ Specifications for the Inter-connection of a Host to an IMP, BBN
+ Report No. 1822; and ARPA Network Working Group Notes #37, 38, 39,
+ 42, 44, 46, 47, 48, 49, 50, 54, 55, 56, 57, 56, 59.]
+
+
+ In the ARPA network, the IMP's 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. Application of the interprocess
+ communication system I have described leads me to different
+ allocation of responsibility. The IMP still continues to correctly
+ move bits from one site to another, 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 perhaps they use
+ 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.
+
+ It is perhaps easiest to step through the five operations again.
+
+ SEND. The Host gives the IMP a SEND port number, a RECEIVE port
+ number, the rendezvous site, and a buffer specification=20 (e.g.,
+ start and end, beginning and length). The SEND is sent to the
+ rendezvous site, normally the local site. When the matching RECEIVE
+ arrives, the Host is notified of the RECEIVE port of the just arrived
+ receive message. This port number is sufficient to identify the
+ SENDing process although a given time-sharing system may have to keep
+ internal tables mapping this port number into useful internal process
+ identifiers. Simultaneously, the IMP will begin to ask the Host for
+ specific chunks of the data buffer. These chunks will be sent off to
+ the destination as the IMP's RFNM control allows. If a RFNM is not
+ received for too long, implying a message has been lost in the
+ network, the Host is asked for the same chunk of data again [which
+ also allows messages to be completely thrown away by the IMP network
+
+
+
+Walden [Page 16]
+
+RFC 61 Interprocess Communication in a Computer Network July 1970
+
+
+ if that should ever be useful], but the Host has the option to abort
+ the transmission at this time. While a transmission is taking place,
+ the Host may ask the IMP 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 Host. If a SEND times out, an error is returned
+ also.
+
+ 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. When chunks of 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 the data in its input buffer. When the last of
+ the SEND buffer is passed into the Host, it is marked accordingly and
+ the Host can then detect this. A second RECEIVE over the same port
+ pair is allowed. A third results in an error message to the Host.
+ The mechanism described in this and the previous paragraphs allows a
+ pair of processes to always 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 providing complete flow control. (It is
+ conceivable that the RECEIVE message could 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.
+
+ RFNM's are tied to the transmission of a particular chunk of buffer
+ just as acknowledgments are now tied to packets and they perform the
+ same function. If the Hosts allow the IMPs to reassemble buffers in
+ the Hosts by the IMP telling the Host where it should put a buffer
+ chunk as described above, chunks of a single buffer can be
+ transmitted in parallel and several RFNMs can be outstanding
+ simultaneously. Packet reassembly is still done in the IMPs.
+
+ A final operation must be provided by the IMP -- the UNIQUE
+ operation. There are many ways to maintain unique numbers and three
+ are presented here. The first possibility is for the Hosts to ask
+ the IMPs for the unique numbers originally and then guarantee the
+
+
+
+Walden [Page 17]
+
+RFC 61 Interprocess Communication in a Computer Network July 1970
+
+
+ integrity of any unique numbers currently owned by local processes
+ and programs using whatever means the Host has at its disposal. In
+ this case the IMPs would provide a method for a unique number to be
+ sent from one host to another and would vouch for the number's
+ identity at the new site.
+
+ The second method is to simply 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 ports)
+ 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 time-sharing 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 [3].
+
+ Random Contents. 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. The IMPs can
+ stop a specific host transmission (by not asking for the next chunk
+ for a while) if that should seem necessary to alleviate congestion
+ problems in the communications subnet. And 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 it becomes
+ imminent that a message for that process will be arriving.
+
+
+
+
+
+
+
+
+
+
+
+ [ This RFC was put into machine readable form for entry ]
+ [ into the online RFC archives by Katsunori Tanaka 4/99 ]
+
+
+
+
+
+
+
+
+Walden [Page 18]
+