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