Book Description

Abstract: Resource management is a key challenge for networking applications. This dissertation addresses challenges arising in two types of networks: high-speed wired networks and wireless sensor networks. The first part of the dissertation focuses on advance reservation of resources in high-speed networks. We first present a polynomial-time algorithmic framework for routing and scheduling called Graded Channel Reservation (GCR). GCR returns the highest graded path, selected according to a general, multi-criteria optimization objective, such as delay or path length. We extend GCR to support path switching and show that it yields significant performance improvement. Next, we demonstrate the feasibility of implementing distributed solutions for advance reservation. We introduce a new distance-vector algorithm that provably returns the earliest time possible for starting a connection between any two nodes. We prove that widest path routing and path switching are necessary to guarantee earliest starting time and propose a novel approach for loop-free distributed widest path routing. Third, we propose new on-line algorithms for advance reservation, based on multi- commodity flow formulations, that are guaranteed to achieve optimal throughput. We explore a simple approach based on the max-flow min-cut theorem that limits the number of parallel paths used by the algorithms while tightly bounding the maximum reduction factor in the transmission throughput. Our simulations show that a few number of parallel paths is sufficient to achieve a throughput performance close to capacity bounds. The second part of the dissertation focuses on efficient monitoring in wireless sensor networks using connected identifying codes. We formulate the minimum connected identifying code problem and prove that it is NP-complete. We propose a novel polynomial-time approximation algorithm, called ConnectlD, that transforms any identifying code into a connected version that is at most twice the size of the original. When the input identifying code is r-robust, we prove that the size of the output by Connect ID decreases roughly as fast as 1 + r -1 or more and converges to the size of the input. Thus, r -robust codes provide connectivity essentially for free