Routing and Spectrum Allocation in Spectrum-Sliced Elastic Optical Path Networks: A Primal-Dual Framework

Abstract

The recent decade has witnessed a tremendous growth of Internet traffic, which is expected to continue climbing for the foreseeable future. As a new paradigm, Spectrum-sliced Elastic Optical Path (SLICE) networks promise abundant (elastic) bandwidth to address the traffic explosion, while bearing other inherent advantages including enhanced signal quality and extended reachability. The fundamental problem in SLICE networks is to route each traffic demand along a lightpath with continuously and consecutively available sub-carriers, which is known as the Routing and Spectrum Allocation (RSA) problem. Given its NP-Hardness, the solutions to the RSA problem can be classified into two categories: optimal solutions using link-based, path-based, and channel-based Integer Linear Programming (ILP) models, which require extensive computational time; and sub-optimal heuristic and meta-heuristic algorithms, which have no guarantee on the solution quality. In this work, inspired by a channel-based ILP model, we propose a novel primal-dual framework to address the RSA problem, which can obtain a near-optimal solution with guaranteed per-instance closeness to the optimal solution.

1. Introduction

The recent decade has witnessed a tremendous growth of Internet traffic, which is expected to continue climbing for the foreseeable future. Recently, Spectrum-sliced Elastic Optical Path (SLICE) networks [1,2,3] have come to light as a promising solution to resolve this traffic explosion. In traditional Wavelength Division Multiplexing (WDM) networks, spectrum resources are coarsely managed at the level of wavelengths (that are separated from each other with fixed guard-bands). In SLICE networks, a traffic demand is accommodated with a group of consecutive sub-carriers, and neighboring sub-carriers can overlap partially in the spectrum domain [1,2,3]. As a single sub-carrier has a finer granular than a wavelength and consecutive sub-carriers can overlap without the fixed guard-bands, SLICE networks can better deliver both sub-wavelength and super-wavelength traffic accommodation [2]. In addition, SLICE networks have other inherent advantages such as enhanced signal quality and extended reachability [2].

It remains a challenging but fundamental problem to efficiently allocate lightpaths in SLICE networks to accommodate traffic demands, which is known as the Routing and Spectrum Allocation (RSA) problem [4]. The challenges originate from three major constraints. First, one has to allocate continuously free sub-carriers along a path to fulfill the demand. Second, the chosen free sub-carriers should as well be consecutive ones in the spectrum domain (i.e., the sub-carrier consecutiveness constraint). Third, the guard-bands between lightpaths are not predetermined and have to be decided at run time. The RSA problem is shown to be NP-Hard [4], and the solutions to the RSA problem can be classified into two categories. First, optimal solutions provided by link-based, path-based, and channel-based Integer Linear Programming (ILP) models. We note that channel-based models inherently capture the second and third constraints above explicitly, thus leading to a compact formulation. Second, sub-optimal heuristic algorithms and meta-heuristic algorithms. Overall, ILP-based approaches demand prohibitive computational time, which limits their applicability in reality; and methods that are heuristic in nature lack guaranteed closeness to the optimal solution.

We seek to avoid the above limitations of existing approaches, and propose a novel primal-dual solution framework to the RSA problem in this paper. Inspired by a compact channel-based ILP solution, we explore the relaxation and decomposition of the model based on the dual variables or Lagrange multipliers of complex coupling constraints, which leads to an upper bound (UB) of the problem. The dual multipliers obtained from above are then fed into a Primal algorithm for obtaining a lower bound (LB) of the problem. Our framework employs these two processes to update the UB and LB iteratively, resulting in a near-optimal solution with a per-instance guarantee on its closeness to the optimal solution.

The rest of the paper is organized as follows. In Section 2, we present the network model, the definition, and a compact ILP model of the studied problem. In Section 3, we explore relaxation and decomposition of the ILP model, and propose an exact solution to the resulting problem. In Section 4, we present the primal-dual framework. In Section 5, we evaluate the proposed framework. In Section 6, we review related literature, and we conclude this work in Section 7.

2. Network Model, Problem Definition, and a Channel-Based ILP Model

In this section, we present the network model, problem definition and complexity, and a channel-based ILP model of the studied problem.

2.1. Network Model

A SLICE network is modeled as a graph $G(V,E,S)$: V consists of nodes of the network; E contains the set of directional fibers connecting nodes in V; and S is the group of sub-carriers on each fiber. The set of traffic demands is denoted as D = {$d_i$} ($i=1,2,3\dots ,\left|D\right|$), and $B_{d_i}$ denotes the required number of sub-carriers for demand $d_i$. Figure 1 shows an example of the SLICE network with six nodes and $S=\{0,1,2,3\}$ (i.e., $\left|S\right|=4$) for each fiber. In Figure 1, the sub-carrier usage of fiber links are only shown for those with partial sub-carriers occupied (i.e., in shadow). In addition, for this example, there is only one demand $d_1$ (from node B to node F) in the set D.

The sub-carrier consecutiveness constraint requires the allocation of a block of $B_d$ consecutive sub-carriers for a demand d. This requirement can be explicitly captured with the concept of channel [5,6]. Note that we exclude the consideration of guard-bands in this paper since which can as well be treated as part of the channel [4,5]. In Figure 1, for example, assuming that the demand size of $d_1$ is 2, one can have three channels of $c_1$, $c_2$, and $c_3$, with two sub-carriers each. Some of the channels, however, cannot be used to accommodate demands when sub-carriers within are occupied. For instance, in Figure 1, for the request $d_1$ of size 2 between B and F along the path B-C-F, only channel $c_3$ can be allocated.

