Push-In First-Out (PIFO) offers a unified abstraction for rapidly deploying diverse scheduling algorithms on the same hardware. As SerDes-lane aggregation pushes port rates to 1.6 Tbps, the perpacket processing budget is at a sub-nanosecond scale, making single-queue PIFO designs fail to keep up. Mirroring lane aggregation, we advocate interleaving multiple PIFO queues. However, simple round-robin parallelization introduces substantial scheduling error, and in the worst case, it can grow to the order of the buffer size.

AI training and inference are driving cloud networks toward terabit-per-second (Tbps) bandwidth per server, challenging the scalability and efficiency of today's cloud network architectures. A prevalent design scales bandwidth by stacking monolithic Data Processing Units (DPUs), but this approach tightly couples control and data plane resources, leading to excessive cost, power consumption, and operational complexity. We identify a fundamental control-data plane divergence in AI clouds: while data plane bandwidth demand grows rapidly, control plane demand remains largely flat due to the dominance of elephant flows. As a result, monolithic DPUs become systematically over-provisioned when used as bandwidth scaling primitives.

Packet schedulers are essential for managing packet transmission order in high-speed networks, where scheduling metadata must be processed at line rate under bursty traffic conditions. In such systems, packet scheduling and traffic management operate on compact packet descriptors rather than on full packets. FIFO-based schedulers are attractive for their simplicity and throughput, but implementations that statically partition descriptor memory across queues must provision for worst-case occupancy, leading to inefficient memory utilization. This paper presents MetaFlex, a scalable architecture for efficient implementation of calendar-queue–based packet scheduling using shared descriptor memory. MetaFlex dynamically allocates descriptor storage to scheduling queues on demand, allowing memory to be effectively shared across a large number of rank bins while maintaining constant-time enqueue and dequeue operations. Rather than introducing a new scheduling algorithm, MetaFlex focuses on the architectural realization of shared-memory descriptor queues that scale to large queue counts with predictable timing and modest hardware cost. We evaluate MetaFlex using NS2 simulations of weighted fair scheduling and a hardware prototype implemented in VHDL on an AMD/Xilinx Alveo U250 FPGA board. Simulation results show that MetaFlex achieves comparable or lower packet loss than fixed-memory calendar queues under identical descriptor-memory budgets, while using substantially less descriptor storage under typical traffic conditions. The FPGA prototype operates at 322 MHz, sustains 100 Gb/s line rate for packets larger than 370 bytes, and uses less than 1% of logic resources and less than 5% of on-chip memory, demonstrating the practicality of MetaFlex for high-speed hardware datapaths.

The increasing volume of video traffic presents significant challenges to network transmission, while edge computing accelerates video delivery by leveraging caching and computation to optimize content forwarding. However, as edge computing is generally deployed by service providers in a transparent manner, clients cannot perceive edge states, e.g., cache availability, potentially resulting in suboptimal bitrate decisions. This issue persists even with intelligent bitrate selection approaches on the client side, as the inaccurate estimation of network delivery capacity due to edge cache transparency remains unresolved. Meanwhile, single-edge servers or nodes, with limited cache space and computational capacity for a small number of users, can be more effective by aggregating into clusters to better serve users and optimize resource utilization. Therefore, we propose an edge-assisted bitrate re-adaptation scheme (e-BitRead) for adaptive streaming, utilizing neighbor edges to accelerate video deliveries.e-BitReadintroduces three key innovations: (i) it employs a bitrate re-adaptation mechanism that intelligently selects alternative bitrates from edge servers instead of strictly responding with the requested bitrate, (ii) it utilizes collaborative caching across multiple edge servers to expand available bitrate options through coordinated resource sharing, and (iii) it enhances the learning efficiency through joint optimization of network architecture and reward design, which leverages actor-critic structure to fit into multi-edge bitrate adaptation. In experiments with an intelligent client ABR,e-BitReaddemonstrates its superiority by achieving a 1.43x higher hit ratio compared to the baseline, while improving QoE by 1.93x over the scheme without smart bitrate matching and delivering a 33% gain over the single-edge re-adaptation approach.

The increasing popularity of large models and datasets has highlighted the significance of distributed training networks. As gradient synchronization generates substantial traffic, in-network aggregation (INA) has emerged as a solution to offload aggregation onto the switch, alleviating network congestion and accelerating distributed training. However, the limited memory capacity of the INA switch becomes a potential bottleneck as computation shifts into the network, especially in multi-tenant scenarios. To address this bottleneck and enhance network throughput, we propose the Aggregation with Innetwork Resource Pooling (AIRP) framework. Unlike existing approaches that optimize individual switches in a localized manner, AIRP takes a holistic view and efficiently pools switch memory resources across the entire network, allocating them to multiple tenants. Evaluation using the ns-3 simulator and P4 testbed demonstrates that AIRP can accelerate the training of various models, including computer vision and language models. The experimental results show that AIRP outperforms existing INA approaches by up to 7 times in terms of network throughput in multi-tenant scenarios, while also achieving great flexibility and efficiency in deployment.

With the increasing popularity of distributed training applications, the growth in network traffic has become an impediment to the communication among worker nodes in the system. In-network aggregation (INA) has emerged as a solution to improve communication efficiency by offloading gradient aggregation to switches. However, in multi-tenant scenarios, INA switch memory capacity has been identified as a main bottleneck, leading to reduced network throughput and slower training processes. To address this, we propose Adaptive Gradient Quantization (AGQ) on the switch. AGQ reduces the quantization bit-width of gradients, allowing for storage of more gradients within the limited switch memory while maintaining training accuracy. Compared to quantization on hosts, AGQ can swiftly adapt to the available memory on switches and offers an improved balance between minimizing precision loss and enhancing training throughput. We implement AGQ on a P4 switch testbed, and experimental results demonstrate that enabling AGQ can achieve an up to 100% increase in training throughput without explicit drop of training accuracy compared with existing INA solutions like ATP and host-based quantization methods like THC.

Brain simulation is an inherently highly parallel and time-sensitive task, requiring the simulation of billions of neurons and their interactions within just a few milliseconds. With the growing availability of brain data from biological research, more realistic and detailed simulations are becoming feasible. However, this also poses unprecedented challenges for parallel computing due to the extreme sparsity and heterogeneity of the emerging workloads. Efficient deployment of such workloads on modern HPC systems is critical to overcoming these challenges. We propose BMapper, a deployment framework that enables efficient parallel execution of brain simulations on supercomputers. BMapper comprises three synergistic components: BPartitioning, which introduces a novel multi-dimensional hybrid partitioning strategy to balance workloads across GPUs and reduce inter-GPU spike traffic; BPlacement, which applies deterministic spectral partitioning to minimize inter-server communication; and BRelaying, which identifies lightly loaded GPUs to assist the top-k heavily loaded ones by relaying spike traffic. These components work together to balance loads and minimize communication overhead, enabling high-speed simulation of large-scale brain models. BMapper has been deployed to simulate up to 10 billion neurons on a 1000-GPU supercomputer, achieving 25.15%–47.48% faster execution than state-of-the-art methods.

Flowlet-level load balancing has not demonstrated the expected robust capability in RDMA networks due to insufficient flowlets and the adverse effects of PFC. To delve deeper, we conduct measurements at end hosts and perform a detailed analysis of time gaps between packets. Our investigation reveals that in RDMA networks, the number of time gaps exceeding the flowlet timeout is considerably lower than the number in TCP networks. We also identify a stepwise time gap pattern that predicts the occurrence of PFC. Based on these observations, we propose$\text{HF}^{2} \mathrm{T}$, a host-based time gap adjustment method to improve the effectiveness of flowlet-level load balancing in RDMA networks. The core idea involves delaying a minimal number of specific packets at the host, actively extending the time gaps between them, thereby fostering the generation of sufficient flowlets at the switch and enhancing the utilization of equal-cost links. Incorporating an identification algorithm for the time gap pattern that predicts PFC,$\text{HF}^{2} \mathrm{T}$also leverages the time gap extension to reroute traffic away from potential PFC paths in advance, thus mitigating PFC occurrences. The minor cost of delaying a few packets is vastly offset by the benefits of generating flowlets and reducing PFC. We use DPDK to implement a prototype of$\text{HF}^{2} \mathrm{T}$, and through testbed experiments, we demonstrate that$\text{HF}^{2} \mathrm{T}$, serving as a building block for flowlet load balancing, can enhance the throughput of CONGA by 16.82%. The simulation results also show that$\text{HF}^{2} \mathrm{T}$can reduce the average FCT by 16.38% and the 99-percentile FCT by 21.13% compared to the state-of-the-art RDMA load balancing ConWeave.

Congestion control algorithms (CCAs) play a critical role in determining transmission quality. With their rapid evolution during the past few decades, understanding the CCA landscape on the Internet has become increasingly essential for network advancement. Traditional CCA census tools, however, rely heavily on manual configuration and construction, necessitating significant human effort to keep pace with the introduction of new CCAs.

This paper presents ZooRoute, a tenant-transparent, fast failure recovery service that requires no modifications to physical devices. ZooRoute leverages the overlay layer and enables traffic flows to bypass failures by altering source ports (srcPorts) in packet headers during encapsulation. To enable deployment in large-scale cloud networks, ZooRoute proposes: 1) On-demand probing to efficiently monitor a vast number of hosts while minimizing telemetry costs. 2) Table compression to record the states of numerous paths with limited on-chip resources. 3) A device-sensing mechanism to prevent unnecessary reconnections in stateful forwarding. Deployed in Alibaba Cloud for 18 months, ZooRoute has significantly improved network reliability, reducing cumulative outage time by 92.71%.

Access Control Lists (ACLs) are crucial for ensuring the security and integrity of modern cloud and carrier networks by regulating access to sensitive information and resources. However, previous software and hardware implementations no longer meet the requirements of modern datacenters. The emergence of FPGA-based SmartNICs presents an opportunity to offload ACL functions from the host CPU, leading to improved network performance in datacenter applications. However, previous FPGA-based ACL designs lacked the necessary flexibility to support different rulesets without hardware reconfiguration while maintaining high performance. In this paper, we propose HACL, a heterogeneous and adaptive architecture for decision-tree-based ACL engine on FPGA. By employing techniques such as tree decomposition and recirculated pipeline scheduling, HACL can accommodate various rulesets without reconfiguring the underlying architecture. To facilitate the efficient mapping of different decision trees to memory and optimize the throughput of a ruleset, we also introduce a heterogeneous framework with a compiler in CPU platform for HACL. We implement HACL on a typical SmartNIC and evaluate its performance. The results demonstrate that HACL achieves a throughput exceeding 260 Mpps when processing 100K-scale ACL rulesets, with low hardware resource utilization. By integrating more engines, HACL can achieve even higher throughput and support larger rulesets.

