INFOCOM 2024 Papers

In mobile edge computing (MEC), resource scheduling is crucial to task requests’ performance and service providers’ cost, involving multi-layer heterogeneous scheduling decisions. Existing schedulers typically adopt static timescales to regularly update scheduling decisions of each layer, without adaptive adjustment of timescales for different layers, resulting in potentially poor performance in practice.We notice that the adaptive timescales would significantly improve the trade-off between the operation cost and delay performance. Based on this insight, we propose EdgeTimer, the first work to automatically generate adaptive timescales to update multi-layer scheduling decisions using deep reinforcement learning (DRL). First, EdgeTimer uses a three-layer hierarchical DRL framework to decouple the multi-layer decision-making task into a hierarchy of independent sub-tasks for improving learning efficiency. Second, to cope with each sub-task, EdgeTimer adopts a safe multi-agent DRL algorithm for decentralized scheduling while ensuring system reliability. We apply EdgeTimer to a wide range of Kubernetes scheduling rules, and evaluate it using production traces with different workload patterns. Extensive trace-driven experiments demonstrate that EdgeTimer can learn adaptive timescales, irrespective of workload patterns and built-in scheduling rules. It obtains up to 9:1 more profit than existing approaches without sacrificing the delay performance.

Radio environment maps provide a comprehensive spatial view of the wireless channel and are especially useful in on-demand UAV wireless networks where operators are not afforded the typical time spent planning base station deployments (e.g. emergency response). Equipped with an accurate radio environment map, a mobile UAV can quickly locate to an optimal location to serve users on the ground. Machine learning has recently been proposed as a tool to create radio environment maps from satellite images of the target environment. However, the highly dynamic nature that precipitates most on-demand aerial network deployments likely renders the satellite image data available for the environment to be inaccurate. In this paper we present, OREMAN, a hybrid offline-online system for aerial radio environment map creation which leverages a common sensing modality present on most UAVs: visual cameras. OREMAN combines a suite of off-line trained neural network models with an adaptive trajectory planning algorithm to iteratively predict/refine the radio environment map and estimate the most valuable trajectory locations. By using UAV vision, OREMAN arrives at a highly accurate map much faster and with fewer measurements than other approaches, and is very effective even in scenarios where no prior environmental knowledge is available.

Federated Reinforcement Learning (FRL) has garnered increasing attention recently. However, due to the intrinsic spatio-temporal non-stationarity of data distributions, the current approaches typically suffer from high interaction and communication costs. In this paper, we introduce a new FRL algorithm, named MFPO, that utilizes momentum, importance sampling, and additional server-side adjustment to control the shift of stochastic policy gradients and enhance the efficiency of data utilization. We prove that by proper selection of momentum parameters and interaction frequency, MFPO can achieve $\widetilde {\mathcal{O}}\left({H{N^{ - 1}}{\varepsilon ^{ - 3/2}}}\right)$ and $\widetilde {\mathcal{O}}\left({{\varepsilon ^{ - 1}}}\right)$ interaction and communication complexities (N represents the number of agents), where the interaction complexity achieves linear speedup with the number of agents, and the communication complexity aligns the best achievable of existing first-order FL algorithms. Extensive experiments corroborate the substantial performance gains of MFPO over existing methods on a suite of complex and high-dimensional benchmarks.

With the rapid evolution of space-borne capabilities, space edge computing (SEC) is becoming a new computation paradigm for future integrated space and terrestrial networks. Satellite edges adopt advanced on-board hardware, which not only enables new opportunities to perform complex intelligent tasks in orbit, but also involves new challenges due to the additional energy consumption in power-constrained space environment.In this paper, we present Phoenix, an energy-efficient task scheduling framework for emerging SEC networks. Phoenix exploits a key insight that in the SEC network, there always exist a number of sunlit edges which are illuminated during the entire orbital period and have sufficient energy supplement from the sun. Phoenix accomplishes energy-efficient in-orbit computing by judiciously offloading space tasks to "sunlight-sufficient" edges or to the ground. Specifically, Phoenix first formulates the SEC battery energy optimizing (SBEO) problem which aims at minimizing the average battery energy consumption while satisfying various task completion constraints. Then Phoenix incorporates a sunlight-aware scheduling mechanism to solve the SBEO problem and schedule SEC tasks efficiently. Finally, we implement a Phoenix prototype and build an SEC testbed. Extensive data-driven evaluations demonstrate that as compared to other state-of-the-art solutions, Phoenix can effectively reduce up to 54.8% SEC battery energy consumption and prolong battery lifetime to 2.9× while still completing tasks on time.

