In this dissertation, we studied methods for improving efficiency and effectiveness of multipath routing in computer networks. We showed that multipath routing can improve network performance for failure recovery, load balancing, Quality of Service (QoS), and energy consumption. We presented a method for reducing the overhead of computing dynamic path metrics, one of the obstacles for implementing dynamic multipath routing in real world networks. In the first part, we proposed a method for building disjoint multipaths that could be used for local failure recovery as well as for multipath routing. Proactive failure recovery schemes have been recently proposed for continuous service of delay-sensitive applications during failure transients at the cost of extra infrastructural support in the form of routing table entries, extra addresses, etc. These extra infrastructure supports could be exploited to build alternative disjoint paths in those frameworks, while keeping the lengths of the alternative paths close to those of the primary paths. The evaluations showed that it was possible to extend the proactive failure recovery schemes to provide support for nearly-disjoint paths which could be employed in multipath routing for load balancing and QoS. In the second part, we proposed a method for reducing overhead of measuring dynamic link state information for multipath routing, specifically path delays used in Wardrop routing. Even when dynamic routing could be shown to offer convergence properties without oscillations, it has not been widely adopted. One of reasons was that the expected cost of keeping the link metrics updated at various nodes in the network. We proposed threshold-based updates to propagate the link state only when the currently measured link state differs from the last updated state consider- ably. Threshold-based updates were shown through analysis and simulations to offer bounded guarantees on path quality while significantly reducing the cost of propagating the dynamic link metric information. The simulation studies indicated that threshold based updates can reduce the number of link updates by up to 90-95% in some cases. In the third part, we proposed methods of using multipath routing for reducing energy consumption in computer networks. Two different approaches have been advocated earlier, from traffic engineering and topology control to hardware-based approaches. We proposed solutions at two different time scales. On a finer time granularity, we employed a method of forwarding through alternate paths to enable longer sleep schedules of links. The proposed schemes achieved more energy saving by increasing the usage of active links and the down time of sleeping links as well as avoiding too frequent link state changes. To the best of our knowledge, this was the first technique combining a routing scheme with hardware scheme to save energy consumption in networks. In our evaluation, alternative forwarding reduced energy consumption by 10% on top of a hardware-based sleeping scheme. On a longer time granularity, we proposed a technique that combined multipath routing with topology control. The proposed scheme achieved increased energy savings by maximizing the link utilization on a reduced topology where the number of active nodes and links are minimized. The proposed technique reduced energy consumption by an additional 17% over previous schemes with single/shortest path routing.

No description available.

The GPS tracking in sprint orienteering is often a poor supplement to the viewer experience during events taking place in urban areas because of multipath effects. Since the GPS tracking of runners is an important means to making the sport more spectator friendly, it is of interest to make it more accurate. In this thesis project, the information provided by the map of a competition is fused with the GPS tracker position measurements and punch time data in a particle filter to create estimates of the runner trajectories. The map is used to create constraints and to predict motion of runners, as well as to create a model of the GPS reliability depending on map position. A simple observation model is implemented, using the map to decide if a GPS measurement is reliable or not depending on the distance to the closest building. A rather complex motion model is developed to predict the runner motion within the constraints given by the map. The results show that given certain conditions the improvements are vast compared to the traditional GPS tracking. The estimates are bound to possible routes, and they are often very good given that alternative route choices are easily separable. It is however principally difficult to generally improve the tracking using this method. Better measurements or observation models are needed in order to receive a fully satisfying tracking.

<p>The soaring demands for always-on and fast-response online services have driven modern datacenter networks to undergo tremendous growth. These networks often rely on scale-out designs with large numbers of commodity switches to reach immense capacity while keeping capital expenses under check. Today, datacenter network operators spend tremendous time and efforts on two key challenges: 1) how to efficiently utilize the bandwidth connecting host pairs and 2) how to promptly handle network failures with minimal disruptions to the hosted services.</p><p>To resolve the first challenge, we propose solutions in both network layer and transport layer. In the network layer solution, We advocate to design practical datacenter architectures for easy operation, i.e., an architecture should be reliable, capable of improving bisection bandwidth, scalable and debugging-friendly. By strictly following these four guidelines, We propose DARD, a Distributed Adaptive Routing architecture for Datacenter networks. DARD allows each end host to reallocate traffic from overloaded paths to underloaded paths without central coordination. We use congestion game theory to show that DARD converges to a Nash equilibrium in finite steps and its gap to the optimal flow allocation is bounded in the order of 1/logL, with L being the number of links. We use a testbed implementation and simulations to show that DARD can achieve a close-to-optimal flow allocation with small control overhead in practice.</p><p>In the transport layer solution, We propose Explicit Multipath Congestion Control Protocol (MPXCP), which achieves four desirable properties: fast convergence, efficiency, being fair to flows with different RTTs and negligible queue size. Intensive ns-2 simulation shows that MPXCP can quickly converge to efficiency and fairness without building up queues despite different delay-bandwidth products.</p><p>To resolve the second challenge, recent research efforts have focused on automatic failure localization. Yet, resolving failures still requires significant human interventions, resulting in prolonged failure recovery time. Unlike previous work, we propose NetPilot, a system aims to quickly mitigate rather than resolve failures. NetPilot mitigates failures in much the same way operators do -- by deactivating or restarting suspected offending components. NetPilot circumvents the need for knowing the exact root cause of a failure by taking an intelligent trial-and-error approach. The core of NetPilot is comprised of an Impact Estimator that helps guard against overly disruptive mitigation actions and a failure-specific mitigation planner that minimizes the number of trials. We demonstrate that NetPilot can effectively mitigate several types of critical failures commonly encountered in production datacenter networks.</p> / Dissertation

