In the Segment Routing over IPv6 (SRv6) network, a wide range of network events (e.g., attacks, intrusions, violations, malicious route announcements) may occur. Network management requires real-time monitoring of untrusted and unreliable environments (e.g., unsafe components and devices). Early localization of abnormal links causing violations in the SRv6 network helps minimize the compensation required for service unavailability. However, the overhead of the state-of-the-art methods does not scale efficiently to large-scale SRv6 networks and exhibit poor robustness to addressing various disturbances from unreliable networks. To cope with these challenges, we propose Glint, an in-band network telemetry framework to localize abnormal links in SRv6 networks. The key idea of Glint is sampling part of the information while the overall information is known. Glint provides probabilistic in-band collection to gather segment-level telemetry data, reducing overhead and improving efficiency. Glint also proposes distributed verification-based detection to enhance the trustworthiness of security assessments, further improving robustness against disturbances. In addition, we design selective telemetry that reduces telemetry reports while preserving security-relevant visibility. Our evaluations demonstrate that, compared to the state-of-the-art frameworks, Glint significantly reduces header bandwidth overhead by 75.6% and memory overhead by 48.7% while reducing false positives. We also implement Glint on the Intel Tofino switch, achieving over a 50% reduction in hardware resource consumption compared to existing methods.

The rapid development of the Internet catalyzes emerging applications and diverse requirements. However, the single best-effort path selection paradigm of BGP impedes the inter-domain routing system for addressing such demands. Despite numerous protocols designed for optimization, they manifest limitations: 1) a single protocol often fails to cater to the broad spectrum of AS requirements, and 2) the adoption of multiple protocols occurs disjointedly, leading to partial-deployment issues. In addressing these challenges, we propose Vinculum-BGP ($\textsf {VBGP}$), enabling ASes to flexibly optimize routes and fostering the evolution of inter-domain routing. The core of$\textsf {VBGP}$is a low-cost vinculum (named as$\textsf {rra}$) scheme for bi-directional path negotiation. This scheme improves upon current multipath routing protocols by allowing ASes to discover unpropagated but beneficial paths, ensuring seamless integration with a majority of routers and adaptability to various requirements. We formally prove the stability of routing under$\textsf {rra}$, showing that$\textsf {VBGP}$facilitates the optimization between different protocols without compromising routing stability. We also introduce some simple-to-implement$\textsf {rra}$policies, so that$\textsf {VBGP}$ASes can achieve comparable results to existing complex protocols in terms of pathavailabilityandquality. Finally, we assess the efficacy of$\textsf {VBGP}$through Internet-scale simulations spanning various deployment scenarios, showcasing its substantial benefits to ASes during the initial deployment phase with minimal costs.

Segment Routing over IPv6 (SRv6) is widely deployed, where operators construct numerous parallel SR-based network slices. An accurate diagnosis of latency bottlenecks in SRv6 tunnels is essential to maintain service-level objectives. However, building a distributed, at-scale probing system is non-trivial: SRv6 priority policies, SR-aware multipath forwarding, and slice isolation collectively invalidate assumptions made by existing diagnostic methods. In this paper, we present SRmesh, a distributed system for diagnosing latency bottleneck links in SRv6 networks. First, we adopt distributed SR-based probing agents to control routing paths and ensure that probe packets emulate per-slice production traffic. Second, we employ a latency-based multipath inference that runs in parallel across slices to resolve SR-induced routing ambiguities. Third, we introduce a sliceparallel progressive diagnosis that incrementally reuses probe results to reduce redundant measurements, optimizing diagnostic overhead for large-scale SRv6 overlay networks. We implement a prototype of SRmesh and conduct extensive evaluations on 247 real network topologies. The results indicate that SRmesh achieves high diagnostic accuracy with a 93.4% reduction in probe overhead, demonstrating its practicality and scalability in large-scale SRv6 environments.

The Resource Public Key Infrastructure (RPKI) plays a crucial role in securing BGP against prefix hijacking by enabling Route Origin Validation (ROV). However, the limited adoption of ROV in the real world undermines the effectiveness of RPKI. Hence, measuring ROV deployment in practice is essential for assessing the impact of RPKI. Existing measurement efforts either suffer from limited coverage and accuracy due to reliance on control-plane data, or require controlled IP prefixes or large-scale deployment of vantage points. Furthermore, most studies focused on IPv4, leaving ROV status in IPv6 largely underexplored.

Segment Routing over IPv6 (SRv6) has attracted more attention from network operators. Diagnosing performance bottlenecks for SRv6 tunnels is critical to maintaining network quality. However, SRv6 introduces priority policies, special forms of multipath routing, and SR-based network slicing, all of which make existing methods difficult to apply. In this paper, we present SRmesh, a framework for diagnosing latency bottleneck links specifically tailored for SRv6 tunnel performance analysis. First, we adopt SR-based probing to deterministically control routing paths and ensure that probe packets emulate real production traffic. Second, we employ a latency-based multipath inference to resolve routing ambiguities caused by SR. Third, we introduce a topology-independent progressive diagnosis that incrementally reuses probe results to reduce redundant measurements, optimizing diagnostic overhead for large-scale SRv6 overlay networks. We implement a prototype of SRmesh and conduct extensive evaluations on real network topologies. The results indicate that SRmesh achieves high diagnostic accuracy with up to a 91.9% reduction in probe overhead, demonstrating its practicality and scalability in large-scale SRv6 environments.

The complexity of routing requirements leads to increasingly intricate routing metrics. Existing routing algebra theories have demonstrated that convergent and optimal routing algorithms can be designed only when path metrics satisfy certain properties such as monotonicity and isotonicity. Furthermore, some non-isotonic metrics can be converted into isotonic forms on partial orders through reduction. However, practical scenarios often involve non-commutative algebraic properties, which are overlooked by existing theories. For these problems, there lacks a unified framework to study their solvability, a systematic method for their reduction, and an efficient algorithm to compute optimal routes. In this work, we extend routing algebra to accommodate non-commutative routing problems, propose general reduction methods for them, and explore their solvability. In addition, we design a link state algorithm that converge fast on a reduced partial order. All these discussions are supported by concrete examples, theoretical proofs, and simulations on various network topologies.

Source Address Validation (SAV) is a security mechanism deployed at network boundaries to prevent packets with illegal source addresses from crossing these boundaries. While SAV plays an important role in mitigating source address spoofing, its deployment across the global Internet remains limited. Measuring SAV deployment is essential for enhancing the understanding of the security landscape of networks. In this study, we propose a novel method for measuring SAV deployment based on 6 in 4 tunnels, complementing existing measurement work. Using this method, we measure inbound SAV for IPv4 and outbound SAV for IPv6, obtaining results from 12,417 and 2,104 Autonomous Systems (ASes), respectively. Based on our measurements, we analyze factors that may influence SAV deployment, including network address space size, AS type, and geographical location. Additionally, we provide a global heatmap of spoofable rates for networks in different countries and regions. Note that the measuring method using bin4 tunnels we introduce is not only applicable to SAV measurements but also holds potential for other measurement tasks, such as connectivity testing and transmission path discovery. This method offers a new way for large-scale measurement tasks across different networks, which may benefit future research.

Network structures are sophisticated and hence vulnerable to errors. Link failures and traffic load fluctuations lead to complexity in network states. Different failure scenarios can result in varying network traffic distribution patterns. Meanwhile, the load on links within the same failure scenario dynamically changes with fluctuations in traffic. Network administrators are particularly concerned about whether links along the paths traversed by critical traffic are overload-free guaranteed when link failures occur. Yet, no attention was ever paid to overload-free property analysis for critical traffic. We propose Offaela, an efficient and accurate probabilistic analysis framework that verifies an overload-free property for critical traffic. We prudently formulate the problem and prove its computational hardness, then storm this fortification by proffering a failure scenario merging algorithm and adopting a randomized approximation method. Evaluations on real networks show that Offaela outperforms the state-of-the-art solution by 4.83 x and can provide availability analysis assistance such as identifying vulnerable failure scenarios.

Attacks against data centers are becoming more common as a result of the fast expansion of applications. In order to keep pace with the growing amount of data centers connected to their networks, internet service providers must offer comprehensive security services. However, existing network intrusion detection systems (NIDS) are either ineffective or inefficient for the high-speed encrypted network traffic. In this paper, we design and implement Mazu, an inline network intrusion detection system with programmable switches specifically developed to protect data centers connecting to the internet service provider. Mazu proposes a dual-plane feature extraction model to extract extensive traffic features at near line-speed. Mazu also proposes a lightweight one-class classification model that trains the best parameters exclusively on benign traffic to identify the malicious traffic. In addition, Mazu introduces an online update mechanism aimed at dynamically adjusting the detection model in response to environmental changes. Mazu has been in production for two years, during which time it has identified over 10 critical attack events and protect more than 10 million servers for two ISPs. Our production and testbed evaluations demonstrate that Mazu can detect malicious traffic entering the data center sites with approximately 90% accuracy within minutes.

