The explosive growth of modern short-video platforms like WeChat Channels — approaching 1.4 billion monthly active users (MAU) while serving over one billion queries per second (QPS) — has exposed fundamental limitations in conventional content delivery network (CDN) architectures, particularly their inability to handle highly dynamic content popularity patterns. The traditional cache-centric approach proves to be catastrophic when faced with ephemeral content exhibiting a "million-item waist" distribution. This phenomenon results in severe cache pollution (manifesting as 5–40% origin miss ratios) and introduces prohibitive back-to-origin bandwidth costs. Our TritonFlow overcomes these challenges by introducing access point scheduling as a novel origin traffic compensator, which reduces the operational cost of back-to-origin fetches by enhancing CDN cache affinity. Through analysis of production traces (peak >1B QPS), we demonstrate that TritonFlow reduces scheduling fluctuations by 96% and decreases back-to-origin traffic caused by non-compulsory cache misses by 35%, all while maintaining sub-200ms fetch latency.

The deployment of Mixture-of-Experts (MoE) models on production high-bandwidth superpods, such as NVIDIA's NVL72/576 and Huawei's CloudMatrix384, introduces critical challenges beyond raw interconnect bandwidth. While these systems provide unified global address spaces and high-bandwidth fabrics, their full potential for sparse MoE communication is hindered by three fundamental bottlenecks: (1) Strict execution serialization imposed by coarse-grained Bulk Synchronous Parallel (BSP) orchestration of interdependent communication phases; (2) Prohibitive synchronization overhead that fails to scale alongside high interconnect bandwidth; and (3) Severe load imbalance resulting from distance-agnostic scheduling of irregular token traffic. To eliminate these bottlenecks, we introduce UBEP (Unified-Bus Expert Parallelism), a production-ready communication library that rethinks MoE's All-to-All primitives for modern superpod architectures. Through large-scale experiments, UBEP reduces All-to-All latency by up to 52.4% and MoE inference Time Per Output Token (TPOT) by up to 11.1%.

Data centers rely on Priority-based Flow Control (PFC) to achieve lossless data transmission in Ethernet networks. To avoid buffer overflow, PFC pauses flows in a coarse-grained manner, which brings potential problems, e.g., Head-of-Line (HoL) blocking, and PFC deadlock. Although the state-of-the-art approach BFC with per-flow backpressure tackles some of the limitations of PFC, it faces implementation challenges due to the need for a large number of queues. In this paper, we present F-PFC, a fine-grained flow control scheme that only leverages a small amount of queues to address the limitations of PFC. Specifically, F-PFC first designs a fine-grained flow backpressure scheme to adjust the intensity of flow control adaptively. With different levels of flow backpressure, F-PFC ensures high throughput and low latency simultaneously. Then, F-PFC presents an accurate flow identification scheme to locate flows that really contribute to congestion. Finally, F-PFC presents a dynamic queue assignment and scheduling scheme to isolate congestion flows with limited queues. We theoretically analyze the performance of F-PFC and present the implementation of F-PFC. Extensive testbed experiments and large-scale simulations verify the performance of F-PFC. The experimental results show that F-PFC reduces tail latency by at least 33% and queue occupancy by 46% compared with state-of-the-art approaches.

In modern datacenters, the effectiveness of end-to-end congestion control (CC) is quickly diminishing with the rapid bandwidth evolution. Per-hop flow control (FC) can react to congestion more promptly. However, a coarse-grained FC can result in Head-Of-Line (HOL) blocking. A fine-grained, per-flow FC can eliminate HOL blocking caused by flow control, however, it does not scale well. This paper presents Pyrrha, a scalable flow control approach that provably eliminates HOL blocking while using a minimum number of queues. In Pyrrha, flow control first takes effect on the root of the congestion, i.e., the port where congestion occurs. And then flows are controlled according to their contributed congestion roots. A prototype of Pyrrha is implemented on Tofino2 switches. Compared with state-of-the-art approaches, the average FCT of uncongested flows is reduced by 42%-98%, and 99th-tail latency can be$1.6\times $-$215\times $lower, without compromising the performance of congested flows.

Network failure uncertainty and traffic demand uncertainty pose a series of challenges to efficiently solve network traffic engineering (TE) problems in the production wide-area networks (WANs). Prior works especially predict-then-optimize paradigm in TE systems encounter a significant mismatch between the upstream prediction task and the downstream optimization task, leading to potential demand loss risk and further degrading the performance of customer-facing applications in the cloud. In this paper, we present TUFTTE, a risk-driven TE optimization framework, where the objective function and constraints can be flexibly specified by the network operators. We employ a differentiable optimization layer to guide the prediction model with the objective of minimizing the network risks. When the network risk is defined as the demand loss, our approach can provably converge to the global optimum. Experimental results on real-world topology demonstrate that TUFTTE reduces the demand loss by 11.59% on average compared to the state-of-the- art algorithm. We believe that our paper deeply explores the potential of prediction and promotes the understanding on how to develop and deploy a general learning module into the commercial TE optimization.

The emergence of long-context text applications utilizing large language models (LLMs) has presented significant scalability challenges, particularly in memory footprint. The linear growth of the Key-Value (KV) cache, which stores attention keys and values to reduce redundant computations, can significantly increase memory usage and may prevent models from functioning properly in memory-constrained environments. To address this issue, we propose a novel approach called Cache Sparse Representation (CSR), which converts the KV cache by transforming the dense Key-Value cache tensor into sparse indexes and weights, offering a more memory-efficient representation during LLM inference. Furthermore, we introduce NeuralDict, a novel neural network-based method to automatically generate the dictionary used in our sparse representation. Our extensive experiments demonstrate that CSR matches the performance of state-of-the-art KV cache quantization algorithms while ensuring robust functionality in memory-constrained environments.

Optimizing anycast catchment to ensure clients connect to their expected PoPs remains a significant challenge in production networks, primarily due to BGP’s inherent lack of performance awareness. Existing approaches either lack fine-grained routing policy control or prove operationally impractical. In this paper, we present AnyTuner, an automatic route management system that strategically optimizes anycast performance through AS-path prepending and BGP communities. AnyTuner integrates three key components: a measurement-driven optimization loop, a neural network for PoP traffic matrix prediction, and an automated recommendation engine for configuration generation. Deployed for over two years on a commercial cloud platform, AnyTuner demonstrates remarkable efficacy in our evaluation across 18 PoPs and 9,000+ probes, achieving a 39.9% reduction in median RTT (from 36.3 ms to 21.8 ms) compared to policy-free baseline configurations and outperforming state-of-the-art alternatives like AnyOpt by 27.8%.

Network failure uncertainty and traffic demand uncertainty pose a series of challenges to efficiently solve network traffic engineering (TE) problems in the production wide-area networks (WANs). Prior works especially predict-then-optimize paradigm in TE systems encounter a significant mismatch between the upstream prediction task and the downstream optimization task, leading to potential demand loss risk and further degrading the quality of services in the cloud. In this paper, we present TUFTTE, a risk-driven TE optimization framework, where the objective function and constraints can be flexibly specified by the network operators. We employ a differentiable optimization layer to guide the prediction model with the objective of minimizing the network risks. When the network risk is defined as the demand loss, our approach can provably converge to the global optimum. Experimental results on real-world topology demonstrate that TUFTTE reduces the demand loss by 11.59 % on average compared to the state-of-the-art algorithm. We believe that our paper deeply explores the potential of prediction and promotes the understanding on how to develop and deploy a general learning module into the commercial TE optimization.

Low-latency interactive video streaming services critically depend on robust congestion control algorithms (CCA). However, existing CCAs often exhibit frequent self-induced oscillations from unconstrained probing, causing periodic heavy queuing and degrading the user experience. We propose Themis, a novel end-to-end CCA designed to achieve stabilized near-zero queuing delay with high bitrate. By precisely quantifying the trade-off between bitrate and queuing delay within a utility feedback mechanism, Themis effectively controls the amplitude and frequency of probing while ensuring fairness. In parallel, Themis incorporates the awareness of the queuing state through an adaptive-pacing method, combined with utility feedback to guide a three-phase bitrate adjustment strategy. This enables rapid and stable convergence to the optimal utility. We implemented Themis in QUIC, evaluated it on the Mahimahi and conducted a 90-day large-scale A/B test in a real-world network. Compared to state-of-the-art CCAs, Themis effectively suppresses self-induced oscillations, increases the average frame bitrate by 66.8%, and reduces the average frame delay by 13.5%, demonstrating a superior trade-off between high bitrate and low queuing delay.

Online Internet platforms require sophisticated marketing strategies to optimize user retention and platform revenue — a classical resource allocation problem. Traditional solutions adopt a two-stage pipeline: machine learning (ML) for predicting individual treatment effects to marketing actions, followed by operations research (OR) optimization for decision-making. This paradigm presents two fundamental technical challenges. First, the prediction-decision misalignment: Conventional ML methods focus solely on prediction accuracy without considering downstream optimization objectives, leading to improved predictive metrics that fail to translate to better decisions. Second, the bias-variance dilemma: Observational data suffers from multiple biases (e.g., selection bias, position bias), while experimental data (e.g., randomized controlled trials), though unbiased, is typically scarce and costly --- resulting in high-variance estimates. We propose **Bi**-level **D**ecision-**F**ocused **C**ausal **L**earning (**Bi-DFCL**) that systematically addresses these challenges. First, we develop an unbiased estimator of OR decision quality using experimental data, which guides ML model training through surrogate loss functions that bridge discrete optimization gradients. Second, we establish a bi-level optimization framework that jointly leverages observational and experimental data, solved via implicit differentiation. This novel formulation enables our unbiased OR estimator to correct learning directions from biased observational data, achieving optimal bias-variance tradeoff. Extensive evaluations on public benchmarks, industrial marketing datasets, and large-scale online A/B tests demonstrate the effectiveness of Bi-DFCL, showing statistically significant improvements over state-of-the-art. Currently, Bi-DFCL has been deployed across several marketing scenarios at Meituan, one of the largest online food delivery platforms in the world.

Learned indexes, which model key-value data structures by machine learning models, have been extensively studied. However, the fastest immutable learned indexes (e.g., RMI) do not provide the same tight lookup bounds as classical indexes such as B-trees. There are learned indexes that provide tight bounds (e.g., PGM) but those fall short in query performance. This gives rise to an interesting open question: whether there exists a learned index that simultaneously achieves state-of-the-art empirical performance and matching complexity? In this paper, we give a positive answer to this standing problem.We propose two new online model-building policies: (1) simplifying distribution by the adoption of a proper granularity (i.e., grouping multiple keys together for model-building) and (2) actively tuning distribution through key repositioning. Additionally, we introduce a general framework that combines these two policies for performance optimization under a given memory budget. We put everything together to design VEGA, a learned index that simultaneously achieves competitive theoretical and empirical performance compared to state-of-the-art learned indexes. We conducted extensive evaluations, demonstrating VEGA achieves both better lookup and building performance.

