Abstract

Optical networks, such as wavelength-division multiplexing networks and elastic optical networks, require high reliability and efficient wavelength allocation. We propose a new physical topology optimization method that achieves both high reliability and efficient wavelength allocation. We compare the results of conventional algebraic connectivity optimization, which discusses physical topology optimization from the viewpoint of spectral graph theory, with those based on reliability optimization, which is important from the viewpoint of network operations. From the comparison analysis, it is shown that our proposed two-step degree bounded reliability-optimization model, which optimizes reliability with appropriate node degree constraints, leads to a physical topology that has high wavelength capacity without compromising reliability.

© 2021 Optical Society of America under the terms of the OSA Open Access Publishing Agreement

1. INTRODUCTION

A. Optical Networks and Topology Optimization

As the Internet population continues to grow, and as online technologies such as augmented reality (AR) and virtual reality (VR) become more widespread, the requirements for low latency, high capacity, and high reliability of optical networks will far exceed the current network performance limits. For example, assuming an online service using VR, the current VR technology requires a spatial resolution of ${2000} \times {2000}\;{\rm pixels}$ and a temporal resolution of about 100 frames per second. Assuming a data volume of 3 bytes/pixel, a transmission capacity of at least 9.6 Gbps/user is required. On the basis of these assumptions, metro and backbone networks require a transmission capacity of at least ${10^{2 - 3}}\;{\rm Tbps}$ and ${10^{0 - 1}}\;{\rm Pbps}$, respectively. Optical network technologies, such as wavelength-division multiplexing (WDM) networks and elastic optical networks (EONs) [1], are expected to achieve low latency approaching the physical limit. However, how to provide the above requirements for high-capacity communication with high reliability remains an issue.

We focus our discussion on the physical topology issue of optical network topology. As shown in Fig. 1, network performance is determined by the relations among the traffic matrix, physical topology, and routing and wavelength assignment (RWA) algorithm. Traffic is determined by user requirements and usually given as an ad hoc element. Thus, the study of optical networks can be generally divided into two categories. The first is to find an efficient algorithm given a traffic matrix and physical topology: it is called the RWA problem in WDM networks and the routing and spectrum allocation (RSA) problem in EONs [2]. The other is to find the optimal physical topology given the traffic matrix and the RWA/RSA algorithm. We focus on the latter physical topology optimization problem in optical networks. We refer to the physical topology simply as topology.

 figure: Fig. 1.

Fig. 1. Relations among the traffic matrix, physical topology, and RWA/RSA algorithm in communication networks.

Download Full Size | PPT Slide | PDF

B. Related Works on Topology Optimization

There are many variations of topologies, such as bus, star, ring, random, and mesh. These topologies have been studied in terms of reliability, efficiency of wavelength usage, and relations to existing networks. In terms of reliability, ring and mesh topologies are suitable for redundant route design and have been used in communication networks. For example, a comparison of ring and mesh topologies in terms of the spare capacity of main and redundant routes [3], and the minimum optimization of routes and spare capacity in mesh [4] have been proposed. Survivable network topology optimization has also been proposed [5,6]. Tran and Saito [5] proposed a link-addition method with which link failure probability due to earthquakes is integrated along a geographical route, and the disaster tolerance and route length (cost) are optimized in a multi-objective manner. Agrawal et al. [6] developed an earthquake-risk model based on the classification of seismic zones and proposed a method of improving the topology by node relocation using risk assessment. In terms of efficiency of wavelength usage, the impact of physical topology on EONs has been shown: total network load changes up to $\sim{70}\%$ under the same levels of requests blocked ratio when the dynamic RSA algorithm is applied to various topologies with the same number of nodes and edges [7]. In terms of existing networks, a topology construction method close to real networks has been proposed on the basis of the analysis of actual node degree and node/link-disjoint connectivity distribution [8]. Another study compared simulation results optimized for reliability with existing networks, and showed that there is room for reliability improvement in real networks without increasing capital expenditure [9]. It is challenging to discuss optimal topology quantitatively, considering relations to reliability and efficiency of wavelength usage simultaneously. Also, it is difficult to compare and analyze topologies such as ring and mesh under equal conditions since they are already separated into different topologies. Therefore, we attempt to discuss topology optimization at a more abstract level.

Graph theory is an effective means of increasing the level of abstraction and discussing topology. Waxman [10] considered the geometric distance between nodes in the random graph model, and it has been shown that random geometric graph models can be used to construct topologies similar to real optical fiber networks [8]. Recently, Matzner et al. [11] proposed a new graph generation model on the basis of the Barabasi-Albert [12] scale-free network model. In the conventional scale-free graph generation algorithm, the probability of edge existence is modeled by node degree information, and the edge is constructed on the basis of the “rich get richer” principal. However, the scale-free model does not consider physical properties in real optical fiber networks. Therefore in [11], they consider physical properties such as SNR degradation caused by signal propagation through a light path to the edge probability model, and the algorithm successfully generates high-throughput networks compared to conventional graph generation algorithms.

In the midst of this progress, optimizing both network reliability and communication capacity simultaneously remains a challenging problem. We therefore explore a different approach: we focus on spectral graph theory and global optimization using spectral indices. Spectral graph theory reduces topological problems to linear algebraic problems and enables us to handle the global characteristics of a graph more easily. A popular form in spectral graph theory is the graph Laplacian matrix $L$, which is defined as the difference between the node degree matrix $D$ and the adjacency matrix $A$: $L = D - A$. The second eigenvalue of the graph Laplacian is called algebraic connectivity [13], and it is widely studied as one of the indicators of network topology. We denote algebraic connectivity for a graph $G$ as ${a_G}(L)$ or simply ${a_G}$. In terms of optical networks, previous studies have shown that there are two important relations between ${a_G}$ and network reliability and ${a_G}$ and capacity.

The first, the relation between ${a_G}$ and reliability, is pointed out from mathematical research: it has been shown that there is a relation among ${a_G}$, vertex-connectivity ${\kappa _V}(G)$, and edge-connectivity ${\kappa _E}(G)$ of a graph $G$: ${a_G} \le {\kappa _V}(G) \le {\kappa _E}(G)$ [13]. Note that the vertex/edge-connectivity ${\kappa _{V/E}}(G) \in \aleph$ is defined as a natural number where the graph is connected even if ${\kappa _{V/E}} - 1$ vertices/edges are removed from the graph $G$. The vertex/edge-connectivity is a necessary condition of the topology for node/link-disjoint protection techniques [14], and they are considered to be important metrics in terms of network reliability design. For this reason, the optimization maximizing ${a_G}$ has been studied as one of the topology optimization problems to improve network robustness. For example, the perturbation heuristic developed by Ghosh and Boyd [15], which maximizes ${a_G}$ in terms of an edge addition problem, has been applied to free space optical (FSO) networks [16,17] and aircraft route design problems [18].

The second relation between ${a_G}$ and network capacity is pointed out from terrestrial optical fiber network research. It has been shown that the number of wavelengths ${N_\lambda}$ required to accommodate a given traffic matrix without wavelength blocking depends on the topology [19,20]. The relation between ${a_G}$ and ${N_\lambda}$ has been investigated for various topologies, and the specific relationship ${N_\lambda} \propto a_G^{- 0.8}$ has been reported [21]. In other words, the larger ${a_G}$ is, the fewer wavelengths that are required to allocate the given traffic. This suggests that topology optimization is important to improve wavelength-allocation efficiency as well as the pursuit of RWA/RSA algorithms.

C. Problem Statement and Objective of this Work

From the above, it can be considered that the maximum optimization of ${a_G}$ would be important to improve the reliability and spectrum-allocation efficiency of optical networks, such as WDM networks and EONs. On the other hand, it has also been pointed out that the relation between vertex/edge-connectivity and ${a_G}$ is not so trivial. Specifically, the relations among ${a_G}$, ${\kappa _V}$, and ${\kappa _E}$ were investigated for several network topologies such as small world, random, and scale-free networks, and it was pointed out that the relation between ${a_G}$ and vertex/edge-connectivity changes depending on the topology [22]. This suggests that a large ${a_G}$ and high network reliability are not necessary or sufficient, and there is yet no clear solution for topology optimization that achieves both high reliability and efficient wavelength allocation.

We focused on obtaining this solution. Specifically, we compared the results of the ${a_G}$-optimization with those of reliability optimization, and investigated whether the optimization maximizing ${a_G}$ is suitable from the viewpoint of network reliability. The results suggest that it is not always suitable. Therefore, we analyzed the comparison results and developed a method of optimizing both ${a_G}$ and reliability.

The structure of this paper is as follows. In Section 2, we set up the basic problem and discuss the comparison of the simulation models of the ${a_G}$-optimization and reliability-optimization methods. The simulation model of our proposed method of optimizing both ${a_G}$ and reliability is also described. In Section 3, the comparison results and discussion are presented, and the motivation for our proposed optimization method is given. In Section 4, a summary and future perspective are presented.