Recently, sharding has become a popular direction to scale out blockchain systems by dividing the network into shards that process transactions in parallel. However, secure and efficient cross-shard transaction processing remains a vital and unaddressed challenge. Existing work handles a cross-shard transaction via transaction division: dividing it into sub-transactions, processing them separately, and combing the processing results. Such an approach is unfavorable for decentralized blockchain due to its reliance on trustworthy parties, e.g., the client or a reference node, to perform the transaction division and result combination. Furthermore, the processing result of one transaction can affect another, violating the important property of transaction isolation. In this work, we propose Sharon, a novel sharding protocol that processes cross-shard transactions via shard rotation rather than transaction division. In Sharon, shards rotate to merge pairwisely and process cross-shard transactions when merged. Sharon eliminates reliance on trustworthy parties and provides transaction isolation in nature because transactions are no longer divided. Nevertheless, it poses a scientific question of when and how to merge the shards to improve system performance. To answer the question, we formally define the shard scheduling problem to minimize transaction confirmation latency and propose a novel construction algorithm. The proposed algorithm is proven optimal and runs in polynomial time. We conduct extensive experiments on Amazon EC2 instances using Bitcoin and Ethereum data. The results indicate that Sharon achieves nearly linear scalability, improves the system throughput by 139%, and saves the transaction processing latency by 72.4% compared with state-of-the-art approaches.

Mobile edge computing offers a myriad of opportunities to innovate and introduce novel applications, thereby enhancing user experiences considerably. A critical issue extensively investigated in this domain is efficient deployment of Service Function Chains (SFCs) across the physical network, spanning from the edge to the cloud. This problem is known to be NP-hard. As a result of its practical importance, there is significant interest in the development of high-quality sub-optimal solutions.In this paper, we consider this problem and propose a novel near-optimal heuristic that is extremely efficient and scalable. We compare our solution to the state-of-the-art heuristic and to the theoretical optimum. In our large scale evaluations, we use realistic topologies which were previously reported in the literature. We demonstrate that the execution time offered by our solution grows slowly as the number of Virtual Network Function (VNF) forwarding graph embedding requests grows, and it handles one million requests in slightly more than 20 seconds for 100 nodes and 150 edges physical topology.

Cross-silo federated learning (FL) enables multiple institutions (clients) to collaboratively build a global model without sharing their private data. To prevent privacy leakage during aggregation, homomorphic encryption (HE) is widely used to encrypt model updates, yet incurs high computation and communication overheads. To reduce these overheads, packed HE (PHE) has been proposed to encrypt multiple plaintexts into a single ciphertext. However, the original design of PHE does not consider the heterogeneity among different clients, an intrinsic problem in cross-silo FL, often resulting in undermined training efficiency with slow convergence and stragglers. In this work, we propose FedPHE, an efficiently packed homomorphically encrypted FL framework with secure weighted aggregation and client selection to tackle the heterogeneity problem. Specifically, using CKKS with sparsification, FedPHE can achieve efficient encrypted weighted aggregation by accounting for contributions of local updates to the global model. To mitigate the straggler effect, we devise a sketching-based client selection scheme to cherry-pick representative clients with heterogeneous models and computing capabilities. We show, through rigorous security analysis and extensive experiments, that FedPHE can efficiently safeguard clients’ privacy, achieve a training speedup of 1.85 − 4.44×, cut the communication overhead by 1.24 − 22.62× , and reduce the straggler effect by up to 1.71 − 2.39×.

Free weight training (FWT) is of utmost importance for physical well-being. However, the success of FWT depends on choosing the suitable workload, as improper selections can lead to suboptimal outcomes or injury. Current workload estimation approaches rely on manual recording and specialized equipment with limited feedback. Therefore, we introduce PPGSpotter, a novel PPG-based system for FWT monitoring in a convenient, low-cost, and fine-grained manner. By characterizing the arterial geometry compressions caused by the deformation of distinct muscle groups during various exercises and workloads in PPG signals, PPGSpotter can infer essential FWT factors such as workload, repetitions, and exercise type. To remove pulse-related interference that heavily contaminates PPG signals, we develop an arterial interference elimination approach based on adaptive filtering, effectively extracting the pure motion-derived signal (MDS). Furthermore, we explore 2D representations within the phase space of MDS to extract spatiotemporal information, enabling PPGSpotter to address the challenge of resisting sensor shifts. Finally, we leverage a multi-task CNN-based model with workload adjustment guidance to achieve personalized FWT monitoring. Extensive experiments with 15 participants confirm that PPGSpotter can achieve workload estimation (0.59 kg RMSE), repetitions estimation (0.96 reps RMSE), and exercise type recognition (91.57% F1-score) while providing valid workload adjustment recommendations.

In the era of global services, low-latency analytics on large-volume geo-distributed data has been a regular demand for application decision-making. Serverless computing facilitates fast function start-up and deployment, making it an attractive way for geo-distributed analytics. We argue that the serverless paradigm holds the potential to breach current performance bottlenecks via fine-grained function orchestration. However, how to configure it for geo-distributed analytics remains ambiguous. To fill this gap, we present Demeter, a scalable fine-grained function orchestrator for geo-distributed serverless analytics systems. Demeter aims to minimize the composite cost of co-existing jobs while meeting the user-specific Service Level Objectives (SLO). To handle the volatile environments and learn the diverse function demands, a Multi-Agent Reinforcement Learning (MARL) solution is used to co-optimize the per-function placement and resource allocation. The MARL extracts holistic and compact states via hierarchical graph neural networks, and then designs a novel actor network to shrink the huge decision space and model complexity. Finally, we implement Demeter and evaluate it using realistic workloads. The experimental results reveal that Demeter significantly saves costs by 23.3%∼32.7%, while reducing SLO violations by over 27.4%, surpassing state-of-the-art solutions.

A boundary is a physical or virtual line that marks the edge or limit of a specific region, which has been widely used in many applications, such as autonomous driving, virtual wall, and robotic lawn mowers. However, none of existing work can well balance the cost, the deployability, and the scalability of a boundary. In this paper, we propose a new RFID-based boundary scheme together with its detection algorithm called RF-Boundary, which has the competitive advantages of being battery-free, low-cost, and easy-to-maintain. We develop two technologies of phase gradient and dual-antenna DoA to address the key challenges posed by RF-boundary, in terms of lack of calibration information and multi-edge interference. We implement a prototype of RF-Boundary with commercial RFID systems and a mobile robot. Extensive experiments verify the feasibility as well as the good performance of RF-Boundary.

Two-way backscatter is essential to general-purpose backscatter communication as it provides rich interaction to support diverse applications on commercial devices. However, existing Bluetooth backscatter systems suffer from unstable uplinks due to poor carrier-identification capability and inefficient downlinks caused by packet-length modulation. This paper proposes EffBlue, an efficient two-way backscatter design for commercial Bluetooth devices. EffBlue employs a simple edge backscatter server that alleviates the computational burden on the tag and helps build efficient uplinks and downlinks. Specifically, efficient uplinks are designed by introducing an accurate synchronization scheme, which can effectively eliminate the use of non-compliant packets as carriers. To break the limitation of packet-level modulation, we design a new symbollevel WiFi-ASK downlink where the edge sends ASK-like WiFi signals and the tag can decode such signals using a simple envelope detector. We prototype the edge server using commodity WiFi and Bluetooth chips and build two-way backscatter tags with FPGAs. Experimental results show that EffBlue can identify the target excitations with more than 99% precision. Meanwhile, its WiFi-ASK downlink can achieve up to 124 kbps, which is 25x better than FreeRider.

We study the design of scheduling policies to minimize monitoring error for a collection of correlated sources, where only one source can be observed at any given time. We model correlated sources as a discrete-time Wiener process, where the increments are multivariate normal random variables, with a general covariance matrix that captures the correlation structure between the sources. Under a Kalman filter based optimal estimation framework, we show that the performance of all scheduling policies oblivious to instantaneous error, can be lower and upper bounded by the weighted sum of Age of Information (AoI) across the sources for appropriately chosen weights. We use this insight to design scheduling policies that are only a constant factor away from optimality, and make the rather surprising observation that AoI-based scheduling that ignores correlation is sufficient to obtain performance guarantees. We also derive scaling results that show that the optimal error scales roughly as the square of the dimensionality of the system, even in the presence of correlation. Finally, we provide simulation results to verify our claims.

Transformer-based models have unlocked a plethora of powerful intelligent applications at the edge, such as voice assistant in smart home. Traditional deployment approaches offload the inference workloads to the remote cloud server, which would induce substantial pressure on the backbone network as well as raise users’ privacy concerns. To address that, in-situ inference has been recently recognized for edge intelligence, but it still confronts significant challenges stemming from the conflict between intensive workloads and limited on-device computing resources. In this paper, we leverage our observation that many edge environments usually comprise a rich set of accompanying trusted edge devices with idle resources and propose Galaxy, a collaborative edge AI system that breaks the resource walls across heterogeneous edge devices for efficient Transformer inference acceleration. Galaxy introduces a novel hybrid model parallelism to orchestrate collaborative inference, along with a heterogeneity-aware parallelism planning for fully exploiting the resource potential. Furthermore, Galaxy devises a tile-based fine-grained overlapping of communication and computation to mitigate the impact of tensor synchronizations on inference latency under bandwidth-constrained edge environments. Extensive evaluation based on prototype implementation demonstrates that Galaxy remarkably outperforms state-of-the-art approaches under various edge environment setups, achieving up to 2.5× end-to-end latency reduction.

Accurate channel estimation is crucial for the performance gains of massive multiple-input multiple-output (mMIMO) technologies. However, it is bandwidth-unfriendly to estimate large channel matrix frequently to combat the time-varying wireless channel. Deep learning-based channel prediction has emerged to exploit the temporal relationships between historical and future channels to address the bandwidth-accuracy trade-off. Existing methods with convolutional or recurrent neural networks suffer from their intrinsic limitations, including restricted receptive fields and propagation errors. Therefore, we propose a Transformer-based model, CS3T-UNet tailored for mMIMO channel prediction. Specifically, we combine the cross-shaped spatial attention with a group-wise temporal attention scheme to capture the dependencies across spatial and temporal domains, respectively, and introduce the shortcut paths to well-aggregate multi-resolution representations. Thus, CS3T-UNet can globally capture the complex spatial-temporal relationship and predict multiple steps in parallel, which can meet the requirement of channel coherence time. Extensive experiments demonstrate that the prediction performance of CS3T-UNet surpasses the best baseline by at most 6.86 dB with a smaller computation cost on two channel conditions.

Recently, multi-core and multi-mode fibers (MCMMFs) have been considered to overcome physical limitations and increase transport capacity. They are combined with elastic optical networks (EONs) to form spectrally-spatially elastic optical networks (SS-EONs), an emerging technology. Fragmentation and crosstalk (XT) are well-known drawbacks of SS-EONs that increase blocking probability; evaluating blocking probability analytically is difficult due to additional constraints. When calculating blocking probabilities in MCMMFs-based SS-EONs, it is observed that all current studies either employ simulation-based techniques or do not consider defragmentation of their analytical models. This paper proposes an exact analytical continuous-time Markov chain model for blocking probabilities, named AnalyticalDF, in SS-EONs, which considers defragmentation and the XT-avoided approach. AnalyticalDF generates all possible states and transitions while avoiding inter-core and inter-mode XTs for single-class and multi-class requests. Single-class requests utilize the same number of slots, whereas multi-class requests adopt varying numbers of slots to accommodate client needs. We introduce an iterative approximation model for a single-hop link when AnalyticalDF is not tractable due to scalability. We evaluate AnalyticalDF, the iterative approximate model, and simulation studies for a single-hop link. The numerical results indicate that AnalyticalDF outperforms a non-defragmentation-aware benchmark model.