Estimating per-flow cardinality from high-speed data streams has many applications such as anomaly detection and resource allocation. Yet despite tracking single flow cardinality with approximation algorithms offered, there remain algorithmical challenges for monitoring multi-flows especially under unbalanced cardinality distribution: existing methods adopt a uniform sketch layout and incur a large memory footprint to achieve high accuracy. Furthermore, they are hard to implement in the compact hardware used for line-rate processing. In this paper, we propose Couper, a memory-efficient measurement framework that can estimate cardinality for multi-flows under unbalanced cardinality distribution. We propose a two-layer structure based on a classic coupon collector's principle, where numerous mice flows are confined to the first layer and only the potential elephant flows are allowed to enter the second layer. Our two-layer structure can better fit the unbalanced cardinality distribution in practice and achieve much higher memory efficiency. We implement Couper in both software and hardware. Extensive evaluation under real-world and synthetic data traces show more than 20× improvements in terms of memory-efficiency compared to state-of-the-art.

With the increase of diversity in application preferences and networks, existing congestion control algorithms (CCAs) do not accommodate this complicated reality. Previous classic CCAs are designed for a specific domain with fixed rules, failing to adapt to such diversities. Recently surged learning-based CCAs have great potential in adaptability and flexibility but are not practical due to unsatisfying performance on convergence, fairness, overhead, consistency and safety assurance. In this paper, we propose Libra, a unified congestion control framework, that can empower these properties by combining the wisdom of classic and reinforcement learning (RL)-based CCAs. Extensive evaluation of Libra’s Linux kernel implementations on both live Internet and emulated networks shows performance improvement under dynamic networks (e.g.,$1.2\times $throughput than Orca on average). At the same time, Libra can flexibly satisfy different application needs, reduce the running overhead by at most$0.88\times $and perform good fairness and convergence properties, well-fitting our theoretical analysis.

Approximate membership query (AMQ) data structures can approximately determine whether an element exists in a given dataset. They are widely used in parallel and distributed systems (e.g., high-performance databases, distributed cache systems, and bioinformatics systems) to avoid unnecessary dataset accesses, thereby accelerating massive data processing. For AMQ data structures used in the above systems, achieving high throughput, low false positive rate, and large capacity objectives simultaneously is critical but challenging. Porting AMQ data structures from DRAM to persistent memory makes it possible to achieve the above three objectives simultaneously, but this porting is not a trivial task. Specifically, existing AMQ data structures generate numerous random accesses and/or sequential writes on persistent memory, resulting in poor throughput. Therefore, in the conference version of this paper, we proposed a novel AMQ data structure called wormhole filter, which achieves high throughput on persistent memory, thereby achieving the above three objectives simultaneously. In this journal version, we extend our prior work by introducing parallel wormhole filters to enhance parallel performance. Additionally, we integrate parallel wormhole filters into the LevelDB database system to show that porting AMQ data structures to persistent memory significantly improves system endto-end throughput. Theoretical analysis and experimental results show that wormhole filters significantly outperform state-of-theart AMQ data structures. For example, wormhole filters achieve 12.06× insertion throughput, 1.98× positive lookup throughput, and 8.82× deletion throughput of the best competing baseline.

Approximate membership query (AMQ) data structures can approximately determine whether an element is in the set with high efficiency. They are widely used in distributed systems, database systems, bioinformatics, IoT applications, data stream mining, etc. However, the memory consumption of AMQ data structures grows rapidly as the data scale grows, which limits the system's ability to process a massive amount of data. The emerging persistent memory provides a close-to-DRAM access speed and terabyte-level capacity, facilitating AMQ data structures to handle massive data. Nevertheless, existing AMQ data structures perform poorly on persistent memory due to intensive random accesses and/or sequential writes. Therefore, we propose a novel AMQ data structure called wormhole filter, which achieves high performance on persistent memory by reducing random accesses and sequential writes. In addition, we reduce the number of log records for lower recovery overhead. Theoretical analysis and experimental results show that wormhole filters significantly outperform competitive state-of-the-art AMQ data structures. For example, wormhole filters achieve 23.26× insertion throughput, 1.98× positive lookup throughput, and 8.82× deletion throughput of the best competing baseline.

Marketing optimization plays an important role to enhance user engagement in online Internet platforms. Existing studies usually formulate this problem as a budget allocation problem and solve it by utilizing two fully decoupled stages, i.e., machine learning (ML) and operation research (OR). However, the learning objective in ML does not take account of the downstream optimization task in OR, which causes that the prediction accuracy in ML may be not positively related to the decision quality.

Online controlled experiments play a crucial role in enabling data-driven decisions across a wide range of companies. Variance reduction is an effective technique to improve the sensitivity of experiments, achieving higher statistical power while using fewer samples and shorter experimental periods. However, typical variance reduction methods (e.g., regression-adjusted estimators) are built upon the intuitional assumption of Gaussian distributions and cannot properly characterize the real business metrics with heavy-tailed distributions. Furthermore, outliers diminish the correlation between pre-experiment covariates and outcome metrics, greatly limiting the effectiveness of variance reduction.

Network monitoring is essential for network management and optimization. In modern data centers, fluctuations in flow rates and network congestion events (e.g., microbursts) typically manifest on a microsecond timescale. However, the time granularity of network monitoring systems has not been refined correspondingly to efficiently capture these behaviors. Attaining the monitoring granularity at the microsecond scale can greatly facilitate network performance analysis and management, but poses considerable challenges regarding memory, bandwidth, and deployment costs. We propose μMon, a novel microsecond-level network monitoring system for data centers. The key of μMon is WaveSketch, an innovative algorithm that measures and compresses flow rate curves using in-dataplane wavelet transform. WaveSketch allows for more accurate characterization of application traffic patterns and aids in profiling transport algorithms. Furthermore, by combining the fine-grained flow rate measurements with network-collected congestion information, μMon can 'replay' congestion events to analyze their cause and impact. We evaluate μMon through testbed deployment and simulations at a granularity of 8.192 μs. The evaluation results demonstrate that μMon can achieve a 90% accuracy in microsecond-level rate measurements with an average of 5 Mbps bandwidth overhead per host. Additionally, it can capture 99% heavy congestion events with 31--82 Mbps bandwidth overhead per switch.

Charger placement is an important problem in improving the quality of service in wireless rechargeable sensor networks. This paper studies the problem ofWireless ChArger PlacemeNt with Multiple (Directional) Antennas (WANDA). The problem is described as follows: given a set of wireless chargers equipped with multiple directional antennas and a set of wireless rechargeable sensors, determine the chargers' positions and orientations to maximize the overall charging utility. According to the relative positional relationship between the antennas, the problem is classified into Relative Orientation Fixed (WANDA-ROF) and Relative Orientation Unfixed (WANDA-ROU) situations. To address WANDA, we present a piecewise constant function to approximate the nonlinearity of charging power and propose an area discretization technique to reduce the infinite solution space to a limited one without performance loss. Then, we prove the monotonic submodularity of WANDA, and present a$\frac{1}{2}-\epsilon$approximation algorithm for the ROF situation and a$\frac{1}{2}-\epsilon$approximation algorithm for the ROU situation, all run in polynomial time. Finally, we conduct extensive simulation and experiments to show that our algorithms outperform comparison algorithms by at least 16% for ROF situation and 12% for ROU situation.

Truck-drone systems, wherein trucks carrying drones drive to pre-planned positions and then free drones equipped with cameras to monitor a known number of objects with reported positions, have been used for various scenarios. An object's quality of monitoring (QoM) by a camera is defined as a function of camera focal length and monitoring distance. Improving the QoM would help downstream tasks, including object detection and recognition. The monitoring utility is the fusion of all the QoMs of an object from multiple cameras. This paper optimizes theDeploymentOfTrucksAndDrones forObject monitoring (DOTADO) problem,i.e., deploying a truck-drone system, where each drone is equipped with a varifocal camera, to maximize the overall monitoring utility for all objects. Firstly, we model the hybrid system and define monitoring quality and utility. Then, we discretize the solution space into deployment strategies with performance bound. To select deployment strategies, we prove the submodularity of the problem and propose a two-level greedy algorithm with a bounded approximation ratio. Finally, we devise an optimal method to adjust the strategy for energy saving and communication improvement without losing monitoring utility. We perform both simulations and field experiments to verify the proposed framework.

Nowadays, there exists a lot of cross-region data transmission demand on the cloud. It is promising to use serverless computing for data compressing to save the total data size. However, it is challenging to estimate the data transmission time and monetary cost with serverless compression. In addition, minimizing the data transmission cost is non-trivial due to the enormous parameter space. This paper focuses on this problem and makes the following contributions: 1) We propose empirical data transmission time and monetary cost models based on serverless compression. It can also predict compression information, e.g., ratio and speed using chunk sampling and machine learning techniques. 2) For single-task cloud data transmission, we propose two efficient parameter search methods based on Sequential Quadratic Programming (SQP) and Eliminate then Divide and Conquer (EDC) with proven error upper bounds. Besides, we propose a parameter fine-tuning strategy to deal with transmission bandwidth variance. 3) Furthermore, for multi-task scenarios, a parameter search method based on dynamic programming and numerical computation is proposed. We have implemented the system called Fluid-Shuttle, which includes straggler optimization, cache optimization, and the autoscaling decompression mechanism. Finally, we evaluate the performance of Fluid-Shuttle with various workloads and applications on the real-world AWS serverless computing platform. Experimental results show that the proposed approach can improve the parameter search efficiency by over$3\times $compared with the state-of-art methods and achieves better parameter quality. In addition, our approach achieves higher time efficiency and lower monetary cost compared with competing cloud data transmission approaches.

