A protection and fragmentation management approach in elastic optical networks under multicast traffic

Abstract

Elastic Optical Networks (EONs) support the flexible allocation of bandwidth and contribute to high-speed all-optical data communications. Any traffic demand passing through optical fibers is susceptible to link failure, which may lead to tremendous data and revenue loss. Another serious concern related to spectrum allocation in EONs is fragmentation, which is the problem of not being able to use free spectrum blocks because of misalignment. To provide survivability to the multicast traffic demands and also manage the problem of fragmentation in EONs, we propose an approach that integrates multicast light-tree protection using a dedicated protection approach and three policies of spectrum allocation to manage fragmentation in EONs. We have also considered a traffic grooming based approach along with the proposed approach. Grooming of traffic demands means routing similar traffic demands through a common light-tree and allocating spectrum to the links of the light-tree according to the cumulative bandwidth demand of the groomed traffic. The simulation results performed on several network topologies indicate that our proposed approach outperforms existing approaches concerning bandwidth blocking probability and fragmentation index.

1 Introduction

The number of Internet users is increasing day-by-day exponentially. As per CISCO, the annual global Internet traffic rate will read up to 4.8 ZB per year by 2022 [1]. Thus, to cater to this explosive growth of Internet traffic requirements, a suitable bandwidth allocation technology must be explored. The traditional wavelength division multiplexing (WDM) optical networks provide a rigid grid spectrum allocation technique [2, 3]. In WDM optical networks, it is required to allocate a full wavelength to a traffic demand, the full wavelength is not utilised most of the times, and it causes spectrum wastage. These drawbacks of WDM optical networks lead to the search for a new technology known as Elastic Optical Networks (EONs), which makes use of orthogonal frequency division multiplexing (OFDM) to allocate bandwidths. EONs provide flexible spectrum allocation and contribute to high-speed all-optical data communications [4, 5]. In EONs, each spectrum link is sliced up into a number of frequency slots (FSs), and the demands are fulfilled by allocating the required number of contiguous slots. This contributes a lot towards reduction in spectrum wastage and improves both flexibility and scalability. Due to the benefits of EONs, researchers acknowledged it as the next-generation high-speed network.

The data carried by EONs are transmitted through a high-speed network; a traffic demand passing through optical fibers is susceptible to link failure, which may lead to tremendous data and revenue loss. Survivability against link failure is an essential issue in EONs [6, 7]. A dedicated backup path for each primary path protect against link failures and are considered to be one of the most reliable technique.

In EONs, the spectrum allocation technique must follow three constraints while allocating slots to traffic demands i) spectrum continuity constraint: it indicates that a traffic demand should have same spectrum slots allocated in all links, ii) spectrum contiguity constraint: it indicates that the allocated spectrum slots to a traffic demand should be adjacent to each other, iii) spectrum non-overlapping constraint: it indicates that if a spectrum slot is allocated to any traffic demand, then it must not be allocated to any other traffic demand [8]. In EONs, traffic demands arrive and leave dynamically; this and the enforcement of spectrum allocation constraints leads to spectrum fragmentation. Fragmentation is a problem in spectrum allocation technique in which we cannot allocate slots to traffic demands even if the required number of slots are available, because the slots are not contiguous along the route [9, 10]. Spectrum fragmentation emerged as a severe concern for EONs researchers.

We consider three different policies of spectrum allocation to manage fragmentation and also protect the multicast traffic demands against single link failure. A light-tree based routing is incorporated. For each primary light-tree, a link-disjoint secondary light-tree is found. To manage fragmentation, required spectrum is allocated to primary and secondary light-trees using one of the three policies of spectrum allocation. We have also considered a traffic grooming based approach with our proposed approach. After a tree is constructed, the grooming algorithm is called to check whether any existing active traffic demand is having a tree similar to that of the incoming traffic demand. The traffic demands which are possible to be groomed are routed together and their cumulative spectrum slots are allocated to all links of the routing tree using first-fit spectrum allocation. It is observed that the grooming approach has less bandwidth blocking probability and more free contiguous slot blocks compared to its non-grooming counterpart.

2 Related study

Many protection based approaches in EONs have been reported in literature all through the last decade.

