faqs.org - Internet FAQ Archives

RFC 333 - Proposed experiment with a Message Switching Protocol


Or Display the document by number




Network Working Group                                       Bob Bressler
Request for Comments: 333                           MIT/Dynamic Modeling
NIC # 9926                                                    Dan Murphy
Category: C9 (experimentation)                                 BBN/TENEX
Obsoletes: 62                                                Dave Walden
Updates: none                                                    BBN/IMP
                                                             15 May 1972

        A PROPOSED EXPERIMENT WITH A MESSAGE SWITCHING PROTOCOL

CONTENTS

   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 ...................................................... 26

INTRODUCTION

   A message switching protocol (MSP) is a system whose function is to
   switch messages among its ports.

   For example, there is an implementation of an MSP in each Interface
   Message Processor.  We believe that the effective utilization of
   communications networks by computer operating systems will require a
   better understanding of MSPs.  In particular, we feel that Network
   Control Programs (NCPs), as they have been implemented on the ARPA
   Computer Network (ARPANET), do not adequately emphasize the
   communications aspects of networking -- i.e., they reflect a certain
   reluctance on the part of systems people to move away from what we
   term "the stream orientation".  We propose, as an aside the network
   development using the current NCPs, to rethink the design of NCP-
   level software beginning with a consideration of MSPs.

   The thrust of this note is to sketch how one would organize the
   lowest level host-host protocol in the ARPANET around MSPs and how
   this organization would affect the implementation of host software.

SOME BACKGROUND

   Over the past several weeks there has been considerable informal
   discussion about the possibility of implementing, on an experimental
   basis, in several of the ARPA Network Host Computers, NCPs which
   follow a protocol based on the concept of message switching rather
   than the concept of line switching (see the parenthetical sentence in
   the first paragraph of page 6 of NIC document 8246, Host/Host
   Protocol for the ARPA Network).  Party to this discussion have been
   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).

   Several interesting points and conclusions have been made during this
   discussion:

      1. Bressler has implemented a message switched interprocess
         communication system for the Dynamic Modeling PDP-10 and has
         extended it so it could be used for interprocess communication
         between processes in the Dynamic Modeling PDP-10 and the AI
         PDP-10.  He reports that it is something like an order of
         magnitude smaller than his NCP.

      2. Murphy has noted that a Host/Host protocol based on message
         switching could be implemented experimentally and run in
         parallel with the real Host/Host protocol using some of the
         links set aside for experimentation.  Further, Murphy has noted
         that if this experimental message switching protocol were
         implemented in TENEX, a number of (TENEX) sites could easily
         participate in the experiment.

      3. It is the consensus of the discussants that Bressler should
         take a crack at specifying a message switching protocol* and
         that if this specification looked relatively easy to implement,
         a serious attempt should be made by Murphy and Bressler to find
         the resources to implement the experimental protocol on the two
         BBN TENEX and the MIT Dynamic Modeling and AI machines.

      4. MSP was chosen as the acronym for Message Switching Protocol,
         and links 192-195 were reserved for use in an MSP experiment.

   -------------
   *This note fulfills any obligation Bressler may have incurred to
   produce an MSP specification.

   We solicit comments and suggestions from the Network Working Group
   with regard to this experiment.  However, although we will very much
   appreciate comments and suggestions, because this is a limited
   experiment and not an attempt to specify a protocol to supersede the
   present Host/Host protocol for the ARPA Network, we may arbitrarily
   reject suggestions.

REFERENCES

   Familiarly with the following references will be helpful to the
   reading of the rest of this note.

      1) NIC document 8246, HOST/HOST PROTOCOL FOR THE ARPA NETWORK

      2) NIC document 9348 on the Telnet Protocol

      3) NIC document 7101, OFFICIAL INITIAL CONNECTION PROTOCOL,
         DOCUMENT # 2

      4) a system of interprocess communication in a resource sharing
         computer network, CACM, April, 1972.

   Reference 4 is a revision of RFC 62.  We strongly suggest the reader
   be familiar with reference 4 before he attempts to read the present
   RFC; a reprint of reference 4 is attached as an appendix.

