Internet Draft Harikishan Desineni Document:draft-kishan-lsp-btrace-04.txt Kameswararao Avasarala Expires: April 2003 Ericsson October 2002 Backtrace Messages for Label Switched Paths draft-kishan-lsp-btrace-04.txt 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 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 and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or cite them other than as "work in progress". The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/lid-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html This document is an individual submission to the IETF. Comments should be directed to the authors. Abstract Label switched path (LSP) backtrace is a method to backtrack the paths followed by packets in a particular multi protocol label switching (MPLS) forwarding equivalence class (FEC). This document describes encoding and procedures for new label distribution protocol (LDP) messages, backtrace message and backtrace reply message used for performing LSP backtrace. Backtrace message is sent upstream for an established LSP. Backtrace message can be used for LDP LSPs as well as for constraint based label switched paths (CR-LSPs). Data requested through backtrace message is encoded into backtrace reply message. Backtrace reply message is sent in downstream direction. It Harikishan, et. al. [Page 1] Internet Draft Backtrace Messages for Label Switched Paths July 2002 always travels towards the tail end of an LSP. Backtrace mechanism described in this document can also be used for obtaining additional attributes of LSPs. TABLE OF CONTENTS 1. Introduction...............................................2 2. Terminology ...............................................4 3. New Messages ..............................................5 4. LDP Message Structure Overview ............................5 5. Behavior of LSRs with constraints in handling the backtrace message ...................................................6 6. Backtrace message .........................................8 6.1 Backtrace message encoding ................................8 6.2 Backtrace message procedures...............................9 7. Backtrace reply message ..................................10 7.1 Backtrace reply message encoding .........................10 7.2 Backtrace reply message procedures .......................12 8. TLVs .....................................................13 8.1 Query TLV extensions .....................................13 8.2 Tree TLV .................................................14 8.3 Ingress Flags TLV ........................................14 8.4 Reserved Bandwidth TLV ...................................15 8.5 Aggregation TLV ..........................................16 8.6 Notification message handling ............................17 9 Security Considerations...................................17 10 IANA Considerations.......................................18 11 Acknowledgements..........................................18 12 Normative References......................................18 13 Informative References....................................18 14 Author's Addresses........................................19 1. Introduction This document describes a backtrace mechanism for label switched path (LSP) or constraint based label switched path (CR-LSP). It specifies procedures and encoding for new backtrace messages added to label distribution protocol (LDP) [LDP] for backtracking an LSP in multi protocol label switching (MPLS) [MPLS] domain. Extensions to RSVP-TE [RSVP-TE] to provide the same functionality are subject for future study and will be covered in future draft versions. Backtrace mechanism described in this document can also be used for obtaining additional attributes of an LSP. Examples of additional LSP attributes include bandwidth allocated for an LSP at an intermediate LSR, outgoing label allocated for an LSP at an intermediate LSR, forwarding equivalence class (FEC) aggregation occurring along an LSP. The following example describes the way backtrace mechanism works. Harikishan, et. al. [Page 2] Internet Draft Backtrace Messages for Label Switched Paths July 2002 Consider a MPLS domain with six nodes and six links captured as a graph in the below shown diagram. [R2] |f | [R5] a / \e / \ [R1]---[R4] \ / b \ /d [R6] |c | [R3] Figure 1 Nodes R1,R2,R3 and R4 are the edge Label Switched Routers (LSRs) of the MPLS domain. Let R4 be the egress for FEC "F". Assume that there exists following LSPs in the MPLS domain for the FEC "F". Assume that R5,R6 are merge capable. LSP for FEC "F" from R1 to R4 is L1 = {R1,a,R5,e,R4} LSP for FEC "F" from R2 to R4 is L2 = {R2,f,R5,e,R4} LSP for FEC "F" from R3 to R4 is L3 = {R3,c,R6,d,R4} R5 has merged L1 and L2. Triggering LSP backtrace from R4 should result in the following LSP tree rooted at LSR R4. [R1] \a \ [R5] / \e /f \ [R2] [R4] / / d / [R6] / /c [R3] Harikishan, et. al. [Page 3] Internet Draft Backtrace Messages for Label Switched Paths July 2002 Figure 2 To perform the construction of LSP tree, we introduce backtrace and backtrace reply messages in LDP. Egress LSR R4 sends backtrace messages to R6 and R5. LSR R5 in turn propagates the backtrace message to R1 and R2. At R6,backtrace message is propagated to R3. As R1,R2 and R3 are ingresses for FEC "F", they respond with backtrace reply message. Backtrace reply message from each LSR includes the sub tree originating from it, representing the set of LSPs merging at it for FEC "F". R5 collects the sub trees in the backtrace replies from R1,R2,appends its own information, builds the new sub tree with root being itself and sends the new subtree in a new backtrace reply message to R4. R6 receives the backtrace reply from R3,appends its own information, builds the new sub tree with root being itself and sends the new sub tree in a new backtrace reply message to R4. R4 collets the sub trees in the backtrace replies from R5,R6 and builds a complete LSP tree for FEC "F" with root being itself. Above mechanism builds LSP tree rooted at an LSR acting as egress for a FEC in the MPLS domain. It is also possible to append additional information to backtrace reply message at each LSR. Additional information could include details such as bandwidth allocated for an LSP over a particular link, labels used along the LSP, merging capabilities of an LSR (VP, VC, VP and VC merges in case of MPLS over ATM) and any other type of information which can be useful for MPLS network management. Though the egress LSR is treated as a node of choice for triggering LSP backtrace, this mechanism can also be performed from any LSR acting as intermediate LSR for an LSP. LSP backtrace should be able to obtain as much information as possible from LSRs in MPLS domain. If an LSR cannot propagate the backtrace message upstream, it may respond with a backtrace reply message with additional information stating that it is not an ingress for the FEC. Some LSRs may act as both intermediate and ingress LSR for a FEC. Backtrace reply message traverses the exact reverse path followed by backtrace message and collects information at the same LSP level as traversed by backtrace message. Backtracing at an LSP level different from the level at which the backtrace message is issued is a subject for further study and is beyond the scope of this document. 2. Terminology true ingress LSR An LSR which acts only as an ingress LSR for an LSP and is not acting as intermediate LSR for the same LSP. 3. New Messages Harikishan, et. al. [Page 4] Internet Draft Backtrace Messages for Label Switched Paths July 2002 New LDP messages introduced for supporting backtrace are backtrace message and backtrace reply message. The following new TLVs are added to accommodate the encoding for the backtrace and backtrace reply messages: - tree TLV - ingress flags TLV - reserved bandwidth TLV - aggregation TLV LDP uses the TCP transport for session, advertisement and notification messages; i.e., for everything but the UDP based discovery mechanism. The messages, which are added to support backtrace mechanism, are sent over TCP as well. 4. LDP Message Structure Overview As described in LDP Specification draft [LDP], all LDP messages have the following format: U bit Unknown message bit. Upon receipt of an unknown message, if U is clear(=0), a notification is returned to the message originator; if U is set(=1), the unknown message is silently ignored. Message Type Identifies the type of message Message Length Specifies the cumulative length in octets of the Message ID, Mandatory Parameters, and Optional Parameters. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |U| Message Type | Message Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Message ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + + | Mandatory Parameters | + + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + + | Optional Parameters | + + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Harikishan, et. al. [Page 5] Internet Draft Backtrace Messages for Label Switched Paths July 2002 Message ID 32-bit value used to identify this message. Used by the sending LSR to facilitate identifying notification messages that may apply to this message. An LSR sending a notification message in response to this message should include this Message Id in the Status TLV carried by the notification message. Mandatory Parameters Variable length set of required message parameters. Some messages have no required parameters. For messages that have required parameters, the required parameters must appear in the order specified by the individual message specifications in the sections that follow. Optional Parameters Variable length set of optional message parameters. Many messages have no optional parameters. For messages that have optional parameters, the optional parameters may appear in any order. 5. Behavior of LSRs with constraints in handling the backtrace message Upon receiving a backtrace message, an LSR has to behave according to its configuration constraints in handling the backtrace message and returning information requested in the backtrace message. The following cases were identified: - The LSR does not support the code to handle the messages for backtrace mechanism. In this case, the LSR has to behave as if it received an unknown message type. It has therefore to honor the U bit. - The LSR supports the code to handle the messages for backtrace mechanism, but it is configured not to return any data. In this case, the LSR is able to decode and process backtrace messages. However, it is configured to hide all the data. It should not propagate the message to the upstream LSP peers. - The LSR supports the code to handle the messages for backtrace mechanism, but it is configured not to return part of the requested data. In this case, the LSR is able to decode and process backtrace messages. It has to propagate backtrace reply message. In the backtrace reply message, it has to encode values for the data types that it is willing to return and zero length TLVs for values for the data that is hidden. Harikishan, et. al. [Page 6] Internet Draft Backtrace Messages for Label Switched Paths July 2002 Note: Zero length TLV encoding can be used for all types of requested information except the merge information, true ingress LSR information and tree TLV information. When an LSR is configured to hide its sibling information(information about upstream LSRs for the given FEC),it has to encode sibling count (number of upstream LSRs) for the given FEC as 255 in tree TLV. For more information on tree TLV, see the section 8.2 "Tree TLV". For more information on true ingress LSR information see the section 8.3 "Ingress Flags TLV". - The LSR supports the code to handle the messages for backtrace mechanism, and it is configured to return all the data, which is requested in the backtrace message. This is the normal case for an LSR. In this case, the behavior of LSR has to follow the backtrace and backtrace reply procedures described in the following sections. The decision that an LSR can share the information requested in backtrace message has to be controlled through local configuration. 6. Backtrace Message This section describes the backtrace message and its encoding and procedures. This message is meant to gather information about an LSP tree (multipoint to point LSP) for a FEC. It can be sent at any time for an established LSP. The backtrace message can be used to gather information about: -Paths, which form the LSP tree of the FEC. -Labels used along the paths forming the LSP tree. -Information about which LSRs are acting as merging points in the LSP tree. -Reserved bandwidth for LSPs forming the LSP tree. -Information about FEC aggregation occurring at LSRs in the LSP tree. -Anything that is needed in future for MPLS network management, which can be computed and encoded in a TLV. The information requested in the backtrace message is encoded in the backtrace reply message, which is sent downstream, as a response to the backtrace message. Harikishan, et. al. [Page 7] Internet Draft Backtrace Messages for Label Switched Paths July 2002 6.1. Backtrace message encoding The encoding for the backtrace message is: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0| Backtrace type TBD IANA | Message Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Message ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | FEC TLV | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Query TLV | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Hop Count TLV | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Optional Parameters | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Message ID 32-bit value used to identify this message. FEC TLV The FEC TLV must include only one FEC element corresponding to the LSP being backtracked. Query TLV What to query. This TLV is used to request additional information about LSPs in the resulting LSP tree. See [QUERY] for Query TLV encoding. Also see section 8.1 "Query TLV extensions". Hop Count TLV Specifies the number of hops that can still be traversed before the message is dropped. It is initialized to the maximum value of 255 (or the configured value, if any). Every LSR that receives the backtrace message has to subtract one from the hop count value. The backtrace message should be dropped if the hop count value becomes zero. Optional Parameters No optional parameters are defined at present for this message. 6.2. Backtrace Message Procedures This message is always propagated in upstream direction. The egress LSR initiates the backtrace message. It populates the query TLV parameters according to what kind of information it wants to gather. Backtrace for an LSP is done by its FEC. Upon receiving a backtrace Harikishan, et. al. [Page 8] Internet Draft Backtrace Messages for Label Switched Paths July 2002 message, an LSR decodes the FEC and finds the outgoing label to identify the LSP is being backtracked. If it cannot find the outgoing label, it sends downstream a notification message with status set to "No LSP to backtrace". Otherwise, it finds the incoming set of labels, which are merged into the found outgoing label. The LSR computes the upstream LDP peer set "S", containing LDP peers corresponding to each incoming label in the incoming label set. It computes another set "P", which is a subset of "S" containing only the upstream LSRs, which were advertised label binding for a FEC, which in turn either subsumes or is subsumed by the FEC received in the backtrace message. It is not mandatory to compute "S", before computing "P". Implementations may compute "P" without computing "S". After computing the upstream LSR peer set "P", the LSR propagates the backtrace message to all the members of set "P" computed as described in the above paragraph. Sometimes it may be necessary to send more than one backtrace message to the same upstream LDP peer in the set "P". This situation arises when an LSR advertises several FEC-label bindings to an upstream peer, where each of the advertised FECs may either subsume or be subsumed by the FEC received in backtrace request. It also arises with a non merging LSR, which has advertised multiple labels for the same FEC to the same upstream LSR. A mechanism to find the upstream LDP peer for an incoming label can be found in [LDP-STATE]. When the backtrace request message gets to an LSP tunnel, it has to be propagated to the upstream LDP peer at the same LSP level. It means that the backtrace request message must never be propagated to LDP peers at an LSP level different from the LSP level at which it was received. Upon receiving the backtrace message, the ingress LSR has to respond with a backtrace reply message. The backtrace reply message contains the query TLV, which was received in the backtrace message. The query TLV tells the LSRs along the path which information is being requested and allows intermediate LSRs to piggy back their own information on the backtrace reply message. 7. Backtrace Reply Message This message is propagated downstream. It is sent in response to a backtrace message. The egress LSR, which initiated the backtrace message, is interested in gathering information from all the nodes in the LSP tree for the FEC. However, there are situations in which the backtrace message does not reach all the ingress LSRs for the FEC being backtraced. In these scenarios it would be useful if the egress LSR gathered at least some information about the LSRs, which are along the path, up to the one that failed. If the backtrace reply message is full, TCP will take care of it by segmenting and reassembling the message. Backtrace reply message is described in the following sections. Harikishan, et. al. [Page 9] Internet Draft Backtrace Messages for Label Switched Paths July 2002 7.1. Backtrace reply message encoding This message can be generated by any LSR along the LSP tree. It is sent downstream, by each LSR along the path. The encoding for the backtrace reply message is: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0|Backtrace Reply Type TBD IANA| Message Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Message ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Query TLV | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Message Id TLV | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Tree TLV | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Optional Parameters | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Message ID 32-bit value used to identify this message. Query TLV What was queried? See [QUERY] for TLV encoding and section 8.1 "Query TLV extensions". Message Id TLV The value of this parameter is the message id of the corresponding backtrace message. Optional Parameters This variable length field contains zero or more parameters, each encoded as a TLV. The optional parameters are: Optional Parameter Length Value Query Label TLV var See [QUERY] Query Merge Flags TLV var See [QUERY] Ingress Flags TLV var See Section 8.3 Reserved Bandwidth TLV var See Section 8.4 Aggregation TLV var See Section 8.5 For simplicity we reuse here TLV types defined in [QUERY]. They are: - Query Label TLV (see [QUERY]) - Query Merge Flags TLV (see [QUERY]) Harikishan, et. al. [Page 10] Internet Draft Backtrace Messages for Label Switched Paths July 2002 Query label TLV contains a list of generalized label TLVs. The query label TLVs received from upstream LSRs are concatenated in the same sequence as the tree TLVs. If Q2 bit is set in the query flags and if the LSR is configured to reveal the label information, it should add outgoing label to the query label TLV resulting after the concatenation of query label TLVs received from upstream LSRs and update the length field. If an LSR is configured to hide the label information, a zero length TLV has to be encoded. Query merge flags TLVs received from upstream LSRs are concatenated in the same sequence as the tree TLVs. If Q4 bit is set in the query flags the LSR should add merge flags to the query merge flags TLV resulting after the concatenation of query merge flags TLVs received from upstream LSRs. Then it has to update the length field and increment the number of merge flags field. Ingress flags TLV is a list of pair of bits. It informs whether the LSR acts as an ingress or intermediate or both for the LSP. It has variable length and every two bits in the mask will correspond to an LSR along the LSP tree. Its length is rounded up to the next byte. Ingress flags TLVs received from upstream LSRs are concatenated in the same sequence as the tree TLVs. If Q7 bit is set in the query flags, the LSR should add ingress flags to the ingress flags TLV resulting after the concatenation of ingress flags TLVs received from upstream LSRs. Then it has to update the length field and increment the number of LSRs field. Reserved bandwidth TLV informs the bandwidth allocated for the LSP over the out bound link. Reserved bandwidth TLVs received from upstream LSRs are concatenated in the same sequence as the tree TLVs. If Q5 is set in query TLV, every LSR along the LSP tree will have to fill this information, if it is configured to reveal such information. If an LSR is configured to hide the bandwidth information, a zero length TLV has to be encoded. For more information on this TLV, see section 8.4 "Reserved Bandwidth TLV". Aggregation TLV informs the FEC aggregation occurring along the paths in the LSP tree. Aggregation TLVs received from upstream LSRs are concatenated in the same sequence as the tree TLVs. If Q6 flag is set in aggregation TLV, every LSR along the LSP tree will have to fill this information, if it is configured to reveal such information. If the LSR is performing FEC aggregation, the encoded information includes a FEC, which either subsumes or subsumed by the FEC encoded in the corresponding backtrace message. Zero length TLV concept is not applicable to aggregation TLV. For more information on this TLV, see section 8.5 "Aggregation TLV". The information encoded in the above TLVs by each LSR, should be relatively in the same location as the LSR's IP address information Harikishan, et. al. [Page 11] Internet Draft Backtrace Messages for Label Switched Paths July 2002 encoded in tree TLV. Each TLV size grows as the backtrace reply message propagates towards egress. 7.2. Backtrace Reply Message Procedures A backtrace reply message can be generated by any LSR, which receives a backtrace message, if the LSR is able to identify an LSP for the FEC received. If the node is not able to identify the FEC, it replies with a notification message with status set to "No LSP to backtrace". If the node is true ingress LSR for the LSP, it can immediately send the backtrace reply to the downstream LSP peer. If the node is not the ingress of the LSP, it waits for the responses from LSRs in the upstream LDP peer(siblings)set "P", computed as described in section 6.2. The timeout period for the responses from upstream LDP peers is implementation dependent and should be locally configurable. Once the timeout period expires, the LSR should generate a backtrace reply with the information it has gathered from the upstream LDP peers, which have responded within the timeout interval. The gathered LSP sub tree information is encoded as tree TLV in backtrace reply message sent downstream. Responses received after timeout interval should be ignored. The LSR need not wait until the entire timeout period elapses, if it receives responses from all LDP peers in set "P" before the local timer expires. If the node is not able to propagate the backtrace message to all upstream LDP peers in set "P", it should immediately respond with a backtrace reply message with its own information. This information must state that this node is not a true ingress LSR for the FEC received in backtrace message. This is informed through ingress flags TLV in the backtrace reply message. For more details about the ingress flags TLV see section 8.3 "Ingress Flags TLV". Each LSR has to encode a message Id TLV into the backtrace reply message. The mapping between a backtrace message and a backtrace reply message is done based on the message id. Besides the message Id TLV, each LSR has to encode the information that was requested (bandwidth, merging info, ingress or intermediate LSR, aggregation info, etc.,). After the encoding is done, the backtrace reply message is sent downstream towards the egress LSR. Every LSR along the LSP tree has to encode its information according to what query flags are set. The backtrace response must follow the exact reverse path and same LSP level traversed by backtrace message. 8. TLVs 8.1. Query TLV extensions. Harikishan, et. al. [Page 12] Internet Draft Backtrace Messages for Label Switched Paths July 2002 The query TLV travels in the backtrace message till it reaches the ingress or an LSR, which cannot forward the backtrace message further upstream. It then gets copied into a reverse flowing backtrace reply message and is used by ingress and intermediate LSRs to know what information is requested in the backtrace message. The following section describes the extensions to the query TLV introduced in [QUERY]. For the purpose of collecting allocated bandwidth and ingress information in the LSP tree, we introduce two new flags Q5 and Q7. Flag Q6 is introduced to collect FEC aggregation information. Q5,Q6 and Q7 are reserved flags in [QUERY]. Flags Q2,Q4 are reused from [QUERY]. - Q5: Query the bandwidth; if set, the LSR that receives the backtrace message has to encode the bandwidth allocated over the outbound link for the LSP. For details about reserved bandwidth see section 8.4 "Reserved Bandwidth TLV". - Q6: Query FEC aggregation information. For details about FEC aggregation see section 8.5 "Aggregation TLV". - Q7: Query which LSRs in the LSP tree act as ingresses for the FEC received in backtrace message. For details about ingress information see section 8.3 "Ingress Flags TLV". 8.2. Tree TLV The format for the tree TLV is: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0|0| Tree TLV Type TBD IANA | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Address Family | IP Address .... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Sibling Count | Subûtree 1 .... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sub-tree 2 ...... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Address Family Address family of the following IP addresses in the TLV. IP Address IP V4/V6 address of the LSR. Sibling Count Total number siblings for the present node in the LSP tree. Harikishan, et. al. [Page 13] Internet Draft Backtrace Messages for Label Switched Paths July 2002 Sub-tree 1/2 Another sequence of IP address, sibling count and a tree TLV value field. The value field of tree TLV is a recursive structure capturing a tree. Each LSR encodes IP address followed by the sibling count. LSR IP Address is the router id of the LSR. The LSR's outbound port IP address for the LSP can also be used for encoding the LSR's IP address in the TLV. Sibling count indicates the total number of sub trees originating from the present node. Sibling count is 8 bit value with range from 0 to 255. Value 255 is reserved. It is used to inform that the LSR is not willing to reveal the sibling count. Sub tree information follows the sibling count field. For example, we show the formation of the LSP tree shown in figure 2 in section 1. The tree TLV encoded by R1 will have the value field { R1, 0 } The tree TLV encoded by R2 will have the value field { R2, 0 } The tree TLV encoded by R3 will have the value field { R3, 0 } R5 will extract the tree TLVs in backtrace replies received from R1, R2,concatenate them and add it's own information to form a new tree TLV with value field {R5, 2, R1, 0, r2, 0}. R6 will extract the tree TLV from the backtrace reply received from R3 and form a new tree TLV with value field {R6, 1, R3, 0}. R4 will extract the tree TLVs from the backtrace replies received from R5,R6, concatenate them and add it's own information to form a new tree TLV with value set to { R4, 2, R5, 2, R1, 0 , R2, 0, R6, 1, R3, 0 }. As the backtrace reply message traverses, the tree structure gets encoded in depth first order. The order of concatenation of the upstream tree TLVs is irrelevant. The concatenation of other upstream TLVs must match the order followed while concatenating the upstream tree TLVs. The leaf nodes in the tree will have zero sibling count. The leaf nodes are most likely the ingress LSRs of the LSP. Whether a node in the tree is true ingress LSR or not can be found from the ingress flags TLV. The details of ingress TLV are present in the following section. 8.3. Ingress Flags TLV The format for the ingress flags TLV is: Harikishan, et. al. [Page 14] Internet Draft Backtrace Messages for Label Switched Paths July 2002 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0|0| Ingress Flags TLV TBD IANA| Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Number of LSRS | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Ingress flags | | | ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The ingress flags TLV has 4 bytes field to store the number of LSRs in the LSP tree. This number is same as the number of LSR IP addresses, which are encoded in the Tree TLV. Each two bits in the ingress flags field represent the ingress information for an LSR. The bits are set to 01 if the LSR is true ingress LSR for the backtracked LSP. It is set to 10 if the LSR acts as an intermediate LSR for the LSP. It is set to 11 if the LSR can act as both ingress and intermediate LSR for the LSP. If the LSR wants to hide the ingress information, it has to set the ingress flags to 00. The length of the encoding is rounded up to the next byte. Every LSR has to update the number of LSRs field and set its corresponding bits accordingly. The ingress information of the LSRs is encoded in the same order as the LSR IP addresses in the tree TLV. 8.4. Reserved Bandwidth TLV The format for the reserved bandwidth TLV is: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0|0|Rsvd Bandwidth TLV TBD IANA| Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LSP ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |HOLDINGPRIORITY| Bandwidth Allocated (IEEE float) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | Address family |IP address of +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | interface (near end) ..... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ IP address of interface (far end) ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Optional parameters | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Harikishan, et. al. [Page 15] Internet Draft Backtrace Messages for Label Switched Paths July 2002 LSP ID LSP ID of the backtraced CR-LSP. Holding Priority Holding priority of the CR-LSP Bandwidth Allocated Bandwidth allocated over the outbound link of the CR-LSP in bytes per second.(these units are unidirectional bytes per second) Address Family Address family of the following two IP addresses in the TLV. Finally the interfaceÆs IP address and far end's IP address are placed in the TLV. For example if the first address is A (near end) and the second address is B (far end), the bandwidth is reserved in the A to B direction. The LSRs along the LSP tree append their reserved bandwidth information to the backtrace reply message. The elements of this TLV are encoded in the same order as the IP addresses of the LSRs in the tree TLV. For example assume that the tree TLV {R1, 2, S1, 0, S2, 0} has the reserved bandwidth vector {10, 100}. This indicates that 10 is the bandwidth unit reserved on link between R1 and (root of)S1, 100 is the bandwidth unit reserved on the link between R1 and(root of)S2. The IP addresses on each side of the link and hold priority of the LSP can be obtained by decoding individual elements of the received bandwidth TLV. Optional Parameters: No optional parameters are defined at present. 8.5. Aggregation TLV The format for aggregation TLV is: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0|0| Aggregation TLV TBD IANA | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Number of LSRs | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Aggregation Element 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | | ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Aggregation Element n | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Harikishan, et. al. [Page 16] Internet Draft Backtrace Messages for Label Switched Paths July 2002 The aggregation TLV is a list of aggregation elements. The order of the LSR aggregation elements matches the order of LSR IP addresses in tree TLV. The aggregation TLV has 4 bytes field to store the number of LSRs in the LSP tree. This number is same as the number of LSR IP addresses, which are encoded in the tree TLV. The length of this TLV encoding is rounded up to the next byte. Aggregation element is encoded as below. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | FEC Element ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ First two bits in aggregate element represent the aggregation information for an LSR. The bits are set to 01 if the LSR is performing aggregation and are set to 10 otherwise. If the LSR wants to hide the aggregation information, it has to set these bits to 00. These two bits are followed by FEC element. FEC element will not be present if the aggregation bits are set to 10 or 00. For more details about FEC element encoding see [LDP]. 8.6. Notification message Handling When a notification message with status ôNo LSP to backtraceö is received from a LDP peer, as response to the backtrace message, the LSR has to stop waiting for backtrace reply from that peer LSR. Status code summary Status Code E Status Data Section Title No LSP to backtrace 1 TBD IANA "Backtrace Message procedures.." 9. Security Considerations The backtrace mechanism inherits the same security mechanism described in Section 5 of [LDP]. The backtrace mechanism provides an additional security measure for cases when a node cannot share the information being requested by backtrace message. Such nodes have the option of hiding their information, if their configuration requires it. Please refer to Section 5 of this document - "Behavior of LSRs with constraints in handling the backtrace message" for more details. Harikishan, et. al. [Page 17] Internet Draft Backtrace Messages for Label Switched Paths July 2002 10. IANA Considerations The backtrace mechanism does not require a new message type space, a TLV type space or a status code space. Extensions to the LDP spaces are required, as follows: - the message types for backtrace message, backtrace reply message should be provided by extending the LDP message type space. - the TLV types for tree TLV, ingress Flags TLV, reserved bandwidth TLV and aggregation TLV should be provided by extending the LDP TLV type space. - the status code "No LSP to backtrace" should be provided by extending the LDP status code space. 11. Acknowledgements The authors would like to acknowledge Srinivas Chilakalapudi, Chandrasen Gunda, Venkat Rapaka, Michael Zdan, Anil Gunturu and Amitabha Sen. 12. Normative References [MPLS] Rosen E., Viswanathan A., "Multiprotocl Label Switching Architecture", RFC3031, January 2001. [CR-LDP] Jamoussi et al., "Constraint-Based LSP Setup using LDP", RFC3212, January 2002. [LDP] Andersson et al., "LDP Specification",RFC3036, January 2001. [QUERY] Peter Ashwood-Smith et al., "MPLS LDP Query Message description", Work in Progress, draft-ietf-mpls-lsp-query-04.txt. [LDP-STATE] Christophe Boscher et al., "LDP State Machine",RFC3215, January 2002 [OPTICAL] Ashwood-Smith P., Berger L., "Generalized MPLS-Signaling Functional Description", draft-ietf-mpls-generalized-mpls-signaling- 09.txt, November 2001,Work in progress. 13. Informative References [RSVP-TE] Awduche et al., "RSVP-TE: Extensions to RSVP for LSP Tunnels",RFC3209, December 2001. Harikishan, et. al. [Page 18] Internet Draft Backtrace Messages for Label Switched Paths July 2002 14. Author's Addresses Hari Kishan Desineni, KameswaraRao Avasarala, Ericsson,70,Castiian Drive, Ericsson,70,Castiian Drive, Santa Barbara, California Santa Barbara, California USA-93117 USA-93117 Phone: +1 805 252 2641 Phone: +1 805 562 6212 Email: desineni@hotmail.com Email: avasaralak@yahoo.com Harikishan, et. al. [Page 19]