RFC 2887

The Reliable Multicast Design Space for Bulk Data Transfer

📅 published August 2000, from ietf

RFC 2887: The Reliable Multicast Design Space for Bulk Data Transfer 💖

Okay bestie, the title block first 🎀 This one is RFC 2887, from the Network Working Group, filed as Informational in August 2000. The authors are M. Handley, S. Floyd (both from ACIRI), B. Whetten (Talarian), R. Kermode (Motorola), L. Vicisano (Cisco), and M. Luby (Digital Fountain, Inc.). It doesn't obsolete anything and doesn't update anything 🦋

Status of this Memo ✨

This memo gives information to the Internet community. It is not an Internet standard of any kind, and it's free to share with anyone 🌸

Copyright (C) The Internet Society (2000). All Rights Reserved. 💅

Abstract

The design space for reliable multicast is huge, and people have come up with lots of solutions already 🔥 But application requirements narrow that giant space down to a much smaller solution space. This document walks through the design space and shows how an application's constraints change which solutions are possible 🧚

1. Introduction 🌈

Okay so "general purpose reliable multicast protocol" is kind of an oxymoron, ngl 💀 Different applications want different things from a reliable multicast protocol, and those needs limit the design space so much that two apps with different requirements often can't share one solution. That said, there are plenty of successful reliable multicast designs that do their special-purpose job really well ⭐

In this document we look at the design space for reliable multicast protocols meant for bulk data transfer. "Bulk data transfer" should be read broadly. The main limits are that the data stream is continuous and long-lived, and those constraints are needed for the forms of congestion control we currently understand 🎀 The point of this review is to collect an overview of the field and spell out the constraints that particular mechanisms bring with them. The goal is to guide the standardization process for protocols and protocol building blocks. To do that, we group potential solutions into a few loose categories. Real protocols might mix mechanisms from more than one of these clusters 🫶

The biggest constraint on solutions comes from the need to scale to large receiver sets. For small receiver sets, the design space is a lot less restricted 🦋

2. Application Constraints 💜

Application requirements for reliable multicast (RM) are as broad and varied as the apps themselves. Still, there's a set of requirements that really shapes how an RM protocol gets designed. A quick list includes:

  • Does the application need to know that everyone received the data?
  • Does the application need to constrain differences between receivers?
  • Does the application need to scale to large numbers of receivers?
  • Does the application need to be totally reliable?
  • Does the application need ordered data?
  • Does the application need to provide low-delay delivery?
  • Does the application need to provide time-bounded delivery?
  • Does the application need many interacting senders?
  • Is the application data flow intermittent?
  • Does the application need to work in the public Internet?
  • Does the application need to work without a return path (e.g. satellite)?
  • Does the application need to provide secure delivery?

When we're standardizing bulk data transfer protocols, we can rule out apps with multiple interacting senders and intermittent data flows 🙈 It's not that these apps don't matter. It's just that we don't have effective congestion control for them yet 😭

2.1. Did everyone receive the data? 🍓

Lots of applications have a logically defined unit (or units) of data that needs to go to multiple clients. Think a file or a set of files, a software package, a stock quote or a package of stock quotes, an event notification, a set of slides, or a frame or block from a video. An application data unit (ADU) is a logically separable chunk of data that's useful to the application. Sometimes an ADU is small enough to fit in one packet (like an event notification or a stock quote). Other times an ADU is way bigger than a packet (like a software package) 📦

A protocol may optionally provide delivery confirmation to make sure delivery is reliable. That's a way for receivers to tell the sender when data has arrived. There are two types of confirmation: ADU-level and packet-level. ADU-level confirmation is useful at the application level. It tells the app how far along receivers are, and it helps decide when to stop sending packets about a particular ADU ✨ Packet-level confirmation is useful at the transport level. It tells the transport layer when it can free the buffer space it was using to store packets that have been confirmed delivered 🧚

Some apps have a strong need to confirm that every receiver got an ADU. If not, they need to find out which specific receivers failed to get the whole thing. Examples are apps where receivers pay for data, and reliable file-system replication. Other apps don't need that at all, like distributing free software 💅

If the application does need to know that every receiver got the ADU, then a positive acknowledgment must be received from every receiver. These acknowledgments can be aggregated, though. If the application needs to know exactly which receivers failed to get the ADU, that adds extra constraints on how acknowledgments can be aggregated 🤔

