draft-ietf-pim-v2-dm-01.txt   draft-ietf-pim-v2-dm-02.txt 
Network Working Group Stephen Deering (Cisco)
Network Working Group Stephen Deering (cisco)
Internet Draft Deborah Estrin (USC) Internet Draft Deborah Estrin (USC)
Dino Farinacci (cisco) Dino Farinacci (Cisco)
Van Jacobson (LBL) Van Jacobson (Cisco)
Ahmed Helmy (USC) Ahmed Helmy (USC)
David Meyer (cisco) David Meyer (Cisco)
Liming Wei (cisco) Liming Wei (Cisco)
Protocol Independent Multicast Version 2 Dense Mode Specification Protocol Independent Multicast Version 2 Dense Mode Specification
Status of This Memo Status of This Memo
This document is an Internet Draft. Internet Drafts are working This document is an Internet-Draft and is in full conformance
documents of the Internet Engineering Task Force (IETF), its Areas, with all provisions of Section 10 of RFC2026.
and its Working Groups. (Note that other groups may also distribute
working documents as Internet Drafts).
Internet Drafts are draft documents valid for a maximum of six Internet-Drafts are working documents of the Internet Engineering
months. Internet Drafts may be updated, replaced, or obsoleted by Task Force (IETF), its areas, and its working groups. Note that
other documents at any time. It is not appropriate to use Internet other groups may also distribute working documents as Internet-
Drafts as reference material or to cite them other than as a Drafts.
``working'' draft'' or ``work in progress.''
Please check the I-D abstract listing contained in each Internet Internet-Drafts are draft documents valid for a maximum of six months
Draft directory to learn the current status of this or any other and may be updated, replaced, or obsoleted by other documents at any
Internet Draft. time. It is inappropriate to use Internet- Drafts as reference
material or to cite them other than as work in progress.
Deering,Estrin,Farinacci,Jacobson,Helmy,Meyer,Wei [Page 1] The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
1 Introduction 1 Introduction
This specification defines a multicast routing algorithm efficient for This specification defines a multicast routing algorithm efficient for
multicast groups that are densely distributed across a network. This multicast groups that are densely distributed across a network. This
protocol does not have a topology discovery mechanism often used by a protocol does not have a topology discovery mechanism often used by a
unicast routing protocol. It employes the same packet formats sparse- unicast routing protocol. It employs the same packet formats sparse-
mode PIM [PIMSM] uses. This protocol is called dense-mode PIM. The mode PIM [PIMSM] uses. This protocol is called dense-mode PIM. The
foundation of this design was largely built on Deering's early work on foundation of this design was largely built on Deering's early work on
IP multicast routing [Deering91]. IP multicast routing [Deering91].
2 Terminology 2 Terminology
The key words ``MUST'', ``MUST NOT'', ``REQUIRED'', ``SHALL'', ``SHALL The key words ``MUST'', ``MUST NOT'', ``REQUIRED'', ``SHALL'', ``SHALL
NOT'', ``SHOULD'', ``SHOULD NOT'', ``RECOMMENDED'', ``MAY'', and NOT'', ``SHOULD'', ``SHOULD NOT'', ``RECOMMENDED'', ``MAY'', and
``OPTIONAL'' in this document are to be interpreted as described in ``OPTIONAL'' in this document are to be interpreted as described in
RFC 2119. RFC 2119.
skipping to change at line 72 skipping to change at page 3, line 4
This mechanism provides sufficient topological information This mechanism provides sufficient topological information
for a router to determine whether a neighbor system is for a router to determine whether a neighbor system is
upstream with respect to each multicast source. Some topology upstream with respect to each multicast source. Some topology
discovery mechanism can also determine if a neighbor is discovery mechanism can also determine if a neighbor is
downstream with respect to each multicast source. An existing downstream with respect to each multicast source. An existing
unicast routing protocol or a clone of it is sometimes used unicast routing protocol or a clone of it is sometimes used
for this purpose (such as in DVMRP[DVMRP]). When a multicast for this purpose (such as in DVMRP[DVMRP]). When a multicast
routing protocol has a topology discovery mechanism built-in, routing protocol has a topology discovery mechanism built-in,
the topology discovery mechanism is sometimes referred to as the topology discovery mechanism is sometimes referred to as
the unicast routing part of the protocol (even though it is the unicast routing part of the protocol (even though it is
Deering,Estrin,Farinacci,Jacobson,Helmy,Meyer,Wei [Page 2]
not used for forwarding unicast packets). not used for forwarding unicast packets).
4 PIM-DM Protocol Overview 4 PIM-DM Protocol Overview
Dense-mode PIM assumes that when a source starts sending, all Dense-mode PIM assumes that when a source starts sending, all
downstream systems want to receive multicast datagrams. Initially, downstream systems want to receive multicast datagrams. Initially,
multicast datagrams are flooded to all areas of the network. If some multicast datagrams are flooded to all areas of the network. If some
areas of the network do not have group members, dense-mode PIM will areas of the network do not have group members, dense-mode PIM will
prune off the forwarding branch by setting up prune state. The prune prune off the forwarding branch by setting up prune state. The prune
state has an associated timer, which on expiration will turn into state has an associated timer, which on expiration will turn into
skipping to change at line 118 skipping to change at page 4, line 5
each interface leads to any downstream neighbors for a particular each interface leads to any downstream neighbors for a particular
source. We chose to accept the additional overhead in favor of the source. We chose to accept the additional overhead in favor of the
simplification and flexibility gained by not depending on a specific simplification and flexibility gained by not depending on a specific
type of topology discovery protocol. type of topology discovery protocol.
In relation to sparse-mode PIM, dense-mode PIM differs in two In relation to sparse-mode PIM, dense-mode PIM differs in two
essential ways: 1) there are no periodic joins transmitted, only essential ways: 1) there are no periodic joins transmitted, only
explicit triggered grafts/prunes, and 2) there is no Rendezvous Point explicit triggered grafts/prunes, and 2) there is no Rendezvous Point
(RP). (RP).
Deering,Estrin,Farinacci,Jacobson,Helmy,Meyer,Wei [Page 3]
5 Protocol Description 5 Protocol Description
Dense mode PIM initiates forwarding state in routers when a source Dense mode PIM initiates forwarding state in routers when a source
begins to send. A source does not give any prior notifications to the begins to send. A source does not give any prior notifications to the
network when it sends multicast datagrams to a group G. If a receiving network when it sends multicast datagrams to a group G. If a receiving
router does not already have a forwarding entry, it creates it for the router does not already have a forwarding entry, it creates it for the
source and group G. This forwarding entry is called a (S,G) entry. It source and group G. This forwarding entry is called a (S,G) entry. It
includes the following contents: source address, group address, the includes the following contents: source address, group address, the
incoming interface, a list of outgoing interfaces, a few flags and a incoming interface, a list of outgoing interfaces, a few flags and a
few timers. The incoming interface for (S,G) is determined by an RPF few timers. The incoming interface for (S,G) is determined by an RPF
skipping to change at line 162 skipping to change at page 4, line 47
forwarding entry expiration and the adaptation to topology changes. forwarding entry expiration and the adaptation to topology changes.
5.1 Leaf network detection 5.1 Leaf network detection
In dense mode PIM, prune state is first instantiated on routers In dense mode PIM, prune state is first instantiated on routers
connected to leaf networks without group members. A network on a connected to leaf networks without group members. A network on a
router interface is deemed a leaf if there is no other PIM neighbors router interface is deemed a leaf if there is no other PIM neighbors
on that network. The notion of leaf network here might be slightly on that network. The notion of leaf network here might be slightly
different from that defined in other protocols. [*] different from that defined in other protocols. [*]
_________________________ _________________________
[*] E.g. In DVMRP a leaf network for a source is de- [*] E.g. In DVMRP a leaf network for a source is
fined as one without downstream neighbor DVMRP routers. defined as one without downstream neighbor DVMRP
Each DVMRP router is able to decide whether it has a routers. Each DVMRP router is able to decide whether it
downstream DVMRP neighbor with respect to each source. has a downstream DVMRP neighbor with respect to each
This is due to the RIP-like mechanism used in its to- source. This is due to the RIP-like mechanism used in
Deering,Estrin,Farinacci,Jacobson,Helmy,Meyer,Wei [Page 4]
A router determines it is a leaf by not receiving PIM Hello messages. A router determines it is a leaf by not receiving PIM Hello messages.
A leaf router can detect that there are no members downstream when it A leaf router can detect that there are no members downstream when it
is the only router on a network and there are no IGMP Host-Report is the only router on a network and there are no IGMP Host-Report
messages received from hosts. A router should not populate a messages received from hosts. A router should not populate a
forwarding entry's outgoing interface list with a leaf network forwarding entry's outgoing interface list with a leaf network
interface without downstream members. interface without downstream members.
It should be noted that a non-leaf router in PIM dense-mode is not It should be noted that a non-leaf router in PIM dense-mode is not
necessarily a non-leaf node on a particular multicast forwarding tree. necessarily a non-leaf node on a particular multicast forwarding tree.
There are topologies where two parallel routers are connected to a There are topologies where two parallel routers are connected to a
common LAN where none of the routers uses the other one to reach a common LAN where none of the routers uses the other one to reach a
source. Therefore both routers will be leaves of any forwarding trees source. Therefore both routers will be leaves of the shortest path
rooted at the source. When there are no group members on this LAN, tree rooted at the source. When there are no group members on this
both routers must not forward packets onto it. This is achieved by an LAN, both routers must not forward packets onto it. This is achieved
assert process. Please see section 5.5 for more details. by an assert process. See section 5.5 for more details.
A dense mode PIM implementation must take proper actions when a non- A dense mode PIM implementation must take proper actions when a non-
leaf router becomes a leaf router. When the last PIM neighbor on an leaf router becomes a leaf router. When the last PIM neighbor on an
interface goes away and turns the connected subnet into a leaf interface goes away and turns the connected subnet into a leaf
network, the router should delete that interface from the outgoing network, the router should delete that interface from the outgoing
interface lists of all groups without attached group members. interface lists of all groups without attached group members.
5.2 Pruning of branches 5.2 Pruning of branches
5.2.1 Pruning on multi-access LANs and prune-override 5.2.1 Pruning on multi-access LANs and prune-override
To avoid PIM-Prune message storms, PIM-Prune messages must not be sent To avoid PIM Prune message storms, PIM Prune messages must not be sent
on LANs in response to each received multicast packet that is on LANs in response to each received multicast packet that is
associated with an existing negative cache entry. associated with an existing negative cache entry.
A prune is sent upstream when a router creates a (S,G) entry with an A prune is sent upstream when a router creates a (S,G) negative cache
empty outgoing interface list, or when the outgoing interface list entry, or when the entry turns into a negative cache. Prune
becomes empty. [*] information is flushed periodically. This causes multicast datagrams
to be sent in RPF mode again which in turn triggers prune messages.
Prune information is flushed periodically. This causes multicast
datagrams to be sent in RPF mode again which in turn triggers prune
messages.
When a prune message is sent onto an upstream LAN, it is data link When a prune message is sent onto an upstream LAN, it is data link
multicast and IP addressed to the all PIM routers group address multicast and IP addressed to the all PIM routers group address
224.0.0.13. The router to process the prune will be indicated by 224.0.0.13. The router to process the prune will be indicated by
inclusion of its address in the "Address" field of the message. This inclusion of its address in the "Address" field of the message. This
address is obtained by an RPF look up for the source. When the prune address is obtained by an RPF look up for the source. When the prune
_________________________ message is sent, the expected upstream router will schedule a prune
pology discovery (or ``unicast routing'') protocol. request of the LAN from its outgoing interfaces for the (S,G) entry.
[*] I.e. the set of forwarding interfaces in the out- The suggested default delay time before deletion is 3 seconds.
going interface list is NULL.
Deering,Estrin,Farinacci,Jacobson,Helmy,Meyer,Wei [Page 5] _________________________
message is sent, the expected upstream router will schedule a deletion its topology discovery (or ``unicast routing'')
request of the LAN from its outgoing interfaces for the (S,G) entry protocol.
from the prune list. The suggested delay time before deletion should
be greater than 3 seconds. The default prune delay time is 3 seconds.
Other routers on the LAN will hear the prune message and respond with Other routers on the LAN will hear the prune message and respond with
a join if they still expect multicast datagrams from the expected a join if they still expect multicast datagrams from the expected
upstream router. The PIM-Join message is data link multicast and IP upstream router. The Join message is data link multicast and IP
addressed to the all PIM routers group address 224.0.0.13. The router addressed to the all PIM routers group address 224.0.0.13. The router
to process the join will be indicated by inclusion of its address in to process the join will be indicated by inclusion of its address in
the "Address" field of the message. The address is determined by an the "Address" field of the message. The address is determined by an
RPF lookup for the source. When the expected router receives the join RPF lookup for the source. When the expected router receives the join
message, it will cancel the deletion request. This process is called message, it will cancel the prune request. This process is called
prune-override. prune-override.
Routers that need to send prune-override joins will randomly generate Routers that need to send prune-override joins will randomly generate
a join message delay timer. If a join is heard from another router a join message delay timer. If a join is heard from another router
before a router sends its own, it will cancel sending its own join. before a router sends its own, it will cancel sending its own join.
This will reduce control traffic on the LAN. The maximum join delay This will reduce control traffic on the LAN. The maximum join delay
timer should be equal to or smaller than the prune delay timer value. timer should be equal to or smaller than the prune delay timer value.
The default is 3 seconds. The default is 3 seconds.
If the expected upstream router does not receive any PIM-Join messages If the expected upstream router does not receive any PIM Join messages
before the scheduled expiration time for the deletion request, it before the scheduled expiration time for the deletion request, it
prunes the outgoing LAN interface from the (S,G) multicast forwarding prunes the outgoing LAN interface from the (S,G) multicast forwarding
entry. entry.
However, if the prune-override join message is lost, the deletion will However, if the prune-override join message is lost, the deletion will
occur and there will be no data delivery for the amount of time the occur and there will be no data delivery for the amount of time the
interface remains in prune state. To reduce the probability of this interface remains in prune state. To reduce the probability of this
occurance, a router that has scheduled to prune the interface off is occurence, a router that has scheduled to prune the interface off
required to immediately send a prune onto the interface. This gives should immediately send a prune onto the interface. This gives other
other routers another chance to hear the prune, and to respond with a routers another chance to hear the prune, and to respond with a join.
join.
Additionally, equal-cost paths leading to a LAN presents a special Additionally, equal-cost paths leading to a LAN presents a special
case for join/prune processing. When an upstream router is chosen by case for join/prune processing. When an upstream router is chosen by
an RPF lookup there may be equal-cost paths to reach the source. The an RPF lookup there may be equal-cost paths to reach the source. The
higher IP addressed system is always chosen. If the unicast routing higher IP addressed system is always chosen. If the unicast routing
protocol does not store all available equal-cost paths in the routing protocol does not store all available equal-cost paths in the routing
table, the "Address" field may contain the address of the wrong table, the "Address" field may contain the address of the wrong
upstream router. To avoid this situation, the "Address" field may upstream router. To avoid this situation, the "Address" field may
optionally be set to 0.0.0.0 which means that all upstream routers optionally be set to 0.0.0.0 which means that all upstream routers
(the ones that have the LAN as an outgoing interface for the (S,G) (the ones that have the LAN as an outgoing interface for the (S,G)
entry) may process the packet. entry) may process the packet.
Deering,Estrin,Farinacci,Jacobson,Helmy,Meyer,Wei [Page 6]
5.2.2 Pruning a Point-to-point link 5.2.2 Pruning a Point-to-point link
PIM-Prune messages received on a point to point link are not delayed Prune messages received on a point to point link are not delayed
before processing as they are in the LAN procedure. If the prune is before processing as they are in the LAN procedure. If the prune is
received on an interface that is in the outgoing interface list, it is received on an interface in the outgoing interface list, it is pruned
deleted immediately. immediately.
Prunes may be rate-limited on point-to-point interfaces when a Prunes may be rate-limited on point-to-point interfaces when a
multicast datagram is received for a negative cache entry, or if the multicast datagram is received for a negative cache entry, or if the
point-to-point interface receiving the datagram is not the RPF point-to-point interface receiving the datagram is not the RPF
interface toward the source. interface toward the source.
5.3 New members joining an existing group 5.3 New members joining an existing group
If a router is directly connected to a host that wants to become a If a router is directly connected to a host that wants to become a
member of a group, the router may send a PIM-Graft message toward member of a group, the router may send a Graft message toward known
known sources. This allows join latency to be reduced below that sources. This allows join latency to be reduced below that indicated
indicated by the relatively large timeout value suggested for prune by the relatively large timeout value suggested for prune information.
information.
The host indicates its interest in group G by sending an IGMP report. The host indicates its interest in group G by sending an IGMP report.
If a receiving router has state for group G, it adds the interface on If a receiving router has state for group G, it adds the interface on
which the IGMP Report or PIM-Graft was received for all known (S,G)'s. which the IGMP Report or Graft was received for all known (S,G)'s. If
If the (S,G) entry was a negative cache entry, the router sends a the (S,G) entry was a negative cache entry, the router sends a Graft
PIM-Graft message upstream toward S. message upstream toward S.
A router receiving the PIM-Graft message adds the received interface A router receiving the Graft message adds the received interface into
into the matching (S,G) entry's outgoing interface list. If the entry the matching (S,G) entry's outgoing interface list. If the entry
transitions to forward state due to this added outgoing interface, the transitions to forward state due to this added outgoing interface, the
router must send a PIM-Graft message toward the source. router must send a Graft message toward the source.
Routers with no group state do nothing on receipt of IGMP reports, Routers with no group state do nothing on receipt of IGMP reports,
since dense-mode PIM will deliver multicast datagrams to all since dense-mode PIM will deliver multicast datagrams to all
interfaces when creating state for a group. interfaces when creating state for a group.
PIM-Graft message is the only PIM message that uses a positive Graft message is the only PIM message that uses a positive
acknowledgment strategy. Senders of PIM-Graft messages unicast them to acknowledgment strategy. Senders of Graft messages unicast them to
their upstream RPF neighbors. The neighbor processes each (S,G) and their upstream RPF neighbors. The neighbor processes each (S,G) and
immediately acknowledges each (S,G) in a PIM-GraftAck message. This is immediately acknowledges each (S,G) in a GraftAck message. This is
relatively easy, since the receiver simply changes the PIM message relatively easy, since the receiver simply changes the PIM message
type from Graft to Graft-Ack and unicasts the original packet back to type from Graft to Graft-Ack and unicasts the original packet back to
the source. The sender periodically retransmits the PIM-Graft message the source. The sender periodically retransmits the Graft message for
for any (S,G) that has not been acknowledged. The interval between any (S,G) that has not been acknowledged. The interval between each
each retransmission is 3 seconds. Note that the sender need not keep a retransmission is 3 seconds. Note that the sender need not keep a
retransmission list for each neighbor since PIM-Grafts are only sent retransmission list for each neighbor since Grafts are only sent to
the RPF neighbor. Only the (S,G) entry needs to be tagged for
Deering,Estrin,Farinacci,Jacobson,Helmy,Meyer,Wei [Page 7]
to the RPF neighbor. Only the (S,G) entry needs to be tagged for
retransmission. retransmission.
5.4 Designated Router Election 5.4 Designated Router Election
Dense mode PIM itself does not need the function of a designated Dense mode PIM itself does not need the function of a designated
router (DR). But a DR is needed on multi-access LANs running IGMP router (DR). But a DR is needed on multi-access LANs running IGMP
version 1, which relies on a routing protocol to select a query router version 1, which relies on a routing protocol to select a query router
for the purpose of sending IGMP Host-Query messages. Dense-mode PIM for the purpose of sending IGMP Host-Query messages. Dense-mode PIM
designated router (DR) election has the same procedure sparse-mode PIM designated router (DR) election has the same procedure sparse-mode PIM
uses. uses.
Each PIM router connected to a multi-access LAN should periodicly Each PIM router connected to a multi-access LAN should periodically
transmit PIM-Hello messages onto the LAN. The period is specified as transmit Hello messages onto the LAN. The period is specified as
[Hello-Timer] in the sparse mode specification (default 30 seconds). [Hello-Timer] in the sparse mode specification (default 30 seconds).
The highest IP addressed router becomes the DR. The discovered PIM The highest IP addressed router becomes the DR. The discovered PIM
routers should be timed out after 105 seconds (the [Neighbor-Timer] in routers should be timed out after [Neighbor-Timer] (default 105
the PIM-SM specification]. If the DR goes down, a new DR is elected. seconds) in the PIM-SM specification. If the DR goes down, a new DR is
elected.
DR election is only necessary on multi-access networks. DR election is only necessary on multi-access networks.
5.5 Parallel paths to a source 5.5 Parallel paths to a source
Two or more routers may receive the same multicast datagram that was Two or more routers may receive the same multicast datagram replicated
replicated upstream. In particular, if two routers have equal cost upstream. In particular, if two routers have equal cost paths to a
paths to a source and are connected on a common multi-access network, source and are connected on a common multi-access network, duplicate
duplicate datagrams will travel downstream onto the LAN. Dense-mode datagrams will travel downstream onto the LAN. Dense-mode PIM will
PIM will detect such a situation and will not let it persist. detect such a situation and will not let it persist.
If a router receives a multicast datagram on an outgoing interface on If a router receives a multicast datagram on an outgoing interface on
a multi-access LAN, the packet must be a duplicate. In this case a a multi-access LAN, the packet must be a duplicate. In this case a
single forwarder must be elected. Using PIM Assert messages addressed single forwarder must be elected. The upstream routers can decide
to 224.0.0.13 on the LAN, upstream routers can decide which one which one becomes the forwarder, using Assert messages addressed to
becomes the forwarder. Downstream routers listen to the Asserts so 224.0.0.13 on the LAN. Downstream routers listen to the Asserts so
they know which one was elected (typically this is the same as the they know which one was elected (typically this is the same as the
downstream router's RPF neighbor but there are circumstances when downstream router's RPF neighbor but there are circumstances when
using different unicast protocols where this might not be the case). using different unicast protocols where this might not be the case).
The upstream router elected is the one that has the best metric to the The upstream router elected is the one that has the best metric to the
source. When a packet is received on an outgoing interface, a router source. When a packet is received on an outgoing interface, a router
will send an Assert packet on the LAN indicating what metric it uses will send an Assert packet on the LAN indicating what metric it uses
to reach the source of the data packet. If metrics are comparable, the to reach the source of the data packet. If metrics are comparable, the
router with the best metric will become the forwarder. Incomparable router with the best metric will become the forwarder. Incomparable
metrics will be discussed later in this section when metric preference metrics will be discussed later in this section when metric preference
is described. All other upstream routers will delete the interface is described. All other upstream routers will prune the interface from
from their outgoing interface list. The downstream routers also do the their outgoing interface list. The downstream routers also do the
Deering,Estrin,Farinacci,Jacobson,Helmy,Meyer,Wei [Page 8]
comparison in case the forwarder is different than the RPF neighbor. comparison in case the forwarder is different than the RPF neighbor.
This is important so downstream routers send subsequent Prunes or This is important so downstream routers send subsequent Prunes or
Grafts to the correct neighbor. Grafts to the correct neighbor.
Associated with the metric is a metric preference value. This is Associated with the metric is a metric preference value. This is
provided to deal with the case where the upstream routers may run provided to deal with the case where the upstream routers may run
different unicast routing protocols. The numerically smaller metric different unicast routing protocols. The numerically smaller metric
preference is always preferred. The metric preference should be preference is always preferred. The metric preference should be
treated as the high-order part of an Assert metric comparison. treated as the high-order part of an Assert metric comparison.
Therefore, a metric value can be compared with another metric value Therefore, a metric value can be compared with another metric value
skipping to change at line 404 skipping to change at page 9, line 40
1 Compare metric received in Assert with the one you would have 1 Compare metric received in Assert with the one you would have
advertised in an Assert. If the value in the Assert is less than advertised in an Assert. If the value in the Assert is less than
your value, prune the interface. If the value is the same, and your value, prune the interface. If the value is the same, and
your address is less than the Assert sender, prune the interface. your address is less than the Assert sender, prune the interface.
2 If you have won the election and there are directly connected 2 If you have won the election and there are directly connected
members on the LAN, keep the interface in your outgoing interface members on the LAN, keep the interface in your outgoing interface
list. You are the forwarder for the LAN. list. You are the forwarder for the LAN.
Deering,Estrin,Farinacci,Jacobson,Helmy,Meyer,Wei [Page 9]
3 If you have won the election but there are no directly connected 3 If you have won the election but there are no directly connected
members on the LAN, schedule to prune the interface. The LAN might members on the LAN, schedule to prune the interface. The LAN might
be a stub LAN with no members (and no downstream routers). If no be a stub LAN with no members (and no downstream routers). If no
subsequent Joins are received, delete the interface from the subsequent Joins are received, prune the interface from the
outgoing interface list. Otherwise keep the interface in your outgoing interface list. Otherwise keep the interface in your
outgoing interface. You are the forwarder for the LAN. outgoing interface. You are the forwarder for the LAN.
4 The assert winner sends an assert with its own metric on the LAN, 4 The assert winner SHOULD send an assert with its own metric on the
so that all other routers know who the winner is. LAN, so that all other routers know who the winner is.
Asserts received on incoming interface: Asserts received on incoming interface:
1 Downstream routers will select the upstream router with the 1 Downstream routers will select the upstream router with the
smallest metric as their RPF neighbor. If two metrics are the smallest metric as their RPF neighbor. If two metrics are the
same, the highest IP address is chosen to break the tie. same, the highest IP address is chosen to break the tie.
If the upstream router selected is different from the RPF neighbor If the upstream router selected is different from the RPF neighbor
selected natively, it should start an Assert-Timer. When this selected natively, it should start an Assert-Timer. When this
timer expires, it restores the RPF information obtained by the RPF timer expires, it restores the RPF information obtained by the RPF
skipping to change at line 447 skipping to change at page 10, line 40
multicast routing entry itself, one for each pruned interface in the multicast routing entry itself, one for each pruned interface in the
outgoing interface list and one to time out information about upstream outgoing interface list and one to time out information about upstream
assert winner (Assert_timer). An outgoing interface in forward state assert winner (Assert_timer). An outgoing interface in forward state
does not time out or change state without external events. The does not time out or change state without external events. The
outgoing interface stays in forward state in the list as long as there outgoing interface stays in forward state in the list as long as there
is a group member connected, or there is a downstream PIM neighbor is a group member connected, or there is a downstream PIM neighbor
that has not sent a prune to it. The interface is deleted from the that has not sent a prune to it. The interface is deleted from the
outgoing interface list if it is on a leaf network and there is no outgoing interface list if it is on a leaf network and there is no
connected member. The interface timer for a pruned interface should be connected member. The interface timer for a pruned interface should be
started with the holdtime in the prune message (also referred to as started with the holdtime in the prune message (also referred to as
Deering,Estrin,Farinacci,Jacobson,Helmy,Meyer,Wei [Page 10]
the prune timer). the prune timer).
When a (S,G) entry is in forwarding state, its expiration timer is set When a (S,G) entry is in forwarding state, its expiration timer is set
to [Data-Timeout], as specified in the companion sparse mode to [Data-Timeout], as specified in the companion sparse mode
specification [PIMSM], which is 210 seconds by default. This timer is specification [PIMSM], default is 210 seconds. This timer is restarted
restarted when a data packet is being forwarded. The (S,G) entry is when a data packet is forwarded. The (S,G) entry is deleted when this
deleted if this timer expires. timer expires.
Once all interfaces in the outgoing interface list are pruned, the Once all interfaces in the outgoing interface list are pruned, the
(S,G)'s expiration timer should be set to the maximum prune timer (S,G)'s expiration timer should be set to the maximum prune timer
among all its outgoing interfaces. During this time the entry is known among all its outgoing interfaces. During this time the entry is known
as a negative cache entry. as a negative cache entry.
If the prune timers on different outgoing interfaces are different, If the prune timers on different outgoing interfaces are different,
the pruned interface with the shortest remaining timer may expire the pruned interface with the shortest remaining timer may expire
first and turn the negative cache entry into forwarding state. When first and turn the negative cache entry into forwarding state. When
this happens, a graft should be triggered upstream. When a negative this happens, a graft should be triggered upstream. When a negative
skipping to change at line 488 skipping to change at page 11, line 36
5.7 Adapting to unicast route changes 5.7 Adapting to unicast route changes
When unicast route changes occur, the RPF interface for many (S,G) When unicast route changes occur, the RPF interface for many (S,G)
entries will also change. The following should be done for the entries will also change. The following should be done for the
affected entries: affected entries:
1 A prune should be sent toward the old incoming interface; 1 A prune should be sent toward the old incoming interface;
2 A graft should be sent to the new RPF neighbor. 2 A graft should be sent to the new RPF neighbor.
Deering,Estrin,Farinacci,Jacobson,Helmy,Meyer,Wei [Page 11] 6 Generation Identifier (GenID)
6 Packet Formats When a router goes offline and restarts, it loses all multicast
forwarding state. If the upstream router has (S,G) entries in forward
state, data will come down and recreate state in the restarted router.
However, if the upstream router is in negative cache state, no data
packet can flow down until the upstream negative cache state expires.
This results in join latencies for new members joining after the
router went down.
To reduce this join latency, all PIM Hello messages SHOULD carry a
``Generation ID''(GenID) option. The GenID is a randomly generated
32-bit number, that MUST be different between different router
reloads.
When a new GenID is detected from a PIM neighbor, the local router
will need to go through its multicast forwarding table, and attempt to
recover the prune state for the PIM neighbor.
If a new GenID is received on a pruned outgoing interface of a (S,G)
entry, that interface SHOULD be turned into forward state. If the
(S,G) entry transitions into forward state from pruned state, a graft
MUST be sent to the upstream RPF neighbor.
If the new GenID is sent by the RPF neighbor of a negative cache (S,G)
entry, a (S,G) prune SHOULD be immediately sent to that RPF neighbor,
as if the local state just transitioned into prune state.
7 Packet Formats
This section describes the details of the packet formats for PIM This section describes the details of the packet formats for PIM
control messages. control messages.
All PIM control messages have protocol number 103. All PIM control messages have protocol number 103.
Basically, PIM messages are either unicast (e.g. Registers and Basically, PIM messages are either unicast (e.g. Registers and
Register-Stop), or multicast hop-by-hop to `ALL-PIM-ROUTERS' group Register-Stop), or multicast hop-by-hop to `ALL-PIM-ROUTERS' group
`224.0.0.13' (e.g. Join/Prune, Asserts, etc.). `224.0.0.13' (e.g. Join/Prune, Asserts, etc.).
skipping to change at line 527 skipping to change at page 14, line 4
5 = Assert 5 = Assert
6 = Graft (used in PIM-DM only) 6 = Graft (used in PIM-DM only)
7 = Graft-Ack (used in PIM-DM only) 7 = Graft-Ack (used in PIM-DM only)
8 = Candidate-RP-Advertisement 8 = Candidate-RP-Advertisement
Reserved Reserved
Set to zero. Ignored upon receipt. Set to zero. Ignored upon receipt.
Checksum Checksum
The checksum is the 16-bit one's complement of the one's The checksum is the 16-bit one's complement of the one's
Deering,Estrin,Farinacci,Jacobson,Helmy,Meyer,Wei [Page 12]
complement sum of the entire PIM message. For computing the complement sum of the entire PIM message. For computing the
checksum, the checksum field is zeroed. checksum, the checksum field is zeroed.
{ For all the packet format details, refer to the PIM sparse-mode { For all the packet format details, refer to the PIM sparse-mode
specification.} specification.}
6.1 PIM-Hello Message 7.1 PIM-Hello Message
It is sent periodically by PIM routers on all interfaces. It is sent periodically by PIM routers on all interfaces.
6.2 PIM-SM-Register Message The Generation ID option has OptionType of 20, and OptionLength of 4.
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| OptionType = 20 (GenID) | OptionLength = 4 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Random Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
7.2 PIM-SM-Register Message
Used in sparse-mode. Refer to PIM sparse-mode specification. Used in sparse-mode. Refer to PIM sparse-mode specification.
6.3 PIM-SM-Register-Stop Message 7.3 PIM-SM-Register-Stop Message
Used in sparse-mode. Refer to PIM sparse-mode specification. Used in sparse-mode. Refer to PIM sparse-mode specification.
6.4 Join/Prune Message 7.4 Join/Prune Message
It is sent by routers toward upstream sources. A join creates It is sent by routers toward upstream sources. A join creates
forwarding state and a prune destroys forwarding state. Refer to PIM forwarding state and a prune destroys forwarding state. Refer to PIM
sparse-mode specification. sparse-mode specification.
6.5 PIM-SM-Bootstrap Message 7.5 PIM-SM-Bootstrap Message
Used in sparse-mode. Refer to PIM sparse-mode specification. Used in sparse-mode. Refer to PIM sparse-mode specification.
6.6 PIM-Assert Message 7.6 PIM-Assert Message
The PIM-Assert message is sent when a multicast data packet is The PIM-Assert message is sent when a multicast data packet is
received on an outgoing interface corresponding to the (S,G) or (*,G) received on an outgoing interface corresponding to the (S,G) or (*,G)
associated with the source. This message is used in both dense-mode associated with the source. This message is used in both dense-mode
and sparse-mode PIM. For packet format, refer to PIM sparse-mode and sparse-mode PIM. For packet format, refer to PIM sparse-mode
specification. specification.
6.7 PIM-Graft Message 7.7 PIM-Graft Message
This message is sent by a downstream router to a neighboring upstream This message is sent by a downstream router to a neighboring upstream
router to reinstate a previously pruned branch of a source tree. This router to reinstate a previously pruned branch of a source tree. This
is done for dense-mode groups only. The format is the same as a is done for dense-mode groups only. The format is the same as a
Join/Prune message, except that the value in the type field is 6. The Join/Prune message, except that the value in the type field is 6. The
source address hsould be included in teh join section of the message. source address should be included in the join section of the message.
The holdtime field is unused, and is ignored when a graft is received. The holdtime field is unused, and is ignored when a graft is received.
Deering,Estrin,Farinacci,Jacobson,Helmy,Meyer,Wei [Page 13] 7.8 PIM-Graft-Ack Message
6.8 PIM-Graft-Ack Message
Sent in response to a received Graft message. The Graft-Ack is only Sent in response to a received Graft message. The Graft-Ack is only
sent if the interface in which the Graft was received is not the sent if the interface in which the Graft was received is not the
incoming interface for the respective (S,G). This is done for dense- incoming interface for the respective (S,G). This is done for dense-
mode groups only. The format is the same as Join/Prune message, except mode groups only. The format is the same as Join/Prune message, except
that the value of the message type field is 7. The ``Encoded-Unicast- that the value of the message type field is 7. The ``Encoded-Unicast-
Upstream Neighbor Address'' field is unused and needs not be checked Upstream Neighbor Address'' field is unused and needs not be checked
when this message is received. The holdtime field in the packet is when this message is received. The holdtime field in the packet is
ignored when received. ignored when received.
7 Acknowledgement 8 Security Considerations
Security issues are discussed in detail in the companion document
``Authenticating PIM Version 2 Messages'' [PIMAU].
9 Acknowledgement
Thanks to Manoj Leelanivas, Sangeeta Mukherjee, Nitin Jain and many Thanks to Manoj Leelanivas, Sangeeta Mukherjee, Nitin Jain and many
members of the PIM/IDMR working group for their helpful comments. members of the PIM/IDMR working group for their helpful comments.
8 References 10 References
[Deering91] S.E. Deering. Multicast Routing in a Datagram [Deering91] S.E. Deering. Multicast Routing in a Datagram
Internetwork. PhD thesis, Electrical Engineering Dept., Stanford Internetwork. PhD thesis, Electrical Engineering Dept., Stanford
University, December 1991. University, December 1991.
[DVMRP] RFC 1075, Distance Vector Multicast Routing Protocol. [DVMRP] RFC 1075, Distance Vector Multicast Routing Protocol.
Waitzman, D., Partridge, C., Deering, S.E, November 1988 Waitzman, D., Partridge, C., Deering, S.E, November 1988
[PIMSM] Protocol Independent Multicast Sparse-Mode (PIM-SM): Protocol [PIMSM] Protocol Independent Multicast Sparse-Mode (PIM-SM): Protocol
Specification. D. Estrin, D. Farinacci, A. Helmy, D. Thaler, S. Specification. D. Estrin, D. Farinacci, A. Helmy, D. Thaler, S.
Deering, M. Handley, V. Jacobson, C. Liu, P.Sharma, L. Wei draft- Deering, M. Handley, V. Jacobson, C. Liu, P.Sharma, L. Wei draft-
ietf-idmr-pim-sm-specv2-00.txt. ietf-idmr-pim-sm-specv2-00.txt.
[PIMARCH] An Architecture for Wide-Area Multicast Routing, S. Deering, [PIMARCH] An Architecture for Wide-Area Multicast Routing, S. Deering,
D. Estrin, D. Farinacci, V. Jacobson, G. Liu,L. Wei, USC Technical D. Estrin, D. Farinacci, V. Jacobson, G. Liu,L. Wei, USC Technical
Report, available from authors, Nov 1996. Report, available from authors, Nov 1996.
[RFC1112] Host Extensions for IP Multicasting, Network Working Group, [RFC1112] Host Extensions for IP Multicasting, Network Working Group,
RFC 1112, S. Deering, August 1989 RFC 1112, S. Deering, August 1989
9 Security Considerations [PIMAU] Authenticating PIM Version 2 Messages, L. Wei. <draft-ietf-
pim-v2-auth-00.txt>, Nov, 1999
Security issues are not discussed in this memo.
10 Authors' Addresses
Deering,Estrin,Farinacci,Jacobson,Helmy,Meyer,Wei [Page 14] 11 Authors' Addresses
Stephen Deering Stephen Deering
Cisco Systems Inc Cisco Systems Inc
170 West Tasman Drive, 170 West Tasman Drive,
San Jose, CA 95134 San Jose, CA 95134
deering@cisco.com deering@cisco.com
Deborah Estrin Deborah Estrin
Computer Science Department/ISI Computer Science Department/ISI
University of Southern California University of Southern California
Los Angeles, CA 90089 Los Angeles, CA 90089
estrin@usc.edu estrin@usc.edu
Dino Farinacci Dino Farinacci
cisco Systems Inc cisco Systems Inc
170 West Tasman Drive 170 West Tasman Drive
San Jose, CA 95134 San Jose, CA 95134
dino@cisco.com dino@cisco.com
Van Jacobson Van Jacobson
Lawrence Berkeley Laboratory cisco Systems Inc
1 Cyclotron Road 170 West Tasman Drive
Berkeley, CA 94720 San Jose, CA 95134
van@ee.lbl.gov van@cisco.com
Ahmed Helmy Ahmed Helmy
Computer Science Department Computer Science Department
University of Southern California University of Southern California
Los Angeles, CA 90089 Los Angeles, CA 90089
ahelmy@catarina.usc.edu ahelmy@catarina.usc.edu
David Meyer David Meyer
cisco Systems, Inc cisco Systems, Inc
170 West Tasman Drive 170 West Tasman Drive
San Jose, CA95134 San Jose, CA95134
meyer@cisco.com meyer@cisco.com
Liming Wei Liming Wei
cisco Systems Inc cisco Systems Inc
170 West Tasman Drive 170 West Tasman Drive
San Jose, CA 95134 San Jose, CA 95134
lwei@cisco.com lwei@cisco.com
Deering,Estrin,Farinacci,Jacobson,Helmy,Meyer,Wei [Page 15]
Deering,Estrin,Farinacci,Jacobson,Helmy,Meyer,Wei [Page 16]
 End of changes. 

This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/