Network configurations in brownfield environments often degenerate into “append-only” artifacts whose original design intent has been lost to personnel churn and documentation decay. In this paper, we identify intent recovery as a distinct problem: given an observed network state of interest, the goal is to infer why it exists rather than merely what it does. We characterize this task as an ill-posed inverse problem, because the compilation from high-level intent to low-level configuration discards rich contextual information, making the inverse mapping inherently one-to-many. To resolve this ambiguity, we observe that the original design process leaves residual traces in surrounding operational artifacts. We propose Matt, a framework that regularizes the inference by mining and fusing three complementary dimensions of such residual context: Semantics (business hierarchy), Provenance (configuration structure), and History (evolutionary timeline). An ablation study on synthetic datasets calibrated to real campus features confirms that each dimension provides a unique, irreplaceable contribution, with the full pipeline achieving 0.71 Exact Match accuracy and 0.79 Intent F1 score.

Diffusion Transformers (DiTs) have shown remarkable performance in generating high-quality videos. However, the quadratic complexity of 3D full attention remains a bottleneck in scaling DiT training, especially with high-definition, lengthy videos, where it can consume up to 95% of processing time and demand specialized context parallelism.

Disaggregating the generation and training stages in RL is widely adopted to scale LLM post-training. There are two critical challenges here. First, the generation stage often becomes a bottleneck due to dynamic workload shifts and severe execution imbalances. Second, the decoupled stages result in diverse and dynamic network traffic patterns that strain the conventional static fabric.

With the rapid advancement of mobile technologies, including self-driving cars and drones, the deployment of mobile software has become increasingly complex. In this context, virtualization plays a pivotal role by simplifying service deployment through containers and enabling container orchestration plat forms to efficiently manage an expanding number of container clusters. This is achieved by leveraging standardized interfaces and minimizing resource optimization overhead. However, the use of distributed servers in mobile edge clusters introduces several challenges, such as bandwidth limitations, network performance fluctuations, and resource constraints, which complicate deployment in these dynamic and resource-constrained environments. In this paper, we rethink the layer-based structure, a fundamental container design, and analyze the challenges and potential of real edge platform traces. Consequently, we propose BREAK, an acceleration middleware for efficient container deployment. With the primary insight of enhancing layer-reuse and deriving benefits from it, we develop a co-design approach centered on layer structure for efficient deployment, ensuring backward compatibility: (i) a container image refactoring solution that optimizes efficiency while preserving the stack-of-layers structure, (ii) distributed shared layer-stack caches, dynamically optimized for collaborative container deployment among mobile edge clusters, (iii) a customized Kubernetes (K8s) scheduler extending awareness of network performance, disk space, and container layer cache for container placement, and (iv) a tailored storage-driver of the standard container runtime for efficient layer extraction. Results indicate that BREAK accelerates the deployment process by up to 2.1× and reduces redundant image size by up to 3.11× compared to the state-of-the-art approach.

Bodun Hu, Shuozhe Li, Saurabh Agarwal, Myungjin Lee, Akshay Jajoo, Jiamin Li, Le Xu, Geon-Woo Kim, Donghyun Kim, Hong Xu, Amy Zhang, Aditya Akella. Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2025.

Large language model (LLM)-based applications consist of both LLM and non-LLM components, each contributing to the end-to-end latency. Despite great efforts to optimize LLM inference, end-to-end workflow optimization has been overlooked. Existing frameworks employ coarse-grained orchestration with task modules, which confines optimizations to within each module and yields suboptimal scheduling decisions.

Network function (NF) offloading on SmartNICs has been widely used in modern data centers, offering benefits in host resource saving and programmability. Co-running NFs on the same SmartNICs can cause performance interference due to contention of onboard resources. To meet performance SLAs while ensuring efficient resource management, operators need mechanisms to predict NF performance under such contention. However, existing solutions lack SmartNIC-specific knowledge and exhibit limited traffic awareness, leading to poor accuracy for on-NIC NFs.

This paper presents a comprehensive analysis of diffusion model serving challenges in production cloud environments. We examine the unique computational patterns and resource requirements that distinguish diffusion model serving from traditional ML workloads, revealing fundamental systemlevel challenges from their multi-stage pipeline architectures. Our analysis is based on a dataset collected from a commercial image generation service processing 3.5 million requests across 300+ GPUs of production operation.

The capacity of Large Language Models (LLMs) to comprehend and reason over long contexts is pivotal for advancements in diverse fields. Yet, they still stuggle with capturing long-distance dependencies within sequences to deeply understand semantics. To address this issue, we introduce Query-aware Inference for LLMs (Q-LLM), a system designed to process extensive sequences akin to human cognition. By focusing on memory data relevant to a given query, Q-LLM can accurately capture pertinent information within a fixed window size and provide precise answers to queries. It doesn’t require extra training and can be seamlessly integrated with any LLMs. Q-LLM using LLaMA3 (QuickLLaMA) can read Harry Potter within 30s and accurately answer the questions. On widely recognized benchmarks, Q-LLM improved by 7.17% compared to the current state-of-the-art on LLaMA3, and by 3.26% on Mistral on the \infty-bench. In the Needle-in-a-Haystack and BABILong task, Q-LLM improved upon the current SOTA by 7.0% and 6.1%. Our code is in https://github.com/dvlab-research/Q-LLM.

Neural image compression, necessary in various machine-to-machine communication scenarios, suffers from its heavy encode-decode structures and inflexibility in switching between different compression levels. Consequently, it raises significant challenges in applying the neural image compression to edge devices that are developed for powerful servers with high computational and storage capacities. We take a step to solve the challenges by proposing a new transformer-based edge-computefree image coding framework called Easz. Easz shifts the computational overhead to the server, and hence avoids the heavy encoding and model switching overhead on the edge. Easz utilizes a patch-erase algorithm to selectively remove image contents using a conditional uniform-based sampler. The erased pixels are reconstructed on the receiver side through a transformer-based framework. To further reduce the computational overhead on the receiver, we then introduce a lightweight transformer-based reconstruction structure to reduce the reconstruction load on the receiver side. Extensive evaluations conducted on a realworld testbed demonstrate multiple advantages of Easz over existing compression approaches, in terms of adaptability to different compression levels, computational efficiency, and image reconstruction quality.

In recent years, developing compact and efficient large language models (LLMs) has emerged as a thriving area of research.Traditional Supervised Fine-Tuning (SFT), which relies on singular ground truth labels, often fails to capture token-level dependencies and linguistic diversity.To address these limitations, we propose a logits-based fine-tuning framework that integrates the strengths of supervised learning and knowledge distillation.Our approach constructs enriched training targets by combining teacher logits with ground truth labels, preserving both correctness and linguistic diversity.This ensures more reliable and effective training.We constructed a large-scale 1.2M logits dataset and trained a series of science-focused models.Experimental results demonstrate that our method achieves significant improvements, with accuracy gains of 18% on Mawps and 22.7% on TabMWP.Across nine widely used mathematical benchmarks, our method consistently outperforms prior SFT models, achieving an average improvement of 7.28%.Codes are available at https://github.com/dvlab- research/Logits-Based-Finetuning.

Runtime traffic analysis on programmable data-plane requires substantial human effort, and the high speed and complexity of dataplane often make human capacity the efficiency bottleneck. While existing work has proposed LLM-based approaches, they typically rely on offline network logs, failing to address the human capacity limitations in real-time environments. This paper explores the potential of leveraging evolving LLMs to mitigate these human-centric challenges in real physical dataplane. It outlines a novel framework called NetSophon, which features an LLM-based brain for efficient decision-making and an effective arm to manipulate and perceive the physical programmable dataplane. Through interactions among the brain, arm, and dataplane, NetSophon acts as a "super-copilot" for human operators, facilitating real-time dataplane traffic analysis at scale. A case study demonstrates NetSophon’s potential to assist human operators in interacting with dataplane.

Graph processing is crucial for unstructured-data-driven applications in various domains.In recent years, there has been a growing need to perform real-time analytics on largescale evolving graphs, which involves evaluating a graph query on a sequence of snapshots within a given time window.Some prior studies have explored utilizing persistent memory (PM) technologies, such as non-volatile memory, for efficient evolving graph analytics.However, the latest incremental processing designs fail to fully exploit the PM potential, suffering from severe read and write amplification during update ingestion and query evaluation.In this paper, we develop PIE, a PM-based incremental processing framework for fast and scalable evolving graph analytics.We first observe that leveraging CommonGraph, a recently proposed DRAM-based incremental approach that transforms costly deletions into additions, can significantly improve efficiency for evolving graph analytics in PM, although the direct adaptation introduces significant PM access inefficiencies.To enable PM-friendly incremental processing, PIE introduces a logical graph view abstraction that is detached from the physical storage to avoid extra PM writes, and a

Learn to Optimize (L2O) trains deep neural network-based solvers for optimization, achieving success in accelerating convex problems and improving non-convex solutions. However, L2O lacks rigorous theoretical backing for its own training convergence, as existing analyses often use unrealistic assumptions-a gap this work highlights empirically. We bridge this gap by proving the training convergence of L2O models that learn Gradient Descent (GD) hyperparameters for quadratic programming, leveraging the Neural Tangent Kernel (NTK) theory. We propose a deterministic initialization strategy to support our theoretical results and promote stable training over extended optimization horizons by mitigating gradient explosion. Our L2O framework demonstrates over 50% better optimality than GD and superior robustness over state-of-the-art L2O methods on synthetic datasets. The code of our method can be found from https://github.com/NetX-lab/MathL2OProof-Official.

Reliability is essential for ensuring efficiency in LLM training. However, many real-world reliability issues remain difficult to resolve, resulting in wasted resources and degraded model performance. Unfortunately, today's collective communication libraries operate as black boxes, hiding critical information needed for effective root cause analysis.

We study resource allocation and task scheduling for mobile artificial intelligence generated content (AIGC) in a three-layer cloud-edge-device network. Escalating industry demand for computational resources presents significant challenges in resource allocation and optimization, particularly for edge-side AIGC, which faces high computational costs and requires advanced techniques for efficient model deployment on mobile devices. Optimal resource allocation in mobile AIGC networks is naturally formulated into a 0-1 ILP, which is proven NP-hard. We reformulate the problem into both its Comp-Exp and dual forms. Then, we design an online auction framework online AIGC task scheduling (OATS) to optimize decisions on instances and time schedules, maximizing social welfare for the AIGC ecosystem. Our analysis demonstrates that OATS achieves high social welfare through appropriate bid acceptance and resource allocation. Simulation results corroborate the theoretical analysis, showcasing the efficacy of our online algorithms.

Thanks to advances in deep learning techniques, Human Pose Estimation (HPE) has achieved significant progress in natural scenarios. However, these models perform poorly in artificial scenarios such as painting and sculpture due to the domain gap, constraining the development of virtual reality and augmented reality. With the growth of model size, retraining the whole model on both natural and artificial data is computationally expensive and inefficient. Our research aims to bridge the domain gap between natural and artificial scenarios with efficient tuning strategies. Leveraging the potential of language models, we enhance the adaptability of traditional pose estimation models across diverse scenarios with a novel framework called VLPose. VLPose leverages the synergy between language and vision to extend the generalization and robustness of pose estimation models beyond the traditional domains. Our approach has demonstrated improvements of 2.26% and 3.74% on HumanArt and MSCOCO, respectively, compared to state-of-the-art tuning strategies.

In the domain of very-large-scale integration (VLSI) design, the accuracy of prerouting timing prediction is of paramount importance for ensuring the performance and reliability of integrated circuits. Traditional methods based on machine learning necessitate the availability of extensive and high-quality datasets. However, this requirement poses significant challenges for advanced technology nodes due to the laborious and time-intensive nature of data preparation. To address this critical issue, we introduce a novel transfer learning framework that leverages data from preceding technology nodes to facilitate learning and prediction on the target node. Our methodology commences with the disentanglement and alignment of timing path features across different nodes, ensuring the preservation and effective translation of intrinsic timing path properties. Subsequently, we employ a Bayesian-based model to predict the arrival times of individual timing paths. This model is particularly adept at managing the high-variability inherent in arrival times and exhibits strong generalization capabilities to novel design scenarios. Moreover, we propose a new algorithm to reweight the preceding node data during training by estimating their transferability through the cell type distribution. We validate the efficacy of our proposed framework through comprehensive experimental evaluations, demonstrating successful transfer learning from 130 or 45 to 7-nm technology nodes. The results underscore the potential of our approach to significantly mitigate the dependency on extensive data preparation while maintaining high accuracy in timing prediction for cutting-edge VLSI designs.

Federated learning (FL) is increasingly adopted to combine knowledge from clients in training without revealing their private data. In order to improve the performance of different participants, personalized FL has recently been proposed. However, considering the non-independent and identically distributed (non-IID) data and limited bandwidth at clients, the model performance could be compromised. In reality, clients near each other often tend to have similar data distributions. In this work, we train the personalized edge-based model in the client-edge-server FL. While considering the differences in data distribution, we fully utilize the limited bandwidth resources. To make training efficient and accurate at the same time, An intuitive idea is to learn as much useful knowledge as possible from other edges and reduce the accuracy loss incurred by non-IID data. Therefore, we devise Grouping Hierarchical Personalized Federated Learning (GHPFL). In this framework, each edge establishes physical connections with multiple clients, while the server physically connects with edges. It clusters edges into groups and establishes client-edge logical connections for synchronization. This is based on data similarities that the nodes actively identify, as well as the underlying physical topology. We perform a large-scale evaluation to demonstrate GHPFL’s benefits over other schemes.

