INFOCOM 2020 论文列表

Network Function Virtualization (NFV) is a new paradigm to enable service innovation through virtualizing traditional network functions. To construct a new NFV-enabled network, there are two critical requirements: minimizing server deployment cost and satisfying switch resource constraints. However, prior work mostly focuses on the server deployment cost, while ignoring the switch resource constraints (e.g., switch's flow-table size). It thus results in a large number of rules on switches and leads to massive control overhead. To address this challenge, we propose an incremental server deployment (INSD) problem for construction of scalable NFV-enabled networks. We prove that the INSD problem is NP-Hard, and there is no polynomial-time algorithm with approximation ratio of (1- ε) ·ln m, where ε is an arbitrarily small value and m is the number of requests in the network. We then present an efficient algorithm with an approximation ratio of 2 · H(q · p)1, where q is the number of VNF's categories and p is the maximum number of requests through a switch. We evaluate the performance of our algorithm with experiments on physical platform (Pica8), Open vSwitches, and large-scale simulations. Both experiment and simulation results show high scalability of the proposed algorithm. For example, our solution can reduce the control and rule overhead by about 88% with about 5% additional server deployment, compared with the existing solutions.

In network function computation is as a means to reduce the required communication flow in terms of number of bits transmitted per source symbol. However, the rate region for the function computation problem in general topologies is an open problem, and has only been considered under certain restrictive assumptions (e.g. tree networks, linear functions, etc.). In this paper, we propose a new perspective for distributing computation, and formulate a flow-based delay cost minimization problem that jointly captures the costs of communications and computation. We introduce the notion of entropic surjectivity as a measure to determine how sparse the function is and to understand the limits of computation. Exploiting Little's law for stationary systems, we provide a connection between this new notion and the computation processing factor that reflects the proportion of flow that requires communications. This connection gives us an understanding of how much a node (in isolation) should compute to communicate the desired function within the network without putting any assumptions on the topology. Our analysis characterizes the functions only via their entropic surjectivity, and provides insight into how to distribute computation. We numerically test our technique for search, MapReduce, and classification tasks, and infer for each task how sensitive the processing factor to the entropic surjectivity is.

With the proliferation of Dynamic Spectrum Access (DSA), Internet of Things (IoT), and Mobile Edge Computing (MEC) technologies, various methods have been proposed to deduce key network and user information in cellular systems, such as available cell bandwidths, as well as user locations and mobility. Not only is such information dominated by cellular networks of vital significance on other systems co-located spectrum-wise and/or geographically, but applications within cellular systems can also benefit remarkably from inferring such information, as exemplified by the endeavours made by video streaming to predict cell bandwidth. Hence, we are motivated to develop a new tool to uncover as much information used to be closed to outsiders or user devices as possible with off-the-shelf products. Given the wide-spread deployment of LTE and its continuous evolution to 5G, we design and implement U-CIMAN, a client-side system to accurately UnCover as much Information in Mobile Access Networks as allowed by LTE encryption. Among the many potential applications of U-CIMAN, we highlight one use case of accurately measuring the spectrum tenancy of a commercial LTE cell. Besides measuring spectrum tenancy in unit of resource blocks, U-CIMAN discovers user mobility and traffic types associated with spectrum usage through decoded control messages and user data bytes. We conduct 4-month detailed accurate spectrum measurement on a commercial LTE cell, and the observations include the predictive power of Modulation and Coding Scheme on spectrum tenancy, and channel off-time bounded under 10 seconds, to name a few.

Betweenness centrality is a graph parameter that has been successfully applied to network analysis. In the context of computer networks, it was considered for various objectives, ranging from routing to service placement. However, as observed by Maccari et al. [INFOCOM 2018], research on betweenness centrality for improving protocols was hampered by the lack of a usable, fully distributed algorithm for computing this parameter. We resolve this issue by designing an efficient algorithm for computing betweenness centrality, which can be implemented by minimal modifications to any distance-vector routing protocol based on Bellman-Ford. The convergence time of our implementation is shown to be proportional to the diameter of the network.

With the commoditization of private data, data trading in consideration of user privacy protection has become a fascinating research topic. The trading for private web browsing histories brings huge economic value to data consumers when leveraged by targeted advertising. In this paper, we study the trading of multiple correlated queries on private web browsing history data. We propose TERBE, which is a novel trading framework for correlaTed quEries based on pRivate web Browsing historiEs. TERBE first devises a modified matrix mechanism to perturb query answers. It then quantifies privacy loss under the relaxation of classical differential privacy and a newly devised mechanism with relaxed matrix sensitivity, and further compensates data owners for their diverse privacy losses in a satisfying manner. Through real-data based experiments, our analysis and evaluation results demonstrate that TERBE balances total error and privacy preferences well within acceptable running time, and also achieves all desired economic properties of budget balance, individual rationality, and truthfulness.

Interest in fine-grained indoor localization remains high and various approaches including those based on Radio Frequency (RF), ultrasound, acoustic, magnetic field and light have been proposed. However, while the achieved accuracy may be high, many of these approaches do not work well in environments with lots of obstructions. In this paper, we present MagB, a decimeter-level localization scheme that uses the magnetometer available on many IoT devices. MagB estimates the bearing of magnetic beacons by detecting changes in the magnetic field strength. Localization is then performed based on Angle-of-Arrival (AoA) information. We have built a prototype of MagB using low cost, off-the-shelf components. Our evaluation shows that MagB is able to achieve a median accuracy of about 13cm and can localize devices even when they are placed in steel filing cabinet or inside the casing of a running PC.

Real-time analytics on video data demands intensive computation resources and high energy consumption. Traditional cloud-based video analytics relies on large centralized clusters to ingest video streams. With edge computing, we can offload compute-intensive analysis tasks to the nearby server, thus mitigating long latency incurred by data transmission via wide area networks. When offloading frames from the front-end device to the edge server, the application configuration (frame sampling rate and frame resolution) will impact several metrics, such as energy consumption, analytics accuracy and user-perceived latency. In this paper, we study the configuration adaption and bandwidth allocation for multiple video streams, which are connected to the same edge node sharing an upload link. We propose an efficient online algorithm, called JCAB, which jointly optimizes configuration adaption and bandwidth allocation to address a number of key challenges in edge-based video analytics systems, including edge capacity limitation, unknown network variation, intrusive dynamics of video contents. Our algorithm is developed based on Lyapunov optimization and Markov approximation, works online without requiring future information, and achieves a provable performance bound. Simulation results show that JCAB can effectively balance the analytics accuracy and energy consumption while keeping low system latency.

Traditional one-time user authentication processes might cause friction and unfavorable user experience in many widely-used applications. This is a severe problem in particular for security-sensitive facilities if an adversary could obtain unauthorized privileges after a user's initial login. Recently, continuous user authentication (CA) has shown its great potential by enabling seamless user authentication with few active participation. We devise a low-cost system exploiting a user's pulsatile signals from the photoplethysmography (PPG) sensor in commercial wrist-worn wearables for CA. Compared to existing approaches, our system requires zero user effort and is applicable to practical scenarios with non-clinical PPG measurements having motion artifacts (MA). We explore the uniqueness of the human cardiac system and design an MA filtering method to mitigate the impacts of daily activities. Furthermore, we identify general fiducial features and develop an adaptive classifier using the gradient boosting tree (GBT) method. As a result, our system can authenticate users continuously based on their cardiac characteristics so little training effort is required. Experiments with our wrist-worn PPG sensing platform on 20 participants under practical scenarios demonstrate that our system can achieve a high CA accuracy of over 90% and a low false detection rate of 4% in detecting random attacks.

We consider a cache network in which intermediate nodes equipped with caches can serve content requests. We model this network as a universally stable queuing system, in which packets carrying identical responses are consolidated before being forwarded downstream. We refer to resulting queues as M/M/1c or counting queues, as consolidated packets carry a counter indicating the packet's multiplicity. Cache networks comprising such queues are hard to analyze; we propose two approximations: one via M/M/∞ queues, and one based on M/M/1c queues under the assumption of Poisson arrivals. We show that, in both cases, the problem of jointly determining (a) content placements and (b) service rates admits a poly-time, 1 1/e approximation algorithm. Numerical evaluations indicate-that both approximations yield good solutions in practice, significantly outperforming competitors.

With the development of 5G technology, mobile edge computing is emerging as an enabling technique to promote Quality of Service (QoS) of network services. In particular, the response latency of network services can be significantly reduced by deploying cloudlets at 5G base stations in mobile edge clouds. Network service providers that usually deploy their services in remote clouds now shift their services from the remote clouds to the network edge in the proximity of users. However, the permanent placement of their services into edge clouds may not be economic, since computing and bandwidth resources in edge clouds are limited and relatively expensive. A smart way is to cache the services that are frequently requested by mobile users in edge clouds. In this paper, we study the problem of service caching in mobile edge network under a mobile service market with multiple network service providers completing for both computation and bandwidth resources of the edge cloud. We propose an Integer Linear Program (ILP) and a randomized rounding algorithm, for the problem without resource sharing among the network service providers. We also devise a distributed and stable game-theoretical mechanism for the problem with resource sharing among the network service providers, with the objective to minimize the social cost of all network service providers, by introducing a novel cost sharing model and a coalition formation game. We analyze the performance of the mechanism by showing a good guaranteed gap between the solution obtained and the optimal one, i.e., Strong Price of Anarchy (SPoA). We finally evaluate the performance of our algorithms by extensive simulations, and the obtained results show that the social cost of all players can be reduced significantly via allowing cooperation among network service providers in service caching.

High-accuracy localization technology has gained increasing attention in gesture and motion control and many diverse applications. Due to the shadowing, multi-path fading, blockage effects in indoor propagation, 0.1m-level precise localization is still challenging. Promising for 6G wireless communications, the Terahertz (THz) spectrum provides ultra-broad bandwidth for indoor applications. Applying to indoor localization, the channel state information (CSI) of THz wireless signals, including angle of arrival (AoA), received power, and delay, has unprecedented resolution that can be explored for positioning. In this paper, a Structured Bidirectional Long Short-term Memory (SBi-LSTM) recurrent neural network (RNN) architecture is proposed to solve the CSI-based three-dimensional (3D) THz indoor localization problem with significantly improved accuracy. As a two-level structure, the features of individual multi-path ray are first analyzed in the Bi-LSTM network at the base level. Furthermore, the upper level residual network (ResNet) of the constructed SBi-LSTM network extracts for the geometric coordinates. Simulation results validate the convergence of our SBi-LSTM method and the robustness against indoor non-line-of-sight (NLoS) blockage. Specifically, the localization accuracy in the metric of mean distance error is within 0.27m under the NLoS environment, which demonstrates 60% enhancement over the state-of-the-art techniques.

In this paper, we address the problem of stochastic optimization over distributed processing networks, which is motivated by machine learning applications performed in data centers. In this problem, each of a total n nodes in a network receives stochastic realizations of a private function fi(x) and aims to reach a common value that minimizes Σi=1nfi(x) via local updates and communication with its neighbors. We focus on zeroth-order methods where only function values of stochastic realizations can be used. Such kind of methods, which are also called derivative-free, are especially important in solving realworld problems where either the (sub)gradients of loss functions are inaccessible or inefficient to be evaluated. To this end, we propose a method called Distributed Stochastic Alternating Direction Method of Multipliers (DS-ADMM) which can choose to use two kinds of gradient estimators for different assumptions. The convergence rates of DS-ADMM are O(n√k log (2k)/T) for general convex loss functions and O(n k log (2kT)/T) for strongly convex functions in terms of optimality gap, where k is the dimension of domain and T is the time horizon of the algorithm. The rates can be improved to O(n/√T )and O(n log T/T) if objective functions have Lipschitz gradients. All these results are better than previous distributed zerothorder methods. Lastly, we demonstrate the performance of DSADMM via experiments of two examples called distributed online least square and distributed support vector machine arising in estimation and classification tasks.

Many mobile applications have been developed to apply deep learning for video analytics. Although these advanced deep learning models can provide us with better results, they also suffer from the high computational overhead which means longer delay and more energy consumption when running on mobile devices. To address this issue, we propose a framework called FastVA, which supports deep learning video analytics through edge processing and Neural Processing Unit (NPU) in mobile. The major challenge is to determine when to offload the computation and when to use NPU. Based on the processing time and accuracy requirement of the mobile application, we study two problems: Max-Accuracy where the goal is to maximize the accuracy under some time constraints, and Max-Utility where the goal is to maximize the utility which is a weighted function of processing time and accuracy. We formulate them as integer programming problems and propose heuristics based solutions. We have implemented FastVA on smartphones and demonstrated its effectiveness through extensive evaluations.

Low Power Wide Area Networks (LPWAN) are an emerging well-adopted platform to connect the Internet-of-Things. With the growing demands for LPWAN in IoT, the number of supported end-devices cannot meet the IoT deployment requirements. The core problem is the transmission collisions when large-scale end-devices transmit concurrently. The previous research mainly includes transmission scheduling strategies, collision detection and avoidance mechanism. The use of these existing approaches to address the above limitations in LPWAN may introduce excessive communication overhead, end-devices cost, power consumption, or hardware complexity. In this paper, we present S-MAC, an adaptive MAC-layer scheduler for LPWAN. The key innovation of S-MAC is to take advantage of the periodic transmission characteristics of LPWAN applications and also the collision behaviour features of LoRa PHY-layer to enhance the scalability. Technically, S-MAC is capable of adaptively perceiving clock drift of end-devices, adaptively identifying the join and exit of end-devices, and adaptively performing the scheduling strategy dynamically. Meanwhile, it is compatible with native LoRaWAN, and adaptable to existing Class A, B and C devices. Extensive implementations and evaluations on commodity devices show that S-MAC increases the number of connected end-devices by 4.06× and improves network throughput by 4.01× with PRR requirement of > 95%.

The real-time query of massive surveillance video data plays a fundamental role in various smart urban applications such as public safety and intelligent transportation. Traditional cloud-based approaches are not applicable because of high transmission latency and prohibitive bandwidth cost, while edge devices are often incapable of executing complex vision algorithms with low latency and high accuracy due to restricted resources. Given the infeasibility of both cloud-only and edge-only solutions, we present SurveilEdge, a collaborative cloud-edge system for real-time queries of large-scale surveillance video streams. Specifically, we design a convolutional neural network (CNN) training scheme to reduce the training time with high accuracy, and an intelligent task allocator to balance the load among different computing nodes and to achieve the latency-accuracy tradeoff for real-time queries. We implement SurveilEdge on a prototype1with multiple edge devices and a public Cloud, and conduct extensive experiments using real-world surveillance video datasets. Evaluation results demonstrate that SurveilEdge manages to achieve up to 7× less bandwidth cost and 5.4× faster query response time than the cloud-only solution; and can improve query accuracy by up to 43.9% and achieve 15.8× speedup respectively, in comparison with edge-only approaches.

Deep learning shows great promise in providing more intelligence to the mobile web, but insufficient infrastructure, heavy models, and intensive computation limit the use of deep learning in mobile web applications. In this paper, we present DeepAdapter, a collaborative framework that ties the mobile web with an edge server and a remote cloud server to allow executing deep learning on the mobile web with lower processing latency, lower mobile energy, and higher system throughput. DeepAdapter provides a context-aware pruning algorithm that incorporates the latency, the network condition and the computing capability of the mobile device to fit the resource constraints of the mobile web better. It also provides a model cache update mechanism improving the model request hit rate for mobile web users. At runtime, it matches an appropriate model with the mobile web user and provides a collaborative mechanism to ensure accuracy. Our results show that DeepAdapter decreases average latency by 1.33x, reduces average mobile energy consumption by 1.4x, and improves system throughput by 2.1x with a considerable accuracy. Its contextaware pruning algorithm also improves inference accuracy by up to 0.3% with a smaller and faster model.

Remote Direct Memory Access (RDMA) suffers from unfairness issues and performance degradation when multiple applications share RDMA network resources. Hence, an efficient resource scheduling mechanism is urged to optimally allocates RDMA resources among applications. However, traditional Network Utility Maximization (NUM) based solutions are inadequate for RDMA due to three challenges: 1) The standard NUM-oriented algorithm cannot deal with coupling variables introduced by multiple dependent RDMA operations; 2) The stringent constraint of RDMA on-board resources complicates the standard NUM by bringing extra optimization dimensions; 3) Naively applying traditional algorithms for NUM suffers from scalability and convergence issues in solving a large-scale RDMA resource scheduling problem.

