Internet Draft
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]