INFOCOM 2020 Papers

The fast development of virtual network functions (VNFs) brings new opportunities to network service deployment on edge networks. For complicated services, VNFs can chain up to form service function chains (SFCs). Despite the promises, it is still not clear how to backup VNFs to minimize the cost while meeting the SFC availability requirements in an online manner. In this paper, we propose a novel self-adapting scheme named SAB to efficiently backup VNFs over both the edge and the cloud. Specifically, SAB uses both static backups and dynamic ones created on the fly to accommodate the resource limitation of edge networks. For each VNF backup, SAB determines whether to place it on the edge or the cloud, and if on the edge, which edge server to use for load balancing. SAB does not assume failure rates of VNFs but instead strives to find the sweet point between the desired availability of SFCs and the backup cost. Both theoretical performance bounds and extensive simulation results highlight that SAB provides significantly higher availability with lower backup cost compared with existing baselines.

Due to the massive size of the neural network models and training datasets used in machine learning today, it is imperative to distribute stochastic gradient descent (SGD) by splitting up tasks such as gradient evaluation across multiple worker nodes. However, running distributed SGD can be prohibitively expensive because it may require specialized computing resources such as GPUs for extended periods of time. We propose cost-effective strategies to exploit volatile cloud instances that are cheaper than standard instances, but may be interrupted by higher priority workloads. To the best of our knowledge, this work is the first to quantify how variations in the number of active worker nodes (as a result of preemption) affects SGD convergence and the time to train the model. By understanding these trade-offs between preemption probability of the instances, accuracy, and training time, we are able to derive practical strategies for configuring distributed SGD jobs on volatile instances such as Amazon EC2 spot instances and other preemptible cloud instances. Experimental results show that our strategies achieve good training performance at substantially lower cost.

For modern large-scale networked systems, ranging from cloud to edge computing systems, the topology design has a significant impact on the system performance in terms of scalability, cost, latency, throughput, and fault-tolerance. These performance metrics may conflict with each other and design criteria often vary across different networks. To date, there has been little theoretic foundation on topology designs from a prescriptive perspective, indicating that the current status quo of the design process is more of an art than a science. In this paper, we advocate a novel unified framework to describe, generate, and analyze topology design in a systematic fashion. By reverse-engineering existing topology designs and developing a fine-grained decomposition method for topology design, we propose a general procedure that serves as a common language to describe topology design. By proposing general criteria for the procedure, we devise a top-down approach to generate topology models, based on which we can systematically construct and analyze new topologies. To validate our approach, we leverage concrete tools based on combinatorial design theory and propose a novel layered topology model. With quantitative performance analysis, we reveal the trade-offs among performance metrics and generate new topologies with various advantages for different large-scale networks.

Long Range (LoRa) communication, thanks to its wide network coverage and low energy operation, has attracted extensive attentions from both academia and industry. However, existing LoRa-based Wide Area Network (LoRaWAN) suffers from severe inter-network interference, due to the following two reasons. First, the densely-deployed LoRa ends usually share the same network configurations, such as spreading factor (SF), bandwidth (BW) and carrier frequency (CF), causing interference when operating in the vicinity. Second, LoRa is tailored for low-power devices, which excludes LoRaWAN from using the listen-before-talk (LBT) mechanisms commonly used in wireless communication technologies, such as WiFi and ZigBee -LoRaWAN has to use the duty-cycled medium access policy and thus being incapable of channel sensing or collision avoidance. To mitigate the inter-network interference, we propose a novel solution achieving the online concurrent transmissions at LoRa gateway, called OCT, which recovers collided packets at the gateway and thus improves LoRaWAN's throughput. Moreover, OCT achieves the online concurrent transmission using only LoRa's (de)modulation information, thus can be easily deployed at LoRa gateway. We have implemented and evaluated OCT on USRP platform and commodity LoRa ends, showing OCT achieves: (i) >90% packet reception rate (PRR), (ii) 3 × 10-3bit error rate (BER), (iii) 2x and 3x throughput in the scenarios of two- and three- packet collisions respectively, and (iv) reducing 67% latency compared with state-of-the-art.

