INFOCOM 2016 论文列表

We study network response to a stream of queries that require computations on remotely located data, and we seek to characterize the network performance limits in terms of maximum sustainable query rate that can be satisfied. The available network setup consists of (i) a communication network graph with finite-bandwidth links over which data is routed, (ii) computation nodes with certain computation capacity, over which computation load is balanced, and (iii) network nodes that need to schedule raw and processed data transmissions. Our aim is to design a universal methodology and distributed algorithm to adaptively allocate resources in order to support maximum query rate. The proposed algorithms extend in a nontrivial way the backpressure (BP) algorithm to take into account computations carried out in the presence of query streams. They contribute to the fundamental understanding of network computation performance limits when the query rate is limited by both the communication bandwidth and the computation capacity, a classical setting that arises in streaming big data applications in network clouds and fogs.

We study distributed algorithms for achieving efficient communications in the Rayleigh-fading Model. This model extends the popular deterministic SINR model using stochastic propagation to address fading effects observed in reality. Stochastic propagation greatly increases the difficulty of dealing with interference and collisions, especially in a local context without much global knowledge. We present a new technique called Inductive Coloring that can be used to schedule fast transmissions with Rayleigh-fading interference. The computation of inductive coloring takes only O(log2n) time with the proposed distributed algorithm, where n is the number of nodes in the network. We illustrate the power of inductive coloring by giving algorithms for implementing two basic communication primitives. The first primitive is Local Broadcast (LB), which can work in a MAC layer and has been widely studied in different interference models. The proposed algorithm for LB matches the fastest one under the simpler SINR model. The second primitive is Single-Reception (SR), which is to make each node receive at least one message from its neighbors. The proposed algorithm can implement SR in O(log2n) rounds. To illustrate the versatility of the SR primitive, we use the primitive to derive efficient algorithms for information broadcast and function computations. We conduct simulations to verify all the proposed algorithms, and the results show that the algorithms also perform well in realistic environments.

MPEG DASH is a widely used standard for adaptive video streaming over HTTP. The conceptual architecture for DASH includes a web server and clients, which download media segments from the server. Clients select the resolution of video segments by using an Adaptive Bit-Rate (ABR) strategy; in particular, a throughput-based ABR is used in the case of live video applications. However, recent papers show that these strategies may suffer from the presence of proxies/caches in the network, which are instrumental in streaming video on a large scale. To face this issue, we propose to extend the MPEG DASH architecture with a Tracker functionality, enabling client-to-client sharing of control information. This extension paves the way to a novel family of Tracker-assisted strategies that allow a greater design flexibility, while solving the specific issue caused by proxies/caches; in addition, its utility goes beyond the problem at hand, as it can be used by other applications as well, e.g. for peer-to-peer streaming.

Wireless Power Transfer has become a commercially viable technology to charge devices because of the convenience of no power wiring and the reliability of continuous power supply. This paper concerns the fundamental issue of wireless charger placement with electromagnetic radiation (EMR) safety. Although there are a few wireless charging schemes consider EMR safety, none of them addresses the charger placement issue. In this paper, we propose PESA, a wireless charger Placement scheme that guarantees EMR SAfety for every location on the plane. First, we discretize the whole charging area and formulate the problem into the Multidimensional 0/1 Knapsack (MDK) problem. Second, we propose a fast approximation algorithm to the MDK problem. Third, we optimize our scheme to improve speed by double partitioning the area. We prove that the output of our algorithm is better than (1 - ϵ) of the optimal solution to PESA with a smaller EMR threshold (1 - ϵ/2)Rt and a larger EMR coverage radius (1 + ϵ/2)D. We conducted both simulations and field experiments to evaluate the performance of our scheme. Our experimental results show that in terms of charging utility, our algorithm outperforms the prior art by up to 45.7%.

