RFC 5401
Multicast Negative-Acknowledgment (NACK) Building Blocks
RFC 5401: Multicast Negative-Acknowledgment (NACK) Building Blocks 🎀
okay bestie, this one is about how to build reliable multicast protocols that use NACKs 🦋 Here's the title block, so you know who wrote it and where it fits:
- Network Working Group 💜
- RFC: 5401
- Title: Multicast Negative-Acknowledgment (NACK) Building Blocks
- Category: Standards Track (a real Internet standard, not an experiment 👑)
- Date: November 2008
- Obsoletes: RFC 3941 🫶
- Authors:
- B. Adamson, Naval Research Laboratory
- C. Bormann, Universitaet Bremen TZI
- M. Handley, University College London
- J. Macker, Naval Research Laboratory
Status of This Memo ✨
This document specifies an Internet standards track protocol for the Internet community, and it's asking for discussion and suggestions for improvements 💅 Check the current edition of the "Internet Official Protocol Standards" (STD 1) for the standardization state and status of this protocol. Distribution of this memo is unlimited.
Copyright Notice 🌸
Copyright (c) 2008 IETF Trust and the persons identified as the document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) as they stand on the date of publication. Please read these carefully, bestie, because they spell out your rights and restrictions for this document 📜
Abstract 🧚
This document is all about making reliable multicast protocols that use negative-acknowledgment (NACK) feedback. It lays out the design goals and assumptions behind them, and it names the technical challenges that NACK-based (and sometimes general) reliable multicast protocols run into. Those goals and challenges get turned into a set of functional "building blocks," each one tackling a different part of reliable multicast operation. The hope is that these building blocks will be handy for creating different instantiations of reliable multicast protocols 🔥 This document obsoletes RFC 3941.
Table of Contents 🍓
1. Introduction ....................................................2
1.1. Requirements Language ......................................4
2. Rationale .......................................................4
2.1. Delivery Service Model .....................................5
2.2. Group Membership Dynamics ..................................6
2.3. Sender/Receiver Relationships ..............................6
2.4. Group Size Scalability .....................................6
2.5. Data Delivery Performance ..................................7
2.6. Network Environments .......................................7
2.7. Intermediate System Assistance .............................8
3. Functionality ...................................................8
3.1. Multicast Sender Transmission .............................11
3.2. NACK Repair Process .......................................13
3.3. Multicast Receiver Join Policies and Procedures ...........26
3.4. Node (Member) Identification ..............................26
3.5. Data Content Identification ...............................27
3.6. Forward Error Correction (FEC) ............................28
3.7. Round-Trip Timing Collection ..............................29
3.8. Group Size Determination/Estimation .......................33
3.9. Congestion Control Operation ..............................34
3.10. Intermediate System Assistance ...........................34
4. NACK-Based Reliable Multicast Applicability ....................35
5. Security Considerations ........................................36
6. Changes from RFC 3941 ..........................................38
7. Acknowledgements ...............................................38
8. References .....................................................39
8.1. Normative References ......................................39
8.2. Informative References ....................................391. Introduction ✨
Reliable multicast transport is a total must-have when you want to distribute data to a group on the Internet, efficiently and reliably 💖 Group communication is messy, so different protocol types and instantiations are needed to hit the range of performance and scalability goals that different reliable multicast apps and users have (see [RFC2357]). This document is about creating reliable multicast protocols that use negative-acknowledgment (NACK) feedback. NACK-based protocols usually send feedback less often than reliability protocols built on positive acknowledgment (ACK). That's the secret sauce, because fewer feedback messages make the feedback implosion problem easier to handle as the group grows bigger 🦋 Different instantiations might be needed for specific application and network architecture demands [ArchConsiderations], but there are a bunch of fundamental components that can be shared across them.
This document covers the framework and the shared "building block" components for multicast protocols that rely mainly on NACK operation for reliable transport. There's a big pile of reliable multicast components and issues relevant to NACK-based design in here, but it zooms in on the following building blocks, which other IETF documents don't cover:
- NACK-based multicast sender transmission strategies,
- NACK repair process with timer-based feedback suppression, and
- Round-trip timing for adapting NACK and other timers.
NACK-based reliable multicast implementations SHOULD make use of Forward Error Correction (FEC) erasure coding techniques, as described in the FEC Building Block [RFC5052] document. 🔥 Packet-level erasure coding lets missing packets from a given FEC block get recovered using parity packets, instead of classic, individualized retransmission of the original source data content. That's why this document calls the reliability mechanisms a "repair process." 🧚 NACK-based protocols can also reactively send parity packets in response to receiver repair requests, not just proactively add FEC parity content to the original transmission. A hybrid of proactive and reactive FEC use is possible with the mechanisms described here too. Some classes of FEC coding, like Maximal Separable Distance (MDS) codes, let senders dynamically run deterministic, highly efficient receiver group repair strategies as part of a NACK-based, selective automated repeat-request (ARQ) scheme. Iconic, honestly 👑
The relationships to other reliable multicast transport building blocks (like FEC and congestion control), along with general issues with NACK-based reliable multicast protocols, are also discussed. This document follows the guidelines in [RFC3269] 💅
Statement of Intent
This memo describes building blocks that can be applied when designing reliable multicast protocols that use negative-acknowledgement (NACK) feedback. [RFC3941] had a previous description of this specification 💜 RFC 3941 was published in the "Experimental" category. At that time, the Reliable Multicast Transport (RMT) working group intended to resubmit this specification as an IETF Proposed Standard in due course.
This Proposed Standard specification is based on [RFC3941] and has been updated according to accumulated experience and growing protocol maturity since RFC 3941 came out. That experience applies both to this specification itself and to the congestion control strategies related to using it 🌈
The differences between [RFC3941] and this document are listed in Section 6.
1.1. Requirements Language 🎀
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 [RFC2119] 🫶
2. Rationale 🌸
Every potential protocol instantiation that uses the building blocks here (and the ones in other applicable building block documents) is going to have its own specific criteria that can shape its design 💖 To help develop applicable building blocks, it's useful to identify and summarize the driving general protocol design goals and assumptions. These are areas that each protocol instantiation needs to address in detail. Each building block description in this document includes a discussion of how these design criteria impact it. The categories of design criteria considered here are:
- Delivery Service Model,
- Group Membership Dynamics,
- Sender/Receiver Relationships,
- Group Size Scalability,
- Data Delivery Performance, and
- Network Environments.
All of these areas get at least a brief discussion. Other reliable multicast transport building block documents, like [RFC5052], were created to cover areas outside this document's scope, so NACK-based instantiations may depend on those building blocks as well as the ones here. This document focuses on the areas that are unique to NACK-based reliable multicast, but they can be used alongside the other building block areas 🦋 Sometimes one building block can handle a wide range of assumptions, while other times there are trade-offs to meet different application needs or operating environments. Where needed, building block features are designed to be parametric so they can meet different requirements. An underlying goal is to minimize design complexity and to at least recommend default values for any such parameters that meet a general purpose "bulk data transfer" requirement in a typical Internet environment ⭐ The forms of "bulk data transfer" covered here include reliable transport of bulky, fixed-length, a priori static content, and also transmission of non-predetermined, perhaps streamed, content of indefinite length. Section 3.5 goes deeper on these different forms of bulk data content 🧚
2.1. Delivery Service Model 💖
okay so the big goal of a reliable multicast transport protocol is getting data reliably delivered to everyone in a group that's communicating over IP multicast datagram service 🦋 but ngl, the specific service the app is trying to provide can totally change design choices 🤔. The most basic model is "bulk transfer," which is the main focus of this doc and other related RMT working group docs ✨. BUT the same protocol design principles can also work for other service models, like more interactive exchanges of small messages, e.g., white-boarding or text chat 💬. Within these models there are things like whether the sender can cache transmitted data (or state referencing it) for retransmission or repair 🧠. The needs for ordering and/or causality in the sequence of transmissions and receptions among group members may be different depending on the data content 🎀. Group communication is really different from point-to-point, because depending on the data content type, some receivers may finish receiving part of the content and be able to act on it before other members have received it 👀. That may be acceptable (or even desirable) for some apps but not for others 💅. These varying requirements are why we need a bunch of different protocol instantiation designs 🌈. A big challenge is building generally useful building blocks that can handle even a limited range of these capabilities without defining specific application-level details 😭.
Another factor is that the receivers in the multicast group might have really different quality of network connectivity 📶. This may involve receivers with very limited goodput due to connection rate or substantial packet loss 💀. NACK-based protocol implementations may want policies that exclude extremely poor-performing receivers from the main group or move them to a separate delivery group 🙈. Note that some application models may need the entire group to be constrained to the performance of the "weakest member" to meet operational requirements 🫶. Either way, protocol designs should consider this aspect of the reliable multicast delivery service model 👑.
2.2. Group Membership Dynamics 🧚
Here's the tea: group communication can be different from point-to-point because even if the group's composition changes, the "thread" of communication can still exist 🧵. Compare that to point-to-point, where if either of the two parties leaves, the communication process (the exchange of data) is terminated (or at least paused) 😵. Depending on app goals, senders and receivers in a reliable multicast transport "session" may be able to join late, leave, and/or potentially rejoin while the ongoing group communication "thread" stays functional and useful 🌸. Also, this can impact protocol message content 📨. If "late joiners" are supported, some extra information may be placed in message headers to make that work 🍓. Or, the info can be sent in its own message (on demand or now and then) if the impact on the overhead of typical message transmissions is considered too great 🙃. Group dynamics can also impact other protocol mechanisms, like NACK timing, congestion control operation, etc. ⏱️
2.3. Sender/Receiver Relationships 🎀
The relationship between senders and receivers among group members needs some thought 🤝. In some apps there may be a single sender multicasting to a group of receivers 📣. In other cases there may be more than one sender, or the potential for everyone in the group to be both a sender and a receiver of data may exist 🔁.
2.4. Group Size Scalability 📈
Native IP multicast [RFC1112] may scale to extremely large group sizes 🌍. Some apps may want to scale along with the multicast infrastructure's ability to scale, and that's totally valid 💜. In its simplest form, there are limits to the group size a NACK-based protocol can handle without the volume of NACK feedback messages potentially overwhelming network capacity 😱. This is often called "feedback implosion" 💥. Research suggests that NACK-based reliable multicast group sizes on the order of tens of thousands of receivers may operate with acceptable levels of feedback to the sender, using probabilistic, timer-based suppression techniques [NormFeedback] ✨. Instead of receivers immediately sending feedback when loss is detected, these techniques use purposefully-scaled, random back-off timeouts, so some potential NACKing receivers can self-suppress their feedback after hearing messages from other receivers that picked shorter random timeout intervals 🫧. There may also be additional NACK suppression heuristics that can be applied to help these protocols scale to even larger group sizes 🚀. In large-scale cases, it may be prohibitive for members to keep state on all other members (in particular, other receivers) in the group 🙅. The impact of group size needs to be considered when developing applicable building blocks 🧱.
Group size scalability may also be aided by intermediate system assistance; see section 2.7 below 🦋.
2.5. Data Delivery Performance ⚡
There's a trade-off between scalability and data delivery latency when designing NACK-oriented protocols ⚖️. If probabilistic, timer-based NACK suppression is going to be used, some delays will be built into the NACK process 🕰️. This lets suppression happen and lets the sender of data identify appropriate content for efficient repair transmission 🛠️. For example, back-off timeouts can be used to ensure efficient NACK suppression and repair transmission, but this comes at the cost of 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 is made when such bounds are applied 💡.
2.6. Network Environments 🌐
The Internet Protocol has historically had the job of providing service across heterogeneous network topologies 🧩. It's desirable for a reliable multicast protocol to be able to effectively operate across a wide range of the networks that general purpose IP service applies to 🌈. The bandwidth on the links between members of a single group can vary today, from low numbers of kbit/s for wireless links to multiple Gbit/s for high-speed LAN connections, with varying degrees of contention from other flows 📶. Recently, a bunch of asymmetric network services have started to pop off, including 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 IP multicast service is a great fit for 🙌. Also, policy and/or technical issues may result in topologies where multicast connectivity is limited to a source-specific multicast (SSM) model from a specific source [RFC4607] 🔒. Receivers in the group may be restricted to unicast feedback for NACKs and other messages 📬. Consideration must be given, in building block development and protocol design, to the nature of the underlying networks 🧐.
2.7. Intermediate System Assistance 🧚♀️
Intermediate assistance from devices or systems that have direct knowledge of the underlying network topology may be used to increase the performance and scalability of NACK-based reliable multicast protocols 🚀. Feedback aggregation and filtering of sender repair data may be possible with NACK-based protocols using FEC-based repair strategies, as described in the present and other reliable multicast transport building block documents 🔍. However, there will keep being instances where intermediate system assistance 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 utilizing these features when they're available 🫶 ✨.
3. Functionality ✨
Okay bestie, so the last bit was all about what building blocks are and the stuff that makes picking them tricky for NACK-based reliable multicast 🧩 Now we get to the actual building block areas! Some of them are NACK-only, and the rest are general stuff that other reliable multicast protocols use too. For the general ones, we talk about what they need from the NACK side of things, and where it makes sense we point you to other building block docs that can help 🦋
Every building block gets a notional "interface description," which is basically a little map of what it depends on 🗺️ Any "inputs" a building block needs and any "output" it gives back get defined and described in that interface description. Also, the building blocks here don't fully cover each other's "input" and "output" needs. Some inputs have to come from building blocks outside this document (like congestion control or FEC), and others have to be handled by the specific protocol instantiation or implementation (like application data and control) 💅
Here are the building block components that matter for NACK-based reliable multicast:
NORM (NACK-Oriented Reliable Multicast)-Specific
- Multicast Sender Transmission
- NACK Repair Process
- Multicast Receiver Join Policies and Procedures
General Purpose
- Node (Member) Identification
- Data Content Identification
- Forward Error Correction (FEC)
- Round-Trip Timing Collection
- Group Size Determination/Estimation
- Congestion Control Operation
- Intermediate System Assistance
- Ancillary Protocol Mechanisms
Figure 1 gives you a pic overview of these building block areas and how they connect 📸 For example, the content of the data messages a sender first transmits depends on the "Node Identification," "Data Content Identification," and "FEC" components, while how fast messages go out will usually depend on the "Congestion Control" component. Then the receivers' responses (like NACKing for repair) depend on the data message content and inputs from the other components. Finally, the sender processes those responses and feeds them back into its transmission strategy 🔁
The components on the left side of the figure may be useful beyond NACK-based reliable multicast. The bigger ones get covered in other building block docs, like the FEC Building Block [RFC5052]. Quick descriptions of those areas and their roles in NACK-based reliable multicast protocols are below, and "RTT Collection" gets the deep dive in Section 3.7 of this document 🌸
The components on the right are seen as specific to NACK-based reliable multicast protocols, especially the NACK repair process. Those areas get the detailed treatment below (mainly "Multicast Sender Transmission" and "NACK Repair Process" in Sections 3.1 and 3.2). Some other components (like "Security") affect lots of parts of the protocol, and others are more invisible to the core protocol processing. Where it applies, specific technical recommendations are made for mechanisms that will properly meet the goals of NACK-based reliable multicast transport for the Internet 💜
Application Data and Control
|
v
.---------------------. .-----------------------.
| Node Identification |-------+-->| Sender Transmission |<---.
`---------------------' | `-----------------------' |
.---------------------. | | .------------------. |
| Data Identification |-------+ | | Rcvr Join Policy | |
`---------------------' | V `------------------' |
.---------------------. | .----------------------. |
.->| Congestion Control |-------+ | Receiver NACK | |
| `---------------------' | | Repair Process | |
| .---------------------. | | .------------------. | |
| | |-------' | | NACK Initiation | | |
| | FEC |-----. | `------------------' | |
| | |--. | | .------------------. | |
| `---------------------' | | | | NACK Content | | |
| .---------------------. | | | `------------------' | |
`--| RTT Collection |--|--+---->| .------------------. | |
| |--+ | | | NACK Suppression | | |
`---------------------' | | | `------------------' | |
.---------------------. | | `----------------------' |
| Group Size Est. |--|--' | .-----------------. |
| |--+ | | Intermediate | |
`---------------------' | | | System Assist | |
.---------------------. | v `-----------------' |
| Other | | .-------------------------. |
`---------------------' `------->| Sender NACK Processing |--'
| and Repair Response |
`-------------------------'
^ ^
| |
.-----------------------------.
| (Security) |
`-----------------------------'Figure 1: NACK-Based Reliable Multicast Building Block Framework
3.1. Multicast Sender Transmission
Reliable multicast senders send data content into the multicast session 📮 What that data is depends on the application. The sender transmits data content at a rate, and with message sizes, that come from application and/or network architecture requirements. Any FEC encoding of sender transmissions SHOULD conform with the guidelines of the FEC Building Block [RFC5052]. When congestion control mechanisms are needed (REQUIRED for general Internet operation), the sender transmission rate SHALL be controlled by the congestion control mechanism. Either way, it is RECOMMENDED that all data transmissions from multicast senders be subject to rate limitations set by the application or congestion control algorithm 🚦 The sender's transmissions SHOULD make good utilization of the available capacity (which may be limited by the application and/or by congestion control). So yeah, new data and repair content are going to overlap and get multiplexed together ✨ Other factors tied to application operation may decide sender transmission formats and methods too. For example, some thought needs to go into how the sender behaves during intermittent idle periods when it has no data to send 😴
Other sender messages or commands can also be used as part of protocol operation 📣 These can happen outside the scope of application data transfer. In NACK-based reliable multicast protocols, reliability for those protocol messages may be attempted by redundant transmission when positive acknowledgement is prohibitive because of group size scalability concerns. Also, protocol design SHOULD provide mechanisms for dealing with cases where those messages aren't received by the group 🙈 As an example, a sender might redundantly transmit a command message to say it is temporarily (or permanently) halting transmission. At that point, it may make sense for receivers to respond with NACKs for any outstanding repairs they need, following the rules of the NACK procedure. For efficiency, the sender should allow sufficient time between the redundant transmissions to receive any NACK responses from the receivers to this command ⏰
In general, when there's any NACK or other feedback operation, the timing of redundant transmission of control messages from a sender, plus other NACK-based reliable multicast protocol timeouts, should be dependent upon the group greatest round-trip timing (GRTT) estimate and any expected resulting NACK or other feedback operation 🕰️ The sender GRTT is an estimate of the worst-case round-trip timing from a given sender to any receivers in the group. It's assumed that the GRTT interval is a conservative estimate of the maximum span (with respect to delay) of the multicast group across a network topology, relative to a given sender 🌐 NACK-based reliable multicast instantiations SHOULD be able to dynamically adapt to a wide range of multicast network topologies 💖
Inputs:
- Application data and control.
- Sender node identifier.
- Data identifiers.
- Segmentation and FEC parameters.
- Transmission rate.
- Application controls.
- Receiver feedback messages (e.g., NACKs).
Outputs:
- Controlled transmission of messages with headers uniquely identifying data or repair content within the context of the reliable multicast session.
- Commands indicating sender's status or other transport control actions to be taken.
3.2. NACK Repair Process
The NACK repair process is a huge deal for NACK-based reliable multicast protocols 👑 It covers both the receiver's job of spotting and requesting repairs and the sender's response to those requests. There are four primary elements of the NACK repair process:
- Receiver NACK process initiation,
- NACK suppression,
- NACK message content,
- Sender NACK processing and repair response.
3.2.1. Receiver NACK Process Initiation ✨
okay bestie, so the NACK process (cycle) gets kicked off by receivers 💅 who notice they need repair transmissions from a specific sender so they can reliably receive everything. when FEC is in play, a receiver should start the NACK process only when it's known that its repair requirements are bigger than the amount of pending FEC transmission for a given coding block of data content 🧚. this can get figured out at the end of the current transmission block (if it's indicated) or once a later coding block or transmission object starts arriving. it basically means the sender's data content gets marked with its FEC block number, and that ordinal relationship has to be kept in the order things get transmitted 🔥.
Alternatively, if the sender's transmission advertises how many repair packets it's already planning to send for a block, the receiver may be able to start the NACK process earlier 👀. letting receivers start NACK cycles any time they spot that their repair needs have gone past the pending repair transmissions may result in slightly quicker repair cycles ⚡. however, it might be useful to limit NACK process initiation to specific events, like the end-of-transmission of an FEC coding block or the moment subsequent coding blocks show up 🌸. this lets receivers bundle their NACK content into a smaller number of NACK messages, and it gives some implicit loose synchronization across the receiver set, which helps the probabilistic suppression of NACK feedback work well 🫶. the receiver MUST keep a history of the data content it's received from the sender so it can figure out its current repair needs 📚. when FEC is used, the history is expected to line up with a record of pending or partially-received coding blocks 💜.
For probabilistic, timer-based suppression of feedback, the NACK cycle should begin with receivers waiting out backoff timeouts ⏳. at the same time as starting this backoff timeout, it's important that receivers record the position in the sender's transmission sequence where they started the NACK cycle 📍. when the suppression backoff timeout runs out, the receivers should only look at their repair needs up to that recorded transmission position when deciding whether to send or suppress a NACK 🙈. without this restriction, suppression gets way weaker, since more content keeps arriving from the sender while a NACK message travels across the network to the sender and the other receivers 😭.
Inputs:
- Sender data content with sequencing identifiers from sender transmissions.
- History of content received from sender.
Outputs:
- NACK process initiation decision.
- Recorded sender transmission sequence position.
3.2.2. NACK Suppression ✨
okay bestie, the big trick to stop the sender from getting buried in NACKs is making receivers wait a random little moment before they speak 🤫 this is called feedback suppression and it's giving strategy. receivers that need repairs pick a random backoff timeout before sending anything [SrmFramework]. when that timer runs out, a receiver asks for repairs unless its pending needs have already been completely covered by NACKs it heard from other receivers (when receivers are multicasting their NACKs) or by some hint from the sender 🫶. if receivers are unicasting NACKs instead, the sender can help out by forwarding what it got in those NACKs to the whole group, or by sending some other signal about the repairs it's about to send 📣.
For suppression that actually works at scale, each receiver should independently and randomly pick its backoff timeout using a truncated exponential distribution [McastFeedback] 🦋. the result is that most of the group holds its NACKs, trusting that the small crew of "early NACKers" will cover everyone else's repair needs 🏃♀️. the mean of that distribution should be based on the sender's current GRTT estimate and a group size estimate. that estimate either comes from other mechanisms in the protocol or gets preset by the multicast application.
A simple algorithm can generate random backoff timeouts with the right distribution 💖. the algorithm may also be tuned to optimize the backoff distribution for the number of receivers ("R") that could be generating feedback. this "optimization" cuts down the number of feedback messages (like NACKs) in the worst case, where every single receiver sends a NACK 💀. the maximum backoff timeout ("T_maxBackoff") is the knob you turn to balance reliable delivery latency against feedback traffic volume. a bigger "T_maxBackoff" means a lower density of feedback traffic for a given repair cycle 🌸. a smaller one gives shorter latency, and it also cuts down how much buffering senders and receivers need for reliable transport ⭐.
In the functions below, "log()" means the natural logarithm, and "exp()" is based on the mathematical constant 'e' (aka Euler's number), so "exp(x)" is '"e"' raised to the power of '"x"' 🧮. given the receiver group size ("groupSize") and the maximum allowed backoff timeout ("T_maxBackoff"), you can pick random backoff timeouts ("t'") with a truncated exponential distribution using this algorithm:
- Establish an optimal mean ("L") for the exponential backoff based on the "groupSize":
L = log(groupSize) + 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- Transform this random variate to generate the desired random backoff time ("t'") with the following equation:
t' = T_maxBackoff/L * log(x * (exp(L) - 1) * (T_maxBackoff/L))this "C" function can generate an appropriate random backoff time interval 💅:
double RandomBackoff(double T_maxBackoff, double groupSize)
{
double lambda = log(groupSize) + 1;
double x = UniformRand(lambda/T_maxBackoff) +
lambda / (T_maxBackoff*(exp(lambda)-1));
return ((T_maxBackoff/lambda) *
log(x*(exp(lambda)-1)*(T_maxBackoff/lambda)));
} // end RandomBackoff()where "UniformRand(double max)" returns uniformly distributed random numbers from the range "0..max" 🎀. for example, using the POSIX "rand()" function, this "C" code works:
double UniformRand(double max)
{
return (max * ((double)rand()/(double)RAND_MAX));
}the number of NACK messages expected ("N") within the first round-trip time for a single feedback event is roughly:
N = exp(1.2 * L / (2*T_maxBackoff/GRTT))so the maximum backoff time is how you trade worst-case NACK volume against latency 👑. this comes from the equations in [McastFeedback] and assumes "T_maxBackoff >= GRTT", with "L" being the mean of the distribution optimized for the given group size, like in the algorithm above. just know that other mechanisms in the protocol can cut down redundant NACK generation even more 🙈. it's suggested that "T_maxBackoff" be picked as an integer multiple of the sender's current advertised GRTT estimate, like this:
T_maxBackoff = K * GRTT; where K >= 1for general Internet operation, K=4 is RECOMMENDED when NACKs are delivered by multicast (to the group at large) 🔥. K=6 is the RECOMMENDED default for unicast NACK delivery 💜. other values can be used to hit the sweet spot between buffer utilization, reliable delivery latency, and group size scalability ✨.
since "K*GRTT" is the maximum backoff time receivers use before sending a NACK, the other timeouts in the NACK repair process can be scaled to match 🧚. one of them is the holdoff time a receiver waits after sending a NACK before it's allowed to start another NACK backoff/transmission cycle ("T_rcvrHoldoff"). this wait should be long enough for the sender to answer the NACK with repairs 🍓. the right value depends on how long the NACK takes to reach the sender, plus how long the sender takes to send its repair response. this MUST include any sender NACK aggregation period, which is the window where several NACKs get collected so the sender can work out an efficient repair response 😭. more on these timeouts in Section 3.2.4.
there are also secondary tricks that can make feedback suppression work better 🌈. for example, the sender's data transmissions can follow an ordinal sequence. when repairs happen, a receiver can tell the sender has "rewound" its transmission position by looking at the data object, FEC block number, and FEC symbol identifiers 🦋. receivers SHOULD only send NACKs when the sender's current transmission position is past the point where the receiver has incomplete reception. this stops receivers from asking for repairs too early for data the sender is about to send anyway in response to other receivers 🙌. this trick can be super effective for protocol convergence in high loss conditions, especially when other receivers' NACKs (or the sender's signals) get lost 💅. another one (especially useful when FEC is used) is for the sender to embed a heads-up about upcoming repair transmissions in the packets it's already sending. for example, that heads-up could be as simple as advertising how many FEC packets are coming for the current coding block 📣.
one more idea: receivers could use their NACKing history to bias which backoff timeout they pick ⭐. say a receiver has been dealing with the most loss for a while. it could promote itself to statistically NACK sooner than everyone else 🏃♀️. but this only works if the loss a receiver sees stays correlated over successive intervals of time, and that correlation MAY not always show up in multicast networks 🙈. adjusting backoff selection like this might also need an extra "early NACK" slot for these historical NACKers. that extra slot makes the repair cycle longer, which might not be desirable for some applications 😬. how you resolve these trade-offs can depend on the protocol's target application set or network 🎀.
once the random backoff timeout has expired, the receiver decides whether to actually send a NACK repair request or whether it's been suppressed 💖. the NACK is suppressed if any of the following conditions has happened:
- The accumulated state of NACKs heard from other receivers (or forwarded by the sender) is equal to or supersedes the local receiver's repair needs. the local receiver should only consider its repair needs up to the sender transmission position recorded when the NACK cycle started (when the backoff timer got activated) 🧠.
- The sender's data content transmission position "rewinds" to a point ordinally less than the lowest sequence position of the local receiver's repair needs. (spotting this "rewind" means the sender has already responded to repair needs from other receivers, which the local receiver might not know about 👀.) this "rewind" can happen at any time between 1) when the NACK cycle started with the backoff timeout activation and 2) the current moment, when the backoff timeout has expired to suppress the NACK. the receiver has to start another NACK cycle once the sender's transmission sequence position passes the receiver's lowest ordinal repair point 🔁. and it's possible the local receiver already got its repair needs satisfied by the sender's response to other receivers, in which case no more NACKing is needed 🫶.
if none of these conditions has happened and the receiver still has pending repair needs, a NACK message gets generated and sent 🚀. the NACK should be 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 its content gets truncated if it'd go over the payload size of a single protocol message ✂️. when those NACK payload limits kick in, the NACK content SHOULD request the ordinally lowest repair content the receiver needs from the sender 💜.
Inputs:
- NACK process initiation decision.
- Recorded sender transmission sequence position.
- Sender GRTT.
- Sender group size estimate.
- Application-defined bound on backoff timeout period.
- NACKs from other receivers.
- Pending repair indication from sender (may be forwarded NACKs).
- Current sender transmission sequence position.
Outputs:
- Yes/no decision to generate NACK message upon backoff timer expiration.
3.2.3. NACK Message Content ✨
okay so the NACK messages that reliable multicast receivers send are basically their "hey, here's what I still need" texts 💌. What goes inside depends on how FEC is being used in the NACK repair process. Figuring out what's missing depends on the data content identification (see Section 3.5 below) 🔍. At the top level, the NACK tells the sender who it's addressed to and which data transport object (or stream) in that sender's transmission needs fixing 🎀. For that transport entity, it then names the specific FEC coding blocks and/or symbols it needs to rebuild the full transmitted data 🧩. That can look like FEC block erasure counts, explicit lists of missing blocks or symbols (segments) of data and FEC content, or both 💜. Also, NACK-based reliable multicast can work really well without reliable NACK delivery, using the techniques discussed here 🦋.
3.2.3.1. NACK and FEC Repair Strategies 💅
Okay, when FEC-based repair is in play, the NACK has to at minimum say which coding block(s) need repair and give an erasure count (missing packets) for that block 🫶. An exact erasure count means the FEC algorithm can fix any loss combination inside the coding block 🔥. Some FEC algorithms might need that count adjusted, though 🤏.
Multiple repair rounds might be needed to finish the job, so an erasure count also assumes the server has basically unlimited unique FEC parity packets to send 🌈. That means the server can always come up with new, unique, never-before-sent parity packets for any later repair request on the same coding block ✨. The other option is that the sender "round-robin" transmits through its available FEC symbols for a given coding block and eventually gets the repair done 🔄. For the most efficient repair, though, the NACK also needs to explicitly say which symbols (information and/or parity) the receiver needs to rebuild the coding block's content 🎯. This matters most for small- to medium-size block FEC codes (e.g., Reed Solomon [FecSchemes]) that can only provide a limited number of parity symbols per FEC coding block 🌸.
Now, when FEC isn't part of the repair process, or the protocol has to keep things reliable even after the sender has already sent all available parity for a coding block (or the sender's ability to buffer transmission history gets overwhelmed by the (delay*bandwidth*loss) characteristics of the network topology), the NACK needs explicit coding block and/or segment loss info 😭. That way the sender knows exactly which repair packets and/or data retransmissions to send 🎀. Explicit loss info in a NACK can also be useful for other things. For example, it can help decorrelate loss characteristics across a group of receivers, which helps tell apart candidate congestion control bottlenecks in the receiver set 🕵️♀️.
When FEC is used and the NACK content is built to include explicit repair requests, 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 packets for a given 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 within the coding block is being used (e.g., Reed Solomon) 🍓. The whole goal is to squeeze the most out of the available parity while keeping the data and repair transmissions to the group as small as possible during reliable transfer 👑.
When systematic FEC codes are used, the sender transmits the coding block's data content (and optionally some parity packets) in its very first transmission 🌷. A systematic FEC coding block is logically made up of the contiguous set of source data vectors plus the parity vectors for the FEC algorithm in use 🧠. For instance, a systematic scheme with 64 data symbols and 32 parity symbols per coding block would have FEC symbol identifiers in the range of 0 to 95 🔢.
Receivers can then build NACKs that ask for just enough content to cover their repair needs 💖. Take the example from before: if a receiver has three erasures in a given received coding block, it will request transmission of the three lowest ordinal parity vectors in that block 🦋. In our example scheme, that means the receiver would explicitly request parity symbols 64 to 66 to fill its three erasures for the coding block 🎀. But if the receiver's loss for the coding block goes over the available parity quantity (more than 32 missing symbols in our example), the receiver will have to ask for all (32) of the available parity symbols plus some extra missing data symbols so it can rebuild the block 😵. If every receiver in the group does this consistently, the NACKs end up making up a minimal set of sender transmissions to cover their repair needs 🫶.
Quick recap, bestie: on the first NACK cycle, request 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 request the subset of the ordinally highest 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 a minor tweak to this strategy ✨.
On later NACK repair cycles, a receiver might get some of the repair content it asked for earlier 🥹. When that happens, 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 💜.
Other FEC schemes might need changes to the NACK and repair strategy described here 🌸. For example, some of the large block or expandable FEC codes described in [RFC3453] may be less deterministic when it comes to defining the best repair requests from receivers or the best repair transmission strategies from senders 🤔. For those codes, it may be enough for receivers to NACK with an estimate of how many additional FEC symbols they need to finish reliable reception, and then the sender responds accordingly 🍓. This looks like a disadvantage next to codes such as Reed Solomon, but it can be balanced out by the reduced computational requirements and/or the ability to support large coding blocks for better repair efficiency that these codes offer 💅.
After the sender has received and collected NACKs during the aggregation period, it can start sending fresh (never-before-transmitted) parity symbols for the coding block, based on the highest receiver erasure count, if it has enough parity symbols that weren't sent before 🎀. Otherwise, the sender MUST fall back to transmitting the explicit set of repair vectors that was requested 🚨. This approach means the sender doesn't need to keep much state about requests it got from the group, and it doesn't need to sync repair requests across the group 🫧. Since every receiver uses the same consistent algorithm to express its explicit repair needs, NACK suppression gets simpler across multiple repair cycles 👑. Receivers can just compare the NACKs they hear from other receivers against their own calculated repair needs to decide whether to send or suppress their pending NACK messages 🦋.
3.2.3.2. NACK Content Format 💅
okay so the NACK content format depends on the protocol's data service model and on how the protocol identifies its data content 🫶. It also depends on what kind of FEC encoding (if any) is being used 🦋. Figure 2 shows a logical, hierarchical content identification scheme, and it's giving "it's up to the protocol instantiation" energy, because objects (or streams) and FEC blocking are both optional ✨. Note that identifying objects is done with respect to a given sender 🎀. It is recommended that transport data content identification happens within the context of a sender in a given session 🌸. Since the session "streams" and "blocks" are optional, the whole framework degenerates into typical transport data segmentation and reassembly in its simplest form 🧚.
Session_
\_
Sender_
\_
[Object/Stream(s)]_
\_
[FEC Blocks]_
\_
Symbols
Figure 2: Reliable Multicast Data Content Identification HierarchyThe format of NACK messages should enable the following:
- Identification of transport data units required to repair the received content, whether this is an entire missing object/stream (or range), entire FEC coding block(s), or sets of symbols,
- Simple processing for NACK aggregation and suppression,
- Inclusion of NACKs for multiple objects, FEC coding blocks, and/or symbols in a single message, and
- A reasonably compact format.
If the reliable multicast transport object/stream is identified with an <objectId> and the FEC symbol being transmitted is identified with an <fecPayloadId>, then the concatenation of <objectId::fecPayloadId> makes up 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 no hierarchical object delineation or FEC blocking is used, the TPDU is 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 indicate which portion 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 request repair for, so it needs some mechanism to request repair (or retransmission) of the entire unit represented by an <objectId> 😭. The same goes for entire FEC coding blocks, represented by one or a range of <sourceBlockNumbers>, that have been lost 💀.
Inputs:
- Sender identification.
- Sender data identification.
- Sender FEC object transmission information.
- Recorded sender transmission sequence position.
- Current sender transmission sequence position. History of repair needs for this sender.
Outputs:
- NACK message with repair requests.
3.2.4. Sender NACK Processing and Repair Response 🎀
okay so when the sender gets a repair request from a receiver in the group, it kicks off a repair response procedure 👑. The sender may want to hold off on sending repair content until it has collected potentially multiple NACKs from the receiver set ⭐. That way it can work out the most efficient repair strategy for a given transport stream/object or FEC coding block 🧚. Depending on the approach, some protocols may find it helpful for the sender to include an indicator of pending repair transmissions in its current transmitted message content 💖. This can help 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) plus 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 about "(1*GRTT)" in the case of 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 at least:
T_sndrAggregate = T_maxBackoff + 1*GRTT = (K+1)*GRTTRight after the sender NACK aggregation period, the sender starts transmitting repair content determined from the aggregate NACK state, and then keeps going with any new transmission 🚀. At this same moment, the sender should observe a "hold-off" period where it holds itself back from starting a new NACK aggregation period, so the new transmission sequence position from the repair response can propagate to the receiver group 🦋. To allow for worst case asymmetry, this "hold-off" time should be:
T_sndrHoldoff = 1*GRTTReceivers also use a "hold-off" timeout after generating a NACK message, to give the sender time to respond 🌸. Given a sender "<T_sndrAggregate>" plus "<T_sndrHoldoff>" time of "(K+1)*GRTT", the receivers should use hold-off timeouts of:
T_rcvrHoldoff = T_sndrAggregate + T_sndrHoldoff = (K+2)*GRTTThis covers the worst-case propagation time of the receiver's NACK to the sender, the sender's aggregation time, and the propagation of the sender's response back to the receiver 🍓. Also, when feedback from the receiver set is unicast, it may be useful for the sender to forward (via multicast) a representation of its aggregated NACK content to the group, so NACK suppression still works when the receivers don't have multicast connectivity among themselves 🌈.
When the "<T_sndrAggregate>" timeout expires, the sender starts transmitting repair messages based on the accumulated 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 🔥:
When FEC is used, it's beneficial for the sender to transmit previously untransmitted parity content as repair messages whenever it can 💜. This maximizes the receiving nodes' ability to rebuild the entire transmitted content from their own subsets of received messages 🙌.
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 follows the discipline of repairing the earliest content first (e.g., ordinally lowest FEC blocks), receivers can hold off on repair requests for later content until the sender gets back to that point in the object/stream transmission sequence ⏳. This can boost overall message efficiency across the group and help keep repair cycles roughly in sync, without depending on strict time synchronization between the sender and receivers ✨. It also helps minimize the buffering requirements of receivers and senders and cuts down on redundant transmission of data to the group at large 🫧.
Inputs:
- Receiver NACK messages.
- Group timing information.
Outputs:
- Repair messages (FEC and/or Data content retransmission).
- Advertisement of current pending repair transmissions when unicast receiver feedback is detected.
3.3. Multicast Receiver Join Policies and Procedures 🚪
Think about the policies and procedures for how new receivers join a group (maybe where reliable transmission is already in progress) and start requesting repair 🎀. If receiver joins are unconstrained, the dynamics of group membership can get in the way of the application meeting its goals for moving data forward 😵💫. Policies that limit when receivers can start taking part in the NACK process can be used to get the behaviour you want 💖. For example, it may be good for receivers to start reliable reception from a newly heard sender only on non-repair transmissions of data in the first FEC block of an object or logical portion of a stream 🧚. The sender may also set policies that limit which receivers it will accept NACK requests from, 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 on session management mechanisms to limit group dynamics that can hurt performance in some types of bulk transfer applications (or for potential interactive reliable multicast applications) 🌸.
Inputs:
- Current object/stream data/repair content and sequencing identifiers from sender transmissions.
Outputs:
- Receiver yes/no decision to begin receiving and NACKing for reliable reception of data.
3.4. Node (Member) Identification 🪪
In a NACK-based reliable multicast protocol (or other multicast protocols) where there could be multiple data sources, there has to be some mechanism to uniquely identify the sources (and possibly some or all receivers) within the group 💫. Receivers that send NACK messages to the group need to identify the sender the NACK is meant for 🫶. Identity based on the source addresses of arriving packets isn't enough, and there are several reasons why 😭. These include routing changes for hosts with multiple interfaces, which can give a host different packet source addresses over time 🌪️; network address translation (NAT) or firewall devices 🧱; and other transport/network bridging approaches 🌉. So, some type of unique source identifier <sourceId> field SHOULD be present in packets transmitted by reliable multicast session members 👑.
3.5. Data Content Identification ✨
Okay bestie, so the data and repair content a NACK-based reliable multicast sender transmits needs some kind of ID tucked into the protocol header fields 🆔. That ID is required to make the NACK-oriented repair process work, and it's literally the whole point 💅. These identifiers also get used again in the NACK messages that get generated. This building block doc assumes two very general kinds of bulk transfer content: static, discrete objects of finite size and continuous non-finite streams 🌊. An app can reliably multicast with either paradigm, or both.
Could some apps generalize further and wrap static objects inside a stream? Maybe 🤷♀️, but there are real perks to giving static bulk objects and messages their own distinct support inside a reliable multicast session 🎀. Think content caching servers, file transfer, or collaborative tools with bulk content 📁. Those apps can lean on transport layer mechanisms (segmentation/reassembly, caching, integrated forward error correction coding, etc.) instead of being required to build their own versions at the application layer 🙌.
As noted, some apps might instead want to send bulk content as one or more streams of non-finite size 💫. Examples include continuous quasi-real-time message broadcasts (e.g., stock ticker) or content types that are part of collaborative tools or other apps. And, as mentioned above, some apps may want to pack other bulk content (e.g., files) into one or more streams within a multicast session 🧚.
The components in this building block doc are meant to work for both models, and even a mix of both types in a single multicast session 🌈. To make that happen, the normal data content identification should include a field that uniquely identifies the object or stream (e.g., <objectId>) within some reasonable temporal or ordinal interval ⭐. Note that this data content identification is not expected to be globally unique 🙈. The object/stream identifier is expected to 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 "bulk" object/stream content usually needs segmentation, some form of segment identification must also be provided 🧩. This segment identifier is relative to any object or stream identifier that has been provided. So in some cases, NACK-based reliable multicast 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 Basic Schemes building block [FECSchemes], plus descriptions of additional FEC schemes that may be documented later, provide a standard message format for identifying FEC transmission content 📝. NACK-based reliable multicast protocol instantiations using FEC SHOULD follow such guidelines 💀, so please don't skip this part.
Flags are also likely to matter for determining how the content identifier fields are used (e.g., stream vs. object) 🚩. Flags may serve other purposes in data content identification too. Any flags defined will depend on the individual protocol instantiation, so there's no one-size-fits-all list here 🫶.
Okay, in summary, these are the data content identification fields that may be required for NACK-based reliable multicast protocol data content messages 👑:
- Source node identifier (
<sourceId>). - Object/Stream identifier (
<objectId>), if applicable. - FEC Block identifier (
<sourceBlockNumber>), if applicable. - FEC Symbol identifier (
<encodingSymbolId>). - Flags to differentiate interpretation of identifier fields or identifier structure that implicitly indicates usage.
- Additional FEC transmission content fields per FEC Building Block.
These fields made the list because any generated NACK messages will use these identifiers when requesting repair or retransmission of data 💖.
3.6. Forward Error Correction (FEC) 🦋
Multiple forward error correction (FEC) approaches using erasure coding techniques have been identified that can give huge performance boosts to the repair process of NACK-oriented and other reliable multicast protocols [FecBroadcast], [RmFec], [RFC3453] 🚀. NACK-based reliable multicast protocols get extra perks too, since FEC-based repair doesn't generally need explicit knowledge of repair content within the bounds of its coding block size (in symbols) ✨. In NACK-based reliable multicast, parity repair packets generated will generally be transmitted only in response to NACK repair requests from receiving nodes 🙏.
That said, there are benefits in some network environments to transmitting some predetermined quantity of FEC repair packets multiplexed with the regular data symbol transmissions [FecHybrid] 🔁. This can reduce the amount of NACK traffic generated with relatively little overhead cost when group sizes are very large, or when the network connectivity has a large "delay*bandwidth" product with some nominal level of expected packet loss 📉. FEC isn't unique to NACK-based reliable multicast, but these sorts of requirements may dictate which types of algorithms and protocol approaches are applicable 🧠.
A specific issue with using FEC in NACK-based reliable multicast is the mechanism used to identify which portion(s) of transmitted data content each FEC packet applies to 🔍. FEC algorithms are expected to generate a set of parity repair packets for a corresponding block of transmitted data packets. Since data content packets are uniquely identified by the concatenation <sourceId::objectId::sourceBlockNumber::encodingSymbolId> during transport, it is expected that FEC packets will be identified in a similar manner 💜. The FEC Building Block document [RFC5052] provides detailed recommendations about applying FEC, plus standard formats for related reliable multicast protocol messages 📚.
3.7. Round-Trip Timing Collection ⏱️
Measuring packet propagation round-trip time (RTT) among members of the group is required to support timer-based NACK suppression algorithms, timing of sender commands or certain repair functions, and congestion control operation 🕰️. The nature of the round-trip information collected depends on the type of interaction among the group members. With "one-to-many" transmission, it may be that only the sender needs RTT knowledge of the GRTT and/or RTT knowledge of only a portion of the group 📡. Here, the GRTT information might be collected in a reasonably scalable manner 🌸.
For congestion control operation, it's possible that each receiver in the group may need knowledge of its own individual RTT 🎯. In this case, an alternative RTT collection scheme may be used, where receivers collect individual RTT measurements with respect to the sender(s) and advertise them to the group or sender(s) 📣. Where exchange of reliable multicast data is likely to happen among the group on a "many-to-many" basis, there are alternative measurement techniques that might be employed for increased efficiency [DelayEstimation] 🤝. In some cases, there might be absolute time synchronization available among the participating hosts, which may simplify RTT measurement 🕒.
There are trade-offs in multicast congestion control design that need further consideration before a universal recommendation on RTT (or GRTT) measurement can be specified 🧐. Regardless of how RTT information is collected (and more specifically GRTT) with respect to congestion control or other requirements, the sender will need to advertise its current GRTT estimate to the group for the various NACK timeouts used by receivers ⭐💅.
3.7.1. One-to-Many Sender GRTT Measurement ✨
okay bestie, so the goal here is for the sender to estimate the GRTT among the receivers who are actively joining in on NACK-based reliable multicast 💅 That set could be the whole group, or just a subset that another mechanism in the protocol picks out. Here's how the GRTT info gets collected 🦋
The sender periodically polls the group with a message (independent, or "piggy-backed" onto other transmissions) carrying a "<sendTime>" timestamp, measured against the sender's own internal clock 🕰️ When a receiver gets that message, it records the "<sendTime>" and also the time it got the message, by its own clock, which is "<recvTime>". Then when the receiver sends feedback (explicitly, or tucked inside other feedback messages depending on how the protocol instantiation is specced 🎀), it builds a "response" like this:
grttResponse = sendTime + (currentTime - recvTime)where <sendTime> is the timestamp from the last probe message the receiver got from the source, and (<currentTime> - <recvTime>) is the time differential from when that request arrived until the receiver generated the response 💖
The sender processes each receiver's response by working out a current RTT for whichever receiver sent it ✨
RTT_rcvr = currentTime - grttResponseDuring each periodic GRTT probing interval, the source keeps track of the peak round-trip timing measurement (RTT_peak) from all the responses it got 👑 A conservative estimate of GRTT is kept, because that maximizes the efficiency of redundant NACK suppression and repair aggregation 🫶 The source updates its ongoing GRTT estimate by following these rules:
- If a receiver's response round-trip time (
RTT_rcvr) is greater than the currentGRTTestimate, theGRTTis immediately updated to this new peak value:GRTT = RTT_rcvr - At the end of the response collection period (i.e., the GRTT probe interval), if the recorded "peak" response (
RTT_peak) is less than the current GRTT estimate, the GRTT is updated to:GRTT = MAX(0.9*GRTT, RTT_peak) - If no feedback is received, the sender's GRTT estimate remains unchanged.
- At the end of the response collection period, the peak tracking value (
RTT_peak) is reset to ZERO for subsequent peak detection 🔥
The GRTT collection period (aka how often the probing happens) could be fixed at a value on the order of what's expected for group membership and/or network topology dynamics 🌈 For robustness, more rapid probing could be used at protocol startup, then it settles into a less frequent, steady-state interval. Optionally, an algorithm may be developed to adjust the GRTT collection period dynamically, based on the current GRTT estimate (or variations in it) and an estimate of packet loss 😭 That means the probing overhead can drop when the GRTT estimate is stable and unchanging, and then speed up to track things more closely during periods of variation with shorter GRTT collection periods. GRTT collection MAY also be coupled with collection of other information for congestion control purposes 💜
In summary, even though NACK repair cycle timeouts are based on GRTT, it should be noted that convergent operation of the protocol does not depend on highly accurate GRTT estimation 🙈 The current mechanism has proved sufficient in simulations and in the environments where NACK-based reliable multicast 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 relatively high loss connectivity 🍓 The steady-state probing/update interval may be varied 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. The "age" of a receiver's RTT measurement should be kept by the receiver and used 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 has aged the most, should get precedence over other receivers. On the flip side, the sender may have limited capacity to provide an "echo" of the receiver timestamps back to the group, so it could use this RTT "age" metric to decide which receivers get precedence 💅 The sender can determine the "GRTT" as described in 3.7.1 if it provides sender timestamps to the group. Alternatively, receivers who note that their RTT is greater than the sender GRTT can compete in the feedback opportunity/suppression scheme to give the sender and the group this information 🌸
3.7.3. Many-to-Many RTT Measurement
For reliable multicast sessions that involve multiple senders, it may be useful to have RTT measurements happen on a true "many-to-many" basis, rather than having each sender independently track its own RTT 🎀 Some protocol efficiency can be gained when receivers can infer an approximation of their RTT with respect to a sender, based on the RTT information they have about another sender and that other sender's RTT with respect to the new sender of interest. For example, for receiver "a" and senders "b" and "c", it is likely that:
RTT(a<->b) <= RTT(a<->c)) + RTT(b<->c)Further refinement of this estimate can happen if a node has RTT information about its own RTT with respect to a small subset of other group members, and if it learns RTT information among those other group members during protocol operation 🌟
3.7.4. Sender GRTT Advertisement
To make protocol operation deterministic, the sender should robustly advertise its current estimate of "GRTT" to the receiver set 🫶 Common, robust knowledge of the sender's current operating GRTT estimate across the group lets the protocol progress in its most efficient manner 💖 The sender can robustly advertise its GRTT estimate to the group by simply embedding the estimate into all pertinent messages it transmits. The overhead of this can be made quite small by quantizing (compressing) the GRTT estimate down to a single byte of information 🧠 The following C-language functions let you do this over a wide range of GRTT values (RTT_MIN through RTT_MAX), while keeping more precision for small values and less precision for large values. Values of 1.0e-06 seconds and 1000 seconds are RECOMMENDED for RTT_MIN and RTT_MAX respectively. NACK-based reliable multicast applications may wish to place an additional, smaller upper limit on the GRTT advertised by senders, to meet application data delivery latency constraints, at the expense of greater 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)));
}Note that this function is useful for quantizing GRTT times in the range of 1 microsecond to 1000 seconds 🌈 Of course, NACK-based reliable multicast protocol implementations may wish to further constrain advertised GRTT estimates (e.g., limit the maximum value) for practical reasons 💅
3.8. Group Size Determination/Estimation
When NACK-based reliable multicast protocol operation includes mechanisms that stir up feedback from the group at large (e.g., congestion control), it may be possible to roughly estimate the group size based on the number of feedback messages received, relative to the distribution of the probabilistic suppression mechanism used 🔥 The timer-based suppression mechanism described in this document doesn't need a very accurate group size estimate to work well. So a rough estimate, especially if it's managed conservatively, may be enough 🦋 Group size may also be determined administratively. If there's no group size determination mechanism at all, a default group size value of 10,000 is RECOMMENDED for reasonable management of feedback, given how scalable NACK-based reliable multicast usage is expected to be 👑 This conservative (over-)estimate of group size in the algorithms above adds some latency to the NACK repair process if the actual group is smaller, but it comes with a guarantee of feedback implosion protection 🫶 The study of the timer-based feedback suppression mechanism described in [McastFeedback] and [NormFeedback] showed that the group size estimate only needs to be within an order of magnitude to give effective suppression performance ✨
3.9. Congestion Control Operation
Congestion control that fairly shares available network capacity with other reliable multicast and TCP instantiations is REQUIRED for general Internet operation 💖 The TCP-Friendly Multicast Congestion Control (TFMCC) [TfmccPaper] or Pragmatic General Multicast Congestion Control (PGMCC) [PgmccPaper] techniques can be applied to NACK-based reliable multicast operation to meet this requirement 🌸 The former technique has been further documented in [RFC4654] and has been successfully applied in the NACK-Oriented Reliable Multicast Protocol (NORM) [RFC3940] 🎀
3.10. Intermediate System Assistance ✨
okay so NACK-based multicast protocols may totally benefit from general purpose intermediate system help 🧚 like, the routers and boxes in the middle giving the protocol a hand. 💖 If intermediate systems can aggregate NACK content (or filter out duplicate NACK content) from receivers as it's relayed toward the sender, that could seriously boost NORM group size scalability 📈
for NACK-based reliable multicast protocols using FEC, intermediate systems may be able to filter FEC repair messages so they can do an intelligent "subcast" of repair content to different legs of the multicast topology 🌿 depending on the repair needs learned from previous receiver NACKs 🎯
similarly, intermediate systems could monitor receiver NACKs and provide repair transmissions on-demand in response, if enough state on the content being transmitted is being maintained 👀 this can reduce the latency and volume of repair transmissions when the intermediate system is attached to a network link that's super problematic when it comes to packet loss 🥲
these kinds of assist functions would require intermediate systems to interpret transport data unit content identifiers and flags 🔍 NACK-based protocol designs should consider the potential for intermediate system assistance when they specify protocol messages and operations 📝 it's likely that intermediate system assistance will be more pragmatic if message parsing requirements are modest, and if the amount of state an intermediate system has to maintain is relatively small 💅
4. NACK-Based Reliable Multicast Applicability 🌸
the Multicast NACK building block applies to protocols that want to use negative acknowledgement to get reliable data transfer 🫶 properly designed NACK-based reliable multicast protocols offer scalability advantages for applications and/or network topologies where, for various reasons, it's prohibitive to build a higher order delivery infrastructure on top of the basic Layer 3 IP multicast service (e.g., unicast or hybrid unicast/multicast data distribution trees) 🌳
also, the multicast scalability property of NACK-based protocols [RmComparison], [RmClasses] applies where broad "fan-out" is expected for a single network hop (e.g., cable-TV data delivery, satellite, or other broadcast communication services) 📺🛰️ plus, the simplicity of a protocol based on "flat" group-wide multicast distribution may offer advantages for a broad range of distributed services or dynamic networks and applications 🦋 NACK-based reliable multicast protocols can make use of reciprocal (among senders and receivers) multicast communication under the any-source multicast (ASM) model defined in RFC 1112 [RFC1112], and they're capable of scalable operation in asymmetric topologies, like source-specific multicast (SSM) [RFC4607], where there may only be unicast routing service from the receivers to the sender(s) 🧠
NACK-based reliable multicast protocol operation is compatible with transport layer forward error correction coding techniques as described in [RFC3453], and with congestion control mechanisms such as those described in [TfmccPaper] and [PgmccPaper] 🧁 a principal limitation involves group size scalability when network capacity for receiver feedback is very limited 🥺 it's possible that, with proper protocol design, the intermediate system assistance techniques mentioned in Section 2.4 and described further in Section 3.10 can allow NACK-based approaches to scale to larger group sizes ✨ NACK-based reliable multicast operation is also governed by implementation buffering constraints. buffering greater than that required for typical point-to-point reliable transport (e.g., TCP) is recommended to allow for disparity in the receiver group connectivity and to allow for the feedback delays required to attain group size scalability 🫧
prior experimental work included various protocol instantiations that implemented some of the concepts described in this building block document 🧪 this includes the Pragmatic General Multicast (PGM) protocol described in [RFC3208], as well as others that were documented or deployed outside of IETF activities. while the PGM protocol specification and some other approaches encompassed many of the goals of bulk data delivery as described here, this NACK-based building block provides a more generalized framework so that different application needs can be met by different protocol instantiation variants 🎀 the NACK-based building block approach described here includes compatibility with the other protocol mechanisms, including FEC and congestion control, that are described in other IETF reliable multicast building block documents 🤝 the NACK repair process described in this document can provide performance advantages compared to PGM when both are deployed on a pure end-to-end basis without intermediate system assistance 🏆 the round-trip timing estimation described here, and its use in the NACK repair process, allow protocol operation to more automatically adapt to different network environments, or to operate within environments where connectivity is dynamic 🔄 use of the FEC payload identification techniques described in the FEC building block [RFC5052] and specific FEC instantiations gives protocol instantiations more flexibility as FEC techniques evolve, compared to the specific sequence number data identification scheme described in the PGM specification 💫 similar flexibility is expected if protocol instantiations are designed to modularly invoke (at design time, if not run-time) the appropriate congestion control building block for different application or deployment purposes 🌈
5. Security Considerations 🔐
⚠️ bestie, this section is SERIOUS. read it all.
NACK-based reliable multicast protocols are expected to be subject to the same security vulnerabilities as other IP and IP multicast protocols 🚨 however, unlike point-to-point (unicast) transport protocols, it is possible that one badly behaving participant can impact the transport service experience of others in the group 😤 for example, a malicious receiver node could intentionally transmit NACK messages to cause the sender(s) to unnecessarily transmit repairs instead of making forward progress with reliable transfer. also, group-wise messaging to support congestion control or other aspects of protocol operation may be subject to similar vulnerabilities. thus, it is highly RECOMMENDED that security techniques such as authentication and data integrity checks be applied for NACK-based reliable multicast deployments. protocol instantiations using this building block MUST identify approaches to security that can be used to address these and other security considerations 🛡️
NACK-based reliable multicast is compatible with IP security (IPsec) authentication mechanisms [RFC4301] that are RECOMMENDED for protection against session intrusion and denial of service attacks 🔒 a particular threat for NACK-based protocols is that of NACK replay attacks, which could prevent a multicast sender from making forward progress in transmission 🙈 any standard IPsec mechanisms that can provide protection against such replay attacks are RECOMMENDED for use. the IETF Multicast Security (MSEC) Working Group has developed a set of recommendations in its "Multicast Extensions to the Security Architecture for the Internet Protocol" [IpsecExtensions] that can be applied to appropriately extend IPsec mechanisms to multicast operation 🧩 an appendix of this document specifically addresses the NACK-Oriented Reliable Multicast protocol service model. as complete support for IPsec multicast operation may potentially follow reliable multicast deployment, NACK-based reliable multicast protocol instantiations SHOULD consider providing support for their own NACK replay attack protection when network layer mechanisms are not available. This MAY be necessary when IPsec implementations are used that do not provide multicast replay attack protection when multiple sources are present.
for NACK-based multicast deployments with large receiver groups using IPsec, approaches might be developed that use shared, common keys for receiver-originated protocol messages to maintain a practical number of IPsec Security Associations (SAs) 🔑 however, such group-based authentication may not be sufficient unless the receiver population can be completely trusted 🤨 additionally, this can make identification of badly behaving (although authenticated) receiver nodes problematic, as such nodes could potentially masquerade as other receivers in the group 👻 in deployments such as this, one SHOULD consider use of source-specific multicast (SSM) instead of any-source multicast (ASM) models of multicast operation 💡 SSM operation can simplify security challenges in a couple of ways:
- A NACK-based protocol supporting SSM operation can eliminate direct receiver-to-receiver signaling. This dramatically reduces the number of security associations that need to be established.
- The SSM sender(s) can provide a centralized management point for secure group operation for its respective data flow, as the sender alone is required to conduct individual host authentication for each receiver when group-based authentication does not suffice or is not pragmatic to deploy.
when individual host authentication is required, then it is possible receivers could use a digital signature on the IPsec Encapsulating Security Protocol (ESP) payload as described in [RFC4359] 🪪 either an identity-based signature system or a group-specific public key infrastructure could avoid per-receiver state at the sender(s). additionally, implementations MUST also support policies to limit the impact of extremely or exceptionally poor-performing (due to bad behavior or otherwise) receivers upon overall group operation, if this is acceptable for the relevant application 🚫
as described in Section 3.4, deployment of NACK-based reliable multicast in some network environments may require identification of group members beyond that of IP addressing 🗺️ if protocol-specific security mechanisms are developed, then it is RECOMMENDED that protocol group member identifiers are used as selectors (as defined in [RFC4301]) for the applicable security associations. When IPsec is used, it is RECOMMENDED that the protocol implementation verify that the source IP addresses of received packets are valid for the given protocol source identifier, in addition to usual IPsec authentication. This would prevent a badly behaving (although authorized) member from spoofing messages from other legitimate members, provided that individual host authentication is supported 🕵️
the MSEC Working Group has also developed automated group keying solutions that are applicable to NACK-based reliable multicast security 🗝️ for example, to support IPsec or other security mechanisms, the Group Secure Association Key Management Protocol [RFC4535] MAY be used for automated group key management. the technique it identifies for "Group Establishment for Receive-Only Members" may be application NACK-based reliable multicast SSM operation 🎉
you're all caught up, bestie 💜
6. Changes from RFC 3941 💅
okay so this is the glow-up list 🌸 It covers what changed between the Experimental version of this spec, [RFC3941], and this one:
- Change of title to avoid confusion with NORM Protocol specification,
- Updated references to related, updated RMT Building Block documents, and
- More detailed security considerations. 🔒
7. Acknowledgements 🫶
(and these are not Negative) 💜
bestie, the authors gave a shoutout to some legends 🙌 They thank George Gross, Rick Jones, and Joerg Widmer for their valuable comments on this document. They also thank the RMT working group chairs, Roger Kermode and Lorenzo Vicisano, for their support in developing this specification, and Sally Floyd for her early inputs into this document. ✨
8. References 📚
8.1. Normative References
[RFC1112] Deering, S., "Host extensions for IP
multicasting", STD 5, RFC 1112, August 1989.
[RFC2119] Bradner, S., "Key words for use in RFCs to
Indicate Requirement Levels", BCP 14, RFC 2119,
March 1997.
[RFC4607] Holbrook, H. and B. Cain, "Source-Specific
Multicast for IP", RFC 4607, August 2006.8.2. Informative References
these are the extra reads if you want to go deeper 🤓
[ArchConsiderations] Clark, D. and D. Tennenhouse, "Architectural
Considerations for a New Generation of
Protocols", Proc. ACM SIGCOMM, pp. 201-208,
September 1990.
[DelayEstimation] Ozdemir, V., Muthukrishnan, S., and I. Rhee,
"Scalable, Low-Overhead Network Delay
Estimation", NCSU/AT&T White Paper,
February 1999.
[FECSchemes] Watson, M., "Basic Forward Error Correction
(FEC) Schemes", Work in Progress, July 2008.
[FecBroadcast] Metzner, J., "An Improved Broadcast
Retransmission Protocol", IEEE Transactions on
Communications Vol. Com-32, No. 6, June 1984.
[FecHybrid] Gossink, D. and J. Macker, "Reliable Multicast
and Integrated Parity Retransmission with
Channel Estimation", IEEE Globecomm 1998, 1998.
[FecSchemes] Lacan, J., Roca, V., Peltotalo, J., and S.
Peltotalo, "Reed-Solomon Forward Error
Correction (FEC) Schemes", Work in Progress,
November 2007.
[IpsecExtensions] Weis, B., Gross, G., and D. Ignjatic,
"Multicast Extensions to the Security
Architecture for the Internet Protocol", Work
in Progress, June 2008.
[McastFeedback] Nonnenmacher, J. and E. Biersack, "Optimal
Multicast Feedback", IEEE Infocom p. 964,
March/April 1998.
[NormFeedback] Adamson, B. and J. Macker, "Quantitative
Prediction of NACK-Oriented Reliable Multicast
(NORM) Feedback", IEEE MILCOM 2002,
October 2002.
[PgmccPaper] Rizzo, L., "pgmcc: A TCP-Friendly Single-Rate
Multicast Congestion Control Scheme", ACM
SIGCOMM 2000, August 2000.
[RFC2357] Mankin, A., Romanov, A., Bradner, S., and V.
Paxson, "IETF Criteria for Evaluating Reliable
Multicast Transport and Application Protocols",
RFC 2357, June 1998.
[RFC3208] Speakman, T., Crowcroft, J., Gemmell, J.,
Farinacci, D., Lin, S., Leshchiner, D., Luby,
M., Montgomery, T., Rizzo, L., Tweedly, A.,
Bhaskar, N., Edmonstone, R., Sumanasekera, R.,
and L. Vicisano, "PGM Reliable Transport
Protocol Specification", RFC 3208,
December 2001.
[RFC3269] Kermode, R. and L. Vicisano, "Author Guidelines
for Reliable Multicast Transport (RMT) Building
Blocks and Protocol Instantiation documents",
RFC 3269, April 2002.
[RFC3453] 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.
[RFC3940] Adamson, B., Bormann, C., Handley, M., and J.
Macker, "Negative-acknowledgment (NACK)-
Oriented Reliable Multicast (NORM) Protocol",
RFC 3940, November 2004.
[RFC3941] Adamson, B., Bormann, C., Handley, M., and J.
Macker, "Negative-Acknowledgment (NACK)-
Oriented Reliable Multicast (NORM) Building
Blocks", RFC 3941, November 2004.
[RFC4301] Kent, S. and K. Seo, "Security Architecture for
the Internet Protocol", RFC 4301,
December 2005.
[RFC4359] Weis, B., "The Use of RSA/SHA-1 Signatures
within Encapsulating Security Payload (ESP) and
Authentication Header (AH)", RFC 4359,
January 2006.
[RFC4535] Harney, H., Meth, U., Colegrove, A., and G.
Gross, "GSAKMP: Group Secure Association Key
Management Protocol", RFC 4535, June 2006.
[RFC4654] Widmer, J. and M. Handley, "TCP-Friendly
Multicast Congestion Control (TFMCC): Protocol
Specification", RFC 4654, August 2006.
[RFC5052] Watson, M., Luby, M., and L. Vicisano, "Forward
Error Correction (FEC) Building Block",
RFC 5052, August 2007.
[RmClasses] Levine, B. and J. Garcia-Luna-Aceves, "A
Comparison of Known Classes of Reliable
Multicast Protocols", Proc. International
Conference on Network Protocols (ICNP-
96) Columbus, OH, October 1996.
[RmComparison] Pingali, S., Towsley, D., and J. Kurose, "A
Comparison of Sender-Initiated and Receiver-
Initiated Reliable Multicast Protocols", Proc.
INFOCOMM San Francisco, CA, October 1993.
[RmFec] Macker, J., "Reliable Multicast Transport and
Integrated Erasure-based Forward Error
Correction", IEEE MILCOM 1997, October 1997.
[SrmFramework] 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.
[TfmccPaper] Widmer, J. and M. Handley, "Extending Equation-
Based Congestion Control to Multicast
Applications", ACM SIGCOMM 2001, August 2001.Authors' Addresses 🦋
meet the squad who wrote it 💖
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
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📦 where this page comes from
- ietf: rfc5401 2008-11
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms