Haoliang Huang, Zihuang Cai, Zhuo Tang, Yifan Liu, Chen Tian, Kenli Li, Changjian Chen. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026.

Large language model (LLM) training is prone to anomalies due to its long duration and large scale, which can lead to significant performance degradation or even training crashes. Due to the synchronization nature of LLM training, anomalies exhibit the cascading effect, making their diagnosis challenging. Existing approaches rely on collecting communication operator information via code instrumentation, which yields only coarse-grained monitoring data and requires modifications to training code or communication libraries. We propose Pulse, a fine-grained, non-intrusive, and easy-to-deploy monitoring system. Our key idea is to enable fine-grained monitoring via traffic measurement. Pulse conducts microsecond-level RDMA traffic measurement on NICs, and transforms flow-level measurements into communication operator measurements, thereby enabling fine-grained and non-intrusive monitoring. We deploy Pulse on a testbed with 64 H200 GPUs and evaluate its anomaly localization capability under common failure scenarios. Pulse achieves machine-level localization in 10 out of 12 scenarios, while existing methods succeed in only 4 and even misdiagnose 2 of the remaining scenarios. Additionally, Pulse achieves over 90% precision and 100% recall, supports up to 2000 concurrent RDMA flow measurements per NIC, and imposes negligible overhead on training performance, making it a practical solution for real-world LLM training environments.

Range-top-k queries retrieve the top-k elements within an arbitrary subrange of a large array and are a key primitive in real-time analytics. Unlike one-shot top-k selection, practical deployments issue large volumes of queries over varying and often overlapping ranges, frequently interleaved with streaming updates. In this setting, applying conventional GPU top-k kernels per query is inefficient: each query triggers range rescans or O(n)-scale passes that overwhelm HBM bandwidth, thrash on-chip caches, and provide little reuse across overlapping windows.

Large Language Model (LLM) inference has emerged as a fundamental paradigm, however, variations in output length cause severe workload imbalance in the decode phase, particularly for long-output reasoning tasks. Existing systems, such as PD disaggregation architectures, rely on static prefill-to-decode scheduling, which often results in SLO violations and OOM failures under evolving decode workloads. In this paper, we propose STAR, a decode rescheduling system powered by length prediction to anticipate future workloads. Our core contributions include: (1) A lightweight and continuous LLM-native prediction method that leverages LLM hidden state to model remaining generation length with high precision (reducing MAE by 49.42%) and low overhead (cutting predictor parameters by 93.28%); (2) A rescheduling solution in decode phase with a dynamic balancing mechanism that integrates current and predicted workloads, reducing P99 TPOT by 75.1% and achieving 2.63 × higher goodput.

Training large language models faces frequent interruptions due to various faults, demanding robust fault-tolerance. Existing backup-free methods, such as redundant computation, dynamic parallelism, and data rerouting, each incur performance penalties, whether from ongoing overhead, lengthy reconfigurations, or post-recovery inefficiencies. We propose Chameleon, an adaptive fault-tolerant system that intelligently selects optimal recovery strategies when a failure occurs. Chameleon achieves this through a unified performance model, expedient execution plan search, accurate performance estimation, and efficient communication optimizations. Experiments on a 32-card cluster show that Chameleon maintains a performance gap of within 11.00% between post-recovery and failure-free training, while preserving model convergence and efficient memory usage. Compared to state-of-the-art methods, Chameleon achieves up to 1.229x and 1.355x higher average throughput than Oobleck and Recycle, respectively.

RFID has revolutionized item-level intelligence in IoT ecosystems, yet static localization with passive tags remains challenging due to multipath interference inherent in RF signals. We present LuxTag, the first system to enable visible light-based sensing and localization using standard, commercial RFID tags by transforming them into ambient light sensors. Our key insight leverages the discovery that photon-induced leakage currents in passive RFID ICs modulate their persistence time (i.e., the duration a tag remains operational after RF excitation ceases) proportional to ambient illuminance. LuxTag introduces two innovations: (i) a first-principles model characterizing how ambient light alters tag persistence time, enabling battery-free light sensing without hardware modifications; (ii) a differential measurement technique and zero-shot calibration method to isolate light effects and autonomously derive tag parameters, ensuring robust and accurate static localization system using COTS RFID infrastructure. Extensive experiments demonstrate that LuxTag achieves a mean light intensity error of 3.6 lux and 60.7% improvement over state-of-the-art static RFID localization. By synergizing the ubiquity of RFID with the multipath resilience of optical sensing, LuxTag opens new avenues for static RFID localization in smart warehouses, retails, and beyond.

From the perspective of user experience, when optimizing resource provisioning in networks, we have to maximize social utility, which is an abstraction of what users can obtain from the service provided by a network. In quantum networks, unlike their counterparts, circuit-switched classical networks, (i) the utility obtained by a demand is not always concave for the number of Entanglement Connections (ECs) we provision to it; and (ii) each demand requires a different amount of quantum resources over each link along the path to establish an EC. As a result, the Social Utility Maximization (SUM) problem is more challenging than in classic circuit-switched networks. In this paper, we propose an approach also called SUM to maximize social utility in quantum networks by provisioning an appropriate number of ECs (and corresponding resources) to demands. We first formulate the SUM problem and analyze it based on Lagrangian relaxation and duality techniques. Accordingly, we derive the optimal EC provisioning scheme for a given Lagrangian multiplier, depending on whether the utility function of each demand is convex, concave, or sigmoid-like. After that, a primal-dual iteration algorithm is proposed to determine the optimal EC provisioning scheme to maximize social utility. We conduct extensive simulations to demonstrate that SUM outperforms the state-of-the-art approach to maximizing quantum network throughput,i.e., EFiRAP, by up to 58.4%.

As large language models (LLMs) increasingly integrate into every aspect of our work and daily lives, there are growing concerns about user privacy, which push the trend toward local deployment of these models. There are a number of lightweight LLMs (e.g., Gemini Nano, LLAMA2 7B) that can run locally on smartphones, providing users with greater control over their personal data. As a rapidly emerging application, we are concerned about their performance on commercialoff- the-shelf mobile devices. To fully understand the current landscape of LLM deployment on mobile platforms, we conduct a comprehensive measurement study on mobile devices. While user experience is the primary concern for endusers, developers focus more on the underlying implementations. Therefore, we evaluate both user-centric metrics-such as token throughput, latency, and response quality-and developer-critical factors, including resource utilization, OS strategies, battery consumption, and launch time. We also provide comprehensive comparisons across the mobile system-on-chips (SoCs) from major vendors, highlighting their performance differences in handling LLM workloads, which may help developers identify and address bottlenecks for mobile LLM applications. We hope that this study can provide insights for both the development of on-device LLMs and the design for future mobile system architecture.

Node-centric Data Centers (NDCs) are highly flexible, cost-efficient, and failure-resilient, and have gained growing popularity in recent years. However, RDMA technology used in NDC still faces challenges, including high retransmission overhead, Head-of-Line Blocking (HoLB) and deadlock problems. Existing solutions for traditional data centers cannot simultaneously address these issues due to the unique topology and server transmission characteristics of NDC. In this paper, we propose a per-port flow control named PortFC for NDC. PortFC addresses the above problems through the designs of a Pause/Resume control signal, a per-port queue allocation method, an egress-detecting per-port flow control mechanism, and a server-aware queue scheduling method. Our evaluation shows that PortFC is free from retransmission, capable of eliminating HoLB and avoiding deadlocks. PortFC achieves 1.7-8.0 times higher throughput and reduces latency by 11.7%-87.7% compared to the state-of-the-art lossy RDMA based on IRN and the lossless RDMA method based on PFC. In particular, PortFC still demonstrates good performance in a Rail-only NDC with heterogeneous bandwidth domains.

Many proposals have demonstrated the efficiency advantages of software-defined networking (SDN) in managing data center networks. Common practices employ centralized traffic engineering (TE) in the SDN control plane to optimize load balancing and throughput. Meanwhile, for high availability purposes, the control plane is partitioned to ensure the impact of a single faulty controller is contained. However, the interaction between these two aspects is often overlooked. In particular, we show that the current control plane partitioning approach leads to imbalanced link loads and degraded application performance. To address this issue, we proposevirtual slicing, a new control plane partitioning scheme. Virtual slicing achieves desirable traffic engineering performance while retaining the availability guarantees from the current approach. Virtual slicing is implemented and evaluated with real-world and synthetic traffic traces on production spine-free data center networks. Results show that virtual slicing reduces tail link utilizations by up to 28.4%, and improves flow completion times by up to 36%.

Distributed AI model training generates bursty, low-entropy elephant flows that challenge existing single-path transport protocols in multi-stage Clos networks, leading to congestion and inefficiency. Multipath transport emerges as a promising solution, leveraging multiple paths to balance traffic and enhance resilience. However, current multipath RDMA solutions suffer from scalability, congestion control, and load-balancing inefficiencies. This paper introduces Unified Delay-driven Multipath Protocol (UDMP), a novel approach that co-designs congestion control and load balancing using network delay as a unified signal. UDMP employs delay-gradient-based congestion control to precisely resolve unavoidable congestion. Moreover, UDMP leverages delay-assisted load balancing to shift traffic across paths with minimal latency adaptively, maintaining throughput when encountering avoidable congestion. A novel Token Pool design integrates these components, eliminating per-path state overhead while achieving fine-grained traffic distribution. Implementations on DPDK and NS3 demonstrate that UDMP achieves up to 2x higher throughput and reduces flow completion times by up to 30% compared to state-of-the-art methods like MPRDMA and QP-Scaling. These results highlight UDMP’s effectiveness in meeting the stringent performance requirements of modern distributed AI training workloads.

In modern GPU-centric clusters, large-scale AI training relies on two distinct communication domains: a high-bandwidth intra-node domain using proprietary interconnects (e.g., NVLink), and a scale-out inter-node network domain (e.g., RDMA). We observe that the widely-used ring algorithm, often create a significant load imbalance across these domains. This leads to the counter-intuitive scenario where the expensive, high-bandwidth intra-node domain becomes a performance bottleneck, while the inter-node network remains underutilized. This inefficiency is further exacerbated by the disparity in bandwidth provisioning: inter-node network bandwidth is generally more cost-effective and accessible, whereas intra-node bandwidth is often proprietary and more costly to scale. To address this fundamental imbalance, we propose RAIL, aimed at resolving the intra-node bottleneck by strategically rearranging inter-GPU communication paths. This rebalancing ensures that traffic loads are appropriately matched with the distinct transmission capabilities of each domain, thereby maximizing overall communication performance. RAIL incorporates a Load Distributing Strategy (LDS) that can accurately partition physical nodes into logical nodes based on the a transmission capabilities of both domains, shifting excess traffic from the overloaded intra-node domain to the underutilized network domain. Additionally, the Intra-Rail Strategy (IRS) leverages topological characteristics to ensure optimal communication paths through the network domain between logical nodes. Our evaluation demonstrates that RAIL effectively mitigates congestion and achieves a 30.7% average increase in collective communication bus bandwidth compared to the widely-used NCCL solution.

Conventional entanglement routing approaches decide the Entanglement Paths (EPs) to establish Entanglement Connections (ECs) before trying to create Entanglement Links (ELs). By doing so, very few EL failures will result in a low network throughput. In this paper, we study how to choose the EPs to establish ECs after knowing which ELs are successfully created. This is called the Deferred EP Selection (DEPS) problem. DEPS is a generalized integer multi-commodity flow problem and we cannot solve it quickly with conventional optimization methods. To address this issue, we propose a Deep Reinforcement Learning based EP Selection (DRLEPS) approach. The salient features of DRLEPS include (i) by controlling the number of candidate EPs, DRLEPS can achieve a trade-off between time complexity and the EC establishment rate; and (ii) using candidate EPs as input, DRLEPS is robust to request variation; and (iii) by training neural networks with different topologies, a model derived by DRLEPS can be applied to various networks (even with a different number of nodes) without fine-tune. Through extensive simulations, we show that even in a network with 200 nodes, DRLEPS can solve the DEPS problem in 0.39 seconds with a Nvidia GeForce 3090 GPU. It outperforms the approach always establishing ECs through the EP with the largest success probability by up to 23.4% in EC establishment rate. It also outperforms the Integer Linear Programming (ILP) based scheme, which can achieve the maximum EC establishment rate, by up to 184.2x in network throughput.

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.

