System and method for point to multipoint inter-domain multiprotocol label switching traffic engineering path calculation

• US 8,351,418 B2
• Filed: 02/18/2010
• Issued: 01/08/2013
• Est. Priority Date: 02/19/2009
• Status: Expired

• Current Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Inventors: Zhao, Qianglin Quintin, Chen, Huaimo
• Primary Examiner(s): CHO, HONG SOL
• Application Number:
  US12/708,048
• Publication Number:
  US 20100208733A1
• Time in Patent Office: 1,055 Days
• Field of Search: 370/254, 370/255, 370/351, 370/390, 370/40, 370/401
• US Class Current: 370/351
• CPC Class Codes: H04L 12/185 with management of multicast group membership
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 45/44 Distributed routing
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/484 using multiple routing trees
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]

Abstract

A system comprising a plurality of path computation elements (PCEs) configured to communicate with an ingress node, jointly compute a core tree for an inter-domain point-to-multipoint (P2MP) tree across a plurality of network domains, and independently compute a plurality of sub-trees in at least some of the network domains, wherein the core tree connects the ingress node to a boundary node (BN) in each one of the network domains that have a destination node and each sub-tree connects the BN to a plurality of destination nodes in one of the network domains that have a destination node.

Claims

1. A system comprising:

a plurality of path computation elements (PCEs) configured to communicate with an ingress node, jointly compute a core tree for an inter-domain point-to-multipoint (P2MP) tree across a plurality of network domains, and independently compute a plurality of sub-trees in at least some of the network domains that contain at least one destination node,

wherein the core tree connects the ingress node to at least one boundary node (BN) in each one of the network domains that have has a destination node,

wherein each sub-tree connects at least one of the BNs to at least one destination node in one of the network domains that has a destination node, and

wherein the inter-domain P2MP tree is a combination of the core tree and at least one sub-tree.

2. The system of claim 1, wherein the core tree comprises the ingress node, the BNs in each of the domains that has a destination node, at least one BN of a domain that does not have any destination node, and a branch node, a transit node, or both, and wherein the sub-tree comprises a branch node, a transit node, or both, and the destination nodes.

3. The system of claim 1, wherein the PCEs are arranged in a distributed PCE topology that comprise a root PCE associated with one of the network domains that comprises the ingress node, a transit PCE associated with one of the domains that transfers traffic from the ingress node to another one of the domains, a branch PCE associated with one of the domains that forwards traffic from the ingress node to at least two of the domains, and a leaf PCE associated with one of the domains that comprises the destination nodes.

4. The system of claim 3, wherein at least some of the PCEs and the ingress node exchange a PCE sequence object that specifies the distributed PCE topology, wherein the PCE sequence object comprises an object class, an object type (OT), an object length, a root PCE address, and a leaf PCE address.

5. The system of claim 1, wherein at least some of the PCEs and the ingress node exchange a request/reply (RP) object that indicates a path computation request/reply for the inter-domain P2MP tree.

6. The system of claim 5, wherein the RP object comprises a RP core tree bit (C) flag, a strict/loose bit (O) flag, a bi-directional bit (B) flag, a re-optimization bit (R) flag, a plurality of priority flags, a plurality of other flags, and a request identifier (ID) number.

7. The system of claim 6, wherein the C flag is set to indicate that the request or reply message is for a core tree related to an inter-domain P2MP tree computation.

8. The system of claim 1, wherein at least some of the PCEs and the ingress node exchange an end-point object that comprises an address for the ingress node, a plurality of addresses for the destination nodes, and a leaf type.

9. The system of claim 8, wherein the leaf type is set to indicate whether the object is associated with a request to add a new leaf to the P2MP tree, to remove a leaf from the P2MP tree, to modify or re-compute a path for an existing leaf, or to maintain and keep the path to the leaf unchanged.

10. A network component comprising:

at least one processor configured to obtain a computation request for an inter-domain point-to-multipoint (P2MP) tree from a source node to a plurality of leaf nodes across a plurality of network domains;