MSP SPECIFICATION

   Our MSP is essentially a generalization of the interprocess
   communication system outlined in Section 3 of the fourth reference.
   (Henceforth, if we are required to mention the interprocess
   communication system presented in Section 3 of reference 4, we shall
   call it "the IPC".)  For two processes to communicate using the MSP,
   the process desiring to send must in some sense execute a SEND and
   the process desiring to receive must in some sense execute a RECEIVE.
   The SEND and RECEIVE, in effect, rendezvous somewhere and
   transmission is allowed to take place.  With the RECEIVE are
   specified (among other things) a FROM-TO-PORT-ID, a TO-PORT-ID, and a
   RENDEZVOUS HOST.  With SEND are specified a from-port-id, a to-port-
   id, a rendezvous Host, and (possibly) some data to be transmitted.
   Using SEND and RECEIVE, sending a message from a SENDER PROCESS to a
   RECEIVER PROCESS takes place as follows.  The sender process executes
   a SEND which causes an OUT-MESSAGE plus the specified data to be
   transmitted to the Host specified as the rendezvous Host in the SEND.
   Concurrently (although not necessarily simultaneously)the receiver
   process executes a RECEIVE which causes an IN-MESSAGE to be sent to
   the Host specified as the rendezvous Host in the RECEIVE.  At the
   rendezvous Host, OUT-messages and IN-messages are entered in a table
   called the RENDEZVOUS TABLE.  When an OUT-message and an IN-message
   are detected with matching to-port-id, from-port-id, and rendezvous
   Host, three things are done:  1)  the OUT-message plus the data is
   forwarded to the Host which was the source of the IN-message, 2)  the
   IN-message is forwarded to the Host which was the source of the OUT-
   message, and 3)  the IN-message and OUT-message plus the data are
   deleted from the rendezvous table in the rendezvous Host.

   The process is greatly simplified if the rendezvous Host is also
   either the send Host or receive Host.  Specific algorithms
   enumerating these sequences appear later in this note.

   To clarify the basic concepts, let us look at a case involving three
   Hosts, to which we shall give the names SND, RCV, and RNDZ.  At Host
   SND, process S is doing a send, and at Host RCV, process R is doing a
   receive.  Both 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.

Host SND then 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.  As above,
   Host RCV creates a table entry in its rendezvous table and sends an
   "IN" message to Host RNDZ (see following figure).

   (Don't panic now about buffering in an intermediate Host.  The time
   to panic is afer 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 and thus Host RNDZ takes three actions:

      1. Sends an "IN to Host SND (from-port-id = S, to-port-id = R,
         rendezvous-Host = RNDZ).

      2. Sends an "OUT" and the buffered data to Host RCV (from-port-id
         = S, to-port-id = R, rendezvous-Host =RNDZ)

      3. 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 and finds the matching entry in its
   table.  It gives the DATA to process R and clears the entry from its
   table.

   Host SND gets an "IN" which matches an entry in his table and clears
   that entry.  This message serves as 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 take place.  These are illustrated in
   the following four figures.  In the figures crossed or parallel
   dotted lines are used to indicate rendezvous.  The site of the
   "crossed rendezvous" is the important difference between types of
   transmission illustrated in figures.  Circles indicate processes.
   Rectangles are rendezvous tables.

   The figures also show "(IN)" and "(OUT)" messages being passed into
   the processes.  The parentheses are used to indicate that the "IN"
   and "OUT" are only CONCEPTUALLY passed into the processes.  What
   actually happens is implementation dependent.  The process might be
   awakened and be given no further information if it blocked when
   issuing the SEND or RECEIVE.  The process might be interrupted and
   passed some information such as the to-port-id from the IN or the
   from-port-id of the OUT.  The process might actually be passed 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 Host

ISSUES