Finding special items in data streams, like heavy hitters, top-$k$items, and persistent items, has always been a hot topic in the field of network measurement. While data streams nowadays are usually high-dimensional, most prior works optimize data structures to accurately find special items according to a certain primary dimension and yield little insight into the correlations between dimensions, where the dimension can be a single data dimension or a combination of multiple data dimensions. Therefore, we propose to find special quadratic elements in data streams to reveal the close correlations between the primary and secondary dimensions. Here, both the primary and secondary dimensions are selected according to specific application purposes. Based on the special items mentioned above, we extend our problem to three applications related to heavy hitters, top-$k$, and persistent items, and design a generic framework DUET to process them. We analyze the error bound of our algorithm theoretically and conduct extensive experiments on four publicly available data sets. Our experimental results show that DUET can achieve 3.5 times higher throughput and three orders of magnitude lower average relative error than cutting-edge algorithms. Moreover, we propose an optimized framework based on DUET, namely O-DUET, to further improve the estimation accuracy. We also discuss a hardware-version DUET and deploy it on Tofino.

The quality of the video stream is the key to neural network-based video analytics. However, low-quality video is inevitably collected by existing surveillance systems because of poor-quality cameras or over-compressed/pruned video streaming protocols, e.g., as a result of upstream bandwidth limit. To address this issue, existing studies use quality enhancers (e.g., neural super-resolution) to improve the quality of videos (e.g., resolution) and eventually ensure inference accuracy. Nevertheless, directly applying quality enhancers does not work in practice because it will introduce unacceptable latency. In this paper, we present AccDecoder, a novel accelerated decoder for real-time and neural-enhanced video analytics, selects a few frames adaptively via Deep Reinforcement Learning (DRL) to enhance the quality and inference then reuse on the unselected ones. Next, we extend AccDecoder to AccDecoder$+$by formulating the resolution-involved Markov decision process (MDP) to achieve resolution adaptation; it aims to trade accuracy and latency corresponding under various video resolutions. Proved by experiments, AccDecoder provides efficient inference capability via filtering important frames using DRL for DNN-based inference and reusing the results for the other frames via extracting the reference relationship among frames and blocks, which contributes 6-21% accuracy improvement and a latency reduction of 20-80% than baselines. Compared with AccDecoder, AccDecoder$+$achieves an additional 2-7% accuracy improvement.

The approximate membership query (AMQ) data structure is a kind of space-efficient probabilistic data structure. It can approximately indicate whether an element exists in a set. The AMQ data structure has been widely used in network measurements, network security, network caching,etc. Resizing is an extensively utilized operation of the AMQ data structure, but it can lead to system performance degradation. We summarize two main problems that lead to such degradation. Specifically, one of them is that the resizing operation can block other operations, while the other one is that the throughput of AMQ structures will deteriorate after multiple resizing operations due to more computation cost. However, existing related work cannot alleviate both of them. Therefore, we propose a novel AMQ data structure called bamboo filters, which can alleviate the two problems simultaneously. Bamboo filters can insert, look up, and delete an element in constant time. They can also dynamically resize in a fine-grained way. Furthermore, we propose space utilization adaptive bamboo filters that adaptively trigger resizing operations according to the space utilization, thereby achieving lower average memory consumption. Experimental results show that our scheme significantly outperforms state-of-the-art work. Especially, bamboo filters achieve 2.12$\times$lookup throughput of the logarithmic dynamic cuckoo filter.

Multipath TCP (MPTCP) is a burgeoning transport protocol which enables the server to transmit the traffic across multiple network interfaces in parallel. Classic MPTCPs have good friendliness and practicality such as relatively low overhead, but are hard to achieve consistent high-throughput and adaptability, especially for the ability to flexibly balance the congestion among different subpaths. In contrast, learning-based MPTCPs can essentially achieve consistent high-throughput and adaptability, but have poor friendliness and practicality. In this paper, we proposed MPLibra, a combined multipath congestion control framework that can complement the advantages of classic MPTCPs and learning-based MPTCPs together. MPLibra periodically leverages both classic MPTCPs and learning-based MPTCPs to make decisions and select the better one based on real-time network feedbacks. Extensive simulations on NS3 show that MPLibra can achieve good performance and outperform state-of-the-art MPTCPs under different network conditions. MPLibra improves the throughput by 40.5% and reduces the file download time by 29.94% compared with LIA, achieves good friendliness and balances congestion timely. What’s more, on the basis of MPLibra, we propose MPLibra+ which adds a safety module and an optimized packet scheduler and is the upgrade version of MPLibra. MPLibra+ has better ability to cope with untrained network environment and achieve better performance on heterogeneous scenarios compared with MPLibra.

Data centers heavily rely on scale-out architectures like fat-tree, BCube and VL2 to accommodate a large number of commodity servers. Since the traditional electrical network is demand-oblivious and cannot perfectly respond to the bursty traffic generated by big data applications, a growing trend is to design demand-aware topologies via introducing the converters with adjustable optical links, instead of adding more wiring links. However, little is known today about how to fully exploit the potential of the flexibility from the converters: the joint optimization on adjusting the optical links inside the converters and the routing in the whole network remains algorithmically challenging. In this paper, we design a set of customized converters for Diamond, VL2 and BCube topologies and initiate the optimization study in hybrid switching data center networks. As a case study, we introduce demand-aware load balancing problem (DLBP), i.e., a joint optimization on the physical layer (how the optical links interconnect inside the converter) and the network layer (how to determine the route especially for elephant flows in the whole network). We prove that DLBP is not only NP-hard, but also$\rho $-inapproximation. Accordingly, we design two algorithms: the first one is an intuitive greedy algorithm and the second one uses reinforcement learning to improve upon the solution of the first one. Trace-driven evaluations show that our algorithms can reduce the traffic congestion by 12% on average.

Marketing is an important mechanism to increase user engagement and improve platform revenue, and heterogeneous causal learning can help develop more effective strategies. Most decision-making problems in marketing can be formulated as resource allocation problems and have been studied for decades. Existing works usually divide the solution procedure into two fully decoupled stages, i.e., machine learning (ML) and operation research (OR) --- the first stage predicts the model parameters and they are fed to the optimization in the second stage. However, the error of the predicted parameters in ML cannot be respected and a series of complex mathematical operations in OR lead to the increased accumulative errors. Essentially, the improved precision on the prediction parameters may not have a positive correlation on the final solution due to the side-effect from the decoupled design. In this paper, we propose a novel approach for solving resource allocation problems to mitigate the side-effects. Our key intuition is that we introduce the decision factor to establish a bridge between ML and OR such that the solution can be directly obtained in OR by only performing the sorting or comparison operations on the decision factor. Furthermore, we design a customized loss function that can conduct direct heterogeneous causal learning on the decision factor, an unbiased estimation of which can be guaranteed when the loss convergences. As a case study, we apply our approach to two crucial problems in marketing: the binary treatment assignment problem and the budget allocation problem with multiple treatments. Both large-scale simulations and online A/B Tests demonstrate that our approach achieves significant improvement compared with state-of-the-art.

Estimating per-flow cardinality from high-speed data streams has many applications such as anomaly detection and resource allocation. Yet despite tracking single flow cardinality with approximation algorithms offered, there remain algorithmical challenges for monitoring multi-flows especially under unbalanced cardinality distribution: existing methods adopt a uniform sketch layout and incur a large memory footprint to achieve high accuracy. Furthermore, they are hard to implement in the compact hardware used for line-rate processing.In this paper, we propose Couper, a memory-efficient measurement framework that can estimate cardinality for multi-flows under unbalanced cardinality distribution. We propose a two-layer structure based on a classic coupon collector’s principle, where numerous mice flows are confined to the first layer and only the potential elephant flows are allowed to enter the second layer. Our two-layer structure can better fit the unbalanced cardinality distribution in practice and achieve much higher memory efficiency. We implement Couper in both software and hardware. Extensive evaluation under real-world and synthetic data traces show more than 20× improvements in terms of memory-efficiency compared to state-of-the-art.

Classic contextual combinatorial multi-armed bandit problems aim to maximize the expected cumulative joint reward in the long run, where a learner plays a set of arms (i.e., a super arm) with time-invariant linear rewards of context features in each round. However, in many real-world applications, linear-reward assumptions often fail to be satisfied and the environment is in general non-stationary, leading to low performance with the bandit models above. Existing works fail to deal with non-linear rewards in the non-stationary environment and the algorithmic challenge remains. In this paper, we initiate the study of a non-stationary neural contextual combinatorial bandit problem, where the reward function of each individual arm can be estimated by a deep neural network based on boundedness assumption and a time-variant reward mapping function. Furthermore, we design an algorithm NNCMAB, which dynamically partitions the context subspace into multiple subspaces and fits reward mapping functions for each subspace by neural networks such that only the models of related subspaces are re-trained when local environment changes happen. NNCMAB can provably achieve $\tilde{O}\left(T^{\frac{3}{4}}+\sqrt{T}N_{c}\right)$ regret, where T is the number of rounds, and $N_{c}$ is a parameter associated with the distribution change. Evaluation results under synthetic and real-world LastFM datasets show that NNCMAB significantly outperforms other state-of-the-art with both linear and non-linear individual rewards under non-stationary environments.

Approximate membership query (AMQ) data structures can efficiently indicate whether an element exists in a data set. Therefore, they are widely used in data mining applications such as IoT streaming data mining, anomaly detection, duplicate detection, record linkage, and community discovery. The data amount to be processed in real-world applications often changes frequently and dynamically. Thus, before using the AMQ data structures, it is necessary to configure their capacity to the maximum number of elements that will be stored during runtime. We observe that when the number of elements stored in an AMQ data structure is lower than its capacity, a significant amount of space is wasted, making the false positive rate much higher than expected. To tackle this problem, we propose the variable-length encoding framework. It dynamically adjusts the encoding length of each element according to the number of elements stored in the AMQ data structure. Based on this design, the variable-length encoding framework can make full use of the memory space allocated to AMQ data structures, thereby improving the space efficiency and reducing the false positive rate. In addition, as a general encoding scheme, the variable-length encoding framework can be widely used in different types of AMQ data structures. Theoretical analysis and evaluation results show that AMQ data structures using the variable-length encoding framework have significantly lower false positive rates compared with state-of-the-art AMQ data structures. For example, when the load factor is 25%, the variable-length encoding framework can reduce the false positive rate of AMQ data structures by 88.15% on average (up to 99.40%).

As the emergence of recently popular large language model, distributed training (DT) optimizes the performance via using different parallelization strategies, resource schedulers and advanced compression techniques. Meanwhile, a promising acceleration primitive, In-Network Aggregation (INA), offloads the gradient aggregation to programmable switches to further reduce the communication overhead using the switch memory. However, to the best of our knowledge, how to identify the performance bottleneck in real time remains challenging. In this paper, we build Argus, a performance bottleneck monitoring framework for INA. Argus implements an aggregation digest extracting mechanism for real-time monitoring of DT jobs at the multi-tenant, multi-rack clusters. Argus models aggregation to identify performance bottlenecks in aggregation, which assists the scheduler in deciding the resource allocation. Extensive evaluation and prototype implementation show that Argus provides real-time and packet-level aggregation monitoring for identifying bottlenecks in INA with minimal performance overhead.

