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 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.
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.
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.
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:
_________________ __________________ _____________
| 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 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 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.