RFlowSpec and an RHID parameter will create database entries
for streams in both directions and will allocate resources in
both directions for them. By this we mean that an ST agent
will reserve resources to the next-hop agent for the normal
stream and resources back to the previous-hop agent for the
reverse stream. This is necessary since it is expected that
network reservation interfaces will require the destination
address(es) in order to make reservations, and because all ST
agents must use the same reservation model.
The target agent will select a Name for the reverse stream and
return it (in the RName parameter) and the resulting FlowSpec
(in the RFlowSpec parameter) of the ACCEPT message. Each agent
that processes the ACCEPT will update its partial stream
database entry for the reverse stream with the Name contained
in the RName parameter. We assume that the next higher
protocol layer will use the same SAP for both streams.
3.6.4. NoRecovery Option
The NoRecovery option is used to indicate that ST agents should
not attempt recovery in case of network or component failure.
If a failure occurs, the origin will be notified via a REFUSE
message and the target(s) via a DISCONNECT, with an appropriate
reason code of "failure" (i.e., one of DropFailAgt,
DropFailHst, DropFailIfc, DropFailNet, IntfcFailure,
NetworkFailure, STAgentFailure, FailureRecovery). They can
then decide whether to wait for the failed component to be
fixed, or drop the target via DISCONNECT/REFUSE messages. The
NoRecovery option can only be set to one (1) by the origin, and
must be the same for the entire stream.
3.6.5. RevChrg Option
The RevChrg option bit in the FlowSpec is set to one (1) by the
origin to request that the target(s) pay any charges associated
with the stream (to the target(s)); see Section 4.2.2.3 (page
83). If the target is not willing to accept charges, the bit
should be set to zero (0) by the target before returning the
FlowSpec to the origin in an ACCEPT message.
If the FDx option is also specified, the target pays charges
for both streams.
3.6.6. Source Route Option
The Source Route Option may be used both for diagnostic
purposes, and, in those hopefully infrequent cases where the
standard routing mechanisms do not produce paths that satisfy
some policy constraint, to allow the origin to prespecify the
ST agents along the path to the target(s). The idea is that
the origin can explicitly specify the path to a target, either
strictly hop-by-hop or more loosely by specification of one or
more agents through which the path must pass.
The option is specified by including source routing information
in the Target structure. A target may contain zero or more
SrcRoute options; when multiple options are present, they are
processed in the order in which they occur. The parameter code
indicates whether the portion of the path contained in the
parameter is of the strict or loose variety.
Since portions of a path may pass through portions of an
internet that does not support ST agents, there are also forms
of the SrcRoute option that are converted into the
Application Agent A Agent 2 Agent 3 Agent B
1. (open B<SR=2,3>)
2. V (proc B listening)
3. (source routed to 2)
V
4. (check resources from A to Agent 2: already allocated,
V reuse control link & HID, no additional resources needed)
5. +-> CONNECT B<SR=2,3>->-+-+
<RVLId=23><SVLId=5> | |
6. <Ref=50> V |
7. +<- ACK ----------------+ |
<RVLId=5><SVLId=23> |
<Ref=50> V
8. (source routed to 3)
V
9. (reserve resources 2 to 3)
V
10. +-> CONNECT B<SR=3> ---->+
<RVLId=0><SVLId=24> |
<Ref=280><HID=4801> V
11. +<- HID-APPROVE <--------+
<RVLId=24><SVLId=33> |
<Ref=280><HID=4801> |
V
(routing to B)
V
(reserve resources from 3 to B)
V
12. +-> CONNECT B ---------->+
<RVLId=0><SVLId=32> |
<Ref=330><HID=6000> V
13. +<- HID-APPROVE <--------+
<RVLId=32><SVLId=45> |
<Ref=330><HID=6000> V
14. (proc B accepts)
V
... perform normal ACCEPT processing ... <-----+
Figure 17. Source Routing Option
corresponding IP Source Routing options by the ST agent that
performs the encapsulation.
The SrcRoute option is usually selected by the origin, but may
be used by intermediate agents if specified as a result of the
routing function.
For example, in the topology of Figure 2, if A wants to add B
back into the stream, its routing function might decide that
the best path is via Agent 3. Since the data is already being
multicast across the network connected to C, D, and E, the
route via Agent 3 might cost less than having A replicate the
data packets and send them across A's network a second time.
3.7. Ancillary Functions
There are several functions and procedures that are required by
the ST Protocol. They are described in subsequent sections.
3.7.1. Failure Detection
The ST failure detection mechanism is based on two assumptions:
1 If a neighbor of an ST agent is up, and has been up
without a disruption, and has not notified the ST agent
of a problem with streams that pass through both, then
the ST agent can assume that there has not been any
problem with those streams.
2 A network through which an ST agent has routed a stream
will notify the ST agent if there is a problem that
affects the stream data packets but does not affect the
control packets.
The purpose of the robustness protocol defined here is for ST
agents to determine that the streams through a neighbor have
been broken by the failure of the neighbor or the intervening
network. This protocol should detect the overwhelming majority
of failures that can occur. Once a failure is detected,
recovery procedures are initiated.
3.7.1.1. Network Failures
In this memo, a network is defined to be the protocol
layer(s) below ST. This function can be implemented in a
hardware module separate from the ST agent, or as software
modules within the ST agent itself, or as a combination of
both. This specification and the robustness protocol do not
differentiate between these alternatives.
An ST agent can detect network failures by two mechanisms;
the network can report a failure, or the ST agent can
discover a failure by itself. They differ in the amount of
information that ST agent has available to it in order to
make a recovery decision. For example, a network may be
able to report that reserved bandwidth has been lost and the
reason for the loss and may also report that connectivity to
the neighboring ST agent remains intact. In this case, the
ST agent may request the network to allocate bandwidth anew.
On the other hand, an ST agent may discover that
communication with a neighboring ST agent has ceased because
it has not received any traffic from that neighbor in some
time period. If an ST agent detects a failure, it may not
be able to determine if the failure was in the network while
the neighbor remains available, or the neighbor has failed
while the network remains intact.
3.7.1.2. Detecting ST Stream Failures
Each ST agent periodically sends each neighbor with which it
shares a stream a HELLO message. A HELLO message is ACKed
if the Reference field is non-zero. This message exchange
is between ST agents, not entities representing streams or
applications (there is no Name field in a HELLO message).
That is, an ST agent need only send a single HELLO message
to a neighbor regardless of the number of streams that flow
between them. All ST agents (host as well as intermediate)
must participate in this exchange. However, only agents
that share active streams need to participate in this
exchange.
To facilitate processing of HELLO messages, an
implementation may either create a separate Virtual Link
Identifier for each neighbor having an active stream, or may
use the reserved identifier of one (1) for the SVLId field
in all its HELLO messages.
An implementation that wishes to send its HELLO messages via
a data path instead of the control path may setup a separate
stream to its neighbor agent for that purpose. The HELLO
message would contain a HID of zero, indicating a control
message, but would be identified to the next lower protocol
layer as being part of the separate stream.
As well as identifying the sender, the HELLO message has two
fields; a HelloTimer field that is in units of milliseconds
modulo the maximum for the field size, and a
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
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
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.
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.
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.
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.
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
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.
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
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.
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)
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
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)
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)
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
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.
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