Dynamic RSA

Many studies have been performed proposing optimization solutions for off-line (or static) RSA in Elastic Optical Networks. In the last 3 years, however, focus have migrated to the dynamic performance of RSA. In this version of the problem the main issue to be solved is the spectrum fragmentation. The spectrum fragmentation occurs when connections with diverse rate are dynamically established and torn down, leaving gaps of available spectrum that may be smaller than connections requests that are dynamically arriving and therefore increasing demands blocking probability. In this sense solutions for the fragmentation problem may be sub classified into a fragmentation-aware RSA or a defragmentation technique with spectrum re-allocation.

Dynamic RSA algorithms may RSA be designed as one or two step approach. In two-step approaches, RSA problem is divided into routing and spectrum assignment sub-problems. In the one step approach routing and spectrum allocation are solved in tandem as one problem.

Connections Preemption Original Studies

-->

"Connection preemption can be a means to provide available and reliable services to high-priority connections when a network is heavily loaded and connection request arrival patterns are unknown, or when the network experiences link or node failures.

The importance or value of a connection, which can also relate to the connection’s quality of service (QoS) requirements can be expressed by a priority level. The priority levels can be preassigned by the end-system or by the network administrator using various factors such as reliability desired, pricing structure, bandwidth requirement, real-time delivery constraints, desired blocking probability, and nature of traffic such as multimedia, voice, and facsimiles.

The first algorithm optimizes the criteria of (i) the number of connections to be preempted, (ii) the bandwidth to be preempted, and (iii) the priority of connections to be preempted, in that order, and has polynomial complexity. The second algorithm optimizes the criteria of (i) the bandwidth to be preempted, (ii) the priority of connections to be preempted, and (iii) the number of connections to be preempted, in that order, and has exponential complexity."

[50] Peyravian, M.; Kshemkalyani, A.D.; , "Connection preemption: issues, algorithms, and a simulation study ," INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE , vol.1, no., pp.143-151 vol.1,7-12, Apr1997 URL:http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=635124&isnumber=13791

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.