some portion of its previously requested repair content, the receiver
will use the same strategy, but only NACK for the set of parity
and/or data symbols it has not yet received. Optionally, the
receivers could also provide a count of erasures as a convenience to
the sender or intermediate systems assisting NACK operation.
After receipt and accumulation of NACK messages during the
aggregation period, the sender can begin transmission of fresh
(previously untransmitted) parity symbols for the coding block based
on the highest receiver erasure count _if_ it has a sufficient
quantity of parity symbols that were _not_ previously transmitted.
Otherwise, the sender MUST resort to transmitting the explicit set of
repair vectors requested. With this approach, the sender needs to
maintain very little state on requests it has received from the group
without need for synchronization of repair requests from the group.
Since all receivers use the same consistent algorithm to express
their explicit repair needs, NACK suppression among receivers is
simplified over the course of multiple repair cycles. The receivers
can simply compare NACKs heard from other receivers against their own
calculated repair needs to determine whether they should transmit or
suppress their pending NACK messages.
3.2.3.2. NACK Content Format
The format of NACK content will depend on the protocol’s data service
model and the format of data content identification the protocol
uses. This NACK format also depends upon the type of FEC encoding
(if any) used. Figure 2 illustrates a logical, hierarchical
transmission content identification scheme, denoting that the notion
of objects (or streams) and/or FEC blocking is optional at the
protocol instantiation’s discretion. Note that the identification of
objects is with respect to a given sender. It is recommended that
transport data content identification is done within the context of a
sender in a given session. Since the notion of session "streams" and
"blocks" is optional, the framework degenerates to that of typical
transport data segmentation and reassembly in its simplest form.
Session_
\_
Sender_
\_
[Object/Stream(s)]_
\_
[FEC Blocks]_
\_
Symbols
Fig. 2: NORM Data Content Identification Hierarchy
The format of NACK messages should meet the following goals:
1) Able to identify transport data unit transmissions required to
repair a portion of the received content, whether it is an entire
missing object/stream (or range), entire FEC coding block(s), or
sets of symbols,
2) Be simple to process for NACK aggregation and suppression,
3) Be capable of including NACKs for multiple objects, FEC coding
blocks and/or symbols in a single message, and
4) Have a reasonably compact format.
If the NORM transport object/stream is identified with an <objectId>
and the FEC symbol being transmitted is identified with an
<fecPayloadId>, the concatenation of <objectId::fecPayloadId>
comprises a basic transport protocol data unit (TPDU) identifier for
symbols from a given source. NACK content can be composed of lists
and/or ranges of these TPDU identifiers to build up NACK messages to
describe the receivers repair needs. If no hierarchical object
delineation or FEC blocking is used, the TPDU is a simple linear
representation of the data symbols transmitted by the sender. When
the TPDU represents a hierarchy for purposes of object/stream
delineation and/or FEC blocking, the NACK content unit may require
flags to indicate which portion of the TPDU is applicable. For
example, if an entire "object" (or range of objects) is missing in
the received data, the receiver will not necessarily know the
appropriate range of <sourceBlockNumbers> or <encodingSymbolIds> for
which to request repair and thus requires some mechanism to request
repair (or retransmission) of the entire unit represented by an
<objectId>. The same is true if entire FEC coding blocks represented
by one or a range of <sourceBlockNumbers> have been lost.
NACK Content Interface Description
Inputs:
1) Sender identification.
2) Sender data identification.
3) Sender FEC Object Transmission Information.
4) Recorded sender transmission sequence position.
5) Current sender transmission sequence position. History of
repair needs for this sender.
Outputs:
1) NACK message with repair requests.
3.2.4. Sender Repair Response
Upon reception of a repair request from a receiver in the group, the
sender will initiate a repair response procedure. The sender may
wish to delay transmission of repair content until it has had
sufficient time to accumulate potentially multiple NACKs from the
receiver set. This allows the sender to determine the most efficient
repair strategy for a given transport stream/object or FEC coding
block. Depending upon the approach used, some protocols may find it
beneficial for the sender to provide an indicator of pending repair
transmissions as part of its current transmitted message content.
This can aid some NACK suppression mechanisms. The amount of time to
perform this NACK aggregation should be sufficient to allow for the
maximum receiver NACK backoff window ("T_maxBackoff" from Section
3.2.2) and propagation of NACK messages from the receivers to the
sender. Note the maximum transmission delay of a message from a
receiver to the sender may be approximately (1*GRTT) in the case of
very asymmetric network topology with respect to transmission delay.
Thus, if the maximum receiver NACK backoff time is T_maxBackoff =
K*GRTT, the sender NACK aggregation period should be equal to at
least:
T_sndrAggregate = T_maxBackoff + 1*GRTT = (K+1)*GRTT
Immediately after the sender NACK aggregation period, the sender will
begin transmitting repair content determined from the aggregate NACK
state and continue with any new transmission. Also, at this time,
the sender should observe a "holdoff" period where it constrains
itself from initiating a new NACK aggregation period to allow
propagation of the new transmission sequence position due to the
repair response to the receiver group. To allow for worst case
asymmetry, this "holdoff" time should be:
T_sndrHoldoff = 1*GRTT
Recall that the receivers will also employ a "holdoff" timeout after
generating a NACK message to allow time for the sender’s response.
Given a sender <T_sndrAggregate> plus <T_sndrHoldoff> time of
(K+1)*GRTT, the receivers should use holdoff timeouts of:
T_rcvrHoldoff = T_sndrAggregate + T_sndrHoldoff = (K+2)*GRTT
This allows for a worst-case propagation time of the receiver’s NACK
to the sender, the sender’s aggregation time and propagation of the
sender’s response back to the receiver. Additionally, in the case of
unicast feedback from the receiver set, it may be useful for the
sender to forward (via multicast) a representation of its aggregated
NACK content to the group to allow for NACK suppression when there is
not multicast connectivity among the receiver set.
At the expiration of the <T_sndrAggregate> timeout, the sender will
begin transmitting repair messages according to the accumulated
content of NACKs received. There are some guidelines with regards to
FEC-based repair and the ordering of the repair response from the
sender that can improve reliable multicast efficiency:
1) When FEC is used, it is beneficial that the sender transmit
previously untransmitted parity content as repair messages
whenever possible. This maximizes the receiving nodes’ ability
to reconstruct the entire transmitted content from their
individual subsets of received messages.
2) The transmitted object and/or stream data and repair content
should be indexed with monotonically increasing sequence numbers
(within a reasonably large ordinal space). If the sender observes
the discipline of transmitting repair for the earliest content
(e.g., ordinally lowest FEC blocks) first, the receivers can use a
strategy of withholding repair requests for later content until
the sender once again returns to that point in the object/stream
transmission sequence. This can increase overall message
efficiency among the group and help work to keep repair cycles
relatively synchronized without dependence upon strict time
synchronization among the sender and receivers. This also helps
minimize the buffering requirements of receivers and senders and
reduces redundant transmission of data to the group at large.
Sender Repair Response Interface Description
Inputs:
1) Receiver NACK messages
2) Group timing information
Outputs
1) Repair messages (FEC and/or Data content retransmission)
2) Advertisement of current pending repair transmissions when
unicast receiver feedback is detected.
3.3. NORM Receiver Join Policies and Procedures
Consideration should be given to the policies and procedures by which
new receivers join a group (perhaps where reliable transmission is
already in progress) and begin requesting repair. If receiver joins
are unconstrained, the dynamics of group membership may impede the
application’s ability to meet its goals for forward progression of
data transmission. Policies limiting the opportunities when
receivers begin participating in the NACK process may be used to
achieve the desired behavior. For example, it may be beneficial for
receivers to attempt reliable reception from a newly-heard sender
only upon non-repair transmissions of data in the first FEC block of
an object or logical portion of a stream. The sender may also
implement policies limiting the receivers from which it will accept
NACK requests, but this may be prohibitive for scalability reasons in
some situations. Alternatively, it may be desirable to have a looser
transport synchronization policy and rely upon session management
mechanisms to limit group dynamics that can cause poor performance,
in some types of bulk transfer applications (or for potential
interactive reliable multicast applications).
Group Join Policy Interface Description
Inputs:
1) Current object/stream data/repair content and sequencing
identifiers from sender transmissions.
Outputs:
1) Receiver yes/no decision to begin receiving and NACKing for
reliable reception of data
3.4. Reliable Multicast Member Identification
In a NORM protocol (or other multicast protocols) where there is the
potential for multiple sources of data, it is necessary to provide
some mechanism to uniquely identify the sources (and possibly some or
all receivers in some cases) within the group. Identity based on
arriving packet source addresses is insufficient for several reasons.
These reasons include routing changes for hosts with multiple
interfaces that result in different packet source addresses for a
given host over time, network address translation (NAT) or firewall
devices, or other transport/network bridging approaches. As a
result, some type of unique source identifier <sourceId> field should
be present in packets transmitted by reliable multicast session
members.
3.5. Data Content Identification
The data and repair content transmitted by a NORM sender requires
some form of identification in the protocol header fields. This
identification is required to facilitate the reliable NACK-oriented
repair process. These identifiers will also be used in NACK messages
generated. This building block document assumes two very general
types of data that may comprise bulk transfer session content. One
type is static, discrete objects of finite size and the other is
continuous non-finite streams. A given application may wish to
reliably multicast data content using either one or both of these
paradigms. While it may be possible for some applications to further
generalize this model and provide mechanisms to encapsulate static
objects as content embedded within a stream, there are advantages in
many applications to provide distinct support for static bulk objects
and messages with the context of a reliable multicast session. These
applications may include content caching servers, file transfer, or
collaborative tools with bulk content. Applications with
requirements for these static object types can then take advantage of
transport layer mechanisms (i.e., segmentation/reassembly, caching,
integrated forward error correction coding, etc.) rather than being
required to provide their own mechanisms for these functions at the
application layer.
As noted, some applications may alternatively desire to transmit bulk
content in the form of one or more streams of non-finite size.
Example streams include continuous quasi-real-time message broadcasts
(e.g., stock ticker) or some content types that are part of
collaborative tools or other applications. And, as indicated above,
some applications may wish to encapsulate other bulk content (e.g.,
files) into one or more streams within a multicast session.
The components described within this building block document are
envisioned to be applicable to both of these models with the
potential for a mix of both types within a single multicast session.
To support this requirement, the normal data content identification
should include a field to uniquely identify the object or stream
<objectId> within some reasonable temporal or ordinal interval. Note
that it is _not_ expected that this data content identification will
be globally unique. It is expected that the object/stream identifier
will be unique with respect to a given sender within the reliable
multicast session and during the time that sender is supporting a
specific transport instance of that object or stream.
Since the "bulk" object/stream content usually requires segmentation,
some form of segment identification must also be provided. This
segment identifier will be relative to any object or stream
identifier that has been provided. Thus, in some cases, NORM
protocol instantiations may be able to receive transmissions and
request repair for multiple streams and one or more sets of static
objects in parallel. For protocol instantiations employing FEC the
segment identification portion of the data content identifier may
consist of a logical concatenation of a coding block identifier
<sourceBlockNumber> and an identifier for the specific data or parity
symbol <encodingSymbolId> of the code block. The FEC Building Block
document [9] provides a standard message format for identifying FEC
transmission content. NORM protocol instantiations using FEC SHOULD
follow that document’s guidelines.
Additionally, flags to determine the usage of the content identifier
fields (e.g., stream vs. object) may be applicable. Flags may also
serve other purposes in data content identification. It is expected
that any flags defined will be dependent upon individual protocol
instantiations.
In summary, the following data content identification fields may be
required for NORM protocol data content messages:
1) Source node identifier (<sourceId>)
2) Object/Stream identifier (<objectId>), if applicable.
3) FEC Block identifier (<sourceBlockNumber>), if applicable.
4) FEC Symbol identifier (<encodingSymbolId>)
5) Flags to differentiate interpretation of identifier fields or
identifier structure that implicitly indicates usage.
6) Additional FEC transmission content fields per FEC Building Block
These fields have been identified because any generated NACK messages
will use these identifiers in requesting repair or retransmission of
data. NORM protocols that use these data content fields should also
be compatible with support for intermediate system assistance to
reliable multicast transport operation when available.
3.6. Forward Error Correction (FEC)
Multiple forward error correction (FEC) approaches have been
identified that can provide great performance enhancements to the
repair process of NACK-oriented and other reliable multicast
protocols [11], [12], [13]. NORM protocols can reap additional
benefits since FEC-based repair does not _generally_ require explicit
knowledge of repair content within the bounds of its coding block
size (in symbols). In NORM, parity repair packets generated will
generally be transmitted only in response to NACK repair requests
from receiving nodes. However, there are benefits in some network
environments for transmitting some predetermined quantity of FEC
repair packets multiplexed with the regular data symbol transmissions
[14]. This can reduce the amount of NACK traffic generated with
relatively little overhead cost when group sizes are very large or
the network connectivity has a large delay*bandwidth product with
some nominal level of expected packet loss. While the application of
FEC is not unique to NORM, these sorts of requirements may dictate
the types of algorithms and protocol approaches that are applicable.
A specific issue related to the use of FEC with NORM is the mechanism
used to identify the portion(s) of transmitted data content to which
specific FEC packets are applicable. It is expected that FEC
algorithms will be based on generating a set of parity repair packets
for a corresponding block of transmitted data packets. Since data
content packets are uniquely identified by the concatenation of
<sourceId::objectId::sourceBlockNumber::encodingSymbolId> during
transport, it is expected that FEC packets will be identified in a
similar manner. The FEC Building Block document [9] provides
detailed recommendations concerning application of FEC and standard
formats for related reliable multicast protocol messages.
3.7. Round-trip Timing Collection
The measurement of packet propagation round-trip time (RTT) among
members of the group is required to support timer-based NACK
suppression algorithms, timing of sender commands or certain repair
functions, and congestion control operation. The nature of the
round-trip information collected is dependent upon the type of
interaction among the members of the group. In the case where only
"one-to-many" transmission is required, it may be that only the
sender require RTT knowledge of the greatest RTT (GRTT) among the
receiver set and/or RTT knowledge of only a portion of the group.
Here, the GRTT information might be collected in a reasonably
scalable manner. For congestion control operation, it is possible
that RTT information may be required by each receiver in the group.
In this case, an alternative RTT collection scheme may be utilized
where receivers collect individual RTT measurements with respect to
the sender and advertise them to the group or sender. Where it is
likely that exchange of reliable multicast data will occur among the
group on a "many-to-many" basis, there are alternative measurement
techniques that might be employed for increased efficiency [15]. And
in some cases, there might be absolute time synchronization among
hosts that may simplify RTT measurement. There are trade-offs in
multicast congestion control design that require further
consideration before a universal recommendation on RTT (or GRTT)
measurement can be specified. Regardless of how the RTT information
is collected (and more specifically GRTT) with respect to congestion
control or other requirements, the sender will need to advertise its
current GRTT estimate to the group for various timeouts used by
receivers.
3.7.1. One-to-Many Sender GRTT Measurement
The goal of this form of RTT measurement is for the sender to learn
the GRTT among the receivers who are actively participating in NORM
operation. The set of receivers participating in this process may be
the entire group or some subset of the group determined from another
mechanism within the protocol instantiation. An approach to collect
this GRTT information follows.
The sender periodically polls the group with a message (independent
or "piggy-backed" with other transmissions) containing a <sendTime>
timestamp relative to an internal clock at the sender. Upon
reception of this message, the receivers will record this <sendTime>
timestamp and the time (referenced to their own clocks) at which it
was received <recvTime>. When the receiver provides feedback to the
sender (either explicitly or as part of other feedback messages
depending upon protocol instantiation specification), it will
construct a "response" using the formula:
grttResponse = sendTime + (currentTime - recvTime)
where the <sendTime> is the timestamp from the last probe message
received from the source and the (<currentTime> - <recvTime>) is the
amount of time differential since that request was received until the
receiver generated the response.
The sender processes each receiver response by calculating a current
RTT measurement for the receiver from whom the response was received
using the following formula:
RTT_rcvr = currentTime - grttResponse
During the each periodic GRTT probing interval, the source keeps the
peak round trip timing measurement (RTT_peak) from the set of
responses it has received. A conservative estimate of GRTT is kept
to maximize the efficiency of redundant NACK suppression and repair
aggregation. The update to the source’s ongoing estimate of GRTT is
done observing the following rules:
1) If a receiver’s response round trip time (RTT_rcvr) is greater
than the current GRTT estimate, the GRTT is immediately updated to
this new peak value:
GRTT = RTT_rcvr
2) At the end of the response collection period (i.e., the GRTT probe
interval), if the recorded "peak" response RTT_peak) is less than
the current GRTT estimate, the GRTT is updated to:
GRTT = MAX(0.9*GRTT, RTT_peak)
3) If no feedback is received, the sender GRTT estimate remains
unchanged.
4) At the end of the response collection period, the peak tracking
value (RTT_peak) is reset to ZERO for subsequent peak detection.
The GRTT collection period (i.e., period of probe transmission) could
be fixed at a value on the order of that expected for group
membership and/or network topology dynamics. For robustness, more
rapid probing could be used at protocol startup before settling to a
less frequent, steady-state interval. Optionally, an algorithm may
be developed to adjust the GRTT collection period dynamically in
response to the current GRTT estimate (or variations in it) and to an
estimation of packet loss. The overhead of probing messages could
then be reduced when the GRTT estimate is stable and unchanging, but
be adjusted to track more dynamically during periods of variation
with correspondingly shorter GRTT collection periods. GRTT
collection may also be coupled with collection of other information
for congestion control purposes.
In summary, although NORM repair cycle timeouts are based on GRTT, it
should be noted that convergent operation of the protocol does not
_strictly_ depend on highly accurate GRTT estimation. The current
mechanism has proved sufficient in simulations and in the
environments where NORM-like protocols have been deployed to date.
The estimate provided by the algorithm tracks the peak envelope of
actual GRTT (including operating system effect as well as network
delays) even in relatively high loss connectivity. The steady-state
probing/update interval may potentially be varied to accommodate
different levels of expected network dynamics in different
environments.
3.7.2. One-to-Many Receiver RTT Measurement
In this approach, receivers send messages with timestamps to the
sender. To control the volume of these receiver-generated messages,