Sampling is a powerful tool to reduce the processing overhead in various systems. NetFlow uses a local table for counting records per flow, and sFlow sends out the collected packet headers periodically to a collecting server over the network. Any measurement system falls into either one of these two models. To reduce the overhead, as in sFlow, simple random sampling (SRS) has been widely used in practice because of its simplicity. However, SRS provides non-uniform sampling rates for different fine-grained flows (defined by 5-tuple), because it samples packets over an aggregated data flow (defined by switch port or VLAN). Consequently, some flows are sampled more than the designated sampling rate (resulting in over-estimation), and others are sampled fewer (resulting in under-estimation). Starting with a simple idea that "independent per-flow packet sampling provides the most accurate estimation of each flow", we introduce a new concept of per-flow systematic sampling, aiming to provide the same sampling rate across all flows. In addition, we provide a concrete sampling method called SketchFlow, which approximates the idea of the per-flow systematic sampling using a sketch saturation event. We demonstrate SketchFlow's performance in terms of accuracy, sampling rate, and overhead using real-world datasets, including a backbone network trace, I/O trace, and Twitter dataset. Experimental results show that SketchFlow outperforms SRS (i.e., sFlow) and the non-linear sampling method while requiring a small CPU overhead to measure high-speed traffic in real-time.

The rapid growth of computing capabilities at network edge calls for efficient management frameworks that not only considers placing hot data on edge storage for best accessibility and performance, but also makes optimal utilization of edge storage space. In this paper, we solve a joint optimization problem by exploiting both data popularity (for optimal data access performance) and data similarity (for optimal storage space efficiency). We show that the proposed optimization is NP- hard and develop a 2⌈2Γ⌉ - 1 + ϵ-approximation algorithm by (i) making novel use of δ-similarity graph to capture pairwise data similarity and (ii) leveraging the k-MST algorithm to solve a Prize Collecting Steiner Tree problem on the graph. The proposed algorithm is prototyped using an open-source distributed storage system, Cassandra. We evaluate its performance extensively on a real-world testbed and with respect to real-world IoT datasets. The algorithm is shown to achieve over 55% higher edge service rate and reduces request response time by about 30%.

Network alignment (NA) - i.e., linking entities from different networks (also known as identity linkage) - is a fundamental problem in many application domains. Recent advances in deep graph learning have inspired various auspicious approaches for tackling the NA problem. However, most of the existing works suffer from efficiency and generalization, due to complexities and redundant computations.We approach the NA from a different perspective, tackling it via meta-learning in a semi-supervised manner, and propose an effective and efficient approach called Meta-NA - a novel, conceptually simple, flexible, and general framework. Specifically, we reformulate NA as a one-shot classification problem and address it with a graph meta-learning framework. Meta-NA exploits the meta-metric learning from known anchor nodes to obtain latent priors for linking unknown anchor nodes. It contains multiple sub-networks corresponding to multiple graphs, learning a unified metric space, where one can easily link entities across different graphs. In addition to the performance lift, Meta-NA greatly improves the anchor linking generalization, significantly reduces the computational overheads, and is easily extendable to multi-network alignment scenarios. Extensive experiments conducted on three real-world datasets demonstrate the superiority of Meta-NA over several state-of-the-art baselines in terms of both alignment accuracy and learning efficiency.

With the maturation of wireless charging technology, Wireless Rechargeable Sensor Networks (WRSNs) has become a promising solution for prolong network lifetimes. Recently studies propose to employ a mobile charger (MC) to simultaneously charge multiple sensors within the same charging range, such that the charging performance can be improved. In this paper, we aim to jointly optimize the number of dead sensors and the energy usage effectiveness in such multi-node charging scenarios. We achieve this by introducing the partial charging mechanism, meaning that instead of following the conventional way that each sensor gets fully charged in one time step, our work allows MC to fully charge a sensor by multiple times. We show that the partial charging mechanism causes minimizing the number of dead sensors and maximizing the energy usage effectiveness to conflict with each other. We formulate this problem and develop a multi-node temporal spatial partial-charging algorithm (MTSPC) to solve it. The optimality of MTSPC is proved, and extensive simulations are carried out to demonstrate the effectiveness of MTSPC.

