Allocation Algorithms for Networks with Scarce Resources

Abstract

Many fundamental algorithmic techniques have roots in applications to computer networks. We consider several problems that crop up in wireless ad hoc networks, sensor networks, P2P networks, and cluster networks. The common challenge here is to deal with certain bottleneck resources that are crucial for performance of the underlying system. Broadly, we deal with the following issues. Data: The primary goal in resource replication problems is to replicate data objects on server nodes with limited storage capacities, so that the latency of client nodes needing these objects is minimized. Previous work in this area is heuristic and without guarantees. We develop tight (or nearly) approximation algorithms for several problems including basic resource replication - where clients need all objects and server can store at most one object, subset resource replication - where clients require different subsets of objects and servers have limited non-uniform capacity, and related variants. Computational resources: To facilitate packing of jobs needing disparate amounts of computational resources in cluster networks, an important auxiliary problem to solve is that of container selection. The idea is to select a limited number of containers'' that represent a given pool of jobs while minimizing wastage'' of resources. Subsequently, containers representing jobs can be packed instead of jobs themselves. We study this problem in two settings: continuous - where there are no additional restrictions on chosen containers, and discrete - where we must choose containers from a given set. We show that the continuous variant is NP-hard and admits a polynomial time approximation scheme. Contrastingly, the discrete variant is shown to be NP-hard to approximate. Therefore, we seek bi-approximation algorithms for this case.

Energy resources: Wireless ad hoc networks contain nodes with limited battery life and it is crucial to design energy efficient algorithms. We obtain tight approximation (up to constant factors) guarantees for partial and budgeted versions of the connected dominating set problem, which is regarded as a good model for a virtual backbone of a wireless ad hoc network. Further, we will discuss approximation algorithms for some problems involving target monitoring in sensor networks and message propagation in radio networks. We will end with a discussion on future work.