Entanglement routing plays a vital role in supporting various applications in quantum networks. Existing works on entanglement routing either ignored the Entangled Photon Source (EPS) placement issue or simply assumed a pool of EPSes at a centralized location that can provision entanglement over arbitrary quantum links. In this paper, we propose LIGHTER and fidelity-aware LIGHTER (named F-LIGHTER) to solve the joint EPS placement and entanglement routing problem based on the assumption that EPSes are co-located with quantum nodes and each EPS can send one entangled photon at a time to one of its adjacent nodes only. The salient features of LIGHTER and F-LIGHTER include (i) LIGHTER and F-LIGHTER use a demand-agnostic EPS placement scheme to maximize network throughput and fairness for all feasible Entanglement Connection EC) establishment demands, and (ii) most requested ECs can be established over Entanglement Paths (EPs) determined offline, and only a small percentage of them will be established over online calculated EPs, resulting in fast and efficient entanglement routing. Extensive simulations show that compared with schemes without proper EPS placement or entanglement routing, LIGHTER can improve the network throughput by up to 175.6% and 37.0%, respectively. When the fidelity is considered, the network throughput improvement achieved by F-LIGHTER will be up to 135.0% and 21.5%, respectively.

Recent advancements in deep learning have significantly increased AI processors' energy consumption, which is becoming a critical factor limiting AI development. Dynamic Voltage and Frequency Scaling (DVFS) stands as a key method in power optimization. However, due to the latency of DVFS control in AI processors, previous works typically apply DVFS control at the granularity of a program's entire duration or sub-phases, rather than at the level of AI operators.

With the rise of deep learning, many companies have developed domain-specific architectures (DSAs) optimized for AI workloads, with Ascend being a representative. To fully realize the operator performance on Ascend, effective analysis and optimization is urgently needed. Compared to GPU, Ascend requires users to manage operations manually, leading to complex performance issues that require precise analysis. However, existing roofline models face challenges of visualization complexity and inaccurate performance assessment. To address these needs, we introduce a component-based roofline model that abstracts components to capture operator performance, thereby effectively identifying bottleneck components. Furthermore, through practical operator optimization case studies, we illustrate a comprehensive process of optimization based on roofline analysis, summarizing common performance issues and optimization strategies. Finally, extensive end-to-end optimization experiments demonstrate significant model speed improvements, ranging from 1.07× to 2.15×, along with valuable insights from practice.

Cloud providers require high-throughput traffic to test the effectiveness of congestion control (CC) configurations (i.e., CC algorithm selection and their parameter settings) in networks. A network tester capable of evaluating CC configurations needs to fulfill the following requirements: (R1) Capable of generating traffic with CC behaviors. (R2) Ability to customize CC algorithms. (R3) High throughput CC traffic generation. However, existing network testers fail to meet these requirements simultaneously. The paper presents Marlin, a novel high-throughput network tester designed for CC evaluation. Marlin leverages a high-throughput, low-programmability device to amplify the traffic generated by a low-throughput, high-programmability device. The low-throughput device is responsible for complex computational tasks, such as running CC and flow scheduling algorithms, and communicates with the high-throughput device at a high frequency using small packets to instruct it to generate high-throughput traffic with CC behaviors. This hybrid approach allows for customizable, high-throughput CC testing. Our experiments demonstrate that Marlin can accurately emulate CC behaviors and replicate real-world scenarios. Marlin can generate 1.2 Tbps of CC traffic using a single programmable switch pipeline and one 100 Gbps port of an FPGA NIC, supporting up to 65,536 concurrent flows.

Random walks are a primary means for extracting information from large-scale graphs. While most real-world graphs are inherently dynamic, state-of-the-art random walk engines failed to efficiently support such a critical use case. This paper takes the initiative to build a general random walk engine for dynamically changing graphs with two key principles: (i) This system should support both low-latency streaming updates and high-throughput batched updates. (ii) This system should achieve fast sampling speed while maintaining acceptable space consumption to support dynamic graph updates. Upholding both standards, we introduce Bingo, a GPU-based random walk engine for dynamically changing graphs. First, we propose a novel radix-based bias factorization algorithm to support constant time sampling complexity while supporting fast streaming updates. Second, we present a group-adaption design to reduce space consumption dramatically. Third, we incorporate GPU-aware designs to support high-throughput batched graph updates on massively parallel platforms. Together, Bingo outperforms existing efforts across various applications, settings, and datasets, achieving up to a 271.11x speedup compared to the state-of-the-art efforts.

In data center networks, various types of traffic with strict performance requirements operate simultaneously, necessitating effective isolation and scheduling through priority queues. However, most switches support only around ten priority queues. Virtual priority can address this limitation by emulating multi-priority queues on a single physical queue, but existing solutions often require complex switch-level scheduling and hardware changes. Our key insight is that virtual priority can be achieved by carefully managing bandwidth contention in a physical queue, which is traditionally handled by congestion control (CC) algorithms. Hence, the virtual priority mechanism needs to be tightly coupled with CC. In this paper, we propose PrioPlus, a CC enhancement algorithm that can be integrated with existing congestion control schemes to enable virtual priority transmission. PrioPlus assigns specific delay ranges to different priority levels, ensuring that flows transmit only when the delay is within the assigned range, effectively meeting virtual priority requirements. Compared to Swift CC with physical priority queues, PrioPlus provides strict priority for high-priority flows without impacting performance sensibly. Meanwhile, it benefits low-priority flows from 25% to 41% as its priority-aware design enhances CC's ability to fully utilize available bandwidth once higher-priority traffic completes. As a result, in coflow and model training scenarios, PrioPlus improves job completion times by 21% and 33%, respectively, compared to Swift with physical priority queues.

BCube is a modular data center network.Compared with other topologies, BCube has natural advantages, such as lower deployment costs and stronger failure recovery capabilities.However, RDMA technology used in BCube still faces challenges, including high retransmission overhead, Head-of-Line Blocking (HoLB) and deadlock problems.Existing solutions for traditional data centers cannot simultaneously address these issues due to the unique topology and server transmission characteristics of BCube.In this paper, we propose a per-port flow control named PortFC for BCube.PortFC addresses the above problems through the designs of a Pause/Resume control signal, a per-port queue allocation method, an egress-detecting per-port flow control mechanism, and a serveraware queue scheduling method.Our evaluation shows that PortFC is free from retransmission, capable of eliminating HoLB and avoiding deadlocks.PortFC achieves 1.7-8.0times higher throughput and reduces latency by 11.7%-87.7%compared to the state-of-the-art

The Louvain algorithm is one of the most popular algorithms for community detection. Observing that existing implementations suffer from inaccurate pruning and inefficient intermediate state management, we introduce GALA, GPU-Accelerated Louvain Algorithm, which incorporates two key innovations. The first innovation is a novel modularity gain-based pruning strategy, supported by rigorous theoretical guarantees of optimality and able to reduce up to 76% of vertices as well as their corresponding computations. To take advantage of the memory hierarchy and parallelism of GPUs, the second innovation is workload-aware kernels, featuring a shuffle-based kernel founded on the warp-level primitives for exchange states and a hash-based kernel that prioritizes shared memory in hashtable design. GALA further scales to multiple GPUs by minimizing the synchronization overhead between GPUs through a dense-sparse synchronization strategy. We evaluate the performance of GALA through theoretical analysis and practical experiments on various real-world graphs. The experimental results confirm that GALA significantly improves the performance of the parallel Louvain algorithm on GPUs, surpassing state-of-the-art solutions by 6× on average.

The flourishing of Large Language Models (LLMs) calls for increasingly ultra-scale training. In this paper, we share our experience in designing, deploying, and operating our novel Astral datacenter infrastructure, along with operational lessons and evolutionary insights gained from its production use. Astral has three important innovations: (i) a same-rail interconnection network architecture on tier-2, which enables the scaling of LLM training. To physically deploy this high-density infrastructure, we introduce a distributed high-voltage direct current power system and a new air-liquid integrated cooling system. (ii) a full-stack monitoring system featuring cross-host and hierarchical logging correlation, which diagnoses failures at scale and precisely localizes root causes. (iii) an operator-granular forecasting component Seer that efficiently generates operator execution timelines with acceptable accuracy, aiding in fault diagnosis, model tuning, and network architecture upgrading. Astral infrastructure has been gradually deployed over 18 months, supporting LLM training and inference for multiple customers.

Root causing and failure localization are critical to maintain reliability in cloud network operations. When an incident is reported, network operators must review massive volumes of monitoring data and identify the root cause (i.e., error device) as fast as possible, making it extremely challenging even for experienced operators. Large language models (LLMs) have shown great potential in text understanding and reasoning. In this paper, we present BiAn, an LLM-based framework designed to assist operators in efficient incident investigation. BiAn processes monitoring data and generates error device rankings with detailed explanations. To date, BiAn has been deployed in our network infrastructure for 10 months and it has successfully assisted operators in identifying error devices more quickly, reducing time to root causing by 20.5% (55.2% for high-risk incidents). Extensive performance evaluations based on 17 months of real cases further demonstrate that BiAn achieves accurate and fast failure localization. It improves accuracy by 9.2% compared to the baseline approach.

Payment channel networks (PCNs) offer a crucial solution to the scalability challenges of blockchain-based transaction systems. However, most existing PCN routing protocols employ a “guess-and-check” approach, which undermines their transaction success rate and efficiency. In this paper, we propose a routing protocol named RCS, based on a novel “Refined Confirm-and-Send” approach. Utilizing PCN topology statistics, RCS performs a refined probing of possible transaction paths and verifies whether a path has sufficient available balance before executing the transaction through it. This method effectively improves the transaction success rate while maintaining restrained overhead. Additionally, to address users' privacy concerns, we design a privacy-preserving version of RCS, named RCS+. RCS+ uses secure comparisons to identify paths with sufficient funds without disclosing channel balances or transaction amounts. Extensive simulations with real-world and synthetic datasets demonstrate that RCS and RCS+ outperform existing state-of-the-art protocols. RCS and RCS+ achieve a$\mathbf{1 0 \%}$higher transaction success rate compared to the Shortest Path approach, which serves as the core of Lightning Network's current routing mechanism. In terms of overhead, RCS maintains the lowest cost among all tested protocols, e.g., only 20 % of the Flash protocol. While RCS+ incurs marginally higher overhead due to its enhanced privacy guarantees, its cost remains just 30 % of Flash's overhead. Furthermore, RCS/RCS+ exhibits robust adaptability to dynamic changes in PCN topologies, ensuring scalability as the network evolves.

The wireless communication network, comprising billions of cloud, edge, and end devices, enables emerging applications such as the metaverse—an immersive virtual environment where experiences and user interactions converge. However, user interactions in the metaverse generate substantial amounts of private data (e.g., identity, location), raising significant privacy concerns despite their utility in training machine learning models. Artificial Intelligence of Things (AIoT) offers solutions to these challenges, with Federated Learning (FL) serving as a decentralized framework that enables collaborative model training without exposing local data. Nevertheless, deploying FL in large-scale environments like the metaverse increases vulnerability to malicious attacks. To address this issue, we propose a blockchain-based FL architecture that enhances trust and security. The architecture integrates a multi-task FL strategy with blockchain sharding to boost system throughput and reduce resource consumption. By partitioning the blockchain into smaller shards, we lower computational demands and enable concurrent training of multiple models, improving efficiency. We also design a shard creation algorithm based on bipartite matching and a bandwidth scheduling mechanism that prioritizes reliable devices with informative data. Experimental results show that our architecture outperforms existing baselines across multiple evaluation metrics.

