CAPES; CNPq / Este trabalho apresenta a implementação de um modelo do TCP-Reno, bem como uma técnica de modelamento de rede, detalhadamente apresentada, com o objetivo de mensurar a rajada e a vazão das conexões TCP compartilhadas em um roteador congestionado. Isso se faz necessário, para permitir estudar e prever o comportamento de uma rede. A validação do modelo implementado foi realizada por meio de comparações com resultados de simulações baseadas no software Network Simulator (NS-2). Posteriormente a apresentação do modelo, e como objetivo principal deste trabalho, foi feita uma análise detalhada de uma modificação no protocolo que implementa QoS (Quality of Service) na camada de transporte. Essa modificação no protocolo, denominada de TCP TS- Prio, implementa uma diferenciação no tamanho da janela deslizante, através de atribuição de prioridade para determinados fluxos. Essa análise revela as qualidades e limitações da utilização desse protocolo em cenários diferentes do original do TCP TS-Prio, onde o autor focava principalmente no comportamento dinâmico do protocolo. Como resultado do trabalho chega-se a conclusão de que o TCP TS-Prio é capaz de oferecer diferenciação de serviço, porém isto depende diretamente do estado de congestionamento da rede em questão. / This work presents the implementation of a model for the TCP-Reno protocol, as well as a detailed technique for modeling the network, with the purpose of measuring the burstiness and the throughput of TCP traffic in a congested shared router. This is necessary to study and to predict the behavior of a data network. The model was validated by comparing its results to simulations carried out with specialized simulation software, namely the Network Simulator (NS-2). After presenting the model and the main goals of this work, a detailed analysis of a modi- fied protocol that implements QoS (Quality of Service) in the transport layer was done. This protocol called TCP TS-Prio, implements a differentiation in the size of the sliding window, thus giving priorities to certain flows. This analysis is needed to reveal qualities and limitations of this protocol in several network environments (scenarios), because in the original work on TCP TS-Prio the author focused mainly on the dynamic behavior of the Protocol. We then conclude that TCP TS-Prio is able to offer service differentiation, but this depends directly on the network congestion degree. / 5000

CAPES; CNPq / Este trabalho apresenta a implementação de um modelo do TCP-Reno, bem como uma técnica de modelamento de rede, detalhadamente apresentada, com o objetivo de mensurar a rajada e a vazão das conexões TCP compartilhadas em um roteador congestionado. Isso se faz necessário, para permitir estudar e prever o comportamento de uma rede. A validação do modelo implementado foi realizada por meio de comparações com resultados de simulações baseadas no software Network Simulator (NS-2). Posteriormente a apresentação do modelo, e como objetivo principal deste trabalho, foi feita uma análise detalhada de uma modificação no protocolo que implementa QoS (Quality of Service) na camada de transporte. Essa modificação no protocolo, denominada de TCP TS- Prio, implementa uma diferenciação no tamanho da janela deslizante, através de atribuição de prioridade para determinados fluxos. Essa análise revela as qualidades e limitações da utilização desse protocolo em cenários diferentes do original do TCP TS-Prio, onde o autor focava principalmente no comportamento dinâmico do protocolo. Como resultado do trabalho chega-se a conclusão de que o TCP TS-Prio é capaz de oferecer diferenciação de serviço, porém isto depende diretamente do estado de congestionamento da rede em questão. / This work presents the implementation of a model for the TCP-Reno protocol, as well as a detailed technique for modeling the network, with the purpose of measuring the burstiness and the throughput of TCP traffic in a congested shared router. This is necessary to study and to predict the behavior of a data network. The model was validated by comparing its results to simulations carried out with specialized simulation software, namely the Network Simulator (NS-2). After presenting the model and the main goals of this work, a detailed analysis of a modi- fied protocol that implements QoS (Quality of Service) in the transport layer was done. This protocol called TCP TS-Prio, implements a differentiation in the size of the sliding window, thus giving priorities to certain flows. This analysis is needed to reveal qualities and limitations of this protocol in several network environments (scenarios), because in the original work on TCP TS-Prio the author focused mainly on the dynamic behavior of the Protocol. We then conclude that TCP TS-Prio is able to offer service differentiation, but this depends directly on the network congestion degree. / 5000

