We present AutoSchemaKG, a framework for fully autonomous knowledge graph construction that eliminates the need for predefined schemas. Our system leverages large language models to simultaneously extract knowledge triples and induce comprehensive schemas directly from text, modeling both entities and events while employing conceptualization to organize instances into semantic categories. Processing over 50 million documents, we construct ATLAS (Automated Triple Linking And Schema induction), a family of knowledge graphs with 900+ million nodes and 5.9 billion edges. This approach outperforms state-of-the-art baselines on multi-hop QA tasks and enhances LLM factuality. Notably, our schema induction achieves 92\% semantic alignment with human-crafted schemas with zero manual intervention, demonstrating that billion-scale knowledge graphs with dynamically induced schemas can effectively complement parametric knowledge in large language models.

We develop a unified mathematical framework for certified Top-$k$ attention truncation that quantifies approximation error at both the distribution and output levels. For a single attention distribution $P$ and its Top-$k$ truncation $\hat P$, we show that the total-variation distance coincides with the discarded softmax tail mass and satisfies $\mathrm{TV}(P,\hat P)=1-e^{-\mathrm{KL}(\hat P\Vert P)}$, yielding sharp Top-$k$-specific bounds in place of generic inequalities. From this we derive non-asymptotic deterministic bounds -- from a single boundary gap through multi-gap and blockwise variants -- that control $\mathrm{TV}(P,\hat P)$ using only the ordered logits. Using an exact head-tail decomposition, we prove that the output error factorizes as $\|\mathrm{Attn}(q,K,V)-\mathrm{Attn}_k(q,K,V)\|_2=τ\|μ_{\mathrm{tail}}-μ_{\mathrm{head}}\|_2$ with $τ=\mathrm{TV}(P,\hat P)$, yielding a new head-tail diameter bound $\|\mathrm{Attn}(q,K,V)-\mathrm{Attn}_k(q,K,V)\|_2\leτ\,\mathrm{diam}_{H,T}$ and refinements linking the error to $\mathrm{Var}_P(V)$. Under an i.i.d. Gaussian score model $s_i\sim\mathcal N(μ,σ^2)$ we derive closed-form tail masses and an asymptotic rule for the minimal $k_\varepsilon$ ensuring $\mathrm{TV}(P,\hat P)\le\varepsilon$, namely $k_\varepsilon/n\approxΦ_c(σ+Φ^{-1}(\varepsilon))$. Experiments on bert-base-uncased and synthetic logits confirm the predicted scaling of $k_\varepsilon/n$ and show that certified Top-$k$ can reduce scored keys by 2-4$\times$ on average while meeting the prescribed total-variation budget.

Rack-aware storage systems organize the storage nodes in racks such that the cross-rack communication cost is much more expensive than the intra-rack communication cost. In this paper, we primarily investigate the cross-rack update bandwidth defined as the average amount of symbols transferred across different racks during an update process of one single node. It is critical to design erasure codes that minimize the cross-rack update bandwidth. Our main contributions are as follows. First, we establish the model of cross-rack update bandwidth of irregular array codes over rack-aware storage systems. Second, we derive the tight lower bound on cross-rack update bandwidth, and define minimum cross-rack update bandwidth (MCUB) codes as the irregular array codes that can achieve our tight lower bound. Third, we derive the tight lower bound on redundancy defined as the total number of parity symbols for MCUB codes, and define minimum redundancy MCUB (MR-MCUB) codes as the MCUB codes that can achieve the redundancy lower bound. Fourth, we present explicit constructions of MR-MCUB codes that achieve both the minimum cross-rack update bandwidth and the minimum redundancy, which means that the two lower bounds are tight. Last, we define intra-rack update bandwidth as the average amount of symbols incurred within one rack in an update process, and derive the lower bound of intra-rack update bandwidth of MCUB codes. Moreover, we show that our MCUB codes constructions can also achieve the lower bound of intra-rack update bandwidth.

In-memory key-value storage necessitates a substantial quantity of computation and storage resources for both performance and scalability, thereby diminishing the resources available for user applications. The emergence of programmable network hardware, including SmartNICs and programmable switches, provides the opportunity to offload operations from server CPUs. We present Epiphron, a novel distributed in-memory key-value store architecture that co-designs with off-path SmartNICs and programmable switches. Facing the limited performance of off-path SmartNICs, Epiphron successfully achieves high resource efficiency while keeping load balancing and fault tolerance by$(i)$hybridizing erasure coding with replication in storage management,$(ii)$accelerating read operations with a new data plane design (conflict detection and RDMA-compatible forwarding) on programmable switches,$(iii)$employing a network protocol extended from one-sided RDMA. We evaluate Epiphron on Barefoot Tofino switches, NVIDIA BlueField-2 SmartNICs, and commodity servers. The experimental results demonstrate that compared to existing solutions, Epiphron improves throughput by up to 2.2× and consumes 47% less memory while completely bypassing server CPUs.

Recent popular programmable switches provide programmability in packet processing at the line rate, promising to host various Network Functions (NFs). However, the limitations on the switch programmability make it unable to manage runtime dynamic NF states. In the status quo, on-switch NFs rely on the network controller for dynamic state management, suffering from high first-packet latency. This paper proposes DNF, a hardware-software co-design system for dynamic state management of network functions on programmable switches. DNF designs a dynamic State Table on the switch, which providesopportunisticservice to NF flows and sets upfallbackNFs on the server to handle flows that fail on the switch. DNF proposes a state pre-computation andruntime-bindingmethod for per-flow state initialization, which avoids a flow’s runtime interaction with the controller and the consequent latency. DNF devises astate replacementmethod, which periodically swaps hot flows into the switch. It could maximize the switch resource utilization and the throughput. We prototype DNF on P4 switches, implement six representative NFs, and compare DNF with state-of-the-art solutions. Our experiments show DNF reduces the first-packet latency by up to 98% compared with the controller-assisted architecture and improves the system throughput by up to 4.87 times compared with the software solution.

High-capacity solid-state drives (SSDs) with expected capacities of one PByte and more will address cloud storage and archiving environments previously dominated by magnetic disks. These new applications are very cost-sensitive, so unnecessary overhead must be reduced as much as possible without sacrificing the performance advantages of SSDs. An expensive component within a scale-up SSD is the on-device memory to map host logical page numbers to flash pages. This article, therefore, proposes HyTorC, which builds on the idea of S-FTL to represent sequentially stored logical pages using bitmaps instead of providing one entry per logical page. HyTorC extends this idea by introducing, for the first time in an FTL, compression of these bitmaps using run-length encoding, and by investigating the effects of background scrubbing to realign randomly written pages into contiguous runs. This background scrubbing allows HyTorC to keep large portions of the mapping table in block mapping mode, further reducing the memory footprint. HyTorC retains the flexibility of the page mapping scheme and supports compression of logical blocks within the SSD, allowing multiple compressed logical pages to be stored within a single physical page. HyTorC is fully implemented in an open-channel SSD. Our tests show that HyTorC can reduce memory consumption by an average of 98.9% over standard page mapping, 95.6% over the DFTL scheme, 87.3% over S-FTL, and 56.5% over the learned index-based approach LeaFTL for the Alibaba Cloud block traces, and by 98.6% over standard page mapping, 95.5% over the DFTL scheme, 84.1% over S-FTL, and 61.5% over LeaFTL for the Microsoft Research Cambridge traces. HyTorC focuses on the memory footprint of the FTL and not on performance. However, the performance evaluation shows that HyTorC achieves similar performance compared to page mapping and FTLs based on learned indexes.

Data plane verification (DPV) can be critical in ensuring the network operates correctly. To be useful in practice, they need to be: (1) fast so as to prevent significant packet loss or security violations; (2) scalable so as to accommodate today's large-scale network architecture. Current DPV tools struggle to meet these requirements due to their centralized architecture. To be concrete, there is a bottleneck for a single-point server to perform real-time DPV tasks. Furthermore, a single-point server makes it hard to collect real-time data plane updates from every device in large-scale networks.

Neural Vector Search (NVS) has exhibited superior search quality over traditional key-based strategies for information retrieval tasks. An effective NVS architecture requires high recall, low latency, and high throughput to enhance user experience and cost-efficiency. However, implementing NVS on existing neural network accelerators and vector search accelerators is sub-optimal due to the separation between the embedding stage and vector search stage at both algorithm and architecture levels. Fortunately, we unveil that Product Quantization (PQ) opens up an opportunity to break separation. However, existing PQ algorithms and accelerators still focus on either the embedding stage or the vector search stage, rather than both simultaneously. Simply combining existing solutions still follows the beaten track of separation and suffers from insufficient parallelization, frequent data access conflicts, and the absence of scheduling, thus failing to reach optimal recall, latency, and throughput. To this end, we propose a unified and efficient NVS accelerator dubbed NeuVSA based on algorithm and architecture co-design philosophy. Specifically, on the algorithm level, we propose a learned PQ-based unified NVS algorithm that consolidates two separate stages into the same computing and memory access paradigm. It integrates an end-to-end joint training strategy to learn the optimal codebook and index for enhanced recall and reduced PQ complexity, thus achieving smoother acceleration. On the architecture level, we customize a homogeneous NVS accelerator based on the unified NVS algorithm. Each sub-accelerator is optimized to exploit all parallelism exposed by unified NVS, incorporating a structured index assignment strategy and an elastic on-chip buffer to alleviate buffer conflicts for reduced latency. All sub-accelerators are coordinated using a hardware-aware scheduling strategy for boosted throughput. Experimental results show that the joint training strategy improves recall by 4.6% over the separated strategy and accuracy by 43.5% over LUT-NN. NeuVSA achieves $2.82 \times$ to $416.17 \times$ lower latency over CPU, GPU, DFX+ANNA, and PQA+ANNA, and up to $49.60 \times$ and $10.57 \times$ higher average throughput over CPU and GPU, respectively. NeuVSA also reduces chip area by 65.2% over PQA+ANNA.

Graph stream is a special kind of data stream, where every item coming in sequence represents an edge in a dynamic graph. Graph stream has wide application in many fields, including cyber security, social networks and financial fraud detection. In this paper, we propose HourglassSketch, a two-stage data structure, for high-accuracy graph stream summarization. In Stage 1, HourglassSketch uses a CocoSketch to accurately record a partial collection of large-weight edges. In Stage 2, HourglassSketch integrates a TowerSketch with a TCMSketch to approximately record the statistics of most small-weight edges. In addition, we propose a key technique named Error Funnel to further reduce its error margin. Theoretical analysis and experimental results demonstrate that HourglassSketch supports various kinds of query operation and adapts well to graph stream storage. HourglassSketch achieves up to 100x smaller error and 2.7x higher speed than prior work. We also explore the versatility of HourglassSketch as a hardware-friendly framework by implementing it on FPGA and P4 platforms. We have released our codes on GitHub.

Analog error-correcting codes (Analog ECCs) can effectively detect and correct computational errors generated during vector-matrix multiplication in the real domain. Recently, several related classes of single-error and multiple-error Analog ECCs have been proposed. However, most existing constructions encounter limitations such as high storage overhead, limited code length range, and high decoding complexity, which diminish their practical applicability. In this paper, we first propose a new framework for generating MDS Analog ECCs with arbitrary code length for single-error detection and correction. Utilizing this framework, we propose a new decoding algorithm for our codes with lower decoding complexity than the existing decoding method. We divide decoding algorithm into two parts: syndrome calculation and error correction. We show that the error correction complexity of our method which is explicit is$O(\log (n))$, while the error correction complexity of existing decoding method based on geometric features which is not explicit is at least$O(n)$, here$n$represents the code length. Simulation experiments demonstrate that our decoding algorithm maintains a high error correction success rate for correcting a single outlying error, even when the error scale is significantly below our established theoretical threshold.

Piggybacking codes have garnered extensive research attention for their potential to reduce the repair bandwidth of traditional maximum distance separable (MDS) codes. The existing piggybacking codes are only considered for improving the repair performance for single-node erasure. In this paper, we propose a new piggybacking code construction with a small sub-packetization level. Through carefully designed piggyback functions, our code can effectively reduce the repair bandwidth for both single-node and double-node erasures. Specifically, we show that when$r$is large and$r \ll k$(here,$r$represents the number of parity nodes and$k$represents the number of data nodes), our code can achieve a reduction in the average repair bandwidth for double-node erasure by approximately 33 %, and for single-node erasure by around 50 %, when compared to the traditional MDS property-based repair method. To our knowledge, this is the first exploration for efficient repair of multi-node erasure under the piggybacking framework.

Matrix multiplication over the real field constitutes a foundational operation in the training of deep learning models, serving as a computational cornerstone for both forward and backward propagation processes. However, the presence of silent data corruption (SDC) in large-scale distributed training environments poses a significant threat to model convergence and predictive accuracy, particularly when such errors manifest during matrix multiplication. Due to their transient and non-intrusive nature, these errors often evade detection, allowing them to propagate and accumulate over time, ultimately leading to substantial degradation in model performance. In this paper, we introduce a novel error-correcting coding framework specifically tailored for matrix multiplication operations. Our proposed framework is designed to detect and correct multiple computational errors that may arise during the execution of matrix products. By leveraging a grid-based structural encoding scheme, our approach enhances error localization and correction capabilities across all participating matrices, thereby significantly improving the fault tolerance of the computation. Experimental results demonstrate that our method achieves deterministic correction of up to two erroneous symbols distributed across three matrices with 100% reliability, while incurring only a 24% overhead in computational time on GPU architectures. Furthermore, we provide a rigorous theoretical analysis of the error-correction properties inherent to our coding scheme, establishing its correctness and robustness under well-defined fault models.

GPU Direct Storage (GDS) plays a vital role in GPU-based training and inference systems, leveraging Peer-to-Peer Direct Memory Access (P2P-DMA) to establish a direct data transfer path between the GPU and the storage device. The direct I/O path reduces GPU storage access latency and CPU overhead, thus improving the efficiency of data transfer. Currently, however, GDS employs a phony buffer in the host memory to interact with the Linux kernel, which results in suboptimal I/O performance, extra resource consumption, and high deployment complexity.

Maximum distance separable (MDS) codes in distributed storage systems provide the optimal tradeoff between fault tolerance and storage overhead. As a kind of MDS codes, minimum storage regenerating (MSR) codes have attracted a lot of attention since they are also optimal in terms of repair bandwidth. However, MSR codes suffer from a high repair degree, meaning many helper nodes are needed in the node repair process. Compared to MSR codes, locally repairable codes (LRCs) can significantly reduce the repair degree at the cost of increased storage overhead. The recently introduced concept of vector LRCs combines the advantages of MSR codes and LRCs, providing a tradeoff between repair degree/repair bandwidth and storage overhead. Most existing vector LRCs are built on MSR codes or their shortened versions. However, existing MSR codes have an unavoidably large sub-packetization levels, which also result in large sub-packetization levels in the corresponding vector LRCs. In this paper, we propose a new vector LRC structure, where MDS array codes (without shortening) can be employed as the local codes. Based this new structure, we propose three constructions of vector LRCs with small sub-packetization levels and small repair bandwidth, whose required field sizes are comparable to the code lengths. Additionally, the first two constructions offer a flexible tradeoff between the sub-packetization level and the repair bandwidth, while the third construction has a sub-packetization level of 2, making it easy to implement. Compared to existing vector LRCs, the new vector LRCs provide significantly smaller sub-packetization levels and support a wider range of parameters.

Piggybacking codes are a class of maximum distance separable (MDS) array codes that can achieve repair bandwidth reduction of single-node erasure by adding some piggyback functions to a subset of parity symbols. However, the repair bandwidth reduction is limited since the number of parity symbols the piggyback function can be added should be strictly less than a value to maintain the MDS property. In this paper, we first propose a new transformation on parity nodes that can effectively reduce the repair bandwidth of parity nodes, and the MDS property can still be maintained without changing the field size of the base code. Combined with the new transformation, we jointly design piggyback functions to reduce the repair bandwidth of data nodes. Since the new transformation no longer obeys the constraints under the piggybacking framework, we call the newly obtained codes aspiggybacking+codes. We theoretically show that the repair bandwidth of the piggybacking+ code is strictly lower than that of the existing piggybacking codes at high-code-rate parameters. We also show that our piggybacking+ codes have 3% to 29% repair bandwidth reduction than the existing piggybacking codes for the evaluated high-code-rate parameters.

Reed-Solomon (RS) codes are widely used to correct errors in storage systems. Finding the error locator polynomial is one of the key steps in the error correction procedure of RS codes. Modular Approach (MA) is an effective algorithm for solving the Welch-Berlekamp (WB) key-equation problem to find the error locator polynomial that needs$2t$steps, wheretis the error correction capability. In this paper, we first present a new MA algorithm that only requires$2e$steps and then propose two fast decoding algorithms for RS codes based on our MA algorithm, whereeis the number of errors and$e\leq t$. We propose the Improved-Frequency Domain Modular Approach (I-FDMA) algorithm that needs$2e$steps to solve the error locator polynomial and present our first decoding algorithm based on the I-FDMA algorithm. We show that, compared with the existing methods based on MA algorithms, our I-FDMA algorithm can effectively reduce the decoding complexity of RS codes when$e\lt t$. Furthermore, we propose the$t_{0}$-Shortened I-FDMA ($t_{0}$-SI-FDMA) algorithm ($t_{0}$is a predetermined even number less than$2t-1$) based on the new termination mechanism to solve the error numberequickly. We propose our second decoding algorithm based on the SI-FDMA algorithm for RS codes and show that the multiplication complexity of our second decoding algorithm is lower than our first decoding algorithm (the I-FDMA decoding algorithm) when$2e\lt t_{0}+1$.

