System and method for point to multipoint inter-domain MPLS traffic engineering path calculation

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.

What is claimed is: 
     
       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 sub-tree in at least some each of the network domains that contain at least one has a destination node, 
 wherein the core tree connects the an ingress node to at least one a 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 a BN to at least one a destination node in one each 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, and 
 wherein a root PCE of the plurality of PCEs and the ingress node exchange a request/reply (RP) object that indicates a path computation request/reply for the inter-domain P2MP tree, the root PCE is associated with one of the network domains that comprises the ingress node, 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. 
 
     
     
       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 first branch node, a first transit node, or both, and wherein the sub-tree comprises a second branch node, a second 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 the 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 the root PCE 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 bidirectional 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  1, 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 the root PCE 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 system of claim  10  1, 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 system of claim  10  1, wherein a the each 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 system of  claim 14 , wherein the each sub-tree is computed using a Constrained Shortest Path First (CSPF) procedure. 
     
     
       16. The network component system of  claim 14 , wherein the each sub-tree is computed based on an objective function (OF) that is used to compute a path, to synchronize computation of a the 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 for computing an inter-domain point-to-multipoint (P2MP) tree which crosses a plurality of domains, the plurality of domains comprising a first domain which comprises an ingress node of the inter-domain P2MP tree and a second domain which comprises a destination node of the P2MP tree, the method comprising:
 computing, at least one by a root path computation element (PCE) and a leaf PCE, a core tree from a source the ingress node to a boundary node (BN) in each of a plurality of domains that comprise a leaf node the second domain, the root PCE being associated with the first domain and the leaf PCE being associated with the second domain; 
 computing, by the leaf PCE, a sub-tree from the BN in each of the domains the second domain to the leaf destination node in the same domains second domain; and 
 combining, by the root PCE, the core tree and the sub-tree in each of the domains to establish an the inter-domain point-to-multipoint (P2MP) tree, 
 wherein the root PCE and the ingress node exchange a request/reply (RP) object that indicates a path computation request/reply for the inter-domain P2MP tree, 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. 
 
     
     
       20. The method of  claim 19 , wherein the sub-tree is computed in each of the domains the second domain 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 an ingress node and at least one boundary node in each of a plurality of network domains that have has 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, 
 wherein the at least one PCE and the ingress node exchange a request/reply (RP) object that indicates a path computation request/reply for the inter-domain P2MP tree, the root PCE is associated with one of the network domains that comprises the ingress node, the RP object comprising 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. 
 
     
     
       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 ingress node to each boundary node in each of the plurality of network domains that have has a destination node, wherein the plurality of paths from the root ingress 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 ingress node 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 ingress node 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. 
     
     
       25. The method of 19, wherein the sub-tree in each of a plurality of domains having the destination node is computed after computation of the core-tree.  
     
     
       26. The method of claim 19, 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.  
     
     
       27. The method of claim 22, 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.  
     
     
       28. A network computing device, comprising:
 a memory;   a processor coupled to the memory, the processor configured to
 compute a core tree for a plurality of network domains, wherein a root of the core tree is coupled to an ingress node and a leaf node of the core tree is coupled to a boundary node in each of the plurality of network domains having a destination node; and 
 combine the core tree with a sub-tree in each of the plurality of network domains having a destination node to establish an inter-domain point-to-multipoint (P2MP) tree, wherein a root of the sub-tree is coupled to the boundary node in each of the plurality of the network domains having a destination node; and 
   an input/output (I/O) device configured to exchange a request/reply (RP) object with the ingress node, wherein the RP object indicates a path computation request/reply for the inter-domain P2MP tree, 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.    
     
     
       29. The network computing device of claim 28, wherein the network computing device is associated with one of the plurality of network domains having the ingress node.  
     
     
       30. The network computing device of claim 29, wherein the network computing device is further configured to compute the sub-tree in the one of the plurality of network domains having the ingress node if the one of the plurality of network domains has a destination node.  
     
     
       31. The network computing device of claim 28, wherein the network computing device is further configured to communicate with a plurality of other network computing devices that are associated with other network domains not having the ingress node.  
     
     
       32. The network computing device of claim 31, wherein each of the plurality of other network computing devices is configured to compute the sub-tree in each of the associated other network domains having a destination node.  
     
     
       33. The network computing device of claim 31, wherein the network computing device is further configured to receive a computation result of the sub-tree from each of the plurality of other network computing devices associated other network domains having a destination node.  
     
     
       34. The network computing device of claim 31, wherein the core tree is computed by the network computing device that receives information related to core tree computation from the plurality of other network computing devices.  
     
     
       35. The network computing device of claim 28, wherein the sub-tree is computed after computation of the core tree.  
     
     
       36. The network computing device of claim 28, 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.