It should be noted that different mechanisms can be used for ADU-level confirmation and packet-level confirmation in the same application. For example, an ADU-level confirmation mechanism that uses positive acknowledgments may sit on top of a packet-level NACK or FEC-based transport. This typically only makes sense when ADUs are a lot bigger than a single packet 🌸

2.2. Constraining differences 🎀

Some apps need to keep differences between receivers under control, so that the data reception characteristics for all receivers fall within some range. A stock price feed is a good example. It's totally unacceptable for one receiver to get delivery that's way more delayed than everyone else's 😭

This requirement is hard to satisfy without hurting performance. Solutions usually involve not sending more than a limited amount of new data until positive acknowledgments have come back from all the receivers. The catch is that this kind of solution doesn't handle network and end-system failures very well 💀

2.3. Receiver Set Scaling 🦋

Plenty of RM apps don't need to scale to large numbers of receivers. For those apps, there are solutions available that wouldn't be an option for apps where scaling to big receiver sets is a must-have 🌈

A protocol must achieve good throughput of application data units to receivers. That means most of the data delivered to receivers is actually useful for recovering the ADU they're trying to get. A protocol must also provide good congestion control, so the available network resources are shared fairly between all applications 👑 Receiver set scaling is one of the most important constraints for meeting these requirements, because it strictly limits which mechanisms can achieve them. Only mechanisms that scale efficiently to a large receiver population are left in the running. Lots of systems have used acknowledgement packets to reach these goals, but it's important to understand the strengths and limitations of the different ways of using them 🫶

In a very small system, it may be fine to have receivers acknowledge every packet. This gives the sender the most information possible about reception conditions at all the receivers. That information can be used both to get good throughput and for congestion control 🔥

For larger systems, these "flat ACK" schemes cause acknowledgement implosions at the sender 💀 People have tried to fix this by sending aggregate ACKs infrequently [RMWT98, BC94], but it's really hard to build effective congestion control into those protocols because the feedback is so sparse 🙈

Using negative acknowledgments (NACKs) instead of ACKs shrinks the problem to a NACK implosion. Only receivers that are missing packets send NACKs. Since the sender really only needs to know that at least one receiver is missing data to get good throughput, various NACK suppression mechanisms can be applied 🌸

Another option besides NACKs is ACK aggregation. You arrange the receivers into a logical tree, so each leaf sends ACKs to its parent, which aggregates them and passes them up the tree. Tree-based protocols scale well, but forming the tree can be tricky 🌳

Other ACK topologies, like rings, are also possible. They're often harder to form and maintain than trees, though 🧚 Another strategy is to add mechanisms to routers so they can help achieve good throughput or lower the cost of getting it ✨

All of these solutions improve receiver set scaling, but every one of them has limits of some kind ⭐ One class of solutions scales to an infinite number of receivers by having no feedback channel whatsoever to achieve good throughput. These open-loop solutions take the initial data and encode it with an FEC-style mechanism. The encoded data then gets sent in a continuous stream. Receivers join the session and keep receiving packets until they have enough to decode the original data. At that point, they leave the session 🦋

So yeah, the intended scale of the session limits the possible solutions. Every solution works for very small sessions, but as the intended receiver set grows, the range of solutions that can be deployed safely shrinks 📉

It should also be noted that hybrids of these mechanisms are possible. Using one mechanism at the packet level and a different (typically higher-overhead) solution at the ADU level may also scale reasonably if the ADUs are large compared to packets 🎀

2.4. Total vs Semi-reliable 💖

okay so some apps need total reliability 😭 like, if even ONE piece of an application data unit goes missing, none of the rest of it is useful. File transfer is the classic example, bestie. a file with a hole in it is just a broken file 💀

But some apps are way more chill about it 🫶 audio broadcasting is the perfect example: if a few packets go missing, the audio gets a little worse, but it's still totally listenable ✨ Those apps can sometimes get by with no extra reliability on top of native IP reliability, but honestly, having a semi-reliable multicast protocol is often super desirable 🎀

2.5. Time-bounded Delivery 🦋

Lots of apps just want data to reach the receivers as fast as possible 🏃‍♀️ They don't have an absolute deadline for delivery. vibes only 🌸

But some apps have hard delivery constraints 😤 If the data doesn't arrive at the receiver by a certain time, there is literally no point delivering it at all 💀 That time-boundedness can come from real-time constraints like audio or video streaming, or from new data superseding old data 🔥 In both cases, the app needs a much greater degree of control over precisely what it sends at which time, compared with apps like file transfer 👑

