INFOCOM 2016 Papers

Human respiratory rate is widely recognized as a vital measure of a patient's health and a primary indicator of several medical problems. Yet, it is usually ignored by medical practitioners due to limitations with available measurements techniques that are either performed through visual counting by trained personnel or using invasive and/or devices limited to medical facilities. We present Zephyr, a ubiquitous low-cost smartphone-based robust respiratory rate estimator. Our analysis shows that accelerometer and gyroscope measurements from a standard smartphone held on a person's chest is affected by her respiration cycle. Zephyr employs a series of signal processing modules to extract the breathing signal from the noisy inertial sensor measurements and handle noisy user movements. Furthermore, as part of Zephyr design, we propose a novel respiratory rate signal quality estimate that we leverage through a probabilistic framework to fuse the estimates from the different sensors, leading to a robust respiratory rate estimate. Implementation of the system on different off-the-shelf Android devices using more than 150 experiments with seven participants of different ages and genders under different typical settings with a side-by-side comparison to a commercial device shows that Zephyr can estimate the user's respiratory rate accurately with a median absolute error of 0.04 breaths per minute in realtime. In addition, Zephyr's quality-based probabilistic framework improves the respiratory rate estimation by more than 51% as compared to using any of the individual sensor measurements. This remarkable accuracy is achieved within 30 seconds of measurements, highlighting the viability of Zephyr as a ubiquitous low-cost respiratory rate estimator.

It is important for cloud service brokers to provide a multi-cloud storage service to minimize their payment cost to cloud service providers (CSPs) while providing service level objective (SLO) guarantee to their customers. Many multi-cloud storage services have been proposed or payment cost minimization or SLO guarantee. However, no previous works fully leverage the current cloud pricing policies (such as resource reservation pricing) to reduce the payment cost. Also, few works achieve both cost minimization and SLO guarantee. In this paper, we propose a multi-cloud Economical and SLO-guaranteed Storage Service (ES3), which determines data allocation and resource reservation schedules with payment cost minimization and SLO guarantee. ES3 incorporates (1) a coordinated data allocation and resource reservation method, which allocates each data item to a datacenter and determines the resource reservation amount on datacenters by leveraging all the pricing policies; (2) a genetic algorithm based data allocation adjustment method, which reduce data Get/Put rate variance in each datacenter to maximize the reservation benefit; and (3) a dynamic request redirection method, which dynamically redirects a data request from a reservation-overutilized datacenter to a reservation-underutilized datacenter to further reduce the payment. Our trace-driven experiments on a supercomputing cluster and on real clouds (i.e., Amazon S3, Windows Azure Storage and Google Cloud Storage) show the superior performance of ES3 in payment cost minimization and SLO guarantee in comparison with previous methods.

This paper studies the practically important problem of top-k queries, which is to find the top k largest categories and their corresponding sizes. In this paper, we propose a Top-k Query (TKQ) protocol and a technique that we call Segmented Perfect Hashing (SPH) for optimizing TKQ. Specifically, TKQ is based on the framed slotted Aloha protocol. Each tag responds to the reader with a Single-One Geometric (SOG) string using the ON-OFF Keying modulation. TKQ leverages the length of continuous leading 1s in the combined signal to estimate the corresponding category size. TKQ can quickly eliminate the sufficiently small categories, and only needs to focus on a limited number of large-size categories that require more accurate estimation. We conduct rigorous analysis to guarantee the predefined accuracy constraints. To further improve time-efficiency, we propose the SPH scheme, which improves the average frame utilization of TKQ from 36.8% to nearly 100% by establishing a bijective mapping between tag categories and slots. To minimize the overall time cost, we optimize the key parameter that trades off between communication cost and computation cost. Experimental results show that our TKQ+SPH protocol not only achieves the required accuracy constraints, but also achieves a 2.6~7x faster speed than the existing protocols.

In data center networks, many network-intensive applications typically suffer TCP incast throughput collapse when bursty concurrent TCP flows share a single bottleneck link. To address the TCP incast problem, we first reveal theoretically and empirically that controlling the number of concurrent flows is much more effective in reducing the incast probability than controlling the congestion window. We further propose a novel cross-layer design called Adaptive Request Schedule (ARS), which dynamically adjusts the number of concurrent TCP flows by batching application requests according to the congestion state acquired from transport layer. ARS is deployed only at the aggregator-side, while making no modification on hundreds or thousands of workers. Broad applicability is another advantage of ARS. We integrated ARS transparently (i.e., without modification) with DCTCP and TCP NewReno on NS2 simulation and a physical testbed, respectively. The experimental results show that ARS significantly reduces the incast probability across different TCP protocols and that the network goodput can be increased consistently by on average 6x under severe congestion.

