INFOCOM 2016 Papers

Embedded screen-camera communication techniques encode information in screen imagery that can be decoded with a camera receiver yet remains unobtrusive to the human observer. These techniques have applications in tagging content on screens similar to QR-code tagging for other objects. This paper characterizes the design space for flicker-free embedded screen-camera communication. In particular, we identify an orthogonal dimension to prior work: spatial content-adaptive encoding, and observe that it is essential to combine multiple dimensions to achieve both high capacity and minimal flicker. From these insights, we develop content-adaptive encoding techniques that exploit visual features such as edges and texture to unobtrusively communicate information. These can then be layered over existing techniques to further boost the capacity. Our experimental results show that there is potential to achieve an average goodput of about 22 kbps, significantly outperforming existing work while remaining flicker-free.

We investigate emerging proximity-based Mobile Crowd Service or pMCS systems, in which services are provided and consumed by users carrying smart mobile devices (e.g., smartphones) and in proximity of each other (e.g., within Bluetooth range). Due to limited resources on smartphones, it is crucial to provide a mechanism to incentivize users' participation and ensure fair trading in a pMCS system. In this paper, we design a multi-market dynamic double auction mechanism for a pMCS system, referred to as MobiAuc, and we show that it is truthful, feasible, individual-rational, no-deficit, and computationally efficient. The novelty and significance of MobiAuc is that it addresses and solves the fair trading problem in a multi-market dynamic double auction setting which naturally occurs in a mobile wireless environment. We demonstrate its efficiency via simulations based on generated user patterns (stochastic arrivals and random market clustering of users) and real-world traces. Our preliminary implementation of MobiAuc and experiments on Android platform have demonstrated the feasibility of MobiAuc mechanism in practice.

Being able to determine the location of a node is of great advantage in many IoT and WSN applications. For example, in health care scenarios or for autonomous configuration of IoT setups this information can be useful. One of the key challenges in localization is to estimate the distance between nodes. Most present indoor localization systems require additional hardware for this estimation which is costly in terms of money and energy consumption. To overcome this disadvantage, we developed a system which is able to perform distance measurements without adding any extra hardware and costs. It is based on phase measurements performed by the IEEE 802.15.4 transceiver chip that is normally solely used to realize communication. In the evaluation we investigate the performance of our system in different real world environments that are typical for IoT and WSN setups.

The stability and throughput of the Slotted Aloha protocol have been studied at length, yielding results that depend on the environment and channel assumptions, in many cases indicating e-1 as the S-Aloha capacity. When users can detect only their own collisions, and the number of users N goes to infinity, no definite capacity result exists. Approximated models have been introduced to study the exponential back-off mechanism, which seem to indicate an asymptotic capacity of ln(2)/2 when binary back-off is used, and again e-1 when the exponential base is optimized. Here we introduce a more accurate and flexible model that shows that past results miss their mark. In fact, we prove that with binary back-off the capacity is practically 0.370, slightly greater than e-1; furthermore, and more important, we prove that using 1.35 as exponential back-off base, the capacity reaches 0.4303 with an infinite number of users, and up to 0.496 with N = 2 users.

User-centric base station (BS) cooperation has been regarded as an effective solution to improve network coverage and throughput in next-generation wireless systems. However, it also introduces more complicated handoff patterns, which may potentially degrade user performance. In this paper, we aim to quantify the number of handoffs in user-centric cooperative wireless networks. The challenges are two-fold: (1) BSs are spatially randomly deployed, and (2) user-centric BS cooperation further creates complicated network topologies so that it is difficult to track handoffs in the system. We propose a stochastic geometric analysis framework on user mobility, to derive a theoretical expression for the handoff rate experienced by an active user with arbitrary movement trajectory. Furthermore, we characterize the average downlink user data rate under a common non-coherent joint-transmission scheme, which is used to illustrate the tradeoff between handoff rate and data rate in optimizing the cooperative cluster size for each user. Finally, computer simulation is conducted to validate the correctness and usefulness of our analysis.

