doc: Add RFC documents

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]
+