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.

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 simulation plays a critical role in improving the efficiency of large-scale AI clusters for design validation, parameter tuning, and protocol development. However, high-fidelity network simulation becomes prohibitively slow at scale, especially when running large batches of experiments on topologies with tens or hundreds of thousands of accelerators. We observe that a key bottleneck comes from the control plane. Existing network simulators typically compute routes and install forwarding tables at initialization, which can consume hundreds of GB of memory before packet-event execution begins and limit overall simulation throughput. In this paper, we present Nüwa, which views routing as a compilation problem, it leverages the hierarchical and symmetric structure common in AI fabrics and compiles a declarative topology description together with routing policies into compact forwarding artifacts that are fast to generate and efficient to look up. Evaluations show that Nüwa can reduce simulation initialization time from hours to only 25 seconds for a 65,536-GPU cluster. For end-to-end simulation time, Nüwa takes only 20% of that required by existing approaches in a 40K+ GPU cluster, and Nüwa can scale to a 221,184-GPU cluster.

Network verification, synthesis, and repair tools help enforce high-level operational intent, but their limited explainability makes configuration maintenance costly in practice, as operators must still manually reason about large, low-level configurations. We propose localized subspecifications, which explain how individual configuration elements preserve a given network property by constraining their admissible behaviors. A user study with 15 professional network operators and 8 graduate students shows 52% higher accuracy and 23% time savings, and 70% of participants reported that they would like to use subspecifications in daily operations, demonstrating practical benefits. To support real deployments, we develop SpecLens, an explainable network verification system that generates localized subspecifications using a scalable algorithm with soundness guarantees. SpecLens computes line-level and field-level subspecifications in 10 minutes on the real-world Internet2 configuration and 25 minutes on FatTree networks with up to 1,280 routers.

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

With the diversification of cloud services, cloud providers offer flexible access control by letting users apply fine-grained cloud access control policies to secure their cloud resources. However, flexibility comes with the cost that configuring cloud access control policies is error-prone. Therefore, cloud providers have developed SMT-based tools to formally analyze the user-defined policies. Unfortunately, we find these analyzers slow, due to the complex regular expression matching conditions in policies. To this end, this paper introduces Relia, a general method to speed up the analysis of cloud access control policies. The key idea of Relia is to pre-compute a set of String Equivalence Classes (SECs) based on the regular expressions in a policy, assign a unique integer to each SEC, and rewrite the regular constraints into equivalent integer constraints, which are easier to solve. We implement Relia as a transparent layer between our in-house access analyzer and off-the-shelf SMT solvers. Based on real policies from a large public cloud provider, we show that: when enabling Relia, our in-house portfolio solver (consisting of Z3, Cvc4, and Cvc5) can speed up the analysis process for nearly 95% of all cases, with an average speedup of 8.21×.

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.

Advanced router configuration synthesizers aim to prevent network outages by automatically synthesizing configurations that implement routing protocols. However, the lack of interpretability makes operators uncertain about how low-level configurations are synthesized and whether the automatically generated configurations correctly align with routing intents. This limitation restricts the practical deployment of synthesizers.In this paper, we present NetKG, an interpretable configuration synthesis tool.(i) NetKG leverages a knowledge graph as the intermediate representation for configurations, reformulating the configuration synthesis problem as a configuration knowledge completion task; (ii) NetKG regards network intents as query tasks that need to be satisfied in the current configuration space, achieving this through knowledge reasoning and completion; (iii) NetKG explains the synthesis process and the consistency between configuration and intent through the configuration knowledge involved in reasoning and completion.We show that NetKG can scale to realistic networks and automatically synthesize intent-compliant configurations for static routes, OSPF, and BGP. It can explain the consistency between configuration and intent at different granularities through a visual interface. Experimental results indicate that NetKG synthesizes configurations in 2 minutes for a network with up to 197 routers, which is 7.37x faster than the SMT-based synthesizer.

