Internet Engineering Task Force                                W. Fenner
INTERNET-DRAFT                                      AT&T Labs - Research
draft-ietf-msdp-traceroute-00.txt                               D. Meyer
                                                           cisco Systems
                                                             March, 2000
                                                  Expires September 2000

                            MSDP Traceroute

Status of this Memo

This document is an Internet Draft and is in full conformance with all
provisions of Section 10 of RFC2026.  Internet Drafts are working docu-
ments of the Internet Engineering Task Force (IETF), its Areas, and its
Working Groups.  Note that other groups may also distribute working doc-
uments 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 docu-
ments at any time.  It is not appropriate to use Internet Drafts as ref-
erence material or to cite them other than as a "working draft" or "work
in progress."

The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.

The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.

Distribution of this document is unlimited.

                                Abstract

     In order to diagnose problems with the Peer-RPF-Flooding mechanisms
     in the Multicast Source Discovery Protocol [MSDP], we introduce a
     method of tracing the path that an SA message should have taken,
     along with collecting statistics along that path.  This occurs in a
     way similar to multicast traceroute [MTRACE], with each router
     appending information about this hop and forwarding the message
     towards the desired RP.

This document is a product of the MSDP working group within the Internet
Engineering Task Force.  Comments are solicited and should be addressed
to the working group's mailing list at msdp@network-services.uoregon.edu



Fenner, Meyer            Expires September 2000                 [Page 1]


Internet Draft      draft-ietf-msdp-traceroute-00.txt        March, 2000


and/or the authors.


















































Fenner, Meyer            Expires September 2000                 [Page 2]


Internet Draft      draft-ietf-msdp-traceroute-00.txt        March, 2000


1.  Introduction

One of the key problems in the deployment of MSDP [MSDP] infrastructures
has been the inability to trace the path taken by MSDP control packets.
The protocol specified in the document addresses this problem by provid-
ing a traceroute facility for MSDP Source Active (SA) Messages.  It is
important to note that, with the exception of data encapsulated in SA
messages, MSDP traceroute traces a path through the MSDP control plane.
It is important to note that the MSDP control path need not be the same
as the path followed by data packets.

As is the case for multicast traceroute, the goals of MSDP traceroute
include

 o To be able to trace the path that a SA message would take from some
   source router (RP) to some destination route (RP).

 o To be able to isolate SA Message loss problems

 o To be able to isolate configuration problems (e.g., TTL threshold).

 o To minimize packets sent (e.g. no flooding, no implosion).


1.1.  Definitions

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED",  "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119].

2.  Originating an MSDP Traceroute Query


As is the case for other kinds of traceroute, both routers and hosts
will want to originate MSDP traceroute queries.


2.1.  Routers Originating an MSDP Traceroute Query

When a router originates an MSDP traceroute Query, it formulates the
Query by filling its first block and unicasts the Query packet its RPF
neighbor toward the specified RP. Note that this is unlike multicast
traceroute, in which the Query is sent to the last-hop multicast router
for the destination, converted into a Request, and fowarded back towards
the source and group.






Fenner, Meyer            Expires September 2000                 [Page 3]


Internet Draft      draft-ietf-msdp-traceroute-00.txt        March, 2000


2.2.  Hosts Originating an MSDP Traceroute Query

When a host originates an MSDP traceroute Query, it formulates the Query
by filling its first block with the RP (and optionally the source and
group), and then unicasts the UDP encapsulated Query packet to the spec-
ified RP [means UDP encapsulation has to be supported]. The RP must
store state that describes the host that made the query [security stuff
here]. If a router receives a Query packet and is not running MSDP, the
router discards the packet and returns a response with error code TBD
[do we want a notification for this in the MSDP spec?]



3.  Packet Formats

Encapsulated in 2 different MSDP TLVs:

In-progress MSDP traceroute: ...

MSDP traceroute answer: ...

Fixed request header contains S, G, RP, query ID, current router pointer
(for returning packet HBH).  Variable length request header contains
optional data (TBD, must be skipped by implementations that don't sup-
port it).

 0                   1                   2                   3
 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                     Source Address                            |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                      Group Address                            |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       RP Address                              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                        Query ID                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  skip hops    |   max hops    |  addl length  |  rtr pointer  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... maxhops*4  octets of router addresses ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... addl length*4 octets of additional request data ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+








Fenner, Meyer            Expires September 2000                 [Page 4]


Internet Draft      draft-ietf-msdp-traceroute-00.txt        March, 2000


3.1.  Source Address

     Source in (S,G,RP)

3.2.  Group Address

     Group in (S,G,RP)

3.3.  RP Address

     RP in (S,G,RP)

