INFOCOM 2022 Papers

Serverless edge computing adopts an event-based model where Internet-of-Things (IoT) services are executed in lightweight containers only when requested, leading to significantly improved edge resource utilization. Unfortunately, the startup latency of containers degrades the responsiveness of IoT services dramatically. Container caching, while masking this latency, requires retaining resources thus compromising resource efficiency. In this paper, we study the retention-aware container caching problem in serverless edge computing. We leverage the distributed and heterogeneous nature of edge platforms and propose to optimize container caching jointly with request distribution. We reveal step by step that this joint optimization problem can be mapped to the classic ski-rental problem. We first present an online competitive algorithm for a special case where request distribution and container caching are based on a set of carefully designed probability distribution functions. Based on this algorithm, we propose an online algorithm called O-RDC for the general case, which incorporates the resource capacity and network latency by opportunistically distributing requests. We conduct extensive experiments to examine the performance of the proposed algorithms with both synthetic and real-world serverless computing traces. Our results show that ORDC outperforms existing caching strategies of current serverless computing platforms by up to 94.5% in terms of the overall system cost.

The edge-cloud system has the potential to com-bine the advantages of heterogeneous devices and truly realize ubiquitous computing. However, for service providers to guar-antee the Service-Level-Agreement (SLA) priorities, the complex networked environment brings inherent challenges such as multi-resource heterogeneity, resource competition, and networked sys-tem dynamics. In this paper, we design a framework for the edge-cloud system, namely EdgeMatrix, to maximize the throughput while guaranteeing various SLA priorities. First, EdgeMatrix introduces Networked Multi-agent Actor-Critic (NMAC) algorithm to redefines physical resources as logically isolated resource combinations, i.e., resource cells. Then, we use a clustering algorithm to group the cells with similar characteristics into various sets, i.e., resource channels, for different channels can offer different SLA guarantees. Besides, we design a multi-task mechanism to solve the problem of joint service orchestration and request dispatch (JSORD) among edge-cloud clusters, significantly reducing the runtime than traditional methods. To ensure stability, EdgeMatrix adopts a two-time-scale framework, i.e., coordinating resources and services at the large time scale and dispatching requests at the small time scale. The real trace-based experimental results verify that EdgeMatrix can improve system throughput in complex networked environments, reduce SLA violations, and significantly reduce the runtime than traditional methods.

LoRa is widely deployed for various applications. Though the knowledge of the channel occupancy is the prerequisite of all aspects of network management, acquiring the channel occupancy for LoRa is challenging due to the large number of channels to be detected. In this paper, we propose LoRadar, a novel LoRa channel occupancy acquirer based on cross-channel scanning. Our in-depth study finds that Channel Activity Detection (CAD) in a narrow band can indicate the channel activities of wide bands because they have the same slope in the time-frequency domain. Based on our finding, we design the cross-channel scanning mechanism that infers the channel occupancy states of all the overlapping channels by the distribution of CAD results. We elaborately select and adjust the CAD settings to enhance the distribution features. We also design the pattern correction method to cope with distribution distortions. We implement LoRadar on commodity LoRa platforms and evaluate its performance on the indoor testbed and the outdoor deployed network. The experimental results show that LoRadar can achieve a detection accuracy of 0.99 and reduce the acquisition overhead by up to 0.90, compared to existing traversal-based methods.