In [11], the authors compare different protection methods for the case of multicast-only traffic and another case that considers multicast, anycast, and unicast traffic in EONs. The authors propose a method of protection that employs segment-based protection strategy and with an additional feature of changing modulation format within a multicast tree. The authors also propose a partial protection method to protect only some receiver nodes. The simulation results show that the proposed approach accept more traffic and save more optical resources. The authors in [12], propose a p-cycle protection method under dynamic traffic scenario in EONs. They propose a method to integrate protected working capacity envelope-p-cycle design with spectrum planning and to solve the coverage problem associated with it. The authors aim to reduce backup path lengths by adopting a topology partition policy. According to the simulation results, the proposed method has a lower blocking probability compared to shared path protection method. In [13], the authors propose a shared protection method that analyze the link between the spectrum consumption and joint failure probability of primary and backup paths. This algorithm finds the minimum spectrum block consumption. Authors propose two other algorithms, maximum shared spectrum block consumption algorithm, and conventional shared spectrum block consumption. The result section present and analyze the relationship between minimum spectrum block consumption and average joint failure probability. In [14], the authors investigate shared-path protection in EONs. They propose two methods of backup path sharing, aggressive method, and conservative method. The difference between these two methods are, in aggressive method two backup paths can share backup resources even if they differ in bandwidth. For the conservative method, two backup paths need to have the same bandwidth to share backup resources. The simulation results conclude that aggressive policy is better than conservative policy regarding capacity utilisation efficiency. In [15], the authors propose a dynamic load balancing shared-path protection algorithm that combines spectrum resource sharing of the backup path, traffic-aware restoration, and dynamic load balancing. As a result, traffic becomes evenly distributed, better utilisation of spectrum is attained, and achieves better survivability. In [10], the authors provide a 1+1 dedicated path protection along with a hitless defragmentation approach in EONs under a dynamic traffic environment. This approach reallocates backup paths for defragmentation because backup paths are used only when there is a failure. The reallocation process also does not create service disruption. This approach enhances resource utilisation. The authors in [16] present a segment based survivability scheme for both static and dynamic traffic. The authors propose two approaches and add regenerators to both algorithms to achieve improved performance. The metrics used to evaluate the simulation results are blocking performance and resource usage performance. The proposed algorithms improve performance compared to traditional methods. In [17], the authors propose an efficient dynamic routing and spectrum allocation approach in multi-fiber EONs. The authors use a multi-path selection technique to route any traffic demand and a fragmentation-aware spectrum allocation (SA) policy. They present a SA policy that optimizes the state of a network after spectrum allocation. The simulation results reveal that the proposed approach performs better than the standard approaches regarding demand blocking ratio and bandwidth fragmentation. The authors in [18], present a solution for the dynamic routing and SA solution in EONs with mixed line rates. The authors provide a multi-constrained routing technique and two allocation policies that could reduce bandwidth fragmentation and bandwidth usage. They use different routing strategies in the evaluation process. The result analysis reveals that the proposed routing and SA solution in the dynamic scenario has better blocking probability and reduce spectrum fragmentation compared to other baseline approaches in a dynamic scenario. In [19], the authors propose a dynamic routing and SA solution in transparent optical networks. The proposed solution considers traffic bit-rates and their relationship with spectrum bandwidth, and it also satisfies spectrum continuity constraint and transmission distance constraint. The proposed solution is designed in a manner so that it supports both flexible-grid and fixed-grid optical network architectures. The authors design a programming model for the proposed method and provide some solutions that are based on the segment representation of the spectrum. According to simulation result analysis, the modulation-adaptive solution performs better regarding capacity blocking than a non-adaptive approach. The authors in [20] study different routing and spectrum allocation methods and introduce fragmentation reducing techniques. The objective behind proposing several techniques is to reduce computation complexity and increase performance efficiency. The routing and spectrum allocation processes are split into three steps: network resource evaluation, routing, and spectrum allocation. The incoming traffic bandwidth and distribution of traffic bandwidth are considered in the network resource evaluation step. Two approaches are proposed: fragmentation-aware load-balanced shortest path routing and fragmentation-aware load balanced k-shortest path routing. These two approaches achieve standard blocking performance and with less computational complexity. The simulation results reveal that proposed approaches improve network accommodation capacity. In [21], the authors investigate two protection policies: full 1+1 protection path policy and quasi 1+1 protection path policy, along with route-partitioning based de-fragmentation approach. This approach aims to reduce blocking probability and to minimize retuning interference. The type of traffic considered here is unicast and so light-path based routing is used. Different settings and various networks are used to evaluate the proposed approach and this approach is compared with state-of-the-art approaches.

In the existing works, we did not find any approach that considers both fragmentation management and protection approach considering light-tree based routing (or for multicast traffic demands). This motivated us to investigate and propose an approach that considers protecting traffic demands and also adopts fragmentation managing policies for dynamic multicast traffic demands.

3 Problem formulation

In this section, we provide an integer linear programming (ILP) formulation for protection and fragmentation management problem in EONs.

For each traffic demand, the ILP needs to determine which links are to be included in each tree (primary and backup). The paths of both primary and backup tree will be determined based on the constraints of the ILP.

• Assumptions

  • 1. The network nodes do not have spectrum conversion capability.

  • 2. Total number of slots per link is fixed.

  • 3. Dividing of a traffic demand into multiple low-speed traffic demands are not allowed.

