home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1997 December / Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso / rfc / rfc2117 < prev    next >
Text File  |  1997-06-16  |  152KB  |  3,701 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7. Network Working Group                                       D.  Estrin
  8. Request for Comments: 2117                                         USC
  9. Category: Experimental                                    D. Farinacci
  10.                                                                  CISCO
  11.                                                               A. Helmy
  12.                                                                    USC
  13.                                                              D. Thaler
  14.                                                                  UMICH
  15.                                                             S. Deering
  16.                                                                  XEROX
  17.                                                             M. Handley
  18.                                                                    UCL
  19.                                                            V. Jacobson
  20.                                                                    LBL
  21.                                                                 C. Liu
  22.                                                                    USC
  23.                                                              P. Sharma
  24.                                                                    USC
  25.                                                                 L. Wei
  26.                                                                  CISCO
  27.                                                              June 1997
  28.  
  29.  
  30.  
  31.      Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol
  32.                              Specification
  33.  
  34. Status of This Memo
  35.  
  36.    This memo defines an Experimental Protocol for the Internet
  37.    community.  This memo does not specify an Internet standard of any
  38.    kind.  Discussion and suggestions for improvement are requested.
  39.    Distribution of this memo is unlimited.
  40.  
  41. Acknowledgements
  42.  
  43.    The author list has been reordered to reflect the involvement in
  44.    detailed editorial work on this specification document.  The first
  45.    four authors are the primary editors and are listed alphabetically.
  46.    The rest of the authors, also listed alphabetically, participated in
  47.    all aspects of the architectural and detailed design but managed to
  48.    get away without hacking the latex!
  49.  
  50.  
  51.  
  52.  
  53.  
  54.  
  55.  
  56.  
  57.  
  58. Estrin, et. al.               Experimental                      [Page 1]
  59.  
  60. RFC 2117                         PIM-SM                       June 1997
  61.  
  62.  
  63. 1 Introduction
  64.  
  65.    This document describes a protocol for efficiently routing to
  66.    multicast groups that may span wide-area (and inter-domain)
  67.    internets.  We refer to the approach as Protocol Independent
  68.    Multicast--Sparse Mode (PIM-SM) because it is not dependent on any
  69.    particular unicast routing protocol, and because it is designed to
  70.    support sparse groups as defined in [1][2]. This document describes
  71.    the protocol details.  For the motivation behind the design and a
  72.    description of the architecture, see [1][2]. Section 2 summarizes
  73.    PIM-SM operation.  It describes the protocol from a network
  74.    perspective, in particular, how the participating routers interact to
  75.    create and maintain the multicast distribution tree.  Section 3
  76.    describes PIM-SM operations from the perspective of a single router
  77.    implementing the protocol; this section constitutes the main body of
  78.    the protocol specification.  It is organized according to PIM-SM
  79.    message type; for each message type we describe its contents, its
  80.    generation, and its processing.
  81.  
  82.    Sections 3.8 and 3.9 summarize the timers and flags referred to
  83.    throughout this document. Section 4 provides packet format details.
  84.  
  85.    The most significant functional changes since the January '95 version
  86.    involve the Rendezvous Point-related mechanisms, several resulting
  87.    simplifications to the protocol, and removal of the PIM-DM protocol
  88.    details to a separate document [3] (for clarity).
  89.  
  90. 2 PIM-SM Protocol Overview
  91.  
  92.    In this section we provide an overview of the architectural
  93.    components of PIM-SM.
  94.  
  95.    A router receives explicit Join/Prune messages from those neighboring
  96.    routers that have downstream group members. The router then forwards
  97.    data packets addressed to a multicast group, G, only onto those
  98.    interfaces on which explicit joins have been received. Note that all
  99.    routers mentioned in this document are assumed to be PIM-SM capable,
  100.    unless otherwise specified.
  101.  
  102.    A Designated Router (DR) sends periodic Join/Prune messages toward a
  103.    group-specific Rendezvous Point (RP) for each group for which it has
  104.    active members. Each router along the path toward the RP builds a
  105.    wildcard (any-source) state for the group and sends Join/Prune
  106.    messages on toward the RP. We use the term route entry to refer to
  107.    the state maintained in a router to represent the distribution tree.
  108.    A route entry may include such fields as the source address, the
  109.    group address, the incoming interface from which packets are
  110.    accepted, the list of outgoing interfaces to which packets are sent,
  111.  
  112.  
  113.  
  114. Estrin, et. al.               Experimental                      [Page 2]
  115.  
  116. RFC 2117                         PIM-SM                       June 1997
  117.  
  118.  
  119.    timers, flag bits, etc. The wildcard route entry's incoming interface
  120.    points toward the RP; the outgoing interfaces point to the
  121.    neighboring downstream routers that have sent Join/Prune messages
  122.    toward the RP. This state creates a shared, RP-centered, distribution
  123.    tree that reaches all group members. When a data source first sends
  124.    to a group, its DR unicasts Register messages to the RP with the
  125.    source's data packets encapsulated within. If the data rate is high,
  126.    the RP can send source-specific Join/Prune messages back towards the
  127.    source and the source's data packets will follow the resulting
  128.    forwarding state and travel unencapsulated to the RP.  Whether they
  129.    arrive encapsulated or natively, the RP forwards the source's
  130.    decapsulated data packets down the RP-centered distribution tree
  131.    toward group members.  If the data rate warrants it, routers with
  132.    local receivers can join a source-specific, shortest path,
  133.    distribution tree, and prune this source's packets off of the shared
  134.    RP-centered tree. For low data rate sources, neither the RP, nor
  135.    last-hop routers need join a source-specific shortest path tree and
  136.    data packets can be delivered via the shared, RP-tree.
  137.  
  138.    The following subsections describe SM operation in more detail, in
  139.    particular, the control messages, and the actions they trigger.
  140.  
  141. 2.1 Local hosts joining a group
  142.  
  143.  
  144.    In order to join a multicast group, G, a host conveys its membership
  145.    information through the Internet Group Management Protocol (IGMP), as
  146.    specified in [4][5], (see figure 1).  From this point on we refer to
  147.    such a host as a receiver, R, (or member) of the group G.
  148.  
  149.    Note that all figures used in this section are for illustration and
  150.    are not intended to be complete. For complete and detailed protocol
  151.    action see Section 3.
  152.  
  153.       [Figures are present only in the postscript version]
  154.       Fig. 1  Example: how a receiver joins, and sets up shared tree
  155.  
  156.  
  157.    When a DR (e.g., router A in figure 1) gets a membership indication
  158.    from IGMP for a new group, G, the DR looks up the associated RP. The
  159.    DR creates a wildcard multicast route entry for the group, referred
  160.    to here as a (*,G) entry; if there is no more specific match for a
  161.    particular source, the packet will be forwarded according to this
  162.    entry.
  163.  
  164.  
  165.  
  166.  
  167.  
  168.  
  169.  
  170. Estrin, et. al.               Experimental                      [Page 3]
  171.  
  172. RFC 2117                         PIM-SM                       June 1997
  173.  
  174.  
  175.    The RP address is included in a special field in the route entry and
  176.    is included in periodic upstream Join/Prune messages. The outgoing
  177.    interface is set to that included in the IGMP membership indication
  178.    for the new member.  The incoming interface is set to the interface
  179.    used to send unicast packets to the RP.
  180.  
  181.    When there are no longer directly connected members for the group,
  182.    IGMP notifies the DR.  If the DR has neither local members nor
  183.    downstream receivers, the (*,G) state is deleted.
  184.  
  185. 2.2 Establishing the RP-rooted shared tree
  186.  
  187.    Triggered by the (*,G) state, the DR creates a Join/Prune message
  188.    with the RP address in its join list and the the wildcard bit (WC-
  189.    bit) and RP-tree bit (RPT-bit) set to 1. The WC-bit indicates that
  190.    any source may match and be forwarded according to this entry if
  191.    there is no longer match; the RPT-bit indicates that this join is
  192.    being sent up the shared, RP-tree. The prune list is left empty. When
  193.    the RPT-bit is set to 1 it indicates that the join is associated with
  194.    the shared RP-tree and therefore the Join/Prune message is propagated
  195.    along the RP-tree. When the WC-bit is set to 1 it indicates that the
  196.    address is an RP and the downstream receivers expect to receive
  197.    packets from all sources via this (shared tree) path. The term RPT-
  198.    bit is used to refer to both the RPT-bit flags associated with route
  199.    entries, and the RPT-bit included in each encoded address in a
  200.    Join/Prune message.
  201.  
  202.    Each upstream router creates or updates its multicast route entry for
  203.    (*,G) when it receives a Join/Prune with the RPT-bit and WC-bit set.
  204.    The interface on which the Join/Prune message arrived is added to the
  205.    list of outgoing interfaces (oifs) for (*,G). Based on this entry
  206.    each upstream router between the receiver and the RP sends a
  207.    Join/Prune message in which the join list includes the RP. The packet
  208.    payload contains Multicast-Address=G, Join=RP,WC-bit,RPT-bit,
  209.    Prune=NULL.
  210.  
  211. 2.3 Hosts sending to a group
  212.  
  213.    When a host starts sending multicast data packets to a group,
  214.    initially its DR must deliver each packet to the RP for distribution
  215.    down the RP-tree (see figure 2).  The sender's DR initially
  216.    encapsulates each data packet in a Register message and unicasts it
  217.    to the RP for that group. The RP decapsulates each Register message
  218.    and forwards the enclosed data packet natively to downstream members
  219.    on the shared RP-tree.
  220.  
  221.       [Figures are present only in the postscript version]
  222.       Fig. 2  Example: a host sending to a group
  223.  
  224.  
  225.  
  226. Estrin, et. al.               Experimental                      [Page 4]
  227.  
  228. RFC 2117                         PIM-SM                       June 1997
  229.  
  230.  
  231.    If the data rate of the source warrants the use of a source-specific
  232.    shortest path tree (SPT), the RP may construct a new multicast route
  233.    entry that is specific to the source, hereafter referred to as (S,G)
  234.    state, and send periodic Join/Prune messages toward the source. Note
  235.    that over time, the rules for when to switch can be modified without
  236.    global coordination.  When and if the RP does switch to the SPT, the
  237.    routers between the source and the RP build and maintain (S,G) state
  238.    in response to these messages and send (S,G) messages upstream toward
  239.    the source.
  240.  
  241.    The source's DR must stop encapsulating data packets in Registers
  242.    when (and so long as) it receives Register-Stop messages from the RP.
  243.    The RP triggers Register-Stop messages in response to Registers, if
  244.    the RP has no downstream receivers for the group (or for that
  245.    particular source), or if the RP has already joined the (S,G) tree
  246.    and is receiving the data packets natively.  Each source's DR
  247.    maintains, per (S,G), a Register-Suppression-timer.  The Register-
  248.    Suppression-timer is started by the Register-Stop message; upon
  249.    expiration, the source's DR resumes sending data packets to the RP,
  250.    encapsulated in Register messages.
  251.  
  252. 2.4 Switching from shared tree (RP-tree)  to  shortest  path  tree  (SP-
  253.       tree)
  254.  
  255.    A router with directly-connected members first joins the shared RP-
  256.    tree.  The router can switch to a source's shortest path tree (SP-
  257.    tree) after receiving packets from that source over the shared RP-
  258.    tree. The recommended policy is to initiate the switch to the SP-tree
  259.    after receiving a significant number of data packets during a
  260.    specified time interval from a particular source. To realize this
  261.    policy the router can monitor data packets from sources for which it
  262.    has no source-specific multicast route entry and initiate such an
  263.    entry when the data rate exceeds the configured threshold.  As shown
  264.    in figure 3, router `A' initiates a (S,G) state.
  265.  
  266.       [Figures are present only in the postscript version]
  267.       Fig. 3  Example: Switching from shared tree to shortest path tree
  268.  
  269.    When a (S,G) entry is activated (and periodically so long as the
  270.    state exists), a Join/Prune message is sent upstream towards the
  271.    source, S, with S in the join list. The payload contains Multicast-
  272.    Address=G, Join=S, Prune=NULL. When the (S,G) entry is created, the
  273.    outgoing interface list is copied from (*,G), i.e., all local shared
  274.    tree branches are replicated in the new shortest path tree. In this
  275.    way when a data packet from S arrives and matches on this entry, all
  276.    receivers will continue to receive the source's packets along this
  277.    path. (In more complicated scenarios, other entries in the router
  278.    have to be considered, as described in Section 3). Note that (S,G)
  279.  
  280.  
  281.  
  282. Estrin, et. al.               Experimental                      [Page 5]
  283.  
  284. RFC 2117                         PIM-SM                       June 1997
  285.  
  286.  
  287.    state must be maintained in each last-hop router that is responsible
  288.    for initiating and maintaining an SP-tree. Even when (*,G) and (S,G)
  289.    overlap, both states are needed to trigger the source-specific
  290.    Join/Prune messages.  (S,G) state is kept alive by data packets
  291.    arriving from that source. A timer, Entry-timer, is set for the (S,G)
  292.    entry and this timer is restarted whenever data packets for (S,G) are
  293.    forwarded out at least one oif, or Registers are sent.  When the
  294.    Entry-timer expires, the state is deleted. The last-hop router is the
  295.    router that delivers the packets to their ultimate end-system
  296.    destination.  This is the router that monitors if there is group
  297.    membership and joins or prunes the appropriate distribution trees in
  298.    response.  In general the last-hop router is the Designated Router
  299.    (DR) for the LAN. However, under various conditions described later,
  300.    a parallel router connected to the same LAN may take over as the
  301.    last-hop router in place of the DR.
  302.  
  303.    Only the RP and routers with local members can initiate switching to
  304.    the SP-tree; intermediate routers do not. Consequently, last-hop
  305.    routers create (S,G) state in response to data packets from the
  306.    source, S; whereas intermediate routers only create (S,G) state in
  307.    response to Join/Prune messages from downstream that have S in the
  308.    Join list.
  309.  
  310.    The (S,G) entry is initialized with the SPT-bit cleared, indicating
  311.    that the shortest path tree branch from S has not yet been setup
  312.    completely, and the router can still accept packets from S that
  313.    arrive on the (*,G) entry's indicated incoming interface (iif). Each
  314.    PIM multicast entry has an associated incoming interface on which
  315.    packets are expected to arrive.
  316.  
  317.    When a router with a (S,G) entry and a cleared SPT-bit starts to
  318.    receive packets from the new source S on the iif for the (S,G) entry,
  319.    and that iif differs from the (*,G) entry's iif, the router sets the
  320.    SPT-bit, and sends a Join/Prune message towards the RP, indicating
  321.    that the router no longer wants to receive packets from S via the
  322.    shared RP-tree. The Join/Prune message sent towards the RP includes S
  323.    in the prune list, with the RPT-bit set indicating that S's packets
  324.    must not be forwarded down this branch of the shared tree. If the
  325.    router receiving the Join/Prune message has (S,G) state (with or
  326.    without the route entry's RPT-bit flag set), it deletes the arriving
  327.    interface from the (S,G) oif list.  If the router has only (*,G)
  328.    state, it creates an entry with the RPT-bit flag set to 1. For
  329.  
  330.  
  331.  
  332.  
  333.  
  334.  
  335.  
  336.  
  337.  
  338. Estrin, et. al.               Experimental                      [Page 6]
  339.  
  340. RFC 2117                         PIM-SM                       June 1997
  341.  
  342.  
  343.    brevity we refer to an (S,G) entry that has the RPT-bit flag set to 1
  344.    as an (S,G)RPT-bit entry. This notational distinction is useful to
  345.    point out the different actions taken for (S,G) entries depending on
  346.    the setting of the RPT-bit flag. Note that a router can have no more
  347.    than one active (S,G) entry for any particular S and G, at any
  348.    particular time; whether the RPT-bit flag is set or not. In other
  349.    words, a router never has both an (S,G) and an (S,G)RPT-bit entry for
  350.    the same S and G at the same time. The Join/Prune message payload
  351.    contains Multicast-Address=G, Join=NULL, Prune=S,RPT-bit.
  352.  
  353.    A new receiver may join an existing RP-tree on which source-specific
  354.    prune state has been established (e.g., because downstream receivers
  355.    have switched to SP-trees). In this case the prune state must be
  356.    eradicated upstream of the new receiver to bring all sources' data
  357.    packets down to the new receiver.  Therefore, when a (*,G) Join
  358.    arrives at a router that has any (Si,G)RPT-bit entries (i.e., entries
  359.    that cause the router to send source-specific prunes toward the RP),
  360.    these entries must be updated upstream of the router so as to bring
  361.    all sources' packets down to the new member. To accomplish this, each
  362.    router that receives a (*,G) Join/Prune message updates all existing
  363.    (S,G)RPT-bit entries. The router may also trigger a (*,G) Join/Prune
  364.    message upstream to cause the same updating of RPT-bit settings
  365.    upstream and pull down all active sources' packets. If the arriving
  366.    (*,G) join has some sources included in its prune list, then the
  367.    corresponding (S,G)RPT-bit entries are left unchanged (i.e., the
  368.    RPT-bit remains set and no oif is added).
  369.  
  370. 2.5 Steady state maintenance of distribution tree (i.e., router state)
  371.  
  372.    In the steady state each router sends periodic Join/Prune messages
  373.    for each active PIM route entry; the Join/Prune messages are sent to
  374.    the neighbor indicated in the corresponding entry. These messages are
  375.    sent periodically to capture state, topology, and membership changes.
  376.    A Join/Prune message is also sent on an event-triggered basis each
  377.    time a new route entry is established for some new source (note that
  378.    some damping function may be applied, e.g., a short delay to allow
  379.    for merging of new Join information). Join/Prune messages do not
  380.    elicit any form of explicit acknowledgment; routers recover from lost
  381.    packets using the periodic refresh mechanism.
  382.  
  383. 2.6 Obtaining RP information
  384.  
  385.    To obtain the RP information, all routers within a PIM domain collect
  386.    Bootstrap messages. Bootstrap messages are sent hop-by-hop within the
  387.    domain; the domain's bootstrap router (BSR) is responsible for
  388.    originating the Bootstrap messages. Bootstrap messages are used to
  389.    carry out a dynamic BSR election when needed and to distribute RP
  390.    information in steady state.
  391.  
  392.  
  393.  
  394. Estrin, et. al.               Experimental                      [Page 7]
  395.  
  396. RFC 2117                         PIM-SM                       June 1997
  397.  
  398.  
  399.    A domain in this context is a contiguous set of routers that all
  400.    implement PIM and are configured to operate within a common boundary
  401.    defined by PIM Multicast Border Routers (PMBRs). PMBRs connect each
  402.    PIM domain to the rest of the internet.
  403.  
  404.    Routers use a set of available RPs (called the {RP-Set}) distributed
  405.    in Bootstrap messages to get the proper Group to RP mapping. The
  406.    following paragraphs summarize the mechanism; details of the
  407.    mechanism may be found in Sections 3.6 and Appendix 6.2. A (small)
  408.    set of routers, within a domain, are configured as candidate BSRs
  409.    and, through a simple election mechanism, a single BSR is selected
  410.    for that domain. A set of routers within a domain are also configured
  411.    as candidate RPs (C-RPs); typically these will be the same routers
  412.    that are configured as C-BSRs.  Candidate RPs periodically unicast
  413.    Candidate-RP-Advertisement messages (C-RP-Advs) to the BSR of that
  414.    domain. C-RP-Advs include the address of the advertising C-RP, as
  415.    well as an optional group address and a mask length field, indicating
  416.    the group prefix(es) for which the candidacy is advertised.  The BSR
  417.    then includes a set of these Candidate-RPs (the RP-Set), along with
  418.    the corresponding group prefixes, in Bootstrap messages it
  419.    periodically originates.  Bootstrap messages are distributed hop-by-
  420.    hop throughout the domain.
  421.  
  422.    Routers receive and store Bootstrap messages originated by the BSR.
  423.    When a DR gets a membership indication from IGMP for (or a data
  424.    packet from) a directly connected host, for a group for which it has
  425.    no entry, the DR uses a hash function to map the group address to one
  426.    of the C-RPs whose Group-prefix includes the group (see Section 3.7).
  427.    The DR then sends a Join/Prune message towards (or unicasts Registers
  428.    to) that RP.
  429.  
  430.    The Bootstrap message indicates liveness of the RPs included therein.
  431.    If an RP is included in the message, then it is tagged as `up' at the
  432.    routers; while RPs not included in the message are removed from the
  433.    list of RPs over which the hash algorithm acts. Each router continues
  434.    to use the contents of the most recently received Bootstrap message
  435.    until it receives a new Bootstrap message.
  436.  
  437.    If a PIM domain partitions, each area separated from the old BSR will
  438.    elect its own BSR, which will distribute an RP-Set containing RPs
  439.    that are reachable within that partition. When the partition heals,
  440.    another election will occur automatically and only one of the BSRs
  441.    will continue to send out Bootstrap messages. As is expected at the
  442.    time of a partition or healing, some disruption in packet delivery
  443.    may occur.  This time will be on the order of the region's round-trip
  444.    time and the bootstrap router timeout value.
  445.  
  446.  
  447.  
  448.  
  449.  
  450. Estrin, et. al.               Experimental                      [Page 8]
  451.  
  452. RFC 2117                         PIM-SM                       June 1997
  453.  
  454.  
  455. 2.7 Interoperation with dense mode  protocols such as DVMRP
  456.  
  457.    In order to interoperate with networks that run dense-mode,
  458.    {broadcast and prune}, protocols, such as DVMRP, all packets
  459.    generated within a PIM-SM region must be pulled out to that region's
  460.    PIM Multicast Border Routers (PMBRs) and injected (i.e., broadcast)
  461.    into the DVMRP network.  A PMBR is a router that sits at the boundary
  462.    of a PIM-SM domain and interoperates with other types of multicast
  463.    routers such as those that run DVMRP.  Generally a PMBR would speak
  464.    both protocols and implement interoperability functions not required
  465.    by regular PIM routers. To support interoperability, a special entry
  466.    type, referred to as (*,*,RP), must be supported by all PIM routers.
  467.    For this reason we include details about (*,*,RP) entry handling in
  468.    this general PIM specification.
  469.  
  470.    A data packet will match on a (*,*,RP) entry if there is no more
  471.    specific entry (such as (S,G) or (*,G)) and the destination group
  472.    address in the packet maps to the RP listed in the (*,*,RP) entry. In
  473.    this sense, a (*,*,RP) entry represents an aggregation of all the
  474.    groups that hash to that RP. PMBRs initialize (*,*,RP) state for each
  475.    RP in the domain's RPset. The (*,*,RP) state causes the PMBRs to send
  476.    (*,*,RP) Join/Prune messages toward each of the active RPs in the
  477.    domain.  As a result distribution trees are built that carry all data
  478.    packets originated within the PIM domain (and sent to the RPs) down
  479.    to the PMBRs.
  480.  
  481.    PMBRs are also responsible for delivering externally-generated
  482.    packets to routers within the PIM domain. To do so, PMBRs initially
  483.    encapsulate externally-originated packets (i.e., received on DVMRP
  484.    interfaces) in Register messages and unicast them to the
  485.    corresponding RP within the PIM domain. The Register message has a
  486.    bit indicating that it was originated by a border router and the RP
  487.    caches the originating PMBR's address in the route entry so that
  488.    duplicate Registers from other PMBRs can be declined with a
  489.    Register-Stop message.
  490.  
  491.    All PIM routers must be capable of supporting (*,*,RP) state and
  492.    interpreting associated Join/Prune messages. We describe the handling
  493.    of (*,*,RP) entries and messages throughout this document; however,
  494.    detailed PIM Multicast Border Router (PMBR) functions will be
  495.    specified in a separate interoperability document (see directory,
  496.    http://catarina.usc.edu/pim/interop/).
  497.  
  498. 2.8 Multicast data packet processing
  499.  
  500.    Data packets are processed in a manner similar to other multicast
  501.    schemes.  A router first performs a longest match on the source and
  502.    group address in the data packet. A (S,G) entry is matched first if
  503.  
  504.  
  505.  
  506. Estrin, et. al.               Experimental                      [Page 9]
  507.  
  508. RFC 2117                         PIM-SM                       June 1997
  509.  
  510.  
  511.    one exists; a (*,G) entry is matched otherwise. If neither state
  512.    exists, then a (*,*,RP) entry match is attempted as follows: the
  513.    router hashes on G to identify the RP for group G, and looks for a
  514.    (*,*,RP) entry that has this RP address associated with it.  If none
  515.    of the above exists, then the packet is dropped. If a state is
  516.    matched, the router compares the interface on which the packet
  517.    arrived to the incoming interface field in the matched route entry.
  518.    If the iif check fails the packet is dropped, otherwise the packet is
  519.    forwarded to all interfaces listed in the outgoing interface list.
  520.  
  521.    Some special actions are needed to deliver packets continuously while
  522.    switching from the shared to shortest-path tree. In particular, when
  523.    a (S,G) entry is matched, incoming packets are forwarded as follows:
  524.  
  525.       1    If the SPT-bit is set, then:
  526.  
  527.  
  528.            1    if the incoming interface is the same as a matching
  529.                 (S,G) iif, the packet is forwarded to the oif-list of
  530.                 (S,G).
  531.  
  532.            2    if the incoming interface is different than a matching
  533.                 (S,G) iif , the packet is discarded.
  534.  
  535.  
  536.  
  537.       2    If the SPT-bit is cleared, then:
  538.  
  539.  
  540.            1    if the incoming interface is the same as a matching
  541.                 (S,G) iif, the packet is forwarded to the oif-list of
  542.                 (S,G). In addition, the SPT bit is set for that entry
  543.                 if the incoming interface differs from the incoming
  544.                 interface of the (*,G) or (*,*,RP) entry.
  545.  
  546.            2    if the incoming interface is different than a matching
  547.                 (S,G) iif, the incoming interface is tested against a
  548.                 matching (*,G) or (*,*,RP) entry. If the iif is the
  549.                 same as one of those, the packet is forwarded to the
  550.                 oif-list of the matching entry.
  551.  
  552.            3    Otherwise the iif does not match any entry for G and
  553.                 the packet is discarded.
  554.  
  555.    Data packets never trigger prunes.  However, data packets may trigger
  556.    actions that in turn trigger prunes. For example, when router B in
  557.    figure 3 decides to switch to SP-tree at step 3, it creates a (S,G)
  558.    entry with SPT-bit set to 0. When data packets from S arrive at
  559.  
  560.  
  561.  
  562. Estrin, et. al.               Experimental                     [Page 10]
  563.  
  564. RFC 2117                         PIM-SM                       June 1997
  565.  
  566.  
  567.    interface 2 of B, B sets the SPT-bit to 1 since the iif for (*,G) is
  568.    different than that for (S,G). This triggers the sending of prunes
  569.    towards the RP.
  570.  
  571. 2.9 Operation over Multi-access Networks
  572.  
  573.    This section describes a few additional protocol mechanisms needed to
  574.    operate PIM over multi-access networks: Designated Router election,
  575.    Assert messages to resolve parallel paths, and the Join/Prune-
  576.    Suppression-Timer to suppress redundant Joins on multi-access
  577.    networks.
  578.  
  579.    * Designated router election
  580.  
  581.    When there are multiple routers connected to a multi-access network,
  582.    one of them must be chosen to operate as the designated router (DR)
  583.    at any point in time.  The DR is responsible for sending triggered
  584.    Join/Prune and Register messages toward the RP.
  585.  
  586.    A simple designated router (DR) election mechanism is used for both
  587.    SM and traditional IP multicast routing.  Neighboring routers send
  588.    Hello messages to each other. The sender with the largest IP address
  589.    assumes the role of DR. Each router connected to the multi-access LAN
  590.    sends the Hellos periodically in order to adapt to changes in router
  591.    status.
  592.  
  593.    * Parallel paths to a source or the RP--Assert process
  594.  
  595.    If a router receives a multicast datagram on a multi-access LAN from
  596.    a source whose corresponding (S,G) outgoing interface list includes
  597.    the interface to that LAN, the packet must be a duplicate.  In this
  598.    case a single forwarder must be elected.  Using Assert messages
  599.    addressed to `224.0.0.13' (ALL-PIM-ROUTERS group) on the LAN,
  600.    upstream routers can resolve which one will act as the forwarder.
  601.    Downstream routers listen to the Asserts so they know which one was
  602.    elected, and therefore where to send subsequent Joins. Typically this
  603.    is the same as the downstream router's RPF (Reverse Path Forwarding)
  604.    neighbor; but there are circumstances where this might not be the
  605.    case, e.g., when using multiple unicast routing protocols on that
  606.    LAN. The RPF neighbor for a particular source (or RP) is the next-hop
  607.    router to which packets are forwarded en route to that source (or
  608.    RP); and therefore is considered a good path via which to accept
  609.    packets from that source.
  610.  
  611.    The upstream router elected is the one that has the shortest distance
  612.    to the source. Therefore, when a packet is received on an outgoing
  613.    interface a router sends an Assert message on the multi-access LAN
  614.    indicating what metric it uses to reach the source of the data
  615.  
  616.  
  617.  
  618. Estrin, et. al.               Experimental                     [Page 11]
  619.  
  620. RFC 2117                         PIM-SM                       June 1997
  621.  
  622.  
  623.    packet.  The router with the smallest numerical metric (with ties
  624.    broken by highest address) will become the forwarder. All other
  625.    upstream routers will delete the interface from their outgoing
  626.    interface list. The downstream routers also do the comparison in case
  627.    the forwarder is different than the RPF neighbor.
  628.  
  629.    Associated with the metric is a metric preference value. This is
  630.    provided to deal with the case where the upstream routers may run
  631.    different unicast routing protocols. The numerically smaller metric
  632.    preference is always preferred. The metric preference is treated as
  633.    the high-order part of an assert metric comparison.  Therefore, a
  634.    metric value can be compared with another metric value provided both
  635.    metric preferences are the same.  A metric preference can be assigned
  636.    per unicast routing protocol and needs to be consistent for all
  637.    routers on the multi-access network.
  638.  
  639.    Asserts are also needed for (*,G) entries since an RP-Tree and an
  640.    SP-Tree for the same group may both cross the same multi- access
  641.    network. When an assert is sent for a (*,G) entry, the first bit in
  642.    the metric preference (RPT-bit) is always set to 1 to indicate that
  643.    this path corresponds to the RP tree, and that the match must be done
  644.    on (*,G) if it exists. Furthermore, the RPT-bit is always cleared for
  645.    metric preferences that refer to SP-tree entries; this causes an SP-
  646.    tree path to always look better than an RP-tree path. When the SP-
  647.    tree and RPtree cross the same LAN, this mechanism eliminates the
  648.    duplicates that would otherwise be carried over the LAN.
  649.  
  650.    In case the packet, or the Assert message, matches  on  oif  for
  651.    (*,*,RP) entry, a (*,G) entry is created, and asserts take place as
  652.    if the matching state were (*,G).
  653.  
  654.    The DR may lose the (*,G) Assert process to another router on the LAN
  655.    if there are multiple paths to the RP through the LAN.  From then on,
  656.    the DR is no longer the last-hop router for local receivers and
  657.    removes the LAN from its (*,G) oif list. The winning router becomes
  658.    the last-hop router and is responsible for sending (*,G) join
  659.    messages to the RP.
  660.  
  661.    * Join/Prune suppression
  662.  
  663.    Join/Prune suppression may be used on multi-access LANs to reduce
  664.    duplicate control message overhead; it is not required for correct
  665.    performance of the protocol. If a Join/Prune message arrives and
  666.    matches on the incoming interface for an existing (S,G), (*,G), or
  667.    (*,*,RP) route entry, and the Holdtime included in the Join/Prune
  668.    message is greater than the recipient's own [Join/Prune-Holdtime]
  669.    (with ties resolved in favor of the higher IP address), a timer (the
  670.    Join/Prune-Suppression-timer) in the recipient's route entry may be
  671.  
  672.  
  673.  
  674. Estrin, et. al.               Experimental                     [Page 12]
  675.  
  676. RFC 2117                         PIM-SM                       June 1997
  677.  
  678.  
  679.    started to suppress further Join/Prune messages.  After this timer
  680.    expires, the recipient triggers a Join/Prune message, and resumes
  681.    sending periodic Join/Prunes, for this entry. The Join/Prune-
  682.    Suppression-timer should be restarted each time a Join/Prune message
  683.    is received with a higher Holdtime.
  684.  
  685. 2.10 Unicast Routing Changes
  686.  
  687.    When unicast routing changes, an RPF check is done on all active
  688.    (S,G), (*,G) and (*,*,RP) entries, and all affected expected incoming
  689.    interfaces are updated.  In particular, if the new incoming interface
  690.    appears in the outgoing interface list, it is deleted from the
  691.    outgoing interface list. The previous incoming interface may be added
  692.    to the outgoing interface list by a subsequent Join/Prune from
  693.    downstream.  Join/Prune messages received on the current incoming
  694.    interface are ignored.  Join/Prune messages received on new
  695.    interfaces or existing outgoing interfaces are not ignored. Other
  696.    outgoing interfaces are left as is until they are explicitly pruned
  697.    by downstream routers or are timed out due to lack of appropriate
  698.    Join/Prune messages. If the router has a (S,G) entry with the SPT-bit
  699.    set, and the updated iif(S,G) does not differ from iif(*,G) or
  700.    iif(*,*,RP), then the router resets the SPT-bit.
  701.  
  702.    The router must send a Join/Prune message with S in the Join list out
  703.    any new incoming interfaces to inform upstream routers that it
  704.    expects multicast datagrams over the interface.  It may also send a
  705.    Join/Prune message with S in the Prune list out the old incoming
  706.    interface, if the link is operational, to inform upstream routers
  707.    that this part of the distribution tree is going away.
  708.  
  709. 2.11 PIM-SM for Inter-Domain Multicast
  710.  
  711.    Future documents will address the use of PIM-SM as a backbone inter-
  712.    domain multicast routing protocol. Design choices center primarily
  713.    around the distribution and usage of RP information for wide area,
  714.    inter-domain groups.
  715.  
  716. 2.12 Security
  717.  
  718.    All PIM control messages may use IPsec [6] to address security
  719.    concerns.  Security mechanisms are likely to be enhanced in the near
  720.    future.
  721.  
  722. 3 Detailed Protocol Description
  723.  
  724.    This section describes the protocol operations from the perspective
  725.    of an individual router implementation.  In particular, for each
  726.    message type we describe how it is generated and processed.
  727.  
  728.  
  729.  
  730. Estrin, et. al.               Experimental                     [Page 13]
  731.  
  732. RFC 2117                         PIM-SM                       June 1997
  733.  
  734.  
  735. 3.1 Hello
  736.  
  737.    Hello messages are sent so neighboring routers can discover each
  738.    other.
  739.  
  740. 3.1.1 Sending Hellos
  741.  
  742.    Hello messages are sent periodically between PIM neighbors, every
  743.    [Hello-Period] seconds.  This informs routers what interfaces have
  744.    PIM neighbors.  Hello messages are multicast using address 224.0.0.13
  745.    (ALL-PIM-ROUTERS group). The packet includes a Holdtime, set to
  746.    [Hello-Holdtime], for neighbors to keep the information valid.
  747.    Hellos are sent on all types of communication links.
  748.  
  749. 3.1.2 Receiving Hellos
  750.  
  751.    When a router receives a Hello message, it stores the IP address for
  752.    that neighbor, sets its Neighbor-timer for the Hello sender to the
  753.    Holdtime included in the Hello, and determines the Designated Router
  754.    (DR) for that interface.  The highest IP addressed system is elected
  755.    DR. Each Hello received causes the DR's address to be updated.
  756.  
  757.    When a router that is the active DR receives a Hello from a new
  758.    neighbor (i.e., from an IP address that is not yet in the DRs
  759.    neighbor table), the DR unicasts its most recent RP-set information
  760.    to the new neighbor.
  761.  
  762. 3.1.3 Timing out neighbor entries
  763.  
  764.    A periodic process is run to time out PIM neighbors that have not
  765.    sent Hellos. If the DR has gone down, a new DR is chosen by scanning
  766.    all neighbors on the interface and selecting the new DR to be the one
  767.    with the highest IP address. If an interface has gone down, the
  768.    router may optionally time out all PIM neighbors associated with the
  769.    interface.
  770.  
  771. 3.2 Join/Prune
  772.  
  773.    Join/Prune messages are sent to join or prune a branch off of the
  774.    multicast distribution tree. A single message contains both a join
  775.    and prune list, either one of which may be null.  Each list contains
  776.    a set of source addresses, indicating the source- specific trees or
  777.    shared tree that the router wants to join or prune.
  778.  
  779. 3.2.1 Sending Join/Prune Messages
  780.  
  781.    Join/Prune messages are merged such that a message sent to a
  782.    particular upstream neighbor, N, includes all of the current joined
  783.  
  784.  
  785.  
  786. Estrin, et. al.               Experimental                     [Page 14]
  787.  
  788. RFC 2117                         PIM-SM                       June 1997
  789.  
  790.  
  791.    and pruned sources that are reached via N; according to unicast
  792.    routing Join/Prune messages are multicast to all routers on multi-
  793.    access networks with the target address set to the next hop router
  794.    towards S or RP. Join/Prune messages are sent every [Join/Prune-
  795.    Period] seconds. In the future we will introduce mechanisms to rate-
  796.    limit this control traffic on a hop by hop basis, in order to avoid
  797.    excessive overhead on small links.  In addition, certain events cause
  798.    triggered Join/Prune messages to be sent.
  799.  
  800. 3.2.1.1 Periodic Join/Prune Messages
  801.  
  802.    A router sends a periodic Join/Prune message to each distinct RPF
  803.    neighbor associated with each (S,G), (*,G) and (*,*,RP) entry.
  804.    Join/Prune messages are only sent if the RPF neighbor is a PIM
  805.    neighbor.  A periodic Join/Prune message sent to a particular RPF
  806.    neighbor is constructed as follows:
  807.  
  808.    1    Each router determines the RP for a (*,G) entry by using
  809.         the hash function described. The RP address (with RPT and
  810.         WC bits set) is included in the join list of a periodic
  811.         Join/Prune message under the following conditions:
  812.  
  813.         1    The Join/Prune message is being sent to the RPF
  814.              neighbor toward the RP for an active (*,G) or (*,*,RP)
  815.              entry, and
  816.  
  817.         2    The outgoing interface list in the (*,G) or (*,*,RP)
  818.              entry is non-NULL, or the router is the DR on the same
  819.              interface as the RPF neighbor.
  820.  
  821.    2    A particular source address, S, is included in the join
  822.         list with the RPT and WC bits cleared under the following
  823.         conditions:
  824.  
  825.         1    The Join/Prune message is being sent to the RPF
  826.              neighbor toward S, and
  827.  
  828.         2    There exists an active (S,G) entry with the RPT-bit
  829.              flag cleared, and
  830.  
  831.         3    The oif list in the (S,G) entry is not null.
  832.  
  833.    3    A particular source address, S, is included in the prune
  834.         list with the RPT and WC bits cleared under the following
  835.         conditions:
  836.  
  837.         1    The Join/Prune message is being sent to the RPF
  838.              neighbor toward S, and
  839.  
  840.  
  841.  
  842. Estrin, et. al.               Experimental                     [Page 15]
  843.  
  844. RFC 2117                         PIM-SM                       June 1997
  845.  
  846.  
  847.         2    There exists an active (S,G) entry with the RPT-bit
  848.              flag cleared, and
  849.  
  850.         3    The oif list in the (S,G) entry is null.
  851.  
  852.    4    A particular source address, S, is included in the prune
  853.         list with the RPT-bit set and the WC bit cleared under the
  854.         following conditions:
  855.  
  856.         1    The Join/Prune message is being sent to the RPF
  857.              neighbor toward the RP and there exists a (S,G) entry
  858.              with the RPT-bit flag set and null oif list, or
  859.  
  860.         2    The Join/Prune message is being sent to the RPF
  861.              neighbor toward the RP, there exists a (S,G) entry
  862.              with the RPT-bit flag cleared and SPT-bit set, and the
  863.              incoming interface toward S is different than the
  864.              incoming interface toward the RP, or
  865.  
  866.         3    The Join/Prune message is being sent to the RPF
  867.              neighbor toward the RP, and there exists a (*,G) entry
  868.              and (S,G) entry for a directly connected source.
  869.  
  870.    5    The RP address (with RPT and WC bits set) is included in
  871.         the prune list if:
  872.  
  873.         1    The Join/Prune message is being sent to the RPF
  874.              neighbor toward the RP and there exists a (*,G) entry
  875.              with a null oif list (see Section 3.5.2).
  876.  
  877. 3.2.1.2 Triggered Join/Prune Messages
  878.  
  879.    In addition to periodic messages, the following events will trigger
  880.    Join/Prune messages if as a result, a) a new entry is created, or b)
  881.    the oif list changes from null to non-null or non-null to null. The
  882.    contents of triggered messages are the same as the periodic,
  883.    described above.
  884.  
  885.    1    Receipt of an indication from IGMP that the state of
  886.         directly-connected- membership has changed (i.e., new members
  887.         have just joined `membership indication' or all members have
  888.         left), for a group G, may cause the last-hop router to build
  889.         or modify corresponding (*,G) state.  When IGMP indicates
  890.         that there are no longer directly connected members, the oif
  891.         is removed from the oif list if the oif- timer is not
  892.         running.  A Join/Prune message is triggered if and only if
  893.         a) a new entry is created, or b) the oif list changes from
  894.         null to non-null or non-null to null, as follows :
  895.  
  896.  
  897.  
  898. Estrin, et. al.               Experimental                     [Page 16]
  899.  
  900. RFC 2117                         PIM-SM                       June 1997
  901.  
  902.  
  903.         1    If the receiving router does not have a route entry
  904.              for G the router creates a (*,G) entry, copies the
  905.              oif list from the corresponding (*,*,RP) entry
  906.              (if it exists), and includes the interface included
  907.              in the IGMP membership indication in the oif list;
  908.              as always, the router never includes the entry's iif
  909.              in the oif list.  The router sends a Join/Prune
  910.              message towards the RP with the RP address and RPT-bit
  911.              and WC-bits set in the join list. Or,
  912.  
  913.         2    If a (S,G)RPT-bit or (*,G) entry already exists, the
  914.              interface included in the IGMP membership indication
  915.              is added to the oif list (if it was not included already).
  916.  
  917.    2    Receipt of a Join/Prune message for (S,G), (*,G) or (*,*,RP)
  918.         will cause building or modifying corresponding state, and
  919.         subsequent triggering of upstream Join/Prune messages, in the
  920.         following cases:
  921.  
  922.         1    When there is no current route entry, the RP address
  923.              included in the Join/Prune message is checked against
  924.              the local RP-Set information. If it matches, an entry
  925.              will be created and the new entry will in turn trigger
  926.              an upstream Join/Prune message. If the router has no
  927.              RP-Set information it may discard the message, or
  928.              optionally use the RP address included in the message.
  929.  
  930.         2    When the outgoing interface list of an (S,G)RPT-bit
  931.              entry becomes null, the triggered Join/Prune message
  932.              will contain S in the prune list.
  933.  
  934.         3    When there exists a (S,G)RPT-bit with null oif list,
  935.              and an (*,G) Join/Prune message is received, the
  936.              arriving interface is added to the oif list and a (*,G)
  937.              Join/Prune message is triggered upstream.
  938.  
  939.         4    When there exists a (*,G) with null oif list, and a
  940.              (*,*,RP) Join/Prune message is received, the receiving
  941.              interface is added to the oif list and a (*,*,RP)
  942.              Join/Prune message is triggered upstream.
  943.  
  944.    3    Receipt of a packet that matches on a (S,G) entry whose
  945.         SPT-bit is cleared triggers the following if the packet
  946.         arrived on the correct incoming interface and there is a
  947.         (*,G) or (*,*,RP) entry with a different incoming
  948.         interface: a) the router sets the SPT-bit on the (S,G)
  949.         entry, and b) the router sends a Join/Prune message
  950.         towards the RP with S and a set RPT-bit in the prune list.
  951.  
  952.  
  953.  
  954. Estrin, et. al.               Experimental                     [Page 17]
  955.  
  956. RFC 2117                         PIM-SM                       June 1997
  957.  
  958.  
  959.    4    When a Join/Prune message is received for a group G, the
  960.         prune list is checked. If the prune list contains a source
  961.         or RP for which the receiving router has a corresponding
  962.         active (S,G), (*,G) or (*,*,RP) entry, and whose iif is
  963.         that on which the Join/Prune was received, then a join for
  964.         (S,G), (*,G) or (*,*,RP) is triggered to override the prune,
  965.         respectively. (This is necessary in the case of parallel
  966.         downstream routers connected to a multi-access network.)
  967.  
  968.    5    When the RP fails, the RP will not be included in the
  969.         Bootstrap messages sent to all routers in that domain.
  970.         This triggers the DRs to send (*,G) Join/Prune messages
  971.         towards new RP for the group, as determined by the RP-Set
  972.         and the hash function.  As described earlier, PMBRs trigger
  973.         (*,*,RP) joins towards each RP in the RP-Set.
  974.  
  975.    6    When an entry's Join/Prune-Suppression timer expires, a
  976.         Join/Prune message is triggered upstream corresponding to
  977.         that entry, even if the outgoing interface has not
  978.         transitioned between null and non-null states.
  979.  
  980.    7    When the RPF neighbor changes (whether due to an Assert or
  981.         changes in unicast routing), the router sets a random delay
  982.         timer (the Random-Delay-Join-Timer) whose expiration triggers
  983.         sending of a Join/Prune message for the asserted route entry
  984.         to the Assert winner (if the Join/Prune Suppression timer has
  985.         expired.)
  986.  
  987.    We do not trigger prunes onto interfaces based on data packets.  Data
  988.    packets that arrive on the wrong incoming interface are silently
  989.    dropped.  However, on point-to-point interfaces triggered prunes may
  990.    be sent as an optimization.
  991.  
  992.    3.2.1.3 Fragmentation: It is possible that a Join/Prune message
  993.    constructed according to the preceding rules could exceed the MTU of
  994.    a network. In this case, the message can undergo semantic
  995.    fragmentation whereby information corresponding to different groups
  996.    can be sent in different messages.  However, if a Join/Prune message
  997.    must be fragmented the complete prune list corresponding to a group G
  998.    must be included in the same Join/Prune message as the associated
  999.    RP-tree Join for G. If such semantic fragmentation is not possible,
  1000.    IP fragmentation should be used between the two neighboring hops.
  1001.  
  1002.  
  1003.  
  1004.  
  1005.  
  1006.  
  1007.  
  1008.  
  1009.  
  1010. Estrin, et. al.               Experimental                     [Page 18]
  1011.  
  1012. RFC 2117                         PIM-SM                       June 1997
  1013.  
  1014.  
  1015. 3.2.2 Receiving Join/Prune Messages When a router receives a
  1016.            Join/Prune message, it processes it as follows.
  1017.  
  1018.    The receiver of the Join/Prune notes the interface on which the PIM
  1019.    message arrived, call it I. The receiver then checks to see if the
  1020.    Join/Prune message was addressed to the receiving router itself
  1021.    (i.e., the router's address appears in the Unicast Upstream Neighbor
  1022.    Router field of the Join/Prune message).  (If the router is connected
  1023.    to a multiaccess LAN, the message could be intended for a different
  1024.    router.) If the Join/Prune is for this router the following actions
  1025.    are taken.
  1026.  
  1027.    For each group address G, in the Join/Prune message, the associated
  1028.    join list is processed as follows. We refer to each address in the
  1029.    join list as Sj; Sj refers to the RP if the RPT- bit and WC-bit are
  1030.    both set. For each Sj in the join list of the Join/Prune message:
  1031.  
  1032.    1    If an address, Sj, in the join list of the Join/Prune
  1033.         message  has  the RPT-bit and WC-bit set, then Sj is the RP
  1034.         address used by the downstream router(s) and the  following
  1035.         actions are taken:
  1036.  
  1037.         1    If Sj is not the same as the receiving router's RP
  1038.              mapping for G, the receiving router may ignore the
  1039.              Join/Prune message with respect to that group entry.
  1040.              If the router does not have any RP-Set information, it
  1041.              may use the address Sj included in the Join/Prune
  1042.              message as the RP for the group.
  1043.  
  1044.         2    If Sj is the same as the receiving router's RP mapping
  1045.              for G, the receiving router adds I to the outgoing
  1046.              interface list of the (*,G) route entry (if there is
  1047.              no (*,G) entry, the router creates one first) and sets
  1048.              the Oif-timer for that interface to the Holdtime
  1049.              specified in the Join/Prune message.  In addition, the
  1050.              Oif-Deletion-Delay for that interface is set to 1/3rd
  1051.              the Holdtime specified in the Join/Prune message.
  1052.  
  1053.              If a (*,*,RP) entry exists, for the RP associated with
  1054.              G, then the oif list of the newly created (*,G) entry
  1055.              is copied from that (*,*,RP) entry.
  1056.  
  1057.         3    For each (Si,G) entry associated with group G, if Si
  1058.              is not included in the prune list, and if I is not the
  1059.              iif then interface I is added to the oif list and the
  1060.              Oif-timer for that interface in each affected entry
  1061.              is increased (never decreased) to the Holdtime included
  1062.              in the Join/Prune message.  In addition, if the
  1063.  
  1064.  
  1065.  
  1066. Estrin, et. al.               Experimental                     [Page 19]
  1067.  
  1068. RFC 2117                         PIM-SM                       June 1997
  1069.  
  1070.  
  1071.              Oif-timer for that interface is increased, the
  1072.              Oif-Deletion-Delay for that interface is set to 1/3rd
  1073.              the Holdtime specified in the Join/Prune message.
  1074.  
  1075.              If the group address in the Join/Prune message is `*'
  1076.              then every (*,G) and (S,G) entry, whose group address
  1077.              hashes to the RP indicated in the (*,*,RP) Join/Prune
  1078.              message, is updated accordingly. A `*' in the group
  1079.              field of the Join/Prune is represented by a group
  1080.              address 224.0.0.0 and a group mask length of 4,
  1081.              indicating a (*,*,RP) Join.
  1082.  
  1083.         4    If the (Si,G) entry has its RPT-bit flag set to 1, and
  1084.              its oif list is the same as the (*,G) oif list, then
  1085.              the (Si,G)RPT-bit entry is deleted,
  1086.  
  1087.         5    The incoming interface is set to the interface used to
  1088.              send unicast packets to the RP in the (*,G) route
  1089.              entry, i.e., RPF interface toward the RP.
  1090.  
  1091.    2    For each address, Sj, in the join list whose RPT-bit and
  1092.         WC-bit are not set, and for which there is no existing (Sj,G)
  1093.         route entry, the router initiates one.  The router creates a
  1094.         (S,G) entry and copies all outgoing interfaces from the
  1095.         (S,G)RPT-bit entry, if it exists. If there is no (S,G) entry,
  1096.         the oif list is copied from the (*,G) entry; and if there is
  1097.         no (*,G) entry, the oif list is copied from the (*,*,RP)
  1098.         entry, if it exists.  In all cases, the iif of the (S,G)
  1099.         entry is always excluded from the oif list.
  1100.  
  1101.         1    The outgoing interface for (Sj,G) is set to I.  The
  1102.              incoming interface for (Sj,G) is set to the interface
  1103.              used to send unicast packets to Sj (i.e., the RPF
  1104.              neighbor).
  1105.  
  1106.         2    If the interface used to reach Sj, is the same as I,
  1107.              this represents an error (or a unicast routing change)
  1108.              and the Join/Prune must not be processed.
  1109.  
  1110.  
  1111.  
  1112.  
  1113.  
  1114.  
  1115.  
  1116.  
  1117.  
  1118.  
  1119.  
  1120.  
  1121.  
  1122. Estrin, et. al.               Experimental                     [Page 20]
  1123.  
  1124. RFC 2117                         PIM-SM                       June 1997
  1125.  
  1126.  
  1127.    3    For each address, Sj, in the join list of the Join/Prune
  1128.         message, for which there is an existing (Sj,G) route entry,
  1129.  
  1130.         1    If the RPT-bit is not set for Sj listed in the
  1131.              Join/Prune message, but the RPT-bit flag is set on the
  1132.              existing (Sj,G) entry, the router clears the RPT-bit
  1133.              flag on the (Sj,G) entry, sets the incoming interface
  1134.              to point towards Sj for that (Sj,G) entry, and sends a
  1135.              Join/Prune message corresponding to that entry through
  1136.              the new incoming interface; and
  1137.  
  1138.         2    If I is not the same as the existing incoming
  1139.              interface, the router adds I to the list of outgoing
  1140.              interfaces.
  1141.  
  1142.         3    The Oif-timer for I is increased (never decreased)
  1143.              to the Holdtime included in the Join/Prune message.
  1144.              In addition, if the Oif-timer for that interface is
  1145.              increased, the Oif-Deletion-Delay for that interface
  1146.              is set to 1/3rd the Holdtime specified in the
  1147.              Join/Prune message.
  1148.  
  1149.         4    The (Sj,G) entry's SPT bit is cleared until data comes
  1150.              down the shortest path tree.
  1151.  
  1152.    For each group address G, in the Join/Prune message, the associated
  1153.    prune list is processed as follows. We refer to each address in the
  1154.    prune list as Sp; Sp refers to the RP if the RPT-bit and WC-bit are
  1155.    both set. For each Sp in the prune list of the Join/Prune message:
  1156.  
  1157.  
  1158.    1    For each address, Sp, in the prune list whose RPT-bit and
  1159.         WC-bit are cleared:
  1160.  
  1161.         1    If there is an existing (Sp,G) route entry, the router
  1162.              lowers the Oif-timer for I to its Oif-Deletion-Delay,
  1163.              allowing for other downstream routers on a multi-
  1164.              access LAN to override the prune. However, on point-
  1165.              to-point links, the oif-timer is expired immediately.
  1166.  
  1167.         2    If the router has a current (*,G), or (*,*,RP), route
  1168.              entry, and if the existing (Sp,G) entry has its RPT-
  1169.              bit flag set to 1, then this (Sp,G)RPT-bit entry is
  1170.              maintained (not deleted) even if its outgoing
  1171.              interface list is null.
  1172.  
  1173.  
  1174.  
  1175.  
  1176.  
  1177.  
  1178. Estrin, et. al.               Experimental                     [Page 21]
  1179.  
  1180. RFC 2117                         PIM-SM                       June 1997
  1181.  
  1182.  
  1183.    2    For each address, Sp, in the prune list whose RPT-bit is
  1184.         set and whose WC-bit cleared:
  1185.  
  1186.         1    If there is an existing (Sp,G) route entry, the router
  1187.              lowers the entry's Oif-timer for I to its
  1188.              Oif-Deletion-Delay, allowing for other downstream
  1189.              routers on a multi- access LAN to override the prune.
  1190.              However, on point-to-point links, the oif-timer is
  1191.              expired immediately.
  1192.  
  1193.         2    If the router has a current (*,G), or (*,*,RP), route
  1194.              entry, and if the existing (Sp,G) entry has its
  1195.              RPT- bit flag set to 1, then this (Sp,G)RPT-bit entry
  1196.              is not deleted, and the Entry-timer is restarted, even
  1197.              if its outgoing interface list is null.
  1198.  
  1199.         3    If (*,G), or corresponding (*,*,RP), state exists, but
  1200.              there is no (Sp,G) entry, an (Sp,G)RPT-bit entry is
  1201.              created. The outgoing interface list is copied from the
  1202.              (*,G), or (*,*,RP), entry, with the interface, I, on
  1203.              which the prune was received, is deleted.  Packets from
  1204.              the pruned source, Sp, match on this state and are not
  1205.              forwarded toward the pruned receivers.
  1206.  
  1207.         4    If there exists a (Sp,G) entry, with or without the
  1208.              RPT-bit set, the oif-timer for I is expired, and the
  1209.              Entry-timer is restarted.
  1210.  
  1211.    3    For each address, Sp, in the prune list whose RPT-bit and
  1212.         WC-bit are both set:
  1213.  
  1214.         1    If there is an existing (*,G) entry, with Sp as the RP
  1215.              for G, the router lowers the entry's Oif-timer for I
  1216.              to its Oif-Deletion-Delay, allowing for other
  1217.              downstream routers on a multi-access LAN to override the
  1218.              prune. However, on point-to-point links, the oif-timer
  1219.              is expired immediately.
  1220.  
  1221.         2    If the corresponding (*,*,RP) state exists, but there
  1222.              is no (*,G) entry, a (*,G) entry is created. The
  1223.              outgoing interface list is copied from (*,*,RP) entry,
  1224.              with the interface, I, on which the prune was
  1225.              received, deleted.
  1226.  
  1227.         For any new (S,G), (*,G) or (*,*,RP) entry created by an
  1228.         incoming Join/Prune message, the SPT-bit is cleared (and if a
  1229.         Join/Prune-Suppression timer is used, it is left off.)
  1230.  
  1231.  
  1232.  
  1233.  
  1234. Estrin, et. al.               Experimental                     [Page 22]
  1235.  
  1236. RFC 2117                         PIM-SM                       June 1997
  1237.  
  1238.  
  1239.    If the entry has a Join/Prune-Suppression timer associated with it,
  1240.    and if the received Join/Prune does not indicate the router as its
  1241.    target, then the receiving router examines the join and prune lists
  1242.    to see if any addresses in the list `completely- match' existing
  1243.    (S,G), (*,G), or (*,*,RP) state for which the receiving router
  1244.    currently schedules Join/Prune messages. An element on the join or
  1245.    prune list `completely-matches' a route entry only if both the IP
  1246.    addresses and RPT-bit flag are the same. If the incoming Join/Prune
  1247.    message completely matches an existing (S,G), (*,G), or (*,*,RP)
  1248.    entry and the Join/Prune arrived on the iif for that entry, then the
  1249.    router compares the Holdtime included in the Join/Prune message, to
  1250.    its own [Join/Prune-Holdtime].  If its own [Join/Prune-Holdtime] is
  1251.    lower, the Join/Prune-Suppression-timer is started at the
  1252.    [Join/Prune-Suppression-Timeout]. If the [Join/Prune-Holdtime] is
  1253.    equal, the tie is resolved in favor of the Join/Prune Message
  1254.    originator that has the higher IP address. When the Join/Prune timer
  1255.    expires, the router triggers a Join/Prune message for the
  1256.    corresponding entry(ies).
  1257.  
  1258. 3.3 Register and Register-Stop
  1259.  
  1260.    When a source first starts sending to a group its packets are
  1261.    encapsulated in Register messages and sent to the RP. If the data
  1262.    rate warrants source-specific paths, the RP sets up source specific
  1263.    state and starts sending (S,G) Join/Prune messages toward the source,
  1264.    with S in the join list.
  1265.  
  1266. 3.3.1 Sending Registers and Receiving Register-Stops
  1267.  
  1268.    Register messages are sent as follows:
  1269.  
  1270.    1    When a DR receives a packet from a directly connected
  1271.         source, S
  1272.  
  1273.         1    If there is no corresponding (S,G) entry, and the
  1274.              router has RP-Set information, the DR creates one with
  1275.              the Register-Suppression-timer turned off and the RP
  1276.              address set according to the hash function mapping for
  1277.              the corresponding group. The oif list is copied from
  1278.              existing (*,G) or (*,*,RP) entries, if they exist. The
  1279.              iif of the (S,G) entry is always excluded from the oif
  1280.              list.
  1281.  
  1282.         2    If there is a (S,G) entry in existence, the DR  simply
  1283.              restarts the corresponding Entry-timer.
  1284.  
  1285.  
  1286.  
  1287.  
  1288.  
  1289.  
  1290. Estrin, et. al.               Experimental                     [Page 23]
  1291.  
  1292. RFC 2117                         PIM-SM                       June 1997
  1293.  
  1294.  
  1295.         When a PMBR (e.g., a router that connects the PIM-SM region to
  1296.         a dense mode region running DVMRP or PIM-DM) receives a packet
  1297.         from a source in the dense mode region,  the  router treats  the
  1298.         packet as if it were from a directly connected source. A
  1299.         separate document will describe  the  details  of
  1300.         interoperability.
  1301.  
  1302.    2    If the new or previously-existing (S,G) entry's Register-
  1303.         Suppression-timer is not running, the data packet is
  1304.         encapsulated in a Register message and unicast to the RP
  1305.         for that group. The data packet is also forwarded according
  1306.         to (S,G) state in the DR if the oif list is not null; since
  1307.         a receiver may join the SP-tree while the DR is still
  1308.         registering to the RP.
  1309.  
  1310.    3    If the (S,G) entry's Register-Suppression-timer is running,
  1311.         the data packet is not sent in a Register message, it is
  1312.         just forwarded according to the (S,G) oif list.
  1313.  
  1314.    When the DR receives a Register-Stop message, it restarts the
  1315.    Register-Suppression-timer in the corresponding (S,G) entry(ies) at
  1316.    [Register-Suppression-Timeout] seconds. If there is data to be
  1317.    registered, the DR may send a null Register (a Register message with
  1318.    a zero-length data portion in the inner IP packet) to the RP,
  1319.    [Probe-Time] seconds before the Register- Suppression-timer expires,
  1320.    to avoid sending occasional bursts of traffic to an RP unnecessarily.
  1321.  
  1322. 3.3.2 Receiving Register Messages and Sending Register-Stops
  1323.  
  1324.    When a router (i.e., the RP) receives a Register message, the router
  1325.    does the following:
  1326.  
  1327.    1    Decapsulates the data packet, and checks for a
  1328.         corresponding (S,G) entry.
  1329.  
  1330.         1    If a (S,G) entry with cleared (0) SPT bit exists, and
  1331.              the received Register does not have the Null-
  1332.              Register-Bit set to 1, the packet is forwarded; and
  1333.              the SPT bit is left cleared (0). If the SPT bit is 1,
  1334.              the packet is dropped, and Register-Stop messages are
  1335.              triggered.  Register-Stops should be rate-limited (in
  1336.              an implementation-specific manner) so that no more
  1337.              than a few are sent per round trip time. This prevents
  1338.              a high datarate stream of packets from triggering a
  1339.              large number of Register-Stop messages between the
  1340.              time that the first packet is received and the time
  1341.              when the source receives the first Register-Stop.
  1342.  
  1343.  
  1344.  
  1345.  
  1346. Estrin, et. al.               Experimental                     [Page 24]
  1347.  
  1348. RFC 2117                         PIM-SM                       June 1997
  1349.  
  1350.  
  1351.         2    If there is no (S,G) entry, but there is a (*,G)
  1352.              entry, and the received Register does not have the
  1353.              Null-Register-Bit set to 1, the packet is forwarded
  1354.              according to the (*,G) entry.
  1355.  
  1356.         3    If there is a (*,*,RP) entry but no (*,G) entry, and
  1357.              the Register received does not have the Null-
  1358.              Register-Bit set to 1, a (*,G) or (S,G) entry is
  1359.              created and the oif list is copied from the (*,*,RP)
  1360.              entry to the new entry.  The packet is forwarded
  1361.              according to the created entry.
  1362.  
  1363.         4    If there is no G or (*,*,RP) entry corresponding to G,
  1364.              the packet is dropped, and a Register-Stop is
  1365.              triggered.
  1366.  
  1367.         5    A "Border bit" bit is added to the Register message,
  1368.              to facilitate interoperability mechanisms. PMBRs set
  1369.              this bit when registering for external sources (see
  1370.              Section 2.7).  If the "Border bit" is set in the
  1371.              Register, the RP does the following:
  1372.  
  1373.              1    If there is no matching (S,G) state, but there
  1374.                   exists (*,G) or (*,*,RP) entry, the RP creates a
  1375.                   (S,G) entry, with a `PMBR' field.  This field
  1376.                   holds the source of the Register (i.e. the outer
  1377.                   IP address of the register packet).  The RP
  1378.                   triggers a (S,G) join towards the source of the
  1379.                   data packet, and clears the SPT bit for the (S,G)
  1380.                   entry.  If the received Register is not a `null
  1381.                   Register' the packet is forwarded according to
  1382.                   the created state. Else,
  1383.  
  1384.              2    If the `PMBR' field for the corresponding (S,G)
  1385.                   entry matches the source of the Register packet,
  1386.                   and the received Register is not a `null
  1387.                   Register', the decapsulated packet is forwarded
  1388.                   to the oif list of that entry. Else,
  1389.  
  1390.              3    If the `PMBR' field for the corresponding (S,G)
  1391.                   entry matches the source of the Register packet,
  1392.                   the decapsulated packet is forwarded to the oif
  1393.                   list of that entry, else
  1394.  
  1395.              4    The packet is dropped, and a Register-stop is
  1396.                   triggered towards the source of the Register.
  1397.  
  1398.  
  1399.  
  1400.  
  1401.  
  1402. Estrin, et. al.               Experimental                     [Page 25]
  1403.  
  1404. RFC 2117                         PIM-SM                       June 1997
  1405.  
  1406.  
  1407.         The (S,G) Entry-timer is restarted  by  Registers arriving from
  1408.         that source to that group.
  1409.  
  1410.    2    If the matching (S,G) or (*,G) state contains a null oif
  1411.         list, the RP unicasts a Register-Stop message to the source
  1412.         of the Register message; in the latter case, the source-
  1413.         address field, within the Register-Stop message, is set to
  1414.         the wildcard value (all 0's). This message is not processed
  1415.         by intermediate routers, hence no (S,G) state is
  1416.         constructed between the RP and the source.
  1417.  
  1418.    3    If the Register message arrival rate warrants it and there
  1419.         is no existing (S,G) entry, the RP sets up a (S,G) route
  1420.         entry with the outgoing interface list, excluding iif(S,G),
  1421.         copied from the (*,G) outgoing interface list, its SPT-bit
  1422.         is initialized to 0. If a (*,G) entry does not exist, but
  1423.         there exists a (*,*,RP) entry with the RP corresponding to
  1424.         G , the oif list for (S,G) is copied -excluding the iif-
  1425.         from that (*,*,RP) entry.
  1426.  
  1427.         A timer (Entry-timer) is set for the (S,G) entry and this
  1428.         timer is restarted by receipt of data packets for (S,G).
  1429.         The (S,G) entry causes the RP to send a Join/Prune message
  1430.         for the indicated group towards the source of the register
  1431.         message.
  1432.  
  1433.         If the (S,G) oif list becomes null, Join/Prune messages
  1434.         will not be sent towards the source, S.
  1435.  
  1436. 3.4 Multicast Data Packet Forwarding
  1437.  
  1438.    Processing a multicast data packet involves the following steps:
  1439.  
  1440.    1    Lookup route state based on a longest match of the source
  1441.         address, and an exact match of the destination address in
  1442.         the data packet. If neither S, nor G, find a longest match
  1443.         entry, and the RP for the packet's destination group
  1444.         address has a corresponding (*,*,RP) entry, then the
  1445.         longest match does not require an exact match on the
  1446.         destination group address. In summary, the longest match is
  1447.         performed in the following order: (1) (S,G), (2) (*,G). If
  1448.         neither is matched, then a lookup is performed on (*,*,RP)
  1449.         entries.
  1450.  
  1451.    2    If the packet arrived on the interface found in the
  1452.         matching-entry's iif field, and the oif list is not
  1453.         null:
  1454.  
  1455.  
  1456.  
  1457.  
  1458. Estrin, et. al.               Experimental                     [Page 26]
  1459.  
  1460. RFC 2117                         PIM-SM                       June 1997
  1461.  
  1462.  
  1463.         1    Forward the packet to the oif list for that entry
  1464.              and restart the Entry-timer if the matching entry is
  1465.              (S,G).  Optionally, the (S,G) Entry-timer may be
  1466.              restarted by periodic checking of the matching packet
  1467.              count.
  1468.  
  1469.         2    If the entry is a (S,G) entry with a cleared SPT-bit,
  1470.              and a (*,G) or associated (*,*,RP) also exists whose
  1471.              incoming interface is different than that for (S,G),
  1472.              set the SPT-bit for the (S,G) entry and trigger an
  1473.              (S,G) RPT-bit prune towards the RP.
  1474.  
  1475.         3    If the source of the packet is a directly-connected
  1476.              host and the router is the DR on the receiving
  1477.              interface, check the Register-Suppression-timer
  1478.              associated with the (S,G) entry. If it is not running,
  1479.              then the router encapsulates the data packet in a
  1480.              register message and sends it to the RP.
  1481.  
  1482.         This covers the common case of a packet arriving on the RPF
  1483.         interface to the source or RP and being forwarded to all
  1484.         joined branches. It also detects when packets arrive on the
  1485.         SP-tree, and triggers their pruning from the RP-tree. If it
  1486.         is the DR for the source, it sends data packets
  1487.         encapsulated in Registers to the RPs.
  1488.  
  1489.    3    If the packet matches to an entry but did not arrive on the
  1490.         interface found in the entry's iif field, check the
  1491.         SPT-bit of the entry. If the SPT-bit is set, drop the
  1492.         packet.  If the SPT-bit is cleared, then lookup the (*,G),
  1493.         or (*,*,RP), entry for G. If the packet arrived on the
  1494.         iif found in (*,G), or the corresponding (*,*,RP),
  1495.         forward the packet to the oif list of the matching
  1496.         entry. This covers the case when a data packet matches on a
  1497.         (S,G) entry for which the SP-tree has not yet been
  1498.         completely established upstream.
  1499.  
  1500.    4    If the packet does not match any entry, but the source of
  1501.         the data packet is a local, directly-connected host, and
  1502.         the router is the DR on a multi-access LAN and has RP-Set
  1503.         information, the DR uses the hash function to determine the
  1504.         RP associated with the destination group, G. The DR creates
  1505.         a (S,G) entry, with the Register-Suppression-timer not
  1506.         running, encapsulates the data packet in a Register message
  1507.         and unicasts it to the RP.
  1508.  
  1509.    5    If the packet does not match to any entry, and it is not a
  1510.         local host or the router is not the DR, drop the packet.
  1511.  
  1512.  
  1513.  
  1514. Estrin, et. al.               Experimental                     [Page 27]
  1515.  
  1516. RFC 2117                         PIM-SM                       June 1997
  1517.  
  1518.  
  1519. 3.4.1 Data triggered switch to shortest path tree (SP-tree)
  1520.  
  1521.    Different criteria can be applied to trigger switching over from the
  1522.    RP-based shared tree to source-specific, shortest path trees.
  1523.  
  1524.    One proposed example is to do so based on data rate.  For example,
  1525.    when a (*,G), or corresponding (*,*,RP), entry is created, a data rate
  1526.    counter may be initiated at the last-hop routers.  The counter is
  1527.    incremented with every data packet received for directly connected
  1528.    members of an SM group, if the longest match is (*,G) or (*,*,RP). If
  1529.    and when the data rate for the group exceeds a certain configured
  1530.    threshold (t1), the router initiates `source-specific' data rate
  1531.    counters for the following data packets. Then, each counter for a
  1532.    source, is incremented when packets matching on (*,G), or (*,*,RP),
  1533.    are received from that source. If the data rate from the particular
  1534.    source exceeds a configured threshold (t2), a (S,G) entry is created
  1535.    and a Join/Prune message is sent towards the source.  If the RPF
  1536.    interface for (S,G) is not the same as that for (*,G) -or (*,*,RP),
  1537.    then the SPT-bit is cleared in the (S,G) entry.
  1538.  
  1539.    Other configured rules may be enforced to cause or prevent
  1540.    establishment of (S,G) state.
  1541.  
  1542. 3.5 Assert
  1543.  
  1544.    Asserts are used to resolve which of the parallel routers connected to
  1545.    a multi-access LAN is responsible for forwarding packets onto the LAN.
  1546.  
  1547. 3.5.1 Sending Asserts
  1548.  
  1549.    The following Assert rules are provided when a multicast packet is
  1550.    received on an outgoing multi-access interface "I" of an existing
  1551.    (S,G) entry:
  1552.  
  1553.    1    Do unicast routing table lookup on source IP address from
  1554.         data packet, and send assert on interface "I" for source
  1555.         IP address in data packet; include metric preference of
  1556.         routing protocol and metric from routing table lookup.
  1557.  
  1558.    2    If route is not found, use metric preference of 0x7fffffff
  1559.         and metric 0xffffffff.
  1560.  
  1561.    When an assert is sent for a (*,G) entry, the first bit in the
  1562.    metric preference (the RPT-bit) is set to 1, indicating the data
  1563.    packet is routed down the RP-tree.
  1564.  
  1565.    Asserts should be rate-limited in an implementation-specific
  1566.    manner.
  1567.  
  1568.  
  1569.  
  1570. Estrin, et. al.               Experimental                     [Page 28]
  1571.  
  1572. RFC 2117                         PIM-SM                       June 1997
  1573.  
  1574.  
  1575. 3.5.2 Receiving Asserts
  1576.  
  1577.    When an Assert is received the router performs a longest match on the
  1578.    source and group address in the Assert message. The router checks the
  1579.    first bit of the metric preference (RPT-bit).
  1580.  
  1581.    1    If the RPT-bit is set, the router first does a match on
  1582.         (*,G), or (*,*,RP), entries; if no matching entry is found,
  1583.         it ignores the Assert.
  1584.  
  1585.    2    If the RPT-bit is not set in the Assert, the router first
  1586.         does a match on (S,G) entries; if no matching entry is
  1587.         found, the router matches (*,G) or (*,*,RP) entries.
  1588.  
  1589.    3.5.2.1 Receiving Asserts on an entry's outgoing interface
  1590.  
  1591.    If the interface that received the Assert message is in the oif list
  1592.    of the matched entry, then this Assert is processed by this router as
  1593.    follows:
  1594.  
  1595.    1    If the Assert's RPT-bit is set and the matching entry is
  1596.         (*,*,RP), the router creates a (*,G) entry. If the Assert's
  1597.         RPT-bit is cleared and the matching entry is (*,G), or
  1598.         (*,*,RP), the router creates a (S,G)RPT-bit entry.
  1599.         Otherwise, no new entry is created in response to the
  1600.         Assert.
  1601.  
  1602.    2    The router then compares the metric values received in the
  1603.         Assert with the metric values associated with the matched
  1604.         entry. The RPT-bit and metric preference (in that order)
  1605.         are treated as the high-order part of an Assert metric
  1606.         comparison. If the value in the Assert is less than the
  1607.         router's value (with ties broken by the IP address, where
  1608.         higher IP address wins), delete the interface from the
  1609.         entry.  When the deletion occurs for a (*,G) or (*,*,RP)
  1610.         entry , the interface is also deleted from any associated
  1611.         (S,G)RPT-bit or (*,G) entries, respectively. The Entry-
  1612.         timer for the affected entries is restarted.
  1613.  
  1614.    3    If the router has won the election the router keeps the
  1615.         interface in its outgoing interface list. It acts as the
  1616.         forwarder for the LAN.
  1617.  
  1618.    The winning router sends an Assert message containing its own metric
  1619.    to that outgoing interface. This will cause other routers on the LAN
  1620.    to prune that interface from their route entries. The winning router
  1621.    sets the RPT-bit in the Assert message if a (*,G) or (S,G)RPT-bit
  1622.    entry was matched.
  1623.  
  1624.  
  1625.  
  1626. Estrin, et. al.               Experimental                     [Page 29]
  1627.  
  1628. RFC 2117                         PIM-SM                       June 1997
  1629.  
  1630.  
  1631.    3.5.2.2 Receiving Asserts on an entry's incoming interface
  1632.  
  1633.    If the Assert arrived on the incoming interface of an existing (S,G),
  1634.    (*,G), or (*,*,RP) entry, the Assert is processed as follows.  If the
  1635.    Assert message does not match the entry, exactly, it is ignored; i.e,
  1636.    longest-match is not used in this case. If the Assert message does
  1637.    match exactly, then:
  1638.  
  1639.    1    Downstream routers will select the upstream router with the
  1640.         smallest metric preference and metric as their RPF
  1641.         neighbor. If two metrics are the same, the highest IP
  1642.         address is chosen to break the tie. This is important so
  1643.         that downstream routers send subsequent Joins/Prunes (in
  1644.         SM) to the correct neighbor. An Assert-timer is initiated
  1645.         when changing the RPF neighbor to the Assert winner.  When
  1646.         the timer expires, the router resets its RPF neighbor
  1647.         according to its unicast routing tables to capture network
  1648.         dynamics and router failures.
  1649.  
  1650.    2    If the downstream routers have downstream members, and if
  1651.         the Assert caused the RPF neighbor to change, the
  1652.         downstream routers must trigger a Join/Prune message to
  1653.         inform the upstream router that packets are to be forwarded
  1654.         on the multi-access network.
  1655.  
  1656. 3.6 Candidate-RP-Advertisements and Bootstrap messages
  1657.  
  1658.    Candidate-RP-Advertisements (C-RP-Advs) are periodic PIM messages
  1659.    unicast to the BSR by those routers that are configured as
  1660.    Candidate-RPs (C-RPs).
  1661.  
  1662.    Bootstrap messages are periodic PIM messages originated by the
  1663.    Bootstrap router (BSR) within a domain, and forwarded hop-by-hop to
  1664.    distribute the current RP-set to all routers in that domain.
  1665.  
  1666.    The Bootstrap messages also support a simple mechanism by which the
  1667.    Candidate BSR (C-BSR) with the highest BSR-priority and IP address
  1668.    (referred to as the preferred BSR) is elected as the BSR for the
  1669.    domain.  We recommend that each router configured as a C-RP also be
  1670.    configured as a C-BSR. Sections 3.6.2 and 3.6.3 describe the combined
  1671.    function of Bootstrap messages as the vehicle for BSR election and
  1672.    RP-Set distribution.
  1673.  
  1674.    A Finite State Machine description of the BSR election and RP- Set
  1675.    distribution mechanisms is included in Appendix II.
  1676.  
  1677.  
  1678.  
  1679.  
  1680.  
  1681.  
  1682. Estrin, et. al.               Experimental                     [Page 30]
  1683.  
  1684. RFC 2117                         PIM-SM                       June 1997
  1685.  
  1686.  
  1687. 3.6.1 Sending Candidate-RP-Advertisements
  1688.  
  1689.    C-RPs periodically unicast C-RP-Advs to the BSR for that domain.  The
  1690.    interval for sending these messages is subject to local configuration
  1691.    at the C-RP.
  1692.  
  1693.    Candidate-RP-Advertisements carry group address and group mask
  1694.    fields.  This enables the advertising router to limit the
  1695.    advertisement to certain prefixes or scopes of groups.  The
  1696.    advertising router may enforce this scope acceptance when receiving
  1697.    Registers or Join/Prune messages.  C-RPs should send C-RP-Adv
  1698.    messages with the Authoritative bit cleared.
  1699.  
  1700. 3.6.2 Receiving C-RP-Advs and Originating Bootstrap
  1701.  
  1702.    Upon receiving a C-RP-Adv, a router does the following:
  1703.  
  1704.    1    If the router is not the elected BSR, it ignores the
  1705.         message, else
  1706.  
  1707.    2    The BSR adds the RP address to its local pool of candidate
  1708.         RPs, according to the associated group prefix(es) in the
  1709.         C-RP-Adv message. The Holdtime in the C-RP-Adv message is
  1710.         also stored with the corresponding RP, to be included later
  1711.         in the Bootstrap message. The BSR may apply a local
  1712.         policy to limit the number of Candidate RPs included
  1713.         in the Bootstrap message.  The BSR may override the prefix
  1714.         indicated in a C-RP-Adv unless the Authoritative bit in the
  1715.         C-RP-Adv is set.
  1716.  
  1717.    The BSR keeps an RP-timer per RP in its local RP-set.  The RP- timer
  1718.    is initialized to the Holdtime in the RP's C-RP-Adv. When the timer
  1719.    expires, the corresponding RP is removed from the RP- set.  The RP-
  1720.    timer is restarted by the C-RP-Advs from the corresponding RP.
  1721.  
  1722.    The BSR also uses its Bootstrap-timer to periodically send Bootstrap
  1723.    messages.  In particular, when the Bootstrap-timer expires, the BSR
  1724.    originates an Bootstrap message on each of its PIM interfaces.  The
  1725.    message is sent with a TTL of 1 to the `ALL-PIM-ROUTERS' group. In
  1726.    steady state, the BSR originates Bootstrap messages periodically. At
  1727.    startup, the Bootstrap-timer is initialized to [Bootstrap-Timeout],
  1728.    causing the first Bootstrap message to be originated only when and if
  1729.    the timer expires. For timer details, see Section 3.6.3. A DR
  1730.    unicasts a Bootstrap message to each new PIM neighbor, i.e., after
  1731.    the DR receives the neighbor's Hello message (it does so even if the
  1732.    new neighbor becomes the DR).
  1733.  
  1734.  
  1735.  
  1736.  
  1737.  
  1738. Estrin, et. al.               Experimental                     [Page 31]
  1739.  
  1740. RFC 2117                         PIM-SM                       June 1997
  1741.  
  1742.  
  1743.    The Bootstrap message is subdivided into sets of {group- prefix,RP-
  1744.    Count,RP-addresses}.  For each RP-address, the corresponding Holdtime
  1745.    is included in the "RP-Holdtime" field.  The format of the Bootstrap
  1746.    message allows `semantic fragmentation', if the length of the
  1747.    original Bootstrap message exceeds the packet maximum boundaries (see
  1748.    Section 4). However, we recommend against configuring a large number
  1749.    of routers as C-RPs, to reduce the semantic fragmentation required.
  1750.  
  1751. 3.6.3 Receiving and Forwarding Bootstrap
  1752.  
  1753.    Each router keeps a Bootstrap-timer, initialized to [Bootstrap-
  1754.    Timeout] at startup.
  1755.  
  1756.    When a router receives Bootstrap message sent to `ALL-PIM- ROUTERS'
  1757.    group, it performs the following:
  1758.  
  1759.    1    If the message was not sent by the RPF neighbor towards the
  1760.         BSR address included, the message is dropped. Else
  1761.  
  1762.    2    If the included BSR is not preferred over, and not equal
  1763.         to, the currently active BSR:
  1764.  
  1765.  
  1766.         1    If the Bootstrap-timer has not yet expired, or if the
  1767.              receiving router is a C-BSR, then the Bootstrap
  1768.              message is dropped. Else
  1769.  
  1770.         2    If the Bootstrap-timer has expired and the receiving
  1771.              router is not a C-BSR, the receiving router stores the
  1772.              RP-Set and BSR address and priority found in the
  1773.              message, and restarts the timer by setting it to
  1774.              [Bootstrap-Timeout]. The Bootstrap message is then
  1775.              forwarded out all PIM interfaces, excluding the one
  1776.              over which the message arrived, to `ALL-PIM-ROUTERS'
  1777.              group, with a TTL of 1.
  1778.  
  1779.         3    If the Bootstrap message includes a BSR address that is
  1780.              preferred over, or equal to, the currently active BSR, the
  1781.              router restarts its Bootstrap-timer at [Bootstrap-Timeout]
  1782.              seconds. and stores the BSR address and RP-Set information.
  1783.  
  1784.              The Bootstrap message is then forwarded out all PIM
  1785.              interfaces, excluding the one over which the message
  1786.              arrived, to `ALL-PIM-ROUTERS' group, with a TTL of 1.
  1787.  
  1788.  
  1789.  
  1790.  
  1791.  
  1792.  
  1793.  
  1794. Estrin, et. al.               Experimental                     [Page 32]
  1795.  
  1796. RFC 2117                         PIM-SM                       June 1997
  1797.  
  1798.  
  1799.         4    If the receiving router has no current RP set information
  1800.              and the Bootstrap was unicast to it from a directly
  1801.              connected neighbor, the router stores the information as
  1802.              its new RP-set.  This covers the startup condition when a
  1803.              newly booted router obtains the RP-Set and BSR address from
  1804.              its DR.
  1805.  
  1806.    When a router receives a new RP-Set, it checks if each of the RPs
  1807.    referred to by existing state (i.e., by (*,G), (*,*,RP), or
  1808.    (S,G)RPT-bit entries) is in the new RP-Set. If an RP is not in the new
  1809.    RP-set, that RP is considered unreachable and the hash algorithm (see
  1810.    below) is re-performed for each group with locally active state that
  1811.    previously hashed to that RP. This will cause those groups to be
  1812.    distributed among the remaining RPs. When the new RP-Set contains a
  1813.    new RP, the value of the new RP is calculated for each group covered
  1814.    by that C-RP's Group- prefix.  Any group for which the new RP's value
  1815.    is greater than the previously active RP's value is switched over to
  1816.    the new RP.
  1817.  
  1818. 3.7 Hash Function
  1819.  
  1820.    The hash function is used by all routers within a domain, to map a
  1821.    group to one of the C-RPs from the RP-Set. For a particular group, G,
  1822.    the hash function uses only those C-RPs whose Group- prefix covers G.
  1823.    The algorithm takes as input the group address, and the addresses of
  1824.    the Candidate RPs, and gives as output one RP address to be used.
  1825.  
  1826.    The protocol requires that all routers hash to the same RP within a
  1827.    domain (except for transients). The following hash function must be
  1828.    used in each router:
  1829.  
  1830.  
  1831.    1    For each RP address C(i) in the RP-Set, whose Group-prefix
  1832.         covers G, compute a value:
  1833.  
  1834.    Value(G,M,C(i))=
  1835.    (1103515245 * ((1103515245 * (G&M)+12345) XOR C(i)) + 12345) mod 2^31
  1836.  
  1837.          where M is a hash-mask included in Bootstrap messages.
  1838.          This hash-mask allows a small number of consecutive groups
  1839.          (e.g., 4) to always hash to the same RP.  For instance,
  1840.          hierarchically-encoded data can be sent on consecutive
  1841.          group addresses to get the same delay and fate-sharing
  1842.          characteristics.
  1843.  
  1844.    2    The candidate with the highest resulting value is then
  1845.         chosen as the RP for that group, and its identity and hash
  1846.         value are stored with the entry created.
  1847.  
  1848.  
  1849.  
  1850. Estrin, et. al.               Experimental                     [Page 33]
  1851.  
  1852. RFC 2117                         PIM-SM                       June 1997
  1853.  
  1854.  
  1855.         Ties between C-RPs having the same hash value, are broken
  1856.         in advantage of the highest address.
  1857.  
  1858.    The hash function algorithm is invoked by a DR, upon reception of a
  1859.    packet, or IGMP membership indication, for a group, for which the DR
  1860.    has no entry. It is invoked by any router that has (*,*,RP) state when
  1861.    a packet is received for which there is no corresponding (S,G) or
  1862.    (*,G) entry.  Furthermore, the hash function is invoked by all routers
  1863.    upon receiving a (*,G) or (*,*,RP) Join/Prune message.
  1864.  
  1865. 3.8 Processing Timer Events
  1866.  
  1867.    In this subsection, we enumerate all timers that have been discussed
  1868.    or implied. Since some critical timer events are not associated with
  1869.    the receipt or sending of messages, they are not fully covered by
  1870.    earlier subsections.
  1871.  
  1872.    Timers are implemented in an implementation-specific manner. For
  1873.    example, a timer may count up or down, or may simply expire at a
  1874.    specific time. Setting a timer to a value T means that it will expire
  1875.    after T seconds.
  1876.  
  1877. 3.8.1 Timers related to tree maintenance
  1878.  
  1879.    Each (S,G), (*,G), and (*,*,RP) route entry has multiple timers
  1880.    associated with it: one for each interface in the outgoing interface
  1881.    list, one for the multicast routing entry itself, and one optional
  1882.    Join/Prune-Suppression-Timer. Each (S,G) and (*,G) entry also has an
  1883.    Assert-timer and a Random-Delay-Join-Timer for use with Asserts.  In
  1884.    addition, DR's have a Register- Suppression-timer for each (S,G) entry
  1885.    and every router has a single Join/Prune-timer. (A router may
  1886.    optionally keep separate Join/Prune-timers for different interfaces or
  1887.    route entries if different Join/Prune periods are desired.)
  1888.  
  1889.    *    [Join/Prune-Timer] This timer is used for periodically
  1890.         sending aggregate Join/Prune messages.  To avoid
  1891.         synchronization among routers booting simultaneously, it is
  1892.         initially set to a random value between 1 and [Join/Prune-
  1893.         Period].  When it expires, the timer is immediately
  1894.         restarted to [Join/Prune-Period]. A Join/Prune message is
  1895.         then sent out each interface.  This timer should not be
  1896.         restarted by other events.
  1897.  
  1898.    *    [Join/Prune-Suppression-Timer (kept per route entry)] A
  1899.         route entry's (optional) Join/Prune-Suppression-Timer may
  1900.         be used to suppress duplicate joins from multiple
  1901.         downstream routers on the same LAN. When a Join message is
  1902.         received from a neighbor on the entry's incoming interface
  1903.  
  1904.  
  1905.  
  1906. Estrin, et. al.               Experimental                     [Page 34]
  1907.  
  1908. RFC 2117                         PIM-SM                       June 1997
  1909.  
  1910.  
  1911.         in which the included Holdtime is higher than the router's
  1912.         own [Join/Prune-Holdtime] (with ties broken by higher IP
  1913.         address), the timer is set to [Join/Prune-Suppression-
  1914.         Timeout], with some random jitter introduced to avoid
  1915.         synchronization of triggered Join/Prune messages on
  1916.         expiration. (The random timeout value must be < 1.5 *
  1917.         [Join/Prune-Period] to prevent losing data after 2 dropped
  1918.         Join/Prunes.)  The timer is restarted every time a
  1919.         subsequent Join/Prune message (with higher Holdtime/IP
  1920.         address) for the entry is received on its incoming
  1921.         interface.  While the timer is running, Join/Prune messages
  1922.         for the entry are not sent.  This timer is idle (not
  1923.         running) for point-to-point links.
  1924.  
  1925.    *    [Oif-Timer (kept per oif for each route entry)] A timer for
  1926.         each oif of a route entry is used to time out that oif.
  1927.         Because some of the outgoing interfaces in an (S,G) entry
  1928.         are copied from the (*,G) outgoing interface list, they may
  1929.         not have explicit (S,G) join messages from some of the
  1930.         downstream routers (i.e., where members are joining to the
  1931.         (*,G) tree only). Thus, when an Oif-timer is restarted in a
  1932.         (*,G) entry, the Oif-timer is restarted for that interface
  1933.         in each existing (S,G) entry whose oif list contains that
  1934.         interface. The same rule applies to (*,G) and (S,G) entries
  1935.         when restarting an Oif-timer on a (*,*,RP) entry.
  1936.  
  1937.         The following table shows its usage when first adding the
  1938.         oif to the entry's oiflist, when it should be restarted
  1939.         (unless it is already higher), and when it should be
  1940.         decreased (unless it is already lower).
  1941.  
  1942.  
  1943.  
  1944.  
  1945.  
  1946.  
  1947.  
  1948.  
  1949.  
  1950.  
  1951.  
  1952.  
  1953.  
  1954.  
  1955.  
  1956.  
  1957.  
  1958.  
  1959.  
  1960.  
  1961.  
  1962. Estrin, et. al.               Experimental                     [Page 35]
  1963.  
  1964. RFC 2117                         PIM-SM                       June 1997
  1965.  
  1966.  
  1967.    Set to                   | When                         | Applies  to
  1968.    -------------------------|------------------------------|------------
  1969.    included Holdtime        | adding oif off Join/Prune    | (S,G) (*,G)
  1970.                             |                              | (*,*,RP)
  1971.  
  1972.  
  1973.  
  1974.    Increased (only) to      | When                         |  Applies to
  1975.    -------------------------|------------------------------|------------
  1976.    included  Holdtime       | received Join/Prune          | (S,G) (*,G)
  1977.                             |                              | (*,*,RP)
  1978.                             |                              |
  1979.    Value of (*,*,RP)        | (*,*,RP) oif-timer restarted | (S,G) (*,G)
  1980.       oif-timer             |                              |
  1981.                             |                              |
  1982.    Value of (*,G)           | (*,G) oif-timer restarted    | (S,G)
  1983.       oif-timer             |                              |
  1984.  
  1985.  
  1986.    Decreased (only) to      |  When                        | Applies  to
  1987.    -------------------------|------------------------------|------------
  1988.    Oif-Deletion-Delay       | prune received               | (S,G) (*,G)
  1989.  
  1990.  
  1991.         When the timer expires, the oif is removed from the oiflist
  1992.         if there are no directly-connected members. When deleted,
  1993.         the oif is also removed in any associated (S,G) or (*,G)
  1994.         entries.
  1995.  
  1996.    *    [Entry-Timer (kept per route entry)] A timer for each route
  1997.         entry is used to time out that entry. The following table
  1998.         summarizes its usage when first adding the oif to the
  1999.         entry's oiflist, and when it should be restarted (unless it
  2000.         is already higher).
  2001.  
  2002.  
  2003.  
  2004.  
  2005.  
  2006.  
  2007.  
  2008.  
  2009.  
  2010.  
  2011.  
  2012.  
  2013.  
  2014.  
  2015.  
  2016.  
  2017.  
  2018. Estrin, et. al.               Experimental                     [Page 36]
  2019.  
  2020. RFC 2117                         PIM-SM                       June 1997
  2021.  
  2022.  
  2023.    Set to                |  When                    | Applies to
  2024.    ----------------------|--------------------------|------------
  2025.    [Data- Timeout]       | created off data packet  | (S,G)
  2026.                          |                          |
  2027.    included Holdtime     | created off Join/Prune   | (S,G) (*,G)
  2028.    (*,*,RP)
  2029.  
  2030.  
  2031.    Increased  (only)  to |  When                    | Applies to
  2032.    ----------------------|--------------------------|------------
  2033.    [Data-Timeout]        | receiving  data  packets | (S,G)no RPT-bit
  2034.                          |                          |
  2035.    Value of oif-timer    | any oif-timer restarted  | (S,G)RPT-bit (*,G)
  2036.                          |                          | (*,*,RP)
  2037.                          |                          |
  2038.    [Assert-Timeout]      | assert received          | (S,G)RPT-bit
  2039.                          |                          | (*,G)w/null oif
  2040.  
  2041.  
  2042.         When the timer expires, the route entry is deleted; if the
  2043.         entry is a (*,G) or (*,*,RP) entry, all associated
  2044.         (S,G)RPT-bit entries are also deleted.
  2045.  
  2046.    *    [Register-Suppression-Timer (kept per (S,G) route entry)]
  2047.         An (S,G) route entry's Register-Suppression-Timer is used
  2048.         to suppress registers when the RP is receiving data packets
  2049.         natively.  When a Register-Stop message for the entry is
  2050.         received from the RP, the timer is set to a random value in
  2051.         the range 0.5 * [Register-Suppression-Timeout] to 1.5 *
  2052.         [Register-Suppression-Timeout]. While the timer is running,
  2053.         Registers for that entry will be suppressed.  If null
  2054.         registers are used, a null register is sent [Probe-Time]
  2055.         seconds before the timer expires.
  2056.  
  2057.    *    [Assert-Timer (per (S,G) or (*,G) route entry)] The
  2058.         Assert-Timer for an (S,G) or (*,G) route entry is used for
  2059.         timing out Asserts received. When an Assert is received and
  2060.         the RPF neighbor is changed to the Assert winner, the
  2061.         Assert-Timer is set to [Assert-Timeout], and is restarted
  2062.         to this value every time a subsequent Assert for the entry
  2063.         is received on its incoming interface.  When the timer
  2064.         expires, the router resets its RPF neighbor according to
  2065.         its unicast routing table.
  2066.  
  2067.    *    [Random-Delay-Join-Timer (per (S,G) or (*,G) route entry)]
  2068.         The Random-Delay-Join-Timer for an (S,G) or (*,G) route
  2069.         entry is used to prevent synchronization among downstream
  2070.         routers on a LAN when their RPF neighbor changes. When the
  2071.  
  2072.  
  2073.  
  2074. Estrin, et. al.               Experimental                     [Page 37]
  2075.  
  2076. RFC 2117                         PIM-SM                       June 1997
  2077.  
  2078.  
  2079.         RPF neighbor changes, this timer is set to a random value
  2080.         between 0 and [Random-Delay-Join-Timeout] seconds. When the
  2081.         timer expires, a triggered Join/Prune message is sent for
  2082.         the entry unless its Join/Prune-Suppression-Timer is
  2083.         running.
  2084.  
  2085. 3.8.2 Timers relating to neighbor discovery
  2086.  
  2087.    *    [Hello-Timer] This timer is used to periodically send Hello
  2088.         messages.  To avoid synchronization among routers booting
  2089.         simultaneously, it is initially set to a random value
  2090.         between 1 and [Hello-Period]. When it expires, the timer is
  2091.         immediately restarted to [Hello-Period]. A Hello message is
  2092.         then sent out each interface.  This timer should not be
  2093.         restarted by other events.
  2094.  
  2095.    *    [Neighbor-Timer (kept per neighbor)] A Neighbor-Timer for
  2096.         each neighbor is used to time out the neighbor state. When
  2097.         a Hello message is received from a new neighbor, the timer
  2098.         is initially set to the Holdtime included in the Hello
  2099.         message (which is equal to the neighbor's value of [Hello-
  2100.         Holdtime]).  Every time a subsequent Hello is received from
  2101.         that neighbor, the timer is restarted to the Holdtime in
  2102.         the Hello.  When the timer expires, the neighbor state is
  2103.         removed.
  2104.  
  2105. 3.8.3 Timers relating to RP information
  2106.  
  2107.    *    [C-RP-Adv-Timer (C-RP's only)] Routers configured as
  2108.         candidate RP's use this timer to periodically send C-RP-Adv
  2109.         messages. To avoid synchronization among routers booting
  2110.         simultaneously, the timer is initially set to a random
  2111.         value between 1 and [C-RP-Adv-Period]. When it expires, the
  2112.         timer is immediately restarted to [C-RP-Adv-Period]. A C-
  2113.         RP-Adv message is then sent to the elected BSR. This timer
  2114.         should not be restarted by other events.
  2115.  
  2116.    *    [RP-Timer (BSR only, kept per RP in RP-Set)] The BSR uses a
  2117.         timer per RP in the RP-Set to monitor liveness. When a C-RP
  2118.         is added to the RP-Set, its timer is set to the Holdtime
  2119.         included in the C-RP-Adv message from that C-RP (which is
  2120.         equal to the C-RP's value of [RP-Holdtime]). Every time a
  2121.         subsequent C-RP-Adv is received from that RP, its timer is
  2122.         restarted to the Holdtime in the C-RP-Adv. When the timer
  2123.         expires, the RP is removed from the RP-Set included in
  2124.         Bootstrap messages.
  2125.  
  2126.  
  2127.  
  2128.  
  2129.  
  2130. Estrin, et. al.               Experimental                     [Page 38]
  2131.  
  2132. RFC 2117                         PIM-SM                       June 1997
  2133.  
  2134.  
  2135.    *    [Bootstrap-Timer] This timer is used by the BSR to
  2136.         periodically originate Bootstrap messages, and by other
  2137.         routers to time out the BSR (see 3.6.3).  This timer is
  2138.         initially set to [Bootstrap-Timeout].  A C-BSR restarts
  2139.         this timer to [Bootstrap-Timeout] upon receiving a Bootstrap
  2140.         message from a preferred router, and originates an Bootstrap
  2141.         message and restarts the timer to [Bootstrap-Period] when it
  2142.         expires.  Routers not configured as C-BSR's restart this
  2143.         timer to [Bootstrap-Timeout] upon receiving a Bootstrap
  2144.         message from the elected or a more preferred BSR, and ignore
  2145.         Bootstrap messages from non-preferred C-BSRs while it is
  2146.         running.
  2147.  
  2148. 3.8.4 Default timer values
  2149.  
  2150.    Most of the default timeout values for state information are 3.5
  2151.    times the refresh period. For example, Hellos refresh Neighbor state
  2152.    and the default Hello-timer period is 30 seconds, so a default
  2153.    Neighbor-timer duration of 105 seconds is included in the Holdtime
  2154.    field of the Hellos.  In order to improve convergence, however, the
  2155.    default timeout value for information related to RP liveness and
  2156.    Bootstrap messages is 2.5 times the refresh period.
  2157.  
  2158.    In this version of the spec, we suggest particular numerical timer
  2159.    settings.  A future version of the specification will specify a
  2160.    mechanism for timer values to be scaled based upon observed network
  2161.    parameters.
  2162.  
  2163.    *    [Join/Prune-Period] This is the interval between
  2164.         sending Join/Prune messages. {Default: 60 seconds.} This
  2165.         value may be set to take into account such things as the
  2166.         configured bandwidth and expected average number of
  2167.         multicast route entries for the attached network or link
  2168.         (e.g., the period would be longer for lower-speed links, or
  2169.         for routers in the center of the network that expect to
  2170.         have a larger number of entries ). In addition, a router
  2171.         could modify this value (and corresponding Join/Prune-
  2172.         Holdtime value) if the number of route entries changes
  2173.         significantly (e.g., by an order of magnitude).  For
  2174.         example, given a default minimum Join/Prune-Period value,
  2175.         if the number of route entries with a particular iif
  2176.         increases from N to N*100, the router could increase its
  2177.         Join/Prune-Period (and Join/Prune-Holdtime), for that
  2178.         interface, by a factor of 10; and if/when the number of
  2179.         entries decreases back to N, the Join/Prune-Period (and
  2180.         Join/Prune-Holdtime) could be decreased to its previous
  2181.         value. If the Join/Prune-Period is modified, these changes
  2182.         should be made relatively infrequently and the router
  2183.  
  2184.  
  2185.  
  2186. Estrin, et. al.               Experimental                     [Page 39]
  2187.  
  2188. RFC 2117                         PIM-SM                       June 1997
  2189.  
  2190.  
  2191.         should continue to refresh at its previous Join/Prune-
  2192.         Period for at least Join/Prune-Holdtime, in order to allow
  2193.         the upstream router to adapt.
  2194.  
  2195.    *    [Join-Prune Holdtime] This is the Holdtime specified in
  2196.         Join/Prune messages, and is used to time out oifs. This
  2197.         should be set to 3.5 * [Join/Prune-Period]. {Default: 210
  2198.         seconds.}
  2199.  
  2200.    *    [Join/Prune-Suppression-Timeout] This is the mean
  2201.         interval between receiving a Join/Prune with a higher
  2202.         Holdtime (with ties broken by higher IP addres) and
  2203.         allowing duplicate Join/Prunes to be sent again. This
  2204.         should be set to approximately 1.25 * [Join/Prune-Period].
  2205.         {Default: 75 seconds. }
  2206.  
  2207.    *    [Data-Timeout] This is the time after which (S,G) state
  2208.         for a silent source will be deleted.  {Default: 210
  2209.         seconds.}
  2210.  
  2211.    *    [Register-Suppression-Timeout] This is the mean
  2212.         interval between receiving a Register-Stop and allowing
  2213.         Registers to be sent again.  A lower value means more
  2214.         frequent register bursts at RP, while a higher value means
  2215.         longer join latency for new receivers.  {Default: 60
  2216.         seconds.} (Note that if null Registers are sent [Probe-
  2217.         Time] seconds before the timeout, register bursts are
  2218.         prevents, and [Register-Suppression-Timeout] may be lowered
  2219.         to decrease join latency.)
  2220.  
  2221.    *    [Probe-Time] When null Registers are used, this is the
  2222.         time between sending a null Register and the Register-
  2223.         Suppression-Timer expiring unless it is restarted by
  2224.         receiving a Register-Stop. Thus, a null Register would be
  2225.         sent when the Register-Suppression-Timer reaches this
  2226.         value. {Default: 5 seconds.}
  2227.  
  2228.    *    [Assert-Timeout] This is the interval between the last
  2229.         time an Assert is received, and the time at which the
  2230.         assert is timed out. {Default: 180 seconds.}
  2231.  
  2232.    *    [Random-Delay-Join-Timeout] This is the maximum
  2233.         interval between the time when the RPF neighbor changes,
  2234.         and the time at which a triggered Join/Prune message is
  2235.         sent.  {Default: 4.5 seconds.}
  2236.  
  2237.    *    [Hello-Period] This is the interval between sending
  2238.         Hello messages. {Default: 30 seconds.}
  2239.  
  2240.  
  2241.  
  2242. Estrin, et. al.               Experimental                     [Page 40]
  2243.  
  2244. RFC 2117                         PIM-SM                       June 1997
  2245.  
  2246.  
  2247.    *    [Hello-Holdtime] This is the Holdtime specified in
  2248.         Hello messages, after which neighbors will time out their
  2249.         neighbor entries for the router. This should be set to 3.5
  2250.         * [Hello-Period]. {Default: 105 seconds.}
  2251.  
  2252.    *    [C-RP-Adv-Period] For C-RPs, this is the interval
  2253.         between sending C-RP-Adv messages. {Default: 60 seconds.}
  2254.  
  2255.    *    [RP-Holdtime] For C-RPs, this is the Holdtime specified
  2256.         in C-RP-Adv messages, and is used by the BSR to time out
  2257.         RPs. This should be set to 2.5 * [C-RP-Adv-Period].
  2258.         {Default: 150 seconds.}
  2259.  
  2260.    *    [Bootstrap-Period] At the elected BSR, this is the
  2261.         interval between originating Bootstrap messages, and should
  2262.         be equal to 60 seconds.
  2263.  
  2264.  
  2265.    *    [Bootstrap-Timeout] This is the time after which the
  2266.         elected BSR will be assumed unreachable when Bootstrap
  2267.         messages are not received from it. This should be set to
  2268.         2.5 * [Bootstrap-Period]. {Default: 150 seconds.}
  2269.  
  2270.  
  2271.  
  2272.  
  2273.  
  2274.  
  2275.  
  2276.  
  2277.  
  2278.  
  2279.  
  2280.  
  2281.  
  2282.  
  2283.  
  2284.  
  2285.  
  2286.  
  2287.  
  2288.  
  2289.  
  2290.  
  2291.  
  2292.  
  2293.  
  2294.  
  2295.  
  2296.  
  2297.  
  2298. Estrin, et. al.               Experimental                     [Page 41]
  2299.  
  2300. RFC 2117                         PIM-SM                       June 1997
  2301.  
  2302.  
  2303. 3.9 Summary of flags used
  2304.  
  2305.    Following is a summary of all the flags used in our scheme.
  2306.  
  2307. Bit           |  Used in    |  Definition
  2308.  
  2309. Authoritative | C-RP-Adv    | Group-prefix information should not be
  2310.                               over-ridden by BSR
  2311. Border        | Register    | Register for external sources is coming
  2312.                               from PIM multicast border router
  2313. Null          | Register    | Register sent as Probe of RP, the
  2314.                               encapsulated IP data packet should not
  2315.                               be forwarded
  2316. RPT           | Route entry | Entry represents state on the RP-tree
  2317. RPT           | Join/Prune  | Join is associated with the shared tree
  2318.                               and therefore the Join/Prune message is
  2319.                               propagated along the RP-tree (source
  2320.                               encoded is an RP address)
  2321. RPT           | Assert      | The data packet was routed down the shared
  2322.                               tree; thus, the path indicated corresponds
  2323.                               to the RP tree
  2324. SPT           | (S,G) entry | Packets have arrived on the iif towards S,
  2325.                               and the iif is different from the (*,G)
  2326.                               iif
  2327. WC            |Join         | The receiver expects to receive packets
  2328.                               from all sources via this (shared tree)
  2329.                               path. Thus, the Join/Prune applies to a
  2330.                               (*,G) entry
  2331. WC            | Route entry | Wildcard entry; if there is no more
  2332.                               specific match for a particular source,
  2333.                               packets will be forwarded according to
  2334.                               this entry
  2335.  
  2336.  
  2337. 3.10 Security
  2338.  
  2339.    All PIM control messages may use IPSec [6] to address security
  2340.    concerns.
  2341.  
  2342. 4 Packet Formats
  2343.  
  2344.    This section describes the details of the packet formats for PIM
  2345.    control messages.
  2346.  
  2347.    All PIM control messages have protocol number 103.
  2348.  
  2349.  
  2350.  
  2351.  
  2352.  
  2353.  
  2354. Estrin, et. al.               Experimental                     [Page 42]
  2355.  
  2356. RFC 2117                         PIM-SM                       June 1997
  2357.  
  2358.  
  2359.    Basically, PIM messages are either unicast (e.g.  Registers and
  2360.    Register-Stop), or multicast hop-by-hop to `ALL-PIM-ROUTERS' group
  2361.    `224.0.0.13' (e.g. Join/Prune, Asserts, etc.).
  2362.  
  2363.     0                   1                   2                   3
  2364.     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
  2365.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2366.    |PIM Ver| Type  | Addr length   |           Checksum            |
  2367.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2368.  
  2369.  
  2370.    PIM Ver
  2371.          PIM Version number is 2.
  2372.  
  2373.    Type  Types for specific PIM messages.  PIM Types are:
  2374.  
  2375.       0 = Hello
  2376.       1 = Register
  2377.       2 = Register-Stop
  2378.       3 = Join/Prune
  2379.       4 = Bootstrap
  2380.       5 = Assert
  2381.       6 = Graft (used in PIM-DM only)
  2382.       7 = Graft-Ack (used in PIM-DM only)
  2383.       8 = Candidate-RP-Advertisement
  2384.  
  2385.    Addr length
  2386.          Address length in bytes.  Throughout this section this
  2387.          would indicate the number of bytes in the Address field of
  2388.          an address, including unicast and group addresses.
  2389.  
  2390.    Checksum
  2391.          The checksum is the 16-bit one's complement of  the  one's
  2392.          complement  sum  of  the entire PIM message, (excluding the
  2393.          data portion in the Register message).  For  computing  the
  2394.          checksum, the checksum field is zeroed.
  2395.  
  2396. 4.1 Encoded Source and Group Address formats
  2397.  
  2398.    1    Unicast address: Only the address is included.  The length
  2399.         of the unicast address in bytes is specified in the `Addr
  2400.         length' field in the header.
  2401.  
  2402.    2    Encoded-Group-Address: Takes the following format:
  2403.  
  2404.  
  2405.  
  2406.  
  2407.  
  2408.  
  2409.  
  2410. Estrin, et. al.               Experimental                     [Page 43]
  2411.  
  2412. RFC 2117                         PIM-SM                       June 1997
  2413.  
  2414.  
  2415.    0                   1                   2                   3
  2416.    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
  2417.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2418.    |     Reserved  |  Mask Len     | Group multicast Address ...   |
  2419.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2420.    | ...Group multicast Address ...|
  2421.    +-+-+-+-+-+-+-+-+-+-+~+~+~+~+~+~+
  2422.  
  2423.  
  2424.         Reserved
  2425.               Transmitted as zero. Ignored upon receipt.
  2426.  
  2427.         Mask Length
  2428.               The Mask length is 8 bits. The value is the number of
  2429.               contiguous bits left justified used as a mask which
  2430.               describes the address. It is less than or equal to
  2431.               Addr length * 8. If the message is sent for a single
  2432.               group then the Mask length must equal Addr length * 8
  2433.               (i.e. 32 for IPv4 and 128 for IPv6).
  2434.  
  2435.         Group multicast Address
  2436.               contains the group address, and has number of bytes
  2437.               equal to that specified in the Addr length field.
  2438.  
  2439.    3    Encoded-Source-Address: Takes the following format:
  2440.  
  2441.  
  2442.    0                   1                   2                   3
  2443.    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
  2444.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2445.    | Rsrvd   |S|W|R|  Mask Len     | Source Address ...            |
  2446.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2447.    |  ...  Source Address          |
  2448.    +-+-+-+-+-+-+-+-+-+-+-+-+-+~+~+-+
  2449.  
  2450.  
  2451.         Reserved
  2452.               Transmitted as zero, ignored on receipt.
  2453.  
  2454.         S,W,R See Section 4.5 for details.
  2455.  
  2456.  
  2457.  
  2458.  
  2459.  
  2460.  
  2461.  
  2462.  
  2463.  
  2464.  
  2465.  
  2466. Estrin, et. al.               Experimental                     [Page 44]
  2467.  
  2468. RFC 2117                         PIM-SM                       June 1997
  2469.  
  2470.  
  2471.         Mask Length
  2472.               Mask length is 8 bits. The value is the number of
  2473.               contiguous bits left justified used as a mask which
  2474.               describes the address. The mask length must be less
  2475.               than or equal to Addr Length * 8. If the message is
  2476.               sent for a single source then the Mask length must
  2477.               equal Addr length * 8.  In version 2 of PIM, it is
  2478.               strongly recommended that this field be set to 32 for
  2479.               IPv4.
  2480.  
  2481.         Source Address
  2482.               The address length is indicated from the Addr length
  2483.               field at the beginning of the header. For IPv4, the
  2484.               address length is 4 octets.
  2485.  
  2486. 4.2 Hello Message
  2487.  
  2488.    It is sent periodically by routers on all interfaces.
  2489.  
  2490.    0                   1                   2                   3
  2491.    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
  2492.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2493.    |PIM Ver| Type  | Addr length   |           Checksum            |
  2494.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2495.    |       OptionType              |         OptionLength          |
  2496.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2497.    |                          OptionValue                          |
  2498.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+~+~+
  2499.    |                               .                               |
  2500.    |                               .                               |
  2501.    |                               .                               |
  2502.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2503.    |       OptionType              |         OptionLength          |
  2504.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2505.    |                          OptionValue                          |
  2506.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+~+~+
  2507.  
  2508.  
  2509.    PIM Version, Type, Addr length, Checksum
  2510.          Described above.
  2511.  
  2512.    OptionType
  2513.          The type of the option given in the following OptionValue
  2514.          field.
  2515.  
  2516.    OptionLength
  2517.          The length of the OptionValue field in bytes.
  2518.  
  2519.  
  2520.  
  2521.  
  2522. Estrin, et. al.               Experimental                     [Page 45]
  2523.  
  2524. RFC 2117                         PIM-SM                       June 1997
  2525.  
  2526.  
  2527.    OptionValue
  2528.          A variable length field, carrying the value of the option.
  2529.  
  2530.    The Option fields may contain the following values:
  2531.  
  2532.    *    OptionType = 1; OptionLength = 2; OptionValue = Holdtime;
  2533.         where Holdtime is the amount of time a receiver must keep
  2534.         the neighbor reachable, in seconds. If the Holdtime is set
  2535.         to `0xffff', the receiver of this message never times out
  2536.         the neighbor. This may be used with ISDN lines, to avoid
  2537.         keeping the link up with periodic Hello messages.
  2538.         Furthermore, if the Holdtime is set to `0', the information
  2539.         is timed out immediately.
  2540.  
  2541.    *    OptionType 2 to 16: reserved
  2542.  
  2543.    *    The rest of the OptionTypes are defined in another
  2544.         document.
  2545.  
  2546.    In general, options may be ignored; but a router must not ignore the
  2547.    'Holdtime' OptionType.
  2548.  
  2549. 4.3 Register Message
  2550.  
  2551.    A Register message is sent by the DR or a PMBR to the RP when a
  2552.    multicast packet needs to be transmitted on the RP-tree. Source IP
  2553.    address is set to the address of the DR, destination IP address is to
  2554.    the RP's address.
  2555.  
  2556.  
  2557.    0                   1                   2                   3
  2558.    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
  2559.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2560.    |PIM Ver| Type  | Addr length   |           Checksum            |
  2561.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2562.    |B|N|                       Reserved                            |
  2563.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2564.    |                                                               |
  2565.    ~                      Multicast data packet                    ~
  2566.    |                                                               |
  2567.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2568.  
  2569.  
  2570.    PIM Version, Type, Addr length, Checksum
  2571.         Described above.  {Note that the checksum for Registers
  2572.         is done only on the PIM header, excluding the data packet
  2573.         portion.}
  2574.  
  2575.  
  2576.  
  2577.  
  2578. Estrin, et. al.               Experimental                     [Page 46]
  2579.  
  2580. RFC 2117                         PIM-SM                       June 1997
  2581.  
  2582.  
  2583.    B     The Border bit. If the router is a DR for a source that it
  2584.          is directly connected to, it sets the B bit to 0. If the
  2585.          router is a PMBR for a source in a directly connected
  2586.          cloud, it sets the B bit to 1.
  2587.  
  2588.    N     The Null-Register bit. Set to 1 by a DR that is probing
  2589.          the RP before expiring its local Register-Suppression
  2590.          timer. Set to 0 otherwise.
  2591.  
  2592.    Multicast data packet
  2593.          The original packet sent by the source.
  2594.  
  2595.    For (S,G) null Registers, the Multicast data packet portion contains
  2596.    only a dummy IP header with S as the source address, G as the
  2597.    destination address, and a data length of zero.
  2598.  
  2599. 4.4 Register-Stop Message
  2600.  
  2601.    A Register-Stop is unicast from the RP  to  the  sender  of  the
  2602.    Register  message. Source IP address is the address to which the
  2603.    register was addressed. Destination IP  address  is  the  source
  2604.    address of the register message.
  2605.  
  2606.  
  2607.    0                   1                   2                   3
  2608.    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
  2609.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2610.    |PIM Ver| Type  | Addr length   |           Checksum            |
  2611.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2612.    |                    Encoded-Group Address                      |
  2613.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2614.    |                    Unicast-Source Address                     |
  2615.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2616.  
  2617.  
  2618.    PIM Version, Type, Addr length, Checksum
  2619.          Described above.
  2620.  
  2621.    Encoded-Group Address
  2622.          Format described above. Note that for Register-Stops the
  2623.          Mask Len field contains Addr length * 8 (32 for IPv4), if
  2624.          the message is sent for a single group.
  2625.  
  2626.    Unicast-Source Address
  2627.          IP host address of source from multicast data packet in
  2628.          register. The length of this field in bytes is specified in
  2629.          the Addr length field. A special wild card value (0.0.0.0),
  2630.          can be used to indicate any source.
  2631.  
  2632.  
  2633.  
  2634. Estrin, et. al.               Experimental                     [Page 47]
  2635.  
  2636. RFC 2117                         PIM-SM                       June 1997
  2637.  
  2638.  
  2639. 4.5 Join/Prune Message
  2640.  
  2641.    A Join/Prune message is sent by routers towards upstream sources and
  2642.    RPs.  Joins are sent to build shared trees (RP trees) or source trees
  2643.    (SPT). Prunes are sent to prune source trees when members leave
  2644.    groups as well as sources that do not use the shared tree.
  2645.  
  2646.  
  2647.  
  2648.  
  2649.  
  2650.  
  2651.  
  2652.  
  2653.  
  2654.  
  2655.  
  2656.  
  2657.  
  2658.  
  2659.  
  2660.  
  2661.  
  2662.  
  2663.  
  2664.  
  2665.  
  2666.  
  2667.  
  2668.  
  2669.  
  2670.  
  2671.  
  2672.  
  2673.  
  2674.  
  2675.  
  2676.  
  2677.  
  2678.  
  2679.  
  2680.  
  2681.  
  2682.  
  2683.  
  2684.  
  2685.  
  2686.  
  2687.  
  2688.  
  2689.  
  2690. Estrin, et. al.               Experimental                     [Page 48]
  2691.  
  2692. RFC 2117                         PIM-SM                       June 1997
  2693.  
  2694.  
  2695.     0                   1                   2                   3
  2696.     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
  2697.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2698.    |PIM Ver| Type  | Addr length   |           Checksum            |
  2699.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2700.    |             Unicast-Upstream Neighbor Address                 |
  2701.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2702.    |  Reserved     | Num groups    |          Holdtime             |
  2703.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2704.    |            Encoded-Multicast Group Address-1                  |
  2705.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2706.    |   Number of Joined  Sources   |   Number of Pruned Sources    |
  2707.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2708.    |               Encoded-Joined Source Address-1                 |
  2709.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2710.    |                             .                                 |
  2711.    |                             .                                 |
  2712.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2713.    |               Encoded-Joined Source Address-n                 |
  2714.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2715.    |               Encoded-Pruned Source Address-1                 |
  2716.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2717.    |                             .                                 |
  2718.    |                             .                                 |
  2719.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2720.    |               Encoded-Pruned Source Address-n                 |
  2721.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2722.    |                           .                                   |
  2723.    |                           .                                   |
  2724.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2725.    |                Encoded-Multicast Group Address-n              |
  2726.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2727.    |   Number of Joined  Sources   |   Number of Pruned Sources    |
  2728.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2729.    |               Encoded-Joined Source Address-1                 |
  2730.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2731.    |                             .                                 |
  2732.    |                             .                                 |
  2733.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2734.    |               Encoded-Joined Source Address-n                 |
  2735.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2736.    |               Encoded-Pruned Source Address-1                 |
  2737.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2738.    |                             .                                 |
  2739.    |                             .                                 |
  2740.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2741.    |               Encoded-Pruned Source Address-n                 |
  2742.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2743.  
  2744.  
  2745.  
  2746. Estrin, et. al.               Experimental                     [Page 49]
  2747.  
  2748. RFC 2117                         PIM-SM                       June 1997
  2749.  
  2750.  
  2751.    PIM Version, Type, Addr length, Checksum
  2752.          Described above.
  2753.  
  2754.    Upstream Neighbor Address
  2755.          The IP address of the RPF or upstream neighbor.
  2756.  
  2757.    Reserved
  2758.          Transmitted as zero, ignored on receipt.
  2759.  
  2760.    Holdtime
  2761.          The amount of time a receiver must keep the Join/Prune
  2762.          state alive, in seconds.  If the Holdtime is set to
  2763.          `0xffff', the receiver of this message never times out the
  2764.          oif. This may be used with ISDN lines, to avoid keeping the
  2765.          link up with periodical Join/Prune messages.  Furthermore,
  2766.          if the Holdtime is set to `0', the information is timed out
  2767.          immediately.
  2768.  
  2769.    Number of Groups
  2770.          The number of multicast group sets contained in the
  2771.          message.
  2772.  
  2773.    Encoded-Multicast group address
  2774.          For format description see Section
  2775.          4.1. A wild card group in the (*,*,RP) join is represented
  2776.          by a 224.0.0.0 in the group address field and `4' in the
  2777.          mask length field. A (*,*,RP) join also has the WC-bit and
  2778.          the RPT-bit set.
  2779.  
  2780.    Number of Joined Sources
  2781.          Number of join source addresses listed for a given group.
  2782.  
  2783.    Join Source Address-1 .. n
  2784.          This list contains the sources that the sending router
  2785.          will forward multicast datagrams for if received on the
  2786.          interface this message is sent on.
  2787.  
  2788.          See format section 4.1. The fields explanation for the
  2789.          Encoded-Source-Address format follows:
  2790.  
  2791.  
  2792.         Reserved
  2793.               Described above.
  2794.  
  2795.         S     The Sparse bit is a 1 bit value, set to 1 for PIM-SM.
  2796.               It is used for PIM v.1 compatibility.
  2797.  
  2798.  
  2799.  
  2800.  
  2801.  
  2802. Estrin, et. al.               Experimental                     [Page 50]
  2803.  
  2804. RFC 2117                         PIM-SM                       June 1997
  2805.  
  2806.  
  2807.         W     The WC bit is a 1 bit value. If 1, the join or prune
  2808.               applies to the (*,G) or (*,*,RP) entry. If 0, the join
  2809.               or prune applies to the (S,G) entry where S is Source
  2810.               Address.  Joins and prunes sent towards the RP must
  2811.               have this bit set.
  2812.  
  2813.         R     The RPT-bit is a 1 bit value. If 1, the information
  2814.               about (S,G) is sent towards the RP.  If 0, the
  2815.               information must be sent toward S, where S is the
  2816.               Source Address.
  2817.  
  2818.         Mask Length, Source Address
  2819.               Described above.
  2820.  
  2821.  
  2822.         Represented in the form of < WC-bit >< RPT-bit > < Mask length
  2823.         ><Source address>:
  2824.  
  2825.         A source address could be a host IP address :
  2826.  
  2827.          < 0 >< 0 >< 32 >< 192.1.1.17 >
  2828.  
  2829.         A source address could be the RP's IP address :
  2830.  
  2831.          < 1 >< 1 >< 32 >< 131.108.13.111 >
  2832.  
  2833.         A source address could be a subnet address to prune from the
  2834.         RP-tree :
  2835.  
  2836.          < 0 >< 1 >< 28 >< 192.1.1.16 >
  2837.  
  2838.         A source address could be a general aggregate :
  2839.  
  2840.          < 0 >< 0 >< 16 >< 192.1.0.0 >
  2841.  
  2842.    Number of Pruned Sources
  2843.          Number of prune source addresses listed for a group.
  2844.  
  2845.    Prune Source Address-1 .. n
  2846.          This list contains the sources that the sending router
  2847.          does not want to forward multicast datagrams for when
  2848.          received on the interface this message is sent on.  If the
  2849.          Join/Prune message boundary exceeds the maximum packet
  2850.          size, then the join and prune lists for the same group must
  2851.          be included in the same packet.
  2852.  
  2853.  
  2854.  
  2855.  
  2856.  
  2857.  
  2858. Estrin, et. al.               Experimental                     [Page 51]
  2859.  
  2860. RFC 2117                         PIM-SM                       June 1997
  2861.  
  2862.  
  2863. 4.6 Bootstrap Message
  2864.  
  2865.    The Bootstrap messages are multicast to `ALL-PIM-ROUTERS' group, out
  2866.    all interfaces having PIM neighbors (excluding the one over which the
  2867.    message was received).  Bootstrap messages are sent with TTL value of
  2868.    1. Bootstrap messages originate at the BSR, and are forwarded by
  2869.    intermediate routers.
  2870.  
  2871.    Bootstrap message is divided up into `semantic fragments', if the
  2872.    original message exceeds the maximum packet size boundaries.
  2873.  
  2874.    The semantics of a single `fragment' is given below:
  2875.  
  2876.  
  2877.  
  2878.  
  2879.  
  2880.  
  2881.  
  2882.  
  2883.  
  2884.  
  2885.  
  2886.  
  2887.  
  2888.  
  2889.  
  2890.  
  2891.  
  2892.  
  2893.  
  2894.  
  2895.  
  2896.  
  2897.  
  2898.  
  2899.  
  2900.  
  2901.  
  2902.  
  2903.  
  2904.  
  2905.  
  2906.  
  2907.  
  2908.  
  2909.  
  2910.  
  2911.  
  2912.  
  2913.  
  2914. Estrin, et. al.               Experimental                     [Page 52]
  2915.  
  2916. RFC 2117                         PIM-SM                       June 1997
  2917.  
  2918.  
  2919.    0                   1                   2                   3
  2920.    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
  2921.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2922.    |PIM Ver| Type  | Addr length   |           Checksum            |
  2923.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2924.    |         Fragment Tag          | Hash Mask len | BSR-priority  |
  2925.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2926.    |                         Unicast-BSR-Address                   |
  2927.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2928.    |                         Encoded-Group Address-1               |
  2929.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2930.    | RP-Count-1    | Frag RP-Cnt-1 |         Reserved              |
  2931.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2932.    |                         Unicast-RP-Address-1                  |
  2933.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2934.    |          RP1-Holdtime         |           Unicast- . . .      |
  2935.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2936.    | . . . RP-Address-2            |       RP2-Holdtime            |
  2937.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2938.    |                               .                               |
  2939.    |                               .                               |
  2940.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2941.    |                         Unicast-RP-Address-m                  |
  2942.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2943.    |          RPm-Holdtime         |            Encoded- . . .     |
  2944.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2945.    | . . . Group Address-2         . . .                           |
  2946.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2947.    |                               .                               |
  2948.    |                               .                               |
  2949.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2950.    |                         Encoded-Group Address-n               |
  2951.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2952.    | RP-Count-m    | Frag RP-Cnt-m |          Reserved             |
  2953.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2954.    |                         Unicast-RP-Address-1                  |
  2955.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2956.    |          RP1-Holdtime         |           Unicast- . . .      |
  2957.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2958.    | . . . RP-Address-2            |       RP2-Holdtime            |
  2959.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2960.    |                               .                               |
  2961.    |                               .                               |
  2962.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2963.    |                         Unicast-RP-Address-m                  |
  2964.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2965.    |          RPm-Holdtime         |
  2966.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2967.  
  2968.  
  2969.  
  2970. Estrin, et. al.               Experimental                     [Page 53]
  2971.  
  2972. RFC 2117                         PIM-SM                       June 1997
  2973.  
  2974.  
  2975.    PIM Version, Type, Addr length, Checksum
  2976.          Described above.
  2977.  
  2978.    Fragment Tag
  2979.         A randomly generated number, acts to distinguish the
  2980.         fragments belonging to different Bootstrap messages;
  2981.         fragments belonging to same Bootstrap message carry the
  2982.         same `Fragment Tag'.
  2983.  
  2984.    Hash Mask len
  2985.         The length (in bits) of the mask to use in the hash
  2986.         function.  For IPv4 we recommend a value of 30. For IPv6 we
  2987.         recommend a value of 126.
  2988.  
  2989.    BSR-priority
  2990.         Contains the BSR priority value of the included BSR.  This
  2991.         field is considered as a high order byte when comparing BSR
  2992.         addresses.
  2993.  
  2994.    Unicast-BSR-Address
  2995.         The IP address of the bootstrap router for the domain. The
  2996.         length of this field in bytes is specified in Addr length.
  2997.  
  2998.    Encoded-Group Address-1..n
  2999.         The group prefix (address and mask) with which the
  3000.         Candidate RPs are associated. Format previously described.
  3001.  
  3002.    RP-Count-1..n
  3003.         The number of Candidate RP addresses included in the whole
  3004.         Bootstrap message for the corresponding group prefix. A
  3005.         router does not replace its old RP-Set for a given group
  3006.         prefix until/unless it receives `RP-Count' addresses for
  3007.         that prefix; the addresses could be carried over several
  3008.         fragments.  If only part of the RP-Set for a given group
  3009.         prefix was received, the router discards it, without
  3010.         updating that specific group prefix's RP-Set.
  3011.  
  3012.    Frag RP-Cnt-1..m
  3013.         The number of Candidate RP addresses included in this
  3014.         fragment of the Bootstrap message, for the corresponding
  3015.         group prefix. The `Frag RP-Cnt' field facilitates parsing
  3016.         of the RP-Set for a given group prefix, when carried over
  3017.         more than one fragment.
  3018.  
  3019.    Unicast-RP-address-1..m
  3020.         The address of the Candidate RPs, for the corresponding
  3021.         group prefix.  The length of this field in bytes is
  3022.         specified in Addr length.
  3023.  
  3024.  
  3025.  
  3026. Estrin, et. al.               Experimental                     [Page 54]
  3027.  
  3028. RFC 2117                         PIM-SM                       June 1997
  3029.  
  3030.  
  3031.    RP1..m-Holdtime
  3032.         The Holdtime for the corresponding RP. This field is copied
  3033.         from the `Holdtime' field of the associated RP stored at
  3034.         the BSR.
  3035.  
  3036. 4.7 Assert Message
  3037.  
  3038.    The Assert message is sent when a multicast data packet is received
  3039.    on an outgoing interface corresponding to the (S,G) or (*,G)
  3040.    associated with the source.
  3041.  
  3042.  
  3043.     0                   1                   2                   3
  3044.     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
  3045.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3046.    |PIM Ver| Type  | Addr length   |           Checksum            |
  3047.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3048.    |                      Encoded-Group Address                    |
  3049.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3050.    |                      Unicast-Source Address                   |
  3051.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3052.    |R|                        Metric Preference                    |
  3053.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3054.    |                          Metric                               |
  3055.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3056.  
  3057.  
  3058.    PIM Version, Type, Addr length, Checksum
  3059.          Described above.
  3060.  
  3061.    Encoded-Group Address
  3062.          The group address to which the data packet was addressed,
  3063.          and which triggered the Assert.  Format previously
  3064.          described.
  3065.  
  3066.    Unicast-Source Address
  3067.          Source IP address from IP multicast datagram that
  3068.          triggered the Assert packet to be sent. The length of this
  3069.          field in bytes is specified in Addr length.
  3070.  
  3071.    R     RPT-bit is a 1 bit value. If the IP multicast datagram
  3072.          that triggered the Assert packet is routed down the RP
  3073.          tree, then the RPT-bit is 1; if the IP multicast datagram
  3074.          is routed down the SPT, it is 0.
  3075.  
  3076.    Metric Preference
  3077.          Preference value assigned to the unicast routing protocol
  3078.          that provided the route to Host address.
  3079.  
  3080.  
  3081.  
  3082. Estrin, et. al.               Experimental                     [Page 55]
  3083.  
  3084. RFC 2117                         PIM-SM                       June 1997
  3085.  
  3086.  
  3087.    Metric The unicast routing table metric. The metric is in units
  3088.          applicable to the unicast routing protocol used.
  3089.  
  3090. 4.8 Graft Message
  3091.  
  3092.    Used in dense-mode. Refer to PIM dense mode specification.
  3093.  
  3094. 4.9 Graft-Ack Message
  3095.  
  3096.    Used in dense-mode. Refer to PIM dense mode specification.
  3097.  
  3098. 4.10 Candidate-RP-Advertisement
  3099.  
  3100.    Candidate-RP-Advertisements are periodically unicast from the C-RPs
  3101.    to the BSR.
  3102.  
  3103.  
  3104.     0                   1                   2                   3
  3105.     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
  3106.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3107.    |PIM Ver| Type  | Addr length   |           Checksum            |
  3108.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3109.    | Prefix-Cnt    |A| Reserved    |             Holdtime          |
  3110.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3111.    |                         Unicast-RP-Address                    |
  3112.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3113.    |                         Encoded-Group Address-1               |
  3114.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3115.    |                               .                               |
  3116.    |                               .                               |
  3117.    |                               .                               |
  3118.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3119.    |                         Encoded-Group Address-n               |
  3120.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  3121.  
  3122.  
  3123.    PIM Version, Type, Addr length, Checksum
  3124.          Described above.
  3125.  
  3126.    Prefix-Cnt
  3127.          The number of encoded group addresses included in the
  3128.          message; indicating the group prefixes for which the C-RP
  3129.          is advertising. A Prefix-Cnt of `0' implies a prefix of
  3130.          224.0.0.0 with mask length of 4; i.e. all multicast groups.
  3131.          If the C-RP is not configured with Group-prefix
  3132.          information, the C-RP puts a default value of `0' in this
  3133.          field.
  3134.  
  3135.  
  3136.  
  3137.  
  3138. Estrin, et. al.               Experimental                     [Page 56]
  3139.  
  3140. RFC 2117                         PIM-SM                       June 1997
  3141.  
  3142.  
  3143.    A     The Authoritative bit. This bit indicates that the BSR
  3144.          should not override the group-prefix information indicated
  3145.          in the C-RP Advertisement. In most cases C-RPs set this bit
  3146.          to 0.
  3147.  
  3148.    Holdtime
  3149.          The amount of time the advertisement is valid. This field
  3150.          allows advertisements to be aged out.
  3151.  
  3152.    Unicast-RP-Address
  3153.          The address of the interface to advertise as a Candidate
  3154.          RP.  The length of this field in bytes is specified in Addr
  3155.          length.
  3156.  
  3157.    Encoded-Group Address-1..n
  3158.          The group prefixes for which the C-RP is advertising.
  3159.          Format previously described.
  3160.  
  3161. 5 Acknowledgments
  3162.  
  3163.    Tony Ballardie, Scott Brim, Jon Crowcroft, Bill Fenner, Paul Francis,
  3164.    Joel Halpern, Horst Hodel, Polly Huang, Stephen Ostrowski, Lixia
  3165.    Zhang and Girish Chandranmenon provided detailed comments on previous
  3166.    drafts. The authors of CBT [7] and membership of the IDMR WG provided
  3167.    many of the motivating ideas for this work and useful feedback on
  3168.    design details.
  3169.  
  3170.    This work was supported by the National Science Foundation, ARPA,
  3171.    cisco Systems and Sun Microsystems.
  3172.  
  3173.  
  3174.  
  3175.  
  3176.  
  3177.  
  3178.  
  3179.  
  3180.  
  3181.  
  3182.  
  3183.  
  3184.  
  3185.  
  3186.  
  3187.  
  3188.  
  3189.  
  3190.  
  3191.  
  3192.  
  3193.  
  3194. Estrin, et. al.               Experimental                     [Page 57]
  3195.  
  3196. RFC 2117                         PIM-SM                       June 1997
  3197.  
  3198.  
  3199. 6 Appendices
  3200.  
  3201. 6.1 Appendix I: Major Changes and Updates to the Spec
  3202.  
  3203.    This appendix populates the major changes in the specification
  3204.    document as compared to `draft-ietf-idmr-pim-spec-01.ps,txt'.
  3205.  
  3206.    * Major Changes
  3207.  
  3208.    List of changes since March '96 IETF:
  3209.  
  3210.    (*,*,RP) Joins state and data forwarding check; replaces (*,G-
  3211.    Prefix) Joins state for interoperability. (*,G) negative cache
  3212.    introduced for the (*,*,RP) state supporting mechanisms.
  3213.  
  3214.    Semantic fragmentation for the Bootstrap message.
  3215.  
  3216.    Refinement of Assert details.
  3217.  
  3218.    Addition and refinement of Join/Prune suppression and Register
  3219.    suppression (introduction of null Registers).
  3220.  
  3221.    Editorial changes and clarifications to the timers section.
  3222.  
  3223.    Addition of Appendix II (BSR Election and RP-Set Distribution), and
  3224.    Appendix III (Glossary of Terms).
  3225.  
  3226.    Addition of table of contents.
  3227.  
  3228.    List of changes incurred since version 1 of the spec.:
  3229.  
  3230.    Proposal and refinement of bootstrap router (BSR) election mechanisms
  3231.  
  3232.    Introduction of hash functions for Group to RP mapping
  3233.  
  3234.    New RP-liveness indication mechanisms based upon the the Bootstrap
  3235.    Router (BSR) and the Bootstrap messages.
  3236.  
  3237.    Removal of reachability messages, RP reports and multiple RPs per
  3238.    group.
  3239.  
  3240.  
  3241.    * Packet Format Changes
  3242.  
  3243.    Packet Format incurred updates to accommodate different address
  3244.    lengths, and address aggregation.
  3245.  
  3246.  
  3247.  
  3248.  
  3249.  
  3250. Estrin, et. al.               Experimental                     [Page 58]
  3251.  
  3252. RFC 2117                         PIM-SM                       June 1997
  3253.  
  3254.  
  3255.    1    The `Addr length' field was added to the PIM fixed header
  3256.         to specify the address length in bytes of the underlying
  3257.         protocol, see section 4.
  3258.  
  3259.    2    The Encoded source and group address formats were
  3260.         introduced, with the use of a `Mask length' field to allow
  3261.         aggregation, section 4.1.
  3262.  
  3263.    3    Packet formats are no longer IGMP messages; rather PIM
  3264.         messages.
  3265.  
  3266.  
  3267.    PIM message types and formats were also modified:
  3268.  
  3269.    [Note: most changes were made to the May 95 version, unless otherwise
  3270.    specified].
  3271.  
  3272.    1    Obsolete messages:
  3273.  
  3274.         Register-Ack [Feb. 96]
  3275.  
  3276.         Poll and Poll Response [Feb. 96]
  3277.  
  3278.         RP-Reachability [Feb. 96]
  3279.  
  3280.         RPlist-Mapping [Feb. 96]
  3281.  
  3282.  
  3283.    2    New messages:
  3284.  
  3285.         Candidate-RP-Advertisement [change made in October 95]
  3286.         RP-Set [Feb. 96]
  3287.  
  3288.  
  3289.    3    Modified messages:
  3290.  
  3291.         Join/Prune [Feb. 96]
  3292.         Register [Feb. 96]
  3293.         Register-Stop [Feb.  96]
  3294.         Hello (addition of OptionTypes) [Aug 96]
  3295.  
  3296.  
  3297.    4    Renamed messages:
  3298.  
  3299.         Query messages are renamed as Hello messages [Aug. 96]
  3300.         RP-Set messages are renamed as Bootstrap messages [Aug. 96]
  3301.  
  3302.  
  3303.  
  3304.  
  3305.  
  3306. Estrin, et. al.               Experimental                     [Page 59]
  3307.  
  3308. RFC 2117                         PIM-SM                       June 1997
  3309.  
  3310.  
  3311. 6.2 Appendix II: BSR Election and RP-Set Distribution
  3312.  
  3313.    For simplicity, the Bootstrap message is used in both the BSR election
  3314.    and the RP-Set distribution.
  3315.  
  3316.    The above two mechanisms; the BSR election, and the RP-Set
  3317.    distribution; are realized through the following state machine,
  3318.    illustrated in figure 4:
  3319.  
  3320.       [Figures are present only in the postscript version]
  3321.       Fig.  4 State Diagram for the BSR election and RP-Set
  3322.       distribution mechanisms
  3323.  
  3324.    The protocol transitions for a C-BSR are given in state diagram (a).
  3325.    For routers not configured as C-BSRs, the protocol transitions are
  3326.    given in state diagram (b).
  3327.  
  3328.    Each PIM router keeps a Bootstrap-timer, initialized to
  3329.    [Bootstrap-Timeout], in addition to a local BSR field `LclBSR'
  3330.    (initialized to a local address if C-BSR, or to 0 otherwise), and a
  3331.    local RP-Set `LclRP-Set' (initially empty).  The two main stimuli to
  3332.    the state machine are the timer events, and receiving an Bootstrap
  3333.    message:
  3334.  
  3335.    * Initial States and Timer Events
  3336.  
  3337.  
  3338.    1    If the router is a C-BSR:
  3339.  
  3340.         1    The router operates initially in the `CandBSR' state, where
  3341.              it does not originate any Bootstrap messages.
  3342.  
  3343.         2    If the Bootstrap-timer expires, and the current state is
  3344.              `CandBSR', the router originates an Bootstrap message -
  3345.              carrying the local RP-Set, and its own BSR priority and
  3346.              address-, restarts the Bootstrap-timer at [Bootstrap-
  3347.              Period] seconds and transits into the `ElectedBSR' state.
  3348.  
  3349.         3    If the Bootstrap-timer expires, and the current state is
  3350.              `ElectedBSR', the router originates an Bootstrap message,
  3351.              and restarts the RP-Set timer at [Bootstrap-Period].  No
  3352.              state transition is incurred.
  3353.  
  3354.              This way, the elected BSR originates periodic Bootstrap
  3355.              messages every [Bootstrap-Period].
  3356.  
  3357.  
  3358.  
  3359.  
  3360.  
  3361.  
  3362. Estrin, et. al.               Experimental                     [Page 60]
  3363.  
  3364. RFC 2117                         PIM-SM                       June 1997
  3365.  
  3366.  
  3367.    2    If a router is not a C-BSR:
  3368.  
  3369.         1    The router operates initially in the 'AxptAny' state.  In
  3370.              such state, a router accepts the first Bootstrap message
  3371.              from the RPF neighbor toward the included BSR. The Reverse
  3372.              Path Forwarding (RPF) neighbor in this case is the next hop
  3373.              router en route to the included BSR.
  3374.  
  3375.         2    If the Bootstrap-timer expires, and the current state is
  3376.              `AxptPref', -where the router accepts only preferred.
  3377.              Bootstrap messages from the RPF neighbor toward the
  3378.              included BSR-, the router transits into the `AxptAny'
  3379.              state (preferred Bootstrap messages are those that carry
  3380.              BSR-priority and address higher than, or equal to,
  3381.              `LclBSR').
  3382.  
  3383.              In this case, if an elected BSR becomes unreachable, the
  3384.              routers start accepting Bootstrap messages from another C-
  3385.              BSR after the Bootstrap-timer expires.  All PIM routers
  3386.              within a domain converge on the preferred (with highest
  3387.              priority and address) reachable C-BSR.
  3388.  
  3389.  
  3390.    * Receiving Bootstrap Message
  3391.  
  3392.    To avoid loops, an RPF check is performed on the included BSR address.
  3393.    Upon receiving an Bootstrap message from the RPF neighbor toward the
  3394.    included BSR, the following actions are taken:
  3395.  
  3396.    1    If the router is not a C-BSR:
  3397.  
  3398.         1    If the current state is 'AxptAny', the router accepts the
  3399.              Bootstrap message, and transits into the 'AxptPref' state.
  3400.  
  3401.         2    If the current state is 'AxptPref', and the Bootstrap
  3402.              message is preferred, the message is accepted. No state
  3403.              transition is incurred.
  3404.  
  3405.    2    If the router is a C-BSR, and the Bootstrap message is
  3406.         preferred, the message is accepted. Further, if this happens
  3407.         when the current state is
  3408.  
  3409.    When an Bootstrap message is accepted, the router restarts the
  3410.    Bootstrap-timer at [Bootstrap-Timeout], stores the received BSR
  3411.    priority and address in `LclBSR', and the received RP-Set in
  3412.    `LclRP-Set', and forwards the Bootstrap message out all interfaces
  3413.    except the receiving interface.
  3414.  
  3415.  
  3416.  
  3417.  
  3418. Estrin, et. al.               Experimental                     [Page 61]
  3419.  
  3420. RFC 2117                         PIM-SM                       June 1997
  3421.  
  3422.  
  3423.    If an Bootstrap message is rejected, no state transitions are
  3424.    triggered.
  3425.  
  3426. 6.3 Appendix III: Glossary of Terms
  3427.  
  3428.    Following is an alphabetized list of terms and definitions used
  3429.    throughout this specification.
  3430.  
  3431.  
  3432.    *    {Bootstrap router (BSR)}. A BSR is a dynamically elected router
  3433.         within a PIM domain. It is responsible for constructing the RP-
  3434.         Set and originating Bootstrap messages.
  3435.  
  3436.    *    {Candidate-BSR (C-BSR)}. A C-BSR is a router configured to
  3437.         participate in the BSR election and act as BSRs if elected.
  3438.  
  3439.    *    {Candidate RP (C-RP)}. A C-RP is a router configured to send
  3440.         periodic Candidate-RP-Advertisement messages to the BSR, and act
  3441.         as an RP when it receives Join/Prune or Register messages for
  3442.         the advertised group prefix.
  3443.  
  3444.    *    {Designated Router (DR)}.  The DR sets up multicast route
  3445.         entries and sends corresponding Join/Prune and Register messages
  3446.         on behalf of directly-connected receivers and sources,
  3447.         respectively.  The DR may or may not be the same router as the
  3448.         IGMP Querier. The DR may or may not be the long-term, last-hop
  3449.         router for the group; a router on the LAN that has a lower
  3450.         metric route to the data source, or to the group's RP, may take
  3451.         over the role of sending Join/Prune messages.
  3452.  
  3453.    *    {Incoming interface (iif)}. The iif of a multicast route entry
  3454.         indicates the interface from which multicast data packets are
  3455.         accepted for forwarding. The iif is initialized when the entry
  3456.         is created.
  3457.  
  3458.    *    {Join list}. The Join list is one of two lists of addresses that
  3459.         is included in a Join/Prune message; each address refers to a
  3460.         source or RP.  It indicates those sources or RPs to which
  3461.         downstream receiver(s) wish to join.
  3462.  
  3463.    *    {Last-hop router}. The last-hop router is the last router to
  3464.         receive multicast data packets before they are delivered to
  3465.         directly-connected member hosts. In general the last-hop router
  3466.         is the DR for the LAN.  However, under various conditions
  3467.         described in this document a parallel router connected to the
  3468.         same LAN may take over as the last-hop router in place of the
  3469.         DR.
  3470.  
  3471.  
  3472.  
  3473.  
  3474. Estrin, et. al.               Experimental                     [Page 62]
  3475.  
  3476. RFC 2117                         PIM-SM                       June 1997
  3477.  
  3478.  
  3479.    *    {Outgoing interface (oif) list}. Each multicast route entry has
  3480.         an oif list containing the outgoing interfaces to which
  3481.         multicast packets should be forwarded.
  3482.  
  3483.    *    {Prune List}. The Prune list is the second list of addresses
  3484.         that is included in a Join/Prune message. It indicates those
  3485.         sources or RPs from which downstream receiver(s) wish to prune.
  3486.  
  3487.    *    {PIM Multicast Border Router (PMBR)}. A PMBR connects a PIM
  3488.         domain to other multicast routing domain(s).
  3489.  
  3490.    *    {Rendezvous Point (RP)}. Each multicast group has a shared-tree
  3491.         via which receivers hear of new sources and new receivers hear
  3492.         of all sources. The RP is the root of this per-group shared
  3493.         tree, called the RP-Tree.
  3494.  
  3495.    *    {RP-Set}. The RP-Set is a set of RP addresses constructed by
  3496.         the BSR based on Candidate-RP advertisements received. The RP-
  3497.         Set information is distributed to all PIM routers in the BSR's
  3498.         PIM domain.
  3499.  
  3500.    *    {Reverse Path Forwarding (RPF)}. RPF is used to select the
  3501.         appropriate incoming interface for a multicast route entry . The
  3502.         RPF neighbor for an IP address X is the the next-hop router used
  3503.         to forward packets toward X. The RPF interface is the interface
  3504.         to that RPF neighbor. In the common case this is the next hop
  3505.         used by the unicast routing protocol for sending unicast packets
  3506.         toward X. For example, in cases where unicast and multicast
  3507.         routes are not congruent, it can be different.
  3508.  
  3509.    *    {Route entry.} A multicast route entry is state maintained in a
  3510.         router along the distribution tree and is created, and updated
  3511.         based on incoming control messages.  The route entry may be
  3512.         different from the forwarding entry; the latter is used to
  3513.         forward data packets in real time. Typically a forwarding entry
  3514.         is not created until data packets arrive, the forwarding entry's
  3515.         iif and oif list are copied from the route entry, and the
  3516.         forwarding entry may be flushed and recreated at will.
  3517.  
  3518.    *    {Shortest path tree (SPT)}.  The SPT is the multicast
  3519.         distribution tree created by the merger of all of the shortest
  3520.         paths that connect receivers to the source (as determined by
  3521.         unicast routing).
  3522.  
  3523.    *    {Sparse Mode (SM)}. SM is one mode of operation of a multicast
  3524.         protocol.  PIM SM uses explicit Join/Prune messages and
  3525.         Rendezvous points in place of Dense Mode PIM's and DVMRP's
  3526.         broadcast and prune mechanism.
  3527.  
  3528.  
  3529.  
  3530. Estrin, et. al.               Experimental                     [Page 63]
  3531.  
  3532. RFC 2117                         PIM-SM                       June 1997
  3533.  
  3534.  
  3535.    *    {Wildcard (WC) multicast route entry}. Wildcard multicast route
  3536.         entries are those entries that may be used to forward packets
  3537.         for any source sending to the specified group. Wildcard bots in
  3538.         the join list of a Join/Prune message represent either a (*,G)
  3539.         or (*,*,RP) join; in the prune list they represent a (*,G)
  3540.         prune.
  3541.  
  3542.    *    {(S,G) route entry}. (S,G) is a source-specific route entry. It
  3543.         may be created in response to data packets, Join/Prune messages,
  3544.         or Asserts. The (S,G) state in routers creates a source-rooted,
  3545.         shortest path (or reverse shortest path) distribution tree.
  3546.         (S,G)RPT bit entries are source-specific entries on the shared
  3547.         RP-Tree; these entries are used to prune particular sources off
  3548.         of the shared tree.
  3549.  
  3550.    *    {(*,G) route entry}. Group members join the shared RP-Tree for
  3551.         a particular group. This tree is represented by (*,G) multicast
  3552.         route entries along the shortest path branches between the RP
  3553.         and the group members.
  3554.  
  3555.    *    {(*,*,RP) route entry}. (*,*,RP) refers to any source and any
  3556.         multicast group that maps to the RP included in the entry. The
  3557.         routers along the shortest path branches between a domain's
  3558.         RP(s) and its PMBRs keep (*,*,RP) state and use it to determine
  3559.         how to deliver packets toward the PMBRs if data packets arrive
  3560.         for which there is not a longer match. The wildcard group in the
  3561.         (*,*,RP) route entry is represented by a group address of
  3562.         224.0.0.0 and a mask length of 4 bits.
  3563.  
  3564.  
  3565.    References
  3566.  
  3567. 1.   Deering, S., D.Estrin, D.Farinacci, V.Jacobson, C.Liu, L.Wei,
  3568.      P.Sharma, and A.Helmy.  Protocol independent multicast (pim) :
  3569.      Motivation and architecture. Work in Progress.
  3570.  
  3571.  
  3572. 2.   Deering, S., D.Estrin, D.Farinacci, V.Jacobson, C.Liu, and L.Wei.
  3573.      The pim architecture for wide-area multicast routing.
  3574.      ACM Transactions on Networks, April 1996.
  3575.  
  3576.  
  3577. 3.   Estrin, D., D.Farinacci, V.Jacobson, C.Liu, L.Wei, P.Sharma, and
  3578.      A.Helmy.  Protocol independent multicast-dense mode (pim-dm) :
  3579.      Protocol specification.  Work in Progress.
  3580.  
  3581.  
  3582. 4.   Deering, S. Host extensions for ip multicasting, Aug 1989. RFC1112.
  3583.  
  3584.  
  3585.  
  3586. Estrin, et. al.               Experimental                     [Page 64]
  3587.  
  3588. RFC 2117                         PIM-SM                       June 1997
  3589.  
  3590.  
  3591. 5.   Fenner, W. Internet group management protocol, version 2.
  3592.      Work in Progress.
  3593.  
  3594.  
  3595. 6.   Atkinson, R. Security architecture for the internet protocol,
  3596.      August 1995. RFC-1825.
  3597.  
  3598.  
  3599. 7.   Ballardie, A.J., P.F. Francis, and J.Crowcroft. Core based trees.
  3600.      In Proceedings of the ACM SIGCOMM, San Francisco, 1993.
  3601.  
  3602.  
  3603.    Addresses of Authors:
  3604.  
  3605.    Deborah Estrin
  3606.    Computer Science Dept/ISI
  3607.    University of Southern Calif.
  3608.    Los Angeles, CA 90089 
  3609.    estrin@usc.edu
  3610.  
  3611.    Dino Farinacci
  3612.    Cisco Systems Inc.
  3613.    170 West Tasman Drive,
  3614.    San Jose, CA 95134
  3615.    dino@cisco.com
  3616.  
  3617.    Ahmed Helmy
  3618.    Computer Science Dept.
  3619.    University of Southern Calif.
  3620.    Los Angeles, CA 90089
  3621.    ahelmy@catarina.usc.edu
  3622.  
  3623.    David Thaler
  3624.    EECS Department
  3625.    University of Michigan
  3626.    Ann Arbor, MI 48109
  3627.    thalerd@eecs.umich.edu
  3628.  
  3629.    Stephen Deering
  3630.    Xerox PARC
  3631.    3333 Coyote Hill Road
  3632.    Palo Alto, CA 94304
  3633.    deering@parc.xerox.com
  3634.  
  3635.  
  3636.  
  3637.  
  3638.  
  3639.  
  3640.  
  3641.  
  3642.  
  3643. Estrin, et. al.               Experimental                     [Page 65]
  3644.  
  3645. RFC 2117                         PIM-SM                       June 1997
  3646.  
  3647.  
  3648.    Mark Handley
  3649.    Department of Computer Science
  3650.    University College London
  3651.    Gower Street
  3652.    London, WC1E 6BT
  3653.    UK
  3654.    m.handley@cs.ucl.ac.uk
  3655.  
  3656.    Van Jacobson
  3657.    Lawrence Berkeley Laboratory
  3658.    1 Cyclotron Road
  3659.    Berkeley, CA 94720
  3660.    van@ee.lbl.gov
  3661.  
  3662.    Ching-gung  Liu
  3663.    Computer Science Dept.
  3664.    University of Southern Calif.
  3665.    Los Angeles, CA 90089
  3666.    charley@catarina.usc.edu
  3667.  
  3668.    Puneet Sharma
  3669.    Computer Science Dept.
  3670.    University of Southern Calif.
  3671.    Los Angeles, CA 90089
  3672.    puneet@catarina.usc.edu
  3673.  
  3674.    Liming Wei
  3675.    Cisco Systems Inc.
  3676.    170 West Tasman Drive,
  3677.    San Jose, CA 95134
  3678.    lwei@cisco.com
  3679.  
  3680.  
  3681.  
  3682.  
  3683.  
  3684.  
  3685.  
  3686.  
  3687.  
  3688.  
  3689.  
  3690.  
  3691.  
  3692.  
  3693.  
  3694.  
  3695.  
  3696.  
  3697.  
  3698.  
  3699. Estrin, et. al.               Experimental                     [Page 66]
  3700.  
  3701.