In order to provide security connections to the enterprise campus sites, internet service providers are offering comprehensive intrusion detection services at the network layer. However, existing network intrusion detection systems (NIDS) are either ineffective or inefficient for high-speed network protection, especially for encrypted traffic analysis. In this paper, we design and implement SiteGuard, an inline network intrusion detection system with programmable switches specifically developed to protect enterprise campus sites connecting to ISP. SiteGuard proposes a dual-plane feature extraction model to extract extensive traffic features at near line-speed. SiteGuard also proposes a lightweight one-class classification model that trains the best parameters exclusively on benign traffic to identify malicious traffic. In addition, SiteGuard introduces an online update mechanism that aims to dynamically adjust the detection model in response to environmental changes. SiteGuard has been in production for more than three years. Our production and testbed evaluations demonstrate SiteGuard can detect malicious traffic with approximately 90% accuracy in minutes.

Abstract In recent years, DNS hijacking represents a significant security threat to the infrastructure of the Domain Name System (DNS). A prevalent form of DNS hijacking involves exploiting open resolvers to manipulate DNS records. Such attacks undermine the availability and confidentiality of network services, posing serious risks to legitimate users. Current DNS hijacking detection methods tend to focus on specific domains, leveraging the unique characteristics of domain-specific hijacking to identify attacks. Consequently, these methods are often limited in applicability and may lack accuracy when dealing with diverse hijacking scenarios. Additionally, many existing approaches face challenges related to efficiency, making them less effective for long-term monitoring of hijacking activities. To address these challenges, this paper introduces an efficient detection method F2D tailored for general DNS hijacking. First, F2D uses an accurate and efficient filtration funnel strategy for targeted resolver hijacking detection. Second, two optimized detection algorithms are proposed for comprehensive filtration. Third, the method includes an efficient mechanism for identifying CDN domains, enabling the filtration of a large number of content replication servers and enhancing overall detection efficiency. During the validation phase, we monitor around 36k domains and around 600 resolvers over a one-month period. The effectiveness of our method is validated using manually labeled sample data. Experimental results demonstrate that our method can improve the F1 performance by 10% with the same false alert level, and time efficiency by 39% compared to the state-of-the-arts. Furthermore, we conduct an in-depth analysis of the captured hijacking incidents and deduce the motivation of the hijacking.

The Domain Name System (DNS) is a critical internet infrastructure that translates human-readable domain names into machine-routable IP addresses. However, DNS is inherently vulnerable to manipulation, with hijacking attacks growing in both frequency and sophistication. Existing detection methods primarily rely on traffic analysis at specific network points. However, they suffer from limited coverage and low accuracy in complex environments, such as when CDN is employed. While recent approaches employ graph-based techniques, they still suffer from detection inaccuracy issues due to their failure to account for the complex interdependencies among multiple types of nodes. To address these limitations, we propose a novel heterogeneous graph-based detection framework. Based on the collected DNS records from distributed scanners, our method extracts activity and security features and constructs a heterogeneous graph to capture resolution patterns and cross-entity relationships. We further design a time-decay graph neural network TNHAN that enhances traditional Heterogeneous Graph Attention Networks (HAN) by dynamically weighting recent records. This network improves adaptability to legitimate DNS changes. For evaluation, we conduct experiments on real-world resolvers and domain datasets. Experiment results demonstrate the effectiveness of our method. Our method can achieve an F1-score of 0.96, outperforming the best baseline by 0.057 on average, and up to 0.113 under low label proportion. Moreover, we conduct several case studies on detected incidents, including cases related to geopolitical conflicts, censorship-related hijacking, and manipulation by malicious resolvers. These cases demonstrate the method’s effectiveness in identifying diverse hijacking behaviors in practice.

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.

IPv6 scanning is a critical technique for network security assessment and Internet measurement. However, the prevalence of aliased prefixes significantly distorts scan results and severely interferes with target generation algorithms (TGAs) that rely on dynamic density feedback. To address the limitations of existing aliased prefix detection methods, such as insufficient accuracy and excessive overhead, this paper proposes PMAPD, a Passive-Enhanced Multi-Level Aliased Prefix Detection approach. PMAPD integrates passive analysis with active probing. The passive analysis component reuses existing scan data—primarily host responsiveness obtained at no extra cost from the main address scan, and opportunistically uses port and service information if available, to enhance detection accuracy and efficiency. The active probing component builds upon the strengths of prior active methods while incorporating optimizations to achieve a better balance between detection precision and cost. Experimental results demonstrate PMAPD’s superiority in improving the discovery of de-aliased active addresses, reducing aliased addresses in scanning results, and significantly lowering detection overhead. Across three different TGAs tested (6Tree, DET, 6Sense), PMAPD significantly outperforms the widely used traditional method MAPD: it improves the de-aliased hits by 12% to 57%, substantially reduces the aliased ratio in scan results by over 9% to 94%, and dramatically lowers detection overhead, costing only 3% to 17% of MAPD’s overhead. PMAPD offers a novel and effective aliased prefix detection solution for efficient and accurate IPv6 network scanning.

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.

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.

