Internet Engineering Task Force W. Fenner
INTERNET-DRAFT AT&T Labs - Research
draft-ietf-msdp-traceroute-05.txt D. Meyer
cisco Systems
R. Roberts
Stanford University
March, 2001
Expires September 2001
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.
Fenner, Meyer, Roberts Expires September 2001 [Page 1]
Internet Draft draft-ietf-msdp-traceroute-01.txt March, 2001
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
and/or the authors.
Fenner, Meyer, Roberts Expires September 2001 [Page 2]
Internet Draft draft-ietf-msdp-traceroute-01.txt March, 2001
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 router (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, Roberts Expires September 2001 [Page 3]
Internet Draft draft-ietf-msdp-traceroute-01.txt March, 2001
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, query-type bits, and
the router pointer (for returning packet HBH). Following are two
tables, one for router addresses and the other for fixed-length response
info filled in at each hop. The remainder of the packet is available to
collect more detailed response info as specified by the query-type bit
vector.
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 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Query-type bits |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| skip hops | max hops | reserved | rtr pointer |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... maxhops*4 octets of router addresses ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... maxhops*4 octets of fixed-length response info ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Fenner, Meyer, Roberts Expires September 2001 [Page 4]
Internet Draft draft-ietf-msdp-traceroute-01.txt March, 2001
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. Query-type bits
Bit vector apecifying collection of more detailed response data to
be collected for the hops between skip hops and max hops or until
the packet size is exceeeded.
3.6. skip hops
The number of hops to be skipped in this request before beginning
to collect detailed response data. This allows for the data col-
lection specified by the query-type bit vector to begin at this
point in the path. Specified by the requestor.
3.7. max hops
The max. # of hops requested in this traceroute request.
3.8. reserved
This octet is reserved for future use.
3.9. rtr pointer
The rtr pointer is a pointer into both the router addresses table
and the fixed-length response info 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).
Fenner, Meyer, Roberts Expires September 2001 [Page 5]
Internet Draft draft-ietf-msdp-traceroute-01.txt March, 2001
3.10. router addresses
Table of the outgoing interfaces that this request has traversed.
Inserted by requestor, max hops * 4 octets.
4. fixed-length response info
Table of fixed response words containing limited status info for
each router along the path. Inserted by requestor, max hops * 4
octets.
Fixed response word:
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Peer Uptime | Cache Entry | |D|R|N|C| Return Code |
| | Uptime | | |P|C| | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Peer uptime: RPF peer uptime in minutes, capped at 255.
Cache Entry Uptime: cache entry uptime in minutes, capped at 255.
Bits:
D-bit: set if have this (S,G) in cache but with a different RP.
RP-bit: set if this router is an RP
NC-bit: set if this router is not caching SA's
C-bit: set if this (S,G,RP) tuple is in the cache.
Return Code:
0 No-error
1 Hit-src-RP
2 Filled-packet
3 No-RPF-neighbor
4 Reached-max-hops
Fenner, Meyer, Roberts Expires September 2001 [Page 6]
Internet Draft draft-ietf-msdp-traceroute-01.txt March, 2001
4.1. Detailed response block
Each detailed response block begins with a bit vector describing what
types of responses are present (equal to or a sub-set of the query-type
bits):
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Response Type Bits |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Types of info:
Bit 0: RPF Neighbor info
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Next-Hop Router Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Bit 1: SA info
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 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 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Bit 2: Peer info
Fenner, Meyer, Roberts Expires September 2001 [Page 7]
Internet Draft draft-ietf-msdp-traceroute-01.txt March, 2001
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Peering Uptime |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| # of Peering Resets |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
5. Protocol Processing
5.1. Processing an in-progress traceroute packet
The following steps are taken when receiving an in-progress tracer-
oute:
1. If rtr pointer is greater than max hops, something bad has
happened; immediately process as a partial response.
2. If this router is the source RP, set the Hit-src-RP return
code and the RP-bit in the fixed-length response info word and
store in the fixed-length response info table as offset by rtr
pointer. Proceed to Return packet as a response.
3. If this router is an RP, set the RP-bit in the fixed-length
response info word. If this router is not doing SA caching,
set the NC-bit in the fixed-length response info word and pro-
ceed to the RPF peer check. Otherwise look up the SA cache
information for the (S,G,RP). If the SA cache entry exists,
set the C-bit in the fixed-length response info word and
insert the Cache Entry Uptime field in the fixed-length
response info word. If no SA cache entry exists for the
(S,G,RP), check if there is a cache entry for (S,G) with a
different RP. If so, then set the D-bit in the fixed-length
response info word.
4. Look up the MSDP RPF neighbor for the RP, using the MSDP peer-
RPF-forwarding rules in the MSDP spec [MSDP].
5. If this lookup returns a peering, insert your IP address on
this peering into the router address table as offset by the
current rtr pointer. Insert the Peer Uptime field in the
fixed-length response info word and move it to the fixed-
length response info table as offset by the current rtr
pointer. If all the query-type bits are zero, proceed to For-
ward packet to RPF neighbor. Otherwise proceed to Append
detailed response data.
Fenner, Meyer, Roberts Expires September 2001 [Page 8]
Internet Draft draft-ietf-msdp-traceroute-01.txt March, 2001
6. If the RPF neighbor lookup failed, set the No-RPF-neighbor
return code in the fixed-length response info word and move it
to the fixed-length response info table as offset by the cur-
rent rtr pointer and proceed to Return packet as a response.
5.1.1. Append detailed response data
The detailed response data, as specified by the query-type bits, is
appended to the received packet.
Until rtr pointer is greater than skip hops, do not append detailed
data. If there is a non-zero return code in the fixed-length
response info word, proceed to Return packet as a response other-
wise proceed to Forward packet to RPF neighbor.
Verify that space remains in the packet to add the detailed
response data block(s) as specfied by the query-type bits. If
adding these blocks would cause this packet to exceed the MSDP MTU
(1400 bytes), set the Filled-packet return code in the fixed-length
response info word and move it to the fixed-length response info
table as offset by the current rtr pointer. Proceed to Return
packet as a respose.
Copy the query-type bits to the response type bits word, first of
the detailed response data.
If the Next Hop info query-type bit is set, insert the RPF peer's
address into the Next-Hop Router Address word.
If the SA info query-type bit is set, fill in the SA-info query
words. If no matching SA entry or the router is not caching SAs,
fill words with zeros.,
If the Peer info query-type bit is set, fill in the Peer-info query
words.
5.1.2. Forward packet to RPF neighbor
Increment the rtr pointer field.
If the rtr pointer == max hops, decrement the rtr pointer field,
set the Reached-max-hops return code in the fixed-length response
info word and move it to the fixed-length response info table as
offset by the current rtr pointer. Proceed to Return packet as a
response.
Fenner, Meyer, Roberts Expires September 2001 [Page 9]
Internet Draft draft-ietf-msdp-traceroute-01.txt March, 2001
Otherwise, unicast the current packet over the MSDP peering to the
RPF neighbor.
5.2. Return packet as a response
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 address table.
5.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 address table.
6. Security Considerations
(flesh these out)
7. 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.
MTRACE Fenner, W. and S. Casner, "A "traceroute" facility for IP
Multicast", draft-ietf-idmr-traceroute-ipm-06.txt, March,
2000.
Fenner, Meyer, Roberts Expires September 2001 [Page 10]
Internet Draft draft-ietf-msdp-traceroute-01.txt March, 2001
8. 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
Ronald G. Roberts
Stanford University
241 Panama St
Pine Hall Room 175
Stanford, CA 94305-4122
Phone: +1 650 723 3352
Email: rgr@stanford.edu
Fenner, Meyer, Roberts Expires September 2001 [Page 11]