RFC 2102
Multicast Support for Nimrod : Requirements and Solution Approaches
RFC 2102: Multicast Support for Nimrod ✨
Okay bestie, this one is from February 1997 and it's a Network Working Group doc by R. Ramanathan at BBN Systems and Technologies. 🎀 It's Informational, which means it's sharing info for the Internet community. It is not a standard 💅. The title block doesn't list anything it obsoletes or updates, so there's no drama there 🦋.
Title: Multicast Support for Nimrod : Requirements and Solution Approaches Author: R. Ramanathan, BBN Systems and Technologies Category: Informational Date: February 1997
Status of this Memo 📜
This memo gives information to the Internet community. It does not specify an Internet standard of any kind 🙈. Distribution is unlimited, so share it with everyone 🌈.
Abstract 🔮
Nimrod doesn't pick one specific solution for multicasting. Instead, Nimrod can use any of a bunch of emerging multicast techniques 🧚. This doc lays out the requirements Nimrod has for a multicast support solution. It also compares existing approaches for multicasting inside an internetwork, including their pros and cons ⚖️. As an example, it outlines how Nimrod could support multicast using the scheme being developed in the IETF, the Protocol Indpendent Multicast (PIM) protocol 👑.
Table of Contents 📖
1 Introduction................................................. 2
2 Multicast vs Unicast......................................... 3
3 Goals and Requirements....................................... 4
4 Approaches................................................... 6
5 A Multicasting Scheme based on PIM........................... 10
5.1 Overview ................................................ 10
5.2 Joining and Leaving a Tree .............................. 12
5.2.1 An Example ........................................ 15
5.3 Establishing a Shared Tree .............................. 16
5.4 Switching to a Source-Rooted Shortest Path Tree.......... 18
5.5 Miscellaneous Issues..................................... 20
6 Security Considerations...................................... 21
7 Summary...................................................... 21
8 References................................................... 22
9 Acknowledgements............................................. 23
10 Author's Address............................................. 231. Introduction 💖
Okay so emerging apps like videoconferencing and remote classrooms are a whole vibe, and they make multicasting essential for any future routing architecture 🔥. Multicasting works by using a multicast delivery tree whose leaves are the multicast destinations 🌸.
Nimrod doesn't propose a solution for the multicasting problem, and there are two main reasons 💅. First, multicasting is a non-trivial problem, and its requirements still aren't well understood 🙈. Second, a bunch of groups (like the IDMR working group of the IETF) are already studying the problem on their own, so Nimrod isn't trying to duplicate that work 🫶.
This attitude toward multicasting is totally consistent with Nimrod's general philosophy of flexibility, adaptability, and incremental change ✨.
Multicasting solutions aren't part of Nimrod's "core" architecture, but Nimrod does require that the solution have certain characteristics 🦋. This document talks through some of those requirements and evaluates approaches for meeting them 🍓.
Here's how it's organized 🗺️. Section 2 explains why multicasting is treated a little differently than unicast, even though multicast is basically a generalization of unicast 🧠. Section 4 covers current approaches to multicasting 🌈. Section 5 gives an example of how Nimrod multicasting could be done using PIM [DEF+94a] 💜. If you don't have time to read the whole thing, there's a summary at the end ⭐.
This doc uses lots of terms and concepts from the Nimrod Architecture document [CCS96], and some terms and concepts in section 5 come from the Nimrod Functionality document [RS96] 🎀. Most of the discussion assumes you've read at least the Nimrod Architecture document [CCS96] 📚.
2. Multicast vs Unicast 🦄
Let's compare unicast routing and multicast routing 👯♀️. Both need two phases: route generation and packet forwarding 🧚. With unicast routing, Nimrod specifies the modes of packet forwarding, but route generation itself isn't specified and is left to the particular routing agent 💅. For multicasting, Nimrod leaves both route generation and packet forwarding mechanisms unspecified 🙈. To explain why, here are three aspects that make multicasting totally different from unicasting 👑:
- Groups and group dynamism. In multicasting, the destinations are part of a group, and that group's membership is dynamic 🌊. This brings up the following issues:
- An association between the multicast group and the EIDs and locators of the members in that group 🔗. This is especially relevant for sender-initiated multicasting and policy support 💌.
- A mechanism to fold new group members into the delivery when they get added, and a mechanism to "prune" the delivery when members leave 🌿.
- State creation. Most multicasting solutions can basically be viewed as creating state in routers for multicast packet forwarding 🏗️. Depending on who creates the state, multicasting solutions are different 🍭. There are several options here, like the sender, the receivers, or the intermediate routers 🛸.
- Route generation. Even more than in unicast routing, you can pick from a rich spectrum of heuristics, each with different tradeoffs across parameters like cost, delay, algorithmic time complexity, and optimality 🧮. For example, some heuristics make a low-cost tree with high end-to-end delay, and some make trees that give the shortest path to each destination but cost more 💸. Multicasting heuristics are a big research area right now, and we expect advances to lead to sophisticated heuristics in the near future 🔭.
Okay so there are lots of possible combinations of route generation, group dynamism handling, and state creation for a solution, and each one could be the best fit for different applications 🌈. That's why Nimrod doesn't specify one particular approach to multicasting 🙌. Every implementation of Nimrod is free to use its own multicasting technique, as long as it meets the goals and requirements of Nimrod 🦋. However, for interoperability, certain things must be agreed upon, like the structure of the forwarding information database that they create (we talk about this more in section 4) 🤝.
So we won't go into the details of any multicast solution here, just its requirements in the context of Nimrod 💫. For the rest of this document, the discussion is structured around two themes 🎀:
- What goals do we want to meet when providing multicasting in Nimrod, and what specific requirements do those goals imply for the multicast solution? 🎯
- What are some of the approaches to multicasting being discussed right now, and how relevant is each one to Nimrod? 🔍
To be continued, bestie! 🧚💜
4. Approaches ✨
okay bestie, here's the rundown of the multicasting approaches that are running right now or that the IETF is still cooking up 🍓
- Distance vector multicast routing protocol (DVMRP)[DC90]. This one is built on distance-vector routing info distribution and hop-by-hop forwarding. It uses Reverse Path Forwarding (RPF)[DM78], which is a distributed algorithm for constructing an internetwork broadcast tree 🌳. DVMRP uses a modified RPF algorithm, basically a truncated broadcast tree, to build a reverse shortest path sender-based multicast delivery tree. A reverse shortest path from s to d is a path that uses the same intermediate nodes as the shortest path from d to s. (If the paths are symmetric, meaning they cost the same in either direction, the reverse shortest path is the same as the shortest path.) RPF is already out in the wild on the Internet in what people call the MBONE 🌸. An improvement is being rolled out too. It adds "prune" messages to truncate even more of the routers that aren't on the path to the destinations, plus "graft" messages to undo that truncation later if it's needed.
The big win here is that it's simple 💅. The major handicap is scalability 😭. Two issues have been raised about it[BFC93]. First, if S is the number of active sources and G is the number of groups, the state overhead is O(GS), which might be unacceptable when resources are limited. Second, routers that aren't on a multicast tree still get involved (sending and tracking prune and graft messages) even when they aren't interested in that particular source-group pair. It's expected to perform relatively poorly on large networks where group membership is sparsely distributed. On top of that, there's no support for policies or QOS 💀.
- Core Based Trees (CBT)[BFC93]. This scheme uses a single tree shared by all sources per group. The tree has a single router as its core (with additional routers for robustness), and branches come out from that core 🎀. The chief thing that makes CBT special is that it's receiver initiated. That means receivers who want to join a multicast group find the tree (or its core) and attach themselves to it, with no participation from the sources. Main character energy 👑.
The big motivation here is cutting the state overhead down to O(G), compared to DVMRP and PIM (more on that below) ✨. Also, only the routers on the path between the core and the potential members get involved. Core-based tree formation and packet flow are decoupled from the underlying unicast routing.
The main disadvantage is that packets no longer travel the shortest path from the source to their destinations 🙈. How well it performs generally depends on carefully placing the cores and on coordination between them. Traffic concentration on links incident to the core is another problem. It also depends on network entities (in other administrative domains, for instance) for resource reservation and policy routing.
- Protocol Independent Multicasting (PIM)[DEFJ93]. Yet another approach built on the receiver initiated philosophy 🦋. It's designed to get the advantages of DVMRP and CBT. It uses a "rendezvous point," which is a lot like the core we just talked about, and it allows shared trees and source-specific multicast trees to exist at the same time 🧚. In the steady state, data can be delivered either over the reverse shortest path from the sender to the receiver (for better end-to-end delay) or over the shared tree.
It has two modes of operation, sparse and dense, so it gives improved performance both when group membership in an internetwork is sparse and when it's dense 🌈. It is, however, a complex protocol 😵💫. One limitation of PIM is that its shortest paths are based on the reverse metrics, so they're only truly "shortest" when the links are symmetric.
- Multicast Open Shortest Path First (MOSPF)[Moy92]. Unlike the approaches above, this one is based on link-state routing information distribution. The packet forwarding mechanism is hop-by-hop. Since every router has complete topology information, every router computes the shortest path multicast tree from any source to any group using Dijkstra's algorithm. If the router doing the computation falls within the tree it computed, it can figure out which links it has to forward copies onto 🧠.
MOSPF inherits the advantages of OSPF and link-state distribution, namely localized route computation (and easy verification of loop-freedom), fast convergence to link-state changes, and so on 🔥. However, group membership information gets sent throughout the network, including over links that aren't on the direct path to the multicast destinations. So, like DVMRP, this is most suitable for small internetworks, meaning as an intra-domain routing mechanism 🍓.
- Inter-Domain Policy Routing (IDPR)[Ste]. This approach uses link-state routing information distribution like MOSPF, but it uses source-specified packet forwarding 💜. Using the link-state database, the source generates a policy multicast route to the destinations. With that route, the IDPR path-setup procedure sets up state in intermediate entities for packet duplication and forwarding. That state holds info about the next-hop entities for the multicast flow. When a data packet arrives, it gets forwarded to each next-hop entity obtained from the state.
The perks of this approach are that it's great at supporting policy-based multicast routing with ease, and it gives independence (flexibility) in the choice of multicasting algorithm used at the source 🫶. IDPR also allows resource sharing over multiple multicast trees. The major disadvantage is that group membership changes (additions and deletions) are relatively harder to handle, since those changes have to be communicated to the source of the tree first, and then the source adds branches appropriately 😩.
We're about to talk about how all of these fit with Nimrod 🌟. Everything described here has one thing in common: we need to set up state in the intermediate routers for multicast packet forwarding. The approaches mainly differ on who starts the state creation. Is it the sender (like IDPR and PIM), the receiver (like CBT and PIM), or do the routers create state themselves without being kicked off by the sender or receivers (like DVMRP and MOSPF)? 🤔
Nimrod should be able to handle both sender initiated and receiver initiated state creation for multicasting 💖. In the rest of this section, we'll go over the pros and cons of these approaches for Nimrod.
Nimrod uses link-state routing information distribution (topology maps) and has four modes of packet forwarding: flow mode, Connectivity Specification Chain (CSC) mode, Connectivity Specification Sequence (CSS) mode, and datagram mode [CCS96] ✨.
An approach similar to the one used in IDPR is viable for multicasting in flow mode. The source can set up state in intermediate routers, which can then duplicate packets appropriately 🦋. For the CSC, BTES and datagram modes, an approach similar to the one used in MOSPF is applicable. In these situations, the advantages and disadvantages of these approaches in the context of Nimrod are similar to the advantages and disadvantages of IDPR and MOSPF, respectively 🎀.
Sender based trees can be set up using an approach similar to IDPR, generalized to an "n" level hierarchy 🌈. A significant advantage of this approach is policy-based routing. The source knows about the policies of nodes that choose to advertise them, and it can choose a route the way it wants. It doesn't have to depend on other entities to pick the route, unlike some of the schemes mentioned above 👑. Another advantage is that each source can use the multicast route generation algorithm and packet forwarding scheme that suits it best, instead of being forced to use whatever is implemented elsewhere in the network 💅. On top of that, this approach allows new multicast tree generation algorithms to be deployed incrementally as research in that area progresses 🧚.
CBT-like methods may be used to set up receiver initiated trees. Nimrod provides link-state maps for generating routes, and a CBT-like method is compatible with that 🗺️. For instance, a receiver that wants to join a group may generate a (policy) route to the core for that group using its link-state map, and then attach itself to the tree 🫶.
A disadvantage of sender based methods in general seems to be supporting group dynamism 😬. Specifically, if the group's membership changes, the particular database containing the group-destination mapping has to be updated. By comparison, receiver oriented approaches seem to accommodate group dynamism more naturally 💜.
Nimrod doesn't rule out multiple approaches to multicasting existing at the same time, or switching from one to another depending on how group distributions are changing 🔄. Interoperability is an issue, meaning the question of whether or not different implementations of Nimrod can take part in the same tree. But as long as the structure of the state created is agreed on (so the states can be interpreted uniformly for packet forwarding), this shouldn't be a problem 🌸. For instance, a receiver that wants to join a sender created tree might set up state on a path between itself and a router on the tree, with the sender itself being unaware of it. Packets entering the router would now also be forwarded along this new "branch" to the new receiver 🌿.
In conclusion, the architecture of Nimrod can accommodate diverse approaches to multicasting 🌈. Each approach has its disadvantages with respect to the requirements mentioned in the previous section. The architecture doesn't demand that one particular solution be used. In fact, we expect that a combination of approaches will be employed and engineered in whatever way is most appropriate to the requirements of the particular application or subscriber 💖.
5. A Multicasting Scheme based on PIM 💜
The Inter-Domain Multicast Routing (IDMR) working group of the IETF has developed a specification for a new multicast scheme, namely Protocol Independent Multicasting (PIM), for use in the Internet [DEF+94a, DEF+94b] 🌐. In this section, we describe how the schemes mentioned therein may be implemented using the facilities provided by Nimrod.
We note that the path setup facility provided in Nimrod makes it very conducive to PIM-style multicasting. Despite the length of the description given here, we assure the reader that it's quite simple to implement PIM style multicasting in Nimrod 🫶✨.
Before reading this section, we recommend that the reader acquire some familiarity with PIM (see [DEF+94a, DEF+94b]) 📚.
5.1. Overview ✨
okay so PIM is giving receiver-initiated membership 🎀 which is the classic IP multicast vibe, and the best part is it doesn't care which unicast routing protocol you use (hence the name!) 💅
PIM is lowkey iconic because it can build two kinds of trees 🌳. One is a shared tree, great for low "cost" multicasting, and the other is a source-based tree, great for low delay multicasting 💖
A shared tree is rooted at a rendezvous point (RP), which is usually a prespecified router for the multicast group in question 🧚 To set one up, the designated router (DR) for a host that wants to join group G starts a flow setup from the RP for G to that DR. Meanwhile, a source S that wants to send to group G starts a flow setup between S and the RP for G. Once both flow setups wrap up, packets can go from S to H through the RP 🦋 For how the flow setup protocol actually works, check out [DEF+94b] 📚
After the shared tree is set up, a recipient for group G can choose to switch over to a source-based shortest path tree 👑 In this tree, packets go from the source to each recipient along the shortest path, no detours! To build it, the DR for H looks at the source S of the packets it's getting over the shared tree and sets up a flow between S and the DR. The flow follows the shortest path from the DR to S, so strictly speaking it's the reverse shortest path being used 🙈 After that, packets can go from S to H on that shortest path and skip the RP entirely ✨ For the protocol details on source-based trees in PIM, see [DEF+94b] again 💜
When a host wants to leave a multicast group, its DR sends a prune message toward the source (for source-based trees) or toward the RP (for shared trees) 🍓 For more on this and the other PIM features, see [DEF+94b] 🫶
Now, how PIM works in Nimrod 🌈 We call PIM-based multicast Nimpim. To join a shared tree, an endpoint (or an agent acting for the endpoint) that wants to join group G queries the association database for the EID and locator of the RP for G. For well-known groups, that association might just be configured already 💅 Every multicast group G is required to have such an association maintained. The endpoint then gets a route for the RP and starts a multicast flow setup to the RP. A multicast flow setup is basically like the unicast flow setup in [CCS96], with one big twist: when a multicast flow setup request hits a node that already has that flow, the request doesn't get forwarded any further. Instead, the new flow gets "spliced" in as a new branch of the existing multicast tree 🌸 The source does the same thing and sets up a flow to the RP. The RP then creates state that links these two flows together, and now packets can flow from the source to the endpoints 🎉 Each flow setup can be "hierarchical" and involve lots of subflows, but honestly that's all transparent to Nimpim 🙈 For the details on managing hierarchical flows, see [CCS96] 🎀
To create the source-based tree, the representative for a recipient node N grabs the EID or locator of the source from the data packets and starts a multicast flow setup to the source 🦋 The route agent for node N uses its map to calculate the shortest path from the source to N, and the flow request travels along the reverse of that path 🧠 Here's the tea: how "short" the path is depends on how much routing information is available locally. But since the map is available locally, you can actually find the real shortest path from the source to N, instead of just using the shortest path from N to S. So with Nimrod you can fix a PIM shortcoming pretty easily 💖 slay honestly 👑
We'll now go deeper into Nimpim 🧚 First up is multicast flow setup, which is the "basic" stuff you need to make multicasting work. Once this "building block" is clear, we'll use it to explain how the shared tree gets set up (in section 5.3) and how the source-based tree gets set up (in section 5.4) ✨
We only talk about sparse-mode multicasting here, as described in [DEF+94a] 🌿 To keep things simple, we assume there's a single Rendezvous Point per group 💜 And to keep things concise, we "address" every entity by its EID alone. Locators could be used alongside EIDs to cut down on database lookup overhead, but we're not doing that here 🫶
5.2. Joining and Leaving a Tree 🦋
Nimpim uses two control packets to set up a flow: the Nimrod Multicast Flow-Request packet (NMFReq) and the Nimrod Multicast Flow-Reply packet (NMFRep) 💅
The NMFReq packet is a control packet that gets identified by a prespecified "payload type" 🎀 Its protocol-specific part includes the following fields. Heads up: every field except the Code field is also present in the Unicast Flow-Request packet 🙈
- S-EID: The EID of the initiator of the flow.
- T-EID: The EID of the target of the flow.
- Flow-id: A label denoting the flow.
- Direction: The direction of the flow, whether from the initiator to the target (FORW), from the target to the initiator (REVERSE), or both (BOTH).
- Code: Denotes whether the packet is for joining a flow (NMFReq-Join) or for leaving a flow (NMFReq-Prune) 🍓
- Source Route: A sequence of node locators the packet must travel through 🧚
Processing an NMFReq at a forwarding agent on node N is pretty similar to processing a unicast flow request (see [CCS96]). The difference is that the new flow can now "splice" onto an existing delivery tree, or "un-splice" from one 🌈 Specifically:
- If the Code is NMFReq-Join, the forwarding agent for node N runs the algorithm shown in Figure 1.
- If the Code is NMFReq-Prune, the forwarding agent at node N runs the algorithm shown in Figure 2.
The NMFRep packet is used to accept or reject an NMFReq-Join or NMFReq-Prune 🫶 Its packet format is the same as the one for a unicast flow request. But the NMFRep packet is generated by the first node N that grafts the new flow onto the existing tree, which might not be the same as the target of the NMFReq 👑
It is required that a leaf router keep track of all hosts currently joined to the group, and send a prune message only if there's no host in the local network for the group 💖
The NMFReq and NMFRep exchanges make up a procedure for joining a multicast delivery tree (when the Code is Join) and for leaving one (when the Code is Prune) ✨ We call these procedures Tree-Join and Tree-Leave respectively, and we'll use them as "building-blocks" for building shared trees (section 5.3) and source-based trees (section 5.4) 🦋
begin
if the flow-id F in NMFReq-Join is in flow-list then
if T-EID in NMFReq-Join = target in flow state for F then
if Direction in NMFReq-Join is REVERSE or BOTH then
Add the node preceding N in source route to child list for F
else
discard packet
else
discard packet
else
begin
install state for F in N, i.e.,
assign parent(F) = node succeeding N in source route
assign child(F) = node preceeding N in source route
assign target(F) = T-EID in NMFReq-Join
forward NMFReq-Join to parent(F)
end
end.Figure 1: Algorithm executed by a forwarding agent for node N when when it receives an NMFReq-Join. 🌸
begin
if the flow-id F in NMFReq-Prune is in flow-list
then begin
delete previous hop in source route from child list for F, if exists
if child list for F is empty
then begin
delete the flow-id and state associated with it
forward to next hop in source route
end
else discard packet
end
else forward to next hop in source-route
end.Figure 2: Algorithm executed by a forwarding agent for node N when it receives an NMFReq-Prune. 💅
5.2.1. An Example 🧚
Let's see how a tree gets joined with the help of Figure 3 🎀 In the figure, the bold lines show an existing tree. A representative R, acting on behalf of host H, joins the tree by sending an NMFJoin-Req toward a target T. When used in shared tree mode, the target is the RP. When used in source tree mode, it's the source (root) of the multicast tree 🌳 Say a host H wants to join the multicast tree. These steps happen:
Step 1. A representative R of H queries the route agent for a route from T to R. It gets the route T - C - B - A - R. It builds an NMFJoin-Req packet with source route R, A, B, C, T and flow F, and forwards it to A. 📦
Step 2. A looks for flow F in its installed flow database and doesn't find it. It installs state for F (it makes R a child and B a parent in the multicast tree) and sends the NMFJoin-Req packet to B 🦋
Step 3. B looks for flow F in its installed flow database and finds it. It adds B to its child list, builds an NMFJoin-Rep packet, and sends it to A 🫶
Step 4. A forwards the packet to R, and the tree joining is complete 🎉 Branch B-A-R is now added to the tree 🔥
5.3. Establishing a Shared Tree 🌈
There are two parts to setting up a shared tree 💖 First is the receiver-to-RP communication, where the receiver joins the delivery tree rooted at the RP. Second is the sender-to-RP communication, where the RP joins the delivery tree rooted at the sender ✨
T
+---+
| |\
+---+ \
/ \
/ \
C / \ X
+---+ +---+
| | | |
+---+ +---+
\
\
\
R join-req join-req \ B
+---+ - - - - -> +---+ - - - - -> +---+
| |<------------| |<-----------| |
+---+ join-rep +---+ join-rep +---+
| A \
| \
| \ Y
( ) +---+
H | |
+---+Figure 3: Illustration for the example describing joining an existing
multicast tree. 🌳✨
Receiver-RP Communications: Okay so when an endpoint wants to join multicast group G, its endpoint representative goes and grabs the Rendezvous Point EID for G 🎀. We're assuming the association database already has that mapping, obviously. For how that database query actually gets implemented, go check [CCS96] 📚.
The representative also grabs the flow-id it's going to use for the flow 💅. The flow-id is built as the tuple (RP-EID, G) or some equivalent thing. The flow-id has to be unique to that particular multicast flow, no cap 🔒. And honestly, this isn't the only way to get a flow-id, or even the best way 🙈. We talk about other ways to get one in section 5.5 🦋.
Next, the representative starts a Tree-Join procedure 🚀.
The NMFReq packet fields look like this:
S-EID: The EID of the endpoint that wants to join.T-EID: The RP EID (grabbed from the Association Database).Flow-id: The flow-id for this group (grabbed the way we just talked about).Direction:REVERSE(from the RP to the receiving endpoint).Code:Join.Source Route: The reverse of the route the map agent gives back for a query "from RP-EID to Receiver-EID".
At the first node that already has this Flow-id, or at the RP, an NMFRep packet gets generated 💖. The S-EID, T-EID, Direction and Flow-id fields get copied over from the NMFReq packet, and the Code gets set to Join-Accept or Join-Refuse, whichever one fits the situation 👑. The source route gets reversed from the NMFReq packet too.
Sender-RP Communications: When an endpoint wants to send to multicast group G, the endpoint representative grabs the Rendezvous Point EID for G 💜. Same deal here: we assume the association database has that mapping, and [CCS96] has the details on how that query is implemented 🧚.
The representative also gets the flow-id for the flow 🍓. This time the flow-id is built as the tuple (Sender-EID, G) or an equivalent thereof. Again, it has to be unique to that particular multicast flow, and this isn't the only method or the best method for getting one. Alternate methods are in section 5.5 ✨.
Then the representative sends an RP-Register Message to the RP 📨. This register message is equivalent to the PIM-Register described in [DEF+94b] 🌈. The RP-Register message carries the group G, the flow-id (gotten the way we just talked about), and the sender EID.
The RP then starts a Tree-Join with the Sender EID as the target 🎯. The NMFReq fields are:
S-EID:RP-EID.T-EID: Sender EID (copied from the RP-Register Message).Flow-id: The flow-id field from the RP-Register Message.Code:Join.Direction:REVERSE.Source Route: The reverse of the route the map agent gives back for the query "from Sender-EID to RP-EID".
The NMFRep fields are obvious 🙄.
Shared Tree Data Forwarding: Packets sent from the source for group G carry the Flow-id that the senders and receivers use to set up the delivery tree 🔥. The packets from the sender go to the RP, where they get multicast using the state made for the flow, into the delivery tree rooted at the RP, out to every receiver that did a Tree-Join 💅✨.
5.4 Switching to a Source-Rooted Shortest Path Tree 🌊
Switching to a Source-Rooted Shortest Path Tree has two parts 🧩. First there's the receiver-source communications, where the receiver joins a multicast delivery tree rooted at the source. Second there's the receiver-RP communications, where the receiver leaves the shared tree 👋.
Receiver-Source Communications: An endpoint E that's receiving packets through the shared tree from source S gets the option to switch to a delivery tree rooted at the source 🦋. That way, packets from S to E take the shortest path (using whatever metric you like) 🏃♀️.
The endpoint representative of E grabs the flow-id it'll use for the flow 💖. The flow-id is built the same way as the tuple (Source-EID, G). Again, it has to be unique to that particular multicast flow, and this isn't the only method or the best method for getting a flow-id. Alternate methods are in section 5.5 🫶.
The representative for E starts a Tree-Join toward S, with NMFReq fields like this:
S-EID: EID of the EndpointE.T-EID: EID of the source.Flow-id: Flow id for the multicast (grabbed as mentioned above).Code:Join.Direction:REVERSE.Source Route: To get the route, the route agent gets queried for a shortest path route (based on the chosen metric, which is typically the delay) from the source to the endpoint 🗺️. The quality of that route is limited by how much routing information the route agent has, directly or indirectly ⚠️. The Source Route is the reverse of the route that comes back.
Here's a comment on how the shortest-path trees from the RPF tree (as in [DEF+94b, DC90]) differ from the trees we get here 🤓. With the RPF scheme, packets from the source S to the endpoint E follow the shortest path from E to S. That's only the desired path if the path is symmetric in both directions 🙃. But in the Nimrod mechanism described here, packets follow the "actual" shortest path from S to E, symmetric or not 💅✨.
The NMFRep fields are obvious 🙄.
Receiver-RP Communications: Once the receiver has joined the source-rooted tree, it can optionally disassociate itself from the shared tree 👋. To do that, it starts a Tree-Leave procedure 🚪.
The representative sends an NMFReq packet toward the RP with these fields:
S-EID: The EID of the endpoint that wants to leave the shared tree.T-EID: The RP-EID.Flow-id: The flow-id it used to join the shared tree.Code:Prune.Direction:REVERSE.Source Route: Obtained the same way as for the Tree-Join.
The prune packet gets processed by the intermediate forwarding agents, as described in section 5.2 🧹. When the receiver gets the NMFRep packet back, it has left the shared tree 🎉.
Source Tree Data Forwarding: Packets from the source carry the flow-id that was used to join the source tree for a given multicast group 📦. Forwarding agents just use the state made by the Tree-Join procedure to duplicate and forward packets toward the receivers 🪞.
5.5 Miscellaneous Issues 🎀
Obtaining the Flow-Id: In the scheme above, the flow-id for a multicast group G was made by combining the RP-EID and the group set-id (G-SID) (for a shared tree), or by combining the Source-EID and the G-SID (for a source-based tree) 🧃. The downside is that the bit-length of EID/SID can be pretty high (more than 64 bits), so the flow-id could end up super long 😭. There are bit-based data structures and search algorithms, like Patricia Trees, that can be used for an efficient implementation 🌿. Still, it's worth considering some other methods instead of combining EID/SID. Here are some we describe below ✨:
- For shared trees, the flow-id for a particular group
Gmay be stored and updated in the association database. Since we have to use the association database anyway to get the RP-EID, this doesn't cause much extra burden 💅.
However, this can't be used efficiently for source-based trees, because we'd need a flow-id for every combination of Source and Group 🙅♀️.
- The flow-id for shared trees could be done as above. When the sender does an RP-Register, it could send the RP the flow-id it wants receivers to use when they switch to a source-based tree 💌. That could be included in the RP-Register message. The RP could then multicast that flow-id to all receivers in a special packet 📣. When the receivers want to switch, they use that flow-id 🦋.
This needs the definition of the "special" packet 🛠️.
- The flow-id only gets handed out by the source (for source-based trees) or the RP (for shared trees) 👑. The receivers use a "dummy" flow-id in the NMFReq when doing a Tree-Join 🎭. The correct flow-id to use gets returned in the NMFRep message generated by the forwarding agent where the new branch meets the existing tree 🌸. Forwarding agents on the path of the NMFRep packet update the state information by rewriting the dummy flow-id with the correct flow-id from the NMFRep packet 🔁.
This needs a redefinition of the NMFRep packet. Note that the NMFRep packet now needs space for two flow-ids: one for the "dummy" flow-id, and one for the "correct" flow-id that has to replace the dummy flow-id 🧠.
We claim that each of the schemes above gets the flow-id synchronized across the various parts of the internetwork, and that each flow-id is unique to the multicast delivery tree 🤞. A formal proof of these claims is beyond the scope of this document 📝.
Dense Mode Multicast: The PIM architecture [DEF+94a] includes a multicast protocol for when group membership is densely distributed across the internetwork 🌐. In this mode, no Rendezvous Points are used, and a source-rooted tree is formed based on Reverse Path Forwarding, similar to DVMRP [DC90] 🌳.
We don't give the details of how Nimrod can implement Dense Mode Multicast here 🤐.
Multiple RPs: Our discussion above assumed there's one RP per group. PIM allows more than one RP per group, but we don't discuss multiple-RP PIM here 🙈.
6 Security Considerations 🔐
Security issues are not discussed in this memo. 😱
7 Summary 📝
- Nimrod does not specify a particular multicast route generation algorithm or state creation procedure. Nimrod can accommodate diverse multicast techniques and leaves the choice of technique to the particular instantiation of Nimrod 🌈.
- A solution for multicasting within Nimrod should be capable of:
- Scaling to large networks, large numbers of multicast groups, and large multicast groups 📈.
- Supporting policy, including quality of service and access restrictions 🛡️.
- Resource sharing 🤝.
- Interoperability with other solutions 🔗.
- Multicasting typically requires setting up state in intermediate routers for packet forwarding. The state setup may be initiated by the sender (e.g., IDPR), by the receiver (e.g., CBT), by both (e.g., PIM), or by neither. The architecture of Nimrod provides sufficient flexibility to accommodate any of these approaches 🦋.
- A receiver-initiated multicast protocol, PIM, is being designed by the IDMR working group of the IETF. The facilities provided by Nimrod make using PIM as a multicast protocol quite straightforward 👑✨.
8 References 📚
[BFC93] A. J. Ballardie, P. F. Francis, and J. Crowcroft. Core based trees. In Proceedings of ACM SIGCOMM, 1993.
[CCS96] Castineyra, I., Chiappa, N., and M. Steenstrup, "The Nimrod Routing Architecture", RFC 1992, August 1996.
[DC90] S. Deering and D. Cheriton. Multicast routing in datagram internetworks and extended lans. ACM Transactions on Computer Systems, pages 85--111, May 1990.
[DEF+94a] Deering, S., Estrin, D., Farinacci, D., Jacobson, V., Liu, C., and L. Wei, "Protocol Independent Multicast (PIM) : Motivation and Architecture, Work in Progress. 💜
[DEF+94b] Deering, S., Estrin, D., Farinacci, D., Jacobson, V., Liu, C., and L. Wei, "Protocol Independent Multicast (PIM) : Sparse Mode Protocol Specification, Work in Progress.
[DEFJ93] Deering, S., Estrin, D., Farinacci, D., and V. Jacobson, "IGMP router extensions for routing to sparse multicast groups, Work in Progress.
[DM78] Y. K. Dalal and R. M. Metcalfe. Reverse path forwarding of broadcast packets. Communications of the ACM, 21(12), pages 1040--1048, 1978.
[Moy92] Moy, J., "Multicast Extensions to OSPF, RFC 1584, March 1994.
[RS96] Ramanathan, S., and M. Steenstrup, "Nimrod functional and protocol specifications, Work in Progress.
[Ste] Steenstrup, M., "Inter-domain policy routing protocol specification: Version 2", Work in Progress.
9. Acknowledgements 🙌
Huge thank-yous to Isidro Castineyra (BBN), Charles Lynn (BBN), Martha Steenstrup (BBN) and the rest of the Nimrod Working Group 🫶 for their comments and suggestions on this memo. Iconic team behavior, honestly 💜
10. Author's Address 💌
Ram Ramanathan
BBN Systems and Technologies
10 Moulton Street
Cambridge, MA 02138
Phone: (617) 873-2736
EMail: ramanath@bbn.com📦 where this page comes from
- ietf: rfc2102 1997-02
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms