description of these areas and their role in the NORM protocol is
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.,
"Security") impact many aspects of the protocol, and others such as
"Router Assistance" may be more transparent to the core protocol
processing. The sections below describe the "NORM Sender
Transmission", "NORM Repair Process", and "RTT Collection" building
blocks in detail. The relationships to and among the other building
block areas are also discussed, focusing on issues applicable to NORM
protocol design. Where applicable, specific technical
recommendations are made for mechanisms that will properly satisfy
the goals of NORM transport for the Internet.
3.1. NORM Sender Transmission
NORM senders will transmit data content to the multicast session.
The data content will be application dependent. The sender will
transmit data content at a rate, and with message sizes, determined
by application and/or network architecture requirements. Any FEC
encoding of sender transmissions SHOULD conform with the guidelines
of [9]. When congestion control mechanisms are needed (REQUIRED for
general Internet operation), NORM transmission SHALL be controlled by
the congestion control mechanism. In any case, it is RECOMMENDED
that all data transmissions from NORM senders be subject to rate
limitations determined by the application or congestion control
algorithm. The sender’s transmissions SHOULD make good utilization
of the available capacity (which may be limited by the application
and/or by congestion control). As a result, it is expected there
will be overlap and multiplexing of new data content transmission
with repair content. Other factors related to application operation
may determine sender transmission formats and methods. For example,
some consideration needs to be given to the sender’s behavior during
intermittent idle periods when it has no data to transmit.
In addition to data content, other sender messages or commands may be
employed as part of protocol operation. These messages may occur
outside of the scope of application data transfer. In NORM
protocols, reliability of such protocol messages may be attempted by
redundant transmission when positive acknowledgement is prohibitive
due to group size scalability concerns. Note that protocol design
SHOULD provide mechanisms for dealing with cases where such messages
are not received by the group. As an example, a command message
might be redundantly transmitted by a sender to indicate that it is
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
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.
In general, when there is any resultant NACK or other feedback
operation, the timing of redundant transmission of control messages
issued by a sender and other NORM protocol timeouts should be
dependent upon the group greatest round trip timing (GRTT) estimate
and any expected resultant NACK or other feedback operation. The
NORM GRTT is an estimate of the worst-case round-trip timing from a
sender to any receivers in the group. It is assumed that the GRTT
interval is a conservative estimate of the maximum span (with respect
to delay) of the multicast group across a network topology with
respect to given sender. NORM instantiations SHOULD be able to
dynamically adapt to a wide range of multicast network topologies.
Sender Transmission Interface Description
Inputs:
1) Application data and control
2) Sender node identifier
3) Data identifiers
4) Segmentation and FEC parameters
5) Transmission rate
6) Application controls
7) Receiver feedback messages (e.g., NACKs)
Outputs:
1) Controlled transmission of messages with headers uniquely
identifying data or repair content within the context of the
NORM session.
2) Commands indicating sender’s status or other transport
control actions to be taken.
3.2. NORM Repair Process
A critical component of NORM protocols is the NACK repair process.
This includes the receiver’s role in detecting and requesting repair
needs, and the sender’s response to such requests. There are four
primary elements of the NORM repair process:
1) Receiver NACK process initiation,
3) NACK suppression,
2) NACK message content,
4) Sender NACK processing and response.
3.2.1. Receiver NACK Process Initiation
The NORM NACK process (cycle) will be initiated by receivers that
detect a need for repair transmissions from a specific sender to
achieve reliable reception. When FEC is applied, a receiver should
initiate the NACK process only when it is known its repair
requirements exceed the amount of pending FEC transmission for a
given coding block of data content. This can be determined at the
end of the current transmission block (if it is indicated) or upon
the start of reception of a subsequent coding block or transmission
object. This implies the NORM data content is marked to identify its
FEC block number and that ordinal relationship is preserved in order
of transmission.
Alternatively, if the sender’s transmission advertises the quantity
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 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
to limit NACK process initiation to specific events such as at the
end-of-transmission of an 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
implicit loose 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
sender to determine its current repair needs. When FEC is employed,
it is expected that the history will correspond to a record of
pending or partially-received coding blocks.
For probabilistic, timer-base suppression of feedback, the NACK cycle
should begin with receivers observing backoff timeouts. In
conjunction with initiating this backoff timeout, it is important
that the 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
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 during the time a NACK message propagates
across the network to the sender and other receivers.
Receiver NACK Process Initiation Interface Description
Inputs:
1) Sender data content with sequencing identifiers from sender
transmissions.
2) History of content received from sender.
Outputs:
1) NACK process initiation decision
2) Recorded sender transmission sequence position.
3.2.2. NACK Suppression
An effective NORM feedback suppression mechanism is the use of random
backoff timeouts prior to NACK transmission by receivers requiring
repairs [10]. Upon expiration of the backoff timeout, a receiver
will request repairs unless its pending repair needs have been
completely superseded by NACK messages heard from other receivers
(when receivers are multicasting NACKs) or from some indicator from
the sender. When receivers are unicasting NACK messages, the sender
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
transmitting.
For effective and scalable suppression performance, the backoff
timeout periods used by receivers should be independently, randomly
picked by receivers with a truncated exponential distribution [6].
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 mean of the distribution should be
determined as a function of the current estimate of sender<->group
GRTT and a group size estimate that is determined by other mechanisms
within the protocol or preset by the multicast application.
A simple algorithm can be constructed to generate random backoff
timeouts with the appropriate distribution. Additionally, the
algorithm may be designed to optimize the backoff distribution given
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. The
maximum backoff timeout (T_maxBackoff) can be set to control reliable
delivery latency versus volume of feedback traffic. A larger value
of T_maxBackoff will result in a lower density of feedback traffic
for a given repair cycle. A smaller value of T_maxBackoff results in
shorter latency which also reduces the buffering requirements of
senders and receivers for reliable transport.
Given the receiver group size (R), and maximum allowed backoff
timeout (T_maxBackoff), random backoff timeouts (t’) with a truncated
exponential distribution can be picked with the following algorithm:
1) Establish an optimal mean (L) for the exponential backoff based on
the group size:
L = ln(R) + 1
2) Pick a random number (x) from a uniform distribution over a range
of:
L L L
-------------------- to -------------------- + ----------
T_maxBackoff*(exp(L)-1) T_maxBackoff*(exp(L)-1) T_maxBackoff
3) Transform this random variate to generate the desired random
backoff time (t’) with the following equation:
t’ = T_maxBackoff/L * ln(x * (exp(L) - 1) * (T_maxBackoff/L))
This C language function can be used to generate an appropriate
random backoff time interval:
double RandomBackoff(double maxTime, double groupSize)
{
double lambda = log(groupSize) + 1;
double x = UniformRand(lambda/maxTime) +
lambda / (maxTime*(exp(lambda)-1));
return ((maxTime/lambda) *
log(x*(exp(lambda)-1)*(maxTime/lambda)));
} // end RandomBackoff()
where UniformRand(double max) returns random numbers with a uniform
distribution from the range of 0..max. For example, based on the
POSIX "rand()" function, the following C code can be used:
double UniformRand(double max)
{
return (max * ((double)rand()/(double)RAND_MAX));
}
The number of expected NACK messages generated (N) within the first
round trip time for a single feedback event is approximately:
N = exp(1.2 * L / (2*T_maxBackoff/GRTT))
Thus the maximum backoff time can be adjusted to tradeoff worst-case
NACK feedback volume versus latency. This is derived from [6] and
assumes T_maxBackoff >= GRTT, and L is the mean of the distribution
optimized for the given group size as shown in the algorithm above.
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’s current advertised
GRTT estimate such that:
T_maxBackoff = K * GRTT ;where K >= 1
For general Internet operation, a default value of K=4 is RECOMMENDED
for operation with multicast (to the group at large) NACK delivery
and a value of K=6 for unicast NACK delivery. Alternate values may
be used to for buffer utilization, reliable delivery latency and
group size scalability tradeoffs.
Given that (K*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
is the amount of time a 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 to respond to the received 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
response. This MUST include any amount of sender 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 NACK Processing and Repair
Response".
There are also secondary measures that can be applied to improve the
performance of feedback suppression. For example, the sender’s data
content transmissions can follow an ordinal sequence of transmission.
When repairs for data content occur, the receiver can note that the
sender has "rewound" its data content transmission position by
observing the data object, FEC block number, and FEC symbol
identifiers. Receivers SHOULD limit transmission of NACKs to only
when the sender’s current transmission position exceeds the point to
which the receiver has incomplete reception. This reduces premature
requests for repair of data the sender may be planning to provide in
response to other receiver requests. This mechanism can be very
effective for protocol convergence in high loss conditions when
transmissions of NACKs from other receivers (or indicators from the
sender) are lost. Another mechanism (particularly applicable when
FEC is used) is for the sender to embed an indication of impending
repair transmissions in current packets sent. For example, the
indication may be as simple as an advertisement of the number of FEC
packets to be sent for the current applicable coding block.
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
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
experienced by a receiver. Such correlation MAY not be present in
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
in a longer repair cycle process that may not be desirable for some
applications. The resolution of these trade-offs may be dependent
upon the protocol’s target application set or network.
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
following conditions has occurred:
1) The accumulated state of NACKs heard from other receivers (or
forwarding of this state by the sender) is equal to or supersedes
the repair needs of the local receiver. Note that the local
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).
2) The sender’s data content transmission position "rewinds" to a
point ordinally less than that of the lowest sequence position of
the local receiver’s repair needs. (This detection of sender
"rewind" indicates the sender has already responded to other
receiver repair needs of which the local 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. Another NACK cycle must be
initiated by the receiver when the sender’s transmission sequence
position exceeds the receiver’s lowest ordinal repair point. Note
it is possible that the local receiver may have had its repair
needs satisfied as a result of the sender’s response to the repair
needs of other receivers and no further NACKing is required.
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
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
exceeds the payload size of single protocol message. When such NACK
payload limits occur, the NACK content SHOULD contain requests for
the ordinally lowest repair content needed from the sender.
NACK Suppression Interface Description
Inputs:
1) NACK process initiation decision.
2) Recorded sender transmission sequence position.
3) Sender GRTT.
4) Sender group size estimate.
5) Application-defined bound on backoff timeout period.
6) NACKs from other receivers.
7) Pending repair indication from sender (may be forwarded
NACKs).
8) Current sender transmission sequence position.
Outputs:
1) Yes/no decision to generate NACK message upon backoff timer
expiration.
3.2.3. NACK Content
The content of NACK messages generated by reliable multicast
receivers will include information detailing their current repair
needs. The specific information depends on the use and type of FEC
in the NORM repair process. The identification of repair needs is
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 is addressed and the data transport object
(or stream) within the sender’s transmission that needs repair. For
the indicated transport entity, the NACK content will then identify
the specific FEC coding blocks and/or symbols it requires to
reconstruct the complete transmitted data. This content may consist
of FEC block erasure counts and/or explicit indication of missing
blocks or symbols (segments) of data and FEC content. It should also
be noted that NORM can be effectively instantiated without a
requirement for reliable NACK delivery using the techniques discussed
here.
3.2.3.1. NACK and FEC Repair Strategies
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
block. An exact count of erasures implies the FEC algorithm is
capable of repairing _any_ loss combination within the coding block.
This count may need to be adjusted for some FEC algorithms.
Considering that multiple repair rounds may be required to
successfully complete repair, an erasure count also implies that the
quantity of unique FEC parity packets the server has available to
transmit is essentially unlimited (i.e., the server will always be
able to provide new, unique, previously unsent parity packets in
response to any subsequent repair requests for the same coding
block). Alternatively, the sender may "round-robin" transmit through
its available set of FEC symbols for a given coding block, and
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
reconstruct the content of the coding block. This will be
particularly true of small to medium size block FEC codes (e.g., Reed
Solomon) that are capable of provided a limited number of parity
symbols per FEC coding block.
When FEC is not used as part of the repair process, or the protocol
instantiation is required to provide reliability even when the sender
has transmitted all available parity for a given coding block (or the
sender’s ability to buffer transmission history is exceeded by the
delay*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 can provide appropriate
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 of receivers to help differentiate
candidate congestion control bottlenecks among the receiver set.
When FEC is used and 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
repair efficiency. The assumptions for this strategy are that sender
may potentially exhaust its supply of new, unique parity packets
available for a given coding block and be required to explicitly
retransmit some data or parity symbols to complete reliable transfer.
Another assumption is that an FEC algorithm where any parity packet
can fill any erasure within the coding block (e.g., Reed Solomon) is
used. The goal of this strategy is to make maximum use of the
available parity and provide the minimal amount of data and repair
transmissions during reliable transfer of data content to the group.
When systematic FEC codes are used, the sender transmits the data
content of the coding block (and optionally some quantity of parity
packets) in its initial transmission. Note that a systematic FEC
coding block is considered to be logically made up of the contiguous
set of data vectors plus parity vectors for the given FEC algorithm
used. For example, a coding scheme that provides for 64 data symbols
and 32 parity symbols per coding block would contain FEC symbol
identifiers in the range of 0 to 95.
Receivers then can construct NACK messages requesting sufficient
content to satisfy their repair needs. For example, if the receiver
has three erasures in a given received coding block, it will request
transmission of the three lowest ordinal parity vectors in the coding
block. In our example coding scheme from the previous paragraph, the
receiver would explicitly request parity symbols 64 to 66 to fill its
three erasures for the coding block. Note that if the receiver’s
loss for the coding block exceeds the available parity quantity
(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
repair needs.
In summary, the rule is to request the lower ordinal portion of the
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
ordinally highest missing data symbols to cover what the parity
symbols will not fill. Note this strategy assumes FEC codes such as
Reed-Solomon for which a single parity symbol can repair any erased
symbol. This strategy would need minor modification to take into
account the possibly limited repair capability of other FEC types.
On subsequent NACK repair cycles where the receiver may have received