Middleboxes are essential for a wide range of advanced traffic processing in modern enterprise networks. Recent trend of deploying middleboxes in cloud as virtualized services further expands potential benefits of middleboxes while avoiding local maintenance burdens. Despite promising, designing outsourced middleboxes still faces several security challenges. First, many middlebox processing services, like intrusion detection, require packet payload inspection, while the ever-increasing adoption of HTTPS limits the function due to the end-to-end encryption. Second, many packet inspection rules used by middleboxes can be proprietary in nature. They may contain sensitive information of enterprises, and thus need strong protection when configuring middleboxes in untrusted outsourced environments. In this paper, we propose a practical system architecture for outsourced middleboxes to perform deep packet inspection over encrypted traffic, without revealing either packet payloads or inspection rules. Our first design is an encrypted high-performance rule filter that takes randomized tokens from packet payloads for encrypted inspection. We then elaborate through carefully tailored techniques how to comprehensively support open-source real rulesets. We formally analyze the security strength. Implementations at Amazon Cloud show that our system introduces roughly 100 millisecond latency in each connection initialization, with individual processing throughput over 3500 packets/second for 500 concurrent connections.

This paper considers dynamic power allocation in MIMO fading systems with unknown channel state distributions. First, the ideal case of perfect instantaneous channel state information at the transmitter (CSIT) is treated. Using the drift-plus-penalty method, a dynamic power allocation policy is developed and shown to approach optimality, regardless of the channel state distribution and without requiring knowledge of this distribution. Next, the case of delayed and quantized channel state information is considered. Optimal utility is fundamentally different in this case, and a different online algorithm is developed that is based on convex projections. The proposed algorithm for this delayed-CSIT case is shown to have an O (δ) optimality gap, where δ is the quantization error of CSIT.

Distributed stream monitoring has numerous potential applications in future smart cities. Communication efficiency, and data privacy are two main challenges for distributed stream monitoring services. In this paper, we propose PriStream, the first communication-efficient and privacy-preserving distributed stream monitoring system for thresholded PERCENTILE aggregates. PriStream allows the monitoring service provider to evaluate an arbitrary function over a desired percentile of distributed data reports and monitor when the output exceeds a predetermined system threshold. Detailed theoretical analysis and evaluations show that PriStream has high accuracy and communication efficiency, and differential privacy guarantees under a strong adversary model.

Cloud computing allows on demand elastic service scaling. The capability of a service to predict resource requirements for the next operational period defines how well it will exploit the elasticity of cloud computing in order to reduce operational costs. In this work, we consider a capacity planning process for service scale-out as an online pricing model. In particular, we study the impact of buffering service requests on revenues in various settings with allocation and maintenance costs. In addition, we analyze the incurred latency implied by buffering service requests. We believe that our insights will allow to significantly simplify predictions and mitigate the unknowns of future demands on resources.

The inference of traffic volume of the whole network from partial traffic measurements becomes increasingly critical for various network engineering tasks, such as traffic prediction, network optimization, and anomaly detection. Previous studies indicate that the matrix completion is a possible solution for this problem. However, as a two-dimension matrix cannot sufficiently capture the spatial-temporal features of traffic data, these approaches fail to work when the data missing ratio is high. To fully exploit hidden spatial-temporal structures of the traffic data, this paper models the traffic data as a 3-way traffic tensor and formulates the traffic data recovery problem as a low-rank tensor completion problem. However, the high computation complexity incurred by the conventional tensor completion algorithms prevents its practical application for the traffic data recovery. To reduce the computation cost, we propose a novel Sequential Tensor Completion algorithm (STC) which can efficiently exploit the tensor decomposition result for the previous traffic data to deduce the tensor decomposition for the current data. To the best of our knowledge, we are the first to apply the tensor to model Internet traffic data to well exploit their hidden structures and propose a sequential tensor completion algorithm to significantly speed up the traffic data recovery process. We have done extensive simulations with the real traffic trace as the input. The simulation results demonstrate that our algorithm can achieve significantly better performance compared with the literature tensor and matrix completion algorithms even when the data missing ratio is high.

To guarantee correct operation of their networks, operators have to promptly detect and diagnose data-plane issues, like broken interface cards or link failures. Networks are becoming more complex, with a growing number of Equal Cost MultiPath (ECMP) and link bundles. Hence, some data-plane problems (e.g. silent packet dropping at one router) can hardly be detected with control-plane protocols or simple monitoring tools like ping or traceroute. In this paper, we propose a new technique, called SCMon, that enables continuous monitoring of the data-plane, in order to track the health of all routers and links. SCMon leverages the recently proposed Segment Routing (SR) architecture to monitor the entire network with a single box (and no additional monitoring protocol). In particular, SCMon uses SR to (i) force monitoring probes to travel over cycles; and (ii) test parallel links and bundles at a per-link granularity. We present original algorithms to compute cycles that cover all network links with a limited number of SR segments. Further, we prototype and evaluate SCMon both with simulations and Linux-based emulations. Our experiments show that SCMon quickly detects and precisely pinpoints data-plane problems, with a limited overhead.

