NACK
Click on the red underlined text to get to the source
... document addresses the creation of negative-acknowledgment (NACK)-
oriented reliable multicast (NORM ...
... "building block" components relevant to multicast protocols based
primarily on NACK operation for reliable transport. While this
document discusses a large set of reliable multicast ...
... NORM sender transmission strategies,
2) NACK-oriented repair process with timer-based feedback
suppression, and
...
... Group dynamics can also impact other protocol mechanisms such
as NACK timing, congestion control operation, etc.
...
... multicast infrastructure's ability to scale. In its simplest form,
there are limits to the group size to which a NACK-oriented protocol
can apply without NACK implosion problems. Research suggests that
...
... group size to which a NACK-oriented protocol
can apply without NACK implosion problems. Research suggests that
NORM group ...
... 7]. However, the potential for
router assistance and/or other NACK suppression heuristics may enable
these protocols to scale to very large group ...
... delivery latency
when designing NACK-oriented protocols. If probabilistic, timer-
based NACK ...
... NACK-oriented protocols. If probabilistic, timer-
based NACK suppression is to be used, there will be some delays built
into the NACK process to allow suppression to occur and for the
...
... based NACK suppression is to be used, there will be some delays built
into the NACK process to allow suppression to occur and for the
sender of data to identify appropriate content for efficient repair
...
... sender of data to identify appropriate content for efficient repair
transmission. For example, backoff timeouts can be used to ensure
efficient NACK suppression and repair transmission, but this comes at
a cost of increased delivery latency ...
... group may be restricted to
unicast feedback for NACKs and other messages. Consideration must be
given, in building block development and protocol design, to the
...
... multicast protocols,
there will continue to be a number of instances where this is not
available or practical. Any building block components for NACK-
oriented reliable multicast SHALL be capable of operating without
...
... block areas applicable to NORM protocols. Some of these areas are
specific to NACK-oriented protocols. Detailed descriptions of such
areas are provided. In other cases, the areas (e.g., node
identifiers, forward error correction ...
... below describes requirements placed on those other general building
block areas from the standpoint of NACK-oriented reliable multicast.
Where applicable, other building block documents are referenced for
...
... .->| Congestion Control |-' ' | Receiver NACK | |
| `---------------------' .' | Repair Process | |
| .---------------------. .' | .------------------. | |
...
... | .---------------------. .' | .------------------. | |
| | FEC |'. | | NACK Initiation | | |
| `---------------------'` `._ | `------------------' | |
| .---------------------. ``. `-._ | .------------------. | |
...
... | .---------------------. ``. `-._ | .------------------. | |
`--| RTT Collection |._` ` `->| | NACK Content | | |
`---------------------' .`- ` | `------------------' | |
.---------------------. \ `-`._ | .------------------. | |
...
... .---------------------. \ `-`._ | .------------------. | |
| Group Size Est. |---.-`---`->| | NACK Suppression | | |
`---------------------'`. ` ` | `------------------' | |
.---------------------. ` ` ` `------------------------' |
...
... `.`' .-------------------------. |
`>| Sender NACK Processing |_____/
| and Repair Response |
`-------------------------'
...
... given below. The components on the right are seen as specific to
NORM protocols, most notably the NACK repair process. These areas
are discussed in detail below. Some other components (e.g.,
...
... temporarily (or permanently) halting transmission. At this time, it
may be appropriate for receivers to respond with NACKs for any
outstanding repairs they require following the rules of the NORM NACK ...
... NACKs for any
outstanding repairs they require following the rules of the NORM NACK
procedure. For efficiency, the sender should allow sufficient time
...
... procedure. For efficiency, the sender should allow sufficient time
between the redundant transmissions to receive any NACK-oriented
responses from the receivers to this command.
...
... receivers to this command.
In general, when there is any resultant NACK or other feedback
operation, the timing of redundant transmission of control messages
...
... A critical component of NORM protocols is the NACK repair process.
This includes the receiver's role ...
...
The NORM NACK process (cycle) will be initiated by receivers that
detect a need for repair transmissions from a specific sender ...
... receiver should
initiate the NACK process only when it is known its repair
requirements exceed the amount of pending FEC ...
... of repair packets it is already planning to send for a block, the
receiver may be able to initiate the NACK processor earlier.
Allowing receivers ...
... processor earlier.
Allowing receivers to initiate NACK cycles at any time they detect
their repair needs have exceeded pending repair transmissions may
result in slightly quicker repair cycles. However, it may be useful
...
... their repair needs have exceeded pending repair transmissions may
result in slightly quicker repair cycles. However, it may be useful
to limit NACK process initiation to specific events such as at the
end-of-transmission of an FEC coding block or upon detection of
...
... FEC coding block or upon detection of
subsequent coding blocks. This can allow receivers to aggregate NACK
content into a smaller number of NACK messages and provide some
...
... receivers to aggregate NACK
content into a smaller number of NACK messages and provide some
implicit loose synchronization among the receiver ...
... synchronization among the receiver set to help
facilitate effective probabilistic suppression of NACK feedback. The
receiver MUST maintain a history of data content received from the
...
...
For probabilistic, timer-base suppression of feedback, the NACK cycle
should begin with receivers observing backoff timeouts. In
...
... receivers record the current position in the sender's
transmission sequence at which they initiate the NACK cycle. When
the suppression backoff timeout expires, the receivers should only
...
... receivers should only
consider their repair needs up to this recorded transmission position
in making the decision to transmit or suppress a NACK. Without this
restriction, suppression is greatly reduced as additional content is
received from the sender ...
... restriction, suppression is greatly reduced as additional content is
received from the sender during the time a NACK message propagates
across the network to the sender ...
... Outputs:
1) NACK process initiation decision
2) Recorded sender transmission sequence position.
...
... NACK Suppression ...
... An effective NORM feedback suppression mechanism is the use of random
backoff timeouts prior to NACK transmission by receivers requiring
repairs [10 ...
... receiver
will request repairs unless its pending repair needs have been
completely superseded by NACK messages heard from other receivers
(when receivers ...
... (when receivers are multicasting NACKs) or from some indicator from
the sender. When receivers ...
... NACK messages, the sender
may facilitate NACK suppression by forwarding a representation of
NACK content it has received to the group ...
... may facilitate NACK suppression by forwarding a representation of
NACK content it has received to the group at large or provide some
other indicator of the repair information it will be subsequently
...
... This results in the majority of the receiver set holding off
transmission of NACK messages under the assumption that the smaller
number of "early NACKers" will supersede the repair needs of the
remainder of the group ...
... the number of receivers (R) potentially generating feedback. This
"optimization" minimizes the number of feedback messages (e.g., NACK)
in the worst-case situation where all receivers generate a NACK ...
... NACK)
in the worst-case situation where all receivers generate a NACK. The
maximum backoff timeout (T_maxBackoff) can be set to control reliable
delivery ...
... }
The number of expected NACK messages generated (N) within the first
round trip time for a single feedback event is approximately:
...
...
Thus the maximum backoff time can be adjusted to tradeoff worst-case
NACK feedback volume versus latency. This is derived from [6] and
...
...
Note that other mechanisms within the protocol may work to reduce
redundant NACK generation further. It is suggested that T_maxBackoff
be selected as an integer multiple of the sender ...
... for operation with multicast (to the group at large) NACK delivery
and a value of K=6 for unicast ...
... delivery
and a value of K=6 for unicast NACK delivery. Alternate values may
be used to for buffer ...
... GRTT) is the maximum backoff time used by the receivers
to initiate NACK transmission, other timeout periods related to the
NACK repair process can be scaled accordingly. One of those timeouts
...
... to initiate NACK transmission, other timeout periods related to the
NACK repair process can be scaled accordingly. One of those timeouts
is the amount of time a receiver should wait after generating a NACK ...
... NACK repair process can be scaled accordingly. One of those timeouts
is the amount of time a receiver should wait after generating a NACK
message before allowing itself to initiate another NACK
...
... receiver should wait after generating a NACK
message before allowing itself to initiate another NACK
backoff/transmission cycle (T_rcvrHoldoff). This delay should be
sufficient for the sender ...
... backoff/transmission cycle (T_rcvrHoldoff). This delay should be
sufficient for the sender to respond to the received NACK with repair
messages. An appropriate value depends upon the amount of time for
the NACK ...
... NACK with repair
messages. An appropriate value depends upon the amount of time for
the NACK to reach the sender and the sender to provide a repair
...
... sender to provide a repair
response. This MUST include any amount of sender NACK aggregation
period during which possible multiple NACKs ...
... NACK aggregation
period during which possible multiple NACKs are accumulated to
determine an efficient repair response. These timeouts are further
discussed in the section below on "Sender ...
... determine an efficient repair response. These timeouts are further
discussed in the section below on "Sender NACK Processing and Repair
Response".
...
... FEC symbol
identifiers. Receivers SHOULD limit transmission of NACKs to only
when the sender's current transmission position exceeds the point to
...
... effective for protocol convergence in high loss conditions when
transmissions of NACKs from other receivers (or indicators from the
sender ...
... Finally, some consideration might be given to using the NACKing
history of receivers to weight their selection of NACK backoff
timeout intervals. For example, if a receiver has historically been
...
... receiver has historically been
experiencing the greatest degree of loss, it may promote itself to
statistically NACK sooner than other receivers. Note this requires
there is correlation over successive intervals of time in the loss
...
... multicast networks. This adjustment of backoff timeout selection may
require the creation of an "early NACK" slot for these historical
NACKers. This additional slot in the NACK backoff window will result
...
... require the creation of an "early NACK" slot for these historical
NACKers. This additional slot in the NACK backoff window will result
in a longer repair cycle process that may not be desirable for some
applications. The resolution of these trade-offs may be dependent
...
... After the random backoff timeout has expired, the receiver will make
a decision on whether to generate a NACK repair request or not (i.e.,
it has been suppressed). The NACK will be suppressed when any of the
...
... a decision on whether to generate a NACK repair request or not (i.e.,
it has been suppressed). The NACK will be suppressed when any of the
following conditions has occurred:
...
... receiver should consider its repair needs only up to the sender
transmission position recorded at the NACK cycle initiation (when
the backoff timer was activated).
...
... receiver may not have
been aware). This "rewind" event can occur any time between 1)
when the NACK cycle was initiated with the backoff timeout
activation and 2) the current moment when the backoff timeout has
expired to suppress the NACK ...
... NACK cycle was initiated with the backoff timeout
activation and 2) the current moment when the backoff timeout has
expired to suppress the NACK. Another NACK cycle must be
initiated by the receiver ...
... activation and 2) the current moment when the backoff timeout has
expired to suppress the NACK. Another NACK cycle must be
initiated by the receiver when the sender ...
... If these conditions have not occurred and the receiver still has
pending repair needs, a NACK message is generated and transmitted.
The NACK should consist of an accumulation of repair needs from the
...
... pending repair needs, a NACK message is generated and transmitted.
The NACK should consist of an accumulation of repair needs from the
receiver's lowest ordinal repair point up to the current sender ...
... receiver's lowest ordinal repair point up to the current sender
transmission sequence position. A single NACK message should be
generated and the NACK message content should be truncated if it
...
... transmission sequence position. A single NACK message should be
generated and the NACK message content should be truncated if it
exceeds the payload size of single protocol ...
...
payload limits occur, the NACK content SHOULD contain requests for
the ordinally lowest repair content needed from the sender.
...
... Inputs:
1) NACK process initiation decision.
2) Recorded sender transmission sequence position.
...
... group size estimate.
5) Application-defined bound on backoff timeout period.
6) NACKs from other receivers.
7) Pending repair indication from sender ...
... 7) Pending repair indication from sender (may be forwarded
NACKs).
8) Current sender transmission sequence position.
...
... NACK Content ...
... dependent upon the data content identification (See Section 3.5
below). At the highest level the NACK content will identify the
sender to which the NACK ...
... NACK content will identify the
sender to which the NACK is addressed and the data transport object
(or stream ...
... the indicated transport entity, the NACK content will then identify
the specific FEC coding blocks and/or symbols it requires to
...
... NORM can be effectively instantiated without a
requirement for reliable NACK delivery using the techniques discussed
here.
...
...
Where FEC-based repair is used, the NACK message content will
minimally need to identify the coding block(s) for which repair is
needed and a count of erasures (missing packets) for the coding
...
... eventually affect repair. For a most efficient repair strategy, the
NACK content will need to also _explicitly_ identify which symbols
(information and/or parity) the receiver requires to successfully
...
... bandwidth*loss characteristics of the network topology), the
NACK content will need to contain _explicit_ coding block and/or
segment loss information so that the sender ...
... repair packets and/or data retransmissions. Explicit loss
information in NACK content may also potentially serve other
purposes. For example, it may be useful for decorrelating loss
characteristics among a group ...
...
When FEC is used and NACK content is designed to contain explicit
repair requests, there is a strategy where the receivers can NACK ...
... NACK content is designed to contain explicit
repair requests, there is a strategy where the receivers can NACK for
specific content that will help facilitate NACK suppression and
...
... receivers can NACK for
specific content that will help facilitate NACK suppression and
repair efficiency. The assumptions for this strategy are that sender
...
...
Receivers then can construct NACK messages requesting sufficient
content to satisfy their repair needs. For example, if the receiver
...
... (i.e., greater than 32 missing symbols in our example), the receiver
will be required to construct a NACK requesting all (32) of the
available parity symbols plus some additional portions of its missing
data symbols in order to reconstruct the block. If this is done
...
... consistently across the receiver group, the resulting NACKs will
comprise a minimal set of sender transmissions to satisfy their
...
... parity content for the FEC coding block to satisfy the erasure repair
needs on the first NACK cycle. If the available number of parity
symbols is insufficient, the receiver will also request the subset of
...
... account the possibly limited repair capability of other FEC types.
On subsequent NACK repair cycles where the receiver may have received
some portion of its previously requested repair content, the receiver ...
... 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 ...
... 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 ...
... NACK operation.
After receipt and accumulation of NACK messages during the
aggregation period, the sender ...
... 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 ...
... receivers
can simply compare NACKs heard from other receivers against their own
calculated repair needs to determine whether they should transmit or
...
... receivers against their own
calculated repair needs to determine whether they should transmit or
suppress their pending NACK messages.
...
... 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
...
... service
model and the format of data content identification the protocol
uses. This NACK format also depends upon the type of FEC encoding
...
... Data Content Identification Hierarchy
The format of NACK messages should meet the following goals:
1) Able to identify transport ...
... sets of symbols,
2) Be simple to process for NACK aggregation and suppression,
...
... aggregation and suppression,
3) Be capable of including NACKs for multiple objects, FEC coding
blocks and/or symbols in a single message, and
...
... data unit (TPDU) identifier for
symbols from a given source. NACK content can be composed of lists
and/or ranges of these TPDU identifiers ...
... and/or ranges of these TPDU identifiers to build up NACK messages to
describe the receivers repair needs. If no hierarchical 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 ...
... Outputs:
1) NACK message with repair requests.
...
... 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 ...
... 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 ...
... 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 ...
... 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 ...
... receiver NACK backoff window ("T_maxBackoff" from Section
3.2.2) and propagation of NACK messages from the receivers to the
sender ...
... network topology with respect to transmission delay.
Thus, if the maximum receiver NACK backoff time is T_maxBackoff =
K*GRTT, the sender ...
... 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
...
... 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 ...
...
This allows for a worst-case propagation time of the receiver's NACK
to the sender, the sender ...
... sender to forward (via multicast) a representation of its aggregated
NACK content to the group to allow for NACK suppression when there is
...
... NACK content to the group to allow for NACK suppression when there is
not multicast connectivity among the receiver ...
... 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
...
... 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 ...
... 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
...
... 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 ...
... 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 ...
... FEC Building Block
These fields have been identified because any generated NACK messages
will use these identifiers in requesting repair or retransmission ...
... identified that can provide great performance enhancements to the
repair process of NACK-oriented and other reliable multicast
protocols [11 ...
... block
size (in symbols). In NORM, parity repair packets generated will
generally be transmitted only in response to NACK repair requests
from receiving nodes ...
... repair packets multiplexed with the regular data symbol transmissions
[14]. This can reduce the amount of NACK traffic generated with
relatively little overhead ...
... members of the group is required to support timer-based NACK
suppression algorithms, timing of sender ...
... responses it has received. A conservative estimate of GRTT is kept
to maximize the efficiency of redundant NACK suppression and repair
aggregation. The update ...
... sender. To control the volume of these receiver-generated messages,
a suppression mechanism similar to that described for NACK
suppression my be used. The "age" of receivers' RTT ...
...
NACK-oriented protocols may benefit from general purpose router
assistance. In particular, additional NACK ...
... NACK-oriented protocols may benefit from general purpose router
assistance. In particular, additional NACK suppression where routers
or intermediate systems can aggregate NACK ...
... NACK suppression where routers
or intermediate systems can aggregate NACK content (or filter
duplicate NACK ...
... NACK content (or filter
duplicate NACK content) from receivers as it is relayed toward the
sender ...
... topology depending
on the repair needs learned from previous receiver NACKs. Both of
these types of assist functions would require router interpretation
...
... negative acknowledgement to achieve reliable data transfer. Properly
designed negative-acknowledgement (NACK)-oriented reliable multicast
...
... session intrusion
and denial of service attacks. A particular threat for NACK based
protocols is that of NACK replay attacks ...
... denial of service attacks. A particular threat for NACK based
protocols is that of NACK replay attacks that would prevent a NORM
sender from making forward progress in transmission. Any standard
...
... replay
attacks are RECOMMENDED for use. Additionally, NORM protocol
instantiations SHOULD consider providing support for their own NACK
replay attack protection when network ...