Fast sector-steering in the mmWave band for vehicular mobility scenarios remains an open challenge. This is because standard-defined exhaustive search over predefined antenna sectors cannot be assuredly completed within short contact times. This paper proposes machine learning to speed up sector selection using data from multiple non-RF sensors, such as LiDAR, GPS, and camera images. The contributions in this paper are threefold: First, a multimodal deep learning architecture is proposed that fuses the inputs from these data sources and locally predicts the sectors for best alignment at a vehicle. Second, it studies the impact of missing data (e.g., missing LiDAR/images) during inference, which is possible due to unreliable control channels or hardware malfunction. Third, it describes the first-of-its-kind multimodal federated learning framework that combines model weights from multiple vehicles and then disseminates the final fusion architecture back to them, thus incorporating private sharing of information and reducing their individual training times. We validate the proposed architectures on a live dataset collected from an autonomous car equipped with multiple sensors (GPS, LiDAR, and camera) and roof-mounted Talon AD7200 60GHz mmWave radios. We observe 52.75% decrease in sector selection time than 802.11ad standard while maintaining 89.32% throughput with the globally optimal solution.

We address the problem of persistent item tracking in large-scale data streams. A persistent item refers to the one that persists to occur in the stream over a long timespan. Tracking persistent items is an important and pivotal functionality for many networking and computing applications as persistent items, though not necessarily contributing significantly to the data volume, may convey valuable information on the data pattern about the stream. The state-of-the-art solutions of tracking persistent items require to know the monitoring time horizon to set the sampling rate. This limitation is further accentuated when we need to track the persistent items in recent w slots where w can be any value between 0 and T to support different monitoring granularity. Motivated by this limitation, we develop a persistent item tracking algorithm that can function without knowing the monitoring time horizon beforehand, and can thus track persistent items up to the current time t or within a certain time window at any moment. Our central technicality is adaptively reducing the sampling rate such that the total memory overhead can be limited while still meeting the target tracking accuracy. Through both theoretical and empirical analysis, we fully characterize the performance of our proposition.

Mobile edge computing facilitates users to offload computation tasks to edge servers for meeting their stringent delay requirements. Previous works mainly explore task offloading when system-side information is given (e.g., server processing speed, cellular data rate), or centralized offloading under system uncertainty. But both generally fall short of handling task placement involving many coexisting users in a dynamic and uncertain environment. In this paper, we develop a multi-user offloading framework considering unknown yet stochastic system-side information to enable a decentralized user-initiated service placement. Specifically, we formulate the dynamic task placement as an online multi-user multi-armed bandit process, and propose a decentralized epoch based offloading (DEBO) to optimize user rewards which are subject to the network delay. We show that DEBO can deduce the optimal user-server assignment, thereby achieving a close-to-optimal service performance and tight O(log T ) offloading regret. Moreover, we generalize DEBO to various common scenarios such as unknown reward gap, dynamic entering or leaving of clients, and fair reward distribution, while further exploring when users’ offloaded tasks require heterogeneous computing resources. Particularly, we accomplish a sub-linear regret for each of these instances. Real measurements based evaluations corroborate the superiority of our offloading schemes over state-of-the-art approaches in optimizing delay-sensitive rewards.

Programmable Logic Controllers (PLCs) are the brains of Industrial Control Systems (ICSes), and thus, are often targeted by attackers. While many intrusion detection systems (IDSes) have been adapted to monitor ICS, they cannot detect malicious network packets from a compromised PLC that con-form to the network protocol. A domain expert needs to manually construct IDS rules to model a PLC’s behavior. That approach is time-consuming and error-prone. Alternatively, machine learning can infer a PLC’s behavior model from network traces, but that model may be inaccurate due to a lack of high-quality training data. This paper presents CoToRu - a toolchain that takes in the PLC’s code to automatically generate a comprehensive set of IDS rules. CoToRu comprises (1) an analyzer that parses PLC code to build a state transition table for modeling the PLC’s behavior, and (2) a generator that instantiates IDS rules for detecting deviations in PLC behavior. The generated rules can be imported into Zeek IDS to detect various attacks. We apply CoToRu to a power grid testbed and show that our generated rules provide superior performance compared to existing IDSes, including those based on statistical analysis, invariant-checking, and machine learning. Our prototype with CoToRu’s generated rules provide sub-millisecond detection latency, even for complex PLC logic.