2. SIMULATION MODELS

A. Basic Problem Setting

We define the network structure as an undirected graph, $G({V,E})$, where $V$ and $E$ are the node set and edge set, respectively. The topology optimization method is based on the edge addition method described in a previous paper [15]. In addition to the base edge set, ${E_{{\rm base}}}$, we add $| {{E_{{\rm add}}}} | = {N_k}$ edges to construct an optimal topology. The positions of the nodes ${v_i} \in V({i = 1,\ldots ,10})$ are given in Fig. 2. The node spacing is set to be the same, and the major nodes are colored. As an initial condition, ${E_{{\rm base}}}$ is given by the minimum spanning tree connecting the major nodes. (The initial conditions can be applied to topologies other than minimum spanning trees such as rings and stars.) The minimum spanning tree is constructed from a weighted complete graph, $K(V)$. The weight of each edge, ${e_{i,j}}$, in $K(V)$ is given by the availability ${p_{i,j}} \in ({0,1}]$; ${p_{i,j}}$ is calculated as ${p_{i,j}} = 1 - {q_{i,j}}$. The unavailability ${q_{i,j}}$ is assumed to be a uniform random number and given to each edge. The average link unavailability $\bar q$ is defined as an ensemble average of ${q_{i,j}}$. For example, the label of the edge in Fig. 2 shows ${p_{i,j}}$ when $\bar q = 0.25$. The simulation parameters are ${N_k} = 8$ and $\bar q \in \{{5 \times {{10}^{- 4}},0.05,0.1,0.15,0.2,0.25} \}$. The $\bar q$ was chosen to cover a wide range of possible applications: the average unavailability per edge ranges from $\bar q \le {10^{- 3}}$ for fiber optic networks [23] to networks that have larger link unavailability.

 figure: Fig. 2.

Fig. 2. Node position and initial configuration for the basic problem. Colored nodes are primary nodes.

Download Full Size | PPT Slide | PDF

B. Two Basic Models and the TSDBR Model

First, let us define the ${a_G}$-optimization and reliability of graph $G$ [hereafter referred to as $R(G)$ or simply $R$] optimization models.

The ${a_G}$-optimization is defined as

$$\begin{split}&{\rm maximize}\quad {a_G}({L({{E_{{\rm base}}} \cup {E_{{\rm add}}}})})\\&{\rm subject}\,{\rm to}\quad | {{E_{{\rm add}}}}| = {N_k}\\&\qquad \qquad{E_{{\rm add}}} \subseteq {E_{{\rm cand}}}.\end{split}$$
The ${a_G}$-maximization of the objective function is important to improve the spectrum-allocation efficiency in optical networks such as WDM networks and EONs. From the candidate edge set, ${E_{{\rm cand}}}$, we select an edge to add to the graph. The selection of ${E_{{\rm add}}}$ from ${E_{{\rm cand}}}$ follows the perturbation heuristic [15]. Unlike an exhaustive search, which calculates ${a_G}$ for all graphs after the addition of all ${e_{i,j}} \in {E_{{\rm cand}}}$, this heuristic predicts the addition from the eigenvectors before the addition of edges. The optimization result close to an exhaustive search can then be obtained while reducing the computation time to $1/|{E_{{\rm cand}}}|$. Specifically, we choose an edge ${e_{i,j}} \in {E_{{\rm cand}}}$ that has the theoretical upper limit, $\max [{{p_{i,j}}{{({{\nu _i} - {\nu _j}})}^2}}]$. The upper limit is estimated by the increase in ${a_G}({L_w})$, which is calculated from the graph Laplacian, ${L_w}$, weighted by ${p_{i,j}}$ [18]. The $\nu$ in the upper limit is the eigenvector (Fiedler vector) corresponding to ${a_G}$.

The $R(G)$-optimization is defined as

$$\begin{split}&{{\rm maximize}\quad R(G) = {f_{{\rm BDD}}}({{q_{i,j}}})}\\&{{\rm subject}\,{\rm to}\quad | {{E_{{\rm add}}}}| = {N_k}}\\&\qquad \qquad {{E_{{\rm add}}} \subseteq {E_{{\rm cand}}}},\end{split}$$
where $R(G)$ is defined as the reliability between major nodes and calculated by the binary decision diagram (BDD) method [24,25] on the basis of the unavailability ${q_{i,j}}$ of each edge. An additional edge, ${e_{i,j}} \in {E_{{\rm add}}}$, is selected from ${E_{{\rm cand}}}$ by an exhaustive search maximizing $R({G({E_{{\rm base}}} \cup {E_{{\rm add}}}}))$.

As a modification to the $R$-optimization described above, we define the two-step degree bounded reliability (TSDBR) optimization model by adding the following conditional equations (3)–(5) to ${E_{{\rm cand}}}$ in Eq. (2):

$$\begin{split}{E_{{\rm cand}}} &= {E_{{\rm st}1}}\quad {\rm if}\;{E_{{\rm st}1}} \ne \emptyset ,\\ &= {E_{{\rm st}2}}\quad {\rm if}\; ({{E_{{\rm st}1}} = \emptyset}) \cap ({{E_{{\rm st}2}} \ne \emptyset})\\ &= \emptyset \quad {\rm else},\end{split}$$
where
$$\begin{split}E_{{\rm st}1} & = ({{I_{\max}} \cap {J_{\min}}}) \cup ({{I_{\min}} \cap {J_{\max}}}),\\{E_{{\rm st}2}} &= ({{I_{\max}} \cap {J_{\max}}} ) \backslash {E_{{\rm st}1}},\end{split}$$
and
$$\begin{split}{I_{{\min}/{\max}}} &= \{{{v_i} \in V{:}\; ({{v_i},{v_j}}) \in {E_{{\rm cand}}} \cap d ({v_i}) \lt {D_{{\min}/{\max}}}}\},\\{J_{{\min}/{\max}}} &= \{{{v_j} \in V{:}\; ({{v_i},{v_j}}) \in {E_{{\rm cand}}} \cap d ({v_j}) \lt {D_{{\min}/{\max}}}}\}.\end{split}$$
${E_{{\rm st}1}}$ and ${E_{{\rm st}2}}$ are illustrated in Fig. 3. Defining the degree of a node as $d({v_i})$, the above equations are almost equivalent to imposing the degree constraint ${D_{\min}} \le d({v_i}) \le {D_{\max}}$. Equations (3)–(5) play an important role in increasing ${a_G}$ while optimizing the reliability. The results of solving only Eq. (2) and Eqs. (2)–(5) are respectively shown in Sections 3.A and 3.B and are compared and discussed at the end of Section 3.B.
 figure: Fig. 3.

Fig. 3. Schematic view of the two-step degree bound conditions.

Download Full Size | PPT Slide | PDF

The TSDBR expressed in Eqs. (2)–(5) can be implemented as in Algorithm 1. The input is the initial graph $G$, complete graph $K$, and fixed parameters. The output is the graph after edges have been added. The problem is solved until the number of added edges reaches the target (line 1) or there are no more candidate edges (line 12). The candidate edges are obtained at each step from the difference between the edges of the initial or updated (line 11) graph and complete graph (line 2). Lines 3–6 correspond to Eqs. (3)–(6), and the exclusion of lines 3–6 corresponds to solving Eq. (2), which is discussed in Section 3.A as an exhaustive search for $R$.

In terms of computational complexity, the algorithm is combinational, and the overall computational cost is approximately the product of $\left({\begin{array}{* {20}{c}}{| {{E_{{\rm cand}}}} |}\\k\end{array}}\right)$ and the computational cost of line 10. The reliability calculation for line 10 is NP-complete [26], which is computationally difficult. For scalability, it is important to apply appropriate ${E_{{\rm cand}}}$ refinement to lines 3–6, parallel computation to line 8, and faster algorithms for reliability computation to line 10. The BDD algorithm is considered an efficient algorithm among the exact solution algorithms for network reliability computation [25].

Tables Icon

Algorithm 1. TSDBR Optimization

3. RESULTS AND DISCUSSION

In Section 3.A, we compare the optimization results on the basis of the ${a_G}$-optimization equation [Eq. (1)] and $R$-optimization equation [Eq. (2)], and discuss the trade-off between capacity and reliability. In Section 3.B, we compare the TSDBR equation [Eqs. (2) + (3)–(5)] with the ${a_G}$-optimization equation [Eqs. (1) + (3)–(5)] to improve the problem discussed in Section 3.A. From the comparison results, we present important findings for constructing a reliable and wavelength-capacity-efficient optical network topology.

A. Comparison of ${a_G}$- and $R$-Optimization