Um dos mais importantes elementos que compõem uma rede de telecomunicações é o roteador. Os roteadores modernos empregam sofisticados comutadores para a transmissão de pacotes. A arquitetura de comutadores com filas de entrada exige um processo de escalonamento que estabelece a transferência de pacotes das portas de entrada às portas de saída. O desempenho do sistema depende diretamente do algoritmo de escalonamento, considerando sua vazão e complexidade. Esta dissertação realiza o levantamento teórico dos algoritmos de escalonamento mais relevantes e propõe uma abordagem de escalonamento usando algoritmos genéticos. Um simulador baseado em eventos discretos foi desenvolvido para a realização de testes de desempenho dos escalonadores estudados. O algoritmo proposto, denominado GENIUS, apresentou desempenho relevante e baixa complexidade. / One of the most important components of network telecommunications is the router. Modern routers employ input-queued crossbar switches that require sophisticated scheduling techniques for packet transmission. The architecture of switches with input queues requires an scheduling process that establishes the transfer of packets from input to output ports. The performance of router depends of the scheduling algorithm, considering its throughput and complexity. In this work we survey the most relevant theoretical scheduling algorithms and propose a scheduling approach using genetic algorithms. We developed a simulator of discrete events for testing of schedulers performance. The proposed algorithm, called GENIUS, presents relevant performance and low complexity.

Um dos mais importantes elementos que compõem uma rede de telecomunicações é o roteador. Os roteadores modernos empregam sofisticados comutadores para a transmissão de pacotes. A arquitetura de comutadores com filas de entrada exige um processo de escalonamento que estabelece a transferência de pacotes das portas de entrada às portas de saída. O desempenho do sistema depende diretamente do algoritmo de escalonamento, considerando sua vazão e complexidade. Esta dissertação realiza o levantamento teórico dos algoritmos de escalonamento mais relevantes e propõe uma abordagem de escalonamento usando algoritmos genéticos. Um simulador baseado em eventos discretos foi desenvolvido para a realização de testes de desempenho dos escalonadores estudados. O algoritmo proposto, denominado GENIUS, apresentou desempenho relevante e baixa complexidade. / One of the most important components of network telecommunications is the router. Modern routers employ input-queued crossbar switches that require sophisticated scheduling techniques for packet transmission. The architecture of switches with input queues requires an scheduling process that establishes the transfer of packets from input to output ports. The performance of router depends of the scheduling algorithm, considering its throughput and complexity. In this work we survey the most relevant theoretical scheduling algorithms and propose a scheduling approach using genetic algorithms. We developed a simulator of discrete events for testing of schedulers performance. The proposed algorithm, called GENIUS, presents relevant performance and low complexity.