Congestion control (CC) plays a pivotal role in low-latency interactive video streaming such as cloud gaming. However, existing end-to-end CC methods often cause self-induced network queuing. As a result, they may largely delay video frame transmission and undermine the user’s quality of experience. In this paper, we present a new, practical CC algorithm namedPudicathat strives to achieve near-zero queuing delay and high link utilization while respecting cross-flow fairness. Pudica introduces several judicious approaches to utilize the paced frame to probe the bandwidth utilization ratio (BUR) instead of bandwidth itself. By leveraging BUR estimations, Pudica designs a holistic bitrate adjustment policy to balance low queuing, efficiency, and fairness. We conducted thorough and comprehensive evaluations in real production networks. In comparison to the state-of-the-art methods, Pudica reduces the average and tailed frame delay by 3.1$\times$and 5.1$\times$, respectively. Meanwhile, it increases the frame bitrate by 12.1%. Pudica has been deployed in a large-scale cloud gaming platform, currently serving millions of players.

Containers are widely embraced for their deployment and performance benefits over virtual machines. Yet, for many data-intensive applications in containerized clouds, bulky data transfers may impose performance issues. In particular, communication across co-located containers on the same host incurs large overheads in memory copy and the kernel’s TCP stack. Existing solutions such as shared-memory networking and RDMA have their own limitations, including insufficient memory isolation and limited scalability. This paper presents PipeDevice, a new system for low overhead intra-host container communication. PipeDevice follows a hardware-software co-design approach — it offloads data forwarding entirely onto hardware, which accesses application data in hugepages on the host, thereby eliminating CPU overhead from memory copy and TCP processing. PipeDevice preserves memory isolation and scales well to connections, making it deployable in public clouds. Isolation is achieved by allocating dedicated memory to each connection from hugepages. To achieve high scalability, PipeDevice stores the connection states entirely in host DRAM and manages them in software. Evaluation with a prototype implementation on commodity FPGA shows that for delivering 80Gbps across containers PipeDevice saves 63.2% CPU compared to kernel TCP stack, and 40.5% over FreeFlow. PipeDevice provides salient benefits to applications. For example, we port baidu-allreduce to PipeDevice and obtain$\sim 2.2\times $gains in allreduce throughput.

Deduplication compresses backup data by identifying and removing duplicate blocks. However, deduplication cannot detect when two blocks are very similar, which opens up opportunities for further data reduction using delta compression. Most existing works find similar blocks by characterizing each block by a set of features and matching similar blocks using coarse-grained super-features. If two blocks share a super-feature, delta compression only needs to store their delta for the new block.

Learning to optimize (L20) is an emerging technique to solve mathematical optimization problems with learning-based methods. Although with great success in many real-world scenarios such as wireless communications, computer networks, and electronic design, existing L2O works lack theoretical demonstration of their performance and robustness in out-of-distribution (OOD) scenarios. We address this gap by providing comprehensive proofs. First, we prove a sufficient condition for a robust L2O model with ho-mogeneous convergence rates over all In-Distribution (InD) instances. We assume an L2O model achieves robustness for an InD scenario. Based on our proposed methodology of aligning OOD problems to InD problems, we also demonstrate that the L2O model's convergence rate in OOD scenarios will deteriorate by an equation of the L2O model's input features. Moreover, we propose an L2O model with a concise gradient-only feature construction and a novel gradient-based history modeling method. Numerical simulation demonstrates that our proposed model outperforms the state-of-the-art baseline in both InD and OOD scenar-ios and achieves up to 10 × convergence speedup. The code of our method can be found from https://github.com/NetX-lab/GoMathL2O-Official.

Inverse lithography technology (ILT) plays a crucial role in optical proximity correction, tending to generate curvilinear masks for optimal process windows. Traditional curvilinear mask manufacturing involves fracturing into rectangles, requiring expensive mask write times. A novel E-beam mask writer that writes variable radius circles per shot significantly reduces the shot count for curvilinear masks. To exploit this mask writer's benefits, we present two methods to generate circular fracturing-aware masks. The first one converts pixel-based masks from existing ILT methods into circle-based masks using predefined rules. The second one integrates circular constraints into the ILT process, generating circle-based masks directly via optimization. Extensive experimental results validate both approaches' effectiveness.

In VLSI design, accurate pre-routing timing prediction is paramount. Traditional machine learning-based methods require extensive data, posing challenges for advanced technology nodes due to the time-consuming data preparation. To mitigate this issue, we propose a novel transfer learning framework that uses data from previous nodes for learning on the target node. Our method initially disentangles and aligns timing path features across different nodes, then predicts each path's arrival time employing a Bayesian-based model capable of handling highly variable arrival time and generalizing to new designs. Experimental results on transfer learning from 130nm to 7nm nodes validate our method's effectiveness.

Delta compression attracts many researchers' interest for its high efficiency in eliminating redundant data. It identifies a similar block for the incoming block and stores only the differences between them. The key challenge lies in detecting suitable similar blocks. Existing approaches have their limitations. Hash-based solutions like NTransform miss many similar blocks due to the high similarity detection threshold, while complex-threshold solutions like DeepSketch and Palantir have high computation overhead.

In times when ground infrastructure can be disrupted by conflicts or natural events, the use of Unmanned Aerial Vehicle (UAV) trajectories for network services has become a crucial backup plan. Yet, many current methods don't fully optimize how UAVs are scheduled or allocate resources, resulting in less effective service. Our research aims to enhance social welfare by optimizing UAV scheduling and trajectory planning. To tackle this challenging problem, we first set up a non-convex linear programming issue and then restructure it into both its exponential and dual forms. We introduce a two-part solution. The$A_{OST}$algorithm manages task bids and UAV resource allocation, considering factors like bid values, resources, and task needs. It ranks tasks based on the value they bring. Next, the$A_{dual}$algorithm refines decisions on tasks and UAV planning by weighing task costs against benefits. Our analysis shows our method reaches a balance that boosts social welfare, ensuring the best task and resource decisions. Tests back up these claims, showing improvement in network service, and proving our method's practical value in maximizing social welfare during disruptions.

Register Transfer Level (RTL) code optimization is crucial for enhancing the efficiency and performance of digital circuits during early synthesis stages. Currently, optimization relies heavily on manual efforts by skilled engineers, often requiring multiple iterations based on synthesis feedback. In contrast, existing compiler-based methods fall short in addressing complex designs. This paper introduces RTLRewriter, an innovative framework that leverages large models to optimize RTL code. A circuit partition pipeline is utilized for fast synthesis and efficient rewriting. A multi-modal program analysis is proposed to incorporate vital visual diagram information as optimization cues. A specialized search engine is designed to identify useful optimization guides, algorithms, and code snippets that enhance the model's ability to generate optimized RTL. Additionally, we introduce a Cost-aware Monte Carlo Tree Search (C-MCTS) algorithm for efficient rewriting, managing diverse retrieved contents and steering the rewriting results. Furthermore, a fast verification pipeline is proposed to reduce verification cost. To cater to the needs of both industry and academia, we propose two benchmarking suites: the long Rewriter benchmark, targeting complex scenarios with extensive circuit partitioning, optimization trade-offs, and verification challenges, and the short Rewriter benchmark, designed for a wider range of scenarios and patterns. Our comparative analysis with established compilers such as Yosys and E-graph demonstrates significant improvements, highlighting the benefits of integrating large models into the early stages of circuit design. We provide our benchmarks at https://github.com/yaoxufeng/RTLRewriter-Bench.

A prominent challenge in serving requests for NLP tasks is handling the varying length of input texts. Existing solutions, such as uniform zero-padding and compiler support, suffer from either computational inefficiency or suboptimal latency. To address these practical issues, we propose an approach called polymorphing. Polymorphing involves creating and utilizing multiple runtimes of the model, each statically compiled with a different input length, to serve requests accordingly. This fine-grained use of statically-compiled runtimes reduces the overheads of zero-padding while improving latency performance compared to dynamic compilation. To practically realize polymorphing, we have developed an inference scheduling system, Arlo, which leverages the observed input length distribution to periodically allocate compute resources across multiple runtimes by solving an integer linear program. Upon request arrival, Arlo uses a multi-level queue-based heuristic to dispatch requests to the most suitable runtime instances, efficiently adapting to the dynamics of request length and instance load. Extensive testbed evaluations and large-scale simulations using production traces demonstrate Arlo’s promising potential. It achieves 23.7%–98.1% mean latency reductions compared to existing schemes while significantly reducing tail latency.

This work explores a Personalized Federated Learning (PFL) system with a central server, multiple edges and clients. Edges contain significant data distribution diversity and data scarcity. We design an auction-based online algorithm for dynamically selecting clients, who are motivated to connect with edges for model serving and participate in training for rewards. Our auction focuses on bids for model service usage, yet incorporates a reward mechanism to compute social welfare. This approach fosters enhanced collaboration between clients and edges. Through extensive simulation, we demonstrate that our algorithm substantially improves the usage of model serving requests from clients, showing an increase in social welfare with a low competitive ratio. The personalized models benefit from clients’ computational contributions and diverse datasets, while outperforming conventional FL frameworks in model accuracy. Our contributions offer a scalable, practical solution to PFL challenges, ensuring improved model performance and client engagement in a data-sensitive, reward-driven context.

Fiber cuts reduce network capacity and take a long time to fix in optical wide-area networks. It is important to select the best restoration plan that minimizes throughput loss by reconfiguring wavelengths on remaining healthy fibers for affected IP links. Recent work studies optimal restoration plan or ticket selection problem in traffic engineering (TE) in a one-shot setting of only one TE interval (5 minutes). Since fiber repair often takes hours, in this work, we extend to consider restoration ticket selection with traffic dynamics over multiple intervals.To balance restoration performance with reconfiguration overhead, we perform dynamic ticket selection every T time steps. We propose an end-to-end learning approach to solve this T-step ticket selection problem as a classification task, combining traffic trend extraction and ticket selection in the same learning model. It uses convolution LSTM network to extract temporal and spatial features from past demand matrices to determine the ticket most likely to perform well T steps down the road, without predicting future traffic or solving any TE optimization. Trace-driven simulation shows that our new TE system, Archie, reduces over 25% throughput loss and is over 3500x faster than conventional demand prediction approach, which requires solving TE many times.

Container technology has revolutionized service deployment, offering streamlined processes and enabling container orchestration platforms to manage a growing number of container clusters. However, the deployment of containers in distributed edge clusters presents challenges due to their unique characteristics, such as bandwidth limitations and resource constraints. Existing approaches designed for cloud environments often fall short in addressing the specific requirements of edge computing. Additionally, very few edge-oriented solutions explore fundamental changes to the container design, resulting in difficulties achieving backward compatibility.In this paper, we reevaluate the fundamental layer-based structure of containers. We identify that the proliferation of redundant files and operations within image layers hinders efficient container deployment. Drawing upon the crucial insight of enhancing layer reuse and extracting benefits from it, we introduce BREAK, a holistic approach centered on layer structure throughout the entire container deployment pipeline, ensuring backward compatibility. BREAK refactors image layers and proposes an edge-oriented cache solution to enable ubiquitous and shared layers. Moreover, it addresses the complete deployment pipeline by introducing a customized scheduler and a tailored storage driver. Our results demonstrate that BREAK accelerates the deployment process by up to 2.1× and reduces redundant image size by up to 3.11× compared to state-of-the-art approaches.

Solving the sum rate maximization problem for interference reduction in multi-cell multi-user multiple-input multiple-output (MIMO) wireless communication systems has been investigated for a decade. Several machine learning-assisted methods have been proposed under conventional sum rate maximization frameworks, such as the Weighted Minimum Mean Square Error (WMMSE) framework. However, existing learning-assisted methods suffer from a deficiency in parallelization, and their performance is intrinsically bounded by WMMSE. In contrast, we propose a structural learning-only framework from the abstraction of WMMSE. Our proposed framework increases the solvability of the original MIMO sum rate maximization problem by dimension expansion via a unitary learnable parameter matrix to create an equivalent problem in a higher dimension. We then propose a structural solution updating method to solve the higher dimensional problem, utilizing neural networks to generate the learnable matrix-multiplication parameters. We show that the proposed structural learning framework achieves lower complexity than WMMSE thanks to its parallel implementation. Simulation results under practical communication network settings demonstrate that our proposed learning-only framework achieves up to 98% optimality over state-of-the-art algorithms while providing up to 47× acceleration in various scenarios.

Federated Learning (FL) has surged in popularity, allowing machine learning models to be collaboratively trained using decentralized client data, all while upholding privacy and security standards. However, leveraging locally-stored data introduces challenges related to data heterogeneity. While many past studies have addressed this non-IID problem, they often overlook the dynamic nature of each individual client’s data or disrupt its continuous shift. In this paper, our emphasis is on the challenges posed by temporal data distribution shift alongside non-IID data across clients, a more prevalent yet complex situation in real-world FL. We propose to analytically capture the evolving nature of each local data distribution, by modeling them as a time-varying composite of multiple latent Gaussian distributions. We then employ the expectation maximization (EM) algorithm to deduce the distribution model parameters based on the prevailing observed training data, ensuring that the learned mixture proportion weights mirror a consistent trajectory. Additionally, by embedding an adaptive data partitioning method into the EM algorithm and using each partition to train a distinct sub-model, we realize an intuitive and novel personalized FL paradigm. This refines the FL training by exploiting the heterogeneity and temporal shifts of clients’ datasets. We derive analytical results to guarantee the convergence of our training method. Comprehensive tests across diverse datasets and distribution configurations also underscore our enhanced efficacy compared to several state-of-the-art.

