INFOCOM 2017 论文列表

The growing demands of processing massive datasets have promoted irresistible trends of running machine learning applications on MapReduce. When processing large input data, it is often of greater values to produce fast and accurate enough approximate results than slow exact results. Existing techniques produce approximate results by processing parts of the input data, thus incurring large accuracy losses when using short job execution times, because all the skipped input data potentially contributes to result accuracy. We address this limitation by proposing AccurateML that aggregates information of input data in each map task to create small aggregated data points. These aggregated points enable all map tasks producing initial outputs quickly to save computation times and decrease the outputs' size to reduce communication times. Our approach further identifies the parts of input data most related to result accuracy, thus first using these parts to improve the produced outputs to minimize accuracy losses. We evaluated AccurateML using real machine learning applications and datasets. The results show: (i) it reduces execution times by 30 times with small accuracy losses compared to exact results; (ii) when using the same execution times, it achieves 2.71 times reductions in accuracy losses compared to existing approximate processing techniques.

We consider a general multi-user mobile cloud computing system with a computing access point (CAP), where each mobile user has multiple independent tasks that may be processed locally, at the CAP, or at a remote cloud server. The CAP serves both as the network access gateway and a computation service provider to the mobile users. We aim to jointly optimize the offloading decisions of all users' tasks as well as the allocation of computation and communication resources, to minimize the overall cost of energy, computation, and delay for all users. This problem is NP-hard in general. We propose an efficient three-step algorithm comprising of semidefinite relaxation (SDR), alternating optimization (AO), and sequential tuning (ST). It is shown to always compute a locally optimal solution, and give nearly optimal performance under a wide range of parameter settings. Through evaluating the performance of different combinations of the three components of this SDR-AO-ST algorithm, we provide insights into their roles and contributions in the overall solution. We further compare the performance of SDR-AO-ST against a lower bound to the minimum cost, purely local processing, purely cloud processing, and hybrid local-cloud processing without using the CAP. Our numerical results demonstrate the effectiveness of the proposed algorithm in the joint management of computation and communication resources in mobile cloud computing systems with a CAP.

Adaptive bitrate streaming (ABR) has become the de facto technique for video streaming over the Internet. Despite a flurry of techniques, achieving high quality ABR streaming over cellular networks remains a tremendous challenge. ABR streaming can be naturally modeled as a feedback control problem. There has been some initial work on using PID, a widely used feedback control technique, for ABR streaming. Existing studies, however, either use PID control directly without fully considering the special requirements of ABR streaming, leading to suboptimal results, or conclude that PID is not a suitable approach. In this paper, we take a fresh look at PID-based control for ABR streaming. We design a framework called PIA that strategically leverages PID control concepts and incorporates several novel strategies to account for the various requirements of ABR streaming. We evaluate PIA using simulation based on real LTE network traces, as well as using real DASH implementation. The results demonstrate that PIA outperforms state-of-the-art schemes in providing high average bitrate with significantly lower bitrate changes (reduction up to 40%) and stalls (reduction up to 85%), while incurring very small runtime overhead.

After a massive scale failure, the assessment of damages to communication networks requires local interventions and remote monitoring. While previous works on network recovery require complete knowledge of damage extent, we address the problem of damage assessment and critical service restoration in a joint manner. We propose a polynomial algorithm called Centrality based Damage Assessment and Recovery (CeDAR) which performs a joint activity of failure monitoring and restoration of network components. CeDAR works under limited availability of recovery resources and optimizes service recovery over time. We modified two existing approaches to the problem of network recovery to make them also able to exploit incremental knowledge of the failure extent. Through simulations we show that CeDAR outperforms the previous approaches in terms of recovery resource utilization and accumulative flow over time of the critical services.

As a virtual backbone structure, connected dominating sets (CDSs) play an important role in topology control for wireless networks. In this paper, we develop a distributed self-stabilizing CDS construction algorithm under the SINR model (also known as the physical interference model), a more practical yet more challenging interference model for distributed algorithm design. Specifically, we propose a randomized distributed algorithm that can construct a CDS in O (log n) timeslots with a high probability, where n is the total number of nodes in the network. The constructed CDS achieves constant approximation in both density and diameter. To the best of our knowledge, this is the first known asymptotically optimal self-stabilizing result in terms of both density and diameter for distributed CDS construction under the practical SINR model.

