+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|version| type=5| hdr_len | sequence |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| source_id |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| server_id |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| instance_id | ack_type | ack_id |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| grtt_response_sec |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| grtt_response_usec |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| header extensions (if applicable) |
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ack_payload (if applicable) |
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
NORM_ACK Message Format
The NORM common message header fields serve their usual purposes.
The "server_id", "instance_id", and "grtt_response" fields serve the
same purpose as the corresponding fields in NORM_NACK messages. And
header extensions may be applied to support congestion control
feedback or other functions in the same manner.
The "ack_type" field indicates the nature of the NORM_ACK message.
This directly corresponds to the "ack_type" field of the
NORM_CMD(ACK_REQ) message to which this acknowledgment applies.
The "ack_id" field serves as a sequence number so that the sender can
verify that a NORM_ACK message received actually applies to a current
acknowledgment request. The "ack_id" field is not used in the case
of the NORM_ACK_CC and NORM_ACK_FLUSH acknowledgment types.
The "ack_payload" format is a function of the "ack_type". The
NORM_ACK_CC message has no attached content. Only the NORM_ACK
header applies. In the case of NORM_ACK_FLUSH, a specific
"ack_payload" format is defined:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| fec_id | reserved | object_transport_id |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| fec_payload_id |
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
NORM_ACK_FLUSH "ack_payload" Format
The "object_transport_id" and "fec_payload_id" are used by the
receiver to acknowledge applicable NORM_CMD(FLUSH) messages
transmitted by the sender identified by the "server_id" field.
The "ack_payload" of NORM_ACK messages for application-defined
"ack_type" values is specific to the application but is limited in
size to a maximum the NormSegmentSize of the sender referenced by the
"server_id".
4.4. General Purpose Messages
Some additional message formats are defined for general purpose in
NORM multicast sessions whether the participant is acting as a sender
and/or receiver within the group.
4.4.1. NORM_REPORT Message
This is an optional message generated by NORM participants. This
message could be used for periodic performance reports from receivers
in experimental NORM implementations. The format of this message is
currently undefined. Experimental NORM implementations may define
NORM_REPORT formats as needed for test purposes. These report
messages SHOULD be disabled for interoperability testing between
different NORM implementations.
5. Detailed Protocol Operation
This section describes the detailed interactions of senders and
receivers participating in a NORM session. A simple synopsis of
protocol operation is given here:
1) The sender periodically transmits NORM_CMD(CC) messages as needed
to initialize and collect roundtrip timing and congestion control
feedback from the receiver set.
2) The sender transmits an ordinal set of NormObjects segmented in
the form of NORM_DATA messages labeled with NormTransportIds and
logically identified with FEC encoding block numbers and symbol
identifiers. NORM_INFO messages may optionally precede the
transmission of data content for NORM transport objects.
3) As receivers detect missing content from the sender, they initiate
repair requests with NORM_NACK messages. Note the receivers track
the sender’s most recent objectId::fecPayloadId transmit position
and NACK _only_ for content ordinally prior to that transmit
position. The receivers schedule random backoff timeouts before
generating NORM_NACK messages and wait an appropriate amount of
time before repeating the NORM_NACK if their repair request is not
satisfied.
4) The sender aggregates repair requests from the receivers and
logically "rewinds" its transmit position to send appropriate
repair messages. The sender sends repairs for the earliest
ordinal transmit position first and maintains this ordinal repair
transmission sequence. Previously untransmitted FEC parity
content for the applicable FEC coding block is used for repair
transmissions to the greatest extent possible. If the sender
exhausts its available FEC parity content on multiple repair
cycles for the same coding block, it resorts to an explicit repair
strategy (possibly using parity content) to complete repairs.
(The use of explicit repair is expected to be an exception in
general protocol operation, but the possibility does exist for
extreme conditions). The sender immediately assumes transmission
of new content once it has sent pending repairs.
5) The sender transmits NORM_CMD(FLUSH) messages when it reaches the
end of enqueued transmit content and pending repairs. Receivers
respond to the NORM_CMD(FLUSH) messages with NORM_NACK
transmissions (following the same suppression backoff timeout
strategy as for data) if they require further repair.
6) The sender transmissions are subject to rate control limits
determined by congestion control mechanisms. In the baseline
NORM-CC operation, each sender in a NormSession maintains its own
independent congestion control state. Receivers provide
congestion control feedback in NORM_NACK and NORM_ACK messages.
NORM_ACK feedback for congestion control purposes is governed
using a suppression mechanism similar to that for NORM_NACK
messages.
While this overall concept is relatively simple, there are details to
each of these aspects that need to be addressed for successful,
efficient, robust, and scalable NORM protocol operation.
5.1. Sender Initialization and Transmission
Upon startup, the NORM sender immediately begins sending NORM_CMD(CC)
messages to collect round trip timing and other information from the
potential group. If NORM-CC congestion control operation is enabled,
the NORM-CC Rate header extension MUST be included in these messages.
Congestion control operation SHALL be observed at all times when
operating in the general Internet. Even if congestion control
operation is disabled at the sender, it may be desirable to use the
NORM_CMD(CC) messaging to collect feedback from the group using the
baseline NORM-CC feedback mechanisms. This proactive feedback
collection can be used to establish a GRTT estimate prior to data
transmission and potential NACK operation.
In some cases, applications may wish for the sender to also proceed
with data transmission immediately. In other cases, the sender may
wish to defer data transmission until it has received some feedback
or request from the receiver set indicating that receivers are indeed
present. Note, in some applications (e.g., web push), this
indication may come out-of-band with respect to the multicast session
via other means. As noted, the periodic transmission of NORM_CMD(CC)
messages may precede actual data transmission in order to have an
initial GRTT estimate.
With inclusion of the OPTIONAL NORM FEC Object Transmission
Information Header Extension, the NORM protocol sender message
headers can contain all information necessary to prepare receivers
for subsequent reliable reception. This includes FEC coding
parameters, the sender NormSegmentSize, and other information. If
this header extension is not used, it is presumed that receivers have
received the FEC Object Transmission Information via other means.
Additionally, applications may leverage the use of NORM_INFO messages
associated with the session data objects in the session to provide
application-specific context information for the session and data
being transmitted. These mechanisms allow for operation with minimal
pre-coordination among the senders and receivers.
The NORM sender begins segmenting application-enqueued data into
NORM_DATA segments and transmitting it to the group. The
segmentation algorithm is described in Section 5.1.1. The rate of
transmission is controlled via congestion control mechanisms or is a
fixed rate if desired for closed network operations. The receivers
participating in the multicast group provide feedback to the sender
as needed. When the sender reaches the end of data it has enqueued
for transmission or any pending repairs, it transmits a series of
NORM_CMD(FLUSH) messages at a rate of one per 2*GRTT. Receivers may
respond to these NORM_CMD(FLUSH) messages with additional repair
requests. A protocol parameter "NORM_ROBUST_FACTOR" determines the
number of flush messages sent. If receivers request repair, the
repair is provided and flushing occurs again at the end of repair
transmission. The sender may attach an OPTIONAL "acking_node_list"
to NORM_CMD(FLUSH) containing the NormNodeIds for receivers from
which it expects explicit positive acknowledgment of reception. The
NORM_CMD(FLUSH) message may be also used for this optional function
any time prior to the end of data enqueued for transmission with the
NORM_CMD(FLUSH) messages multiplexed with ongoing data transmissions.
The OPTIONAL NORM positive acknowledgment procedure is described in
Section 5.5.3.
5.1.1. Object Segmentation Algorithm
NORM senders and receivers must use a common algorithm for logically
segmenting transport data into FEC encoding blocks and symbols so
that appropriate NACKs can be constructed to request repair of
missing data. NORM FEC coding blocks are comprised of multi-byte
symbols which are transmitted in the payload of NORM_DATA messages.
Each NORM_DATA message contains one source or encoding symbol and the
NormSegmentSize sender parameter defines the maximum symbol size in
bytes. The FEC encoding type and associated parameters govern the
source block size (number of source symbols per coding block). NORM
senders and receivers use these FEC parameters, along with the
NormSegmentSize and transport object size to compute the source block
structure for transport objects. These parameters are provided in
the FEC Transmission Information for each object. The algorithm
given below is used to compute a source block structure such that all
source blocks are as close to being equal length as possible. This
helps avoid the performance disadvantages of "short" FEC blocks.
Note this algorithm applies only to the statically-sized
NORM_OBJECT_DATA and NORM_OBJECT_FILE transport object types where
the object size is fixed and predetermined. For NORM_OBJECT_STREAM
objects, the object is segmented according to the maximum source
block length given in the FEC Transmission Information, unless the
FEC Payload ID indicates an alternative size for a given block.
The NORM block segmentation algorithm is defined as follows. For a
transport object of a given length (L_obj) in bytes, a first number
of FEC source blocks (N_large) is delineated of a larger block size
(B_large), and a second number of source blocks (N_small) is
delineated of a smaller block size (B_small). Given the maximum FEC
source block size (B_max) and the sender’s NormSegmentSize, the block
segmentation for a given NORM transport object is determined as
follows:
Inputs:
B_max = Maximum source block length (i.e., maximum number of source
symbols per source block)
L_sym = Encoding symbol length in bytes (i.e., NormSegmentSize)
L_obj = Object length in bytes
Outputs:
N_total = The total number of source blocks into which the transport
object is partitioned.
N_large = Number of larger source blocks (first set of blocks)
B_large = Size (in encoding symbols) of the larger source blocks
N_small = Number of smaller source blocks (second set of blocks)
B_small = Size (in encoding symbols) of the smaller source blocks
L_final = Length (in bytes) of the last source symbol of the last
source block (All other symbols are of length L_sym).
Algorithm:
1) The total number of source symbols in the transport object is
computed as: S_total = L_obj/L_sym [rounded up to the nearest
integer]
2) The transport object is partitioned into N_total source blocks,
where: N_total = S_total/B_max [rounded up to the nearest
integer]
3) The average length of a source block is computed as: B_ave =
S_total/N_total (this may be non-integer)
4) The size of the first set of larger blocks is computed as:
B_large = B_ave [rounded up to the nearest integer] (Note it will
always be the case that B_large <= B_max)
5) The size of the second set of smaller blocks is computed as:
B_small = B_ave [rounded down to the nearest integer] (Note if
B_ave is an integer B_small = B_large; otherwise B_small = B_large
- 1)
6) The fractional part of B_ave is computed as: B_fraction = B_ave -
B_small
7) The number of larger source blocks is computed as: N_large =
B_fraction * N_total (Note N_large is an integer in the range 0
through N_total - 1)
8) The number of smaller source blocks is computed as: N_small =
N_total - N_large
9) Each of the first N_large source blocks consists of B_large source
symbols. Each of the remaining N_small source blocks consists of
B_small source symbols. All symbols are L_sym bytes in length
except for the final source symbol of the final source block which
is of length (in bytes):
L_final = L_obj - (N_large*B_large + N_small*B_small - 1) * L_sym
5.2. Receiver Initialization and Reception
The NORM protocol is designed such that receivers may join and leave
the group at will. However, some applications may be constrained
such that receivers need to be members of the group prior to start of
data transmission. NORM applications may use different policies to
constrain the impact of new receivers joining the group in the middle
of a session. For example, a useful implementation policy is for new
receivers joining the group to limit or avoid repair requests for
transport objects already in progress. The NORM sender
implementation may wish to impose additional constraints to limit the
ability of receivers to disrupt reliable multicast performance by
joining, leaving, and rejoining the group often. Different receiver
"join policies" may be appropriate for different applications and/or
scenarios. For general purpose operation, default policy where
receivers are allowed to request repair only for coding blocks with a
NormTransportId and FEC coding block number greater than or equal to
the first non-repair NORM_DATA or NORM_INFO message received upon
joining the group is RECOMMENDED. For objects of type
NORM_OBJECT_STREAM it is RECOMMENDED that the join policy constrain
receivers to start reliable reception at the current FEC coding block
for which non-repair content is received.
5.3. Receiver NACK Procedure
When the receiver detects it is missing data from a sender’s NORM
transmissions, it initiates its NACKing procedure. The NACKing
procedure SHALL be initiated _only_ at FEC coding block boundaries,
NormObject boundaries, and upon receipt of a NORM_CMD(FLUSH) message.
The NACKing procedure begins with a random backoff timeout. The
duration of the backoff timeout is chosen using the "RandomBackoff"
algorithm described in the NORM Building Block document [4] using
(Ksender*GRTTsender) for the "maxTime" parameter and the sender
advertised group size (GSIZEsender) as the "groupSize" parameter.
NORM senders provide values for GRTTsender, Ksender and GSIZEsender
via the "grtt", "backoff", and "gsize" fields of transmitted
messages. The GRTTsender value is determined by the sender based on
feedback it has received from the group while the Ksender and
GSIZEsender values may determined by application requirements and
expectations or ancillary information. The backoff factor "Ksender"
MUST be greater than one to provide for effective feedback
suppression. A value of K = 4 is RECOMMENDED for the Any Source
Multicast (ASM) model while a value of K = 6 is RECOMMENDED for
Single Source Multicast (SSM) operation.
Thus:
T_backoff = RandomBackoff(Ksender*GRTTsender, GSIZEsender)
To avoid the possibility of NACK implosion in the case of sender or
network failure during SSM operation, the receiver SHALL
automatically suppress its NACK and immediately enter the "holdoff"
period described below when T_backoff is greater than (Ksender-
1)*GRTTsender. Otherwise, the backoff period is entered and the
receiver MUST accumulate external pending repair state from NORM_NACK
messages and NORM_CMD(REPAIR_ADV) messages received. At the end of
the backoff time, the receiver SHALL generate a NORM_NACK message
only if the following conditions are met:
1) The sender’s current transmit position (in terms of
objectId::fecPayloadId) exceeds the earliest repair position of
the receiver.
2) The repair state accumulated from NORM_NACK and
NORM_CMD(REPAIR_ADV) messages do not equal or supersede the
receiver’s repair needs up to the sender transmission position at
the time the NACK procedure (backoff timeout) was initiated.
If these conditions are met, the receiver immediately generates a
NORM_NACK message when the backoff timeout expires. Otherwise, the
receiver’s NACK is considered to be "suppressed" and the message is
not sent. At this time, the receiver begins a "holdoff" period
during which it constrains itself to not reinitiate the NACKing
process. The purpose of this timeout is to allow the sender worst-
case time to respond to the repair needs before the receiver requests
repair again. The value of this "holdoff" timeout (T_rcvrHoldoff)
as described in [4] is:
T_rcvrHoldoff =(Ksender+2)*GRTTsender
The NORM_NACK message contains repair request content beginning with
lowest ordinal repair position of the receiver up through the coding
block prior to the most recently heard ordinal transmission position
for the sender. If the size of the NORM_NACK content exceeds the
sender’s NormSegmentSize, the NACK content is truncated so that the
receiver only generates a single NORM_NACK message per NACK cycle for
a given sender. In summary, a single NACK message is generated
containing the receiver’s lowest ordinal repair needs.
For each partially-received FEC coding block requiring repair, the
receiver SHALL, on its _first_ repair attempt for the block, request
the parity portion of the FEC coding block beginning with the lowest
ordinal _parity_ "encoding_symbol_id" (i.e., "encoding_symbol_id" =
"source_block_len") and request the number of FEC symbols
corresponding to its data segment erasure count for the block. On
_subsequent_ repair cycles for the same coding block, the receiver
SHALL request only those repair symbols from the first set it has not
yet received up to the remaining erasure count for that applicable
coding block. Note that the sender may have provided other
different, additional parity segments for other receivers that could
also be used to satisfy the local receiver’s erasure-filling needs.
In the case where the erasure count for a partially-received FEC
coding block exceeds the maximum number of parity symbols available
from the sender for the block (as indicated by the NORM_DATA
"fec_num_parity" field), the receiver SHALL request all available
parity segments plus the ordinally highest missing data segments
required to satisfy its total erasure needs for the block. The goal
of this strategy is for the overall receiver set to request a lowest
common denominator set of repair symbols for a given FEC coding
block. This allows the sender to construct the most efficient repair
transmission segment set and enables effective NACK suppression among
the receivers even with uncorrelated packet loss. This approach also
requires no synchronization among the receiver set in their repair
requests for the sender.
For FEC coding blocks or NormObjects missed in their entirety, the
NORM receiver constructs repair requests with NORM_NACK_BLOCK or
NORM_NACK_OBJECT flags set as appropriate. The request for
retransmission of NORM_INFO is accomplished by setting the
NORM_NACK_INFO flag in a corresponding repair request.
5.4. Sender NACK Processing and Response
The principle goal of the sender is to make forward progress in the
transmission of data its application has enqueued. However, the
sender must occasionally "rewind" its logical transmission point to
satisfy the repair needs of receivers who have NACKed. Aggregation
of multiple NACKs is used to determine an optimal repair strategy
when a NACK event occurs. Since receivers initiate the NACK process
on coding block or object boundaries, there is some loose degree of
synchronization of the repair process even when receivers experience
uncorrelated data loss.
5.4.1. Sender Repair State Aggregation
When a sender is in its normal state of transmitting new data and
receives a NACK, it begins a procedure to accumulate NACK repair
state from NORM_NACK messages before beginning repair transmissions.
Note that this period of aggregating repair state does _not_
interfere with its ongoing transmission of new data.
As described in [4], the period of time during which the sender
aggregates NORM_NACK messages is equal to:
T_sndrAggregate = (Ksender+1)*GRTT
where "Ksender" is the same backoff scaling value used by the
receivers, and "GRTT" is the sender’s current estimate of the group’s
greatest round-trip time.
When this period ends, the sender "rewinds" by incorporating the
accumulated repair state into its pending transmission state and
begins transmitting repair messages. After pending repair
transmissions are completed, the sender continues with new
transmissions of any enqueued data. Also, at this point in time, the
sender begins a "holdoff" timeout during which time the sender
constrains itself from initiating a new repair aggregation cycle,
even if NORM_NACK messages arrive. As described in [4], the value of
this sender "holdoff" period is:
T_sndrHoldoff = (1*GRTT)
If additional NORM_NACK messages are received during this sender