Timeouts.

   The issue of timeouts is a very sticky one.  A coherent system of
   timeouts simplifies everything and does away with races.  However,
   many Hosts are unwilling or unable to use timeouts, especially
   timeouts whose duration is specified.

   Without these timeouts there is probably a need for a negative
   acknowledgment which goes back to the source of an IN or OUT when one
   is timed out.  However, this now leads to races.

   A negative acknowledgment (which we will refer to as a FLUSH message)
   could be employed by a Host to mean:

      1. I have no room in my table

      2. I have no more available buffer space or

      3. I no longer wish to retain the table entry/buffer.

      In general, we believe that a Host should be allowed to throw away
      an IN or OUT+data whenever it is no longer convenient for the Host
      to hold the messages.  This can be immediately on the arrival of a
      message; for instance, if the Host does not want to buffer traffic
      for which it does not have a user buffer.  In lieu 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 a question which is left implementation dependent.  In
      general, we do not think it is 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.  In fact, we see nothing  inherently wrong with
      a process doing two or more SENDs to the same port as long as the
      communicating processes know what they are doing.  Of course, some
      communicating processes will prohibit several simultaneous
      messages being in transit between the same ports, for instance the
      TELNETs may well prohibit this.  However, for reasons of
      increasing bandwidth, etc., two processes may well want several
      simultaneous messages.  In this case we think it is up to the
      processes to worry about the sequencing of messages; however, we
      refer users desiring their processes to take a care of message
      sequencing 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 with regard to message
      buffering.  First, most OUTs will probably be accompanied by data.
      Therefore, in general, since the receiver process may be swapped
      out, the receiver Host monitor must be prepared to buffer some
      data somewhere.  To minimize the amount of buffering needed, the
      monitor could refuse further traffic from the IMP until the
      earlier traffic from the IMP has been written on a disk or drum.
      Or the monitor could have a small number of buffers in the monitor
      area of memory which it fills as traffic comes from the IMP, and
      which are swapped with buffers claimed earlier by the receiver
      processes as the receiver processes are swapped in.  Note that the
      buffers may be less than the maximum subnet message size in length
      if the RECEIVEs never specify a longer message length -- of
      course, this can be enforced.  Finally note that the message size,

      receive-port-id, etc. are available in the first 144 bits which
      come in from the IMP.  It might be useful to read this before
      deciding into which buffer to read the rest of the message.