Networks are error-prone due to misconfigurations, and it is hard to identify the root causes in the configuration and find a repair due to the size and complexity of networks running distributed routing protocols. Thus, we advocate Automatic Configuration Repair (ACR) to reduce the manual effort. Specifically, we draw some insights from the field of Automatic Software Repair (ASR), crystallize some lessons learned from the real-world repair experience of a large service provider, and propose some directions to realize ACR. Inspired by the generate-and-validate approach from ASR, we propose localize-fix-validate as a possible approach to realize ACR.

Existing network verifiers can efficiently identify failure-induced bugs. However, an equally-important concern is identification of external-routes-induced bugs, which has not been well addressed. Comprehensively reasoning about external routes is challenging, since each external neighbor can advertise an arbitrary set of routes, which is quite a huge space. This paper introduces a new network verifier, Expresso, which uses symbolic simulation to explore the equivalences in the space of external routes. We evaluate the effectiveness and scalability of Expresso on the WAN of a large cloud service provider and Internet2. Expresso found various property violations, some of which have already been confirmed by the operators. To the best of our knowledge, Expresso is the only verifier that can check the correctness of WANs amidst arbitrary external routes in a tractable amount of time, while other verifiers time-out after 1 day.

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 verification often requires analyzing properties across different spaces (header space, failure space, or their product) under different failure models (deterministic and/or probabilistic). Existing verifiers efficiently cover the header or failure space, but not both, and efficiently reason about deterministic or probabilistic failures, but not both. Consequently, no single verifier can support all analyses that require different space coverage and failure models. This paper introduces Symbolic Router Execution (SRE), a general and scalable verification engine that supports various analyses. SRE symbolically executes the network model to discover what we call packet failure equivalence classes (PFECs), each of which characterises a unique forwarding behavior across the product space of headers and failures. SRE enables various optimizations during the symbolic execution, while remaining agnostic of the failure model, so it scales to the product space in a general way. By using BDDs to encode symbolic headers and failures, various analyses reduce to graph algorithms (e.g., shortest-path) on the BDDs. Our evaluation using real and synthetic topologies show SRE achieves better or comparable performance when checking reachability, mining specifications, etc. compared to state-of-the-art methods.

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.

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.

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

Data centers, the critical infrastructure underpinning Cloud computing, often employ Software-Defined Networks (SDN) to manage cluster, wide-area and enterprise networks. As the network forwarding in SDN is dynamically programmed by controllers, it is crucial to ensure that the controller intent is correctly translated into underlying forwarding rules. Therefore, detecting and locating forwarding anomalies in SDN is a fundamental problem in production networks. Existing research proposals, roughly categorized into probing-based, packet piggybacking-based, and flow statistics analysis-based, either impose significant overhead or do not provide sufficient coverage for certain forwarding anomalies. In this article, we propose${\sf FADE}$, a controllable and passive measuring scheme to simultaneously deliver detection efficiency and accuracy.${\sf FADE}$first analyzes the entire network topology and flow rules, and then computes a minimal set of flows that can cover all forwarding rules. For each selected network flow,${\sf FADE}$decides the optimal number of monitoring positions on its path (much less than total number of hops), and installs dedicated rules to collect flow statistics.${\sf FADE}$controls the installation and expiration of these rules, along with unique flow labels, to guarantee the accuracy of collected statistics, based on which${\sf FADE}$algorithmically decides whether a forwarding anomaly is detected, and if so it further locates the anomaly. On top of${\sf FADE}$, we propose${\sf iFADE}$(a more scalable version of${\sf FADE}$) to further optimize the usage and deployment of dedicated measurement rules.${\sf iFADE}$achieves over 40 percent rule reduction compared with${\sf FADE}$. We implement a prototype of both${\sf FADE}$and${\sf iFADE}$in about 12000 lines of code and evaluate the prototype extensively. The experiment results demonstrate${\sf (i)}$${\sf FADE}$and${\sf iFADE}$are accurate, e.g., they achieve over 95 percent true positive rate and 99 percent true negative rate in anomaly detection;${\sf (ii)}$${\sf FADE}$and${\sf iFADE}$are lightweight, e.g., they reduce the overhead of control messages compared with state-of-the-art by about 50 and 90 percent, respectively.

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.

