MPLS Working Group Heinrich Hummel Internet Draft Siemens AG Expiration Date: December 1999 Swee Loke Nortel Networks June 1999 Explicit Tree Routing draft-hummel-mpls-explicit-tree-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 except that the right to produce derivative works is not granted. 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 to cite them other than as "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. Abstract This draft proposes the TREE ROUTE TLV that encodes a tree structured route which can be used to carry explicit routing information. It also specifies the progression of the TLV from the root of the tree to the leaf nodes. Every node that the TLV traversed has to decode/process the TLV in such a way that the correct child link/ nodes are determined as well as the respective subtree route information. Individual Information targetted for a specific node or a contiguous cluster of nodes can also be packed into this TREE ROUTE TLV. Hummel & Loke June 1999 [Page 1] Explicit Tree Routing Exp. Dec 1999 The draft also presents the benefits of using TREE ROUTE TLV in MPLS. The applications include constrain based routing, traffic engineering, VPN installations and static multicast tree. The capability of carrying targetted information for individual node in the tree is very powerful in MPLS. This allows different nodes in the tree route to use the same tree route for different FECs. Different bandwidth requirement information targetted for different sections of a tree can also be packed into the TREE TROUTE TLV. The application of this TLV is not mpls-specific. Other Working Groups may consider the proposed TLV as well. 1. Introduction It is agreed that explicit routing is needed in MPLS. Different TLVs and protocols have been designed or enhanced to support explicit routing. Most of the work has been focused on point-to-point LSPs. This draft proposes the TREE ROUTE TLV which can encode a tree structured route. In addition to that, it can also carry targetted information destined to a particular node or a specific contigous cluster of nodes. The tree structured route may be provided based on some static configuration information or derived algorithmically from the results of a dynamic route computation. The decision is up to the protocols that use the TLV, and is outside the scope of this draft. The TREE ROUTE TLV can be used in some LSP setup protocol (E.g., LDP with possibly some new message types) to setup different types of explicit routes such as point-to-point, point-to-multipoint and multipoint-to-point LSPs. The exact specification of supporting TREE ROUTE TLV in the LSP setup protocol is for further study, and is outside the scope of this draft. Section 2 presents different applications of the TREE ROUTE TLV in MPLS and their benefits. The TREE ROUTE TLV is independent of its application. It guides the message/packet to each leaf properly, and indicates if certain piece of targetted information should be processed and/or forwarded by a particular node specified in the TREE ROUTE TLV. However, it has no indication of any application-dependent actions to be taken on the way to the leaves. Instead, to give such instructions, that should be the job of the protocol message (e.g., LDP message) that carries the TREE ROUTE TLV (or of any other TLV). Consequently, the TREE ROUTE TLV can be used for MPLS and NON-MPLS applications. Section 3 specifies the TREE ROUTE TLV. The progression of the TLV from the root to the leaf nodes are specified in section 4. Individual pieces of targetted information Hummel & Loke June 1999 [Page 2] Explicit Tree Routing Exp. Dec 1999 will also be processed and/or forwarded by each traversed node according to the TREE ROUTE TLV. When all intermediate routers process the received TREE ROUTE TLV using the same processing algorithm, the TREE ROUTE TLV will be forwarded exactly along the tree route as indicated by the TLV. 2. Applications and Benefits The TREE ROUTE TLV can be used to setup different types of MPLS LSPs. The following subsections presents different MPLS applications of the TREE ROUTE TLV and their benefits. Although the benefits are presented with examples of point-to-multipoint and multipoint-to- point LSPs, certain benefits are also applicable to point-to-point LSPs. 2.1 mp2p LSP: Egress-rooted Label Switch Tree (ELST) ELST refers to a multipoint-to-point LSP triggered by the Egress LER. This type of Label Switch Tree (LST) is very useful for traffic engineering and VPN configuration. The benefits: - The ELST setup info only needs to to be configured at one node, namely the Egress node. This saves having to configure multiple point-to-point LSPs from the Ingress nodes to Egress. By establishing a multipoint-to-point LST explicitly, we can specify where the merge points are and have more control on the traffic flow. - The capability to indicate if a node along the tree is also an ingress node by tagging the node as a leaf node. The saves the troubles of having to set up multiple point-to-point LSP to achieve the same results. - Information targetted for a node or a contigous sequence of nodes can be carried inside the TREE ROUTE TLV. Information that contains certain preference indications for a particular sequence of nodes can also be carried by the TREE ROUTE TLV. Examples of these are bandwidth requirements and security preference indications. Hummel & Loke June 1999 [Page 3] Explicit Tree Routing Exp. Dec 1999 Different bandwidth requiremnet information can be passed to different sections of the same LSP. This is essential since the bandwidth requirement for the links closer to the root may be different than that of the leaf nodes. This capability can also be useful when an LSP traversed across different administrative domain, and needs to conform to different traffic engineering agreement and/or chooses different security peferences on Ingress traffic. Since information targetted for each node can be packed into this TREE ROUTE TLV, the leaf nodes (ingress and intermediate routers) can use the same tree for different FECs. Once data traffic enters the ELST, it will be forwarded to the root, regardless what the FEC is. By defining the FEC(s) for the tree route on each node, it allows other point-to-point LSPs of that FEC to join the tree. - The LST will not be triggered if the Egress node is down. In the existing ER LSP, the Ingress node will always try to set up the ER LSP by sending the label request regardless if the Egress is up. 2.2 p2mp LSP: Ingress-rooted Label Switch Tree (ILST) ILST refers to a point-to-multipoint LSP setup by the Ingress LER. This type of Label Switch Tree (LST) is useful for static multicast tree and VPN. The benefits: - All the same benefits as existing point-to-point ER LSP. - The ILST setup info only needs to be configured at one node, namely the Ingress node. This saves having to configure multiple point-to-point LSPs from the Ingress to multiple Egress nodes. - The capability to indicate if a node along the tree is also an egress node by tagging the node as a leaf node. The saves the troubles of having to set up multiple point-to-point LSPs to achieve the same results. - Information targetted for a node or a contigous sequence of nodes can be carried inside the TREE ROUTE TLV. See description in previous seciton. Hummel & Loke June 1999 [Page 4] Explicit Tree Routing Exp. Dec 1999 - The static tree can be used to deliver multicast traffic across different multicast routing domain. Each leaf node of the LST can be the root of its own multicast tree. The tree can allow dynamic branches by allowing the leaf of the tree to be the RP or core of a dynamic multicast tree. This may be useful in certain VPN environmemt where a static multicast tree across the backbone is configured to avoid periodic join/prune messages flooded across the carrier's backbone. The extending/pruning of the LST is for future study. - The point-to-multipoint LST can be used to deliver broadcast type messages to VPN LAN that is emulated across the MPLS backbone. 3. TREE ROUTE TLV Specification This section presents the definition of a tree route and the notation of a TREE ROUTE TLV. 3.1 Tree Route Definition A TREE ROUTE TLV can encode an explicit routing tree that consists of the following types of nodes: - Root node A root node is the node where the initial TREE ROUTE TLV is generated. It is also where the data traffic enters the tree route (in point-to-multipoint case) or where the data traffic terminates (in multipoint-to-point case). There is only one root node per tree. - Transit Node A Transit node is a node that is responsible for forwarding the data traffic along the tree route. Every node in a tree route, except the root node and the pure leaf nodes, is a transit node. Hummel & Loke June 1999 [Page 5] Explicit Tree Routing Exp. Dec 1999 - Leaf Node A leaf node is a node + which is to receive data traffic sent to the tree route from the root (in point-to-multipoint case), OR + where the data traffic to be delivered to the root enters the tree route (in multipoint-to-point case) For example, a leaf node in the point-to-multipoint multicast tree is a node that is to receive the traffic from the root, whereas a leaf node in a multipoint-to-point tree acts as an Ingress node for data traffic sent towards the root. A leaf node can be also a transit node. Hence, in the point-to-multipoint case, a leaf node that is also a transit node receives the data traffic itself and also forwards the data traffic along the tree route. - Cluster of nodes A cluster of nodes is defined as a contiguous subsection of a tree. It may be consist of only one node. 3.2 TREE ROUTE TLV The TREE ROUTE TLV contains a sequence of TLVs of the following types: - TYPE "(" - TYPE ")" - TYPE "ER-TLV" - TYPE "Opaque-Info" - TYPE "Node-Info" - TYPE "" Hummel & Loke June 1999 [Page 6] Explicit Tree Routing Exp. Dec 1999 "("-TLV and ")"-TLV The "("-TLVs and the ")"-TLVs have no associated values and have type length of zero, as they are used only to shape the tree. The "("-TLV marks the beginning of a branch, and ")"-TLV marks the end of a branch. ER-TLV The "ER-TLV" is the Explicit Route TLV as defined in [CR-LDP]. It specifies one or more hops that form a linear section of the tree route. A TREE ROUTE TLV contains at least one ER-TLV. The hop types currently supported by the TREE ROUTE TLV are "IPv4 prefix" and "IPv6 prefix". Opaque-Info TLV Although "Opaque-Info"-TLV is not really defined by TREE ROUTE TLV, but it is specified here for illustration purpose. Essentially, it is some information that is targetted for a node or a cluster of nodes. It can be the FEC-TLV, PFC-TLV or Traffic-TLV. The TREE ROUTE TLV is unaware of the content of these types of TLVs, but only instructs the nodes to use and/or forward them. Node-Info TLV The "Node-Info" TLV has to be placed immediately after an "ER-TLV", it is targetted to a traversed node that identify with the last ER- HOP in the ER-TLV. E.g., ER[hop1, ... , hopN"], Node-Info [Info-for-hopN]. The "Node-Info" TLV contains a mandatory 8 bit flag that indicates the structure or restriction of a node. Currently only the L bit is defined. An L bit that is set indicates a node is a leaf node. All other bits are reserved for future use and should be set to 0. 0 1 2 3 4 5 6 7 +------------+-+ | reserved |L| +------------+-+ The mandatory flag Each "Node-Info" TLV can contain zero or more "Opaque-Info" TLV. All these TLV will be processed by the specified node and not forwarded further. Hummel & Loke June 1999 [Page 7] Explicit Tree Routing Exp. Dec 1999 TLV The "Nodes-Info-End>" TLV contains a mandatory 16 bit sequence number that identyfies which instance of ""-TLV with a sequence number 0 applies to all ""-TLV. By proper placing "", a root node can create a TREE ROUTE TLV that instruct pieces of information to be passed to a cluster of nodes and only that cluster of nodes. Notation Syntax In all examples presented in this draft, the following notations will be used to represent the different TLVs that comprise the TREE ROUTE TLV: ER[...] represents an ER TLV where every ER hop type is IPv4 prefix that represents a router id. Each hop is separated by a period. ) represents a ")"-TLV Hummel & Loke June 1999 [Page 8] Explicit Tree Routing Exp. Dec 1999 ( represents a "("-TLV Node[...] represents a "Node-Info" TLV with Leaf bit not set Node[L;...] represents a "Node-Info" TLV with Leaf bit set [N] represents a "Nodes-Info-End>" TLV with sequence number N Opaque-n represents a piece of information to be forwarded by TREE ROUTE TLV. Each TLV notation are shown separated by a comma. 3.3 General rules for encoding an initial TREE ROUTE TLV - The first contained ER TLV is always an ER-TLV whose first hop either points to the next receiving node or denotes the link to the next receiving node. - Each entire subtree route following a branching node is embraced with "("-TLV and ")"-TLV. E.g., ER[R1], (, ER[R2], ... ,), (, ER[R7], ... ,), ... - A leaf node X is specified by the presence of a "Node-Info" TLV with the leaf bit set. E.g., ER[ ... X], Node[L], ... - Information targetted for node X is packed inside the "Node-Info" TLV immediately after the ER-TLV where node X is specified. E.g., ER[ ... X], Node[Opaque-i], ... - Information targetted for a cluster of nodes starts from node X is packed inside the "[1] ) Note that here "Nodes>[1]" is redundant and can be omitted because the information cannot be forwarded further anyway. Example 3: Here the TREE ROUTE TLV specifies the same tree in Figure 1, but with following information to be forwarded along: Hummel & Loke June 1999 [Page 11] Explicit Tree Routing Exp. Dec 1999 - A piece of information (Opaque-1234) is to be targetted to R1, R2, R3 and R4, and all the links from R1 on. ER[R1], TLV "Nodes-Info-End>" TLV indicates that the information packed inside the corresponding "[1] , ( ER[R4] , Node[L], Nodes>[2] , ER[R5], Node[L;Opaque-3] ) ( ER[R6.R7] ) ER[...] represents an ER TLV where each hop is of type IPv4 prefix that specifies a router. R2 decodes the received TREE ROUTE TLV, concludes that it should use Opaque-1. It also knows that it needs to forward Opaque-2 to R3. R2 then sends the following revised TREE ROUTE TLV to R3: [1], ( ER[R4] , Node[L], Nodes>[2] , ER[R5], Node[L;Opaque-3] ) , ( ER[R6.R7] ) R3 recognizes itself being a leaf node in addition to a branching node. It also interprets that: - it should use but not forward Opaque-1. - it should use and forward Opaque-2 R3 sends to R4: [2] , ER[R5], Node[L;Opaque-3] R3 sends to R6: " TLV is optional in this example. 6. Conclusion This draft proposes a generic TREE ROUTE TLV that can be used in different areas, inside and outside of MPLS. In MPLS, it can be used to establish LSPs for point-to-multipoint or multipoint-to-point flows. The TREE ROUTE TLV is designed to specify a tree structure route and to deliver targetted information to certain nodes in the tree. The protocol message that carries the TREE ROUTE TLV should instruct the traversed nodes what actions are required. The TREE ROUTE TLV works well also in case of linear routes. The strength of carrying different information targetted for different sets of nodes in an LSP is valuable even for point-to-point LSPs. The application of this TLV is not mpls-specific. Other Working Groups (e.g. which are dealing with Multicast) may consider the proposed TLV as well. The specification of handling TREE ROUTE TLV in LSP setup protocols is for further study. 7. Intellectual Property Considerations Siemens AG and Nortel Networks may seek patent or other intellectual property protection for some or all of the technologies disclosed in this document. If any standards arising from this document are or become protected by one or more patents assigned to Siemens AG or Nortel Networks, Siemens AG and Nortel Networks intend to disclose those patents and license them under openly specified and non-discriminatory terms. 8. References [MPLS-ARCH] Rosen, Viswanathan, Callon: A Proposed Architecture for MPLS, (Work In Progress) Internet Draft, draft-ietf-mpls-arch-05.txt, April 1999. [CR-LDP] Constraint-Based LSP Setup using LD, (Work In Progress) Internet Draft, draft-ietf-mpls-cr-ldp-01.txt, Feb 1999 Hummel & Loke June 1999 [Page 16] Explicit Tree Routing Exp. Dec 1999 9. Authors' Addresses Heinrich Hummel Siemens AG Hofmannstrasse 51 81379 Munich, Germany Tel: +49 89 722 32057 Email: heinrich.hummel@icn.siemens.de Swee Loke Nortel Networks P.O.Box 3511 Station C Ottawa ON K1Y 4H7 Canada Tel: (613) 763-9658 Email: loke@nortelnetworks.com Hummel & Loke June 1999 [Page 17]