Definition 1.

Channel—Achannelis a block of consecutive sub-carriers of size $B_d$ for a request d.

2.2. Problem Definition

The formal definition of the studied problem is stated below.

Definition 2.

Routing and Spectrum Allocation with Optimal Revenue (ROR)—given the demand set D, and a SLICE network $G(V,E,S)$, the ROR problem aims to achieve the maximum revenue by satisfying requests from D with available channels along the routes of requests.

Note that our general definition leaves the freedom for exact ways of defining the revenue. Some typical definitions of revenue, however, are addressed in the subsection below. We further note that the ROR problem is NP-Hard, as shown in Theorem 1.

Theorem 1.

The ROR problem is NP-Hard.

Proof of Theorem 1.

One can simply reduce a regular RSA problem [4] to the ROR problem by setting the revenue of each request to be the same. Thus the ROR problem is NP-Hard.    □

2.3. A Channel-Based Model for the ROR Problem

Next we adapt the channel-based ILP model from [5] and present it below, which adopts the following variables/notations.

$x_d$:	0 if demand d is not accommodated, 1 otherwise;
$y_{p,c}$:	1 for the chosen channel c along the chosen path p, 0 otherwise;
$p\left(d\right)$:	the path set for demand d;
$c\left(d\right)$:	the channel set for demand d;
$R_d$:	the revenue factor for accepting demand d;
${\theta }_{p,e}$:	1 if path p includes e (∈ E) as an edge, 0 otherwise;
$r_{c,s}$:	1 if channel c contains sub-carrier s, 0 otherwise.

Each demand is associated with a revenue factor $R_d$, which may reflect the incentive of accepting demand d. The resulting objective of maximizing the total revenue is expressed as in Equation (1). We discuss two typical ways of defining $R_d$. One can set $R_d=1$ for $\forall d\in D$, then revenue is reflected as the total number of accepted requests in Equation (2). Likewise, one can set $R_d=B_d\forall d\in D$, then revenue is reflected as the total volume of accommodated requests as in Equation (3).

(1)$MAX\sum _{d\in D}{x}_d\times R_d$

(2)$MAX\sum _{d\in D}{x}_d$

(3)$MAX\sum _{d\in D}{x}_d\times B_d$

There are only two groups of constraints in this compact model (and the sub-carrier consecutiveness constraint is already taken into account implicitly). The constraints of Equation (4) ensure that demand d is accepted when one and only one channel along its route is chosen (i.e., $y_{p,c}=1$). In addition, Equation (5) is employed to avoid a sub-carrier clash, which happens only when two conditions are both satisfied: first, a given sub-carrier appears in overlapping channels of multiple requests; the given sub-carrier is over a common fiber link that resides in paths of those requests.

(4)$x_d=\sum _{p\in p\left(d\right)}\sum _{c\in c\left(d\right)}{y}_{p,c}\forall d\in D$

(5)$\sum _{d\in D}\sum _{p\in p\left(d\right)}\sum _{c\in c\left(d\right)}(r_{c,s}\times {\theta }_{p,e}\times y_{p,c})\le 1\forall e\in E,s\in S$

One well-known issue with a model that is path-based in nature is the potential exponential number of path-related variables (i.e., $y_{p,c}$). Interestingly, with our proposed framework, we can obtain solutions based on the above model without this issue.

3. Resolve the Channel-Based Model: Relaxation, Decomposition and Channel-Graph-Based Algorithm

In this section, we apply relaxation, and decomposition in sequence to the channel-based model, resulting in a simplified model that can be exactly resolved by a Channel-Graph-based algorithm.

3.1. Relaxation of the Channel-Based Model

Note that the most complex constraints of the channel-based ROR model lie in Equation (5). We take the dual variables of Equation (5) (i.e., ${\lambda }_{e,s}$ (≥0)), and apply Lagrange relaxation to the constraints of Equation (5) (with the aim of simplifying the channel-based model). The revised objective is shown in Equation (6). The resulting Relaxed model consists of Equation (6) and Equation (7), and is referred to as the R model hereafter.

(6)$\begin{array}{c}\hfill MAX\sum _{d\in D}{x}_d\ast R_d+\sum _{e\in E,s\in S}{\lambda }_{e,s}-\sum _{e\in E,s\in S}({\lambda }_{e,s}\times \sum _{d\in D}\sum _{p\in p\left(d\right)}\sum _{c\in c\left(d\right)}(r_{c,s}\times {\theta }_{p,e}\times y_{p,c}))\end{array}$

(7)$x_d=\sum _{p\in p\left(d\right)}\sum _{c\in c\left(d\right)}{y}_{p,c}\forall d\in D$

It remains to address two issues to resolve the original ROR problem. First, one needs to find the optimal ${\lambda }_{e,s}$ for the R model, which essentially solves the dual problem of the R model and can be addressed with a Sub-gradient algorithm. Second, one needs to resolve the R model at any given dual variables ${\lambda }_{e,s}$, namely the R(${\lambda }_{e,s}$) model, which is further elaborated below.

3.2. Decomposition of the R(${\lambda }_{e,s}$) Model

It can be observed that, in the R(${\lambda }_{e,s}$) model, for a given demand d, constraints of Equation (7) are not coupled with that of any other demands. This observation inspires us to further decompose the R(${\lambda }_{e,s}$) model on a per-demand basis. The resulting model consists of Equation (8), and Equation (9) as the objective and constraints, respectively. Note that the term ${\sum }_{e,s}{\lambda }_{e,s}$ in the objective of Equation (6) is a constant at any fixed dual variables, thus it is excluded in Equation (8).