As Distributed Deep Learning (DDL) gains prominence, network constraints have emerged as a critical bottleneck impacting DDL performance. While state-of-the-art loss-tolerant (LT) transmission protocols enhance DDL efficiency, their application in federated learning (FL) environments is hindered by several challenges: (1) LT protocols necessitate client-side modifications, impractical in FL settings; (2) maintaining LT protocol transparency to senders compromises congestion control integrity; (3) LT protocols disrupt stream cipher, which is widely utilized in FL. To address these hurdles, this paper introduces UniFL, an innovative LT protocol tailored for FL applications. UniFL seamlessly integrates with FL architectures by preserving congestion control via a specialized speed limiter and adopting an advanced encryption technique that withstands packet loss, ensuring data integrity. UniFL is implemented within the NS3 for simulation evaluation. UniFL’s efficacy is evaluated across diverse models and datasets, demonstrating substantial performance enhancements in FL operations. In detail, UniFL can bring up to 40x speedup than the original FL with widely used congestion control algorithms and achieves throughput close to the state-of-the-art LT while being transparent to the workers.

In modern data center networks, RDMA is widely applied in scenarios such as high-performance computing, distributed storage and machine learning. In recent studies, it has been observed that flowlet switching load balancers cannot fully unleash their robust capabilities due to an insufficient number of flowlets in RDMA networks. In this paper, we scrutinize the traffic pattern at the end hosts and meticulously analyze time gaps between packets. Our findings reveal that in RDMA, the proportion of time gaps between packets larger than the flowlet threshold is notably scarce, constituting only a fraction of those in TCP, averaging 1/300. Based on this observation, we propose HF2T, a host-based method to improve the effectiveness of flowlet-level load balancing in RDMA. The core idea is to postpone a minimal number of specific packets at the host, actively elongating the time gaps between them, and promoting flowlet generation at the switch. The cost of postponing a minimal number of packets is far outweighed by the benefits of flowlets generation at the switch, improving the network performance. Simulation experiments confirm that HF2T, when deployed in conjunction with the flowlet load balancing, achieves an average reduction of 37.32% in Medium FCT and an average reduction of 28.75% in 99-percentile FCT, compared to deploying the same flowlet load balancing scheme solely at switches.

Sketch algorithms are crucial for identifying top-k items in large-scale data streams. Existing methods often compromise between performance and accuracy, unable to efficiently handle increasing data volumes with limited memory. We present Bubble Sketch, a compact algorithm that excels in both performance and accuracy. Bubble Sketch achieves this by (1) Recording only full keys of hot items, significantly reducing memory usage, and (2) Using threshold relocation to resolve conflicts, enhancing detection accuracy. Unlike traditional methods, Bubble Sketch eliminates the need for a Min-Heap, ensuring fast processing speeds. Experiments show Bubble Sketch outperforms the other seven algorithms compared, with the highest throughput and precision, and surpasses HeavyKeeper in accuracy by up to two orders of magnitude.

Modern data centers (DCs) employ various traffic load balancers to achieve high bisection bandwidth. Among them, flowlet switching has shown remarkable performance in both load balancing and upper-layer protocol (e.g., TCP) friendliness. However, flowlet-based load balancers suffer from the inflexibility of flowlet timeout value (FTV) and result in sub-optimal performance under various application workloads. To this end, we propose Halflife, a novel flowlet-based load balancer that leverages fading FTVs to reroute traffic promptly under different workloads without any prior knowledge. Halflife not only balances traffic better, but also avoids the performance degradation caused by frequent oscillation or shifting of lows between paths. Furthermore, Halflife's fading mechanism is not only compatible with most flowlet-based load balancers, such as CONGA and LetFlow, but also improves their performance when leveraging flowlet switching in RDMA network. Through testbed experiments and simulations, we prove that Halflife improves the performance of CONGA and LetFlow by 10% ~ 150%, and it outperforms other load balancers by 30% ~ 200% across most application workloads.

Parameter Server (PS) and Ring-AllReduce (RAR) are two widely utilized synchronization architectures in multiworker Deep Learning (DL), also referred to as Distributed Deep Learning (DDL). However, PS encounters challenges with the “incast” issue, while RAR struggles with problems caused by the long dependency chain. The emerging In-network Aggregation (INA) has been proposed to integrate with PS to mitigate its incast issue. However, such PS-based INA has poor incremental deployment abilities as it requires replacing all the switches to show significant performance improvement, which is not costeffective. In this study, we present the incorporation of INA capabilities into RAR, called RAR with In-Network Aggregation (Rina), to tackle both the problems above. Rina features its agent-worker mechanism. When an INA-capable ToR switch is deployed, all workers in this rack run as one abstracted worker with the help of the agent, resulting in both excellent incremental deployment capabilities and better throughput. We conducted extensive testbed and simulation evaluations to substantiate the throughput advantages of Rina over existing DDL training synchronization structures. Compared with the state-of-the-art PS-based INA methods ATP, Rina can achieve more than$\mathbf{5 0 \%}$throughput with the same hardware cost.

Byte-addressable Persistent Storage (BPS), such as persistent memory and CXL-enabled SSDs, has become an extension of main memory. This opens up new possibilities for indexes that operate and persist data directly on the memory bus. Recent learned indexes exploit data distribution and have shown great potential for some workloads. Despite some work proposed for integrating learned indexes into BPS, they are mainly based on Intel’s first-generation persistent memory. The current design suffers from the following problems: 1) Excessive storage line accesses due to large node in learned indexes; 2) Inefficient concurrency control due to volatile cache; 3) Write amplification due to mismatch access granularity.

Interconnection network in HPC is becoming a bottleneck due to increasing traffic load. We model adaptive routing mechanisms and prove that even with advanced adaptive routing, static networks like Dragonfly cannot handle non-uniform traffic efficiently, let alone the frequently changing non-uniform traffic. Therefore, it requires architectural changes for network-wide improvements, e.g., reconfigurable networks.Existing reconfigurable networks hardly support agile reaction to traffic changes with little impact on network. Therefore, we propose MUSE1, a Dragonfly-based runtime incrementally reconfigurable network to enable a small number of link adjustments for agility and little impact on transmitting flows during every reconfiguration with optical circuit switch (OCS).Simulations with both synthetic traffic and real-world workloads prove that MUSE can prevent saturation under typical traffic patterns that cause congestion in static Dragonfly. MUSE is 30-55% better than static Dragonfly and Flexfly w.r.t commonly used performance metrics like flow completion time (FCT). We also build a MUSE prototype and demonstrate that MUSE enables 20-30% less application finish time (AFT).

RDMA over Converged Ethernet (RoCE) has been widely used in datacenter networks and it relies on Priority Flow Control (PFC) to ensure a lossless network. However, PFC brings certain side effects, such as Head-of-Line (HoL) blocking, congestion spreading, and deadlock. Existing solutions demonstrate inherent limitations: either fail to completely eliminate the adverse impacts of PFC or introduce extra challenges. In light of these observations, this paper proposes a novel and practical scheme, Restricted Priority Flow Control (R-PFC). R-PFC consists of two parts: one-hop PFC and Virtual Next Output Queue (VNOQ). Instead of passively regarding PFC as a tool to guarantee a lossless network, one-hop PFC proactively employs PFC in a restrictive manner to minimize packet loss while limiting the spread of congestion within one hop. To further enhance the one-hop PFC, the fine-grained VNOQ solves the HoL blocking issue. We theoretically prove that R-PFC does not lead to deadlock and evaluate the performance of R-PFC under typical datacenter network scenarios in ns3 simulations. The results show that R-PFC outperforms both lossless and lossy networks by 43.76% and 39.46% on average.

Software Defined Networking (SDN) provides users with a unified abstraction of physical networks. To meet the demands of modern data centers, many works have focused on designing network virtualization hypervisors that support multi-tenant SDN. Ternary Content Addressable Memory (TCAM) is widely used in SDN switches for rule storage. While it has extremely high lookup throughput, it also features drawbacks such as small capacity and slow update speed. Faced with multi-tenant scenarios, its limitations are even more pronounced. Existing hypervisors lack consideration for TCAM isolation, leading to slower TCAM updates and the mutual impact of requests from different tenants. Consequently, they fail to provide guaranteed performance to tenants. To solve these problems, we propose TCAMVisor, which further isolates TCAM resources based on traditional SDN hypervisors. Specifically, TCAMVisor provides better allocation mechanisms for TCAM entry and control bandwidth, ensuring inter-tenant isolation while improving resource utilization. Additionally, TCAMVisor improves the update speed of TCAM by delicately placing tenant rules. To the best of our knowledge, TCAMVisor is the first work to effectively achieve tenant isolation in TCAM, with an average throughput improvement of 5.5 times compared to FlowVisor.

Content Delivery Networks (CDNs) are designed to reduce user-perceived waiting times and alleviate backbone bandwidth pressure. Since CDN cache servers have limited storage capacity, effective cache replacement policies are needed. However, existing CDN cache replacement policies mainly focus on improving content hit rates. As a result, some content with long origin fetch latency may not be cached, resulting in the long tail latency and degrading user experience. In this paper, we present Hierarchical Sketch, an efficient, scalable, and latency-aware cache replacement algorithm. Our approach leverages hierarchical slicing and voting mechanisms on a modified sketch to optimize content caching, reducing sorting complexity from O(log n) to O(1) with minimal loss of hit rate. Extensive simulations on synthetic and real-life industry CDN traces demonstrate that Hierarchical Sketch outperforms other algorithms in four different scenarios, with up to a 15% improvement.

Programmable packet scheduling enables the integration of scheduling algorithms into switches without the need for hardware redesign. The Push-In First-Out (PIFO) queue facilitates a programmable packet scheduler, supporting a single scheduling algorithm flexibly. However, hierarchical scheduling required in Multi-Tenant Data Centers (MTDCs) remains non-programmable. Dynamic and diverse hierarchical scheduling algorithms necessitate alterations in both the number of PIFO queues and their connection topology, posing a significant challenge to support them on fixed hardware.

As a programmable accelerator, SmartNIC provides more opportunities for algorithmic packet classification. Our aim in this work is to achieve both line-speed rule search and efficient rule update, two highly desired metrics for SDN data plane. We leverage the parallelism offered by the FPGA in SmartNIC following an algorithm/hardware co-design paradigm. Particularly, we first design an algorithm that constructs multiple trees for the rule set with a recursive rule sifting process. Unlike traditional space-cutting-based multi-tree construction, our rule sifting mechanism breaks the space constraints of rule-to-tree mapping and enables bounded height on each tree, thus providing the potential of bounded worst-case and line-speed performance. We then design a flexible hardware architecture with multiple systolic arrays that can be implemented in parallel on FPGA. Each systolic array works as a coarse-grained pipeline, and the multiple trees constructed earlier will be mapped onto these pipeline stages. This hardware-software mapping enables bounded worst-case rule searching. Additionally, incremental rule update is achieved simply by traversing the pipeline in one pass, with little and bounded impact on rule searching. Experimental results show that our design achieves an average classification throughput of 600.8/147.5 MPPS and an update throughput of 8.2/5.9 MUPS for 10k/100k-scale 5-tuple and OpenFlow rule sets.

Network experiments are essential to network-related scientific research (e.g., congestion control, QoS, network topology design, and traffic engineering). However, (re)configuring various topologies on a real testbed is expensive, time-consuming, and error-prone. In this paper, we propose Software Defined Topology Testbed (SDT), a method for constructing a user-defined network topology using a few commodity switches. SDT is low-cost, deployment-friendly, and reconfigurable, which can run multiple sets of experiments under different topologies by simply using different topology configuration files at the controller we designed. We implement a prototype of SDT and conduct numerous experiments. Evaluations show that SDT only introduces at most 2% extra overhead than full testbeds on multi-hop latency and is far more efficient than software simulators (reducing the evaluation time by up to 2899x). SDT is more cost-effective and scalable than existing Topology Projection (TP) solutions. Further experiments show that SDT can support various network research experiments at a low cost on topics including but not limited to topology design, congestion control, and traffic engineering.

