Tech-invite3GPPspaceIETF RFCsSIP
9190898887868584838281807978777675747372717069686766656463626160595857565554535251504948474645444342414039383736353433323130292827262524232221201918171615141312111009080706050403020100
in Index   Prev   Next

RFC 3973

Protocol Independent Multicast - Dense Mode (PIM-DM): Protocol Specification (Revised)

Pages: 61
Experimental
Errata
Updated by:  8736
Part 1 of 3 – Pages 1 to 13
None   None   Next

Top   ToC   RFC3973 - Page 1
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.
Top   ToC   RFC3973 - Page 2

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
Top   ToC   RFC3973 - Page 3
       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
Top   ToC   RFC3973 - Page 4

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.
Top   ToC   RFC3973 - Page 5

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.
Top   ToC   RFC3973 - Page 6
   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.
Top   ToC   RFC3973 - Page 7

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)
Top   ToC   RFC3973 - Page 8

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)
Top   ToC   RFC3973 - Page 9
   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}
Top   ToC   RFC3973 - Page 10
   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.
Top   ToC   RFC3973 - Page 11
   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.
Top   ToC   RFC3973 - Page 12

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.
Top   ToC   RFC3973 - Page 13

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)

Next Section