Packet-level network simulation provides high-fidelity modeling but suffers from severe scalability bottlenecks. Existing scaling approaches remain inefficient for modern data-center and AI-training networks. Spatial parallelism requires substantial hardware resources, while temporal-skipping approaches become less effective under bursty traffic. We observe that homogeneous data-center deployments introduce substantial execution redundancy during simulation.

This paper presents EmuFork, a novel emulation paradigm that eliminates redundant initialization by mimicking OS-level fork semantics. EmuFork captures the post-initialization state of a single template router and rapidly restores all subsequent instances from this shared snapshot via Copy-on-Write. By bypassing redundant computations and resolving cloning conflicts, EmuFork accelerates large-scale emulation by up to 86% and reduces peak memory usage by up to 30%.

Data compression techniques significantly improve storage efficiency, bandwidth utilization, and energy efficiency, yet they introduce challenges for the rapid browsing and retrieval of valuable information within compressed data. Existing approaches achieve high-speed, lossless matching by exploiting the context-free property of automata. However, they are constrained by the recursive reference structures in compressed data, which necessitate state copying to ensure matching safety.

Abstract Configurations of routing protocols in wide area networks (WANs) are highly sophisticated and prone to bugs, leading to severe network outages and security breaches. SMT-based network verification can assist operators in checking the configurations, but it still faces scalability challenges when reasoning about failures: to check whether a property holds when no more than k links fail, a verifier needs to explore a tremendous space of failure scenarios. To this end, this paper proposes VeriBoost , a method that can leverage the topology features of WANs to reduce the space of failure scenarios, thereby improving the scalability of SMT-based verification on WANs. VeriBoost achieves the reduction by pruning links that are irrelevant to a property, and compressing multiple links whose failures have an equivalent impact on the property. Experiments on real WAN topologies show that it speeds up SMT-based verification by 2–47 $$\times $$ × .

Network specification, which describes what an existing network is designed for, can help operators better understand and manage their networks, and is a critical pre-condition for network verification and synthesis tools to work. Existing tools for specification mining either cannot scale to large networks, or scale by sacrificing fidelity. Moreover, the specification contains a huge number of low-level intents (e.g., tens of thousands of pairwise reachability), making it hard for operators to read. To this end, this paper presentsNetMiner, which can mine specification from network configurations, with high scalability, fidelity, and easier to read. The key idea ofNetMineris to faithfully simulate the network routing and forwarding behaviors with control plane simulators and data plane verifiers, so as to achieve high fidelity. Meanwhile,NetMinerimproves the scalability by identifying relevant failure scenarios, and aggregating them to significantly reduce the number of needed simulations. Moreover,NetMinerclusters similar low-level intents into a high-level intent, to make the specification more concise and easier to read. Experiments using real configurations from a large cloud service provider and synthetic configurations show thatNetMinercan mine specification$10\times $faster, and reduce the number of intents by$100\times $, compared to state-of-the-art tools.

In datacenters, lossless network is very attractive as it can achieve ultra-low latency. In commodity Ethernet, lossless forwarding is achieved by hop-by-hop Priority-based Flow Control (PFC). To avoid buffer overflow, PFC-enabled switches need to reserve some buffer asheadroom, absorbing in-flight packets during the delay for backpressure messages to take effect. However, with the growing link speed in production networks, the buffer becomes increasingly insufficient, and the headroom can occupy a considerable fraction of buffer. As a result, the remaining buffer for absorbing normal traffic bursts is significantly squeezed, leading to frequent PFC messages that degrade the network performance. Worse yet, we find that the current static and queue-independent headroom allocation scheme is quite inefficient, resulting in significant buffer wastage. In light of this, we propose Dynamic and Shared Headroom allocation scheme (DSH), which dynamically allocates headroom to congested queues and enables sharing of allocated headroom among different queues. To achieve this, DSH first introduces port-level flow control, which performs flow control at the granularity of individual ports, guaranteeing lossless forwarding with a small fraction of per-port headroom. With this lossless guarantee, the switch is liberated for dynamic headroom adjustment. DSH dynamically allocates per-queue headroom based on the congestion status of each queue. Meanwhile, DSH preserves the queue-level flow control to protect the non-congested queues from being paused by congested queues, ensuring performance isolation on buffer sharing. Extensive experiments show that DSH can reduce the flow completion time by up to ~78.8%.

Today's high-speed switches employ an on-chip shared packet buffer. The buffer is becoming increasingly insufficient as it cannot scale with the growing switching capacity. Nonetheless, the buffer needs to face highly intense bursts and meet stringent performance requirements for datacenter applications. This imposes rigorous demand on the Buffer Management (BM) scheme, which dynamically allocates the buffer across queues. However, the de facto BM scheme, designed over two decades ago, is ill-suited to meet the requirements of today's network.

It is observed that the bottleneck in distributed training has shifted from computation to communication due to contention in concurrent transmissions and substantial redundant traffic. In the Parameter Server (PS) architecture, the server aggregates gradients from multiple workers and then distributes updated model parameters back to the workers in a one-to-many manner. Currently, model parameters are distributed via unicast, sending multiple identical copies of the data, which leads to significant bandwidth waste. Although multicast can save bandwidth, current approaches have two main drawbacks: on one hand, many protocols require maintaining excessive multicast state inside the network; on the other hand, the lack of coordination among multiple multicast trees can still lead to path conflicts. In this work, we propose path-aware multicast, which includes innetwork multicast tree reservation and per-hop control multicast. Specifically, before each round of model parameter distribution, the server queries the network for a multicast tree that satisfies the bandwidth requirement. The calculated multicast tree is then returned with bandwidth reserved at its tree nodes. Next, model parameters are forwarded with hop-by-hop control along the multicast tree. After the multicast is completed, the reserved network resources are released. Our evaluation shows that in an$8 \times 8$spine-leaf topology, path-aware multicast improves link load balancing by 32.6 % compared to random multicast and accelerates model parameter distribution by up to nearly$N \times$compared to unicast, where$N$is the number of workers.

Network configuration verifiers can proactively reason about a network's correctness to prevent network outages. However, even recent efforts have proposed algorithms to "scale up" the verification to several thousand switches, these algorithms still cannot be used for networks with more than 10K switches or 1000M routes, which is common for large service providers. In this paper, instead of further scaling up the verification limited to a single server, we study how to "scale out" the verification using the resources of multiple servers. To achieve this, we propose S2, a distributed verifier for network configurations. S2 partitions the network model and distributes the verification tasks, i.e., control plane simulation and data plane verification, to run on multiple servers in parallel. Additionally, S2 uses prefix sharding during control plane simulation to further reduce the memory footprint on each server. We implement a prototype of S2 based on Batfish, the state-of-the-art network verifier. Based on real datacenter topologies of a large service provider and synthetic FatTree topologies, we show that S2 can verify networks with 10K routers and 1000M routes within 2 hours.

This paper introduces Galvatron, a domain-specific language designed to simplify transport layer programming. Galvatron obscures the underlying data structures and operations, and exposes parametric processing stages to the developer, thus significantly reducing coding effort. Our evaluation demonstrate Galvatron’s ability to encapsulate complex semantics of 4 real-world transport protocols using merely 2% of the code compared to native implementations.

Migrating enterprise IT services to the cloud is becoming a trend. However, configuring virtual networks in the cloud is a costly and error-prone task. In this paper, we model the problem of VPC intent compilation and prove that the problem is NP-hard. We design a heuristic method to automatically translate the intents into VPC configurations. To facilitate the heuristic, we propose an algorithm for finding small cuts (AFSC) based on the Louvain algorithm, which is used to separate subnets across VPCs. The generated configurations find an equilibrium between maximizing the network performance and minimizing the resource consumption. Experimental results show that our heuristic method reaches 100% correctness, compiles large intent sets from real-world networks with hundreds of subnets and thousands of intents in under a minute, and improves the effectiveness by ∼2.8× in terms of resource consumption relative to network performance.

Middleboxes are becoming indispensable in modern networks. However, programming the network stack of middleboxes to support emerging transport protocols and flexible stack hierarchy is still a daunting task. To this end, we propose Rubik, a language that greatly facilitates the task of middlebox stack programming. Different from existing hand-written approaches, Rubik offers various high-level constructs for relieving the operators from dealing with massive native code, so that they can focus on specifying their processing intents. We show that using Rubik one can program the middlebox stack with minor effort, e.g., 250 lines of code for a complete TCP/IP stack, which is a reduction of 2 orders of magnitude compared to the hand-written versions. To maintain a high performance, we conduct extensive optimizations at the middle-and back-end of the compiler. Experiments show that the stacks generated by Rubik outperform the mature hand-written stacks by at least 30% in throughput.

