INFOCOM 2017 Papers

Image retrieval has become an important function in many emerging computer vision applications e.g. online shopping via images, medical health care systems. More and more images are being generated and stored in public clouds. However, recent photo leakage events raise concerns about privacy leaks for images stored in public clouds. In this paper, we present an efficient scalable hierarchical image retrieval system (CASHEIRS) which provides privacy-aware image retrieval feature. CASHEIRS employs transformed Convolutional Neural Network features to improve image retrieval accuracy and an encrypted hierarchical index tree to speed up the query process. Extensive evaluations using Caltech256 and INRIA Holiday datasets show that CASHEIRS is more effective than three existing schemes. We also demonstrate its practicality on a mobile device.

One model for viral marketing is the positive influence. In this model, an inactive node is changed into active if and only if at least half of its neighbors are already in active state. The positive influence model can be viewed as a special case of a general threshold model, in which the threshold function at each node has value one if at least a certain fraction of neighbors are in active state, and value 0 otherwise. This function can be proved to be monotonically increasing and nonsubmodular for any predefined fraction. Therefore, given a seed set, the number of influenced nodes is not submodular with respect to the size of the seed set. This fact makes those optimization problems related with positive influence very hard, including the minimum partial positive influence seeding problem: Given a social network G = (V, E) and a number 02H ([pn]))-approximation algorithm for the minimum partial positive influence seeding problem, where n is the number of nodes, and H(·) is the Harmonic number.

Ideally, users in cognitive radio networks (CRNs) are capable of sensing and exploiting any potential transmission opportunities in the available spectrum band ranging from 30 KHz to 300 GHz. With the multiple-diverse-band spectrum, the network can provide more radio resources and capacity to a large number of CR users. However, the multiband scenario (e.g., TV band + 2/3G band + 4/5G band) also introduces significant challenges in channel rendezvous, a fundamental operation for users in CRNs to set up their communication link on a common channel. Existing studies on channel rendezvous suffer from unacceptable long delay and high energy consumption when applied to such scenarios. In this paper, we propose a two-dimensional heterogeneous rendezvous (2D-HR) protocol which can support multi-wideband CRNs (MWB-CRNs) with a significantly reduced rendezvous delay and energy consumption for various rendezvous scenarios, such as the pair-wise rendezvous, any-wise rendezvous, and multi-wise rendezvous. The proposed design also performs better than existing efforts even when dealing with traditional single-band rendezvous. The merits of 2D-HR are proved theoretically and validated against extensive simulations. To the best of our knowledge, this is the first work that addresses heterogeneous rendezvous in MWB-CRNs.

Multi-User Multiple Input Multiple Output (MU-MIMO) enables a multi-antenna access point (AP) to serve multiple users simultaneously, and has been adopted as the IEEE 802.11ac standard. While several PHY-MAC designs have recently been proposed to improve the throughput performance of a MU-MIMO WLAN, they, however, usually assume that all the concurrent streams are of roughly equal length. In reality, users usually have frames with heterogeneous lengths even after aggregation, leading to different lengths of transmission time. Hence, the concurrent transmission opportunities might not always be fully utilized when some streams finish earlier than the others in a transmission opportunity (TXOP). To resolve this inefficiency, this paper presents acPad, a PHY-MAC design that adds additional frames to fill up the idle channel time and better utilize the spatial multiplexing gain. Our acPad identifies proper users as the padding so as to improve the padding gain, while preventing this padding from harming all the ongoing streams. Our evaluation via large-scale trace-driven simulations demonstrates that acPad improves the throughput by up to 2.83×, or by 1.36× on average, as compared to the conventional 802.11ac.