(8)$MAX{x}_d\ast R_d-\sum _{e\in E,s\in S}({\lambda }_{e,s}\times \sum _{p\in p\left(d\right)}\sum _{c\in c\left(d\right)}(r_{c,s}\times {\theta }_{p,e}\times y_{p,c}))$

(9)$x_d=\sum _{p\in p\left(d\right)}\sum _{c\in c\left(d\right)}{y}_{p,c}$

We refer to above Decomposed Relaxed model as the DR model. Note that after the DR model for each demand is resolved, one can combine the solutions to resolve the R(${\lambda }_{e,s}$) model.

3.3. Channel-Graph-Based Algorithm for the DR Model

Now we design a polynomial time algorithm to resolve the DR model based on the concept of Channel-Graph. A Channel-Graph is a snapshot of the network at a particular channel, thus there are at most $\left|S\right|-B_d+1$ Channel-Graphs for a demand d. An example of the Channel-Graph (CG) construction for the six-node network in Figure 1 is shown in Figure 2, Figure 3 and Figure 4. We assume that the demand $d_1$ has a size of 2, which leads to three possible channels: $c_1$, $c_2$, and $c_3$ in Figure 1, with respective Channel-Graphs shown in Figure 2, Figure 3 and Figure 4. As an example, in Figure 2 of channel $c_1$, link A-B, link B-C, and link C-F are removed from the original network due to the occupancy of sub-carriers of $c_1$ (i.e., Sub-carrier 0 or 1) on those three links.

Based on the channel-graphs, Algorithm 1 provides an exact solution for the DR model of each demand. Variable i in Line 1 is the index of all possible channels for demand d (i.e., $1\le i\le \left|S\right|-B_d+1$). Lines 4 to 7 construct the channel-graph for each channel (say c), and assign the weight of an edge e as ${\sum }_{s\in c}({\lambda }_{e,s}\times r_{c,s})$. The rational of this weight assignment is further elaborated below in the proof of Theorem 2. Lines 8 to 12 employ the Dijkstra’s algorithm for the shortest path over all channel-graphs to decide the best channel (i.e., $Ch$) and path (i.e., $Pf$). $C_d$ represents the weight of the found shortest path. As shown in Lines 14 to 17, a demand is accepted (i.e., $x_d=1$, and $y_{Pf,Ch}=1$) if $C_d\le R_d$ (i.e., non-negative revenue). As shown in Theorem 2, we claim that Algorithm 1 exactly resolves the DR model.

Theorem 2.

Algorithm 1 resolves DR model of a demand d optimally.

Proof of Theorem 2.

For a given demand d, note that the corresponding DR model only has a single constraint in Equation (9). Equation (9) essentially corresponds to a path and channel selection for demand d (i.e., $y_{p,c}$). With the constructed channel-graphs, we can separately examine the objective of the model per channel if the weight of the edges in each channel-graph is properly assigned. For a demand d, the maximization of the objective is equivalent to the minimization of the term ${\sum }_{e\in E,s\in S}({\lambda }_{e,s}\times {\sum }_{p\in p\left(d\right)}{\sum }_{c\in c\left(d\right)}(r_{c,s}\times {\theta }_{p,e}\times y_{p,c}))$. We reformulate this term as ${\sum }_{e\in E,c\in C}{\sum }_{p\in p\left(d\right)}(y_{p,c}\times {\theta }_{p,e}\times {\sum }_{s\in S}({\lambda }_{e,s}\times r_{c,s}))$. This inspires us to assign weight as ${\sum }_{s\in c}({\lambda }_{e,s}\times r_{c,s})$ for link e on the channel c, thus the minimum weight path over all channel-graphs of demand d leads to the minimization of the term ${\sum }_{e\in E,s\in S}({\lambda }_{e,s}\times {\sum }_{p\in p\left(d\right)}{\sum }_{c\in c\left(d\right)}(r_{c,s}\times {\theta }_{p,e}\times y_{p,c}))$, and further the optimization of the DR model.    □

Algorithm 1 Channel-Graph-Based Algorithm for DR Model of Demand d.

1:. $i\leftarrow 1$ 2:. $C_d\leftarrow R_d$ 3:. for $i\le \left|S\right|-s_d+1$ do 4:.     Make a copy of the original network, namely $C{G}_{i,d}$ 5:.     for all Link $e\in C{G}_{i,d}$ do 6:.         Remove e from $C{G}_{i,d}$ if Channel i is not available on e, otherwise: 7:.         $w_e\leftarrow {\sum }_{s\in i}({\lambda }_{e,s}\times r_{i,s})$ 8:.     end for 9:.     Obtain the minimum weight path on $C{G}_{i,d}$ using Dijkstra’s algorithm (assume that the found path p has weight W) 10:.     if $W\le C_d$ then 11:.         $C_d\leftarrow W$ 12:.         $Ch\leftarrow i$ 13:.         $Pf\leftarrow p$ 14:.     end if 15:.     $i\leftarrow i+1$ 16:. end for 17:. $x_d\leftarrow 0$ 18:. if $C_d\le R_d$ then 19:.     $x_d\leftarrow 1$ 20:.     $y_{Pf,Ch}\leftarrow 1$ 21:. end if

With the exact solution of DR model, we can resolve the R(${\lambda }_{e,s}$) by combining the results from each demand $d\in D$. It now remains to find the optimal dual variables ${\lambda }_{e,s}$ to resolve the original problem, which is elaborated in the next section.

4. The Primal-Dual Framework for the ROR Problem

We present the solution framework in this section, focusing on two major components of this framework: the Primal algorithm, and a Sub-gradient algorithm. Note that the Primal algorithm addresses the ROR problem directly (i.e., the primal problem), while the Sub-gradient algorithm finds the optimal ${\lambda }_{e,s}$ (which essentially resolves the dual problem of ROR). We hence refer to the framework as the primal-dual framework.

4.1. The Primal Algorithm

Note that the solution obtained by Algorithm 1 may not be feasible for the ROR problem as Equation (5) is relaxed. We need an algorithm that directly solves the ROR problem for a definite feasible solution, which is presented in Algorithm 2, namely the Primal algorithm. As the solution found by Algorithm 2 is feasible, the associated revenue is adopted as a lower bound (LB) for that of the ROR problem.

Algorithm 2 The Primal Algorithm for the ROR Problem.

1:. for all $d\in D$ do 2:.     for all $e\in C{G}_{c,d},c\in c\left(d\right)$ do 3:.         $w_{e,c}^d\leftarrow {\sum }_{s\in c}{\lambda }_{e,s}$ 4:.     end for 5:. end for 6:. Arrange demands in D in descending order based on the value of $x_d\ast R_d-C_d$ 7:. for all $d\in D$ do 8:.     W ← ∞ 9:.     for all Channel $c_i\in c\left(d\right)$ do 10:.         Obtain the minimum-weight path on the current channel-graph of d using Dijkstra’s algorithm (assume that the found path p has weight $wc$) 11:.         if $wc$ ≤ W then 12:.            W ← $wc$ 13:.            $P_d$* ← p 14:.            $C{h}_d$* ← $c_i$ 15:.         end if 16:.     end for 17:.     for all Channel-Graph $C{G}_{c^{\prime },d^{\prime }},c^{\prime }\cap c\ne \varnothing$ do 18:.         for all $e\in P_d$* do 19:.            Remove e from $C{G}_{c^{\prime },d^{\prime }}$ 20:.         end for 21:.     end for 22:. end for

Following the descending order of $x_d\ast R_d-C_d$ (i.e., the revenue found by Algorithm 1), Algorithm 2 sequentially accepts demands in D. In Lines 5–7, we assign the weight ($w_{e,c}^d$) of edge e on $C{G}_{c,d}$ as ${\sum }_{s\in c}{\lambda }_{e,s}$. Note that this weight reflects the extent that the corresponding constraints are violated after the relaxation. The minimum-weight path found (i.e., path $P_d$* along channel $C{h}_d$*) in Lines 7 to 12 attempts to achieve the least violation of the original constraints. As Channel $C{h}_d$* is planned to be reserved along path $P_d$*, we remove corresponding edges from other channel-graphs to prevent the related sub-carriers from being used again in Lines 13 to 15.

4.2. The Sub-Gradient Algorithm for the R Model

The Sub-gradient Algorithm is an iterative process that is guaranteed to converge to the best dual variable or Lagrange multiplier (i.e., ${\lambda }_{e,s}$) [7]. The objective of the found solution with a Sub-gradient Algorithm is an upper bound (UB) of that of the original problem [7]. The Sub-gradient Algorithm is reflected in Algorithm 3 (excluding Line 11). In Algorithm 3, i is the iteration number. The dual variable in Iteration i is denoted as ${\lambda }_{e,s}^i$, and hence the R model of the current iteration is denoted as $R\left({\lambda }_{e,s}^i\right)$. In Lines 8 to 10, Algorithm 1 resolves the decomposed $R\left({\lambda }_{e,s}^i\right)$ model (i.e., the DR model), and updates UB and/or LB (if better UB and/or LB are found). The dual variables are updated in each iteration by taking the violations of the relaxed constraints of the original model into account in Lines 12 to 13, where $\alpha$ is a standard scalar [7].

4.3. Summary of the Overall Framework

The Primal-Dual framework presented in Algorithm 3 iteratively maintains an upper bound and lower bound for the original ROR problem from the Sub-gradient algorithm and the Primal algorithm, respectively. Line 11 applies the Primal algorithm to obtain a feasible solution to the ROR problem in each iteration. There are two possible stopping criteria (i.e., Line 16): the maximum iteration number (i.e., $MAX$) and the value of $\Delta$= $\frac{UB-LB}{LB}$. The second criteria is reached when the upper bound and lower bound are close enough (e.g., $\Delta \le \epsilon$, and $\epsilon$ is a small number that can be customized as an input).

It is worth noting that the proposed framework bears a few important merits. First, our framework stays away from directly solving any time-prohibitive ILP models (even though it is derived from a channel-based model). Second, our framework avoids exploring the exponential number of potential paths. DR model is exactly solved with the simple Dijkstra’s algorithm following a proper link weight assignment (Line 8 of Algorithm 1). Likewise, in the Sub-gradient algorithm, only selected paths in the current iteration (i.e., for which $y_{p,c}$ = 1) contribute to the updating of the dual variables in Line 13 of Algorithm 3. Third, with either stopping criteria in Line 16 of Algorithm 3, the obtained solution has a guaranteed closeness to the optimal solution as shown in Theorem 3 below, where $OPT$ is the revenue from the optimal solution.

Theorem 3.

The framework can obtain a feasible solution with a revenue no less than $(1-\Delta )$*$OPT$.

Proof of Theorem 3.

First note that the solution found by the Primal algorithm or the one with LB updated in Line 10 of Algorithm 3 is always feasible. We have $LB\le RV\le OPT\le UB$, where $RV$ denotes the obtained revenue from the framework. As $OPT-UB+LB\le UB-UB+LB=LB$, we have $RV\ge LB\ge OPT-UB+LB=(1-\frac{UB-LB}{OPT})\ast OPT\ge (1-\frac{UB-LB}{LB})\ast OPT=(1-\Delta )\ast OPT$.    □

Algorithm 3 The Primal-Dual Framework for the ROR Problem.

1:. for all $e\in E$, $s\in S$ do 2:.     ${\lambda }_{e,s}^0\leftarrow 0$ 3:. end for 4:. $UB\leftarrow$ Revenue of accommodating all demands 5:. $LB\leftarrow 0$ 6:. $\alpha \leftarrow 1$ 7:. $i\leftarrow 0$ 8:. repeat 9:.     Apply Algorithm 1 to resolve the decomposed $R\left({\lambda }_{e,s}^i\right)$ model, and update the UB if needed 10:.     if The solution in the above step is feasible then 11:.         Update the LB if needed 12:.     end if 13:.     Apply the Primal algorithm, and update the LB if needed 14:.     for all $e\in E$, $s\in S$ do 15:.         ${\lambda }_{e,s}^{i+1}\leftarrow {[{\lambda }_{e,s}^i+\alpha \ast ({\sum }_{d\in D}{\sum }_{p\in p\left(d\right)}{\sum }_{c\in c\left(d\right)}{r}_{c,s}\times {\theta }_{p,e}\times y_{p,c}-1)]}^{+}$ 16:.     end for 17:.     $i\leftarrow i+1$ 18:.     $\alpha \leftarrow \frac{1}{i}$ 19:. until $i==MAXor\Delta$ is small enough

5. Performance Evaluation

In this section, the proposed framework is evaluated and analyzed. The NSFNET network is used as the network topology with $\left|S\right|$ = 40. The demand set D consists of a demand from each node-pair, with $B_d$ as an integer number uniformly distributed within $[1,x]$ (x is an integer number) for each demand d. For each experiment, average performance based on hundreds of instances (at the same setting) are collected and reported below. Furthermore, the proposed framework does not require an ILP solver such as ILOG CPLEX [8] as a polynomial-time algorithm (i.e., Algorithm 1) is proposed to address the DR model.

5.1. The Impact of the Stopping Criteria

As we discuss above, we have two stopping criteria: the maximum iteration number, and the closeness of the current solution (i.e., $\Delta$). We investigate the impact of these two criteria to uncover some insights on the choice of these two parameters.

We first investigate the impact of parameter of $\Delta$ on computational time in Figure 5 where the X-axis is the $\Delta$ value and the Y-axis is the computational time needed to achieve the respective $\Delta$. Clearly, with the increase of $\Delta$, the required computational time decreases as the larger $\Delta$s correspond to lower revenues. Approximately, to achieve $\Delta =0.05$, 700 iterations are consumed while less than 100 iterations are needed to achieve $\Delta =0.1$. The best $\Delta$ achieved in Figure 5 is $0.05$. One question arises is: Do more iterations lead to a further decrease in Δ?. We investigate this problem below.

Figure 6 plots the trend of computational time (i.e., the Y-axis) as the number of iterations (i.e., the X-axis) grows. Evidently, it reveals an almost linear increase of time with the growth of the number of iterations. This observation is to be expected. Note that, however, an increasing number of iterations does not lead to definite performance improvement based on the labeled $\Delta$ value in Figure 6. When the number of iterations is at the lower end, its increase leads to an evident increase in performance (i.e., the decrease in $\Delta$). When the number of iterations reaches a larger value (e.g., 700 in Figure 5), a further increase does not lead to revenue increase as ${\lambda }_{e,s}$ already converges to the optimal value. Based on the above discussion, in reality, depending on time-sensitivity and the solution quality requirement, one can trade-off along these two dimensions.

5.2. Performance in Revenue

We further study the performance of the proposed framework by examining the achieved revenue, and the SPSR (Shortest Path with Maximum Spectrum Reuse) and BLSA (Balanced Load Spectrum Assignment) algorithms (which are commonly adopted as benchmark algorithms in the literature) from [4] are used for comparison. The major difference between SPSR and BLSA lies in the routing: the shortest-path routing is used in the former; and load-balanced routing is used in the latter. The maximum iteration number (i.e., $MAX$) is set to be 700. The performance comparison is shown in Figure 7 where the X-axis of Figure 7 corresponds to x or the maximum value for demands between node-pairs and the Y-axis shows the revenue by setting $R_d=B_d$ for each demand d. In Figure 7, PD(n) represents the proposed Primal-Dual framework when setting $\Delta \le n$. UB refers to the upper bound that is obtained by the Sub-gradient algorithm (while LB matches the respective revenue from PD(n) solution). From Figure 7, with a light traffic load (e.g., $x\le 8$), all schemes demonstrate a similar performance as all requests are accommodated with all schemes. With the increase of the load, the proposed schemes achieve higher revenue than that of BLSA and SPSR. The performance difference even enlarges with the further increase of traffic load. The PD($0.05$) scheme apparently outperforms the PD($0.1$) scheme in most cases at the expense of a possible longer computational time.

6. Related Work

The Routing and Spectrum Allocation (RSA) problem shares similarity with the Routing and Wavelength Assignment (RWA) problem in WDM networks. The latter has been extensively studied in the literature (see, e.g., [9,10,11,12,13,14]), however, the solutions to RWA problem cannot be applied to RSA due to two major reasons. First, in RWA, a traffic demand is typically accommodated as a lightpath at the granular of individual wavelength. In SLICE networks, however, one may have to allocate a group of consecutive sub-carriers [2]. Second, RWA problem is guard-band-oblivious since guard-bands are predetermined and fixed in WDM networks. In the RSA problem, however, guard-bands between lightpaths have to be determined at run time [4].

After being introduced by a group of pioneering work [2,4,15,16], there have been extensive studies on the RSA problem [17]. We classify those solutions based on two different criteria. According to the nature of the adopted methodologies, those solutions can be broadly classified into two categories. First, optimal ILP-based approaches that provide exact solutions to the RSA problem, which can be further divided into three types: link-based models [4], path-based models [15], and channel-based models [5]. ILP models typically are limited to small size RSA problem instances due to the prohibitive computational time. Second, non-optimal solutions to the RSA problem, which include heuristic algorithm and meta-heuristic algorithms. Non-optimal solutions typically divide the routing and spectrum allocation process into two sub-problems (i.e., routing sub-problem, and spectrum allocation sub-problem) and solves the two problems in sequence [4,18]. Meta-heuristic approaches employ varieties of methodologies including tabu-search [19], differential evolution [20,21], ant colony optimization [21], bee colony optimization [22], Genetic algorithm [18], as well as AI/ML (Artificial Intelligence/Machine Learning) techniques (e.g., [23,24], and see [25] for a comprehensive discussion). The main drawback of heuristic/meta-heuristic algorithms is the lack of a guaranteed closeness to the optimal solution. These limitations of existing approaches partially motivated this work.

Alternatively, we can classify the RSA problem based on the employed physical constraints, resulting in many variations of the RSA problem. When the modulation level of the signal is introduced to RSA, the resulting problem is referred to as the RMLSA (Routing, Modulation Level, and Spectrum Allocation) problem [26,27,28]. The study in [29] in fact further incorporated the consideration of signal regeneration in RMLSA (as well as survivability). When physical layer security (e.g., eavesdropping) is taken into account, the resulting RSA problem adds in security-awareness [30]. The RSA problem can also consider the physical layer power spectral density [31]. With the emerging of Space Division Multiplexing (SDM) technologies, the RSA variant further addresses the assignment of fiber cores, which is referred to as the Routing, Modulation, Spectrum, and Core Allocation (RMSCA) problem in this context [32,33,34]. RSA can also be studied under other assumptions including: RSA for multi-cast traffic [35], RSA allowing delayed decision [36], and RSA with the presence of multiple fibers [37], to name a few. It is worth mentioning that the RSA problem overlaps with the Optical Virtual Network Embedding (OVNE) problem in SLICE networks [6,38,39,40]. The OVNE problem contains an instance of the RSA problem in the link mapping process where bandwidth requests between virtual nodes are instantiated as lightpaths of SLICE networks. The framework presented in this work mainly addresses the baseline RSA problem, and extensions to the above variations of the RSA problem will be explored in the future.

7. Conclusions

It is important to study the fundamental Routing and Spectrum (RSA) problem in Spectrum-sliced Elastic Optical Path (SLICE) networks. Despite extensive literature on this topic, the search continues for a solution that avoids the extensive computational time in Integer Linear Programming (ILP) models and addresses the lack of guarantee on solution quality in heuristic/meta-heuristic solutions for RSA. In this paper, we propose a novel primal-dual solution framework to the RSA problem. Our framework iteratively maintains an upper bound (UB) (based on the relaxation and decomposition of a channel-based model) and a lower bound (from a proposed Primal algorithm) for the problem, resulting a near-optimal solution with a per-instance guarantee on its closeness to the optimal solution. In our future work, we plan to extend the proposed framework to take other important aspects of a SLICE network design such as the modulation level/signal reachability, survivablity, and network virtualization into account.

Author Contributions

The article was conceived and structured by Y.W., C.L., Q.H. and M.J. Y.W., C.L. and M.J. conceived the model and performed analysis. J.F. performed simulations. Y.W., C.L. and Q.H. wrote the paper. All authors have read and agreed to the published version of the manuscript.

Funding

This research received no external funding.

Conflicts of Interest

The authors declare no conflict of interest.

Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Figures

Figure 1. An Example of a Six-Node Network.

Figure 2. Channel Graph for [Forumla omitted. See PDF.].

Figure 3. Channel Graph for [Forumla omitted. See PDF.].

Figure 4. Channel Graph for [Forumla omitted. See PDF.].

Figure 5. [Forumla omitted. See PDF.] and Computational Time.

Figure 6. Iteration Number and Computational Time.

Figure 7. Revenue Comparisons.

References

1. Jinno, M.; Takara, H.; Kozichi, B. Dynamic Optical Mesh Networks: Drivers, challenges, and solutions for the future. Proceedings of the ECOC; Vienna, Austria, 20–24 September 2009; pp. 1-5.

2. Jinno, M.; Takara, H.; Kozichi, B.; Tsukishima, Y.; Sone, Y. Spectrum-Efficient and Scalable Elastic Optical Path Network: Architecture, Benefits, and Enabling Technologies. IEEE Commun. Mag.; 2009; 47, pp. 66-73. [DOI: https://dx.doi.org/10.1109/MCOM.2009.5307468]

3. Jinno, M.; Kozichi, B.; Takara, H.; Watanabe, A.; Sone, Y.; Tanaka, T.; Hirano, A. Distance-Adaptive Spectrum Resource Allocation in Spectrum-sliced Elastic Optical Path Network. IEEE Commun. Mag.; 2010; 48, pp. 138-145. [DOI: https://dx.doi.org/10.1109/MCOM.2010.5534599]

4. Wang, Y.; Cao, X.; Pan, Y. A study of the routing and spectrum allocation in the SLICE network. Proceedings of the IEEE INFOCOM; Shanghai, China, 10–15 April 2011; pp. 1-9.

5. Velasco, L.; Klinkowski, M.; Ruiz, M.; Comellas, J. Modeling the Routing and Spectrum Allocation Problem for Flexgrid Optical Networks. Photonic Netw. Commun.; 2012; 24, pp. 177-186. [DOI: https://dx.doi.org/10.1007/s11107-012-0378-7]

6. Wang, Y.; Hu, Q. A Path Growing Approach to Optical Virtual Network Embedding in SLICE Networks. J. Light. Technol.; 2021; 39, pp. 2253-2262. [DOI: https://dx.doi.org/10.1109/JLT.2020.3047713]

7. Ahuja, R.K.; Magnanti, T.L.; Orlin, J.B. Network Flows: Theory, Algorithms, and Applications; Prentice Hall: Hoboken, NJ, USA, 1993.

8. ILOG CPLEX. Available online: https://www.ibm.com/analytics/cplex-optimizer/ (accessed on 4 September 2021).

9. Chlamtac, I.; Ganz, A.; Karmi, G. Lightpath communications: An approach to high bandwidth optical WAN’s. IEEE Trans. Commun.; 1992; 40, pp. 1171-1182. [DOI: https://dx.doi.org/10.1109/26.153361]

10. Subramaniam, S.; Azizoglu, M.; Somani, A.K. All-optical networks with sparse wavelength conversion. IEEE/ACM Trans. Netw.; 1996; 4, pp. 544-547. [DOI: https://dx.doi.org/10.1109/90.532864]

11. Baroni, S.; Bayvel, P. Wavelength Requirements in Arbitrarily Connected Wavelength-Routed Optical Networks. IEEE J. Light. Technol.; 1997; 15, pp. 242-251. [DOI: https://dx.doi.org/10.1109/50.554330]

12. Baroni, S. Routing and Wavelength Allocation in WDM Optical Networks. Ph.D. Thesis; Department of Electrionic and Electrical Engineering, University College London: London, UK, 1998.

13. Gerstel, O.; Sasaki, G.; Kutten, S.; Ramaswami, R. Worst-case Analysis of Dynamic Wavelength Allocation in Optical Networks. IEEE Trans. Netw.; 1999; 7, pp. 833-845. [DOI: https://dx.doi.org/10.1109/90.811449]

14. Zang, H.; Jue, J.; Mukherjee, B. A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks. Opt. Netw. Mag.; 2000; 1, pp. 47-60.

15. Christodoulopoulos, K.; Tomkos, I.; Varvarigos, E. Routing and Spectrum Allocation in OFDM-based Optical Networks with Elastic Bandwidth Allocation. Proceedings of the IEEE GLOBECOM; Miami, FL, USA, 6–10 December 2010; pp. 1-6.

16. Klinkowski, M.; Walkowiak, K. Routing and Spectrum Assignment in Spectrum Sliced Elastic Optical Path Network. IEEE Commun. Lett.; 2011; 15, pp. 884-886. [DOI: https://dx.doi.org/10.1109/LCOMM.2011.060811.110281]

17. Chatterjee, B.C.; Sarma, N.; Oki, E. Routing and Spectrum Allocation in Elastic Optical Networks: A Tutorial. IEEE Commun. Surv. Tutor.; 2015; 17, pp. 1776-1800. [DOI: https://dx.doi.org/10.1109/COMST.2015.2431731]

18. Dinarte, H.A.; Correia, B.V.; Chaves, D.A.; Almeida, R.C. Routing and spectrum assignment: A metaheuristic for hybrid ordering selection in elastic optical networks. Comput. Netw.; 2021; 197, 108287. [DOI: https://dx.doi.org/10.1016/j.comnet.2021.108287]

19. Goścień, R.; Klinkowski, M.; Walkowiak, K. A tabu search algorithm for routing and spectrum allocation in elastic optical networks. Proceedings of the 2014 16th International Conference on Transparent Optical Networks (ICTON); Graz, Austria, 6–10 July 2014; pp. 1-4.

20. Lezama, F.; Castañón, G.; Sarmiento, A.M.; Martins, I.B. Routing and spectrum allocation in flexgrid optical networks using differential evolution optimization. Proceedings of the 2014 16th International Conference on Transparent Optical Networks (ICTON); Graz, Austria, 6–10 July 2014; pp. 1-4.

21. Lezama, F.; Martínez-Herrera, A.F.; Castañón, G.; Del-Valle-Soto, C.; Sarmiento, A.M.; de Cote, E.M. Solving routing and spectrum allocation problems in flexgrid optical networks using pre-computing strategies. Photonic Netw. Commun.; 2021; 41, pp. 17-35. [DOI: https://dx.doi.org/10.1007/s11107-020-00918-4]

22. Marković, G.Z. Routing and spectrum allocation in elastic optical networks using bee colony optimization. Photonic Netw. Commun.; 2017; 34, pp. 356-374. [DOI: https://dx.doi.org/10.1007/s11107-017-0706-z]

23. Chen, X.; Li, B.; Proietti, R.; Lu, H.; Zhu, Z.; Yoo, S.J.B. DeepRMSA: A Deep Reinforcement Learning Framework for Routing, Modulation and Spectrum Assignment in Elastic Optical Networks. J. Light. Technol.; 2019; 37, pp. 4155-4163. [DOI: https://dx.doi.org/10.1109/JLT.2019.2923615]

24. Salani, M.; Rottondi, C.; Tornatore, M. Routing and Spectrum Assignment Integrating Machine-Learning-Based QoT Estimation in Elastic Optical Networks. Proceedings of the IEEE INFOCOM 2019—IEEE Conference on Computer Communications; Paris, France, 29 April–2 May 2019; pp. 1738-1746. [DOI: https://dx.doi.org/10.1109/INFOCOM.2019.8737413]

25. Gu, R.; Yang, Z.; Ji, Y. Machine learning for intelligent optical networks: A comprehensive survey. J. Netw. Comput. Appl.; 2020; 157, 102576. [DOI: https://dx.doi.org/10.1016/j.jnca.2020.102576]

26. Christodoulopoulos, K.; Tomkos, I.; Varvarigos, E.A. Elastic Bandwidth Allocation in Flexible OFDM-Based Optical Networks. J. Light. Technol.; 2011; 29, pp. 1354-1366. [DOI: https://dx.doi.org/10.1109/JLT.2011.2125777]

27. Garrido, C.; Leiva, A.; Beghelli, A. A RMLSA algorithm with modulation format conversion at intermediate nodes. Proceedings of the 2017 19th International Conference on Transparent Optical Networks (ICTON); Girona, Spain, 2–6 July 2017; pp. 1-4.

28. Costa, L.R.; Drummond, A.C. New Distance-Adaptive Modulation Scheme for Elastic Optical Networks. IEEE Commun. Lett.; 2017; 21, pp. 282-285. [DOI: https://dx.doi.org/10.1109/LCOMM.2016.2624288]

29. Guo, H.; Li, Y.; Li, L.; Shen, G. Adaptive Modulation and Regeneration-Aware Routing and Spectrum Assignment in SBPP-Based Elastic Optical Networks. IEEE Photonics J.; 2017; 9, pp. 1-15. [DOI: https://dx.doi.org/10.1109/JPHOT.2017.2685418]

30. Savva, G.; Manousakis, K.; Ellinas, G. Eavesdropping-Aware Routing and Spectrum/Code Allocation in OFDM-Based EONs Using Spread Spectrum Techniques. J. Opt. Commun. Netw.; 2019; 11, pp. 409-421. [DOI: https://dx.doi.org/10.1364/JOCN.11.000409]

31. Yan, L.; Agrell, E.; Dharmaweera, M.N.; Wymeersch, H. Joint Assignment of Power, Routing, and Spectrum in Static Flexible-Grid Networks. J. Light. Technol.; 2017; 35, pp. 1766-1774. [DOI: https://dx.doi.org/10.1109/JLT.2017.2657698]

32. Oliveira, H.M.N.S.; da Fonseca, N.L.S. Multipath Routing, Spectrum and Core Allocation in Protected SDM Elastic Optical Networks. Proceedings of the 2019 IEEE Global Communications Conference (GLOBECOM); Waikoloa, HI, USA, 9–13 December 2019; pp. 1-6. [DOI: https://dx.doi.org/10.1109/GLOBECOM38437.2019.9013523]

33. Oliveira, H.M.N.S.; da Fonseca, N.L.S. P-cycle Protected Multipath Routing, Spectrum and Core Allocation in SDM Elastic Optical Networks. Proceedings of the ICC 2019—2019 IEEE International Conference on Communications (ICC); Shanghai, China, 20–24 May 2019; pp. 1-6. [DOI: https://dx.doi.org/10.1109/ICC.2019.8762098]

34. Rodrigues, E.; Rosário, D.; Cerqueira, E.; Oliveira, H. Routing, Modulation, Spectrum and Core Allocation Based on Mapping Scheme. Proceedings of the 2020 IEEE Symposium on Computers and Communications (ISCC); Rennes, France, 8–10 July 2020; pp. 1-6. [DOI: https://dx.doi.org/10.1109/ISCC50000.2020.9219625]

35. Datta Choudhury, P.; Reddy, P.R.; Chatterjee, B.C.; Oki, E.; De, T. Performance of routing and spectrum allocation approaches for multicast traffic in elastic optical networks. Opt. Fiber Technol.; 2020; 58, 102247. [DOI: https://dx.doi.org/10.1016/j.yofte.2020.102247]

36. Afsharlar, P.; Deylamsalehi, A.; Plante, J.M.; Zhao, J.; Vokkarane, V.M. Routing and spectrum assignment with delayed allocation in elastic optical networks. J. Opt. Commun. Netw.; 2017; 9, pp. B101-B111. [DOI: https://dx.doi.org/10.1364/JOCN.9.00B101]

37. Wu, J.; Subramaniam, S.; Hasegawa, H. Efficient dynamic routing and spectrum assignment for multifiber elastic optical networks. J. Opt. Commun. Netw.; 2019; 11, pp. 190-201. [DOI: https://dx.doi.org/10.1364/JOCN.11.000190]

38. Zhao, J.; Subramaniam, S.; Brandt-Pearce, M. Virtual topology mapping in elastic optical networks. Proceedings of the 2013 IEEE International Conference on Communications (ICC); Budapest, Hungary, 9–13 June 2013; pp. 3904-3908. [DOI: https://dx.doi.org/10.1109/ICC.2013.6655167]

39. Gong, L.; Zhu, Z. Virtual Optical Network Embedding (VONE) Over Elastic Optical Networks. J. Light. Technol.; 2014; 832, pp. 450-460. [DOI: https://dx.doi.org/10.1109/JLT.2013.2294389]

40. Wang, Y.; McNulty, Z.; Nguyen, H. Network Virtualization in Spectrum Sliced Elastic Optical Path Networks. IEEE/OSA J. Light. Technol.; 2017; 35, pp. 1962-1970. [DOI: https://dx.doi.org/10.1109/JLT.2017.2678462]