IEN 119
     
     
                 ST - A Proposed Internet Stream Protocol
     
                                    by
     
                              James W. Forgie
     
     
                        M. I. T. Lincoln Laboratory
     
                             7 September 1979
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     

IEN 119                      ST.DOC              7 September 1979
     
     
     
     
     1.0  INTRODUCTION
     
             The internet stream protocol (ST) described in this
     document has been developed to support efficient delivery of
     streams of packets to either single or multiple destinations in
     applications requiring guaranteed data rates and controlled delay
     characteristics.  The principal applications with these
     requirements are point-to-point speech communication and voice
     conferencing.  While ST has been developed as a part of the ARPA
     Internet Program and has been formulated as an extension to the
     presently defined Internet Protocol (IP), it is not likely to
     find useful application in the current ARPA internet environment
     where the networks and gateways lack the capacity to handle
     significant speech communication.  Instead, ST is aimed at
     application in wideband networks, in particular those intended to
     carry a large fraction of packet voice in their traffic mixes.
     Work is currently underway on such networks both for local access
     and long haul use. These networks will serve as vehicles for
     research on techniques for flow and traffic control and as
     testbeds for evaluating the potential of packet technology for
     providing economical speech communication.  The design of the ST
     protocol represents a compromise among the sometimes conflicting
     requirements of compatibility with the existing IP and the
     gateways which handle it, the need for flexibility in supporting
     flow and traffic control research, and transmission efficiency.
     
             The concepts in this protocol originated in the
     deliberations of a working group consisting of Danny Cohen, Estil
     Hoversten, and the author.  They have been influenced by
     interactions with many other people.  In order to examine the
     cost and feasibility of the protocol, the author has fleshed out
     some aspects of the protocol in detail.  The other working group
     participants have not had an opportunity to approve or modify
     these detailed aspects of the protocol, and consequently all
     responsibility for them lies with the author.
     
             The state of the protocol is such that, while there are
     still details to be worked out, implementation could begin if the
     protocol were acceptable to those interested.
     
     
     
     
     
     
     
     
                                    -2-
     

IEN 119                      ST.DOC              7 September 1979
     
     
     2.0  MOTIVATION AND GENERAL DESCRIPTION
     
             It is reasonable to ask why a new protocol is required to
     handle applications such as point-to-point speech and voice
     conferencing.  This section addresses that question and begins
     with a brief statement of the requirements for packet speech
     communication.  They are:
     
           1.  The network must be able to keep up with the data rate
               requirements of the speech terminal.  Because no bits
               need be transmitted during silent intervals, the
               average data rate for conversational speech can be
               expected to be between 40 and 50% of the peak data rate
               for commonly used constant-rate encoding techniques.
               Experimental variable-rate encoding techniques have
               exhibited higher peak-to-average ratios.  The network
               must be able to sustain the peak rate for the duration
               of talkspurt that can be as long as 20 seconds.
     
           2.  The stream of packets containing a talkspurt (a
               continuous segment of speech between silent intervals)
               must be delivered with a delay dispersion whose spread
               does not exceed some value that can be estimated with a
               high probability of success prior to the start of the
               talkspurt.  Since the individual packets of the spurt
               will experience different delays as they pass through
               the net, delay must be added at the receiver to allow
               continuous speech to be played out for the listener.
               It is necessary to predict the value of this smoothing
               delay before starting to play out the talkspurt.
               Packets that are delayed more than the predicted
               worst-case value will arrive too late to be used, and
               gaps will occur in the output speech.
     
           3.  Overall delay should be kept low.  If the overall
               round-trip delay is less than about l/4 second,
               conversations are carried out in a "normal" fashion
               with considerable feedback from "listener" to "talker"
               taking place.  When greater delay is experienced,
               people switch to a more formal mode in which feedback
               utterances are mostly suppressed, and the listener
               generally waits until the talker indicates that he has
               finished before saying anything.  User satisfaction
               declines with increasing delay, but systems remain
               usable for delays as long as several seconds.
     
           4.  The amount of speech for any one talker contained in a
               packet (the basic unit subject to transmission loss)
               should be kept small.  The loss of small (50 msec or
               less) chunks of speech produces a degradation of
               quality, but sentence intelligibility tends to be
     
     
                                    -3-
     

IEN 119                      ST.DOC              7 September 1979
     
     
               preserved up to fairly high percentage losses.  Larger
               chunks of speech represent whole syllables or words,
               and their loss can change the meaning of sentences.
     
           5.  Listeners will tolerate some packet loss without
               downgrading the acceptability of the system, but the
               probability of loss due to either failed or late
               delivery must be kept in the order of 1% or less to be
               considered acceptable for everyday (non-crisis) use.
     
           6.  As a network approaches its load limit it should reject
               (or hold off) new offered load on a call basis not on
               an individual packet basis.  Continuing to accept new
               calls beyond capacity can result in unsatisfactory
               communication for many users.
     
           7.  If packet-switched speech transmission is to become
               economically competitive with circuit-switched
               transmission, a further requirement must be met.  The
               product of packet efficiency and average link
               utilization must equal or exceed the efficiency of
               circuit switching. That efficiency is defined as one
               minus the fraction of the time that silence occurs in
               conversational situations.  Estimates of this fraction
               for real-world conversations give values for efficiency
               between 40 and 50%.  We will use 45% as a convenient
               figure for comparative purposes.  Packet switching can
               easily take advantage of the silent intervals in a
               conversation by not transmitting packets, but that
               advantage may be lost through the combination of
               overhead bits in packet headers (packet efficiency) and
               the difficulty of operating communication links at high
               average utilization while keeping queueing delays
               within reasonable bounds.
     
             Conventional datagram networks are unsatisfactory for
     speech communication except under conditions of light overall
     load or where speech constitutes a small fraction of the overall
     load and can be given priority service.  The difficulty with
     datagram nets comes from their inability to provide the
     controlled delay and guaranteed data rate required for speech.
     Delay increases with offered load, slowly at light load, but
     dramatically as average load approaches capacity. Flow control
     strategies tend to be aimed at buffer management and fairness
     goals, both of which will operate to restrict the effective data
     rate available to an individual user as load increases.  Traffic
     control strategies are mainly concerned with congestion control
     and are primarily defensive, resulting in offered datagrams being
     held off or refused when difficulties are detected.
     Unfortunately for the speech user, by the time congestion is
     detected, it is already too late.  For satisfactory speech
     
     
                                    -4-
     

IEN 119                      ST.DOC              7 September 1979
     
     
     service, congestion due to overload must be prevented.  Since a
     datagram net has no knowledge of the a priori requirements of
     users, it cannot develop traffic control strategies to meet these
     requirements.
     
             Another disadvantage of datagrams for speech is their
     packet efficiency.  The speech content of an individual user
     packet can be anything from 50 or so bits up to 1200 or 1300 bits
     depending upon the speech digitization technique in use.  The
     need to carry full source and destination addresses as well as
     other packet-handling information in each packet penalizes
     datagrams relative to other packet and circuit switching
     techniques.  In the internet case the penalty is worse since two
     sets of header information have to be carried.
     
             For example, IP datagrams on SATNET carrying 40-msec
     chunks of 16-kbps speech (a reasonaable chunk size and popular
     data rate) would have a packet efficiency of about 56% and would
     require utilization factors of about 80% to break even with
     respect to circuit switching. It is unlikely that delay
     characteristics would be satisfactory at this level of load.
     
             The goal of the ST design effort has been to attempt to
     overcome both of the difficulties associated with datagrams.  ST
     uses abbreviated internet headers and also allows speech from
     many talkers to be aggregated into single packets for
     transmission on wide-band networks where such aggregation is
     possible.  For the case of ST messages on a wide-band SATNET each
     carrying ten 40-msec chunks of 16-kbps speech for ten different
     talkers, packet efficiency would be about 86% allowing break-even
     link utilization to occur at 52%, a much more comfortable level
     for assuring desirable delay characteristics.
     
             Overcoming the inability of datagram nets to maintain
     data rates and delay characteristics as offered load increases is
     more difficult to achieve than improving packet efficiency.
     Circuit switching solves the problem by dedicating communication
     capacity to individual streams.  The goal of ST is to support
     traffic control policies that match stated user requirements to
     available resources taking into account the statistical
     properties of these requirements rather than the peak
     requirements used in circuit switching.  ST does not itself
     specify the traffic control algorithms to be used.  The
     development of such algorithms is an area of research that the
     protocol is intended to support.  Some algorithms may need only
     rough statistical knowledge of user requirements and network
     behavior.  Others may want more detailed knowledge and need to
     monitor the behavior of individual streams.  The protocol is
     intended to be general enough to support both extremes.  A
     successful traffic control algorithm would retain much of the
     statistical multiplexing advantages of datagram nets while at the
     
     
                                    -5-
     

