The current optical networks are facing a serious shortage of optical resources triggered by the exponential growth of the new emerged diversified services, such as high-definition video distribution, social networking, and cloud computing, which makes the current optical networks face the unprecedented challenges and the undue pressure in terms of the optical resource utilization [1-4]. The future internet network is in urgent need of a spectrum-efficient, data-rate flexible, and low latency optical network. To address this problem, an optical-orthogonal frequency division multiplexing (O-OFDM) enabled EON has emerged to alleviate pressure of spectrum shortage [5-8]. With the help of the advanced liquid crystal-on-silicon (LCOS) WSS over the O-OFDM, the optical resource of wavelength is changed into a spectrum of much finer spectral granularity by slicing the wavelength into narrow frequency interval, e.g. 6.25 GHz or 12.5 GHz. Thus, the services could be allocated with just enough spectrum slots in traffic bandwidth reconfiguration and modification through the super-channels, sub-channels [9-12].

To deal with the optical resource shortage problem and improve the spectrum utilization further, RSA has also attracted many researchers’ attention and has been widely studied in recent years. The existing research studies of RSA can be generally divided into the static RSA [13], the dynamic RSA [14], the fragmentation-aware RSA [15], distance-adaptive RSA [16], and so forth. Based on these RSA studies, we observe that most research studies utilize single-path strategy to accommodate the requests, especially for the unicast service [17]. Such single-path strategy may cause significant spectrum resource overhead based on the single type of BV-transponder over the EON. Moreover, as the traffic load becomes heavy, the random arrival of the services may result in unbalanced network load and low spectrum utilization [18]. However, a multipath routing scheme has been demonstrated to be efficient in balancing the network load, improving the network resource utilization, and guaranteeing the network reliability [19]. Notably, with the help of the O-OFDM technology, the requests can be split over multiple routing paths to occupy the spectrum slots in more efficient way [20, 21].

Besides, multicast draws intensive research interests recently, and it has been viewed as an efficient transmission scheme to connect the source node to the multicast group. Compared with the conventional IP multicast, all-optical multicast has more potential advantages of being more transparent and power-efficient, and transferring petabyte-scale data to the geographically dispersed subscribers [22]. The provisioning of all-optical multicast is a meaningful topic over the EON, due to the huge demand of all-optical multicast based applications. Since now, a few studies of RSA have been performed for multicast over the EON. A layered approach based integrated MC-RSA algorithm is proposed for multicast requests in the EON [23]. The joint ILP and separate ILP models for the multicast provisioning problem in the EON are proposed [24].

Network coding has the advantages of increasing the network throughput, balancing the network load and reducing the optical resource consumption for multicast services. Enabling the potential immediate nodes with the network coding, maximum multicast rate can be achieved over the network coding based multicast networks [25, 26]. After introducing the network coding into the EON, some new optimization problems appear, such as how to further improve the transmission efficiency, the network capacity and the robustness of all-optical multicast. Compared with RSA over the EON [27-29], the elastic resource optimization problem over the network coding based EON becomes more complicated. This is because the network coding operations should be considered as the services transmitting through the network coding node. Notably, RSA for the hybrid unicast and network coding based multicast services over the flexible optical networks is investigated [30]. However, rare research studies the multipath RSA for the single type of multicast services over the network coding enabled EON.

In addition, more and more multicast services, such as the video conferencing applications and the real-time games, have a high demand for the real time communication. For example, if the multicast users in a distributed database system or the online video games cannot receive the message from the source simultaneously, the real-time and fair multicast transmission will not be achieved. Moreover, the buffer sizes are limited in the optical networks, and the QoS constraints should be considered for network applications [31]. The multicast over all-optical network has a higher demand for the real time communication. Thus, the time delay constraint should be considered in the RSA to guarantee the real-time communication for multicast.

