INFOCOM 2017 Papers

Currently, the limitation of battery has become a serious obstacle for the development of Internet of things (IoTs). Therefore, a new network architecture, named as battery-free network, were proposed. In a typical battery-free network, the battery-free nodes are equipped with any battery and can only gain energy from the environment. Such network extremely expands the scope of the IoT applications, however, it also brings many troubles for some network operations, e.g. data collection, since the energy of each node is quite small. Considering that the Connected Dominating Sets (CDSs) are commonly used to support data collection and network communication in wireless networks, and thus we will also investigate the CDS construction problem in battery-free networks. In this paper, the problem of constructing CDS in a battery-free network is formally defined, and we prove that it is NP-Complete. Thus, four approximation algorithms were proposed to deal with the snapshot, continuous and time-window based CDS construction requirements, respectively. Finally, the extensive experiments were carried out and the results verify that the proposed algorithms have high performance in term of accuracy and efficiency.

Tree-based RFID identification adopts a binary-tree structure to collect IDs of an unknown set. Tag IDs locate at the leaf nodes and the reader queries through intermediate tree nodes and converges to these IDs using feedbacks from tag responses. Existing works cannot function well under random ID distribution as they ignore the distribution information hidden in the physical-layer signal of colliding tags. Different from them, we introduce PHY-Tree, a novel tree-based scheme that collects two types of distribution information from every encountered colliding signal. First, we detect if all colliding tags send the same bit content at each bit index by looking into inherent temporal features of the tag modulation schemes. If such resonant states are detected, either left or right branch of a certain subtree can be trimmed horizontally. Second, we estimate the number of colliding tags in a slot by computing a related metric defined over the signal's constellation map, based on which nodes in the same layers of a certain subtree can be skipped vertically. Evaluations from both experiments and simulations demonstrate that PHY-Tree outperforms state-of-the-art schemes by at least 1.79×.

Device localization is a highly important functionality for a range of applications. It is particularly beneficial in mmWave networks, where it can be used to reduce the beam training overhead and anticipate handovers between access points. In this paper, we present JADE, an algorithm that estimates the location of a mobile user in an indoor space without any knowledge about the surrounding environment (floor plan, location of walls and presence of reflective surfaces) or about the location and number of access points available therein. JADE leverages the beam procedure used in pre-standard and commercial mmWave equipment to estimate the angle-of-arrival of multipath components of the signal sent by visible access points. This information is then employed to localize the mobile user, estimate the position of access points and finally form a map of the environment. No radar-like ranging operations are required for this. Our results demonstrate that JADE can localize a user with sub-meter accuracy in the broad majority of the cases, and that it even outperforms localization algorithms that require full knowledge of the environment and access point positions.

Load balancing algorithms play a crucial role in delivering robust application performance in data centers and cloud networks. Recently, strong interest has emerged in Join-the-Idle-Queue (JIQ) algorithms, which rely on tokens issued by idle servers in dispatching tasks and outperform power-of-d policies. Specifically, JiQ strategies involve minimal information exchange, and yet achieve zero blocking and wait in the many-server limit. The latter property prevails in a multiple-dispatcher scenario when the loads are strictly equal among dispatchers. For various reasons it is not uncommon however for skewed load patterns to occur. We leverage product-form representations and fluid limits to establish that the blocking and wait then no longer vanish, even for arbitrarily low overall load. Remarkably, it is the least-loaded dispatcher that throttles tokens and leaves idle servers stranded, thus acting as bottleneck. Motivated by the above issues, we introduce two enhancements of the ordinary JIQ scheme where tokens are either distributed non-uniformly or occasionally exchanged among the various dispatchers. We prove that these extensions can achieve zero blocking and wait in the many-server limit, for any subcritical overall load and arbitrarily skewed load profiles. Extensive simulation experiments demonstrate that the asymptotic results are highly accurate, even for moderately sized systems.

Today's WiFi networks deliver a large fraction of traffic. However, the performance and quality of WiFi networks are still far from satisfactory. Among many popular quality metrics (throughput, latency), the probability of successfully connecting to WiFi APs and the time cost of the WiFi connection set-up process are the two of the most critical metrics that affect WiFi users' experience. To understand the WiFi connection set-up process in real-world settings, we carry out measurement studies on 5 million mobile users from 4 representative cities associating with 7 million APs in 0.4 billion WiFi sessions, collected from a mobile “WiFi Manager” App that tops the Android/iOS App market. To the best of our knowledge, we are the first to do such large scale study on: how large the WiFi connection set-up time cost is, what factors affect the WiFi connection set-up process, and what can be done to reduce the WiFi connection set-up time cost. Based on our data-driven measurement and analysis, we reveal the insights as follows: (1) Connection set-up failure and large connection set-up time cost are common in today's WiFi use. As large as 45% of the users suffer connection set-up failures, and 15% (5%) of them have large connection set-up time costs over 5 seconds (10 seconds). (2) Contrary to the state-of-the-art work, scan, one of the subphase of four phases in the connection set-up process, contributes the most (47%) to the overall connection set-up time cost. (3) Mobile device model and AP model can greatly help us to predict the connection set-up time cost if we can make good use of the hidden information. Based on the measurement analysis, we develop a machine learning based AP selection strategy that can significantly improve WiFi connection set-up performance, against the conventional strategy purely based on signal strength, by reducing the connection set-up failures from 33% to 3.6% and reducing 80% time costs of the connection set-up processes by more than 10 times.