Figures 4(a) and 4(b) respectively show the ${a_G}$ and $R$ optimal graphs after adding ${N_k}$ edges for $\bar q = 0.25$. (Results for $\bar q = 5 \times {10^{- 4}}$ and 0.25 are not shown but are similar.) Figures 5(a) and 5(b) show the response of ${a_G}$ to edge addition for $\bar q = 5 \times {10^{- 4}}$ and 0.25, respectively. The difference between the ${a_G}$-optimization and $R$-optimization results is indicated with shaded lines; compared with the ${a_G}$-optimization result, ${a_G}$ in the case of $R$-optimization is less than 1/3 regardless of $\bar q$.

 figure: Fig. 4.

Fig. 4. Graphs $G({E,V})$ optimized for (a) ${a_G}$ and (b) $R$ for $\bar q = 0.25$ without node degree constraints.

Download Full Size | PPT Slide | PDF

 figure: Fig. 5.

Fig. 5. Relation between number of edges added and ${a_G}$ for (a) $\bar q = 5 \times {10^{- 4}}$ and (b) $\bar q = 0.25$ without node degree constraints.

Download Full Size | PPT Slide | PDF

Figures 6(a) and 6(b) respectively show the response of $R$ to edge addition for $\bar q = 5 \times {10^{- 4}}$ and 0.25. For $\bar q = 5 \times {10^{- 4}}$, there seems to be no difference in $R$ (left axis) for $k \ge 2$, but the failure probability of the whole network $1 - R$ (right axis) differs by more than one order of magnitude. The failure probability decreases monotonically regardless of $\bar q$, and the absolute value of the difference in reliability is larger when $\bar q$ is large.

 figure: Fig. 6.

Fig. 6. (a) Relation between number of edges added and $R$ for (a) $\bar q = 5 \times {10^{- 4}}$ and (b) $\bar q = 0.25$ without node degree constraints.

Download Full Size | PPT Slide | PDF

To summarize the comparison results in Figs. 5 and 6, there is a trade-off between ${a_G}$-optimization and $R$-optimization, i.e., trade-off between total capacity and reliability. In ${a_G}$-optimization, the absolute value of the difference in reliability is as large as ${10^{- 2}}$ for large $\bar q$. In $R$-optimization, the magnitude of ${a_G}$ (wavelength accommodation efficiency) decreases to less than 1/3 that in ${a_G}$-optimization regardless of $\bar q$. In considering how to improve this unbalanced optimization, we return to the basic policy choice: ${a_G}$-optimization or $R$-optimization. Since the topology is deeply related to the backbone network application that bundles multi-user information, as mentioned in Section 1.A, and disaster tolerance, as mentioned in Section 1.B, we choose $R$-optimization. Thus, we consider how to increase ${a_G}$ in $R$-optimization.

Looking at the results with the above in mind, there was a clear difference in the degree distribution of the nodes. Figures 7(a) and 7(b) show the degree distributions of ${a_G}$-optimization and $R$-optimization after the addition of the edge for $\bar q = 5 \times {10^{- 4}}$ and 0.25, respectively. In ${a_G}$-optimization, the distribution of node degree is concentrated in the 3–4 range, while in $R$-optimization, the node degree widely distributes in the 1–6 range. This tendency does not depend on $\bar q$. From [8], the node degrees of the existing networks are distributed in the 2–7 range, and the average of minimum and maximum node degrees are 2.18 and 4.14, respectively. Compared to existing networks, the minimum node degree is smaller in $R$-optimization, and the node degree distribution is more concentrated in ${a_G}$-optimization.

 figure: Fig. 7.

Fig. 7. Distribution of node degree, $d(V)$, in the cases of (a) $\bar q = 5 \times {10^{- 4}}$ and (b) $\bar q = 0.25$ without node degree constraints.

Download Full Size | PPT Slide | PDF

B. Comparison of ${a_G}$- and TSDBR-Optimization

From the results presented in Section 3.A, we argue that the node degree constraint in $R$-optimization is effective in improving the problem. Therefore, we compare the TSDBR-optimization model in Eqs. (2)–(5) with the ${a_G}$-optimization model in Eqs. (1) + (3)–(5).

 figure: Fig. 8.

Fig. 8. Graphs $G({E,V})$ optimized for (a) ${a_G}$ and (b) $R$ by TSDBR for $\bar q = 0.25$ with node degree constraints $({{D_{\min}},{D_{\max}}}) = ({2,4})$.

Download Full Size | PPT Slide | PDF

 figure: Fig. 9.

Fig. 9. Relation between number of edges added and ${a_G}$ for (a) $\bar q = 5 \times {10^{- 4}}$ and (b) $\bar q = 0.25$; $({{D_{\min}},{D_{\max}}}) = ({2,4})$.

Download Full Size | PPT Slide | PDF

 figure: Fig. 10.

Fig. 10. Relation between number of edges added and $R$ for (a) $\bar q = 5 \times {10^{- 4}}$ and (b) $\bar q = 0.25$; $({{D_{\min}},{D_{\max}}}) = ({2,4})$.

Download Full Size | PPT Slide | PDF

Figures 8(a) and 8(b) respectively show the ${a_G}$ optimal graph and $R$ optimal graph after adding ${N_k}$ edges for $\bar q = 0.25$ and $({{D_{\min}},{D_{\max}}}) = (2,4)$. Figures 9(a) and 9(b) respectively show the response of ${a_G}$ to edge addition for $\bar q = 5 \times {10^{- 4}}$ and 0.25 with $({{D_{\min}},{D_{\max}}}) = ({2,4})$. From the comparison between Fig. 5 without node degree constraints and Fig. 9 with degree constraints, we can see that ${a_G}$ is improved in $R$-optimization regardless of $\bar q$. Figures 10(a) and 10(b) show the response of $R$ to edge addition for $\bar q = 5 \times {10^{- 4}}$ and 0.25, respectively. The failure probability $1 - R$ tends to saturate in $R$-optimization, but in the range of $k \le 4$, reliability seems to be independent of degree constraints.

To discuss the relation between ${a_G}$-optimization and $R$-optimization and their dependence on the node degree constraint more comprehensively, we define the following ${l_2}$ norm (Euclidean distance):

$$\| {{l_2}} \|: = {\left[{\mathop \sum \limits_{k = 1}^{N_k} {{\big({{l_{{a_G}\,{\rm optimize},k}} - {l_{R\,{\rm optimize},k}}} \big)}^2}} \right]^{1/2}}.$$
The above expresses the similarity between the ${a_G}$-optimization and $R$-optimization results of the measurement $l$. The similarities ${\| {a_G} \|_2}$ and ${\| R \|_2}$ are discussed. For convenience, the parameter space $\boldsymbol{S}$ is defined by $\boldsymbol{S} = ({{D_{\min}},{D_{\max}},\bar q})$. For example, ${\| {a_G} \|_2}$ for $\boldsymbol{S} = (2,4,5 \,\times {{10}^{- 4}})$ corresponds to the shaded area in Fig. 9(a).

Figures 11 and 12 respectively show (a) ${\| {a_G} \|_2}$ and (b) ${\| R \|_2}$ in $\boldsymbol{S}({{D_{\min}} = 1})$ and $\boldsymbol{S}({{D_{\min}} = 2})$ spaces. From these results, we obtain two important points. First, by comparing (a) and (b) in Figs. 11 and 12, adding the node degree constraint (along the horizontal axis) does not change the distance of reliability but only the distance of ${a_G}$. (It should be mentioned from the comparison between Figs. 6 and 9 that the failure probability in TSDBR slightly increases. However, the increase is small, which makes little difference for ${\| R \|_2}$.) Second, from Figs. 11(a) and 12(a), we can see that there is a threshold of maximum node degree constraint where the distance of ${a_G}$ decreases. Figure 12(c), the line graph of Fig. 12(a), shows that the distance of ${a_G}$ shrinks (similarity increases) regardless of $\bar q$ for ${D_{\max}} \lt 5$. In other words, if we impose an appropriate maximum node degree constraint, we can effectively improve ${a_G}$ (wavelength-allocation efficiency) without losing reliability. Since the above tendency is independent of $\bar q$, it would be effective from the networks with small $\bar q$ such as optical fiber communication systems to those with larger $\bar q$.

 figure: Fig. 11.

Fig. 11. (a) ${\| {a_G} \|_2}$ and (b) ${\| R \|_2}$ for $\boldsymbol{S}({{D_{\min}} = 1})$.

Download Full Size | PPT Slide | PDF

 figure: Fig. 12.

Fig. 12. (a) ${\| {a_G} \|_2}$ and (b) ${\| R \|_2}$ for $\boldsymbol{S}({{D_{\min}} = 2})$. (c) Line graph of (a).

Download Full Size | PPT Slide | PDF

 figure: Fig. 13.

Fig. 13. Improvement of ${a_G}$ for $({{D_{\min}},{D_{\max}}}) = ({2,4})$ and $\bar q = \{{5 \times {{10}^{- 4}},0.05,0.1,0.15,0.2,0.25} \}$.

Download Full Size | PPT Slide | PDF

