draft-ietf-idmr-pim-sm-spec-05.txt   draft-ietf-idmr-pim-sm-spec-06.txt 
Network Working Group Steven Deering (XEROX) Network Working Group Deborah Estrin (USC)
Internet Draft Deborah Estrin (USC) Internet Draft Dino Farinacci (CISCO)
Dino Farinacci (CISCO)
Mark Handley (UCL)
Ahmed Helmy (USC) Ahmed Helmy (USC)
David Thaler (UMICH)
Steven Deering (XEROX)
Mark Handley (UCL)
Van Jacobson (LBL) Van Jacobson (LBL)
Chinggung Liu (USC) Chinggung Liu (USC)
Puneet Sharma (USC) Puneet Sharma (USC)
David Thaler (UMICH) Liming Wei (CISCO) *
Liming Wei (CISCO)
Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol
Specification Specification
Status of This Memo Status of This Memo
This document is an Internet Draft. Internet Drafts are working This document is an Internet Draft. Internet Drafts are working
documents of the Internet Engineering Task Force (IETF), its Areas, documents of the Internet Engineering Task Force (IETF), its Areas,
and its Working Groups. (Note that other groups may also distribute and its Working Groups. (Note that other groups may also distribute
working documents as Internet Drafts). working documents as Internet Drafts).
Internet Drafts are draft documents valid for a maximum of six Internet Drafts are draft documents valid for a maximum of six
months. Internet Drafts may be updated, replaced, or obsoleted by months. Internet Drafts may be updated, replaced, or obsoleted by
other documents at any time. It is not appropriate to use Internet other documents at any time. It is not appropriate to use Internet
Drafts as reference material or to cite them other than as a Drafts as reference material or to cite them other than as a
``working'' draft'' or ``work in progress.'' ``working'' draft'' or ``work in progress.''
Please check the I-D abstract listing contained in each Internet Please check the I-D abstract listing contained in each Internet
Draft directory to learn the current status of this or any other Draft directory to learn the current status of this or any other
Internet Draft. Internet Draft.
[Page 1] [*] The author list has been reordered to reflect the involvement in
detailed editorial work on this specification document.
The first four authors are the primary editors and are listed
alphabetically.
The rest of the authors, also listed alphabetically, participated
in all aspects of the architectural and detailed design but
managed to get away without hacking the latex!
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 1]
1 Introduction 1 Introduction
This document describes a protocol for efficiently routing to This document describes a protocol for efficiently routing to
multicast groups that may span wide-area (and inter-domain) multicast groups that may span wide-area (and inter-domain)
internets. We refer to the approach as Protocol Independent internets. We refer to the approach as Protocol Independent
Multicast--Sparse Mode (PIM-SM) because it is not dependent on any Multicast--Sparse Mode (PIM-SM) because it is not dependent on any
particular unicast routing protocol, and because it is designed to particular unicast routing protocol, and because it is designed to
support sparse groups as defined in [1][2]. This document describes support sparse groups as defined in [1][2]. This document describes
the protocol details. For the motivation behind the design and a the protocol details. For the motivation behind the design and a
description of the architecture, see [1][2]. Section 2 summarizes description of the architecture, see [1][2]. Section 2 summarizes
PIM-SM operation. It describes the protocol from a network PIM-SM operation. It describes the protocol from a network
perspective, in particular, how the participating routers interact to perspective, in particular, how the participating routers interact to
create and maintain the multicast distribution tree. Section 3 create and maintain the multicast distribution tree. Section 3
describes PIM-SM operations from the perspective of a single router describes PIM-SM operations from the perspective of a single router
implementing the protocol; this section constitutes the main body of implementing the protocol; this section constitutes the main body of
the protocol specification. It is organized according to PIM-SM the protocol specification. It is organized according to PIM-SM
message type; for each message type we describe its contents, its message type; for each message type we describe its contents, its
generation, and its processing. generation, and its processing.
Section 4 provides packet format details. Sections 3.8 and 3.9 Sections 3.8 and 3.9 summarize the timers and flags referred to
summarize the timers and flags referred to throughout this document. throughout this document. Section 4 provides packet format details.
The most significant functional changes since the January '95 version The most significant functional changes since the January '95 version
involve the Rendezvous Point-related mechanisms, several resulting involve the Rendezvous Point-related mechanisms, several resulting
simplifications to the protocol, and removal of the PIM-DM protocol simplifications to the protocol, and removal of the PIM-DM protocol
details to a separate [3] (for clarity). details to a separate [3] (for clarity).
2 PIM-SM Protocol Overview 2 PIM-SM Protocol Overview
In this section we provide an overview of the architectural In this section we provide an overview of the architectural
components of PIM-SM. components of PIM-SM.
A router [*] A router receives explicit Join/Prune messages from those neighboring
routers that have downstream group members. The router then forwards
receives explicit Join/Prune messages from those neighboring routers data packets addressed to a multicast group, G, only onto those
that have downstream group members. The router then forwards data interfaces on which explicit joins have been received. Note that all
packets addressed to a multicast group, G, only onto those interfaces routers mentioned in this document are assumed to be PIM-SM capable,
on which explicit joins have been received. unless otherwise specified.
A Designated Router (DR) sends periodic Join/Prune messages toward a A Designated Router (DR) sends periodic Join/Prune messages toward a
group-specific Rendezvous Point (RP) for each group for which it has group-specific Rendezvous Point (RP) for each group for which it has
active members. Each router along the path toward the RP builds a active members. Each router along the path toward the RP builds a
wildcard (any-source) forwarding state. for the group and sends wildcard (any-source) state for the group and sends Join/Prune
_________________________ messages on toward the RP. We use the term route entry to refer to
[*] All routers mentioned in this document are assumed the state maintained in a router to represent the distribution tree.
to be PIM-SM capable, unless otherwise specified. A route entry may include such fields as the source address, the
group address, the incoming interface from which packets are
[Page 2] Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 2]
messages on toward the RP. We use the term entry to refer to the accepted, the list of outgoing interfaces to which packets are sent,
forwarding state maintained in a router to represent the distribution timers, flag bits, etc. The wildcard route entry's incoming interface
tree. Each entry includes such things as the incoming interface from points toward the RP; the outgoing interfaces point to the
which packets are accepted, the list of outgoing interfaces to which neighboring downstream routers that have sent Join/Prune messages
packets are sent, timers, flag bits, etc. The wildcard forwarding toward the RP. This state creates a shared, RP-centered, distribution
entry's incoming interface points toward the RP; the outgoing tree that reaches all group members. When a data source first sends
interfaces point to the neighboring downstream routers that have sent to a group, its DR unicasts Register messages to the RP with the
Join/Prune messages toward the RP. This forwarding state creates a source's data packets encapsulated within. If the data rate is high,
shared, RP-centered, distribution tree that reaches all group the RP can send source-specific Join/Prune messages back towards the
members. When a data source first sends to a group, its DR unicasts source and the source's data packets will follow the resulting
Register messages to the RP with the source's data packets forwarding state and travel unencapsulated to the RP. Whether they
encapsulated within. If the data rate is high, the RP can send arrive encapsulated or natively, the RP forwards the source's
source-specific Join/Prune messages back towards the source and the decapsulated data packets down the RP-centered distribution tree
source's data packets will follow the resulting forwarding state and toward group members. If the data rate warrants it, routers with
travel unencapsulated to the RP. Whether they arrive encapsulated or local receivers can join a source-specific, shortest path,
natively, the RP forwards the source's decapsulated data packets down distribution tree, and prune this source's packets off of the shared
the RP-centered distribution tree toward group members. If the data RP-centered tree. For low data rate sources, neither the RP, nor
rate warrants it, routers with local receivers can join a source- last-hop routers need join a source-specific shortest path tree and
specific, shortest path, distribution tree, and prune these source's data packets can be delivered via the shared, RP-tree.
packets off of the shared RP-centered tree. Even if all receivers
switch to the shortest path tree, state for that source will be kept
at the RP, so that new members that join the RP-centered tree will
receive data packets from the source. For low data rate sources,
neither the RP, nor last-hop routers need join a source-specific
shortest path tree and data packets can be delivered via the shared,
RP-tree.
The following subsections describe SM operation in more detail, in The following subsections describe SM operation in more detail, in
particular, the control messages, and the actions they trigger. particular, the control messages, and the actions they trigger.
Section 3 describes protocol operation from an implementors
perspective, i.e., the actions performed by a single router.
2.1 Local hosts joining a group 2.1 Local hosts joining a group
In order to join a multicast group, G, a host sends an IGMP Host- In order to join a multicast group, G, a host conveys its membership
Membership-Report message identifying the particular group. As information through the Internet Group Management Protocol (IGMP),
specified in [4], IGMP Host-Membership-Report messages are sent in as specified in [4][5], (see figure 1).
response to a directly-connected router's IGMP Host-Membership-Query From this point on we refer to such a host as
message (see figure 1) [*] From this point on we refer to such a a receiver, R, (or member) of the group G.
host as a receiver, R, (or member) of the group G.
_________________________ Note that all figures used in this section are for illustration and
[*] All figures used in this section are for illustra- are not intended to be complete. For complete and detailed protocol
tion and are not intended to be complete. For complete action see Section 3.
and detailed protocol action see Section 3 .
[Page 3] [Figures are present only in the postscript version]
Fig. 1 Example: how a receiver joins, and sets up shared tree Fig. 1 Example: how a receiver joins, and sets up shared tree
When a DR receives an IGMP Host-Membership-Report for a new group, G, When a DR (e.g., router A in figure 1) gets a membership
the DR looks up the associated RP. The DR (e.g., router A in figure indication from IGMP for a new group, G, the DR looks up the associated
1) creates a wildcard multicast forwarding entry for the group, RP. The DR creates a wildcard multicast route entry for the group,
referred to here as a (*,G) entry; if there is no more specific match referred to here as a (*,G) entry; if there is no more specific match
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 3]
for a particular source, the packet will be forwarded according to for a particular source, the packet will be forwarded according to
this entry. this entry.
The RP address is included in a special field in the forwarding entry The RP address is included in a special field in the route entry and
and is included in periodic upstream Join/Prune messages. The is included in periodic upstream Join/Prune messages. The outgoing
outgoing interface is set to that over which the IGMP Host- interface is set to that included in the IGMP membership
Membership-Report was received from the new member. The incoming indication for the new member.
interface is set to the interface used to send unicast packets to the The incoming interface is set to
RP. The RPT-bit flag associated with this entry is also set to 1, the interface used to send unicast packets to the RP.
indicating that this entry, (*,G), represents state on the shared
RP-tree. Each DR on the RP-tree with directly connected members sets When there are no longer directly connected members for the group,
a timer for this entry. If the timer expires and the DR has neither IGMP notifies the DR.
local members nor downstream receivers, the (*,G) state is deleted. If the DR has neither local members nor downstream
If the DR does have local members, it refreshes the (*,G) entry timer receivers, the (*,G) state is deleted.
each time it gets an IGMP Host-Membership-Report.
2.2 Establishing the RP-rooted shared tree 2.2 Establishing the RP-rooted shared tree
Triggered by the (*,G) state, the DR creates a Join/Prune message Triggered by the (*,G) state, the DR creates a Join/Prune message
with the RP address in its join list and the the WC-bit and RPT-bit with the RP address in its join list and the the wildcard bit (WC-
set to 1. The prune list is left empty. When the RPT-bit is set to 1 bit) and RP-tree bit (RPT-bit) set to 1. The WC-bit indicates that
it indicates that the join is associated with the shared RP-tree and any source may match and be forwarded according to this entry if
therefore the Join/Prune message is propagated along the RP-tree. there is no longer match; the RPT-bit indicates that this join is
When the WC-bit is set to 1 it indicates that the address is an RP being sent up the shared, RP-tree. The prune list is left empty. When
and the downstream receivers expect to receive packets from all the RPT-bit is set to 1 it indicates that the join is associated with
sources via this (shared tree) path; WC stands for wildcard the shared RP-tree and therefore the Join/Prune message is propagated
[*] along the RP-tree. When the WC-bit is set to 1 it indicates that the
address is an RP and the downstream receivers expect to receive
Each upstream router creates or updates its multicast forwarding packets from all sources via this (shared tree) path. The term RPT-
_________________________ bit is used to refer to both the RPT-bit flags associated with route
[*] Note that the term RPT-bit is used to refer to both entries, and the RPT-bit included in each encoded address in a
the RPT-bit flags associated with forwarding entries,
and the RPT-bit included in each encoded address in a
Join/Prune message. Join/Prune message.
[Page 4] Each upstream router creates or updates its multicast route entry for
entry for (*,G) when it receives a Join/Prune with the RPT-bit and (*,G) when it receives a Join/Prune with the RPT-bit and WC-bit set.
WC-bit set. The interface on which the Join/Prune message arrived is The interface on which the Join/Prune message arrived is added to the
added to the list of outgoing interfaces (oifs) for (*,G). Based on list of outgoing interfaces (oifs) for (*,G). Based on this entry
this entry each upstream router between the receiver and the RP sends each upstream router between the receiver and the RP sends a
a Join/Prune message in which the join list includes the RP. The Join/Prune message in which the join list includes the RP. The packet
packet payload contains Multicast-Address=G, Join=RP,WC-bit,RPT-bit, payload contains Multicast-Address=G, Join=RP,WC-bit,RPT-bit,
Prune=NULL. Prune=NULL.
2.3 Hosts sending to a group 2.3 Hosts sending to a group
When a host starts sending multicast data packets to a group, When a host starts sending multicast data packets to a group,
initially its DR must deliver each packet to the RP for distribution initially its DR must deliver each packet to the RP for distribution
down the RP-tree (see figure 2). The sender's DR initially down the RP-tree (see figure 2). The sender's DR initially
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 4]
encapsulates each data packet in a Register message and unicasts it encapsulates each data packet in a Register message and unicasts it
to the RP for that group. The RP decapsulates each Register message to the RP for that group. The RP decapsulates each Register message
and forwards the enclosed data packet natively to downstream members and forwards the enclosed data packet natively to downstream members
on the shared RP-tree. on the shared RP-tree.
[Figures are present only in the postscript version]
Fig. 2 Example: a host sending to a group Fig. 2 Example: a host sending to a group
If the data rate of the source warrants [*] If the data rate of the source warrants the use of a source-specific
shortest path tree (SPT), the RP may construct a new multicast route
the use of a source-specific shortest path tree (SPT), the RP may entry that is specific to the source, hereafter referred to as (S,G)
construct a new multicast forwarding entry that is specific to the state, and send periodic Join/Prune messages toward the source. Note
source, hereafter referred to as (S,G) state, and send periodic that over time, the rules for when to switch can be modified without
Join/Prune messages toward the source. The routers between the source global coordination. When and if the RP does switch to the SPT, the
and the RP build and maintain (S,G) state in response to these routers between the source and the RP build and maintain (S,G) state
messages and send (S,G) messages upstream toward the source. in response to these messages and send (S,G) messages upstream toward
the source.
The source's DR must stop encapsulating data packets in Registers The source's DR must stop encapsulating data packets in Registers
when (and so long as) it receives Register-Stop messages from the RP. when (and so long as) it receives Register-Stop messages from the RP.
The RP triggers Register-Stop messages in response to Registers, if The RP triggers Register-Stop messages in response to Registers, if
the RP has no downstream receivers for the group (or for that the RP has no downstream receivers for the group (or for that
particular source), or if the RP has already joined the (S,G) tree particular source), or if the RP has already joined the (S,G) tree
_________________________
[*] This decision is a local policy established at the
RP. For example, when the Register rate exceeds a con-
figured threshold at the RP, this may warrant the use
of the SPT.
[Page 5]
and is receiving the data packets natively. Each source's DR and is receiving the data packets natively. Each source's DR
maintains, per (S,G), a Register-bit and a Register-bit timer. The maintains, per (S,G), a Register-Suppression-timer. The Register-
Register-bit timer is started by the Register-Stop message; upon Suppression-timer is started by the Register-Stop message; upon
expiration, the Register-bit is set to 1 and the source's DR resumes expiration, the source's DR resumes sending data packets to the RP,
sending data packets encapsulated in Register messages. encapsulated in Register messages.
2.4 Switching from shared tree (RP-tree) to shortest path tree (SP- 2.4 Switching from shared tree (RP-tree) to shortest path tree (SP-
tree) tree)
When a router has directly-connected members, it first joins the A router with directly-connected members first joins the shared RP-
shared RP-tree. The router can switch to a source's shortest path tree. The router can switch to a source's shortest path tree (SP-
tree (SP-tree) after receiving packets from that source over the tree) after receiving packets from that source over the shared RP-
shared RP-tree. The recommended policy is to initiate the switch to tree. The recommended policy is to initiate the switch to the SP-tree
the SP-tree after receiving a significant number of data packets after receiving a significant number of data packets during a
during a specified time interval from a particular source. To realize specified time interval from a particular source. To realize this
this policy the router can monitor data packets from sources for policy the router can monitor data packets from sources for which it
which it has no source-specific multicast forwarding entry and has no source-specific multicast route entry and initiate such an
initiate such an entry when the data rate exceeds the configured entry when the data rate exceeds the configured threshold. As shown
threshold. As shown in figure 3, router `A' initiates a (S,G) state. in figure 3, router `A' initiates a (S,G) state.
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 5]
[Figures are present only in the postscript version]
Fig. 3 Example: Switching from shared tree to shortest path tree Fig. 3 Example: Switching from shared tree to shortest path tree
When a (S,G) entry is activated (and periodically so long as the When a (S,G) entry is activated (and periodically so long as the
state exists), a Join/Prune message is sent upstream towards the state exists), a Join/Prune message is sent upstream towards the
source, S, with S in the join list. The payload contains Multicast- source, S, with S in the join list. The payload contains Multicast-
Address=G, Join=S, Prune=NULL. When the (S,G) entry is created, the Address=G, Join=S, Prune=NULL. When the (S,G) entry is created, the
outgoing interface list is copied from (*,G), i.e., all local shared outgoing interface list is copied from (*,G), i.e., all local shared
tree branches are replicated in the new shortest path tree [*] In tree branches are replicated in the new shortest path tree. In this
this way when a data packet from S arrives and matches on this entry, way when a data packet from S arrives and matches on this entry, all
all receivers will continue to receive the source's packets along receivers will continue to receive the source's packets along this
this path. Note that (S,G) state must be maintained in each last-hop path. (In more complicated scenarios, other entries in the router
router that is responsible for initiating and maintaining an SP-tree. have to be considered, as described in Section 3). Note that (S,G)
[*] state must be maintained in each last-hop router that is responsible
_________________________ for initiating and maintaining an SP-tree. Even when (*,G) and (S,G)
[*] In more complicated scenarios, other entries in the overlap, both states are needed to trigger the source-specific
router have to be considered. For details see Section 3. Join/Prune messages. (S,G) state is kept alive by data packets
[*] By last-hop router we mean the router that delivers arriving from that source. A timer, Entry-timer, is set for the (S,G)
the packets to their ultimate end-system destination. entry and this timer is restarted whenever data packets for (S,G) are
This is the router that monitors if there is group forwarded out at least one oif, or Registers are sent. When the
membership and joins or prunes the appropriate distri- Entry-timer expires, the state is deleted. The last-hop router is the
router that delivers the packets to their ultimate end-system
[Page 6] destination. This is the router that monitors if there is group
Even when (*,G) and (S,G) overlap, both states are needed to trigger membership and joins or prunes the appropriate distribution trees in
the source-specific Join/Prune messages. (S,G) state is kept alive by response. In general the last-hop router is the Designated Router
data packets arriving from that source. A timer, S-timer, is set for (DR) for the LAN. However, under various conditions described later,
the (S,G) entry and this timer is restarted whenever a data packet a parallel router connected to the same LAN may take over as the
for (S,G) is forwarded out at least one oif. When the S-timer expires last-hop router in place of the DR.
the state is deleted.
Only the RP and routers with local members can initiate switching to Only the RP and routers with local members can initiate switching to
the SP-tree; intermediate routers do not. Consequently, last-hop the SP-tree; intermediate routers do not. Consequently, last-hop
routers create (S,G) state in response to data packets from the routers create (S,G) state in response to data packets from the
source, S; whereas intermediate routers only create (S,G) state in source, S; whereas intermediate routers only create (S,G) state in
response to Join/Prune messages from downstream that have S in the response to Join/Prune messages from downstream that have S in the
Join list [*] Join list.
The (S,G) entry is initialized with the SPT-bit cleared, indicating The (S,G) entry is initialized with the SPT-bit cleared, indicating
that the shortest path tree branch from S has not yet been setup that the shortest path tree branch from S has not yet been setup
completely, and the router can still accept packets from S that completely, and the router can still accept packets from S that
arrive on the (*,G) entry's indicated incoming interface (iif). [*] arrive on the (*,G) entry's indicated incoming interface (iif). Each
PIM multicast entry has an associated incoming interface on which
packets are expected to arrive.
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 6]
When a router with a (S,G) entry and a cleared SPT-bit starts to When a router with a (S,G) entry and a cleared SPT-bit starts to
receive packets from the new source S on the iif for the (S,G) entry, receive packets from the new source S on the iif for the (S,G) entry,
and that iif differs from the (*,G) entry's iif, the router sets the and that iif differs from the (*,G) entry's iif, the router sets the
SPT-bit, and sends a Join/Prune message towards the RP, indicating SPT-bit, and sends a Join/Prune message towards the RP, indicating
that the router no longer wants to receive packets from S via the that the router no longer wants to receive packets from S via the
shared RP-tree. The Join/Prune message sent towards the RP includes S shared RP-tree. The Join/Prune message sent towards the RP includes S
in the prune list, with the RPT-bit set indicating that S's packets in the prune list, with the RPT-bit set indicating that S's packets
should not be forwarded down this branch of the shared tree. If the must not be forwarded down this branch of the shared tree. If the
router receiving the Join/Prune message has (S,G) state (with or router receiving the Join/Prune message has (S,G) state (with or
without the forwarding entry's RPT-bit flag set), it deletes the without the route entry's RPT-bit flag set), it deletes the arriving
arriving interface from the (S,G) oif list. If the router has only interface from the (S,G) oif list. If the router has only (*,G)
(*,G) state, it creates an entry with the RPT-bit flag set to 1. For state, it creates an entry with the RPT-bit flag set to 1. For
brevity we refer to an (S,G) entry that has the RPT-bit flag set to 1 brevity we refer to an (S,G) entry that has the RPT-bit flag set to 1
_________________________
bution trees in response. In general the last-hop
router is the Desgnated Router (DR) for the LAN. Howev-
er, under various conditions described later, a paral-
lel router connected to the same LAN may take over as
the last-hop router in place of the DR.
[*] For example, to implement the policy that source-
specific trees are only setup for high-data rate
source, a last-hop router might not create a (S,G) en-
try until it has received m data packets from the
source within some interval of n seconds.
[*] As in DVMRP, each PIM multicast forwarding entry
has an associated incoming interface on which packets
are expected to arrive.
[Page 7]
as an (S,G)RPT-bit entry. This notational distinction is useful to as an (S,G)RPT-bit entry. This notational distinction is useful to
point out the different actions taken for (S,G) entries depending on point out the different actions taken for (S,G) entries depending on
the setting of the RPT-bit flag. Note that a router can have no more the setting of the RPT-bit flag. Note that a router can have no more
than one (S,G) entry for any particular S and G, at any particular than one active (S,G) entry for any particular S and G, at any
time; whether the RPT-bit flag is set or not. In other words, a particular time; whether the RPT-bit flag is set or not. In other
router never has both an (S,G) and an (S,G)RPT-bit entry for the same words, a router never has both an (S,G) and an (S,G)RPT-bit entry for
S and G at the same time. The Join/Prune message payload contains the same S and G at the same time. The Join/Prune message payload
Multicast-Address=G, Join=NULL, Prune=S,RPT-bit. contains Multicast-Address=G, Join=NULL, Prune=S,RPT-bit.
A new receiver may join an existing RP-tree on which source-specific A new receiver may join an existing RP-tree on which source-specific
prune state has been established (e.g., because downstream receivers prune state has been established (e.g., because downstream receivers
have switched to SP-trees). In this case the prune state must be have switched to SP-trees). In this case the prune state must be
eradicated upstream of the new receiver to bring all sources' data eradicated upstream of the new receiver to bring all sources' data
packets down to the new receiver. Therefore, when a (*,G) Join packets down to the new receiver. Therefore, when a (*,G) Join
arrives at a router that has any (Si,G)RPT-bit entries (i.e., entries arrives at a router that has any (Si,G)RPT-bit entries (i.e., entries
that cause the router to send source-specific prunes toward the RP), that cause the router to send source-specific prunes toward the RP),
these entries must be updated upstream of the router so as to bring these entries must be updated upstream of the router so as to bring
all sources' packets down to the new member. To accomplish this, each all sources' packets down to the new member. To accomplish this, each
router that receives a (*,G) Join/Prune message updates any existing router that receives a (*,G) Join/Prune message updates all existing
(S,G)RPT-bit entries. The router may also trigger a (*,G) join (S,G)RPT-bit entries. The router may also trigger a (*,G) Join/Prune
upstream to cause the same updating of RPT-bit settings upstream and message upstream to cause the same updating of RPT-bit settings
pull down all active sources' packets. If the arriving (*,G) join has upstream and pull down all active sources' packets. If the arriving
some sources included in its prune list, then the corresponding (*,G) join has some sources included in its prune list, then the
(S,G)RPT-bit entries are left unchanged (i.e., the RPT-bit remains corresponding (S,G)RPT-bit entries are left unchanged (i.e., the
set and no oif is added). RPT-bit remains set and no oif is added).
2.5 Steady state maintenance of distribution tree (i.e., router state) 2.5 Steady state maintenance of distribution tree (i.e., router state)
In the steady state each router sends periodic Join/Prune messages In the steady state each router sends periodic Join/Prune messages
for each active PIM forwarding entry; the Join/Prune messages are for each active PIM route entry; the Join/Prune messages are sent to
sent to the neighbor indicated in the iif field of the corresponding the neighbor indicated in the corresponding entry. These messages are
entry. These messages are sent periodically to capture state, sent periodically to capture state, topology, and membership changes.
topology, and membership changes. A Join/Prune message is also sent A Join/Prune message is also sent on an event-triggered basis each
on an event-triggered basis each time a new forwarding entry is time a new route entry is established for some new source (note that
established for some new source (note that some damping function may
be applied, e.g., a merge time). Join/Prune messages do not elicit Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 7]
any form of explicit acknowledgment; routers recover from lost some damping function may be applied, e.g., a short delay to allow
for merging of new Join information). Join/Prune messages do not
elicit any form of explicit acknowledgment; routers recover from lost
packets using the periodic refresh mechanism. packets using the periodic refresh mechanism.
2.6 Obtaining RP information 2.6 Obtaining RP information
To obtain the RP information, all routers within a PIM domain collect To obtain the RP information, all routers within a PIM domain collect
RP-Set messages. RP-Set messages are sent hop-by-hop within the Bootstrap messages. Bootstrap messages are sent hop-by-hop within the
domain; the domain's bootstrap router (BSR) is responsible for domain; the domain's bootstrap router (BSR) is responsible for
originating the RP-set messages. The BSR is elected dynamically originating the Bootstrap messages. Bootstrap messages are used to
within each domain. carry out a dynamic BSR election when needed and to distribute RP
information in steady state.
[Page 8]
[*]
Routers then use the set of RPs to get the proper Group to RP A domain in this context is a contiguous set of routers that all
mapping. Details are as follows: implement PIM and are configured to operate within a common boundary
defined by PIM Multicast Border Routers (PMBRs). PMBRs connect each
PIM domain to the rest of the internet.
A (small) set of routers, within a domain, are configured as Routers use a set of available RPs (called the {RP-Set}) distributed
candidate bootstrap routers. Initially, each of these candidates in Bootstrap messages to get the proper Group to RP mapping. The
includes its address in `RP-set' messages. Through a simple election following paragraphs summarize the mechanism; details of the
mechanism, a single bootstrap router (BSR) is elected for that domain mechanism may be found in Sections 3.6 and Appendix 6.2. A (small)
(see Section 3.6). set of routers, within a domain, are configured as candidate BSRs
and, through a simple election mechanism, a single BSR is selected
for that domain. A set of routers within a domain are also configured
as candidate RPs (C-RPs); typically these will be the same routers
that are configured as C-BSRs. Candidate RPs periodically unicast
Candidate-RP-Advertisement messages (C-RP-Advs) to the BSR of that
domain. C-RP-Advs include the address of the advertising C-RP, as
well as an optional group address and a mask length field, indicating
the group prefix(es) for which the candidacy is advertised. The BSR
then includes a set of these Candidate-RPs (the RP-Set), along with
the corresponding group prefixes, in Bootstrap messages it
periodically originates. Bootstrap messages are distributed hop-by-
hop throughout the domain.
A set of routers within a domain are configured as candidate RPs (C- Routers receive and store Bootstrap messages originated by the BSR.
RPs); typically these will be the same routers that are configured as When a DR gets a membership indication from IGMP for (or a data
C-BSRs. Candidate RPs periodically unicast Candidate-RP-Advertisement packet from) a directly connected host, for a group for which it
messages (C-RP-Advs) to the BSR of that domain. C-RP-Advs include the has no entry, the DR uses a hash function to map the group address
address of the advertising C-RP, as well as an optional group address to one of the C-RPs whose Group-prefix includes the group (see
and a mask length field, indicating the group prefix(es) for which Section 3.7).
the candidacy is advertised. The BSR then includes a set of these The DR then sends a Join/Prune message towards (or unicasts Registers
Candidate-RPs in the RP-Set messages, along with the corresponding to) that RP.
group prefixes (see Section
3.6.2). RP-Set messages are periodically sent hop-by-hop throughout
the domain.
Routers receive and store RP-Set messages originated by the BSR. When The Bootstrap message indicates liveness of the RPs included therein.
a DR receives IGMP Host-Membership-Report (or a data packet) from a If an RP is included in the message, then it is tagged as `up' at the
directly connected host, for a group for which it has no entry, the
DR uses a hash function to map the pertinent group to one of the C-
RPs whose Group-prefix includes the group (see Section 3.7). The DR
then sends a Join/Prune message towards (or unicasts Registers to)
that RP.
The RP-Set message indicates liveness of the RPs included therein; if Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 8]
an RP is included in the message, then it is tagged as `up' at the routers; while RPs not included in the message are removed from the
routers, while RPs not included in the message are tagged as `down' list of RPs over which the hash algorithm acts. Each router continues
and removed from the list of RPs over which the hash algorithm acts. to use the contents of the most recently received Bootstrap message
Each router continues to use the contents of the most recently until it receives a new Bootstrap message.
received RP-set message until it receives a new RP-set message.
_________________________
[*] A domain in this context is a contiguous set of
routers that all implement PIM and are configured to
operate within a common boundary defined by PIM Multi-
cast Border Routers (PMBRs). PMBRs connect each PIM
domain to the rest of the internet.
[Page 9] If a PIM domain partitions, each area separated from the old BSR will
elect its own BSR, which will distribute an RP-Set containing RPs
that are reachable within that partition. When the partition heals,
another election will occur automatically and only one of the BSRs
will continue to send out Bootstrap messages. As is expected at the
time of a partition or healing, some disruption in packet delivery
may occur. This time will be on the order of the region's round-trip
time and the bootstrap router timeout value.
2.7 Interoperation with dense mode protocols such as DVMRP 2.7 Interoperation with dense mode protocols such as DVMRP
In order to interoperate with networks that run dense-mode, In order to interoperate with networks that run dense-mode,
broadcast and prune, protocols, such as DVMRP, all packets generated {broadcast and prune}, protocols, such as DVMRP, all packets generated
within a PIM-SM region must be pulled down to that region's PIM within a PIM-SM region must be pulled out to that region's PIM
Multicast Border Routers (PMBRs) and injected (i.e., broadcast) into Multicast Border Routers (PMBRs) and injected (i.e., broadcast) into
the DVMRP network. [*] the DVMRP network. A PMBR is a router that sits at the boundary of a
PIM-SM domain and interoperates with other types of multicast routers
To achieve this capability, a special entry type, referred to as such as those that run DVMRP. Generally a PMBR would speak both
(*,*,RP), must be supported by all PIM routers. For this reason we protocols and implement interoperability functions not required by
include details about (*,*,RP) entry handling in this general PIM regular PIM routers. To support interoperability, a special entry
specification. type, referred to as (*,*,RP), must be supported by all PIM routers.
For this reason we include details about (*,*,RP) entry handling in
this general PIM specification.
A data packet will match on a (*,*,RP) entry if there is no more A data packet will match on a (*,*,RP) entry if there is no more
specific entry (such as (S,G) or (*,G)) and the destination group specific entry (such as (S,G) or (*,G)) and the destination group
address in the packet maps to the RP listed in the (*,*,RP) entry. In address in the packet maps to the RP listed in the (*,*,RP) entry. In
this sense, a (*,*,RP) entry represents an aggregation of all the this sense, a (*,*,RP) entry represents an aggregation of all the
groups supported by that RP. PMBRs initialize (*,*,RP) state for each groups that hash to that RP. PMBRs initialize (*,*,RP) state for each
RP in the domain's RPset. The (*,*,RP) state causes the PMBRs to send RP in the domain's RPset. The (*,*,RP) state causes the PMBRs to send
Join/Prune messages toward each of the active RPs in the domain. As a (*,*,RP) Join/Prune messages toward each of the active RPs in the
result distribution trees are built that carry all data packets domain. As a result distribution trees are built that carry all data
originated within the PIM domain (and sent to the RPs) down to the packets originated within the PIM domain (and sent to the RPs) down
PMBRs. to the PMBRs.
PMBRs are also responsible for delivering externally-generated
packets to routers within the PIM domain. To do so, PMBRs initially
encapsulate externally-originated packets (i.e., received on DVMRP
interfaces) in Register messages and unicast them to the
corresponding RP within the PIM domain. The Register message has a
bit indicating that it was originated by a border router and the RP
caches the originating PMBR's address in the route entry so that
duplicate Registers from other PMBRs can be declined with a
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 9]
Register-Stop message.
All PIM routers must be capable of supporting (*,*,RP) state and All PIM routers must be capable of supporting (*,*,RP) state and
interpreting associated Join/Prune messages. We describe the handling interpreting associated Join/Prune messages. We describe the handling
of (*,*,RP) entries and messages throughout this document. However, of (*,*,RP) entries and messages throughout this document; however,
detailed PIM Multicast Border Router functions will be specified in a detailed PIM Multicast Border Router (PMBR) functions will be
separate interoperability document. specified in a separate interoperability document (see directory,
http://catarina.usc.edu/pim/interop/).
2.8 Multicast data packet processing 2.8 Multicast data packet processing
Data packets are processed in a manner similar to existing multicast Data packets are processed in a manner similar to other multicast
schemes. A router first performs a longest match on the source and schemes. A router first performs a longest match on the source and
group address in the data packet. A (S,G) entry is matched first if group address in the data packet. A (S,G) entry is matched first if
one exists; a (*,G) entry is matched otherwise. If neither state one exists; a (*,G) entry is matched otherwise. If neither state
exists, then a (*,*,RP) entry match is attempted as follows: the exists, then a (*,*,RP) entry match is attempted as follows: the
router hashes on G to identify the RP for group G, and looks for a router hashes on G to identify the RP for group G, and looks for a
_________________________
[*] A PMBR is a router that sits at the boundary of a
PIM-SM domain and interoperates with other types of
multicast routers such as those that run DVMRP. Gen-
erally a PMBR would speak both protocols and implement
interoperability functions not required by regular PIM
routers.
[Page 10]
(*,*,RP) entry that has this RP address associated with it. If none (*,*,RP) entry that has this RP address associated with it. If none
of the above exists, then the packet is dropped. If a state is of the above exists, then the packet is dropped. If a state is
matched, the router compares the interface on which the packet matched, the router compares the interface on which the packet
arrived to the incoming interface field in the matched forwarding arrived to the incoming interface field in the matched route entry.
entry. If the iif check fails the packet is dropped, otherwise the If the iif check fails the packet is dropped, otherwise the packet is
packet is forwarded to all interfaces listed in the outgoing forwarded to all interfaces listed in the outgoing interface list.
interface list.
Some special actions are needed to deliver packets continuously while Some special actions are needed to deliver packets continuously while
switching from the shared to shortest-path tree. In particular, when switching from the shared to shortest-path tree. In particular, when
a (S,G) entry is matched, incoming packets are forwarded as follows: a (S,G) entry is matched, incoming packets are forwarded as follows:
1 If the SPT-bit is set, then: 1 If the SPT-bit is set, then:
1 if the incoming interface is the same as a matching 1 if the incoming interface is the same as a matching
(S,G) iif, the packet is forwarded to the oif-list of (S,G) iif, the packet is forwarded to the oif-list of
(S,G). (S,G).
2 if the incoming interface is different than a matching 2 if the incoming interface is different than a matching
(S,G) iif , the packet is discarded. (S,G) iif , the packet is discarded.
2 If the SPT-bit is cleared, then: 2 If the SPT-bit is cleared, then:
1 if the incoming interface is the same as a matching 1 if the incoming interface is the same as a matching
(S,G) iif, the packet is forwarded to the oif-list of (S,G) iif, the packet is forwarded to the oif-list of
(S,G). In addition, the SPT bit is set for that entry (S,G). In addition, the SPT bit is set for that entry
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 10]
if the incoming interface differs from the incoming if the incoming interface differs from the incoming
interface of the (*,G) or (*,*,RP) entry. interface of the (*,G) or (*,*,RP) entry.
2 if the incoming interface is different than a matching 2 if the incoming interface is different than a matching
(S,G) iif, the incoming interface is tested against a (S,G) iif, the incoming interface is tested against a
matching (*,G) or (*,*,RP) entry. IF the iif is the matching (*,G) or (*,*,RP) entry. If the iif is the
same as one of those, the packet is forwarded to the same as one of those, the packet is forwarded to the
oif-list of the matching entry. oif-list of the matching entry.
3 Otherwise the iif does not match any entry for G and 3 Otherwise the iif does not match any entry for G and
the packet is discarded. the packet is discarded.
Data packets never trigger prunes. However, data packets may Data packets never trigger prunes. However, data packets may
trigger actions that in turn trigger prunes. For example, when trigger actions that in turn trigger prunes. For example, when
router B in figure 3 decides to switch to SP-tree at step 3, it router B in figure 3 decides to switch to SP-tree at step 3, it
[Page 11]
creates a (S,G) entry with SPT-bit set to 0. When data packets creates a (S,G) entry with SPT-bit set to 0. When data packets
from S arrive at interface 2 of B, B sets the SPT-bit to 1 from S arrive at interface 2 of B, B sets the SPT-bit to 1
since the iif for (*,G) is different than that for (S,G). This since the iif for (*,G) is different than that for (S,G). This
triggers the sending of prunes towards the RP. triggers the sending of prunes towards the RP.
2.9 Operation over Multi-access Networks 2.9 Operation over Multi-access Networks
This section describes a few additional protocol mechanisms This section describes a few additional protocol mechanisms
needed to operate PIM over multi-access networks: Designated needed to operate PIM over multi-access networks: Designated
Router election, Assert messages to resolve parallel paths, and Router election, Assert messages to resolve parallel paths, and
the Joiner bit to suppress redundant Joins on multi-access the Join/Prune-Suppression-Timer to suppress redundant Joins on
networks. multi-access networks.
2.9.1 Designated router election * Designated router election
When there are multiple routers connected to a multi-access When there are multiple routers connected to a multi-access
network, one of them should be chosen to operate as the network, one of them must be chosen to operate as the designated
designated router (DR) at any point in time. The DR is router (DR) at any point in time. The DR is responsible for
responsible for sending triggered Join/Prune and Register sending triggered Join/Prune and Register messages toward the
messages toward the RP [*] RP.
A simple designated router (DR) election mechanism is used for A simple designated router (DR) election mechanism is used for
both SM and traditional IP multicast routing. both SM and traditional IP multicast routing. Neighboring
routers send Hello messages to each other. The sender with the
Neighboring routers send Query messages to each other. The largest IP address assumes the role of DR. Each router connected
sender with the largest IP address assumes the role of DR. Each to the multi-access LAN sends the Hellos periodically in order
router connected to the multi-access LAN sends the Queries to adapt to changes in router status.
periodically in order to adapt to changes in router status.
2.9.2 Parallel paths to a source or the RP--Assert process Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 11]
* Parallel paths to a source or the RP--Assert
process
If a router receives a multicast datagram on a multi-access LAN If a router receives a multicast datagram on a multi-access LAN
from a source whose corresponding (S,G) outgoing interface list from a source whose corresponding (S,G) outgoing interface list
includes the interface to that LAN, the packet must be a includes the interface to that LAN, the packet must be a
duplicate. In this case a single forwarder must be elected. duplicate. In this case a single forwarder must be elected.
Using Assert messages addressed to `224.0.0.13' (ALL-PIM-ROUTERS Using Assert messages addressed to `224.0.0.13' (ALL-PIM-ROUTERS
group) on the LAN, upstream routers can resolve which one will group) on the LAN, upstream routers can resolve which one will
act as the forwarder. Downstream routers listen to the Asserts act as the forwarder. Downstream routers listen to the Asserts
so they know which one was elected, and therefore where to send so they know which one was elected, and therefore where to send
_________________________
[*] IGMP Queries are sent by a PIMv2 DR if it supports
IGMPv1. If a PIMv2 router is using IGMPv2 then Host
queries are not sent by the PIMv2 DR but by the IGMP
querier.
[Page 12]
subsequent Joins. Typically this is the same as the downstream subsequent Joins. Typically this is the same as the downstream
router's RPF (Reverse Path Forwarding) neighbor; but there are router's RPF (Reverse Path Forwarding) neighbor; but there are
circumstances where this might not be the case, e.g., when using circumstances where this might not be the case, e.g., when using
different unicast protocols. [*] multiple unicast routing protocols on that LAN. The RPF neighbor
for a particular source (or RP) is the next-hop router to which
packets are forwarded en route to that source (or RP); and
therefore is considered a good path via which to accept packets
from that source.
The upstream router elected is the one that has the shortest The upstream router elected is the one that has the shortest
distance to the source. Therefore, when a packet is received on distance to the source. Therefore, when a packet is received on
an outgoing interface a router sends an Assert message on the an outgoing interface a router sends an Assert message on the
multi-access LAN indicating what metric it uses to reach the multi-access LAN indicating what metric it uses to reach the
source of the data packet. The router with the smallest source of the data packet. The router with the smallest
numerical metric (with ties broken by highest address) will numerical metric (with ties broken by highest address) will
become the forwarder. All other upstream routers will delete the become the forwarder. All other upstream routers will delete the
interface from their outgoing interface list. The downstream interface from their outgoing interface list. The downstream
routers also do the comparison in case the forwarder is routers also do the comparison in case the forwarder is
different than the RPF neighbor. different than the RPF neighbor.
Associated with the metric is a metric preference value. This is Associated with the metric is a metric preference value. This is
provided to deal with the case where the upstream routers may provided to deal with the case where the upstream routers may
run different unicast routing protocols. The numerically smaller run different unicast routing protocols. The numerically smaller
metric preference is always preferred. The metric preference metric preference is always preferred. The metric preference is
should be treated as the high-order part of an assert metric treated as the high-order part of an assert metric comparison.
comparison. Therefore, a metric value can be compared with Therefore, a metric value can be compared with another metric
another metric value provided both metric preferences are the value provided both metric preferences are the same. A metric
same. A metric preference can be assigned per unicast routing preference can be assigned per unicast routing protocol and
protocol and needs to be consistent for all routers on the needs to be consistent for all routers on the multi-access
multi-access network. network.
Asserts are also needed for (*,G) entries since there may be Asserts are also needed for (*,G) entries since an RP-Tree and
parallel paths from the RP and sources to a multi-access an SP-Tree for the same group may both cross the same multi-
network. When an assert is sent for a (*,G) entry, the first bit access network. When an assert is sent for a (*,G) entry, the
in the metric preference (RPT-bit) is always set to 1 to first bit in the metric preference (RPT-bit) is always set to 1
indicate that this path corresponds to the RP tree, and that the to indicate that this path corresponds to the RP tree, and that
match should be done on (*,G) if it exists. Furthermore, the the match must be done on (*,G) if it exists. Furthermore, the
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 12]
RPT-bit is always cleared for metric preferences that refer to RPT-bit is always cleared for metric preferences that refer to
SP-tree entries; this causes an SP-tree path to always look SP-tree entries; this causes an SP-tree path to always look
better than an RP-tree path. When the SP-tree and RPtree cross better than an RP-tree path. When the SP-tree and RPtree cross
the same LAN, this mechanism eliminates the duplicates that the same LAN, this mechanism eliminates the duplicates that
would otherwise be carried over the LAN. would otherwise be carried over the LAN.
In case the packet, or the Assert message, matches on oif for In case the packet, or the Assert message, matches on oif for
_________________________
[*] The RPF neighbor for a particular source (or RP) is
the next-hop router to which packets are forwarded en
route to that source (or RP); and therefore is con-
sidered a good path via which to accept packets from
that source.
[Page 13]
(*,*,RP) entry, a (*,G) entry is created, and asserts take place (*,*,RP) entry, a (*,G) entry is created, and asserts take place
as if the matching state were (*,G). as if the matching state were (*,G).
The DR may lose the (*,G) Assert process to another router on The DR may lose the (*,G) Assert process to another router on
the LAN if there are multiple paths to the RP through the LAN. the LAN if there are multiple paths to the RP through the LAN.
From then on, the DR is no longer the last-hop router for local From then on, the DR is no longer the last-hop router for local
receivers and removes the LAN from its (*,G) oif list. The receivers and removes the LAN from its (*,G) oif list. The
winning router becomes the last-hop router and is responsible winning router becomes the last-hop router and is responsible
for sending (*,G) join messages to the RP. Asserts are rate for sending (*,G) join messages to the RP.
limited.
2.9.3 Join/Prune suppression * Join/Prune suppression
If a Join/Prune message arrives and matches on the incoming Join/Prune suppression may be used on multi-access LANs to
interface for an existing (S,G), (*,G), or (*,*,RP) entry, and reduce duplicate control message overhead; it is not required
the sender of the Join/Prune has a higher IP address than the for correct performance of the protocol. If a Join/Prune message
recipient of the message, the Joiner-bit in the recipient's arrives and matches on the incoming interface for an existing
multicast routing table entry is cleared to suppress further (S,G), (*,G), or (*,*,RP) route entry, and the Holdtime included
Join/Prune messages. A timer is set for the Joiner-bit; after it in the Join/Prune message is greater than the recipient's own
expires the recipient sets the Joiner-bit to resume further [Join/Prune-Holdtime] (with ties resolved in favor of the higher
periodic Join/Prunes for this entry. The Joiner-bit timer is IP address), a timer (the Join/Prune-Suppression-timer) in the
restarted each time a Join/Prune message is received from a recipient's route entry may be started to suppress further
higher-IP-addressed PIM neighbor. Join/Prune messages. After this timer expires, the recipient
triggers a Join/Prune message, and resumes sending periodic
Join/Prunes, for this entry. The Join/Prune-Suppression-timer
should be restarted each time a Join/Prune message is received
with a higher Holdtime.
2.10 Unicast Routing Changes 2.10 Unicast Routing Changes
When unicast routing changes, an RPF check is done on all active When unicast routing changes, an RPF check is done on all active
(S,G), (*,G) and (*,*,RP) entries, and all affected expected (S,G), (*,G) and (*,*,RP) entries, and all affected expected
incoming interfaces are updated. In particular, if the new incoming interfaces are updated. In particular, if the new
incoming interface appears in the outgoing interface list, it is incoming interface appears in the outgoing interface list, it is
deleted from the outgoing interface list. The previous incoming deleted from the outgoing interface list. The previous incoming
interface may be added to the outgoing interface list by a interface may be added to the outgoing interface list by a
subsequent Join/Prune from downstream. Join/Prune messages subsequent Join/Prune from downstream. Join/Prune messages
received on the current incoming interface are ignored. received on the current incoming interface are ignored.
Join/Prune messages received on new interfaces or existing Join/Prune messages received on new interfaces or existing
outgoing interfaces are not ignored. Other outgoing interfaces outgoing interfaces are not ignored. Other outgoing interfaces
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 13]
are left as is until they are explicitly pruned by downstream are left as is until they are explicitly pruned by downstream
routers or are timed out due to lack of appropriate Join/Prune routers or are timed out due to lack of appropriate Join/Prune
messages. If the router has a (S,G) entry with the SPT-bit set, messages. If the router has a (S,G) entry with the SPT-bit set,
and the updated iif(S,G) does not differ from iif(*,G) or and the updated iif(S,G) does not differ from iif(*,G) or
iif(*,*,RP), then the router resets the SPT-bit. iif(*,*,RP), then the router resets the SPT-bit.
The router must send a Join/Prune message with S in the Join The router must send a Join/Prune message with S in the Join
list out its new incoming interface to inform upstream routers list out any new incoming interfaces to inform upstream routers
that it expects multicast datagrams over the interface. It may that it expects multicast datagrams over the interface. It may
also send a Join/Prune message with S in the Prune list out the also send a Join/Prune message with S in the Prune list out the
old incoming interface, if the link is operational, to inform old incoming interface, if the link is operational, to inform
[Page 14]
upstream routers that this part of the distribution tree is upstream routers that this part of the distribution tree is
going away. going away.
2.11 PIM-SM for Inter-Domain Multicast 2.11 PIM-SM for Inter-Domain Multicast
Future documents will address the use of PIM-SM as a backbone Future documents will address the use of PIM-SM as a backbone
inter-domain multicast routing protocol. Design choices center inter-domain multicast routing protocol. Design choices center
primarily around the distribution and usage of RP information primarily around the distribution and usage of RP information
for wide area, inter-domain groups. for wide area, inter-domain groups.
2.12 Security 2.12 Security
All PIM control messages may use [5] to address security All PIM control messages may use [6] to address security
concerns. Security mechanisms are likely to be enhanced in the concerns. Security mechanisms are likely to be enhanced in the
near future. near future.
[Page 15] Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 14]
3 Detailed Protocol Description 3 Detailed Protocol Description
This section describes the protocol operations from the This section describes the protocol operations from the
perspective of an individual router implementation. In perspective of an individual router implementation. In
particular, for each message type we describe how it is particular, for each message type we describe how it is
generated and processed. generated and processed.
3.1 Query 3.1 Hello
Query messages are sent so neighboring routers can discover each Hello messages are sent so neighboring routers can discover each
other. other.
3.1.1 Sending Queries 3.1.1 Sending Hellos
Query messages are sent periodically between PIM neighbors. By Hello messages are sent periodically between PIM neighbors,
default they are transmitted every 30 seconds. This informs every [Hello-Period] seconds. This informs routers what
routers what interfaces have PIM neighbors. Query messages are interfaces have PIM neighbors. Hello messages are multicast
multicast using address 224.0.0.13 (ALL-PIM-ROUTERS group). The using address 224.0.0.13 (ALL-PIM-ROUTERS group). The packet
packet includes the holdtime for neighbors to keep the includes a Holdtime, set to [Hello-Holdtime], for neighbors to
information valid. The recommended holdtime is 3 times the query keep the information valid. Hellos are sent on all types of
transmission interval. By default the holdtime is 90 seconds. communication links.
Queries are sent on all types of communication links.
3.1.2 Receiving queries 3.1.2 Receiving Hellos
When a router receives a Query packet, it stores the IP address When a router receives a Hello message, it stores the IP address
for that neighbor, sets the PIM neighbor timer based on the for that neighbor, sets its Neighbor-timer for the Hello sender
Query holdtime, and determines the Designated Router (DR) for to the Holdtime included in the Hello, and determines the
that interface. The highest IP addressed system is elected DR. Designated Router (DR) for that interface. The highest IP
Each query received causes the DR's address to be updated. addressed system is elected DR. Each Hello received causes the
DR's address to be updated.
When a router that is the active DR receives a query from a new When a router that is the active DR receives a Hello from a new
neighbor (i.e., from an IP address that is not yet in the DRs neighbor (i.e., from an IP address that is not yet in the DRs
neighbor table), the DR unicasts its most recent RP-set neighbor table), the DR unicasts its most recent RP-set
information to the new neighbor. information to the new neighbor.
3.1.3 Timing out neighbor entries 3.1.3 Timing out neighbor entries
A periodic process is run to time out PIM neighbors that have A periodic process is run to time out PIM neighbors that have
not sent queries. If the DR has gone down, a new DR is chosen by not sent Hellos. If the DR has gone down, a new DR is chosen by
scanning all neighbors on the interface and selecting the new DR scanning all neighbors on the interface and selecting the new DR
to be the one with the highest IP address. If an interface has to be the one with the highest IP address. If an interface has
gone down, the router may optionally time out all PIM neighbors gone down, the router may optionally time out all PIM neighbors
associated with the interface. associated with the interface.
[Page 16] Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 15]
3.2 Join/Prune 3.2 Join/Prune
Join/Prune messages are sent to join or prune a branch off of Join/Prune messages are sent to join or prune a branch off of
the multicast distribution tree. A single message contains both the multicast distribution tree. A single message contains both
a join and prune list, either one of which may be null. Each a join and prune list, either one of which may be null. Each
list contains a set of source addresses, indicating the source- list contains a set of source addresses, indicating the source-
specific trees or shared tree that the router wants to join or specific trees or shared tree that the router wants to join or
prune. prune.
3.2.1 Sending Join/Prune Messages 3.2.1 Sending Join/Prune Messages
Join/Prune messages are merged such that a message sent to a Join/Prune messages are merged such that a message sent to a
particular upstream neighbor, N, includes all of the current particular upstream neighbor, N, includes all of the current
joined and pruned sources that are reached via N; according to joined and pruned sources that are reached via N; according to
unicast routing Join/Prune messages are multicast to all routers unicast routing Join/Prune messages are multicast to all routers
on multi-access networks with the target address set to the next on multi-access networks with the target address set to the next
hop router towards S or RP. Join/Prune messages are sent hop router towards S or RP. Join/Prune messages are sent every
periodically. Currently the period is set to 60 seconds. [*] [Join/Prune-Period] seconds. In the future we will introduce
mechanisms to rate-limit this control traffic on a hop by hop
In addition, certain events cause triggered Join/Prune messages basis, in order to avoid excessive overhead on small links. In
to be sent. addition, certain events cause triggered Join/Prune messages to
be sent.
3.2.1.1 Periodic Join/Prune Messages 3.2.1.1 Periodic Join/Prune Messages
A router sends a periodic Join/Prune message to each distinct A router sends a periodic Join/Prune message to each distinct
RPF neighbor associated with each (S,G), (*,G) and (*,*,RP) RPF neighbor associated with each (S,G), (*,G) and (*,*,RP)
entry. Join/Prune messages are only sent if the RPF neighbor is entry. Join/Prune messages are only sent if the RPF neighbor is
a PIM neighbor. A periodic Join/Prune message sent to a a PIM neighbor. A periodic Join/Prune message sent to a
particular RPF neighbor is constructed as follows: particular RPF neighbor is constructed as follows:
1 Each router determines the RP for a (*,G) entry by using 1 Each router determines the RP for a (*,G) entry by using
the hash function described. The RP address (with RP and WC the hash function described. The RP address (with RPT and
bits set) is included in the join list of a periodic WC bits set) is included in the join list of a periodic
Join/Prune message under the following conditions: Join/Prune message under the following conditions:
1 The Join/Prune message is being sent to the RPF 1 The Join/Prune message is being sent to the RPF
neighbor toward the RP for an active (*,G) or (*,*,RP) neighbor toward the RP for an active (*,G) or (*,*,RP)
entry, and entry, and
_________________________
[*] In the future we will introduce mechanisms to
rate-limit this control traffic on a hop by hop basis,
in order to avoid excessive overhead on small links.
[Page 17]
2 The outgoing interface list in the (*,G) or (*,*,RP) 2 The outgoing interface list in the (*,G) or (*,*,RP)
entry is non-NULL, or the router is the DR on the same entry is non-NULL, or the router is the DR on the same
interface as the RPF neighbor. interface as the RPF neighbor.
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 16]
2 A particular source address, S, is included in the join 2 A particular source address, S, is included in the join
list with the RP and WC bits cleared under the following list with the RPT and WC bits cleared under the following
conditions: conditions:
1 The Join/Prune message is being sent to the RPF 1 The Join/Prune message is being sent to the RPF
neighbor toward S, and neighbor toward S, and
2 There exists an active (S,G) entry with the RPT-bit 2 There exists an active (S,G) entry with the RPT-bit
flag cleared, and flag cleared, and
3 The oif list in the (S,G) entry is not null. 3 The oif list in the (S,G) entry is not null.
3 A particular source address, S, is included in the prune 3 A particular source address, S, is included in the prune
list with the RP and WC bits cleared under the following list with the RPT and WC bits cleared under the following
conditions: conditions:
1 The Join/Prune message is being sent to the RPF 1 The Join/Prune message is being sent to the RPF
neighbor toward S, and neighbor toward S, and
2 There exists an active (S,G) entry with the RPT-bit 2 There exists an active (S,G) entry with the RPT-bit
flag cleared, and flag cleared, and
3 The oif list in the (S,G) entry is null. 3 The oif list in the (S,G) entry is null.
4 A particular source address, S, is included in the prune 4 A particular source address, S, is included in the prune
list with the RPT-bit set and the WC bit cleared under the list with the RPT-bit set and the WC bit cleared under the
following conditions: following conditions:
1 The Join/Prune message is being sent to the RPF 1 The Join/Prune message is being sent to the RPF
neighbor toward the RP and there exists a (S,G) entry neighbor toward the RP and there exists a (S,G) entry
with the RPT-bit flag set and null oif list, or with the RPT-bit flag set and null oif list, or
2 The Join/Prune message is being sent to the RPF 2 The Join/Prune message is being sent to the RPF
[Page 18]
neighbor toward the RP, there exists a (S,G) entry neighbor toward the RP, there exists a (S,G) entry
with the RPT-bit flag cleared and SPT-bit set, and the with the RPT-bit flag cleared and SPT-bit set, and the
incoming interface toward S is different than the incoming interface toward S is different than the
incoming interface toward the RP, or incoming interface toward the RP, or
3 The Join/Prune message is being sent to the RPF 3 The Join/Prune message is being sent to the RPF
neighbor toward the RP, and there exists a (*,G) entry neighbor toward the RP, and there exists a (*,G) entry
and (S,G) entry for a directly connected source. and (S,G) entry for a directly connected source.
5 The RP address (with RP and WC bits set) is included in the Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 17]
prune list if: 5 The RP address (with RPT and WC bits set) is included in
the prune list if:
1 The Join/Prune message is being sent to the RPF 1 The Join/Prune message is being sent to the RPF
neighbor toward the RP and there exists a (*,G) entry neighbor toward the RP and there exists a (*,G) entry
with a null oif list (see Section 3.5.2). with a null oif list (see Section 3.5.2).
3.2.1.2 Triggered Join/Prune Messages 3.2.1.2 Triggered Join/Prune Messages
In addition to periodic messages, the following events will In addition to periodic messages, the following events will
trigger Join/Prune messages (the contents of triggered messages trigger Join/Prune messages if as a result, a) a new entry is
are the same as the periodic, described above): created, or b) the oif list changes from null to non-null or
non-null to null. The contents of triggered messages are the
same as the periodic, described above.
1 Receipt of an IGMP Host-Membership-Report message for a 1 Receipt of an indication from IGMP that the state of
group G will cause building or modifying corresponding directly-connected- membership has changed (i.e., new
(*,G) state, and subsequent triggering of upstream members have just joined `membership indication' or all
Join/Prune messages as follows: members have left), for a group G, may cause the last-hop
router to build or modify corresponding (*,G) state. When
IGMP indicates that there are no longer directly connected
members, the oif is removed from the oif list if the oif-
timer is not running. A Join/Prune message is triggered if
and only if a) a new entry is created, or b) the oif list
changes from null to non-null or non-null to null, as
follows :
1 If the receiving router does not have a forwarding 1 If the receiving router does not have a route entry
entry for G the router creates a (*,G) entry, with the for G the router creates a (*,G) entry, copies the oif
interface upon which the IGMP Host-Membership-Report list from the corresponding (*,*,RP) entry (if it
was received included in the oif list. The router exists), and includes the interface included in the
sends a Join/Prune message towards the RP with the RP IGMP membership indication in the oif list; as always,
address and RPT-bit and WC-bits set in the join list. the router never includes the entry's iif in the oif
A timer is initiated for each interface in the oif list. The router sends a Join/Prune message towards
list. Or, the RP with the RP address and RPT-bit and WC-bits set
in the join list. Or,
2 If the (*,G) already exists, the interface upon which 2 If a (S,G)RPT-bit or (*,G) entry already exists, the
the IGMP Host-Membership-Report was received is added interface included in the IGMP membership indication is
to the oif list (if it was not included already) and added to the oif list (if it was not included
the timer for that interface is restarted. already).
[Page 19] Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 18]
2 Receipt of a Join/Prune message for (S,G), (*,G) or 2 Receipt of a Join/Prune message for (S,G), (*,G) or
(*,*,RP) will cause building or modifying corresponding (*,*,RP) will cause building or modifying corresponding
state, and subsequent triggering of upstream Join/Prune state, and subsequent triggering of upstream Join/Prune
messages, in the following cases: messages, in the following cases:
1 When there is no current forwarding entry, the RP 1 When there is no current route entry, the RP address
address included in the Join/Prune message is checked included in the Join/Prune message is checked against
against the local RP-Set information. If it matches, the local RP-Set information. If it matches, an entry
an entry will be created. If the router has no RP-Set will be created and the new entry will in turn trigger
information it may discard the message, or optionally an upstream Join/Prune message. If the router has no
use the RP address included in the message. RP-Set information it may discard the message, or
optionally use the RP address included in the message.
The new entry will in turn trigger an upstream 2 When the outgoing interface list of an (S,G)RPT-bit
Join/Prune message. entry becomes null, the triggered Join/Prune message
will contain S in the prune list.
2 When the outgoing interface list of (S,G)RPT-bit entry 3 When there exists a (S,G)RPT-bit with null oif list,
is null, the triggered Join/Prune message will contain and an (*,G) Join/Prune message is received, the
S in the prune list. arriving interface is added to the oif list and a
(*,G) Join/Prune message is triggered upstream.
4 When there exists a (*,G) with null oif list, and a
(*,*,RP) Join/Prune message is received, the receiving
interface is added to the oif list and a (*,*,RP)
Join/Prune message is triggered upstream.
3 Receipt of a packet that matches on a (S,G) entry whose 3 Receipt of a packet that matches on a (S,G) entry whose
SPT-bit is cleared triggers the following if the packet SPT-bit is cleared triggers the following if the packet
arrived on the correct incoming interface and there is a arrived on the correct incoming interface and there is a
(*,G) or (*,*,RP) entry with a different incoming RPF (*,G) or (*,*,RP) entry with a different incoming
neighbor: a) the router sets the SPT-bit on the (S,G) interface: a) the router sets the SPT-bit on the (S,G)
entry, and b) if the iif of the (S,G) entry is different entry, and b) the router sends a Join/Prune message towards
from the iif of the local (*,G) or (*,*,RP) entries, the the RP with S and a set RPT-bit in the prune list.
router sends a Join/Prune message towards the RP with S and
a set RPT-bit in the prune list.
4 When a Join/Prune message is received for a group G, the 4 When a Join/Prune message is received for a group G, the
prune list is checked. If it contains a source for which prune list is checked. If the prune list contains a source
the receiving router has a corresponding active (S,G), or RP for which the receiving router has a corresponding
(*,G) or (*,*,RP) entry, and whose iif is that on which active (S,G), (*,G) or (*,*,RP) entry, and whose iif is
the Join/Prune was received, then a join for (S,G), (*,G) that on which the Join/Prune was received, then a join for
or (*,*,RP) is triggered to override the prune,
respectively. (This is necessary in the case of parallel
downstream routers connected to a multi-access network.)
5 When the RP fails, the RP will not be included in the RP- Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 19]
(S,G), (*,G) or (*,*,RP) is triggered to override the
prune, respectively. (This is necessary in the case of
parallel downstream routers connected to a multi-access
network.)
[Page 20] 5 When the RP fails, the RP will not be included in the
Set messages sent to all routers in that domain. This Bootstrap messages sent to all routers in that domain. This
triggers the DRs to send (*,G) Join/Prune messages towards triggers the DRs to send (*,G) Join/Prune messages towards
the new RP for the group, as determined by the RP-Set and the new RP for the group, as determined by the RP-Set and
the hash function [*] the hash function. As described earlier, PMBRs trigger
(*,*,RP) joins towards each RP in the RP-Set.
We do not trigger prunes onto interfaces for SM groups based on 6 When an entry's Join/Prune-Suppression timer expires, a
data packets. Data packets that arrive on the wrong incoming Join/Prune message is triggered upstream corresponding to
interface for an SM group are silently dropped. that entry, even if the outgoing interface has not
transitioned between null and non-null states.
3.2.1.3 Fragmentation 7 When the RPF neighbor changes (whether due to an Assert or
It is possible that a Join/Prune message changes in unicast routing), the router sets a random delay
constructed according to the preceeding rules could exceed the timer (the Random-Delay-Join-Timer) whose expiration
triggers sending of a Join/Prune message for the asserted
route entry to the Assert winner (if the Join/Prune
Suppression timer has expired.)
We do not trigger prunes onto interfaces based on data packets.
Data packets that arrive on the wrong incoming interface are
silently dropped. However, on point-to-point interfaces
triggered prunes may be sent as an optimization.
3.2.1.3 Fragmentation: It is possible that a Join/Prune message
constructed according to the preceding rules could exceed the
MTU of a network. In this case, the message can undergo semantic MTU of a network. In this case, the message can undergo semantic
fragmentation whereby information corresponding to different fragmentation whereby information corresponding to different
groups can be sent in different messages. However, if a groups can be sent in different messages. However, if a
Join/Prune message must be fragmented the complete prune list Join/Prune message must be fragmented the complete prune list
corresponding to a group G must be included in the same corresponding to a group G must be included in the same
Join/Prune message as the associated RP-tree Join for G. Join/Prune message as the associated RP-tree Join for G. If such
semantic fragmentation is not possible, IP fragmentation should
be used between the two neighboring hops.
3.2.2 Receiving Join/Prune Messages When a router receives a 3.2.2 Receiving Join/Prune Messages When a router receives a
Join/Prune message, it processes it as follows. Join/Prune message, it processes it as follows.
The receiver of the Join/Prune notes the interface on which the The receiver of the Join/Prune notes the interface on which the
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 20]
PIM message arrived, call it I. The receiver then checks to see PIM message arrived, call it I. The receiver then checks to see
if the Join/Prune message was addressed to the receiving router if the Join/Prune message was addressed to the receiving router
itself (i.e., the router's address appears in the Unicast itself (i.e., the router's address appears in the Unicast
Upstream Neighbor Router field of the the Join/Prune message) Upstream Neighbor Router field of the Join/Prune message). (If
[*] If the Join/Prune is for this router the following actions the router is connected to a multiaccess LAN, the message could
are taken. be intended for a different router.) If the Join/Prune is for
this router the following actions are taken.
For each Sj in the join list of the Join/Prune message: For each group address G, in the Join/Prune message, the
associated join list is processed as follows. We refer to each
address in the join list as Sj; Sj refers to the RP if the RPT-
bit and WC-bit are both set. For each Sj in the join list of the
Join/Prune message:
1 If an address, Sj, in the join list of the Join/Prune 1 If an address, Sj, in the join list of the Join/Prune
messagehas the RPT-bit and WC-bit set, then Sj is the RP messagehas the RPT-bit and WC-bit set, then Sj is the RP
address used by the downstream router(s) and the following address used by the downstream router(s) and the following
actions are taken: actions are taken:
1 If Sj is not the same as the receiving router's RP 1 If Sj is not the same as the receiving router's RP
mapping for G, the receiving router may ignore the mapping for G, the receiving router may ignore the
_________________________
[*] As described earlier, PMBRs trigger (*,*,RP) joins
towards each RP in the RP-Set.
[*] If the router is connected to a multiaccess LAN,
the message could be intended for a different router.
[Page 21]
Join/Prune message with respect to that group entry. Join/Prune message with respect to that group entry.
If the router does not have any RP-Set information, it If the router does not have any RP-Set information, it
may use the address Sj included in the Join/Prune may use the address Sj included in the Join/Prune
message as the RP for the group. message as the RP for the group.
2 If Sj is the same as the receiving router's RP mapping 2 If Sj is the same as the receiving router's RP mapping
for G, the receiving router adds I to the outgoing for G, the receiving router adds I to the outgoing
interface list of the (*,G) forwarding entry and sets interface list of the (*,G) route entry (if there is
the timer for that interface (if there is no (*,G) no (*,G) entry, the router creates one first) and sets
entry, the router creates one first). If a (*,*,RP) the Oif-timer for that interface to the Holdtime
entry exists, for the RP associated with G, then the specified in the Join/Prune message.
oif list of the newly created (*,G) entry is copied In addition, the Oif-Deletion-Delay for that interface
from that (*,*,RP) entry. is set to 1/3rd the Holdtime specified in the Join/Prune
message.
If a (*,*,RP) entry exists, for the RP associated with
G, then the oif list of the newly created (*,G) entry
is copied from that (*,*,RP) entry.
3 For each (Si,G) entry associated with group G, if Si 3 For each (Si,G) entry associated with group G, if Si
is not included in the prune list, and if I is not the is not included in the prune list, and if I is not the
iif then interface I is added to the oif list and iif then interface I is added to the oif list and
the timers are restarted for that interface in each the Oif-timer for that interface in each affected
affected entry. If the group address in the Join/Prune entry is increased (never decreased) to the Holdtime
message is `*' then every (*,G) and (S,G) entry, whose included in the Join/Prune message.
group address hashes to the RP indicated in the In addition, if the Oif-timer for that interface is
(*,*,RP) Join/Prune message, is updated accordingly increased, the Oif-Deletion-Delay for that interface
[*] is set to 1/3rd the Holdtime specified in the
Join/Prune message.
If the group address in the Join/Prune message is `*'
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 21]
then every (*,G) and (S,G) entry, whose group address
hashes to the RP indicated in the (*,*,RP) Join/Prune
message, is updated accordingly. A `*' in the group
field of the Join/Prune is represented by a group
address 224.0.0.0 and a group mask length of 4,
indicating a (*,*,RP) Join.
4 If the (Si,G) entry has its RPT-bit flag set to 1, and 4 If the (Si,G) entry has its RPT-bit flag set to 1, and
its oif list is the same as the (*,G) oif its oif list is the same as the (*,G) oif
list, then the (Si,G)RPT-bit entry is deleted, list, then the (Si,G)RPT-bit entry is deleted,
5 The incoming interface is set to the interface used to 5 The incoming interface is set to the interface used to
send unicast packets to the RP in the (*,G) forwarding send unicast packets to the RP in the (*,G) route
entry, i.e., RPF interface toward the RP. entry, i.e., RPF interface toward the RP.
2 For each address, Sj, in the join list whose RPT-bit and 2 For each address, Sj, in the join list whose RPT-bit and
WC-bit are not set, and for which there is no existing WC-bit are not set, and for which there is no existing
(Sj,G) forwarding entry, the router initiates one. (Sj,G) route entry, the router initiates one. The router
[*] creates a (S,G) entry and copies all outgoing interfaces
_________________________ from the (S,G)RPT-bit entry, if it exists. If there is no
[*] A `*' in the group field of the Join/Prune is (S,G) entry, the oif list is copied from the (*,G) entry;
represented by a group address 224.0.0.0 and a group and if there is no (*,G) entry, the oif list is copied from
mask length of 4, indicating a (*,*,RP) Join. the (*,*,RP) entry, if it exists. In all cases, the iif of
[*] The router creates a (S,G) entry and copies all the (S,G) entry is always excluded from the oif list.
[Page 22]
1 The outgoing interface for (Sj,G) is set to I. The 1 The outgoing interface for (Sj,G) is set to I. The
incoming interface for (Sj,G) is set to the interface incoming interface for (Sj,G) is set to the interface
used to send unicast packets to Sj (i.e., the RPF used to send unicast packets to Sj (i.e., the RPF
neighbor). neighbor).
2 If the interface, I, used to reach Sj, is the same as 2 If the interface used to reach Sj, is the same as I,
the outgoing interface being initialized, this this represents an error (or a unicast routing change)
represents an error (or a unicast routing change) and and the Join/Prune must not be processed.
the Join/Prune should not be processed.
3 For each address, Sj, in the join list of the Join/Prune 3 For each address, Sj, in the join list of the Join/Prune
message, for which there is an existing (Sj,G) forwarding message, for which there is an existing (Sj,G) route entry,
entry,
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 22]
1 If the RPT-bit is not set for Sj listed in the 1 If the RPT-bit is not set for Sj listed in the
Join/Prune message, but the RPT-bit flag is set on the Join/Prune message, but the RPT-bit flag is set on the
existing (Sj,G) entry, the router clears the RPT-bit existing (Sj,G) entry, the router clears the RPT-bit
flag on the (Sj,G) entry, sets the incoming interface flag on the (Sj,G) entry, sets the incoming interface
to point towards Sj for that (Sj,G) entry, and sends a to point towards Sj for that (Sj,G) entry, and sends a
Join/Prune message corresponding to that entry through Join/Prune message corresponding to that entry through
the new incoming interface; and the new incoming interface; and
2 If I is not the same as the existing incoming 2 If I is not the same as the existing incoming
interface, the router adds I to the list of outgoing interface, the router adds I to the list of outgoing
interfaces. interfaces.
3 The timer for I is restarted. 3 The Oif-timer for I is increased (never decreased)
to the Holdtime included in the Join/Prune message.
In addition, if the Oif-timer for that interface
is increased, the Oif-Deletion-Delay for that interface
is set to 1/3rd the Holdtime specified in the
Join/Prune message.
4 The (Sj,G) entry's SPT bit is cleared until data comes 4 The (Sj,G) entry's SPT bit is cleared until data comes
down the shortest path tree. down the shortest path tree.
_________________________ For each group address G, in the Join/Prune message, the
outgoing interfaces from the (S,G)RPT-bit entry, if it associated prune list is processed as follows. We refer to each
exists. If there is no (S,G) entry, the oif list is address in the prune list as Sp; Sp refers to the RP if the
copied from the (*,G) entry; and if there is no (*,G) RPT-bit and WC-bit are both set. For each Sp in the prune list
entry, the oif list is copied from the (*,*,RP) entry, of the Join/Prune message:
if it exists. In all cases, the iif of the (S,G) entry
is always excluded from the oif list.
[Page 23]
For each Sp in the prune list of the Join/Prune message:
1 For each address, Sp, in the prune list whose RPT-bit and 1 For each address, Sp, in the prune list whose RPT-bit and
WC-bit are cleared: WC-bit are cleared:
1 If there is an existing (Sp,G) forwarding entry, the 1 If there is an existing (Sp,G) route entry, the router
router schedules a deletion of I from the list of lowers the Oif-timer for I to its Oif-Deletion-Delay,
outgoing interfaces by lowering that oif timer to 5 allowing for other downstream routers on a multi-
seconds (unless it is already lower). The deletion is access LAN to override the prune. However, on point-
not executed until this timer expires, allowing for to-point links, the oif-timer is expired immediately.
other downstream routers on a multi-access LAN to
override the prune.
2 If the router has a current (*,G), or (*,*,RP), 2 If the router has a current (*,G), or (*,*,RP), route
forwarding entry, and if the existing (Sp,G) entry has entry, and if the existing (Sp,G) entry has its RPT-
its RPT-bit flag set to 1, then this (Sp,G)RPT-bit bit flag set to 1, then this (Sp,G)RPT-bit entry is
entry is maintained (not deleted) even if its outgoing maintained (not deleted) even if its outgoing
interface list is null. interface list is null.
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 23]
2 For each address, Sp, in the prune list whose RPT-bit is 2 For each address, Sp, in the prune list whose RPT-bit is
set and whose WC-bit cleared: set and whose WC-bit cleared:
1 If there is an existing (Sp,G) forwarding entry, the 1 If there is an existing (Sp,G) route entry, the router
router schedules a deletion of I from the list of lowers the entry's Oif-timer for I to its
outgoing interfaces by lowering that oif timer to 5 Oif-Deletion-Delay,
seconds (unless it is already lower). The deletion is allowing for other downstream routers on a multi-
not executed until this timer expires, allowing for access LAN to override the prune. However, on point-
other downstream routers on a multi-access LAN to to-point links, the oif-timer is expired immediately.
override the prune.
2 If the router has a current (*,G), or (*,*,RP), 2 If the router has a current (*,G), or (*,*,RP), route
forwarding entry, and if the existing (Sp,G) entry has entry, and if the existing (Sp,G) entry has its RPT-
its RPT-bit flag set to 1, then this (Sp,G)RPT-bit bit flag set to 1, then this (Sp,G)RPT-bit entry is
entry is maintained (not deleted) even if its outgoing not deleted, and the Entry-timer is restarted, even if
interface list is null. its outgoing interface list is null.
3 If (*,G), or corresponding (*,*,RP), state exists, but 3 If (*,G), or corresponding (*,*,RP), state exists, but
there is no (Sp,G) entry, an (Sp,G)RPT-bit entry is there is no (Sp,G) entry, an (Sp,G)RPT-bit entry is
created . The outgoing interface list is copied from created . The outgoing interface list is copied from
[Page 24]
the (*,G), or (*,*,RP), entry, with the interface, I, the (*,G), or (*,*,RP), entry, with the interface, I,
on which the prune was received, is deleted. Packets on which the prune was received, is deleted. Packets
from the pruned source, Sp, match on this state and from the pruned source, Sp, match on this state and
are not forwarded toward the pruned receivers. are not forwarded toward the pruned receivers.
4 If there exists a (Sp,G) entry, with or without the 4 If there exists a (Sp,G) entry, with or without the
RPT-bit set, the iif on which the prune was received, RPT-bit set, the oif-timer for I is expired, and the
I, is deleted from the oif list, and the entry Entry-timer is restarted.
timer is restarted.
3 For each address, Sp, in the prune list whose RPT-bit and 3 For each address, Sp, in the prune list whose RPT-bit and
WC-bit are both set: WC-bit are both set:
1 If there is an existing (*,G) entry, with Sp as the RP 1 If there is an existing (*,G) entry, with Sp as the RP
for G, the router schedules a deletion of I from the for G, the router lowers the entry's Oif-timer for I
list of outgoing interfaces by lowering that oif timer to its Oif-Deletion-Delay,
to 5 seconds (unless it is already lower). The allowing for other downstream routers
deletion is not executed until this timer expires, on a multi-access LAN to override the prune. However,
allowing for other downstream routers on a multi- on point-to-point links, the oif-timer is expired
access LAN to override the prune. immediately.
2 If the corresponding (*,*,RP) state exists, but there 2 If the corresponding (*,*,RP) state exists, but there
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 24]
is no (*,G) entry, a (*,G) entry is created. The is no (*,G) entry, a (*,G) entry is created. The
outgoing interface list is copied from (*,*,RP) entry, outgoing interface list is copied from (*,*,RP) entry,
with the interface, I, on which the prune was with the interface, I, on which the prune was
received, deleted. received, deleted.
3 If there exists a (*,G) entry, the interface on which
the prune was received, I, is deleted from the oif
list, and the entry timer is restarted.
For any new (S,G), (*,G) or (*,*,RP) entry created by an For any new (S,G), (*,G) or (*,*,RP) entry created by an
incoming Join/Prune message, the Joiner-bit is initialized incoming Join/Prune message, the SPT-bit is cleared (and if
to 1 and the SPT-bit is cleared. a Join/Prune-Suppression timer is used, it is left off.)
If the received Join/Prune does not indicate the router as its
target, then if the Join/Prune matches an existing (S,G), (*,G),
[Page 25]
or (*,*,RP) entry and the Join/Prune arrived on the iif for
that entry, then the router compares the IP address of the
generator of the Join/Prune, to its own IP address and sets the
Joiner-bit as follows.
1 If its own IP address is higher, the Joiner-bit in the
entry is set.
2 If its own IP address is lower, the Joiner-bit in the entry
is cleared, and the Joiner-bit timer is activated.
After the timer expires the Joiner-bit is set indicating further If the entry has a Join/Prune-Suppression timer associated with
periodic Join/Prunes should be sent for this entry. The Joiner- it, and if the received Join/Prune does not indicate the router
bit timer is restarted each time a Join/Prune message is as its target, then the receiving router examines the join and
received from a higher-IP-addressed PIM neighbor. prune lists to see if any addresses in the list `completely-
match' existing (S,G), (*,G), or (*,*,RP) state for which the
receiving router currently schedules Join/Prune messages. An
element on the join or prune list `completely-matches' a route
entry only if both the IP addresses and RPT-bit flag are the
same. If the incoming Join/Prune message completely matches an
existing (S,G), (*,G), or (*,*,RP) entry and the Join/Prune
arrived on the iif for that entry, then the router compares
the Holdtime included in the Join/Prune message, to its own
[Join/Prune-Holdtime]. If its own [Join/Prune-Holdtime] is
lower, the Join/Prune-Suppression-timer is started at the
[Join/Prune-Suppression-Timeout]. If the [Join/Prune-Holdtime]
is equal, the tie is resolved in favor of the Join/Prune Message
originator that has the higher IP address. When the Join/Prune
timer expires, the router triggers a Join/Prune message for the
corresponding entry(ies).
3.3 Register and Register-Stop 3.3 Register and Register-Stop
When a source first starts sending to a group its packets are When a source first starts sending to a group its packets are
encapsulated in Register messages and sent to the RP. If the encapsulated in Register messages and sent to the RP. If the
data rate warrants source-specific paths, the RP sets up source data rate warrants source-specific paths, the RP sets up source
specific state and starts sending (S,G) Join/Prune messages specific state and starts sending (S,G) Join/Prune messages
toward the source, with S in the join list. toward the source, with S in the join list.
3.3.1 Sending Registers and Receiving Register-Stops 3.3.1 Sending Registers and Receiving Register-Stops
Register messages are sent as follows: Register messages are sent as follows:
1 When a DR receives a packet from a directly connected 1 When a DR receives a packet from a directly connected
source, S [*] :
1 If there is no corresponding (S,G) entry, and the Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 25]
_________________________ source, S
[*] When a PMBR (e.g., a router that connects the PIM-
SM region to a dense mode region running DVMRP or PIM-
DM) receives a packet from a source in the dense mode
region, the router treats the packet as if it were from
a directly connected source. A separate document will
describe the details of interoperabiity.
[Page 26] 1 If there is no corresponding (S,G) entry, and the
router has RP-Set information, the DR creates one with router has RP-Set information, the DR creates one with
the Register-bit set to 1 and the RP address set the Register-Suppression-timer turned off and the RP
according to the hash function mapping for the address set according to the hash function mapping for
corresponding group. The Register-bit-timer is the corresponding group. The oif list is copied from
initialized to zero; the Register-bit-timer is non- existing (*,G) or (*,*,RP) entries, if they exist. The
zero only when the Register-bit is set to 0. iif of the (S,G) entry is always excluded from the oif
list.
2 If there is a (S,G) entry in existence, the DR simply 2 If there is a (S,G) entry in existence, the DR simply
restarts the corresponding S-timer (entry timer). restarts the corresponding Entry-timer.
2 If the new or previously-existing (S,G) entry has the When a PMBR (e.g., a router that connects the PIM-SM region
Register-bit set, the data packet is encapsulated in a to a dense mode region running DVMRP or PIM-DM) receives a
Register message and unicast to the RP for that group. The packet from a source in the dense mode region, the router
data packet is also forwarded according to (S,G) state in treats the packet as if it were from a directly connected
the DR if the oif list is not null; since a receiver may source. A separate document will describe the details of
join the SP-tree while the DR is still registering to the interoperability.
RP.
3 If the (S,G) entry has the Register-bit cleared, the data 2 If the new or previously-existing (S,G) entry's Register-
packet is not sent in a Register message, it is just Suppression-timer is not running, the data packet is
forwarded according to the (S,G) oif list. encapsulated in a Register message and unicast to the RP
for that group. The data packet is also forwarded according
to (S,G) state in the DR if the oif list is not null; since
a receiver may join the SP-tree while the DR is still
registering to the RP.
When the DR receives a Register-Stop message it clears the 3 If the (S,G) entry's Register-Suppression-timer is running,
Register-bit and restarts the Register-bit-timer in the the data packet is not sent in a Register message, it is
corresponding (S,G) entry(ies). just forwarded according to the (S,G) oif list.
When a Register-bit-timer expires, the corresponding entry(ies) When the DR receives a Register-Stop message, it restarts the
Register-bit is set to 1 to reinstigate encapsulation of data Register-Suppression-timer in the corresponding (S,G) entry(ies)
packets in Register messages. at [Register-Suppression-Timeout] seconds. If there is data to
be registered, the DR may send a null Register (a Register
message with a zero-length data portion in the inner IP packet)
to the RP, [Probe-Time] seconds before the Register-
Suppression-timer expires, to avoid sending occasional bursts of
traffic to an RP unnecessarily.
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 26]
3.3.2 Receiving Register Messages and Sending Register-Stops 3.3.2 Receiving Register Messages and Sending Register-Stops
When a router (i.e., the RP) receives a Register message, the When a router (i.e., the RP) receives a Register message, the
router does the following: router does the following:
1 Decapsulates the data packet, and checks for a 1 Decapsulates the data packet, and checks for a
corresponding (S,G) entry. corresponding (S,G) entry.
[Page 27] 1 If a (S,G) entry with cleared (0) SPT bit exists, and
1 If a (S,G) entry exists, the packet is forwarded but the received Register does not have the Null-
Register-Bit set to 1, the packet is forwarded; and
the SPT bit is left cleared (0). If the SPT bit is 1, the SPT bit is left cleared (0). If the SPT bit is 1,
the packet is dropped, and Register-Stop messages are the packet is dropped, and Register-Stop messages are
triggered. Register-Stops are rate limited. [*] triggered. Register-Stops should be rate-limited (in
an implementation-specific manner) so that no more
than a few are sent per round trip time. This prevents
a high datarate stream of packets from triggering a
large number of Register-Stop messages between the
time that the first packet is received and the time
when the source receives the first Register-Stop.
2 If there is no (S,G) entry, but there is a (*,G) 2 If there is no (S,G) entry, but there is a (*,G)
entry, or a (*,*,RP) entry with the RP corresponding entry, and the received Register does not have the
to G, the packet is forwarded according to that entry. Null-Register-Bit set to 1, the packet is forwarded
according to the (*,G) entry.
3 If there is a (*,*,RP) entry but no (*,G) entry, a 3 If there is a (*,*,RP) entry but no (*,G) entry, and
(*,G) or (S,G) entry is created and the oif is copied the Register received does not have the Null-
from the (*,*,RP) entry to the new entry. Register-Bit set to 1, a (*,G) or (S,G) entry is
created and the oif list is copied from the (*,*,RP)
entry to the new entry. The packet is forwarded
according to the created entry.
4 If there is no G or (*,*,RP) entry corresponding to G, 4 If there is no G or (*,*,RP) entry corresponding to G,
the packet is dropped, and a Register-Stop is the packet is dropped, and a Register-Stop is
triggered. triggered.
5 A ``Border bit'' bit is added to the Register message, 5 A ``Border bit'' bit is added to the Register message,
to facilitate interoperability mechanisms. PMBRs set to facilitate interoperability mechanisms. PMBRs set
this bit when registering for external sources (see this bit when registering for external sources (see
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 27]
Section 2.7). If the ``Border bit'' is set in the Section 2.7). If the ``Border bit'' is set in the
Register, the RP does the following: Register, the RP does the following:
1 If there is no matching (S,G) state, the RP 1 If there is no matching (S,G) state, but there
creates one, with a `PMBR' field. This field exists (*,G) or (*,*,RP) entry, the RP creates a
(S,G) entry, with a `PMBR' field. This field
holds the source of the Register (i.e. the outer holds the source of the Register (i.e. the outer
IP address of the register packet). The RP IP address of the register packet). The RP
triggers a (S,G) join towards the source of the triggers a (S,G) join towards the source of the
data packet, and clears the SPT bit for the (S,G) data packet, and clears the SPT bit for the (S,G)
entry, else entry. If the received Register is not a `null
Register' the packet is forwarded according to
_________________________ the created state. Else,
[*] Register-Stops should be rate limited so that no
more than a few are sent per round trip time. This
prevents a high datarate stream of packets from
triggering a large number of Register-stop messages
between the time that the first packet is received and
the time when the source receives the first Register-
Stop.
[Page 28]
2 If the `PMBR' field for the corresponding (S,G) 2 If the `PMBR' field for the corresponding (S,G)
entry matches the source of the Register packet, entry matches the source of the Register packet,
and the received Register is not a `null
Register', the decapsulated packet is forwarded
to the oif list of that entry. Else,
3 If the `PMBR' field for the corresponding (S,G)
entry matches the source of the Register packet,
the decapsulated packet is forwarded to the oif the decapsulated packet is forwarded to the oif
list of that entry, else list of that entry, else
3 The packet is dropped, and a Register-stop is 4 The packet is dropped, and a Register-stop is
triggered towards the source of the Register. triggered towards the source of the Register.
The (S,G) state timer is restarted by Registers arriving The (S,G) Entry-timer is restarted by Registers arriving
from that source to that group. from that source to that group.
2 If the matching (S,G) or (*,G) state contains a null oif 2 If the matching (S,G) or (*,G) state contains a null oif
list, the RP unicasts a Register-Stop message to the source list, the RP unicasts a Register-Stop message to the source
of the Register message; in the latter case, the source- of the Register message; in the latter case, the source-
address field, within the Register-Stop message, is set to address field, within the Register-Stop message, is set to
the wildcard value (all 0's). This message is not processed the wildcard value (all 0's). This message is not processed
by intermediate routers, hence no (S,G) state is by intermediate routers, hence no (S,G) state is
constructed between the RP and the source. constructed between the RP and the source.
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 28]
3 If the Register message arrival rate warrants it and there 3 If the Register message arrival rate warrants it and there
is no existing (S,G) entry, the RP sets up a (S,G) is no existing (S,G) entry, the RP sets up a (S,G) route
forwarding entry with the outgoing interface list, entry with the outgoing interface list, excluding iif(S,G),
excluding iif(S,G), copied from the (*,G) outgoing copied from the (*,G) outgoing interface list, its SPT-bit
interface list, its SPT-bit is initialized to 0. If a (*,G) is initialized to 0. If a (*,G) entry does not exist, but
entry does not exist, but there exists a (*,*,RP) entry there exists a (*,*,RP) entry with the RP corresponding to
with the RP corresponding to G , the oif list for (S,G) is G , the oif list for (S,G) is copied -excluding the iif-
copied -excluding the iif- from that (*,*,RP) entry. from that (*,*,RP) entry.
A timer is set for the (S,G) entry and this timer is A timer (Entry-timer) is set for the (S,G) entry and this
restarted by receipt of data packets for (S,G). The (S,G) timer is restarted by receipt of data packets for (S,G).
entry causes the RP to send a Join/Prune message for the The (S,G) entry causes the RP to send a Join/Prune message
indicated group towards the source of the register message. for the indicated group towards the source of the register
message.
If the (S,G) oif list becomes null, Join/Prune messages If the (S,G) oif list becomes null, Join/Prune messages
will not be sent towards the source, S. will not be sent towards the source, S.
3.4 Multicast Data Packet Forwarding 3.4 Multicast Data Packet Forwarding
Processing a multicast data packet involves the following steps: Processing a multicast data packet involves the following steps:
[Page 29] 1 Lookup route state based on a longest match of the source
1 Lookup forwarding state based on a longest match of the address, and an exact match of the destination address in
source address, and an exact match of the destination the data packet. If neither S, nor G, find a longest match
address in the data packet. If neither S, nor G, find a entry, and the RP for the packet's destination group
longest match entry, and the RP for the packet's address has a corresponding (*,*,RP) entry, then the
destination group address has a corresponding (*,*,RP) longest match does not require an exact match on the
entry, then the longest match does not require an exact destination group address. In summary, the longest match is
match on the destination group address. In summary, the performed in the following order: (1) (S,G), (2) (*,G). If
longest match is performed in the following order: (1) neither is matched, then a lookup is performed on (*,*,RP)
(S,G), (2) (*,G). If neither is matched, then a lookup is entries.
performed on (*,*,RP) entries.
2 If the packet arrived on the interface found in the 2 If the packet arrived on the interface found in the
matching-entry's iif field, and the oif list is not matching-entry's iif field, and the oif list is not
null: null:
1 Forward the packet to the oif list for that entry 1 Forward the packet to the oif list for that entry
and restarted the entry's timer if the matching entry and restart the Entry-timer if the matching entry is
is (S,G) [*] (S,G). Optionally, the (S,G) Entry-timer may be
restarted by periodic checking of the matching packet
count.
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 29]
2 If the entry is a (S,G) entry with a cleared SPT-bit, 2 If the entry is a (S,G) entry with a cleared SPT-bit,
and a (*,G) or associated (*,*,RP) also exists whose and a (*,G) or associated (*,*,RP) also exists whose
incoming interface is different than that for (S,G), incoming interface is different than that for (S,G),
set the SPT-bit for the (S,G) entry and trigger an set the SPT-bit for the (S,G) entry and trigger an
(S,G) RPT-bit prune towards the RP. (S,G) RPT-bit prune towards the RP.
3 If the source of the packet is a directly-connected 3 If the source of the packet is a directly-connected
host and the router is the DR on a multi-access host and the router is the DR on the receiving
network, check the Register-bit associated with the interface, check the Register-Suppression-timer
(S,G) entry. If it is set, then the router associated with the (S,G) entry. If it is not running,
encapsulates the data packet in a register message and then the router encapsulates the data packet in a
sends it to the RP. register message and sends it to the RP.
This covers the common case of a packet arriving on the RPF This covers the common case of a packet arriving on the RPF
interface to the source or RP and being forwarded to all interface to the source or RP and being forwarded to all
joined branches. It also detects when packets arrive on the joined branches. It also detects when packets arrive on the
SP-tree, and triggers their pruning from the RP-tree. If it SP-tree, and triggers their pruning from the RP-tree. If it
_________________________
[*] Optionally, the (S,G) timer may be restarted by
periodic checking of the matching packet count.
[Page 30]
is the DR for the source, it sends data packets is the DR for the source, it sends data packets
encapsulated in Registers to the RPs. encapsulated in Registers to the RPs.
3 If the packet matches to an entry but did not arrive on the 3 If the packet matches to an entry but did not arrive on the
interface found in the entry's iif field, check the interface found in the entry's iif field, check the
SPT-bit of the entry. If the SPT-bit is set, drop the SPT-bit of the entry. If the SPT-bit is set, drop the
packet. If the SPT-bit is cleared, then lookup the (*,G), packet. If the SPT-bit is cleared, then lookup the (*,G),
or (*,*,RP), entry for G. If the packet arrived on the or (*,*,RP), entry for G. If the packet arrived on the
iif found in (*,G), or the corresponding (*,*,RP), iif found in (*,G), or the corresponding (*,*,RP),
forward the packet to the oif list of the matching forward the packet to the oif list of the matching
entry. This covers the case when a data packet matches on a entry. This covers the case when a data packet matches on a
(S,G) entry for which the SP-tree has not yet been (S,G) entry for which the SP-tree has not yet been
completely established upstream. completely established upstream.
4 If the packet does not match to any entry, but the source 4 If the packet does not match any entry, but the source of
of the data packet is a local, directly-connected host, and the data packet is a local, directly-connected host, and
the router is the DR on a multi-access LAN and has RP-Set the router is the DR on a multi-access LAN and has RP-Set
information, the DR uses the hash function to determine the information, the DR uses the hash function to determine the
RP associated with the destination group, G. The DR then RP associated with the destination group, G. The DR creates
checks the Register-bit associated with the local sender a (S,G) entry, with the Register-Suppression-timer not
(if there is no such a Register-bit, a new register flag, running, encapsulates the data packet in a Register message
associated with the local sender, is created and set), and and unicasts it to the RP.
encapsulates the data packet in a Register message and
unicasts it to the RP.
5 If the packet does not match to any entry, and it is not a 5 If the packet does not match to any entry, and it is not a
local host or the router is not the DR, drop the packet. local host or the router is not the DR, drop the packet.
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 30]
3.4.1 Data triggered switch to shortest path tree (SP-tree) 3.4.1 Data triggered switch to shortest path tree (SP-tree)
Different criteria can be applied to trigger switching over from Different criteria can be applied to trigger switching over from
the RP-based shared tree to source-specific, shortest path the RP-based shared tree to source-specific, shortest path
trees. trees.
One proposed example is to do so based on data rate. For One proposed example is to do so based on data rate. For
example, when a (*,G), or corresponding (*,*,RP), entry is example, when a (*,G), or corresponding (*,*,RP), entry is
created, a data rate counter may be initiated at the last-hop created, a data rate counter may be initiated at the last-hop
routers. The counter is incremented with every data packet routers. The counter is incremented with every data packet
received for directly connected members of an SM group, if the received for directly connected members of an SM group, if the
longest match is (*,G) or (*,*,RP). If and when the data rate longest match is (*,G) or (*,*,RP). If and when the data rate
for the group exceeds a certain configured threshold (t1), the for the group exceeds a certain configured threshold (t1), the
router initiates `source-specific' data rate counters for the router initiates `source-specific' data rate counters for the
[Page 31]
following data packets. Then, each counter for a source, is following data packets. Then, each counter for a source, is
incremented when packets matching on (*,G), or (*,*,RP), are incremented when packets matching on (*,G), or (*,*,RP), are
received from that source. If the data rate from the particular received from that source. If the data rate from the particular
source exceeds a configured threshold (t2), a (S,G) entry is source exceeds a configured threshold (t2), a (S,G) entry is
created and a Join/Prune message is sent towards the source. If created and a Join/Prune message is sent towards the source. If
the RPF interface for (S,G) is the RPF interface for (S,G) is
not the same as that for (*,G) -or (*,*,RP), then the SPT-bit not the same as that for (*,G) -or (*,*,RP), then the SPT-bit
is cleared in the (S,G) entry. is cleared in the (S,G) entry.
Other configured rules may be enforced to cause or prevent Other configured rules may be enforced to cause or prevent
skipping to change at line 1336 skipping to change at line 1369
3.5 Assert 3.5 Assert
Asserts are used to resolve which of the parallel routers Asserts are used to resolve which of the parallel routers
connected to a multi-access LAN is responsible for forwarding connected to a multi-access LAN is responsible for forwarding
packets onto the LAN. packets onto the LAN.
3.5.1 Sending Asserts 3.5.1 Sending Asserts
The following Assert rules are provided when a multicast packet The following Assert rules are provided when a multicast packet
is received on an outgoing multi-access interface of an existing is received on an outgoing multi-access interface ``I'' of an
(S,G) entry: existing (S,G) entry:
1 Do unicast routing table lookup on source IP address from 1 Do unicast routing table lookup on source IP address from
data packet, and send assert on interface for source IP data packet, and send assert on interface ``I'' for source
address in data packet; include metric preference of IP address in data packet; include metric preference of
routing protocol and metric from routing table lookup. routing protocol and metric from routing table lookup.
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 31]
2 If route is not found, use metric preference of 0x7fffffff 2 If route is not found, use metric preference of 0x7fffffff
and metric 0xffffffff. and metric 0xffffffff.
When an assert is sent for a (*,G) entry, the first bit in the When an assert is sent for a (*,G) entry, the first bit in the
metric preference (the RPT-bit) is set to 1, indicating the data metric preference (the RPT-bit) is set to 1, indicating the data
packet is routed down the RP-tree. packet is routed down the RP-tree.
Asserts are rate-limited by the router. Asserts should be rate-limited in an implementation-specific
manner.
[Page 32]
3.5.2 Receiving Asserts 3.5.2 Receiving Asserts
When an assert is received the router performs a longest match When an Assert is received the router performs a longest match
on the source and group address in the assert message. The on the source and group address in the Assert message. The
router checks the first bit of the metric preference (RPT-bit). router checks the first bit of the metric preference (RPT-bit).
1 If the RPT-bit is set, the router first does a match on 1 If the RPT-bit is set, the router first does a match on
(*,G), or (*,*,RP), entries; if no matching entry is found, (*,G), or (*,*,RP), entries; if no matching entry is found,
the router matches (S,G) entries. it ignores the Assert.
2 If the RPT-bit is not set in the Assert, the router first 2 If the RPT-bit is not set in the Assert, the router first
does a match on (S,G) entries; if no matching entry is does a match on (S,G) entries; if no matching entry is
found, the router matches (*,G) or (*,*,RP) entries. found, the router matches (*,G) or (*,*,RP) entries.
3.5.2.1 Receiving Asserts on an entry's outgoing interface 3.5.2.1 Receiving Asserts on an entry's outgoing interface
If the interface that received the Assert message is in the If the interface that received the Assert message is in the
oif list of the matched entry, then this assert should be oif list of the matched entry, then this Assert is processed
processed by this router as follows: by this router as follows:
1 If the Assert's RPT-bit is set and the matching entry is 1 If the Assert's RPT-bit is set and the matching entry is
(*,*,RP), the router creates a (*,G) entry. If the Assert's (*,*,RP), the router creates a (*,G) entry. If the Assert's
RPT-bit is cleared and the matching entry is (*,G), or RPT-bit is cleared and the matching entry is (*,G), or
(*,*,RP), the router creates a (S,G)RPT-bit entry. (*,*,RP), the router creates a (S,G)RPT-bit entry.
Otherwise, no new entry is created in response to the
Assert.
2 Compare the metric received in the Assert with the one the 2 The router then compares the metric values received in the
router would have advertised in an assert. The metric Assert with the metric values associated with the matched
preference should be treated as the high-order part of an entry. The RPT-bit and metric preference (in that order)
assert metric comparison. If the value in the assert is are treated as the high-order part of an Assert metric
less than the router's value, delete the interface from the comparison. If the value in the Assert is less than the
entry. If the value is the same, compare IP addresses, if
the routers address is less than the assert sender, delete
the interface.
3 If the router has won the election and there are directly
connected members on the multi-access LAN, the router keeps
the interface in its outgoing interface list. It acts as
[Page 33] Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 32]
the forwarder for the LAN. router's value (with ties broken by the IP address, where
higher IP address wins), delete the interface from the
entry. When the deletion occurs for a (*,G) or (*,*,RP)
entry , the interface is also deleted from any associated
(S,G)RPT-bit or (*,G) entries, respectively. The Entry-
timer for the affected entries is restarted.
4 If the router won the election but there are no directly 3 If the router has won the election the router keeps the
connected members on the multi-access LAN, the router interface in its outgoing interface list. It acts as the
schedules to delete the interface. The LAN might be a stub forwarder for the LAN.
LAN with no members (and no downstream routers). If no
subsequent Join/Prunes are received, the router deletes the
interface from the outgoing interface list; otherwise it
keeps the interface in its outgoing interface and acts as
the forwarder for the LAN.
The winning router should send out an assert message including The winning router sends an Assert message containing its own
its own metric to that outgoing interface. This will cause other metric to that outgoing interface. This will cause other routers
routers on the LAN to prune that interface from their forwarding on the LAN to prune that interface from their route entries. The
entries. winning router sets the RPT-bit in the Assert message if a (*,G)
or (S,G)RPT-bit entry was matched.
3.5.2.2 Receiving Asserts on an entry's incoming interface 3.5.2.2 Receiving Asserts on an entry's incoming interface
If the Assert arrived on the incoming interface of an existing If the Assert arrived on the incoming interface of an existing
(S,G), (*,G), or (*,*,RP) entry, the Assert is processed as (S,G), (*,G), or (*,*,RP) entry, the Assert is processed as
follows. If the Assert message does not match the entry, follows. If the Assert message does not match the entry,
exactly, it is ignored; i.e, longest-match is not used in this exactly, it is ignored; i.e, longest-match is not used in this
case. If the Assert message does match exactly, then: case. If the Assert message does match exactly, then:
1 Downstream routers will select the upstream router with the 1 Downstream routers will select the upstream router with the
smallest metric as their RPF neighbor. If two metrics are smallest metric preference and metric as their RPF
the same, the highest IP address is chosen to break the neighbor. If two metrics are the same, the highest IP
tie. [*] address is chosen to break the tie. This is important so
that downstream routers send subsequent Joins/Prunes (in
2 If the downstream routers have downstream members, they SM) to the correct neighbor. An Assert-timer is initiated
must schedule a join to inform the upstream router that when changing the RPF neighbor to the Assert winner. When
packets should be forwarded on the multi-access network. the timer expires, the router resets its RPF neighbor
This will cause the upstream forwarder to cancel its according to its unicast routing tables to capture network
_________________________ dynamics and router failures.
[*] This is important so that downstream routers send
subsequent Joins/Prunes (in SM) to the correct neigh-
bor. An Assert timer is initiated when changing the RPF
neighbor to the Assert winner. When the timer expires
the router resets its RPF neighbor according to its un-
icast routing tables to capture failures of the Assert
winner.
[Page 34] 2 If the downstream routers have downstream members, and if
scheduled deletion of the interface. the Assert caused the RPF neighbor to change, the
downstream routers must trigger a Join/Prune message to
inform the upstream router that packets are to be forwarded
on the multi-access network.
3.6 Candidate-RP-Advertisements and RP-Set messages Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 33]
3.6 Candidate-RP-Advertisements and Bootstrap messages
Candidate-RP-Advertisements (C-RP-Advs) are periodic PIM Candidate-RP-Advertisements (C-RP-Advs) are periodic PIM
messages unicast by those routers that are configured as messages unicast to the BSR by those routers that are configured
Candidate-RPs (C-RPs). as Candidate-RPs (C-RPs).
RP-Set messages are periodic PIM messages originated by the Bootstrap messages are periodic PIM messages originated by the
Bootstrap router (BSR) within a domain, and forwarded hop-by-hop Bootstrap router (BSR) within a domain, and forwarded hop-by-hop
to distribute the current RP-set to all routers in that domain. to distribute the current RP-set to all routers in that domain.
The RP-Set messages also support a simple mechanism by which the The Bootstrap messages also support a simple mechanism by which
Candidate BSR (C-BSR) with the highest BSR-priority and IP the Candidate BSR (C-BSR) with the highest BSR-priority and IP
address (referred to as the preferred BSR) is elected as the BSR address (referred to as the preferred BSR) is elected as the BSR
for the domain [*] Sections 3.6.2 and 3.6.3 describe the for the domain. We recommend that each router configured as a
combined function of RP-Set messages as the vehicle for BSR C-RP also be configured as a C-BSR. Sections 3.6.2 and 3.6.3
election and RP-Set distribution. describe the combined function of Bootstrap messages as the
vehicle for BSR election and RP-Set distribution.
_________________________ A Finite State Machine description of the BSR election and RP-
[*] We recommend that each router configured as a C-RP Set distribution mechanisms is included in Appendix II.
also be configured as a C-BSR.
[Page 35]
3.6.1 Sending Candidate-RP-Advertisements 3.6.1 Sending Candidate-RP-Advertisements
C-RPs periodically unicast C-RP-Advs to the BSR for that domain. C-RPs periodically unicast C-RP-Advs to the BSR for that domain.
The interval for sending these messages is subject to local The interval for sending these messages is subject to local
configuration at the C-RP. A recommended default value is 60 configuration at the C-RP.
seconds.
Candidate-RP-Advertisements carry group address and group mask Candidate-RP-Advertisements carry group address and group mask
fields. This enables the advertising router to limit the fields. This enables the advertising router to limit the
advertisement to certain prefixes or scopes of groups. The advertisement to certain prefixes or scopes of groups. The
advertising router may enforce this scope acceptance when advertising router may enforce this scope acceptance when
receiving Registers or Join/Prune messages. receiving Registers or Join/Prune messages. C-RPs should send
C-RP-Adv messages with the Authoritative bit cleared.
3.6.2 Receiving C-RP-Advs and Originating RP-Set 3.6.2 Receiving C-RP-Advs and Originating Bootstrap
Upon receiving a C-RP-Adv, a router does the following: Upon receiving a C-RP-Adv, a router does the following:
1 If the router is not the elected BSR, it ignores the 1 If the router is not the elected BSR, it ignores the
message, else message, else
2 The BSR adds the RP address to its local pool of candidate 2 The BSR adds the RP address to its local pool of candidate
RPs, according to the associated group prefix(es) in the RPs, according to the associated group prefix(es) in the
C-RP-Adv message [*] The BSR may override the prefix
indicated in a C-RP-Adv. Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 34]
C-RP-Adv message. The BSR may apply a local policy to limit
the number of Candidate RPs included in the Bootstrap
message. The BSR may override the prefix indicated in a C-
RP-Adv unless the Authoritative bit in the C-RP-Adv is set.
The BSR keeps an RP-timer per RP in its local RP-set. The RP- The BSR keeps an RP-timer per RP in its local RP-set. The RP-
timer is initialized to the holdtime in the RP's C-RP-Adv. When timer is initialized to the Holdtime in the RP's C-RP-Adv. When
the timer expires, the corresponding RP is removed from the RP- the timer expires, the corresponding RP is removed from the RP-
set. The RP-timer is restarted by the C-RP-Advs from the set. The RP-timer is restarted by the C-RP-Advs from the
corresponding RP. corresponding RP.
The BSR also keeps an RP-Set timer to send RP-Set messages The BSR also uses its Bootstrap-timer to periodically send
periodically. In particular, when the RP-Set timer expires, the Bootstrap messages. In particular, when the Bootstrap-timer
BSR originates an RP-Set message on each of its PIM interfaces. expires, the BSR originates an Bootstrap message on each of its
The message is sent with a TTL of 1 to the `ALL-PIM-ROUTERS' PIM interfaces. The message is sent with a TTL of 1 to the
group. In steady state, the BSR originates RP-Set messages every `ALL-PIM-ROUTERS' group. In steady state, the BSR originates
60 seconds. At startup, the RP-Set timer is initialized to 180 Bootstrap messages periodically. At startup, the Bootstrap-timer
seconds, causing the first RP-Set message to be originated after is initialized to [Bootstrap-Timeout], causing the first
180 seconds, when/if the timer expires. For timer details see Bootstrap message to be originated only when and if the timer
Section 3.6.3. A DR unicasts an RP-Set message to new PIM expires. For timer details, see Section 3.6.3. A DR unicasts a
neighbors starting up, after receiving their Query messages. Bootstrap message to each new PIM neighbor, i.e., after the DR
_________________________ receives the neighbor's Hello message (it does so even if the
[*] The BSR may apply a local policy to limit the new neighbor becomes the DR).
number of Candidate RPs included in the RP-Set message.
[Page 36]
(since after DR election the new neighbor may become the new
DR.)
The RP-Set message is subdivided into sets of group-prefix,RP- The Bootstrap message is subdivided into sets of group-
Count,RP-addresses. The format of the RP-Set message allows prefix,RP-Count,RP-addresses. The format of the Bootstrap
`semantic fragmentation', if the length of the original RP-Set message allows `semantic fragmentation', if the length of the
message exceeds the packet maximum boundaries (see Section 4). original Bootstrap message exceeds the packet maximum boundaries
However, we recommend against configuring a large number of (see Section 4). However, we recommend against configuring a
routers as C-RPs, to reduce the semantic fragmentation required. large number of routers as C-RPs, to reduce the semantic
fragmentation required.
3.6.3 Receiving and Forwarding RP-Set 3.6.3 Receiving and Forwarding Bootstrap
Each router keeps an RP-Set timer, initialized to 180 seconds at Each router keeps a Bootstrap-timer, initialized to [Bootstrap-
startup. Timeout] at startup.
When a router receives RP-Set message sent to `ALL-PIM-ROUTERS' When a router receives Bootstrap message sent to `ALL-PIM-
group, it performs the following: ROUTERS' group, it performs the following:
1 If the message was not sent by the RPF neighbor towards the 1 If the message was not sent by the RPF neighbor towards the
BSR address included, the message is dropped. Else BSR address included, the message is dropped. Else
2 If the included BSR is not preferred over, and not equal 2 If the included BSR is not preferred over, and not equal
to, the currently active BSR: to, the currently active BSR:
1 If the RP-Set timer is not yet expired, or if the Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 35]
receiving router is a C-BSR, then the RP-Set message 1 If the Bootstrap-timer has not yet expired, or if the
is dropped. Else receiving router is a C-BSR, then the Bootstrap
message is dropped. Else
2 The RP-Set timer has expired and the receiving router 2 If the Bootstrap-timer has expired and the receiving
is not a C-BSR, so the receiving router stores the router is not a C-BSR, the receiving router stores the
RP-Set and BSR address and priority found in the RP-Set and BSR address and priority found in the
message, and restarts the timer with its maximum message, and restarts the timer by setting it to
value. The RP-Set message is then forwarded out all [Bootstrap-Timeout]. The Bootstrap message is then
PIM interfaces, excluding the one over which the forwarded out all PIM interfaces, excluding the one
message arrived, to `ALL-PIM-ROUTERS' group, with a over which the message arrived, to `ALL-PIM-ROUTERS'
TTL of 1. group, with a TTL of 1.
3 If the RP-Set message includes a BSR address that is 3 If the Bootstrap message includes a BSR address that is
preferred over, or equal to, the currently active BSR, the preferred over, or equal to, the currently active BSR, the
router resets its RP-Set timer to 180 seconds, and stores router restarts its Bootstrap-timer at [Bootstrap-Timeout]
the BSR address and RP-Set information. The RP-Set message seconds. and stores the BSR address and RP-Set information.
is then forwarded out all PIM interfaces, excluding the one
over which the message arrived, to `ALL-PIM-ROUTERS' group,
[Page 37] The Bootstrap message is then forwarded out all PIM
with a TTL of 1. interfaces, excluding the one over which the message
arrived, to `ALL-PIM-ROUTERS' group, with a TTL of 1.
4 If the receiving router has no current RP set information 4 If the receiving router has no current RP set information
and the RP-set was unicast to it from a directly connected and the Bootstrap was unicast to it from a directly
neighbor, the router stores the information as its new RP- connected neighbor, the router stores the information as
set. This covers the startup condition when a newly booted its new RP-set. This covers the startup condition when a
router obtains the RP-Set and BSR address from its DR. newly booted router obtains the RP-Set and BSR address from
its DR.
When a router receives a new RP-Set it checks if each of the RPs When a router receives a new RP-Set, it checks if each of the
referred to by existing state (i.e., by (*,G), (*,*,RP), or RPs referred to by existing state (i.e., by (*,G), (*,*,RP), or
(S,G)RPT-bit entries) is in the new RP-Set. If an RP is not in (S,G)RPT-bit entries) is in the new RP-Set. If an RP is not in
the new RP-set, that RP is considered unreachable and the hash the new RP-set, that RP is considered unreachable and the hash
algorithm (see below) is re-performed for each group with algorithm (see below) is re-performed for each group with
locally active state that previously hashed to that RP. This locally active state that previously hashed to that RP. This
will cause those groups to be distributed among the remaining will cause those groups to be distributed among the remaining
RPs. When the new RP-Set contains a new RP, the value of the new RPs. When the new RP-Set contains a new RP, the value of the new
RP is calculated for each group covered by that C-RP's Group- RP is calculated for each group covered by that C-RP's Group-
prefix. Any group for which the new RP's value is greater than prefix. Any group for which the new RP's value is greater than
the previously active RP's value is switched over to the new RP. the previously active RP's value is switched over to the new RP.
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 36]
3.7 Hash Function 3.7 Hash Function
The hash function is used by all routers within a domain, to map The hash function is used by all routers within a domain, to map
a group to one of the C-RPs from the RP-Set. For a particular a group to one of the C-RPs from the RP-Set. For a particular
group, G, the hash function uses only those C-RPs whose Group- group, G, the hash function uses only those C-RPs whose Group-
prefix covers G. The algorithm takes as input the group address, prefix covers G. The algorithm takes as input the group address,
and the addresses of the Candidate RPs, and gives as output one and the addresses of the Candidate RPs, and gives as output one
RP address to be used. RP address to be used.
The protocol requires that all routers hash to the same RP The protocol requires that all routers hash to the same RP
within a domain (except for transients). The following hash within a domain (except for transients). The following hash
function must be used in each router: function must be used in each router:
1 For each candidate RP address Ci in the Candidate-RP- 1 For each RP address C(i) in the RP-Set, whose Group-prefix
Set, whose Group-prefix covers G, compute a value: covers G, compute a value:
Value(G,M,Ci) =
1103515245 ((1103515245 (G&M)+12345) XOR Ci)+ 12345 mod 2^31 Value(G,M,C(i))=
where M is a hash-mask included in RP-Set messages. (1103515245 * ((1103515245 * (G&M)+12345) XOR C(i)) + 12345) mod 2^31
This hash-mask allows a small number of
consecutive groups (e.g., 4) to always hash to the same RP. where M is a hash-mask included in Bootstrap messages.
For instance, hierarchically-encoded data can be sent on This hash-mask allows a small number of consecutive groups
consecutive group addresses to get the same delay and (e.g., 4) to always hash to the same RP. For instance,
fate-sharing characteristics. hierarchically-encoded data can be sent on consecutive
group addresses to get the same delay and fate-sharing
characteristics.
[Page 38]
In standard C, this corresponds to: In standard C, this corresponds to:
srand(G & M); srand(G & M);
srand(rand() ^ Ci); srand(rand() ^ Ci);
value = rand(); value = rand();
This assumes the use of the BSD rand, which generates
32-bit numbers, rather than the System-V rand which
only generates 16-bit numbers.
2 The candidate with the highest resulting value is then 2 The candidate with the highest resulting value is then
chosen as the RP for that group, and its identity and hash chosen as the RP for that group, and its identity and hash
value are stored with the entry created. value are stored with the entry created.
Ties between C-RPs having the same hash value, are broken Ties between C-RPs having the same hash value, are broken
in advantage of the highest address. in advantage of the highest address.
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 37]
The hash function algorithm is invoked by a DR, upon reception The hash function algorithm is invoked by a DR, upon reception
of a packet, or IGMP Host-Membership-Report, for a group, for of a packet, or IGMP membership indication, for a group, for
which the DR has no entry. It is invoked by any router that has which the DR has no entry. It is invoked by any router that has
(*,*,RP) state when a packet is received for which there is no (*,*,RP) state when a packet is received for which there is no
corresponding (S,G) or (*,G) entry. Furthermore, the hash corresponding (S,G) or (*,G) entry. Furthermore, the hash
function is invoked by all routers upon receiving a Join/Prune function is invoked by all routers upon receiving a (*,G) or
message with WC-bit set. (*,*,RP) Join/Prune message.
3.8 Processing Timer Events 3.8 Processing Timer Events
In this subsection, we enumerate all timers that have been In this subsection, we enumerate all timers that have been
discussed or implied. Since some critical timer events are not discussed or implied. Since some critical timer events are not
associated with the receipt or sending of messages, they are not associated with the receipt or sending of messages, they are not
fully covered by earlier subsections. fully covered by earlier subsections.
Timers may either count up or count down. If they count up then Timers are implemented in an implementation-specific manner. For
expiration means that the timer has reached its configured example, a timer may count up or down, or may simply expire at a
maximum value. If they count down then expiration means that the specific time. Setting a timer to a value T means that it will
timer has reached zero. expire after T seconds.
In many cases, the values for timers come from Holdtime fields
in PIM control messages, in which case the default values used
in these Holdtime fields are shown in the tables below.
Otherwise, the default value used when setting the timer is
shown. In general, the default timeout value for state
information is three times the refresh period. For example,
Queries refresh Neighbor state and the default Query-timer
period is 30 seconds, so a default Neighbor-timer duration of 90
[Page 39]
seconds is included in the Holdtime field of the Queries.
In this version of the spec we suggest particular numerical
timer settings. A future version of the specification will
specify a mechanism for timers to be set as a function of the
outgoing link bandwidth.
3.8.1 Timers related to tree maintenance 3.8.1 Timers related to tree maintenance
Each (S,G), (*,G), and (*,*,RP) entry has multiple timers Each (S,G), (*,G), and (*,*,RP) route entry has multiple timers
associated with it: one for each interface in the outgoing associated with it: one for each interface in the outgoing
interface list, one for the multicast routing entry itself, and interface list, one for the multicast routing entry itself, and
one for the Joiner-bit. Each (S,G) and (*,G) entry also has an one optional Join/Prune-Suppression-Timer. Each (S,G) and (*,G)
Assert timer and an Assert-rate-limit timer. In addition, DR's entry also has an Assert-timer and a Random-Delay-Join-Timer for
have a Register-bit-timer for each (S,G) entry and every router use with Asserts. In addition, DR's have a Register-
has a single Join/Prune timer. Suppression-timer for each (S,G) entry and every router has a
single Join/Prune-timer. (A router may optionally keep separate
Join/Prune-timers for different interfaces or route entries if
different Join/Prune periods are desired.)
Because some of the outgoing interfaces in an (S,G) entry are * [Join/Prune-Timer] This timer is used for periodically
copied from the (*,G) outgoing interface list, they may not have sending aggregate Join/Prune messages. To avoid
explicit (S,G) join messages from some of the downstream routers synchronization among routers booting simultaneously, it is
(i.e., where members are joining to the (*,G) tree only). Thus, initially set to a random value between 1 and [Join/Prune-
when a timer is reset for an outgoing interface listed in a Period]. When it expires, the timer is immediately
(*,G) entry, the timers are reset for that interface in each restarted to [Join/Prune-Period]. A Join/Prune message is
existing (S,G) entry whose oif list contains that interface [*] then sent out each interface. This timer should not be
The same rule applies to (*,G) and (S,G) entries when resetting restarted by other events.
an oif timer on a (*,*,RP) entry.
_________________________ * [Join/Prune-Suppression-Timer (kept per route entry)] A
[*] If there are sources in the prune list of the (*,G)
join, then the timers for the arriving interface will
first be reset for those sources, and then this inter-
face will be deleted from these same entries; producing
a correct result, even though the updating of the ti-
mers was unnecessary. An implementation could optimize
this by checking the prune list before processing the
join list.
[Page 40] Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 38]
Timer DefVal Notes route entry's (optional) Join/Prune-Suppression-Timer may
be used to suppress duplicate joins from multiple
downstream routers on the same LAN. When a Join message is
received from a neighbor on the entry's incoming interface
in which the included Holdtime is higher than the router's
own [Join/Prune-Holdtime] (with ties broken by higher IP
address), the timer is set to [Join/Prune-Suppression-
Timeout], with some random jitter introduced to avoid
synchronization of triggered Join/Prune messages on
expiration. (The random timeout value must be < 1.5 *
[Join/Prune-Period] to prevent losing data after 2 dropped
Join/Prunes.) The timer is restarted every time a
subsequent Join/Prune message (with higher Holdtime/IP
address) for the entry is received on its incoming
interface. While the timer is running, Join/Prune messages
for the entry are not sent. This timer is idle (not
running) for point-to-point links.
Joiner-bit 90 Started : When Joiner bit is cleared * [Oif-Timer (kept per oif for each route entry)] A timer for
per route entry Reset by: Receiving Join from higher-IP neighbor on iif each oif of a route entry is used to time out that oif.
Action : Set Joiner bit Because some of the outgoing interfaces in an (S,G) entry
are copied from the (*,G) outgoing interface list, they may
not have explicit (S,G) join messages from some of the
downstream routers (i.e., where members are joining to the
(*,G) tree only). Thus, when an Oif-timer is restarted in a
(*,G) entry, the Oif-timer is restarted for that interface
in each existing (S,G) entry whose oif list contains that
interface. The same rule applies to (*,G) and (S,G) entries
when restarting an Oif-timer on a (*,*,RP) entry.
Join/Prune 60 Started : When booting The following table shows its usage when first adding the
Reset by: Nothing oif to the entry's oiflist, when it should be restarted
Action : Send Join/Prune to each RPF neighbor, restart timer (unless it is already higher), and when it should be
decreased (unless it is already lower).
oif 180 Started : When adding oif to oiflist Set to | When | Applies to
per (*,*,RP) oif Restarted by: Receiving (*,*,RP) Join on that iface included Holdtime | adding oif off Join/Prune | (S,G) (*,G) (*,*,RP)
Action : Remove oif from oiflist
oif 180 Started : When adding oif to oiflist Increased (only) to | When | Applies to
per (*,G) oif Restarted by: Receiving (*,G) Join or IGMP included Holdtime | received Join/Prune | (S,G) (*,G) (*,*,RP)
Host-Membership-Report for G on that iface, or (*,*,RP) oif-timer value | (*,*,RP) oif-timer restarted | (S,G) (*,G)
restartedting oif timer in (*,*,RP). (*,G) oif-timer value | (*,G) oif-timer restarted | (S,G)
Action : Remove oif from oiflist
oif 180 Started : When adding oif to oiflist Decreased (only) to | When | Applies to
per (S,G) oif Restarted by: Receiving (S,G) Join on that Oif-Deletion-Delay | prune received | (S,G) (*,G)
iface, or restartedting oif timer in (*,G) or
(*,*,RP).
Action : Remove oif from oiflist
(*,*,RP) entry 180 Started : When entry is created Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 39]
per (*,*,RP) Restarted by: Restartedting timer on any oif When the timer expires, the oif is removed from the oiflist
Action : Delete entry if there are no directly-connected members. When deleted,
the oif is also removed in any associated (S,G) or (*,G)
entries.
(*,G) entry 180 Started : When entry is created * [Entry-Timer (kept per route entry)] A timer for each route
per (*,G) Restarted by: Receiving (*,G) prune, entry is used to time out that entry. The following table
restarting timer on any oif, or receiving an summarizes its usage when first adding the oif to the
Assert with RPT-bit set. entry's oiflist, and when it should be restarted (unless it
Action : Delete entry and any associated is already higher).
(S,G)RPT-bit entries
(S,G) entry 180 Started : When entry is created Set to | When | Applies to
aka S-timer Restarted by: Forwarding data packet, [Data- Timeout] | created off data packet | (S,G)
per (S,G) receiving Register, receiving (S,G)RPT-bit included Holdtime | created off Join/Prune | (S,G) (*,G) (*,*,RP)
prune, restarting timer on any oif,
or receiving an Assert without RPT-bit set.
Action : Delete entry
Register-bit 60 Started : When Register bit is cleared by Increased (only) to | When | Applies to
per (S,G) receiving a Register-Stop [Data-Timeout] | receiving data packets | (S,G)no RPT-bit
Restarted by: Receiving Register-Stop oif-timer value | any oif-timer restarted | (S,G)RPT-bit (*,G) (*,*,RP)
[Assert-Timeout] | assert received | (S,G)RPT-bit (*,G) w/null oif
[Page 41] When the timer expires, the route entry is deleted; if the
Action : Set Register bit entry is a (*,G) or (*,*,RP) entry, all associated
(S,G)RPT-bit entries are also deleted.
Assert 180 Started : Receiving an Assert where the * [Register-Suppression-Timer (kept per (S,G) route entry)]
per (S,G) upstream RPF neighbor is not your unicast RPF An (S,G) route entry's Register-Suppression-Timer is used
and (*,G) neighbor. to suppress registers when the RP is receiving data packets
Restarted by: Receiving an Assert where the natively. When a Register-Stop message for the entry is
upstream RPF neighbor is not your unicast received from the RP, the timer is set to a random value in
RPF neighbor. the range 0.5 * [Register-Suppression-Timeout] to 1.5 *
Action : Change RPF neighbor to unicast RPF neighbor [Register-Suppression-Timeout]. While the timer is running,
Registers for that entry will be suppressed. If null
registers are used, a null register is sent [Probe-Time]
seconds before the timer expires.
Assert-Rate-limit 5 Started : When an Assert is sent * [Assert-Timer (per (S,G) or (*,G) route entry)] The
per (S,G) Restarted by: Nothing Assert-Timer for an (S,G) or (*,G) route entry is used for
and (*,G) Action : Allow asserts to be triggered by timing out Asserts received. When an Assert is received and
data packets the RPF neighbor is changed to the Assert winner, the
Assert-Timer is set to [Assert-Timeout], and is restarted
to this value every time a subsequent Assert for the entry
is received on its incoming interface. When the timer
expires, the router resets its RPF neighbor according to
3.8.2 Timers relating to neighbor discovery Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 40]
its unicast routing table.
Timer DefVal Notes * [Random-Delay-Join-Timer (per (S,G) or (*,G) route entry)]
The Random-Delay-Join-Timer for an (S,G) or (*,G) route
entry is used to prevent synchronization among downstream
routers on a LAN when their RPF neighbor changes. When the
RPF neighbor changes, this timer is set to a random value
between 0 and [Random-Delay-Join-Timeout] seconds. When the
timer expires, a triggered Join/Prune message is sent for
the entry unless its Join/Prune-Suppression-Timer is
running.
Query 30 Started : When booting 3.8.2 Timers relating to neighbor discovery
Restarted by: Nothing
Action : Send Query on all ifaces, restart timer
Neighbor 90 Started : When receive first Query from neighbor * [Hello-Timer] This timer is used to periodically send Hello
per neighbor Restarted by: When receive subsequent Queries messages. To avoid synchronization among routers booting
Action : Delete neighbor entry simultaneously, it is initially set to a random value
between 1 and [Hello-Period]. When it expires, the timer is
immediately restarted to [Hello-Period]. A Hello message is
then sent out each interface. This timer should not be
restarted by other events.
* [Neighbor-Timer (kept per neighbor)] A Neighbor-Timer for
each neighbor is used to time out the neighbor state. When
a Hello message is received from a new neighbor, the timer
is initially set to the Holdtime included in the Hello
message (which is equal to the neighbor's value of [Hello-
Holdtime]). Every time a subsequent Hello is received from
that neighbor, the timer is restarted to the Holdtime in
the Hello. When the timer expires, the neighbor state is
removed.
3.8.3 Timers relating to RP information 3.8.3 Timers relating to RP information
[Page 42] * [C-RP-Adv-Timer (C-RP's only)] Routers configured as
Timer DefVal Notes candidate RP's use this timer to periodically send C-RP-Adv
messages. To avoid synchronization among routers booting
simultaneously, the timer is initially set to a random
C-RP-Adv 60 Started : When booting if you're a Cand-RP Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 41]
Restarted by: Nothing value between 1 and [C-RP-Adv-Period]. When it expires, the
Action : Send C-RP-Adv, restart C-RP-Adv timer timer is immediately restarted to [C-RP-Adv-Period]. A C-
RP-Adv message is then sent to the elected BSR. This timer
should not be restarted by other events.
RP 180 Started : When adding an RP to the RP-Set if * [RP-Timer (BSR only, kept per RP in RP-Set)] The BSR uses a
per RP you are BSR timer per RP in the RP-Set to monitor liveness. When a C-RP
Restarted by: Receiving C-RP-Adv is added to the RP-Set, its timer is set to the Holdtime
Action : Remove RP from RP-Set included in the C-RP-Adv message from that C-RP (which is
equal to the C-RP's value of [RP-Holdtime]). Every time a
subsequent C-RP-Adv is received from that RP, its timer is
restarted to the Holdtime in the C-RP-Adv. When the timer
expires, the RP is removed from the RP-Set included in
Bootstrap messages.
RP-Set 180/60 Started : Set to 180 when booting if * [Bootstrap-Timer] This timer is used by the BSR to
you're a C-BSR periodically originate Bootstrap messages, and by other
Restarted by: Restarted to 180 when receive routers to time out the BSR (see
RP-Set from preferred router if you're a C-BSR 3.6.3). This timer is initially set to [Bootstrap-
Action : Send RP-Set and restart timer to 60 secs Timeout]. A C-BSR restarts this timer to [Bootstrap-
Timeout] upon receiving a Bootstrap message from a
preferred router, and originates an Bootstrap message and
restarts the timer to [Bootstrap-Period] when it expires.
Routers not configured as C-BSR's restart this timer to
[Bootstrap-Timeout] upon receiving a Bootstrap message from
the elected or a more preferred BSR, and ignore Bootstrap
messages from non-preferred C-BSRs while it is running.
3.8.4 Default timer values
Most of the default timeout values for state information are 3.5
times the refresh period. For example, Hellos refresh Neighbor
state and the default Hello-timer period is 30 seconds, so a
default Neighbor-timer duration of 105 seconds is included in
the Holdtime field of the Hellos. In order to improve
convergence, however, the default timeout value for information
related to RP liveness and Bootstrap messages is 2.5 times the
refresh period.
In this version of the spec, we suggest particular numerical
timer settings. A future version of the specification will
specify a mechanism for timer values to be scaled based upon
observed network parameters.
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 42]
* [Join/Prune-Period] This is the interval between
sending Join/Prune messages. {Default: 60 seconds.} This
value may be set to take into account such things as the
configured bandwidth and expected average number of
multicast route entries for the attached network or link
(e.g., the period would be longer for lower-speed links, or
for routers in the center of the network that expect to
have a larger number of entries ). In addition, a router
could modify this value (and corresponding Join/Prune-
Holdtime value) if the number of route entries changes
significantly (e.g., by an order of magnitude). For
example, given a default minimum Join/Prune-Period value,
if the number of route entries with a particular iif
increases from N to N*100, the router could increase its
Join/Prune-Period (and Join/Prune-Holdtime), for that
interface, by a factor of 10; and if/when the number of
entries decreases back to N, the Join/Prune-Period (and
Join/Prune-Holdtime) could be decreased to its previous
value. If the Join/Prune-Period is modified, these changes
should be made relatively infrequently and the router
should continue to refresh at its previous Join/Prune-
Period for at least Join/Prune-Holdtime, in order to allow
the upstream router to adapt.
* [Join-Prune Holdtime] This is the Holdtime specified in
Join/Prune messages, and is used to time out oifs. This
should be set to 3.5 * [Join/Prune-Period]. {Default: 210
seconds.}
* [Join/Prune-Suppression-Timeout] This is the mean
interval between receiving a Join/Prune with a higher
Holdtime (with ties broken by higher IP addres) and
allowing duplicate Join/Prunes to be sent again. This
should be set to approximately 1.25 * [Join/Prune-Period].
{Default: 75 seconds. }
* [Data-Timeout] This is the time after which (S,G) state
for a silent source will be deleted. {Default: 210
seconds.}
* [Register-Suppression-Timeout] This is the mean
interval between receiving a Register-Stop and allowing
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 43]
Registers to be sent again. A lower value means more
frequent register bursts at RP, while a higher value means
longer join latency for new receivers. {Default: 60
seconds.} (Note that if null Registers are sent [Probe-
Time] seconds before the timeout, register bursts are
prevents, and [Register-Suppression-Timeout] may be lowered
to decrease join latency.)
* [Probe-Time] When null Registers are used, this is the
time between sending a null Register and the Register-
Suppression-Timer expiring unless it is restarted by
receiving a Register-Stop. Thus, a null Register would be
sent when the Register-Suppression-Timer reaches this
value. {Default: 5 seconds.}
* [Assert-Timeout] This is the interval between the last
time an Assert is received, and the time at which the
assert is timed out. {Default: 180 seconds.}
* [Random-Delay-Join-Timeout] This is the maximum
interval between the time when the RPF neighbor changes,
and the time at which a triggered Join/Prune message is
sent. {Default: 4.5 seconds.}
* [Hello-Period] This is the interval between sending
Hello messages. {Default: 30 seconds.}
* [Hello-Holdtime] This is the Holdtime specified in
Hello messages, after which neighbors will time out their
neighbor entries for the router. This should be set to 3.5
* [Hello-Period]. {Default: 105 seconds.}
* [C-RP-Adv-Period] For C-RPs, this is the interval
between sending C-RP-Adv messages. {Default: 60 seconds.}
* [RP-Holdtime] For C-RPs, this is the Holdtime specified
in C-RP-Adv messages, and is used by the BSR to time out
RPs. This should be set to 2.5 * [C-RP-Adv-Period].
{Default: 150 seconds.}
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 44]
* [Bootstrap-Period] At the elected BSR, this is the
interval between originating Bootstrap messages, and should
be equal to 60 seconds.
* [Bootstrap-Timeout] This is the time after which the
elected BSR will be assumed unreachable when Bootstrap
messages are not received from it. This should be set to
2.5 * [Bootstrap-Period]. {Default: 150 seconds.}
3.9 Summary of flags used 3.9 Summary of flags used
Following is a summary of all the flags used in our scheme. Following is a summary of all the flags used in our scheme.
Bit Used in Definition Bit | Used in | Definition
Border Register Register is coming from a PIM multicast border router. Authoritative | C-RP-Adv | Group-prefix information should not be over-
Joiner Route entry Periodic Join/Prunes should be sent for this entry. ridden by BSR
Register (S,G) entry Encapsulate packets from directly connected Border | Register | Register for external sources is coming from
sources in Register messages unicast to the RP PIM multicast border router
for that group. Null | Register | Register sent as Probe of RP, the encapsulated
RP Route entry Entry represents state on the RP-tree. IP data packet should not be forwarded
RP Join/Prune Join is associated with the shared tree and therefore RPT | Route entry | Entry represents state on the RP-tree
the Join/Prune message is propagated along the RP-tree. RPT | Join/Prune | Join is associated with the shared tree and
RP Assert The data packet was routed down the shared tree; thus, therefore the Join/Prune message is propagated
the path indicated corresponds to the RP tree. along the RP-tree (source encoded is an RP
SPT (S,G) entry Packets have arrived on the iif towards S, address)
and the iif is different from the (*,G) iif. RPT | Assert | The data packet was routed down the shared
WC Join Included address is an RP and the receiver expects to tree; thus, the path indicated corresponds
receive packets from all sources via this (shared tree) to the RP tree
path. Thus, the Join/Prune applies to a (*,G) entry. SPT | (S,G) entry | Packets have arrived on the iif towards S, and
WC Route entry Wildcard entry; if there is no more specific match for the iif is different from the (*,G) iif
a particular source, packets will be forwarded according WC |Join | The receiver expects to receive packets from all sources via this (shared tree) path. Thus, the
to this entry. Join/Prune applies to a (*,G) entry
WC | Route entry | Wildcard entry; if there is no more specific
match for a particular source, packets will
be forwarded according to this entry
[Page 43] Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 45]
3.10 Security 3.10 Security
Editors Note: this section is to be completed. All PIM control messages may use [6] to address security
All PIM control messages may use [5] to address security
concerns. concerns.
[Page 44] Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 46]
4 Packet Formats 4 Packet Formats
This section describes the details of the packet formats for PIM This section describes the details of the packet formats for PIM
control messages. control messages.
All PIM control messages have protocol number 103. All PIM control messages have protocol number 103.
Basically, PIM messages are either unicast (e.g. Registers and Basically, PIM messages are either unicast (e.g. Registers and
Register-Stop), or multicast hop-by-hop to `ALL-PIM-ROUTERS' Register-Stop), or multicast hop-by-hop to `ALL-PIM-ROUTERS'
group `224.0.0.13' (e.g. Join/Prune, Asserts, etc.). group `224.0.0.13' (e.g. Join/Prune, Asserts, etc.).
skipping to change at line 1829 skipping to change at line 2016
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|PIM Ver| Type | Addr length | Checksum | |PIM Ver| Type | Addr length | Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
PIM Ver PIM Ver
PIM Version number is 2. PIM Version number is 2.
Type Types for specific PIM messages. PIM Types are: Type Types for specific PIM messages. PIM Types are:
0 = Query 0 = Hello
1 = Register 1 = Register
2 = Register-Stop 2 = Register-Stop
3 = Join/Prune 3 = Join/Prune
4 = RP-Set 4 = Bootstrap
5 = Assert 5 = Assert
6 = Graft (used in PIM-DM only) 6 = Graft (used in PIM-DM only)
7 = Graft-Ack (used in PIM-DM only) 7 = Graft-Ack (used in PIM-DM only)
8 = Candidate-RP-Advertisement 8 = Candidate-RP-Advertisement
Addr length Addr length
Address length in bytes. Throughout this section this Address length in bytes. Throughout this section this
would indicate the number of bytes in the Address field of would indicate the number of bytes in the Address field of
an address, including unicast and group addresses. an address, including unicast and group addresses.
[Page 45] Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 47]
Checksum Checksum
The checksum is the 16-bit one's complement of the one's The checksum is the 16-bit one's complement of the one's
complement sum of the entire PIM message, (excluding the complement sum of the entire PIM message, (excluding the
data portion in the Register message). For computing the data portion in the Register message). For computing the
checksum, the checksum field is zeroed. checksum, the checksum field is zeroed.
[Page 46] Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 48]
4.1 Encoded Source and Group Address formats 4.1 Encoded Source and Group Address formats
1 Unicast address: Only the address is included. The length 1 Unicast address: Only the address is included. The length
of the unicast address in bytes is specified in the `Addr of the unicast address in bytes is specified in the `Addr
length' field in the header. length' field in the header.
2 Encoded-Group-Address: Takes the following format: 2 Encoded-Group-Address: Takes the following format:
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reserved | Mask Len | Group multicast Address ... | | Reserved | Mask Len | Group multicast Address ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ...Group multicast Address ...| | ...Group multicast Address ...|
+-+-+-+-+-+-+-+-+-+-+~+~+~+~+~+~+ +-+-+-+-+-+-+-+-+-+-+++++++
Reserved Reserved
Transmitted as zero. Ignored upon receipt. Transmitted as zero. Ignored upon receipt.
Mask Len Mask Len
The Mask length is 8 bits. The value is the number of The Mask length is 8 bits. The value is the number of
contiguous bits left justified used as a mask which contiguous bits left justified used as a mask which
describes the address. It is less than or equal to describes the address. It is less than or equal to
Addr length * 8. If the message is sent for a single Addr length * 8. If the message is sent for a single
group then the Mask length should equal Addr length * group then the Mask length must equal Addr length * 8
8 (i.e. 32 for IPv4 and 128 for IPv6). (i.e. 32 for IPv4 and 128 for IPv6).
Group multicast Address Group multicast Address
contains the group address, and has number of bytes contains the group address, and has number of bytes
equal to that specified in the Addr length field. equal to that specified in the Addr length field.
3 Encoded-Source-Address: Takes the following format: 3 Encoded-Source-Address: Takes the following format:
[Page 47] Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 49]
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Rsrvd |S|W|R| Mask Len | Source Address ... | | Rsrvd |S|W|R| Mask Len | Source Address ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... Source Address | | ... Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+~+~+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+++-+
Reserved Reserved
Transmitted as zero, ignored on receipt. Transmitted as zero, ignored on receipt.
S,W,R See Section 4.5 for details. S,W,R See Section 4.5 for details.
Mask Length Mask Length
Mask length is 8 bits. The value is the number of Mask length is 8 bits. The value is the number of
contiguous bits left justified used as a mask which contiguous bits left justified used as a mask which
describes the address. The mask length must be less describes the address. The mask length must be less
than or equal to Addr Length * 8. If the message is than or equal to Addr Length * 8. If the message is
sent for a single source then the Mask length should sent for a single source then the Mask length must
equal Addr length * 8. In version 2 of PIM, it is equal Addr length * 8. In version 2 of PIM, it is
strongly recommended that this field be set to 32 for strongly recommended that this field be set to 32 for
IPv4. IPv4.
Source Address Source Address
The address length is indicated from the Addr length The address length is indicated from the Addr length
field at the beginning of the header. For IPv4, the field at the beginning of the header. For IPv4, the
address length is 4 octets. address length is 4 octets.
[Page 48] Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 50]
4.2 Query Message 4.2 Hello Message
It is sent periodically by routers on all interfaces. It is sent periodically by routers on all interfaces.
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|PIM Ver| Type | Addr length | Checksum | |PIM Ver| Type | Addr length | Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reserved | Holdtime | | OptionType | OptionLength |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| OptionValue |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+++
| . |
| . |
| . |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| OptionType | OptionLength |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| OptionValue |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+++
PIM Version, Type, Addr length, Checksum PIM Version, Type, Addr length, Checksum
Described above. Described above.
Reserved OptionType
Transmitted as zero, ignored on receipt. The type of the option given in the following OptionValue
field.
Holdtime OptionLength
The amount of time a receiver should keep the neighbor The length of the OptionValue field in bytes.
reachable, in seconds.
[Page 49] OptionValue
A variable length field, carrying the value of the option.
The Option fields may contain the following values:
* OptionType = 1; OptionLength = 2; OptionValue = Holdtime;
where Holdtime is the amount of time a receiver must keep
the neighbor reachable, in seconds. If the Holdtime is set
to `0xffff', the receiver of this message never times out
the neighbor. This may be used with ISDN lines, to avoid
keeping the link up with periodic Hello messages.
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 51]
Furthermore, if the Holdtime is set to `0', the information
is timed out immediately.
* OptionType 2 to 16: reserved
* The rest of the OptionTypes are defined in another
document.
In general, options may be ignored; but a router must not ignore
the
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 52]
4.3 Register Message 4.3 Register Message
It is sent by the Designated Router (DR) to the RP when a A Register message is sent by the DR or a PMBR to the RP when a
multicast packet needs to be transmitted on the RP-tree. Source multicast packet needs to be transmitted on the RP-tree. Source
IP address is set to the address of the DR, destination IP IP address is set to the address of the DR, destination IP
address is to the RP's address. address is to the RP's address.
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|PIM Ver| Type | Addr length | Checksum | |PIM Ver| Type | Addr length | Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|B| Reserved | |B|N| Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
Multicast data packet Multicast data packet
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
PIM Version, Type, Addr length, Checksum PIM Version, Type, Addr length, Checksum
Described above. Note that the checksum for Registers Described above. {Note that the checksum for Registers
is done only on the PIM header, excluding the data packet is done only on the PIM header, excluding the data packet
portion. portion.}
B The Border bit. Set to zero by all DRs. Set to `1' by the B The Border bit. If the router is a DR for a source that it
PIM Multicast Border Routers, when registering for external is directly connected to, it sets the B bit to 0. If the
sources. router is a PMBR for a source in a directly connected
cloud, it sets the B bit to 1.
N The Null-Register bit. Set to 1 by a DR that is probing
the RP before expiring its local Register-Suppression
timer. Set to 0 otherwise.
Multicast data packet Multicast data packet
The original packet sent by the source. The original packet sent by the source.
[Page 50] For (S,G) null Registers, the Multicast data packet portion
contains only a dummy IP header with S as the source address, G
as the destination address, and a data length of zero.
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 53]
4.4 Register-Stop Message 4.4 Register-Stop Message
A Register-Stop is unicast from the RP to the sender of the A Register-Stop is unicast from the RP to the sender of the
Register message. Source IP address is the address to which the Register message. Source IP address is the address to which the
register was addressed. Destination IP address is the source register was addressed. Destination IP address is the source
address of the register message. address of the register message.
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
skipping to change at line 1992 skipping to change at line 2222
| Encoded-Group Address | | Encoded-Group Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Unicast-Source Address | | Unicast-Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
PIM Version, Type, Addr length, Checksum PIM Version, Type, Addr length, Checksum
Described above. Described above.
Encoded-Group Address Encoded-Group Address
Format described above. Note that for Register-Stops the Format described above. Note that for Register-Stops the
Mask Len field should contain Addr length * 8 (32 for Mask Len field contains Addr length * 8 (32 for IPv4), if
IPv4), if the message is sent for a single group. the message is sent for a single group.
Unicast-Source Address Unicast-Source Address
IP host address of source from multicast data packet in IP host address of source from multicast data packet in
register. The length of this field in bytes is specified in register. The length of this field in bytes is specified in
the Addr length field. A special wild card value (0.0.0.0), the Addr length field. A special wild card value (0.0.0.0),
can be used to indicate any source. can be used to indicate any source.
[Page 51] Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 54]
4.5 Join/Prune Message 4.5 Join/Prune Message
It is sent by routers towards upstream sources and RPs. A join A Join/Prune message is sent by routers towards upstream sources
creates forwarding state and a prune destroys forwarding state. and RPs. Joins are sent to build shared trees (RP trees) or
Joins are sent to build shared trees (RP trees) or source trees source trees (SPT). Prunes are sent to prune source trees when
(SPT). Prunes are sent to prune source trees when members leave members leave groups as well as sources that do not use the
groups as well as sources that do not use the shared tree. shared tree.
[Page 52] Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 55]
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|PIM Ver| Type | Addr length | Checksum | |PIM Ver| Type | Addr length | Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Unicast-Upstream Neighbor Address | | Unicast-Upstream Neighbor Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reserved | Num groups | Holdtime | | Reserved | Num groups | Holdtime |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Multicast Group Address-1 | | Encoded-Multicast Group Address-1 |
skipping to change at line 2059 skipping to change at line 2289
| . | | . |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Joined Source Address-n | | Encoded-Joined Source Address-n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Pruned Source Address-1 | | Encoded-Pruned Source Address-1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| . | | . |
| . | | . |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
[Page 53] Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 56]
| Encoded-Pruned Source Address-n | | Encoded-Pruned Source Address-n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
PIM Version, Type, Addr length, Checksum PIM Version, Type, Addr length, Checksum
Described above. Described above.
Upstream Neighbor Address Upstream Neighbor Address
The IP address of the RPF or upstream neighbor. The IP address of the RPF or upstream neighbor.
Reserved Reserved
Transmitted as zero, ignored on receipt. Transmitted as zero, ignored on receipt.
Holdtime Holdtime
The amount of time a receiver should keep the Join/Prune The amount of time a receiver must keep the Join/Prune
state alive, in seconds. state alive, in seconds. If the Holdtime is set to
`0xffff', the receiver of this message never times out the
oif. This may be used with ISDN lines, to avoid keeping the
link up with periodical Join/Prune messages. Furthermore,
if the Holdtime is set to `0', the information is timed out
immediately.
Number of Groups Number of Groups
The number of multicast group sets contained in the The number of multicast group sets contained in the
message. message.
Encoded-Multicast group address Encoded-Multicast group address
For format description see Section For format description see Section
4.1. A wild card group in the (*,*,RP) join is represented 4.1. A wild card group in the (*,*,RP) join is represented
by a 224.0.0.0 in the group address field and `4' in the by a 224.0.0.0 in the group address field and `4' in the
mask length field. A (*,*,RP) join also has the WC-bit and mask length field. A (*,*,RP) join also has the WC-bit and
skipping to change at line 2098 skipping to change at line 2333
Number of join source addresses listed for a given group. Number of join source addresses listed for a given group.
Join Source Address-1 .. n Join Source Address-1 .. n
This list contains the sources that the sending router This list contains the sources that the sending router
will forward multicast datagrams for if received on the will forward multicast datagrams for if received on the
interface this message is sent on. interface this message is sent on.
See format section 4.1. The fields explanation for the See format section 4.1. The fields explanation for the
Encoded-Source-Address format follows: Encoded-Source-Address format follows:
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 57]
Reserved Reserved
Described above. Described above.
[Page 54]
S The Sparse bit is a 1 bit value, set to 1 for PIM-SM. S The Sparse bit is a 1 bit value, set to 1 for PIM-SM.
It is used for PIM v.1 compatability. It is used for PIM v.1 compatibility.
W The WC bit is a 1 bit value. If 1, the join or prune W The WC bit is a 1 bit value. If 1, the join or prune
applies to the (*,G) or (*,*,RP) entry. If 0, the join applies to the (*,G) or (*,*,RP) entry. If 0, the join
or prune applies to the (S,G) entry where S is Source or prune applies to the (S,G) entry where S is Source
Address. Joins and prunes sent towards the RP should Address. Joins and prunes sent towards the RP must
have this bit set. have this bit set.
R The RPT-bit is a 1 bit value. If 1, the information R The RPT-bit is a 1 bit value. If 1, the information
about (S,G) is sent towards the RP. If 0, the about (S,G) is sent towards the RP. If 0, the
information should be sent about (S,G) toward S, where information must be sent toward S, where S is the
S is Source Address. Source Address.
Mask Length, Source Address Mask Length, Source Address
Described above. Described above.
Represented in the form of < WC-bit >< RPT-bit >< Represented in the form of < WC-bit >< RPT-bit ><
Mask length >< Source address>: Mask length >< Source address>:
A source address could be a host IP address : A source address could be a host IP address :
< 0 >< 0 >< 32 >< 192.1.1.17 > < 0 >< 0 >< 32 >< 192.1.1.17 >
skipping to change at line 2145 skipping to change at line 2380
A source address could be a general aggregate : A source address could be a general aggregate :
< 0 >< 0 >< 16 >< 192.1.0.0 > < 0 >< 0 >< 16 >< 192.1.0.0 >
Number of Pruned Sources Number of Pruned Sources
Number of prune source addresses listed for a group. Number of prune source addresses listed for a group.
Prune Source Address-1 .. n Prune Source Address-1 .. n
This list contains the sources that the sending router This list contains the sources that the sending router
does not want to forward multicast datagrams for when does not want to forward multicast datagrams for when
received on the interface this message is sent on [*]
_________________________
[*] If the Join/Prune message boundary exceeds the max-
[Page 55] Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 58]
4.6 RP-Set received on the interface this message is sent on. If the
Join/Prune message boundary exceeds the maximum packet
size, then the join and prune lists for the same group must
be included in the same packet.
The RP-Set messages are multicast to `ALL-PIM-ROUTERS' group, Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 59]
4.6 Bootstrap Message
The Bootstrap messages are multicast to `ALL-PIM-ROUTERS' group,
out all interfaces having PIM neighbors (excluding the one over out all interfaces having PIM neighbors (excluding the one over
which the message was received). RP-Set messages are sent with which the message was received). Bootstrap messages are sent
TTL value of 1. RP-Set messages originate at the BSR, and are with TTL value of 1. Bootstrap messages originate at the BSR,
forwarded by intermediate routers. and are forwarded by intermediate routers.
RP-Set message is divided up into `semantic fragments', if the Bootstrap message is divided up into `semantic fragments', if
original message exceeds the maximum packet size boundaries. the original message exceeds the maximum packet size boundaries.
The semantics of a single `fragment' is given below: The semantics of a single `fragment' is given below:
_________________________ Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 60]
imum packet size, then the join and prune lists for the
same group must be included in the same packet.
[Page 56]
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|PIM Ver| Type | Addr length | Checksum | |PIM Ver| Type | Addr length | Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Fragment Tag | Hash Mask len | BSR-priority | | Fragment Tag | Hash Mask len | BSR-priority |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Unicast-BSR-Address | | Unicast-BSR-Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Group Address-1 | | Encoded-Group Address-1 |
skipping to change at line 2211 skipping to change at line 2445
| . | | . |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Unicast-RP-Address-m | | Unicast-RP-Address-m |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
PIM Version, Type, Addr length, Checksum PIM Version, Type, Addr length, Checksum
Described above. Described above.
Fragment Tag Fragment Tag
[Page 57] Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 61]
A randomly generated number, acts to distinguish the A randomly generated number, acts to distinguish the
fragments belonging to different RP-Set messages; fragments fragments belonging to different Bootstrap messages;
belonging to same RP-Set message carry the same `Fragment fragments belonging to same Bootstrap message carry the
Tag'. same `Fragment Tag'.
Hash Mask len Hash Mask len
The length (in bits) of the mask to use in the hash The length (in bits) of the mask to use in the hash
function. For IPv4 we recommend a value of 30. For IPv6 we function. For IPv4 we recommend a value of 30. For IPv6 we
recommend a value of 126. recommend a value of 126.
BSR-priority BSR-priority
Contains the BSR priority value of the included BSR. This Contains the BSR priority value of the included BSR. This
field is considered as a high order byte when comparing BSR field is considered as a high order byte when comparing BSR
addresses. addresses.
skipping to change at line 2237 skipping to change at line 2471
Unicast-BSR-Address Unicast-BSR-Address
The IP address of the bootstrap router for the domain. The The IP address of the bootstrap router for the domain. The
length of this field in bytes is specified in Addr length. length of this field in bytes is specified in Addr length.
Encoded-Group Address-1..n Encoded-Group Address-1..n
The group prefix (address and mask) with which the The group prefix (address and mask) with which the
Candidate RPs are associated. Format previously described. Candidate RPs are associated. Format previously described.
RP-Count-1..n RP-Count-1..n
The number of Candidate RP addresses included in the whole The number of Candidate RP addresses included in the whole
RP-Set message for the corresponding group prefix [*] Bootstrap message for the corresponding group prefix. A
router does not replace its old RP-Set for a given group
prefix until/unless it receives `RP-Count' addresses for
that prefix; the addresses could be carried over several
fragments. If only part of the RP-Set for a given group
prefix was received, the router discards it, without
updating that specific group prefix's RP-Set.
Frag RP-Cnt-1..m Frag RP-Cnt-1..m
The number of Candidate RP addresses included in this The number of Candidate RP addresses included in this
fragment of the RP-Set message, for the corresponding group fragment of the Bootstrap message, for the corresponding
prefix. The `Frag RP-Cnt' field facilitates parsing of the group prefix. The `Frag RP-Cnt' field facilitates parsing
RP-Set for a given group prefix, when carried over more of the RP-Set for a given group prefix, when carried over
than one fragment. more than one fragment.
Unicast-RP-address-1..m Unicast-RP-address-1..m
The address of the Candidate RPs, for the corresponding The address of the Candidate RPs, for the corresponding
_________________________
[*] A router does not replace its old RP-Set for a
given group prefix until/unless it receives `RP-Count'
addresses for that prefix; the addresses could be car-
ried over several fragments. If only part of the RP-Set
for a given group prefix was received, the router dis-
cards it, without updating that specific group prefix's
RP-Set.
[Page 58]
group prefix. The length of this field in bytes is group prefix. The length of this field in bytes is
specified in Addr length. specified in Addr length.
[Page 59] Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 62]
4.7 Assert Message 4.7 Assert Message
The Assert message is sent when a multicast data packet is The Assert message is sent when a multicast data packet is
received on an outgoing interface corresponding to the (S,G) or received on an outgoing interface corresponding to the (S,G) or
(*,G) associated with the source. (*,G) associated with the source.
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|PIM Ver| Type | Addr length | Checksum | |PIM Ver| Type | Addr length | Checksum |
skipping to change at line 2307 skipping to change at line 2537
tree, then the RPT-bit is 1; if the IP multicast datagram tree, then the RPT-bit is 1; if the IP multicast datagram
is routed down the SPT, it is 0. is routed down the SPT, it is 0.
Metric Preference Metric Preference
Preference value assigned to the unicast routing protocol Preference value assigned to the unicast routing protocol
that provided the route to Host address. that provided the route to Host address.
Metric The unicast routing table metric. The metric is in units Metric The unicast routing table metric. The metric is in units
applicable to the unicast routing protocol used. applicable to the unicast routing protocol used.
[Page 60] Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 63]
4.8 Graft Message 4.8 Graft Message
Used in dense-mode. Refer to PIM dense mode specification. Used in dense-mode. Refer to PIM dense mode specification.
4.9 Graft-Ack Message 4.9 Graft-Ack Message
Used in dense-mode. Refer to PIM dense mode specification. Used in dense-mode. Refer to PIM dense mode specification.
[Page 61] Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 64]
4.10 Candidate-RP-Advertisement 4.10 Candidate-RP-Advertisement
Candidate-RP-Advertisements are periodically unicast from the Candidate-RP-Advertisements are periodically unicast from the
C-RPs to the BSR. C-RPs to the BSR.
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|PIM Ver| Type | Addr length | Checksum | |PIM Ver| Type | Addr length | Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Prefix-Cnt | Reserved | Holdtime | | Prefix-Cnt |A| Reserved | Holdtime |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Unicast-RP-Address | | Unicast-RP-Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Group Address-1 | | Encoded-Group Address-1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| . | | . |
| . | | . |
| . | | . |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Group Address-n | | Encoded-Group Address-n |
skipping to change at line 2352 skipping to change at line 2582
Prefix-Cnt Prefix-Cnt
The number of encoded group addresses included in the The number of encoded group addresses included in the
message; indicating the group prefixes for which the C-RP message; indicating the group prefixes for which the C-RP
is advertising. A Prefix-Cnt of `0' implies a prefix of is advertising. A Prefix-Cnt of `0' implies a prefix of
224.0.0.0 with mask length of 4; i.e. all multicast groups. 224.0.0.0 with mask length of 4; i.e. all multicast groups.
If the C-RP is not configured with Group-prefix If the C-RP is not configured with Group-prefix
information, the C-RP puts a default value of `0' in this information, the C-RP puts a default value of `0' in this
field. field.
A The Authoritative bit. This bit indicates that the BSR
should not override the group-prefix information indicated
inthe C-RP Advertisement. In most cases C-RPs set this bit
to 0.
Holdtime Holdtime
The amount of time the advertisement is valid. This field The amount of time the advertisement is valid. This field
allows advertisements to be aged out. allows advertisements to be aged out.
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 65]
Unicast-RP-Address Unicast-RP-Address
The address of the interface to advertise as a Candidate The address of the interface to advertise as a Candidate
RP. The length of this field in bytes is specified in Addr RP. The length of this field in bytes is specified in Addr
[Page 62]
length. length.
Encoded-Group Address-1..n Encoded-Group Address-1..n
The group prefixes for which the C-RP is advertising. The group prefixes for which the C-RP is advertising.
Format previously described. Format previously described.
[Page 63] Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 66]
5 Appendix I: Major Changes and Updates to the Spec 5 Acknowledgments
Tony Ballardie, Scott Brim, Jon Crowcroft, Bill Fenner, Paul
Francis, Joel Halpern, Horst Hodel, Polly Huang, Stephen
Ostrowski, Lixia Zhang and Girish Chandranmenon provided
detailed comments on previous drafts. The authors of [7] and
membership of the IDMR WG provided many of the motivating ideas
for this work and useful feedback on design details.
This work was supported by the National Science Foundation,
ARPA, cisco Systems and Sun Microsystems.
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 67]
6 Appendices
6.1 Appendix I: Major Changes and Updates to the Spec
This appendix populates the major changes in the specification This appendix populates the major changes in the specification
document as compared to `draft-ietf-idmr-pim-spec-01.ps,txt'. document as compared to `draft-ietf-idmr-pim-spec-01.ps,txt'.
5.1 Major Changes * Major Changes
List of changes since March '96 IETF: List of changes since March '96 IETF:
1. (*,*,RP) Joins state and data forwarding check; replaces (*,G- (*,*,RP) Joins state and data forwarding check; replaces (*,G-
Prefix) Joins state for interoperability. (*,G) negative cache Prefix) Joins state for interoperability. (*,G) negative cache
introduced for the (*,*,RP) state supporting mechanisms. introduced for the (*,*,RP) state supporting mechanisms.
2. Semantic fragmentation for the RP-Set message. Semantic fragmentation for the Bootstrap message.
Refinement of Assert details.
Addition and refinement of Join/Prune suppression and Register
suppression (introduction of null Registers).
Editorial changes and clarifications to the timers section.
Addition of Appendix II (BSR Election and RP-Set Distribution),
and Appendix III (Glossary of Terms).
Addition of table of contents.
List of changes incurred since version 1 of the spec.: List of changes incurred since version 1 of the spec.:
1. Proposal and refinement of bootstrap router (BSR) election Proposal and refinement of bootstrap router (BSR) election
mechanisms mechanisms
2. Introduction of hash functions for Group to RP mapping Introduction of hash functions for Group to RP mapping
3. New RP-liveness indication mechanisms based upon the the New RP-liveness indication mechanisms based upon the the
Bootstrap Router (BSR) and the RP-Set messages. Bootstrap Router (BSR) and the Bootstrap messages.
4. Removal of reachability messages, RP reports and multiple RPs Removal of reachability messages, RP reports and multiple RPs
per group. per group.
5.2 Packet Format Changes Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 68]^L
* Packet Format Changes
Packet Format incurred updates to accommodate different address Packet Format incurred updates to accommodate different address
lengths, and address aggregation. lengths, and address aggregation.
1 The `Addr length' field was added to the PIM fixed header 1 The `Addr length' field was added to the PIM fixed header
to specify the address length in bytes of the underlying to specify the address length in bytes of the underlying
protocol, see section 4. protocol, see section 4.
[Page 64]
2 The Encoded source and group address formats were 2 The Encoded source and group address formats were
introduced, with the use of a `Mask length' field to allow introduced, with the use of a `Mask length' field to allow
aggregation, section 4.1. aggregation, section 4.1.
3 Packet formats are no longer IGMP messages; rather PIM 3 Packet formats are no longer IGMP messages; rather PIM
messages. messages.
PIM message types and formats were also modified: PIM message types and formats were also modified:
[ Note: most changes were made to the May 95 version, unless [ Note: most changes were made to the May 95 version, unless
otherwise specified]. otherwise specified].
1 Obsolete messages: 1 Obsolete messages:
(a) Register-Ack [Feb. 96] Register-Ack [Feb. 96]
(b) Poll and Poll Response [Feb. 96] Poll and Poll Response [Feb. 96]
(c) RP-Reachability [Feb. 96] RP-Reachability [Feb. 96]
(d) RPlist-Mapping [Feb. 96] RPlist-Mapping [Feb. 96]
2 New messages: 2 New messages:
(a) Candidate-RP-Advertisement [change made in October 95] Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 69]
Candidate-RP-Advertisement [change made in October 95]
RP-Set [Feb. 96] RP-Set [Feb. 96]
3 Modified messages: 3 Modified messages:
(a) Join/Prune [Feb. 96] Join/Prune [Feb. 96]
Register [Feb. 96]
Register-Stop [Feb. 96]
Hello (addition of OptionTypes) [Aug 96]
(b) Register [Feb. 96] 4 Renamed messages:
(c) Register-Stop [Feb. 96] Query messages are renamed as Hello messages [Aug. 96]
RP-Set messages are renamed as Bootstrap messages [Aug. 96]
[Page 65] Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 70]
[Page 66] 6.2 Appendix II: BSR Election and RP-Set Distribution
6 Acknowledgments
Tony Ballardie, Scott Brim, Jon Crowcroft, Bill Fenner, Paul For simplicity, the Bootstrap message is used in both the BSR
Francis, Joel Halpern, Horst Hodel, Polly Huang, Stephen election and the RP-Set distribution.
Ostrowski, and Lixia Zhang provided detailed comments on
previous drafts. The authors of [6] and membership of the IDMR
WG provided many of the motivating ideas for this work and
useful feedback on design details.
This work was supported by the National Science Foundation, The above two mechanisms; the BSR election, and the RP-Set
ARPA, cisco Systems and Sun Microsystems. distribution; are realized through the following state machine,
illustrated in figure 4:
[Figures are present only in the postscript version]
Fig. 4 State Diagram for the BSR election and RP-Set
distribution mechanisms
The protocol transitions for a C-BSR are given in state diagram (a).
For routers not configured as C-BSRs, the protocol transitions are
given in state diagram (b).
Each PIM router keeps a Bootstrap-timer, initialized to [Bootstrap-
Timeout], in addition to a local BSR field `LclBSR' (initialized
to a local address if C-BSR, or to 0 otherwise), and a local RP-Set
`LclRP-Set' (initially empty). The two main stimuli to the state
machine are the timer events, and receiving an Bootstrap message:
* Initial States and Timer Events
1 If the router is a C-BSR:
1 The router operates initially in the `CandBSR' state, where
it does not originate any Bootstrap messages.
2 If the Bootstrap-timer expires, and the current state is
`CandBSR', the router originates an Bootstrap message -
carrying the local RP-Set, and its own BSR priority and
address-, restarts the Bootstrap-timer at [Bootstrap-
Period] seconds and transits into the `ElectedBSR' state.
3 If the Bootstrap-timer expires, and the current state is
`ElectedBSR', the router originates an Bootstrap message,
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 71]
and restarts the RP-Set timer at [Bootstrap-Period]. No
state transition is incurred.
This way, the elected BSR originates periodic Bootstrap
messages every [Bootstrap-Period].
2 If a router is not a C-BSR:
1 The router operates initially in the 'AxptAny' state. In
such state, a router accepts the first Bootstrap message
from the RPF neighbor toward the included BSR The Reverse
Path Forwarding (RPF) neighbor in this case is the next hop
router en route to the included BSR.
2 If the Bootstrap-timer expires, and the current state is
`AxptPref', -where the router accepts only preferred.
Preferred Bootstrap messages are those that carry BSR-
priority and address higher than, or equal to, `LclBSR'.
Bootstrap messages from the RPF neighbor toward the
included BSR-, the router transits into the `AxptAny'
state.
In this case, if an elected BSR becomes unreachable, the
routers start accepting Bootstrap messages from another C-
BSR after the Bootstrap-timer expires. All PIM routers
within a domain converge on the preferred (with highest
priority and address) reachable C-BSR.
* Receiving Bootstrap Message
To avoid loops, an RPF check is performed on the included BSR
address. Upon receiving an Bootstrap message from the RPF neighbor
toward the included BSR, the following actions are taken:
1 If the router is not a C-BSR:
1 If the current state is 'AxptAny', the router accepts the
Bootstrap message, and transits into the 'AxptPref' state.
2 If the current state is 'AxptPref', and the Bootstrap
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 72]
message is preferred, the message is accepted. No state
transition is incurred.
2 If the router is a C-BSR, and the Bootstrap message is
preferred, the message is accepted. Further, if this happens
when the current state is
When an Bootstrap message is accepted, the router restarts the
Bootstrap-timer at [Bootstrap-Timeout], stores the received BSR
priority and address in `LclBSR', and the received RP-Set in
`LclRP-Set', and forwards the Bootstrap message out all interfaces
except the receiving interface.
If an Bootstrap message is rejected, no state transitions are
triggered.
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 73]
6.3 Appendix III: Glossary of Terms
Following is an alphabetized list of terms and definitions used
throughout this specification.
* {Bootstrap router (BSR)}. A BSR is a dynamically elected router
within a PIM domain. It is responsible for constructing the RP-
Set and originating Bootstrap messages.
* {Candidate-BSR (C-BSR)}. A C-BSR is a router configured to
participate in the BSR election and act as BSRs if elected.
* {Candidate RP (C-RP)}. A C-RP is a router configured to send
periodic Candidate-RP-Advertisement messages to the BSR, and act
as an RP when it receives Join/Prune or Register messages for
the advertised group prefix.
* {Designated Router (DR)}. The DR sets up multicast route
entries and sends corresponding Join/Prune and Register messages
on behalf of directly-connected receivers and sources,
respectively. The DR may or may not be the same router as the
IGMP Querier. The DR may or may not be the long-term, last-hop
router for the group; a router on the LAN that has a lower
metric route to the data source, or to the group's RP, may take
over the role of sending Join/Prune messages.
* {Incoming interface (iif)}. The iif of a multicast route entry
indicates the interface from which multicast data packets are
accepted for forwarding. The iif is initialized when the entry
is created.
* {Join list}. The Join list is one of two lists of addresses that
is included in a Join/Prune message; each address refers to a
source or RP. It indicates those sources or RPs to which
downstream receiver(s) wish to join.
* {Last-hop router}. The last-hop router is the last router to
receive multicast data packets before they are delivered to
directly-connected member hosts. In general the last-hop router
is the DR for the LAN. However, under various conditions
described in this document a parallel router connected to the
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 74]
same LAN may take over as the last-hop router in place of the
DR.
* {Outgoing interface (oif) list}. Each multicast route entry has
an oif list containing the outgoing interfaces to which
multicast packets should be forwarded.
* {Prune List}. The Prune list is the second list of addresses that
is included in a Join/Prune message. It indicates those sources
or RPs from which downstream receiver(s) wish to prune.
* {PIM Multicast Border Router (PMBR)}. A PMBR connects a PIM
domain to other multicast routing domain(s).
* {Rendezvous Point (RP)}. Each multicast group has a shared-tree
via which receivers hear of new sources and new receivers hear
of all sources. The RP is the root of this per-group shared
tree, called the RP-Tree.
* {RP-Set}. The RP-Set is a set of RP addresses constructed by
the BSR based on Candidate-RP advertisements received. The RP-
Set information is distributed to all PIM routers in the BSR's
PIM domain.
* {Reverse Path Forwarding (RPF)}. RPF is used to select the
appropriate incoming interface for a multicast route entry . The
RPF neighbor for an IP address X is the the next-hop router used
to forward packets toward X. The RPF interface is the interface
to that RPF neighbor. In the common case this is the next hop
used by the unicast routing protocol for sending unicast packets
toward X. For example, in cases where unicast and multicast
routes are not congruent, it can be different.
* {Route entry.} A multicast route entry is state maintained in a
router along the distribution tree and is created, and updated
based on incoming control messages. The route entry may be
different from the forwarding entry; the latter is used to
forward data packets in real time. Typically a forwarding entry
is not created until data packets arrive, the forwarding entry's
iif and oif list are copied from the route entry, and the
forwarding entry may be flushed and recreated at will.
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 75]
* {Shortest path tree (SPT)}. The SPT is the multicast
distribution tree created by the merger of all of the shortest
paths that connect receivers to the source (as determined by
unicast routing).
* {Sparse Mode (SM)}. SM is one mode of operation of a multicast
protocol. PIM SM uses explicit Join/Prune messages and
Rendezvous points in place of Dense Mode PIM's and DVMRP's
broadcast and prune mechanism.
* {Wildcard (WC) multicast route entry}. Wildcard multicast route
entries are those entries that may be used to forward packets
for any source sending to the specified group. Wildcard bots in
the join list of a Join/Prune message represent either a (*,G)
or (*,*,RP) join; in the prune list they represent a (*,G)
prune.
* {(S,G) route entry}. (S,G) is a source-specific route entry. It
may be created in response to data packets, Join/Prune messages,
or Asserts. The (S,G) state in routers creates a source-rooted,
shortest path (or reverse shortest path) distribution tree.
(S,G)RPT bit entries are source-specific entries on the shared
RP-Tree; these entries are used to prune particular sources off
of the shared tree.
* {(*,G) route entry}. Group members join the shared RP-Tree for
a particular group. This tree is represented by (*,G) multicast
route entries along the shortest path branches between the RP
and the group members.
* {(*,*,RP) route entry}. (*,*,RP) refers to any source and any
multicast group that maps to the RP included in the entry. The
routers along the shortest path branches between a domain's
RP(s) and its PMBRs keep (*,*,RP) state and use it to determine
how to deliver packets toward the PMBRs if data packets arrive
for which there is not a longer match. THe wildcard group in the
(*,*,RP) route entry is represented by a group address of
224.0.0.0 and a mask length of 4 bits.
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 76]
References References
1. S.Deering, D.Estrin, D.Farinacci, V.Jacobson, C.Liu, L.Wei, 1. S.Deering, D.Estrin, D.Farinacci, V.Jacobson, C.Liu, L.Wei,
P.Sharma, and A.Helmy. Protocol independent multicast (pim) : P.Sharma, and A.Helmy. Protocol independent multicast (pim) :
Motivation and architecture. Motivation and architecture.
Internet Draft, May 1995. Internet Draft, May 1995.
2. S.Deering, D.Estrin, D.Farinacci, V.Jacobson, C.Liu, and L.Wei. 2. S.Deering, D.Estrin, D.Farinacci, V.Jacobson, C.Liu, and L.Wei. The
The pim architecture for wide-area multicast routing. pim architecture for wide-area multicast routing.
ACM Transactions on Networks, April 1996. ACM Transactions on Networks, April 1996.
3. D.Estrin, D.Farinacci, V.Jacobson, C.Liu, L.Wei, P.Sharma, and 3. D.Estrin, D.Farinacci, V.Jacobson, C.Liu, L.Wei, P.Sharma, and
A.Helmy. Protocol independent multicast-dense mode (pim-dm) : A.Helmy. Protocol independent multicast-dense mode (pim-dm) :
Protocol specification. Internet Draft, November 1995. Protocol specification. Internet Draft, November 1995.
4. S.Deering. Host extensions for ip multicasting, aug 1989. 4. S.Deering. Host extensions for ip multicasting, aug 1989. RFC1112.
RFC1112.
5. R.Atkinson. Security architecture for the internet protocol, 5. W.Fenner. Internet group management protocol, version 2.
August 1995. RFC-1825. Internet Draft, May 1996.
6. A.J. Ballardie, P.F. Francis, and J.Crowcroft. Core based trees. 6. R.Atkinson. Security architecture for the internet protocol, August
In Proceedings of the ACM SIGCOMM, San Francisco, 1993. 1995. RFC-1825.
[Page 67] 7. A.J. Ballardie, P.F. Francis, and J.Crowcroft. Core based trees. In
Proceedings of the ACM SIGCOMM, San Francisco, 1993.
Estrin,Farinacci,Helmy,Thaler,Deering,Handley,Jacobson,Liu,Sharma,Wei [Page 77]
 End of changes. 

This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/