The low latency is a prime concern for large Network-on-Chips (NoCs) typically used in chip-multiprocessors (CMPs) and multiprocessor system-on-chips (MPSoCs). A significant component of overall latency is the serialization delay for applications which have long packets such as typical video stream traffic. To address the serialization latency, we propose to exploit the inherent path diversity available in a typical 2-D Mesh with our two novel router architectures, Dual-path router and Dandelion router. We observe that, in a 2-D mesh, for any source-destination pair, there are two minimal paths along the edges of the bounding box. We call it XY Dimension Order Routing (DOR) and YX DOR. There are also two non-minimal paths which are non-coinciding and out of the bounding box created by XY and YX DOR paths. Dual-path Router implements two injection and two ejection ports for parallel packet injection through two minimal paths. Packets are split into two halves and injected simultaneously into the network. Dandelion router implements four injection and ejection ports for parallel packet injection. Packets are split into smaller sub-packets and are injected simultaneously in all possible directions which typically include two minimal paths and two non-minimal paths. When all the sub-packets reach the destination, they are eventually recombined. We find that our technique significantly increases the throughput and reduces the serialization latency and hence overall latency of long packets. We explore the impact of Dual-path and Dandelion on various packet lengths in order to prove the advantage of our routers over the baseline. We further implement different deadlock free disjoint path models for Dandelion and develop a switching mechanism between Dual-path and Dandelion based on the traffic congestion.

Reachability routing is a newly emerging paradigm in networking, where the goal is to determine all paths between a sender and a receiver. It is becoming relevant with the changing dynamics of the Internet and the emergence of low-bandwidth wireless/ad hoc networks. This thesis presents the case for reinforcement learning (RL) as the framework of choice to realize reachability routing, within the confines of the current Internet backbone infrastructure. The setting of the reinforcement learning problem offers several advantages, including loop resolution, multi-path forwarding capability, cost-sensitive routing, and minimizing state overhead, while maintaining the incremental spirit of the current backbone routing algorithms. We present the design and implementation of a new reachability algorithm that uses a model-based approach to achieve cost-sensitive multi-path forwarding. Performance assessment of the algorithm in various troublesome topologies shows consistently superior performance over classical reinforcement learning algorithms. Evaluations of the algorithm based on different criteria on many types of randomly generated networks as well as realistic topologies are presented. / Master of Science

One of the problems sensor networks face is adversaries corrupting nodes along the path to the base station. One way to reduce the effect of these attacks is multipath routing. This introduces some intrusion-tolerance in the network by way of redundancy but at the cost of a higher power consumption by the sensor nodes. Erasure coding can be applied to this scenario in which the base station can receive a subset of the total data sent and reconstruct the entire message packet at its end. This thesis uses two commonly used encodings and compares their performance with respect to power consumed for unencoded data in multipath routing. It is found that using encoding with multipath routing reduces the power consumption and at the same time enables the user to send reasonably large data sizes. The experiments in this thesis were performed on the Tiny OS platform with the simulations done in TOSSIM and the power measurements were taken in PowerTOSSIM. They were performed on the simple radio model and the lossy radio model provided by Tiny OS. The lossy radio model was simulated with distances of 10 feet, 15 feet and 20 feet between nodes. It was found that by using erasure encoding, double or triple the data size can be sent at the same power consumption rate as unencoded data. All the experiments were performed with the radio set at a normal transmit power, and later a high transmit power.

No description available.

Prior research in routing for wireless ad hoc networks has shown that multipath routing can enhance data delivery reliability and provide load balancing. Nevertheless, only a few multipath routing algorithms have been proposed and their interaction with transport layer protocols has not been thoroughly addressed in the literature. In this work, we propose the multipath “Fresnel zone” routing (FZR) algorithm for wireless ad hoc networks. FZR constructs multiple parallel paths from source to destination based on the concept of “Fresnel zones” in a wireless network. The zone construction method assigns intermediate routers into different “Fresnel zones” according to their capacity and efficiency in forwarding traffic. The central idea in FZR is to disperse traffic to different zones according to network load and congestion conditions, thus achieving better throughput and avoiding congestion at intermediate routers. FZR differs from most existing multipath routing approaches in that both source and intermediate nodes use multiple forwarding paths. FZR also adopts a combination of proactive and on-demand (reactive) approaches to reduce control overhead and latency for packet delivery. Simulation experiments have shown that FZR outperforms unipath distance vector routing, multipath distance vector (MDV) routing, and split multipath routing (SMR) algorithms in quasistatic wireless ad hoc networks. In our simulations, FZR achieves up to 100 percent higher average throughput using the User Datagram Protocol (UDP) and 50 percent higher average throughput using the Transmission Control Protocol (TCP). FZR can also provide better load balancing among different paths, improve network resource utilization, and enable fairer resource allocation among different data transmission sessions. Future work is needed to evaluate FZR in mobile scenarios. / Master of Science

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.

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.

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.

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.

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.