Distributed deep learning (DDL) is a promising research area, which aims to increase the efficiency of training deep learning tasks with large size of datasets and models. As the computation capability of DDL nodes continues to increase, the network connection between nodes is becoming a major bottleneck. Various methods of gradient compression and improved model synchronization have been proposed to address this bottleneck in Parameter-Server-based DDL. However, these two types of methods can result in accuracy loss due to discarded gradients and have limited enhancement on the throughput of model synchronization, respectively. To address these challenges, we propose a new model synchronization method named Overlapped Synchronization Parallel (OSP), which achieves efficient communication with a 2-stage synchronization approach and uses Local-Gradient-based Parameter correction (LGP) to avoid accuracy loss caused by stale parameters. The prototype of OSP has been implemented using PyTorch and evaluated on commonly used deep learning models and datasets with a 9-node testbed. Evaluation results show that OSP can achieve up to 50% improvement in throughput without accuracy loss compared to popular synchronization models.

RoCEv2 (RDMA over Converged Ethernet version 2) is typically used in a PFC-enabled lossless network for high performance, but PFC can cause side effects, such as head-of-line (HoL) blocking and congestion spreading. Optimizing packet loss recovery mechanisms in lossy networks can enhance RDMA network performance, but packet loss can increase FCT of short flows and waste network resources. This paper proposes a novel concept of semi-lossless networks to exploit the advantages of lossless and lossy networks, and reduce their negative effects. Our proposed solution, Selective PFC (S-PFC), implements semi-lossless networks in two dimensions. First, S-PFC ensures no packet loss for short flows while timely dropping long flows. Second, S-PFC guarantees no packet loss at the network edge to prevent premature packet loss and unnecessary resource waste. Typical data center network scenarios and large-scale simulations show that S-PFC can accommodate different traffic demands effectively.

Distributed Machine Learning (DML) systems are utilized to enhance the speed of model training in data centers (DCs) and edge nodes. The Parameter Server (PS) communication architecture is commonly employed, but it faces severe long-tail latency caused by many-to-one “incast” traffic patterns, negatively impacting training throughput. To address this challenge, we design the Loss-tolerant Transmission Protocol (LTP), which permits partial loss of gradients during synchronization to avoid unneeded retransmission and contributes to faster synchronization per iteration. LTP implements loss-tolerant transmission through out-of-order transmission and out-of-order Acknowledges (ACKs). LTP employs Early Close to adjust the loss-tolerant threshold based on network conditions and bubble-filling for data correction to maintain training accuracy. LTP is implemented by C++ and integrated into PyTorch. Evaluations on a testbed of 8 worker nodes and one PS node demonstrate that LTP can significantly improve DML training task throughput by up to 30x compared to traditional TCP congestion controls, with no sacrifice to final accuracy.

Ternary Content Addressable Memory (TCAM) is widely used in Software-Defined Networking (SDN) switches due to its impressive throughput. But its unique circuit design results in long and inconsistent update delays. To overcome this challenge, many TCAM update algorithms based on rule semantics have been proposed. These algorithms eliminate unnecessary order restrictions, thus reducing update delays in theory. However, most commodity switches are semantic-unaware, which maintain rules in strict priority order. These algorithms are therefore not available for practical use. To address this issue, this paper proposes Rusen, a framework that enables the use of many semantic-based algorithms on Semantic-unaware commodity switches. Working as a transparent middle layer, the core idea of Rusen is to express the update scheme derived by semantic-based algorithms as messages that the Semantic-unaware switches can execute. In addition, Rusen optimizes the update scheme based on the specific characteristics of each switch, leading to improved performance of these algorithms. We evaluate the performance of Rusen by enabling several state-of-the-art semantic-based algorithms on commodity SDN switches. Results show that the average update delay can be significantly reduced by 23%∼94% on OpenFlow switches and 39%∼84% on a P4 switch.

Push-In-First-Out (PIFO) queue has been extensively studied as a programmable scheduler. To achieve accurate, large-scale, and high-throughput PIFO implementation, we propose the Balanced Multi-way (BMW) Sorting Tree for real-time packet sorting. The tree is highly modularized, insertion-balanced and pipeline-friendly with autonomous nodes.

Distributed Machine Learning (DML) is proposed not only to accelerate the training of machine learning, but also to solve the inadequate ability for handling a large amount of training data. It adopts multiple computing nodes in data center to collaboratively work in parallel at the cost of high communication overhead. Gradient Compression (GC) is introduced to reduce the communication overhead by reducing the number of synchronized gradients among computing nodes. However, existing GC solutions suffer from varying network congestion. To be specific, when some computing nodes experience high network congestion, their gradient transmission process could be significantly delayed, slowing down the entire training process. To solve the problem, we propose FLASH, a congestion-aware GC solution for DML. FLASH accelerates the training process by jointly considering the iterative approximation of machine learning and dynamic network congestion scenarios. It can maintain good training performance by adaptively adjust and schedule the number of synchronized gradients among computing nodes. We evaluate the effectiveness of FLASH using AlexNet and Resnet18 under different network congestion scenarios. Simulation results show that under the same number of training epochs, FLASH reduces training time 22-71%, maintains good accuracy, and low loss, compared with the existing memory top-K GC solution.

Edge-assisted Distributed Learning (EDL) is a popular machine learning paradigm that uses a set of distributed edge nodes to collaboratively train a machine learning model using training data. Most of existing works implicitly assume that the fixed amount of training data is pre-collected and dispatched from user devices to edge nodes. In real world, however, training data in edge nodes are collected from user devices through wireless networks, and the volume and distribution of training data in edge nodes could exhibit temporal and spatial fluctuations due to varying wireless situations (e.g., network congestion, link capacity variation). In this way, existing solutions suffer from slow convergence and low accuracy. In this paper, we propose SpongeTraining to achieve high efficiency and accuracy for online EDL. To accommodate to fluctuations in training data, SpongeTraining uses a buffer at each worker to store received training data and adaptively adjusts training batch size and learning rate of each worker based on training data extracted from the buffer. Experiment results based on real-world datasets show that SpongeTraining outperforms existing solutions by accelerating the training process up to 50% for reaching the same training accuracy.

Frequency estimation and top-k flows identification are fundamental problems in network traffic measurement. Sketch, as a basic probabilistic data structure, has been extensively investigated and used in different management applications. However, few of them is suitable for both estimating frequency and finding top-k flows due to the unbalanced distribution of real-world network streams. By introducing a pre-filtering stage to isolate elephant and mice flows, the recently proposed Augmented Sketch (ASketch) significantly improves accuracy for both tasks. However, it suffers from serious performance degradation because of frequent flow exchanges. In this paper, we propose Cuckoo Counter (CC), an adaptive structure that consists of several buckets organized in a specific way. The size of the entry in each bucket is carefully designed to match the actual distribution of streams. During processing, CC hashes a flow to buckets and uses the idea of cuckoo hashing to relocate the flow if an overflow or collision happens, which contributes to fully utilizing memory. Therefore, the replacement strategy helps CC precisely record elephant flows and cover more mice flows, and also guarantees the throughput. Extensive experimental results show that CC has the highest (Freq.) accuracy, excellent (Heavy hitter / change) accuracy, highest (Top-k) precision, and competitive throughput compared to the state-of-the-art. Specifically, CC improves the throughput and accuracy by around 1 and 2 orders of magnitude respectively compared to the well-known ASketch.

Emerging network-attached resource disaggregation architecture requires ultra-low latency rack-scale communication. However, current hardware offloading (e.g., RDMA) and user-space (e.g., mTCP) communication schemes still rely on heavily layered protocol stacks which requires the translation between PCIe bus and network protocol, or complex connection/memory resource management within RNICs, inevitably bringing latency overhead.

FPGA has been recognized as an attractive acceler-ator for line-speed packet classification in SmartNIC due to its ability to reconfigure and provide massive parallelism. As a promising algorithmic approach that can fully exploit the FPGA characteristics, decision tree based packet classification on FPGA has been actively investigated in the past decade. However, most of them suffer from unbalanced tree structures with unpredictable depths under certain rule sets, so the potential of FPGA may not be brought into full play. Worse still, few of them can support efficient rule updates on-the-fly, which is highly required in virtualized data centers. To address these issues, we design and implement an efficient hardware ar-chitecture based on the recently proposed KickTree algorithm, which consists of multiple balanced trees with bounded depth. A strategy of multi-PE (processing element), parallel search, and serial update is adopted to decouple the search and update process. The parsing of multiple tree search results adopts a modular and hierarchical design, supporting architecture with various tree numbers. Additionally, incremental rule updates can be achieved simply by traversing all PEs in one pass, with little and bounded impact on rule searching. Experimental results on FPGA show that our design can achieve an average classification throughput of 182.6 MPPS and an average update throughput of 3.1 MUPS for various 100k-scale rule sets.

The modern data centers require high throughput and low latency transmission to meet the demands of distributed applications on communication delay. Compared with traditional sender-driven try-and-back-off protocols (e.g., TCP and its variants), receiver-driven protocols (RDPs) achieve the ultra-low transmission latency by reacting to credits or tokens from receivers. However, RDPs face fairness challenges when coexisting with sender-driven protocols (SDPs) in multi-tenant data centers. Their flows barely survive during coexistence with SDP flows since the delicate scheduling of their credits is disrupted and overwhelmed by SDP data packets. To tackle this issue, we propose the Equivalent Rate Adaptor (ERA), a scheme that converts the proactive try-and-back-off mode of SDPs to an RDP-like credit-based reactive mode. ERA leverages the advertised window field in ACK headers at the receiver side to elaborately limit the number of the in-flight packets or bytes in SDPs and thus reduce their impacts on RDPs. Therefore, ERA not only ensures the fairness between two different types of protocols, but also maintains the low latency feature of RDPs. Moreover, ERA is lightweight, flexible, and transparent to tenants by embedding into the prevalent Open vSwitch in the public cloud. The evaluation of both test-bed and NS2 simulation shows that ERA enables SDP flows and RDP flows to maintain good throughput and share the bandwidth fairly, improving the bandwidth stolen by up to 94.29%.

Time-Sensitive Networking (TSN) is proposed in recent years to satisfy the strict performance requirements of time-sensitive traffic in a growing number of emerging applications. Even though several traffic scheduling algorithms have been standardized for TSN to pursue this goal, time-sensitive flows may not be forwarded as planned and thus fail to achieve the expected performance in real networks. The fundamental cause lies in the fact that static offline planning cannot adapt to the intrinsic dynamic factors in TSN (e.g., time-synchronization error) at runtime. Hence, next-generation TSN will benefit from a closed-loop design where a performance monitoring system provides feedback of real-time packet-forwarding information. In our research, TSN-Peeper, a light-weight, fast-response and full-coverage TSN performance monitoring system, is designed and evaluated. This paper describes its architecture design and data collection mechanisms that enable timely identification and collection of packet-forwarding misbehavior at low-cost in TSN. TSN-Peeper offloads the misbehavior identification in the switch to relieve the burden on the controller and network bandwidth. To reduce the interruption frequency to the controller, it uses probe packets to collect misbehavior information in aggregation with optimized path planning. To realize controllable reporting delays, it optimizes the sending moments of probe packets according to the flow settings. Experimental results verify that TSN-Peeper offers fast response with low cost while providing full coverage and being scalable.

