INFOCOM 2017 Papers

Datacenter networks are often structured as multi-rooted trees to provide high bisection bandwidth at low cost. To utilize the available bisection bandwidth, an efficient load balancing algorithm is required. Packet Spraying is known to perform well in symmetric topologies as it provides per-packet load balancing over equal cost paths. However, packet spraying performs poorly in asymmetric topologies. In this paper we ask, “How can we make packet spraying effective in asymmetric topologies while retaining its simplicity?” Towards this end, we propose SAPS, “Symmetric Adaptive Packet Spraying”, an SDN-based scheme that uses packet spraying over symmetric virtual topologies. SAPS is based on the key insight that if we provide each flow with a symmetric view of the network fabric, then packet spraying can produce near-optimal performance. We evaluate SAPS using simulations and testbed experiments. Our results indicate that SAPS performs well for a variety of application workloads and asymmetric network scenarios.

Crowdsourcing has emerged as an important data collection paradigm in participatory and human-centric sensing applications. While many crowdsourcing studies focus on sensing and recovering the status of the physical world, this paper investigates the problem of profiling the crowd sensors (i.e., humans). In particular, we study the problem of accurately inferring the home locations of people from the noisy and sparse crowdsourcing data they contribute. In this study, we propose a semi-supervised framework, Where Are You From (WAYF), to accurately infer the home locations of people by explicitly exploring the localness of people and the dependency between people based on their check-in behaviors under a rigorous analytical framework. We perform extensive experiments to evaluate the performance of our scheme and compared it to the state-of-the-art techniques using three real world data traces collected from Foursquare. The results showed the effectiveness of our scheme in accurately profiling the home locations of people.

It has become routine for large volumes of data to be generated, stored, and processed across geographically distributed datacenters. To run a single data analytic job on such geo-distributed data, recent research proposed to distribute its tasks across datacenters, considering both data locality and network bandwidth across datacenters. Yet, it remains an open problem in the more general case, where multiple analytic jobs need to fairly share the resources at these geo-distributed data-centers. In this paper, we focus on the problem of assigning tasks belonging to multiple jobs across datacenters, with the specific objective of achieving max-min fairness across jobs sharing these datacenters, in terms of their job completion times. We formulate this problem as a lexicographical minimization problem, which is challenging to solve in practice due to its inherent multi-objective and discrete nature. To address these challenges, we iteratively solve its single-objective subproblems, which can be transformed to equivalent linear programming (LP) problems to be efficiently solved, thanks to their favorable properties. As a highlight of this paper, we have designed and implemented our proposed solution as a fair job scheduler based on Apache Spark, a modern data processing framework. With extensive evaluations of our real-world implementation on Amazon EC2, we have shown convincing evidence that max-min fairness has been achieved using our new job scheduler.

Indoor-outdoor (IO) detection provides very useful hints for a mobile device to perform context-aware services. To that end, GPS presents a viable solution by relating a device's IO status with its positioning performance, which depends on the device's exposure to the open sky. This approach, however, is prohibitively expensive in terms of energy consumption and response time. Recent work has thus been focused on exploiting low-energy sensors such as light, cellular, and magnetic sensors to infer the IO status indirectly, at the cost of reduced adaptability or explicit user involvement. In this paper, we propose an improving solution to this problem. Our method, called SatProbe, reverts to the GPS approach for its directness and robustness, but avoids its drawback by extracting only the number of visible satellites from the raw GPS data, instead of going through extensive computation to obtain a final position. This metric provides a clear indicator of the IO status, yet can be obtained with great efficiency. Experiments on 79 raw GPS traces with 2595 detection points across a variety of environments show that SatProbe produces higher detection accuracy than previous solutions, with more than an order of magnitude reductions in energy consumption and detection time.

Cloud storage services such as Dropbox have been widely used for file collaboration among multiple users. However, this desirable functionality is yet restricted to the “walled-garden” of each service. At present, the only effective approach to cross-cloud file collaboration seems to be using web APIs, whose performance is known to be highly unstable and unpredictable. Now that using inefficient web APIs is inevitable, in this paper we attempt to achieve sound user-perceived performance for cross-cloud file collaboration. This attempt is enabled by two key observations from real-world measurements. First, for each cloud, we are always able to deploy one or several nearby (client) proxies which can efficiently access the web APIs. Second, during file collaboration, significant similarity exists among different versions of a file. This can be exploited to substantially reduce inter-proxy traffic and thus shorten the data sync time. Guided by the observations, we design and implement an open-source prototype system called CoCloud. Currently, it supports file collaboration among four popular cloud storage services in the US and China. Its performance is well acceptable to users under representative workloads, even approaching or exceeding intra-cloud performance in many cases.