Fundação Araucária / O gerenciamento do tráfego na Internet tornou-se essencial devido à grande utilização de serviços em rede nos últimos anos. Assim, para executar alguns serviços que demandam um certo grau de qualidade é necessário otimizar o uso de recursos existentes. Organizações mantenedoras de backbones são responsáveis por rotear o tráfego, utilizando protocolos que encaminham dados da origem ao destino. Um dos protocolos de roteamento mais utilizados mundialmente é o Open Shortest Path First (OSPF). A qualidade das rotas oferecidas pelo protocolo OSPF depende dos pesos atribuídos pelo operador de rede às ligações (enlaces). A determinação destes pesos depende dos critérios técnicos ou econômicos considerados necessários por parte da empresa provedora de serviços telemáticos. Nesta dissertação aborda-se o problema de rotear a demanda de tráfego na rede com o objetivo de oferecer uma qualidade de serviço satisfatória por meio de uma atribuição inteligente de pesos aos enlaces. O problema de atribuição de pesos (WSP), consiste em encontrar um conjunto de pesos OSPF que otimiza o desempenho da rede. Para solução deste problema, a literatura científica apresenta algoritmos que, na sua maioria, buscam equilibrar o tráfego na rede pelo ajuste correto da carga de cada enlace. Essa dissertação visa solucionar o WSP propondo uma nova abordagem que leva em consideração a perda de pacotes em caminhos origem-destino e a sobrecarga gerada em cada enlace. Também uma formulação estendida é proposta, permitindo a obtenção de um conjunto de pesos operacionais em ambientes normais e em ambientes onde ocorrem falhas de nós. A aplicação de duas heurísticas conhecidas, Simulated Annealing e Harmony Search, a este problema permite encontrar soluções satisfatórias para os critérios de desempenho especificados. / Internet traffic management becomes essential due the large use of the Internet the past decades. Balancing the use of existing IP resources improves the performance of services. Backbone manteiners are responsible for routing data that are sent along the network links from a source to a destination host. A routing protocol is used to perform this task. One of the most commonly used internal routing protocol is OSPF (Open Shortest Path First). The quality of the routes offered by the OSPF protocol mainly depends on weights that are assigned by the network operator to the links. The determination of these weights depends on technical or economic criteria deemed necessary by the ISPs. This master dissertation addresses the routing problem aiming at providing network quality of service by optimizing the weights assigned to links. The weight setting problem (WSP) corresponds to find a set of OSPF weights that optimize network performance. To solve this problem, the literature shows algorithms that mostly seek to balance the network traffic by correctly setting link loads. This work aims at solving WSP proposing a new approach that takes into account packet losses over origin-destination paths and link overhead. Also an extended formulation is proposed, to obtain a set of operating weights in normal environments and in environments where node failures can occur. The application of two well known heuristics, Simulated Annealing and Harmony Search, to this problem allows to find satisfactory solutions to the performance criteria specified.

Esta tese apresenta um novo protocolo de roteamento voltado para as Redes Tolerantes a Atrasos que exibem comportamentos complexos e dinâmicos. O protocolo proposto chama-se Cultural GrAnt (do inglês Cultural Greedy Ant) uma vez que este utiliza um sistema híbrido composto por um Algoritmo Cultural (AC) e uma versão gulosa da meta-heurística de Otimização por Colônia de Formigas (ACO). No Cultural GrAnt, o ACO representa o espaço populacional de um AC e utiliza uma regra de transição gulosa de modo a intensificar bons caminhos já encontrados ou explorar novos caminhos através da seleção, dentre um conjunto de candidatos, dos nós encaminhadores de mensagens mais promissores. A principal motivação para o uso do ACO é tirar proveito da sua busca baseada em população de indivíduos e da adaptação da sua estrutura de aprendizado. O AC obtém informações durante o processo evolucionário e as utiliza para guiar a população e, então, acelerar o aprendizado enquanto provê soluções mais eficientes. Considerando informações de funções heurísticas, concentração de feromônio e conhecimentos armazenados no espaço de crenças do AC, o protocolo Cultural GrAnt inclui três módulos: roteamento; escalonamento; e gerenciamento de buffer. Esse é o primeiro protocolo de roteamento que emprega ACO e AC de modo a: inferir os melhores encaminhadores de mensagens através de informações oportunistas sobre a conectividade social entre os nós; determinar os melhores caminhos que uma mensagem deve seguir para eventualmente alcançar o seu destino final, enquanto limita o número de replicações e descartes de mensagens na rede; determinar a ordem de escalonamento das mensagens; e gerenciar o espaço de armazenamento do buffer dos nós. O protocolo Cultural GrAnt é comparado com os protocolos Epidêmico e PROPHET em dois cenários de mobilidade distintos: um modelo de movimento baseado em atividades, onde simula-se o dia-a-dia de pessoas em suas atividades de trabalho, lazer e descanso; e um modelo de movimento baseado em comunidades de pessoas. Os resultados de simulações obtidos através do simulador ONE mostram que em ambos os cenários, o protocolo Cultural GrAnt alcança uma taxa mais alta de entrega de mensagens, uma replicação menor de mensagens e um número menor de mensagens descartadas se comparado com os protocolos Epidêmico e PROPHET. / This work presents a new routing protocol for complex and dynamic Delay Tolerant Networks (DTN). The proposed protocol is called Cultural GrAnt (Greedy Ant), as it uses a hybrid system composed of a Cultural Algorithm and a greedy version of the Ant Colony Optimization (ACO) metaheuristic. In Cultural GrAnt, ACO represents the population space of the cultural algorithm and uses a greedy transition rule to either exploit previously found good paths or explore new paths by selecting, among a set of candidates, the most promising message forwarders. The main motivation for using ACO is to take advantage of its population-based search and adaptive learning framework. Conversely, CA gathers information during the evolutionary process and uses it to guide the population and thus accelerate learning while providing more efficient solutions. Considering information from heuristic functions, pheromone concentration, and knowledge stored in the CA belief space, the Cultural GrAnt protocol includes three modules: routing, scheduling, and buffer management. To the best of our knowledge, this is the first routing protocol that employs both ACO and CA to infer the best message forwarders using opportunistic information about social connectivity between nodes, determine the best paths a message must follow to eventually reach its destination while limiting message replications and droppings, and perform message transmission scheduling and buffer space management. Cultural GrAnt is compared to the Epidemic and PROPHET protocols in two different mobility scenarios: an activity-based movement model, which simulates the daily lives of people in their work, leisure and rest activities; and a community-based movement model. Simulation results obtained by the ONE simulator show that, in both scenarios, Cultural GrAnt achieves a higher delivery ratio, lower message replication, and fewer dropped messages than Epidemic and PROPHET.

