As redes de telecomunicações são responsáveis pelo envio de informação entre pontos de origem e destino. Dentre os diversos dispositivos que participam deste processo, destaca-se o sistema de roteamento, que realiza a seleção das rotas a serem percorridas pelas mensagens ao longo da rede e sua condução ao destino desejado. O avanço das tecnologias utilizadas pelas redes de telecomunicações provocou a necessidade de novos sistemas de roteamento, que sejam capazes de lidar corretamente com as diversas situações enfrentadas atualmente. Dentro deste contexto, este projeto de pesquisa desenvolveu um algoritmo de roteamento adaptativo e distribuído, resultado da integração de três estratégias de aprendizagem e da adição de alguns mecanismos extras, com o objetivo de obter um algoritmo eficiente e robusto às diversas variações das condições de operação da rede. As abordagens utilizadas foram a aprendizagem-Q, aprendizagem por reforço dual e aprendizagem baseada no comportamento coletivo de formigas. O algoritmo desenvolvido foi aplicado a duas redes de comutação de circuitos e seu desempenho foi comparado ao de dois algoritmos baseados no comportamento coletivo de formigas, que foram aplicados com sucesso ao problema de roteamento. Os experimentos conduzidos envolveram situações reais enfrentadas pelas redes, como variações dos seus padrões de tráfego, nível de carga e topologia. Além disto, foram realizados testes envolvendo a presença de ruído nas informações utilizadas para a seleção das rotas a serem percorridas pelas chamadas. O algoritmo proposto obteve melhores resultados que os demais, apresentando maior capacidade de adaptação às diversas situações consideradas. Os experimentos demonstraram que novos mecanismos de otimização devem ser anexados ao algoritmo proposto, para melhorar seu comportamento exploratório sob variações permanentes do nível de carga da rede e presença de ruído nos dados utilizados em suas tarefas. / The telecommunications networks are responsible for transmiting information between source and destination points in a fast, secure and reliable way, providing low cost and high quality services. Among the several devices that takes place on this process, there is thre routing system, which selects the routes to be traversed by the messages through the network and their forwarding to the destination desired. The advances in tecnologies used by telecommunications networks caused the necessity of new routing systems, that can work correctly with the situations faced by current telecommunications networks. Hence, this research project developed an adaptive and distributed routing algorithm, resulting of the integration of three leaming strategies and addition of some extra mechanisms, with the goal of having a robust and adaptive algorithm to the several variations on operation network conditions. The approaches chosen were Q-learning, dual reinforcement learning and learning based on collective behavior of ants. The developed algorithm was applied to two circuit-switching telecommunications networks and its performance was compared to two algorithms based on ant colony behavior, which were used with success to solve the routing problem. The experiments run comprised real situations faced by telecommunications networks, like variations on the network traffic patterns, load level and topology. Moreover, we did some tests with the presence of noise in information used to select the routes to be traversed by calls. The algorithm proposed produced better results than the others, showing higher capacity of adaptation to the several situations considered. The experiments showed that new optimization mechanisms must be added to the routing algorithm developed, to improve its exploratory behavior under permanent variations on network load level and presence of noise in data used in its tasks.

Orientadores: Maurício Ferreira Magalhães, Christian Rodolfo Esteve Rothenberg / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-23T04:19:23Z (GMT). No. of bitstreams: 1 Ambiel_LisianeMariaBannwart_M.pdf: 4602800 bytes, checksum: 2d2a0d47c7410c9fd817dde52a62472d (MD5) Previous issue date: 2013 / Resumo: As Redes Orientadas a Conteúdo (ROC) se apresentam como uma nova forma de pensar a Internet: mudam o paradigma de comunicação apresentando uma nova abordagem com base no conteúdo independente de sua localização. Esta dissertação propõe uma arquitetura de rede orientada a conteúdos no nível de enlace sem uso de qualquer esquema de endereçamento. Os Content Routers (CR) são à base desta arquitetura, responsáveis pelo armazenamento de dados e roteamento de pacotes diretamente no conteúdo. Diferente do ambiente IP, onde existe o conhecimento do endereço do provedor de conteúdo, a arquitetura proposta no nível de enlace requisita conteúdos através da inundação de mensagens de forma controlada. Um protótipo é desenvolvido para validação da arquitetura e é utilizado em alguns cenários comparando duas abordagens: IP/overlay e nível de enlace. Alguns cenários de uso da arquitetura de CRs em redes domiciliares também são avaliados. Os resultados sugerem que arquiteturas orientadas a conteúdo e sem uso do IP podem ser viáveis e interessantes para redes de menor escala, que se beneficiariam de uma arquitetura simples, sem necessidade de configuração e gerenciamento como ocorre na arquitetura TCP/IP / Abstract: Content Oriented Networking is a new way to think about networking by changing the communication paradigm to an approach where content becomes the basis in replace of network location identifiers. This thesis proposes content oriented network architecture at the link layer without the use of network addressing schemes. Content Routers (CR) are the basis for this architecture and are in charge of packet caching and routing directly on content names. Different from IP environments, where the destination address of the content source is known, the proposed linklevel architecture requests contents by controlled message flooding. The work includes a prototype implementation which is used in some scenarios comparing two approaches: IP/overlay and link layer. Scenarios using CR architecture in home networks are also evaluated. Results suggest that content oriented IP-less architecture may be interesting for small networks such as home networks that would benefit from the simplicity of such architecture, without configuration and management as required when using TCP/IP / Mestrado / Engenharia de Computação / Mestra em Engenharia Elétrica

Orientadores: André Luiz Morelato França, Paulo Morelato França / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-20T08:47:23Z (GMT). No. of bitstreams: 1 Usberti_FabioLuiz_D.pdf: 2207082 bytes, checksum: 83078a448a40f75c373b989f9af006fb (MD5) Previous issue date: 2012 / Resumo:O problema de roteamento em arcos capacitado e aberto (open capacitated arc routing problem, OCARP) é um problema de otimização combinatorial NP-difícil em que, dado um grafo não-direcionado, o objetivo consiste em encontrar um conjunto de rotas de custo mínimo para veículos com capacidade restrita que atendam a demanda de um subconjunto de arestas. O OCARP está relacionado com o problema de roteamento em arcos capacitado (capacitated arc routing problem, CARP), mas difere deste pois o OCARP não possui um nó depósito e as rotas não estão restritas a ciclos. Aplicações da literatura para o OCARP são discutidas. Uma formula ção de programação linear inteira é fornecida junto com propriedades do problema. Uma metaheurística GRASP (greedy randomized adaptive search procedure) com reconexão por caminhos (path-relinking) é proposta e comparada com outras metaheurísticas bem-sucedidas da literatura. Algumas características do GRASP são: (i) ajuste reativo de parâmetros, cujos valores são estocasticamente selecionados com viés 'aqueles valores que produziram, em média, as melhores soluções; (ii) um filtro estatístico que descarta soluções iniciais caso estas tenham baixa probabilidade de superar a melhor solução incumbente; (iii) uma busca local infactível que gera soluções de baixo custo utilizadas para explorar fronteiras factíveis/infactíveis do espaço de soluções; (iv) a reconexão por caminhos evolutiva aprimora progressivamente um conjunto de soluções de elevada qualidade (soluções elites). Testes computacionais foram conduzidos com instâncias CARP e OCARP e os resultados mostram que o GRASP é bastante competitivo, atingindo os melhores desvios entre os custos das soluções e limitantes inferiores conhecidos. Este trabalho também propõe um algoritmo exato para o OCARP que se baseia no paradigma branch-and-bound. Três limitantes inferiores são propostos e um deles utiliza o método dos subgradientes para resolver uma relaxação lagrangeana. Testes computacionais comparam o algoritmo branch-and-bound com o CPLEX resolvendo um modelo reduzido OCARP de programa ção linear inteira. Os resultados revelam que o algoritmo branch-and-bound apresentou resultados melhores que o CPLEX no que diz respeito aos desvios entre limitantes e ao número de melhores soluções / Abstract: The Open Capacitated Arc Routing Problem (OCARP) is an NP-hard combinatorial optimization problem where, given an undirected graph, the objective is to find a minimum cost set of tours that services a subset of edges with positive demand under capacity constraints. This problem is related to the Capacitated Arc Routing Problem (CARP) but differs from it since OCARP does not consider a depot, and tours are not constrained to form cycles. Applications to OCARP from literature are discussed. An integer linear programming formulation is given, followed by some properties of the problem. A Greedy Randomized Adaptive Search Procedure (GRASP) with path-relinking (PR) solution method is proposed and compared with other successful metaheuristics. Some features of this GRASP with PR are (i) reactive parameter tuning, where the metaheuristic parameters values are stochastically selected biased in favor of those values which produced the best solutions in average; (ii) a statistical filter, which discards initial solutions if they are unlikely to improve the incumbent best solution; (iii) infeasible local search, where high-quality solutions, though infeasible, are used to explore the feasible/infeasible boundaries of the solution space; (iv) evolutionary PR, a recent trend in which a pool of elite solutions is progressively improved by relinking pairs of elite solutions. Computational tests were conducted for both CARP and OCARP instances, and results reveal that the GRASP with PR is very competitive, achieving the best overall deviation from lower bounds. This work also proposes an exact algorithm for OCARP, based on the branch-and-bound paradigm. Three lower bounds are proposed, one of them uses a subgradient method to solve a Lagrangian relaxation. The computational tests compared the proposed branch-and-bound with a commercial state-of-the-art ILP solver. Results reveal that the branch-and-bound outperformed CPLEX in the overall average deviation from lower bounds / Doutorado / Automação / Doutor em Engenharia Elétrica

[pt] O problema de Roteamento de Veículos com restrição de capacidade (CVRP) é um dos problemas mais estudados em Otimização Combinatória. Sendo uma generalização imediata do conhecido problema do Caixeiro Viajante, o CVRP tem atraído a atenção dos pesquisadores mais proeminentes da área desde os anos 60. Um dos algoritmos mais importantes para a sua resolução foi proposto no início dos anos 80 quando um algoritmo utilizando uma relaxação Lagrangeana particularmente adequada provou ser bastante superior aos algoritmos contemporâneos. Este algoritmo sugeriu a utilização de técnicas de geração de colunas que, nos anos seguintes até o início dos anos 90, assumiram o rótulo de melhor algoritmo para o CVRP. Finalmente, em meados dos anos 90, algoritmos de planos de corte apresentaram resultados que convenceram a comunidade de que esta deveria ser a abordagem para resolver os problemas mais difíceis de CVRP. Esta dissertação apresenta uma revisão deste algoritmos anteriores e propõe um formulação que permite reunir o melhor deles. O algortimo resultante, que pode ser rotulado como de branch-and-cut-and-price, trabalha com um número exponencial de variáveis e restrições que definem um espaço relaxado de soluções que corresponde à interseção dos espaços de solução relaxados utilizados pelos algoritmos anteriores. Esta dissertação também descreve um implementação especial do algoritmo de programação dinâmica para resolução do problema de geração de colunas. Estratégias para fazer um branching robusto também são discutidas. Tudo isso permite construir um algoritmo que é capaz de ter uma boa performance quando aplicado a diferentes classes de instâncias. A experiência computacional mostrou que a abordagem proposta obtém limites inferiores consistentemente melhores que os dos algoritmos anteriores. Mais ainda, permite resolver em tempo hábil diferentes tipos de instâncias de até 135 vértices, incluindo 18 que foram resolvidas pela primeira vez. / [en] The Capacitated Vehicle Routing problem (CVRP) has been one of the most studied problems in the field of Combinatorial Optimization. A straight forward generalization of the popular Travelling Salesperson problem, the CVRP has drawn attention of the most prominent researchers since the early 60`s. One of the most important algorithms appeared in the early 80`s when a suitable Lagrangean relaxation algorithm has demonstrated to be far better than the contemporary ones. This algorithm suggested the use of column generation algorithms that succeeded to become the best ones in the late 80`s and early 90`s. Finally, in the mid 90`s, cutting plane methods presented results that convinced the community that this should be the approach for solving the hardest CVRP problems. This dissertation presents an overview of those early algorithms and proposes a formulation that allows uniting the best contributions of them. The resulting algorithm, labeled as a branch-and-cut-and-price algorithm, deals with exponentially many variables and constraints that define a relaxed solution space that is the intersection of the relaxed solution spaces considered in the previous algorithms. The dissertation also describes a specially devised dynamic programming algorithm to solve the column generation subproblem and discusses robust branching strategies that altogether allowed to build an algorithm that perfoms well on several different classes of instances. The computational experience has shown that the approach here proposed leads to lower bounds superior than the previous ones. Moreover, it allowed to consistently solve instances with up to 135 vertices, including 18 that were solved for the first time.

[pt] A busca pelo desenvolvimento sustentável tem como importante fator diferencial as fontes de energia renováveis. O biodiesel desponta como uma das alternativas mais relevantes, mas suas formas de obtenção no Rio de Janeiro não foram suficientemente investigadas. Este trabalho identifica a oportunidade da produção de biodiesel a partir de óleos residuais de fritura neste cenário, enfatizando os custos de transporte do óleo desde os principais produtores comerciais até a obtenção do biocombustível. O objetivo é avaliar os custos de forma a verificar a viabilidade do emprego desta alternativa. Para tanto, foram estudadas as diversas ferramentas de resolução do Problema de Roteamento de Veículos e foi proposto um algoritmo que visa à otimização dos custos. A formulação matemática utilizada baseia-se numa extensão de algoritmos clássicos, como o apresentado por Arenales et al. (2007), e nas equações desenvolvidas em Kallehauge (2006). Os resultados do modelo de roteamento, atrelados aos custos de produção, impostos e insumos, foram comparados com informações sobre a comercialização do biodiesel, comprovando sua viabilidade econômica. A consolidação dos dados obtidos aponta a produção de biodiesel a partir de óleo residual de fritura como viável, com custos logísticos equivalentes a R/tmp/aaaUFg8ya,19 por litro e custo final de R,22 por litro. / [en] The search for a sustainable development has in renewable energy sources an important differential factor. Biodiesel is one of the most important alternatives, but its obtainment forms in Rio de Janeiro have not been investigated enough. This work identifies the opportunity of biodiesel production from waste cooking oil in this scenery, emphasizing oil`s transport costs until factories, where it is possible to obtain biodiesel in its final form. The objective is to evaluate costs in order to verify viability of this alternative source of energy. Hence, this research analysed several tools for solving Vehicle Routing Problem and it proposes an algorithm that results in cost optimization. The adapted mathematic formulation is based in an extension of classic algorithms, like those presented by Arenales (2007), and in equations developed by Kallehauge (2006). The routing model results, linked to production, tributes and input costs, have been compared with information about biodiesel commercialization, verifying its economic viability. The data consolidation obtained indicates that the biodiesel production from waste cooking oil is viable, with logistic costs equal to R/tmp/aaaPLIh7a,19 per liter and final cost equal to R,22 per liter.

[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.

[pt] Uma rede móvel ad hoc consiste de uma coleção de dispositivos computacionais portáteis, equipados com uma interface de comunicação sem fio, com uma distribuição arbitrária e dinâmica no espaço, e onde cada host também serve de roteador para os demais hosts, descobrindo e mantendo rotas multi-hop entre os hosts. De uma forma geral, os protocolos para redes móveis ad hoc são mais complexos do que os protocolos para as redes fixas, devido à várias características destas redes, como por exemplo, a topologia dinâmica, a interferência mútua, o acesso compartilhado e a largura de banda restrita dos enlaces sem fio, bem como a operação com energia restrita e menor quantidade de recursos disponíveis nos hosts móveis. Um grande foco da pesquisa em redes móveis ad hoc tem sido o desenvolvimento, a análise e a comparação de protocolos de roteamento. Por isto, existe a demanda por ambientes para a prototipação rápida, a simulação e a depuração de protocolos de roteamento (e de outras camadas) para este tipo de redes. Preferencialmente estes ambientes devem ser flexíveis, ser simples de usar, e permitir definir vários níveis de abstrações para descrever as características físicas da rede móvel, tais como o padrão de mobilidade, os enlaces sem fio, consumo de energia, etc. Esta dissertação trata do projeto e implementação de um framework para a simulação de redes móveis ad hoc que visa facilitar a criação de ambientes para prototipação, teste, análise de desempenho e complexidade de protocolos para este tipo de redes. / [en] A mobile ad hoc network consists of a set of portable computational devices, equipped with a wireless communication interface, that are randomly and dynamically distributed in space, and where each host serves as a router for the other hosts by discovering and maintaining multi-hop routes among the hosts. In general, protocols for mobile ad hoc networks are more complex than equivalent protocols for static networks, due to several properties of such networks, such as its dynamic topology, the mutual interference, concurrent access and smaller communication bandwidth of the wireless links, as well as, operation with restricted amount of energy, and scarce resources of the mobile devices. A main focus of research in mobile ad hoc networks has been the development, analysis and comparison of routing protocols for such networks. Therefore, there is some demand for environments that facilitate the rapid prototyping, the simulation and the debugging of protocols at the network and other layers for such networks. These environments should preferably be flexible, easy to use, and allow for the definition of different levels of abstractions for modeling the main characteristics of the mobile network, such as the pattern of mobility, the wireless links, the energy consumption, etc. This thesis describes the design and implementation of a framework for the simulation of mobile ad hoc networks, which aims at supporting the development of concrete simulation environments for prototyping, testing and doing the complexity and performance analysis of protocols for such networks.

[pt] Os problemas de roteamento estão entre os problemas combinatórios mais difíceis de encontrar limites melhores do que os existentes ou de provar novas soluções ótimas. Nesta tese, são abordados o Capacitated Arc Routing Problem (CARP) e o Generalized Vehicle Routing Problem (GVRP). Em ambos os problemas, existe um conjunto de clientes os quais estão espalhados por um grafo dado, onde cada cliente possui uma demanda que deve ser atendida por exatamente um veículo de um conjunto de veículos idênticos. Os custos de travessia e o vértice de depósito são dados. O objetivo é encontrar rotas que coletam todas as demandas com custo mínimo, sem exceder a capacidade de nenhum veículo. No CARP, os clientes são um subconjunto de arestas, chamadas de arestas requireds, e para o GVRP, cada cliente é um subconjunto de vértices, chamado de grupo, onde cada grupo deve ser atendido visitando-se exatamente um vértice deste grupo. Além disto, vale notar que quando cada grupo possui apenas um vértice, o problema passa a ser o Capacitated Vehicle Routing Problem (CVRP). Primeiramente, são investigados métodos para melhorar os limites inferiores de instâncias de grande porte. É proposta a exploração da velocidade de uma heurística dual ascent para gerar cortes de capacidade. Em seguida, é apresentado um algoritmo de geração de colunas com um pricing eficiente para um tipo especial de rota não-elementar. O pricing proposto combina a técnica Decremental State-Space Relaxation (DSSR) com limites de complemento. Estas técnicas permitem o fortalecimento da regra de dominância entre as rotas, reduzindo drasticamente o número total de rótulos utilizados pela programação dinâmica. Finalmente, um algoritmo de branch-cut-and-price é criado o qual usa a geração de colunas e a separação de cortes previamente apresentadas. Além disto, este branch-cut-and-price é implementado usando strong branching e fixação por custo reduzido. Ao fim de cada parte, são apresentados resultados computacionais os quais avaliam a qualidade dos algoritmos propostos, os quais obtém novos limites inferiores para um grande número de instâncias do CARP e do GVRP. / [en] Routing problems stand among the hardest combinatorial problems to find high quality bounds or to prove new optimal solutions. In this thesis, we tackle the Capacitated Arc Routing Problem (CARP) and the Generalized Vehicle Routing Problem (GVRP). For both problems, there are a set of customers spread over a given graph, where each customer has a demand which must be serviced by exactly one vehicle from a set of identical vehicles. The traversal costs and a depot vertex are given. The objective is to find routes that collect all the demands, without exceeding the capacity of any vehicle, at minimum cost. For the CARP, the customers are a subset of edges, called the required edges, and for the GVRP, each customer is a subset of vertices, called clusters, where each cluster must be serviced by visiting exactly one vertex of it. Furthermore, it is noteworthy that when every cluster contains just a single vertex, the problem is the Capacitated Vehicle Routing Problem (CVRP). Firstly, we investigate methods to improve lower bounds for large scale instances. We propose to explore the speed of a new dual ascent heuristic to generate capacity cuts. The quality of the cuts found is next improved with a new exact separation which is used in the linear program resolution that follows the dual heuristic. Following, we present a column generation algorithm with an efficient pricing for a special kind of non-elementary routes. The proposed pricing algorithm combines Decremental State-Space Relaxation(DSSR) technique with completion bounds. These techniques allow the strengthening of the domination rule between routes, drastically reducing the total number of labels used during the dynamic programming. Finally, we devise a branch-cut-and-price algorithm which uses the previously presented column generation and cut separation. Moreover, this branch-cutand- price is implemented using strong branching and reduced cost fixing. At the end of each part, we present computational experiments which evaluate the quality of the proposed algorithms and show new best lower bounds for a large number of CARP and GVRP instances.

Orientador: Nelson Luis Saldanha da Fonseca / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-27T12:19:41Z (GMT). No. of bitstreams: 1 Santi_Julianade_D.pdf: 2864937 bytes, checksum: 7526ed7e2e57bec4e7361a8c0f9f8b47 (MD5) Previous issue date: 2015 / Resumo: As redes ópticas com multiplexação por comprimento de onda (WDM) permitem a transmissão de grande volume de dados através de múltiplos canais com capacidade de transmissão de vários Gbps. Entretanto, as demandas por banda passante dos fluxos IPs são significativamente inferior à capacidade disponível em cada canal WDM. Para lidar com esta disparidade e utilizar de forma eficiente a banda disponível, é necessária a transmissão simultânea de vários fluxos em um caminho óptico, chamado de agregação de tráfego. Especificações de qualidade de serviço dos fluxos devem, também, ser consideradas nas decisões de agregação de tráfego. Ademais, aplicações emergentes podem demandar largura de banda superior à capacidade de um comprimento de onda, sendo necessário utilizar vários caminhos ópticos (roteamento multicaminho) para provisionar tais fluxos. Além disso, a expansão da infraestrutura e utilização das redes WDM têm elevado o consumo de energia, causando impactos econômicos e ambientais. Estas questões têm desafiado e motivado pesquisadores a encontrar alternativas para aprimorar as transmissões nas redes ópticas WDM, o que inclui a agregação de tráfego e o roteamento multicaminho. Nesta tese, abordam-se diversos problemas em agregação de tráfego e roteamento multicaminho em redes ópticas WDM. Foram desenvolvidos e validados algoritmos pelo menos tão eficientes quanto algoritmos existentes na literatura. Propõe-se um algoritmo de agregação de tráfego que considera a duração das conexões e a banda disponível. Para atender demandas superiores à capacidade de um comprimento de onda, desenvolveu-se um algoritmo que considera a duração do fluxo, divide-o em subfluxos e os transmite em múltiplos canais. Para este algoritmo, foi proposta uma versão aproximada visando reduzir o tempo de resolução do problema. Introduziu-se, também, um algoritmo que indica a postergação do momento de início da transmissão das conexões a fim de agregar lotes de conexões. Para reduzir o consumo de energia, foram desenvolvidas duas estratégias, de roteamento multicaminho e reroteamento, que levam em consideração o consumo de energia das operações envolvidas na transmissão da conexão / Abstract: The wavelength division multiplexing (WDM) optical networks allow the transmission of large volume of data through multiple channels with severals Gbps of transmission capacity. However, the demand for bandwidth of IP flows are significantly lower than the available capacity in each WDM channel. To address this disparity and make efficient use of the available bandwidth, it is necessary to transmit simultaneously multiple streams in lightpath, called traffic grooming. The quality of service specifications inherent to connections should also be considered in the traffic aggregation decisions. Moreover, emerging applications can request bandwidth greater than the capacity of a wavelength, which require several lightpaths (multipath routing) to establish such connections. In addition, infrastructure expansion and use of WDM networks have increased the energy consumption, leading to economic and environmental concerns. These issues have challenged and motivated researchers to find alternatives to enhance transmissions in WDM optical networks, which includes the traffic grooming and multipath routing. This thesis addresses several problems in traffic grooming and multipath routing in WDM optical networks. For each problem algorithms were developed and validated that are at least as efficient as existing algorithms in the literature. It was proposed a traffic grooming algorithm that considers the duration of connections and the available bandwidth along the path. In order to establish connections demanding bandwidth greater than the capacity of a wavelength, it was proposed an algorithm that considers the duration of a connection and divides this connection in to substreams and transmits them on multiple wavelengths. For this algorithm, it was proposed an approximate version to reduce the run time. Moreover, it was introduced an algorithm which postpones the time to establish the connections and aggregates batch connections. In order to reduce the energy consumption, two strategies, multipath routing and rerouting, were developed that take into account the energy consumption of each operation involved in the connection transmission / Doutorado / Ciência da Computação / Doutora em Ciência da Computação

Orientador: Nelson Luis Saldanha da Fonseca / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-27T20:17:10Z (GMT). No. of bitstreams: 1 Moura_PedroMesquita_M.pdf: 2113385 bytes, checksum: 1ba529be35f0f2fbcb95f91c01acfa29 (MD5) Previous issue date: 2015 / Resumo: As redes ópticas com multiplexação por comprimento de onda empregam uma grade fixa de divisão do espectro, dividindo-o em grandes faixas com alta capacidade de transmissão. Apesar de este esquema atingir altas velocidades de até 100Gb/s atualmente, a demanda de tráfego está cada vez maior e novas soluções são propostas como futuro das redes ópticas. A divisão do espectro em grandes faixas pode gerar problemas de falta de flexibilidade, onde requisições com baixas demandas de tráfego subutilizam comprimentos de onda. Nesse contexto as redes ópticas elásticas emergem, buscando flexibilizar a alocação do espectro utilizando alta granularidade na divisão do espectro, de modo que as conexões utilizem tipicamente vários slots, que são a unidade de alocação de redes ópticas elásticas. Utilizando-se da tecnologia de Multiplexação por Divisão de Frequências Ortogonais (OFDM), é possível fazer com que os slots adjacentes se sobreponham ortogonalmente, sem interferência, atingindo alta eficiência de utilização do espectro. O roteamento e alocação de espectro surge neste contexto com o objetivo de alocar rotas nas redes ópticas elásticas, necessitando caminhos na rede que possuam espectro suficiente para acomodar a demanda de tráfego, e a fim de manter o sinal no domínio óptico e evitar a custosa operação de conversão opto eletrônica, é necessário manter a mesma porção do espectro alocada em todos os enlaces do caminho, problema denominado de restrição de continuidade do espectro. Os slots devem ser também adjacentes para que estes se sobreponham utilizando OFDM, problema chamado de restrição de contiguidade do espectro. Esta dissertação investiga o problema roteamento e alocação de espectro e propõe algoritmos que melhoram características da rede, como qualidade de serviço, custo operacional e eficiência energética / Abstract: Wavelength division multiplexing optical networks employ fixed grid for spectrum, with high capacity transmission slots. Although this division allows high speeds of up to 100Gbps nowadays, the traffic demand grows each year and new solutions are needed in optical networks. The high capacity fixed grid can produce problems like the sub utilization of wavelengths by requests with lower traffic demand than their capacity. In this context the elastic optical networks emerged, allowing flexible division of spectrum, in a way that connections allocate several slots, the unit of spectrum of elastic optical networks. Together with Orthogonal Frequency Division Multiplexing (OFDM), it is possible to orthogonally overlap adjacent slots, without interference, achieving higher spectrum efficiency. The routing and spectrum assignment problem aims to allocate routes and spectrum in elastic optical networks, finding for paths with enough spectrum to accommodate the traffic demand. In order to avoid the costly optoelectronic signal conversion, it is necessary to allocate the same portion of spectrum in each link of the path, problem called spectrum continuity constraint. The slots must also be allocated contiguously, in order to the overlapping with OFDM be effective, problem called spectrum contiguity constraint. This work investigate the routing and spectrum assignment problem and proposes algorithms to improve network characteristics such as quality of service, operational expenditure and energy efficiency / Mestrado / Ciência da Computação / Mestre em Ciência da Computação