Elastic Resource Allocation for Multi-Granularity Multicasting Traffic in OFDM-Based Optical Networks

Lijun Li¹, Huanlai Xing², Zhenni Wang¹, Hui Shi¹

¹School of Electronics and Information Engineering, Taiyuan University of Science and Technology, Taiyuan, China.
²School of Information Science and Technology, Southwest Jiaotong University, Chengdu, China.

DOI: 10.4236/opj.2018.811028                

Abstract

With the increasing requirements of the multicast services in the whole data traffic service, the optical multicast technology becomes a key technology supporting wide bandwidth and high speed multicasting communication. The transmission efficiency, capacity and robustness of optical multicast network can be further improved by introducing network coding technology into optical multicast networks. Meanwhile, facing to demand of emerging rate-variable multi-granularity multicast service, a multi-path transmission scheme based on network coding for routing and spectrum allocation (RSA) is proposed. It can not only allocate spectrum resources effectively and flexibly for various-rate multicast traffic, but also balance the network load, improve network throughput and reduce transmission blocking rate. In this paper, RSA problem is decomposed into two subproblems, namely routing allocation based on network coding and spectrum allocation based on maximum spectrum first (MSF) strategy, which are solved sequentially. Simulation experiments are carried out to analyze transmission performance with proposed RSA scheme. The simulation results show that the proposed RSA mechanism can allocate spectrum resources efficiently and flexibly for multi-granularity multicast traffic. Compared with RSA schemes based on shortest path tree (SPT) and minimal spanning tree (MST), the proposed RSA scheme is more efficient for spectrum resource utilization and load balancing, and spectrum resource is saved more than 20%.

Keywords

Optical Multicasting, Elastic Optical Networks, Routing and Spectrum Allocation, Network Coding, Orthogonal Frequency Division Multiplexing

1. Introduction

With the rapid development of broadband network, the rate of backbone network communication has been into T bit/s recently [1] . At the same time, support IPTV, remote education, video conference, etc. The multicast communication services, such as IPTV, remote education, and video conference, are expected to meet the high quality and diverse demand of more and more users. Therefore, multicast service networks are facing the challenges on the network bandwidth and efficient resource allocation for multi-granularity multicast services.

The optical multicast technology overcomes the limitations on transmission rate caused by optical-electric-optical convention, so it becomes a key technology supporting wide bandwidth and high speed multicasting communication. And the transmission efficiency, capacity and robustness of optical multicast network can be further improved by introducing network coding technology [2] into optical multicast network, so network coding technology is also considered as an effective solution for the high-bandwidth multicast [3] . Meanwhile, the current multicast traffic is of various types and has diverse bitrates, so how to allocate the routing and spectrum resource efficiently and flexibly for multi-granularity multicast traffic is an urgent problem for multicast services. OFDM technology achieves fine-granularity capacity to satisfy the diverse traffic demands by elastically accommodating multiple subcarriers [4] , which improve the efficiency of spectrum allocation comparing with wavelength-division multiplexing (WDM) technology of rigid fixed-grid and coarse bandwidth allocation [5] . In order to achieve high-speed and high-efficiency multicast traffic transmission, this paper mainly focuses on the research on elastic resource allocation scheme based on network coding technology and orthogonal frequency division multiplexing (OFDM) technology in optical network.

Facing to rate-variable traffic requests, elastic optical network employ flexible routing and spectrum allocation algorithms to improve resource utilization efficiency [6] . Multicast requests adopting single path transmission are served by selecting the adaptive modulation level according to transmission distance, and a lower capacity blocking probability is achieved [7] [8] . Multipath routing and spectrum allocation scheme is help for improving blocking performance and fairness [9] [10] , but it is mainly researched on unicast service. Meanwhile, routing resource is reserved dynamically according to proposed load balancing routing strategy [11] [12] , and the bandwidth blocking probability will be decreased. However, the existing researches have not solved the multipath routing problem for multicast traffic transmitting, and the performance of multicast traffic transmitting needs to be improved further.

