Internet DRAFT - draft-ietf-rmt-norm-bb
draft-ietf-rmt-norm-bb
RMT Working Group B. Adamson/Newlink
INTERNET-DRAFT C. Bormann/Tellique
draft-ietf-rmt-norm-bb-02.txt M. Handley/ACIRI
Expires: January 2002 J. Macker/NRL
July 2001
NACK-Oriented Reliable Multicast (NORM) Protocol Building Blocks
Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other docu-
ments at any time. It is inappropriate to use Internet-Drafts as
reference material or to cite them other than as "work in
progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
Copyright Notice
Copyright (C) The Internet Society (2001). All Rights Reserved.
Abstract
This memo describes issues related to the creation of negative-
acknowledgment (NACK) oriented reliable multicast (NORM) protocols.
The general goals and assumptions for NORM are defined. The tech-
nical challenges related to NACK-oriented (and in some cases gen-
eral) reliable multicast protocol design are identified. These
challenges are resolved into a set of applicable "building blocks"
which are described in further detail. It is anticipated that
these building blocks (as they are further refined and defined in
future revisions of this document) will be useful in generating
different instantiations of reliable multicast protocols.
Adamson, Bormann, et al. Expires January 2002 [Page 1]
Internet Draft NORM Building Blocks July 2001
1.0 Background
Reliable multicast transport is a desirable technology for the
efficient and reliable distribution of data to a group on the
Internet. The complexities of group communication paradigms neces-
sitate different protocol types and instantiations to meet the
range of performance and scalability requirements of different
potential reliable multicast applications and users [Mankin98].
Properly designed negative-acknowledgement (NACK) oriented reliable
multicast (NORM) protocols offer scalability advantages for appli-
cations and/or network topologies where, for various reasons, it
is prohibitive to construct a higher order delivery infrastructure
above the basic Layer 3 IP multicast service (e.g. unicast or
hybrid unicast/multicast data distribution trees). Additionally,
the scalability property of NACK-oriented protocols [Pingali93,
Levine96] may be applicable where broad "fanout" is expected for a
single network hop (e.g. cable-TV data delivery, satellite, or
other broadcast communication communication services). Further-
more, the simplicity of a protocol based on "flat" group-wide mul-
ticast distribution may offer advantages for a broad range of dis-
tributed services or dynamic networks and applications.
While different protocol instantiations may be required to meet
specific application and network architecture demands [Clark90],
there are a number of fundamental components which may be common to
these different instantiations. This document describes the frame-
work and common "building block" components relevant to multicast
protocols based primarily on NACK operation for reliable transport.
2.0 Applicability
Each potential protocol instantiation using the building blocks
presented here (and other applicable building block documents) will
have specific criteria which will influence individual protocol
design. To support the development of applicable building blocks,
it is useful to identify and summarize driving general protocol
design goals and assumptions. These are areas which each protocol
instantiation will need to address in detail. Each building block
description in this document will include a discussion of the
impact of these design criteria. The categories of design criteria
considered here include:
1) Data content model
2) Group membership dynamics
3) Sender/receiver relationships
4) Group size
5) Data delivery performance
6) Network topology
Adamson, Bormann, et al. Expires January 2002 [Page 2]
Internet Draft NORM Building Blocks July 2001
3) Router/intermediate system assistance
In some cases, a building block may be designed to address a wide
range of assumptions while in other cases there will be trade-offs
required to meet different application needs. Where necessary,
building block features will designed to be parametric to meet dif-
ferent requirements. Of course, an underlying goal will be to min-
imize design complexity and to at least recommend default values
for any such parameters which meet a general purpose "bulk data
transfer" requirement in a typical Internet environment.
2.1 Data content model
The implicit goal of a reliable multicast protocol is the reliable
delivery of "data" among a group of members communicating through
IP multicast datagram service. However, the nature of the data
content and the service the application is attempting to provide
can impact design decisions. The service model may range from
long-lived transfer sessions of bulk quantities of data (file
broadcast) to more interactive exhanges of small messages (e.g.
white-boarding, text chat). And within those different models
there are other issues such as the sender's ability to cache
transmitted data (or state referencing it) for retransmission or
repair. The needs for ordering and/or causality in the sequence of
transmissions and receptions among members in the group may be dif-
ferent depending upon data content. The group communication
paradigm differs significantly from the point-to-point model in
that, depending upon the data content type, some receivers may com-
plete reception of a portion of data content and be able to act
upon it before other members have received the content. This may
be acceptable (or even desirable) for some applications but not for
others. These varying requirements drives the need for a number of
different protocol instantiation designs.
A significant challenge in developing generally useful building
block mechanisms is accommodating even a limited range of these
capabilities without defining specific application-level details.
Note that this particular building block "guideline" may be gener-
ally applicable beyond the realm of NACK-oriented reliable multi-
cast.
2.2 Group membership dynamics
Group communication can differ from point-to-point communications
with respect to the fact that even if the composition of the group
changes, the "thread" of communication can still exist. This con-
trasts with the point-to-point communication model where, if either
of the two parties leave, the communication process (exchange of
Adamson, Bormann, et al. Expires January 2002 [Page 3]
Internet Draft NORM Building Blocks July 2001
data) is terminated (or at least paused). Depending upon applica-
tion goals, senders and receivers participating in a reliable mul-
ticast transport "session" may be able to join late, leave, and/or
potentially rejoin while the ongoing group communication "thread"
still remains functional and useful.
Also note that this can impact protocol message content. If "late
joiners" are supported, some amount of additional information may
be placed in message headers to accommodate this functionality.
Alternatively, the information may be sent in its own message (on
demand or intermittently) if the impact to the overhead of typical
message transmissions is deemed too great. Group dynamics can also
impact other protocol mechanisms such as NACK or other timing, con-
gestion control operation, etc.
2.3 Sender/receiver relationships
The relationship of senders and receivers among group members
requires consideration. In some applications, there may be a sin-
gle sender multicasting to a group of receivers. In other cases,
there may be more than one sender or the potential for everyone in
the group to be a sender _and_ receiver of data may exist.
2.4 Group size
Native IP multicast [Deering89] may scale to extremely large group
sizes. It may be desirable for some applications to be able to
scale along with the 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.
However, the potential for router assistance or other non-linear
NACK suppression mechanisms may enable these protocols to scale to
very large group sizes. In large scale cases, it may be pro-
hibitive for members to maintain state on all other members (in
particular, other receivers) in the group. The impact of group
size needs to be considered in the development of generally appli-
cable building blocks.
2.5 Data delivery performance
There is a trade-off between scalability and data delivery latency
when designing NACK-oriented protocols. If NACK suppression is to
be used, there will be some delays built into the NACK generation
and repair transmission process to allow suppression to occur and
for the sender of data to identify appropriate content for effi-
cient 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 and
Adamson, Bormann, et al. Expires January 2002 [Page 4]
Internet Draft NORM Building Blocks July 2001
increased buffering requirements for both senders and receivers.
The building blocks should allow applications to establish bounds
for data delivery performance. Note that application designers
must be aware of the scalabilty trade-off which is made when such
bounds are applied.
2.6 Network topology
The Internet Protocol has historically assumed a role of providing
service across heterogeneous network topologies. It is desirable
that a reliable multicast protocol be capable of effectively oper-
ating across a wide range of the networks to which general purpose
IP service applies. The bandwidth available on the links between
the members of a single group today may vary between low numbers
of kbit/s for wireless links and multiple Gbit/s for high speed LAN
connections, with varying degrees of contention from other flows.
Recently, a number of asymmetric network services including
56K/ADSL modems, CATV Internet service, satellite and other wire-
less communication services have begun to proliferate. Many of
these are inherently broadcast media with potentially large
"fanouts" to which IP multicast service is highly applicable.
Additionally, policy and/or technical issues may result in topolo-
gies where multicast connectivity is limited to a single logical
direction from a specific source or set of sources to the group at
large. Receivers in the group may be restricted to unicast feed-
back for NACKs and other messages. Consideration must be given, in
building block development and protocol design, to the nature of
the underlying networks over which the protocols may be operating.
2.7 Router/Intermediate System Assistance
While intermediate assistance from devices/systems with direct
knowledge of the underlying network topology may used to leverage
the performance and scalability of reliable 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 should be capable of operating without
such assistance but should also be capable of utilizing these fea-
tures when available.
3.0 Building Block Areas
The previous section has presented in general what building blocks
are intended to be and some of the criteria which may affect build-
ing block identification/design. This section describes different
building block areas applicable to NACK-oriented reliable multi-
cast protocols. Some of these areas are specific to NACK-oriented
Adamson, Bormann, et al. Expires January 2002 [Page 5]
Internet Draft NORM Building Blocks July 2001
protocols. Detailed descriptions of such areas are provided
below. In other cases, the areas (e.g. node identifiers, FEC,
etc) may be generally applicable to other forms of reliable multi-
cast. In those cases, the discussion below describes requirements
placed on those other general building block areas from the stand-
point of NACK-oriented reliable multicast.
For the individual building blocks to be incorporated as part of a
specific protocol instantiation, it is expected that a description
of some notional "interface" to the building blocks' functionality
be provided. For example, a building block component may require
some form of "input" from another building block component or
other source in order to perform its function. Any "inputs"
required by each building block component and/or any resultant
"output" provided by the building block will be defined and
described as the building block component's interface definition.
The following building block areas are described below:
(NACK-Oriented Components)
1) Sender transmission
2) NACK-oriented Repair Process
3) "Late-joining" Receiver Policies and Mechanisms
(Generally-applicable Components)
4) Node (member) Identification
5) Data Content Identification
6) Forward Error Correction
7) Round-trip Timing Collection
8) Group Size Determination/Estimation
9) Congestion Control Operation
10) Router/Intermediate System Assistance
11) Additional Protocol Mechanisms
Figure 1 provides an pictoral overview of these building block
areas and their relationships. For example, the content of the
data messages that sender initially transmits depends upon the
"Node Identification", Data Content Identification", "FEC" , and
"Congestion Control components (Note that the rate of message
transmission will generally depend upon the "Congestion Control"
component). Subsequently, the receivers response to these trans-
missions (e.g. NACKing for repair) will depend upon the content of
these transmissions and inputs from other building block compo-
nents. Then, the sender's processing of these responses will feed
back into its transmission strategy.
Application Data
|
Adamson, Bormann, et al. Expires January 2002 [Page 6]
Internet Draft NORM Building Blocks July 2001
V
.---------------------. .-----------------------.
| Node Identification |----------->| Sender Transmission |<------.
'---------------------' _.-' '-----------------------' |
.---------------------. _.-' .' | |
| Data Identification |--' .'' | ("Join" Policy) |
'---------------------' .' ' V |
.---------------------. .' ' .------------------------. |
.->| Congestion Control |-' ' | Receiver NACK-oriented | |
| '---------------------' .' | Repair Process | |
| .---------------------. .' | .------------------. | |
| | FEC |'. | | NACK Initiation | | |
| '---------------------'. '._ | '------------------' | |
| .---------------------. , '-._ | .------------------. | |
'--| RTT Collection |._' '->| | NACK Content | | |
'---------------------' .''. | '------------------' | |
.---------------------. ' ''-._ | .------------------. | |
| Group Size Est. |---'-'---'->| | NACK Suppression | | |
'---------------------''. ' ' | '------------------' | |
.---------------------. ' ' ' '------------------------' |
| Other | ' ' ' | |
'---------------------' ' ' ' | (Router Assistance) |
'. ' ' V |
'.'' .-------------------------. |
'>| Sender NACK Processing |_____/
| and Repair Response |
'-------------------------'
^ ^
| |
.-----------------------------.
| (Security) |
'-----------------------------'
Fig. 1 - NORM Building Block Framework
The components on the left side of this figure represent the components
which may be generally applicable beyond NORM and those on the right are
specific to NORM protocols. Some components (e.g. "Security") will
impact many aspects of the protocol and others such as "Router Assis-
tance" may be more transparent to the core protocol processing. The
sections below discuss issues with regards to these building block com-
ponents and their relationships. Where applicable, specific technical
recommendations are made for mechanisms which will properly satisfy the
goals of reliable multicast bulk transport for the Internet.
3.1 Sender transmission
Adamson, Bormann, et al. Expires January 2002 [Page 7]
Internet Draft NORM Building Blocks July 2001
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 packet sizes determined by application and/or
network architecture requirements. When congestion control mechanisms
are used (recommended), the transmission rate will be controlled by the
congestion control mechanism. It is recommended that all data transmis-
sions from senders be subject to rate limitations determined by the
application or congestion control algorithm. The sender's transmissions
should make good utlization of the available capacity (which may be lim-
ited 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.
In addition to data content, other sender messages or commands may be
employed as part of protocol operation. For NACK-oriented operation,
the reliability of any such commands may depend upon redundant transmis-
sion. Other factors related to NACK-oriented operation may determine
sender transmission formats and methods. Some consideration needs to be
given to the sender's behavior during intermittent idle periods when it
has no data to transmit. While many aspects may be protocol-specific,
there are techniques which may be generally applicable to NACK-oriented
reliable multicast. For example, the periodicity of redundant transmis-
sion of command messages issued by a sender should be dependent upon the
greatest round trip timing estimate and the resultant NACK operation.
More specifically, 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 NACK process described below. For efficiency, the
sender should allow sufficient time between redundant transmissions to
receive any NACK-oriented responses from the receiver set to this com-
mand. Other protocol components may benefit from a similar approach.
Inputs:
1) Data content
2) Segmentation size
3) Transmission rate
4) Application controls
Outputs:
1) Rate-controlled stream of packets with headers uniquely
identifying data or repair content within the context of the
reliable multicast session.
2) Commands indicating sender's status or other transport con-
trol actions to be taken.
Adamson, Bormann, et al. Expires January 2002 [Page 8]
Internet Draft NORM Building Blocks July 2001
3.2 NACK-oriented repair process
The most critical component of the NACK-oriented reliable multicast
protocol building block is the NACK repair process. There are four
primary elements of a general NACK repair process:
1) Method for determining when receivers will initiate the NACK
process in response to sender transmission for which they
need repair.
2) NACK message content.
3) NACK suppression mechanisms to promote scalability of the
protocol.
4) Sender NACK reception, aggregation, and repair response.
3.2.1 NACK Process Initiation
The NACK process (cycle) will be initiated by receivers who detect
they require repair transmissions from a specific sender at defined
opportunities. When FEC is applied, a NACK cycle should only be
initiated when it is known by the receiver that its repair require-
ments exceed the amount of FEC pending transmission for a given
coding block of packets. This may be determined by the receiver if
the sender's transmission advertises the quantity of repair packets
it is already planning to send for a block, and/or at the end of
the current transmission block (if it is indicated) or at the start
of subsequent coding block for packets transmitted within the con-
text of a designed data content set (See object/stream data content
identifier discussion below).
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 use-
ful to limit the initiation opportunities to specific events such
as at the end-of-transmission of an FEC coding block (or alterna-
tively at detection of subsequent coding blocks). This can allow
receivers to aggregate NACK content into a smaller number of NACK
messages. In either case, the NACK cycle should begin with
receivers observing backoff timeouts to facilitate NACK suppression
as described below.
Interface Description
Inputs:
1) Object/stream data content and sequencing identifiers from
sender transmissions.
Outputs:
Adamson, Bormann, et al. Expires January 2002 [Page 9]
Internet Draft NORM Building Blocks July 2001
1) NACK Process Initiation Decision
3.2.2 NACK Content
The content of NACK messages generated by reliable multicast
receivers will include information detailing the current repair
needs of each receiver. 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 data transport object (or stream) within the mul-
ticast session which needs repair. For the indicated transport
entity, the NACK content will then identify the specific coding
blocks and/or segments of coding blocks it needs to reconstruct the
transmitted data. This content may consist FEC block erasure
counts and/or explicit indication of missing blocks or segments of
data and FEC content.
3.2.2 NACK Content Strategies
Where FEC-based repair is used, the NACK message content will need
to identify the coding block(s) for which repair is needed and the
count of erasures (missing packets) in the coding block. Note that
this assumes the FEC algorithm is capable of repairing _any_ loss
combination within the coding block and that the quantity of unique
FEC parity packets the server has available to transmit is essen-
tially unlimited (i.e. the server will always be able to provide
new parity packets in response to anysubsequent repair requests for
the same coding block). In other cases, the NACK content will need
to also _explicitly_ identify which packets (information and/or
parity) the receiver needs to successfully reconstruct the content
of the 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 packet 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.
For cases where the amount of loss is very small with respect to
the coding block size, it may be efficient to simply provide a list
Adamson, Bormann, et al. Expires January 2002 [Page 10]
Internet Draft NORM Building Blocks July 2001
of coding block vector identifiers. However, in many cases, a bit
mask marking the locations of missing packets may be significantly
more efficient for communicating receiver repair needs. And since
the data content is logically divided into coding blocks, a system
of hierarchical bit masks can be used to encode missing content at
the object/stream, FEC block, and individual packet levels. Hier-
archical bit mask encoding can provide compact NACK messages even
in high delay*bandwidth*loss conditions. Bit mask based NACK con-
tent can also be efficiently processed with logical operations dur-
ing protocol operation.
When FEC is used and NACK content is designed to contain explicit
repair requests, there is strategy where the receivers can NACK for
specific content which 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 segments to complete
reliable transfer. Another assumption is that an FEC algorithm
where any parity packet can fill any erasure within the coding
block 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 a coding block to
the group.
In this approach, the sender transmits the data content of the cod-
ing block (and optionally some quantity of parity packets) in its
initial transmission. Note that a 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. The sender transmits
parity vectors from the lowest ordinal part of the parity portion
of the coding block. When the receivers construct explicit NACK
content, they request transmission of only the _upper_ ordinal por-
tion, corresponding to the number of _data_ vectors, of the logical
coding block required to fill their packet erasures (Note this
_may_ include data vectors if there is a smaller number of parity
vectors than data vectors for the selected code, but generally will
consist solely of parity vectors). The receivers can also provide
a count of erasures as a convenience (saves processing time) to the
sender. Upon receipt of the NACK message, the sender will schedule
transmission of fresh, new parity vectors based on the erasure
count _if_ it has a sufficient quantity of vectors which were _not_
previously transmitted and ignore the explicit content requested..
Otherwise, the sender will resort to transmitting the set of repair
vectors requested. With this approach, the sender needs to main-
tain 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 this same algorithm to express their
Adamson, Bormann, et al. Expires January 2002 [Page 11]
Internet Draft NORM Building Blocks July 2001
explict repair needs, NACK suppression among receivers is simpli-
fied 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 General Purpose NACK Content Encapsulation Format
This section describes a general format for encapsulating negative
acknowledgement (NACK) feedback content for reliable data transmis-
sion protocols. This includes protocols which may incorporate for-
ward error correction (FEC) for repair packet generation as well as
those which do not. This NACK format is structured according to a
logical, hierarchical framework where the sender transmits data
optionally in the form of one or more "streams" or "objects", with
each optionally composed of a series of FEC coding "blocks" with
each "block" composed of some number of data transmission segments
with source data and/or FEC parity content. This allows any seg-
ment of transmitted data (or FEC parity) to be hierarchically
addressed, as applicable, by the concatenation of "stream/object",
"block", and "segment" identifiers.
Note that multiple levels of streams and substreams or objects can
be instantiated within a hierarchy as required by protocol instan-
tiations to meet protocol or application needs. Also note that the
notional hierarchy of "streams" and/or "blocks" can be omitted for
protocols which do not employ them and the appropriate subset of
the message scheme described here can still be used for NACK repair
requests. Thus a protocol with a single virtual "stream" would
invoke only the message sets relevant to FEC "blocks" and transmis-
sion "segments".
Figure 2 illustrates this logical hierarchy of transmission content
identification, denoting that the notion streams (or objects)
and/or FEC blocking is optional at the protocol instantiation's
discretion. Since the notion of session "streams" and "blocks" are
optional, the framework degenerates to that of typical transport
data segmentation and reassembly in its simplest form.
Session_
\_
[Stream(s)]_
\_
[FEC Blocks]_
\_
Segments
Adamson, Bormann, et al. Expires January 2002 [Page 12]
Internet Draft NORM Building Blocks July 2001
Figure 2: Hierarchy of Reliable Data Transfer Content
Besides providing a general purpose, standard format for encapsu-
lating NACK content, the format presented here has other beneficial
properties:
1) A variety of forms of repair requests are supported: individ-
ual, ranges, and lists of repair symbols. Also, bitmask
formats for repair needs which can lend themselves to effi-
cient packing and processing are supported.
2) The format is independent of FEC type where FEC is applica-
ble.
3) Intermediate systems can process this format and perform
functions in support of feedback suppression or other proto-
col assistance with minimal side information.
In this specification, it is assumed that any "Streams" (or
Objects) and "FEC Blocks" can be identified with 32-bit numeric
fields. In some protocols, "Segments" may be identified by numeric
fields whose size is dependent upon the FEC coding technique used.
Thus, in this specification, feedback messages with "segment"
repair content identified fall into message categories denoting the
explicit size (in bytes) of segment identifier fields to allow mes-
sage parsing independent of FEC-type knowledge. Currently, segment
identification fields of 1, 2, and 4 bytes (8, 16, 32 bits) are
supported, but additional field sizes could easily be supported.
Additionally, it is understood that the use of "Streams" and/or
"Blocks" may not be applicable to some protocols. In this case,
the specification supports NACK content consisting soley of repair
requests for sets of transmission segments.
3.2.3.1 NACK Content Common Header
A simple common header allows NACK content to be efficiently encap-
sulated by receivers and parsed by senders and intermediate sys-
tems. This header is usually followed by content dependent upon
the header content, including sub-encapsulation of lower-level
NACKs. This header consists of NackType, NackForm, and NackLength
fields as follows:
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| NackType | NackForm | NackLength (bytes) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
enum NackType = {STREAM, BLOCKS, SEGMT1, SEGMT2, SEGMT4, OOB_DATA}
Adamson, Bormann, et al. Expires January 2002 [Page 13]
Internet Draft NORM Building Blocks July 2001
enum NackForm = {SINGLE, RANGE, LIST, MASK, SUBSET, COUNT}
The NackType field is of one of the values: STREAM, BLOCKS,
SEGMT1, SEGMT2, SEGMT4, or OOB_DATA. For example, the "STREAM"
type indicates the Nack is requesting repair transmission for one
or more "stream(s)" (or object) which have been transmitted. The
STREAM type and other NackTypes are described in detail in the sec-
tions below.
The NackForm field is used to describe the format of the content of
the given NACK message. The form "SINGLE" indicates the NACK is a
request for repair of a single unit of the given NackType (STREAM,
BLOCK, SEGMT1, SEGMT2, SEGMT4, or OOB_DATA) identified with appro-
priate fields (Note the "SINGLE" form can also be used for some
"wildcard" requests as described below). The "RANGE" form indi-
cates that repair is requested for a contiguous range of units of
the NackType field and the "LIST" form is used for discrete lists
of units of the NackType. The "MASK" form indicates that bitmask
content to describe the repair needs follows. Bitmask encoding of
repair needs can be efficient in terms of size and processing for
much NACK content. The "SUBSET" form is used to indicate content
comprised of NACKs for units below the level of the given NackType.
The "SUBSET" form provides context for the content with an indenti-
fier for the given NackType. For example, a NACK of {type=STREAM,
form=SUBSET} might encapsulate a NACK of {type=BLOCKS, form=SINGLE}
to denote a missing FEC coding block for the given stream or
object. Note the "COUNT" NackForm is only used with the SEGMTx
NackTypes and is used indicate the number of erasures (missing seg-
ments) in a given FEC coding block. The format for different com-
binations of NackType and NackForm are described in detail below.
The NackLength field is the size of the content attached to the
NACK encapsulation header. This includes the total length of "SUB-
SET" NACK content as well as the fields associated with the given
NACK (not including its own encapsulation header). The NackLength
is in units of bytes. Note in some cases there may be zero content
attached to a given NACK. The NackLength field assists in the
parsing of NACK content. For example, when the NACK content con-
sists of a concatenation of different NACK units (NACK messages,
bit masks, etc), the parser can use the NackLength field to find
the end of the given NACK content (or the beginning of the next set
of content).
3.2.3.2 STREAM NackType
The STREAM NackType is used by receivers to request repair for spe-
cific stream(s) or object(s) in the context of the reliable data
Adamson, Bormann, et al. Expires January 2002 [Page 14]
Internet Draft NORM Building Blocks July 2001
transfer session. Streams (or objects) are indentified by 32-bit
fields. The STREAM NackType may of NackForm SINGLE, RANGE, LIST,
MASK, or SUBSET. The following formats are used for these differ-
ent STREAM Nack forms:
STREAM::SINGLE
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = STREAM | form = SINGLE | NackLength |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| stream/object id* |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Note: The "STREAM::SINGLE" NACK can be used as a "wildcard"
NACK requesting transmission/repair of all content the
sender is willing to send under it's transmission/repair
policies for late-joining receivers. This is done by
setting the NackLength value equal to zero and omitting
the "stream/object id" field.
STREAM::RANGE
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = STREAM | form = RANGE | NackLength |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| start stream/object id |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| end stream/object id |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Adamson, Bormann, et al. Expires January 2002 [Page 15]
Internet Draft NORM Building Blocks July 2001
STREAM::LIST
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = STREAM | form = LIST | NackLength |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| stream index 0 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| stream index 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| stream index N-1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Notes on STREAM::LIST content:
1) The list length can be determined from the NackLength field
by right shifting it 2 places (i.e. divide by 4).
STREAM::MASK
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = STREAM | form = MASK | NackLength |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| mask1 offset (stream/object id) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| mask1 length (bytes) | mask1 data ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| mask2 offset (stream/object id) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| mask2 length (bytes) | mask2 data ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| maskN offset (stream/object id) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| maskN length (bytes) | maskN data ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Adamson, Bormann, et al. Expires January 2002 [Page 16]
Internet Draft NORM Building Blocks July 2001
Notes on STREAM::MASK content:
1) The offset is an index to the starting stream id of the sub-
sequent bitmask.
2) The offset stream id shall be an even multiple of 32 for
alignment.
3) The MASK NackForm content is a concatenation of one or more
bitmasks. The NackLength field can be used by the parser to
determine the number of individual bitmasks included.
STREAM::SUBSET
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = STREAM | form = SUBSET | NackLength |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| stream/object id |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| SubsetType | SubsetForm | SubsetLength |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| subset content ... |
Notes on STREAM::SUBSET content:
1) Valid STREAM::SUBSET NackTypes (i.e. SubsetType) include
STREAM, BLOCKS, SEGMENTS (SEGMT1, SEGMT2, SEGMT4), and
OOB_DATA. (Note that the "STREAM" (stream/object) type can
be a subset of the STREAM type so that protocol instantia-
tions may build multi-level hierarchies of streams, sub-
streams, and objects as needed. This allows the number of
hierarchy levels to be different for different protocols and
maintain protocol-independent parsing of NACK content).
2) The "stream/object id" field gives context for the attached
"subset" NACK content.
3) Multiple "subset" NACKs may be concatenated for the given,
identified stream. The NackLength can be used by the parser
to determine the number of subset items included.
3.2.3.3 BLOCKS NackType
The BLOCKS NackType is used by the receiver to request repair con-
tent for one or more specific FEC coding blocks. The BLOCK Nack-
Type may generally be enclosed as SUBSET content for a STREAM NACK,
but can be a stand-alone NACK type for protocols with a single
implicit transmission stream. FEC blocks are indentified by 32-bit
fields. The BLOCKS NackType may of the forms SINGLE, RANGE, LIST,
MASK, or SUBSET. The "non-SUBSET" forms implicity indicates the
Adamson, Bormann, et al. Expires January 2002 [Page 17]
Internet Draft NORM Building Blocks July 2001
specified FEC coding blocks are missing in entirety while the SUB-
SET form indicates repair is needed only for a portion of the iden-
tified coding block. The same formats as used for the STREAM Nack-
Type are used for the BLOCK NackType except that identifier fields
contain FEC block identifiers instead of stream/object identifiers.
The following formats are used for these different BLOCKS Nack
forms:
BLOCKS::SINGLE
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = BLOCKS | form = SINGLE | NackLength |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| FEC block id |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Note: The "BLOCKS::SINGLE" NACK can be used as a "wildcard"
NACK requesting transmission/repair of all FEC blocks for
an indicated stream/object (if applicable) the sender is
willing to send under it's transmission/repair policies
for late-joining receivers. This is done by setting the
NackLength value equal to zero and omitting the "block
id" field. This NACK method may be useful when a
receiver has only received out-of-band data associated
with a given stream or object and requires all of the
associated content.
BLOCKS::RANGE
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = BLOCKS | form = RANGE | NackLength |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| start FEC block id |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| end FEC block id |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Adamson, Bormann, et al. Expires January 2002 [Page 18]
Internet Draft NORM Building Blocks July 2001
BLOCKS::LIST
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = BLOCKS | form = LIST | NackLength |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| FEC block index 0 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| FEC block index 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| FEC block index N-1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Notes on STREAM::LIST content:
1) The list length can be determined from the NackLength field
by right shifting it 2 places (i.e. divide by 4).
BLOCKS::MASK
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = BLOCKS | form = MASK | NackLength |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| mask1 offset (block id) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| mask1 length (bytes) | mask1 data ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| mask2 offset (block id) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| mask2 length (bytes) | mask2 data ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| maskN offset (block id) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| maskN length (bytes) | maskN data ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Adamson, Bormann, et al. Expires January 2002 [Page 19]
Internet Draft NORM Building Blocks July 2001
Notes on BLOCKS::MASK content:
1) The offset is an index to the starting block id of the subse-
quent bitmask.
2) The offset block id shall be an even multiple of 32 for
alignment.
3) The MASK NackForm content is a concatenation of one or more
bitmasks. The NackLength field can be used by the parser to
determine the number of individual bitmasks included.
BLOCKS::SUBSET
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = BLOCKS | form = SUBSET | NackLength |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| block id |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| SubsetType | SubsetForm | SubsetLength |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| subset content ... |
Notes on BLOCKS::SUBSET content:
1) Valid BLOCKS::SUBSET NackTypes (i.e. SubsetType) include SEG-
MENTS (SEGMT1, SEGMT2, SEGMT4) only.
2) The "block id" field gives context for the attached "subset"
NACK content.
3) Multiple "subset" NACKs may be concatenated for the given,
identified block.
The NackLength can be used by the parser to determine the
number of subset items included.
3.2.3.4 SEGMENTS (SEGMT1, SEGMT2, and SEGMT4) NackTypes
The SEGMENTS NackTypes are used by the receiver to request repair
content for a set of segments possible associated with a given
stream and/or FEC coding block. For protocols employing FEC block-
ing, the SEGMENTS NackTypes may generally be enclosed as SUBSET
content for a BLOCK Nack (which in turn may be enclosed as part of
a STREAM NackType if applicable), but can be a stand-alone NACK
type for protocols with a single implicit transmission stream and
no block-based encoding. Segments are indentified by numeric iden-
tifiers. The appropriate size of segment identifier can be a func-
tion of the FEC encoding technique. For example, segments that are
part of FEC coding blocks up to 256 packets in length may use an
8-bit identifier while larger block codes may require a
Adamson, Bormann, et al. Expires January 2002 [Page 20]
Internet Draft NORM Building Blocks July 2001
correspondingly large segment identification field. For this rea-
son, the SEGMENTS NackType is split into distinct types of SEGMT1,
SEGMT2, and SEGMT4. As shown in the table below, the numeric por-
tion of the NackType name (1, 2, or 4) corresponds to the number of
bytes with which segment identifier fields occupy in the content of
that NackType. These values correspond to 8, 16, or 32 bit indexes
for fields related to segment identification, etc. Segment identi-
fier fields use "Big Endian" ordering of most to least significant
bytes.
+---------+----------------------+
|NackType | Bytes per Segment-Id |
+---------+----------------------+
| SEGMT1 | 1 |
+---------+----------------------+
| SEGMT2 | 2 |
+---------+----------------------+
| SEGMT4 | 4 |
+---------+----------------------+
Note that the use of appropriately sized fields allow for proper
computing alignment of associated message content while maintaining
efficient packing of NACK payload content for small to large block
sizes. If needed, this protocol specification could be easily
extended to include other word sizes (e.g. SEGMT5 for 64-bit index-
ing and alignment of segment identifiers).
The SEGMENTS NackTypes (SEGMT1, SEGMT2, SEGMT4) may of NackForm
SINGLE, RANGE, LIST, or MASK. Formats similar to those used for
the STREAM and BLOCK NackTypes are used with the appropriate inter-
pretation of segment identifier fields. The following formats are
used for these resulting different SEGMENTS NackForms:
SEGMENTS::SINGLE
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = SEGMTx | form = SINGLE | NackLength |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ...segment id... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Note: The "segment id" field is of length 1, 2, or 4 bytes
directly corresponding to the type of SEGMT1, SEGMT2, or
SEGMT4.
Adamson, Bormann, et al. Expires January 2002 [Page 21]
Internet Draft NORM Building Blocks July 2001
SEGMENTS::RANGE
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = SEGMTx | form = RANGE | NackLength |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ...start segment id... | ...end segment id... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Note: The "start segment id" and "end segment id" fields are of
length 1, 2, or 4 bytes directly corresponding to the
type of SEGMT1, SEGMT2, or SEGMT4.
SEGMENTS::LIST
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = SEGMTx | form = LIST | NackLength |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ...segment index 0... | ...segment index 1... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ...segment index N-2... | ...segment index N-2... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Notes on SEGMENTS::LIST content:
1) The "segment index" fields are of length 1, 2, or 4 bytes
directly corresponding to the type of SEGMT1, SEGMT2, or
SEGMT4.
2) The LIST length can be determined from the NackLength field
by right shifting it 0, 1, or 2 places as needed for the
given SEGMTx type (i.e. divide by 1, 2, or 4).
SEGMENTS::MASK
An "erasure count" field is included for SEGMENT NackType content
of NackForm MASK. The "erasure count" field allows the parser of
the NACK message (generally a sender or repairer of data) to
quickly determine FEC repair strategies without needing to count
the "set" portion of the bitmask content. Note that the "erasure
count" can easily be determined for the "RANGE" and "LIST" forms
from the corresponding "end-start+1" or "NackLength" values. The
MASK form can also be used to provide "erasure count only" feedback
by omitting inclusion of bitmask content and setting the NackLength
Adamson, Bormann, et al. Expires January 2002 [Page 22]
Internet Draft NORM Building Blocks July 2001
appropriately small.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = SEGMTx | form = MASK | NackLength |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ...erasure count... | ...mask1 offset (seg id)... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ...mask1 length... | mask1 data ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ...mask2 offset (seg id)... | ...mask2 length... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| mask2 data ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ...maskN offset (seg id)... | ...maskN length... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| maskN data ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Notes on SEGMENTS::MASK content:
1) The "list length" and "segment index" fields are of length 1,
2, or 4 bytes directly corresponding to the type of SEGMT1,
SEGMT2, or SEGMT4.
2) The "offset" (segment id) shall be an even multiple of 8, 16,
or 32 corresponding to NackTypes of SEGMT1, SEGMT2, or
SEGMT4 for computing alignment purposes.
3) The "mask length" field shall be an even multiple of 1, 2, or
4 corresponding to NackTypes of SEGMT1, SEGMT2, or SEGMT4
for computing alignment purposes.
4) The "offset" is an index to the starting block id of the sub-
sequent bitmask.
5) The MASK NackForm content is a concatenation of one or more
bitmasks. The NackLength field can be used by the parser to
determine the number of individual bitmasks included.
Adamson, Bormann, et al. Expires January 2002 [Page 23]
Internet Draft NORM Building Blocks July 2001
SEGMENTS::COUNT
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = SEGMTx | form = COUNT | NackLength |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ...erasure count... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Note: The "erasure count" field is of length 1, 2, or 4 bytes
directly corresponding to the NackType of SEGMT1, SEGMT2,
or SEGMT4.
3.2.3.5 OOB_DATA NackType
The OOB_DATA NackType is used by receivers to request repair of
out-of-band data content associated with a specific stream/object
or with the general context of a reliable data transfer session.
The nature of OOB_DATA is protocol specific, but the NACK format
specified in this document provides a general approach for request-
ing this type of repair. The only NackForm supported for the
OOB_DATA NackType is SINGLE. The OOB_DATA NACK can be transmitted
as a stand-alone NACK message where it is implicitly understood
that the request is for any OOB_DATA content general to the reli-
able data transfer session. Alternatively, the OOB_DATA NackType
can be transmitted as "subset" content of a STREAM NACK when the
receiver is requesting out-of-band data associated with a specific
stream or object within the session.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = O_DATA | form = SINGLE | NackLength = 0 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Adamson, Bormann, et al. Expires January 2002 [Page 24]
Internet Draft NORM Building Blocks July 2001
3.2.3.6 Example NACK Messages:
Request for OOB_DATA associated with a given stream/object:
(stream:1)
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = STREAM | form = SUBSET | NackLength = 8 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| stream/object id = 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = O_DATA | form = SINGLE | NackLength = 0 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Request for a SINGLE segment: (stream:1 block:5 segment:10 seg-
ment_id_length:2)
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = STREAM | form = SUBSET | NackLength = 18 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| stream/object id = 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = BLOCKS | form = SUBSET | NackLength = 10 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| block id = 5 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = SEGMT2 | form = SINGLE | NackLength = 2 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| segId = 10 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Adamson, Bormann, et al. Expires January 2002 [Page 25]
Internet Draft NORM Building Blocks July 2001
Request for a LIST of segments: (stream:1 block:5 seg-
ments:11,12,21,32 segment_id_length:1)
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = STREAM | form = SUBSET | NackLength = 20 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| stream/object id = 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = BLOCKS | form = SUBSET | NackLength = 12 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| block id = 5 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = SEGMT2 | form = LIST | NackLength = 4 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| segId = 11 | segId = 12 | segId = 21 | segId = 32 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Request indicating erasure count for a specfic FEC coding block:
(stream:1 block:5 erasures:4)
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = STREAM | form = SUBSET | NackLength = 17 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| stream/object id = 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = BLOCKS | form = SUBSET | NackLength = 9 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| block id = 5 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = SEGMT1 | form = COUNT | NackLength = 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| count = 4 |
+-+-+-+-+-+-+-+-+
Adamson, Bormann, et al. Expires January 2002 [Page 26]
Internet Draft NORM Building Blocks July 2001
Request with Bitmask indicating repair needs for a specific FEC
block: (stream:1 block:5 segment_id_length:1):
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = STREAM | form = SUBSET | NackLength = 27 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| stream/object id = 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = BLOCKS | form = SUBSET | NackLength = 19 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| block id = 5 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = SEGMT1 | form = MASK | NackLength = 11 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| offset = 0 | erasures = 16 | maskLen = 8 | maskData[0] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| maskData[1] | maskData[2] | maskData[3] | maskData[4] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| maskData[5] | maskData[6] | maskData[7] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Request for range of segments for coding block (no stream/objects):
(block:12 segments:239-283)
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = BLOCKS | form = SUBSET | NackLength = 12 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| block id = 5 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = SEGMT2 | form = RANGE | NackLength = 4 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| start = 239 | end = 283 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Adamson, Bormann, et al. Expires January 2002 [Page 27]
Internet Draft NORM Building Blocks July 2001
Request for range of segments for coding block associated with an
object (or stream) which is a subset of another stream: (stream: 1
object: 342 block:12 segments:143-212)
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = STREAM | form = SUBSET | NackLength = 28 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| stream/object id = 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = STREAM | form = SUBSET | NackLength = 20 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| stream/object id = 342 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = BLOCKS | form = SUBSET | NackLength = 12 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| block id = 5 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type = SEGMT2 | form = RANGE | NackLength = 4 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| start = 143 | end = 212 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
3.2.3 NACK Suppression Mechanisms
A primary NACK suppression mechanism is the use of initial backoff
timeouts by receivers wishing to transmit NACK messages[Floyd95].
Upon expiration of the timeout, a receiver will transmit a NACK
unless the content of the pending repair request is completely
superseded by NACK messages heard from other receivers (when
receivers are multicasting NACKs) or from some indicator from the
sender. (Note: When receivers are unicasting NACK messages, the
sender may facilitate NACK suppression by forwarding appropriate
NACKs it has received to the group at large or provide some other
indicator of the repair information it will be subsequently trans-
mitting).
The backoff timeout periods used by receivers should be indepen-
dently, randomly picked by receivers with an exponential distribu-
tion [Nonnenmacher98]. This results in the bulk 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 dis-
tribution should be determined as a function of the current esti-
mate of sender<->group greatest round trip time (GRTT) and a group
size estimate which determined by other mechanisms within the pro-
tocol (See section below) or preset by the multicast application.
Adamson, Bormann, et al. Expires January 2002 [Page 28]
Internet Draft NORM Building Blocks July 2001
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) can also be controlled to
allow the application or protocol tradeoff NACK latency versus vol-
ume of feedback traffic. A larger value of T will result in a
lower density of feedback traffic for a given repair cycle. A
smaller value of T results in shorter latency which reduces the
buffering requirements of senders and receivers for reliable trans-
port.
Given the receiver group size (R), and maximum allowed backoff
timeout (T), a truncated exponential backoff timeout (t') 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 * (exp(L) - 1) T * (exp(L) - 1) T
3) Transform this random variate to generate the
desired random backoff time (t) with the following
equation:
t' = T/L * ln(x * (exp(L) - 1) * (T/L))
This is a C language function which can be used to perform this
function:
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()
Adamson, Bormann, et al. Expires January 2002 [Page 29]
Internet Draft NORM Building Blocks July 2001
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 code can be used:
double UniformRand(double max)
{
return (max * ((double)rand()/(double)RAND_MAX));
}
The number of expected NACKs generated (N) within the first round
trip time for a single loss event can be approximately expected to
be:
N = exp(1.2 * L / (2*T/GRTT))
Thus the maximum backoff time (T) can be adjusted to tradeoff
worst-case NACK feedback volume versus latency. This is derived
from [Nonnenmacher98] and assumes T >= 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 protocol may
work to reduce redundant NACK generation further.
There are some secondary NACK suppression mechanisms which can also
be considered. For example, the sender's transmissions may follow
an ordinal sequence of transmission (observed through data/repair
content <objectIds> and/or <segmentIds>) which is "rewound" during
repair transmissions. Receivers may wish to limit transmission of
their NACKs only when the sender's current sequence of transmission
passes the point at which the receiver has incomplete transmis-
sions, thus reducing premature requests for repair of data the
sender may be providing 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 mecha-
nism (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
advertisment of the number of FEC packets to be sent for the cur-
rent 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 assumes there is some degree of correlation
over successive intervals of time in the loss experienced by
receivers. 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
Adamson, Bormann, et al. Expires January 2002 [Page 30]
Internet Draft NORM Building Blocks July 2001
result in a longer repair cycle process which 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.
Interface Description
Inputs:
1) Group greatest round trip time estimate (GRTT).
2) Group size estimate.
3) Application-defined bound on backoff timeout period.
4) NACKs from other receivers.
5) Pending repair indication from sender (may be forwarded
NACKs).
6) Current sender transmission sequence position.
Outputs:
1) Yes/no decision to generate NACK message upon backoff timer
expiration.
3.2.4 Sender NACK Processing and 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 effi-
cient 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 pend-
ing repair transmissions as part of the its current transmitted
message content. This can aid some NACK suppression mechanisms.
Alternatively, in the case of unicast feedback from the receiver
set, it may be useful for the sender to forward (via multicast)
superseding NACK messages to the group to allow for NACK suppres-
sion when there is not multicast connectivity among the receiver
set.
When FEC is used, it is beneficial that the sender transmit previ-
ously untransmitted parity content whenever possible. This maxi-
mizes the receiving nodes' ability to reconstruct the entire trans-
mitted content from their individual subsets of received messages.
The transmitted object and/or stream content will be marked with
monotonically increasing sequence numbers (within a reasonably
large ordinal space). If the sender observes the discipline of
transmitting repair for the earliest content first, the receivers
Adamson, Bormann, et al. Expires January 2002 [Page 31]
Internet Draft NORM Building Blocks July 2001
can use a strategy of witholding 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 tim-
ing. This also helps minimize the buffering requirements of
receivers and senders and reduces redundant transmission of data to
the group at large.
Interface Description
Inputs:
1) Receiver NACKs
1) Group timing information
Outputs:
1) Repair messages (FEC and/or Data content retransmission)
3.3 Group "Join" Policies/ Procedures
Consideration should be given to how new receivers join a group
(perhaps where reliable transmission is already in progress) and
beging NACKing for any repair needs. If this is unconstrained, the
dynamics of group membership may impede the application's ability
to meet it goals progressing the transmission of data. Policies
limiting the opportunities at which receivers begin participating
in the NACK process may be used to achieve the desired behavior.
For example, it may be beneficial if receivers only attempt reli-
able reception from a newly-heard sender when upon non-repair
transmissions of data in the first FEC block of an object or logi-
cal portion of a stream. The sender may also implement policies
limiting which receivers from which it will accept NACK requests,
but this may be prohibitive for scalability reasons in some situa-
tions. In some types of bulk transfer applications (and for poten-
tial interactive applications), it may alternatively desirable to
have a looser transport synchronization policy and rely upon ses-
sion management mechanisms to control group dynamics which may
result in poor behavior.
Inputs:
1) Current object/stream data/repair content and sequencing
identifiers from sender transmissions.
Outputs:
Adamson, Bormann, et al. Expires January 2002 [Page 32]
Internet Draft NORM Building Blocks July 2001
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 pro-
vide 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 sev-
eral reasons. These reasons include routing changes for hosts with
multiple interfaces which result 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 ses-
sion 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 be used in NACK messages
generated.
There are two very general types of data which may comprise bulk
transfer session content. These data types are static objects of
finite size and continuous non-finite streams. A given application
may wish to reliably multicast data content using either one or
both of these data models. While it may be possible for some
applications to further generalize this model and provide mecha-
nisms to encapsulate static objects as content embedded within a
stream, there are advantages to many applications to provide dis-
tinct 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-realtime message broad-
casts (e.g. stock ticker) or some content types which are part of
collaborative tools or other more complex applications. And, as
Adamson, Bormann, et al. Expires January 2002 [Page 33]
Internet Draft NORM Building Blocks July 2001
indicated above, some applications may wish to encapsulate other
bulk content (e.g. files) into one more streams within a multicast
session. Additionally, multiple streams can allow for parallized
transmission within the context of a single multicast session.
The components described within this building block draft document
are envisioned to be applicable to both of these models with the
potential for a mix of both types within a single multicast ses-
sion. To support this requirement, the normal data content identi-
fication should include a field to uniquely identify the object or
stream <objectId> within some reasonable temporal or ordinal inter-
val. Note that it is _not_ expected that this data content identi-
fication 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 will generally require seg-
mentation, some form of segment identification <segmentId> must
also be provided. This segment identifier will be relative to any
object or stream identifier which has been provided. Thus, in some
cases, NORM protocol instantiations may be able to receive trans-
missions and request repair for multiple streams and one or more
sets of static objects in parallel. For protocol instantiations
employing FEC the <segmentId> portion of the data content identi-
fier may consist of a logical concatenation of a coding block iden-
tifier <blockId> and identifer for the specific data or parity seg-
ment of the code block. The RMT FEC Building Block (currently
"draft-ietf-rmt-bb-fec-02.txt") provides a standard message format
for identifying FEC transmission content. The "General Purpose
NACK Encapsulation Format" described herein (Section 3.2.2) is com-
patible with the RMT FEC Building Block specification.
Additionally, flags to determine the usage of the content identi-
fier 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 individ-
ual protocol instantiations.
In summary, the following data content identification fields may be
required for NORM protocol data content messages:
1) Source node identifier (<senderId>)
2) Object/Stream identifier (<objectId>), if applicable.
3) FEC Block identifier (<blockId>), if applicable.
4) Segment identifier (<segmentId>)
5) Flags to differentiate interpretation of identifier fields
Adamson, Bormann, et al. Expires January 2002 [Page 34]
Internet Draft NORM Building Blocks July 2001
or identifier structure which implicitly indicates usage.
6) Additional FEC transmission content fields per FEC Building
Block
These fields have been identified since any generated NACK messages
will use these identifiers in requesting repair or retransmission
of data. NORM protocols are expected to greatly benefit from
interaction with other reliable multicast building blocks (Generic
Router Assist(GRA), in particular) and those other building blocks
will need to appropriately consider these anticipated requirements.
3.6 Forward Error Correction
Multiple forward error correction (FEC) approaches have been iden-
tified which can provide great performance enhancements to the
repair process of NACK-oriented and other reliable multicast proto-
cols [Metzner84, Macker97]. NORM protocols can reap additional
benefits since FEC-based repair does not _generally_ require
explicit knowledge of repair content within the bounds of its cod-
ing block size (in packets).
Generally, repair packets generated using FEC algorithms with good
erasure filling properties (e.g. Reed-Solomon) will be transmitted
only in response to NACK repair requests from receiving nodes.
However, there are benefits in some network environments for trans-
mitting some predetermined quantity of FEC repair packets multi-
plexed with the regular data segment transmissions [Gossink98].
This can reduce the amount of NACK traffic generated with rela-
tively 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 which are applica-
ble.
A specific issue related to the use of FEC with NORM is the mecha-
nism used to identify which 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 concate-
nation of <sourceId/objectId/blockId/segmentId> during transport,
it is expected that FEC packets will be identified in a similar
manner. The RMT FEC Building Block specification provides detailed
recommendations concerning application of FEC and standard formats
for related reliable multicast protocol messages.
3.7 Round-trip Timing Collection
Adamson, Bormann, et al. Expires January 2002 [Page 35]
Internet Draft NORM Building Blocks July 2001
The measurement of packet propagation round-trip time (RTT) among
members of the group is required to support NACK suppression algo-
rithms, timing of sender commands or certain repair functions, and
congestion control operation. The nature of the round-trip infor-
mation 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 necessary 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 man-
ner. 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 (or an competed subset) 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 which might be employed for
increased efficiency [Ozdemir99]. And in some cases, there might
be absolute time synchronization among hosts which may simplify RTT
measurement. There are trade-offs in multicast congestion control
design which need further consideration before a universal recom-
mendation on RTT (or GRTT) measurement can be specified. Regard-
less 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 timing of the
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 recep-
tion 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 instantion specification), it will con-
struct a "response" using the formula:
<grttResponse> = <sendTime> + (<currentTime> - <recv_Time>)
Adamson, Bormann, et al. Expires January 2002 [Page 36]
Internet Draft NORM Building Blocks July 2001
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 cur-
rent RTT measurement for the receiver from whom the response was
received using the following formula:
<receiverRtt> = <currentTime> - <grttResponse>
During the each periodic GRTT probing interval, the source keeps
the peak round trip estimate from the set of responses it has
received. The GRTT estimate should be filtered to be conservative
towards maintaining an estimate biased towards the greatest
receiver RTT measurements received. A conservative estimate of
GRTT maximizes the efficiency 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 calculation is greater
than the current GRTT estimate AND current peak, the
response value is immediately fed into the GRTT update fil-
ter given below. In any case, the source records the "peak"
receiver RTT measurement for the current probe interval.
2) At the end of the response collection period (i.e. the GRTT
probe interval), if the recorded "peak" response is less
than the current GRTT estimate AND this is the third consec-
utive collection period with a peak less than the current
GRTT estimate the recorded peak is fed into the GRTT update.
(Implicitly, Rule #1 was applied otherwise so no new update
is required).
3) At the end of the response collection period, the peak
tracking value is set to either ZERO if the "peak" is
greater than or equal to the current GRTT estimate (i.e.
Already incorporated into the filter under Rule #1) or kept
the same if its value is less than the current GRTT estimate
AND was not yet incorporated into the GRTT update filter
according to Rule #2. Thus for decreases in the source's
estimate of GRTT, the "peak" is tracked across three consec-
utive probe intervals. The current MDP implementation uses
the following GRTT update filter to incorporate new peak
responses into the the GRTT estimate:
if (peak > current_estimate)
current_estimate = 0.25 * current_estimate + 0.75 * peak;
Adamson, Bormann, et al. Expires January 2002 [Page 37]
Internet Draft NORM Building Blocks July 2001
else
current_estimate = 0.75 * current_estimate + 0.25 * peak;
This update method is biased towards maintaining an estimate of the
worst-case round trip delay. The reason the GRTT estimate is
reduced only after 3 consecutive collection periods with smaller
response peaks is to be conservative where packet loss may have
resulted in lost response messages. And then the reduction is
additionally conservatively weighted using the averaging filter
from above.
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 unchang-
ing, but be adjusted to track more dynamically during periods of
variation with correspondingly shorter GRTT collection periods.
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 accurate GRTT estimation. The current
mechanism has proved sufficient in simulations and in the environ-
ments in which 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 relaitvely high loss connectivity. The steady-
state probing/update interval may potentially be varied to accommo-
date different levels of expected network dynamics in different
environments.
3.7.2 One-to-Many Receiver RTT Measurement
(TBD - Receivers "ping" sender for RTT measurement, and then
receivers competitively (worst case RTT metric) advertise their
measurements to the sender and optionally group so the sender can
determine GRTT ... Sender should still robustly advertise its cur-
rent GRTT knowledge to the group so group can use appropriate tim-
ing)
3.7.3 Many-to-Many RTT Measurement
(TBD - Describe approach based on Ozdemir99, if appropriate/appli-
cable?)
Adamson, Bormann, et al. Expires January 2002 [Page 38]
Internet Draft NORM Building Blocks July 2001
3.7.4 Sender GRTT Advertisement
To facilitate determistic NORM protocol operation, the sender
should robustly advertise its current estimation of GRTT to the
receiver set. Common, robust knowledge of the sender's current
operating GRTT estimate among the group will allow the protocol to
progress in its most efficient manner. The sender's GRTT estimate
can be robustly advertised to the group by simply embedding the
estimate into all pertinent messages transmitted by the sender.
The overhead of this can be made quite small by quantizing (com-
pressing) the GRTT estimate to a single byte of information. The
following C-lanquage function algorithm allows this to be done over
a wide range of GRTT values while maintaining a greater range of
precision for small GRTT values and less precision for large val-
ues:
unsigned char QuantizeGrtt(double grtt)
{
if (grtt > 1.0e03)
grtt = 1.0e03;
else if (grtt < 1.0e-06)
grtt = 1.0e-06;
if (grtt < 3.3e-05)
return ((unsigned char)(grtt * 1.0e06) - 1);
else
return ((unsigned char)(ceil(255.0.-
(13.0 * log(1.0e03/grtt)))));
}
Note that this function is useful for quantizing GRTT times in the
range of 1 microsecond to 1000 seconds. Of course, NORM protocol
implementations may wish to further constrain advertised GRTT esti-
mates (e.g. limit the maximum value) for practical reasons.
3.8 Group Size Determination/Estimation
(TBD)
3.9 Congestion Control Operation
(TBD - A NACK-oriented protocol may place limitations/requirements
on collection of information to facilitate congestion control of
senders. There are a number of specific issues of TCP-Friendly
Multicast Congestion Control (TFMCC)which must be addressed.)
3.10 Router/Intermediate System assistance
(TBD - NACK-oriented protocols can potentially benefit greatly from
Adamson, Bormann, et al. Expires January 2002 [Page 39]
Internet Draft NORM Building Blocks July 2001
router assistance. In particular, additional NACK suppression
would be beneficial (This may impact how synchronized receiver NACK
cycles are, sender advertisement of NACK-cycle parameters (i.e.
GRTT, group size, etc), NACK content, others)
3.11 Additional protocol mechanisms
(TBD- e.g. positive acknowledgement collection, performance
statistics collection, session management, etc)
4.0 Security Considerations (TBD)
5.0 References
[Mankin98] A. Mankin, A. Romanow, S. Bradner, V. Paxson, "IETF
Criteria for Evaluating Reliable Multicast Transport and Applica-
tion Protocols", RFC 2357, June 1998.
[Pingali93] S. Pingali, D. Towsley, J. Kurose. "A Comparison of
Sender-Initiated and Receiver-Initiated Reliable Multicast Proto-
cols". In Proc. INFOCOM, San Francisco, CA, October 1993.
[Levine96] B.N. Levine, J.J. Garcia-Luna-Aceves. "A Comparison of
Known Classes of Reliable Multicast Protocols", Proc. Interna-
tional Conference on Network Protocols (ICNP-96), Columbus, Ohio,
Oct 29--Nov 1, 1996.
[Clark90] D. Clark, D. Tennenhouse, "Architectural Considerations
for a New Generation of Protocols". In Proc. ACM SIGCOMM, pages
201--208, September 1990.
[Deering89] S. Deering. "Host Extensions for IP Multicasting".
Internet RFC1112, August 1989.
[Floyd95] S. Floyd, V. Jacobson, S. McCanne, C. Liu, and L.
Zhang. "A Reliable Multicast Framework for Light-weight Sessions
and Application Level Framing", Proc. ACM SIGCOMM, August 1995.
[Nonnenmacher98] J. Nonnenmacher and E. W. Biersack, "Optimal
multicast feedback," in IEEE Infocom , (San Francisco, California),
p. 964, March/April 1998.
[Gossink98] D. Gossink, J. Macker, "Reliable Multicast and Inte-
grated Parity Retransmission with Channel Estimation", IEEE GLOBE-
COM 98'.
[Metzner84] J. Metzner, "An Improved Broadcast Retransmission Pro-
tocol", IEEE Transactions on Communications, Vol. Com-32, No.6,
Adamson, Bormann, et al. Expires January 2002 [Page 40]
Internet Draft NORM Building Blocks July 2001
June 1984.
[Macker97a] J. Macker, "Integrated Erasure-Based Coding for Reli-
able Multicast Transmission", IRTF Meeting presentation, March
1997.
[Macker97b] J. Macker, "Reliable Multicast Transport and Integrated
Erasure-based Forward Error Correction", Proc. IEEE MILCOM 97,
October 1997.
[Ozdemir99] V. Ozdemir, S. Muthukrishnan, I. Rhee, "Scalable, Low-
Overhead Network Delay Estimation", NCSU/AT&T White Paper, February
1999.
6.0 Authors' Addresses
Brian Adamson
adamson@itd.nrl.navy.mil
Naval Research Laboratory
Washington, DC, USA, 20375
Carsten Bormann
cabo@tellique.de
Tellique Kommunikationstechnik GmbH
Gustav-Meyer-Allee 25 Geb ude 12
D-13355 Berlin, Germany
Mark Handley
mjh@aciri.org
1947 Center Street, Suite 600
Berkeley, CA 94704
Joe Macker
macker@itd.nrl.navy.mil
Naval Research Laboratory
Washington, DC, USA, 20375
Adamson, Bormann, et al. Expires January 2002 [Page 41]