Programmable switches have been proposed in today’s network to enable flexible reconfiguration of devices and reduce time-to-deployment. Buffer sizing, an important factor for network performance, however, has not received enough attention in programmable network. The state-of-the-art buffer sizing solutions usually employ either fixed buffer size or adjust the buffer size heuristically. Without programmability, they suffer from either massive packet drops or large queueing delay in dynamic environment. In this paper, we propose Adaptive Buffer Sizing (ABS), a low-cost and deploy-friendly framework compatible with programmable network. By decoupling the data plane and control plane, ABS-capable switches only need to react to the actions from controller, optimizing network performance in run-time under dynamic traffic. Meanwhile, actions can be programmed by particular Machine Learning (ML) models in the controller to meet different network requirements. In this paper, we address two specific ML models for different scenarios, a reinforcement learning model for relatively stable network with user specific quality requirements, and a supervised learning model for highly dynamic network condition. We implement the ABS framework by integrating the prevalent network simulator NS-2 with ML module. The experiment shows that ABS outperforms state-of-the-art buffer sizing solutions by up to 38.23x under various network environments.

The unique hardware structure of Ternary Content-Addressable Memory (TCAM) enables its unparalleled lookup throughput but also causes slow update due to the Priority Order Constraint (POC). With the increase of application demands, TCAM update has become a bottleneck in the network. This paper proposes a new TCAM management mechanism named BubbleTCAM to enable fast TCAM update, in which available empty entries are defined as bubbles. The core idea of Bub-bleTCAM is to uniformly distribute bubbles and dependency chains in TCAM, which is beneficial to updates. BubbleTCAM consists of two components: bubble management and rule insertion. Bubble management enables TCAM to have uniformly distributed bubbles at all times through three key procedures: bubble lock reservation, bubble lock release and bubble generation. Rule insertion ensures that dependency chains of rules are uniformly stretched and distributed in TCAM. In addition, BubbleTCAM avoids the reorder problem by pre-sorting. Our evaluation based on the rulesets generated by ClassBench shows that BubbleTCAM effectively reduces the average cost and worst cost (in units of rule movements) during rule updates by at least 48% and 50%, respectively. Especially for the worst cost, the performance can be improved by up to 196x.

Load Balancing plays a vital role in cloud data centers to distribute traffic among instances of network functions or services. State-of-the-art load balancers dispatch traffic obliviously without considering the real-time utilization of service instances and therefore can lead to uneven load distribution and sub-optimal performance. In this article, we design and implement Spotlight, a scalable and distributed load balancing architecture that maintains connection-to-instance mapping consistency at the edge of data center networks. Spotlight uses a new stateful flow dispatcher which periodically polls instances’ load and dispatches incoming connections to instances in proportion to their available capacity. Our design utilizes a distributed control plane and in-band flow dispatching; thus, it scales horizontally in data center networks. Through extensive flow-level simulation and packet-level experiments on a testbed with HTTP traffic on unmodified Linux kernel, we demonstrate that compared to existing methods Spotlight distributes traffic more efficiently and has near-optimum performance in terms of overall service utilization. Compared to existing solutions, Spotlight improves aggregated throughput and average flow completion time by at least 20 percent with infrequent control plane updates. Moreover, we show that Spotlight scales horizontally as it updates the switches at O(100ms) and is resilient to lack of control plane convergence.

Software-defined networking (SDN) is increasingly popular in today’s information technology industry, but existing SDN control plane is insufficiently scalable to support on-demand, high-frequency flow requests. Weaknesses along SDN control paths can be exploited by malicious third parties to launch distributed denial-of-service (DDoS) attacks against the SDN control plane. Recently proposed solutions only partially solve the problem, by protecting either the SDN network edges or the centralized controller. We propose SDNShield, a solution based on emerging network function virtualization (NFV) technologies, which enforces more comprehensive defense against potential DDoS attacks on SDN control plane. SDNShield incorporates a three-stage overload control scheme. The first stage statistically identifies legitimate flows with low complexity and performance overhead. The second stage further performs in-depth TCP handshake verification to ensure good flows are eventually served. The third stage intellectually salvages the misclassified legitimate flows that are falsely dropped from the first two stages. Prototype tests and real data-driven simulation results show that SDNShield can achieve high resilience against brute-force attacks, and maintain good flow-level service quality at the same time.

Providing resilient network control is a critical concern for deploying Software-Defined Networking (SDN) into Wide-Area Networks (WANs). For performance reasons, a Software-Defined WAN is divided into multiple domains controlled by multiple controllers with a logically centralized view. Under controller failures, we need to remap the control of offline switches from failed controllers to other active controllers. Existing solutions have three limitations: (1) the least flow programmability (e.g., the ability to change paths of flows) cannot be maintained; (2) active controllers could be overloaded, interrupting their normal operations; (3) network performance could be degraded because of the increasing controller-switch communication overhead. In this paper, we propose RetroFlow+ to recover the flow programmability and achieve low communication overhead during controller failures. By intelligently configuring a set of selected offline switches working under the legacy routing mode and several active controllers releasing a few control resources, RetroFlow+ enables active controllers to use the minimum control resource to sustain the flow programmability. RetroFlow+ also smartly transfers the control of offline switches with the SDN routing mode to active controllers to minimize the communication overhead from these offline switches to the active controllers. Simulation results show that RetroFlow+ realizes low communication overhead, recovers all offline flows under one and two controller failures, and improves the flow recovery percentage up to 70% under three controller failures, compared with the state-of-the-art solution.

Traditional routing schemes usually use fixed models for routing policies and thus are not good at handling complicated and dynamic traffic, leading to performance degradation (e.g., poor quality of service). Emerging Deep Reinforcement Learning (DRL) coupled with Software-Defined Networking (SDN) provides new opportunities to improve network performance with automatic traffic analysis and policy generation. However, existing DRL-based routing solutions usually rely on all node information to make routing decisions for the network and hence are both hard to converge in large networks and vulnerable to topology changes. In this paper, we propose ScaleDeep, a scalable DRL-based routing scheme for SDN, which improves the routing performance and is resilient to topology changes. Essentially, ScaleDeep takes advantage of partial control on network nodes and DRL. We select a set of critical nodes from a network as driver nodes, which can simulate the entire network operation, based on the control theory. By observing the traffic variation on the driver nodes, DRL dynamically adjusts some link weights for a weighted shortest path algorithm to change the routing paths and improve the routing performance. Limiting the control on driver nodes improves the convergence ability of DRL and reduces the dependency of the DRL agent on the fixed network topology. To validate the performance of ScaleDeep, we conduct packet-level simulations on different topologies. The results show that ScaleDeep outperforms existing DRL-based schemes by reducing the average flow completion time by up to 36% and exhibiting better robustness against minor topology changes.

As a promising alternative to TCAM-based solutions for packet classification, FPGA has received increasing attention. Although extensive research has been conducted in this area, existing FPGA-based packet classifiers cannot satisfy the burgeoning needs from OpenFlow, which demands large-scale rule sets and frequent rule updates. As a recently proposed hardware-specific approach, TabTree avoids rule replication and supports dynamic rule update. However, it still faces problems of unbalanced rule subset partition, unevenly distributed subtrees and excessive TSS leaf nodes when implemented on FPGA. In this paper, we propose a hardware-friendly packet classification approach called KickTree, which is elaborated by considering hardware properties. To take advantage of intrinsic parallelism of FPGA, KickTree adopts multiple balanced decision trees which can run simultaneously. The bit selection is more flexible which breaks the restriction of rule subset. Moreover, each subset size is strictly limited, leading to bounded and evenly-distributed

TCAM is widely used for flow table lookup in Software-Defined Networking (SDN) switches for datacenter and enterprise networks. While its lookup throughput is unparalleled, TCAM updating, particularly for new rule insertions, can impair the overall system performance. A rule insertion entails two steps: 1) Computing the rule moving operations; and 2) Interrupting the TCAM lookups to apply the operations. In previous work, the performance gain on one step is always at the expense of the performance loss on the other. However, update throughput and latency depend on both. In this paper, we present a faster and more balanced TCAM update scheme, which not only achieves the shortest interrupt time so far but also significantly reduces the computation time. By using a novel sequential stack, FastUp reduces the time and space complexity of the state-of-the-art schemes from$O(m^{2})$and$O(m)$to$O(m\log h)$and$O(h)$, respectively, where$h << m$. Evaluations show that FastUp shortens the computation time and the interrupt time by$100\times$and$1.6\times$, respectively, which is equivalent to update delay${15\times}$reduction and$\mathbf{10\times}$update throughput gain against the state-of-the-art schemes. Moreover, we debunk a common mistake and show the dynamic programming based algorithm cannot be used to solve the reorder problem, and instead we use a bidirectional rule moving method to address the problem. In addition, we propose a practical method to find the theoretical lower bound of interrupt time in relatively large TCAM, which can be used to evaluate the optimality degree of TCAM update schemes. Evaluations show that FastUp achieves 90 % optimality.

Ternary Content-Addressable Memory (TCAM) is a popular solution for high-speed flow table lookup in Software-Defined Networking (SDN). Rule insertion in TCAM is a time-consuming operation. To ensure semantic correctness, rules overlapped must be stored in TCAM with decreasing priority order and many rule movements may be needed to make space for a single inserted rule. When a rule insertion is in progress, the regular flow table lookup will be suspended, which could lead to a degraded user experience for SDN applications. In this paper, we propose a multiple-TCAM framework named MagicTCAM to reduce the rule movements during a rule insertion. The core of MagicTCAM lies in three operations: layering, partitioning and rotating. By layering, rules with the least overlapping will be grouped (i.e., layered) into a sub-ruleset. The number of rule movements is therefore greatly reduced as most of rules in a sub-ruleset are non-overlapped. To achieve balanced load in TCAMs, rules in each sub-ruleset are further partitioned and dispatched into different TCAMs in a rotating manner. In addition, an inter-TCAM movement algorithm is proposed to allow rules to be moved between TCAMs for reduced rule movement. Experiment results show that with two half-sized TCAMs, MagicTCAM reduces the rule movements by 39% on average compared with the state-of-the-art work while the computation time is shortened by half as well.