Key-value stores in Cloud environments can contain more than 2 45 unique elements and be larger than 100 PByte. B + -Trees are well suited for these larger-than-memory datasets and seamlessly index data stored on thousands of secondary storage devices. Unfortunately, it is often uneconomical to even store all inner tree nodes in memory for these dataset sizes. Therefore, lookup performance is affected by the additional IOs for reading inner nodes. This number of inner nodes can be reduced by increasing the size of leaf nodes. We propose HLN-Trees, which support huge leaf nodes without increasing the IO sizes for individual index operations. They partition leaf nodes in arrays of independent subnodes and combine ideas from BD-trees with rebalancing, learning key deviations, and storing locality predictors. HLN-Trees have been initially designed for uniform random key distributions and support arbitrary key distributions through an additional layer of hashing in leaf nodes. HLN-Trees decrease the number of inner nodes by up to 256× for uniform random key distributions and by 16× to 64× for arbitrary ones compared to B + -Trees, while keeping their performance at the same level even at high concurrency levels. We show analytically and through real-world and synthetic benchmarks that HLN-Trees also outperform state-of-the-art learned indexes for secondary storage.

Nowadays, data centers consolidate latency-critical (LC) tenants and best-effort (BE) tenants on the same cloud platform to increase resource utilization and reduce costs. In such a scenario, the underlying distributed storage systems are responsible for guaranteeing SLOs for LC tenants while maximizing bandwidth for BE tenants. As high-performance NVMe SSDs are widely deployed, how to make full use of their performance capabilities and guarantee SLOs has become an urgent problem. However, current methods restrict the performance capabilities of NVMe SSDs based on a conservative offline model, and also ignore runtime changes in tenant loads and device states, which definitely affect the performance capabilities.

Log-structured merge tree (LSM-tree) has been widely adopted by modern key-value stores. Deploying LSM-tree across heterogeneous SSD storage which combines the fast but expensive NVMe storage tier with the slow but economical SATA storage tier has emerged as the optimal choice for maximizing cost-effectiveness. However, existing studies typically focus on optimizing the performance of individual storage layers, thereby impeding the full utilization potential of both storage layers. We notice that they tend to over-rely on one storage layer and underutilize the other. In this paper, we present HyperDB, a novel hybrid key-value store designed to enhance the overall performance of both layers via deploying tailored data structures in different media. Especially, HyperDB devises a zone-based data layout for NVMe SSDs to reduce migration overhead, while also implementing a semi-sorted table on the SATA storage layer to minimize merge overhead. Furthermore, we propose a preemptive compaction method at the block-granularity level to further alleviate resource consumption caused by background compaction. Experimental results show that HyperDB achieves 2.25 × faster on average throughput and a 60.3% reduction in background task traffic, compared to the standard use of RocksDB in data centers today.

Although the native RDMA interface allows for high throughput and low latency, its low-level abstraction raises significant programming challenges. Consequently, numerous systems encapsulate the RDMA interface into more user-friendly high-level abstractions such as Socket, MPI, and RPC. However, this ease of development often incurs considerable performance degradation. To address this trade-off, this paper introduces RB2, a high-performance RDMA-based Distributed Ring Buffer (DRB). RB2serves as a middle layer that effectively conceals the low-level details of the RDMA interface while also facilitating extension to other high-level abstractions.Nonetheless, it is non-trivial for DRBs to preserve the RDMA performance. We optimize the performance of RB2in three aspects. First, we perform micro-benchmarks to identify the pointer synchronization methods that are seemingly counter-intuitive but offer optimal performance improvements. Second, we propose an adaptive batching mechanism to alleviate the limitations of conventional fixed batching. Finally, we build an efficient memory subsystem using various optimization techniques. RB2outperforms SOTA designs by achieving 2.5 × to 7.5 × throughput while maintaining comparable tail latency for small messages.

In-memory database in the data center plays an indispensable role in many fields. B+tree is the most recognized index in in-memory database, but its indexing latency has become the bottleneck that prevents the database from achieving higher performance. The existing work reduces latency by caching B+tree nodes using slow DRAM on computing clients, or directly caching data using fast SRAM on programmable switch. However, no existing work can meet all three key requirements: (1) Efficiency: providing enough fast memory to accelerate indexing. (2) Compatibility: compatible with multiple architectures and query types. (3) Adaptability: adapting to various workloads and database scales. Inspired by structrual similarity between the network topology of modern data centers and the B+tree structure, we propose Fat-B+Tree, which embeds the B+tree into the in-network fast memory provided by the hierarchical connected programmable switches, thus meeting all design requirements. We have fully implemented the Fat-B+Tree prototype, and the experimental results show that compared with the baseline system, it reduces query latency by up to 76% and improves throughput by up to 3.93 times. The source codes of Fat-B+Tree are open-sourced at GitHub.

Reed-Solomon (RS) codes are widely used to correct errors, finding the error locator polynomial is one of the key steps in the error correction procedure of RS codes. Modular Approach (MA) is a classical algorithm to solve the Welch-Berlekamp (WB) key-equation problem to find the error locator polynomial that needs$2t$steps, where$t$is the error correction capability. In this paper, we present a new MA algorithm that only requires$2e$steps, where$e$is the number of errors. Moreover, we propose a new error correction algorithm based on our MA algorithm, which is called the Improved-Frequency Domain Modular Approach (I-FDMA) algorithm. We show that, compared with the existing methods based on MA algorithms, our I-FDMA algorithm can effectively reduce the decoding complexity of RS codes when$e < t$.

Erasure codes have been widely employed in distributed storage systems to provide high data reliability at a cost of small redundancy. Modern distributed storage systems usually organize the storage nodes in racks, in which the cross-rack communication cost is much more expensive than the intra-rack communication cost. When the original data symbols stored in a single node are updated, it is critical to design erasure codes that can update the corresponding coded symbols with the cross-rack update bandwidth defined as the average amount of symbols transferred across different racks as small as possible. In this paper, we first derive a tight lower bound on the cross-rack update bandwidth under the condition of$(n, k)$reconstruction property that is any$k$out of the$n$nodes can retrieve all the data symbols. Moreover, we derive the lower bound on redundancy subject to the minimum cross-rack update bandwidth. Furthermore, we propose explicit constructions that can achieve both the minimum cross-rack update bandwidth and the minimum redundancy.

Maximum distance separable (MDS) codes facilitate the achievement of elevated levels of fault tolerance in storage systems while incurring minimal redundancy overhead. Reed-Solomon (RS) codes are typical MDS codes with the sub-packetization level being one, however, they require large repair bandwidth defined as the total amount of symbols downloaded from other surviving nodes during single-node failure/repair. In this paper, we present the set transformation, which can transform any MDS code into set transformed code such that (i) the sub-packetization level is flexible and ranges from 2 to$(n-k)^{\lfloor\frac{n}{n-k}\rfloor}$in which$n$is the number of nodes and$k$is the number of data nodes, (ii) the new code is MDS code, (iii) the new code has lower repair bandwidth for any single-node failure. We show that our set transformed codes have both lower repair bandwidth and lower field size than the existing related MDS array codes, such as elastic transformed codes [1]. Specifically, our set transformed codes have 2% - 6.6% repair bandwidth reduction compared with elastic transformed codes [1] for the evaluated typical parameters.

Reed-Solomon (RS) codes are widely used in storage systems to ensure data reliability. In this paper, we first propose a new construction of RS codes with between three to five parity symbols over a special finite field of size 256. We show that all the operations involved in the encoding/decoding process can be implemented by XOR and cyclic shift. Second, we present a fast encoding/decoding algorithm for our codes by designing a modified Reed-Muller (RM) transform that has both small computational complexity and space complexity. We show that our codes have much lower space complexity and nearly the same computational complexity, compared with the existing RM-based RS codes. Simulation results demonstrate that our codes improve encoding and decoding throughput by 34.06% and 31.66%, respectively, under evaluated parameters, compared with existing RM-based RS codes.

