Due to the high availability of cheap hardware, wireless multi-hop networks and in particular Wireless Mesh Networks (WMNs) are becoming popular in more and more contexts. For instance, IEEE 802.11 based WMNs have already started to be deployed as means to provide Internet access to rural areas in the developing world. To lower the cost and increase the coverage in such deployments, the wired network is extended with a wireless backbone of fixed mesh routers. With advances in technology and reduction in price comes also the possibility for more powerful wireless nodes, having multiple radios that allow transmitting on different channels in parallel. To be a successful platform for providing general Internet access, wireless multi-hop networks must provide support for common Internet applications. As most of the applications in the Internet today use the Transmission Control Protocol (TCP), TCP performance is crucial. Unfortunately, the design of TCP’s congestion control that made it successful in today’s Internet makes it perform less than optimal in wireless multi-hop networks. This is due to, among others, TCP’s inability to distinguish wireless losses from congestion losses. The current trend for operating system designers is also to focus TCP development on high-speed fixed networks, rather than on wireless multi-hop networks. To enable wireless multi hop networks as a successful platform there is therefore a need to provide good performance using TCP variants commonly deployed in the Internet. In this thesis, we develop novel proposals for the network layer in wireless multi-hop networks to support TCP traffic more efficiently. As an initial study, we experimentally evaluate different TCP variants, with and without mobile nodes, in a MANET context. Our results show that TCP Vegas, which does not provoke packet loss to determine available bandwidth, reduces the stress on the network while still providing the same or slightly increased performance, compared to TCP Newreno. We further propose and evaluate packet aggregation combined with aggregation aware multi-path forwarding to better utilize the available bandwidth. IP layer packet aggregation, where small packets are combined to larger ones before sent to the link layer, has been shown to improve the performance in wireless multi-hop networks for UDP and small packet transfers. Only few studies have been made on the impact of packet aggregation on TCP traffic, despite the fact that TCP traffic constitutes the majority of the Internet traffic. We propose a novel aggregation algorithm that is specifically addressing TCP relevant issues like packet reordering, fairness and TCP timeouts. In a typical WMN scenario, the aggregation algorithm increases TCP performance by up to 70 % and decreases round trip time (RTT) by up to 40 %. A detailed evaluation of packet aggregation in a multi radio setting has shown that a naive combination of multi path routing and packet aggregation can cause valuable aggregation opportunities to be lost. Therefore, we propose a novel combined packet aggregation and aggregation aware forwarding strategy that can reduce delay, packet loss and increase TCP performance by around 30 %.

A wireless Mobile Ad Hoc Network (MANET) comprises of a number of mobile nodes that uses multi-hop routing to provide network connectivity. MANETs require self-organizing capabilities as there are no centralized points (base stations, access points etc), and each mobile node functions as router and/or hosts. The wireless topology in MANET can change rapidly with mobility of nodes in unpredictable ways or remain static for long periods of time. MANETs have applications in neighborhood area networks (NANs), impromptu communication among groups of people, disaster management and dynamic military systems. As progress in MANET continues, there is an increase in demand with regard to supporting content-rich video streaming in such networks. This is due to the fact that real-time video is far more substantive than simple data communication. This work involves implementing a Genetic Algorithm (GA) based multipath routing methodologies in a proactive routing protocol (Optimized Link State Routing Protocol) to send/forward/receive multimedia streams on experimental testbed. We study the problem of multipath video routing in wireless ad hoc networks by following an application-centric cross-layer approach. A full implementation of GA-based routing and real-time video conferencing application (server and client) written in C++ is presented. The robustness of our routing scheme was tested through experiments using five computer nodes. The performance of the routing protocol for video, as well as issues such as applicability and scalability in practice are addressed. / Master of Science