Time Sensitive Networking (TSN) is an emerging Ethernet technology for real-time systems. To address different Quality-of-Service (QoS) requirements of applications, IEEE 802.1 TSN Task Group has standardized several packet scheduling and shaping algorithms. The software implementation of these algorithms is hard to meet the performance requirements, while the hardware implementation in Application-Specific Integrated Circuit (ASIC) is inflexible. A hardware-programmable scheduler is necessary to deal with this dilemma. Among the existing primitives, the most expressive one is Push-In-Extract-Out (PIEO), but its complexity makes the implementation very expensive. A relatively lower-cost implementation of PIEO cannot guarantee the scheduling correctness for the most critical Time-Triggered (TT) traffic in TSN. As a remedy, in this paper we propose a new Push-In-Pick-Out (PIPO) primitive under a TSN programmable scheduling framework. Composed of simple priority queues, PIPO can express all existing TSN scheduling and shaping algorithms, and is flexible enough to support future ones. Our PIPO implementation guarantees the TT traffic scheduling correctness. The simulation results corroborate the theoretical analysis that the low-cost PIPO can closely approximate PIEO and sustain a high bandwidth utilization. The prototype on Xilinx FPGA shows that, with 2,048 inputs, the PIPO-based scheduler achieves a throughput of 70 Mpps, which is 1.64x higher than the PIEO-based one, but using only 14.7% Look-Up Tables (LUTs) and 40.5% Block RAMs of the latter.

The traffic of modern data centers exhibits long-tail distribution, in which massive delay-sensitive short flows and a small number of bandwidth-hungry long flows co-exist. These two types of flows could share same bottleneck links in the data center networks but request different or even opposite network requirements. Existing solutions try to realize a trade-off between the requirements of different flows by either prioritizing short flows or limiting the buffer used by long flows at switches or end-hosts. However, they do not consider the dynamic traffic change and suffer from performance degradation, resulted from severe queueing delay and massive packet drops for short flows under current First-In-First- Out (FIFO) queueing mechanism. In this paper, we propose a novel buffer management scheme at switches, called Cut-in Queue (CQ), to achieve both low latency for short flows and high throughput for long flows. Based on network status in real time, CQ prioritizes short flows by dynamically cutting the short flows’ packets into the head of long flows or evicting some enqueued long flows’ packets and enables high throughput for long flows in most of the cases. Evaluation of both DPDK testbed and NS2 simulations show that CQ outperforms state-of-the-art buffer management schemes by reducing flow completion time by up to 73%.

Rule update in TCAM has long been identified as a key technical challenge due to the rule order constraint. Existing algorithms take each rule update as an independent task. However, emerging applications produce batch rule update requests. Processing the updates individually causes high aggregated cost which can strain the processor and/or incur excessive TCAM lookup interrupts. This paper presents the first true batch update algorithm, ABUT. Unlike the other alleged batch update algorithms, ABUT collectively evaluates and optimizes the TCAM placement for whole batches throughout. By applying the topology grouping and maintaining the group order invariance in TCAM, ABUT achieves substantial computing time reduction yet still yields the best-in-class placement cost. Our evaluations show that ABUT is ideal for low-latency and high-throughput batch TCAM updates in modern high-performance switches.

Power-aware traffic engineering via coordinated sleeping is usually formulated into Integer Programming problems, which are generally NP-hard with unbounded computation time for large-scale networks. This results in delayed control decision making in dynamic network environments. Motivated by advances in deep Reinforcement Learning, we consider building intelligent systems that learn to adaptively change router/switch’s power state according to changing network conditions. Neural network’s forward propagation can greatly speed up power on/off decision making. Generally, conducting RL requires a learning agent to iteratively explore and perform the "good" actions based on the feedback from the environment. By coupling Software-Defined Networking for performing centrally calculated actions to the environment and In-band Network Telemetry for collecting feedback from the environment, we develop GreenTE.ai, a closed-loop control/training system to automate power-aware traffic engineering. Furthermore, we propose novel techniques to enhance the learning ability and reduce the learning complexity. With both energy efficiency and traffic load balancing considered, GreenTE.ai can generate reasonable power saving actions within 276ms under a network testbed of 11 software P4 switches.

The scalability issue hinders the deployment of Software-Defined Networking (SDN) in the Wide Area Networks (WANs). Existing solutions have two issues: (1) network performance relies on complicated controller synchronization, which increases the complexity of network control; (2) fine-grained flow processing enables flexible flow control at the cost of high processing load on the controllers and high flow table occupancy on switches. In this paper, we propose a scalable routing solution named HybridFlow, which achieves a good load balancing performance using a single controller with low control overhead (i.e., flow routing and rerouting overhead). HybridFlow mainly employs two techniques: hybrid routing and crucial flow rerouting. Hybrid routing enabled by commercial SDN switches gives us opportunities to reduce the processing load of the controller by routing flows with the hybrid OpenFlow/OSPF mode. Thus, the majority of flows can be routed by OSPF without involving the controller. Crucial flow rerouting realizes load balancing by dynamically identifying crucial flows based on a new metric called Variation Slope and rerouting these flows with the hybrid OpenFlow/OSPF mode. The simulation based on the real traffic traces and network typologies shows that compared with the optimal solution, HybridFlow can achieve 87% of the optimal load balancing performance by rerouting 36% less flows on average.

Power-efficient Data Center Networks (DCNs) have been proposed to save power of DCNs using OpenFlow. In these DCNs, the OpenFlow controller adaptively turns on/off links and OpenFlow switches to form a minimum-power subnet that satisfies the traffic demand. As the subnet changes, flows are dynamically routed and rerouted to the routes composed of active switches and links. However, existing flow scheduling schemes could cause undesired results: (1) power inefficiency: due to unbalanced traffic allocation on active routes, extra switches and links may be activated to cater to bursty traffic surges on congested routes, and (2) Quality of Service (QoS) fluctuation: because of the limited flow entry processing ability, switches may not be able to timely install/delete/update flow entries to properly route/reroute flows. In this paper, we propose AggreFlow, a dynamic flow scheduling scheme that achieves power efficiency and QoS improvement using three techniques: Flow-set Routing, Lazy Rerouting, and Adaptive Rerouting. Flow-set Routing achieves load balancing with a small number of flow entry operations by routing flows in a coarse-grained flow-set fashion. Lazy Rerouting spreads rerouting operations over a relatively long period of time, reducing the burstiness of entry operation on switches. Adaptive Rerouting selectively reroutes flow-sets to maintain load balancing. We built an NS3 based fat-tree network simulation platform to evaluate AggreFlow's performance. The simulation results show that AggreFlow reduces power consumption by about 18%, yet achieving load balancing and improved QoS (low packet loss rate and reducing the number of processing entries for flow scheduling by 98%), compared with baseline schemes.

Ternary Content Addressable Memory (TCAM) is widely used by modern routers and switches to support policy-based forwarding due to its incomparable lookup speed and flexible matching patterns. However, the limited TCAM capacity does not scale with the ever-increasing rule table size due to the high hardware cost and high power consumption. At present, using TCAM just as a rule cache is an appealing solution, but one must resolve several tricky issues including the rule dependency and the associated TCAM updates. In this paper, we propose a new approach which can generate dependency-free rules to cache. By removing the rule dependency, the complex TCAM update problem also disappears. We provide the complete T-cache system design including slow path processing and cache replacement, and implement a T-cache prototype on Barefoot Tofino switches. We conduct comprehensive software simulations and hardware experiments based on real-world and synthesized rule tables and packet traces to show that T-cache is efficient and robust for network traffic in various scenarios.

Machine Learning (ML)-based routing optimization has been proposed to optimize the performance of flow routing for future networks, such as Software-Defined Networks (SDNs). However, existing studies are either hard to converge for large networks or vulnerable to topology changes. In this paper, we propose SINET, a scalable and intelligent network control framework for routing optimization. To improve the robustness and scalability, SINET selects several critical routing nodes to be directly controlled by a Deep Reinforcement Learning (DRL) agent, which dynamically generates routing policy to optimize network performance. Simulation results show that SINET can reduce the average flow completion time by at least 32% for a network with 82 nodes and exhibit better robustness against minor topology changes, compared to other DRL-based schemes.

While widely used for flow tables in SDN switches, TCAM faces challenges for rule updates. Both the computation time and interrupt time need to be short. We propose FastUp, a new TCAM update algorithm, which improves the previous dynamic programming-based algorithms. Evaluations show that FastUp shortens the computation time by 40~100× and the interrupt time by 1.2~2.5×. In addition, we are the first to prove the NP-hardness of the optimal TCAM update problem, and provide a practical method to evaluate an algorithm's degree of optimality. Experiments show that FastUp's optimality reaches 90%.

Ternary Content Addressable Memory (TCAM) is widely used by modern routers and switches to support policy-based forwarding. However, the limited TCAM capacity does not scale with the ever-increasing rule table size. Using TCAM just as a rule cache is a plausible solution, but one must resolve several tricky issues including the rule dependency and the associated TCAM updates. In this paper, we propose a new approach which can generate dependency-free rules to cache. By removing the rule dependency, the TCAM update problem also disappears. We provide the complete T-cache system design including slow path processing and cache replacement. Evaluations based on real-world and synthesized rule tables and traces show that T-cache is efficient and robust for network traffic in various scenarios.

With the rapid development of Internet applications, diversified Quality of Service (QoS) has been required in packet routing to meet the demand of various types of applications. This paper presents an Intelligent QoS-aware Routing (IQoR) framework with the assistance of Deep Reinforcement Learning (DRL), which supports multi-class QoS provisioning for packet forwarding. The simulation results show that IQoR outperforms the widely-used benchmark routing algorithms by significantly reducing the average delay and jitter of packets.

Although many distributed denial of service (DDoS) attacks detection algorithms have been proposed and even some of them have claimed high detection accuracy, DDoS attacks are still a major problem for network security. The latent and inherent problems of these detection algorithms are 1) Requirement of both normal and attack data for building detection models, and 2) Almost inability to detect novel and unknown DDoS attacks. To conquer the problems, this paper proposes an AutoEncoder based DDoS attacks Detection Framework (AE-D3F), which only uses normal traffic to build the detection model and is able to update itself automatically as time goes. Experimental results on synthetic and public traffic show that our AE-D3F can not only achieve 82.00% detection rate (DR) with 0 false positive rate (FPR), better than classical anomaly detection approaches, but also detect novel and unknown attacks.

Providing resilient network control is a critical concern for deploying Software-Defined Networking (SDN) into Wide-Area Networks (WANs). For performance reasons, a Software-Defined WAN is divided into multiple domains controlled by multiple controllers with a logically centralized view. Under controller failures, we need to remap the control of offline switches from failed controllers to other active controllers. Existing solutions could either overload active controllers to interrupt their normal operations or degrade network performance because of increasing the controller-switch communication overhead. In this paper, we propose RetroFlow to achieve low communication overhead without interrupting the normal processing of active controllers during controller failures. By intelligently configuring a set of selected offline switches working under the legacy routing mode, RetroFlow relieves the active controllers from controlling the selected offline switches while maintaining the flow programmability (e.g., the ability to change paths of flows) of SDN. RetroFlow also smartly transfers the control of offline switches with the SDN routing mode to active controllers to minimize the communication overhead from these offline switches to the active controllers. Simulation results show that compared with the baseline algorithm, RetroFlow can reduce the communication overhead up to 52.6% during a moderate controller failure by recovering 100% flows from offline switches and can reduce the communication overhead up to 61.2% during a serious controller failure by setting to recover 90% of flows from offline switches.