The past few years have witnessed the explosive growth of Internet of Things (IoT) devices. The necessity of real-time edge intelligence for IoT applications demands that decision making must take place right here right now at the network edge, thus dictating that a high percentage of the IoT created data should be stored and analyzed locally. However, the computing resources are constrained and the amount of local data is often very limited at edge nodes. To tackle these challenges, we propose a distributionally robust optimization (DRO)-based edge intelligence framework, which is based on an innovative synergy of cloud knowledge transfer and local learning. More specifically, the knowledge transfer from the cloud learning is in the form of a reference distribution and its associated uncertainty set. Further, based on its local data, the edge device constructs an uncertainty set centered around its empirical distribution. The edge learning problem is then cast as a DRO problem subject to the above two distribution uncertainty sets. Building on this framework, we investigate two problem formulations for DRO-based edge intelligence, where the uncertainty sets are constructed using the Kullback-Leibler divergence and the Wasserstein distance, respectively. Numerical results demonstrate the effectiveness of the proposed DRO-based framework.

The increasing congestion of the RF spectrum is a key challenge for low-power wireless networks using concurrent transmissions. The presence of radio interference can indeed undermine their dependability, as they rely on a tight synchronization and incur a significant overhead to overcome packet loss. In this paper, we present Harmony, a new data collection protocol that exploits the benefits of concurrent transmissions and embeds techniques to ensure a reliable and timely packet delivery despite highly congested channels. Such techniques include, among others, a data freezing mechanism that allows to successfully deliver data in a partitioned network as well as the use of network coding to shorten the length of packets and increase the robustness to unreliable links. Harmony also introduces a distributed interference detection scheme that allows each node to activate various interference mitigation techniques only when strictly necessary, avoiding unnecessary energy expenditures while finding a good balance between reliability and timeliness. An experimental evaluation on real-world testbeds shows that Harmony outperforms state-of-the-art protocols in the presence of harsh Wi-Fi interference, with up to 50% higher delivery rates and significantly shorter end-to-end latencies, even when transmitting large packets.

As 5G deployments start to roll-out, indoor solutions are increasingly pressed towards delivering a similar user experience. Wi-Fi is the predominant technology of choice indoors and major vendors started addressing this need by incorporating the mmWave band to their products. In the near future, mmWave devices are expected to become pervasive, opening up new business opportunities to exploit their unique properties.In this paper, we present a novel PASsive Intrusion Detection system, namely PASID, leveraging on already deployed indoor mmWave communication systems. PASID is a software module that runs in off-the-shelf mmWave devices. It automatically models indoor environments in a passive manner by exploiting regular beamforming alignment procedures and detects intruders with a high accuracy. We model this problem analytically and show that for dynamic environments machine learning techniques are a cost-efficient solution to avoid false positives. PASID has been implemented in commercial off-the-shelf devices and deployed in an office environment for validation purposes. Our results show its intruder detection effectiveness (~99% accuracy) and localization potential (~ 2 meters range) together with its negligible energy increase cost (~ 2%).

Erasure coding becomes increasingly popular in distributed storage systems (DSSes) for providing high reliability with low storage overhead. However, traditional random data placement causes massive cross-rack traffic and severely unbalanced load during failure recovery, degrading the recovery performance significantly. In addition, various erasure coding policies coexisting in a DSS exacerbates the above problem. In this paper, we propose PDL, a PBD-based Data Layout, to optimize failure recovery performance in DSSes. PDL is constructed based on Pairwise Balanced Design, a combinatorial design scheme with uniform mathematical properties, and thus presents a uniform data layout. Then we propose rPDL, a failure recovery scheme based on PDL. rPDL reduces cross-rack traffic effectively and provides nearly balanced cross-rack traffic distribution by uniformly choosing replacement nodes and retrieving determined available blocks to recover the lost blocks. We implemented PDL and rPDL in Hadoop 3.1.1. Compared with existing data layout of HDFS, experimental results show that rPDL reduces degraded read latency by an average of 62.83%, delivers 6.27× data recovery throughput, and provides evidently better support for front-end applications.