Hence, in this paper, a novel elastic resource allocation scheme for multi-granularity multicast traffic is proposed. A multi-path transmission scheme based on network coding for routing allocation relieves the pressure of single link throughput efficiently, and the distributed bandwidth allocation is beneficial to balance the network load and avoid network congestion. Meanwhile, network coding technology supports the two traffic flows sharing the same transmitting links and spectrum resource, so the spectrum utilization is improved. The maximum spectrum first (MSF) strategy is adopted for spectrum allocation, which gives priority to the high bandwidth multicast traffic, and it is helpful for decreasing network blocking probability.

This paper is organized as follows: the elastic spectrum allocation scheme and multi-path multicast routing scheme based on network coding scheme are illustrated in Section 2. Section 3 shows the integer linear programming (ILP) formulation and heuristic algorithm based on GA for solving routing and spectrum allocation. Section 4 presents the simulations on proposed scheme, and relevant spectrum resource utilization efficiency and load balancing performance on multi-granularity multicast traffic are analyzed and discussed. Finally, our conclusion is summarized in Section 5.

2. Scheme Design and Operation Principle

2.1. Elastic Spectrum Resource Allocation Based on OFDM

Traditional WDM network assigns a fixed spectral grid (50 GHz or 100 GHz) for each traffic demand. When the multicast traffic is lower than the entire wavelength capacity, it results in inefficient resource utilization because of the rigid fixed-grid and coarse bandwidth allocation. However, elastic optical networks based on optical OFDM technology adopt flexible bandwidth allocation to match multi-granularity traffic by elastically accommodating multiple subcarriers [13] , and the spectrum gird is set 12.5 GHz or 6.25 GHz. Lower spectrum gird is easier to provide fine-granularity capacity to satisfy the traffic demands, and the bandwidth utilization is improved. Therefore, optical OFDM technology has been regarded as a promising optical transmission technology because of its high-speed transmission, high spectral efficiency and flexible spectrum allocation.

Optical OFDM technology can satisfy multi-granularity traffic demand by adjusting the number of OFDM multiplexing subcarrier. Figure 1 illustrates the routing and spectrum resource allocation scheme for three parallel multi-granularity traffic demands.

The routing allocation scheme for three multicast traffic streams is shown in Figure 1(a). In order to avoid the collision among traffic streams transmission, the relevant spectrum allocation scheme is shown in Figure 1(b). According to the various multicast traffic, enough spectrum resource is offered by allocating different number of subcarriers. For instance, traffic a from node 1 is transmitted to node 4 via node 2, lightpath 1→2 and 2→4 reserve the same spectrum for it. Traffic a and traffic b occupy the same lightpath, so the collision is avoided by allocating different spectrum resource.

2.2. Multicast Routing Scheme Based on Network Coding

Network coding technique changed the traditional multicast scheme for setting up multicast tree. Traditional multicast tree set a single path between the source

Figure 1. Resource allocation scheme for multi-granularity multicast traffic. (a) Routing allocation scheme; (b) Spectrum allocation scheme.

node and destination node, while multicast tree scheme based on network coding technology will build at least two paths between the source node and destination node. The data will be transmit to the destination node via two different path. As shown in Figure 2, there are comparison and analysis the difference between traditional multicast tree and network coding multicast tree.

In Figure 2, s is the source node, a, b, c and e are the intermediate nodes, and d1 and d2 are the destination nodes. Supposing two multicast traffic data packet m and n are broadcast to destination nodes d1 and d2 from source node s respectively. As shown in Figure 2(a), data packets m and n are broadcasted by the path s - a - d1 and s - b - d2 separately in traditional multicast tree, and each path is occupied twice. Meanwhile, data packets m and n are sent in parallel via different paths in the network coding multicast tree, as shown in Figure 2(b). When two data packets meet at node c, they will be encoded by linear logic bitwise exclusive OR (XOR) operation. Then the encoded data packet m ⨁ n is transmitted to the destination node d1 and d2 respectively. The original packets m and n can be recovered by decoding operation at destination node d1 and d2. For example, the data packets m and m ⨁ n are received respectively at destination node d1, and data packet n can be recovered by XOR decoding operation m ⨁ (m ⨁ n). Although multicast tree based on network coding takes the more paths than the traditional multicast tree for multicast traffic, each path is occupied by only once. Multicast scheme based on network coding can distribute the multicast traffic over more routing paths, so as to increase the network throughput and balance the network load, and the advantages will be more significant in the large-scale networks.

