INFOCOM 2016 论文列表

Nearly every setting is increasingly populated with wireless and mobile devices - whether appliances in a home, medical devices in a health clinic, sensors in an industrial setting, or devices in an office or school. There are three fundamental operations when bringing a new device into any of these settings: to configure the device to join the wireless local-area network, to partner the device with other nearby devices so they can work together, and (3) to configure the device so it connects to the relevant individual or organizational account in the cloud. The challenge is to accomplish all three goals simply, securely, and consistent with user intent. We present a novel approach we call Wanda - a `magic wand' that accomplishes all three of the above goals - and evaluate a prototype implementation.

In the past years, the centralized management of dense wireless local area networks has been emerged as a powerful paradigm for improving energy efficiency as well as avoiding severe interference. In this paper, we study the joint optimization on power-operation modes in access points (APs), channel selections and user-AP associations for improving energy efficiency and avoiding interference without sacrificing users' demands. To this end, we first formulate it as a mixed-integer programming using the popular Lyapunov approach, but it turns out to be computationally intractable, i.e., NP-hard. To address the issue, we propose a polynomial-time approximation algorithm and prove that it achieves a constant-factor approximation guarantee under mild assumptions. The main novelty underlying our algorithm design is based on a linear programming relaxation combining with two different greedy rounding schemes, where each achieves a constant-factor approximation in different regimes of parameters. We verify the performance of the proposed algorithm via extensive simulations and also demonstrate its practicability by implementing it at commercial APs using a Software-defined Networking framework, which shows that it reduces the wasted energy significantly while maintaining even higher throughput.

Timekeeping is central to network measurement. In typical systems, its accuracy is ultimately dependent on the forest of timeservers accessible over the network, whose roots are the stratum-1 timeservers, which benefit from reference hardware. It is essential that these servers are accurate and reliable, and it is commonly assumed that this is the case. We put this belief to the test through an examination of around 100 publicly accessible stratum-1 servers, using datasets spanning over 3 years, collected in a testbed with reference timestamping. We develop a methodology capable of disambiguating the effects of routing changes, congestion related variability, and server anomalies on timestamps. We use it to make a first assessment of the health of (public) network timing, by reporting on the type, severity, and frequency of anomalies we encounter.

To ensure security, cloud service providers employ security groups as a key tool for cloud tenants to protect their virtual machines (VMs) from attacks. However, security groups can be complex and often hard to configure, which may result in security vulnerabilities that impact the entire cloud platform. The goal of this paper is to investigate and understand how cloud tenants configure security groups and to assist them in designing better security groups. We first conduct a measurement-based analysis of security group configuration and usage by tenants in an IaaS cloud. We then propose and develop a tool called Socrates, which enables tenants to visualize and hence understand the static and dynamic access relations among VMs. Socrates also helps diagnose potential misconfigurations and provides suggestions to refine security group configurations based on observed traffic traversing tenants' VMs. Applying Socrates to all tenants hosted on the IaaS cloud, we analyze the common usage (“good” as well as “bad” practices) of cloud security groups and report the key lessons learned in our study. To the best of our knowledge, our work is the first to analyze cloud security group usage based on real-world datasets, and to develop a system to help cloud tenants understand, diagnose and better refine their security group configurations.

Content-Centric Networking (CCN) naturally supports multi-path communication, as it allows the simultaneous use of multiple interfaces (e.g. LTE and WiFi). When multiple sources and multiple clients are considered, the optimal set of distribution trees should be determined in order to optimally use all the available interfaces. This is not a trivial task, as it is a computationally intense procedure that should be done centrally. The need for central coordination can be removed by employing network coding, which also offers improved resiliency to errors and large throughput gains. In this paper, we propose NetCodCCN, a protocol for integrating network coding in CCN. In comparison to previous works proposing to enable network coding in CCN, NetCodCCN permits Interest aggregation and Interest pipelining, which reduce the data retrieval times. The experimental evaluation shows that the proposed protocol leads to significant improvements in terms of content retrieval delay compared to the original CCN. Our results demonstrate that the use of network coding adds robustness to losses and permits to exploit more efficiently the available network resources. The performance gains are verified for content retrieval in various network scenarios.

Functioning as an intermediary between cloud tenants and providers, cloud service brokerages (CSBs) bring about great benefits to the cloud market. To maximize its own profit, a CSB is faced with a challenge: how to reserve servers and distribute tenant demands to the reserved servers such that the total reservation cost is minimized while the reserved servers can satisfy the tenant service level agreement (SLA)? Demand prediction and demand allocation are two steps to solve this problem. However, previous demand prediction methods cannot accurately predict tenant demands since they cannot accurately estimate prediction errors and also assume the existence of seasonal periods of demands. Previous demand allocation methods only aim to minimize the number of reserved servers rather than the server reservation cost, which is more challenging. To solve this challenge, we propose a Probabilistic Demand Allocation system (PDA). It predicts demands and more accurate prediction errors without the assumption of the existence of seasonal periods. It then formulates a nonlinear programming problem and has a decentralized method to find the problem solution. In addition to overcoming the shortcomings in previous methods, PDA is novel in that rather than separately conducting the prediction and demand allocation, it considers prediction errors in demand allocation in order to allocate demands with offsetting prediction errors (e.g., -1 and +1) to the same server, which helps find the problem solution. Both simulation and real-world experimental results demonstrate the superior performance of our system in reducing servers' reservation cost.

Distributed caching architectures have been proposed for bringing content close to requesters and the key problem is to design caching algorithms for reducing content delivery delay. The problem obtains an interesting new twist with the advent of advanced layered-video encoding techniques such as Scalable Video Coding (SVC). We show that the problem of finding the caching configuration of video encoding layers that minimizes average delay for a network operator is NP-Hard, and we establish a pseudopolynomial-time optimal solution using a connection with the multiple-choice knapsack problem. We also design caching algorithms for multiple operators that cooperate by pooling together their co-located caches, in an effort to aid each other, so as to avoid large delays due to downloading content from distant servers. We derive an approximate solution to this cooperative caching problem using a technique that partitions the cache capacity into amounts dedicated to own and others' caching needs. Numerical results based on real traces of SVC-encoded videos demonstrate up to 25% reduction in delay over existing (layer-agnostic) caching schemes, with increasing gains as the video popularity distribution gets steeper, and cache capacity increases.

Task-aware flow schedulers collect task information across the data center to optimize task-level performance. However, the majority of the tasks, which generate short flows and are called tiny tasks, have been largely overlooked by current schedulers. The large number of tiny tasks brings significant overhead to the centralized schedulers, while the existing decentralized schedulers are too complex to fit in commodity switches. In this paper we present OPTAS, a lightweight, commodity-switch-compatible scheduling solution that efficiently monitors and schedules flows for tiny tasks with low overhead. OPTAS monitors system calls and buffer footprints to recognize the tiny tasks, and assigns them with higher priorities than larger ones. The tiny tasks are then transferred in a FIFO manner by adjusting two attributes, namely, the window size and round trip time, of TCP. We have implemented OPTAS as a Linux kernel module, and experiments on our 37-server testbed show that OPTAS is at least 2.2× faster than fair sharing, and 1.2× faster than only assigning tiny tasks with the highest priority.

Operators, struggling to continuously add capacity and upgrade their architecture to keep up with data traffic increase, are turning their attention to denser deployments that improve spectral efficiency. Denser deployments make the problem of user association challenging, and much work has been devoted to finding algorithms that strike a tradeoff between user quality of service (QoS), and network-wide performance (load-balancing). Nevertheless, the majority of these algorithms typically consider only the radio access part, and ignore the backhaul topology and potential capacity limitations. Backhaul constraints are emerging as a key performance bottleneck in future heterogeneous networks, partly due to the continuous improvement of the radio interface, and partly due to the need for inexpensive backhaul links to reduce CAPEX/OPEX. To this end, we propose an analytical framework for user association that jointly considers radio access and backhaul performance. We derive an algorithm that takes into account spectral efficiency, base station load, backhaul link capacities and topology, and uplink and downlink traffic demand, and prove it converges to an optimal solution. We then use extensive simulations to study the impact of (i) backhaul capacity limitations and (ii) backhaul topology on key performance metrics.

Activity recognition has applications in a variety of human-in-the-loop settings such as smart home health monitoring, green building energy and occupancy management, intelligent transportation, and participatory sensing. While fine-grained activity recognition systems and approaches help enable a multitude of novel applications, discovering them with non-intrusive ambient sensor systems pose challenging design, as well as data processing, mining, and activity recognition issues. In this paper, we develop a low-cost heterogeneous Radar based Activity Monitoring (RAM) system for recognizing fine-grained activities. We exploit the feasibility of using an array of heterogeneous micro-doppler radars to recognize low-level activities. We prototype a short-range and a long-range radar system and evaluate the feasibility of using the system for fine-grained activity recognition. In our evaluation, using real data traces, we show that our system can detect fine-grained user activities with 92.84% accuracy.

In Search Engine Marketing (SEM), “third-party” partners play an important intermediate role by bridging the gap between search engines and advertisers in order to optimise advertisers' campaigns in exchange of a service fee. In this paper, we present an economic analysis of the market involving a third-party broker in Google AdWords and the broker's customers. We show that in order to optimise his profit, a third-party broker should minimise the weighted average Cost Per Click (CPC) of the portfolio of keywords attached to customer's ads while still satisfying the negotiated customer's demand. To help the broker build and manage such portfolio of keywords, we develop an optimisation framework inspired from the classical Markowitz portfolio management which integrates the customer's demand constraint and enables the broker to manage the tradeoff between return on investment and risk through a single risk aversion parameter. We then propose a method to augment the keywords portfolio with relevant keywords extracted from trending and popular topics on Twitter. Our evaluation shows that such a keywords-augmented strategy is very promising and enables the broker to achieve, on average, four folds larger return on investment than with a non-augmented strategy, while still maintaining the same level of risk.

Device-free localization (DfL) techniques, which can localize targets without carrying any wireless devices, have attracting an increasing attentions. Most current DfL approaches, however, have two main drawbacks hindering their practical applications. First, one needs to collect large number of measurements to achieve a high localization accuracy, inevitably causing a high deployment cost, and the areas variety will further exacerbate this problem. Second, as the pre-obtained Received Signal Strength (RSS) from each location (i.e., radio-map) in a specific area cannot be directly applied to new areas for localization, the calibration process of different areas will lead to the high human effort cost. In this paper, we propose, FitLoc, a fine-grained and low cost DfL approach that can localize multiple targets in various areas. By taking advantage of the compressive sensing (CS) theory, FitLoc decreases the deployment cost by collecting only a few of RSS measurements and performs a fine-grained localization. Further, FitLoc employs a rigorously designed transfer scheme to unify the radio-map over various areas, thus greatly reduces the human effort cost. Theoretical analysis about the effectivity of the problem formulation is provided. Extensive experimental results illustrate the effectiveness of FitLoc.

Caching in wireless ad hoc networks can reduce network traffic and content access delay, as nodes can retrieve contents from near neighbors rather than the faraway server. However, the fundamental performance limits of caching in wireless ad hoc networks have rarely been studied in an analytical manner. In this paper, we study the fundamental property of wireless networks with caching, i.e., the scaling laws of the network capacity based on cache size of individual node, the total size of unique content and the number of nodes in the network. We present an upper bound on network capacity, and present an achievable capacity lower bound, where we propose a caching scheme to show what capacity can actually be achievable. Our results suggest that the capacity of wireless ad hoc networks with caching can remain constant even as the number of nodes in the network increases. We also present numerical results and demonstrate that our results are consistent with existing analytical results under extreme conditions where the node communication scenario matches theirs.

Although Software-Defined Networking (SDN) enables flexible network resource allocations for traffic engineering, current literature mostly focuses on unicast communications. Compared to traffic engineering for multiple unicast flows, multicast traffic engineering for multiple trees is very challenging not only because minimizing the bandwidth consumption of a single multicast tree by solving the Steiner tree problem is already NP-Hard, but the Steiner tree problem does not consider the link capacity constraint for multicast flows and node capacity constraint to store the forwarding entries in Group Table of OpenFlow. In this paper, therefore, we first study the hardness results of scalable multicast traffic engineering in SDN. We prove that scalable multicast traffic engineering with only the node capacity constraint is NP-Hard and not approximable within δ, which is the number of destinations in the largest multicast group. We then prove that scalable multicast traffic engineering with both the node and link capacity constraints is NP-Hard and not approximable within any ratio. To solve the problem, we design a δ-approximation algorithm, named Multi-Tree Routing and State Assignment Algorithm (MTRSA), for the first case and extend it to the general multicast traffic engineering problem. The simulation and implementation results demonstrate that the solutions obtained by the proposed algorithm outperform the shortest-path trees and Steiner trees. Most importantly, MTRSA is computation-efficient and can be deployed in SDN since it can generate the solution with numerous trees in a short time.

This paper studies information source detection in networks under the independent cascade (IC) model. Assume the spread of information starts from a single source in a network and a complete snapshot of the network is obtained at some time. The goal is to identify the source based on the observation. We derive the maximum a posterior (MAP) estimator of the source for tree networks and propose a Short-Fat Tree (SFT) algorithm for general networks based on the MAP estimator. The algorithm selects the Jordan infection center [1] and breaks ties according the degree of boundary infected nodes. Loosely speaking, the algorithm selects the node such that the breadth-first search (BFS) tree from it has the minimum depth but the maximum number of leaf nodes. On the Erdos-Renyi (ER) random graph, we establish the following possibility and impossibility results: (i) when the infection duration0.5, SFT identifies the source with probability 1 (w.p.1) asymptotically (as network size increases to infinity), where n is the network size and μ is the average node degree; (ii) when the infection duration > ⌈log n/ log μ ⌉ + 2, the probability of identifying the source approaches zero asymptotically under any algorithm; and (iii) when infection duration0, asymptotically, at least 1-δ fraction of the nodes on the BFS tree starting from the source are leaf-nodes, where δ = 3√log n/μ, i.e., the BFS tree starting from the actual source is a fat tree. 1Numerical experiments on tree networks, the ER random graphs and real world networks with different evaluation metrics show that the SFT algorithm outperforms existing algorithms.

We investigate the scheduling problem in a centralized dual-hop 60 GHz network with multiple Source-Destination (SD) pairs, relays, and a PicoNet Coordinator (PNC). The objective is to minimize the Maximum Expected Delivery Time (MEDT) among all SD pairs by jointly optimizing relay and link selection, while exploiting reflected mmWave transmissions and considering link blockage dynamics. We develop a Decomposition Principle to transform this problem into two sub-problems, one for link selection and the other for relay assignment when there is enough replays. We prove that the proposed scheme can achieve an optimality gap of just 1 time slot at greatly reduced complexity. We also develop a heuristic scheme to handle the case when there is no enough relays. The proposed schemes are validated with simulations, where their superior performance is observed.

In many applications including interactive services and big data analytics, a timely result with a good match is often more valuable than a perfect yet delayed result. This fact can be utilized to improve the total utility gain of a cloud computing platform by allowing partial execution of jobs. A fundamental challenge, however, is that in many real environments, scheduling decisions have to be made online without knowledge about future jobs, which makes it difficult to choose between more valuable jobs with large deadlines and less valuable jobs that are more emergent. Moreover, jobs are often heterogeneous in their utilities, deadlines, and demands for different types of resources. In this paper, we study the problem of online scheduling for deadline-sensitive jobs with concave utility functions that can deliver partial results. We develop efficient online multi-resource allocation algorithms that achieve low competitive ratios for both continuous and discrete job models.

Powered by the emergence of the Internet of Things, smart homes containing a variety of sensors and actuators are expected to monitor and react to the activities of the residents with the goal of improving convenience, comfort and safety. However, in typical home settings, each human Activity of Daily Living (ADL) generates events from multiple sensors, and each sensor is triggered by multiple ADLs. Consequently, achieving high detection accuracy in these complex environments requires large amounts of training data for every possible multiplexing scenario, making it a complex problem. In this paper, we propose a data driven three-step de-multiplexing approach that simplifies the ADL recognition problem by first segmenting the event stream into periods of interest, before feeding to a classifier. We mine datasets to identify salient features which allow us to achieve a good segmentation. Extensive evaluation on ten public datasets shows that our approach achieves upto 77% segmentation accuracy, and a activity detection accuracy within 91% of the best possible.

Mobile online social networks (OSNs) are emerging as the popular mainstream platform for information and content sharing among people. In order to provide Quality of Experience (QoE) support for mobile OSN services, in this paper we propose a socially-driven learning-based framework, namely Spice, for media content prefetching to reduce the access delay and enhance mobile user's satisfaction. Through a large-scale data-driven analysis over real-life mobile Twitter traces from over 17,000 users during a period of five months, we reveal that the social friendship has a great impact on user's media content click behavior. To capture this effect, we conduct social friendship clustering over the set of user's friends, and then develop a cluster-based Latent Bias Model for socially-driven learning-based prefetching prediction. We then propose a usage-adaptive prefetching scheduling scheme by taking into account that different users may possess heterogeneous patterns in the mobile OSN app usage. We comprehensively evaluate the performance of Spice framework using trace-driven emulations on smartphones. Evaluation results corroborate that the Spice can achieve superior performance, with an average 67.2% access delay reduction at the low cost of cellular data and energy consumption. Furthermore, by enabling users to offload their machine learning procedures to a cloud server, our design can achieve speed-up of a factor of 1000 over the local data training execution on smartphones.