Low Overhead Path Computation Flooding

In (Perelló et al., 2010) a variation on the PCF is proposed, in the Low Overhead Path Computation Flooding (Lo-PCF) architecture a PCE from a given domain would only add the VSPT from one domain for each request Id. In order to accomplish this, upon receipt of a PRep message containing a VSPT the PCE checks if any other Prep from that request Id have already been processed, if so it discards the message. In case no reply message for that request Id have already been processed, the PCE updates the VSPT and forwards it in a message to all upstream domain PCEs. This scheme may lead to suboptimal resulting path compared to the PCF scheme, but it results in much lessen control messages exchanged. For this scheme to work properly request Ids must globally unique in the multi-domain network, but this scheme guarantees loop free path calculation without requiring a domain list as it is necessary in the PCF.

Perelló, J.; Hernández-Sola, G.; Agraz, F.; Spadaro, S. & Comellas, J. (2010), 'Scalable Path Computation Flooding Approach for PCE-Based Multi-domain Networks', ETRI journal 32(4).

Hybrid BRPC and H-PCE

In (Hernandez-Sola et al., 2010) a hybrid architecture between BRPC and H-PCE is proposed in order to increase the optimality of the resulting end-to-end path without increasing too much the number of control messages exchanged. “Additionally, a trade-off between shared routing information, scalability and security across domains is also obtained” (Hernandez-Sola et al., 2001). In the proposed architecture by default each child PCE executes the BRPC for path computation where the domain sequence is previously determined by a BGP protocol. In case the number of domains to be crossed (from a child source domain to the target domain) reaches a given threshold the child PCE delegates the path computation to the parent PCE. 

In the performance simulations presented in the paper the threshold value was fixed in 2 and 3 (referring to the number of domains to be crossed). The tests performed showed that the higher threshold value demand less interference of the parent PCE decreasing number of control messages, less computation burden to the parent PCE but in the other hand a subtle higher level of blocking probability.

Hernández-Sola, G.; Perelló, J.; Spadaro, S.; Moreno, A.; Agraz, F.; Comellas, J. & Junyent, G. (2010), Analysis of traffic engineering information dissemination strategies in PCE-based multi-domain optical networks, in 'Transparent Optical Networks (ICTON), 2010 12th International Conference on', pp. 1—4.

Hierarchical PCE architecture

In the Hierarchical PCE architecture child PCE's report to a parent PCE responsible to gather necessary information for an end-to-end LSP calculation not limited by a predetermined domain sequence. The parent PCE knows a topology map of the child domains and their respective child PCEs, the domains are seen as vertex and the links between border nodes at each domain (also known by the parent PCE) are the edges in such a topology. The parent PCE does not know the topology of each child domain (King & Farrel, 2009). Even though the end-to-end path resulting from this architecture reaches a higher level of optimality, it largely increases the number of control messages exchanged between PCEs and therefore problems of scalability may occur.

King, D. and Farrel, A. “The Application of the PCE Architecture to the Determination of a Sequence of Domains in MPLS &GMPLS,” IETF draft draft-king-pce-hierarchy-fwk-03.txt, Dec. 2009. http://tools.ietf.org/html/draft-king-pce-hierarchy-fwk-00

Path Computation Flooding

In a multi-domain network when a end-to-end path computation relies on a fixed, previously known domain sequence the resulting end-to-end path is considered to suboptimal in terms of resulting blocking probability (Hernández-Sola et al, 2010). To improve the optimality of the resulting path, the domain sequence should ideally be calculated on demand by one or more PCEs present in the network. However to achieve this optimality the number of overhead control messages is increased and therefore the burden of processing in the PCEs jeopardizes the scalability of the whole system, since the larger the multi-domain network the higher is the necessity of processing of control messages (Perelló et al., 2010). The control messages refer to both the constant update on link state (via OSPFs link sate advertisement) and the messages exchanged between different domains PCEs. 

Based on the BRPC, the Path Computation Flooding (PCF) is a different approach where a domain sequence is not previously stipluated. In this architecture, the destination domain PCE upon receipt of a PCReq from the source domain PCE calculates an egress VSPT and sends this as a message to all the PCE in adjacent domains and so on so forth till the PCE in the source domain receives a VSPT from all of his adjacent domain PCEs and selects the final optimum path (King & Farrel, 2009). The PCF generates too many control overhead messages and therefore presents serious scalability issues. 

Hernández-Sola, G.; Perelló, J.; Spadaro, S.; Moreno, A.; Agraz, F.; Comellas, J. & Junyent, G. (2010), Analysis of traffic engineering information dissemination strategies in PCE-based multi-domain optical networks, in 'Transparent Optical Networks (ICTON), 2010 12th International Conference on', pp. 1—4. 

King, D. and Farrel, A. “The Application of the PCE Architecture to the Determination of a Sequence of Domains in MPLS &GMPLS,” IETF draft draft-king-pce-hierarchy-fwk-03.txt, Dec. 2009. http://tools.ietf.org/html/draft-king-pce-hierarchy-fwk-00

Perelló, J.; Hernández-Sola, G.; Agraz, F.; Spadaro, S. & Comellas, J. (2010), 'Scalable Path Computation Flooding Approach for PCE-Based Multi-domain Networks', ETRI journal 32(4).

Back Recursive Path Computation

A multi-domain network presents a mayor obstacle to the effective computation of an end-to-end path that resides on the fact that a multi-domain network contains various independently managed system (autonomous system) that have confidential information on their own networks topology and state mainly due to security reasons. 

This information confidentiality prevents each single domain PCE to have full topology and Traffic Engineering information on the whole network which is necessary to compute an optimal or even feasible end-to-end path. 

In order to achieve a feasible end-to-end path computation it is possible to implement distributed or hierarchical architectures relying on the PCE. One possibility is to compute the path in a distributed way where each domain PCE computes the LSP for its own domain. In this architecture, usually, in domain sequence to be crossed is previously determined (normally via the BGP protocol). 

In a per domain path calculation, entry border nodes of each domain request its domain PCE for a LSP inside that domain, and therefore the resulting end-to-end path is a concatenation of those LSPs. In Back Recursive Path Computation (BRPC) PCEs present in each domain of the sequence collaborate to create a Virtual Shortest Path Tree. This VSPT comprises all possible end-to-end paths that cross the stipulated domain sequence. A request message is sent to the PCE in the destination domain and this one sends a VSPT to the PCE in his neighbor domain belonging to the sequence and so on so forth until the all the VSPT from all domains in the sequence reach the PCE in the source domain. Once the VSPT is informed to the source domain PCE, this selects the final path (Vasseur et al.,2009).

Vasseur, J.P. et al., “A Backward-Recursive PCE-Based Computation Procedure (BRPC) to Compute Shortest Constrained Inter-domain Traffic Engineering LSPs,” IETF RFC 5441, Apr. 2009.