RFC 3973
Protocol Independent Multicast - Dense Mode (PIM-DM): Protocol Specification (Revised)
Network Working Group A. Adams Request for Comments: 3973 NextHop Technologies Category: Experimental J. Nicholas ITT A/CD W. Siadak NextHop Technologies January 2005 Protocol Independent Multicast - Dense Mode (PIM-DM): Protocol Specification (Revised) Status of This Memo This memo defines an Experimental Protocol for the Internet community. It does not specify an Internet standard of any kind. Discussion and suggestions for improvement are requested. Distribution of this memo is unlimited. Copyright Notice Copyright (C) The Internet Society (2005).Abstract
This document specifies Protocol Independent Multicast - Dense Mode (PIM-DM). PIM-DM is a multicast routing protocol that uses the underlying unicast routing information base to flood multicast datagrams to all multicast routers. Prune messages are used to prevent future messages from propagating to routers without group membership information.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1. Definitions . . . . . . . . . . . . . . . . . . . . . . 4 2.2. Pseudocode Notation . . . . . . . . . . . . . . . . . . 5 3. PIM-DM Protocol Overview . . . . . . . . . . . . . . . . . . . 5 4. Protocol Specification . . . . . . . . . . . . . . . . . . . . 6 4.1. PIM Protocol State . . . . . . . . . . . . . . . . . . . 7 4.1.1. General Purpose State . . . . . . . . . . . . . 7 4.1.2. (S,G) State . . . . . . . . . . . . . . . . . . 8 4.1.3. State Summarization Macros . . . . . . . . . . . 8 4.2. Data Packet Forwarding Rules . . . . . . . . . . . . . . 10 4.3. Hello Messages . . . . . . . . . . . . . . . . . . . . . 11 4.3.1. Sending Hello Messages . . . . . . . . . . . . . 11 4.3.2. Receiving Hello Messages . . . . . . . . . . . . 11 4.3.3. Hello Message Hold Time . . . . . . . . . . . . 12 4.3.4. Handling Router Failures . . . . . . . . . . . . 12 4.3.5. Reducing Prune Propagation Delay on LANs . . . . 13 4.4. PIM-DM Prune, Join, and Graft Messages . . . . . . . . . 13 4.4.1. Upstream Prune, Join, and Graft Messages . . . . 14 4.4.1.1. Transitions from the Forwarding (F) State . . . . . . . . . . . . . . 17 4.4.1.2. Transitions from the Pruned (P) State . . . . . . . . . . . . . . 18 4.4.1.3. Transitions from the AckPending (AP) State . . . . . . . . . . . . . . 19 4.4.2. Downstream Prune, Join, and Graft Messages . . . 21 4.4.2.1. Transitions from the NoInfo State . . 23 4.4.2.2. Transitions from the PrunePending (PP) State . . . . . . . . . . . . . . 24 4.4.2.3. Transitions from the Prune (P) State . . . . . . . . . . . . . . 25 4.5. State Refresh . . . . . . . . . . . . . . . . . . . . . 26 4.5.1. Forwarding of State Refresh Messages . . . . . . 26 4.5.2. State Refresh Message Origination . . . . . . . 28 4.5.2.1. Transitions from the NotOriginator (NO) State . . . . . . . . . . . . . . 29 4.5.2.2. Transitions from the Originator (O) State . . . . . . . . . . . . . . 29
4.6. PIM Assert Messages . . . . . . . . . . . . . . . . . . 30
4.6.1. Assert Metrics . . . . . . . . . . . . . . . . . 30
4.6.2. AssertCancel Messages . . . . . . . . . . . . . 31
4.6.3. Assert State Macros . . . . . . . . . . . . . . 32
4.6.4. (S,G) Assert Message State Machine . . . . . . . 32
4.6.4.1. Transitions from NoInfo State . . . . 34
4.6.4.2. Transitions from Winner State . . . . 35
4.6.4.3. Transitions from Loser State . . . . . 36
4.6.5. Rationale for Assert Rules . . . . . . . . . . . 38
4.7. PIM Packet Formats . . . . . . . . . . . . . . . . . . . 38
4.7.1. PIM Header . . . . . . . . . . . . . . . . . . . 38
4.7.2. Encoded Unicast Address . . . . . . . . . . . . 39
4.7.3. Encoded Group Address . . . . . . . . . . . . . 40
4.7.4. Encoded Source Address . . . . . . . . . . . . . 41
4.7.5. Hello Message Format . . . . . . . . . . . . . . 42
4.7.5.1. Hello Hold Time Option . . . . . . . . 43
4.7.5.2. LAN Prune Delay Option . . . . . . . . 43
4.7.5.3. Generation ID Option . . . . . . . . . 44
4.7.5.4. State Refresh Capable Option . . . . . 44
4.7.6. Join/Prune Message Format . . . . . . . . . . . 45
4.7.7. Assert Message Format . . . . . . . . . . . . . 47
4.7.8. Graft Message Format . . . . . . . . . . . . . . 48
4.7.9. Graft Ack Message Format . . . . . . . . . . . . 48
4.7.10. State Refresh Message Format . . . . . . . . . . 48
4.8. PIM-DM Timers . . . . . . . . . . . . . . . . . . . . . 50
5. Protocol Interaction Considerations . . . . . . . . . . . . . 53
5.1. PIM-SM Interactions . . . . . . . . . . . . . . . . . . 53
5.2. IGMP Interactions . . . . . . . . . . . . . . . . . . . 54
5.3. Source Specific Multicast (SSM) Interactions . . . . . . 54
5.4. Multicast Group Scope Boundary Interactions . . . . . . 54
6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 54
6.1. PIM Address Family . . . . . . . . . . . . . . . . . . . 54
6.2. PIM Hello Options . . . . . . . . . . . . . . . . . . . 55
7. Security Considerations. . . . . . . . . . . . . . . . . . . . 55
7.1. Attacks Based on Forged Messages . . . . . . . . . . . . 55
7.2. Non-cryptographic Authentication Mechanisms . . . . . . 56
7.3. Authentication Using IPsec . . . . . . . . . . . . . . . 56
7.4. Denial of Service Attacks . . . . . . . . . . . . . . . 58
8. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 58
9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 58
9.1. Normative References . . . . . . . . . . . . . . . . . . 58
9.2. Informative References . . . . . . . . . . . . . . . . . 59
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 60
Full Copyright Statement . . . . . . . . . . . . . . . . . . . . . 61
1. Introduction
This specification defines a multicast routing algorithm for multicast groups that are densely distributed across a network. This protocol does not have a topology discovery mechanism often used by a unicast routing protocol. It employs the same packet formats sparse mode PIM (PIM-SM) uses. This protocol is called PIM - Dense Mode. The foundation of this design was largely built on Deering's early work on IP multicast routing [12].2. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" are to be interpreted as described in RFC 2119 [11] and indicate requirement levels for compliant PIM-DM implementations.2.1. Definitions
Multicast Routing Information Base (MRIB) This is the multicast topology table, which is typically derived from the unicast routing table, or from routing protocols such as MBGP that carry multicast-specific topology information. PIM-DM uses the MRIB to make decisions regarding RPF interfaces. Tree Information Base (TIB) This is the collection of state maintained by a PIM router and created by receiving PIM messages and IGMP information from local hosts. It essentially stores the state of all multicast distribution trees at that router. Reverse Path Forwarding (RPF) RPF is a multicast forwarding mode in which a data packet is accepted for forwarding only if it is received on an interface used to reach the source in unicast. Upstream Interface Interface toward the source of the datagram. Also known as the RPF Interface. Downstream Interface All interfaces that are not the upstream interface, including the router itself. (S,G) Pair Source S and destination group G associated with an IP packet.
2.2. Pseudocode Notation
We use set notation in several places in this specification. A (+) B is the union of two sets, A and B. A (-) B are the elements of set A that are not in set B. NULL is the empty set or list. Note that operations MUST be conducted in the order specified. This is due to the fact that (-) is not a true difference operator, because B is not necessarily a subset of A. That is, A (+) B (-) C = A (-) C (+) B is not a true statement unless C is a subset of both A and B. In addition, we use C-like syntax: = denotes assignment of a variable. == denotes a comparison for equality. != denotes a comparison for inequality. Braces { and } are used for grouping.3. PIM-DM Protocol Overview
This section provides an overview of PIM-DM behavior. It is intended as an introduction to how PIM-DM works and is NOT definitive. For the definitive specification, see Section 4, Protocol Specification. PIM-DM assumes that when a source starts sending, all downstream systems want to receive multicast datagrams. Initially, multicast datagrams are flooded to all areas of the network. PIM-DM uses RPF to prevent looping of multicast datagrams while flooding. If some areas of the network do not have group members, PIM-DM will prune off the forwarding branch by instantiating prune state. Prune state has a finite lifetime. When that lifetime expires, data will again be forwarded down the previously pruned branch. Prune state is associated with an (S,G) pair. When a new member for a group G appears in a pruned area, a router can "graft" toward the source S for the group, thereby turning the pruned branch back into a forwarding branch.
The broadcast of datagrams followed by pruning of unwanted branches is often referred to as a flood and prune cycle and is typical of dense mode protocols. To minimize repeated flooding of datagrams and subsequent pruning associated with a particular (S,G) pair, PIM-DM uses a state refresh message. This message is sent by the router(s) directly connected to the source and is propagated throughout the network. When received by a router on its RPF interface, the state refresh message causes an existing prune state to be refreshed. Compared with multicast routing protocols with built-in topology discovery mechanisms (e.g., DVMRP [13]), PIM-DM has a simplified design and is not hard-wired into a specific topology discovery protocol. However, this simplification does incur more overhead by causing flooding and pruning to occur on some links that could be avoided if sufficient topology information were available; i.e., to decide whether an interface leads to any downstream members of a particular group. Additional overhead is chosen in favor of the simplification and flexibility gained by not depending on a specific topology discovery protocol. PIM-DM differs from PIM-SM in two essential ways: 1) There are no periodic joins transmitted, only explicitly triggered prunes and grafts. 2) There is no Rendezvous Point (RP). This is particularly important in networks that cannot tolerate a single point of failure. (An RP is the root of a shared multicast distribution tree. For more details, see [4]).4. Protocol Specification
The specification of PIM-DM is broken into several parts: * Section 4.1 details the protocol state stored. * Section 4.2 specifies the data packet forwarding rules. * Section 4.3 specifies generation and processing of Hello messages. * Section 4.4 specifies the Join, Prune, and Graft generation and processing rules. * Section 4.5 specifies the State Refresh generation and forwarding rules. * Section 4.6 specifies the Assert generation and processing rules. * Section 4.7 gives details on PIM-DM Packet Formats. * Section 4.8 summarizes PIM-DM timers and their defaults.
4.1. PIM Protocol State
This section specifies all the protocol states that a PIM-DM implementation should maintain to function correctly. We term this state the Tree Information Base or TIB, as it holds the state of all the multicast distribution trees at this router. In this specification, we define PIM-DM mechanisms in terms of the TIB. However, only a very simple implementation would actually implement packet forwarding operations in terms of this state. Most implementations will use this state to build a multicast forwarding table, which would then be updated when the relevant state in the TIB changes. Unlike PIM-SM, PIM-DM does not maintain a keepalive timer associated with each (S,G) route. Within PIM-DM, route and state information associated with an (S,G) entry MUST be maintained as long as any timer associated with that (S,G) entry is active. When no timer associated with an (S,G) entry is active, all information concerning that (S,G) route may be discarded. Although we precisely specify the state to be kept, this does not mean that an implementation of PIM-DM has to hold the state in this form. This is actually an abstract state definition, which is needed in order to specify the router's behavior. A PIM-DM implementation is free to hold whatever internal state it requires and will still be conformant with this specification as long as it results in the same externally visible protocol behavior as an abstract router that holds the following state.4.1.1. General Purpose State
A router stores the following non-group-specific state: For each interface: Hello Timer (HT) State Refresh Capable LAN Delay Enabled Propagation Delay (PD) Override Interval (OI) Neighbor State: For each neighbor: Information from neighbor's Hello Neighbor's Gen ID. Neighbor's LAN Prune Delay Neighbor's Override Interval Neighbor's State Refresh Capability Neighbor Liveness Timer (NLT)
4.1.2. (S,G) State
For every source/group pair (S,G), a router stores the following state: (S,G) state: For each interface: Local Membership: State: One of {"NoInfo", "Include"} PIM (S,G) Prune State: State: One of {"NoInfo" (NI), "Pruned" (P), "PrunePending" (PP)} Prune Pending Timer (PPT) Prune Timer (PT) (S,G) Assert Winner State: State: One of {"NoInfo" (NI), "I lost Assert" (L), "I won Assert" (W)} Assert Timer (AT) Assert winner's IP Address Assert winner's Assert Metric Upstream interface-specific: Graft/Prune State: State: One of {"NoInfo" (NI), "Pruned" (P), "Forwarding" (F), "AckPending" (AP) } GraftRetry Timer (GRT) Override Timer (OT) Prune Limit Timer (PLT) Originator State: Source Active Timer (SAT) State Refresh Timer (SRT)4.1.3. State Summarization Macros
Using the state defined above, the following "macros" are defined and will be used in the descriptions of the state machines and pseudocode in the following sections. The most important macros are those defining the outgoing interface list (or "olist") for the relevant state. immediate_olist(S,G) = pim_nbrs (-) prunes(S,G) (+) (pim_include(*,G) (-) pim_exclude(S,G) ) (+) pim_include(S,G) (-) lost_assert(S,G) (-) boundary(G)
olist(S,G) = immediate_olist(S,G) (-) RPF_interface(S)
The macros pim_include(*,G) and pim_include(S,G) indicate the
interfaces to which traffic might or might not be forwarded because
of hosts that are local members on those interfaces.
pim_include(*,G) = {all interfaces I such that:
local_receiver_include(*,G,I)}
pim_include(S,G) = {all interfaces I such that:
local_receiver_include(S,G,I)}
pim_exclude(S,G) = {all interfaces I such that:
local_receiver_exclude(S,G,I)}
The macro RPF_interface(S) returns the RPF interface for source S.
That is to say, it returns the interface used to reach S as indicated
by the MRIB.
The macro local_receiver_include(S,G,I) is true if the IGMP module or
other local membership mechanism ([1], [2], [3], [6]) has determined
that there are local members on interface I that seek to receive
traffic sent specifically by S to G.
The macro local_receiver_include(*,G,I) is true if the IGMP module or
other local membership mechanism has determined that there are local
members on interface I that seek to receive all traffic sent to G.
Note that this determination is expected to account for membership
joins initiated on or by the router.
The macro local_receiver_exclude(S,G,I) is true if
local_receiver_include(*,G,I) is true but none of the local members
seek to receive traffic from S.
The set pim_nbrs is the set of all interfaces on which the router has
at least one active PIM neighbor.
The set prunes(S,G) is the set of all interfaces on which the router
has received Prune(S,G) messages:
prunes(S,G) = {all interfaces I such that
DownstreamPState(S,G,I) is in Pruned state}
The set lost_assert(S,G) is the set of all interfaces on which the
router has lost an (S,G) Assert.
lost_assert(S,G) = {all interfaces I such that
lost_assert(S,G,I) == TRUE}
boundary(G) = {all interfaces I with an administratively scoped
boundary for group G}
The following pseudocode macro definitions are also used in many
places in the specification. Basically RPF' is the RPF neighbor
toward a source unless a PIM-DM Assert has overridden the normal
choice of neighbor.
neighbor RPF'(S,G) {
if ( I_Am_Assert_loser(S, G, RPF_interface(S) )) {
return AssertWinner(S, G, RPF_interface(S) )
} else {
return MRIB.next_hop( S )
}
}
The macro I_Am_Assert_loser(S, G, I) is true if the Assert state
machine (in Section 4.6) for (S,G) on interface I is in the "I am
Assert Loser" state.
4.2. Data Packet Forwarding Rules
The PIM-DM packet forwarding rules are defined below in pseudocode.
iif is the incoming interface of the packet. S is the source address
of the packet. G is the destination address of the packet (group
address). RPF_interface(S) is the interface the MRIB indicates would
be used to route packets to S.
First, an RPF check MUST be performed to determine whether the packet
should be accepted based on TIB state and the interface on which that
the packet arrived. Packets that fail the RPF check MUST NOT be
forwarded, and the router will conduct an assert process for the
(S,G) pair specified in the packet. Packets for which a route to the
source cannot be found MUST be discarded.
If the RPF check has been passed, an outgoing interface list is
constructed for the packet. If this list is not empty, then the
packet MUST be forwarded to all listed interfaces. If the list is
empty, then the router will conduct a prune process for the (S,G)
pair specified in the packet.
Upon receipt of a data packet from S addressed to G on interface iif:
if (iif == RPF_interface(S) AND UpstreamPState(S,G) != Pruned) {
oiflist = olist(S,G)
} else {
oiflist = NULL
}
forward packet on all interfaces in oiflist
This pseudocode employs the following "macro" definition:
UpstreamPState(S,G) is the state of the Upstream(S,G) state machine
in Section 4.4.1.
4.3. Hello Messages
This section describes the generation and processing of Hello
messages.
4.3.1. Sending Hello Messages
PIM-DM uses Hello messages to detect other PIM routers. Hello
messages are sent periodically on each PIM enabled interface. Hello
messages are multicast to the ALL-PIM-ROUTERS group. When PIM is
enabled on an interface or when a router first starts, the Hello
Timer (HT) MUST be set to random value between 0 and
Triggered_Hello_Delay. This prevents synchronization of Hello
messages if multiple routers are powered on simultaneously.
After the initial Hello message, a Hello message MUST be sent every
Hello_Period. A single Hello timer MAY be used to trigger sending
Hello messages on all active interfaces. The Hello Timer SHOULD NOT
be reset except when it expires.
4.3.2. Receiving Hello Messages
When a Hello message is received, the receiving router SHALL record
the receiving interface, the sender, and any information contained in
recognized options. This information is retained for a number of
seconds in the Hold Time field of the Hello Message. If a new Hello
message is received from a particular neighbor N, the Neighbor
Liveness Timer (NLT(N,I)) MUST be reset to the newly received Hello
Holdtime. If a Hello message is received from a new neighbor, the
receiving router SHOULD send its own Hello message after a random
delay between 0 and Triggered_Hello_Delay.
4.3.3. Hello Message Hold Time
The Hold Time in the Hello Message should be set to a value that can reasonably be expected to keep the Hello active until a new Hello message is received. On most links, this will be 3.5 times the value of Hello_Period. If the Hold Time is set to '0xffff', the receiving router MUST NOT time out that Hello message. This feature might be used for on- demand links to avoid keeping the link up with periodic Hello messages. If a Hold Time of '0' is received, the corresponding neighbor state expires immediately. When a PIM router takes an interface down or changes IP address, a Hello message with a zero Hold Time SHOULD be sent immediately (with the old IP address if the IP address is changed) to cause any PIM neighbors to remove the old information immediately.4.3.4. Handling Router Failures
If a Hello message is received from an active neighbor with a different Generation ID (GenID), the neighbor has restarted and may not contain the correct (S,G) state. A Hello message SHOULD be sent after a random delay between 0 and Triggered_Hello_Delay (see 4.8) before any other messages are sent. If the neighbor is downstream, the router MAY replay the last State Refresh message for any (S,G) pairs for which it is the Assert Winner indicating Prune and Assert status to the downstream router. These State Refresh messages SHOULD be sent out immediately after the Hello message. If the neighbor is the upstream neighbor for an (S,G) entry, the router MAY cancel its Prune Limit Timer to permit sending a prune and reestablishing a Pruned state in the upstream router. Upon startup, a router MAY use any State Refresh messages received within Hello_Period of its first Hello message on an interface to establish state information. The State Refresh source will be the RPF'(S), and Prune status for all interfaces will be set according to the Prune Indicator bit in the State Refresh message. If the Prune Indicator is set, the router SHOULD set the PruneLimitTimer to Prune_Holdtime and set the PruneTimer on all downstream interfaces to the State Refresh's Interval times two. The router SHOULD then propagate the State Refresh as described in Section 4.5.1.
4.3.5. Reducing Prune Propagation Delay on LANs
If all routers on a LAN support the LAN Prune Delay option, then the PIM routers on that LAN will use the values received to adjust their J/P_Override_Interval on that interface and the interface is LAN Delay Enabled. Briefly, to avoid synchronization of Prune Override (Join) messages when multiple downstream routers share a multi-access link, sending of these messages is delayed by a small random amount of time. The period of randomization is configurable and has a default value of 3 seconds. Each router on the LAN expresses its view of the amount of randomization necessary in the Override Interval field of the LAN Prune Delay option. When all routers on a LAN use the LAN Prune Delay Option, all routers on the LAN MUST set their Override_Interval to the largest Override value on the LAN. The LAN Delay inserted by a router in the LAN Prune Delay option expresses the expected message propagation delay on the link and SHOULD be configurable by the system administrator. When all routers on a link use the LAN Prune Delay Option, all routers on the LAN MUST set Propagation Delay to the largest LAN Delay on the LAN. PIM implementers should enforce a lower bound on the permitted values for this delay to allow for scheduling and processing delays within their router. Such delays may cause received messages to be processed later and triggered messages to be sent later than intended. Setting this LAN Prune Delay to too low a value may result in temporary forwarding outages, because a downstream router will not be able to override a neighbor's prune message before the upstream neighbor stops forwarding.
(page 13 continued on part 2)
