RFC 3941

Negative-Acknowledgment (NACK)-Oriented Reliable Multicast (NORM) Building Blocks

📅 published November 2004, from ietf

Title Block 💖

Okay bestie, this is RFC 3941 🦋 Its title is Negative-Acknowledgment (NACK)-Oriented Reliable Multicast (NORM) Building Blocks. It was written by four people: B. Adamson (NRL), C. Bormann (Universitaet Bremen TZI), M. Handley (UCL), and J. Macker (NRL). It's published under the Network Working Group, it's in the Experimental category, and the date is November 2004. The header doesn't have an Obsoletes or Updates line, so it doesn't list anything it obsoletes or updates. ✨

Status of This Memo 📜

This memo defines an Experimental Protocol for the Internet community, so it's not an Internet standard of any kind. The authors want feedback and suggestions for making it better, and distribution of the memo is unlimited. 🌈

Copyright (C) The Internet Society (2004). 💅

Abstract 🔥

This doc is about creating NACK-oriented reliable multicast (NORM) protocols, aka the big brain stuff for reliable group data delivery 🧠 It explains why NORM has the goals and assumptions it has, and it calls out the technical challenges for NACK-based reliable multicast (and sometimes reliable multicast in general). Then it breaks all of that down into a set of functional "building blocks" that each handle a different part of how NORM works. The authors expect these building blocks to be useful for making different versions of reliable multicast protocols. 🎀

Table of Contents 🗂️

1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . .   3
   2. Rationale. . . . . . . . . . . . . . . . . . . . . . . . . .   4
      2.1. Delivery Service Model  . . . . . . . . . . . . . . . . .   4
      2.2. Group Membership Dynamics . . . . . . . . . . . . . . . .   5
      2.3. Sender/Receiver Relationships . . . . . . . . . . . . . .   5
      2.4. Group Size Scalability. . . . . . . . . . . . . . . . . .   6
      2.5. Data Delivery Performance . . . . . . . . . . . . . . . .   6
      2.6. Network Environments. . . . . . . . . . . . . . . . . . .   6
      2.7. Router/Intermediate System Assistance . . . . . . . . . .   7
   3. Functionality. . . . . . . . . . . . . . . . . . . . . . . . .   7
      3.1. NORM Sender Transmission. . . . . . . . . . . . . . . . .  10
      3.2. NORM Repair Process . . . . . . . . . . . . . . . . . . .  11
           3.2.1. Receiver NACK Process Initiation . . . . . . . . .  11
           3.2.2. NACK Suppression . . . . . . . . . . . . . . . . .  13
           3.2.3. NACK Content . . . . . . . . . . . . . . . . . . .  17
                  3.2.3.1. NACK and FEC Repair Strategies. . . . . .  17
                  3.2.3.2. NACK Content Format . . . . . . . . . . .  20
           3.2.4. Sender Repair Response . . . . . . . . . . . . . .  21
      3.3. NORM Receiver Join Policies and Procedures. . . . . . . .  23
      3.4. Reliable Multicast Member Identification. . . . . . . . .  24
      3.5. Data Content Identification . . . . . . . . . . . . . . .  24
      3.6. Forward Error Correction (FEC). . . . . . . . . . . . . .  26
      3.7. Round-trip Timing Collection. . . . . . . . . . . . . . .  27
           3.7.1. One-to-Many Sender GRTT Measurement. . . . . . . .  27
           3.7.2. One-to-Many Receiver RTT Measurement . . . . . . .  29
           3.7.3. Many-to-Many RTT Measurement . . . . . . . . . . .  29
           3.7.4. Sender GRTT Advertisement. . . . . . . . . . . . .  30
      3.8. Group Size Determination/Estimation . . . . . . . . . . .  31
      3.9. Congestion Control Operation. . . . . . . . . . . . . . .  31
      3.10 Router/Intermediate System Assistance . . . . . . . . . .  31
      3.11 NORM Applicability. . . . . . . . . . . . . . . . . . . .  31
   4. Security Considerations. . . . . . . . . . . . . . . . . . . .  32
   5. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . .  33
   6. References . . . . . . . . . . . . . . . . . . . . . . . . . .  33
      6.1. Normative References. . . . . . . . . . . . . . . . . . .  33
      6.2. Informative References. . . . . . . . . . . . . . . . . .  33
   7. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . .  35
      Full Copyright Statement . . . . . . . . . . . . . . . . . . .  36

1. Introduction ✨

Okay so reliable multicast transport is the move for sending data to a whole group on the Internet, efficiently and reliably 🫶 Group communication has a lot of moving parts, so different protocol types and versions are needed to hit the performance and scalability goals of different reliable multicast apps and users [3]. This document is about creating NACK-oriented reliable multicast (NORM) protocols. Different protocol versions might be needed for specific app and network architecture demands [4], but there are some core pieces that can be shared across all of them 💜 This doc lays out the framework and the common "building block" pieces for multicast protocols that mostly rely on NACKs for reliable transport. It covers a big set of reliable multicast pieces and NORM design issues, but it digs deep into these three building blocks, which aren't covered in other IETF docs:

  1. NORM sender transmission strategies,
  2. NACK-oriented repair process with timer-based feedback suppression, and
  3. Round-trip timing for adapting NORM timers.

It also talks about how NORM could relate to the other reliable multicast building blocks (Forward Error Correction (FEC) and congestion control), plus general NORM protocol issues. This document is a product of the IETF RMT WG and follows the guidelines in RFC 3269 [5]. The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14, RFC 2119 [1]. 🎀

Statement of Intent 🦋

This memo has part of the definitions you need to fully specify a Reliable Multicast Transport protocol, following RFC 2357 🌸 And per RFC 2357, using any reliable multicast protocol on the Internet requires an adequate congestion control scheme. Literally a must.

While they wait for that scheme to be available, or for an existing one to be proven adequate, the Reliable Multicast Transport working group (RMT) is publishing this Request for Comments in the "Experimental" category. 🧪

The RMT plans to resubmit this spec as an IETF Proposed Standard as soon as that condition is met. 👑

2. Rationale 🌸

Each protocol version that uses these building blocks (and the other applicable building block docs) will have its own criteria that shape its design. To help develop the building blocks, it's useful to identify and sum up the big-picture design goals and assumptions 💅 These are the areas each protocol version has to handle in detail. Each building block description in this doc will talk about how these design criteria affect it. The design criteria categories covered here are:

  1. Delivery Service Model,
  2. Group Membership Dynamics,
  3. Sender/receiver relationships,
  4. Group Size Scalability,
  5. Data Delivery Performance,
  6. Network Environments, and
  7. Router/Intermediate System Interactions.

Every one of these areas gets at least a quick discussion. Other reliable multicast transport building block docs, like [9], cover areas outside this doc's scope, so NORM protocol versions might rely on those too, along with the ones here. This doc focuses on the stuff that's unique to NORM, but it can be used alongside the other building block areas. Sometimes one building block can handle a wide range of assumptions, and other times there are trade-offs to meet different app needs or operating environments. When needed, building block features are made parametric so they can meet different requirements 🧚 Of course the big goal is to keep design complexity low and to at least recommend default values for those parameters that meet a general-purpose "bulk data transfer" need in a typical Internet environment. 🍓

2.1. Delivery Service Model 🦋

The implicit goal of a reliable multicast transport protocol is reliable delivery of data among a group of members communicating over IP multicast datagram service 💖 But the specific service the app is trying to provide can change design decisions. The most basic service model for reliable multicast transport is "bulk transfer," which is the main focus of this doc and other related RMT working group docs. The same protocol design principles can also apply to other service models, like more interactive exchanges of small messages (think white-boarding or text chat) 💬 Within these models there are issues like whether the sender can cache transmitted data (or state that references it) for retransmission or repair. The need for ordering and/or causality in the sequence of transmissions and receptions among group members can differ depending on the data content. Group communication is really different from point-to-point in this way: depending on the data content type, some receivers might finish receiving part of the content and be able to act on it before other members have it. That might be totally fine (or even desirable) for some apps, but not for others 🙈 These different needs are why there are so many different protocol designs. The hard part is building generally useful block mechanisms that handle even a limited range of these capabilities without defining app-level details. 🔥