Third-party RPC services have become the mainstream way for users to access Ethereum. In this paper, we present a novel deanonymization attack that can link an Ethereum address to a real-world identity such as IP address of a user who accesses Ethereum via a third-party RPC service. We find that RPC API calls result in distinguishable sizes of encrypted TCP packets. An attacker can then find when a user sends a transaction to an RPC provider and immediately send a beacon transaction after the user transaction. By exploiting the differences in the distributions of inter-arrival time intervals of normal transactions and two simultaneously initiated transactions, the attacker can identify the victim transaction in the Ethereum network. This enables the attacker to correlate the Ethereum address of the victim transaction’s initiator with the source IP address of TCP packets from a victim user. We model the attack through empirical measurements and conduct extensive real-world experiments to validate the effectiveness of our attack. With three optimization strategies, the correlation accuracy can reach to 98.70% and 96.60% respectively in Ethereum testnet and mainnet. We are the first to study the deanonymization of Ethereum users behind third-party RPC services.

We consider a variant of the online caching problem where the items exhibit dependencies among each other: an item can reside in the cache only if all its dependent items are also in the cache. The dependency relations can form any directed acyclic graph. These requirements arise in systems such as CacheFlow (SOSR 2016) that cache forwarding rules for packet classification in IP-based communication networks.First, we present an optimal randomized online caching algorithm which accounts for dependencies among the items. Our randomized algorithm is O(log k)-competitive, where k is the size of the cache, meaning that our algorithm never incurs the cost of O(log k) times higher than even an optimal algorithm that knows the future input sequence.Second, we consider the bypassing model, where requests can be served at a fixed price without fetching the item and its dependencies into the cache — a variant of caching with dependencies introduced by Bienkowski et al. at SPAA 2017. For this setting, we give an $O\left( {\sqrt {k \cdot \log k} } \right)$-competitive algorithm, which significantly improves the best known competitiveness. We conduct a small case study, to find out that our algorithm incurs on average 2x lower cost.

Federated Graph Learning (FGL) has garnered widespread attention by enabling collaborative training on multiple clients for semi-supervised classification tasks. However, most existing FGL studies do not well consider the missing inter-client topology information in real-world scenarios, causing insufficient feature aggregation of multi-hop neighbor clients during model training. Moreover, the classic FGL commonly adopts the FedAvg but neglects the high training costs when the number of clients expands, resulting in the overload of a single edge server. To address these important challenges, we propose a novel FGL framework, named SpreadFGL, to promote the information flow in edge-client collaboration and extract more generalized potential relationships between clients. In SpreadFGL, an adaptive graph imputation generator incorporated with a versatile assessor is first designed to exploit the potential links between subgraphs, without sharing raw data. Next, a new negative sampling mechanism is developed to make SpreadFGL concentrate on more refined information in downstream tasks. To facilitate load balancing at the edge layer, SpreadFGL follows a distributed training manner that enables fast model convergence. Using real-world testbed and benchmark graph datasets, extensive experiments demonstrate the effectiveness of the proposed SpreadFGL. The results show that SpreadFGL achieves higher accuracy and faster convergence against state-of-the-art algorithms.

Large-scale quantum networks with thousands of nodes require topology-oblivious routing protocols to realize. Most existing quantum network routing protocols only consider the intra-domain scenario, where all nodes belong to a single party with complete topology knowledge. However, like the classical Internet, quantum Internet will likely be provided by multiple quantum Internet Service Providers (qISPs). In this paper, we consider the inter-domain scenario, where the network consists of multiple subnetworks owned by mutually untrusted parties without centralized control. Under this setting, previously proposed quantum entanglement routing policies, which rely on the network topology knowledge, are no longer applicable. We propose a Quantum Border Gateway Protocol (QBGP) for efficiently routing entanglement across qISP boundaries. To guarantee high-quality information transmission, we propose an algorithm named online top-K path selection. This algorithm utilizes the information gain introduced in this paper to adaptively decide on measurement parameters, allowing for the selection of high-fidelity paths and accurate fidelity estimates, while minimizing costs. Additionally, we implement a quantum network simulator and evaluate our protocol and algorithm. Our evaluation shows that QBGP effectively distributes entanglement across different qISPs, and our path selection algorithm increases the network performance by selecting high-fidelity paths with much lower resource consumption than other methods.