Big data has received a great deal attention from many sectors, including academia, industry and government. The Hadoop framework has emerged for supporting its storage and analysis using the MapReduce programming module. However, this framework is a complex system that has more than 150 parameters and some of them can exert a considerable effect on the performance of a Hadoop job. The optimum tuning of the Hadoop parameters is a difficult task as well as being time consuming. In this thesis, an optimisation approach is presented to improve the performance of a Hadoop framework by setting the values of the Hadoop parameters automatically. Specifically, genetic programming is used to construct a fitness function that represents the interrelations among the Hadoop parameters. Then, a genetic algorithm is employed to search for the optimum or near the optimum values of the Hadoop parameters. A Hadoop cluster is configured on two severe at Brunel University London to evaluate the performance of the proposed optimisation approach. The experimental results show that the performance of a Hadoop MapReduce job for 20 GB on Word Count Application is improved by 69.63% and 30.31% when compared to the default settings and state of the art, respectively. Whilst on Tera sort application, it is improved by 73.39% and 55.93%. For better optimisation, SDN is also employed to improve the performance of a Hadoop job. The experimental results show that the performance of a Hadoop job in SDN network for 50 GB is improved by 32.8% when compared to traditional network. Whilst on Tera sort application, the improvement for 50 GB is on average 38.7%. An effective computing platform is also presented in this thesis to support solar irradiation data analytics. It is built based on RHIPE to provide fast analysis and calculation for solar irradiation datasets. The performance of RHIPE is compared with the R language in terms of accuracy, scalability and speedup. The speed up of RHIPE is evaluated by Gustafson's Law, which is revised to enhance the performance of the parallel computation on intensive irradiation data sets in a cluster computing environment like Hadoop. The performance of the proposed work is evaluated using a Hadoop cluster based on the Microsoft azure cloud and the experimental results show that RHIPE provides considerable improvements over the R language. Finally, an effective routing algorithm based on SDN to improve the performance of a Hadoop job in a large scale cluster in a data centre network is presented. The proposed algorithm is used to improve the performance of a Hadoop job during the shuffle phase by allocating efficient paths for each shuffling flow, according to the network resources demand of each flow as well as their size and number. Furthermore, it is also employed to allocate alternative paths for each shuffling flow in the case of any link crashing or failure. This algorithm is evaluated by two network topologies, namely, fat tree and leaf-spine, built by EstiNet emulator software. The experimental results show that the proposed approach improves the performance of a Hadoop job in a data centre network.

