A CCG virtual system for big data application communication costs analysis

Network topology and routing are two important factors in determining the communication costs of big data applications at large scale. As for a given Cluster, Cloud, or Grid system, the network topology is fixed and static or dynamic routing protocols are preinstalled to direct the network traffic. Users cannot change them once the system is deployed. Hence, it is hard for application developers to identify the optimal network topology and routing algorithm for their applications with distinct communication patterns. In this study, we design a CCG virtual system (CCGVS), which first uses container-based virtualization to allow users to create a farm of lightweight virtual machines on a single host. Then, it uses software-defined networking (SDN) technique to control the network traffic among these virtual machines. Users can change the network topology and control the network traffic programmingly, thereby enabling application developers to evaluate their applications on the same system with different network topologies and routing algorithms. The preliminary experimental results through both synthetic big data programs and NPB benchmarks have shown that CCGVS can represent application performance variations caused by network topology and routing algorithm.

Locant: A nature inspired location service for ad hoc networks

An efficient location service is a prerequisite to any robust, effective and precise location information aided Mobile Ad Hoc Network (MANET) routing protocol. Locant, presented in this paper is a nature inspired location service which derives inspiration from the insect colony framework, and it is designed to work with a host of location information aided MANET routing protocols. Using an extensive set of simulation experiments, we have compared the performance of Locant with RLS, SLS and DLS, and found that it has comparable or better performance compared to the above three location services on most metrics and has the least overhead in terms of number of bytes transmitted per location query answered.

Design and analysis of rate aware ad hoc 802.11 networks

802.11 WLANs are characterized by high bit error rate and frequent changes in network topology. The key feature that distinguishes WLANs from wired networks is the multi-rate transmission capability, which helps to accommodate a wide range of channel conditions. This has a significant impact on higher layers such as routing and transport levels. While many WLAN products provide rate control at the hardware level to adapt to the channel conditions, some chipsets like Atheros do not have support for automatic rate control. We first present a design and implementation of an FER-based automatic rate control state machine, which utilizes the statistics available at the device driver to find the optimal rate. The results show that the proposed rate switching mechanism adapts quite fast to the channel conditions. The hop count metric used by current routing protocols has proven itself for single rate networks. But it fails to take into account other important factors in a multi-rate network environment. We propose transmission time as a better path quality metric to guide routing decisions. It incorporates the effects of contention for the channel, the air time to send the data and the asymmetry of links. In this paper, we present a new design for a multi-rate mechanism as well as a new routing metric that is responsive to the rate. We address the issues involved in using transmission time as a metric and presents a comparison of the performance of different metrics for dynamic routing.

QoS Aware Trust Metric based Framework for Wireless Sensor Networks

Wireless Sensor Networks have gained popularity due to their real time applications and low-cost nature. These networks provide solutions to scenarios that are critical, complicated and sensitive like military fields, habitat monitoring, and disaster management. The nodes in wireless sensor networks are highly resource constrained. Routing protocols are designed to make efficient utilization of the available resources in communicating a message from source to destination. In addition to the resource management, the trustworthiness of neighboring nodes or forwarding nodes and the energy level of the nodes to keep the network alive for longer duration is to be considered. This paper proposes a QoS Aware Trust Metric based Framework for Wireless Sensor Networks. The proposed framework safeguards a wireless sensor network from intruders by considering the trustworthiness of the forwarder node at every stage of multi-hop routing. Increases network lifetime by considering the energy level of the node, prevents the adversary from tracing the route from source to destination by providing path variation. The framework is built on NS2 Simulator. Experimental results show that the framework provides energy balance through establishment of trustworthy paths from the source to the destination. (C) 2015 The Authors. Published by Elsevier B.V.

Uma nova métrica para protocolos de roteamento em redes em malha sem fio.

