Wireless and mobile systems are becoming an ubiquitous part of everyday life. Some of the most common systems have become commoditized, enabling higher-layer application-driven research while at the same time inhibiting lower-layer research. On the other hand, new frontiers of wireless communications are opening up in various spectrum bands hitherto not used for wireless data communications. This talk will cover the future of wireless systems-driven research and contributions to science & technology from the vantage point of the National Science Foundation.

WiFi networks have been globally deployed and most mobile devices are currently WiFi-enabled. While WiFi has been proposed for multimedia content distribution, its lack of adequate support for multicast services hinders its ability to provide multimedia content distribution to a large number of devices. In this paper, we present the AMuSe system, whose objective is to enable scalable and adaptive WiFi multicast services. AMuSe is based on accurate receiver feedback and incurs a small control overhead. In particular, we develop an algorithm for dynamic selection of a subset of the multicast receivers as feedback nodes, which periodically send information about the channel quality to the multicast sender. This feedback information can be used by the multicast sender to optimize multicast service quality, e.g., by dynamically adjusting transmission bitrate. AMuSe does not require any changes to the standards or any modifications to the WiFi devices. We implemented AMuSe on the ORBIT testbed and evaluated its performance in large groups with approximately 200 WiFi devices, both with and without interference sources. Our extensive experiments demonstrate that AMuSe can provide accurate feedback in a dense multicast environment. It outperforms several alternatives even in the case of external interference and changing network conditions.