Traffic policing is widely used by ISPs to limit their customers’ traffic rates. It has long been believed that a well-tuned traffic policer offers a satisfactory performance for TCP. However, we find this belief breaks with the emergence of new congestion control (CC) algorithms: flows using new CC algorithms can easily occupy the majority of bandwidth, starving traditional TCP flows. We confirm this problem with experiments and reveal its root cause as follows. Without a buffer in traffic policers, congestion only causes packet losses, while new CC algorithms are loss-resilient. When being policed, they will not reduce the sending rate until an unacceptable loss ratio for TCP is reached, resulting in low throughput for competing TCP flows. Simply adding a buffer to the traffic policer improves fairness but incurs high latency. To this end, we propose FairPolicer, which can achieve fair bandwidth allocation without sacrificing latency. FairPolicer regards a token as a basic unit of bandwidth and fairly allocates tokens to active flows in a round-robin manner. To avoid bandwidth waste when flows come and go, FairPolicer puts all available tokens in a global bucket and maintains the amount of residual bucket space rather than the number of available tokens. To scale to massive concurrent flows, FairPolicer uses a Count-Min Sketch structure to maintain per-flow data with a small memory footprint. Testbed experiments show that FairPolicer can allocate bandwidth in a max-min fair manner and achieve much lower latency than other kinds of rate limiters.

In datacenters, lossless network is very attractive as it can achieve ultra-low latency. In commodity Ethernet, lossless forwarding is achieved by hop-by-hop Priority-based Flow Control (PFC). To avoid buffer overflow, PFC-enabled switches need to reserve some buffer as headroom, which is for absorbing in-flight packets during the delay for backpressure messages to take effect. However, with the growing link speed in production networks, the buffer becomes increasingly insufficient, and the headroom can occupy a considerable fraction of buffer. As a result, the remaining buffer for absorbing normal traffic bursts is significantly squeezed, leading to frequent PFC messages that degrade the network performance. However, the current static and queue-independent headroom allocation scheme is inherently inefficient in solving this problem. In light of this, we propose Dynamic and Shared Headroom allocation scheme (DSH), which dynamically allocates headroom to congested queues and enables the allocated headroom to be shared among different queues. By statistical multiplexing, DSH needs much less headroom to ensure lossless forwarding. Furthermore, DSH can be implemented on switching chips with moderate modifications. Extensive simulations show that DSH can absorb 4× more bursts without triggering PFC messages and reduce the flow completion time by up to ~31%.

Traffic shaping is a common function at end hosts. Compared with hardware ones, software shapers are more flexible to be developed and deployed, and thus are very attractive. Nevertheless, software approaches are still unsatisfactory as they struggle to saturate 40Gbps and higher speed.While much effort has been made to reduce the intrinsic overhead of software traffic shaping, we find that it is the extrinsic overhead, such as PCIe communications and interrupts, that hinders shaping from achieving 40Gbps - 100Gbps speed. Batching is an effective way to amortize these overheads. However, blindly batching can degrade the network performance, as it introduces bursts into the network. Diving into the dilemma, we find that intra-flow burst is to blame for harming the network performance, while inter-flow burst, consisting of packets from different flows, can be naturally demultiplexed in the network.Based on the insight, we present FlowBundler, which can achieve efficient traffic shaping by inter-flow batching. Testbed experiments show that FlowBundler can achieve an accurate shaping of 98Gbps with a single CPU core, which is 2.6× better than state-of-the-art approaches. Large-scale simulations show that FlowBundler can batch packet transmissions without harming the network performance.

Network programming languages (NPLs) empower operators to program network data planes (NDPs) with unprecedented efficiency. Currently, various NPLs and NDPs coexist and no one can prevail over others in the short future. Such diversity is raising many problems including: (1) programs written with different NPLs can hardly interoperate in the same network, (2) most NPLs are bound to specific NDPs, hindering their independent evolution, and (3) compilation techniques cannot be readily reused, resulting in much wasteful work. These problems are mostly owing to the lack of modularity in the compilers, where the missing part is an intermediate representation (IR) for NPLs. To this end, we proposeNetwork Transaction Automaton (NTA), a highly-expressive and language-independent IR, and show it can express semantics of 7 mainstream NPLs. Then, we designCODER, a modular compiler based on NTA, which currently supports 2 NPLs and 3 NDPs. Experiments with real and synthetic programs show CODER can correctly compile those programs for real networks within moderate time.

