RMT Working Group B. Adamson/Newlink INTERNET-DRAFT C. Bormann/Tellique draft-ietf-rmt-pi-norm-01.txt S. Floyd/ACIRI Expires: September 2001 M. Handley/ACIRI J. Macker/NRL March 2001 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 (1999). All Rights Reserved. Abstract This document describes the messages and procedures of the Nega- tive-acknowledgement (NACK) oriented reliable multicast (NORM). This revision of the document represents an initial outline of the protocol description. The document requires refinement in a number of areas to be considered complete. At this time, the document describes the high level details of the reliable multicast bulk transfer service model this protocol hopes to fulfill and the gen- eral message types and mechanisms which will be used to accomplish those goals. Adamson, Borman, et al. Expires September 2001 [Page 1] Internet Draft NORM Protocol March 2001 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 single source 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. 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 Adamson, Borman, et al. Expires September 2001 [Page 2] Internet Draft NORM Protocol March 2001 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. Single Source Multicast Routing, asymmetric topologies, etc). 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 Adamson, Borman, et al. Expires September 2001 [Page 3] Internet Draft NORM Protocol March 2001 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 units of content. The use of the NORM_OBJECT_STREAM type is at the application's discretion and conceivably be used to carry static data or file content also. Reliable stream service also opens up other possibilities such as reliable messaging or other unbounded, perhaps dynamically produced content. The NORM_OBJECT_STREAM pro- vides for reliable transport analogous to that of the Transmission Control Protocol (TCP) although NORM receivers will be able to begin receiving stream content at any point in time (The applica- bility of this feature will depend upon the application). The static data and file services are anticpated to be useful for mul- ticast-based cache applications with the ability to reliably pro- vide transmission/repair of a large set of static data. Other types of static data/file "casting" services might make use of these transport object types, too. The NORM protocol 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 con- trol of the receiver node's participation in the current transport activity. This allows the protocol to be flexible with minimal pre-coordination among senders and receivers. NORM does _not_ provide for global or application-level identifica- tion of data content within in its message headers (It should be noted that the NORM_INFO out-of-band data mechanism can be lever- aged by the application for this purpose if desired, or identifica- tion could alternatively be embedded within the data content). 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 Adamson, Borman, et al. Expires September 2001 [Page 4] Internet Draft NORM Protocol March 2001 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 independently so NormObjects are uniquely identified during transport by the con- catenation 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 ses- sions. The NORM protocol provides mechanisms so that the sender application may terminate transmission of data content and inform the group of this in an efficient manner. Other similar protocol control mechanisms (e.g. session termination, receiver synchroniza- tion, etc) are specified so that reliable multicast application variants may construct different, complete bulk transfer communica- tion 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 sepa- rate 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 investigation 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. However, the Adamson, Borman, et al. Expires September 2001 [Page 5] Internet Draft NORM Protocol March 2001 protocol also supports asymmetry where receiver participants may transmit back to sender participants via unicast routing instead of broadcasting to the session multicast address. Each participant (NormNode) within an NormSession is assumed to have an preselected unique XX-bit (TBD) identifier (NormNodeId). NormNodes MUST have uniquely assigned identifiers within a single NormSession to distinquish between possible multiple senders and to distinguish feedback information from different receivers. The protocol does not preclude multiple sender nodes actively transmit- ting 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). 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). 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 on 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 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 buld transfer, Adamson, Borman, et al. Expires September 2001 [Page 6] Internet Draft NORM Protocol March 2001 reliable 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. An 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 gen- erated in response to certain commands transmitted by the sender. In the general (and most scalable) protocol mode, receivers do not transmit any NORM_ACK messages. However, in order to meet poten- tial user requirements for positive data acknowledgement, and to collect more detailed information for potential multicast conges- tion control algorithms, NORM_ACK messages are defined and poten- tially used. NORM_ACK messages are also generated by a small sub- set of receivers when NORM 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 size which are encapsulated for transmission and are temporarily yet uniquely identified with the given sender's NormNodeId and a temporarily Adamson, Borman, et al. Expires September 2001 [Page 7] Internet Draft NORM Protocol March 2001 unique NormObjectTransportId. The third type of 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 congestion control is enabled, it may be desirable in some cases to establish minimum and maximum bounds for the rate adjustment depending upon the applica- tion. 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. 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: +---------+---------------+-----------------------------------+ | Field | Length (bits) | Purpose | +---------+---------------+-----------------------------------+ |type | (TBD) | NORM message type | +---------+---------------+-----------------------------------+ |version | (TBD) | NORM version number | +---------+---------------+-----------------------------------+ |node_id | (TBD) | Message originator's NormNodeId | +---------+---------------+-----------------------------------+ |sequence | (TBD) | Sequence number for loss tracking | +---------+---------------+-----------------------------------+ The message "type" field is a (TBD)-bit value indicating the NORM protocol message type. These types are defined as follows: Message Value NORM_INFO 1 NORM_DATA 2 NORM_CMD 3 Adamson, Borman, et al. Expires September 2001 [Page 8] Internet Draft NORM Protocol March 2001 NORM_NACK 4 NORM_ACK 5 NORM_REPORT 6 The "version" field is a (TBD)-bit value indicating the protocol version 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 "node_id" field is a (TBD)-bit value uniquely identifying the source of 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 can suffice, but alterna- tive methodologies for assignment of unique node identifiers within a multicast session need to be considered. For example, the "source identifier" mechanism defined in the RTPv2 specification [REF RTP] may be applicable to use for NORM node identifiers. At this point in time, the protocol makes no assumptions about how these unique identifiers are actually assigned. The "sequence" field is a (TBD)-bit value which is set by the mes- sage 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 quan- tity of packet loss within the expected delay-bandwidth product of NORM Message Types Sender Messages: 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 Adamson, Borman, et al. Expires September 2001 [Page 9] Internet Draft NORM Protocol March 2001 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. +---------------+---------------+----------------------------------+ | Field | Length (bits) | Purpose | +---------------+---------------+----------------------------------+ | segment_size | 16 | Source maximum segment payload | | | | (bytes) | +---------------+---------------+----------------------------------+ | fec_type | (TBD) | Source's FEC encoder description | +---------------+---------------+----------------------------------+ | grtt | 8 | Quantized current sender GRTT | | | | advertisement | +---------------+---------------+----------------------------------+ | object_id | 32 | NormObjectTransportId identifier | +---------------+---------------+----------------------------------+ | flags | 8 | Object transmission flags | +---------------+---------------+----------------------------------+ | object_size | (TBD) | Size of object (in bytes) | +---------------+---------------+----------------------------------+ | segment_id | (TBD) | Segment identifier } | | | | offset* (TBD) T{ Data con- | | | | tent's "offset" within object | +---------------+---------------+----------------------------------+ | length* | 16 | Length of data content (bytes) | +---------------+---------------+----------------------------------+ | data* | -- | Data or parity content (up to | | | | "segment_size" bytes) | +---------------+---------------+----------------------------------+ * Note the "offset" and "length" fields for NORM_DATA messages con- taining parity information are actually values computed from FEC encoding of the "offset" and "length" fields of the data segments of the applicable coding block. 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 "grtt" field contains a non-linear quantized representation of the sender's current estimate of group round-trip time (GRTT). Adamson, Borman, et al. Expires September 2001 [Page 10] Internet Draft NORM Protocol March 2001 This value is used to control timing of the NACK repair process and other aspects of protocol operation as described in this document. The "object_id" field is a monotonically and incrementally increas- ing value assigned by a sender to the object being transmitted. Transmissions and repair requests related to that object use the same "object_id" value. For sessions of very long or indefinite duration, the "object_id" field may be repeated, but it is presumed that the 32-bit field size provides 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 identifiers 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_id". Note that NORM_INFO messages associated with the identified object carry the same "object_id" value. 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: +---------------------+-------+------------------------------------------+ | Flag | Value | Purpose | +---------------------+-------+------------------------------------------+ |NORM_FLAG_REPAIR | 0x01 | Indicates message is a repair transmis- | | | | sion | +---------------------+-------+------------------------------------------+ |NORM_FLAG_INFO | 0x02 | Indicates availability of NORM_INFO for | | | | object, | +---------------------+-------+------------------------------------------+ |NORM_FLAG_UNRELIABLE | 0x04 | Indicates that repair transmissions for | | | | the specified object will be unavail- | | | | able. (One-shot, best effort transmis- | | | | sion) | +---------------------+-------+------------------------------------------+ |NORM_FLAG_FILE | 0x08 | Indicates object is "file-based" data | | | | (hint to use disk storage for reception) | +---------------------+-------+------------------------------------------+ |NORM_FLAG_STREAM | 0x10 | 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 Adamson, Borman, et al. Expires September 2001 [Page 11] Internet Draft NORM Protocol March 2001 process 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 retransmis- sion of NORM_INFO only when it is available. The NORM_FLAG_UNRELI- ABLE flag is set when the sender wishes to transmit and object with "best effort" delivery only and will not supply repair transmis- sions 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 identified 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 "object_size" field indicates the total size of the object. This information is used by receivers to determine storage require- ments 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 "segment_id" field identifies the position of the NORM_DATA message within the transmission sequence. This identification includes the applicable FEC coding block indentifier and the posi- tion of this particular segment within the coding block. The for- mat of the "segment_id" is dependent upon the FEC coding type used. The "segment_id" may also need to contain information on the cur- rent FEC code block length if a coding technique using variable block lengths is employed. For systematic FEC coding, the position of the segment within the coding block can be used to determine if the content portion of the NORM_DATA message is original data con- tent or parity information. The "offset" and "length" fields are used to identify the position and quantity of data content of the segment. For senders employing systematic FEC encoding, these fields will correspond to the actual values for NORM_DATA messages which contain original data content. For NORM_DATA messages containing calculated 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 corre- sponding FEC coding block. This allows the "offset" and "length" values of missing data content to be determined when decoding an FEC coding block. The "data" field contains original data or computed parity content for the identified segment. The maximum length of this field cor- responds 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 Adamson, Borman, et al. Expires September 2001 [Page 12] Internet Draft NORM Protocol March 2001 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 content and deliver it to the application. 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 transmission pro- cess. +---------------+---------------+----------------------------------+ | Field | Length (bits) | Purpose | +---------------+---------------+----------------------------------+ | segment_size | 16 | Source maximum segment payload | | | | (bytes) | +---------------+---------------+----------------------------------+ | fec_type | (TBD) | Source's FEC encoder description | +---------------+---------------+----------------------------------+ | grtt | 8 | Quantized current sender GRTT | | | | advertisement | +---------------+---------------+----------------------------------+ | object_id | 32 | NormObjectTransportId identifier | +---------------+---------------+----------------------------------+ | flags | 8 | Object transmission flags | +---------------+---------------+----------------------------------+ | object_size | (TBD) | Size of object (in bytes) | +---------------+---------------+----------------------------------+ | data | -- | Application defined info content | | | | (up to "segment_size" bytes) | +---------------+---------------+----------------------------------+ The "segment_size", "fec_type", "grtt", "object_id", "flags", and "object_size" fields carry the same information and serve the same purpose as with NORM_DATA messages. The "data" field contains the Adamson, Borman, et al. Expires September 2001 [Page 13] Internet Draft NORM Protocol March 2001 application-defined content which can be used by the receiver application for various purposes. 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: +---------------+---------------+----------------------------------+ | Field | Length (bits) | Purpose | +---------------+---------------+----------------------------------+ | segment_size | 16 | Source maximum segment payload | | | | (bytes) | +---------------+---------------+----------------------------------+ | fec_type | (TBD) | Source's FEC encoder description | +---------------+---------------+----------------------------------+ | grtt | 8 | Quantized current sender GRTT | | | | advertisement | +---------------+---------------+----------------------------------+ | flavor | 8 | NORM_CMD type | +---------------+---------------+----------------------------------+ The "segment_size", "fec_type", and "grtt" 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 com- mand to follow. The command types include: Adamson, Borman, et al. Expires September 2001 [Page 14] Internet Draft NORM Protocol March 2001 +------------------+--------------+----------------------------------+ | 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 of a watermark point from a | | | | specific list of receivers. | +------------------+--------------+----------------------------------+ |NORM_CMD_GRTT_REQ | 4 | Probe used in collection of | | | | sender's group GRTT estimate and | | | | possibly congestion control | | | | feedback. | +------------------+--------------+----------------------------------+ NORM_CMD_FLUSH The NORM_CMD_FLUSH command is sent when the sender reaches the end of the data content and any pending repairs it has queued for transmission. This command is repeated once per 2*GRTT to excite the receiver set for any outstanding repair requests. 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 server 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. The format of the NORM_CMD_FLUSH message (in addition to the NORM message common header and the NORM_CMD common header) is: Adamson, Borman, et al. Expires September 2001 [Page 15] Internet Draft NORM Protocol March 2001 +-------------+---------------+----------------------------------+ | Field | Length (bits) | Purpose | +-------------+---------------+----------------------------------+ | object_id | 32 | NormObjectTransportId of most | | | | current NormObject for which the | | | | sender has transmitted (or is | | | | transmitting) | +-------------+---------------+----------------------------------+ | segment_id | (TBD) | Segment identifier of most cur- | | | | rent NORM_DATA message sent for | | | | the identified object (same as | | | | NORM_DATA segment_id) | +-------------+---------------+----------------------------------+ The "object_id" field identifies the sender's most current Norm- TransportId and the "segment_id" identifies the most current por- tion of that object which has been transmitted. Receivers are expected to check their completion state and initiate the NACK repair process if they have outstanding repair needs up to this transmission point. If the receivers have no outstanding 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. 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 forward 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 infre- quently, 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 an encoded list of NormTransportId which are valid. The starting point of the included list begins at the greatest (latest) of the sender's earliest 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 NormSeg- mentSize. This allows the receivers to learn the status of the Adamson, Borman, et al. Expires September 2001 [Page 16] Internet Draft NORM Protocol March 2001 sender's applicable object repair window with minimal transmission of NORM_CMD_SQUELCH commands. The format of the NORM_CMD_SQUELCH message (in addition to the NORM message common header and the NORM_CMD common header) is: +-------------+---------------+----------------------------------+ | Field | Length (bits) | Purpose | +-------------+---------------+----------------------------------+ | object_id | 32 | NormObjectTransportId of lowest | | | | NormObject for which the sender | | | | supports repair. | +-------------+---------------+----------------------------------+ | segment_id | (TBD) | Segment identifier of most low- | | | | est point within the identified | | | | object for which repair is sup- | | | | ported. | +-------------+---------------+----------------------------------+ | list_id | 32 | NormObjectTransportId indexing | | | | start of included validation | | | | list | +-------------+---------------+----------------------------------+ | data | -- | Bitmask encoded list of valid | | | | NormObjectTransportIds. "True" | | | | (one) values mark valid objects. | | | | "False" (zero) mark invalidated | | | | objects in list. | +-------------+---------------+----------------------------------+ The "object_id" identifies the earliest ordinal NormTransportId for which it is supporting repair and the "segment_id" delineates te earliest repair point in that object. The "list_id" provides the starting index for the attached bitmask indicating valid and invalid objects. The length of the bitmask can be determined from the payload length of the datagram carrying this message. The sta- tus of objects lying between the "object_id" value and the "list_id" values are _not_ advertised by this message. In most cases, it is expected that the "object_id" and "list_id" will be equal, but this mechanism allows the receivers to efficiently learn the sender's repair window when the NormSegmentSize limits complete repair window status to be advertised in a single message. Receivers are expected to ignore values in the bitmask which are ordinally later than the most recent NormTransportId for which they are maintaining state for the sender in question. NORM_CMD_ACK_REQ The NORM_CMD_ACK_REQ message is used by the sender to request Adamson, Borman, et al. Expires September 2001 [Page 17] Internet Draft NORM Protocol March 2001 acknowledgement from a specified list of receivers. This message serves in a lightweight positive acknowledgement mechanism which can be optionally employed by the reliable multicast application to deterministically determine that watermark points in the reliable transmission have been achieved by specific receivers. er's appli- cable object repair window with minimal transmission of NORM_CMD_SQUELCH commands. The format of the NORM_CMD_ACK_REQ mes- sage (in addition to the NORM message common header and the NORM_CMD common header) is: +-------------+---------------+----------------------------------+ | Field | Length (bits) | Purpose | +-------------+---------------+----------------------------------+ | object_id | 32 | NormObjectTransportId of water- | | | | mark NormObject for which the | | | | sender supports acknowledgement. | +-------------+---------------+----------------------------------+ | segment_id | (TBD) | Segment identifier of watermark | | | | point within the identified | | | | object. | +-------------+---------------+----------------------------------+ | data | -- | List of NormNodeIds to which the | | | | request applies. | +-------------+---------------+----------------------------------+ The "object_id" and "segment_id" are used to identify the watermark point for which the positive acknowledgement request applies. The "data" field contains the current list receivers which should reply to this request. Replying receivers will 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), 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. 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 dynami- cally updated as this process progresses and ACKs are received from the specified receiver set. The process SHALL terminate when all Adamson, Borman, et al. Expires September 2001 [Page 18] Internet Draft NORM Protocol March 2001 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 transmis- sions up to the specified watermark point. NORM_CMD_RTT_REQ The NORM_CMD_RTT_REQ is periodically transmitted by the sender to provide a reference point (a timestamp) so that receivers can cal- culate appropriate response content in NORM_NACK and NORM_NACK mes- sages 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. Generally, 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 gener- ation [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. There is expected to be sufficient content in this message that it merits a separate message rather than be periodically 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_RTT_REQ message (in addition to the NORM mes- sage common header and the NORM_CMD common header) is: +----------+---------------+----------------------------------+ | Field | Length (bits) | Purpose | +----------+---------------+----------------------------------+ | req_seq | 8 | NORM_CMD_RTT_REQ sequence number | | | | T} send_time 64 T{ Timestamp | | | | referenced to sender clock for | | | | when the command was generated. | +----------+---------------+----------------------------------+ The "req_seq" field is an 8-bit, monotonically increasing sequence number which is incremented with each NORM_CMD_RTT_REQ command gen- erated by the sender. Responses to the NORM_CMD_RTT_REQ embedded in receiver NORM_NACK and NORM_ACK messages will identify the sequence number of the NORM_CMD_RTT_REQ which they have most Adamson, Borman, et al. Expires September 2001 [Page 19] Internet Draft NORM Protocol March 2001 recently received. The "send_time" field is a precision timestamp indicating the time that the NORM_CMD_GRTT_REQ message was transmitted. This consists of a 64-bit field containing 32-bits with the time in seconds and 32-bits with the time in microseconds since some reference time the source maintains (usually 00:00:00, 1 January 1970). The ordering of the fields in Big Endian network order. Other candidate fields for this message include: "flags" to mark different forms/purposes of the request. (e.g. a WILDCARD flag to prompt an explicit response from the entire group) "hold_time" field to provide a random back-off scaling factor when an entire group response is expected. Congestion control parameters such as "tx_rate", "rtt", "loss", etc for assisting a congestion control mechanism appropiate for NORM. Techniques are under investigation. Receiver Messages: 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 addi- tional 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 a list of "ObjectNACKs" for different objects and portions of a those objects. In addition to the common message header the NORM_NACK messages contain the following fields: Adamson, Borman, et al. Expires September 2001 [Page 20] Internet Draft NORM Protocol March 2001 +--------------------+---------------+----------------------------------+ | Field | Length (bits) | Purpose | +--------------------+---------------+----------------------------------+ | server_id | 32 | NormNodeId of source for which | | | | NACK is intended | +--------------------+---------------+----------------------------------+ | grtt_response | 64 | Response to source's | | | | NORM_CMD_GRTT_REQ, if any (zero | | | | value if none) | +--------------------+---------------+----------------------------------+ | loss_estimate | 16 | Current packet loss estimate for | | | | the indicated source. | +--------------------+---------------+----------------------------------+ | grtt_req_sequence | 8 | Sequence number identifier of | | | | applicable NORM_CMD_GRTT_REQ | +--------------------+---------------+----------------------------------+ | data | -- | ObjectNACK list | +--------------------+---------------+----------------------------------+ 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" field contains 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_GRTT_REQ. However, note that the "grtt_response" timestamp is _relative_ to the "send_time" the source provided with the corresponding NORM_CMD_GRTT_REQ command. The receiver adjusts the source's NORM_CMD_GRTT_REQ "send_time" timestamp by the time differential from when the receiver received the NORM_CMD_GRTT_REQ to when the NORM_NACK was transmitted to calculate the value in the "grtt_response" field. The following formula applies: "grtt_response" = request "send_time" + request_to_response_differential If the "grtt_response" has ZERO value, that is an indication that the receiver has not yet received a NORM_CMD_GRTT_REQ command from the source and the source should ignore this portion of the response. The "loss_estimate" 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 per- cent packet loss. The 16-bit "loss_estimate" value is calculated by the following formula: Adamson, Borman, et al. Expires September 2001 [Page 21] Internet Draft NORM Protocol March 2001 "loss_estimate" = decimal_loss_fraction * 65535.0 The "grtt_req_sequence" field contains the sequence number identi- fier of the received NORM_CMD_GRTT_REQ to which the response infor- mation in this NORM_NACK applies. The "data" field of the NORM_NACK contains the list of ObjectNACKs for different source NormObjects. Note that ObjectNACKs for multi- ple objects may be contained in one NORM_NACK message and that each ObjectNACK consists of a hierarchical set of indicators and bit masks depending upon what data the receiver has detected is miss- ing. Each ObjectNACK in the list contained in the NORM_NACK "data" field is made up of the following fields: +------------+---------------+----------------------------------+ | Field | Length (bits) | Purpose | +------------+---------------+----------------------------------+ | object_id | 32 | NormTransportId of object for | | | | enclosed RepairRequests | +------------+---------------+----------------------------------+ | nack_len | 16 | Total length (in bytes) of | | | | RepairRequests for indicated | | | | object. | +------------+---------------+----------------------------------+ | data | -- | RepairRequest list | +------------+---------------+----------------------------------+ The content in the data field of an ObjectNACK consists of a list of individual "RepairRequests" for the indicated NormObject. There are multiple types of RepairRequests which each begin with an 8-bit type field of one of the following values: Adamson, Borman, et al. Expires September 2001 [Page 22] Internet Draft NORM Protocol March 2001 +------------------+------+----------------------------------+ | RepairRequest | Type | Purpose | +------------------+------+----------------------------------+ | | | | +------------------+------+----------------------------------+ | REPAIR_SEGMENTS | 1 | Indicates receiver is missing | | | | portions of an encoding block. | +------------------+------+----------------------------------+ | REPAIR_BLOCKS | 2 | Indicates receiver is missing | | | | some blocks in entirety. | +------------------+------+----------------------------------+ | REPAIR_INFO | 3 | Indicates receiver requires | | | | retransmission of NORM_INFO for | | | | object. | +------------------+------+----------------------------------+ | REPAIR_OBJECT | 4 | Indicates receiver requires | | | | retransmission of entire object | +------------------+------+----------------------------------+ A REPAIR_SEGMENTS RepairRequest identifies the beginning the coding block (by its offset) and then provides a bit mask indicating which segments within that block require retransmission. A count of the total number of missing segments (erasures) is also provided. So, the following fields comprise a REPAIR_SEGMENTS RepairRequest: +-----------+---------------+-----------------------------------------+ | Field | Length (bits) | Purpose | +-----------+---------------+-----------------------------------------+ | type | 8 | value = 1 (REPAIR_SEGMENTS) | +-----------+---------------+-----------------------------------------+ | nerasure | (TBD) | Count of missing segments in the block. | +-----------+---------------+-----------------------------------------+ | block_id | 32 | Identifier of applicable coding block. | +-----------+---------------+-----------------------------------------+ | mask_len | 16 | Length of attached bit mask (in bytes) | +-----------+---------------+-----------------------------------------+ | mask | -- | Bit mask content | +-----------+---------------+-----------------------------------------+ The REPAIR_BLOCKS RepairRequest identifies the beginning of a set of FEC coding blocks (by the initial offset) and then provides a bit mask indicating which coding blocks require retransmission in entirety. The following fields make up a REPAIR_BLOCKS RepairRe- quest: Adamson, Borman, et al. Expires September 2001 [Page 23] Internet Draft NORM Protocol March 2001 +-----------+---------------+----------------------------------------+ | Field | Length (bits) | Purpose | +-----------+---------------+----------------------------------------+ | type | 8 | value = 2 (REPAIR_BLOCKS) | +-----------+---------------+----------------------------------------+ | block_id | 32 | Identifier of initial FEC coding block | +-----------+---------------+----------------------------------------+ | mask_len | 16 | Length of attached bit mask (in bytes) | +-----------+---------------+----------------------------------------+ | mask | -- | Bit mask content | +-----------+---------------+----------------------------------------+ The REPAIR_INFO RepairRequest implicitly identifies by its type that the receiver requires retransmission of the NORM_INFO associ- ated with an object and thus consists of a single byte: +-------+---------------+----------------------------------+ |Field | Length (bits) | Purpose | +-------+---------------+----------------------------------+ | type | 8 | value = 3 (REPAIR_INFO) | +-------+---------------+----------------------------------+ The REPAIR_OBJECT RepairRequest is also very simple and also con- sists of a single byte to request retransmission of an entire NORM transport object: +-------+---------------+----------------------------------+ |Field | Length (bits) | Purpose | +-------+---------------+----------------------------------+ | type | 8 | value = 4 (REPAIR_OBJECT) | +-------+---------------+----------------------------------+ 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. (TBD) Detailed description. General Messages: Adamson, Borman, et al. Expires September 2001 [Page 24] Internet Draft NORM Protocol March 2001 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. 3.0 Detailed Protocol Operation (TBD) This section describes the detailed interactions of senders and receivers participating in a NORM session. Candidate subsec- tions: 3.1 Sender Initialization and Transmission (TBD) Describes how a sender becomes active within the group, transmits data content and how it may potentially go inactive or leave the group. 3.2 Receiver Initialization and Reception (TBD) Describes how a receiver joins the group, begins receiving data content and any requirements on dynamically leaving and poten- tially rejoining the group. 3.3 Receiver NACK Process (TBD) Describes receiver criteria by which/when it chooses to transmit NACK-based repair requests and the content of the these messages. 3.3.1 NACK initiation 3.3.2 NACK content 3.4 Sender NACK Processing and Repair Transmission (TBD) Describes how the sender accumulates NACK repair requests and transmits repair information in response to these requests. 3.5 Additional Protocol Mechanisms (TBD) Describes any other protocol mechanisms running periperally or embedded as part of other protocol messaging. Adamson, Borman, et al. Expires September 2001 [Page 25] Internet Draft NORM Protocol March 2001 3.5.1 Round-trip time collection 3.5.2 Congestion control operation 3.5.3 Other (e.g. optional scalable, positive acknowledgements, asymmet- ric feedback, performance reporting, etc) 4.0 Security Considerations (TBD) 5.0 Suggested Use (TBD) 6.0 References (TBD) 7.0 Authors' Addresses Brian Adamson adamson@itd.nrl.navy.mil Newlink Global Engineering Corporation 8580 Cinder Bed Road, Suite 1000 Newington, VA, USA, 22122 Carsten Bormann cabo@tellique.de Tellique Kommunikationstechnik GmbH Gustav-Meyer-Allee 25 Geb ude 12 D-13355 Berlin, Germany Sally Floyd floyd@aciri.org 1947 Center Street, Suite 600 Berkeley, CA 94704 Mark Handley mjh@aciri.org 1947 Center Street, Suite 600 Berkeley, CA 94704 Joe Macker Adamson, Borman, et al. Expires September 2001 [Page 26] Internet Draft NORM Protocol March 2001 macker@itd.nrl.navy.mil Naval Research Laboratory Washington, DC, USA, 20375 Adamson, Borman, et al. Expires September 2001 [Page 27]