Internet Draft Harikishan Desineni Document:draft-kishan-lsp-btrace-01.txt Kameswararao Avasarala Expires: November 2002 Ericsson May 2002 LSP backtrace using MPLS-LDP/CR-LDP draft-kishan-lsp-btrace-01.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 This document describes the encoding and procedures for new LDP messages, the back trace message and back trace reply message. The back trace message is sent for an established LSP. The back trace message can be used for LDP LSPs as well as for CR-LSPs. The data requested is encoded into the back trace reply message. TABLE OF CONTENTS 1. Introduction...............................................2 Harikishan, et. al. [Page 1] Internet Draft LSP Back trace using MPLS-LDP/CR-LDP May 2002 2. Terminology ...............................................4 3. New Messages ..............................................4 4. LDP Message Structure Overview ............................4 5. Behavior of LSRs with constraints in handling the backtrace message ...................................................5 6. BackTrace Message .........................................7 6.1 BackTrace message encoding ................................8 6.2 BackTrace Message procedures...............................8 7. Backtrace Reply Message ...................................9 7.1 Backtrace reply message encoding ..........................9 7.2 BackTrace Reply Message Procedures .......................11 8. TLVs .....................................................12 8.1 Query TLV extensions .....................................12 8.2 Tree TLV .................................................13 8.3 Ingress Flags TLV ........................................13 8.4 Reserved Bandwidth TLV ...................................14 8.5 Aggregation TLV ..........................................15 8.6 Notification message Handling ............................16 9. Authors Addresses .........................................16 10. References ...............................................16 1. Introduction This draft describes the backtrace mechanism for an LSP or CR-LSP. It specifies procedures and encoding for the new messages added for the backtrace mechanism. Extensions to 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 draft can be used for obtaining the MPLS topology information for a particular FEC in a MPLS domain. The following example describes the way backtracing mechanism works. 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] Harikishan, et. al. [Page 2] Internet Draft LSP Back trace using MPLS-LDP/CR-LDP May 2002 Nodes R1,R2,R3 and R4 are the edge 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 R4. [R1] \a \ [R5] / \e /f \ [R2] [R4] / / d / [R6] / /c [R3] To perform the construction of LSP tree, we introduce LSP back trace and backtrace reply messages in MPLS-LDP. The egress LSR R4 sends backtrace messages to R6 and R5.LSR R5 in turn propagates the backtrace message to R1 and R2.At R6,the backtrace message is propagated to R3. As R1,R2 and R3 are ingresses for FEC "F", they respond with backtrace reply message. The 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 backtrace replies from LSR 1, LSR 2, appends its own information, builds the new sub tree with root being it self and sends new backtrace response to R4. R6 receives the backtrace response from R3,appends its own information, builds the new sub tree with root being it self and sends a new backtrace response to R4. R4 collets the sub trees in the backtrace replies from R5,R6 and builds the complete LSP Tree for FEC "F" with root being it self. The above mechanism builds LSP tree rooted at an LSR acting as egress for an FEC in the MPLS domain. It is also possible to append additional information to the LSP backtrace message at each LSR. Additional information could include details such as bandwidth allocated for the LSP over the particular link, amount of unreserved bandwidth on the link, labels used along the LSP, merging capabilities of the LSR (VP, VC, VP and VC merges in case of MPLS over ATM), availability of label resources 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 the LSP Backtrace, this mechanism can also be performed from any node acting as intermediate LSR for a FEC. LSP backtrace should be able to obtain as much information as possible from the LSRs in the MPLS Harikishan, et. al. [Page 3] Internet Draft LSP Back trace using MPLS-LDP/CR-LDP May 2002 domain. If a 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. The backtrace response message traverses the exact reverse path of the backtrace message and collects information at the same LSP level traversed by backtrace message. Backtracing LSPs at a 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 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 RFC2119. This section gives a general conceptual overview of the terms used in this document. Some of these terms are more precisely defined in later sections of the document. LSP Backtrace A method to identify the label switched paths at one level of the hierarchy followed by packets in a particular FEC. TRUE Ingress LSR An LSR which acts only as an Ingress LSR for a FEC and is not acting as intermediate LSR for the same FEC. 3. New Messages The 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 the backtrace mechanism, are sent over TCP as well. 4. LDP Message Structure Overview As described in LDP Specification draft, all LDP messages have the following format: U bit Harikishan, et. al. [Page 4] Internet Draft LSP Back trace using MPLS-LDP/CR-LDP May 2002 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 | + + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 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. Harikishan, et. al. [Page 5] Internet Draft LSP Back trace using MPLS-LDP/CR-LDP May 2002 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 the queried information. The following cases were identified: - The LSR does not support the code to handle the messages for the 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 the backtrace mechanism, but it is configured not to return any data. In this case, the LSR is able to decode and process the backtrace messages. However, it is configured to hide all the data. It should propagate the message to the upstream LSP peers. When backtrace reply message is received from upstream, the LSR is requested to propagate the reply message downstream after it encodes the zero- length TLVs for the queried data. When the egress or the LSR which initiated the backtrace request receives backtrace reply, it can identify which TLVs are empty; it can therefore ignore the zero length TLVs and process the rest of the data. Note: Zero length TLV encoding can be used for all types of queried information except the merge information, True Ingress information and LSP root node information in the Tree TLV. For more information on Tree TLV, see the section on "Tree TLV". For more information on true ingress information see the section "True Ingress Flags TLV". For more information about merge flags information see [QUERY]. - The LSR supports the code to handle the messages for the backtrace mechanism, but it is configured not to return part of the queried data. In this case, the LSR is able to decode and process the backtrace messages. It has to propagate the 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. Note: Zero length TLV encoding can be used for all types of queried information except the merge information, True Ingress information and LSP root node information in the Tree TLV. When a 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 Harikishan, et. al. [Page 6] Internet Draft LSP Back trace using MPLS-LDP/CR-LDP May 2002 more information on Tree TLV, see the section on "Tree TLV". For more information on true ingress information see the section "Ingress Flags TLV". For more information about ingress flags information see section "Ingress Flags TLV". - The LSR supports the code to handle the messages for the backtrace mechanism, and it is configured to return all the data, which is queried. 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 backtrace information 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 for a FEC. It can be sent at any time for an established LSP. The backtrace message can be used to gather information about: - LSRs, which form the LSP-Tree of a FEC. - Labels used along the LSP-Tree. - Information about which LSRs are merging points in the LSP tree. - Unreserved bandwidth (as described in [TOPOLOGY])along LSPs forming the LSP Tree. - Allocated bandwidth for LSPs forming the LSP-Tree.(This will be useful for MPLS network monitoring purpose). See "Reserved Bandwidth TLV" section. - 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 backtrace information is encoded in the backtrace reply message, which is sent back downstream, as a response to the backtrace message. Harikishan, et. al. [Page 7] Internet Draft LSP Back trace using MPLS-LDP/CR-LDP May 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 (TBA) | 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 FEC being backtraced. Query TLV What to query. This TLV is used to query additional information about LSPs in the LSP-Tree. See [QUERY] for Query TLV for encoding. Also see "Query TLV extensions" section. Hop Count TLV Specifies the number of LSR hops that can still be traversed before the message is dropped. It is initialized to the max 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 Query 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 The LSR Egress initiates the backtrace message. It populates the Query TLV Parameters according to what kind of information it wants to gather. Backtrace for a LSP is done by its FEC. Upon receiving a backtrace Message, an LSR decodes the FEC and finds the out going label to identify the LSP is being backtraced. If it cannot find the Harikishan, et. al. [Page 8] Internet Draft LSP Back trace using MPLS-LDP/CR-LDP May 2002 LSP, it sends back a Notification message with "No LSP to backtrace" status. Otherwise, it finds the in coming set of labels, which are merged into the already found out going label. Then the LSR computes the upstream LSR peer set "S", containing a LDP peer corresponding to each incoming label in the incoming label set. Then it computes another set "P", which is a subset of "S" containing only the upstream LSRs, which were advertised a label binding for a FEC, which in turn either subsumes the FEC received in the backtrace message or is subsumed by the FEC in the backtrace message. After computing the upstream LSR peer set "P", the LSR propagates the backtrace request 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 request to the same member of the set "P". This situation arises when a 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. A mechanism to find the upstream peer for an incoming label can be found in [LDP-STATE]. When the backtrace request message gets to a tunnel, it has to be propagated to the upstream LSP peer at the same LSP level. I.e., the backtrace request message should never be propagated to LSP peers at a 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 queried and allows intermediate LSRs to piggy back their own queried information on the backtrace reply message. 7. Backtrace Reply Message This message is propagated downstream. It is sent in response to a backtrace request message. The egress, 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. 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. Harikishan, et. al. [Page 9] Internet Draft LSP Back trace using MPLS-LDP/CR-LDP May 2002 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 (TBA) | Message Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Message ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Query TLV | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | MessageId 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 "Query TLV extensions" section. Message Id TLV The value of this parameter is the message id of the corresponding Query message. Optional Parameters This variable length field contains 0 or more parameters, each Encoded as a TLV. The optional parameters are: Optional Parameter Length Value Query Label TLV var See [QUERY] IPV4/6 specified link feedback TLV var See [TOPOLOGY] Query Merge Flags TLV var See[QUERY] Ingress Flags TLV var See Section 7.3 Reserved Bandwidth TLV var See Section 7.4 Aggregation TLV var See Section 7.5 For simplicity we reuse here TLV types defined in [CR- LDP],[LDP],[QUERY] and [OPTICAL]. They are: - IPV4/6 specified link feedback TLV - Generalized Label TLV (used in the Query Label TLV encoding) - Query Label TLV - Query Merge Flags TLV Harikishan, et. al. [Page 10] Internet Draft LSP Back trace using MPLS-LDP/CR-LDP May 2002 Ingress Flags TLV is a list of pair of bits. 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. If Q7 is set in Query TLV, every LSR along the path will have to set its corresponding bits in the mask. The bits have to be set in the same order as the nodes in the tree TLV. Reserved bandwidth TLV informs the bandwidth allocated for the LSP over the out bound link. It Q4 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 such information, a ZERO Length TLV has to be encoded. For more information on this TLV, see section "Reserved Bandwidth TLV". Aggregation TLV informs the FEC aggregation occurring along the paths in the LSP-Tree. If Q5 flag 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 the LSR is performing FEC aggregation, the encoded information includes a FEC, which is either subsumes or subsumed by the FEC being backtraced. For more information on this TLV, see section "Aggregation TLV". The information encoded in the above TLVs s by each LSR, should be in the same order as its information in tree TLV. For more information for the TLV encoding of the TLVs which are reused, please see [CR-LDP],[LDP],[TOPOLOGY],[OPTICAL] and [QUERY]. 7.2 BackTrace Reply Message Procedures A BackTrace reply message can be generated by any node, which receives a backtrace request message, if the node 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 "No LSP to backtrace" status. If the node is true ingress of 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 LSP peer (siblings) set "P", computed as described in section 5.2. The timeout period for the responses from upstream LSP peers is implementation dependent and should be locally configurable. Once the timeout period expires, the node should generate a backtrace reply with whatever information it has gathered from the upstream LSP peers that have responded within the timeout interval. The gathered LSP sub-tree information is encoded as tree TLV in backtrace reply message. Responses received after timeout interval should be ignored. If the node is not able to propagate the backtrace request to any upstream LSP peer, it should immediately respond with a backtrace Harikishan, et. al. [Page 11] Internet Draft LSP Back trace using MPLS-LDP/CR-LDP May 2002 reply message with its own information. This information must state that this node is not a true ingress 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 TLV see section "Ingress Flags TLV". Each node has to encode into the backtrace reply message a message Id TLV. The mapping between a backtrace request and a backtrace reply message is done based on the message id. Besides the message Id TLV, each node has to encode the information that was queried (bandwidth, merging info, Ingress or Non Ingress LSR, Aggregation info, etc.,). After the encoding is done, the backtrace reply message is sent back on the reverse path, towards the egress. 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 the same LSP level traversed by backtrace message. 8. TLVs 8.1 Query TLV extensions. The Query TLV travels in the backtrace message till it reaches the ingress or a node, 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 being queried in the backtrace. The following section describes the extensions to the Query TLV introduced in [QUERY]. Flags Q3,Q8 are never used in backtrace message. If they are set, they must be ignored by the LSRs along the LSP-Tree. For the purpose of collecting allocated bandwidth and ingress information in the LSP- Tree, we introduce two new flags Q4 and Q7.(Q4 and Q7 are reserved flags in [QUERY]). - Q4: 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. - Q5: Query FEC aggregation information. See "Aggregation TLV" section. - Q7: Query which LSRs in the LSP-Tree act as Ingresses for the FEC received in backtrace message. Harikishan, et. al. [Page 12] Internet Draft LSP Back trace using MPLS-LDP/CR-LDP May 2002 8.2 Tree TLV 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 (TBA) | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Address Family | IP Address .... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Sibling Count | SubûTree 1 .... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sub-Tree 2 ...... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The value field of tree TLV is a recursive structure capturing a tree. Each LSR (Root)IP address is followed by the sibling count. Root IP Address is the IP V4/V6 address of the root node. The LSPs outbound port IP address is encoded as the Root IP address in the TLV. Sibling count follows the IP address of the root node. Sibling count indicates the total no of sub-trees following the present (sub) tree root. Sibling count is 8-bit value with range 0-255. Value 255 is reserved. It is used to inform that the LSR is not willing to reveal the sibling count. Sub-tree structure follows the sibling count field. The tree structure is encoded in depth first order. The leaf nodes in the tree will have ZERO sibling count. The leaf nodes are most likely the Ingress LSRs of the LSP. Whether the LSR is True ingress 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: 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(TBA) | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Number of LSRS | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Ingress flags | | | ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Harikishan, et. al. [Page 13] Internet Draft LSP Back trace using MPLS-LDP/CR-LDP May 2002 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 LSRs, which are encoded in the Tree TLV. Each 2 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 for the backtraced LSP and are set to 10 otherwise. It is set to 11 if the LSR can act as both ingress and intermediate LSR for the FEC. 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 is encoded in the same order as the nodes in the tree TLV. 8.4 Reserved Bandwidth TLV 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| TBA | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LSP ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |HOLDINGPRIORITY| Bandwidth Allocated +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | Address family |IP addr of +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | interface (near end) ..... ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ IP address of interface (far end) ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Optional parameters | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ LSP ID LSP ID of the backtraced CR-LSP. Holding Priority Holding priority of the CR-LSP Bandwidth Allocated Bandwidth allocated over the out-bound link of the CR-LSP in bytes per second. Address Family Address family of the following two IP addresses in the TLV. Finally the interfaceÆs IP address and far ends address are placed in the TLV. Harikishan, et. al. [Page 14] Internet Draft LSP Back trace using MPLS-LDP/CR-LDP May 2002 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 vector are encoded in the same order as the nodes 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 S1, 100 is the bandwidth unit reserved on the link between R1 and 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 vector. Optional Parameters: No optional parameters are defined at present. 8.5 Aggregation TLV The encoding 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| TBA | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Number of LSRs | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Aggregation Element 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Aggregation Element 2 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Aggregation Element n | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The aggregation TLV is a list of aggregation elements. The order of the FEC elements corresponds to the order of LSRs 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 LSRs, 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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Harikishan, et. al. [Page 15] Internet Draft LSP Back trace using MPLS-LDP/CR-LDP May 2002 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. 8.6 Notification message Handling When a notification message with status ôNo LSP to backtraceö is received from a LSP peer, as response to the backtrace message, the LSR has to stop waiting for a backtrace reply from that peer LSR. Status code summary Status Code E Status Data Section Title No LSP to backtrace 1 TBA "Backtrace Message procedures" 9. Authors Addresses Harikishan Desineni Ericsson 70,Castiian Drive Santa Barbara California USA-93117 Tel: +1 805 562 6419 Mobile: +1 805 252 2641 Email: desineni@hotmail.com KameswaraRao Avasarala Ericsson 70,Castlian Drive Santa Barbara California USA-93117 Phone: +1 805 562 6212 Email: kameswara.rao@ericsson.com 10. 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. Harikishan, et. al. [Page 16] Internet Draft LSP Back trace using MPLS-LDP/CR-LDP May 2002 [LDP] Andersson et al., "LDP Specification",RFC3036, January 2001. [QUERY] Peter Ashwood-Smith et al.,"MPLS LDP Query Message description", draft-ietf-mpls-lsp-query-03.txt, August 2001. (Work in progress) [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- 07.txt, November 2001.(Work in progress) [TOPLOGY] Ashwood-Smith P., Bilel., "Improving Topology Data Base Accuracy with LSP Feed Back", draft-ietf-mpls-te-feed-03.txt, November 2001.(Work in progress) Harikishan, et. al. [Page 17]