compute a core tree that comprises a plurality of paths from the source node to a boundary node (BN) in each of the network domains that comprises at least some of the leaf nodes;

calculate a sub-tree for each of the network domains that comprises at least some of the leaf nodes from at least one of the BNs in the core tree to the leaf nodes; and

send a result of the inter-domain P2MP tree computation to the source node,

wherein the inter-domain P2MP tree is a combination of the core tree and at least one sub-tree.

11. The network component of claim 10, wherein the core tree is computed using a Backward Recursive Path Calculation (BRPC) procedure and a Virtual Shortest Path Tree (VSPT) procedure.

12. The network component of claim 11, wherein the at least one processor is further configured to:

compute a plurality of sub-paths from the source node to the BN in each of the network domains that comprises at least some of the leaf nodes;

calculate a cost for each combination of the sub-paths that connect the source node to the BN in each of the network domains that comprises at least some of the leaf nodes; and

select a combination of the sub-paths that best satisfies a metric.

13. The network component of claim 12, wherein each of the sub-paths is computed by adding a plurality of nodes to a path in a sequence from the BN in each of the network domains to the source node.

14. The network component of claim 10, wherein a sub-tree is computed independently from the core tree to connect the BN to the leaf nodes in each of the network domains that comprises at least some of the leaf nodes.

15. The network component of claim 14, wherein the sub-tree is computed using a Constrained Shortest Path First (CSPF) procedure.

16. The network component of claim 14, wherein the sub-tree is computed based on an objective function (OF) that is used to compute a path, to synchronize computation of a plurality of paths, or both.

17. The network component of claim 10, wherein the result of the inter-domain P2MP tree computation comprises an inter-domain P2MP tree from the source node to the destination nodes if the inter-domain P2MP tree is computed successfully.

18. The network component of claim 10, wherein the result of the inter-domain P2MP tree computation comprises an error code and detail information for a reason why an inter-domain P2MP tree can not be found if no inter-domain P2MP tree is computed.

19. A method comprising:

computing, at least one path computation element (PCE), a core tree from a source node to a boundary node (BN) in each of a plurality of domains that comprise a leaf node;

computing a sub-tree from the BN in each of the domains to the leaf node in the same domains; and

combining the core tree and the sub-tree in each of the domains to establish an inter-domain point-to-multipoint (P2MP) tree.

20. The method of claim 19, wherein the sub-tree is computed in each of the domains independently without sharing confidential information between the domains, and the sub-tree is a minimum cost tree or a shortest path tree.

21. The method of claim 20, wherein computing the core tree comprises selecting the core tree from among at least two candidate trees according to a total cost of the core tree.

22. A method comprising:

performing, by at least one path computation element (PCE), a core tree computation procedure to compute a core tree, wherein the core tree comprises a root node and at least one boundary node in each of a plurality of network domains that have a destination node;

performing a sub-tree computation procedure to compute a plurality of sub-trees, one sub-tree for each network domain that has a destination node; and

combining the sub-trees and the core tree to form an inter-domain point-to-multipoint (P2MP) tree.

23. The method of claim 22, wherein performing a core tree computation procedure comprises:

using a backwards recursive path computation (BRPC) procedure to compute a plurality of paths from the root node to each boundary node in each of the plurality of network domains that have a destination node, wherein the plurality of paths from the root node to the ith boundary node is referred to as the ith Virtual Shortest Path Tree VSPT(i);

pick a first set of paths comprising a path from the root to the ith boundary node in each VSPT(i) for all i and merge the first set of paths into a core tree candidate;

pick a second set of paths from the root to the ith boundary node in each VSPT(i) for all i and merge the second set of paths into a second core tree candidate, wherein the second set of paths is different from the first set of paths by at least one path; and

select the core tree as a core tree candidate from among a plurality of core tree candidates with a minimum cost by applying an objective function (OF) to each core tree candidate, wherein the plurality of core tree candidates includes the first and second core tree candidates.

24. The method of claim 23, wherein the BRPC procedure does not prune any paths at transit nodes.