[pt] Este trabalho investiga o problema de alocação sub-óptima de conversores de comprimento de onda em nós de redes ópticas parciais, através da proposição de 3 algoritmos baseados nas metaheurísticas GA (Algoritmo Genético), PSO (Optimização por Enxame de Partícula) e SA (Recozimento Simulado). Simulações são apresentadas para ratificar os benefícios com a introdução de conversores nas arquiteturas de rede. Os desempenhos dos algoritmos são mensurados via um simulador, comparando-os com outros algoritmos estabelecidos na literatura. / [en] This work investigates the problem of suboptimally placing wavelength converters at nodes of partial optical networks, through the proposition of 3 algorithms based on the metaheuristics GA (Genetic Algorithm), PSO (Particle Swarm Optimization) and SA (Simulated Annealing). Simulations are presented to ratify the benefits with the introduction of wavelength converters on networks architectures. The results of these algorithms are measure by a simulator, comparing them with other algorithms in literature.

[pt] Nas redes de fibras óticas, as informações são transmitidas na forma de um sinal luminoso através de uma fibra ótica. A tecnologia de multiplexação WDM permite a transmissão simultânea de vários sinais em um mesmo enlace. As conexões entre estações terminais são estabelecidas na forma de caminhos óticos, que são definidos em função de sua rota e do comprimento de onda no qual são multiplexados. Conversores de comprimentos de onda não são considerados neste trabalho. Conseqüentemente, os caminhos óticos devem permanecer com o mesmo comprimento de onda em todos os enlaces do transmissor ao receptor. O Problema de Roteamento e Atribuição Mínima de Comprimentos de Onda (min- RWA) consiste em estabelecer um conjunto de conexões entre pares de estações e atribuir um determinado comprimento de onda para cada uma delas, de forma que caminhos óticos que compartilhem algum enlace da rede tenham comprimentos de onda diferentes e que o número total de comprimentos de onda utilizados seja mínimo. Neste trabalho, uma nova heurística é proposta para min-RWA, onde k possíveis rotas são calculadas para cada conexão e, em seguida, uma rota (dentre as rotas pré-calculadas) e um comprimento de onda são atribuídos a cada conexão resolvendo-se um Problema de Coloração de Partições (PCP). O PCP é um problema de coloração em grafos particionados, ou seja, grafos onde os vértices estão particionados em subconjuntos disjuntos. O PCP consiste em selecionar e colorir um único vértice de cada subconjunto, de modo que dois vértices adjacentes, no grafo induzido pelos vértices selecionados tenham cores diferentes e que o número total de cores utilizadas seja mínimo. Nesta dissertação, são apresentadas e propostas novas heurísticas para PCP e min-RWA. Estas heurísticas são comparadas com as melhores conhecidas na literatura. / [en] In optical networks, the information is transmitted along the optical fibers as optical signals. Wavelength Division Multiplexing (WDM) allows more efficient use of the huge capacity of optical fibers, as far as it permits the simultaneous transmission of different channels along the same fiber, each of them using a different wavelength. The connections are established by lightpaths, in which the signal is converted to the optical domain and reaches the receptor without conversion to the electrical domain. A lightpath is defined by a route and a wavelength. We assume that wavelength conversion along a lightpath is not permitted, since this technology is not yet fully available. Therefore, each lightpath should use the same wavelength from the transmitter to the receiver. The Routing and Wavelength Assignment problem consists in routing a set of lightpaths and assigning a wavelength to each of them. All connection requirements are known beforehand and one seeks to minimize the total number of wavelengths used for routing these connections, so as that two lightpaths sharing a common link use different wavelengths. In this work, we propose a new heuristic in which min-RWA is solved by a combined approach involving the computation of alternative routes for the lightpaths, followed by the solution of a Parttion Coloring Problem (PCP). Given a graph where the vertex set is partitioned in disjoint susets, PCP consists in selecting and coloring only one vertex in each subset, so as that every two adjacent colored nodes have different colors and the total number of colors used is minimum. We present and propose new heuristics for PCP and min-RWA. Computational experiments are reported comparing the new heuristics and those which already appeared in the literature.