Monotonic graph algorithms, such as shortest path, BFS, and reachability, are fundamental to graph analytics and are widely used across domains. Recent systems employ pruning techniques to accelerate the processing of these algorithms. However, state-of-the-art monotonic graph engines are restricted to in-memory execution and cannot scale to graphs that exceed main memory capacity. In contrast, existing out-of-core graph engines are designed for general-purpose workloads and lack effective pruning mechanisms tailored to monotonic graph algorithms. To bridge this gap, we present Gem, an out-of-core graph engine designed for monotonic graph algorithms. Gem introduces a PageRank-based graph sketch that captures key topological features inmemory with minimal preprocessing overhead. Building on this sketch, we propose a novel graph abstraction that enables the direct derivation of tight bounds for monotonic graph algorithms, supporting effective pruning at both the vertex and partition levels. Comprehensive evaluations on six real-world datasets, including the 42.5-billion-edge ClueWeb graph, show that Gem significantly outperforms existing systems. It achieves up to 135.40× speedup over GridGraph and 12.58× over Wonderland in out-of-core settings, and also delivers substantial improvements in other modes: up to 10.41× over RisGraph in memory and 20.64× over CGgraph out-of-GPU memory.

Graph data analysis, particularly local triangle counting, plays a pivotal role in deciphering complex relationships within graph data. This method is invaluable across diverse fields such as social networks, transportation, and cybersecurity. However, this process often involves handling sensitive information, necessitating that the relationship between any two nodes is considered private. Differential privacy (DP) is a formal model to address privacy concerns and can be categorized into two types: the central DP (CDP) model, which achieves better result accuracy, and the local DP (LDP) model, which does not assume a trusted server. To bridge the gap between the two models, we propose Sectric, a server-aided crypto-assisted local triangle counting protocol, in this paper. It can achieve the same result accuracy with the same privacy budget as the CDP model without assuming a trusted server. Sectric also explores a new approach in crypto-assisted graph data analysis algorithms that represents a node's neighbors using a set instead of an adjacency vector, and successfully achieves higher efficiency compared to other crypto-assisted solutions. We also conduct theoretical and empirical evaluations to demonstrate that Sectric achieves the design principles.

While the flexibility of programmable switches brings opportunities, it also introduces security risks. Hence, it is vital to conduct effective troubleshooting in the programmable switch to mitigate frequent network failures. However, troubleshooting programmable switch failures is challenging due to their enhanced flexibility and functionality compared to regular switches, posing increased difficulty in debugging, particularly with limited debugging tools and information. To address this problem, we propose an efficient troubleshooting method that records real-time information about packets in the data plane, including the tables involved in packet processing. Unfortunately, due to hardware limitations, it is infeasible to record all tables’ information in the data plane. Thus, the key is to find the table set reflecting the execution path a packet goes through while minimizing the resource overhead. We first represent P4 programs as a probabilistic transition directed acyclic graph (DAG) and employ information entropy to quantify the information within a set of tracked tables. Then, we adopt a two-step approach and design algorithms to find both optimal and approximately optimal table record plans. The evaluation results show the efficacy of the proposed method, including achieving the same path recovery rate as the related works with less than one-third of the resource consumption.

Congestion control protocols play a vital role in enhancing the performance of various applications within datacenter networks. While reactive congestion control (RCC) protocols are widely deployed in commercial datacenters, the research community has actively explored token-based proactive congestion control (TCC) protocols to further push the boundaries of performance. However, despite the emergence of numerous TCC variants, there has been a lack of systematic exploration in the design space of TCC. This paper aims to bridge this gap by proposing a framework for understanding the design choices within the TCC approach. In this study, we systematically analyze different design choices of TCC approaches and leverage this understanding to develop a novel TCC protocol called ToCC. To implement ToCC, we address a set of challenges and deploy it in NP-based smart NICs. We compare ToCC with state-of-the-art TCC and RCC protocols through extensive large-scale simulations and testbed evaluations. The results demonstrate that ToCC exhibits robustness in achieving low latency across various scenarios. Additionally, ToCC effectively reduces buffer occupancy by 4.8 times compared to existing approaches, and under incast scenarios, it significantly shortens flow completion time by up to 90%. Congestion control protocols are crucial for optimizing the performance of datacenter network applications. Although reactive congestion control (RCC) protocols are commonly used in commercial datacenters, researchers have been exploring token-based proactive congestion control (TCC) protocols to further enhance network performance. Despite the development of numerous TCC variants, there has not been a thorough examination of the design space of TCC protocols until now. This paper aims to address this gap by introducing a framework for understanding the design choices within the TCC approach for TCC protocols. By analyzing various design aspects of TCC approaches, we create a novel TCC protocol called ToCC. At the central of ToCC design is that it leverages congestion control mechanisms over tokens. To implement ToCC, we tackle several challenges and integrate it into NP-based smart NICs. Comparing ToCC with state-of-the-art TCC and RCC protocols through extensive large-scale simulations and testbed evaluations, we find that ToCC consistently achieves low latency across different scenarios. Moreover, ToCC significantly reduces buffer occupancy by 4.8 times compared to existing methods, and during incast scenarios, it decreases flow completion time by up to 90%.

The state-of-the-art storage structure relies on the NVMe devices and SmartNICs to provide high IO performance and low CPU overhead. In data centers, the existing data transmission control and storage methods are not ideal, resulting in long flow completion time, especially for small IO, which directly affects the performance of disaggregated storage systems. In this paper, we present Thunder, a disaggregated storage solution designed to minimize tail latency. Firstly, Thunder achieves the minimum I/O tail latency for disaggregated storage via packet-level write-through, and has an ingenious mechanism for precise semantic conversion from message level to packet level. It refers to the process of converting message level data into packet level data and ensuring the integrity and reliability of data transmission. This process involves steps such as message segmentation, addressing, acknowledgment, and reassembly. Secondly, we present a novel optimization approach for end-to-end and information transmission processes, aiming to address a range of issues such as user usage, congestion control, and system compatibility. Finally, we conducted both testbed and large-scale simulations to verify the performance of Thunder. The results show that Thunder reduced the average latency and tail latency by 71.6% and 59.7%, respectively compared to Gimbal and Timely. Furthermore, it effectively avoids queue head blocking and congestion diffusion in PFC, increasing throughput by 2.5X and reducing tail latency by an average of 49.7%.

Enhancing the networking system with appropriate functions is a longstanding goal. Unfortunately, in today’s large-scale high-speed data centers, the feature velocity of network functions is slow because it is hard to verify the function in realistic scenarios. Recent advances in programmable switching ASICs have enabled the network data plane to move beyond its traditional role of packet forwarding. However, the current compromise between performance and flexibility results in limitations such as restricted memory/computation resources and programmable models. These limitations make it challenging for programmable switches to offer more features and to be deployed in large-scale production environments. In response, we present CLIP, a framework that works in collaboration with programmable devices and commodity servers to enhance the validation and deployment velocity of features. CLIP defines a cross-platform function definition framework and provides a set of tools to reduce the complexity of manually writing cross-platform programs. We propose an automatic traffic placement and scaling mechanism to coordinate packet processing performance across heterogeneous devices. Compared with software-based Network Functions (NFs), CLIP achieves a throughput ranging from$1.36\times $to$16.06\times $under different realistic traffic loads. Through the development and deployment of three self-defined functions within a realistic testbed, we demonstrate the feasibility and efficiency of CLIP.

As one of the pillars in cluster computing frameworks, coflow scheduling algorithms can effectively shorten the network transmission time of cluster computing jobs, thus reducing the job completion times and improving the execution performance. However, most of existing coflow scheduling algorithms failed to consider the influences of concurrent flows, which can degrade their performance under a massive number of concurrent flows. To fill the gap, we propose a unified communication agent named Courier to minimize the number of concurrent flows in cluster computing applications, which is compatible with the mainstream coflow scheduling approaches. To maintain the scheduling order given by the scheduling algorithms, Courier merges multiple flows between each pair of hosts into a unified flow, and determines its order based on that of origin flows. In addition, in order to adapt to various types of topologies, Courier introduces a control mechanism to adjust the number of flows while maintaining the scheduling order. Extensive large-scale trace-driven simulations have shown that Courier is compatible with existing scheduling algorithms, and outperforms the state-of-the-art approaches by about 30% under a variety of workloads and topologies.

Discrete-event simulation (DES) is a prevalent tool for evaluating network designs. Although DES offers full fidelity and generality, its slow performance limits its application. To speed up DES, many network simulators employ parallel discrete-event simulation (PDES). However, adapting existing network simulation models to PDES requires complex reconfigurations and often yields limited performance improvement. In this paper, we address this gap by proposing a parallel-efficient and user-transparent network simulation kernel, Unison, that adopts fine-grained partition and load-adaptive scheduling optimized for network scenarios. We prototype Unison based on ns-3. Existing network simulation models of ns-3 can be seamlessly transitioned to Unison. Testbed experiments on commodity servers demonstrate that Unison can achieve a 40× speedup over DES using 24 CPU cores, and a 10× speedup compared with existing PDES algorithms under the same CPU cores.

Due to the privacy advantages of federated learning (FL), federated recommendation systems (FedRSs) are gaining popularity for improving recommendation performance through training on local data. However, FedRSs frequently face the significant challenge of high communication costs between the server and clients. Most FedRSs utilize a client-server communication architecture, leading to heavy communication loads and single points of failure due to dependence on a central server. Clients may also encounter problems due to limited communication resources. In view of this challenge, in this paper, we propose a blockchain-assisted federated learning method at edge for communication-efficient recommendation systems, named BFedRec. Specifically, BFedRec reduces reliance on the central server by utilizing blockchain systems on edge servers to aggregate and distribute the recommendation model. To mitigate the high communication costs between clients and blockchain in each iteration, a communication-efficient training algorithm is used that trains the recommendation model directly on low-rank compressed parameters. Finally, we conduct extensive experiments on real-world datasets to verify the communication efficiency of BFedRec compared to existing methods. The experimental results show that BFedRec effectively improves communication efficiency without compromising recommendation performance.

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.

RDMA over Converged Ethernet (RoCEv2) has been widely deployed to data centers (DCs) for its better compatibility with Ethernet/IP than Infiniband (IB). As cross-DC applications emerge, they also demand high throughput, low latency, and lossless network for cross-DC data transmission. However, RoCEv2’s underlying lossless mechanism Priority-based Flow Control (PFC) cannot fit into the long-haul transmission scenario and degrades the performance of RoCEv2. PFC is myopic and only considers queue length to pause upstream senders, which leads to large queueing delay. This paper proposes Bifrost, a downstream-driven lossless flow control that supports long distance cross-DC data transmission. Bifrost uses virtual incoming packets, which indicates the upper bound of in-flight packets, together with buffered packets to control the flow rate. It minimizes the buffer space requirement to one-hop bandwidth delay product (BDP) and achieves low one-way latency. Moreover, we extend Bifrost and propose BifrostX, to accommodate the multi-priority queue of the current switch implementation. BifrostX enables flow control for each queue separately while maintaining low buffer reservation, no throughput loss, and no packet loss. Real-world experiments are conducted with prototype switches and 80 kilometers cables. Evaluations demonstrate that compared to PFC, Bifrost reduces average/tail flow completion time (FCT) of inter-DC flows by up to 22.5%/42.0%, respectively. Bifrost is compatible with existing infrastructure and can support distance of thousands of kilometers.

Reactive congestion control (RCC) protocols have undergone decades of evolution, where senders first send data packets and then back off when congestion occurs. Recently, there has been a surge of interest in proactive congestion control (PCC) that allocates bandwidth before transmission. Despite its potential, we found that there are certain scenarios where PCC may fall short. In this paper, we aim to provide a comprehensive understanding of PCC and motivate further exploration of this area. We conduct case studies and leverage NS3 simulations to compare state-of-the-art PCC with RCCs, delving into the real dilemma of PCC.

With the continuously increasing scale of deep neural network models, there is a clear trend towards distributed DNN model training. State-of-the-art training frameworks support this approach using collective communication libraries such as NCCL, MPI, Gloo, and Horovod. These libraries have many parameters that can be adjusted to fit different hardware environments, and these parameters can greatly impact training performance. Therefore, careful tuning of parameters for each training environment is required. However, given the large parameter space, manual exploration can be time-consuming and laborious.

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%).