Este trabalho propõe uma nova métrica denominada AP (Alternative Path), a ser utilizada para o cálculo de rotas em protocolos de roteamento em redes em malha sem fio. Esta métrica leva em consideração a interferência causada por nós vizinhos na escolha de uma rota para um destino. O desempenho da métrica AP é avaliado e comparado com o da métrica ETX (Expected Transmission Count) e com o da métrica número de saltos (Hop Count). As simulações realizadas mostram que a métrica AP pode propiciar desempenho superior à rede quando comparada com as outras duas métricas. A métrica AP apresenta melhor desempenho em cenários com maior diversidade de caminhos alternativos.

无线多跳网中具有网络编码意识的机会路由协议

针对现有COPE协议消极编码的问题,提出一种具有网络编码意识的机会路由协议NCAOR。该协议兼取机会路由和网络编码的优势实现高效地报文投递。在每一跳转发时,节点均选取多个冗余邻居节点构成机会节点集协助数据发送。收到报文后,机会节点利用局部拓扑知识和侦听的邻居报文接收信息判断转发报文的网络编码机会,并通过综合路径距离和编码收益的效用函数评估报文转发效能,智能设置转发响应时间。仿真结果表明,该协议相对采用最短路径路由的COPE方案具有网络吞吐量大、能耗低和节点编码机会更多的优点。

Robust, High-Speed Network Design for Large-Scale Multiprocessing

As multiprocessor system size scales upward, two important aspects of multiprocessor systems will generally get worse rather than better: (1) interprocessor communication latency will increase and (2) the probability that some component in the system will fail will increase. These problems can prevent us from realizing the potential benefits of large-scale multiprocessing. In this report we consider the problem of designing networks which simultaneously minimize communication latency while maximizing fault tolerance. Using a synergy of techniques including connection topologies, routing protocols, signalling techniques, and packaging technologies we assemble integrated, system-level solutions to this network design problem.

Extracting Location from Contact Traces

Localization is essential feature for many mobile wireless applications. Data collected from applications such as environmental monitoring, package tracking or position tracking has no meaning without knowing the location of this data. Other applications have location information as a building block for example, geographic routing protocols, data dissemination protocols and location-based services such as sensing coverage. Many of the techniques have the trade-off among many features such as deployment of special hardware, level of accuracy and computation power. In this paper, we present an algorithm that extracts location constraints from the connectivity information. Our solution, which does not require any special hardware and a small number of landmark nodes, uses two types of location constraints. The spatial constraints derive the estimated locations observing which nodes are within communication range of each other. The temporal constraints refine the areas, computed by the spatial constraints, using properties of time and space extracted from a contact trace. The intuition of the temporal constraints is to limit the possible locations that a node can be using its previous and future locations. To quantify this intuitive improvement in refine the nodes estimated areas adding temporal information, we performed simulations using synthetic and real contact traces. The results show this improvement and also the difficulties of using real traces.

Ferramenta de gestão de redes MESH

Mestrado em Engenharia Electrotécnica e de Computadores - Área de Especialização de Telecomunicações

Amostragem Adaptativa em Redes de Sensores

