draft-ietf-pim-sm-bsr-03.txt

BCAST Implementation for NS2

Figure 2: Per-Scope-Zone State-machine for a router not configured as C-
                          BSR in tabular form

+-----------------------------------------------------------------------+
|                        When in No Info state                          |
+--------------------+--------------------------------------------------+
|     Event          |         Receive BSM for unknown Admin Scope      |
+--------------------+--------------------------------------------------+
|                    |         -> AP State                              |
|     Action         |         Forward BSM; Store RP-Set;               |
|                    |         Set BS Timer to BS Timeout;              |
|                    |         Set SZ Timer to SZ Timeout               |
+--------------------+--------------------------------------------------+


+-----------------------------------------------------------------------+
|                       When in Accept Any state                        |
+---------------+-----------------------------+-------------------------+
|   Event       |     Receive BSM             |     SZ Timer Expires    |
+---------------+-----------------------------+-------------------------+
|               |     -> AP State             |     -> No Info state    |
|               |     Forward BSM; Store      |     cancel timers;      |
|   Action      |     RP-Set; Set BS          |     clear state         |
|               |     Timer to BS             |                         |
|               |     Timeout                 |                         |
+---------------+-----------------------------+-------------------------+


+-----------------------------------------------------------------------+
|         When in Accept Preferred state                                |
+------------+-------------------+-------------------+------------------+
| Event      |   Receive         |   BS Timer        |  Receive Non-    |
|            |   Preferred BSM   |   Expires         |  preferred BSM   |
+------------+-------------------+-------------------+------------------+
|            |   -> AP State     |   -> AA State     |  -> AP State     |
|            |   Forward BSM;    |                   |                  |
| Action     |   Store RP-Set;   |                   |                  |
|            |   Set BS Timer    |                   |                  |
|            |   to BS Timeout   |                   |                  |
+------------+-------------------+-------------------+------------------+

A router that is not a candidate-BSR may be in one of three states:

No Info
     The router has no information about this scope zone.  This state



Fenner/Handley/Kermode/Thaler                      Section 3.  [Page 13]

INTERNET-DRAFT            Expires: August 2003             February 2003


     does not apply if the router is configured to know about this scope
     zone, or for the global scope zone.  When in this state, no state
     information is held and no timers run that refer to this scope
     zone.

Accept Any (AA)
     The router does not know of an active BSR, and will accept the
     first bootstrap message it sees as giving the new BSR's identity
     and the RP-Set.  If the router has an RP-Set cached from an
     obsolete bootstrap message, it continues to use it.

Accept Preferred (AP)
     The router knows the identity of the current BSR, and is using the
     RP-Set provided by that BSR.  Only bootstrap messages from that BSR
     or from a C-BSR with higher weight than the current BSR will be
     accepted.

On startup, the initial state for this scope zone is "Accept Any" for
routers that know about this scope zone, either through configuration or
because the scope zone is the global scope which always exists; the SZ
Timer is considered to be always running for such scope zones.  For
routers that do not know about a particular scope zone, the initial
state is No Info; no timers exist for the scope zone.

In addition to the three states, there are two timers:

o The bootstrap timer (BS Timer) - that is used to time out old
  bootstrap router information.

o The scope zone timer (SZ Timer) - that is used to time out the scope
  zone itself if BS messages specifying this scope zone stop arriving.

Bootstrap Message Processing Checks

When a bootstrap message is received, the following initial checks must
be performed:















Fenner/Handley/Kermode/Thaler                      Section 3.  [Page 14]

INTERNET-DRAFT            Expires: August 2003             February 2003