Smartphone theft is a non-negligible problem that causes serious concerns on personal property, privacy, and public security. The existing solutions to this problem either provide only functions like retrieving a phone, or require dedicated hardware to detect thefts. How to protect smartphones from being stolen at all times is still an open problem. In this paper, we propose iGuard, a real-time anti-theft system for smartphones. iGuard utilizes only the inertial sensing data from the smartphone. The basic idea behind iGuard is to distinguish different people holding a smartphone, by identifying the order of the motions during the `take-out' behavior and how each motion is performed. For this purpose, we design a motion segmentation algorithm to detect the transition between two motions from the noisy sensing data. We then leverage the distinct feature contained in each sub-segment of a motion, instead of the entire motion, to estimate the probability that the motion is performed by the smartphone owner himself/herself. Based on such pre-processed data, we propose a Markov Chain based model to track the behavior of a smartphone user. According to this model, iGuard instantly alarms once the tracked data deviate from the smartphone owner's usual habit. We implement iGuard on Android and evaluate its performance in real environments. The experimental results show that iGuard is accurate and robust in various scenarios.

In this paper, we study how to perform traffic engineering at an extremely-small time scale with segment routing, addressing a critical need for modern wide area networks. Prior work has shown that segment routing enables to better engineer traffic, thanks to its ability to program detours in forwarding paths, at scale. Two main approaches have been explored for traffic engineering with segment routing, respectively based on integer linear programming and constraint programming. However, no previous work deeply investigated how quickly those approaches can react to unexpected traffic changes and failures. We highlight limitations of existing algorithms, both in terms of required execution time and amount of path changes to be applied. Thus, we propose a new approach, based on local search and focused on the quick re-arrangement of (few) forwarding paths. We describe heuristics for sub-second recomputation of segment-routing paths that comply with requirements on the maximum link load (e.g., for congestion avoidance). Our heuristics enable a prompt answer to sudden criticalities affecting network services and business agreements. Through extensive simulations, we indeed experimentally show that our proposal significantly outperforms previous algorithms in the context of time-constrained optimization, supporting radical traffic changes in few tens of milliseconds for realistic networks.

Memory caches are being aggressively used in today's data-parallel systems such as Spark, Tez, and Piccolo. However, prevalent systems employ rather simple cache management policies — notably the Least Recently Used (LRU) policy — that are oblivious to the application semantics of data dependency, expressed as a directed acyclic graph (DAG). Without this knowledge, memory caching can at best be performed by “guessing” the future data access patterns based on historical information (e.g., the access recency and/or frequency), which frequently results in inefficient, erroneous caching with low hit ratio and a long response time. In this paper, we propose a novel cache replacement policy, Least Reference Count (LRC), which exploits the application-specific DAG information to optimize the cache management. LRC evicts the cached data blocks whose reference count is the smallest. The reference count is defined, for each data block, as the number of dependent child blocks that have not been computed yet. We demonstrate the efficacy of LRC through both empirical analysis and cluster deployments against popular benchmarking workloads. Our Spark implementation shows that, compared with LRU, LRC speeds up typical applications by 60%.

Ideally, minimizing the flow completion time (FCT) requires millions of priorities supported by the underlying network so that each flow has its unique priority. However, in production datacenters, the available switch priority queues for flow scheduling are very limited (merely 2 or 3). This practical constraint seriously degrades the performance of previous approaches. In this paper, we introduce Explicit Priority Notification (EPN), a novel scheduling mechanism which emulates fine-grained priorities (i.e., desired priorities or DP) using only two switch priority queues. EPN can support various flow scheduling disciplines with or without flow size information. We have implemented EPN on commodity switches and evaluated its performance with both testbed experiments and extensive simulations. Our results show that, with flow size information, EPN achieves comparable FCT as pFabric that requires clean-slate switch hardware. And EPN also outperforms TCP by up to 60.5% if it bins the traffic into two priority queues according to flow size. In information-agnostic setting, EPN outperforms PIAS with two priority queues by up to 37.7%. To the best of our knowledge, EPN is the first system that provides millions of priorities for flow scheduling with commodity switches.

WiFi technology has gained a wide prevalence for not only wireless communication but also pervasive sensing. A wide variety of emerging applications leverage accurate measurements of the Channel State Information (CSI) information obtained from commodity WiFi devices. Due to hardware imperfection of commodity WiFi devices, the frequency response of internal signal processing circuit is mixed with the real channel frequency response in passband, which makes deriving accurate channel frequency response from CSI measurements a challenging task. In this paper, we identify non-negligible non-linear CSI phase errors and report that IQ imbalance is the root source of non-linear CSI phase errors. We conduct intensive analysis on the characteristics of such non-linear errors and find that such errors are prevalent among various WiFi devices. Furthermore, they are rather stable along time and the received signal strength indication (RSSI) but sensitive to frequency bands used between a transmission pair. Based on these key observations, we propose new calibration methods to compensate both non-linear and linear CSI phase errors. We demonstrate the efficacy of the proposed methods by applying them in CSI splicing. Results of extensive real-world experiments indicate that accurate CSI phase measurements can significantly improve the performance of splicing and the stability of the derived power delay profiles (PDPs).

Modern datacenters are increasingly required to deal with latency-sensitive applications. A major question here is how to represent latency in desired objectives. Incorporation of multiple traffic characteristics (e.g., packet values and required processing requirements) significantly increases the complexity of buffer management policies. In this work, we consider weighted throughput optimization (total transmitted value) in the setting where every incoming packet is branded with intrinsic value, required processing, and slack (an offset from the arrival time when a packet should be transmitted), and the buffer is unbounded but effectively bounded by slacks. The main result is a 3-competitive algorithm as the slack-to-work ratio increases. Our results supported by a comprehensive evaluation study on CAIDA network traces.

This work introduces a new model for cloud gaming systems aimed at optimizing the timeliness of video frames based on an age of information (AoI) metric. Mobile clients submit actions through an access network to a game server. The game server generates video frames at a constant frame rate. At the mobile device, the display of these frames represent game status updates. We develop a Markov model to characterize the frame delivery process in low-latency edge cloud gaming systems. Based on this model, we derive a simple formula for the average status age of a tightly synchronized low-latency mobile gaming system in which the inter-frame period is a significant contributor to the system latency. We validate the model by ns-3 simulation of a low-latency edge cloud gaming system. Our evaluation scenarios included single-player games as well as multi-player games in which the game processing was conducted by a combination of a centralized game server and edge cloud renderers.

Motivated by applications in social network community analysis, we introduce a new clustering paradigm termed motif clustering. Unlike classical clustering, motif clustering aims to minimize the number of clustering errors associated with both edges and certain higher order graph structures (motifs) that represent “atomic units” of social organizations. Our contributions are two-fold: We first introduce motif correlation clustering, in which the goal is to agnostically partition the vertices of a weighted complete graph so that certain predetermined “important” social subgraphs mostly lie within the same cluster, while “less relevant” social subgraphs are allowed to lie across clusters. We then proceed to introduce the notion of motif covers, in which the goal is to cover the vertices of motifs via the smallest number of (near) cliques in the graph. Motif cover algorithms provide a natural solution for overlapping clustering and they also play an important role in latent feature inference of networks. For both motif correlation clustering and its extension introduced via the covering problem, we provide hardness results, algorithmic solutions and community detection results for two well-studied social networks.

Cross-device interaction is becoming an increasingly hot topic as we often have multiple devices at our immediate disposal in this era of mobile computing. Various cross-device applications such as file sharing, multi-screen display, and cross-device authentication have been proposed and investigated. However, one of the most fundamental enablers remains unsolved: How to achieve ubiquitous multi-device localization? Though pioneer efforts have resorted to gesture-assisted or sensing-assisted localization, they either require extensive user participation or impose some strong assumptions on device sensing abilities. This introduces extra costs and constraints, and thus degrades their practicality. To overcome these limitations, we propose TUM, an acoustic-assisted localization scheme Towards Ubiquitous Multi-device localization. The basic idea of TUM is to utilize the dual-microphones and speakers to obtain distance cues among devices. At the same time it resolves the location ambiguity with the help of MEMS sensors. We devise techniques for distance constraint extraction, static localization, continuous localization, and multi-device localization, and build a prototype that runs on commodity devices. Extensive experiments show that TUM provides a real-time 3D relative localization service under 10cm mean error for both static and continuous localization.

Recommendation systems usually try to “guess” a user's preferences from the system's view. We study another side of recommendation: active opinion-formation from the perspective of the user. In real life, a user's opinion evolves with time and refines when new evidence occurs. Then, how does an online user form his/her own opinion actively in large social networks? The problem has three challenges: the factor, the effect and the open environment. To address those challenges, we investigate: (1) what factors or channels a user will consider, (2) how those channels will take effect, and (3) an incremental approach to incorporate multiple channels. We explore three types of channels: the internal opinion of an individual user, influences from trusted friends, and influences from public channels. A novel simulator, OpinionFormer, is proposed to incorporate those channels incrementally. It differentiates the effects of friends and public channels as well as positive and negative opinions. We validate the performance of OpinionFormer by predicting users' opinions using real-world data sets. Experimental results show that our model can improve accuracy over other models that ignore some channels or that neglect the evolving features.

Crowdsourced signal monitoring systems are gaining attention for capturing the wireless spectrum at large geographical scale. Yet, most of the current systems are still limited to simple power spectrum measurements reported by each sensor. Our objective is to enhance such systems with signal decoding capabilities performed in the backend while retaining the original vision of a low-cost and crowdsourced setup. We propose a distributed system architecture for collaborative radio signal monitoring and decoding that builds on $12 low-cost radio frequency (RF) frontends and embedded boards and that takes into consideration the limited network bandwidth from the sensors to the backend. We present a distributed time multiplexing mechanism to sample the spectrum in a coordinated fashion that exploits the similarity of the radio signal received by more than one RF frontend in the same radio coverage. We address the strict time synchronization required among sensors to reconstruct the signal from the samples they receive when in the same radio coverage. We study and implement techniques to identify and overcome errors in the timing information in the presence of noise sources and decode the data in the backend. We provide an evaluation based on simulations and on real signals transmitted by Long-Term Evolution (LTE) base stations. Our results show that we can reliably reconstruct and decode radio signals received by low-cost crowdsourced sensors.

Detecting Sybils in online social networks (OSNs) is a fundamental security research problem as adversaries can leverage Sybils to perform various malicious activities. Structure-based methods have been shown to be promising at detecting Sybils. Existing structure-based methods can be classified into two categories: Random Walk (RW)-based methods and Loop Belief Propagation (LBP)-based methods. RW-based methods cannot leverage labeled Sybils and labeled benign users simultaneously, which limits their detection accuracy, and they are not robust to noisy labels. LBP-based methods are not scalable, and they cannot guarantee convergence. In this work, we propose SybilSCAR, a new structure-based method to perform Sybil detection in OSNs. SybilSCAR maintains the advantages of existing methods while overcoming their limitations. Specifically, SybilSCAR is Scalable, Convergent, Accurate, and Robust to label noises. We first propose a framework to unify RW-based and LBP-based methods. Under our framework, these methods can be viewed as iteratively applying a (different) local rule to every user, which propagates label information among a social graph. Second, we design a new local rule, which SybilSCAR iteratively applies to every user to detect Sybils. We compare SybilSCAR with a state-of-the-art RW-based method and a state-of-the-art LBP-based method, using both synthetic Sybils and large-scale social network datasets with real Sybils. Our results demonstrate that SybilSCAR is more accurate and more robust to label noise than the compared state-of-the-art RW-based method, and that SybilSCAR is orders of magnitude more scalable than the state-of-the-art LBP-based method and is guaranteed to converge. To facilitate research on Sybil detection, we have made our implementation of SybilSCAR publicly available on our webpages.

The increasing complexity of smartphone applications and services necessitate high battery consumption but the growth of smartphones' battery capacity is not keeping pace with these increasing power demands. To overcome this problem, researchers gave birth to the Mobile Cloud Computing (MCC) research area. In this paper we advance on previous ideas, by proposing and implementing the first known Near Field Communication (NFC)-based computation offloading framework. This research is motivated by the advantages of NFC's short distance communication, with its better security, and its low battery consumption. We design a new NFC communication protocol that overcomes the limitations of the default protocol; removing the need for constant user interaction, the one-way communication restraint, and the limit on low data size transfer. We present experimental results of the energy consumption and the time duration of two computationally intensive representative applications: (i) RSA key generation and encryption, and (ii) gaming/puzzles. We show that when the helper device is more powerful than the device offloading the computations, the execution time of the tasks is reduced. Finally, we show that devices that offload application parts considerably reduce their energy consumption due to the low-power NFC interface and the benefits of offloading.

We consider the problem of throughput-optimal packet dissemination, in the presence of an arbitrary mix of unicast, broadcast, multicast and anycast traffic, in a general wireless network. We propose an online dynamic policy, called Universal Max-Weight (UMW), which solves the above problem efficiently. To the best of our knowledge, UMW is the first throughput-optimal algorithm of such versatility in the context of generalized network flow problems. Conceptually, the UMW policy is derived by relaxing the precedence constraints associated with multi-hop routing, and then solving a min-cost routing and max-weight scheduling problem on a virtual network of queues. When specialized to the unicast setting, the UMW policy yields a throughput-optimal cycle-free routing and link scheduling policy. This is in contrast to the well-known throughput-optimal BackPressure (BP) policy which allows for packet cycling, resulting in excessive delay. Extensive simulation results show that the proposed policy incurs a substantially lower delay as compared to the BP policy. The proof of throughput-optimality of the UMW policy combines techniques from stochastic Lyapunov theory with a sample path argument from adversarial queueing theory and may be of independent theoretical interest.

Accurate orientation information is the key in many applications, ranging from map reconstruction with crowdsourcing data, location data analytics, to accurate indoor localization. Many existing solutions rely on noisy magnetic and inertial sensor data, leading to limited accuracy, while others leverage multiple, dense anchor points to improve the accuracy, requiring significant deployment efforts. This paper presents LiCompass, the first system that enables a commodity camera to accurately estimate the object orientation using just a single optical anchor. Our key idea is to allow a camera to observe varying intensity level of polarized light when it is in different orientations and, hence, perform estimation directly from image pixel intensity. As the estimation relies only on pixel intensity, instead of the location of the anchor in an image, the system performs reliably at long distance, with low resolution images, and with large perspective distortion. LiCompass' core designs include an elaborate optical anchor design and a series of signal processing techniques based on trigonometric properties, which extend the range of orientation estimation to full 360 degrees. Our prototype evaluation shows that LiCompass produces very accurate estimates with median errors of merely 2.5 degrees at 5 meters and 7.4 degrees at 2.5 meters with an irradiance angle of 55 degrees.