Boolean network tomography is a powerful tool to infer the state (working/failed) of individual nodes from path-level measurements obtained by egde-nodes. We consider the problem of optimizing the capability of identifying network failures through the design of monitoring schemes. Finding an optimal solution is NP-hard and a large body of work has been devoted to heuristic approaches providing lower bounds. Unlike previous works, we provide upper bounds on the maximum number of identifiable nodes, given the number of monitoring paths and different constraints on the network topology, the routing scheme, and the maximum path length. The proposed upper bounds represent a fundamental limit on the identifiability of failures via Boolean network tomography. This analysis provides insights on how to design topologies and related monitoring schemes to achieve the maximum identifiability under various network settings. Through analysis and experiments we demonstrate the tightness of the bounds and efficacy of the design insights for engineered as well as real networks.

Balancing the load in content addressing schemes for route-restricted networks represents a challenge with a wide range of applications. Solutions based on greedy embeddings maintain minimal state information and enable efficient routing, but any such solutions currently result in either imbalanced content addressing, overloading individual nodes, or are unable to efficiently account for network dynamics. In this work, we propose a greedy embedding in combination with a content addressing scheme that provides balanced content addressing while at the same time enabling efficient stabilization in the presence of network dynamics. We point out the tradeoff between stabilization complexity and maximal permitted imbalance when deriving upper bounds on both metrics for two variants of the proposed algorithms. Furthermore, we substantiate these bounds through a simulation study based on both real-world and synthetic data.

To reduce the energy consumption of a smartphone, multiple data transfer requests from applications can be bundled together and granted at once in order to reduce the time the radio interface is on. The side effect of bundling is the increased delay experienced by mobile applications. While several bundling algorithms have been proposed in the literature, a general and systematic solution to balance the energy-delay tradeoff is missing. In this paper, we formulate bundling as a cost minimization problem, in which the tradeoff between energy and delay is captured by a cost function. We then propose an online algorithm for minimizing the bundling cost and show that the algorithm is 4-competitive with respect to the optimal offline algorithm that knows the entire sequence of data transfer requests a priori. We evaluate the performance of the proposed algorithm and the accuracy of our results in a range of realistic scenarios using both model-driven simulations and real experiments on a smartphone. Our results show that depending on the delay tolerance level of a user, energy savings ranging from zero (delay intolerant) to about 100% (delay tolerant) can be achieved using our algorithm.

Increasing dynamics of electrical loads presents uncertainty and hence new challenges for power grid controls and optimization. In economic dispatch control (EDC) for minimizing generation cost, demand reporting by customers is a promising approach for managing the uncertainty, but it raises important privacy concerns. Adding random noise to aggregate queries of demand reports can provide differential privacy (DP) for the individual customers. But the noisy query results can adversely impact the EDC's optimality. In this paper, we analyze the privacy cost in demand reporting in terms of how DP-induced noise will increase the total generation cost. Our analysis shows that the noise amounts for different customers are intricately coupled with one another in determining the total cost. In view of the coupling, we apply the principle of Shapley value to attribute fair shares of the total cost to the power grid buses. For efficient sharing of the privacy cost, in a manner scalable to large power systems with many buses, we additionally propose heuristic algorithms to approximate the Shapley value. Trace-driven simulations based on a 5-bus power system model validate our analysis and illustrate the performance of the proposed cost sharing algorithms.

Implants are poised to revolutionize personalized healthcare by monitoring and actuating physiological functions. Such implants operate under challenging constraints of limited battery energy, heterogeneous tissue-dependent channel conditions and human-safety regulations. To address these issues, we propose a new cross-layer protocol for galvanic coupled implants wherein weak electrical currents are used in place of classical radio frequency (RF) links. As the first step, we devise a method that allows multiple implants to communicate individual sensed data to each other through CDMA code assignments, but delegates the computational burden of decoding only to the on-body surface relays. Then, we devise a distributed beamforming approach that allows coordinated transmissions from the implants to the relays by considering the specific tissue path chosen and tissue heating-related safety constraints. Our contributions are two fold: First, we devise a collision-free protocol that prevents undue interference at neighboring implants, especially for multiple deployments. Second, this is the first application of near-field distributed beamforming in human tissue. Results reveal significant improvement in the network lifetime for implants of up to 79% compared to the galvanic coupled links without beamforming.

