One document matched: draft-ietf-idmr-dvmrp-v3-06.txt
Differences from draft-ietf-idmr-dvmrp-v3-05.txt
T. Pusateri
INTERNET DRAFT Juniper Networks
Obsoletes: RFC 1075 March 1998
draft-ietf-idmr-dvmrp-v3-06 Expires: September 1998
Distance Vector Multicast Routing Protocol
Status of this Memo
This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas,
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 months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as `'work in progress.''
To learn the current status of any Internet-Draft, please check the
`'1id-abstracts.txt'' listing contained in the Internet-Drafts Shadow
Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
ftp.isi.edu (US West Coast).
Abstract
DVMRP is an Internet routing protocol that provides an efficient
mechanism for connection-less datagram delivery to a group of hosts
across an internetwork. It is a distributed protocol that dynamically
generates IP Multicast delivery trees using a technique called
Reverse Path Multicasting (RPM) [Deer90]. This document is an update
to Version 1 of the protocol specified in RFC 1075 [Wait88].
Pusateri [Page 1]
INTERNET-DRAFT DVMRP Version 3 March 1998
1. Introduction
DVMRP uses a distance vector distributed routing algorithm in order
for each router to determine the distance from itself to any IP
Multicast traffic source. By determining the best path back to a
source, a router can know which interface it should expect traffic
from that source to arrive on. A good introduction to distance
vector routing can be found in [Perl92]. The application of distance
vector routing to multicast tree formulation is described in
[Deer91].
1.1. Reverse Path Multicasting
Datagrams follow multicast delivery trees from a source to all
members of a multicast group [Deer89], replicating the packet only at
necessary branches in the delivery tree. The trees are calculated and
updated dynamically to track the membership of individual groups.
When a datagram arrives on an interface, the reverse path to the
source of the datagram is determined by examining a DVMRP routing
table of known source networks. If the datagram arrives on an
interface that would be used to transmit datagrams back to the
source, then it is forwarded to the appropriate list of downstream
interfaces. Otherwise, it is not on the optimal delivery tree and
should be discarded. In this way duplicate packets can be filtered
when loops exist in the network topology. The source specific
delivery trees are automatically pruned back as group membership
changes or leaf routers determine that no group members are present.
This keeps the delivery trees to the minimum branches necessary to
reach all of the group members. New sections of the tree can also be
added dynamically as new members join the multicast group by grafting
the new sections onto the delivery trees.
1.2. Tunnel Encapsulation
Because not all IP routers support native multicast routing, DVMRP
includes direct support for tunneling IP Multicast datagrams through
routers. The IP Multicast datagrams are encapsulated in unicast IP
packets and addressed to the routers that do support native multicast
routing. DVMRP treats tunnel interfaces in an identical manner to
physical network interfaces.
In previous implementations, DVMRP protocol messages were sent un-
encapsulated to the unicast tunnel endpoint address. While this was
Pusateri [Page 2]
INTERNET-DRAFT DVMRP Version 3 March 1998
more direct, it increased the complexity of firewall configuration.
The most noticable change in this specification regarding tunnels is
that all DVMRP protocol messages should be sent encapsulated across
the tunnel. Previously, protocol messages were sent un-encapsulated
directly to the tunnel endpoint. See Appendix C for backward
compatibility issues.
Note: All protocol messages sent on point-to-point links (including
tunnels) should use a destination address of All-DVMRP-Routers. This
change will allow the protocol messages to be fowarded across
multicast-only tunnels without making encapsulation and decapsulation
difficult.
In practice, tunnels typically use either IP-IP [Perk96] or Generic
Routing Encapsulation (GRE) [Han94a,Han94b], although, other
encapsulation methods are acceptable.
1.3. Document Overview
Section 2 provides an overview of the protocol and the different
message types exchanged by DVMRP routers. Those who wish to gain a
general understanding of the protocol but are not interested in the
more precise details may wish to only read this section. Section 3
explains the detailed operation of the protocol to accommodate
developers needing to provide inter-operable implementations.
Included in Appendix A, is a summary of the DVMRP parameters. A
section on DVMRP support for tracing and troubleshooting is the topic
of Appendix B. Finally, a short DVMRP version compatibility section
is provided in Appendix C to assist with backward compatibility
issues.
2. Protocol Overview
DVMRP can be summarized as a "broadcast & prune" multicast routing
protocol. It performs Reverse Path Forwarding checks to determine
when multicast traffic should be forwarded to downstream interfaces.
In this way, source-rooted shortest path trees can be formed to reach
all group members from each source network of multicast traffic.
2.1. Neighbor Discovery
Pusateri [Page 3]
INTERNET-DRAFT DVMRP Version 3 March 1998
Neighbor DVMRP routers can be discovered dynamically by sending
Neighbor Probe Messages on local multicast capable network interfaces
and tunnel pseudo interfaces. These messages are sent periodically to
the All-DVMRP-Routers [Reyn94] IP Multicast group address. (See
Appendix C for backwards compatibility issues.) The IP TTL of these
messages should be set to 1.
Each Neighbor Probe message should contain the list of Neighbor DVMRP
routers for which Neighbor Probe messages have been received on that
interface. In this way, Neighbor DVMRP routers can ensure that they
are seen by each other. Care must be taken to inter-operate with
older implementations of DVMRP that do not include this list of
neighbors. It can be assumed that older implementations of DVMRP
will safely ignore this list of neighbors in the Probe message.
Therefore, it is not necessary to send both old and new types of
Neighbor Probes.
2.2. Source Location
When an IP Multicast datagram is received by a router running DVMRP,
it first looks up the source network in the DVMRP routing table. The
interface of the next hop of packets sent back to the source of the
datagram is called the upstream interface. If the datagram arrived
on the correct upstream interface, then it is a candidate for
forwarding to one or more downstream interfaces. If the datagram did
not arrive on the anticipated upstream interface, it is discarded.
This check is known as a reverse path forwarding check and must be
performed by all DVMRP routers.
In order to ensure that all DVMRP routers have a consistent view of
the path back to a source, a routing table is propagated to all DVMRP
routers as an integral part of the protocol. Each router advertises
the network number and mask of the interfaces it is directly
connected to as well as relaying the routes received from neighbor
routers. DVMRP requires an interface metric to be configured on all
physical and tunnel interfaces. When a route is received, the metric
of the upstream interface over which the datagram was received must
be added to the metric of the route being propagated. This adjusted
metric should be used when comparing metrics to determine the best
upstream neighbor.
Although there is certainly additional overhead associated with
propagating a separate DVMRP routing table, it does provide two nice
features. First, since all DVMRP routers are exchanging the same
routes, there are no inconsistencies between routers when determining
the upstream interface (aside from normal convergence issues related
Pusateri [Page 4]
INTERNET-DRAFT DVMRP Version 3 March 1998
to distance vector routing protocols). By placing the burden of
synchronization on the protocol as opposed to the network manager,
DVMRP reduces the risk of creating routing loops or black holes due
to disagreement between neighbor routers on the upstream interface.
Second, by propagating its own routing table, DVMRP makes it
convenient to have separate paths for unicast vs. multicast
datagrams. Although, ideally, many network managers would prefer to
keep their unicast and multicast traffic aligned, tunneled multicast
topologies may prevent this causing the unicast and multicast paths
to diverge. Additionally, service providers may prefer to keep the
unicast and multicast traffic separate for routing policy reasons as
they experiment with IP multicast routing and begin to offer it as a
service.
2.3. Dependent Downstream Routers
In addition to providing a consistent view of source networks, the
exchange of routes in DVMRP provides one other important feature.
DVMRP uses the route exchange as a mechanism for upstream routers to
determine if any downstream routers depend on them for forwarding
from particular source networks. DVMRP accomplishes this by using a
technique called "Poison Reverse". If a downstream router selects an
upstream router as the best next hop to a particular source network,
this is indicated by echoing back the route to the upstream router
with a metric equal to the original metric plus infinity. When the
upstream router receives the report and sees a metric that lies
between infinity and twice infinity, it can then add the downstream
router from which it received the report to a list of dependent
routers for this source.
This list of dependent routers per source network built by the
"Poison Reverse" technique will provide the foundation necessary to
determine when it is appropriate to prune back the IP source specific
multicast trees.
2.4. Designated Forwarder
When two or more DVMRP routers are connected to a multi-access
network, it is possible for duplicate packets to be forwarded on the
network (one copy from each router). DVMRP does not require a special
mechanism to prevent duplication. Instead, this feature is a
consequence of the route exchange. When two routers on a multi-access
network exchange source networks, each of the routers will know the
Pusateri [Page 5]
INTERNET-DRAFT DVMRP Version 3 March 1998
others metric back to each source network. Therefore, of all the
DVMRP routers on a shared network, the router with the lowest metric
to a source network is responsible for forwarding data on to the
shared network. If two or more routers have an equally low metric,
the router with the lowest IP address becomes the designated
forwarder for the network. In this way, DVMRP does an implicit
designated forwarder election for each source network on each
downstream interface.
2.5. Building Multicast Trees
As previously mentioned, when an IP multicast datagram arrives, the
upstream interface is determined by looking up the interface that
would be used if a datagram was being sent back to the source of the
datagram. If the upstream interface is correct, then a DVMRP router
will forward the datagram to a list of downstream interfaces.
2.5.1. Adding Leaf Networks
Initially, the DVMRP router must consider all of the remaining IP
multicast capable interfaces (including tunnels) on the router. If
the downstream interface under consideration is a leaf network (has
no dependent downstream neighbors for the source network), then the
IGMP local group database must be consulted. DVMRP routers can easily
determine if a directly attached network is a leaf network by keeping
a list of all routers from which DVMRP Router Probe messages have
been received on the interface. Obviously, it is necessary to refresh
this list and age out entries received from routers that are no
longer being refreshed.
The IGMP local group database is maintained by all IP multicast
routers on each physical, multicast capable network [Fenn97]. If the
destination group address is listed in the local group database, and
the router is the designated forwarder for the source, then the
interface should be included in the list of downstream interfaces.
If there are no group members on the interface, then the interface
can be removed from the outgoing interface list.
2.5.2. Adding Non-Leaf Networks
Initially, all non-leaf networks should be included in the downstream
interface list when a forwarding cache entry is first being created.
Pusateri [Page 6]
INTERNET-DRAFT DVMRP Version 3 March 1998
This allows all downstream routers to be aware of traffic destined
for a particular (source network, group) pair. The downstream routers
will then have the option to send prunes and grafts for this (source
network, group) pair as requirements change from their respective
downstream routers and local group members.
2.6. Pruning Multicast Trees
As mentioned above, routers at the edges with leaf networks will
remove their leaf interfaces that have no group members associated
with an IP multicast datagram. If a router removes all of its
downstream interfaces, it can notify the upstream router that it no
longer wants traffic destined for a particular (source network,
group) pair. This is accomplished by sending a DVMRP Prune message
upstream to the router it expects to forward datagrams from a
particular source.
Recall that a downstream router will inform an upstream router that
it depends on the upstream router to receive datagrams from
particular source networks by using the "Poison Reverse" technique
during the exchange of DVMRP routes. This method allows the upstream
router to build a list of downstream routers on each interface that
are dependent upon it for datagrams from a particular source network.
If the upstream router receives prune messages from each one of the
dependent downstream routers on an interface, then the upstream
router can in turn remove this interface from its downstream
interface list. If the upstream router is able to remove all of its
downstream interfaces in this way, it can then send a DVMRP Prune
message to its upstream router. This continues until the unneeded
branches are removed from the delivery tree.
In order to remove old prune state information for (source network,
group) pairs that are no longer active, it is necessary to limit the
life of a prune and periodically resume the flooding procedure.
Inside the prune message is a prune lifetime. This indicates the
length of time that the prune should remain in effect. When the prune
lifetime expires, the interface is joined back onto the multicast
delivery tree. If unwanted multicast datagrams continue to arrive,
the prune mechanism will be re-initiated and the cycle will continue.
If all of the downstream interfaces are removed from a multicast
delivery tree causing a DVMRP Prune message to be sent upstream, the
lifetime of the prune sent will be equal to the minimum of the
remaining prune lifetimes of the downstream interfaces.
Pusateri [Page 7]
INTERNET-DRAFT DVMRP Version 3 March 1998
2.7. Grafting Multicast Trees
Once a tree branch has been pruned from a multicast delivery tree,
packets from the corresponding (source network, group) pair will no
longer be forwarded. However, since IP multicast supports dynamic
group membership, new hosts may join the multicast group. In this
case, DVMRP routers use Grafts to undo the prunes that are in place
from the host back on to the multicast delivery tree. A router will
send a Graft message to its upstream neighbor if a group join occurs
for a group that the router has previously sent a prune. Separate
Graft messages must be sent to the appropriate upstream neighbor for
each source network that has been pruned. Since there would be no
way to tell if a Graft message sent upstream was lost or the source
simply quit sending traffic, it is necessary to acknowledge each
Graft message with a DVMRP Graft Ack message. If an acknowledgment
is not received within a Graft Time-out period, the Graft message
should be retransmitted. Duplicate Graft Ack messages should simply
be ignored. The purpose of the Graft Ack message is to simply
acknowledge the receipt of a Graft message. It does not imply that
any action was taken as a result of receiving the Graft message.
Therefore, all Graft messages should be acknowledged whether or not
they cause an action on the receiving router.
3. Detailed Protocol Operation
This section contains a detailed description of DVMRP. It covers
sending and receiving of DVMRP messages as well as the generation and
maintenance of IP Multicast forwarding cache entries.
3.1. Protocol Header
DVMRP packets are encapsulated in IP datagrams, with an IP protocol
number of 2 (IGMP) as specified in the Assigned Numbers RFC [Reyn94].
All fields are transmitted in Network Byte Order. DVMRP packets use a
common protocol header that specifies the IGMP [Fenn97] Packet Type
as hexadecimal 0x13 (DVMRP). DVMRP protocol packets should be sent
with the Precedence field in the IP header set to Internetwork
Control (hexadecimal 0xc0 for the Type of Service Octet) [Post81]. A
diagram of the common protocol header follows:
Pusateri [Page 8]
INTERNET-DRAFT DVMRP Version 3 March 1998
0 8 16 31
+---------+---------+--------------------+
| Type | Code | Checksum |
|(0x13) | | |
+---------+---------+----------+---------+
| Reserved | Minor | Major |
| | Version |Version |
+-------------------+----------+---------+
Figure 1 - Common Protocol Header
A Major Version of 3 and a Minor Version of 0xFF should be used to
indicate compliance with this specification. The value of the Code
field determines the DVMRP packet type. Currently, there are codes
allocated for DVMRP protocol message types as well as protocol
analysis and troubleshooting packets. The protocol message Codes
are:
Code Packet Type Description
----------------------------------------------------------------
1 DVMRP Probe for neighbor discovery
2 DVMRP Report for route exchange
7 DVMRP Prune for pruning multicast delivery trees
8 DVMRP Graft for grafting multicast delivery trees
9 DVMRP Graft Ack for acknowledging graft messages
----------------------------------------------------------------
Table 1 - Standard Protocol Packet Types
There are additional codes used for protocol analysis and
troubleshooting. These codes are discussed in Appendix B. The
Checksum is the 16-bit one's complement of the one's complement sum
of the DVMRP message. The checksum of the DVMRP message should be
calculated with the checksum field set to zero.
3.2. Probe Messages
When a DVMRP router is configured to run on an interface (physical or
tunnel), it sends local IP Multicast discovery packets to inform
other DVMRP routers that it is operational. These discovery packets
Pusateri [Page 9]
INTERNET-DRAFT DVMRP Version 3 March 1998
are called DVMRP Probes and they serve three purposes.
1. Probes provide a mechanism for DVMRP routers to locate each other.
DVMRP sends on each interface, a Probe Message containing the list
of the neighbors detected for that specific interface. This list
of DVMRP neighbors provides a foundation for the dependent
downstream neighbor list. If no DVMRP neighbors are found, the
network is considered to be a leaf network.
2. Probes provide a way for DVMRP routers to determine the
capabilities of each other. This may be deduced from the major and
minor version numbers in the Probe packet or directly from the
capability flags. These flags were first introduced to allow
optional protocol features. This specification now mandates the
use of Generation Id's and pruning and, therefore, provides no
optional capabilities. Other capability flags were used for
tracing and troubleshooting and are no longer a part of the actual
protocol.
3. Probes provide a keep-alive function in order to quickly detect
neighbor loss. DVMRP probes sent on each multicast capable
interface configured for DVMRP SHOULD have an interval of 10
seconds. The neighbor time-out interval SHOULD be set at 35
seconds. This allows fairly early detection of a lost neighbor yet
provides tolerance for busy multicast routers. These values MUST
be coordinated between all DVMRP routers on a physical network
segment.
3.2.1. Router Capabilities
In the past, there have been many versions of DVMRP in use with a
wide range of capabilities. Practical considerations require a
current implementation to inter-operate with these older
implementations that don't formally specify their capabilities and
are not compliant with this specification. For instance, for major
versions less than 3, it can be assumed that the neighbor does not
support pruning. The formal capability flags were first introduced
in an well known implementation (Mrouted version 3.5) in an attempt
to take the guess work out which features are supported by a
neighbor. Many of these flags are no longer necessary since they are
now a required part of the protocol, however, special consideration
is necessary to not confuse older implementations that expect these
flags to be set. Appendix C was written to assist with these and
Pusateri [Page 10]
INTERNET-DRAFT DVMRP Version 3 March 1998
other backward compatibility issues.
Three of the flags were used for actual protocol operation. The
other two assigned flags were used for troubleshooting purposes which
should be documented in a separate specification. All of the bits
marked "U" in the Figure below are now unused. They may be defined in
the future and MUST be set to 0. Bit position 0 is the LEAF bit which
is a current research topic. It MUST be set to 0. Bit positions 1,
2, and 3 MUST be set to 1 for backward compatibility. They were used
to specify the PRUNE, GENID, and MTRACE bits. The first two, PRUNE
and GENID, are now required features. The MTRACE bit must be set so
existing implementations will not assume this neighbor does not
support multicast trace-route [Fenn96]. However, since this bit is
now reserved and set to 1, newer implementations should not use this
bit in the Probe message to determine if multicast trace-route is
supported by a neighbor. Instead, the M bit should only be used in a
Neighbors2 message as described in Appendix B. The bit marked S
stands for SNMP capable. This bit is used by troubleshooting
applications and should only be tested in the Neighbors2 message.
7 6 5 4 3 2 1 0
U U U S M G P L
+---+---+---+---+----+---+---+---+
|0 |0 |0 | 0 | 1 |1 |1 | 0 |
+---+---+---+---+----+---+---+---+
Figure 2 - Probe Capability Flags
3.2.2. Generation ID
If a DVMRP router is restarted, it will want to learn all of the
routes known by its neighbors without having to wait for an entire
report interval to pass. In order for the neighbor to detect that the
router has restarted, a non-decreasing number is placed in the
periodic probe message called the generation ID. When a router
detects an increase in the generation ID of a neighbor, it should
send a unicast copy of its entire routing table to the neighbor.
If a change in generation ID is detected, any prune information
received from the router is no longer valid and should be flushed.
If this prune state has caused prune information to be sent upstream,
a graft will need to be sent upstream just as though a new member has
joined below. Once data begins to be delivered downstream, if the
Pusateri [Page 11]
INTERNET-DRAFT DVMRP Version 3 March 1998
downstream router again decides to be pruned from the delivery tree,
a new prune can be sent upstream at that time.
A time of day clock provides a good source for a non-decreasing 32
bit integer.
3.2.3. Neighbor Addresses
As a DVMRP router sees Probe messages from its DVMRP neighbors, it
records the neighbor addresses on each interface and places them in
the Probe message sent on the particular interface. This allows the
neighbor router to know that its probes have been received by the
sending router.
In order to minimize one-way neighbor relationships, a router MUST
delay sending poison route reports to a neighbor until the neighbor
includes the routers address in its probe messages. On point-to-point
interfaces and tunnel pseudo-interfaces, this means that no packets
should be forwarded onto these interfaces until two-way neighbor
relationships have formed.
Implementations written before this specification will not wait
before sending reports nor will they ignore reports sent. Therefore,
reports from these implementations SHOULD be accepted whether or not
a probe with the routers address has been received.
3.2.4. Neighbor Time-Out
When a neighbor times out, the following steps should be taken:
1. All routes learned from this neighbor should be immediately placed
in hold-down. All downstream dependencies ON this neighbor should
be removed.
2. If this neighbor is considered to be the designated forwarder for
any of the routes it is advertising, a new designated forwarder
for each source network should be selected.
3. Any forwarding cache entries based on this upstream neighbor
should be flushed.
Pusateri [Page 12]
INTERNET-DRAFT DVMRP Version 3 March 1998
4. Any outstanding Grafts awaiting acknowledgement should be flushed.
5. All downstream dependencies received FROM this neighbor should be
removed. Forwarding cache entries should be checked to see if
this is the last downstream dependent neighbor on the interface.
If so, and this router isn't the designated forwarder (with local
group members present), the interface should be removed. If the
last downstream interface is removed, a prune should be sent
upstream.
3.2.5. Probe Packet Format
The Probe packet is variable in length depending on the number of
neighbor IP addresses included. The length of the IP packet can be
used to determine the number of neighbors in the Probe message. The
current Major Version is 3. To maintain compatibility with previous
versions, implementations of Version 3 must include pruning and
grafting of multicast trees. Non-pruning implementations SHOULD NOT
be implemented at this time.
Pusateri [Page 13]
INTERNET-DRAFT DVMRP Version 3 March 1998
7 15 23 31
+---------+--------------+--------------------+
| Type | Code | Checksum |
| (0x13) | (0x1) | |
+---------+--------------+----------+---------+
| | | | |
|Reserved | Capabilities | Minor | Major |
+---------+--------------+----------+---------+
| |
| Generation ID |
+---------------------------------------------+
| |
| Neighbor IP Address 1 |
+---------------------------------------------+
| |
| Neighbor IP Address 2 |
+---------------------------------------------+
| |
| ... |
+---------------------------------------------+
| |
| Neighbor IP Address N |
+---------------------------------------------+
Figure 3 - DVMRP Probe Packet Format
3.2.6. IGMP Designated Querier Election
Since it is wasteful to have more than a single router sending IGMP
Host Membership Queries on a given physical network, a single router
on each physical network is elected as the Designated Querier. This
election was formerly a part of DVMRP. However, this is now
specified as a part of the IGMP version 2 protocol. See Appendix C
for details on backwards compatibility. DVMRP Version 3 REQUIRES the
use of IGMP Version 2 or later specifying that the Designated Querier
election is performed as a part of IGMP.
Even though only one router will act as the designated querier, all
DVMRP routers must listen to IGMP Host Membership Reports and keep a
local group database.
Pusateri [Page 14]
INTERNET-DRAFT DVMRP Version 3 March 1998
3.3. Building Forwarding Cache Entries
In order to create multicast delivery trees, DVMRP was designed to
keep separate forwarding cache entries for each (source network,
destination group) pair. Because the possible combinations of these
is quite large, forwarding cache entries are generated on demand as
data arrives at a multicast router. Since the IP forwarding decision
is made on a hop by hop basis (as with the unicast case), it is
imperative that each multicast router has a consistent view of the
reverse path back to the source network.
3.3.1. Designated Forwarder
Initially, a DVMRP router should assume it is the designated
forwarder for all source networks on all downstream interfaces. As it
receives route reports, it can determine if other routers on multi-
access networks have better routes back to a particular source
network. A route is considered better if the received metric is less
than the metric that it will advertise for the source network on the
received interface or if the metrics are the same but the IP address
of the neighbor is lower.
If this neighbor becomes unreachable or starts advertising a worse
metric, then the router should become the designated forwarder for
this source network again on the downstream interface until it hears
from a better candidate.
If the upstream RPF interface changes, then the router should become
the designated forwarder on the previous upstream interface (which is
now a potential downstream interface) until it hears from a better
candidate.
3.3.2. Determining the upstream interface
When a multicast packet arrives, a DVMRP router will use the DVMRP
routing table to determine which interface leads back to the source.
If the packet did not arrive on that interface, it should be
discarded without further processing. Each multicast forwarding entry
should cache the upstream interface for a particular source host or
source network after looking this up in the DVMRP routing table.
Pusateri [Page 15]
INTERNET-DRAFT DVMRP Version 3 March 1998
3.3.3. Determining the downstream interface list
The downstream interface list is built from the remaining list of
multicast capable interfaces. Any interfaces designated as leaf
networks that do not have members of the particular multicast group
can be automatically removed from list of downstream interfaces. The
remaining interfaces will either have downstream DVMRP routers or
directly attached group members. If the router is not the designated
forwarder on interfaces with directly attached group members, these
interfaces can be removed as well. This prevents duplicate packets
from arriving on multi-access networks.
3.4. Route Exchange
It was mentioned earlier that since not all IP routers support IP
multicast forwarding, it is necessary to tunnel IP multicast
datagrams through these routers. One effect of using these
encapsulated tunnels is that IP multicast traffic may not be aligned
with IP unicast traffic. This means that a multicast datagram from a
particular source can arrive on a different (logical) interface than
the expected upstream interface based on traditional unicast routing.
The routing information propagated by DVMRP is used for determining
the reverse path neighbor back to the source of the multicast
traffic. The interface used to reach this neighbor is called the
upstream interface. Tunnel pseudo-interfaces are considered to be
distinct from the physical interface on which the packet is actually
transmitted for the purpose of determining upstream and downstream
interfaces.
The routing information that is propagated by DVMRP contains a list
of source networks and an appropriate metric. The metric used is a
hop count which is incremented by the cost of the incoming interface
metric. Traditionally, physical interfaces use a metric of 1 while
the metric of a tunnel interface varies with the distance and
bandwidth in the path between the two tunnel endpoints. Users are
encouraged to configure tunnels with the same metric in each
direction to create symmetric routing and provide for easier problem
determination although the protocol does not strictly enforce this.
3.4.1. Source Network Aggregation
Pusateri [Page 16]
INTERNET-DRAFT DVMRP Version 3 March 1998
Implementations may wish to provide a mechanism to aggregate source
networks to reduce the size of the routing table. All implementations
should be able to accept reports for aggregated source networks in
accordance with Classless Inter-Domain Routing (CIDR) as described in
[Rekh93] and [Full93].
There are two places where aggregation is particularly useful.
1. At organizational boundaries to limit the number of source
networks advertised out of the organization.
2. Within an organization to summarize non-local routing information
by using a default (0/0) route.
If an implementation wishes to support source aggregation, it MUST
transmit Prune and Graft messages according to the following rules:
A. If a Prune is received on a downstream interface for which the
source network advertised to that neighbor is an aggregate
generated by the receiving router, then the aggregating router
should pretend as though prunes were received for each
contributing routes of the aggregated route. If this is the last
downstream dependent neighbor, this may trigger a prune to be sent
upstream to the longest match contributing route of the aggregate
route determined by the source address in the received prune.
There may be active forwarding cache entries for other
contributing routes to the aggregate. Prunes should not be sent
upstream to the contributing routes that have no forwarding state.
The downstream interface on which the aggregated prune was
received should be removed from these forwarding cache entries.
This may trigger a prune being sent upstream for these
contributing routes. However, since these sources may no longer
be active, it might be preferable to wait until data arrives from
these other contributing sources before sending prunes to each
one. This reduces the control traffic and minimizes the number of
prunes sent to only active sources.
In order to be notified when data arrives, the forwarding cache
entries based on these contributing routes should be removed from
the forwarding path in order to trigger the on-demand route lookup
and prune response.
If data from another contributing route of the aggregated network
is received by the aggregating router at a later time, the
aggregating router should remember that a prune was received for
Pusateri [Page 17]
INTERNET-DRAFT DVMRP Version 3 March 1998
this contributing route by the downstream neighbor who previously
sent the aggregated prune. This may trigger sending a prune
upstream for the contributed route.
B. If a Graft is received on a downstream interface for which the
source network advertised to that neighbor is an aggregate
generated by the receiving router, then Graft messages MUST be
sent upstream (if necessary) to the neighbors advertising each of
contributing source networks that were used to generate the
aggregate.
3.4.2. Route Packing and Ordering
Since DVMRP Route Reports may need to refresh several thousand routes
each report interval, routers MUST attempt to spread the routes
reported across the whole route update interval. This reduces the
chance of synchronized route reports causing routers to become
overwhelmed for a few seconds each report interval. Since the route
report interval is 60 seconds, it is suggested that the total number
routes being updated be split across multiple Route Reports sent at
regular intervals. There was an earlier requirement that Route
Reports MUST contain source network/mask pairs sorted first by
increasing network mask and then by increasing source network. This
restriction has been lifted. Implementations conforming to this
specification MUST be able to receive Route Reports containing any
mixture of network masks and source networks.
In order to pack more source networks into a route report, source
networks are often represented by less than 4 octets. The number of
non-zero bytes in the mask value is used to determine the number of
octets used to represent each source network within that particular
mask value. For instance if the mask value of 255.255.0.0 is being
reported, the source networks would only contain 2 octets each. DVMRP
assumes that source networks will never be aggregated into networks
whose prefix length is less than 8. Therefore, it does not carry the
first octet of the mask in the Route Report since, given this
assumption, the first octet will always be 0xFF. This means that the
netmask value will always be represented in 3 octets. This method of
specifying source network masks is compatible with techniques
described in [Rekh93] and [Full93] to group traditional Class C
networks into super-nets and to allow different subnets of the same
Class A network to be discontinuous. In this notation, the default
route is represented as the least three significant octets of the
netmask [00 00 00], followed by one octet for the network number
[00].
Pusateri [Page 18]
INTERNET-DRAFT DVMRP Version 3 March 1998
3.4.3. Route Metrics
For each source network reported, a route metric is associated with
the route being reported. The metric is the sum of the interface
metrics between the router originating the report and the source
network. For the purposes of DVMRP, the Infinity metric is defined to
be 32. This limits the breadth across the whole DVMRP network and is
necessary to place an upper bound on the convergence time of the
protocol.
As seen in the packet format below, Route Reports do not contain a
count of the number of routes reported for each netmask. Instead, the
high order bit of the metric is used to signify the last route being
reported for a particular mask value. If a metric is read with the
high order bit of the 8-bit value set and if the end of the message
has not been reached, the next value will be a new netmask to be
applied to the subsequent list of routes.
3.4.4. Route Dependencies
In order for pruning to work correctly, each DVMRP router needs to
know which downstream routers depend on it for receiving datagrams
from particular source networks. Initially, when a new datagram
arrives from a particular source/group pair, it is flooded to all
downstream interfaces that have DVMRP neighbors who have indicated a
dependency on the receiving DVMRP router for that particular source.
A downstream interface can only be removed when it has received Prune
messages from each of the dependent routers on that interface. Each
downstream router uses Poison Reverse to indicate to the upstream
router which source networks it expects to receive from the upstream
router. The downstream router indicates this by echoing back the
source networks it expects to receive from the upstream router with
infinity added to the advertised metric. This means that the legal
values for the metric now become between 1 and (2 x Infinity - 1) or
1 and 63. Values between 1 and 31 indicate reachable source networks.
The value Infinity (32) indicates the source network is not
reachable. Values between 33 and 63 indicate that the downstream
router originating the Report is depending upon the upstream router
to provide multicast datagrams from the corresponding source network.
3.4.5. Sending Route Reports
Pusateri [Page 19]
INTERNET-DRAFT DVMRP Version 3 March 1998
All of the active routes MUST be advertised over all interfaces with
neighbors present each Route Report Interval. In addition, flash
updates MAY be sent as needed but any given route MUST not be
advertised more often than the Minimum Flash Update Interval (5
seconds). Flash updates can reduce the chances of routing loops and
black holes occurring when source networks become unreachable through
a particular path. Flash updates need only contain the source
networks that have changed. It is not necessary to report all of the
source networks from a particular mask value when sending an update.
When a router sees its own address in a neighbor probe packet for the
first time, it should send a unicast copy of its entire routing table
to the neighbor to reduce start-up time.
Route Reports containing downstream dependent "poison" metrics MUST
be sent to the All-DVMRP-Routers address. These reports should not
be sent to a neighbor until a router has seen its own address in the
neighbors Probe router list. See Appendix C for exceptions. These
Reports should be refreshed at the standard Route Update Interval.
3.4.6. Receiving Route Reports
After receiving a route report, a check should be made to verify it
is from a known neighbor. Neighbors are learned via received Probe
messages which also indicate the capabilities of the neighbor.
Therefore, route reports from unknown neighbors are discarded.
In the following discussion, "Metric" refers to the metric of the
route as received in the route report. "Adjusted Metric" refers to
the metric of the route after the incoming interface metric has been
added.
If the metric received is less than infinity but the Adjusted Metric
is greater than or equal to infinity, the Adjusted Metric should be
set to infinity.
If the metric is greater than or equal to infinity, then no
adjustment of the metric should be made.
Each route in the report is then parsed and processed according to
the following rules:
Pusateri [Page 20]
INTERNET-DRAFT DVMRP Version 3 March 1998
A. If the route is new and the Adjusted Metric is less than infinity,
the route should be added.
If the new route overlaps an existing route for which prunes have
been received from downstream neighbors, the prune state of the
less specific route that falls within the range of the more
specific route should be deleted.
B. If the route already exists, several checks must be performed.
1. Adjusted Metric < infinity
If this neighbor is a downstream dependent neighbor, the
neighbor is now learning the route from another source. Cancel
the downstream dependency.
In the following cases, the designated forwarder for the source
network on either the receiving interface or one of the
downstream interfaces should be updated:
- If the receiving router is the designated forwarder on the
interface and the Metric received is better than the metric
that it is advertising on that interface (or the metric is
the same but the received IP address is lower). Then the
advertising router becomes the new designated forwarder for
the source on the receiving interface. This may trigger a
Prune to be sent upstream.
- If the Metric received would cause the router to advertise a
better metric on a downstream interface than the existing
designated forwarder on that interface (or advertised metric
would be the same but the router's IP address is lower than
the existing designated forwarder on that interface). Then
the receiving router becomes the new designated forwarder on
that interface. This may trigger a graft to be sent
upstream.
- If the metric being advertised by the current designated
forwarder is worse than the receiving routers Adjusted
Metric that it would advertise on the receiving interface
(from learning the same route from a neighbor on another
interface). Then the receiving router becomes the new
designated forwarder on that interface. This may trigger a
graft to be sent upstream.
A route is considered better when either the received Metric is
lower than the existing metric or the received Metric is the
same but the advertising router's IP address is lower.
Pusateri [Page 21]
INTERNET-DRAFT DVMRP Version 3 March 1998
a. Adjusted Metric > existing metric
If the Adjusted Metric is greater than the existing metric,
then check to see if the same neighbor is reporting the
route. If so, update the route metric and flash update the
route. Otherwise, discard the route.
b. Adjusted Metric < existing metric
Update the metric for the route and if the neighbor
reporting the route is different, update the upstream
neighbor in the routing table. Flash update the route to
downstream neighbors and if the upstream interface changed,
a flash poison update should be sent upstream indicating a
change in downstream dependency.
c. Adjusted metric = existing metric
If the neighbor reporting the route is the same as the
existing upstream neighbor, then simply refresh the route.
If the neighbor reporting the route has a lower IP address
than the existing upstream neighbor, then update the route.
If the upstream interface changes, a flash poison update
should be sent on the new interface.
Again, the receiving router may need to update its
designated forwarder status if the neighbor is a better
candidate.
2. Adjusted Metric = infinity
If the neighbor was considered to be the designated
forwarder, the receiving router should now become the
designated forwarder for the source network on this
interface unless it knows of a better candidate. (Another
neighbor on the interface advertising a metric better than
the metric this router would advertise or with the same
metric but a lower IP address.)
a. Next hop = existing next hop
If the existing metric was less than infinity, the route is
now unreachable. Update the route and possibly flash update
the route as well.
b. Next hop != existing next hop
The route can be ignored since the existing next hop has a
Pusateri [Page 22]
INTERNET-DRAFT DVMRP Version 3 March 1998
metric better than or equal to this next hop.
If the neighbor was considered a downstream dependent
neighbor, this should be cancelled. Check to determine if
removing this neighbor triggers a Prune.
3. infinity < Metric < 2 x infinity
The neighbor considers the receiving router to be upstream for
the route and is indicating it is dependent on the receiving
router.
If the neighbor was considered to be the designated forwarder,
the receiving router should now become the designated forwarder
for the source network on this interface unless it knows of a
better candidate. (Another neighbor on the interface
advertising a metric better than the metric this router would
advertise or with the same metric but a lower IP address.)
a. Neighbor on down stream interface
If the sending neighbor is considered to be on a downstream
interface for that route then the neighbor should be
registered as a downstream dependent router for that route.
If this is the first time the neighbor has indicated
downstream dependence for this source and one or more prunes
have been sent upstream containing this source network, then
Graft messages will need to be sent upstream in the
direction of the source network for each group with existing
prune state.
b. Neighbor not on down stream interface
If the receiving router thinks the neighbor is on the
upstream interface, then the indication of downstream
dependence should be ignored.
4. 2 x infinity <= Metric
If the Metric is greater than or equal to 2 x infinity, the
Metric is illegal and the route should be ignored.
Pusateri [Page 23]
INTERNET-DRAFT DVMRP Version 3 March 1998
3.4.7. Route Expiration and Hold-down
When a route learned via a particular gateway expires or the gateway
begins advertising an infinity metric for the route, a router may be
able to reach the source network described by the route through an
alternate gateway. However, in the presence of complex topologies,
often, the alternate gateway may only be echoing back the same route
learned via a different path. If this occurs, the route will continue
to be propagated long after it is no longer valid.
In order to prevent this, it is common in distance vector protocols
to continue to advertise a route that has been deleted with a metric
of infinity for one or more report intervals. During this time, the
route may be learned via a different gateway and the router is
permitted to use this new gateway. However, the router MUST NOT
advertise this new gateway during the hold-down period.
A route expires if it has not been refreshed within the Route
Expiration time. This should be set to 2 x Route Report Interval + 20
(or 140) seconds. When the route expires, it should go into a hold-
down period for 2 Report Intervals. During this hold-down period, the
route should be advertised with an infinity metric. When the hold-
down period is over, a new gateway (if one exists) can start being
advertised. In the absence of a new gateway, the route is simply
removed.
When a route goes into hold-down, all forwarding cache entries based
on the route should be flushed.
Route hold-down is not effective if only some of the routers
implement it. Therefore, it is now a REQUIRED part of the protocol.
In order to minimize outages caused by flapping routes, it is
permissible to prematurely take a route out of hold-down only if the
route is re-learned from the SAME router with the SAME metric.
3.4.8. Graceful Shutdown
During a graceful shutdown, an implementation MAY want to inform
neighbor routers that it is terminating. Routes that have been
advertised with a metric less than infinity should now be advertised
with a metric equal to infinity. This will allow neighbor routers to
switch more quickly to an alternate path for a source network if one
exists.
Pusateri [Page 24]
INTERNET-DRAFT DVMRP Version 3 March 1998
Routes that have been advertised with a metric between infinity and 2
x infinity (indicating downstream neighbor dependence) should now be
advertised with a metric equal to infinity (canceling the downstream
dependence).
3.4.9. Route Report Packet Format
The format of a sample Route Report Packet is shown in Figure 4
below. The packet shown is an example of how the source networks are
packed into a Report. The number of octets in each Source Network
will vary depending on the mask value. The values below are only an
example for clarity and are not intended to represent the format of
every Route Report.
7 15 23 31
+-----------+------------+-------------------------+
| Type | Code | Checksum |
| (0x13) | (0x2) | |
+-----------+------------+------------+------------+
| Reserved | Minor | Major |
| | Version | Version |
+-----------+------------+------------+------------+
| Mask1 | Mask1 | Mask1 | Src |
| Octet2 | Octet3 | Octet4 | Net11 |
+-----------+------------+------------+------------+
| SrcNet11(cont.)... | Metric11 | Src |
| | | Net12 |
+------------------------+------------+------------+
| SrcNet12(cont.)... | Metric12 | Mask2 |
| | | Octet2 |
+-----------+------------+------------+------------+
| Mask2 | Mask2 | SrcNet21 |
| Octet3 | Octet4 | |
+-----------+------------+------------+------------+
| SrcNet21(cont.)... | Metric21 | Mask3 |
| | | Octet2 |
+-----------+------------+------------+------------+
| Mask3 | Mask3 | ... |
| Octet3 | Octet4 | |
+-----------+------------+-------------------------+
Figure 4 - Example Route Report Packet Format
Pusateri [Page 25]
INTERNET-DRAFT DVMRP Version 3 March 1998
3.5. Pruning
DVMRP is described as a broadcast and prune multicast routing
protocol since datagrams are initially sent out all dependent
downstream interfaces forming a tree rooted at the source of the
data. But as the routers at the leafs of the tree begin to receive
unwanted multicast traffic, they send prune messages upstream toward
the source. This allows the tree branches to become optimal for a
given source network and a given set of receivers.
3.5.1. Leaf Networks
Detection of leaf networks is very important to the pruning process.
Routers at the end of a source specific multicast delivery tree must
detect that there are no further downstream routers. This detection
mechanism is covered above in section 3.2 titled Probe Messages. If
there are no group members present for a particular multicast
datagram received, the leaf routers will start the pruning process by
removing their downstream interfaces and sending a prune to the
upstream router for that source.
3.5.2. Source Networks
It is important to note that prunes are specific to a group and
source network. A prune sent upstream triggered by traffic received
from a particular source applies to all sources on that network. It
is not currently possible to remove only one or a subset of hosts on
a source network for a particular group. All or none of the sources
must be removed.
Although the Prune message contains the host address of a source, the
source network can be determined easily by a best-match lookup using
the routing table distributed as a part of DVMRP.
3.5.3. Receiving a Prune
When a prune is received, the following steps should be taken:
1. If the neighbor is unknown, discard the received prune.
Pusateri [Page 26]
INTERNET-DRAFT DVMRP Version 3 March 1998
2. Since Prune messages are currently fixed length, ensure the prune
message contains at least the correct amount of data.
3. Extract the source address, group address, and prune time-out
values
4. If there is no current state information for the (source network,
group) pair, then ignore the prune.
5. Verify that the prune was received from a dependent neighbor for
the source network. If not, discard the prune.
6. Determine if a prune is currently active from the same dependent
neighbor for this (source network, group) pair.
7. If so, reset the timer to the new time-out value. Otherwise,
create state for the new prune and set a timer for the prune
lifetime.
8. Determine if all dependent downstream routers on the interface
from which the prune was received have now sent prunes.
9. If so, then determine if there are group members active on the
interface.
10. If no group members are found, then remove the interface.
11. If all downstream interfaces have now been removed, send a prune
to the upstream neighbor.
3.5.4. Sending a Prune
When sending a prune upstream, the following steps should be taken:
1. Decide if upstream neighbor is capable of receiving prunes.
Pusateri [Page 27]
INTERNET-DRAFT DVMRP Version 3 March 1998
2. If not, then proceed no further.
3. Stop any pending Grafts awaiting acknowledgments.
4. Determine the prune lifetime. This value should be the minimum of
the prune lifetimes remaining from the downstream neighbors and
the default prune lifetime.
5. Form and transmit the packet to the upstream neighbor for the
source.
3.5.5. Retransmitting a Prune
By increasing the prune lifetime to ~2 hours, the effect of a lost
prune message becomes more apparent. Therefore, an implementation
SHOULD choose to retransmit prunes messages using exponential back-
off for the lifetime of the prune if traffic is still arriving on the
upstream interface.
One way to implement this would be to send a prune, install a
negative cache entry for 3 seconds while waiting for the prune to
take effect. Then remove the negative cache entry. If traffic
continues to arrive, a new forwarding cache request will be
generated. The prune can be resent with the remaining prune lifetime
and a negative cache entry can be installed for 6 seconds. After
this, the negative cache entry is removed. This procedure is repeated
while each time doubling the length of time the negative cache entry
is installed.
The actual retransmission time should be randomized to reduce
synchronized prune retransmissions.
On multi-access networks, even if a prune is received correctly, data
may still be received due to other receivers on the network.
Pusateri [Page 28]
INTERNET-DRAFT DVMRP Version 3 March 1998
3.5.6. Prune Packet Format
In addition to the standard IGMP and DVMRP headers, a Prune Packet
contains three additional fields: the source host IP address, the
destination group IP address, and the Prune Lifetime in seconds.
The Prune Lifetime is a derived value calculated as the minimum of
the default prune lifetime (2 hours) and the remaining lifetimes of
of any downstream prunes received for the same cache entry. A router
with no downstream dependent neighbors would use the the default
prune lifetime.
7 15 23 31
+-----------+------------+-------------------------+
| Type | Code | Checksum |
| (0x13) | (0x7) | |
+-----------+------------+------------+------------+
| Reserved | Minor | Major |
+------------------------+------------+------------+
| Source Address |
+--------------------------------------------------+
| Group Address |
+--------------------------------------------------+
| Prune Lifetime |
+--------------------------------------------------+
Figure 5 - Prune Packet Format
3.6. Grafting
Once a multicast delivery tree has been pruned back, DVMRP Graft
messages are necessary to join new receivers onto the multicast tree.
Graft messages are sent upstream from the new receiver's first-hop
router until a point on the multicast tree is reached. Graft
messages are re-originated between adjacent DVMRP routers and are not
forwarded by DVMRP routers. Therefore, the first-hop router does not
know if the Graft message ever reaches the multicast tree. To remedy
this, each Graft message is acknowledged hop by hop. This ensures
that the Graft message is not lost somewhere along the path between
the receiver's first-hop router and the closest point on the
multicast delivery tree.
One or more Graft messages should be sent under the following
conditions:
Pusateri [Page 29]
INTERNET-DRAFT DVMRP Version 3 March 1998
1. A new local member joins a group that has been pruned upstream.
2. A new dependent downstream router appears on a pruned branch.
3. A dependent downstream router on a pruned branch restarts (new
Generation ID).
4. A Graft Retransmission Timer expires before a Graft-Ack is
received.
3.6.1. Grafting Each Source Network
It is important to realize that prunes are source network specific
and are sent up different trees for each source network. Grafts are
sent in response to a new Group Member which is not source specific.
Therefore, separate Graft messages must be sent to the appropriate
upstream routers to counteract each previous source specific prune
that was sent.
3.6.2. Sending a Graft
As mentioned above, a Graft message sent to the upstream DVMRP router
should be acknowledged hop by hop guaranteeing end-to-end delivery.
If a Graft Acknowledgment is not received within the Graft
Retransmission Time-out period, the Graft should be resent to the
upstream router. The initial retransmission period is 5 seconds. A
binary exponential back-off policy is used on subsequent
retransmissions. In order to send a Graft message, the following
steps should be taken:
1. Verify a forwarding cache entry exists for the (source network,
group) pair and that a prune exists for the cache entry.
2. Verify that the upstream router is capable of receiving prunes
(and therefore grafts).
3. Add the graft to the retransmission timer list awaiting an
acknowledgment.
Pusateri [Page 30]
INTERNET-DRAFT DVMRP Version 3 March 1998
4. Formulate and transmit the Graft packet.
3.6.3. Receiving a Graft
The actions taken when a Graft is received depends on the state in
the receiving router for the (source network, group) pair in the
received Graft message. If the Graft was received from a downstream
dependent neighbor from which a prune had previously been received,
then the prune state for this neighbor should be removed. If
necessary, any forwarding cache entries based on this (source
network, group) pair should be updated to include this downstream
interface. If a prune had been sent upstream, this may trigger a
graft to now be sent to the upstream router.
Whether or not any actions are taken, a Graft Acknowledgment must be
sent back to the source of the Graft message.
3.6.4. Graft Packet Format
The format of a Graft packet is show below:
7 15 23 31
+-----------+------------+-------------------------+
| Type | Code | Checksum |
| (0x13) | (0x8) | |
+-----------+------------+------------+------------+
| Reserved | Minor | Major |
+------------------------+------------+------------+
| Source Address |
+--------------------------------------------------+
| Group Address |
+--------------------------------------------------+
Figure 6 - Graft Packet Format
3.6.5. Sending a Graft Acknowledgment
A Graft Acknowledgment packet is sent to a downstream neighbor in
response to receiving a Graft message. All Graft messages should be
acknowledged. This is true even if no other action is taken in
Pusateri [Page 31]
INTERNET-DRAFT DVMRP Version 3 March 1998
response to receiving the Graft to prevent the source from
continually re-transmitting the Graft message. The Graft
Acknowledgment packet is identical to the Graft packet except that
the DVMRP code in the common header is set to Graft Ack. This allows
the receiver of the Graft Ack message to correctly identify which
Graft was acknowledged and stop the appropriate retransmission timer.
3.6.6. Receiving a Graft Acknowledgment
When a Graft Acknowledgment is received, the (source address, group)
pair in the packet can be used to determine if a Graft was sent to
this particular upstream router. If no Graft was sent, the Graft Ack
can simply be ignored. If a Graft was sent, and the acknowledgment
has come from the correct upstream router, then it has been
successfully received and the retransmission timer for the Graft can
be stopped.
3.6.7. Graft Acknowledgment Packet Format
The format of a Graft Ack packet (which is identical to that of a
Graft packet) is show below:
7 15 23 31
+-----------+------------+-------------------------+
| Type | Code | Checksum |
| (0x13) | (0x9) | |
+-----------+------------+------------+------------+
| Reserved | Minor | Major |
+------------------------+------------+------------+
| Source Address |
+--------------------------------------------------+
| Group Address |
+--------------------------------------------------+
Figure 7 - Graft Ack Packet Format
3.7. Interfaces
Interfaces running DVMRP will either be multicast capable physical
interfaces or encapsulated tunnel pseudo-interfaces. Physical
Pusateri [Page 32]
INTERNET-DRAFT DVMRP Version 3 March 1998
interfaces may either be multi-access networks or point-to-point
networks. Tunnel interfaces are used when there are non-multicast
capable routers between DVMRP neighbors. Protocol messages and
multicast data traffic are sent between tunnel endpoints using a
standard encapsulation method [Perk96,Han94a,Han94b]. The unicast IP
addresses of the tunnel endpoints are used as the source and
destination IP addresses in the outer IP header. The inner IP header
remains unchanged from the original packet.
Protocol messages on point-to-point links should always use a
destination IP address of All-DVMRP-Routers for ALL message types.
While Prune, Graft, and Graft-Ack messages are only intended for a
single recipient, the use of a multicast destination address is
necessary for un-numbered links and encapsulated interfaces.
When multiple addresses are configured on a single interface, it is
necessary that all routers on the interface know about the same set
of network addresses. In this way, each router will make the same
choice for the designated forwarder for each source. In addition, a
router configured with multiple addresses on an interface should
consistently use the same address when sending DVMRP control
messages.
The maximum packet length of any DVMRP message should be the maximum
packet size required to be forwarded without fragmenting. The use of
Path MTU Discovery [Mogu90] is encouraged to determine this size. In
the absence of Path MTU, the Requirements for Internet Hosts [Brad89]
specifies this number as 576 octets. Be sure to consider the size of
the encapsulated IP header as well when calculating the maximum size
of a DVMRP protocol message.
4. IANA Considerations
The Internet Assigned Numbers Authority (IANA) is the central
coordinator for the assignment of unique parameter values for
Internet protocols. DVMRP uses IGMP [Fenn97] IP protocol messages to
communicate between routers. The IGMP Type field is hexadecimal 0x13.
On IP multicast capable networks, DVMRP uses the All-DVMRP-Routers
local multicast group. This group address is 224.0.0.4.
5. Network Management Considerations
Pusateri [Page 33]
INTERNET-DRAFT DVMRP Version 3 March 1998
DVMRP provides several methods for network management monitoring and
troubleshooting. Appendix B describes a request/response mechanism to
directly query DVMRP neighbor information. In addition, a Management
Information Base for DVMRP is defined in [Thal97]. A protocol
independent multicast trace-route facility is defined in [Fenn96].
6. Security Considerations
Security for DVMRP follows the general security architecture provided
for the Internet Protocol [Atk95a]. This framework provides for both
privacy and authentication. It recommends the use of the IP
Authentication Header [Atk95b] to provide trusted neighbor
relationships. Confidentiality is provided by the addition of the IP
Encapsulating Security Payload [Atk95c]. Please refer to these
documents for the general architecture design as well as the specific
implementation details.
7. References
[Atk95a] Atkinson, R., "Security Architecture for the Internet
Protocol", RFC 1825, August 1995.
[Atk95b] Atkinson, R., "IP Authentication Header", RFC 1826, August
1995.
[Atk95c] Atkinson, R., "IP Encapsulating Security Payload (ESP)",
RFC 1827, August 1995.
[Brad89] Braden, R., "Requirements for Internet Hosts --
Communication Layers", RFC 1122, October 1989.
[Deer89] Deering, S., "Host Extensions for IP Multicasting", RFC
1112, August 1989.
[Deer90] Deering, S., Cheriton, D., "Multicast Routing in Datagram
Internetworks and Extended LANs", ACM Transactions on
Computer Systems, Vol. 8, No. 2, May 1990, pp. 85-110.
[Deer91] Deering, S., "Multicast Routing in a Datagram
Internetwork", PhD thesis, Electric Engineering Dept.,
Stanford University, December 1991.
Pusateri [Page 34]
INTERNET-DRAFT DVMRP Version 3 March 1998
[Fenn96] Fenner, W., Casner, S., "A "traceroute" facility for IP
Multicast", Work In Progress, November 1996.
[Fenn97] Fenner, W., "Internet Group Management Protocol, Version
2", Work In Progress, October 1997.
[Full93] Fuller, V., T. Li, J. Yu, and K. Varadhan, "Classless
Inter-Domain Routing (CIDR): an Address Assignment and
Aggregation Strategy", RFC 1519, September 1993.
[Han94a] Hanks, S., Li, T, Farinacci, D., and P. Traina, "Generic
Routing Encapsulation", RFC 1701, NetSmiths, Ltd., and
cisco Systems, October 1994.
[Han94b] Hanks, S., Li, T., Farinacci, D., and P. Traina, "Generic
Routing Encapsulation over IPv4 networks", RFC 1702,
NetSmiths, Ltd., cisco Systems, October 1994.
[Mogu90] Mogul, J., Deering, S., "Path MTU Discovery", RFC 1191,
November 1990.
[Perk96] Perkins, C., "IP Encapsulation within IP", RFC 2003,
October 1996.
[Perl92] Perlman, R., "Interconnections: Bridges and Routers",
Addison-Wesley, May 1992, pp. 205-211.
[Post81] Postel, J., "Internet Protocol", RFC 791, September, 1981.
[Rekh93] Rekhter, Y., and T. Li, "An Architecture for IP Address
Allocation with CIDR", RFC 1518, September 1993.
[Reyn94] Reynolds, J., Postel, J., "Assigned Numbers", STD 0002,
October 1994.
[Thal97] Thaler, D., "Distance-Vector Multicast Routing Protocol
MIB", Work In Progress, April 1997.
[Wait88] Waitzman, D., Partridge, C., Deering, S., "Distance Vector
Multicast Routing Protocol", RFC 1075, November 1988.
Pusateri [Page 35]
INTERNET-DRAFT DVMRP Version 3 March 1998
8. Author's Address
Thomas Pusateri
Juniper Networks, Inc.
385 Ravendale Dr.
Moutain View, CA 94043
Phone: (919) 558-0700
EMail: pusateri@juniper.net
9. Acknowledgments
The author would like to acknowledge the original designers of the
protocol, Steve Deering, Craig Partridge, and David Waitzman.
Version 3 of the protocol would not have been possible without the
original work of Ajit Thyagarajan and the ongoing (and seemingly
endless) work of Bill Fenner. Credit also goes to Danny Mitzel and
Dave Thaler for the careful review of this document and Nitin Jain,
Dave LeRoy, Charles Mumford, Ravi Shekhar, and Shuching Shieh for
their helpful comments.
Pusateri [Page 36]
INTERNET-DRAFT DVMRP Version 3 March 1998
10. Appendix A - Constants & Configurable Parameters
The following table provides a summary of the DVMRP timing
parameters:
Parameter Value (seconds)
----------------------------------------------------------
Probe Interval 10
Neighbor Time-out Interval 35
Minimum Flash Update Interval 5
Route Report Interval 60
Route Expiration Time 140
Route Hold-down 2 x Route Report Interval
Prune Lifetime variable (< 2 hours)
Prune Retransmission Time 3 with exp. back-off
Graft Retransmission Time 5 with exp. back-off
----------------------------------------------------------
Table 2 - Parameter Summary
Pusateri [Page 37]
INTERNET-DRAFT DVMRP Version 3 March 1998
11. Appendix B - Tracing and Troubleshooting support
There are several packet types used to gather DVMRP specific
information. They are generally used for diagnosing problems or
gathering topology information. The first two messages are now
obsoleted and should not be used. The remaining two messages provide
a request/response mechanism to determine the versions and
capabilities of a particular DVMRP router.
Code Packet Type Description
-----------------------------------------------------------
3 DVMRP Ask Neighbors Obsolete
4 DVMRP Neighbors Obsolete
5 DVMRP Ask Neighbors 2 Request Neighbor List
6 DVMRP Neighbors 2 Respond with Neighbor List
-----------------------------------------------------------
Table 3 - Debugging Packet Types
11.1. DVMRP Ask Neighbors2
The Ask Neighbors2 packet is a unicast request packet directed at a
DVMRP router. The destination should respond with a unicast
Neighbors2 message back to the sender of the Ask Neighbors2 message.
0 8 16 31
+---------+---------+--------------------+
| Type | Code | Checksum |
|(0x13) | (0x5) | |
+---------+---------+----------+---------+
| Reserved | Minor | Major |
| | Version |Version |
+-------------------+----------+---------+
Figure 8 - Ask Neighbors 2 Packet Format
Pusateri [Page 38]
INTERNET-DRAFT DVMRP Version 3 March 1998
11.2. DVMRP Neighbors2
The format of a Neighbors2 response packet is shown below. This is
sent as a unicast message back to the sender of an Ask Neighbors2
message. There is a common header at the top followed by the routers
capabilities. One or more sections follow that contain an entry for
each logical interface. The interface parameters are listed along
with a variable list of neighbors learned on each interface.
If the interface is down or disabled, list a single neighbor with an
address of 0.0.0.0 for physical interfaces or the remote tunnel
endpoint address for tunnel pseudo-interfaces.
Pusateri [Page 39]
INTERNET-DRAFT DVMRP Version 3 March 1998
0 8 16 31
+-----------+--------------+--------------------------+
| Type | Code | Checksum |
| (0x13) | (0x6) | |
+-----------+--------------+------------+-------------+
| Reserved | Capabilities | Minor | Major |
| | | Version | Version |
+-----------+--------------+------------+-------------+
| |
| Local Addr 1 |
+-----------+--------------+------------+-------------+
| | | | |
| Metric 1 | Threshold 1 | Flags 1 | Nbr Count 1 |
+-----------+--------------+------------+-------------+
| |
| Nbr 1 |
+-----------------------------------------------------+
| |
| ... |
+-----------------------------------------------------+
| |
| Nbr m |
+-----------------------------------------------------+
| |
| Local Addr N |
+-----------+--------------+------------+-------------+
| | | | |
| Metric N | Threshold N | Flags N | Nbr Count N |
+-----------+--------------+------------+-------------+
| |
| Nbr 1 |
+-----------------------------------------------------+
| |
| ... |
+-----------------------------------------------------+
| |
| Nbr k |
+-----------------------------------------------------+
Figure 9 - Neighbors 2 Packet Format
Pusateri [Page 40]
INTERNET-DRAFT DVMRP Version 3 March 1998
The capabilities of the local router are defined as follows:
Bit Flag Description
---------------------------------------------------
0 Leaf This is a leaf router
1 Prune This router understands pruning
2 GenID This router sends Generation Id's
3 Mtrace This router handles Mtrace requests
4 Snmp This router supports the DVMRP MIB
---------------------------------------------------
Table 4 - DVMRP Router Capabilities
Pusateri [Page 41]
INTERNET-DRAFT DVMRP Version 3 March 1998
The flags associated with a particular interface are:
Bit Flag Description
----------------------------------------------------------
0 Tunnel Neighbor reached via tunnel
1 Source Route Tunnel uses IP source routing
2 Reserved No longer used
3 Reserved No longer used
4 Down Operational status down
5 Disabled Administrative status down
6 Querier Querier for interface
7 Leaf No downstream neighbors on interface
----------------------------------------------------------
Table 5 - DVMRP Interface flags
Pusateri [Page 42]
INTERNET-DRAFT DVMRP Version 3 March 1998
12. Appendix C - Version Compatibility
There have been two previous major versions of DVMRP with
implementations still in circulation. If the receipt of a Probe
message reveals a major version of 1 or 2, then it can be assumed
that this neighbor does not support pruning or the use of the
Generation ID in the Probe message. However, since these older
implementations are known to safely ignore the Generation ID and
neighbor information in the Probe packet, it is not necessary to
send specially formatted Probe packets to these neighbors.
There were three minor versions (0, 1, and 2) of major version 3
that did support pruning but did not support the Generation ID or
capability flags. These special cases will have to be accounted
for.
Any other minor versions of major version 3 closely compare to
this specification.
In addition, cisco Systems is known to use their software major
and minor release number as the DVMRP major and minor version
number. These will typically be 10 or 11 for the major version
number. Pruning was introduced in Version 11.
Implementations prior to this specification may not wait to send
route reports until probe messages have been received with the
routers address listed. Reports SHOULD be sent to these neighbors
without first requiring a received probe with the routers address
in it as well as reports from these neighbors SHOULD be accepted.
Although, this allows one-way neighbor relationships to occur, it
does maintain backward compatibility.
It may be necessary to form neighbor relationships based solely on
Route Report messages. Neighbor timeout values may need to be
configured to a value greater than the Route Report Interval for
these neighbors.
Implementations that do not monitor Generation ID changes can
create more noticeable black holes when using long prune lifetimes
such as ~2 hours. This happens when a long prune is sent upstream
and then the router that sent the long prune restarts. If the
upstream router ignores the new Generation ID, the prune received
by the upstream router will not be flushed and the downstream
router will have no knowledge of the upstream prune. For this
reason, prunes sent upstream to routers that are known to ignore
Generation ID changes should have short lifetimes.
Pusateri [Page 43]
INTERNET-DRAFT DVMRP Version 3 March 1998
If the router must run IGMP version 1 on an interface for
backwards compatibility, DVMRP must elect the DVMRP router with
the highest IP address as the IGMP querier.
Some implementations of tools that send DVMRP Ask Neighbors2
requests and receive Neighbors2 response messages require a
neighbor address of 0.0.0.0 when no neighbors are listed in the
response packet. (Mrinfo)
When DVMRP protocol packets are sent to tunnel endpoints, some
implementations do not accept packets addressed to the All-DVMRP-
Routers address and then encapsulated with the tunnel endpoint
address. Mrouted versions 3.9beta2 and earlier are known to have
this problem.
Pusateri [Page 44]
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 2
1.1. Reverse Path Multicasting . . . . . . . . . . . . . . . . 2
1.2. Tunnel Encapsulation . . . . . . . . . . . . . . . . . . 2
1.3. Document Overview . . . . . . . . . . . . . . . . . . . . 3
2. Protocol Overview . . . . . . . . . . . . . . . . . . . . . 3
2.1. Neighbor Discovery . . . . . . . . . . . . . . . . . . . 3
2.2. Source Location . . . . . . . . . . . . . . . . . . . . . 4
2.3. Dependent Downstream Routers . . . . . . . . . . . . . . 5
2.4. Designated Forwarder . . . . . . . . . . . . . . . . . . 5
2.5. Building Multicast Trees . . . . . . . . . . . . . . . . 6
2.6. Pruning Multicast Trees . . . . . . . . . . . . . . . . . 7
2.7. Grafting Multicast Trees . . . . . . . . . . . . . . . . 8
3. Detailed Protocol Operation . . . . . . . . . . . . . . . . 8
3.1. Protocol Header . . . . . . . . . . . . . . . . . . . . . 8
3.2. Probe Messages . . . . . . . . . . . . . . . . . . . . . 9
3.3. Building Forwarding Cache Entries . . . . . . . . . . . . 15
3.4. Route Exchange . . . . . . . . . . . . . . . . . . . . . 16
3.5. Pruning . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.6. Grafting . . . . . . . . . . . . . . . . . . . . . . . . 29
3.7. Interfaces . . . . . . . . . . . . . . . . . . . . . . . 32
4. IANA Considerations . . . . . . . . . . . . . . . . . . . . 33
5. Network Management Considerations . . . . . . . . . . . . . 33
6. Security Considerations . . . . . . . . . . . . . . . . . . 34
7. References . . . . . . . . . . . . . . . . . . . . . . . . 34
8. Author's Address . . . . . . . . . . . . . . . . . . . . . 35
9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . 36
10. Appendix A - Constants & Configurable Parameters . . . . . 37
11. Appendix B - Tracing and Troubleshooting support . . . . . 38
11.1. DVMRP Ask Neighbors2 . . . . . . . . . . . . . . . . . . 38
11.2. DVMRP Neighbors2 . . . . . . . . . . . . . . . . . . . . 39
12. Appendix C - Version Compatibility . . . . . . . . . . . . 43
Pusateri [Page i]
| PAFTECH AB 2003-2026 | 2026-04-23 10:49:37 |