Tech-invite3GPPspaceIETFspace
959493929190898887868584838281807978777675747372717069686766656463626160595857565554535251504948474645444342414039383736353433323130292827262524232221201918171615141312111009080706050403020100
in Index   Prev   Next

RFC 1190

Experimental Internet Stream Protocol: Version 2 (ST-II)

Pages: 148
Obsoleted by:  1819
Part 3 of 6 – Pages 50 to 74
First   Prev   Next

ToP   noToC   RFC1190 - Page 50   prevText
            Restarted bit specifying that the ST agent has been
            restarted recently.  The HelloTimer must appear to be
            incremented every millisecond whether a HELLO message is
            sent or not, but it is allowable for an ST agent to create a
            new HelloTimer only when it sends a HELLO message.  The
            HelloTimer wraps around to zero after reaching the maximum
            value.  Whenever an ST agent suffers a catastrophic event
            that may result in it losing ST state information, it must
            reset its HelloTimer to zero and must set the Restarted bit
            for the following HelloTimerHoldDown seconds.

            An ST agent must send HELLO messages to its neighbor with a
            period shorter than the smallest RecoveryTimeout parameter
            of the FlowSpecs of all the active streams that pass between
            the two agents, regardless of direction.  This period must
            be smaller by a factor, called HelloLossFactor, which is at
            least as large as the greatest number of consecutive HELLO
            messages that could credibly be lost while the communication
            between the two ST agents is still viable.

            An ST agent may send simultaneous HELLO messages to all its
            neighbors at the rate necessary to support the smallest
            RecoveryTimeout of any active stream.  Alternately, it may
            send HELLO messages to different neighbors independently at
            different rates corresponding to RecoveryTimeouts of
            individual streams.

            The agent that receives a HELLO message expects to receive
            at least one new HELLO message from a neighbor during the
            RecoveryTimeout of every active stream through that
            neighbor.  It can detect duplicate or delayed HELLO messages
            by saving the HelloTimer field of the most recent valid
            HELLO message from that neighbor and comparing it with the
            HelloTimer field of incoming HELLO messages.  It will only
            accept an incoming HELLO message from that neighbor if it
            has a HelloTimer field that is greater than the most recent
            valid HELLO message by the time elapsed since that message
            was received plus twice the maximum likely delay variance
            from that neighbor.  If the ST agent does not receive a
            valid HELLO message within the RecoveryTimeout of a stream,
            it must assume that the neighboring ST agent or the
            communication link between the two has failed and it must
            initiate stream recovery activity.

            Furthermore, if an ST agent receives a HELLO message that
            contains the Restarted bit set, it must assume that the
            sending ST agent has lost its ST state.  If it shares
            streams with that neighbor, it must initiate stream recovery
            activity.  If it does not share streams with that neighbor,
            it should not attempt to create one until that
ToP   noToC   RFC1190 - Page 51
            bit is no longer set.  If an ST agent receives a CONNECT
            message from a neighbor whose Restarted bit is still set, it
            must respond with ERROR-IN-REQUEST with the appropriate
            reason code (RemoteRestart).  If it receives a CONNECT
            message while its own Restarted bit is set, it must respond
            with ERROR-IN-REQUEST with the appropriate reason code
            (RestartLocal).


         3.7.1.3.         Subset

            This failure detection mechanism subsets by reducing the
            complexity of the timing and decisions.  A subsetted ST
            agent sends HELLO messages to all its ST neighbors
            regardless of whether there is an active ST stream between
            them or not.  The RecoveryTimeout parameter of the FlowSpec
            is ignored and is assumed to be the DefaultRecoveryTimeout.
            Note that this implies that a REFUSE should be sent for all
            CONNECT or CHANGE messages whose RecoveryTimeout is less
            than DefaultRecoveryTimeout.  An ST agent will accept an
            incoming HELLO message if it has a HelloTimer field that is
            greater than the most recent valid HELLO message by
            DefaultHelloFactor times the time elapsed since that message
            was received.


      3.7.2.        Failure Recovery

         Streams can fail from various causes;  an ST agent can break, a
         network can break, or an ST agent can intentionally break a
         stream in order to give the stream's resources to a higher
         precedence stream.  We can envision several approaches to
         recovery of broken streams, and we consider the one described
         here the simplest and therefore the most likely to be
         implemented and work.

         If an intermediate agent fails or a network or part of a
         network fails, the previous-hop agent and the various next-hop
         agents will discover the fact by the failure detection
         mechanism described in Section 3.7.1 (page 48).  An ST agent
         that intentionally breaks a stream obviously knows of the
         event.

         The recovery of an ST stream is a relatively complex and time
         consuming effort because it is designed in a general manner to
         operate across a large number of networks with diverse
         characteristics.  Therefore, it may require information to be
         distributed widely, and may require relatively long timers.  On
         the other hand, since a network is a homogeneous system,
         failure recovery in the network may be a relatively faster and
         simpler operation.  Therefore an ST agent that detects a
         failure should attempt to fix the network failure before
ToP   noToC   RFC1190 - Page 52
         attempting recovery of the ST stream.  If the stream that
         existed between two ST agents before the failure cannot be
         reconstructed by network recovery mechanisms alone, then the ST
         stream recovery mechanism must be invoked.

         If stream recovery is necessary, the different ST agents may
         need to perform different functions, depending on their
         relation to the failure.

         An intermediate agent that breaks the stream intentionally
         sends DISCONNECT messages with the appropriate reason code
         (StreamPreempted) toward the affected targets.  If the
         NoRecovery option is selected, it sends a REFUSE message with
         the appropriate reason code(StreamPreempted) toward the origin.
         If the NoRecovery option is not selected, then this agent
         attempts recovery of the stream, as described below.

         A host agent that is a target of the broken stream or is itself
         the next-hop of the failed component should release resources
         that are allocated to the stream, but should maintain the
         internal state information describing the stream.  It should
         inform any next higher protocol of the failure.  It is
         appropriate for that protocol to expect that the stream will be
         fixed shortly by some alternate path and so maintain, for some
         time period, whatever information in the ST layer, the next
         higher layer, and the application is necessary to reactivate
         quickly entries for the stream as the alternate path develops.
         The agent should use a timeout to delete all the stream
         information in case the stream cannot be fixed in a reasonable
         time.

         An intermediate agent that is a next-hop of a failure that was
         not due to a preemption should first verify that there was a
         failure.  It can do this using STATUS messages to query its
         upstream neighbor.  If it cannot communicate with that
         neighbor, then it should first send a REFUSE message with the
         appropriate reason code of "failure" to the neighbor to speed
         up the failure recovery in case the hop is unidirectional,
         i.e., the neighbor can hear the agent but the agent cannot hear
         the neighbor.  The ST agent detecting the failure must then
         send DISCONNECT messages with the same reason code toward the
         targets.  The intermediate agents process this DISCONNECT
         message just like the DISCONNECT that tears down the stream.
         However, a target ST agent that receives a DISCONNECT message
         with the appropriate reason code (StreamPreempted, or
         "failure") will maintain the stream state and notify the next
         higher protocol of the failure.  In effect, these DISCONNECT
         messages tear down the stream from the point of the failure to
         the targets, but inform the targets that the stream may be
         fixed shortly.