Uma nova área tecnológica está em crescente desenvolvimento. Esta área, denominada de internet das coisas, surge na necessidade de interligar vários objetos para uma melhoria a nível de serviços ou necessidades por parte dos utilizadores. Esta dissertação concentra-se numa área específica da tecnologia internet das coisas que é a sensorização. Esta rede de sensorização é implementada pelo projeto europeu denominado de Future Cities [1] onde se cria uma infraestrutura de investigação e validação de projetos e serviços inteligentes na cidade do Porto. O trabalho realizado nesta dissertação insere-se numa das plataformas existentes nessa rede de sensorização: a plataforma de sensores ambientais intitulada de UrbanSense. Estes sensores ambientais que estão incorporados em Data Collect Unit (DCU), também denominados por nós, medem variáveis ambientais tais como a temperatura, humidade, ozono e monóxido de carbono. No entanto, os nós têm recursos limitados em termos de energia, processamento e memória. Apesar das grandes evoluções a nível de armazenamento e de processamento, a nível energético, nomeadamente nas baterias, não existe ainda uma evolução tão notável, limitando a sua operacionalidade [2]. Esta tese foca-se, essencialmente, na melhoria do desempenho energético da rede de sensores UrbanSense. A principal contribuição é uma adaptação do protocolo de redes Ad Hoc OLSR (Optimized Link State Routing Protocol) para ser usado por nós alimentados a energia renovável, de forma a aumentar a vida útil dos nós da rede de sensorização. Com esta contribuição é possível obter um maior número de dados durante períodos de tempo mais longos, aproximadamente 10 horas relativamente às 7 horas anteriores, resultando numa maior recolha e envio dos mesmos com uma taxa superior, cerca de 500 KB/s. Existindo deste modo uma aproximação analítica dos vários parâmetros existentes na rede de sensorização. Contudo, o aumento do tempo de vida útil dos nós sensores com recurso à energia renovável, nomeadamente, energia solar, incrementa o seu peso e tamanho que limita a sua mobilidade. Com o referido acréscimo a determinar e a limitar a sua mobilidade exigindo, por isso, um planeamento prévio da sua localização. Numa primeira fase do trabalho analisou-se o consumo da DCU, visto serem estes a base na infraestrutura e comunicando entre si por WiFi ou 3G. Após uma análise dos protocolos de routing com iv suporte para parametrização energética, a escolha recaiu sobre o protocolo OLSR devido à maturidade e compatibilidade com o sistema atual da DCU, pois apesar de existirem outros protocolos, a implementação dos mesmos, não se encontram disponível como software aberto. Para a validação do trabalho realizado na presente dissertação, é realizado um ensaio prévio sem a energia renovável, para permitir caracterização de limitações do sistema. Com este ensaio, tornou-se possível verificar a compatibilidade entre os vários materiais e ajustamento de estratégias. Num segundo teste de validação é concretizado um ensaio real do sistema com 4 nós a comunicar, usando o protocolo com eficiência energética. O protocolo é avaliado em termos de aumento do tempo de vida útil do nó e da taxa de transferência. O desenvolvimento da análise e da adaptação do protocolo de rede Ad Hoc oferece uma maior longevidade em termos de tempo de vida útil, comparando ao que existe durante o processamento de envio de dados. Apesar do tempo de longevidade ser inferior, quando o parâmetro energético se encontra por omissão com o fator 3, a realização da adaptação do sistema conforme a energia, oferece uma taxa de transferência maior num período mais longo. Este é um fator favorável para a abertura de novos serviços de envio de dados em tempo real ou envio de ficheiros com um tamanho mais elevado.

Protocole de routage basé sur des passerelles mobiles pour un accès Internet dans les réseaux véhiculaires

La rapide progression des technologies sans fil au cours de ces dernières années a vu naître de nouveaux systèmes de communication dont les réseaux véhiculaires. Ces réseaux visent à intégrer les nouvelles technologies de l’information et de la communication dans le domaine automobile en vue d’améliorer la sécurité et le confort sur le réseau routier. Offrir un accès Internet aux véhicules et à leurs occupants peut sans doute aider à anticiper certains dangers sur la route tout en rendant plus agréables les déplacements à bord des véhicules. Le déploiement de ce service nécessite que des messages soient échangés entre les véhicules. Le routage constitue un élément crucial dans un réseau, car définissant la façon dont les différentes entités échangent des messages. Le routage dans les VANETS constitue un grand défi car ces derniers sont caractérisés par une forte mobilité entraînant une topologie très dynamique. Des protocoles ont été proposés pour étendre Internet aux réseaux véhiculaires. Toutefois, la plupart d’entre eux nécessitent un coût élevé de messages de contrôle pour l’établissement et le maintien des communications. Ceci a pour conséquence la saturation de la bande passante entrainant ainsi une baisse de performance du réseau. Nous proposons dans ce mémoire, un protocole de routage qui s’appuie sur des passerelles mobiles pour étendre Internet aux réseaux véhiculaires. Le protocole prend en compte la mobilité des véhicules et la charge du réseau pour l’établissement et le maintien des routes.

Métriques de routage dans les réseaux maillés sans fil