As maximum distance separable (MDS) array codes, piggybacking codes can effectively reduce the repair bandwidth of traditional MDS codes for single-node failure with small sub-packetization. However, the requirement of maintaining MDS property over small field size imposes severe restrictions on the design of piggyback functions in the piggybacking framework, which limits the reduction of repair bandwidth. In this paper, we propose conjugate-piggybacking codes over a small sub-packetization level. We design conjugate transformation for piggyback functions in our codes, which enables some parity nodes to achieve optimal repair bandwidth. We show that our codes are MDS codes over a slightly larger field size than the existing related piggybacking codes. We also show that our codes have lower repair bandwidth than the existing related piggybacking codes under evaluated high-code-rate parameters and$\mathbb{F}_{2^{8}}$.

As a special class of array codes, piggybacking codes are maximum distance separable (MDS) codes that can achieve low repair bandwidth for single-node erasure. An (n,k,m) piggybacking code containskdata nodes andr=n-kparity nodes, each node storesmsymbols. In this paper, we propose a new piggybacking design by jointly designing piggyback functions for both data node repair and parity node repair to reduce the repair bandwidth. Our piggybacking codes can support flexible sub-packetizationmwith 2 ≤m≤r. Whenm=r, we derive a new lower bound of repair bandwidth based on our piggybacking structure and show that this lower bound is lower than the corresponding lower bounds derived from the existing piggybacking codes for 5r≪k. Whenmr, we show that our piggybacking codes have lower repair bandwidth than the existing piggybacking codes for all the evaluated high-code-rate parameters with 10 ≤r≤ 20,k= 100 andm≤ 5. Moreover, we derive the lower bound of repair complexity defined as the number of multiplication operations required in repairing single-node erasure under general piggybacking framework and show that our codes can achieve the repair complexity lower bound, i.e., our codes have optimal repair complexity.

Maximum distance separable (MDS) codes have the optimal trade-off between storage efficiency and fault tolerance, which are widely used in distributed storage systems. As typical non-MDS codes, simple regenerating codes (SRCs) can achieve both smaller repair bandwidth and smaller repair locality than traditional MDS codes in repairing single-node erasure. In this paper, we propose generalized simple regenerating codes (GSRCs) that can support much more parameters than that of SRCs. We show that there is a trade-off between sub-packetization and fault tolerance in our GSRCs, and SRCs achieve a special point of the trade-off of GSRCs. We show that the fault tolerance of our GSRCs increases when the sub-packetization increases linearly. We also show that our GSRCs can locally repair any single-symbol erasure and any single-node erasure, and the repair bandwidth of our GSRCs is smaller than that of the existing related codes.

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

As a special class of array codes,$(n,\ k,\ m)$piggy-backing codes are$n\times m$MDS array codes with each node storing$m$symbols that can achieve low repair bandwidth for single-node failure. The existing piggybacking codes design piggyback functions for either data node repair or parity node repair. In this paper, we propose new piggybacking codes by jointly designing piggyback functions for both data node repair and parity node repair that have lower repair bandwidth than the related existing piggybacking codes. In our piggybacking codes, the sub-packetization$m$satisfies that$2\leq m\leq n-k$. When$m=n-k$, we derive a lower bound of repair bandwidth for our piggybacking codes, and prove that this lower bound is lower than the corresponding lower bounds of the existing piggybacking codes for$5 < n-k\ll k$. When$m < n-k$, we show that our piggybacking codes have lower repair bandwidth than the existing piggybacking codes for all the evaluated high-code-rate parameters with$10 < n-k < 20, k=100$and$m\leq 5$.

In distributed storage systems, storage nodes are organized in racks in which the cross-rack communication cost is much more expensive than the intra-rack communication cost. It is critical to design erasure codes that minimize the cross-rack update bandwidth which is defined as the total amount of symbols transferred across different racks during an update process. In this paper, we analyze the cross-rack update bandwidth of erasure codes for distributed storage systems. We derive a lower bound on the cross-rack update bandwidth and show that the proposed lower bound is achievable under certain parameters.

Piggybacking codes are a class of maximum distance separable (MDS) array codes that can achieve repair bandwidth reduction of single-node failure by adding some piggyback functions in a subset of parity symbols. However, the repair bandwidth reduction is limited since the number of parity symbols of which the piggyback function can be added should be strictly less than a value in order to maintain the MDS property. In this paper, we present a new class of MDS array codes, call piggybacking+ codes with linear sub-packetization level and small finite field that can achieve lower repair bandwidth compared with the existing piggybacking codes. We show that our piggybacking+ codes have 3% to 29% repair bandwidth reduction of the existing piggybacking codes for the evaluated high -code- rate parameters. Our main idea is that we design piggyback functions for data node repair and transformation functions for parity node repair such that the number of parity symbols which can add piggyback function or transformation function is larger than that of the existing piggybacking codes.

In this paper, we propose a new type of item in data streams, called simplex items. Simplex items have frequencies in consecutive p windows that can be approximated by a polynomial of degree at most k, where k = 0, 1, 2. These low-order representable simplex items have a wide range of potential applications. For example, when k = 1, we can leverage these items whose frequency has obvious linear increase or decrease to speed up the running time of a class of machine learning models and detect network attacks such as distributed denial-of-service (DDoS), etc. To find k-degree simplex items in real time, we propose a novel sketch, namely X-Sketch, to accurately record simplex items in a compact space. The key idea of X-Sketch is to effectively filter out non-simplex items with less memory overhead, and then monitor the remaining potential simplex items and keep those items with more consecutive windows. We conduct extensive experiments, and the experimental results show that the F1 Score of X-Sketch is on average 68.6%, 57.9%, and 42.2% higher than the baseline solution for k = 0, 1, 2, respectively. Finally, we also provide a case study that applies X-Sketch to "accelerate" the two machine learning models through end-to-end experiments. We have released our source code at GitHub.

This paper proposes the re-encoding transformed (ReT) based list decoding using the module basis reduction (BR) interpolation for algebraic geometric (AG) codes on Cabcurves. The two ReT approaches are introduced to facilitate the BR interpolation. One is realized by the bivariate Lagrange polynomial. The other is conducted by the ReT of Reed-Solomon (RS) codes based on the mathematical structure of AG codes. The ReT based BR interpolation (ReT-BR) algorithm for decoding the AG codes is further introduced. Finally, complexity of the proposed algorithm is analyzed and validated by the simulation results, demonstrating its complexity advantage over the non-ReT counterpart.

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

The recently proposed learned indexes have attracted much attention as they can adapt to the actual data and query distributions to attain better search efficiency. Based on this technique, several existing works build up indexes for multi-dimensional data and achieve improved query performance. A common paradigm of these works is to (i) map multi-dimensional data points to a one-dimensional space using a fixed space-filling curve (SFC) or its variant and (ii) then apply the learned indexing techniques. We notice that the first step typically uses a fixed SFC method, such as row-major order and z -order. It definitely limits the potential of learned multi-dimensional indexes to adapt variable data distributions via different query workloads. In this paper, we propose a novel idea of learning a space-filling curve that is carefully designed and actively optimized for efficient query processing. We also identify innovative offline and online optimization opportunities common to SFC-based learned indexes and offer optimal and/or heuristic solutions. Experimental results demonstrate that our proposed method, LMSFC, outperforms state-of-the-art non-learned or learned methods across three commonly used real-world datasets and diverse experimental settings.

Abundant high-rate$(n, k)$minimum storage regenerating (MSR) codes have been reported in the literature. However, most of them require contacting all the surviving nodes during a node repair process, resulting in a repair degree of$d=n-1$. In practical systems, it may not always be feasible to connect and download data from all surviving nodes, as some nodes may be unavailable. Therefore, there is a need for MSR code constructions with a repair degree of$d < n-1$. Up to now, only a few$(n, k)$MSR code constructions with repair degree$d < n-1$have been reported, some have a large sub-packetization level, a large finite field, or restrictions on the repair degree$d$. In this paper, we propose a new$(n, k)$MSR code construction that works for any repair degree$d>k$, and has a smaller sub-packetization level or finite field than some existing constructions. Additionally, in conjunction with a previous generic transformation to reduce the sub-packetization level, we obtain an MDS array code with a small sub-packetization level and$(1+\epsilon)$-optimal repair bandwidth (i.e.,$(1+\epsilon)$times the optimal repair bandwidth) for repair degree$d=n-1$. This code outperforms some existing ones in terms of either the sub-packetization level or the field size.

Partial maximum distance separable (PMDS) codes are a kind of erasure codes where the nodes are divided into multiple groups with each forming an MDS code with a smaller code length, thus they allow repairing a failed node with only a few helper nodes and can correct all erasure patterns that are information-theoretically correctable. However, the repair of a failed node of PMDS codes still requires a large amount of communication if the group size is large. Recently, PMDS array codes with each local code being an MSR code were introduced to reduce the repair bandwidth further. However, they require extensive rebuilding access and unavoidably a significant sub-packetization level. In this paper, we first propose two constructions of PMDS array codes with two global parities that have smaller sub-packetization levels and much smaller finite fields than the existing one. One construction can support an arbitrary number of local parities and has$(1+\epsilon)$-optimal repair bandwidth (i.e.,$(1+\epsilon)$times the optimal repair bandwidth), while the other one is limited to two local parities but has significantly smaller rebuilding access and its sub-packetization level is only 2. In addition, we present a construction of PMDS array code with three global parities, which has a smaller sub-packetization level as well as$(1+\epsilon)$-optimal repair bandwidth, the required finite field is significantly smaller than existing ones.