RDMA is becoming increasingly prevalent from private data centers to public multi-tenant clouds, due to its remarkable performance improvement. However, its lossless traffic control, i.e., PFC, introduces new complexities in network performance anomalies (NPAs) due to its cascading congestion spreading property, which usually incurs complaints from customers/applications about certain flows' performance degradation. Existing studies fall short in fine-grained visibility of PFC impact and traceability of PFC causality, and are thus ineffective in diagnosing the root causes for RDMA NPAs. In this paper, we propose Hawkeye, an accurate and efficient RDMA NPA diagnosis system based on PFC provenance. Hawkeye comprises 1) a fine-grained PFC-aware telemetry mechanism to record the PFC impact on flows; 2) an in-network PFC causality analysis and tracing mechanism to quickly and efficiently collect causal telemetry for diagnosis; and 3) a provenance-based diagnosis algorithm to comprehensively present the anomaly breakdown, identifying the anomaly type and root causes accurately. Through extensive evaluations on both NS-3 simulations and a Tofino testbed, Hawkeye can quickly and accurately diagnose multiple RDMA NPAs with over 90% precision and 1–4 orders of magnitude lower overhead than baselines.

The Automatic Certificate Management Environment (ACME) protocol automates the issuance and renewal of secure socket layer certificates, simplifying the management of large-scale certificate deployments. To reduce the load on Certificate Authority (CA) servers, ACME employs a caching mechanism that stores domain validation (DV) results for 30 days. However, this mechanism allows attackers to reuse previously authorized results, potentially bypassing the DV process. In this paper, we introduce the ACME Authz Cache Attack, whereby an attacker can obtain fraudulent certificates without domain control. We demonstrate that even the prominent CA, Let's Encrypt, is vulnerable to this attack. To mitigate this, we propose ACME++, an enhanced protocol that binds the client's IP address and a unique identifier to the ACME account, ensuring secure authorization for each new client and effectively preventing the ACME Authz Cache Attack. Our implementation of ACME++ shows that it introduces little overhead to the CA server.

Critical devices on the Internet are frequently targeted by skilled and advanced network attackers. These attackers often orchestrate complex and persistent intrusion campaigns, which involve multiple stages of attacks. In the context of host-based threat detection, the reconstruction of the entire attack scenario is crucial for tracing threats and fixing system vulnerabilities. Prior anomaly-based studies lack the capability to interpret the attack scenario, while rule-based approaches struggle with detecting novel attack patterns. We introduce eaGle, an end-to-end framework that takes original host-based data as input and reconstructs the potential attack scenario as output. It leverages an anomaly-based algorithm and a fine-grained misuse detection module to assign anomalous scores to host data, constructs the potential attack scenario using a novel anomalous subtree detection algorithm, and generates the interpretable attack scenario graph through a coarse-grained rule matching method. We assess the performance of eaGle using three attack scenarios from the DARPA TC dataset and three deployment scenarios. The results demonstrate that eaGle can effectively uncover the hidden attack scenario within the host data and outperforms three state-of-the-art attack scenario reconstruction systems.

Knowledge of the business relationships between Autonomous Systems (ASes) is the basis for studying many aspects of the Internet. Despite the significant progress achieved by the latest inference algorithms, their inference results still suffer from errors on many special or critical links, thus hindering many relationship-related applications. We take an in-depth analysis on the challenges inherent in inferring AS relationships, including complex routing policies, limited and biased vantage point (VP) coverage, as well as a lack of accurate validation data. To address these challenges, we introduce HELA, a framework for inferring AS relationships with a hybrid of empirical and machine learning algorithms. HELA incorporates an array of grouping, voting, and machine learning algorithms and allows flexible substitution of each. We systematically evaluate various combinations of them to determine the most effective one for HELA. Furthermore, we describe the collection of varied validation datasets, including BGP community and RPSL records from Internet Routing Registries (IRRs), as well as OneStep community. Our up-to-date dataset corrects errors in previous published validation sets, contains 95% more labelled links, and exhibits a closer alignment to actual link distribution. Using routing data and validation datasets composed for each month during$2021\sim 2023$, we access HELA’s superiority in both inference accuracy and stability compared to the state-of-the-art inference algorithms, i.e., AS-Rank, ProbLink, and HELA’s predecessor TopoScope. In particular, HELA achieves up to$2.9\times $reduction on error rates across overall datasets, up to$2.6\times $reduction with a$4.5\times $decrease on standard deviation on incomplete and biased datasets, and up to$1.7\times $reduction on various sources of validation datasets.

Network utility maximization (NUM) is a fundamental problem for network traffic management and resource allocation. Due to the inherent decentralization and complexity of networks, much of the existing research has focused on developing decentralized algorithms for NUM. However, with the rise of Software-Defined Networking (SDN), especially in cloud networks and inter-datacenter networks managed by large enterprises, there has been growing interest in centralized NUM algorithms. To cope with the large and increasing number of flows in such SDN networks, existing studies on centralized NUM focus on the scalability of the algorithm with respect to the number of flows, but the efficiency is ignored. In this paper, we propose a centralized, efficient and scalable algorithm for the NUM problem. By designing smooth utility and penalty functions, we formulate the NUM problem with a smooth objective function, which enables the use of Nesterov’s accelerated gradient method (AGM). We prove that the proposed method achieves an$O(d/t^{2})$convergence rate, demonstrating superior convergence speed with respect to the number of iterationst, and our method is scalable with respect to the number of flowsdin the network. Our smooth objective NUM formulation and AGM are effective not only in simple network scenarios with non-prioritized flows routed on one simple paths, but also in more complex and practical scenarios involving prioritized flows routed across multiple complex paths. Experiment results confirm that our method obtains accurate solutions with fewer iterations, and achieves close-to-optimal network utility.

Deep learning (DL) based anomaly detection has shown great promise in the field of security due to its remarkable performance in various tasks. However, the issue of poor interpretability in DL models has significantly impeded their deployment in practical security applications. Despite the progress made in existing studies on DL explanations, the majority of them focus on providing local explanations for individual samples, neglecting the global understanding of the model knowledge. Furthermore, most explanations for supervised models fail to apply to anomaly detection due to their different learning mechanisms.

The last decade has seen the increasing application of machine learning to various tasks, including network anomaly detection . But anomaly detection methods based on a single machine learning algorithm usually fail to achieve good results, since network traffic have complex and changeable patterns. Therefore, many solutions based on ensemble learning have been proposed to address this problem. However, most previous studies have the main drawback that they overlook the similarity between the weak classifiers , which may degrade the detection performance. What is more, most existing works use offline and supervised algorithms, which means a large number of computing resources and reliable labels are necessary during the training period. In this paper, we propose ADSim , an online, unsupervised, and similarity-aware network anomaly detection algorithm based on ensemble learning. For a similarity-aware scheme, the target of ADSim can be intuitively described as recognizing the similar weak classifiers during the training phase and treat them as a whole. To achieve this, ADSim first incrementally maintains a distance matrix to record the similarity between the classifiers in the training phase and uses Hierarchy Clustering to group the similar classifiers. In the detecting phase, each cluster will be assigned a weight depending on the consistency of the detection results of the classifiers within it. Moreover, the working procedure of ADSim is online and unsupervised, which significantly improves its practicality. We test ADSim on two datasets, MAWILab and CIC-IDS-2017. The results show that ADSim outperforms the state-of-the-art ensemble learning methods and has ideal runtime performance.

Network managers configure networks to enforce various high-level policies, and to respond to the wide range of network events (e.g., attacks, intrusions, malicious route announcements from neighbors) that may occur. It is incredibly difficult to specify these high-level policies in terms of distributed low-level configuration. These high-level policies hold only if the distributed configurations are well equipped to react to unsafe and unreliable environments (e.g., malicious route announcements, unsafe components and devices). Therefore, it is important to proactively verify whether network policies hold across continually changing environments in terms of current network configurations. State-of-the-art policy verification techniques are limited because they can check only the Boolean policies (e.g., forwarding reachability, waypoint or blackhole-freeness). However, many policy violations express themselves in quantitative ways (e.g., a link becomes overloaded). In this paper, we propose quantitative network verification (QNV) analyzing the quantitative policies of networks across unsafe and unreliable environments. QNV translates network configurations into a symbolic simulation model that captures the stable states to which the network forwarding will converge as a result of interactions between routing protocols. It then generates a logical formula matrix that describes network forwarding in the event of failures and verifies quantitative policies based on the formula matrix. We implement QNV and evaluate it on realistic and synthetic configurations. Our evaluation shows that QNV can precisely verify quantitative policies in only a few minutes, even in large networks.

