**Path Splitting For Virtual Network Embedding In** **Elastic Optical Networks**

** **Badr Oulad Nassar and Takuji Tachibana

^{ }Graduate School of Engineering, University of Fukui, Fukui City, Japan

*Abstract*

*In elastic optical networks, a wavelength is divided into frequency slots (FS) and optical signals are switched at multiple FS intervals. On the other hand, network virtualization manages network resources by efficiently mapping virtual nodes and links to physical ones (virtual network embedding). In this paper, we propose a dynamic virtual network embedding algorithm to decrease the rejection rate of virtual optical network requests. We deﬁne four schemes for node mapping. For link mapping, the primary path, which is the shortest path between the mapped nodes, is computed. If there are no available FSs, path splitting is performed and FSs are assigned at links in primary and alternatives paths. By simulation, we evaluate the effectiveness of path splitting for NSFNET and ARPA2. Numerical results show that path splitting is effective in decreasing the rejection rate. Finally, LLNL scheme, which considers both node and link resources, has the smallest rejection rate.*

* **Keywords*

Path Splitting, Virtual Optical Network, Virtual Network Embedding, Elastic Optical Network

**1.Introduction**

With the considerable increase of network-based applications, the need for more ﬂexible and scalable networking technologies has attracted research interests. Wavelength division multiplexing (WDM), where thousands of wavelengths are multiplexed into a single optical ﬁber, has been utilized as an integral part of the infrastructure networks [1]. WDM networks can support the high-speed data transmission from hundreds of gigabits per second (Gbps) to several terabits per second (Tbps) on a single optical ﬁber [2], [3], [4], [5], [6]. In WDM, a ﬁxed 50 GHz International Telecommunication Union (ITU) wavelength grid (with optical spectrum 1530-1565 nm) is used for data transmission. However, with the exponential increase in Internet bandwidth demand, the current ﬁxed ITU grid will result in ineffective resource utilization [7]. Especially, for high data bit rates, the ﬁxed ITU grid will no longer be able to support bit rates over 100 Gbps [8].

In order to support such high data bit rates, Elastic Optical Networks (EON) has been proposed [9]. In EON, it is possible to change the wavelength grid [10], [11], [12]. This is because a wavelength can be divided into multiple frequency slots (FS) and bandwidth-variable transponders allow transmitting, receiving and switching optical signals at multiple FS intervals [13]. Note that FSs have to be allocated contiguously by considering the spectrum contiguity constraint [14].

On the other hand, network virtualization has emerged as a promising solution that can utilize and manage network resources simply, ﬂexibly, and effectively [15], [16]. In network virtualization, multiple virtual networks (VN) with speciﬁc topologies and resource requirements can be constructed over a physical network. The main challenge in virtual network embedding (VNE) is to construct a VN by efﬁciently mapping both the requested node and link resources into a physical network [17], [18], [19]. If there are enough available node resources (e.g. CPU, memory) and link resources (e.g. Bandwidth), a VN is constructed based on a user’s request. Such VNE problems are formulated as optimization problems, and those can be solved by using some algorithms [15].

Here, over optical networks, Virtual Optical Networks (VON) can be constructed by using the virtualization technology. Moreover, in EON, VONs can be constructed so as to utilize FS more efﬁciently [20]. Here, in order to construct VONs, the conventional VNE techniques cannot be used for virtual optical network embedding (VONE) problem because the spectrum contiguity constraint has to be considered [21], [22]. Even if both the available amount of node resources and the available number for FSs are enough for constructing a VON, the available FSs have to be adjacent on the optical spectrum due to the spectrum contiguity constraint.

In terms of VONE over EON, several techniques have been proposed. In [23], a heuristics algorithm has been proposed for static trafﬁc and dynamic trafﬁc, respectively. For static trafﬁc, the utilization of FSs can be maximized based on the information of trafﬁc. For the dynamic trafﬁc, the proposed algorithm minimizes the rejection rate of VON. In [24], network cost for survivable optical networks is minimized by solving ILP in the case where the amount of trafﬁc is known in advance. Network cost has been calculated based on the number and type of transponders and regenerators, and the survivability can be realized by providing a backup path. Moreover, in [25], the authors have modelled VONE as a mixed integer linear programming (MILP) and have proposed a heuristic algorithm for MILP so as to minimize the utilization of spectrum. Here, [25] has considered multicast oriented services and VONs are constructed for the multicast oriented services. In [26], the authors have also presented a load-balancing algorithm for VONE. In this algorithm, the spectrum can be fragmented to realize the load balancing.