2.2. Group Membership Dynamics 💜

Here's a way group communication differs from point-to-point: even when the group's membership changes, the "thread" of communication can keep going 🧵 Compare that to point-to-point, where if either party leaves, the communication (the data exchange) ends (or at least pauses). Depending on app goals, senders and receivers in a reliable multicast transport "session" might be able to join late, leave, and/or potentially rejoin while the ongoing group "thread" stays functional and useful ✨ This also affects protocol message content. If "late joiners" are supported, some extra info might need to go in message headers to make that work 🌈 Or that info can be sent in its own message (on demand or now and then) if adding it to every message would add too much overhead 😭 Group dynamics can also affect other protocol mechanisms, like NACK timing and congestion control operation, and so on. 🦋

2.3. Sender/Receiver Relationships 💌

okay so the relationship between senders and receivers in a group is a whole thing and it needs real thought 🧠. In some apps there's just one sender blasting data out to a group of receivers, super simple 📣. But in other cases there could be more than one sender, or even the potential for everyone in the group to be a sender _and_ a receiver at the same time 🌈. Main character group energy 👑.

2.4. Group Size Scalability 📈

Native IP multicast [2] may scale to extremely large group sizes 🦋. It might be desirable for some apps to scale right alongside the multicast infrastructure's ability to scale 💅. In its simplest form, there are limits to the group size a NACK-oriented protocol can handle before you get NACK implosion problems 😭. Research suggests that NORM group sizes on the order of tens of thousands of receivers may operate with modest feedback to the sender, using probabilistic, timer-based suppression techniques [7] 🫶. However, router assistance and/or other NACK suppression heuristics may enable these protocols to scale to very large group sizes ✨. In large scale cases, it may be prohibitive for members to maintain state on all other members (in particular, other receivers) in the group 🙈. The impact of group size needs to be considered when developing the applicable building blocks 🧚.

2.5. Data Delivery Performance ⏱️

There's a trade-off between scalability and data delivery latency when you design NACK-oriented protocols, and it's giving "pick your poison" 💀. If probabilistic, timer-based NACK suppression is used, there will be some delays built into the NACK process 🐢. Those delays let suppression happen and give the sender time to figure out the right content for an efficient repair transmission 🔧. For example, backoff timeouts can ensure efficient NACK suppression and repair transmission, but the cost is increased delivery latency and increased buffering requirements for both senders and receivers 😤. The building blocks SHOULD allow applications to establish bounds for data delivery performance 🎀. Note that application designers must be aware of the scalability trade-off that gets made when such bounds are applied ⚠️.

2.6. Network Environments 🌍

The Internet Protocol has historically been the one providing service across heterogeneous network topologies, and it's honestly iconic 👑. It's desirable that a reliable multicast protocol can effectively operate across a wide range of the networks that general purpose IP service applies to 💖. The bandwidth on links between members of a single group can vary from low numbers of kbit/s for wireless links all the way up to multiple Gbit/s for high speed LAN connections, with varying amounts of contention from other flows 🏎️. Recently, a bunch of asymmetric network services have started to proliferate, like 56K/ADSL modems, CATV Internet service, satellite, and other wireless communication services 📡. Many of these are inherently broadcast media with potentially large "fan-out," which is exactly where IP multicast service is highly applicable 🦋. Also, policy and/or technical issues may result in topologies where multicast connectivity is limited to a single source multicast (SSM) model from a specific source [8] 🔒. Receivers in the group may be restricted to unicast feedback for NACKs and other messages 📬. When building block development and protocol design happen, you MUST consider the nature of the underlying networks 🫶.

2.7. Router/Intermediate System Assistance 🤖

While intermediate assistance from devices or systems with direct knowledge of the underlying network topology may be used to level up the performance and scalability of reliable multicast protocols 🚀, there will keep being a bunch of situations where this isn't available or practical 😅. Any building block components for NACK-oriented reliable multicast SHALL be capable of operating without such assistance 💯. However, it is RECOMMENDED that such protocols also consider using these features when they're available 💜.

  1. Functionality 🎀

The previous section presented the role of protocol building blocks and some of the criteria that may affect NORM building block identification and design 🧩. This section describes different building block areas that apply to NORM protocols 🍓. Some of these areas are specific to NACK-oriented protocols, and detailed descriptions of those are provided 🔍. In other cases, the areas (e.g., node identifiers, forward error correction (FEC), etc.) may apply to other forms of reliable multicast 🌸. In those cases, the discussion below describes requirements placed on those other general building block areas from the standpoint of NACK-oriented reliable multicast 🧚. Where it applies, other building block documents are referenced for possible contribution to NORM protocols 📚.

For each building block, a notional "interface description" is provided to show any dependencies one building block component has on another, or on other protocol parameters 🔗. A building block component may need some form of "input" from another building block component or other source to do its job 💌. Any "inputs" a building block component needs, and any resulting "output" it provides, will be defined and described in that component's interface description 📝. Heads up: the set of building blocks presented here do not fully satisfy each other's "input" and "output" needs ⚠️. In some cases, "inputs" for these building blocks must come from other building blocks outside this document (e.g., congestion control or FEC) 🌐. In other cases, NORM building block "inputs" must be satisfied by the specific protocol instantiation or implementation (e.g., application data and control) 🎯.

The following building block components relevant to NORM are identified 👇:

(NORM-Specific)
     1)   NORM Sender Transmission
     2)   NORM Repair Process
     3)   NORM Receiver Join Policies
(General Purpose)
     4)   Node (member) Identification
     5)   Data Content Identification
     6)   Forward Error Correction (FEC)
     7)   Round-trip Timing Collection
     8)   Group Size Determination/Estimation
     9)   Congestion Control Operation
    10)   Router/Intermediate System Assistance
    11)   Ancillary Protocol Mechanisms

Figure 1 gives a pictorial overview of these building block areas and some of their relationships 🖼️. For example, the content of the data messages a sender initially transmits depends on the "Node Identification", "Data Content Identification", and "FEC" components, while the rate of message transmission will generally depend on the "Congestion Control" component 🚦. After that, the receivers' responses to these transmissions (e.g., NACKing for repair) will depend on the data message content and inputs from other building block components 📨. Finally, the sender's processing of receiver responses feeds back into its transmission strategy 🔁.

                                 Application Data and Control
                                             |
                                             v
.---------------------.            .-----------------------.
| Node Identification |----------->|  Sender Transmission  |<------.
`---------------------'       _.-' `-----------------------'       |
.---------------------.   _.-' .'            | .--------------.    |
| Data Identification |--'   .''             | |  Join Policy |    |
`---------------------'    .' '              v `--------------'    |
.---------------------.  .'  '     .------------------------.      |
.->| Congestion Control  |-'   '      | Receiver NACK          |      |
|  `---------------------'   .'       | Repair Process         |      |
|  .---------------------. .'         | .------------------.   |      |
|  |        FEC          |'.          | | NACK Initiation  |   |      |
|  `---------------------'` `._       | `------------------'   |      |
|  .---------------------. ``. `-._   | .------------------.   |      |
`--|    RTT Collection   |._` `    `->| | NACK Content     |   |      |
   `---------------------' .`- `      | `------------------'   |      |