Finally, we discuss the improvement of wavelength-allocation efficiency in $R$-optimization. Figure 13 shows the response of the improvement rate of ${a_G}$ to the edge addition. The improvement rate is defined as

$${\rm Improvement} ({a_G}) := 100 \times \left({\frac{{{a_{G,{\rm TSDBR}}}}}{{{a_{G,{{{\rm exhaustive}\,{\rm search}\,{\rm for}\,R}}}}}} - 1} \right).$$
Regardless of $\bar q$, the improvement is approximately 200%. This can be translated into an improvement in wavelength-allocation efficiency based on the result of a previous study, ${N_\lambda} \propto a_G^{- 0.8}$ [21]. For ${a_G}$ ${\rm improvement} = {200}\%$, ${N_\lambda}$ becomes ${3^{- 0.8}} \simeq 0.42$ times. In other words, comparing the results before and after the improvement of topology optimization for $R$, the number of wavelengths required for the given traffic is 58% less.

4. SUMMARY

A. Summary of this Study

We focus on the physical topology optimization problem for highly reliable and efficient wavelength-assignable optical networks. In previous studies, the relations among algebraic connectivity (${a_G}$), network reliability, and wavelength-allocation efficiency were investigated, and the maximum optimization of ${a_G}$ was considered for high reliability and high capacity. It has also been pointed out that the relation between algebraic connectivity and reliability is not necessary or sufficient. Therefore, we quantitatively evaluated both ${a_G}$-optimization and $R$-optimization. The results showed that neither optimization provides both high reliability and high wavelength-allocation efficiency, but rather a trade-off between them. From the comparative analysis of the results, we proposed a modified $R$-optimization method, TSDBR, which takes algebraic connectivity improvement into account by focusing on the node degree distribution, and the improvement does not depend on $\bar q$. The most important feature of TSDBR is that it links two different metrics: capacity and reliability. Therefore, TSDBR is expected to contribute to increasing the capacity of networks where reliability is required.

B. Applications and Future Perspective

The findings of this study and the proposed method can be applied to two possible areas in optical networks. The first is a design technique for the route planning of optical fiber infrastructure, and the second is a dynamic link control technique for FSO networks. In both cases, it is expected to increase the capacity of the network while increasing its reliability.

The first is particularly useful for operators to make decisions on where to build (or delete) new optical fiber routes in the current network. By modeling the accumulated knowledge of failures and disaster risks and attributing them to ${q_{i,j}}$, it allows us to propose a systematic method of improving the physical topology with excellent reliability and wavelength-allocation efficiency. From the viewpoint of survivability, for example, ${q_{i,j}}$ would be calculated on the basis of the findings in previous studies [5,6].

The second is the application to FSO networks such as ground [27,28] and low orbit satellite constellations [17,29]. This technology would be applied to the construction of dynamically changing acquisition and tracking links. Taking real-time evaluation of ${q_{i,j}}$ for shielding and atmospheric fluctuations into account, it is expected to improve the reliability of the acquisition and tracking links compared with conventional ${a_G}$-optimization.

There are two major issues to be addressed. The first is the relation to real networks. The TSDBR model can apply various topologies, such as ring and star, as initial conditions. When discussing the problem of improving a network that already has a large node degree, however, no candidate edges can be found. In this case, it would be necessary to consider the edge-deletion problem in the model. It is also necessary to clarify which nodes are assumed to be major nodes in the real network.

The second is the effect of geographic distance. The larger the distance between nodes, the larger the cost of fiber installation and signal impairment due to linear and nonlinear effects [3032], but these effects are not yet considered with this model. As a more comprehensive issue, it is important to verify topology optimization together with RSA research. For example, an RSA algorithm that is less susceptible to topology changes has recently been proposed [33], and we can discuss the effectiveness of topology optimization using such an algorithm. As the geometric distance increases, it is also necessary to consider the relation with signal regeneration. Signal regeneration increases design freedom, and gives the relation between topology and power consumption [34]. It also introduces the relation to cross-layer design such as traffic grooming, and the grooming strategy changes the equipment requirements [35], which in turn generate feedback on reliability. A systematic framework for the relation among physical topology, reliability, efficiency of wavelength usage, and further design policy would give us a more comprehensive and quantitative way to construct a better physical topology.

Acknowledgment

The authors thank colleagues at NTT Network Innovation Laboratories for useful discussion.

REFERENCES

1. V. Lopez and L. Velasco, Elastic Optical Networks (Springer, 2016).

2. B. Chatterjee, N. Sarma, and E. Oki, “Routing and spectrum allocation in elastic optical networks: a tutorial,” IEEE Commun. Surv. Tutorials17, 1776–1800 (2015). [CrossRef]  

3. J. M. Simmons, Optical Network Design and Planning (Springer, 2014).

4. W. D. Grover, Mesh-Based Survivable Networks: Options and Strategies for Optical, MPLS, SONET and ATM Networking (Prentice Hall PTR, 2003).

5. P. Tran and H. Saito, “Enhancing physical network robustness against earthquake disasters with additional links,” J. Lightwave Technol.34, 5226–5238 (2016). [CrossRef]  

6. A. Agrawal, V. Bhatia, and S. Prakash, “Network and risk modeling for disaster survivability analysis of backbone optical communication networks,” J. Lightwave Technol.37, 2352–2362 (2019). [CrossRef]  

7. R. Tessinari, M. Paiva, M. Monteiro, M. Segatto, A. Garcia, G. Kanellos, R. Nejabati, and D. Simeonidou, “On the impact of the physical topology on the optical network performance,” in IEEE British and Irish Conference on Optics and Photonics (2018).

8. C. Pavan, R. Morais, J. Rocha, and A. Pinto, “Generating realistic optical transport network topologies,” J. Opt. Commun. Netw.2, 80–90 (2010). [CrossRef]  

9. C. Pavan, L. Lima, M. Paiva, and M. Segatto, “How reliable are the real-world optical transport networks?” J. Opt. Commun. Netw.7, 578–585 (2015). [CrossRef]  

10. B. Waxman, “Routing of multipoint connections,” IEEE J. Sel. Areas Commun.6, 1617–1622 (1988). [CrossRef]  

11. R. Matzner, D. Semrau, R. Luo, G. Zervas, and P. Bayvel, “Making intelligent topology design choices: understanding structural and physical property performance implications in optical networks,” J. Opt. Commun. Netw.13, D53–D67 (2021). [CrossRef]  

12. A.-L. Barabasi and R. Albert, “Emergence of scaling in random networks,” Science286, 509–512 (1999). [CrossRef]  

13. M. Fiedler, “Algebraic connectivity of graphs,” Czech. Math. J.23, 298–305 (1973). [CrossRef]  

14. R. Bhandari, “Optimal physical diversity algorithms and survivable networks,” in Proceedings of the 2nd IEEE Symposium on Computer and Communications (1997), pp. 433–441.

15. A. Ghosh and S. Boyd, “Growing well-connected graphs,” in Proceedings of the 45th IEEE Conference on Decision & Control (2006), pp. 6605–6611.

16. I. Son and S. Mao, “Design and optimization of a tired wireless access network,” in Proceedings of IEEE INFOCOM (2010).

17. Y. Zheng, S. Zhao, Y. Liu, Y. Li, Q. Tan, and N. Xin, “Weighted algebraic connectivity maximization for optical satellite networks,” IEEE Access5, 6885–6893 (2017). [CrossRef]  

18. P. Wei and D. Sun, “Weighted algebraic connectivity: an application to airport transportation network,” IFAC Proc.44, 13864–13869 (2011). [CrossRef]  

19. S. Baroni and P. Bayvel, “Wavelength requirements in arbitrarily connected wavelength-routed optical networks,” J. Lightwave Technol.15, 242–251 (1997). [CrossRef]  

20. C. Fenger, E. Limal, U. Gliese, and C. Mahon, “Statistical study of the correlation between topology and wavelength usage in optical networks with and without conversion,” in Networking, Vol. 1815 of Lecture Notes in Computer Science (2000), pp. 168–175.

21. B. Chatelain, M. Belanger, C. Tremblay, F. Ganon, and D. Plant, “Topological wavelength usage estimation in transparent wide area networks,” J. Opt. Commun. Netw.1, 196–203 (2009). [CrossRef]  

22. A. Jamakovic and S. Uhlig, “On the relationship between the algebraic connectivity and graph’s robustness to node and link failures,” in Next Generation Internet Networks, 3rd EuroNGI Conference (2007), pp. 96–102.

23. R. L. Freeman, Telecommunication System Engineering, 4th ed. (Wiley, 2015).

24. S. Kuo, S. Lu, and F. Yeh, “Determining terminal-pair reliability based on edge expansion diagrams using OBDD,” IEEE Trans. Reliab.48, 234–246 (1999). [CrossRef]  

25. S. Kuo, F. Min, and H. Lin, “Efficient and exact reliability evaluation for networks with imperfect vertices,” IEEE Trans. Reliab.56, 288–300 (2007). [CrossRef]  

26. B. Bollig and I. Wegener, “Improving the variable ordering of OBDDs is NP-complete,” IEEE Trans. Comput.45, 993–1002 (1996). [CrossRef]  

27. C. Davis, I. Smolyaninov, and S. Milner, “Flexible optical wireless links and networks,” IEEE Commun. Mag.41(3), 51–57 (2003). [CrossRef]  

28. T. Shang, Y. Yang, G. Ren, B. Hu, T. Ding, and W. Chen, “Topology control algorithm and dynamic management scheme for mobile FSO networks,” J. Opt. Commun. Netw.7, 906–917 (2015). [CrossRef]  

29. V. W. S. Chan, “Optical satellite networks,” J. Lightwave Technol.21, 2811–2827 (2003). [CrossRef]  

30. B. Ramamurthy, D. Datta, H. Feng, J. Heritage, and B. Mukherjee, “Impact of transmission impairments on the teletraffic performance of wavelength-routed optical networks,” J. Lightwave Technol.17, 1713–1723 (1999). [CrossRef]  

31. C. Saradhi and S. Subramaniam, “Physical layer impairment aware routing (PLIAR) In WDM optical networks: issues and challenges,” IEEE Commun. Surv. Tutorials11, 109–130 (2009). [CrossRef]  

32. P. Poggiolini, G. Bosco, A. Carena, V. Curri, Y. Jiang, and F. Forghieri, “The GN-model of fiber non-linear propagation and its applications,” J. Lightwave Technol.32, 694–721 (2014). [CrossRef]  

33. R. Vincent, D. Ives, and S. Savory, “Scalable capacity estimation for nonlinear elastic all-optical core networks,” J. Lightwave Technol.37, 5380–5391 (2019). [CrossRef]  

34. F. Musumeci, M. Tornatore, and A. Pattavina, “A power consumption analysis for IP-over-WDM core network architectures,” J. Opt. Commun. Netw.4, 108–117 (2012). [CrossRef]  

35. S. Zhang, C. Martel, and B. Mukherjee, “Dynamic traffic grooming in elastic optical networks,” IEEE J. Sel. Areas Commun.31, 4–12 (2013). [CrossRef]  

jocn-14-3-16-i001 Katsuaki Higashimori received the B.S. (2009), M.S. (2011), and Ph.D. (2015) degrees from the University of Tokyo. In 2020, he joined Nippon Telegraph and Telephone (NTT) Corporation Network Innovation Laboratories. His specialty is in plasma physics and turbulence (-2015), free-space optical communication (2015-2020) and optical fiber communication networks (2020-).

jocn-14-3-16-i002 Fumikazu Inuzuka received the B.E. and M.E. degrees in applied physics from the Tokyo University of Agriculture and Technology, Tokyo, Japan, in 2002 and 2004, respectively. In 2004, he joined Nippon Telegraph and Telephone (NTT) Corporation, Kanagawa, Japan, where he is engaged in research on high-speed photonic transport and processing systems and photonic networking and management systems. He is a member of the Institute of Electronics, Information, and Communication Engineers (IEICE) of Japan.

jocn-14-3-16-i003 Takuya Ohara [M] is a senior research engineer, supervisor, in the Transport Innovation Laboratory, NTT Network Innovation Laboratories. He received his B.E. and M.E. degrees in electronic engineering from the University of Tokyo in 1998 and 2000, respectively. He joined NTT Network Innovation Laboratories in 2000. His research interests are optical fiber communication, in particular, optical networking, optical transport network (OTN) evolution, and high-speed and large-capacity optical transmission systems. He is involved in OTN standardization activities and has been active in ITU-T SG15 since 2006. He was a visiting researcher at AT&T Labs Research, Middletown, New Jersey, from 2007 to 2008, where he was involved in research on an optical path tracing technique.

References

  • View by:

  1. V. Lopez and L. Velasco, Elastic Optical Networks (Springer, 2016).
  2. B. Chatterjee, N. Sarma, and E. Oki, “Routing and spectrum allocation in elastic optical networks: a tutorial,” IEEE Commun. Surv. Tutorials 17, 1776–1800 (2015).
    [Crossref]
  3. J. M. Simmons, Optical Network Design and Planning (Springer, 2014).
  4. W. D. Grover, Mesh-Based Survivable Networks: Options and Strategies for Optical, MPLS, SONET and ATM Networking (Prentice Hall PTR, 2003).
  5. P. Tran and H. Saito, “Enhancing physical network robustness against earthquake disasters with additional links,” J. Lightwave Technol. 34, 5226–5238 (2016).
    [Crossref]
  6. A. Agrawal, V. Bhatia, and S. Prakash, “Network and risk modeling for disaster survivability analysis of backbone optical communication networks,” J. Lightwave Technol. 37, 2352–2362 (2019).
    [Crossref]
  7. R. Tessinari, M. Paiva, M. Monteiro, M. Segatto, A. Garcia, G. Kanellos, R. Nejabati, and D. Simeonidou, “On the impact of the physical topology on the optical network performance,” in IEEE British and Irish Conference on Optics and Photonics (2018).
  8. C. Pavan, R. Morais, J. Rocha, and A. Pinto, “Generating realistic optical transport network topologies,” J. Opt. Commun. Netw. 2, 80–90 (2010).
    [Crossref]
  9. C. Pavan, L. Lima, M. Paiva, and M. Segatto, “How reliable are the real-world optical transport networks?” J. Opt. Commun. Netw. 7, 578–585 (2015).
    [Crossref]
  10. B. Waxman, “Routing of multipoint connections,” IEEE J. Sel. Areas Commun. 6, 1617–1622 (1988).
    [Crossref]
  11. R. Matzner, D. Semrau, R. Luo, G. Zervas, and P. Bayvel, “Making intelligent topology design choices: understanding structural and physical property performance implications in optical networks,” J. Opt. Commun. Netw. 13, D53–D67 (2021).
    [Crossref]
  12. A.-L. Barabasi and R. Albert, “Emergence of scaling in random networks,” Science 286, 509–512 (1999).
    [Crossref]
  13. M. Fiedler, “Algebraic connectivity of graphs,” Czech. Math. J. 23, 298–305 (1973).
    [Crossref]
  14. R. Bhandari, “Optimal physical diversity algorithms and survivable networks,” in Proceedings of the 2nd IEEE Symposium on Computer and Communications (1997), pp. 433–441.
  15. A. Ghosh and S. Boyd, “Growing well-connected graphs,” in Proceedings of the 45th IEEE Conference on Decision & Control (2006), pp. 6605–6611.
  16. I. Son and S. Mao, “Design and optimization of a tired wireless access network,” in Proceedings of IEEE INFOCOM (2010).
  17. Y. Zheng, S. Zhao, Y. Liu, Y. Li, Q. Tan, and N. Xin, “Weighted algebraic connectivity maximization for optical satellite networks,” IEEE Access 5, 6885–6893 (2017).
    [Crossref]
  18. P. Wei and D. Sun, “Weighted algebraic connectivity: an application to airport transportation network,” IFAC Proc. 44, 13864–13869 (2011).
    [Crossref]
  19. S. Baroni and P. Bayvel, “Wavelength requirements in arbitrarily connected wavelength-routed optical networks,” J. Lightwave Technol. 15, 242–251 (1997).
    [Crossref]
  20. C. Fenger, E. Limal, U. Gliese, and C. Mahon, “Statistical study of the correlation between topology and wavelength usage in optical networks with and without conversion,” in Networking, Vol. 1815 of Lecture Notes in Computer Science (2000), pp. 168–175.
  21. B. Chatelain, M. Belanger, C. Tremblay, F. Ganon, and D. Plant, “Topological wavelength usage estimation in transparent wide area networks,” J. Opt. Commun. Netw. 1, 196–203 (2009).
    [Crossref]
  22. A. Jamakovic and S. Uhlig, “On the relationship between the algebraic connectivity and graph’s robustness to node and link failures,” in Next Generation Internet Networks, 3rd EuroNGI Conference (2007), pp. 96–102.
  23. R. L. Freeman, Telecommunication System Engineering, 4th ed. (Wiley, 2015).
  24. S. Kuo, S. Lu, and F. Yeh, “Determining terminal-pair reliability based on edge expansion diagrams using OBDD,” IEEE Trans. Reliab. 48, 234–246 (1999).
    [Crossref]
  25. S. Kuo, F. Min, and H. Lin, “Efficient and exact reliability evaluation for networks with imperfect vertices,” IEEE Trans. Reliab. 56, 288–300 (2007).
    [Crossref]
  26. B. Bollig and I. Wegener, “Improving the variable ordering of OBDDs is NP-complete,” IEEE Trans. Comput. 45, 993–1002 (1996).
    [Crossref]
  27. C. Davis, I. Smolyaninov, and S. Milner, “Flexible optical wireless links and networks,” IEEE Commun. Mag. 41(3), 51–57 (2003).
    [Crossref]
  28. T. Shang, Y. Yang, G. Ren, B. Hu, T. Ding, and W. Chen, “Topology control algorithm and dynamic management scheme for mobile FSO networks,” J. Opt. Commun. Netw. 7, 906–917 (2015).
    [Crossref]
  29. V. W. S. Chan, “Optical satellite networks,” J. Lightwave Technol. 21, 2811–2827 (2003).
    [Crossref]
  30. B. Ramamurthy, D. Datta, H. Feng, J. Heritage, and B. Mukherjee, “Impact of transmission impairments on the teletraffic performance of wavelength-routed optical networks,” J. Lightwave Technol. 17, 1713–1723 (1999).
    [Crossref]
  31. C. Saradhi and S. Subramaniam, “Physical layer impairment aware routing (PLIAR) In WDM optical networks: issues and challenges,” IEEE Commun. Surv. Tutorials 11, 109–130 (2009).
    [Crossref]
  32. P. Poggiolini, G. Bosco, A. Carena, V. Curri, Y. Jiang, and F. Forghieri, “The GN-model of fiber non-linear propagation and its applications,” J. Lightwave Technol. 32, 694–721 (2014).
    [Crossref]
  33. R. Vincent, D. Ives, and S. Savory, “Scalable capacity estimation for nonlinear elastic all-optical core networks,” J. Lightwave Technol. 37, 5380–5391 (2019).
    [Crossref]
  34. F. Musumeci, M. Tornatore, and A. Pattavina, “A power consumption analysis for IP-over-WDM core network architectures,” J. Opt. Commun. Netw. 4, 108–117 (2012).
    [Crossref]
  35. S. Zhang, C. Martel, and B. Mukherjee, “Dynamic traffic grooming in elastic optical networks,” IEEE J. Sel. Areas Commun. 31, 4–12 (2013).
    [Crossref]

