To provide fast traffic recovery upon failures, most modern networks support static Fast Rerouting (FRR) mechanisms for mission critical services. However, configuring FRR mechanisms to toleratemultiplefailures poses challenging algorithmic problems. While state-of-the-art solutions leveraging arc-disjoint arborescence-based network decompositions ensure that failover routes always reach their destinations eventually, even under multiple concurrent failures, these routes may be long and introduce unnecessary loads; moreover, they are tailored to worst-case failure scenarios. This article presents an algorithmic framework for improving a given FRR network decomposition,using postprocessing. In particular, our framework is based on iterative arc swapping strategies and supports a number of use cases, from strengthening the resilience (e.g., in the presence of shared risk link groups) to improving the quality of the resulting routes (e.g., reducing route lengths and induced loads). Our simulations show that postprocessing is indeed beneficial in various scenarios, and can therefore enhance today’s approaches.

To provide a high availability and to be able to quickly react to link failures, most communication networks feature fast rerouting (FRR) mechanisms in the data plane. However, configuring these mechanisms to provide a high resilience against multiple failures is algorithmically challenging, as rerouting rules can only depend on local failure information and need to be pre-defined. This paper is motivated by the observation that the common approach to design fast rerouting algorithms, based on spanning trees and covering arborescences, comes at a cost of reduced resilience as it does not fully exploit the available links in heterogeneous topologies. We present several novel fast rerouting algorithms which are not limited by spanning trees, but rather extend and combine ("graft") multiple spanning arborescences to improve resilience. We compare our algorithms analytically and empirically, and show that they can significantly improve not only the resilience, but also accelerate the preprocessing to generate the local fast failover rules.

Highly dependable communication networks usually rely on some kind of Fast Re-Route (FRR) mechanism which allows to quickly re-route traffic upon failures, entirely in the data plane. This paper studies the design of FRR mechanisms for emerging reconfigurable switches. Our main contribution is an FRR primitive for programmable data planes, PURR, which provides low failover latency and high switch throughput, by avoiding packet recirculation. PURR tolerates multiple concurrent failures and comes with minimal memory requirements, ensuring compact forwarding tables, by unveiling an intriguing connection to classic “string theory” (i.e., stringology), and in particular, the shortest common supersequence problem. PURR is well-suited for high-speed match-action forwarding architectures (e.g., PISA) and supports the implementation of a broad variety of FRR mechanisms. Our simulations and prototype implementation (on an FPGA and a Tofino switch) show that PURR improves TCAM memory occupancy by a factor of 1.5 ×- 10.8 × compared to a naïve encoding when implementing state-of-the-art FRR mechanisms. PURR also improves the latency and throughput of datacenter traffic up to a factor of 2.8 ×- 5.5 × and 1.2 ×- 2 ×, respectively, compared to approaches based on recirculating packets.

Highly dependable communication networks usually rely on some kind of Fast Re-Route (FRR) mechanism which allows to quickly re-route traffic upon failures, entirely in the data plane. This paper studies the design of FRR mechanisms for emerging reconfigurable switches.

To provide high availability despite link failures, many modern communication networks feature fast failover mechanisms in the data plane, which operates orders of magnitude faster than the control plane. While the configuration of highly resilient data planes is known to be a difficult combinatorial problem, over the last years, much progress has been made in the design of algorithms which provably guarantee connectivity even under many concurrent link failures. However, while these algorithms provide connectivity, the resulting routes after failures can be very long, which in turn can harm performance. In this paper, we propose, analyze, and evaluate methods for fast failover algorithms which account for the quality of the routes after failures, in addition to connectivity. In particular, we revisit the existing approach to cover the to-be-protected network with arc-disjoint spanning arborescences to define alternative routes to the destination, aiming to keep the stretch imposed by these trees low (hence the name of our method: Bonsai). We show that the underlying problem is NP-hard on general topologies and present lower bound results that are tight for various topologies, for any class of fast failover algorithms. We also present heuristics for general networks and demonstrate their performance benefits in extensive simulations. Finally, we show that failover algorithms using low-stretch arborescences, as a side effect, can provide connectivity under more general failure models than usually considered in the literature.

To provide fast traffic recovery upon failures, most modern networks support static Fast Rerouting (FRR) mechanisms for mission critical services. However, configuring FRR mechanisms to tolerate multiple failures poses challenging algorithmic problems. While state-of-the-art solutions leveraging arc-disjoint arborescence-based network decompositions ensure that failover routes always reach their destinations eventually, even under multiple concurrent failures, these routes may be long and introduce unnecessary loads; moreover, they are tailored to worst-case failure scenarios. This paper presents an algorithmic framework for improving a given FRR network decomposition, using postprocessing. In particular, our framework is based on iterative arc swapping strategies and supports a number of use cases, from strengthening the resilience (e.g., in the presence of shared risk link groups) to improving the quality of the resulting routes (e.g., reducing route lengths and induced loads). Our simulations show that postprocessing is indeed beneficial in various scenarios, and can therefore enhance today's approaches.

Intrusion detection in modern enterprise networks faces challenges due to the increasing large volume of data and insufficient training data for anomaly detections. In this work, we propose a novel network topology for improved intrusion detection through multi-phase data monitoring system. Rather than the all-or-nothing approach to terminate all sessions identified as suspicious, the topology route traffic to different servers replicas with different monitoring intensity level based on their likelihood of attacks. This topology leverages recent advances in software-defined networking (SDN) to dynamically route such sessions into risk-appropriate computing environments. These environments offer enhanced training opportunities intrusion detection systems (IDSes) by exposing data streams that would not have been observable had the session merely been terminated at the first sign of maliciousness. They also afford defenders finer- grained risk management by supporting a continuum of endpoint environments, ranging from fully trusted, to semi-trusted, to fully untrusted, for example.

Software-Defined Networking (SDN) is a new paradigm that promises to enhance network flexibility and innovation. However, operators need to thoroughly assess its advantages and threats before they can implement it. Robustness and fault tolerance are among the main criteria to be considered in such assessment. The currently available SDN controllers offer different fault tolerance mechanisms, but there are still many open issues, especially regarding the trade-off between consistency and performance in a fault- tolerant SDN platform. In this paper, we describe existing fault-tolerant SDN controller solutions, and propose a mechanism to design a consistent and fault-tolerant Master-Slave SDN controller that is able to balance consistency and performance. The main objective of this paper is to bring the performance of an SDN Master-Slave controller as close as possible to the one offered by a single controller. This is obtained by introducing a simple replication scheme, combined with a consistency check and a correction mechanism, that influence the performance only during the few intervals when it is needed, instead of being active during the entire operation time.