Target generation is a crucial step for efficient Internet-wide IPv6 scanning, yet existing techniques are hindered by limited pattern discovery and biased target distribution. We introduce RGen, a novel target generation algorithm employing real-time pattern mining and a stochastic generation strategy. RGen minimizes pattern loss, dynamically incorporates new addresses, and promotes balanced target distribution, overcoming prior limitations. Experiments show RGen achieves the highest overall hit rate (58%), surpassing the previous best (AddrMiner-S) by 60%, while simultaneously leading in network discovery, finding the most new BGP prefixes and new / 64 prefixes.

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.

As microservices grow in scale and complexity, their operation and debugging become increasingly challenging. Even a single user request can involve interactions across hundreds of components. In such intricate systems, distributed tracing, which tracks the end-to-end execution flow of requests, has become a critical monitoring tool. Among these, non-intrusive tracing frameworks that do not require code modification are particularly valued for their convenience. However, existing non-intrusive solutions either have limited applicability or lack sufficient accuracy under high concurrency. To address these challenges, we propose DeepTrace, a transaction-based, non-intrusive distributed tracing framework designed for microservices. DeepTrace leverages API endpoints and transaction fields embedded within request content to categorize requests into distinct transactions, thereby reducing the likelihood of incorrectly merging traces from different transactions. Compared to state-of-the-art frameworks, DeepTrace maintains an accuracy rate of over 95% even under high concurrency. It has also been adopted by dozens of companies in their production systems for tasks such as failure diagnosis and resource optimization.

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.

Abstract In recent years, DoE methods have been regarded as a novel trend within the realm of the DNS ecosystem. Measuring these DoE services in the wild can promote improvements in DoE methods and facilitate their widespread adoption. A primary requirement for measuring DoE methods is the discovery of these services. The discovery is relatively straightforward for DoT and DoQ, but complex for DoH since it shares port 443 with web services as suggested in RFC 8484. Although previous works primarily analyze the surface of the DoH service, they (1) result in long detection time and large traffic volume by adopting an enumeration strategy to discover the DoH service; (2) lack an in-depth analysis of the status of upper-layer DNS services. In this paper, we propose the E-DoH method for elegant, efficient, and in-depth DoH service measurement. First, we propose a measurement mechanism to enable a single DoH connection to accomplish multiple tasks including service discovery, correctness validation, and dependency construction with minimal backend configuration. Second, we propose a dynamic protocol negotiation strategy to enhance probing efficiency while significantly reducing the required traffic volume. Based on the above optimization methods, we conducted an exploration of the IPv4 space and performed an in-depth analysis of DoH based on the collected information. Through experiments, our approach demonstrates a remarkable 80% improvement in time efficiency and only requires 4–20% traffic volume to complete the detection task. In wild detection, our approach discovered 46k DoH services, which nearly doubles the number discovered by the state-of-the-art. This indicates the growing trend of DoH services. Based on the collected information, we present several intriguing conclusions about the current DoH service ecosystem.

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.

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.

Software Defined Network (SDN) has been widely used in modern network architecture. The SD-WAN is considered as a technology that has a potential to revolutionize the WAN service usage by utilizing the SDN philosophy. Attacking SDN router and controller can affect the network and block the entire services. In this paper, we propose a machine learning based anomalous traffic detection framework named OADSD over SD-WAN that can achieve task independent and has the ability of adapting to the environment. The OADSD adopts Distributed Dynamic Feature Extraction (DDFE) to extract representative features directly from the raw traffic, and proposes the On-demand Evolving Isolation Forest (OEIF) to make the system adapt to an environment. We provide a theoretical analysis of the performance of the OADSD. We also conduct comprehensive experiments to evaluate the performance of the OADSD with real world public datasets as well as a small real testbed. Our experiments under real world public datasets show that, the OADSD can accurately detect various kinds of attacks with a high performance. Compared with the state-of-the-art systems, the OADSD can achieve up to 60% accuracy improvement.

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.

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.