Since, current widely available network protocols/ systems are mainly throughput-oriented designs, meeting stringent delay requirements of new applications such as virtual reality and vehicle-to-vehicle communications on cellular network requires new network protocol/system designs. C2TCP is an effort toward that new design direction. C2TCP is inspired by in-network active queue management designs such as RED and CoDel and motivated by lack of a flexible end-to-end approach which can adapt itself to different applications' QoS requirements without modifying any network devices. It copes with unique challenges in cellular networks for achieving ultra-low latency (including highly variable channels, deep per-user buffers, self-inflicted queuing delays, and radio uplink/downlink scheduling delays) and intends to satisfy stringent delay requirements of different applications while maximizing the throughput. C2TCP works on top of classic throughput-oriented TCP and accommodates various target delays without requiring any channel prediction, network state profiling, or complicated rate adjustment mechanisms. We have evaluated C2TCP in both real-world environment and extensive trace-based emulations and compared its performance with different TCP variants and state-of-the-art schemes including PCC-Vivace, Google's BBR, Verus, Sprout, TCP Westwood, and Cubic. Results show that C2TCP outperforms all these schemes and achieves lower average delay, jitter, and 95th percentile delay for packets.

To improve traffic management ability, Internet Service Providers (ISPs) are gradually upgrading legacy network devices to programmable devices that support Software-Defined Networking (SDN). The coexistence of legacy and SDN devices gives rise to a hybrid SDN. Existing hybrid SDNs do not consider the potential performance issues introduced by a centralized SDN controller: flow requests processed by a highly loaded controller may experience long-tail processing delay; inappropriate multi-controller deployment could increase the propagation delay of flow requests. In this paper, we propose to jointly consider the deployment of SDN switches and their controllers for hybrid SDNs. We formulate the joint problem as an optimization problem that maximizes the number of flows that can be controlled and managed by the SDN and minimizes the propagation delay of flow requests between SDN controllers and switches under a given upgrade budget constraint. We show this problem is NP-hard. To efficiently solve the problem, we propose some techniques (e.g., strengthening the constraints and adding additional valid inequalities) to accelerate the global optimization solver for solving the problem for small networks and an efficient heuristic algorithm for solving it for large networks. The simulation results from real network topologies illustrate the effectiveness of the proposed techniques and show that our proposed heuristic algorithm uses a small number of controllers to manage a high amount of flows with good performance.

Multiple distributed controllers have been used in software-defined networks (SDNs) to improve scalability and reliability, where each controller manages one static partition of the network. In this paper, we show that dynamic mapping between switches and controllers can improve efficiency in managing traffic load variations. In particular, we propose balanced controller (BalCon) and BalConPlus, two SDN switch migration schemes to achieve load balance among SDN controllers with small migration cost. BalCon is suitable for the scenarios where the network does not require a serial processing of switch requests. For other scenarios, BalConPlus is more suitable, as it is immune to the switch migration blackout and does not cause any service disruption. Simulations demonstrate that BalCon and BalConPlus significantly reduce the load imbalance among SDN controllers by migrating only a small number of switches with low computation overhead. We also build a prototype testbed based on the open-source SDN framework RYU to verify the practicality and effectiveness of BalCon and BalConPlus. Experiment confirms the results of the simulations. It also shows that BalConPlus is immune to switch migration blackout, an adverse effect in the baseline BalCon.

Many applications in public clouds require a high fan-in, many-to-one type of data communication (known as TCP incast) in modern Data Center Networks (DCNs). Such communication could cause severe incast congestion in switches and result in TCP throughput collapse, substantially degrading the application performance. The root cause of throughput collapse is the Retransmission Timeouts (RTO) due to packet losses in congested switches. Tenants in public clouds can opt to use a variety of TCP versions. However, the existing solutions rely on modifications of TCP protocols and specific techniques from switches, and thus these existing solutions are not always feasible for public clouds. In this paper, we are inspired by the emerging virtualization and network softwarization technologies to develop a novel scheme called Retransmission timeout Avoidance by Packet Intelligent Discarding (RAPID) using software switches. RAPID considers the number of packets of each incast flow, buffered in the switch to selectively discard some packets, and ensures that the Fast Retransmission/Fast Recovery rather than RTO is invoked at the sender(s) in response to packet loss. Thus, the long idle period of a timeout and the throughput drop are avoided. We prove that, given a predetermined minimum switch buffer space, dedicated to the incast application, RAPID can prevent RTO in all the incast senders. We also present a low-complexity heuristic version of RAPID named RAPID-ED, which combines the principles of RAPID and early detection and is extremely easy to implement on today's software switches. We evaluate the two proposed schemes in a data center network testbed built on NS-3 simulator. The simulation results confirm the theoretical expectation, and show that the RAPID and RAPID-ED perform very well to prevent RTO of TCP incast flows and hence the throughput collapse. Compared with other incast solutions, RAPID and RAPID-ED do not modify TCP protocols and therefore are more suitable in public clouds.

Advances in software-defined networking (SDN) enable a wave of innovation in a wide selection of networks ranging from data center networks to WAN. While existing standard bodies for mobile networks define stringent requirements, they too are embracing the flexibility of SDN in defining the specifications of the next generation of mobile networks. Mobile edge computing (MEC), in particular, is an emerging architecture to bring virtualized network functions and programmable network devices closer to the user. For instance, delay-sensitive or bandwidth-hungry computing resources are moved to the edge of the radio access network (RAN) to provide low latency computation and/or content for users while alleviating the backhaul pressure for network operators. In this paper, we propose an edge gateway (EGW) in the MEC that enables offloading of computation and storage resources to the edge of mobile networks. The EGW is backward compatible with components and protocols of LTE networks and does not require any modification in the user equipment, LTE software, or offloaded resources. We have designed and implemented the EGW using P4 language and verified its operation on a small testbed using a low-end P4 target and a reference LTE protocol stack.

Vehicular Cloud and autonomous vehicles require a scalable and reliable mobile communication network. LTE and Dedicated Short Range Communication (DSRC) have been trying to fit for such role, yet neither can satisfy all requirement due to inherent architectural limitations. Fortunately the fifth generation mobile network, 5G and Mobile Edge Cloud/Computing (MEC) is around the corner, targeting ultra low packet delay, high reliability, and Gigabit level wireless bandwidth. This paper introduces a unique vehicular MEC architecture where instead of simply off-loading application service to the edge servers on MEC, vehicular communication packets are routed through the MEC network. We discuss in detail how it accommodates vehicle to vehicle (V2V) and vehicle to infrastructure (V2I) communication with high scalability and guaranteed low packet delay. We also provide an in depth analysis of the pros and cons of our MEC vehicle network design, and address the mobility management issue on edge cloud. Applying distributed mobility management (DMM) operations we are able to make edge cloud IP handoff seamless and transparent. Proof of concept simulations are conducted using NS3.

Enforcing network policies is critical for service deployments over software-defined networks (SDN). Most existing studies suggest proactively compiling policies into flow entries in the data plane and updating the installed entries when necessary. With a growing amount of applications, taking a proactive approach may overflow underlying switch memory. Meanwhile, certain policies can be frequently updated. Such updates may propagate across configurations in the network, leading to a long time for correctness validation. To improve both the scalability and the flexibility of SDN policy enforcement, we advocate reactively deploying network policies in the data plane. To this end, we propose a network-wide policy enforcement framework named BigMaC. BigMaC advertises a neat policy model for network managers to specify various network policies as rules. It then caches the rules as flow entries in the switches reactively on demand. One major challenge for the BigMaC design is to guarantee the consistency of defined policies and cached entries in the network. To maintain consistency with efficient table usage and simple updates, we group rules into buckets and perform rule caching in the unit of buckets. With trace-driven simulations, we verify that BigMaC can significantly save table space and reduce update complexity compared to prior proposals.

Scalability and reliability are among the main concerns in large-scale Software Defined Networking (SDN) application scenarios. A common approach is to use multiple distributed controllers, each managing one static partition of the network. In this paper, we show that dynamic mapping can improve efficiency in managing traffic load variations. We then propose BalCon (Balanced Controller): an algorithmic solution designed to tackle and reduce the load imbalance among SDN controllers through proper SDN switch migrations. Simulations demonstrate that BalCon is lightweight from the computational point of view and reduces the load imbalance among SDN controllers (expressed as variance) by 40% by migrating only a small number of switches. We also built a realistic prototype of SDN controller, BalConController, based on the open-source SDN framework RYU.

Emerging commercial live content broadcasting platforms are facing great challenges to accommodate large scale dynamic viewer populations. Existing solutions constantly suffer from balancing the cost of deploying at the edge close to the viewers and the quality of content delivery. We propose LiveJack, a novel network service to allow CDN servers to seamlessly leverage ISP edge cloud resources. LiveJack can elastically scale the serving capacity of CDN servers by integrating Virtual Media Functions (VMF) in the edge cloud to accommodate flash crowds for very popular contents. LiveJack introduces minor application layer changes for streaming service providers and is completely transparent to end users. We have prototyped LiveJack in both LAN and WAN environments. Evaluations demonstrate that LiveJack can increase CDN server capacity by more than six times, and can effectively accommodate highly dynamic workloads with an improved service quality.

Power-efficient Data Center Networks (DCNs) have been proposed to save power of DCNs using OpenFlow. In these DCNs, the OpenFlow controller adaptively turns on and off links and OpenFlow switches to form a minimum-power subnet that satisfies traffic demand. As the subnet changes, flows are scheduled dynamically to routes composed of active switches and links. However, existing flow scheduling schemes could cause undesired results: (1) power inefficiency: due to unbalanced traffic allocation on active routes, extra switches and links may be activated to cater to bursty traffic surges on congested routes, and (2) Quality of Service (QoS) fluctuation: because of the limited flow entry processing ability, switches cannot timely install/delete/update flow entries to properly schedule flows. In this paper, we propose AggreFlow, a dynamic flow scheduling scheme that achieves power efficiency in DCNs and improved QoS using two techniques: Flow-set Routing and Lazy Rerouting. Flow-set Routing achieves load balancing and reduces the number of entry installment on switches by routing flows in a coarse-grained flow-set fashion. Lazy Rerouting maintains load balancing and spreads rerouting operations over a relatively long period of time, reducing the burstiness of entry installment/deletion/update on switches. We built a NS3 based fat-tree network simulation platform to evaluate AggreFlow's performance. The simulation results show AggreFlow reduces power consumption by about 18%, achieves load balancing and improved QoS (i.e., low packet loss rate and reducing the number of processing entries for flow scheduling by 98%), compared with baseline schemes.

Packet classification is one of the major challenges today in designing high-speed routers and firewalls, as it involves sophisticated multi-dimensional searching. Ternary content addressable memory (TCAM) has been widely used to implement packet classification, thanks to its parallel search capability and constant processing speed. However, TCAMs have limitations of high cost and high power consumption, which ignite the desire to reduce TCAM usage. Recently, many works have been presented on this subject due to two opportunities. One is the well-known range expansion problem for packet classifiers to be stored in TCAM entries. The other is that there often exists redundancy among rules. In this paper, we propose a novel technique called Block Permutation (BP) to compress the packet classification rules stored in TCAMs. Unlike previous schemes that compress classifiers by converting the original classifiers to semantically equivalent classifiers, the BP technique innovatively finds semantically nonequivalent classifiers to achieve compression by performing block-based permutations on the rules represented in Boolean Space. We have developed an efficient heuristic approach to find permutations for compression and have designed its hardware implementation by using a field-programmable gate array (FPGA) to preprocess incoming packets. Our experiments with ClassBench classifiers and Internet Service Provider (ISP) real-life classifiers show that the proposed BP technique can significantly reduce 31.88% TCAM entries on average, in addition to the reduction contributed by other state-of-the-art schemes.

