Orientador: Nelson Luis Saldanha da Fonseca / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-17T07:49:48Z (GMT). No. of bitstreams: 1 Drummond_AndreCosta_D.pdf: 3173697 bytes, checksum: 8c446932862579ce4a57c4c53cce79b7 (MD5) Previous issue date: 2010 / Resumo: 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 à falhas / Abstract: 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 algorithms / Doutorado / Doutor em Ciência da Computação

Orientadores: Nelson Luis Saldanha da Fonseca, Marcos Rogério Salvador / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-16T21:55:02Z (GMT). No. of bitstreams: 1 Figueiredo_GustavoBittencourt_D.pdf: 3834927 bytes, checksum: ec5c4028c4e9daddb1935b922f19a729 (MD5) Previous issue date: 2009 / Resumo: A demanda cada vez maior por largura de banda tem levado a implantação de uma Internet de nova geração, com backbones com alta capacidade de transmissão baseados nas tecnologia de multiplexação Wavelength Division Multiplexing (WDM). Para o eficiente transporte do tráfego da Internet, é necessário o uso de um paradigma de transmissão flexível e capaz de se adequar às flutuações do tráfego da rede. Devido a imaturidade da tecnologia de comutação de pacotes ópticos (do inglês Optical Packet Switching - OPS) e das desvantagens da comutação de circuitos ópticos (do inglês Optical Circuit Switching - OCS), a comutação de rajadas ópticas (do inglês Optical Burst Switching - OBS) é uma opção atrativa, dada a sua flexibilidade, maturidade tecnológica e eficiência. Nas redes OBS, os pacotes IP são agrupados em unidades de transmissão maiores, denominadas rajadas, cuja transmissão é precedida por um pacote de controle que sinaliza, entre outras coisas, o momento em que os recursos devem ser reservados. O processo de reserva de recursos é feito em uma via, o que indica que o transmissor não necessita aguardar confirmação por parte do receptor antes de enviar as rajadas. Se não houver recursos disponíveis no momento da transmissão, a rajada é sumariamente descartada. O fato do transmissor não esperar confirmação por parte do receptor para a transmissão das rajadas, implica na necessidade de um dimensionamento adequado da rede, sob pena de alta probabilidade de bloqueio. Nesta tese, são propostos diferentes mecanismos de controle para redes OBS que podem ser usados conjuntamente, a fim de melhorar o desempenho da rede. Esta tese apresenta, inicialmente, um estudo sobre a ocorrência de transformações nas propriedades estatísticas do tráfego submetido à redes OBS, devido ao processo de montagem de rajadas, que ocorre na borda das redes OBS. Verificou-se que a transformação do tráfego está relacionada à escala limitante do tráfego multifractal. Além disso, verificou-se que o tráfego transformado em monofractal demanda menos recursos da rede. Assim, foi proposto um método para identificação automática da escala limitante de fluxos multifractais, além de um conjunto de algoritmos de montagem capazes de induzir as transformações nas propriedades estatísticas do tráfego. Foi proposto, também, na tese, um algoritmo adaptativo para escalonamento de canais em redes OBS que aloca comprimentos de onda com menor chance de reutilização por rajadas futuras. Analisou-se também, nesta tese, o problema de escalonamento em lote de canais em redes OBS. Foram propostos dois algoritmos ótimos: um para o caso quando as requisições que transitam pela rede não possuem diferenciação, e outro para quando a rede exige tratamento diferenciado das requisições. Além disso, foi proposta uma estratégia para a formação dos lotes que pode ser considerada uma extinção do protocolo Just Enough Time - JET. Os mecanismos propostos foram avaliados em comparação com outros existentes na literatura. Os resultados obtidos evidenciam ganhos e a adequabilidade para implementação em redes OBS, a fim de melhorar o desempenho destas redes / Abstract: The growth of the number of Internet users has led to the increase of the bandwidth demand which, consequently, led to the need of adoption of high capacity links in the Internet backbone. Moreover, a flexible switching paradigm is necessary to provide efficient transport of Internet traffic. Due to the limitations of both optical packet switching (OPS) and optical circuit switching (OCS), optical burst switching (OBS) emerged as an attractive switching choice. In OBS networks, IP packets are aggregated into larger transmission units, called bursts. The transmission of a burst follows the transmission of its associated control packet, which carries among other information, the time that bandwidth should be reserved for that burst. In OBS networks, the process of bandwidth reservation is done in one way, which means that the burst is discarded if there is not enough bandwidth for the transmission of the burst at a node when the burst arrives. Therefore, scheduling and burst assembling mechanisms should be conceived to avoid burst loss as well as to support the quality of service of applications running over an OBS network. Initially, a study on traffic transformation at the edge of the network was conducted for the derivation of efficient mechanisms. The study aimed at verifying the changes of traffic descriptors due to the assembly of packets into bursts. It was found that the cutoff time scale of multifractal traffic impacts the traffic transformation. Moreover, it was found that these transformations can lead to smaller bandwidth demands. Based on findings, an automatic method was proposed for the identification of the cutoff time scale of multifractal flows, and a set of burst assembly algorithms for inducing such transformations were introduced. Furthermore, an adaptive algorithm for channel scheduling that allocates wavelengths with small chances of being reused by future requests was proposed. Two optimal algorithms were introduced for the provisioning of differentiated services. In addition, a batch assembly strategy, which can be considered an extension of JET protocol, was created. The proposed mechanisms were evaluated in comparison with other mechanisms in the literature via simulation. Results evince that the mechanisms introduced in this thesis are effective for the improvement of OBS networks performance / Doutorado / Redes de Computadores / Doutor em Ciência da Computação