RMT Working Group B. Adamson/NRL INTERNET-DRAFT C. Bormann/Tellique draft-ietf-rmt-pi-norm-05.txt M. Handley/ACIRI Expires: May 2003 J. Macker/NRL November 2002 NACK-Oriented Reliable Multicast Protocol (NORM) 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 (2002). All Rights Reserved. Abstract This document describes the messages and procedures of the Nega- tive-acknowledgement (NACK) oriented reliable multicast (NORM) pro- tocol. 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 acknowledgement mechanism for transport reliability and offers additional protocol mechanism to conduct reliable multicast ses- sions with little "a priori" coordination among senders and receivers. It is capable of operating with both reciprocal multi- cast routing among senders and receivers and with asymmetric Adamson, Borman, et al. Expires May 2003 [Page 1] Internet Draft NORM Protocol November 2002 connectivity (possibly a unicast return path) from the senders to receivers. The protocol offers a number of features to allow dif- ferent types of applications or possibly other higher level trans- port protocols to utilize its service in different ways. The pro- tocol leverages the use of FEC-based repair and other IETF reliable multicast transport (RMT) building blocks in its design. 1.0 Protocol Design Goals NORM is designed to provide end-to-end reliable transport of data from sender(s) to a group of receivers over a multicast-capable network. The primary design goal of NORM is to provide for effi- cient, scalable, and robust bulk data (e.g. computer files, trans- mission of persistent data) transfer adaptable (preferably in an automated fashion) across heterogeneous networks and topologies. The protocol is capable of operating in an end-to-end fashion with no assistance from intermediate systems beyond basic IP multicast group management and forwarding services. However, an additional design goal will be compatibility with other reliable multicast "building blocks" [REF RMT Building Block Guidelines] to take advantage of additional network capabilities when available. Thus, while the techniques utilized in NORM are principally applicable to "flat" network distribution, they might also be applied to a given level of a hierarchical (e.g. tree-based) multicast distribution system if so desired. NORM can make use of reciprocal (among senders and receivers) multicast routing when available but will also be capable of efficient operation in asymmetric multicast topologies [REF source specific multicast, etc]. Group communication scalability requirements leads to adaptation of negative acknowledgement (NACK) based protocol schemes [REF.]. NORM is a protocol centered around the use of selective NACKs to request repairs of missing data. NORM also uses NACK suppression methods and dynamic event timers to reduce retransmission requests and avoid congestion within the network. When used in pure multi- cast session operation, both NACKs and repair transmissions are multicast to the group to aid in feedback and control message sup- pression. This feature and additional message aggregation func- tionality reduce the likelihood of multicast control message implo- sion. NORM also dynamically measures the greatest group roundtrip time (GRTT) between sources and the set of multicast receivers to further improve the efficiency of the protocol state timers and probabilistic backoff algorithms. 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. NORM also provides for the use of packet-level forward error correction (FEC) techniques for efficient multicast repair and optional proac- tive transmission robustness. Adamson, Borman, et al. Expires May 2003 [Page 2] Internet Draft NORM Protocol November 2002 Another aspect of the NORM protocol design is providing support for distributed multicast session participation with minimal coordina- tion among sources and receivers. The protocol allows sources and receivers to dynamically join and leave multicast sessions at will with minimal overhead for control information and timing synchro- nization among participants. To accommodate this capability, NORM protocol message headers contain some common information allowing receivers to easily synchronize to sources throughout the lifetime of a defined session. These common headers also include support for collection of transmission timing information (e.g., round trip delays) that allows NORM to adapt itself to a wide range of dynamic network conditions with little or no pre-configuration. The proto- col is purposely designed to be tolerant of inaccurate timing esti- mations or lossy conditions which may occur many networks includin mobile and wireless. The protocol is also designed to exhibit con- vergence even under cases of heavy packet loss and large queueing or transmission delays. While the various features of NORM are designed to provide some measure of general purpose utility, it is important to emphasize the understanding that "no one size fits all" in the reliable mul- ticast transport arena. There are numerous engineering tradeoffs involved in reliable multicast transport design and this requires an increased awareness of application and network architecture con- siderations. Performance requirements affecting design can include: group size, heterogeneity (e.g., capacity and/or delay), asymmetric delivery, data ordering, delivery delay, group dynamics, mobility, congestion control, and transport across low capacity connections. NORM contains various protocol parameters to accommo- date many of these differing requirements, but there is an assumed model of bulk transfer transport service that drives the trade-offs resulting in the protocol described here. 1.1 NORM Transport Service Model An instance of the NORM protocol (NormSession) is defined within the context of one or more senders and receivers mutually communi- cating with prdefined IP addresses and host port(s). While point- to-point (unicast) NormSessions may be established between a pair of protocol participants (NormNodes), it is anticipated the proto- col will be used for multicast data distribution and that partici- pating nodes will communicate on a common IP multicast group address and port number which has been chosen via other means (e.g. MBONE session directory tools, administrative coordination, SIP signalling, etc). Note that the protocol provides for an optional mechanism for receiver nodes to use unicast addressing to provide feedback to senders in networks where this is required (e.g. Source Specific Multicast Routing, asymmetric topologies, etc). Adamson, Borman, et al. Expires May 2003 [Page 3] Internet Draft NORM Protocol November 2002 The protocol design is principally driven with the assumption of a single sender transmitting bulk data content to a group of receivers. However, the protocol does provide for multiple senders to coexist within the context of a NormSession. In initial imple- mentations of this protocol, it is anticipated that multiple senders will transmit independently of one another and receivers will maintain state as necessary for each independent sender. In future iterations of this document, it is possible that some aspects of protocol operation (e.g. round-trip time collection) will provide for alternate modes allowing more efficient perfor- mance for applications requiring multiple senders. NORM provides for three types of bulk data content objects (NormOb- jects) to be reliably transported. These types include static com- puter memory data content (NORM_OBJECT_DATA), computer storage files (NORM_OBJECT_FILE), and non-finite streams of continuous data content (NORM_OBJECT_STREAM). 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. The use of the NORM_OBJECT_STREAM type is at the application's discretion and con- ceivably be used to carry static data or file content also. Reli- able stream service also opens up other possibilities such as reli- able 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 con- tent at any point in time (The applicability of this feature will depend upon the application). The static data and file services are anticipated to be useful for multicast-based cache applications with the ability to reliably provide transmission/repair of a large set of static data. Other types of static data/file "casting" ser- vices might make use of these transport object types, too. The NORM protocol also allows for a small amount of "out-of-band" data (NORM_INFO) 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 bulk content (data, file, or stream) being transmitted to allow application-level control of the receiver node's participa- tion in the current transport activity. This 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 a single NORM message. NORM does _not_ provide for global or application-level Adamson, Borman, et al. Expires May 2003 [Page 4] Internet Draft NORM Protocol November 2002 identification of data content within in its message headers (It should be noted that the NORM_INFO out-of-band data mechanism can be leveraged by the application for this purpose if desired, or identification could alternatively be embedded within the data con- tent). NORM identifies data content objects (NormObjects) with transport identifiers which are applicable while the sender is transmitting and/or repairing the given object. These transport data content identifiers are assigned in a montonically increasing fashion by each NORM sender during the course of a NormSession. Each sender maintains its transport identifier assignments indepen- dently so NormObjects are uniquely identified during transport by the concatenation of the sender's session-unique identifier (NormNodeId) and the assigned NormObject transport identifier (NormTransportId). The NormTransportIds are assigned from a large (32 bit?) numeric space in increasing order and may be reassigned for long-lived sessions. The NORM protocol provides mechanisms so that the sender application may terminate transmission of data con- tent 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 mul- ticast application variants may construct different, complete bulk transfer communication models to meet their goals. In summary, the NORM protocol's goal is to provide reliable trans- port of data content objects (including a potentially mixed set of types) to the receiver set from one or more senders. The senders will queue and transmit content in the form of static data or files and/or non-finite, ongoing stream types. The sender will provide for repair transmission of this content in response to NACK mes- sages received from the receiver group. Mechanisms for "out-of- band" information and other session management mechanisms are also specified for use by applications to form a complete reliable mul- ticast transport solutions for a range different purposes. 2.0 Protocol Definition 2.1 Assumptions A NORM protocol instantiation (NormSession) is defined by the con- text of participants communicating connectionless (e.g. User Data- gram Protocol (UDP)) packets over an Internet Protocol (IP) network on a common, pre-determined network address and host port number. Generally, the participants exchange packets on an IP multicast group address, but unicast transport may also be established or applied as an adjunct to multicast delivery. Currently the protocol uses a single multicast address for transmissions associated with a given NORM session. However, in the future, it is possible that multiple multicast addresses might be employed to segregate Adamson, Borman, et al. Expires May 2003 [Page 5] Internet Draft NORM Protocol November 2002 separate degrees of repair information to different groups of receivers experiencing different packet loss characteristics with respect to a given sender. This capability is under ongoing inves- tigation in the research community [REF]. For multicast operation, the NORM protocol assumes basic IP multicast forwarding service is available at least from the sender(s) to the receiver set. How- ever, the protocol also supports asymmetry where receiver partici- pants may transmit back to sender participants via unicast routing instead of broadcasting to the session multicast address. Each participant (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 distinquish between possible multiple senders and to distin- guish feedback information from different receivers. The protocol does not preclude multiple sender nodes actively transmitting within the context of a single NORM session (i.e. many- to-many operation), but any type of interactive coordination among these senders is assumed to be controlled by a higher protocol layer (perhaps using some of the optional NORM mechanisms later specified to perform this coordination). 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. The "wildcard" NormNodeId value may be useful in certain messages when a general response (from all session participants) is required by some messages. Unique data content transmitted within a NormSession uses sender- assigned identifiers (NormObjectTransportIds) which are valid and applicable only during the actual _transport_ of the particular portion of data content (i.e. for as long as the sender is trans- mitting and providing repair of the indicated data content). For a long-lived session, the NormObjectTransportId field will wrap and previously-used identifiers will be re-used. Any globally unique identification of transported data content must be assigned and processed by the higher level application using the NORM transport service. 2.2 General Protocol Operation A NORM sender primarily generates messages of type NORM_DATA which carry the data content and related FEC parity-based repair informa- tion for the bulk data/file or stream objects being transferred. Parity content is by default sent only in response to receiver repair requests (NACKs) and thus normally imposes no additional protocol overhead. However, the transport of an object can be optionally configured to proactively transmit some amount of parity packets along with the original data content to potentially enhance Adamson, Borman, et al. Expires May 2003 [Page 6] Internet Draft NORM Protocol November 2002 performance (e.g., improved delay) at the cost of additional over- head with initial data transmission. This configuration may be sensible for certain network conditions and can allow for robust, asymmetric multicast (e.g., unidirectional routing, satellite, cable) [REF] with minimal receiver feedback, or, in some cases, none. A sender message of type NORM_INFO is also defined and is used to carry any optional "out-of-band" context information for a given transport object. Because of its simple, nature content of NORM_INFO messages can be NACKed and repaired with a slightly lower delay process than NORM's general FEC-encoded data content. NORM_INFO may serve special purposes for some bulk transfer, reli- able multicast applications where receivers join the group mid- stream and need to ascertain contextual information on the current content being transmitted. The NACK process for NORM_INFO will be described later. The sender also generates messages of type NORM_CMD to perform cer- tain protocol operations such as congestion control, end-of-trans- mission flushing, round trip time estimation, receiver synchroniza- tion, and optional positive acknowledgement requests or application defined commands. The transmission of NORM_CMD messages from the sender is accomplished by one of three different processes. These include single, best effort unreliable transmission of the command, repeated redundant transmission of the command, and positively acknowledged commands. The transmission technique used for a given command depends upon the function of the command. Several core commands are defined for basic protocol operation. Additionally, implementations may wish to consider providing the option of appli- cation-defined commands which can take advantage of these transmis- sion methodologies available for command. These transmission methodologies make use of information available to the protocol engine (e.g. round-trip timing, transmission rate, etc) to perform efficiently. A NORM receiver generates messages of type NORM_NACK or NORM_ACK in response to transmissions of data and commands from a sender. The NORM_NACK messages are generated to request repair of detected data transmission losses. Receivers generally detect losses by tracking the sequence of transmission from a sender. Sequencing information is embedded in the transmitted data packets and end-of-transmission commands from the sender. NORM_ACK messages are generated in response to certain commands transmitted by the sender. In the general (and most scalable) protocol mode, receivers do not trans- mit any NORM_ACK messages. However, in order to meet potential user requirements for positive data acknowledgement, and to collect more detailed information for potential multicast congestion con- trol algorithms, NORM_ACK messages are defined and potentially used. NORM_ACK messages are also generated by receivers when NORM Adamson, Borman, et al. Expires May 2003 [Page 7] Internet Draft NORM Protocol November 2002 dynamic end-to-end congestion control is in operation. NORM allows for reliable transfer of three different types of data content. These include the type NORM_OBJECT_DATA which are static, persistent blocks of data content maintained in the sender's appli- cation memory storage and the type NORM_OBJECT_FILE which corre- sponds to data stored in the sender's non-volatile file system. Both of these types represent "NormObjects" of finite, but poten- tially very large, size which are encapsulated for transmission and are temporarily yet uniquely identified with the given sender's NormNodeId and a temporarily unique NormObjectTransportId. The third type of data content is NORM_OBJECT_STREAM which identifies that the current NORM content is an ongoing transmission of unde- fined length. This is analogous to the reliable streaming content provide by TCP for unicast data transport. NORM protocol implemen- tations 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 appli- cation. In either case, the NORM sender and receiver implementa- tions are anticpated to provide buffering to facilitate repair of the stream as it is transported. All transmissions by individual senders and receivers are subject to rate control governed by a peak transmission rate set for each participant by the application. This can be used to limit the quantity of multicast data transmitted by the group. When NORM's congestion control algorithm is enabled the rate for senders is automatically adjusted. And even when dynamic congestion control is enabled, it may be desirable in some cases to establish minimum and maximum bounds for the rate adjustment depending upon the application. 2.3 Message Type and Header Definitions As mentioned previously, there are two primary classes of NORM mes- sages: messages generated by the sender of reliable multicast traf- fic and messages generated by receivers. These are described in corresponding sections below after the portion of NORM Message header common to all NORM messages is described. 2.3.1 NORM Common Message Header There are some common message fields contained in all NORM message types. All NORM protocol messages begin with a common header with information fields as follows: Adamson, Borman, et al. Expires May 2003 [Page 8] Internet Draft NORM Protocol November 2002 NORM Common Packet Header 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | version | type | sequence | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | source_id | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The "version" field is a 8-bit value indicating the protocol ver- sion number. Currently, NORM implementations SHOULD ignore received messages with a different protocol version number. This number is intended to indicate and distinguish upgrades of the pro- tocol which may be non-interoperable. The message "type" field is a 8-bit value indicating the NORM pro- tocol message type. These types are defined as follows: Message Value NORM_INFO 1 NORM_DATA 2 NORM_CMD 3 NORM_NACK 4 NORM_ACK 5 NORM_REPORT 6 The "sequence" field is a 16-bit value which is set by the message originator as a monotonically increasing number incremented with each NORM message transmitted. This value can be monitored by receiving nodes to detect packet losses in the transmission. Note that this value is NOT used to detect missing reliable data con- tent, but is intended for use in an algorithm estimating raw packet loss for congestion control purposes. The size of this field is intended to be sufficient to allow detection of a reasonable range of packet loss within the expected delay-bandwidth product of expected network connections. The "source_id" field is a 32-bit value identifying the node which sent the message. A participant's NORM node identifier (NormNodeId) can be set according to the application needs but unique identifiers must be assigned within a single NormSession. In some cases, use of the host IP address or a hash of it can suf- fice, but alternative methodologies for assignment and potential collision resolution of node identifiers within a multicast session Adamson, Borman, et al. Expires May 2003 [Page 9] Internet Draft NORM Protocol November 2002 need to be considered. For example, the "source identifier" mecha- nism defined in the RTPv2 specification [REF RTP] may be applicable to use for NORM node identifiers. At this point in time, the pro- tocol makes no assumptions about how these unique identifiers are actually assigned. 2.3.2 Sender Messages: 2.3.2.1 NORM_DATA This is expected to be the predominant message type transmitted by NORM senders. These messages will contain data content for objects of type NORM_OBJECT_DATA, NORM_OBJECT_FILE, and NORM_OBJECT_STREAM. A goal of the protocol design is to provide for parallel transmis- sion of different streams and data/file sets. NORM_DATA messages will generally consist of original data content of the application data being transmitted. The content size of these messages will a maximum of NormSegmentSize which is constant for the duration of a given sender's term of participation in the session. Senders advertise their NormSegmentSize in applicable messages which they transmit. This allows receivers to allocate appropriate buffering resources and to determine other information in order to properly process received data messaging. Note this message type will also be used to convey FEC parity repair content for NormObjects sent. Adamson, Borman, et al. Expires May 2003 [Page 10] Internet Draft NORM Protocol November 2002 NORM_DATA Header 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | flags | grtt | gsize | fec_id | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | segment_size | object_size_msb | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | object_size_lsb | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | reserved | fec_encoding_name | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | fec_num_parity | fec_block_len | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | object_transport_id | fec_block_number_msb | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | fec_block_number_lsb | fec_symbol_id | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | payload_len* | offset_msb* | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | offset_lsb* | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | payload_data* | * Note the "offset" and "payload_len" fields for NORM_DATA messages containing parity information are actually values computed from FEC encoding of the "offset" and "payload_len" fields of the data seg- ments of the applicable coding block. Thus, for parity packets, these do _not_ represent these values directly. The "flags" field contains a number of different binary flags pro- viding information and hints regarding how the receiver should han- dle the identified object. Defined flags in this field include: Adamson, Borman, et al. Expires May 2003 [Page 11] Internet Draft NORM Protocol November 2002 +---------------------+-------+------------------------------------------+ | Flag | Value | Purpose | +---------------------+-------+------------------------------------------+ |NORM_FLAG_REPAIR | 0x01 | Indicates message is a repair transmis- | | | | sion | +---------------------+-------+------------------------------------------+ |NORM_FLAG_EXPLICIT | 0x02 | Indicates availability of NORM_INFO for | | | | object | +---------------------+-------+------------------------------------------+ |NORM_FLAG_INFO | 0x04 | Indicates availability of NORM_INFO for | | | | object | +---------------------+-------+------------------------------------------+ |NORM_FLAG_UNRELIABLE | 0x08 | Indicates that repair transmissions for | | | | the specified object will be unavail- | | | | able. (One-shot, best effort transmis- | | | | sion) | +---------------------+-------+------------------------------------------+ |NORM_FLAG_FILE | 0x10 | Indicates object is "file-based" data | | | | (hint to use disk storage for reception) | +---------------------+-------+------------------------------------------+ |NORM_FLAG_STREAM | 0x20 | Indicates object is of type | | | | NORM_OBJECT_STREAM. | +---------------------+-------+------------------------------------------+ The NORM_FLAG_REPAIR flag is set when the associated transmission is a repair transmission. This information can be used by receivers to facilitate a join policy where it is desired that newly joining receivers only begin participating in the NACK pro- cess upon receipt of new "fresh" data. The NORM_FLAG_INFO flag is se only when there optional NORM_INFO content is available for the associated object. Thus, receivers will NACK for retransmission of NORM_INFO only when it is available. The NORM_FLAG_UNRELIABLE flag is set when the sender wishes to transmit and object with "best effort" delivery only and will not supply repair transmissions for the object. The NORM_FLAG_FILE flag can be set as a "hint" from the sender that the associated object should be stored in non- volatile storage. The NORM_FLAG_STREAM flag is set when the iden- tified object is of type NORM_OBJECT_STREAM. Note that the "object_size" field is no longer applicable (Another use for this field for "stream" objects may be determined as this capability is designed). The "grtt" field contains a non-linear quantized representation of the sender's current estimate of group round-trip time (GRTT). This value is used to control timing of the NACK repair process and other aspects of protocol operation as described in this document. The algorithm for encoding and decoding this field is described in the RMT NORM Building Block document (currently "draft-rmt-bb- Adamson, Borman, et al. Expires May 2003 [Page 12] Internet Draft NORM Protocol November 2002 norm-04.txt"). The "gsize" field contains a representation of the sender's current estimate of group size. This value is used to control feedback suppression mechanisms within the protocol for more optimized per- formance for different group sizes. The 8-bit "gsize" field con- sists of 4 bits of mantissa in the 4 most significant bits and 4 bits of base 10 exponent (order of magnitude) information in the 4 least significant bits. For example, to represent an approximate group size of 100 (or 1e02), the value of the upper 4 bits is 0x01 (to represent the mantissa of 1) and the lower 4 bits value would be 0x02 for an 8-bit representation of "0x12". As another example, a group size of 9000 (9e03) would be represented by the value 0x93. The group size does not need to be represented with a high degree of precision to appropriately scale backoff timers, etc. The "fec_id" field corresponds to the FEC Encoding Identifier described in the FEC Building Block document (currently "draft- ietf-rmt-bb-fec-04.txt"). Note the packet format illustrated above assumes "Small Block Systematic Codes" which corresponds to an FEC Encoding Identifier equal to 129. The other "fec" fields may be interpreted differently for supporting other FEC Encoding indenti- fier types in the future. The "segment_size" field indicates the sender's current setting for maximum message payload content (in bytes). The "fec_type" field describes the error correction coding technique and parameters the sender is using to calculate parity repair segments. Knowledge of these fiels allows a NORM receiver to allocate appropriate buffer- ing and FEC decoding resources. The "object_size" fields indicate the total size of the object (in bytes). This information is used by receivers to determine storage requirements and/or allocate storage for the received object. Receivers with insufficient storage capability may wish to forego reception (i.e. not NACK for) of the indicated object. The "object_size" fields are not applicable for objects of type NORM_OBJECT_STREAM. (Note: The "object_size" fields _may_ be defined to serve an alternative use in this case). The "fec_encoding_name" and "fec_num_parity" fields correspond to the "FEC Encoding Name" and "Number of redundant symbols" fields of the FEC Object Transmission Information format given by the FEC Building Block document. The "fec_encoding_name" shall be a value corresponding to the particular type of Small Block Systematic Code being used (e.g. Reed-Solomon GF(2^8), Reed-Solomon GF(2^16), etc). The standardized assignment of these values is TBD. The "fec_num_parity" field corresponds to a parameter for generating Adamson, Borman, et al. Expires May 2003 [Page 13] Internet Draft NORM Protocol November 2002 specific FEC encoding/decoding algorithms for the named code. For example, Reed-Solomon codes may be arbitrarily shortened to create different code variations for a given block length. In this case, the "fec_num_parity" value indicates the maximum number of avail- able parity segments for the coding block from the sender. This field _may_ be interpreted differently for other systematic codes as they are defined. The "fec_block_len" corresponds to the number of user data symbols in the current FEC coding block for the Small Block Systematic Code being used. Given the "fec_block_len" (Source block length) infor- mation of how many symbols of application data is contained in the block, the receiver can determine whether the attached segment is data or parity content and treat it appropriately. (For systematic codes, symbols numbered 0 through (fec_block_len-1) contain appli- cation data while segments numbered (fec_block_len) through (fec_block_len+fec_num_parity-1) contain the parity symbols calcu- lated for the block). The "object_transport_id" field is a monotonically and incremen- tally increasing value assigned by a sender to the object being transmitted. Transmissions and repair requests related to that object use the same "object_transport_id" value. For sessions of very long or indefinite duration, the "object_transport_id" field may be repeated, but it is presumed that the 16-bit field size pro- vides an adequate enough sequence space to prevent temporary object confusion amongst receivers and sources (i.e. receivers SHOULD re- synchronize with a server when receiving object sequence identi- fiers sufficiently out-of-range with the current state kept for a given source). During the course of its transmission within a NORM session, an object is uniquely identified by the concatenation of the sender "node_id" and the given "object_transport_id". Note that NORM_INFO messages associated with the identified object carry the same "object_transport_id" value. The "fec_block_number" and "fec_symbol_id" fields directly corre- spond to the "encoding block number" and "encoding symbol id" fields of the FEC Payload ID format given by the FEC Building Block document. The "fec_fec_block_number" identifies the coding block while the "fec_symbol_id" identifies which specific symbol (seg- ment) within the coding block the attached packet conveys. Depend- ing upon the value of the "fec_symbol_id" and the associated "fec_block_len" and "fec_num_parity" parameters for the block, the symbol (segment) referenced may be a user data or an FEC parity segment. Note the concatenation of "object_tranport_id>fec_block_num- ber>fec_symbol_id" can be viewed as a transport data unit (TPDU) Adamson, Borman, et al. Expires May 2003 [Page 14] Internet Draft NORM Protocol November 2002 identifier for the attached segment. The "offset" and "payload_len" fields are used to identify the position and quantity of the content of the packet payload. For senders employing systematic FEC encoding, these fields will corre- spond to the actual values for NORM_DATA messages which contain original data content. For NORM_DATA messages containing calcu- lated parity content, these fields will actually contain the values computed by FEC encoding of the "offset" and "length" values of the data segments of the corresponding FEC coding block. This allows the "offset" and "length" values of missing data content to be determined when decoding an FEC coding block. The "payload_data" field contains original data or computed parity content for the identified segment. The maximum length of this field corresponds to the sender's NormSegmentSize. The length of this field for messages containing parity content will always be of the length NormSegmentSize. When encoding a block of data segments of varying sizes, the FEC encoder SHALL assume zero value padding for data segments less than the NormSegmentSize. The receiver will use the "length" information to properly retrieve receive data con- tent and deliver it to the application. 2.3.2.2 NORM_INFO The NORM_INFO message is used to convey _optional_ "out-of-band" context information for objects transmitted. An example may be MIME type information for the associated file, data, or stream object. Receivers might use this information to make a decision as whether to participate in reliable reception of the associated object. Each NormObject may have an independent unit of NORM_INFO associated with it. NORM_DATA messages contain a flag to indicate the availability of NORM_INFO for a given NormObject. NORM receivers may NACK for retransmission of NORM_INFO when they have not received it for a given NormObject. The size of the NORM_INFO content is limited to that of a single NormSegmentSize for the given sender. This atomic nature allows the NORM_INFO to be rapidly and efficiently repaired within the NORM reliable transmis- sion process. Adamson, Borman, et al. Expires May 2003 [Page 15] Internet Draft NORM Protocol November 2002 NORM_INFO Header 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | flags | grtt | gsize | fec_id | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | segment_size | object_size_msb | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | object_size_lsb | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | fec_encoding_name | fec_num_parity | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | fec_block_len | object_transport_id | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | payload_data | The "flags", "grtt", "gsize", "fec_id", "segment_size", "object_transport_id", "object_size", "fec_encoding_name", "fec_num_parity", and "fec_block_len" fields carry the same infor- mation and serve the same purpose as with NORM_DATA messages. Note the "fec_block_len" value will correspond to the maximum (nominal) FEC block size for the encoding used. These values allow the receiver to prepare buffering, etc for further transmissions from the sender if this is the first message received. The "pay- load_data" field contains application-defined content which can be used by the receiver application for various purposes. 2.3.2.3 NORM_CMD NORM_CMD messages are transmitted by senders to perform a number of different protocol functions. This includes round-trip timing col- lection, potential congestion control functions, synchronization of receiver NACKing "windows", notification of sender status and other core protocol functions. A core set of NORM_CMD messages will be enumerated. A range of command types will remain undefined for potential application-specific usage. Some NORM_CMD types (possi- bly including application-defined commands) may have some dynamic content attached. This content will be limited to a single Norm- SegmentSize to retain the atomic nature of commands. The NORM_CMD message begins with a common header, following the usual NORM mes- sage common header. The header format is defined as: Adamson, Borman, et al. Expires May 2003 [Page 16] Internet Draft NORM Protocol November 2002 NORM_CMD Common Header 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | grtt | gsize | flavor | ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The "grtt" and "gsize" fields provide the same information and serve the same purpose as with NORM_DATA and NORM_INFO messages. The "flavor" field indicates the type of command to follow. The command flavors (types) include: +----------------------+--------------+----------------------------------+ | Command | Flavor Value | Purpose | +----------------------+--------------+----------------------------------+ |NORM_CMD(FLUSH) | 1 | Indicates sender temporary or | | | | permanent end-of-transmission. | | | | (Assists in robustly initiating | | | | outstanding repair requests from | | | | receivers). | +----------------------+--------------+----------------------------------+ |NORM_CMD(SQUELCH) | 2 | Advertisement of current repair | | | | window in response to out-of- | | | | range NACKs. | +----------------------+--------------+----------------------------------+ |NORM_CMD(ACK_REQ) | 3 | Requests positive acknowledge- | | | | ment from a list of receivers. | +----------------------+--------------+----------------------------------+ |NORM_CMD(REPAIR_ADV) | 4 | Advertise sender's aggregated | | | | NACKs for suppression of unicast | | | | feedback. | +----------------------+--------------+----------------------------------+ |NORM_CMD(CC) | 5 | Probe possibly used for explic- | | | | itly collecting congestion con- | | | | trol feedback. | +----------------------+--------------+----------------------------------+ |NORM_CMD(APPLICATION) | 6 | Robustly repeated application- | | | | defined command which can tem- | | | | porarily preempt NORM data | | | | transmission. | +----------------------+--------------+----------------------------------+ NORM_CMD(FLUSH) The NORM_CMD(FLUSH) command is sent when the sender reaches the end of any data content and pending repairs it has queued for Adamson, Borman, et al. Expires May 2003 [Page 17] Internet Draft NORM Protocol November 2002 transmission. This command is repeated once per 2*GRTT to excite the receiver set for any outstanding repair requests for data up to and including the point indicated by the FLUSH message. The number of repeats is equal to ROBUST_FACTOR. The greater this number, the higher the probability that all applicable receivers will be excited for repair requests (NACKs) _and_ the corresponding NACKs are delivered to the sender. If a NACK message interrupts the flush process, the sender will re-initiate the flush process when repair transmissions are completed. Note that receivers also employ a timeout mechanism to self-initiate NACKing when a sender is determined to have gone "idle". This inactivity timeout is related to 2*GRTT*ROBUST_FACTOR and will be discussed more later. With a sufficient ROBUST_FACTOR value, data content is delivered with a high assurance of reliability. The penalty of a large ROBUST_FACTOR value is potentially excess sender NORM_CMD(FLUSH) transmissions and a longer timeout for receivers to self-initiate a terminal NACK process. For finite-size transport objects such NORM_OBJECT_DATA and NORM_OBJECT_FILE, the flush process (if there no further pending transmissions) will occur at the end of these objects and thus any FEC repair information is available for repairs in response to repair requests elicited by the flush command. However, for NORM_OBJECT_STREAM, the flush may occur in the middle of an FEC coding block. In this case, the sender will not be able to provide FEC parity content for repair for the concurrent coding block and will be required to use explicit repair of stream data content at that point. Thus, applications which anticipate frequent flusing of stream content should be judicious in the selection of the FEC coding block size (i.e. not use a very large coding block size if frequent flushing occurs). For example, a reliable multicast application transmitting on on-going session of intermittent, rela- tively small messaging content will need to make a trade-off in using NORM's NORM_OBJECT_DATA paradigm or the NORM_OBJECT_STREAM paradigm with an appropriate FEC coding block size. This is analo- gous to application trade-offs such as the selection of different TCP modes of operation such "no delay", etc. The format of the NORM_CMD(FLUSH) message (in addition to the NORM message common header) is: Adamson, Borman, et al. Expires May 2003 [Page 18] Internet Draft NORM Protocol November 2002 NORM_CMD(FLUSH) Message 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | grtt | gsize | flavor = 1 | flags | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | object_transport_id | fec_block_number_msb | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | fec_block_number_lsb | fec_symbol_id | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ In addition to the common NORM_CMD "grtt", "gsize", and "flavor" fields, the NORM_CMD(FLUSH) message contains fields to identify the current status and logical transmit position of the sender. A single "flag" value is currently defined: NORM_FLUSH_FLAG_EOT = 0x01 When the NORM_FLUSH_FLAG_EOT is set, it indicates the sender is preparing to terminate transmission and no longer provide response to repair requests. This allows the receiver set to gracefully reach closure of operation with this sender and free any resources which are no longer needed. For NORM_OBJECT_STREAM objects, the receiver will request explicit repair of the terminating coding block if the "fec_symbol_id" is less than "fec_block_size - 1". An explicit repair request con- sists of constructing NACK content for the applicable "fec_block_number" which does not include request for parity-based repair. The other fields defining the sender's current "transmit postion" consist of "object_transport_id"., "fec_symbol_id" and "fec_block_number". These fields are interpreted in the same man- ner as the fields of the same names in the NORM_DATA message type. Receivers are expected to check their completion state and initiate the NACK repair process if they have outstanding repair needs up through this transmission point. If the receivers have no out- standing repair needs, no response is generated. NORM_CMD(SQUELCH) The NORM_CMD(SQUELCH) command is multicast to the receiver set in response to invalid NACKs received by the sender. Receivers are expected to stop (i.e. "squelch") further invalid requests when Adamson, Borman, et al. Expires May 2003 [Page 19] Internet Draft NORM Protocol November 2002 receiving this message. The NORM_CMD(SQUELCH) command is limited to be sent at once per 2*GRTT at the most. The NORM_CMD(SQUELCH) advertises the "repair window" of the sender by identifying the earliest (lowest) transmission point for which it will provide repair, along with an encoded list of objects from that point for- ward which are still valid for repair. This mechanism allows the sender application to abort intermediate objects still in repair transmission. For example, an object pending transmission/repair may for some reason may have become obsolete. The receiver set learns from the NORM_CMD(SQUELCH) the set of data for which it is valid to request repair. In normal conditions, it is expected the NORM_CMD(SQUELCH) will be used infrequently, and is generally anticipated to provide a reference for receivers who have fallen "out-of-sync" with the sender. The NORM_CMD(SQUELCH) contains the identity of the earliest transmission point and includes a set of NormTransportIds which are valid. The starting point of the included set begins at the greatest (latest) of the sender's earli- est transmission point or the lowest invalid NormTransportId in the invalid NACK(s) which prompted the generation of the NORM_CMD(SQUELCH). The length of the list in the NORM_CMD(SQUELCH) is limited by the sender's NormSegmentSize. This allows the receivers to learn the status of the sender's applicable object repair window with minimal transmission of NORM_CMD(SQUELCH) com- mands. The format of the NORM_CMD(SQUELCH) message (in addition to the NORM message common header) is: NORM_CMD(SQUELCH) Header 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | grtt | gsize | flavor = 2 | reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | object_transport_id | fec_block_number_msb | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | fec_block_number_lsb | fec_symbol_id | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | invalid_object_list ... | In addition to the common NORM_CMD "grtt" and "flavor" fields, the NORM_CMD(SQUELCH) message contains fields to identify the earliest logical transmit position of the sender's current repair window and a "repair window description" beginning with the index of the logi- cally earliest invalid repair request from the offending NACK mes- sage which initiated the SQUELCH response. The "object_transport_id", "fec_block_number", and "fec_symbol_id" fields are concatenated to indicate the beginning of the sender's Adamson, Borman, et al. Expires May 2003 [Page 20] Internet Draft NORM Protocol November 2002 current repair window (i.e. the logically earliest point in its transmission history for which the sender can provide repair). This serves as an advertisement of a "synchronization point" for receivers to request repair. Note, while the "fec_symbol_id" is provided here, when FEC is used, the sender's repair window will generally be incremented on an FEC coding block basis. The "invalid_object_list" is a list of 16-bit object_transport_ids which, although they are within the sender's current repair window, are no longer available for repair from the sender (For example, a sender application may dequeue an out-of-date object even though it is still within the repair window). The total size of the "invalid_object_list" content is implied by the packets payload length and is limited to a maximum of the NormSegmentSize of the sender. Thus, for very large repair windows, it is possible that a single SQUELCH message may not be capable of listing the entire set of invalid objects in the repair window. In this case, the sender SHALL ensure that the list begins with an "object_transport_id" which is greater than or equal to the lowest ordinal invalid "object_transport_id" from the NACK message(s) which prompted the SQUELCH generation. This insures convergence of the SQUELCH pro- cess, even if multiple invalid NACK/ SQUELCH response iterations are required. This explicit description of invalid content within the sender's current window, allows the sender application (most notably for discrete "object" based transport) to arbitrarily invalidate (i.e. dequeue) portions of enqueued content (e.g. cer- tain objects) for which it no longer wishes to provide reliable transport. (TBD) Provide example SQUELCH messages. NORM_CMD(ACK_REQ) The NORM_CMD(ACK_REQ) message is used by the sender to request acknowledgement from a specified list of receivers. This message is used in providing a lightweight positive acknowledgement mecha- nism which can optionally be employed by the reliable multicast application to deterministically determine that watermark points in the reliable transmission have been achieved by specific receivers. The format of the NORM_CMD(ACK_REQ) message (in addition to the NORM message common header) is shown below. Adamson, Borman, et al. Expires May 2003 [Page 21] Internet Draft NORM Protocol November 2002 NORM_CMD(ACK_REQ) Message 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | grtt | gsize | flavor = 3 | ack_flavor | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ack_req_content | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ack_req_content (cont'd) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | acking_node_list ... | The NORM_CMD(ACK_REQ) Message consists of "grtt", "gsize", and "flavor" fields as with other NORM_CMD messages. Then an "ack_fla- vor" field is specified followed by 64-bits of "ack_flavor" spe- cific content and a list of NormNodeIds which are expected to explicitly respond to the acknowledgement request. The "ack_fla- vor" field is used to indicate the interpretation of the 64-bit ack_req_content" field space following the "ack_flavor" field. The following "ack_flavor" values are defined: +--------------------+--------------+----------------------------------+ | ACK Type | Flavor Value | Purpose | +--------------------+--------------+----------------------------------+ |NORM_ACK(WATERMARK) | 1 | Request for acknowledgement of | | | | reliable reception of watermark | | | | transmission point. | +--------------------+--------------+----------------------------------+ |NORM_ACK(RTT) | 2 | Sender timestamp information and | | | | optional request for explicit | | | | RTT collection response | +--------------------+--------------+----------------------------------+ The NORM_ACK(WATERMARK) identifies a watermark point in the sender's reliable transmission and explicitly requests positive acknowledgement from a portion of the receiver set. So, the for- mat of the NORM_CMD(ACK_REQ(WATERMARK)) message (in addition to the NORM common message header) is: Adamson, Borman, et al. Expires May 2003 [Page 22] Internet Draft NORM Protocol November 2002 NORM_CMD(ACK_REQ(WATERMARK)) Message 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | grtt | gsize | flavor = 3 | ack_flavor = 1| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | object_transport_id | fec_block_number_msb | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | fec_block_number_lsb | fec_symbol_id | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | acking_node_list ... | The "object_transport_id", "fec_fec_block_number", and "fec_sym- bol_id" are used to identify the watermark point for which the pos- itive acknowledgement request applies. This watermark point is similar to that used in MDP_CMD(FLUSH) message. It should be noted that all receivers are expected to treat the ACK_REQ command equiv- alently to a FLUSH command and appropriately initiate NACK repair cycles in response to any detected missing data up to the watermark point. The "acking_node_list" field contains the current list of receiver NormNodeIds which should reply with postive acknowledgement to this request. The packet payload length implies the length of the "ack- ing_node_list" and its length is limited to the NormSegmentSize. The NormNodeIds are listed in network (Big Endian) order. The indicated receivers SHALL send a NORM_ACK message in response to this request IF they have no outstanding repair needs up to and including the watermark point. Note this does _not_ necessarily mean the receivers actually received all of the data, but simply that, for whatever reason (including the fact they may have already received the data or if the receiving application simply chose _not_ to receive the indicated data), they have no outstanding repair needs prior to the watermark point. Verification of actual received data content must be accomplished by another means outside of this transport layer protocol. Receivers SHALL randomly spread their response to this request using a uniform distribution over 1 GRTT of time. Again, note the size of the included list is limited to the sender's NormSegmentSize setting. Thus, multiple NORM_CMD(ACK_REQ) cycles may be required to achieve responses from all receivers specified. Also, the number of attempts to excite a response from a given receive SHALL be limited to ROBUST_FACTOR. The NORM_CMD(ACK_REQ) is repeated at a rate of once per 2*GRTT. Note that the content of the attached NormNodeId list will be dynamically updated as this process progresses and ACKs are received from the specified receiver set. The process SHALL Adamson, Borman, et al. Expires May 2003 [Page 23] Internet Draft NORM Protocol November 2002 terminate when all desired receivers have responded or the maximum number of attempts has been achieved. Note that repair requests can interrupt the positive acknowledgement process and the positive acknowledgment process will resume only when there are no pending repair transmissions up to the specified watermark point. NORM_CMD(ACK_REQ(RTT)) The NORM_CMD(ACK_REQ(RTT)) is periodically transmitted by the sender to provide a reference point (a timestamp) so that receivers can calculate appropriate response content in NORM_NACK and NORM_ACK messages from which the sender can monitor and estimate the current GRTT. Currently, this reference is sent separately from other sender message and not included in every message because of the excessive overhead it may impose on data transmission. Gen- erally, the GRTT is not expected to be so dynamic as to require rapid update. However, a technique is being investigated by the author to provide a low overhead reference which could be attached to every sender transmission and used for the receiver response generation [REF]. This command may also potentially be leveraged serve as part of NORM congestion control to periodically provide updated congestion control information and/or probing to the group. If this is the case, there will likely be sufficient content in this message that it merits a separate message rather than be peri- odically included in the overhead of other sender transmissions. This command may also be extended to assume some responsibility in initializing and updating a group size estimator used to appropri- ately scale NACK suppression back-off timing, etc. For now, a min- imal format is defined as a placeholder for this message. The for- mat of the NORM_CMD(GRTT_REQ) message (in addition to the NORM mes- sage common header and the NORM_CMD common header) is: NORM_CMD(ACK_REQ(RTT)) Message 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | grtt | gsize | flavor = 3 | ack_flavor = 2| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | send_time_sec | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | send_time_usec | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | acking_node_list ... | The "send_time" field is a precision timestamp indicating the time that the NORM_CMD(GRTT_REQ) message was transmitted. This consists Adamson, Borman, et al. Expires May 2003 [Page 24] Internet Draft NORM Protocol November 2002 of a 64-bit field containing 32-bits with the time in seconds ("sent_time_sec") and 32-bits with the time in microseconds ("send_time_usec") since some reference time the source maintains (usually 00:00:00, 1 January 1970). The ordering of the fields in Big Endian network order. The "acking_node_list" again is a list of NormNodeIds for receivers which should explicitly respond to the request. The "wildcard" NormNodeId may be listed when a response is expected from all receivers. When this "wildcard" response is elicited, the receiver set is expected to randomly spread their response over time, scaled as a function of the "grtt" and "gsize" values to avoid response implosion. The receivers corresponding to other listed specific NormNodeIds are expected to respond immediately with an appropriate NORM_ACK message (unless a NORM_NACK message is already queued for response). Both NORM_NACK and NORM_ACK messages are designed to contain information to allow the sender to determine round trip times for responding receivers. NORM_CMD(REPAIR_ADV) The NORM_CMD(REPAIR_ADV) message is used by the sender to "adver- tise" its aggregated repair state from accumulated NORM_NACK mes- sages accumulated during a repair cycle and/or congestion control feedback received. This message is sent only when the sender has received NORM_NACK and/or NORM_ACK(RTT) (when congestion control is enabled) messages via unicast transmission instead of multicast. By "echoing" this information to the receiver set, suppression of feedback can be achieved even when receivers are unicasting that feedback instead of multicasting it among the group. [REF] NORM_CMD(REPAIR_ADV) Header 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | grtt | gsize | flavor = 4 | flags | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | cc_flags | cc_rtt | cc_rate | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | repair_adv_content ... | The "grtt", "gsize" and "flavor" fields serve the same purpose as in other NORM_CMD messages. There is one flag defined: NORM_REPAIR_ADV_FLAG_LIMIT = 0x01 Adamson, Borman, et al. Expires May 2003 [Page 25] Internet Draft NORM Protocol November 2002 This flag is set by the sender when it is unable to fits its full current repair state into a single NormSegmentSize. If this flag is set, receivers should limit their NACKing to generating NACKs only up through the maximum ordinal transmission position (objec- tId::fecBlockId::fecSymbolId) included in the "repair_adv_content". When congestion control operation is enabled, the "cc_flags", "cc_rtt", and "cc_rate" fields contain values for the receiver with the lowest calculated congestion control rate from which feedback was received since the last NORM_CMD(REPAIR_ADV) transmission. These fields are used by receivers to suppress rounds of congestion control feedback. The definition of these fields is given in the description of the NORM_CMD(CC) message below. The "repair_adv_content" is in exactly the same form as the "nack_content" of NORM_NACK messages and can be processed by receivers for suppression purposes in the same manner with the exception of the condition when the NORM_REPAIR_ADV_FLAG_LIMIT is set. NORM_CMD(CC) The NORM_CMD(CC) message is a sender message which may be applica- ble when congestion control mechanism are applied to NORM protocol operation. The NORM_CMD(CC) messages contains fields to enable sender->receiver set round-trip time collection. Also, a list of "congestion control representatives" (or candidates) is provided, each given with information so that the "congestion control candi- dates" may determine their role in congestion control operation. Different congestion control techniques are under consideration and this message format will be revised in futre versions of this docu- ment. In addition to common NORM message fields and the "grtt", "gsize", and "flavor" fields of all NORM_CMD messages, the NORM_CMD(CC) mes- sage has fields which are also common to the NORM_CMD(ACK_REQ) mes- sages which allow the sender to advertise a timestamp ("send_time" here) to facilitate collection of RTT/GRTT information. When con- gestion control operation is enabled, the NORM_CMD(CC) message is used in lieu of NORM_CMD(ACK_REQ(RTT)) messages for GRTT determina- tion. Adamson, Borman, et al. Expires May 2003 [Page 26] Internet Draft NORM Protocol November 2002 NORM_CMD(CC) Message Fields 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | grtt | gsize | flavor = 5 | cc_sequence | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | send_time_sec | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | send_time_usec | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | send_rate | reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | cc_node_list ... | The "cc_sequence" field is a sequence number applied by the sender to congestion control command messages. The greatest received "cc_sequence" value is recorded by receivers and fed back to the sender in any NORM_ACK or NORM_NACK messages generated by the receivers for that sender. This feedback allows the sender to assess the receivers' status with regards to successful reception of NORM_CMD(CC) and possibly other messages. The "send_time" field is a 64-bit timestamp (with microsecond pre- cision) referenced to the sender's time reference of when the NORM_CMD(CC) message was transmitted. Receivers feed back this value adjusted by the amount of delay from when they receive the NORM_CMD(CC) message to when they respond with any NORM_ACK or NORM_NACK messages generated. This allows the sender to evaluate the round-trip time to different receivers for congestion control and other (i.e. GRTT) purposes. The "send_rate" field indicates the sender's current transmission rate in bytes per second. The 16-bit "send_rate" field consists of 12 bits of mantissa in the most significant byte and 4 bits of base 10 exponent (order of magnitude) information in the least signifi- cant byte. The 12-bit mantissa portion of the field is scaled such that a floating point value of 0.0 corresponds to 0 and a floating point value of 10.0 corresponds to 4096. Thus: value = (int) (mantissa * 4096.0 / 10.0 + 0.5) For example, to represent a transmission rate of 256 kbps (3.2e+04 bytes per second), the lower 4 bits of the 16-bit field contain a value of 0x04 to represent the exponent while the upper 12 bits contain a value of 0x51f as determined from the equation given above: value = (int)((3.2 * 4096.0 / 10.0) + 0.5) = 1311 = 0x51f To decode the "send_rate" field, the following equation can be Adamson, Borman, et al. Expires May 2003 [Page 27] Internet Draft NORM Protocol November 2002 used: sendRate = * 10..0 / 4096.0 * power(10.0, ) Note the maximum transmission rate representable by this scheme is approximately 9.99e+15 bytes per second. The "cc_node_list" consists of a list of NormNodeIds for receivers which are expected to proactively (and immediately) respond to reception of the NORM_CMD(CC) message with a NORM_ACK message. The length of the "cc_node_list" can be inferred from the length of the NORM_CMD(CC) message. The length of of the NORM_CMD(CC) message implies the length of the "cc_node_list". Each item in the "cc_node_list" is in the follow- ing format. Congestion Control Node List Item Fields 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | cc_node_id | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | cc_flags | cc_rtt | cc_rate | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The "cc_node_id" is the NormNodeId of the receiver which the item represents. The "cc_flags" field contains flags indicating the congestion con- trol status of the indicated receiver. The following flags are defined: +----------------+-------+------------------------------------------+ | Flag | Value | Purpose | +----------------+-------+------------------------------------------+ |NORM_FLAG_WPR | 0x01 | Receiver is the current worst path rep- | | | | resentative (WPR) | +----------------+-------+------------------------------------------+ |NORM_FLAG_WPC | 0x02 | Receiver is a worst path candidate (WPC) | +----------------+-------+------------------------------------------+ |NORM_FLAG_RTT | 0x04 | Receiver has measured RTT (and rate) | | | | with respect to sender | +----------------+-------+------------------------------------------+ |NORM_FLAG_START | 0x08 | Sender/receiver in "slow start" phase of | | | | congestion control operation | +----------------+-------+------------------------------------------+ Adamson, Borman, et al. Expires May 2003 [Page 28] Internet Draft NORM Protocol November 2002 The "cc_rtt" contains a quantized representation of the receiver's individual sender<->receiver RTT. This field is only valid if and only if the NORM_FLAG_RTT flag is set in the "cc_flags" field. This one byte field is quantized representation of the RTT using the quantization algorithm described in the RMT NORM Building Block document (currently "draft-rmt-bb-norm-04.txt"). The "cc_rate" field contains a representation of the receiver's current calculated (during steady-state congestion control opera- tion) or measured (during the "slow start" phase) congestion con- trol rate. This field is encoded and decoded using the same tech- nique as described for the NORM_CMD(CC) "send_rate" field. NORM_CMD(APPLICATION) This command allows the NORM application to robustly transmit application defined content. The message preempts any ongoing data transmission and is repeated ROBUST_FACTOR times at a rate of once per 2*GRTT. This rate of repeat allows the application to collect a response (if that is the application's purpose for the command) before it is repeated. Regular data object transmission is resumed when the repeated transmission of this message has completed. This command allows NORM applications to have a robust simple communica- tion with less state than the transfer of FEC encoded reliable con- tent requires. NORM_CMD(APPLICATION) Message 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | grtt | gsize | flavor = 6 | reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | application defined content ... | 2.3.3 Receiver Messages: 2.3.3.1 NORM_NACK The principal purpose of NORM_NACK messages will be for receivers to request repair of content via negative acknowledgement upon detection of incomplete data. NORM_NACKs will be transmitted according to the rules of NACK generation and suppression of the NORM NACK process. A goal for the content of these messages is to use a format which can be potentially used by compatible intermedi- ate systems [REF Generic Router Assist Building Block] to provide assistance in promoting protocol scalability and efficiency when available. NORM_NACK messages generated will also contain Adamson, Borman, et al. Expires May 2003 [Page 29] Internet Draft NORM Protocol November 2002 additional content to provide feedback to sender(s) for purposes of round-trip timing collection, congestion control, etc. NORM_NACK messages are transmitted by NORM receivers in response to the detection of missing data in the sequence of transmissions received from a particular source. The specific times and condi- tions under which receivers will generate and transmit these NORM_NACK messages are governed by the processes described in detail later in this document. The payload of NORM_NACK messages contains one or more "ObjectNACKs" for different objects and por- tions of those objects. In addition to the common message header the NORM_NACK messages contain the following fields: NORM_NACK Header 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | server_id | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | grtt_response_sec | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | grtt_response_usec | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | cc_flags | cc_rtt | cc_loss | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | cc_rate | cc_sequence | reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | nack_content ... | The "server_id" field identifies the source to which the NORM_NACK message is destined. Other sources should ignore this message. (Note that this another reason why multiple potential sources within an NORM session MUST have unique NormNodeIds). The "grtt_response" fields contain a timestamp indicating the time at which the NORM_NACK was transmitted. The format of this times- tamp is the same as the "send_time" field of the NORM_CMD(ACK_REQ(RTT)). However, note that the "grtt_response" timestamp is _relative_ to the "send_time" the source provided with the corresponding NORM_CMD(ACK_REQ(RTT)) command. The receiver adjusts the source's NORM_CMD(ACK_REQ(RTT)) "send_time" timestamp by the time differential from when the receiver received the NORM_CMD(ACK_REQ(RTT)) to when the NORM_NACK was transmitted to calculate the value in the "grtt_response" field. This is the "receive_to_response_differential" value in he following formula: "grtt_response" = request "send_time" + receive_to_response_differential Adamson, Borman, et al. Expires May 2003 [Page 30] Internet Draft NORM Protocol November 2002 The receiver may set the "grtt_response" to a ZERO value, to indi- cate that the it has not yet received a NORM_CMD(ACK_REQ(RTT)) com- mand from the source and the source should ignore the grtt_response in this message. The "cc_flags", "cc_rtt", and "cc_rate" fields have the same possi- ble values and interpretation as the corresponding field in the NORM_CMD(CC) "cc_node_list" items. The values for these fields are determined locally by the receiver based on information it has mea- sured or received from the sender. The "cc_loss" field is the receiver's current packet loss fraction estimate for the indicated source. The loss fraction is a value from 0.0 to 1.0 corresponding to a range of zero to 100 percent packet loss. The 16-bit "cc_loss" value is calculated by the fol- lowing formula: "cc_loss" = decimal_loss_fraction * 65535.0 The "cc_sequence" field contains the value of the current greatest "cc_sequence" number of received NORM_CMD(CC) messages from the corresponding sender. This information can assist the sender in congestion control operation by providing an indicator of how cur- rent ("fresh") the receiver's round-trip time reference time and whether the receiver has been successfully receiving recent conges- tion control probes. For example, if it is apparent the receiver has not been receiving recent congestion control probes (and thus possibly other messages from the sender), the sender may choose to take congestion avoidance measures. The "cc_flags" field contains bits set pertaining to the receiver's state with respect to congestion control operation. The possible values for the "cc_flags" field are the same as specified for the NORM_CMD(CC) message node list member flags. The "nack_content" of the NORM_NACK message specifies the repair needs of this client pertaining to the indicated "server_id". The repair needs are specified as one or more lists of individual "items", "ranges", and/or FEC coding block "erasure_counts" of identified NORM_DATA and/or NORM_INFO messages required for the receiver to complete reliable reception of objects being transmit- ted by the sender. Each list of "items", "ranges", or "erasure_counts" is specified with the following packet format: Adamson, Borman, et al. Expires May 2003 [Page 31] Internet Draft NORM Protocol November 2002 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | form | flags | length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | object_transport_id | fec_block_number_msb | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | fec_block_number_lsb | fec_symbol_id or erasure_count| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | The "form" field indicates currently whether the NACK content that follows is a list of NORM_NACK_ITEMS, NORM_NACK_RANGES, or NORM_NACK_ERASURES. Possible values for the "form" field include: Form Value NORM_NACK_ITEMS 1 NORM_NACK_RANGES 2 NORM_NACK_ERASURES 3 When the list consists of individual NORM_NACK_ITEMS, each concate- nation of "object_transport_id>fec_block_number>fec_symbol_id" identifies an individual repair need of the NACKing receiver. When the list consists of NORM_NACK_RANGES, pairs of "object_trans- port_id>fec_block_number>fec_symbol_id" sets are given to indicate the inclusive range of sender information needed by the receiver. When the list consists of NORM_NACK_ERASURES, each "object_trans- port_id>fec_block_number>erasure_count" concatenation listed indi- cates the receiver's FEC erasure count for the identified object and FEC encoding block. The "flags" field is currently used to indicate if the NACK content applies to NORM_DATA content, NORM_INFO content, or both. Thus, defined flags in this field include: Adamson, Borman, et al. Expires May 2003 [Page 32] Internet Draft NORM Protocol November 2002 +------------------+-------+------------------------------------------+ | Flag | Value | Purpose | +------------------+-------+------------------------------------------+ |NORM_NACK_SEGMENT | 0x01 | Indicates the listed segment(s) are | | | | required as repair. | +------------------+-------+------------------------------------------+ |NORM_NACK_BLOCK | 0x02 | Indicates the entire listed block(s) are | | | | required as repair. | +------------------+-------+------------------------------------------+ |NORM_NACK_INFO | 0x04 | Indicates the object's NORM_INFO is | | | | required as repair. | +------------------+-------+------------------------------------------+ |NORM_NACK_OBJECT | 0x08 | Indicates the entire listed object(s) | | | | are required as repair. | +------------------+-------+------------------------------------------+ When the NORM_FLAG_SEGMENT flag is set, the "object_transport_id", "fec_block_number" and "fec_symbol_id" fields are concatenated to determine which sets or ranges of individual NORM_DATA segments are needed to repair data at this receiver. When the NORM_FLAG_BLOCK flag is set, this indicates the receiver is completely missing the indicated coding block(s) and requires transmissions sufficient to repair the block(s) in entirety. In this case the "fec_symbol_id" fields are ignored. When the NORM_NACK_INFO flag is set, this indicates the receiver is missing the NORM_INFO segment for the indicated "object_transport_id". Note the NORM_NACK_INFO may be set in combination with the NORM_NACK_BLOCK or NORM_NACK_SEGMENT flags, or may be set alone. When the NORM_NACK_OBJECT flag is set, this indicates the receiver is missing the entire NormTransportOb- ject referenced by the "object_transport_id". This implicitly includes any available NORM_INFO if applicable. The "fec_block_number" and "fec_symbol_id" fields are ignored when this flag is set. The "length" field is given (in bytes) to indicate the length of the list of NORM_NACK_ITEMS or NORM_NACK_RANGES. Multiple lists of NACK items and/or ranges may be concatenated together within a sin- gle NORM_NACK message. NACK Content Examples: In Example 1, a list of individual NORM_NACK_ITEMS is given. In Example 2, a list of NORM_NACK_RANGES _and_ a list of a single NORM_NACK_ITEM are concatenated to illustrate the possible content of a NORM_NACK message. Note that FEC coding block erasure counts are provided in each case. Adamson, Borman, et al. Expires May 2003 [Page 33] Internet Draft NORM Protocol November 2002 Example 1: NACK for object 12, Coding Block 3, segments 2,5,8 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | form = 3 | flags = 0x01 | length = 8 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | object_transport_id = 12 | fec_block_number_msb = 0 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | fec_block_number_msb = 3 | erasure_count = 3 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | form = 1 | flags = 0x01 | length = 24 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | object_transport_id = 12 | fec_block_number_msb = 0 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | fec_block_number_msb = 3 | fec_symbol_id = 2 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | object_transport_id = 12 | fec_block_number_msb = 0 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | fec_block_number_msb = 3 | fec_symbol_id = 5 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | object_transport_id = 12 | fec_block_number_msb = 0 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | fec_block_number_msb = 3 | fec_symbol_id = 8 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Adamson, Borman, et al. Expires May 2003 [Page 34] Internet Draft NORM Protocol November 2002 Example 2: NACK for object 18, Coding Block 6, segments 5, 6, 7, 8, 9, 10 and object 19, NORM_INFO and Coding Block 1, segment 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | form = 3 | flags = 0x01 | length = 8 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | object_transport_id = 18 | fec_block_number_msb = 0 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | fec_block_number_msb = 6 | erasure_count = 6 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | form = 2 | flags = 0x01 | length = 16 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | object_transport_id = 18 | fec_block_number_msb = 0 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | fec_block_number_msb = 6 | fec_symbol_id = 5 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | object_transport_id = 18 | fec_block_number_msb = 0 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | fec_block_number_msb = 6 | fec_symbol_id = 10 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | form = 3 | flags = 0x05 | length = 8 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | object_transport_id = 19 | fec_block_number_msb = 0 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | fec_block_number_msb = 1 | erasure_count = 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | form = 1 | flags = 0x05 | length = 8 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | object_transport_id = 19 | fec_block_number_msb = 0 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | fec_block_number_msb = 1 | fec_symbol_id = 3 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2.3.3.2 NORM_ACK The basic operation of NORM transport will _not_ rely on the use NORM_ACK (positive acknowledgement) messages. However, some appli- cations may benefit from some limited form of positive acknowledge- ment for certain functions. A simple, scalable positive acknowl- edgement scheme is defined which can be leveraged by protocol implementations when appropriate. Adamson, Borman, et al. Expires May 2003 [Page 35] Internet Draft NORM Protocol November 2002 NORM_ACK Message 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | server_id | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | grtt_response_sec | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | grtt_response_usec | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | cc_flags | cc_rtt | cc_loss | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | cc_rate | cc_sequence | ack_flavor | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ACK Content ... | The "server_id", "grtt_response", "cc_flags", "cc_rtt", "cc_loss", "cc_rate", and "cc_sequence" fields serve the same purpose as the corresponding fields in NORM_NACK messages. The "ack_flavor" field indicates the nature of the following ACK content. This directly corresponds to the "ack_flavor" field of the NORM_CMD(ACK_REQ) message. For example, if the sender has requested explicit positive acknowledgement of reception of a watermark "object_transport_id" and "fec_block_number", the receiver will respond with "ack_flavor=NORM_ACK(WATERMARK) and appopriately valued "object_transport_id" and "fec_block_number" fields. If the NORM_ACK is simply a response to an explicit NORM_CMD(GRTT_REQ), the "ack_flavor" is set to NORM_ACK(RTT) and there is _no_ ACK content. (The length of the content may be inferred from the NORM_ACK packet payload size). NORM_ACK(WATERMARK) Content +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | object_transport_id | fec_block_number_msb | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | fec_block_number_lsb | fec_symbol_id | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The "object_transport_id", "fec_block_number", and "fec_symbol_id" are used by the receiver to acknowledge a NORM_CMD(ACK_REQ(WATER- MARK)) transmitted by the sender identified by the "server_id" field. The NORM_ACK(RTT) message has no attached content. Only the NORM_ACK header applies. Note that the NORM_ACK(RTT) message is Adamson, Borman, et al. Expires May 2003 [Page 36] Internet Draft NORM Protocol November 2002 also used as a feedback message in response to NORM_CMD(CC) mes- sages as well as NORM_CMD(ACK_REQ(RTT)) messages. Since it may be useful for applications to leverage the NORM posi- tive acknowledgement mechanism for other purposes, additional NORM_ACK "ack_flavors" may be used by the application for other purposes. The content of the NORM_ACK message (past the NORM_ACK header "reserved" field) for application-defined "ack_flavor" val- ues, is specific to the application but is limited is size to the NormSegmentSize of the sender referenced by the "server_id". 2.3.4 General Messages: 2.3.4.1 NORM_REPORT This is an optional message generated by NORM participants. This message may include periodic performance reports from receivers. Additionally, this message type may be potentially used by applica- tions to perform other session management functions such as period- ically advertising the full identity of a participant or the gen- eral context (more general than NORM_INFO messages which are asso- ciated with specific data content objects) of the content being transmitted to the group by a sender. The format of this message is TBD. 3.0 Detailed Protocol Operation This section describes the detailed interactions of senders and receivers participating in a NORM session. A simple synopsis of protocol operation is given in the following items. 1) The sender periodically transmits NORM_CMD(ACK_REQ(RTT)) mes- sages and/or NORM_CMD(CC) messages as needed to initialize and col- lect roundtrip timing and congestion control feedback from the receiver set. 2) The sender transmits an ordinal set of NormObjects in the form of NORM_DATA (and optional NORM_INFO) messages labelled with Nor- mObjectTransportIds and logically identified with FEC encoding block numbers and symbol identifiers. 3) As receivers detect missing content from the receiver, they ini- tiate repair requests with NORM_NACK messages. Note the receivers track the sender's most recent "object_transport_id>fec_block_num- ber>fec_symbol_id" transmit position and NACK _only_ for content ordinally prior to that transmit position. The receivers use ran- dom backoff timeouts before generating NORM_NACK messages and wait an appropriate amount of time before repeating the NORM_NACK if Adamson, Borman, et al. Expires May 2003 [Page 37] Internet Draft NORM Protocol November 2002 their repair request is not satisified. 4) The sender aggregates repair requests from the receiver set and "rewinds" to send appropriate repair messages. The sender sends repairs for the earliest ordinal transmit position first and main- tains this ordinal repair transmission sequence. Previously untransmitted FEC parity content for the applicable FEC coding block is used for repair transmissions to the greatest extent pos- sible. If the sender exhausts its available FEC parity content on multiple repair cycles for the same coding block, it resorts to an explicit repair strategy (again using parity content) to complete repairs. (The use of explicit repair is expected to be an excep- tion in general protocol operation, but the possibility does exist). The sender immediately assumes transmission of new content once it has sent pending repair transmissions. 5) The sender transmits NORM_CMD(FLUSH) messages when it reaches the end of newly available transmit content. Receivers respond to the NORM_CMD(FLUSH) messages with NORM_NACK transmissions (follow- ing the same suppression backoff timeout strategy as for data). 6) The sender transmission rate is subject to rate control limits determined by congestion control. Each sender in a NormSession maintains its own independent congestion control state. While the overall concept of the protocol is relatively simple, there are details to each of these aspects which need to be addressed for successful, robust, and scalable operation. 3.1 Sender Initialization and Transmission Upon startup, the NORM sender immediately begins sending either NORM_CMD(ACK_REQ(RTT)) or NORM_CMD(CC) (when congestion control operation is enabled) messages to collect GRTT and other informa- tion from the potential group. In some cases, applications may wish for the sender to also proceed with data transmission immedi- ately. In other cases, the sender may wish to defer data transmis- sion until it has received some feedback or request from the receiver set indicating that receivers are indeed present. Note, in some applications (e.g. web push), this indication may come out- of-band with respect to the multicast session via other means. The NORM protocol sender message headers contain all information necessary to configure receivers for subsequent reliable reception. This includes FEC coding parameters, the sender NormSegmentSize, and other information. Additionally, applications, may leverage the use of NORM_INFO messages associated with the session or data objects in the session to provide application-specific context Adamson, Borman, et al. Expires May 2003 [Page 38] Internet Draft NORM Protocol November 2002 information for the session and/or data being transmitted. The NORM sender begins segmenting application-enqueued data into NORM_DATA segments and transmitting it to the group. The rate of transmission is controlled via the congestion control mechanisms described in this document or at a fixed rate if desired for closed network operations. The receivers who have joined (or subsequently join) the multicast group provide feedback to the sender as needed. 3.2 Receiver Initialization and Reception The NORM protocol is designed such that receivers may join and leave the group at will. However, some applications may be con- strained that receivers need to be members of the group prior to start of data transmission. NORM protocol implementations may use different policies to constrain the impact of new receivers joining the group in the middle of a session. For example, a useful imple- mentation policy is for new receivers joining the group to restrain requesting repair of transport objects in progress. The NORM sender implementation may wish to impose additional constraints to limit the ability of receivers to disrupt reliable multicast per- formance by joining, leaving, and rejoining the group often. Dif- ferent receiver join "policies" may be appropriate for different applications and/or scenarios. 3.3 Receiver NACK Procedure When the receiver detects it is missing data from a sender's stream of reliable transmissions, it initiates its NACKing procedure. The NACKing procedure SHALL be initiated _only_ at NormObject bound- aries, FEC coding block boundaries, or upon receipt of a NORM_CMD(FLUSH) or NORM_CMD(ACK_REQ(WATERMARK)) message. The NACKing procedure begins with a random backoff timeout. The duration of the backoff timeout is chosen using the "RandomBackoff" algorithm described in the NORM Building Block document (currently "draft-ietf-rmt-bb-norm-04.txt") using (K*GRTTsender) for the "max- Time" parameter and the sender advertised group size (GSIZEsender) as the "groupSize" parameter. The backoff factor "K" should be greater than one to provide for any suppression and a value of 4 is recommended for most purposes. Thus: T_backoff = RandomBackoff(K*GRTTsender, GSIZEsender) During this backoff time, the receiver accumulates external pending repair state from NORM_NACK messages and NORM_CMD(REPAIR_ADV) mes- sages received. At the end of the backoff time, the receiver SHALL generate a NORM_NACK message only if the following conditions are Adamson, Borman, et al. Expires May 2003 [Page 39] Internet Draft NORM Protocol November 2002 met: 1) The sender's current transmit position (in terms of "object_transport_id>fec_block_number>fec_symbol_id" exceeds the earliest repair position of the receiver. 2) The repair state accumulated from NORM_NACK and NORM_CMD(REPAIR_ADV) messages do not equal or supersede the receiver's repair needs. If these conditions are met, the receiver immediately generates a NORM_NACK message when the backoff timeout expires. The content of the NORM_NACK message contains NACK content begin- ning with lowest ordinal repair position for the receiver up to the most recently heard ordinal transmission position for the sender. If size of the NACK content exceeds the NormSegmentSize, the NACK content is limited to that point so that the receiver only gener- ates a single NORM_NACK message per NACK cycle for a given sender. For each FEC coding block requiring repair, the receiver MUST, on the _first_ repair cycle for the block, request the parity portion of the FEC coding block beginning with the lowest ordinal _parity_ "fec_symbol_id" and request the number of symbols corresponding to its erasure count for the block. On _subsequent_ repair cycles for the same coding block, the receiver MUST request only those parity repair symbols from the first set it has not yet received up to the remaining erasure count for that applicable coding block. (Note that the sender may have provided other additional parity segments for other receivers which can also be used to satisfy the local receiver's erasure-filling needs). The goal of this strategy is for the overall receiver set to request a lowest common denominator set of repair symbols for a given FEC coding block. This allows the sender to construct the most efficient repair transmission seg- ment set and enables effective NACK suppression among the receivers even with uncorrelated packet loss. 3.4 Sender NACK Processing and Repair Transmission 3.4.1 NORM_NACK Repair State Aggregation The principle goal of the sender is to make forward progress in the transmission of data its application has enqueued. However, the sender must occasionally "rewind" to satisfy the repair needs of receivers who have NACKed. When a sender is in its normal state of transmitting new data and receives a NACK, it begins a procedure to accumulate NACK repair state from NORM_NACK messages before begin- ning repair transmissions. Note that this period of aggregating Adamson, Borman, et al. Expires May 2003 [Page 40] Internet Draft NORM Protocol November 2002 repair state does _not_ interfere with its ongoing transmission of new data. The period of time during which the sender aggregates NORM_NACK messages is equal to K*GRTT where "K" is the same backoff scaling value used by the receivers and "GRTT" is the sender's current estimate of the group's greatest round-trip time. When this period ends, the sender "rewinds" by incorporating the accumulated repair state into its pending transmission state and begins transmitting repair messages, then continuing with new transmissions of any enqueued data. Also, at this point in time, the sender begins a "holdoff" timeout of 1*GRTT during which time the sender constrains itself from initiating a new repair aggregation cycle, even if NORM_NACK messages arrive. If additional NORM_NACK messages are received during this hold-off period, the sender will immediately incorporate these into its pending transmission state ONLY if the NACK content is ordinally greater than the sender's current trans- mission position. This "holdoff" time allows worst case time for the sender to propagate its current transmission sequence position to the group, thus avoiding redundant repair transmissions. After the holdoff timeout expires, a new NACK accumulation period can be begun (upon arrival of a NACK) in concert with the pending repair and new data transmission. The sender repeats the same process of incorporating accumulated repair state into its transmission plan during the the new aggregation period and subsequently "rewinding" to transmit the lowest ordinal repair data. 3.4.2 FEC Repair Transmission Strategy The NORM sender should leverage transmission of FEC parity content for repair to the greatest extent possible. Recall that the receivers' use a strategy to request a lowest common denominator of explicit repair (including parity content) in the formation of their NORM_NACK messages. Before falling back to explicitly satis- fying all of the different receivers' repair needs, the sender can make use of the general erasure filling capability of FEC-generated parity segments. The sender can determine the maximum erasure filling needs for individual FEC coding blocks from the NORM_NACK messages received during the repair aggregation period. Then, if the sender has a sufficient number (less than or equal to the maxi- mum erasure count) of previously unsent parity segments available for the applicable coding blocks, the sender can transmit these in lieu of the specific packets the receiver set has requested. Only after exhausting its supply of "fresh" (unsent) parity segments for a given coding block should the sender resort to explicit transmis- sion of the receiver set's repair needs. In general, if a suffi- ciently powerful FEC code is used, the need for explicit repair will be an exception, and the fulfillment of reliable multicast can Adamson, Borman, et al. Expires May 2003 [Page 41] Internet Draft NORM Protocol November 2002 be accomplished quite efficiently. However, the ability to resort to explicit repair allows the protocol to be reliable under even very extreme circumstances. NORM_DATA messages sent as repair transmissions are flagged with the NORM_FLAG_REPAIR flag. This allows receivers to obey any poli- cies which limit new receivers from joining the reliable transmis- sion on repair transmissions. To facilitate operation with Generic Router Assist (GRA), the sender can additionally flag NORM_DATA transmissions sent as explicit repair with the NORM_FLAG_EXPLICIT flag. The GRA router needs to only subcast a sufficient count of non-explicit parity repairs to satisfy the sub-tree's erasure filling needs for a given FEC coding block. When the sender has resorted to explicit repair, the GRA router will subcast all of the explicit repair packets to those portions of the routing tree still requiring repair for a given coding block. (Note the GRA router will be required to con- duct repair state accumulation for sub-routes in a manner similar to the sender's repair state accumulation in order to have suffi- cient information to perform the subcasting. Additionally, the GRA router can perform additional NORM_NACK suppression/aggregation as it conducts this repair state accumulation for NORM repair cycles). 3.4.3 NORM_CMD(SQUELCH) Generation If the sender receives a NORM_NACK message for repair of data it is no longer supporting, the sender generates a NORM_CMD(SQUELCH) mes- sage to advertise its repair window and squelch any receivers from additional NACKing of invalid data. The transmission rate of NORM_CMD(SQUELCH) messages is limited to once per 2*GRTT. The "invalid_object_list" (if applicable) of the NORM_CMD(SQUELCH) mes- sage SHALL begin with the lowest "object_transport_id" from the set of NORM_NACKs for invalid data received since the last NORM_CMD(SQUELCH) transmission. Lower ordinal invalid "object_transport_ids" should be included only while the NORM_CMD(SQUELCH) payload is less than the sender's NormSegmentSize parameter. 3.4.4 NORM_CMD(REPAIR_ADV) Generation When a NORM sender receives NORM_NACK messages from receivers via unicast transmission, it uses NORM_CMD(REPAIR_ADV) messages to advertise its accumulated repair state to the receiver set since the receiver set is not communicating this with each other via mul- ticast communication. The NORM_CMD(REPAIR_ADV) message is multi- cast to the receiver set. The content of this message is in the same format as NORM_NACK messages and receivers are able to process Adamson, Borman, et al. Expires May 2003 [Page 42] Internet Draft NORM Protocol November 2002 these messages in a similar manner that NORM_NACKs from other receivers are processed to facilitate feedback suppression. Note the sender does not merely retransmit the NACK content it receives, but instead transmits a representation of its aggregated repair state. The transmission of NORM_CMD(REPAIR_ADV) messages are sub- ject to the sender transmit rate limit and NormSegmentSize limit. When the NORM_CMD(REPAIR_ADV) message is of maximum size, receivers should also consider the maximum ordinal transmission position value embedded in the the message as the senders "current" trans- mission position and not NACK for ordinally higher repairs. 3.5 Additional Protocol Mechanisms 3.5.1 Round-trip time collection For NORM receivers to appropriately scale backoff timeouts and the senders to use proper corresponding timeouts, the participants must agree on a common time base. Each NORM sender monitors the round- trip time of active receivers and determines the greatest round- trip time of the group (GRTT). The sender advertises this GRTT estimate in every message it transmits so that receivers have this time available. The sender periodically sends NORM_CMD(ACK_REQ(RTT)) messages which contain a locally generated timestamp. Receivers are expected to record this timestamp along with the time the NORM_CMD(ACK_REQ(RTT)) is received. Then, when the receivers generate feedback messages to the sender, an adjusted version of the sender timestamp is embedded in the feedback message (NORM_NACK or NORM_ACK). The adjustment adds the amount of time the receiver held the timestamp before generating its response. From this adjusted timestamp, the sender is able to calculate the round-trip time to that receiver. The round-trip time for each receiver is fed into an algorithm which weights and smooths the values for a conservative estimate of the GRTT. The algorithm and methodology is described in the NORM Building Block document (currently "draft-ietf-rmt-bb-norm-03.txt") in section 3.7.1 "One-to-Many Sender GRTT Measurement". A conser- vative estimate helps feedback suppression at a small cost in over- all protocol repair delay. The sender's current estimate of GRTT is advertised in the "grtt" field found in all NORM sender mes- sages. The advertised GRTT is also limited to be at least as big as the nominal inter-packet transmission time given the sender's current transmission rate. The reason for this additional limit is to keep the receiver somewhat "event driven" by making sure the sender has had adequate time to generate any response to repair requests from receivers given transmit rate limitations due to con- gestion control or configuration. Adamson, Borman, et al. Expires May 2003 [Page 43] Internet Draft NORM Protocol November 2002 Typically, the "acking_node_list" of the NORM_CMD(ACK_REQ(RTT)) message may be empty with only NORM_NACK feedback messages supply- ing adjusted timestamps to the sender for processing. However, it may be useful for a session initialization period to explicitly collect feedback from all receivers. In this case the "ack- ing_node_list" can contain the "wildcard" NormNodeId value and/or a specific list of receivers to provide GRTT feedback. Note the round-trip values collected with this mechanism _may_ be useful for congestion control operation. However, it is possible that congestion control may require receivers to determine their round-trip time with respect to the sender and additional mecha- nisms may be provided with the NORM_CMD(CC) message. 3.5.2 Group Size Estimation (TBD) Group size may be approximated from the volume of feedback messages which follow the exponentially weighted random backoff. NORM_NACK messages might be used during normal protocol operation or a bootstrap procedure can be created to obtain an initial size estimation and track group size with receiver join/leave dynamics. This might also be combined with congestion control feedback col- lection. The details of this are TBD. Until then, the group size estimation used by NORM participants may be determined a priori, via out-of-band means, or set conservatively. With the exponen- tially-distributed feedback mechanisms used in NORM, a conservative estimate of group size will result in some additional delay in reliable transmission (and thus slightly increase buffering requirements for a given multicast topology), but will not result in excessive feedback from the group. 3.5.3 Congestion control operation This section describes congestion control operation for the NORM protocol. The supporting NORM message formats and approach described here are an adaptation of the equation-based TCP-Friendly Multicast Congestion Control (TFMCC) approach described in [REF]. With this TFMCC-based approach, the transmission rate of NORM senders is controlled in a rate-based manner as opposed to window- based congestion control algorithms as in TCP. However, it is pos- sible that the NORM protocol message set may alternatively be used to support a window-based multicast congestion control scheme such as PGMCC [REF]. The details of that alternative will be described separately or in a future revision of this document. In either case (rate-based TFMCC or window-based PGMCC), successful control of sender transmission depends upon collection of sender->receiver packet loss estimates and sender<->receiver RTT to identify the congestion control bottleneck path(s) within the multicast topology Adamson, Borman, et al. Expires May 2003 [Page 44] Internet Draft NORM Protocol November 2002 and adjust the sender rate accordingly. The receiver with loss and RTT estimates that correspond to the lowest result transmission rate is identified as the "worst path representative" (WPR). The steady-state sender transmission rate, to be "friendly" with competing TCP flows is calculated as: S Rsender = --------------------------------------------------------------- tRTT * (sqrt((2/3)*p) + 12 * sqrt((3/8)*p) * p * (1 + 32*(p^2))) where S = Nominal transmitted packet size. (The "nominal" packet size is determined by the sender as an exponentially weighted moving average (EWMA) of transmitted packet sizes to account for variable message sizes). tRTT = The RTT estimate of the current "worst path representative" (WPR). p = The loss event fraction of the WPR. To support congestion control feedback collection and operation, the NORM sender periodically transmits NORM_CMD(CC) command mes- sages. When congestion control operation is enabled, the NORM_CMD(CC) messages supersed the NORM_CMD(ACK_REQ(RTT)) messages sent to assist in the estimation of GRTT. With congestion control operation, the GRTT is determined from congestion control feedback. The NORM_CMD(CC) messages are interleaved with NORM data and repair transmissions and serves several of purposes: 1) Stimulate explicit feedback from the general receiver set to collect congestion control information. 2) Communicate state to the receiver set on the sender's current congestion control state including details of the current WPR. 3) Initiate rapid (immediate) feedback from the current WPR in order to closely track the dynamics of congestion control for that "worst path" in the sender->receiver multicast topology. The format of the NORM_CMD(CC) message is describe in Section 2.3.2.3 of this document. The NORM_CMD(CC) message contains infor- mation to allow for determination of sender<->receiver RTT, to inform the group of the current congestion control "worst path Adamson, Borman, et al. Expires May 2003 [Page 45] Internet Draft NORM Protocol November 2002 representative", and to provide feedback of individual RTT informa- tion to receivers in the group. 3.5.3.1 NORM_CMD(CC) Transmission The NORM_CMD(CC) message is tranmitted periodically by the sender along with its normal data transmission. Note that the repeated transmission of NORM_CMD(CC) messages may be initiated some time before transmission of user data content at session startup. This may be done to collect some estimation of the current state of the multicast topology with respect to group and individual RTT and congestion control state. A NORM_CMD(CC) message is immediately transmitted at sender startup. The interval of subsequent NORM_CMD(CC) message transmis- sion is determined as follows: 1) By default, the interval is set according to the current sender GRTT estimate. A default GRTT of 0.5 seconds is recommended when no feedback has yet been received from the group. 2) If a "worst path representative" (WPR) has been identified (based on previous receiver feedback), the interval is the sender<->receiver RTT for the current WPR. 3) Additionally, if the interval of nominal data message transmis- sion is greater than the GRTT or WPR RTT interval, the NORM_CMD(CC) interval is set to this greater value. This ensures that the transmission of this control message is not done to the exclusion of user data transmission. The "cc_sequence" field is incremented with each transmission of a NORM_CMD(CC) message. The "cc_sequence" most recently received by receivers is included in feedback to the sender. This allows the sender to determine the "age" of feedback to assist in congestion avoidance. The sender advertises its current transmission rate in the "cc_rate" field of the NORM_CMD(CC) message. This rate information is used by receivers to bias the timing of explicit feedback and to initialize loss estimation during congestion control startup or restart. The "cc_node_list" contains a list of entries identifying receivers and their current congestion control state ("rtt" and "loss" esti- mates). The list may be empty if the sender has not yet received any feedback from the group. If the sender has received feedback, the list will minimally contain an entry identifying the current Adamson, Borman, et al. Expires May 2003 [Page 46] Internet Draft NORM Protocol November 2002 WPR. A NORM_FLAG_WPR flag value is provided for the "cc_flags" field to identify the WPR entry. It is recommended that the WPR entry is first in the list for implementation efficiency. Addi- tional entries in the list are used to feedback individual RTT estimates to receivers in the group. The number of additional entries in this list is dependent upon the percentage of control traffic the sender application is willing to send with respect to user data message transmissions. More entries in the list may allow the sender to be more responsive to congestion control dynam- ics. The length of the list may be dynamically determined accord- ing to the current transmission rate and scheduling of NORM_CMD(CC) messages. The maximum length of the list corresponds to the sender's "NormSegmentSize" parameter for the session. The inclu- sion of additional entries in the list based on receiver feedback are prioritized with following rules: 1) Receivers which have not yet been provided RTT feedback get first priority. Of these, those with the greatest loss fraction receive precedence for list inclusion. 2) Secondly, receivers which have previously been provided RTT are included with receivers yielding the lowest calculated congestion rate getting precedence. There are also "cc_flag" values in addition to NORM_FLAG_WPR which may be used to provide for some optional congestion control func- tionality. The NORM_FLAG_WPC ("worst path candidate" (WPC)) flag value is used to mark additional receivers from which the sender would like to have immediate, non-suppressed feedback. These may be receivers which the sender has algorithmically identified as potential, future WPRs or which have been pre-configured as poten- tial congestion control points in the network. The NORM_FLAG_RTT indicates the validity of the "cc_rtt" and "cc_rate" fields for the associated receiver node. Normally, this flag will be set since the receivers in the list will typically be receivers from which the sender has previously received feedback. However, in the case that the NORM sender has been pre-configured with a set of "worst path candidates", feedback from those receivers may not yet have been collected and thus the "cc_rtt" and "cc_rate" fields do not contain valid values. 3.5.3.2 NORM_CMD(CC) Feedback Response Receivers explicitly respond to NORM_CMD(CC) messages in the form of a NORM_ACK(RTT) message. Receivers which are are marked as WPR or WPC receivers in the NORM_CMD(CC) "cc_node_list" immeditately provide feedback to this message. When a NORM_CMD(CC) is received, Adamson, Borman, et al. Expires May 2003 [Page 47] Internet Draft NORM Protocol November 2002 non-WPR or non-WPC receivers initiate random feedback backoff time- outs similar to that used when the receiver initiates a repair cycle (See Section 3.3) in response to detection of data loss. The goal of the congestion control feedback is to determine the receivers with the lowest congestion control rates. As described in [TFMCC reference], the receiver feedback timeouts can be biased in favor of lower rate receivers (while maintaining effective feed- back suppression). This is not necessarily possible with suppres- sion of NORM_NACK messages since previous data and repair loss his- tory may not be correlated with the current data loss. The backoff timeout for the congestion control response is picked and biased as follows: T_backoff = y*r*(K*GRTTsender) + (1 - y)*RandomBack- off(K*GRTTsender, GSIZEsender) where "y" is the fraction of (K*GRTT) used to offset the backoff with respect to the sender's current transmission rate. A value of y = 0.25 is recommended. "r" is adjusted ratio of the local receiver's calculated rate to the sender's current rate. During steady-state congestion control operation, "r" is determined as: r = (MAX(MIN((Rcalc / Rsender), 0.9), 0.5) - 0.5) / 0.4 During the "slow start" phase of congestion control operation, "r" is determined simply as: r = Rrecv / Rsender where "Rrecv" is the measured received rate. This "Rrecv" rate is also what the receiver places in the "cc_rate" field of its NORM_NACK or NORM_ACK feedback messages during the "slow start" phase of congestion control operation. The RandomBackoff() algorithm provides a truncated exponentially distributed random number and is described in the NORM Building Block document (currently "draft-ietf-rmt-bb-norm-04.txt"). "K" is the same backoff factor used with the GRTT as for NORM_NACK suppression. Again, a value of K = 4 is generally recommended. A receiver shall cancel the backoff timeout and thus its pending transmission of a NORM_ACK(RTT) message under the following Adamson, Borman, et al. Expires May 2003 [Page 48] Internet Draft NORM Protocol November 2002 conditions: 1) The receiver provides another feedback message (NORM_NACK or NORM_ACK) before the congestion control feedback timeout expires, 2) A "suppressing" NORM_ACK(RTT) message is heard from another receiver or via a NORM_CMD(REPAIR_ADV) message from the sender. The local receiver's feedback is canceled if the rate of the com- peting feedback (Rfb) is sufficiently close to or less than the local receiver's calculated rate (Rcalc). The local receiver's feedback is canceled when: Rcalc > (0.9 * Rfb) According to [TFMCC REF], this bias of suppression is recommended to help ensure that the receiver with the lowest rate reports, while still maintaining a low volume of feedback from the receiver set. After the backoff timer expires the receiver generates a NORM_ACK(RTT) message to provide feedback to the sender and group. This message may be multicast to the group for most effective sup- pression in appropriate topologies or unicast to the sender depend- ing upon how the NORM protocol is deployed and configured. After a congestion control feedback message is generated or when the feedback is suppressed, the receiver begins a "holdoff" timeout period during which it will restrain itself from initiating another feedback cycle, even if NORM_CMD(CC) messages are received from the sender. The value of this timeout period is: T_holdoff = (K*GRTT) Thus, non-WPR receivers are constrained to providing explicit con- gestion control feedback once per K*GRTT intervals. Note however, that as the session progresses, different receivers will be responding to different NORM_CMD(CC) messages and there will be relatively continuous feedback of congestion control information while the sender is active. 3.5.3.3 Congestion Control Rate Adjustment During typical steady-state operation, the sender will directly adjust its transmission rate to the rate indicated by the feedback from its currently selected WPR. The estimation of parameters (loss and RTT) by the WPR constrain the rate changes possible within acceptable bounds. For rate increases, the sender SHALL observe a maximum rate of increase of one packet per RTT at all times during steady-state operation. There are some additional Adamson, Borman, et al. Expires May 2003 [Page 49] Internet Draft NORM Protocol November 2002 cases besides steady-state operatio which need to considered in protocol operation. These cases include: 1) Session startup, 2) When no feedback is received from the WPR, and 3) When the sender has a break in data transmission. During session startup, the congestion control operation shall observe a "slow start" procedure to quickly approach its fair band- width share. An initial startup rate is assumed where: Rinitial = MIN(NormSegmentSize / GRTT, NormSegmentSize) bytes/second. The rate is increased only when feedback is received from the receiver set. The "slow start" phase proceeds until any receiver provides feedback indicating that loss has occurred. Rate increase during "slow start" is applied as: Rnew = 2 * Rrecv_min where "Rrecv_min" is the minimum reported receiver rate in the "cc_rate" field of congestion control feedback messages received from the group. Rate increase adjustment is limited to once per GRTT during slow start. The sender can track the "age" of the feedback it has received from the WPR by comparing its current "cc_sequence" value (Ssender) to the last "cc_sequence" value received from the WPR (Swpr). As the "age" of the WPR feedback increases with no new feedback, the sender shall begin reducing its rate once per WPR RTT as a conges- tion avoidance measure. Note this assumes that the sender does not have explicit knowledge that the WPR intentionally left the group. If WPR intentionally leaves the group and the sender is informed (TBD - a message should be provided for this), the sender may choose the receiver with the next lowest rate as the new WPR. The sender is limited to increasing its rate at one additional packet per RTT towards the new WPR rate. The following algorithm is used to determine the decrease in sender rate (Rsender bytes/sec) as the WPR feedback, unexpectedly, exces- sively ages: Age = Ssender - Swpr; rate1 = MAX((Rsender - NormSegmentSize), 0.0); // bytes per sec rate2 = Rsender * 0.5 if (Age > 4) Rsender = MIN(rate1, rate2); Adamson, Borman, et al. Expires May 2003 [Page 50] Internet Draft NORM Protocol November 2002 else if (Age > 2) Rsender = MAX(rate1, rate2); Note that a longer term timeout may be implemented to drop the cur- rent WPR and pick another. The recommended length of this timeout is ROBUST_FACTOR * GRTT to allow adequate time for a response from the WPR. At this point, the sender may set the NORM_FLAG_START flag in its NORM_CMD(CC) messages to indicate to the receiver set that a "slow start" phase should be re-entered. In this case, the receivers will set the NORM_FLAG_START flag in their responses until another loss event is detected and "slow start" is once again exited. When the sender has a break in its data transmission, it can con- tinue to probe the group with NORM_CMD(CC) messages to maintain RTT collection from the group. This will enable the sender to quickly determine an effective WPR upon data transmission restart. How- ever, the sender should exponentially reduce its target rate to be used for transmission restart as time since the break elapses. The target rate should be recalculated once per WPR RTT as: Rsender = Rsender * 0.5; Upon restart, the sender should set the NORM_FLAG_START flag in its NORM_CMD(CC) messages and the group should observer "slow start" congestion control procedures until any receiver experiences a new loss event. 3.5.4 Positive Acknowledgment Procedure NORM provides an option for the source application to request posi- tive acknowledgment (ACK) of a reliable reception of watermark points of transmission or other events from a subset of receivers in the group. A simple robust polling procedure is used. This polling procedure is not intended to scale to very large receiver subsets. The list of receivers providing acknowledgement is deter- mined by the source application with "a priori" knowledge of par- ticipating nodes or via some other application-level mechanism. The "ack_flavor" of NORM_ACK(WATERMARK) (value = 1) is predefined for the sender to request positive acknowledgement of reliable reception to a watermark transmission point. The "ack_flavor" of NORM_ACK(RTT) (value = 2) is also defined for explicit round-trip timing collection as described above. It is possible that addi- tional "ack_flavor" values may be application-dependent so that applications (or other protocols utilizing NORM mechanisms) may leverage NORM's built-in positive acknowledgement collection Adamson, Borman, et al. Expires May 2003 [Page 51] Internet Draft NORM Protocol November 2002 mechanism. The ACK process is initiated by the sender who generates NORM_CMD(ACK_REQ) messages in periodic "rounds". For NORM_ACK(WATERMARK), these requests contain the "object_trans- port_id" and "fec_block_number>fec_symbol_id" denoting the water- mark transmission point. The ACK process is self-limiting and avoids ACK implosion in that: 1) Only a single NORM_CMD(ACK_REQ) message is generated once per (2*GRTT), and 2) The size of the "acking_node_list" of NormNodeIds from which ACK is requested is limited to a maximum of the sender Norm- SegmentSize setting per round of the positive acknowledge- ment process. The indicated receivers randomly spread their NORM_ACK responses uniformly in time over a window of (1*GRTT). As the source receives responses from receivers, it eliminates them from the mes- sage payload list and adds in pending receiver NormNodeIds keeping within the NormSegmentSize limitation of the list size. Each receiver is only queried for a maximum number of repeats (ROBUST_FACTOR, by default). Any receivers not responding within this number of repeated requests are removed from the payload list to make potential room for other receivers pending acknowledgement. The transmission of the NORM_CMD(ACK_REQ) is repeated until no further responses are required or until the repeat threshold is exceeded for all pending receivers. Note the positive acknowledg- ment process may be interrupted in response to negative acknowl- edgement repair requests (NACKs) received from receivers during the acknowledgment period. The ACK process is resumed once any pending repairs have been transmitted. Note that receivers will not ACK until they have received complete transmission of all data up to and including the watermark transmission point indicated in the NORM_CMD(ACK_REQ) message from the sender. Receivers will respond to the request with a NACK message if any repairs are required. 3.5.5 Operation with Generic Router Assist (GRA) NORM packet formats will be extended to allow for operation with GRA reliable multicast functions. Additional NACK suppression and selective sub-casting of repair transmissions in the network will be possible with GRA. (Section 3.4.2 discusses some NORM mecha- nisms related to this). Additional details will be provide in future versions of this document. Adamson, Borman, et al. Expires May 2003 [Page 52] Internet Draft NORM Protocol November 2002 3.5.6 Other (e.g. performance reporting, etc) 4.0 Security Considerations There are several security considerations with NORM which should be addressed for widespread deployment of this protocol. In addition to vulnerabilities which any IP and IP multicast protocol implemen- tation may be generally subject to, the NACK based feedback of NORM may be exploited by replay attacks which force the NORM sender to unnecessarily transmit repair information. This may be addressed by network layer IP security implementations which guard against this potential security exploitation. It is recommended that such IP security mechanisms be used when available. While NORM does leverage FEC-based repair for scalability, this does not alone guarantee integrity of received data. Application-level integrity-checking of data content is highly recommended. 5.0 Suggested Use The present NORM protocol is seen as useful tool for the reliable data transfer over generic IP multicast services. It is not the intention of the authors to suggest it is suitable for supporting all envisioned multicast reliability requirements. NORM provides a simple and flexible framework for multicast applications with a degree of concern for network traffic implosion and protocol over- head efficiency. NORM-like protocols have been successfully demon- strated within the MBone for bulk data dissemination applications, including weather satellite compressed imagery updates servicing a large group of receivers and a generic web content reliable "push" application. In addition, this framework approach has some design features mak- ing it attractive for bulk transfer in asymmetric and wireless internetwork applications. NORM is capable of successfully oper- ating independent of network structure and in environments with high packet loss, delay, and misordering. Hybrid proactive/reac- tive FEC-based repairing improve protocol performance in some mul- ticast scenarios. A sender-only repair approach often makes addi- tional engineering sense in asymmetric networks. NORM's unicast feedback capability may be suitable for use in asymmetric networks or in networks where only unidirectional multicast routing/delivery service exists. Asymmetric architectures supporting multicast delivery are likely to make up an important portion of the future Internet structure (e.g., DBS/cable/PSTN hybrids) and efficient, reliable bulk data transfer will be an important capability for servicing large groups of subscribed receivers. Adamson, Borman, et al. Expires May 2003 [Page 53] Internet Draft NORM Protocol November 2002 6.0 References (TBD) 7.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, Borman, et al. Expires May 2003 [Page 54]