The future generation of transportation system will be featured by electrified public transportation. To fulfill metropolitan transit demands, electric vehicles (EVs) must be continuously operable without recharging downtime. Wireless Power Transfer (WPT) techniques for in-motion EV charging is a solution. It however brings up a challenge: how to deploy charging lanes in a metropolitan road network to minimize the deployment cost while enabling EVs' continuous operability. In this paper, we propose CatCharger, which is the first work that handles this challenge. From a metropolitan-scale dataset collected from multiple sources of vehicles, we observe the diversity of vehicle passing speed and daily visit frequency (called traffic attributes) at intersections (i.e., landmarks), which are important factors for charging lane deployment. To select landmarks for deployment, we first group landmarks with similar traffic attribute values using the entropy minimization clustering method, and choose better candidate landmarks from each group suitable for deployment. To determine the deployment locations from the candidate landmarks, we infer the expected vehicle residual energy at each landmark using a Kernel Density Estimator fed by the vehicles' mobility, and formulate and solve an optimization problem to minimize the total deployment cost while ensuring a certain level of expected residual energy of EVs at each landmark. Our trace-driven experiments demonstrate the superior performance of CatCharger over other methods.

We describe an end-to-end platform called SpecSense to support large scale spectrum monitoring. SpecSense crowdsources spectrum monitoring to low-cost, low-power commodity SDR/embedded platforms and provides necessary analytics support in a central spectrum server. In this work, we describe SpecSense and address specific challenges related to accurately estimate spectrum occupancy on demand with low overhead. To address the accuracy question, we augment state-of-the-art spatial interpolation techniques to accommodate scenarios where RF propagation characteristics change across space. To address the overhead question, we solve the sensor selection problem to select the minimum number of spectrum sensors that can best estimate the spectrum at the requested locations.

The recent proliferation of human-carried mobile devices has given rise to the mobile crowd sensing (MCS) systems. However, the sensory data provided by the participating workers are usually not reliable. As an efficient technique to extract truthful information from unreliable data, truth discovery has drawn significant attention. Currently, the privacy concern of the participating workers poses a major challenge on the design of truth discovery mechanisms. Although the existing mechanism can conduct truth discovery with high accuracy and strong privacy guarantee, tremendous overhead is incurred on the worker side. In this paper, we propose a novel lightweight privacy preserving truth discovery framework, L-PPTD, which is implemented by involving two non-colluding cloud platforms and adopting additively homomorphic cryptosystem. This framework not only achieves the protection of each worker's sensory data and reliability information but also introduces little overhead to the workers. In order to further reduce each worker's overhead in the scenarios where only the sensory data need to be protected, we propose another more lightweight framework named L2-PPTD. The desirable performance of the proposed frameworks is verified through extensive experiments conducted on real world MCS systems.

Device-free Passive (DfP) indoor localization releases the users from the burden of wearing sensors or carrying smartphones. Instead of locating devices, DfP technology directly locates human bodies. This promising technology upgrades and even redefines many services, such as intruder alarm, fire rescue, fall detection, baby monitoring, etc. Using Wi-Fi based fingerprints, DfP approaches can achieve a nearly perfect accuracy with a resolution less than one meter. However, Wi-Fi localization profiles may easily drift with a minor environment change, resulting in an inconsistency between fingerprints and new profiles. This inconsistency issue could lead to large errors, and may quickly ruin the whole system. To address this issue, we propose a approach named AutoFi to automatically calibrate the localization profiles in an unsupervised manner. AutoFi embraces a new technique that online estimates and cancels profile contaminants introduced by environment changes. It applies an autoencoder to preserve critical features of fingerprints, and reproduces them later in new localization profiles. Experiment results demonstrate that AutoFi indeed rescues the Wi-Fi fingerprints from variations in the surrounding. The localization accuracy is improved from 18.8% (before auto-calibration) to 84.9% (after auto-calibration).

Photos crowdsourced from mobile devices can be used in many applications such as disaster recovery to obtain information about a target area. However, such applications often have resource constraints in terms of bandwidth, storage, and processing capability, which limit the number of photos that can be crowdsourced. Thus, it is a challenge to use the limited resources to crowdsource photos that best cover the target area. In this paper, we leverage various geographical and geometrical information about photos, called metadata, to address this challenge. Metadata includes the location, orientation, field of view, and range of a camera. Based on metadata, we define photo utility to measure how well a target area is covered by a set of photos. We propose various techniques to analyze such coverage and calculate photo utility accurately and efficiently. We also study the problem of selecting photos with the largest utility under a resource budget, and propose an efficient algorithm that achieves constant approximation ratio. With our design, the crowdsourcing server can select photos based on metadata instead of real images, and thus use the limited resources to crowdsource the most useful photos. Both simulation and experimental results demonstrate the effectiveness of our design.