Fine-grained attack detection is an important network security task. A large number of machine learning/deep learning( ML/DL) based algorithms have been proposed. However, attacks not present in the training set pose a challenge to the model (openset problem). Further, ML/DL based models face the problem of adversarial attacks. Despite the large amount of work attempting to address these problems, there are still some challenges as follows. First, the open-set problem in fine-grained attack detection is difficult to solve because there is no effective representation of the distribution of unknown attacks. Second, in the open set environment, how the fine-grained attack detection model resists the adversarial attack is a more difficult problem. For example, the presence of unknown attacks poses a challenge for adversarial defense. For these reasons, we propose the RFG-HELAD model, which consists of aKclassification model based on deep neural network (DNN) with contrastive learning (CL), and aK+ 1 classification model combining a generative adversarial networks (GAN) with two discriminators and deepk-nearest neighbors (Deep kNN). Among them, Deep kNN uses latent features from GAN and contrastive learning as input, which is essentially a distance-based out-of-distribution detection algorithm used to determine unknown attacks. The large category of unknown attacks has been added to theKclassification, so it is aK+ 1 classification. To further improve the robustness of the RFG-HELAD model, we perform Fourier transform as well as feature fusion on the features, and also conduct adversarial training on theKclassification model. Generative adversarial training of our GAN model can implicitly defend against adversarial attack. Experiments show that our model is superior to other state-of-the-art (SOTA) models in the presence of unknown attacks as well as under adversarial attacks. Especially, our model improves the accuracy by at least 18.7% over the corresponding SOTA model with adversarial defense. Further, we discuss the grounded deployment of the model and demonstrate its feasibility.

Numerous distributed applications are deployed in the cross-datacenter networks (Cross-DC) where geographically distributed data centers (DC) are connected by wide area network (WAN). These online applications will generate both intra-datacenter and inter-datacenter traffic, each with distinct requirements and characteristics. We find that existing combined congestion control schemes ignore the interaction of the two types of traffic and the hybrid congestion control schemes fail to accurately estimate cross data center network congestion extent. In this paper, we propose IDCC a delay based congestion control scheme that uses delay to handle congestion inside the DC and in the WAN, respectively. We respectively utilize In-band network telemetry (INT) and round trip time (RTT) to measure the queuing delay inside DC and in the WAN and guarantee the stability of the algorithm by Proportional Integral Derivative (PID). Simultaneously, we demonstrate the empirical results of optimizing flow completion time (FCT) of intra-DC short flow by weight function in cross-DC. We implemented IDCC in simulation platform ns-3 and have performed extensive large scale simulation evaluations. Results show that IDCC decreases the FCT of intra-DC traffic by 3.6× to 12× and improves the throughput of inter-DC traffic by 9% to 16% compared to Gemini, Annulus.

Microservices are becoming more complicated, posing new challenges for traditional performance monitoring solutions. On the one hand, the rapid evolution of microservices places a significant burden on the utilization and maintenance of existing distributed tracing frameworks. On the other hand, complex infrastructure increases the probability of network performance problems and creates more blind spots on the network side. In this paper, we present DeepFlow, a network-centric distributed tracing framework for troubleshooting microservices. DeepFlow provides out-of-the-box tracing via a network-centric tracing plane and implicit context propagation. In addition, it eliminates blind spots in network infrastructure, captures network metrics in a low-cost way, and enhances correlation between different components and layers. We demonstrate analytically and empirically that DeepFlow is capable of locating microservice performance anomalies with negligible overhead. DeepFlow has already identified over 71 critical performance anomalies for more than 26 companies and has been utilized by hundreds of individual developers. Our production evaluations demonstrate that DeepFlow is able to save users hours of instrumentation efforts and reduce troubleshooting time from several hours to just a few minutes.

Inter-DataCenter Wide Area Network (Inter-DC WAN) that connects geographically distributed data centers is becoming one of the most critical network infrastructures. Due to limited bandwidth and inevitable link failures, it is highly challenging to guarantee network availability for services, especially those with stringent bandwidth demands, over inter-DC WAN. We present$\mathsf {TEDAT}$, a novel Traffic Engineering (TE) framework for Diverse Availability Targets (DAT), where a Service Level Agreement (SLA) is defined to ensure that each bandwidth demand must be satisfied with a stipulated probability, when subjected to the network capacity and possible failures of the inter-DC WAN.$\mathsf {TEDAT}$has two core components, i.e., traffic scheduling and failure recovery, which are crystalized through different mathematical models and theoretically analyzed. They are also extensively compared against state-of-the-art TE schemes, using a testbed as well as real trace driven simulations across different topologies, traffic matrices and failure scenarios. Our evaluations show that, compared with the optimal admission strategy,$\mathsf {TEDAT}$can speed up the online admission control by$30\times $at the expense of less than 4% false rejections. On the other hand, compared with the latest TE schemes like FFC and TEAVAR,$\mathsf {TEDAT}$can meet the bandwidth availability SLAs for 23%~60% more demands under normal loads, and when network failure causes SLA violations, it can retain 10%~20% more profit under a pricing and refunding model.

The correctness and reliability of modern networks are often the greatest concerns. A myriad network events like software update, device crash and resource exhaustion, inevitably lead to liveness errors on data plane. This paper focuses on fault detection of the network data plane using test packets. Existing test packet generation techniques are limited in two aspects: i) it is difficult to collect the input data plane snapshot through SNMP or terminals ii) it may rise false negatives due to inconsistent snapshot. In this paper, we propose a new framework, SWIFT, that automatically generates test packets with network configurations. SWIFT minimizes the number of test packets by allowing a packet to go through multiple links or interfaces. For network updates, SWIFT updates test packets in an incremental way to revalidate the network. We evaluate its performance using hundreds of benchmark network configurations. The results show that it takes few seconds to generate test packets to exercise all links and interfaces, and updates the test packets in few seconds for configuration changes. We also deployed a SWIFT prototype in a university network, and successfully detected many network outages.

Network utility maximization (NUM) is a well-studied problem for network traffic management and resource allocation. Because of the inherent decentralization and complexity of networks, most researches develop decentralized NUM algorithms. In recent years, the Software Defined Networking (SDN) architecture has been widely used, especially in cloud networks and inter-datacenter networks managed by large enterprises, promoting the design of centralized NUM algorithms. To cope with the large and increasing number of flows in such SDN networks, existing researches about centralized NUM focus on the scalability of the algorithm with respect to the number of flows, however the efficiency is ignored. In this paper, we focus on the SDN scenario, and derive a centralized, efficient and scalable algorithm for the NUM problem. By the designing of a smooth utility function and a smooth penalty function, we formulate the NUM problem with a smooth objective function, which enables the use of Nesterov's accelerated gradient method. We prove that the proposed method has$O(d/t^{2})$convergence rate, which is the fastest with respect to the number of iterations$t$, and our method is scalable with respect to the number of flows$d$in the network. Experiments show that our method obtains accurate solutions with less iterations, and achieves close-to-optimal network utility.

Host-based threats such as Program Attack, Malware Implantation, and Advanced Persistent Threats (APT), are commonly adopted by modern attackers. Recent studies propose leveraging the rich contextual information in data provenance to detect threats in a host. Data provenance is a directed acyclic graph constructed from system audit data. Nodes in a provenance graph represent system entities (e.g.,processesandfiles) and edges represent system calls in the direction of information flow. However, previous studies, which extract features of the provenance graph, are not sensitive to the small quantity of threat-related entities and thus result in low performance when hunting stealthy threats. We present THREATRACE, an anomaly-based detector that detects host-based threats at system entity level without prior knowledge of attack patterns. We tailor GraphSAGE, an inductive graph neural network, to learn every benign entity’s role in a provenance graph. THREATRACE is a real-time system, which is scalable of monitoring a long-term running host and capable of detecting host-based intrusion in their early phase. We evaluate THREATRACE on five public datasets. The results show that THREATRACE outperforms seven state-of-the-art host intrusion detection systems.

