tech-invite   World Map     

3GPP     Specs     Glossaries     Architecture     IMS     UICC       IETF     RFCs     Groups     SIP     ABNFs       Search

RFC 4601

 
 
 

Protocol Independent Multicast - Sparse Mode (PIM-SM): Protocol Specification (Revised)

Part 4 of 6, p. 62 to 90
Prev RFC Part       Next RFC Part

 


prevText      Top      Up      ToC       Page 62 
4.5.5.  Sending (*,*,RP) Join/Prune Messages

   The per-interface state machines for (*,*,RP) hold join state from
   downstream PIM routers.  This state then determines whether a router
   needs to propagate a Join(*,*,RP) upstream towards the RP.

   If a router wishes to propagate a Join(*,*,RP) upstream, it must also
   watch for messages on its upstream interface from other routers on
   that subnet, and these may modify its behavior.  If it sees a
   Join(*,*,RP) to the correct upstream neighbor, it should suppress its
   own Join(*,*,RP).  If it sees a Prune(*,*,RP) to the correct upstream
   neighbor, it should be prepared to override that prune by sending a
   Join(*,*,RP) almost immediately.  Finally, if it sees the Generation
   ID (see Section 4.3) of the correct upstream neighbor change, it
   knows that the upstream neighbor has lost state, and it should be
   prepared to refresh the state by sending a Join(*,*,RP) almost
   immediately.

   In addition, if the MRIB changes to indicate that the next hop
   towards the RP has changed, the router should prune off from the old
   next hop and join towards the new next hop.

   The upstream (*,*,RP) state machine contains only two states:

   Not Joined
      The downstream state machines and local membership information do
      not indicate that the router needs to join the (*,*,RP) tree for
      this RP.

   Joined
      The downstream state machines and local membership information
      indicate that the router should join the (*,*,RP) tree for this
      RP.

   In addition, one timer JT(*,*,RP) is kept that is used to trigger the
   sending of a Join(*,*,RP) to the upstream next hop towards the RP,
   NBR(RPF_interface(RP), MRIB.next_hop(RP)).

Top      Up      ToC       Page 63 
       Figure 6: Upstream (*,*,RP) state machine in tabular form

+-------------------++-------------------------------------------------+
|                   ||                      Event                      |
|  Prev State       ++-------------------------+-----------------------+
|                   ||   JoinDesired           |    JoinDesired        |
|                   ||   (*,*,RP) ->True       |    (*,*,RP) ->False   |
+-------------------++-------------------------+-----------------------+
|                   ||   -> J state            |    -                  |
|  NotJoined (NJ)   ||   Send Join(*,*,RP);    |                       |
|                   ||   Set Join Timer to     |                       |
|                   ||   t_periodic            |                       |
+-------------------++-------------------------+-----------------------+
|  Joined (J)       ||   -                     |    -> NJ state        |
|                   ||                         |    Send Prune         |
|                   ||                         |    (*,*,RP); Cancel   |
|                   ||                         |    Join Timer         |
+-------------------++-------------------------+-----------------------+

   In addition, we have the following transitions, which occur within
   the Joined state:

+----------------------------------------------------------------------+
|                         In Joined (J) State                          |
+-------------------+--------------------+-----------------------------+
| Timer Expires     |  See               |   See                       |
|                   |  Join(*,*,RP)      |   Prune(*,*,RP)             |
|                   |  to MRIB.          |   to MRIB.                  |
|                   |  next_hop(RP)      |   next_hop(RP)              |
+-------------------+--------------------+-----------------------------+
| Send              |  Increase Join     |   Decrease Join             |
| Join(*,*,RP);     |  Timer to          |   Timer to                  |
| Set Join Timer    |  t_joinsuppress    |   t_override                |
| to t_periodic     |                    |                             |
+-------------------+--------------------+-----------------------------+

Top      Up      ToC       Page 64 
+----------------------------------------------------------------------+
|                         In Joined (J) State                          |
+-----------------------------------+----------------------------------+
|    NBR(RPF_interface(RP),         |       MRIB.next_hop(RP) GenID    |
|    MRIB.next_hop(RP))             |       changes                    |
|    changes                        |                                  |
+-----------------------------------+----------------------------------+
|    Send Join(*,*,RP) to new       |       Decrease Join Timer to     |
|    next hop; Send                 |       t_override                 |
|    Prune(*,*,RP) to old           |                                  |
|    next hop; set Join Timer       |                                  |
|    to t_periodic                  |                                  |
+-----------------------------------+----------------------------------+

   This state machine uses the following macro:

     bool JoinDesired(*,*,RP) {
        if immediate_olist(*,*,RP) != NULL
            return TRUE
        else
            return FALSE
     }

   JoinDesired(*,*,RP) is true when the router has received (*,*,RP)
   Joins from any downstream interface.  Note that although JoinDesired
   is true, the router's sending of a Join(*,*,RP) message may be
   suppressed by another router sending a Join(*,*,RP) onto the upstream
   interface.

   Transitions from NotJoined State

   When the upstream (*,*,RP) state machine is in NotJoined state, the
   following event may trigger a state transition:

     JoinDesired(*,*,RP) becomes True
          The downstream state for (*,*,RP) has changed so that at least
          one interface is in immediate_olist(*,*,RP), making
          JoinDesired(*,*,RP) become True.

          The upstream (*,*,RP) state machine transitions to Joined
          state.  Send Join(*,*,RP) to the appropriate upstream
          neighbor, which is NBR(RPF_interface(RP), MRIB.next_hop(RP)).
          Set the Join Timer (JT) to expire after t_periodic seconds.

   Transitions from Joined State

   When the upstream (*,*,RP) state machine is in Joined state, the
   following events may trigger state transitions:

Top      Up      ToC       Page 65 
     JoinDesired(*,*,RP) becomes False
          The downstream state for (*,*,RP) has changed so no interface
          is in immediate_olist(*,*,RP), making JoinDesired(*,*,RP)
          become False.

          The upstream (*,*,RP) state machine transitions to NotJoined
          state.  Send Prune(*,*,RP) to the appropriate upstream
          neighbor, which is NBR(RPF_interface(RP), MRIB.next_hop(RP)).
          Cancel the Join Timer (JT).

     Join Timer Expires
          The Join Timer (JT) expires, indicating time to send a
          Join(*,*,RP)

          Send Join(*,*,RP) to the appropriate upstream neighbor, which
          is NBR(RPF_interface(RP), MRIB.next_hop(RP)).  Restart the
          Join Timer (JT) to expire after t_periodic seconds.

     See Join(*,*,RP) to MRIB.next_hop(RP)
          This event is only relevant if RPF_interface(RP) is a shared
          medium.  This router sees another router on RPF_interface(RP)
          send a Join(*,*,RP) to NBR(RPF_interface(RP),
          MRIB.next_hop(RP)).  This causes this router to suppress its
          own Join.

          The upstream (*,*,RP) state machine remains in Joined state.

          Let t_joinsuppress be the minimum of t_suppressed and the
          HoldTime from the Join/Prune message triggering this event.
          If the Join Timer is set to expire in less than t_joinsuppress
          seconds, reset it so that it expires after t_joinsuppress
          seconds.  If the Join Timer is set to expire in more than
          t_joinsuppress seconds, leave it unchanged.

     See Prune(*,*,RP) to MRIB.next_hop(RP)
          This event is only relevant if RPF_interface(RP) is a shared
          medium.  This router sees another router on RPF_interface(RP)
          send a Prune(*,*,RP) to NBR(RPF_interface(RP),
          MRIB.next_hop(RP)).  As this router is in Joined state, it
          must override the Prune after a short random interval.

          The upstream (*,*,RP) state machine remains in Joined state.
          If the Join Timer is set to expire in more than t_override
          seconds, reset it so that it expires after t_override seconds.
          If the Join Timer is set to expire in less than t_override
          seconds, leave it unchanged.

