Browsing by Author "Parthasarathy, Srinivasan"
Now showing 1 - 5 of 5
Results Per Page
Sort Options
Item Distributed Strategies for Channel Allocation and Scheduling in Software-defined Radio Networks(2008-01-14) Han, Bo; Kumar, V. S. Anil; Marathe, Madhav; Parthasarathy, Srinivasan; Srinivasan, AravindEquipping wireless nodes with multiple radios can significantly increase the capacity of wireless networks, by making these radios simultaneously transmit over multiple nonoverlapping channels. However, due to the limited number of radios and available orthogonal channels, designing efficient channel assignment and scheduling algorithms in such networks is a major challenge. In this paper, we present provably-good (centralized and distributed) algorithms for simultaneous channel allocation of individual links and packet-scheduling, in Software- Defined Radios (SDR) wireless networks. Our distributed algorithms are very simple to implement, and do not require any coordination even among neighboring nodes. A novel access hash function or random oracle methodology is one of the key drivers of our results. With this access hash function, each radio can know the transmitters’ decisions for links in its interference set for each time slot without introducing any extra communication overhead between them. Further, by utilizing the inductivescheduling technique, each radio can also backoff appropriately to avoid collisions. Extensive simulations demonstrate that our bounds are valid in practice.Item Fast Distributed Well Connected Dominating Sets for Ad Hoc Networks(2004-02-25) Parthasarathy, Srinivasan; Gandhi, RajivWe present the first distributed algorithms for computing connected dominating sets (CDS) for ad hoc networks that break the linear-time barrier. We present two algorithms which require O(Delta log^2(n)) and O(log^2(n)) running time respectively, where Delta is the maximum node degree and 'n' is the size of the network. This is a substantial improvement over existing implementations, all of which require Omega(n) running time. A basic primitive which underlies our first algorithm is Distance-2 coloring of the network. This primitive arises naturally in many applications such as broadcast scheduling and channel assignment. Minimizing the number of colors used in the coloring is very desirable for these applications, but this is known to be NP-hard. We present a fast distributed implementation of D2-coloring for ad hoc networks which is guaranteed to use at most O(1) times the number of colors required by the optimal algorithm. Our algorithms are geared towards constructing Well Connected Dominating Sets (WCDS) which have certain powerful and useful structural properties such as low size, low stretch and low degree. In this work, we also explore the rich connections between WCDS and routing in ad hoc networks. Specifically, we combine the properties of WCDS with other ideas to obtain the following interesting applications: * An online distributed algorithm for collision-free, low latency, low redundancy and high throughput broadcasting. * Distributed capacity preserving backbones for unicast routing and scheduling. Throughout this work, our focus is on obtaining distributed algorithms for ad hoc wireless networks with "provably good analytical we also explore the rich connections between WCDS and routing in ad hoc networks. Specifically, we combine the properties of WCDS with other ideas to obtain the following interesting applications: * An online distributed algorithm for collision-free, low latency, low redundancy and high throughput broadcasting. * Distributed capacity preserving backbones for unicast routing and scheduling. Throughout this work, our focus is on obtaining distributed algorithms for ad hoc wireless networks with "provably good analyticalItem A Protocol for Scalable Application Layer Multicast(2001-09-05) Banerjee, Suman; Bhattacharjee, Bobby; Parthasarathy, SrinivasanWe describe a new application-layer multicast protocol that is specifically designed to scale to large groups. Our scheme is based upon a hierarchical clustering of the application-layer multicast peers and can be used to produce a number of different data delivery trees with specific properties. On average, group members using our protocol maintain only a constant amount of state about other group members, and incur a constant amount of control overhead. We present extensive simulations of both our protocol and the Narada protocol over Internet-like topologies. Our results show that for groups of size 32 or more, we reduce control overhead by orders of magnitude, and link stress by 25%, while retaining similar end-to-end latencies and failure recovery properties.Item Resource Allocation in Networked and Distributed Environments(2006-08-30) Parthasarathy, Srinivasan; Srinivasan, Aravind; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)A central challenge in networked and distributed systems is resource management: how can we partition the available resources in the system across competing users, such that individual users are satisfied and certain system-wide objectives of interest are optimized? In this thesis, we deal with many such fundamental and practical resource allocation problems that arise in networked and distributed environments. We invoke two sophisticated paradigms -- linear programming and probabilistic methods -- and develop provably-good approximation algorithms for a diverse collection of applications. Our main contributions are as follows. Assignment problems: An assignment problem involves a collection of objects and locations, and a load value associated with each object-location pair. Our goal is to assign the objects to locations while minimizing various cost functions of the assignment. This setting models many applications in manufacturing, parallel processing, distributed storage, and wireless networks. We present a single algorithm for assignment which generalizes many classical assignment schemes known in the literature. Our scheme is derived through a fusion of linear algebra and randomization. In conjunction with other ideas, it leads to novel guarantees for multi-criteria parallel scheduling, broadcast scheduling, and social network modeling. Precedence constrained scheduling: We consider two precedence constrained scheduling problems, namely sweep scheduling and tree scheduling, which are inspired by emerging applications in high performance computing. Through a careful use of randomization, we devise the first approximation algorithms for these problems with near-optimal performance guarantees. Wireless communication: Wireless networks are prone to interference. This prohibits proximate network nodes from transmitting simultaneously, and introduces fundamental challenges in the design of wireless communication protocols. We develop fresh geometric insights for characterizing wireless interference. We combine our geometric analysis with linear programming and randomization, to derive near-optimal algorithms for latency minimization and throughput capacity estimation in wireless networks. In summary, the innovative use of linear programming and probabilistic techniques for resource allocation, and the novel ways of connecting them with application-specific ideas is the pivotal theme and the focal point of this thesis.Item Similarity Searching in Peer-to-Peer Databases(2004-02-25) Bhattacharya, Indrajit; Kashyap, Srinivas R.; Parthasarathy, SrinivasanWe consider the problem of handling "similarity queries" in peer-to-peer databases. Given a query for a data object, we propose an indexing and searching mechanism which returns the set of objects in the database that are semantically related to the query. Our schemes can be implemented on a variety of structured overlays such as CAN, CHORD, Pastry, and Tapestry. We provide analytical and experimental evaluation of our schemes in terms of the search accuracy, search cost, and load balancing. Our analytical guarantees perfectly predict the experimentally observed trends for the search accuracy.