INFOCOM 2023 Papers

Cloud computing develops rapidly in recent years and provides service to many applications, in which job scheduling becomes more and more important to improve the quality of service. Parallel processing on cloud requires different machines starting simultaneously on the same job and brings processing slowdown due to communications overhead, defined as synchronization constraint and parallel slowdown. This paper investigates a new job scheduling problem of makespan minimization on uniform machines and identical machines with synchronization constraint and parallel slowdown. We first conduct complexity analysis proving that the problem is difficult in the face of adversarial job allocation. Then we propose a novel job scheduling algorithm, United Wrapping Scheduling (UWS), and prove that UWS admits an O(logm)-approximation for makespan minimization over m uniform machines. For the special case of identical machines, UWS is simplified to Sequential Allocation, Refilling and Immigration algorithm (SARI), proved to have a constant approximation ratio of 8 (tight up to a factor of 4). Performance evaluation implies that UWS and SARI have better makespan and realistic approximation ratio of 2 compared to baseline methods United-LPT and FIFO, and lower bounds.

Container based microservices have been widely applied to promote the cloud elasticity. The mainstream Docker containers are structured in layers, which are organized in stack with bottom-up dependency. To start a microservice, the required layers are pulled from a remote registry and stored on its host server, following the layer dependency order. This incurs long microservice startup time and hinders the performance efficiency. In this paper, we discover that, for the first time, the layer pulling order can be adjusted to accelerate the microservice startup. Specifically, we address the problem on microservice layer pulling orchestration for startup time minimization and prove it as NP-hard. We propose a Longest-chain based Out-of-order layer Pulling Orchestration (LOPO) strategy with low computational complexity and guaranteed approximation ratio. Through extensive real-world trace driven experiments, we verify the efficiency of our LOPO and demonstrate that it reduces the microservice startup time by 22.71% on average in comparison with state-of-the-art solutions.

Overlapping gradient communication with backward computation is a popular technique to reduce communication cost in the widely adopted data parallel S-SGD training. However, the resource contention between computation and All-Reduce communication in GPU-based training reduces the benefits of overlap. With GPU cluster network evolving from low bandwidth TCP to high speed networks, more GPU resources are required to efficiently utilize the bandwidth, making the contention more noticeable. Existing communication libraries fail to account for such contention when allocating GPU threads and have suboptimal performance. In this paper, we propose to mitigate the contention by balancing the overlapped computation and communication time. We formulate an optimization problem that decides the communication thread allocation to reduce overall backward time. We develop a dynamic programming based near-optimal solution and extend it to co-optimize thread allocation with tensor fusion. We conduct simulated study and real-world experiment using an 8-node GPU cluster with 50Gb RDMA network training four representative DNN models. Results show that our method reduces backward time by 10%-20% compared with Horovod-NCCL, by 6%-13% compared with tensor-fusion-optimization-only methods. Simulation shows that our method achieves the best scalability with a training speedup of 1.2x over the best-performing baseline as we scale up cluster size.

Federated learning (FL) enables distributed clients to collaboratively learn a shared model while keeping their raw data private. To mitigate the system heterogeneity issues of FL and overcome the resource constraints of clients, we investigate a novel paradigm in which heterogeneous clients learn uniquely designed models with different architectures, and transfer knowledge to the server to train a larger server model that in turn helps to enhance client models. For efficient knowledge transfer between client models and server model, we propose FedHKT, a Hierarchical Knowledge Transfer framework for FL. The main idea of FedHKT is to allow clients with similar data distributions to collaboratively learn to specialize in certain classes, then the specialized knowledge of clients is aggregated to a super knowledge covering all specialties to train the server model, and finally the server model knowledge is distilled to client models. Specifically, we tailor a hybrid knowledge transfer mechanism for FedHKT, where the model parameters based and knowledge distillation (KD) based methods are respectively used for client-edge and edge-cloud knowledge transfer, which can harness the pros and evade the cons of these two approaches in learning performance and resource efficiency. Besides, to efficiently aggregate knowledge for conducive server model training, we propose a weighted ensemble distillation scheme with server-assisted knowledge selection, which aggregates knowledge by its prediction confidence, selects qualified knowledge during server model training, and uses selected knowledge to help improve client models. Extensive experiments demonstrate the superior performance of FedHKT compared to state-of-the-art baselines.

Deploying deep convolutional neural network (CNN) to perform video analytics at edge poses a substantial system challenge, as running CNN inference incurs a prohibitive cost in computational resources. Model partitioning, as a promising approach, splits CNNs and distributes them to multiple edge devices in closer proximity to each other for serial inferences, however, it causes considerable cross-edge delay for transmitting intermediate feature maps. To overcome this challenge, we present ResMap, a new edge video analytics framework that significantly improves the cross-edge transmission and flexibly partitions the CNNs. Briefly, by exploiting the sparsity of the intermediate raw or residual feature map, ResMap effectively removes the redundant transmission, thereby decreasing the cross-edge transmission delay. In addition, ResMap incorporates an Online Data-Aware Scheduler to regularly update the CNN partitioning scheme so as to adapt to the time-varying edge runtime and video content. We have implemented ResMap fully based on COTS hardware, and the experimental results show that ResMap reduces the intermediate feature map volume by 14.93-46.12% and improves the average processing time by 17.43-30.6% compared to other alternative designs.