Motivated by the great potential of implicit and seamless user authentication, we attempt to build an efficient middle layer running on mobile devices to support implicit authentication (IA) systems with adaptive sampling. Various activities, such as user location, application usage, user motion, and battery usage have been popular choices to generate behaviors, the soft biometrics, for implicit authentication. Unlike password-based or hard biometric-based authentication, implicit authentication does not require explicit user action or expensive hardware. However, user behaviors can change unpredictably which renders it more challenging to develop systems that depend on them. Various machine learning algorithms have been used to address this challenge. The expensive training process is usually outsourced to the remote server but this can potentially increase the chance of data leakage. In addition, mobile devices may not always have reliable network connections to send real-time data to the server for training. Motivated by these limitations, we propose a W-layer, an overlay that provides an energy-efficient solution for real-time implicit authentication on mobile devices. The size of the data the system needs to collect at different times depends on the legitimacy of the user. This in turn affects how the sampling rate is adjusted which can reduce energy consumption. To evaluate our method, we conducted several experiments on both synthetic and real datasets. The average accuracy of identifying legitimate users is 96.73% using the synthetic dataset and 96.70% using the real dataset. Furthermore, we tested the power consumption on a low-end Nexus S smartphone to obtain a more pessimistic result. We found that our method consumed 14.5% of the device's total battery usage. The power consumption performance is expected to improve significantly on high-end mobile devices.

Local business service systems (LBSS), such as Yelp and Dianping, play an essential role in making decisions like choosing a restaurant for our daily life. These systems heavily rely on individuals' voluntarily submitted reviews to build the reputation for nearby businesses. Unfortunately, the reviews expose users' private information such as visited places to the public and adversaries. Even worse, such location information is always public as it is the basic information of businesses, and adversaries could be anyone ranging from advertisement spammer to physical stalker. This paper formalizes the privacy preserving problem in local business service systems and propose a novel location privacy preserving framework. The framework can preserve users' location privacy in arbitrary local area and can maintain a good utility for both the system and every user. We evaluate our framework thoroughly towards real-world data traces. The results validate that the framework can achieve a good performance.

Optical switches have been drawing attention due to their large data bandwidth and low power consumption. However, scheduling policies need to account for the schedule reconfiguration delay of optical switches to achieve good performance. The Adaptive MaxWeight policy achieves optimal throughput for switches with nonzero reconfiguration delay, and has been shown in simulation to have good delay performance. In this paper, we analyze the queue length behavior of a switch with nonzero reconfiguration delay operating under the Adaptive MaxWeight. We first show that the Adaptive MaxWeight policy exhibits a weak state space collapse behavior in steady-state, which could be viewed as an inheritance of the MaxWeight policy in a switch with zero reconfiguration delay. We then use the weak state space collapse result to obtain a steady state delay bound under the Adaptive MaxWeight algorithm in heavy traffic by applying a recently developed drift technique. The resulting delay bound is dependent on the expected schedule duration. We then derive the relation between the expected schedule duration and the steady state queue length through drift analysis, and obtain asymptotically tight queue length bounds in the heavy traffic regime.

In a software defined network (SDN), the control plane needs to frequently collect flow statistics measured at the data plane switches for different applications, such as traffic engineering, flow re-routing, and attack detection. However, existing solutions for flow statistics collection may result in large bandwidth cost in the control channel and long processing delay on switches, which significantly interfere with the basic functions such as packet forwarding and route update. To address this challenge, we propose a Cost-Optimized Flow Statistics Collection (CO-FSC) scheme using wildcard-based requests. We prove that the CO-FSC problem is NP-Hard and present a rounding-based algorithm with an approximation factor f, where f is the maximum number of switches visited by each flow. Moreover, our CO-FSC problem is extended to the general case, in which only a part of flows in a network need to be collected. The extensive simulation results show that the proposed algorithms can reduce the bandwidth overhead by over 41% and switch processing delay by over 45% compared with the existing solutions.

The need of customized network functions for enterprises in Infrastructure-as-a-Service (IaaS) clouds is emerging. However, existing network functions in IaaS clouds are very limited, inflexible, and hard to control by the tenants. Recently, the introduction of Software-Defined Networking (SDN) technology brings the hope of flexible control of network flows and creation of diverse network functions. Unfortunately, enterprises lose access to the SDN controller when they move to clouds. Moreover, the cloud SDN controller is only managed by the provider administrators for security and performance reasons. To allow enterprise tenants to develop and deploy their own SDN apps in the cloud, in this paper, we introduce a new cloud usage paradigm: Bring Your Own Controller (BYOC). BYOC offers each tenant an individual SDN controller, where tenants can deploy SDN apps to manage their network. To manage these tenant SDN controllers, we propose BYOC-Visor, a new SDN-based virtualization platform. BYOC-VISOR addresses several security and performance challenges which are specific to IaaS clouds. We show that BYOC-Visor supports different controller platforms and diverse SDN security applications such as firewall, IDS, and access control. We implement a prototype system and the performance evaluation results show that our system has low overhead.