Network configurations are constantly changing, and each change poses a risk of catastrophic network outages. Consequently, the networking community has put significant effort into developing and optimizing configuration verifiers. However, we observe existing configuration verifiers still have a significant drawback: they are not optimized for configuration changes. That is, they always check a snapshot of network configuration from scratch, even though the configuration often changes slightly since the last verification. In this paper, we demonstrate the benefits, opportunities, and challenges of incremental network configuration verification (INCV). We also demonstrate the feasibility of INCV by introducing RealConfig, an incremental configuration verifier that can check configuration changes within one second.

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.

Software defined networking (SDN) reshapes the ossified network architectures, by decoupling the control plane and data plane. Due to such a decoupling, SDN assumes that rules issued by the control plane are always correctly enforced by the data plane. However, this assumption breaks as an adversary can prevent the data plane from enforcing the rules, by exploiting the vulnerabilities of switch OS and control channel. The serious consequence is that packets may deviate from their original paths, thereby violating critical security policies like access control. To this end, this paper introduces rule enforcement verification (REV), which enables the controller to check whether switches have correctly enforced the rules that it issues. Since using message authentication code (MAC) can incur heavy switch-to-controller traffic, we propose the compressive MAC, which lets switches compress MACs before reporting to the controller, thereby significantly reducing the bandwidth cost. Finally, we propose a heuristic flow selection algorithm, which allows the controller to verify much less flows for rule coverage. We implement REV based on Open vSwitch with DPDK, and use experiments to show: (1) by using compressive MAC, REV achieves a 97% reduction in switch-to-controller traffic, and an 8× increase in verification throughput; (2) by using the heuristic flow selection algorithm, REV can reduce the number of flows to verify by 40%-60%.

A key feature of software-defined networking (SDN) is the decoupling of control pane and data plane. Although delivering huge benefits, such a decoupling also brings a new risk: the data plane states (i.e., flow tables) may deviate from the control plane policies. Existing data plane testing tools such as RuleScope check the correctness of flow tables by injecting probes. However, they are limited in four aspects: 1) are slow in generating probes due to solving SAT problems; 2) may raise false negatives when there are multiple missing rules; 3) cannot test cascaded flow tables used by OpenFlow switches; and 4) either does not support incremental update or has a slow update speed. To overcome these limitations, we present RuleChecker, a fast data plane testing tool for SDN. In contrast to previous tools that generate each probe by solving an SAT problem, the RuleChecker takes the flow table as whole and generates all probes through an iteration of simple set operations. By leveraging binary decision diagram to encode sets, we make the RuleChecker extremely fast: nearly$20\times $faster than the RuleScope, and can update probes in less than 2 ms for 90% of the cases, based on the Stanford backbone rule set.

Distinct sampling is fundamental for computing statistics (e.g., the age and gender distribution of distinct users accessing a particular website) depending on the set of distinct keys (e.g., user IDs) in a large and high speed data stream such as a sequence of key-update pairs. However, the major shortcoming of existing methods is their high computational cost incurred by determining whether each incoming key in the data stream is currently in the set of sampled keys and keeping track of sampled keys’ update aggregations. To solve this challenge, we develop a new methodrandom projection and eviction(RPE) that uses a list of buckets to continuously sample distinct keys and their update aggregations. RPE processes each key-update pair with small and nearly constant time complexity$O(1)$. Besides centralized data streams, we also develop a novel method DRPE to deal with distributed data streams consisting of key-update pairs observed at multiple distributed sites. We conduct extensive experiments on real-world datasets, and the results demonstrate that RPE and DRPE reduce the memory, computational, and message costs of state-of-the-art methods by several times.

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.

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.