Positive Acknowledgments

      Built into the system is a certain form of acknowledgment.  The
      information is always available as to 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

      The following section deals with the specific format of Host to
      Host messages and algorithms describing the proper response to a
      given message.

      Each message begins with a 144 bit header containing the following
      fields:

      1. HOST-TO-IMP leader (32 bits) as specified in BBN Reports 1822

      2. to port ID (i.e., the id of the port receiving the message) (24
         bits)

      3. MSG TYPE (8 bits) IN, OUT, FLUSH, etc.

      4. from port ID (i.e., id or the port sending the message) (24
         bits)

      5. initiating Host's table position (8 bits) see below.

      6. HOST "sourcing" this message (8 bits) see below.

      7. RENDEZVOUS HOST (8 bits)

      8. bit count of data (16 bits)

   The header format has been arranged so that no data item will cross a
   word boundary on machines with 16, 32, and 36-bit words, except where
   the size of the item is greater than the word size.  The actual
   arrangement of bytes within words is shown in the following figures
   for these three word sizes.  For the benefit of 36-bit Hosts, bytes 4
   and 13 (numbering from 0) are unused.  The 2 and 3-byte items do not

   cross word boundaries except for the port ID's on the 16 bit
   machines.  This attention to packing and unpacking ease was given
   both for general convenience, and in particular because Hosts may
   wish to examine the header at interrupt level to determine 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 Format

   The fields within the Host/IMP leader are already familiar to NCP
   programmers however, two points about these fields are worth
   mentioning.  First, the destination field originally contains the
   number of the rendezvous Host.  After rendezvous at a intermediate
   site, the destination field contains the source of the message
   rendezvous with.  Second, the link field for the MSP experiment can
   only contain link number 192-195.  We have not taken the time to
   figure out a sensible allocation of these four links among all the
   messages which might be sent using the MSP.  One alternative is to
   cycle over the links to increase the bandwidth of the "pipe" between
   any two Hosts. For the time being, until further consideration is
   given to this issue, we suggest each Host at a site using one
   (unique) link for all its communication.

   The message types we have to represent in the message type field are
   few now: we suggest message type 2 for SEND or OUT messages and
   message 3 for RECEIVE or IN messages.  Message type 4 is the FLUSH
   message, if FLUSH is used.

   The rendezvous Host field needs no comment.  Except that the field is
   unnecessary after the rendezvous has taken place and could then be
   used for something else.

   The bit count is a count of data bits in an OUT message or the size
   of the input buffer (not including the header) in an IN message.
   Thus the sender process can tell from the IN message bit count when
   it receives the IN message how much of the data in the OUT message
   was accepted by the receiver process and can use this knowledge to
   retransmit the remainder of the message if so desired.  After the
   rendezvous, we recommend that all of the data in the message be sent
   on the source of the IN message even if the OUT bit count was greater
   than the IN bit count.  Thus, at the receiver Host the monitor has
   the option (if it wants to take it) of discarding the message for
   being too long, sending the number of bits the receiver process has
   done an IN for into the receiver process and discarding the rest, or
   queuing the rest of the bits and somehow notify the receiver process
   that there are more bits which the receiver process can ask for.

   The to- and from-port-id fields are 24-bit numbers.  This size was
   chosen to help the TIPs.  The first eight bits of a port Id should be
   the number of the Host at which this port id was created.  Note well,
   that this is not necessarily the Host at which the port is being
   used.  This is necessary since rendezvous take place at intermediate
   sites and because ports may move from site to site.  We suggest that
   all port ids with the first eight bits all zero be reserved for
   network-wide use.  In particular, a port id with all 24 bits zero
   will be used to mean "ANY".  This gives us the options of:

            RECEIVE from ANY to SPECIFIC

            RECEIVE from SPECIFIC to SPECIFIC

            SEND from SPECIFIC to ANY

       and  SEND from SPECIFIC to SPECIFIC

   Examples of the use of these options will be given below.

   The other options (RECEIVE to ANY) and (SEND from ANY) we feel are
   kind of useless but would not prohibit them.  We believe that in the
   absence of explicit specification of rendezvous Host, the use of an
   ANY port id in the user's system call should affect the default
   rendezvous site as follows:

      RECEIVE from ANY--rendezvous in receiver

      RECEIVE from SPECIFIC--rendezvous in sender

      SEND to ANY--rendezvous in sender

      SEND to SPECIFIC--rendezvous in sender

   The less significant 16 bits of the id can be used however a Host
   wants to.  For instance, eight bits might be used as a process id and
   eight bits might be used as a channel specification within the
   specified process.  We suggest that each Host reserve the port ids
   with the middle eight bits all zero for special uses as well known
   ports.

   The table position field is included to help prevent costly table
   searches at interrupt level.  Hosts sending INs and OUTs, put in the
   table position field the rendezvous table position of the SEND or
   RECEIVE associated with the IN or OUT.  At an intermediate Host
   rendezvous, the table position fields in the matching IN and OUT are
   swapped so that when the messages arrive at the opposite end, the
   matching SEND and RECEIVE can be found quickly.  The MSP must do the
   swap at the rendezvous, but of course the MSPs need not fill in the
   table position field when first transmitting an IN or OUT in which
   case the information arriving in an IN or OUT will be meaningless.
   The general algorithm, then, is to check the table position as
   specified in this field and if that fails, search the whole table.

   The source field is filled in INs and OUTs by the MSP which
   originally sends these messages.  At the rendezvous the source of
   each message is preserved in the message being forwarded to the final
   Host.  When an IN or OUT arrives at a process, the process can use

   the source information to update its understanding of the rendezvous
   Host (e.g., when the destination Host and rendezvous Host are
   different).

EXAMPLES

The typical example.

   We envision communication normally taking place using specifications
   to and from ports and rendezvous at the sender.  For instance, the
   TIP would probably send to other Hosts using this method and would
   certainly receive from other Host 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 the exact correct length.

The logging example

   Consider an example of SEND to SPECIFIC and RECEIVE from ANY with the
   rendezvous at the receiver.  This method might be used by some
   logging receiver process with a well-known to-port.  For instance, a
   measurements program to which statistics are sent from many processes
   throughout the net.