Botnets are the machines that increasingly controlled by cybercriminals to perform various attacks. They use Domain Generation Algorithm (DGA) to frequently generate their illegitimate domains for preventing detection. To overcome such dynamics, existing solutions try to capture the characteristics of domain names, such that the automatically generated domains can be identified. However, those solutions are not conformed to the linguistic conventions of reading and writing. For a comprehensive understanding of strings of domain names, we present DOmain Linguistic PHonIcs detectioN (DOLPHIN), a novel method that can detect the illegitimate domain names generated by DGAs. Considering the correspondence between pronunciations and spellings, we design the DOLPHIN patterns. They are the classification of vowels and consonants in variable lengths as follow the principles of phonics. DOLPHIN recognizes strings of domain names and reconstructs them with the components of variable-length vowels and consonants following the DOLPHIN patterns. We implement the features used DOLPHIN in supervised learning methods and compare them to the fore-most method FANCI. Experimental results show that, compared to FANCI with RFs, DOLPHIN can achieve higher detection accuracy of 0.0238 in average with lower FPR without much overhead.

Visibility is essential for operating and troubleshooting intricate networks. In-band Network Telemetry (INT) has been embedded in the latest merchant silicons to offer high-precision device and traffic state visibility. INT is actually an underlying technique and each INT instance covers only one monitoring path. The network-wide measurement coverage therefore requires a high-level orchestration to provision multiple INT paths. An optimal path planning is expected to produce a minimum number of paths with a minimum number of overlapping links. Eulerian trail has been used to solve the general problem. However, in production networks, the vantage points where one can deploy probes to start and terminate INT paths are constrained. In this work, we propose an optimal path planning algorithm, INT-probe, which achieves the network-wide telemetry coverage under the constraint of stationary probes. INT-probe formulates the constrained path planning into an extended multi-depot k-Chinese postman problem (MDCPP-set) and then reduces it to a solvable minimum weight perfect matching problem. We analyze algorithm's theoretical bound and the complexity. Extensive evaluation on both wide area networks and data center networks with different scales and topologies are conducted. We show INT-probe is efficient, high-performance, and practical for real-world deployment. For a large-scale data center networks with 1125 switches, INT-probe can generate 112 monitoring paths (reduced by 50.4 %) by allowing only 1.79% increase of the total path length, promptly resolving link failures within 744.71ms.

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.

Traffic policing is widely used by ISPs to limit their customers' traffic rates. It has long been believed that a well-tuned traffic policer offers a satisfactory performance for TCP. However, we find this belief breaks with the emergence of new congestion control (CC) algorithms like BBR: flows using these new CC algorithms can easily occupy the majority of the bandwidth, starving traditional TCP flows. We confirm this problem with experiments and reveal its root cause as follows. Without buffer in traffic policers, congestion only causes packet losses, while new CC algorithms are loss-resilient, i.e. they adjust the sending rate based on other network feedback like delay. Thus, when being policed they will not reduce the sending rate until an unacceptable loss ratio for TCP is reached, resulting in low throughput for TCP. Simply adding buffer to the traffic policer improves fairness but incurs high latency. To this end, we propose FairPolicer, which can achieve fair bandwidth allocation without sacrificing latency. FairPolicer regards token as a basic unit of bandwidth and fairly allocates tokens to active flows in a round-robin manner. Testbed experiments show that FairPolicer can significantly improve the fairness and achieve much lower latency than other kinds of rate-limiters.

Information-Centric Networking (ICN) provides scalable and efficient content distribution at the Internet scale due to in-network caching and native multicast. To support these features, a content router needs high performance at its data plane, which consists of three forwarding steps: checking the Content Store (CS), then the Pending Interest Table (PIT), and finally the Forwarding Information Base (FIB). In this work, we build an analytical model of the router and identify that CS is the actual bottleneck. Then, we propose a novel mechanism called “NB-Cache” to address CS’s performance issue from a network-wide point of view. In NB-Cache, when packets arrive at a router whose CS is fully loaded, instead of being blocked and waiting for the CS, these packets are forwarded to the next-hop router, whose CS may not be fully loaded. This approach essentially utilizes Content Stores of all the routers along the forwarding path in parallel rather than checking each CS sequentially. NB-Cache follows a design pattern of on-demand load balancing and can be formulated into a non-trivial N-queue bypass model. We use the Markov chain to establish its theoretical base and find an algorithm for automated transition rate matrix generation. Experiments show significant improvement of data plane performance: 70% reduction in round-trip time (RTT) and 130% increase in throughput. NB-Cache decouples the fast packet forwarding from the slower content retrieval thus substantially reducing CS’s heavy dependency on fast but expensive memory.