A key feature of Software Defined Network is the decoupling of control pane and data plane. Although delivering huge benefits, such a decoupling also brings a new risk: the data plane states (i.e., flow tables) may deviate from the control plane policies. Existing data plane testing tools like Monocle check the correctness of flow tables by injecting probes. However, they are limited in four aspects: (1) slow in generating probes due to solving SAT problems, (2) may raise false negatives when there are multiple missing rules, (3) do not support incremental probe update to work in dynamic networks, and (4) cannot test cascaded flow tables used by OpenFlow switches. To overcome these limitations, we present RuleChecker, a fast and complete data plane testing tool. In contrast to previous tools that generate each probe by solving an SAT problem, RuleChecker takes the flow table as whole and generates all probes through an iteration of simple set operations. By lever-aging Binary Decision Diagram (BDD) to encode sets, we make RuleChecker extremely fast: around 5 χ faster than Monocle (when detecting rule missing faults), and nearly 20 χ faster than RuleScope (when detecting both rule missing and priority faults), and can update probes in less than 2 ms for 90% of cases, based on the Stanford backbone rule set.

Software defined networks (SDNs) reshape the ossified network architectures, by introducing centralized and programmable network control. Despite the huge benefits, SDNs also open doors to what we call rule modification attack, an attack largely overlooked by the community. In such an attack, the adversary can modify rules by exploiting implementation vulnerabilities of switch OSes and control channels. As a result, packets may deviate from their original paths, thereby violating network policies. To defend against rule modification attack, this paper introduces a new security primitive named rule enforcement verification (REV). REV allows a controller to check whether switches have enforced the rules installed by it, using message authentication code (MAC). Since using standard MACs will incur heavy switch-to-controller traffic, this paper proposes a new compressive MAC, which allows switches to compress MACs before reporting to the controller. Experiments show that REV based on compressive MAC can achieve a 97% reduction in switch-to-controller traffic, and a Sx increase in verification throughput.

Traffic statistics are fundamental for many network measurement tasks like heavy hitter identification, traffic matrix estimator, anomaly detection, etc. However, traditional techniques like NetFlow and sFlow only provide coarse-grained statistics due to packet or flow sampling. Even Software Defined Networking (SDN) offers fine-grained traffic statistics collection, most of existing methods focus on specific applications and thus lack generality. To this end, we propose CounterMap, a generic traffic statistics collection and query platform. CounterMap maintains a full map of flow counters by actively polling switches and passively monitoring flow timeouts. For efficient storage and query, CounterMap stores the counters in fast off-the-shelf inmemory data store, and offers a generic SQL-like query language. With the CounterMap language, applications can gain visibility into both existing and historical flows, without querying the dataplane devices themselves. We show how network applications benefit from CounterMap, with higher measurement accuracy and lower dataplane overhead.

As a popular realization of Information-Centric Network (ICN), Named Data Networking (NDN) greatly improves the efficiency of Internet content-distribution. A feature of NDN is that it improves privacy, as no addresses are needed for either the content consumer or publisher. However, NDN packets contain content names, and hence a well-motivated adversary can still deducewhatcontent the user is requesting once it can link the packets and users. How to provide privacy in NDN, given its unique data retrieval mode, is an open problem. In this paper, we explore a specific content-oriented anonymity model calledcontent-user unlinkability, which breaks the relationship between the content and the requesting user. We argue that achieving content-user unlinkability efficiently is a non-trivial task, since existing tunnel-based approaches will largely dismiss content caching of NDN, resulting in large content retrieval delay. To this end, we propose CRISP, namelyCooperativeRandomIntereStPropagation. In CRISP, routers cooperate to form full-meshed groups, within which content requests are randomly propagated before they are forwarded to content producers. We show CRISP can achieve probable content-user unlinkability with probabilistic models. Extensive simulations demonstrate that CRISP outperforms existing solutions including ANDANA and Crowds, in terms of both content retrieval latency and data throughput.

