On-demand routing, modulation level and spectrum allocation (OD-RMSA) for multicast service aggregation in elastic optical networks

Xin Li; Lu Zhang; Ying Tang; Tao Gao; Yongjun Zhang; Shanguo Huang

doi:10.1364/OE.26.024506

1. Introduction

Optical communication which takes advantages of large-capacity, low energy consumption, and no electromagnetic interference has been widely applied to backbone transmission, data center interconnection, and data transmission between satellites [1–3]. Instead of traditional fixed-grid optical networks, the concept of flex-grid has been introduced into optical networks recently [4]. It supports the adaptive and fine-grained spectrum allocation, and thus can accommodate both sub- and super-wavelength traffic. Flex-grid optical network is also called elastic optical network (EON) that becomes a promising candidate for next-generation optical network. It is mainly based on optical-orthogonal frequency division multiplexing (O-OFDM) technology [5] and Nyquist-WDM technology [6]. Moreover, the basic components are bandwidth-variable transponder (BVT) and bandwidth-variable wavelength cross-connect (BV-WXC). At present, the most commonly used BV-WXC is the reconfigurable optical add-drop multiplexer (ROADM) that is implemented by multiple bandwidth-variable wavelength selective switches (BV-WSSs) [7]. Recently, with the development of emerging industries such as mobile internet, cloud computing, big data, internet of things (IoT), and data center, multicast services such as data backup, scientific computing, ultra-high definition TV delivery, and video conferencing are gaining popularity and momentum [8]. The point to multi-point transmission is the typical characteristic of multicast services. In optical layer, light-trees rather than light-paths are usually used to accommodate multicast services [9–12]. Furthermore, to accommodate multicast services with a large number of requesters, the sub-tree based optical multicasting scheme was also proposed. In [13], the authors proposed a light-forest scheme in which the rateless network coding is incorporated into sub-tree construction. In [14], the authors proposed a distributed sub-tree based optical multicasting (DST-OM) scheme that used multiple distributed sub-trees to jointly serve one multicast demand. In brief, the light-tree based optical multicasting (LT-OM) scheme provides a promising method to accommodate emerging multicast services in optical networks. Besides, to accommodate a large number of finer-grained multicast services in a cost-efficient way, the light-tree based multicast service aggregation (LT-MSA) scheme was also proposed and studied. In [15], the authors proposed a multi-class flow aggregation scheme for IPTV content delivery in IP over optical core networks. Multiple multicast IPTV flows were aggregated together and transmitted through a light-tree while satisfying the requirement that secure programs can only be sent to authorized users. In [16], the authors proposed a multicast dynamic light-tree grooming algorithm that supports multi-hops traffic grooming. A light-tree can be dropped, branched, and extended when a route is to be established for a new request. In [17,18], the authors proposed two multicast service aggregation strategies, i.e., user-cover ratio based strategy and modulation-level-aware strategy. Multiple multicast services can be aggregated together only if they satisfy the designated user-cover ratio or there exists a highest or lowest available modulation-level. In [19], the authors proposed a novel BV-WSS based flow aggregation scheme in which each unicast service can travel different paths.

In traditional wavelength division multiplexing (WDM) networks, a light-tree is usually implemented by multiple light-splitters. Each fiber link of a light-tree is allocated with the same spectrum. Because of this, when multiple multicast services which do not have exactly the same requesters are aggregated together, spectrum redundancy may exist in some fiber links. Most of the time, the requesters of multicast services are quite different from each other. The result is that a large amount of spectrum resources will be wasted. This shortcoming also restricts the application scope of the LT-MSA scheme while accommodating ordinary and secure multicast services simultaneously. To avoid unauthorized users receiving secure services, ordinary and secure multicast services cannot be aggregated together. It can be seen that how to aggregate multicast services with different requesters becomes a great challenge for applying the LT-MSA scheme into optical networks. In EONs, an elastic optical node can be implemented by the architectures of broadcast-and-select, spectrum routing, switch and select with dynamic functionality, and architecture on demand (AoD) [20]. Most of these architectures support both optical multicasting and bandwidth-variable spectrum selection. Leveraging these node architectures, the aggregated multicast flow can be partially selected at each intermediate node of a light-tree.

Based on this, we consider on-demand routing and spectrum allocation (OD-RMSA) for the LT-MSA scheme. The allocated spectrum on each link of a light-tree is determined by all desired multicast services of downstream destination users of this link. The OD-RMSA eliminates spectrum redundancy on each link of a light-tree. Moreover, it helps to guarantee that any user can only obtain desired multicast services. Since a BV-WSS can only select continuous spectrum, node adjacent redundancy may exist on some fiber links which are adjacent to elastic optical nodes. We define the maximum aggregating group (MAG) to eliminate node adjacent redundancy. The OD-RMSA strategy also expands the application scope of the LT-MSA scheme that it supports accommodating ordinary and secure multicast services simultaneously. An Integer Linear Programming (ILP) model with the objective of minimizing the total transceiver and spectrum resource consumptions is developed to realize OD-RMSA for the LT-MSA scheme in small-scale EONs. A heuristic algorithm is developed to search MAGs among a large number of multicast services. Based on MAG, a scalable heuristic approach is developed to realize OD-RMSA for the LT-MSA scheme in large-scale EONs. Simulations are conducted on n6e8 and NSFNet. Numerical results show that the OD-RMSA strategy saves transceiver than the light-tree scheme and reduces spectrum consumption than the conventional consistent routing, modulation level and spectrum allocation (C-RMSA) strategy. It can also help to ensure that each user can get only all desired multicast services that expands the application scope of the LT-MSA scheme

The rest of this paper is organized as follows. Section 2 discusses implementation basis. Section 3 gives problem description. The ILP model and heuristic algorithms are developed in Section 4 and Section 5 respectively. We present numerical results and conduct performance analysis in Section 6. Finally, Section 7 concludes this paper.

2. Implementation basis

In this section, we focus on the O-OFDM based multicast service aggregation mechanism. Elastic node architectures supporting both optical multicasting and bandwidth-variable spectrum selection are elaborated. Moreover, our contributions are also listed.

2.1 The O-OFDM based multicast service aggregation

To reduce optical transceiver consumption while accommodating a large number of finer-grained multicast services, multiple multicast services can be aggregated together into a large multicast flow at transmitting end. Based on the O-OFDM technology, multiple multicast services are modulated onto several continuous frequency slots (FSs). Since the basic selective granularity of BV-WSS is the FS, the O-OFDM technology merely supports the aggregation level of the FS at optical layer. In other words, multicast services of which the transmission rate is smaller than the capacity of a FS should be aggregated in other layers.

The O-OFDM signal can be generated through the Fast Fourier Transform (FFT) based approach where subcarriers are generated in electrical domain or through optical approach where subcarriers are generated in optical domain [21]. Figure 1(a) and 1(b) present two FFT-based multicast O-OFDM signal synthesis architectures, i.e., intermediate frequency up/down conversion architecture and direct up/down conversion architecture. In Fig. 1(a), multiple multicast services are firstly transformed into the complex-valued OFDM signal through a RF OFDM transmitter. Then, the complex-valued OFDM signal is up-converted to an intermediate frequency, and modulated onto optical carriers through a single-ended Mach-Zehnder modulator (MZM). In Fig. 1(b), two MZMs of which one is configured with a 90° phase shifter in series, is used to up-convert the complex-valued OFDM signal from the electrical domain to the optical domain.

Fig. 1 The FFT-based multicast O-OFDM signal synthesis, (a) intermediate frequency up/down conversion architecture, (b) direct up/down conversion architecture.

Download Full Size | PDF

Figure 2 presents the schematic diagram of multicast all-optical OFDM signal synthesis. In Fig. 2, multi-carrier generator produces multiple optical subcarriers from a continuous-wave light source. Then, multiple multicast services are modulated onto several continuous FSs and a free FS that is regarded as guard band is intercalated between any two adjacent multicast services. Guard band is used to avoid crosstalk between two adjacent multicast services. Finally, all these subcarriers are coupled together to form a multicast all-optical OFDM signal. The OD-RMSA strategy for the LT-MSA scheme is applicable for both the FFT-based multicast O-OFDM signal synthesis and all-optical OFDM signal synthesis.

Fig. 2 Multicast all-optical OFDM signal synthesis.

Download Full Size | PDF

2.2 Elastic optical node architectures

The OD-RMSA strategy requires that each optical node must support both optical multicasting and bandwidth-variable spectrum selection. In [20], the authors reviewed several elastic optical node architectures, such as broadcast-and-select, spectrum routing, switch and select with dynamic functionality, and AoD [22].

Among these architectures, BV-WSS plays an important role. As shown in Fig. 3, the architectures of broadcast-and-select, switch and select with dynamic functionality, and AoD support both optical multicasting and bandwidth-variable spectrum selection. For the architecture of spectrum routing, an extra light-splitter needs to be configured at each output port of an incoming BV-WSS to support optical multicasting.