Accurate indoor localization is a key enabling technology for numerous applications such as indoor navigation, mobile social networking, and augmented reality. Despite major effort from the research community, state-of-the-art indoor localization performance remains unsatisfactory. Current approaches using radio frequency entail tedious site surveys and have limited accuracy. While vision-based localization techniques are promising, they struggle with human recognition and changing environments. This paper proposes Flash-Loc, an accurate indoor localization system leveraging flashes of light to localize people carrying mobile phones in areas with deployed surveillance cameras. A person's mobile phone emits a sequence of flashes that uniquely “represents” the person from the cameras' view. Flash-Loc develops three key mechanisms that distinguish people while avoiding long irritating flashes: adaptive-length flash coding, pulse width modulation based flash generation, and image subtraction based flash localization. Further, we design a system in which Flash-Loc cooperates with fingerprinting and dead reckoning for accurate human localization. We implement Flash-Loc on commercial off-the-shelf equipment. Our real-world experiments show Flash-Loc achieves accurate indoor localization by itself and in cooperation with other localization technology. In particular, Flash-Loc can localize a user 45 m away from the camera with sub-meter accuracy.

Due to frequency selective fading, modern wideband 802.11 transmissions have unevenly distributed bit BERs in a packet. In this paper, we propose to unequally protect packet bits according to their BERs. By doing so, we can best match the effective transmission rate of each bit to channel condition, and improve throughput. The major design challenge lies in deriving an accurate relationship between the frequency selective channel condition and the decoded packet bit BERs, all the way through the complex 802.11 PHY layer. Based on our study, we find that the decoding error of a packet bit corresponds to dense errors in the underlying codeword bits, and the BER can be truthfully approximated by the codeword bit error density. With above observation, we propose UnPKT, scheme that protects packet bits using different MAC-layer FEC redundancies based on bit-wise BER estimation to augment wide-band 802.11 transmissions. UnPKT is software-implementable and compatible with the existing 802.11 architecture. Extensive evaluations based on Atheros 9580 NICs and GNU-Radio platforms show the effectiveness of our design. UnPKT can achieve a significant goodput improvement over state-of-the-art approaches.

Although Visible Light Communication (VLC) is gaining increasing attentions in research, developing a practical VLC system to harness its immediate benefits using Commercial Off-The-Shelf (COTS) devices is still an open issue. To this end, we develop and deploy CeilingCast as a location-bound wireless broadcast system using COTS LEDs as transmitters and smartphone cameras as receivers. CeilingCast innovates in its effective coding and efficient decoding schemes, so that it can be fully hosted in a smartphone and is feasible for all possible indoor environments. Moreover, we analyze the impact of various parameters on the performance of CeilingCast, in order to derive a model for such VLC systems enabled by COTS devices and hence provide general guidance for future VLC deployments in larger scales. Finally, we conduct extensive field experiments to validate the effectiveness of our LED-camera VLC model, as well as to demonstrate the promising performance of CeilingCast under various parameters.

This paper focuses on the design of provably efficient online link scheduling algorithms for multi-hop wireless networks. We consider single-hop flows and the one-hop interference model. The objective is twofold: 1) maximize the throughput when the flow sources continuously inject packets into the network, and 2) minimize the evacuation time when there are no future packet arrivals. The prior work mostly employs the link-based approach, which leads to throughput-efficient algorithms but often does not guarantee satisfactory evacuation time performance. In this paper, we adopt a novel node-based approach and propose a service-balanced online scheduling algorithm, called NSB, which gives balanced scheduling opportunities to the nodes with heavy workload. We rigorously prove that NSB guarantees to achieve an efficiency ratio no worse (or no smaller) than 2/3 for the throughput and an approximation ratio no worse (or no greater) than 3/2 for the evacuation time. It is remarkable that NSB is both throughput-optimal and evacuation-time-optimal if the underlying network graph is bipartite. Further, we develop a lower-complexity NSB algorithm, called LC-NSB, which provides the same performance guarantees as NSB. Finally, we conduct numerical experiments to elucidate our theoretical results.

We consider the problem of scheduling jobs with varying demands on multiple servers. Each server has a certain computing capacity and can schedule multiple jobs simultaneously as long as the jobs' total demand does not exceed the server's capacity. This scenario arises commonly in virtualization, cloud computing, and MapReduce (or Hadoop). We study this problem with the requirement that jobs must be scheduled non-preemptively, meaning that every job must be completed without interruption once it gets started. Often, preemption is out of choice since preempting a job can be prohibitively costly or is not allowed due to system constraints. We focus on the popular objective of minimizing total completion time of jobs. This problem is NP hard hence we study heuristics with provable approximation guarantees. Succinctly, the interaction between two orthogonal quantities, jobs demands and sizes makes the scheduling decision significantly more challenging. In this paper we propose novel algorithms for scheduling jobs with non-uniform demands on multiple homogeneous servers without preemption. We first observe that the Smallest Volume First (SVF) algorithm that favors jobs with smaller volumes could perform very poorly in general. However, we show that SVF yields a nearly optimal schedule when the system is overloaded and jobs have demands considerably smaller than servers' capacities. This result supports the intuition that SVF should work well unless some jobs with high demands occupy the servers for long, blocking other jobs. Building on this intuition and using reduction to geometric packing problems, we develop algorithms that are constant approximation for all instances for the first time. Prior to our work, there was no theoretical study on this problem even for the single server case.