The program library example

   Suppose within a given time-sharing system there is a particular
   library routine which is available for use by any process in the
   network.  The library process has a RECEIVE from ANY always pending
   at a well-known port.  Eventually, some process sends a message to
   the library process' well-known-port.  This message includes the data
   to be processed, a port to use for sending the answer, and the money.
   The library process takes some of the money and sends it to the
   well-known port of the accounting process which itself has a RECEIVE
   from ANY pending.  The library process then processes the data and
   sends the answer back to the process which requested the service
   using a SEND to SPECIFIC message which rendezvous at the destination
   where there is already a RECEIVE from SPECIFIC pending.  Of course,
   in this message besides the answer, any change the requesting process
   has coming is returned.

A comment

   As can be seen from our examples, we think rendezvousing at an
   intermediate Host will seldom be done as the chief benefit of this
   comes when it is desirable to move a port (see reference 4 for a
   discussion of this).  We would like to see all Hosts provide some

   (meager) amount of buffering for this purpose but would not require
   it.  It shouldn't be too painful to provide a little of this kind of
   buffering-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 us postulate a pair of Telnet programs that maintain two
   bidirectional communication paths, one for data and one for control.
   Let us also assume, for convenience that the port IDs are as follows:

      If the WRITE-CONTROL-ID is N, then --

         READ-CONTROL-ID=N+1,

         WRITE-DATA=N+2,

         READ-DATA=N+3.

   The initial state is the server Telnet sitting with a READ-FROM-ANY
   pending.

   The user Telnet now issues a SEND-TO-SPECIFIC with the data field
   containing the PORT-ID of the SERVER's WRITE-CONTROL-ID. This message
   is sent from the user-Telnet's WRITE-CONTROL-ID.

   Thus all port IDs are specified by the user Telnet, so, if desired,
   he need only remember one number and derive the rest.  Uniqueness is
   preserved since the port IDs supplied by the user Telnet contain his
   Host ID and other information making the ID unique to him.

   Now that these communication paths are established, the two processes
   can exchange data and control information according to established
   Telnet protocols.

