[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.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:5215 |
| Date | 22 July 2004 |
| Creators | THIAGO FERREIRA DE NORONHA |
| Contributors | CELSO DA CRUZ CARNEIRO RIBEIRO, CELSO DA CRUZ CARNEIRO RIBEIRO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | English |
| Type | TEXTO |
Page generated in 0.0027 seconds