In this paper, we mainly investigate the multicast service efficiently provisioning problem over the network coding enabled EON, considering the time delay constraints. To address this problem, an efficient heuristic algorithm is proposed to solve the multipath RSA with the objective of minimizing the total number of the spectrum consumption for multicast services. Besides, two request ordering strategies are utilized to process the multiple multicast requests one by one. We choose three test networks of random networks, the Euro network, and the US network [32], to evaluate the performances of the proposed algorithm. Besides, we also evaluate the impact of the parameter w and two request ordering strategies on the performances of the proposed algorithm.

The rest of the paper is organized as follows. In Section II, we discuss the multipath RSA problem for multicast services over the network coding enabled EON. An efficient heuristic algorithm, called the Network Coding based Multicast Capable Multipath Routing and Spectrum Allocation (NCMC-MRSA), is proposed to solve the multicast service provision problem over the network coding enabled EON. We conduct a series of simulation experiments in different network scenarios to evaluate the performances of the proposed algorithm in Section III. In Section IV, we give the conclusions of the paper.

In this section, we mainly discuss the proposed heuristic algorithm, which mainly solves the multicast services provisioning problem over the network coding enabled elastic optical networks (EONs). The problem can be classified as the static RSA, and the network resources are assumed to be partially used at the beginning. We consider G(V, E ) as a physical graph of the network coding enabled EON, where V indicates the node set, and E indicates the edge set. Specifically, all the intermediate nodes in V are assumed to be capable of combing the messages from their different input links with network coding operations, such as XOR. As a group of multicast services arrive, we propose a heuristic algorithm called Network Coding based Multicast Capable Multipath Routing and Spectrum Allocation algorithm (NCMC-MRSA) to accommodate a set of multicast requests with the minimal spectrum resources. Specifically, we adopt the multipath strategy to serve the multicast requests, considering the time delay constraint. , i ∈ nR_M, is considered as the set of multicast services, where s_i is the source node, D_i is the destination node set of multicast services, n_i is the number of the spectrum slots requirement, and nR_M is the index set of multicast services. The parameter definitions for proposed algorithm NCMC-MRSA are shown in Table 1.

To the best of our knowledge, most existing RSA research investigates over the EON. However, these RSA research is not useful in the network coding enabled EON, due to that all immediate nodes in the network coding enabled EON are capable of combining different data flows with network coding operations. An intuitive example of the routing topologies for multicast in the EON and network coding based EON is shown in Fig. 1. For each source and destination node pair (s, d_i) of multicast request, routing in the EON is to find an end-to-end path p(s, d_i), shown in Fig. 1(a). While, Fig. 1(b) presents that routing in the network coding enabled EON is to establish multiple link-disjoint parallel paths from the source node s to each destination node d_i of multicast group D_i indicated as the path set P(s, d_i). The multicast request is split over multiple routing paths with no common link, and only in this way the original message could be obtained at the destination node side after the decoding operations. It should be noted that the time delay constraint is considered in the routing to guarantee the physical constraint.

The challenge for the proposed algorithm NCMC-MRSA is not only in the establishment of the network coding based multicast tree (NCMT) under the time delay constraint, but also in the stage of the spectrum allocation under the spectrum contiguity constraint and non-overlapping spectrum constraint. Notably, the well-known layered auxiliary graph approach is utilized [23] to solve the spectrum allocation in the network coding enabled EON. With the help of the layered auxiliary graph approach, the NCMC-MRSA solves the multipath routing and spectrum allocation in an integrated way. Besides, we also discuss two request-ordering strategies of the Maximum Spectrum Request Priority (MSRP) and the Spectrum Request Balancing (SRB), as multiple multicast services arrive the network simultaneously.

The detailed procedures of the NCMC-MRSA are explained as follows.

Step 1: As a group of multicast requests arrive, a request ordering strategy, MSRP or SRB, is utilized to accommodate multiple multicast requests sequentially. MSRP indicates that the multicast request required the most number of spectrum slots will be processed with the priority. SRB indicates that the multicast requests are ordered according to the balanced spectrum requirement of the sequenced requests. In other words, the spectrum requirements of the successive multicast requests should not be too large or too small.

