Name: DANIELA BERTOLINI DEPIZZOL
Publication date: 26/11/2018
Advisor:
Name |
Role |
|---|---|
| MARCELO EDUARDO VIEIRA SEGATTO | Advisor * |
Examining board:
| Name |
Role |
|---|---|
| MARCELO EDUARDO VIEIRA SEGATTO | Advisor * |
| MARIA CLAUDIA SILVA BOERES | External Examiner * |
| MOISÉS RENATO NUNES RIBEIRO | Internal Examiner * |
Summary: Optical networks play a vital role in the current information society, and this puts the design of such networks as a central issue. Poor design of an optical network can lead to wasted resources and poor network performance. Many parameters can indicate the characteristics of a network, and among them there is the minimum number of wavelengths (λ) required to meet a given traffic demand, which is a dominant cost factor in network designing, WHERE its optimization maximizes the spectrum available on the network. A natural modeling for optical networks is by means of graphs, which have a number of
nodes (n) and edges (m). The number of possible networks grows exponentially with n, which makes difficult to find networks that minimize λ, what is aggravated by the fact that the calculation of λ is a NP-Hard problem. With the hypothesis that the value of λ to be influenced by the network topology, it is sought to find topological invariants of graphs with polynomial computational time, that are well correlated with λ, and so that λ can be estimated more quickly, as a function of these invariants. In the present
work, it is proceeded with an exploratory search of graphs topological invariants, in the best of efforts. Such raised base of invariants is ranked, in an unprecedented selection of attributes in optical networks, via mutual information estimators. For this, a sample with 2.2 × 106 random networks that mimic real networks is used, WHERE the invariants ranking occurs with all networks together and also separated by n. As a result, stand out the invariants derived from edge betweenness, which are among the best positioned in the obtained rankings, demonstrating their good representativeness to explain λ. Then, from the most significant invariants to explain λ, it is proceeded with appropriate regressions to estimate λ. This estimation facilitates the λ test in a large number of graphs and is considered in heuristics to search, in a few minutes, for topologies that minimize the
requirement for wavelengths. The total savings between the real input networks and their output networks varies from 23% to 59% and, in addition, output networks demonstrate greater reliability compared to real input networks.
