Exploring graph coloring heuristics for optical networks planning

Abstract

Optical networks are essential in today’s global communications, and the study of planning tools that efficiently allocate network resources is crucial to network providers. The assignment of wavelengths, alongside routing, are critical functions in all optical network planning tools. This dissertation focuses on the study of wavelength assignment algorithms based on Graph Coloring techniques. In this dissertation, we analyse the performance of the usual Greedy heuristic, a well-known Graph Coloring heuristic applied to optical network planning, as well as the Degree of Saturation (DSATUR) and Recursive Largest First (RLF) heuristics, in several real net- work scenarios. These last two heuristics, to the best of our knowledge, have not yet been applied in the context of optical networks. Extensive simulations have been performed, using real network topologies, such as COST 239, and CONUS networks, considering a full mesh logical topology, and we conclude that DSATUR and RLF heuristics can out-perform Greedy heuristic in network scenarios where there are several network clusters interconnected by only one or two links. In these cases, the RLF and DSATUR heuristics provide less 9 and 5 wavelengths respectively than the Greedy heuristic. Despite generating fewer wavelengths, we have verified that these heuristics need a higher computing time than the Greedy heuristic. Besides these heuristics, the traditional First Fit and Most-Used heuristics were also studied, and lead to performance similar to the Greedy heuristics.

As redes óticas são essenciais nas comunicações globais atuais e, o estudo de ferramentas de planeamento que utilizem eficientemente os recursos da rede são cruciais aos operadores de rede. A atribuição de comprimentos de onda, juntamente com o encaminhamento, são funções críticas em todas as ferramentas de planeamento de redes óticas. Esta dissertação foca-se no estudo de algoritmos de atribuição de comprimentos de onda baseados em técnicas de Coloração de Grafos. Na presente dissertação analisamos o desempenho da heuríıstica Greedy, uma heurística de Coloração de Grafos tipicamente aplicada ao planeamento de redes óticas, assim como as heurísticas Degree of Saturation (DSATUR) and Recursive Largest First (RLF), em diversos cenários de redes reais. Estas duas últimas heurísticas, tanto quanto sabemos, ainda não foram aplicadas no contexto de redes óticas. Foram realizadas inúmeras simulações, utilizando topologias de redes reais, como as redes COST 239, e CONUS considerando uma topologia lógica em malha completa e concluímos que as heurísticas DSATUR e RLF podem superar a heurística Greedy em cenários de rede onde existem vários clusters de rede interligados por apenas uma ou duas ligações. Nestas redes, as heurísticas RLF e DSATUR, proporcionam menos 9 e 5 comprimentos de onda, respetivamente, do que a heurística Greedy. Apesar de gerarem menos comprimentos de onda, verificamos que estas heurísticas necessitam de um tempo de computação superior ao da heurística Greedy. Além de terem sido estudadas estas heurísticas, também foram estudadas as heurísticas tradicionais First Fit e Most-Used e concluímos que têm um desempenho semelhante à heurística Greedy.