ToP   noToC   RFC1190 - Page 53
         An ST agent that is the previous-hop before the failed
         component first verifies that there was a failure by querying
         the downstream neighbor using STATUS messages.  If the neighbor
         has lost its state but is available, then the ST agent may
         reconstruct the stream if the NoRecovery option is not
         selected, as described below.  If it cannot communicate with
         the next-hop, then the agent detecting the failure releases any
         resources that are dedicated exclusively to sending data on the
         broken branch and sends a DISCONNECT message with the
         appropriate reason code ("failure") toward the affected
         targets.  It does so to speed up failure recovery in case the
         communication may be unidirectional and this message might be
         delivered successfully.

         If the NoRecovery option is selected, then the ST agent that
         detects the failure sends a REFUSE message with the appropriate
         reason code ("failure") to the previous-hop.  If it is breaking
         the stream intentionally, it sends a REFUSE message with the
         appropriate reason code (StreamPreempted) to the previous-hop.
         The TargetList in these messages contains all the targets that
         were reached through the broken branch.  Multiple REFUSE
         messages may be required if the PDU is too long for the MTU of
         the intervening network.  The REFUSE message is propagated all
         the way to the origin, which can attempt recovery of the stream
         by sending a new CONNECT to the affected targets.  The new
         CONNECT will be treated by intermediate ST agents as an
         addition of new targets into the established stream.

         If the NoRecovery option is not selected, the ST agent that
         breaks the stream intentionally or is the previous-hop before
         the failed component can attempt recovery of the stream.  It
         does so by issuing a new CONNECT message to the affected
         targets.  If the ST agent cannot find new routes to some
         targets, or if the only route to some targets is through the
         previous-hop, then it sends one or more REFUSE messages to the
         previous-hop with the appropriate reason code ("failure" or
         StreamPreempted) specifying the affected targets in the
         TargetList.  The previous-hop can then attempt recovery of the
         stream by issuing a CONNECT to those targets.  If it cannot
         find an appropriate route, it will propagate the REFUSE message
         toward the origin.

         Regardless of which agent attempts recovery of a damaged
         stream, it will issue one or more CONNECT messages to the
         affected targets.  These CONNECT messages are treated by
         intermediate ST agents as additions of new targets into the
         established stream.  The FlowSpecs of the new CONNECT messages
         should be the same as the ones contained in the most recent
         CONNECT or CHANGE messages that the ST agent had sent toward
         the affected targets when the stream was operational.
ToP   noToC   RFC1190 - Page 54
         The reconstruction of a broken stream may not proceed smoothly.
         Since there may be some delay while the information concerning
         the failure is propagated throughout an internet, routing
         errors may occur for some time after a failure.  As a result,
         the ST agent attempting the recovery may receive REFUSE or
         ERROR-IN-REQUEST messages for the new CONNECTs that are caused
         by internet routing errors.  The ST agent attempting the
         recovery should be prepared to resend CONNECTs before it
         succeeds in reconstructing the stream.  If the failure
         partitions the internet and a new set of routes cannot be found
         to the targets, the REFUSE messages will eventually be
         propagated to the origin, which can then inform the application
         so it can decide whether to terminate or to continue to attempt
         recovery of the stream.

         The new CONNECT may at some point reach an ST agent downstream
         of the failure before the DISCONNECT does.  In this case, the
         agent that receives the CONNECT is not yet aware that the
         stream has suffered a failure, and will interpret the new
         CONNECT as resulting from a routing failure.  It will respond
         with an ERROR-IN-REQUEST message with the appropriate reason
         code (StreamExists).  Since the timeout that the ST agents
         immediately preceding the failure and immediately following the
         failure are approximately the same, it is very likely that the
         remnants of the broken stream will soon be torn down by a
         DISCONNECT message with the appropriate reason code
         ("failure").  Therefore, the ST agent that receives the ERROR-
         IN-REQUEST message with reason code (StreamExists) should
         retransmit the CONNECT message after the ToConnect timeout
         expires.  If this fails again, the request will be retried for
         NConnect times.  Only if it still fails will the ST agent send
         a REFUSE message with the appropriate reason code (RouteLoop)
         to its previous-hop.  This message will be propagated back to
         the ST agent that is attempting recovery of the damaged stream.
         That ST agent can issue a new CONNECT message if it so chooses.
         The REFUSE is matched to a CONNECT message created by a
         recovery operation through the LnkReference field in the
         CONNECT.

         ST agents that have propagated a CONNECT message and have
         received a REFUSE message should maintain this information for
         some period of time.  If an agent receives a second CONNECT
         message for a target that recently resulted in a REFUSE, that
         agent may respond with a REFUSE immediately rather than
         attempting to propagate the CONNECT.  This has the effect of
         pruning the tree that is formed by the propagation of CONNECT
         messages to a target that is not reachable by the routes that
         are selected first.  The tree will pass through any given ST
         agent only once, and the stream setup phase will be completed
         faster.