Top      Up      ToC       Page 66 
     NBR(RPF_interface(RP), MRIB.next_hop(RP)) changes
          A change in the MRIB routing base causes the next hop towards
          the RP to change.

          The upstream (*,*,RP) state machine remains in Joined state.
          Send Join(*,*,RP) to the new upstream neighbor, which is the
          new value of NBR(RPF_interface(RP), MRIB.next_hop(RP)).  Send
          Prune(*,*,RP) to the old upstream neighbor, which is the old
          value of NBR(RPF_interface(RP), MRIB.next_hop(RP)).  Set the
          Join Timer (JT) to expire after t_periodic seconds.

     MRIB.next_hop(RP) GenID changes
          The Generation ID of the router that is MRIB.next_hop(RP)
          changes.  This normally means that this neighbor has lost
          state, and so the state must be refreshed.

          The upstream (*,*,RP) state machine remains in Joined state.
          If the Join Timer is set to expire in more than t_override
          seconds, reset it so that it expires after t_override seconds.

4.5.6.  Sending (*,G) Join/Prune Messages

   The per-interface state machines for (*,G) hold join state from
   downstream PIM routers.  This state then determines whether a router
   needs to propagate a Join(*,G) upstream towards the RP.

   If a router wishes to propagate a Join(*,G) upstream, it must also
   watch for messages on its upstream interface from other routers on
   that subnet, and these may modify its behavior.  If it sees a
   Join(*,G) to the correct upstream neighbor, it should suppress its
   own Join(*,G).  If it sees a Prune(*,G) to the correct upstream
   neighbor, it should be prepared to override that prune by sending a
   Join(*,G) almost immediately.  Finally, if it sees the Generation ID
   (see Section 4.3) of the correct upstream neighbor change, it knows
   that the upstream neighbor has lost state, and it should be prepared
   to refresh the state by sending a Join(*,G) almost immediately.

   If a (*,G) Assert occurs on the upstream interface, and this changes
   this router's idea of the upstream neighbor, it should be prepared to
   ensure that the Assert winner is aware of downstream routers by
   sending a Join(*,G) almost immediately.

   In addition, if the MRIB changes to indicate that the next hop
   towards the RP has changed, and either the upstream interface changes
   or there is no Assert winner on the upstream interface, the router
   should prune off from the old next hop and join towards the new next
   hop.

Top      Up      ToC       Page 67 
   The upstream (*,G) state machine only contains two states:

   Not Joined
      The downstream state machines indicate that the router does not
      need to join the RP tree for this group.

   Joined
      The downstream state machines indicate that the router should join
      the RP tree for this group.

   In addition, one timer JT(*,G) is kept that is used to trigger the
   sending of a Join(*,G) to the upstream next hop towards the RP,
   RPF'(*,G).

         Figure 7: Upstream (*,G) state machine in tabular form

+-------------------++-------------------------------------------------+
|                   ||                      Event                      |
|  Prev State       ++------------------------+------------------------+
|                   ||   JoinDesired(*,G)     |    JoinDesired(*,G)    |
|                   ||   ->True               |    ->False             |
+-------------------++------------------------+------------------------+
|                   ||   -> J state           |    -                   |
|  NotJoined (NJ)   ||   Send Join(*,G);      |                        |
|                   ||   Set Join Timer to    |                        |
|                   ||   t_periodic           |                        |
+-------------------++------------------------+------------------------+
|  Joined (J)       ||   -                    |    -> NJ state         |
|                   ||                        |    Send Prune(*,G);    |
|                   ||                        |    Cancel Join Timer   |
+-------------------++------------------------+------------------------+

   In addition, we have the following transitions, which occur within
   the Joined state:

+----------------------------------------------------------------------+
|                        In Joined (J) State                           |
+----------------+-----------------+-----------------+-----------------+
|Timer Expires   | See Join(*,G)   | See Prune(*,G)  | RPF'(*,G)       |
|                | to RPF'(*,G)    | to RPF'(*,G)    | changes due to  |
|                |                 |                 | an Assert       |
+----------------+-----------------+-----------------+-----------------+
|Send            | Increase Join   | Decrease Join   | Decrease Join   |
|Join(*,G); Set  | Timer to        | Timer to        | Timer to        |
|Join Timer to   | t_joinsuppress  | t_override      | t_override      |
|t_periodic      |                 |                 |                 |
+----------------+-----------------+-----------------+-----------------+

Top      Up      ToC       Page 68 
+----------------------------------------------------------------------+
|                         In Joined (J) State                          |
+----------------------------------+-----------------------------------+
|    RPF'(*,G) changes not         |       RPF'(*,G) GenID changes     |
|    due to an Assert              |                                   |
+----------------------------------+-----------------------------------+
|    Send Join(*,G) to new         |       Decrease Join Timer to      |
|    next hop; Send                |       t_override                  |
|    Prune(*,G) to old next        |                                   |
|    hop; Set Join Timer to        |                                   |
|    t_periodic                    |                                   |
+----------------------------------+-----------------------------------+

   This state machine uses the following macro:

     bool JoinDesired(*,G) {
        if (immediate_olist(*,G) != NULL OR
            (JoinDesired(*,*,RP(G)) AND
             AssertWinner(*, G, RPF_interface(RP(G))) != NULL))
            return TRUE
        else
            return FALSE
     }

   JoinDesired(*,G) is true when the router has forwarding state that
   would cause it to forward traffic for G using shared tree state.
   Note that although JoinDesired is true, the router's sending of a
   Join(*,G) message may be suppressed by another router sending a
   Join(*,G) onto the upstream interface.

   Transitions from NotJoined State

   When the upstream (*,G) state machine is in NotJoined state, the
   following event may trigger a state transition:

     JoinDesired(*,G) becomes True
          The macro JoinDesired(*,G) becomes True, e.g., because the
          downstream state for (*,G) has changed so that at least one
          interface is in immediate_olist(*,G).

          The upstream (*,G) state machine transitions to Joined state.
          Send Join(*,G) to the appropriate upstream neighbor, which is
          RPF'(*,G).  Set the Join Timer (JT) to expire after t_periodic
          seconds.