Many network applications can be formulated as NP-hard combinatorial optimization problems of community detection (CD) that partitions nodes of a graph into several groups with dense linkage. Most existing CD methods are transductive , which independently optimized their models for each single graph, and can only ensure either high quality or efficiency of CD by respectively using advanced machine learning techniques or fast heuristic approximation. In this study, we consider the CD task and aims to alleviate its NP-hard challenge. Motivated by the efficient inductive inference of graph neural networks (GNNs), we explore the possibility to achieve a better tradeoff between the quality and efficiency of CD via an inductive embedding scheme across multiple graphs of a system and propose a novel inductive community detection (ICD) method. Concretely, ICD first conducts the offline training of an adversarial dual GNN structure on historical graphs to capture key properties of a system. The trained model is then directly generalized to new graphs of the same system for online CD without additional optimization, where a better tradeoff between quality and efficiency can be achieved. Compared with existing inductive approaches, we develop a novel feature extraction module based on graph coarsening, which can efficiently extract informative feature inputs for GNNs. Moreover, our original designs of adversarial dual GNN and clustering regularization loss further enable ICD to capture permutation-invariant community labels in the offline training and help derive community-preserved embedding to support the high-quality online CD. Experiments on a set of benchmarks demonstrate that ICD can achieve a significant tradeoff between quality and efficiency over various baselines.

Temporal link prediction (TLP) is an inference task on dynamic graphs that predicts future topology using historical graph snapshots. Existing TLP methods are usually designed for unweighted graphs with fixed node sets. Some of them cannot be generalized to the prediction of weighted graphs with non-fixed node sets. Although several methods can still be used to predict weighted graphs, they can only derivelow-qualityprediction snapshots sensitive to large edge weights but fail to distinguish small and zero weights in adjacency matrices. In this study, we consider the challenginghigh-qualityTLP on weighted dynamic graphs and propose a novel inductive dynamic embedding aggregation (IDEA) method, inspired by the high-resolution video prediction. IDEA combines conventional error minimization objectives with a scale difference minimization objective, which can generatehigh-qualityweighted prediction snapshots, distinguishing differences among large, small, and zero weights in adjacency matrices. Since IDEA adopts an inductive dynamic embedding scheme with an attentive node aligning unit and adaptive embedding aggregation module, it can also tackle the TLP on weighted graphs even with non-fixed node sets. Experiments on datasets of various scenarios validate that IDEA can derivehigh-qualityprediction results for weighted dynamic graphs and tackle the variation of node sets.

Training a large DNN (e.g., GPT3) efficiently on commodity clouds is challenging even with the latest 3D parallel training systems (e.g., Megatron v3.0). In particular, along the pipeline parallelism dimension, computational tasks that produce a whole DNN's gradients with multiple input batches should be concurrently activated; along the data parallelism dimension, a set of heavy-weight communications (for aggregating the accumulated outputs of computational tasks) isinevitably serializedafter the pipelined tasks, undermining the training performance (e.g., in Megatron, data parallelism caused all GPUs idle for over 44% of the training time) over commodity cloud networks. To deserialize these communicational and computational tasks, we propose the AIAO scheduling (for 3D parallelism) which slices a DNN into multiple segments, so that the computational tasks processing the same DNN segment can be scheduled together, and the communicational tasks that synchronize this segment can be launched and overlapped (deserialized) with other segments’ computational tasks. We realized this idea in ourFold3Dtraining system. Extensive evaluation showsFold3Deliminated most of the all-GPU 44% idle time in Megatron (caused by data parallelism), leading to 25.2%–42.1% training throughput improvement compared to four notable baselines over various settings;Fold3D's high performance scaled to many GPUs.

Large-scale high code-rate maximum distance separable (MDS) codes are critical and important in distributed storage systems that can provide high fault tolerance with extremely small storage redundancy. Repair access (defined as the total amount of symbols accessed in repairing one single-node failure) is a key metric of designing MDS codes. In large-scale MDS codes, one single-node failure can be recovered by connecting a large number of helper nodes. However, one or more helper nodes may be busy and can not send symbols during the repair process. In this paper, we define the total amount of symbols accessed in repairing one single-node failure with one or more busy nodes as the repair access with busy-node. We then propose a class of MDS array codes over a well-designed binary cyclic ring that is with small sub-packetization, small repair access, small repair access with busy-node, and small encoding complexity.

Partial maximum distance separable (PMDS) codes are a kind of erasure codes where the storage nodes are divided into multiple groups with each forming an MDS code of a smaller code length. They allow repairing a failed node by contacting only a few helper nodes and can correct all erasure patterns which are information-theoretically correctable. However, the repair of a failed node of PMDS codes still requires a large amount of communication if the group size is large. Recently, PMDS array codes with each local code being an MSR code were introduced to further reduce the repair bandwidth, but codes over small finite fields only exist for two global parities, and require large rebuilding access and unavoidably a large sub-packetization level. In this paper, we propose two constructions of PMDS array codes with two and three global parities, respectively. Both have a small sub-packetization level, small repair bandwidth, and much smaller finite fields than existing ones.

In this paper, we propose a method of checking data integrity in distributed storage systems. Compare with conventionally used cyclic redundancy check (CRC) method, the proposed method may usually achieve a 99% reduction of bandwidth with the expense of losing only a little detection capacity. We also provide an analysis of performance and a suggestion of auxiliary matrix used in the proposed framework. Besides, a theoretical upper bound of CRC method’s detection capacity is given.

With the trend of processing a large volume of sensitive data on PaaS services (e.g., DNN training), a TEE architecture that supports general heterogeneous accelerators, enables spatial sharing on one accelerator, and enforces strong isolation across accelerators is highly desirable. However, none of the existing TEE solutions meet all three requirements. In this paper, we propose CRONUS, the first TEE architecture that achieves the three crucial requirements. The key idea of CRONUS is to partition heterogeneous computation into isolated TEE enclaves, where each enclave encapsulates only one kind of computation (e.g., GPU computation), and multiple enclaves can spatially share an accelerator. Then, CRONUS constructs heterogeneous computing using remote procedure calls (RPCs) among enclaves. With CRONUS, each accelerator’s hardware and its software stack are strongly isolated from others’, and each enclave trusts only its own hardware. To tackle the security challenge caused by inter-enclave interactions, we design a new streaming remote procedure call abstraction to enable secure RPCs with high performance. CRONUS is software-based, making it general to diverse accelerators. We implemented CRONUS on ARM TrustZone. Evaluation on diverse workloads with CPUs, GPUs and NPUs shows that, CRONUS achieves less than 7.1% extra computation time compared to native (unprotected) executions.

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

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

The Bloom filter, answering whether an item is in a set, has achieved great success in various fields, including networking, databases, and bioinformatics. However, the Bloom filter has two main shortcomings: no support of item deletion and no support of expansion. Existing solutions either support deletion at the cost of using additional memory, or support expansion at the cost of increasing the false positive rate and decreasing the query speed. Unlike existing solutions, we propose the Elastic Bloom filter (EBF) to address the two shortcomings simultaneously. Importantly, when EBF expands, the false positives decrease. Our key technique isElastic Fingerprints, which dynamically absorb and release bits during compression and expansion. To support deletion, EBF can first delete the corresponding fingerprint and then update the corresponding bit in the Bloom filter. To support expansion, Elastic Fingerprints release bits and insert them to the Bloom filter. Our experimental results show that the Elastic Bloom filter significantly outperforms existing works.

The increasing computational complexity of DNNs achieved unprecedented successes in various areas such as machine vision and natural language processing (NLP), e.g., the recent advanced Transformer has billions of parameters. However, as large-scale DNNs significantly exceed GPU's physical memory limit, they cannot be trained by conventional methods such as data parallelism. Pipeline parallelism that partitions a large DNN into small subnets and trains them on different GPUs is a plausible solution. Unfortunately, the layer partitioning and memory management in existing pipeline parallel systems are fixed during training, making them easily impeded by out-of-memory errors and the GPU under-utilization. These drawbacks amplify when performing neural architecture search (NAS) such as the evolved Transformer, where different network architectures of Transformer needed to be trained repeatedly. vPipe is the first system that transparently provides dynamic layer partitioning and memory management for pipeline parallelism. vPipe has two unique contributions, including (1) an online algorithm for searching a near-optimal layer partitioning and memory management plan, and (2) a live layer migration protocol for re-balancing the layer distribution across a training pipeline. vPipe improved the training throughput of two notable baselines (Pipedream and GPipe) by 61.4-463.4 percent and 24.8-291.3 percent on various large DNNs and training settings.