ToP   noToC   RFC1190 - Page 55
         The time period for which the failure information is maintained
         must be consistent with the expected lifetime of that
         information.  Failures due to lack of reachability will remain
         relevant for time periods large enough to allow for network
         reconfigurations or repairs.  Failures due to routing loops
         will be valid only until the relevant routing information has
         propagated, which can be a short time period.  Lack of
         bandwidth resulting from over-allocation will remain valid
         until streams are terminated, which is an unpredictable time,
         so the time that such information is maintained should also be
         short.

         If a CONNECT message reaches a target, the target should as
         efficiently as possible use the state that it has saved from
         before the stream failed during recovery of the stream.  It
         will then issue an ACCEPT message toward the origin.  The
         ACCEPT message will be intercepted by the ST agent that is
         attempting recovery of the damaged stream, if not the origin.
         If the FlowSpec contained in the ACCEPT specifies the same
         selection of parameters as were in effect before the failure,
         then the ST agent that is attempting recovery will not
         propagate the ACCEPT.  If the selections of the parameters are
         different, then the agent that is attempting recovery will send
         the origin a NOTIFY message with the appropriate reason code
         (FailureRecovery) that contains a FlowSpec that specifies the
         new parameter values.  The origin may then have to change its
         data generation characteristics and the stream's parameters
         with a CHANGE message to use the newly recovered subtree.


         3.7.2.1.         Subset

            Subsets of this mechanism may reduce the functionality in
            the following ways.  A host agent might not retain state
            describing a stream that fails with a DISCONNECT message
            with the appropriate reason code ("failure" or
            StreamPreempted).

            An agent might force the NoRecovery option always to be set.
            In this case, it will allow the option to be propagated in
            the CONNECT message, but will propagate the REFUSE message
            with the appropriate reason code ("failure" or
            StreamPreempted) without attempting recovery of the damaged
            stream.

            If an ST agent allows stream recovery and attempts recovery
            of a stream, it might choose a FlowSpec to specify exactly
            the current values of the parameters, with no ranges or
            options.
ToP   noToC   RFC1190 - Page 56
      3.7.3.        A Group of Streams

         There may be a need to associate related streams.  The Group
         mechanism is simply an association technique that allows ST
         agents to identify the different streams that are to be
         associated.  Streams are in the same Group if they have the
         same Group Name in the GroupName field of the (R)Group
         parameter.  At this time there are no ST control messages that
         modify Groups.  Group Names have the same format as stream
         Names, and can share the same name space.  A stream that is a
         member of a Group can specify one or more (Subgroup Identifier,
         Relation) tuples.  The Relation specifies how the members of
         the Subgroup of the Group are related.  The Subgroups
         Identifiers need only be unique within the Group.

         Streams can be associated into Groups to support activities
         that deal with a number of streams simultaneously.  The
         operation of Groups of streams is a matter for further study,
         and this mechanism is provided to support that study.  This
         mechanism allows streams to be identified as belonging to a
         given Group and Subgroup, but in order to have any effect, the
         behavior that is expected of the Relation must be implemented
         in the ST agents.  Possible applications for this mechanism
         include the following:

          o  Associating streams that are part of a floor-controlled
             conference.  In this case, only one origin can send data
             through its stream at any given time.  Therefore, at any
             point where more than one stream passes through a branch
             or network, only enough bandwidth for one stream needs
             to be allocated.

          o  Associating streams that cannot exist independently.  An
             example of this may be the various streams that carry
             the audio, video, and data components of a conference,
             or the various streams that carry data from the
             different participants in a conference.  In this case,
             if some ST agent must preempt more than a single stream,
             and it has selected any one of the streams so
             associated, then it should also preempt the rest of the
             members of that Subgroup rather than preempting any
             other streams.

          o  Associating streams that must not be completed
             independently.  This example is similar to the preceding
             one, but relates to the stream setup phase.  In this
             example, any single member of a Subgroup of streams need
             not be completed unless the rest are also completed.
             Therefore, if one stream becomes blocked, all the others
             will also be blocked.  In this case, if there are not
             enough resources to support all the conferences that are
             attempted, some number of the conferences will complete
ToP   noToC   RFC1190 - Page 57
             and other will be blocked, rather than all conferences
             be partially completed and partially blocked.

         This document assumes that the creation and membership of the
         Group will be managed by the next protocol above ST, with the
         assistance of ST.  For example, the next higher protocol
         would request ST to create a unique Group Name and a set of
         Subgroups with specified characteristics.  The next higher
         protocol would distribute this information to the other
         participants that were to be members of the Group.  Each
         would transfer the Group Name, Subgroups, and Relations to
         the ST layer, which would simply include them in the stream
         state.


         3.7.3.1.         Group Name Generator

            This facility is provided so that an application or higher
            layer protocol can obtain a unique Group Name from the ST
            layer.  This is a mechanism for the application to request
            the allocation of a Group Name that is independent of the
            request to create a stream.  The Group Name is used by the
            application or higher layer protocol when creating the
            streams that are to be part of a group.  All that is
            required is a function of the form:

               AllocateGroupName()
                  -> result, GroupName

            A corresponding function to release a Group Name is also
            desirable;  its form is:

               ReleaseGroupName( GroupName )
                  -> result


         3.7.3.2.         Subset

            Since Groups are currently intended to support
            experimentation, and it is not clear how best to use them,
            it is appropriate for an implementation not to support
            Groups.  At this time, a subsetted ST agent may ignore the
            Group parameter.  It is expected that in the future, when
            Groups transition from being an experimental concept to an
            operational one, it may be the case that such subsetting
            will no longer be acceptable.  At that time, a new
            subsetting option may be defined.
ToP   noToC   RFC1190 - Page 58
      3.7.4.        HID Negotiation

         Each data packet must carry a value to identify the stream to
         which it belongs, so that forwarding can be performed.
         Conceptually, this value could be the Name of the stream.  A
         shorthand identifier is desirable for two reasons.  First,
         since each data packet must carry this identifier, network
         bandwidth efficiency suggests that it be as small as
         possible.  This is particularly important for applications
         that use small data packets, and that use low bandwidth
         networks, such as voice across packet radio networks.
         Second, the operation of mapping this identifier into a data
         object that contains the forwarding information must be
         performed at each intermediate ST agent in the stream.  To
         minimize delay and processing overhead, this operation should
         be as efficient as possible.  Most likely, this identifier
         will be used to index into an internal table.  To meet these
         goals, ST has chosen to use a 16-bit hop-by-hop identifier
         (HID).  It is large enough to handle the foreseen number of
         streams during the expected life of the protocol while small
         enough not to preclude its use as a forwarding table index.
         Note, however, that HID 0 is reserved for control messages,
         and that HIDs 1-3 are also reserved for future use.

         When ST makes use of multicast ability in networks that
         provide it, a data packet multicast by an ST agent will be
         received identically by several next-hop ST agents.  In a
         multicast environment, the HID must be selected either by
         some network-wide mechanism that selects unique identifiers,
         or it must be selected by the sender of the CONNECT message.
         Since we feel any network-wide mechanism is outside the scope
         of this protocol, we propose that the previous-hop agent
         select the HID and send it in the CONNECT message (with the
         HID Field option set, see Section 3.6.1 (page 44)) subject to
         the approval of the next-hop agents.  We call this "HID
         negotiation".

         As an origin ST agent is creating a stream or as an
         intermediate agent is propagating a CONNECT message, it must
         make a routing decision to determine which targets will be
         reached through which next-hop ST agents.  In some cases,
         several next-hops can be reached through a network that
         supports multicast delivery.  If so, those next-hops will be
         made members of a multicast group and data packets will be
         sent to the group.  Different CONNECT messages are sent to
         the several next-hops even if the data packets will be sent
         to the multicast group, because the CONNECT messages contain
         different TargetLists and are acknowledged and accepted
         separately.  However, the HID contained by the different
         CONNECT message must be identical.  The ST agent selects a
         16-bit quantity to be the HID and inserts it into each