Metropolitan areas witness significant fluctuations in mobile traffic due to patterns of human mobility. This fluctuation drastically deteriorates the efficiency and financial viability of conventional maximum-based network design. If networks are deployed to deal with the peak traffic rate at each site, their capacities are underutilized for most of time. To improve the efficiency of deploying base stations (BSs), this paper proposes a concept of an Autonomous Base Station with Optical Reflex Backhaul (ABSORB) architecture that can adapt to fluctuations in mobile traffic. In the ABSORB architecture, traffic at demand nodes is forwarded to and from an ABS with an arbitrary radio access technology (RAT). An ABS is connected to a gateway node through ORB, which consists of fiber optic networks. ABSs move to new locations following the demand movement, according to a relocation schedule that is periodically rearranged by an ABSORB controller. The network is flexibly reconstructed according to the demand distribution. The ABSORB architecture can be employed in various networks, and can coexist with traditional static architectures. It will drastically reduce the number of BSs, total deployment cost, and power consumption in comparison with the traditional design.

Real-time Calculus (RTC) is a non-stochastic queuing theory to the worst-case performance analysis of distributed real-time systems. Workload as well as resources are modelled as piece-wise linear, pseudo-periodic curves and the system under investigation is modelled as a sequence of algebraic operations over these curves. The memory footprint of computed curves increases exponentially with the sequence of operations and RTC may become computationally infeasible fast. Recently, Finitary RTC has been proposed to counteract this problem. Finitary RTC restricts curves to finite input domains and thereby counteracts the memory demand explosion seen with pseudo periodic curves of common RTC implementations. However, the proof to the correctness of Finitary RTC specifically exploits the operational semantic of the greed processing component (GPC) model and is tied to the maximum busy window size. This is an inherent limitation, which prevents a straight-forward generalization. In this paper, we provide a generalized Finitary RTC that abstracts from the operational semantic of a specific component model and reduces the finite input domains of curves even further. The novel approach allows for faster computations and the extension of the Finitary RTC idea to a much wider range of RTC models.

Distributed storage systems are known to be susceptible to long tails in response time. It has been shown that in modern online applications such as Bing, Facebook, and Amazon, the long tail of latency is of particular concern, with 99.9th percentile response times being orders of magnitude worse than the mean. As erasure codes emerge as a popular technique in distributed storage to achieve high data reliability while attaining space efficiency, taming tail latency remains an open problem due to the lack of mathematical models for analyzing such erasure-coded storage systems. In this paper, we quantify tail latency in distributed storage systems that employ erasure coding. In particular, we derive upper bounds on tail latency in closed-form for arbitrary service time distribution and heterogeneous files. Based on the model, we formulate an optimization problem to jointly minimize weighted latency tail probability of all files. The non-convex problem is solved using an efficient, alternating optimization algorithm. Simulation results show significant reduction of tail latency for erasure-coded storage systems with realistic workload.

In this paper, we investigate the problem of integrity auditing for cloud deduplication storage. Specifically, in addition to the outsourced data confidentiality, we also aim to ensure the integrity of the deduplicated cloud storage. With the existing works based on Provable Data Possession (PDP)/Proof of Retrievability (PoR), we are either required to rely on a fully trusted proxy server or inevitably sacrifice the privacy and efficiency. In contrast, we present a novel message-locked integrity auditing scheme without an additional proxy server, which is applicable to both file-level and chunk-level deduplication systems. In particular, our scheme is storage efficient in the sense that apart from eliminating the ciphertext redundancy, we also enable the integrity tag deduplication by a message-derived signing key, which merely incurs minimal client-side computation overhead. Besides, we can still publicly perform the integrity check over any client's cloud storage by incorporating the proxy re-signature technique. We show that the proposed scheme will not disclose the data ownership information and is provably secure under the Computational Diffie-Hellman (CDH) assumption in the random oracle model. Finally, the performance evaluation demonstrates its effectiveness and efficiency.