Large amounts of time-series data need to be continually delivered from IoT devices to the cloud for real-time data analytics. The data delivery process is intrinsically slow and costly. Therefore, lots of work proposes various data reduction methods to accelerate it. Yet, they are either designed for the simple linear time-series data or computation-intensive, which is not suitable for the IoT devices with limited resources. In this paper, we propose Xender, a system to accelerate time-series data delivery. Xender consists of two key components: data sampler and data generator. Data sampler works on IoT devices to sample time-series data with low resource footprint, and data generator works on the cloud to efficiently generate data that significantly resembles the original. Besides, Xender can adapt to the dynamic characteristics of the time-series data with the content-aware mechanism, as well as the dynamic computation resources by supporting multiple data generation quality levels and using the anytime generation mechanism. We implement Xender and evaluate it with testbed experiments using six real-world datasets. The results show that it can significantly reduce data delivery time by 45.79% on average compared against existing schemes, and adapt to computation resources with up to 1014.40Mbps data generation throughput.

Various datacenter network (DCN) load balancing schemes have been proposed in the past decade. Unfortunately, most of these solutions designed for lossy DCNs do not work well for Priority Flow Control (PFC) enabled lossless DCNs, primarily due to the reason that the individual congestion signals used in these solutions, e.g., link load, queue length, Round Trip Time (RTT) and Explicit Congestion Notification (ECN), may not be able to correctly or timely reflect the hop-by-hop PFC pausing. This paper first reveals the above problems via extensive experiments, and then based on the insights learned, we present Proteus, a PFC-aware load balancing scheme that is resilient to PFC pausing by exploring a combination of multi-level congestion signals. At its heart, Proteus leverages RTT-level signals (i.e., RTT and link utilization) to detect path status for initial routing decision, and exploits sub-RTT level signal (i.e., cumulative sojourn time) to reflect instantaneous PFC pausing and make timely rerouting choices based on the idea of better-late-than-never. We have implemented Proteus in the hardware programmable switch. Our testbed experiments as well as large-scale simulations show that Proteus can effectively handle PFC pausing under realistic workloads and achieve up to 35%, 31%, 28%, 22% and 46%, 42%, 34%, 29% better average FCT and$99^{th}$percentile FCT than CONGA, DRILL, Hermes and MP-RDMA, respectively.

Federated learning allows edge devices to collaboratively train a global model without sharing their local private data. Yet, with limited network bandwidth at the edge, communication often becomes a severe bottleneck. In this paper, we find that it is unnecessary to always synchronize the full model in the entire training process, because many parameters already become mature (i.e., stable) prior to model convergence, and can thus be excluded from later synchronizations. This allows us to reduce the communication overhead without compromising the model accuracy. However, challenges are that the local parameters excluded from global synchronization may diverge on different clients, and meanwhile some parameters may stabilize only temporally. To address these challenges, we propose a novel scheme called Adaptive Parameter Freezing (APF), which fixes (freezes) the non-synchronized stable parameters in intermittent periods. Specifically, the freezing periods are tentatively adjusted in an additively-increase and multiplicatively-decrease manner—depending on whether the previously-frozen parameters remain stable in subsequent iterations. We also extend APF into APF# and APF++, which freeze parameters in a more aggressive manner to achieve larger performance benefit for large complex models. We implemented APF and its variants as Python modules with PyTorch, and extensive experiments show that APF can reduce data transfer amount by over 60%.

Multiple patterning lithography (MPL) has been widely adopted in advanced technology nodes to enhance lithography resolution. As layout decomposition for triple patterning lithography (TPL) and beyond is NP-hard, existing approaches formulate mathematical programming problems and leverage general-purpose solvers such as integer linear programming (ILP) and semidefinite programming (SDP) to trade off quality against runtime. With the aggressive increase in design complexity, existing approaches can no longer scale to solve complicated designs with high solution quality. In this paper, we propose a dedicated low-rank SDP algorithm for MPL decomposition with augmented Lagrangian relaxation and Riemannian optimization. Experimental results demonstrate that our method is 186×, 25×, and 12× faster than the state-of-the-art decomposition approaches with highly competitive solution quality.

Large language models, such as OpenAI's Chat-GPT, have demonstrated exceptional language understanding capabilities in various NLP tasks.Sparsely activated mixture-of-experts (MoE) has emerged as a promising solution for scaling models while maintaining a constant number of computational operations.Existing MoE model adopts a fixed gating network where each token is computed by the same number of experts.However, this approach contradicts our intuition that the tokens in each sequence vary in terms of their linguistic complexity and, consequently, require different computational costs.Little is discussed in prior research on the tradeoff between computation per token and model performance.This paper introduces adaptive gating in MoE, a flexible training strategy that allows tokens to be processed by a variable number of experts based on expert probability distribution.The proposed framework preserves sparsity while improving training efficiency.Additionally, curriculum learning is leveraged to further reduce training time.Extensive experiments on diverse NLP tasks show that adaptive gating reduces at most 22.5% training time while maintaining inference quality.Moreover, we conduct a comprehensive analysis of the routing decisions and present our insights when adaptive gating is used.

Organizations often build separate training and inference clusters for deep learning, and use separate schedulers to manage them. This leads to problems for both: inference clusters have low utilization when the traffic load is low; training jobs often experience long queuing due to a lack of resources. We introduce Lyra, a new cluster scheduler to address these problems. Lyra introduces capacity loaning to loan idle inference servers for training jobs. It further exploits elastic scaling that scales a training job's resource allocation to better utilize loaned servers. Capacity loaning and elastic scaling create new challenges to cluster management. When the loaned servers need to be returned, we need to minimize job preemptions; when more GPUs become available, we need to allocate them to elastic jobs and minimize the job completion time (JCT). Lyra addresses these combinatorial problems with principled heuristics. It introduces the notion of server preemption cost, which it greedily reduces during server reclaiming. It further relies on the JCT reduction value defined for each additional worker of an elastic job to solve the scheduling problem as a multiple-choice knapsack problem. Prototype implementation on a 64-GPU testbed and large-scale simulation with 15-day traces of over 50,000 production jobs show that Lyra brings 1.53x and 1.48x reductions in average queuing time and JCT, and improves cluster usage by up to 25%.

Various datacenter network (DCN) load balancing schemes have been proposed in the past decade. Unfortunately, most of these solutions designed for lossy DCNs do not work well for Priority Flow Control (PFC) enabled lossless DCNs, primarily due to the reason that the individual congestion signals used in these solutions, e.g., link load, queue length, Round Trip Time (RTT) and Explicit Congestion Notification (ECN), may not be able to correctly or timely reflect the hop-by-hop PFC pausing. This paper first reveals the above problems via extensive experiments, and then based on the insights learned, we present Proteus, a PFC-aware load balancing scheme that is resilient to PFC pausing by exploring a combination of multi-level congestion signals. At its heart, Proteus leverages RTT-Ievel signals (i.e., RTT and link utilization) to detect path status for initial routing decision, and exploits sub-RTT level signal (i.e., cumulative sojourn time) to reflect instantaneous PFC pausing and make timely rerouting choices based on the idea of better-late-than-never. We have implemented Proteus in the hardware programmable switch. Our testbed experiments as well as large-scale simulations show that Proteus can effectively handle PFC pausing under realistic workloads and achieve up to 35 %, 31 %, 28%, 22% and 46 %, 42 %, 34 %, 29 % better average FCT and 99thpercentile FCT than CONGA, DRILL, Hermes and MP-RDMA, respectively.

The proliferation of edge devices has pushed computing from the cloud to the data sources, and video analytics is among the most promising applications of edge computing. Running video analytics is compute- and latency-sensitive, as video frames are analyzed by complex deep neural networks (DNNs) which put severe pressure on resource-constrained edge devices. To resolve the tension between inference latency and resource cost, we present Polly, a cross-camera inference system that enables co-located cameras with different but overlapping fields of views (FoVs) to share inference results between one another, thus eliminating the redundant inference work for objects in the same physical area. Polly’s design solves two basic challenges of cross-camera inference: how to identify overlapping FoVs automatically, and how to share inference results accurately across cameras. Evaluation on NVIDIA Jetson Nano with a real-world traffic surveillance dataset shows that Polly reduces the inference latency by up to 71.4% while achieving almost the same detection accuracy with state-of-the-art systems.

3D object detection plays a pivotal role in many applications, most notably autonomous driving and robotics. These applications are commonly deployed on edge devices to promptly interact with the environment, and often require near real-time response. With limited computation power, it is challenging to execute 3D detection on the edge using highly complex neural networks. Common approaches such as offloading to the cloud induce significant latency overheads due to the large amount of point cloud data during transmission. To resolve the tension between wimpy edge devices and compute-intensive inference workloads, we explore the possibility of empowering fast 2D detection to extrapolate 3D bounding boxes. To this end, we present Moby, a novel system that demonstrates the feasibility and potential of our approach. We design a transformation pipeline for Moby that generates 3D bounding boxes efficiently and accurately based on 2D detection results without running 3D detectors. Further, we devise a frame offloading scheduler that decides when to launch the 3D detector judiciously in the cloud to avoid the errors from accumulating. Extensive evaluations on NVIDIA Jetson TX2 with real-world autonomous driving datasets demonstrate that Moby offers up to 91.9% latency improvement with modest accuracy loss over state of the art.

The gap between the stagnation of CPU power and the increase in network bandwidth has promoted a shift towards placing more computation on network hardware [16, 17]. Therefore, SmartNICs have become prevalent in data centers to serve various cloud applications, from network functions [15, 17, 22] to high-level applications like distributed applications and storage [14, 16, 18--21, 23].

Federated learning (FL) enables distributed clients to collectively train a global model without revealing their private data, and for efficiency clients synchronize their gradients periodically. However, this can lead to the inaccuracy in model convergence due to inconsistent data distributions among clients. In this work, we find that there is a strong correlation between FL accuracy loss and the synchronization frequency, and seek to fine tune the synchronization frequency at training runtime to make FL accurate and also efficient. Specifically, aware that under the FL privacy requirement only gradients can be utilized for making frequency tuning decisions, we propose a novel metric called gradient consistency, which can effectively reflect the training status despite the instability of realistic FL scenarios. We further devise a feedback-driven algorithm called Gradient-Instructed Frequency Tuning (GIFT), which adaptively increases or decreases the synchronization frequency based on the gradient consistency metric. We have implemented GIFT in PyTorch, and large-scale evaluations show that it can improve FL accuracy by up to 10.7% with a time reduction of 58.1%.

Flow scheduling and congestion control are two important techniques to reduce flow completion time in data center networks. While existing works largely treat them independently, the interactions between flow scheduling and congestion control are in general overlooked which leads to sub-optimal solutions, especially given that the link capacity is increasing faster than the switch port buffer size. In this paper, we presentFlash, a simple yet effective scheme that integrates scheduling and congestion control. Specifically,Flashputs forward a congestion-aware scheduling scheme to determine the priority of flows based on the latest network congestion extent and the flow’s bytes sent. Besides,Flashproposes a priority-based packet dropping scheme in switch port buffers and implements a priority-aware congestion control scheme. Experiment results show thatFlashhas superior performance: (1) it has 35.8% lower tail latency than PIAS and performs similar with pFabric in a 10G network without knowing the flow size, (2) in 100G networks with shallow buffers, the information agnosticFlashhas 6.8% lower average FCT than the information-aware pFabric, (3) it outperforms pFabric by 13.5% in FCT if flow size is also known toFlash.

Coflow scheduling is critical to data-parallel applications in data centers. While schemes like Varys can achieve optimal performance, they require a priori information about coflows which is hard to obtain in practice. Existing non-clairvoyant solutions like Aalo generalize least attained service (LAS) scheduling discipline to address this issue. However, they fail to identify the bottleneck flows in a coflow and tend to allocate excessive bandwidth to the non-bottleneck flows, leading to bandwidth wastage and inferior overall performance. To this end, we present Fai that strives to improve the overall coflow performance by accelerating the bottleneck flows without priori knowledge. Fai employs bottleneck-aware scheduling. It adopts loose coordination to update coflow priority and flow rates based on total bytes sent. In addition, Fai detects bottleneck flows based on a flow’s rate and bytes sent, and de-allocates bandwidth for other flows to match the bottleneck rate without affecting the coflow completion time (CCT). The saved bandwidth is then distributed among coflows according to their priority to improve overall performance. Testbed evaluation on a 40-node cluster shows that Fai improves average (P95) CCT by 1.73× (3.43×), compared to Aalo. Large-scale trace-driven simulations also show that Fai outperforms Aalo substantially.

In Priority Flow Control (PFC) enabled datacenter networks (DCNs), PFC is inevitably triggered due to bursty traffic even with end-to-end congestion control. Load balancing as a complementary mechanism to transport protocols can make rerouting decisions in time to alleviate PFC’s head-of-line (HoL) blocking problem. However, prior solutions designed for lossy DCNs do not work well in PFC-enabled networks, because the unreliable rerouting signals such as separate local queue length, round-trip time (RTT), explicit congestion notification (ECN), and link load cannot timely and correctly reflect PFC pausing.