A crucial requirement for Software Defined Network (SDN) is that data plane forwarding behaviors should always agree with control plane policies. Such requirement cannot be met when there areforwarding anomalies, where packets deviate from the paths specified by the controller. Most anomaly detection methods for SDN install dedicated rules to collect statistics of each flow, and check whether the statistics conform to the “flow conservation principle”. We find these methods have a limited detection scope: they look at one flow each time, thus can only check a small number of flows simultaneously. In addition, dedicated rules for statistics collection can impose a large overhead on flow tables of SDN switches. To this end, this paper presents FOCES, a network-wide forwarding anomaly detection and localization method in SDN. Different from previous methods, FOCES applies a new kind of flow conservation principle at network wide, and can check forwarding behaviors ofallflows in the network simultaneously, without installing any dedicated rules. Finally, FOCES applies a voting-based method to localize malicious switches when anomalies are detected. Experiments with four network topologies show that FOCES can achieve a detection precision higher than 90%, when the packet loss rate is no larger than 10%, and a localization accuracy of around 80% when the packet loss rate is no larger than 5%.

Network programming languages (NPLs) empower operators to program network data planes (NDPs) with unprecedented efficiency. Currently, various NPLs and NDPs coexist and no one can prevail over others in the short future. Such diversity is raising many problems including: (1) programs written with different languages can hardly interoperate in the same network, and (2) most NPLs are bound to specific NDPs, hindering their independent evolution. These problems are mostly owing to the lack of modularity in the compilers, where the missing part is an intermediate representation (IR) for NPLs. To this end, we propose Network Transaction Automaton (NTA), a highly-expressive and language-independent representation as the IR. We show that NTA can express semantics of 6 mainstream NPLs, and can be composed efficiently without any semantics loss.

Network programming languages (NPLs) empower operators to program network data planes (NDPs) with unprecedented efficiency. Currently, various NPLs and NDPs coexist and no one can prevail over others in the short future. Such diversity is raising many problems including: (1) programs written with different NPLs can hardly interoperate in the same network, (2) most NPLs are bound to specific NDPs, hindering their independent evolution, and (3) compilation techniques cannot be readily reused, resulting in much wasteful work. These problems are mostly owing to the lack of modularity in the compilers, where the missing part is an intermediate representation (IR) for NPLs. To this end, we propose Network Transaction Automaton (NTA), a highly-expressive and language-independent IR, and show it can express semantics of 7 mainstream NPLs. Then, we design CODER, a modular compiler based on NTA, which currently supports 2 NPLs and 3 NDPs. Experiments with real and synthetic network programs show CODER is efficient and scalable.

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

One major research challenge for Software-Defined Networking is to properly deploy and efficiently utilize multiple controllers to improve resource utilization and maintain high network performance. While addressing this Controller Placement Problem (CPP), many existing studies overlooked the importance and influence of the Controller Scheduling Problem (CSP) with the central focus on proper distribution of requests from all switches among all controllers. In this paper, we define a new Controller Placement and Scheduling Problem (CPSP), emphasizing on the necessity and importance of tackling both CPP and CSP simultaneously in a coherent framework. To solve CPSP, we must seek a combination of solutions to both problems. Particularly, CSP is addressed based on a given solution to CPP and a Gradient-Descent-based (GD-based) scheduling algorithm is developed to optimize the probabilistic distribution of requests among all controllers. Built on the GD-based approach for controller scheduling, a Clustering-based Genetic Algorithm with Cooperative Clusters (CGA-CC) is further proposed to address CPP. In comparison to the majority of heuristic methods developed in the past, CGA-CC has two unique strengths. Specifically, it partitions a large network to substantially reduce the search space of the Genetic Algorithm (GA), resulting in fast identification of high-quality CPP solutions. Moreover, a greedy load re-distribution mechanism is developed to handle unexpected demand variations by dynamically forwarding bursting requests to neighboring sub-networks. Extensive simulations showed that our algorithms can significantly outperform several existing algorithms, including a recently proposed approach called Multi-controller Selection and Placement Algorithm (MSPA), in terms of both response time and controller utilization.