if ( (DirectlyConnected(BSM.src_ip_address) == FALSE)
     OR (we have no Hello state for BSM.src_ip_address)) {
  drop the BS message silently
}
if (BSM.dst_ip_address == ALL-PIM-ROUTERS group) {
  if ( BSM.src_ip_address != RPF_neighbor(BSM.BSR_ip_address) ) {
     drop the BS message silently
  }
} else if (BSM.dst_ip_address is one of my addresses) {
  if ( (Any previous BSM for this scope has been accepted) {
     #the packet was unicast, but this wasn't
     #a quick refresh on startup
     drop the BS message silently
  }
} else {
  drop the BS message silently
}
if (the interface the message arrived on is an Admin Scope
    border for the BSM.first_group_address) {
  drop the BS message silently
}

Basically, the packet must have come from a directly connected neighbor
for which we have active Hello state.  It must have been sent to the
ALL-PIM-ROUTERS group by the correct upstream router towards the BSR
that originated the BS message, or the router must have no BSR state (it
just restarted) and have received the BS message by unicast.  In
addition it must not have arrived on an interface that is a configured
admin scope border for the first group address contained in the BS
message.


BS State-machine Transition Events

If the bootstrap message passes the initial checks above without being
discarded, then it may cause a state transition event in one of the
above state-machines.  For both candidate and non-candidate BSRs, the
following transition events are defined:

     Receive Preferred BSM
          A bootstrap message is received from a BSR that has greater
          than or equal weight than the current BSR.  In a router is in
          P-BSR state, then it uses its own weight as that of the
          current BSR.

          The weighting for a BSR is the concatenation in fixed-
          precision unsigned arithmetic of the BSR priority field from
          the bootstrap message and the IP address of the BSR from the



Fenner/Handley/Kermode/Thaler                      Section 3.  [Page 15]

INTERNET-DRAFT            Expires: August 2003             February 2003


          bootstrap message (with the BSR priority taking the most-
          significant bits and the IP address taking the least
          significant bits).

     Receive BSM
          A bootstrap message is received, regardless of BSR weight.
A non-candidate BSM also has the following transition event defined:

     Receive BSM for unknown Admin Scope
          As "Receive BSM", except that the admin scope zone indicated
          in the BSM was not previously known at this router.

BS State-machine Actions

The state-machines specify actions that include setting the BS timer to
the following values:

     BS Period
          The periodic interval with which bootstrap messages are
          normally sent.  The default value is 60 seconds.

     BS Timeout
          The interval after which bootstrap router state is timed out
          if no bootstrap message from that router has been heard.  The
          default value is 2 times the BS Period plus 10 seconds, which
          is 130 seconds.

     Randomized Override Interval
          The randomized interval during which a router avoids sending a
          bootstrap message while it waits to see if another router has
          a higher bootstrap weight.  This interval is to reduce control
          message overhead during BSR election.  The following
          pseudocode is proposed as an efficient implementation of this
          "randomized" value:

          Delay = 5 + 2 * log_2(1 + bestPriority - myPriority)
                  + AddrDelay


          where myPriority is the Candidate-BSR's configured priority,
          and bestPriority equals:

          bestPriority = Max(storedPriority, myPriority)

          and AddrDelay is given by the following for IPv4:






Fenner/Handley/Kermode/Thaler                      Section 3.  [Page 16]

INTERNET-DRAFT            Expires: August 2003             February 2003


          if ( bestPriority == myPriority) {
              AddrDelay = log_2(storedAddr - myAddr) / 16
          } else {
              AddrDelay = 2 - (myAddr / 2^31)
          }

          and AddrDelay is given by the following for IPv6:

          if ( bestPriority == myPriority) {
              AddrDelay = log_2(storedAddr - myAddr) / 64
          } else {
              AddrDelay = 2 - (myAddr / 2^127)
          }


          where myAddr is the Candidate-BSR's address, storedAddr is the
          stored BSR's address, and storedPriority is the stored BSR's
          priority.

     SZ Timeout
          The interval after which a router will time out an Admin Scope
          zone that it has dynamically learned.  The interval MUST be
          larger than the BS Timeout.  The default value is ten times
          the BS Timeout, which is 1300 seconds.

In addition to setting the timers, the following actions may be
triggered by state-changes in the state-machines:

     Forward BSM
          A bootstrap message that passes the Bootstrap Message
          Processing Checks is forwarded out of all interfaces with PIM
          neighbors (including the interface it is received on), except
          where this would cause the BSM to cross an admin-scope
          boundary for the scope zone indicated in the message.  The
          source IP address of the message is the forwarding router's IP
          address on the interface the message is being forwarded from,
          the destination address is ALL-PIM-ROUTERS, and the TTL of the
          message is set to 1.

          As an optimation, a router MAY choose not to forward a BSM out
          of the interface the message was received on if that interface
          is a point-to-point interface.  On interfaces with multiple
          PIM neighbors, a router MUST forward an accepted BSM onto the
          interface that BSM was received on, but if the number of PIM
          neighbors on that interface is large, it MAY delay forwarding
          a BSM onto that interface by a small randomized interval to
          prevent message implosion.




Fenner/Handley/Kermode/Thaler                      Section 3.  [Page 17]

INTERNET-DRAFT            Expires: August 2003             February 2003


          Rationale: A BSM needs to be forwarded onto the interface the
          message was received on (in addition to the other interfaces)
          because the routers on a LAN may not have consistent routing
          information.  If three routers on a LAN and A, B, and C, and
          at router B RPF(BSR)==A and at router C RPF(BSR)==B, then
          router A originally forwards the BSM onto the LAN, but router
          C will only accept it when router B re-forwards the message
          onto the LAN.

     Originate BSM
          A new bootstrap message is constructed by the BSR, giving the
          BSR's address and BSR priority, and containing the BSR's
          chosen RP-Set.  The message is forwarded out of all multicast-
          capable interfaces, except where this would cause the BSM to
          cross an admin-scope boundary for the scope zone indicated in
          the message.  The IP source address of the message is the
          originating router's IP address on the interface the message
          is being forwarded from, the destination address is ALL-PIM-
          ROUTERS, and the TTL of the message is set to 1.

     Store RP Set
          The RP-Set from the received bootstrap message is stored and
          used by the router to decide the RP for each group that the
          router has state for.  Storing this RP Set may cause other
          state-transitions to occur in the router.  The BSR's IP
          address and priority from the received bootstrap message are
          also stored to be used to decide if future bootstrap messages
          are preferred.

In addition to the above state-machine actions, a DR also unicasts a
stored copy of the Bootstrap message to each new PIM neighbor, i.e.,
after the DR receives the neighbor's first Hello message, and sends a
Hello message in response.  It does so even if the new neighbor becomes
the DR.

3.1.  Sending Candidate-RP-Advertisements

Every C-RP periodically unicasts a C-RP-Adv to the BSR for that scope
zone to inform the BSR of the C-RP's willingness to function as an RP.
Unless configured otherwise, it does this for every Admin Scope zone for
which it has state, and for the global scope zone.  If the same router
is the BSR for more than one scope zone, the C-RP-Adv for these scope
zones MAY be combined into a single message.

If the C-RP is a ZBR for an admin scope zone, then the Admin Scope bit
MUST be set in the C-RP-Adv messages it sends for that scope zone;
otherwise this bit MUST NOT be set.  This information is currently only
used for logging purposes by the BSR, but might allow for future



Fenner/Handley/Kermode/Thaler                    Section 3.1.  [Page 18]

INTERNET-DRAFT            Expires: August 2003             February 2003


extensions of the protocol.