Traditional tools like NetFlow face great challenges as both the speed and the complexity of the network traffic increase. To keep the pace up, we propose HashFlow for more efficient and accurate collection of flow records. HashFlow keeps large flows in its main flow table and uses an ancillary table to summarize the other flows when the main table is full. With ourflow collision resolutionandflow record promotionschemes, a flow in the ancillary table is promoted back to the main flow table with a guaranteed probability when it becomes large enough. These operations can be performed highly efficiently, so HashFlow can keep up with ultra-high traffic speed. We implement HashFlow in a Tofino switch, and using traces from different operational networks, we compare its performance against some state-of-the-art flow measurement algorithms. Our experiments show that, for various types of traffic analysis applications, HashFlow consistently demonstrates clearly better performance than its competitors. For example, the performance of HashFlow in flow size estimation, flow size distribution estimation and heavy hitter detection is up to 21, 60 and 35 percent better than those of the best competitors respectively, and these merits of HashFlow come with almost no degradation of throughput.

Unsupervised Deep Learning (DL) techniques have been widely used in various security-related anomaly detection applications, owing to the great promise of being able to detect unforeseen threats and superior performance provided by Deep Neural Networks (DNN). However, the lack of interpretability creates key barriers to the adoption of DL models in practice. Unfortunately, existing interpretation approaches are proposed for supervised learning models and/or non-security domains, which are unadaptable for unsupervised DL models and fail to satisfy special requirements in security domains.

Edge Computing (EC) provides delay protection for some delay-sensitive network services by deploying cloud infrastructure with limited resources at the edge of the network. In addition, Network Function Virtualization (NFV) implements network functions by replacing traditional dedicated hardware devices with Virtual Network Function (VNF) that can run on general servers. In NFV environment, Service Function Chaining (SFC) is regarded as a promising way to reduce the cost of configuring network services. NFV therefore allows to deploy network functions in a more flexible and cost-efficient manner, and schedule network resources according to the dynamical variation of network traffic in EC. For service providers, seeking an optimal SFC embedding scheme can improve service performance and reduce embedding cost. In this paper, we study the problem of how to dynamically embed SFC in geo-distributed edge clouds network to serve user requests with different delay requirements, and formulate this problem as a Mixed Integer Linear Programming (MILP) which aims to minimize the total embedding cost. Furthermore, a novel SFC Cost-Efficient emBedding (SFC-CEB) algorithm has been proposed to efficiently embed required SFC and optimize the embedding cost. Based on the results of trace-driven simulations, the proposed algorithm can reduce SFC embedding cost by up to 37% compared with state-of-the-art schemes (e.g., RDIP).

Segment Routing (SR) is a source routing paradigm that routes a packet through an ordered list of instructions called segments. It is widely used in Traffic Engineering (TE) because of its simplicity and scalability. Although there are lots of research about TE with SR (SR-TE), fewer consider network failures. The reactive approaches may suffer from latency and update issues, and the proactive approaches don't perform very well because the objectives aren't carefully designed. Besides, although different types of failures are considered, the failure probabilities are ignored. In this paper, we take failure probabilities in to consideration, and propose a proactive 2-SR model 2SRPF to handle SR-TE problem with network failures, aiming at minimizing maximum link utilization (MLU). Considering that severe failures are more noteworthy, we use probability as a severity threshold, and minimize the expectation of the larger MLUs whose corresponding failure states have probabilities sum to a specific threshold value. We solve it with probabilistic risk management. Experiments show that 2SRPF performs well with one threshold setting for different topologies consistently, and gets close to optimal results when network fails.

Inter-DataCenter Wide Area Network (Inter-DC WAN) that connects geographically distributed data centers is becoming one of the most critical network infrastructures. Due to limited bandwidth and inevitable link failures, it is highly challenging to guarantee network availability for services, especially those with stringent bandwidth demands, over inter-DC WAN. We present BATE, a novel Traffic Engineering (TE) framework for bandwidth availability (BA) provision, which aims to ensure that each bandwidth demand must be satisfied with a stipulated probability, when subjected to the network capacity and possible failures of the inter-DC WAN. The three core components of BATE, i.e., admission control, traffic scheduling and failure recovery, are formulated through different mathematical models and theoretically analyzed. They are also extensively compared against state-of-the-art TE schemes, using a testbed as well as real trace driven simulations across different topologies, traffic matrices and failure scenarios. Our evaluations show that, compared with the optimal admission strategy, BATE can speed up the online admission control by 30x at the expense of less than 4% false rejections. On the other hand, compared with the latest TE schemes like FFC and TEAVAR, BATE can meet the bandwidth availability targets for 23%~60% more demands under normal loads, and when network failure causes BA targets violations.

With the increasing network security risks, network intrusion detection technology has become more important. At present, machine learning is applied in most advanced traffic anomaly detection algorithms, but these algorithms have three main shortcomings. First, algorithms using deep neural network are highly complex and not suitable for real-time online processing. Second, algorithms based on supervised learning require training on huge labeled data sets, which are limited and insufficient. Third, most algorithms have such poor generalization ability and portability that they are less suitable for real-world environments. Therefore, we propose a novel network anomaly detection model, STRAD. We use Word2vec and Damped Incremental Statistics algorithm for spatiotemporal features extraction, latent space compression (LSC) for feature vectors compression and an unsupervised one-class classifier for anomaly detection. Our evaluations show that STRAD has a better performance than other state of the art algorithms.

Flow-based network measurement enables operators to perform a wide range of network management tasks in a scalable manner. Recently, various algorithms have been proposed for flow record collection at very high speed. However, they all focus on processing traffic in a short time window, but overlook the fact that flow measurements are typically needed continuously for unlimited time. To this end, we propose a new algorithm named SuperFlow to support continuous and accurate flow record collection at very high speed by monitoring the flow activeness and exporting the inactive records from the data plane automatically. Our data structures and the corresponding algorithms are carefully designed and analyzed, so the above goal is achieved with limited memory and bandwidth consumption. We implement SuperFlow on both x86 CPU and state-of-the-art PISA target. Comprehensive experiments show that SuperFlow consistently outperforms its competitors significantly. Especially, compared with the best competitor, it records around 136.7% more flows, reduces the error in flow size estimation by 51.5%, and reduces the memory or bandwidth consumption by up to 71.0%, while bringing only negligible throughput degradation.

Machine learning (ML), especially deep learning (DL) techniques have been increasingly used in anomaly-based network intrusion detection systems (NIDS). However, ML/DL has shown to be extremely vulnerable to adversarial attacks, especially in such security-sensitive systems. Many adversarial attacks have been proposed to evaluate the robustness of ML-based NIDSs. Unfortunately, existing attacks mostly focused on feature-space and/or white-box attacks, which make impractical assumptions in real-world scenarios, leaving the study on practical gray/black-box attacks largely unexplored. To bridge this gap, we conduct the first systematic study of the gray/black-box traffic-space adversarial attacks to evaluate the robustness of ML-based NIDSs. Our work outperforms previous ones in the following aspects: (i) practical -the proposed attack can automatically mutate original traffic with extremely limited knowledge and affordable overhead while preserving its functionality; (ii) generic -the proposed attack is effective for evaluating the robustness of various NIDSs using diverse ML/DL models and non-payload-based features; (iii) explainable -we propose an explanation method for the fragile robustness of ML-based NIDSs. Based on this, we also propose a defense scheme against adversarial attacks to improve system robustness. We extensively evaluate the robustness of various NIDSs using diverse feature sets and ML/DL models. Experimental results show our attack is effective (e.g., >97% evasion rate in half cases for Kitsune, a state-of-the-art NIDS) with affordable execution cost and the proposed defense method can effectively mitigate such attacks (evasion rate is reduced by >50% in most cases).

Cloud technology has brought great convenience to enterprises as well as customers. System logs record notable events and are becoming valuable resources to track and investigate system status. Detecting anomaly from logs as fast as possible can improve the quality of service significantly. Although many machine learning algorithms (e.g., SVM, Logistic Regression) have high detection accuracy, we find that they assume data are clean and might have high training time. Facing these challenges, in this paper, we propose Robust Online Evolving Anomaly Detection (ROEAD) framework which adopts Robust Feature Extractor (RFE) to remove the effects of noise and Online Evolving Anomaly Detection (OEAD) to dynamic update parameters. We propose Online Evolving SVM (OES) algorithm as the example of online anomaly detection methods. We analyze the performance of OES in theory and prove the performance difference between OES and the best hypothesis tends to zero as time goes infinity. We compare the performance of ROEAD against state-of-the-art anomaly detection algorithms using public log datasets. The results demonstrate that ROEAD is able to remove the effects of noise and OES can improve the detection accuracy by more than 40%.