ToP   noToC   RFC1190 - Page 59
         CONNECT message that is then sent to the appropriate
         next-hop.

         The next-hop agents that receive the CONNECT messages must
         propagate the CONNECT messages toward the targets, but must
         also look at the HID and decide whether they can approve it.
         An ST agent can only receive data packets with a given HID if
         they belong to a single stream.  If the ST agent already has
         an established stream that uses the proposed HID, this is a
         HID collision, and the agent cannot approve the HID for the
         new stream.  Otherwise the agent can approve the HID.  If it
         can approve the HID, then it must make note of that HID and
         it must respond with a HID-APPROVE message (unless it can
         immediately respond with an ERROR-IN-REQUEST or a REFUSE).
         If it cannot approve the HID then it must respond with a
         HID-REJECT message.

         An agent that sends a CONNECT message with the H bit set
         awaits its acknowledgment message (which could be a
         HID-ACCEPT, HID-REJECT, or an ERROR-IN-REQUEST) from the
         next-hops independently of receiving ACCEPT messages.  If it
         does not receive an acknowledgment within timeout ToConnect,
         it will resend the CONNECT.  If each next-hop agent responds
         with a HID-ACCEPT, this implies that they have each approved
         of the HID, so it can be used for all subsequent data
         packets.  If one or more next-hops respond with an
         HID-REJECT, then the agent that selected the HID must select
         another HID and send it to each next-hop in a set of
         HID-CHANGE messages.  The next-hop agents must respond to
         (and thus acknowledge) these HID-CHANGE messages with either
         a HID-ACCEPT or a HID-REJECT (or, in the case of an error, an
         ERROR-IN-REQUEST, or a REFUSE if the next-hop agent wants to
         abort the HID negotiation process after rejecting NHIDAbort
         proposed HIDs).  If the agent does not receive such a
         response within timeout ToHIDChange, it will resend the
         HID-CHANGE up to NHIDChange times.  If any next-hop agents
         respond with a REFUSE message that specifies all the targets
         that were included in the corresponding CONNECT, then that
         next-hop is removed from the negotiation.  The overall
         negotiation is complete only when the agent receives a
         HID-ACCEPT to the same proposed HID from all the next-hops
         that do not respond with an ERROR-IN-REQUEST or a REFUSE.

         This negotiation may continue an indeterminate length of
         time.  In fact, the CONNECT messages could propagate to the
         targets and their ACCEPT messages may potentially propagate
         back to the origin before the negotiation is complete.  If
         this were permitted, the origin would not be aware of the
         incomplete negotiation and could begin to send data packets.
         Then the agent that is attempting to select a HID would have
         to discard any data rather than sending it to the next-hops
         since it might not have a valid HID to send with the data.
ToP   noToC   RFC1190 - Page 60
         To prevent this situation, an ACCEPT should not be propagated
         back to the previous-hop until the HID negotiation with the
         next-hops has been completed.

         Although it is possible that the negotiation extends for an
         arbitrary length of time, we consider this to be very
         unlikely.  Since the HID is only relevant across a single
         hop, we can estimate the probability that a randomly selected
         HID will conflict with the HID of an established stream.
         Consider a stream in which the hop from an ST agent to ten
         next-hop agents is through the multicast facility of a given
         network.  Assume also that each of the next-hop agents
         participates in 1000 other streams, and that each has been
         created with a different HID.  A randomly selected 16-bit HID
         will have a probability of greater than 85.9% of succeeding
         on the first try, 98.1% of succeeding on the second, and
         99.8% of succeeding on the third.  We therefore suggest that
         a 16-bit HID space is sufficiently large to support ST until
         better multicast HID selection procedures, e.g., HID servers,
         can be deployed.

         An obvious way to select the HID is for the ST agents to use
         a random number generator as suggested above.  An alternate
         mechanism is for the intermediate agents to use the HID
         contained in the incoming CONNECT message for all the
         outgoing CONNECT messages, and generate a random number only
         as a second choice.  In this case, the origin ST agent would


          Agent 3                      Agent B

      1.     +-> CONNECT B -------------->+
                 <RVLId=0><SVLId=32>      |
                 <Ref=315><HID=5990>      V
      2.             (Check HID Table, 5990 busy, 6000-11 unused)
                                          V
      3.     +<- HID-REJECT --------------+
             |   <RVLId=32><SVLId=45>
             |   <Ref=315><HID=5990>
             V   <FreeHIDs=5990:0000FFF0>
      4.     +-> HID-CHANGE  ------------>+
                 <RVLId=45><SVLId=32>     |
                 <Ref=320><HID=6000>      V
      5.             (Check HID Table, 6000 (still) available)
                                          V
      6.     +<- HID-APPROVE -------------+
                 <RVLId=32><SVLId=45>
                 <Ref=320><HID=6000>

      7.     (Both parties have now agreed to use HID 6000)

         Figure 18.  Typical HID Negotiation (No Multicasting)