Extracting fields from layer 7 protocols such as HTTP, known as L7 parsing, is the key to many critical network applications. However, existing L7 parsing techniques center around protocol specifications, thereby incurring large human efforts in specifying data format and high computational/memory costs that poorly scale with the explosive number of L7 protocols. To this end, this paper introduces a new framework namedcontent-based L7 parsing, where the content instead of the format becomes the first class citizen. Under this framework, users only need to label what content they are interested in, and the parser learns an extraction model from the users’ labeling behaviors. Since the parser is specification-independent, both the human effort and computational/memory costs can be dramatically reduced. To realize content-based L7 parsing, we propose REPLAY which builds on recurrent neural network (RNN) and addresses a series of technical challenges like large labeling overhead and slow parsing speed. We prototype REPLAY on GPUs, and show it can achieve a precision of 98% and a recall of 97%, with a throughput as high as 12Gbps for diverse extraction tasks.

Information-Centric Networking (ICN) provides scalable and efficient content distribution at the Internet scale due to its in-network caching and native multicast capabilities. To support these features, a content router needs high performance at its data plane, which consists of three forwarding steps: checking the Content Store (CS), then the Pending Interest Table (PIT), and finally the Forwarding Information Base (FIB). While prior works focus on performance optimization of a single step, we build an analytical model of content router's entire data plane and identify that CS is the actual bottleneck in the pipeline. Compared with PIT and FIB, CS is more challenging because it has more data to read/write, may have more entries in its table to store and lookup, and needs to organize content objects to sustain frequent cache replacement. Then, we propose a novel mechanism called "NB-Cache" to address CS's performance issue from a network-wide point of view rather than a single router's. In NB-Cache, when packets arrive at a router whose CS is fully loaded, instead of being blocked and waiting for the CS, these packets are forwarded to the next-hop router, whose CS may not be fully loaded. This approach essentially utilizes Content Stores of all the routers along the forwarding path in parallel rather than checking each CS sequentially. Our experiments show significant improvement of data plane performance: 70% reduction in round-trip time (RTT) and 130% increase in throughput.

A crucial requirement for Software Defined Network (SDN) is that data plane forwarding behaviors should always agree with control plane policies. Such requirement cannot be met when there are forwarding anomalies, where packets deviate from the paths specified by the controller. Most anomaly detection methods for SDN install dedicated rules to collect statistics of each flow, and check whether the statistics conform to the flow conservation principle. Such per-flow detection methods have a limited detection scope: they look at one flow each time, thus can only check a limited number of flows simultaneously. In addition, dedicated rules for statistics collection can impose a large overhead on flow tables of SDN switches. To this end, this paper presents FOCES, a network-wide forwarding anomaly detection method in SDN. Different from previous methods, FOCES applies a new kind of flow conservation principle at network wide, and can check forwarding behaviors of all flows in the network simultaneously, without installing any dedicated rules. Experiments show FOCES can achieve a detection precision higher than 90% for four network topologies, even when packet loss rates are as high as 10%.

Software Defined Network (SDN) enables flexible update of network functions with a well-defined abstraction between the control and the data plane. However, multiple active network functions with the same priority will potentially trigger conflicts among policies with overlapped flow space, causing the flow table explosion. In contrast to the local switch conflict resolution schemes proposed by previous works, this paper tackles the same problem from a different angle and resolves the policy conflict problem by coordinating all switches under a global centralized view. Specifically, we propose COnflict RAzor (CORA), which tremendously reduces the storage cost of conflicting policies leveraging the global network information obtained in the controller. The basic idea of CORA is migrating policies causing large explosions across the network if necessary, while keeping the semantics equivalence. We prove CORA's NP hardness and propose a heuristic to efficiently search a near-optimal policy migration strategy. Our experiments demonstrate that, CORA can effectively reduce the flow table storage occupation by at least 49% within less than 40 seconds.

