Multicast data packet
The original packet sent by the source.
For (S,G) null Registers, the Multicast data packet portion
contains only a dummy 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 address is the address to which the register was
addressed. Destination 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 | Reserved | Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Group Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Unicast-Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
PIM Version, Type, Reserved, Checksum
Described above.
Encoded-Group Address
Format described above. Note that for Register-Stops the
Mask Len field contains full address length * 8 (e.g. 32
for IPv4 native encoding), if the message is sent for a
single group.
Encoded-Unicast-Source Address
host address of source from multicast data packet in
register. The format for this address is given in the
Encoded-Unicast-Address in 4.1. A special wild card value
(0's), 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.
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 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Unicast-Upstream Neighbor Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reserved | Num groups | Holdtime |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Multicast Group Address-1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Number of Joined Sources | Number of Pruned Sources |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Joined Source Address-1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| . |
| . |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Joined Source Address-n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Pruned Source Address-1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| . |
| . |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Pruned Source Address-n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| . |
| . |
| . |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Multicast Group Address-n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Number of Joined Sources | Number of Pruned Sources |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Joined Source Address-1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| . |
| . |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Joined Source Address-n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Pruned Source Address-1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| . |
| . |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Pruned Source Address-n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
PIM Version, Type, Reserved, Checksum
Described above.
Encoded-Unicast Upstream Neighbor Address
The address of the RPF or upstream neighbor. The format
for this address is given in the Encoded-Unicast-Address in
4.1. .IP "Reserved"
Transmitted as zero, ignored on receipt.
Holdtime
The amount of time a receiver must keep the Join/Prune
state alive, in seconds. If the Holdtime is set to
`0xffff', the receiver of this message never times out the
oif. This may be used with ISDN lines, to avoid keeping the
link up with periodical Join/Prune messages. Furthermore,
if the Holdtime is set to `0', the information is timed out
immediately.
Number of Groups
The number of multicast group sets contained in the
message.
Encoded-Multicast group address
For format description see Section
4.1. A wild card group in the (*,*,RP) join is represented
by a 224.0.0.0 in the group address field and `4' in the
mask length field. A (*,*,RP) join also has the WC-bit and
the RPT-bit set.
Number of Joined Sources
Number of join source addresses listed for a given group.
Join Source Address-1 .. n
This list contains the sources that the sending router
will forward multicast datagrams for if received on the
interface this message is sent on.
See format section 4.1. The fields explanation for the
Encoded-Source-Address format follows:
Reserved
Described above.
S The Sparse bit is a 1 bit value, set to 1 for PIM-SM.
It is used for PIM v.1 compatibility.
W The WC bit is a 1 bit value. If 1, the join or prune
applies to the (*,G) or (*,*,RP) entry. If 0, the join
or prune applies to the (S,G) entry where S is Source
Address. Joins and prunes sent towards the RP must
have this bit set.
R The RPT-bit is a 1 bit value. If 1, the information
about (S,G) is sent towards the RP. If 0, the
information must be sent toward S, where S is the
Source Address.
Mask Length, Source Address
Described above.
Represented in the form of
< WC-bit >< RPT-bit ><Mask length >< Source address>:
A source address could be a host IPv4 native encoding
address :
< 0 >< 0 >< 32 >< 192.1.1.17 >
A source address could be the RP's IP address :
< 1 >< 1 >< 32 >< 131.108.13.111 >
A source address could be a subnet address to prune from
the RP-tree :
< 0 >< 1 >< 28 >< 192.1.1.16 >
A source address could be a general aggregate :
< 0 >< 0 >< 16 >< 192.1.0.0 >
Number of Pruned Sources
Number of prune source addresses listed for a group.
Prune Source Address-1 .. n
This list contains the sources that the sending router
does not want to forward multicast datagrams for when
received on the interface this message is sent on. If the
Join/Prune message boundary exceeds the maximum packet
size, then the join and prune lists for the same group must
be included in the same packet.
4.6 Bootstrap Message
The Bootstrap messages are multicast to `ALL-PIM-ROUTERS' group, out
all interfaces having PIM neighbors (excluding the one over which the
message was received). Bootstrap messages are sent with TTL value of
1. Bootstrap messages originate at the BSR, and are forwarded by
intermediate routers.
Bootstrap message is divided up into `semantic fragments', if the
original message exceeds the maximum packet size boundaries.
The semantics of a single `fragment' is given below:
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 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Fragment Tag | Hash Mask len | BSR-priority |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Unicast-BSR-Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Group Address-1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RP-Count-1 | Frag RP-Cnt-1 | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Unicast-RP-Address-1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RP1-Holdtime | RP1-Priority | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Unicast-RP-Address-2 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RP2-Holdtime | RP2-Priority | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| . |
| . |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Unicast-RP-Address-m |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RPm-Holdtime | RPm-Priority | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Group Address-2 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| . |
| . |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Group Address-n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RP-Count-n | Frag RP-Cnt-n | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Unicast-RP-Address-1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RP1-Holdtime | RP1-Priority | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Unicast-RP-Address-2 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RP2-Holdtime | RP2-Priority | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| . |
| . |
| . |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Unicast-RP-Address-m |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RPm-Holdtime | RPm-Priority | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
PIM Version, Type, Reserved, Checksum
Described above.
Fragment Tag
A randomly generated number, acts to distinguish the
fragments belonging to different Bootstrap messages;
fragments belonging to same Bootstrap message carry the
same `Fragment Tag'.
Hash Mask len
The length (in bits) of the mask to use in the hash
function. For IPv4 we recommend a value of 30. For IPv6 we
recommend a value of 126.
BSR-priority
Contains the BSR priority value of the included BSR. This
field is considered as a high order byte when comparing BSR
addresses.
Encoded-Unicast-BSR-Address
The address of the bootstrap router for the domain. The
format for this address is given in the Encoded-Unicast-
Address in 4.1. .IP "Encoded-Group Address-1..n"
The group prefix (address and mask) with which the
Candidate RPs are associated. Format previously described.
RP-Count-1..n
The number of Candidate RP addresses included in the whole
Bootstrap message for the corresponding group prefix. A
router does not replace its old RP-Set for a given group
prefix until/unless it receives `RP-Count' addresses for
that prefix; the addresses could be carried over several
fragments. If only part of the RP-Set for a given group
prefix was received, the router discards it, without
updating that specific group prefix's RP-Set.
Frag RP-Cnt-1..m
The number of Candidate RP addresses included in this
fragment of the Bootstrap message, for the corresponding
group prefix. The `Frag RP-Cnt' field facilitates parsing
of the RP-Set for a given group prefix, when carried over
more than one fragment.
Encoded-Unicast-RP-address-1..m
The address of the Candidate RPs, for the corresponding
group prefix. The format for this address is given in the
Encoded-Unicast-Address in 4.1. .IP "RP1..m-Holdtime"
The Holdtime for the corresponding RP. This field is
copied from the `Holdtime' field of the associated RP
stored at the BSR.
RP1..m-Priority
The `Priority' of the corresponding RP and Encoded-Group
Address. This field is copied from the `Priority' field
stored at the BSR when receiving a Candidate-RP-
Advertisement. The highest priority is `0' (i.e. the lower
the value of the `Priority' field, the higher). Note that
the priority is per RP per Encoded-Group Address.
4.7 Assert Message
The Assert message is sent when a multicast data packet is received
on an outgoing interface corresponding to the (S,G) or (*,G)
associated with the source.
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 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Group Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Unicast-Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|R| Metric Preference |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Metric |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
PIM Version, Type, Reserved, Checksum
Described above.
Encoded-Group Address
The group address to which the data packet was addressed,
and which triggered the Assert. Format previously
described.
Encoded-Unicast-Source Address
Source address from multicast datagram that triggered the
Assert packet to be sent. The format for this address is
given in the Encoded-Unicast-Address in 4.1. .IP "R"
RPT-bit is a 1 bit value. If the multicast datagram that
triggered the Assert packet is routed down the RP tree,
then the RPT-bit is 1; if the multicast datagram is routed
down the SPT, it is 0.
Metric Preference
Preference value assigned to the unicast routing protocol
that provided the route to Host address.
Metric The unicast routing table metric. The metric is in units
applicable to the unicast routing protocol used.
4.8 Graft Message
Used in dense-mode. Refer to PIM dense mode specification.
4.9 Graft-Ack Message
Used in dense-mode. Refer to PIM dense mode specification.
4.10 Candidate-RP-Advertisement
Candidate-RP-Advertisements are periodically unicast from the C-RPs
to the BSR.
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 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Prefix-Cnt | Priority | Holdtime |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Unicast-RP-Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Group Address-1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| . |
| . |
| . |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoded-Group Address-n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
PIM Version, Type, Reserved, Checksum
Described above.
Prefix-Cnt
The number of encoded group addresses included in the
message; indicating the group prefixes for which the C-RP
is advertising. A Prefix-Cnt of `0' implies a prefix of
224.0.0.0 with mask length of 4; i.e. all multicast groups.
If the C-RP is not configured with Group-prefix
information, the C-RP puts a default value of `0' in this
field.
Priority
The `Priority' of the included RP, for the corresponding
Encoded-Group Address (if any). highest priority is `0'
(i.e. the lower the value of the `Priority' field, the
higher the priority). This field is stored at the BSR upon
receipt along with the RP address and corresponding
Encoded-Group Address.
Holdtime
The amount of time the advertisement is valid. This field
allows advertisements to be aged out.
Encoded-Unicast-RP-Address
The address of the interface to advertise as a Candidate
RP. The format for this address is given in the Encoded-
Unicast-Address in 4.1. .IP "Encoded-Group Address-1..n"
The group prefixes for which the C-RP is advertising.
Format previously described.
5 Acknowledgments
Tony Ballardie, Scott Brim, Jon Crowcroft, Bill Fenner, Paul Francis,
Joel Halpern, Horst Hodel, Polly Huang, Stephen Ostrowski, Lixia
Zhang and Girish Chandranmenon provided detailed comments on previous
drafts. The authors of CBT [8] and membership of the IDMR WG provided
many of the motivating ideas for this work and useful feedback on
design details.
This work was supported by the National Science Foundation, ARPA,
cisco Systems and Sun Microsystems.
6 Appendices
6.1 Appendix I: Major Changes and Updates to the Spec
This appendix populates the major changes in the specification
document as compared to `draft-ietf-idmr-pim-spec-01.ps,txt'.
bsubsection*Major Changes
List of changes since March '96 IETF:
1. (*,*,RP) Joins state and data forwarding check; replaces (*,G-
Prefix) Joins state for interoperability. (*,G) negative cache
introduced for the (*,*,RP) state supporting mechanisms.
2. Semantic fragmentation for the Bootstrap message.
3. Refinement of Assert details.
4. Addition and refinement of Join/Prune suppression and Register
suppression (introduction of null Registers).
5. Editorial changes and clarifications to the timers section.
6. Addition of Appendix II (BSR Election and RP-Set Distribution),
and Appendix III (Glossary of Terms).
7. Addition of table of contents.
List of changes incurred since version 1 of the spec.:
1. Proposal and refinement of bootstrap router (BSR) election
mechanisms
2. Introduction of hash functions for Group to RP mapping
3. New RP-liveness indication mechanisms based upon the the
Bootstrap Router (BSR) and the Bootstrap messages.
4. Removal of reachability messages, RP reports and multiple RPs
per group.
*Packet Format Changes
Packet Format incurred updates to accommodate different address
lengths, and address aggregation.
1 The `Addr Family' and `Encoding Type' fields were added to the
packet formats.
2 The Encoded source and group address formats were introduced,
with the use of a `Mask length' field to allow aggregation, section
4.1.
3 Packet formats are no longer IGMP messages; rather PIM messages.
PIM message types and formats were also modified:
[Note: most changes were made to the May 95 version, unless
otherwise specified].
1 Obsolete messages:
Register-Ack [Feb. 96]
Poll and Poll Response [Feb. 96]
RP-Reachability [Feb. 96]
RPlist-Mapping [Feb. 96]
2 New messages:
Candidate-RP-Advertisement [change made in October 95]
RP-Set [Feb. 96]
3 Modified messages:
Join/Prune [Feb. 96]
Register [Feb. 96]
Register-Stop [Feb. 96]
Hello (addition of OptionTypes) [Aug 96]
4 Renamed messages:
Query messages are renamed as Hello messages [Aug. 96]
RP-Set messages are renamed as Bootstrap messages [Aug. 96]
6.2 Appendix II: BSR Election and RP-Set Distribution
For simplicity, the bootstrap message is used in both the BSR
election and the RP-Set distribution mechanisms. These mechanisms
are described by the following state machine, illustrated in figure
4. The protocol transitions for a Candidate-BSR are given in state
diagram (a). For routers not configured as Candidate-BSRs, the
protocol transitions are given in state diagram (b).
[Figures are present only in the postscript version] Fig. 4 State
Diagram for the BSR election and RP-Set distribution
Each PIM router keeps a bootstrap-timer, initialized to [Bootstrap-
Timeout], in addition to a local BSR field `LclBSR' (initialized to a
local address if Candidate-BSR, or to 0 otherwise), and a local RP-
Set `LclRP-Set' (initially empty). The main stimuli to the state
machine are timer events and arrival of bootstrap messages:
bsubsection*Initial States and Timer Events
1
2 If the router is a Candidate-BSR:
1
2 The router operates initially in the `CandBSR' state,
where it does not originate any bootstrap messages.
3 If the bootstrap-timer expires, and the current state
is `CandBSR', the router originates a bootstrap
message carrying the local RP-Set and its own BSR
priority and address, restarts the bootstrap-timer at
[Bootstrap-Period] seconds, and transits into the
`ElectedBSR' state. Note that the actual sending of
the bootstrap message may be delayed by a random value
to reduce transient control overhead. To obtain best
results, the random value is set such that the
preferred BSR is the first to originate a bootstrap
message. We propose the following as an efficient
implementation of the random value delay (in seconds):
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:
1 if ( bestPriority equals myPriority) then
[AddrDelay = log_2(bestAddr - myAddr) / 16, ]
2 else [AddrDelay = 2 - (myAddr / 2^31) ]
where myAddr is the Candidate-BSR's address, and
bestAddr is the stored BSR's address.
4 If the bootstrap-timer expires, and the current state
is `ElectedBSR', the router originates a bootstrap
message, and restarts the RP-Set timer at [Bootstrap-
Period]. No state transition is incurred.
This way, the elected BSR originates periodic
bootstrap messages every [Bootstrap-Period].
3 If a router is not a Candidate-BSR:
1
2 The router operates initially in the `AxptAny' state.
In such state, a router accepts the first bootstrap
message from the The Reverse Path Forwarding (RPF)
neighbor toward the included BSR. The RPF neighbor in
this case is the next hop router en route to the
included BSR.
3 If the bootstrap-timer expires, and the current state
is `AxptPref'-- where the router accepts only
preferred bootstrap messages (those that carry BSR-
priority and address higher than, or equal to,
`LclBSR') from the RPF neighbor toward the included
BSR-- the router transits into the `AxptAny' state.
In this case, if an elected BSR becomes unreachable,
the routers start accepting bootstrap messages from
another Candidate-BSR after the bootstrap-timer
expires. All PIM routers within a domain converge on
the preferred reachable Candidate-BSR.
Receiving Bootstrap Message:
To avoid loops, an RPF check is performed on the included BSR
address. Upon receiving a bootstrap message from the RPF
neighbor toward the included BSR, the following actions are
taken:
1 If the router is not a Candidate-BSR:
1 If the current state is `AxptAny', the router accepts
the bootstrap message, and transits into the
`AxptPref' state.
2 If the current state is `AxptPref', and the bootstrap
message is preferred, the message is accepted. No
state transition is incurred.
2 If the router is a Candidate-BSR, and the bootstrap message
is preferred, the message is accepted. Further, if this
happens when the current state is `Elected BSR', the router
transits into the `CandBSR' state.
When a bootstrap message is accepted, the router restarts the
bootstrap-timer at [Bootstrap-Timeout], stores the received BSR
priority and address in `LclBSR', and the received RP-Set in
`LclRP-Set', and forwards the bootstrap message out all
interfaces except the receiving interface.
If a bootstrap message is rejected, no state transitions are
triggered.
6.3 Appendix III: Glossary of Terms
Following is an alphabetized list of terms and definitions used
throughout this specification.
* { Bootstrap router (BSR)}. A BSR is a dynamically elected
router within a PIM domain. It is responsible for constructing
the RP-Set and originating Bootstrap messages.
* { Candidate-BSR (C-BSR)}. A C-BSR is a router configured to
participate in the BSR election and act as BSRs if elected.
* { Candidate RP (C-RP)}. A C-RP is a router configured to
send periodic Candidate-RP-Advertisement messages to the BSR,
and act as an RP when it receives Join/Prune or Register
messages for the advertised group prefix.
* { Designated Router (DR)}. The DR sets up multicast route
entries and sends corresponding Join/Prune and Register
messages on behalf of directly-connected receivers and
sources, respectively. The DR may or may not be the same
router as the IGMP Querier. The DR may or may not be the
long-term, last-hop router for the group; a router on the LAN
that has a lower metric route to the data source, or to the
group's RP, may take over the role of sending Join/Prune
messages.
* { Incoming interface (iif)}. The iif of a multicast route
entry indicates the interface from which multicast data
packets are accepted for forwarding. The iif is initialized
when the entry is created.
* Join list. The Join list is one of two lists of addresses
that is included in a Join/Prune message; each address refers
to a source or RP. It indicates those sources or RPs to which
downstream receiver(s) wish to join.
* { Last-hop router}. The last-hop router is the last router
to receive multicast data packets before they are delivered to
directly-connected member hosts. In general the last-hop
router is the DR for the LAN. However, under various
conditions described in this document a parallel router
connected to the same LAN may take over as the last-hop router
in place of the DR.
* { Outgoing interface (oif) list}. Each multicast route
entry has an oif list containing the outgoing interfaces to
which multicast packets should be forwarded.
* Prune List. The Prune list is the second list of addresses
that is included in a Join/Prune message. It indicates those
sources or RPs from which downstream receiver(s) wish to
prune.
* { PIM Multicast Border Router (PMBR)}. A PMBR connects a
PIM domain to other multicast routing domain(s).
* { Rendezvous Point (RP)}. Each multicast group has a
shared-tree via which receivers hear of new sources and new
receivers hear of all sources. The RP is the root of this
per-group shared tree, called the RP-Tree.
* { RP-Set}. The RP-Set is a set of RP addresses constructed
by the BSR based on Candidate-RP advertisements received. The
RP-Set information is distributed to all PIM routers in the
BSR's PIM domain.
* { Reverse Path Forwarding (RPF)}. RPF is used to select the
appropriate incoming interface for a multicast route entry .
The RPF neighbor for an address X is the the next-hop router
used to forward packets toward X. The RPF interface is the
interface to that RPF neighbor. In the common case this is the
next hop used by the unicast routing protocol for sending
unicast packets toward X. For example, in cases where unicast
and multicast routes are not congruent, it can be different.
* { Route entry.} A multicast route entry is state maintained
in a router along the distribution tree and is created, and
updated based on incoming control messages. The route entry
may be different from the forwarding entry; the latter is used
to forward data packets in real time. Typically a forwarding
entry is not created until data packets arrive, the forwarding
entry's iif and oif list are copied from the route entry, and
the forwarding entry may be flushed and recreated at will.
* { Shortest path tree (SPT)}. The SPT is the multicast
distribution tree created by the merger of all of the shortest
paths that connect receivers to the source (as determined by
unicast routing).
* { Sparse Mode (SM)}. SM is one mode of operation of a
multicast protocol. PIM SM uses explicit Join/Prune messages
and Rendezvous points in place of Dense Mode PIM's and DVMRP's
broadcast and prune mechanism.
* { Wildcard (WC) multicast route entry}. Wildcard multicast
route entries are those entries that may be used to forward
packets for any source sending to the specified group.
Wildcard bots in the join list of a Join/Prune message
represent either a (*,G) or (*,*,RP) join; in the prune list
they represent a (*,G) prune.
* { (S,G) route entry}. (S,G) is a source-specific route
entry. It may be created in response to data packets,
Join/Prune messages, or Asserts. The (S,G) state in routers
creates a source-rooted, shortest path (or reverse shortest
path) distribution tree. (S,G)RPT bit entries are source-
specific entries on the shared RP-Tree; these entries are used
to prune particular sources off of the shared tree.
* { (*,G) route entry}. Group members join the shared RP-Tree
for a particular group. This tree is represented by (*,G)
multicast route entries along the shortest path branches
between the RP and the group members.
* { (*,*,RP) route entry}. (*,*,RP) refers to any source and
any multicast group that maps to the RP included in the entry.
The routers along the shortest path branches between a
domain's RP(s) and its PMBRs keep (*,*,RP) state and use it to
determine how to deliver packets toward the PMBRs if data
packets arrive for which there is not a longer match. The
wildcard group in the (*,*,RP) route entry is represented by a
group address of 224.0.0.0 and a mask length of 4 bits.
References
1. Deering, S., Estrin, D., Farinacci, D., Jacobson, V., Liu, C.,
Wei, L., Sharma, P., and A. Helmy, "Protocol Independent Multicast
(pim): Motivation and Architecture", Work in Progress.
2. S. Deering, D. Estrin, D. Farinacci, V. Jacobson, C. Liu, and L.
Wei. The pim architecture for wide-area multicast routing. ACM
Transactions on Networks, April 1996.
3. Estrin, D., Farinacci, D., Jacobson, V., Liu, C., Wei, L., Sharma,
P., and A. Helmy, "Protocol Independent Multicast-dense Mode (pim-
dm): Protocol Specification", Work in Progress.
4. Deering, S., "Host Extensions for IP Multicasting", STD 5, RFC
1112, August 1989.
5. Fenner, W., "Internet Group Management Protocol, Version 2", RFC
2236, November 1997.
6. Atkinson, R., "Security Architecture for the Internet Protocol",
RFC1825, August 1995.
7. Mark R. Nelson. File verification using CRC. Dr. Dobb's
Journal, May 1992.
8. A.J. Ballardie, P.F. Francis, and J.Crowcroft. Core based trees.
In Proceedings of the ACM SIGCOMM, San Francisco, 1993.
Authors' Addresses
NOTE: The author list has been reordered to reflect the involvement
in detailed editorial work on this specification document. The first
four authors are the primary editors and are listed alphabetically.
The rest of the authors, also listed alphabetically, participated in
all aspects of the architectural and detailed design but managed to
get away without hacking the latex!
Deborah Estrin
Computer Science Dept/ISI
University of Southern Calif.
Los Angeles, CA 90089
EMail: estrin@usc.edu
Dino Farinacci
Cisco Systems Inc.
170 West Tasman Drive,
San Jose, CA 95134
EMail: dino@cisco.com
Ahmed Helmy
Computer Science Dept.
University of Southern Calif.
Los Angeles, CA 90089
EMail: ahelmy@catarina.usc.edu
David Thaler
EECS Department
University of Michigan
Ann Arbor, MI 48109
EMail: thalerd@eecs.umich.edu
Stephen Deering
Xerox PARC
3333 Coyote Hill Road
Palo Alto, CA 94304
EMail: deering@parc.xerox.com
Mark Handley
Department of Computer Science
University College London
Gower Street
London, WC1E 6BT
UK
EMail: m.handley@cs.ucl.ac.uk
Van Jacobson
Lawrence Berkeley Laboratory
1 Cyclotron Road
Berkeley, CA 94720
EMail: van@ee.lbl.gov
Ching-gung Liu
Computer Science Dept.
University of Southern Calif.
Los Angeles, CA 90089
EMail: charley@catarina.usc.edu
Puneet Sharma
Computer Science Dept.
University of Southern Calif.
Los Angeles, CA 90089
EMail: puneet@catarina.usc.edu
Liming Wei
Cisco Systems Inc.
170 West Tasman Drive,
San Jose, CA 95134
EMail: lwei@cisco.com
Full Copyright Statement
Copyright (C) The Internet Society (1998). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.