INFOCOM 2016 Papers

We wonder that in a competitive environment, how an influence uses the minimum cost to choose seeds such that its influence spread can reach a desired threshold under thwarting from its competitors. At first we take a simple fact into account: the information arriving first has heavy impact, and present Competitive — Independent Cascade (C-IC) model to characterize how different influences competing with others in a social network. We have found that a specific influence's spread is monotone and submodular, and these nice properties make algorithm performance tractable. We then propose Minimum Cost Seed Set problem (MinSeed) to answer our original concern and give a greedy algorithm. We analyze the ratio of greedy algorithm, and give result significantly better than similar ones analyzed by others. Noticing that the computation of real information spread is hard to compute and simple greedy is too time consuming, we design an effective method for estimating information spread in C-IC model, and devise scalable algorithm applying for large social networks. Through simulation on real world datasets, we confirm that, our scalable algorithm outputs seed set with small total cost comparable to that given by simple greedy, with very fast computation.

In cognitive radio networks (CRNs), dynamic spectrum access has been proposed to improve the spectrum utilization, but it also generates spectrum misuse problems. One common solution to these problems is to deploy monitors to detect misbehaviors on certain channel. However, in multi-channel CRNs, it is very costly to deploy monitors on every channel. With a limited number of monitors, we have to decide which channels to monitor. In addition, we need to determine how long to monitor each channel and in which order to monitor, because switching channels incurs costs. Moreover, the information about the misuse behavior is not available a priori. To answer those questions, we model the spectrum usage monitoring problem as an adversarial multi-armed bandit problem with switching costs and design two effective online algorithms, SpecWatch and SpecWatch+. In SpecWatch, we select strategies based on the monitoring history and repeat the same strategy for certain timeslots to reduce switching costs. We prove its expected weak regret, i.e., the performance difference between the solution of SpecWatch and optimal (fixed) solution, is O(T2/3), where T is the time horizon. Whereas, in SpecWatch+, we select strategies more strategically to improve the performance. We show its actual weak regret is O(T2/3) with probability 1-δ, for any δ e (0,1). Both algorithms are evaluated through extensive simulations.

Per-flow measurement can provide fine-grained statistics for advanced network management and thus has been studied extensively. As network line rate continues its rapid growth, wire-speed per-flow measurement meets great challenges, for large numbers of statistics counters are required to record flow information at extremely high speed. Most of the previous efforts are committed to elaborate excellent sampling algorithms to make counters' memory occupation as small as possible, so as to fit into off-chip SRAM(s), but the throughput is rigidly bounded by the speed of SRAM. To break the wall, we explore a new path by proposing CASE: a cache-assisted stretchable estimator, which uses the on-chip memory as the fast cache of the off-chip SRAM. In this way, most of the accesses to the counters will happen on cache, thanks to the heavy-tailed distribution of Internet traffic. In this paper, we present CASE's design and derive strict mathematical proof to its relative error bound. Extensive experiments on real-world traces are conducted and the evaluation results indicate CASE can achieve up to 300Gbps throughput when using on-chip memory with 128K entries (equivalent to 1.125MB). Meanwhile CASE is more accurate and stretchable than uncached approaches.

For many emerging mobile broadband services and applications, the source and destination are located in the same local region. Consequently, it is very important to design access networks to facilitate efficient local data exchange. In the past few years, most existing studies focus on either the wired or wireless domains. In this paper, we aim to exploit both the wired and wireless domains. Specifically, we consider a Fiber-Wireless access network in which a passive optical network (PON) connects densely deployed base stations. In such a scenario, we propose a novel access scheme, namely, NCDA, where the main idea is to utilize both network coding and device association. To understand the potentials of NCDA, we first formulate a mixed integer nonlinear programming (MINLP) to minimize the weighted number of packet transmissions (WNT), which is related to both the system capacity and energy consumption. We then theoretically analyze the tight upper bounds of the minimal WNT in the PON, which helps us to approximate the original problem by a mixed integer linear programming (MILP). Next, we develop efficient algorithms based on linear programming relaxation to solve the optimal NCDA problem. To validate our design, we conduct extensive simulation experiments, which demonstrate the impact of important network parameters and the promising potentials of the proposed scheme.