With the rapid development of big data technology, big data systems are more and more used to process SQL query jobs. However, intricate big data system parameters have big effects on the quality of service for big data query performance. Moreover, the types of query jobs and data sizes of data sets are diversified, which have different optimal parameters for best running performance. There exist high complexity and difficulties in tuning the big data system parameters for efficient query job execution. To address this issue, we propose Magpie, an efficient big data query tuning system based on the genetic algorithm with customized pruning strategies. The experimental results show that the proposed approaches can reduce big data query job execution time by 35.5% on average compared with the cuttingedge big data system parameter tuning methods.

Weighted congestion control aims to provide end-to-end differentiated bandwidth allocation. MulTCP and EWTCP are two closely related schemes for this purpose and they both want to achieve weighted proportionality through modifying AIMD behaviors. In this paper, we revisit the performance of MulTCP and EWTCP in terms of weighted proportionality. Through testbed experiments, we reveal a lot of counter-intuitive phenomena for achieving weighted proportionality — the switch buffer size, propagation delay and ACK options have a dominant impact on the weighted proportionality. Specifically, we develop WCC, a fundamental weighted AIMD-based congestion control building block, which can be implemented via individually modifying AI (WCC-AI) or MD (WCC-MD) behavior. We analyze WCC using extended fluid models, NS3 simulations and Linux kernel implementations with droptail and RED queues, and point out the determinant of performance. Finally, we clarify the influences of dynamic network characteristics on weighted proportionality with sufficient experimental results and summarize a basic law of how to implement weighted AIMD-based congestion control.

Recent studies show that an end system's traffic may reach a distant anycast site within a global IP anycast system, resulting in high latency. To address this issue, some private and public CDNs have implemented regional IP anycast, a technique that involves dividing content-hosting sites into geographic regions, announcing a unique IP anycast prefix for each region, and utilizing DNS and IP-geolocation to direct clients to CDN sites in their corresponding geographic regions. In this work, we aim to understand how a regional anycast CDN partitions its sites and maps its customers' clients to its sites, and how a regional anycast CDN performs compared to its global anycast counterpart. We study the deployment strategies and the performance of two CDNs (Edgio and Imperva) that currently deploy regional IP anycast. We find that both Edgio and Imperva partition their sites and clients following continent or country borders. Furthermore, we compare the client latency distribution in Imperva's regional anycast CDN with its similar-scale DNS global anycast network, while accounting for and mitigating the relevant deployment differences between the two networks. We find that regional anycast can effectively alleviate the pathology in global IP anycast where BGP routes clients' traffic to distant CDN sites. However, DNS mapping inefficiencies, where DNS returns a sub-optimal regional IP anycast address that does not cover a client's low-latency CDN sites, can harm regional anycast's performance. Finally, we show what performance benefits regional IP anycast can achieve with a latency-based region partition method using the Tangled testbed. When compared to global anycast, regional anycast significantly reduces the 90th percentile client latency by 58.7% to 78.6% for clients across different geographic areas.

Approximate query processing (AQP) is one of the key techniques to cope with big data querying problem on account that it obtains approximate answers efficiently. To address non-trivial sample selection and heavy sampling cost issues in AQP, we propose ShadowAQP, an efficient and accurate approach based on attribute-oriented sample size allocation and data generation. We select samples according to group-by and join attributes, and determine the sample size for each group of unique value combinations to improve query accuracy. We design a conditional variational autoencoder model with automatic table data encoding and model update strategies. To further improve accuracy and efficiency, we propose a set of extensions, including parallel multi-round sampling aggregation, data outlier-aware sampling, and dimension reduction optimization. Evaluation results on diversified datasets show that, compared with SOTA approaches, ShadowAQP achieves 5.8× query speed performance improvement on average (up to 12.8×), while reducing query error by 74% on average (up to 95%) at the same time.

A controller needs to solve the multi-commodity flow problem and globally update the network under tight time constraints to maintain optimal network configurations. This centralized optimization in data centers involves many variables and constraints, which has a slow convergence speed and little scalability. In this paper, we propose MiFi, which aims to Minimize Flow cost or intuitively average transmission delay (delay or latency of flows), under reconfiguration budget constraints in data centers. Thus, we formulate this optimization problem as a constrained Markov Decision Process and propose a set of algorithms to solve it in a scalable manner. We first develop a propagation algorithm to identify the flows mostly affected in terms of latency and configuration in the next update. Then, we set a limitation range (the subset of switches requiring network updates) for updating them to improve adaptability and scalability by updating a less number of flows each time to achieve fast operations. Further, based on the Drift-Plus-Penalty method in Lyapunov theory, we propose a heuristic policy without prior information of flow demand and a renewal policy with a performance guarantee to minimize the additive optimality gap. To the best of our knowledge, MiFi is the first paper that studies the range and frequency of flow reconfigurations, which has both theoretical and practical significance in the area. Emulations and numerical simulations, which are much better than the estimated theoretical bound, show that MiFi outperforms the state of the art algorithms in terms of latency by over 45% while making improvements in adaptability and scalability.

Virtualized network functions (VNFs) enable software applications to replace traditional middleboxes, which are more flexible and scalable in the network service provision. This paper focuses on ensuring Service Availability via Failure Elimination (SAFE) using VNF scaling, that is, given the resource requirements of VNF instances, finding an optimal and robust instance consolidation strategy, which can recover from one instance failure quickly. To address the above problem, we present a framework based on rounding and dynamic programming. First, we discretize the range of resource requirements into several sub-ranges, and thus the number of instance types becomes a constant. Second, we further reduce the number of instance types by gathering several small instances into a bigger one. Third, we propose an algorithm built on dynamic programming to solve the instance consolidation problem with a limited number of instance types. Finally, we set up a testbed to profile the functional relationship between the resource and the throughput for different types of VNFs, and conduct simulations to validate our theoretical results according to profiling results. The simulation results show that our algorithm outperforms the standby deployment model by 27.33% on average in terms of the number of servers required. Furthermore, SAFE has marginal overheads, around 7.22%, compared to the instance consolidation strategy without VNF backup consideration.

The approximate membership query (AMQ) data structure is a kind of space-efficient probabilistic data structure. It can approximately indicate whether an element exists in a set. The AMQ data structure has been widely used in database indexing, network security, IoT applications, etc. Resizing is an extensively utilized operation of the AMQ data structure, but it can lead to system performance degradation. We summarize two main problems that lead to such degradation. Specifically, one of them is that the resizing operation can block other operations, while the other is that the performance of AMQ structures will deteriorate after multiple resizing operations. However, existing related work cannot alleviate both of them. Therefore, we propose a novel AMQ data structure called bamboo filter, which can alleviate the two problems simultaneously. Bamboo filters can insert, search and delete an element in constant time. Moreover, bamboo filters can dynamically resize in a fine-grained way according to the number of contained elements. Experimental results show that bamboo filters significantly outperform state-of-the-art resizable AMQ data structures in insertion, lookup, and deletion operations. For example, bamboo filters achieve$\mathbf{2.46}\times$lookup throughput of the dynamic cuckoo filter, on average.

Mobile edge computing (MEC) is emerging as a novel computing paradigm that pushes network resources (such as computation and storage resources) away from the centralized data center to distributed edge servers. By hiring various resources of nearby edge servers, the MEC provides high-bandwidth and low-latency network services for mobile users. As numerous mobile users may compete for limited edge servers’ resources, to improve the resource utilization of the MEC system, it is very critical to investigate an effective user allocation policy. Previous studies mainly focus on investigating offline user allocation policies. However, mobile users may arrive online, and the MEC should be able to allocate these users online too. In a real-world MEC environment, online allocation decisions should not be made entirely in the dark. The historical user requests which may contain powerful hints about future user requests, can be adopted to assist in making allocation decisions. In this paper, we take the historical data into account and study the history-assisted online user allocation strategy. Specifically, we formulate the user allocation problem with a comprehensive model and show its hardness. Then, we present an online algorithm named HOUA to allocate mobile users according to both the online arrived user requests and the historical user requests. The competitive ratio of HOUA is proved. To further verify the effectiveness of HOUA, we conduct experiments on a widely-used real-world dataset. We show that HOUA can allocate more mobile users and achieve high resource rental revenue compared with the other approaches.

Bi-objective online stochastic bipartite matching can capture a wide range of real-world problems such as online ride-hailing, crowdsourcing markets, and internet adverting, where the vertices in the left side are known in advance and that in the right side arrive from a known identical independent distribution (KIID) in an online manner. Mutual interest and limited attention-span are two common conditions and can be modeled as the edge existence probability and two-sided limited patience. Existing works fail to take them into bi-objective online optimization. This paper establishes a unified model for bi-objective online stochastic bipartite matching that can provide a general tradeoff among the matched edges (OBJ-1) and vertices (OBJ-2). We formulate two linear programs (LP) and accordingly design four LP-based parameterized online algorithms to tradeoff OBJ-1 and OBJ-2, with the best competitive ratio of (0.3528α, 0.3528β), where α, β are two positive input parameters and α + β = 1. Our hardness analysis proves that any non-adaptive algorithm cannot achieve (δ1, δ2)-competitive such that ${\delta _1} + {\delta _2} > 1 - \frac{1}{e}$. Trace-driven experiments show that our algorithms can always achieve better performance and provide a flexible tradeoff.

The limitation on the flight range motivates a hybrid monitoring system, wherein trucks carrying drones drive to pre-planned positions and then free drones for task execution. While the flight range limitation is mitigated, it is challenging to determine the destination of trucks and drones and set airborne cameras. This paper optimizes the joint Deployment of trUcks and dronEs for objecT monitoring (DUET), that is, deploy a set of trucks where each truck carries drones, and each drone is equipped with a varifocal camera such that the overall monitoring utility for target objects is maximized. To tackle the DUET problem, we first model the hybrid system and monitoring utility; then, discretize the solution space of DUET with performance bound. In this way, the problem is transformed into a two-level combinatorial optimization problem satisfying submodularity. To address it, a two-level greedy algorithm with $\frac{{{{(e - 1)}^2}}}{{e(2e - 1)}} \cdot (1 - \varepsilon )$ approximation ratio is proposed to select deployment strategies. After the strategy selection, an optimal method is devised to carefully adjust the strategy for energy saving and communication improvement without loss of monitoring utility. Both simulations and field experiments are conducted to evaluate the proposed framework, which outperforms baseline algorithms on monitoring utility by at least 28.4% and 40%, respectively.

Unmanned aerial vehicle (UAV) has attracted much attention due to its excellent ability to collect visual information of surroundings. In this paper, we investigate a new monitoring model to focus on sizes and shapes of objects, and occlusion between objects, and then study the placement of a set of UAVs to monitor polygonal sizable objects. Our aim is to maximize the overall monitoring utility of all objects by determining the positions and orientations of UAVs, given a set of polygonal sizable objects with fixed coordinates and shapes on a$2\mathbf{D}$plane. We study two typical scenarios of the problem: the former stipulates that a line segment is effectively monitored only when it is completely monitored by a single UAV, and the latter allows multiple UAVs to cooperatively monitor a line segment and then integrate their image information. The problem is proved to be NP-hard with infinite continuous solution space. For the first scenario, we propose a$(1-1/e)$-approximation algorithm. For the second one, we first propose a 1/2-approximation algorithm to address its simple version, and then propose a heuristic solution. Numerical evaluations validate the effectiveness of our proposed algorithms.

The emerging paradigm of Network Function Virtualization (NFV) promises to shorten the renewal cycles of network functions and reduce the capital expenses by flexibly deploying virtualized network functions (VNFs) implementation on commodity servers. However, the required resource of each type (CPU, memory, etc.) for the running VNF should be provisioned to guarantee the performance when processing packets. This comes with different deployment cost, especially in a heterogeneous cloud consisting of a large number of network function platforms from various vendors. To optimally operate VNFs, it is necessary for the network operator to dynamically deploy VNFs in the expensive cloud infrastructures. In this article, we initiate the study of minimizing the deployment cost under multi-resource constraints in a heterogeneous cloud. We formulate multi-resource VNF deployment problem (MVDP) as an optimization program and prove its hardness. We propose an offline$(1, d+1)$-bicriteria approximation algorithm and an$(\mathcal {O}(1), \mathcal {O}(n \cdot \log n))$-competitive online algorithm to deploy VNFs in a scalable manner, where$d$is the number of resource types and$n$is the number of required VNFs. Large-scale simulations and DPDK-based OpenNetVM implementation show that our algorithms can reduce the overall cost by 34% and improve the performance in terms of multi-resource allocation.

Online bipartite matching has attracted wide interest since it can successfully model the popular online car-hailing problem and sharing economy. Existing works consider this problem under either adversary setting or i.i.d. setting. The former is too pessimistic to improve the performance in the general case; the latter is too optimistic to deal with the varying distribution of vertices. In this article, we initiate the study of the non-stationary online bipartite matching problem, which allows the distribution of vertices to vary with time and is more practical. We divide the non-stationary online bipartite matching problem into two subproblems, the matching problem and the selecting problem, and solve them individually. Combining Batch algorithms and deep Q-learning networks, we first construct a candidate algorithm set to solve the matching problem. For the selecting problem, we use a classical online learning algorithm, Exp3, as a selector algorithm and derive a theoretical bound. We further propose CDUCB as a selector algorithm by integrating distribution change detection into UCB. Rigorous theoretical analysis demonstrates that the performance of our proposed algorithms is no worse than that of any candidate algorithms in terms of competitive ratio. Finally, extensive experiments show that our proposed algorithms have much higher performance for the non-stationary online bipartite matching problem comparing to the state-of-the-art.

This paper considers the fundamental problem of deployment of Unmanned AerialVehIcles for aniSotropic monItoringTasks (VISIT), that is, given a set of objects with determined coordinates and directions in 2D area, deploy a fixed number of UAVs by adjusting their coordinates and orientations such that the overall monitoring utility for all objects is maximized. We develop a theoretical framework to address VISIT problem. First, we establish monitoring model whose quality of monitoring (QoM is anisotropic with monitoring angle and varying with various monitoring distance. To the best of our knowledge, we are the first considering the anisotropy of monitoring angle. Then, we propose a framework consisting of area discretization and Monitoring Dominating Set (MDS) extraction to reduce the infinite solution space of VISIT to a limited one with performance bound. Finally, we model the reformulated problem as maximizing a monotone submodular function subject to a matroid constraint, and present a greedy algorithm with$1-1/e-\epsilon$approximation ratio. We conduct both simulations and field experiments to evaluate our framework, and the results show that our algorithm outperforms comparison algorithms by at least 41.3 percent.

Network update enables Software-Defined Networks (SDNs) to optimize the data plane performance. The single update focuses on processing one update event at a time,i.e., updating a set of flows from their initial routes to target routes, but it fails to handle continuously arriving update events in time incurred by high-frequency network changes. On the contrary, the continuous update proposed in “Update Algebra” can handle multiple update events concurrently and respond to the network condition changes at all times. However, “Update Algebra” only guarantees the blackhole-free and loop-free update. The congestion-free property cannot be respected. In this paper, we propose Coeus to achieve the continuous update while maintaining consistency,i.e., ensuring the blackhole-free, loop-free, and congestion-free properties simultaneously. Firstly, we establish the continuous update model based on the update operations in update events. With the update model, we dynamically reconstruct the operation dependency graph (ODG) to capture the relationship between update operations and link utilization variations. Then, we develop a composition algorithm to eliminate redundant operations in update events. To further speed up the update procedure, we present a partition algorithm to split the operation nodes of the ODG into a series of suboperation nodes that can be executed independently. The partition algorithm is proven to be optimal. Finally, extensive evaluations show that Coeus can improve the update speed by at least 179% and reduce redundant operations by at least 52% compared with state-of-the-art approaches when the arrival rate of update events equals three times per second.

Network measurement provides operators an efficient tool for many network management tasks such as performance diagnosis, traffic engineering and intrusion prevention. However, with the rapid and continuous growth of traffic speed, it needs more computing and memory resources to monitor traffic in per-flow or per-packet granularity. Sample-based measurement systems (e.g., NetFlow, sFlow) have been developed to perform coarse-grained measurement, but they may miss part of records, especially for mice flows, which are important for some network management tasks (e.g., anomaly detection, performance diagnosis). To address these issues, data streaming algorithms such as hash tables and sketches have been introduced to balance the trade-off among accuracy, speed, and memory usage. In this article, we present a systematic survey of various data structures, algorithms and systems which have been proposed in recent years to perform fine-grained measurement for high-speed networks. We organize these methods and systems from a software-defined perspective. In particular, we abstract fine-grained network measurement into three-layer architecture. We introduce the responsibility of each layer and categorize existing state-of-the-art works into this architecture. Finally, we conclude the article and discuss the future directions of fine-grained network measurement.

With the increase of diversity in application needs and networks, existing congestion control algorithms (CCAs) do not accommodate this complicated reality. Previous classic CCAs are designed for a specific domain with fixed rules, failing to adapt to such diversities. Recently surged learning-based CCAs have great potential in adaptability and flexibility but are not practical due to unsatisfying performance on convergence, fairness, overhead and safety assurance. In this paper, we propose Libra, a unified congestion control framework, which empowers flexibility, adaptability, and practicality, by combining the wisdom of classic and reinforcement learning (RL)-based CCAs. Extensive evaluation of Libra's Linux kernel implementations on both live Internet and emulated networks shows performance improvement under dynamic networks (e.g., 1.2x throughput than Orca on average). At the same time, Libra can flexibly satisfy different application needs, reduce the running overhead by at most 0.92x and perform good fairness and convergence properties, well-fitting our theoretical analysis.

Multipath TCP (MPTCP) is a burgeoning transport protocol which enables the server to split the traffic across multiple network interfaces. Classic MPTCPs have good friendliness and practicality such as relatively low overhead, but are hard to achieve consistent high-throughput and adaptability, especially for the ability of flexibly balancing congestion among different paths. In contrast, learning-based MPTCPs can essentially achieve consistent high-throughput and adaptability, but have poor friendliness and practicality. In this paper, we proposed MPLibra, a combined multipath congestion control framework that can complement the advantages of classic MPTCPs and learning-based MPTCPs. Extensive simulations on NS3 show that MPLibra can achieve good performance and outperform state-of-the-art MPTCPs under different network conditions. MPLibra improves the throughput by 40.5% and reduces the file download time by 47.7% compared with LIA, achieves good friendliness and balances congestion timely.

Edge computing provides task offloading services to extend the computational capacity of mobile users and reduce task latency. The deadline-awareness offloading algorithm plays a key role in guaranteeing the quality of service (QoS) requirement. Prior studies mainly focus on tasks with strict deadlines. However, some tasks may not always have to be finished before hard deadlines, e.g., multimedia tasks. Tasks with soft deadlines can miss their primary deadlines, but not by too much. This has not been properly considered by existing offloading approaches. In this paper, we propose CONFECT to offload tasks with mixed deadlines. We formulate the problem and prove its hardness. Then, we propose two online algorithms with proven competitive ratios to solve the problem collectively, including an algorithm that assigns tasks to edge servers and an algorithm that adjusts the task execution order on each server. Extensive experiments show that CONFECT outperforms five baseline algorithms.

The increasing challenge in designing online algorithms lies in the distribution uncertainty. To cope with the distribution variations in online optimization, an intuitive idea is to reselect an algorithm from the candidate set that will be more suitable to future distributions. In this paper, we propose Ostasos, an automatic algorithm selection framework that can choose the most suitable algorithm on the fly with provable guarantees. Rigorous theoretical analysis demonstrates that the performance of Ostasos is no worse than that of any candidate algorithms in terms of competitive ratio. Finally, we apply Ostasos to the online car-hailing problem and trace-driven experiments verify the effectiveness of Ostasos.

State-of-the-art inter-datacenter WANs rely on centralized traffic engineering (TE) to improve the network performance, where TE computation is a periodical procedure and timely performs routing configurations (i.e., enforces TE polices via add, remove and modify forwarding rules) in response to the changing network conditions. The TE computation determines the routing configurations corresponding to the current network conditions and the network update operations change the routing configurations from last TE to current TE solution. Existing works take centralized TE computation and network update as two individual optimization procedures, which inevitably leads to suboptimal solution in the long run. In this paper we initiate the study of online joint optimization on TE computation and network update with the objective of minimizing the sum of TE cost and network update cost. We formulate this problem as an optimization program and propose a set of provable online algorithms with rigorous competitive and regret analysis. Trace-driven simulations on two empirical topologies demonstrate that our algorithms can significantly decrease the total cost.

Although the logically-centralized perspective is offered in Software-Defined Networking (SDN), the data plane is still distributed. Update commands sent by the centralized controller are executed asynchronously and independently in each switch. The timed SDN enables synchronous and coordinated update operations as each update command can be triggered by a pre-defined timestamp. Prior work on timed update mainly focuses on producing a congestion-free update sequence, whereas finding a congestion-free timed update sequence may prolong the update time. Even worse, such an update order may not exist. In this paper, we propose Chronus+, a novel timed update system that utilizes the switch buffer to shorten the update time while minimizing the switch buffer during updates. First, we formulate the Minimum Switch Buffer Problem (MSBP) as an integer linear programming and show its hardness. Then, we propose a set of efficient algorithms to solve the problem in polynomial time. Extensive evaluations in Mininet and large-scale simulations show that Chronus+can reduce the update time by at least 17% and the switch buffer size by at least 27% compared with state-of-the-art approaches.

This paper studies the problem of cHarging tAskScheduling for direcTional wireless chargEr networks (HASTE), i.e., given a set of rotatable directional wireless chargers on a 2D area and a series of offline (online) charging tasks, scheduling the orientations of all the chargers with time in a centralized offline (distributed online) fashion to maximize the overall charging utility for all the tasks. We prove that HASTE is NP-hard. Then, we prove that a relaxed version of HASTE falls within the realm of maximizing a submodular function subject to a partition matroid constraint, and propose a centralized offline algorithm that achieves$(1-\rho)(1-\frac{1}{e})$approximation ratio to address HASTE where$\rho$is the switching delay of chargers. Further, we propose a distributed online algorithm and prove it achieves$\frac{1}{2}(1-\rho)(1-\frac{1}{e})$competitive ratio. We conduct simulations and field experiments on a testbed consisting of eight off-the-shelf power transmitters and 8 rechargeable sensor nodes. The results show that our distributed online algorithm achieves 92.97 percent of the optimal charging utility, and outperforms the comparison algorithms by up to 15.28 percent in terms of charging utility.

Due to the distributed and asynchronous nature in data plane, the packets can be forwarded into a loop during routing updates. Software-Defined Networks (SDNs) enable a controller to schedule the update operations of routing rules in a loop-free manner. However, the existing rule replacement mechanism cannot give an efficient solution for large-scale update scenarios. In this paper, we make use of the ingress port field in forwarding rules to design a loop-free update scheme, Inport-Matching Update (IMU), for per-flow and destination-based unicast, which significantly improves efficiency of solving update scenarios and reduces update rounds. In both our proposed and previous mechanisms, a subproblem called Rule Replacement Scheduling (RRS) problem needs to be solved and we prove that the scale of RRS problem can be reduced at least by half. Moreover, we use the inclusion-exclusion principle to rigorously prove that the probability that an RRS problem under IMU has a trivial solution, i.e., one round, is always higher than 83.7%, given a random per-flow unicast update scenario with ingress port rules. Experimental results show that our proposed Inport-Matching Update mechanism remarkably reduces the average number of rounds and runtime for solving the RRS problem compared to the existing rule replacement mechanism.

Although the logically-centralized perspective is offered in Software-Defined Networks (SDNs), the data plane is still distributed in nature. Update commands sent by the centralized controller are executed asynchronously and independently in each switch. The timed SDNs enable synchronous and coordinate update operations as each update command can be triggered by a pre-defined time point. Prior work on timed update mainly focuses on how to produce a congestion-free update sequence, whereas finding a congestion-free timed update sequence may be too long to be applied in practice, even worse, such an update order may not exist. In this paper, we propose Chronus+, a timed update system that utilizes switch buffer to shorten the update time while minimizing the switch buffer size during updates. We formulate the Minimum Switch Buffer Size Problem (MSBSP) as an optimization program and show its hardness. A set of efficient algorithms is proposed to determine a timed update sequence in polynomial time. Extensive evaluations in Mininet and large-scale simulations show that Chronus+can reduce the update time by at least 17% and the switch buffer by at least 27% compared with state-of-the-art approaches.

Network update enables Software-Defined Networks (SDNs) to optimize the data plane performance via southbound APIs. The single update between the initial and the final network states fail to handle high-frequency changes or the burst event during the update procedure in time, leading to prolonged update time and inefficiency. On the contrary, the continuous update can respond to the network condition changes at all times. However, existing work, especially "Update Algebra" can only guarantee blackhole- and loop-free. The congestion-free property cannot be respected during the update procedure. In this paper, we propose Coeus, a continuous network update system while maintaining blackhole-, loop- and congestion-free simultaneously. Firstly, we establish an operation-based continuous update model. Based on this model, we dynamically reconstruct an operation dependency graph to capture unexecuted update operations and the link utilization variations. Subsequently, we develop an operation composition algorithm to eliminate redundant update commands and an operation node partition algorithm to speed up the update procedure. We prove that the partition algorithm is optimal and can guarantee the consistency. Finally, extensive evaluations show that Coeus can improve the makespan by at least 179% compared with state-of-the-art approaches when the arrival rate of update events equals to three times per second.

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.

Compared with hardware implementation, the software packet scheduler uses the packet queuing data structure and a ranking function according to different dimensions to flexibly determine the packet dequeue order, which can significantly shorten the renewal cycles and increase the function deployment flexibility. The key data structure in prior work either bounds the number of rank or suffers from high computation overhead. In addition, they only support a single dimension and do not scale well. In this paper, we present Proteus, a software packet scheduling system that supports multi-dimensional and arbitrary numbers of ranks. We design a k-dimension heap data structure and develop “push” and “pop” algorithms to perform “enqueue” and “dequeue” operations. Furthermore, we implement a prototype of Proteus in software switch. Extensive experiments on BESS and numerical simulations show that Proteus can decrease the computation overhead, save the storage space and run much faster than state of the art.

Text sentiment classification is of critical importance to improve the autonomous decision making and communication ability among object peers in the Social Internet of Things (SIoT). To classify sentiment polarity on a fine-grained level, aspect-level sentiment classification has become a promising direction in recent years. However, the existing solutions typically ignore the mutual information between sentences and their respective aspect terms while generally performing sentiment classification by using the simple attention mechanism. Thus, the relevant results seem to be unpromising. We aim to develop a novel neural-network-based model, by relying on the natural language processing model for rich feature extraction, called mutual attention neural networks (MANs), to conduct the aspect-level sentiment classification tasks in this article. Compared with the previous work, our proposed MAN model takes advantage of the bidirectional long short-term memory (Bi-LSTM) networks to obtain semantic dependence of sentences and their respective aspect terms, while learning the sentiment polarities of aspect terms in sentences by proposing the mutual attention mechanism. To evaluate the performance of MAN, we conduct our experiments on three real-world data sets, i.e., LAPTOP, REST, and TWITTER. The experimental results show that our proposed MAN model has significant performance improvements when compared to several existing models, in terms of aspect-level sentiment classification.

Today's cellular core relies on a few expensive and dedicated hardware racks to connect the radio access network and the egress point to the Internet, which are geographically placed at fixed locations and use the specific routing policies. This inelastic architecture fundamentally leads to increased capital and operating expenses, poor application performance and slow evolution. The emerging paradigm of Network Function Virtualization (NFV) and Software Defined Networking (SDN) bring new opportunities for cellular networks, which makes it possible to flexibly deploy service chains on commodity servers and fine-grained control the routing policies in a centralized way. We present a two-stage optimization framework Plutus. The network-level optimization aims to minimize the service chain deployment cost, while the server-level optimization requires to determine which Virtualized Network Function (VNF) should be deployed onto which CPU core to balance the CPU processing capability. We formulate these two problems as two optimization programs and prove their hardness. Based on parallel multi-block ADMM, we propose a (δ, 2)-bicriteria approximation algorithm and a learning-based algorithm to address two cases whether the flow information and the resource consumption can be known as a priori, respectively. Large-scale simulations and DPDK-based OpenNetVM platform show that Plutus can reduce the capital cost by 84% and increase the throughput by 36% on average.

This paper considers the problem of practical Heterogeneous wireless charger Placement with Obstacles (HIPO), i.e., given a number of heterogeneous rechargeable devices distributed on a 2D plane where obstacles of arbitrary shapes exist, deploying heterogeneous chargers with a given cardinality of each type, i.e., determining their positions and orientations, the combination of which we name as strategies, on the plane such that the rechargeable devices achieve maximized charging utility. After presenting our practical directional charging model, we first propose to use a piecewise constant function to approximate the nonlinear charging power, and divide the whole area into multi-feasible geometric areas in which a certain type of chargers have constant approximated charging power. Next, we propose the Practical Dominating Coverage Set extraction algorithm to reduce the unlimited solution space to a limited one by exacting a finite set of candidate strategies for all multi-feasible geometric areas. Finally, we prove the problem falls in the realm of maximizing a monotone submodular function subject to a partition matroid constraint, which allows a greedy algorithm to solve with approximation ratio of 1/2 - ε. We conduct experiments to evaluate the performance. Results show that our algorithm outperforms the comparison algorithms by at least 33.49 percent on average.

This paper concerns the problem of finding persistent items in distributed datasets, which has many applications such as port scanning and intrusion detection. To the best of our knowledge, there is no existing solution for finding persistent items in distributed datasets. In this paper, we propose DISPERSE, a probabilistic algorithm that can find persistent items in distributed datasets without collecting all the datasets. Our basic idea is that each monitor compresses each item ID in its dataset in a lossy fashion, sends the set of lossily compressed item IDs to the server, then the server recovers the IDs of the persistent items. We design the lossy compression so that given one lossily compressed item ID, the server cannot recover the item ID, but when the number of lossily compressed versions of the same item ID exceeds a threshold, which means that such items are persistent ones, the server can recover the item ID with a high probability. This threshold is exactly the threshold in the definition of persistent items. We implemented DISPERSE and evaluated its performance. In comparison with the straightforward solution, DISPERSE achieves a compression ratio of 26.5% with FNR=3.5% and FPR=0. In comparison with a developed Bloom filter based scheme and the adapted kBF and IBF schemes, our scheme can achieve 7.9, 5.7, and 6.6 times performance gains, respectively, in terms of compression ratio.

We consider a fundamental update problem of avoiding forwarding loops based on the node-ordering protocol in Software Defined Networks (SDNs). Due to the distributed data plane, forwarding loops may occur during the updates and influence the network performance. The node-ordering protocol can avoid such forwarding loops by controlling the update orders of the switches and does not consume extra flow table space overhead. However, an Ω(n) lower bound on the number of rounds required by any algorithm using this protocol with loop-free constraint has been proved, where n is the number of switches in the network. To accelerate the updates, a weaker notion of loop-freedom - relaxed loop-freedom - has been introduced. Despite that, the theoretical bound of the node-ordering protocol with relaxed loop-free constraint remains unknown yet. In this article, we solve a long-standing open problem: how to derive ω(1) -round lower bound or to show that O(1)-round schedules always exist for the relaxed loop-free update problem. Specifically, we prove that any algorithm needs Ω(log n) rounds to guarantee relaxed loop freedom in the worst case. In addition, we develop a fast relaxed loop-free update algorithm named Savitar that touches the tight lower bound. For any update instance, Savitar can use at most 2⌊log2n⌋ - 1 rounds to schedule relaxed loop-free updates. Extensive experiments on Mininet using a Floodlight controller show that Savitar can significantly decrease the update time, achieve near optimal performance and save over 30% of the rounds compared with the state of the art.

In memory computing and high-end distributed storage demand low latency, high throughput, and zero data loss simultaneously from datacenter networks. Existing reactive congestion control approaches cannot both minimize queuing latency and ensure zero data loss. A token-oriented proactive approach can achieve them together by controlling congestion even before sending data packets. However, state-of-the-art token-oriented approaches only strive to optimize network-level metrics: maximizing throughput while achieving flow-level fairness. This article answers the question of how to support objective-aware traffic scheduling in token-oriented approaches. The novelty of Token-Oriented in-network Prioritization (TOP) is that it prioritizes tokens instead of data packets. We make three contributions. Via simulations over a hypothetical TOP system, our first contribution is demonstrating the potential performance gain that can be brought by TOP. Second, we investigate the applicability of TOP. Although the overhead of enabling necessary TOP features in switches is trivial, we find that mainstream commodity datacenter switches do not support them. We hence propose a readily-deployable remedy to achieve in-network prioritization by pushing both switch and end-host hardware capacity to an extreme end. Lastly, we implement a running TOP system with Linux hosts and commodity switches, and evaluate TOP in testbeds and with large-scale simulations for various scenarios.

Remote Direct Memory Access(RDMA) technology rapidly changes the landscape of nowadays datacenter applications. Congestion control for RDMA networking is a critical challenge. As an end-to-end layer 3 congestion control mechanism, Datacenter QCN (DCQCN) alleviates the unfairness and head-of-the-line blocking problems of Priority-based Flow Control (PFC). However, a lossless network does not guarantee low latency even with DCQCN enabled. When network congestion happens, switch queues still build-up due to the response latency of end-to-end solutions. In this article, we propose Predictive PFC (P-PFC) to reduce tail latency in RDMA networks. P-PFC monitors the derivative of buffer occupation, predicts the happening of PFC trigger in the future, and proactively triggers PFC pause in advance. The benefit is that buffer usage can be maintained at a low level, hence the tail latency can be controlled. Preliminary evaluation results demonstrate that P-PFC can reduce tail latency by more than half of that in standard PFC in many scenarios, without hurting the throughput and average latency. P-PFC can also protect innocent flows compared with standard PFC according to our experiments. To our best knowledge, this is the first work of using derivative to improve PFC in lossless RDMA networks.

Due to the unpredictable update orders in the data plane, a transient forwarding loop may be introduced in Software Defined Networks (SDNs) during the updates, which can result in packet drops and influence the application performance. The node-ordering protocol is a major update mechanism without incurring extra flow table space overhead. Existing algorithms using this protocol with loop-free constraint require Ω(n)-round lower bound, where n is the number of switches in the network. To accelerate the updates, a weaker notion of loop-freedom - relaxed loop-freedom - has been introduced. However, many problems about the theoretical bound of the node-ordering protocol with relaxed loop-free constraint remain unsolved yet. In this paper, we provide a rigorous proof to derive a Ω (log n)-round lower bound for relaxed loop-free update problem, which closes a long-term open problem whether O(1)-round schedules always exist or not. In addition, we develop a fast relaxed loop-free update algorithm named Savitar that touches the tight lower bound. Specifically, we prove that Savitar can use at most 2⌊log2n⌋ - 1 rounds to guarantee relaxed loop-freedom for any update instance. Extensive experiments on Mininet using a Floodlight controller show that Savitar can significantly decrease the update time, achieve the near optimal solution and save the number of rounds over 30% compared with the state of the art.

Software-Defined Networks make it more principled and formal to operate and verify networks, which decouple the control plane and the data plane and introduce flexibility and programmability into the network. The SDN control plane needs to frequently update the data plane. However, the decoupled control and data planes face new challenges. The network is still an asynchronous distributed system in rule updates. If the update operations are not carefully scheduled, it may result in blackhole, congestions, and violate the consistency properties. Motivated by the tightly synchronized SDNs, we proposed TIDERS Algorithm for consistent network updates in "timed SDNs" - where one node update can be scheduled at specific time. In TIDERS, we use synchronized time technique to achieve fast network updates while guaranteeing consistency properties. We focus on congestion-free in scheduling the update operations. To achieve this, we first set up a flow-based dependency graph and transform it into switch-operation level dependency graph. Based on operation dependency graph, we generate an update schedule and gradually optimize it to finally get a fast update schedule. After that, we conduct a series of simulations comparing our approach with several other methods to evaluate it.

In this paper, we propose Deep-RL-a marking decision with Deep Reinforcement Learning (DRL) via per-port for solving the erroneously marking problems in multi-queue multi service scenarios of Data Center Networks (DCNs). We formulate the statement as a DRL problem and use Deep Neural Network (DNN) to achieve the best possible policy for the agent. In this way we can model the complex DCNs in order to obtain the optimal threshold in the output port when the marked packets from queue buffers are not a concern. Unlike prior research that focused on mathematical models or used machine learning in DCN, Deep-RL is a novel DRL based method, which optimizes the real value of threshold with continues action space. Thus, this fact makes our work incomparable with previous research. To the best of our knowledge, we are the first to discuss the problem with DRL and DNN. Simulation results demonstrate that Deep-RL utilizes the buffer capacity at exactly 30% and achieves near optimal flow completion time.

Virtualized network functions (VNFs) enable software applications to replace traditional middleboxes, which is more flexible and scalable in the network service provision. This paper focuses on ensuring Service Availability via Failure Elimination (SAFE) using VNF scaling, that is, given the resource requirements of VNF instances, finding an optimal and robust instance consolidation strategy, which can recover from one instance failure quickly. To address the above problem, we present a framework based on rounding and dynamic programming. First, we discretize the range of resource requirements for VNF instances deployment into several sub-ranges, so that the number of instance types becomes a constant. Second, we further reduce the number of instance types by gathering several small instances into a bigger one. Third, we propose an algorithm built on dynamic programming to solve the instance consolidation problem with a limited number of instance types. We set up a testbed to profile the functional relationship between resource and throughput for different types of VNF instances, and conduct simulations to validate our theoretical results according to profiling results. The simulation results show that our algorithm outperforms the standby deployment model by 27.33% on average in terms of the number of servers required. Furthermore, SAFE has marginal overhead, around 7.22%, compared to instance consolidation strategy without VNF backup consideration.

Today's data centers rely on scale-out architectures like fat-tree, BCube, VL2, etc. to connect a large number of commodity servers. It's important to balance the traffic load across the available links. Since the traditional electrical network cannot perfectly respond to the traffic variations in data centers, a growing trend is to introduce converters with adjustable optical links instead of adding more wiring links. However, little is known today about how to fully exploit the potential of the flexibility from the converters: the joint optimization on adjusting the optical links inside the converters and the routing in the whole network remains algorithmically challenging. In this paper, we initiate the study of dynamic load balancing problem (DLBP) in hybrid switching data center networks with converters. We design a set of specific converters for Diamond, VL2, BCube topologies to introduce more flexibility. Based on it, the connections of the optical links inside the converter and the route for each flow needs to be jointly optimized to minimize the maximum link utilization in the whole network. We formulate DLBP as an optimization program and prove that it's not only NP-hard, but also ρ-inapproximation. Further, we design a greedy algorithm to solve it. Extensive experiments show that our algorithm can reduce the traffic congestion by 12% on average.

Today's cellular core relies on a few expensive and dedicated hardware racks to connect the radio access network and the egress point to the Internet, which are geographically placed at fixed locations and use the specific routing policies. This inelastic architecture fundamentally leads to increased capital and operating expenses, poor application performance and slow evolution. The emerging paradigm of Network Function Virtualization (NFV) and Software Defined Networking (SDN) bring new opportunities for cellular networks, which makes it possible to flexibly deploy service chains on commodity servers and fine-grained control the routing policies in a centralized way.

Software-Defined Networks (SDNs) introduce great flexibilities in how packet routes can be defined and changed over time, and enable a more fine-grained and adaptive traffic engineering. The recently introduced support for more accurate synchronization in SDNs further improves the degree of control an operator can have over the packets' forwarding paths, and also allows to avoid disruptions and inconsistencies during network updates, i.e., during the rerouting of flows. However, how to optimally exploit such technology algorithmically - to efficiently schedule the update of multiple flows in such timed SDNs - while accounting for possible interference and congestion, is not well-understood today. We, in this paper, initiate the study of the fundamental problem of how to reroute the updates of multiple network flows in a synchronized SDN in a congestion-free manner. We rigorously prove that the problem is NP-hard for flows of unit size and network links with unit delay. We also show that a greedy approach to update the network can delay the update significantly. Our main contribution is the first solution to this problem: Chronicle. Our approach is based on time-extended network construction and the resource dependency graph, which is implemented by Openflow 1.5 using the scheduled bundles feature. The evaluation results show that Chronicle can reduce the makespan by 63% and reduce the number of changed rules by 50% compared to state-of-the-art.

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.

Recently, wireless power transfer technology (WPT) has attracted considerable attention and become a promising technology to prolong the lifetime of wireless sensor networks (WSNs) by providing perpetual energy to sensors. However, electromagnetic radiation (EMR) incurred by WPT is largely overlooked in most of the existing literature. In this article, we first propose and study the radiation constrained fair charging problem for WPT, i.e., maximizing the minimum utility of sensors by adjusting the power of wireless chargers with no EMR intensity at any location in the field exceeding a given threshold R t . To address this problem, we first adopt an area discretization method to transform it from nonlinear to linear. Then, we propose four algorithms to deal with the reformulated problem, i.e., 1/3 and 1/4 Approximation Algorithms, Primal-Dual algorithm, and area division algorithm. In particular, the area division algorithm is not only fully distributed but also provably achieves an approximation ratio of (1 − ϵ). Further, we conduct extensive simulations and build a field testbed to verify our theoretical findings. Our simulation results show that the approximation ratios of the proposed algorithms hold; the Primal-Dual and area division algorithms have comparable performance of the optimal results and outperform baseline algorithms obviously.

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.

ECN is a powerful tool that can achieve low latency and high throughput simultaneously. Support ECN for multiqueue scenarios is an industry trend in datacenter networks. However, ECN schemes developed for per-port marking cannot be applied directly to the multi-queue scenarios. It hurts at least one metric among latency, throughput, and the scheduling policy. State-of-the-art multi-queue ECN marking schemes each has its own limitations. In this paper, we present per-Port Marking with Selective Blindness (PMSB). The intuition is that: if a flow is found to be a victim of per-port marking, we can either revoke the marking or cancel the flow back-off even if its packets qualify the per-port threshold (i.e., selective blindness). By breaking the fixed causal relationship between ECN marking and flow backoff, flows from un-congested queues can be protected. We evaluate PMSB with large-scale NS-3 simulations. Our results demonstrate that PMSB can preserve a given scheduling policy. Compared with the current practice, PMSB can reduce the average/99% completion time for small flows by 64.49%/72.89% respectively while delivering a slightly better performance for large flows.

The advent of more accurate synchronization in Software-Defined Networks (SDNs) in general and the notion of timed updates in particular, enables operators to fully exploit the potential of the more fine-grained and adaptive traffic engineering, by avoiding disruptions and inconsistencies during the update. However, little is known today about how to schedule the update of multiple flows in such timed SDNs: As flows compete for limited resources, implementing a congestion-free update remains algorithmically challenging, even in timed SDNs. This paper initiates the study of the fundamental problem of how to reroute the update of multiple network flows in a synchronized SDN in a congestion-free manner. We show that that the problem is NP-hard already for flows of unit size and network links with unit delay. Our main contribution is a first solution for this problem: Chronicle. Our approach is based on a time-extended network construction and resource dependency graph, which is implemented by Openflow 1.5 using the scheduled bundles feature. Evaluation results show that Chronicle can reduce the makespan by 63% and reduce the number of changed rules by 50% compared to state-of-the-art.

Remote Direct Memory Access (RDMA) gains growing popularity in datacenter networks. The state-of-the-art congestion control scheme is DCQCN. However, DCQCN has performance problems when large-scale incast communication happens. DCQCN uses fixed period and steps for rate increase when probing for available bandwidth and this scheme is not scalable. Our key insight is that: senders should be aware of the scale of each incast, so that they can adjust their aggressiveness accordingly. The challenges come from different aspects. The scale of congestion is not easy to estimate while the control scheme should be cautiously designed. In this paper, we propose DCQCN+ to improve performance for large-scale incast congestion in RDMA networks. DCQCN+ adapts the rate control mechanisms to different scenarios. DCQCN+ can deal with incast congestion of at least 2,000 flows both in simulation and testbed. The scale is 10 times larger than that of DCQCN in simulation and 4 times larger in testbed. DCQCN+ also has 10 times smaller latency.

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.

Previous researches on (Virtualized Network Function)VNF deployment mainly focus on resource and VNF distribution given several candidate paths, whereas routing, though more practical, is not under consideration. Especially, resource distribution does not remain optimal given continuously coming flows with different characteristics. No quantitative approach is proposed to determine the timing to redistribute resources and functions while real-time adjusting network distribution is too expensive. In this paper, we claim an alternative approach to handle the resource-and-flow matching problem using the method of routing. We find a routing and evaluate its costs using our VNFs Routing Evaluation Model. We prove the NP-hardness of VNF - RE. While previous works focus on heuristic algorithms, whose performance cannot be proven, we propose a two phase approach and prove the approximation ratio. The problem is formulated as an optimization problem which jointly considers VNF covering, multi-resource consumption, and routing overhead. We prove that the problem is NP-hard and our solution 0 ((1 + (kD fmax /$D$−1)β)) log3$N$log m) approximates the optimal where k, Dfrnax and β are variables that depend on the input flow. The simulation compares our work with several representative heuristic algorithms and shows that VNF - RE has better performance.