Top      Up      ToC       Page 69 
   Transitions from Joined State

   When the upstream (*,G) state machine is in Joined state, the
   following events may trigger state transitions:

     JoinDesired(*,G) becomes False
          The macro JoinDesired(*,G) becomes False, e.g., because the
          downstream state for (*,G) has changed so no interface is in
          immediate_olist(*,G).

          The upstream (*,G) state machine transitions to NotJoined
          state.  Send Prune(*,G) to the appropriate upstream neighbor,
          which is RPF'(*,G).  Cancel the Join Timer (JT).

     Join Timer Expires
          The Join Timer (JT) expires, indicating time to send a
          Join(*,G)

          Send Join(*,G) to the appropriate upstream neighbor, which is
          RPF'(*,G).  Restart the Join Timer (JT) to expire after
          t_periodic seconds.

     See Join(*,G) to RPF'(*,G)
          This event is only relevant if RPF_interface(RP(G)) is a
          shared medium.  This router sees another router on
          RPF_interface(RP(G)) send a Join(*,G) to RPF'(*,G).  This
          causes this router to suppress its own Join.

          The upstream (*,G) state machine remains in Joined state.

          Let t_joinsuppress be the minimum of t_suppressed and the
          HoldTime from the Join/Prune message triggering this event.
          If the Join Timer is set to expire in less than t_joinsuppress
          seconds, reset it so that it expires after t_joinsuppress
          seconds.  If the Join Timer is set to expire in more than
          t_joinsuppress seconds, leave it unchanged.

     See Prune(*,G) to RPF'(*,G)
          This event is only relevant if RPF_interface(RP(G)) is a
          shared medium.  This router sees another router on
          RPF_interface(RP(G)) send a Prune(*,G) to RPF'(*,G).  As this
          router is in Joined state, it must override the Prune after a
          short random interval.

Top      Up      ToC       Page 70 
          The upstream (*,G) state machine remains in Joined state.  If
          the Join Timer is set to expire in more than t_override
          seconds, reset it so that it expires after t_override seconds.
          If the Join Timer is set to expire in less than t_override
          seconds, leave it unchanged.

     RPF'(*,G) changes due to an Assert
          The current next hop towards the RP changes due to an
          Assert(*,G) on the RPF_interface(RP(G)).

          The upstream (*,G) state machine remains in Joined state.  If
          the Join Timer is set to expire in more than t_override
          seconds, reset it so that it expires after t_override seconds.
          If the Join Timer is set to expire in less than t_override
          seconds, leave it unchanged.

     RPF'(*,G) changes not due to an Assert
          An event occurred that caused the next hop towards the RP for
          G to change.  This may be caused by a change in the MRIB
          routing database or the group-to-RP mapping.  Note that this
          transition does not occur if an Assert is active and the
          upstream interface does not change.

          The upstream (*,G) state machine remains in Joined state.
          Send Join(*,G) to the new upstream neighbor, which is the new
          value of RPF'(*,G).  Send Prune(*,G) to the old upstream
          neighbor, which is the old value of RPF'(*,G).  Use the new
          value of RP(G) in the Prune(*,G) message or all zeros if RP(G)
          becomes unknown (old value of RP(G) may be used instead to
          improve behavior in routers implementing older versions of
          this spec).  Set the Join Timer (JT) to expire after
          t_periodic seconds.

     RPF'(*,G) GenID changes
          The Generation ID of the router that is RPF'(*,G) changes.
          This normally means that this neighbor has lost state, and so
          the state must be refreshed.

          The upstream (*,G) state machine remains in Joined state.  If
          the Join Timer is set to expire in more than t_override
          seconds, reset it so that it expires after t_override seconds.

Top      Up      ToC       Page 71 
4.5.7.  Sending (S,G) Join/Prune Messages

   The per-interface state machines for (S,G) hold join state from
   downstream PIM routers.  This state then determines whether a router
   needs to propagate a Join(S,G) upstream towards the source.

   If a router wishes to propagate a Join(S,G) upstream, it must also
   watch for messages on its upstream interface from other routers on
   that subnet, and these may modify its behavior.  If it sees a
   Join(S,G) to the correct upstream neighbor, it should suppress its
   own Join(S,G).  If it sees a Prune(S,G), Prune(S,G,rpt), or
   Prune(*,G) to the correct upstream neighbor towards S, it should be
   prepared to override that prune by scheduling a Join(S,G) to be sent
   almost immediately.  Finally, if it sees the Generation ID of its
   upstream neighbor change, it knows that the upstream neighbor has
   lost state, and it should refresh the state by scheduling a Join(S,G)
   to be sent almost immediately.

   If a (S,G) Assert occurs on the upstream interface, and this changes
   the this router's idea of the upstream neighbor, it should be
   prepared to ensure that the Assert winner is aware of downstream
   routers by scheduling a Join(S,G) to be sent almost immediately.

   In addition, if MRIB changes cause the next hop towards the source to
   change, and either the upstream interface changes or there is no
   Assert winner on the upstream interface, the router should send a
   prune to the old next hop and a join to the new next hop.

   The upstream (S,G) state machine only contains two states:

   Not Joined
      The downstream state machines and local membership information do
      not indicate that the router needs to join the shortest-path tree
      for this (S,G).

   Joined
      The downstream state machines and local membership information
      indicate that the router should join the shortest-path tree for
      this (S,G).

   In addition, one timer JT(S,G) is kept that is used to trigger the
   sending of a Join(S,G) to the upstream next hop towards S, RPF'(S,G).

Top      Up      ToC       Page 72 
         Figure 8: Upstream (S,G) state machine in tabular form

+-------------------+--------------------------------------------------+
|                   |                      Event                       |
|  Prev State       +-------------------------+------------------------+
|                   |   JoinDesired(S,G)      |   JoinDesired(S,G)     |
|                   |   ->True                |   ->False              |
+-------------------+-------------------------+------------------------+
|  NotJoined (NJ)   |   -> J state            |   -                    |
|                   |   Send Join(S,G);       |                        |
|                   |   Set Join Timer to     |                        |
|                   |   t_periodic            |                        |
+-------------------+-------------------------+------------------------+
|  Joined (J)       |   -                     |   -> NJ state          |
|                   |                         |   Send Prune(S,G);     |
|                   |                         |   Set SPTbit(S,G) to   |
|                   |                         |   FALSE; Cancel Join   |
|                   |                         |   Timer                |
+-------------------+-------------------------+------------------------+

   In addition, we have the following transitions, which occur within
   the Joined state:

+----------------------------------------------------------------------+
|                         In Joined (J) State                          |
+-----------------+-----------------+-----------------+----------------+
| Timer Expires   | See Join(S,G)   | See Prune(S,G)  | See Prune      |
|                 | to RPF'(S,G)    | to RPF'(S,G)    | (S,G,rpt) to   |
|                 |                 |                 | RPF'(S,G)      |
+-----------------+-----------------+-----------------+----------------+
| Send            | Increase Join   | Decrease Join   | Decrease Join  |
| Join(S,G); Set  | Timer to        | Timer to        | Timer to       |
| Join Timer to   | t_joinsuppress  | t_override      | t_override     |
| t_periodic      |                 |                 |                |
+-----------------+-----------------+-----------------+----------------+

