Exploring optimal solutions for planning optical networks with graph coloring techniques

Abstract

Optical networks are crucial in today’s communications, so their planning is of paramount importance. Routing and Wavelength Assignment (WA) are essential planning functions to transport the data in these networks. This work aims to study different graph coloring techniques for WA in static optical networks. We analyze and compare different graph coloring algorithms such as the Greedy heuristic, an exact algorithm based on Integer Linear Programming (ILP) and the Tabu Search meta-heuristic, for WA in optical networks. The studies are performed considering several real network scenarios, different logical and path topologies, and the number of colors and computation time of each one of the studied algorithms is analysed. We have concluded that the exact algorithm based on ILP, although giving always the optimum number of colors, is only applicable to networks with less than 20 nodes, due to its higher computation time. It was also concluded that the Tabu Search algorithm gives always the same results as the exact algorithm, for the real networks studied, but in a much faster computation time. Finally, we have concluded that the common Greedy algorithm performs as well as the Tabu Search algorithm, for all the real networks studied, but in some scenarios, with random path matrices, the Tabu Search gives a lower number of colors than the Greedy algorithm. For example, the Tabu Search gives less 35 colors than the Greedy algorithm for a random path matrix with 1000 paths and a 50% probability that each path has one or more links being used by the other paths.

As redes óticas são fundamentais para as comunicações atuais, tendo o seu planeamento uma grande importância. O encaminhamento e a atribuição de comprimentos de onda são funções essenciais no planeamento do transporte de dados nestas redes. Este trabalho pretende estudar diferentes técnicas de coloração de grafos para a atribuição de comprimentos de onda nas redes óticas. Analisamos e comparamos diferentes algoritmos de atribuição de comprimentos de onda, como a heurística Greedy, um algoritmo exato baseado em Programação Linear Inteira (PLI) e um algoritmo de procura meta-heurístico, o Tabu Search. Estudaram-se estes algoritmos para diferentes redes reais, diferentes topologias lógicas e de caminhos, com o objetivo de analisar o número de cores e o tempo computacional obtidos por cada algoritmo estudado. Concluímos que o algoritmo exato baseado em PLI, embora devolva sempre um número de cores ótimo, aplica-se apenas a redes com menos de 20 nós, devido ao seu tempo computacional elevado. Também se concluiu que o Tabu Search devolve sempre os mesmos resultados que o algoritmo exato, para as redes reais, mas com mais rapidez computacional. Concluiu-se também para as redes reais, que o Greedy estima o mesmo número de cores que o Tabu Search. No entanto, com matrizes geradas aleatoriamente, nalguns casos, o Tabu Search retorna menos cores que o Greedy. Por exemplo, o Tabu Search devolve menos 35 cores que o Greedy para uma matriz de 1000 caminhos e 50% de probabilidade de cada caminho ter uma ou mais ligações pertencentes aos restantes caminhos.