Open Access
Add to BibSonomyAbstract
A communication network is a multilayer network comprising various layered technologies, and the underlying physical topology is an important aspect that determines the upper bound of overall system performance, including total communication capacity, cost, and robustness. We expect that understanding the impact of the physical topology on system performance will lead to better optical communication network design in the future, and we thus focus on clarifying the relationship between physical topology features and system performance. There have been various studies on the relationship between topology features and overall network performance. For example, the average number of hops and the cluster coefficient are well known to change network properties in complex networks. From the perspective of optical communication networks, it is known that the algebraic connectivity and average path length are related to total network capacity, and these findings have been applied in physical topology design models. On the other hand, there have been no quantitative comparisons among various topology features, and the comprehensiveness of the population from which these features are extracted is insufficient. Hence, we have developed a multilayer (physical topology and layer 1) correlation analysis framework that enables a quantitative comparison of topology features. We use this framework to numerically examine the relationships between physical topology features and the total communication capacity, cost, and robustness of optical communication networks, including graph features (especially graph spectra) that have not been investigated. The results show that the Laplacian spectral radius and geodesic distance Laplacian spectral radius are strongly related to system performance, in addition to the conventional average number of hops, cluster coefficient, algebraic connectivity, and average path length. We confirm that these correlations hold for the different network sizes and spatial nonuniformity of real optical backbone networks in different countries and regions. The results show that the average path length and cluster coefficient, or the Laplacian spectral radius and geodesic distance Laplacian spectral radius, are important guidelines for physical topology design of real optical backbone networks.
© 2023 Optica Publishing Group under the terms of the Optica Open Access Publishing Agreement
1. INTRODUCTION
A. General Introduction
Today’s information society depends on optical communication networks. The overall capacity of optical communication networks continues to increase every year [1], and high-capacity, low-power-consumption optical networks will become increasingly important in terms of social issues such as global warming. Optical communication networks are multilayer networks comprising various layers and technologies [2]. For efficiency in layer 1, over the past decade, researchers have developed adaptive modulation techniques for flexible signal bandwidth selection based on the signal propagation distance [3], reconfigurable optical add/drop multiplexer technology for controlling optical path directions [4], optical routing and spectrum allocation (RSA) algorithms [5], and grooming algorithms [6]. Optical network control technologies are also advancing [7,8] toward implementation of elastic optical networks (EONs) and even space-division multiplexing networks.
Such optical communication networks are constructed on physical optical fiber networks, which involve physical topologies, as shown in Fig. 1. In particular, the physical topology greatly influences not only the system’s cost and robustness but also its total communication capacity in conjunction with routing and spectrum assignment in layer 1. For example, the upper bound on communication capacity alone can vary by more than 70% depending on the physical topology [9]. Hence, from a medium- to long-term perspective, it is important to design physical topologies with careful consideration of their impact on overall system performance, including total communication capacity, cost, and robustness. Also, the network size and spatial nonuniformity (of node locations) vary among countries and regions, and it is unclear whether a universal design model that includes the effects of these factors is possible. Against this background, it is important to understand the relationship between the physical topology and system metrics, including a network’s scale and spatial inhomogeneity, to expand the possibilities for future physical topology design.
In this paper, we propose an analytical framework for understanding the relationship between physical topology features and system performance, which includes the multilayer nature of optical communication networks. Using this framework, we extract key topology features that significantly affect the overall performance of optical communication networks, and we reveal new knowledge about physical topology features. First, in Section 1.B, we review research on physical topologies in relation to the multilayer nature of these networks and research on simplifying this complex multilayer nature via physical topology features. Then, in Section 1.C, we give a problem statement and describe our contributions and the paper’s structure.
B. Related Works on Physical Topology in Relation to Multilayer Nature
A physical topology is generally represented by a graph whose nodes are communication buildings and edges are conduits connecting nodes. Various methods have been applied to physical topology design, including mixed integer linear programming (MILP), graphical models, and heuristic models. Among these, we focus here on studies that deal with the complexity of the upper layers. In [10], a cost minimization approach was proposed as a green field design model for a mesh network by the MILP method. That model deals with a routing problem in the upper layers, including spare capacity. Its complexity is said to be difficult even for about 10 nodes without the spectrum assignment problem. In [11], multilayer optimization was proposed to minimize the cost via MILP. That approach considered protection routing for reliability while adding innovations in the IP layer to absorb traffic nonuniformity and thus increase capacity; however, it did not include optimization of the spectrum assignment in layer 1. The physical topology was updated by adding new fiber for long-term planning. In another study, a signal-to-noise ratio aware Barabási-Albert (SNR-BA) graph model [12], which accounts for the signal propagation characteristics in the BA model [13], was shown to rapidly generate physical topologies with high capacity. In general, a graphical model constructs a topology by providing basic rules for the probability of the existence of edges, and the SNR-BA model increases the total capacity by imposing rules for signal propagation to deal with the multilayer nature. Another study [14] aimed to use a heuristic to combine the high robustness of a physical topology and the high capacity of layer 1. To address the multilayer nature, that approach optimized the physical topology and layer 1 together by replacing the RSA problem with a specific graph feature.
In either approach, the challenge is to deal with the multilayer complexity that especially arises from the RSA problem. In terms of physical topology design, a possible way to deal with this challenge is to approximate the RSA problem’s complexity by certain representative measures related to the physical topology layer, and then to treat it as a single physical topology layer problem. From this viewpoint, for optical communication networks, especially wavelength-division multiplexing networks, Baroni and Bayvel have shown that the number of wavelengths required to accommodate a given traffic demand strongly depends on the topology [15]. This relationship between the wavelength assignment efficiency and topology has been found to hold with or without wavelength continuity constraints [16]. It has since been shown that algebraic connectivity has a strong correlation with the wavelength assignment efficiency [17]. Moreover, an analysis of the relationship between the average path length and total capacity [18] has led to better methods [19]. Recently, there have been interesting attempts to apply machine learning to find MILP constraints that do not depend on the intuition of individual engineers and researchers [20].
C. Problem Statement and Our Contribution
Against the above background, this paper focuses on the relationship between physical topology features and the performance of an optical communication network. Among the remaining issues, the current understanding is limited to a few topological features, and there have been no quantitative comparisons among them. Also, these features’ impact on other system performance indicators such as cost and robustness is unclear. Comprehensive knowledge of the impact on multiple performance indicators is important for understanding the existence of trade-offs.
Hence, we seek to address two problems in this paper. The first is to comprehensively clarify the relationships between various physical topology features and system performance indicators, under the assumption of a realistic optical network. The second is to identify physical topology features that simplify the complex multilayer nature and can be used for design guidance according to multiple performance indicators.
Our main contributions here are twofold. First, we propose a multilayer analysis framework comprising a physical topology and layer 1. This framework enables a quantitative comparison of the characteristics of various physical topologies with respect to multiple aspects of system performance. Second, through comprehensive analysis using this framework under realistic conditions, we found that two nonspectral quantities, the average path length and cluster coefficient, and two spectral quantities, the Laplacian spectral radius and geodesic distance Laplacian spectral radius, are important guidelines for physical topology design as they reflect the total capacity, cost, and robustness of a multilayer optical network. The framework was partially introduced in [21], but in the current study, we added robustness to the performance metrics and performed a more comprehensive analysis with a realistic topology.
Regarding the structure of this paper, Section 2.A describes the proposed correlation analysis framework, and Section 2.B describes the topology features examined here. In Section 3.A, we present basic analysis results and extract the important topology features, including the effects of network size and spatial nonuniformity. Section 3.B summarizes the relationship between the key topology features extracted in Section 3.A and system performance, and then describes potential applications in future physical topology design. Finally, Section 4 provides our conclusions.
2. SIMULATION MODEL
A. Correlation Analysis Framework
The proposed analysis framework consists of a system, its input and output, and a graph analysis component, as shown in Fig. 2. The framework is designed to obtain a correlation coefficient $\rho$ between the physical topology features and system performance. The system is assumed to comprise all photonic networks with two layers, for the physical topology ${G_n}({V,E})$ and the layer 1 RSA algorithm. Here, $V$ and $E$ denote the sets of nodes and edges, respectively, and $n = 1, \ldots ,N$ is an identifier that distinguishes topologies. These $N$ topologies were generated by randomly selecting edges with a given network size and node locations. Later, we describe the detailed conditions and illustrate them in Fig. 3. The system inputs are the traffic matrix ${T_{\textit{ij}}}$, node locations $({X,Y})$, and network size $({| V |,| E |})$. The outputs are the total communication capacity $\xi _n^*$, cost ${C_n}$, and robustness ${R_n}$ determined for each physical topology ${G_n}$. The graph feature ${\psi _n}$ for each physical topology ${G_n}$ is an arbitrary measure obtained from graph analysis. Finally, for all $n$, the Pearson correlation coefficient $\rho$ is calculated. Specifically, the relationship between the total communication capacity and the physical topology is obtained from a communication capacity set ${\xi ^*} = \{{\xi _1^*, \ldots ,\xi _N^*} \}$ and a graph feature set $\psi = \{{{\psi _1}, \ldots ,{\psi _N}} \}$ in terms of the following correlation coefficient:
The total communication capacity $\xi _n^*$ is defined as the traffic load with a request blocking ratio of ${10^{- 3}}$ for a given physical topology ${G_n}$. Here, $\xi _n^*$ is obtained by a simple heuristic based on a binary search. We choose a small traffic load ${\xi _{n,0}}$ as an initial value and then calculate the average steady-state request blocking rate $p_{n,i}$ by the RSA algorithm for each traffic load while coarsely increasing the load ${\xi _{n,i}}$. If the average request blocking rate exceeds ${10^{- 3}}$, the binary search starts by targeting ${10^{- 3}}$, and it ends when $| {{\xi _{n,i + 1}} - {\xi _{n,i}}} |$ reaches a target resolution ${{{\Delta}}_\xi}$, set as ${{{\Delta}}_\xi} = {10^{- 2}}$ in this paper. $\xi _n^*$ is on the least-squares fitting curve, $\log_{10} {p_n} = {c_1}{\xi _n} + {c_0}$. The coefficients, ${c_0}$ and ${c_1}$, are determined by using ${p_n} =\{{p_{n,i}}|{p_{n,i}}\ge 10^{-4}\}$ and ${\xi_n} =\{{\xi_{n,i}}|{p_{n,i}}\ge 10^{-4}\}$. The error $\epsilon _n^*$ of $\xi _n^*$ is obtained from the standard deviation $\sigma _n^*$ of the blocking rate near the target rate of ${10^{- 3}}$, by converting it to a traffic load assuming a 95% confidence interval. The cost ${C_n}$ is the total conduit length (fiber length) as in previous studies [12,23]. Although smaller networks require a more detailed cost model including elements such as transponders [24], this paper assumes a long-haul network. The relation between cost and fiber length may become nonlinear with a short optical reach in a careful cost design [2], and this point should be considered in future works. The robustness ${R_n}$ is the average edge connectivity $R_n^e: = {[{| V |({| V | - 1})}]^{- 1}}\mathop \sum \nolimits_{\textit{sd}} {\kappa _{e,{\textit{sd}}}}$ or the average node connectivity $R_n^v: = {[{| V |({| V | - 1})}]^{- 1}}\mathop \sum \nolimits_{\textit{sd}} {\kappa _{v,{\textit{sd}}}}$ for the physical topology ${G_n}$, where ${\kappa _{e,{\textit{sd}}}}/{\kappa _{v,{\textit{sd}}}}$ is the edge/node connectivity between $({s,d})$ node pairs. These indices represent the numbers of link/node disjoint paths and are important quantities for protection paths in optical communication networks [25].
For RSA, we apply the dynamic routing, modulation, and spectrum allocation algorithm. The k-shortest paths first-fit (kSP-FF) algorithm, which is generally used as a benchmark, is applied for route and frequency allocation throughout this paper. To investigate the difference in system performance due to different RSA algorithms, we also examine the FF-kSP algorithm, which has been shown to be closer to an exact solution in terms of total capacity [26]. Although we observe that the absolute total capacity differs with the RSA algorithm even in the same topology, we verified that the correlation coefficient’s variation is small enough (0.01–0.02), as shown in Fig. 6(a) below. We note this issue simply to indicate that this paper’s discussion of the “relative” relation among many topologies is independent of the RSA algorithms [see Fig. 6(a) below]; however, we do not deny the RSA algorithm’s importance in improving the absolute network performance.
Fig. 3. (a) Distribution of real optical networks for $| V | \lt 40$ (data adapted from Table 1 in [12,38]). (b), (c) Examples of ideal networks studied in this paper. (d) ${\rm{NSFNET}} \in {\cal G}_{14,21}^{{\rm{Real}}}$, (e) ${\rm{Germany}} \in {\cal G}_{17,26}^{{\rm{Real}}}$, (f) ${\rm{Arpanet}} \in {\cal G}_{20,32}^{{\rm{Real}}}$, (g) ${\rm{Cox}} \in {\cal G}_{24,40}^{{\rm{Real}}}$, and (h) ${\rm{Europe\; networks}} \in {\cal G}_{28,41}^{{\rm{Real}}}$.
Returning to the RSA specifics, we also verified that the correlation coefficient’s variation is within 0.01–0.02 at the maximum number of routes ${k_{{\max}}} = 4$, 6, 8 by both the kSP-FF and FF-kSP algorithms. Hence, ${k_{{\max}}}$ is set to six. A request ${q_m} = ({{s_m},{d_m},{b_m},{\tau _m}})$, where $m \in \aleph$ is the request identifier, is generated dynamically. Source–destination node pairs $({{s_m},{d_m}})$ are randomly generated following a uniform traffic matrix ${T_{\textit{ij}}}$. The requested transmission capacity ${b_m}$ is determined uniformly at random in the range of (25,400] Gbps. The requested time ${\tau _m}$ statistically follows an exponential distribution. The number of allocated frequency slots, ${{{\Delta}}_{\textit{mk}}}$, is calculated from ${b_m}$ and the $k$th path [27]:
Next, for the physical topology, we first define the network size and node locations. In the real optical backbone network distribution shown by the black circles in Fig. 3(a), the chosen networks are the eight represented by the colored circles along a least-squares fitting (dashed line). Because $\mathop \sum \nolimits_i {k_i}/| V | = 2| E |/\def\LDeqbreak{}| V | = 3.4 - 7/| V |$ from the fitted line and the hand shake lemma, where ${k_i}$ is the node degree, a network with an average node degree of about 3–3.4 is selected for $| V | \geq 14$. Two cases of node positions are considered: spatially uniform (red circles) and spatially nonuniform (blue circles). This enables a comparison of the difference between the two cases and analysis of the effect of spatial nonuniformity.
Table 1. Spectral Quantities
Table 2. Nonspectral Quantities
The spatially uniform physical topology consists of equally spaced hexagonal nodes as shown in Fig. 3(b). The interval between nodes is 500 km. Nodes are added in a counterclockwise manner to create a larger network, as shown in Fig. 3(c). For convenience, we denote the set of physical topologies that forms the basic unit of analysis as ${{\cal G}_{| V |,| E |}}$. For the spatially uniform case, we examine eight physical topology sets: ${{\cal G}_{6,9}}$, ${{\cal G}_{7,11}}$, ${{\cal G}_{10,16}}$, ${{\cal G}_{14,21}}$, ${{\cal G}_{17,26}}$, ${{\cal G}_{20,32}}$, ${{\cal G}_{24,38}}$, and ${{\cal G}_{28,41}}$. For each set, a physical topology is generated by selecting $| E |$ edges with equal probability from a complete graph ${K_{| V |}}$ with the given nodes. Only topologies with edge connectivity ${\kappa _e} \geq 2$ are extracted, and this is done by simply removing ${\kappa _e} \lt 2$ graphs from a large random graph set (${\rm{size}} \gg N$). In this study, to investigate the general relationship between topological features and system performance, no constraints other than edge connectivity are applied. This is because we think that examining the topology and system response before applying constraints would provide preliminary material for the invention of specific design constraints. For each topology set, $N = {10^3}$ to ensure the statistical accuracy of the correlation analysis (the accuracy converges for $N \geq 4 \times {10^2}$).
Figures 3(d)–3(h) show the node locations in the real nonuniform physical topologies, and we denote these physical topology sets by ${\cal G}_{| V |,| E |}^{{\rm{Real}}}$ for convenience. The real physical topologies were chosen for comparison among the NSFNET, Germany, and Europe networks (respectively, ${\cal G}_{14,21}^{{\rm{Real}}}$, ${\cal G}_{17,26}^{{\rm{Real}}}$, and ${\cal G}_{28,41}^{{\rm{Real}}}$), which are geographically very different, and among the NSFNET, Arpanet, and Cox networks (respectively, ${\cal G}_{14,21}^{{\rm{Real}}}$, ${\cal G}_{20,32}^{{\rm{Real}}}$, and ${\cal G}_{24,40}^{{\rm{Real}}}$), which are geographically similar but have different spatial inhomogeneities of their node locations. The edge selection and $N$ are the same as in the uniform case. The distance between nodes is obtained via the World Geodesic System 1984 (WGS84) from the nodes’ latitudes and longitudes.
When comparing and discussing spatial uniformity and nonuniformity, we use a scale factor $\phi$ to ensure that the spatial node densities of compared physical topologies are equal. For example, in the case of NSFNET, $\phi = {z_x}{z_y}/({{z_x^{\rm NSFNET}}{z_y^{\rm NSFNET}}})$ is multiplied by the spatial uniform physical topology ${G_m} \in {{\cal G}_{14,21}}$ to adjust the spatial node density for comparison.
B. Topological Features
Physical topology features can be broadly classified into spectral and nonspectral quantities. The former are widely discussed in terms of spectral graph theory, and the latter, in complex networks.
For spectral quantities, a spectrum is a sequence of eigenvalues of the matrix representation of a graph. A matrix representation of a graph is a Laplacian, for example, which is defined by the difference between the adjacency matrix and the degree matrix. Table 1 defines the four matrices studied in this paper. They can be classified via a combination of two perspectives: whether they contain adjacent node or path information, and whether they reflect an edge’s realistic physical length. The spectral quantities of the Laplacian, which contains adjacency but no physical length information, have been discussed from various perspectives, including connectivity [30], and the distance Laplacian has been studied relatively recently [31]. For the Laplacian ${\cal L}$, the relationship between the second smallest eigenvalue, called the algebraic connectivity (denoted as ${a_G}$ for convenience), and the connectivity [32] or wavelength assignment efficiency [17] has been studied. The maximum eigenvalue, called the Laplacian spectral radius ${r_G}$, is a topological feature that is newly suggested in this paper to have a relation to robustness. The weight of the geodesic Laplacian ${{\cal L}_g}$ is the geodesic distance between nodes. The maximum eigenvalue of the distance Laplacian ${{\cal L}^D}$, which contains path information but no physical length information, is called the distance Laplacian spectral radius, and its relation to the chromatic number has been investigated [33]. The geodesic distance Laplacian ${\cal L}_g^D$ consists of information on the shortest path lengths between nodes. The maximum eigenvalue of ${\cal L}_g^D$ is called the geodesic distance Laplacian spectral radius, ${\partial _G}$. It is a topological feature that is newly shown in this study to have a relation to optical networks.
The nonspectral quantities are defined in Table 2. The average number of hops, $\bar h$, and the cluster coefficient $\bar c$ are the most commonly used indicators in complex network analysis. In general, topologies approach random graphs when the number of hops is small and regular graphs when the number of hops is large. Regarding the clustering coefficient, ${\bar h_{{\rm{SW}}}} \sim {\bar h_{{\rm{ER}}}} \lt {\bar h_{{\rm{Regular}}}}$ and ${\bar c_{{\rm{ER}}}} \lt {\bar c_{{\rm{SW}}}} \sim {\bar c_{{\rm{Regular}}}}$ for small-world (SW) networks [34]. We also evaluate the average shortest path length ${\bar h_g}$ and the weighted cluster coefficient ${\bar c_g}$ [35], thus accounting for the physical distance between $\bar h$ and $\bar c$. To measure the network size, we evaluate the diameters $\delta$ and ${\delta _g}$, which are respectively determined by the maximum number of hops and the maximum shortest path length. The global efficiency $\bar \eta$ and geodesic global efficiency ${\bar \eta _g}$ correspond to $\bar h$ and ${\bar h_g}$, respectively. They are used in complex network analysis as more stable features [36].
3. RESULTS AND DISCUSSION
A. Important Topology Features and Dependence on Network Scale/Nonuniformity
To illustrate a typical relationship between the physical topology features and system performance, Fig. 4 shows the relationship between the algebraic connectivity ${a_G}$ and total capacity ${\xi ^*}$. There is a strong correlation of $\rho ({{\xi ^*},{a_G}}) = 0.83$, and the total network capacity increases in proportion to the algebraic connectivity, even though the correlation itself does not indicate clear causality. At minimum, the dynamic frequency assignment problem for EONs and the static wavelength assignment problem based on graph coloring are dual problems; accordingly, we can see that the problem here is essentially the same as the relationship between the number of required wavelengths and the algebraic connectivity, as mentioned in [17].
Fig. 4. Relation between algebraic connectivity ${a_G}$ and total capacity ${\xi ^*}$ for ${{\cal G}_{14,21}}$ by the kSP-FF algorithm.
Figure 5 shows the results of correlation analysis between spectral quantities other than the algebraic connectivity and system performance, including cost and robustness. In the figure, $S({\cal L})$ represents the spectrum of ${\cal L}$. There are three cases for evaluation: no correlation, $| \rho | \lt 0.4$; correlation, $0.4 \le | \rho | \lt 0.7$; and strong correlation, $0.7 \le | \rho |$. The strongest correlation with the total capacity is exhibited by the Laplacian’s second eigenvalue, i.e., algebraic connectivity. Moreover, among the quantities that are strongly correlated with total capacity, the maximum value of $S({{\cal L}_g^D})$, the geodesic distance Laplacian spectral radius ${\partial _G}$, is also correlated with cost. The Laplacian’s maximum eigenvalue ${r_G}$ has the strongest correlation with robustness.
Fig. 5. Correlations between a graph’s spectral quantities and the system performance indices for ${{\cal G}_{14,21}}$: (a) $\rho ({{\xi ^*},\psi})$ by the kSP-FF algorithm; (b) $\rho ({C,\psi})$; and (c), (d) $\rho ({R,\psi})$, where $\psi = \{{S({\cal L}),S({{{\cal L}_g}}),S({{{\cal L}^D}}),S({{\cal L}_g^D})} \}$, and $S({\cal L})$ represents the spectrum of ${\cal L}$. The eigenvalues of these spectra, ${\mu _i}$ ($i = 1,2, \ldots ,| V |$), are listed in the order ${\mu _1} \le {\mu _2} \le \cdots \le {\mu _{| V |}}$.
Fig. 6. Correlations between various graph quantities in $\psi$ (horizontal axis) and system performance indices for ${{\cal G}_{14,21}}$: (a) $\rho ({{\xi ^*},\psi})$ by the kSP-FF (black) and FF-kSP (red) algorithms, (b) $\rho ({C,\psi})$, and (c), (d) $\rho ({R,\psi})$.
Next, Fig. 6 shows the results for the nonspectral quantities, along with the spectral quantities $\{{{a_G},{\partial _G},{r_G}} \}$ extracted in the discussion of Fig. 5. First, as shown in Fig. 6(a), we verified that the RSA algorithm’s impact on the correlation coefficients is small enough to be negligible in the following discussion. Thus, we focus hereafter on the kSP-FF algorithm’s results. The quantities can be generally classified into three groups: the first group is correlated only with the total capacity, the second group is correlated with both the total capacity and cost, and the third group is correlated with robustness. Here, we exclude $({\delta ,{\delta _g},{{\bar c}_g}})$ from the following discussion because $({\bar h,{{\bar h}_g},\bar c})$ show better correlation. A topology focused on total capacity can be obtained by increasing $\{{\bar \eta ,{a_G}} \}$ or decreasing $\bar h$. Among these quantities, the spectral quantity ${a_G}$ has the strongest correlation. On the other hand, a physical topology with good capacity and cost can be obtained by increasing $\{{{{\bar h}_g},{\partial _G}} \}$ or ${\bar \eta _g}$. Among these quantities, the geodesic distance Laplacian spectral radius ${\partial _G}$ has the strongest correlation with total capacity, while ${\bar \eta _g}$ has the strongest correlation with cost. Topologies become more robust by increasing ${a_G}$ or decreasing $\{{\bar c,{r_G}} \}$. The results suggest that the lower bound of the Laplacian spectral radius ${r_G}$, which has the strongest correlation with the mean edge connectivity, is related to the connectivity. The cluster coefficients show a strong negative correlation with the mean node connectivity. Studies of complex networks with large node and edge sizes have suggested that, as the cluster coefficient increases, the graph’s node/edge connectivity also increases (e.g., Fig. 9 in [37]). However, for optical backbone networks with $| V | \lt 40$, it is desirable to have a small cluster coefficient to maintain robustness.
Next, Fig. 7 shows the dependence of the correlation between physical topology features and system performance on network size. The physical topology features $\{\bar h,\bar \eta ,{a_G},\bar c,\def\LDeqbreak{}{r_G},{{\bar h}_g},{{\bar \eta}_g},{\partial _G} \}$ were extracted as described in the discussion of Fig. 6. First, we examine $\{{\bar h,\bar \eta ,{a_G}} \}$, which are correlated only with total capacity. From Fig. 7(a), the correlations for $\{{\bar h,\bar \eta ,{a_G}} \}$ become stronger as the scale increases, with ${a_G}$ being the most suitable feature for increasing network capacity. Because $\bar \eta$ is slightly less correlated than $\bar h$ and behaves in almost the same way, we exclude it from the following discussion. Next, we examine $\{{{{\bar h}_g},{{\bar \eta}_g},{\partial _G}} \}$, which are correlated with both the total capacity and cost. We exclude ${\bar \eta _g}$ from the following discussion because it loses its correlation with total capacity as network size increases. In contrast, ${\bar h_g}$ remains correlated with both, although the correlation weakens as network size increases. ${\partial _G}$ behaves almost the same as ${\bar h_g}$, but in comparison to ${\bar h_g}$, the cost correlation is weaker while the total capacity correlation is stronger. The choice of $\{{{{\bar h}_g},{\partial _G}} \}$ thus depends on whether we emphasize total capacity or cost. For $\{{{a_G},\bar c,{r_G}} \}$ in relation to robustness, ${r_G}$ remains correlated regardless of size, while $\{{{a_G},\bar c} \}$ lose their correlation, as shown in Fig. 7(c).
Fig. 7. Dependencies of correlations (a) $\rho ({{\xi ^*},\psi})$, (b) $\rho ({C,\psi})$, and (c), (d) $\rho ({R,})$ on network size.
Finally, we examine whether the above argument holds even for the realistic nonuniform topologies shown in Fig. 8. Among the important topological features $\{{\bar h,{a_G},\bar c,{r_G},{{\bar h}_g},{\partial _G}} \}$, only those related to distance, $\{{{{\bar h}_g},{\partial _G}} \}$, are discussed here. By comparing the results for the spatially uniform (solid lines) and nonuniform (dashed lines) node locations in the geographically different NSFNET, Germany, and Europe networks (${{\cal G}_{14,21}}$, ${{\cal G}_{17,26}}$, and ${{\cal G}_{28,41}}$) in Figs. 8(a) and 8(b), we see that the relationship between ${\partial _G}$ and the total capacity is slightly different, but the differences tend to be the same in all three cases. This trend also holds for the NSFNET, Arpanet, and Cox networks (respectively, ${{\cal G}_{14,21}}$, ${{\cal G}_{20,32}}$, and ${{\cal G}_{24,40}}$), which are geographically similar but have different node locations and sizes. Thus, at least within this experiment’s scope, we have confirmed that the relationship between a topology metric and overall performance can be examined without distinguishing the generally spatially uniform and nonuniform cases.
Fig. 8. Correlation of distance-related features $\{{{{\bar h}_g},{\partial _G}} \}$ with the total capacity and cost for uniform (solid lines) and nonuniform (dashed lines) physical topologies.
B. Relation between Key Topology Features and Physical Topology Design
From the comprehensive analysis described in Section 3.A, we have found that the following physical topology features are related to the system metrics of an optical backbone network: the three nonspectral quantities of the average number of hops, cluster coefficient, and average path length, $\{{\bar h,\bar c,{{\bar h}_g}} \}$, and the three spectral quantities of the algebraic connectivity, Laplacian spectral radius, and geodesic distance Laplacian spectral radius, $\{{{a_G},{r_G},{\partial _G}} \}$. The importance of $\{{{r_G},{\partial _G}} \}$ is a new result.
First, we discuss the nonspectral quantities. Among $\{{\bar h,\bar c,{{\bar h}_g}} \}$, no universal physical topology feature correlates with all three performance indicators: total capacity, cost, and robustness. Therefore, at least two quantities are necessary to create a physical topology set that is aware of the total capacity, cost, and robustness. As the number of hops has no correlation with cost and only the cluster coefficient is correlated with robustness, the minimal feature combination is $\{{\bar c,{{\bar h}_g}} \}$. In real networks, cluster coefficients are distributed between 0 and 0.6 (e.g., Fig. 10 in [38]), and a design with a large cluster coefficient cannot be ruled out. Regarding this point, Figs. 9(a)–9(d) show the distribution of overall performance in the feature space including cluster coefficient values, and some topologies certainly show good total capacity and robustness even with a large cluster coefficient. However, the proportion is so small that it does not effectively narrow down a topology set that is aware of the capacity, cost, and robustness.
Fig. 9. Scatter plots of system performance in $({{{\bar h}_g},\bar c})$ space for ${\cal G}_{14,21}^{{\rm{Real}}}$. The stars indicate NSFNET, shown in Fig. 3(d).
Next, we discuss the spectral quantities. First, for intuitive understanding, Fig. 10(a) shows the correlations among the topology features. These correlations were calculated for the physical topology set ${\cal G}_{14,21}^{{\rm{Real}}}$, and the trend is similar for the other topology sets. The correlations show that $\{{{a_G},{\partial _G}} \}$ are quantities with respectively similar properties to $\{{\bar h,{{\bar h}_g}} \}$, whereas ${r_G}$ is an abstract quantity with no intuitively connected measure. When narrowing the search space for a certain optimization method, it is preferable to consider a combination of ${\partial _G}$, which is correlated with cost, and ${r_G}$, which is highly independent. Figures 10(b)–10(e) show scatter plots like those in Fig. 9, Figs. 7(c), 9(c), and 10(d), indicating that a focus on spectral rather than nonspectral quantities is more effective in narrowing candidates for better edge connectivity in large-scale networks.
Fig. 10. (a) Correlation among topological features. (b)–(e) Scatter plots of system performance in $({{r_G},{\partial _G}})$ space for ${\cal G}_{14,21}^{{\rm{Real}}}$.
Finally, we discuss the applicability of this work. Among nonspectral quantities, because ${\bar h_g}$ can be linearized, the search space can be narrowed down as constraints of MILP. For graphical models, SNR-BA [12] already introduced an algorithm to efficiently reduce the average path length. In addition, it may be possible to generate more robust graphs by, for example, suppressing local triplets in preferential attachment constraints. A spectral quantity could also be used as an indicator for efficiently narrowing the search space by using a heuristic. For instance, more efficient designs may be possible through graph sparsification [39], which reduces the number of edges significantly and quickly while preserving spectral properties.
4. CONCLUSION
To address the physical topology design problem regarding the multilayer nature of optical networks, we have examined the relationship between overall system performance indicators and physical topology features. To identify key topological features that are more strongly correlated with multiple system performance indicators, such as the total capacity, cost, and robustness, we proposed a framework to enable a quantitative comparison of various topological features. Then, we comprehensively studied the relationship between performance indicators and topological features under realistic optical network conditions. As a result, we found that two nonspectral quantities, the average path length and cluster coefficient, and two spectral quantities, the Laplacian spectral radius and geodesic distance Laplacian spectral radius, are key topological features affecting overall system performance. In particular, our framework revealed a new relation between the two spectral quantities and optical networks.
We have not discussed specific applications of these topological features, but they are useful for simplifying complex multilayer networks, narrowing down possibilities in the big picture, and determining myriad possible edge combinations. For nonspectral quantities, note that the correlation between cluster coefficients and average edge connectivity becomes small when the network size exceeds 20 nodes. While spectral quantities are difficult to grasp intuitively, they can serve as indicators that reflect a better correlation with the total capacity, cost, and robustness in optical backbone networks.
Acknowledgment
Portions of this work were presented at the International Conference on Optical Network Design and Modeling (ONDM) in 2022.
REFERENCES
1. “Cisco Annual Internet Report (2018–2023) White Paper,” 2020, https://www.cisco.com/c/en/us/solutions/collateral/executive-perspectives/annual-internet-report/white-paper-c11-741490.html.
2. J. M. Simmons, Optical Network Design and Planning (Springer, 2014).
3. M. Jinno, H. Takara, B. Kozicki, Y. Tsukishima, Y. Sone, and S. Matsuoka, “Spectrum-efficient and scalable elastic optical path network: architecture, benefits, and enabling technologies,” IEEE Commun. Mag.47(11), 66–73 (2009). [CrossRef]
4. S. Gringeri, B. Basch, V. Shukla, R. Egorov, and T. J. Xia, “Flexible architectures for optical transport nodes and networks,” IEEE Commun. Mag.48(7), 40–50 (2010). [CrossRef]
5. 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]
6. S. Zhang, C. Martel, and B. Mukherjee, “Dynamic traffic grooming in elastic optical networks,” IEEE J. Sel. Areas Commun.31, 4–12 (2013). [CrossRef]
7. A. Giorgetti, A. Sgambelluri, R. Casellas, R. Morro, A. Campanella, and P. Castoldi, “Control of open and disaggregated transport networks using the Open Network Operating System (ONOS) [Invited],” J. Opt. Commun. Netw.12, A171–A181 (2020). [CrossRef]
8. R. Casellas, R. Martínez, R. Vilalta, R. Muñoz, A. González-Muñiz, O. González de Dios, and J. P. Fernández-Palacios, “Advances in SDN control and telemetry for beyond 100G disaggregated optical networks [Invited],” J. Opt. Commun. Netw.14, C23–C37 (2022). [CrossRef]
9. R. S. Tessinari, M. H. M. Paiva, M. E. Monteiro, M. E. V. Segatto, A. S. Garcia, G. T. 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).
10. W. D. Grover, Mesh-Based Survivable Networks: Options and Strategies for Optical, MPLS, SONET and ATM Networking (Prentice Hall PTR, 2003).
11. S. Ahuja, V. Gupta, V. Dangui, S. Bali, A. Gopalan, H. Zhong, P. Lapukhov, Y. Xia, and Y. Zhang, “Capacity-efficient and uncertainty-resilient backbone network planning with hose,” in SIGCOMM (2021).
12. 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]
13. A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” Science286, 509–512 (1999). [CrossRef]
14. K. Higashimori, F. Inuzuka, and T. Ohara, “Physical topology optimization for highly reliable and efficient wavelength-assignable optical networks,” J. Opt. Commun. Netw.14, 16–24 (2022). [CrossRef]
15. S. Baroni and P. Bayvel, “Wavelength requirements in arbitrarily connected wavelength-routed optical networks,” J. Lightwave Technol.15, 242–251 (1997). [CrossRef]
16. 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.
17. B. Châtelain, M. P. Belanger, C. Tremblay, F. Ganon, and D. V. Plant, “Topological wavelength usage estimation in transparent wide area networks,” J. Opt. Commun. Netw.1, 196–203 (2009). [CrossRef]
18. D. Semrau, S. Durrani, G. Zervas, R. I. Killey, and P. Bayvel, “On the relationship between network topology and throughput in mesh optical networks,” arXiv, arXiv:2008.06708v1 (2020). [CrossRef]
19. P. Bayvel, R. Luo, R. Matzner, D. Semrau, and G. Zervas, “Intelligent design of optical networks: which topology features help maximise throughput in the nonlinear regime?” in European Conference on Optical Communication (2020).
20. H. Zhu, V. Gupta, S. Ahuja, Y. Tian, Y. Zhang, and X. Jin, “Network planning with deep reinforcement learning,” in SIGCOMM (2021).
21. K. Higashimori, T. Inoue, T. Tanaka, F. Inuzuka, and T. Ohara, “Impact of physical topology features on performance of optical backbone networks,” in International Conference on Optical Network Design and Modeling (ONDM) (2022).
22. P. Schober, C. Boer, and L. A. Schwarte, “Correlation coefficients: appropriate use and interpretation,” Anesth. Analg.126, 1763–1768 (2018). [CrossRef]
23. E. K. Cetinkaya, M. J. F. Alenazi, Y. Cheng, A. M. Peck, and J. P. G. Sterbenz, “A comparative analysis of geometric graph models for modelling backbone networks,” Opt. Switching Netw.14, 95–106 (2014). [CrossRef]
24. K. C. Guan and V. W. S. Chan, “Cost-efficient fiber connection topology design for metropolitan area WDM networks,” J. Opt. Commun. Netw.1, 158–175 (2009). [CrossRef]
25. R. Bhandari, “Optimal physical diversity algorithms and survivable networks,” in Proceedings of 2nd IEEE Symposium on Computer and Communications (1997), pp. 433–441.
26. 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]
27. L. Gong, X. Zhou, X. Liu, W. Zhao, W. Lu, and Z. Zhu, “Efficient resource allocation for all-optical multicascading over spectrum-sliced elastic optical networks,” J. Opt. Commun. Netw.5, 836–847 (2013). [CrossRef]
28. Z. Zhu, X. Liu, Y. Wang, W. Lu, L. Gong, S. Yu, and N. Ansari, “Impairment- and splitting-aware cloud-ready multicast provisioning in elastic optical networks,” IEEE/ACM Trans. Netw.25, 1220–1234 (2017). [CrossRef]
29. “Spectral grids for WDM applications: DWDM frequency grid,” ITU-T Recommendation G.694.1 (2020).
30. A. E. Brouwer and W. H. Haemers, Spectra of Graphs (Springer, 2011).
31. M. Aouchiche and P. Hansen, “Two Laplacians for the distance matrix of a graph,” Linear Algebr. Appl.439, 21–33 (2013). [CrossRef]
32. M. Fiedler, “Algebraic connectivity of graphs,” Czech. Math. J.23, 298–305 (1973). [CrossRef]
33. M. Aouchiche and P. Hansen, “Distance Laplacian eigenvalues and chromatic number in graphs,” Filomat31, 2545–2555 (2017). [CrossRef]
34. D. Watts and S. Strogatz, “Collective dynamics of ‘small-world’ networks,” Nature393, 440–442 (1998). [CrossRef]
35. J. Onnela, J. Saramäki, J. Kertész, and K. Kaski, “Intensity and coherence of motifs in weighted complex networks,” Phys. Rev. E71, 065103 (2005). [CrossRef]
36. V. Latora and M. Marchiori, “Efficient behavior of small-world networks,” Phys. Rev. Lett.87, 198701 (2001). [CrossRef]
37. 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.
38. C. Pavan, R. M. Morais, J. R. F. Rocha, and A. N. Pinto, “Generating realistic optical transport network topologies,” J. Opt. Commun. Netw.2, 80–90 (2010). [CrossRef]
39. J. D. Batson, D. A. Spielman, and N. Srivastava, “Twice-Ramanujan sparsifiers,” SIAM Rev.56, 315–334 (2014). [CrossRef]
Katsuaki Higashimori received 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 specialties are space plasma physics (through 2015, mainly interested in collision-less plasmas and phenomena at high magnetic Reynolds numbers), free-space optical communication (2015–2020, devoting himself to the development of an inter-satellite free space optical communication system), and optical fiber communication networks (since 2020, mainly interested in network mathematization and optimization methods to improve real networks). He is a member of the IEICE.
Takafumi Tanaka received a B.E. degree in electronics engineering (2007) and an M.S. degree in informatics (2009) from the University of Tokyo. He is currently a research engineer at NTT Network Innovation Laboratories working on intelligent design and control of photonic networks. He received the IEEE ComSoc JC Young Engineer Award from the IEEE ComSoc Japan Chapter in 2012 and the IEICE Communications Society Best Paper Award in 2022. He is a member of the IEICE.
Fumikazu Inuzuka received B.E. (2002) and M.E. (2004) degrees in applied physics from the Tokyo University of Agriculture and Technology, Tokyo, Japan. In 2004, he joined Nippon Telegraph and Telephone (NTT) Corporation, Kanagawa, Japan, where he researches high-speed photonic transport and processing systems, and photonic networking and management systems. He is a member of the IEICE.
Takuya Ohara [M] is a senior research engineer and supervisor at the Transport Innovation Laboratory, NTT Network Innovation Laboratories. He received B.E. (1998) and M.E. (2000) degrees in electronic engineering from the University of Tokyo. He joined NTT Network Innovation Laboratories in 2000. His research interest is optical fiber communication, specifically, optical networking, optical transport network (OTN) evolution, and high-speed, 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 researched an optical path tracing technique.
Takeru Inoue is a Distinguished Researcher at Nippon Telegraph and Telephone Corporation (NTT) Laboratories, Japan. He received B.E. (1998) and M.E. (2000) degrees in engineering science and a Ph.D. degree in information science (2006) from Kyoto University, Japan. In 2000, he joined NTT Laboratories. From 2011 to 2013, he was an ERATO researcher with the Japan Science and Technology Agency, where his research focused on algorithms and data structures. His research interests widely cover algorithmic approaches in communication networks. Dr. Inoue has received several prestigious awards, including the Best Paper Award of the Asia-Pacific Conference on Communications in 2005, the Best Paper Award of the IEEE International Conference on Communications in 2016, the Best Paper Award of the IEEE Global Communications Conference in 2017, the Best Paper Award of IEEE Reliability Society Japan Joint Chapter in 2020, the IEEE Asia/Pacific Board Outstanding Paper Award in 2020, and the IEICE Paper of the Year in 2021. He serves as an associate editor of the IEEE Transactions on Network and Service Management.
