RFC 333
Proposed experiment with a Message Switching Protocol
RFC 333: A Proposed Experiment with a Message Switching Protocol 🎀
Okay bestie, let's get into RFC 333 💅 It's a Network Working Group doc (NIC # 9926) dated 15 May 1972, written by Bob Bressler (MIT/Dynamic Modeling), Dan Murphy (BBN/TENEX), and Dave Walden (BBN/IMP). It's Category C9 (experimentation) ✨, so this is an experiment and not a new standard. It obsoletes RFC 62 and doesn't update anything (Updates: none). Here's the full contents list:
Introduction .................................................. 1
Some Background ............................................... 2
References .................................................... 3
MSP Specification ............................................. 4
Issue ......................................................... 8
Message Header ................................................ 10
Examples ...................................................... 15
TELNET ........................................................ 16
The Information Operator ...................................... 16
Unique Port Numbers ........................................... 20
Flow Chart .................................................... 23
MSP Variations ................................................ 25
Appendix ...................................................... 26Introduction 🦋
So a message switching protocol (MSP) is a system whose whole job is switching messages between its ports 💌
For example, every Interface Message Processor runs an implementation of an MSP 🖥️ We think networked computer operating systems are going to need a much better understanding of MSPs if they're gonna use the network effectively. The thing is, the Network Control Programs (NCPs) on the ARPA Computer Network (ARPANET) don't really focus on the communications side of networking. Honestly, they show a bit of a reluctance from systems people to let go of what the note calls "the stream orientation" 🙈 So the plan is to keep developing the network with the current NCPs on the side, and meanwhile rethink the design of NCP-level software, starting from MSPs 🌸
The main point of this note is to sketch how you'd organize the lowest-level host-host protocol on the ARPANET around MSPs, and how that setup would change the way host software gets built 🧚
Some Background 🌸
Over the last few weeks there's been a ton of informal chatter about maybe running NCPs based on message switching (instead of line switching) on several ARPA Network Host Computers as an experiment 👀 (Check the parenthetical sentence in the first paragraph of page 6 of NIC document 8246, Host/Host Protocol for the ARPA Network, if you want the context.) The people in on this discussion were Bob Bressler (MIT/Dynamic Modeling), Steve Crocker (ARPA), Will Crowther (BBN/IMP), Tom Knight (MIT/AI), Alex McKenzie (BBN/IMP), Bob Metcalfe (MIT/Dynamic Modeling), Dan Murphy (BBN/TENEX), Jon Postel (UCLA/NMC), and Dave Walden (BBN/IMP) 🫶
A few interesting points came out of the chat:
- Bressler already built a message-switched interprocess communication system for the Dynamic Modeling PDP-10, and extended it so processes on the Dynamic Modeling PDP-10 and the AI PDP-10 could talk to each other. He says it's something like an order of magnitude smaller than his NCP 🤯
- Murphy pointed out that a message-switching Host/Host protocol could be implemented experimentally and run alongside the real Host/Host protocol, using some of the links set aside for experimentation. He also noted that if this experimental protocol got implemented in TENEX, a bunch of TENEX sites could easily join in 💻
- The discussants basically agreed that Bressler should take a crack at specifying a message switching protocol.* If that spec looked relatively easy to implement, Murphy and Bressler should seriously try to find the resources to implement the experimental protocol on the two BBN TENEX machines and the MIT Dynamic Modeling and AI machines 🔥
- MSP got picked as the acronym for Message Switching Protocol, and links 192-195 got reserved for an MSP experiment 🎀
Footnote *: This note fulfills any obligation Bressler may have incurred to produce an MSP specification.
The authors are asking the Network Working Group for comments and suggestions about this experiment, and they really do appreciate them 💖 But this is a limited experiment, not an attempt to replace the present Host/Host protocol for the ARPA Network. So they say they may arbitrarily reject suggestions. Not personal, just the vibe 😌
References 📚
Being familiar with the following references will help you through the rest of this note:
- NIC document 8246, HOST/HOST PROTOCOL FOR THE ARPA NETWORK
- NIC document 9348 on the Telnet Protocol
- NIC document 7101, OFFICIAL INITIAL CONNECTION PROTOCOL, DOCUMENT # 2
- a system of interprocess communication in a resource sharing computer network, CACM, April, 1972.
Reference 4 is a revision of RFC 62, and the authors strongly suggest you read it before this RFC. A reprint of reference 4 is attached as an appendix 📎
MSP Specification 🎀
Our MSP is basically a generalization of the interprocess communication system described in Section 3 of the fourth reference. (From here on, whenever we need to mention the interprocess communication system from Section 3 of reference 4, we'll just call it "the IPC".) 🌈
Here's the deal: for two processes to talk over the MSP, the sending process has to kind of execute a SEND, and the receiving process has to kind of execute a RECEIVE. The SEND and RECEIVE meet up somewhere (a rendezvous) and then the transmission can happen 🤝 The RECEIVE specifies (among other things) a FROM-TO-PORT-ID, a TO-PORT-ID, and a RENDEZVOUS HOST. The SEND specifies a from-port-id, a to-port-id, a rendezvous Host, and (maybe) some data to send.
So sending a message from a SENDER PROCESS to a RECEIVER PROCESS goes like this ✨ The sender runs a SEND, which causes an OUT-MESSAGE plus the specified data to be transmitted to the Host named as the rendezvous Host in the SEND. At around the same time (not necessarily simultaneously), the receiver runs a RECEIVE, which causes an IN-MESSAGE to be sent to the Host named as the rendezvous Host in the RECEIVE. At the rendezvous Host, OUT-messages and IN-messages get entered into a table called the RENDEZVOUS TABLE. When an OUT-message and an IN-message show up with matching to-port-id, from-port-id, and rendezvous Host, three things happen:
- the OUT-message plus the data gets forwarded to the Host that was the source of the IN-message,
- the IN-message gets forwarded to the Host that was the source of the OUT-message, and
- the IN-message and OUT-message plus the data get deleted from the rendezvous table in the rendezvous Host.
It's way simpler if the rendezvous Host is also either the send Host or the receive Host 🫧 The specific algorithms for these sequences show up later in this note.
To make the basic idea click, let's look at a case with three Hosts, which we'll call SND, RCV, and RNDZ. At Host SND, process S is doing a send, and at Host RCV, process R is doing a receive. Both of them specify rendezvous at Host RNDZ 🦋
+--------------------+ +----------+ +--------------------+
|HOST SND | | | |HOST RCV |
| | | | | |
| | | | | |
| (PROCESS) | +----------+ | |
| ( S ) | HOST | |
| \ | RNDZ | (PROCESS) |
| [DATA]| | ( R ) |
+--------------------+ +--------------------+Process S now executes a SEND with:
from-port-id = S, to-port-id = R, and rendezvous-Host = RNDZ.Then Host SND creates a table entry in its rendezvous table 💖
+-----------------------------------+
|HOST SND MSP _ _ _ |
| ------------->|_ _ _| |
| / ^ |_ _ _| <-|-------RENDEZVOUS
| / | |_ _ _| | TABLE
|(PROCESS) | |
|( S ) +-- SEND (from=S to=R; rend=RNDZ)
| \ |
| [DATA] |
+-----------------------------------+Host SND now sends an "OUT" message with S's data to Host RNDZ 📨✨
HOST SND HOST RNDZ
+------------+ +---------------------------+
| MSP| "OUT" + DATA |MSP _____ RENDEZVOUS |
| |--------------------|--> |_ _ _| TABLE |
| | from=S; to=R | \ |_ _ _| |
| | | \ |_ _ _| |
+------------+ | \ __ |
| \---------->| | DATA |
| |__|BUFFER |
| |
+---------------------------+Concurrently, process R at Host RCV executes a RECEIVE with from-port-id = S, to-port-id = R, and rendezvous-Host = RNDZ 🦋 Just like before, Host RCV creates a table entry in its rendezvous table and sends an "IN" message to Host RNDZ (see the following figure) 💅
(Don't panic about buffering in an intermediate Host yet 🙈 The time to panic is after you've read and understood the rest of our arguments 💀)
HOST RNDZ HOST RCV
+------------------------+ +-----------------------+
| MSP | | MSP |
| TABLE _____ | | _____ TABLE |
| +-|_ _ _| | "IN" | |_ _ _| |
| | |_ _ _|<-|----------|_ _ _|<-\ |RECEIVE
| | |_ _ _| | | |_ _ _| \ <--|(from=S
| | | | \ | to=R
| _V_ | | \ | rend=RNDZ)
| BUFFER | | | | (PROCESS) |
| |___| | | ( R ) |
+------------------------+ +-----------------------+Host RNDZ now notices that the "OUT" from Host SND and the "IN" from R at RCV match one another, so Host RNDZ takes three actions 👑
- Sends an "IN to Host SND (from-port-id = S, to-port-id = R, rendezvous-Host = RNDZ).
- Sends an "OUT" and the buffered data to Host RCV (from-port-id = S, to-port-id = R, rendezvous-Host =RNDZ)
- Clears the entry from its table.
HOST SND HOST RCV
+------------------+ +------------+ +-------------+
| | | TABLE | | |
| TABLE ___ | "IN" | ___ | "OUT" | ___ TABLE|
| |___| | | |___| | + DATA | |_ _| |
| |___|<---|--------|---|___|----|---------|->|_ _| |
| |___| | | |___| | | |_ _| |
| ( S ) | +------------+ | ( R )|
| | HOST RNDZ | |
+------------------+ +-------------+Host RCV gets the "OUT" and DATA, finds the matching entry in its table, gives the DATA to process R, and clears the entry from its table 🎀
Host SND gets an "IN" that matches an entry in its table and clears that entry 🌸 This message is a combined acknowledgement and go ahead, which can be passed along to process S ✨
The transmission is now complete 🥳💖
By both, one, or neither of the sender and receiver processes specifying a remote rendezvous Host, four important different kinds of transmissions can be made to happen 🌈 They're illustrated in the next four figures 🦋 In the figures, crossed or parallel dotted lines show rendezvous, and the site of the "crossed rendezvous" is the big difference between the types of transmission 🫶 Circles are processes and rectangles are rendezvous tables 💜
The figures also show "(IN)" and "(OUT)" messages being passed into the processes. The parentheses mean the "IN" and "OUT" are only CONCEPTUALLY passed in, and what actually happens is implementation dependent 🙈 The process might be awakened and given no further information if it blocked when issuing the SEND or RECEIVE 💤 It might be interrupted and passed some information, like the to-port-id from the IN or the from-port-id of the OUT 🧚 It might even get the complete IN or OUT message 📦
------ _________ ------
( ) | | ( )
( ) SEND | | RECEIVE ( )
( )------>|--+ +---|<--------( )
( ) | \/ | ( )
( ) (IN) | /\ | (OUT) ( )
( )<------|--+ +--|-------->( )
(______) |_________| +DATA (______)
|<------------- Host K ------------------>|
A Rendezvous at the Sender's Host ---- _______ ______ ----
( ) | | | | ( )
( ) SEND | | IN | | RECEIVE( )
( )------>|-+ +--|<------------|------|<-------( )
( ) | \/ | | | ( )
( ) (IN) | /\ | OUT+DATA | | (OUT) ( )
( )<------|-+ +--|------------>|------|------->( )
(____) |_______| |______| +DATA (____)
|<---- Host K ------>|<-- Network-->|<----- Host L ----->|
A Rendezvous at the Sender's Host ---- ______ _______ ----
( ) | | | | ( )
( ) SEND | | OUT+DATA | | RECEIVE( )
( )------>|------|------------->|-+ +--|<-------( )
( ) | | | \/ | ( )
( ) (IN) | | IN | /\ | (OUT) ( )
( )<------|------|<-------------|-+ +--|------->( )
( ) | | | | +DATA ( )
(____) |______| |______ | (____)
|<---- Host K ----->|<-- Network-->|<----- Host L ----->|
A Rendezvous at the Receiver's Host ---- ______ _______ ______ ----
( ) | | | | | | ( )
( ) SEND | | OUT+DATA | | IN | |RECEIVE( )
( )------>|------|--------->|-+ +--|<---------|------|<------( )
( ) | | | \/ | | | ( )
( ) (IN) | | IN | /\ |OUT+DATA | | (OUT) ( )
( )<------|------|<---------|-+ +--|--------->|------|------>( )
( ) | | | | | | +DATA ( )
(____) |______| |______ | |______| (____)
|<---- Host K ----->|<--Net-->|<-Host->|<--Net-->|<----- Host L ----->|
M
A Rendezvous at an Intermediate HostISSUES 🔥
Timeouts.
Ohhh, timeouts are a SUPER sticky topic 😭 A coherent system of timeouts makes everything simpler and gets rid of races ✨ But lots of Hosts are unwilling or unable to use timeouts, especially timeouts with a specified duration 💀
Without these timeouts, there's probably a need for a negative acknowledgment that goes back to the source of an IN or OUT when one times out 🙃 The catch is that this brings back races 🥲
A negative acknowledgment (which we'll call a FLUSH message) could be used by a Host to mean:
- I have no room in my table
- I have no more available buffer space, or
- I no longer wish to retain the table entry/buffer.
Generally, we think a Host should be allowed to throw away an IN or OUT+data whenever it's no longer convenient for the Host to hold onto the messages 🗑️ This can happen right when a message arrives. For example, if the Host doesn't want to buffer traffic it doesn't have a user buffer for, that's a valid reason 💅 Instead of timeouts, any time a process issues a SEND or RECEIVE, it can take it back by issuing the matching RECEIVE or SEND 🔄
Blocking the Process After a Send or Receive.
This is left up to the implementation 🧩 Generally, we don't think it's a good idea to block the process after a SEND, since it may want to do another to another port or even do a RECEIVE 🙅♀️ We also don't see anything inherently wrong with a process doing two or more SENDs to the same port, as long as the communicating processes know what they're doing 💖 Of course, some communicating processes will prohibit several simultaneous messages in transit between the same ports. The TELNETs, for example, may well prohibit this 🙅♀️ But for reasons like increasing bandwidth, etc., two processes may really want several simultaneous messages 🚀 In that case, we think it's up to the processes to worry about the sequencing of messages 🎀 If you want your processes to handle message sequencing, we refer you to the method used in the IMP/Very Distant Host interface, which is documented in Appendix F of BBN Report 1822 📚
Message Buffering
A few points are worth mentioning about message buffering 🧺 First, most OUTs will probably come with data 📦 So, in general, since the receiver process may be swapped out, the receiver Host monitor must be ready to buffer some data somewhere 😬 To minimize how much buffering is needed, the monitor could refuse further traffic from the IMP until the earlier traffic from the IMP has been written to a disk or drum 💾 Or the monitor could keep a small number of buffers in the monitor area of memory, fill them as traffic comes from the IMP, and swap them with buffers claimed earlier by the receiver processes as those processes are swapped in 🔁 Note that the buffers may be shorter than the maximum subnet message size if the RECEIVEs never specify a longer message length. Of course, this can be enforced 📏 Finally, the message size, receive-port-id, etc. are available in the first 144 bits that come in from the IMP 👀 It might be useful to read those before deciding which buffer to read the rest of the message into 🧠
Positive Acknowledgments
The system has a certain form of acknowledgment built in 🫶 The information is always available about when the receiving process has done a RECEIVE 👑 The sending Host is assured of receiving an "IN" when the receive call is issued 💌
Further forms of acknowledgment and validation can be implemented at the first user level, and advanced protocols will probably develop a library of such routines 📚💜
MESSAGE HEADER 💖
okay so this section is all about the exact shape of Host to Host messages, plus what each host should do when one shows up. it's giving very precise packing energy 🎀
Each message begins with a 144 bit header containing the following fields:
- HOST-TO-IMP leader (32 bits) as specified in BBN Reports 1822
- to port ID (i.e., the id of the port receiving the message) (24 bits)
- MSG TYPE (8 bits) IN, OUT, FLUSH, etc.
- from port ID (i.e., id or the port sending the message) (24 bits)
- initiating Host's table position (8 bits) see below.
- HOST "sourcing" this message (8 bits) see below.
- RENDEZVOUS HOST (8 bits)
- bit count of data (16 bits)
The header is laid out so that no data item crosses a word boundary on machines with 16, 32, and 36-bit words, unless the item is bigger than the word itself. The diagrams below show how the bytes sit inside words for each of those three sizes. The 36-bit Hosts get bytes 4 and 13 (counting from 0) as unused. The 2 and 3-byte items don't cross word boundaries, except the port IDs on the 16 bit machines. Packing and unpacking this neatly was a big deal for convenience, and especially because Hosts may want to check the header at interrupt level to figure out where the rest of the message should go 🧚
+-------------+-------------+
0 | HOST/IMP | DESTINATION |
| FLAGS | |
+-------------+-------------+
1 | LINK | /////////// |
| | /////////// |
+-------------+-------------+
2 | /////////// | |
| /////////// | |
+-------------+ |
3 | TO PORT ID |
| |
+-------------+-------------+
4 | MESSAGE | |
| TYPE | |
+-------------+ |
5 | FROM PORT ID |
| |
+-------------+-------------+
6 | TABLE | /////////// |
| POSITION | /////////// |
+-------------+-------------+
7 | SOURCE | RENDEZVOUS |
| HOST | HOST |
+-------------+-------------+
8 | BIT COUNT |
| |
+-------------+-------------+
| |
9 | DATA |
// //
| |
+-------------+-------------+
16-bit Host Format
+-------------+
| | ////////// = unused
| | //////////
+-------------+
8 bits
0 8 16 24 32 36
+-------------+-------------+-------------+-------------+------+
0 | HOST/IMP | FOREIGN | LINK | ////////////////// |
| FLAGS | HOST | | ////////////////// |
+------+------+-------------+-------------+-------+-----+------+
1 | //// | TO PORT ID | MESSAGE |
| //// | | TYPE |
+------+------+-------------+-------------+-------------+------+
2 | FROM PORT ID | TABLE | //// |
| | POSITION | //// |
+------+-------------+-------------+------+-------------+------+
3 | //// | SOURCE | RENDEZVOUS | BIT COUNT |
| //// | HOST | HOST | |
+------+-------------+-------------+---------------------------+
| |
4 | |
// DATA //
| |
| |
+-------------+-------------+-------------+-------------+------+
36-bit Host Format
+-------------+-------------+-------------+-------------+
0 | HOST/IMP | FOREIGN | LINK | /////////// |
| FLAGS | HOST | | /////////// |
+-------------+-------------+-------------+-------------+
1 | /////////// | TO PORT ID |
| | |
+-------------+-------------+-------------+-------------+
2 | MESSAGE | FROM PORT ID |
| TYPE | |
+-------------+-------------+-------------+-------------+
3 | TABLE | /////////// | SOURCE | RENDEZVOUS |
| POSITION | /////////// | HOST | HOST |
+-------------+-------------+-------------+-------------+
| BIT COUNT | |
| | |
+-------------+-------------+ |
| |
// DATA //
| |
+-------------+-------------+-------------+-------------+
32-bit Host FormatThe fields inside the Host/IMP leader will already be familiar to NCP programmers, but two things about them are worth a mention 👑 First, the destination field starts out holding the number of the rendezvous Host. Once the rendezvous happens at an intermediate site, the destination field holds the source of the message that the rendezvous was done with. Second, the link field for the MSP experiment can only hold link numbers 192-195. We haven't yet worked out a sensible way to split those four links among all the messages that might go over the MSP. One idea is to cycle over the links to boost the bandwidth of the "pipe" between any two Hosts. Until this gets more thought, we suggest that each Host at a site uses one (unique) link for all of its communication 💅
The message types we need to represent in the message type field are few for now. We suggest message type 2 for SEND or OUT messages, and message type 3 for RECEIVE or IN messages. Message type 4 is the FLUSH message, if FLUSH is used 🦋
The rendezvous Host field doesn't need much explaining. The only extra detail is that the field is unnecessary once the rendezvous has happened, so it could be reused for something else 🌸
The bit count is the number of data bits in an OUT message, or the size of the input buffer (not counting the header) in an IN message. So when the sender process gets an IN message, it can read the bit count to see how much of the OUT data the receiver process accepted, and then resend the rest if it wants to. After the rendezvous, we recommend sending all of the message data to the source of the IN message, even if the OUT bit count was bigger than the IN bit count. That way, at the receiving Host, the monitor has a few options (if it wants any of them): it can throw the message away for being too long, it can pass the receiver process the number of bits that the receiver process did an IN for and discard the rest, or it can queue the rest of the bits and somehow tell the receiver process that more bits are waiting for it to ask for ✨
The to- and from-port-id fields are 24-bit numbers. This size was picked to help the TIPs 🎀 The first eight bits of a port ID should be the number of the Host where that port ID was created. Heads up: that isn't necessarily the Host where the port is being used. This matters because rendezvous can happen at intermediate sites, and ports can move from site to site. We suggest that every port ID whose first eight bits are all zero gets reserved for network-wide use. In particular, a port ID with all 24 bits zero means "ANY". That gives us these options:
RECEIVE from ANY to SPECIFIC
RECEIVE from SPECIFIC to SPECIFIC
SEND from SPECIFIC to ANY
and SEND from SPECIFIC to SPECIFICWe'll go over examples of these options below 🧚
The other two options, (RECEIVE to ANY) and (SEND from ANY), we think are kind of useless, but we wouldn't ban them. We believe that when no rendezvous Host is explicitly specified, using an ANY port ID in the user's system call should set the default rendezvous site like this:
RECEIVE from ANY--rendezvous in receiver
RECEIVE from SPECIFIC--rendezvous in sender
SEND to ANY--rendezvous in sender
SEND to SPECIFIC--rendezvous in senderThe less significant 16 bits of the ID can be used however a Host wants. For example, eight bits could be a process ID, and the other eight bits could be a channel specification within that process. We suggest that each Host reserves the port IDs whose middle eight bits are all zero for special uses as well-known ports 🌈
The table position field is there to help avoid expensive table searches at interrupt level. Hosts sending INs and OUTs put the rendezvous table position of the matching SEND or RECEIVE into the table position field. At an intermediate Host rendezvous, the table position fields in the matching IN and OUT get swapped, so that when the messages reach the far end, the matching SEND and RECEIVE can be found quickly. The MSP has to do the swap at the rendezvous. MSPs don't need to fill in the table position field when they first transmit an IN or OUT, in which case the value that arrives in an IN or OUT will be meaningless. So the general algorithm is: check the table position given in this field, and if that fails, search the whole table 💜
The source field is filled in on INs and OUTs by the MSP that first sends them. At the rendezvous, the source of each message is kept in the message that gets forwarded to the final Host. When an IN or OUT reaches a process, the process can use the source information to update its idea of the rendezvous Host (for example, when the destination Host and the rendezvous Host are different) 🫶
EXAMPLES 🧚
The typical example.
We picture communication normally happening with specifications to and from ports, with the rendezvous at the sender. For example, the TIP would probably send to other Hosts this way, and it would definitely receive from other Hosts until the TIP asks for it. In this "normal" method, a monitor could even look at the bit count in the arriving IN message, use that as an allocation, and then simulate an OUT message of exactly the right length 💖
The logging example
Let's look at an example of SEND to SPECIFIC and RECEIVE from ANY, with the rendezvous at the receiver. This could be used by a logging receiver process with a well-known to-port, like a measurements program that gets statistics sent from many processes all over the net 📊🔥
The program library example 💖
Okay bestie, picture this. There's a library routine on a time-sharing system that any process in the network can use 📚. The library process keeps a RECEIVE from ANY pending at a well-known port 🔔. Eventually some process sends a message to that port. The message has the data to be processed, a port to send the answer back on, and the money 💸. The library process takes some of the money and sends it to the well-known port of the accounting process, which also has a RECEIVE from ANY pending 🧾. Then the library processes the data and sends the answer back to the requester with a SEND to SPECIFIC. That message rendezvouses at the destination, where a RECEIVE from SPECIFIC is already waiting 🎯. And of course, any change the requesting process has coming gets sent back in that same message 🪙✨
A comment 🦋
Okay so, as you can see from these examples, rendezvousing at an intermediate Host will rarely happen 🙈. The big benefit only shows up when you want to move a port (see reference 4 for more on that). We'd love for all Hosts to provide some (meager) buffering for this, but it's not required 🫶. It shouldn't be too painful to add a little, especially since a Host can throw away any message it can't handle 🗑️
(THIS PAGE WILL BE REPLACED WITH A BETTER DESCRIPTION OF TELNET UNDER MSP IN A FEW DAYS--DCW) 📝
TELNET 🖥️
Let's imagine a pair of Telnet programs that keep two bidirectional communication paths open, one for data and one for control 💜. For convenience, let's also assume the port IDs are laid out like this:
If the WRITE-CONTROL-ID is N, then --
READ-CONTROL-ID=N+1,
WRITE-DATA=N+2,
READ-DATA=N+3.The server Telnet starts out sitting with a READ-FROM-ANY pending 😴. Then the user Telnet issues a SEND-TO-SPECIFIC, with the data field holding the PORT-ID of the SERVER's WRITE-CONTROL-ID. That message gets sent from the user-Telnet's WRITE-CONTROL-ID 📨
So the user Telnet specifies all the port IDs, which means they only need to remember one number and can work out the rest 🧮. Uniqueness is kept because the port IDs the user Telnet supplies contain their Host ID and other info, which makes each ID unique to them 🔐. Once those communication paths are set up, the two processes can swap data and control info using the established Telnet protocols 🎀
THE INFORMATION OPERATOR 🧚
The Message Switching Protocol itself doesn't put any fixed requirements on how port ID's get used, and figuring out who's who is kind of separate from how the communication actually happens 🤷♀️. Still, it's a big part of the whole interprocess communication story, so we're specifying a facility for process identification here: the information operator 🕵️♀️
One goal of a process identification scheme is to let processes pick their own identifiers that can be guaranteed unique and that mean something to the user 🌸. Port ID's can't be made big enough to do that, because efficiency gets in the way 😤. Efficiency aside, it'd be ideal to let processes use character strings of any length to identify themselves ✨. Uniqueness is easy to get then, for example if users put their names in the identification string 🙋♀️. The rest of the name can carry some meaning tied to what it's used for, which is super convenient for users 💅
One solution is to agree that the symbolic identifiers only get used during an initial phase of communication, not in every message 🦋. So processes identify each other up front with symbolic identifiers, and at the same time they swap local port identifiers, which get used for every message after that 💫
Here's how it works: there's a process at each of a number of Hosts (for example, all server Hosts) called the "information operator" 🧚. Its job is to link symbolic identification strings to port ID's 🔗. A process can identify itself and/or a foreign process to the information operator, and it can ask for the port ID of a foreign process 📮. The symbolic identification strings are picked by the processes and are long enough to hold meaningful info, like LOGGER or MURPHY-TESTPROG 🎀
Talking to the information operator, whether the caller is local or remote, happens through the regular MSP functions 📞. The information operator always has a RECEIVE ANY outstanding on a well-known port 👀. This could be the only well-known port that exists 🌟. A message received on this port has these parameters:
- String identifying the foreign process with which communication is desired.
- String identifying the calling process.
- Calling process' port number.
- A delay specification.
The format of these parameters is shown in Fig. 4 🖼️. Sometimes one or more of the arguments will be null 🫥. After getting a message, the information operator will, in some cases, do a SEND SPECIFIC to the calling process' port number, giving back the info asked for or a notice of failure 💌
The following two cases seem to cover everything the information operator does 💯. They line up with the SEND/RECEIVE SPECIFIC ANY cases of the MSP 🧩
- Two processes that each know the specific identity of the other want to communicate 👯. Each one does a SEND SPECIFIC to the information operator with parameters 1-2, and the default delay spec here is WAIT ⏳. When the information operator gets the second of these and sees that there's a match, it sends each process the port ID of the other, then deletes both strings and both port ID's from its tables 🗑️. The two processes, each of which did a RECEIVE SPECIFIC in anticipation of the foreign port number, can now talk using just the port numbers and the basic MSP functions 🥰
- A process is set up to offer some kind of general service or information, and its name and protocol get advertised 📣. This process plans to keep a SEND or RECEIVE ANY outstanding for the first (and maybe only) message transaction, like the library process we talked about earlier 📚. Most of these processes start out as receivers, but there might be a few cases where a SEND gets left outstanding, and a forcing process can come along and grab the info 🏃♀️. Either way, the service process does a SEND SPECIFIC to the information operator with its local symbolic ID and local port ID 🪪. The foreign symbolic ID is null, and the default delay spec is NO-WAIT 🙅♀️. So it looks like this:
INFO ( -, local ID, local port)The information operator puts this info in its tables and returns nothing to the caller ✍️. The caller then goes on to do its SEND/RECEIVE ANY to wait for business 👂. When another process wants to use the advertised service, it asks the logger for the port ID of the service process, like this:
INFO (service ID, -, local port)The local symbolic ID doesn't need to be specified, and the default delay spec is NO-WAIT ⚡. The information operator SENDs the port ID of the service process to the caller's local port and keeps the table entry for future callers 🗂️. Only the service process can ask for the entry to be deleted 🔒. If the service ID wasn't known to the information operator when this call came in, it immediately returns a failure indication, which is zero 🙅♀️❌
Communicating processes would normally use the information operator local to one of them or the other, and just like the rendezvous Host in the MSP, that gets agreed on in advance 🤝. Service processes would normally use the information operator at their local site, and user processes would call the information operator at the site where the service process is expected to be available 📍. There's no restriction on using an information operator at some other site, of course 🌍. Some small and/or lazy servers could even use a different Host for their service process ID's 😌. It's totally fine for two or more information operators to have entries for the same service process 👯♀️. In fact, that might be really desirable for special types of service processes that exist in only one place on the net but move around from time to time 🛸
Processes specify their own local port numbers, and each system has to provide some way to help user processes do that 🛠️. In TENEX, for example, you'd probably use the job number concatenated with another number assigned within the job 🔢. The information operator can't supply port numbers, because it runs on a different Host than one or both of the communicants and can't know what's a unique number for that Host 🙅♀️. In some cases, processes ask the "unique number process" (described below) for their local port ID, and then make it known through the information operator 📢
In actual practice, a few exceptions get made to the rule that the information operator is the only "well-known" port in the world 🌈. These exceptions are processes common to many Hosts, like LOGGER, or processes in especially frequent use ⭐. For those, unique port numbers get assigned by administrative fiat and then recorded and published to all users 📜
The symbolic identification strings are specified to be from 1 to 39 (an arbitrary maximum) ASCII characters, terminated by a null (a byte of all zeroes) 💅. The characters are 7-bit ASCII in 8-bit bytes, with the high order bit set to zero 🔟. A null string (first byte is null) is used where no argument is required 🫧
Format of Information Operator Messages 📦
To Information Operator: A stream of 8-bit bytes.
+------+--//---+------+------+--//---+------+------+-------+-------+
|char 0| 1// n | null |char 0| 1// n | null | port | number| delay |
| | // | | | // | | | |spec |
+------+--//---+------+------+--//---+------+------+-------+-------+
\ /\ /\ /\ /
\_________________/ \___________________/ \___________/ \____/
PARAMETER 1 PARAMETER 2 PARAMETER 3 PARAMETER
4Parameters given:
- String identifying the foreign process with which communication is desired. (1 to 39 characters, or null)
- String identifying the calling process. (1 to 39 characters, or null)
- Calling process' port number.
- Delay specification:
0=default
1=wait for match
2=don't wait for matchFrom Information Operator: 3 8-bit bytes.
+--------|-------|-------+
| byte 0 | 1 | 2 |
+--------|-------|-------+Port number (24 bits) of requested foreign port if successful, 0 if unsuccessful. 🎉
UNIQUE PORT NUMBERS 🦋
okay so unique port numbers are literally essential to how the MSP works 💖 Picture two processes that want message rendezvous at an intermediate site. They have to pick to- and from-ports that no other process using message rendezvous at that same site is using, or messages could get delivered to the wrong place 😭 We hinted at a way to handle this earlier, and it's to chop up the 24-bit port number space into disjoint segments and hand one segment to each Host in the network. That Host then distributes its segment whenever it's asked to "create" a unique port id ✨
So each 24-bit number has two major parts. The first 8 bits are the number of the Host doing the "creating," and the next 16 bits can be used however that creating Host wants 🎀 That gives every Host 2^16 port numbers to hand out, and each Host is responsible for distributing its own segment in a unique way. We recommend that port numbers with the middle 8 bits equal to zero get reserved for well-known ports in the creating Host's system 🌸 We also already recommended, in an earlier section, that port numbers with the first 8 bits equal to zero be reserved for network-wide use. And the port number with all 24 bits equal to zero is the one used to mean ANY 🧚
Now here's the catch 🙈 Each Host only has 2-16- port numbers to hand out, so in general, port numbers can't be held and used by processes for long periods of time, like weeks or months. What usually happens is that a Host implicitly "takes back" every port number it has distributed each time its system goes down, and then redistributes them as needed once it comes back up. So port numbers won't generally stay unique across a going-down of the creating Host. That said, a given Host might choose to hand the same port numbers to a bunch of standard processes (like the FORTRAN compiler) every time it comes up, so port numbers registered with an information operator will often stay constant across system ups and downs 💜
Even with all that, a lot of people still want long-term unique port numbers, and honestly, I get it 🥺 Some folks think going through the information operator is way too much like making a connection. They insist their processes should be able to talk through ports whose identifiers stay constant for long stretches of time. So it would be nice to have a long-term unique number service at one or two places in the network. We'll call the process providing this service the Unique Number Process 👑
The Unique Number Process would be assigned one segment of the unique port number space, like all the port numbers whose first 8 bits are equal to 377-8 🌈 It would keep a SEND-to-ANY pending from a well-known port with local rendezvous specified. When a process wants a unique number it can count on not being used for all time (or until the number is given back), it sends a RECEIVE-from-SPECIFIC that names the well-known port of the Unique Number Process and rendezvous at that process's Host. The Unique Number Process's pending SEND-to-ANY would then contain a unique number ⭐ The Unique Number Process would also keep a RECEIVE-from-ANY always pending at another well-known port with local rendezvous specified, and that's where it receives the unique numbers that processes are giving back 🦋
It would maintain a bit table 2-16- bits long that shows the state of each of its unique numbers (free or in use). That table would live in some long-term storage medium, like the file system 💾 It might also keep some info about each process it has given a unique number to, so that when the supply runs low, processes can be asked to return them 💅
It's already been mentioned that some of the process ID's registered along with their symbolic names at the information operator might be long-term unique numbers from the Unique Number Process 🎀 But honestly, there's no real reason (other than running out of storage space) that you couldn't also register arbitrary port numbers with their symbolic identifiers at an information operator. That's in addition to the port number you get primary access through, which is the process ID from the previous section 🌸 For example, instead of registering the name BBN-FORTRAN with one port number, you could register port numbers with the symbolic identifiers BBN-FORTRAN-CONTROL-TELETYPE, BBN-FORTRAN-INPUT-FILE, BBN-FORTRAN-LISTING-FILE, and BBN-FORTRAN-BINARY-OUTPUT-FILE 🧚 This might be a bit at odds with standard operating system practice, but it fits the philosophy of reference 4 that communication happens with ports and not processes 💖
Okay, now we need to talk about something that's been ignored up to this point and was only hinted at in reference 4: port protection 😤 We haven't given this a ton of thought, but one mechanism seems pretty straightforward. The heart of it is a process at each Host that we'll call (alliteratively) the Port Protection Process, or PPP ✨ The PPP keeps a list of all processes that exist at the Host and, for each process, the numbers of all the ports it has "legally" obtained 🦋
Every time a process does a SEND or RECEIVE, the monitor checks with the PPP to see whether the process has specified port numbers it has the right to use, meaning the ones it legally obtained 🫶 The PPP also has some RECEIVEs always pending at well-known ports. When one process wants to pass a port to another process, the first one sends a message to the PPP. That message specifies the number of the port to be sent, the Host number where the second process lives, a port where the second process is expecting to receive the port, and so on. The PPP checks its tables to see whether the first process actually has the port it wants to send. If it does, the PPP sends a message to the PPP at the destination site. That message contains the number of the port being transferred and the RECEIVE port for the destination process 💌
Then the destination PPP checks its table to see whether the process has that RECEIVE port. If it does, the PPP passes the new port to the process and updates its tables to show the process now has the new port 🌈 Messages to a PPP can optionally specify that a copy of a port be sent, that a port be deleted, and so on ⭐ The PPPs would probably have some built-in legal ports for each process, especially the ports that processes use to talk to the PPP 🍓 The exact specification still needs to be developed, but that shouldn't be too hard (see (3),(6), and (7) in reference 4) 💅 The main difficulty we see is checking the PPP's tables efficiently. The monitor has to do that for every single RECEIVE or SEND, and it has to happen without entirely replacing the monitor's current protection system 😭
FLOW CHART 💅
okay, this part is the flow chart for most of the MSP 🔥 It's a lot, but it's really just a few patterns repeated over and over. There are two kinds of things happening. One is the calls made by local processes, called SEND and RECEIVE. The other is the messages coming in over the NET, called IN and OUT 🦋 On top of that, there's a split between calls (or messages) with a local rendezvous and those with a foreign rendezvous Host 💜 The code is pretty similar across all of these, so technically you don't need to make the distinction, but it's included to keep things clear ✨
It's assumed that the MSP has table provisions for the following items:
- source of message
- rendezvous Host
- FROM-PORT-ID
- TO-PORT-ID
- table position
- type of message
- data size and location
- data about the user process
Here's the procedure, copied exactly so you can see the structure 🌸
User does a SEND or RECEIVE
A. Rendezvous is at a foreign host
1. Store the appropriate table data
2. Send a message to the rendezvous host
a. SEND: OUT + DATA
b. RECEIVE: IN
B. Rendezvous is local - look for entry in table
1. Entry NOT found: create entry with appropriate data
2. A matching entry exists in table:
a. RECEIVE: give user the data
b. Send a message to the other host (as specified by the source
field of the original msg)
1)SEND: OUT+DATA
2)RECEIVE: IN
c. Alert user to the fact that transaction is complete
d. Clear table entry
An IN is received over the NET-search table for matching entry.
A. No matching entry create an entry with appropriate data.
B. A match exists
1. Entry was cause by a local SEND
a. Send "OUT _ DATA" to source of IN
b. Inform user of transaction
c. Clear table entry
2. Entry was caused by an OUT received over net-acting as third
host.
a. Send IN to site that created table entry
b. Send OUT + DATA (previously buffered) to site sending the IN
c. Clear table entry
An OUT + DATA is received over the NET -search table for matching
entry
A. No match is found
1. buffer data
2. create appropriate table information
B. A match is found
1. Table entry was caused by locally executed RECEIVE
a. give data to the user and alert him to its existence.
b. send a matching "IN" to the source of the "OUT"
c. remove entry from table
2. Table entry was caused by the receipt of an "IN" over the NET,
thus we are acting as a third party host
a. send the "OUT + DATA" to the host stored in the table
b. send an "IN" to the host from which the "OUT" had just
arrived.MSP VARIATIONS ✨
okay so, it may be of interest to you, bestie 🫶, to know about some of the other MSPs we looked at before we landed on the one in this note 🧚
The simplest one we looked at is an MSP where all the rendezvous happen at the destination Host 🎀 The sender process sends an OUT-message plus the data to the destination Host. The receiver process does an IN, which stays at the receiver's Host. The OUT and RECEIVE rendezvous, and the data gets passed to the receiver process. The transmission is now complete, except that in some versions of this MSP an acknowledgement is sent to the sender process. This one has a couple of disadvantages 😭 In the simplest version, the RECEIVE had to be waiting when the OUT+data arrived, otherwise the OUT data were thrown away. That puts way too tight a constraint on the timing of the SEND and RECEIVE, especially since the sender and receiver processes can be a continent apart 🌍 If the IN is allowed to arrive first and has to be held until it's matched by a RECEIVE, then the monitor has to buffer an indeterminate amount of data in every case, including the normal one 💀 Also, basing everything on rendezvous at the destination makes moving a port difficult 🙈
The next simplest MSP we looked at was the IPC of reference 4 🌸 It works the opposite of the one above, because it's based on almost all rendezvous happening at the source Host, with two special messages to handle the relatively uncommon cases when a rendezvous has to happen at the destination or at an intermediate Host. This system, plus its advantages and disadvantages, is discussed at very great length in the reference, so go check it out if you're curious 📚
A third variation, suggested by Crowther, is the same as the present MSP in that the OUT and IN rendezvous at a process-specified rendezvous Host, and the OUT is sent to the source of the IN and the IN is sent to the source of the OUT. The difference is that the data is not sent along with the OUT. Instead, when the OUT finally reaches the source of the IN, another message is sent from the receiver Host to the source Host asking for the data to be sent. The data is finally transmitted to the destination in response to this data request message 📨 Our main objection to this system is its lack of symmetry 😤 But we do recognize that it doesn't require any Host to buffer data for which a process hasn't set up an input buffer, and maybe for that reason it's a better system than the MSP we're presenting 🦋
In the last MSP variation we looked at, the difference between SEND or RECEIVE and OUT or IN was dropped 💅 In this case only one message is used, which we'll call TRANSFER. When a process executes a TRANSFER, it can specify an input buffer, an output buffer, both, or neither. Two processes that want to communicate both execute TRANSFERs specifying the same to and from port ids and the same rendezvous Host. The TRANSFERs result in TRANSFER-messages plus data in the case that an output buffer was specified, and these rendezvous at the rendezvous Host. When the rendezvous occurs, the TRANSFER-messages plus their data cross, and each one is sent to the source of the other. The system lets processes skip knowing whether they must do a SEND or a RECEIVE, and it's (perhaps) a nice generalization of the MSP presented in this note ✨ For example, two processes can exchange data using this system, or two processes can kind of interrupt each other by sending dataless TRANSFERs 👀 This variation is a development of a suggestion by Steve Crocker. Its disadvantages are:
- unintentional matches are more likely to occur,
- rendezvous selection site is more complex, and
- it's hard to think about 💀
APPENDIX 🎀
A system for Interprocess Communication in a Resource Sharing Computer Network. Communications of the ACM, April, 1972. Permission to reprint this paper was granted by permission of the Association for Computing Machinery. [Omitted in republished version of RFC 333.]
N.B. The ideas of section 4 of the following paper are in no way critical to the ideas developed in section 3--DCW. 💖
[ This RFC was put into machine readable form for entry ] [ into the online RFC archives by Via Genie 3/00 ] 🧚✨
📦 where this page comes from
- ietf: rfc333 1972-05
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms