Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2017. / Submitted by Priscilla Sousa (priscillasousa@bce.unb.br) on 2017-10-09T13:02:47Z No. of bitstreams: 1 2017_AlexandreLucchesiAlencar.pdf: 1212791 bytes, checksum: d649afa5d4e58b36d30548964058710d (MD5) / Approved for entry into archive by Raquel Viana (raquelviana@bce.unb.br) on 2017-10-09T16:17:08Z (GMT) No. of bitstreams: 1 2017_AlexandreLucchesiAlencar.pdf: 1212791 bytes, checksum: d649afa5d4e58b36d30548964058710d (MD5) / Made available in DSpace on 2017-10-09T16:17:08Z (GMT). No. of bitstreams: 1 2017_AlexandreLucchesiAlencar.pdf: 1212791 bytes, checksum: d649afa5d4e58b36d30548964058710d (MD5) Previous issue date: 2017-10-09 / Roteadores em software são uma solução promissora para lidar com o encaminhamento de pacotes devido ao seu bom custo-benefício e flexibilidade. Contudo, é desafiador o desenvolvimento de roteadores em software capazes de atingir as taxas de encaminhamento de pacotes necessárias. O uso de sistemas e técnicas de computação paralela pode ser uma abordagem viável para melhorar o desempenho dessas soluções. A fase de consulta IP constitui uma operação central no encaminhamento de pacotes, que é implementada através de um algoritmo de Casamento de Maior Prefixo (CMP). Assim, este trabalho propõe e avalia o uso de técnicas e processadores paralelos no desenvolvimento de um algoritmo otimizado que emprega filtros de Bloom (BFs) e tabelas hash para a execução de consultas IP. Especificamente, tem-se como alvo a implementação desse algoritmo no coprocessador many-core Intel® Xeon Phi™ (Intel Phi), mas também avalia-se o seu desempenho em CPUs multi-core e em um modelo de execução cooperativa que usa ambos os processadores com várias otimizações. Os resultados experimentais mostram que foi possível atingir altas taxas de consultas IP — até 182,7 Mlps (milhões de pacotes por segundo) ou 119,9 Gbps para pacotes IPv6 de 84B — em um único Intel Phi. Este desempenho indica que o Intel Phi é uma plataforma promissora para a implantação de algoritmos de consultas IP. Além disso, comparou-se o desempenho do algoritmo BFs com uma abordagem eficiente baseada na Multi-Index Hybrid Trie (MIHT), na qual o algoritmo BFs foi até 5,39x mais rápido. Esta comparação mostra que o algoritmo sequencial mais eficiente pode não ser a melhor opção em uma configuração paralela. Alternativamente, é necessário avaliar as características dos processadores, as demandas de computação/dados dos algoritmos e as estruturas de dados empregadas para analisar como os algoritmos podem se beneficiar de um dispositivo de computação paralelo, potenciais limitações na escalabilidade e oportunidades de otimização. Estas descobertas também são importantes para novos esforços no desenvolvimento de algoritmos nessa área, os quais têm sido, em sua maioria, focados em soluções sequenciais. / Software routers are a promising solution to deal with packet forwarding because of their good cost benefit and flexibility. However, it is challenging to develop software routers that can attain the required packet forwarding rates. The use of parallel computing systems and techniques may be a viable approach to improve the performance of these solutions. The IP lookup phase is a core operation in packet forwarding, which is implemented via a Longest Prefix Matching (LPM) algorithm to find the next hop address for every input packet. Therefore, this work proposes and evaluates the use of parallel processors and techniques in the development of an optimized algorithm that employs Bloom filters (BFs) and hash tables to the IP lookup problem. Specifically, we target the implementation on the Intel® Xeon Phi™ (Intel Phi) many-core coprocessor, but we also evaluate its performance on multi-core CPUs and on a cooperative execution model that uses both processors with several optimizations. The experimental results show that we were able to attain high IP lookup throughputs — up to 182.7 Mlps (million packets per second) or 119.9 Gbps for 84B IPv6 packets — on a single Intel Phi. This performance indicates that the Intel Phi is a very promising platform for deployment of IP lookup algorithms. We have also compared the BFs algorithm to an efficient approach based on the Multi-Index Hybrid Trie (MIHT) in which the BFs algorithm was up to 5.39x faster. This comparison shows that the most efficient sequential algorithm may not be the best option in a parallel setting. Instead, it is necessary to evaluate the processors characteristics, algorithms compute/data demands, and data structures employed to analyze how the algorithms will benefit from parallel computing devices, potential limitations on scalability and opportunities for optimizations. These findings are also important to new efforts in algorithmic developments in the topic, which have been highly focused on sequential solutions.

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2015. / Submitted by Fernanda Percia França (fernandafranca@bce.unb.br) on 2016-03-08T20:32:53Z No. of bitstreams: 1 2015_HenriqueDominguesGarcia.pdf: 3010082 bytes, checksum: e6564015e1b7fbb36c0f633990fb3005 (MD5) / Approved for entry into archive by Raquel Viana(raquelviana@bce.unb.br) on 2016-03-31T10:48:59Z (GMT) No. of bitstreams: 1 2015_HenriqueDominguesGarcia.pdf: 3010082 bytes, checksum: e6564015e1b7fbb36c0f633990fb3005 (MD5) / Made available in DSpace on 2016-03-31T10:48:59Z (GMT). No. of bitstreams: 1 2015_HenriqueDominguesGarcia.pdf: 3010082 bytes, checksum: e6564015e1b7fbb36c0f633990fb3005 (MD5) / Este trabalho apresenta uma metodologia de engenharia de tráfego que tem como objetivo otimizar o custo do enlace de protocolos tradicionais de roteamento tais como o OSPF (Open Shortest Path First), a partir da otimização de métricas baseadas na utilização e na característica do tráfego do enlace. Foi utilizado um modelo de programação linear extraído da curva do atraso máximo do enlace calculado com o FEP (Fractal Envelope Process). Os resultados mostram que para o tráfego de vídeo que possui um alto grau de autossimilaridade, é necessário preservar a utilização média do enlace abaixo de 25\% para obter valores de atrasos compatíveis com os requerimentos de QoS (Quality of Service) da aplicação. / This paper presents a traffic engineering methodology that aims to optimize the link cost of traditional routing protocols such as OSPF (Open Shortest Path First) using link metrics based on the link load and traffic characteristics. We propose a linear programming model based on the maximum delay curve of the link calculated by the FEP (Fractal Envelope Process). The results show that for video traffic that has a high degree of self-similarity, the average link utilization must be below 25% to archive delay values compatible with the QoS requirements (Quality of Service) of the application.