Information freshness, which is characterized by a new performance metric called age of information (AoI), significantly influences decision making in numerous applications. In wireless sensor networks, unmanned aerial vehicle (UAV) has been widely adopted for fresh data collection. The key to applying UAV lies in UAV trajectory planning. Considering several fixed waypoints in UAV trajectory, the trajectory planning is an NP-hard combinatorial optimization problem, and is difficult to solve in practice. To well balance between the accuracy and efficiency, we propose an end-to-end AI-based framework in this paper to deal with the UAV trajectory planning within two stages. First, the hover positions of UAV and data transmission time are decided using a clustering module. Then, the AoI-minimal flight path is obtained through a neural trajectory solver. Compared with classic heuristic algorithms, the proposed AI-based framework achieves a smaller AoI with two orders of magnitude lower computational time. Besides, the proposed AI-based framework can be easily generalized to larger-scale scenarios (e.g., up to 2,000 sensor nodes) which cannot be solved by exact algorithms (e.g., dynamic programming) in a limited time. Moreover, the AI-based framework is comparable in accuracy with the commercial open-source solver Google OR-tools, but the efficiency is increased by 200%.

A distributed database utilizing the wide-spread edge computing servers to provide low-latency data access with the serializability guarantee is highly desirable for emerging edge computing applications. In an edge database, nodes are divided into regions, and a transaction can be categorized as intra-region (IRT) or cross-region (CRT) based on whether it accesses data in different regions. In addition to serializability, we insist that a practical edge database should provide low tail latency for both IRTs and CRTs, and such low latency must be scalable to a large number of regions. Unfortunately, none of existing geo-replicated serializable databases or edge databases can meet such requirements.

Despite that cloud virtual reality (VR) is the most promising service in 5G networks, a reasonable traffic model for it is still unknown. Based on statistics of real cloud VR traces, we justify that the Markovian arrival process (MAP) can well characterize the inter-arrival times (IATs) among packets. Moreover, we discuss possible methods to efficiently estimate parameters for flow aggregation. Since MAPs are analytically tractable, we quantify the performance of delivering cloud VR traffic from a queueing theory perspective. Aiming at supporting quantile metrics, we provide distributions of queue-length and latency for an arbitrary packet. The accuracy of estimated latency is validated by comparing with measured latency on an industrial 5G platform. The MAP-based traffic model will potentially serve as an input for performance evaluation and network planning for assuring high requirements of user experience.

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

Piggybacking is a class of coding framework for MDS array codes that can achieve small repair bandwidth with small sub-packetization. An ($n, k, \alpha$) piggybacking code can be represented by an$n\times \alpha$array such that each node (row) stores$\alpha$symbols and any$k$rows can retrieve all$k\alpha$data symbols. In this paper, we first propose a new piggybacking framework for MDS array codes with lower sub-packetization and then propose two specific piggybacking codes based on the proposed framework. We show that the average repair bandwidth of any single-node failure of our piggybacking codes is lower than all the existing piggybacking codes with the same parameters when the sub-packetization is small (usually$\alpha\leq 8$) and$n-k\geq 10$.

In this paper, we consider two rack-aware storage systems. First, large-scale rack-aware storage system, which is very common in large-scale storage system, is a rack-aware storage system where all sizes of racks are at least the number of redundant nodes. For such storage system, we prove that any Maximum Distance Separable (MDS) codes can have optimal inter-rack repair bandwidth and give a closed-form representation of all repair schemes with optimal inter-rack repair bandwidth. Furthermore, we show that the optimal repair access and optimal inter-rack repair bandwidth can be attained simultaneously for such storage system. Second, we investigate the rack-aware storage system of all racks with the same size, which is called uniform rack-aware storage system. We prove that, except the trivial cases, we cannot attain optimal inter-rack repair bandwidth and optimal repair access for such storage system at the same time. Specifically, we establish the lower bound of repair access for a repair scheme with optimal interrack repair bandwidth, which is tight for some parameters, and also the tight lower bound of inter-rack repair bandwidth for a repair scheme with optimal repair access.

Regenerating codes are designed to reduce the repair bandwidth (access bandwidth) for rebuilding a fail node in an erasure-coded storage system. In practical systems, the fail node is not rebuilt immediately. Before its rebuilding, the data originally stored in the failed node might be accessed by the system. Hence, accessing the data in the failed disk (degraded read) with low latency is crucial for any practical storage system. In this work, to solve this problem, a new class of the regenerating codes based on the maximum distance separable (MDS) array codes is defined, named the MDS array code with the property of degraded read friendly (DRF). For the DRF MDS array codes with 2 redundant nodes and the sub-packetization level of 2, the lower bound of their access bandwidth is derived. A class of the DRF MDS array codes that achieves the derived bound is given to solidify the achievability of the proposed lower bound.

Predicting block popularity is of crucial importance for data placement in multi-tiered multimedia storage systems. Traditional methods, such as least recently used and exponential smoothing, are commonly employed to predict future block access frequencies and fail to achieve good performance for complex and changing access patterns. Recently, deep neural networks have brought great success to pattern recognition and prediction, which motivates us to introduce deep learning to solve the problem of block popularity prediction. In this paper, we first analyze and verify the temporal and spatial correlations among the multimedia I/O traces. Then, we design a multi-dimension feature to capture such correlations, which serves as the input of the designed deep neural network. A spatial-temporal-sequential neural network (STSNN) and its variants that capture the locality information, time dependency information, and block sequential information are proposed to predict the block popularity. We systematically evaluate our STSNN models against six baseline models from three different categories, i.e., heuristic methods, regression methods and neural network-based methods. Experiment results show that our proposed STSNN models are very promising for predicting block access frequencies under some of Huawei and Microsoft datasets and particularly achieve 2-6 times better performance compared with the baselines in terms of the I/O hit ratio, I/O recall rate and I/O prediction ratio under the Microsoft 64 MB-block dataset.

A permissioned blockchain framework typically runs an efficient Byzantine consensus protocol and is attractive to deploy fast trading applications among a large number of mutually untrusted participants (e.g., companies). Unfortunately, all existing permissioned blockchain frameworks adopt sequential workflows for invoking the consensus protocol and executing applications' transactions, making the performance of these applications much lower than deploying them in traditional systems (e.g., in-datacenter stock exchange).

Data-driven approaches have recently emerged as promising remedies for communication system designs, which leverage deep learning techniques for automated development and optimization. In this paper, we revisit the designs of multi-input multi-output (MIMO) wireless systems and investigate the end-to-end learning for MIMO systems with temporal correlations. Our objective is to develop a MIMO transceiver to improve the communication performance by making fully use of the available temporal information. Although the end-to-end learning framework has been applied to various communication systems, existing designs largely rely on memoryless autoencoders (AEs) and overlook the time dependency. To overcome this issue, we propose a novel learning-based MIMO transceiver, namely, the TC-MIMONet, which extends the conventional memoryless AE-based transceivers by customizing two neural network components with memory. In particular, a long short-term memory (LSTM)-based CSI predictor is adopted at the transmitter, while a two-timescale LSTM-based decoder is developed for the receiver. Simulation results show that TC-MIMONet achieves significant block error rate reduction compared to two baseline schemes without utilizing the available temporal information.

Advanced network management systems, including network measurement and traffic control, rely on a remote controller to make control decisions. However, this approach incurs a long control loop of a few seconds to minutes. Even if we switch to switch-local controller, the latency is still tens of milliseconds and is unacceptable for many latency-sensitive tasks. In this paper, we propose Martini, a general framework that supports measurement-based timely control. The key idea is to perform measurement, control decision, and control entirely in the switch data plane. This could shorten the control loop of management tasks that require timely control based on only locally measured statistics in the switch. First, Martini introduces a set of primitives to describe management tasks. Next, Martini provides an innovative network-wide task placement mechanism to exploit resources of all switches to accommodate massive management tasks. Finally, Martini provides a code library and a compiler to support measurement and control on a state-of-the-art switching ASIC. Evaluation results show that Martini can effectively support a wide range of fine-timescale management tasks such as microburst detection and fast load balancing by reducing the control loop from seconds to nanoseconds.