Sharing the resources of multiple wireless networks with overlapped coverage areas has a potential of improving the transmission throughput. However, in the existing frameworks, the improvement cannot be achieved in congestion scenarios because of independent congestion control procedures among the end-to-end paths. Although various network characteristics make the congestion control complex, this variety can be useful in congestion avoidance if the networks cooperate with each other. When congestion happens in an end-to-end path, it is inevitable to have a packet transmission rate less than the minimum requested rate due to congestion window size adjustments. Cooperation among networks can help to avoid this problem for better service quality. When congestion is predicted for one path, some of the on-going packets can be sent over other paths instead of the congested path. In this way, the traffic can be shifted from a congested network to others, and the overall transmission throughput does not degrade in a congestion scenario. However, cooperation is not always advantageous since the throughput of cooperative transmission in an uncongested scenario can be less than that of non-cooperative transmission due to cooperation costs such as cooperation setup time, additional signalling for cooperation, and out-of-order packet reception. In other words, a trade-off exists between congestion avoidance and cooperation cost. Thus, cooperation should be triggered only when it is beneficial according to congestion level measurements. In this research, our aim is to develop an efficient cooperative congestion control scheme for a heterogeneous wireless environment. To this end, a cooperative congestion control algorithm is proposed, in which the state of an end-to-end path is provided at the destination terminal by measuring the queuing delay and estimating the congestion level. The decision on when to start/stop cooperation is made based on the network characteristics, instantaneous traffic condition, and the requested quality of service (QoS). Simulation results demonstrate the throughput improvement of the proposed scheme over non-cooperative congestion control.

In this thesis, an investigation of the performance of multipath routing in Wireless Sensor Networks (WSN) is performed. The communication in the network under study is to take place from individual nodes to the sink node. The investigation involved multipath finding methods in WSN. Also, it involves investigating the weight assignment, traffic splitting and route selection methods for the different paths discovered by each node in the WSN. Also, a comparison between Hybrid Routing Protocol, Source Routing Protocol and Diffusion Routing Protocol is performed. A simple traffic routing algorithm for each routing protocol has been developed to conceptualize how the network traffic is routed on a set of active paths. The investigation of the Hybrid, Source and Diffusion Routing Protocol involved using multiple paths simultaneously to transmit messages that belong to the same flow by using a weight assigned to each path and transmit each message as a whole. Finally, the power consumption and the QoS in terms of message delays for a WSN were investigated and compared between different protocols.

The Publish/Subscribe (pub/sub) model has been widely applied in a variety of application scenarios which demand loose-coupling and asynchronous communication between a large number of information sources and sinks. In this model, clients are granted the flexibility to specify their interests at a high level and rely on the pub/sub middleware for delivery of their publications of interest. This increased flexibility and ease of use on the client side results in substantial complexity on part of the pub/sub middleware implementation. Furthermore, for several reasons including improved scalability, availability and avoiding a single point of failure, the pub/sub middleware is commonly composed of a set of collaborating message routers, a.k.a. brokers. The distributed nature of this design further introduces new challenges in ensuring end-to-end reliability as well as efficiency of operation. These challenges are largely unique to the pub/sub model and hence absent in both point-to-point or multicast protocols. This thesis develops solutions that ensure the dependable operation of the pub/sub system by exploiting the notion of overlay neighborhoods in a formal manner. More specifically, brokers maintain information about their neighbors within a configurable distance in the pub/sub overlay and exploit this knowledge to construct alternative forwarding paths or make smart forwarding decisions that improves efficiency, bandwidth utilization and delivery delay, all at the same time. Furthermore, in the face of failures overlay neighborhoods enable fast reconstruction of forwarding paths in the system without compromising its reliability and availability. Finally, as an added benefit of overlay neighborhoods, this thesis develops large-scale algorithms that bring the advantages of the pub/sub model to the domain of file sharing and bulk content dissemination applications. Experimental evaluation results with deployments as large as 1000 nodes illustrate that the pub/sub system scales well and outperforms the traditional BitTorrent protocol in terms of content dissemination delay.

In this thesis, symbol timing recovery in MSK signals is investigated making use of matched filtering. A decision-directed symbol synchronizer cascaded with an MLSE receiver is proposed for fine timing. Correlation (matched filter) method is used to recover the timing epoch from the tentative decisions obtained from the Viterbi algorithm. The fractional delays are acquired using interpolation and an iterative maximum search process. In order to investigate the tracking performance of the proposed symbol synchronizer, a study is carried out on three possible optimum timing phase criteria: (i) Mazo criterion, (ii) the minimum squared ISI criterion (msISI), and (iii) the minimum BER criterion. Moreover, a discussion is given about the timing sensitivity of the MLSE receiver. The performance of the symbol synchronizer is assessed by computer simulations. It is observed that the proposed synchronizer tracks the variations of the channels almost the same as the msISI criterion. The proposed method eliminates the cycle slips very succesfully and is robust to frequency-selective multipath fading channel conditions even in moderate signal-to-noise ratios.

[pt] Este trabalho apresenta a base de um modelo matemático destinado a interpretar teoricamente o comportamento estatístico de sinais sujeitos a desvanecimentos rápidos em enlaces de microondas em visibilidade. As teorias existentes para explicar a dependência do fenômeno com as características de um lance são discutidas em função dos resultados experimentais disponíveis. Foi investigado com especial atenção o relacionamento entre as profundidades de desvanecimento e a rugosidade do relevo, demonstrando-se que a fórmula empírica atualmente em uso é perfeitamente adequada para quantificar este efeito. / [en] The purpose of this work is to present a mathematical model to interpret theoreticallly the statistical behavior of deep fades in line-of-sight microware paths. The previous theories are discussed and compared to the known experimental data. A simple model is used to obtain a theoretical dependence of the fades deepth with the path roughness. The results show that the empirical expression presently in use quantifies correctly this effect.

Esta tese apresenta DCE, ou Execução Dinâmica Condicional, como uma alternativa para reduzir o custo da previsão incorreta de desvios. A idéia básica do modelo apresentado é buscar e executar todos os caminhos de desvios que obedecem à certas restrições no que diz respeito a complexidade e tamanho. Como resultado, tem-se um número menor de desvios sendo previstos e consequentemente um número menor de desvios previstos incorretamente. DCE busca todos os caminhos dos desvios selecionados evitando quebras no fluxo de busca quando estes desvios são buscados. Os caminhos buscados dos desvios selecionados são então executados mas somente o caminho correto é completado. Nesta tese nós propomos uma arquitetura para executar múltiplos caminhos dos desvios selecionados. A seleção dos desvios ocorre baseada no tamanho do desvio e em outras condições. A seleção de desvios simples e complexos permite a predicação dinâmica destes desvios sem a necessidade da existência de um conjunto específico de instruções nem otimizações especiais por parte do compilador. Além disso, é proposta também uma técnica para reduzir a sobrecarga gerada pela execução dos múltiplos caminhos dos desvios selecionados. O desempenho alcançado atinge níveis de até 12% quando um previsor de desvios Local é usado no DCE e um previsor Global é usado na máquina de referência. Quando ambas as máquinas empregam previsão Local, há um aumento de desempenho da ordem de 3-3.5%. / This thesis presents DCE, or Dynamic Conditional Execution, as an alternative to reduce the cost of mispredicted branches. The basic idea is to fetch all paths produced by a branch that obey certain restrictions regarding complexity and size. As a result, a smaller number of predictions is performed, and therefore, a lesser number of branches are mispredicted. DCE fetches through selected branches avoiding disruptions in the fetch flow when these branches are fetched. Both paths of selected branches are executed but only the correct path commits. In this thesis we propose an architecture to execute multiple paths of selected branches. Branches are selected based on the size and other conditions. Simple and complex branches can be dynamically predicated without requiring a special instruction set nor special compiler optimizations. Furthermore, a technique to reduce part of the overhead generated by the execution of multiple paths is proposed. The performance achieved reaches levels of up to 12% when comparing a Local predictor used in DCE against a Global predictor used in the reference machine. When both machines use a Local predictor, the speedup is increased by an average of 3-3.5%.