Hybrid Policy of Routing and Spectrum Assignment in Elastic Optical Networks ()
1. Introduction
RSA (Routing and spectrum allocation) problem is solved whenever there is a connection request in elastic optical networks [1] [2] [3] . This problem is consists of two sub-problems which are routing (R) and spectrum allocation (SA). Solving these two sub-problems is complex [4] . These sub-problems are solved independently according to two predefined orders namely R-SA and SA-R. When the order is R-SA, the routing problem is solved before the spectrum allocation problem. Also, when the order is SA-R, the spectrum allocation problem is solved before the routing problem. Each of these two approaches has a specific advantage [1] [5] . In the R-SA approach, the average number of hops is reduced. In the SA-R approach, load distribution across network links and fragmentation are improved. [1] proposes a hybrid approach in which the R-SA or SA-R approach is chosen for a given connection request if it improves the network performance. In [5] , the authors used the hybrid approach to solve the RSA problem and multi-path routing to improve the protection of optical paths in elastic optical networks. In many papers, R-SA or SA-R strategies are performed for all topology node pairs. However, there are very few articles in which R-SA or SA-R strategies are performed for each topology nodes pair.
In optical networks, some techniques are proposed to reduce the blocking rate of connection requests. These techniques include rerouting, defragmentation and reconfiguration. For all these techniques, the same routing policy is applied for all the node pair in the network; for example, R-SA policy [6] [7] or SA-R policy [8] . In this work, we propose a dynamic spectrum routing and allocation policy. For an initial routing policy of all node pairs in a network, the proposal consists of changing the policy of some node pairs. This is possible because [1] justified the benefits of a hybrid routing policy. The change in routing policy of a pair of nodes can occur when connection requests for this pair of nodes are blocked. The objective is to accommodate a maximum number of incoming connection requests and maximize resource utilization efficiency.
2. Related Work
Literature techniques used to improve network resource utilization and accommodate new requests include defragmentation, rerouting, and reconfiguration. Defragmentation consists of reorganizing the frequency slots allocated to connections. It helps to reduce spectrum fragmentation [9] [10] [11] . Rerouting consists of resolving the RSA problem for connections already established in the network. Reconfiguration, for its part, consists of changing the initial routing of connections to a predetermined final routing [12] [13] . Reconfiguration and rerouting also enable better use of network resources. These techniques certainly have advantages. But they can create disruptions to existing connections; for example, flow interruptions. In this article, we propose to change the RSA problem resolution strategy of some nodes pairs in order to accept new connection requests. This will have the advantage of not disrupting already established connections and improving the blocking rate.
Algorithm 1 and Algorithm 2 respectively present the pseudocodes for solving the RSA problem when the order of resolution is R-SA (Algorithm 1) and SA-R (Algorithm 2) proposed in [1] . The Routing-Ordering-Algorithm function allows to determine the paths between a source node s and a destination node d, and bandwidth required T. The algorithm used determines the k shortest paths between s and d. The Spectrum-Ordering-Algorithm function allows to allocate frequency slots on the links of a path. The algorithm used is First-Fit.
3. Proposed Algorithm
Thus, suppose that the initial RSA policy of the network is R-SA and (s, d) a pair of nodes in the network. The RSA policy of this nodes pair is R-SA. If connection requests which have this nodes pair as source and destination are blocked, then we propose to change its RSA policy which will become SA-R.
In this paper, we propose a hybrid approach to RSA strategy (Algorithm 3). The proposed algorithm is described below.
Assume that the network’s RSA policy is R-SA. When a connection of source s, destination d and rate T arrives:
1) Solve the RSA problem using the R-SA algorithm;
2) If the problem has a solution, then accept the connection;
3) Otherwise Solve the RSA problem using the SA-R algorithm;
4) If the problem has a solution, then accept the connection;
5) Change the RSA strategy of the pair of nodes (s, d) to SA-R for a throughput greater than T.
6) Otherwise block the connection.
The routing strategy can be performed by any routing algorithm. In this work, it is performed by searching the k shortest paths. The SA strategy can be performed by any SA strategy. In this work, it is performed by First-Fit algorithm.
4. Simulation Setup
Our algorithm was evaluated using the FlexgridSim simulator [14] . The functions of this simulator have been adapted to take our proposal into account. Figure 1 represents USA-Backbone and NSFNet, network topologies used for the simulation. These three topologies have different characteristics in terms of number of links and nodes.
![]()
Figure 1. Topologies—(a) USA-Backbone and (b) NSFNet.
Each fiber has a capacity of 120 FS (Frequency Slot). Each connection request has bandwidth requiring slots evenly distributed between 2 and 10 slots. Traffic is generated dynamically and the request arrival time and connection hold time are generated according to an exponential distribution. 500 and 1000 connection requests are randomly generated. The source and destination node pairs of connection requests are generated according to a uniform distribution. The k-shortest path (k = 2) routing algorithm is used, with hop as cost metric, along with first-fit (FF) spectral assignment policy.
5. Performances Evaluation
Two metrics allow us to evaluate our proposals, namely the blocking probability and the fragmentation rate:
- The blocking probability (BP) is defined as the ratio between the total number of blocked connection requests (B) and the total number of requested connections (R).
(1)
- The metric used to calculate the fragmentation rate is Shannon entropy [15] presented in Equation (2):
(2)
where S is the number of slots per network link and fi a contiguous block of i slots.
The network fragmentation rate, which is the average of the network link fragmentation rate, is calculated after processing 100 requests.
Figures 2-5 present the blocking rates of new connections by implementing these three algorithms in the USA-Backbone and NSFNet networks. The results in Figure 2 and Figure 3 show different blocking rates, with better rates for our proposed LR-FSK algorithm (hybrid policy). For 500 connections, as shown, the blocking rate of LR (R-SA algorithm) is better than that of FSK (SA-R algorithm) when the network load is small, as shown in Figure 2. This result is confirmed by Figure 4. The blocking rate of FSK becomes better when the network load increases, as shown in Figure 3 for 1000 connections. This result is confirmed by Figure 5. For these two situations, the blocking rate of the new proposal is better than the others. The two topologies used have different characteristics. The results obtained in these two topologies show that the proposed algorithm is better in terms of blocking rate. This improvement in the blocking rate is explained by the routing policy implemented in the new proposal. Initially, the entire network has a routing policy set, e.g. routing followed by spectrum assignment for all node pairs.
The new proposal allowing policy change for a given node pair when a connection request is blocked with the current policy, increases the probability of accepting new connections for a given node pair. This explains the reduction in blocking rate of LR-FSK compared to LR and FSK algorithms.
![]()
Figure 2. Blocking probability for NSFNET with 500 requests.
![]()
Figure 3. Blocking probability for NSFNET with 1000 requests.
![]()
Figure 4. Blocking probability for USA-Backbone with 500 requests.
![]()
Figure 5. Blocking probability for USA-Backbone with 1000 requests.
6. Conclusion
This article focused on the problem of routing and slot assignment in elastic optical networks. We proposed a hybrid routing and slot assignment policy to improve blocking rate of connection requests. The proposed solution consists to change the routing policy of nodes pair if the connection request is blocked. The proposed algorithm improves blocking rate of new connection requests. This approach has been validated by evaluations. Future work may focus on scaling up the evaluations using other routing and slot allocation algorithms.
Acknowledgements
The authors thank LARIT and UREN for providing a pleasant working environment.