2.3. Multi-Path Transmission Scheme

Previous researches mainly focus on allocating single path for each traffic. However, if multicast traffic is beyond the bandwidth of path, it will increase the blocking probability. Meanwhile, single transmitting method is likely to result in network load imbalance. Multi-path transmission scheme contributes to improve the network throughput and resource utilization efficiency [14] .

Based on the hardware structure of encoding node supporting multi-granularity multicast traffic transmission in optical network [15] , this paper

Figure 2. The diagrams of multicast tree. (a) Traditional multicast tree; (b) Multicast tree based on network coding.

proposed a NC-based multi-path transmission RSA scheme. The different transmission rate of multicast service is unable to match the network coding operation, so the NC-based multi-path routing allocation operates every multicast traffic separately. As shown in Figure 2(b), the multicast traffic flow is divided into two parts of the same size m and n at the source node s, and both traffic flows are assigned different multicast path transmitting to the destination node. There is no collision among paths for m and n, and traffic m and n are combined to one traffic at encoding node c. Thus, the same spectrum can be allocated for both m and n. Comparing with single path transmission, multi-path transmission distributes the bandwidth of multicast traffic into two parts, and the spectrum resource occupying on each path reduces by half, and it is beneficial to reduce blocking probability on each links.

3. Model Programming and Heuristic Algorithm for RSA

3.1. ILP Formulation

In this paper, we formulate integer liner programming (ILP) model. In order to reduce the computation complexity, we allocate the resource separately for every multicast traffic request.

Notations:

$G=\left(V,E\right)$ : the physical topology, where V is the node set, E is the link set.

$M_i=\left(s_i,D_i,F{S}_i\right)$ : the multicast requests set, where S_i is the source node of M_i, D_i is the destination node set of M_i, and FS_i is the bandwidth of M_i.

d_ij: the jth destination node in D_i, $d_{ij}\in D_i$ , $j=1,2,\cdots ,\left|D_i\right|$ .

C_e: the capacity of fiber links, $e\in E$ .

$R_{s,d}$ : the path from the source node to the destination node.

Variables:

${\lambda }_r$ : Boolean variable that equals 1 if path r( $r\in R$ ) is allocated for M_i, and 0 otherwise.

${\omega }_e^i$ : Boolean variable that equals 1 ifmulticast request M_i occupies the spectrum resource on link e, and 0 otherwise.

${\pi }_e$ : the times of multicast traffic occupies link e.

$GFS$ : the number of frequency slots for guard spectrum, GFS is equal to the space of subcarrier

$\xi$ : the number of frequency slots for multicast traffic spectrum.

Objective:

Minimize $\xi$ (1)

In this paper, optimization goal is minimizing the total number of all the multicast traffic requests.

Constraints:

1) Multicast tree constraints:

${\displaystyle \underset{r\in R}{\sum }{\lambda }_r=2}$ , $\forall d_{ij}\in D_i$ (2)

Equation (2) constrains that the multicast traffic is divided into two paths for transmitting from ${\text{s}}_i$ to $d_{ij}$ , and

${\pi }_e\le 1$ (3)

Equation (3) constrains that every link is only occupied once for each multicast traffic.

2) Spectrum allocation constraints:

$F{S}_i\le C_e$ (4)

Equation (4) constrains that the spectrum resource allocated for multicast traffic is less than the capacity of fiber link. If cannot be satisfied, the traffic will be blocking.

${\omega }_e^i\le 1$ (5)

Equation (5) constrains that the same frequency slot only can be allocated for one traffic.

3.2. Heuristic Algorithm for RSA