Containers are prevalently adopted due to the deployment and performance advantages over virtual machines. For many containerized data-intensive applications, however, bulky data transfers may pose performance issues. In particular, communication across co-located containers on the same host incurs large overheads in memory copy and the kernel's TCP stack. Existing solutions such as shared-memory networking and RDMA have their own limitations, including insufficient memory isolation and limited scalability.

Short videos have received extraordinary success in recent years. To provide smooth playback and avoid rebuffering delay, prefetching upcoming videos is commonly used in cellular networks. Current prefetching designs fall short in dealing with bandwidth overhead, especially the exit overhead of downloaded but unconsumed chunks due to user exit. Measurement from a large short video platform shows that exit overhead accounts for up to 43.5% of bandwidth overhead. Thus we build Alfie, a bandwidth-efficient short video prefetching algorithm via reinforcement learning. Essentially Alfie adjusts prefetching based upon user viewing patterns in addition to network conditions. We demonstrate that Alfie outperforms the state of the art by up to 26.8% in overall performance while reducing the exit overhead by up to 84.9%.

In recent years, quantitative verification concerning network availability has received increasing attention due to its practical importance in network management. Existing work extends upon qualitative verification and tries to answer whether a network would have any link overload under failures and dynamic traffic. The simple yes-or-no question falls short of accurately characterizing the robustness of a network under uncertainties, which the operators are in dire need of. Thus, we argue that it is necessary to design a probabilistic framework to analyze network availability comprehensively. We propose Pita, a novel network analysis framework that outputs the overall probability of the network being unavailable under a range of failure scenarios and traffic demands. We formalize the problem and show that it is #P-hard which does not admit deterministic approximation solutions. We further develop an improved randomized approximation that exploits the structural property of our problem to reduce the computational cost of the so-called boundary oracle procedure, a key bottleneck of the approximation, without any accuracy loss. Evaluation with real topologies shows that Pita provides up to 2.25x speedup over state-of-the-art solutions, and can be effectively used in many network management tasks such as identifying high-risk failure scenarios, and aiding robust traffic engineering design.

Much effort has been devoted to improving the performance of network transmission. Yet, the impact of packet size which is limited by the 1500-byte maximum transmission unit (MTU) has not received adequate attention. Through comprehensive experiments, we find that jumbo frames which are commonly used as an alternate do not always yield the best performance under different transmission situations.In this paper, we elaborate on the limitations of the regular and jumbo frames and analyze how packet sizes affect network performance. Based on these, we present Adaptively Packet Sizing (APS), a dynamic packet size adjustment method that can be easily integrated into existing window-based congestion control algorithms. APS utilizes a machine learning method to predict the optimal packet size, which can minimize flow completion time (FCT) according to the instantaneous network condition. Besides, a packet size based priority mechanism is proposed to further improve the performance. We implement APS in both simulation and testbed environments. APS reduces the FCT by up to 50% and gains better performance in scenarios with various loss rates.

Power-of-d-choices (Pod) is a popular load balancing strategy, which has received much attention from both academia and industry. However, much prior work on Pod has focused on uniform tasks without priorities. In reality, tasks may have different priorities according to their service sensitivity, pricing, or importance to guarantee the quality of service (QoS). In this work, we distinguish two types of priorities in Pod: scheduling and service priorities. We propose Pod-SSP, which is a Pod algorithm with Scheduling and Service Priorities. To better understand the impact of priorities on the performance of tasks, we consider two simple variants of Pod-SSP: Pod with SCheduling Priorities (Pod-SCP) and Pod with SErvice Priorities (Pod-SEP). Utilizing mean-field approximation, we systematically study the performance of these protocols in the large-system regime. Our theoretical and simulation results show that high-priority tasks can have a more than 3x better delay relative to a system running the original Pod algorithm, and meanwhile, low-priority tasks only slightly sacrifice their delay.

On-boarding new devices into an existing SDN network is a pain for network operations (NetOps) teams, because much expert effort is required to bridge the gap between the configuration models of the new devices and the unified data model in the SDN controller. In this work, we present an assistant framework NAssim, to help NetOps accelerate the process of assimilating a new device into a SDN network. Our solution features a unified parser framework to parse diverse device user manuals into preliminary configuration models, a rigorous validator that confirm the correctness of the models via formal syntax analysis, model hierarchy validation and empirical data validation, and a deep-learning-based mapping algorithm that uses state-of-the-art neural language processing techniques to produce human-comprehensible recommended mapping between the validated configuration model and the one in the SDN controller. In all, NAssim liberates the NetOps from most tedious tasks by learning directly from devices' manuals to produce data models which are comprehensible by both the SDN controller and human experts. Our evaluation shows, NAssim can accelerate the assimilation process by 9.1x. In this process, we also identify and correct 243 errors in four mainstream vendors' device manuals, and release a validated and expert-curated dataset of parsed manual corpus for future research.

Network simulators are an essential tool for network operators, and can assist important tasks such as capacity planning, topology design, and parameter tuning. Popular simulators are all based on discrete event simulation, and their performance does not scale with the size of modern networks. Recently, deep-learning-based techniques are introduced to solve the scalability problem, but, as we show with experiments, they have poor visibility in their simulation results, and cannot generalize to diverse scenarios. In this work, we combine scalable and generalized continuous simulation techniques with discrete event simulation to achieve high scalability, while providing packet-level visibility. We start from a solid queueing-theoretic modeling of modern networks, and carefully identify the mathematically-intractable or computationally-expensive parts, only which are then modeled using deep neural networks (DNN). Dubbed DeepQueueNet, our approach combines prior knowledge of networks, and supports arbitrary topology and device traffic management mechanisms (given sufficient training data). Our extensive experiments show that DeepQueueNet achieves near-linear speedup in the number of GPUs, and its estimation accuracy for average and 99th percentile round-trip time outperforms existing end-to-end DNN-based performance estimators in all scenarios.

This paper presents a system called NetKernel that decouples the network stack from the guest virtual machine and offers it as an independent module. NetKernel represents a new paradigm where network stack can be managed as part of the virtualized infrastructure. It provides important efficiency benefits: By gaining control and visibility of the network stack, operators can perform network management more directly and flexibly, such as multiplexing VMs running different applications to the same network stack module to save CPU cores, and enforcing fair bandwidth sharing. Users also benefit from the simplified stack deployment and better performance: For example mTCP can be deployed without API change to support nginx natively, and shared memory networking can be readily enabled to improve performance of colocated VMs. Testbed evaluation using 100G NICs shows that NetKernel preserves the performance and scalability of both kernel and userspace network stacks, and provides the same isolation as the current architecture.

Network function virtualization (NFV) enables elastic scaling to middlebox deployment and management. Therefore, efficient stateful scaling is an important task because operators often need to shift traffic and the associated flow states across VNF instances to deal with time-varying loads. Existing NFV scaling methods, however, typically focus on one aspect of the scaling pipeline and does not offer an end-to-end scaling framework. This article presents ScaleFlux, a complete stateful scaling system that efficiently reduces flow-level latency and achieves near-optimal resource usage. ScaleFlux (1) monitors traffic load for each VNF instance and adopts a queue-based mechanism to detect load burstiness timely, (2) deploys a flow bandwidth predictor to predict flow bandwidth time-series with the ABCNN-LSTM model, and (3) schedules the necessary flow and state migration using the simulated annealing algorithm to achieve both flow-level latency guarantee and resource usage minimization. Testbed evaluation with a five-machine cluster shows that ScaleFlux reduces flow completion time by at least 8.7× for all the workloads and achieves near-optimal CPU usage during scaling.

The parameter server architecture is prevalently used for distributed deep learning. Each worker machine in a such system trains the complete model, which leads to a large amount of network data transfer between workers and servers. We empirically observe that the data transfer has a major impact on training time. We present a new distributed training system called Stanza to tackle this problem. Stanza exploits the fact that in many models such as convolution neural networks, most data exchange is attributed to the fully connected layers, while most computation is carried out in convolutional layers. Thus, we propose layer separation in distributed training: most nodes of the cluster train only the convolutional layers, while the rest train the fully connected layers. Gradients and parameters of the fully connected layers no longer need to be exchanged across the entire cluster, thereby substantially reducing the data transfer volume. We implement Stanza on PyTorch and evaluate its performance on Azure and EC2. Results show that Stanza accelerates training significantly over current parameter server systems: on EC2 instances with Tesla V100 GPU and 10Gb bandwidth for example, Stanza is 1.34x–13.9x faster for common deep learning models.

Federated learning allows edge devices to collaboratively train a global model by synchronizing their local updates without sharing private data. Yet, with limited network bandwidth at the edge, communication often becomes a severe bottleneck. In this paper, we find that it is unnecessary to always synchronize the full model in the entire training process, because many parameters gradually stabilize prior to the ultimate model convergence, and can thus be excluded from being synchronized at an early stage. This allows us to reduce the communication overhead without compromising the model accuracy. However, challenges are that the local parameters excluded from global synchronization may diverge on different clients, and meanwhile some parameters may stabilize only temporally. To address these challenges, we propose a novel scheme called Adaptive Parameter Freezing (APF), which fixes (freezes) the non-synchronized stable parameters in intermittent periods. Specifically, the freezing periods are tentatively adjusted in an additively-increase and multiplicatively-decrease manner, depending on if the previously-frozen parameters remain stable in subsequent iterations. We implemented APF as a Python module in PyTorch. Our extensive array of experimental results show that APF can reduce data transfer by over 60%.

In federated learning a global model is trained with training data geographically distributed over a number of clients. To reduce the communication cost over the expensive wide area network, clients complete multiple local iterations before synchronization. However, since the training data are non-iid, such infrequent synchronization would compromise the accuracy after model convergence. In order to tackle this problem, we propose Two-Dimensional Learning Rate Decay (2D-LRD) in this paper, which aims to improve the model performance by adaptively tuning the learning rate on two dimensions: round-dimension and iteration-dimension during the model training. That is, we gradually decrease the learning rate and decrease the learning rates of local iterations in a synchronization round with different speeds. Based on our experiments and analysis, we find that the sum of the inner product of round updates is a valuable signal for learning rate tuning. We perform evaluation and demonstrate that 2D-LRD can make great progress compared to the baseline scheme.

In software-defined networking (SDN) systems, it is a common practice to adopt a multi-controller design and control devolution techniques to improve the performance of the control plane. However, in such systems the decision-making for joint switch-controller association and control devolution often involves various uncertainties, e.g., the temporal variations of controller accessibility, and computation and communication costs of switches. In practice, statistics of such uncertainties are unattainable and need to be learned in an online fashion, calling for an integrated design of learning and control. In this article, we formulate a stochastic network optimization problem that aims to minimize time-average system costs and ensure queue stability. By transforming the problem into a combinatorial multi-armed bandit problem with long-term stability constraints, we adopt bandit learning methods and optimal control techniques to handle the exploration-exploitation tradeoff and long-term stability constraints, respectively. Through an integrated design of online learning and online control, we propose an effective Learning-Aided Switch-Controller Association and Control Devolution (LASAC) scheme. Our theoretical analysis and simulation results show that LASAC achieves a tunable tradeoff between queue stability and system cost reduction with a sublinear time-averaged regret bound over a finite time horizon.

Modern data analytics systems use long-running executors to run an application's entire DAG. Executors exhibit salient time-varying resource requirements. Yet, existing schedulers simply reserve resources for executors statically, and use the peak resource demand to guide executor placement. This leads to low utilization and poor application performance. We present Elasecutor, a novel executor scheduler for data analytics systems. Elasecutor dynamically allocates and explicitly sizes resources to executors over time according to the predicted time/varying resource demands. Rather than placing executors using their peak demand, Elasecutor strategically assigns them to machines based on a concept called dominant remaining resource to minimize resource fragmentation. Elasecutor further adaptively reprovisions resources in order to tolerate inaccurate demand prediction and reschedules tasks to deal with inadequate reprovisioning resources on one machine. Testbed evaluation on a 35-node cluster with our Spark-based prototype implementation shows that Elasecutor reduces makespan by more than 36% on average, and improves cluster utilization by up to 55% compared to existing work.

Data center networks need to provide low latency, especially at the tail, as demanded by many interactive applications. To improve tail latency, existing approaches require modifications to switch hardware and/or end-host operating systems, making them difficult to be deployed. We present the design, implementation, and evaluation of RepNet, an application layer transport that can be deployed today. RepNet exploits the fact that only a few paths among many are congested at any moment in the network, and applies simple flow replication to mice flows to opportunistically use the less congested path. RepNet has two designs for flow replication: (1) RepSYN, which only replicates SYN packets and uses the first connection that finishes TCP handshaking for data transmission, and (2) RepFlow which replicates the entire mice flow. We implement RepNet on node.js, one of the most commonly used platforms for networked interactive applications. node's single threaded event-loop and non-blocking I/O make flow replication highly efficient. Performance evaluation on a real network testbed and in Mininet reveals that RepNet is able to reduce the tail latency of mice flows, as well as application completion times, by more than 50 percent.

DNN inference is becoming prevalent for many real-world applications. Current machine learning frameworks usually schedule inference tasks with the goal of optimizing throughput under predictable workloads and task arrival patterns. Yet, inference workloads are becoming more dynamic with bursty queries generated by various video analytics pipelines which run expensive inference only on a fraction of video frames. Thus it is imperative to optimize the completion time of these unpredictable queries and improve customer experience.