Knowledge of the Internet topology and the business relationships between Autonomous Systems (ASes) is the basis for studying many aspects of the Internet. Despite the significant progress achieved by latest inference algorithms, their inference results still suffer from errors on some critical links due to limited data, thus hindering many applications that rely on the inferred relationships. We take an in-depth analysis on the challenges inherent in the data, especially the limited coverage and biased concentration of the vantage points (VPs). Some aspects of them have been largely overlooked but will become more exacerbated when the Internet further grows. Then we develop TopoScope, a framework for accurately recovering AS relationships from such fragmentary observations. TopoScope uses ensemble learning and Bayesian Network to mitigate the observation bias originating not only from a single VP, but also from the uneven distribution of available VPs. It also discovers the intrinsic similarities between groups of adjacent links, and infers the relationships on hidden links that are not directly observable. Compared to state-of-the-art inference algorithms, TopoScope reduces the inference error by up to 2.7-4 times, discovers the relationships for around 30,000 upper layer hidden AS links, and is still more accurate and stable under more incomplete or biased observations.

Anycast, as a network layer solution for providing faster and stabler services to end-users, is actively deployed on the Internet today. A common argument is that the underpinning routing system will automatically direct users to the closest site among the set of anycast sites. However, anycast path inflations are observed, where users are unexpectedly directed to a site farther away. In this paper, we study a specific kind of anycast path inflation called AS-level Anycast Path Inflation (AAPI). AAPI means, after the deployment of an anycast site in a different Autonomous System (AS), the number of ASes that traffic passes through is larger than that before, so that users may experience increased latencies or be exposed to higher inter-domain security risks. We discuss AAPI’s causes, analyse its characteristics, and propose deployment guidance. In particular, we classify AAPI in two basic forms, i.e. Route Suppression (RS) and Route Promotion (RP), and present their various characteristics as well as their possible coupling. We propose Conflict Point (CP), a topological feature which represents the intrinsic conflict between routing policies and AS path length at these nodes, to further study the necessary and sufficient conditions for AAPI. And based on the properties of CP, we give some suggestions on anycast deployment strategy to avoid AAPI and verify them by simulation.

Segment Routing (SR) is a source routing paradigm which is widely used in Traffic Engineering (TE). By using SR, a node steers a packet through an ordered list of instructions called segments. By some extensions of interior gateway protocol, SR can be applied to IP/MPLS or IPv6 network without signal protocol. SR over IPv6 (SRv6) is attracting wide attention because of its interoperation ability with IPv6. However, upgrading the existing IPv6 network directly to a full SRv6 one can be difficult, because large-scale equipment replacement or software upgrade may cause economic and technical problems. TE in partially deployed SR network is becoming a hot research topic. In this paper, we propose the TE algorithm Weight Adjustment-SRTE (WA-SRTE) in partially deployed SRv6 network, in which SRv6 capable nodes are dispersedly deployed. Our objective is to minimize the network's maximum link utilization. WA-SRTE converts the TE problem into a Deep Reinforcement Learning problem and optimizes the OSPF weight, SRv6 node deployment and traffic paths simultaneously. Besides, traffic variation is also considered and we use a representative Traffic Matrix (TM) to epitomize the traffic characteristics over a period of time. Experiments demonstrate that with 20% to 40% of the SRv6 nodes deployed, we can achieve TE performance as good as in a full SR network for the experiment topologies. The results with WA remarkably outperform the results without it. Our algorithm also gets near-optimal results with changing traffic.

Collecting flow records is a common practice of network operators and researchers for monitoring, diagnosing and understanding a network. Traditional tools like NetFlow face great challenges when both the speed and the complexity of the network traffic increase. To keep pace up, we propose HashFlow, a tool for more efficient and accurate collection and analysis of flow records. The central idea of HashFlow is to maintain accurate records for elephant flows, but summarized records for mice flows, by applying a novel collision resolution and record promotion strategy to hash tables. We have implemented HashFlow as well as several latest flow measurement algorithms in a P4 software switch, and use traces from different operational networks to evaluate the algorithms. In these experiments, for various types of traffic analysis applications, HashFlow consistently demonstrates a clearly better performance against its state-of-the-art competitors. For example, using a small memory of 1 MB, HashFlow can accurately record around 55K flows, which is often 12.5% higher than the others. For estimating the sizes of 50K flows, HashFlow achieves a relative error of around 11.6%, while the estimation error of the best competitor is 42.9% higher. It detects 96.1% of the heavy hitters out of 250K flows with a size estimation error of 5.6%, which is 11.3% and 73.7% better than the best competitor respectively. At last, we show these merits of HashFlow come with almost no degradation of throughput.

Traffic matrix (TM) is a critical information for network operation and management, especially for traffic engineering (TE). Due to the technical and mercantile problems, real time measurement for TM is difficult in large scale networks. In this paper, we focus on predicting TM for dynamic traffic engineering. We propose several TM prediction methods based on Neural Networks (NN) and predict TM from three perspectives: predict the overall TM directly, predict each origin-destination (OD) flow separately and predict the overall TM combined with key element correction. In addition to the prediction accuracy, we evaluate different prediction methods through the performance of TE, as well as the prediction time. We test the proposed methods by real world datasets from Abilene, CERNET and GÉANT. The experiment results show that prediction methods based on Recurrent Neural Networks (RNN) can achieve better prediction accuracy than methods leveraging Convolutional Neural Networks (CNN) and Deep Belief Networks (DBN). Predicting each OD flow through RNN models can further improve the prediction accuracy, as well as the performance of TE under the OSPF network scenario, the SDN/OSPF hybrid network scenario and the multi-commodity flow problem scenario. However, it takes longer prediction time for predicting each OD flow sequence. In contrast, predicting the overall TM combined with key element correction can provide a trade-off between the TE results and the prediction overhead, which is more appropriate for dynamic TE in the above three scenarios.

Data center has become an important facility for hosting various applications. For data center networks, deadline missing rate and average flow completion time are two main metrics for the performance of applications. In this paper, we find deadline-aware methods can only reduce the percentage of flows missing deadline, while flowsize-aware and information-cumulative methods can only optimize the average flow completion time. However, traffic in data center is the mixture of various flows and focusing on the single goal is not enough. We advocate to incorporate deadline and flow duration time into flow rate control. Then we design DA&FD (Deadline-Aware and Flow Duration) based rate control mechanism and analyze its performance in theory. At last, we evaluate DA&FD under different topologies, real world traffic and load scenarios, both by simulation and in real testbed. Our results show that DA&FD performs close to D2TCP and about 15%, 25%, 30%, 35% better than Ameon, L2DCT, Karuna, DCTCP on deadline missing rate. For average FCT, the performance of DA&FD is similar to L2DCT and compared with Ameon, D2TCP, Karuna, DCTCP, DA&FD can reduce average FCT by 10%, 15%, 20%, 25%.

Traditional network resource management mechanisms are mainly flow or packet based. Recently, coflow has been proposed as a new abstraction to capture the communication patterns in a rich set of data parallel applications in data centers. Coflows effectively model the application-level semantics of network resource usage, so high-level optimization goals, such as reducing the transfer latency of applications, can be better achieved by taking coflows as the basic elements in network resource allocation or scheduling. Although efficient coflow scheduling methods have been studied, in this paper, we advocate to schedule weighted coflows as a further step in this direction, where weights are used to express the importances or priorities of different coflows or their corresponding applications. We propose the Weighted Coflow Completion Time (WCCT) minimization problem and a (2-2/n+1)-approximate optimal offline algorithm, where n is the concurrent number of coflows. We then design an information-agnostic online algorithm named IAOA to dynamically schedule coflows according to their weights and the instantaneous network condition. We also design and implement a coflow scheduling system named FlyTransfer, which can use the online algorithm as its scheduling method. We test the performance of FlyTransfer by trace-driven simulations as well as real deployment in openstack. Our evaluation results show that, compared to the latest information-agnostic coflow scheduling algorithms, FlyTransfer can reduce more than 40 percent of the WCCT, and more than 30 percent of the completion time for coflows with above-the-average level of importance. It even outperforms the most efficient clairvoyant coflow scheduling method by reducing around 30 percent WCCT, and 25- 30 percent of the completion time for coflows with above-the-average importance, respectively.