Remote Direct Memory Access has been widely adopted in distributed storage systems. However, it only supports unicast operations, which degrades the performance significantly for data replication because of bandwidth waste and CPU overhead. To address the problem, we propose MC-RDMA, a distributed and reliable multicast RDMA. It is compatible with existing unicast RDMA but supports lazy packet replication with reliable RDMA multicasting. The key idea of MC-RDMA is utilizing in-network programmable switches to build a NIC-transparent reliable multicast protocol for RDMA. MC-RDMA combines the address information of the IP and RoCEv2 into a sender-initialized multicast routing protocol. Besides, it synchronizes the hardware transmission states of multiple receivers by merging ACKs and NAKs. To verify the effectiveness of MC-RDMA, we implement it with Mellanox ConnectX-6 commodity RNICs and Intel Tofino P4 programmable switches. Experimental results show that MC-RDMA can double the sender bandwidth utilization and reduce the CPU overhead significantly compared to unicast-based RDMA replications. Moreover, it reduces the storage request latency by -30% with realistic workloads and decreases the training time by -50% in the distributed training system.

RDMA over Converged Ethernet (RoCEv2) has been widely deployed to data centers (DCs) for its better compatibility with Ethernet/IP than Infiniband (IB). As cross-DC applications emerge, they also demand high throughput, low latency, and lossless network for cross-DC data transmission. However, RoCEv2's underlying lossless mechanism Priority-based Flow Control (PFC) cannot fit into the long-haul transmission scenario and degrades the performance of RoCEv2. PFC is myopic and only considers queue length to pause upstream senders, which leads to large queueing delay. This paper proposes Bifrost, a downstream-driven lossless flow control that supports long distance cross-DC data transmission. Bifrost uses virtual incoming packets, which indicates the upper bound of in-flight packets, together with buffered packets to control the flow rate. It minimizes the buffer space requirement to one-hop bandwidth delay product (BDP) and achieves low one-way latency. Real-world experiments are conducted with prototype switches and 80 kilometers cables. Evaluations demonstrate that compared to PFC, Bifrost reduces average/tail flow completion time (FCT) of inter-DC flows by up to 22.5%/42.0%, respectively. Bifrost is compatible with existing infrastructure and can support distance of thousands of kilometers.

Cloud network serves a large number of tenants and a variety of applications. The continuously changing demands require a programmable data plane to achieve fast feature velocity. However, the years-long release cycle of traditional function-fixed switches can not meet this requirement. Emerging programmable switches provide the flexibility of packet processing without sacrificing hardware performance. Due to the trade-off between performance and flexibility, the current programmable switches make compromises in some aspects such as limited memory/computation resources, and lack of the capacity to realize complicated computation. The programmable switches can not satisfy the demand for network services and applications in production networks. We propose a framework that leverages host servers to extend the capability of network switches quickly, accelerates new feature deployment, and verifies new ideas in production networks. Specifically, to build the unified programmable data plane, we propose essential design and implementation challenges including a programming abstraction that allows automatically and effectively deploying network functions on switch and server clusters, allocating traffic to fully utilize the server resources, and supporting flexible scaling of the system. The quick deployment of self-defined functions in a realistic system has verified the feasibility and practicality of the proposed framework.

Learning-based Internet congestion control algorithms have attracted much attention due to their potential performance improvement over traditional algorithms. However, such performance improvement is usually at the expense of black-box design and high computational overhead, which prevent them from large-scale deployment over production networks. To address this problem, we propose a novel Internet congestion control algorithm called Gemini. It contains a parameterized congestion control module, which is white-box designed with low computational overhead, and an online parameter optimization module, which serves to adapt the parameterized congestion control module to different networks for higher transmission performance. Extensive trace-driven emulations reveal Gemini achieves better balances between delay and throughput than state-of-the-art algorithms. Moreover, we successfully deploy Gemini over production networks. The evaluation results show that the average throughput of Gemini is 5% higher than that of Cubic (4% higher than that of BBR) over a mobile application downloading service and 61% higher than that of Cubic (33% higher than that of BBR) over a commercial network speed-test benchmarking service.

Remote Procedure Call (RPC) is widely used in distributed systems and it usually needs to serialize data before transmission. Serialization accounts for a large proportion of the overhead in RPC and becomes a bottleneck for RPC communications. Because the size of the output serialized message cannot be predicted in advance, there could be multiple memory reallocations and copies in typical serialization libraries (e.g., FlatBuffers), which dominates the overhead. We propose the novel serialization library, zFlatBuffers, to eliminate these avoidable copies during the serialization process and realize zero copy during communication. Unlike the typical serialization library, FlatBuffers, the message generated by zFlatBuffers consists of multiple non-contiguous buffers due to its zero-copy nature. Moreover, we integrate zFlatBuffers with RDMA-based RPC systems. For RDMA Unreliable Datagram, we modify the message buffer of eRPC to enable it to transmit messages composed of multiple buffers. We also build the zRPC system based on RDMA Reliable Connection, which transmits the zFlatBuffers message by the scatter/gather function. Compared to the original FlatBuffers, zFlatBuffers improves the throughput of eRPC and zRPC by 11.2%-33.7% and 5.8%-53.6%, respectively.

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.

Butterfly (a cyclic graph motif) counting is a fundamental task with many applications in graph analysis, which aims at computing the number of butterflies in a large graph. With the rapid growth of graph data, it is more and more challenging to do butterfly counting due to the super-linear time complexity and large memory consumption. In this paper, we study I/O-efficient algorithms for doing butterfly counting on hierarchical memory. Existing algorithms of the kind cannot guarantee I/O optimality. Observing that in order to count butterflies, it suffices to "witness" a subgraph instead of the whole structure, a new class of algorithms called semi-witnessing algorithm is proposed. We prove that a semi-witnessing algorithm is not restricted by the lower bound Ømega(|E|2/MB) of a witnessing algorithm, and give a new bound of Ømega(min(|E|2/MB, |E|/|V| √M B)). We further develop the IOBufs algorithm that manages to approach the I/O lower bound, and thus claim its optimality. Finally, we make efforts to parallelize IOBufs to further improve the performance and scalability. We show in the experiment that IOBufs significantly outperforms the state-of-the-art algorithms EMRC and BFC-EM. In addition, IOBufs can scale to conducting butterfly counting on the Clueweb graph with 37 billion edges and quintillions (10^18 ) of butterflies.

Remote Direct Memory Access (RDMA) has been widely deployed in datacenters for its high performance. Large-scale high performance cloud services built on geographically distributed datacenters require long-range RDMA for performance requirements. However, existing RDMA solutions can hardly satisfy the stringent requirements of the emerging large-scale high-performance cloud services built on geo-distributed datacenters in terms of throughput and delay. On the one hand, lossless RDMA suffers from a deep buffer and potential suboptimal throughput for inter-datacenter traffic due to delayed response to Priority Flow Control (PFC) messages. On the other hand, lossy RDMA with selective retransmissions suffers from poor performance when multiple flows with different round-trip times (RTTs) coexist in cross-datacenter scenarios. This article proposesSwing, which expands the high-performance lossless RDMA to long-distance links through PFC-Relay.Swingensures the throughput of long-distance links while minimizing the buffer requirement for long-range RDMA. It enables long-range RDMA without making any modifications to existing in-datacenter networks. The evaluation shows thatSwingcan reduce the average flow completion time (FCT) by 14%-66% in a variety of traffic scenarios.

Cloud-based AI infrastructure is increasingly important, especially on large-scale distributed training. To improve its efficiency and serviceability, real-time monitoring of the infrastructure and profiling the workload are proved to be the effective approach empirically. However, cloud environment poses great challenges as service providers cannot interfere with their tenants' workloads or touch user data, thus previous instrumentation-based monitoring approach cannot be applied, nor does the workload trace collection.We propose Moneo, a non-intrusive cloud-friendly monitoring system for AI infrastructure. Moneo is capable of intelligently collecting the key architecture-level metrics at finer granularity in real-time without instrumenting or tracing the workloads, which has been deployed in real production cloud, Azure. We analyze the results reported by Moneo for typical large-scale distributed AI workloads from real deployment. Results demonstrate that Moneo can effectively help service providers understand the real resource usage patterns of various AI workloads and real networking requirements, so as to get valuable findings help improve the efficiency of cloud infrastructure and optimize the software stack with the consideration of the characteristic resource usage requirements for different AI workloads.

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

Network measurement is important to data center operators. Most existing efforts focus on developing new implementation schemes for measurement tasks. Little attention is paid to on-the-fly task reconfiguration. Due to resource constraints, it is impossible to configure all needed tasks at start-up and dynamically turn on/of them. To support real-time reconfiguration of many different tasks, a key observation is that it is unnecessary to bind a task and its implementation at the compilation phase. We design FlyMon, the first sketch-based measurement system that can make on-the-fly reconfigurations on a large set of measurement tasks. FlyMon introduces the concept of Composable Measurement Units (CMUs), which are general operation units that support reconfigurable implementation for measurement tasks combined from different flow keys and flow attributes. FlyMon maps the design of CMUs to programmable switches' data planes so that the number of compacted CMUs can be maximized. FlyMon also provides dynamic memory management. We prototype FlyMon on Tofino and currently enable four frequently used flow attributes. Each CMU Group (with 3 CMUs) can concurrently perform up to 96 isolated measurement tasks with less than 8.3% hardware resources. The tasks can be deployed with configurable memory size at the millisecond level. By cross-stacking, FlyMon can deploy up to 27 CMUs in one pipeline of Tofino.

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.

One critical issue for wireless power transfer is to avoid human health impairments caused by electromagnetic radiation (EMR) exposure. The existing studies mainly focus on scheduling wireless chargers so that (expected) EMR at any point in the area does not exceed a threshold$R_t$. Nevertheless, they overlook the EMR jitter that leads to exceeding of$R_t$even if the expected EMR is no more than$R_t$. This paper studies the fundamental problem ofRObustlySafEcharging for wireless power transfer (ROSE), that is, scheduling the power of chargers so that the charging utility for all rechargeable devices is maximized while the probability that EMR anywhere does not exceed$R_t$is no less than a given confidence. We first build our empirical probabilistic charging model and EMR model. Then, we present EMR approximation and area discretization techniques to formulate ROSE into a Second-Order Cone Program. After that, we propose the first redundant second-order cone constraints reduction algorithm to reduce the computational cost, and therefore obtain a$(1-\epsilon)$-approximation centralized algorithm. Further, we propose a$(1-\epsilon)$-approximation fully distributed algorithm scalable with network size for ROSE. We conduct both simulation and field experiments, and the results show that our algorithms can outperform comparison algorithms by 480.19 percent.

Datacenter networks enable multiple paths between hosts to provide large bisection bandwidth. It requires load balancers to cope with network uncertainties such as traffic dynamics and topology asymmetry. Existing edge-based load balancing schemes are usually faced with the problem of limited network visibility. This article proposesMeet, a rack-level pooling based load-balancer deployed at the edge that can handle the aformentioned uncertainties.Meetutilizes both passive information as well as active probing to comprehensively sense the network conditions with relatively low cost.Meetdynamically reroutes flows effectively based on the visibility of the network condition.Meethas been tested with extensive flow-level simulations against state-of-the-art load balancers. It outperforms Hermes by up to 10% in the experiments, and outperforms others solutions such as DRILL by up to 50%.Meetrequires no modifications to the switches and is feasible to deploy at the edge.

The average/tail Flow Completion Times (FCTs) are critical to many datacenter applications. Congestion control plays a central role in optimizing FCT. Inappropriate congestion control can exacerbate buffer occupancy, thus hurting the flow performance. Our observations are that current approaches are too aggressive in injecting packets into underlying networks. Instead of handling buffer explosion afterward, we reduce buffer occupancy in the first place. We propose PayDebt, a novel and readily-deployable proactive congestion control protocol. At its heart, adebtmechanism provides bandwidth coordination between the already-buffered and the forthcoming packets. We evaluate PayDebt both in a testbed and large-scale simulations. The buffer occupancy can be decreased by up to 8.0×-35.9× compared to DCQCN and Homa.

To minimize a job's completion time, we need to minimize the completion time of its final stage's last task. Scheduling of machine slots and networks largely dominates the variable part of each task's duration. Finding an optimal schedule is NP-hard even for offline and simplified scenarios. Previous work does lead to improved performance with various strategies. State-of-the-art task placement and network scheduling efforts are largely disjunctive. Without joint optimization, they are sub-optimal and myopic in many scenarios. Task placement usually treats the network as a black box. Thus, we use prioritized bandwidth allocation among tasks making the network bothpredictableandefficientto achieve joint scheduling. With this feature, joint scheduling can be transformed into a specialbin-packing problem. Over this minimal yet power-enough abstraction, we propose PushBox to schedule data-parallel jobs in multi-tenant clusters. When designing the joint scheduling algorithm, we not only embrace the wisdom of prior art but also respect administrators’ fairness intent, which is so far largely ignored. We implement PushBox on Hadoop 3. PushBox performs persistently well on both a small testbed and a trace-driven simulator.

Once started, existing hash tables cannot change their pre-defined hash functions, even if the incoming data cannot be evenly distributed to the hash table buckets. In this paper, we presentDHash, a type of hash table for shared memory systems, that can change its hash function and rebuild the hash table on the fly, without noticeably degrading its service. The major technical novelty ofDHashstems from an efficient distributing mechanism that can atomically distribute every node when rebuilding, without locking the corresponding hash table buckets. This not only enables non-blocking lookup, insert, and delete operations, but more importantly, makesDHashindependent of the implementation of hash table buckets, such thatDHashallows programmers to select the set algorithms that meet their requirements best from a variety of existing lock-free and wait-free set algorithms. Evaluations show thatDHashcan efficiently change its hash function on the fly. Moreover, when rebuilding,DHashconsistently outperforms the state-of-the-art hash tables in terms of throughput and response time of concurrent operations, at different concurrency levels, and with different operation mixes and average load factors.

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.

Incast occurs frequently in datacenter networks where a large number of senders send data to a single receiver simultaneously, which makes the last hop the network bottleneck. Incast can hurt flows' performance. However, congestion control protocols are not effective at handling incast. One key insight is that it is too late to handle incast packets after they have already piled up at the last hop. Instead, we should avoid incast as early as possible. Inspired by flood control in Hydrologic Engineering, we propose Floodgate, a novel switch-based per-hop flow control to handle incast. Floodgate is compatible with existing congestion control protocols. We integrate it with practical congestion control approaches such as DCQCN, TIMELY, and HPCC. We evaluate Floodgate both in our implementations and large-scale simulations. Compared with state of the art, Floodgate reduces the buffer occupancy by a factor of 6.6x, as well as the queuing delay. Therefore, the average FCT and tail latency are greatly reduced.

Campus networks are widely deployed for organizations like universities and large companies. Applications and network-based services require campus networks to guarantee short queue and provide low latency and large bandwidth. However, the widely adopted packet-loss-based congestion control mechanism in client hosts builds up long queues in the switch buffer, which is prone to packet loss in burst scenarios, resulting in great network delay. Therefore, a scheme for efficiently controlling queue length of shallow buffer switches in campus networks is urgently needed. Explicit Congestion Notification(ECN) as an explicit feedback mechanism is widely adopted in data center networks to build lossless networks. In this paper, we propose Clean, an efficient queue length control scheme based on transparent ECN-proxy for campus networks. Clean is able to exert fine-grained control over arbitrary client TCP stacks by enforcing per-flow congestion control in the access point(AP). It allows the campus network switches to maintain a low queue length, resulting in high throughput, low latency and zero packet loss. Evaluation results demonstrate that Clean reduces the maximum queue length of the switch by 86% and reduces the 99th percentile latency by 85%. Clean also achieves zero packet loss in burst scenarios.

This paper presents Aquila, the first practically usable verification system for Alibaba's production-scale programmable data planes. Aquila addresses four challenges in building a practically usable verification: (1) specification complexity; (2) verification scalability; (3) bug localization; and (4) verifier self validation. Specifically, first, Aquila proposes a high-level language that facilitates easy expression of specifications, reducing lines of specification codes by tenfold compared to the state-of-the-art. Second, Aquila constructs a sequential encoding algorithm to circumvent the exponential growth of states associated with the upscaling of data plane programs to production level. Third, Aquila adopts an automatic and accurate bug localization approach that can narrow down suspects based on reported violations and pinpoint the culprit by simulating a fix for each suspect. Fourth and finally, Aquila can perform self validation based on refinement proof, which involves the construction of an alternative representation and subsequent equivalence checking. To this date, Aquila has been used in the verification of our production-scale programmable edge networks for over half a year, and it has successfully prevented many potential failures resulting from data plane bugs.

Today's cloud is shared among multiple tenants running different applications, and a desirable multi-tenant datacenter network infrastructure should provide bandwidth guarantees for throughput-intensive applications, low latency for latency-sensitive short messages, as well as work conservation to fully utilize the network bandwidth. Despite significant efforts in recent years, none of them can achieve these three properties simultaneously. In this paper, we identify the key deficiency of prior solutions and use this insight to motivate our design of Trinity-a simple, practical yet effective solution that achieves bandwidth guarantees, work conservation and low latency simultaneously in the cloud. We implement Trinity using existing commodity hardwares and demonstrate its superior performance over prior solutions using testbed experiments.

With the development of applications on end devices, such as cell phones and tablets, more and more passengers would like to have entertainment on these end devices when they are cruising on vehicles. Due to the limited computation ability of the end devices, some of these applications have back-end components on the edge clouds, which are realized by Service Entities (SEs). In this work, we propose a system named DSEP to Dynamically determine the SEPlacement, such that the maximum latency experienced by the passengers can be minimized. To this end, we first train two sequential neural networks to predict the position of each individual vehicle, and propose an efficient algorithm based on optimization relaxation and Lagrange decomposition to determine the SE placement. Through extensive real-data driven simulations, we find that with the two sequential neural networks proposed in this paper, there are less than 1 percent errors on estimating where the passengers will access the edge cloud system. When the computation resources in the edge cloud are limited, DSEP can reduce the response latency by up to 43 percent compared with the nearest placement scheme. Even averaging the performance improvement over all simulation settings, DSEP can reduce the response latency by 16 percent.

Reducing Coflow Completion Time (CCT) has a significant impact on application performance in data-parallel frameworks. Most existing works assume that the endpoints of constituent flows in each coflow are predetermined. We argue that CCT can be further optimized by treating flows' destinations as an additional optimization dimension via reducer placement. In this article, we propose and implement RPC, a joint online Reducer Placement and Coflow bandwidth scheduling framework, to minimize the average CCT in cloud clusters. We first develop a 2-approximation algorithm to minimize the CCT of a single coflow, and then schedule all the coflows following the Shortest Remaining Time First (SRTF) principle. We use real testbed experiments and extensive large-scale simulations to demonstrate that RPC can reduce the average CCT by 64.98% compared with the state-of-the-art technologies.

Triangle counting is a building block for a wide range of graph applications. Traditional wisdom suggests that i) hashing is not suitable for triangle counting, ii) edge-centric triangle counting beats vertex-centric design, and iii) communication-free and workload balanced graph partitioning is a grand challenge for triangle counting. On the contrary, we advocate that i) hashing can help the key operations for scalable triangle counting on Graphics Processing Units (GPUs), i.e., list intersection and graph partitioning, ii) vertex-centric design reduces both hash table construction cost and memory consumption, which is limited on GPUs. In addition, iii) we exploit graph and workload collaborative, and hashing-based 2D partitioning to scale vertex-centric triangle counting over 1000 GPUs with sustained scalability. In this article, we present Trust which performs triangle counting with the hash operation and vertex-centric mechanism at the core. To the best of our knowledge, Trust is the first work that achieves over one trillion Traversed Edges Per Second (TEPS) rate for triangle counting.

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.

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.

In this paper, we consider the scenario in which a mobile charger (MC) periodically travels within a sensor network to recharge the sensors wirelessly. We design joint charging and scheduling schemes to maximize the Quality of Monitoring (QoM) for stochastic events, which arrive and depart according to known probability distributions of time. Information is considered captured if it is sensed by at least one sensor. We focus on two closely related research issues, i.e., how to choose the sensors for charging and decide the charging time for each of them, and how to schedule the sensors' activation schedules according to their received energy. We formulate our problem as the maximum QoM CHArging and SchEduling problem (CHASE). We first ignore the MC's travel time and study the resulting relaxed version of the problem, which we call CHASE-R. We show that both CHASE and CHASE-R are NP-hard. For CHASE-R, we prove that it can be formulated as a submodular function maximization problem, which allows two algorithms to achieve 1/6- and 1/(4 + ε)-approximation ratios. Then, for CHASE, we propose approximation algorithms to solve it by extending the CHASE-R results. We conduct simulations to validate our algorithm design.

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.

With the development of data center networks, traditional TCP/IP cannot support the demand in data centers. Remote Direct Memory Access (RDMA) technology could improve the performance of DCN significantly because of high throughput and low latency. However, load balancing is a key issue in RDMA which has not been solved distribute. This paper will propose an algorithm to solve the load balance problem in RDMA on application layer without hardware changing. The main idea is to divide data to chunks and data chunks on multiple reachable paths for transmission. However, it is no trivial to find the optimal chunk size and the path number, some empirical values are found by varieties of experiments and tests. Moreover, the chunk allocation scheme also needs to consider the traffic condition in DCNs to find more free paths to transmit. We evaluate the algorithm in application layer with ns3 simulator. The experiment results show that with our algorithm the completion time can decrease 81.03% at most.

Modern data center applications need high throughput (40Gbps) and ultra-low latency (<;10us per hop), along with low CPU overhead. Remote Direct Memory Access (RDMA), which can be deployed in RDMA over commodity Ethernet (RoCEv2) protocol, has the potential to satisfy the requirements. RoCEv2 needs a lossless environment to achieve high performance. RoCEv2 provides Priority-based Flow Control (PFC) to prevent packet loss caused by buffer overflow. But packet loss can still happen in today’s data centers due to other reasons such as switch configuration error. There are two retransmission algorithms dealing with the packet loss recovery: Go-Back-0 and Go-Back-N. Unfortunately, by simply applying Go-Back-N algorithm to RoCEv2, the relative throughput will drop to nearly zero when the packet loss rate exceeds 1%. This is mainly caused by the improper triggering mechanism of generating NAK. This paper proposed an Improved Go-Back-N algorithm to solve this problem, which involves two mechanism. The Improved Go-Back-N is easy to be deployed in today’s data centers because it makes no changes on switches. It can improve the relative throughput to about 60% when the packet loss rate increases to 1%.

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.

In-network Access Control List (ACL) is an important technique in ensuring network-wide connectivity and security. As cloud-scale WANs today constantly evolve in size and complexity, in-network ACL rules are becoming increasingly more complex. This presents a great challenge to the updating process of ACL configurations: network operators are frequently required to update "tangled" ACL rules across thousands of devices to meet diverse business requirements, and even a single ACL misconfiguration may lead to network disruptions. Such increasing challenges call for an automated system to improve the efficiency and correctness of ACL updates. This paper presents Jinjing, a system that aids Alibaba's network operators in automatically and correctly updating ACL configurations in Alibaba's global WAN. Jinjing allows the operators to express in a declarative language, named LAI, their update intent (e.g., ACL migration and traffic control). Then, Jinjing automatically synthesizes ACL update plans that satisfy their intent. At the heart of Jinjing, we develop a set of novel verification and synthesis techniques to rigorously guarantee the correctness of update plans. In Alibaba, our operators have used Jinjing to efficiently update their ACLs and have thus prevented significant service downtime.

Modern data centers are the host for multitude of large-scale distributed applications. These applications generate tremendous amount of network flows to complete their tasks. At this scale, efficient network control manages the network traffic at the level of flow aggregates (or slices ) who need to share the network with respect to operator’s proportionality policy. Existing slice scheduling mechanisms can not meet this goal in multi-path data center networks. Hence, in this paper, we aim to fulfil this goal and satisfy the congestion proportionality policy for network sharing. The policy is applied to the traffic traversing congested links in the network. We propose Uranus, a novel slice scheduler based on a combination of flow-level control mechanisms. The scheduler implements two-tier weight allocation to individual flows. Then, relying on a non-blocking big switch abstraction, slice weights are allocated at the inter-rack level by aggregating the weights of rack-to-rack flows. Finally, Uranus can dynamically divide the rack-level weight to its constituent flows. We also implement Weighted Virtual Congestion Control (WVCC), an end-host shim-layer that enforces weighted bandwidth sharing among competing flows. Trace-driven NS3 simulations demonstrate that Uranus closely approximates the congestion-proportionality and is able to improve the proportional fairness by 31.49% compared to the state-of-the-art mechanisms. The results also prove Uranus’s capability of intra-slice scheduling optimization. Moreover, Uranus’s throughput in Clos fabrics outperforms the state-of-the-art mechanisms by 10%.

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.