Nowadays, Deep Packet Inspection (DPI) becomes a critical component of the network traffic detection applications. For comprehensive analysis of traffic, regular expression matching as the core technique of DPI is widely used. However, web services tend to compress their traffic for less data transmission, which challenges the regular expression matching to achieve wire-speed processing. In this paper, we propose Twins, a fast regular expression matching method over compressed traffic that leverages the returned states encoding in the compression to skip the bytes to be scanned. In our evaluation results, Twins can skip about 90% compression data and can achieve 1.5Gbps throughput, which gains 2.7~3.4 performance boost to the state-of-the-art work.

The prohibitive cost of deploying a sophisticated DNS-based CDN makes anycast-based CDN an attractive alternative for new or small CDN operators. In anycast-based CDNs, user requests are naturally routed to the “closest” server determined by Internet routing. For the operators, however, this comes at a cost—loss of control—how the traffic is routed is entirely at the mercy of BGP routing. The “closest” server may be overloaded, or simply not the best choice. This “loss of control” undermines thescalabilityof anycast-based CDN architectures. To have control over how traffic is routed, existing work either requires adding a large amount of complexity to the system (high Capex/Opex) or is unable to achieve precise and fine-grained control. This paper proposes T-SAC, a scalable anycast-based CDN architecture that capitalizes on the programmability and flexibility of SDN/NFV, enabling fine-grained traffic redirection among CDN servers. T-SAC achieves precise control by leveraging a load-based redirection algorithm and a single 1-bit no-redirect flag. We implement T-SAC in the real system and evaluate its performance from various aspects using DASH and web applications. The results show that T-SAC is capable of redirecting the right amount of traffic at the right time to the right servers, making the system highly scalable.

The reactive model of Software Defined Networking (SDN) invokes controller to dynamically determine the behaviors of a new flow without any pre-knowledge in the data plane. However, the reactive events raised by such flexible model meanwhile consume lots of the bottleneck resources of the fast memory in switch and bandwidth between controller and switches. To address this problem, we propose SoftRing with the motivation to mitigate the overhead to handle a reactive event. In fact, the reactive packets are not necessarily stored in the switch or sent to the controller; instead, they are forwarded to traverse a pre-defined loop path. The packets will finally leave the loop path after the switch rules related to the packet flow being updated to switches in the loop with fewer flow entries. We have implemented a SoftRing system that integrates the controller and software/hardware SDN switches. The results show that SoftRing can eliminate the fast memory requirement for reactive packets and reduce the control channel bandwidth consumption up to 80%, with the cost of less than 5% data plane bandwidth, an average of three extra flow entries in each switch, and minor extra latency for the flow forwarding.

Matching multiple patterns is the key technology in firewall, Intrusion Detection Systems, etc. However, most of the web services nowadays tend to compress their traffic for less transferring data and better user experience, which has challenged the multi-pattern matching original working only on raw content. Naive and straightforward solutions towards this challenge either decompress the compressed data first and apply legacy multi-pattern matching methods, or have to scan redundant data during the matching., which are not fast and memory efficient. In this paper, we propose COmpression INspection (COIN) method for multi-pattern matching on compressed HTTP traffic. COIN does not decompress the data before matching and only scans once each bit of the traffic under inspection. We have collected real traffic data from Alexa.com top 500 and Alexa.cn top 20000 web sites and have performed the experiments under 1430 SNORT patterns. The evaluation results show that COIN is 10–31% faster than state-of-the-art approach.

Software defined networks provide new opportunities for automating the process of network debugging. Many tools have been developed to verify the correctness of network configurations on the control plane. However, due to software bugs and hardware faults of switches, the correctness of control plane may not readily translate into that of data plane. To bridge this gap, we present VeriDP, which can monitor "whether actual forwarding behaviors are complying with network configurations". Given that policies are well-configured, operators can leverage VeriDP to monitor the correctness of the network data plane. In a nutshell, VeriDP lets switches tag packets that they forward, and report tags together with headers to the verification server before the packets leave the network. The verification server pre-computes all header-to-tag mappings based on the configuration, and checks whether the reported tags agree with the mappings. We prototype VeriDP with both software and hardware OpenFlow switches, and use emulation to show that VeriDP can detect common data plane fault including black holes and access violations, with a minimal impact on the data plane.