Ces dernières années, les technologies sans fil ont connu un essor fulgurant. Elles ont permis la mise en place de réseaux sans fil à hautes performances. Les réseaux maillées sans fil (RMSF) sont une nouvelle génération de réseaux sans fil qui offrent des débits élevés par rapport aux réseaux Wi-Fi (Wireless Fidelity) classiques et aux réseaux ad-hoc. Ils présentent de nombreux avantages telles que leur forte tolérance aux pannes, leur robustesse, leur faible coût etc. Les routeurs des RMSF peuvent disposer de plusieurs interfaces radio et chaque interface peut opérer sur plusieurs canaux distincts, c’est des RMSF multiples-radios, multiples-canaux. Ce type de réseau peut accroître de manière considérable les performances des RMSF. Cependant plusieurs problèmes subsistent et doivent être résolus notamment celui du routage. Le routage dans les RMSF demeure un défi majeur. Le but des protocoles de routage est de trouver les meilleures routes i.e. des routes qui maximisent les débits et minimisent les délais, lors de l’acheminement du trafic. La qualité des routes dans les RMSF peut être fortement affectée par les interférences, les collisions, les congestions etc. Alors les protocoles doivent être en mesure de détecter ces problèmes pour pouvoir en tenir compte lors de la sélection des routes. Plusieurs études ont été dédiées aux métriques et aux protocoles de routage dans les RMSF afin de maximiser les performances de celles ci. Mais la plupart ne prennent pas en considération toutes les contraintes telles que les interférences, le problème des stations cachées etc. Ce mémoire propose une nouvelle métrique de routage pour RMSF. Nous avons mis en place une nouvelle métrique de routage pour RMSF appelée MBP (Metric Based on Probabilities). Cette métrique est destinée aux RMSF mono-radio ou multiples-radios. Elle permet d’éviter les routes à forte ii interférence. Les résultats des simulations ont montré que MBP présente des améliorations par rapport à certaines métriques : ETT, WCETT et iAWARE qui sont connues dans le domaine.

Détection de la retransmission sélective sur les réseaux de capteurs

L'attaque de retransmission sélective est une menace sérieuse dans les réseaux de capteurs sans fil (WSN), en particulier dans les systèmes de surveillance. Les noeuds peuvent supprimer de manière malicieuse certains paquets de données sensibles, ce qui risque de détruire la valeur des données assemblées dans le réseau et de diminuer la disponibilité des services des capteurs. Nous présentons un système de sécurité léger basé sur l'envoi de faux rapports pour identifier les attaques de retransmission sélective après avoir montré les inconvénients des systèmes existants. Le grand avantage de notre approche est que la station de base attend une séquence de faux paquets à un moment précis sans avoir communiqué avec les noeuds du réseau. Par conséquent, elle sera capable de détecter une perte de paquets. L'analyse théorique montre que le système proposé peut identifier ce type d'attaque et peut alors améliorer la robustesse du réseau dans des conditions d'un bon compromis entre la fiabilité de la sécurité et le coût de transmission. Notre système peut atteindre un taux de réussite élevé d‟identification face à un grand nombre de noeuds malicieux, tandis que le coût de transmission peut être contrôlé dans des limites raisonnables.

Routage adaptatif et stabilité dans les réseaux maillés sans fil