We address the problem of localizing an (illegal) transmitter using a distributed set of sensors. Our focus is on developing techniques that perform the transmitter localization in an efficient manner, wherein the efficiency is defined in terms of the number of sensors used to localize. Localization of illegal transmitters is an important problem which arises in many important applications, e.g., in patrolling of shared spectrum systems for any unauthorized users. Localization of transmitters is generally done based on observations from a deployed set of sensors with limited resources, thus it is imperative to design techniques that minimize the sensors' energy resources. In this paper, we design greedy approximation algorithms for the optimization problem of selecting a given number of sensors in order to maximize an appropriately defined objective function of localization accuracy. The obvious greedy algorithm delivers a constant-factor approximation only for the special case of two hypotheses (potential locations). For the general case of multiple hypotheses, we design a greedy algorithm based on an appropriate auxiliary objective function - and show that it delivers a provably approximate solution for the general case. We develop techniques to significantly reduce the time complexity of the designed algorithms, by incorporating certain observations and reasonable assumptions. We evaluate our techniques over multiple simulation platforms, including an indoor as well as an outdoor testbed, and demonstrate the effectiveness of our designed techniques - our techniques easily outperform prior and other approaches by up to 50-60% in large-scale simulations.

Federated learning is a very promising machine learning paradigm where a large number of clients cooperatively train a global model using their respective local data. In this paper, we consider the application of federated learning in wireless networks featuring uplink multiuser multiple-input and multiple-output (MU-MIMO), and aim at optimizing the communication efficiency during the aggregation of client-side updates by exploiting the inherent superposition of radio frequency (RF) signals. We propose a novel approach named Physical-Layer Arithmetic (PhyArith), where the clients encode their local updates into aligned digital sequences which are converted into RF signals for sending to the server simultaneously, and the server directly recovers the exact summation of these updates as required from the superimposed RF signal by employing a customized sum-product algorithm. PhyArith is compatible with commodity devices due to the use of full digital operation in both the client-side encoding and the server-side decoding processes, and can also be integrated with other updates compression based acceleration techniques. Simulation results show that PhyArith further improves the communication efficiency by 1.5 to 3 times for training LeNet-5, compared with solutions only applying updates compression.