Named data networking (NDN) enhances traditional IP networking by supporting in-network content caching for better bandwidth usage and location-independent data accesses for multi-path forwarding. However, NDN also brings new security challenges. For example, an adversary can arbitrarily inject packets to NDN to poison content cache, or access content packets without any restrictions. We propose capability-based security enforcement architecture (CSEA), a capability-based security enforcement architecture that enables data authenticity in NDN in a distributed manner. CSEA leverages capabilities to specify the access rights of forwarded packets. It allows NDN routers to verify the authenticity of forwarded packets, and throttles flooding-based DoS attacks from unsolicited packets. We further develop a lightweight one-time signature scheme for CSEA to ensure the timeliness of packets and support efficient verification. We prototype CSEA on the open-source CCNx platform, and evaluate CSEA via testbed and Planetlab experiments. Our experimental results show that CSEA only incurs around 4% of additional delays in retrieving data packets.

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.

OpenFlow, as the Software Defined Networking (SDN) primitive, provides a simple forwarding plane abstraction, which heavily relies on the fast memory inside the OpenFlow Switch (OFS). OFS components, e.g. flow table, meter table, counters, have to compete for the limited fast memory resource. As a result, only a few counting functions are defined as mandatory in the OFS specification, although a lot of SDN proposals depend on a detailed states collected by the optional counters in the specification. This fact motivates us to rethink the way to maintain counters in the OFS. We propose a new architecture called CACTI, which only consumes several registers in the fast path and moves the completed counters into the on chip RAM like cache in the slow path processor. Theoretical analysis and experiments on the prototype system demonstrated the efficiency of our architecture: CACTI is capable to achieve the throughput of 29.4-39.7M pps packets per second (pps). No RAM resource is needed any more in the fast path, instead, CACTI consumes only 0.24-0.54\% Look-Up Table and 0.35-0.43\% flip-flops compared with the entire FPGA-based OFS design in the fast path, and the unused CPU cache in the slow path.

Controllers play a critical role in software-defined networking (SDN). However, existing single-controller SDN architectures are vulnerable to single-point failures, where a controller’s capacity can be saturated by flooded flow requests. In addition, due to the complicated interactions between applications and controllers, the flow setup latency is relatively large. To address the above security and performance issues of current SDN controllers, we propose distributed rule store (DRS), a new multi-controller architecture for SDNs. In DRS, the controller caches the flow rules calculated by applications, and distributes these rules to multiple controller instances. Each controller instance holds only a subset of all rules, and periodically checks the consistency of flow rules with each other. Requests from switches are distributed among multiple controllers, in order to mitigate controller capacity saturation attack. At the same time, when rules at one controller are maliciously modified, they can be detected and recovered in time. We implement DRS based on Floodlight and evaluate it with extensive emulation. The results show that DRS can effectively maintain a consistently distributed rule store, and at the same time can achieve a shorter flow setup time and a higher processing throughput, compared with ONOS and Floodlight.

Location Based Service (LBS) is gaining popularity on smart phones. One fundamental LBS is range search, which returns all Point of Interests (POIs) within a user-specified range. However, people also leave their location privacy at risks when using LBS like range search. How can a user invoke such service without revealing his location is an interesting, yet challenging problem to solve. Most existing approaches blur a user's location into a cloaked region, so that LBS cannot figure out the exact location of the requesting user. However, this would make the returning results inaccurate, containing some out-of-range POIs. To this end, we propose PAPERS, a new method to provide location privacy for users of range search. PAPERS leverage homomorphic encryption to let the user encrypt her location, and the LBS server can compute distances on ciphertext. In this way, the returning results by LBS are exactly the POIs within the specified range, while LBS learns nothing about user's real location. We implement a prototype of PAPERS, and evaluate it with real POI set of a large-scale production LBS. Experimental results show that PAPERS can achieve the goal of privacy protection, with reasonable overhead in response time and communication cost.

