A Backward-Recursive PCE-Based Computation (BRPC) Procedure to Compute Shortest Constrained Inter-Domain Traffic Engineering Label Switched Paths
Extracted elements (25)
BRPC's simultaneous computation of diverse path segments within the VSPT enables optimal diverse TE LSP computation, unlike a 2-step approach (compute first path, remove traversed elements, compute second) which cannot guarantee finding a solution even when one exists or achieving optimality under objective functions.
Each VSPT branch may be returned as either an explicit path (all hops listed) or a loose path (only BN specified) to preserve domain confidentiality. Loose paths can be resolved to explicit paths during signaling using path keys.
In inter-AS TE, metric normalization between ASes may be required for path computation to be meaningful. Service providers should agree on a TE metric normalization scheme and use the TE metric (requested via the METRIC object) rather than modifying IGP metrics.
No topology or resource information is distributed between domains, preserving IGP/BGP scalability and confidentiality. This is a core assumption mandated by RFC 4105 and RFC 4216 requirements.
The BRPC procedure uses a backward-recursive technique where computation starts at the destination domain and propagates upstream, building a Virtual Shortest Path Tree (VSPT). This guarantees finding the globally optimal constrained inter-domain TE LSP, unlike per-domain forward computation which cannot guarantee optimality.
For inter-AS TE LSP path computation, the BRPC procedure requires knowledge of TE attributes of inter-AS TE links. ASBRs may flood TE information for inter-ASBR links via IGP extensions (RFC 5316 for IS-IS, RFC 5392 for OSPF) even without IGP adjacency over those links.
If a PCE does not recognize the VSPT flag of the RP object, it sends PCErr with Error-Type=4 (Not supported object), Error-value=4 (Unsupported parameter) per RFC 5440. The RP object included should contain the whole bit flag field with all bits after the unsupported parameter set to zero.
The BRPC procedure may be used in conjunction with per-domain path computation (RFC 5152) to compute path segments, but in that case end-to-end path optimality can no longer be guaranteed.
A BRPC implementation SHOULD provide monitoring parameters including number of successful completions, failures due to unrecognized VSPT flag, and failures due to unsupported BRPC procedure, all on a per-PCE-peer basis.
A PCE that can compute the requested path for more than one consecutive domain SHOULD perform this computation for all such domains before passing the PCRep to the previous PCE in the sequence.
Because path segments computed by a downstream PCE in the BRPC procedure MUST be provided along with their respective path costs, the C flag of the METRIC object carried within the PCReq message MUST be set.
If a PCE along the domain path recognizes but does not support the BRPC procedure, it MUST return a PCErr message to the upstream PCE with Error-Type 13 ('BRPC procedure completion failure').
If a PCE requires relaying a path computation request per BRPC but no downstream PCE is available, the PCE MUST send a negative path computation reply using a PCReq message containing a NO-PATH object with the 'BRPC path computation chain unavailable' bit (bit 28) set in the NO-PATH-VECTOR TLV.
If the BRPC procedure is not supported or allowed on a PCE, it MUST send a PCErr message as specified in Section 9.
SVEC object diversity requests (link, node, or SRLG diversity flags L, N, S) MUST be taken into account by each PCE along the path computation chain during VSPT computation in the BRPC procedure.
The PCC MAY indicate the sequence of domains to be traversed using the Include Route Object (IRO) defined in RFC 5440, making the domain sequence available to all PCEs in the computation chain.
The PCErr message reporting BRPC procedure completion failure MUST be relayed to the requesting PCC.
A new VSPT flag is defined for bit 25 of the RP object in the PCEP PCReq message. When set, it indicates the PCC requests inter-domain TE LSP computation using the BRPC procedure.
The Virtual Shortest Path Tree (VSPT) is a multipoint-to-point (MP2P) tree rooted at the TE LSP destination, with branches to each entry boundary node BN-en(k,i) of domain i. Each branch represents the shortest constrained path segment from that boundary node to the destination.
RFC 5441 allocates bit 25 (VSPT) in the 'RP Object Flag Field' sub-registry of the PCEP Numbers registry, and bit 4 ('BRPC path computation chain unavailable') in the 'NO-PATH-VECTOR TLV Flag Field' sub-registry.
RFC 5441 allocates Error-Type 13 ('BRPC procedure completion failure') with Error-value 1 ('BRPC procedure not supported by one or more PCEs along the domain path') in the 'PCEP-ERROR Object Error Types and Values' sub-registry, and Error-value 4 (Unsupported parameter) under existing Error-Type 4.
The BRPC procedure does not increase the information exchanged between ASes and preserves topology confidentiality, in compliance with RFC 4105 and RFC 4216 requirements for inter-domain TE.
The BRPC procedure inherits all potential attacks described in RFC 5440 Section 10, including spoofing, snooping, falsification, and denial of service. An implementation MAY support a policy module governing conditions under which a PCE participates in BRPC (e.g., origin of requests, rate limits).
BRPC proceeds in three stages: (1) PCReq forwarded domain-by-domain from PCC to PCE(n) in destination domain; (2) PCE(n) computes VSPT(n) and returns it upstream; (3) each PCE(i) from n-1 to 1 extends the VSPT using its own TED, with PCE(1) computing and returning the final end-to-end path to the PCC.
The VSPT is encoded in a PCRep message as a non-ordered list of Explicit Route Objects (EROs), where each ERO represents a path segment from a boundary node to the destination specified in the END-POINT object of the corresponding PCReq message.