We consider the scenario where a cloud service provider (CSP) operates multiple geo-distributed datacenters to provide Internet-scale service. Our objective is to minimize the total electricity and bandwidth cost by jointly optimizing electricity procurement from wholesale markets and geographical load balancing (GLB), i.e., dynamically routing workloads to locations with cheaper electricity. Under the ideal setting where exact values of market prices and workloads are given, this problem reduces to a simple LP and is easy to solve. However, under the realistic setting where only distributions of these variables are available, the problem unfolds into a non-convex infinite-dimensional one and is challenging to solve. Our main contribution is to develop an algorithm that is proven to solve the challenging problem optimally and efficiently, by exploring the full design space of strategic bidding. Trace-driven evaluations corroborate our theoretical results, demonstrate fast convergence of our algorithm, and show that it can reduce the cost for the CSP by up to 20% as compared to baseline alternatives. Our study highlights the intriguing role of uncertainty. While variability in workloads deteriorates the cost-saving performance of joint electricity procurement and GLB, counter-intuitively, variability in market prices can be exploited to achieve a cost reduction even larger than the setting without price variability.

Social data outsourcing is an emerging paradigm for effective and efficient access to the social data. In such a system, a third-party Social Data Provider (SDP) purchases complete social datasets from Online Social Network (OSN) operators and then resells them to data consumers who can be any individuals or entities desiring the complete social data satisfying some criteria. The SDP cannot be fully trusted and may return wrong query results to data consumers by adding fake data and deleting/modifying true data in favor of the businesses willing to pay. In this paper, we initiate the study on verifiable social data outsourcing whereby a data consumer can verify the trustworthiness of the social data returned by the SDP. We propose three schemes for verifiable queries over outsourced social data. The three schemes all require the OSN provider to generate some cryptographic auxiliary information, based on which the SDP can construct a verification object for the data consumer to verify the query-result trustworthiness. They differ in how the auxiliary information is generated and how the verification object is constructed and verified. Extensive experiments based on a real Twitter dataset confirm the high efficacy and efficiency of our schemes.

As the cost of human full genome sequencing continues to fall, we will soon witness a prodigious amount of human genomic data in the public cloud. To protect the confidentiality of the genetic information of individuals, the data has to be encrypted at rest. On the other hand, encryption severely hinders the use of this valuable information, such as Genome-wide Range Query (GRQ), in medical/genomic research. While the problem of secure range query on outsourced encrypted data has been extensively studied, the current schemes are far from practical deployment in terms of efficiency and scalability due to the data volume in human genome sequencing. In this paper, we investigate the problem of secure GRQ over human raw aligned genomic data in a third-party outsourcing model. Our solution contains a novel secure range query scheme based on multi-keyword symmetric searchable encryption (MSSE). The proposed scheme incurs minimal ciphertext expansion and computation overhead. We also present a hierarchical GRQ-oriented secure index structure tailored for efficient and large-scale genomic data lookup in the cloud while preserving the query privacy. Our experiment on real human genomic data shows that a secure GRQ request with range size 100,000 over more than 300 million encrypted short reads takes less than 3 minutes, which is orders of magnitude faster than existing solutions.

Recently, a new paradigm of multiple access (MAC) along with one eavesdropper to achieve secrecy transmissions has been getting in focus. However, all existing work on such multiple access wiretap channel (MAC-WT) mainly concentrates on the secrecy performance of the system as a whole from an information theoretic perspective. In this work, we investigate the secrecy performance of a single transmitter in the quasi-static Rayleigh fading MAC-WT on basis of two decoding methods, zero-forcing (ZF) and minimum mean-square error (MMSE), jointly with successive interference cancellation (SIC). We evaluate the secrecy performance in three metrics: positive secrecy capacity probability, secrecy outage probability and effective secrecy throughput. The analytical and simulation results show that, 1) the SIC order has great impacts on the secrecy performance for both methods; 2) MMSE-SIC outperforms ZF-SIC, while the performance gap can be overcome via adjusting SIC order, or increasing SNR, or enhancing the spatial diversity gain; 3) in high SNR regime, the secrecy performance is only determined by the relative distance to eavesdropper over legitimate receiver rather than the SNR.

This paper studies how the efficiency of an online platform is impacted by the degree to which access of platform participants is open or controlled. The study is motivated by an emerging trend within platforms to impose increasingly fine-grained control over the options available to platform participants. While early online platforms allowed open access, e.g., Ebay allows any seller to interact with any buyer; modern platforms often impose matches directly, e.g., Uber directly matches drivers to riders. This control is performed with the goal of achieving more efficient market outcomes. However, the results in this paper highlight that imposing matches may create new strategic incentives that lead to increased inefficiency. In particular, in the context of networked Cournot competition, we prove that open access platforms guarantee social welfare within 7/16 of the optimal; whereas controlled allocation platforms can have social welfare unboundedly worse than optimal.

