[en] HEURISTICS FOR ROUTING AND WAVELENGTH ASSIGNMENT BY PARTITION COLORING

THIAGO FERREIRA DE NORONHA

[pt] HEURÍSTICAS PARA ROTEAMENTO E ATRIBUIÇÃO MÍNIMA DE COMPRIMENTOS DE ONDA POR COLORAÇÃO DE PARTIÇÕES

dc.contributor	CELSO DA CRUZ CARNEIRO RIBEIRO
dc.contributor	CELSO DA CRUZ CARNEIRO RIBEIRO
dc.creator	THIAGO FERREIRA DE NORONHA
dc.date	2004-07-22
dc.date.accessioned	2022-09-21T21:43:59Z
dc.date.available	2022-09-21T21:43:59Z
dc.identifier	https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=5215@1
dc.identifier	https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=5215@2
dc.identifier	http://doi.org/10.17771/PUCRio.acad.5215
dc.identifier.uri	https://hdl.handle.net/20.500.12032/42795
dc.description	[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.
dc.description	[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.
dc.language	pt
dc.publisher	MAXWELL
dc.subject	[pt] COMPRIMENTOS DE ONDA
dc.subject	[pt] ROTEAMENTO
dc.subject	[pt] COLORACAO DE PARTICOES
dc.subject	[pt] REDES OPTICAS
dc.subject	[pt] METAEURISTICA
dc.subject	[pt] OTIMIZACAO COMBINATORIA
dc.subject	[en] WAVELENGTH
dc.subject	[en] ROUTING
dc.subject	[en] PARTITION COLORING
dc.subject	[en] OPTICAL NETWORKS
dc.subject	[en] METAHEURISTIC
dc.subject	[en] COMBINATORIAL OPTIMIZATION
dc.title	[en] HEURISTICS FOR ROUTING AND WAVELENGTH ASSIGNMENT BY PARTITION COLORING
dc.title	[pt] HEURÍSTICAS PARA ROTEAMENTO E ATRIBUIÇÃO MÍNIMA DE COMPRIMENTOS DE ONDA POR COLORAÇÃO DE PARTIÇÕES
dc.type	TEXTO

Files in this item

Files	Size	Format	View
There are no files associated with this item.

This item appears in the following Collection(s)

Documentos - PUC-RIO

Show simple item record