Network Function Virtualization (NFV) has the potential to significantly reduce the capital and operating expenses, shorten product release cycle, and improve service agility. In this paper, we focus on minimizing the total number of Virtual Network Function (VNF) instances to provide a specific service (possibly at different locations) to all the flows in a network. Certain network security and analytics applications may allow fractional processing of a flow at different nodes (corresponding to datacenters), giving an opportunity for greater optimization of resources. Through a reduction from the set cover problem, we show that this problem is NP-hard and cannot even be approximated within a factor of (1 - o(1))lnm (where m is the number of flows) unless P=NP. Then, we design two simple greedy algorithms and prove that they achieve an approximation ratio of (1 - o(1))ln m + 2, which is asymptotically optimal. For special cases where each node hosts multiple VNF instances (which is typically true in practice), we also show that our greedy algorithms have a constant approximation ratio. Further, for tree topologies we develop an optimal greedy algorithm by exploiting the inherent topological structure. Finally, we conduct extensive numerical experiments to evaluate the performance of our proposed algorithms in various scenarios.

Lacking of floor plans is a fundamental obstacle to ubiquitous indoor location-based services. Recent work have made significant progress to accuracy, but they largely rely on slow crowdsensing that may take weeks or even months to collect enough data. In this paper, we propose Knitter that can generate accurate floor maps by a single random user's one hour data collection efforts. Knitter extracts high quality floor layout information from single images, calibrates user trajectories and filters outliers. It uses a multi-hypothesis map fusion framework that updates landmark positions/orientations and accessible areas incrementally according to evidences from each measurement. Our experiments on 3 different large buildings and 30+ users show that Knitter produces correct map topology, and 90-percentile landmark location and orientation errors of 3 ~ 5m and 4 ~ 6°, comparable to the state-of-the-art at more than 20× speed up: data collection can finish in about one hour even by a novice user trained just a few minutes.

The content delivery network (CDN) intensively uses cache to push the content close to end users. Over both traditional Internet architecture and emerging cloud-based framework, cache allocation has been the core problem that any CDN operator needs to address. As the first step for cache deployment, CDN operators need to discover or estimate the distribution of user requests in different geographic areas. This step results in a statistical spatial model for the user requests, which is used as the key input to solve the optimal cache deployment problem. More often than not, the temporal information in user requests is omitted to simplify the CDN design. In this paper, we disclose that the spatial request model alone may not lead to truly optimal cache deployment. By considering the temporal information in user requests, we provide a dynamic traffic based solution to this broadly studied problem. Via experiments over the North American ISPs Points of Presence (PoPs) network, our new solution outperforms traditional CDN design method and saves the overall delivery cost by 16% to 20%.

Modern planetary-scale online services have massive data to transfer over the wide area network (WAN). Due to the tremendous cost of building WANs and the stringent timing requirement of distributed applications, it is critical for network operators to make efficient use of network resources to optimize data transfers. By leveraging software-defined networking (SDN) and reconfigurable optical devices, recent solutions design centralized systems to jointly control the network layer and the optical layer. While these solutions show it is promising to significantly reduce data transfer times by centralized cross-layer control, they do not have any theoretical guarantees on the proposed algorithms. This paper presents approximation algorithms and theoretical analysis for the online transfer scheduling problem over optical WANs. The goal of the scheduling problem is to minimize the makespan (the time to finish all transfers) or the total sum of completion times. We design and analyze various greedy, online scheduling algorithms that can achieve 3-competitive ratio for makespan, 2-competitive ratio for minimum sum completion time for jobs of unit size, and 3α-competitive ratio for jobs of arbitrary transfer size and each node having degree constraint d, where α = 1 when d = 1 and α = 1.86 when d ≥ 2. We also evaluated the performance of these algorithms and compared the performance with prior heuristics.