Recently backscatter communication with commodity radios has received significant attention since specialized hardware is no longer needed. The state-of-the-art BLE backscatter system, FreeRider, realizes ultra-low-power BLE backscatter communication entirely using commodity devices. It, however, suffers from several key reliability issues, including unreliable two-step modulation, productive-data dependency, and lack of interference countermeasures. To address these problems, we propose RBLE, a reliable BLE backscatter system that works with a single commodity receiver. It first introduces direct frequency shift modulation with the single tone generated by an excitation BLE device, making robust single-bit modulation possible. Then it designs dynamic channel configuration that enables channel hopping to avoid interfered channels. Moreover, it presents BLE packet regeneration that uses adaptive encoding to further enhance reliability for various channel conditions. The prototype is implemented using TI BLE radios and customized tags with FPGAs. Empirical results demonstrate that RBLE achieves more than 17x uplink goodput gains over FreeRider under indoor LoS, NLoS, and outdoor environments. We also show that RBLE can realize uplink ranges of up to 25 m for indoors and 56 m for outdoors.

Collaborative computing, leveraging resource on multiple wireless-connected devices, enables complex applications that a single device cannot support individually. However, the problem of assigning tasks over devices becomes challenging in the dynamic environments encountered in real-world settings, considering that the resource availability and channel conditions change over time in unpredictable ways due to mobility and other factors. In this paper, we formulate the task assignment problem as an online learning problem using an adversarial multi-armed bandit framework. We propose MABSTA, a novel algorithm that learns the performance of unknown devices and channel qualities continually through exploratory probing and makes task assignment decisions by exploiting the gained knowledge. The implementation of MABSTA, based on Gibbs Sampling approach, is computational-light and offers competitive performance in different scenarios on the trace-data obtained from a wireless IoT testbed. Furthermore, we prove that MABSTA is 1-competitive compared to the best offline assignment for any dynamic environment without stationarity assumptions, and demonstrate the polynomial-time algorithm for the exact implementation of the sampling process. To the best of our knowledge, MABSTA is the first online learning algorithm tailored to this class of problems.

The link speed in production datacenters is growing fast, from 1Gbps to 40Gbps or even 100Gbps. However, the buffer size of commodity switches increases slowly, e.g., from 4MB at 1Gbps to 16MB at 100Gbps, thus significantly outpaced by the link speed. In such extremely shallow-buffered networks, today's TCP/ECN solutions, such as DCTCP, suffer from either excessive packet loss or substantial throughput degradation.To this end, we present BCC1, a simple yet effective solution that requires just one more ECN config (i.e., shared buffer ECN/RED) over prior solutions. BCC operates based on real-time global shared buffer utilization. When available buffer space suffices, BCC delivers both high throughput and low packet loss rate as prior work; Once it gets insufficient, BCC automatically triggers the shared buffer ECN to prevent packet loss at the cost of sacrificing little throughput. BCC is readily deployable with existing commodity switches. We validate BCC's hardware feasibility in a small 100G testbed and evaluate its performance using large-scale simulations. Our results show that BCC maintains low packet loss rate while slightly degrading throughput when the available buffer becomes insufficient. For example, compared to current practice, BCC achieves up to 94.4% lower 99th percentile flow completion time (FCT) for small flows while degrading average FCT for large flows by up to 3%.