Traffic Engineering is an efficient tool to balance the network flows and, thus improving the network performance with limited network resources. The goal of traffic engineering is to find an efficient and robust routing to balance the flows with changing traffic. Multiple traffic matrices are good representatives of the changing traffic. The emergence of Software Defined Networking (SDN) provides us a more flexible way to route the network flows with multiple traffic matrices. We expect to optimize the routing of the average case performance over multiple traffic matrices and, at the same time, bound the worst case performance for some unexpected traffic in hybrid SDN network. In this paper, we first formulate the problem of optimizing both the average case and worst case performance of the routing over multiple traffic matrices. Then, we prove the problem is NP-hard and propose a heuristic algorithm to solve it. Finally, we evaluate our algorithm with real traffic datasets. Through extensive experiments, we observe that the worst case performance of our routing can be dramatically improved by 32.15% with a little sacrifice of the average case performance by 2.01% and demonstrate the effectiveness of our algorithm in optimizing both the average case and worst case performance of routing.

With the rapidly growing of geo-distributed applications in the Internet, there is a huge amount of data generated in geo-distributed datacenters everyday. However, because of region privacy concerns and limitation of inter-DC WAN bandwidth, moving all the geo-distributed data to a single datacenter for centralized processing is not practical. Therefore, we intend to process the data where it generates by the big data applications and optimize the coflow routing in inter-DC WAN to improve the performance of the applications. Previous studies consider only routing or task placement optimization, which is inefficient. In this paper, we propose an algorithm PRO with an approximation ratio (1+\epsilon) that jointly optimize the placement of tasks and the routing of a coflow. Our proposed algorithm can efficiently reduce the coflow completion time.

Multiple SDN applications can make several harmful interferences unintentionally, although each individual application may be properly developed. This paper proposes a Multiple SDN Applications Interference Detector (MSAID). To bridge the gap between the source code of applications and the actual interferences, we leverage symbolic execution and constraint solving to obtain how the event handler handles the input messages. We then analyze the complex interaction of multiple applications and present novel methods to identify the interferences. Finally, we evaluate its correctness and prove its usefulness with a series of SDN applications.

Recently, coflow has been proposed as a new abstraction to capture the communication patterns in a rich set of data parallel applications in data centers. Coflows effectively model the application-level semantics of network resource usage, so high-level optimization goals, such as reducing the transfer latency of applications, can be better achieved by taking coflows as the basic elements in network resource allocation or scheduling. Although efficient coflow scheduling methods have been studied, in this paper, we propose to schedule weighted coflows as a further step in this direction, where weights are used to express the emergences or priorities of different coflows or their corresponding applications. We design an information-agnostic online algorithm to dynamically schedule coflows according to their weights and the instantaneous network condition. Then We implement the algorithm in a scheduling system named Yosemite. Our evaluation results show that, compared to the latest information-agnostic coflow scheduling algorithms, Yosemite can reduce more than 40% of the WCCT (Weighted Coflow Completion Time), and more than 30% of the completion time for coflows with above-the-average level of emergence. It even outperforms the most efficient clairvoyant coflow scheduling method by reducing around 30% WCCT, and 25%~30% of the completion time for coflows with above-the-average emergence, respectively.

With the deployment of big data applications, more and more data are stored in the online storage. Erasure coding storage system has been widely used by companies such as Google and Facebook, since it provides space-optimal data redundancy to protect against data loss. In erasure coding storage system, (n, k) MDS erasure code is used to divide file into n chunks. When a user want to access the file, any subset of k out of n chunks will be needed to reconstruct the file. In this case, how to select k out of n chunks and how to let the chunks transfer quickly become important problems. In this paper, we joint the two problems together to optimize. Our optimization goal is to minimize average file access time (FAT). To achieve this, we propose smallest load first heuristic to do source selection and design an online algorithm to reduce chunks transfer latency. Base on this, we design and implement D-Target, a centralized scheduler that tries to minimize average FAT in distributed erasure coding storage system. We then test D-Target's performance by trace-driven simulation. Results show that, for the trace of AT&T, D-Target performs 2.5×, 1.7×, 1.8×, 3.6× better than TCP, Aalo, Barrat and pFabric respectively.

Nowadays, there are two major challenges to detect traffic anomalies in a large scale network. One is how to handle huge amounts of traffic data when we detect traffic anomalies in a network, and the other is how to carry out fast and detailed detection and classification. To address these two challenges, we propose a Change based Effective Frequent flow Features approach (CEFF), which can quickly obtain the anomaly detection and classification results by scanning the flow data only once. We implement CEFF for both offline and online detection and classification in Spark, a popular big data processing platform. Besides, we evaluate CEFF using China Telecom NetFlow format data in experiments, and make comparisons between CEFF and Shannon entropy based method, which has been proved to be effective for traffic anomaly detection. The experiment results show that CEFF has excellent performance in traffic anomaly detection and classification.

The programmability of Software-Defined Networking (SDN) challenges the correctness and reliability of networks. There may be design flaws as well as implementation bugs in SDN applications. White-box testing methods with formal models rely on source codes, which limits the applicability of these methods. Black-box methods without behavior models cannot systematically cover an application's functions. Most previous work has mainly focused on design flaws and has ignored implementation bugs. In this paper, we propose a new black-box test framework to detect both design flaws and implementation bugs. Following this test framework, we propose a new model, Information Table Extended State Machine (IT-EFSM), combining a group of parallel state machines and an abstract topology to specify the SDN applications. We employ a model checking tool to generate tests against design flaws and propose a test generation based on partial composition, symmetry simplification on the topology and topology simulated execution to expose implementation bugs. The experimental results of the testing process demonstrate the effectiveness and applicability of our method.

In typical data center networks, an overwhelming majority of the flows are smaller than 200 KB in size, while most transmitted bytes are from a small fraction of large flows. The small flows are usually from the applications interacting with end users, thus they require small completion times. Meanwhile, the data center owners hope to keep the high throughput of the network to make full use of their investments on the network devices. To reduce the completion times of small flows while maintaining the high throughput of the network, we propose a novel transport algorithm, SCT (Transport with Slight Congestion), in this paper. SCT gives small flows higher priority by increasing their congestion windows at a higher rate. Moreover, SCT keeps the network to be in high utilization, thus the throughput of network is guaranteed. Extensive simulations show that SCT can reduce the average completion time of small flows by up to 48% at the expense of degrading the throughput of network by 5% only, compared with DCTCP.

Data Center is now becoming an important facility for many applications (e.g, web search and retail). As TCP can't meet applications' demands for latency and throughput, many tcp-based protocols (e.g, DCTCP, D2TCP, L2DCT) have been proposed. Among them, protocols such as D2TCP incorporate explicit deadline into congestion window adjustment procedure to guarantee flows' latency and protocols such as L2DCT consider flow size when computing congestion window adjustment factor to guarantee the throughput of short flows. These two methods work well at some scenery but they have some deficiencies on two aspects. Firstly, we find that they can only reduce the percentage of flows missing deadline or reduce flow completion time, but can not meet both the goals simultaneously. Secondly, most of these methods need the user to know flow information (e.g, deadline, flow size), which may be hard to know exact value beforehand. In this paper, we advocate to use flow duration time into congestion window adjustment procedure. Based on this, we propose FDRC-Flow Duration Time based Rate Control algorithm. We find that without knowing flow information beforehand, FDRC can achieve the goal of reducing the percentage of flows missing deadline and cutting average flow completion time simultaneously. We theoretically analyze FDRC's behavior and implement FDRC into ns-2 as well as linux kernel. Our experiments show that FDRC performs better than D2TCP and L2DCT at nearly all the scenarios. On average, it performs 30% better than the state-of-art deadline-aware congestion control protocol D2TCP and 10% better than the state-of-art flowsize-aware protocol L2DCT.

To enhance the network reliability without incurring significant extra overhead, we propose a novel link protection scheme, Hybrid Link Protection (HLP), to achieve failure resilient routing. Compared to previous schemes, HLP ensures high network availability in a more efficient way, and also provides other features such as load balancing. HLP is implemented in two stages. Stage one provides Multiple Next-hop Protection (MNP), where only one single Shortest Path Tree (SPT) needs to be constructed on each node to find multiple next hops for any destination. Stage two provides Backup Path Protection (BPP), where only a minimum number of links need to be protected, using special paths and packet headers, to meet the network availability requirement. We evaluate these algorithms in a wide spread of relevant topologies, both real and synthetic, and the results reveal that HLP can achieve high network availability without introducing conspicuous overhead.