IEN 119                      ST.DOC              7 September 1979
     
     
     same time gaining much of the guaranteed data rate and controlled
     delay capabilities of circuit switched nets.  A packet net using
     ST also has the ability of a circuit switched network to deny
     access to, or negotiate lower rates with, users whose demands
     would exceed capability.
     
             The ST protocol requires users to state the data rate and
     delay requirements for a data stream before accepting any stream
     data.  These requirements are used by ST agents (host processes
     and gateways) to determine whether or not resources are available
     in the catenet to support the offered stream load.  The
     determination is based on knowledge of the stated requirements of
     other users, negotiation with networks such as SATNET which have
     built-in resource allocation mechanisms, and statistical load
     estimates of traffic on networks that lack such mechanisms. In
     order to accept the offered stream load, the cooperating agents
     must find a route through networks with sufficient uncommitted
     capacity to handle the new stream.  In the process of routing the
     stream, intermediate agents retain information about the stream.
     The existence of this information allows the use of abbreviated
     headers on stream data packets and the efficient distribution of
     the multi-addressed packets required for conferencing.
     
             The process used by ST agents in finding a route with
     sufficient capacity between source and destination is assumed to
     use a distributed routing algorithm to take advantage of the
     robustness and flexibility characteristic of distributed packet
     routing techniques.  In the simplest case, the result would be a
     fixed-path internet route (a fixed set of intermediate agents
     (gateways)) for the stream packets.  In the event of gateway or
     network failure, rerouting would be required.  This can be
     undertaken automatically, but success is not guaranteed, since
     loss of the failed element or elements is likely to result in
     inadequate capacity to carry the original load.  Fixed-path
     routing is not required by the protocol.  If desired, dynamic
     alternate routing of stream packets can be used at the discretion
     of individual agents, but gateway implementation and the routing
     process will be more complex if that option is chosen.  The
     protocol described in this document assumes fixed-path routing.
     
             The goal toward which the cooperating ST agents in a
     catenet work is the maintenance of a controlled delay, guaranteed
     data rate environment in which packet speech communications can
     take place in a satisfactory fashion.  Obviously, other non-
     cooperating users of the networks involved in the catenet can
     make it impossible to achieve that goal. Some independence of
     other users can be obtained in some networks such as SATNET by
     the use of dedicated resources.  Gateways can be programmed to
     throttle non-cooperating internet traffic.  To some extent,
     networks with poor delay characteristics can be avoided in the
     routing process.  Priority service can be used in some nets to
     
     
                                    -6-
     

IEN 119                      ST.DOC              7 September 1979
     
     
     allow small quantities (proportionately) of ST traffic to be
     handled satisfactorily in spite of the activities of other users.
     However, the success of ST or any other approach to handling
     packet speech will require either the cooperation of all network
     users or the involvement of the networks themselves in providing
     the required controlled delay, guaranteed data rate services.
     
     3.0  RELATIONSHIP TO IP
     
             ST is intended to operate as an extension of the
     presently defined internet protocol (IP).  ST provides a
     different kind of service than the datagram service offered by
     IP.  ST must operate on the same level as IP in order to access
     local net resources such as SATNET streams and to be able to take
     advantage of any available local net multi-address delivery
     capabilities to support conferencing applications.  If an ST
     agent shares a local net port with an IP datagram handler, the
     two must cooperate in the use of the port to regulate traffic
     flow through the port.
     
             In order to get the advantage of abbreviated headers on
     stream packets, ST uses a different header format than that used
     for IP datagrams.  Packets with this format (see Section 5.0 for
     details) are called ST packets in this document.  They pass from
     one ST agent to another, and the abbreviated header information
     changes on a hop-to-hop basis.  However, ST packets cannot be
     transmitted until a route for the stream has been found and
     intermediate agents have built routing tables to translate the
     abbreviated headers.  Since end-to-end negotiation between ST
     users is often desirable before stream routing takes place, for
     example to agree on vocoder type and data rate, and it is
     convenient for a user to interface to only one protocol handler,
     ST provides a second type of service.  This service uses IP
     datagrams with an "ST" value in the IP Protocol Field.  These
     packets are called "IP.ST" packets.  They pass through datagram
     handlers in gateways and reach ST agents only at their
     destination hosts.
     
             A third type of packet is allowed by the protocol.  This
     type is realized by embedding an ST packet in an IP.ST packet.
     This method of sending an ST packet allows it to pass through
     gateways that do not support the ST protocol but do support IP
     datagrams.  Of course, the packet efficiency and traffic control
     benefits of ST are lost in such a case, but the use of this
     artifice could be justified on the grounds that any communication
     is better than none.
     
     
     
     
     
     
     
                                    -7-
     

IEN 119                      ST.DOC              7 September 1979
     
     
     4.0  CONCEPTS
     
             The key concept in ST is that of a connection.
     Connections are supported by entities called agents which are
     made aware of the connection during a setup process that precedes
     use of the connection for data transfer.
     
     4.1  Agents
     
             There are four types of agents that may be involved in
     supporting ST connections.  They are:
     
     4.1.1  ST Hosts
     
             The users of connections are processes that run in host
     computers and communicate over connections through other
     processes or software modules that adhere to the ST protocol.
     Hosts having these processes or modules are called "ST hosts" (or
     "hosts," when the context permits).  ST hosts perform the
     functions of gateway halves in interacting with gateways for
     internet traffic.  ST hosts share the management of local net ST
     resources with the other agents on the local net and are capable
     of routing connections to other agents as may be required.  In
     networks with local multi-addressing capability, ST hosts make
     use of this capability in routing conference connections.  In
     networks lacking such capability, ST hosts may need to replicate
     messages for conference connections unless a special agent called
     a "replicator" is available in the local net.  In some local nets
     it may be desirable for hosts to forward traffic for conference
     connections.  The protocol allows but does not require the latter
     capability.
     
     4.1.2  ST Gateways
     
             ST gateways perform routing and forwarding functions very
     similar to those performed by IP gateways.  Unlike IP gateways,
     they store information about the connections they support and
     share the management of resources in the nets to which they are
     connected with the other agents in those nets. Like hosts, ST
     gateways may have to replicate packets for conference
     connections.
     
     4.1.3  Replicators
     
             In networks that lack multi-addressing or broadcast
     capability it may be desirable to provide special server hosts to
     handle the replication required for conferences.  Replicators are
     needed in situations where the load caused by replication would
     produce congestion at a gateway port.  Use of a replicator adds
     delay and is probably not warranted unless the number of copies
     needed in a particular net exceeds some threshold that depends
     
     
                                    -8-
     

IEN 119                      ST.DOC              7 September 1979
     
     
     upon network port capacity. In worst-case situations a daisy-
     chain type of replication might be required because the peak rate
     could not be sustained at any network site.  The existence of a
     replicator does not eliminate the need for replication in hosts
     and gateways.  For example, a host in a conference with some
     participants on the same net but others on other nets may need to
     send packets to one or more gateways for speedy internet delivery
     as well as to a replicator for automatic distribution to other
     local net participants.
     
     4.1.4  Access Controllers
     
             The management of ST conference connections involves the
     services of an access controller.  The functions of an access
     controller are to control conference participation and provide a
     central source for information about the data rate requirements
     of a conference connection. Ideally, access control services
     would be provided by a set of hosts distributed throughout the
     catenet that shared information about the connections being
     controlled.  The addresses of these public access controllers
     would be known to all other agents, and a query to any one
     controller would provide information about any connection.  In
     the absence of public access controllers, the protocol allows any
     host to serve as a private access controller.  It is proposed to
     use a bit in the conference connection name to allow agents to
     determine whether a public or private access controller is
     responsible for a particular conference.  The name identifies the
     "owner" of the conference.  The owner is also the access
     controller in the private case.
     
     4.2  Connections
     
             Most applications for ST connections require full-duplex
     (bi-directional) communication between the parties in a point-
     to-point connection and omni-directional communication among the
     participants in a conference connection.  In the design of the
     protocol two different approaches to realizing the desired
     capability have been considered. The first, called the simplex
     approach, uses a combination of simplex (one-way) connections.
     For example, in the simplex approach the caller requests a
     simplex connection to the called party, who, after accepting the
     connection, requests another simplex connection for the return
     path to the caller.  In the second, called the full-duplex
     approach, the caller requests a full-duplex connection at the
     outset, and as soon as the called party has accepted the
     connection, data can flow in both directions.
     
             For conference connections, the simplex approach requires
     each participant to request a simplex connection to all the
     others.  The full-duplex approach requires that a participant
     request connection only to those that have not already requested
     
     
                                    -9-
     

IEN 119                      ST.DOC              7 September 1979
     
     
     connection to him.
     
             Both approaches can provide workable bases for the
     required capabilities.  The pros and cons for both may be
     summarized as follows:
     
           1.  Simplex connections can take maximum advantage of
               available resources by using different routes for the
               forward and return paths.  The routing of a full-duplex
               connection is more likely to fail since a path with the
               desired capacity in both directions must be found.
               This advantage for simplex connections is most
               pronounced in networks where load is assymetrical, a
               situation to be expected in nets carrying relatively
               heavy data loads.
     
           2.  Full-duplex connections can, except perhaps under
               conditions of heavy load, be set up more rapidly and
               with less control message traffic. The difference is
               most pronounced for conference connections.  With
               full-duplex components of a conference connection, m-l
               connection requests are required for an m-participant
               conference, since each new participant must connect to
               all those already in the conference.  In the case of
               simplex components each new participant must also
               connect to all those already in the conference; but, in
               addition, those already in must connect to each
               newcomer.  This activity adds sigma (m-l) connection
               requests (and responses) to the setup procedure.
     
           3.  Simplex connections have an advantage in situations in
               which two parties attempt to call each other at the
               same time.  The two simplex connections can easily be
               combined into the required full-duplex connection. If
               the two parties start out with full-duplex connections,
               one of them must be refused or disconnected, a somewhat
               more complex task for the higher level protocol
               requesting the connection.
     
             This document proposes a full-duplex basis for ST
     connections because the author believes that the advantage of
     relative simplicity and efficiency in setting up conference
     connections outweighs the advantages of the simplex basis.  To
     allow connections with assymetrical flow requirements, the
     protocol allows users to specify different data rates in the two
     directions.
     
             Even though traffic can flow in both directions on an ST
     connection, the connection has an orientation, and packets are
     said to move in either the "forward" or "backward" direction
     depending on whether they are moving away from or toward the
     
     
                                   -10-
     

IEN 119                      ST.DOC              7 September 1979
     
     
     originator of the connection.
     
             ST provides two types of connections:  Point-to-Point
     (PTP) and Conference (CONF).  PTP connections use different
     packet header formats and setup procedures to reduce overhead and
     allow faster setup for that more frequently used type.
     
     
     4.2.1  Point-to-Point (PTP) Connections
     
             PTP connections are set up in response to a CONNECT
     command from an originating process to an ST agent.  The CONNECT
     specifies the following:
     
           1.  The NAME of the connection.  The NAME is obtained by
               concatenating the ST address of the originating process
               (ORIGIN) with an arbitrary number.  The ST address is
               the internet host address (ala IP) concatenated with an
               "extension" field (32 bits) to specify a process in the
               host (a telephone for NVP applications).  It is the
               responsibility of the originating process to provide
               arbitrary numbers that keep the names of all
               outstanding connections unique.
     
           2.  The internet address of the process to which the
               connection is desired.  This address is called the
               "TARGET." The terms "ORIGIN" and "TARGET" are used
               instead of "SOURCE" and "DESTINATION" because the
               latter terms will be used to refer to the senders and
               receivers of packets travelling on the connection.
               Thus the ORIGIN process can be both SOURCE and a
               DESTINATION for packets on the full-duplex connection.
     
           3.  A flow specification (FLOW-SPEC) that tells ST agents
               about the desired characteristics of the connection.
               In addition to information about the data rate
               requirements for both directions of the full-duplex
               connection, the FLOW-SPEC has a PRECEDENCE value that
               agents can use as a basis for the preemption of this or
               other connections as part of the traffic control
               strategy.  The FLOW-SPEC is discussed in more detail in
               Section 4.5.
     
           4.  An arbitrary 16-bit number that the agent is to use to
               identify all ST packets that it will send to the
               originator on the connection (the backward direction).
               This identifier is called the "CID.B."  If the
               connection request is accepted, the originator will be
               given a CID.F to be used to identify all packets it
               sends in the forward direction on the connection.
               These CID's allow abbreviated headers to be used on ST
     
     
                                   -11-
     

IEN 119                      ST.DOC              7 September 1979
     
     
               packets and provide a means for agents to rapidly
               locate the stored forwarding table involved in handling
               a received packet.  CID's are assigned by the agents
               receiving packets and need be only locally unique since
               they are reassigned on a hop-by-hop basis.  The CID to
               be used on the next hop is stored in the agent's
               forwarding table.
     
             During the setup procedure the CONNECT command propagates
     from agent to agent until it reaches the TARGET process.  This
     propagation differs from ordinary packet forwarding in that the
     intermediate agents inspect the command, take appropriate action,
     and retain information about the requested connection.  If the
     TARGET process agrees to the connection, it sends an ACCEPT
     command that is propagated back through the same intermediate
     agents that handled the CONNECT.  The agents take appropriate
     action as they process the ACCEPT.  If the TARGET process is not
     willing to accept the connection, it issues a REFUSE command
     which propagates back in the same fashion as the ACCEPT.
     REFUSE's are generated by intermediate agents if they find
     themselves unable to support a requested connection. An agent
     receiving such a REFUSE tries alternate routes and passes the
     REFUSE back another hop only when it has exhausted its routing
     alternatives. Appropriate REASON codes are included in the REFUSE
     commands.
     
             After a connection has become established (an ACCEPT has
     reached the ORIGIN), changes to the FLOW-SPEC can be accomplished
     by the ORIGIN issuing a new CONNECT or the TARGET issuing a new
     ACCEPT command.  (Actually, the TARGET can issue a new ACCEPT at
     any time after issuing the first ACCEPT, and it can also at that
     time begin sending packets on the connection although there is
     some hazard in doing so since they may pass the ACCEPT enroute
     and be discarded.)  For the case where the FLOW-SPEC calls for a
     connection whose rate can be varied at the discretion of the
     catenet, intermediate agents issue CONNECT's and ACCEPT's to
     inform other agents and the end users about rate changes.  These
     commands are marked to distinguish them from end user commands.
     
             The ACCEPT command contains the same kinds of information
     as the CONNECT except that the backward connection identifier
     (CID.B) is replaced by a forward identifier (CID.F).  In
     addition, the FLOW-SPEC will generally be different and will
     indicate the data rates and delay characteristics accepted by the
     agents.  The CONNECT that arrives at the TARGET will be similarly
     modified from the CONNECT that was issued by the ORIGIN and will
     match the ACCEPT received by the ORIGIN.  See Section 4.5 for a
     discussion of the changes that can occur to the FLOW-SPEC.
     
     
     
     
     
                                   -12-
     

IEN 119                      ST.DOC              7 September 1979
     
     
     4.2.2  Conference (CONF) Connections
     
             The type of connection required for voice conferencing is
     one in which any participant can send messages to all the others.
     Connections of this type have been called "omniplex" connections.
     ST realizes a conference connection by means of a superposition
     of tree-like components that start from an origin process (the
     root) and extend to a set of targets (the leaves).  The set of
     participants in a conference is represented by a bit map.  Each
     participant has a location in the conference bit map that is
     assigned by the access controller (AC).  When a conference
     CONNECT command is given, a TARGET-BIT-MAP (TBM) is used to
     specify the set of targets to which connection is requested.  The
     TBM is supplied by the AC when a participant joins a conference.
     The tree-like components all have the same NAME, and intermediate
     agents combine branches from the components whenever possible to
     minimize resources committed to the conference.  Because of this
     combining, an ORIGIN-BIT-MAP (OBM) is needed to represent the set
     of originators that have requested connection to a particular
     participant.
     
             The list of participating processes in a CONF connection
     is not carried in the CONNECT request but is is maintained by the
     AC and provided to agents and participants when needed.  Another
     function of the AC is to provide the FLOW-SPEC for the connection
     to any agent on request.  The reason for assigning these tasks to
     an access controller is to prevent unauthorized connection to a
     conference and to assure that all components of the connection
     use the same FLOW-SPEC.
     
             The first step in establishing a conference is to install
     a list of participants and a FLOW-SPEC in an AC.  The list of
     participants may be fixed at the outset or be allowed to grow
     during the course of the conference.  A participant may depart
     from a conference, but his position in the list and the bit maps
     is not reused.  The method by which the list of participants is
     made known to the AC is not of concern to ST itself and is not
     specified in this document.  Higher level protocols such as a
     network voice protocol (NVP) engage in communications between
     participant processes and the AC in the process of setting up a
     conference.  For example, an NVP issues a JOIN  command to
     request access to a conference.  If the NVP process is on the
     participant list or is otherwise acceptable, the AC responds with
     a WELCOME command that among other things tells the participating
     NVP its location in the CONF bit map.  The NVP then sends TELL-ME
     messages to the AC to obtain the participant list and FLOW-SPEC
     for the CONF connection.  This information is provided in INFO
     messages from the AC.  Several of these messages may be required
     to transmit all the information about a large conference.  The
     messages exchanged between participants and the AC are IP.ST
     datagrams.  They cannot be ST packets because no ST connection
     
     
                                   -13-
     