To achieve scalable, high-throughput, low-latency packet processing, TCP implementations are parallelized across cores in multicore platforms. This, however, significantly affects the order in which packets from different flows are delivered to application processing. Our measurements record up to 75% of the packets are delivered to applications in a way that does not match the order in which they are received on the network interface. For many important classes of applications, such as financial services, bidding and trading engines, game engines, this cross-flow packet reordering affects their ability to provide fairness guarantees. To address this gap, we propose TCP-Ordo - a TCP stack which provides strict ordering of packets across multiple flows, as well as flexibility to control the degree to which ordering is enforced. TCP-Ordo outperforms existing TCP implementations in both latency and throughput. The current prototype is implemented as a user-level TCP stack for Mellanox Connectx3 NICs with 40Gbps Ethernet interfaces. Without ordering guarantees TCP-Ordo delivers one way latency of 4.75usec (a 5x improvement over the Linux kernel) for 150B packets and throughput of 22Gbps (a 2x improvement over mTCP) for 1500B packets. Furthermore, with TCP-Ordo applications are provided with strict packet order delivery, with performance that continues to be superior to the state-of-the-art, even when enforcing packet order across 800,000 connections on a 12-core platform. Finally, TCP-Ordo supports the notion of `ordered domains' that offer flexibility in the degree of ordering that an application will experience, and pay for.

Online social networks have gained significant popularity recently. The problem of influence maximization in online social networks has been extensively studied. However, in prior works, influence propagation in the physical world, which is also an indispensable factor, is not considered. The Location-Based Social Networks (LBSNs) are a special kind of online social networks in which people can share location-embedded information. In this paper, we make use of mobile crowdsourced data obtained from location-based social network services to study influence maximization in LBSNs. A novel network model and an influence propagation model taking influence propagation in both online social networks and the physical world into consideration are proposed. An event activation position selection problem is formalized and a corresponding solution is provided. The experimental results indicate that the proposed influence propagation model is meaningful and the activation position selection algorithm has high performance.

In multi-tenant cloud environments, the absence of strict network performance guarantees leads to unpredictable job execution times. To address this issue, recently there have been several proposals on how to provide guaranteed network performance. These proposals, however, rely on computing resource reservation schedules a priori. Unfortunately, this is not practical in today's cloud environments, where application demands are inherently unpredictable, e.g., due to differences in the input datasets or phenomena such as failures and stragglers. To overcome these limitations, we designed KRAKEN, a system that allows tenants to dynamically request and update minimum guarantees for both network bandwidth and compute resources at runtime. Unlike previous work, Kraken does not require prior knowledge about the resource needs of the tenants' applications but allows tenants to modify their reservation at runtime. Kraken achieves this through an online resource reservation scheme which comes with provable optimality guarantees. In this paper, we motivate the need for dynamic resource reservation schemes, present how this is provided by Kraken, and evaluate Kraken via extensive simulations.

Typically called big data processing, processing large volumes of data from geographically distributed regions with machine learning algorithms has emerged as an important analytical tool for governments and multinational corporations. The traditional wisdom calls for the collection of all the data across the world to a central datacenter location, to be processed using data-parallel applications. This is neither efficient nor practical as the volume of data grows exponentially. Rather than transferring data, we believe that computation tasks should be scheduled where the data is, while data should be processed with a minimum amount of transfers across datacenters. In this paper, we design and implement Flutter, a new task scheduling algorithm that improves the completion times of big data processing jobs across geographically distributed datacenters. To cater to the specific characteristics of data-parallel applications, we first formulate our problem as a lexicographical min-max integer linear programming (ILP) problem, and then transform it into a nonlinear program with a separable convex objective function and a totally unimodular constraint matrix, which can be solved using a standard linear programming solver efficiently in an online fashion. Our implementation of Flutter is based on Apache Spark, a modern framework popular for big data processing. Our experimental results have shown that we can reduce the job completion time by up to 25%, and the amount of traffic transferred among datacenters by up to 75%.

Recently, Visible Light Communication (VLC) over a screen-camera channel has drawn considerable attention to unobtrusive design. It overcomes the distractive nature of traditional coded image approaches (e.g., barcodes). Previous unobtrusive methods fall into two categories: 1) utilizing alpha channel, a well known concept in computer graphics, to encode bits into the pixel translucency change with off-the-shelf smart devices; and 2) leveraging the spatial-temporal flicker-fusion property of human vision system with the fast frame rate of modern displays. However, these approaches heavily rely on high-end devices to achieve both unobtrusive and high accuracy screen-camera-based data communication without affecting video-viewing experience. Unlike previous approaches, we propose Uber-in-light, a novel unobtrusive and accurate VLC system, that enables real-time screen-camera communication, applicable to any screen and camera. The proposed system encodes the data as complementary intensity changes over Red, Green, and Blue (RGB) color channels that could be successfully decoded by camera while leaving the human visual perception unaffected. We design a MFSK modulation scheme with dedicated frame synchronization signal embedded in an orthogonal color channel to achieve high throughput. Furthermore, together with the complementary color intensity, an enhanced MUSIC-based demodulation scheme is developed to ensure highly accurate data transmission. Our user experience experiments confirmed the effectiveness of delivering unobtrusive data across different types of video content and resolutions. Extensive real-time performance evaluations are conducted using our prototype implementation to demonstrate the efficiency and reliability of the proposed system under diverse wireless environments.

Even though indoor smoking ban is being put into practice in civilized countries, existing vision or sensor-based smoking detection methods cannot provide ubiquitous smoking detection. In this paper, we take the first attempt to build a ubiquitous passive smoking detection system, which leverages the patterns smoking leaves on WiFi signals to identify the smoking activity even in the non-line-of-sight and through-wall environments. We study the behaviors of smokers and leverage the common features to recognize the series of motions during smoking, avoiding the target-dependent training set to achieve the high accuracy. We design a foreground detection based motion acquisition method to extract the meaningful information from multiple noisy subcarriers even influenced by posture changes. Without requirements of target's compliance, we leverage the rhythmical patterns of smoking to reduce the detection false positives. We prototype Smokey with the commodity WiFi infrastructure and evaluate its performance in real environments. Experimental results show Smokey is accurate and robust in various scenarios.

As a major driving force for adopting cloud computing, continuous cost reduction has been constantly pursued by cloud users. For a group of users with heterogeneous cloud resource demands, it may be possible for them to buy resources in a collaborative way in order to save the purchase cost, which is known as group-buying in business. While group-buying can benefit cloud users in principle, the question is how to design an implementation scheme to support group-buying on the cloud market. In this paper, we address the question by studying a coalition formation game, aiming to design a way under which the users can form stable coalitions for group-buying. It turns out that group-buying on the cloud market is challenging in that most popular solution concepts may fail to constitute stable coalitions. In order to sustain group-buying for cloud services, we propose a new solution concept, contractually group stable, which is an extension of an existing concept in the literature. We show that this new solution concept can guarantee the existence of stable coalitions, making group-buying always possible on the cloud market. We also develop computing algorithms for solving the coalition formation game under our concept. Computational experiments show that our concept can bring in substantial cost reduction for cloud users.

Visual Sensor Networks (VSNs) have been recently used for implementing automatic visual analysis tasks where local image features, instead of images, are compressed and transmitted to a central controller. Such features may also be compressed in a multi-view fashion, exploiting the redundancy between overlapping views. In this paper we analyze the problem of multi-view coding and routing of features in VSNs. We empirically analyze the relationship between the bitrate reduction obtained with a practical multi-view local features encoder and several geometry-based, image-based and feature-based predictors. The purpose of this analysis is to identify the most accurate, yet compact predictor of the achievable compression efficiency when jointly encoding correlated streams of local features. Then, we propose a robust optimization framework that exploits the aforementioned predictors. The proposed mathematical problem maximizes the amount of data extracted from the VSN by properly routing the streams of features, subject to capacity, interference and energy constraints, explicitly considering the uncertainty in the compression efficiency estimation. Extensive experiments on simulated VSNs show that multi-view coding maximizes the amount of data extracted from camera nodes, while the robust optimization approach provides significant improvement in uncertain scenarios compared to the optimal solution of a deterministic approach.

This paper presents BlueAer, the first three-dimensional (3D) spatial-temporal fine particulate matter (PM2.5) monitoring system, which is designed to understand urban PM2.5concentration distribution in a fine-grained level. For cost-efficient data collection, vast amount of 3D samples are collected by limited mobile carriers with built-in low-cost sensors. A 3D probabilistic concentration estimated method (3D-PCEM) is proposed to infer PM2.5concentration for undetected area, so that the accuracy of BlueAer is ensured. A prototype system of BlueAer has been implemented and worked throughout a year in a 64km2testing area with a population of 400,000 in Hangzhou, China. Experimental data has verified that BlueAer can achieve good performance in terms of stability as well as a fine grained 3D distribution of PM2.5concentration. The inference accuracy of 3D-PCEM is enhanced by 15.4% and 41.0%, comparing to Gaussian Process (GP) and Artificial Network (ANN) respectively. BlueAer can easily be extended for a larger scale and applied city-wise. Besides, our findings can help ordinary citizens better understand their immediate air quality and serve as a framework towards detailed national-wise real-time pollution management.

Community detection aims to reveal the community structure in a social network, which is one of the fundamental problems. In this paper we investigate the community detection problem based on the concept of terminal set. A terminal set is a group of users within which any two users belong to different communities. Although the community detection is hard in general, the terminal set can be very helpful in designing effective community detection algorithms. We first present a 2-approximation algorithm running in polynomial time for the original community detection problem. In the other issue, in order to better support real applications we further consider the case when extra restrictions are imposed on feasible partitions. For such customized community detection problems, we provide two randomized algorithms which are able to find the optimal partition with a high probability. Demonstrated by the experiments performed on benchmark networks the proposed algorithms are able to produce high-quality communities.

Recent years have witnessed the prevalence of wearable devices. Wearable devices are intelligent and multifunctional, but they rely heavily on batteries. This greatly limits their application scope, where replacement of battery or recharging is challenging or inconvenient. We note that wearable devices have the opportunity to harvest energy from human motion, as they are worn by the people as long as being functioning. In this study, we propose a battery-free sensing platform for wearable devices in the form-factor of shoes. It harvests the kinetic energy from walking or running to supply devices with power for sensing, processing and wireless communication, covering all the functionalities of commercial wearable devices. We achieve this goal by enabling the whole system running on the harvested energy from two feet. Each foot performs separate tasks and two feet are coordinated by ambient backscatter communication. We instantiate this idea by building a prototype, containing energy harvesting insoles, power management circuits and ambient backscatter module. Evaluation results demonstrate that the system can wake up shortly after several seconds' walk and have sufficient Bluetooth throughput for supporting many applications. We believe that our framework can stir a lot of useful applications that were infeasible previously.

We study the problem of load balancing in datacenter networks, namely, assigning the end-to-end data flows among the available paths in order to efficiently balance the load in the network. The solutions used today rely typically on ECMP (Equal Cost Multi Path) mechanism which essentially attempts to balance the load in the network by hashing the flows to the available shortest paths. However, it is well known that ECMP performs poorly when there is asymmetry either in the network topology or the flow sizes, and thus there has been much interest recently in alternative mechanisms to address these shortcomings. In this paper, we consider a general network topology where each link has a cost which is a convex function of the link utilization. Flows among the various source-destination pairs are generated dynamically over time, each with a size (bandwidth requirement) and a duration. Once a flow is assigned to a path in the network, it consumes bandwidth equal to its size from all the links along its path for its duration. We propose a low-complexity congestion-aware algorithm that assigns the flows to the available paths in an online fashion and without splitting, and prove that it asymptotically minimizes the total network cost. Extensive simulation results are presented to verify the performance of our algorithm under a wide range of traffic conditions and under different datacenter architectures.

Backscatter communication networks receive much attention recently due to the small size and low power of backscatter nodes. As backscatter communication is often influenced by the dynamic wireless channel quality, rate adaptation becomes necessary. Most existing approaches share a common drawback: they do not distinguish channel qualities from different nodes or sub-channels. Consequently, the transmission rate may be improperly selected, resulting in low network throughput. Through extensive experimental studies, we observe that channel diversity plays a significant role in rate selection. Therefore, there are opportunities of exploiting channel diversity for better rate adaptation, improving network throughput. In this paper, we propose a Channel-Aware Rate Adaptation framework (CARA) for backscatter communication networks. By employing a lightweight channel probing scheme, we are able to obtain fine-grained channel information that enables accurate channel estimation. We further design a novel channel selection algorithm, benefiting as many backscatter nodes as possible. On each selected channel, CARA chooses data rate with respect to the node that has the best channel condition. We implement CARA on commercial readers and the experiment results show that CARA achieves up to 4× goodput gain compared with state-of-the-art rate adaptation scheme.

Load on cellular towers is one of the key metrics that cellular service providers monitor as part of their operational and management tasks. Increased load on the towers can lead to congestion, which in turn can severely degrade quality of service perceived by users. Hence, it is of great interest to cellular service providers to minimize the maximum load at cell towers, and thereby minimize chances of congestion in the event of a sudden increase in load due to user demand changes. This goal can be achieved by proactive load balancing among neighboring cell towers, i.e., proactively identify opportunities to balance the load through re-binding of users from heavily loaded cell towers to lightly loaded neighboring towers. In this paper, we propose a new tool Libra to effectively assess the impact of load balancing related parameter changes. Libra provides an objective measure of the degree of load imbalance across multiple network locations and identifies if the measure improves or degrades after parameter changes. Our evaluation of Libra using real-world data collected from a large cellular provider demonstrates its effectiveness in accurately capturing the degree of imbalance at multiple cell towers.