idnits 2.17.1 draft-ietf-idmr-traceroute-ipm-03.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-26) 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. ** The document is more than 15 pages and seems to lack a Table of Contents. == 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 separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 8 instances of too long lines in the document, the longest one being 6 characters in excess of 72. ** The abstract seems to contain references ([Bradner97]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. == There are 3 instances of lines with non-RFC2606-compliant FQDNs in the document. == There are 2 instances of lines with multicast IPv4 addresses in the document. If these are generic example addresses, they should be changed to use the 233.252.0.x range defined in RFC 5771 Miscellaneous warnings: ---------------------------------------------------------------------------- -- 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 (December 1998) is 9264 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) -- Missing reference section? 'Bradner97' on line 51 looks like a reference -- Missing reference section? 'Brad88' on line 155 looks like a reference -- Missing reference section? 'Katz97' on line 612 looks like a reference -- Missing reference section? 'Pusa98' on line 685 looks like a reference -- Missing reference section? 'Thal98a' on line 685 looks like a reference -- Missing reference section? 'Thal98b' on line 685 looks like a reference Summary: 10 errors (**), 0 flaws (~~), 3 warnings (==), 8 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Internet Engineering Task Force Inter-Domain Multicast Routing Working Group 2 INTERNET-DRAFT W. Fenner 3 draft-ietf-idmr-traceroute-ipm-03.txt Xerox PARC 4 S. Casner 5 Precept Software 6 August 5, 1998 7 Expires December 1998 9 A "traceroute" facility for IP Multicast. 11 Status of this Memo 13 This document is an Internet-Draft. Internet-Drafts are working docu- 14 ments of the Internet Engineering Task Force (IETF), its areas, and its 15 working groups. Note that other groups may also distribute working doc- 16 uments as Internet-Drafts. 18 Internet-Drafts are draft documents valid for a maximum of six months 19 and may be updated, replaced, or obsoleted by other documents at any 20 time. It is inappropriate to use Internet- Drafts as reference material 21 or to cite them other than as "work in progress." 23 To view the entire list of current Internet-Drafts, please check the 24 "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow 25 Directories on ftp.is.co.za (Africa), ftp.nordu.net (Northern Europe), 26 ftp.nis.garr.it (Southern Europe), munnari.oz.au (Pacific Rim), 27 ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast). 29 Distribution of this document is unlimited. 31 Abstract 33 This draft describes the IGMP multicast traceroute facility. As 34 the deployment of IP multicast has spread, it has become clear that 35 a method for tracing the route that a multicast IP packet takes 36 from a source to a particular receiver is absolutely required. 37 Unlike unicast traceroute, multicast traceroute requires a special 38 packet type and implementation on the part of routers. This speci- 39 fication describes the required functionality. 41 This document is a product of the Inter-Domain Multicast Routing working 42 group within the Internet Engineering Task Force. Comments are 43 solicited and should be addressed to the working group's mailing list at 44 idmr@cs.ucl.ac.uk and/or the author(s). 46 Key Words 48 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 49 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 50 document are to be interpreted as described in RFC 2119 [Bradner97]. 52 1. Introduction 54 The unicast "traceroute" program allows the tracing of a path from one 55 machine to another, using a mechanism that already existed in IP. 56 Unfortunately, no such existing mechanism can be applied to IP multicast 57 paths. The key mechanism for unicast traceroute is the ICMP TTL 58 exceeded message, which is specifically precluded as a response to mul- 59 ticast packets. Thus, we specify the multicast "traceroute" facility to 60 be implemented in multicast routers and accessed by diagnostic programs. 61 While it is a disadvantage that a new mechanism is required, the multi- 62 cast traceroute facility can provide additional information about packet 63 rates and losses that the unicast traceroute cannot, and generally 64 requires fewer packets to be sent. 66 Goals: 68 o To be able to trace the path that a packet would take from some 69 source to some destination. 71 o To be able to isolate packet loss problems (e.g., congestion). 73 o To be able to isolate configuration problems (e.g., TTL threshold). 75 o To minimize packets sent (e.g. no flooding, no implosion). 77 2. Overview 79 Given a multicast distribution tree, tracing from a source to a multi- 80 cast destination is hard, since you don't know down which branch of the 81 multicast tree the destination lies. This means that you have to flood 82 the whole tree to find the path from one source to one destination. 83 However, walking up the tree from destination to source is easy, as most 84 existing multicast routing protocols know the previous hop for each 85 source. Tracing from destination to source can involve only routers on 86 the direct path. 88 The party requesting the traceroute (which need be neither the source 89 nor the destination) sends a traceroute Query packet to the last-hop 90 multicast router for the given destination. The last-hop router turns 91 the Query into a Request packet by adding a response data block contain- 92 ing its interface addresses and packet statistics, and then forwards the 93 Request packet via unicast to the router that it believes is the proper 94 previous hop for the given source and group. Each hop adds its response 95 data to the end of the Request packet, then unicast forwards it to the 96 previous hop. The first hop router (the router that believes that pack- 97 ets from the source originate on one of its directly connected networks) 98 changes the packet type to indicate a Response packet and sends the com- 99 pleted response to the response destination address. The response may 100 be returned before reaching the first hop router if a fatal error condi- 101 tion such as "no route" is encountered along the path. 103 Multicast traceroute uses any information available to it in the router 104 to attempt to determine a previous hop to forward the trace towards. 105 Multicast routing protocols vary in the type and amount of state they 106 keep; multicast traceroute endeavors to work with all of them by using 107 whatever is available. For example, if a DVMRP router has no active 108 state for a particular source but does have a DVMRP route, it chooses 109 the parent of the DVMRP route as the previous hop. If a PIM-SM router 110 is on the (*,G) tree, it chooses the parent towards the RP as the previ- 111 ous hop. In these cases, no source/group-specific state is available, 112 but the path may still be traced. 114 3. Multicast Traceroute header 116 The header for all multicast traceroute packets is as follows: 118 0 1 2 3 119 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 120 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 121 | IGMP Type | # hops | checksum | 122 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 123 | Multicast Group Address | 124 +=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ 125 | Source Address | 126 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 127 | Destination Address | 128 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 129 | Response Address | 130 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 131 | resp ttl | Query ID | 132 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 134 3.1. IGMP Type: 8 bits 136 The IGMP type field is defined to be 0x1F for traceroute queries 137 and requests. The IGMP type field is changed to 0x1E when the 138 packet is completed and sent as a response from the first hop 139 router to the querier. Two codes are required so that multicast 140 routers won't attempt to process a completed response in those 141 cases where the initial query was issued from a router or the 142 response is sent via multicast. 144 3.2. # hops: 8 bits 146 This field specifies the maximum number of hops that the requester 147 wants to trace. If there is some error condition in the middle of 148 the path that keeps the traceroute request from reaching the first- 149 hop router, this field can be used to perform an expanding-length 150 search to trace the path to just before the problem. 152 3.3. Checksum: 16 bits 154 The checksum is the 16-bit one's complement of the one's complement 155 sum of the whole IGMP message (the entire IP payload)[Brad88]. 156 When computing the checksum, the checksum field is set to zero. 157 When transmitting packets, the checksum MUST be computed and 158 inserted into this field. When receiving packets, the checksum 159 MUST be verified before processing a packet. 161 3.4. Group address 163 This field specifies the group address to be traced, or zero if no 164 group-specific information is desired. Note that non-group-spe- 165 cific traceroutes may not be possible with certain multicast rout- 166 ing protocols. 168 3.5. Source address 170 This field specifies the IP address of the multicast source for the 171 path being traced, or 0xFFFFFFFF if no source-specific information 172 is desired. Note that non-source-specific traceroutes may not be 173 possible with certain multicast routing protocols. 175 3.6. Destination address 177 This field specifies the IP address of the multicast receiver for 178 the path being traced. The trace starts at this destination and 179 proceeds toward the traffic source. 181 3.7. Response Address 183 This field specifies where the completed traceroute response packet 184 gets sent. It can be a unicast address or a multicast address, as 185 explained in section 6.2. 187 3.8. resp ttl: 8 bits 189 This field specifies the TTL at which to multicast the response, if 190 the response address is a multicast address. 192 3.9. Query ID: 24 bits 194 This field is used as a unique identifier for this traceroute 195 request so that duplicate or delayed responses may be detected and 196 to minimize collisions when a multicast response address is used. 198 4. Definitions 200 Since multicast traceroutes flow in the opposite direction to the data 201 flow, we always refer to "upstream" and "downstream" with respect to 202 data, unless explicitly specified. 204 Incoming Interface 205 The interface on which traffic is expected from the specified 206 source and group. 208 Outgoing Interface 209 The interface on which traffic is forwarded from the specified 210 source and group towards the destination. Also called the "Recep- 211 tion Interface", since it is the interface on which the multicast 212 traceroute Request was received. 214 Previous-Hop Router 215 The router, on the Incoming Interface, which is responsible for 216 forwarding traffic for the specified source and group. 218 5. Response data 220 Each router adds a "response data" segment to the traceroute packet 221 before it forwards it on. The response data looks like this: 223 0 1 2 3 224 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 225 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 226 | Query Arrival Time | 227 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 228 | Incoming Interface Address | 229 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 230 | Outgoing Interface Address | 231 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 232 | Previous-Hop Router Address | 233 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 234 | Input packet count on incoming interface | 235 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 236 | Output packet count on outgoing interface | 237 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 238 | Total number of packets for this source-group pair | 239 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 240 | | |M| | | | 241 | Rtg Protocol | FwdTTL |B|S| Src Mask |Forwarding Code| 242 | | |Z| | | | 243 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 245 5.1. Query Arrival Time 247 The Query Arrival Time is a 32-bit NTP timestamp specifying the 248 arrival time of the traceroute request packet at this router. The 249 32-bit form of an NTP timestamp consists of the middle 32 bits of 250 the full 64-bit form; that is, the low 16 bits of the integer part 251 and the high 16 bits of the fractional part. 253 The following formula converts from a UNIX timeval to a 32-bit NTP 254 timestamp: 256 query_arrival_time = (tv.tv_sec + 32384) << 16 + ((tv.tv_usec << 257 10) / 15625) 259 The constant 32384 is the number of seconds from Jan 1, 1900 to Jan 260 1, 1970 truncated to 16 bits. ((tv.tv_usec << 10) / 15625) is a 261 reduction of ((tv.tv_usec / 100000000) << 16). 263 5.2. Incoming Interface Address 265 This field specifies the address of the interface on which packets 266 from this source and group are expected to arrive, or 0 if unknown. 268 5.3. Outgoing Interface Address 270 This field specifies the address of the interface on which packets 271 from this source and group flow to the specified destination, or 0 272 if unknown. 274 5.4. Previous-Hop Router Address 276 This field specifies the router from which this router expects 277 packets from this source. This may be a multicast group if the 278 previous hop is not known because of the workings of the multicast 279 routing protocol. However, it should be 0 if the incoming inter- 280 face address is unknown. 282 5.5. Input packet count on incoming interface 284 This field contains the number of multicast packets received for 285 all groups and sources on the incoming interface, or 0xffffffff if 286 no count can be reported. 288 5.6. Output packet count on outgoing interface 290 This field contains the number of multicast packets that have been 291 transmitted for all groups and sources on the outgoing interface, 292 or 0xffffffff if no count can be reported. 294 5.7. Total number of packets for this source-group pair 296 This field counts the number of packets from the specified source 297 forwarded by this router to the specified group, or 0xffffffff if 298 no count can be reported. If the S bit is set, the count is for 299 the source network, as specified by the Src Mask field. If the S 300 bit is set and the Src Mask field is 63, indicating no source-spe- 301 cific state, the count is for all sources sending to this group. 303 5.8. Rtg Protocol: 8 bits 305 This field describes the routing protocol in use between this 306 router and the previous-hop router. Specified values include: 308 1 DVMRP 309 2 MOSPF 310 3 PIM 311 4 CBT 312 5 PIM using special routing table 313 6 PIM using a static route 314 7 DVMRP using a static route 316 5.9. FwdTTL: 8 bits 318 This field contains the TTL that a packet is required to have 319 before it will be forwarded over the outgoing interface. 321 5.10. MBZ: 1 bit 323 Must be zeroed on transmission and ignored on reception. 325 5.11. S: 1 bit 327 If this bit is set, it indicates that the packet count for the 328 source-group pair is for the source network, as determined by mask- 329 ing the source address with the Src Mask field. 331 5.12. Src Mask: 6 bits 333 This field contains the number of 1's in the netmask this router 334 has for the source (i.e. a value of 24 means the netmask is 335 0xffffff00). If the router is forwarding solely on group state, 336 this field is set to 63 (0x3f). 338 5.13. Forwarding Code: 8 bits 340 This field contains a forwarding information/error code. Defined 341 values include: 343 Value Name Description 344 -------------------------------------------------------------------- 345 0x00 NO_ERROR No error 346 0x01 WRONG_IF Traceroute request arrived on an interface to 347 which this router would not forward for this 348 source,group,destination. 349 0x02 PRUNE_SENT This router has sent a prune upstream which 350 applies to the source and group in the tracer- 351 oute request. 353 0x03 PRUNE_RCVD This router has stopped forwarding for this 354 source and group in response to a request from 355 the next hop router. 356 0x04 SCOPED The group is subject to administrative scoping 357 at this hop. 358 0x05 NO_ROUTE This router has no route for the source. 359 0x06 WRONG_LAST_HOP This router is not the proper last-hop router. 360 0x07 NOT_FORWARDING This router is not forwarding this 361 source,group for an unspecified reason. 362 0x08 REACHED_RP Reached Rendez-vous Point or Core 363 0x09 RPF_IF Traceroute request arrived on the expected RPF 364 interface for this source,group. 365 0x0A NO_MULTICAST Traceroute request arrived on an interface 366 which is not enabled for multicast. 367 0x81 NO_SPACE There was not enough room to insert another 368 response data block in the packet. 369 0x82 OLD_ROUTER The previous hop router does not understand 370 traceroute requests. 371 0x83 ADMIN_PROHIB Traceroute is administratively prohibited. 373 Note that if a router discovers there is not enough room in a 374 packet to insert its response, it puts the 0x81 error code in the 375 previous router's Forwarding Code field, overwriting any error the 376 previous router placed there. It is expected that a multicast 377 traceroute client, upon receiving this error, will restart the 378 trace at the last hop listed in the packet. 380 The 0x80 bit of the Forwarding Code is used to indicate a fatal 381 error. A fatal error is one where the router may know the previous 382 hop but cannot forward the message to it. 384 6. Router Behavior 386 All of these actions are performed in addition to (NOT instead of) for- 387 warding the packet, if applicable. E.g. a multicast packet that has TTL 388 remaining MUST be forwarded normally, as MUST a unicast packet that has 389 TTL remaining and is not addressed to this router. 391 6.1. Traceroute Query 393 A traceroute Query message is a traceroute message with no response 394 blocks filled in, and uses IGMP type 0x1F. 396 6.1.1. Packet Verification 398 Upon receiving a traceroute Query message, a router must examine 399 the Query to see if it is the proper last-hop router for the 400 destination address in the packet. It is the proper last-hop 401 router if it has a multicast-capable interface on the same subnet 402 as the Destination Address and is the router that would forward 403 traffic from the given source onto that subnet. 405 If the router determines that it is not the proper last-hop router, 406 or it cannot make that determination, it does one of two things 407 depending if the Query was received via multicast or unicast. If 408 the Query was received via multicast, then it MUST be silently 409 dropped. If it was received via unicast, a forwarding code of 410 NOT_LAST_HOP is noted and processing continues as in section 7.2. 412 Duplicate Query messages as identified by the tuple (IP Source, 413 Query ID) SHOULD be ignored. 415 6.1.2. Normal Processing 417 When a router receives a traceroute Query and it determines that it 418 is the proper last-hop router, it treats it like a traceroute 419 Request and performs the steps listed in section 7.2. 421 6.2. Traceroute Request 423 A traceroute Request is a traceroute message with some number of 424 response blocks filled in, and also uses IGMP type 0x1F. Routers 425 can tell the difference between Queries and Requests by checking 426 the length of the packet. 428 6.2.1. Packet Verification 430 If the traceroute Request is not addressed to this router, or if 431 the Request is addressed to a multicast group which is not a link- 432 scoped group (e.g. 224.0.0.x), it MUST be silently ignored. 434 6.2.2. Normal Processing 436 When a router receives a traceroute Request, it performs the fol- 437 lowing steps. Note that it is possible to have multiple situations 438 covered by the Forwarding Codes. The first one encountered is the 439 one that is reported, i.e. all "note forwarding code N" should be 440 interpreted as "if forwarding code is not already set, set forward- 441 ing code to N". 443 1. Insert a new response block into the packet and fill in the 444 Query Arrival Time, Outgoing Interface Address, Output Packet 445 Count, and FwdTTL. 447 2. Attempt to determine the forwarding information for the source 448 and group specified, using the same mechanisms as would be used 449 when a packet is received from the source destined for the 450 group. State need not be instantiated, it can be "phantom" 451 state created only for the purpose of the trace. 453 3. If no forwarding information can be determined, an error code 454 of NO_ROUTE is inserted in the Forwarding Code field, the 455 remaining fields that have not yet been filled in are set to 456 zero, and the packet is forwarded to the requester as described 457 in "Forwarding Traceroute Requests". 459 4. Fill in the Incoming Interface Address, Previous-Hop Router 460 Address, Input Packet Count, Total Number of Packets, Routing 461 Protocol, S, and Src Mask from the forwarding information that 462 was determined. 464 5. If traceroute is administratively prohibited or the previous 465 hop router does not understand traceroute requests, note the 466 appropriate forwarding code (ADMIN_PROHIB or OLD_ROUTER). If 467 traceroute is administratively prohibited and any of the fields 468 as filled in step 4 are considered private information, zero 469 out the applicable fields. Then the packet is forwarded to the 470 requester as described in "Forwarding Traceroute Requests". 472 6. If the reception interface is not enabled for multicast, note 473 forwarding code NO_MULTICAST. If the reception interface is 474 the interface from which the router would expect data to arrive 475 from the source, a forwarding code of RPF_IF is noted. Other- 476 wise, if the reception interface is not one to which the router 477 would forward data from the source, a forwarding code of 478 WRONG_IF is noted. 480 7. If the group is subject to administrative scoping on either the 481 Outgoing or Incoming interfaces, a forwarding code of SCOPED is 482 noted. 484 8. If this router is the Rendez-vous Point or Core for the group, 485 a forwarding code of REACHED_RP is noted. 487 9. If this router has sent a prune upstream which applies to the 488 source and group in the traceroute Request, it notes forwarding 489 code PRUNE_SENT. If the router has stopped forwarding down- 490 stream in response to a prune sent by the next hop router, it 491 notes forwarding code PRUNE_RCVD. If the router should nor- 492 mally forward traffic for this source and group downstream but 493 is not, it notes forwarding code NOT_FORWARDING. 495 10. The packet is then sent on to the previous hop or the requester 496 as described in "Forwarding Traceroute Requests". 498 6.3. Traceroute response 500 A router must forward all traceroute response packets normally, 501 with no special processing. If a router has initiated a traceroute 502 with a Query or Request message, it may listen for Responses to 503 that traceroute but MUST still forward them as well. 505 6.4. Forwarding Traceroute Requests 507 If the Previous-hop router is known for the source and group (or, 508 if no group is specified, the previous-hop router for the source, 509 or if no source is specified, the previous-hop router for the 510 group) and the number of response blocks is less than the number 511 requested, the packet is sent to that router. If the Incoming 512 Interface is known but the Previous-hop router is not known, the 513 packet is sent to an appropriate multicast address on the Incoming 514 Interface. The appropriate multicast address may depend on the 515 routing protocol in use, MUST be a link-scoped group (i.e. 516 224.0.0.x), MUST NOT be ALL-SYSTEMS.MCAST.NET (224.0.0.1) and may 517 be ALL-ROUTERS.MCAST.NET (224.0.0.2) if the routing protocol in use 518 does not define a more appropriate group. Otherwise, it is sent to 519 the Response Address in the header, as described in "Sending 520 Traceroute Responses". 522 6.5. Sending Traceroute Responses 524 6.5.1. Destination Address 526 A traceroute response must be sent to the Response Address in the 527 traceroute header. 529 6.5.2. TTL 531 If the Response Address is unicast, the router inserts its normal 532 unicast TTL in the IP header. If the Response Address is multi- 533 cast, the router copies the Response TTL from the traceroute header 534 into the IP header. 536 6.5.3. Source Address 538 If the Response Address is unicast, the router may use any of its 539 interface addresses as the source address. Since some multicast 540 routing protocols forward based on source address, if the Response 541 Address is multicast, the router MUST use an address that is known 542 in the multicast routing table if it can make that determination. 544 6.5.4. Sourcing Multicast Responses 546 When a router sources a multicast response, the response packet 547 MUST be sent on a single interface, then forwarded as if it were 548 received on that interface. It MUST NOT source the response packet 549 individually on each interface, since that causes duplicate pack- 550 ets. 552 7. Using multicast traceroute 554 7.1. Sample Client 556 This section describes the behavior of an example multicast traceroute 557 client. 559 7.1.1. Sending Initial Query 561 When the destination of the trace is the machine running the 562 client, the traceroute Query packet can be sent to the ALL-ROUTERS 563 multicast group (224.0.0.2). This will ensure that the packet is 564 received by the last-hop router on the subnet. Otherwise, if the 565 proper last-hop router is known for the trace destination, the 566 Query could be unicasted to that router. Otherwise, the Query 567 packet should be multicasted to the group being queried; if the 568 destination of the trace is a member of the group this will get the 569 Query to the proper last-hop router. In this final case, the 570 packet should contain the Router Alert option, to make sure that 571 routers that are not members of the multicast group notice the 572 packet. See also section 8.2 on determining the last-hop router. 574 7.1.2. Determining the Path 576 The client could send a small number of Initial Query messages with 577 a large "# hops" field, in order to try to trace the full path. If 578 this attempt fails, one strategy is to perform a linear search (as 579 the traditional unicast traceroute program does); set the "#hops" 580 field to 1 and try to get a response, then 2, and so on. If no 581 response is received at a certain hop, the hop count can continue 582 past the non-responding hop, in the hopes that further hops may 583 respond. These attempts should continue until a user-defined time- 584 out has occurred. 586 See also section 8.3 and 8.4 on receiving the results of a trace. 588 7.1.3. Collecting Statistics 590 After a client has determined that it has traced the whole path or 591 as much as it can expect to (see section 8.5), it might collect 592 statistics by waiting a short time and performing a second trace. 593 If the path is the same in the two traces, statistics can be dis- 594 played as described in section 9.3 and 9.4. 596 Details of performing a multicast traceroute: 598 7.2. Last hop router 600 The traceroute querier may not know which is the last hop router, 601 or that router may be behind a firewall that blocks unicast packets 602 but passes multicast packets. In these cases, the traceroute 603 request should be multicasted to the group being traced (since the 604 last hop router listens to that group). All routers except the 605 correct last hop router should ignore any multicast traceroute 606 request received via multicast. Traceroute requests which are mul- 607 ticasted to the group being traced must include the Router Alert IP 608 option [Katz97]. 610 Another alternative is to unicast to the trace destination. 611 Traceroute requests which are unicasted to the trace destination 612 must include the Router Alert IP option [Katz97], in order that the 613 last-hop router is aware of the packet. 615 If the traceroute querier is attached to the same router as the 616 destination of the request, the traceroute request may be multicas- 617 ted to 224.0.0.2 (ALL-ROUTERS.MCAST.NET) if the last-hop router is 618 not known. 620 7.3. First hop router 622 The traceroute querier may not be unicast reachable from the first 623 hop router. In this case, the querier should set the traceroute 624 response address to a multicast address, and should set the 625 response TTL to a value sufficient for the response from the first 626 hop router to reach the querier. It may be appropriate to start 627 with a small TTL and increase in subsequent attempts until a suffi- 628 cient TTL is reached, up to an appropriate maximum (such as 192). 630 The IANA has assigned 224.0.1.32, MTRACE.MCAST.NET, as the default 631 multicast group for multicast traceroute responses. Other groups 632 may be used if needed, e.g. when using mtrace to diagnose problems 633 with the IANA-assigned group. 635 7.4. Broken intermediate router 637 A broken intermediate router might simply not understand traceroute 638 packets, and drop them. The querier would then get no response at 639 all from its traceroute requests. It should then perform a hop-by- 640 hop search by setting the number of responses field until it gets a 641 response (both linear and binary search are options, but binary is 642 likely to be slower because a failure requires waiting for a time- 643 out). 645 7.5. Trace termination 647 When performing an expanding hop-by-hop trace, it is necessary to 648 determine when to stop expanding. 650 7.5.1. Arriving at source 652 A trace can be determined to have arrived at the source if the 653 Incoming Interface of the last router in the trace is non-zero, but 654 the Previous Hop router is zero. 656 7.5.2. Fatal Error 658 A trace has encountered a fatal error if the last Forwarding Error 659 in the trace has the 0x80 bit set. 661 7.5.3. No Previous Hop 663 A trace can not continue if the last Previous Hop in the trace is 664 set to 0. 666 7.5.4. Trace shorter than requested 668 If the trace that is returned is shorter than requested (i.e. the 669 number of Response blocks is smaller than the "# hops" field), the 670 trace encountered an error and could not continue. 672 7.6. Continuing after an error 674 When the NO_SPACE error occurs, the client might try to continue 675 the trace by starting it at the last hop in the trace. It can do 676 this by unicasting to this router's outgoing interface address, 677 keeping all fields the same. If this results in a single hop and a 678 "WRONG_IF" error, the client may try setting the trace destination 679 to the same outgoing interface address. 681 If a trace times out, it is likely to be because a router in the 682 middle of the path does not support multicast traceroute. That 683 router's address will be in the Previous Hop field of the last 684 entry in the last reply packet received. A client may be able to 685 determine (via mrinfo[Pusa98] or SNMP[Thal98a,Thal98b]) a list of 686 neighbors of the non-responding router. If desired, each of those 687 neighbors could be probed to determine the remainder of the path. 688 Unfortunately, this heuristic may end up with multiple paths, since 689 there is no way of knowing what the non-responding router's algo- 690 rithm for choosing a previous-hop router is. However, if all paths 691 but one flow back towards the non-responding router, it is possible 692 to be sure that this is the correct path. 694 7.7. Multicast Traceroute and shared-tree routing protocols 696 When using shared-tree routing protocols like PIM-SM and CBT, it is 697 still possible to use multicast traceroute to determine paths. 699 7.7.1. PIM-SM 701 When a multicast traceroute reaches a PIM-SM RP and the RP does not for- 702 ward the trace on, it means that the RP has not performed a source-spe- 703 cific join so there is no more state to trace. However, the path that 704 traffic would use if the RP did perform a source-specific join can be 705 traced by setting the trace destination to the RP, the trace source to 706 the traffic source, and the trace group to 0. This trace Query may be 707 unicasted to the RP. 709 7.7.2. CBT 711 When a multicast traceroute reaches a CBT Core, it must simply stop 712 since CBT does not have source-specific state. However, a second trace 713 can be performed, setting the trace destination to the traffic source, 714 the trace group to the group being traced, and the trace source to the 715 Core (or to 0, since CBT does not have source-specific state). This 716 trace Query may be unicasted to the Core. There are two possibilities 717 when combining the two traces: 719 7.7.2.1. No overlap 721 If there is no overlap between the two traces, the second trace can 722 be reversed and appended to the first trace. This composite trace 723 shows the full path from the source to the destination. 725 7.7.2.2. Overlapping paths 727 If there is a portion of the path that is common to the ends of the 728 two traces, that portion is removed from both traces. Then, as in 729 the no overlap case, the second trace is reversed and appended to 730 the first trace, and the composite trace again contains the full 731 path. 733 This algorithm works whether the source has joined the CBT tree or not. 735 8. Problem Diagnosis 737 8.1. Forwarding Inconsistencies 739 The forwarding error code can tell if a group is unexpectedly 740 pruned or administratively scoped. 742 8.2. TTL problems 744 By taking the maximum of (hops from source + forwarding TTL thresh- 745 old) over all hops, you can discover the TTL required for the 746 source to reach the destination. 748 8.3. Congestion 750 By taking two traces, you can find packet loss information by com- 751 paring the difference in input packet counts to the difference in 752 output packet counts at the previous hop. On a point-to-point 753 link, any difference in these numbers implies packet loss. Since 754 the packet counts may be changing as the trace query is propagat- 755 ing, there may be small errors (off by 1 or 2) in these statistics. 756 However, these errors will not accumulate if multiple traces are 757 taken to expand the measurement period. On a shared link, the 758 count of input packets can be larger than the number of output 759 packets at the previous hop, due to other routers or hosts on the 760 link injecting packets. This appears as "negative loss" which may 761 mask real packet loss. 763 In addition to the counts of input and output packets for all mul- 764 ticast traffic on the interfaces, the response data includes a 765 count of the packets forwarded by a node for the specified source- 766 group pair. Taking the difference in this count between two traces 767 and then comparing those differences between two hops gives a mea- 768 sure of packet loss just for traffic from the specified source to 769 the specified receiver via the specified group. This measure is 770 not affected by shared links. 772 On a point-to-point link that is a multicast tunnel, packet loss is 773 usually due to congestion in unicast routers along the path of that 774 tunnel. On native multicast links, loss is more likely in the out- 775 put queue of one hop, perhaps due to priority dropping, or in the 776 input queue at the next hop. The counters in the response data do 777 not allow these cases to be distinguished. Differences in packet 778 counts between the incoming and outgoing interfaces on one node 779 cannot generally be used to measure queue overflow in the node 780 because some packets may be routed only to or from other interfaces 781 on that node. 783 In the multicast extensions for SunOS 4.1.x from Xerox PARC, both 784 the output packet count and the packet forwarding count for the 785 source-group pair are incremented before priority dropping for rate 786 limiting occurs and before the packets are put onto the interface 787 output queue which may overflow. These drops will appear as (posi- 788 tive) loss on the link even though they occur within the router. 790 In release 3.3/3.4 of the UNIX multicast extensions, a multicast 791 packet generated on a router will be counted as having come in an 792 interface even though it did not. This can create the appearance 793 of negative loss even on a point-to-point link. 795 In releases up through 3.5/3.6, packets were not counted as input 796 on an interface if the reverse-path forwarding check decided that 797 the packets should be dropped. That causes the packets to appear 798 as lost on the link if they were output by the upstream hop. This 799 situation can arise when two routers on the path for the group 800 being traced are connected by a shared link, and the path for some 801 other group does not flow between those two routers because the 802 downstream router receives packets for the other group on another 803 interface, but the upstream router is the elected forwarder to 804 other routers or hosts on the shared link. 806 8.4. Link Utilization 808 Again, with two traces, you can divide the difference in the input 809 or output packet counts at some hop by the difference in time 810 stamps from the same hop to obtain the packet rate over the link. 811 If the average packet size is known, then the link utilization can 812 also be estimated to see whether packet loss may be due to the rate 813 limit or the physical capacity on a particular link being exceeded. 815 8.5. Time delay 817 If the routers have synchronized clocks, it is possible to estimate 818 propagation and queueing delay from the differences between the 819 timestamps at successive hops. 821 9. Acknowledgments 823 This specification started largely as a transcription of Van Jacobson's 824 slides from the 30th IETF, and the implementation in mrouted 3.3 by Ajit 825 Thyagarajan. Van's original slides credit Steve Casner, Steve Deering, 826 Dino Farinacci and Deb Agrawal. A multicast traceroute client, mtrace, 827 has been implemented by Ajit Thyagarajan, Steve Casner and Bill Fenner. 829 The idea of unicasting a multicast traceroute Query to the destination 830 of the trace with Router Alert set is due to Tony Ballardie. The idea 831 of the "S" bit to allow statistics for a source subnet is due to Tom 832 Pusateri. 834 10. IANA Considerations 836 10.1. Routing Protocols 838 The IANA is responsible for allocating new Routing Protocol codes. 839 The Routing Protocol code is somewhat problematic, since in the 840 case of protocols like CBT and PIM it must encode both a unicast 841 routing algorithm and a multicast tree-building protocol. The 842 space was not divided into two fields because it was already small 843 and some combinations (e.g. DVMRP) would be wasted. 845 Routing Protocol codes should be allocated for any combination of 846 protocols that are in common use in the Internet. 848 10.2. Forwarding Codes 850 New Forwarding codes must only be created by an RFC that modifies 851 this document's section 7, fully describing the conditions under 852 which the new forwarding code is used. The IANA may act as a cen- 853 tral repository so that there is a single place to look up forward- 854 ing codes and the document in which they are defined. 856 11. Security Considerations 858 11.1. Topology discovery 860 mtrace can be used to discover any actively-used topology. If your 861 network topology is a secret, mtrace may be restricted at the bor- 862 der of your domain, using the ADMIN_PROHIB forwarding code. 864 11.2. Traffic rates 866 mtrace can be used to discover what sources are sending to what 867 groups and at what rates. If this information is a secret, mtrace 868 may be restricted at the border of your domain, using the 869 ADMIN_PROHIB forwarding code. 871 11.3. Unicast replies 873 The "Response address" field may be used to send a single packet 874 (the traceroute Reply packet) to an arbitrary unicast address. It 875 is possible to use this facility as a packet amplifier, as a small 876 multicast traceroute Query may turn into a large Reply packet. 878 12. References 880 Brad88 Braden, B., D. Borman, C. Partridge, "Computing the 881 Internet Checksum", RFC 1071, ISI, September 1988. 883 Bradner97 Bradner, S., "Key words for use in RFCs to Indicate 884 Requirement Levels", RFC 2119/BCP 14, Harvard University, 885 March 1997. 887 Katz97 Katz, D., "IP Router Alert Option," RFC 2113, Cisco Sys- 888 tems, February 1997. 890 13. Authors' Addresses 892 William C. Fenner 893 Xerox PARC 894 3333 Coyote Hill Road 895 Palo Alto, CA 94304 897 Phone: +1 650 812 4816 899 Email: fenner@parc.xerox.com 901 Stephen L. Casner 902 Cisco Systems 903 1072 Arastradero Road 904 Palo Alto, CA 94304 906 Email: casner@precept.com