In this paper, we propose a dynamic VONE algorithm to decrease the rejection rate of VON requests by performing path splitting for a case where the amount of available FSs is small at the physical links. In our proposed method, we consider four algorithms for node mapping. Moreover, after computing the shortest path between two requested nodes, called primary path, a VON is constructed with node resources and FSs in the primary path. If there are not enough FSs for the VONE, path splitting is performed in the proposed method by allocating a part of the required FSs in the primary path and the remaining part through other paths, called secondary paths. If the amount of node resources and/or FSs is small even in the secondary paths, the VON request is rejected. By performing path splitting, a larger number of VON requests can be embedded and the rejection rate is expected to be decreased. We evaluate the performance of the proposed method with simulation for NSFNET and ARPA2 and investigate its effectiveness.

This paper is organized as follows. Introduction is provided in Section 1. Section 2 summarizes some related work on virtual optical networks and path splitting. In Section 3, we explain our system model. Section 4 describes our proposed method with path splitting. Numerical results are shown in Section 5, and ﬁnally conclusions are presented in Section 6.

**2.Related Work**

** ****2.1. Virtual Optical Networks (VON) over Elastic Optical networks (EON)**

** **In this subsection, we explain Virtual Optical Network (VON) and Elastic Optical Networks (EON). Figure 1 illustrates the differences between EON and WDM networks in terms of the utilization of optical spectrum. As shown in Figure 1, the ITU grid is ﬁxed in WDM networks but the ITU grid is variable in EON. Therefore, in WDM networks, the frequency is not fully utilized when multiple data transmissions utilize the optical spectrum. This is because some parts of the wavelength grid cannot be used. Moreover, in WDM networks, a guard-band is needed between adjacent ITU grids even when the adjacent grids are used by a connection. On the other hand, in EON, the optical spectrum can be allocated per a FS, and guard-bands are not needed. As a result, the optical spectrum can be utilized in EON more efﬁciently.

Here, VONs can be constructed over EON by using virtualization technology. For general physical networks, virtual networks can be constructed based on a user’s request about network topology and network resources such as CPU, memory, and bandwidth. This virtual network construction is performed by mapping requested resources to the available node and link resources in a physical network. On the other hand, for the construction of VON over EON, requested resources have to be mapped to available FSs in a VON. Hence, the spectrum contiguity constraint has to be constrained. Moreover, if wavelength conversion is not allowed, the same FSs have to be utilized along all virtual links in a VON.

**Figure 1**. Utilization of spectrum grid in WDM and EON.

**2.2. Path Splitting**

** **Next, in this subsection, we explain path splitting that is used to utilize network resources effectively. This path splitting is available for VNE. In [27], path splitting is utilized to split a virtual link into multiple paths for embedding many VNs.

When the available amount of link resources is smaller than the amount of requested link resources, path splitting is utilized in order to construct VNs for using the limited amount of network resources [27]. Numerical results show that the proposed algorithm with path splitting can achieve a more effective utilization of network resources. However, the proposed algorithm in [27] cannot be used for VONE in EON. This is because the spectrum contiguity constraints cannot be satisﬁed when a VON is constructed.

For EON, in contrast to the path splitting, spectrum splitting has been utilized to establish lightpaths in [28], [29] [30] and [31]. Spectrum splitting is used to split a single trafﬁc demand into multiple lightpaths with multiple sets of spectrum. However, spectrum splitting is not utilized for VON over EON because node resources are not considered.

Thus, the path splitting is effective for the construction of virtual networks. However, path splitting cannot be utilized for VON over EON. Moreover, the spectrum splitting can be used for the lightpath establishment in EON, but it cannot be used for VON.

**3. System Model**

**Figure 2**. System model.