It has become a common practice that enterprises outsource their networks to the cloud by renting multiple virtual machines (VMs) in cloud datacenters. Due to the multi-tenant nature of cloud datacenter, how to efficiently share the network resources becomes an important issue. Recent studies, e.g., SecondNet and Oktopus, have taken network bandwidth into consideration when allocating VMs. However, these schemes are problematic in that the allocation is not that accurate, and can result in a low multiplexing rate. To this end, we present VirtualRack (VR), a new bandwidth-aware VM allocation scheme in multi-tenant datacenters. VR simultaneously considers intra-datacenter bandwidth and Internet-access-bandwidth requirements in the allocation process. In addition, we introduce a redundancy factor α that can be specified by tenants to accommodate their dynamic requirements. Simulation results show that VR can guarantee the network performance for each of the multiple tenants, and at the same time keep a high acceptance ratio without any false allocation.

Many web service providers use commercial cloud computing infrastructures like Amazon for flexible and reliable service deployment. For these web service providers, the cost of cloud computing usage becomes a big part of their IT department cost. Facing the diverse pricing models including on-demand, reserved, and spot instance, it is difficult for web service providers to optimize their cost. This paper introduces a new cloud brokerage service to help web service providers to minimize their cloud computing cost for deadline-constrained batch jobs, which have been a significant workload in web services. Our cloud brokerage service associates each batch job with deadline, and always tries to use cheaper reserved instances for computation to maintain a minimum cost. We achieve this with the following two steps: (1) given a set of jobs' specifications, determine the scheduling of jobs, (2) given the scheduling and pricing options, find an optimal instance renting strategy. We prove that both problems in two steps are computation intractable, and propose approximation algorithms for them. Trace-based evaluation shows that our cloud brokerage service can reduce up to 57% of the cloud computing cost.

Energy saving is an important issue in Mobile Ad Hoc Networks (MANETs). Recent studies show that network coding can help reduce the energy consumption in MANETs by using less transmissions. However, apart from transmission cost, there are other sources of energy consumption, e.g., data encryption/decryption. In this paper, we study how to leverage network coding to reduce the energy consumed by data encryption in MANETs. It is interesting that network coding has a nice property of intrinsic security, based on which encryption can be done quite efficiently. To this end, we propose P-Coding, a lightweight encryption scheme to provide confidentiality for network-coded MANETs in an energy-efficient way. The basic idea of P-Coding is to let the source randomly permute the symbols of each packet (which is prefixed with its coding vector), before performing network coding operations. Without knowing the permutation, eavesdroppers cannot locate coding vectors for correct decoding, and thus cannot obtain any meaningful information. We demonstrate that due to its lightweight nature, P-Coding incurs minimal energy consumption compared to other encryption schemes.

This paper proposes a new network-wide optimized time division multiple access (TDMA) scheduling scheme for wireless sensor networks (WSNs). It can simultaneously achieve maximum throughput and fair rate allocation given the requirement of network lifetime. To achieve this object, we first formulate the rate allocation problem based on the Lexicographic Max-Min (LMM) criterion, which takes fairness, throughput maximization, and slot reuse into consideration. Then, we develop a polynomial-time algorithm by exploiting iterative linear program (LP) to solve the LMM optimization. Based on the optimal rate allocation vector and relay scheme derived from the optimization model, we present a TDMA scheduling algorithm to achieve a minimum TDMA frame length through slot reuse. We jointly interconnect the LMM rate allocation and TDMA scheduling algorithm with a slot reuse control parameter, and propose a procedure to iteratively calculate a proper value for this parameter. Numerical results show that our proposed TDMA schedule improves the fairness and throughput significantly.