In recent years, distributed computing frameworks, such as Hadoop MapReduce and Spark, are widely used for big data processing. With the explosive growth of the amount of data, companies tend to store intermediate data of the shuffle phase on disk instead of memory. Therefore, intensive network and disk I/O are both involved in the shuffle phase. To optimize the overhead of the shuffle phase, we propose OPS, an open-source distributed computing shuffle management system based on Spark, which provides an independent shuffle service for Spark. By using early-merge and early-shuffle strategy, OPS alleviates the I/O overhead in the shuffle phase and efficiently schedules the I/O and computing resources. OPS also proposes a slot-based scheduling algorithm to predict and calculate the optimal scheduling result of the reduce task. Besides, OPS provides a taint-redo strategy to ensure the fault tolerance of computing jobs. We evaluated the performance of OPS on a 100-node Amazon AWS EC2 cluster. Overall, OPS optimizes the overhead of shuffle by nearly 50%. In the test cases of HiBench, OPS improves end-to-end completion time by nearly 30% on average.

A distributed control plane is more scalable and robust in software defined networking. This paper focuses on controller load balancing using packet-in request redirection, that is, given the instantaneous state of the system, determining whether to redirect packet-in requests for each switch, such that the overall control plane response time (CPRT) is minimized. To address the above problem, we propose a framework based on Lyapunov optimization. First, we use the drift-plus-penalty algorithm to combine CPRT minimization problem with controller capacity constraints, and further derive a non-linear program, whose optimal solution is obtained with brute force using standard linearization techniques. Second, we present a greedy strategy to efficiently obtain a solution with a bounded approximation ratio. Third, we reformulate the program as a problem of maximizing a non-monotone submodular function subject to matroid constraints. We implement a controller proto-type for packet-in request redirection, and conduct trace-driven simulations to validate our theoretical results. The results show that our algorithms can reduce the average CPRT by 81.6% compared to static controller-switch assignment, and achieve a 3× improvement in maximum controller capacity violation ratio.

In software-defined networking (SDN) systems, it is a common practice to adopt a multi-controller design and control devolution techniques to improve the performance of the control plane. However, in such systems the decision making for joint switch-controller association and control devolution often involves various uncertainties, e.g., the temporal variations of controller accessibility, and computation and communication costs of switches. In practice, statistics of such uncertainties are unattainable and need to be learned in an online fashion, calling for an integrated design of learning and control. In this paper, we formulate a stochastic network optimization problem that aims to minimize time-average system costs and ensure queue stability. By transforming the problem into a combinatorial multi-armed bandit problem with long-term stability constraints, we adopt bandit learning methods and optimal control techniques to handle the exploration-exploitation tradeoff and long-term stability constraints, respectively. Through an integrated design of online learning and online control, we propose an effective Learning-Aided Switch-Controller Association and Control Devolution (LASAC) scheme. Our theoretical analysis and simulation results show that LASAC achieves a tunable tradeoff between queue stability and system cost reduction with a sublinear regret bound over a finite time horizon.

Existing traffic engineering (TE) solutions perform well for software defined network (SDN) in average cases. However, during peak hours, bursty traffic spikes are challenging to handle, because it is difficult to react in time and guarantee high performance even after failures with limited flow entries.We propose TED, a scalable TE system that can guarantee high throughput in peak hours. TED can quickly compute a group of maximum number of edge-disjoint paths for each ingress-egress switch pair. Such paths are suitable for well connected networks with unique edge capacity and TED is not limited to use only these paths. We design two methods to select paths under the limit of flow table size. We then input the selected paths to TED to minimize the maximum link utilization. In case of large traffic matrix making the maximum link utilization larger than 1, we input the utilization and the traffic matrix to the optimization of maximizing overall throughput under a new constrain. Thus we obtain a realistic traffic matrix, which has the maximum overall throughput and guarantees no traffic starvation. Experiments show that TED has much better performance for heavily-loaded SDN and has 10% higher probability to satisfy all (> 99.99%) the traffic after a single link failure for G-Scale topology than Smore under the same limit of flow table size.

For software-defined networking (SDN) systems, to enhance the scalability and reliability of control plane, existing solutions adopt either multi-controller design with static switch-controller association, or static control devolution by delegating certain request processing back to switches. Such solutions can fall short in face of temporal variations of request traffics, incurring considerable local computation costs on switches and their communication costs to controllers. So far, it still remains an open problem to develop a joint online scheme that conducts dynamic switch-controller association and dynamic control devolution. In addition, the fundamental benefits of predictive scheduling to SDN systems still remain unexplored. In this paper, we identify the non-trivial trade-off in such a joint design and formulate a stochastic network optimization problem which aims to minimize time-averaged total system costs and ensure long-term queue stability. By exploiting the unique problem structure, we devise a predictive online switch-controller association and control devolution (POSCAD) scheme, which solves the problem through a series of online distributed decision making. Theoretical analysis shows that without prediction, POSCAD can achieve near-optimal total system costs a tunable trade-off for queue stability. With prediction, POSCAD can achieve even better performance with shorter latencies. We conduct extensive simulations to evaluate POSCAD. Notably, with mild-value of future information, POSCAD incurs a significant reduction in request latencies, even when faced with prediction errors.

Offchain networks emerge as a promising solution to address the scalability challenge of blockchain. Participants make payments through offchain networks instead of committing transactions on-chain. Routing is critical to the performance of offchain networks. Existing solutions use either static routing with poor performance or dynamic routing with high overhead to obtain the dynamic channel balance information. In this paper, we propose Flash, a new dynamic routing solution that leverages the unique transactions characteristics in offchain networks to strike a better tradeoff between path optimality and probing overhead. By studying the traces of real offchain networks, we find that the payment sizes are heavy-tailed, and most payments are highly recurrent. Flash thus differentiates the treatment of elephant payments from that of mice payments. It uses a modified max-flow algorithm for elephant payments to find paths with sufficient capacity, and strategically routes the payment across paths to minimize the transaction fees. Mice payments are sent directly by looking up a routing table with a few precomputed paths to reduce probing overhead. Testbed experiments and trace-driven simulations show that Flash improves the success volume of payments by up to 2.3x compared to the state-of-the-art routing algorithm.

Similarity join of two datasets P and Q is a primitive operation that is useful in many application domains. The operation involves identifying pairs (p, q), in the Cartesian product of P and Q such that (p, q) satisfies a stipulated similarity condition. In a high-dimensional space, an approximate similarity join based on locality-sensitive hashing (LSH) provides a good solution while reducing the processing cost with a predictable loss of accuracy. A distributed processing framework such as MapReduce allows the handling of large and high-dimensional datasets. However, network cost frequently turns into a bottleneck in a distributed processing environment, thus resulting in a challenge of achieving faster and more efficient similarity join [2]. This paper focuses on collision counting LSH-based similarity join in MapReduce and proposes a network-efficient solution called C2Net to improve the utilization of MapReduce combiners. The solution uses two graph partitioning schemes: (i) minimum spanning tree for organizing LSH buckets replication; and (ii) spectral clustering for runtime collision counting task scheduling. Experiments have shown that, in comparison to the state of the art, the proposed solution is able to achieve 20% data reduction and 50% reduction in shuffle time.

In software-defined networking (SDN) systems, the scalability and reliability of the control plane still remain as major concerns. Existing solutions adopt either multi-controller designs or control devolution back to the data plane. The former requires a flexible yet efficient switch-controller association mechanism to adapt to workload changes and potential failures, while the latter demands timely decision making with low overheads. The integrate design for both is even more challenging. Meanwhile, the dramatic advancement in machine learning techniques has boosted the practice of predictive scheduling to improve the responsiveness in various systems. Nonetheless, so far little work has been conducted for SDN systems. In this paper, we study the joint problem of dynamic switch-controller association and control devolution, while investigating the benefits of predictive scheduling in SDN systems. We propose POSCAD, an efficient, online, and distributed scheme that exploits predictive future information to minimize the total system cost and the average request response time with queueing stability guarantee. Theoretical analysis and trace-driven simulation results show that POSCAD requires only mild-value of future information to achieve a near-optimal system cost and near-zero average request response time. Further, POSCAD is robust against mis-prediction to reduce the average request response time.

Similarity join of two datasets$P$and$Q$is a primitive operation that is useful in many application domains. The operation involves identifying pairs$(p,q)$, in the Cartesian product of$P$and$Q$such that$(p,q)$satisfies a stipulated similarity condition. In a high-dimensional space, an approximate similarity join based on locality-sensitive hashing (LSH) provides a good solution while reducing the processing cost with a predictable loss of accuracy. A distributed processing framework such as MapReduce allows the handling of large and high-dimensional datasets. However, network cost estimation frequently turns into a bottleneck in a distributed processing environment, thus resulting in a challenge of achieving faster and more efficient similarity join. This paper focuses on collision counting LSH-based similarity join in MapReduce and proposes a network-efficient solution called C2Net to improve the utilization of MapReduce combiners. The solution uses two graph partitioning schemes: (i)minimum spanning treefor organizing LSH buckets replication; and (ii)spectral clusteringfor runtime collision counting task scheduling. Experiments have shown that, in comparison to the state of the art, the proposed solution is able to achieve 20 percent data reduction and 50 percent reduction in shuffle time.

Traffic engineering (TE) is a fundamental task in networking. Conventionally, traffic can take any path connecting the source and destination. Emerging technologies such as segment routing, however, use logical paths that are composed of shortest paths going through a predetermined set of middlepoints in order to reduce the flow table overhead of TE implementation. Inspired by this, in this paper, we introduce the problem of node-constrained TE, where the traffic must go through a set of middlepoints, and study its theoretical fundamentals. We show that the general node-constrained TE that allows the traffic to take any path going through one or more middlepoints is NP-hard for directed graphs but strongly polynomial for undirected graphs, unveiling a profound dichotomy between the two cases. We also investigate a variant of node-constrained TE that uses only shortest paths between middlepoints, and prove that the problem can now be solved in weakly polynomial time for a fixed number of middlepoints, which explains why existing work focuses on this variant. Yet, if we constrain the end-to-end paths to be acyclic, the problem can become NP-hard. An important application of our work concerns flow centrality, for which we are able to derive complexity results. Furthermore, we investigate the middlepoint selection problem in general node-constrained TE. We introduce and study group flow centrality as a solution concept, and show that it is monotone but not submodular. Our work provides a thorough theoretical treatment of node-constrained TE and sheds light on the development of the emerging node-constrained TE in practice.

Network failures are common in wide area networks (WANs). Failure recovery in a software-defined WAN takes minutes or longer, as the controller needs to calculate a new traffic engineering solution and update the forwarding rules across all switches. This severely degrades application performance. Existing reactive and proactive approaches inevitably lead to transient congestion or bandwidth underutilization and impair the efficiency of running the expensive WANs. We present Sentinel, a novel failure recovery system for traffic engineering in software-defined WANs. Sentinel pre-computes and installs backup tunnels to accelerate failure recovery. When a link fails, switches locally redirect traffic to backup tunnels and recover immediately in the data plane, thus substantially reducing the transient congestion compared to reactive rescaling. On the other hand, Sentinel completely avoids the bandwidth headroom required by existing proactive approaches. Extensive experiments on Mininet and numerical simulations show that similar to state-of-the-art FFC, Sentinel reduces congestion by 45% compared with rescaling, and its algorithm runs much faster than FFC. Sentinel only introduces a small number of additional forwarding rules and can be readily implemented on today’s Openflow switches.

Data center networks demand high-performance, robust, and practical data plane load balancing protocols. Despite progress, existing work falls short of meeting these requirements. We design, analyze, and evaluate Luopan, a novel sampling based load balancing protocol that overcomes these challenges. Luopan operates at flowcell granularity similar to Presto. It periodically samples a few paths for each destination switch and directs flowcells to the least congested one. By being congestion-aware, Luopan improves flow completion time (FCT), and is more robust to topological asymmetries compared to Presto. The sampling approach simplifies the protocol and makes it much more scalable for implementation in large-scale networks compared to existing congestion-aware schemes. We provide analysis to show that Luopan's periodic sampling has the same asymptotic behavior as instantaneous sampling: taking 2 random samples provides exponential improvements over 1 sample. We conduct comprehensive packet-level simulations with production workloads. The results show that Luopan consistently outperforms state-of-the-art schemes in large-scale topologies. Compared to Presto, Luopan with 2 samples improves the 99.9%ile FCT of mice flows by up to 35 percent, and average FCT of medium and elephant flows by up to 30 percent. Luopan also performs significantly better than Local Sampling with large asymmetry.

The SDN control plane needs to frequently update the data plane as the network conditions change. Since each switch updates its flow table independently and asynchronously, the transition of data plane state - if done directly from the initial to the final stage - may result in serious flash congestion. Prior work strives to find a congestion-free update plan with multiple stages, each with the property that there will be no congestion independent of the update order. Yet congestion-free update may prevent the network from being fully utilized. It also requires solving a series of LP which is time-consuming. In this paper, we propose congestion-minimizing update and focus on two general problems: The first is to find routing at each intermediate stage that minimizes transient congestion for a given number of intermediate stages. The second is to find the minimum number of intermediate stages and an update plan for a given maximum level of transient congestion. We formulate them as two optimization programs and prove their hardness. We propose a set of algorithms to find the update plan in a scalable manner. Extensive experiments with Mininet show that our solution reduces update time by 50 percent and saves control overhead by 38 percent compared to prior work.

Modern data analytics systems use long-running executors to run an application's entire DAG. Executors exhibit salient time-varying resource requirements. Yet, existing schedulers simply reserve resources for executors statically, and use the peak resource demand to guide executor placement. This leads to low utilization and poor application performance.