The proposed RSA algorithm is illustrated as follow, and the relevant flow diagram is shown in Figure 3.

Figure 3. The flow diagram on proposed RSA algorithm.

When multicast tree based on network coding is established for one multicast traffic, it prefer to choose spare path for multicast routing, so as to balance the network load. If there is no spare path for multicast routing, the other available frequency slots is allocated for new multicast traffic on the same path.

In this paper, genetic algorithm (GA) is used for planning the multicast routing based on network coding. The multicast routing from a single source node to multi-destination nodes is optimized by GA, whose objective is minimizing the cost of encoding. As a result, the proposed optimized multicast tree is of minimum number of encoding node and encoding sides. The individuals population are denoted as binary symbol, and each bit is generated randomly from the set of [0,1]. The each bit of individuals is denoted a link for encoding node, and the each chromosome of populations is denoted a network topology. The fitness of chromosome R_i is set:

$F\left(R_i\right)=\{\begin{array}{ll}L-L_{\text{coding}}\hfill & R_i\text{is feasible solution}\hfill \\ 0\hfill & R_i\text{is not feasible solution}\hfill \end{array}$ (6)

where L is the number of links in network topology, and L_coding is the number of encoding sides. In proposed scheme, individuals of higher fitness have a larger probability to survive. Thus, when R_i is feasible solution, if L_coding is smaller, the fitness is higher, and the corresponding individual has larger probability to survive in next generation. The tournament selection is adopted for selection operation, and the lowest fitness individual is replaced by the highest fitness individual in each generation, so that the highest fitness individuals is easier be chosen. Meanwhile, the crossover is single-point operation and the mutation is multi-point operation.

4. Simulation Analyzing and Results Discussion

4.1. Simulation Analyzing

In this section, we compare the performance of proposed NC-MSF RSA scheme with RSA based on Shortest Path Tree (SPT) and Minimal Spanning Tree (MST). The multicast tree based on SPT has the shortest path from source node to multi-destination nodes, and multicast traffic will go through the least number of nodes. The multicast tree based on MST contains the source node and all the destination nodes, its topology has the least sum of all the path. The transmission performance of three RSA schemes is evaluated using topology 1 and topology 2, as shown in Figure 4 and Figure 5. Table 1 illustrates the relevant simulation parameters.

In simulation, C band is deployed for elastic spectrum allocation, and flexible grid spectrum scheme based on OFDM is set 12.5 GHz to be the bandwidth of each frequency slot, so each fiber link can accommodate 358 frequency slots for multicast traffic requests. In simulation scenario, multi-granularity multicast traffic requests of diverse rate 10, 20, 40, 50, 80, 100 Gbit/s are chosen randomly, and the spectrum utilization is analyzed when the number of multicast traffic requests are set 3, 5, 10, 15, 20 respectively.

Topology 1 for simulation experiment has 25 nodes and 36 links, and topology 2 has 20 nodes and 35 links. In topology 1, the set of source nodes is {1, 2, 3, 4, 5, 6, 7}, and the set of destination nodes is {22, 23, 24, 25}. In topology 2, the

Figure 4. Topology 1 for simulation experiment.

Figure 5. Topology 2 for simulation experiment.

set of source nodes is {1, 2, 3, 4, 5, 6}, and the set of destination nodes is {14, 17, 18, 19, 20}. According to the number of multicast traffic requests, the nodes are chosen from the set of nodes separately, and the number of destination nodes is set as 2, 3, 4 and 5 in sequence. All the links is set normalization for simple.

In this paper, the NC-MSF algorithm employs the genetic algorithm based on network coding for multicast routing. The number of population is set 30, the crossover probability is set 0.8, and the mutation probability is set 0.1. When the maximum number of iterative reached 100, the algorithm is terminated, and corresponding multicast routing is established. Then, the utilization of spectrum

Table 1. Simulation parameters.

resource is calculated for multicast traffic requests. In each simulation scenario, according to the bandwidth of multicast traffic requests and the number of multicast traffic requests, average maximum frequency slots occupied on topology links is calculated by simulating 10 times respectively. Afterwards, the utilization of routing and spectrum resource and the performance of network load balance are discussed.

4.2. Results Discussion

Figure 6 and Figure 7 show the maximum average usage of frequency slots on each links versus request sizes for flexible-bitrate multicast traffic in topology 1 and topology 2. Comparing with SPT and MST, proposed multi-path NC-MSF scheme will occupy less frequency slots on each link. Multi-path strategy dispersed the usage of frequency slots on the links, and it is efficient for avoiding link congestion. Meanwhile, on the basis of multi-path based on network, two multicast traffic flows can be combined by encoding operation, and they are transmitted on sharing links, without increasing the spectrum resource utilization. Therefore, the network throughput will be improved.

In Figure 6 and Figure 7, we also can find that the maximum usage of frequency slots will increase with the increasing number of multicast traffic requests. More spectrum resource need to be allocated for satisfying the multicast traffic demands. Compare Figure 6 and Figure 7, when they have the same number of destination nodes and multicast traffic requests, the maximum average usages of frequency slots are closed to each other, due to the similar number of nodes and links. However, on the whole, the maximum average usage of frequency slots in topology 2 is still less than topology 1, because it mainly affected by the structure of topology. The in-degree and out-degree of topology 2 nodes are more than topology 1, it easily provides a different multicast routing for different multicast traffic, which will reduce the frequency slots utilization.

Figure 8 depicts the maximum average usage of frequency slots performance versus the number of destination nodes in topology 1, where the number of multicast traffic requests is five. As shown in Figure 8, the average usages of frequency slots increase slightly with the number of destination nodes increasing. It is due to the influence of topology tree structure.

As shown in Figure 9, the improvement of spectrum utilization efficiency on proposed multi-path NC-MSF scheme comparing with SPT is illustrated. The

Figure 6. Average usage of frequency slots in topology 1. (a) D = 2, (b) D = 3, (c) D = 4.

Figure 7. Average usage of frequency slots in topology 2. (a) D = 2, (b) D = 3, (c) D = 4, (d) D = 5.

Figure 8. Average usage of frequency slots versus the number of destination nodes in topology 1.

Figure 9. The improvement of spectrum utilization efficiency.

simulation is operated in topology 1 scenario. When the same number of multicast traffic requests is transmitted, the proposed multi-path NC-MSF scheme will improve the utilization of spectrum resources more than 20% comparing with SPT scheme. The simulation results illustrate that multi-path NC-MSF scheme is beneficial to reduce the maximum average usage of frequency slots on each links, and the performance of load balance is improved obviously.

5. Conclusion

A multi-path transmission scheme based on network coding for routing and spectrum allocation is proposed for multi-granularity multicast traffic transmitting in elastic optical network. The routing spectrum allocation is optimized by decomposing into multi-path routing based on network coding and spectrum allocation based on maximum spectrum first. In simulation experiments, the spectrum resource can be allocated dynamically and efficiently to satisfy diverse rate multicast traffic demand, and the maximum average usage of frequency slots on each links is analyzed. The simulation results verify that the multi-path transmission scheme based network coding can balance the network load, increase network throughput and reduce blocking probability effectively.

Acknowledgements

This research was jointly supported by National Youth Science Foundation of China (No. 61703297), Youth Foundation of Shanxi Province (No. 201601D021065, No. 201701D221109), and Doctoral Scientific Research Foundation of Taiyuan University of Science and Technology (No. 20152023).

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Zhang, G., Leenheer, M.D., Morea, A. and Mukherjee, B. (2013) A Survey on OFDM-Based Elastic Core Optical Networking. IEEE Communications Surveys & Tutorials, 15, 65-87. https://doi.org/10.1109/SURV.2012.010912.00123
[2]	Ahlswede, R., Ning, C., Li, S.-Y.R. and Yeung, R.W. (2000) Network Information Flow. IEEE Transactions on Information Theory, 46, 1204-1216. https://doi.org/10.1109/18.850663
[3]	Long, L. and Kamal, A.E. (2009) Reducing Network Cost of Many-to-Many Communication in Unidirectional WDM Rings with Network Coding. Journal of Lightwave Technology, 27, 4209-4220. https://doi.org/10.1109/JLT.2009.2022845
[4]	Varvarigos, E.A. and Christodoulopoulos, K. (2014) Algorithmic Aspects in Planning Fixed and Flexible Optical Networks with Emphasis on Linear Optimization and Heuristic Techniques. IEEE Journal Surveys& Magazine, 32, 681-693.
[5]	Rubén, R.Z., Luis, V., Claudio, C., Flavio, R. and Pablo, C.J. (2019) Resource Allocation in WDM vs. Flex-Grid Networks: Use Case in CEDIA Optical Backbone Network. Advances in Intelligent Systems and Computing, 884, 18-33. https://doi.org/10.1007/978-3-030-02828-2_2
[6]	Gerstel, O., Jinno, M., Lord, A. and Yoo, S.J.B. (2012) Elastic Optical Networking: A New Dawn for the Optical Layer. IEEE Communications Magazine, 50, S12-S20. https://doi.org/10.1109/MCOM.2012.6146481
[7]	Gong, L., Zhou, X., Liu, X., Zhao, W., Lu, W. and Zhu, Z. (2013) Efficient Resource Allocation for All-Optical Multicasting over Spectrum-Sliced Elastic Optical Networks. Journal of Optical Communications and Networking, 5, 836-847. https://doi.org/10.1364/JOCN.5.000836
[8]	Li, X., Zhang, L., Tang, Y., Gao, T., Zhang, Y.J. and Huang, S.G. (2018) On-Demand Routing, Modulation Level and Spectrum Allocation (OD-RMSA) for Multicast Service Aggregation in Elastic Optical Networks. Optics Express, 26, 24506-24530. https://doi.org/10.1364/OE.26.024506
[9]	Zhu, Z., Lu, W., Zhang, L. and Ansari, N. (2013) Dynamic Service Provisioning in Elastic Optical Networks with Hybrid Single-/Multi-Path Routing. Journal of Lightwave Technology, 31, 15-22. https://doi.org/10.1109/JLT.2012.2227683
[10]	Ruan, L. and Zheng, Y.W. (2014) Dynamic Survivable Multipath Routing and Spectrum Alloction in OFDM-Based Flexible Optical Networks. Journal of Optical Communication Networks, 6, 77-85. https://doi.org/10.1364/JOCN.6.000077
[11]	Thabo, S. and Xie, K. (2019) Efficient Load Balancing and Multicasting for Uncertain-Source SDN: Real-Time Link-Cost Monitoring. Advances in Intelligent Systems and Computing, 763, 178-187. https://doi.org/10.1007/978-3-319-91186-1_19
[12]	Liu, H.L., Huang, J., Chen, Y. and Chen, D.R. (2018) Traffic Load-Aware Dynamic Energy-Efficient Routing Strategy with Spectrum Reservation and Load Balance in Elastic Optical Networks. Optical Fiber Technology, 45, 106-114. https://doi.org/10.1016/j.yofte.2018.05.001
[13]	Christodoulopoulos, K., Tomkos, I. and Varvarigos, E.A. (2011) Elastic Bandwidth Allocation in Flexible OFDM-Based Optical Networks. Journal of Lightwave Technology, 29, 1354-1366. https://doi.org/10.1109/JLT.2011.2125777
[14]	Fan, Z.Y., Qiu, Y. and Chan, C.-K. (2015) Dynamic Multipath Routing with Traffic Grooming in OFDM-Based Elastic Optical Path Networks. Journal of Lightwave Technology, 33, 275-281. https://doi.org/10.1109/JLT.2014.2387312
[15]	Li, L.J., Gu, R.T. and Ji, Y.F. (2014) Design for Multi-Granularity Multicast Traffic Transmitting in Orthogonal Frequency Division Multiplexing-Based Flexible-Grid Optical Networks. Optical Engineering, 53, 036104.