THE INFORMATION OPERATOR

   The Message Switching Protocol itself impose no fixed requirements on
   the use of the port ID's, and the problem of process identification
   is somewhat separated from the means used to effect communication.
   It is, however, very much a part of the overall issue of interprocess
   communication, and so we here specify a facility for handling process
   identification, the information operator.

   One goal in a process identification scheme is to provide a means by
   which processes can select their own identifiers which can be
   guaranteed unique and can contain information meaningful to the user.
   Problems of efficiency prevent making the port ID's themselves large
   enough to accomplish this aim.  Efficiency questions aside, it would
   appear to be ideal to allow processes to use character strings of
   arbitrary length to identify themselves.  Uniqueness can then be
   easily ensured if, for example, users follow the convention of
   including their names in the process identification string.  Further,
   the remainder of the name can be chosen to have some meaning related
   to its use with obvious advantages and convenience for users.

   One solution is to establish a convention whereby the symbolic
   identifiers are used only during some initial phase of communication
   and not in every message.  That is, processes identify each other
   initially using symbolic identifiers, but exchange local port
   identifiers at the same time which are used for all ensuing messages.

   The means of providing this facility is to establish a process at
   each of a number of Hosts (e.g., all server Hosts) called the
   "information operator".  The function of this process is to associate
   symbolic identification strings and port ID's.  A process can
   identify itself and/or a foreign process to the information operator,
   and may request the port ID of the foreign process.  The symbolic
   identification strings are chosen by the processes and are long
   enough to contain meaningful information, e.g., LOGGER, MURPHY-
   TESTPROG.

   Communication with the information operator, whether by local or
   remote processes, is via the regular MSP functions.  The information
   operator will always have a RECEIVE ANY outstanding on a well-known
   port.  This could in general be the only well-known port in
   existence.  A message received on this port contains the following
   parameters:

      1. String identifying the foreign process with which communication
         is desired.

      2. String identifying the calling process.

      3. Calling process' port number.

      4. A delay specification.

   The format of these parameters is shown in Fig. 4.  In some cases,
   one or more of the arguments would be null.  Following receipt of a
   message, the information operator will, in some cases, do a SEND
   SPECIFIC to the calling process' port number providing the desired
   information or notice of failure.

   The following two cases would appear to cover all functions of the
   information operator.  They correspond to the SEND/RECEIVE SPECIFIC
   ANY cases of the MSP.

   1. Two processes each knowing the specific identify of the other wish
      to communicate.  Each does a SEND SPECIFIC to the information
      operator, giving parameters 1-2, the default delay spec in this
      case being WAIT.  When the information operator receives the
      second of these and notes that a match exists, it sends to each
      process the port ID of the other process and deletes both strings
      and both port ID's from its tables.  The two processes, which have
      each done a RECEIVE SPECIFIC in anticipation of the foreign port
      number, can then communicate using just the port numbers and basic
      MSP functions.

   2. A process is set up to provide some sort of general service or
      information, and its name and protocol advertised.  This process
      intends to maintain an outstanding SEND or RECEIVE ANY for the
      first (and perhaps only) message transaction, e.g., the library
      process discussed earlier.  Most such processes would be receivers
      initially, but there might be a few cases where a SEND could be
      left outstanding, and a forcing process could come along and pick
      up the information.  In either case, the service process will do
      SEND SPECIFIC to the information operator giving the local
      symbolic ID and local port ID.  The foreign symbolic ID would be
      null, and the default delay spec is NO-WAIT.  That is,

         INFO ( -, local ID, local port)

      The information operator will enter this information in its tables
      but return nothing to the caller.  The caller would proceed to do
      its SEND/RECEIVE ANY to wait for business.  When another process
      wishes to use the advertised service, it asks the logger for the
      port ID of the service process, i.e.,

         INFO (service ID, -, local port)

      The local symbolic ID need not be specified, and the default delay
      spec is NO-WAIT.  The information operator would SEND the port ID
      of the service process to the local port of the caller, and retain
      the table entry for future callers.  Only the service process

      could request the entry be deleted.  If the service ID was unknown
      to the information operator at the time of this call, it would
      immediately return a failure indication, i.e., zero.

   Communicating processes would normally use the information operator
   local to one or the other, and like the rendezvous Host in the MSP,
   this would be agreed upon in advance.  Service processes would
   normally use the information operator at their local site, and
   correspondingly, user processes would call the information operator
   at the site where the service process was expected to be available.
   There is no restriction on using an information operator at some
   other site of course, and some small and/or lazy servers could use a
   different Host for their service process ID's.  It presents no
   problem for two or more information operators to have entries for the
   same service process, and in fact, this may be very desirable for
   special types of service processes which exist only one place on the
   net and may move around from time to time.

   Processes would specify their own local port numbers, and each system
   would have to provide some way to help user processes do this.  In
   TENEX for example, one would probably use the job number concatenated
   with another number assigned within the job.  The information
   operator cannot supply port numbers because it will be running on a
   different Host than one or both of the communicants and cannot know
   what is a unique number for that Host.  In some cases, processes
   would ask the "unique number process" (described below) for their
   local port ID, and would make it known via the information operator.

   In actual practice, a few exceptions would be made to the rule that
   the only "well-known" port in the world is the information operator.
   Such exceptions would be processes common to many Hosts, e.g.,
   LOGGER, or those in particularly frequent use.  In such cases the
   unique port numbers would be assigned by administrative fiat and
   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 (byte of
   all zeroes).  The characters will be 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
                                                             4
   Parameters given:

      1. String identifying the foreign process with which communication
         is desired. (1 to 39 characters, or null)

      2. String identifying the calling process. (1 to 39 characters, or
         null)

      3. Calling process' port number.

      4. Delay specification:

            0=default
            1=wait for match
            2=don't wait for match

