Traceroute Using an IP Option
draft-malkin-traceroute-01

Internet Engineering Task Force                                G. Malkin
Internet Draft                                                  Xylogics
                                                            October 1992

                               Traceroute

Abstract

   Traceroute serves as a valuable network debugging tool.  The way in
   which it is currently implemented has the advantage of being
   automatically supported by all of the routers.  It's two problems are
   the number of packets it generates and the amount of time it takes to
   run.

   This document specifies a new IP option and ICMP message type which
   duplicates the functionality of the existing traceroute method while
   generating fewer packets and completing in a shorter time.

Status of this Memo

   This document is an Internet Draft.  Internet Drafts are working
   documents of the Internet Engineering Task Force (IETF), its Areas,
   and its Working Groups. Note that other groups may also distribute
   working documents as Internet Drafts).

   Internet Drafts are draft documents valid for a maximum of six
   months. Internet Drafts may be updated, replaced, or obsoleted by
   other documents at any time.  It is not appropriate to use Internet
   Drafts as reference material or to cite them other than as a "working
   draft" or "work in progress."

   Please check the I-D abstract listing contained in each Internet
   Draft directory to learn the current status of this or any other
   Internet Draft.

   It is intended that this document will be submitted to the IESG for
   consideration as a standards document.  Distribution of this document
   is unlimited.

Table of Contents

   1.  Traceroute Today  . . . . . . . . . . . . . . . . . . . . . 2
   2.  Traceroute Tomorrow . . . . . . . . . . . . . . . . . . . . 2
   2.1 Basic Algorithm . . . . . . . . . . . . . . . . . . . . . . 2
   2.2 IP Traceroute option format . . . . . . . . . . . . . . . . 3
   2.3 ICMP Traceroute message format  . . . . . . . . . . . . . . 4
   3.  Protocol  . . . . . . . . . . . . . . . . . . . . . . . . . 5
   3.1 Hop Counts  . . . . . . . . . . . . . . . . . . . . . . . . 5

Expiration: April 29, 1993                                      [Page 1]
Internet Draft                 Traceroute                   October 1993

   3.2 Destination Node Operation  . . . . . . . . . . . . . . . . 6
   3.3 Router Operation  . . . . . . . . . . . . . . . . . . . . . 6
   4.  References  . . . . . . . . . . . . . . . . . . . . . . . . 6
   5.  Security Considerations . . . . . . . . . . . . . . . . . . 7
   6.  Author's Address  . . . . . . . . . . . . . . . . . . . . . 7

1.  Traceroute Today

   The existing traceroute operates by sending out a packet with a Time
   To Live (TTL) of 1.  The first hop then sends back an ICMP [1] error
   message indicating that the packet could not be forwarded because the
   TTL expired.  The packet is then resent with a TTL of 2, and the
   second hop returns the TTL expired.  This process continues until the
   destination is reached.  The purpose behind this is to record the
   source of each ICMP TTL exceeded message to provide a trace of the
   path the packet took to reach the destination.

   The advantage of this algorithm, is that every router already has the
   ability to send TTL exceeded messages.  No special code is required.
   The disadvantages are the number of packets generated (2n, where n is
   the number of hops), the time it takes to duplicate all the nearer
   hops with each successive packet, and the fact that the path may
   change during this process.  Also, this algorithm does not trace the
   return path, which may differ from the outbound path.

2.  Traceroute Tomorrow

   The proposed traceroute would use a different algorithm to achieve
   the same goal, namely, to trace the path to a host.  Because the new
   traceroute uses an ICMP message designed for the purpose, additional
   information, unavailable to the original traceroute user, can be made
   available.

2.1 Basic Algorithm

   A new IP Traceroute option will be defined.  The presence of this
   option in a ICMP Echo (or any other) packet will cause a router to
   send the newly defined ICMP Traceroute message to the originator of
   the packet.  In this way, the outbound path of the packet will be
   logged by the originator with only n+1 (instead of 2n) packets.  This
   algorithm does not suffer from a changing path and allows the return
   packet's path to be traced (provided the destination preserves the IP
   Traceroute option.

   The disadvantage of this method is that the traceroute function will
   have to be put into the routers.  To counter this disadvantage,

Expiration: April 29, 1993                                      [Page 2]
Internet Draft                 Traceroute                   October 1993

   however, is the fact that this mechanism is easily ported to the new
   IP version 7 work which is being done in the IETF.

2.2 IP Traceroute option format

    0               8              16              24
   +-+-+-+-+-+-+-+-+---------------+---------------+---------------+
   |F| C |  Number |    Length     |          ID Number            |
   +-+-+-+-+-+-+-+-+---------------+---------------+---------------+
   |                     Originator IP Address                     |
   +---------------+---------------+---------------+---------------+
   |      OHC      |      RHC      |
   +- - - - - - - -+- - - - - - - -+

   F (copy to fragments)

      0 (do not copy to fragments)

   C (class)

      2 (Debugging & Measurement)

   Number

      To Be Assigned

   ID Number

      An arbitrary number used by the originator of the ping packet to
      identify the ICMP Traceroute messages.

   Originator IP Address

      The IP address of the originator of the ping packet.

   OHC (Outbound Hop Count)

      The number of routers through which the outbound ping packet has
      passed.  The OHC field is optional.  If the length of the option
      is 8, then there are no hop counts.  If the length is 9
      (indicating that this is the outgoing packet), then there is an
      OHC which must be incremented by each router (but NOT the
      destination).  If the length is 10 (indicating that this is the
      return packet), then the OHC is not incremented.

   RHC (Return Hop Count)

      The number of routers through which the return packet has passed.