Fundação Araucária / O gerenciamento do tráfego na Internet tornou-se essencial devido à grande utilização de serviços em rede nos últimos anos. Assim, para executar alguns serviços que demandam um certo grau de qualidade é necessário otimizar o uso de recursos existentes. Organizações mantenedoras de backbones são responsáveis por rotear o tráfego, utilizando protocolos que encaminham dados da origem ao destino. Um dos protocolos de roteamento mais utilizados mundialmente é o Open Shortest Path First (OSPF). A qualidade das rotas oferecidas pelo protocolo OSPF depende dos pesos atribuídos pelo operador de rede às ligações (enlaces). A determinação destes pesos depende dos critérios técnicos ou econômicos considerados necessários por parte da empresa provedora de serviços telemáticos. Nesta dissertação aborda-se o problema de rotear a demanda de tráfego na rede com o objetivo de oferecer uma qualidade de serviço satisfatória por meio de uma atribuição inteligente de pesos aos enlaces. O problema de atribuição de pesos (WSP), consiste em encontrar um conjunto de pesos OSPF que otimiza o desempenho da rede. Para solução deste problema, a literatura científica apresenta algoritmos que, na sua maioria, buscam equilibrar o tráfego na rede pelo ajuste correto da carga de cada enlace. Essa dissertação visa solucionar o WSP propondo uma nova abordagem que leva em consideração a perda de pacotes em caminhos origem-destino e a sobrecarga gerada em cada enlace. Também uma formulação estendida é proposta, permitindo a obtenção de um conjunto de pesos operacionais em ambientes normais e em ambientes onde ocorrem falhas de nós. A aplicação de duas heurísticas conhecidas, Simulated Annealing e Harmony Search, a este problema permite encontrar soluções satisfatórias para os critérios de desempenho especificados. / Internet traffic management becomes essential due the large use of the Internet the past decades. Balancing the use of existing IP resources improves the performance of services. Backbone manteiners are responsible for routing data that are sent along the network links from a source to a destination host. A routing protocol is used to perform this task. One of the most commonly used internal routing protocol is OSPF (Open Shortest Path First). The quality of the routes offered by the OSPF protocol mainly depends on weights that are assigned by the network operator to the links. The determination of these weights depends on technical or economic criteria deemed necessary by the ISPs. This master dissertation addresses the routing problem aiming at providing network quality of service by optimizing the weights assigned to links. The weight setting problem (WSP) corresponds to find a set of OSPF weights that optimize network performance. To solve this problem, the literature shows algorithms that mostly seek to balance the network traffic by correctly setting link loads. This work aims at solving WSP proposing a new approach that takes into account packet losses over origin-destination paths and link overhead. Also an extended formulation is proposed, to obtain a set of operating weights in normal environments and in environments where node failures can occur. The application of two well known heuristics, Simulated Annealing and Harmony Search, to this problem allows to find satisfactory solutions to the performance criteria specified.

