Preferred path route graphs in a network

Abstract

A method implemented by a network element (NE) in a network, comprising receiving, by the NE, preferred path route (PPR) information describing a PPR graph, the PPR graph representing a plurality of PPRs between an ingress NE and an egress NE in the network, and updating, by the NE, a forwarding database to include a forwarding entry for the egress NE in response to identifying the NE in the plurality of PPR-PDEs, the forwarding entry indicating a next hop by which to forward a data packet comprising the PPR-ID.

What is claimed is: 
     
       1. A method implemented by a network element (NE) in a network, comprising:
 receiving, by the NE, preferred path route (PPR) information describing a PPR graph, the PPR graph representing a plurality of PPRs between one or more ingress NEs and one or more egress NEs in the network, the PPR information including a PPR graph identifier (PPG-ID), a PPR-identifier (PPR-ID), and a plurality of PPR-Path Description Elements (PPR-PDEs), the PPG-ID identifying the PPR graph, the PPR-ID being associated with the egress NE, the plurality of PPR-PDEs describing a plurality of elements included in the PPR graph, a PPR-PDE describing the ingress NE including a source flag and a PPR-PDE describing the egress NE including a destination flag; and 
 updating, by the NE, a forwarding database to include a forwarding entry for the egress NE in response to identifying the NE in the plurality of PPR-PDEs excluding the PPR-PDE describing the egress NE, the forwarding entry indicating a next hop by which to forward a data packet comprising the PPR-ID. 
 
     
     
       2. The method of  claim 1 , wherein the PPR graph comprises a plurality of branches, wherein each branch comprises a plurality of elements on a path between two NEs included in the PPR graph. 
     
     
       3. The method of  claim 1 , wherein the PPR graph comprises a plurality of ingress NEs and only the egress NE, wherein the PPR graph comprises a plurality of branches, wherein each of the branches comprises a plurality of elements on a path connecting one of the ingress NEs to an NE along the path to the egress NE, wherein each of the plurality of branches includes at least one common NE, and wherein the method further comprises:
 sequentially searching, by the NE, a plurality of PPR-PDEs on a first branch of the plurality of branches to determine whether the NE is identified in one of the plurality of PPR-PDEs; 
 determining, by the NE, the egress NE of the first branch based on the destination flag in response to being identified in the one of the plurality of PPR-PDEs; and 
 generating, by the NE, the forwarding entry for the egress NE indicating that a next hop toward the egress NE is a next PPR-PDE of the plurality of PPR-PDEs. 
 
     
     
       4. The method of  claim 1 , wherein the PPR graph comprises a plurality of ingress NEs and a plurality of egress NEs, wherein the PPR graph comprises a plurality of branches, wherein each of the branches comprises a plurality of elements on a path connecting one of the ingress NEs to an NE along the path to one of the egress NEs, wherein each of the plurality of branches includes at least one common NE, and wherein the method further comprises:
 sequentially searching, by the NE, a plurality of PPR-PDEs on a first branch of the plurality of branches to determine whether the NE is identified in one of the plurality of PPR-PDEs; 
 determining, by the NE, a plurality of egress NEs of the first branch in response to being identified in the one of the plurality of PPR-PDEs; and 
 generating, by the NE, a plurality of forwarding entries for the plurality of egress NEs. 
 
     
     
       5. The method of  claim 1 , wherein the PPR information includes a flag indicating that the PPR graph is a bidirectional forest, wherein the PPR graph comprises a plurality of ingress NEs and a plurality of egress NEs, wherein the PPR graph comprises a plurality of branches, wherein each of the plurality of branches comprises a plurality of elements on a bidirectional path connecting one of the ingress NEs to an NE along the bidirectional path to one of the egress NEs, wherein each of the plurality of branches includes at least one common NE, and wherein the method further comprises:
 sequentially searching, by the NE, a plurality of PPR-PDEs on a first branch of the plurality of branches to determine whether the NE is identified in one of the plurality of PPR-PDEs; 
 determining, by the NE, a first plurality of destinations along a first direction of the first branch in response to being identified in the one of the plurality of PPR-PDEs; 
 generating, by the NE, a plurality of forwarding entries for the first plurality of destinations; 
 determining, by the NE, a second plurality of destinations along a second direction of the first branch; and 
 generating, by the NE, a plurality of forwarding entries for the second plurality of destinations. 
 
     
     
       6. The method of  claim 1 , wherein the PPR information includes a policy group tag associated with one or more PPR graphs, wherein the one or more PPR graphs are assigned the policy group tag based on an attribute associated with the one or more PPR graphs, wherein the attribute is at least one of a traffic engineering (TE) parameter, network characteristic, or service requirement that is associated with a resource to be reserved on each of the one or more PPR graphs. 
     
     
       7. The method of  claim 1 , wherein the PPR information is received from another NE in the network as a plurality of fragments, wherein each fragment includes the PPG-ID, a fragment identifier, a last fragment flag, and a subset of the plurality of PPR-PDEs, wherein the fragment identifier indicates a sequence number of a respective fragment, and wherein the last fragment flag indicates whether the respective fragment is a last fragment representing the PPR graph of the plurality of fragments. 
     
     
       8. A network element (NE) implemented in a network, comprising:
 a memory configured to store instructions; and 
 a processor coupled to the memory and configured to execute the instructions to cause the processor to be configured to:
 receive preferred path route (PPR) information describing a PPR graph, the PPR graph representing a plurality of PPRs between one or more ingress NEs and one or more egress NEs in the network, the PPR information including a PPR graph identifier (PPG-ID), a PPR-identifier (PPR-ID), and a plurality of PPR-Path Description Elements (PPR-PDEs), the PPG-ID identifying the PPR graph, the PPR-ID being associated with the egress NE, the plurality of PPR-PDEs describing a plurality of elements included in the PPR graph, a PPR-PDE describing the ingress NE including a source flag and a PPR-PDE describing the egress NE including a destination flag; and 
 update a forwarding database to include a forwarding entry for the egress NE in response to identifying the NE in the plurality of PPR-PDEs excluding the PPR-PDE describing the egress NE, the forwarding entry indicating a next hop by which to forward a data packet comprising the PPR-ID. 
 
 
     
     
       9. The NE of  claim 8 , wherein the PPR graph comprises a plurality of branches, wherein each branch comprises a plurality of elements on a path between two NEs included in the PPR graph. 
     
     
       10. The NE of  claim 8 , wherein the PPR graph comprises a plurality of ingress NEs and only the egress NE, wherein the PPR graph comprises a plurality of branches, wherein each of the branches comprises a plurality of elements on a path connecting one of the ingress NEs to an NE along the path to the egress NE, wherein each of the plurality of branches includes at least one common NE, and wherein the instructions further cause the processor to be configured to:
 sequentially search a plurality of PPR-PDEs on a first branch of the plurality of branches to determine whether the NE is identified in one of the plurality of PPR-PDEs; 
 determine the egress NE of the first branch based on the destination flag in response to being identified in the one of the plurality of PPR-PDEs; and 
 generate the forwarding entry for the egress NE indicating that a next hop toward the egress NE is a next PPR-PDE of the plurality of PPR-PDEs. 
 
     
     
       11. The NE of  claim 8 , wherein the PPR graph comprises a plurality of ingress NEs and a plurality of egress NEs, wherein the PPR graph comprises a plurality of branches, wherein each of the branches comprises a plurality of elements on a path connecting one of the ingress NEs to an NE along the path to one of the egress NEs, wherein each of the plurality of branches includes at least one common NE, and wherein the instructions further cause the processor to be configured to:
 sequentially search a plurality of PPR-PDEs on a first branch of the plurality of branches to determine whether the NE is identified in one of the plurality of PPR-PDEs; 
 determine a plurality of egress NEs of the first branch in response to being identified in the one of the plurality of PPR-PDEs; and 
 generate a plurality of forwarding entries for the plurality of egress NEs. 
 
     
     
       12. The NE of  claim 8 , wherein the PPR information includes a flag indicating that the PPR graph is a bidirectional forest, wherein the PPR graph comprises a plurality of ingress NEs and a plurality egress NEs, wherein the PPR graph comprises a plurality of branches, wherein each of the plurality of branches comprises a plurality of elements on a bidirectional path connecting one of the ingress NEs to an NE along the bidirectional path to one of the egress NEs, wherein each of the plurality of branches includes at least one common NE, and wherein the instructions further cause the processor to be configured to:
 sequentially search a plurality of PPR-PDEs on a first branch of the plurality of branches to determine whether the NE is identified in one of the plurality of PPR-PDEs; 
 determine a first plurality of destinations along a first direction of the first branch in response to being identified in the one of the plurality of PPR-PDEs; 
 generate a plurality of forwarding entries for the first plurality of destinations; 
 determine a second plurality of destinations along a second direction of the first branch; and 
 generate a plurality of forwarding entries for the second plurality of destinations. 
 
     
     
       13. The NE of  claim 8 , wherein the forwarding entry comprises an address prefix indicating the next hop, wherein the address prefix represents a plurality of NEs along a branch of the PPR graph. 
     
     
       14. The NE of  claim 8 , wherein the PPR information includes a type field indicating that the plurality of PPR-PDEs describes a tree, a forest, or a bidirectional forest. 
     
     
       15. A non-transitory computer readable medium configured to store a computer program product comprising computer executable instructions that, when executed by a processor of a network element (NE) implemented in a network, cause the processor to:
 receive preferred path route (PPR) information describing a PPR graph, the PPR graph representing a plurality of PPRs between one or more ingress NEs and one or more egress NEs in the network, the PPR information including a PPR graph identifier (PPG-ID), a PPR-identifier (PPR-ID), and a plurality of PPR-Path Description Elements (PPR-PDEs), the PPG-ID identifying the PPR graph, the PPR-ID being associated with the egress NE, the plurality of PPR-PDEs describing a plurality of elements included in the PPR graph, a PPR-PDE describing the ingress NE including a source flag and a PPR-PDE describing the egress NE including a destination flag; and 
 update a forwarding database to include a forwarding entry for the egress NE in response to identifying the NE in the plurality of PPR-PDEs excluding the PPR-PDE describing the egress NE, the forwarding entry indicating a next hop by which to forward a data packet comprising the PPR-ID. 
 
     
     
       16. The non-transitory computer readable medium of  claim 15 , wherein the PPR graph comprises a plurality of branches, wherein each branch comprises a plurality of elements on a path between two NEs included in the PPR graph. 
     
     
       17. The non-transitory computer readable medium of  claim 15 , wherein the PPR graph comprises a plurality of ingress NEs and only the egress NE, wherein the PPR graph comprises a plurality of branches, wherein each of the branches comprises a plurality of elements on a path connecting one of the ingress NEs to an NE along the path to the egress NE, wherein each of the plurality of branches includes at least one common NE. 
     
     
       18. The non-transitory computer readable medium of  claim 15 , wherein the PPR graph comprises a plurality of ingress NEs and a plurality of egress NEs, wherein the PPR graph comprises a plurality of branches, wherein each of the branches comprises a plurality of elements on a path connecting one of the ingress NEs to an NE along the path to one of the egress NEs, wherein each of the plurality of branches includes at least one common NE. 
     
     
       19. The non-transitory computer readable medium of  claim 15 , wherein the PPR information includes a flag indicating that the PPR graph is a bidirectional forest, wherein the PPR graph comprises a plurality of ingress NEs and a plurality of egress NEs, wherein the PPR graph comprises a plurality of branches, wherein each of the plurality of branches comprises a plurality of elements on a bidirectional path connecting one of the ingress NEs to an NE along the bidirectional path to one of the egress NEs, wherein each of the plurality of branches includes at least one common NE. 
     
     
       20. The non-transitory computer readable medium of  claim 15 , wherein a first PPR-PDE on a branch of the PPR graph includes a flag indicating that the branch is cyclical.