3.4.  Query ID

     This field is used as a unique identifier for this traceroute
     request so that duplicate or delayed responses may be detected.


3.5.  skip hops

     The number of hops that have been skipped in this request. This
     allows for partial replies.

3.6.  max hops

     The max. # of hops requested in this traceroute request.

3.7.  addl length

     Length (in units of 4 octets) of accompanying additional request
     data.

3.8.  rtr pointer

     The rtr pointer is a pointer into the router addresses table. When
     the query is being filled in (outbound) the rtr pointer points to
     the next available entry. On return to the query originator, it
     points to the next hop back (toward the originator).

3.9.  router addresses

     Table of the outgoing interfaces that this request has traversed.
     Inserted by requestor, max hops * 4 octets.

3.10.  optional data

     Optional data, addl length * 4 octets long.




Fenner, Meyer            Expires September 2000                 [Page 5]


Internet Draft      draft-ietf-msdp-traceroute-00.txt        March, 2000


Fixed part of response block contains: - my IP address on outgoing
interface (in the routing block) - RPF peer - flag: (S,G,RP) present?  -
flag: hit source - who I learned this SA from - msdpSACacheInSAs - msdp-
SACacheInDataPackets - msdpSACacheUpTime - msdpSACacheExpiryTime Vari-
able length part to go with request's variable length part.

 0                   1                   2                   3
 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| addl length   |      MBZ                      |     Code      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                    Next-Hop Router Address                    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|         Count of SA messages received for this (S,G,RP)       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Count of encapsulated data packets received for this (S,G,RP) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                    SA cache entry uptime                      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                 SA cache entry expiry time                    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... addl length * 4 octets of additional data ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


4.  Protocol Processing


4.1.  Processing an in-progress traceroute

     The following steps are taken when receiving an in-progress tracer-
     oute:

     1.   If the # of hops have already been exceeded, then something
          bad happened; just turn it into a response and return it.

     2.   Append an empty router response to the packet.  If this action
          causes the message to exceed MSDP's 1400-byte MTU, follow the
          steps in section XXX, Returning Partial Responses, and then
          continue with the now-smaller packet.

     3.   Look up the SA cache information for the (S,G,RP).  If no SA
          cache entry exists, fill in zeros for these values.

     4.   Look up the MSDP RPF neighbor for the RP, using the MSDP peer-
          RPF-forwarding rules in the MSDP spec [MSDP].





Fenner, Meyer            Expires September 2000                 [Page 6]


Internet Draft      draft-ietf-msdp-traceroute-00.txt        March, 2000


     5.   This lookup returns a peering.  Insert your IP address on this
          peering into the current hop in the router info table, and
          increment the rtr count field.  Insert the peer's address into
          the Next-Hop Router Address field.

     6.   If the RPF neighbor lookup failed, or if the rtr pointer ==
          max hops, switch to a response and return this packet.  Other-
          wise, unicast the current packet over the MSDP peering to the
          RPF neighbor.

4.2.  Returning partial responses

     Turn the MSDP type from traceroute request to traceroute response.

     Decrement the router pointer.

     If the router pointer was already 0, you're the one who requested
     the trace.

     Otherwise, send the message on your MSDP peering with the router at
     the current router pointer's offset in the router table.


4.3.  Processing a traceroute answer

     Decrement the router pointer.

     If the router pointer was already 0, you're the one who requested
     the trace.

     Otherwise, send the message on your MSDP peering with the router at
     the current router pointer's offset in the router table.


5.  Security Considerations

(flesh these out)

6.  References

RFC2119        Bradner, S., "Key words for use in RFCs to Indicate
               Requirement Levels", RFC 2119/BCP 14, Harvard University,
               March 1997.

MSDP           Farinacci, D., et. al. "Multicast Source Discovery Proto-
               col (MSDP)", draft-ietf-msdp-spec-05.txt, February, 2000.





Fenner, Meyer            Expires September 2000                 [Page 7]


Internet Draft      draft-ietf-msdp-traceroute-00.txt        March, 2000


MTRACE         Fenner, W. and S. Casner, "A "traceroute" facility for IP
               Multicast", draft-ietf-idmr-traceroute-ipm-06.txt, March,
               2000.

7.  Author's Addresses


   William C. Fenner
   AT&T Labs - Research
   75 Willow Rd
   Menlo Park, CA 94025
   Phone: +1 650 330 7893
   Email: fenner@research.att.com

   David Meyer
   Cisco Systems
   170 Tasman Drive
   San Jose, CA, 95134
   Phone: +1 541 915 0094
   Email: dmm@cisco.com































Fenner, Meyer            Expires September 2000                 [Page 8]