Esta tese apresenta um novo protocolo de roteamento voltado para as Redes Tolerantes a Atrasos que exibem comportamentos complexos e dinâmicos. O protocolo proposto chama-se Cultural GrAnt (do inglês Cultural Greedy Ant) uma vez que este utiliza um sistema híbrido composto por um Algoritmo Cultural (AC) e uma versão gulosa da meta-heurística de Otimização por Colônia de Formigas (ACO). No Cultural GrAnt, o ACO representa o espaço populacional de um AC e utiliza uma regra de transição gulosa de modo a intensificar bons caminhos já encontrados ou explorar novos caminhos através da seleção, dentre um conjunto de candidatos, dos nós encaminhadores de mensagens mais promissores. A principal motivação para o uso do ACO é tirar proveito da sua busca baseada em população de indivíduos e da adaptação da sua estrutura de aprendizado. O AC obtém informações durante o processo evolucionário e as utiliza para guiar a população e, então, acelerar o aprendizado enquanto provê soluções mais eficientes. Considerando informações de funções heurísticas, concentração de feromônio e conhecimentos armazenados no espaço de crenças do AC, o protocolo Cultural GrAnt inclui três módulos: roteamento; escalonamento; e gerenciamento de buffer. Esse é o primeiro protocolo de roteamento que emprega ACO e AC de modo a: inferir os melhores encaminhadores de mensagens através de informações oportunistas sobre a conectividade social entre os nós; determinar os melhores caminhos que uma mensagem deve seguir para eventualmente alcançar o seu destino final, enquanto limita o número de replicações e descartes de mensagens na rede; determinar a ordem de escalonamento das mensagens; e gerenciar o espaço de armazenamento do buffer dos nós. O protocolo Cultural GrAnt é comparado com os protocolos Epidêmico e PROPHET em dois cenários de mobilidade distintos: um modelo de movimento baseado em atividades, onde simula-se o dia-a-dia de pessoas em suas atividades de trabalho, lazer e descanso; e um modelo de movimento baseado em comunidades de pessoas. Os resultados de simulações obtidos através do simulador ONE mostram que em ambos os cenários, o protocolo Cultural GrAnt alcança uma taxa mais alta de entrega de mensagens, uma replicação menor de mensagens e um número menor de mensagens descartadas se comparado com os protocolos Epidêmico e PROPHET. / This work presents a new routing protocol for complex and dynamic Delay Tolerant Networks (DTN). The proposed protocol is called Cultural GrAnt (Greedy Ant), as it uses a hybrid system composed of a Cultural Algorithm and a greedy version of the Ant Colony Optimization (ACO) metaheuristic. In Cultural GrAnt, ACO represents the population space of the cultural algorithm and uses a greedy transition rule to either exploit previously found good paths or explore new paths by selecting, among a set of candidates, the most promising message forwarders. The main motivation for using ACO is to take advantage of its population-based search and adaptive learning framework. Conversely, CA gathers information during the evolutionary process and uses it to guide the population and thus accelerate learning while providing more efficient solutions. Considering information from heuristic functions, pheromone concentration, and knowledge stored in the CA belief space, the Cultural GrAnt protocol includes three modules: routing, scheduling, and buffer management. To the best of our knowledge, this is the first routing protocol that employs both ACO and CA to infer the best message forwarders using opportunistic information about social connectivity between nodes, determine the best paths a message must follow to eventually reach its destination while limiting message replications and droppings, and perform message transmission scheduling and buffer space management. Cultural GrAnt is compared to the Epidemic and PROPHET protocols in two different mobility scenarios: an activity-based movement model, which simulates the daily lives of people in their work, leisure and rest activities; and a community-based movement model. Simulation results obtained by the ONE simulator show that, in both scenarios, Cultural GrAnt achieves a higher delivery ratio, lower message replication, and fewer dropped messages than Epidemic and PROPHET.