IEN 119                      ST.DOC              7 September 1979
     
     
     exists between the participants and the AC.
     
             Once a participant has received a WELCOME message from
     the AC, it can issue a CONNECT.CONF command to its ST host agent.
     It uses a TARGET-BIT-MAP (TBM) that it received as part of the
     data in the WELCOME message.  This TBM has bits set for all the
     previous joiners of the conference.  The CONNECT.CONF will thus
     attempt to establish a full-duplex path to each of the previous
     joiners.  These paths will make use of common links where
     possible and will result in a connection resembling a tree rooted
     at the site of the process originating the connection.  When the
     CONNECT.CONF is issued by the originator it contains an ORIGIN-
     BIT-MAP (OBM) with a single bit set corresponding to the
     originating participant.  If the CONNECT.CONF is successful
     (i.e., some subset of the targets are reached), an ACCEPT.CONF
     will be returned with bits set in the TBM indicating the
     participants to which connection has been achieved.  In a CONF
     connection attempt, success may not be achieved with the entire
     set of targets specified by TBM.  Some may be unreachable for any
     of a number of reasons.  REFUSE.CONF messages will be returned
     for all such failures with bits in the TBM identifying the
     unreachable participants.  If the failures in a particular
     attempt are due to more than one REASON, at least one REFUSE.CONF
     will be returned for each reason.
     
     
             The technique for setting up conference connections
     proposed for ST results in each participant actively connecting
     to some subset of the others while accepting connections from the
     rest.  The first participant does not issue a CONNECT and accepts
     all the others.  The last connects to all the others and accepts
     none.  Each participant can maintain up-to-date information about
     participation in the conference by utilizing the information in
     the CONNECT and ACCEPT messages it receives.
     
     
             The CONNECT.CONF messages received by agents during the
     setup procedure do not contain information about the identity of
     the participants.  In order to route the connection, the agents
     must acquire this information, and they do so by sending TELL-ME
     messages to the AC and getting INFO messages in response.  They
     need to retain this information only during the routing phase of
     connection setup.  Once the connection is established, bit map
     information in forwarding tables combined with a FORWARDING-BIT-
     MAP (FBM) in the ST packet is sufficient to handle the forwarding
     of packets on the connection.  The FBM is used to specify the set
     of destinations for the packet.  Thus a packet can be sent to all
     or any subset of the connection participants. The source of the
     packet is identified by a number representing the position of the
     source participant in the conference bit map.
     
     
     
                                   -14-
     

IEN 119                      ST.DOC              7 September 1979
     
     
             In the case of a voice conference, no useful purpose is
     accomplished when many people speak at the same time.  It is
     expected that a higher level protocol (part of NVP) would
     regulate the activity of the conference and would normally allow
     one or perhaps two persons to transmit speech at the same time.
     ST is not involved in this aspect of conference control except to
     the extent that if there are too many simultaneous talkers, the
     traffic-handling capability of the connection could be exceeded,
     and ST might discard some of the packets.  The higher level
     control protocol should set the FLOW-SPEC for the connection to
     accommodate the expected traffic flow.  Thus, for a simple one-
     at-a-time conference, ST would be asked for a data rate
     corresponding to a single speech stream.
     
             The above discussion has described a connection
     arrangement suitable for supporting voice conferences in which
     any participant can transmit and be heard by all others.  ST also
     provides another kind of multi-address message delivery
     capability.  If only one participant issues a CONNECT.CONF
     command with a TBM specifying connection to all the others, a
     tree-like connection will be set up that allows the ORIGIN to
     send packets to all the others and receive from any of the
     others, but packets sent by the others will be received only by
     the ORIGIN.
     
     4.2.3  Taking Connections Down
     
             The process of taking a connection down is initiated
     either by an ORIGIN issuing a DISCONNECT message or a TARGET
     issuing a REFUSE. These messages propagate from agent to agent
     along the connection path so that intermediate agents can take
     appropriate action to clean up their stored information about the
     connection.
     
             Connections can also be taken down as a result of
     intermediate agents detecting a faulty link or gateway or
     deciding to preempt the connection.  In this case the agent or
     agents involved issue a DISCONNECT/ REFUSE pair that propagate in
     the appropriate directions.  A REASON code in the messages
     informs the users as to the cause of the disconnection.
     
             In the case of conference connections, bit maps allow
     selective disconnection and refusal.
     
     4.3  Types of Service
     
             ST offers two types of service for packets travelling on
     connections.  Neither type has any delivery guarantees, i.e.,
     there are no acknowledgements or retransmissions on either a
     hop-by-hop or an end-to-end basis.  Neither type guarantees
     packet integrity; i.e., if local nets offer a type of service
     
     
                                   -15-
     

IEN 119                      ST.DOC              7 September 1979
     
     
     that can deliver packets with bits in error, ST may use that type
     of service.  The headers of ST packets are sum-checked by ST
     agents, but the data portions are not.
     
             The two types of service differ in whether or not they
     use the channel capacity nominally allocated to the connection
     and also in the strategy used by intermediate agents in buffering
     them.  The two types are:
     
           1.  Stream Packets (called ST.ST packets).  These packets
               use the allocated resources and are buffered for a
               short time only, since they are intended for
               applications such as speech communication where a late
               packet is not worth delivering.  They are discarded by
               intermediate agents if queue conditions indicate that
               they cannot be delivered in a timely fashion.
     
           2.  Datagrams (called ST.DG packets).  These packets have
               the same form as ST.ST packets except for a flag bit in
               the header and travel over the same connection path.
               They use allocated resources only when spare capacity
               exists, e.g., when the ST.ST flow drops below the
               allocated value.  Otherwise they share local net
               resources with other IP datagram traffic.  They are
               buffered with a queueing strategy appropriate for
               datagram traffic and are discarded only when agent
               buffer resources approach exhaustion.  They are
               intended for use by higher level protocols such as NVP
               in applications such as dynamic control of the "floor"
               in a conference.  They are also used by ST itself for
               connection management.
     
     4.4  Packet Aggregation
     
             ST allows any ST packets, stream or datagram, to be
     aggregated together that have the same next-agent local-net
     destination.  "Aggregation" is a form of multiplexing, but is
     given a different name to distinguish it from the multiplexing
     done in the IP Multiplexing protocol that allows multiplexing
     only for packets with the same end-to-end source and destination.
     The term "envelope" is used to refer to any ST message sent from
     one agent to another.  An envelope may contain one or more ST
     packets and is limited in size by the maximum size of packet that
     the local net can carry.  The envelope has a short header in
     addition to the header of the individual aggregated packets.  See
     Section 5.0 for a description of header formats.
     
             The ST aggregation technique requires agents to look
     inside of received envelopes and handle the packets as individual
     entities.  This procedure adds to the computing load of gateways,
     but can achieve significant communication savings in networks
     
     
                                   -16-
     

IEN 119                      ST.DOC              7 September 1979
     
     
     with high per-packet overhead such as SATNET, particularly when
     many short packets must be handled.
     
     4.5  Flow Specifications
     
             The FLOW-SPEC that is carried by CONNECT and ACCEPT
     messages contains several fields.  Some are specified by the
     originator of the CONNECT.  Others are produced either during the
     process of setting up the connection or changing its allowed flow
     characteristics.  Some apply in common to both directions of the
     full-duplex connection.  Others apply individually to allow
     different flows in the two directions and appear in pairs in the
     control messages.
     
             Data rate, the basic quantity used in traffic control
     computations, is specified by means of three parameters; a stream
     interval (SI), a packet length (PL), and a duty factor (DF).  The
     average expected data rate can be computed by taking the product
     of PL, DF, and the reciprocol of SI.  The FLOW SPEC allows for
     one value each for SI and DF for each direction.  However, as
     many as four values of PL can be provided as options, allowing
     the ST agents flexibility in allocating resources for some types
     of traffic flow.
     
             The flow type (TYPE) parameter is intended to allow ST to
     take into account a variety of different user load
     characteristics.  The set of possible types can be expected to
     grow with experience, but a relatively few types seem to be
     adequate to deal with presently contemplated voice encoding
     techniques.  These are:
     
           1.  Fixed Rate.  The data rate is held fixed for the life
               of the connection.  A simple speech encoder that can
               run at only one rate would use this type value with all
               four PL's set to the same value.  A somewhat more
               complex encoder that could run at more than one rate
               but could not change rates on the fly would use the
               fixed-rate type but could offer a choice of up to four
               values for PL.  A variable-rate vocoder such as the
               LPC2 vocoder used in the ARPANET that has a rate that
               varies depending on the short time behavior of the
               speech signal would also use the fixed-rate type but
               would set the duty factor to a lower value than the 0.5
               or so used by a simple encoder.
     
           2.  Multiple Rate.  The data rate allowed can be of any of
               the four specified by the four PL's and the agents are
               free to change rates at any time to accommodate to
               network load changes.  Whenever an agent changes the
               rate, it sends appropriate CONNECT and ACCEPT messages
               to tell other agents and the users about the change.
     
     
                                   -17-
     