Machine slot-time spent on data transmission has direct impact on average job completion time (JCT). In this paper, we propose Macroflow, a networking abstraction that can capture the primitive scheduling granularity of machine slot-time. We demonstrate that minimizing machine slot-time is equivalent to minimizing the average macroflow completion time (MCT). We prove that minimizing MCT to be strongly NP-hard and focus on developing effective heuristics. We propose the Smallest-Macroflow-First (SMF) and Smallest-Average-Macroflow-First (SAMF) heuristics that greedily schedule macroflows based on their network footprint. To work with existing commodity switches, priority discretization is performed to classify macroflows into a small number of priority queues.

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.

Reducing Coflow Completion Time (CCT) has a significant impact on application performance in data-parallel frameworks. Most existing works assume that the endpoints of constituent flows in each coflow are predetermined. We argue that CCT can be further optimized by treating flows' destinations as an additional optimization dimension via reducer placement. In this paper, we propose and implement RPC, a joint online Reducer Placement and Coflow bandwidth scheduling framework, to minimize the average CCT in cloud clusters. We first develop a 2-approximation algorithm to minimize the CCT of a single coflow, then schedule all the coflows following the Shortest Remaining Time First (SRTF) principle. We use a real testbed implementation and extensive large-scale simulations to demonstrate that RPC can reduce the average CCT by 64.98% compared with state-of-the-art technologies.

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.

One critical issue for wireless power transfer is to avoid human health impairments caused by electromagnetic radiation (EMR) exposure. The existing studies mainly focus on scheduling wireless chargers so that (expected) EMR at any point in the area doesn't exceed a threshold Rt. Nevertheless, they overlook the EMR jitter that leads to exceeding of Rteven if the expected EMR is no more than Rt. This paper studies the fundamental problem of RObustly SafE charging for wireless power transfer (ROSE), that is, scheduling the power of chargers so that the charging utility for all rechargeable devices is maximized while the probability that EMR anywhere doesn't exceed Rt is no less than a given confidence. We first build our empirical probabilistic charging model and EMR model. Then, we present EMR approximation and area discretization techniques to formulate ROSE into a Second-Order Cone Program, and the first redundant second-order cone constraints reduction algorithm to reduce the computational cost, and therefore obtain a (1-ε)-approximation centralized algorithm. Further, we propose a (1-ε)-approximation fully distributed algorithm scalable with network size for ROSE. Simulations and field experiments show that our algorithms can outperform comparison algorithms by 480.19%.

Datacenter networks are critical to Cloud computing. The coflow abstraction is a major leap forward of application-aware network scheduling. In the context of multistage jobs, there are dependencies among coflows. As a result, there is a large divergence between coflow-completion-time (CCT) and job-completion-time (JCT). To our best knowledge, this is the first work that systematically studies: how to schedule dependent coflows of multi-stage jobs, so that the total weighted job completion time can be minimized. We present a formal mathematical formulation. We also prove that this problem is strongly NP-hard. Inspired by the optimal solution of the relaxed linear programming, we design an algorithm that runs in polynomial time to solve this problem with an approximation ratio of (2M + 1), where M is the number of machines. Evaluation results demonstrate that, the largest gap between our algorithm and the lower bound is only 9.14%. We reduce the average JCT by up to 33.48 % compared with Aalo, a heuristic multi-stage coflow scheduler. We reduce the total weighted JCT by up to 83.31 % compared with LP-OV-LS, the state-of-the-art approximation algorithm of coflow scheduling.

Using FPGA as accelerators is gaining popularity in Cloud computing. Usually, FPGA accelerators in a datacenter are managed as a single resource pool. By issuing a request to this pool, a tenant can transparently access FPGA resources. FPGA requests usually arrive in batches. The objective of scheduling is to minimize the make-span of a given batch of requests, which is the completion time of the entire batch of jobs. As a result, either the responsiveness is improved, or the system throughput is maximized. The key technical challenge is the existence of multiple resource bottlenecks. An FPGA job can be bottlenecked by either computation (i.e., computation-intensive) or network (i.e., network-intensive), and sometimes by both. To the best of our knowledge, this is the first work that minimizes the make-span of batched requests for an FPGA accelerator pool in Cloud computing that considers multiple resource bottlenecks. In this paper, we design several scheduling algorithms to address the challenge. We implement our scheduling algorithms in an IBM Cloud system. We conduct extensive evaluations on both a small scale testbed and a large-scale simulator. Compared with the Shortest-Job-First scheduling, our algorithms can reduce the make-span by 36.25 percent, and improve the system throughput by 36.05 percent.

In datacenter networks, flows can have different performance objectives. We use a tenant-objective division to denote all flows of a tenant that share the same objective. Bandwidth allocation in datacenters should support not only performance isolation among divisions but also objective-oriented scheduling among flows within the same division. This paper studies the Multi-Tenant Multi-Objective (MT-MO) bandwidth allocation problem. To our best knowledge, no existing practical work support performance isolation and objective scheduling simultaneously. We propose Stacked Congestion Control (SCC), a distributed host-based bandwidth allocation design, where an underlay congestion control (UCC) layer handles contention among divisions, and a private congestion control (PCC) layer for each division optimizes its performance objective. Via the tenant-objective tunnel abstraction, SCC achieves weighted bandwidth sharing for each division in a distributed and transparent way. By adding a rate-limiting send queue in the ingress of each tunnel, mechanisms between performance isolation and objective scheduling are completely decoupled. We evaluate SCC both on a small-scale testbed and with large-scale NS-2 simulations. Compared to the direct coexistence cases, SCC reduces latency by up to 40% for Latency-Sensitive flows, deadline miss ratio by up to 3.2× for Deadline-Sensitive flows, and average flow-completion-time by up to 53% for Completion-Sensitive flows.

Bus service is the most important function of public transportation. Besides the major goal of carrying passengers around, providing a comfortable travel experience for passengers is also a key business consideration. To provide a comfortable travel experience, effective bus scheduling is essential. Traditional approaches are based on fixed timetables. The wide adoptions of smart card fare collection systems and GPS tracing systems in public transportation provide new opportunities for using the data-driven approaches to fit the demand of passengers. In this paper, we associate these two independent data sets to derive the passengers' origin and destination. As the data are real time, we build a system to forecast the passenger flow in real time. To the best of our knowledge, this is the first paper, which implements a system utilizing smart card data and GPS data to forecast the passenger flow in real time.

Metro systems play an important role in meeting the demand for urban transportation in large cities. The understanding of passenger route choice is critical for public transit management. The wide deployment of automated fare collection (AFC) systems opens up a new opportunity. However, only each trip's tap-in and tap-out time stamp and stations can be directly obtained from AFC system records; the train and route chosen by a passenger are unknown, information necessary to solve our problem. While existing methods work well in some specific situations, they hardly work for complicated situations. In this paper, we propose a solution that needs no additional equipment or human involvement than the AFC systems. We develop a probabilistic model that can estimate from empirical analysis how the passenger flows are dispatched to different routes and trains. We validate our approach using a large-scale data set collected from the Shenzhen Metro system. The measured results provide us with useful input when building the passenger path choice model.

Today's content delivery is characterized by key trends such as converged media delivery over HTTP, increasing volumes of multimedia content delivered over IP, and elevated user expectations on quality-of-experience. In this respect, server provisioning is a critical phase of CDN management, which affects both incumbent and entrant CDN operators as well as internet service providers. However, existing tools and approaches to solve server placement problems have serious shortcomings: they offer only coarse tuning knobs and limit servers to a set of candidate sites givena priori. Our conversations with CDN operators reveal that a new provisioning mechanism is necessary to take advantage of emerging opportunities such as faster speed to roll out new locations and more access networks. In this paper, we present the design of DISC, a decision support system to help CDN operators systematically investigate different design tradeoffs and evaluate what-if scenarios. The key enabler underlying DISC is a network coordinate-based data analysis workflow that can flexibly embed different cost, performance, and workload characteristics without sacrificing the fidelity. We describe practical use cases and experiences in applying DISC to a large country-wide deployment. The results show that DISC significantly reduces average latency, deployment cost, and interdomain traffic.

Many existing data center network (DCN) flow scheduling schemes, that minimize flow completion times (FCT) assume prior knowledge of flows and custom switch functions, making them superior in performance but hard to implement in practice. By contrast, we seek to minimize FCT with no prior knowledge and existing commodity switch hardware. To this end, we present PIAS, a DCN flow scheduling mechanism that aims to minimize FCT by mimicking shortest job first (SJF) on the premise that flow size is not knowna priori. At its heart, PIAS leverages multiple priority queues available in existing commodity switches to implement a multiple level feedback queue, in which a PIAS flow is gradually demoted from higher-priority queues to lower-priority queues based on the number of bytes it has sent. As a result, short flows are likely to be finished in the first few high-priority queues and thus be prioritized over long flows in general, which enables PIAS to emulate SJF without knowing flow sizes beforehand. We have implemented a PIAS prototype and evaluated PIAS through both testbed experiments and ns-2 simulations. We show that PIAS is readily deployable with commodity switches and backward compatible with legacy TCP/IP stacks. Our evaluation results show that PIAS significantly outperforms existing information-agnostic schemes, for example, it reduces FCT by up to 50% compared to DCTCP[11]and L2DCT[32]; and it only has a 1.1% performance gap to an ideal information-aware scheme, pFabric[13], for short flows under a production DCN workload.

Inter-data center wide area networks (inter-DC WANs) carry a significant amount of data transfers that require to be completed within certain time periods, or deadlines. However, very little work has been done to guarantee such deadlines. The crux is that the current inter-DC WAN lacks an interface for users to specify their transfer deadlines and a mechanism for provider to ensure the completion while maintaining high WAN utilization. In this paper, we address the problem by introducing a deadline-based network abstraction (DNA) for inter-DC WANs. DNA allows users to explicitly specify the amount of data to be delivered and the deadline by which it has to be completed. The malleability of DNA provides flexibility in resource allocation. Based on this, we develop a system calledAmoebathat implements DNA. Our simulations and test bed experiments show thatAmoeba, by harnessing DNA’s malleability, accommodates 15% more user requests with deadlines, while achieving 60% higher WAN utilization than prior solutions.

Matrix multiplication is a dominant but very time-consuming operation in many big data analytic applications. Thus its performance optimization is an important and fundamental research issue. The performance of large-scale matrix multiplication on distributed data-parallel platforms is determined by both computation and IO costs. For existing matrix multiplication execution strategies, when the execution concurrency scales up above a threshold, their execution performance deteriorates quickly because the increase of the IO cost outweighs the decrease of the computation cost. This paper presents a novel parallel execution strategy CRMM (Concurrent Replication-based Matrix Multiplication) along with a parallel algorithm, Marlin, for large-scale matrix multiplication on data-parallel platforms. The CRMM strategy exploits higher execution concurrency for sub-block matrix multiplication with the same IO cost. To further improve the performance of Marlin, we also propose a number of novel system-level optimizations, including increasing the concurrency of local data exchange by calling native library in batch, reducing the overhead of block matrix transformation, and reducing disk heavy shuffle operations by exploiting the semantics of matrix computation. We have implemented Marlin as a library along with a set of related matrix operations on Spark and also contributed Marlin to the open-source community. For large-sized matrix multiplication, Marlin outperforms existing systems including Spark MLlib, SystemML and SciDB, with about 1.29×, 3.53× and 2.21× speedup on average, respectively. The evaluation upon a real-world DNN workload also indicates that Marlin outperforms above systems by about 12.8×, 5.1× and 27.2× speedup, respectively.