Data center network has become an important facility for hosting various online services and applications, and thus its performance and underlying technologies are attracting more and more interests. In order to achieve better network performance, recent studies have proposed to tailor data center network traffic management in different aspects, devising various routing and transport schemes. In particular, for applications that must serve users in a timely manner, strict deadlines for their internal traffic flows should be met, and are explicitly taken into consideration in some latest flow rate control or scheduling algorithms in data center networks. In this paper, we advocate that when designing such deadline-aware rate control schemes, a simple principle should be followed: flows with different deadlines should be differentiated in their bandwidth allocation/occupation, and the more traffic load, the more differentiation should be made. We derive sufficient and necessary conditions for a flow rate control scheme to follow this principle, and present a simple congestion control algorithm called Load Proportional Differentiation (LPD) as its application. We have evaluated LPD under different topologies and load scenarios, both by simulation and in real testbed. Our results show that LPD nearly always outperforms D2TCP, a latest deadline-aware rate control scheme, and often reduces the number of flows missing their deadlines by more than 50%. We also give some other applications of this principle, for example, in reducing flow completion time.

Traffic engineering is a method to balance the flows and optimize the routing in the network. Software defined networking is a new network architecture and we can gain great benefit by migrating the traditional IP network to the SDN-enabled network from the perspective of traffic engineering. However, due to the economical, organizational and technical challenges, migrating to the network with a full deployment of SDN routers is impractical in the short term. It is a desirable choice to deploy SDN incrementally. In this paper, we seek to search for an optimal migration sequence of the legacy routers to SDN-enabled routers so that we can decide where and how many routers to migrate firstly. Our main contribution is that we propose a heuristic algorithm, i.e., genetic algorithm, to seek a migration sequence of the routers that obtains the most of the benefit from the perspective of traffic engineering. We evaluate the algorithm by conducting simulation experiments, making comparison to the greedy migration algorithm and static migration algorithms that we propose. The experiments exhibit that the genetic algorithm, outperforms the other migration algorithms in searching for a migration sequence. When properly deployed, about a migration of 40% of routers reaps most of the benefit.

The internet faces severe routing scalability problem - the rapid increasing of prefix and updates. There are two classes of factors that contribute to scalability problem: inappropriate allocation of IP addresses and inappropriate usage of them. Existing works mainly focus on inappropriate usage of allocations, so this work focuses on inappropriate allocation of IP addresses. We carry out the measurement from two perspectives. From the perspective of each AS, we classify preprocessed prefixes according to their contribution to aggregating addresses inside the AS. We find that factors due to inappropriate allocation of IP address contribute more than that of inappropriate usage of them in values. From the perspective of Internet, we propose a new metric Brother Prefix Distance, which implies the likelihood of aggregating addresses of different ASes. We find that Brother Prefix Distance increase over time, which implies that impact of address allocation on routing scalability increases over time.

The diversity of QoS (Quality-of-Service) requirements of Internet applications motivates various QoS routing algorithms that take different QoS metrics into consideration. Routing algebra has been proposed as a framework to study the fundamental properties of QoS routing algorithms, such as their optimality and loop-freeness. However, for multipath QoS routing, little has been done in these aspects. Existing multipath QoS routing algorithms often take a rather conservative approach to guarantee loop-freeness, at the cost of efficiency. On the other hand, simply adapting existing efficient multipath routing algorithms to support various QoS metrics cannot guarantee correctness. In face of that, we propose a routing metric algebra for multipath QoS routing in link state networks, where a key property of the routing metrics called isotonicity, which plays an important role. To let routers efficiently and correctly find multiple next-hops for each destination, we also develop two distributed multipath QoS routing algorithms. The algorithms are run locally and independently, without exchanging messages other than the basic link states. They are specifically tailored for algebras with strict or non strict isotonicity, and their correctness are formally proved.

Today network traffic anomaly detection is very challenging in a big and constantly changing network, because there are millions of flows being transferred in a network at the same time, and the flow numbers change all the time. Although traditional information entropy has been proved to be an effective metric on network traffic anomaly detection, such a metric shows some limitations in large scale networks with constantly changing flow numbers, and it makes the traditional entropy inefficient for traffic anomaly detection. Another challenge is how to process large-scale traffic data in a scalable way. In this paper, we propose Adjustable Piecewise Entropy for traffic anomaly detection, and implement Adjustable Piecewise Shannon entropy in Hadoop platform with a cluster of five servers in Tsinghua University Campus Network. Furthermore, we analyze and validate Adjustable Piecewise Entropy in both mathematics and experiments. The experiment results show that Adjustable Piecewise Entropy has better performance for traffic anomaly detection.

Nowadays, due to the rapid growing popularity of Internet, the global routing system suffers from great scalability problem. Many solutions are proposed to solve the problem, including FIB aggregation, core/edge separation solutions, et al. The limitation of these existing solutions is that they all make the assumption that all addresses in the Internet must be globally visible and these routing information must be spread worldwide. We propose to make some network prefixes globally invisible and eliminate the routing information of these prefixes from the global routing system to further improve the scalability of the Internet. Our solution distinguishes content provider networks (containing content providers) from content consumer networks (containing only content consumers) and removes the routing information of content consumer networks. In order to cope with the communication between content consumer networks and content provider networks, we propose HSR (Hybrid Source Routing), in which source routing is used to assist network-based routing to achieve end-to-end reachability. We carry out performance evaluation by simulation, and experimental results show that if only top 1 million websites are globally visible, the visible ASes, prefixes in forwarding table and received updates can be reduced to 40%, 12% and 10%.

Traffic engineering under OSPF routes along the shortest paths, which may cause network congestion. Software Defined Networking (SDN) is an emerging network architecture which exerts a separation between the control plane and the data plane. The SDN controller can centrally control the network state through modifying the flow tables maintained by routers. Network operators can flexibly split arbitrary flows to outgoing links through the deployment of the SDN. However, SDN has its own challenges of full deployment, which makes the full deployment of SDN difficult in the short term. In this paper, we explore the traffic engineering in a SDN/OSPF hybrid network. In our scenario, the OSPF weights and flow splitting ratio of the SDN nodes can both be changed. The controller can arbitrarily split the flows coming into the SDN nodes. The regular nodes still run OSPF. Our contribution is that we propose a novel algorithm called SOTE that can obtain a lower maximum link utilization. We reap a greater benefit compared with the results of the OSPF network and the SDN/OSPF hybrid network with fixed weight setting. We also find that when only 30% of the SDN nodes are deployed, we can obtain a near optimal performance.

Existing tools for Software-Defined Networking (SDN) data plane testing can be classified into two classes: white box and black-box. For the former, all or part of source codes should be accessed. But for testers outside the manufacturers, the accessing of source code is impossible or very difficult in most cases, especially for hardware devices. For the latter, test cases are manually developed, which cannot ensure the coverage. In this paper, we present a model based black-box systematic testing method for SDN data plane. We propose a new model, Pipelined Extended Finite State Machine (Pi-EFSM), to specify the multiple-level pipeline of SDN data plane. For the Pi-EFSM model, we present a 3-phase systematic test generation approach. By using a hierarchical test generation strategy, the proposed test generation method can alleviate state space explosion to some extent. Our test generation method can achieve the systematic coverage towards the elements of the model. We apply our method in the testing of Open Flow switches (specification version 1.3.0). We build a Pi-EFSM model for Open Flow switches and derive the executable test sequences. Some implementation faults and specification confusions are exposed when we test two switches, Open switch 2.1.0 and CPqD Open Flow 1.3 Software Switch.

Current intra-domain routing protocols computes only shortest paths for any pair of nodes which cannot provide good fast reroute when network failures occur. Multipath routing can be fundamentally more efficient than the currently used single path routing protocols. It can significantly reduce congestion in network by shifting traffic to unused network resources. This improves network utilization and provides load balancing. To enhance failure resiliency we propose a new scheme More Nodes Have At Least Two Choices (MNTC) where the goal is how to maximize the number of nodes that have at least two next-hops towards their destinations. We evaluate the algorithm in a wide space of relevant topologies and the results show that it can achieve good reliability while keeping low stretch.

The Internet is playing an increasingly crucial role in both personal and business activities. Handling link failures is an important task in designing routing protocols. To enhance the network availability without incurring significant extra overhead, we propose a novel link protection algorithm, Hybrid Link Protection Scheme (HLP) to achieve failure resilient routing.

As the soul of the Software-Defined Networking (SDN), the quality of control plane applications determines the reliability of the networks. Unfortunately, better programmability in SDN increases the risk of bugs and challenges for testing. Because manually testing seems to be inefficient, automatic testing methods become promising alternative. Both white-box method with models and black-box method without model have limitations. In this paper, we propose a formal model for blackbox testing of SDN applications. We use a group of components to describe the data structure stored in the applications and the system behaviors. It is easier and more natural to specify applications. Based on our models, we present our work-in-progress testing framework. It can iteratively improve the design model with model verification and expose implement bugs with model-based testing.

Current researches on model-based testing mainly focus on the single component model, such as FSM (Finite State Machine) and EFSM (Extended FSM). To model and test parallelism and concurrency among different protocol components, traditional CFSM (Communicating FSMs) models communication as asynchronous message exchange, which is not suitable for the scenario that parallel protocol components read shared variables from each other. We have developed Parallel Parameterized Extended Finite State Machine (PaP-EFSM) to handle this situation. In this paper, we present a hierarchical test generation approach for PaP-EFSMs based on reachability graphs. The combination of bottom-up reachability graph generation and top-down test sequence generation ensures the executability of the test sequences and alleviates state explosion. We apply this method to the conformance testing of SAVI, a real protocol for anti-spoofing of IP source addresses. We build a set of PaP-EFSMs for SAVI and derive the executable test sequences, which expose many implementation faults when applied to real devices from 4 different vendors.

High reliability is always pursued by network designers. Multipath routing can provide multiple paths for transmission and failover, and is considered to be effective in the improvement of the network reliability. However, existing multipath routing algorithms focus on how to find as many paths as possible, rather than their computation or communication overhead. We propose a dynamic distributed multipath algorithm (DMPA) to help a router in a link-state network find multiple nexthops for each destination. A router runs the algorithm locally and independently, where only one single shortest path tree (SPT) needs to be constructed, and no message other than the basic link states is disseminated. DMPA maintains the SPT and dynamically adjusts it in response to network state changes, so the sets of nexthops can be incrementally and efficiently updated. At the same time, DMPA guarantees loop-freeness of the induced forwarding path by a partial order of the routers underpinning it. We evaluate DMPA and compare it with some latest multipath algorithms, using a set of real, inferred and synthetic topologies. The results show that DMPA can provide good reliability and fast recovery for the network with very low overhead.

Nowadays, the global routing system suffers from great scalability problem. Core/edge separation solutions are proposed to solve the problem. However, they bring a global mapping system which might also suffer from scalability problem. We come up with an idea to reduce the necessary routing or mapping information, which is to separate content provider networks (containing content providers) from content consumer networks (containing only content consumers) and remove the routing or mapping information of content consumer networks. We combine this idea with core/edge separation solutions to reduce the necessary information in the global mapping system.

High reliability is always pursued by network and protocol designers. Multipath routing can provide multiple paths for transmission and failover, and is considered to be effective in the improvement of network reliability. To compute multiple paths efficiently, we present MLSA, a tree based link-state multipath algorithm, to help a node to find multiple next hops for each destination. On each node, only a single tree needs to be maintained, locally and independently, while no other information than the basic link states need to be exchanged. We also prove the loop-freeness of MLSA, guaranteed by a underlying partial order established over the nodes. We evaluate MLSA with both real and synthetic topologies. The simulation results show that, MLSA can achieve comparable reliability as the naive algorithms based on shortest path trees, with much less computation overhead.

Software-defined networking (SDN) is an emerging network architecture and OpenFlow is one of the representative works in SDN. As a possible approach towards future network, it has been introduced into a lot of application scenarios. Although SDN/OpenFlow have a lot of advantages, it is still debatable that whether they can manipulate a significant amount of real-life traffic when they are deployed in a large-scale ISP (Internet Service Provider) network. However, there are few studies of performance evaluation of SDN/OpenFlow system with real-life traffic. In this paper we present OFSim, an event-driven OpenFlow simulator that supports the performance evaluation of OpenFlow system with packet-level real-life traffic traces. We use OFSim to perform evaluations with real-life ISP traffic and experimental results show that: (i) Current OpenFlow switch implementations cannot meet the need of real-life ISP traffic; (ii) Although the issue of controller scalability exists, greater performance bottleneck may be located in the current OpenFlow switches, and the flow table entry installation delay is a more pressing issue. This study can be helpful to better understand the performance bottleneck of OpenFlow system under the scenario in an ISP network.

Border Gateway Protocol (BGP) plays a critical role in the Internet inter-domain routing reliability. Invalid routes generated by mis-configurations or forged by malicious attacks may hijack the traffic and devastate the Internet routing system, but it is unlikely that a secure BGP can be deployed in the near future to completely prevent them. Although many hijacking detection systems have been developed, they more or less have weaknesses such as long detection delay, high false alarm rate and deployment difficulty, and no systematic detection results have been studied.

Routing failures are common on the Internet and routing protocols can not always react fast enough to recover from them, which usually cause packet delivery failures. To address the problem, fast reroute solutions have been proposed to guarantee reroute path availability and to avoid high packet loss after network failures. However, existing solutions are often specific to single type of routing protocol. It is hard to deploy these solutions together to protect Internet routing including both intra- and inter-domain routing protocols because of their individual computational and storage complexity. Moreover, most of them can not provide effective protection for traffic over failed links, especially for the bi-directional traffic. In this paper, we propose a unified fast reroute solution for routing protection under network failures. Our solution leverages identifier based direct forwarding to guarantee the effectiveness of routing protection and supports incremental deployment. In particular, enhanced protection cycle (e-cycle) is proposed to construct rerouting paths and to provide node and link protection for both intra- and inter-domain routing protocols. We evaluate our solution by simulations, and the results show that the solution provides 100% failure coverage for all end-to-end routing paths with approximately two extra Forwarding Information Base (FIB) entries. Furthermore, we report an experimental evaluation of the proposed solution in operational networks. Our results show that the proposed solution effective provides failure recovery and does not introduce processing overhead to packet forwarding.

The information of temporal correlations among network-wide data flows is crucial to a wide range of network management applications, such as root-cause analysis, threat monitoring, and traffic profiling. While several prior work had only studied the centralized and offline computation of flow correlations, we present DisTrack, a space-efficient network management mechanism for online tracking of network-wide temporal flow correlations. The major benefits of DisTrack include low space complexity, high processing speed, and ease of distributed deployment. This paper presents its randomized data structures, with theoretical analysis on the trade-off between space complexity and accuracy. We further provide extensive empirical evaluations on real network traces.

Routing failures are common on the Internet and routing protocols can not always react fast enough to recover from them, which usually causes packet delivery failures. To address the problem, fast reroute solutions have been proposed to guarantee reroute path availability and to avoid high packet loss after network failures. However, existing solutions are often specific to single type of routing protocol. It is hard to deploy these solutions together to protect Internet routing including intra- and inter-domain routing because of their individual computational and storage complexity. Moreover, most of them can not provide effective protection for traffic over failed links, especially for the bi-directional traffic. In this paper, we propose a unified fast reroute solution for routing protection under network failures. Our solution leverages identifier based direct forwarding to guarantee the effectiveness of routing protection and supports incremental deployment. In particular, enhanced protection cycle (e-cycle) is proposed to construct rerouting paths and to provide node and link protection for both intra- and inter-domain routing. We evaluate our solution by simulations, and the results show that the solution provides 100% failure coverage for all end-to-end routing paths with approximately two extra Forwarding Information Base (FIB) entries.

The critical requirement on reliability, fault-tolerance and security of network devices highlights the necessity of protocol robustness testing. Mutation testing of protocol messages is an important part of robustness testing, but related theory and practices are not well developed. This paper builds a NFSM model for mutation testing of protocol messages and proposes two types of normal-verification sequence to enhance verdict mechanism. For single-field mutation testing of protocol messages, we propose the concept of compound anomalous test case to further simplify test sequences. As a standard test specification language, TTCN-3 reveals strong excellence in conformance testing, so we apply TTCN-3 to mutation testing and extend it according to test requirements. Using our method we test OSPFv2 sufficiently with a test system based on extended TTCN-3. The results indicate that our method has good capability of error-finding.

Mobile IPv6 (MIPv6) protocol is a new protocol designed to support the node mobility of IPv6 protocol, which is a basic protocol of the next generation Internet. Protocol testing consists of conformance testing, interoperability testing and performance testing. Protocol emulation testing, which we adopt in this paper, is a way of protocol testing. This paper designs an emulation-based method for performance testing of mobile IPv6 protocol, gives performance evaluation metrics in view of the three kinds of MIPv6 nodes (HA, home agent; MN, mobile node; CN, correspondent node), tests and analyzes MIPL 1.1 on Linux 2.4.26. Our method is easy to implement on commonly used hardware, very convenient to deploy and more flexible compared to most commercial test instruments. As far as we know, this is the first work on the research of performance testing of Mobile IPv6 protocol.