• Notations

  • G(V, E): G represents physical network. V represents vertices set and E represents edges set.

  • B: represents the highest number of slots per link.

  • i: represents $i^{th}$ traffic demand of the set R, where R is set of all multicast traffic demands and |R| is denoted by $\rho$.

  • $S_{i}$: represents source of $i^{th}$ traffic demand.

  • $D_{i}$: represents destination set $\{d_{1},d_{2}\ldots d_{n}\}$ of $i^{th}$ traffic demand.

  • $b_{i}$: represents bandwidth requirement for $i^{th}$ traffic demand.

  • $T_{i}$: represents multicast trees $\{t_{1},t_{2}\ldots t_{k}\}$ possible for $i^{th}$ traffic demand and $|T_{i} |$ is denoted by $\tau$.

  • e: represents $e^{th}$ link, $e \in E$

  • $L_{i,t}$: if $t^{th}$ tree is selected for $i^{th}$ traffic demand, then $L_{i,t}$ represents value of number of links in this selected tree.

• Design variables

  • 1. $PX_{t,i}$: represents a boolean variable, it will be 1, if $t^{th}$ tree is selected as primary tree for $i^{th}$ traffic demand, otherwise it will be 0.

  • 2. $BX_{t,i}$: represents a boolean variable, it will be 1, if $t^{th}$ tree is selected as backup tree for $i^{th}$ traffic demand, otherwise it will be 0.

  • 3. $P^{i}_{e}$: represents a boolean variable, it will be 1, if for $i^{th}$ traffic demand, the link e belongs to primary tree, otherwise it will be 0.

  • 4. $B^{i}_{e}$: represents a boolean variable, it will be 1, if for $i^{th}$ traffic demand, the link e belongs to backup tree, otherwise it will be 0.

  • 5. $slot_{i,e}$: If traffic demand i has link e in either primary or backup path then the variable $slot_\mathrm{{i,e}}$ has value equal to the number of slots allocated to that traffic demand, otherwise its value is 0.

  • 6. $start_{i,e}$: If link e of traffic demand i is allocated, then value of this variable contains the starting slot index of link e in the slot matrix, otherwise the value is 0.

  • 7. $end_{i,e}$: If link e of traffic demand i is allocated, then value of this variable contains the ending slot index of link e in the slot matrix, otherwise the value is 0.

• Objective function

  $$ {\text{Minimize}}\quad {\text{TSU}} = {\text{ PSU}} + {\text{BSU}} $$

  (1)
  $${\text{BSU}} = {\text{ }}\sum\limits_{{i = 1}}^{{i = \rho }} {\sum\limits_{{t = 1}}^{{t = \tau }} {L_{{i,t}} } } *b_{i} *BX_{{t,i}} {\text{ }}$$

  (2)
  $$ {\text{PSU}} = {\text{ }}\sum\limits_{{i = 1}}^{{i = \rho }} {\sum\limits_{{t = 1}}^{{t = \tau }} {L_{{i,t}} } } *b_{i} *PX_{{t,i}} {\text{ }}$$

  (3)

  The primary slots utilisation (PSU) is equal to number of slots required by a traffic demand multiplied with number of links in the primary tree. Similarly, average backup slot utilisation (BSU) is equal to number of slots required by a traffic demand multiplied with number of links in the backup tree. TSU is the total slot utilisation which means the total number of slots utilized in a network.

• Constraints

  $$\begin{aligned} \sum _{i=1}^{i=R} b_{i} \le B \end{aligned}$$

  (4)

  For each link, the sum of all the slots required among all the demands using that link (in primary or backup tree) should not exceed the total number of slots on that link.

$$\begin{aligned} L_{i,t} \le V-1, \quad \forall i \in R, \quad \forall t \in T_{i} \end{aligned}$$

(5)

The ILP will determine the primary and backup tree for each traffic demand. For traffic demand i, links of tree t must be either less than or same as one minus sum of all vertices of graph $G's$. This is expressed by constraint in eq. (5)

$$\begin{aligned} L_{i,t} \ge |D_{i} |, \quad \forall i \in R, \quad \forall t \in T_{i} \end{aligned}$$

(6)

We have computed candidate trees for each traffic demand. For traffic demand i, links of tree t must be more or same as the destination set size of $i^{th}$ traffic demand. This is expressed by constraint in eq. (6).

$$\begin{aligned} \sum _{t=1}^{t=|T_{i} |} PX_{t,i} =1, \quad \forall i \in R, \quad \forall t \in T_{i} \end{aligned}$$

(7)

For a traffic demand i, a single tree will be selected as its primary tree, out of all the trees. This is expressed by constraint in eq. (7)

$$\begin{aligned} \sum _{t=1}^{t= |T_{i} |} BX_{t,i} =1, \quad \forall i \in R, \quad \forall t \in T_{i} \end{aligned}$$

(8)

