[Docs] [txt|pdf] [Tracker] [WG] [Email] [Nits]
Versions: 00 01 02 03 04 05 06 07 08 09 10 11
INTERNET-DRAFT T. Pusateri
Obsoletes: RFC 1075 NetEdge Systems
February 1996
Expires: August 1996
Distance Vector Multicast Routing Protocol
<draft-ietf-idmr-dvmrp-v3-00.txt>
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).
1. Introduction
DVMRP is a TCP/IP routing protocol that provides an
efficient mechanism for connectionless datagram delivery to
a group of hosts across an internetwork. It is a
distributed protocol that dynamically generates multicast
delivery trees for IP Multicast datagrams using a technique
called Reverse Path Multicasting (RPM) [1]. This document
describes Version 3 of the protocol replacing Version 1
specified in RFC 1075 [2].
Pusateri [Page 1]
INTERNET-DRAFT DVMRP Version 3 February 1996
1.1 Reverse Path Multicasting
Datagrams follow multicast delivery trees from a source to
all members of a multicast group [3], 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 unicast routing table
of known source networks. If the datagram arrives on an
interface that would be used to transmit unicast 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 IP-IP Tunnels
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.
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 interoperable implementations. The interaction
Pusateri [Page 2]
INTERNET-DRAFT DVMRP Version 3 February 1996
with the Internet Group Management Protocol (IGMP) [4] is
discussed in Appendix A. A summary of the DVMRP constants
and configurable parameters are included in Appendix B. A
section on DVMRP support for tracing and troubleshooting
procedures is the topic of Appendix C. Finally, a short
DVMRP version history is provided in Appendix D to assist
with backward compatibility issues.
Table of Contents
1. INTRODUCTION ...........................................1
1.1 REVERSE PATH MULTICASTING ............................2
1.2 IP-IP TUNNELS ........................................2
1.3 DOCUMENT OVERVIEW ....................................2
2. PROTOCOL OVERVIEW ......................................5
2.1 NEIGHBOR DISCOVERY ...................................5
2.2 SOURCE LOCATION ......................................6
2.3 DEPENDENT DOWNSTREAM ROUTERS .........................7
2.4 BUILDING MULTICAST TREES .............................8
2.4.1 Adding Leaf Networks .............................8
2.4.2 Adding Non-Leaf Networks .........................9
2.5 PRUNING MULTICAST TREES ..............................9
2.6 GRAFTING MULTICAST TREES ............................10
2.7 SUPPRESSING DUPLICATE PACKETS .......................11
3. DETAILED PROTOCOL OPERATION ...........................11
3.1 PROTOCOL HEADER .....................................11
3.2 DVMRP PROBE MESSAGES ................................12
3.2.1 Router Capabilities .............................13
3.2.2 Generation ID ...................................14
3.2.3 Neighbor Addresses ..............................14
3.2.4 Probe Packet Format .............................15
3.2.5 Designated Router Election ......................16
3.3 BUILDING FORWARDING CACHE ENTRIES ...................16
3.3.1 Determining the upstream interface ..............16
3.3.2 Determining the downstream interface list .......16
3.4 UNICAST ROUTE EXCHANGE ..............................17
Pusateri [Page 3]
INTERNET-DRAFT DVMRP Version 3 February 1996
3.4.1 Route Packing and Ordering ......................17
3.4.2 Unicast Route Metrics ...........................18
3.4.3 Unicast Route Dependencies ......................19
3.4.4 Sending Route Reports ...........................19
3.4.5 Receiving Route Reports .........................20
3.4.6 Route Report Packet Format ......................20
3.5 PRUNING .............................................21
3.5.1 Leaf Networks ...................................21
3.5.2 Source Networks .................................22
3.5.3 Receiving a Prune ...............................22
3.5.4 Sending a Prune .................................23
3.5.5 Prune Packet Format .............................23
3.6 GRAFTING ............................................23
3.6.1 Grafting All Sources ............................24
3.6.2 Sending a Graft .................................24
3.6.3 Receiving a Graft ...............................24
3.6.4 Graft Packet Format .............................26
3.6.5 Sending a Graft Acknowledgment ..................26
3.6.6 Receiving a Graft Acknowledgment ................26
3.6.7 Graft Acknowledgment Packet Format ..............27
3.7 LOOP DETECTION AND SUPPRESSION ......................27
3.8 INTERFACES ..........................................27
3.8.1 IP Tunnels ......................................27
3.8.2 Parameters ......................................27
3.8.3 Metric ..........................................27
3.8.4 Threshold .......................................27
3.8.5 Scope Control ...................................27
4. SECURITY CONSIDERATIONS ...............................27
5. REFERENCES ............................................27
6. AUTHOR'S ADDRESS ......................................29
7. APPENDIX A - INTERACTION WITH IGMP (V1 & V2) ..........29
8. APPENDIX B - CONSTANTS & CONFIGURABLE PARAMETERS ......29
Pusateri [Page 4]
INTERNET-DRAFT DVMRP Version 3 February 1996
9. APPENDIX C - TRACING AND TROUBLESHOOTING SUPPORT ......29
9.1 DVMRP ASK NEIGHBORS .................................30
9.2 DVMRP NEIGHBORS .....................................30
9.3 DVMRP ASK NEIGHBORS2 ................................30
9.4 DVMRP NEIGHBORS2 ....................................30
9.5 DVMRP INFO MESSAGE ..................................30
10. APPENDIX D - VERSION HISTORY .........................30
2. Protocol Overview
2.1 Neighbor Discovery
Neighbor DVMRP routers can be discovered dynamically by
sending Neighbor Probe Messages on all of the local
multicast capable network interfaces. These messages are
sent periodically to the All-DVMRP-Routers IP Multicast
group address. This address falls into the range of IP
Multicast addresses that are to remain on the locally
attached IP network and therefore are not forwarded by
multicast routers. Beginning with Version 3 of DVMRP
outlined in this document, each Neighbor Probe message
should contain the list of Neighbor DVMRP routers for which
Neighbor Probe messages have been received. In this way,
Neighbor DVMRP routers can ensure that they are seen by
each other. Care must be taken to interoperate 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. In addition to the
list of known neighbors, the Probe message should contain a
set of flags describing the attributes of the DVMRP router.
There are currently four attributes defined.
1. PRUNE - This router supports Pruning of multicast
delivery trees
2. GENID - This router is including a Generation
Identifier in the probe message that can be used to
Pusateri [Page 5]
INTERNET-DRAFT DVMRP Version 3 February 1996
detect when a neighbor wants to re-synchronize its
unicast routing database.
3. LEAF - This router considers itself a leaf router.
(i.e. it is not aware of any downstream multicast
routers.)
4. MTRACE - This router is capable of responding to a
multicast trace route request.
As mentioned before, DVMRP versions prior to this
specification may not include this set of flags and this
information will have to be determined by the DVMRP Major
and Minor version numbers.
2.2 Source Location
When an IP Multicast datagram is received by a router
running DVMRP, it first looks up the interface of the
unicast route back to the source of the datagram. This
interface 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 unicast path back to a source, a unicast
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 allows for 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 computed before the route is compared to the
metric of the current next hop gateway. As is customary
with distance vector routing protocols, split horizon
should be applied to the route propagation policy in order
Pusateri [Page 6]
INTERNET-DRAFT DVMRP Version 3 February 1996
to prevent advertising a route to a destination over the
interface from which it was received.
Although there is certainly additional overhead associated
with propagating a separate unicast routing table, it does
provide two nice features. First, since all DVMRP routers
are using the same unicast routing protocol, there are no
inconsistencies between routers when determining the
upstream interface (aside from normal convergence issues
related 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 blackholes due to disagreement between
neighbor routers on the upstream interface.
Second, by propagating its own unicast 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. For these benefits, DVMRP
has chosen to accept the additional overhead of propagating
unicast routes.
2.3 Dependent Downstream Routers
In addition to providing a consistent view of source
networks, the exchange of unicast routes in DVMRP provides
one other important feature. DVMRP uses the unicast 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 well known technique called _Poison Reverse_. If a
downstream router selects a particular upstream router as
the best next hop to a particular source network, then it
signifies this to the upstream router by echoing back the
route to the upstream router with a metric equal to the
original metric plus infinity. When the upstream router
Pusateri [Page 7]
INTERNET-DRAFT DVMRP Version 3 February 1996
receives the report and sees a metric that lies between
infinity and two times 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 source specific IP multicast trees.
2.4 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.4.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 other IP multicast
routers on it), 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 an elected IP multicast router on
each physical, multicast capable network. The details of
the election procedure are discussed in section 3. If the
destination group address is listed in the local group
database, 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 pruned from the
candidate list.
Pusateri [Page 8]
INTERNET-DRAFT DVMRP Version 3 February 1996
2.4.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. This allows all downstream routers to
be aware of traffic destined for a particular (source,
group) pair. The downstream routers will then have the
option to prune and graft this (source, group) pair to and
from the multicast delivery tree as requirements change
from their downstream routers and local group members.
2.5 Pruning Multicast Trees
As mentioned above, routers at the edges with leaf networks
will prune their leaf interfaces that have no group members
associated with an IP multicast datagram. If a router
prunes all of its downstream interfaces, it can notify the
upstream router that it no longer wants traffic destined
for a particular (source, 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 unicast
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 prune this
interface from its downstream interface list. If the
upstream router is able to prune all of its downstream
interfaces in this way, it can then send a DVMRP Prune
message to its upstream router. This continues until the
minimum tree necessary to reach all of the receivers
remains. Since IP multicast routers may be restarted at any
time and lose state information about existing prunes, it
is necessary to limit the life of a prune and periodically
resume the flooding procedure. This will reinitiate the
prune mechanism and the cycle will continue. When a router
decides to prune one of its downstream interfaces, it will
set a timer to indicate the lifetime of the prune. If all
Pusateri [Page 9]
INTERNET-DRAFT DVMRP Version 3 February 1996
of its downstream interfaces become pruned off the
multicast delivery tree and a DVMRP Prune message is sent
upstream, the lifetime of the prune will be equal to the
minimum of the remaining lifetimes of the pruned
interfaces.
2.6 Grafting Multicast Trees
Once a tree branch has been pruned from a multicast
delivery tree, packets from the pruned (source, group) pair
will no longer be forwarded. There are two different ways
for packets from the (source, group) pair to be forwarded
again. First, since IP multicast supports dynamic group
membership, new hosts may join the multicast group. In this
case, DVMRP routers will need a mechanism to undo the
prunes that are in place from the host back to the first
branch that was pruned from the multicast tree. This is
accomplished with a DVMRP Graft message. A router will send
a Graft message to its upstream neighbor if a group join
occurs for a group that currently has pruned sources.
Separate Graft messages must be sent to the appropriate
upstream neighbor for each source 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. Second, if the prune interval
expires, the negative cache entries are removed and the
packets will automatically be forwarded again. This is a
necessary feature since routers may be restarted and lose
all prune state information or new routers may appear.
Since these routers will not have prune state associated
with the (source, group) pair, they will not realize that a
DVMRP Graft message is necessary if a new host joins the
group. Therefore, by periodically timing out the prunes and
re-flooding the traffic, any new or restarted routers can
have their prune state periodically refreshed.
Pusateri [Page 10]
INTERNET-DRAFT DVMRP Version 3 February 1996
2.7 Suppressing Duplicate Packets
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. All DVMRP packets use a common protocol
header that specifies the IGMP Packet Type as hexadecimal
0x13 (DVMRP). A diagram of the common protocol header
follows:
Table 1 - Common Protocol Header
0 8 16 31
+--------------------------------------+
| | | |
| Type | Code | Checksum |
| (0x13) | | |
+--------------------------------------+
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:
Pusateri [Page 11]
INTERNET-DRAFT DVMRP Version 3 February 1996
Table 2 - Standard Protocol Packet Types
Code Packet Type Description
-------------------------------------------
1 DVMRP Probe for neighbor discovery
2 DVMRP Report for unicast route
exchange
7 DVMRP Prune for pruning multicast
delivery trees
8 DVMRP Graft for grafting multicast
delivery trees
9 DVMRP Graft for acknowledging
Ack graft messages
-------------------------------------------
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 DVMRP Probe Messages
When a DVMRP router is configured to run on an physical
interface, it sends local IP Multicast discovery packets to
inform other DVMRP routers that it is operational. These
discovery packets are called DVMRP Probes and they serve
three purposes.
1. Probes provide a mechanism for DVMRP routers to locate
each other. The existence of other routers is used for
network leaf detection and the list of addresses of
the other routers are used in designated router
Pusateri [Page 12]
INTERNET-DRAFT DVMRP Version 3 February 1996
election. In addition, this list of DVMRP neighbors
provides a foundation for neighbor prune lists.
2. They 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. Examples
of these capabilities are whether Generation IDs are
used, if the neighbor supports pruning, if the
neighbor is a leaf router, and whether the neighbor
supports the multicast trace route function.
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 140 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 interoperate with these
older implementations that don't formally specify their
capabilities. 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 version 3.5 in an attempt to take the guess work out
which features are supported by a neighbor. A complete
version history is summarized in Appendix A to assist with
backward compatibility. A DVMRP router MUST specify its
capabilities in a Probe message. The following capabilities
are currently defined:
Pusateri [Page 13]
INTERNET-DRAFT DVMRP Version 3 February 1996
Table 3 - Probe Capability Flags
15 8 7 0
+--------------------------------------+
| | |
| Reserved | M G P L|
| | |
+--------------------------------------+
LEAF - The LEAF bit is set if the router does not
have any downstream DVMRP neighbor routers.
PRUNE - router is capable of handling prunes
GENID - router keeps a non-decreasing generation id
for synchronization on restart.
MTRACE - router includes multicast trace route
support
3.2.2 Generation ID
If a DVMRP router is restarted, it must immediately
exchange unicast routing tables with all of its neighbors.
If a neighbor doesn't automatically detect that the
neighbor has restarted, then it will not send its entire
routing table immediately. Instead, it will spread the
updates over an entire routing update interval. In order
for the neighbor to detect a router that is restarted, a
non-decreasing number is placed in the periodic probe
message called the generation ID. If a router detects an
increase in the generation ID of a neighbor, it should
exchange its entire unicast routing table with the
neighbor. 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
Pusateri [Page 14]
INTERNET-DRAFT DVMRP Version 3 February 1996
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.
3.2.4 Probe Packet Format
The Probe packet is variable in length depending on the
number of neighbor IP addresses included. 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 are HIGHLY discouraged at this time.
Table 4 - DVMRP Probe Packet Format
0 8 16 24
+-------------------+--------+---------+
| | | |
| Capabilities | Minor | Major |
| |Version | Version |
+-------------------+--------+---------+
| |
| Generation ID |
+--------------------------------------+
| |
| Neighbor IP Address 1 |
+--------------------------------------+
| |
| Neighbor IP Address 2 |
+--------------------------------------+
| |
| ... |
+--------------------------------------+
| |
| Neighbor IP Address N |
+--------------------------------------+
Pusateri [Page 15]
INTERNET-DRAFT DVMRP Version 3 February 1996
3.2.5 Designated Router Election
Since it is wasteful to have more than a single router
sending IGMP Host Membership Queries on a given physical
network, DVMRP provides a method to elect a single router
on each physical network as the Designated Querier. Based
on the list of neighbors from which DVMRP Probe messages
were received, a router will pick the router with the
lowest IP address as the designated querier. The router
must be sure and include itself in this list of candidates.
3.3 Building Forwarding Cache Entries
In order to create optimal multicast delivery trees, IP
Multicast 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. For this reason, DVMRP includes its own unicast
routing protocol.
3.3.1 Determining the upstream interface
When a multicast packet arrives, a DVMRP router will use
the internal DVMRP unicast 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
unicast routing table.
3.3.2 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 and do not have members of the
particular multicast group can be automatically pruned from
list of downstream interfaces. The remaining interfaces
Pusateri [Page 16]
INTERNET-DRAFT DVMRP Version 3 February 1996
will either have downstream DVMRP routers or directly
attached group members. These interfaces may be pruned in
the future if it is determined that there are no group
members anywhere along the entire tree branch.
3.4 Unicast 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 interface than the upstream
interface back to the unicast source of the multicast
datagram.
Therefore, when determining the reverse path back to a
particular source it is not always possible to use the
standard unicast routing table. DVMRP's solution to this
problem is to create its own routing table of unicast
routes for determining upstream routers for each source.
This routing information is used exclusively for
determining the reverse path back to source of multicast
traffic. Tunnels are considered to be distinct interfaces
and route reports are sent unicast between tunnel endpoints
as though they arrived on the tunnel pseudo interface. The
routing information that is propagated by DVMRP contains a
list of unicast source networks and an appropriate metric.
The metric used is a hop count which is incremented by the
cost of the outgoing interface. 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
in order to prevent routing loops although the protocol
does not strictly enforce this.
3.4.1 Route Packing and Ordering
Since DVMRP Route Reports may need to refresh several
thousand routes each Report interval, routers MUST attempt
Pusateri [Page 17]
INTERNET-DRAFT DVMRP Version 3 February 1996
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. One implementation
splits all unicast routes across 6 Report periods sent at
10 seconds intervals. Due to limitations of older
implementations of DVMRP, Route Reports should contain
source network/mask pairs sorted first by increasing
network mask and then by increasing source network within
each possible mask value.
In order to pack more source networks into a route report,
source networks are often represented by less than 4
octets. The number of significant 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.
Immediately following each source network is an octet
containing the metric advertised to reach the source
network.
3.4.2 Unicast Route Metrics
For each source network reported, a route metric is also
contained in the route report. The metric is the sum of the
outgoing interface metrics between the router originating
the report and the source network. 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.
Pusateri [Page 18]
INTERNET-DRAFT DVMRP Version 3 February 1996
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, then 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. This technique is
used to prevent wasting space in the Route Report message
for a count of unicast source networks for each netmask
value contained in the Report.
3.4.3 Unicast 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
pruned when it has received Prune messages from each of the
dependent routers on that interface. Each downstream router
uses a method called 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*Infinity -1 or 1 and 63.
Values between 1 and 31 indicate reachable unicast source
networks. The value of Infinity or 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.4 Sending Route Reports
Full Route Reports MUST be sent out every Route Report
Interval. In addition, flash updates CAN be sent between
Pusateri [Page 19]
INTERNET-DRAFT DVMRP Version 3 February 1996
full route reports. 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.
3.4.5 Receiving Route Reports
3.4.6 Route Report Packet Format
The format of a sample Route Report Packet is shown in
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.
Pusateri [Page 20]
INTERNET-DRAFT DVMRP Version 3 February 1996
Table 5 - Route Report Packet Format
0 8 16 31
+--------+---------+---------+---------+
| | | | |
| Mask | Mask | Mask | Src |
|Octet 2 | Octet 3 | Octet 4 | Net11 |
+--------+---------+---------+---------+
|Src Net11 (cont.) | Metric Src |
| ... | Net12 |
+------------------+-------------------+
|Src Net12 (cont.) | Metric + Mask |
| ... | 0x80 Octet 2 |
+------------------+-------------------+
| Mask Mask | Src Net21 |
|Octet 3 Octet 4 | |
+------------------+-------------------+
|Src Net21 (cont.) | Metric + Mask |
| ... | 0x80 Octet 2 |
+------------------+-------------------+
| Mask Mask | ... |
|Octet 3 Octet 4 | |
+------------------+-------------------+
3.5 Pruning
DVMRP is described as a flood and prune multicast routing
protocol since datagrams are initially sent out all
dependent downstream interfaces and then pruned back to
only the downstream interfaces that are on a reverse
shortest path to a receiver. Prunes are data driven and are
sent in response to receiving unwanted multicast traffic at
the leafs of the multicast tree rooted at a particular
source network.
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 DVMRP Probe Messages. If there
are no group members present for a particular multicast
Pusateri [Page 21]
INTERNET-DRAFT DVMRP Version 3 February 1996
datagram received, the leaf routers will start the pruning
process by pruning their downstream interfaces and sending
a prune to the upstream router for that source.
3.5.2 Source Networks
It is important to remember that because prunes are based
on group membership, a prune sent upstream for a particular
source applies to all sources on the source network. It is
not possible to prune only one or a subset of hosts on a
source network for a particular group. All or none of the
sources on a source network sending to a particular group
must be pruned.
3.5.3 Receiving a Prune
When a prune is received, the following steps should be
taken:
1. Determine if a Probe has been received from this
router recently.
2. If not, discard prune since there is no prior state
about this neighbor.
3. If so, make sure the neighbor advertises it is capable
of pruning.
4. Ensure the packet meets the minimum length requirement
for a prune.
5. Extract the source address, group address, and prune
time-out values
6. If no state exists for the (source, group) pair, then
ignore the prune.
7. Verify that the prune was received from a dependent
neighbor for the source network. If not, discard the
prune.
8. Determine if a prune is currently active for this
(source, group) pair.
9. 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.
10. Determine if all dependent downstream routers have now
sent prunes.
11. If so, a prune should be sent upstream.
Pusateri [Page 22]
INTERNET-DRAFT DVMRP Version 3 February 1996
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.
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 cache lifetime of the
(source, group) pair.
5. Form and transmit the packet to the upstream neighbor
for the source.
3.5.5 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.
Table 6 - Prune Packet Format
0 31
+--------------------------------------+
| |
| Source Address |
+--------------------------------------+
| |
| Group Address |
+--------------------------------------+
| |
| Prune Lifetime |
+--------------------------------------+
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 receivers 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
Pusateri [Page 23]
INTERNET-DRAFT DVMRP Version 3 February 1996
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.
3.6.1 Grafting All Sources
It is important to realize that prunes are source specific
and are sent up different trees for each source. 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 a Graft Retransmission Time-out period, the
Graft should be resent to the upstream router. The time-out
period is fixed at 5 seconds.
In order to send a Graft message, the following steps
should be taken:
1. Verify a forwarding cache entry exists for the
(source, 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.
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, group) pair
in the received Graft message. If the receiving router has
prune state for the (source, group) pair, then it must
acknowledge the received graft and send a subsequent graft
to its upstream router.
Pusateri [Page 24]
INTERNET-DRAFT DVMRP Version 3 February 1996
If the receiving router has some pruned downstream
interfaces but has not sent a prune upstream, then the
receiving interface can simply be added to the list of
downstream interfaces in the forwarding cache. A Graft
Acknowledgment must also be sent back to the source of the
Graft message.
If the receiving router has no state at all for the
(source, group) pair, then datagrams arriving for the
(source, group) pair should automatically be flooded when
they arrive. A Graft Acknowledgment must be sent to the
source of the Graft message.
If a Graft message is received from an unknown neighbor, it
should be discarded.
Pusateri [Page 25]
INTERNET-DRAFT DVMRP Version 3 February 1996
3.6.4 Graft Packet Format
The format of a Graft packet is show below:
Table 7 - Graft Packet Format
0 31
+--------------------------------------+
| |
| Source Address |
+--------------------------------------+
| |
| Group Address |
+--------------------------------------+
3.6.5 Sending a Graft Acknowledgment
A Graft Acknowledgment packet is sent to a downstream
neighbor in response to receiving a Graft message. Grafts
received from unknown neighbors should be discarded but all
other correctly formatted Graft messages should be
acknowledged. This is true even if no other action is taken
in 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,
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.
Pusateri [Page 26]
INTERNET-DRAFT DVMRP Version 3 February 1996
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:
Table 8 - Graft Ack Packet Format
0 31
+--------------------------------------+
| |
| Source Address
+--------------------------------------+
| |
| Group Address
+--------------------------------------+
3.7 Loop Detection and Suppression
3.8 Interfaces
3.8.1 IP Tunnels
3.8.2 Parameters
3.8.3 Metric
3.8.4 Threshold
3.8.5 Scope Control
4. Security Considerations
Security considerations will be discussed in an upcoming
revision of this document.
5. References
[1]. Deering, S., Cheriton, D., "Multicast Routing in
Datagram Internetworks and Extended LANs", ACM
Transactions on Computer Systems, Vol. 8, No. 2, May
1990, Pages 85-110.
[2]. Waitzman, D., Partridge, C., Deering, S., "Distance
Vector Multicast Routing Protocol", RFC 1075,
Internet Architecture Board, November 1988.
Pusateri [Page 27]
INTERNET-DRAFT DVMRP Version 3 February 1996
[3]. Deering, S., "Host Extensions for IP Multicasting",
RFC 1112, Internet Architecture Board, August 1989.
[4]. Deering, S., "Host Extensions for IP Multicasting -
Appendix 1 (IGMP)", RFC 1112, Internet Architecture
Board, August 1989.
Pusateri [Page 28]
INTERNET-DRAFT DVMRP Version 3 February 1996
6. Author's Address
Thomas Pusateri
NetEdge Systems, Inc.
PO Box 14993
Research Triangle Park, NC 27709
Phone: 919-991-9028
Fax: 919-991-9060
EMail: pusateri@NetEdge.COM
7. Appendix A - Interaction with IGMP (V1 & V2)
8. Appendix B - Constants & Configurable Parameters
9. Appendix C - Tracing and Troubleshooting support
Table 9 - Tracing and Debugging Packet Types
Code Packet Type Description
---------------------------------------------
3 DVMRP Ask Obsolete
Neighbors
4 DVMRP Neighbors Obsolete
5 DVMRP Ask Request Neighbor List
Neighbors 2
6 DVMRP Neighbors 2 Respond with Neighbor
List
13 DVMRP Info General Information
Request/Reply
---------------------------------------------
Pusateri [Page 29]
INTERNET-DRAFT DVMRP Version 3 February 1996
9.1 DVMRP Ask Neighbors
9.2 DVMRP Neighbors
9.3 DVMRP Ask Neighbors2
9.4 DVMRP Neighbors2
9.5 DVMRP Info message
10. Appendix D - Version History
Pusateri [Page 30]
Html markup produced by rfcmarkup 1.129d, available from
https://tools.ietf.org/tools/rfcmarkup/