Delay is known to be a critical performance metric for various real-world routing applications including multimedia communication and freight delivery. Provisioning delay-minimal (or at least delay-bounded) routing services for all traffic of an application is highly important. As a basic paradigm of networking, multi-path routing has been proven to be able to obtain lower delay performance than the single-path routing, since traffic congestions can be avoided. However, to our best knowledge, (i) many of existing delay-aware multi-path routing studies only consider the aggregate traffic delay. Considering that even the solution achieving the optimal aggregate traffic delay has a possibly unbounded delay performance for certain individual traffic unit, those studies may be insufficient in practice; besides, (ii) most existing studies which optimize or bound delays of all traffic are best-effort, where the achieved solutions have no theoretical performance guarantee. In this dissertation, we study four delay-aware multi-path routing problems, with the delay performances of all traffic taken into account. Three of them are in communication and one of them is in transportation. Note that our study differ from all related ones as we are the first to study the four fundamental problems to our best knowledge. Although we prove that our studied problems are all NP-hard, we design approximation algorithms with theoretical performance guarantee for solving each of them. To be specific, we claim the following contributions. Minimize maximum delay and average delay. First, we consider a single-unicast setting where in a multi-hop network a sender requires to use multiple paths to stream a flow at a fixed rate to a receiver. Two important delay metrics are the average sender-to-receiver delay and the maximum sender-to-receiver delay. Existing results say that the two delay metrics of a flow cannot be both within bounded-ratio gaps to the optimal. In comparison, we design three different flow solutions, each of which can minimize the two delay metrics simultaneously within a $(1/epsilon)$-ratio gap to the optimal, at a cost of only delivering $(1-epsilon)$-fraction of the flow, for any user-defined $epsilonin(0,1)$. The gap $(1/epsilon)$ is proven to be at least near-tight, and we further show that our solutions can be extended to the multiple-unicast setting. Minimize Age-of-Information (AoI). Second, we consider a single-unicast setting where in a multi-hop network a sender requires to use multiple paths to periodically send a batch of data to a receiver. We study a newly proposed delay-sensitive networking performance metric, AoI, defined as the elapsed time since the generation of the last received data. We consider the problem of minimizing AoI subject to throughput requirements, which we prove is NP-hard. We note that our AoI problem differs from existing ones in that we are the first to consider the batch generation of data and multi-path communication. We develop both an optimal algorithm with a pseudo-polynomial time complexity and an approximation framework with a polynomial time complexity. Our framework can build upon any polynomial-time $alpha$-approximation algorithm of the maximum delay minimization problem, to construct an $(alpha+c)$-approximate solution for minimizing AoI. Here $c$ is a constant dependent on throughput requirements. Maximize network utility. Third, we consider a multiple-unicast setting where in a multi-hop network there exist many network users. Each user requires a sender to use multiple paths to stream a flow to a receiver, incurring an utility that is a function of the experienced maximum delay or the achieved throughput. Our objective is to maximize the aggregate utility of all users under throughput requirements and maximum delay constraints. We observe that it is NP-complete either to construct an optimal solution under relaxed maximum delay constraints or relaxed throughput requirements, or to figure out a feasible solution with all constraints satisfied. Hence it is non-trivial even to obtain approximate solutions satisfying relaxed constraints in a polynomial time. We develop a polynomial-time approximation algorithm. Our algorithm obtains solutions with constant approximation ratios under realistic conditions, at the cost of violating constraints by up to constant-ratios. Minimize fuel consumption for a heavy truck to timely fulfill multiple transportation tasks. Finally, we consider a common truck operation scenario where a truck is driving in a national highway network to fulfill multiple transportation tasks in order. We study an NP-hard timely eco-routing problem of minimizing total fuel consumption under task pickup and delivery time window constraints. We note that optimizing task execution times is a new challenging design space for saving fuel in our multi-task setting, and it differentiates our study from existing ones under the single-task setting. We design a fast and efficient heuristic. We characterize conditions under which the solution of our heuristic must be optimal, and further prove its optimality gap in case the conditions are not met. We simulate a heavy-duty truck driving across the US national highway system, and empirically observe that the fuel consumption achieved by our heuristic can be $22%$ less than that achieved by the fastest-/shortest- path baselines. Furthermore, the fuel saving of our heuristic as compared to the baselines is robust to the number of tasks. / Doctor of Philosophy / We consider a network modeled as a directed graph, where it takes time for data to traverse each link in the network. It models many critical applications both in the communication area and in the transportation field. For example, both the European education network and the US national highway network can be modeled as directed graphs. We consider a scenario where a source node is required to send multiple (a set of) data packets to a destination node through the network as fast as possible, possibly using multiple source-to-destination paths. In this dissertation we study four problems all of which try to figure out routing solutions to send the set of data packets, with an objective of minimizing experienced travel time or subject to travel time constraints. Although all of our four problems are NP-hard, we design approximation algorithms to solve them and obtain solutions with theoretically bounded gaps as compared to the optimal. The first three problems are in the communication area, and the last problem is in the transportation field. We claim the following specific contributions. Minimize maximum delay and average delay. First, we consider the setting of simultaneously minimizing the average travel time and the worst (largest) travel time of sending the set of data packets from source to destination. Existing results say that the two metrics of travel time cannot be minimized to be both within bounded-ratio gaps to the optimal. As a comparison, we design three different routing solutions, each of which can minimize the two metrics of travel time simultaneously within a constant bounded ratio-gap to the optimal, but at a cost of only delivering a portion of the data. Minimize Age-of-Information (AoI). Second, we consider the problem of minimizing a newly proposed travel-time-sensitive performance metric, i.e., AoI, which is the elapsed time since the generation of the last received data. Our AoI study differs from existing ones in that we are the first to consider a set of data and multi-path routing. We develop both an optimal algorithm with a pseudo-polynomial time complexity and an approximation framework with a polynomial time complexity. Maximize network utility. Third, we consider a more general setting with multiple source destination pairs. Each source incurs a utility that is a function of the experienced travel time or the achieved throughput to send data to its destination. Our objective is to maximize the aggregate utility under throughput requirements and travel time constraints. We develop a polynomial-time approximation algorithm, at the cost of violating constraints by up to constant-ratios. It is non-trivial to design such algorithms, as we prove that it is NPcomplete either to construct an optimal solution under relaxed delay constraints or relaxed throughput requirements, or to figure out a feasible solution with all constraints satisfied. Minimize fuel consumption for a heavy truck to timely fulfill multiple transportation tasks. Finally, we consider a truck and multiple transportation tasks in order, where each task requires the truck to pick up cargoes at a source timely, and deliver them to a destination timely. The need of coordinating task execution times is a new challenging design space for saving fuel in our multi-task setting, and it differentiates our study from existing ones under the single-task setting. We design an efficient heuristic. We characterize conditions under which the solution of our heuristic must be optimal, and further prove its performance gap as compared to the optimal in case the conditions are not met.