Edge-cloud jobs are rapidly prevailing in many application domains, posing the challenge of using both resource-strenuous edge devices and elastic cloud resources. Efficient resource allocation on such jobs via scheduling algorithms is essential to guarantee their performance, e.g. latency. Deep reinforcement learning (DRL) is increasingly adopted to make scheduling decisions but faces the conundrum of achieving high rewards at a low training overhead. It is unknown if such a DRL can be applied to timely tune the scheduling algorithms that are adopted in response to fast changing workloads and resources. In this paper, we propose EdgeTuner to effectively leverage DRL to select scheduling algorithms online for edge-cloud jobs. The enabling features of EdgeTuner are sophisticated DRL model that captures complex dynamics of Edge-Cloud jobs/tasks and an effective simulator to emulate the response times of short-running jobs in accordance to dynamically changing scheduling algorithms. EdgeTuner trains DRL agents offline by directly interacting with the simulator. We implement EdgeTuner on Kubernetes scheduler and extensively evaluate it on Kubernetes cluster testbed driven by the production traces. Our results show that EdgeTuner outperforms prevailing scheduling algorithms by achieving significant lower job response time while accelerating DRL training speed by more than 180x.

Employing today’s deep neural network (DNN) into the cross-platform web with an offloading way has been a promising means to alleviate the tension between intensive inference and limited computing resources. However, it is still challenging to directly leverage the distributed DNN execution into web apps with the following limitations, including (1) how special computing tasks such as DNN inference can provide fine-grained and efficient offloading in the inefficient JavaScript-based environment? (2) lacking the ability to balance the latency and mobile energy to partition the inference facing various web applications’ requirements. (3) and ignoring that DNN inference is vulnerable to the operating environment and mobile devices’ computing capability, especially dedicated web apps. This paper designs AoDNN, an automatic offloading framework to orchestrate the DNN inference across the mobile web and the edge server, with three main contributions. First, we design the DNN offloading based on providing a snapshot mechanism and use multi-threads to monitor dynamic contexts, partition decision, trigger offloading, etc. Second, we provide a learning-based latency and mobile energy prediction framework for supporting various web browsers and platforms. Third, we establish a multi-objective optimization to solve the optimal partition by balancing the latency and mobile energy.

Distributed computing has become a common practice nowadays, where recent focus has been given to the usage of smart networking devices with in-network computing capabilities. State-of-the-art switches with near-line rate computing and aggregation capabilities enable acceleration and improved performance for various modern applications like big data analytics and large-scale distributed and federated machine learning.In this work, we formulate and study the theoretical algorithmic foundations of such approaches, and focus on how to deploy and use constrained in-network computing capabilities within the data center. We focus our attention on reducing the network congestion, i.e., the most congested link in the network, while supporting the given workload(s). We present an efficient optimal algorithm for tree-like network topologies and show that our solution provides as much as an x13 improvement over common alternative approaches. In particular, our results show that having merely a small fraction of network devices that support in-network aggregation can significantly reduce the network congestion, both for single and multiple workloads.

IFTTT is a programming framework for Applets (i.e., user customized policies with a "trigger-action" syntax), and is the most popular Home Internet-of-Things (H-IoT) platform. The execution of an Applet prompted by a device operation suffers from a long delay, since IFTTT has to periodically reads the states of the device to determine whether the trigger is satisfied, with an interval of up to 5min for professionals and 60min for normal users. Although IFTTT sets up a flexible polling interval based on the past several times an Applet has run, the delay is still around 2min even for frequently executed Applets. This paper proposes a novel trigger notification mechanism "RTX-IFTTT" to implement real-time execution of Applets. The mechanism does not require any changes to the current IFTTT framework or the H-IoT devices, but only requires an H-IoT edge node (e.g., router) to identify the device events (e.g., turning on/off) and notify IFTTT to perform the action of an Applet when an identified event is the trigger of that Applet. The experimental results show that the averaged Applet execution delay for RTX-IFTTT is only about 2sec.

IMU-based eavesdropping has brought growing concerns over smartphone users’ privacy. In such attacks, adversaries utilize IMUs that require zero permissions for access to acquire speeches. A common countermeasure is to limit sampling rates (within 200 Hz) to reduce overlap of vocal fundamental bands (85-255 Hz) and inertial measurements (0-100 Hz). Nevertheless, we experimentally observe that IMUs sampling below 200 Hz still record adequate speech-related information because of aliasing distortions. Accordingly, we propose a practical side-channel attack, InertiEAR, to break the defense of sampling rate restriction on the zero-permission eavesdropping. It leverages IMUs to eavesdrop on both top and bottom speakers in smartphones. In the InertiEAR design, we exploit coherence between responses of the built-in accelerometer and gyroscope and their hardware diversity using a mathematical model. The coherence allows precise segmentation without manual assistance. We also mitigate the impact of hardware diversity and achieve better device-independent performance than existing approaches that have to massively increase training data from different smartphones for a scalable network model. These two advantages re-enable zero-permission attacks but also extend the attacking surface and endangering degree to off-the-shelf smartphones. InertiEAR achieves a recognition accuracy of 78.8% with a cross-device accuracy of up to 49.8% among 12 smartphones.

Redundancy elimination (RE) systems allow network users to remove duplicate parts in their messages by introducing caches at both message senders’ and receivers’ sides. While RE systems have been successfully deployed for handling unencrypted traffic, making them work over encrypted links is still open. A few solutions have been proposed recently, however they either completely violate end-to-end security or focus on single-user setting. In this paper, we present a highly secure RE solution which supports cross-user redundancy eliminations on encrypted traffics. Our solution not only preserves the end-to-end security against outside adversaries, but also protects users’ privacy against semi-honest RE agents. Furthermore, our solution can defend malicious users’ poisoning attack, which is crucial for cross-user RE systems but has never been studied before. In cross-user RE systems, since all users inside a LAN write into a shared, global cache and use it to recover their original messages from deduplicated ones, the poisoning attack is prone to happen, and cause systematic damage to all users even when only one user is malicious and injects poisoned data into the cache. We rigorously prove our solution’s security properties, and demonstrate its promising performance via testing the proof-of-concept implementation with real-world internet traffic data.

In Machine Learning, the emergence of the right to be forgotten gave birth to a paradigm named machine unlearning, which enables data holders to proactively erase their data from a trained model. Existing machine unlearning techniques focus on centralized training, where access to all holders’ training data is a must for the server to conduct the unlearning process. It remains largely underexplored about how to achieve unlearning when full access to all training data becomes unavailable. One noteworthy example is Federated Learning (FL), where each participating data holder trains locally, without sharing their training data to the central server. In this paper, we investigate the problem of machine unlearning in FL systems. We start with a formal definition of the unlearning problem in FL and propose a rapid retraining approach to fully erase data samples from a trained FL model. The resulting design allows data holders to jointly conduct the unlearning process efficiently while keeping their training data locally. Our formal convergence and complexity analysis demonstrate that our design can preserve model utility with high efficiency. Extensive evaluations on four real-world datasets illustrate the effectiveness and performance of our proposed realization.

Sharding technique, which divides the whole network into multiple disjoint groups or committees, has been recognized as a revolutionary solution to enhance the scalability of blockchains. For account-based model, state data are partitioned over all committees and organized as Merkle trees to ensure data consistency and immutability. However, existing techniques on Merkle tree-based state storage fail to scale out due to a large amount of network and compute overheads incurred by data migration and Merkle tree reconstruction, respectively. In this paper, we propose $\mathcal{S}$-Store, a scalable data storage technique towards permissioned blockchain sharding based on Aggregate Merkle B+ tree (AMB-tree). $\mathcal{S}$-Store utilizes consistent hashing to reduce data migration among committees and uses split and merge on AMB-tree to decrease Merkle tree reconstruction overheads. $\mathcal{S}$-Store also employs a novel committee addition protocol that guarantees the system service availability during data migration. Extensive experiments show that $\mathcal{S}$-Sotre outperforms existing techniques by one order of magnitude in terms of transaction execution, data transmission, and committee addition.