In this section, we explain our system model where VONs are constructed over EON. Figure 2 shows our system model where a physical network is illustrated as a graph *G _{p }*(

On the other hand, *W* wavelengths are multiplexed in the *i ^{th}* fiber link

On the other hand, a VON is modelled as a graph *G _{v }*(

Moreover, a VON will be constructed if the requested virtual nodes can be mapped to the physical nodes (node mapping) and virtual links to the physical links (link mapping). In node mapping, if virtual node *n _{v }*∈

**4.Dynamic Path Splitting Vone Algorithm**

In this section, we propose a dynamic VONE algorithm to decrease the rejection rate of VON requests. In this method, path splitting is performed when the number of available FSs is not enough at physical links. Note that a VON request is rejected when the number of FSs and/or the amount of node resources are not enough for constructing a VON even when the path splitting is used.

**4.1. Overview**

**Figure 3**. Flow chart of our proposed method.

In this subsection, we explain an overview of the proposed algorithm. In the following, we assume that a request for constructing a VON arrives at an EON. Here, the request includes the information about the number *k _{v}* of nodes, the number

In our proposed method, a VON is constructed according to the request with the following steps (see Fig.3).

Step 1: A VON request that includes *k _{v}*,

Step 2: The destination node *n _{p}^{d}* is selected among all nodes according to one of the schemes in subsection 4.2.

Step 3: The amount of computing resources is checked at the source node *n _{p}^{s}* and the destination node

Step 4: The primary path, which is the shortest path, is computed between *n _{p}^{s}* and

Step 5: The number of FSs is checked whether Equation 4 can be satisfied at each link along the primary path. If Equation 4 is satisfied, go to Step 8. Otherwise, go to Step 6.

Step 6: Path splitting is performed. The next *K* shortest paths are computed between *n _{p}^{s}* and

Step 7: If the number of available FSs is larger than the number of requested FSs (see equation 5) at each link along the secondary path, go to Step 8. Otherwise, go to Step 9.

Step 8: The VON request is accepted and VON can be constructed. If path splitting is utilized, FSs are allocated at all links for both the primary path and the secondary path.

Step 9: The VON request is rejected.

In the next subsections, we explain the node selection schemes at Step 2 in subsection 4.2, and we explain the path splitting at Steps 5 to 9 in subsection 4.3.

**4.2. Selection Schemes of Destination Nodes**

**Figure 4**. Selection schemes of the destination node.

In our proposed method, as shown in the previous subsection, the destination node has to be selected at Step 2. Here, the destination node is selected among all nodes according to one of the following schemes as shown in Fig. 4. Here, the utilization rate for each node and each link is shown in Fig. 4.

**Scheme 1: Random Selection**

The destination node is selected at random among all nodes except for the source node.

**Scheme 2: Least Loaded Node (LLN)**

The node whose utilization rate is the smallest is selected as the destination node *n _{p}^{d}*. In Fig. 4, node

**Scheme 3: Least Loaded Link (LLL)**

First, we consider the shortest path between each node and the source node *n _{p}^{s}*. Then, for these shortest paths, the average utilization rate is calculated. When the average utilization rate of the shortest path is the smallest for a node, the node is selected as the destination node. In Fig. 4,

**Scheme 4: Least Loaded Node and Link (LLNL)**

This scheme utilizes the average utilization rate for the two rates in scheme 2 and scheme 3.The node with the smallest average utilization rate is selected as the destination node. By combining LLN and LLL, in Figure 4, node *n _{p}^{d}* is selected as the destination node.

**4.3. Path Splitting **

**Figure 5**. Path splitting for VONE.

If the number of available FSs at each link along the primary path is smaller than the number of requested FSs, the path splitting is utilized. In Step 6, a secondary path is computed for the path splitting. At first, the next *K* shortest paths are computed between *n _{p}^{s}* and

Moreover, if path splitting is performed, the number of contiguous FS that are allocated at each link in the secondary path is defined in Equation 5. In Fig. 5(b) the number of available FSs is smaller than the number of required FSs. As a result, three FSs are allocated at each link in the primary path and two FSs are allocated in the secondary path.

If the number of FSs and/or the amount of node resources are not enough for constructing a VON even when the path splitting is used, the VON requested is rejected.

**5.Numerical Results**

**Figure 6**. Network topologies for simulation.

In this section, we evaluate the performance of our proposed method with simulation according to the node selection schemes explained in subsection 4.2. For our proposed method, as shown in subsection 4.2, Scheme 1 is denoted as Random, Scheme 2 as LLN, Scheme 3 as LLL, and Scheme 4 as LLNL, respectively. In addition, we evaluate the performance of VONE over EON without path splitting, denoted as NoPS. In this scheme, the destination node is selected at random. The topologies of physical network are NSFNET and ARPA2 (See Fig. 6). In NSFNET, the number *N _{p}* of nodes is 14 and the number

Finally, we denote *R** _{accept}* as the number of accepted VON requests and

**5.1. Effect on the Overall Rejection Rate**

**Figure 7**. Overall rejection rate vs. arrival rate in NSFNET topology.

In this subsection, we investigate the impact of path splitting on the overall rejection rate. Figure 7 shows the overall rejection rate against the arrival rate λfor the NSFNET topology. In this ﬁgure, we compare the performance of the proposed four node selection schemes with the performance of NoPS.From this figure, we ﬁnd that the overall rejection rate for all schemes becomes large as the arrival rate increases. In addition, it is shown that the rejection rate for LLNL is the smallest regardless of the arrival rate. This is because LLNL chooses the node with the largest amount of available computing resources and FSs．Hence, a larger number of VON requests can be embedded. Moreover, the overall rejection rate of NoPS is the largest. These results show that path splitting is effective in reducing the overall rejection rate.

**5.2. Impact of the arrival rate on the average number of path splits**

**Figure 8**. Number of path splits vs. arrival rate in NSFNET topology.

Next, we investigate the impact of the arrival rate λ on the average number of path splits. Figure 8 shows the average number of path splits against the arrival rate for the proposed four schemes. From this ﬁgure, we can see that the number of path splits increases as the arrival rate increases for all schemes. This is because VON requests are rejected frequently as the arrival rate increases. In addition, the number of path splits is the smallest for the LLL scheme and the largest for the random scheme. This is because the random scheme does not consider the amount of available computing resources at nodes and the number of available FSs at links when constructing a VON. In contrast, the LLL scheme constructs a VON such that links with the most available FSs are used. Therefore, the number of path splits is the smallest for LLL because FSs are allocated more effectively.

**5.3. Impact of the maximum ****amount of link resources per request**

**Figure 9**. Overall rejection rate vs. arrival rate in NSFNET topology.

Finally, we investigate how the maximum number of FSs per request affects the overall rejection rate for the proposed four schemes and the scheme NoPS. Figure 9 illustrates the case of NSFNET. We set the maximum number of FSs per link is set to 32, 16 and 10 for case 1, case 2, and case 3, respectively. Moreover, we consider the case where the arrival rate is 60 requests per millisecond. Figure 9 shows the overall rejection rate for all four schemes in cases 1, 2 and 3. From this ﬁgure, we ﬁnd that the overall rejection rate in case 1 is the largest and is the smallest in case 3 for all schemes. This is because in case 1, the maximum number of FSs per link is large. As a result, VON requests are rejected frequently because there are no available FSs at links. On the other hand, in case 3, the maximum number of FSs per link is small, hence increasing the probability for other VONs to be constructed. Furthermore, in overall, the LLNL shows the best performance in terms of overall rejection rate.

Similar simulation results were obtained for the case of ARPA2.

**6.Conclusion**

In this paper, we proposed path splitting for virtual network embedding in elastic optical networks and evaluated its effectiveness in NSFNET and ARPA2. In our proposed method, path splitting is performed when there are no available FSs at links in the primary path. From the numerical results, we found that path splitting is effective in reducing the overall rejection rate. Furthermore, the LLNL scheme in node mapping has shown the best overall performance. Finally, we believe that combining our path splitting method with other existing VONE over EON algorithms can reduce further the overall rejection rate.

**References**

** **[1] M. Yoo, C. Qiao, & S. Dixit, (2000) “QoS Performance of Optical Burst Switching in IP-Over-WDM Networks”, IEEE J. Select. Areas Comm., Vol. 18, No. 10, pp. 2062-2071.

[2] B. C. Chatterjee, N. Sarma, P. P. Sahu, & E. Oki, (2017) “Introduction to Optical Network, in Routing and Wavelength Assignment for WDM-based Optical Networks”, Springer International Publishing, pp. 1-16.

[3] B. Mukherjee, (2006) “Optical Networking: Principles and Challenges”, Optical WDM Networks, pp. 3-41.

[4] M. Murata, K. Kitayama, & H. Miyahara, (2000) “IP Over a-Thousand Wavelength Division Multiplexing: Is It Useful and Possible for Resolving the Network Bottlenecks?”, Optical Networks Magazine, Vol. 99, No. 674, pp. 55-60.

[5] N. Ghani, S. Dixit, & T. S. Wang, (2000) “On IP-over-WDM Integration”, IEEE Comm. Magazine, Vol. 38, No. 3, pp. 72-84.

[6] K. Struyve, N. Wauters, P. Falcao, P. Arijis, D. Colle, P. Demeester, & P. Lagasse, (2000) “Application, Design, and Evolution of WDM in GTS’s Pan-European Transport Network”, IEEE Comm. Magazine, Vol. 38, No. 3, pp. 114-121.

[7] B. C. Chatterjee, N. Sarma, P. P. Sahu, & E. Oki, (2017) “Limitations of Conventional WDM Optical Networks and Elastic Optical Networks for Possible Solutions”, Routing and Wavelength Assignment for WDM-based Optical Networks, pp. 101-115.

[8] M. Jinno, H. Takara, B. Kozicki, Y. Tsukishima, Y. Sone, & S. Matsuoka, (2009) “Spectrum-Efficient and Scalable Elastic Optical Path Network: Architecture, Benefits, and Enabling Technologies”, IEEE Comm. Magazine, Vol. 47, No. 11, pp.66 -73.

[9] O. Gerstel, M. Jinno, A. Lord, & S. J. B. Yoo, (2012) “Elastic Optical Networking: A New Dawn for the Optical Layer?”, IEEE Comm. Magazine, Vol. 50, No. 2, pp. S12–S20.

[10] O. Rival & A. Morea, (2010) “Elastic optical networks with 25-100G format-versatile WDM transmission systems”, Proceedings of OECC, pp. 100–101.

[11] O. Rival & A. Morea, (2010) “Advantages of elasticity versus fixed data rate schemes for restorable optical networks”, Proceedings of OECC, pp. 1–3.

[12] A. Klekamp, F. Buchali, R. Dischler, & F. Ilchmann, (2010) “Comparison of DWDM network topologies with bit-rate adaptive optical OFDM regarding restoration”, European Conference and Exhibition, pp. 1–3.

[13] M. Recalcan, F. Musumeci, M. Tornatore, S. Bregni, & Achille Pattavina, (2014) “Benefits of Elastic Spectrum Allocation in Optical Networks with Dynamic Traffic”, Proc. IEEE/LATINCOM, pp. 1–6.

[14] M. Jinno et al., (2010) “Distance-adaptive spectrum resource allocation in spectrum-sliced elastic optical path network”, IEEE Comm. Magazine, Vol. 48, No. 8, pp. 138 – 145.

[15] N. Chowdhury & R. Boutaba, (2010) “A Survey of Network Virtualization”, Computer Networks, Vol. 54, No. 5, pp.862-876.

[16] N. M. Chowdhury & R. Boutaba, (2009) “Network Virtualization:The Past,The Present,and The Future”, IEEE Comm. Magazine, pp. AS4H. 4.

[17] A. Fischer, J. Botero, M. Beck, H. De Meer, & X. Hesselbach, (2013) “Virtual network embedding: A survey”, IEEE Communications Surveys Tutorials, pp.1-19.

[18] N. Chowdhury, M. Rahman, & R. Boutaba, (2009) “Virtual network embedding with coordinated node and link mapping”, IEEE INFOCOM, pp. 783 –791.

[19] Z. Cai, F. Liu, N. Xiao, Q. Liu, & Z. Wang, (2010) “Virtual network embedding for evolving networks”, IEEE Global Telecommunications Conference, pp. 1 –5.

[20] L. Gong & Z. Zhu, (2014) “Virtual Optical Network Embedding (VONE) Over Elastic Optical Networks”, Journal of lightwave technology, Vol. 32, No.3, pp. 450 –460.

[21] R. Nejabati, E. Escalona, S. Peng, & D. Simeonidou, (2011) “Optical network virtualization”, Optical Network Design and Modeling, pp. 1–5.

[22] L. Gong, W. Zhao, Y. Wen, & Z. Zhu, (2013) “Dynamic transparent virtual network embedding over elastic optical infrastructures”, IEEE International Conference on Communications, pp. 3466-3470.

[23] J. Zhao, S. Subramaniam, & M. Brandt-Pearce, (2013) “Virtual topology mapping in elastic optical networks”, IEEE International Conference on Communications, pp. 3904-3908.

[24] B. Chen, J. Zhang, W. Xie, J. P. Jue, Y. Zhao, S. Huang, & W. Gu, (2014) “Minimum-cost survivable virtual optical network mapping in flexible bandwidth optical networks”, IEEE Global Communications Conference, pp. 2023-2028.

[25] X. Gao, Z. Ye, W. Zhong, C. Qiao, X. Cao, H. Zhao, H. Yu & V. Anand, (2015) “Virtual Network Mapping for Multicast Traffic over Elastic Optical Networks”, Techniqual Report, CSE, UB.

[26] F. M. Madani & S. Mokhtari, (2015) “Fragmentation-Aware Load-Balancing Virtual Optical Network Embedding (VONE) Over Elastic Optical Networks”, Cloud computing, pp. 27-32.

[27] J. Perello, P. Pavon-Marino, & S. Spadaro, (2013) “Cost-Efficient Virtual Optical Network Embedding for Manageable Inter-Data-Center Connectivity”, ETRI Journal, Vol. 35, No. 1, pp. 142–145.

[28] M. Yu, Y. Yi, J. Rexford, & M. Chiang, (2008) “Rethinking virtual network embedding: Substrate support for path splitting and migration”, ACM SIGCOMM Computer Communication Review, Vol. 38, No. 2, pp. 17-29.

[29] M. Xia, R. Proietti, S. Dahlfort, & S. J. B. Yoo, (2012) “Split spectrum: A multi-channel approach to elastic optical networking”, Optics Express, Vol. 20, No. 28, pp. 29143-29148.

[30] Z. Zhu, W. Lu, L. Zhang, & N. Ansari, (2013) “Dynamic service provisioning in elastic optical networks with hybrid single-/multi-path routing”, Journal of Lightwave Technology, Vol. 31, No. 1, pp.15-22.

[31] T. Hashimoto, K. Baba, & S. Shimojo, (2015) “Optical path splitting methods for elastic optical network design”, Proc. of OSA Asia Communications and Photonics Conference, pp. AS4H. 4.

**Authors**

**Badr Oulad Nassar **He received a B. Eng. degree from the School of Science and Engineering, Al Akhawayn University in Ifrane, Morocco, in 2005. He received in 2009 a MS Eng, from the Department of Information Systems, Graduate School of Information Science, Nara Institute of Science and Technology, Japan. He is currently a PhD candidate at the Graduate School of Engineering, University of Fukui, Japan. His research has been sponsored by the Japan Ministry of Education, Culture, Sports, Science and Technology (MEXT) through a honours scholarship. His research interests include network architectures in optical networking. He is a student member of the Institute of Electronics, Information and Communication Engineers (IEICE).

**Takuji Tachibana **He received the B. Eng. degree from the Department of Systems Engineering, Nagoya Institute of Technology, Japan, in 2000. He received the M. Eng. and Dr. Eng. degrees from the Department of Information Systems, Graduate School of Information Science, Nara Institute of Science and Technology, Japan, in 2001 and 2004, respectively. From 2004 to 2006, he was an expert researcher in the Information and Network Systems Department, National Institute of Information and Communications Technology, Japan. From 2006 to 2011, he was an assistant professor at the Department of Information Systems, Graduate School of Information Science, Nara Institute of Science and Technology, Japan. Since 2011, he has been an associate professor at Graduate School of Engineering, University of Fukui, Japan. His research interests include network architectures in optical networking and performance analysis of computer and communication systems. He is a member of the IEEE, The Institute of Electronics, Information and Communication Engineers (IEICE), and the Operations Research Society of Japan.

%d bloggers like this: