Abstract:
This dissertation is a collection of several pieces of mostly unrelated projects conducted during the several past years in Wings lab in Department of Computer Science in Stony Brook University. The only common theme of these various project is the use of wireless links as the underlying medium of communication and building block of the network. The first chapter is dedicated to the pice de rsistance of this thesis. The chapter explores a practical and cost competitive method for constructing a mostly wireless data center network. Conventional wired data center (DC) network designs offer extreme cost vs. performance tradeoffs. Recent results make the case for a promising alternative to the current dominant architectures where an oversubscribed network is augmented with reconfigurable inter-rack wireless or optical links. Inspired by the promise of reconfigurability, the chapter presents FireFly, an inter-rack network solution that pushes DC network design to the extreme on three key fronts: (1) all links are reconfigurable; (2) all links are wireless; and (3) the non-ToR switches are eliminated altogether. This vision, if realized, can offer significant benefits in terms of increased flexibility, reduced equipment cost, and minimal cabling complexity. In order to achieve this vision, one need to look beyond traditional RF wireless solutions due to their large interference footprint which limits range and data rates. Thus, this work make the case for using free-space optics (FSO). The chapter demonstrates the viability of FSO by building a proof-of-concept prototype of a steerable small form factor FSO device using commodity components. In addition, it address practical algorithmic and system-level challenges in network design and management to near-optimally leverage the benefits of the FireFly vision. The second chapter addresses the problem of preserving generated data in a sensor network in case of node failures. The chapter focus on the type of node failures that have explicit spatial shapes such as circles or rectangles (e.g., modeling a bomb attack or a river overflow). Two different schemes for introducing redundancy in the network is considered, simply replicating data or by using erasure codes, with the objective to minimize the communication cost incurred to build such data redundancy. It is proven that the problem is NP-hard using either replication or coding. A O(α )-approximation algorithm for each of the schemes is proposed, where _ is the " fatness" of the potential node failure events. In addition, a distributed approximation algorithm using erasure codes is designed. Simulation results show that by exploiting the spatial properties of the node failure patterns, one can substantially reduce the communication cost, compared with resilient data storage schemes in the prior literature. The third chapter studies the effect of introducing delayed scheduling of user traffic on the performance of broadband cellular networks. The work is motivated by the studies which have indicated the traffic load on the cellular base stations varies significantly over time. This gives an opportunity to accommodate additional traffic with the same network capacity if some of the traffic (e.g., p2p, cloud sync) can be amenable to delayed scheduling without hurting the user experience any significantly. In this chapter, various algorithmic problems that can arise in this context is studied. Using a model where all flows can have certain flexibility in scheduling (via use of a deadline), optimal or near-optimal algorithms to determine the minimum network capacity for two different models is developed. In addition, various semi-online and online algorithms for online scheduling of flows, and analyze their performance are developed. In particular, even though the online scheduling problem is shown to be intractable, the proposed semi-online algorithm can schedule flows optimally if aided by historical data and slightly additional network capacity over the optimal. Finally, using flow level traffic traces collected at the core of a commercially operated cellular network, the effectiveness of these techniques is evaluated. Evaluations show that delayed scheduling, when done efficiently (using an offline optimal algorithm), can accommodate the same traffic with much lower network capacity (up to 50only modest delays. While such an optimal solution needs an offline approach, one can demonstrate that online scheduling can be almost equally effective when historical traffic data can be exploited for estimation purposes. The fourth chapter studies the problem of channel assignment in femtocells. Femtocells are short-range devices deployed to provide increased coverage and capacity in a small area. They offer a way to increase the capacity of a cellular network by relaying cellular traffic to the wired network. In this chapter, the problem of optimizing the overall capacity of a femtocell network, as defined by Shannon's law and physical interference, by appropriate power and channel assignment to the femtocells is studied. In particular, an approximation algorithm for the objective of maximizing the total network capacity is designed for large uniform networks with arbitrary coverage regions. The second objective of maximizing the minimum capacity at a femtocell in the network is considered, and an algorithm for arbitrary networks is designed which has an appropriate performance guarantee if there is a lower-bound on the distance of any two femtocells. Through simulations, it is demonstrated the performance of our designed algorithms by comparing them with a bound on the optimal values. The fifth chapter addresses the problem of optimal spectrum management in continuous frequency domain in multiuser interference channels. The objective is to maximize the sum of user capacities. The main results are as follows: (i) For frequency-selective channels, it is proven that in an optimal solution, each user uses maximum power; this result also generalizes to the case where the objective is to maximize the product of user capacities (i.e., proportional fairness). (ii) For the special case of two users in flat channels, we solve the problem optimally.