For a traffic demand i, a single tree will be selected as backup tree, out of all trees. This constraint is expressed by eq. (8).

$$\begin{aligned} PX_{t,i} + BX_{t,i} \le 1, \quad \forall i \in R, \quad \forall t \in T_{i} \end{aligned}$$

(9)

The primary tree and backup tree should not be the same for each t and i. This constraint is expressed by eq. (9).

$$\begin{aligned} P^{i}_{e} + B^{i}_{e} \le 1 \end{aligned}$$

(10)

The value of $P^{i}_{e}$ will be 1 only when the value of $PX_{t,i}$ is 1. Similarly, the value of $B^{i}_{e}$ will be 1 only when the value of $BX_{t,i}$ is 1. The constraint in eq. (10) indicates that link e can be used either in primary tree or in backup tree but it cannot be used in both.

$${\text{start }}i,e_{1} = {\text{start}}_{{i,e_{2} }} = \ldots = {\text{start}}_{{i,e_{n} }} ,\quad \forall e_{1} ,e_{2} \ldots e_{n} \in E $$

(11)

The constraint in eq. (11) indicates, that for any traffic demand, all the links in primary tree of $i^{th}$ traffic demand should have same starting slot index. Similarly, all the links in the backup tree will have same starting slot index. However the start time slot index depends on slot allocation method which depends on contiguity of free slots, hence the start slot index of primary tree and backup tree may or may not be same, it will depend on free slots.

$$ {\text{end}}_{{i,e_{1} }} = {\text{end}}_{{i,e_{2} }} = \ldots = {\text{end}}_{{i,e_{n} }} ,\quad \forall e_{1} ,e_{2} \ldots e_{n} \in E $$

(12)

The constraint in eq. (12) indicates, that for any traffic demand, the ending slot index of all links in primary/backup tree of $i^{th}$ traffic demand should be same.

$$\begin{aligned} end_{i,e} - start_{i,e} + 1 = b_{i}, \quad \forall i \in R, \quad e \in E \end{aligned}$$

(13)

The constraint in eq. (13) indicates, that one more than the difference between the starting and ending slot indices of any traffic demand should be equal to the bandwidth demanded.

$$ {\text{start}}_{{i,e}} \le B - b_{i} + 1,\quad \forall i \in R,\quad e \in E $$

(14)

Any link’s start slot index corresponding to a traffic demand must be less than or same as one more than the difference between maximum slots in the link and bandwidth required for that traffic demand. This constraint is expressed by eq.( 14).

$$ {\text{end}}_{{i,e}} - {\text{start}}_{{i,e}} \le {\text{slot}}_{{i,e}} ,\quad \forall i \in R,\quad e \in E{\text{ }} $$

(15)

The value of $\text{slot}_{i,e}$ is true only when either value of $P^{i}_{e}$ is true or $B^{i}_{e}$ is true. The number of allocated slots in each link of each traffic demand will be more than the difference of ending and starting slot indices. This constraint is expressed by eq. (15).

4 Proposed approach

The given network topology is represented by G(V, E), where V denotes the set of vertices in the network and E denotes the set of bidirectional links. The multicast traffic demand is represented by $\{S,\{D\}\}$, where S is the source, $\{D\}$ represents the destination set. The bandwidth requirement for $i^{th}$ traffic demand is denoted as $b_{i}$ and the holding time is denoted as $h_{i}$. We have selected various modulation formats depending on the path length of a traffic demand. When the path length of a traffic demand is reduced, we select a less robust modulation format, which helps to improve spectrum utilization of the network.

The fragmentation index of any link is defined by the ratio of number of contiguous blocks ($N_\mathrm{{cf}}$) by the total number of free slot blocks ($N_\mathrm{{f}}$). It is shown by the Eq.(16). The fragmentation index is computed after spectrum allocation to verify that whether it leads to spectrum fragmentation. The fragmentation index is calculated for each link in the network and the link with the lowest value of fragmentation index corresponds to the most fragmented link.

$$ {\text{Fragmentation Index (FI)}} = \frac{{N_{{{\text{cf}}}} }}{{N_{{\text{f}}} }} $$

(16)

Specifically, if we have a free spectrum slice constituted to $\alpha$ frequency slot units (size of the slice), this spectrum slice will contribute with $\alpha -1$ free consecutive frequency slot units. The one slot is deducted because it indicates the guard band slot For example, consider an elastic optical network with 10 frequency slot units on each link and a given link comprises of two non-contiguous blocks with 4 and 2 free frequency slot units, will have FI value as 0.6667 ( $N_\mathrm{{cf}} = 3 + 1 = 4$ and $N_\mathrm{{f}} = 4 + 2 = 6$). For calculating $N_\mathrm{{cf}}$, we have added 3 (4-1) with 1 (2-1), since 4 frequency slot units contribute to 3 free consecutive frequency slot units and 2 frequency slot units contribute to 1 free consecutive frequency slot units.