The ever increasing of display resolution on mobile devices raises high demand for GPU rendering details. However, the challenge of poor hardware support but fine-grained rendering details often makes user unsatisfied especially in calling for high frame rate scenarios, e.g., game. To resolve such issue, we propose BUTTERFLY, a novel system which collaboratively utilizes mobile GPUs to process high-quality rendering details for on-the-go mobile users. In particular, ButterFly achieves two technical contributions for the collaborative design: (1) a mobile device can migrate GPU workloads in buffer queue to peers, and (2) the collaborative rendering mechanism benefits user high quality details while significant power saving performance. Both techniques are compatible with the OpenGL ES standards. Furthermore, a 40-person survey perceives that ButterFly can provide excellent user experience of both rendering details and frame rate over Wi-Fi network. In addition, our comprehensive trace-driven experiments on Android prototype reveal the benefits of Butterfly have more superior performance over state-of-the-art systems, which achieves more than 28.3% power saving.

We investigate the potential gains of Physical-Layer Network Coding (PLNC) in multi-hop wireless networks. Physical-Layer Network Coding was first introduced as a solution to increase the throughput of a two-way relay channel communication. Unlike most wireless communications techniques which try to avoid collisions, PLNC allows two simultaneous transmissions to a common receiver. Such transmitted messages are summed at signal level and then decoded at packet level. In basic topologies, Physical-Layer Network Coding has been shown to significantly enhance the throughput performance compared to classical communications. However, the impact of PLNC in large multi-hop networks remains an open question. We therefore exploit Linear Programming to evaluate the impact of this paradigm in large realistic radio deployments. Our numerical results show that PLNC can increase the throughput in large multi-hop topologies by 30%. Such gains set theoretical benchmarks for designing new access methods and routing protocols to efficiently exploit the Physical-Layer Network Coding concept.

Distributed cloud networking builds on network functions virtualization (NFV) and software defined networking (SDN) to enable the deployment of network services in the form of elastic virtual network functions (VNFs) instantiated over general purpose servers at distributed cloud locations. We address the design of fast approximation algorithms for the NFV service distribution problem (NSDP), whose goal is to determine the placement of VNFs, the routing of service flows, and the associated allocation of cloud and network resources that satisfy client demands with minimum cost. We show that in the case of load-proportional costs, the resulting fractional NSDP can be formulated as a multi-commodity-chain flow problem on a cloud-augmented graph, and design a queue-length based algorithm, named QNSD, that provides an O(ε) approximation in time O (1/ε). We then address the case in which resource costs are a function of the integer number of allocated resources and design a variation of QNSD that effectively pushes for flow consolidation into a limited number of active resources to minimize overall cloud network cost.

Streaming data analytics has become increasingly vital in many applications such as dynamic content delivery (e.g., advertisements), Twitter sentiment analysis, and security event processing (e.g., intrusion detection systems, and spam filters). Emerging stream processing systems, such as Spark Streaming, treat the continuous stream as a series of micro-batches of data and continuously process these micro-batch jobs. Such micro-batch based stream processing provides several advantages over traditional stream processing systems, which process streaming data one record at a time, including fast recovery from failures, better load balancing and scalability. However, efficient scheduling of micro-batch jobs to achieve high throughput and low latency is very challenging due to the complex data dependency and dynamism inherent in streaming workloads. In this paper, we propose A-scheduler, an adaptive scheduling approach that dynamically schedules parallel micro-batch jobs in Spark Streaming and automatically adjusts scheduling parameters to improve performance and resource efficiency. Specifically, A-scheduler dynamically schedules multiple jobs concurrently using different policies based on their data dependencies and automatically adjusts the level of job parallelism and resource shares among jobs based on workload properties. We implemented A-scheduler and evaluated it with a real-time security event processing workload. Our experimental results show that A-scheduler can reduce end-to-end latency by 42% and improve workload throughput and energy efficiency by 21% and 13%, respectively, compared to the default Spark Streaming scheduler.

In order to cope with the severe path loss, millimeter-wave (mm-wave) systems exploit highly directional communication. As a consequence, even a slight beam mis-alignment between two communicating devices (for example, due to mobility) can generate a significant signal drop. This leads to frequent invocations of time-consuming mechanisms for beam re-alignment, which deteriorate system performance. In this paper, we propose smart beam training and tracking strategies for fast mm-wave link establishment and maintenance under node mobility. We leverage the ability of hybrid analog-digital transceivers to collect channel information from multiple spatial directions simultaneously and formulate a probabilistic optimization problem to model the temporal evolution of the mm-wave channel under mobility. In addition, we present for the first time a beam tracking algorithm that extracts information needed to update the steering directions directly from data packets, without the need for spatial scanning during the ongoing data transmission. Simulation results, obtained by a custom simulator based on ray tracing, demonstrate the ability of our beam training/tracking strategies to keep the communication rate only 10% below the optimal bound. Compared to the state of the art, our approach provides a 40% to 150% rate increase, yet requires lower complexity hardware.