Fig. 3 Elastic optical node architectures (a) broadcast-and-select, (b) spectrum routing, (c) switch and select with dynamic functionality, (d) AoD.

Download Full Size | PDF

2.3 Our contributions

Our contributions include three aspects.

1) We consider OD-RMSA for the LT-MSA scheme. It improves spectrum efficiency and also expands the application scope of the LT-MSA scheme while accommodating ordinary and secure multicast services simultaneously.
2) To eliminate the node adjacent redundancy on each link of a light-tree, we define the concept of MAG. A heuristic algorithm is developed to construct MAGs for a large number of finer-grained multicast services.
3) An ILP model and a heuristic approach are developed to realize the OD-RMSA strategy for the LT-MSA scheme in small-scale and large-scale EONs.

3. Problem description

In this section, the C-RMSA and the OD-RMSA strategies are elaborated for the LT-MSA scheme. The concept of MAG is introduced for the OD-RMSA strategy to eliminate node adjacent redundancy. Besides, the relationship matrix is used to represent MAGs.

3.1 The C-RMSA strategy

To reduce transceiver consumption, the LT-MSA scheme aggregates a large number of finer-grained multicast services into one large multicast flow. A multicast demand can be modeled as MD(o, $Ω$ ,ms), where o denotes source node, ms denotes the desired multicast service, and $Ω$ denotes a set of destination users which request multicast service ms. To avoid crosstalk between multicast services, a free FS that is regarded as guard band is intercalated between any two adjacent multicast services in the aggregated multicast flow.

In Fig. 4(a), there are three multicast demands MD(o,{u₁},ms₁), MD(o,{u₁,u₂},ms₂), and MD(o,{u₂,u₃},ms₃). The LT-MSA scheme aggregates multicast services ms₁, ms₂, and ms₃ together and the aggregated traffic flow is transmitted through the light-tree which originates from source node o and terminates at nodes D, E, and F. For the C-RMSA strategy, each fiber link of this light-tree is allocated with the same spectrum resource. Here, we assume that each multicast service consumes two FSs. Then, the total number of consumed FSs is 8*5 = 40. However, since the requesters of these three multicast services are different, the allocated FSs on some link are not necessary. Here, we take link A→D for example. Since user u₁ only requests multicast services ms₁ and ms₂, only multicast services ms₁ and ms₂ need to be allocated with spectrum resource on link A→D. The allocated FSs for multicast service ms₃ on link A→D are wasted. If we consider OD-RMSA for the LT-MSA scheme as presented in Fig. 4(b), the total number of consumed FSs is only 8 + 5 + 5 + 5 + 2 = 25. Besides, if multicast service ms₃ is a secure multicast service and user u₃ is unauthorized user, multicast services ms₁, ms₂, and ms₃ cannot be aggregated together. Otherwise, user u₃ will receive the unauthorized service. It can be seen that spectrum redundancy and narrow application range are two main shortcomings of the C-RMSA strategy. Considering these two shortcomings, we expect to eliminate spectrum redundancy and extend the application range of the LT-MSA scheme. Therefore, we consider the OD-RMSA strategy for the LT-MSA scheme.

Fig. 4 The LT-MSA scheme (a) the C-RMSA strategy, (b) the OD-RMSA strategy.

Download Full Size | PDF

3.2 The OD-RMSA strategy

The OD-RMSA strategy allocates FSs on each link of a light-tree according to all desired multicast services of downstream destination users of this link. For the OD-RMSA strategy, only multicast services ms₁ and ms₂ are allocated with spectrum resource on link A→D, only multicast services ms₂ and ms₃ are allocated with spectrum resource on link A→C and link C→E, and only multicast service ms₃ are allocated with spectrum resource on link C→F. Figure 4(b) shows that any user can only obtain the desired multicast services.

In Fig. 5(a), we assume that user u₃ requests multicast services ms₁ and ms₃. When multicast services ms₁, ms₂, and ms₃ are aggregated together, multicast services ms₁ and ms₃ should be allocated with spectrum resource on link C→F. Since a port of a BV-WSS can only select continuous spectrum, the spectrum allocated for multicast service ms₂ will be reserved on link C→F. In other words, there exists a node adjacent redundancy on link C→F. The node adjacent redundancy consumes extra spectrum resources and causes insecurity.

Fig. 5 The OD-RMSA strategy (a) node adjacent redundancy, (b) light-tree for ms₁ and ms₂, (c) light-tree for ms₃.

Download Full Size | PDF

The relationship between a link of a light-tree and all desired multicast services of its downstream destination users can be modeled by a two-dimensional matrix. Figure 6(a) presents a two-dimensional matrix which elaborates the relationship between links and the desired multicast services of their downstream destination users for multicast demands MD(o,{u₁},ms₁), MD(o,{u₁,u₂},ms₂), and MD(o,{u₂,u₃},ms₃). In this matrix, if the downstream destination users of link i requests multicast service j, the value at point[i,j] will be set to 1. In Fig. 6(a), we can find that all values of 1 are continuous at any line of this matrix. Figure 6(b) presents a two-dimensional matrix which elaborates the relationship between links and all desired multicast services of their downstream destination users for multicast demands MD(o,{u₁,u₃},ms₁), MD(o,{u₁,u₂},ms₂), and MD(o,{u₂,u₃},ms₃). In Fig. 6 (b), at third line, all values of 1 are not continuous. Even if we exchange the position of some columns, there also exists a line where all values of 1 are not continuous. Figure 6(a) and 6(b) show that multicast services can be aggregated together without node adjacent redundancy if and only if all values of 1 are continuous at any line in the relationship matrix. To eliminate node adjacent redundancy, we define the concept of MAG that represents an ordered set of multicast services. In a MAG, all desired multicast services of downstream destination users of any link are adjacent to each other. In other words, for all downstream destination users of any link, all their desired multicast services are allocated with continuous spectrum. When a MAG is modeled by a two-dimensional matrix, then all values of 1 are continuous at any line of this matrix. Therefore, there does not exist node adjacent redundancy on any link when multicast services in a MAG are aggregated together. In Fig. 6(c), multicast services ms₁, ms₂, and ms₃ can be divided into two MAGs. Multicast services ms₁ and ms₂ are aggregated together. Figure 5(b) constructs a light-tree for aggregating multicast services ms₁ and ms₂. Figure 5(c) constructs a light-tree for transmitting multicast services ms₃. For a large number of multicast demands, we search all MAGs and then conduct OD-RMSA for each MAG.

Fig. 6 Relationship matrix (a) continuous spectrum, (b) discontinuous spectrum, (c) two MAGs.

Download Full Size | PDF

4. The ILP model

In this section, the ILP models for the OD-RMSA strategy and the C-RMSA strategy are developed. The coverage area of a light-tree is limited due to signal attenuation, light-splitting, amplified spontaneous emission (ASE), nonlinear impairments, etc. In [23], the authors showed that the length of the longest branch of a light-tree is close to the transmissions reach of an optical signal along a light-path with the help of amplifier and equalizer at the elastic optical node with the broadcast and select architecture. In this paper, we also assume that the transmission reach of an optical signal along a multicast light-tree is equal to that of an optical signal along a light-path.

4.1 The ILP model of the OD-RMSA Strategy

The ILP model developed for the OD-RMSA strategy is to minimizing the total transceiver and spectrum consumptions of all constructed multicast light-trees.

Notations:

G(V,U,E): EON, V denotes the set of optical nodes, U denotes the set of users, E denotes the set of fiber links.

l₍_i_,_j₎: the length of link(i,j) $\in$ E in kilometers.

S: the set of multicast services, s $\in$ S.

b_s: the required transmission rate of multicast service s.

T: the set of light-trees, k $\in$ T.

B: the base capacity of a FS with modulation-level BPSK.

M: the set of modulation-levels, m $\in$ M. m = 1, 2, 3 represent modulation levels BPSK, QPSK, 8QAM respectively.

d_m: the maximum transmission reach of modulation-level m.

_$Λ$: $Λ$ = {f₁, f₂, …, $f_{| Λ |}$ } is the ordered set of FSs in each fiber link.

MD: a set of multicast demands.

MD(o, $Ω$ ,s): a multicast demand, where o denotes source node, $Ω$ denotes a set of users, and s denotes a multicast service, MD(o, $Ω$ ,s) $\in$ MD.

_$Δ$: a very large positive integer.

R_m: the maximum transmission reach of modulation-level m.

Variables:

_{$P_{(i, j)}^{k} \in {0, 1}$}: equals one if link(i,j) is occupied by light-tree k, otherwise 0.

_{$X_{(i, j), f}^{k} \in {0, 1}$}: equals one if FS f in link(i,j) is used by light-tree k, otherwise 0.

_{$N_{i}^{k} \in {0, 1}$}: equals one if node i is occupied by light-tree k, otherwise 0.

_{$h_{i}^{k} \in {0, 1}$}: equals one if node i is the source node of light-tree k, otherwise 0.

_{$d_{u}^{k} \in {0, 1}$}: equals one if node u is a destination user of light-tree k, otherwise 0.