The fragmentation index of a traffic demand is the sum of the fragmentation indices of all the links of the multicast tree constructed for that traffic demand.

Fragmentation rate FR is defined below, we have used this metric for comparison with the metric FI.

$$\begin{aligned} \text {Fragmentation Rate} (f_{rl}) = \frac{Q_{el}}{W-\sum _{j=1}^{W} B_{l}(j)} \end{aligned}$$

(17)

where $f_{rl}$ is the fragmentation rate per link, $Q_{el}$ stands for maximal contiguous block of free frequency slots on the link $e_{l} \in E$. W is the total number of frequency slots per link and $B_{l}(j)$ represents the $j^{th}$ frequency slot of the link $e_{l}$, if the link is occupied. The value of $B_{l}(j)$ is equal to 1 when the link is occupied otherwise $B_{l}(j)$ is 0. FR is the summation of $f_{rl}$ for all links.

We have considered the same example which was used to compute the Fragmentation Index in eq 16, to compute Fragmentation rate metric given in eq 17. For this example, the fragmentation rate value is 1.5, while the fragmentation index value is 0.6667.

The proposed approach first constructs a primary shortest path tree and a link disjoint backup path tree corresponding to each primary tree of a multicast traffic demand, using Dijkstra’s shortest path algorithm [22] and constructing a tree from individual shortest paths. The slot matrix is virtually divided into two halves, we consider the first half to be primary slot matrix and second half to be backup slot matrix.

For each incoming traffic demand, allocate slots in primary slot matrix and backup slot matrix by using one of the three policies, given as follows.

• Policy 1: According to the first policy, primary tree of a traffic demand is placed in the primary slot matrix and the backup tree is placed in backup slot matrix.

• Policy 2: Both primary and backup trees are placed in the primary slot matrix.

• Policy 3: Both primary and backup trees are placed in the backup slot matrix.

Also, note down the fragmentation index in all the policies. We allocate the slots using the policy, which gives the highest FI. If two or more policies have the same highest FI, we use the policy having the least highest index slot and update the permanent slot matrix accordingly.

Dijkstra’s shortest path algorithm is used to find the shortest path from single source to a destination, we consider the union of all the shortest paths computed for source to each destination node. The resulting tree is a shortest path multicast (SPT) [23].

The proposed scheme is explained with an example. We consider a network topology shown in Fig. 1 and a set of traffic demands shown in Table 1. Figs. 2, 3, and  4 show the primary and backup multicast trees for the three traffic demands, respectively.

Fig. 1

Physical network topology

Table 1 Sample input traffic demands

Fig. 2

Primary and backup tree for traffic demand $r_{1}$

Fig. 3

Primary and backup tree for traffic demand $r_{2}$

Fig. 4

Primary and backup tree for traffic demand $r_{3}$

We virtually divide the slot matrix into two halves, consider the first half as the primary slot matrix and the second half as the backup slot matrix. The slot allocation of traffic demands is based on the selected policy, which achieves the highest FI value.

The FI value is computed for each link of a traffic demand by using eq. (16), then the sum of FI for all the links are calculated, corresponding to the allocation shown in Fig. 5. The Total FI for traffic demand $r_{1}$ will be sum of FI values of individual links. The total FI value for traffic demand $r_{2}$ and $r_{3}$ are calculated in the same way (sum of FI values of individual links), corresponding to the allocations shown in Figs. 6 and 7 respectively.

The policy which provides the highest FI value is considered better than other policies. Greater values of FI means that the free frequency slots of the links are less fragmented. The FI of traffic demand $r_{1}$ is 0.88, 0.64, and 1.05 using policies one, two, and three, respectively. Traffic demand $r_{1}$ is allocated by using policy three because it has the highest FI value. The FI of traffic demand $r_{2}$ is 1.23, 1.12, and 1.39 using policy one, two and three respectively. Traffic demand $r_{2}$ is allocated by using policy three because it has the highest value of FI. The FI of traffic demand $r_{3}$ are 1.72, 1.62 and 1.92 using policy one, two and three respectively. Policy three is selected as it has the highest FI value. If there is tie in FI values of any two policies, then the highest slot index used is checked, the policy having the lowest highest slot index is selected.

Our algorithm is designed in such a way that we try to find free contiguous blocks in both primary slot block and backup slot block. We select the policy for allocation where there will be more free contiguous slot blocks both in the primary partition and in the backup partition.

Figures 5, 6, and  7 illustrates the slot allocation matrices, after allocating the traffic demands for both primary and backup tree for traffic demands one, two and three, respectively. The filled colored boxes indicate allocation for the primary tree, and the diagonally dashed boxes indicate allocation for the backup tree in the slot matrices. In the final slot matrix, the contiguous blocks available after allocating the traffic demands are shown by dashed lines. Two contiguous blocks are obtained, as shown in Fig. 7.