Step 2: The multipath routing strategy is utilized to accommodate the multicast services in the way of splitting the request over multiple paths (with the number of w). w is assumed as 2 in order to avoid establishing too many links. Multicast request occupies the spectrum slots with the number of n_i / w on each fiber link.

Step 3: As arrives, the layered auxiliary graph approach [23] is utilized to construct a set of layered graphs, indicated as subG = {subG^g(subV^g, subE^g)}. For each fiber link with the number of spectrum slots of F, the maximum number of the layered graphs over the network coding enabled EON is F − n_i / w + 1. The set of layered graphs is calculated in iterations. In each iteration, if there are continuous spectrum slots with the number of n_i / w from the first spectrum slot to (F − n_i / w + 1)-th on the fiber link, the link will be inserted into subG^g, ∀g ∈ [1, F − n_i / w + 1]. This process can be formulated as subV^g = V, and , where ,b_e[ j ] = 1 indicates that the j-th spectrum slot is used; otherwise b_e[ j ] = 0. The layered graph subG^g is obtained under the spectrum contiguity constraint along the path until all the links are searched. After all the iterations, we obtain the set of layered graphs subG^g, g ∈[1, F − n_i / w + 1] .

Step 4: Then, each obtained layered graph subG^g will be validated if the multicast message can be transmitted from the source node s to the destination node set D_i. If not, the layered graph subG^g is invalid and will be deleted.