New optical technologies offer the ability to reconfigure network topologies dynamically, rather than setting them once and for all. This is true in both optical wide area networks (optical WANs) and in datacenters, despite the many differences between these two settings. Because of these new technologies, there has been a surge of both practical and theoretical research on algorithms to take advantage of them. In particular, Jia et al. [INFOCOM '17] designed online scheduling algorithms for dynamically reconfigurable topologies for both the makespan and sum of completion times objectives. In this paper, we work in the same setting but study an objective that is more meaningful in an online setting: the sum of flow times. The flow time of a job is the total amount of time that it spends in the system, which may be considerably smaller than its completion time if it is released late. We provide competitive algorithms for the online setting with speed augmentation, and also give a lower bound proving that speed augmentation is in fact necessary. As a side effect of our techniques, we also improve and generalize the results of Jia et al. on completion times by giving an O(1)-competitive algorithm for arbitrary sizes and release times even when nodes have different degree bounds, and moreover allow for the weighted sum of completion times (or flow times).

The emergence of bandwidth-intensive latency-critical traffic in 5G Networks, such as Virtual Reality and Cloud Gaming, has motivated interest in wireless resource allocation problems for flows with hard-deadlines. Attempting to solve this problem brings about the following two key challenges: (i) The flow arrival and the wireless channel state information are not known to the Base Station (BS) apriori, thus, the allocation decisions need to be made in an online manner. (ii) Resource allocation algorithms that attempt to maximize a reward in the wireless setting will likely be unfair, causing unacceptable service for some users. In the first part of this paper, we model the problem of allocating resources to deadline-sensitive traffic as an online convex optimization problem, where the BS acquires a per-request reward that depends on the amount of traffic transmitted within the required deadline. We address the question of whether we can efficiently solve that problem with low complexity. In particular, whether we can design a constant-competitive scheduling algorithm that is oblivious to requests' deadlines. To this end, we propose a primal-dual Deadline-Oblivious (DO) algorithm, and show it is approximately 3.6-competitive. Furthermore, we show via simulations that our algorithm tracks the prescient offline solution very closely, significantly outperforming several algorithms that were previously proposed. Our results demonstrate that even though a scheduler may not know the deadlines of each flow, it can still achieve good theoretical and empirical performance. In the second part, we impose a stochastic constraint on the allocation, requiring a guarantee that each user achieves a certain timely throughput (amount of traffic delivered within the deadline over a period of time). We propose a modified version of our algorithm, called the Long-term Fair Deadline Oblivious (LFDO) algorithm for that setup. We combine the Lyapunov framework for stochastic optimization with the Primal-Dual analysis of online algorithms, to show that LFDO retains the high-performance of DO, while satisfying the long-term stochastic constraints.

A significant challenge for future virtual reality (VR) applications is to deliver high quality-of-experience, both in terms of video quality and responsiveness, over wireless networks with limited bandwidth. This paper proposes to address this challenge by leveraging the predictability of user movements in the virtual world. We consider a wireless system where an access point (AP) serves multiple VR users. We show that the VR application process consists of two distinctive phases, whereby during the first (proactive scheduling) phase the controller has uncertain predictions of the demand that will arrive at the second (deadline scheduling) phase. We then develop a predictive scheduling policy for the AP that jointly optimizes the scheduling decisions in both phases. In addition to our theoretical study, we demonstrate the usefulness of our policy by building a prototype system. We show that our policy can be implemented under Furion, a Unity-based VR gaming software, with minor modifications. Experimental results clearly show visible difference between our policy and the default one. We also conduct extensive simulation studies, which show that our policy not only outperforms others, but also maintains excellent performance even when the prediction of future user movements is not accurate.

A long-standing vision of backscatter communications is to provide long-range connectivity and high-speed transmissions for batteryless Internet-of-Things (IoT). Recent years have seen major innovations in designing backscatters toward this goal. Yet, they either operate at a very short range, or experience extremely low throughput. This paper takes one step further toward breaking this stalemate, by presenting PolarScatter that exploits channel polarization in long-range backscatter links. We transform backscatter channels into nearly noiseless virtual channels through channel polarization, and convey bits with extremely low error probability. Specifically, we propose a new polar code scheme that automatically adapts itself to different channel quality, and design a low-cost encoder to accommodate polar codes on resource-constrained backscatter tags. We build a prototype PCB tag and test it in various outdoor and indoor environments. Our experiments show that our prototype achieves up to 10× throughput gain, or extends the range limit by 1.8× compared with the state-of-the-art long-range backscatter solution. We also simulate an IC design in TSMC 65 nm LP CMOS process. Compared with traditional encoders, our encoder reduces storage overhead by three orders of magnitude, and lowers the power consumption to tens of microwatts.