The separation of compute and storage in modern cloud services eases the deployment of general applications. However, with the development of accelerators such as GPU/TPU, Deep Learning (DL) training is suffering from potential IO bottlenecks when loading data from storage clusters. Therefore, DL training jobs need to either create local cache in the compute cluster to reduce the bandwidth demands or scale up the IO capacity with higher bandwidth cost. It is full of challenges to choose the best strategy due to the heterogeneous cache/IO preference of DL models, shared dataset among multiple jobs and dynamic GPU scaling of DL training. In this work, we exploit the job characteristics based on their training throughput, dataset size and scalability. For fixed GPU allocation of jobs, we propose CBA to minimize the training cost with a closed-form approach. For clusters that can automatically scale the GPU allocations of jobs, we extend CBA to AutoCBA to support diverse job utility functions and improve social welfare within a limited budget. Extensive experiments with production traces validate that CBA and AutoCBA can reduce IO cost and improve total social welfare by up to 20.5% and 2.27×, respectively, over the state-of-the-art schedulers for DL training.

Tile-based streaming and super resolution are two representative technologies adopted to improve bandwidth efficiency of immersive video steaming. The former allows selective download of contents in the user viewport by splitting the video into multiple independently decodable tiles. The latter leverages client-side computation to reconstruct the received video into higher quality using advanced neural network models. In this work, we propose CASE, a collaborated adaptive streaming and enhancement framework for mobile immersive videos, which integrates super resolution with tile-based streaming to optimize user experience with dynamic bandwidth and limited computing capability. To coordinate the video transmission and reconstruction in CASE, we identify and address several key design issues including unified video quality assessment, computation complexity model for super resolution, and buffer analysis considering the interplay between transmission and reconstruction. We further formulate the quality-of-experience (QoE) maximization problem for mobile immersive video streaming and propose a rate adaptation algorithm to make the best decisions for download and for reconstruction based on the Lyapunov optimization theory. Extensive evaluation results validate the superiority of our proposed approach, which presents stable performance with considerable QoE improvement, while enabling trade-off between playback smoothness and video quality.

The massive MIMO gain for wireless communication has been greatly hindered by the feedback overhead of channel state information (CSI) growing linearly with the number of antennas. Recent efforts leverage the DNN-based encoder-decoder framework to exploit correlations within the CSI matrix for better CSI compression. However, existing works have not fully exploited the unique features of CSI, resulting in an unsatisfactory performance under high compression ratios and sensitivity to multipath effects. Instead of treating CSI as common 2D matrices like images, we reveal the intrinsic stripe-based correlation across the CSI matrix. Driven by this insight, we propose CSI-StripeFormer, a stripe-aware encoder-decoder framework to exploit the unique stripe feature for better CSI compression. We design a lightweight encoder with asymmetric convolution kernels to capture various shape features. We further incorporate novel designs tailored for stripe features, including a novel hierarchical Transformer backbone in the decoder and a hybrid attention mechanism to extract and fuse correlations in angular and delay domains. Our evaluation results show that our system achieves an over 7dB channel reconstruction gain under a high compression ratio of 64 in multipath-rich scenarios, significantly superior to current state-of-the-art approaches. This gain can be further improved to 17dB given the extended embedded dimension of our backbone.

Mobile edge caching (MEC) allows edge devices to cache popular contents and deliver them to end-users directly, which can effectively alleviate increasing backbone loads and improve end-users’ quality of service. Peer content sharing (PCS) enables edge devices to share the cached contents with others, and can further increase the caching efficiency. While many efforts have been made to content caching or sharing technologies, it remains open to study the complicated technical and economic interplay between both technologies. In this paper, we propose a joint MEC-PCS framework, and focus on capturing the strategic interactions between different types of edge devices. Specifically, we model their interactions as a non-cooperative game, where each device (player) can choose to be an agent (who caches and shares contents with others) or a requester (who doesn’t cache but requests contents from others) of each content. We analyze the existence and uniqueness of the game equilibrium systematically under the generic usage-based pricing (for PCS). To address the incomplete information issue, we further design a behavior rule that allows players to achieve the equilibrium via a dynamic learning algorithm. Simulations show that the joint MEC-PCS framework can reduce the total system cost by 60%, compared with the benchmark pure caching system without PCS.

