As per Relevance of the word approach, we have this rfc below:
Network Working Group R.
Request for Comments: 2102 BBN Systems and
Category: Informational February 1997
Multicast Support for Nimrod : Requirements and Solution
Status of this
This memo provides information for the Internet community. This
does not specify an Internet standard of any kind. Distribution
this memo is unlimited
Nimrod does not specify a particular solution for multicasting
Rather, Nimrod may use any of a number of emerging
techniques. We identify the requirements that Nimrod has of
solution for multicast support. We compare existing approaches
multicasting within an internetwork and discuss their advantages
disadvantages. Finally, as an example, we outline the mechanisms
support multicast in Nimrod using the scheme currently
developed within the IETF - namely, the Protocol Indpendent
(PIM) protocol
Table of
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
The nature of emerging applications such as videoconferencing,
classroom, etc. makes the support for multicasting essential for
future routing architecture. Multicasting is performed by using
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
the IETF) are studying the problem by itself and it is not
intention to duplicate those efforts
This attitude towards multicasting is consistent with Nimrod'
general philosophy of flexibility, adaptability and
change
While a multicasting solution per se is not part of the "core"
architecture, Nimrod does require that the solution have
characteristics. It is the purpose of this document to discuss
of these requirements and evaluate approaches towards meeting them
This document is organized as follows. In section 2 we discuss
multicasting is treated a little differently than unicast despite
fact that the former is essentially a generalization of the latter
Following that, in section 4 we discuss current approaches
multicasting . In section 5, we give an example of how
multicasting may be done using PIM [DEF+94a]. For readers who do
have the time to go through the entire document, a summary is
at the end
This document uses many terms and concepts from the
Architecture document [CCS96] and some terms and concepts (in
5) from the Nimrod Functionality document [RS96]. Much of
discussion assumes that you have read at least the
Architecture document [CCS96].
Ramanathan Informational [Page 2]
RFC 2102 Nimrod Multicast Support February 1997
2 Multicast vs
We begin by looking at the similarities and differences
unicast routing and multicast routing. Both unicast and
routing require two phases - route generation and packet forwarding
In the case of unicast routing, Nimrod specifies modes of
forwarding; route generation itself is not specified but left to
particular routing agent. For multicasting, Nimrod leaves both
generation and packet forwarding mechanisms unspecified. To
why, we first point out three aspects that make multicasting
different from unicasting :
o Groups and group dynamism. In multicasting, the destinations are
of a group, whose membership is dynamic. This brings up the
issues :
- An association between the multicast group and the EIDs
locators of the members comprising that group. This is
relevant in the case of sender initiated multicasting and
support
- A mechanism to accommodate new group members in the delivery
response to addition of members, and a mechanism to "prune"
delivery in response to departures
o State creation. Most solutions to multicasting can essentially
viewed as creating state in routers for multicast packet forwarding
Based on who creates the state, multicasting solutions differ.
multicasting, we have several options for this - e.g., the sender,
receivers or the intermediate routers
o Route generation. Even more so than in unicast routing, one can
from a rich spectrum of heuristics with different tradeoffs between
number of parameters (such as cost and delay, algorithmic
complexity and optimality etc.). For instance, some heuristics
a low-cost tree with high end-to-end delay and some produce trees
give the shortest path to each destination but with a higher cost
Heuristics for multicasting are a significant research area today,
we expect advances to result in sophisticated heuristics in the
future
Noting that there are various possible combinations of
generation, group dynamism handling and state creation for a
and that each solution conceivably has applications for which it
the most suitable, we do not specify one particular approach
multicasting in Nimrod. Every implementation of Nimrod is free
use its own multicasting technique, as long as it meets the goals
requirements of Nimrod. However, for interoperability, it
Ramanathan Informational [Page 3]
RFC 2102 Nimrod Multicast Support February 1997
necessary that certain things are agreed upon - for instance,
structure of the forwarding information database that they create (
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,
structure the discussion in the remainder of this document on
following two themes :
o What are the goals that we want to meet in providing multicasting
Nimrod, and what specific requirements do these goals imply for
multicast solution
o What are some of the approaches to multicasting being
currently, and how relevant are each of these approaches to Nimrod
3 Goals and
The chief goals of Nimrod multicasting and their implications
solution requirements are as follows
1. Scalability. Nimrod multicasting must scale in terms of the size
the internetwork, the number of groups supported and the number
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
not be involved in state management. In a network with a
number of routers, a solution that does involve such routers
unlikely to scale
o It is likely that there will be a number of applications that
a few members per group (e.g., medical imaging) and a number
applications that have a large number of members per group (e.g.,
news distribution). Nimrod multicasting should scale for
these situations. If no single mechanism adequately scales
both sparse and dense group memberships simultaneously,
combination of mechanisms should be considered
o In the face of group membership change, there must be a
for incremental addition or deletion of "branches" in
multicast tree. Reconstructing the tree from scratch is not
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.,
which are more or less permanent in existence) and some
groups. The dynamics of group membership are likely to
different for each class of groups, and the solution should
that into account as appropriate
2. Policy support. This includes both quality of service (QOS)
well as access restrictions, although currently, demand is
higher for QOS. In particular, every path from a source to
destination in the multicast group should satisfy the
quality of service and conform to the access restrictions.
implications for the multicasting solution are :
o It is likely that many multicasting applications will be
conscious in addition to having strict quality of service
(such as delay and jitter). Balancing these will
dealing with some new parameters - e.g., the tree cost (sum of
"cost" of each link), the tree delay (maximum, mean and
in end-to-end delay) etc
o In order to support policy-based routing, we need to know where
destinations are (so that we can decide what route we can take
them). In such a case, a mechanism that provides an
between a group id and a set of destination locators is
required
o Some policy constraints are likely to be destination specific.
instance, a domain might refuse transit service to traffic going
certain destination domains. This presents certain unique
- in particular, for a single group, multiple trees may need to
built, each tree "servicing" disjoint partitions of the
destinations
3. Resource sharing. Multicasting typically goes hand in hand with
traffic volume or applications with a high demand for resources
These, in turn, imply efficient resource management and sharing
possible. Therefore, it is important that we place an emphasis
interaction with resource reservation. For instance, Nimrod must
able to provide information on which tree resources are shareable
which are not so that resource reservation may use it while
resources to flows
4. Interoperability. There are two issues in this context. First,
solution must be independent of mechanisms that provide the
with information it needs. For instance, many multicast
(e.g., PIM) make use of information supplied by unicast
protocols. The multicast solution must not be dependent on
unicast protocol is used
Ramanathan Informational [Page 5]
RFC 2102 Nimrod Multicast Support February 1997
Second, a multicast solution must interoperate with other
solutions in the construction of a delivery tree. This implies
kind of "agreement" at some "level". For instance, the
could be that everybody use the same structure for storing
information in the routers. Since the delivery tree is defined by
nature of forwarding information in the routers and not by
particular mechanism used to create that information,
implementations can coexist
4
The approaches to multicasting currently in operation and those
considered by the IETF include the following :
1. Distance vector multicast routing protocol (DVMRP)[DC90].
approach is based upon distance-vector routing information
and hop-by-hop forwarding. It uses Reverse Path Forwarding (RPF)[DM78]
- a distributed algorithm for constructing an internetwork
tree. DVMRP uses a modified RPF algorithm, essentially a
broadcast tree, to build a reverse shortest path sender-based
delivery tree. A reverse shortest path from s to d is a path that
the same intermediate nodes as those in the shortest path from d
s (If the paths are symmetric (i.e., cost the same) in
direction, the reverse shortest path is same as the shortest path.)
An implementation of RPF exists in the current Internet in
is commonly referred to as the MBONE. An improvement to this is in
process of being deployed. It incorporates "prune" messages
truncate further the routers not on the path to the destinations
"graft" messages to undo this truncation, if later necessary
The main advantage of this scheme is that it is simple. The
handicap is scalability. Two issues have been raised in
context[BFC93]. First, if S is the number of active sources and
the number of groups, then the state overhead is O(GS) and might
unacceptable when resources are limited. Second, routers not on
multicast tree are involved (in terms of sending/tracking prune
graft messages) even though they might not be interested in
particular source-group pair. The performance of this scheme
expected to be relatively poor for large networks with
distributed group membership. Furthermore, no support for
or QOS is provided
2. Core Based Trees (CBT)[BFC93]. This scheme uses a single tree
by all sources per group. This tree has a single router as the
(with additional routers for robustness) from which branches emanate
The chief distinguishing characteristic of CBT is that it is
initiated, i.e., receivers wishing to join a multicast group find
tree (or its core) and attach themselves to it, without
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
overhead, to O(G), in comparison to DVMRP and PIM(described below).
Also, only routers in the path between the core and the
members are involved in the process. Core-based tree formation
packet flow are decoupled from underlying unicast routing
The main disadvantage is that packets no longer traverse the
path from the source to their destinations. The performance
general depends on judicious placement of cores and
between them. Traffic concentration on links incident to the core
another problem. There is also a dependence on network entities (
other administrative domains, for instance) for resource
and policy routing
3. Protocol Independent Multicasting (PIM)[DEFJ93]. Yet another
based on the receiver initiated philosophy, this is designed to
the advantages of DVMRP and CBT. Using a "rendezvous point",
concept similar to the core discussed above, it allows for
simultaneous existence of shared and source-specific multicast trees
In the steady state, data can be delivered over the reverse
path from the sender to the receiver (for better end-to-end delay)
over the shared tree
Using two modes of operation, sparse and dense, this
improved performance, both when the group membership in
internetwork is sparse and when it is dense. It is however,
complex protocol. A limitation of PIM is that the shortest paths
based on the reverse metrics and therefore truly "shortest" only
the links are symmetric
4. Multicast Open Shortest Path First (MOSPF)[Moy92]. Unlike
abovementioned approaches, this is based on link-state
information distribution. The packet forwarding mechanism
hop-by-hop. Since every router has complete topology information
every router computes the shortest path multicast tree from
source to any group using Dijkstra's algorithm. If the
doing the computation falls within the tree computed, it
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,
localized route computation (and easy verification of loop-freedom),
fast convergence to link-state changes etc. However, group
information is sent throughout the network, including links that
not in the direct path to the multicast destinations. Thus,
DVMRP, this is most suitable for small internetworks, that is, as
intra-domain routing mechanism
5. Inter-Domain Policy Routing (IDPR)[Ste]. This approach
link-state routing information distribution like MOSPF, but
source-specified packet forwarding. Using the link-
database, the source generates a policy multicast route to
destinations. Using this, the IDPR path-setup procedure sets
state in intermediate entities for packet duplication
forwarding. The state contains information about the next-
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
policy based multicast routing with ease and
(flexibility) in the choice of multicasting algorithm used at
source. IDPR also allows resource sharing over multiple
trees. The major disadvantage is that it makes it relatively
difficult to handle group membership changes (additions
deletions) since such changes must be first communicated to
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
set up state in the intermediate routers for multicast
forwarding. The approaches differ mainly on who initiates the
creation - the sender (e.g., IDPR, PIM), the receiver (e.g., CBT
PIM) or the routers themselves create state without intitiation
the sender or receivers (e.g., DVMRP, MOSPF).
Nimrod should be able to accommodate both sender initiated as well
receiver initiated state creation for multicasting. In the
of this section, we discuss the pros and cons of these approaches
Nimrod
Nimrod uses link-state routing information distribution (
maps) and has four modes of packet forwarding - flow mode
Connectivity Specification Chain (CSC) mode,
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
using the flow mode. The source can set up state in
routers which can then appropriately duplicate packets. For the CSC
BTES and datagram modes, an approach similar to the one used in
is applicable. In these situations, the advantages and
of these approaches in the context of Nimrod is similar to
advantages and disadvantages of IDPR and MOSPF respectively
Sender based trees can be set up using an approach similar to
and generalizing it to an "n" level hierarchy. A
advantage of this approach is policy-based routing. The source
about the policies of nodes that care to advertise them and
choose a route the way it wants (i.e., not depend upon other
to choose the route, as in some schemes mentioned above).
advantage is that each source can use the multicast route
algorithm and packet forwarding scheme that best suits it, instead
being forced to use whatever is implemented elsewhere in the network
Further, this approach allows for incrementally deploying
multicast tree generation algorithms as research in that
progresses
CBT-like methods may be used to set up receiver initiated trees
Nimrod provides link-state maps for generating routes and a CBT-
method is compatible with this. For instance, a receiver wishing
join a group may generate a (policy) route to the core for that
using its link-state map and attach itself to the tree
A disadvantage of sender based methods in general seems to be
support of group dynamism. Specifically, if there is a change in
membership of the group, the particular database which contains
group-destination mapping must be updated. In comparison,
oriented approaches seem to be able to accommodate group
more naturally
Nimrod does not preclude the simultaneous existence of
approaches to multicasting and the possibility of switching from
to the other depending on the dynamics of group distributions
Interoperability is an issue - that is, the question of whether
not different implementations of Nimrod can participate in the
tree. However, as long as there is agreement in the structure of
state created (i.e., the states can be interpreted uniformly
packet forwarding), this should not be a problem. For instance,
receiver wishing to join a sender created tree might set up state
a path between itself and a router on the tree with the sender
being unaware of it. Packets entering the router would now
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
approaches to multicasting. Each approach has its disadvantages
respect to the requirements mentioned in the previous section.
architecture does not demand that one particular solution be used
and indeed, we expect that a combination of approaches will
employed and engineered in a manner most appropriate to
requirements of the particular application or subscriber
5 A Multicasting Scheme based on
The Inter-Domain Multicast Routing (IDMR) working group of the
has developed a specification for a new multicast scheme, namely
Protocol Independent Multicasting (PIM) for use in the
[DEF+94a, DEF+94b]. In this section, we decribe how the
mentioned therein may be implemented using the facilities provided
Nimrod
We note that the path setup facility provided in Nimrod makes it
conducive to PIM-style multicasting; despite the length of
description given here, we assure the reader that it is quite
to implement PIM style multicasting in Nimrod
Before reading this section, we recommend that the reader
some familiarity with PIM (see [DEF+94a, DEF+94b]).
5.1
The PIM architecture maintains the traditional IP multicast
model of receiver-initiated membership and is independent of
specific unicast routing protocol (hence the name).
A significant aspect of PIM is that it provides mechanisms
establishing two kinds of trees - a shared tree, which is
for low "cost" multicasting and a source-based tree, intended for
delay multicasting
A shared tree is rooted at a rendezvous point (RP), which
typically a prespecified router for the multicast group in question
In order to establish a shared tree, a designated router (DR) for
host wishing to join a group G initiates a flow setup from the RP
G to the DR. A source S wishing to send to a group G initiates a
setup between S and the RP for group G. At the conclusion of
flow setups, packets can be forwarded from S to H through the RP.
details on the protocol used to implement this flow setup
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
option of switching to a source-based shortest path tree. In such
tree, packets are delivered from the source to each recipient
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
the shared tree and establishes a flow between S and the DR. The
is established along the shortest path from the DR to S (Thus
strictly speaking, it is the reverse shortest path that is
used.) Subsequently, packets can be forwarded from S to H using
shortest path and thereby bypassing the RP. For details on
protocol used to implement source-based trees in PIM please refer
[DEF+94b].
When a host wishes to leave a multicast group, its designated
sends a prune message towards the source (for source-based trees)
towards the RP (for shared trees). For details on this and
features of PIM please refer to [DEF+94b].
In Nimrod, PIM is implemented as follows (we refer to PIM
multicast as Nimpim). In order to join a shared tree, an
(or an agent acting on behalf of the endpoint) wishing to join
group G queries the association database for the EID and locator
the RP for G (for well-known groups the association may
configured). It is required that such an association be
for every multicast group G. The endpoint gets a route for the RP
initiates a multicast flow setup to the RP (a multicast flow setup
similar to an unicast flow setup described in [CCS96] except for
feature - when a multicast flow setup request reaches a node
already has that flow present, the request is not forwarded further
The new flow gets "spliced" in as a new branch of the
multicast tree). Similarly, the source establishes a flow to the RP
The RP creates state to associate these two flows and now packets
be forwarded to the endpoints from the source. Note that each
setup may be "hierarchical" and involve many subflows. All this
however, is transparent to Nimpim. For details on management
hierarchical flows please refer to [CCS96].
To create the source-based tree, the representative for a
node N obtains the EID or locator of the source from the data
and initiates a multicast flow setup to the source. The route
for the node N uses its map in order to calculate the shortest
from the source to N. The flow request is sent along the reverse
this path. We note that the "shortness" of the path is
by the amount of routing information available locally. However
since the map is available locally, one can find the actual
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
relative ease
Ramanathan Informational [Page 11]
RFC 2102 Nimrod Multicast Support February 1997
We now discuss some more details of Nimpim. We start with
description of multicast flow setup. This is the "basic
functionality required to implement multicasting. Having
"building-block" spelt out, we use this to specify the
of the shared tree (in section 5.3) and the establishment of
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
Rendezvous Point per group. Finally, we "address" all entities
terms of their EIDs alone for reasons of conciseness - the
could be used in conjuction to reduce the overhead of
lookups
5.2 Joining and Leaving a
Nimpim uses two control packets in order to setup a flow - the
Multicast Flow-Request packet (NMFReq) and the Nimrod
Flow-Reply packet (NMFRep).
The NMFReq packet is a control packet identified by a
"payload type". The protocol-specific part of this packet
the following fields (except for the Code field, these fields
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
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
(NMFReq-Join) for leaving a flow (NMFReq-Prune).
6. Source Route : A sequence of node locators through which the
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
similar to that of the unicast flow request (see [CCS96]), except
the fact that now we provide the ability for the new flow to "splice
onto an existing delivery tree or "un-splice" from an
delivery tree. Specifically
o If the Code is NMFReq-Join then the algorithm executed by
forwarding agent for node N is shown in Figure 1.
o If the Code is NMFReq-Prune then the algorithm is executed by
forwarding agent at node N is shown in Figure 2.
The NMFRep packet is used to accept or reject an NMFReq-Join
NMFReq-Prune. The packet format is the same as that for unicast
request. However, an NMFRep packet is generated now by the
node N that grafts the new flow to the existing tree. This may
different from the target of the NMFReq
It is required that a leaf router keep track of all hosts
joined to the group and send a prune message only if there is no
in the local network for the group
The NMFReq - NMFRep exchanges constitute a procedure for joining
multicast delivery tree (when the Code is Join) and for leaving
multicast delivery tree (when the Code is Prune). We term
procedures Tree-Join and Tree-Leave respectively; we shall be
these procedures as "building-blocks" in the construction of
trees (section 5.3) and of source-based trees (section 5.4).
Ramanathan Informational [Page 13]
RFC 2102 Nimrod Multicast Support February 1997
if the flow-id F in NMFReq-Join is in flow-list
if T-EID in NMFReq-Join = target in flow state for F
if Direction in NMFReq-Join is REVERSE or BOTH
Add the node preceding N in source route to child list for
discard
discard
install state for F in N, i.e.,
assign parent(F) = node succeeding N in source
assign child(F) = node preceeding N in source
assign target(F) = T-EID in NMFReq-
forward NMFReq-Join to parent(F
end
Figure 1: Algorithm executed by a forwarding agent for node N
when it receives an NMFReq-Join
if the flow-id F in NMFReq-Prune is in flow-
then
delete previous hop in source route from child list for F, if
if child list for F is
then
delete the flow-id and state associated with
forward to next hop in source
else discard
else forward to next hop in source-
end
Figure 2: Algorithm executed by a forwarding agent for node N when
receives an NMFReq-Prune
Ramanathan Informational [Page 14]
RFC 2102 Nimrod Multicast Support February 1997
5.2.1 An
An example of how a tree is joined is given here with the help
Figure 3. In the figure, bold lines indicate an existing tree
Representative R on behalf of host H joins the tree by sending
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
source (root) of the multicast tree. Suppose that a host H wants
join the multicast tree. The following steps are executed :
Step 1. A representative R of H queries the route agent for a
from T to R. It obtains the route T - C- B - A - R. It builds
NMFJoin-Req packet with source route as R, A, B, C, T and
as F forwards it to A
Step 2. A looks for flow F in its installed flow database
doesn't find it. It installs state for F (makes R a child
B a parent in the multicast tree) and sends the NMFJoin-Req
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
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
There are two parts to establishing a shared tree - the receiver-to
RP communication wherein the receiver joins the delivery tree
at RP and the sender-to-RP communication wherein the RP joins
delivery tree rooted at the sender
+---+
| |\
+---+ \
/ \
/ \
C / \
+---+ +---+
| | | |
+---+ +---+
\
\
\
R join-req join-req \
+---+ - - - - -> +---+ - - - - -> +---+
| |<------------| |<-----------| |
+---+ join-rep +---+ join-rep +---+
| A \
| \
| \
( ) +---+
H | |
+---+
Figure 3: Illustration for the example describing joining an
multicast tree
Receiver-RP Communications: When an endpoint wishes to join
multicast group G, the endpoint representative obtains the
Point EID for G. We assume that the association database
such a mapping. For details on how the association database query
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
thereof. Note that the flow-id must be unique to the
multicast flow. This is not the only method or perhaps even the
method for obtaining a flow id. Alternate methods for obtaining
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
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
for a query "from RP-EID to Receiver-EID".
At the first node already containing this Flow-id or the RP,
NMFRep packet is generated. The S-EID, T-EID, Direction and Flow-
fields are copied from the NMFReq packet and the Code is set
Join-Accept or Join-Refuse as the case may be. The source route
reversed from the NMFReq packet
Sender-RP Communications: When an endpoint wishes to send to
multicast group G, the endpoint representative obtains the
Point EID for G. We assume that the association database
such a mapping. For details on how the association database query
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
equivalent thereof. Note that the flow-id must be unique to
particular multicast flow. This is not the only method or
even the best method for obtaining a flow id. Alternate methods
obtaining the flow-id are discussed in section 5.5.
The representative then sends a RP-Register Message to the RP.
register message is equivalent to the PIM-Register described
[DEF+94b]. The RP-Register message contains the group G and
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
query "from Sender-EID to RP-EID".
The NMFRep fields are obvious
Shared Tree Data Forwarding: Packets sent from the source for group
contain the Flow-id used by the sender(s) and receiver(s) for
up the delivery tree. The packets from the sender are sent to the
where they are multicast, using the state created for the flow,
the delivery tree rooted at the RP to all of the receivers that did
Tree-Join
5.4 Switching to a Source-Rooted Shortest Path
There are two parts involved in switching to a Source-Rooted
Path Tree - the receiver-source communications wherein the
joins a multicast delivery tree rooted at the source and
receiver-RP communications wherein the receiver leaves the
tree
Receiver-Source Communications: An endpoint E that is
packets through the shared tree from source S has the option
switching to a delivery tree rooted at the source such that
from S to E traverse the shortest path (using whatever metric).
The endpoint representative of E obtains the flow-id to be used
the flow. The flow-id is constructed equivalently to the
(Source-EID, G). Note that the flow-id must be unique to
particular multicast flow. This is not the only method or
even the best method for obtaining a flow id. Alternate methods
obtaining the flow-id are discussed in section 5.5.
The representative for E initiates a Tree-Join toward S with
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
a shortest path route (based on the chosen metric, typically,
delay) from the source to the endpoint. We note that the
of the route is constrained by the amount of routing
available, directly or indirectly, to the route agent. The
Route is the reverse of the route thus obtained
A comment on the difference between the shortest-path trees
using the RPF tree as in [DEF+94b, DC90] and the trees that are
obtained here. When using the RPF scheme, the packets from
source S to the endpoint E follow a path that is the shortest
from E to S. This is the desired path if and only if the path
symmetric in either direction. However, in the mechanism
here for Nimrod, the packets do follow the "actual" shortest
from S to E whether or not the path is symmetric
The NMFRep fields are obvious
Receiver-RP Communications: After the receiver has joined
source-rooted tree, it can optionally disassociate itself from
shared tree. This is done by initiating a Tree-Leave procedure
The representative sends a NMFReq packet toward the RP with
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
as mentioned in section 5.2. When the receiver gets back the
packet, the receiver has left the shared tree
Source Tree Data Forwarding: Packets from the source contain
flow-id that was used to join the source tree for a given
group. Forwarding agents simply use the state created by the Tree
Join procedure in order to duplicate and forward packets toward
receivers
Ramanathan Informational [Page 19]
RFC 2102 Nimrod Multicast Support February 1997
5.5 Miscellaneous
Obtaining the Flow-Id: In the above scheme the flow-id for
particular multicast group G was obtained by combining the RP-EID
the group set-id (G-SID) (in case of shared tree) or by combining
Source-EID and the G-SID (in case of source-based tree).
disadvantage of this approach is that the bit-length of EID/SID
potentially high (more than 64 bits) and thus the flow-id could
very long. While there do exist bit-based data structures and
algorithms (such as Patricia Trees) that may be used for an
implementation, it is worth considering some other methods in lieu
using the EID/SID combination. We describe some methods below :
1. For shared trees, the flow-id for a particular group G may be
and updated in the association database. Since we have to use
association database anyway to obtain the RP-EID, these does not
much additional burden
However, this cannot be used efficiently for source-based trees
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
does an RP-Register, it could send the RP the flow-id that it wishes
be used by receivers when they switch to a source-based tree.
could be included in the RP-Register message. The RP could
multicast that flow-id to all receivers in a special packet. When
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
the NMFReq when doing a Tree-Join. The correct flow-id to be used
returned in the NMFRep message generated by the forwarding agent
the new branch meets the existing tree. Forwarding agents in the
of the NMFRep packet update the state information by rewriting
dummy flow-id by the correct flow-id contained in the NMFRep packet
This requires the re-definition of the NMFRep packet. Note that
there must be space for two flow-ids in the NMFRep packet - one for
"dummy" flow-id and the other for the "correct" flow-id that
replace the dummy flow-id
We claim that each of the above schemes achieves synchronization
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
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
multicast protocol when the group membership is densely
within the internetwork. In this mode, no Rendezvous Points are
and a source rooted tree is formed based on Reverse Path
in a manner similar to that of DVMRP [DC90].
We do not give details of how Nimrod can implement Dense
Multicast here
Multiple RPs: Our discussion above has been based on the
that there is one RP per group. PIM allows more than one RP
group. We do not discuss multiple-RP PIM here
6 Security
Security issues are not discussed in this memo
7
o Nimrod does not specify a particular multicast route
algorithm or state creation procedure. Nimrod can accommodate
multicast techniques and leaves the choice of the technique to
particular instantiation of Nimrod
o A solution for multicasting within Nimrod should be capable of
- Scaling to large networks, large numbers of multicast groups
large multicast groups
- Supporting policy, including quality of service and
restrictions
- Resource sharing
- Interoperability with other solutions
o Multicasting typically requires the setting up of state in
routers for packet forwarding. The state setup may be initiated by
sender (e.g., IDPR), by the receiver (e.g., CBT), by both (e.g., PIM
or by neither. The architecture of Nimrod provides
flexibility to accommodate any of these approaches
o A receiver-initiated multicast protocol, PIM, is being designed by
IDMR working group of the IETF. The facilities provided by Nimrod
the use of PIM as a multicast protocol quite straightforward
Ramanathan Informational [Page 21]
RFC 2102 Nimrod Multicast Support February 1997
8
[BFC93] A. J. Ballardie, P. F. Francis, and J. Crowcroft. Core
trees. In Proceedings of ACM SIGCOMM, 1993.
[CCS96] Castineyra, I., Chiappa, N., and M. Steenstrup, "The
Routing Architecture", RFC 1992, August 1996.
[DC90] S. Deering and D. Cheriton. Multicast routing in
internetworks and extended lans. ACM Transactions on
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
groups, Work in Progress
[DM78] Y. K. Dalal and R. M. Metcalfe. Reverse path forwarding
broadcast packets. Communications of the ACM, 21(12),
1040--1048, 1978.
[Moy92] Moy, J., "Multicast Extensions to OSPF, RFC 1584, March 1994.
[RS96] Ramanathan, S., and M. Steenstrup, "Nimrod functional
protocol specifications, Work in Progress
[Ste] Steenstrup, M., "Inter-domain policy routing
specification: Version 2", Work in Progress
Ramanathan Informational [Page 22]
RFC 2102 Nimrod Multicast Support February 1997
9
We thank Isidro Castineyra (BBN), Charles Lynn (BBN),
Steenstrup (BBN) and other members of the Nimrod Working Group
their comments and suggestions on this memo
10 Author's
Ram
BBN Systems and
10 Moulton
Cambridge, MA 02138
Phone: (617) 873-2736
EMail: ramanath@bbn.
Ramanathan Informational [Page 23]
if you see any problems within the linking, don't worry be happy,
this is version 0.1 of the Relevance System and you gotta expect some crappy subroutines sometimes,
just be content we did not write this in Java, which would have made this "bigger and better" HAHAHHA.
RFC documents can be found at I.E.T.F.
Relevance System Copyright © 2002 Spectrum WorldResearch
other technical nosh by ServerMasters Corporation
collaboration of BobX