Top      Up      ToC       Page 73 
+----------------------------------------------------------------------+
|                        In Joined (J) State                           |
+-----------------+-----------------+----------------+-----------------+
| See Prune(*,G)  | RPF'(S,G)       | RPF'(S,G)      | RPF'(S,G)       |
| to RPF'(S,G)    | changes not     | GenID changes  | changes due to  |
|                 | due to an       |                | an Assert       |
|                 | Assert          |                |                 |
+-----------------+-----------------+----------------+-----------------+
| Decrease Join   | Send Join(S,G)  | Decrease Join  | Decrease Join   |
| Timer to        | to new next     | Timer to       | Timer to        |
| t_override      | hop; Send       | t_override     | t_override      |
|                 | Prune(S,G) to   |                |                 |
|                 | old next hop;   |                |                 |
|                 | Set Join Timer  |                |                 |
|                 | to t_periodic   |                |                 |
+-----------------+-----------------+----------------+-----------------+

   This state machine uses the following macro:

     bool JoinDesired(S,G) {
         return( immediate_olist(S,G) != NULL
                 OR ( KeepaliveTimer(S,G) is running
                      AND inherited_olist(S,G) != NULL ) )
     }

   JoinDesired(S,G) is true when the router has forwarding state that
   would cause it to forward traffic for G using source tree state.  The
   source tree state can be as a result of either active source-specific
   join state, or the (S,G) Keepalive Timer and active non-source-
   specific state.  Note that although JoinDesired is true, the router's
   sending of a Join(S,G) message may be suppressed by another router
   sending a Join(S,G) onto the upstream interface.

   Transitions from NotJoined State

   When the upstream (S,G) state machine is in NotJoined state, the
   following event may trigger a state transition:

     JoinDesired(S,G) becomes True
          The macro JoinDesired(S,G) becomes True, e.g., because the
          downstream state for (S,G) has changed so that at least one
          interface is in inherited_olist(S,G).

          The upstream (S,G) state machine transitions to Joined state.
          Send Join(S,G) to the appropriate upstream neighbor, which is
          RPF'(S,G).  Set the Join Timer (JT) to expire after t_periodic
          seconds.

Top      Up      ToC       Page 74 
   Transitions from Joined State

   When the upstream (S,G) state machine is in Joined state, the
   following events may trigger state transitions:

     JoinDesired(S,G) becomes False
          The macro JoinDesired(S,G) becomes False, e.g., because the
          downstream state for (S,G) has changed so no interface is in
          inherited_olist(S,G).

          The upstream (S,G) state machine transitions to NotJoined
          state.  Send Prune(S,G) to the appropriate upstream neighbor,
          which is RPF'(S,G).  Cancel the Join Timer (JT), and set
          SPTbit(S,G) to FALSE.

     Join Timer Expires
          The Join Timer (JT) expires, indicating time to send a
          Join(S,G)

          Send Join(S,G) to the appropriate upstream neighbor, which is
          RPF'(S,G).  Restart the Join Timer (JT) to expire after
          t_periodic seconds.

     See Join(S,G) to RPF'(S,G)
          This event is only relevant if RPF_interface(S) is a shared
          medium.  This router sees another router on RPF_interface(S)
          send a Join(S,G) to RPF'(S,G).  This causes this router to
          suppress its own Join.

          The upstream (S,G) state machine remains in Joined state.

          Let t_joinsuppress be the minimum of t_suppressed and the
          HoldTime from the Join/Prune message triggering this event.

          If the Join Timer is set to expire in less than t_joinsuppress
          seconds, reset it so that it expires after t_joinsuppress
          seconds.  If the Join Timer is set to expire in more than
          t_joinsuppress seconds, leave it unchanged.

     See Prune(S,G) to RPF'(S,G)
          This event is only relevant if RPF_interface(S) is a shared
          medium.  This router sees another router on RPF_interface(S)
          send a Prune(S,G) to RPF'(S,G).  As this router is in Joined
          state, it must override the Prune after a short random
          interval.

Top      Up      ToC       Page 75 
          The upstream (S,G) state machine remains in Joined state.  If
          the Join Timer is set to expire in more than t_override
          seconds, reset it so that it expires after t_override seconds.

     See Prune(S,G,rpt) to RPF'(S,G)
          This event is only relevant if RPF_interface(S) is a shared
          medium.  This router sees another router on RPF_interface(S)
          send a Prune(S,G,rpt) to RPF'(S,G).  If the upstream router is
          an RFC-2362-compliant PIM router, then the Prune(S,G,rpt) will
          cause it to stop forwarding.  For backwards compatibility,
          this router should override the prune so that forwarding
          continues.

          The upstream (S,G) state machine remains in Joined state.  If
          the Join Timer is set to expire in more than t_override
          seconds, reset it so that it expires after t_override seconds.

     See Prune(*,G) to RPF'(S,G)
          This event is only relevant if RPF_interface(S) is a shared
          medium.  This router sees another router on RPF_interface(S)
          send a Prune(*,G) to RPF'(S,G).  If the upstream router is an
          RFC-2362-compliant PIM router, then the Prune(*,G) will cause
          it to stop forwarding.  For backwards compatibility, this
          router should override the prune so that forwarding continues.

          The upstream (S,G) state machine remains in Joined state.  If
          the Join Timer is set to expire in more than t_override
          seconds, reset it so that it expires after t_override seconds.

     RPF'(S,G) changes due to an Assert
          The current next hop towards S changes due to an Assert(S,G)
          on the RPF_interface(S).

          The upstream (S,G) state machine remains in Joined state.  If
          the Join Timer is set to expire in more than t_override
          seconds, reset it so that it expires after t_override seconds.
          If the Join Timer is set to expire in less than t_override
          seconds, leave it unchanged.

     RPF'(S,G) changes not due to an Assert
          An event occurred that caused the next hop towards S to
          change.  Note that this transition does not occur if an Assert
          is active and the upstream interface does not change.

Top      Up      ToC       Page 76 
          The upstream (S,G) state machine remains in Joined state.
          Send Join(S,G) to the new upstream neighbor, which is the new
          value of RPF'(S,G).  Send Prune(S,G) to the old upstream
          neighbor, which is the old value of RPF'(S,G).  Set the Join
          Timer (JT) to expire after t_periodic seconds.

     RPF'(S,G) GenID changes
          The Generation ID of the router that is RPF'(S,G) changes.
          This normally means that this neighbor has lost state, and so
          the state must be refreshed.

          The upstream (S,G) state machine remains in Joined state.  If
          the Join Timer is set to expire in more than t_override
          seconds, reset it so that it expires after t_override seconds.