We propose Bohr, a similarity aware geo-distributed data analytics system that minimizes query completion time. The key idea is to exploit similarity between data in different data centers (DCs), and transfer similar data from the bottleneck DC to other sites with more WAN bandwidth. Though these sites have more input data to process, these data are more similar and can be more efficiently aggregated by the combiner to reduce the intermediate data that needs to be shuffled across the WAN. Thus our similarity aware approach reduces the shuffle time and in turn the query completion time (QCT).

Network function virtualization (NFV) aims to run software network functions (NFs) in commodity servers. As CPU is general-purpose hardware, one has to use many CPU cores to handle complex packet processing at line rate. Owing to its performance and programmability, FPGA has emerged as a promising platform for NFV. However, the programmable logic blocks on an FPGA board are limited and expensive. Implementing the entire NFs on FPGA is thus resource-demanding. Further, FPGA needs to be reprogrammed when the NF logic changes which can take hours to synthesize the code. It is thus inflexible to use FPGA to implement the entire NFV service chain. We present dynamic hardware library (DHL), a novel CPU-FPGA co-design framework for NFV with both high performance and flexibility. DHL employs FPGA as accelerators only for complex packet processing. It abstracts accelerator modules in FPGA as a hardware function library, and provides a set of transparent APIs for developers. DHL supports running multiple concurrent software NFs with distinct accelerator functions on the same FPGA and provides data isolation among them. We implement a prototype of DHL with Intel DPDK. Experimental results demonstrate that DHL greatly reduces the programming efforts to access FPGA, brings significantly higher throughput and lower latency over CPU-only implementation, and minimizes the CPU resources.

State-of-the-art inter-datacenter WANs rely on software defined networking (SDN) to orchestrate their data transmission. Optimization requires frequent network update operations to switch forwarding tables. When scheduling inter-datacenter WANs, the utility of services should be respected. Yet, existing network update approaches do not respect network utility and could result in performance degradation during the network update procedure. Further, the update causes not only performance degradation, but also the degradation period is unnecessarily prolonged. In this paper we propose Hermes, a utility-aware network update system. We aim to find a rate limiting scheme for update which maximizes the sum of service utility, while ensuring the congestion-free property during the update. We propose an optimization framework for the maximum utility network update problem (MUP). MUP is NP-hard and a series of algorithms are developed to solve it. Extensive simulation and testbed experiments with a prototype demonstrate that Hermes can increase the total utility by 80% compared to state-of-the-art. At the same time, it reduces the total update time and control overhead by 40% and 55%, respectively.

With the evolution of Network Function Virtual-izaiton (NFV), enterprises are increasingly outsourcing their network functions to the cloud. However, using virtualized network functions (VNFs) to provide flexible services in today's cloud is challenging due to the inherent difficulty in intelligently scaling VNFs to cope with traffic fluctuations. To best utilize cloud resources, NFV providers need to dynamically scale the VNF deployments and reroute traffic demands for their customers. Since most existing work is reactive in nature, we seek a proactive approach to provision new instances for overloaded VNFs ahead of time based on the estimated flow rates. We formulate the VNF provisioning problem in order that the cost incurred by inaccurate prediction and VNF deployment is minimized. In the proposed online algorithm, we first employ an efficient online learning method which aims at minimizing the error in predicting the service chain demands. We then derive the requested instances with adaptive processing capacities and call two other algorithms for new instance assignment and service chain rerouting, respectively, while achieving good competitive ratios. The joint online algorithm is proven to provide good performance guarantees by both theoretical analysis and trace-driven simulation.

Network faults like link or switch failures can cause heavy congestion and packet loss. Traffic engineering systems need a lot of time to detect and react to such faults, which results in significant recovery times. Recent work either preinstalls a lot of backup paths in the switches to ensure fast rerouting or proactively prereserves bandwidth to achieve fault resiliency. Our idea agilely reacts to failures in the data plane while eliminating the preinstallation of backup paths. We propose Kuijia, a robust traffic engineering system for data center WANs, which relies on a novel failover mechanism in the data plane called rate rescaling. The victim flows on failed tunnels are rescaled to the remaining tunnels and enter lower priority queues to avoid performance impairment of aboriginal flows. Real system experiments show that Kuijia is effective in handling network faults and significantly outperforms the conventional rescaling method.

As the critical infrastructure for supporting Internet and cloud computing services, massive geo-distributed data centers are notorious for their huge electricity appetites and carbon footprints. Nonetheless, a lesser-known fact is that data centers are also “thirsty”: to operate data centers, millions of gallons of water are required for cooling and electricity production. The existing water-saving techniques primarily focus on improved “engineering” (e.g., upgrading to air economizer cooling, diverting recycled/sea water instead of potable water) and do not apply to all data centers due to high upfront capital costs and/or location restrictions. In this paper, we propose a software-based approach towards water conservation by exploiting the inherent spatio-temporal diversity of water efficiency across geo-distributed data centers. Specifically, we propose a batch job scheduling algorithm, called WACE (minimization of WAter, Carbon and Electricity cost), which dynamically adjusts geographic load balancing and resource provisioning to minimize the water consumption along with carbon emission and electricity cost while satisfying average delay performance requirement. WACE can be implemented online without foreseeing the far future information and yields a total cost (incorporating electricity cost, water consumption and carbon emission) that is provably close to the optimal algorithm with lookahead information. Finally, we validate WACE through a trace-based simulation study and show that WACE outperforms state-of-the-art benchmarks: 25 percent water saving while incurring an acceptable delay increase. We also extend WACE to joint scheduling of batch workloads and delay-sensitive interactive workloads for further water footprint reduction in geo-distributed data centers.

Optical interconnects are emerging as a high bandwidth and low energy alternative to traditional electrical networks. However, most exiting designs put optical switching in the core layer due to issues, including limited scalability, potential bottleneck of the control plane, and high cost of the multi-wavelength switch. To this end, we propose Thor, a hybrid network architecture using optical interconnects as the main load bearing portion. It employs the hypercube topology and multi-hop circuit switching to enable server-level optical access, thus solving the scalability and connectivity limitations. Then, in order to build a faster control plane operating short-lived circuits in a large scale, Thor uses a distributed control system over the electrical network, with a new path setup mechanism capable of establishing multiple optical circuits concurrently. Moreover, Thor employs a novel optical switch design to utilize multiple wavelengths more efficiently. Our evaluation results show that Thor consumes at least 59% and 6% less power than existing electrical and optical designs. For performance, Thor is able to deliver 90% bisection bandwidth of a non-blocking network and reduce the end-to-end latency significantly. Finally, by separately delivering mice and elephant flows, Thor achieves salient improvements in average flow completion times compared with existing approaches.

As one type of the most popular cloud storage services, OpenStack Swift and its follow-up systems replicate each object across multiple storage nodes and leverageobject sync protocolsto achieve high reliability andeventual consistency. The performance of object sync protocols heavily relies on two key parameters:$r$(number of replicas for each object) and$n$(number of objects hosted by each storage node). In existing tutorials and demos, the configurations are usually$r=3$and$n<1,000$by default, and the sync process seems to perform well. However, we discover in data-intensive scenarios, e.g., when$r>3$and$n\gg 1,000$, the sync process is significantly delayed and produces massive network overhead, referred to as thesync bottleneck problem. By reviewing the source code of OpenStack Swift, we find that its object sync protocol utilizes a fairly simple and network-intensive approach to check the consistency among replicas of objects. Hence in a sync round, the number of exchanged hash values per node is$\Theta (n\times r)$. To tackle the problem, we propose a lightweight and practical object sync protocol,LightSync, which not only remarkably reduces the sync overhead, but also preserves high reliability and eventual consistency. LightSync derives this capability from three novel building blocks: 1)Hashing of Hashes, which aggregates all the$h$hash values of each data partition into a single but representative hash value with the Merkle tree; 2)Circular Hash Checking, which checks the consistency of different partition replicas by only sending the aggregated hash value to the clockwise neighbor; and 3)Failed Neighbor Handling, which properly detects and handles node failures with moderate overhead to effectively strengthen the robustness of LightSync. The design of LightSync offers provable guarantee on reducing the per-node network overhead from$\Theta (n\times r)$to$\Theta (\frac{n}{h})$. Furthermore, we have implemented LightSync as an open-source patch and adopted it to OpenStack Swift, thus reducing the sync delay by up to 879$\times$and the network overhead by up to 47.5$\times$.

Data center networks carry a mix of flows, some with deadlines and some without. Existing mix-flow transport designs assume prior knowledge of flow sizes, which may not hold in practice. Without such information, mix-flow scheduling becomes particularly challenging due to (1) the lack of precise rate control of deadline flows with minimal impact on non-deadline flows; (2) difficulty in assigning priority to both two types of flows.

The tenant network stack is implemented inside the virtual machines in today's public cloud. This legacy architecture presents a barrier to protocol stack innovation due to the tight coupling between the network stack and the guest OS. In particular, it causes many deployment troubles to tenants and management and efficiency problems to the cloud provider. To address these issues, we articulate a vision of providing the network stack as a service. The central idea is to decouple the network stack from the guest OS, and offer it as an independent entity implemented by the cloud provider. This re-architecting allows tenants to readily deploy any stack independent of its kernel, and the provider to offer meaningful SLAs to tenants by gaining control over the network stack. We sketch an initial design called NetKernel to accomplish this vision. Our preliminary testbed evaluation with a prototype shows the feasibility and benefits of our idea.

In software-defined networking (SDN), as data plane scale expands, scalability and reliability of the control plane have become major concerns. To mitigate such concerns, two kinds of solutions have been proposed separately. One is multi-controller architecture, i.e., a logically centralized control plane with physically distributed controllers. The other is control devolution, i.e., delegating control of some flows back to switches. Most of existing solutions adopt either static switch-controller association or static devolution, which may not adapt well to the traffic variation, leading to high communication costs between switches and controller, and high computation costs of switches. In this paper, we propose a novel scheme to jointly consider both solutions, i.e., we dynamically associate switches with controllers and dynamically devolve control of flows to switches. Our scheme is an efficient online algorithm that does not need the statistics of traffic flows. By adjusting some parameter V, we can make a trade-off between costs and queue backlogs. Theoretical analysis and extensive simulations show that our scheme yields much lower costs and latency compared to static schemes, and balanced loads among controllers.

Middleboxes are widely deployed to perform various network functions to ensure security and improve performance. The recent trend of Network Function Virtualization (NFV) makes it easy for operators to deploy software implementations of these network functions on commodity servers. However, virtual network functions consume different amounts of resources when processing packets. Thus a multi-resource load balancing (MRLB) mechanism is needed to efficiently utilize server resources. MRLB problem in the context of NFV is fundamentally different from multi-resource allocation problems, as well as traditional single-resource load balancing and multi-resource load balancing problems in task scheduling. In this paper, we tackle the MRLB problem in NFV by first proposing dominant load-the load of the most stressed resource on a server-as the load balancing metric. We then formulate the MRLB problem as an optimization to minimize the maximum dominant load of all NFV servers given the demand. Based on proximal Jacobian ADMM, we propose an efficient algorithm to solve the problem in large scale settings. Through extensive trace-driven simulations and prototype experiments on a testbed, we show that our MRLB algorithm with dominant load performs significantly better and faster than benchmarking algorithms.

Network functions virtualization (NFV) is increasingly adopted by telecommunications (telecos) service providers for cost savings and flexible management. However, deploying virtual network functions (VNFs) in geo-distributed central offices (COs) is not straightforward. Unlike most existing centralized schemes in clouds, VNFs of a service chain usually need to be deployed in multiple COs due to limited resource capacity and uneven setup cost at various locations. To ensure the Quality of Service of service chains, a key problem for service providers is to determine where a VNF should go, in order to achieve cost-efficiency and load balancing of both computing and bandwidth resources, across all selected COs. To this end, we present a framework of CO Selection (CS) and VNF Assignment (VA) for distributed deployment of NFV. Specifically, we first select a set of COs that minimizes the communication cost among the selected COs. Then, we employ a shadow-routing based approach, which minimizes the maximum of appropriately defined CO utilizations, to jointly solve the VNF-CO and VNF-server assignment problem. Simulations demonstrate the effectiveness of CS algorithm, and asymptotic optimality, scalability and high adaptivity of the VNF assignment approach.

Software defined networking is increasingly prevalent in data center networks for it enables centralized network configuration and management. However, since switches are statically assigned to controllers and controllers are statically provisioned, traffic dynamics may cause long response time and incur high maintenance cost. To address these issues, we formulate the dynamic controller assignment problem (DCAP) as an online optimization to minimize the total cost caused by response time and maintenance on the cluster of controllers. By applying the randomized fixed horizon control framework, we decompose DCAP into a series of stable matching problems with transfers, guaranteeing a small loss in competitive ratio. Since the matching problem is NP-hard, we propose a hierarchical two-phase algorithm that integrates key concepts from both matching theory and coalitional games to solve it efficiently. Theoretical analysis proves that our algorithm converges to a near-optimal Nash stable solution within tens of iterations. Extensive simulations show that our online approach reduces total cost by about 46%, and achieves better load balancing among controllers compared with static assignment.