Time-bounded delivery usually also implies a semi-reliable protocol, but the converse does not necessarily hold 🧚 (iykyk: time-bounded usually comes with semi-reliable, but semi-reliable doesn't automatically mean time-bounded.)

3. Network Constraints 🌈

The properties of the network the app is deployed in can themselves constrain the reliable multicast design space 🗺️

3.1. Internet vs Intranet 🏢

In principle the Internet and intranets are the same. In practice though, an intranet being under one administration might allow solutions that can't easily be done on the public Internet 🤓 So if the data is of very high value, it might be appropriate to enhance the routers to help a reliable multicast transport protocol 💅 On the public Internet, the extra expense of supporting this state in the routers is less likely to be acceptable 💸

3.2. Return Path 📬

In principle, when feedback is required from receivers, it can be multicast or unicast. Multicast feedback has advantages, especially in NACK-based protocols where it's valuable for NACK suppression ✨ However, it's not clear at this time whether all ISPs will allow all members of a session to send to that session 😬 If multicast feedback isn't allowed, unicast feedback can almost always be substituted, although often at the expense of additional messages and mechanisms.

Some networks may not allow any form of feedback, though 🛰️ The main example is satellite broadcasts, where the back channel may be very narrow or even non-existent. For those networks the solution space is super constrained: only FEC-based encodings have any real chance of working 🫠 If the receivers are direct satellite receivers, then no congestion control is needed, but it's dangerous to assume that, because a satellite hop can feed downstream networks ⚠️ So congestion control still needs to be considered for solutions that don't have a return path.

3.3. Network Assistance 🧚

A reliable multicast protocol must involve mechanisms running in end hosts, and must involve routers forwarding multicast packets. However, under some circumstances it's possible to rely on some additional degree of assistance from network elements. Broadly speaking, we can cluster RM protocols into four classes depending on the degree of support they receive from other network elements 💜

  • No Additional Support: The routers merely forward packets, and only the sender and receivers have any reliable multicast protocol state.
  • Layered Approaches: Data is split across multiple multicast groups. Receivers join appropriate groups to receive only the traffic they require. This may in some cases require fast join or leave functionality from the routers, and may require more forwarding state in the routers.
  • Server-based Approaches: Additional nodes are used to assist with data delivery or feedback aggregation. These additional nodes might not be normal senders or receivers, and may be present on the distribution or feedback tree only to provide assistance to the reliable multicast protocol. They would not otherwise receive the multicast traffic.
  • Router-based Approaches: With router-based approaches, routers on the normal data distribution tree from the sender to the receivers assist in the delivery of data, or in feedback aggregation or suppression. As routers can directly influence multicast routing, they have more control over which traffic goes to which group members than server-based approaches do. However, routers don't normally have a large amount of spare memory or processing power, which restricts how much functionality can be placed in them. In addition, router code is normally more difficult to upgrade than application code, so router-based approaches need to be very general, as they are more difficult to deploy and to change 🫣

4. Good Throughput Mechanisms 🍓

Two main concerns a RM protocol must address are congestion control and good throughput ✨ Packet loss plays a major role with respect to both. The primary symptom of congestion in many networks is packet loss. The primary obstacle to overcome for good throughput is also packet loss. So measuring and reacting to packet loss is crucial for addressing both concerns 📉 RM solutions that address these concerns can be roughly categorized as using one or more of the following techniques:

  • Data packet acknowledgment.
  • Negative acknowledgment of missing data packets.
  • Redundancy allowing not all packets to be received.

These techniques can themselves be usefully subdivided, so we can examine the parts of the requirement space where each mechanism can be deployed 🧩 In this section we focus on using these mechanisms for achieving good throughput, and in the next section we focus on using them for congestion control 💖

4.1. ACK-based Mechanisms 🎀

The simplest ACK-based mechanism involves every receiver sending an ACK packet for every data packet it receives, and resending packets that are lost by any receiver. Such mechanisms are limited to very small receiver groups by the implosion of ACKs received at the sender, so for this reason they're impractical for most applications 🙅‍♀️

Putting multiple ACKs into a single data packet [RMWT98] reduces the implosion problem by a constant amount, allowing slightly larger receiver groups 📦 However, a limit is soon reached where feedback to the sender is too infrequent for sender-based congestion control mechanisms to work reliably.

Arranging the receivers into a ring [WKM94], where an "ACK-token" is passed around the ring, prevents the implosion problem for data 💍 However, ring creation and maintenance may itself be problematic. Also, if ring creation doesn't take network topology into account (which is difficult to achieve in practice), then the number of ACK packets crossing the network backbone for each data packet sent may increase O(n) with the number of receivers 📈

4.1.1. Tree-based ACK Mechanisms 🌳

Arranging the receivers into a tree [MWB+98, KCW98], where receivers generate ACKs to a parent node, which aggregates those ACKs to its parent in turn, is both more robust and more easily configured than a ring 🥰 The ACK-tree is typically only used for ACK-aggregation, and data packets are multicast from the sender to the receivers as normal. Trees are easier to construct than rings because more local information can be used in their construction. They can also be more fault tolerant than rings, because node failures only affect a subset of receivers, each of which can easily and locally decide to bypass its parent and report directly to the node one level higher in the tree. With good ACK-tree formation, tree-based ACK mechanisms have the potential to be one of the most scalable RM solutions 🚀

To be simple to deploy, tree-based protocols must be self-organizing: the receivers must form the tree themselves, using local information in a scalable manner 🐝 Such mechanisms are possible, but they aren't trivial. The main scaling limitations of tree-based protocols therefore come from the tree formation and maintenance mechanisms, rather than from the use of ACKs. Without such a scalable, automatic tree-formation mechanism, tree-based protocols must rely on manual configuration, which significantly limits their applicability (often to intranets) and, due to the complexity of configuration, their scalability 😵‍💫

Orthogonal to tree formation is the issue of subtree retransmission 🔁 With appropriate router mechanisms, or the use of multiple multicast groups, it's possible to let the intermediate tree nodes retransmit missing data to the nodes below them in the tree, rather than relying on the original sender to retransmit it. This relies on there being a good correlation, at the intermediate node, between the ACK tree and the actual data tree, as well as there being a mechanism to constrain the retransmission to the subtree. A good automatic tree formation mechanism combined with the use of administrative scoped multicast groups might provide such a solution. Without such tree formation mechanisms, subtree retransmission is difficult to deploy in large groups on the public Internet. This could also be solved by using transport-level router mechanisms to assist or perform retransmission, although existing router mechanisms [FLST98] support NACK-based rather than ACK-based protocols 🫠

Another important issue is the nature of the aggregation performed at interior nodes on the ACK-tree 🧠 Such nodes could:

  1. aggregate ACKs by sending a single ACK when all their children have ACKed,
  2. aggregate ACKs by listing all the children that have ACKed,
  3. send an aggregated ACK with a NACK-like exception list.

For data packets, option 1 is clearly more scalable and should be preferred 👑 However, if the sender needs to know exactly which receivers received the data, options 2 and 3 provide this information. Fortunately, there's usually no need to do this on a per-packet basis, but rather on a per-ADU basis 💅 Doing option 1 on a per-packet basis and option 3 on a per-ADU basis is the most scalable solution for applications that need this information, and it suffers virtually no disadvantage compared with the other solutions used on a per-packet basis 🎉

4.2. NACK-based mechanisms ✨

okay so instead of sending an ACK for every data packet a receiver gets, receivers can send a negative acknowledgment (NACK) for every data packet they realize they didn't get 🙈 and honestly this has some seriously iconic perks over ACK-based mechanisms 💅:

  • The sender no longer needs to know exactly how many receivers there are 🫶 which means the topology-building phase needed for ring- or tree-style ACK-based algorithms just... disappears 🧚
  • Fault-tolerance gets somewhat simpler because the receivers are the ones responsible for reliability 💜
  • Sender state can be significantly reduced, because the sender doesn't have to keep track of the receivers' state 🌸
  • Only a single NACK is needed from any receiver to flag a packet that's missing for any number of receivers. So NACK suppression is possible 🔥

the downsides though 😭: it's harder for the sender to know when it's safe to free its transmission buffers, and if the sender really needs to know that a particular receiver actually got all the data, you need additional session level mechanisms. BUT for lots of applications neither of these is an issue, so no stress 🎀

the vibe check: NACKs are great, just know what you're trading away 👑

4.2.1. NACK Suppression 🦋

ngl this is where the drama is. The key differences between NACK-based protocols come down to how NACK suppression gets done 💖 The goal is for only one NACK to reach the sender (or a node that can resend the missing data) as soon as possible after the loss is first noticed, and for only one copy of the missing data to be received by the nodes that need retransmission ✨

different mechanisms get close to hitting these goals in different ways, and here's the lineup 💅:

  • SRM [FJM95] uses random timers weighted by the round trip time between the sender and each node missing the data. It's effective, but it requires computing the RTT to each receiver before suppression works properly 🙈
  • NTE [HC97] uses a sender-triggered mechanism based on random keys and sliding masks. It doesn't need random timers and works for very large sessions 🌈 but it makes it difficult to provide the constant low-level stream of feedback needed to perform congestion control 😭
  • AAP [Ha99] uses exponentially distributed random timers and is effective for large sessions without needing to compute the RTT to each receiver 🍓
  • PGM [FLST98] and LMS [PPV98] use additional mechanisms in routers to suppress duplicate NACKs. In PGM's case, router assistance supplements SRM-style random timers and localizes the suppression, so the whole group doesn't have to get suppressed 🧚

the most general of these is probably exponentially weighted random timers 👑 Sure, SRM-style timers can reduce feedback delay, but they're harder to use correctly when not all the RTTs are known, or when the number of respondees is unknown 💀 Exponentially weighted random timers, on the other hand, work well across a large range of session sizes with good worst case delay characteristics ✨ main character energy, no cap 🦋

either form of random timer based mechanism can be supplemented by router support where it's available 🫶 Sender triggered NACK mechanisms (e.g. [HC97]) are more difficult to integrate with router-based support mechanisms 🙈

4.3. Replication 🌸

some RM protocols can be designed so they don't need explicit reliability mechanisms except in comparatively rare cases 🧚 An example is a multicast game, where the position of a moving object gets continuously multicast. That positional stream doesn't need extra reliability, because a new position superseding the old one will be sent before any retransmission could even happen 💖 However, when the moving object interacts with other objects or stops moving, an explicit reliability mechanism IS needed to reliably send the interaction information or last position 😭

and it's not just games that can be built this way! The NTE shared text editor [HC97] uses exactly this kind of mechanism for changes to a line of text. For every change, the whole line gets sent, so as long as the user keeps typing, no explicit reliability mechanism is needed ✨

the major advantage of replication is that it isn't susceptible to spatially uncorrelated packet loss 🦋 With a traditional ACK or NACK based protocol, the probability of any particular packet being received by all the receivers in a large group can be very low, and that leads to high retransmission rates 💀 Replicated streams, in contrast, don't suffer as the receiver group grows: different receivers lose different packets, but this doesn't increase network traffic 🎀

4.4. Packet-level Forward Error Correction 🔥

Forward Error Correction (FEC) is a well known technique for protecting data against corruption 💅 For reliable multicast it's most useful in the form of erasure codes 👑

the simplest form of packet-level FEC is to take a group of packets that's about to be sent and XOR the packets together to form a new packet, which also gets sent 🧚 So say there are three original packets plus the XOR packet. If a receiver is missing any one of the original data packets but gets the XOR packet, it can reproduce the missing original packet 🫶 iykyk, it's literally math magic ✨

more general erasure codes exist [BKKKLZ95], [Ri97], [LMSSS97] and they allow the generation of n encoding packets from k original data packets 🌈 In those cases, as long as at least k of the n encoding packets are received, the k original data packets can be reproduced 💜

to apply FEC, the sender groups data packets into rounds, and encoding packets are produced based on all the data packets in a round 🍓 A round might consist of all the data packets in an entire application data unit in some cases, while in other cases it might be a group of data packets that make up only a small portion of an application data unit 🦋

using erasure codes to repair packet loss is a significant improvement over simple retransmission, because the dependency on which packets have been lost is removed 🙌 So the amount of repair traffic needed to repair spatially uncorrelated packet loss is considerably lessened 💖

we can divide packet-level FEC schemes into two categories: proactive FEC and reactive FEC 🌸 The difference is that with proactive FEC, the sender decides a priori how many encoding packets to send for each round of data packets. With reactive FEC, the sender initially transmits only the original data packets for each round. Then it uses feedback from the receivers to compute how many packets were lost by the receiver that experienced the most loss in that round, and only that many additional encoding packets get sent for that round 🔥 Those encoding packets also serve to repair loss at the other receivers that are missing fewer packets ✨ The receivers report via ACKs or NACKs how many packets are missing from each round. With NACKs, only the receiver missing the most packets needs to send a NACK for that round, so this count is used to weight the random timers in the NACK calculation 🧚

proactive and reactive FEC can be combined 👑 For example, a certain amount of proactive FEC can be sent for each round, and if there are receivers that experience more loss than that can overcome for some rounds, they can request and receive additional encoding packets for those rounds 🫶

FEC is very effective at reducing repair traffic for packet loss 💅 However, it requires the data to be sent to be grouped into rounds, which can add to end-to-end latency 😭 For bulk-data applications this is typically not a problem, but it may be an issue for interactive applications, where replication may be a better solution 🙈

4.5. Layered FEC 🌈

an alternative use of packet level FEC is possible when data is spread across several multicast groups [RVC98], [BLMR98] 💖 In such cases, the original k data packets are used to generate n encoding packets, where n is much larger than k. The n encoded packets are then striped across multiple multicast groups 🦋 When a receiver wants to receive the original data, it joins one or more of the multicast groups and receives the encoding packets. Once it has received k different encoding packets, the receiver can leave all the multicast groups and reconstruct the original data 🍓

the primary importance of this layering is that it lets different receivers receive the traffic at different rates, according to the available capacity 👑 Such schemes don't require any form of feedback from the receivers to the sender to ensure good throughput, so the need for good throughput doesn't constrain the size of the receiver set 🔥 However, performing adequate network congestion control using receiver joins and leaves this way may require coordination between members that are behind the same congested link from the sender 😭 As described in the next section, [RVC98] suggests such a layered congestion control scheme ✨

5. Congestion Control Mechanisms ✨

okay so the Internet's basic delivery model is best-effort 🌸 which means nobody promises you any throughput, delay, or packet loss. end-systems are expected to be adaptive and slow their sending rate down to whatever fits the congestion state of the network. the Internet is slowly starting to support reserved bandwidth and differentiated service classes for specialist apps, but unless an end-system knows for sure that it has reserved bandwidth, it must still perform congestion control. no exceptions bestie 💅

broadly speaking, there are five classes of single-sender multicast congestion control solution 🦋

  • Sender-controlled, one group.

A single multicast group handles the data distribution, and feedback from the group members is used to control the rate of that group. the goal is to transmit at a rate set by the slowest receiver 🐢

  • Sender-controlled, multiple groups.

one initial multicast group gets adaptively split into multiple subgroups, and the splits are centered on congestion points in the network. application-level relays buffer data from a group closer to the original sender, then retransmit it at a slower rate into a group further away. this way, different receivers can receive the data at different rates. sender-based congestion control happens between the members of a subgroup and their relay ✨

  • Receiver-controlled, one group.

a single multicast group handles the data distribution. the receivers figure out whether the sender is transmitting too fast for the current congestion state of the network, and if it is, they leave the group 🏃‍♀️

  • Receiver-controlled, layered organization.

a layered approach for combining this scheme with a congestion control protocol that needs no receiver feedback is described in [RVC98]. the sender stripes data across multiple multicast groups at the same time. receivers join and leave these layered groups based on their measurements of the congestion state of the network, so the amount of data being received is always appropriate. BUT (and this is a big but 😭) this scheme relies on receivers joining and leaving the different multicast groups in a coordinated fashion behind a bottleneck link, and it has not yet been completely confirmed that this approach will scale in practice to the Internet. so more work on this congestion control mechanism would be beneficial 🧐

  • Router-based congestion control.

it is possible to add extra mechanisms to multicast routers to help with multicast congestion control. such mechanisms could include:

  • Conditional joins (a multicast join that specifies a loss rate above which it is acceptable for the router to reject the join).
  • Router filtering of traffic that exceeds a reasonable rate. this may include mechanisms for filtering traffic at different points in the network at different rates, depending on local congestion conditions [LVS99].
  • Fair queuing schemes combined with end-to-end adaptation.

router-based schemes generally need more state in network routers than has traditionally been acceptable for backbone routers. so in the near term, these schemes are only likely to be applicable for intranet solutions 🏢

for reliable multicast protocols, it is important to think about congestion control at the same time as reliability. the same mechanisms used to provide reliability will sometimes be used to provide congestion control too, so they're literally intertwined 🫶

in the case of receiver-based congestion control, open-loop delivery using FEC is the likely choice for getting good throughput for bulk-data transfer. this is because open-loop delivery requires no feedback from receivers, which makes it a perfect match for a receiver-based congestion control mechanism that operates without feedback from receivers 💜

6. Security Considerations 🔐

generally speaking, security considerations have relatively little effect on constraining the design space for reliable multicast protocols. the main issues constraining the design space are all related to receiver-set scaling. for authentication of the source and data integrity, receiver-set scaling is not a significant issue. however, for data encryption, key distribution, and especially re-keying, receiver-set scaling may be significantly affected. tree and graph based re-keying solutions[WHA98,WGL97] would appear to be appropriate solutions to these problems. it is not clear, however, that such re-keying solutions need to directly affect the design of the data distribution part of a reliable multicast protocol.

the primary question to consider for the security of reliable multicast protocols is the role of third parties. if nodes other than the original source of the data are allowed to send or resend data packets, then the security model for the protocol must take this into account. in particular, it must be clear whether such third parties are trusted or untrusted. a requirement for trusted third parties can make protocols difficult to deploy on the Internet 😬

untrusted third parties (such as receivers that retransmit the data) may be used so long as the data authentication mechanisms take this into account. typically this means that the original sender digitally signs and timestamps the data, and that the third parties resend this signed, timestamped payload unmodified 🔏

⚠️ unlike unicast protocols, denial-of-service attacks on multicast transport state are easy if the protocol design does not take such attacks into account. this is because any receiver can join the session and then produce feedback that influences the progress of a session involving many other receivers. so protection against denial-of-service attacks on reliable multicast protocols must be carefully considered. a receiver that requests retransmission of every packet, or that refuses to acknowledge packets in an ACK-based protocol, can potentially bring a reliable multicast session to a standstill. senders must have appropriate policy to deal with such conditions and, if necessary, evict the receiver from the group. a single receiver masquerading as a large number of receivers may still be an issue under such circumstances with protocols that support NACK-like functionality. providing unique "keys" to each NACKer when they first NACK, using a unicast response, might potentially prevent such attacks. 🚨

denial-of-service attacks caused by traffic flooding are, however, somewhat easier to protect against than with unicast. unwanted senders can simply be pruned from the distribution tree using the mechanisms implemented in IGMP v3[CDT99] 🌳

7. Conclusions 🎀

in this document we present an overview of the design space for reliable multicast within the context of one-to-many bulk-data transfer. other flavors of multicast application are not considered in this document, so the overview given should not be considered inclusive of the design space for protocols that fall outside one-to-many bulk-data transfer. during this overview, we reaffirmed that the process of designing a reliable multicast protocol is affected by a number of factors, which means a "one size fits all solution" is moot. these factors are then described to show how an application's needs constrain the set of available techniques that can be used to create a reliable multicast protocol. we also examined a number of basic techniques and showed how well they can meet the needs of certain types of applications 🧠

this document is meant to give guidance to the IETF community about standardizing reliable multicast protocols for bulk-data transfer. given how much application requirements constrain reliable multicast solutions, and the diverse set of applications that need support, it should be clear that any standardization work should take great pains to be future-proof 🔮. that seems to imply not standardizing complete reliable multicast transport protocols in one pass. instead, we should examine how separable such protocols are into functional building blocks, and standardize those blocks separately to the maximum degree that makes sense. this approach allows for protocol evolution, and lets applications with new constraints be supported with maximal reuse of existing, tested mechanisms 🧩

8. Acknowledgments 🫶

this document is an overview of the reliable multicast design space. the ideas presented are not the authors' own; they were collected from the varied presentations and discussions in the IRTF Reliable Multicast Research Group. there are too many to list here, but we thank everyone who took part in those discussions for their contributions 💖

9. Authors' Addresses 📮

Mark Handley
ATT Center for Internet Research at ICSI,
International Computer Science Institute,
1947 Center Street, Suite 600,
Berkeley, CA 94704, USA

EMail: mjh@aciri.org


Sally Floyd
ATT Center for Internet Research at ICSI,
International Computer Science Institute,
1947 Center Street, Suite 600,
Berkeley, CA 94704, USA

EMail: floyd@aciri.org


Brian Whetten
Talarian Corporation,
333 Distel Circle,
Los Altos, CA 94022, USA

EMail: whetten@talarian.com
Roger Kermode
Motorola Australian Research Centre
Level 3, 12 Lord St,
Botany  NSW  2019,
Australia

EMail: Roger.Kermode@motorola.com


Lorenzo Vicisano
Cisco Systems,
170 West Tasman Dr.
San Jose, CA 95134, USA

EMail: lorenzo@cisco.com


Michael Luby
Digital Fountain, Inc.
600 Alabama Street
San Francisco, CA  94110

EMail: luby@digitalfountain.com

10. References 📚

okay bestie, here's the reading list the authors used. every citation is listed in full so you can go find the originals 🔍

  • [BC94] K. Birman, T. Clark. "Performance of the Isis Distributed Computing Toolkit." Technical Report TR-94-1432, Dept. of Computer Science, Cornell University.
  • [BKKKLZ95] J. Bloemer, M. Kalfane, M. Karpinski, R. Karp, M. Luby, D. Zuckerman, "An XOR-based Erasure Resilient Coding Scheme", ICSI Technical Report No. TR-95-048, August 1995.
  • [BLMR98] J. Byers, M. Luby, M. Mitzenmacher, A. Rege, "A Digital Fountain Approach to Reliable Distribution of Bulk Data", Proc ACM SIGCOMM 98.
  • [CDT99] Cain, B., Deering, S., and A. Thyagarajan, "Internet Group Management Protocol, Version 3", Work in Progress.
  • [FLST98] Farinacci, D., Lin, S., Speakman, T. and A. Tweedly, "PGM reliable transport protocol specification", Work in Progress.
  • [FJM95] S. Floyd, V. Jacobson, S. McCanne, "A Reliable Multicast Framework for Light-weight Sessions and Application Level Framing", Proc ACM SIGCOMM 95, Aug 1995 pp. 342-356.
  • [Ha99] Handley, M., "Multicast address allocation protocol (AAP)", Work in Progress.
  • [HC97] M. Handley and J. Crowcroft, "Network text editor (NTE) a scalable shared text editor for MBone," ACM Computer Communication Review, vol. 27, pp. 197-208, Oct. 1997. ACM SIGCOMM'97, Sept. 1997.
  • [KCW98] Kadansky, M., Chiu, D. and J. Wesley, "Tree-based reliable multicast (TRAM)", Work in Progress.
  • [LMSSS97] M. Luby, M. Mitzenmacher, A. Shokrollahi, D. Spielman, V. Stemann, "Practical Loss-Resilient Codes", Proc ACM Symposium on Theory of Computing, 1997.
  • [MWB+98] Montgomery, T., Whetten, B., Basavaiah, M., Paul, S., Rastogi, N., Conlan, J. and T. Yeh, "THE RMTP-II PROTOCOL", Work in Progress.
  • [PPV98] C. Papadopoulos, G. Parulkar, and G. Varghese, "An error control scheme for large-scale multicast applications," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (San Francisco, California), p. 1188, March/April 1998.
  • [Ri97] L. Rizzo, "Effective erasure codes for reliable computer communication protocols," ACM Computer Communication Review, vol. 27, pp. 24-36, Apr. 1997.
  • [RV97] L. Rizzo, L. Vicisano, "A Reliable Multicast data Distribution Protocol based on software FEC techniques", Proc. of The Fourth IEEE Workshop on the Architecture and Implementation of High Performance Communication Systems (HPCS'97), Sani Beach, Chalkidiki, Greece June 23-25, 1997.
  • [RVC98] L. Rizzo, L. Vicisano, J. Crowcroft, "The RLC multicast congestion control algorithm", submitted to IEEE Network - special issue multicast.
  • [RMWT98] Robertson, K., Miller, K., White, M. and A. Tweedly, "StarBurst multicast file transfer protocol (MFTP) specification", Work in Progress.
  • [WHA98] Wallner, D., Hardler, E. and R. Agee, "Key Management for Multicast: Issues and Architectures", RFC 2627, June 1999.
  • [WKM94] Brian Whetten, Simon Kaplan, and Todd Montgomery, "A high performance totally ordered multicast protocol," research memorandum, Aug. 1994.
  • [WGL97] C.K. Wong, M. Gouda, S. Lam, "Secure Group Communications Using Key Graphs," Technical Report TR 97-23, Department of Computer Sciences, The University of Texas at Austin, July 1997.

Copyright (C) The Internet Society (2000). All Rights Reserved. 💖

You're allowed to copy this document and share it, and translations of it too. You can also write derivative works that comment on or explain it, or that help people implement it, and publish and distribute those in whole or in part with no restrictions at all. The one catch is that the copyright notice and this paragraph have to be included on every copy and every derivative work. ✨

What you can't do is modify this document itself in any way. That includes removing the copyright notice or the references to the Internet Society or other Internet organizations. The exceptions are when it's needed for developing Internet standards, in which case the copyright procedures defined in the Internet Standards process must be followed, or when it's being translated into languages other than English. 🌈

These permissions are perpetual, and the Internet Society or its successors or assigns won't revoke them. 🦋

This document and the information in it are provided on an "AS IS" basis, and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 💅

Acknowledgement 🫶

Funding for the RFC Editor function is currently provided by the Internet Society. 🎀

📦 where this page comes from