2021 (1)

2019 (2)

2017 (1)

Y. Zheng, S. Zhao, Y. Liu, Y. Li, Q. Tan, and N. Xin, “Weighted algebraic connectivity maximization for optical satellite networks,” IEEE Access 5, 6885–6893 (2017).
[Crossref]

2016 (1)

2015 (3)

2014 (1)

2013 (1)

S. Zhang, C. Martel, and B. Mukherjee, “Dynamic traffic grooming in elastic optical networks,” IEEE J. Sel. Areas Commun. 31, 4–12 (2013).
[Crossref]

2012 (1)

2011 (1)

P. Wei and D. Sun, “Weighted algebraic connectivity: an application to airport transportation network,” IFAC Proc. 44, 13864–13869 (2011).
[Crossref]

2010 (1)

2009 (2)

B. Chatelain, M. Belanger, C. Tremblay, F. Ganon, and D. Plant, “Topological wavelength usage estimation in transparent wide area networks,” J. Opt. Commun. Netw. 1, 196–203 (2009).
[Crossref]

C. Saradhi and S. Subramaniam, “Physical layer impairment aware routing (PLIAR) In WDM optical networks: issues and challenges,” IEEE Commun. Surv. Tutorials 11, 109–130 (2009).
[Crossref]

2007 (1)

S. Kuo, F. Min, and H. Lin, “Efficient and exact reliability evaluation for networks with imperfect vertices,” IEEE Trans. Reliab. 56, 288–300 (2007).
[Crossref]

2003 (2)

V. W. S. Chan, “Optical satellite networks,” J. Lightwave Technol. 21, 2811–2827 (2003).
[Crossref]

C. Davis, I. Smolyaninov, and S. Milner, “Flexible optical wireless links and networks,” IEEE Commun. Mag. 41(3), 51–57 (2003).
[Crossref]

1999 (3)

B. Ramamurthy, D. Datta, H. Feng, J. Heritage, and B. Mukherjee, “Impact of transmission impairments on the teletraffic performance of wavelength-routed optical networks,” J. Lightwave Technol. 17, 1713–1723 (1999).
[Crossref]

S. Kuo, S. Lu, and F. Yeh, “Determining terminal-pair reliability based on edge expansion diagrams using OBDD,” IEEE Trans. Reliab. 48, 234–246 (1999).
[Crossref]

A.-L. Barabasi and R. Albert, “Emergence of scaling in random networks,” Science 286, 509–512 (1999).
[Crossref]

1997 (1)

S. Baroni and P. Bayvel, “Wavelength requirements in arbitrarily connected wavelength-routed optical networks,” J. Lightwave Technol. 15, 242–251 (1997).
[Crossref]

1996 (1)

B. Bollig and I. Wegener, “Improving the variable ordering of OBDDs is NP-complete,” IEEE Trans. Comput. 45, 993–1002 (1996).
[Crossref]

1988 (1)

B. Waxman, “Routing of multipoint connections,” IEEE J. Sel. Areas Commun. 6, 1617–1622 (1988).
[Crossref]

1973 (1)

M. Fiedler, “Algebraic connectivity of graphs,” Czech. Math. J. 23, 298–305 (1973).
[Crossref]

Agrawal, A.

Albert, R.

A.-L. Barabasi and R. Albert, “Emergence of scaling in random networks,” Science 286, 509–512 (1999).
[Crossref]

Barabasi, A.-L.

A.-L. Barabasi and R. Albert, “Emergence of scaling in random networks,” Science 286, 509–512 (1999).
[Crossref]

Baroni, S.

S. Baroni and P. Bayvel, “Wavelength requirements in arbitrarily connected wavelength-routed optical networks,” J. Lightwave Technol. 15, 242–251 (1997).
[Crossref]

Bayvel, P.

Belanger, M.

Bhandari, R.

R. Bhandari, “Optimal physical diversity algorithms and survivable networks,” in Proceedings of the 2nd IEEE Symposium on Computer and Communications (1997), pp. 433–441.

Bhatia, V.

Bollig, B.

B. Bollig and I. Wegener, “Improving the variable ordering of OBDDs is NP-complete,” IEEE Trans. Comput. 45, 993–1002 (1996).
[Crossref]

Bosco, G.

Boyd, S.

A. Ghosh and S. Boyd, “Growing well-connected graphs,” in Proceedings of the 45th IEEE Conference on Decision & Control (2006), pp. 6605–6611.

Carena, A.

Chan, V. W. S.

Chatelain, B.

Chatterjee, B.

B. Chatterjee, N. Sarma, and E. Oki, “Routing and spectrum allocation in elastic optical networks: a tutorial,” IEEE Commun. Surv. Tutorials 17, 1776–1800 (2015).
[Crossref]

Chen, W.

Curri, V.

Datta, D.

Davis, C.

C. Davis, I. Smolyaninov, and S. Milner, “Flexible optical wireless links and networks,” IEEE Commun. Mag. 41(3), 51–57 (2003).
[Crossref]

Ding, T.

Feng, H.

Fenger, C.

C. Fenger, E. Limal, U. Gliese, and C. Mahon, “Statistical study of the correlation between topology and wavelength usage in optical networks with and without conversion,” in Networking, Vol. 1815 of Lecture Notes in Computer Science (2000), pp. 168–175.

Fiedler, M.

M. Fiedler, “Algebraic connectivity of graphs,” Czech. Math. J. 23, 298–305 (1973).
[Crossref]

Forghieri, F.

Freeman, R. L.

R. L. Freeman, Telecommunication System Engineering, 4th ed. (Wiley, 2015).

Ganon, F.

Garcia, A.

R. Tessinari, M. Paiva, M. Monteiro, M. Segatto, A. Garcia, G. Kanellos, R. Nejabati, and D. Simeonidou, “On the impact of the physical topology on the optical network performance,” in IEEE British and Irish Conference on Optics and Photonics (2018).

Ghosh, A.

A. Ghosh and S. Boyd, “Growing well-connected graphs,” in Proceedings of the 45th IEEE Conference on Decision & Control (2006), pp. 6605–6611.

Gliese, U.

C. Fenger, E. Limal, U. Gliese, and C. Mahon, “Statistical study of the correlation between topology and wavelength usage in optical networks with and without conversion,” in Networking, Vol. 1815 of Lecture Notes in Computer Science (2000), pp. 168–175.

Grover, W. D.

W. D. Grover, Mesh-Based Survivable Networks: Options and Strategies for Optical, MPLS, SONET and ATM Networking (Prentice Hall PTR, 2003).

Heritage, J.

Hu, B.

Ives, D.

Jamakovic, A.

A. Jamakovic and S. Uhlig, “On the relationship between the algebraic connectivity and graph’s robustness to node and link failures,” in Next Generation Internet Networks, 3rd EuroNGI Conference (2007), pp. 96–102.

Jiang, Y.

Kanellos, G.

R. Tessinari, M. Paiva, M. Monteiro, M. Segatto, A. Garcia, G. Kanellos, R. Nejabati, and D. Simeonidou, “On the impact of the physical topology on the optical network performance,” in IEEE British and Irish Conference on Optics and Photonics (2018).