4.5.8.  (S,G,rpt) Periodic Messages

   (S,G,rpt) Joins and Prunes are (S,G) Joins or Prunes sent on the RP
   tree with the RPT bit set, either to modify the results of (*,G)
   Joins, or to override the behavior of other upstream LAN peers.  The
   next section describes the rules for sending triggered messages.
   This section describes the rules for including a Prune(S,G,rpt)
   message with a Join(*,G).

   When a router is going to send a Join(*,G), it should use the
   following pseudocode, for each (S,G) for which it has state, to
   decide whether to include a Prune(S,G,rpt) in the compound Join/Prune
   message:

     if( SPTbit(S,G) == TRUE ) {
         # Note: If receiving (S,G) on the SPT, we only prune off the
         # shared tree if the RPF neighbors differ.
          if( RPF'(*,G) != RPF'(S,G) ) {
              add Prune(S,G,rpt) to compound message
          }
     } else if ( inherited_olist(S,G,rpt) == NULL ) {
       # Note: all (*,G) olist interfaces received RPT prunes for (S,G).
       add Prune(S,G,rpt) to compound message
     } else if ( RPF'(*,G) != RPF'(S,G,rpt) {
       # Note: we joined the shared tree, but there was an (S,G) assert
       # and the source tree RPF neighbor is different.
       add Prune(S,G,rpt) to compound message
     }

   Note that Join(S,G,rpt) is normally sent not as a periodic message,
   but only as a triggered message.

Top      Up      ToC       Page 77 
4.5.9.  State Machine for (S,G,rpt) Triggered Messages

   The state machine for (S,G,rpt) triggered messages is required per-
   (S,G) when there is (*,G) or (*,*,RP) join state at a router, and the
   router or any of its upstream LAN peers wishes to prune S off the RP
   tree.

   There are three states in the state machine.  One of the states is
   when there is neither (*,G) nor (*,*,RP(G)) join state at this
   router.  If there is (*,G) or (*,*,RP(G)) join state at the router,
   then the state machine must be at one of the other two states.  The
   three states are:

   Pruned(S,G,rpt)
      (*,G) or (*,*,RP(G)) Joined, but (S,G,rpt) pruned

   NotPruned(S,G,rpt)
      (*,G) or (*,*,RP(G)) Joined, and (S,G,rpt) not pruned

   RPTNotJoined(G)
      neither (*,G) nor (*,*,RP(G)) has been joined.

   In addition, there is an (S,G,rpt) Override Timer, OT(S,G,rpt), which
   is used to delay triggered Join(S,G,rpt) messages to prevent
   implosions of triggered messages.

Top      Up      ToC       Page 78 
   Figure 9: Upstream (S,G,rpt) state machine for triggered messages
                            in tabular form

+------------++--------------------------------------------------------+
|            ||                           Event                        |
|            ++--------------+--------------+-------------+------------+
|Prev State  || PruneDesired | PruneDesired | RPTJoin     | inherited_ |
|            || (S,G,rpt)    | (S,G,rpt)    | Desired(G)  | olist      |
|            || ->True       | ->False      | ->False     | (S,G,rpt)  |
|            ||              |              |             | ->non-NULL |
+------------++--------------+--------------+-------------+------------+
|RPTNotJoined|| -> P state   | -            | -           | -> NP state|
|(G) (NJ)    ||              |              |             |            |
+------------++--------------+--------------+-------------+------------+
|Pruned      || -            | -> NP state  | -> NJ state | -          |
|(S,G,rpt)   ||              | Send Join    |             |            |
|(P)         ||              | (S,G,rpt)    |             |            |
+------------++--------------+--------------+-------------+------------+
|NotPruned   || -> P state   | -            | -> NJ state | -          |
|(S,G,rpt)   || Send Prune   |              | Cancel OT   |            |
|(NP)        || (S,G,rpt);   |              |             |            |
|            || Cancel OT    |              |             |            |
+------------++--------------+--------------+-------------+------------+

   Additionally, we have the following transitions within the
   NotPruned(S,G,rpt) state, which are all used for prune override
   behavior.

+----------------------------------------------------------------------+
|                    In NotPruned(S,G,rpt) State                       |
+----------+--------------+--------------+--------------+--------------+
|Override  | See Prune    | See Join     | See Prune    | RPF'         |
|Timer     | (S,G,rpt) to | (S,G,rpt) to | (S,G) to     | (S,G,rpt) -> |
|expires   | RPF'         | RPF'         | RPF'         | RPF' (*,G)   |
|          | (S,G,rpt)    | (S,G,rpt)    | (S,G,rpt)    |              |
+----------+--------------+--------------+--------------+--------------+
|Send Join | OT = min(OT, | Cancel OT    | OT = min(OT, | OT = min(OT, |
|(S,G,rpt);| t_override)  |              | t_override)  | t_override)  |
|Leave OT  |              |              |              |              |
|unset     |              |              |              |              |
+----------+--------------+--------------+--------------+--------------+

   Note that the min function in the above state machine considers a
   non-running timer to have an infinite value (e.g., min(not-running,
   t_override) = t_override).

Top      Up      ToC       Page 79 
   This state machine uses the following macros:

     bool RPTJoinDesired(G) {
       return (JoinDesired(*,G) OR JoinDesired(*,*,RP(G)))
     }

   RPTJoinDesired(G) is true when the router has forwarding state that
   would cause it to forward traffic for G using either (*,G) or
   (*,*,RP) shared tree state.

     bool PruneDesired(S,G,rpt) {
          return ( RPTJoinDesired(G) AND
                   ( inherited_olist(S,G,rpt) == NULL
                     OR (SPTbit(S,G)==TRUE
                         AND (RPF'(*,G) != RPF'(S,G)) )))
     }

   PruneDesired(S,G,rpt) can only be true if RPTJoinDesired(G) is true.
   If RPTJoinDesired(G) is true, then PruneDesired(S,G,rpt) is true
   either if there are no outgoing interfaces that S would be forwarded
   on, or if the router has active (S,G) forwarding state but RPF'(*,G)
   != RPF'(S,G).

   The state machine contains the following transition events:

   See Join(S,G,rpt) to RPF'(S,G,rpt)
      This event is only relevant in the "Not Pruned" state.

      The router sees a Join(S,G,rpt) from someone else to
      RPF'(S,G,rpt), which is the correct upstream neighbor.  If we're
      in "NotPruned" state and the (S,G,rpt) Override Timer is running,
      then this is because we have been triggered to send our own
      Join(S,G,rpt) to RPF'(S,G,rpt).  Someone else beat us to it, so
      there's no need to send our own Join.

      The action is to cancel the Override Timer.

   See Prune(S,G,rpt) to RPF'(S,G,rpt)
      This event is only relevant in the "NotPruned" state.

      The router sees a Prune(S,G,rpt) from someone else to
      RPF'(S,G,rpt), which is the correct upstream neighbor.  If we're
      in the "NotPruned" state, then we want to continue to receive
      traffic from S destined for G, and that traffic is being supplied
      by RPF'(S,G,rpt).  Thus, we need to override the Prune.

Top      Up      ToC       Page 80 
      The action is to set the (S,G,rpt) Override Timer to the
      randomized prune-override interval, t_override.  However, if the
      Override Timer is already running, we only set the timer if doing
      so would set it to a lower value.  At the end of this interval, if
      noone else has sent a Join, then we will do so.

   See Prune(S,G) to RPF'(S,G,rpt)
      This event is only relevant in the "NotPruned" state.

      This transition and action are the same as the above transition
      and action, except that the Prune does not have the RPT bit set.
      This transition is necessary to be compatible with routers
      implemented from RFC2362 that don't maintain separate (S,G) and
      (S,G,rpt) state.

   The (S,G,rpt) prune Override Timer expires
      This event is only relevant in the "NotPruned" state.

      When the Override Timer expires, we must send a Join(S,G,rpt) to
      RPF'(S,G,rpt) to override the Prune message that caused the timer
      to be running.  We only send this if RPF'(S,G,rpt) equals
      RPF'(*,G); if this were not the case, then the Join might be sent
      to a router that does not have (*,G) or (*,*,RP(G)) Join state,
      and so the behavior would not be well defined.  If RPF'(S,G,rpt)
      is not the same as RPF'(*,G), then it may stop forwarding S.
      However, if this happens, then the router will send an
      AssertCancel(S,G), which would then cause RPF'(S,G,rpt) to become
      equal to RPF'(*,G) (see below).

   RPF'(S,G,rpt) changes to become equal to RPF'(*,G)
      This event is only relevant in the "NotPruned" state.

      RPF'(S,G,rpt) can only be different from RPF'(*,G) if an (S,G)
      Assert has happened, which means that traffic from S is arriving
      on the SPT, and so Prune(S,G,rpt) will have been sent to
      RPF'(*,G).  When RPF'(S,G,rpt) changes to become equal to
      RPF'(*,G), we need to trigger a Join(S,G,rpt) to RPF'(*,G) to
      cause that router to start forwarding S again.

      The action is to set the (S,G,rpt) Override Timer to the
      randomized prune-override interval t_override.  However, if the
      timer is already running, we only set the timer if doing so would
      set it to a lower value.  At the end of this interval, if noone
      else has sent a Join, then we will do so.

   PruneDesired(S,G,rpt)->TRUE
      See macro above.  This event is relevant in the "NotPruned" and
      "RPTNotJoined(G)" states.

Top      Up      ToC       Page 81 
      The router wishes to receive traffic for G, but does not wish to
      receive traffic from S destined for G.  This causes the router to
      transition into the Pruned state.

      If the router was previously in NotPruned state, then the action
      is to send a Prune(S,G,rpt) to RPF'(S,G,rpt), and to cancel the
      Override Timer.  If the router was previously in RPTNotJoined(G)
      state, then there is no need to trigger an action in this state
      machine because sending a Prune(S,G,rpt) is handled by the rules
      for sending the Join(*,G) or Join(*,*,RP).

   PruneDesired(S,G,rpt)->FALSE
      See macro above.  This transition is only relevant in the "Pruned"
      state.

      If the router is in the Pruned(S,G,rpt) state, and
      PruneDesired(S,G,rpt) changes to FALSE, this could be because the
      router no longer has RPTJoinDesired(G) true, or it now wishes to
      receive traffic from S again.  If it is the former, then this
      transition should not happen, but instead the
      "RPTJoinDesired(G)->FALSE" transition should happen.  Thus, this
      transition should be interpreted as "PruneDesired(S,G,rpt)->FALSE
      AND RPTJoinDesired(G)==TRUE".

      The action is to send a Join(S,G,rpt) to RPF'(S,G,rpt).

   RPTJoinDesired(G)->FALSE
      This event is relevant in the "Pruned" and "NotPruned" states.

      The router no longer wishes to receive any traffic destined for G
      on the RP Tree.  This causes a transition to the RPTNotJoined(G)
      state, and the Override Timer is canceled if it was running.  Any
      further actions are handled by the appropriate upstream state
      machine for (*,G) or (*,*,RP).

   inherited_olist(S,G,rpt) becomes non-NULL
      This transition is only relevant in the RPTNotJoined(G) state.

      The router has joined the RP tree (handled by the (*,G) or
      (*,*,RP) upstream state machine as appropriate) and wants to
      receive traffic from S.  This does not trigger any events in this
      state machine, but causes a transition to the NotPruned(S,G,rpt)
      state.

Top      Up      ToC       Page 82 
4.5.10.  Background: (*,*,RP) and (S,G,rpt) Interaction

   In Sections 4.5.8 and 4.5.9, the mechanisms for sending periodic and
   triggered (S,G,rpt) messages are described.  The astute reader will
   note that periodic Prune(S,G,rpt) messages are only sent in PIM
   Join/Prune messages containing a Join(*,G), whereas it is possible
   for a triggered Prune(S,G,rpt) message to be sent when the router has
   no (*,G) join state.  This may seem like a contradiction, but in fact
   it is intentional and is a side effect of not optimizing (*,*,RP)
   behavior.

   We first note that reception of a Join(*,*,RP) by itself does not
   cancel (S,G,rpt) prune state on that interface, whereas receiving a
   Join(*,G) by itself does cancel (S,G,rpt) prune state on that
   interface.  Similarly, reception of a Prune(*,G) on an interface with
   (*,*,RP) join state does not by itself prevent forwarding of G using
   the (*,*,RP) state; this is because a Prune(*,G) only serves to
   cancel (*,G) join state.  Conceptually (*,*,RP) state functions
   "above" the normal (*,G) and (S,G) mechanisms, and so neither
   Join(*,*,RP) nor Prune(*,*,RP) messages affect any other state.

   The upshot of this is that to prevent forwarding (S,G) on (*,*,RP)
   state, a Prune(S,G,rpt) must be used.

   We also note that for historical reasons there is no Assert(*,*,RP)
   message, so any forwarding contention is resolved using Assert(*,G)
   messages.

   We now need to consider the interaction between (*,*,RP) state and
   (*,G) state.  If there is a need for an assert between two upstream
   routers on a LAN, we need to ensure that the correct thing happens
   for all combinations of (*,*,RP) and (*,G) forwarding state.  As
   there is no Assert(*,*,RP) message, no router can tell whether the
   assert winner has (*,*,RP) state or (*,G) state.  Thus, a downstream
   router has to treat the two the same and send its periodic
   Prune(S,G,rpt) messages to RPF'(*,G).

   To avoid needing to specify all the complex override rules between
   (*,*,RP), (*,G), and (S,G,rpt), we simply require that to prune (S,G)
   off the (*,*,RP) tree, a Join(*,G) must also be sent.

   If a router is receiving on (*,*,RP) state and has not yet had (*,G)
   state instantiated, it may still need to send a triggered
   Join(S,G,rpt) to override a Prune(S,G,rpt) that it sees directed to
   RPF'(*,G) on its upstream interface.  Hence, triggered (S,G,rpt)
   messages may be sent when JoinDesired(*,G) is false but
   JoinDesired(*,*,RP) is true.

Top      Up      ToC       Page 83 
   Finally, we note that there is an unoptimized case when the upstream
   router on a LAN already has (*,G) join and (S,G,rpt) prune state
   caused by an existing downstream router.  If at this time a new
   Join(*,*,RP) is sent to the upstream router from a different
   downstream router, this will not override the (S,G,rpt) prune state
   at the upstream router.  The override will not occur until the next
   time the original downstream router resends its Prune(S,G,rpt).  This
   case was not considered worth optimizing, as (*,*,RP) state is
   generally very long lived, and so any minor delays in getting traffic
   to a new PMBR seem unimportant.

4.6.  PIM Assert Messages

   Where multiple PIM routers peer over a shared LAN, it is possible for
   more than one upstream router to have valid forwarding state for a
   packet, which can lead to packet duplication (see Section 3.6).  PIM
   does not attempt to prevent this from occurring.  Instead, it detects
   when this has happened and elects a single forwarder amongst the
   upstream routers to prevent further duplication.  This election is
   performed using PIM Assert messages.  Assert messages are also
   received by downstream routers on the LAN, and these cause subsequent
   Join/Prune messages to be sent to the upstream router that won the
   Assert.

   In general, a PIM Assert message should only be accepted for
   processing if it comes from a known PIM neighbor.  A PIM router hears
   about PIM neighbors through PIM Hello messages.  If a router receives
   an Assert message from a particular IP source address and it has not
   seen a PIM Hello message from that source address, then the Assert
   message SHOULD be discarded without further processing.  In addition,
   if the Hello message from a neighbor was authenticated using the
   IPsec Authentication Header (AH) (see Section 6.3), then all Assert
   messages from that neighbor MUST also be authenticated using IPsec
   AH.

   We note that some older PIM implementations incorrectly fail to send
   Hello messages on point-to-point interfaces, so we also RECOMMEND
   that a configuration option be provided to allow interoperation with
   such older routers, but that this configuration option SHOULD NOT be
   enabled by default.

4.6.1.  (S,G) Assert Message State Machine

   The (S,G) Assert state machine for interface I is shown in Figure 10.
   There are three states:

   NoInfo (NI)
      This router has no (S,G) assert state on interface I.

Top      Up      ToC       Page 84 
   I am Assert Winner (W)
      This router has won an (S,G) assert on interface I.  It is now
      responsible for forwarding traffic from S destined for G out of
      interface I.  Irrespective of whether it is the DR for I, while a
      router is the assert winner, it is also responsible for forwarding
      traffic onto I on behalf of local hosts on I that have made
      membership requests that specifically refer to S (and G).

   I am Assert Loser (L)
      This router has lost an (S,G) assert on interface I.  It must not
      forward packets from S destined for G onto interface I.  If it is
      the DR on I, it is no longer responsible for forwarding traffic
      onto I to satisfy local hosts with membership requests that
      specifically refer to S and G.

   In addition, there is also an Assert Timer (AT) that is used to time
   out asserts on the assert losers and to resend asserts on the assert
   winner.

  Figure 10: Per-interface (S,G) Assert State machine in tabular form

+----------------------------------------------------------------------+
|                         In NoInfo (NI) State                         |
+---------------+-------------------+------------------+---------------+
| Receive       |  Receive Assert   |  Data arrives    |  Receive      |
| Inferior      |  with RPTbit      |  from S to G on  |  Acceptable   |
| Assert with   |  set and          |  I and           |  Assert with  |
| RPTbit clear  |  CouldAssert      |  CouldAssert     |  RPTbit clear |
| and           |  (S,G,I)          |  (S,G,I)         |  and AssTrDes |
| CouldAssert   |                   |                  |  (S,G,I)      |
| (S,G,I)       |                   |                  |               |
+---------------+-------------------+------------------+---------------+
| -> W state    |  -> W state       |  -> W state      |  -> L state   |
| [Actions A1]  |  [Actions A1]     |  [Actions A1]    |  [Actions A6] |
+---------------+-------------------+------------------+---------------+

+----------------------------------------------------------------------+
|                   In I Am Assert Winner (W) State                    |
+----------------+------------------+-----------------+----------------+
| Assert Timer   |   Receive        |  Receive        |  CouldAssert   |
| Expires        |   Inferior       |  Preferred      |  (S,G,I) ->    |
|                |   Assert         |  Assert         |  FALSE         |
+----------------+------------------+-----------------+----------------+
| -> W state     |   -> W state     |  -> L state     |  -> NI state   |
| [Actions A3]   |   [Actions A3]   |  [Actions A2]   |  [Actions A4]  |
+----------------+------------------+-----------------+----------------+

Top      Up      ToC       Page 85 
+---------------------------------------------------------------------+
|                   In I Am Assert Loser (L) State                    |
+-------------+-------------+-------------+-------------+-------------+
|Receive      |Receive      |Receive      |Assert Timer |Current      |
|Preferred    |Acceptable   |Inferior     |Expires      |Winner's     |
|Assert       |Assert with  |Assert or    |             |GenID        |
|             |RPTbit clear |Assert       |             |Changes or   |
|             |from Current |Cancel from  |             |NLT Expires  |
|             |Winner       |Current      |             |             |
|             |             |Winner       |             |             |
+-------------+-------------+-------------+-------------+-------------+
|-> L state   |-> L state   |-> NI state  |-> NI state  |-> NI state  |
|[Actions A2] |[Actions A2] |[Actions A5] |[Actions A5] |[Actions A5] |
+-------------+-------------+-------------+-------------+-------------+

+----------------------------------------------------------------------+
|                    In I Am Assert Loser (L) State                    |
+----------------+-----------------+------------------+----------------+
| AssTrDes       |  my_metric ->   |  RPF_interface   |  Receive       |
| (S,G,I) ->     |  better than    |  (S) stops       |  Join(S,G) on  |
| FALSE          |  winner's       |  being I         |  interface I   |
|                |  metric         |                  |                |
+----------------+-----------------+------------------+----------------+
| -> NI state    |  -> NI state    |  -> NI state     |  -> NI State   |
| [Actions A5]   |  [Actions A5]   |  [Actions A5]    |  [Actions A5]  |
+----------------+-----------------+------------------+----------------+

   Note that for reasons of compactness, "AssTrDes(S,G,I)" is used in
   the state machine table to refer to AssertTrackingDesired(S,G,I).

   Terminology:

      A "preferred assert" is one with a better metric than the current
      winner.

      An "acceptable assert" is one that has a better metric than
      my_assert_metric(S,G,I).  An assert is never considered acceptable
      if its metric is infinite.

      An "inferior assert" is one with a worse metric than
      my_assert_metric(S,G,I).  An assert is never considered inferior
      if my_assert_metric(S,G,I) is infinite.

Top      Up      ToC       Page 86 
   The state machine uses the following macros:

CouldAssert(S,G,I) =
     SPTbit(S,G)==TRUE
     AND (RPF_interface(S) != I)
     AND (I in ( ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) )
                 (+) ( pim_include(*,G) (-) pim_exclude(S,G) )
                 (-) lost_assert(*,G)
                 (+) joins(S,G) (+) pim_include(S,G) ) )

   CouldAssert(S,G,I) is true for downstream interfaces that would be in
   the inherited_olist(S,G) if (S,G) assert information was not taken
   into account.

   AssertTrackingDesired(S,G,I) =
        (I in ( ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) )
                (+) ( pim_include(*,G) (-) pim_exclude(S,G) )
                (-) lost_assert(*,G)
                (+) joins(S,G) ) )
        OR (local_receiver_include(S,G,I) == TRUE
            AND (I_am_DR(I) OR (AssertWinner(S,G,I) == me)))
        OR ((RPF_interface(S) == I) AND (JoinDesired(S,G) == TRUE))
        OR ((RPF_interface(RP(G)) == I) AND (JoinDesired(*,G) == TRUE)
            AND (SPTbit(S,G) == FALSE))

   AssertTrackingDesired(S,G,I) is true on any interface in which an
   (S,G) assert might affect our behavior.

   The first three lines of AssertTrackingDesired account for (*,G) join
   and local membership information received on I that might cause the
   router to be interested in asserts on I.

   The 4th line accounts for (S,G) join information received on I that
   might cause the router to be interested in asserts on I.

   The 5th and 6th lines account for (S,G) local membership information
   on I.  Note that we can't use the pim_include(S,G) macro since it
   uses lost_assert(S,G,I) and would result in the router forgetting
   that it lost an assert if the only reason it was interested was local
   membership.  The AssertWinner(S,G,I) check forces an assert winner to
   keep on being responsible for forwarding as long as local receivers
   are present.  Removing this check would make the assert winner give
   up forwarding as soon as the information that originally caused it to
   forward went away, and the task of forwarding for local receivers
   would revert back to the DR.