IEN 119                      ST.DOC              7 September 1979
     
     
               Since such rate changes require extra communication and
               processing in the catenet, agents would have to avoid
               frequent changes.  This flow type would be used by
               enoders that run at a variety of rates and can switch
               rates rapidly but need to do so explicitly either
               because packet formats must change with rate changes or
               because some parameter such as sampling rate must be
               changed at sender and receiver.  This flow type could
               also be useful for sending data rather than voice over
               ST connections.
     
           3.  Prioritized Variable Rate.  This flow type is intended
               for use by certain advanced encoders of a kind called
               "embedded" where subsets of the coded bit stream can be
               stripped en route without loss of intelligibility.
               There is, of course, some loss of quality and/or
               ability to withstand acoustical background noise when
               stripping occurs.  For this flow type each of the four
               PL's corresponds to one of the four packet priorities
               that can be attached to ST.ST packets.  The encoder
               would place the bits needed for its lowest rate in the
               highest priority packet, the next lowest in the second
               highest, etc.  When pressed for channel capacity,
               agents would be free to discard the lower priority
               packets for this flow type.  The overall precedence of
               the connection would also affect the probability of
               packet discard.  It is not anticipated that agents
               would send explicit messages to announce that
               discarding was taking place.
     
             Another set of parameters in the FLOW-SPEC is concerned
     with transmission delay.  ST does not allow the user to specify a
     delay requirement, but it does allow some control over the
     tradeoff between delay and data rate options during the routing
     process.  A ROUTING-STRATEGY parameter is provided for this
     purpose.  Currently, two strategy options for PTP connections are
     envisioned, but others could be added if desired.  One gives
     preference to minimizing delay at the expense of data rate.  The
     other gives preference to data rate over delay.  The ROUTING-
     STRATEGY options are meaningful only when data rate options are
     available.  Otherwise data rate is as absolute requirement in
     routing.
     
             While a user cannot specify a delay requirement to ST, ST
     does provide the user with an estimate of both minimum delay and
     delay dispersion in fields of the FLOW-SPEC.  The estimates are
     based on a priori statistics relating delays to average network
     loads.  When an agent propagates a CONNECT packet, it adds values
     from tables indexed on the current load estimate to the MIN-DELAY
     and DISPERSION fields of the FLOW-SPEC for the forward direction.
     It performs the same function for the backward direction as it
     
     
                                   -18-
     