Dissertação (mestrado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Elétrica, 2008. / Submitted by Diogo Trindade Fóis (diogo_fois@hotmail.com) on 2009-09-17T12:39:08Z No. of bitstreams: 1 Dissert_DinoMacedoAmaral.pdf: 1248768 bytes, checksum: f9bc5c6948f5d042bdd1a3265315120b (MD5) / Approved for entry into archive by Luanna Maia(luanna@bce.unb.br) on 2009-10-19T14:18:24Z (GMT) No. of bitstreams: 1 Dissert_DinoMacedoAmaral.pdf: 1248768 bytes, checksum: f9bc5c6948f5d042bdd1a3265315120b (MD5) / Made available in DSpace on 2009-10-19T14:18:24Z (GMT). No. of bitstreams: 1 Dissert_DinoMacedoAmaral.pdf: 1248768 bytes, checksum: f9bc5c6948f5d042bdd1a3265315120b (MD5) Previous issue date: 2008-02-22 / A necessidade de atender as demandas existentes no mercado de microeletrônica tem levado os projetistas a compactar um grande número de blocos IP’s, o que produz uma diversidade enorme em suas funcionalidades. Do ponto de vista prático, a distribuição destes blocos IP’s torna-se um problema devido aos problemas físicos como alta impiedância devido ao número de fios que os interligam, o gasto de energia para manter todos os blocos IP’s se comunicando, e uma ocupação otimizado da área do chip. Para ajudar os projetistas de SoC, os conceitos usado em rede de computadores têm sido a principal fonte para apontar a uma solução possível para estas situações. Este documento mostra os resultados apresentados usando o gpNoCsim [18] e o modelo analítico mostrado em [12], o que pode ajudar os projetistas de NoC encontrar possíveis gargalos quando for trabalhar com NoCs. ________________________________________________________________________________________ ABSTRACT / The need to meet the existing demands in the microeletronic market has prompted designers to compact a big number of IP blocks in a small silicon area. From the pratical point of view, the distribuition of these IP blocks becomes a issue due to physical issues like high impedance caused by the number of wires that interconncet them, the power consupmtion to keep all IP blocks comunicating. An optimized occupation of the whole space used by the chip. In order to help the SoC designers , the concepts used in networking have been the main source to point out a possible solution for these situations. This paper shows the results of a benchmarck using gpNoCsim [18], which can help the NoC designers to find the bottlenecks when working with NoCs.

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2015. / Submitted by Fernanda Percia França (fernandafranca@bce.unb.br) on 2016-03-21T17:45:15Z No. of bitstreams: 1 2015_LucasRodriguesCosta.pdf: 3317653 bytes, checksum: 94d1e437b44e868ef2c3bc67bf4c7f61 (MD5) / Approved for entry into archive by Raquel Viana(raquelviana@bce.unb.br) on 2016-03-28T19:21:14Z (GMT) No. of bitstreams: 1 2015_LucasRodriguesCosta.pdf: 3317653 bytes, checksum: 94d1e437b44e868ef2c3bc67bf4c7f61 (MD5) / Made available in DSpace on 2016-03-28T19:21:14Z (GMT). No. of bitstreams: 1 2015_LucasRodriguesCosta.pdf: 3317653 bytes, checksum: 94d1e437b44e868ef2c3bc67bf4c7f61 (MD5) / A tecnologia de redes ópticas elásticas surge como uma solução promissora para o futuro da transmissão óptica de alta velocidade. Suas características proporcionam uma flexibilidade e escalabilidade superior na alocação de espectro para os diversos serviços emergentes acompanhando a crescente demanda do tráfego da Internet. Em redes ópticas elásticas as demandas de tráfego são transmitidas usando um número arbitrário de subportadoras OFDM, e um nível de modulação adequado, levando em conta a distância de transmissão. Esta dissertação descreve as principais características do paradigma de redes ópticas elásticas, apresenta as principais linhas de pesquisa encontradas na literatura e propõe soluções para o problema de roteamento e atribuição de espectro com modulação adaptativa (Routing, Modulation Level, and Spectrum Allocation - RMLSA) que visam potencializar o uso da modulação adaptativa com roteamento em múltiplos saltos para o cenário dinâmico de tráfego. Dentre as soluções propostas destacam-se (i) uma abordagem RMLSA que procura realizar a maior quantidade de agregação de tráfego possível usando os níveis de modulação mais altos da rede e (ii) a criação de um esquema de modulação adaptativa, acoplável a qualquer algoritmo RSA, que viabiliza o roteamento do tráfego através de múltiplos saltos na topologia virtual. Os resultados obtidos apresentam uma redução significativa na taxa de bloqueio para diversas soluções RSA da literatura sem comprometer a utilização dos recursos na rede. / The elastic optical networks technology emerges as a promising solution for the future of high-speed optical transmission. It provides flexibility and superior capability in spectrum allocation for the various emerging services along the increasing demand of Internet traffic. In Elastic Optical Networks the traffic demands are transmitted using an arbitrary number of OFDM sub carriers, and a suitable modulation level, taking into consideration the transmission distance. This dissertation describes the main characteristics of the Elastic Optical Network paradigm, presents the main areas of research in the literature and proposes solutions that solve the Routing, Level Modulation, and Spectrum Allocation (RMLSA) problem which seeks enhancing the use of adaptive modulation with multihop routing in the dynamic traffic scenario. Among the solutions developed stands out (i) an RMLSA approach that seeks to achieve the greatest possible amount of traffic grooming using the highest modulation levels in network and (ii) the creation of an adaptive modulation scheme, that work along with any RSA algorithm, that enables the multihop routing traffic. The results showed an important reduction in blocking rate for various RSA approaches from the literature without compromising the use of resources in the network.