_{$R_{o, u}^{k} \in {0, 1}$}: equals one if light-tree k originates at source node o and terminates at user u, otherwise 0.

_{$A_{k}^{(o, Ω, s)} \in {0, 1}$}: equals one if multicast demand MD(o, $Ω$ ,s) is accommodated by light-tree k, otherwise 0.

_{$e_{(i, j)}^{(o, Ω, s), k} \in {0, 1}$}: equals one if multicast demand MD(o, $Ω$ ,s) is transmitted through link(i,j) on light-tree k, otherwise 0.

_{$n_{k, i}^{(o, Ω, s)} \in {0, 1}$}: equals one if multicast demand MD(o, $Ω$ ,s) is transmitted through node i on light-tree k, otherwise 0.

_{$Q_{(i, j)}^{(o, u), k} \in {0, 1}$}: equals one if link(i,j) is occupied by a light-path which originates at source node o and terminates at user u on light-tree k, otherwise 0.

_{$Z_{m}^{k} \in {0, 1}$}: equals one if light-tree k adopts modulation-level m, otherwise 0.

_{$W_{(i, j), f}^{(o, Ω, s), k} \in {0, 1}$}: equals one if FS f in link(i,j) on light-tree k is used by multicast service s of multicast demand MD(o, $Ω$ ,s), otherwise 0.

_{$E_{(i, j)}^{(o, Ω, s), k}$}: an integer commodity-flow variable for multicast service s of multicast demand MD(o, $Ω$ ,s) on light-tree k, each user needs one unit of commodity.

_{$T S_{k}$}: integer variable which denotes the number of transceivers used by all aggregated multicast services on light-tree k.

_{$l_{k}$}: integer variable which denotes the length of the longest branch of light-tree k.

Objective Function:

\min (α * \sum_{k \in T} T S_{k} + \sum_{k \in T} \sum_{(o, Ω, s) \in M D} \sum_{(i, j) \in E} \sum_{f \in Λ} W_{(i, j), f}^{(o, Ω, s), k})

Equation (1) aims to minimize the total optical transceiver and spectrum consumptions of all constructed light-trees for all multicast demands. In this paper, a node is used to represent a transmitter or receiver. In other words, the transceivers of a light-tree contain a source node and several destination nodes. The OD-RMSA strategy aims to aggregating multicast demands without sacrificing more spectrum resources. The parameter α is used to force Eq. (1) to consume the least amount of transceivers. It is usually set to a large positive integer.

Multicast Service Aggregation Constraints:

\sum_{k \in T} A_{k}^{(o, Ω, s)} = 1, \forall (o, Ω, s) \in M D

A_{k}^{(o, Ω, s)} \leq h_{o}^{k}, \forall (o, Ω, s) \in M D, \forall k \in T

