Request for Comments: 3940 NRL
Category: Experimental C. Bormann
Universitaet Bremen TZI
M. Handley
UCL
J. Macker
NRL
November 2004
Negative-acknowledgment (NACK)-Oriented
Reliable Multicast (NORM) Protocol
Status of this Memo
This memo defines an Experimental Protocol for the Internet
community. It does not specify an Internet standard of any kind.
Discussion and suggestions for improvement are requested.
Distribution of this memo is unlimited.
Copyright Notice
Copyright (C) The Internet Society (2004).
Abstract
This document describes the messages and procedures of the Negative-
acknowledgment (NACK) Oriented Reliable Multicast (NORM) protocol.
This protocol is designed to provide end-to-end reliable transport of
bulk data objects or streams over generic IP multicast routing and
forwarding services. NORM uses a selective, negative acknowledgment
mechanism for transport reliability and offers additional protocol
mechanisms to allow for operation with minimal "a priori"
coordination among senders and receivers. A congestion control
scheme is specified to allow the NORM protocol to fairly share
available network bandwidth with other transport protocols such as
Transmission Control Protocol (TCP). It is capable of operating with
both reciprocal multicast routing among senders and receivers and
with asymmetric connectivity (possibly a unicast return path) between
the senders and receivers. The protocol offers a number of features
to allow different types of applications or possibly other higher
level transport protocols to utilize its service in different ways.
The protocol leverages the use of FEC-based repair and other IETF
reliable multicast transport (RMT) building blocks in its design.
Table of Contents
1. Introduction and Applicability. . . . . . . . . . . . . . . . 3
1.1. NORM Delivery Service Model. . . . . . . . . . . . . . . 4
1.2. NORM Scalability . . . . . . . . . . . . . . . . . . . . 6
1.3. Environmental Requirements and Considerations. . . . . . 7
2. Architecture Definition . . . . . . . . . . . . . . . . . . . 7
2.1. Protocol Operation Overview. . . . . . . . . . . . . . . 9
2.2. Protocol Building Blocks . . . . . . . . . . . . . . . . 10
2.3. Design Tradeoffs . . . . . . . . . . . . . . . . . . . . 11
3. Conformance Statement . . . . . . . . . . . . . . . . . . . . 12
4. Message Formats . . . . . . . . . . . . . . . . . . . . . . . 13
4.1. NORM Common Message Header and Extensions. . . . . . . . 14
4.2. Sender Messages. . . . . . . . . . . . . . . . . . . . . 16
4.2.1. NORM_DATA Message . . . . . . . . . . . . . . . . 16
4.2.2. NORM_INFO Message . . . . . . . . . . . . . . . . 24
4.2.3. NORM_CMD Messages . . . . . . . . . . . . . . . . 26
4.3. Receiver Messages. . . . . . . . . . . . . . . . . . . . 43
4.3.1. NORM_NACK Message . . . . . . . . . . . . . . . . 43
4.3.2. NORM_ACK Message. . . . . . . . . . . . . . . . . 50
4.4. General Purpose Messages . . . . . . . . . . . . . . . . 52
4.4.1. NORM_REPORT Message . . . . . . . . . . . . . . . 52
5. Detailed Protocol Operation . . . . . . . . . . . . . . . . . 52
5.1. Sender Initialization and Transmission . . . . . . . . . 54
5.1.1. Object Segmentation Algorithm . . . . . . . . . . 55
5.2. Receiver Initialization and Reception. . . . . . . . . . 57
5.3. Receiver NACK Procedure. . . . . . . . . . . . . . . . . 57
5.4. Sender NACK Processing and Response. . . . . . . . . . . 59
5.4.1. Sender Repair State Aggregation . . . . . . . . . 60
5.4.2. Sender FEC Repair Transmission Strategy . . . . . 61
5.4.3. Sender NORM_CMD(SQUELCH) Generation . . . . . . . 62
5.4.4. Sender NORM_CMD(REPAIR_ADV) Generation. . . . . . 62
5.5. Additional Protocol Mechanisms . . . . . . . . . . . . . 63
5.5.1. Greatest Round-trip Time Collection . . . . . . . 63
5.5.2. NORM Congestion Control Operation . . . . . . . . 64
5.5.3. NORM Positive Acknowledgment Procedure. . . . . . 72
5.5.4. Group Size Estimate . . . . . . . . . . . . . . . 74
6. Security Considerations . . . . . . . . . . . . . . . . . . . 75
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 75
8. Suggested Use . . . . . . . . . . . . . . . . . . . . . . . . 75
9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 76
10. References. . . . . . . . . . . . . . . . . . . . . . . . . . 76
10.1. Normative References. . . . . . . . . . . . . . . . . . 76
10.2. Informative References. . . . . . . . . . . . . . . . . 77
11. Authors’ Addresses. . . . . . . . . . . . . . . . . . . . . . 79
Full Copyright Statement. . . . . . . . . . . . . . . . . . . 80
1. Introduction and Applicability
The Negative-acknowledgment (NACK) Oriented Reliable Multicast (NORM)
protocol is designed to provide reliable transport of data from one
or more sender(s) to a group of receivers over an IP multicast
network. The primary design goals of NORM are to provide efficient,
scalable, and robust bulk data (e.g., computer files, transmission of
persistent data) transfer across possibly heterogeneous IP networks
and topologies. The NORM protocol design provides support for
distributed multicast session participation with minimal coordination
among senders and receivers. NORM allows senders and receivers to
dynamically join and leave multicast sessions at will with minimal
overhead for control information and timing synchronization among
participants. To accommodate this capability, NORM protocol message
headers contain some common information allowing receivers to easily
synchronize to senders throughout the lifetime of a reliable
multicast session. NORM is designed to be self-adapting to a wide
range of dynamic network conditions with little or no pre-
configuration. The protocol is purposely designed to be tolerant of
inaccurate timing estimations or lossy conditions that may occur in
many networks including mobile and wireless. The protocol is also
designed to exhibit convergence and efficient operation even in
situations of heavy packet loss and large queuing or transmission
delays.
This document is a product of the IETF RMT WG and follows the
guidelines provided in RFC 3269 [1]. The key words "MUST", "MUST
NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT",
"RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be
interpreted as described in BCP 14, RFC 2119 [2].
Statement of Intent
This memo contains part of the definitions necessary to fully specify
a Reliable Multicast Transport protocol in accordance with RFC 2357.
As per RFC 2357, the use of any reliable multicast protocol in the
Internet requires an adequate congestion control scheme.
While waiting for such a scheme to be available, or for an existing
scheme to be proven adequate, the Reliable Multicast Transport
working group (RMT) publishes this Request for Comments in the
"Experimental" category.
It is the intent of RMT to re-submit this specification as an IETF
Proposed Standard as soon as the above condition is met.
1.1. NORM Delivery Service Model
A NORM protocol instance (NormSession) is defined within the context
of participants communicating connectionless (e.g., Internet Protocol
(IP) or User Datagram Protocol (UDP)) packets over a network using
pre-determined addresses and host port numbers. Generally, the
participants exchange packets using an IP multicast group address,
but unicast transport may also be established or applied as an
adjunct to multicast delivery. In the case of multicast, the
participating NormNodes will communicate using a common IP multicast
group address and port number that has been chosen via means outside
the context of the given NormSession. Other IETF data format and
protocol standards exist that may be applied to describe and convey
the required "a priori" information for a specific NormSession (e.g.,
Session Description Protocol (SDP) [7], Session Announcement Protocol
(SAP) [8], etc.).
The NORM protocol design is principally driven by the assumption of a
single sender transmitting bulk data content to a group of receivers.
However, the protocol MAY operate with multiple senders within the
context of a single NormSession. In initial implementations of this
protocol, it is anticipated that multiple senders will transmit
independent of one another and receivers will maintain state as
necessary for each sender. However, in future versions of NORM, it
is possible that some aspects of protocol operation (e.g., round-trip
time collection) may provide for alternate modes allowing more
efficient performance for applications requiring multiple senders.
NORM provides for three types of bulk data content objects
(NormObjects) to be reliably transported. These types include:
1) static computer memory data content (NORM_OBJECT_DATA type),
2) computer storage files (NORM_OBJECT_FILE type), and
3) non-finite streams of continuous data content (NORM_OBJECT_STREAM
type).
The distinction between NORM_OBJECT_DATA and NORM_OBJECT_FILE is
simply to provide a "hint" to receivers in NormSessions serving
multiple types of content as to what type of storage should be
allocated for received content (i.e., memory or file storage). Other
than that distinction, the two are identical, providing for reliable
transport of finite (but potentially very large) units of content.
These static data and file services are anticipated to be useful for
multicast-based cache applications with the ability to reliably
provide transmission of large quantities of static data. Other types
of static data/file delivery services might make use of these
transport object types, too. The use of the NORM_OBJECT_STREAM type
is at the application’s discretion and could be used to carry static
data or file content also. The NORM reliable stream service opens up
additional possibilities such as serialized reliable messaging or
other unbounded, perhaps dynamically produced content. The
NORM_OBJECT_STREAM provides for reliable transport analogous to that
of the Transmission Control Protocol (TCP), although NORM receivers
will be able to begin receiving stream content at any point in time.
The applicability of this feature will depend upon the application.
The NORM protocol also allows for a small amount of "out-of-band"
data (sent as NORM_INFO messages) to be attached to the data content
objects transmitted by the sender. This readily-available "out-of-
band" data allows multicast receivers to quickly and efficiently
determine the nature of the corresponding data, file, or stream bulk
content being transmitted. This allows application-level control of
the receiver node’s participation in the current transport activity.
This also allows the protocol to be flexible with minimal pre-
coordination among senders and receivers. The NORM_INFO content is
designed to be atomic in that its size MUST fit into the payload
portion of a single NORM message.
NORM does _not_ provide for global or application-level
identification of data content within in its message headers. Note
the NORM_INFO out-of-band data mechanism could be leveraged by the
application for this purpose if desired, or identification could
alternatively be embedded within the data content. NORM does
identify transmitted content (NormObjects) with transport identifiers
that are applicable only while the sender is transmitting and/or
repairing the given object. These transport data content identifiers
(NormTransportIds) are assigned in a monotonically increasing fashion
by each NORM sender during the course of a NormSession. Each sender
maintains its NormTransportId assignments independently so that
individual NormObjects may be uniquely identified during transport
with the concatenation of the sender session-unique identifier
(NormNodeId) and the assigned NormTransportId. The NormTransportIds
are assigned from a large, but fixed, numeric space in increasing
order and may be reassigned during long-lived sessions. The NORM
protocol provides mechanisms so that the sender application may
terminate transmission of data content and inform the group of this
in an efficient manner. Other similar protocol control mechanisms
(e.g., session termination, receiver synchronization, etc.) are
specified so that reliable multicast application variants may
construct different, complete bulk transfer communication models to
meet their goals.
To summarize, the NORM protocol provides reliable transport of
different types of data content (including potentially mixed types).
The senders enqueue and transmit bulk content in the form of static
data or files and/or non-finite, ongoing stream types. NORM senders
provide for repair transmission of data and/or FEC content in
response to NACK messages received from the receiver group.
Mechanisms for "out-of-band" information and other transport control
mechanisms are specified for use by applications to form complete
reliable multicast solutions for different purposes.
1.2. NORM Scalability
Group communication scalability requirements lead to adaptation of
negative acknowledgment (NACK) based protocol schemes when feedback
for reliability is required [9]. NORM is a protocol centered around
the use of selective NACKs to request repairs of missing data. NORM
provides for the use of packet-level forward error correction (FEC)
techniques for efficient multicast repair and optional proactive
transmission robustness [10]. FEC-based repair can be used to
greatly reduce the quantity of reliable multicast repair requests and
repair transmissions [11] in a NACK-oriented protocol. The principal
factor in NORM scalability is the volume of feedback traffic
generated by the receiver set to facilitate reliability and
congestion control. NORM uses probabilistic suppression of redundant
feedback based on exponentially distributed random backoff timers.
The performance of this type of suppression relative to other
techniques is described in [12]. NORM dynamically measures the
group’s roundtrip timing status to set its suppression and other
protocol timers. This allows NORM to scale well while maintaining
reliable data delivery transport with low latency relative to the
network topology over which it is operating.
Feedback messages can be either multicast to the group at large or
sent via unicast routing to the sender. In the case of unicast
feedback, the sender "advertises" the feedback state to the group to
facilitate feedback suppression. In typical Internet environments,
it is expected that the NORM protocol will readily scale to group
sizes on the order of tens of thousands of receivers. A study of the
quantity of feedback for this type of protocol is described in [13].
NORM is able to operate with a smaller amount of feedback than a
single TCP connection, even with relatively large numbers of
receivers. Thus, depending upon the network topology, it is possible
that NORM may scale to larger group sizes. With respect to computer
resource usage, the NORM protocol does _not_ require that state be
kept on all receivers in the group. NORM senders maintain state only
for receivers providing explicit congestion control feedback. NORM
receivers must maintain state for each active sender. This may
constrain the number of simultaneous senders in some uses of NORM.
1.3. Environmental Requirements and Considerations
All of the environmental requirements and considerations that apply
to the RMT NORM Building Block [4] and the RMT FEC Building Block [5]
also apply to the NORM protocol.
The NORM protocol SHALL be capable of operating in an end-to-end
fashion with no assistance from intermediate systems beyond basic IP
multicast group management, routing, and forwarding services. While
the techniques utilized in NORM are principally applicable to "flat"
end-to-end IP multicast topologies, they could also be applied in the
sub-levels of hierarchical (e.g., tree-based) multicast distribution
if so desired. NORM can make use of reciprocal (among senders and
receivers) multicast communication under the Any-Source Multicast
(ASM) model defined in RFC 1112 [3], but SHALL also be capable of
scalable operation in asymmetric topologies such as Source Specific
Multicast (SSM) [14] where there may only be unicast routing service
from the receivers to the sender(s).
NORM is compatible with IPv4 and IPv6. Additionally, NORM may be
used with networks employing Network Address Translation (NAT)
providing the NAT device supports IP multicast and/or can cache UDP
traffic source port numbers for remapping feedback traffic from
receivers to the sender(s).
2. Architecture Definition
A NormSession is comprised of participants (NormNodes) acting as
senders and/or receivers. NORM senders transmit data content in the
form of NormObjects to the session destination address and the NORM
receivers attempt to reliably receive the transmitted content using
negative acknowledgments to request repair. Each NormNode within a
NormSession is assumed to have a preselected unique 32-bit identifier
(NormNodeId). NormNodes MUST have uniquely assigned identifiers
within a single NormSession to distinguish between possible multiple
senders and to distinguish feedback information from different
receivers. There are two reserved NormNodeId values. A value of
0x00000000 is considered an invalid NormNodeId value and a value of
0xffffffff is a "wildcard" NormNodeId. While the protocol does not
preclude multiple sender nodes concurrently transmitting within the
context of a single NORM session (i.e., many-to-many operation), any
type of interactive coordination among NORM senders is assumed to be
controlled by the application or higher protocol layer. There are
some optional mechanisms specified in this document that can be
leveraged for such application layer coordination.
As previously noted, NORM allows for reliable transmission of three
different basic types of data content. The first type is
NORM_OBJECT_DATA, which is used for static, persistent blocks of data
content maintained in the sender’s application memory storage. The
second type is NORM_OBJECT_FILE, which corresponds to data stored in
the sender’s non-volatile file system. The NORM_OBJECT_DATA and
NORM_OBJECT_FILE types both represent "NormObjects" of finite but
potentially very large size. The third type of data content is
NORM_OBJECT_STREAM, which corresponds to an ongoing transmission of
undefined length. This is analogous to the reliable stream service
provide by TCP for unicast data transport. The format of the stream
content is application-defined and may be byte or message oriented.
The NORM protocol provides for "flushing" of the stream to expedite
delivery or possibly enforce application message boundaries. NORM
protocol implementations may offer either (or both) in-order delivery
of the stream data to the receive application or out-of-order (more
immediate) delivery of received segments of the stream to the
receiver application. In either case, NORM sender and receiver
implementations provide buffering to facilitate repair of the stream
as it is transported.
All NormObjects are logically segmented into FEC coding blocks and
symbols for transmission by the sender. In NORM, an FEC encoding
symbol directly corresponds to the payload of NORM_DATA messages or
"segment". Note that when systematic FEC codes are used, the payload
of NORM_DATA messages sent for the first portion of a FEC encoding
block are source symbols (actual segments of original user data),
while the remaining symbols for the block consist of parity symbols
generated by FEC encoding. These parity symbols are generally sent
in response to repair requests, but some number may be sent
proactively at the end each encoding block to increase the robustness
of transmission. When non-systematic FEC codes are used, all symbols
sent consist of FEC encoding parity content. In this case, the
receiver must receive a sufficient number of symbols to reconstruct
(via FEC decoding) the original user data for the given block. In
this document, the terms "symbol" and "segment" are used
interchangeably.
Transmitted NormObjects are temporarily yet uniquely identified
within the NormSession context using the given sender’s NormNodeId,
NormInstanceId, and a temporary NormObjectTransportId. Depending
upon the implementation, individual NORM senders may manage their
NormInstanceIds independently, or a common NormInstanceId may be
agreed upon for all participating nodes within a session if needed as
a session identifier. NORM NormObjectTransportId data content
identifiers are sender-assigned and applicable and valid only during
a NormObject’s actual _transport_ (i.e., for as long as the sender is
transmitting and providing repair of the indicated NormObject). For
a long-lived session, the NormObjectTransportId field can wrap and
previously-used identifiers may be re-used. Note that globally
unique identification of transported data content is not provided by
NORM and, if required, must be managed by the NORM application. The
individual segments or symbols of the NormObject are further
identified with FEC payload identifiers which include coding block
and symbol identifiers. These are discussed in detail later in this
document.
2.1. Protocol Operation Overview
A NORM sender primarily generates messages of type NORM_DATA. These
messages carry original data segments or FEC symbols and repair
segments/symbols for the bulk data/file or stream NormObjects being
transferred. By default, redundant FEC symbols are sent only in
response to receiver repair requests (NACKs) and thus normally little
or no additional transmission overhead is imposed due to FEC
encoding. However, the NORM implementation MAY be optionally