Content-Centric Network (CCN) provides a cleanslate design for the Internet, where content becomes the primitive of communications. In CCN, routers are equipped with content stores, which act as caches for frequently requested content. This design enables the Internet to provide content distribution services without any application-layer support. On the other hand, as caches are integrated into routers, the overall performance of CCN will be influenced by the caching efficiency. This paper studies the performance issues of caches in CCN, with the aim to gain some understanding on how caches should be designed to maintain a high performance in a cost-efficient way. Specifically, we use a two-dimensional discrete-time Markov chain to model the two-layer cache hierarchy formed by CCN routers, and develop an efficient algorithm to calculate the hit ratios of these caches. Simulations validate the accuracy of our modeling method, and convey some understanding on cache design in CCN.

Reliability is a critical concern in the provision and placement of web services. A breakdown of service would seriously reduce customers' satisfaction, and thus harm the revenue of service providers. To maintain a high reliability, the common approach is deploying multiple service instances across different physical servers. This would inevitably raise another concern of energy consumption. Thus, greening web services also becomes an important issue. In this paper, we study the fundamental tradeoff between reliability and energy consumption, and propose an optimization framework that considers both factors. In specific, we build a continuous-time Markov model to analyze the steady-state reliability and mean time to failure (MTTF) from a service-oriented perspective, and obtain the minimum number of service instances to meet the given reliability requirement. Then, we show that deploying these instances in the server cluster to minimize energy consumption is NP-hard. To this end, we propose a heuristic algorithm to approximate the result. The analytical and experimental results show the effectiveness, and the approximation ratio is less than 1.25 for 90% of the data sets we use.

Practical wireless network coding (e.g., COPE) is a promising technique that can enhance the throughput of wireless networks. However, such a technique also bears a serious security drawback: it breaks the current privacy-preserving protocols (e.g., Onion Routing), since their operations conflict each other. As user privacy in wireless networks is highly valued nowadays, a new privacy-preserving scheme that can function with wireless network coding becomes indispensable. To address such a challenge, we apply the idea of cooperative networking and design a novel anonymity scheme named ANOC, which can function in network-coding-based wireless mesh networks. ANOC is built upon the classic Onion Routing protocol, and resolves its conflict with network coding by introducing efficient cooperation among relay nodes. Using ANOC, we can perform network coding to achieve a higher throughput, while still preserving user privacy in wireless mesh networks. We formally show how ANOC achieves the property of relationship anonymity, and conduct extensive experiments via nsclick to demonstrates its feasibility and efficiency when integrated with network coding.

Network coding provides a promising alternative to traditional store-and-forward transmission paradigm. However, due to its information-mixing nature, network coding is notoriously susceptible to pollution attacks: a single polluted packet can end up corrupting bunches of good ones. Existing authentication mechanisms either incur high computation/bandwidth overheads, or cannot resist the tag pollution proposed recently. This paper presents a novel idea termed “padding for orthogonality” for network coding authentication. Inspired by it, we design a public-key based signature scheme and a symmetric-key based MAC scheme, which can both effectively contain pollution attacks at forwarders. In particular, we combine them to propose a unified scheme termed MacSig, the first hybrid-key cryptographic approach to network coding authentication. It can thwart both normal pollution and tag pollution attacks in an efficient way. Simulative results show that our MacSig scheme has a low bandwidth overhead, and a verification process 2–4 times faster than typical signature-based solutions in some circumstances.

Though providing an intrinsic secrecy, network coding is still vulnerable to eavesdropping attacks, by which an adversary may compromise the confidentiality of message content. Existing studies mainly deal with eavesdroppers that can intercept a lim-ited number of packets. However, real scenarios often consist of more capable adversaries, e.g., global eavesdroppers, which can defeat these techniques. In this paper, we propose P-Coding, a novel security scheme against eavesdropping attacks in network coding. With the lightweight permutation encryption performed on each message and its coding vector, P-Coding can efficiently thwart global eavesdroppers in a transparent way. Moreover, P-Coding is also featured in scalability and robustness, which enable it to be integrated into practical network coded systems. Security analysis and simulation results demonstrate the efficacy and efficiency of the P-Coding scheme.