Top      Up      ToC       Page 87 
   The last three lines account for the fact that a router must keep
   track of assert information on upstream interfaces in order to send
   joins and prunes to the proper neighbor.

   Transitions from NoInfo State

   When in NoInfo state, the following events may trigger transitions:

     Receive Inferior Assert with RPTbit cleared AND
          CouldAssert(S,G,I)==TRUE
          An assert is received for (S,G) with the RPT bit cleared that
          is inferior to our own assert metric.  The RPT bit cleared
          indicates that the sender of the assert had (S,G) forwarding
          state on this interface.  If the assert is inferior to our
          metric, then we must also have (S,G) forwarding state (i.e.,
          CouldAssert(S,G,I)==TRUE) as (S,G) asserts beat (*,G) asserts,
          and so we should be the assert winner.  We transition to the
          "I am Assert Winner" state and perform Actions A1 (below).

     Receive Assert with RPTbit set AND CouldAssert(S,G,I)==TRUE
          An assert is received for (S,G) on I with the RPT bit set
          (it's a (*,G) assert).  CouldAssert(S,G,I) is TRUE only if we
          have (S,G) forwarding state on this interface, so we should be
          the assert winner.  We transition to the "I am Assert Winner"
          state and perform Actions A1 (below).

     An (S,G) data packet arrives on interface I, AND
          CouldAssert(S,G,I)==TRUE
          An (S,G) data packet arrived on an downstream interface that
          is in our (S,G) outgoing interface list.  We optimistically
          assume that we will be the assert winner for this (S,G), and
          so we transition to the "I am Assert Winner" state and perform
          Actions A1 (below), which will initiate the assert negotiation
          for (S,G).

     Receive Acceptable Assert with RPT bit clear AND
          AssertTrackingDesired(S,G,I)==TRUE
          We're interested in (S,G) Asserts, either because I is a
          downstream interface for which we have (S,G) or (*,G)
          forwarding state, or because I is the upstream interface for S
          and we have (S,G) forwarding state.  The received assert has a
          better metric than our own, so we do not win the Assert.  We
          transition to "I am Assert Loser" and perform Actions A6
          (below).

Top      Up      ToC       Page 88 
   Transitions from "I am Assert Winner" State

   When in "I am Assert Winner" state, the following events trigger
   transitions:

     Assert Timer Expires
          The (S,G) Assert Timer expires.  As we're in the Winner state,
          we must still have (S,G) forwarding state that is actively
          being kept alive.  We resend the (S,G) Assert and restart the
          Assert Timer (Actions A3 below).  Note that the assert
          winner's Assert Timer is engineered to expire shortly before
          timers on assert losers; this prevents unnecessary thrashing
          of the forwarder and periodic flooding of duplicate packets.

     Receive Inferior Assert
          We receive an (S,G) assert or (*,G) assert mentioning S that
          has a worse metric than our own.  Whoever sent the assert is
          in error, and so we resend an (S,G) Assert and restart the
          Assert Timer (Actions A3 below).

     Receive Preferred Assert
          We receive an (S,G) assert that has a better metric than our
          own.  We transition to "I am Assert Loser" state and perform
          Actions A2 (below).  Note that this may affect the value of
          JoinDesired(S,G) and PruneDesired(S,G,rpt), which could cause
          transitions in the upstream (S,G) or (S,G,rpt) state machines.

     CouldAssert(S,G,I) -> FALSE
          Our (S,G) forwarding state or RPF interface changed so as to
          make CouldAssert(S,G,I) become false.  We can no longer
          perform the actions of the assert winner, and so we transition
          to NoInfo state and perform Actions A4 (below).  This includes
          sending a "canceling assert" with an infinite metric.

   Transitions from "I am Assert Loser" State

   When in "I am Assert Loser" state, the following transitions can
   occur:

     Receive Preferred Assert
          We receive an assert that is better than that of the current
          assert winner.  We stay in Loser state and perform Actions A2
          below.

Top      Up      ToC       Page 89 
     Receive Acceptable Assert with RPTbit clear from Current Winner
          We receive an assert from the current assert winner that is
          better than our own metric for this (S,G) (although the metric
          may be worse than the winner's previous metric).  We stay in
          Loser state and perform Actions A2 below.

     Receive Inferior Assert or Assert Cancel from Current Winner
          We receive an assert from the current assert winner that is
          worse than our own metric for this group (typically, because
          the winner's metric became worse or because it is an assert
          cancel).  We transition to NoInfo state, deleting the (S,G)
          assert information and allowing the normal PIM Join/Prune
          mechanisms to operate.  Usually, we will eventually re-assert
          and win when data packets from S have started flowing again.

     Assert Timer Expires
          The (S,G) Assert Timer expires.  We transition to NoInfo
          state, deleting the (S,G) assert information (Actions A5
          below).

     Current Winner's GenID Changes or NLT Expires
          The Neighbor Liveness Timer associated with the current winner
          expires or we receive a Hello message from the current winner
          reporting a different GenID from the one it previously
          reported.  This indicates that the current winner's interface
          or router has gone down (and may have come back up), and so we
          must assume it no longer knows it was the winner.  We
          transition to the NoInfo state, deleting this (S,G) assert
          information (Actions A5 below).

     AssertTrackingDesired(S,G,I)->FALSE
          AssertTrackingDesired(S,G,I) becomes FALSE.  Our forwarding
          state has changed so that (S,G) Asserts on interface I are no
          longer of interest to us.  We transition to the NoInfo state,
          deleting the (S,G) assert information.

     My metric becomes better than the assert winner's metric
          my_assert_metric(S,G,I) has changed so that now my assert
          metric for (S,G) is better than the metric we have stored for
          current assert winner.  This might happen when the underlying
          routing metric changes, or when CouldAssert(S,G,I) becomes
          true; for example, when SPTbit(S,G) becomes true.  We
          transition to NoInfo state, delete this (S,G) assert state
          (Actions A5 below), and allow the normal PIM Join/Prune
          mechanisms to operate.  Usually, we will eventually re-assert
          and win when data packets from S have started flowing again.

Top      Up      ToC       Page 90 
     RPF_interface(S) stops being interface I
          Interface I used to be the RPF interface for S, and now it is
          not.  We transition to NoInfo state, deleting this (S,G)
          assert state (Actions A5 below).

     Receive Join(S,G) on Interface I
          We receive a Join(S,G) that has the Upstream Neighbor Address
          field set to my primary IP address on interface I.  The action
          is to transition to NoInfo state, delete this (S,G) assert
          state (Actions A5 below), and allow the normal PIM Join/Prune
          mechanisms to operate.  If whoever sent the Join was in error,
          then the normal assert mechanism will eventually re-apply, and
          we will lose the assert again.  However, whoever sent the
          assert may know that the previous assert winner has died, and
          so we may end up being the new forwarder.

   (S,G) Assert State machine Actions

     A1:  Send Assert(S,G).
          Set Assert Timer to (Assert_Time - Assert_Override_Interval).
          Store self as AssertWinner(S,G,I).
          Store spt_assert_metric(S,I) as AssertWinnerMetric(S,G,I).

     A2:  Store new assert winner as AssertWinner(S,G,I) and assert
          winner metric as AssertWinnerMetric(S,G,I).
          Set Assert Timer to Assert_Time.

     A3:  Send Assert(S,G).
          Set Assert Timer to (Assert_Time - Assert_Override_Interval).

     A4:  Send AssertCancel(S,G).
          Delete assert info (AssertWinner(S,G,I) and
          AssertWinnerMetric(S,G,I) will then return their default
          values).

     A5:  Delete assert info (AssertWinner(S,G,I) and
          AssertWinnerMetric(S,G,I) will then return their default
          values).

     A6:  Store new assert winner as AssertWinner(S,G,I) and assert
          winner metric as AssertWinnerMetric(S,G,I).
          Set Assert Timer to Assert_Time.
          If (I is RPF_interface(S)) AND (UpstreamJPState(S,G) == true)
          set SPTbit(S,G) to TRUE.

   Note that some of these actions may cause the value of
   JoinDesired(S,G), PruneDesired(S,G,rpt), or RPF'(S,G) to change,
   which could cause further transitions in other state machines.


Next RFC Part