4 If there exists a (Sp,G) entry, with or without the
RPT-bit set, the oif-timer for I is expired, and the
Entry-timer is restarted.
3 For each address, Sp, in the prune list whose RPT-bit and
WC-bit are both set:
1 If there is an existing (*,G) entry, with Sp as the RP
for G, the router lowers the entry's Oif-timer for I
to its Oif-Deletion-Delay, allowing for other
downstream routers on a multi-access LAN to override the
prune. However, on point-to-point links, the oif-timer
is expired immediately.
2 If the corresponding (*,*,RP) state exists, but there
is no (*,G) entry, a (*,G) entry is created. The
outgoing interface list is copied from (*,*,RP) entry,
with the interface, I, on which the prune was
received, deleted.
For any new (S,G), (*,G) or (*,*,RP) entry created by an
incoming Join/Prune message, the SPT-bit is cleared (and if a
Join/Prune-Suppression timer is used, it is left off.)
If the entry has a Join/Prune-Suppression timer associated with it,
and if the received Join/Prune does not indicate the router as its
target, then the receiving router examines the join and prune lists
to see if any addresses in the list `completely- match' existing
(S,G), (*,G), or (*,*,RP) state for which the receiving router
currently schedules Join/Prune messages. An element on the join or
prune list `completely-matches' a route entry only if both the IP
addresses and RPT-bit flag are the same. If the incoming Join/Prune
message completely matches an existing (S,G), (*,G), or (*,*,RP)
entry and the Join/Prune arrived on the iif for that entry, then the
router compares the Holdtime included in the Join/Prune message, to
its own [Join/Prune-Holdtime]. If its own [Join/Prune-Holdtime] is
lower, the Join/Prune-Suppression-timer is started at the
[Join/Prune-Suppression-Timeout]. If the [Join/Prune-Holdtime] is
equal, the tie is resolved in favor of the Join/Prune Message
originator that has the higher IP address. When the Join/Prune timer
expires, the router triggers a Join/Prune message for the
corresponding entry(ies).
3.3 Register and Register-Stop
When a source first starts sending to a group its packets are
encapsulated in Register messages and sent to the RP. If the data
rate warrants source-specific paths, the RP sets up source specific
state and starts sending (S,G) Join/Prune messages toward the source,
with S in the join list.
3.3.1 Sending Registers and Receiving Register-Stops
Register messages are sent as follows:
1 When a DR receives a packet from a directly connected
source, S
1 If there is no corresponding (S,G) entry, and the
router has RP-Set information, the DR creates one with
the Register-Suppression-timer turned off and the RP
address set according to the hash function mapping for
the corresponding group. The oif list is copied from
existing (*,G) or (*,*,RP) entries, if they exist. The
iif of the (S,G) entry is always excluded from the oif
list.
2 If there is a (S,G) entry in existence, the DR simply
restarts the corresponding Entry-timer.
When a PMBR (e.g., a router that connects the PIM-SM region to
a dense mode region running DVMRP or PIM-DM) receives a packet
from a source in the dense mode region, the router treats the
packet as if it were from a directly connected source. A
separate document will describe the details of
interoperability.
2 If the new or previously-existing (S,G) entry's Register-
Suppression-timer is not running, the data packet is
encapsulated in a Register message and unicast to the RP
for that group. The data packet is also forwarded according
to (S,G) state in the DR if the oif list is not null; since
a receiver may join the SP-tree while the DR is still
registering to the RP.
3 If the (S,G) entry's Register-Suppression-timer is running,
the data packet is not sent in a Register message, it is
just forwarded according to the (S,G) oif list.
When the DR receives a Register-Stop message, it restarts the
Register-Suppression-timer in the corresponding (S,G) entry(ies) at
[Register-Suppression-Timeout] seconds. If there is data to be
registered, the DR may send a null Register (a Register message with
a zero-length data portion in the inner IP packet) to the RP,
[Probe-Time] seconds before the Register- Suppression-timer expires,
to avoid sending occasional bursts of traffic to an RP unnecessarily.
3.3.2 Receiving Register Messages and Sending Register-Stops
When a router (i.e., the RP) receives a Register message, the router
does the following:
1 Decapsulates the data packet, and checks for a
corresponding (S,G) entry.
1 If a (S,G) entry with cleared (0) SPT bit exists, and
the received Register does not have the Null-
Register-Bit set to 1, the packet is forwarded; and
the SPT bit is left cleared (0). If the SPT bit is 1,
the packet is dropped, and Register-Stop messages are
triggered. Register-Stops should be rate-limited (in
an implementation-specific manner) so that no more
than a few are sent per round trip time. This prevents
a high datarate stream of packets from triggering a
large number of Register-Stop messages between the
time that the first packet is received and the time
when the source receives the first Register-Stop.
2 If there is no (S,G) entry, but there is a (*,G)
entry, and the received Register does not have the
Null-Register-Bit set to 1, the packet is forwarded
according to the (*,G) entry.
3 If there is a (*,*,RP) entry but no (*,G) entry, and
the Register received does not have the Null-
Register-Bit set to 1, a (*,G) or (S,G) entry is
created and the oif list is copied from the (*,*,RP)
entry to the new entry. The packet is forwarded
according to the created entry.
4 If there is no G or (*,*,RP) entry corresponding to G,
the packet is dropped, and a Register-Stop is
triggered.
5 A "Border bit" bit is added to the Register message,
to facilitate interoperability mechanisms. PMBRs set
this bit when registering for external sources (see
Section 2.7). If the "Border bit" is set in the
Register, the RP does the following:
1 If there is no matching (S,G) state, but there
exists (*,G) or (*,*,RP) entry, the RP creates a
(S,G) entry, with a `PMBR' field. This field
holds the source of the Register (i.e. the outer
IP address of the register packet). The RP
triggers a (S,G) join towards the source of the
data packet, and clears the SPT bit for the (S,G)
entry. If the received Register is not a `null
Register' the packet is forwarded according to
the created state. Else,
2 If the `PMBR' field for the corresponding (S,G)
entry matches the source of the Register packet,
and the received Register is not a `null
Register', the decapsulated packet is forwarded
to the oif list of that entry. Else,
3 If the `PMBR' field for the corresponding (S,G)
entry matches the source of the Register packet,
the decapsulated packet is forwarded to the oif
list of that entry, else
4 The packet is dropped, and a Register-stop is
triggered towards the source of the Register.
The (S,G) Entry-timer is restarted by Registers arriving from
that source to that group.
2 If the matching (S,G) or (*,G) state contains a null oif
list, the RP unicasts a Register-Stop message to the source
of the Register message; in the latter case, the source-
address field, within the Register-Stop message, is set to
the wildcard value (all 0's). This message is not processed
by intermediate routers, hence no (S,G) state is
constructed between the RP and the source.
3 If the Register message arrival rate warrants it and there
is no existing (S,G) entry, the RP sets up a (S,G) route
entry with the outgoing interface list, excluding iif(S,G),
copied from the (*,G) outgoing interface list, its SPT-bit
is initialized to 0. If a (*,G) entry does not exist, but
there exists a (*,*,RP) entry with the RP corresponding to
G , the oif list for (S,G) is copied -excluding the iif-
from that (*,*,RP) entry.
A timer (Entry-timer) is set for the (S,G) entry and this
timer is restarted by receipt of data packets for (S,G).
The (S,G) entry causes the RP to send a Join/Prune message
for the indicated group towards the source of the register
message.
If the (S,G) oif list becomes null, Join/Prune messages
will not be sent towards the source, S.
3.4 Multicast Data Packet Forwarding
Processing a multicast data packet involves the following steps:
1 Lookup route state based on a longest match of the source
address, and an exact match of the destination address in
the data packet. If neither S, nor G, find a longest match
entry, and the RP for the packet's destination group
address has a corresponding (*,*,RP) entry, then the
longest match does not require an exact match on the
destination group address. In summary, the longest match is
performed in the following order: (1) (S,G), (2) (*,G). If
neither is matched, then a lookup is performed on (*,*,RP)
entries.
2 If the packet arrived on the interface found in the
matching-entry's iif field, and the oif list is not
null:
1 Forward the packet to the oif list for that entry
and restart the Entry-timer if the matching entry is
(S,G). Optionally, the (S,G) Entry-timer may be
restarted by periodic checking of the matching packet
count.
2 If the entry is a (S,G) entry with a cleared SPT-bit,
and a (*,G) or associated (*,*,RP) also exists whose
incoming interface is different than that for (S,G),
set the SPT-bit for the (S,G) entry and trigger an
(S,G) RPT-bit prune towards the RP.
3 If the source of the packet is a directly-connected
host and the router is the DR on the receiving
interface, check the Register-Suppression-timer
associated with the (S,G) entry. If it is not running,
then the router encapsulates the data packet in a
register message and sends it to the RP.
This covers the common case of a packet arriving on the RPF
interface to the source or RP and being forwarded to all
joined branches. It also detects when packets arrive on the
SP-tree, and triggers their pruning from the RP-tree. If it
is the DR for the source, it sends data packets
encapsulated in Registers to the RPs.
3 If the packet matches to an entry but did not arrive on the
interface found in the entry's iif field, check the
SPT-bit of the entry. If the SPT-bit is set, drop the
packet. If the SPT-bit is cleared, then lookup the (*,G),
or (*,*,RP), entry for G. If the packet arrived on the
iif found in (*,G), or the corresponding (*,*,RP),
forward the packet to the oif list of the matching
entry. This covers the case when a data packet matches on a
(S,G) entry for which the SP-tree has not yet been
completely established upstream.
4 If the packet does not match any entry, but the source of
the data packet is a local, directly-connected host, and
the router is the DR on a multi-access LAN and has RP-Set
information, the DR uses the hash function to determine the
RP associated with the destination group, G. The DR creates
a (S,G) entry, with the Register-Suppression-timer not
running, encapsulates the data packet in a Register message
and unicasts it to the RP.
5 If the packet does not match to any entry, and it is not a
local host or the router is not the DR, drop the packet.
3.4.1 Data triggered switch to shortest path tree (SP-tree)
Different criteria can be applied to trigger switching over from the
RP-based shared tree to source-specific, shortest path trees.
One proposed example is to do so based on data rate. For example,
when a (*,G), or corresponding (*,*,RP), entry is created, a data rate
counter may be initiated at the last-hop routers. The counter is
incremented with every data packet received for directly connected
members of an SM group, if the longest match is (*,G) or (*,*,RP). If
and when the data rate for the group exceeds a certain configured
threshold (t1), the router initiates `source-specific' data rate
counters for the following data packets. Then, each counter for a
source, is incremented when packets matching on (*,G), or (*,*,RP),
are received from that source. If the data rate from the particular
source exceeds a configured threshold (t2), a (S,G) entry is created
and a Join/Prune message is sent towards the source. If the RPF
interface for (S,G) is not the same as that for (*,G) -or (*,*,RP),
then the SPT-bit is cleared in the (S,G) entry.
Other configured rules may be enforced to cause or prevent
establishment of (S,G) state.
3.5 Assert
Asserts are used to resolve which of the parallel routers connected to
a multi-access LAN is responsible for forwarding packets onto the LAN.
3.5.1 Sending Asserts
The following Assert rules are provided when a multicast packet is
received on an outgoing multi-access interface "I" of an existing
(S,G) entry:
1 Do unicast routing table lookup on source IP address from
data packet, and send assert on interface "I" for source
IP address in data packet; include metric preference of
routing protocol and metric from routing table lookup.
2 If route is not found, use metric preference of 0x7fffffff
and metric 0xffffffff.
When an assert is sent for a (*,G) entry, the first bit in the
metric preference (the RPT-bit) is set to 1, indicating the data
packet is routed down the RP-tree.
Asserts should be rate-limited in an implementation-specific
manner.
3.5.2 Receiving Asserts
When an Assert is received the router performs a longest match on the
source and group address in the Assert message. The router checks the
first bit of the metric preference (RPT-bit).
1 If the RPT-bit is set, the router first does a match on
(*,G), or (*,*,RP), entries; if no matching entry is found,
it ignores the Assert.
2 If the RPT-bit is not set in the Assert, the router first
does a match on (S,G) entries; if no matching entry is
found, the router matches (*,G) or (*,*,RP) entries.
3.5.2.1 Receiving Asserts on an entry's outgoing interface
If the interface that received the Assert message is in the oif list
of the matched entry, then this Assert is processed by this router as
follows:
1 If the Assert's RPT-bit is set and the matching entry is
(*,*,RP), the router creates a (*,G) entry. If the Assert's
RPT-bit is cleared and the matching entry is (*,G), or
(*,*,RP), the router creates a (S,G)RPT-bit entry.
Otherwise, no new entry is created in response to the
Assert.
2 The router then compares the metric values received in the
Assert with the metric values associated with the matched
entry. The RPT-bit and metric preference (in that order)
are treated as the high-order part of an Assert metric
comparison. If the value in the Assert is less than the
router's value (with ties broken by the IP address, where
higher IP address wins), delete the interface from the
entry. When the deletion occurs for a (*,G) or (*,*,RP)
entry , the interface is also deleted from any associated
(S,G)RPT-bit or (*,G) entries, respectively. The Entry-
timer for the affected entries is restarted.
3 If the router has won the election the router keeps the
interface in its outgoing interface list. It acts as the
forwarder for the LAN.
The winning router sends an Assert message containing its own metric
to that outgoing interface. This will cause other routers on the LAN
to prune that interface from their route entries. The winning router
sets the RPT-bit in the Assert message if a (*,G) or (S,G)RPT-bit
entry was matched.
3.5.2.2 Receiving Asserts on an entry's incoming interface
If the Assert arrived on the incoming interface of an existing (S,G),
(*,G), or (*,*,RP) entry, the Assert is processed as follows. If the
Assert message does not match the entry, exactly, it is ignored; i.e,
longest-match is not used in this case. If the Assert message does
match exactly, then:
1 Downstream routers will select the upstream router with the
smallest metric preference and metric as their RPF
neighbor. If two metrics are the same, the highest IP
address is chosen to break the tie. This is important so
that downstream routers send subsequent Joins/Prunes (in
SM) to the correct neighbor. An Assert-timer is initiated
when changing the RPF neighbor to the Assert winner. When
the timer expires, the router resets its RPF neighbor
according to its unicast routing tables to capture network
dynamics and router failures.
2 If the downstream routers have downstream members, and if
the Assert caused the RPF neighbor to change, the
downstream routers must trigger a Join/Prune message to
inform the upstream router that packets are to be forwarded
on the multi-access network.
3.6 Candidate-RP-Advertisements and Bootstrap messages
Candidate-RP-Advertisements (C-RP-Advs) are periodic PIM messages
unicast to the BSR by those routers that are configured as
Candidate-RPs (C-RPs).
Bootstrap messages are periodic PIM messages originated by the
Bootstrap router (BSR) within a domain, and forwarded hop-by-hop to
distribute the current RP-set to all routers in that domain.
The Bootstrap messages also support a simple mechanism by which the
Candidate BSR (C-BSR) with the highest BSR-priority and IP address
(referred to as the preferred BSR) is elected as the BSR for the
domain. We recommend that each router configured as a C-RP also be
configured as a C-BSR. Sections 3.6.2 and 3.6.3 describe the combined
function of Bootstrap messages as the vehicle for BSR election and
RP-Set distribution.
A Finite State Machine description of the BSR election and RP- Set
distribution mechanisms is included in Appendix II.
3.6.1 Sending Candidate-RP-Advertisements
C-RPs periodically unicast C-RP-Advs to the BSR for that domain. The
interval for sending these messages is subject to local configuration
at the C-RP.
Candidate-RP-Advertisements carry group address and group mask
fields. This enables the advertising router to limit the
advertisement to certain prefixes or scopes of groups. The
advertising router may enforce this scope acceptance when receiving
Registers or Join/Prune messages. C-RPs should send C-RP-Adv
messages with the Authoritative bit cleared.
3.6.2 Receiving C-RP-Advs and Originating Bootstrap
Upon receiving a C-RP-Adv, a router does the following:
1 If the router is not the elected BSR, it ignores the
message, else
2 The BSR adds the RP address to its local pool of candidate
RPs, according to the associated group prefix(es) in the
C-RP-Adv message. The Holdtime in the C-RP-Adv message is
also stored with the corresponding RP, to be included later
in the Bootstrap message. The BSR may apply a local
policy to limit the number of Candidate RPs included
in the Bootstrap message. The BSR may override the prefix
indicated in a C-RP-Adv unless the Authoritative bit in the
C-RP-Adv is set.
The BSR keeps an RP-timer per RP in its local RP-set. The RP- timer
is initialized to the Holdtime in the RP's C-RP-Adv. When the timer
expires, the corresponding RP is removed from the RP- set. The RP-
timer is restarted by the C-RP-Advs from the corresponding RP.
The BSR also uses its Bootstrap-timer to periodically send Bootstrap
messages. In particular, when the Bootstrap-timer expires, the BSR
originates an Bootstrap message on each of its PIM interfaces. The
message is sent with a TTL of 1 to the `ALL-PIM-ROUTERS' group. In
steady state, the BSR originates Bootstrap messages periodically. At
startup, the Bootstrap-timer is initialized to [Bootstrap-Timeout],
causing the first Bootstrap message to be originated only when and if
the timer expires. For timer details, see Section 3.6.3. A DR
unicasts a Bootstrap message to each new PIM neighbor, i.e., after
the DR receives the neighbor's Hello message (it does so even if the
new neighbor becomes the DR).
The Bootstrap message is subdivided into sets of {group- prefix,RP-
Count,RP-addresses}. For each RP-address, the corresponding Holdtime
is included in the "RP-Holdtime" field. The format of the Bootstrap
message allows `semantic fragmentation', if the length of the
original Bootstrap message exceeds the packet maximum boundaries (see
Section 4). However, we recommend against configuring a large number
of routers as C-RPs, to reduce the semantic fragmentation required.
3.6.3 Receiving and Forwarding Bootstrap
Each router keeps a Bootstrap-timer, initialized to [Bootstrap-
Timeout] at startup.
When a router receives Bootstrap message sent to `ALL-PIM- ROUTERS'
group, it performs the following:
1 If the message was not sent by the RPF neighbor towards the
BSR address included, the message is dropped. Else
2 If the included BSR is not preferred over, and not equal
to, the currently active BSR:
1 If the Bootstrap-timer has not yet expired, or if the
receiving router is a C-BSR, then the Bootstrap
message is dropped. Else
2 If the Bootstrap-timer has expired and the receiving
router is not a C-BSR, the receiving router stores the
RP-Set and BSR address and priority found in the
message, and restarts the timer by setting it to
[Bootstrap-Timeout]. The Bootstrap message is then
forwarded out all PIM interfaces, excluding the one
over which the message arrived, to `ALL-PIM-ROUTERS'
group, with a TTL of 1.
3 If the Bootstrap message includes a BSR address that is
preferred over, or equal to, the currently active BSR, the
router restarts its Bootstrap-timer at [Bootstrap-Timeout]
seconds. and stores the BSR address and RP-Set information.
The Bootstrap message is then forwarded out all PIM
interfaces, excluding the one over which the message
arrived, to `ALL-PIM-ROUTERS' group, with a TTL of 1.
4 If the receiving router has no current RP set information
and the Bootstrap was unicast to it from a directly
connected neighbor, the router stores the information as
its new RP-set. This covers the startup condition when a
newly booted router obtains the RP-Set and BSR address from
its DR.
When a router receives a new RP-Set, it checks if each of the RPs
referred to by existing state (i.e., by (*,G), (*,*,RP), or
(S,G)RPT-bit entries) is in the new RP-Set. If an RP is not in the new
RP-set, that RP is considered unreachable and the hash algorithm (see
below) is re-performed for each group with locally active state that
previously hashed to that RP. This will cause those groups to be
distributed among the remaining RPs. When the new RP-Set contains a
new RP, the value of the new RP is calculated for each group covered
by that C-RP's Group- prefix. Any group for which the new RP's value
is greater than the previously active RP's value is switched over to
the new RP.
3.7 Hash Function
The hash function is used by all routers within a domain, to map a
group to one of the C-RPs from the RP-Set. For a particular group, G,
the hash function uses only those C-RPs whose Group- prefix covers G.
The algorithm takes as input the group address, and the addresses of
the Candidate RPs, and gives as output one RP address to be used.
The protocol requires that all routers hash to the same RP within a
domain (except for transients). The following hash function must be
used in each router:
1 For each RP address C(i) in the RP-Set, whose Group-prefix
covers G, compute a value:
Value(G,M,C(i))=
(1103515245 * ((1103515245 * (G&M)+12345) XOR C(i)) + 12345) mod 2^31
where M is a hash-mask included in Bootstrap messages.
This hash-mask allows a small number of consecutive groups
(e.g., 4) to always hash to the same RP. For instance,
hierarchically-encoded data can be sent on consecutive
group addresses to get the same delay and fate-sharing
characteristics.
2 The candidate with the highest resulting value is then
chosen as the RP for that group, and its identity and hash
value are stored with the entry created.
Ties between C-RPs having the same hash value, are broken
in advantage of the highest address.
The hash function algorithm is invoked by a DR, upon reception of a
packet, or IGMP membership indication, for a group, for which the DR
has no entry. It is invoked by any router that has (*,*,RP) state when
a packet is received for which there is no corresponding (S,G) or
(*,G) entry. Furthermore, the hash function is invoked by all routers
upon receiving a (*,G) or (*,*,RP) Join/Prune message.
3.8 Processing Timer Events
In this subsection, we enumerate all timers that have been discussed
or implied. Since some critical timer events are not associated with
the receipt or sending of messages, they are not fully covered by
earlier subsections.
Timers are implemented in an implementation-specific manner. For
example, a timer may count up or down, or may simply expire at a
specific time. Setting a timer to a value T means that it will expire
after T seconds.
3.8.1 Timers related to tree maintenance
Each (S,G), (*,G), and (*,*,RP) route entry has multiple timers
associated with it: one for each interface in the outgoing interface
list, one for the multicast routing entry itself, and one optional
Join/Prune-Suppression-Timer. Each (S,G) and (*,G) entry also has an
Assert-timer and a Random-Delay-Join-Timer for use with Asserts. In
addition, DR's have a Register- Suppression-timer for each (S,G) entry
and every router has a single Join/Prune-timer. (A router may
optionally keep separate Join/Prune-timers for different interfaces or
route entries if different Join/Prune periods are desired.)
* [Join/Prune-Timer] This timer is used for periodically
sending aggregate Join/Prune messages. To avoid
synchronization among routers booting simultaneously, it is
initially set to a random value between 1 and [Join/Prune-
Period]. When it expires, the timer is immediately
restarted to [Join/Prune-Period]. A Join/Prune message is
then sent out each interface. This timer should not be
restarted by other events.
* [Join/Prune-Suppression-Timer (kept per route entry)] A
route entry's (optional) Join/Prune-Suppression-Timer may
be used to suppress duplicate joins from multiple
downstream routers on the same LAN. When a Join message is
received from a neighbor on the entry's incoming interface
in which the included Holdtime is higher than the router's
own [Join/Prune-Holdtime] (with ties broken by higher IP
address), the timer is set to [Join/Prune-Suppression-
Timeout], with some random jitter introduced to avoid
synchronization of triggered Join/Prune messages on
expiration. (The random timeout value must be < 1.5 *
[Join/Prune-Period] to prevent losing data after 2 dropped
Join/Prunes.) The timer is restarted every time a
subsequent Join/Prune message (with higher Holdtime/IP
address) for the entry is received on its incoming
interface. While the timer is running, Join/Prune messages
for the entry are not sent. This timer is idle (not
running) for point-to-point links.
* [Oif-Timer (kept per oif for each route entry)] A timer for
each oif of a route entry is used to time out that oif.
Because some of the outgoing interfaces in an (S,G) entry
are copied from the (*,G) outgoing interface list, they may
not have explicit (S,G) join messages from some of the
downstream routers (i.e., where members are joining to the
(*,G) tree only). Thus, when an Oif-timer is restarted in a
(*,G) entry, the Oif-timer is restarted for that interface
in each existing (S,G) entry whose oif list contains that
interface. The same rule applies to (*,G) and (S,G) entries
when restarting an Oif-timer on a (*,*,RP) entry.
The following table shows its usage when first adding the
oif to the entry's oiflist, when it should be restarted
(unless it is already higher), and when it should be
decreased (unless it is already lower).
Set to | When | Applies to
-------------------------|------------------------------|------------
included Holdtime | adding oif off Join/Prune | (S,G) (*,G)
| | (*,*,RP)
Increased (only) to | When | Applies to
-------------------------|------------------------------|------------
included Holdtime | received Join/Prune | (S,G) (*,G)
| | (*,*,RP)
| |
Value of (*,*,RP) | (*,*,RP) oif-timer restarted | (S,G) (*,G)
oif-timer | |
| |
Value of (*,G) | (*,G) oif-timer restarted | (S,G)
oif-timer | |
Decreased (only) to | When | Applies to
-------------------------|------------------------------|------------
Oif-Deletion-Delay | prune received | (S,G) (*,G)
When the timer expires, the oif is removed from the oiflist
if there are no directly-connected members. When deleted,
the oif is also removed in any associated (S,G) or (*,G)
entries.
* [Entry-Timer (kept per route entry)] A timer for each route
entry is used to time out that entry. The following table
summarizes its usage when first adding the oif to the
entry's oiflist, and when it should be restarted (unless it
is already higher).
Set to | When | Applies to
----------------------|--------------------------|------------
[Data- Timeout] | created off data packet | (S,G)
| |
included Holdtime | created off Join/Prune | (S,G) (*,G)
(*,*,RP)
Increased (only) to | When | Applies to
----------------------|--------------------------|------------
[Data-Timeout] | receiving data packets | (S,G)no RPT-bit
| |
Value of oif-timer | any oif-timer restarted | (S,G)RPT-bit (*,G)
| | (*,*,RP)
| |
[Assert-Timeout] | assert received | (S,G)RPT-bit
| | (*,G)w/null oif
When the timer expires, the route entry is deleted; if the
entry is a (*,G) or (*,*,RP) entry, all associated
(S,G)RPT-bit entries are also deleted.
* [Register-Suppression-Timer (kept per (S,G) route entry)]
An (S,G) route entry's Register-Suppression-Timer is used
to suppress registers when the RP is receiving data packets
natively. When a Register-Stop message for the entry is
received from the RP, the timer is set to a random value in
the range 0.5 * [Register-Suppression-Timeout] to 1.5 *
[Register-Suppression-Timeout]. While the timer is running,
Registers for that entry will be suppressed. If null
registers are used, a null register is sent [Probe-Time]
seconds before the timer expires.
* [Assert-Timer (per (S,G) or (*,G) route entry)] The
Assert-Timer for an (S,G) or (*,G) route entry is used for
timing out Asserts received. When an Assert is received and
the RPF neighbor is changed to the Assert winner, the
Assert-Timer is set to [Assert-Timeout], and is restarted
to this value every time a subsequent Assert for the entry
is received on its incoming interface. When the timer
expires, the router resets its RPF neighbor according to
its unicast routing table.
* [Random-Delay-Join-Timer (per (S,G) or (*,G) route entry)]
The Random-Delay-Join-Timer for an (S,G) or (*,G) route
entry is used to prevent synchronization among downstream
routers on a LAN when their RPF neighbor changes. When the
RPF neighbor changes, this timer is set to a random value
between 0 and [Random-Delay-Join-Timeout] seconds. When the
timer expires, a triggered Join/Prune message is sent for
the entry unless its Join/Prune-Suppression-Timer is
running.
3.8.2 Timers relating to neighbor discovery
* [Hello-Timer] This timer is used to periodically send Hello
messages. To avoid synchronization among routers booting
simultaneously, it is initially set to a random value
between 1 and [Hello-Period]. When it expires, the timer is
immediately restarted to [Hello-Period]. A Hello message is
then sent out each interface. This timer should not be
restarted by other events.
* [Neighbor-Timer (kept per neighbor)] A Neighbor-Timer for
each neighbor is used to time out the neighbor state. When
a Hello message is received from a new neighbor, the timer
is initially set to the Holdtime included in the Hello
message (which is equal to the neighbor's value of [Hello-
Holdtime]). Every time a subsequent Hello is received from
that neighbor, the timer is restarted to the Holdtime in
the Hello. When the timer expires, the neighbor state is
removed.
3.8.3 Timers relating to RP information
* [C-RP-Adv-Timer (C-RP's only)] Routers configured as
candidate RP's use this timer to periodically send C-RP-Adv
messages. To avoid synchronization among routers booting
simultaneously, the timer is initially set to a random
value between 1 and [C-RP-Adv-Period]. When it expires, the
timer is immediately restarted to [C-RP-Adv-Period]. A C-
RP-Adv message is then sent to the elected BSR. This timer
should not be restarted by other events.
* [RP-Timer (BSR only, kept per RP in RP-Set)] The BSR uses a
timer per RP in the RP-Set to monitor liveness. When a C-RP
is added to the RP-Set, its timer is set to the Holdtime
included in the C-RP-Adv message from that C-RP (which is
equal to the C-RP's value of [RP-Holdtime]). Every time a
subsequent C-RP-Adv is received from that RP, its timer is
restarted to the Holdtime in the C-RP-Adv. When the timer
expires, the RP is removed from the RP-Set included in
Bootstrap messages.
* [Bootstrap-Timer] This timer is used by the BSR to
periodically originate Bootstrap messages, and by other
routers to time out the BSR (see 3.6.3). This timer is
initially set to [Bootstrap-Timeout]. A C-BSR restarts
this timer to [Bootstrap-Timeout] upon receiving a Bootstrap
message from a preferred router, and originates an Bootstrap
message and restarts the timer to [Bootstrap-Period] when it
expires. Routers not configured as C-BSR's restart this
timer to [Bootstrap-Timeout] upon receiving a Bootstrap
message from the elected or a more preferred BSR, and ignore
Bootstrap messages from non-preferred C-BSRs while it is
running.
3.8.4 Default timer values
Most of the default timeout values for state information are 3.5
times the refresh period. For example, Hellos refresh Neighbor state
and the default Hello-timer period is 30 seconds, so a default
Neighbor-timer duration of 105 seconds is included in the Holdtime
field of the Hellos. In order to improve convergence, however, the
default timeout value for information related to RP liveness and
Bootstrap messages is 2.5 times the refresh period.
In this version of the spec, we suggest particular numerical timer
settings. A future version of the specification will specify a
mechanism for timer values to be scaled based upon observed network
parameters.
* [Join/Prune-Period] This is the interval between
sending Join/Prune messages. {Default: 60 seconds.} This
value may be set to take into account such things as the
configured bandwidth and expected average number of
multicast route entries for the attached network or link
(e.g., the period would be longer for lower-speed links, or
for routers in the center of the network that expect to
have a larger number of entries ). In addition, a router
could modify this value (and corresponding Join/Prune-
Holdtime value) if the number of route entries changes
significantly (e.g., by an order of magnitude). For
example, given a default minimum Join/Prune-Period value,
if the number of route entries with a particular iif
increases from N to N*100, the router could increase its
Join/Prune-Period (and Join/Prune-Holdtime), for that
interface, by a factor of 10; and if/when the number of
entries decreases back to N, the Join/Prune-Period (and
Join/Prune-Holdtime) could be decreased to its previous
value. If the Join/Prune-Period is modified, these changes
should be made relatively infrequently and the router
should continue to refresh at its previous Join/Prune-
Period for at least Join/Prune-Holdtime, in order to allow
the upstream router to adapt.
* [Join-Prune Holdtime] This is the Holdtime specified in
Join/Prune messages, and is used to time out oifs. This
should be set to 3.5 * [Join/Prune-Period]. {Default: 210
seconds.}
* [Join/Prune-Suppression-Timeout] This is the mean
interval between receiving a Join/Prune with a higher
Holdtime (with ties broken by higher IP addres) and
allowing duplicate Join/Prunes to be sent again. This
should be set to approximately 1.25 * [Join/Prune-Period].
{Default: 75 seconds. }
* [Data-Timeout] This is the time after which (S,G) state
for a silent source will be deleted. {Default: 210
seconds.}
* [Register-Suppression-Timeout] This is the mean
interval between receiving a Register-Stop and allowing
Registers to be sent again. A lower value means more
frequent register bursts at RP, while a higher value means
longer join latency for new receivers. {Default: 60
seconds.} (Note that if null Registers are sent [Probe-
Time] seconds before the timeout, register bursts are
prevents, and [Register-Suppression-Timeout] may be lowered
to decrease join latency.)
* [Probe-Time] When null Registers are used, this is the
time between sending a null Register and the Register-
Suppression-Timer expiring unless it is restarted by
receiving a Register-Stop. Thus, a null Register would be
sent when the Register-Suppression-Timer reaches this
value. {Default: 5 seconds.}
* [Assert-Timeout] This is the interval between the last
time an Assert is received, and the time at which the
assert is timed out. {Default: 180 seconds.}
* [Random-Delay-Join-Timeout] This is the maximum
interval between the time when the RPF neighbor changes,
and the time at which a triggered Join/Prune message is
sent. {Default: 4.5 seconds.}
* [Hello-Period] This is the interval between sending
Hello messages. {Default: 30 seconds.}
* [Hello-Holdtime] This is the Holdtime specified in
Hello messages, after which neighbors will time out their
neighbor entries for the router. This should be set to 3.5
* [Hello-Period]. {Default: 105 seconds.}
* [C-RP-Adv-Period] For C-RPs, this is the interval
between sending C-RP-Adv messages. {Default: 60 seconds.}
* [RP-Holdtime] For C-RPs, this is the Holdtime specified
in C-RP-Adv messages, and is used by the BSR to time out
RPs. This should be set to 2.5 * [C-RP-Adv-Period].
{Default: 150 seconds.}
* [Bootstrap-Period] At the elected BSR, this is the
interval between originating Bootstrap messages, and should
be equal to 60 seconds.
* [Bootstrap-Timeout] This is the time after which the
elected BSR will be assumed unreachable when Bootstrap
messages are not received from it. This should be set to
2.5 * [Bootstrap-Period]. {Default: 150 seconds.}
3.9 Summary of flags used
Following is a summary of all the flags used in our scheme.
Bit | Used in | Definition
Authoritative | C-RP-Adv | Group-prefix information should not be
over-ridden by BSR
Border | Register | Register for external sources is coming
from PIM multicast border router
Null | Register | Register sent as Probe of RP, the
encapsulated IP data packet should not
be forwarded
RPT | Route entry | Entry represents state on the RP-tree
RPT | Join/Prune | Join is associated with the shared tree
and therefore the Join/Prune message is
propagated along the RP-tree (source
encoded is an RP address)
RPT | Assert | The data packet was routed down the shared
tree; thus, the path indicated corresponds
to the RP tree
SPT | (S,G) entry | Packets have arrived on the iif towards S,
and the iif is different from the (*,G)
iif
WC |Join | The receiver expects to receive packets
from all sources via this (shared tree)
path. Thus, the Join/Prune applies to a
(*,G) entry
WC | Route entry | Wildcard entry; if there is no more
specific match for a particular source,
packets will be forwarded according to
this entry
3.10 Security
All PIM control messages may use IPSec [6] to address security
concerns.
4 Packet Formats
This section describes the details of the packet formats for PIM
control messages.
All PIM control messages have protocol number 103.
Basically, PIM messages are either unicast (e.g. Registers and
Register-Stop), or multicast hop-by-hop to `ALL-PIM-ROUTERS' group
`224.0.0.13' (e.g. Join/Prune, Asserts, etc.).
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 | Addr length | Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
PIM Ver
PIM Version number is 2.
Type Types for specific PIM messages. PIM Types are:
0 = Hello
1 = Register
2 = Register-Stop
3 = Join/Prune
4 = Bootstrap
5 = Assert
6 = Graft (used in PIM-DM only)
7 = Graft-Ack (used in PIM-DM only)
8 = Candidate-RP-Advertisement
Addr length
Address length in bytes. Throughout this section this
would indicate the number of bytes in the Address field of
an address, including unicast and group addresses.
Checksum
The checksum is the 16-bit one's complement of the one's
complement sum of the entire PIM message, (excluding the
data portion in the Register message). For computing the
checksum, the checksum field is zeroed.
4.1 Encoded Source and Group Address formats
1 Unicast address: Only the address is included. The length
of the unicast address in bytes is specified in the `Addr
length' field in the header.
2 Encoded-Group-Address: Takes the following format:
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reserved | Mask Len | Group multicast Address ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ...Group multicast Address ...|
+-+-+-+-+-+-+-+-+-+-+~+~+~+~+~+~+
Reserved
Transmitted as zero. Ignored upon receipt.
Mask Length
The Mask length is 8 bits. The value is the number of
contiguous bits left justified used as a mask which
describes the address. It is less than or equal to
Addr length * 8. If the message is sent for a single
group then the Mask length must equal Addr length * 8
(i.e. 32 for IPv4 and 128 for IPv6).
Group multicast Address
contains the group address, and has number of bytes
equal to that specified in the Addr length field.
3 Encoded-Source-Address: Takes the following format:
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Rsrvd |S|W|R| Mask Len | Source Address ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+~+~+-+
Reserved
Transmitted as zero, ignored on receipt.
S,W,R See Section 4.5 for details.
Mask Length
Mask length is 8 bits. The value is the number of
contiguous bits left justified used as a mask which
describes the address. The mask length must be less
than or equal to Addr Length * 8. If the message is
sent for a single source then the Mask length must
equal Addr length * 8. In version 2 of PIM, it is
strongly recommended that this field be set to 32 for
IPv4.
Source Address
The address length is indicated from the Addr length
field at the beginning of the header. For IPv4, the
address length is 4 octets.
4.2 Hello Message
It is sent periodically by routers on all interfaces.
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 | Addr length | Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| OptionType | OptionLength |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| OptionValue |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+~+~+
| . |
| . |
| . |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| OptionType | OptionLength |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| OptionValue |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+~+~+
PIM Version, Type, Addr length, Checksum
Described above.
OptionType
The type of the option given in the following OptionValue
field.
OptionLength
The length of the OptionValue field in bytes.
OptionValue
A variable length field, carrying the value of the option.
The Option fields may contain the following values:
* OptionType = 1; OptionLength = 2; OptionValue = Holdtime;
where Holdtime is the amount of time a receiver must keep
the neighbor reachable, in seconds. If the Holdtime is set
to `0xffff', the receiver of this message never times out
the neighbor. This may be used with ISDN lines, to avoid
keeping the link up with periodic Hello messages.
Furthermore, if the Holdtime is set to `0', the information
is timed out immediately.
* OptionType 2 to 16: reserved
* The rest of the OptionTypes are defined in another
document.
In general, options may be ignored; but a router must not ignore the
'Holdtime' OptionType.
4.3 Register Message
A Register message is sent by the DR or a PMBR to the RP when a
multicast packet needs to be transmitted on the RP-tree. Source IP
address is set to the address of the DR, destination IP address is to
the RP's address.
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 | Addr length | Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|B|N| Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Multicast data packet ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
PIM Version, Type, Addr length, Checksum
Described above. {Note that the checksum for Registers
is done only on the PIM header, excluding the data packet
portion.}
B The Border bit. If the router is a DR for a source that it
is directly connected to, it sets the B bit to 0. If the
router is a PMBR for a source in a directly connected
cloud, it sets the B bit to 1.
N The Null-Register bit. Set to 1 by a DR that is probing
the RP before expiring its local Register-Suppression
timer. Set to 0 otherwise.
Multicast data packet
The original packet sent by the source.
For (S,G) null Registers, the Multicast data packet portion contains
only a dummy IP header with S as the source address, G as the
destination address, and a data length of zero.
4.4 Register-Stop Message
A Register-Stop is unicast from the RP to the sender of the
Register message. Source IP address is the address to which the
register was addressed. Destination IP address is the source
address of the register message.
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 | Addr length | Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Group Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Unicast-Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
PIM Version, Type, Addr length, Checksum
Described above.
Encoded-Group Address
Format described above. Note that for Register-Stops the
Mask Len field contains Addr length * 8 (32 for IPv4), if
the message is sent for a single group.
Unicast-Source Address
IP host address of source from multicast data packet in
register. The length of this field in bytes is specified in
the Addr length field. A special wild card value (0.0.0.0),
can be used to indicate any source.
4.5 Join/Prune Message
A Join/Prune message is sent by routers towards upstream sources and
RPs. Joins are sent to build shared trees (RP trees) or source trees
(SPT). Prunes are sent to prune source trees when members leave
groups as well as sources that do not use the shared tree.