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

Orientador : Paulo Licio de Geus / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-01T14:55:00Z (GMT). No. of bitstreams: 1 Hirata_Renato_M.pdf: 5857741 bytes, checksum: 8e1fa8af7605a4c06b6ef0174dc317a5 (MD5) Previous issue date: 2002 / Resumo: Com o explosivo crescimento da Web, sua popularização e sua grande importância como meio de comunicação global, cada vez mais a atenção se volta para questões de desempenho. Pelo fato de ser um serviço relativamente recente, são poucos os estudos que abordam de modo geral todos os fatores que influenciam no seu desempenho e como tais fatores estão inter-relacionados. Assim, o objetivo deste trabalho é abordar o problema de desempenho na Web como um todo, levantando e analisando todos os componentes relacionados, fornecendo embasamento teórico para o entendimento desses tópicos e apresentando suas possíveis soluções, de forma a cobrir esta lacuna na bibliografia existente. Em especial, se concentra em tópicos de software na porção servidora de sistemas de grande demanda. Como resultado, o leitor encontrará um texto único na otimização servidores de grande porte, que é um trabalho de referência e ao mesmo tempo um guia de otimização / Abstract: With the Web explosive growth, its popularization and its great importance as a way of global communication, more and more attention is devoted to its performance issues. Due to the Web being a relatively new service, very few works approach the issue of performance affecting factors in a broad sense, as well as their inter-relationship. The goal of this work is to fill that gap by enumerating and analyzing every component that affects Web performance. This is done by covering theoretical issues for a clear understanding of all topics involved and by presenting possible solutions and suggestions. The main focus of this work is on the server portion of high performance systems. As a result, the reader will find a unique text on optimizing performance of very large Web sites, that is both a reference work and a tuning guide / Mestrado / Mestre em Ciência da Computação

Capturar e analisar pacotes de dados que trafegam pelas redes são tarefas essenciais para os administradores de redes. Estas tarefas ajudam na detecção de anomalias nos sistemas e na verificação do estado atual da rede. Existem várias aplicações que desempenham este papel para o sistema operacional GNU/Linux. Estes programas também exportam informações para os usuários e outras aplicações de várias maneiras. Entretanto, não exportam estas informações de forma hierárquica. Esta pesquisa propõe uma arquitetura alternativa aos sistemas atuais. Nossa arquitetura exporta pacotes de dados em uma estrutura hierárquica de arquivos e diretórios. Além disso, por se tratar de uma arquitetura modular, filtros adicionais, desenvolvidos por terceiros, podem ser adicionados ao sistema. A arquitetura proposta acompanha uma implementação de referência: o sistema de arquivos virtuais netsfs (Network Statistics File System), que funciona em espaço de núcleo (kernel space). A arquitetura e o sistema de arquivos netsfs, propostos nesta pesquisa, apresentam um método alternativo para exibir os pacotes de redes. Os resultados mostraram uma aparente melhoria no que diz respeito à vazão da rede. / Capturing and analyzing data packets flowing across networks are essential tasks for network administrators. These tasks help to detect anomalies in the systems and check the current status of a network. There are software applications for the GNU/Linux operating system which perform such tasks. These tools also export their information to users and other applications in different ways. However, current systems do not export this information in a hierarchical manner. This research introduces an alternative architecture to current systems. Our architecture exports data packets in a hierarchical structure of directories and files. Furthermore, since this is a modular architecture, additional third-party filters can be developed and loaded into the system. The proposed architecture comes with a reference implementation: the pseudo file system netsfs (Network Statistics File System), in kernel space. The architecture and the pseudo file system netsfs, developed in this research, introduce an alternative method to display data packets. Results show an apparent improvement regarding network throughput

O controle de congestionamento padrão do TCP apresenta vários problemas; ele não consegue distinguir se o pacote foi perdido por falha no enlace ou por descarte de pacotes devido a um congestionamento de rede (se a falha foi no enlace não há necessidade de ativar os mecanismos de controle de congestionamento); e o correto ajuste de sua taxa de transmissão requer informação de perdas de pacotes. Neste trabalho é apresentado o new generalized window advertising (NGWA), que é um novo esquema de controle de congestionamento para o TCP. O NGWA traz informações da banda disponível da infraestrutura de rede para os pontos finais da conexão TCP. Seu desempenho foi comparado com TCP New Reno, RED e o TCP padrão via simulações com o software NS-3, considerando topologias de rede largamente citadas na literatura. O NGWA foi, também, implementado e testado no Linux (versão 2.6.34). O novo método demonstrou ser superior aos comparados, apresentando uma operação mais estável, melhor justiça e menor taxa de perda de pacotes, considerando o elenco de testes realizados. / The TCP congestion control mechanism in standard implementations presents several problems; he cannot distinguish if the packet was lost by link failure or by congestion in the net (if the fault was in the link there is no need to active congestion control mechanisms); and the right adjust of your transmission rate requires information from packet loss. This work presents the new generalized window advertising (NGWA), which is a new congestion control scheme for TCP. The NGWA provides information considering the available bandwidth of the network infrastructure to the endpoints of the TCP connection. Results obtained by the NGWA approach were compared with those from TCP New Reno, RED, and standard TCP (using the network simulator NS-3), considering network topologies widely cited in the literature. A NGWA Linux implementation is also presented. The new method proved to be superior when compared with the traditional approaches, presenting a more stable operation, better fairness and lower packet loss, considering the set of tests carried out.

O controle de congestionamento padrão do TCP apresenta vários problemas; ele não consegue distinguir se o pacote foi perdido por falha no enlace ou por descarte de pacotes devido a um congestionamento de rede (se a falha foi no enlace não há necessidade de ativar os mecanismos de controle de congestionamento); e o correto ajuste de sua taxa de transmissão requer informação de perdas de pacotes. Neste trabalho é apresentado o new generalized window advertising (NGWA), que é um novo esquema de controle de congestionamento para o TCP. O NGWA traz informações da banda disponível da infraestrutura de rede para os pontos finais da conexão TCP. Seu desempenho foi comparado com TCP New Reno, RED e o TCP padrão via simulações com o software NS-3, considerando topologias de rede largamente citadas na literatura. O NGWA foi, também, implementado e testado no Linux (versão 2.6.34). O novo método demonstrou ser superior aos comparados, apresentando uma operação mais estável, melhor justiça e menor taxa de perda de pacotes, considerando o elenco de testes realizados. / The TCP congestion control mechanism in standard implementations presents several problems; he cannot distinguish if the packet was lost by link failure or by congestion in the net (if the fault was in the link there is no need to active congestion control mechanisms); and the right adjust of your transmission rate requires information from packet loss. This work presents the new generalized window advertising (NGWA), which is a new congestion control scheme for TCP. The NGWA provides information considering the available bandwidth of the network infrastructure to the endpoints of the TCP connection. Results obtained by the NGWA approach were compared with those from TCP New Reno, RED, and standard TCP (using the network simulator NS-3), considering network topologies widely cited in the literature. A NGWA Linux implementation is also presented. The new method proved to be superior when compared with the traditional approaches, presenting a more stable operation, better fairness and lower packet loss, considering the set of tests carried out.