Both interference alignment (IA) and interference neutralization (IN) are exploited for Coordinated Multi-Point (CoMP) transmissions. With the base station's cooperation, transmit precoder and receive filter are designed jointly, and then concurrent transmissions of multiple data streams are achieved. In the design of preprocessing, IN is applied to the interferences carrying same data so as to align the interfering signals with opposite directions in a subspace. On the other hand, for interferences carrying different information, IA is employed to align them with the same direction in a subspace, thus reducing the interference signal dimension observed at the user side. Based on different precoding schemes at the transmitter's side, receivers adopt zero-forcing (ZF) so as to recover the desired data. The proposed interference alignment and neutralization based CoMP (IAN-CoMP) mechanism can achieve effective interference cancellation and suppression by exploiting limited and flexible collaboration only at the base station (BS) side. We also extend the mechanism to general cases where the antenna configurations at both transmitter and receiver side, the number of transmitters participating in CoMP and simultaneously served users are variable. In addition, the proposed scheme can also achieve a flexible tradeoff between cooperation overhead and the system's achievable degrees of freedom (DoFs). Our in-depth simulation results show that IAN-CoMP can significantly improve the spectral efficiency (SE) for cell-edge users.

Multi-cell interference coordination via Block Diagonalization (BD), which is widely used in LTE-Advanced interference management, has three main drawbacks: (1) limitation on the number of supported co-channel users; (2) performance degradation in Doppler channels with feedback delay and quantization; and (3) high signaling overhead to exchange Channel State Information (CSI) and to generate precoding matrix. In this paper, a new approach is proposed to overcome these drawbacks and to improve the multi-cell interference coordination. The core idea is to create a null space only to the users within one cell; to achieve this goal, Zadoff-Chu Sequence (ZCS) spreading is used to eliminate the multi-cell interference by leveraging the zero-correlation property of cyclic shifts of the ZCS. This way, the capacity of the cellular network is improved in Doppler channels with delayed and quantized feedback; moreover, signaling overhead and computational complexity are both reduced. The auxiliary sampling capability of the hardware is utilized to realize the higher sampling rate required by the proposed approach. The new interference-management solution is compared against the existing one via computer simulations and is shown to lead to significant capacity gains even in high-mobility scenarios.

We consider the problem of maximizing performance in multihop wireless networks while achieving fairness among flows. While time-based fairness has been widely recognized as the appropriate fairness mechanism in single-hop wireless networks, no analogous notion has been developed for multihop wireless networks. We define the first general notion of time-based fairness for multihop networks by abstracting a network into a virtual single-hop network and applying the single-hop time-based fairness notion. This produces rate shares for each flow in the network, and we develop a constructive method for achieving these rate shares through physical-interference-aware scheduling. When combined with an appropriate link transmission policy, this scheduling approach preserves the time-based-fair rate shares for flows even with spatial reuse and the resulting rate reductions that occur among concurrent links. To our best knowledge, this is the first constructive approach for achieving fair rate shares in multihop wireless networks with or without interference consideration. We also prove that, with an appropriate scheduling algorithm, this approach produces an aggregate rate that is within a constant factor of the maximum aggregate rate subject to time-based fairness. Finally, we perform extensive simulations, which show that our approach as much as doubles the aggregate rate of a solution that approximates max-min fairness, while achieving a more natural fairness property.

This paper is driven by a simple question of whether traffic engineering in Software Defined Networking (SDN) can react quickly to bursty and unpredictable changes in traffic demand. The key challenge is to strike a careful balance between the overhead (frequently involving the SDN controller) and performance (the degree of congestion measured as the maximum load and the balance between the minimum and the maximum loads). Exploiting OpenFlow (OF) features, quick shift of routing paths for unpredictable traffic bursty is the focal point of this work. It is achieved by using a dual routing scheme and letting the data plane to select the appropriate path in reacting to uncertainty in traffic load. The proposed work is called DUCE (Demand Uncertainty Configuration sElection). Further, we describe a traffic distribution model, an optimization solution that calculates congestion-free traffic distribution plan which guarantees that each switch can select one of the paths in a distributed way, and moreover, OF details about detaching the functionality of responding to the demand uncertainty from the control plane and delegating it to the data plane. Simulations are performed validating the efficiency of DUCE under various network scenarios.

With the increasing adoption of cloud computing, a growing number of users outsource their datasets into cloud. The datasets usually are encrypted before outsourcing to preserve the privacy. However, the common practice of encryption makes the effective utilization difficult, for example, search the given keywords in the encrypted datasets. Many schemes are proposed to make encrypted data searchable based on keywords. However, keyword-based search schemes ignore the semantic representation information of users retrieval, and cannot completely meet with users search intention. Therefore, how to design a content-based search scheme and make semantic search more effective and context-aware is a difficult challenge. In this paper, we proposed an innovative semantic search scheme based on the concept hierarchy and the semantic relationship between concepts in the encrypted datasets. More specifically, our scheme first indexes the documents and builds trapdoor based on the concept hierarchy. To further improve the search efficiency, we utilize a tree-based index structure to organize all the document index vectors. Our experiment results based on the real world datasets show the scheme is more efficient than previous scheme. We also study the threat model of our approach and prove it does not introduce any security risk.

Energy consumption is a fundamental and critical issue in wireless sensor networks. Mobile sensors consume much more energy during the movement than that during the communication or sensing process. Thus how to schedule mobile sensors and minimize their moving distance has great significance to researchers. In this paper, we study the target coverage problem in mobile sensor networks. Our goal is to minimize the moving distance of sensors to cover all targets in the surveillance region. Here initially all the sensors are located at k base stations. Thus we define this problem as k-Sink Minimum Movement Target Coverage. To solve this problem, we propose a PTAS, named Energy Effective Movement Algorithm (EEMA). We can divide EEMA into two phases. In the first phase, we partition the surveillance region into some subareas. In the second phase, we select subareas and schedule sensors to the selected subareas. We also prove that the approximation ratio of EEMA is 1 + ε and the time complexity is ηO(1/ε2 Finally, we conduct experiments to validate the efficiency and effectiveness of EEMA.

In an era of networks in which any individual is connected with one another, such as Internet of Things (IoT) and Online Social Networks (OSNs), the networks are evolving into complex systems, carrying a huge volume of information that may provoke even more. An interesting, yet challenging question is how such information dissemination evolves, that is, to continue or to stop. Specifically, we aim to find out the aftermath of epidemic spreading via individuals and conflicting information dissemination. From a holistic, networking view, it is impossible to take every aspect into accounts for complex networks toward these questions. Therefore, we establish a Susceptible-Infectious-Cured (SIC) propagation model to examine two simple network topologies, clique and star, in terms of extinction time and half-life time of information under controllable, epidemic dynamics. For a network of size n, both theoretical and numerical results suggest that extinction time and half-life time are O(log n/n) for clique networks, and O(log n) for star networks. More interestingly, given an initial network state I0, the extinction time is constant (O(1)) for cliques, and O(log I0) for stars; while the half-life time is O(log 1/I0) for both clique and star networks, respectively. In addition, we developed a method to estimate the conditional infection count distribution, which indicates the scope of information dissemination.

Synchronizing videos over file-hosting services on personal cloud such as Dropbox, Box or Onedrive leads to wastage in bandwidth and storage, which can be critical, while using mobile devices. Users can alternatively download the video on-the-go, but that leads to high latency, depending on network bandwidth and video file size. In contrast, adaptive video streaming allows near-real-time viewing by streaming the best possible quality in a given network condition. This feature is achieved by keeping multiple versions of video in cloud, leading to additional costs in cloud storage. Moreover, current solutions can only support a small set of bitrates, leading to abrupt switches in video resolution especially when the network condition is unstable, as often experienced by mobile users. This paper introduces Vsync, a framework for cloud based video synchronization for mobile devices. A video content is streamed using a cloud-based real-time transcoding and transmission framework to provide smooth video quality. Built over prediction models for video transcoding sessions and a QoE based adaptive video streaming protocol, Vsync is able to obtain the improvements of 37 ~ 80% than other compared schemes. The dataset and evaluation was done on a pool of 220K video clips.

With the proliferation of online video, measuring quality of experience (QoE) has become a pivotal aspect for the analysis of today's over-the-top (OTT) video streaming. To monitor video QoE, we introduce YouSlow that can detect various playback events (e.g., start-up latency, rebufferings and bitrate changes) from video players while a video is being played. Using YouSlow, we have collected more than 400,000 YouTube views from more than 100 countries. We measured the impact of these playback events on video abandonment and found that rebufferings incur abandonment rates six times higher than start-up latency, mostly caused by pre-roll ads. A single rebuffering event has three times the impact of a bitrate change. Even increasing the bitrate can raise abandonment rates by a factor of four compared to keeping the bitrate constant.

Computational RFID (CRFID) devices are emerging platforms that can enable perennial computation and sensing by eliminating the need for batteries. Although much research has been devoted to improving upstream (CRFID to RFID reader) communication rates, the opposite direction has so far been neglected, presumably due to the difficulty of guaranteeing fast and error-free transfer amidst frequent power interruptions of CRFID. With growing interest in the market where CRFIDs are forever-embedded in many structures, it is necessary for this void to be filled. Therefore, we propose Wisent — a robust downstream communication protocol for CRFIDs that operates on top of the legacy UHF RFID communication protocol: EPC C1G2. The novelty of Wisent is its ability to adaptively change the frame length sent by the reader, based on the length throttling mechanism, to minimize the transfer times at varying channel conditions. We present an implementation of Wisent for the WISP 5 and an off-the-shelf RFID reader. Our experiments show that Wisent allows transfer up to 16 times faster than a baseline, non-adaptive shortest frame case, i.e. single word length, at sub-meter distance. As a case study, we show how Wisent enables wireless CRFID reprogramming, demonstrating the world's first wirelessly reprogrammable (software defined) CRFID.

The majority of Internet traffic is now dominated by streamed video content. As video quality continues to increase, the strain that streaming traffic places on the network infrastructure also increases. Caching content closer to users, e.g., using Content Distribution Networks, is a common solution to reduce the load on the network. A simple approach to selecting what to put in regional caches is to put the videos that are most popular globally across the entire customer base. However, this approach ignores distinct regional taste. In this paper we explore the question of how a video content provider could go about determining whether or not they should use a cache filling policy based solely upon global popularity or take into account regional tastes as well. We propose a model that captures the overlap between inter-regional and intra-regional preferences. We focus on movie content and derive a synthetic model that captures “taste” using matrix factorization, similarly to the method used in recommender systems. Our model enables us to widely explore the parameter space, and derive a set of metrics providers can use to determine whether populating caches according to regional of global tastes provides better cache performance.

Crowdsourcing data from multiple sensing agents has become a fundamental mechanism for extracting information in large-scale cyber-physical systems (CPS). However, there has been little attention paid to the difficulties crowdsourcing presents when the desired information is represented by continuous signals. Crowdsourcing can result in unique types of noise in the aggregated data sample set. Errors from clock synchronization, GPS location determination, or sensor heterogeneity result in biased and correlated errors in the sampled data from each individual sensor. Furthermore, in CPS sensors are often mobile and operate asynchronously. This affects the spatial sampling rates among sensors and results in nonuniform sample spacing. We refer to these sampling issues as the noisy multi-source, variable-rate (MSVR) sampling problem. This work introduces and investigates signal reconstruction algorithms given MSVR sampling conditions. These signal reconstructions are investigated for vehicular applications, using a joint road inclination and bank angle signal estimation algorithm that has access to MSVR sampled vehicle GPS and accelerometer data. The signal reconstruction and angle determination algorithms are validated on simulated and real-world vehicle data, where we reconstruct a road elevation signal with 0.89 m root-mean-square error.

In this paper we address the problem of finding top k eigenvalues and corresponding eigenvectors of symmetric graph matrices in networks in a distributed way. We propose a novel idea called complex power iterations in order to decompose the eigenvalues and eigenvectors at node level, analogous to time-frequency analysis in signal processing. At each node, eigenvalues correspond to the frequencies of spectral peaks and respective eigenvector components are the amplitudes at those points. Based on complex power iterations and motivated from fluid diffusion processes in networks, we devise distributed algorithms with different orders of approximation. We also introduce a Monte Carlo technique with gossiping which substantially reduces the computational overhead. An equivalent parallel random walk algorithm is also presented. We validate the algorithms with simulations on real-world networks. Our formulation of the spectral decomposition can be easily adapted to a simple algorithm based on quantum random walks. With the advent of quantum computing, the proposed quantum algorithm will be extremely useful.

Mobile Cloud Computing (MCC) bridges the gap between limited capabilities of mobile devices and the increasing complexity of mobile applications, by offloading the computational workloads from local devices to the cloud. Current research supports workload offloading through appropriate application partitioning and remote method execution, but generally ignores the impact of wireless network characteristics on such offloading. Wireless data transmissions incurred by remote method execution consume a large amount of additional energy during transmission intervals when the network interface stays in the high-power state, and deferring these transmissions increases the response delay of mobile applications. In this paper, we adaptively balance the tradeoff between energy efficiency and responsiveness of mobile applications by developing application-aware wireless transmission scheduling algorithms. We take both causality and run-time dynamics of application method executions into account when deferring wireless transmissions, so as to minimize the wireless energy cost and satisfy the application delay constraint with respect to the practical system contexts. Systematic evaluations show that our scheme significantly improves the energy efficiency of workload offloading over realistic smartphone applications.

In an effort to meet growing demands on the radio frequency spectrum, regulators are exploring methods to enable band sharing among a diverse set of user devices. Proposed spectrum access systems would dynamically assign spectrum resources to users, maintaining databases of spectrum use information. While these systems are anticipated to increase the efficiency of spectrum sharing, incumbent users have raised concerns about exposing details of their operations and have questioned whether their privacy can be protected. In this paper, we explore whether primary users can retain a critical level of privacy when a system uses their information to enable dynamic access to the spectrum by other users. Under a variety of operational scenarios and user models, we examine adversary techniques to exploit the spectrum access system and obfuscation strategies to protect user privacy. We also develop analytical methods to quantify the performance of both the adversary and obfuscation strategies. To our knowledge, this is the first work that considers the privacy of a primary user in the setting of a highly dynamic spectrum access system. Privacy analysis of this kind will help to enable adoption of shared spectrum access systems by allowing incumbent users to quantify and mitigate risks to their privacy.