This paper considers a hybrid cellular architecture in which mobiles can communicate with others in their vicinity, e.g. using 802.11 interface, in addition to the base stations of the cellular network. Such an architecture can aid device-to-device communication as well as assist critical tasks of cellular networks such as mobility management, content caching and relaying. In order to enable these capabilities, base stations need to have sufficient knowledge of the underlying network topology induced by the 802.11 links of the mobiles. Due to the dynamic nature of this network, a compressed snapshot of its topology should be collected within a very short time duration and with minimal communication among mobiles. Addressing this need, we propose a compact topology representation that is suitable for a number of applications. We utilize the broadcast nature of wireless channels to design an efficient topology detection algorithm that acquires a compact representation of the underlying network (at most 3N links and a low `stretch' factor for the N mobiles) within a short duration (10s of ms). Our scheme does not have collision resolution, backoffs or any of the other MAC layer inefficiencies.

Scalable, low-latency and accurate RFID counting algorithms have recently been proposed as a fundamental building block to support more complex query operations in a large-scale RFID system. One distinct feature of these algorithms is that they do not require explicit identification of individual tags and therefore can eliminate the latency bottleneck caused by serialization during multiple access control. However, these algorithms all assume reliable communications between the reader and the tags. While this assumption is also adopted by many tag-identification protocols in the current RFID standards, it is practically unachievable given the current technology and low-cost requirement of RFID tags. In fact, recent empirical studies have found that the communication between an RFID reader and a set of seemingly “in-range” tags are still unreliable and highly non-deterministic due to the varying channel conditions. In this paper, we discuss the design and performance analysis of a set of channel-oblivious RFID counting algorithms which can estimate the size of a tag-set of interest over unreliable wireless channels. The proposed schemes can provide accurate cardinality estimates without any prior knowledge of the channel parameters. We first propose a series of algorithms and analyze their performance under a simplified memoryless lossy channel model. We then extend them to handle the impact due to backscattering effects and correlated losses found in practical RFID systems. Our proposed designs only require simple modifications to standard RFID tags and readers and can be implemented using current technologies with minimal increase in tag/ reader cost. Our designs can also be extended to other RFID counting algorithms which assumed reliable communication channels.

Core and aggregation optical networks are remarkably static, despite the emerging dynamic capabilities of the individual optical devices. This stems from the inability to address optical impairments in real-time. As a result, tasks such as adding and removing wavelengths take a substantial amount of time, and therefore, optical networks are over-provisioned and inefficient in terms of capacity and energy. Optical Performance Monitors (OPMs) that assess the Quality of Transmission (QoT) in real-time can be used to overcome these inefficiencies. However, prior work mostly focused on the single link level. In this paper, we present a network-wide optimization algorithm that leverages OPM measurements to dynamically control the wavelengths' power levels. Hence, it allows adding and dropping wavelengths quickly while mitigating the impacts of impairments caused by these actions, thereby facilitating efficient operation of higher layer protocols. We evaluate the algorithm's performance using a network-scale optical simulator under real-world scenarios and show that the ability to add and drop wavelengths dynamically can lead to significant power savings. Moreover, we experimentally evaluate the algorithm in an optical testbed and discuss the practical implementation issues. To the best of our knowledge, this paper is the first attempt at providing a global power control algorithm that uses live OPM measurements to enable dynamic optical networking.

IEEE 802.11-based wireless local area networks, referred to as WiFi, have been globally deployed and the vast majority of mobile devices are currently WiFi-enabled. While WiFi has been proposed for multimedia content distribution, its lack of adequate support for multicast services hinders its ability to provide multimedia content distribution to a large number of devices. We propose AMuSe, a scalable and adaptive interference mitigation solution for WiFi multicast services which is based on accurate receiver feedback and that incurs a small control overhead. Specifically, we develop a scheme for dynamic selection of a subset of the multicast receivers as feedback nodes, which periodically send information, such as channel quality or received packet statistics, to the multicast sender. This feedback information is used by the multicast sender to optimize the multicast service quality, e.g., by dynamically adjusting the transmission bit-rate. Our proposed solution does not require any changes to the standards or any modifications to the WiFi devices. We have implemented the proposed solution in the ORBIT testbed and evaluated its performance in large groups with approximately 250 receivers, both with and without interference sources. Our online experiments demonstrate that our system provides practical multicast services that can accommodate hundreds of receivers.

Core and aggregation optical networks are remarkably static, despite the emerging dynamic capabilities of the individual optical devices. This stems from the inability to address optical impairments in real-time. As a result, tasks such as adding and removing wavelengths take a substantial amount of time, and therefore, optical networks are over-provisioned and inefficient in terms of capacity and energy. Optical Performance Monitors (OPMs) that assess the Quality of Transmission (QoT) in real-time can be used to overcome these inefficiencies. However, prior work mostly focused on the single link level. In this paper, we present a network-wide optimization algorithm that leverages OPM measurements to dynamically control the wavelengths' power levels. Hence, it allows adding and dropping wavelengths quickly while mitigating the impacts of impairments caused by these actions, thereby facilitating efficient operation of higher layer protocols. We evaluate the algorithm's performance using a network-scale optical simulator under real-world scenarios and show that the ability to add and drop wavelengths dynamically can lead to significant power savings. Moreover, we experimentally evaluate the algorithm in an optical testbed and discuss the practical implementation issues. To the best of our knowledge, this paper is the first attempt at providing a global power control algorithm that uses live OPM measurements to enable dynamic optical networking.

Geographically distributed storage is an important method of ensuring high data availability in cloud computing and storage systems. With the increasing demand for moving file systems to the cloud, current methods of providing such enterprise-grade resiliency are very inefficient. For example, replication based methods incur large storage cost though they provide low access latencies. While erasure coded schemes reduce storage cost, they are associated with large access latencies and high bandwidth cost. In this paper, we propose a novel scheme named CAROM, an ensemble of replication and erasure codes, to provide resiliency in cloud file systems with high efficiency. While maintaining the same consistency semantics seen in today's cloud file systems, CAROM provides the benefit of low bandwidth cost, low storage cost, and low access latencies. We perform a large-scale evaluation using real-world file system traces and demonstrate that CAROM outperforms replication based schemes in storage cost by up to 60% and erasure coded schemes in bandwidth cost by up to 43%, while maintaining low access latencies close to those in replication based schemes.

Cloud service providers (CSP) of today operate multiple data centers, over which they provide resilient infrastructure, data storage and compute services. The links between data centers have very high capacity, and are typically purchased by the CSPs using established billing practices, such as 95-thpercentile billing or average-usage billing. These links are used to serve both client traffic as well as CSP-specific bulk data traffic, such as backup jobs, etc. Past studies have shown a diurnal pattern of traffic over such links. However, CSPs pay for the peak bandwidth, which implies that they are under-utilizing the capacity for which they have paid for. We propose a scheduling framework that considers various classes of jobs that are encountered over such links, and propose GRESE, an algorithm that attempts to minimize overall bandwidth costs to the CSP, by leveraging the flexible nature of the deadlines of these bulk data jobs. We demonstrate the problem is not a simple extension of any well-known scheduling problems, and show how the GRESE algorithm is effective in curtailing CSP bandwidth costs.

Enterprises are moving their IT infrastructure to cloud service providers with the goal of saving costs and simplifying management overhead. One of the critical services for any enterprise is its file system, where users require real-time access to files. Cloud service providers provide several building blocks such as Amazon EBS, or Azure Cache, each with very different pricing structures that differ on the basis of storage, access and bandwidth costs. Moving an entire file system to the cloud using such services is not cost-optimal if we rely on only one of these services. In this paper, we propose FCFS, a storage solution that drastically reduces the cost of operating a file system in the cloud. Our solution integrates multiple storage services and dynamically adapts the storage volume sizes of each service to provide a cost-efficient solution with provable performance bounds. Using real-world large scale data sets spanning a variety of work loads from an enterprise data center, we show that FCFS can reduce file storage and access costs in current cloud services by a factor of two or more, while allowing users to utilize the benefits of the various cloud storage services.

We investigate the potential trade-off between energy efficiency and latency of file transmission over IP and Optical domains. We consider various queueing disciplines that are applicable to these domains, and show that existing schemes achieve only one at the expense of the other. We show that we can simultaneously achieve low-latency file transfers in an energy-efficient manner using an intuitive approach that is easy to implement in next-generation networks.

A low-latency, accurate RFID counting scheme can be used as a fundamental building block to support more elaborated RFID query operations. RFID counting algorithms of such nature have been proposed recently by Kodialam et. al.. One distinct feature of these schemes is that they do not require the reader to explicitly identify individual tags and thus can help to preserve privacy of the RFID users. However, these schemes all assume a perfect communication channel between the reader and the tags which is not achievable in practice. Recent empirical measurement studies have found that the radio communication between an RFID reader and a set of seemingly “in-range” tags are still unreliable and non-deterministic due to ever-changing channel conditions. Worse still, given the stringent cost constraint, it is unlikely that standard channel estimation procedures can be applied for individual tags. In this paper, we propose two new algorithms which can provide good estimates of the size of an RFID tag-set over unreliable, lossy wireless channels while assuming minimal or no prior knowledge of channel parameters. These algorithms are scalable over a wide range of tag-set size using a small, fixed protocol frame-size, which is critical for low-cost RFID tags with typically sub-par synchronization or timing control. They are also adaptive in the sense that, they self-tune the algorithm parameters according to the tag-set size and channel characteristics. This set of features makes them applicable in a wide variety of situations where the reader is unaware of or has very limited knowledge of the channel conditions. We also demonstrate the efficacy of the proposed schemes via extensive simulation studies.

Physical layer capture is one of the basic causes of throughput unfairness in IEEE 802.11 Wireless LANs. While papers have analyzed the impact of capture on the overall throughput of a single 802.11 cell, we are unaware of any analysis of the relative unfairness among users as result of capture. Since this unfairness is related to the relative location of users, we call this as spatial unfairness. We provide, to the best of our knowledge, the first such analysis that characterizes the relative throughput of users as a function of the users' distance from the access point (AP). We experimentally validate our analysis using a single 802.11b cell testbed.

Given a large set of RFID tags, we are interested in determining the categories of tags that are present in the shortest time possible. Since there can be more than one tag present in a particular category, pure randomized strategies that rely on resolving individual tags are very inefficient. Instead, we rely on a pseudo-random strategy that utilizes a uniform hash function to accurately identify all t categories present among a given set of ψ tags with high probability. We propose two algorithms: (a) a single frame algorithm that determines the optimal frame size, and (b) a probabilistic version where the frame size is fixed, and we select the probability to minimize the number of frames needed for identification. Both of these algorithms run in time linear to the number of categories present, t. We show that our approach significantly outperforms existing algorithms for category identification. The performance of our algorithms is within a constant factor of the lower bound.

The increasing use of RFID tags in many applications have brought forth valid concerns of privacy and anonymity among users. One of the primary concerns with RFID tags is their ability to track an individually tagged entity. While this capability is currently thought to be necessary for supporting some features of RFID systems, such practice can lead to potential privacy violations. In this paper, we propose a privacy-preserving scheme that enables anonymous estimation of the cardinality of a dynamic set of RFID tags, while allowing the set membership to vary in both the spatial and temporal domains. In addition, the proposed scheme can identify the dynamics of the changes in the tag set population. The main idea of the scheme is to avoid explicit identification of tags. We demonstrate that the proposed scheme is highly adaptive and can accurately estimate tag populations across many orders of magnitude, ranging from a few tens to millions of tags. The associated probing latency is also substantially lower (les 10%) than that of the schemes which require explicit tag identification. We also show that our proposed scheme performs well even in highly dynamic environments, where the tag set keeps changing rapidly.

In modern cellular networks, the channel quality is dynamic among users and also over time. The time-granularity for such dynamics is significantly diverse - either slow or fast compared to packet transmission time. Because of these issues most existing scheduling policies can not work consistently well. In this work, we propose a scheduling policy with performance relatively insensitive to the time-granularity of the dynamics of channel quality. Our policy is self-adaptive to the scale of channel variations by using an ensemble of proposed algorithms. The proposed scheduling policy is proved to have a worst-case performance bound in the existence of both slow and fast time-varying channels. Simulation results confirm that the policy better tolerates channel variations than other popular schemes such as EDF and the Greedy algorithm.

RFID tags are being used in many diverse applications in increasingly large numbers. These capabilities of these tags span from very dumb passive tags to smart active tags, with the cost of these tags correspondingly ranging from a few pennies to many dollars. One of the common problems that arise in any RFID deployment is the problem of quick estimation of the number of tags in the field up to a desired level of accuracy. Prior work in this area has focused on the identification of tags, which needs more time, and is unsuitable for many situations, especially where the tag set is dense. We take a different, more practical approach, and provide very fast and reliable estimation mechanisms. In particular, we analyze our estimation schemes and show that the time needed to estimate the number of tags in the system for a given accuracy is much better than schemes presented in related work. We show that one can estimate the cardinality of tag-sets of any size in near-constant time, for a given accuracy of estimation.

Next generation fixed wireless broadband networks are being increasingly deployed as mesh networks in order to provide and extend access to the internet. These networks are characterized by the use of multiple orthogonal channels and nodes with the ability to simultaneously communicate with many neighbors using multiple radios (interfaces) over orthogonal channels. Networks based on the IEEE 802.11a/b/g and 802.16 standards are examples of these systems. However, due to the limited number of available orthogonal channels, interference is still a factor in such networks. In this paper, we propose a network model that captures the key practical aspects of such systems and characterize the constraints binding their behavior. We provide necessary conditions to verify the feasibility of rate vectors in these networks, and use them to derive upper bounds on the capacity in terms of achievable throughput, using a fast primal-dual algorithm. We then develop two link channel assignment schemes, one static and the other dynamic, in order to derive lower bounds on the achievable throughput. We demonstrate through simulations that the dynamic link channel assignment scheme performs close to optimal on the average, while the static link channel assignment algorithm also performs very well. The methods proposed in this paper can be a valuable tool for network designers in planning network deployment and for optimizing different performance objectives.

Abstract Next‐generation 3G/4G wireless data networks allow multiple codes (or channels) to be allocated to a single user, where each code can support multiple data rates. Providing fine‐grained QoS to users in such networks poses the two‐dimensional challenge of assigning both power (rate) and codes to every user. This gives rise to a new class of parallel scheduling problems. We abstract general downlink scheduling problems suitable for proposed next‐generation wireless data systems. Our contribution includes a communication‐theoretic model for multirate wireless channels. In addition, while conventional focus has been on throughput maximization, we attempt to optimize the maximum response time of jobs, which is more suitable for streams of user requests. We present provable results on the algorithmic complexity of these scheduling problems. In particular, we are able to provide very simple, on‐line algorithms for approximating the optimal maximum response time. We also perform an experimental study with realistic data of channel conditions and user requests that strengthens our theoretical results. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 45(1), 9–22 2005

This paper considers the problem of determining the achievable rates in multi-hop wireless mesh networks with orthogonal channels. We classify wireless networks with orthogonal channels into two types, half duplex and full duplex, and consider the problem of jointly routing the flows and scheduling transmissions to achieve a given rate vector. We develop tight necessary and sufficient conditions for the achievability of the rate vector. We develop efficient and easy to implement Fully Polynomial Time Approximation Schemes for solving the routing problem. The scheduling problem is a solved as a graph edge-coloring problem. We show that this approach guarantees that the solution obtained is within 50% of the optimal solution in the worst case (within 67% of the optimal solution in a common special case) and, in practice, is close to 90% of the optimal solution on the average. The approach that we use is quite flexible and can be extended to handle more sophisticated interference conditions, and routing with diversity requirements.

The effect of interference on the achievable rate region in multihop wireless networks under three increasingly constraining interference models network throughput characterization namely primary conflict avoidance, receiver conflict avoidance and transmitter-receiver conflict avoidance is studied in this paper. The necessary conditions for achievability in the three models as linear constraints, and the structure of these constraints to develop efficient fully polynomial time approximation algorithms that route end-to-end flows between multiple source destination pairs are exploited. The techniques developed in this paper are applicable to a wide range of problems, including capacity problems, arising in multihop networks with interference constraints.

The exponential growth of mobile data users and services places a heavy burden on the limited wireless bandwidth of cellular data networks. The situation will be exacerbated with the advent of high bandwidth multimedia applications for mobile devices. We propose an architecture called the cellular-based ad hoc peer data sharing system (CAPS) to reduce the load on the cellular network while improving request response times. In CAPS, mobile hosts in a cellular network form an overlay multihop wireless network. This ad hoc network acts as a 'virtual cache' that enables data sharing among mobile hosts. Participating mobiles share the contents of their local caches with other mobiles. A subset of mobile hosts keep track of the location of objects with minimal overhead. Using CAPS, popular objects can be obtained over the ad hoc network without accessing the cellular infrastructure, thereby reducing the load on the cellular network and improving data access latency. We have extensively evaluated the performance of this architecture through simulations in ns-2 across a wide range of scenarios, and find that CAPS reduces the timeouts of the user requests by 70-90% and reduces the load at the base station by up to 60%.

This paper considers the problem of determining the achievable rates in multi-hop wireless networks. We consider the problem of jointly routing the flows and scheduling transmissions to achieve a given rate vector. We develop tight necessary and sufficient conditions for the achievability of the rate vector. We develop efficient and easy to implement Fully Polynomial Time Approximation Schemes for solving the routing problem. The scheduling problem is a solved as a graph edge-coloring problem. We show that this approach guarantees that the solution obtained is within 67% of the optimal solution in the worst case and, in practice, is typically within about 80% of the optimal solution. The approach that we use is quite flexible and is a promising method to handle more sophisticated interference conditions, multiple channels, multiple antennas, and routing with diversity requirements.

Next generation 3G/4G wireless data networks allow multiple codes (or channels) to be allocated to a single user, where each code can support multiple data rates. Providing fine-grained QoS to users in such networks poses the two dimensional challenge of assigning both power (rate) and codes for every user. This gives rise to a new class of parallel scheduling problems. We abstract general downlink scheduling problems suitable for proposed next generation wireless data systems. This includes a communication-theoretic model for multirate wireless channels. In addition, while conventional focus has been on throughput maximization, we attempt to optimize the maximum response time of jobs, which is more suitable for stream of user requests. We present provable results on the algorithmic complexity of these scheduling problems. In particular, we are able to provide very simple, online algorithms for approximating the optimal maximum response time. This relies on resource augmented competitive analysis. We also perform an experimental study with realistic data of channel conditions and user requests to show that our algorithms are more accurate than our worst case analysis shows, and they provide fine-grained QoS to users effectively.

We present a core-stateless quality of service architecture for achieving delay differentiation between flows. There are two key components in our approach: (1) per-class per-hop relative average delay-the average queueing delay perceived by the packets in a delay class at a link is inversely proportional to the delay weight of the class; (2) per-flow end-to-end delay class adaptation-the delay class of a flow is dynamically adjusted based on its perceived end-to-end delay in order to maintain the desired end-to-end average delay requirement of the flow. We show through simulations and analysis that these two components can, in concert, support end-to-end delay differentiation between flows using only simple mechanisms at the core routers in the network.

Link-layer fairness models that have been proposed for wireline and packet cellular networks cannot be generalized for shared channel wireless networks because of the unique characteristics of the wireless channel, such as location-dependent contention, inherent conflict between optimizing channel utilization and achieving fairness, and the absence of any centralized control.

Fair queueing in the wireless domain poses significant challenges due to unique issues in the wireless channel such as location-dependent and bursty channel error. In this paper, we present a wireless fair service model that captures the scheduling requirements of wireless scheduling algorithms, and present a unied wireless fair queueing architecture in which scheduling algorithms can be designed to achieve wireless fair service. We map seven recently proposed wireless fair scheduling algorithms to the unied architecture, and compare their properties through simulation and analysis. We conclude that some of these algorithms achieve the properties of wireless fair service including short-term and long-term fairness, short-term and long-term throughput bounds, and tight delay bounds for channel access.

Many current wireless wide area packet data networks are characterized by very low and variable bandwidths, very high and variable delays, significant non-congestion related loss, asymmetric uplink and downlink channels, and occasional blackouts. Additionally, the majority of the latency in a WWAN connection is incurred over the wireless link. Under such operating conditions, most contemporary wireless TCP algorithms do not perform very well. Sinha, Venkitaraman, Sivakumar and Bharghavan (see Proc. of ACM Mobicom '99, 1999) we presented WTCP, a reliable transport protocol that is designed to operate efficiently and fairly over wireless wide area networks. WTCP is rate-based, uses only end-to-end mechanisms, performs rate control at the receiver, and uses the ratio of sending rate to receiving rate as as the primary metric for rate control. In this paper, we evaluate the performance of WTCP over CDPD networks. We have implemented and evaluated WTCP over the CDPD network, and also simulated it in the ns-2 simulator. Our performance results indicate that WTCP can improve on the performance of comparable algorithms such as TCP-NewReno and TCP-Vegas by between 20% to 200% for typical operating conditions.

b order to support diverse communication-intensive redtirne and non red-time data flows over a scarce, varying and shared wireless channel with location-dependent and bursty errors, we defie a service model that has the following charxteristi~short-tern fairness among flows which perceive a clean channel, worst-case delay bounds for packets, short-term throughput bounds for flows with clean channels and Iong-tem throughput bounds for dl flows with bounded channel error, optimal schedulable region, and support for both delay sensitive and error sensitive data flows.We present a wireless fair service algorithm, and show that it achieves the requirements of the service model through both analysis and simulation.The key aspects of the dg~ rithm are the following (a) an enhanced fair queueing based service scheme that supports decoupling of delay and bandwidth, (b) graceful service compensation for lagging flows and graceful service degradation for leading flows, (c) support for red-time delay sensitive flows as well as non realtime error sensitive flows, and (d) implementation of the wireless fair service rdgorithm within the fiarnework of the simple and robust CSMA/CA wireless medium access pro tocol.