draft-ietf-pim-sm-v2-new-05.txt

xorp源码hg

                iif is in inherited_olist(S,G,rpt) {
       send Assert(*,G) on iif
    }
 }

 oiflist = oiflist (-) iif
 forward packet on all interfaces in oiflist

This pseudocode employs several "macro" definitions:

DirectlyConnected(S) is TRUE if the source S is on any subnet that is
directly connected to this router (or for packets originating on this
router).

inherited_olist(S,G) and inherited_olist(S,G,rpt) are defined in Section
4.1.

Basically inherited_olist(S,G) is the outgoing interface list for
packets forwarded on (S,G) state taking into account (*,*,RP) state,
(*,G) state, asserts, etc.

inherited_olist(S,G,rpt) is the outgoing interface for packets forwarded
on (*,*,RP) or (*,G) state taking into account (S,G,rpt) prune state,
and asserts, etc.



Fenner/Handley/Holbrook/Kouvelas                 Section 4.2.  [Page 26]

INTERNET-DRAFT           Expires: September 2002              March 2002


Update_SPTbit(S,G,iif) is defined in section 4.2.2.

CheckSwitchToSpt(S,G) is defined in section 4.2.1.

UpstreamJPState(S,G) is the state of the finite state machine in section
4.5.7.

Keepalive_Period is defined in Section 4.11.

Data triggered PIM-Assert messages sent from the above forwarding code
should be rate-limited in a implementation-dependent manner.


4.2.1.  Last hop switchover to the SPT

In Sparse-Mode PIM, last-hop routers join the shared tree towards the
RP. Once traffic from sources to joined groups arrives at a last-hop
router it has the option of switching to receive the traffic on a
shortest path tree (SPT).

The decision for a router to switch to the SPT is controlled as follows:


     void
     CheckSwitchToSpt(S,G) {
       if ( ( pim_include(*,G) (-) pim_exclude(S,G)
              (+) pim_include(S,G) != NULL )
            AND SwitchToSptDesired(S,G) ) {
              restart KeepAliveTimer(S,G);
       }
     }


SwitchToSptDesired(S,G) is a policy function that is implementation
defined. An "infinite threshold" policy can be implemented making
SwitchToSptDesired(S,G) return false all the time.  A "switch on first
packet" policy can be implemented by making SwitchToSptDesired(S,G)
return true once a single packet has been received for the source and
group.


4.2.2.  Setting and Clearing the (S,G) SPT bit

The (S,G) SPTbit is used to distinguish whether to forward on
(*,*,RP)/(*,G) or on (S,G) state.  When switching from the RP tree to
the source tree, there is a transition period when data is arriving due
to upstream (*,*,RP)/(*,G) state while upstream (S,G) state is being
established during which time a router should continue to forward only



Fenner/Handley/Holbrook/Kouvelas               Section 4.2.2.  [Page 27]

INTERNET-DRAFT           Expires: September 2002              March 2002


on (*,*,RP)/(*,G) state.  This prevents temporary black-holes that would
be caused by sending a Prune(S,G,rpt) before the upstream (S,G) state
has finished being established.

Thus, when a packet arrives, the (S,G) SPTbit is updated as follows:


     void
     Update_SPTbit(S,G,iif) {
       if ( iif == RPF_interface(S)
             AND JoinDesired(S,G) == TRUE
             AND ( DirectlyConnected(S) == TRUE
                   OR RPF_interface(S) != RPF_interface(RP)
                   OR inherited_olist(S,G,rpt) == NULL
                   OR RPF'(S,G) == RPF'(*,G) ) ) {
          Set SPTbit(S,G) to TRUE
       }
     }

Additionally a router sets SPTbit(S,G) to TRUE when it receives an
Assert(S,G) on RPF_interface(S).

JoinDesired(S,G) is defined in Section 4.5.7, and indicates whether we
have the appropriate (S,G) Join state to wish to send a Join(S,G)
upstream.

Basically Update_SPTbit will set the SPT bit if we have the appropriate
(S,G) join state and the packet arrived on the correct upstream
interface for S, and one or more of the following conditions applies:

1.   The source is directly connected, in which case the switch to the
     SPT is a no-op.

2.   The RPF interface to S is different from the RPF interface to the
     RP.  The packet arrived on RPF_interface(S), and so the SPT must
     have been completed.

3.   No-one wants the packet on the RP tree.

4.   RPF'(S,G) == RPF'(*,G).  In this case the router will never be able
     to tell if the SPT has been completed, so it should just switch
     immediately.

In the case where the RPF interface is the same for the RP and for S,
but RPF'(S,G) and RPF'(*,G) differ, then we wait for an Assert(S,G)
which indicates that the upstream router with (S,G) state believes the
SPT has been completed.  However item (3) above is needed because there
may not be any (*,G) state to trigger an Assert(S,G) to happen.



Fenner/Handley/Holbrook/Kouvelas               Section 4.2.2.  [Page 28]

INTERNET-DRAFT           Expires: September 2002              March 2002


The SPT bit is cleared in the (S,G) upstream state machine (see Section
4.5.7) when JoinDesired(S,G) becomes FALSE.


4.3.  Designated Routers (DR) and Hello Messages

A shared-media LAN like Ethernet may have multiple PIM-SM routers
connected to it.  If the LAN has directly connected hosts, then a single
one of these routers, the DR, will act on behalf of those hosts with
respect to the PIM-SM protocol.  Because the distinction between LANs
and point-to-point interfaces can sometimes be blurred, and because
routers may also have multicast host functionality, the PIM-SM
specification makes no distinction between the two.  Thus DR election
will happen on all interfaces, LAN or otherwise.

DR election is performed using Hello messages.  Hello messages are also
the way that option negotiation takes place in PIM, so that additional
functionality can be enabled, or parameters tuned.


4.3.1.  Sending Hello Messages

PIM-Hello messages are sent periodically on each PIM-enabled interface.
They allow a router to learn about the neighboring PIM routers on each
interface.  Hello messages are also the mechanism used to elect a
Designated Router (DR), and to negotiate additional capabilities A
router must record the Hello information received from each PIM
neighbor.

Hello messages MUST be sent on all active interfaces, including physical
point-to-point links, and are multicast to address 224.0.0.13 (the ALL-
PIM-ROUTERS group).

      We note that some implementations do not send Hello messages
     on point-to-point interfaces.  This is non-compliant behavior.
     A compliant PIM router MUST send Hello messages, even on
     point-to-point interfaces.

A per interface hello timer (HT(I)) is used to trigger sending Hello
messages on each active interface.  When PIM is enabled on an interface
or a router first starts, the hello timer of that interface is set to a
random value between 0 and Triggered_Hello_Delay.  This prevents
synchronization of Hello messages if multiple routers are powered on
simultaneously.  After the initial randomized interval, Hello messages
must be sent every Hello_Period seconds.  The hello timer should not be
reset except when it expires.





Fenner/Handley/Holbrook/Kouvelas               Section 4.3.1.  [Page 29]

INTERNET-DRAFT           Expires: September 2002              March 2002


Note that neighbors will not accept Join/Prune or Assert messages from a
router unless they have first heard a Hello message from that router.
Thus if a router needs to send a Join/Prune or Assert message on an
interface on which it has not yet sent a Hello message, then it MUST
immediately send the relevant without Hello message without waiting for
the Hello timer to expire, followed by the Join/Prune or Assert message.

The DR_Election_Priority Option allows a network administrator to give
preference to a particular router in the DR election process by giving
it a numerically larger DR Election Priority.  The DR_Election_Priority
Option SHOULD be included in every Hello message, even if no DR election
priority is explicitly configured on that interface.  This is necessary
because priority-based DR election is only enabled when all neighbors on
an interface advertise that they are capable of using the DR Election
Priority Option.  The default priority is 1.

The Generation_Identifier (GenID) Option SHOULD be included in all Hello
messages.  The GenID option contains a randomly generated 32-bit value
that is regenerated each time PIM forwarding is started or restarted on
the interface, including when the router itself restarts.  When a Hello
message with a new GenID is received from a neighbor, any old Hello
information about that neighbor SHOULD be discarded and superseded by
the information from the new Hello message.  This may cause a new DR to
be chosen on that interface.

The LAN_Prune_Delay Option SHOULD be included in all Hello messages sent
on multi-access LANs. This option advertises a router's capability to
use values other than the default for the Propagation_Delay and
Override_Interval which affect the setting of the Prune Pending,
Upstream Join and Override Timers (defined in section 4.11).

To allow new or rebooting routers to learn of PIM neighbors quickly,
when a Hello message is received from a new neighbor, or a Hello message
with a new GenID is received from an existing neighbor, a new Hello
message should be sent on this interface after a randomized delay
between 0 and Triggered_Hello_Delay.  This triggered message need not
change the timing of the scheduled periodic message.  If a router needs
to send a Join/Prune to the new neighbor or send an Assert message in
response to an Assert message from the new neighbor before this
randomized delay has expired, then it MUST immediately send the relevant
without Hello message without waiting for the Hello timer to expire,
followed by the Join/Prune or Assert message.  If it does not do this,
then the new neighbor will discard the Join/Prune or Assert message.

Before an interface goes down or changes IP address, a Hello message
with a zero HoldTime should be sent immediately (with the old IP address
if the IP address changed).  This will cause PIM neighbors to remove
this neighbor (or its old IP address) immediately.



Fenner/Handley/Holbrook/Kouvelas               Section 4.3.1.  [Page 30]

INTERNET-DRAFT           Expires: September 2002              March 2002


4.3.2.  DR Election

When a PIM-Hello message is received on interface I the following
information about the sending neighbor is recorded:

     neighbor.interface
          The interface on which the Hello message arrived.

     neighbor.ip_address
          The IP address of the PIM neighbor.

     neighbor.genid
          The Generation ID of the PIM neighbor.

     neighbor.dr_priority
          The DR Priority field of the PIM neighbor if it is present in
          the Hello message.

     neighbor.dr_priority_present
          A flag indicating if the DR Priority field was present in the
          Hello message.

     neighbor.timeout
          A timer value to time out the neighbor state when it becomes
          stale.
          The Neighbor Liveness Timer (NLT(N,I)) is reset to
          Hello_Holdtime (from the Hello Holdtime option) whenever a
          Hello message is received containing a Holdtime option, or to
          Default_Hello_Holdtime if the Hello message does not contain
          the Holdtime option.

Neighbor state is deleted when the neighbor timeout expires.

The function for computing the DR on interface I is:

  host
  DR(I) {
      dr = me
      for each neighbor on interface I {
          if ( dr_is_better( neighbor, dr, I ) == TRUE ) {
              dr = neighbor
          }
      }
      return dr
  }






Fenner/Handley/Holbrook/Kouvelas               Section 4.3.2.  [Page 31]

INTERNET-DRAFT           Expires: September 2002              March 2002


The function used for comparing DR "metrics" on interface I is:

  bool
  dr_is_better(a,b,I) {
      if( there is a neighbor n on I for which n.dr_priority_present
              is false ) {
          return a.ip_address > b.ip_address
      } else {
          return ( a.dr_priority > b.dr_priority ) OR
              ( a.dr_priority == b.dr_priority AND
                   a.ip_address > b.ip_address )
      }
  }

The trivial function I_am_DR(I) is defined to aid readability:

  bool
  I_am_DR(I) {
     return DR(I) == me
  }


The DR election priority is a 32-bit unsigned number and the numerically
larger priority is always preferred.  A router's idea of the current DR
on an interface can change when a PIM-Hello message is received, when a
neighbor times out, or when a router's own DR priority changes.  If the
router becomes the DR or ceases to be the DR, this will normally cause
the DR Register state-machine to change state.  Subsequent actions are
determined by that state-machine.

      We note that some PIM implementations do not send Hello
     messages on point-to-point interfaces, and so cannot perform
     DR election on such interfaces.  This in non-compliant
     behavior.  DR election MUST be performed on ALL active PIM-SM
     interfaces.


4.3.3.  Reducing Prune Propagation Delay on LANs

In addition to the information recorded for the DR