Web browsing is an activity that billions of mobile users perform on a daily basis. Battery life is a primary concern to many mobile users who often find their phone has died at most inconvenient times. The heterogeneous multi-core architecture is a solution for energy-efficient processing. However, the current mobile web browsers rely on the operating system to exploit the underlying hardware, which has no knowledge of individual web contents and often leads to poor energy efficiency. This paper describes an automatic approach to render mobile web workloads for performance and energy efficiency. It achieves this by developing a machine learning based approach to predict which processor to use to run the web rendering engine and at what frequencies the processors should operate. Our predictor learns offline from a set of training web workloads. The built predictor is then integrated into the browser to predict the optimal processor configuration at runtime, taking into account the web workload characteristics and the optimisation goal: whether it is load time, energy consumption or a trade-off between them. We evaluate our approach on a representative ARM big.LITTLE mobile architecture using the hottest 500 webpages. Our approach achieves 80% of the performance delivered by an ideal predictor. We obtain, on average, 45%, 63.5% and 81% improvement respectively for load time, energy consumption and the energy delay product, when compared to the Linux heterogeneous multi-processing scheduler.

This paper develops an algorithm that exploits picture-oriented social networks to localize urban events. We choose picture-oriented networks because taking a picture requires physical proximity, thereby revealing the location of the photographed event. Furthermore, most modern cell phones are equipped with GPS, making picture location, and time metadata commonly available. We consider Instagram as the social network of choice and limit ourselves to urban events (noting that the majority of the world population lives in cities). The paper introduces a new adaptive localization algorithm that does not require the user to specify manually tunable parameters. We evaluate the performance of our algorithm for various real-world datasets, comparing it against a few baseline methods. The results show that our method achieves the best recall, the fewest false positives, and the lowest average error in localizing urban events.

Low robustness under mobility is the Achilles' heel of the emerging 60 GHz networking technology. Instead of using omni-directional antennas as in existing Wi-Fi/cellular networks, 60 GHz radios communicate via highly-directional links formed by phased-array beam-forming, so as to upgrade wireless link throughput to multi-Gbps. However, user motion causes misalignment between the Tx's and Rx's beam directions, and often leads to link outage. Legacy 60 GHz protocols realign the beams by scanning alternative Tx/Rx beams. But unfortunately this tedious process can easily overwhelm the useful channel time, leaving the Tx/Rx in misalignment most of the time during mobility. In this paper, we propose Beam-forecast, a novel model-driven beam steering approach that can sustain high performance for mobile 60 GHz links. Beam-forecast is built on the observation that 60 GHz channel profiles at nearby locations are highly-correlated. By exploiting this correlation, Beam-forecast can reconstruct the channel profile as the Tx/Rx moves, without explicit channel scanning. In this way, it can predict new optimal beams and realign links for mobile users with minimal overhead. We evaluate Beam-forecast using a reconfigurable 60 GHz testbed along with a trace-driven simulator. Our experiments demonstrate multi-fold throughput gain compared with state-of-the-art under various practical scenarios.

Mobile Crowdsourced Access (MCA) enables mobile users (MUs) to share their Internet connections by serving as tethers to other MUs, hence can improve the quality of service of MUs as well as the overall utilization of network resources. However, MCA can also reduce the revenue-generating mobile traffic and increase the network congestion for mobile network operators (MNOs), and thus has been blocked by some MNOs in practice. In this work, we reconcile the conflicting objectives of MNOs and MUs by introducing a pricing framework for MCA, where the direct traffic and tethering traffic are charged independently according to a data price and a tethering price, respectively. We derive the optimal data and tethering prices systematically for MUs with the α-fair utility in two scenarios with cooperative and competitive MNOs, respectively. We show that the optimal tethering prices are zero and the optimal usage-based data prices are identical for all MUs, in both the cooperative and competitive scenarios. Such optimal pricing schemes will lead to mutually beneficial results for MNOs and MUs. Our simulation results show that the proposed pricing scheme approximately triples both the MNOs' profit and the MUs' payoff when the MNOs cooperate, comparing to the case where MCA is blocked. Moreover, competition among MNOs will decrease MNOs' profit and further increase the MUs' payoff.