ToP   noToC   RFC1190 - Page 61
         be responsible for generating the HID, and the same HID could
         be propagated for the entire stream.  This approach has the
         marginal advantage that the HID could be created by a higher
         layer protocol that might have global knowledge and could
         select small, globally unique HIDs for all the streams.  While
         this is possible, we leave it for further study.


       Agent 2                           Agent C        Agent D

   1.    +->+-> CONNECT ---------------------------------->+
            |   <RVLId=0><SVLId=26>                        |
            |   <Ref=250><HID=4824>                        |
            V   <Mcast=224.1.18.216,01:00:5E:01:12:d8>     |
   2.       +-> CONNECT --------------------+              |
                <RVLId=0><SVLId=25>         |              |
                <Ref=252><HID=4824>         |              V
   3.           <Mcast=224.1.18.216,        V      (Check HID Table)
   4.            01:00:5E:01:12:d8> (Check HID Table)  (4824 ok)
                                        (4824 busy)  (4800-4809 ok)
                                      (4800-4820 ok)       |
                                            V              |
   5.       +<- HID-REJECT -----------------+              |
            |   <RVLId=25><SVLId=54>                       |
            |   <Ref=252><HID=4824>                        |
            V   <FreeHIDs=4824:FFFFF800>                   V
   6.    +<-+<- HID-APPROVE -------------------------------+
         |      <RVLId=26><SVLId=64>
         |      <Ref=250><HID=4824>
         V      <FreeHIDs=4824:FFC00080>
         (find common HID 4800)
         V
   7.    +->+-> HID-CHANGE ------------------------------->+
            |   <RVLId=64><SVLId=26>                       |
            V   <Ref=253><HID=4800>                        |
   8.       +-> HID-CHANGE ---------------->+              |
                <RVLId=54><SVLId=25>        |              V
   9.           <Ref=254><HID=4800>         V      (Check HID Table)
   10.                              (Check HID Table)   (4800 ok)
                                      (4800-4820 ok) (4800-4809 ok)
                                            V              |
   11.      +<- HID-APPROVE ----------------+              |
            |   <RVLId=25><SVLId=54>                       |
            |   <Ref=254><HID=4800>                        |
            V   <FreeHIDs=4800:7FFFF800>                   V
   12.   +<-+<- HID-APPROVE -------------------------------+
         |      <RVLId=26><SVLId=64>
         |      <Ref=253><HID=4800>
         V      <FreeHIDs=4800:7FC00080>
   13.   (all parties have now agreed to use HID 4800)

                 Figure 19.  Multicast HID Negotiation
ToP   noToC   RFC1190 - Page 62
      Agent 2                  Agent C        Agent D     Agent 3

  1.   +----> CONNECT B ------------------------------------>+
              <RVLId=0><SVLId=24>                            V
  2.          <Ref=260><HID=4800>                    (Check HID Table)
              <Mcast=224.1.18.216,             (4800 busy, 4801-4810 ok)
               01:00:5E:01:12:d8>                            V
  3.   +<---- HID-REJECT <-----------------------------------+
       |      <RVLId=24><SVLId=33>
       |      <Ref=260><HID=4824>
       V      <FreeHIDs=4824:7FE00000>
  4.   (find common HID 4810)
       V
  5.   +->+-> HID-CHANGE ----------------------------------->+
          |   <RVLId=33><SVLId=24>                           |
          V   <Ref=262><HID=4810>                            |
  6.      +-> HID-CHANGE-ADD ------------------->+           |
          |   <RVLId=64><SVLId=26>               |           V
  7.      V   <Ref=263><HID=4810>                |   (Check HID Table)
  8.      +-> HID-CHANGE-ADD ---->+              |     (4801-4815 ok)
              <RVLId=54><SVLId=25>|              V           |
  9.          <Ref=265><HID=4810> V      (Check HID Table)   |
  10.                     (Check HID Table) (4810 busy)      |
                            (4801-4812 ok) (4801-4807 ok)    |
                                  V              |           |
  11.     +<- HID-APPROVE <-------+              |           |
          |   <RVLId=25><SVLId=54>               |           |
          |   <Ref=265><HID=4810>                |           |
          V   <FreeHIDs=4810:7FD8000>            V           |
  12.     +<- HID-REJECT <-----------------------+           |
          |   <RVLId=26><SVLId=64>                           |
          |   <Ref=263><HID=4810>                            |
          V   <FreeHIDs=4810:7F000000>                       V
  13.  +<-+<- HID-APPROVE <----------------------------------+
       |      <RVLId=24><SVLId=33>
       |      <Ref=262><HID=4810>
       V      <FreeHIDs=4810:7FDF0000>
  14.  +->+-> HID-CHANGE-DELETE ---------------------------->+
       |  |   <RVLId=33><SVLId=24>                           |
       |  V   <Ref=266><HID=4810>                            |
  15.  |  +-> HID-CHANGE-DELETE ->+                          |
       |      <RVLId=54><SVLId=25>|                          |
       |      <Ref=268><HID=4810> V                          |
  16.  |  +<- HID-APPROVE --------+                          |
       |      <RVLId=25><SVLId=54>                           |
       |      <Ref=268><HID=0>                               V
  17.  |  +<- HID-APPROVE -----------------------------------+
       |      <RVLId=24><SVLId=33>
       V      <Ref=266><HID=0>
  18.  (find common HID 4801)

                Figure 20.  Multicast HID Re-Negotiation (part 1)
ToP   noToC   RFC1190 - Page 63
      Agent 2                  Agent C        Agent D     Agent 3

  18.  (find common HID 4801)
       V
  19.  +->+-> HID-CHANGE ----------------------------------->+
          |   <RVLId=33><SVLId=24>                           |
          V   <Ref=270><HID=4801>                            |
  20.     +-> HID-CHANGE-ADD ------------------->+           |
          |   <RVLId=64><SVLId=26>               |           V
  21.     V   <Ref=273><HID=4801>                |   (Check HID Table)
  22.     +-> HID-CHANGE-ADD ---->+              |     (4801-4815 ok)
              <RVLId=54><SVLId=25>|              V           |
  23.         <Ref=274><HID=4801> V      (Check HID Table)   |
  24.                     (Check HID Table)(4801-4807 ok)    |
                            (4801-4812 ok)       |           |
                                  V              |           |
  25.     +<- HID-APPROVE <-------+              |           |
          |   <RVLId=25><SVLId=54>               |           |
          |   <Ref=274><HID=4801>                |           |
          V   <FreeHIDs=4801:3FF80000>           V           |
  26.     +<- HID-APPROVE <----------------------+           |
          |   <RVLId=26><SVLId=64>                           |
          |   <Ref=273><HID=4801>                            |
          V   <FreeHIDs=4801:3F000000>                       V
  27.  +<-+<- HID-APPROVE <----------------------------------+
       |      <RVLId=24><SVLId=33>
       |      <Ref=270><HID=4801>
       V      <FreeHIDs=4801:3FFF0000>
  28.  (switch data stream to HID 4801, drop 4800)
       V
  29.  +->+-> HID-CHANGE-DELETE ---------------->+
          |   <RVLId=64><SVLId=26>               |
          V   <Ref=275><HID=4800>                |
  30.     +-> HID-CHANGE-DELETE ->+              |
              <RVLId=54><SVLId=25>|              |
              <Ref=277><HID=4800> V              |
  31.  +<-+<- HID-APPROVE --------+              |
       |      <RVLId=25><SVLId=54>               |
       V      <Ref=277><HID=0>                   V
  32.  +<-+<- HID-APPROVE -----------------------+
       |      <RVLId=26><SVLId=64>
       V      <Ref=275><HID=0>
       (all parties have now agreed to use HID 4801)

                Figure 20.  Multicast HID Re-Negotiation (part 2)