From 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

   The existence of unique port numbers is essential to the operation of
   the MSP.  For instance, when two communicating processes specify
   message rendezvous at an intermediate site, the processes must be
   able to specify to- and from-ports which are not being used by other
   processes which have specified message rendezvous at the same site or
   else messages may be delivered to incorrect destinations.  We have
   alluded to a method of providing unique port numbers earlier in this
   note.  This method is to partition the 24-bit port number space into
   disjointed segments and give one segment to each Host in the network

   to distribute when it is called upon to "create" a unique port id.
   Thus each 24-bit Host number will consist of two major parts.  The
   first 8 bits will be the number of the Host "creating" the port id
   and the next 16 bits can be used in any manner the creating Host
   desires.  This gives each Host 2^16 port numbers to distribute, and
   each Host will have the burden of distributing its segment of the
   port number space in a unique manner.  We recommend the convention
   that the port numbers with the middle 8 bits equal to zero be
   reserved for well-known ports in the creating Host's system.  We
   already recommend in an earlier section that port numbers with the
   first 8 bits equal to zero be reserved for network-wide use and in
   particular the port number with all 24 bits equal to zero be used to
   mean ANY.

   Since each Host only has 2-16- port numbers to distribute, in general
   port numbers will not be able to be held and used by processes for
   long periods of time (e.g., weeks and months).  More typically, Hosts
   will probably  implicitly "take back' all port numbers the Host has
   distributed each time the Host's system goes down and will
   redistribute the port numbers as required when the system comes back
   up.  In other words, port numbers will not in general remain unique
   over the going down of the creating Hosts.  Of course, a given Host
   may see to give the same port numbers to a number of standard
   processes (such as the FORTRAN compiler) each time it comes up port
   numbers registered with an information operator will frequently
   remain constant over system ups and downs.

   In spite of the fact that each Host will probably not in general be
   able to distribute port numbers to arbitrary user processes which ca
   be guaranteed to remain unique over a long period of time, there will
   still be demand for provision of long-term unique port numbers.  To
   some, the procedure of going through the information operator smacks
   much too much of making a connection.  These people will insist that
   for a variety of reasons their processes be allowed to communicate
   via ports whose identifiers remain constant for long periods of time.
   Therefore, it would be nice if at one or two places in the network, a
   long-term unique number service was provided.  We'll call a process
   providing this service the Unique Number Process.  The Unique Number
   Process would have assigned to it one segment of the unique port
   number space-all those port numbers, for instance, with the first 8-
   bits equal to 377-8.  This process would have a SEND-to-ANY pending
   from a well-known port with local rendezvous specified.  When any
   process wanted a unique number which it could depend on not to be
   used for all time or until the number is given back, it would send a
   RECEIVE-from-SPECIFIC specifying the well-known port of the Unique
   Number Process and rendezvous at the Unique Number Process' Host.
   The Unique Number Process' pending SEND-to-ANY would contain a unique
   number.  Also, the Unique Number Process would have a RECEIVE-from-

   ANY always pending at another well-known port with local rendezvous
   specified.  At this port the Unique Number Process would receive
   unique numbers which processes are giving back.  The Unique Number
   Process would maintain a bit table 2-16- bits long indicating the
   state of each of its unique numbers (free or in use) in some long-
   term storage medium such as in the file system.  The Unique Number
   Process might also maintain some information about each process to
   which it gives a unique number so that when the supply of unique
   number gets depleted, processes can be asked to return them.

   It has 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 gotten from the Unique
   Number Process.  It should also be mentioned that there would seem to
   be no reason, other than scarcity of storage space, that in addition
   to the port number through which primary access is gained to a
   process and which was called the process ID in the previous section,
   arbitrary port numbers along with their symbolic identified could not
   be registered with an information operator.  For instance, rather
   than registering the name BBN-FORTRAN and a single port number, one
   could perhaps register the port numbers whose symbolic identifiers
   were BBN-FORTRAN-CONTROL-TELETYPE, BBN-FORTRAN-INPUT-FILE, BBN-
   FORTRAN-LISTING-FILE, and BBN-FORTRAN-BINARY-OUTPUT-FILE.  This is
   perhaps at odds with standard practice within operating systems, but
   is consistent with the philosophy of reference 4 that communication
   is done with ports and not processes.

   Let us now address an issue which has been ignored up to now and
   which was only alluded to in reference 4, the issue of port
   protection.  We have not given this matter a great deal of thought;
   however, one mechanism for port protection seems quite
   straightforward.  The heart of this mechanism is a process at each
   Host which we shall call (alliteratively) the Port Protection Process
   (PPP).  The PPP maintains a list of all processes which exist at the
   Host and for each process the numbers of all ports which the process
   has "legally" obtained.  Every time a process does a SEND or RECEIVE,
   the monitor checks with the PPP to see if the process has specified
   port numbers it has the right to use; i.e., those legally obtained.
   The PPP has some RECEIVEs always pending at well-known ports.  When
   one process wants to pass a port to some other process, the first
   process sends a message to the PPP specifying the number of the port
   to be sent, the Host number at which the second process resides, a
   port at which the second process is expecting to receive the port,
   etc.  The PPP looks up in its tables whether the first process has
   the port it wants to send.  If it does, it sends a message to the PPP
   at the destination site.  The message contains the number of the port
   to be transferred and the RECEIVE port for the destination process.
   The destination PPP checks in its table whether the process has the

   RECEIVE port, and if so, passes the new port to the process and
   updates its tables to indicate the process now possesses the new
   port.  The messages to a PPP will optionally be able to specify that
   a copy of a port be sent, a port be deleted, etc.  The PPPs would
   probably have some built-in legal ports for each process,
   particularly the port's processes used to communicate with the PPP.
   The exact specification requires development but that should not be
   hard (see (3),(6), and (7) in reference 4).  The main difficulty we
   see is efficient checking of the PPP's tables by the monitor for
   every RECEIVE or SEND without entirely supplanting the monitor's
   current protection system.