The decrease of AS-level route length, called Internet flattening, has a significance impact on the the design of next generation global routing system. However, there is little quantitative assessment of its factors. We report our findings through monitoring and analysis of inter-domain routing. Using BGP routing table and update messages from RouteViews and RIPE RIS, we explore Internet flattening from a view of global inter-domain routing system. Our study shows that Internet flattening is from two dominating sources: (1) ASes close to Tier 1 contribute 36% of the total decrease in route length; and (2) Routes bypassing Tier 1 is responsible for 53% of the total decrease in route length. Our measurement results also indicate that multi-homing is not an important reason of Internet flattening. Besides, leading Content Providers contribute to Internet flattening ten times than that by Internet Service Providers. Base on our result, we propose mechanisms for the performance improvement for Content Providers.

The de facto inter-domain routing protocol, Border Gateway Protocol (BGP), plays a critical role in the Internet routing reliability. Invalid routes generated by mis-configurations or malicious attacks will devastate the Internet routing system. In the near future, deploying a secure BGP in the Internet to completely prevent hijacking is impossible. As a result, lots of hijacking detection systems have emerged. However, they have more or less weaknesses such as long detection delay, high false alarm rate or deploy hardness. This paper proposes Argus, an agile system to fast and accurate detect prefix hijacking. Argus already keeps on running in the Internet for two months and identified several possible hijackings. Initial results show that it usually discovers a hijacking in less than ten seconds, and can significantly decrease the false alarm rate.

Abstract Network protocols often have time constraints. Robustness testing of network protocol with time constraints aims to detect vulnerabilities of its implementation. However, related theory is not well developed. This paper proposes a novel Timed NPEFSM model containing sufficient inputs with various time values and their processing rules to formalize complex protocol with time constraints. In order to test delay transitions, Grid Timed NPEFSM is proposed and it can be generated by state characterization of Timed NPEFSM based on time sampling. Thus, these two models jointly guide robustness testing of protocol with time constraints. For test generation, we propose timed anomalous test case in which only state under test is characterized by time sampling and this method can simplify test sequences largely without compromising test coverage. We also propose several strategies to construct test sequences for timed transitions. To inject test data efficiently and effectively, three types of timed compound anomalous test cases are proposed and the algorithm of generating timed compound anomalous test cases considering both single‐field and multi‐field mutations is then presented. Standard test specification language TTCN‐3 is extended to describe timed compound anomalous test case. We illustrate our test method using an intra‐domain routing protocol OSPFv2. Copyright © 2010 John Wiley & Sons, Ltd.

The separation between edge and core addresses has been proposed to address the scalability problem of the Internet routing system. One main challenge is to design an efficient mapping mechanism for the two address spaces. The layer structure is attractive because of its scalability and simple index mechanism, while existing layered mapping system lacks a clear structure study and faces serious deployment and mapping quality issues. This paper proposes a neutral layered mapping system called NLMS run orthogonal to Internet Service Providers (ISPs) that can be widely acceptable by various networks and be constructed stepwise. A constraint analysis on the layer structure points out that a three-layer NLMS suffices to manage mapping information for IPv6 edge addresses. To guarantee the routing quality under NLMS a two-stage cache mechanism called TSC is further proposed. Experiments show that TSC can effectively reduce mapping delays and enhance other mapping qualities. Compared with existing mapping designs, NLMS succeeds in achieving all the primary goals of mapping design.

In order to better understand BGP dynamics, a time-based approach has been developed to cluster BGP updates into routing events. Its basic idea is to cluster consecutive BGP updates of the same prefix into one routing events if the updates are separated by a time interval less than a threshold. Most of static threshold methods might incorrectly group multiple events into one if the threshold is too high, or divide a single event into multiple ones if the threshold is too low. On the other hand, previous dynamic threshold approach did not present a persuasive way to calculate one of its key parameters. In this paper we present a three-step dynamic threshold method to cluster BGP updates into routing events. We evaluate our approach using updates of BGP beacon prefixes downloaded from route views. The experiment result shows that our dynamic threshold approach could cluster updates into routing events more precisely than previous methods, and thus improve the accuracy of the BGP measurement studies.

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.

Protocol interoperability testing is an important technique to ensure the quality of implementations of network communication protocols. In this paper, we present an efficient method to generate interoperability testing for time dependent protocols. We use the formal model, communicating TIOAs (timed input automata) (CTIOAs), to specify the system under test, in which time constraints are specified by linear expressions involving local clock values. In the method, firstly a global state reachability tree of CTIOAs should be generated, in which test sequences can be selected. Then we analyze the executability of the generated test sequences. By converting linear constraints of local clocks to a global clock, the problem reduces to a linear programming problem. We also select a set of appropriate initial clock values to make test sequences executable. An example of a neighbor discovery protocol is used to illustrate our method.