ToP   noToC   RFC1190 - Page 64
         3.7.4.1.         Subset

            The above mechanism can operate exactly as described even if
            the ST agents do not all use the entire 16 bits of the HID.
            A low capacity ST agent that cannot support a large number
            of simultaneous streams may use only some of the bits in the
            HID, say for example the low order byte.  This may allow
            this disadvantaged agent to use smaller internal data
            structures at the expense of causing HID collisions to occur
            more often.  However, neither the disadvantaged agent's
            previous-hop nor its next-hops need be aware of its
            limitations.  In the HID negotiation, the negotiators still
            exchange a 16-bit quantity.


      3.7.5.        IP Encapsulation of ST

         ST packets may be encapsulated in IP to allow them to pass
         through routers that don't support the ST Protocol.  Of course,
         ST resource management is precluded over such a path, and
         packet overhead is increased by encapsulation, but if the
         performance is reasonably predictable this may be better than
         not communicating at all.  IP encapsulation may also be
         required either for enhanced security (see Section 3.7.8 (page
         67)) or for user-space implementations of ST in hosts that
         don't allow demultiplexing on the IP Version Number field (see
         Section 4 (page 75)), but do allow access to raw IP packets.

         IP-encapsulated ST packets begin with a normal IP header.  Most
         fields of the IP header should be filled in according to the
         same rules that apply to any other IP packet.  Three fields of
         special interest are:

          o  Protocol is 5 to indicate an ST packet is enclosed, as
             opposed to TCP or UDP, for example.  The assignment of
             protocol 5 to ST is an arranged coincidence with the
             assignment of IP Version 5 to ST [18].

          o  Destination Address is that of the next-hop ST agent.
             This may or may not be the target of the ST stream.
             There may be an intermediate ST agent to which the
             packet should be routed to take advantage of service
             guarantees on the path past that agent.  Such an
             intermediate agent would not be on a directly-connected
             network (or else IP encapsulation wouldn't be needed),
             so it would probably not be listed in the normal routing
             table.  Additional routing mechanisms, not defined here,
             will be required to learn about such agents.

          o  Type-of-Service may be set to an appropriate value for
             the service being requested (usually low delay, high
ToP   noToC   RFC1190 - Page 65
         throughput, normal reliability).  This feature is not
         implemented uniformly in the Internet, so its use can't be
         precisely defined here.

         Since there can be no guarantees made about performance across
         a normal IP network, the ST agent that will encapsulate should
         modify the Desired FlowSpec parameters when the stream is being
         established to indicate that performance is not guaranteed.  In
         particular, Reliability should be set to the minimum value
         (1/256), and suitably large values should be added to the
         Accumulated Mean Delay and Accumulated Delay Variance to
         reflect the possibility that packets may be delayed up to the
         point of discard when there is network congestion.  A suitably
         large value is 255 seconds, the maximum packet lifetime as
         defined by the IP Time-to-Live field.

         IP encapsulation adds little difficulty for the ST agent that
         receives the packet.  The IP header is simply removed, then the
         ST header is processed as usual.

         The more difficult part is during setup, when the ST agent must
         decide whether or not to encapsulate.  If the next-hop ST agent
         is on a remote network and the route to that network is through
         a router that supports IP but not ST, then encapsulation is
         required.  As mentioned in Section 3.8.1 (page 69), routing
         table entries must be expanded to indicate whether the router
         supports ST.

         On forwarding, the (mostly constant) IP Header must be inserted
         and the IP checksum appropriately updated.

         On a directly connected network, though, one might want to
         encapsulate only when sending to a particular destination host
         that does not allow demultiplexing on the IP Version Number
         field.  This requires the routing table to include host-route
         as well as network-route entries.  Host-route entries might
         require static definition if the hosts do not participate in
         the routing protocols.  If packet size is not a critical
         performance factor, one solution is always to encapsulate on
         the directly connected network whenever some hosts require
         encapsulation.  Those that don't require the encapsulation
         should be able to remove it upon reception.


         3.7.5.1.         IP Multicasting

            If an ST agent must use IP encapsulation to reach multiple
            next-hops toward different targets, then either the packet
            must be replicated for transmission to each next-hop, or IP
            multicasting [6] may be used if it is implemented in the
            next-hop ST agents and in the intervening IP routers.
ToP   noToC   RFC1190 - Page 66
            This is analogous to using network-level service to
            multicast to several next-hop agents on a directly connected
            network.

            When the stream is established, the collection of next-hop
            ST agents must be set up as an IP multicast group.  It may
            be necessary for the ST agent that wishes to send the IP
            multicast to allocate a transient multicast group address
            and then tell the next-hop agents to join the group.  Use of
            the MulticastAddress parameter (see Section 4.2.2.7 (page
            86)) provides one way that the information may be
            communicated, but other techniques are possible.  The
            multicast group address in inserted in the Destination
            Address field of the IP encapsulation when data packets are
            transmitted.

            A block of transient IP multicast addresses, 224.1.0.0 -
            224.1.255.255, has been allocated for this purpose.  There
            are 2^16 addresses in this block, allowing a direct mapping
            with 16-bit HIDs, if appropriate.  The mechanisms for
            allocating these addresses are not defined here.

            In addition, two permanent IP multicast addresses have been
            assigned to facilitate experimentation with exchange of
            routing or other information among ST agents.  Those
            addresses are:

               224.0.0.7    All ST routers
               224.0.0.8    All ST hosts

            An ST router is an ST agent that can pass traffic between
            attached networks;  an ST host is an ST agent that is
            connected to a single network or is not permitted to pass
            traffic between attached networks.  Note that the range of
            these multicasts is normally just the attached local
            network, limited by setting the IP time-to-live field to 1
            (see [6]).


      3.7.6.        Retransmission

         The ST Control Message Protocol is made reliable through use of
         retransmission when an expected acknowledgment is not received
         in a timely manner.  The problem of when to send a
         retransmission has been studied for protocols such as TCP [2]
         [10] [11].  The problem should be simpler for ST since control
         messages usually only have to travel a single hop and they do
         not contain very much data.  However, the algorithms developed
         for TCP are sufficiently simple that their use is recommended
         for ST as well;  see [2].  An implementor might, for example,
         choose to keep statistics separately for each
ToP   noToC   RFC1190 - Page 67
         neighboring ST agent, or combined into a single statistic for
         an attached network.

         Estimating the packet round-trip time (RTT) is a key function
         in reliable transport protocols such as TCP.  Estimation must
         be dynamic, since congestion and resource contention result in
         varying delays.  If RTT estimates are too low, packets will be
         retransmitted too frequently, wasting network capacity.  If RTT
         estimates are too high, retransmissions will be delayed
         reducing network throughput when transmission errors occur.
         Article [11] identifies problems that arise when RTT estimates
         are poor, outlines how RTT is used and how retransmission
         timeouts (RTO) are estimated, and surveys several ways that RTT
         and RTO estimates can be improved.

         Note the HELLO/ACK mechanism described in Section 3.7.1.2 (page
         49) can give an estimate of the RTT and its variance.  These
         estimates are also important for use with the delay and delay
         variance entries in the FlowSpec.


      3.7.7.        Routing

         ST requires access to routing information in order to select a
         path from an origin to the destination(s).  However, routing is
         considered to be a separate issue and neither the routing
         algorithm nor its implementation is specified here.  ST should
         operate equally well with any reasonable routing algorithm.

         While ST may be capable of using several types of information
         that are not currently available, the minimal information
         required is that provided by IP, namely the ability to find an
         interface and next hop router for a specified IP destination
         address and Type of Service.  Methods to make more information
         available and to use it are left for further study.  For
         initial ST implementations, any routing information that is
         required but not automatically provided will be assumed to be
         manually configured into the ST agents.


      3.7.8.        Security

         The ST Protocol by itself does not provide security services.
         It is more vulnerable to misdelivery and denial of service than
         IP since the ST Header only carries a 16-bit HID for
         identification purposes.  Any information, such as source and
         destination addresses, which a higher-layer protocol might use
         to detect misdelivery are the responsibility of either the
         application or higher-layer protocol.
ToP   noToC   RFC1190 - Page 68
         ST is less prone to traffic analysis than IP since the only
         identifying information contained in the ST Header is a hop-
         by-hop identifier (HID).  However, the use of a HID is also
         what makes ST more vulnerable to denial of service since an ST
         agent has no reliable way to detect when bogus traffic is
         injected into, and thus consumes bandwidth from, a user's
         stream.  Detection can be enhanced through use of per-interface
         forwarding tables and verification of local network source and
         destination addresses.

         We envision that applications that require security services
         will use facilities, such as the Secure Digital Networking
         System (SDNS) layer 3 Security Protocol (SP3/D) [19] [20].  In
         such an environment, ST PDUs would first be encapsulated in an
         IP Header, using IP Protocol 5 (ST) as described in Section
         3.7.5 (page 64).  These IP datagrams would then be secured
         using SP3/D, which results in another IP Protocol 5 PDU that
         can be passed between ST agents.

         This memo does not specify how an application invokes security
         services.


   3.8.       ST Service Interfaces

      ST has several interfaces to other modules in a communication
      system.  ST provides its services to applications or transport-
      level protocols through its "upper" interface (or SAP).  ST in
      turn uses the services provided by network layers, management
      functions (e.g., address translation and routing), and IP.  The
      interfaces to these modules are described in this section in the
      form of subroutine calls.  Note that this does not mean that an
      implementation must actually be implemented as subroutines, but is
      instead intended to identify the information to be passed between
      the modules.

      In this style of outlining the module interfaces, the information
      passed into a module is shown as arguments to the subroutine call.
      Return information and/or success/failure indications are listed
      after the arrow ("->") that follows the subroutine call.  In
      several cases, a list of values must either be passed to or
      returned from a module interface.  Examples include a set of
      target addresses, or the mappings from a target list to a set of
      next hop addresses that span the route to the originally listed
      targets.  When such a list is appropriate, the values repeated for
      each list element are bracketed and an asterisk is added to
      indicate that zero, one, or many list elements can be passed
      across the interface (e.g., "<target>*" means zero, one, or more
      targets).
ToP   noToC   RFC1190 - Page 69
      3.8.1.        Access to Routing Information

         The design of routing functions that can support a variety of
         resource management algorithms is difficult.  In this section
         we suggest a set of preliminary interfaces suitable for use in
         initial experiments.  We expect that these interfaces will
         change as we gain more insight into how routing, resource
         allocation, and decision making elements are best divided.

         Routing functions are required to identify the set of potential
         routes to each destination site.  The routing functions should
         make some effort to identify routes that are currently
         available and that meet the resource requirements. However,
         these properties need not be confirmed until the actual
         resource allocation and connection setup propagation are
         performed.

         The minimum capability required of the interface to routing is
         to identify the network interface and next hop toward a given
         target.  We expect that the traditional routing table will need
         to be extended to include information that ST requires such as
         whether or not a next hop supports ST, and, if so, whether or
         not IP encapsulation (see Section 3.7.5 (page 64)) is required
         to communicate with it.  In particular, host entries will be
         required for hosts that can only support ST through
         encapsulation because the IP software either is not capable of
         demultiplexing datagrams based on the IP Version Number field,
         or the application interface only supports access to raw IP
         datagrams.  This interface is illustrated by the function:

            FindNextHop( destination, TOS )
               -> result, < interface, next hop, ST-capable,
                  MustEncapsulate >*

         However, the resource management functions can best tradeoff
         among alternative routes when presented with a matrix of all
         potential routes.  The matrix entry corresponding to a
         destination and a next hop would contain the estimated
         characteristics of the corresponding pathway.  Using this
         representation, the resource management functions can quickly
         determine the next hop sets that cover the entire destination
         list, and compare the various parameters of the tradeoff
         between the guarantees that can be promised by each set.  An
         interface that returns a compressed matrix, listing the
         suitable routes by next hop and the destinations reachable
         through each, is illustrated by the function:

            FindNextHops( < destination >*, TOS )
               -> result, < destination, < interface, next hop,
                  ST-capable, MustEncapsulate >* >*
ToP   noToC   RFC1190 - Page 70
         We hope that routing protocols will be available that propagate
         additional metrics of bandwidth, delay, bit/burst error rate,
         and whether a router has ST capability.  However, propagating
         this information in a timely fashion is still a key research
         issue.


      3.8.2.        Access to Network Layer Resource Reservation

         The resources required to reach the next-hops associated with
         the chosen routes must be allocated.  These allocations will
         generally be requested and released incrementally.  As the
         next-hop elements for the routes are chosen, the network
         resources between the current node and the next-hops must be
         allocated.  Since the resources are not guaranteed to be
         available -- a network or node further down the path might have
         failed or needed resources might have been allocated since the
         routing decisions where made -- some of these allocations may
         have to be released, another route selected, and a new
         allocation requested.

         There are four basic interface functions needed for the network
         resource allocator.  The first checks to see if the required
         resources are available, returning the likelihood that an
         ensuing resource allocation will succeed.  A probability of 0%
         indicates the resources are not available or cannot promise to
         meet the required guarantees.  Low probabilities indicate that
         most of the resource has been allocated or that there is a lot
         of contention for using the resource.  This call does not
         actually reserve the resources:

            ResourceProbe( requirements )
               -> likelihood

         Another call reserves the resources:

            ResourceReserve( requirements )
               -> result, reservation_id

         The third call adjusts the resource guarantees:

            ResourceAdjust( reservation_id, new requirements )
               -> result

         The final call allows the resources to be released:

            ResourceRelease( reservation_id )
               -> result
ToP   noToC   RFC1190 - Page 71
      3.8.3.        Network Layer Services Utilized

         ST requires access to the usual network layer functions to send
         and receive packets and to be informed of network status
         information.  In addition, it requires functions to enable and
         disable reception of multicast packets.  Such functions might
         be defined as:

            JoinLocalGroup( network level group-address )
               -> result, multicast_id

            LeaveLocalGroup( network level group-address )
               -> result

            RecvNet( SAP )
               -> result, src, dst, len, BufPTR )

            SendNet( src, dst, SAP, len, BufPTR )
               -> result

            GetNotification( SAP )
               -> result, infop


      3.8.4.        IP Services Utilized

         Since ST packets might be sent or received using IP
         encapsulation, IP level routines to join and leave multicast
         groups are required in addition to the usual services defined
         in the IP specification (see the IP specification [2] [15] and
         the IP multicast specification [6] for details).

            JoinHostGroup( IP level group-address, interface )
               -> result, multicast_id

            LeaveHostGroup( IP level group-address, interface )
               -> result

            GET_SRCADDR( remote IP addr, TOS )
               -> local IP address

            SEND( src, dst, prot, TOS, TTL, BufPTR, len, Id, DF,
                  opt )
               -> result

            RECV( BufPTR, prot )
               -> result, src, dst, SpecDest, TOS, len, opt

            GET_MAXSIZES( local, remote, TOS )
               -> MMS_R, MMS_S
ToP   noToC   RFC1190 - Page 72
            ADVISE_DELIVPROB( problem, local, remote, TOS )
               -> result

            SEND_ICMP( src, dst, TOS, TTL, BufPTR, len, Id, DF, opt )
               -> result

            RECV_ICMP( BufPTR )
               -> result, src, dst, len, opt


      3.8.5.        ST Layer Services Provided

         Interface to the ST layer services may be modeled using a set
         of subroutine calls (but need not be implemented as such).
         When the protocol is implemented as part of an operating
         system, these subroutines may be used directly by a higher
         level protocol processing layer.

         These subroutines might also be provided through system service
         calls to provide a raw interface for use by an application.
         Often, this will require further adaptation to conform with the
         idiom of the particular operating system.  For example, 4.3 BSD
         UNIX (TM) provides sockets, ioctls and signals for network
         programming.

         open( connect/listen, SAPBytes, local SAP, local host,
               account, authentication info, < foreign host,
               SAPBytes, foreign SAP, options >*, flow spec,
               precedence, group name, optional parameters )
             -> result, id, stream name, < foreign host,
               foreign SAPBytes, foreign SAP, result, flow spec,
               rname, optional parameters >*

         Note that an open by a target in "listen mode" may cause ST to
         create a state block for the stream to facilitate rendezvous.

         add( id, SAPBytes, local SAP, local host, < foreign host,
              SAPBytes, foreign SAP, options >*, flow spec,
              precedence, group name, optional parameters )
            -> result, < foreign host, foreign SAPBytes,
               foreign SAP, result,
               flow spec, rname, optional parameters >*

         send( id, buffer address, byte count, priority )
            -> result, next send time, burst send time

         recv( id, buffer address, max byte count )
            -> result, byte count

         recvsignal( id )
            -> result, signal, info
ToP   noToC   RFC1190 - Page 73
         receivecontrol( id )
            -> result, id, stream name, < foreign host,
               foreign SAPBytes, foreign SAP, result, flow spec,
               rname, optional parameters >*

         sendcontrol( id, flow spec, precedence, options,
               < foreign host, SAPBytes, foreign SAP, options >*)
            -> result, < foreign host, foreign SAPBytes,
               foreign SAP, result, flow spec, rname,
               optional parameters >*

         change( id, flow spec, precedence, options,
               < foreign host, SAPBytes, foreign SAP, options >*)
            -> result, < foreign host, foreign SAPBytes,
               foreign SAP, result, flow spec, rname,
               optional parameters >*

         close( id, < foreign host, SAPBytes, foreign SAP >*,
               optional parameters )
            -> result

         status( id/stream name/group name )
            -> result, account, group name, protocol,
               < stream name, < foreign host, SAPbytes,
               foreign SAP, state, options, flow spec,
               routing info, rname >*, precedence, options >*

         creategroup( members* )
            -> result, group name

         deletegroup( group name, members* )
            -> result
ToP   noToC   RFC1190 - Page 74
                      [This page intentionally left blank.]


(next page on part 4)

Next Section