We present$\sf {Tentacle}$, a decision support framework to provision edge servers for online services providers (OSPs).$\sf {Tentacle}$takes advantage of the increasingly flexible edge server placement, which is enabled by new technologies such as edge computing platforms, cloudlets and network function virtualization, to optimize the overall performance and cost of edge infrastructures. The key difference between$\sf {Tentacle}$and traditional server placement approaches lies on that$\sf {Tentacle}$can discover proper unforeseen edge locations which significantly improve the efficiency and reduce the cost of edge provisioning. We show how$\sf {Tentacle}$effectively identifies promising edge locations which are close to a collection of users merely with inaccurate network distance estimation methods, e.g., geographic coordinate (GC) and network coordinate systems (NC). We also show how$\sf {Tentacle}$comprehensively considers various pragmatic concerns in edge provisioning, such as traffic limits by law or ISP policy, edge site deployment and resource usage cost, over-provisioning for fault tolerance, etc., with a simple optimization model. We simulate$\sf {Tentacle}$using real network data at global and county-wide scales. Measurement-driven simulations show that with a given cost budget$\sf {Tentacle}$can improve user performance by around 10-45 percent at global scale networks and 15-35 percent at a country-wide scale network.

We propose OpenFunction, an extensible data plane abstraction protocol for platform-independent software-defined middleboxes. The main challenge is how to abstract packet operations, flow states and event generations with elements. The key decision of OpenFunction is: actions/states/events operations should be defined in a uniform pattern and independent from each other. We implemented a working SDM system including one OpenFunction controller and OpenFunction boxes based on Netmap, DPDK and FPGA to verify OpenFunction abstraction.

For a datacenter running a data-parallel analytic framework, minimizing job completion time (JCT) is crucial for application performance. The key observation is that JCT could be improved, if network scheduling can exploit the opportunity of decreasing the amount of occupied machine slot-time spend on communication. We propose Macroflow, a networking abstraction that captures the primitive resource granularity of data-parallel frameworks. We study the inter-macroflow scheduling problem for decreasing application JCT. We propose the Smallest-Macroflow-First (SMF) and Smallest-Average-Macroflow-First (SAMF) heuristics that greedily schedule macroflows based on their network footprint. Trace-driven simulations demonstrate that our algorithms can reduce the average and tail JCT of network-intensive jobs by up to 20% and 25%, respectively; at the same time, the throughput of computation-intensive jobs is increased by up to 2.2×.

Today's cloud is shared among multiple tenants running different applications, and a desirable multi-tenant datacenter network infrastructure should provide bandwidth guarantees for throughput-intensive applications, low latency for latency-sensitive short messages, as well as work conservation to fully utilize the network bandwidth. Despite significant efforts in recent years, none of them can achieve these three properties simultaneously. In this paper, we identify the key deficiency of prior solutions and use this insight to motivate our design of Trinity - a simple, practical yet effective solution that achieves bandwidth guarantees, work conservation and low latency simultaneously in the cloud. We implement Trinity using existing commodity hardwares and demonstrate its superior performance over prior solutions using testbed experiments.

Electric vehicle (EV) taxis have been introduced into the public transportation systems to increase EV market penetration. Different from regular taxis that can refuel in minutes, EV taxis' recharging cycles can be as long as one hour. Due to the long cycle, the bad decision on the charging station, i.e., choosing one without empty charging piles, may lead to a long waiting time of more than an hour in the worst case. Therefore, choosing the right charging station is very important to reduce the overall waiting time. Considering that the waiting time can be a nonnegligible portion to the total work hours, the decision will naturally affect the revenue of individual EV taxis. The current practice of a taxi driver is to choose a station heuristically without a global knowledge. However, the heuristical choice can be a bad one that leads to more waiting time. Such cases can be easily observed in current collected taxi data in Shenzhen, China. Our analysis shows that there exists a large room for improvement in the extra waiting time as large as 30 min/driver. In this paper, we provide a real-time charging station recommendation system for EV taxis via large-scale GPS data mining. By combining each EV taxi's historical recharging events and real-time GPS trajectories, the current operational state of each taxi is predicted. Based on this information, for an EV taxi requesting a recommendation, we can recommend a charging station that leads to the minimal total time before its recharging starts. Extensive experiments verified that our predicted time is relatively accurate and can reduce the cost time of EV taxis by 50% in Shenzhen.

Video-on-demand (VoD) services historically rely on commercial content distribution networks (CDNs) for on-demand capacity provisioning. Content providers gradually prefer a self-managed content infrastructure because of its full control and customization. However, such a dedicated physical infrastructure could be costly in initial capital investment, and complex in management. It has become a promising alternative to host VoD services on pay-as-you-go cloud platforms, on which using dynamic server provisioning to reduce server rental cost is the key objective of content providers. In this paper we address two major challenges to reducing cost: to minimize content reorganization and to tolerate imperfect workload prediction. We first present a practical VoD servicing system design based on a pay-as-you-go cloud. We prove that previous works, focusing exclusively on cost savings, cause significant content reorganization and are vulnerable to imperfect workload prediction. To address such issues, we propose a novel idea called workload absorber, and design a provisioning algorithm called Absorb Window based on the idea. Workload absorbers eliminate the bandwidth wastage and significantly reduce content reorganization. We conduct extensive evaluations with real VoD access traces, and demonstrate the superior scalability of the proposed algorithm by producing highly optimized provisioning in seconds for thousands of servers.

Inter-datacenter wide area networks (inter-DC WAN) carry a significant amount of data transfers that require to be completed within certain time periods, or deadlines. However, very little work has been done to guarantee such deadlines. The crux is that the current inter-DC WAN lacks an interface for users to specify their transfer deadlines and a mechanism for provider to ensure the completion while maintaining high WAN utilization.

In the data flow models of today's data center applications such as MapReduce, Spark and Dryad, multiple flows can comprise a coflow group semantically. Only completing all flows in a coflow is meaningful to an application. To optimize application performance, routing and scheduling must be jointly considered at the level of a coflow rather than individual flows. However, prior solutions have significant limitation: they only consider scheduling, which is insufficient. To this end, we present Rapier, a coflow-aware network optimization framework that seamlessly integrates routing and scheduling for better application performance. Using a small-scale testbed implementation and large-scale simulations, we demonstrate that Rapier significantly reduces the average coflow completion time (CCT) by up to 79.30% compared to the state-of-the-art scheduling-only solution, and it is readily implementable with existing commodity switches.

Summary Over the past decade, content delivery networks (CDNs) have attracted substantial Internet traffic and improved quality of experience for Internet users. However, the evolution of the Internet ecosystem, which is driven by underlying economic incentives and ever emerging technologies, posts great challenges to the existing commercial CDNs (CCDNs). Thoroughly understanding the CDN industry from different aspects including market choice, technology, performance, tendency and infrastructure is indispensable to future Internet. In this paper, we conduct the first comprehensive study of China's CDNs using continuous, at‐scale, content‐driven measurements. Based on the massive amount of measurement data with multidimensional properties, we demystify the CCDNs in China and answer two important questions: (1) what is the development trend of CCDNs in China and (2) what are their unique characteristics. The answers to these questions have significant implications on CDN providers and users. Copyright © 2015 John Wiley & Sons, Ltd.

Efficient sensor network design requires a full understanding of the geometric environment in which sensor nodes are deployed. In practice, a large-scale sensor network often has a complex and irregular topology, possibly containing obstacles/holes. Convex network partitioning, also known as convex segmentation, is a technique to divide a network into convex regions in which traditional algorithms designed for a simple network geometry can be applied. Existing segmentation algorithms heavily depend on concave node detection, or sink extraction from the median axis/skeleton, resulting in sensitivity of performance to network boundary noise. Furthermore, since they rely on the network's 2-D geometric properties, they do not work for 3-D cases. This paper presents a novel segmentation approach based on Morse function, bringing together the notions of convex components and the Reeb graph of a network. The segmentation is realized by a distributed and scalable algorithm, named CONSEL, for CONnectivity-based SEgmentation in Large-scale 2-D/3-D sensor networks. In CONSEL, several boundary nodes first flood the network to construct the Reeb graph. The ordinary nodes then compute mutex pairs locally, generating a coarse segmentation. Next, neighboring regions that are not mutex pairs are merged together. Finally, by ignoring mutex pairs that lead to small concavity, we provide an approximate convex decomposition. CONSEL has a number of advantages over previous solutions: 1) it works for both 2-D and 3-D sensor networks; 2) it uses merely network connectivity information; 3) it guarantees a bound for the generated regions' deviation from convexity. We further propose to integrate network segmentation with existing applications that are oriented to simple network geometry. Extensive simulations show the efficacy of CONSEL in segmenting networks and in improving the performance of two applications: geographic routing and connectivity-based localization.

Many existing data center network (DCN) flow scheduling schemes minimize flow completion times (FCT) based on prior knowledge of flows and custom switch designs, making them hard to use in practice. This paper introduces, Pias, a practical flow scheduling approach that minimizes FCT with no prior knowledge using commodity switches. At its heart, Pias leverages multiple priority queues available in commodity switches to implement a Multiple Level Feedback Queue (MLFQ), in which a PIAS flow gradually demotes from higher-priority queues to lower-priority queues based on the bytes it has sent. In this way, short flows are prioritized over long flows, which enables Pias to emulate Shortest Job First (SJF) scheduling without knowing the flow sizes beforehand. Our preliminary evaluation shows that Pias significantly outperforms all existing information-agnostic solutions. It improves average FCT for short flows by up to 50% and 40% over DCTCP [3] and L2DCT [16]. Compared to an ideal information-aware DCN transport, p-Fabric [5], it only shows 4.9% performance degradation for short flows in a production datacenter workload.

In this paper, we put forward a novel scalable and distributed routing algorithm, called SINUS, for sensor networks deployed on the surface of complex-connected 3D settings such as tunnels, whose topologies are often theoretically modeled as high genus 3D surfaces. SINUS is carried out by first slicing the genus-n surface along a maximum cut set based on Morse theory and Reeb graph, in order to form a genus-0 surface with 2n boundaries. Then, it groups these 2n boundaries into two groups each of which is next connected together. By doing so, a genus-0 surface with exactly two boundaries emerges, which can be flattened into a strip, using the Ricci flow algorithm and next mapped to a planar annulus by Möbius Transform. By assigning nodes virtual coordinates on the planar annulus, SINUS finally realizes a variation of greedy routing to enable individual nodes to make local muting decisions. Our simulation results show that SINUS can achieve low-stretch routing with guaranteed delivery, as well as balanced traffic load.

A cardinal prerequisite for the system design of a sensor network, is to understand the geometric environment where sensor nodes are deployed. The global topology of a large-scale sensor network is often complex and irregular, possibly containing obstacles/holes. A convex network partition, so-called segmentation, is to divide a network into convex regions, such that traditional algorithms designed for a simple geometric region can be applied. Existing segmentation algorithms highly depend on concave node detection on the boundary or sink extraction on the medial axis, thus leading to quite sensitive performance to the boundary noise. More severely, since they exploit the network's 2D geometric properties, either explicitly or implicitly, so far there has been no general 3D segmentation solution. In this paper, we bring a new view to segmentation from a Morse function perspective, bridging the convex regions and the Reeb graph of a network. Accordingly, we propose a novel distributed and scalable algorithm, named CONSEL, for CONnectivity-based SEgmentation in Large-scale 2D/3D sensor networks. Specifically, several boundary nodes first perform flooding to construct the Reeb graph. The ordinary nodes then compute mutex pairs locally, thereby generating the coarse segmentation. Next the neighbor regions which are not mutex pair are merged together. Finally, by ignoring mutex pairs which leads to small concavity, we provide the constraints for approximately convex decomposition. CONSEL is more desirable compared with previous studies: (1) it works for both 2D and 3D sensor networks; (2) it only relies on network connectivity information; (3) it guarantees a bound for the regions' deviation from convexity. Extensive simulations show that CONSEL works well in the presence of holes and shape variation, always yielding appropriate segmentation results.