Social networks allow rapid spread of ideas and innovations while the negative information can also propagate widely. When the cascades with different opinions reaching the same user, the cascade arriving first is the most likely to be taken by the user. Therefore, once misinformation or rumor is detected, a natural containment method is to introduce a positive cascade competing against the rumor. Given a budget k, the rumor blocking problem asks for k seed users to trigger the spread of the positive cascade such that the number of the users who are not influenced by rumor can be maximized. The prior works have shown that the rumor blocking problem can be approximated within a factor of (1 - 1/e- δ) by a classic greedy algorithm combined with Monte Carlo simulation with the running time of O(k3mn ln n/δ2), where n and m are the number of users and edges, respectively. Unfortunately, the Monte-Carlo-simulation-based methods are extremely time consuming and the existing algorithms either trade performance guarantees for practical efficiency or vice versa. In this paper, we present a randomized algorithm which runs in O(km ln n/δ2) expected time and provides a (1 - 1/e - δ)-approximation with a high probability. The experimentally results on both the real-world and synthetic social networks have shown that the proposed randomized rumor blocking algorithm is much more efficient than the state-of-the-art method and it is able to find the seed nodes which are effective in limiting the spread of rumor.

RFID technologies are making their way into numerous applications, including inventory management, supply chain, product tracking, transportation, logistics, etc. One important application is to automatically detect anomalies in RFID systems, such as missing tags, unknown tags, or cloned tags due to theft, management error, or targeted attacks. Existing solutions are all designed to detect a certain type of RFID anomalies, but lack a general functionality for detecting different types of anomalies. This paper attempts to propose a general framework for anomaly detection in RFID systems, thereby reducing the complexity for readers and tags to implement different anomaly-detection protocols. We introduce a new concept of differential Bloom filter (DBF), which turns physical-layer signal data into a segmented Bloom filter that encodes the IDs of abnormal tags. As a case study, we propose a protocol that builds DBF for identifying all missing tags in an efficient way. We implement a prototype for missing-tag identification using USRP and WISP tags to verify the effectiveness our protocol, and use large-scale simulations for performance evaluation. The results show that our solution can significantly improve time efficiency, when comparing with the best existing work.

MultiFath TCP (MPTCP) is a recent TCP extension that enables hosts to send data over multiple paths for a single connection. It is already deployed for various use cases, notably on smartphones. In parallel with this, there is a growing deployment of encryption and authentication techniques to counter various forms of security attacks. Tcpcrypt and TLS are some of these security solutions. In this paper, we propose MPTCPsec, a MultiPath TCP extension that closely integrates authentication and encryption inside the protocol itself. Our design relies on an adaptation for the multipath environment of the ENO option that is being discussed within the IETF tcpinc working group. We then detail how MultiPath TCP needs to be modified to authenticate and encrypt all data and authenticate the different TCP options that it uses. Finally, we implement our proposed extension in the reference implementation of MultiPath TCP in the Linux kernel and we evaluate its performance.

Flow completion times (FCTs) are critical for many cloud applications. To minimize the average FCT, recent transport designs, such as pFabric, PASE, and PIAS, approximate the Shortest Remaining Time First (SRTF) scheduling. A common, implicit assumption of these solutions is that the remaining time is only determined by the remaining flow size. However, this assumption does not hold in many real-world scenarios where applications generate data at diverse rates that are smaller than the network capacity. In this paper, we look into this issue from system perspective and find that the operating system (OS) kernel can be exploited to better estimate the remaining time of a flow. In particular, we use the rate of copying data from user space to kernel space to measure the data generation rate. We design RAX, a rate aware flow scheduling method, that calculates the remaining time of a flow more accurately, based on not only the flow size but also the data generation rate. We have implemented a RAX prototype in Linux kernel and evaluated it through testbed experiments and ns-2 simulations. Our testbed results show that RAX reduces FCT by up to 14.9%/41.8% and 7.8%/22.9% over DCTCP and PIAS for all/medium flows respectively.

This paper identifies two energy saving opportunities of Wi-Fi interface emerged during smartphone's screen-off periods. Exploiting the opportunities, we propose a new power saving strategy, BackPSM, for screen-off Wi-Fi communications. BackPSM regulates client to send and receive packets in batches and coordinates multiple clients to communicate at different slots (i.e., beacon interval). The core problem in BackPSM is how to coordinate client without incurring extra traffic overheads. To handle the problem, we propose a novel paradigm, Out-of-Band Communication (OBC), for client-to-client direct communications. OBC exploits the TIM (Traffic Indication Map) field of Wi-Fi Beacon to create a free side-channel between clients. It is based upon the observation that a client may control 1 → 0 appearing on TIM bit by locally regulating packet receiving operations. We adopt this 1 → 0 as the basic signal, and leverage the time length in between two signals to encode information. We demonstrate that OBC can be used to convey coordination information with close to 100% accuracy. We have implemented and evaluated BackPSM on a testbed. The results show that BackPSM reduces screen-off energy by up to 60%, and outperforms state-of-the-art strategies by 16%-42%.