idnits 2.17.1 draft-ietf-idmr-dvmrp-v3-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-19) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an Abstract section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. == There are 1 instance of lines with non-RFC6890-compliant IPv4 addresses in the document. If these are example addresses, they should be changed. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 479: '... SHOULD have an interval of ...' RFC 2119 keyword, line 480: '...ime-out interval SHOULD be set at 140 ...' RFC 2119 keyword, line 483: '... values MUST be coordinated b...' RFC 2119 keyword, line 497: '...ility. A DVMRP router MUST specify its...' RFC 2119 keyword, line 654: '... Report interval, routers MUST attempt...' (1 more instance...) Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 406 has weird spacing: '...ets are encap...' == Line 432 has weird spacing: '...P Probe for ...' == Line 434 has weird spacing: '... Report for u...' == Line 437 has weird spacing: '...P Prune for ...' == Line 440 has weird spacing: '...P Graft for ...' == (3 more instances...) -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (February 1996) is 10291 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Possible downref: Non-RFC (?) normative reference: ref. '1' ** Downref: Normative reference to an Experimental RFC: RFC 1075 (ref. '2') -- Duplicate reference: RFC1112, mentioned in '4', was also mentioned in '3'. Summary: 11 errors (**), 0 flaws (~~), 8 warnings (==), 4 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 INTERNET-DRAFT T. Pusateri 2 Obsoletes: RFC 1075 NetEdge Systems 3 February 1996 4 Expires: August 1996 6 Distance Vector Multicast Routing Protocol 7 9 Status of this Memo 11 This document is an Internet-Draft. Internet-Drafts are 12 working documents of the Internet Engineering Task Force 13 (IETF), its areas, and its working groups. Note that other 14 groups may also distribute working documents as Internet- 15 Drafts. 17 Internet-Drafts are draft documents valid for a maximum of 18 six months and may be updated, replaced, or obsoleted by 19 other documents at any time. It is inappropriate to use 20 Internet-Drafts as reference material or to cite them other 21 than as `'work in progress.'' 23 To learn the current status of any Internet-Draft, please 24 check the `'1id-abstracts.txt'' listing contained in the 25 Internet-Drafts Shadow Directories on ftp.is.co.za 26 (Africa), nic.nordu.net (Europe), munnari.oz.au (Pacific 27 Rim), ds.internic.net (US East Coast), or ftp.isi.edu (US 28 West Coast). 30 1. Introduction 31 DVMRP is a TCP/IP routing protocol that provides an 32 efficient mechanism for connectionless datagram delivery to 33 a group of hosts across an internetwork. It is a 34 distributed protocol that dynamically generates multicast 35 delivery trees for IP Multicast datagrams using a technique 36 called Reverse Path Multicasting (RPM) [1]. This document 37 describes Version 3 of the protocol replacing Version 1 38 specified in RFC 1075 [2]. 40 1.1 Reverse Path Multicasting 41 Datagrams follow multicast delivery trees from a source to 42 all members of a multicast group [3], replicating the 43 packet only at necessary branches in the delivery tree. The 44 trees are calculated and updated dynamically to track the 45 membership of individual groups. When a datagram arrives 46 on an interface, the reverse path to the source of the 47 datagram is determined by examining a unicast routing table 48 of known source networks. If the datagram arrives on an 49 interface that would be used to transmit unicast datagrams 50 back to the source, then it is forwarded to the appropriate 51 list of downstream interfaces. Otherwise, it is not on the 52 optimal delivery tree and should be discarded. In this way 53 duplicate packets can be filtered when loops exist in the 54 network topology. The source specific delivery trees are 55 automatically pruned back as group membership changes or 56 leaf routers determine that no group members are present. 57 This keeps the delivery trees to the minimum branches 58 necessary to reach all of the group members. New sections 59 of the tree can also be added dynamically as new members 60 join the multicast group by grafting the new sections onto 61 the delivery trees. 63 1.2 IP-IP Tunnels 64 Because not all IP routers support native multicast 65 routing, DVMRP includes direct support for tunneling IP 66 Multicast datagrams through routers. The IP Multicast 67 datagrams are encapsulated in unicast IP packets and 68 addressed to the routers that do support native multicast 69 routing. DVMRP treats tunnel interfaces in an identical 70 manner to physical network interfaces. 72 1.3 Document Overview 73 Section 2 provides an overview of the protocol and the 74 different message types exchanged by DVMRP routers. Those 75 who wish to gain a general understanding of the protocol 76 but are not interested in the more precise details may wish 77 to only read this section. Section 3 explains the detailed 78 operation of the protocol to accommodate developers needing 79 to provide interoperable implementations. The interaction 80 with the Internet Group Management Protocol (IGMP) [4] is 81 discussed in Appendix A. A summary of the DVMRP constants 82 and configurable parameters are included in Appendix B. A 83 section on DVMRP support for tracing and troubleshooting 84 procedures is the topic of Appendix C. Finally, a short 85 DVMRP version history is provided in Appendix D to assist 86 with backward compatibility issues. 88 Table of Contents 90 1. INTRODUCTION ...........................................1 92 1.1 REVERSE PATH MULTICASTING ............................2 93 1.2 IP-IP TUNNELS ........................................2 94 1.3 DOCUMENT OVERVIEW ....................................2 96 2. PROTOCOL OVERVIEW ......................................5 98 2.1 NEIGHBOR DISCOVERY ...................................5 99 2.2 SOURCE LOCATION ......................................6 100 2.3 DEPENDENT DOWNSTREAM ROUTERS .........................7 101 2.4 BUILDING MULTICAST TREES .............................8 102 2.4.1 Adding Leaf Networks .............................8 103 2.4.2 Adding Non-Leaf Networks .........................9 104 2.5 PRUNING MULTICAST TREES ..............................9 105 2.6 GRAFTING MULTICAST TREES ............................10 106 2.7 SUPPRESSING DUPLICATE PACKETS .......................11 108 3. DETAILED PROTOCOL OPERATION ...........................11 110 3.1 PROTOCOL HEADER .....................................11 111 3.2 DVMRP PROBE MESSAGES ................................12 112 3.2.1 Router Capabilities .............................13 113 3.2.2 Generation ID ...................................14 114 3.2.3 Neighbor Addresses ..............................14 115 3.2.4 Probe Packet Format .............................15 116 3.2.5 Designated Router Election ......................16 117 3.3 BUILDING FORWARDING CACHE ENTRIES ...................16 118 3.3.1 Determining the upstream interface ..............16 119 3.3.2 Determining the downstream interface list .......16 120 3.4 UNICAST ROUTE EXCHANGE ..............................17 121 3.4.1 Route Packing and Ordering ......................17 122 3.4.2 Unicast Route Metrics ...........................18 123 3.4.3 Unicast Route Dependencies ......................19 124 3.4.4 Sending Route Reports ...........................19 125 3.4.5 Receiving Route Reports .........................20 126 3.4.6 Route Report Packet Format ......................20 127 3.5 PRUNING .............................................21 128 3.5.1 Leaf Networks ...................................21 129 3.5.2 Source Networks .................................22 130 3.5.3 Receiving a Prune ...............................22 131 3.5.4 Sending a Prune .................................23 132 3.5.5 Prune Packet Format .............................23 133 3.6 GRAFTING ............................................23 134 3.6.1 Grafting All Sources ............................24 135 3.6.2 Sending a Graft .................................24 136 3.6.3 Receiving a Graft ...............................24 137 3.6.4 Graft Packet Format .............................26 138 3.6.5 Sending a Graft Acknowledgment ..................26 139 3.6.6 Receiving a Graft Acknowledgment ................26 140 3.6.7 Graft Acknowledgment Packet Format ..............27 141 3.7 LOOP DETECTION AND SUPPRESSION ......................27 142 3.8 INTERFACES ..........................................27 143 3.8.1 IP Tunnels ......................................27 144 3.8.2 Parameters ......................................27 145 3.8.3 Metric ..........................................27 146 3.8.4 Threshold .......................................27 147 3.8.5 Scope Control ...................................27 149 4. SECURITY CONSIDERATIONS ...............................27 151 5. REFERENCES ............................................27 153 6. AUTHOR'S ADDRESS ......................................29 155 7. APPENDIX A - INTERACTION WITH IGMP (V1 & V2) ..........29 157 8. APPENDIX B - CONSTANTS & CONFIGURABLE PARAMETERS ......29 158 9. APPENDIX C - TRACING AND TROUBLESHOOTING SUPPORT ......29 160 9.1 DVMRP ASK NEIGHBORS .................................30 161 9.2 DVMRP NEIGHBORS .....................................30 162 9.3 DVMRP ASK NEIGHBORS2 ................................30 163 9.4 DVMRP NEIGHBORS2 ....................................30 164 9.5 DVMRP INFO MESSAGE ..................................30 166 10. APPENDIX D - VERSION HISTORY .........................30 168 2. Protocol Overview 170 2.1 Neighbor Discovery 171 Neighbor DVMRP routers can be discovered dynamically by 172 sending Neighbor Probe Messages on all of the local 173 multicast capable network interfaces. These messages are 174 sent periodically to the All-DVMRP-Routers IP Multicast 175 group address. This address falls into the range of IP 176 Multicast addresses that are to remain on the locally 177 attached IP network and therefore are not forwarded by 178 multicast routers. Beginning with Version 3 of DVMRP 179 outlined in this document, each Neighbor Probe message 180 should contain the list of Neighbor DVMRP routers for which 181 Neighbor Probe messages have been received. In this way, 182 Neighbor DVMRP routers can ensure that they are seen by 183 each other. Care must be taken to interoperate with older 184 implementations of DVMRP that do not include this list of 185 neighbors. It can be assumed that older implementations of 186 DVMRP will safely ignore this list of neighbors in the 187 Probe message. Therefore, it is not necessary to send both 188 old and new types of Neighbor Probes. In addition to the 189 list of known neighbors, the Probe message should contain a 190 set of flags describing the attributes of the DVMRP router. 191 There are currently four attributes defined. 193 1. PRUNE - This router supports Pruning of multicast 194 delivery trees 195 2. GENID - This router is including a Generation 196 Identifier in the probe message that can be used to 197 detect when a neighbor wants to re-synchronize its 198 unicast routing database. 199 3. LEAF - This router considers itself a leaf router. 200 (i.e. it is not aware of any downstream multicast 201 routers.) 202 4. MTRACE - This router is capable of responding to a 203 multicast trace route request. 205 As mentioned before, DVMRP versions prior to this 206 specification may not include this set of flags and this 207 information will have to be determined by the DVMRP Major 208 and Minor version numbers. 210 2.2 Source Location 211 When an IP Multicast datagram is received by a router 212 running DVMRP, it first looks up the interface of the 213 unicast route back to the source of the datagram. This 214 interface is called the upstream interface. If the datagram 215 arrived on the correct upstream interface, then it is a 216 candidate for forwarding to one or more downstream 217 interfaces. If the datagram did not arrive on the 218 anticipated upstream interface, it is discarded. This check 219 is known as a reverse path forwarding check and must be 220 performed by all DVMRP routers. 222 In order to ensure that all DVMRP routers have a consistent 223 view of the unicast path back to a source, a unicast 224 routing table is propagated to all DVMRP routers as an 225 integral part of the protocol. Each router advertises the 226 network number and mask of the interfaces it is directly 227 connected to as well as relaying the routes received from 228 neighbor routers. DVMRP allows for an interface metric to 229 be configured on all physical and tunnel interfaces. When a 230 route is received, the metric of the upstream interface 231 over which the datagram was received must be added to the 232 metric of the route being propagated. This adjusted metric 233 should be computed before the route is compared to the 234 metric of the current next hop gateway. As is customary 235 with distance vector routing protocols, split horizon 236 should be applied to the route propagation policy in order 237 to prevent advertising a route to a destination over the 238 interface from which it was received. 240 Although there is certainly additional overhead associated 241 with propagating a separate unicast routing table, it does 242 provide two nice features. First, since all DVMRP routers 243 are using the same unicast routing protocol, there are no 244 inconsistencies between routers when determining the 245 upstream interface (aside from normal convergence issues 246 related to distance vector routing protocols). By placing 247 the burden of synchronization on the protocol as opposed to 248 the network manager, DVMRP reduces the risk of creating 249 routing loops or blackholes due to disagreement between 250 neighbor routers on the upstream interface. 252 Second, by propagating its own unicast routing table, DVMRP 253 makes it convenient to have separate paths for unicast vs. 254 multicast datagrams. Although, ideally, many network 255 managers would prefer to keep their unicast and multicast 256 traffic aligned, tunneled multicast topologies may prevent 257 this causing the unicast and multicast paths to diverge. 258 Additionally, service providers may prefer to keep the 259 unicast and multicast traffic separate for routing policy 260 reasons as they experiment with IP multicast routing and 261 begin to offer it as a service. For these benefits, DVMRP 262 has chosen to accept the additional overhead of propagating 263 unicast routes. 265 2.3 Dependent Downstream Routers 266 In addition to providing a consistent view of source 267 networks, the exchange of unicast routes in DVMRP provides 268 one other important feature. DVMRP uses the unicast route 269 exchange as a mechanism for upstream routers to determine 270 if any downstream routers depend on them for forwarding 271 from particular source networks. DVMRP accomplishes this by 272 using a well known technique called _Poison Reverse_. If a 273 downstream router selects a particular upstream router as 274 the best next hop to a particular source network, then it 275 signifies this to the upstream router by echoing back the 276 route to the upstream router with a metric equal to the 277 original metric plus infinity. When the upstream router 278 receives the report and sees a metric that lies between 279 infinity and two times infinity, it can then add the 280 downstream router from which it received the report to a 281 list of dependent routers for this source. 283 This list of dependent routers per source network built by 284 the _Poison Reverse_ technique will provide the foundation 285 necessary to determine when it is appropriate to prune back 286 the source specific IP multicast trees. 288 2.4 Building Multicast Trees 289 As previously mentioned, when an IP multicast datagram 290 arrives, the upstream interface is determined by looking up 291 the interface that would be used if a datagram was being 292 sent back to the source of the datagram. If the upstream 293 interface is correct, then a DVMRP router will forward the 294 datagram to a list of downstream interfaces. 296 2.4.1 Adding Leaf Networks 297 Initially, the DVMRP router must consider all of the 298 remaining IP multicast capable interfaces (including 299 tunnels) on the router. If the downstream interface under 300 consideration is a leaf network (has no other IP multicast 301 routers on it), then the IGMP local group database must be 302 consulted. DVMRP routers can easily determine if a directly 303 attached network is a leaf network by keeping a list of all 304 routers from which DVMRP Router Probe messages have been 305 received on the interface. Obviously, it is necessary to 306 refresh this list and age out entries received from routers 307 that are no longer being refreshed. The IGMP local group 308 database is maintained by an elected IP multicast router on 309 each physical, multicast capable network. The details of 310 the election procedure are discussed in section 3. If the 311 destination group address is listed in the local group 312 database, then the interface should be included in the list 313 of downstream interfaces. If there are no group members on 314 the interface, then the interface can be pruned from the 315 candidate list. 317 2.4.2 Adding Non-Leaf Networks 318 Initially, all non-leaf networks should be included in the 319 downstream interface list when a forwarding cache entry is 320 first being created. This allows all downstream routers to 321 be aware of traffic destined for a particular (source, 322 group) pair. The downstream routers will then have the 323 option to prune and graft this (source, group) pair to and 324 from the multicast delivery tree as requirements change 325 from their downstream routers and local group members. 327 2.5 Pruning Multicast Trees 328 As mentioned above, routers at the edges with leaf networks 329 will prune their leaf interfaces that have no group members 330 associated with an IP multicast datagram. If a router 331 prunes all of its downstream interfaces, it can notify the 332 upstream router that it no longer wants traffic destined 333 for a particular (source, group) pair. This is accomplished 334 by sending a DVMRP Prune message upstream to the router it 335 expects to forward datagrams from a particular source. 336 Recall that a downstream router will inform an upstream 337 router that it depends on the upstream router to receive 338 datagrams from particular source networks by using the 339 _Poison Reverse_ technique during the exchange of unicast 340 routes. This method allows the upstream router to build a 341 list of downstream routers on each interface that are 342 dependent upon it for datagrams from a particular source 343 network. If the upstream router receives prune messages 344 from each one of the dependent downstream routers on an 345 interface, then the upstream router can in turn prune this 346 interface from its downstream interface list. If the 347 upstream router is able to prune all of its downstream 348 interfaces in this way, it can then send a DVMRP Prune 349 message to its upstream router. This continues until the 350 minimum tree necessary to reach all of the receivers 351 remains. Since IP multicast routers may be restarted at any 352 time and lose state information about existing prunes, it 353 is necessary to limit the life of a prune and periodically 354 resume the flooding procedure. This will reinitiate the 355 prune mechanism and the cycle will continue. When a router 356 decides to prune one of its downstream interfaces, it will 357 set a timer to indicate the lifetime of the prune. If all 358 of its downstream interfaces become pruned off the 359 multicast delivery tree and a DVMRP Prune message is sent 360 upstream, the lifetime of the prune will be equal to the 361 minimum of the remaining lifetimes of the pruned 362 interfaces. 364 2.6 Grafting Multicast Trees 365 Once a tree branch has been pruned from a multicast 366 delivery tree, packets from the pruned (source, group) pair 367 will no longer be forwarded. There are two different ways 368 for packets from the (source, group) pair to be forwarded 369 again. First, since IP multicast supports dynamic group 370 membership, new hosts may join the multicast group. In this 371 case, DVMRP routers will need a mechanism to undo the 372 prunes that are in place from the host back to the first 373 branch that was pruned from the multicast tree. This is 374 accomplished with a DVMRP Graft message. A router will send 375 a Graft message to its upstream neighbor if a group join 376 occurs for a group that currently has pruned sources. 377 Separate Graft messages must be sent to the appropriate 378 upstream neighbor for each source that has been pruned. 379 Since there would be no way to tell if a Graft message sent 380 upstream was lost or the source simply quit sending 381 traffic, it is necessary to acknowledge each Graft message 382 with a DVMRP Graft Ack message. If an acknowledgment is not 383 received within a Graft Time-out period, the Graft message 384 should be retransmitted. Duplicate Graft Ack messages 385 should simply be ignored. Second, if the prune interval 386 expires, the negative cache entries are removed and the 387 packets will automatically be forwarded again. This is a 388 necessary feature since routers may be restarted and lose 389 all prune state information or new routers may appear. 390 Since these routers will not have prune state associated 391 with the (source, group) pair, they will not realize that a 392 DVMRP Graft message is necessary if a new host joins the 393 group. Therefore, by periodically timing out the prunes and 394 re-flooding the traffic, any new or restarted routers can 395 have their prune state periodically refreshed. 397 2.7 Suppressing Duplicate Packets 399 3. Detailed Protocol Operation 400 This section contains a detailed description of DVMRP. It 401 covers sending and receiving of DVMRP messages as well as 402 the generation and maintenance of IP Multicast forwarding 403 cache entries. 405 3.1 Protocol Header 406 DVMRP packets are encapsulated in IP datagrams, with an IP 407 protocol number of 2 (IGMP) as specified in the Assigned 408 Numbers RFC. All DVMRP packets use a common protocol 409 header that specifies the IGMP Packet Type as hexadecimal 410 0x13 (DVMRP). A diagram of the common protocol header 411 follows: 413 Table 1 - Common Protocol Header 415 0 8 16 31 416 +--------------------------------------+ 417 | | | | 418 | Type | Code | Checksum | 419 | (0x13) | | | 420 +--------------------------------------+ 422 The value of the Code field determines the DVMRP packet 423 type. Currently, there are codes allocated for DVMRP 424 protocol message types as well as protocol analysis and 425 troubleshooting packets. The protocol message Codes are: 427 Table 2 - Standard Protocol Packet Types 429 Code Packet Type Description 430 ------------------------------------------- 432 1 DVMRP Probe for neighbor discovery 434 2 DVMRP Report for unicast route 435 exchange 437 7 DVMRP Prune for pruning multicast 438 delivery trees 440 8 DVMRP Graft for grafting multicast 441 delivery trees 443 9 DVMRP Graft for acknowledging 444 Ack graft messages 446 ------------------------------------------- 448 There are additional codes used for protocol analysis and 449 troubleshooting. These codes are discussed in Appendix B. 450 The Checksum is the 16-bit one's complement of the one's 451 complement sum of the DVMRP message. The checksum of the 452 DVMRP message should be calculated with the checksum field 453 set to zero. 455 3.2 DVMRP Probe Messages 456 When a DVMRP router is configured to run on an physical 457 interface, it sends local IP Multicast discovery packets to 458 inform other DVMRP routers that it is operational. These 459 discovery packets are called DVMRP Probes and they serve 460 three purposes. 462 1. Probes provide a mechanism for DVMRP routers to locate 463 each other. The existence of other routers is used for 464 network leaf detection and the list of addresses of 465 the other routers are used in designated router 466 election. In addition, this list of DVMRP neighbors 467 provides a foundation for neighbor prune lists. 468 2. They provide a way for DVMRP routers to determine the 469 capabilities of each other. This may be deduced from 470 the major and minor version numbers in the Probe 471 packet or directly from the capability flags. Examples 472 of these capabilities are whether Generation IDs are 473 used, if the neighbor supports pruning, if the 474 neighbor is a leaf router, and whether the neighbor 475 supports the multicast trace route function. 476 3. Probes provide a keep-alive function in order to 477 quickly detect neighbor loss. DVMRP probes sent on 478 each multicast capable interface configured for DVMRP 479 SHOULD have an interval of 10 seconds. The neighbor 480 time-out interval SHOULD be set at 140 seconds. This 481 allows fairly early detection of a lost neighbor yet 482 provides tolerance for busy multicast routers. These 483 values MUST be coordinated between all DVMRP routers 484 on a physical network segment. 486 3.2.1 Router Capabilities 487 In the past, there have been many versions of DVMRP in use 488 with a wide range of capabilities. Practical considerations 489 require a current implementation to interoperate with these 490 older implementations that don't formally specify their 491 capabilities. For instance, for major versions less than 3, 492 it can be assumed that the neighbor does not support 493 pruning. The formal capability flags were first introduced 494 in version 3.5 in an attempt to take the guess work out 495 which features are supported by a neighbor. A complete 496 version history is summarized in Appendix A to assist with 497 backward compatibility. A DVMRP router MUST specify its 498 capabilities in a Probe message. The following capabilities 499 are currently defined: 501 Table 3 - Probe Capability Flags 503 15 8 7 0 504 +--------------------------------------+ 505 | | | 506 | Reserved | M G P L| 507 | | | 508 +--------------------------------------+ 510 LEAF - The LEAF bit is set if the router does not 511 have any downstream DVMRP neighbor routers. 513 PRUNE - router is capable of handling prunes 515 GENID - router keeps a non-decreasing generation id 516 for synchronization on restart. 518 MTRACE - router includes multicast trace route 519 support 521 3.2.2 Generation ID 522 If a DVMRP router is restarted, it must immediately 523 exchange unicast routing tables with all of its neighbors. 524 If a neighbor doesn't automatically detect that the 525 neighbor has restarted, then it will not send its entire 526 routing table immediately. Instead, it will spread the 527 updates over an entire routing update interval. In order 528 for the neighbor to detect a router that is restarted, a 529 non-decreasing number is placed in the periodic probe 530 message called the generation ID. If a router detects an 531 increase in the generation ID of a neighbor, it should 532 exchange its entire unicast routing table with the 533 neighbor. A time of day clock provides a good source for a 534 non-decreasing 32 bit integer. 536 3.2.3 Neighbor Addresses 537 As a DVMRP router sees Probe messages from its DVMRP 538 neighbors, it records the neighbor addresses on each 539 interface and places them in the Probe message sent on the 540 particular interface. This allows the neighbor router to 541 know that its probes have been received by the sending 542 router. 544 3.2.4 Probe Packet Format 545 The Probe packet is variable in length depending on the 546 number of neighbor IP addresses included. The current Major 547 Version is 3. To maintain compatibility with previous 548 versions, implementations of Version 3 must include pruning 549 and grafting of multicast trees. Non-pruning 550 implementations are HIGHLY discouraged at this time. 552 Table 4 - DVMRP Probe Packet Format 554 0 8 16 24 555 +-------------------+--------+---------+ 556 | | | | 557 | Capabilities | Minor | Major | 558 | |Version | Version | 559 +-------------------+--------+---------+ 560 | | 561 | Generation ID | 562 +--------------------------------------+ 563 | | 564 | Neighbor IP Address 1 | 565 +--------------------------------------+ 566 | | 567 | Neighbor IP Address 2 | 568 +--------------------------------------+ 569 | | 570 | ... | 571 +--------------------------------------+ 572 | | 573 | Neighbor IP Address N | 574 +--------------------------------------+ 576 3.2.5 Designated Router Election 577 Since it is wasteful to have more than a single router 578 sending IGMP Host Membership Queries on a given physical 579 network, DVMRP provides a method to elect a single router 580 on each physical network as the Designated Querier. Based 581 on the list of neighbors from which DVMRP Probe messages 582 were received, a router will pick the router with the 583 lowest IP address as the designated querier. The router 584 must be sure and include itself in this list of candidates. 586 3.3 Building Forwarding Cache Entries 587 In order to create optimal multicast delivery trees, IP 588 Multicast was designed to keep separate forwarding cache 589 entries for each (source network, destination group) pair. 590 Because the possible combinations of these is quite large, 591 forwarding cache entries are generated on demand as data 592 arrives at a multicast router. Since the IP forwarding 593 decision is made on a hop by hop basis (as with the unicast 594 case), it is imperative that each multicast router has a 595 consistent view of the reverse path back to the source 596 network. For this reason, DVMRP includes its own unicast 597 routing protocol. 599 3.3.1 Determining the upstream interface 600 When a multicast packet arrives, a DVMRP router will use 601 the internal DVMRP unicast routing table to determine which 602 interface leads back to the source. If the packet did not 603 arrive on that interface, it should be discarded without 604 further processing. Each multicast forwarding entry should 605 cache the upstream interface for a particular source host 606 or source network after looking this up in the DVMRP 607 unicast routing table. 609 3.3.2 Determining the downstream interface list 610 The downstream interface list is built from the remaining 611 list of multicast capable interfaces. Any interfaces 612 designated as leaf networks and do not have members of the 613 particular multicast group can be automatically pruned from 614 list of downstream interfaces. The remaining interfaces 615 will either have downstream DVMRP routers or directly 616 attached group members. These interfaces may be pruned in 617 the future if it is determined that there are no group 618 members anywhere along the entire tree branch. 620 3.4 Unicast Route Exchange 621 It was mentioned earlier that since not all IP routers 622 support IP multicast forwarding, it is necessary to tunnel 623 IP multicast datagrams through these routers. One effect of 624 using these encapsulated tunnels is that IP multicast 625 traffic may not be aligned with IP unicast traffic. This 626 means that a multicast datagram from a particular source 627 can arrive on a different interface than the upstream 628 interface back to the unicast source of the multicast 629 datagram. 631 Therefore, when determining the reverse path back to a 632 particular source it is not always possible to use the 633 standard unicast routing table. DVMRP's solution to this 634 problem is to create its own routing table of unicast 635 routes for determining upstream routers for each source. 636 This routing information is used exclusively for 637 determining the reverse path back to source of multicast 638 traffic. Tunnels are considered to be distinct interfaces 639 and route reports are sent unicast between tunnel endpoints 640 as though they arrived on the tunnel pseudo interface. The 641 routing information that is propagated by DVMRP contains a 642 list of unicast source networks and an appropriate metric. 643 The metric used is a hop count which is incremented by the 644 cost of the outgoing interface. Traditionally, physical 645 interfaces use a metric of 1 while the metric of a tunnel 646 interface varies with the distance and bandwidth in the 647 path between the two tunnel endpoints. Users are encouraged 648 to configure tunnels with the same metric in each direction 649 in order to prevent routing loops although the protocol 650 does not strictly enforce this. 652 3.4.1 Route Packing and Ordering 653 Since DVMRP Route Reports may need to refresh several 654 thousand routes each Report interval, routers MUST attempt 655 to spread the routes reported across the whole route update 656 interval. This reduces the chance of synchronized route 657 reports causing routers to become overwhelmed for a few 658 seconds each report interval. Since the route report 659 interval is 60 seconds, it is suggested that the total 660 number routes being updated be split across multiple Route 661 Reports sent at regular intervals. One implementation 662 splits all unicast routes across 6 Report periods sent at 663 10 seconds intervals. Due to limitations of older 664 implementations of DVMRP, Route Reports should contain 665 source network/mask pairs sorted first by increasing 666 network mask and then by increasing source network within 667 each possible mask value. 669 In order to pack more source networks into a route report, 670 source networks are often represented by less than 4 671 octets. The number of significant bytes in the mask value 672 is used to determine the number of octets used to represent 673 each source network within that particular mask value. For 674 instance if the mask value of 255.255.0.0 is being 675 reported, the source networks would only contain 2 octets 676 each. DVMRP assumes that source networks will never be 677 aggregated into networks whose prefix length is less than 678 8. Therefore, it does not carry the first octet of the mask 679 in the Route Report since, given this assumption, the first 680 octet will always be 0xFF. This means that the netmask 681 value will always be represented in 3 octets. 683 Immediately following each source network is an octet 684 containing the metric advertised to reach the source 685 network. 687 3.4.2 Unicast Route Metrics 688 For each source network reported, a route metric is also 689 contained in the route report. The metric is the sum of the 690 outgoing interface metrics between the router originating 691 the report and the source network. The Infinity metric is 692 defined to be 32. This limits the breadth across the whole 693 DVMRP network and is necessary to place an upper bound on 694 the convergence time of the protocol. 696 As seen in the packet format below, Route Reports do not 697 contain a count of the number of routes reported for each 698 netmask. Instead, the high order bit of the metric is used 699 to signify the last route being reported for a particular 700 mask value. If a metric is read with the high order bit of 701 the 8-bit value set, then if the end of the message has not 702 been reached, the next value will be a new netmask to be 703 applied to the subsequent list of routes. This technique is 704 used to prevent wasting space in the Route Report message 705 for a count of unicast source networks for each netmask 706 value contained in the Report. 708 3.4.3 Unicast Route Dependencies 709 In order for pruning to work correctly, each DVMRP router 710 needs to know which downstream routers depend on it for 711 receiving datagrams from particular source networks. 712 Initially, when a new datagram arrives from a particular 713 source/group pair, it is flooded to all downstream 714 interfaces that have DVMRP neighbors who have indicated a 715 dependency on the receiving DVMRP router for that 716 particular source. A downstream interface can only be 717 pruned when it has received Prune messages from each of the 718 dependent routers on that interface. Each downstream router 719 uses a method called Poison Reverse to indicate to the 720 upstream router which source networks it expects to receive 721 from the upstream router. The downstream router indicates 722 this by echoing back the source networks it expects to 723 receive from the upstream router with infinity added to the 724 advertised metric. This means that the legal values for the 725 metric now become between 1 and 2*Infinity -1 or 1 and 63. 726 Values between 1 and 31 indicate reachable unicast source 727 networks. The value of Infinity or 32 indicates the source 728 network is not reachable. Values between 33 and 63 indicate 729 that the downstream router originating the Report is 730 depending upon the upstream router to provide multicast 731 datagrams from the corresponding source network. 733 3.4.4 Sending Route Reports 734 Full Route Reports MUST be sent out every Route Report 735 Interval. In addition, flash updates CAN be sent between 736 full route reports. Flash updates can reduce the chances of 737 routing loops and black holes occurring when source 738 networks become unreachable through a particular path. 739 Flash updates need only contain the source networks that 740 have changed. It is not necessary to report all of the 741 source networks from a particular mask value when sending 742 an update. 744 3.4.5 Receiving Route Reports 746 3.4.6 Route Report Packet Format 747 The format of a sample Route Report Packet is shown in 748 below. The packet shown is an example of how the source 749 networks are packed into a Report. The number of octets in 750 each Source Network will vary depending on the mask value. 751 The values below are only an example for clarity and are 752 not intended to represent the format of every Route Report. 754 Table 5 - Route Report Packet Format 756 0 8 16 31 757 +--------+---------+---------+---------+ 758 | | | | | 759 | Mask | Mask | Mask | Src | 760 |Octet 2 | Octet 3 | Octet 4 | Net11 | 761 +--------+---------+---------+---------+ 762 |Src Net11 (cont.) | Metric Src | 763 | ... | Net12 | 764 +------------------+-------------------+ 765 |Src Net12 (cont.) | Metric + Mask | 766 | ... | 0x80 Octet 2 | 767 +------------------+-------------------+ 768 | Mask Mask | Src Net21 | 769 |Octet 3 Octet 4 | | 770 +------------------+-------------------+ 771 |Src Net21 (cont.) | Metric + Mask | 772 | ... | 0x80 Octet 2 | 773 +------------------+-------------------+ 774 | Mask Mask | ... | 775 |Octet 3 Octet 4 | | 776 +------------------+-------------------+ 778 3.5 Pruning 779 DVMRP is described as a flood and prune multicast routing 780 protocol since datagrams are initially sent out all 781 dependent downstream interfaces and then pruned back to 782 only the downstream interfaces that are on a reverse 783 shortest path to a receiver. Prunes are data driven and are 784 sent in response to receiving unwanted multicast traffic at 785 the leafs of the multicast tree rooted at a particular 786 source network. 788 3.5.1 Leaf Networks 789 Detection of leaf networks is very important to the pruning 790 process. Routers at the end of a source specific multicast 791 delivery tree must detect that there are no further 792 downstream routers. This detection mechanism is covered 793 above in section 3.2 titled DVMRP Probe Messages. If there 794 are no group members present for a particular multicast 795 datagram received, the leaf routers will start the pruning 796 process by pruning their downstream interfaces and sending 797 a prune to the upstream router for that source. 799 3.5.2 Source Networks 800 It is important to remember that because prunes are based 801 on group membership, a prune sent upstream for a particular 802 source applies to all sources on the source network. It is 803 not possible to prune only one or a subset of hosts on a 804 source network for a particular group. All or none of the 805 sources on a source network sending to a particular group 806 must be pruned. 808 3.5.3 Receiving a Prune 809 When a prune is received, the following steps should be 810 taken: 811 1. Determine if a Probe has been received from this 812 router recently. 813 2. If not, discard prune since there is no prior state 814 about this neighbor. 815 3. If so, make sure the neighbor advertises it is capable 816 of pruning. 817 4. Ensure the packet meets the minimum length requirement 818 for a prune. 819 5. Extract the source address, group address, and prune 820 time-out values 821 6. If no state exists for the (source, group) pair, then 822 ignore the prune. 823 7. Verify that the prune was received from a dependent 824 neighbor for the source network. If not, discard the 825 prune. 826 8. Determine if a prune is currently active for this 827 (source, group) pair. 828 9. If so, reset the timer to the new time-out value. 829 Otherwise, create state for the new prune and set a 830 timer for the prune lifetime. 831 10. Determine if all dependent downstream routers have now 832 sent prunes. 833 11. If so, a prune should be sent upstream. 835 3.5.4 Sending a Prune 836 When sending a prune upstream, the following steps should 837 be taken: 838 1. Decide if upstream neighbor is capable of receiving 839 prunes. 840 2. If not, then proceed no further. 841 3. Stop any pending Grafts awaiting acknowledgments. 842 4. Determine the prune lifetime. This value should be the 843 minimum of the prune lifetimes remaining from the 844 downstream neighbors and the cache lifetime of the 845 (source, group) pair. 846 5. Form and transmit the packet to the upstream neighbor 847 for the source. 849 3.5.5 Prune Packet Format 850 In addition to the standard IGMP and DVMRP headers, a Prune 851 Packet contains three additional fields: the source host IP 852 address, the destination group IP address, and the Prune 853 Lifetime in seconds. 855 Table 6 - Prune Packet Format 857 0 31 858 +--------------------------------------+ 859 | | 860 | Source Address | 861 +--------------------------------------+ 862 | | 863 | Group Address | 864 +--------------------------------------+ 865 | | 866 | Prune Lifetime | 867 +--------------------------------------+ 869 3.6 Grafting 870 Once a multicast delivery tree has been pruned back, DVMRP 871 Graft messages are necessary to join new receivers onto the 872 multicast tree. Graft messages are sent upstream from the 873 new receivers first-hop router until a point on the 874 multicast tree is reached. Graft messages are re-originated 875 between adjacent DVMRP routers and are not forwarded by 876 DVMRP routers. Therefore, the first-hop router does not 877 know if the Graft message ever reaches the multicast tree. 878 To remedy this, each Graft message is acknowledged hop by 879 hop. This ensures that the Graft message is not lost 880 somewhere along the path between the receiver's first-hop 881 router and the closest point on the multicast delivery 882 tree. 884 3.6.1 Grafting All Sources 885 It is important to realize that prunes are source specific 886 and are sent up different trees for each source. Grafts are 887 sent in response to a new Group Member which is not source 888 specific. Therefore, separate Graft messages must be sent 889 to the appropriate upstream routers to counteract each 890 previous source specific prune that was sent. 892 3.6.2 Sending a Graft 893 As mentioned above, a Graft message sent to the upstream 894 DVMRP router should be acknowledged hop by hop guaranteeing 895 end-to-end delivery. If a Graft Acknowledgment is not 896 received within a Graft Retransmission Time-out period, the 897 Graft should be resent to the upstream router. The time-out 898 period is fixed at 5 seconds. 899 In order to send a Graft message, the following steps 900 should be taken: 901 1. Verify a forwarding cache entry exists for the 902 (source, group) pair and that a prune exists for the 903 cache entry. 904 2. Verify that the upstream router is capable of 905 receiving prunes (and therefore grafts). 906 3. Add the graft to the retransmission timer list 907 awaiting an acknowledgment. 908 4. Formulate and transmit the Graft packet. 910 3.6.3 Receiving a Graft 911 The actions taken when a Graft is received depends on the 912 state in the receiving router for the (source, group) pair 913 in the received Graft message. If the receiving router has 914 prune state for the (source, group) pair, then it must 915 acknowledge the received graft and send a subsequent graft 916 to its upstream router. 918 If the receiving router has some pruned downstream 919 interfaces but has not sent a prune upstream, then the 920 receiving interface can simply be added to the list of 921 downstream interfaces in the forwarding cache. A Graft 922 Acknowledgment must also be sent back to the source of the 923 Graft message. 924 If the receiving router has no state at all for the 925 (source, group) pair, then datagrams arriving for the 926 (source, group) pair should automatically be flooded when 927 they arrive. A Graft Acknowledgment must be sent to the 928 source of the Graft message. 929 If a Graft message is received from an unknown neighbor, it 930 should be discarded. 932 3.6.4 Graft Packet Format 933 The format of a Graft packet is show below: 935 Table 7 - Graft Packet Format 937 0 31 938 +--------------------------------------+ 939 | | 940 | Source Address | 941 +--------------------------------------+ 942 | | 943 | Group Address | 944 +--------------------------------------+ 946 3.6.5 Sending a Graft Acknowledgment 947 A Graft Acknowledgment packet is sent to a downstream 948 neighbor in response to receiving a Graft message. Grafts 949 received from unknown neighbors should be discarded but all 950 other correctly formatted Graft messages should be 951 acknowledged. This is true even if no other action is taken 952 in response to receiving the Graft to prevent the source 953 from continually re-transmitting the Graft message. 954 The Graft Acknowledgment packet is identical to the Graft 955 packet except that the DVMRP code in the common header is 956 set to Graft Ack. This allows the receiver of the Graft Ack 957 message to correctly identify which Graft was acknowledged 958 and stop the appropriate retransmission timer. 960 3.6.6 Receiving a Graft Acknowledgment 961 When a Graft Acknowledgment is received, the (source, 962 group) pair in the packet can be used to determine if a 963 Graft was sent to this particular upstream router. If no 964 Graft was sent, the Graft Ack can simply be ignored. 965 If a Graft was sent, and the acknowledgment has come from 966 the correct upstream router, then it has been successfully 967 received and the retransmission timer for the Graft can be 968 stopped. 970 3.6.7 Graft Acknowledgment Packet Format 971 The format of a Graft Ack packet (which is identical to 972 that of a Graft packet is show below: 974 Table 8 - Graft Ack Packet Format 976 0 31 977 +--------------------------------------+ 978 | | 979 | Source Address 980 +--------------------------------------+ 981 | | 982 | Group Address 983 +--------------------------------------+ 985 3.7 Loop Detection and Suppression 987 3.8 Interfaces 989 3.8.1 IP Tunnels 991 3.8.2 Parameters 993 3.8.3 Metric 995 3.8.4 Threshold 997 3.8.5 Scope Control 999 4. Security Considerations 1000 Security considerations will be discussed in an upcoming 1001 revision of this document. 1003 5. References 1004 [1]. Deering, S., Cheriton, D., "Multicast Routing in 1005 Datagram Internetworks and Extended LANs", ACM 1006 Transactions on Computer Systems, Vol. 8, No. 2, May 1007 1990, Pages 85-110. 1008 [2]. Waitzman, D., Partridge, C., Deering, S., "Distance 1009 Vector Multicast Routing Protocol", RFC 1075, 1010 Internet Architecture Board, November 1988. 1012 [3]. Deering, S., "Host Extensions for IP Multicasting", 1013 RFC 1112, Internet Architecture Board, August 1989. 1014 [4]. Deering, S., "Host Extensions for IP Multicasting - 1015 Appendix 1 (IGMP)", RFC 1112, Internet Architecture 1016 Board, August 1989. 1018 6. Author's Address 1020 Thomas Pusateri 1021 NetEdge Systems, Inc. 1022 PO Box 14993 1023 Research Triangle Park, NC 27709 1025 Phone: 919-991-9028 1026 Fax: 919-991-9060 1027 EMail: pusateri@NetEdge.COM 1029 7. Appendix A - Interaction with IGMP (V1 & V2) 1031 8. Appendix B - Constants & Configurable Parameters 1033 9. Appendix C - Tracing and Troubleshooting support 1035 Table 9 - Tracing and Debugging Packet Types 1037 Code Packet Type Description 1038 --------------------------------------------- 1040 3 DVMRP Ask Obsolete 1041 Neighbors 1043 4 DVMRP Neighbors Obsolete 1045 5 DVMRP Ask Request Neighbor List 1046 Neighbors 2 1048 6 DVMRP Neighbors 2 Respond with Neighbor 1049 List 1051 13 DVMRP Info General Information 1052 Request/Reply 1053 --------------------------------------------- 1055 9.1 DVMRP Ask Neighbors 1057 9.2 DVMRP Neighbors 1059 9.3 DVMRP Ask Neighbors2 1061 9.4 DVMRP Neighbors2 1063 9.5 DVMRP Info message 1065 10. Appendix D - Version History