diff options
Diffstat (limited to 'doc/rfc/rfc2102.txt')
| -rw-r--r-- | doc/rfc/rfc2102.txt | 1291 |
1 files changed, 1291 insertions, 0 deletions
diff --git a/doc/rfc/rfc2102.txt b/doc/rfc/rfc2102.txt new file mode 100644 index 0000000..915df6f --- /dev/null +++ b/doc/rfc/rfc2102.txt @@ -0,0 +1,1291 @@ + + + + + + +Network Working Group R. Ramanathan +Request for Comments: 2102 BBN Systems and Technologies +Category: Informational February 1997 + + + Multicast Support for Nimrod : Requirements and Solution Approaches + + +Status of this Memo + + This memo provides information for the Internet community. This memo + does not specify an Internet standard of any kind. Distribution of + this memo is unlimited. + +Abstract + + Nimrod does not specify a particular solution for multicasting. + Rather, Nimrod may use any of a number of emerging multicast + techniques. We identify the requirements that Nimrod has of a + solution for multicast support. We compare existing approaches for + multicasting within an internetwork and discuss their advantages and + disadvantages. Finally, as an example, we outline the mechanisms to + support multicast in Nimrod using the scheme currently being + developed within the IETF - namely, 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............................................. 23 + + + + + + + +Ramanathan Informational [Page 1] + +RFC 2102 Nimrod Multicast Support February 1997 + + +1 Introduction + + The nature of emerging applications such as videoconferencing, remote + classroom, etc. makes the support for multicasting essential for any + future routing architecture. Multicasting is performed by using a + multicast delivery tree whose leaves are the multicast destinations. + + Nimrod does not propose a solution for the multicasting problem. + There are two chief reasons for this. First, multicasting is a non- + trivial problem whose requirements are still not well understood. + Second, a number of groups (for instance the IDMR working group of + the IETF) are studying the problem by itself and it is not our + intention to duplicate those efforts. + + This attitude towards multicasting is consistent with Nimrod's + general philosophy of flexibility, adaptability and incremental + change. + + While a multicasting solution per se is not part of the "core" Nimrod + architecture, Nimrod does require that the solution have certain + characteristics. It is the purpose of this document to discuss some + of these requirements and evaluate approaches towards meeting them. + + This document is organized as follows. In section 2 we discuss why + multicasting is treated a little differently than unicast despite the + fact that the former is essentially a generalization of the latter. + Following that, in section 4 we discuss current approaches toward + multicasting . In section 5, we give an example of how Nimrod + multicasting may be done using PIM [DEF+94a]. For readers who do not + have the time to go through the entire document, a summary is given + at the end. + + This document uses many terms and concepts from the Nimrod + Architecture document [CCS96] and some terms and concepts (in section + 5) from the Nimrod Functionality document [RS96]. Much of the + discussion assumes that you have read at least the Nimrod + Architecture document [CCS96]. + + + + + + + + + + + + + + +Ramanathan Informational [Page 2] + +RFC 2102 Nimrod Multicast Support February 1997 + + +2 Multicast vs Unicast + + We begin by looking at the similarities and differences between + unicast routing and multicast routing. Both unicast and multicast + routing require two phases - route generation and packet forwarding. + In the case of unicast routing, Nimrod specifies modes of packet + forwarding; route generation itself is not specified but left to the + particular routing agent. For multicasting, Nimrod leaves both route + generation and packet forwarding mechanisms unspecified. To explain + why, we first point out three aspects that make multicasting quite + different from unicasting : + +o Groups and group dynamism. In multicasting, the destinations are part + of a group, whose membership is dynamic. This brings up the following + issues : + + - An association between the multicast group and the EIDs and + locators of the members comprising that group. This is especially + relevant in the case of sender initiated multicasting and policy + support. + + - A mechanism to accommodate new group members in the delivery in + response to addition of members, and a mechanism to "prune" the + delivery in response to departures. + +o State creation. Most solutions to multicasting can essentially be + viewed as creating state in routers for multicast packet forwarding. + Based on who creates the state, multicasting solutions differ. In + multicasting, we have several options for this - e.g., the sender, the + receivers or the intermediate routers. + +o Route generation. Even more so than in unicast routing, one can choose + from a rich spectrum of heuristics with different tradeoffs between a + number of parameters (such as cost and delay, algorithmic time + complexity and optimality etc.). For instance, some heuristics produce + a low-cost tree with high end-to-end delay and some produce trees that + give the shortest path to each destination but with a higher cost. + Heuristics for multicasting are a significant research area today, and + we expect advances to result in sophisticated heuristics in the near + future. + + Noting that there are various possible combinations of route + generation, group dynamism handling and state creation for a solution + and that each solution conceivably has applications for which it is + the most suitable, we do not specify one particular approach to + multicasting in Nimrod. 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, it is + + + +Ramanathan Informational [Page 3] + +RFC 2102 Nimrod Multicast Support February 1997 + + + necessary that certain things are agreed upon - for instance, the + structure of the forwarding information database that they create (we + discuss this in more detail in section 4). + + Thus, we do not discuss the details of any multicast solution here, + only its requirements in the context of Nimrod. Specifically, we + structure the discussion in the remainder of this document on the + following two themes : + + o What are the goals that we want to meet in providing multicasting in + Nimrod, and what specific requirements do these goals imply for the + multicast solution? + + o What are some of the approaches to multicasting being discussed + currently, and how relevant are each of these approaches to Nimrod? + +3 Goals and Requirements + + The chief goals of Nimrod multicasting and their implications on + solution requirements are as follows: + +1. Scalability. Nimrod multicasting must scale in terms of the size of + the internetwork, the number of groups supported and the number of + members per group. It must also support group dynamism efficiently. + This has the following implications for the solution: + + o Routers not on the direct path to the multicast destinations should + not be involved in state management. In a network with a large + number of routers, a solution that does involve such routers is + unlikely to scale. + + o It is likely that there will be a number of applications that have + a few members per group (e.g., medical imaging) and a number of + applications that have a large number of members per group (e.g., + news distribution). Nimrod multicasting should scale for both + these situations. If no single mechanism adequately scales for + both sparse and dense group memberships simultaneously, a + combination of mechanisms should be considered. + + o In the face of group membership change, there must be a facility + for incremental addition or deletion of "branches" in the + multicast tree. Reconstructing the tree from scratch is not likely + to scale. + + + + + + + + +Ramanathan Informational [Page 4] + +RFC 2102 Nimrod Multicast Support February 1997 + + + o It is likely that we will have some well-known groups (i.e., groups + which are more or less permanent in existence) and some ephemeral + groups. The dynamics of group membership are likely to be + different for each class of groups, and the solution should take + that into account as appropriate. + +2. Policy support. This includes both quality of service (QOS) as + well as access restrictions, although currently, demand is probably + higher for QOS. In particular, every path from a source to each + destination in the multicast group should satisfy the requested + quality of service and conform to the access restrictions. The + implications for the multicasting solution are : + + o It is likely that many multicasting applications will be cost + conscious in addition to having strict quality of service bounds + (such as delay and jitter). Balancing these will necessitate + dealing with some new parameters - e.g., the tree cost (sum of the + "cost" of each link), the tree delay (maximum, mean and variance + in end-to-end delay) etc. + + o In order to support policy-based routing, we need to know where the + destinations are (so that we can decide what route we can take to + them). In such a case, a mechanism that provides an association + between a group id and a set of destination locators is probably + required. + + o Some policy constraints are likely to be destination specific. For + instance, a domain might refuse transit service to traffic going to + certain destination domains. This presents certain unique problems + - in particular, for a single group, multiple trees may need to be + built, each tree "servicing" disjoint partitions of the multicast + destinations. + +3. Resource sharing. Multicasting typically goes hand in hand with large + traffic volume or applications with a high demand for resources. + These, in turn, imply efficient resource management and sharing if + possible. Therefore, it is important that we place an emphasis on + interaction with resource reservation. For instance, Nimrod must be + able to provide information on which tree resources are shareable and + which are not so that resource reservation may use it while allocating + resources to flows. + +4. Interoperability. There are two issues in this context. First, the + solution must be independent of mechanisms that provide the solution + with information it needs. For instance, many multicast solutions + (e.g., PIM) make use of information supplied by unicast routing + protocols. The multicast solution must not be dependent on which + unicast protocol is used. + + + +Ramanathan Informational [Page 5] + +RFC 2102 Nimrod Multicast Support February 1997 + + + Second, a multicast solution must interoperate with other multicast + solutions in the construction of a delivery tree. This implies some + kind of "agreement" at some "level". For instance, the agreement + could be that everybody use the same structure for storing forwarding + information in the routers. Since the delivery tree is defined by the + nature of forwarding information in the routers and not by the + particular mechanism used to create that information, multiple + implementations can coexist. + +4 Approaches + + The approaches to multicasting currently in operation and those being + considered by the IETF include the following : + +1. Distance vector multicast routing protocol (DVMRP)[DC90]. This + approach is based upon distance-vector routing information distribution + and hop-by-hop forwarding. It uses Reverse Path Forwarding (RPF)[DM78] + - a distributed algorithm for constructing an internetwork broadcast + tree. DVMRP uses a modified RPF algorithm, essentially 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 those in the shortest path from d to + s (If the paths are symmetric (i.e., cost the same) in either + direction, the reverse shortest path is same as the shortest path.) + An implementation of RPF exists in the current Internet in what + is commonly referred to as the MBONE. An improvement to this is in the + process of being deployed. It incorporates "prune" messages to + truncate further the routers not on the path to the destinations and + "graft" messages to undo this truncation, if later necessary. + + The main advantage of this scheme is that it is simple. The major + handicap is scalability. Two issues have been raised in this + context[BFC93]. First, if S is the number of active sources and G + the number of groups, then the state overhead is O(GS) and might be + unacceptable when resources are limited. Second, routers not on a + multicast tree are involved (in terms of sending/tracking prune and + graft messages) even though they might not be interested in the + particular source-group pair. The performance of this scheme is + expected to be relatively poor for large networks with sparsely + distributed group membership. Furthermore, no support for policies + or QOS is provided. + +2. Core Based Trees (CBT)[BFC93]. This scheme uses a single tree shared + by all sources per group. This tree has a single router as the core + (with additional routers for robustness) from which branches emanate. + The chief distinguishing characteristic of CBT is that it is receiver + initiated, i.e., receivers wishing to join a multicast group find the + tree (or its core) and attach themselves to it, without any + + + +Ramanathan Informational [Page 6] + +RFC 2102 Nimrod Multicast Support February 1997 + + + participation from the sources. + + The chief motivation behind this scheme is the reduction of the state + overhead, to O(G), in comparison to DVMRP and PIM(described below). + Also, only routers in the path between the core and the potential + members are involved in the process. Core-based tree formation and + packet flow are decoupled from underlying unicast routing. + + The main disadvantage is that packets no longer traverse the shortest + path from the source to their destinations. The performance in + general depends on judicious placement of cores and coordination + between them. Traffic concentration on links incident to the core is + another problem. There is also a dependence on network entities (in + other administrative domains, for instance) for resource reservation + and policy routing. + +3. Protocol Independent Multicasting (PIM)[DEFJ93]. Yet another approach + based on the receiver initiated philosophy, this is designed to reap + the advantages of DVMRP and CBT. Using a "rendezvous point", a + concept similar to the core discussed above, it allows for the + simultaneous existence of shared and source-specific multicast trees. + In the steady state, data can be delivered over the reverse shortest + path from the sender to the receiver (for better end-to-end delay) or + over the shared tree. + + Using two modes of operation, sparse and dense, this provides + improved performance, both when the group membership in an + internetwork is sparse and when it is dense. It is however, a + complex protocol. A limitation of PIM is that the shortest paths are + based on the reverse metrics and therefore truly "shortest" only when + the links are symmetric. + +4. Multicast Open Shortest Path First (MOSPF)[Moy92]. Unlike the + abovementioned approaches, this 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 computed, it can + determine which links it must forward copies onto. + + + + + + + + + + + +Ramanathan Informational [Page 7] + +RFC 2102 Nimrod Multicast Support February 1997 + + + MOSPF inherits advantages of OSPF and link-state distribution, namely + localized route computation (and easy verification of loop-freedom), + fast convergence to link-state changes etc. However, group membership + information is sent throughout the network, including links that are + not in the direct path to the multicast destinations. Thus, like + DVMRP, this is most suitable for small internetworks, that is, as an + intra-domain routing mechanism. + +5. Inter-Domain Policy Routing (IDPR)[Ste]. This approach uses + link-state routing information distribution like MOSPF, but uses + source-specified packet forwarding. Using the link-state + database, the source generates a policy multicast route to the + destinations. Using this, the IDPR path-setup procedure sets up + state in intermediate entities for packet duplication and + forwarding. The state contains information about the next-hop + entities for the multicast flow. When a data packet arrives, + it is forwarded to each next hop entity obtained from the state. + + Among the advantages of this approach are its ability to support + policy based multicast routing with ease and 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 it makes it relatively more + difficult to handle group membership changes (additions and + deletions) since such changes must be first communicated to the + source of the tree which will then add branches appropriately. + + We now discuss the applicability of these approaches to Nimrod. + Common to all of the approaches described is the fact that we need to + set up state in the intermediate routers for multicast packet + forwarding. The approaches differ mainly on who initiates the state + creation - the sender (e.g., IDPR, PIM), the receiver (e.g., CBT, + PIM) or the routers themselves create state without intitiation by + the sender or receivers (e.g., DVMRP, MOSPF). + + Nimrod should be able to accommodate both sender initiated as well as + receiver initiated state creation for multicasting. In the remainder + of this section, we discuss 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]. + + + + + + + +Ramanathan Informational [Page 8] + +RFC 2102 Nimrod Multicast Support February 1997 + + + An approach similar to that used in IDPR is viable for multicasting + using the flow mode. The source can set up state in intermediate + routers which can then appropriately duplicate packets. 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 is similar to the + advantages and disadvantages of IDPR and MOSPF respectively. + + Sender based trees can be set up using an approach similar to IDPR + and generalizing it to an "n" level hierarchy. A significant + advantage of this approach is policy-based routing. The source knows + about the policies of nodes that care to advertise them and can + choose a route the way it wants (i.e., not depend upon other entities + to choose the route, as in some schemes mentioned above). Another + advantage is that each source can use the multicast route generation + algorithm and packet forwarding scheme that best suits it, instead of + being forced to use whatever is implemented elsewhere in the network. + Further, this approach allows for incrementally deploying new + multicast tree generation algorithms 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 this. For instance, a receiver wishing to + join a group may generate a (policy) route to the core for that group + using its link-state map and attach itself to the tree. + + A disadvantage of sender based methods in general seems to be the + support of group dynamism. Specifically, if there is a change in the + membership of the group, the particular database which contains the + group-destination mapping must be updated. In comparison, receiver + oriented approaches seem to be able to accommodate group dynamism + more naturally. + + Nimrod does not preclude the simultaneous existence of multiple + approaches to multicasting and the possibility of switching from one + to the other depending on the dynamics of group distributions. + Interoperability is an issue - that is, the question of whether or + not different implementations of Nimrod can participate in the same + tree. However, as long as there is agreement in the structure of the + state created (i.e., the states can be interpreted uniformly for + packet forwarding), this should not be a problem. For instance, a + receiver wishing 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 be + additionally forwarded along this new "branch" to the new receiver. + + + + + +Ramanathan Informational [Page 9] + +RFC 2102 Nimrod Multicast Support February 1997 + + + 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 does not demand that one particular solution be used, + and indeed, we expect that a combination of approaches will be + employed and engineered in a manner 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 decribe 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 is 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 + + The PIM architecture maintains the traditional IP multicast service + model of receiver-initiated membership and is independent of any + specific unicast routing protocol (hence the name). + + A significant aspect of PIM is that it provides mechanisms for + establishing two kinds of trees - a shared tree, which is intended + for low "cost" multicasting and a source-based tree, intended for low + delay multicasting. + + A shared tree is rooted at a rendezvous point (RP), which is + typically a prespecified router for the multicast group in question. + In order to establish a shared tree, a designated router (DR) for a + host wishing to join a group G initiates a flow setup from the RP for + G to the DR. A source S wishing to send to a group G initiates a flow + setup between S and the RP for group G. At the conclusion of these + flow setups, packets can be forwarded from S to H through the RP. For + details on the protocol used to implement this flow setup please + refer to [DEF+94b]. + + + + + + +Ramanathan Informational [Page 10] + +RFC 2102 Nimrod Multicast Support February 1997 + + + After the shared tree has been setup, a recipient for group G has the + option of switching to a source-based shortest path tree. In such a + tree, packets are delivered from the source to each recipient along + the shortest path. To establish a source-based shortest path tree, + the DR for H looks at the source S of the packets it is receiving via + the shared tree and establishes a flow between S and the DR. The flow + is established along the shortest path from the DR to S (Thus, + strictly speaking, it is the reverse shortest path that is being + used.) Subsequently, packets can be forwarded from S to H using this + shortest path and thereby bypassing the RP. For details on the + protocol used to implement source-based trees in PIM please refer to + [DEF+94b]. + + When a host wishes to leave a multicast group, its designated router + sends a prune message towards the source (for source-based trees) or + towards the RP (for shared trees). For details on this and other + features of PIM please refer to [DEF+94b]. + + In Nimrod, PIM is implemented as follows (we refer to PIM based + multicast as Nimpim). In order to join a shared tree, an endpoint + (or an agent acting on behalf of the endpoint) wishing to join a + group G queries the association database for the EID and locator of + the RP for G (for well-known groups the association may be + configured). It is required that such an association be maintained + for every multicast group G. The endpoint gets a route for the RP and + initiates a multicast flow setup to the RP (a multicast flow setup is + similar to an unicast flow setup described in [CCS96] except for one + feature - when a multicast flow setup request reaches a node that + already has that flow present, the request is not forwarded further. + The new flow gets "spliced" in as a new branch of the existing + multicast tree). Similarly, the source establishes a flow to the RP. + The RP creates state to associate these two flows and now packets can + be forwarded to the endpoints from the source. Note that each flow + setup may be "hierarchical" and involve many subflows. All this, + however, is transparent to Nimpim. For details on management of + hierarchical flows please refer to [CCS96]. + + To create the source-based tree, the representative for a recipient + node N obtains the EID or locator of the source from the data packets + and initiates a multicast flow setup to the source. The route agent + for the node N uses its map in order to calculate the shortest path + from the source to N. The flow request is sent along the reverse of + this path. We note that the "shortness" of the path is constrained + by the amount of routing information available locally. However, + since the map is available locally, one can find the actual shortest + path from the source to N and not use the shortest path from N to S. + Thus, with Nimrod one can actually surmount a shortcoming of PIM with + relative ease. + + + +Ramanathan Informational [Page 11] + +RFC 2102 Nimrod Multicast Support February 1997 + + + We now discuss some more details of Nimpim. We start with a + description of multicast flow setup. This is the "basic" + functionality required to implement multicasting. Having this + "building-block" spelt out, we use this to specify the establishment + of the shared tree (in section 5.3) and the establishment of a + source-based tree (in section 5.4). + + We only discuss sparse-mode multicasting, as described in [DEF+94a] + here. Further, to simplify the discussion, we assume a single + Rendezvous Point per group. Finally, we "address" all entities in + terms of their EIDs alone for reasons of conciseness - the locators + could be used in conjuction to reduce the overhead of database + lookups. + +5.2 Joining and Leaving a Tree + + Nimpim uses two control packets in order to setup a flow - the Nimrod + Multicast Flow-Request packet (NMFReq) and the Nimrod Multicast + Flow-Reply packet (NMFRep). + + The NMFReq packet is a control packet identified by a prespecified + "payload type". The protocol-specific part of this packet includes + the following fields (except for the Code field, these fields are + present in the Unicast Flow-Request packet too) : + + 1. S-EID : The EID of the initiator of the flow. + + 2. T-EID : The EID of the target of the flow. + + 3. Flow-id : A label denoting the flow. + + 4. Direction : The direction of the flow - whether from the initiator + to the target (FORW) or from the target to the initiator (REVERSE) + or both (BOTH). + + 5. Code : Denotes whether the packet is for joining a flow + (NMFReq-Join) for leaving a flow (NMFReq-Prune). + + 6. Source Route : A sequence of node locators through which the packet + must travel. + + + + + + + + + + + +Ramanathan Informational [Page 12] + +RFC 2102 Nimrod Multicast Support February 1997 + + + The processing of the NMFReq by a forwarding agent at node N is + similar to that of the unicast flow request (see [CCS96]), except for + the fact that now we provide the ability for the new flow to "splice" + onto an existing delivery tree or "un-splice" from an existing + delivery tree. Specifically, + + o If the Code is NMFReq-Join then the algorithm executed by the + forwarding agent for node N is shown in Figure 1. + + o If the Code is NMFReq-Prune then the algorithm is executed by the + forwarding agent at node N is shown in Figure 2. + + The NMFRep packet is used to accept or reject an NMFReq-Join or + NMFReq-Prune. The packet format is the same as that for unicast flow + request. However, an NMFRep packet is generated now by the first + node N that grafts the new flow to the existing tree. This may be + different from 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 is no host + in the local network for the group. + + The NMFReq - NMFRep exchanges constitute a procedure for joining a + multicast delivery tree (when the Code is Join) and for leaving a + multicast delivery tree (when the Code is Prune). We term these + procedures Tree-Join and Tree-Leave respectively; we shall be using + these procedures as "building-blocks" in the construction of shared + trees (section 5.3) and of source-based trees (section 5.4). + + + + + + + + + + + + + + + + + + + + + + + +Ramanathan Informational [Page 13] + +RFC 2102 Nimrod Multicast Support February 1997 + + +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. + + + + + + + +Ramanathan Informational [Page 14] + +RFC 2102 Nimrod Multicast Support February 1997 + + +5.2.1 An Example + + An example of how a tree is joined is given here with the help of + Figure 3. In the figure, bold lines indicate an existing tree. + Representative R on behalf of host H joins the tree by sending an + NMFJoin-Req towards a target T. When used in the shared tree mode, + the target is the RP and when used in the source tree mode, it is the + source (root) of the multicast tree. Suppose that a host H wants to + join the multicast tree. The following steps are executed : + +Step 1. A representative R of H queries the route agent for a route + from T to R. It obtains the route T - C- B - A - R. It builds a + NMFJoin-Req packet with source route as R, A, B, C, T and flow + as F 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 (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 and constructs 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. + + + + + + + + + + + + + + + + + + + + + + + + + +Ramanathan Informational [Page 15] + +RFC 2102 Nimrod Multicast Support February 1997 + + +5.3 Establishing a Shared Tree + + There are two parts to establishing a shared tree - the receiver-to- + RP communication wherein the receiver joins the delivery tree rooted + at RP and the sender-to-RP communication wherein 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: When an endpoint wishes to join a + multicast group G, the endpoint representative obtains the Rendezvous + Point EID for G. We assume that the association database contains + such a mapping. For details on how the association database query is + implemented, please refer [CCS96]. + + The representative also obtains the flow-id to be used for the flow. + The flow-id is constructed as the tuple (RP-EID, G) or an equivalent + thereof. Note that the flow-id must be unique to the particular + multicast flow. This is not the only method or perhaps even the best + method for obtaining a flow id. Alternate methods for obtaining the + flow-id are discussed in section 5.5. + + + + +Ramanathan Informational [Page 16] + +RFC 2102 Nimrod Multicast Support February 1997 + + + The representative then initiates a Tree-Join procedure. + + The NMFReq packet fields are as follows: + + o S-EID : The EID of the endpoint wishing to join. + + o T-EID : The RP EID (obtained from the Association Database). + + o Flow-id : The flow-id for this group (obtained as mentioned + above). + + o Direction : REVERSE (from the RP to the receiving endpoint). + + o Code : Join. + + o Source Route : Reverse of the route obtained from the map agent + for a query "from RP-EID to Receiver-EID". + + At the first node already containing this Flow-id or the RP, an + NMFRep packet is generated. The S-EID, T-EID, Direction and Flow-id + fields are copied from the NMFReq packet and the Code is set to + Join-Accept or Join-Refuse as the case may be. The source route is + reversed from the NMFReq packet. + + Sender-RP Communications: When an endpoint wishes to send to a + multicast group G, the endpoint representative obtains the Rendezvous + Point EID for G. We assume that the association database contains + such a mapping. For details on how the association database query is + implemented, please refer [CCS96]. + + The representative also obtains the flow-id to be used for the flow. + The flow-id is constructed as the tuple (Sender-EID, G) or an + equivalent thereof. Note that the flow-id must be unique to the + particular multicast flow. This is not the only method or perhaps + even the best method for obtaining a flow id. Alternate methods for + obtaining the flow-id are discussed in section 5.5. + + The representative then sends a RP-Register Message to the RP. This + register message is equivalent to the PIM-Register described in + [DEF+94b]. The RP-Register message contains the group G and the + flow-id (obtained as discussed above) and the sender EID. + + The RP then initiates a Tree-Join with the Sender EID as the target. + The NMFReq fields are as follows : + + o S-EID : RP-EID. + + o T-EID : Sender EID (copied from RP-Register Message). + + + +Ramanathan Informational [Page 17] + +RFC 2102 Nimrod Multicast Support February 1997 + + + o Flow-id : The flow-id field from RP-Register Message. + + o Code : Join. + + o Direction : REVERSE. + + o Source Route : Reverse of the route obtained from map agent + query "from Sender-EID to RP-EID". + + The NMFRep fields are obvious. + + Shared Tree Data Forwarding: Packets sent from the source for group G + contain the Flow-id used by the sender(s) and receiver(s) for setting + up the delivery tree. The packets from the sender are sent to the RP + where they are multicast, using the state created for the flow, into + the delivery tree rooted at the RP to all of the receivers that did a + Tree-Join. + +5.4 Switching to a Source-Rooted Shortest Path Tree + + There are two parts involved in switching to a Source-Rooted Shortest + Path Tree - the receiver-source communications wherein the receiver + joins a multicast delivery tree rooted at the source and the + receiver-RP communications wherein the receiver leaves the shared + tree. + + Receiver-Source Communications: An endpoint E that is receiving + packets through the shared tree from source S has the option of + switching to a delivery tree rooted at the source such that packets + from S to E traverse the shortest path (using whatever metric). + + The endpoint representative of E obtains the flow-id to be used for + the flow. The flow-id is constructed equivalently to the tuple + (Source-EID, G). Note that the flow-id must be unique to the + particular multicast flow. This is not the only method or perhaps + even the best method for obtaining a flow id. Alternate methods for + obtaining the flow-id are discussed in section 5.5. + + The representative for E initiates a Tree-Join toward S with NMFReq + fields as follows: + + o S-EID : EID of the Endpoint E. + + o T-EID : EID of the source. + + o Flow-id : Flow id for the multicast (obtained as mentioned above). + + o Code : Join. + + + +Ramanathan Informational [Page 18] + +RFC 2102 Nimrod Multicast Support February 1997 + + + o Direction : REVERSE. + + o Source Route : To obtain the route, the route agent is queried for + a shortest path route (based on the chosen metric, typically, the + delay) from the source to the endpoint. We note that the quality + of the route is constrained by the amount of routing information + available, directly or indirectly, to the route agent. The Source + Route is the reverse of the route thus obtained. + + A comment on the difference between the shortest-path trees obtained + using the RPF tree as in [DEF+94b, DC90] and the trees that are be + obtained here. When using the RPF scheme, the packets from the + source S to the endpoint E follow a path that is the shortest path + from E to S. This is the desired path if and only if the path is + symmetric in either direction. However, in the mechanism described + here for Nimrod, the packets do follow the "actual" shortest path + from S to E whether or not the path is symmetric. + + The NMFRep fields are obvious. + + Receiver-RP Communications: After the receiver has joined the + source-rooted tree, it can optionally disassociate itself from the + shared tree. This is done by initiating a Tree-Leave procedure. + + The representative sends a NMFReq packet toward the RP with the + fields as follows. + + o S-EID : The EID of the endpoint wishing to leave the shared tree. + + o T-EID : The RP-EID. + + o Flow-id : The flow-id it used to join the shared tree. + + o Code : Prune. + + o Direction : REVERSE. + + o Source Route : Obtained as for the Tree-Join. + + The prune packet is processed by the intermediate forwarding agents + as mentioned in section 5.2. When the receiver gets back the NMFRep + packet, the receiver has left the shared tree. + + Source Tree Data Forwarding: Packets from the source contain the + flow-id that was used to join the source tree for a given multicast + group. Forwarding agents simply use the state created by the Tree- + Join procedure in order to duplicate and forward packets toward the + receivers. + + + +Ramanathan Informational [Page 19] + +RFC 2102 Nimrod Multicast Support February 1997 + + +5.5 Miscellaneous Issues + + Obtaining the Flow-Id: In the above scheme the flow-id for a + particular multicast group G was obtained by combining the RP-EID and + the group set-id (G-SID) (in case of shared tree) or by combining the + Source-EID and the G-SID (in case of source-based tree). A + disadvantage of this approach is that the bit-length of EID/SID is + potentially high (more than 64 bits) and thus the flow-id could be + very long. While there do exist bit-based data structures and search + algorithms (such as Patricia Trees) that may be used for an efficient + implementation, it is worth considering some other methods in lieu of + using the EID/SID combination. We describe some methods below : + +1. For shared trees, the flow-id for a particular group G may be stored + and updated in the association database. Since we have to use the + association database anyway to obtain the RP-EID, these does not cause + much additional burden. + + However, this cannot be used efficiently for source-based trees because + we need a flow-id for each combination of Source and Group. + +2. 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 that it wishes to + be used by receivers when they switch to a source-based tree. This + 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 wish to switch, they use that flow-id. + + This needs the definition of the "special" packet. + +3. The flow-id is handed out only 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 be used is + returned in the NMFRep message generated by the forwarding agent where + the new branch meets the existing tree. Forwarding agents in the path + of the NMFRep packet update the state information by rewriting the + dummy flow-id by the correct flow-id contained in the NMFRep packet. + + This requires the re-definition of the NMFRep packet. Note that now + there must be space for two flow-ids in the NMFRep packet - one for the + "dummy" flow-id and the other for the "correct" flow-id that must + replace the dummy flow-id. + + We claim that each of the above schemes achieves synchronization in + the flow-id in 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. + + + + +Ramanathan Informational [Page 20] + +RFC 2102 Nimrod Multicast Support February 1997 + + + Dense Mode Multicast: The PIM architecture [DEF+94a] includes a + multicast protocol when the group membership is densely distributed + within the internetwork. In this mode, no Rendezvous Points are used + and a source rooted tree is formed based on Reverse Path Forwarding + in a manner similar to that of DVMRP [DC90]. + + We do not give details of how Nimrod can implement Dense Mode + Multicast here. + + Multiple RPs: Our discussion above has been based on the assumption + that there is one RP per group. PIM allows more than one RP per + group. We do not discuss multiple-RP PIM here. + +6 Security Considerations + + Security issues are not discussed in this memo. + +7 Summary + +o 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 the technique to the + particular instantiation of Nimrod. + +o 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. + +o Multicasting typically requires the setting up of 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. + +o A receiver-initiated multicast protocol, PIM, is being designed by the + IDMR working group of the IETF. The facilities provided by Nimrod make + the use of PIM as a multicast protocol quite straightforward. + + + + + + +Ramanathan Informational [Page 21] + +RFC 2102 Nimrod Multicast Support February 1997 + + +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. + + + + + + + + + + + + + + + + +Ramanathan Informational [Page 22] + +RFC 2102 Nimrod Multicast Support February 1997 + + +9 Acknowledgements + + We thank Isidro Castineyra (BBN), Charles Lynn (BBN), Martha + Steenstrup (BBN) and other members of the Nimrod Working Group for + their comments and suggestions on this memo. + +10 Author's Address + + Ram Ramanathan + BBN Systems and Technologies + 10 Moulton Street + Cambridge, MA 02138 + + Phone: (617) 873-2736 + EMail: ramanath@bbn.com + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +Ramanathan Informational [Page 23] + |