Data center networks often use multi-rooted Clos topologies to provide a large number of equal cost paths between two hosts. Thus, load balancing traffic among the paths is important for high performance and low latency. However, it is well known that ECMP-the de facto load balancing scheme-performs poorly in data center networks. The main culprit of ECMP's problems is its congestion agnostic nature, which fundamentally limits its ability to deal with network dynamics. We propose Expeditus, a novel distributed congestion-aware load balancing protocol for general 3-tier Clos networks. The complex 3-tier Clos topologies present significant scalability challenges that make a simple per-path feedback approach infeasible. Expeditus addresses the challenges by using simple local information collection, where a switch only monitors its egress and ingress link loads. It further employs a novel two-stage path selection mechanism to aggregate relevant information across switches and make path selection decisions. Testbed evaluation on Emulab and large-scale ns-3 simulations demonstrate that, Expeditus outperforms ECMP by up to 45% in tail flow completion times (FCT) for mice flows, and by up to 38% in mean FCT for elephant flows in 3-tier Clos networks.

In this paper, we introduce a unified framework for studying various cloud traffic management problems, ranging from geographical load balancing to backbone traffic engineering. We first abstract these real-world problems as a multi-facility resource allocation problem, and then present two distributed optimization algorithms by exploiting the special structure of the problem. Our algorithms are inspired by Alternating Direction Method of Multipliers (ADMM), enjoying a number of unique features. Compared to dual decomposition, they converge with non-strictly convex objective functions; compared to other ADMM-type algorithms, they not only achieve faster convergence under weaker assumptions, but also have lower computational complexity and lower message-passing overhead. The simulation results not only confirm these desirable features of our algorithms, but also highlight several additional advantages, such as scalability and fault-tolerance.

Data center networks often use multi-rooted Clos topologies to provide a large number of equal cost paths between two hosts. Thus, load balancing traffic among the paths is important for high performance and low latency. However, it is well known that ECMP---the de facto load balancing scheme---performs poorly in data center networks. The main culprit of ECMP's problems is its congestion agnostic nature, which fundamentally limits its ability to deal with network dynamics.

Data center networks demand high-performance, robust, and practical data plane load balancing protocols. Despite progress, existing work falls short of satisfying these requirements. We design and evaluate Luopan, a novel sampling based load balancing protocol that overcomes these challenges. Luopan operates at flowcell granularity similar to Presto. It periodically samples a few paths to each destination switch and directs flowcells to the least congested one. By being congestion-aware, Luopan improves flow completion time (FCT), and is more robust to topological asymmetries compared to Presto. The sampling approach simplifies the protocol and makes it much more scalable for implementation in large-scale networks compared to existing congestion-aware schemes. We conduct comprehensive packet-level simulations with a production workload. The results show that Luopan consistently outperforms state-of-the-art schemes in large-scale symmetric and asymmetric topologies. Compared to Presto, Luopan with 2 samples improves the 99%ile FCT of mice flows by up to 45%, and average FCT of medium flows by ~20%.

We present Sentinel, a novel failure recovery system for traffic engineering that pre-computes and installs backup tunnels to improve the robustness of software defined wide area networks (WANs). When a link fails, switches locally redirect traffic to backup tunnels and recover immediately in the data plane, thus substantially reducing the transient congestion compared to reactive rescaling. On the other hand Sentinel completely avoids the bandwidth headroom required by existing proactive approaches like FFC, and improves efficiency of operating the expensive WAN. We make several technical contributions in designing Sentinel. We formulate traffic engineering with backup tunnels (TE-BT) as optimization programs. We propose an approximation algorithm to efficiently solve the problem. We further present a concrete design and implementation of the system based on Openflow group tables for backup tunnels. Extensive experiments on Mininet and numerical simulations show that similar to FFC, Sentinel reduces congestion by 45% compared with rescaling, and its algorithm runs much faster than FFC. Sentinel only introduces a small number of additional forwarding rules and can be readily implemented on today's Openflow switches.

Software defined networking is becoming increasingly prevalent in data center networks for its programmability that enables centralized network configuration and management. However, since switches are statically assigned to controllers, traffic dynamics cause load imbalance among the controllers. As a result, some controllers are not fully utilized, while switches connected to overloaded controllers may experience long response times. In this paper, we consider dynamic controller assignment so as to minimize the average response time of the control plane. We formulate this problem as a stable matching problem with transfers, and propose a hierarchically two-phase algorithm that integrates key concepts from both matching theory and coalitional games to solve it efficiently. Theoretical analysis proves that our algorithm converges to a near-optimal Nash stable solution within tens of iterations. Extensive simulations show that our approach reduces response time by about 86%, and achieves better load balancing among controllers compared to static assignment.

Middleboxes are prevalent in today's enterprise and data center networks. Network function virtualization (NFV) is a promising technology to replace dedicated hardware middleboxes with virtualized network functions (VNFs) running on commodity servers. However, no prior study has examined the energy efficiency of different NFV implementations. In this paper, we conduct a measurement study on the power efficiency of software data planes, the virtual I/O and the software middleboxes, which are important parts of the NFV implementations. We run two popular software middleboxes (Snort and Bro) on three common software data planes (i.e., DPDK-OVS, Click Modular Router and Netmap). Our results show significant differences on power among those different NFV implementations. We analyze the underlying design choices and give implications on how to build more power efficient NFV implementations.

4G/3G Networks have been widely deployed around the world to provide high wireless bandwidth for mobile users. However, the achievable 3G/4G bandwidth is still much lower than their theoretic maximum. Signal strengths and available backhaul capacities may vary significantly at different locations and times, often leading to unsatisfactory performance. Band-width aggregation, which uses multiple interfaces concurrently for data transfer, is a readily deployable solution. Specifically, Multi-Path TCP (MPTCP) has been advocated as a promising approach for leveraging multiple source-destination paths simultaneously in the transport layer. In this paper, we investigate the efficiency of an MPTCP-based bandwidth aggregation frame-work based on extensive measurements. In particular, we evaluate the gain for bandwidth aggregation across up to 4 cellular operators' networks, with respect to factors such as time, user location, data size, aggregation proxy location and congestion control algorithm. Our measurement studies reveal that (1) bandwidth aggregation in general improves the cellular network bandwidth experienced by mobile users, but the performance gain is significant only for bandwidth-intensive delay-tolerant flows, (2) the effectiveness of aggregation depends on many network factors, including QoS of individual cellular interfaces and the location of aggregation proxy, (3) contextual factors, including the time of day and the mobility of a user, also affect the aggregation performance.

Recently, datacenter carbon emission has become an emerging concern for the cloud service providers. Previous works are limited on cutting down the power consumption of datacenters to defuse such a concern. In this paper, we show how the spatial and temporal variabilities of the electricity carbon footprint can be fully exploited to further green the cloud running on top of geographically distributed datacenters. Specifically, we first verify that electricity cost minimization conflicts with carbon emission minimization, based on an empirical study of several representative geo-distributed cloud services. We then jointly consider the electricity cost, service level agreement (SLA) requirement, and emission reduction budget. To navigate such a three-way tradeoff, we take advantage of Lyapunov optimization techniques to design and analyze a carbon-aware control framework, which makes online decisions on geographical load balancing, capacity right-sizing, and server speed scaling. Results from rigorous mathematical analysis and real-world trace-driven evaluation demonstrate the effectiveness of our framework in reducing both electricity cost and carbon emission.

To maximize data center network utilization, the SDN control plane needs to frequently update the data plane as the network conditions change. Since each switch updates its flow table independently and asynchronously, the state transition -- if done directly from the initial to the final stage -- may result in serious flash congestion and packet loss. Prior work strives to find a congestion-free update plan with multiple stages, each with the property that there will be no congestion independent of the update order. Yet congestion-free update requires part of the link capacity to be left vacant and decreases utilization of the expensive network infrastructure. Further, it involves solving a series of LP, which is slow and does not scale well. In this paper, we study the more general problem of minimizing transient congestion during network update, given the number of intermediate stages. This exposes the tradeoff between update speed and transient congestion, and allows an operator to navigate a broader design space for performing network update. We formulate the minimum congestion update problem (MCUP) as an optimization program and prove its hardness. We propose an approximation algorithm and a greedy improvement algorithm to find the update sequence in an efficient and scalable manner. Extensive experiments with Mininet show that our solution reduces update time by 50% and saves control overhead by 30% compared to state of the art.

Lately, for geo-distributed data centers, a workload management approach that routes user requests to locations with cheaper and cleaner electricity has been developed to reduce energy consumption and cost. We consider two key aspects that have not been explored in this approach. First, through empirical studies, we find that the energy efficiency of cooling systems depends critically on the ambient temperature, which exhibits significant geographical diversity. Temperature diversity can be used to reduce the cooling energy overhead. Second, energy consumption comes from not only interactive workloads driven by user requests, but also delay tolerant batch workloads that run at the back-end. The elastic nature of batch workloads can be exploited to further reduce the energy cost. In this paper, we propose to make workload management temperature aware. We formulate the problem as a joint optimization of request routing for interactive workloads and capacity allocation for batch workloads. We develop a distributed algorithm based on an m-block alternating direction method of multipliers (ADMM) algorithm that extends the classical two-block algorithm. We prove the convergence and rate of convergence results under general assumptions. Through trace-driven simulations, we find that our approach consistently provides 15-20 percent cooling energy reduction, and 5-20 percent overall cost reduction over existing methods.

We advocate to create a spot Internet transit market, where transit is sold using the under-utilized backbone capacity at a lower price. The providers can improve profit by capitalizing the perishable capacity, and customers can buy transit on demand without a minimum commitment level for elastic traffic, and as a result improve their surplus (i.e., utility gains). We conduct a systematic study of the economical benefits of spot transit both theoretically and empirically. We propose a simple analytical framework with a general demand function, and solve the pricing problem to maximize the expected profit, taking into account the potential revenue loss of regular transit when spot transit traffic hikes. We prove the price advantage of spot transit, as well as the profit and surplus improvements for tier-1 ISPs and customers, respectively. Using real-world price data and traffic statistics of six IXPs with more than 1,000 ISPs, we evaluate spot transit and show that significant financial benefits can be achieved in both absolute and relative terms, robust to parameter values.

Network virtualization is a promising technology to enable multiple architectures to run on a single network. However, virtualization also introduces additional security vulnerabilities that may be exploited by attackers. It is necessary to ensure that the security requirements of virtual networks are met by the physical substrate, which however has not received much attention thus far. This paper represents an early attempt to consider the security issue in virtual network embedding, the process of mapping virtual networks onto physical nodes and links. We model the security demands of virtual networks by proposing a simple taxonomy of abstractions, which is enough to meet the variations of security requirements. Based on the abstraction, we formulate security-aware virtual network embedding as an optimization problem, proposing objective functions and mathematical constraints which involve both resource and security restrictions. Then a heuristic algorithm is developed to solve this problem. Our simulation results indicate its high efficiency and effectiveness.

Short TCP flows that are critical for many interactive applications in data centers are plagued by long flows and head-of-line blocking in switches. Hash-based load balancing schemes such as ECMP aggravate the matter and result in long-tailed flow completion times (FCT). Previous work on reducing FCT usually requires custom switch hardware and/or protocol changes. We propose RepFlow, a simple yet practically effective approach that replicates each short flow to reduce the completion times, without any change to switches or host kernels. With ECMP the original and replicated flows traverse distinct paths with different congestion levels, thereby reducing the probability of having long queueing delay. We develop a simple analytical model to demonstrate the potential improvement. Further, we conduct NS-3 simulations and Mininet implementation and show that RepFlow provides 50%-70% speedup in both mean and 99-th percentile FCT for all loads, and offers near-optimal FCT when used with DCTCP.

Current multipath routing solution in data centers relies on ECMP to distribute traffic among all equal-cost paths. It is well known that ECMP suffers from two deficiencies. ECMP does not differentiate between elephant and mice flows, creates head-of-line blocking for mice flows in the egress port buffer, and results in long tail latency. Further it does not fully utilize available bandwidth due to hash collision among elephant flows. We propose TinyFlow, a simple yet effective approach that remedies both problems. TinyFlow changes the traffic characteristics of data center networks to be amenable to ECMP by breaking elephants into mice. In a network with a large number of mice flows only, ECMP naturally balances load and performance is improved. We conduct NS-3 simulations and show that TinyFlow provides 20%-40% speedup in both mean and 99-th percentile FCT for mice, and about 40% throughput improvement for elephants.

This work seeks to address two questions in cooperative OFDMA networks: First, how network coding based cooperative diversity can be exploited effectively when overhearing is not readily available. Second, how to realize various forms of gains available, including multi-user diversity, cooperative diversity, and network coding. The main contribution of this paper is an unifying network utility maximization framework that jointly considers relay assignment, relay strategy selection, channel assignment and power allocation. We formulate the optimization problem both with and without XOR-CD, a simple XOR-assisted cooperative diversity scheme. We show that the optimization of physical layer resource allocation with XOR-CD is equivalent to a weighted 3-set packing problem, which is NP-complete, and can be efficiently solved with provably the best approximation factor. Without XOR-CD, the problem reduces to a weighted bipartite matching problem which can be optimally solved.

Many cloud services are running on geographically distributed datacenters for better reliability and performance. We consider the emerging problem of joint request mapping and response routing with distributed datacenters in this paper. We formulate the problem as a general workload management optimization. A utility function is used to capture various performance goals, and the location diversity of electricity and bandwidth costs are realistically modeled. To solve the large-scale optimization, we develop a distributed algorithm based on the alternating direction method of multipliers (ADMM). Following a decomposition-coordination approach, our algorithm allows for a parallel implementation in a datacenter where each server solves a small sub-problem. The solutions are coordinated to find an optimal solution to the global problem. Our algorithm converges to near optimum within tens of iterations, and is insensitive to step sizes. We empirically evaluate our algorithm based on real-world workload traces and latency measurements, and demonstrate its effectiveness compared to conventional methods.