Providing well-satisfactory multi-party video conferencing service is remarkably challenging, which demands not only high bandwidth but also low latency. Current commercial implementations typically use one or multiple multipoint control units (MCUs) as the central points for distributing video bit-streams to all participants in the conferencing session. Such MCU-based solution has limited control on quality of service (QoS), which may cause large delay, single-point malfunction and communication bottleneck for entire system. Recent years have witnessed the emergence of a new paradigm in networking, software defined networking (SDN), which advocates separating data plane and control plane, making network switches in the data plane simple packet forwarding devices and leaving a logically centralized controller to manipulate network behaviors. SDN provides the flexibility of changing underlying infrastructure and makes it possible to radically provide service/flow-aware QoS guarantee. In this paper, we propose a novel architecture for multi-party video conferencing by utilizing SDN-enabled multicasting, where SDN controller helps media controller to buildup multicast trees for video flows originated at video parties. To realize the architecture, we correspondingly propose a novel multicast construction and packing method, in which multiple source-based multicast trees are constructed and integrated to maximize system-wide utility while guaranteeing an end-to-end delay bound. Extensive simulations demonstrate that it could provide better video delivery compared to the conventional MCU-based solution in terms of video rate and delay in both sparsely and densely distributed networks.

Many applications (e.g., cluster based storage and MapReduce) in modern data centers require a high fan-in, many-to-one type of data communication (known as TCP incast), which could cause severe incast congestion in switches and result in TCP goodput collapse, substantially degrading the application performance. The root cause of such a collapse is the long idle period of the Retransmission Timeout (RTO) that is triggered at one or more senders by packet losses in congested switches. In this paper we develop a packet labelling scheme PLATO, which improves the loss detection capabilities of NewReno using an innovative packet labelling system. Packets carrying this special label are preferentially enqueued, at the switch. This allows TCP to detect packet loss using three duplicate acknowledgements, instead of the time expensive RTO; thus avoiding the goodput collapse. PLATO makes minor modifications to NewReno and does not alter its congestion control mechanism. The implementation and simulations have been done in Network Simulator 3 (NS3). PLATO's performance is significantly better than NewReno as well as state-of-art incast solutions Incast Control TCP (ICTCP) and Data Center TCP (DCTCP). We also show that TCP PLATO can be implemented using commodity switches with Weighted Random Early Detection (WRED) function.

String matching is a key technique for network security applications such as network intrusion detection systems and antivirus scanners, where the payload of every packet is inspected against thousands of patterns in real time. As the transmission rate of Internet links is getting higher and higher, the speed of matching engines is required to be faster and faster. Existing deterministic finite automaton (DFA)-based approaches achieve high throughput at the expense of extremely expensive memory cost; therefore, they are not suitable for the scenarios where only limited on-chip memory resources are available. To achieve fast matching speed while controlling memory expense, in this paper, we propose Kangaroo, a compact string matching scheme that scans multiple characters each time by running multiple small-sized finite state machines in parallel. Specifically, Kangaroo processes k consecutive characters mostly in one cycle by accessing k different memories in parallel, where k is a predefined factor that can be tuned based on the requirement of applications. Kangaroo is memory efficient. Experimental evaluations on Snort and ClamAV rule sets show that a tenfold increase in speed can be practically achieved by a single Kangaroo matching engine with a reduced memory cost comparing with the state-of-the-art DFA-based approaches.

Deterministic finite automatons (DFAs) and nondeterministic finite automatons (NFAs) are two typical automatons used in the network intrusion detection system. Although they both perform regular expression matching, they have quite different performance and memory usage properties. DFAs provide fast and deterministic matching performance but suffer from the well-known state explosion problem. NFAs are compact, but their matching performance is unpredictable and with no worst case guarantee. In this paper, we propose a new automaton representation of regular expressions, called tunable finite automaton (TFA), to deal with the DFAs' state explosion problem and the NFAs' unpredictable performance problem. Different from a DFA, which has only one active state, a TFA allows multiple concurrent active states. Thus, the total number of states required by the TFA to track the matching status is much smaller than that required by the DFA. Different from an NFA, a TFA guarantees that the number of concurrent active states is bounded by a bound factor b that can be tuned during the construction of the TFA according to the needs of the application for speed and storage. Simulation results based on regular expression rule sets from Snort and Bro show that, with only two concurrent active states, a TFA can achieve significant reductions in the number of states and memory usage, e.g., a 98% reduction in the number of states and a 95% reduction in memory space.

The emergence of new network applications, such as the network intrusion detection system and packet-level accounting, requires packet classification to report all matched rules instead of only the best matched rule. Although several schemes have been proposed recently to address the multimatch packet classification problem, most of them require either huge memory or expensive ternary content addressable memory (TCAM) to store the intermediate data structure, or they suffer from steep performance degradation under certain types of classifiers. In this paper, we decompose the operation of multimatch packet classification from the complicated multidimensional search to several single-dimensional searches, and present an asynchronous pipeline architecture based on a signature tree structure to combine the intermediate results returned from single-dimensional searches. By spreading edges of the signature tree across multiple hash tables at different stages, the pipeline can achieve a high throughput via the interstage parallel access to hash tables. To exploit further intrastage parallelism, two edge-grouping algorithms are designed to evenly divide the edges associated with each stage into multiple work-conserving hash tables. To avoid collisions involved in hash table lookup, a hybrid perfect hash table construction scheme is proposed. Extensive simulation using realistic classifiers and traffic traces shows that the proposed pipeline architecture outperforms HyperCuts and B2PC schemes in classification speed by at least one order of magnitude, while having a similar storage requirement. Particularly, with different types of classifiers of 4K rules, the proposed pipeline architecture is able to achieve a throughput between 26.8 and 93.1 Gb/s using perfect hash tables.

An important challenge of running large-scale cloud services in a geo-distributed cloud system is to minimize the overall operating cost. The operating cost of such a system includes two major components: electricity cost and wide-area-network (WAN) communication cost. While the WAN communication cost is minimized when all virtual machines (VMs) are placed in one datacenter, the high workload at one location requires extra power for cooling facility and results in worse power usage effectiveness (PUE). In this paper, we develop a model to capture the intrinsic trade-off between electricity and WAN communication costs, and formulate the optimal VM placement problem, which is NP-hard due to its binary and quadratic nature. While exhaustive search is not feasible for large-scale scenarios, heuristics which only minimize one of the two cost terms yield less optimized results. We propose a cost-aware two-phase metaheuristic algorithm, Cut-and-Search, that approximates the best trade-off point between the two cost terms. We evaluate Cut-and-Search by simulating it over multiple cloud service patterns. The results show that the operating cost has great potential of improvement via optimal VM placement. Cut-and-Search achieves a highly optimized trade-off point within reasonable computation time, and outperforms random placement by 50%, and the partial-optimizing heuristics by 10-20%.

Saving power in datacenter networks has become a pressing issue. While in operation, ElasticTree and CARPO can save power consumed by a fat-tree network by using sleep mode where some components such as ports and switches are turned off when traffic demand in the network is relatively moderate. In this paper, we propose a new approach by exploring the design stage of a datacenter network and focus on how to choose the right switch size that can potentially save the most power during the expected operation of the network. We also consider speed scaling where the power of a switch can be varied by adjusting its processing rate according to its traffic demand. We use analysis and simulation to investigate the power-saving performance of different switch sizes, power-saving modes and traffic demand patterns. Our findings with sleep mode reveal that deploying a large number of small switches is more power-efficient than a small number of large switches when the traffic demand is relatively moderate or when servers exchanging traffic are in close proximity. With speed scaling, the reverse is generally true.

One of the challenging problems for multi-stage buffered switching is the performance degradation due to the saturation tree congestion inside the switch when traffic destined for some output ports exceeds their link capacity (i.e., hotspots) and blocks other traffic destined for non-overloaded output ports. In previous work [18], we have proposed HOPE, an effective congestion control scheme, in the 3-stage Clos Network on Chip (NOC). HOPE proactively regulates traffic destined for each output by estimating the number of their backlogged packets in the network and applying a simple stop-and-go mechanism to prevent hotspot traffic from jamming the internal links between the stages. The effectiveness of HOPE in NOC has motivated us to apply it in the multistage buffered switches. Different from an NOC, where Switch Modules (SMs) are all on the single chip, the SMs in a multi-stage buffered switch are separated from each other for a distance up to 100 m. This significantly increases the hardware complexity of HOPE. In this paper, we address the implementation challenges when applying HOPE in the 3-stage Clos network switch. In particular, we propose a scalable traffic measurement mechanism to approximate the backlogged traffic for each output port by taking advantage of the property of Clos network that traffic is evenly distributed among central SMs. We also design an efficient messaging system to notify input sources upon congestion status updates. Simulation results with different traffic patterns show that HOPE can isolate hotspot traffic from non-hotspot traffic, achieve max-min fairness among different traffic types, and provide low latency for non-hotspot traffic and high throughput for hotspot traffic.

Packet classification is one of the major challenges in designing high-speed routers and firewalls as it involves sophisticated multi-dimensional searching. Ternary Content Addressable Memory (TCAM) has been widely used to implement packet classification thanks to its parallel search capability and constant processing speed. However, TCAM-based packet classification has the well-known range expansion problem, resulting in a huge waste of TCAM entries. In this paper, we propose a novel technique called Block Permutation (BP) to compress the packet classification rules stored in TCAMs. The compression is achieved by performing block-based permutations on the rules represented in Boolean Space. We develop an efficient heuristic approach to find the permutations for compression and design its hardware implementation. Experiments on ClassBench classifiers and ISP classifiers show that the proposed BP technique can reduce TCAM entries by 53.99% on average.

Incast applications have grown in popularity with the advancement of data center technology. It is found that the TCP incast may suffer from the throughput collapse problem, as a consequence of TCP retransmission timeouts when the bottleneck buffer is overwhelmed and causes the packet losses. This is critical to the Quality of Service of cloud computing applications. While some previous literature has proposed solutions, we still see the problem not completely solved. In this paper, we investigate the three root causes for the poor performance of TCP incast flows and propose three solutions, one for each at the beginning, the middle and the end of a TCP connection. The three solutions are: admission control to TCP flows so that the flow population would not exceed the network's capacity; retransmission based on timestamp to detect loss of retransmitted packets; and reiterated FIN packets to keep the TCP connection active until the the termination of a session is acknowledged. The orchestration of these solutions prevents the throughput collapse. The main idea of these solutions is to ensure all the on-going TCP incast flows can maintain the self-clocking, thus eliminates the need to resort to retransmission timeout for recovery. We evaluate these solutions and find them work well in preventing the retransmission timeout of TCP incast flows, hence also preventing the throughput collapse.