This paper studies the problem of cHarging tAsk Scheduling for direcTional wireless chargEr networks (HASTE), i.e., given a set of rotatable directional wireless chargers on a 2D area and a series of offline (online) charging tasks, scheduling the orientations of all the chargers with time in a centralized offline (distributed online) fashion to maximize the overall charging utility for all the tasks. We prove that HASTE is NP-hard. Then, we prove that a relaxed version of HASTE falls within the realm of maximizing a submodular function subject to a partition matroid constraint, and propose a centralized offline algorithm that achieves (1-ρ)(1-1/e) approximation ratio to address HASTE where ρ is the switching delay of chargers. Further, we propose a distributed online algorithm and prove it achieves 1/2(1-ρ)(1-1/e) competitive ratio. We conduct simulations, and field experiments on a testbed consisting of 8 off-the-shelf power transmitters and 8 rechargeable sensor nodes. The results show that our distributed online algorithm achieves 92.97% of the optimal charging utility, and outperforms the comparison algorithms by up to 26.19% in terms of charging utility.

This paper proposes a new counter architecture for network measurement called Cache Assisted and randomizEd ShAring counteRs (CAESAR). One of the greatest challenges for per-flow traffic measurement is designing an online measurement module to keep up with the rapid growth of link speed. To address this challenge, we use a fast on-chip memory as the cache before the slow off-chip SRAM counters, thereby decreasing the accesses per flow to off-chip counters to improve time efficiency without any packet loss. We use randomized sharing counters among multiple flows in SRAM to achieve a compact data structure with high storage efficiency. By removing the impact from other flows sharing counters with a specific flow, we theoretically analyze the expectation and confidence interval of its estimated flow size accurately. In this paper, we use the real-world network traces for software simulations and FPGA experiments on the Xilinx Virtex-7 FPGA chip to validate our theoretical findings. The results show that CAESAR is up to 92.4% and 90% faster than prior work CASE and RCS respectively, and CAESAR reduces the average relative error of CASE and RCS by more than half.