Kuo, S.

S. Kuo, F. Min, and H. Lin, “Efficient and exact reliability evaluation for networks with imperfect vertices,” IEEE Trans. Reliab. 56, 288–300 (2007).
[Crossref]

S. Kuo, S. Lu, and F. Yeh, “Determining terminal-pair reliability based on edge expansion diagrams using OBDD,” IEEE Trans. Reliab. 48, 234–246 (1999).
[Crossref]

Li, Y.

Y. Zheng, S. Zhao, Y. Liu, Y. Li, Q. Tan, and N. Xin, “Weighted algebraic connectivity maximization for optical satellite networks,” IEEE Access 5, 6885–6893 (2017).
[Crossref]

Lima, L.

Limal, E.

C. Fenger, E. Limal, U. Gliese, and C. Mahon, “Statistical study of the correlation between topology and wavelength usage in optical networks with and without conversion,” in Networking, Vol. 1815 of Lecture Notes in Computer Science (2000), pp. 168–175.

Lin, H.

S. Kuo, F. Min, and H. Lin, “Efficient and exact reliability evaluation for networks with imperfect vertices,” IEEE Trans. Reliab. 56, 288–300 (2007).
[Crossref]

Liu, Y.

Y. Zheng, S. Zhao, Y. Liu, Y. Li, Q. Tan, and N. Xin, “Weighted algebraic connectivity maximization for optical satellite networks,” IEEE Access 5, 6885–6893 (2017).
[Crossref]

Lopez, V.

V. Lopez and L. Velasco, Elastic Optical Networks (Springer, 2016).

Lu, S.

S. Kuo, S. Lu, and F. Yeh, “Determining terminal-pair reliability based on edge expansion diagrams using OBDD,” IEEE Trans. Reliab. 48, 234–246 (1999).
[Crossref]

Luo, R.

Mahon, C.

C. Fenger, E. Limal, U. Gliese, and C. Mahon, “Statistical study of the correlation between topology and wavelength usage in optical networks with and without conversion,” in Networking, Vol. 1815 of Lecture Notes in Computer Science (2000), pp. 168–175.

Mao, S.

I. Son and S. Mao, “Design and optimization of a tired wireless access network,” in Proceedings of IEEE INFOCOM (2010).

Martel, C.

S. Zhang, C. Martel, and B. Mukherjee, “Dynamic traffic grooming in elastic optical networks,” IEEE J. Sel. Areas Commun. 31, 4–12 (2013).
[Crossref]

Matzner, R.

Milner, S.

C. Davis, I. Smolyaninov, and S. Milner, “Flexible optical wireless links and networks,” IEEE Commun. Mag. 41(3), 51–57 (2003).
[Crossref]

Min, F.

S. Kuo, F. Min, and H. Lin, “Efficient and exact reliability evaluation for networks with imperfect vertices,” IEEE Trans. Reliab. 56, 288–300 (2007).
[Crossref]

Monteiro, M.

R. Tessinari, M. Paiva, M. Monteiro, M. Segatto, A. Garcia, G. Kanellos, R. Nejabati, and D. Simeonidou, “On the impact of the physical topology on the optical network performance,” in IEEE British and Irish Conference on Optics and Photonics (2018).

Morais, R.

Mukherjee, B.

Musumeci, F.

Nejabati, R.

R. Tessinari, M. Paiva, M. Monteiro, M. Segatto, A. Garcia, G. Kanellos, R. Nejabati, and D. Simeonidou, “On the impact of the physical topology on the optical network performance,” in IEEE British and Irish Conference on Optics and Photonics (2018).

Oki, E.

B. Chatterjee, N. Sarma, and E. Oki, “Routing and spectrum allocation in elastic optical networks: a tutorial,” IEEE Commun. Surv. Tutorials 17, 1776–1800 (2015).
[Crossref]

Paiva, M.

C. Pavan, L. Lima, M. Paiva, and M. Segatto, “How reliable are the real-world optical transport networks?” J. Opt. Commun. Netw. 7, 578–585 (2015).
[Crossref]

R. Tessinari, M. Paiva, M. Monteiro, M. Segatto, A. Garcia, G. Kanellos, R. Nejabati, and D. Simeonidou, “On the impact of the physical topology on the optical network performance,” in IEEE British and Irish Conference on Optics and Photonics (2018).

Pattavina, A.

Pavan, C.

Pinto, A.

Plant, D.

Poggiolini, P.

Prakash, S.

Ramamurthy, B.

Ren, G.

Rocha, J.

Saito, H.

Saradhi, C.

C. Saradhi and S. Subramaniam, “Physical layer impairment aware routing (PLIAR) In WDM optical networks: issues and challenges,” IEEE Commun. Surv. Tutorials 11, 109–130 (2009).
[Crossref]

Sarma, N.

B. Chatterjee, N. Sarma, and E. Oki, “Routing and spectrum allocation in elastic optical networks: a tutorial,” IEEE Commun. Surv. Tutorials 17, 1776–1800 (2015).
[Crossref]

Savory, S.

Segatto, M.

C. Pavan, L. Lima, M. Paiva, and M. Segatto, “How reliable are the real-world optical transport networks?” J. Opt. Commun. Netw. 7, 578–585 (2015).
[Crossref]

R. Tessinari, M. Paiva, M. Monteiro, M. Segatto, A. Garcia, G. Kanellos, R. Nejabati, and D. Simeonidou, “On the impact of the physical topology on the optical network performance,” in IEEE British and Irish Conference on Optics and Photonics (2018).

Semrau, D.

Shang, T.

Simeonidou, D.

R. Tessinari, M. Paiva, M. Monteiro, M. Segatto, A. Garcia, G. Kanellos, R. Nejabati, and D. Simeonidou, “On the impact of the physical topology on the optical network performance,” in IEEE British and Irish Conference on Optics and Photonics (2018).

Simmons, J. M.

J. M. Simmons, Optical Network Design and Planning (Springer, 2014).

Smolyaninov, I.

C. Davis, I. Smolyaninov, and S. Milner, “Flexible optical wireless links and networks,” IEEE Commun. Mag. 41(3), 51–57 (2003).
[Crossref]

Son, I.

I. Son and S. Mao, “Design and optimization of a tired wireless access network,” in Proceedings of IEEE INFOCOM (2010).

Subramaniam, S.

C. Saradhi and S. Subramaniam, “Physical layer impairment aware routing (PLIAR) In WDM optical networks: issues and challenges,” IEEE Commun. Surv. Tutorials 11, 109–130 (2009).
[Crossref]

Sun, D.

P. Wei and D. Sun, “Weighted algebraic connectivity: an application to airport transportation network,” IFAC Proc. 44, 13864–13869 (2011).
[Crossref]

Tan, Q.

Y. Zheng, S. Zhao, Y. Liu, Y. Li, Q. Tan, and N. Xin, “Weighted algebraic connectivity maximization for optical satellite networks,” IEEE Access 5, 6885–6893 (2017).
[Crossref]

Tessinari, R.

R. Tessinari, M. Paiva, M. Monteiro, M. Segatto, A. Garcia, G. Kanellos, R. Nejabati, and D. Simeonidou, “On the impact of the physical topology on the optical network performance,” in IEEE British and Irish Conference on Optics and Photonics (2018).

Tornatore, M.

Tran, P.

Tremblay, C.

Uhlig, S.

A. Jamakovic and S. Uhlig, “On the relationship between the algebraic connectivity and graph’s robustness to node and link failures,” in Next Generation Internet Networks, 3rd EuroNGI Conference (2007), pp. 96–102.

Velasco, L.

V. Lopez and L. Velasco, Elastic Optical Networks (Springer, 2016).

Vincent, R.

Waxman, B.

B. Waxman, “Routing of multipoint connections,” IEEE J. Sel. Areas Commun. 6, 1617–1622 (1988).
[Crossref]

Wegener, I.

B. Bollig and I. Wegener, “Improving the variable ordering of OBDDs is NP-complete,” IEEE Trans. Comput. 45, 993–1002 (1996).
[Crossref]

Wei, P.

P. Wei and D. Sun, “Weighted algebraic connectivity: an application to airport transportation network,” IFAC Proc. 44, 13864–13869 (2011).
[Crossref]

Xin, N.

Y. Zheng, S. Zhao, Y. Liu, Y. Li, Q. Tan, and N. Xin, “Weighted algebraic connectivity maximization for optical satellite networks,” IEEE Access 5, 6885–6893 (2017).
[Crossref]

Yang, Y.

Yeh, F.

S. Kuo, S. Lu, and F. Yeh, “Determining terminal-pair reliability based on edge expansion diagrams using OBDD,” IEEE Trans. Reliab. 48, 234–246 (1999).
[Crossref]

Zervas, G.

Zhang, S.