The importance of the dynamics of the viewport pose, i.e., the location and the orientation of users’ points of view, for virtual reality (VR) experiences calls for the development of VR viewport pose models. In this paper, informed by our experimental measurements of viewport trajectories across 3 different types of VR interfaces, we first develop a statistical model of viewport poses in VR environments. Based on the developed model, we examine the correlations between pixels in VR frames that correspond to different viewport poses, and obtain an analytical expression for the visibility similarity (ViS) of the pixels across different VR frames. We then propose a lightweight ViS-based ALG-ViS algorithm that adaptively splits VR frames into the background and the foreground, reusing the background across different frames. Our implementation of ALG-ViS in two Oculus Quest 2 rendering systems demonstrates ALG-ViS running in real time, supporting the full VR frame rate, and outperforming baselines on measures of frame quality and bandwidth consumption.

This study is motivated by the maximum connected coverage problem (MCCP), which is to deploy a connected UAV network with given K UAVs in the top of a disaster area such that the number of users served by the UAVs is maximized. The deployed UAV network must be connected, since the received data by a UAV from its served users need to be sent to the Internet through relays of other UAVs. Motivated by this application, in this paper we study a more generalized problem – the h-hop independently submodular maximization problem, where the MCCP problem is one of its special cases with h = 4. We propose a $\frac{{1 - 1/e}}{{2h + 3}}$-approximation algorithm for the h-hop independently submodular maximization problem, where e is the base of the natural logarithm. Then, one direct result is a $\frac{{1 - 1/e}}{{11}}$-approximate solution to the MCCP problem with h = 4, which significantly improves its currently best $\frac{{1 - 1/e}}{{32}}$-approximate solution. We finally evaluate the performance of the proposed algorithm for the MCCP problem in the application of deploying UAV networks, and experimental results show that the number of users served by deployed UAVs delivered by the proposed algorithm is up to 12.5% larger than those by existing algorithms.

Transfer learning does not train from scratch but leverages existing models to help train the new model of better accuracy. Unfortunately, realizing transfer learning in distributed cloud-edge networks faces critical challenges such as online training, uncertain network environments, time-coupled control decisions, and the balance between resource consumption and model accuracy. We formulate distributed transfer learning as a non-linear mixed-integer program of long-term cost optimization. We design polynomial-time online algorithms by exploiting the real-time trade-off between preserving previous decisions and applying new decisions, based on primal-dual one-shot solutions for each single time slot. While orchestrating model placement, data dispatching, and inference aggregation, our approach produces new models via combining the existing offline models and the online models being trained using weights adaptively updated based on inference upon data samples that dynamically arrive. Our approach provably incurs the number of inference mistakes no greater than a constant times that of the single best model in hindsight, and achieves a constant competitive ratio for the total cost. Evaluations have confirmed the superior performance of our approach compared to alternatives on real-world traces.

The Border Gateway Protocol (BGP) is a distributed protocol that manages interdomain routing without requiring a centralized record of which autonomous systems (ASes) connect to which others. Many methods have been devised to infer the AS topology from publicly available BGP data, but none provide a general way to handle the fact that the data are notoriously incomplete and subject to error. This paper describes a method for reliably inferring AS-level connectivity in the presence of measurement error using Bayesian statistical inference acting on BGP routing tables from multiple vantage points. We employ a novel approach for counting AS adjacency observations in the AS-PATH attribute data from public route collectors, along with a Bayesian algorithm to generate a statistical estimate of the AS-level network. Our approach also gives us a way to evaluate the accuracy of existing reconstruction methods and to identify advantageous locations for new route collectors or vantage points.