This paper considers the problem of Heterogeneous wIreless charger Placement with Obstacles (HIPO), i.e., given a number of heterogeneous rechargeable devices distributed on a 2D plane where obstacles of arbitrary shapes exist, deploying heterogeneous chargers with a given cardinality of each type, i.e., determining their positions and orientations, the combination of which we name as strategies, on the plane such that the rechargeable devices achieve maximized charging utility. After presenting our practical directional charging model, we first propose to use a piecewise constant function to approximate the nonlinear charging power, and divide the whole area into multi-feasible geometric areas in which a certain type of chargers have constant approximated charging power. Next, we propose the Practical Dominating Coverage Set extraction algorithm to reduce the unlimited solution space to a limited one by exacting a finite set of candidate strategies for all multi-feasible geometric areas. Finally, we prove the problem falls in the realm of maximizing a monotone submodular function subject to a partition matroid constraint, which allows a greedy algorithm to solve with approximation ratio of 1/2 -- ϵ. We conduct both simulations and field experiments to evaluate the performance of our algorithm and other five comparison algorithms. The results show that our algorithm outperforms the comparison algorithms by at least 33.49% on average.

Software-Defined Networks (SDNs) introduce interesting new opportunities in how network routes can be defined, verified, and changed over time. Yet despite the logically-centralized perspective offered, an SDN still needs to be considered a distributed system: rule updates communicated from the controller to the individual switches traverse an asynchronous network and may arrive out-of-order, and hence lead to (temporary or permanent) inconsistencies. Accordingly, the consistent network update problem has recently received much attention. Motivated by the advent of tightly synchronized SDNs, we in this paper initiate the study of algorithms for consistent network updates in “timed SDNs”-SDNs in which individual node updates can be scheduled at specific times. This paper presents Chronus, which is based on provably congestion- and loop-free update scheduling algorithms, and avoids the flow table space headroom required by existing two-phase update approaches. We formulate the Minimum Update Time Problem (MUTP) as an optimization program. We propose a tree algorithm to check the feasibility and a greedy algorithm to find a update sequence in polynomial time. Extensive experiments on Mininet and numerical simulations show that Chronus can substantially reduce transient congestion by 75% and save over 60% of the rules compared to the state of the art.

Recently wireless power transfer technology (WPT) attracts considerable attention, its incurred electromagnetic radiation (EMR), however, is largely overlooked by most existing literatures. In this paper, we first propose and study the radiation constrained fair wireless charging problem, i.e., maximizing the minimum utility of devices by adjusting the power of wireless chargers with no EMR intensity at any location in the field exceeding a given threshold . To address this problem, we first adopt an area discretization method to transform it from nonlinear to linear. Then, we propose two algorithms to deal with the reformulated problem. One is called Primal-Dual algorithm, which is semi-distributed and uses lagrangian dual and subgradient methods to solve the problem iteratively. The other is called area division algorithm. It is not only fully distributed and scalable with network size, but also provably achieves an approximation ratio of (1- ϵ). We conducted extensive simulations and built a field test-bed to verify our theoretical findings. Our simulations show that the approximation ratio of the area division algorithm holds; the Primal-Dual and area division algorithms can have comparable and over 90.9% performance of the optimal results, respectively; and both of the algorithms outperform a baseline algorithm by more than 37%.

Software-defined networks (SDNs) introduce interesting new opportunities in how network routes can be defined, verified, and changed over time. Despite the logically-centralized perspective offered, however, an SDN still needs to be considered a distributed system: rule updates communicated from the controller to the individual switches traverse an asynchronous network and may arrive out-of-order. This can lead to (temporary or permanent) inconsistencies and triggered much research over the last years. We, in this paper, initiate the study of algorithms for consistent network updates in “timed SDNs”-SDNs in which individual node updates can be scheduled at specific times. While technology enabling tightly synchronized SDNs is emerging, the resulting algorithmic problems have not been studied yet. This paper presents, implements and evaluates Chronus, a system which provides provably congestion- and loop-free network updates, while avoiding the flow table space headroom required by existing two-phase update approaches. We formulate the minimum update time problem as an optimization program and propose two polynomial-time algorithms which lie at the heart of Chronus: a decision algorithm to check feasibility and a greedy algorithm to find a good update sequence. Extensive experiments on Mininet and numerical simulations show that Chronus can substantially reduce transient congestion and save over 60% of the rules compared with the state of the art.

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.

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.