Expiration: April 29, 1993                                      [Page 3]
Internet Draft                 Traceroute                   October 1993

      The RHC field is optional.  If the length of the option is less
      than 10, then there is no RHC to increment.  If the length is 10,
      then the RHC must be incremented by each router (but NOT the
      originator, which is the destination of the return packet).

2.3  ICMP Traceroute message format

    0               8              16              24
   +---------------+---------------+---------------+---------------+
   |     Type      |     Code      |           Checksum            |
   +---------------+---------------+---------------+---------------+
   |           ID Number           |      OHC      |      RHC      |
   +---------------+---------------+---------------+---------------+
   |                       Output Link Speed                       |
   +---------------+---------------+---------------+---------------+
   |        Output Link MTU        |            unused             |
   +---------------+---------------+---------------+---------------+

   Type

      To Be Assigned

   Code

      0 - Outbound ping packet successfully forwarded
      1 - No route for outbound ping packet; packet discarded

   Checksum

      The 16 bit one's complement of the one's complement sum of all 16
      bit words in the header.  For computing the checksum, the checksum
      field should be zero.

   ID Number

      The ID Number as copied from the IP Traceroute option of the
      packet which caused this Traceroute message to be sent.

   OHC

      The Outbound Hop Count as copied from the IP Traceroute option of
      the packet which caused this Traceroute message to be sent.  If
      there is no OHC is the Traceroute option, this field will have a
      value of zero.

   RHC

      The Return Hop Count as copied from the IP Traceroute option of

Expiration: April 29, 1993                                      [Page 4]
Internet Draft                 Traceroute                   October 1993

      the packet which caused this Traceroute message to be sent.  If
      there is no RHC is the Traceroute option, this field will have a
      value of zero.

   Output Link Speed

      The speed, in bits per second, of the link over which the ping
      packet will be sent.  If this value cannot be determined, the
      field should be set to zero.

   Output Link MTU

      The MTU, in bytes, of the link over which the ping packet will be
      sent.  MTU refers to the data portion (includes IP header;
      excludes datalink header/trailer) of the packet.  If this value
      cannot be determined, the field should be set to zero.

3.  Protocol

   The ping packet which is used to carry the IP Traceroute option
   should use no special Type Of Service (TOS) or Precedence, unless the
   purpose is to trace the path of packets with special TOS or
   Precedence values.

   The TTL of the ping packet should be set to the default value
   specified in "Assigned Numbers" [2].

3.1 Hop Counts

   The hop count fields in the IP Traceroute option are optional.  By
   not including them (and specifying an option length of 8), the
   routers will have less to do (no increment or checksum
   recalculation).  The hop counts may be used to detect the loss of
   ICMP Traceroute messages.  If the number of Traceroute messages
   received is less than the hop count, then some Traceroute messages
   were lost.

   To use hop counts, the originator sets the option length to 9 and
   pads the option with 4 zero bytes (OHC, RHC and 2 end-of-option-list
   options).  When a router sees a Traceroute option with a length of 9,
   it increments the OHC by one before generating the ICMP Traceroute
   message.  When a router sees a Traceroute option with a length of 10,
   it increments the RHC by one before generating the ICMP Traceroute
   message.

   It is important to note that the Traceroute hop counts are NOT the
   same as the IP TTL.  A hop count should only be incremented when an

Expiration: April 29, 1993                                      [Page 5]
Internet Draft                 Traceroute                   October 1993

   ICMP Traceroute message is sent.

3.2 Destination Node Operation

   When a destination node receives a ping packet with an IP Traceroute
   option, the return packet should also carry that option.  The value
   in the ID Number field should be copied into the return packet.  If
   the option length is 9 (outbound hops were being counted), the value
   of the OHC field should also be copied and the option length
   increased to 10.  The destination should NOT increment any hop
   counts.

3.3 Router Operation

   When a router forwards a ping packet with an IP Traceroute option, it
   should send an ICMP Traceroute message to the IP address in the
   Originator IP Address field of the option.  If the Traceroute option
   length is 9, the OHC field should be incremented.  If the option
   length is 10, the RHC field should be incremented.  The Traceroute
   message should reflect the incremented hop count.  The Output Link
   Speed field should be set to the speed of the link over which the
   ping packet will be sent (e.g. 10,000,000 for an Ethernet), or zero
   if the output link speed cannot be determined.  The Output Link MTU
   field should be set to the MTU of the link over which the ping packet
   will be sent or zero if the MTU cannot be determined.

   The ping packet should be forwarded as though the Traceroute option
   did not exist; that is, it should take the same path to the
   destination.

   The ICMP Traceroute message should have TOS and Precedence values of
   zero (default).  The TTL should be set to the default defined in
   "Assigned Numbers".

   If the outbound ping packet cannot be forwarded, the ICMP Traceroute
   message should have a Code value of one.  If the return ping packet
   cannot be forwarded because there is no route, then there is no need
   to send a Traceroute message since it could not be forwarded either.

4.  References

   [1] Postel, J., "Internet Control Message Protocol", RFC 792,
       USC/Information Sciences Institute, September 1981.

   [2] Reynolds, J., J. Postel, "Assigned Numbers", RFC 1340,
       USC/Information Sciences Institute, July, 1992.

Expiration: April 29, 1993                                      [Page 6]
Internet Draft                 Traceroute                   October 1993

5.  Security Considerations

   Security is not discussed in this memo.

6.  Author's Address

   Gary Scott Malkin
   Xylogics, Inc.
   53 Third Avenue
   Burlington, MA 01803

   Phone:  (617) 272-8140
   EMail:  gmalkin@Xylogics.COM

Expiration: April 29, 1993                                      [Page 7]