.---------------------.  \ `-`._   | .------------------.   |      |
|    Group Size Est.  |---.-`---`->| | NACK Suppression |   |      |
`---------------------'`.  ` `     | `------------------'   |      |
.---------------------.  `  ` `    `------------------------'      |
|       Other         |   `  ` `             | .-----------------. |
`---------------------'    `  ` `            | |Router Assistance| |
                            `. ` `           v `-----------------' |
                              `.`' .-------------------------.     |
                                 `>| Sender NACK Processing  |_____/
                                   | and Repair Response     |
                                   `-------------------------'

                ^                         ^
                |                         |
              .-----------------------------.
              |         (Security)          |
              `-----------------------------'

            Fig. 1 - NORM Building Block Framework

The components on the left side of this figure are areas that may apply beyond NORM 🌎. The most significant of these are discussed in other building block documents, such as [9] 📖. A brief description of these areas and their role in the NORM protocol is given below 👀. The components on the right are seen as specific to NORM protocols, most notably the NACK repair process 🛠️. These areas are discussed in detail below 💕. Some other components (e.g., "Security") impact many aspects of the protocol, and others such as "Router Assistance" may be more transparent to the core protocol processing 🕵️. The sections below describe the "NORM Sender Transmission", "NORM Repair Process", and "RTT Collection" building blocks in detail 🎉. The relationships to and among the other building block areas are also discussed, focusing on issues that matter for NORM protocol design 🧠. Where it applies, specific technical recommendations are made for mechanisms that will properly satisfy the goals of NORM transport for the Internet ✨🫶

3.1. NORM Sender Transmission ✨

okay so NORM senders are the ones actually pushing data content out to the multicast session 📤 what that data is depends on the app, and the sender sends at a rate and with message sizes set by the app and/or network architecture requirements 💅 any FEC encoding of sender transmissions SHOULD conform with the guidelines of [9]. when congestion control mechanisms are needed (REQUIRED for general Internet operation), NORM transmission SHALL be controlled by the congestion control mechanism 🔥 either way, it is RECOMMENDED that all data transmissions from NORM senders be subject to rate limitations set by the application or the congestion control algorithm 🫶 the sender's transmissions SHOULD make good utilization of the available capacity (which might be limited by the app and/or by congestion control). so yes, new data content and repair content are gonna overlap and get multiplexed together 🦋 other app stuff may also shape how the sender formats and sends things. for example, we need to think about what the sender does during little idle periods when it has nothing to send 🌸

in addition to data content, senders can send other messages or commands as part of protocol operation 🧚 these can happen outside of the application data transfer. in NORM protocols, reliability of these protocol messages may be attempted by sending redundant copies when positive acknowledgement is too much of a no-go because of group size scalability concerns 💀 note that protocol design SHOULD provide mechanisms for dealing with cases where these messages don't reach the group. for example, a command message might get sent redundantly by a sender to say it is temporarily (or permanently) halting transmission 😭 at that point, receivers may be right to respond with NACKs for any outstanding repairs they need, following the rules of the NORM NACK procedure. for efficiency, the sender should leave enough time between the redundant transmissions to catch any NACK-oriented responses from receivers to this command 🎀

generally, whenever there's a NACK or other feedback operation happening, the timing of redundant control message transmissions from a sender, plus other NORM protocol timeouts, should depend on the group greatest round trip timing (GRTT) estimate and whatever NACK or other feedback operation is expected 👑 the NORM GRTT is an estimate of the worst-case round-trip timing from a sender to any receiver in the group. it's assumed the GRTT interval is a conservative estimate of the maximum span (in terms of delay) of the multicast group across a network topology, with respect to a given sender 🌈 NORM instantiations SHOULD be able to dynamically adapt to a wide range of multicast network topologies ⭐

Sender Transmission Interface Description 🍓

Inputs:

  • 1) Application data and control
  • 2) Sender node identifier
  • 3) Data identifiers
  • 4) Segmentation and FEC parameters
  • 5) Transmission rate
  • 6) Application controls
  • 7) Receiver feedback messages (e.g., NACKs)

Outputs:

  • 1) Controlled transmission of messages with headers uniquely identifying data or repair content within the context of the NORM session.
  • 2) Commands indicating sender's status or other transport control actions to be taken.

3.2. NORM Repair Process 🩷

the NACK repair process is a critical piece of NORM protocols, honestly the main character of reliability 👑 it covers the receiver's role in spotting and asking for repairs, plus how the sender responds to those requests. there are four primary elements of the NORM repair process:

  • 1) Receiver NACK process initiation,
  • 3) NACK suppression,
  • 2) NACK message content,
  • 4) Sender NACK processing and response.

3.2.1. Receiver NACK Process Initiation 🦋

the NORM NACK process (cycle) gets kicked off by receivers that detect they need repair transmissions from a specific sender in order to reliably receive stuff ✨ when FEC is applied, a receiver should only start the NACK process once it knows its repair needs are bigger than the amount of pending FEC transmission for a given coding block of data content. that can be figured out at the end of the current transmission block (if it's indicated) or once a subsequent coding block or transmission object starts arriving 🌸 this means the NORM data content has to be marked with its FEC block number, and that ordinal relationship has to be kept in transmission order 🔥

alternatively, if the sender's transmission advertises how many repair packets it already plans to send for a block, the receiver may be able to start the NACK processor earlier 💅 letting receivers start NACK cycles any time they notice their repair needs have outgrown pending repair transmissions might lead to slightly quicker repair cycles. however, it may be useful to limit NACK process initiation to specific events, like the end-of-transmission of an FEC coding block or detecting subsequent coding blocks 🧚 that lets receivers bundle NACK content into fewer NACK messages, and gives a bit of implicit loose synchronization across the receiver set, which helps make probabilistic suppression of NACK feedback work well 🫶 the receiver MUST maintain a history of data content received from the sender so it can figure out its current repair needs. when FEC is employed, the history is expected to match a record of pending or partially-received coding blocks 🌈

for probabilistic, timer-based suppression of feedback, the NACK cycle should begin with receivers observing backoff timeouts 🎀 along with starting that backoff timeout, it's important that receivers record the current position in the sender's transmission sequence where they started the NACK cycle 📤 when the suppression backoff timeout expires, the receivers should only consider their repair needs up to that recorded transmission position when deciding whether to send or suppress a NACK. without this restriction, suppression is greatly reduced, since extra content keeps coming in from the sender while a NACK message travels across the network to the sender and the other receivers 😭

Receiver NACK Process Initiation Interface Description 🍓

Inputs:

  • 1) Sender data content with sequencing identifiers from sender transmissions.
  • 2) History of content received from sender.

Outputs:

  • 1) NACK process initiation decision
  • 2) Recorded sender transmission sequence position.

3.2.2. NACK Suppression ✨

okay so the big trick for not flooding the sender with NACKs is random backoff timeouts 🎀. Before a receiver that needs repairs sends a NACK [10], it waits a random amount of time. When that timer expires, the receiver asks for repairs unless its pending repair needs have already been completely superseded by NACKs it heard from other receivers (when receivers are multicasting NACKs) or by some indicator from the sender. When receivers are unicasting NACKs, the sender can help out with suppression by forwarding a representation of the NACK content it got to the group at large, or by giving some other hint about the repair info it's about to send 💅

For suppression that actually works and scales 🦋, the backoff timeout periods should be independently, randomly picked by each receiver using a truncated exponential distribution [6]. This means most of the receiver set holds off on sending NACKs, betting that the smaller crew of "early NACKers" will cover everyone else's repair needs 🫶. The mean of that distribution should be worked out from the current sender<->group GRTT estimate plus a group size estimate, which comes from other mechanisms in the protocol or is preset by the multicast application.

A simple algorithm can be built to generate random backoff timeouts with the right distribution ✨. On top of that, the algorithm can be designed to optimize the backoff distribution based on the number of receivers (R) that might generate feedback. This "optimization" minimizes the number of feedback messages (e.g., NACK) in the worst-case situation where every receiver generates a NACK 🙈. The maximum backoff timeout (T_maxBackoff) is the knob you turn to trade off reliable delivery latency against the volume of feedback traffic. A larger value of T_maxBackoff gives a lower density of feedback traffic for a given repair cycle, while a smaller value gives shorter latency, which also reduces the buffering requirements of senders and receivers for reliable transport 💜

Given the receiver group size (R) and the maximum allowed backoff timeout (T_maxBackoff), random backoff timeouts (t') with a truncated exponential distribution can be picked with the following algorithm 🧚:

  1. Establish an optimal mean (L) for the exponential backoff based on the group size:
L = ln(R) + 1
  1. Pick a random number (x) from a uniform distribution over a range of:
               L                           L                   L
       --------------------  to   --------------------  +  ----------
       T_maxBackoff*(exp(L)-1)    T_maxBackoff*(exp(L)-1)  T_maxBackoff
  1. Transform this random variate to generate the desired random backoff time (t') with the following equation:
t' = T_maxBackoff/L * ln(x * (exp(L) - 1) * (T_maxBackoff/L))

This C language function can be used to generate an appropriate random backoff time interval 🌸:

double RandomBackoff(double maxTime, double groupSize)
{
    double lambda = log(groupSize) + 1;
    double x = UniformRand(lambda/maxTime) +
               lambda / (maxTime*(exp(lambda)-1));
    return ((maxTime/lambda) *
            log(x*(exp(lambda)-1)*(maxTime/lambda)));
}  // end RandomBackoff()

where UniformRand(double max) returns random numbers with a uniform distribution from the range of 0..max. For example, based on the POSIX "rand()" function, the following C code can be used:

double UniformRand(double max)
{
    return (max * ((double)rand()/(double)RAND_MAX));
}

The number of expected NACK messages generated (N) within the first round trip time for a single feedback event is approximately:

N = exp(1.2 * L / (2*T_maxBackoff/GRTT))

So the maximum backoff time can be adjusted to tradeoff worst-case NACK feedback volume against latency 🍓. This is derived from [6] and assumes T_maxBackoff >= GRTT, where L is the mean of the distribution optimized for the given group size, as shown in the algorithm above.

Note that other mechanisms within the protocol may work to reduce redundant NACK generation even further 🌈. It is suggested that T_maxBackoff be selected as an integer multiple of the sender's current advertised GRTT estimate, such that:

T_maxBackoff = K * GRTT ;where K >= 1

For general Internet operation, a default value of K=4 is RECOMMENDED for operation with multicast (to the group at large) NACK delivery, and a value of K=6 is used for unicast NACK delivery. Alternate values may be used to tune buffer utilization, reliable delivery latency, and group size scalability tradeoffs ⭐.

Given that (K*GRTT) is the maximum backoff time receivers use to initiate NACK transmission, other timeout periods related to the NACK repair process can be scaled accordingly 💖. One of those timeouts is the amount of time a receiver should wait after generating a NACK message before it's allowed to start another NACK backoff/transmission cycle (T_rcvrHoldoff). This delay should be long enough for the sender to respond to the received NACK with repair messages. The right value depends on how long the NACK takes to reach the sender and how long the sender takes to provide a repair response. This MUST include any amount of sender NACK aggregation period during which multiple possible NACKs are collected to work out an efficient repair response 🔥. These timeouts are discussed further in the section below on "Sender NACK Processing and Repair Response".

There are also secondary measures that can make feedback suppression work even better 👑. For example, the sender's data content transmissions can follow an ordinal sequence of transmission. When repairs for data content happen, a receiver can notice that the sender has "rewound" its data content transmission position by observing the data object, FEC block number, and FEC symbol identifiers. Receivers SHOULD limit transmission of NACKs to only when the sender's current transmission position is past the point to which the receiver has incomplete reception. This cuts down on premature repair requests for data the sender may already be planning to send in response to other receivers' requests. This mechanism can be super effective for protocol convergence in high loss conditions, when NACKs from other receivers (or indicators from the sender) get lost 🦋. Another mechanism, which is especially handy when FEC is used, is for the sender to embed an indication of impending repair transmissions in the packets it's currently sending. For example, the indication may be as simple as an advertisement of the number of FEC packets to be sent for the current applicable coding block.

Finally, some thought might go into using the NACKing history of receivers to weight their selection of NACK backoff timeout intervals 💅. For example, if a receiver has historically been experiencing the greatest degree of loss, it may promote itself to statistically NACK sooner than other receivers. Note that this requires there to be correlation over successive intervals of time in the loss a receiver experiences. Such correlation MAY not be present in multicast networks. This adjustment to backoff timeout selection may require creating an "early NACK" slot for these historical NACKers. That additional slot in the NACK backoff window will result in a longer repair cycle process, which may not be desirable for some applications. Resolving these trade-offs may depend on the protocol's target application set or network 🎀.

After the random backoff timeout has expired, the receiver decides whether to generate a NACK repair request or not (i.e., whether it has been suppressed) 🌸. The NACK will be suppressed when any of the following conditions has occurred:

  1. The accumulated state of NACKs heard from other receivers (or forwarding of this state by the sender) is equal to or supersedes the repair needs of the local receiver. Note that the local receiver should consider its repair needs only up to the sender transmission position recorded at the NACK cycle initiation (when the backoff timer was activated).
  2. The sender's data content transmission position "rewinds" to a point ordinally less than that of the lowest sequence position of the local receiver's repair needs. (This detection of sender "rewind" indicates the sender has already responded to other receivers' repair needs, which the local receiver may not have been aware of.) This "rewind" event can occur at any time between 1) when the NACK cycle was initiated with the backoff timeout activation and 2) the current moment when the backoff timeout has expired to suppress the NACK. Another NACK cycle must be initiated by the receiver when the sender's transmission sequence position exceeds the receiver's lowest ordinal repair point. Note that the local receiver may have had its repair needs satisfied by the sender's response to other receivers' repair needs, in which case no further NACKing is required.

If these conditions have not occurred and the receiver still has pending repair needs, a NACK message is generated and transmitted 🧚. The NACK should consist of an accumulation of repair needs from the receiver's lowest ordinal repair point up to the current sender transmission sequence position. A single NACK message should be generated, and the NACK message content should be truncated if it exceeds the payload size of a single protocol message. When such NACK payload limits occur, the NACK content SHOULD contain requests for the ordinally lowest repair content needed from the sender 🍓.

NACK Suppression Interface Description

Inputs:

  1. NACK process initiation decision.
  2. Recorded sender transmission sequence position.
  3. Sender GRTT.
  4. Sender group size estimate.
  5. Application-defined bound on backoff timeout period.
  6. NACKs from other receivers.
  7. Pending repair indication from sender (may be forwarded NACKs).
  8. Current sender transmission sequence position.

Outputs:

  1. Yes/no decision to generate NACK message upon backoff timer expiration.

3.2.3. NACK Content 🎀

The content of NACK messages generated by reliable multicast receivers includes information detailing their current repair needs 💜. The specific information depends on the use and type of FEC in the NORM repair process. Identifying repair needs depends on the data content identification (See Section 3.5 below). At the highest level, the NACK content identifies the sender to which the NACK is addressed and the data transport object (or stream) within the sender's transmission that needs repair. For the indicated transport entity, the NACK content then identifies the specific FEC coding blocks and/or symbols it requires to reconstruct the complete transmitted data 🦋. This content may consist of FEC block erasure counts and/or explicit indication of missing blocks or symbols (segments) of data and FEC content. It's also worth noting that NORM can be effectively instantiated without a requirement for reliable NACK delivery, using the techniques discussed here 🌈.

3.2.3.1. NACK and FEC Repair Strategies 🦋

Okay bestie, so when repair is done with FEC (forward error correction, the "send extra math so you can rebuild lost stuff" trick), the NACK message needs to say two things at minimum: which coding block(s) need repair, and how many erasures (missing packets) that block has. ✨ If the erasure count is exact, the FEC algorithm can fix any loss combination inside that block. That's a whole vibe. 💅

The count might need tweaking for some FEC algorithms, ngl. 🤔 Since repair can take several rounds, an erasure count also assumes the server has basically unlimited unique parity packets to send. In other words, it can always come up with new, never-sent parity packets for any later repair request on the same block. 🫶 Another option is that the sender "round-robin" cycles through its available FEC symbols for a block and eventually gets the repair done. 🔁 But for the most efficient repair, the NACK also has to explicitly say which symbols (information and/or parity) the receiver needs to rebuild the block. This matters most for small to medium block FEC codes (like Reed Solomon), which can only provide a limited number of parity symbols per coding block. 🌸

When FEC isn't part of the repair, or the protocol has to keep reliability going even after the sender has sent all its parity for a block (or the sender's transmission history buffer can't keep up with the delay*bandwidth*loss characteristics of the network), the NACK has to include explicit coding block and/or segment loss info. That way the sender knows exactly what repair packets or data retransmissions to send. 🎀 Explicit loss info in NACKs can also do other jobs. For example, it can help decorrelate loss patterns across a group of receivers, which helps tell apart the candidate congestion control bottlenecks in the receiver set. 🔍

When FEC is used and the NACK asks for explicit repair, there's a strategy where receivers NACK for specific content, which helps with NACK suppression and repair efficiency. 🧚 This strategy assumes the sender might run out of new, unique parity for a coding block and then have to explicitly retransmit some data or parity symbols to finish reliable transfer. It also assumes an FEC algorithm where any parity packet can fill any erasure in the block (like Reed Solomon) is being used. The goal is to make the most of the available parity while sending the least amount of data and repair transmissions when reliably moving data to the group. 👑

With systematic FEC codes, the sender transmits the block's data content (and optionally some parity packets) in its first transmission. Quick note: a systematic FEC coding block is logically made up of the contiguous set of data vectors plus parity vectors for the FEC algorithm in use. For example, a scheme with 64 data symbols and 32 parity symbols per coding block would have FEC symbol identifiers in the range 0 to 95. 🧮

Then receivers can build NACKs asking for enough content to meet their repair needs. Say a receiver has three erasures in a received coding block. It requests the three lowest ordinal parity vectors in the block. In that same 64-plus-32 example, the receiver would explicitly request parity symbols 64 to 66 to fill its three erasures. 💖 Now, if a receiver's loss for the block is bigger than the available parity (more than 32 missing symbols in our example), it has to build a NACK asking for all 32 available parity symbols plus some of its missing data symbols so it can rebuild the block. 😭 If every receiver in the group does this consistently, the NACKs add up to a minimal set of sender transmissions to meet everyone's repair needs. 🌈

Summary, because this is the important part: on the first NACK cycle, ask for the lower ordinal portion of the parity content for the FEC coding block to cover the erasure repair needs. If there aren't enough parity symbols, also ask for the subset of the highest-ordinal missing data symbols to cover what the parity can't fill. This assumes FEC codes like Reed-Solomon, where a single parity symbol can repair any erased symbol. Other FEC types with limited repair capability would need some minor tweaks. 🙈

On later NACK cycles, a receiver may already have gotten some of the repair content it asked for. Then it uses the same strategy, but only NACKs for the parity and/or data symbols it hasn't received yet. 🦋 Receivers can also optionally include an erasure count as a convenience for the sender or for intermediate systems helping with NACK operation. 🍓

After the sender gathers NACKs during the aggregation period, it can start sending fresh (never-before-sent) parity symbols for the block based on the highest receiver erasure count, if it has enough parity symbols that were not sent before. ✨ Otherwise, the sender MUST fall back to sending the explicit set of repair vectors that were requested. 🚨 This approach means the sender doesn't need to keep much state about the requests it got from the group, and it doesn't need the group to synchronize its repair requests. 💜 Since every receiver runs the same consistent algorithm to express its explicit repair needs, NACK suppression gets simpler over multiple repair cycles. Receivers can just compare the NACKs they hear from others against their own calculated repair needs to decide whether to send or suppress their pending NACK. 🫶 Main character energy, honestly. 👑

3.2.3.2. NACK Content Format 🎀

The NACK content format depends on the protocol's data service model and on the data content identification format the protocol uses. ✨ It also depends on what type of FEC encoding (if any) is being used. 🧚 Figure 2 shows a logical, hierarchical transmission content identification scheme. Objects (or streams) and FEC blocking are both optional, and it's up to the protocol instantiation. 🌸 Also, object identification is relative to a given sender. It is recommended that transport data content identification is done within the context of a sender in a given session. 🔍 Since session "streams" and "blocks" are optional, the framework just turns into typical transport data segmentation and reassembly in its simplest form. 🍓

   Session_
           \_
              Sender_
                     \_
                        [Object/Stream(s)]_
                                           \_
                                              [FEC Blocks]_
                                                           \_
                                                              Symbols

            Fig. 2: NORM Data Content Identification Hierarchy

The NACK message format should hit these goals:

  1. Be able to identify transport data unit transmissions needed to repair part of the received content, whether that's a whole missing object/stream (or range), whole FEC coding block(s), or sets of symbols,
  2. Be simple to process for NACK aggregation and suppression,
  3. Be able to include NACKs for multiple objects, FEC coding blocks and/or symbols in a single message, and
  4. Have a reasonably compact format. 💅

If the NORM transport object/stream is identified with an <objectId> and the FEC symbol being sent is identified with an <fecPayloadId>, then concatenating <objectId::fecPayloadId> gives you a basic transport protocol data unit (TPDU) identifier for symbols from a given source. 🦋 NACK content can be built from lists and/or ranges of these TPDU identifiers to describe the receiver's repair needs. ✨ If there's no hierarchical object delineation or FEC blocking, the TPDU is just a simple linear representation of the data symbols the sender transmitted. 🌈 When the TPDU represents a hierarchy for object/stream delineation and/or FEC blocking, the NACK content unit may need flags to show which part of the TPDU applies. 🙈

For example, if an entire "object" (or range of objects) is missing from the received data, the receiver won't necessarily know the right range of <sourceBlockNumbers> or <encodingSymbolIds> to ask for repair. So it needs some way to request repair (or retransmission) of the entire unit represented by an <objectId>. Same deal if entire FEC coding blocks, represented by one or a range of <sourceBlockNumbers>, have been lost. 😭

NACK Content Interface Description

Inputs:

  1. Sender identification.
  2. Sender data identification.
  3. Sender FEC Object Transmission Information.
  4. Recorded sender transmission sequence position.
  5. Current sender transmission sequence position. History of repair needs for this sender.

Outputs:

  1. NACK message with repair requests. 🔥

3.2.4. Sender Repair Response ✨

okay bestie, so once the sender gets a repair request from someone in the group, it kicks off its repair response procedure 🫶. The sender may wish to hold off on sending repair content until it has had enough time to collect potentially multiple NACKs from the receiver set. That's how it figures out the most efficient repair strategy for a given transport stream/object or FEC coding block 💅. Depending on the approach, some protocols might find it helpful for the sender to include an indicator of pending repair transmissions in the message content it's already sending. That can aid some NACK suppression mechanisms 🦋.

The NACK aggregation time should be long enough to cover the maximum receiver NACK backoff window (T_maxBackoff from Section 3.2.2) and the propagation of NACK messages from the receivers to the sender. Note that the maximum transmission delay of a message from a receiver to the sender may be approximately (1*GRTT) in the case of a very asymmetric network topology with respect to transmission delay. So if the maximum receiver NACK backoff time is T_maxBackoff = K*GRTT, the sender NACK aggregation period should be equal to at least:

T_sndrAggregate = T_maxBackoff + 1*GRTT = (K+1)*GRTT

Immediately after the sender NACK aggregation period, the sender will begin transmitting repair content determined from the aggregate NACK state and continue with any new transmission 🚀. At this point, the sender should also observe a "holdoff" period, where it holds itself back from starting a new NACK aggregation period. This lets the new transmission sequence position from the repair response propagate to the receiver group. To allow for worst case asymmetry, this "holdoff" time should be:

T_sndrHoldoff = 1*GRTT

Recall that the receivers will also employ a "holdoff" timeout after generating a NACK message, to allow time for the sender's response. Given a sender <T_sndrAggregate> plus <T_sndrHoldoff> time of (K+1)*GRTT, the receivers should use holdoff timeouts of:

T_rcvrHoldoff = T_sndrAggregate + T_sndrHoldoff = (K+2)*GRTT

This covers a worst-case propagation time of the receiver's NACK to the sender, the sender's aggregation time, and propagation of the sender's response back to the receiver. Additionally, in the case of unicast feedback from the receiver set, it may be useful for the sender to forward (via multicast) a representation of its aggregated NACK content to the group. That allows NACK suppression when there is not multicast connectivity among the receiver set 🌸.

When the <T_sndrAggregate> timeout expires, the sender will begin transmitting repair messages according to the accumulated content of the NACKs it received. There are some guidelines about FEC-based repair and the ordering of the sender's repair response that can make reliable multicast more efficient 💖:

  1. When FEC is used, it is beneficial that the sender transmit previously untransmitted parity content as repair messages whenever possible. This maximizes the receiving nodes' ability to reconstruct the entire transmitted content from their individual subsets of received messages 🎀.
  2. The transmitted object and/or stream data and repair content should be indexed with monotonically increasing sequence numbers (within a reasonably large ordinal space). If the sender observes the discipline of transmitting repair for the earliest content (e.g., ordinally lowest FEC blocks) first, the receivers can use a strategy of withholding repair requests for later content until the sender once again returns to that point in the object/stream transmission sequence. This can increase overall message efficiency among the group and help keep repair cycles relatively synchronized, without depending on strict time synchronization between the sender and receivers. It also helps minimize the buffering requirements of receivers and senders, and reduces redundant transmission of data to the group at large 🧚.

Sender Repair Response Interface Description

Inputs:

  1. Receiver NACK messages
  2. Group timing information

Outputs:

  1. Repair messages (FEC and/or Data content retransmission)
  2. Advertisement of current pending repair transmissions when unicast receiver feedback is detected.

3.3. NORM Receiver Join Policies and Procedures 🌈

Consideration should be given to the policies and procedures by which new receivers join a group (perhaps where reliable transmission is already in progress) and begin requesting repair. If receiver joins are unconstrained, the dynamics of group membership may impede the application's ability to meet its goals for forward progression of data transmission 😭. Policies limiting the opportunities when receivers begin participating in the NACK process may be used to achieve the desired behavior. For example, it may be beneficial for receivers to attempt reliable reception from a newly-heard sender only upon non-repair transmissions of data in the first FEC block of an object or logical portion of a stream. The sender may also implement policies limiting the receivers from which it will accept NACK requests, but this may be prohibitive for scalability reasons in some situations. Alternatively, it may be desirable to have a looser transport synchronization policy and rely upon session management mechanisms to limit group dynamics that can cause poor performance, in some types of bulk transfer applications (or for potential interactive reliable multicast applications) ✨.

Group Join Policy Interface Description

Inputs:

  1. Current object/stream data/repair content and sequencing identifiers from sender transmissions.

Outputs:

  1. Receiver yes/no decision to begin receiving and NACKing for reliable reception of data

3.4. Reliable Multicast Member Identification 🔥

In a NORM protocol (or other multicast protocols) where there is the potential for multiple sources of data, it is necessary to provide some mechanism to uniquely identify the sources (and possibly some or all receivers in some cases) within the group. Identity based on arriving packet source addresses is insufficient for several reasons. These reasons include routing changes for hosts with multiple interfaces that result in different packet source addresses for a given host over time, network address translation (NAT) or firewall devices, or other transport/network bridging approaches. As a result, some type of unique source identifier <sourceId> field should be present in packets transmitted by reliable multicast session members 👑.

3.5. Data Content Identification 💜

The data and repair content transmitted by a NORM sender requires some form of identification in the protocol header fields. This identification is required to facilitate the reliable NACK-oriented repair process. These identifiers will also be used in NACK messages generated. This building block document assumes two very general types of data that may comprise bulk transfer session content. One type is static, discrete objects of finite size, and the other is continuous non-finite streams. A given application may wish to reliably multicast data content using either one or both of these paradigms. While it may be possible for some applications to further generalize this model and provide mechanisms to encapsulate static objects as content embedded within a stream, there are advantages in many applications to provide distinct support for static bulk objects and messages within the context of a reliable multicast session. These applications may include content caching servers, file transfer, or collaborative tools with bulk content. Applications with requirements for these static object types can then take advantage of transport layer mechanisms (i.e., segmentation/reassembly, caching, integrated forward error correction coding, etc.) rather than being required to provide their own mechanisms for these functions at the application layer 🍓.

As noted, some applications may alternatively desire to transmit bulk content in the form of one or more streams of non-finite size. Example streams include continuous quasi-real-time message broadcasts (e.g., stock ticker) or some content types that are part of collaborative tools or other applications. And, as indicated above, some applications may wish to encapsulate other bulk content (e.g., files) into one or more streams within a multicast session.

The components described within this building block document are envisioned to be applicable to both of these models, with the potential for a mix of both types within a single multicast session. To support this requirement, the normal data content identification should include a field to uniquely identify the object or stream <objectId> within some reasonable temporal or ordinal interval. Note that it is not expected that this data content identification will be globally unique. It is expected that the object/stream identifier will be unique with respect to a given sender within the reliable multicast session, and during the time that sender is supporting a specific transport instance of that object or stream 🦋.

Since the "bulk" object/stream content usually requires segmentation, some form of segment identification must also be provided. This segment identifier will be relative to any object or stream identifier that has been provided. Thus, in some cases, NORM protocol instantiations may be able to receive transmissions and request repair for multiple streams and one or more sets of static objects in parallel. For protocol instantiations employing FEC, the segment identification portion of the data content identifier may consist of a logical concatenation of a coding block identifier <sourceBlockNumber> and an identifier for the specific data or parity symbol <encodingSymbolId> of the code block. The FEC Building Block document [9] provides a standard message format for identifying FEC transmission content. NORM protocol instantiations using FEC SHOULD follow that document's guidelines 🙈.

Additionally, flags to determine the usage of the content identifier fields (e.g., stream vs. object) may be applicable. Flags may also serve other purposes in data content identification. It is expected that any flags defined will be dependent upon individual protocol instantiations.

In summary, the following data content identification fields may be required for NORM protocol data content messages:

  1. Source node identifier (<sourceId>)
  2. Object/Stream identifier (<objectId>), if applicable.
  3. FEC Block identifier (<sourceBlockNumber>), if applicable.
  4. FEC Symbol identifier (<encodingSymbolId>)
  5. Flags to differentiate interpretation of identifier fields or identifier structure that implicitly indicates usage.
  6. Additional FEC transmission content fields per FEC Building Block

These fields have been identified because any generated NACK messages will use these identifiers when requesting repair or retransmission of data. NORM protocols that use these data content fields should also be compatible with support for intermediate system assistance to reliable multicast transport operation, when available 💅✨

3.6. Forward Error Correction (FEC) 🦋

okay so FEC is literally one of the biggest glow-ups for NACK-oriented and other reliable multicast protocols 💅 there's a bunch of approaches that work great, see [11], [12], [13]. NORM gets extra perks because FEC-based repair doesn't _generally_ need to know the exact repair content as long as it stays inside the coding block size (counted in symbols) 🫶 In NORM, parity repair packets are usually only sent when receivers ask for them with NACK repair requests. BUT, in some network environments it's lowkey smart to send a fixed number of FEC repair packets mixed in with the regular data symbols too [14]. This can cut down on NACK traffic with pretty small overhead, especially when groups are super big or the network has a large delay*bandwidth product and some expected level of packet loss 📡 FEC isn't unique to NORM, but these kinds of requirements can decide which algorithms and protocol approaches actually fit ✨

Now the tricky part: figuring out which chunk of transmitted data each FEC packet belongs to 🧩 The plan is that FEC algorithms generate a set of parity repair packets for a matching block of transmitted data packets. Data content packets get uniquely identified during transport by the combo <sourceId::objectId::sourceBlockNumber::encodingSymbolId>, so FEC packets are expected to be identified in a similar way 🎀 For the detailed recs on using FEC and the standard formats for related reliable multicast messages, check out the FEC Building Block document [9] 💜

3.7. Round-trip Timing Collection ⏱️

so measuring the packet round-trip time (RTT) between members of the group is required for a few things: timer-based NACK suppression, timing sender commands or certain repair functions, and congestion control 🔥 What kind of RTT info gets collected depends on how the group members talk to each other. If it's only "one-to-many" transmission, the sender might only need the greatest RTT (GRTT) across the receiver set and/or RTT info from just part of the group 🌸 In that case GRTT info can be collected in a pretty scalable way. For congestion control, though, each receiver might need RTT info. Then an alternative scheme can be used where receivers measure their own individual RTTs against the sender and then advertise them to the group or to the sender 🦋 If the group is likely to exchange reliable multicast data "many-to-many," there are other measurement techniques that can be more efficient [15] 💅 And sometimes hosts have absolute time synchronization, which can make RTT measurement easier 🧚 There are trade-offs in multicast congestion control design that need more thought before anyone can make a universal recommendation on RTT (or GRTT) measurement. No matter how RTT info gets collected (especially GRTT for congestion control or other needs), the sender will need to advertise its current GRTT estimate to the group so receivers can use it for their various timeouts 👑

3.7.1. One-to-Many Sender GRTT Measurement 🌈

the goal here is for the sender to learn the GRTT among the receivers who are actively taking part in NORM operation 💖 That set could be the whole group, or just a subset picked by some other mechanism inside the protocol implementation. Here's one way to collect this GRTT info ✨

The sender periodically polls the group with a message (either standalone or "piggy-backed" onto other transmissions) that carries a <sendTime> timestamp, based on the sender's internal clock 🕰️ When a receiver gets this message, it records that <sendTime> timestamp along with the time it arrived, measured by its own clock (<recvTime>) 🦋 When the receiver sends feedback to the sender (either directly or bundled into other feedback messages, depending on how the protocol is set up), it builds a "response" with this formula:

grttResponse = sendTime + (currentTime - recvTime)

Here <sendTime> is the timestamp from the last probe message the receiver got from the source, and (<currentTime> - <recvTime>) is how long it took from when that probe arrived until the receiver made its response 🫶

The sender handles each receiver response by working out a current RTT measurement for the receiver that sent it:

RTT_rcvr = currentTime - grttResponse

During each periodic GRTT probing interval, the source tracks the peak round-trip timing measurement (RTT_peak) from all the responses it got 👑 To keep redundant NACK suppression and repair aggregation as efficient as possible, the GRTT estimate is kept on the conservative side 💅 The source updates its ongoing GRTT estimate following these rules:

  1. If a receiver's response round-trip time (RTT_rcvr) is greater than the current GRTT estimate, the GRTT is immediately bumped up to this new peak value:
GRTT = RTT_rcvr
  1. At the end of the response collection period (aka the GRTT probe interval), if the recorded peak response RTT (RTT_peak) is less than the current GRTT estimate, the GRTT gets updated to:
GRTT = MAX(0.9*GRTT, RTT_peak)
  1. If no feedback comes in, the sender's GRTT estimate just stays the same 🌸
  2. At the end of the response collection period, the peak tracking value (RTT_peak) gets reset to ZERO so peak detection can start fresh 🔄

The GRTT collection period (aka how often probes go out) could be fixed at a value close to what you'd expect for group membership and/or network topology changes ⭐ For robustness, probing can happen more rapidly at protocol startup, then settle into a less frequent steady-state interval 🎀 Optionally, an algorithm could be built to adjust the GRTT collection period dynamically based on the current GRTT estimate (or changes in it) and an estimate of packet loss 🧠 That way probing overhead drops when GRTT is stable and unchanging, but the probing adapts more quickly during periods of change, with shorter GRTT collection periods 🚀 GRTT collection can also be paired with collecting other info for congestion control purposes 💜

In summary (and this part is important), even though NORM repair cycle timeouts are based on GRTT, convergent operation of the protocol does not _strictly_ depend on super accurate GRTT estimation 🙈 This mechanism has been good enough in simulations and in the environments where NORM-like protocols have been deployed so far 🍓 The estimate tracks the peak envelope of actual GRTT (including operating system effects as well as network delays), even in pretty high-loss connections 🔥 The steady-state probing/update interval can potentially be tweaked to fit different levels of expected network dynamics in different environments ✨

3.7.2. One-to-Many Receiver RTT Measurement 🦋

in this approach, receivers send messages with timestamps to the sender 💌 To keep the volume of these receiver-generated messages under control, a suppression mechanism similar to the one described for NACK suppression may be used 🫧 Receivers should keep track of the "age" of their RTT measurements and use it as a metric when competing for feedback opportunities in the suppression scheme 🏆 For example, receivers who haven't made any RTT measurement, or whose RTT measurement is the oldest, should get precedence over other receivers 👑 The sender might have limited capacity to echo the receivers' timestamps back to the group, and it could use this RTT "age" metric to decide which receivers get precedence 💅 The sender can determine GRTT as described in 3.7.1 if it provides sender timestamps to the group ⏱️ Alternatively, receivers who notice their RTT is greater than the sender's GRTT can compete in the feedback opportunity/suppression scheme to give the sender and the group this info 🌈

3.7.3. Many-to-Many RTT Measurement 🌍

for reliable multicast sessions with multiple senders, it can be really useful to measure RTT on a true "many-to-many" basis, rather than having each sender separately track its own RTT 🫶 Some protocol efficiency can be gained when receivers can infer an approximate RTT to a sender from the RTT info they have about another sender, plus that other sender's RTT to the new sender of interest 🧚 For example, for receiver "a" and senders "b" and "c", it's likely that:

RTT(a<->b) <= RTT(a<->c)) + RTT(b<->c)

This estimate can be refined further if a node knows its own RTT to a small subset of other group members, and it also learns RTT info among those other group members during protocol operation 💖

3.7.4. Sender GRTT Advertisement ✨

okay so, for NORM to run in a predictable way, the sender should robustly advertise its current GRTT estimate to the whole receiver set 💖 When everyone in the group shares the same operating GRTT estimate, the protocol can keep moving in its most efficient way 🚀 The trick is to embed the estimate in every pertinent message the sender transmits 🫶 The overhead stays tiny because the GRTT gets squished (quantized) down into a single byte 🎀 The C functions below do this across a wide range, RTT_MIN through RTT_MAX, so small GRTT values get lots of precision and big ones get less 🧚

Values of 1.0e-06 seconds and 1000 seconds are RECOMMENDED for RTT_MIN and RTT_MAX respectively 💜 NORM applications may wish to put a smaller, extra upper limit on the GRTT that senders advertise, so application data delivery latency stays within limits. The catch is more feedback volume in some network environments 😭

unsigned char QuantizeGrtt(double grtt)
{
    if (grtt > RTT_MAX)
        grtt = RTT_MAX;
    else if (grtt < RTT_MIN)
        grtt = RTT_MIN;
    if (grtt < (33*RTT_MIN))
        return ((unsigned char)(grtt / RTT_MIN) - 1);
    else
        return ((unsigned char)(ceil(255.0-
                                (13.0 * log(RTT_MAX/grtt)))));
}

double UnquantizeRtt(unsigned char qrtt)
{
     return ((qrtt <= 31) ?
               (((double)(qrtt+1))*(double)RTT_MIN) :
              (RTT_MAX/exp(((double)(255-qrtt))/(double)13.0)));
}

Quick note, this function is handy for quantizing GRTT times anywhere from 1 microsecond to 1000 seconds 🌈 Of course, NORM implementations can further constrain advertised GRTT estimates (for example, by capping the maximum value) for practical reasons 💅

3.8. Group Size Determination/Estimation 🍓

When NORM includes mechanisms that stir up feedback from the whole group (like congestion control), it can be possible to roughly estimate the group size 👀 You do this by looking at how many feedback messages come back, compared with how the probabilistic suppression mechanism spreads them out. The timer-based suppression mechanism described in this document doesn't need a super accurate group size to work well, so a rough estimate can be enough, especially if you manage it conservatively 🦋 Group size can also be set administratively. If there's no group size determination mechanism at all, a default group size value of 10,000 is RECOMMENDED for reasonable feedback management, given how scalable NORM is expected to be 🌸

3.9. Congestion Control Operation 🔥

Congestion control that fairly shares the available network capacity with other reliable multicast and TCP instantiations is REQUIRED for general Internet operation 😤 The TCP-Friendly Multicast Congestion Control (TFMCC) [16] or Pragmatic General Multicast Congestion Control (PGMCC) techniques [17] can be applied to NORM operation to meet this requirement 💖

3.10. Router/Intermediate System Assistance 🧚

NACK-oriented protocols might benefit from general purpose router assistance 💜 The big one is extra NACK suppression: if routers or intermediate systems can aggregate NACK content (or filter duplicate NACK content) from receivers as it gets relayed toward the sender, that could seriously boost NORM group size scalability 📈 For NORM protocols using FEC, intermediate systems may be able to filter FEC repair messages and do an intelligent "subcast" of repair content down different legs of the multicast topology, based on the repair needs learned from previous receiver NACKs 🌳 Both of these assist functions would need routers to interpret transport data unit content identifiers and flags 👀

3.11. NORM Applicability 🌈

The NORM building block applies to protocols that want to use negative acknowledgement to get reliable data transfer ✨ Well-designed NACK-oriented reliable multicast (NORM) protocols are great for scalability when it's too much hassle to build a higher order delivery infrastructure above basic Layer 3 IP multicast (say, unicast or hybrid unicast/multicast data distribution trees) 🙌 The scalability property of NACK-oriented protocols [18], [19] also fits when you expect a big "fan-out" over a single network hop, like cable-TV data delivery, satellite, or other broadcast services 📡 And the simplicity of a "flat" group-wide multicast distribution can help a wide range of distributed services and dynamic networks and applications 🧁

NORM protocols can use reciprocal multicast communication (between senders and receivers) under the Any-Source Multicast (ASM) model defined in RFC 1112 [2]. They can also scale nicely in asymmetric topologies like Single-Source Multicast (SSM) [8], where the only routing service from receivers back to the sender(s) might be unicast 🦋

NORM operation works with transport layer forward error correction coding techniques as described in [13], plus congestion control mechanisms like those in [16] and [17] 💅 The main limitation is group size scalability when network capacity for receiver feedback is very limited 😭 NORM is also limited by implementation buffering constraints. Buffering greater than what typical point-to-point reliable transport (e.g., TCP) needs is recommended, so the protocol can handle differences in receiver group connectivity and the feedback delays needed for group size scalability 🫧

4. Security Considerations 🔐

NORM protocols are expected to face the same sort of security vulnerabilities as other IP and IP multicast protocols 😱 NORM is compatible with IP security (IPsec) authentication mechanisms [20], which are RECOMMENDED for protecting against session intrusion and denial of service attacks 🛡️ A particular threat for NACK-based protocols is NACK replay attacks, which could stop a NORM sender from making forward progress in transmission. Any standard IPsec mechanisms that can protect against such replay attacks are RECOMMENDED for use 🙈 On top of that, NORM protocol instantiations SHOULD consider providing their own NACK replay attack protection when network layer mechanisms aren't available 💀 The IETF Multicast Security (msec) Working Group is also developing solutions that may be applicable to NORM in the future 🌟

5. Acknowledgements (and these are not Negative) 🫶

The authors would like to thank Rick Jones and Joerg Widmer for their valuable comments on this document 💜 They also want to thank the RMT working group chairs, Roger Kermode and Lorenzo Vicisano, for their support in developing this specification, and Sally Floyd for her early input into this document 👑

6. References 📚

6.1. Normative References

  • [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.
  • [2] Deering, S., "Host Extensions for IP Multicasting", STD 5, RFC 1112, August 1989.

6.2. Informative References

  • [3] Mankin, A., Romanow, A., Bradner, S., and V. Paxson, "IETF Criteria for Evaluating Reliable Multicast Transport and Application Protocols", RFC 2357, June 1998.
  • [4] Clark, D. and D. Tennenhouse, "Architectural Considerations for a New Generation of Protocols". In Proc. ACM SIGCOMM, pages 201--208, September 1990.
  • [5] Kermode, R. and L. Vicisano, "Author Guidelines for Reliable Multicast Transport (RMT) Building Blocks and Protocol Instantiation documents", RFC 3269, April 2002.
  • [6] Nonnenmacher, J. and E. Biersack, "Optimal Multicast Feedback," in IEEE Infocom, San Francisco, California, p. 964, March/April 1998.
  • [7] Macker, J. and R. Adamson, "Quantitative Prediction of Nack Oriented Reliable Multicast (NORM) Feedback", Proc. IEEE MILCOM 2002, October 2002.
  • [8] Holbrook, H., "A Channel Model for Multicast", Ph.D. Dissertation, Stanford University, Department of Computer Science, Stanford, California, August 2001.
  • [9] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M., and J. Crowcroft, "Forward Error Correction (FEC) Building Block", RFC 3452, December 2002.
  • [10] Floyd, S., Jacobson, V., McCanne, S., Liu, C., and L. Zhang. "A Reliable Multicast Framework for Light-weight Sessions and Application Level Framing", Proc. ACM SIGCOMM, August 1995.
  • [11] Metzner, J., "An Improved Broadcast Retransmission Protocol", IEEE Transactions on Communications, Vol. Com-32, No.6, June 1984.
  • [12] Macker, J., "Reliable Multicast Transport and Integrated Erasure-based Forward Error Correction", Proc. IEEE MILCOM 97, October 1997.
  • [13] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M., and J. Crowcroft, "The Use of Forward Error Correction (FEC) in Reliable Multicast", RFC 3453, December 2002.
  • [14] Gossink, D. and J. Macker, "Reliable Multicast and Integrated Parity Retransmission with Channel Estimation", IEEE GLOBECOM 98'.
  • [15] Ozdemir, V., Muthukrishnan, S., and I. Rhee, "Scalable, Low-Overhead Network Delay Estimation", NCSU/AT&T White Paper, February 1999.
  • [16] Widmer, J. and M. Handley, "Extending Equation-Based Congestion Control to Multicast Applications", Proc ACM SIGCOMM 2001, San Diego, August 2001.
  • [17] Rizzo, L., "pgmcc: A TCP-Friendly Single-Rate Multicast Congestion Control Scheme", Proc ACM SIGCOMM 2000, Stockholm, August 2000.
  • [18] Pingali, S., Towsley, D., and J. Kurose, "A Comparison of Sender-Initiated and Receiver-Initiated Reliable Multicast Protocols". In Proc. INFOCOM, San Francisco, CA, October 1993.
  • [19] B.N. Levine, J.J. Garcia-Luna-Aceves, "A Comparison of Known Classes of Reliable Multicast Protocols", Proc. International Conference on Network Protocols (ICNP-96), Columbus, Ohio, Oct 29--Nov 1, 1996.
  • [20] Kent, S. and R. Atkinson, "Security Architecture for the Internet Protocol", RFC 2401, November 1998.

7. Authors' Addresses 💌

These are the wonderful humans behind NORM, so here's where to find them 🧑‍💻

Brian Adamson
Naval Research Laboratory
Washington, DC 20375

EMail: adamson@itd.nrl.navy.mil


Carsten Bormann
Universitaet Bremen TZI
Postfach 330440
D-28334 Bremen, Germany

EMail: cabo@tzi.org


Mark Handley
Department of Computer Science
University College London
Gower Street
London
WC1E 6BT
UK

EMail: M.Handley@cs.ucl.ac.uk


Joe Macker
Naval Research Laboratory
Washington, DC 20375

EMail: macker@itd.nrl.navy.mil

Okay bestie, the legal bit! 💅 The Internet Society owns the copyright here, © 2004. 📜

This document is covered by the rights, licenses, and restrictions in BCP 78. Except where BCP 78 says otherwise, the authors keep all of their rights. 🦋

Now the important part, so read it, fr fr 🙈 The document and everything in it come AS IS, with no guarantees at all. The contributor, the organization they represent or are sponsored by (if any), the Internet Society, and the Internet Engineering Task Force all say no to every warranty, stated or implied. That includes no promise that using the info won't infringe anyone's rights, and no promise of merchantability or fitness for a particular purpose. Not me, not them, nobody. 💀

Intellectual Property 🌸

Real talk: the IETF doesn't pick a side on whether any Intellectual Property Rights might cover the tech in this document, or whether anyone could get a license for it. It also hasn't done any independent digging to find out. 🕵️‍♀️ If you want the IETF's rules on rights in IETF Documents, check out BCP 78 and BCP 79. 📚

IPR disclosures sent to the IETF Secretariat are kept in the IETF's online IPR repository, along with any promised licenses. You can find it at http://www.ietf.org/ipr. The same goes for the results of any attempt to get a general license or permission to use those rights, which implementers and users can look up there too. 🔍

The IETF also wants to hear from anyone who knows about copyrights, patents, patent applications, or other proprietary rights that might cover tech needed to implement this standard. Send that info to ietf-ipr@ietf.org. 🫶

Acknowledgement 🧚

Funding for the RFC Editor function is currently provided by the Internet Society. Thank you to them! 💖

📦 where this page comes from