Graph coloring techniques for planning dynamic optical networks

Abstract

Dynamic optical networks will be crucial in global optical communications in the next 5-10 years.On-demand services, fuelled by applications such as cloud computing and grid computing, are the main drivers for the availability of an increasingly dynamic network infrastructure. Efficient network planning tools that deal with Routing and Wavelength Assignment problems are of paramount relevance in this dynamics cenario. In this work, a simulator for planning dynamic optical networks was developed, and several real networks were tested, such as National Science Foundation Network, British Telecom, US Backbone Network, and also bidirectional ring networks. In this simulator, we have implemented a graph coloring wavelength assignment algorithm named Small-Bucket algorithm that allows recoloring to occur. A comparison performance with the First-fit algorithm is performed in terms of the blocking probability, number of recolorings, number of colors used and simulation time. It is concluded that the Small-Bucket algorithm originate slower blocking probabilities than the ones obtained with the First-fit algorithm. However, to reach these low blocking probabilities, the Small-Bucket algorithm makes use of a larger number of wavelengths and recolorings.

As redes ópticas dinâmicas serão cruciais nas comunicações ópticas globais nos proximos 5-10 anos. Os principais impulsionadores deste dinamismo são os serviços on-demand, suportados por aplicações como computação em nuvem e computação em grelha, conduzindo à necessidade de uma infraestrutura de rede cada vez mais dinâmica. Ferramentas de planeamento de rede eficientes, que lidam com os problemas de encaminhamento e atribuição de comprimentos de onda serão de extrema relevância neste cenário dinâmico. Neste trabalho foi desenvolvido um simulador para o planeamento de redes ópticas dinâmicas, e várias redes reais foram testadas, como a National Science Foundation Network, a British Telecom, a US Backbone Network e também redes bidirecionais em anel. Neste simulador, implementa-se um algoritmo de coloração de grafos denominado algoritmo Small-Bucket, que permite a ocorrência de recolorações de nós. Este algoritmo é comparado como algoritmo First-fit, em termos de probabilidade de bloqueio, número de recolorações, número de cores usadas e tempo de simulação. Conclui-se que o algoritmo Small-Bucket produz menores probabilidades de bloqueio do que as obtidas com o algoritmo First-fit. No entanto, para atingir essas baixas probabilidades de bloqueio, o algoritmo Small-Bucket faz uso de um maior número de comprimentos de onda e recolorações.