In this paper, we consider a MIMO cyber physical system (CPS) in which a sensor amplifies and forwards the observed MIMO plant state to a remote controller via a MIMO fading channel. We focus on the MIMO amplify-and-forward (AF) precoding design at the sensor to minimize a weighted average state estimation error at the remote controller subject to an average communication power gain constraint of the sensor. The MIMO AF precoding design is formulated as an infinite horizon average cost Markov decision process (MDP). To deal with the curse of dimensionality associated with the MDP, we propose a novel continuous-time perturbation approach and derive an asymptotically optimal closed-form priority function for the MDP. Based on this, we derive a closed-form first-order optimal dynamic MIMO AF precoding solution, and the solution has an event-driven control structure. Specifically, the sensor activates the strongest eigenchannel to deliver a dynamically weighted combination of the plant states to the controller when the accumulated state estimation error exceeds a dynamic threshold. We further establish technical conditions for ensuring the stability of the MIMO CPS.

This paper concerns practical issues of sparse regression codes (SRCs) with approximate message passing (AMP) decoding. First, Gaussian signaling of SRC incurs a high peak-to-average-power ratio (PAPR) problem. Second, the finite length performance of SRCs is poor at low-to-medium rates and cannot be improved by spatial coupling or power allocation. We confront the two challenges by introducing clipping to SRC. For the encoder, clipping is applied to the Gaussian codeword of SRC for reducing the high PAPR. For the decoder, generalized approximate message passing (GAMP) is used to handle the nonlinear clipping distortion. Interestingly, we observe that clipping with proper thresholds can improve the performance of SRC and the performance gain is large at low rates. Based on the state evolution analysis of GAMP decoding, we provide an explanation for such observation from the curve-matching perspective. In the end, some guidelines are provided for choosing proper clipping thresholds empirically.

Finding top-k items in data streams is a fundamental problem in data mining. Existing algorithms that can achieve unbiased estimation suffer from poor accuracy. In this paper, we propose a new sketch, WavingSketch, which is much more accurate than existing unbiased algorithms. WavingSketch is generic, and we show how it can be applied to four applications: finding top-k frequent items, finding top-k heavy changes, finding top-k persistent items, and finding top-k Super-Spreaders. We theoretically prove that WavingSketch can provide unbiased estimation, and then give an error bound of our algorithm. Our experimental results show that, compared with the state-of-the-art, WavingSketch has 4.50 times higher insertion speed and up to 9 x 106 times (2 x 104 times in average) lower error rate in finding frequent items when memory size is tight. For other applications, WavingSketch can also achieve up to 286 times lower error rate. All related codes are open-sourced and available at Github anonymously.

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.

Approximate stream processing has attracted much attention recently. Prior art mostly focuses on characteristics like frequency, cardinality, and quantile. Persistence, as a new characteristic, is getting increasing attention. Unlike frequency, persistence highlights behaviors where an item appears recurrently in many time windows of a data stream. There are two typical problems with persistence - persistence estimation and finding persistent items. In this paper, we propose the On-Off sketch to address both problems. For persistence estimation, using the characteristic that the persistence of an item is increased periodically, we compress increments when multiple items are mapped to the same counter, which significantly reduces the error. Compared with the Count-Min sketch, 1) in theory, we prove that the error of the On-Off sketch is always smaller; 2) in experiments, the On-Off sketch achieves around 6.17 times smaller error and 2.2 times higher throughput. For finding persistent items, we propose a technique to separate persistent and non-persistent items, further improving the accuracy. We show that the space complexity of our On-Off sketch is much better than the state-of-the-art (PIE), and it reduces the error up to 4 orders of magnitude and achieves 2.84 times higher throughput than prior algorithms in experiments.

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.

In data center networks, flows with different objectives coexist and compete for limited resources. From the application-level perspective, it is hard to satisfy the demands of different flows without effective resource planning. To address the bandwidth allocation problem under multi-objective scenarios, we study a multi-objective network utility maximization (NUM) problem and propose our practical bandwidth allocation framework HOMMO, which consists of an upper layer algorithm (ULA) and a lower layer algorithm (LLA). This hierarchical design helps to strike a balance between accuracy and efficiency. Implemented in network switches, ULA is an online learning-based scheme that allocates bandwidth for aggregated flows with different performances objectives. Taking the outputs from ULA as capacity constraints, LLA acts as a fast scheduling method at packet-level. We extend NUMFabric by implementing the design of isolate queues and corresponding dequeue strategy in switches and make it a feasible solution of the LLA. Therefore, HOMMO achieves satisfactory isolation across flows with different objectives, which is equivalent to provide a network slicing solution. To evaluate the proposed framework, we implement it in ns-3 and verify the performance under various scenarios. The simulation results show that HOMMO not only quickly converges to a near-optimal solution of the multi-objective NUM problem but also guarantees a Pareto-optimal solution. Moreover, it outperforms the well-known transport protocol (i.e., DCTCP) with 2x increase on average bandwidth utilization and 1.96x improvement in global network utility at the aggregated flow level.

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

High topology dynamics and intermittent connectivity in Vehicular Ad hoc Network (VANET) bring huge challenges to end-to-end communication. Existing routing protocols for MANET such as AODV and OLSR work fine under modest mobility, but have a difficult time to handle frequent topology changes in VANET. This paper proposes Peeking at the Past and Present Routing (P3R), a routing protocol that will calculate next-hops when the past forwarding is considered invalid. The next-hop calculation is based on the predicted locations of forwarder's neighbors and the packet's destination node, overcoming the inaccuracy caused by stale location information. Furthermore, we differentiate vehicles on crossroads as they have high connectivity in actual urban streets. In this way, P3R is able to deal with link breakages quickly and exploit new links. Simulation results show that P3R outperforms state-of-the-art alternatives in terms of packet delivery ratio, delay and cost, while maintaining strong scalability and robustness. We also implement P3R in a real vehicular testbed and the results reveal it has high connectivity on real streets.

In this paper, we generally formulate the dynamics prediction problem of various network systems (e.g., the prediction of mobility, traffic and topology) as the temporal link prediction task. Different from conventional techniques of temporal link prediction that ignore the potential non-linear characteristics and the informative link weights in the dynamic network, we introduce a novel non-linear model GCN-GAN to tackle the challenging temporal link prediction task of weighted dynamic networks. The proposed model leverages the benefits of the graph convolutional network (GCN), long short-term memory (LSTM) as well as the generative adversarial network (GAN). Thus, the dynamics, topology structure and evolutionary patterns of weighted dynamic networks can be fully exploited to improve the temporal link prediction performance. Concretely, we first utilize GCN to explore the local topological characteristics of each single snapshot and then employ LSTM to characterize the evolving features of the dynamic networks. Moreover, GAN is used to enhance the ability of the model to generate the next weighted network snapshot, which can effectively tackle the sparsity and the wide-value-range problem of edge weights in real-life dynamic networks. To verify the model's effectiveness, we conduct extensive experiments on four datasets of different network systems and application scenarios. The experimental results demonstrate that our model achieves impressive results compared to the state-of-the-art competitors.

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.

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

Fog radio access network (Fog-RAN), which pushes caching and computing capabilities to the network edge, is capable of efficiently delivering content to users by using carefully designed caching placement and content replacement algorithms. In this paper, the transmission scheme design and coding parameter optimization will be considered for coded caching in FogRAN, where the reliability of content delivery, i.e., content outage probability, is used as the performance metric. The problem will be formulated as a complicated multi-objective probabilistic combinatorial optimization. A novel maximum b-matching approach will then be proposed to obtain the Pareto optimal solution with fairness constraint. Based on the fast message passing approach, a distributed algorithm with a low memory usage of O(M + N) is also proposed, where M is the number of users and N is the number of fog access points (Fog-APs). Although it is usually very difficult to derive the closed-form formulas for the optimal solution, the approximation formulas of the content outage probability will also be obtained as a function of coding parameters. The asymptotic optimal coding parameters can then be obtained by defining and deriving the outage exponent region and diversity-multiplexing region. Simulation results will illustrate the accuracy of the theoretical derivations, and verify the outage performance of the proposed approach. Therefore, this paper not only proposes a practical distributed Fog-AP selection algorithm for coded caching but also provides a systematic way to evaluate and optimize the performance of Fog-RANs.

The network link speed is growing at an ever-increasing rate, which requires all network functions on routers/switches to keep pace. Bloom filter is a widely-used membership check data structure in networking applications. Correspondingly, it also faces the urgent demand of improving the performance in membership check speed. To this end, this paper proposes a new Bloom filter variant called Ultra-Fast Bloom Filters (UFBF), by leveraging the Single Instruction Multiple Data (SIMD) techniques. We make three improvements for UFBF to accelerate the membership check speed. First, we develop a novel hash computation algorithm which can compute multiple hash functions in parallel with the use of SIMD instructions. Second, we elaborate a Bloom filter's bit-test process from sequential to parallel, enabling more bit-tests per unit time. Third, we improve the cache efficiency of membership check by encoding an element's information to a small block so that it can fit into a cache-line. We further generalize UFBF, called c-UFBF, to make UFBF supporting large number of hash functions. Both theoretical analysis and extensive evaluations show that the UFBF greatly outperforms the state-of-the-art Bloom filter variants on membership check speed.