S. Zhang, C. Martel, and B. Mukherjee, “Dynamic traffic grooming in elastic optical networks,” IEEE J. Sel. Areas Commun. 31, 4–12 (2013).
[Crossref]

Zhao, S.

Y. Zheng, S. Zhao, Y. Liu, Y. Li, Q. Tan, and N. Xin, “Weighted algebraic connectivity maximization for optical satellite networks,” IEEE Access 5, 6885–6893 (2017).
[Crossref]

Zheng, Y.

Y. Zheng, S. Zhao, Y. Liu, Y. Li, Q. Tan, and N. Xin, “Weighted algebraic connectivity maximization for optical satellite networks,” IEEE Access 5, 6885–6893 (2017).
[Crossref]

Czech. Math. J. (1)

M. Fiedler, “Algebraic connectivity of graphs,” Czech. Math. J. 23, 298–305 (1973).
[Crossref]

IEEE Access (1)

Y. Zheng, S. Zhao, Y. Liu, Y. Li, Q. Tan, and N. Xin, “Weighted algebraic connectivity maximization for optical satellite networks,” IEEE Access 5, 6885–6893 (2017).
[Crossref]

IEEE Commun. Mag. (1)

C. Davis, I. Smolyaninov, and S. Milner, “Flexible optical wireless links and networks,” IEEE Commun. Mag. 41(3), 51–57 (2003).
[Crossref]

IEEE Commun. Surv. Tutorials (2)

C. Saradhi and S. Subramaniam, “Physical layer impairment aware routing (PLIAR) In WDM optical networks: issues and challenges,” IEEE Commun. Surv. Tutorials 11, 109–130 (2009).
[Crossref]

B. Chatterjee, N. Sarma, and E. Oki, “Routing and spectrum allocation in elastic optical networks: a tutorial,” IEEE Commun. Surv. Tutorials 17, 1776–1800 (2015).
[Crossref]

IEEE J. Sel. Areas Commun. (2)

B. Waxman, “Routing of multipoint connections,” IEEE J. Sel. Areas Commun. 6, 1617–1622 (1988).
[Crossref]

S. Zhang, C. Martel, and B. Mukherjee, “Dynamic traffic grooming in elastic optical networks,” IEEE J. Sel. Areas Commun. 31, 4–12 (2013).
[Crossref]

IEEE Trans. Comput. (1)

B. Bollig and I. Wegener, “Improving the variable ordering of OBDDs is NP-complete,” IEEE Trans. Comput. 45, 993–1002 (1996).
[Crossref]

IEEE Trans. Reliab. (2)

S. Kuo, S. Lu, and F. Yeh, “Determining terminal-pair reliability based on edge expansion diagrams using OBDD,” IEEE Trans. Reliab. 48, 234–246 (1999).
[Crossref]

S. Kuo, F. Min, and H. Lin, “Efficient and exact reliability evaluation for networks with imperfect vertices,” IEEE Trans. Reliab. 56, 288–300 (2007).
[Crossref]

IFAC Proc. (1)

P. Wei and D. Sun, “Weighted algebraic connectivity: an application to airport transportation network,” IFAC Proc. 44, 13864–13869 (2011).
[Crossref]

J. Lightwave Technol. (7)

J. Opt. Commun. Netw. (6)

Science (1)

A.-L. Barabasi and R. Albert, “Emergence of scaling in random networks,” Science 286, 509–512 (1999).
[Crossref]

Other (10)

R. Tessinari, M. Paiva, M. Monteiro, M. Segatto, A. Garcia, G. Kanellos, R. Nejabati, and D. Simeonidou, “On the impact of the physical topology on the optical network performance,” in IEEE British and Irish Conference on Optics and Photonics (2018).

J. M. Simmons, Optical Network Design and Planning (Springer, 2014).

W. D. Grover, Mesh-Based Survivable Networks: Options and Strategies for Optical, MPLS, SONET and ATM Networking (Prentice Hall PTR, 2003).

C. Fenger, E. Limal, U. Gliese, and C. Mahon, “Statistical study of the correlation between topology and wavelength usage in optical networks with and without conversion,” in Networking, Vol. 1815 of Lecture Notes in Computer Science (2000), pp. 168–175.

R. Bhandari, “Optimal physical diversity algorithms and survivable networks,” in Proceedings of the 2nd IEEE Symposium on Computer and Communications (1997), pp. 433–441.

A. Ghosh and S. Boyd, “Growing well-connected graphs,” in Proceedings of the 45th IEEE Conference on Decision & Control (2006), pp. 6605–6611.

I. Son and S. Mao, “Design and optimization of a tired wireless access network,” in Proceedings of IEEE INFOCOM (2010).

V. Lopez and L. Velasco, Elastic Optical Networks (Springer, 2016).

A. Jamakovic and S. Uhlig, “On the relationship between the algebraic connectivity and graph’s robustness to node and link failures,” in Next Generation Internet Networks, 3rd EuroNGI Conference (2007), pp. 96–102.

R. L. Freeman, Telecommunication System Engineering, 4th ed. (Wiley, 2015).

Cited By

Optica participates in Crossref's Cited-By Linking service. Citing articles from Optica Publishing Group journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (13)

Fig. 1.
Fig. 1. Relations among the traffic matrix, physical topology, and RWA/RSA algorithm in communication networks.
Fig. 2.
Fig. 2. Node position and initial configuration for the basic problem. Colored nodes are primary nodes.
Fig. 3.
Fig. 3. Schematic view of the two-step degree bound conditions.
Fig. 4.
Fig. 4. Graphs $G({E,V})$ optimized for (a) ${a_G}$ and (b) $R$ for $\bar q = 0.25$ without node degree constraints.
Fig. 5.
Fig. 5. Relation between number of edges added and ${a_G}$ for (a) $\bar q = 5 \times {10^{- 4}}$ and (b) $\bar q = 0.25$ without node degree constraints.
Fig. 6.
Fig. 6. (a) Relation between number of edges added and $R$ for (a) $\bar q = 5 \times {10^{- 4}}$ and (b) $\bar q = 0.25$ without node degree constraints.
Fig. 7.
Fig. 7. Distribution of node degree, $d(V)$, in the cases of (a) $\bar q = 5 \times {10^{- 4}}$ and (b) $\bar q = 0.25$ without node degree constraints.
Fig. 8.
Fig. 8. Graphs $G({E,V})$ optimized for (a) ${a_G}$ and (b) $R$ by TSDBR for $\bar q = 0.25$ with node degree constraints $({{D_{\min}},{D_{\max}}}) = ({2,4})$.
Fig. 9.
Fig. 9. Relation between number of edges added and ${a_G}$ for (a) $\bar q = 5 \times {10^{- 4}}$ and (b) $\bar q = 0.25$; $({{D_{\min}},{D_{\max}}}) = ({2,4})$.
Fig. 10.
Fig. 10. Relation between number of edges added and $R$ for (a) $\bar q = 5 \times {10^{- 4}}$ and (b) $\bar q = 0.25$; $({{D_{\min}},{D_{\max}}}) = ({2,4})$.
Fig. 11.
Fig. 11. (a) ${\| {a_G} \|_2}$ and (b) ${\| R \|_2}$ for $\boldsymbol{S}({{D_{\min}} = 1})$.
Fig. 12.
Fig. 12. (a) ${\| {a_G} \|_2}$ and (b) ${\| R \|_2}$ for $\boldsymbol{S}({{D_{\min}} = 2})$. (c) Line graph of (a).
Fig. 13.
Fig. 13. Improvement of ${a_G}$ for $({{D_{\min}},{D_{\max}}}) = ({2,4})$ and $\bar q = \{{5 \times {{10}^{- 4}},0.05,0.1,0.15,0.2,0.25} \}$.

Tables (1)

Tables Icon

Algorithm 1. TSDBR Optimization

Equations (7)

Equations on this page are rendered with MathJax. Learn more.

m a x i m i z e a G ( L ( E b a s e E a d d ) ) s u b j e c t t o | E a d d | = N k E a d d E c a n d .
m a x i m i z e R ( G ) = f B D D ( q i , j ) s u b j e c t t o | E a d d | = N k E a d d E c a n d ,
E c a n d = E s t 1 i f E s t 1 , = E s t 2 i f ( E s t 1 = ) ( E s t 2 ) = e l s e ,
E s t 1 = ( I max J min ) ( I min J max ) , E s t 2 = ( I max J max ) E s t 1 ,
I min / max = { v i V : ( v i , v j ) E c a n d d ( v i ) < D min / max } , J min / max = { v j V : ( v i , v j ) E c a n d d ( v j ) < D min / max } .
l 2 := [ k = 1 N k ( l a G o p t i m i z e , k l R o p t i m i z e , k ) 2 ] 1 / 2 .
I m p r o v e m e n t ( a G ) := 100 × ( a G , T S D B R a G , e x h a u s t i v e s e a r c h f o r R 1 ) .