Recently, data center carbon emission has become an emerging concern for the cloud service providers. Previous works are limited on cutting down the power consumption of the data centers to defuse such a concern. In this paper, we show how the spatial and temporal variabilities of the electricity carbon footprint can be fully exploited to further green the cloud running on top of geographically distributed data centers. We jointly consider the electricity cost, service level agreement (SLA) requirement, and emission reduction budget. To navigate such a three-way tradeoff, we take advantage of Lyapunov optimization techniques to design and analyze a carbon-aware control framework, which makes online decisions on geographical load balancing, capacity right-sizing, and server speed scaling. Results from rigorous mathematical analyses and real-world trace-driven empirical evaluation demonstrate its effectiveness in both minimizing electricity cost and reducing carbon emission.

Datacenters consume an enormous amount of energy with significant financial and environmental costs. For geo-distributed datacenters, a workload management approach that routes user requests to locations with cheaper and cleaner electricity has been shown to be promising lately. We consider two key aspects that have not been explored in this approach. First, through empirical studies, we find that the energy efficiency of the cooling system depends directly on the ambient temperature, which exhibits a significant degree of geographical diversity. Temperature diversity can be used by workload management to reduce the overall cooling energy overhead. Second, energy consumption comes from not only interactive workloads driven by user requests, but also delay tolerant batch workloads that run at the back-end. The elastic nature of batch workloads can be exploited to further reduce the energy cost. In this work, we propose to make workload management for geo-distributed datacenters temperature aware. We formulate the problem as a joint optimization of request routing for interactive workloads and capacity allocation for batch workloads. We develop a distributed algorithm based on an m-block alternating direction method of multipliers (ADMM) algorithm that extends the classical 2-block algorithm. We prove the convergence and rate of convergence results under general assumptions. Trace-driven simulations demonstrate that our approach is able to provide 5%--20% overall cost savings for geo-distributed datacenters.

In cloud computing, a provider leases its computing resources in the form of virtual machines to users, and a price is charged for the period they are used. Though static pricing is the dominant pricing strategy in today's market, intuitively price ought to be dynamically updated to improve revenue. The fundamental challenge is to design an optimal dynamic pricing policy, with the presence of stochastic demand and perishable resources, so that the expected long-term revenue is maximized. In this paper, we make three contributions in addressing this question. First, we conduct an empirical study of the spot price history of Amazon, and find that surprisingly, the spot price is unlikely to be set according to market demand. This has important implications on understanding the current market, and motivates us to develop and analyze market-driven dynamic pricing mechanisms. Second, we adopt a revenue management framework from economics, and formulate the revenue maximization problem with dynamic pricing as a stochastic dynamic program. We characterize its optimality conditions, and prove important structural results. Finally, we extend to consider a nonhomogeneous demand model.

We study the resource allocation problem in an OFDMA-based cooperative cognitive radio network, where secondary users relay data for primary users in order to gain access to the spectrum. In light of user and channel diversity, we first propose FLEC, a novel flexible channel cooperation scheme. It allows secondary users to freely optimize the use of channels for transmitting primary data along with their own, in order to maximize performance. Further, we formulate a unifying optimization framework based on Nash bargaining solutions to fairly and efficiently allocate resources between primary and secondary networks, in both decentralized and centralized settings. We present an optimal distributed algorithm and a suboptimal centralized heuristic, and verify their effectiveness via realistic simulations. Under the same framework, we also study conventional identical channel cooperation as the performance benchmark, and propose algorithms to solve the corresponding optimization problems.

We present Anchor, a general resource management architecture that uses the stable matching framework to decouple policies from mechanisms when mapping virtual machines to physical servers. In Anchor, clients and operators are able to express a variety of distinct resource management policies as they deem fit, and these policies are captured as preferences in the stable matching framework. The highlight of Anchor is a new many-to-one stable matching theory that efficiently matches VMs with heterogeneous resource needs to servers, using both offline and online algorithms. Our theoretical analyses show the convergence and optimality of the algorithm. Our experiments with a prototype implementation on a 20-node server cluster, as well as large-scale simulations based on real-world workload traces, demonstrate that the architecture is able to realize a diverse set of policy objectives with good performance and practicality.

Many cloud services nowadays are running on top of geographically distributed infrastructures for better reliability and performance. They need an effective way to direct the user requests to a suitable data center, depending on factors including performance, cost, etc. Previous work focused on efficiency and invariably considered the simple objective of maximizing aggregated utility. These approaches favor users closer to the infrastructure. In this paper, we argue that fairness should be considered to ensure users at disadvantageous locations also enjoy reasonable performance, and performance is balanced across the entire system. We adopt a general fairness criterion based on Nash bargaining solutions, and present a general optimization framework that models the realistic environment and practical constraints that a cloud faces. We develop an efficient distributed algorithm based on dual decomposition and the sub gradient method, and evaluate its effectiveness and practicality using real-world traffic traces and electricity prices.

We study the infinite horizon dynamic pricing problem for an infrastructure cloud provider in the emerging cloud computing paradigm. The cloud provider, such as Amazon, provides computing capacity in the form of virtual instances and charges customers a time-varying price for the period they use the instances. The provider's problem is then to find an optimal pricing policy, in face of stochastic demand arrivals and departures, so that the average expected revenue is maximized in the long run. We adopt a revenue management framework to tackle the problem. Optimality conditions and structural results are obtained for our stochastic formulation, which yield insights on the optimal pricing strategy. Numerical results verify our analysis and reveal additional properties of optimal pricing policies for the infinite horizon case.

There has been a recent trend that video-on-demand (VoD) providers such as Netflix are leveraging resources from cloud services for multimedia streaming. In this paper, we consider the scenario that a VoD provider can make reservations for bandwidth guarantees from cloud service providers to guarantee the streaming performance in each video channel. We propose a predictive resource auto-scaling system that dynamically books the minimum bandwidth resources from multiple data centers for the VoD provider to match its short-term demand projections. We exploit the anti-correlation between the demands of video channels for statistical multiplexing and for hedging the risk of under-provision. The optimal load direction from channels to data centers is derived with provable performance. We further provide suboptimal solutions that balance bandwidth and storage costs. The system is backed up by a demand predictor that forecasts the demand expectation, volatility and correlations based on learning. Extensive simulations are conducted driven by the workload traces from a commercial VoD system.

Multicast is an important application in cellular networks. The 4G technologies, including WiMAX and LTE, invariably adopt Multiple-Input-Multiple-Output (MIMO) to facilitate spatial multiplexing and fundamentally increase channel capacity. However, state-of-the-art multicast protocols are designed to perform in single-hop mode with a single session, leading to under-utilization of the scarce spectrum resource. In this paper, we propose YMMV, a novel multicast protocol that jointly considers MIMO and cooperative communications in OFDMA networks. The base station transmits data in multiple sessions using multiple antennas on the same channel to exploit spatial multiplexing in MIMO. Further, cooperative transmission on different channels among users is also utilized. We tackle the resulted session scheduling problem in YMMV, where the multi-channel characteristic of OFDMA further aggravates the difficulty of efficient algorithm design. With rigorous analysis and extensive simulations, we show that our multi-session multicast protocol is able to improve throughput performance significantly.

In this paper, we advocate the use of stable matching framework in solving networking problems, which are traditionally solved using utility-based optimization or game theory. Born in economics, stable matching efficiently resolves conflicts of interest among selfish agents in the market, with a simple and elegant procedure of deferred acceptance. We illustrate through one technical case study how it can be applied in practical scenarios where the impeding complexity of idiosyncratic factors makes defining a utility function difficult. Due to its use of generic preferences, stable matching has the potential to offer efficient and practical solutions to networking problems, while its mathematical structure and rich literature in economics provide many opportunities for theoretical studies. In closing, we discuss open questions when applying the stable matching framework.

Video-on-demand (VoD) servers are usually over-provisioned for peak demands, incurring a low average resource efficiency. However, bandwidth shortage may still occur for individual videos as they share and contend for server resources. In this position paper, we propose a predictive workload management system for VoD servers targeting bandwidth. The system draws belief about future demand as well as demand volatility based on demand history using time series forecasting techniques. The prediction enables dynamic and efficient server bandwidth reservation with QoS guarantees. More importantly, we use a hedging technique similar to investment portfolio management and distribute workloads to multiple servers exploiting demand anti-correlation. The proposed system consolidates the workloads, enhances resource utilization, while in the meantime effectively controlling risk of server overload. The proposed methods are evaluated based on real-world VoD traces.

State-of-the-art spectrum auctions are designed under a primary market paradigm to conduct spectrum trading between legacy owners and large cognitive service providers. In our previous work, we established a spectrum secondary market based on double auctions, and showed that it significantly improves spectrum utilization and user performance by allowing secondary users to dynamically trade among themselves their channel holdings obtained in the primary market. In this paper, we devise a channel portfolio optimization framework in order for users to make intelligent trading decisions without burdensome overhead. By viewing each channel in the secondary market as a stock, users assess its characteristics, and derive which channels to buy or sell at what price and quantity as a portfolio optimization problem to maximize the expected utility. Coupled with the robust secondary market design, the channel portfolio optimization framework offers salient performance with low complexity as corroborated in our simulations.

Cognitive Radio Networks (CRNs) have recently emerged as a promising technology to improve spectrum utilization by allowing secondary users to dynamically access idle primary channels. As progress are made and computationally powerful wireless devices are proliferated, there is a compelling need of enabling multicast services for secondary users. Thus, it is crucial to design an efficient multicast scheduling protocol in CRNs. However, state-of-the-art multicast scheduling protocols are not well designed for CRNs. First, due to primary channel dynamics and user mobility, there may not exist commonly available channels for secondary users, which inevitably makes the multicast scheduling infeasible. Second, the potential benefits provided by user and channel diversities are overlooked, which leads to under-utilization of the scarce wireless bandwidth. In this paper, we present an optimization framework for multicast scheduling in CRNs, by fully embracing its characteristics. In this framework, base station multicasts data to a subset of secondary users first by carefully tuning the power. Concurrently, secondary users opportunistically perform cooperative transmissions using locally idle primary channels, in order to mitigate multicast loss and delay effects. Network coding is adopted during the transmissions to reduce overhead and perform error control and recovery. We jointly consider important design factors in our scheduling protocols, including power control, relay assignment, buffer management, dynamic spectrum access, primary user protection, and fairness. We also incorporate user, channel, and cooperative diversities. Two forms of multicast scheduling protocols in CRNs are proposed accordingly: (i) a greedy protocol based on centralized optimization; (ii) an online protocol based on stochastic optimization in both centralized and decentralized manners. With rigorous analysis based on Lyapunov optimization, we provide closed-form bounds to characterize the performance of our protocols, in terms of the interference to primary users and throughput utility of secondary users. With extensive simulations, we show that our proposed protocols can significantly improve the multicast performance in CRNs.

Dynamic spectrum trading amongst small cognitive users is fundamentally different along two axes: temporal variation, and spatial variation of user demand and channel condition. We advocate that a spectrum secondary market, analogous to the stock market, is to be established for users to dynamically trade among themselves their channel holdings obtained in the primary market from legacy owners. We design a market mechanism based on dynamic double auctions, creating a marketplace in the air to match bandwidth demand with supply. In the analysis we prove important economic properties of the mechanism, notably its truthfulness and asymptotic efficiency in maximizing spectrum utilization. Complimentary simulation studies corroborate that spectrum utilization and user performance can be improved by establishing the spectrum secondary market.

Recently, a cooperative paradigm for single-channel cognitive radio networks has been advocated, where primary users can leverage secondary users to relay their traffic. However, it is not clear how such cooperation can be exploited in multi-channel networks effectively. Conventional cooperation entails that data on one channel has to be relayed on exactly the same channel, which is inefficient in multi-channel networks with channel and user diversity. Moreover, the selfishness of users complicates the critical resource allocation problem, as both parties target at maximizing their own utility. This work represents the first attempt to address these challenges. We propose FLEC, a novel design of flexible channel cooperation. It allows secondary users to freely optimize the use of channels for transmitting primary data along with their own data, in order to maximize performance. Further, we formulate a unifying optimization framework based on Nash Bargaining Solutions to fairly and efficiently address resource allocation between primary and secondary networks, in both decentralized and centralized settings. We present an optimal distributed algorithm and sub-optimal centralized heuristics, and verify their effectiveness via realistic simulations.

Network coding has been leveraged with cooperative diversity to improve performance in single channel wireless networks. However, it is not clear how network coding based cooperative diversity can be exploited effectively in multi-channel networks where overhearing is not readily available. Moreover, the question of how to practically realize the promising gains available, including multi-user diversity, cooperative diversity and network coding in multi-channel networks, also remains unexplored. This work represents the first attempt to unravel these two questions. In this paper, we propose XOR-CD, a novel XOR-assisted cooperative diversity scheme in OFDMA wireless networks. It can greatly improve the relay efficiency by over 100% mostly, thus uplifting the throughput performance by over 30% compared to conventional cooperative diversity scheme. In addition, we formulate a unifying optimization framework that jointly considers relay assignment, relay strategy selection, channel assignment and power allocation to reap different forms of gains. We design efficient polynomial time algorithms to solve the NP-hard problem with provably the best approximation factor, and verify their effectiveness using realistic simulations.