Fig. 5

After allocating traffic demand $r_{1}$ using policy 3

Fig. 6

After allocating traffic demand $r_{2}$ using policy 3

Fig. 7

After allocating traffic demand $r_{3}$ using policy 3

The spectrum allocation matrix after allocating traffic demands $r_{1}$ through $r_{3}$ using traditional spectrum allocation is shown in Fig. 8. In this approach, the primary tree links are allocated in the primary slot matrix, and the links of the backup tree are allocated in the backup slot matrix.

Fig. 8

After allocating traffic demands $r_{1}$ through $r_{3}$ using traditional spectrum allocation

Spectrum is allocated for traffic demands $r_{1}$ through $r_{3}$ using the toggling approach for multicast traffic demands. Figure 9 shows this. The toggling approach exists for unicast traffic demands [24], and we have modified it and made it suitable for multicast traffic demands. In this approach, the links of the primary tree and the links of the backup tree are exchanged before allocation.

The proposed approach has two contiguous blocks in the primary half and backup half of the slot matrix available among all the network links.

Our proposed approach provides dedicated protection and as well as reduced fragmentation compared to traditional and toggling approaches.

Fig. 9

After allocating traffic demands $r_{1}$ through $r_{3}$ using toggling based spectrum allocation

5 Performance analysis

This section is divided into two subsections, in the first subsection to evaluate the presented ILP formulation, we consider a five nodes sample network and a seven nodes sample network, as shown in Figs. 10 and  11, respectively. We compare the ILP results with the proposed heuristic results in terms of average primary slots utilisation and average backup slots utilisation.

In the second subsection, we evaluate the performance results of the proposed heuristic approach, we consider two standard network topologies, namely the national science foundation (NSF) network with 14 nodes [25] and European network with 28 nodes [26], for simulation. The metrics used to evaluate the performance of the proposed approach are bandwidth blocking probability, fragmentation index, average primary slots utilisation and average backup slots utilisation.

5.1 ILP result analysis

The IBM ILOG CPLEX Optimization Studio, version 12.7 is used to solve this ILP. A set of multicast traffic demands are generated randomly for the considered networks, and this is shown in Table 2. For three traffic demands, we select the first three traffic demands from Table 2. Similarly, for six and nine traffic demands, we consider the first six and all nine traffic demands from Table 2, respectively. The bandwidth requirement of each traffic demand is shown in Table 2, in terms of the number of frequency slots required. Table 3 compares results for ILP and the proposed approach.

Fig. 10

Sample 5 nodes network

Fig. 11

Sample 7 nodes network

Table 2 Input data set for networks

Table 3 Results of ILP and heuristic approach

The Table 3 compares the ILP results of average primary slot utilisation and average backup slot utilisation with that of the heuristics approach for two sample networks having 5 nodes and 7 nodes respectively. The results signifies that the proposed heuristic approach gives the result of average primary slot utilisation and average backup slot utilisation close to the optimal results as achieved from ILP solution.

It is evident from Table 3 that the ILP results for average primary and backup slots utilisations are less than that of the proposed heuristic approach because ILP results are optimal, and as our objective function is to minimize average slots utilisation, the ILP results provide minimum values of average primary and backup slots utilisations. It is observed that the proposed heuristic approach shows reasonable performance when compared with the ILP results. The ILP model is applicable only to small networks, it is computationally complex to get ILP results for large networks, hence for larger networks a heuristic approach is desirable to obtain results.

5.2 Result analysis of proposed approach

The proposed approach is evaluated in this subsection. The network topologies and distance among nodes are shown in Figs. 12 and 13 for the NSF network and European network, respectively. We consider each fiber has 320 spectrum slots. We consider both sub-wavelength and super-wavelength traffic demands. The bandwidth requirement for each traffic demand lies in between {1, 2, 3, 4, 5} frequency slots. Each fiber links has a fixed capacity which can be granulated into a finite number of frequency slots. If Binary Phase-Shift Keying (BPSK) modulation technique is used, we consider each slot has a width of 12.5 GHz.

Fig. 12

NSF network

Fig. 13

European network

The multicast traffic demands are generated randomly based on a Poisson distribution process with arrival rate $\lambda$, and the holding time of traffic demands follows an exponential distribution $(H = 1/\mu )$. The network load is used to measure the load in the network at a particular instance of time. The holding duration belongs to {30, 40, 50, 60} s. A traffic is generated and after a time period it gets terminated, so a simulation session comprises of a traffic generation session and a traffic termination session. Thus network loads vary depending on the simulation sessions. If $\delta _{t}$ is the number of traffic demands generated per unit time and $A_{h}$ is the average holding time, then the network load is defined as: $\mathrm{Network~load} = \delta _{t} \times A_{h}$.

We compare our proposed approach with two other approaches, one of the approach is a traditional approach where the primary tree is allocated in primary slot matrix, and the backup tree is allocated in backup slot matrix, and another approach is a toggling based approach, where primary paths of the primary tree are exchanged with backup paths of the backup tree before allocation. The recent existing works relevant to our proposed approach are unicast based approaches, we could not find any multicast based approach in the literature. A toggling based approach exists for unicast traffic demand [24]. We modify it to make it suitable for multicast traffic demands and comparable with our proposed approach.

Figures 14 and 15 show the relationship between network load and bandwidth blocking probability in the NSF network and European network, respectively. The bandwidth blocking probability is defined as the ratio of the amount of bandwidth blocked to the total amount of bandwidth offered in the network. The percentage decrease in bandwidth blocking probability value of the proposed approach is 12% as compared to traditional approach and 10 % as compared to toggling approach for NSF network. The percentage decrease in bandwidth blocking probability value of the proposed approach is 11% and 10% compared to traditional and toggling approaches respectively for European network.

The proposed approach has less bandwidth blocking probability compared to the traditional and toggling approaches because, in this method, a suitable policy of spectral allocation is selected such that more free contiguous spectrum blocks are available for future incoming traffic demands which in turn results in reduced-bandwidth blocking probability.

Fig. 14

Relationship between Bandwidth blocking probability and Network load in NSF network

Fig. 15

Relationship between Bandwidth blocking probability and Network load in European network

Figures 16 and 17 show the relationship between network load and fragmentation index in the NSF network and European network, respectively. The fragmentation index indicates the ratio of the number of free contiguous spectrum blocks to the current total number of free spectrum blocks. The proposed approach has a higher fragmentation index compared to the other two approaches, which means the proposed approach has more free contiguous spectrum blocks. The percentage increase in FI value of the proposed approach is 21% as compared to traditional approach and 22 % as compared to toggling approach for NSF network. The percentage increase in FI value of the proposed approach is 15% and 17% compared to traditional and toggling approaches respectively for European network.

Figures 16 and 17 indicate that as the network load increases, the FI advantage of the proposed approach is more significant that other approaches. The FI is higher for the proposed approach because it checks three different policies for spectrum allocation and selects the one policy which provides the highest FI. When the network load increases, more free and continuous frequency slots are available in the proposed approach compared to the other two approaches.

Fig. 16

Relationship between FI and Network load in NSF network

Fig. 17

Relationship between FI and Network load in European network

The average slot utilisation for primary resources and backup resources for the NSF network are shown in Figs. 18 and 19 respectively. Figures 20 and 21 show the average primary slot utilisation and average backup slot utilisation for the European network, respectively. We have used the formula of average slot utilisation as given in [27].

Fig. 18

Relationship between average primary slot utilisation and network load in NSF network

Fig. 19

Relationship between average backup slot utilisation and network load in NSF network

Fig. 20

Relationship between average primary slot utilisation and network load in European network

Fig. 21

Relationship between average backup slot utilisation and network load in European network

It is observed that for NSF network, all three approaches have similar average backup slot utilisation, and the proposed approach has less average primary slot utilisation compared to the other two approaches. For the European network, the proposed approach has less average primary slot utilisation compared to toggling and traditional approaches, while average backup slot utilisation is similar in all three approaches. It is observed that the average slot utilisation is similar in the three approaches because the average hop count of the three approaches is similar, and according to the average slot utilisation formula, it is directly proportional to average hop count.

Following computations are involved in analyzing the time complexity of the algorithm used here. First of all, in algorithm 1 Dijkstra’s algorithm is implemented twice for each request. Dijkstra’s algorithm is implemented without heaps. So, the time complexity of algorithm 1 comes out to be $O(nV^2)$, where n is the number of traffic demands and V is the number of vertices in the given network topology. Again, in algorithm 2, we are calculating the Fragmentation Index for all the three policies. So, the time complexity of algorithm 2 is $O(nV^2Sp)$. Here, n is the number of traffic demands, S is the number of slots, V is the number of vertices and p is the number of policies. Then, overall time complexity of both algorithms 1 and 2 is $O(nV^2)$ + $O(nV^2S)$ = $O(nV^2S)$. The time complexity of the proposed approach is p times more than the traditional approach and the toggling approach as Fragmentation Index is calculated for p different policies. The comparison of time complexities of the different approaches is shown in Table 4.

Table 4 Comparing Time Complexity of Different Approaches