Though the classical packet-level queueing theory, which treats each packet as an entry, has achieved a great success in network analysis, it can be inaccurate when directly applied to long-term evolution (LTE) networks. This is because arriving packets could be broken down at the LTE base station server across adjacent transmission time intervals (TTIs), which are the smallest scheduling time units in LTE networks. In this paper, we first propose an innovative bit-level queueing theory to address the challenges in performance analysis of LTE networks. To consider the randomness in packet arrivals and packet lengths, we propose two representative compound network traffic models-Poisson-Exponential (PE) and Zeta-Pareto (ZP) models-to approximate light-tailed and heavy-tailed network traffic, respectively. PE models are suitable for conventional voice and low-speed services, while ZP models, which compound power-law distributions, describe complicated high-speed network applications. We derive tail asymptotics for the distributions of the number of bit arrivals in one TTI and the corresponding waiting time. Based on the results in bit-level queueing theory, we present engineering applications that take into account user experience, including estimating the user experience rate (UER), the busy UER and hourly traffic volume. The theoretical results are then validated through extensive simulations. Our novel traffic estimation approach has been adopted by Wireless Product Line at Huawei for network capacity planning and also projected to International Telecommunication Union (ITU) to compose 5G standards.

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.

Fog Computing which extends the cloud computing paradigm to the edge of the network provides great opportunities for applications with stringent latency requirement. How to allocate the limited caching resources of Fog Nodes (FNs)influences the performance of the fog computing system. In contrast to previous works on caching resource allocation with users' utility as the only consideration, we propose OptCaching which jointly optimize the utility of all network participants including Content Provider (CP), Internet Service Provider (ISP)and users. With caching incentive introduced, utility functions of these three roles are defined. Our joint utility optimization caching scheme is conducted in two stages combining global and local decision making. Firstly, interaction between CP and ISP is modeled as a non-cooperative hierarchy Stackelberg game to make decision on incentive caching prices and global caching amount aiming at optimizing the utility of all network participants. Secondly, for the purpose of further optimizing the utility of users, a belief propagation based cache placement algorithm which utilizes global caching amount constraint and local information is conducted by FNs to reduce users' average download delay. Mathematical analysis and simulation results show that the utility of CP, ISP and users are jointly optimized at Stackelberg equilibrium. The utility of users is further optimized by belief propagation based cache placement algorithm with users' average download delay reduced by 33.7% compared with global popularity based caching strategy.

Today's cloud networks are shared among many tenants. Bandwidth guarantees and work conservation are two key properties to ensure predictable performance for tenant applications and high network utilization for providers. Despite significant efforts, very little prior work can really achieve both properties simultaneously even some of them claimed so. In this paper, we present QShare, a comprehensive in-network solution to achieve bandwidth guarantees and work conservation simultaneously. QShare leverages weighted fair queuing on commodity switches to slice network bandwidth for tenants, and solves the challenge of queue scarcity through balanced tenant placement and dynamic tenant-queue binding. We have implemented a QShare prototype and evaluated it extensively via both testbed experiments and simulations. Our results show that QShare ensures bandwidth guarantees while driving network utilization to over 91% even under unpredictable traffic demands.

A data-centric network architecture, Named Data Networking (NDN) has been developed to meet applications' growing demands of network effciency and resilience. Currently, the deployment of NDN in real network environments requires careful system design to not only enable NDN but also support IP traffc, considering IP network has been prevalent for decades and almost all the equipments and applications are IP-based. In this paper, we take the most popular local area network (LAN) technology, Ethernet, as an example to investigate incremental deployment of NDN. Assuming a local network with both NDN and IP traffc, we mainly layout three deployment scenarios: NDN-enabled hosts and all Ethernet switches, NDN-enabled hosts and all Dual-Stack switches (i.e., it can process both NDN and IP traffc), and a hybrid network with both Dual-Stack switches and Ethernet switches. We examine the technical issues involved in each scenario and present solutions. In particular, in the hybrid scenario, we propose heuristics to optimize the placement of Dual-Stack switches. Compared with traditional Ethernet, introducing Dual-Stack switches can improve network effciency and resiliency by utilizing more links, reducing each link's traffc load, and taking shorter paths, at the same time also maintaining the functionality of IP-based applications.

The current inter-domain routing protocol, namely, the Border Gateway Protocol (BGP), cannot provide end-to-end (E2E) quality-of-service (QoS) guarantees. The main reason is that an autonomous system (AS) can only receive guarantees from its first hop ASes via service level agreements (SLAs). But beyond the first hop, QoS along the path from source to destination AS is not within the source AS's control regime. In this paper, we investigate the feasibility of providing high QoS-guaranteed E2E transit services by utilizing a (small) set of ASes/IXPs to serve as "brokers" to provide supervision, control and resource negotiation. Finding an optimal set of ASes as brokers can be formulated as a Maximum Coverage with B-dominating path Guarantee (MCBG) problem, which we prove to be NP-hard. To address this problem, we design a (1-e-1/4)-approximation algorithm and also an efficient heuristic algorithm when considering additional constraints (e.g., path length). Based on the current Internet topology, we discover a "3540-alliance" subset (accounting only 6.8%) of 52,079 ASes/IXPs, which can provide high QoS guarantees for 99.29% E2E connections.

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.

The network link speed is increasing at an alarming rate, which requires all network functions on routers/switches to keep pace. Bloom filter is a widely-used membership check data structure in network applications. It also faces the urgent demand of improving the performance in membership check speed. To this end, this paper proposes a new Bloom filter variant called Ultra-Fast Bloom Filters, by leveraging the SIMD techniques. We make three improvements for the UFBF to accelerate the membership check speed. First, we develop a novel hash computation algorithm which can compute multiple hash functions in parallel with the use of SIMD instructions. Second, we change a Bloom filter's bit-test process from sequential to parallel. Third, we increase the cache efficiency of membership check by encoding an element's information to a small block which can easily fit into a cache-line. Both theoretical analysis and extensive simulations show that the UFBF greatly exceeds the state-of-the-art Bloom filter variants on membership check speed.

Network measurement remains a missing piece in today's software packet processing platforms. Sketches provide a promising building block for filling this void by monitoring every packet with fixed-size memory and bounded errors. However, our analysis shows that existing sketch-based measurement solutions suffer from severe performance drops under high traffic load. Although sketches are efficiently designed, applying them in network measurement inevitably incurs heavy computational overhead.

Application Driven Network(ADN) is a new paradigm that provides on-demand differentiated services for applications. A physical network in ADN is sliced into various logically isolated sub-networks. Each network slice can have its own network architecture and protocol to serve one application exclusively. ADN enhances the user experience while keeping the resource efficiency by further imposing multiplexing among these logically isolated sub-networks.

3G technology has stimulated a wide variety of high-bandwidth applications on smartphones, such as video streaming and content-rich web browsing. Although having those applications mobile is quite appealing, high data rate transmission also poses huge demand for power. It has been revealed that the tail effect in 3G radio operation results in significant energy drain on smartphones. Recent fast dormancy technique can be utilized to remove tails but, without care, can degrade user experience. In this paper, we propose a novel scheme SmartCut, which effectively mitigates the tail effect of radio usage in 3G networks with little side-effect on user experience. The core idea of SmartCut is to utilize the temporal correlation of packet arrivals to predict upcoming packets, based on which unnecessary high-power-state tails of radio are cut out leveraging the Fast Dormancy mechanism. Both prototype experiment and extensive trace-driven simulation results demonstrate the efficacy of SmartCut design. On average, SmartCut can save up to 43 percent network energy while having little side-effect to user experience.

3G technology has stimulated a wide variety of high-bandwidth applications on smartphones, such as video streaming and content-rich web browsing. Although having those applications mobile is quite appealing, high data rate transmission also poses huge demand for power. It has been revealed that the tail effect in 3G radio operation results in significant energy drain on smartphones. Recent fast dormancy technique can be utilized to remove tails but, without care, can degrades user experience. In this paper, we propose a novel scheme SmartCut, which effectively mitigates the tail effect of radio usage in 3G networks with little side-effect on user experience. The core idea of SmartCut is to utilize the temporal correlation of packet arrivals to predict upcoming data, based on which unnecessary high-power-state tails of radio are cut out leveraging the Fast Dormancy mechanism. Extensive trace-driven simulation results demonstrate the efficacy of SmartCut design. On average, SmartCut can save up to 56.57% energy on average while having little side-effect to user experience.