How to debug large networks is always a challenging task. Software Defined Network (SDN) offers a centralized con- trol platform where operators can statically verify network policies, instead of checking configuration files device-by-device. While such a static verification is useful, it is still not enough: due to data plane faults, packets may not be forwarded according to control plane policies, resulting in network faults at runtime. To address this issue, we present VeriDP, a tool that can continuously monitor what we call control-data plane consistency, defined as the consistency between control plane policies and data plane forwarding behaviors. We prototype VeriDP with small modifications of both hardware and software SDN switches, and show that it can achieve a verification speed of 3 μs per packet, with a false negative rate as low as 0.1%, for the Stanford backbone and Internet2 topologies. In addition, when verification fails, VeriDP can localize faulty switches with a probability as high as 96% for fat tree topologies.

Software Defined Networking (SDN) is evolving to such a phase that multiple programming languages and rule specifications coexist. However, current SDN compilers are closely bound to both languages and rules, thus disable the interoperability and compatibility of SDN programs. To solve this problem, we propose to modularize the SDN compiler by leveraging intermediate representation (IR), a common technique for computer compiler design. Specifically, we introduce Semantic Rule (SR) as the first IR for SDN compilers, which is a simple, language-independent, and semantic-preserving representation. We develop two optimizations on the semantic rule to coordinate cross-language programs in a single network and compress the number of compiled rules. We implement a modular compiler prototype with the proposed SR, and demonstrate that RYU programs can run at both OpenFlow and POF network. With synthetic network configurations, we demonstrate that the optimizations on SRs are effective, efficient and scalable.

The de facto implementation of Software Defined Networking (SDN), i.e., OpenFlow, only parses L2-L4 headers, which limits the use of SDN to employ control intelligence in application layer. In this paper, we advocate content parsing to empower SDN with finer grained control ability over traffic. Specifically, we propose a scalable content parser, called COPY, to identify and parse application layer protocols. COPY creates a distinguishable counting context free grammar (DCCFG) to specify the protocol's semantics in application layer, and translates multiple DCCFGs into one distinguishable counting automaton (DCA). DCA is generated without semantic loss from the single DCCFG, and thus provides accurate and scalable parsing ability. Our experiments show that COPY precisely identifies every packet in a labeled trace. When comparing with other six approaches on the real traces, COPY performs 4.2Gb/s and 24.7Gb/s with single- and eight-thread models, respectively, which improves 20%-860% than others, and consumes acceptable offline overhead in time and space.

This paper studies the fine-grained traffic identification (FGTI) for better understanding and managing networks.Instead of only indicating which application/protocol that a packet is related to, FGTI maps the traffic packet to ameaningful user behavior or application context. In this paper, we first propose rule organized optimal matching (ROOM),which splits the identification rules into several fields and elaborately organizes the matching order of the fields. Asa result, ROOM can only activate the matching operations on a (small) part of the rules that could be possibly hit. Weformulate the optimal rule organization problem of ROOM mathematically and demonstrate it to be NP-hard, and then wepropose a heuristic algorithm to solve the problem with the time complexity of O(N2) (N is the number of fields in the rule set). Based on ROOM, wefurther propose MP-ROOM, which is extended to well support the rules cross multiple protocol data units (PDUs) fortraffic identification. In addition, we implement a prototype system including MP-ROOM and related work for evaluations.The evaluations show very promising results: 1.5 ~71.3 times throughput improvement is obtained by MP-ROOM inthe real system with less than 300-MB memory consumption. With multiple-thread parallel programming, we successfullyachieve the throughput over 40 Gb/s for real traces.

Fine-grained traffic identification (FGTI) reveals the context/purpose of each packet that flows through the network nodes/links. Instead of only indicating the application/protocol that a packet is related to, FGTI further maps the packet to a meaningful user behavior or application context. In this paper, we propose a Rule Organized Optimal Matching (ROOM) for fast and memory efficient fine-grained traffic identification. ROOM splits the identification rules into several fields and elaborately organizes the matching order of the fields. We formulate and model the optimal rule organization problem of ROOM mathematically, which is demonstrated to be NP-hard, and then we propose an approximate algorithm to solve the problem with the time complexity of O(N2) (N is the number of fields in a rule). In order to perform evaluations, we implement ROOM and related work as real prototype systems. Also, real traces collected in wired Internet and mobile Internet are used as the experiment input. The evaluations show very promising results: 1.6X to 104.7X throughput improvement is achieved by ROOM in the real system with acceptable small memory cost.