RFC 1190
Experimental Internet Stream Protocol: Version 2 (ST-II)
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
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
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.
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).
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 >* >*
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
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
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
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
[This page intentionally left blank.]
(next page on part 4)
