Traffic grooming in wavelenght division multiplexing optical networks

Orientador: Nelson Luis Saldanha da FonsecaTese (doutorado) - Universidade Estadual de Campinas, Instituto de ComputaçãoResumo: Em redes ópticas com multiplexação por comprimento de onda (WDM), a alocação de banda passante ocorre em múltiplos da capacidade de um comprimento de onda, que, nos dias de hoje, corresponde a 40 Gbps. No entanto, a demanda de banda passante dos fluxos em redes IP sobre WDM é da ordem de Mbps, o que é, consideravelmente inferior a capacidade de um comprimento de onda. Para a utilização eficiente da grande capacidade disponível em redes WDM, agrega-se diversos fluxos com pequena demandas de banda em caminhos ópticos compostos pelos comprimentos de onda. A referida agregação é realizada pelo mecanismo chamado agregação de tráfego (em Inglês, traffic grooming). Para a agregação, é necessário, que se defina a rota a ser utilizada para o estabelecimento de uma conexão entre pares comunicantes, bem como o comprimento de onda a ser utilizado ao longo da rota, ou seja, é necessário resolver o chamado problema de roteamento e alocação de comprimento de onda (do Inglês, routing ou wavelength assignment, usualmente abreviado por RWA). Por outro lado, aplicações emergente em e-Ciência e novas aplicações multimídia demandam banda passante superior 'a capacidade de um comprimento de onda, requerendo que o fluxo seja transmitido em vários caminhos ópticos, possivelmente por rotas distintas, o que traz novos desafios, inclusive para os mecanismos de agregação de tráfego. Esta tese investiga diversos problemas em agregação de tráfego e propõe soluções originais para os mesmos. Propõe-se solução para o problema de coloração de grafo auxiliar para a resolução do problema RWA, através da recente Teoria de Complexidade Parametrizada, a fim de se reduzir a complexidade computacional da solução, tornando-a escalável. Introduzem-se, também, algoritmos para a resolução do problema de agregação dinâmica de tráfego, que consideram, parcialmente, a topologia da rede, para se promover a escalabilidade da solução. Tais algoritmos promovem, adicionalmente, bloqueio balanceado entre os diversos pares comunicantes na rede (justiça de bloqueio). Propõem-se, por último, algoritmos para agregar tráfego quando os fluxos demandam maior quantidade de banda passante do que a capacidade de um canal, através do roteamento por múltiplos caminhos, tanto para cenários envolvendo um único domínio como para cenários envolvendo múltiplos domínios. A solução proposta, redunda em maior robustez à falhasAbstract: In wavelength division multiplexing (WDM) networks, the great discrepancy between the bandwidth demand of Internet Protocol (IP) flows (of the order of Mbps) and the bandwidth availability in one wavelength, which currently can be 40 Gbps, has motivated the adoption of techniques, called traffic grooming, for the efficient transmission of these flows. Traffic grooming aggregates flows with small bandwidth demand in a wavelength. For that, it is necessary to determine the route to be used for the establishment of a requested connection between a source and a destination as well as the wavelength to be allocated to this connection. These are determined by the solution of the so called routing and wavelength assignment problem (RWA). Moreover, the bandwidth requirement of some emerging e-Science and multimedia applications exceed the capacity of one wavelength requiring that a requested connection be established using multiple wavelengths and possibly multiple paths. In this Thesis, several issues in traffic grooming are addressed. An algorithm based on the recent Parametrized Complexity Theory is proposed for solving efficiently the graph coloring problem which is one of the steps in the solution of the RWA problem. Additionally, efficient algorithms which consider partially the topology of the network (zones) are introduced for producing balanced blocking among source destination pairs. Moreover, algorithms for providing connectivity to requests with bandwidth demand greater than the capacity of a wavelength are proposed. These algorithms use multiple paths for both requests that transverse multiple domains and those which do not. Furthermore, robustness to link failure is increased by using these algorithmsDoutoradoDoutor em Ciência da Computaçã