Abstract Middleboxes have become a vital part of modern networks by providing services such as load balancing, optimization of network traffic, and content filtering. A sequence of middleboxes comprising a logical service is called a Service Function Chain (SFC) . In this context, the main issues are to maintain an acceptable level of network path survivability and a fair allocation of the resource between different demands in the event of faults or failures. In this paper, we focus on the problems of traffic engineering, failure recovery, fault prevention, and SFC with reliability and energy consumption constraints in Software Defined Networks (SDN). These types of deployments use Fog computing as an emerging paradigm to manage the distributed small-size traffic flows passing through the SDN-enabled switches (possibly Fog Nodes). The main aim of this integration is to support service delivery in real-time, failure recovery, and fault-awareness in an SFC context. Firstly, we present an architecture for Failure Recovery and Fault Prevention called FRFP; this is a multi-tier structure in which the real-time traffic flows pass through SDN-enabled switches to jointly decrease the network side-effects of flow rerouting and energy consumption of the Fog Nodes. We then mathematically formulate an optimization problem called the Optimal Fog-Supported Energy-Aware SFC rerouting algorithm (OFES) and propose a near-optimal heuristic called Heuristic OFES (HFES) to solve the corresponding problem in polynomial time. In this way, the energy consumption and the reliability of the selected paths are optimized, while the Quality of Service (QoS) constraints are met and the network congestion is minimized. In a reliability context, the focus of this work is on fault prevention; however, since we use a reallocation technique, the proposed scheme can be used as a failure recovery scheme. We compare the performance of HFES and OFES in terms of energy consumption, average path length, fault probability, network side-effects, link utilization, and Fog Node utilization. Additionally, we analyze the computational complexity of HFES. We use a real-world network topology to evaluate our algorithm. The simulation results show that the heuristic algorithm is applicable to large-scale networks.
In @cite_36 , they present a controller-based fault recovery solution that covers path-failure detection and preconfigured backup paths. However, we point out that, unlike our approach: (i) the focus of @cite_36 is on presenting the network configuration in order to manage the traffic flows, which is not an effective solution, by design, in real scenarios; and (ii) the presented fault prevention method in @cite_36 does not support the SFC over the SDN-enabled switches. The authors in @cite_0 propose a solution to quickly detect link failures in order to increase the fault tolerance by combining the flow retrieval which is achieved through analyzing the protection switching times and using a fast protection method. Interestingly, this paper supports the fault minimization over the links and addresses the end-to-end fault tolerance method per flow, but not radically. Overall, the contribution does not afford, by design, jointly the QoSs in the node and link of SDN and does not support the SFC fault minimization, both of which are adopted in this paper.
@cite_36 @cite_0
2041849649 2027076000
When dealing with node or link failures in Software Defined Networking (SDN), the network capability to establish an alternative path depends on controller reachability and on the round trip times (RTTs) between controller and involved switches. Moreover, current SDN data plane abstractions for failure detection (e.g. OpenFlow "Fast-failover") do not allow programmers to tweak switches' detection mechanism, thus leaving SDN operators still relying on proprietary management interfaces (when available) to achieve guaranteed detection and recovery delays. We propose SPIDER, an OpenFlow-like pipeline design that provides i) a detection mechanism based on switches' periodic link probing and ii) fast reroute of traffic flows even in case of distant failures, regardless of controller availability. SPIDER can be implemented using stateful data plane abstractions such as OpenState or Open vSwitch, and it offers guaranteed short (i.e. ms) failure detection and recovery delays, with a configurable trade off between overhead and failover responsiveness. We present here the SPIDER pipeline design, behavioral model, and analysis on flow tables' memory impact. We also implemented and experimentally validated SPIDER using OpenState (an OpenFlow 1.3 extension for stateful packet processing), showing numerical results on its performance in terms of recovery latency and packet losses. Structural fault tolerance (SFT) is the ability of a multiprocessor to reconfigure around faulty processors or links in order to preserve its original processor interconnection structure; In this paper, we focus on the design of SFT multiprocessors that have low switch and link overheads, but can tolerate a very large number of processor faults on the average. Most previous work has concentrated on deterministic k-fault-tolerant (k-FT) designs in which exactly k spare processors and some spare switches and links are added to construct multiprocessors that can tolerate any k processor faults. However, after k faults are reconfigured around, much of the extra links and switches can remain unutilized. It is possible within the basic node-covering framework, which was introduced by Dutt and Hayes as an efficient k-FT design method, to design FT multiprocessors that have the same amount of switches and links as, say, a two-FT deterministic design, but have s spare processors, where s spl Gt 2, so that, on the average, k= spl Theta (s) (k spl les s) processor failures can be reconfigured around. Such designs utilize the spare link and switch capacity very efficiently, and are called probabilistic FT designs. An elegant and powerful method to construct covering graphs or CG's, which are key to obtaining the probabilistic FT designs, is to use linear error-correcting codes (ECCs). We show how to construct probabilistic designs with very high average fault tolerance but low wiring and switch overhead using ECCs like the 2D-parity, full-two, 3D-parity, and full-three codes. Service function chaining (SFC) allows the forwarding of traffic flows along a chain of virtual network functions (VNFs). Software defined networking (SDN) solutions can be used to support SFC to reduce both the management complexity and the operational costs. One of the most critical issues for the service and network providers is the reduction of energy consumption, which should be achieved without impacting the Quality of Service. In this paper, we propose a novel resource allocation architecture which enables energy-aware SFC for SDN-based networks, considering also constraints on delay, link utilization, server utilization. To this end, we formulate the problems of VNF placement, allocation of VNFs to flows, and flow routing as integer linear programming (ILP) optimization problems. Since the formulated problems cannot be solved (using ILP solvers) in acceptable timescales for realistic problem dimensions, we design a set of heuristic to find near-optimal solutions in timescales suitable for practical applications. We numerically evaluate the performance of the proposed algorithms over a real-world topology under various network traffic patterns. Our results confirm that the proposed heuristic algorithms provide near-optimal solutions (at most 14 optimality-gap) while their execution time makes them usable for real-life networks. This paper presents FatTire, a new language for writing fault-tolerant network programs. The central feature of this language is a new programming construct based on regular expressions that allows developers to specify the set of paths that packets may take through the network as well as the degree of fault tolerance required. This construct is implemented by a compiler that targets the in-network fast-failover mechanisms provided in recent versions of the Open- Flow standard, and facilitates simple reasoning about network programs even in the presence of failures. We describe the design of FatTire, present algorithms for compiling FatTire programs to OpenFlow switch configurations, describe our prototype FatTire implementation, and demonstrate its use on simple examples. OpenFlow, initially launched as a technology-enabling network and application experimentation in a campus network, has a disruptive potential in designing a flexible network, fostering innovation, reducing complexity and delivering the right economics. This paper focuses on fault tolerance of OpenFlow to deploy it in carrier-grade networks. The carrier-grade network has a strict requirement that the network should recover from the failure within a 50ms interval. We apply two well-known recovery mechanisms to OpenFlow networks: restoration and protection, and run extensive emulation experiments. In OpenFlow, the controlling software is moved to one or more hardware modules (controllers) which can control many switches. For fast failure recovery, the controller must notify all the affected switches about the recovery action within ms interval. This leads to a significant load on the controller. We show that OpenFlow may not be able to achieve failure recovery within a 50ms interval in this situation. We add the recovery action in the switches themselves so that the switches can do recovery without contacting the controller. We show that this approach can achieve recovery within 50ms in a large-scale network serving many flows. Mobile agents have attracted considerable interest in recent years. In the context of mobile agents, fault tolerance is crucial to enable the integration of mobile agent technology into today's business applications. To further develop mobile agent technology, reliability mechanisms such as fault tolerance and transaction support are required. For this purpose, we first identify two basic requirements for fault-tolerant mobile agent execution: (1) non-blocking (i.e., a single failure does not prevent progress of the mobile agent execution); and (2) exactly-once (i.e., multiple executions of the agent are prevented). To achieve fault tolerance for the agent system, especially for the agent transfer to a new host, we use distributed transaction processing. This paper proposes a novel approach to fault-tolerant mobile agent execution, which is based on modeling agent execution as a sequence of agreement problems. Each agreement problem is one instance of the well-understood consensus problem. Our solution does not require a perfect failure detection mechanism, while preventing blocking and ensuring that the agent is executed exactly once A reliable and scalable mechanism to provide protection against a link or node failure has additional requirements in the context of SDN and OpenFlow. Not only it has to minimize the load on the controller, but it must be able to react even when the controller is unreachable. In this paper we present a protection scheme based on precomputed backup paths and inspired by MPLS “crankback” routing, that guarantees instantaneous recovery times and aims at zero packet-loss after failure detection, regardless of controller reachability, even when OpenFlow's “fast-failover” feature cannot be used. The proposed mechanism is based on OpenState, an OpenFlow extension that allows a programmer to specify how forwarding rules should autonomously adapt in a stateful fashion, reducing the need to rely on remote controllers. We present the scheme as well as two different formulations for the computation of backup paths. Increase in the network usage for more and more performance critical applications has caused a demand for tools that can monitor network health with minimum management traffic. Adaptive probing has the potential to provide effective tools for end-to-end monitoring and fault diagnosis over a network. Adaptive probing based algorithms adapt the probe set to localize faults in the network by sending less probes in healthy areas and more probes in the suspected areas of failure. In this paper we present adaptive probing tools that meet the requirements to provide an effective and efficient solution for fault diagnosis for modern communication systems. We present a system architecture for adaptive probing based fault diagnosis tool and propose algorithms for probe selection to perform failure detection and fault localization. We compare the performance and efficiency of the proposed algorithms through simulation results. In [1], the author introduced a strategy to use network coding on p-Cycles in order to provide 1+N protection for straddling connections and links against single link failures in mesh optical networks. In this paper we extend the work in [1] and introduce a GMPLS-based implementation of this strategy for link protection, that is also used to protect on-cycle links. We refer to this scheme as hybrid 1+N protection, since some data units are transmitted without being combined with other data units. The strategy uses a combination of GMPLS standard label switched paths (LSP) for protecting on-cycle links, and modified LSPs, which we refer to as label switched cycles (LSC), for protecting straddling links. The strategy does not have to explicitly detect failures, but rather detects the absence of data units. Destinations receive backup copies of packets within no more than the p-Cycle propagation delay for on-cycle link failures, and no more than the sum of the propagation delays of the p-Cycle and the longest straddling link for straddling link failures. The implementation details of this strategy are presented, and the cost of implementation, in terms of link usage is evaluated and is shown to be modest. This scheme can therefore provide protection at higher layers, at a speed that is comparable to that achieved at the physical layer, but at a much reduced cost, while being flexible, and requiring less involvement from the management and control planes. A long-term trend in high performance computing is the increasing number of nodes in parallel computing platforms, which entails a higher failure probability. Hence, fault tolerance becomes a key property for parallel application running on parallel computing systems. The message passing interface (MPI) is currently the programming paradigm and communication library most commonly used on parallel computing platforms. MPI applications may be stopped at any time during their execution due to an unpredictable failure. In order to avoid complete restarts of an MPI application because of only one failure, a fault tolerant MPI implementation is essential. In this paper, we propose a fault tolerant approach in cluster computing system. Our approach is based on reassignment of tasks to the remaining system and message logging is used for message losses. This system consists of two main parts, failure diagnosis and failure recovery. Failure diagnosis is the detection of a failure and failure recovery is the action needed to take over the workload of a failed component. This fault tolerant approach is implemented as an extension of the message passing interface. A fault-scalable service can be configured to tolerate increasing numbers of faults without significant decreases in performance. The Query Update (Q U) protocol is a new tool that enables construction of fault-scalable Byzantine fault-tolerant services. The optimistic quorum-based nature of the Q U protocol allows it to provide better throughput and fault-scalability than replicated state machines using agreement-based protocols. A prototype service built using the Q U protocol outperforms the same service built using a popular replicated state machine implementation at all system sizes in experiments that permit an optimistic execution. Moreover, the performance of the Q U protocol decreases by only 36 as the number of Byzantine faults tolerated increases from one to five, whereas the performance of the replicated state machine decreases by 83 . Although Software-Defined Networking and its implementation OpenFlow facilitate managing networks and enable dynamic network configuration, recovering from network failures in a timely manner remains non-trivial. The process of (a) detecting the failure, (b) communicating it to the controller and (c) recomputing the new shortest paths may result in an unacceptably long recovery time. In this paper, we demonstrate that current solutions, employing both reactive restoration or proactive protection, indeed suffer long delays. We introduce a failover scheme with per-link Bidirectional Forwarding Detection sessions and preconfigured primary and secondary paths computed by an OpenFlow controller. Our implementation reduces the recovery time by an order of magnitude compared to related work, which is confirmed by experimental evaluation in a variety of topologies. Furthermore, the recovery time is shown to be constant irrespective of path length and network size. Networks are a shared resource connecting critical IT infrastructure, and the general practice is to always leave them on. Yet, meaningful energy savings can result from improving a network's ability to scale up and down, as traffic demands ebb and flow. We present ElasticTree, a network-wide power1 manager, which dynamically adjusts the set of active network elements -- links and switches--to satisfy changing data center traffic loads. We first compare multiple strategies for finding minimum-power network subsets across a range of traffic patterns. We implement and analyze ElasticTree on a prototype testbed built with production OpenFlow switches from three network vendors. Further, we examine the trade-offs between energy efficiency, performance and robustness, with real traces from a production e-commerce website. Our results demonstrate that for data center workloads, ElasticTree can save up to 50 of network energy, while maintaining the ability to handle traffic surges. Our fast heuristic for computing network subsets enables ElasticTree to scale to data centers containing thousands of nodes. We finish by showing how a network admin might configure ElasticTree to satisfy their needs for performance and fault tolerance, while minimizing their network power bill. Multi agent systems (MAS) are expected to be involved in futuristic technologies. Agents require some execution environment in which they can publish their service interfaces and can provide services to other agent. Such execution environment is called agent platform (AP). From a technical point of view any abnormal behavior of platform can distress agents residing on that platform. That's why it is necessary to provide a suitable architecture for the AP which should not only provide fault tolerance but also scalability features. There also exist some management components within the platform, which provide services to application agents. All the agents within MAS are managed by agent management system (AMS) which is the mandatory supervisory authority of any AP. To be more scalable, a single agent platform can be distributed over several machines which not only provides load balancing but also fault tolerance depending upon the distributed architecture of the AP. In existing systems, AMS is centralized i.e. it exists on one machine. With centralized AMS, this infrastructure lacks fault tolerance, which is a key feature of high assurance. Absence of fault tolerance is the main reason for the small number of deployments of MAS. Failure of AMS leads towards abnormal behavior in the distributed platform. This paper proposes virtual agent cluster (VAC) paradigm which strongly supports decentralized AMS to achieve fault tolerance in distributed AP. VAC provides fault tolerance by using separate communication layers among different machines. Experiments show that it improves performance, brings autonomy and supports fault recovery along with load balancing in distributed AP. As the size of large-scale computer systems increases, their mean-time-between-failures are becoming significantly shorter than the execution time of many current scientific applications. To complete the execution of scientific applications, they must tolerate hardware failures. Conventional rollback-recovery protocols redo the computation of the crashed process since the last checkpoint on a single processor. As a result, the recovery time of all protocols is no less than the time between the last checkpoint and the crash. In this paper, we propose a new application-level fault-tolerant approach for parallel applications called the fault-tolerant parallel algorithm (FTPA), which provides fast self-recovery. When fail-stop failures occur and are detected, all surviving processes recompute the workload of failed processes in parallel. FTPA, however, requires the user to be involved in fault tolerance. In order to ease the FTPA implementation, we developed get it fault-tolerant (GiFT), a source-to-source precompiler tool to automate the FTPA implementation. We evaluate the performance of FTPA with parallel matrix multiplication and five kernels of NAS Parallel Benchmarks on a cluster system with 1,024 CPUs. The experimental results show that the performance of FTPA is better than the performance of the traditional checkpointing approach. Software-defined networking (SDN) is an emerging paradigm that has become increasingly popular in recent years. The core idea is to separate the control and data planes, allowing the construction of network applications using high-level abstractions that are translated to network devices through a southbound interface. SDN architecture is composed of three layers: 1) infrastructure layer, responsible exclusively for data forwarding; 2) control layer, which maintains the network view and provides core network abstractions; and 3) application layer, which uses abstractions provided by the control layer to implement network applications. SDN provides features, such as flexibility and programmability, that are key enablers to meet current network requirements (e.g., multi-tenant cloud networks and elastic optical networks). However, along with its benefits, SDN also brings new issues. In this survey we focus on issues related to fault management. Different fault management threat vectors are introduced by each layer, as well as by the interface between layers. Nevertheless, besides addressing fault management issues of its architecture, SDN also must handle the same problems faced by legacy networks. However, programmability and centralized management might be used to provide flexibility to deal with those issues. This paper presents an overview of fault management in SDN. The major contributions of this paper are as follows: 1) identification of the main fault management issues in SDN and classification according to the affected layers; 2) survey of efforts that address those issues and classification according to the affected planes, issues concerned, general approaches, and features; and 3) discussion about trade-offs of different approaches and their suitability for different scenarios. Enterprise storage clusters increasingly adopt erasure coding to protect stored data against transient and permanent failures. Existing erasure code designs not only introduce extra parity information in a storage-inefficient manner, but also consume substantial cross-rack recovery bandwidth. To relieve both storage and recovery burdens of erasure coding, we adapt our previously proposed STAIR codes into recovery-oriented STAIR (R-STAIR) codes, which achieve storage efficiency, recovery efficiency, and configuration generality against a mix of node and rack failures. We evaluate R-STAIR codes through analysis and Hadoop experiments. We show that by supporting mixed fault tolerance, R-STAIR codes can significantly reduce both storage and recovery burdens in storage clusters. The increasing proportion of data traffic being carried in public networks is necessitating tractable and scalable algorithms in the design of ATM networks. In particular, the design of routing tables for ATM networks operated under the interim inter-switch signalling protocol (IISP) requires a significant amount of manual work in order to design and implement the underlying static routing tables that enable end-to-end connectivity as the network grows. This paper presents a scalable algorithm that generates IISP routing table entries such that no loops are created and so that connectivity is maintained between all origin destination nodes under single-link failures. The algorithm generates shortest (i.e., lowest-cost) primary and alternate paths for any single-link failure scenario, while also demonstrating that at least one such solution can be found for any network graph devoid of bridges. Note that re-routing for single-link failures is considered adequate when sufficient protection is provided at the lower network layers. The algorithm has been fully implemented in a practical software tool, with execution time being a polynomial function of the network complexity. Fault tolerant MPI (FTMPI) enables fault tolerance to the MPICH, an open source GPL licensed implementation of MPI standard by Argonne National Laboratory's Mathematics and Computer Science Division. FTMPI is a transparent fault-tolerant environment, based on synchronous checkpointing and restarting mechanism. FTMPI relies on non-multithreaded single process checkpointing library to synchronously checkpoint an application process. Global replicated system controller and cluster node specific node controller monitors and controls check pointing and recovery activities of all MPI applications within the cluster. This work details the architecture to provide fault tolerance mechanism for MPI based applications running on clusters and the performance of NAS parallel benchmarks and parallelized medium range weather forecasting models, P-T80 and P-TI26. The architecture addresses the following issues also: Replicating system controller to avoid single point of failure. Ensuring consistency of checkpoint files based on distributed two phase commit protocol, and robust fault detection hierarchy. We develop an availability solution, called SafetyNet, that uses a unified, lightweight checkpoint recovery mechanism to support multiple long-latency fault detection schemes. At an abstract level, SafetyNet logically maintains multiple, globally consistent checkpoints of the state of a shared memory multiprocessor (i.e., processors, memory, and coherence permissions), and it recovers to a pre-fault checkpoint of the system and re-executes if a fault is detected. SafetyNet efficiently coordinates checkpoints across the system in logical time and uses "logically atomic" coherence transactions to free checkpoints of transient coherence state. SafetyNet minimizes performance overhead by pipelining checkpoint validation with subsequent parallel execution.We illustrate SafetyNet avoiding system crashes due to either dropped coherence messages or the loss of an interconnection network switch (and its buffered messages). Using full-system simulation of a 16-way multiprocessor running commercial workloads, we find that SafetyNet (a) adds statistically insignificant runtime overhead in the common-case of fault-free execution, and (b) avoids a crash when tolerated faults occur.