Neighbor discovery is a fundamental service for initialization and managing network dynamics in wireless sensor networks and mobile sensing applications. In this paper, we present a novel design principle named Talk More Listen Less (TMLL) to reduce idle-listening in neighbor discovery protocols by learning the fact that more beacons lead to fewer wakeups. We propose an extended neighbor discovery model for analyzing wakeup schedules in which beacons are not necessarily placed in the wakeup slots. Furthermore, we are the first to consider channel occupancy rate in discovery protocols by introducing a new metric to trade off among duty-cycle, latency and channel occupancy rate. Guided by the TMLL principle, we have designed Nihao, a family of energy-efficient asynchronous neighbor discovery protocols for symmetric and asymmetric cases. We compared Nihao with existing state of the art protocols via analysis and real-world testbed experiments. The result shows that Nihao significantly outperforms the others both in theory and practice.

Most existing wireless networking solutions are best-effort and do not provide any delay guarantee required by important applications such as the control traffic of cyber-physical systems. Recently, Hou and Kumar provided the first framework for analyzing and designing delay-guaranteed network solutions. While inspiring, their idle-time-based analysis appears to apply only to flows with a special traffic (arrival and expiration) pattern, and the problem remains largely open for general traffic patterns. This paper addresses this challenge by proposing a new framework that characterizes and achieves the complete delay-constrained capacity region with general traffic patterns in single-hop downlink access-point wireless networks. We first formulate the timely capacity problem as an infinite-horizon Markov Decision Process (MDP) and then judiciously combine different simplification methods to convert it to an equivalent finite-size linear program (LP). This allows us to characterize the timely capacity region of flows with general traffic patterns for the first time in the literature. We then design three timely-flow scheduling algorithms for general traffic patterns. The first algorithm achieves the optimal utility but suffers from the curse of dimensionality. The second and third algorithms are inspired by our MDP framework and are of polynomial-time complexity. Simulation results show that both achieve near-optimal performance and outperform other existing alternatives.

In this paper we consider the problem of supporting real-time communication in mobile networks. To address this challenge, we propose novel transmission scheduling techniques that handle the routing uncertainty introduced by mobility. The core of the scheduling techniques involves controlling the order in which transmissions are scheduled and intelligently scheduling multiple transmissions in a single entry of the scheduling matrix without conflict. Flow-Ordered Mobility-Aware Real-time Scheduling (FO-MARS) integrates these techniques to provide a 14x increase in real-time capacity compared to the baseline algorithms designed for static real-time networks. Additionally, we propose Additive Mobility-Aware Real-time Scheduling (A-MARS), which can handle network dynamics such as the addition or removal of flows without having to reschedule previously admitted flows. As a result, A-MARS achieves significantly lower admission latency than that of the baselines.

Mobile video streaming is one of the fastest growing applications in the mobile Internet. Nevertheless, delivering high-quality streaming video over mobile networks remains a challenge. Researchers have since developed various novel streaming algorithms such as rate-adaptive streaming to improve the performance of mobile streaming services. However, selection or optimization of streaming algorithms is far from trivial and there is no systematic way to incorporate the tradeoffs between various performance metrics. This work aims at attacking the heart of the problem by developing a novel framework called Post Streaming Quality Analysis (PSQA) to automatically tune any streaming algorithms to maximize a given quality-of-experience (QoE) objective. We show that PSQA not only can be applied to optimize the performance of existing streaming algorithms, but also opens a new way for the exploration of new adaptive video streaming protocols and QoE metrics. Simulation results based on real network throughput traces show that PSQA can optimize existing and new streaming algorithms to achieve QoE that is remarkably close to the optimal achieved using brute-force method ex post facto.

Identifying the object that attracts human visual attention is an essential function for automatic services in smart environments. However, existing solutions can compute the gaze direction without providing the distance to the target. In addition, most of them rely on special devices or infrastructure support. This paper explores the possibility of using a smartphone to detect the visual attention of a user. By applying the proposed VADS system, acquiring the location of the intended object only requires one simple action: gazing at the intended object and holding up the smartphone so that the object as well as user's face can be simultaneously captured by the front and rear cameras. We extend the current advances of computer vision to develop efficient algorithms to obtain the distance between the camera and user, the user's gaze direction, and the object's direction from camera. The object's location can then be computed by solving a trigonometric problem. VADS has been prototyped on commercial off-the-shelf (COTS) devices. Extensive evaluation results show that VADS achieves low error (about 1.5° in angle and 0.15m in distance for objects within 12m) as well as short latency. We believe that VADS enables a large variety of applications in smart environments.