Wireless communication has seen a tremendous growth in the last decades. Continuing on this trend, wireless multi-hop networks  are nowadays used or planned for use in a multitude of contexts, spanning from Internet access at home to emergency situations. The Transmission Control Protocol (TCP) provides reliable and ordered delivery of a data and is used by major Internet applications such as web browsers, email clients and file transfer programs. TCP traffic is also the dominating traffic type on the Internet. However, TCP performs less than optimal in wireless multi-hop networks due to packet reordering, low link capacity, packet loss and variable delay. In this thesis, we develop novel proposals for enhancing the network and transport layer to improve TCP performance in wireless multi-hop networks. As initial studies, we experimentally evaluate the performance of different TCP variants, with and without mobile nodes. We further evaluate the impact of multi-path routing on TCP performance and propose packet aggregation combined with aggregation aware multi-path forwarding as a means to better utilize the available bandwidth. The last contribution is a novel extension to multi-path TCP to  enable single-homed hosts to fully utilize the network capacity. / <p>Opponent changed. Prof. C. Lindeman from the University of Leipzig was substituted by Prof. Zhang.</p>

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

Un réseau sans fil multi-saut est un ensemble d’entités mobiles et/ou fixes formant un réseau dynamique temporaire avec ou sans l’aide de toute administration centralisée. Cette particularité rend le routage problématique en cas d’instabilité des éléments qui composent les communications non directes. Afin de palier ces problèmes, de nouvelles formes de routage sont utilisées comme le routage multi-chemin (MC). Le routage MC permet d’envoyer les données sur des chemins multiples et semble être une solution efficace pour ces réseaux. Le but de cette thèse est d’étudier les techniques de routage MC dans un contexte sans fil multi-saut en vue d’obtenir de meilleures performances. Nous avons choisi pour notre étude une extension MC du protocole OLSR, appelée MP-OLSR. Nous évaluons ses performances sous divers scénarios sous NS-2. Ces tests d’évaluation nous ont amenés à mettre en ´evidence deux problèmes dans MP-OLSR : la réactivité du protocole de routage MC suite à des ruptures de route et la stratégie de répartition des données sur les chemins multiples. Nous avons étudié la réactivité de tels mécanismes dans MP-OLSR. Nous avons proposé trois nouvelles techniques de réparation de pannes qui diminuent les temps de rétablissement d’une route et réduisent le taux de perte des flux transmis. Nous proposons aussi un mécanisme qui détecte la dégradation de la qualité des liens durant le transfert d’un trafic de données. Les informations déduites de ce mécanisme servent à adapter la proportion de trafic à affecter à chaque chemin selon les conditions réseaux. Cette nouvelle variante du protocole MP-OLSR est évaluée par simulation. / Wireless multi-hop networks consist of a collection of mobile and/or fixed nodes which dynamically exchange data with (or without) reliance on a (any) centralized administration. They are by definition self-organized. The frequent topological changes make multi-hop routing a crucial issue for these networks. To overcome these problems, new forms of routing schemes are used as the multipath routing (MP). MP routing uses multiple paths to send data and can be regarded as an effective solution for these networks. The purpose of this PhD thesis is to study the MP routing techniques in a wirelessmulti-hop context for better performance. We choose for our study a MP extension of OLSR, called MP-OLSR. We evaluate its performance under various scenarios in NS-2. These tests have led us to highlight two problems in MP-OLSR : the long recovery delays when facing network failure situations and the allocation strategy of data on multiple paths. We define and seek to evaluate the latency introduced by both protocols OLSR and MP-OLSR to find a new path after a link failure. We propose three new different recovery schemes and accordingly extend these original protocols in order to decrease theexpected latency and reduce the packet loss rate of transmitted flow. We also propose a mechanism which is able to detect the deterioration of the link quality during the transfer of data traffic. The information derived from this mechanism is used to adjust the proportion of traffic to be assigned to each path according to network conditions. This new version of MP-OLSR protocol is evaluated by simulation.