Crowdsourced spectrum sensing has great potential in improving current spectrum database services. Without strong incentives and location privacy protection in place, however, mobile users will be reluctant to act as mobile crowdsourcing workers for spectrum sensing tasks. In this paper, we present PriCSS, the first framework for a crowdsourced spectrum sensing service provider to select spectrum-sensing participants in a differentially privacy-preserving manner. Thorough theoretical analysis and simulation studies show that PriCSS can simultaneously achieve differential location privacy, approximate social cost minimization, and truthfulness.

Time synchronization is an enabling service that allows devices to share a consistent notion of time and thus makes it easier to build efficient and robust collaborative services. However, existing synchronization protocols based on wireless packet transmissions are not energy efficient because powering the radio often consumes a significant fraction of the energy budget. In this paper, we propose PSync, a visible light-based time synchronization protocol that relies on an LED light source and is highly energy efficient for the receivers. The key novelty in our protocol is the use of a De Bruijn sequence to provide a rough estimate of time using a minimum amount of information. Experiments show that our scheme achieves an average synchronization error of 1.3 timer ticks (32 μs per clock tick). In addition, the additional energy consumed for one round of synchronization based on PSync can be as low as 19% of the energy needed to receive a small packet (1 byte) using IEEE 802.15.4 radio.

Interventions such as vaccinations or installing anti-virus software are common strategies for controlling the spread of epidemics and malware on complex networks. Typically, nodes decide whether to implement such an intervention independently, depending on the costs they incur. A node can be protected by herd immunity, if enough other nodes implement such an intervention, making the problem of determining strategic decisions for vaccination a natural game-theoretical problem. There has been a lot of work on vaccination and network security game models, but all these models assume the vaccination decisions are made at the start of the game. However, in practice, a lot of individuals defer their vaccination decision, and the reasons for this behavior are not well understood, especially in network models. In this paper, we study a novel repeated game formulation, which considers vaccination decisions over time. We characterize Nash equilibria and the social optimum in such games, and find that a significant fraction of vaccinations might be deferred, in general. This depends crucially on the network structure, and the information and the vaccination delay. We show that finding Nash equilibria and the social optimum are NP-hard in general, and we develop an approximation algorithm for the social optimum whose approximation guarantee depends on the delay.

Mobile data demand is increasing tremendously, and thus new pricing models are in urgent need. One promising new pricing scheme is the “sponsored data plan”, i.e., end users may enjoy free access to contents from certain content providers, while these content providers will pay ISPs for corresponding traffic consumed by end users. Proven a number of advantages, the sponsored data plan is still in its infancy. In this paper, we explore some potential of further development of this plan. We extend the design space and propose the idea of time-dependent, sponsoring, i.e, content providers can decide when to sponsor how much fractions of traffic. The key intuition is by migrating some traffic consumption from peak to valley times, bandwidth resources can be better utilized. We formulate a game model to study the interactions between the ISP, CPs and users, and derive the optimal sponsoring fractions over various times under this new plan. We show that all parties involved can benefit from this plan, and social welfare increases. We believe our proposal, i.e., time-dependent sponsoring, provides important insights to potential development of the sponsored data plan.

We consider an opportunistic wireless network where data repositories provide mobile users access to locally-cached data objects. In this setting using network/erasure coding to disseminate large data objects can greatly improve the performance and robustness of the network, but it becomes more difficult to plan, coordinate, and analyze the distribution of information. We introduce a simplicial data structure, the coverage complex, that captures enough of both the structure of the code and the geometry of the network that it can be used to draw conclusions about network coded data coverage. We give a distributed algorithm for computing the coverage complex based on local information, prove results on using it for coverage testing, and study more complicated cases where coverage testing can fail.

Small cells deployed in licensed spectrum and unlicensed access via WiFi provide different ways of expanding wireless services to low mobility users. That reduces the demand for conventional macro-cellular networks, which are better suited for wide-area mobile coverage. The mix of these technologies seen in practice depends in part on the decisions made by wireless service providers that seek to maximize revenue, and allocations of licensed and unlicensed spectrum by regulators. To understand these interactions we present a model in which a service provider allocates available licensed spectrum across two separate bands, one for macro- and one for small-cells, in order to serve two types of users: mobile and fixed. We assume a service model in which the providers can charge a (different) price per unit rate for each type of service (macro- or small-cell); unlicensed access is free. With this setup we study how the addition of unlicensed spectrum affects prices and the optimal allocation of bandwidth across macro-/small-cells. We also characterize the optimal fraction of unlicensed spectrum when new bandwidth becomes available.

The use of mobile phones while driving has become a major source of distraction to drivers, leading to a large number of car accidents. In this paper, we study the problem of automatically detecting driver phone calls by monitoring smartphone activities and utilizing the vehicle on-board unit. The challenges to overcome include: i) passenger phone calls should be allowed while the calls of the driver should be blocked; ii) the detection mechanism should be phone position-independent and phone owner-independent as the driver may put the smartphone at any position in the front row and make calls via an earphone, or the driver may borrow a passenger's phone to make a call; iii) the in-vehicle environment is noisy resulted from the operating engine, the music the driver and passenger may listen to, and the conversation between passengers and/or the driver; and iv) the computational cost at the smartphone should be light as realtime phone call detection is expected to effectively block an ongoing call to and from the driver. To overcome these challenges and achieve our objective of detecting driver phone calls, we take advantage of the uniqueness of individual's voice features. Through a short period of learning stage, our proposed system can recognize the driver's voice from the collected audio data. Combined with the smartphone's call state, our scheme can determine whether the driver is participating in the current phone call or not. Our strategy takes into account the complicated in-vehicle environment, and the proposed algorithm does not rely on the location of the phone within the vehicle nor the ownership of the smartphone, as the most existing driver phone call detection mechanisms do. We develop a client-server based system with the smartphones being the clients and the vehicle on-board unit being the server. To validate our mechanism, we perform extensive real-world experiments under different scenarios. The results demonstrate a high probability of detecting driver phone calls with a small false alarm rate.

We study the problem faced by a wireless service provider (SP) when offering a “sponsored content” service to multiple content providers (CPs). Each CP specifies the value that it would obtain from additional content views together with estimates on the underlying demand for its content. The SP then determines which CPs should sponsor their content along with the price for doing so. This basic framework has been studied in a variety of different contexts in recent years. However, previous work typically assumes that the CP parameters are reported truthfully to the SP. Another common assumption is that each CP has an independent traffic stream, i.e. there is no notion of competition between CPs in similar markets. In this work we address both of these issues. We present a pricing scheme that optimizes SP profit subject to CPs being incentivized to reveal their valuation and number of potential views in a truthful manner. We also examine how the model is affected if CPs in the same market are vying to sponsor a common pool of content.

With advances in wireless communication technology, more and more people depend heavily on portable mobile devices for businesses, entertainments and social interactions. Although such portable mobile devices can offer various promising applications, their computing resources remain limited due to their portable size. This however can be overcome by remotely executing computation-intensive tasks on clusters of near by computers known as cloudlets. As increasing numbers of people access the Internet via mobile devices, it is reasonable to envision in the near future that cloudlet services will be available for the public through easily accessible public wireless metropolitan area networks (WMANs). However, the outdated notion of treating cloudlets as isolated data-centers-in-a-box must be discarded as there are clear benefits to connecting multiple cloudlets together to form a network. In this paper we investigate how to balance the workload between multiple cloudlets in a network to optimize mobile application performance. We first introduce a system model to capture the response times of offloaded tasks, and formulate a novel optimization problem, that is to find an optimal redirection of tasks between cloudlets such that the maximum of the average response times of tasks at cloudlets is minimized. We then propose a fast, scalable algorithm for the problem. We finally evaluate the performance of the proposed algorithm through experimental simulations. The experimental results demonstrate the significant potential of the proposed algorithm in reducing the response times of tasks.