IEN 119                      ST.DOC              7 September 1979
     
     
     propagates the ACCEPT.  The MIN-DELAY is the simple sum of the
     hop-to-hop contributions, but the DISPERSION is a sum of squares.
     The receiver can compute an estimate of overall delay by adding
     the MIN-DELAY to the square root of the DISPERSION.  The
     DISPERSION estimate by itself can be useful in setting the
     reconstitution delay value needed to play out satisfactory speech
     for listeners.  The proper value can vary over a wide range
     depending on the path through a catenet of networks with very
     different delay characteristics.
     
             Another parameter set by agents during the routing
     process is the ACCEPTED-RATE field.  This field informs the users
     as to which of the four possible data rate options (PL's) have
     been accepted for each of the two directions of the connection.
     Of course, if none were acceptable, a REFUSE would be returned
     with a REASON code indicating unavailability of resources at the
     requested precedence level.  Another flow-related reason for
     refusal could be an inability of the networks to handle a too-
     short stream interval.
     
             All FLOW-SPEC parameters except PRECEDENCE and ROUTING-
     STRATEGY can be independently specified or are reported
     separately for each of the two directions of the full-duplex
     connection.  The exceptions are required to apply to the entire
     connection to simplify the task of gateways in handling
     connections.
     
             The ROUTING-STRATEGY field has other control functions in
     addition to weighting the tradeoff between data rate and delay.
     For CONF connections it indicates whether or not data rate
     options must match in both directions (a requirement for voice
     conferencing) or can be negotiated independently.  If ST agents
     support split routing, (a capability to divide the traffic on a
     connection among two or more paths) the ROUTING-STRATEGY field
     will indicate whether or not this technique is to be applied to
     the connection. Split routing also requires additional fields to
     indicate the fraction of the nominal traffic that has been
     accepted or is requested to be handled. This document does not
     propose the implementations of split routing in the first version
     of ST.
     
     
     
     
     
     
     
     
     
     
     
     
     
                                   -19-
     

IEN 119                      ST.DOC              7 September 1979
     
     
     5.0  PACKET FORMATS
     
             The messages sent between ST agents on connections are
     envelopes containing one or more ST packets.  The envelope
     consists of an envelope header (EH) followed by one or more
     packet headers (PH's) followed by the data portions of the
     packets in the same order.  The envelope thus has the form:
     
             EH, PH1, PH2, . . .PHn, DATA1, DATA2, . . . DATAn
     
     The reason for aggregating the headers separately from the data
     is that doing so allows the header region to be checksummed
     easily as a unit before attempting to parse the envelope.  It is
     expected that ST will be used in networks that can deliver
     messages with bits in error and that some non-negligible fraction
     of the messages will have such errors.  To require the entire
     envelope to be error-free in order to use any of it would result
     in an excessive rate of lost packets.
     
             Since ST operates as an extension of IP, the envelope
     arrives at the same network port that IP uses to receive IP
     datagrams.  It is proposed to use a unique code in the first
     field of the message to identify it as an ST envelope.  The first
     four bits of an IP datagram are defined to be the Version Number
     field.  It is therefore proposed to use one of the 16 possible IP
     versions to distinguish ST envelopes from IP datagrams.  With
     this convention an envelope header will have the following
     format:
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
                                   -20-
     

IEN 119                      ST.DOC              7 September 1979
     
     
                            ENVELOPE HEADER
     
                      0                   1
                      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
                     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                     !  ST   !VERSION! HEADER-LENGTH !
                     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                     !          TOTAL-LENGTH         !
                     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                     !             CKSUM             !
                     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     
               ST is the particular IP Version Number assigned to
               identify ST envelopes.
     
               VERSION is the ST version number.  This document is a
               proposal for VERSION 1.
     
               HEADER-LENGTH* is the length in words of the envelope
               header (3) plus the sum of the header lengths of the
               aggregated packets.
     
               TOTAL-LENGTH is the length of the entire envelope.  It
               does not include any local net headers or trailers.
     
               CKSUM covers the envelope header and all packet
               headers.
     
     ++++++++++++++
     *All ST communications use the 16-bit word as a basic unit.  All
     lengths are in word units.
     ++++++++++++++
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
                                   -21-
     

IEN 119                      ST.DOC              7 September 1979
     
     
             The individual packet headers have one of two formats
     depending on whether they are for PTP or CONF connections.  These
     formats are:
     
                           PTP PACKET HEADER
     
                      0                   1
                      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
                     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                     !              CID              !
                     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                     !0!     BITS    !  DATA-LENGTH  !
                     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     
                           CONF PACKET HEADER
     
                      0                   1
                      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
                     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                     !              CID              !
                     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                     !1!     BITS    !  DATA-LENGTH  !
                     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                     !  Spare  ! FBML! !    SID      !
                     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                     !        FBM - 1st word         !
                     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                                    .
                                    .
                     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                     !        FBM - nth word         !
                     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     
               CID is an arbitrary identifier assigned by the agent
               receiving the packet for the purpose of identifying the
               connection on which the packet is travelling.  Since
               the CID is unique only to the agent that assigned it,
               it will generally have a different value on each hop of
               the connection path.
     
               BITS are defined as follows:
                 Bit 1 distinguishes stream packets (ST.ST) from
                 datagrams (ST.DG) (1 = DG).
     
                 Bits 2 and 3 define the packet priority (00 = highest
                 priority).
     
                 Bits 4 and 5 are spares.
     
                 Bits 6 and 7 are unused (may be used by higher level
                 protocols if desired).
     
     
                                   -22-
     

IEN 119                      ST.DOC              7 September 1979
     
     
               DATA-LENGTH is the length of the data field in words.
     
               FBML (3 bits) is one less than the length of the
               Forwarding Bit Map (FBM) in words.
     
               SID (7 bits) identifies the source of the packet on a
               CONF connection (the source is implicit for a PTP
               connection packet).  The value of SID corresponds to
               the bit position of the source in the conference bit
               map.  Bit numbers start with zero, and positions start
               with the left-most (most significant) bit of the first
               word of the bit map.
     
               FBM is the Forwarding Bit Map.  It can be at most 128
               bits (8 words) long, and thus it limits conferences to
               128 participants (a generous number).  Ones in the FBM
               indicate that the packet is to be delivered to the
               corresponding participants.  The FBM is allowed to
               increase in one word increments to allow new
               participants to enter during the course of a
               conference, but it does not shrink when participants
               leave, and bit positions are not reused.
     
             As pointed out in Section 3.0, ST supports a second type
     of communication called IP.ST datagrams.  These are ordinary IP
     datagrams with an "ST" value in the protocol field.  They are
     used to allow higher level protocols to communicate prior to the
     setting up of an ST connection, and they are also used for
     communication between access controllers and other ST agents
     during the setup of CONF connections.  They are strictly point-
     to-point communications since they are IP datagrams.  According
     to the conventions for IP datagrams, these messages would have
     the form:
     
             IP Header, IP.ST Header, Data
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
                                   -23-
     

IEN 119                      ST.DOC              7 September 1979
     
     
             The IP.ST Header has the following form:
     
                          IP.ST PACKET HEADER
     
                      0                   1
                      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
                     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                     ! IP.ST !VERSION!    LENGTH     !
                     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                     !            SOURCE-            !
                     +-+-+                       +-+-+
                     !           EXTENSION           !
                     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                     !          DESTINATION-         !
                     +-+-+                       +-+-+
                     !           EXTENSION           !
                     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     
     
               IP.ST is a value chosen to be different from the "ST"
               value used in the first four bits of the ST envelope.
               This field allows IP.ST datagrams to be distinguished
               from ST envelopes embedded in IP.ST packets, a
               technique that can be used to get ST envelopes through
               gateways that do not support ST.
     
               VERSION is the ST version number.
     
               LENGTH is the total length of the IP.ST packet
               excluding IP and local net headers, etc.
     
               SOURCE- and DESTINATION-EXTENSION's are 32-bit fields
               used to identify the source and destination processes.
               Like ARPANET NCP process identifiers, they are not
               specified by the protocol.  The source and destination
               host addresses are carried in the IP header.
     
     
     6.0  CONTROL MESSAGES
     
             With the exception of communications with access
     controllers, ST control messages are sent from agent to agent as
     ST.DG packets with the CID set to zero.  This convention is
     similar to the ARPANET NCP use of Link 0 for control.
     Communication with AC's uses IP.ST packets.  The form is
     otherwise the same.  The control protocol follows a request-
     response model with all requests expecting responses and all
     responses expecting acknowledgements.  Retransmission after
     timeout is used to allow for lost or ignored messages.  A packet
     may contain more than one control message.  Control messages do
     not extend across packet boundaries.
     
     
                                   -24-
     

IEN 119                      ST.DOC              7 September 1979
     
     
             Control message headers have the following format:
     
                         CONTROL MESSAGE FORMAT
     
                      0                   1
                      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
                     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                     !    OP-CODE    !    LENGTH     !
                     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                     !             CKSUM             !
                     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                     !           REFERENCE           !
                     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     
               OP-CODE specifies the request or response.
     
               LENGTH is the length of the control message in words.
     
               CKSUM is the checksum of the control message.  Because
               the control messages travel in envelopes that may be
               delivered with bits in error, each control message must
               be checked before it is acted upon.
     
               REFERENCE is an arbitrary reference number used to
               associate requests with responses and acknowledgements.
     
             The header is followed by parameters as required for the
     particular OP-CODE.  Each parameter is identified with a P-CODE
     byte that is followed by a P-LENGTH byte indicating the length of
     the parameter (including the P-CODE, P-LENGTH word) in words.
     Parameters can be sent in any order. The format of individual
     parameters is specified in the following sections in connection
     with the OP-CODE's with which they are used.
     
             Control messages fall into two categories according to
     whether they deal with PTP or CONF connections.  There are four
     messages that are independent of connection type.  These are:
     
     6.0.1  [ACK]
     
             ACK (OP-CODE = 1) has no parameters.  The REFERENCE in
     the header is the REFERENCE number of the message being
     acknowledged.  ACK's are used to acknowledge responses to
     requests and in some cases constitute responses or partial
     responses themselves.
     
     
     
     
     
     
     
     
                                   -25-
     

IEN 119                      ST.DOC              7 September 1979
     
     
     6.0.2  [HELLO]
     
             HELLO (OP-CODE = 2) is used to determine whether or not
     another agent is alive and well.  It has no parameters and
     expects an ACK in response.
     
     6.0.3  [ERROR-IN-REQUEST] <REF> <ERROR-TYPE>
     
             ERROR-IN-REQUEST (OP-CODE = 3) is sent in response to a
     request in which an error is detected.  An ACK is expected.  No
     action is taken on the erroneous request.
     
               REF (P-CODE = 7, P-LENGTH = 2) is the REFERENCE number
               of the erroneous request.
     
               ERROR-TYPE is not yet specified.
     
     6.0.4  [ERROR-IN-RESPONSE] <REF> <ERROR-TYPE>
     
             This message (OP-CODE = 4) is sent in lieu of an ACK for
     a response in which an error is detected.  No ACK is expected.
     Action taken by the requester and responder will vary with the
     nature of the request.
     
               REF identifies the erroneous response.
     
               ERROR-TYPE is not yet specified.
     
     
     6.1  Control Messages for PTP Connections
     
             PTP connections are set up and taken down with the
     following messages:
     
     6.1.1  [CONNECT.PTP] <NAME> <TARGET> <FLOW-SPEC> <CID.B>
     
             CONNECT.PTP (OP-CODE = 5) requests the set up (routing)
     of a PTP connection or asks for a change in the flow
     specification of a connection already routed.  Its parameters
     are:
     
               NAME (P-CODE = 1, P-LENGTH = 6) is the ST address of
               the process that originated the CONNECT.PTP (the
               ORIGIN) concatenated with a 16-bit number chosen to
               make the name unique.  An ST address is a 32-bit IP
               host address concatenated with a 32-bit EXTENSION
               identifier chosen to identify a particular process in
               the host.  The EXTENSION is provided by some higher-
               level protocol and is assumed by ST to be unique to the
               host.  For NVP use the EXTENSION identifies a
               particular telephone and is presumably a well-known
     
     
                                   -26-
     

IEN 119                      ST.DOC              7 September 1979
     
     
               quantity.
     
               TARGET (P-CODE = 2, P-LENGTH = 5) is the ST address of
               the target process.
     
               FLOW-SPEC (P-CODE = 3, P-LENGTH = 18) is a complex
               parameter that both specifies and reports on the flow
               requirements and expected delay characteristics of the
               full-duplex connection.  See Section 4.5 for further
               information.
     
               CID.B (P-CODE = 4, P-LENGTH = 2) is the connection
               identifier to be used on packets moving in the backward
               direction on the connection.
     
             CONNECT.PTP expects a response.  There are four response
     possibilities: ACCEPT.PTP, REFUSE.PTP, ACK, and ERROR-IN-REQUEST.
     Receipt of an ACK means that the agent receiving the request is
     working on it, and the requester should wait for a future ACCEPT
     or REFUSE.  ERROR-IN-REQUEST will be returned only when a format
     error is detected in the CONNECT.PTP.  Other errors, if detected,
     will elicit REFUSE messages.
     
             The processing of CONNECT messages requires care to avoid
     routing loops that could result from delays in propagating
     routing information among gateways. The example in Section 7.0
     describes in some detail the actions of agents in handling
     CONNECT requests while routing a connection.
     
     6.1.2  [ACCEPT.PTP] <NAME> <TARGET> <FLOW-SPEC> <CID.F)
     
     ACCEPT.PTP (OP-CODE = 6) is returned to indicate that the
     requirements of a CONNECT.PTP have been met or that a change in
     flow specifications has occured.  Parameters are the same as for
     CONNECT.PTP except that a CID.F (P-CODE = 5, P-LENGTH = 2) is
     returned for use on packets travelling in the forward direction.
     The FLOW-SPEC will be modified to show the accepted rate and
     accumulated delay information (See Section 4.5).
     
             ACCEPT messages expect ACK's or ERROR-IN-RESPONSE's.
     ERROR-IN-RESPONSE will be returned if an ACCEPT is sent to an
     agent that has no knowledge of the connection.  This may occur if
     an ACCEPT is generated at the same time that a DISCONNECT is
     being propagated.
     
     6.1.3  [REFUSE.PTP] <NAME> <REASON>
     
     REFUSE.PTP (OP-CODE = 7) is returned to indicate that agents have
     failed to set up a requested connection or that a previously
     established connection has been lost. REFUSE's are also returned
     to indicate routing failure, and in such a case may not end up
     
     
                                   -27-
     

IEN 119                      ST.DOC              7 September 1979
     
     
     propagating back to the origin.  TARGET's also issue REFUSE's to
     take down connections intentionally.
     
     REASON (P-CODE = 6, P-LENGTH = 2) indicates the reason for
     connection refusal.  REASON codes apply also to DISCONNECT
     messages and include the following:
     
                CODE            EXPLANATION
     
                 0       No explanation
                 1       Target refuses connection
                 2       Target does not respond
                 3       Target cannot be reached
                 4       Connection preempted
                 5       STREAM INTERVAL too short
                 6       Requested data rate cannot be handled
                 7       Connection broken due to network fault
                 8       Connection broken by ORIGIN
                 9       Conflicting FLOW-SPECs in CONF connections
     
             REFUSE's are ACK'ed and are propagated by intermediate
     agents if meaningful (i.e., the agents had tables for the
     connection).  The backward propagation of a refuse may be halted
     at an intermediate agent if an alternate route exists that has
     not been tried, and the REASON indicates that it is reasonable to
     try the alternate route.  (I.e., it does not indicate that the
     target refuses or does not respond).
     
     6.1.4  [DISCONNECT.PTP] <NAME> <REASON>
     
             DISCONNECT.PTP (OP-CODE = 8) is sent to request that a
     previously requested connection be taken down.  It can be
     generated either by the originator of the CONNECT or by an
     intermediate agent that executes a preemption or detects a fault.
     
             REASON uses the same codes as REFUSE although not all
     codes apply.
     
             DISCONNECT expects an ACK and is propagated in the
     forward direction so long as agents are encountered that know
     about the connection.
     
             A connection can be taken down either by a REFUSE or a
     DISCONNECT (or both) depending upon which end first decides to
     initiate the process. If both start within a propagation time of
     each other, neither message will reach the opposite end.
     
     
     
     
     
     
     
                                   -28-
     

IEN 119                      ST.DOC              7 September 1979
     
     
     6.2  Control Messages for CONF Connections
     
     
             CONF connections are set up and taken down with CONNECT,
     ACCEPT, REFUSE, and DISCONNECT messages, but the CONF versions of
     these messages have somewhat different parameters.  In addition,
     CONF connection setup requires that agents communicate with
     access controllers by means of TELL-ME and INFO messages.  These
     latter messages are sent as IP.ST datagrams.  The former are sent
     as ST.DG packets with CID = 0.
     
     6.2.1  [CONNECT.CONF] <NAME> <OBM> <TBM> <CID.B>
     
             CONNECT.CONF (OP-CODE = 9) requests the setup (routing)
     of a CONF connection or asks for a change in flow specifications
     of a connection already routed.  The parameters NAME and CID.B
     have the same form and interpretation as they do for CONNECT.PTP
     except that NAME is the name of the owner of the conference, not
     the originator of the CONNECT message.  The new parameters OBM
     and TBM allow the message to deal with multiple ORIGIN and TARGET
     processes.  The FLOW-SPEC for the connection is obtained from the
     access controller.
     
             OBM (P-CODE = 8, P-LENGTH = 2-9) is the ORIGIN-BIT-MAP.
     Bits set in the map identify originating processes.  When a
     CONNECT.CONF is first issued by a user process only one bit is
     set in OBM identifying the issuer.  However, as the message
     propagates, intermediate agents may find that they have other
     CONNECT.CONF messages for the same connection on hand at the same
     time.  In that case, they can merge the requests so that more
     bits become set as the message approaches its targets.
     
             TBM (P-CODE = 9, P-LENGTH = 2-9) is the TARGET-BIT-MAP.
     Bits set in the map identify the target processes.  In general,
     the user process will have set many bits in TBM when it first
     issues a CONNECT.CONF.  As the message propagates it will split
     many times, each split reducing the number of bits left set in
     TBM.  When the CONNECT.CONF's reach their targets only one bit
     will be left set in each.
     
             Since the CONNECT.CONF message does not tell its receiver
     anything about the actual identities of the target processes,
     intermediate agents must get this information, as well as the
     FLOW-SPEC, from the access controller by sending TELL-ME messages
     and receiving INFO messages in response.  The agents use the NAME
     to locate the AC, using a bit in the name to distinguish between
     a public or private AC.  The NAME is the ST address of a process
     concatenated with a 16-bit number to make the NAME unique.  It is
     proposed that the most significant bit of that 16-bit number be
     used to distinguish public from private ACs.  A zero in that bit
     would indicate a private AC and in that case, agents would send
     
     
                                   -29-
     

IEN 119                      ST.DOC              7 September 1979
     
     
     TELL-ME messages to the process address in the NAME.  In the
     public case, the agent would communicate with an AC whose address
     was known a priori to the agent.
     
     6.2.2  [ACCEPT.CONF] <NAME> <OBM> <TBM> <FLOW-SPEC> <CID.F>
     
             ACCEPT.CONF (OP-CODE = 10) is similar in function to
     ACCEPT.PTP.  NAME, FLOW-SPEC, and CID.F have the same form and
     interpretation.  OBM specifies the set of originators to which
     the ACCEPT is to be propagated.  TBM specifies the set of targets
     that have accepted the connection.  This set may be a sub-set of
     the targets requested in the CONNECT to which an ACCEPT responds.
     The FLOW-SPEC is included in the ACCEPT because it reflects the
     actual resources granted to the connection.
     
     6.2.3  [REFUSE.CONF] <NAME> <OBM> <TBM> <REASON>
     
             REFUSE.CONF (OP-CODE = 11) is similar in function to
     REFUSE.PTP.  As for ACCEPT.CONF, OBM specifies the set of
     originators to which the REFUSE is to be propagated.  TBM
     specifies the set of targets that cannot be reached, have
     refused, etc.  A single REASON applies to all the targets in the
     TBM.  If more than one REASON applies to a set of targets, as
     many REFUSE's as REASON's will be sent.
     
     6.2.4  [DISCONNECT.CONF] <NAME> <OBM> <TBM> <REASON>
     
             DISCONNECT.CONF (OP-CODE = 12) is similar in function to
     DISCONNECT.PTP.  As for REFUSE.CONF, OBM and TBM specify the sets
     of originators and targets to which the DISCONNECT applies.
     
     6.2.5  [TELL-ME] <NAME> <PART-NUM> <FLOW-SPEC-REQ>
     
             TELL-ME (OP-CODE = 13) is sent from an agent or a
     participant process to an access controller .  The AC is expected
     to return an INFO message with the requested information.  Either
     of the latter two parameters may be omitted.
     
             PART-NUM (P-CODE = 10, P-LENGTH = 2) specifies the number
     of the first participant about which information is requested.
     The response will be a participant list starting with the
     specified participant and continuing until the maximum packet
     size is reached or the list is exhausted.
     
             FLOW-SPEC-REQ (P-CODE = 11, P-LENGTH = 2) requests the AC
     to send the FLOW-SPEC for the connection.
     
     
     
     
     
     
     
                                   -30-
     

IEN 119                      ST.DOC              7 September 1979
     
     
     6.2.6  [INFO] <NAME> <STATUS> <PART-LIST> <FLOW-SPEC>
     
             INFO (OP-CODE = 14) is sent from an AC to an agent or
     participant process in response to a TELL-ME.  It provides the
     requested information.  STATUS is always present.  PART-LIST and
     FLOW-SPEC are present only when requested by the TELL-ME.
     
             STATUS (P-CODE = 12, P-LENGTH = 2) carries 2 bytes of
     information.  Byte 1 is the CONF-TYPE.  Byte 2 gives the length
     of the participant list.  The following values for CONF-TYPE are
     defined:
              Type                  Meaning
     
               0         No conference defined with this NAME
     
               1         Conference with closed participant list
     
               2         Conference with open list and password
     
               3         Conference with completely open list (no
                         password needed).
     
     
             PART-LIST (P-CODE = 13, P-LENGTH = (4m + 2)) provides a
     section of the participant list starting at the location (PART-
     NUM) requested in the TELL-ME and continuing until either the end
     of the list or packet capacity is reached.  The items in the
     PART-LIST are the ST addresses (64 bits) of the participating
     processes.  The addresses are present whether or not the
     participants are active.  The addresses are preceded by a word
     giving the number of the first participant on the list.
     
             FLOW-SPEC is the nominal FLOW-SPEC for the conference.
     
     
     7.0  AN EXAMPLE OF CONF CONNECTION SETUP
     
     
             This section is a rather detailed example of the actions
     called for by ST in setting up a connection for a conference with
     four participants. In addition to showing the control message
     flow, it also indicates the information used and retained by
     gateways in supporting the connection. For the sake of
     simplicity, it is assumed that the flow requirements are always
     met.  The ".CONF" suffix is omitted from OP-CODE's, and
     parameters such as NAME and FLOW-SPEC that are always the same
     are also omitted.  In addition, ACK's are not shown but are
     assumed to occur where required.
     
     
     
     
     
                                   -31-
     

IEN 119                      ST.DOC              7 September 1979
     
     
     
             The example uses the following network configuration:
     
     
     
              +---+                +---+                +---+
              !P3 !                !P2 !                !P1 !
              +---+                +---+                +---+
              !ST3!                !ST2!                !ST1!
              +---+                +---+                +---+
                !                    !                    !
                !                    !                    !
            +-------+  +------+  +-------+  +------+  +-------+
            ! Net A !--! G.AB !--! Net B !--! G.BC !--! Net C !
            +-------+  +------+  +-------+  +------+  +-------+
                !                                         !
                !                                         !
              +---+                                     +---+
              !ST4!                                     !AC !
              +---+                                     +---+
              !P4 !
              +---+
     
     
             Each participant (Pi) communicates through a host agent
     called "STi." The communications between the P's and their local
     ST's are written out as control messages to show the logical flow
     even though in actual implementations they might be handled very
     differently.
     
             The actions involving ST start after the participants
     have joined the conference by communicating with the access
     controller (AC) and have received TARGET-BIT-MAPs (TBMs) telling
     each Pi to which other Pi's connections are to be set up.  The
     notation "{ A, B, C }" is used to indicate a bit map with bits
     set for A, B, and C.  The participants are assumed to have joined
     in the order of their numbers.  Thus P1 got an empty TBM ({ }),
     and P4 got TBM = { P1, P2, P3 }.  According to the rules, P1
     issues no CONNECT messages, but waits for the others to connect
     to it.  The action thus begins with P2 sending:
     
     P2->ST2: [CONNECT] <OBM = { P2 }> <TBM = { P1 }> <CID.B = 3>
     
     ST2->AC: [TELL-ME] <PART-NUM = 1> <FLOW-SPEC-REQ>
     
     AC->ST2: [INFO] <PART-LIST = ADDR.P1, ADDR.P2, ADDR.P3, ADDR.P4>
                <FLOW-SPEC> <STATUS>
     
             These last two commands are executed independently by all
     agents when they first receive a CONNECT.  They will be replaced
     by the phrase "X gets info" in the following.
     
     
                                   -32-
     

IEN 119                      ST.DOC              7 September 1979
     
     
             ST2 observes that ADDR.P1 is not in its local net and
     lacking routing knowledge decides to try G.AB (the wrong
     direction).
     
     ST2->G.AB: [CONNECT] <OBM = { P2 }> <TBM = { P1 }> <CID.B = 17>
     
             G.AB gets info and decides that net C is unreachable
     except through net B from whence the CONNECT came.
     
     G.AB->ST2: [REFUSE] <OBM = { P2 }> <TBM = { P1 }>
                  <REASON = 3 (Target cannot be reached)>
     
             ST2 decides to try another gateway.
     
     ST2->G.BC: [CONNECT] <OBM = { P2 }> <TBM = { P1 }> <CID.B = 17>
     
             G.BC gets info, builds a connection entry, and sends:
     
     G.BC->ST1: [CONNECT] <OBM = { P2 }> <TBM = { P1 }> <CID.B = 100l>
     
             ST1 gets info and sends:
     
     ST1->P1: [CONNECT] <OBM = { P2 }> <TBM = { P1 }> <CID.B = 1>
     
             Since P1 has already joined the conference and recognizes
     P2 as another participant, it sends:
     
     P1->ST1: [ACCEPT] <OBM = { P2 }> <TBM = { P1 }> <CID.F = 1>
     
     ST1->G.BC: [ACCEPT] <OBM = { P2 }> <TBM = { P1 }> <CID.F = 32>
     
             At this point G.BC would have the following stored
     information (neglecting bookkeeping items such as pointers).
     
           1.  A connection block with NAME, FLOW-SPEC, and CID.IN =
               1001 (the same CID can be used for all inputs for the
               connection).  This information is retained for the life
               of the connection.  The PART-LIST used in processing
               may be discarded once an ACCEPT (or REFUSE) has been
               received and the forwarding tables have been created.
               However, since there are likely to be other CONNECT's
               to be processed, it would be efficient to keep the
               PART-LIST for a time (say several minutes).
     
     
     
     
     
     
     
     
     
     
                                   -33-
     

IEN 119                      ST.DOC              7 September 1979
     
     
           2.  Two forwarding tables, one for each packet that might
               be sent in response to an input.
     
                ITEMS                   #1              #2
     
               NET-PORT                  B               C
     
               ADDRESS                  ST2             ST1
     
               MASK.OBM                { P2 }           { }
     
               MASK.TBM                 { }            { P1 }
     
               CID.OUT                   17              32
     
     
             The principal function of the masks is to facilitate
     packet forwarding.  When a packet arrives, the following
     computation is made for each forwarding table to compute the
     output FORWARDING-BIT-MAP (FBM):
     
             FBM.OUT = FBM.IN & (MASK.OBM U MASK.TBM)
     
     If FBM.OUT has no bits set, it is not necessary to send a packet
     to the address in the table.  Otherwise a packet is sent using
     the NET-PORT, ADDRESS, and CID.OUT from the table.
     
             Having built its tables, G.BC sends:
     
     G.BC->ST2: [ACCEPT] <OBM = { P2 }> <TBM = { P1 }> <CID.F = 1001>
     
     ST2->P2: [ACCEPT] <OBM = { P2 }> <TBM = { P1 }> <CID.F = 10>
     
             At this point P2 and P1 are connected and could begin
     talking, if permitted by the higher level protocol.
     
             In connecting P3 and P4 we will assume that both initiate
     requests at essentially the same time so that they propagate
     concurrently.
     
     P3->ST3: [CONNECT] <OBM = { P3 }> <TBM = { P1, P2 }> <CID.B = 5>
     
     P4->ST4: [CONNECT] <OBM = { P4 }> <TBM = { P1, P2, P3 }>
               <CID.B = 1>
     
             ST3 and ST4 get info.  ST3 notices that P1, P2 both are
     outside the local net, but ST4 notices as well that P3 is on the
     same net as P4.
     
     They send:
     
     
     
                                   -34-
     

IEN 119                      ST.DOC              7 September 1979
     
     
     ST3->G.AB: [CONNECT] <OBM = { P3 }> <TBM = { P1, P2 }>
                 <CID.B = 135>
     
     ST4->ST3: [CONNECT] <OBM = { P4 }> <TBM = { P3 }> <CID.B = 27>
     
     ST4->G.AB: [CONNECT] <OBM = { P4 }> <TBM = { P1, P2 }>
                 <CID.B = 27>
     
             ST3 forwards the CONNECT to P3, which accepts, and ST3
     responds to ST4 with:
     
     ST3->ST4: [ACCEPT] <OBM = { P4 }> <TBM = { P3 }> <CID.F = 135>
     
             Meanwhile G.AB gets info and notices that it has two
     CONNECT's for the same NAME.  It decides to merge them and sends:
     
     G.AB->ST2: [CONNECT] <OBM = { P3, P4 }> <TBM = { P2 }>
                 <CID.B = 2356>
     
     and
     
     G.AB->G.BC: [CONNECT] <OBM = { P3, P4 }> <TBM = { P1 }>
                  <CID.B = 2356>
     
             ST2 forwards the CONNECT to P2, which accepts, and ST2
     sends:
     
     ST2->G.AB: [ACCEPT] <OBM = { P3, P4 }> <TBM = { P2 }>
                 <CID.F = 17>
     
             Now G.AB will not continue to propagate the ACCEPT
     because the CONNECT on which it is working asked for connection
     to P1 as well as P2.  It will wait for an ACCEPT or REFUSE from
     P1.
     
             G.BC  already knows about the connection to P1, but it
     does not assume that P1 will accept P3 and P4, so it propagates
     the CONNECT.
     
     G.BC->ST1: [CONNECT] <OBM = { P3, P4 }> <TBM = { P1 }>
                 <CID.B = 1001>
     
             ST1 forwards to P1, which accepts, and ST1 responds:
     
     ST1->G.BC: [ACCEPT] <OBM = { P3, P4 }> <TBM = { P1 }> <CID.F =
     32>
     
             In the latter exchange G.BC and ST1 used the same CID's
     they had used before for this connection.  If either had chosen
     to use a different CID, the newer value would supercede the
     earlier one in the forwarding table.
     
     
                                   -35-
     

IEN 119                      ST.DOC              7 September 1979
     
     
             It should be noted that the protocol could allow G.BC to
     accept the connection from P3 and P4 without forwarding the
     CONNECT to ST1 because G.BC already knows it has a connection to
     P1.  This shortcut is not taken because it denies P1 the
     information about the connection requests from P3 and P4 and the
     opportunity to refuse those connections if desired.
     
     
             To finish the setup we have:
     
     G.BC->G.AB: [ACCEPT] <OBM = { P3, P4 }> <TBM = { P1 }>
                  <CID.F = 1001>
     
             G.AB will now accept for P1 and P2.
     
     G.AB->ST3: [ACCEPT] <OBM = { P3 }> <TBM = { P1, P2 }>
                 <CID.F = 2356>
     
     G.AB->ST4: [ACCEPT] <OBM = { P4 }> <TBM = { P1, P2 }>
                 <CID.F = 2356>
     
             When ST3 and ST4 propagate the ACCEPT's to P3 and P4 the
     conference connection is complete.
     
             At this point the forwarding tables in G.BC are the
     following:
     
           ITEM               #1              #2              #3
     
         NET-PORT              B               C               B
     
         ADDRESS              ST2             ST1             G.AB
     
         MASK.OBM           { P2 }            { }          { P3, P4 }
     
         MASK.TBM             { }            { P1 }           { }
     
         CID.OUT              17              32              2356
     
     
             If at some later time G.BC should decide to preempt the
     connection, it would issue one message for each forwarding table
     entry:
     
     G.BC->ST2: [REFUSE] <OBM = { P2 }> <TBM = { P1 }>
                 <REASON = 4 (Connection preempted)>
     
     G.BC->ST1: [DISCONNECT] <OBM = { P2, P3, P4 }> <TBM = { P1 }>
                 <REASON = 4 (Connection preempted)>
     
     
     
     
                                   -36-
     

IEN 119                      ST.DOC              7 September 1979
     
     
     G.BC->G.AB: [REFUSE] <OBM = { P3, P4 }> <TBM = { P1 }>
                 <REASON = 4 (Connection preempted)>
     
             Having issued these messages and received ACKs in
     response (or timed out in the absence of an ACK), the gateway can
     delete the table entries and reclaim the CID for future use.  The
     REFUSE sent to G.AB would, of course, be propogated to ST3 and
     ST4.
     
     
     8.0  AREAS NEEDING FURTHER WORK
     
             This document does not completely specify the protocol.
     Further work is needed to specify error conditions and their
     handling.  The FLOW-SPEC parameter is not yet laid out in detail.
     Rerouting has not been thought through sufficiently.  The whole
     area of routing strategies and the information to be exchanged
     among gateways has not been given much consideration.  There is
     also a need for agents to exchange information (not yet
     specified) about local net resources.  For example, if agents are
     to make use of local net multi-addressing capability, the
     selection of a CID for a connection is no longer at the
     discretion of an individual agent.  A convention is needed to
     avoid conflicting use of CID's as well as requesting duplicate
     resources to serve a CONF connection.  The CONNECT control
     message needs to be extended to allow agents to indicate local
     net resources that are already committed to a CONF connection.
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
                                   -37-