Grâce à leur flexibilité et à leur facilité d’installation, les réseaux maillés sans fil (WMNs) permettent un déploiement d’une infrastructure à faible coût. Ces réseaux étendent la couverture des réseaux filaires permettant, ainsi, une connexion n’importe quand et n’importe où. Toutefois, leur performance est dégradée par les interférences et la congestion. Ces derniers causent des pertes de paquets et une augmentation du délai de transmission d’une façon drastique. Dans cette thèse, nous nous intéressons au routage adaptatif et à la stabilité dans ce type de réseaux. Dans une première partie de la thèse, nous nous intéressons à la conception d’une métrique de routage et à la sélection des passerelles permettant d’améliorer la performance des WMNs. Dans ce contexte nous proposons un protocole de routage à la source basé sur une nouvelle métrique. Cette métrique permet non seulement de capturer certaines caractéristiques des liens tels que les interférences inter-flux et intra-flux, le taux de perte des paquets mais également la surcharge des passerelles. Les résultats numériques montrent que la performance de cette métrique est meilleure que celle des solutions proposées dans la littérature. Dans une deuxième partie de la thèse, nous nous intéressons à certaines zones critiques dans les WMNs. Ces zones se trouvent autour des passerelles qui connaissent une concentration plus élevé du trafic ; elles risquent de provoquer des interférences et des congestions. À cet égard, nous proposons un protocole de routage proactif et adaptatif basé sur l’apprentissage par renforcement et qui pénalise les liens de mauvaise qualité lorsqu’on s’approche des passerelles. Un chemin dont la qualité des liens autour d’une passerelle est meilleure sera plus favorisé que les autres chemins de moindre qualité. Nous utilisons l’algorithme de Q-learning pour mettre à jour dynamiquement les coûts des chemins, sélectionner les prochains nœuds pour faire suivre les paquets vers les passerelles choisies et explorer d’autres nœuds voisins. Les résultats numériques montrent que notre protocole distribué, présente de meilleurs résultats comparativement aux protocoles présentés dans la littérature. Dans une troisième partie de cette thèse, nous nous intéressons aux problèmes d’instabilité des réseaux maillés sans fil. En effet, l’instabilité se produit à cause des changements fréquents des routes qui sont causés par les variations instantanées des qualités des liens dues à la présence des interférences et de la congestion. Ainsi, après une analyse de l’instabilité, nous proposons d’utiliser le nombre de variations des chemins dans une table de routage comme indicateur de perturbation des réseaux et nous utilisons la fonction d’entropie, connue dans les mesures de l’incertitude et du désordre des systèmes, pour sélectionner les routes stables. Les résultats numériques montrent de meilleures performances de notre protocole en comparaison avec d’autres protocoles dans la littérature en termes de débit, délai, taux de perte des paquets et l’indice de Gini.

Evolving Distributed Algorithms with Genetic Programming

Distributed systems are one of the most vital components of the economy. The most prominent example is probably the internet, a constituent element of our knowledge society. During the recent years, the number of novel network types has steadily increased. Amongst others, sensor networks, distributed systems composed of tiny computational devices with scarce resources, have emerged. The further development and heterogeneous connection of such systems imposes new requirements on the software development process. Mobile and wireless networks, for instance, have to organize themselves autonomously and must be able to react to changes in the environment and to failing nodes alike. Researching new approaches for the design of distributed algorithms may lead to methods with which these requirements can be met efficiently. In this thesis, one such method is developed, tested, and discussed in respect of its practical utility. Our new design approach for distributed algorithms is based on Genetic Programming, a member of the family of evolutionary algorithms. Evolutionary algorithms are metaheuristic optimization methods which copy principles from natural evolution. They use a population of solution candidates which they try to refine step by step in order to attain optimal values for predefined objective functions. The synthesis of an algorithm with our approach starts with an analysis step in which the wanted global behavior of the distributed system is specified. From this specification, objective functions are derived which steer a Genetic Programming process where the solution candidates are distributed programs. The objective functions rate how close these programs approximate the goal behavior in multiple randomized network simulations. The evolutionary process step by step selects the most promising solution candidates and modifies and combines them with mutation and crossover operators. This way, a description of the global behavior of a distributed system is translated automatically to programs which, if executed locally on the nodes of the system, exhibit this behavior. In our work, we test six different ways for representing distributed programs, comprising adaptations and extensions of well-known Genetic Programming methods (SGP, eSGP, and LGP), one bio-inspired approach (Fraglets), and two new program representations called Rule-based Genetic Programming (RBGP, eRBGP) designed by us. We breed programs in these representations for three well-known example problems in distributed systems: election algorithms, the distributed mutual exclusion at a critical section, and the distributed computation of the greatest common divisor of a set of numbers. Synthesizing distributed programs the evolutionary way does not necessarily lead to the envisaged results. In a detailed analysis, we discuss the problematic features which make this form of Genetic Programming particularly hard. The two Rule-based Genetic Programming approaches have been developed especially in order to mitigate these difficulties. In our experiments, at least one of them (eRBGP) turned out to be a very efficient approach and in most cases, was superior to the other representations.