\sum_{j : (j, i) \in E} e_{(j, i)}^{k, (o, Ω, s)} = {\begin{matrix} 0 & i = o \\ A_{k}^{(o, Ω, s)} & i \in Ω \\ n_{k, i}^{(o, Ω, s)} & o t h e r \end{matrix}, \forall (o, Ω, s) \in M D, \forall k \in T

\sum_{j : (i, j) \in E} e_{(i, j)}^{k, (o, Ω, s)} {\begin{matrix} \geq n_{k, i}^{(o, Ω, s)} & o t h e r \\ \leq Δ * n_{k, i}^{(o, Ω, s)} & o t h e r \\ = 0 & i \in Ω \end{matrix}, \forall (o, Ω, s) \in M D, \forall k \in T

n_{k, i}^{(o, Ω, s)} = {\begin{matrix} A_{k}^{(o, Ω, s)} & i = o \\ A_{k}^{(o, Ω, s)} & i \in Ω \end{matrix}, \forall (o, Ω, s) \in M D, \forall k \in T

Equation (2) ensures that a multicast demand can be accommodated by only one light-tree. In this paper, the primary constraint of multicast service aggregation is that multiple multicast demands have a common source node. The source node of a light-tree is the same as the source of all aggregated multicast demands. Equation (3) ensures that a multicast demand can be accommodated by a light-tree as long as they have a common source. Equation (4) ensures that the source node of the searched partial tree for multicast demand MD(o, $Ω$ ,s) on light-tree k has no incoming link and any destination user only has one incoming link. Other nodes have one incoming link if and only if multicast demand MD(o, $Ω$ ,s) transmits through this node. Equation (5) ensures that any destination user of the constructed partial tree for multicast demand MD(o, $Ω$ ,s) on light-tree k has no outgoing links. Excluding all destination users, a node has outgoing links as long as multicast demand MD(o, $Ω$ ,s) transmits through this node. Equation (6) searches source node and all destination users for the constructed partial tree for multicast demand MD(o, $Ω$ ,s) on light-tree k. Equations (4)-(5) search a partial tree which accommodates multicast demand MD(o, $Ω$ ,s) on light-tree k.

Light-Tree Construction Constraints:

(\sum_{(o, Ω, s) \in M D} e_{(i, j)}^{k, (o, Ω, s)} / Δ) \leq P_{(i, j)}^{k} \leq \sum_{(o, Ω, s) \in M D} e_{(i, j)}^{k, (o, Ω, s)}, \forall (i, j) \in E, \forall k \in T

\sum_{j : (j, i) \in E} P_{(j, i)}^{k} \leq 1, \forall i \in (V \cup U), \forall k \in T

(P_{(j, i)}^{k} + P_{(i, j)}^{k}) \leq 1, \forall (i, j) \in E, \forall k \in T

(\sum_{(o, Ω, s) \in M D} n_{k, i}^{(o, Ω, s)} / Δ) \leq N_{i}^{k} \leq \sum_{(o, Ω, s) \in M D} n_{k, i}^{(o, Ω, s)}, \forall i \in (V \cup U), \forall k \in T

h_{i}^{k} \leq N_{i}^{k}, \forall i \in (V \cup U), \forall k \in T

h_{i}^{k} \leq (1 - \sum_{j : (j, i) \in E} P_{(j, i)}^{k}), \forall i \in (V \cup U), \forall k \in T

h_{i}^{k} \geq (N_{i}^{k} - \sum_{j : (j, i) \in E} P_{(j, i)}^{k}), \forall i \in (V \cup U), \forall k \in T

d_{u}^{k} = N_{u}^{k}, \forall u = U, \forall k \in T

R_{o, u}^{k} \leq h_{o}^{k}, \forall o \in V, \forall u \in U, \forall k \in T

R_{o, u}^{k} \leq d_{u}^{k}, \forall o \in V, \forall u \in U, \forall k \in T

R_{o, u}^{k} \geq (h_{o}^{k} + d_{u}^{k} - 1), \forall o \in V, \forall u \in U, \forall k \in T

T S_{k} =(\sum_{i \in V} h_{i}^{k} + \sum_{u \in U} d_{u}^{k}), \forall k \in T

Equation (7) determines the links that belong to light-tree k. Equation (8) ensures that a light-tree only has one source node. Equation (9) ensures that there do not exist rings on any light-tree. Equation (10) ensures that a node belongs to light-tree k if and only if there exist at least one multicast demand which is transmitted through this node and accommodated by light-tree k. Equations (11)-(13) search the source node of light-tree k. Equation (14) searches all destination users of light-tree k. Equations (15)-(17) ensure that light-tree k originates at source node o and terminates at user u as long as source node o and user u both belong to light-tree k. Equation (18) calculates the total number of transceivers of light-tree k.

Longest Branch Calculation Constraints:

\sum_{j : (i, j) \in E} Q_{(i, j)}^{(o, u), k} - \sum_{j : (j, i) \in E} Q_{(j, i)}^{(o, u), k} = {\begin{matrix} R_{o, u}^{k} & i = o \\ - R_{o, u}^{k} & i = u \\ 0 & o t h e r s \end{matrix}, \begin{matrix} \forall o \end{matrix} \in V, \forall u \in U, \forall k \in T

Q_{(i, j)}^{(o, u), k} \leq P_{(i, j)}^{k}, \forall (i, j) \in E, \forall o \in V, \forall u \in U, \forall k \in T

\sum_{(i, j) \in E} Q_{(i, j)}^{(o, u), k} * l_{(i, j)} \leq l_{k}, \begin{matrix} \forall o \end{matrix} \in V, \forall u \in U, \forall k \in T

Equations (19)-(20) search a light-path that originates at source node o and terminates at user u on light-tree k. Equation (21) calculates the length of the longest branch of light-tree k.

Modulation-Level Selection Constraints:

\sum_{m \in M} Z_{m}^{k} \leq 1, \forall k \in T

\sum_{m \in M} R_{m} * Z_{m}^{k} \geq l_{k}, \forall k \in T

Equation (22) ensures that a light-tree can only adopt a kind of modulation-level. Equation (23) ensures that the transmission reach of the adopted modulation-level of light-tree k must exceed the length of the longest branch of light-tree k.

On-Demand Spectrum Allocation Constraints:

E_{(i, j)}^{(o, Ω, s), k} \leq Δ * e_{(i, j)}^{(o, Ω, s), k}, \forall (i, j) \in E, \forall (o, Ω, s) \in M D, \forall k \in T

E_{(i, j)}^{(o, Ω, s), k} \geq e_{(i, j)}^{(o, Ω, s), k}, \forall (i, j) \in E, \forall (o, Ω, s) \in M D, \forall k \in T

(\sum_{j : (j, i) \in E} E_{(j, i)}^{(o, Ω, s), k} - \sum_{j : (i, j) \in E} E_{(i, j)}^{(o, Ω, s), k}) = {\begin{matrix} - | Ω | * A_{k}^{(o, Ω, s)} & i = o \\ 0 & i = o t h e r \\ A_{k}^{(o, Ω, s)} & i \in Ω \end{matrix}, \forall (o, Ω, s) \in M D, \forall k \in T

\sum_{f \in Λ} W_{(i, j), f}^{(o, Ω, s), k} \leq \sum_{m \in M} (Z_{m}^{k} * ⌈ \frac{b_{s}}{m * B} ⌉), \forall (i, j) \in E, \forall (o, Ω, s) \in M D, \forall k \in T

\sum_{f \in Λ} W_{(i, j), f}^{(o, Ω, s), k} \leq Δ * e_{(i, j)}^{k, (o, Ω, s)}, \forall (i, j) \in E, \forall (o, Ω, s) \in M D, \forall k \in T

\sum_{f \in Λ} W_{(i, j), f}^{(o, Ω, s), k} \geq Δ * (e_{(i, j)}^{k, (o, Ω, s)} - 1) + \sum_{m \in M} (Z_{m}^{k} * ⌈ \frac{b_{s}}{m * B} ⌉), \forall (i, j) \in E, \forall (o, Ω, s) \in M D, \forall k \in T

Equations (24)-(25) ensure that the commodity-flow conservation can only be deployed on each link of a light-tree. Equation (26) ensures the commodity-flow conservation at each intermediate node of a light-tree. Moreover, each destination user has an one unit of incoming commodity-flow and the number of outgoing commodity-flow of the source node is equal to the number of destination users of light-tree k. Equations (27)-(29) determine the spectrum allocated to multicast service s on each link of light-tree k.

Spectrum Continuity Constraints:

\sum_{j : (j, i) \in E} (E_{(j, i)}^{(o, Ω, s), k} * W_{(j, i), f}^{(o, Ω, s), k}) = \sum_{j : (i, j) \in E} (E_{(i, j)}^{(o, Ω, s), k} * W_{(i, j), f}^{(o, Ω, s), k}), \forall i \in V & & i \neq o, \forall f \in Λ, \forall (o, Ω, s) \in M D, \forall k \in T

\sum_{j : (j, i) \in E} E W_{(j, i), f}^{(o, Ω, s), k} = \sum_{j : (i, j) \in E} E W_{(i, j), f}^{(o, Ω, s), k}, \forall i \in V & & i \neq o, \forall f \in Λ, \forall (o, Ω, s) \in M D, \forall k \in T

E W_{(i, j), f}^{(o, Ω, s), k} \leq W_{(i, j), f}^{(o, Ω, s), k} * Δ, \forall (i, j) \in E, \forall f \in Λ, \forall (o, Ω, s) \in M D, \forall k \in T

E W_{(i, j), f}^{(o, Ω, s), k} \leq E_{(i, j)}^{(o, Ω, s), k}, \forall (i, j) \in E, \forall f \in Λ, \forall (o, Ω, s) \in M D, \forall k \in T

E W_{(i, j), f}^{(o, Ω, s), k} \geq (W_{(i, j), f}^{(o, Ω, s), k} - 1) * Δ + E_{(i, j)}^{(o, Ω, s), k}, \forall (i, j) \in E, \forall f \in Λ, \forall (o, Ω, s) \in M D, \forall k \in T

Equation (30) ensures the spectrum continuity requirement at each optical node. Because of Eq. (30) is nonlinear, we define an integer variable $E W_{(i, j), f}^{(o, Ω, s), k} = E_{(i, j)}^{(o, Ω, s), k} * W_{(i, j), f}^{(o, Ω, s), k}$ and use Eqs. (32)-(34) to linearize Eq. (30).

Spectrum Contiguity Constraints:

(1 - W_{(i, j), f}^{(o, Ω, s), k} + W_{(i, j), (f + 1)}^{(o, Ω, s), k}) \times Δ \geq \sum_{f' \in [f + 2, | Λ |]} W_{(i, j), f^{'}}^{(o, Ω, s), k}, \forall (i, j) \in E, \forall f \in Λ, \forall (o, Ω, s) \in M D, \forall k \in T

X_{(i, j), f}^{k} = \sum_{(o, Ω, s) \in M D} W_{(i, j), f}^{(o, Ω, s), k}, \forall (i, j) \in E, \forall f \in Λ, \forall k \in T

(1 - X_{(i, j), f}^{k} + X_{(i, j), (f + 1)}^{k}) \times Δ \geq \sum_{f' \in [f + 2, | Λ |]} X_{(i, j), f^{'}}^{k}, \forall (i, j) \in E, \forall f \in Λ, \forall k \in T

Equation (35) ensures that the spectrum allocated to multicast service s on each corresponding link of light-tree k must satisfy spectrum contiguity requirement. Equations (36)-(37) ensure that the spectrum allocated to all multicast service s on each link of light-tree k must also satisfy spectrum contiguity requirement. These three constraints also ensure that there does not exist node adjacent redundancy on any link of a multicast light-tree.

Uniqueness and Capacity Constraints:

\sum_{k \in T} \sum_{(o, Ω, s) \in M D} W_{(i, j), f}^{(o, Ω, s), k} \begin{matrix} \leq 1 & \begin{matrix} \forall (i, j) \end{matrix} \in E, \forall f \in Λ \end{matrix}

\sum_{k \in T} \sum_{(o, Ω, s) \in M D} \sum_{f \in Λ} W_{(i, j), f}^{(o, Ω, s), k} \begin{matrix} \leq | Λ | & \begin{matrix} \forall (i, j) \end{matrix} \in E \end{matrix}

Equation (38) ensures that an FS in a fiber link can only be assigned to one multicast service. Equation (39) ensures that the total number of FSs assigned to all multicast services through a fiber link cannot exceed this link’s capacity.

4.2 The ILP model of the C-RMSA strategy

For the C-RMSA strategy, the allocated FSs on each link of a light-tree are same even if multiple multicast services which have the different requesters are aggregated together.

Variables:

_{$K_{m}^{(o, Ω, s), k} \in {0, 1}$}: equals one if light-tree k adopts modulation-level m and multicast demand MD(o, $Ω$ ,s) is aggregated on light-tree k, otherwise 0.

Objective Function:

\min (α * \sum_{k \in T} T S_{k} + \sum_{k \in T} \sum_{(i, j) \in E} \sum_{f \in Λ} X_{(i, j), f}^{k})

The objective in Eq. (40) also aims to minimize the total optical transceiver and spectrum consumptions of all constructed light-trees for all multicast demands. When the value of α is set to a large positive integer, the ILP model prefers to construct less light-trees even if more spectrum resource will be consumed. In other words, the parameter promotes to multicast service aggregation. In the designed ILP model for the OD-RMSA strategy, multicast service aggregation constraints, light-tree construction constraints, longest branch calculation constraints, and modulation-level selection constraints all can be used by the C-RMSA strategy. The spectrum continuity and contiguity constraints, uniqueness and capacity constraints merely need a minor modification. The spectrum allocation constraints of the C-RMSA strategy are listed as follows.

Spectrum Allocation Constraints:

K_{m}^{(o, Ω, s), k} \leq Z_{m}^{k}, \forall m \in M, \forall (o, Ω, s) \in M D, \forall k \in T

K_{m}^{(o, Ω, s), k} \leq A_{k}^{(o, Ω, s)}, \forall m \in M, \forall (o, Ω, s) \in M D, \forall k \in T

K_{m}^{(o, Ω, s), k} \geq (Z_{m}^{k} + A_{k}^{(o, Ω, s)} - 1), \forall m \in M, \forall (o, Ω, s) \in M D, \forall k \in T

\sum_{f \in Λ} X_{(i, j), f}^{k} \leq \sum_{(o, Ω, s) \in M D} \sum_{m \in M} (K_{m}^{(o, Ω, s), k} * ⌈ \frac{b_{s}}{m * B} ⌉), \forall (i, j) \in E, \forall k \in T

\sum_{f \in Λ} X_{(i, j), f}^{k} \leq Δ * P_{(i, j)}^{k}, \forall (i, j) \in E, \forall k \in T

\sum_{f \in Λ} X_{(i, j), f}^{k} \geq Δ * (P_{(i, j)}^{k} - 1) + \sum_{(o, Ω, s) \in M D} \sum_{m \in M} (K_{m}^{(o, Ω, s), k} * ⌈ \frac{b_{s}}{m * B} ⌉), \forall (i, j) \in E, \forall k \in T

Equations (41)-(43) calculate the value of $K_{m}^{(o, Ω, s), k}$ . Equations (44)-(46) calculate the number of FSs assigned to each link of a light-tree. These equations ensure that the allocated FSs on each link of a light-tree are same. Then, spectrum continuity and contiguity constraints, uniqueness and capacity constraints only need to be carried out on the variable $X_{(i, j), f}^{k}$ .

5. Heuristic approaches

In this section, a heuristic algorithm is developed to search all MAGs among a large number of multicast demands. Based on MAGs, a heuristic algorithm is developed to realize the OD-RMSA strategy for the LT-MFA scheme in large-scale EONs.

5.1 The MAG algorithm

Since a BV-WSS can only select continuous FSs, we define MAG to eliminate node adjacent redundancy on each link of a light-tree. For a large number of multicast services, we should search all MAGs and the number of all found MAGs is as less as possible. A multicast service group can be transformed into a MAG corresponding to the corresponding multicast tree. Therefore, the routing of a light-tree should be given first and MAGs are searched according to this routing. Here, we adopt the greedy algorithm to search MAGs. For a large number of given multicast services, we first construct an empty multicast service group and add the multicast service with the maximum number of requesters into this group. Then, we add other multicast services into this multicast service group and conduct routing calculation for this multicast service group. If the added multicast service causes this multicast service group cannot be transformed into a MAG corresponding to the calculated routing, this multicast service cannot be added. To improve success rate, we choose the multicast service that has more common requesters with multicast services in the constructed multicast service group as the candidate multicast service to be added. In the following pseudo-codes, MDS denotes a multicast demand set in which all multicast demands have a common source, MSG denotes a multicast service group, MSG_R denotes all requesters of multicast service group MSG, ms-max( $Ω$ ) denotes all requesters of multicast demand ms-max, ms-max(s) denotes the multicast service of multicast demand ms-max, and TMD denotes all traversed multicast demands.

Algorithm 1. The MAG Algorithm

View Table | View all tables in this article

The MAG algorithm constructs a MAG at each time. For a large number of multicast demands, this algorithm will not be terminated until each multicast demand is accommodated by a MAG. The time complexity of the MAG algorithm is O( $| E | * N^{2}$ ), where $| E |$ is the total number of fiber links and N is the total number of multicast demands. We design the CA algorithm to transform a multicast service group into a MAG corresponding to the corresponding multicast tree. Here, we define the concept of adjustable column set (ACS) which is used to adjust the positions of columns on relationship matrix. ACS can be modeled as ACS = {… AB_i, … c_j, …}, AB = {… C_m, … c_n, …}, C denotes a group of columns and c denotes a column. The positions of all elements in an ACS are adjustable and the positions of all elements in a C are adjustable. The column adjusting (CA) algorithm adjusts the first row of relationship matrix and makes sure all values of 1 in first row are continuous, and calculates adjustable column set. Then, it adjusts the second row of relationship matrix according to adjustable column set and makes sure all values of 1 in second row are continuous, and updates adjustable column set. And so on, the CA algorithm adjusts the positions of columns at each row until all values of 1 are continuous at any row.

In Fig. 7, for the first four rows, all columns have be adjusted and all values of 1 are continuous in each row. For the fifth row, ACS is {AB₁, AB₂, c₆}, where AB₁ = {c₁, c₂, c₃, [c₄, c₅]} and AB₂ = {[c₇, c₈, c₉, c₁₀]}. In Fig. 7, we can find that all elements in ACS are adjustable and all elements in C are adjustable. The MAG algorithm adjusts columns at the following row according to the obtained ACS. All adjustable elements in ACS can be classified into two types as presented in Fig. 8. First, if all columns at a row cannot be classified into these two types, this multicast service group cannot be transformed into a MAG. In the CA algorithm, all elements in C are adjusted according to these two feasible strategies and all elements in ACS are adjusted to ensure that all values of 1 are continuous. In the following pseudo-codes, RM denotes the initial relationship matrix and T denotes the corresponding multicast tree.

Fig. 7 Adjustable column set construction

Download Full Size | PDF

Fig. 8 Two feasible strategies for column adjustment

Download Full Size | PDF

Algorithm 2. The CA Algorithm

View Table | View all tables in this article

The time complexity of the CA Algorithm is O( $| E | * N$ ), where $| E |$ is the total number of fiber links and N is the total number of multicast demands.

Figure 9(a) presents a relationship matrix with seven rows and six columns. For the first row, the adjustable set is {1, 2, 3, 4, 5, 6}. We adjust all columns and make sure all values of 1 are continuous and put left. As presented in Fig. 9(b), for the second row, the adjustable set is {{ [1,3,6]}, 2, 4, 5}. Since all values of 1 in [1,3,6] and {2, 4, 5} are continuous and located to the left, the second row does not need to conduct column adjustment. Then, we conduct column adjustment for {{ [1,3,6]}, 2, 4, 5} according to the first feasible strategy. Similarly, as presented in Fig. 9(d), all values of 1in {2, 1 [3,6], } and {4, 5} are continuous and located to the left, the third row does not need to conduct column adjustment. Then, we conduct column adjustment for {{2, 1 [3,6], }, 4, 5} according to the first feasible strategy. The CA Algorithm calculates ACS for each row and adjusts all columns according to ACS.

Fig. 9 The CA algorithm for a relationship matrix.

Download Full Size | PDF

5.2 Heuristic OD-RMSA algorithm

Heuristic OD-RMSA algorithm conducts on-demand spectrum allocation for each MAG on the corresponding multicast tree. It first calculates the length of the longest branch of the corresponding multicast tree and determines the highest available modulation level. Then, it calculates the number of required FSs and determines the corresponding relative starting and ending positions of allocated FSs on each link of the corresponding multicast tree. To reduce computation complexity, we adopt the First-Fit strategy to realize on-demand spectrum allocation. Here, we assume the transmission reaches of modulation-levels BPSK, QPSK, and 8QAM are 5000 km, 2500 km, and 1250 km respectively. Moreover, the transmission rates of a FS with modulation-levels BPSK, QPSK, and 8QAM are 12.5 Gbps, 25 Gbps, and 37.5 Gbps respectively [13]. We also assume that the transmission reach of an optical signal along a multicast light-tree is equal to that along a light-path with the help of optical amplifiers [12]. To prevent marginal FSs of two adjacent multicast services influencing bandwidth-variable spectrum selection, one free FS is inserted as the guard band (GB) between any two adjacent multicast services in MAG. In the following pseudo-codes, LT denotes the constructed light-tree for MAG, $Λ$ is the ordered set of FSs in each fiber link, and AB a boolean variable.

Algorithm 3. Heuristic OD-RMSA Algorithm

View Table | View all tables in this article

The time complexity of Algorithm 3 is O( $| E | \times N + | E | \times | Λ |$ ). It is guaranteed to run in polynomial time.

6. Performance evaluation

In this section, the performance of the proposed OD-RMSA strategy for the LT-MSA scheme is evaluated through the developed ILP model and heuristic algorithms. The computer in our simulations is configured with an Intel Core i5 3.3 GHz CPU and 8 G RAM.

6.1. Simulation environment and traffic model

For ILP models, these are implemented by using JAVA in ILOG CPLEX V12.5. In Fig. 10(a), the n6e8 network is the simulation topology. We assume that each fiber link is bidirectional and contains 40 FSs. All used multicast demands are listed in Table 1. The total number of multicast demands is 9. The transmission rate of each multicast service is selected from the set {40Gbps, 60Gbps, and 80Gbps}. The value of parameter α is set to 100. Since the number of trees T greatly influences the running time of the designed model, we believe the number of trees T should not be set to a fixed number. In the code, we increase the number of T for several times (begin with 2 and add 1 at each time) until the result is unchanged.

Fig. 10 Simulation topologies (a) n6e8, (b) NSFNet.

Download Full Size | PDF

Table 1. All Used Multicast Demands in ILP Model.

View Table | View all tables in this article

For heuristic algorithms, these are implemented by using JAVA in Eclipse-JEE-LUNA-SR2. In Fig. 10(a), the NSFNet network is the simulation topology. We assume that each fiber link in NSFNet is bidirectional and contains 320 FSs and each node is equipped with tunable transponders which can use different sets of contiguous FSs. Multicast demands are generated at each optical node according to a uniform distribution. The numbers of generated multicast demands are {40, 50, 60, 70, 80, 90, 100, 110, and 120}. The requesters and source of each multicast demand are generated randomly. Moreover, the average requester number (ARN) of all multicast demands is set to 4, 6, and 8. The ARN is used to represent the size of a multicast demand. Each multicast demand is configured with a multicast service. The transmission rate of each multicast service is selected from the set {40Gbps, 60Gbps, and 80Gbps}. All numerical results are the average of the 10000 times.

6.2. The OD-RMSA under the ILP model

For the proposed ILP models, the transceiver and spectrum consumptions of the LT-OM scheme, the C-RMSA strategy, the OD-RMSA strategy, and heuristic algorithm are evaluated. The numbers of constructed light-trees of these schemes are also given.

Figure 11 and Fig. 12 present the optical transceiver and spectrum consumptions of the LT-OM scheme, the C-RMSA strategy, and the OD-RMSA strategy respectively. Figure 11 shows that the C-RMSA strategy and the OD-RMSA strategy both can reduce transceiver consumption by approximately 50% than the LT-OM scheme. In ILP models, the parameter α plays an important role that it promotes multicast demand aggregation. Figure 12 shows that the OD-RMSA strategy can reduce spectrum consumption by approximately 25.89% than the C-RMSA strategy. Moreover, the spectrum consumption of the OD-RMSA strategy is more slightly than the LT-OM scheme. That because the LT-OM scheme can adopt a highest modulation level for each multicast demand. However, for the OD-RMSA strategy, the adopted modulation level must satisfy the transmission distance requirement of any aggregated multicast demand. In other words, the OD-RMSA strategy may adopt a lower modulation level than the LT-OM scheme in some cases. Therefore, the OD-RMSA strategy will consume more spectrum resource than the LT-OM scheme. Figure 13 presents the number of constructed light-trees. The results show that the OD-RMSA strategy can aggregate as many multicast demands as the C-RMSA strategy. Therefore, the transceiver consumption of the OD-RMSA strategy is equal to that of the C-RMSA strategy. The developed heuristic approach is also verified in n6e8. The results in Fig. 11, Fig. 12 and Fig. 13 show that the heuristic approach presents good performance as the ILP model.

Fig. 11 Transceiver consumption.

Download Full Size | PDF

Fig. 12 Spectrum consumption.

Download Full Size | PDF

Fig. 13 Light-Tree number.

Download Full Size | PDF

Figure 14 presents the time consumption of the OD-RMSA strategy. The results show that the running time exceeds 12120 seconds when the number of multicast demands is 9. When the traffic load continues to increase, the ILP model is not applicable. Usually, we use the ILP model to realize the OD-RMSA strategy in a small topology with a low traffic load.

Fig. 14 Time consumption.

Download Full Size | PDF

6.3. The OD-RMSA under heuristic approach

For heuristic algorithms, the MAG number, success multicast demand number, transceiver consumption, and spectrum consumptions of the C-RMSA strategy and the OD-RMSA strategy are evaluated. When multiple multicast demands in a MAG are aggregated together, the aggregated multicast flow cannot exceed the capacity of an O-OFDM transmitter. In simulations, we assume that each bandwidth-variable transponder can produce at most 50 FSs. To measure the transceiver consumption of the OD-RMSA strategy, we assume that the number of configured transceivers at each optical node is more than enough. All numerical results are the average of the 10000 times. Here, we assume the significance level is 0.05. Then, the confidence level is 95%. We use the following formula to calculate the confidence interval of each obtained result. In Eq. (47), n is the number of samples, X is average value, S is sample variance, and β is the significance level.

[X \pm \frac{S}{\sqrt{n}} t_{β / 2} (n - 1)]

Figure 15 presents the number of constructed MAGs and multicast demand groups of the OD-RMSA strategy and the C-RMSA strategy. When ARN = 4, the confidence intervals of the number of constructed MAGs of the OD-RMSA strategy are [19 ± 0.2554], [22 ± 0.2799], [25 ± 0.3016], [28 ± 0.3120], [30 ± 0.3261], [33 ± 0.3284], [35 ± 0.3290], [38 ± 0.3295], and [40 ± 0.3316] when multicast demand number is 40, 50, …, 120 respectively. When ARN = 6, the confidence intervals of the number of constructed MAGs of the OD-RMSA strategy are [21 ± 0.2445], [25 ± 0.2597], [28 ± 0.2974], [32 ± 0.2987], [35 ± 0.3259], [38 ± 0.3327], [41 ± 0.3385], [45 ± 0.3428], and [48 ± 0.3645] when multicast demand number is 40, 50, …, 120 respectively. When ARN = 8, the confidence intervals of the number of constructed MAGs of the OD-RMSA strategy are [22 ± 0.2402], [26 ± 0.2503], [30 ± 0.2671], [34 ± 0.2774], [38 ± 0.2898], [41 ± 0.3321], [45 ± 0.3433], [48 ± 0.3512] and [52 ± 0.3721] when multicast demand number is 40, 50, …, 120 respectively. With the increase of the number of multicast demands, the OD-RMSA strategy will construct more MAGs. That is because it is difficult to construct a MAG which contains a large number of multicast demands. However, the number of constructed multicast demand groups of the C-RMSA strategy changes with a small range. Figure 13 show that the OD-RMSA strategy increases the number of multicast demand groups by approximately 88.8% when ARN = 4, by approximately 119% when ARN = 6, and by approximately 135% when ARN = 8 than the C-RMSA strategy. The OD-RMSA strategy can make better use of spectrum resource and thus accommodate more multicast demands.

Fig. 15 MAG number and multicast demand group number (a) ARN = 4, (b) ARN = 6, (c) ARN = 8.

Download Full Size | PDF

Figure 16 presents the number of success accommodated multicast demands of the OD-RMSA strategy, the C-RMSA strategy, and the LT-OM scheme. When ARN = 4, the confidence intervals of the number of constructed MAGs of the OD-RMSA strategy are [40 ± 0.0], [50 ± 0.0], [59 ± 0.1885], [68 ± 0.4705], [69 ± 0.6639], [71 ± 0.7784], [71 ± 0.8624], [72 ± 0.8683], and [72 ± 0.8971] when multicast demand number is 40, 50, …, 120 respectively. When ARN = 6, the confidence intervals of the number of constructed MAGs of the OD-RMSA strategy are [40 ± 0.0], [50 ± 0.0], [56 ± 0.3178], [57 ± 0.4070], [57 ± 0.4076], [57 ± 0.4181], [57 ± 0.4227], [57 ± 0.4240], and [57 ± 0.4433] when multicast demand number is 40, 50, …, 120 respectively. When ARN = 8, the confidence intervals of the number of constructed MAGs of the OD-RMSA strategy are [40 ± 0.0], [50 ± 0.0], [53 ± 0.169], [53 ± 0.2428], [53 ± 0.2670], [53 ± 0.2751], [53 ± 0.2971], [53 ± 0.3028], and [53 ± 0.3340] when multicast demand number is 40, 50, …, 120 respectively. Figure 16(a) shows that the OD-RMSA strategy can improve the success number by approximately 25.2% than the C-RMSA strategy, but is lower by approximately 18.1% than the LT-OM scheme when ARN = 4. Figure 16(b) shows that the OD-RMSA strategy can improve the success number by approximately 7.5% than the C-RMSA strategy, but is lower by approximately 4.1% than the LT-OM scheme when ARN = 6. Figure 16(c) shows that the OD-RMSA strategy can improve the success number by approximately 1.5% than the C-RMSA strategy, but is lower by approximately 1.3% than the LT-OM scheme when ARN = 8. Since the LT-OM scheme can adopt a highest modulation level for each multicast demand, it consumes less spectrum resource and can accommodate more multicast demands. Although the LT-OM scheme accommodates more multicast demands, it consumes a large number of transceivers. Moreover, Fig. 16(a) shows that the OD-RMSA strategy presents good performance than the C-RMSA strategy when the value of ARN is small. The results show that the OD-RMSA strategy is more suitable for aggregating multicast demands with a little number of requesters.

Fig. 16 Success multicast demand number (a) ARN = 4, (b) ARN = 6, (c) ARN = 8.

Download Full Size | PDF

Figure 17 presents the transceiver consumptions of the OD-RMSA strategy, the C-RMSA strategy, and the LT-OM scheme. When ARN = 4, the confidence intervals of the number of constructed MAGs of the OD-RMSA strategy are [147 ± 0.8775], [177 ± 1.095], [206 ± 1.2768], [229 ± 2.039], [231 ± 2.4913], [232 ± 2.894], [231 ± 2.896], [231 ± 2.924], and [229 ± 3.23] when multicast demand number is 40, 50, …, 120 respectively. When ARN = 6, the confidence intervals of the number of constructed MAGs of the OD-RMSA strategy are [203 ± 1.093], [246 ± 1.3709], [268 ± 2.0196], [266 ± 2.656], [262 ± 2.691], [260 ± 2.754], [256 ± 2.831], [255 ± 2.848], and [251 ± 2.982] when multicast demand number is 40, 50, …, 120 respectively. When ARN = 8, the confidence intervals of the number of constructed MAGs of the OD-RMSA strategy are [251 ± 1.745], [304 ± 1.765], [313 ± 2.18], [308 ± 2.35], [300 ± 2.565], [296 ± 2.643], [290 ± 2.675], [288 ± 2.689], and [283 ± 2.745] when multicast demand number is 40, 50, …, 120 respectively. Figure 17(a) shows that the OD-RMSA strategy can reduce the transceiver consumption by approximately 45.3% than the LT-OM scheme, but is higher by approximately 76.6% than the C-RMSA strategy when ARN = 4. Figure 17(b) shows that the OD-RMSA strategy can reduce the transceiver consumption by approximately 37.3% than the LT-OM scheme, but is higher by approximately 79.9% than the C-RMSA strategy when ARN = 6. Figure 17(c) shows that the OD-RMSA strategy can reduce the transceiver consumption by approximately 37.8% than the LT-OM scheme, but is higher by approximately 92.9% than the C-RMSA strategy when ARN = 8. Compared with the LT-OM scheme, the OD-RMSA strategy will save a large number of transceivers. Since the C-RMSA strategy only constructs a small number of multicast demand groups, the transceiver consumption of the C-RMSA strategy is least. However, the C-RMSA strategy accommodates less multicast demands and consumes more spectrum resources. Since n6e8 is a small topology. It is not easy to produce node adjacent redundancy when the traffic load is small, so that the OD-RMSA strategy can aggregate as many multicast demands as the C-RMSA strategy. Therefore, the transceiver consumption of the OD-RMSA strategy is equal to the transceiver consumption of the C-RMSA strategy. In NSFNet with a heavy traffic load, the node adjacent redundancy restricts the aggregation ability of the OD-RMSA strategy. Therefore, the OD-RMSA strategy consumes more transceivers than the C-RMSA strategy.

Fig. 17 Transceiver consumption (a) ARN = 4, (b) ARN = 6, (c) ARN = 8.

Download Full Size | PDF

Figure 18 presents the spectrum consumptions of the OD-RMSA strategy, the C-RMSA strategy, and the LT-OM scheme. When ARN = 4, the confidence intervals of the number of constructed MAGs of the OD-RMSA strategy are [0.1083 ± 0.0012], [0.1346 ± 0.0012], [0.1635 ± 0.0013], [0.1840 ± 0.0015], [0.1896 ± 0.0018], [0.1917 ± 0.0019], [0.1937 ± 0.0021], [0.1949 ± 0.0022], and [0.1962 ± 0.0023] when multicast demand number is 40, 50, …, 120 respectively. When ARN = 6, the confidence intervals of the number of constructed MAGs of the OD-RMSA strategy are [0.1413 ± 0.0008], [0.1752 ± 0.0008], [0.1984 ± 0.0013], [0.1999 ± 0.0014], [0.2005 ± 0.0014], [0.2010 ± 0.0015], [0.2014 ± 0.0015], [0.2015 ± 0.0015], and [0.2019 ± 0.0015] when multicast demand number is 40, 50, …, 120 respectively. When ARN = 8, the confidence intervals of the number of constructed MAGs of the OD-RMSA strategy are [0.1669 ± 0.0007], [0.2065 ± 0.0008], [0.2216 ± 0.0009], [0.222 ± 0.0009], [0.2221 ± 0.0009], [0.2223 ± 0.0009], [0.2223 ± 0.0009], [0.2225 ± 0.0010], and [0.2225 ± 0.0011] when multicast demand number is 40, 50, …, 120 respectively. Figure 18(a) shows that the OD-RMSA strategy can reduce the spectrum consumption by approximately 30.1% than the C-RMSA strategy when ARN = 4. Figure 18(b) shows that the OD-RMSA strategy can reduce the spectrum consumption by approximately 27.65% than the C-RMSA strategy when ARN = 6. Figure 18(c) shows that the OD-RMSA strategy can reduce the spectrum consumption by approximately 21.14% than the C-RMSA strategy when ARN = 8. In Fig. 18(a), when the number of multicast demands is 110 and 120, the spectrum consumption of the LT-OM scheme is greater than the OD-RMSA strategy. That is because the LT-OM scheme accommodates more multicast demands than the OD-RMSA strategy at this time. Besides, the spectrum consumption of the OD-RMSA strategy is more close to the LT-OM scheme. We can find that the OD-RMSA strategy is a promising routing and spectrum allocation strategy for the LT-MSG scheme with high spectrum efficiency and low transceiver consumption.

Fig. 18 Spectrum consumption (a) ARN = 4, (b) ARN = 6, (c) ARN = 8.

Download Full Size | PDF

6.4. The fragmentation management for the LT-MSA scheme

In EONs, fragmentation effect is an important influence factor of spectrum efficiency. Since we consider the OD-RMSA strategy, more spectrum fragmentations will be produced. Therefore, fragmentation effect can greatly influence the spectrum efficiency of the LT-MSA scheme. Compared with the light-path, the light-tree is easy to produce spectrum fragmentation and is difficult to defragmentation. At presents, most studies focus on fragmentation management for light-paths in EONs [24,25]. How to achieve fragmentation management for the LT-MSA scheme becomes an important research focus. In general, non-defragmentation approach and defragmentation approach are both suitable for the LT-MSA scheme. These approaches should consider all links of a light-tree, node architecture, and available modulation levels. For defragmentation approaches, to avoid service interruption, hitless defragmentation approaches are more suitable. It adjusts the routing or spectrum position of all constructed light-trees. In some cases, reorganizing multicast service aggregation can also help to reduce spectrum fragmentation.

7. Conclusions

The proposed OD-RMSA strategy for the LT-MAG scheme provides a cost-efficient and spectrum-efficient method to realize all-optical multicasting for a large number of finer-grained multicast services in EONs. It also can help to expand the application scope of the LT-MSA scheme that supports accommodating ordinary and secure multicast services simultaneously. Besides, the optimization of ILP model and the fragmentation management for the LT-MSA scheme are important research focuses in our future works.

Funding

National Natural Science Foundation of China (61701039); Fundamental Research Funds for the Central Universities; National Science Foundation for Outstanding Youth Scholars of China (61622102).

References and links

1. A. Muhammad, M. Fiorani, L. Wosinska, and J. Chen, “Joint optimization of resource allocation for elastic optical intra-datacenter network,” IEEE Commun. Lett. 20(9), 1760–1763 (2018). [CrossRef]

2. H. Yang, J. Zhang, Y. Zhao, Y. Ji, J. Wu, Y. Lin, J. Han, and Y. Lee, “Performance evaluation of multi-stratum resources integrated resilience for software defined inter-data center interconnect,” Opt. Express 23(10), 13384–13398 (2015). [CrossRef] [PubMed]

3. Y. Dong, S. Zhao, H. Ran, Y. Li, and Z. Zhu, “Routing and wavelength assignment in a satellite optical network based on ant colony optimization with the small window strategy,” J. Opt. Commun. Netw. 7(10), 995–1000 (2015). [CrossRef]

4. M. Jinno, H. Takara, B. Kozicki, Y. Tsukishima, Y. Sone, and S. Matsuoka, “Spectrum-efficient and scalable elastic optical path network: architecture, benefits, and enabling technologies,” IEEE Commun. Mag. 47(11), 66–73 (2009). [CrossRef]

5. I. B. Djordjevic and B. Vasic, “Orthogonal frequency division multiplexing for high-speed optical transmission,” Opt. Express 14(9), 3767–3775 (2006). [CrossRef] [PubMed]

6. Z. Zheng, X. Lv, F. Zhang, D. Wang, E. Sun, Y. Zhu, K. Zou, and Z. Chen, “Fiber nonlinearity mitigation in 32-Gbaud 16QAM nyquist-WDM systems,” J. Lightwave Technol. 34(9), 2182–2187 (2016). [CrossRef]

7. S. Sarmiento, J. A. Altabas, D. Izquierdo, I. Garces, S. Spadaro, and J. A. Lazaro, “Cost-effective DWDM ROADM design for flexible sustainable optical metro–access networks,” J. Opt. Commun. Netw. 9(12), 1116–1124 (2017). [CrossRef]

8. S. Mukherjee, F. Bronzino, S. Srinivasan, J. Chen, and D. Raychaudhuri, “Achieving scalable push multicast services using global name resolution,” in Proc. GLOBECOM (2016). [CrossRef]

9. G. N. Rouskas, “Optical layer multicast: rationale, building blocks, and challenges,” IEEE Netw. 17(1), 60–65 (2003). [CrossRef]

10. K. Walkowiak, R. Go’scie’n, M. Klinkowski, and M. Wo’zniak, “Optimization of multicast traffic in elastic optical networks with distance-adaptive transmission,” IEEE Commun. Lett. 18(12), 2117–2120 (2014). [CrossRef]

11. R. Lin, M. Zukerman, G. Shen, and W. Zhong, “Design of light-tree based optical inter-datacenter networks,” J. Opt. Commun. Netw. 5(12), 1443–1455 (2013). [CrossRef]

12. X. Li, L. Zhang, Y. Tang, and S. Huang, “Link importance incorporated failure probability measuring solution for multicast light-Trees in elastic optical networks,” Opt. Eng. 57(3), 036117 (2018). [CrossRef]

13. L. Yang, L. Gong, F. Zhou, B. Cousin, M. Moln’ar, and Z. Zhu, “Leveraging light forest with rateless network coding to design efficient all-optical multicast schemes for elastic optical networks,” J. Lightwave Technol. 33(18), 3945–3955 (2015). [CrossRef]

14. X. Li, L. Zhang, Y. Tang, J. Guo, and S. Huang, “Distributed sub-tree-based optical multicasting scheme in elastic optical data center networks,” IEEE Access 6(1), 6465–6478 (2018).

15. Y. Zhu and J. P. Jue, “Multi-class flow aggregation for IPTV content delivery in IP over optical core networks,” J. Lightwave Technol. 27(12), 1891–1903 (2009). [CrossRef]

16. X. Huang, F. Farahmand, and J. P. Jue, “Multicast traffic grooming in wavelength-routed WDM mesh networks using dynamically changing light-trees,” J. Lightwave Technol. 23(10), 3178–3187 (2005). [CrossRef]

17. C. Xue, X. Li, Y. Tang, L. Zhang, T. Gao, B. Guo, and S. Huang, “Light-tree based multicast flow aggregation scheme in elastic optical datacenter networks,” in Proc. ICOCN (2017). [CrossRef]

18. L. Zhang, X. Li, Y. Tang, T. Gao, B. Guo, and S. Huang, “Modulation-level-awared multicast flow aggregation scheme in elastic optical datacenter networks,” in Proc. ACP (2017). [CrossRef]

19. X. Li, Y. Tang, J. Guo, T. Gao, B. Guo, and S. Huang, “A novel BV-WSS based flow aggregation (BV-WSS-FA) scheme for finer-grained services in elastic optical networks,” in Proc. ICOCN (2017). [CrossRef]

20. B. C. Chatterjee, N. Sarma, and E. Oki, “Routing and spectrum allocation in elastic optical networks: a tutorial,” IEEE Comm. Surv. and Tutor. 17(3), 1776–1800 (2015). [CrossRef]

21. G. Zhang, M. D. Leenheer, A. Morea, and B. Mukherjee, “A survey on OFDM-based elastic core optical networking,” IEEE Comm. Surv. and Tutor. 15(1), 65–87 (2013). [CrossRef]

22. N. Amaya, G. Zervas, and D. Simeonidou, “Architecture on demand for transparent optical networks,” in Proc. 13th IEEE ICTON (2011), pp. 1–4. [CrossRef]

23. N. Sambo, G. Meloni, G. Berrettini, F. Paolucci, A. Malacarne, A. Bogoni, F. Cugini, L. Potì, and P. Castoldi, “Demonstration of data and control plane for optical multicast at 100 and 200 Gb/s with and without frequency conversion,” J. Opt. Commun. Netw. 5(7), 667–676 (2013). [CrossRef]

24. B. C. Chatterjee, S. Ba, and E. Oki, “Fragmentation problems and management approaches in elastic optical networks: a survey,” IEEE Comm. Surv. and Tutor. 20(1), 183–210 (2018). [CrossRef]

25. B. C. Chatterjee, T. Sato, and E. Oki, “Recent research progress on spectrum management approaches in software-defined elastic optical networks,” Opt. Switching Networking 30, 93–104 (2018). [CrossRef]

Algorithm 1: The MAG Algorithm
Input: G(V,U,E), MDS
Output: MAG
1: set MSG←Ф, MSG_R←Ф, TMD←Ф;
2: search multicast demand ms-max which has the maximum number of requesters in MDS and add ms-max(s) into MSG, MSG_R←(MSG_R∪ms-max( $Ω$ )), TMD←(TMD∪ms-max);
3: for each multicast demand MD(o, $Ω$ ,s) in MDS/TMD do
4:	calculate $r a t i o = \frac{\| Ω \cap M S G_R \|}{\| Ω \cup M S G_R \|}$ ;
5:	search multicast demand ms-can with the maximum value of ratio.
6: end for
7: calculate a shortest-path tree T for (MSG∪ms-can(s));
8: use Algorithm 2 to construct a MAG for (MSG∪ms-can(s)) corresponding to T;
9: if (MAG≠NULL) do
10:	add ms-can(s) into MSG, MSG_R←(MSG_R∪ms-can( $Ω$ )), TMD←(TMD∪ms-can), and goto step 3;
11: else
12:	TMD←(TMD∪ms-can) and goto step 3;
13: end if
14: return MAG;

Algorithm 2: The CA Algorithm
Input: G(V,U,E), MSG, T
Output: MAG
1: construct relationship matrix RM for MSG corresponding to T;
2: for each row row_r of relationship matrix RM do
3:	calculate adjustable column set ACS for row_r;
4:	adjust RM according to each C in ACS through two feasible strategies;
5:	adjust RM according to ACS and make sure all values of 1 are continuous in current row;
6:	if all values of 1 are continuous at any line of RM do
7:		sort MSG according to RM, MAG←MSG, return MAG;
8:	end if
9: end for
10: return NULL;

Algorithm 3: Heuristic OD-RMSA Algorithm
Input: G(V,U,E), MAG, T
Output: LT
1: calculate the length of the longest branch of multicast tree T and search the highest available modulation-level m;
2: for each link l on multicast tree T do
3:	set start_l←0, end_l←0;
4:	search all multicast services MS_l in MAG which is reserved on link l;
5:	N = $\sum_{m s \in M S_l} (⌈ \frac{b_{m s}}{m * B} ⌉ + 1)$ ;
6:	for each multicast service ms in a MAG (in the sorted order) do
7:			If (ms is not reserved on link l) do
8:					start_l←(start_l + $⌈ \frac{b_{m s}}{m B} ⌉ + 1$* );
9:			else
10:						end_l←(start_l + N-1), goto step 2;
11:				end if
12:		end for
13: end for
14: for each FS f in Λ (in ascending order) do
15:				set AB←true;
16:				for each link l on multicast tree T do
17:						if (all FSs between [f + start_l, f + end_l] is not free) do
18:							AB←false;
19:						end if
20:				end for
21:				if (AB = = true) do
22:						for each link l on multicast tree T do
23:							allocate FSs between [f + start_l, f + end_l] on link l, LT←LT∪l;
24:						end for
25:						return LT;
26:				end if
27: end for

Multicast demand number			source node	users	multicast service
9	6	3	1	{u₂, u₃, u₆}	s₁: 40Gbps
			1	{u₅, u₆}	s₂: 60Gbps
			1	{u₃, u₄, u₅}	s₃: 80Gbps
			3	{u₂, u₅}	s₄: 40Gbps
			3	{u₁, u₆, u₅}	s₅: 60Gbps
			3	{u₁, u₂, u₆}	s₆: 80Gbps
			6	{u₁, u₂, u₃}	s₇: 40Gbps
			6	{u₃, u₄, u₅}	s₈: 60Gbps
			6	{u₁, u₂, u₃, u₄}	s₉: 80Gbps

Algorithm 1: The MAG Algorithm
Input: G(V,U,E), MDS
Output: MAG
1: set MSG←Ф, MSG_R←Ф, TMD←Ф;
2: search multicast demand ms-max which has the maximum number of requesters in MDS and add ms-max(s) into MSG, MSG_R←(MSG_R∪ms-max( $Ω$ )), TMD←(TMD∪ms-max);
3: for each multicast demand MD(o, $Ω$ ,s) in MDS/TMD do
4:	calculate $r a t i o = \frac{\| Ω \cap M S G_R \|}{\| Ω \cup M S G_R \|}$ ;
5:	search multicast demand ms-can with the maximum value of ratio.
6: end for
7: calculate a shortest-path tree T for (MSG∪ms-can(s));
8: use Algorithm 2 to construct a MAG for (MSG∪ms-can(s)) corresponding to T;
9: if (MAG≠NULL) do
10:	add ms-can(s) into MSG, MSG_R←(MSG_R∪ms-can( $Ω$ )), TMD←(TMD∪ms-can), and goto step 3;
11: else
12:	TMD←(TMD∪ms-can) and goto step 3;
13: end if
14: return MAG;

On-demand routing, modulation level and spectrum allocation (OD-RMSA) for multicast service aggregation in elastic optical networks

Abstract

1. Introduction

2. Implementation basis

2.1 The O-OFDM based multicast service aggregation

2.2 Elastic optical node architectures

2.3 Our contributions

3. Problem description

3.1 The C-RMSA strategy

3.2 The OD-RMSA strategy

4. The ILP model

4.1 The ILP model of the OD-RMSA Strategy

4.2 The ILP model of the C-RMSA strategy

5. Heuristic approaches

5.1 The MAG algorithm

5.2 Heuristic OD-RMSA algorithm

6. Performance evaluation

6.1. Simulation environment and traffic model

6.2. The OD-RMSA under the ILP model

6.3. The OD-RMSA under heuristic approach

6.4. The fragmentation management for the LT-MSA scheme

7. Conclusions

Funding

References and links

Cited By

Figures (18)

Tables (4)

Equations (47)

Optics Express