Many large content publishers use multiple content distribution networks to deliver their content, and many commercial systems have become available to help a broader set of content publishers to benefit from using multiple distribution networks, which we refer to as content multihoming. In this paper, we conduct the first systematic study on optimizing content multihoming, by introducing novel algorithms to optimize both performance and cost for content multihoming. In particular, we design a novel, efficient algorithm to compute assignments of content objects to content distribution networks for content publishers, considering both cost and performance. We also design a novel, lightweight client adaptation algorithm executing at individual content viewers to achieve scalable, fine-grained, fast online adaptation to optimize the quality of experience (QoE) for individual viewers. We prove the optimality of our optimization algorithms and conduct systematic, extensive evaluations, using real charging data, content viewer demands, and performance data, to demonstrate the effectiveness of our algorithms. We show that our content multihoming algorithms reduce publishing cost by up to 40%. Our client algorithm executing in browsers reduces viewer QoE degradation by 51%.

As live streaming networks grow in scale and complexity, they are becoming increasingly difficult to evaluate. Existing evaluation methods including lab/testbed testing, simulation, and theoretical modeling, lack either scale or realism. The industrial practice of gradually-rolling-out in a testing channel is lacking in controllability and protection when experimental algorithms fail, due to its passive approach. In this paper, we design a novel system called ShadowStream that introduces evaluation as a built-in capability in production Internet live streaming networks. ShadowStream introduces a simple, novel, transparent embedding of experimental live streaming algorithms to achieve safe evaluations of the algorithms during large-scale, real production live streaming, despite the possibility of large performance failures of the tested algorithms. ShadowStream also introduces transparent, scalable, distributed experiment orchestration to resolve the mismatch between desired viewer behaviors and actual production viewer behaviors, achieving experimental scenario controllability. We implement ShadowStream based on a major Internet live streaming network, build additional evaluation tools such as deterministic replay, and demonstrate the benefits of ShadowStream through extensive evaluations.

In unstructured peer-to-peer networks, the average response latency and traffic cost of a query are two main performance metrics. Controlled-flooding resource query algorithms are widely used in unstructured networks such as peer-to-peer networks. In this paper, we propose a novel algorithm named Selective Dynamic Query (SDQ). Based on mathematical programming, SDQ calculates the optimal combination of an integer TTL value and a set of neighbors to control the scope of the next query. Our results demonstrate that SDQ provides finer grained control than other algorithms: its response latency is close to the well-known minimum one via Expanding Ring; in the mean time, its traffic cost is also close to the minimum. To our best knowledge, this is the first work capable of achieving a best trade-off between response latency and traffic cost.

This paper presents SHARP: a scalable framework for Dynamic Joint Replica Placement and Request Routing (DJRPRR) scheduling in content delivery networks. After grouping similar proxies and modeling them by a single section, we propose a hierarchical scheduling framework to greatly reduce the dimensions of the mathematical formulation. In every phase the obtained shaped formulation has an easy-solvable form and the complete optimization process is highly scalable. To verify the scalability and effectiveness of our approach, SHARP is evaluated by comprehensive experiment settings which are derived from realistic data/topology of an operational commercial CDN.

Abstract-Underwater Wireless Sensor Networks (UWSNs) can enable a broad range of applications; data aggregation is a fundamental task in such multi-hop wireless sensor networks. To the best of our knowledge, none of existing research works have addressed the interference-free data aggregation scheduling problem in UWSNs. In this paper, we formally define the data aggregation model in UWSNs. We propose a realistic aggregation scheduling scheme together with its theoretical latency bound Rh(C(Δ - 1) + D), where Rhand Δ are the hop radius and the max degree of the network respectively while C and D is a constant. Specifically, we introduce the concept of Virtual Slot to efficiently exploit multiplexing opportunities of time domain. Compared with naively adapted terrestrial algorithms, the evaluation results show that our proposed algorithm achieve far better performance especially when the packet size is small or the node density is high.

User-Generated Content (UGC) is overwhelming the Internet with its interactivity and various contents. However, traditional UGC still have constrains on videos' length and size, which block out a wide variety of potential popular contents. In this paper, we present the first experimental measurements and analysis of an Unconstrained User-Generated Content (UUGC) system - a test site (so-called "T" site in this paper) of a leading VOD service provider in China. This test site is a video-sharing portal just like traditional UGC, while its contents are not constrained by either duration or size. As an UUGC system, its most distinguishing characteristics are the various types of contents uploaded (movie, TV episode, TV show, music, documentary, sports, etc.) and the wide range of uploaders, which make it an interesting case study. By matching relative key words in video's index, we classify the contents into several basic types and analyze the statistics of three major types - movie, TV episode and TV show (labeled MVI, TV-E and TV-S). For further study of various contents, we demonstrate the patterns of flash crowd triggering of MVI, TV-E and TV-S with several typical cases. To find out the viewers' consumption pattern, we investigate daily & weekly cycles, as well as grouping the videos by age and exhibiting the popularity evolution. By means of curve fitting with multiple known distributions to video view traces, we show that power law with exponential cutoff best fits the videos' popularity distribution for this UUGC system.

Dynamic application placement for clustered web applications heavily influences system performance and quality of user experience. Existing approaches claim that they strive to maximize the throughput, keep resource utilization balanced across servers, and minimize the start/stop cost of application instances. However, they fail to minimize the worst case of server utilization; the load balancing performance is not optimal. What's more, some applications need to communicate with each other, which we called dependent applications; the network cost of them also should be taken into consideration. In this paper, we investigate how to minimize the resource utilization of servers in the worst case, aiming at improving load balancing among clustered servers. Our contribution is two-fold. First we propose and define a new optimization objectives: limiting the worst case of each individual server's utilization, formulated by a min-max problem. A novel framework based on binary search is proposed to detect an optimal load balancing solution. Second, we define system cost as the weighted combination of both placement change and inter-application communication cost. By maximizing the number of instances of dependent applications that reside in the same set of servers, the basic load-shifting and placement-change procedures are enhanced to minimize whole system cost. Extensive experiments have been conducted and effectively demonstrate that: 1) the proposed framework achieves a good allocation for clustered web applications. In other words, requests are evenly allocated among servers, and throughput is still maximized; 2) the total system cost maintains at a low level; 3) our algorithm has the capacity of approximating an optimal solution within polynomial time and is promising for practical implementation in real deployments.

Data collection is of paramount importance in many applications of wireless sensor networks (WSNs). Especially, to accommodate ever increasing demands of signal source coding applications, the capacity of processing multi-user data query is crucial in WSNs where the efficiency is one key consideration. To that end, this paper presents EDCA: an Efficient Data Collection Approach for data query in WSNs, which exploits recent matrix completion techniques. Specifically, for the efficiency of energy consumption, we randomly select a part of nodes from the sensor network to sample at each time instance and directly forward the data to the sink. Then, to recover the data precisely, we shift the rank minimization problem, which is NP-hard, to a convex optimization one. Compared with the centralized scheme, energy consumption using EDCA is significantly reduced due to lower sampling rate and fewer packets to transmit. The experimental results demonstrate that EDCA significantly outperforms the existing naive method in terms of energy consumption and the introduced errors are quite trivial.

Many sensor network applications are tightly coupled with the geometric environment where the sensor nodes are deployed. The topological skeleton extraction for the topology has shown great impact on the performance of such services as location, routing, and path planning in wireless sensor networks. Nonetheless, current studies focus on using skeleton extraction for various applications in wireless sensor networks. How to achieve a better skeleton extraction has not been thoroughly investigated. There are studies on skeleton extraction from the computer vision community; their centralized algorithms for continuous space, however, are not immediately applicable for the discrete and distributed wireless sensor networks. In this paper, we present a novel Connectivity-bAsed Skeleton Extraction (CASE) algorithm to compute skeleton graph that is robust to noise, and accurate in preservation of the original topology. In addition, CASE is distributed as no centralized operation is required, and is scalable as both its time complexity and its message complexity are linearly proportional to the network size. The skeleton graph is extracted by partitioning the boundary of the sensor network to identify the skeleton points, then generating the skeleton arcs, connecting these arcs, and finally refining the coarse skeleton graph. We believe that CASE has broad applications and present a skeleton-assisted segmentation algorithm as an example. Our evaluation shows that CASE is able to extract a well-connected skeleton graph in the presence of significant noise and shape variations, and outperforms the state-of-the-art algorithms.

Existing terrestrial synchronization protocols including RBS, FTSP, TPSN, LTS and TSHL have already achieved high precision in radio networks, but none of them perform well in high latency networks like acoustic sensor networks. In this paper, we present tri-message: a lightweight time synchronization protocol for high latency and resource-constrained networks. As its name suggests, only three message exchanges are required in one synchronization process. Meanwhile, tri-message utilizes very simple mathematical operations to calculate the clock skew and offset. Specially, tri-message is feasible for many extremely long latency applications such as space exploration because it has an increasing synchronization precision with the increasement of distance.

Many sensor network applications are tightly coupled with the geometric environment where the sensor nodes are deployed. The topological skeleton extraction has shown great impact on the performance of such services as location, routing, and path planning in sensor networks. Nonetheless, current studies focus on using skeleton extraction for various applications in sensor networks. How to achieve a better skeleton extraction has not been thoroughly investigated. There are studies on skeleton extraction from the computer vision community; their centralized algorithms for continuous space, however, is not immediately applicable for the discrete and distributed sensor networks. In this paper we present CASE: a novel connectivity-based skeleton extraction algorithm to compute skeleton graph that is robust to noise, and accurate in preservation of the original topology. In addition, no centralized operation is required. The skeleton graph is extracted by partitioning the boundary of the sensor network to identify the skeleton points, then generating the skeleton arcs, connecting these arcs, and finally refining the coarse skeleton graph. Our evaluation shows that CASE is able to extract a well-connected skeleton graph in the presence of significant noise and shape variations, and outperforms state-of-the-art algorithms.

This paper presents BCube, a new network architecture specifically designed for shipping-container based, modular data centers. At the core of the BCube architecture is its server-centric network structure, where servers with multiple network ports connect to multiple layers of COTS (commodity off-the-shelf) mini-switches. Servers act as not only end hosts, but also relay nodes for each other. BCube supports various bandwidth-intensive applications by speeding-up one-to-one, one-to-several, and one-to-all traffic patterns, and by providing high network capacity for all-to-all traffic.

Current implementations of BitTorrent-like P2P applications ignore the underlying Internet topology hence incur a large amount of traffic both inside an Internet service provider (ISP)' national backbone networks and over cross-ISP Internet working links. These traffics not only occupy costly bandwidth, but also increase user perceived response latency. ISP-biased neighbor selection proposes to exploit peers' topological locality by biased neighbor selection, in which a peer chooses the majority of its neighbors from peers within the same ISP. In this paper, we propose to further exploit peers' geographic locality. First we improved ISP-biased neighbor selection (ISP-Biased+) to take into consideration network locality (or, city locations) within the same ISP. When required neighbor number is relatively much less than seeds available, ISP-biased neighbor selection+ performs much better than original approach, proved by simulations. Next, we propose that a peer could also choose its neighbors from peers of different ISPs within the same city with priority: assist by a well-know Chinese operator's unique ISP-internetworking content distribution network (CDN), these local cross-ISP traffics can be routed through local CDN cite. Using simulations, we show that cross-ISP traffic burden can be completely shifted to CDN local links and backbone traffic. At the same time, user perceived delay can be significantly reduced.

Controlled-flooding algorithms are widely used in unstructured networks. Expanding ring (ER) achieves low response delay, while its traffic cost is huge; dynamic querying (DQ) is known for its desirable behavior in traffic control, but it achieves lower search cost at the price of an undesirable latency performance; Enhanced dynamic querying (DQ+) can reduce the search latency too, while it is hard to determine a general optimum parameters set. In this paper, a novel algorithm named selective dynamic query (SDQ) is proposed. Unlike previous works that awkwardly processing floating TTL values, SDQ properly select an integer TTL value and a set of neighbors to narrow the scope of next query. Our experiments demonstrate that SDQ provides finer-grained control than other algorithms: its latency is close to the well-known minimum one via ER; in the mean time its traffic cost also close to the minimum. To our best knowledge, this is the first work capable of achieving best performance in terms of both response latency and traffic cost. In addition, our experiments also demonstrate that SDQ works well in various network topologies.