Aho-Corasick (AC) automaton is widely used for multi-string matching in today's Network Intrusion Detection System (NIDS). With fast-growing rule sets, implementing AC automaton with a small memory without sacrificing its performance has remained challenging in NIDS design. In this paper, we propose a multi-dimensional progressive perfect hashing algorithm named P2-Hashing, which allows transitions of an AC automaton to be placed in a compact hash table without any collision. P2-Hashing is based on the observation that a hash key of each transition consists of two dimensions, namely a source state ID and an input character. When placing a transition in a hash table and causing a collision, we can change the value of a dimension of the hash key to rehash the transition to a new location of the hash table. For a given AC automaton, P2-Hashing first divides all the transitions into many small sets based on the two-dimensional values of the hash keys, and then places the sets of transitions progressively into the hash table until all are placed. Hash collisions that occurred during the insertion of a transition will only affect the transitions in the same set. The proposed P2-Hashing has many unique properties, including fast hash index generation and zero memory overhead, which are very suitable for the AC automaton operation. The feasibility and performance of P2-Hashing are investigated through simulations on the full Snort (6.4k rules) and Clam AV (54k rules) rule sets, each of which is first converted to a single AC automaton. Simulation results show that P2-Hashing can successfully construct the perfect hash table even when the load factor of the hash table is as high as 0.91.

Hotspot congestion control is one of the most challenging issues when designing a high-throughput low-latency network on the chip (NOC). When a destination node is overloaded, it starts pushing back the packets destined for it, which in turns blocks the packets destined for other nodes. How to detect the occurrence(s) of hotspot and notify all source nodes to regulate their traffic to the hotspot node(s) can be quite complex because of potentially high volume of information to be collected and the non-negligible latency between the detection point of congestion and the source nodes. In this paper, we propose an effective end-to-end flow control scheme, called HOPE (HOtspot PrEvention), to resolve the hotspot congestion problem for the Clos network on the chip (CNOC). Specifically, HOPE regulates the injected traffic rate proactively by estimating the number of packets inside the switch network destined for each destination and applying a simple stop-and-go protocol to prevent hotspot traffic from jamming the internal links of the network. We evaluate HOPE's overall performance and the required hardware. Extensive simulation results based on both static and dynamic hotspot traffic patterns confirm that HOPE can effectively regulate hotspot flows and improve system performance. Our hardware analysis shows that HOPE has very small logic overhead.

Today's file sharing networks are creating potential security problems to enterprise networks, i.e., the leakage of confidential documents. In order to prevent such leakage, we propose the Data Leakage Prevention System (DLPS) which is applied at the entrance of the enterprise network to filter out the outgoing sensitive information. The DLPS is based on a content scanning engine which defines a new type of matching problem, called longest overlap matching which also exits in many other applications as a basic problem where contents are delivered by small blocks. We study the problem by comparing it with the traditional pattern matching problem in Deep Packet Inspection (DPI) of Network Intrusion Detection Systems (NIDS) whose solutions are based on finite automata. We develop a new finite automata representation called Skip-Finite Automata (Skip-FA) which detects the packets carrying sensitive information by using default transitions to implicitly track the overlapping parts between packets' payloads and sensitive files. The simulation results shows that our system achieves a matching speed of about 10B+ per memory access for small file set (>;20KB) and 100B+ per memory access for large file set (>;2500KB). We also find that the memory consumption of Skip-FA is almost the same to that of the original files.

Multi-string matching is a key technique for implementing network security applications like Network Intrusion Detection Systems (NIDS). Existing DFA-based approaches always tradeoff between memory and throughput, and fail to has the best of both worlds. This paper extends the classic longest prefix principle from single-character to multi-character string matching and proposes a multi-string matching acceleration scheme named Independent Parallel Compact Finite Automata (PC-FA). In the scheme, DFA is divided into k PC-FAs, each of which can process one character from the input stream, achieving a speedup up to k with reduced memory occupation. Theoretical proof is given for the equivalency between traditional DFA and PC-FA approach. Experimental evaluations show that seven times of speedup can be practically achieved with a reduced memory size than up-to-date DFA-based compression approaches.

In Network Intrusion Detection System, De-terministic Finite Automaton (DFA) is widely used to compare packet content at a constant speed against a set of patterns specified in regular expressions (regex patterns). However, combining many regex patterns into a single DFA causes a serious state explosion. Partitioning the pat-tern set into several subsets, each of which produces a small DFA, is a practical way to deflate the state explosion. In this paper, we propose a regex pattern grouping scheme based on a new DFA model called Pattern-Based DFA (P-DFA) which supports efficient pattern-based op-erations, such as insertion, deletion, and etc. By using these basic operations, one can easily measure the state explo-sion when combining a set of regex patterns into a single DFA. Based on the privilege, we develop regex grouping algorithms for mitigating the state explosion in parallel and sequential matching environments, respectively. The evaluation shows that under the same constraints, our ap-proach requires only half the number of groups compared with the most well-known algorithms.

Deterministic Finite Automaton (DFA) is well-known for its constant matching speed in worst case, and widely used in multi-string matching, which is a critical technique in high performance Network Intrusion Detection System (NIDS) design. Existing DFA-based researches achieve high throughput at the expense of extremely high memory cost, so they fail to be used in situations like embedded systems where very tight memory resource is available. In this paper, we propose a memory-efficient multi-string matching acceleration scheme named Synergic Parallel Compact (SPC) Match Engine, which can provide a high matching speedup with no extra memory cost than the traditional DFA. Our scheme can be understood as consisting of k SPC-FAs, each of which can process one character from the input stream, causing achieving a constant speedup factor k with reduced memory occupation. Experimental evaluations with Snort and ClamAV rulesets show that a speedup of 9X can be practically achieved by a single SPC Match Engine instance with a reduced memory size than the up-to-date DFA-based compression approaches.

The emergence of new network applications like network intrusion detection system, packet-level accounting, and load-balancing requires packet classification to report all matched rules, instead of only the best matched rule. Although several schemes have been proposed recently to address the multi-match packet classification problem, most of them require either huge memory or expensive Ternary Content Addressable Memory (TCAM) to store the intermediate data structure, or suffer from steep performance degradation under certain types of classifiers. In this paper, we decompose the operation of multi-match packet classification from the complicated multi-dimensional search to several single-dimensional searches, and present an asynchronous pipeline architecture based on a signature tree structure to combine the intermediate results returned from single-dimensional searches. By spreading edges of the signature tree in multiple hash tables at different stages of the pipeline, the pipeline can achieve a high throughput via the inter-stage parallel access to hash tables. To exploit further intra-stage parallelism, two edge-grouping algorithms are designed to evenly divide the edges associated with each stage into multiple work-conserving hash tables with minimum overhead. Extensive simulation using realistic classifiers and traffic traces shows that the proposed pipeline architecture outperforms HyperCut and B2PC schemes in classification speed by at least one order of magnitude, while with a similar storage requirement. Particularly, with different types of classifiers of 4K rules, the proposed pipeline architecture is able to achieve a throughput between 19.5 Gbps and 91 Gbps.

Switch-Memory-Switch (SMS) architecture exhibits an excellent performance due to its emulating the Output Queueing structure. However, in order to achieve the maximal matching, the first stage scheduling operates at a huge computational complexity, which blocks the SMS from practical implementation. In order to put SMS into more effective industrial applications, especially in super-large size switches/routers with multi-services environment, two parallel iterative scheduling algorithms, named IS-RRM and AIS-RRM respectively, are proposed in this paper. The algorithms abolish totally the traditional departure-time-compatible (DTC) graph, and by using iteration-sharing technology, greatly reduce the required iteration number in each time slot. Using a discrete-time Markov chain to model the AIS-RRM algorithm, we obtain its upper bound of cell loss rate. Meanwhile, experimental and theoretical results show that so long as the number of shared memories is twice the switch size, AIS-RRM algorithm can achieve a cell loss rate of 10 when the input buffer size is 15 and the iteration number of each time slot is 6, despite the arrival traffic pattern and the switch size. Furthermore, the iteration number required in each time slot can be further decreased by increasing the input buffer size.

Emulating Output Queued (OQ) Switch with sustainable implementation cost and low fixed delay is always preferable in designing high performance routers. The Switch-Memory-Switch (SMS) router, also called Distributed Shared Memory (DSM) Switch, provides a possible way towards practically emulating OQ in backbone switches. However, the architectures and algorithms for SMS switches ever proposed are either unpractical or only supporting First-Come-First-Serve (FCFS) scheduling policy, which cannot support QoS and is unfair for light traffic flow. Our improved SMS architecture and algorithm aim at emulating Push-In-First-Out (PIFO) OQ. We employ a randomly-dispatching first stage and resolve memory access conflictions on the second stage of the switch through a probabilistic matching method, at the cost of fixed delay and sufficiently low cell loss probability (PCLP). The relative fixed delay of our algorithms for an NXN switch is composed of two parts: N and (-3/2log2PCLP), which result from the pipelined scheduling process and probabilistic method, respectively. Moreover, both the total memory and fabric bandwidth of our architecture implemented on crossbar could be lowered to only 2NR, where R is line rate, counting read and write separately.

For a combined input and output queued (CIOQ) switch, maximal matching (MM) algorithm with a speedup of 2 has been known to deliver 100% throughput under any admissible traffic, where in each time slot, two independent schedulings and two cell transferrings are made respectively. This paper proposes a new kind of extended maximal matching (EMM) algorithm, which just utilizes a little information of VOQ length. We show that the implementation complexity of CIOQ switches is reduced by using the EMM(2) algorithm, where only one scheduling and two cell transferrings (data speedup of 2) are necessary in each time slot to achieve 100% throughput when input traffic is admissible. The EMM(2) algorithm can be easily realized by modifying the existing MM algorithms. In this paper, we provide a practical instance of EMM(2) algorithm, named EiSLIP(1,2), based on the well-known iSLIP algorithm. Simulations show that EiSLIP(1,2) algorithm with a data speedup of 2 achieves almost the same delay performance as output queued policy under uniform and non-uniform traffic with Bernoulli arrival, as well as the bursty traffic.

Although output queued (OQ) switches are prominent for their high performance, they are not easy to implement due to the high speedup requirement. Using a special scheduling algorithm in the first stage switch, a more scalable switch-memory-switch (SMS) architecture can emulate an OQ switch, where cells must be transferred from the inputs to the shared memories per time slot without arrival and departure conflicts. Although scheduling algorithm achieves good performance, the time complexity for constructing the bipartite graph is too high to be used in practice. In this paper, we propose a new iterative random round-Robin matching (iRRM) algorithm together with its constrained version CiRRM, where no bipartite graph is required to be constructed in advance to solve the departure conflict, and thus high computation overhead is avoided. In our algorithms, both the arrival and the departure conflicts are melted in the iterations. Each iterations consist of two steps: request step and grant step, where randomness and more easily implemented round-robin principle are used respectively. Through theoretical analysis, we obtain that with M=2/spl phi/(N-1) shared memories, where N is the port number and /spl phi/ is a constant larger than (2N-1)/(2N-2), iRRM/CiRRM can complete a matching within O(logM) iterations with high probability in M and the time complexity of CiRRM is only O(log/sup 2/M/loglogM), which is much lower than prior algorithms.