The proposed approach has more time complexity than the traditional and toggling approaches because fragmentation indexes has to be calculated for p different policies as shown in Table 4. The percentage increase in FI value of the proposed approach is 21% as compared to traditional approach and 22 % as compared to toggling approach for NSF network. The percentage increase in FI value of the proposed approach is 15% and 17% compared to traditional and toggling approaches respectively for European network. The percentage decrease in bandwidth blocking probability value of the proposed approach is 12% as compared to traditional approach and 10 % as compared to toggling approach for NSF network. The percentage decrease in bandwidth blocking probability value of the proposed approach is 11% and 10% compared to traditional and toggling approaches respectively for European network. Our aim is to increase the number of available free and continuous frequency slots and decrease the bandwidth blocking probability of the traffic demands, which is being achieved by the proposed approach in spite of the time complexity being just p times higher than traditional and toggling approaches.

If we want to integrate traffic grooming with the proposed approach, then the algorithm 3 is used.

After a tree is constructed, the grooming algorithm is called to check whether any existing active traffic demand is having a tree similar to that of the incoming traffic demand. If grooming is possible, then after grooming of the traffic demands, cumulative spectrum slots are allocated to all links of the routing tree using first-fit spectrum allocation. We incorporate traffic grooming module to the proposed approach, and their results are evaluated. BBP stands for Bandwidth Blocking Probability. G-proposed stands for the approach proposed with the grooming technique.

The relationship between BBP and network load for the grooming based proposed approach, G-proposed, the proposed approach (without grooming), toggling and traditional approaches are compared.

The BBP performance with respect to network load is shown in Figs. 22 and 23.

Fig. 22

Comparison between grooming and non-grooming approaches with respect to BBP and network load in NSF network

Fig. 23

Comparison between grooming and non-grooming approaches with respect to BBP and network load in European network

It is observed that G-proposed approach has less BBP compared to non-grooming approaches because grooming does not require additional guard band slots and saves spectrum as a result the bandwidth blocking is less in grooming approach.

The fragmentation index performance with respect to network load is shown in Figs. 24 and 25, and we have assumed the number of destination set size is three. The relationship between fragmentation index and network load for the grooming based proposed approach, G-proposed, the proposed approach (without grooming), toggling and traditional approaches are compared.

Fig. 24

Comparison between grooming and non-grooming approaches with respect to fragmentation index and network load in NSF network

Fig. 25

Comparison between grooming and non-grooming approaches with respect to fragmentation index and network load in European network

It is observed that G-proposed approach has higher fragmentation index compared to non-grooming based proposed approach. The G-proposed approach perform better compared to its non-grooming counterpart because less number of slots are used in grooming based approach, so more available free slot blocks are available and thus fragmentation index increases.

The average primary slot utilization performance with respect to network load is shown in Figs. 26 and 27. It is observed that grooming approach has less average primary slot utilization compared to non-grooming approaches because grooming ensures better utilization of spectral resources and reduces spectrum wastage due to guard band slots.

Fig. 26

Comparison between grooming and non-grooming approaches with respect to average primary slot utilization and network load in NSF network

Fig. 27

Comparison between grooming and non-grooming approaches with respect to average primary slot utilization and network load in European network

The average backup slot utilization performance with respect to network load is shown in Figs. 28 and 29.

Fig. 28

Comparison between grooming and non-grooming approaches with respect to average backup slot utilization and network load in NSF network

Fig. 29

Comparison between grooming and non-grooming approaches with respect to average backup slot utilization and network load in European network

It is observed that grooming approach has less average backup slot utilization compared to non-grooming approaches because grooming reduces spectrum wastage due to guard band slots and so slot usage is less for grooming approach.

6 Conclusion

The two most important aspects of Elastic optical network are link protection and fragmentation as with the increasing number of Internet users, it has become a challenge for the ISPs(Internet Service Providers)to provide a secure connection in less amount of bandwidth(here, frequency slots). The research area involved in this paper deals with the same. For a multicast traffic demand, to protect the link against single link failure, a dedicated protection approach is used. Every traffic demand has two paths which are link disjoint from each other. Thus, there is a maximum chance that the traffic demand will not suffer from link failure. Again, for reducing fragmentation, three policies are used to serve the traffic demand. The index used for measuring the fragmentation is named as fragmentation index. The policy having the highest fragmentation index is selected. The higher the fragmentation index, the more is the number of free contiguous spectrum slots. The simulations are performed on two standard network topologies, NSF network and European network. On comparing the proposed approach with traditional and toggling based approaches, it is found that the proposed approach has less bandwidth blocking probability. Thus, we are able to satisfy more number of traffic demand in less number of frequency slots, which was the main goal.

If any of the sections are not relevant to your manuscript, please include the heading and write ‘Not applicable’ for that section.

Editorial Policies for:

Springer journals and proceedings: https://www.springer.com/gp/editorial-policies

Nature Portfolio journals: https://www.nature.com/nature-research/editorial-policies

Scientific Reports: https://www.nature.com/srep/journal-policies/editorial-policies

BMC journals: https://www.biomedcentral.com/getpublished/editorial-policies