Step 5: Based on the valid layered graph, the network coding based multicast tree (NCMT) for multicast request is established in iterations. In each iteration, the routing path from s to d_i,k (k ∈ [1, |D_i|] is established under the time delay constraint adopting the ideas of the Warshall-Floyd algorithm [33]. The weight of all links in the network will be saved in a matrix set W. Then, the status of the occupied spectrum will be labeled as used, and the weight of the connected links on the path will be labeled as Inf in order to establish the link-disjoint parallel path in the next step.

Step 6: Another path from s to d_i,k is established repeating the step 5 until the link-disjoint parallel paths with the number of w(w = 2) are established. Then, the weight of all links in the network will be recovered as W.

Step 7: Repeating step 5 and step 6 until all the destination nodes of D_i are connected with the source node s. A network coding based multicast tree is constructed for . The number of the consumed spectrum slots on all occupied links for , is calculated and saved as Ncfs.

Step 8: Repeat the same processes from step 3 to step 7 until all the multicast services , i ∈ nR_M, are served over the network coding enabled EON. The total number of the occupied spectrum slots for all the network coding based multicast services is calculated and saved as Ncfs.

The pseudocode of the proposed algorithm NCMC-MRSA is described in Table 2.

An intuitive example of the processes of the proposed algorithm NCMC-MRSA is shown in Fig. 2, Fig. 3 and Fig. 4. The exemplary topology of the network coding enabled EON is shown in Fig. 2. As the multicast service arrives at the network coding enabled EON, the utilizing status of all network resources is shown in Fig. 3, and the layered auxiliary graph approach [23] is utilized to solve the spectrum allocation. The request will be transmitted in the multipath strategy, and each link along the path will occupy the spectrum slots with the number of n_i / w (n_i / w = 4). In Fig. 3, each fiber link is assumed to contain F(F = 9) spectrum slots at most, and the total number of the constructed layered graphs is F − n_i / w + 1 (F − n_i / w + 1 = 6). In the example shown in Fig. 3, if there are continuous spectrum slots with the number of n_i / w(n_i / w = 4) from link 1 to link 13 in g-th layer, where 1 ≤ g ≤ F − n_i / w + 1, the links will be inserted into g-th layer, indicated as subG^g. For example, in layer 2, the continuous spectrum slots can be found on the link 4, 6, 8, 9, and 11, indicated as green spectrum block. Then, all these links will be inserted in layered graph 2. However, the layered graph 2 is not valid to transmit the request from the source node s to all the destination nodes of D_i , and it will be deleted from the set of the layered graphs. Four layered graphs are constructed until the value of g ranges from 1 to F − n_i / w + 1, and the constructed layered graphs are shown in Fig. 3. After validating all the layered graphs, only the layered graph 4 is valid to connect the source node s to all the destination nodes of D_i.

Based on the layered graph 4, the multipath strategy is utilized to construct the network coding based multicast tree under the time delay constraint. For each source and destination node pair, w (w = 2) link-disjoint parallel paths are established to achieve the network coding operations. The outgoing link of the network coding node, link 10, is considered as a network coding link. After the paths of the request passing through the network coding node, shown as the node with red dash line, different messages from link 7 and link 8 are combined with XOR, and the message on link 10 is x ⊕ y occupying 4 spectrum slots, other than x and y occupying 8 spectrum slots. At the destination node, the original message can be recovered with the decoding operations. The constructed link-disjoint parallel paths for (s, d₁) and (s, d₂) are shown in blue dash lines and green dash lines in Fig. 4, respectively. Then, the processes of multipath RSA for the multicast request are completed in an integrated way.

In this section, we conduct the simulations with the tool of MATLAB on a 2.5 GHz Intel (R) Xeon (R) CPU with 16 GB RAM memory. The network coding enabled EON is assumed to be deployed in the C band with a ~4.475 THz spectrum, and each fiber link with the single-mode contains 358 frequency slots at most [23]. Given a set of multicast requests , i ∈ nR_M, we investigate the multipath RSA at the static network planning stage, and the initial spectrum resources of EON are assumed to be partially used. It should be noted that we set the number of the link-disjoint parallel links for each s_i → d_i,k to 2. Because the multipath RSA in [34] demonstrates that the optimal heuristic algorithm can be achieved, as the number of candidate paths is less than three. In order to evaluate the performances of the proposed algorithm, we choose three types of the test network scenarios, which are the random networks with both (i) small range (n ≤ 120) and (ii) large range(200 ≤ n ≤ 400), the Euro network (28 nodes and 82 links), and the US network (26 nodes and 84 links) [32].

In order to evaluate the performance of the proposed algorithm NCMC-MRSA, we choose the multicast capable-routing and spectrum assignment, MC-RSA [23], as the benchmark algorithm to compare the spectrum utilization performance with NCMC-MRSA. Note that the time delay constraint is considered into the benchmark algorithm, and the network coding is not considered to provision multicast services utilizing MC-RSA over the EON. Moreover, two request-ordering strategies, MSRP or SRB are utilized by the algorithms, and the time delay constraint is also considered to guarantee the physical constraint. As different parameters increase, such as the average number of the receivers and the number of the network nodes, we compare the performance of the spectrum utilization between NCMC-MRSA and the benchmark algorithm. The total number of the spectrum consumption is chosen as the only parameter to evaluate the performance of the proposed algorithm.

As the average number of the receiver nD increases, Figs. 5(a) and 5(b) show the performance comparisons of the total spectrum consumption in small network and large network respectively. It can be observed that NCMC-MRSA under the request ordering strategy of SRB shows the best performance with the least spectrum consumption to serve all multicast requests among all the algorithms in small networks, shown in Fig. 5(a). As utilizing the same request ordering strategy, we find that NCMC-MRSA outperforms MC-RSA in terms of total spectrum consumption in small networks. Although as the average number of receivers nD increases to 14, total spectrum consumption of NCMC-MRSA shows a minor change, the proposed algorithm also shows more efficiency performance than the benchmark algorithm generally. From the simulation results in Fig. 5(b), we can also find that as the average number of receiver nD increases, NCMC-MRSA performs more efficient in terms of spectrum utilization compared with MC-RSA under the same request ordering strategy in large networks. NCMC-MRSA under the request ordering strategy of SRB also consumes the least spectrum slots to serve all multicast requests among all other algorithms in large networks. It is interesting to find that NCMC-MRSA shows more obvious efficiency of the spectrum utilization in large networks than that in small networks. This can be explained that with the help of network coding, more messages can be transmitted consuming less spectrum slots on the network coding links, and the network load is more balanced, especially utilizing the SRB ordering strategy. Specifically, as the spectrum requirements by multicast services are large and the available spectrum resources are limited, NCMC-MRSA will show more efficient spectrum utilization compared with the benchmark algorithm. Moreover, a large network could provide enough links to establish the NCMTs for multicast requests over the network coding enabled EON. The ideal network scenario for our addressed problem is the fully connected network.

As the node number of a small random network increases, performance comparisons in terms of the spectrum utilization between NCMC-MRSA and MC-RSA with different request ordering strategies of SRB and MSRP are shown in Figs. 6(a) and 6(b), respectively. In Fig. 6, we assume that the node number of the small random network ranges from 20 to 120 with 20 nodes for each step increase, and the average number of the multicast receivers in the corresponding network ranges from 4 to 14 with 2 receivers for each step increase. From the simulation results in Fig. 6, as the node number of small random network n and the corresponding parameter nD increase, NCMC-MRSA shows more efficient spectrum utilization performance compared with the benchmark algorithm under the same ordering strategy SRB or MSRP, respectively. However, as the node number of the small random network is below 30, MC-RSA utilizes less spectrum resources with both ordering strategies compared with NCMC-MRSA. It is interesting to see that as the number of multicast requests increases to 8 in Fig. 6(b), the small random network with the node number of 20 cannot accommodate all these multicast requests adopting both algorithms with MSRP ordering strategy. This is reasonable because small random network cannot provide enough link-disjoint parallel paths or spectrum resources to establish the NCMTs for more multicast requests. It has also been demonstrated in [36] that the performance of network coding is not quite efficient in a small network.

Simulation results in Fig. 7 show the performance comparison in terms of total spectrum consumption between NCMC-MRSA and MC-RSA with the ordering strategy of SRB and MSRP, as the node number of a large random network increases. In Fig. 7, we assume that the node number of a large random network ranges from 200 to 400 with 40 nodes for each step increase, and the average number of the receivers of the corresponding network ranges from 24 to 40 with 4 receivers for each step increase. NCMC-MRSA utilizing the request ordering strategy of SRB outperforms all other algorithms in terms of the spectrum utilization, as the parameter n of large random networks and the corresponding parameter nD increase. It also can be observed that as the parameter n and the corresponding parameter nD increase, NCMC-MRSA shows more efficient performance than MC-RSA in terms of the spectrum utilization using both request ordering strategies of SRB and MSRP in large random network, shown in Figs. 7(a) and 7(b) respectively. Compared with the small random network, NCMC-MRSA outperforms MC-RSA more obviously in terms of spectrum utilization in a large random network. This is reasonable because the large size network could provide enough links to establish the routing topologies for multicast requests over the network coding enabled EON. Furthermore, performance of network coding has verified its efficiency in a large network [36].

Besides, we also evaluate the performance comparison between the proposed algorithm NCMC-MRSA and MC-RSA in terms of total spectrum consumption in the Euro network and the US network in Fig. 8. It can be viewed that as the number of the multicast services increases, MC-RSA is slightly superior to NCMC-MRSA in terms of spectrum utilization in the Euro network and the US network shown in Figs. 8(a) and 8(b), respectively. The similar trend can also be found in small random network with the node number below 30, shown in Fig. 6. Overall, compared with MC-RSA, NCMC-MRSA is less efficient in small networks of both random network and real networks in terms of spectrum utilization. MC-RSA with SRB ordering strategy shows the best performance in terms of the spectrum utilization among other algorithms in the Euro and US networks. Note that NCMC-MRSA under SRB or MSRP in the Euro and the US networks can just solve the multipath RSA problem for two multicast requests at most. This is because the scales of Euro and US networks are too small to establish the routing topologies of NCMTs for more multicast services.

Due to that different request ordering strategies will result in different network resource utilization, it is necessary to evaluate the impact of different ordering strategies on the performances of algorithms in different network scenarios. Performance comparisons between SRB and MSRP using the same algorithm in terms of the total spectrum consumption in random network and real network of the Euro network are shown in Figs. 9 and 10, respectively. Specifically, the simulation experiments are carried out under the random networks with 100 nodes (i), 300 nodes (ii), and the Euro network (iii). We set the average number of multicast receivers to 4 in the scenario (i) and (ii), and 2 in the scenario (iii). From the simulation results in Fig. 9, it can be observed that the spectrum utilization performance of the algorithm, NCMC-MRSA or MC-RSA with SRB outperforms the same algorithm with MSRP in both scenarios (i) and (ii). In the scenario (iii), the similar result can also be found that the ordering strategy of SRB outperforms MSRP for both NCMC-MRSA and MC-RSA in terms of spectrum utilization, shown in Figs. 10(a) and 10(b), respectively. This is reasonable because SRB orders the multiple services considering the balance of the total spectrum resource requirements, and the network resource will be allocated more balanced to accommodate more multicast requests under multipath strategy. Moreover, the spectrum resources occupied on the network in a short period time utilizing SRB will not be too large or too small, resulting in efficient and balancing network resource utilization. Overall, SRB ordering strategy for multiple multicast services presents more efficient spectrum utilization performances than MSRP ordering strategy for both the NCMC-MRSA and MC-RSA in most network scenarios.

In order to evaluate the impact of the parameter w on the algorithms, we choose the fully connected network as the test network, which could provide enough links to establish the NCMTs for multicast requests over network coding enabled EON. We conduct the simulation experiments in the fully connected network with 100 nodes to accommodate five multicast requests. The impact of the parameter w on the algorithms of NCMC-MRSA and MC-RSA is evaluated in different simulation conditions when the parameters nD in Figs. 11(a) and 11(b) are set to (i) 2 and (ii) 4, respectively. From the simulation results in Fig. 11(a), the red line indicates that the change of the parameter w has a small impact on the performance of the MC-RSA in terms of spectrum utilization. The similar results of the MC-RSA can also be found in the red line shown in Fig. 11(b) under the condition (ii). This is reasonable because the multicast request not capable of network coding is transmitted over just one routing path for each source and destination node pair using MC-RSA. In other word, the parameter w is always set to 1 using MC-RSA. As the parameter w increases, the simulation results of NCMC-MRSA shown with the black line in Fig. 11(a) presents an obvious decreasing trend under the condition (i). It is also interesting to see that as the parameter w increases to a certain value, the spectrum consumption using NCMC-MRSA is almost unchanged. A similar trend can also be found in Fig. 11(b) that as w increases, the black line for NCMC-MRSA under the condition (ii) also shows a decreasing trend. And as w increases to a certain value, the black line turns to be almost unchanged. This can be explained that as w increases to the number of the required spectrum slots, the multicast service cannot be transmitted over more link-disjoint parallel paths any more. Overall, the parameter w has a slight influence on the performance of MC-RSA in terms of the spectrum utilization. However, the change of the parameter w in a certain range has a significant impact on the performance of NCMC-MRSA.

In this paper, we propose a heuristic algorithm NCMC-MRSA to solve the multicast services provision problem over the network coding enabled EON, considering the time delay constraint. Utilizing the well-known layered graph approach [23], NCMC-MRSA under the multipath routing strategy solves the RSA problem in an integrated way. Compared with the benchmark algorithm, we conduct a series of experimental simulations to evaluate the performances of the proposed algorithm under different request ordering strategies in the network scenarios of the random network, the Euro network, and the US network. Simulation results show that as the average number of the receivers or the node number of random network increases, NCMC-MRSA under SRB ordering strategy shows the best performance in terms of the spectrum utilization among other algorithms in most random network. NCMC-MRSA outperforms the benchmark algorithm in terms of spectrum utilization in most network scenarios, especially such advantage is more obvious in large networks. We also find that NCMC-MRSA shows less efficiency in terms of spectrum utilization than the benchmark algorithm in both small random networks and the real networks. Besides, we evaluate how the ordering strategies of MSRP and SRB impact the performances of our proposed algorithm in different network scenarios. We also find that the change of the parameter w in a certain range can influence the performance of NCMC-MRSA. However, as the parameter w increases to a certain value, the total spectrum consumption of NCMC-MRSA is less influenced by the changes of w.