FLOW CHART

   The following section describes a flow chart for most of the MSP.  A
   distinction is made between calls made by local processes called SEND
   and RECEIVE, and messages coming in over the NET called IN and OUT.
   An additional distinction is made between calls (or messages) with a
   local rendezvous and those with a foreign rendezvous Host.

   Since the code is quite similar, the distinction need not be made,
   but will be included for the sake of clarity.

   It is 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

   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

   It may of interest to the reader to know of some of the other MSPs we
   have considered while arriving at the present one.

   The simplest we considered is an MSP based on all rendezvous being
   done 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 receivers Host.  The OUT and RECEIVE
   rendezvous and the data is passed to the receiver process.  The
   transmission is now complete, except in some variations of this MSP
   an acknowledgement is sent to the sender process.  This MSP has
   couple of disadvantages: In the simplest formulation, the RECEIVE had
   to be waiting when the OUT+data arrived, otherwise the out data were
   thrown away.  This puts too tight a constraint on the timing of the
   SEND and RECEIVE, especially since the sender and receiver processes
   can be a continent apart.  However, if the IN is allowed to arrive
   first and must be held until matched by a RECEIVE, the monitor must
   buffer an indeterminate amount of data in all cases including the
   normal one.  Further, basing everything on rendezvous at the
   destination makes the process of moving a port difficult.

   The next simplest MSP we considered was the IPC of reference 4.  This
   works just the opposite of the above described MSP in that it is
   based on almost all rendezvous being done at the source Host with two
   special messages to handle the relatively uncommon cases when a
   rendezvous must be done at the destination or an intermediate Host.
   This system, its advantages, and disadvantages is discussed at very
   great length in the reference.

   A third variation on the MSP, 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 to the source of the OUT, but 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 requesting the data to be sent.  The data finally is 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 does not require any Host to buffer data for which
   a process has not set up an input buffer and perhaps for that reason
   it is a better system than the MSP we are presenting.

   In the last MSP variation we considered, the difference between SEND
   or RECEIVE and OUT or IN was discarded.  In this case only one
   message is used which we will call TRANSFER.  When a process executes
   a TRANSFER it can specify an input buffer, an output buffer, both, or
   neither.  Two processes wishing 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 which rendezvous at the
   rendezvous Host.  When the rendezvous occurs, the TRANSFER-messages
   plus their data cross and each is sent to the source of the other.
   The system allows processes not to know whether they must do a SEND,
   or RECEIVE and is (perhaps) a nice generalization of the MSP
   presented in this note.  For instance, two processes can exchange
   data using this system, or two processes can kind of interrupt each
   other by sending dataless TRANSFERs.  This variation of the MSP is a
   development of a suggestion of Steve Crocker.  Its disadvantages are:
   (1) unintentional matches are more likely to occur, (2) rendezvous
   selection site is more complex, and (3) 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  ]

 

User Contributions:

Comment about this RFC, ask questions, or add new information about this topic:

CAPTCHA