[pt] Redes ópticas convencionais exigem conversão eletro-óptica em cada nó para roteamento adequado dos pacotes. Adicionalmente, recursos de gerenciamento relevantes são requisitados para auxiliar o roteamento. Neste trabalho, inteligência e funcionalidade são introduzidas na camada física de redes ópticas com topologia em malha de modo a prover um esquema eficiente de roteamento de portadoras ópticas e endereçamento de pacotes. No arranjo apresentado ocorre que: (a) nenhuma conversão optoeletrônica (O/E/O) torna-se necessária, exceto nos nós fonte e destinação; (b). recursos de gerenciamento são praticamente dispensados na camada física. Ao representar a rede por grafos, critérios de custo mínimo são atingidos. Em seguida, utilizam-se algoritmos que, em consonância com os custos mínimos, levam ao roteamento. A conectividade desejada é então introduzida, com os algoritmos seguindo a técnica de reutilização de capacidade dentro um mesmo comprimento de onda. Desta forma, os caminhos de luz são determinados englobando todos os pares de nós da rede. Chamamos este arranjo de SWRA (Smart Wavelength Routing Assignment) dado que cada portadora segue de forma passiva seu exato caminho na rede. A implicação é a sensível redução nos custos, tanto pelo lado dos conversores O/E/O, bem como pelo lado do gerenciamento da rede. Demonstra-se que este arranjo pode estar sujeito a colisão de dados em uma mesma portadora. Uma solução é apresentada pela introdução de buffers elétricos de baixo custo, dimensionados através de ferramentas estatísticas. / [en] In conventional optical networks, optoelectronic conversions are needed in each node for the sake of a proper packet routing. Simultaneously, intensive managing resources should be allocated to accomplish the routing task. The correct introduction of intelligence and functionality within the network physical layer may lead to some advantages over conventional networks. Two advantages are worthwhile be mentioning (a)-no optoelectronic conversions (O/E/O) are needed, except for the source and destination nodes, and (b)-management resources are practically unnecessary within the physical layer. As the network uses a graph representation, it is possible to reach minimal cost criteria. Next, coping with the minimal cost, suitable algorithms are used for proper wavelength routing. The desired connectivity is introduced, and the algorithms will lead to the technique of capacity reuse within the wavelength. In this way, light-paths are obtained, linking all network node pairs. We called this arrangement as SWRA (Smart Wavelength Routing Assignment), since within the network each wavelength follows its precise path in a passive way. The result appears as a significant cost reduction, which reflects the lack of O/E/O converters and on the use of less management gear. However, this arrangement may suffer occasional data collision within any wavelength. Hence, a solution to avoid this impairment is presented and described, using low-cost electric buffers. Additionally, the statistical evaluation of those buffers is supplied. / [es] Redes ópticas convencionales exigen conversión eletro- óptica en cada nodo para un adequado ruteamiento de los paquetes. Adicionalmente, se necesitan recursos relevantes de gerenciamiento para auxiliar el ruteamiento. En este trabajo, inteligencia y funcionalidad son introducidas en la camada física de redes ópticas con topología en malla a fin de proporcionar un esquema eficiente de roteamiento de portadoras ópticas y direccionamiento de paquetes. En el arreglo presentado sucede que: (a) no es necesaria ninguna conversión optoeletrónica (O/E/O), excepto en los nodos fuente y destino; (b). recursos de gerenciamiento son prácticamente dispensados en la camada física. Al representar la rede por grafos, es posible alcanzar criterios de costo mínimo. Enseguida, se utilizan algoritmos que, en consonancia con los costos mínimos, conducen al roteamiento. La conectividad deseada se introduce con los algoritmos siguiendo la técnica de reutilización de la capacidad dentro de la misma longitud de onda. De esta forma, los caminos de luz se determinan englobando todos los pares de nodos de la red. Este arreglo se denomina SWRA (Smart Wavelength Routing Asignment) dado que cada portadora sigue de forma pasiva su exacto camiño en la red. La implicación de este procedimento es uma sensible reducción de los costos, tanto por el lado de los conversores O/E/O, así como por el lado del gerenciamiento de la red. Se demuestra que este arreglo puede estar sujeto a colisión de dados en una misma portadora. Se presenta una solución introduciendo buffers eléctricos de bajo costo, dimensionados a través de herramientas estadísticas.