Online optimization with memory costs has many real-world applications, where sequential actions are made without knowing the future input. Nonetheless, the memory cost couples the actions over time, adding substantial challenges. Conventionally, this problem has been approached by various expert-designed online algorithms with the goal of achieving bounded worst-case competitive ratios, but the resulting average performance is often unsatisfactory. On the other hand, emerging machine learning (ML) based optimizers can improve the average performance, but suffer from the lack of worst-case performance robustness. In this paper, we propose a novel expert-robustified learning (ERL) approach, achieving both good average performance and robustness. More concretely, for robustness, ERL introduces a novel projection operator that robustifies ML actions by utilizing an expert online algorithm; for average performance, ERL trains the ML optimizer based on a recurrent architecture by explicitly considering downstream expert robustification. We prove that, for any λ ≥ 1, ERL can achieve λ-competitive against the expert algorithm and λ•C-competitive against the optimal offline algorithm (where C is the expert’s competitive ratio). Additionally, we extend our analysis to a novel setting of multi-step memory costs. Finally, our analysis is supported by empirical experiments for an energy scheduling application.

We revisit the online dynamic acknowledgment problem. In the problem, a sequence of requests arrive over time to be acknowledged, and all outstanding requests can be satisfied simultaneously by one acknowledgement. The goal of the problem is to minimize the total request delay plus acknowledgement cost. This elegant model studies the trade-off between acknowledgement cost and waiting experienced by requests. The problem has been well studied and the tight competitive ratios have been determined. For this well-studied problem, we focus on how to effectively use machine-learned predictions to have better performance. We develop algorithms that perform arbitrarily close to the optimum with accurate predictions while concurrently having the guarantees arbitrarily close to what the best online algorithms can offer without access to predictions, thereby achieving simultaneous optimum consistency and robustness. This new result is enabled by our novel prediction error measure. No error measure was defined for the problem prior to our work, and natural measures failed due to the challenge that requests with different arrival times have different effects on the objective. We hope our ideas can be used for other online problems with temporal aspects that have been resisting proper error measures.

Recent literature advances motion sensors mounted on smartphones and AR/VR headsets to speech eavesdropping due to their sensitivity to subtle vibrations. The popularity of motion sensors in earphones has fueled a rise in their sampling rate, which enables various enhanced features. This paper investigates a new threat of eavesdropping via motion sensors of earphones by developing EarSpy, which builds on our observation that the earphone’s accelerometer can capture bone conduction vibrations (BCVs) and ear canal dynamic motions (ECDMs) associated with speaking; they enable EarSpy to derive unique information about the wearer’s speech. Leveraging a study on the motion sensor measurements captured from earphones, EarSpy gains abilities to disentangle the wearer’s live speech from interference caused by body motions and vibrations generated when the earphone’s speaker plays audio. To enable user-independent attacks, EarSpy involves novel efforts, including a trajectory instability reduction method to calibrate the waveform of ECDMs and a data augmentation method to enrich the diversity of BCVs. Moreover, EarSpy explores effective representations from BCVs and ECDMs, and develops a convolutional neural model with Connectionist Temporal Classification (CTC) to realize accurate speech recognition. Extensive experiments involving 14 participants demonstrate that EarSpy reaches a promising recognition for the wearer’s speech.

Network monitoring systems struggle with the issue that the measurement data is incomplete, with only a subset of origin-destination (OD) pairs or time slots observed, due to the high deployment and measurement cost. Recent studies show that the missing data can be inferred from partial measurements using neural network models and tensor methods. However, these recovery approaches fail to achieve accuracy, adaptability and high speed, simultaneously. In this paper, we propose RecMon, a deep learning-based data recovery system that satisfies the above three criteria. A global spatio-temporal attention mechanism and a data augmentation algorithm are proposed to improve the recovery accuracy. A semi-supervised learning-based scheme is devised for fast and effective model updates. We conduct extensive experiments on three real-world datasets to compare RecMon with four state-of-the-art methods in terms of online recovery performance. The experimental results show that RecMon can adapt to the latest state of the network and accurately recover network measurement data in less than 100 milliseconds. When 90% of the data is missing, the recovery accuracy of RecMon improves over the strongest baseline method by 22.7%, 16.0%, and 8.2% in the three datasets, respectively.

Federated learning (FL) enables distributed model training from local data collected by users. In distributed systems with constrained resources and potentially high dynamics, e.g., mobile edge networks, the efficiency of FL is an important problem. Existing works have separately considered different configurations to make FL more efficient, such as infrequent transmission of model updates, client subsampling, and compression of update vectors. However, an important open problem is how to jointly apply and tune these control knobs in a single FL algorithm, to achieve the best performance by allowing a high degree of freedom in control decisions. In this paper, we address this problem and propose FlexFL – an FL algorithm with multiple options that can be adjusted flexibly. Our FlexFL algorithm allows both arbitrary rates of local computation at clients and arbitrary amounts of communication between clients and the server, making both the computation and communication resource consumption adjustable. We prove a convergence upper bound of this algorithm. Based on this result, we further propose a stochastic optimization formulation and algorithm to determine the control decisions that (approximately) minimize the convergence bound, while conforming to constraints related to resource consumption. The advantage of our approach is also verified using experiments.