| | | Cancel SAT(S,G) |
+----------------------------------+---------------+-------------------+
4.5.2.1. Transitions from the NotOriginator (NO) State
When the Originating(S,G) state machine is in the NotOriginator (NO)
state, the following event may trigger a transition:
Data Packet received from directly connected Source S addressed to
group G
The router MUST transition to an Originator (O) state, set
SAT(S,G) to SourceLifetime, and set SRT(S,G) to
StateRefreshInterval. The router SHOULD record the TTL of the
packet for use in State Refresh messages.
4.5.2.2. Transitions from the Originator (O) State
When the Originating(S,G) state machine is in the Originator (O)
state, the following events may trigger a transition:
Receive Data Packet from S addressed to G
The router remains in the Originator (O) state and MUST reset
SAT(S,G) to SourceLifetime. The router SHOULD increase its
recorded TTL to match the TTL of the packet, if the packet’s TTL
is larger than the previously recorded TTL. A router MAY record
the TTL based on an implementation specific sampling policy to
avoid examining the TTL of every multicast packet it handles.
SRT(S,G) Expires
The router remains in the Originator (O) state and MUST reset
SRT(S,G) to StateRefreshInterval. The router MUST also generate
State Refresh messages for transmission, as described in the
State Refresh Forwarding rules (Section 4.5.1), except for the
TTL. If the TTL of data packets from S to G are being recorded,
then the TTL of each State Refresh message is set to the highest
recorded TTL. Otherwise, the TTL is set to the configured State
Refresh TTL. Let I denote the interface over which a State
Refresh message is being sent. If the Prune(S,G) Downstream
state machine is in the Pruned (P) state, then the Prune-
Indicator bit MUST be set to 1 in the State Refresh message being
sent over I. Otherwise, the Prune-Indicator bit MUST be set to 0.
SAT(S,G) Expires
The router MUST cancel the SRT(S,G) timer and transition to the
NotOriginator (NO) state.
S is no longer directly connected
The router MUST transition to the NotOriginator (NO) state and
cancel both the SAT(S,G) and SRT(S,G).
4.6. PIM Assert Messages
4.6.1. Assert Metrics
Assert metrics are defined as follows:
struct assert_metric {
metric_preference;
route_metric;
ip_address;
};
When assert_metrics are compared, the metric_preference and
route_metric field are compared in order, where the first lower value
wins. If all fields are equal, the IP address of the router that
sourced the Assert message is used as a tie-breaker, with the highest
IP address winning.
An Assert metric for (S,G) to include in (or compare against) an
Assert message sent on interface I should be computed by using the
following pseudocode:
assert_metric
my_assert_metric(S,G,I) {
if (CouldAssert(S,G,I) == TRUE) {
return spt_assert_metric(S,G,I)
} else {
return infinite_assert_metric()
}
}
spt_assert_metric(S,I) gives the Assert metric we use if we’re
sending an Assert based on active (S,G) forwarding state:
assert_metric
spt_assert_metric(S,I) {
return {0,MRIB.pref(S),MRIB.metric(S),my_addr(I)}
}
MRIB.pref(X) and MRIB.metric(X) are the routing preference and
routing metrics associated with the route to a particular (unicast)
destination X, as determined by the MRIB. my_addr(I) is simply the
router’s network (e.g., IP) address associated with the local
interface I.
infinite_assert_metric() gives the Assert metric we need to send an
Assert but doesn’t match (S,G) forwarding state:
assert_metric
infinite_assert_metric() {
return {1,infinity,infinity,0}
}
4.6.2. AssertCancel Messages
An AssertCancel(S,G) message is simply an Assert message for (S,G)
with infinite metric. The Assert winner sends this message when it
changes its upstream interface to this interface. Other routers will
see this metric, causing those with forwarding state to send their
own Asserts and re-establish an Assert winner.
AssertCancel messages are simply an optimization. The original
Assert timeout mechanism will eventually allow a subnet to become
consistent; the AssertCancel mechanism simply causes faster
convergence. No special processing is required for an AssertCancel
message, as it is simply an Assert message from the current winner.
4.6.3. Assert State Macros
The macro lost_assert(S,G,I), is used in the olist computations of
Section 4.1.3, and is defined as follows:
bool lost_assert(S,G,I) {
if ( RPF_interface(S) == I ) {
return FALSE
} else {
return (AssertWinner(S,G,I) != me AND
(AssertWinnerMetric(S,G,I) is better than
spt_assert_metric(S,G,I)))
}
}
AssertWinner(S,G,I) defaults to NULL, and AssertWinnerMetric(S,G,I)
defaults to Infinity when in the NoInfo state.
4.6.4. (S,G) Assert Message State Machine
The (S,G) Assert state machine for interface I is shown in Figure 4.
There are three states:
NoInfo (NI)
This router has no (S,G) Assert state on interface I.
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 via
interface I.
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.
In addition, an Assert Timer (AT(S,G,I)) is used to time out the
Assert state.
+-------------+ +-------------+
| | Rcv Pref Assert or SR | |
| Winner |----------------------->| Loser |
| | | |
+-------------+ +-------------+
^ | ^ |
| | Rcv Pref Assert or| |
| |AT Expires OR State Refresh| |
| |CouldAssert->FALSE | |
| | | |
| | +-------------+ | |
| +-------->| |----------+ |
| | No Info | |
+-------------| |<-------------+
Rcv Data from dnstrm +-------------+ Rcv Inf Assert from Win OR
OR Rcv Inferior Assert Rcv Inf SR from Winner OR
OR Rcv Inferior SR AT Expires OR
CouldAssert Changes OR
Winner’s NLT Expires
Figure 4: Assert State Machine
In tabular form, the state machine is defined as follows:
+-------------------------------+--------------------------------------+
| | Previous State |
| +------------+------------+------------+
| Event | No Info | Winner | Loser |
+-------------------------------+------------+------------+------------+
| An (S,G) Data packet received | ->W Send | ->W Send | ->L |
| on downstream interface | Assert(S,G)| Assert(S,G)| |
| | Set | Set | |
| | AT(S,G,I) | AT(S,G,I) | |
+-------------------------------+--------------------------------------+
| Receive Inferior (Assert OR | N/A | N/A |->NI Cancel |
| State Refresh) from Assert | | | AT(S,G,I) |
| Winner | | | |
+-------------------------------+--------------------------------------+
| Receive Inferior (Assert OR | ->W Send | ->W Send | ->L |
| State Refresh) from non-Assert| Assert(S,G)| Assert(S,G)| |
| Winner AND CouldAssert==TRUE | Set | Set | |
| | AT(S,G,I) | AT(S,G,I) | |
+-------------------------------+--------------------------------------+
+-------------------------------+--------------------------------------+
| | Previous State |
| +------------+------------+------------+
| Event | No Info | Winner | Loser |
+-------------------------------+------------+------------+------------+
| Receive Preferred Assert OR | ->L Send | ->L Send | ->L Set |
| State Refresh | Prune(S,G) | Prune(S,G) | AT(S,G,I) |
| | Set | Set | |
| | AT(S,G,I) | AT(S,G,I) | |
+-------------------------------+--------------------------------------+
| Send State Refresh | ->NI | ->W Reset | N/A |
| | | AT(S,G,I) | |
+-------------------------------+--------------------------------------+
| AT(S,G) Expires | N/A | ->NI | ->NI |
+-------------------------------+--------------------------------------+
| CouldAssert -> FALSE | ->NI |->NI Cancel |->NI Cancel |
| | | AT(S,G,I) | AT(S,G,I) |
+-------------------------------+--------------------------------------+
| CouldAssert -> TRUE | ->NI | N/A |->NI Cancel |
| | | | AT(S,G,I) |
+-------------------------------+--------------------------------------+
| Winner’s NLT(N,I) Expires | N/A | N/A |->NI Cancel |
| | | | AT(S,G,I) |
+-------------------------------+--------------------------------------+
| Receive Prune(S,G), Join(S,G) | ->NI | ->W | ->L Send |
| or Graft(S,G) | | | Assert(S,G)|
+-------------------------------+--------------------------------------+
Terminology: A "preferred assert" is one with a better metric than
the current winner. An "inferior assert" is one with a worse metric
than my_assert_metric(S,G,I).
The state machine uses the following macro:
CouldAssert(S,G,I) = (RPF_interface(S) != I)
4.6.4.1. Transitions from NoInfo State
In the NoInfo state, the following events may trigger transitions:
An (S,G) data packet arrives on downstream interface I
An (S,G) data packet arrived on a downstream interface. It is
optimistically assumed that this router will be the Assert winner
for this (S,G). The Assert state machine MUST transition to the
"I am Assert Winner" state, send an Assert(S,G) to interface I,
store its own address and metric as the Assert Winner, and set
the Assert_Timer (AT(S,G,I) to Assert_Time, thereby initiating
the Assert negotiation for (S,G).
Receive Inferior (Assert OR State Refresh) AND
CouldAssert(S,G,I)==TRUE
An Assert or State Refresh is received for (S,G) that is inferior
to our own assert metric on interface I. The Assert state machine
MUST transition to the "I am Assert Winner" state, send an
Assert(S,G) to interface I, store its own address and metric as
the Assert Winner, and set the Assert Timer (AT(S,G,I)) to
Assert_Time.
Receive Preferred Assert or State Refresh
The received Assert or State Refresh has a better metric than
this router’s, and therefore the Assert state machine MUST
transition to the "I am Assert Loser" state and store the Assert
Winner’s address and metric. If the metric was received in an
Assert, the router MUST set the Assert Timer (AT(S,G,I)) to
Assert_Time. If the metric was received in a State Refresh, the
router MUST set the Assert Timer (AT(S,G,I)) to three times the
received State Refresh Interval. If CouldAssert(S,G,I) == TRUE,
the router MUST also multicast a Prune(S,G) to the Assert winner
with a Prune Hold Time equal to the Assert Timer and evaluate any
changes in its Upstream(S,G) state machine.
4.6.4.2. Transitions from Winner State
When in "I am Assert Winner" state, the following events trigger
transitions:
An (S,G) data packet arrives on downstream interface I
An (S,G) data packet arrived on a downstream interface. The
Assert state machine remains in the "I am Assert Winner" state.
The router MUST send an Assert(S,G) to interface I and set the
Assert Timer (AT(S,G,I) to Assert_Time.
Receive Inferior Assert or State Refresh
An (S,G) Assert is received containing a metric for S that is
worse than this router’s metric for S. Whoever sent the Assert
is in error. The router MUST send an Assert(S,G) to interface I
and reset the Assert Timer (AT(S,G,I)) to Assert_Time.
Receive Preferred Assert or State Refresh
An (S,G) Assert or State Refresh is received that has a better
metric than this router’s metric for S on interface I. The
Assert state machine MUST transition to "I am Assert Loser" state
and store the new Assert Winner’s address and metric. If the
metric was received in an Assert, the router MUST set the Assert
Timer (AT(S,G,I)) to Assert_Time. If the metric was received in
a State Refresh, the router MUST set the Assert Timer (AT(S,G,I))
to three times the State Refresh Interval. The router MUST also
multicast a Prune(S,G) to the Assert winner, with a Prune Hold
Time equal to the Assert Timer, and evaluate any changes in its
Upstream(S,G) state machine.
Send State Refresh
The router is sending a State Refresh(S,G) message on interface
I. The router MUST set the Assert Timer (AT(S,G,I)) to three
times the State Refresh Interval contained in the State
Refresh(S,G) message.
AT(S,G,I) Expires
The (S,G) Assert Timer (AT(S,G,I)) expires. The Assert state
machine MUST transition to the NoInfo (NI) state.
CouldAssert(S,G,I) -> FALSE
This router’s RPF interface changed, making CouldAssert(S,G,I)
false. This router can no longer perform the actions of the
Assert winner, so the Assert state machine MUST transition to
NoInfo (NI) state, send an AssertCancel(S,G) to interface I,
cancel the Assert Timer (AT(S,G,I)), and remove itself as the
Assert Winner.
4.6.4.3. Transitions from Loser State
When in "I am Assert Loser" state, the following transitions can
occur:
Receive Inferior Assert or State Refresh from Current Winner
An Assert or State Refresh is received from the current Assert
winner that is worse than this router’s metric for S (typically,
the winner’s metric became worse). The Assert state machine MUST
transition to NoInfo (NI) state and cancel AT(S,G,I). The router
MUST delete the previous Assert Winner’s address and metric and
evaluate any possible transitions to its Upstream(S,G) state
machine. Usually this router will eventually re-assert and win
when data packets from S have started flowing again.
Receive Preferred Assert or State Refresh
An Assert or State Refresh is received that has a metric better
than or equal to that of the current Assert winner. The Assert
state machine remains in Loser (L) state. If the metric was
received in an Assert, the router MUST set the Assert Timer
(AT(S,G,I)) to Assert_Time. If the metric was received in a
State Refresh, the router MUST set the Assert Timer (AT(S,G,I))
to three times the received State Refresh Interval. If the
metric is better than the current Assert Winner, the router MUST
store the address and metric of the new Assert Winner, and if
CouldAssert(S,G,I) == TRUE, the router MUST multicast a
Prune(S,G) to the new Assert winner.
AT(S,G,I) Expires
The (S,G) Assert Timer (AT(S,G,I)) expires. The Assert state
machine MUST transition to NoInfo (NI) state. The router MUST
delete the Assert Winner’s address and metric. If CouldAssert ==
TRUE, the router MUST evaluate any possible transitions to its
Upstream(S,G) state machine.
CouldAssert -> FALSE
CouldAssert has become FALSE because interface I has become the
RPF interface for S. The Assert state machine MUST transition to
NoInfo (NI) state, cancel AT(S,G,I), and delete information
concerning the Assert Winner on I.
CouldAssert -> TRUE
CouldAssert has become TRUE because interface I used to be the
RPF interface for S, and now it is not. The Assert state machine
MUST transition to NoInfo (NI) state, cancel AT(S,G,I), and
delete information concerning the Assert Winner on I.
Current Assert Winner’s NeighborLiveness Timer Expires
The current Assert winner’s NeighborLiveness Timer (NLT(N,I)) has
expired. The Assert state machine MUST transition to the NoInfo
(NI) state, delete the Assert Winner’s address and metric, and
evaluate any possible transitions to its Upstream(S,G) state
machine.
Receive Prune(S,G), Join(S,G), or Graft(S,G)
A Prune(S,G), Join(S,G), or Graft(S,G) message was received on
interface I with its upstream neighbor address set to the
router’s address on I. The router MUST send an Assert(S,G) on
the receiving interface I to initiate an Assert negotiation. The
Assert state machine remains in the Assert Loser(L) state. If a
Graft(S,G) was received, the router MUST respond with a
GraftAck(S,G).
4.6.5. Rationale for Assert Rules
The following is a summary of the rules for generating and processing
Assert messages. It is not intended to be definitive (the state
machines and pseudocode provide the definitive behavior). Instead,
it provides some rationale for the behavior.
1. The Assert winner for (S,G) must act as the local forwarder for
(S,G) on behalf of all downstream members.
2. PIM messages are directed to the RPF’ neighbor and not to the
regular RPF neighbor.
3. An Assert loser that receives a Prune(S,G), Join(S,G), or
Graft(S,G) directed to it initiates a new Assert negotiation so
that the downstream router can correct its RPF’(S).
4. An Assert winner for (S,G) sends a cancelling assert when it is
about to stop forwarding on an (S,G) entry. Example: If a router
is being taken down, then a canceling assert is sent.
4.7. PIM Packet Formats
All PIM-DM packets use the same format as PIM-SM packets. In the
event of a discrepancy, PIM-SM [4] should be considered the
definitive specification. All PIM control messages have IP protocol
number 103. All PIM-DM messages MUST be sent with a TTL of 1. All
PIM-DM messages except Graft and Graft Ack messages MUST be sent to
the ALL-PIM-ROUTERS group. Graft messages SHOULD be unicast to the
RPF’(S). Graft Ack messages MUST be unicast to the sender of the
Graft.
The IPv4 ALL-PIM-ROUTERS group is 224.0.0.13. The IPv6 ALL-PIM-
ROUTERS group is ’ff02::d’.
4.7.1. PIM Header
All PIM control messages have the following header:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|PIM Ver| Type | Reserved | Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
PIM Ver PIM version number is 2.
Type
Types for specific PIM messages. Available types are as follows:
0 = Hello
1 = Register (PIM-SM only)
2 = Register Stop (PIM-SM only)
3 = Join/Prune
4 = Bootstrap (PIM-SM only)
5 = Assert
6 = Graft
7 = Graft Ack
8 = Candidate RP Advertisement (PIM-SM only)