The low-cost crystal oscillators embedded in wireless sensor nodes are prone to be affected by their working condition, leading to undesired variation of clock skew. To preserve synchronized clocks, nodes have to undergo frequent re-synchronization to cope with the time-varying clock skew, which in turn means excessive energy consumption. In this paper, we propose DualSync, a synchronization approach for low-power wireless networks under dynamic working condition. By utilizing time-stamp exchanges and local measurement of temperature and voltage, DualSync maintains an accurate clock model to closely trace the relationship between clock skew and the influencing factors. We further incorporate an error-driven mechanism to facilitate interplay between Inter-Sync and Self-Sync, so as to preserve high synchronization accuracy while minimizing communication cost. We evaluate the performance of DualSync across various scenarios and compare it with state-of-art approaches. The experimental results illustrate the superior performance of DualSync in terms of both accuracy and energy efficiency.

It is common for cloud users to require clusters of inter-connected virtual machines (VMs) in a geo-distributed IaaS cloud, to run their services. Compared to isolated VMs, key challenges on dynamic virtual cluster (VC) provisioning (computation + communication resources) lie in two folds: (1) optimal placement of VCs and inter-VM traffic routing involve NP-hard problems, which are non-trivial to solve offline, not to mention if an online efficient algorithm is sought; (2) an efficient pricing mechanism is missing, which charges a market-driven price for each VC as a whole upon request, while maximizing system efficiency or provider revenue over the entire span. This paper proposes efficient online auction mechanisms to address the above challenges. We first design SWMOA, a novel online algorithm for dynamic VC provisioning and pricing, achieving truthfulness, individual rationality, computation efficiency, and (1 + 2 log μ)-competitiveness in social welfare, where μ is related to the problem size. Next, applying a randomized reduction technique, we convert the social welfare maximizing auction into a revenue maximizing online auction, PRMOA, achieving O(log μ)-competitiveness in provider revenue, as well as truthfulness, individual rationality and computation efficiency. We validate the efficacy of the mechanisms through solid theoretical analysis and trace-driven simulations.

With the increasing demand of big data applications, a variety of problems on how to operate the supporting infrastructures more intelligently and efficiently have attracted much attention in the literature. To optimize the data placement among distributed network locations is one of the fundamental problems, which aims at facilitating the data storage and access. However, traditional schemes meet challenges on the running time and the overhead introduced due to the increasing scale of datasets. Therefore, we propose a novel data placement scheme based on sketches to overcome these challenges. We first justify the effectiveness of applying the hypergraph sparsification on the data placement problem, and then present the method of constructing sparsifiers through the sketches of request traffic. Besides, the scheme features on the support of aggregating distributed sketches to make the decision and capturing the pattern of recent traffic through sliding windows. Finally, we obtain numerical results through simulations which confirm that the proposed scheme can place data effectively while reducing the introduced overhead in terms of algorithm running time, space and network traffic.

We consider the problem of placing the minimum number of monitors in a communication network with possible topology changes to identify additive link metrics from path metrics. The core of our solution is a suite of robust monitor placement algorithms with different performance-complexity tradeoffs that guarantee network identifiability for the multiple possible topologies. In particular, we show that the optimal (i.e., minimum) monitor placement is the solution to a generalized hitting set problem, where we provide a polynomial-time algorithm to construct the input. Although the optimal placement is NP-hard in general, we identify non-trivial special cases that can be solved efficiently. We further demonstrate how the proposed algorithms can be augmented to handle unpredictable topology changes and tradeoffs between monitor cost and adaptation cost. Our evaluations on mobility-induced dynamic topologies verify the effectiveness and robustness of the proposed algorithms.

Friend-to-friend (F2F) overlays, which restrict direct communication to mutually trusted parties, are a promising substrate for privacy-preserving communication due to their inherent membership-concealment and Sybil-resistance. Yet, existing F2F overlays suffer from a low performance, are vulnerable to denial-of-service attacks, or fail to provide anonymity. In particular, greedy embeddings allow highly efficient communication in arbitrary connectivity-restricted overlays but require communicating parties to reveal their identity. In this paper, we present a privacy-preserving routing scheme for greedy embeddings based on anonymous return addresses rather than identifying node coordinates. We show that the return addresses allow plausible deniability. Furthermore, we enhance the routing's resilience by using multiple embeddings and propose a method for efficient content addressing. Our extensive simulation study on real-world data indicates that our approach is highly efficient and effectively mitigates failures as well as powerful denial-of-service attacks.