A peer-to-peer (P2P) system is a networked system characterized by the lack of centralized control, in which all or most communication is symmetric. Also, a P2P system is supposed to handle frequent arrivals and departures of nodes, and is expected to scale to very large network sizes. These requirements make the design of P2P systems particularly challenging. We investigate two central issues pertaining to the design of P2P systems: load balancing and routing. In the first part of this thesis, we study the problem of load balancing in the context of Distributed Hash Tables (DHTs). Briefly, a DHT is a giant hash table that is maintained in a P2P fashion: Keys are mapped to a hash space I --- typically the interval [0,1), which is partitioned into blocks among the nodes, and each node stores the keys that are mapped to its block. Based on the position of their blocks in I, the nodes also set up connections among themselves, forming a routing network, which facilitates efficient key location. Typically, in a DHT it is desirable that the nodes' blocks are roughly of equal size, since this usually implies a balanced distribution of the load of storing keys among nodes, and it also simplifies the design of the routing network. We propose and analyze a simple distributed scheme for partitioning I, inspired by the multiple random choices paradigm. This scheme guarantees that, with high probability, the ratio between the largest and smallest blocks remains bounded by a small constant. It is also message efficient, and the arrival or departure of a node perturbs the current partition of I minimally. A unique feature of this scheme is that it tolerates adversarial arrivals and departures of nodes. In the second part of the thesis, we investigate the complexity of a natural decentralized routing protocol, in a broad family of randomized networks. The network family and routing protocol in question are inspired by a framework proposed by Kleinberg to model small-world phenomena in social networks, and they capture many designs that have been proposed for P2P systems. For this model we establish a general lower bound on the expected message complexity of routing, in terms of the average node degree. This lower bound almost matches the corresponding known upper bound.

Checkpointing and rollback recovery are well-known techniques for coping with failures in distributed systems. Future generation Supercomputers will be message passing distributed systems consisting of millions of processors. As the number of processors grow, failure rate also grows. Thus, designing efficient checkpointing and recovery algorithms for coping with failures in such large systems is important for these systems to be fully utilized. We presented a novel communication-induced checkpointing algorithm which helps in reducing contention for accessing stable storage to store checkpoints. Under our algorithm, a process involved in a distributed computation can independently initiate consistent global checkpointing by saving its current state, called a tentative checkpoint. Other processes involved in the computation come to know about the consistent global checkpoint initiation through information piggy-backed with the application messages or limited control messages if necessary. When a process comes to know about a new consistent global checkpoint initiation, it takes a tentative checkpoint after processing the message. The tentative checkpoints taken can be flushed to stable storage when there is no contention for accessing stable storage. The tentative checkpoints together with the message logs stored in the stable storage form a consistent global checkpoint. Ad hoc networks consist of a set of nodes that can form a network for communication with each other without the aid of any infrastructure or human intervention. Nodes are energy-constrained and hence routing algorithm designed for these networks should take this into consideration. We proposed two routing protocols for mobile ad hoc networks which prevent nodes from broadcasting route requests unnecessarily during the route discovery phase and hence conserve energy and prevent contention in the network. One is called Triangle Based Routing (TBR) protocol. The other routing protocol we designed is called Routing Protocol with Selective Forwarding (RPSF). Both of the routing protocols greatly reduce the number of control packets which are needed to establish routes between pairs of source nodes and destination nodes. As a result, they reduce the energy consumed for route discovery. Moreover, these protocols reduce congestion and collision of packets due to limited number of nodes retransmitting the route requests.

GT-ITMis a topology generation tool. Since its release GTITMis widely used in the scientific community for network simulations. GTITM is extended to support routing on its topology. The routing algorithm used for interdomain routing attempts to emulate the BGP routing protocol seen on the internet. It uses a policy file if supplied to make routing decisions. An additional functionality provided with the tool is the ability to automatically generate policy file for large graphs.

The problem of multicasting in wireless multihop networks was studied in this dissertation. Nodes in the multicast routing structures were classified into different classes based on their roles in the multicast routing structures. Optimal multicast routing strategies for different classes were analyzed using the most accurate interference model. Based on the analyses, two algorithms to create interference-aware multicast routing tree and three algorithms to create interference-aware multicast routing mesh were proposed. The proposed multicast routing structures were evaluated using wireless network simulations. To improve the credibility of the wireless network simulations, a frame-level bursty link model was proposed and implemented in ns-3 network simulator. The results showed that, by taking interference into account when building multicast routing structures, the proposed multicast routing structures provided improved performance over other multicast routing structures that do not consider wireless interference when building multicast routing structures.

Many interesting theoretical problems arise from computer networks. In this thesis we will consider three of them: algorithms and data structures for problems involving distances in networks (in particular compact routing schemes, distance labels, and distance oracles), algorithms for wireless capacity and scheduling problems, and algorithms for optimizing iBGP overlays in autonomous systems on the Internet. While at first glance these problems may seem extremely different, they are similar in that they all attempt to look at a previously studied networking problem in new, more realistic frameworks. In other words, they are all as much about new models for old problems as they are about new algorithms. In this thesis we will define these models, design algorithms for them, and prove hardness and impossibility results for these three types of problems.

Energy is an important factor that must be considered by multi-hop wireless mesh routing protocols because most sensors are powered by batteries with a limited capacity. We focus on the industry-standard RPL (Routing Protocol over Low-power and lossy networks) routing protocol that must find energy-efficient paths in low-power and lossy networks. However, the existing RPL objective functions route based on hop-count and ETX (expected transmission count) metrics alone, ignoring the energy cost of data transmission and reception. We address this issue in two ways. First, we design an objective function for RPL that finds paths that require, in expectation, the minimum amount of energy. Second, we design a probing mechanism which configures the transmission power of sensors to minimize energy consumption. The proposed approach is implemented and evaluated using simulations as well as on a small testbed with two Zolertial Z1 motes.

In the multiratecasting problem in wireless sensor networks, the source sensor is usually required to report to multiple destinations at dif- ferent rates for each of them. We present a MST-based rate-aware cost-efficient multiratecast routing protocol (MSTRC). The proposed MSTRC examines only one set partition of destinations at each for- warding step. A message split occurs when the locally-built minimum spanning tree (MST) over the current node and the set of destina- tions has multiple edges originated at the current node. Destinations spanned by each of these edges are grouped together, and for each of these subsets the best neighbor is selected as the next hop. We also suggested a novel face recovery mechanism to deal with void ar- eas, when no neighbor provides positive progress toward destinations. It constructs a MST of current node and destinations without the progress via neighbors, and for each set partition of destinations cor- responding to an edge e in MST, the face routing keeps going until a node that is closer to one of these destinations is found, allowing for greedy continuation, while the process repeats for the remaining desti- nations similarly. Our experimental results demonstrate that MSTRC is highly rate-efficient in all scenarios, and unlike existing solutions, it is adaptive to destination rate deviations.

In the publish/subscribe paradigm, information providers disseminate publications to all consumers who have expressed interest by registering subscriptions. This paradigm has found wide-spread applications, ranging from selective information dissemination to network management. However, all existing publish/subscribe systems cannot capture uncertainty inherent to the information in either subscriptions or publications. In many situations the large number of data sources exhibit various kinds of uncertainties. Examples of imprecision include: exact knowledge to either specify subscriptions or publications is not available; the match between a subscription and a publication with uncertain data is approximate; the constraints used to define a match is not only content based, but also take the semantic information into consideration. All these kinds of uncertainties have not received much attention in the context of publish/subscribe systems. In this thesis, we propose new publish/subscribe models to express uncertainties and semantics in publications and subscriptions, along with the matching semantics for each model. We also develop efficient algorithms to perform filtering for our models so that it can be applied to process the rapidly increasing information on the Internet. A thorough experimental evaluation is presented to demonstrate that the proposed systems can offer scalability to large number of subscribers and high publishing rates.

Delay Tolerant Networks (DTNs) are characterized by the lack of continuous end-to-end connections because of node mobility, constrained power sources, and limited data storage space of some or all of its nodes. Applications of DTNs include vehicular networks and sensor networks in suburban and rural areas. The intermittent connection in DTNs creates a new and challenging environment that has not been tackled before in wireless and wired networks. Traditional routing protocols fail to deliver data packets because they assume the existence of continuous end-to-end connections. To overcome the frequent disconnections, a DTN node is required to store data packets for long periods of time until it becomes in the communication range of other nodes. In addition, to increase the delivery probability, a DTN node spreads multiple copies of the same packet on the network so that one of the copies reaches the destination. Given the limited storage and energy resources of DTN nodes, there is a trade off between maximizing delivery and minimizing storage and energy consumption. DTN routing protocols can be classified as either blind routing, in which no information is provided to select the next node in the path, or guided routing, in which some network information is used to guide data packets to their destinations. In addition they differ in the amount of overhead they impose on the network and its nodes. The objective of DTN routing protocols is to deliver as many packets as possible. Acquiring network information helps in maximizing packet delivery probability and minimizing the network overhead resulting from replicating many packet copies. Network information could be node contact times and durations, node buffer capacities, packet lifetimes, and many others. The more information acquired, the higher performance could be achieved. However, the cost of acquiring the network information in terms of delay and storage could be high to the degree that render the protocol impractical. In designing a DTN routing protocol, the trade-off between the benefits of acquiring information and its costs should be considered. In this thesis, we study the routing problem in DTN with limited resources. Our objective is to design and implement routing protocols that effectively handles the intermittent connection in DTNs to achieve high packet delivery ratios with lower delivery cost. Delivery cost is represented in terms of number of transmissions per delivered packet. Decreasing the delivery cost means less network overhead and less energy consumption per node. In order to achieve that objective, we first target the optimal results that could be achieved in an ideal scenario. We formulate a mathematical model for optimal routing, assuming the presence of a global observer that can collect information about all the nodes in the network. The optimal results provide us with bounds on the performance metrics, and show the room for improvement that should be worked on. However, optimal routing with a global observer is just a theoretical model, and cannot be implemented practically. In DTNs, there is a need for a distributed routing protocol which utilizes local and easily-collectable data. Therefore, We investigate the different types of heuristic (non-optimal) distributed routing protocols, showing their strengths and weaknesses. Out of the large collection of protocols, we select four protocols that represent different routing classes and are well-known and highly referred by others working in the same area. We implement the protocols using a DTN simulator, and compare their performance under different network and node conditions. We study the impact of changing the node buffer capacities, packet lifetimes, number of nodes, and traffic load on their performance metrics, which are the delivery ratio, delivery cost, and packet average delay. Based on these comparisons, we draw conclusions and guidelines to design an efficient DTN routing protocol. Given the protocol design guidelines, we develop our first DTN routing protocol, Eco-Friendly Routing for DTN (EFR-DTN), which combines the strengths of two of the previously proposed protocols to provide better delivery ratio with low network overhead (less power consumption). The protocol utilizes node encounters to estimate the route to destination, while minimizing the number of packet copies throughout the network. All current DTN routing protocols strive to estimate the route from source to destination, which requires collecting information about node encounters. In addition to the overhead it imposes on the network to collect this information, the time to collect this information could render the data worthless to propagate through the network. Our next proposal is a routing protocol, Social Groups Based Routing (SGBR), which uses social relations among network nodes to exclude the nodes that are not expected to significantly increase the probability of delivering the packet to its destination. Using social relations among nodes, detected from node encounters, every group of nodes can form a social group. Nodes belonging to the same social group are expected to meet each other frequently, and meet nodes from other groups less frequently. Spreading packet copies inside the same social group is found to be of low-added value to the carrying node in delivering a packet to its destination. Therefore, our proposed routing protocol spreads the packet copies to other social groups, which decreases the number of copies throughout the network. We compare the new protocol with the optimal results and the existing well-known routing protocols using real-life simulations. Results show that the proposed protocol achieves higher delivery ratio and less average delay compared to other protocols with significant reduction in network overhead. Finally, we discuss the willingness of DTN nodes to cooperate in routing services. From a network perspective, all nodes are required to participate in delivering packets of each other. From a node perspective, minimizing resource consumption is a critical requirement. We investigate the degree of fair cooperation where all nodes are satisfied with their participation in the network routing services. A new credit-based system is implemented to keep track of and reward node participation in packet routing. Results show that the proposed system improves the fairness among nodes and increases their satisfaction.

The increased interest in reducing greenhouse gas emissions has motivated renewed interest in electric vehicles technology as an alternative to current fossil-fuel based transportation equipment. Electric vehicles (EVs) are envisioned as a promising viable technology because of their friendly impact on the environment and higher efficiency over conventional vehicles that rely on fossil fuel. However, the EVs’ limited battery capacity, resulting in limited cruising range and long recharging time, hinders the widespread adoption of EVs. An essential requirement of EV motors is the ability to operate with minimum energy consumption in order to provide at least the same driving range as their Internal Combustion Engine (ICE) counterparts. Energy-optimal routing, which aims to find the least energy consuming routes, under battery constraints has been recognized as a viable approach to prolonging the cruising range of the EV battery. This thesis addresses the problem of optimal routing for EVs and proposes a solution to overcome the difficulties of optimal energy/time routing under battery constraints. A multi-criteria path-finding technique is proposed. The proposed technique functions in two modes and solves the problem of optimal energy/time routing in EVs with worst time complexity of . First, an energy mode to solve the problem of energy-optimal routing under battery constraints is introduced. This mode computes the most energy-efficient route from a source to a destination, thus extending the limited cruising range of a battery. Second, a time mode to solve the problem of optimal travel time routing under battery constraints, by computing the most efficient travel-time route from a source to a destination, is proposed. An EV can operate under these two modes to strike a balance between power consumption and travel time so as to satisfy user constraints and needs. In addition, a technique to reduce the effects of range anxiety on the vehicle operator is proposed. This technique computes a robust estimate of driving range. Furthermore, the technique analyzes an EV’s battery capacity required by the vehicle in order to reach a charging station. The thesis reports experimental work conducted to test and validate the proposed techniques under various driving conditions.