Resource sharing with its implied mutual interference has been considered a major concern for running applications of multiple tenants in shared cloud datacenters. Besides its security benefits, the isolation of traffic might ensure a quality of service (QoS) performance guarantee avoiding interference among tenants. Traffic isolation can be achieved by dedicating the usage of link resources in the network to a single tenant preventing its sharing among others. Accordingly, tenants should be connected through an edge-disjoint tree to enable isolated communication among its hosts. In this paper, we study the problem of establishing edge-disjoint trees in common datacenter topologies. We show that the availability of such trees is highly affected by the mapping of the tenants to hosts of the topology. Specifically, with the flexibility to map tenants in the datacenter topology, we describe a mapping algorithm and an optimal tree establishment for the optimization problem. Given the mapping of the tenants, we prove the problem turns out to be NP-Hard and provide comprehensive heuristics for the problem. Finally, we conduct experiments using real workloads to examine tree availability under various scenarios.

Enabling functionality in modern network is achieved through the use of middleboxes. Middleboxes suffer from temporal unavailability due to various reasons, such as hardware faults. We design a backup scheme that takes advantage of Network Function Virtualization (NFV), an emerging paradigm of implementing network functions in software, deployed on commodity servers. We utilize the agility of software-based systems, and the gap between the resource utilization of active and standby components, in order to design an optimal limited-resource backup scheme. We focus on the case where a small number of middleboxes fail simultaneously, and study the backup resources required for guaranteeing full recovery from any set of failures, of up to some limited size. Via a novel graph-based presentation, we develop a provably optimal construction of such backup schemes. Since full recovery is guaranteed, our construction does not rely on failure statistics, which are typically hard to obtain. Simulation results show that our proposed approach is applicable even for the case of larger numbers of failures.

Enabling functionality in a modern network is achieved through the use of middleboxes. Middleboxes suffer from temporal unavailability due to various reasons, such as hardware faults. We design a backup scheme that takes advantage of network function virtualization, an emerging paradigm of implementing network functions in software, deployed on commodity servers. We utilize the agility of software-based systems, and the gap between the resource utilization of active and standby components, in order to design an optimal limited-resource backup scheme. We focus on the case where a small number of middleboxes fail simultaneously, and study the backup resources required for guaranteeing full recovery from any set of failures, of up to some limited size. Via a novel graph-based presentation, we develop a provably optimal construction of such backup schemes. Since full recovery is guaranteed, our construction does not rely on failure statistics, which are typically hard to obtain. Simulation results show that our proposed approach is applicable even for the case of larger numbers of failures.

Network Function Virtualization (NFV) is a novel paradigm that enables flexible and scalable implementation of network services on cloud infrastructure. An important enabler for the NFV paradigm is software switching, which should satisfy rigid network requirements such as high throughput and low latency. Despite recent research activities in the field of NFV, not much attention was given to understand the costs of software switching in NFV deployments. Existing approaches for traffic steering and orchestration of virtual network functions either neglect the cost of software switching or assume that it can be provided as an input, and therefore real NFV deployments of network services are often suboptimal. In this work, we conduct an extensive and in-depth evaluation that examines the impact of service chaining deployments on Open vSwitch - the de facto standard software switch for cloud environments. We provide insights on network performance metrics such as throughput, CPU utilization and packet processing, while considering different placement strategies of a service chain. We then use these insights to provide an abstract generalized cost function that accurately captures the CPU switching cost of deployed service chains. This cost is an essential building block for any practical optimized placement management and orchestration strategy for NFV service chaining.

In enterprise networks, network functions, such as address translation, firewall, and deep packet inspection, are often implemented in middleboxes. Those can suffer from temporary unavailability due to misconfiguration or software and hardware malfunction. Traditionally, middlebox survivability is achieved by an expensive active-standby deployment where each middlebox has a backup instance, which is activated in case of a failure. Network function virtualization (NFV) is a novel networking paradigm allowing flexible, scalable and inexpensive implementation of network services. In this paper, we suggest a novel approach for planning and deploying backup schemes for network functions that guarantee high levels of survivability with significant reduction in resource consumption. In the suggested backup scheme, we take advantage of the flexibility and resource-sharing abilities of the NFV paradigm in order to maintain only a few backup servers, where each can serve one of multiple functions when corresponding middleboxes are unavailable. We describe different goals that network designers can consider when determining which functions to implement in each of the backup servers. We rely on a graph theoretical model to find properties of efficient assignments and to develop algorithms that can find them. Extensive experiments show, for example, that under realistic function failure probabilities, and reasonable capacity limitations, one can obtain 99.9% survival probability with half the number of servers, compared with standard techniques.

Coping with network failures has been recognized as an issue of major importance in terms of social security, stability, and prosperity. It has become clear that current networking standards fall short of coping with the complex challenge of surviving failures. The need to address this challenge has become a focal point of networking research. In particular, the concept of tunable survivability offers major performance improvements over traditional approaches. Indeed, while the traditional approach aims at providing full (100%) protection against network failures through disjoint paths, it was realized that this requirement is too restrictive in practice. Tunable survivability provides a quantitative measure for specifying the desired level (0%-100%) of survivability and offers flexibility in the choice of the routing paths. Previous work focused on the simpler class of “bottleneck” criteria, such as bandwidth. In this paper, we focus on the important and much more complex class of additive criteria, such as delay and cost. First, we establish some (in part, counter-intuitive) properties of the optimal solution. Then, we establish efficient algorithmic schemes for optimizing the level of survivability under additive end-to-end quality of service (QoS) bounds. Subsequently, through extensive simulations, we show that, at the price of negligible reduction in the level of survivability, a major improvement (up to a factor of 2) is obtained in terms of end-to-end QoS performance. Finally, we exploit the above findings in the context of a network design problem, in which, for a given investment budget, we aim to improve the survivability of the network links.

In enterprise networks, network functions such as address translation, firewall and deep packet inspection are often implemented in middleboxes. Those can suffer from temporary unavailability due to misconfiguration or software and hardware malfunction. Traditionally, middlebox survivability is achieved by an expensive active-standby deployment where each middlebox has a backup instance, which is activated in case of a failure. Network Function Virtualization (NFV) is a novel networking paradigm allowing flexible, scalable and inexpensive implementation of network services. In this work we suggest a novel approach for planning and deploying backup schemes for network functions that guarantee high levels of survivability with significant reduction in resource consumption. In the suggested backup scheme we take advantage of the flexibility and resource-sharing abilities of the NFV paradigm in order to maintain only a few backup servers, where each can serve one of multiple functions when corresponding middleboxes are unavailable. We describe different goals that network designers can take into account when determining which functions to implement in each of the backup servers. We rely on a graph theoretical model to find properties of efficient assignments and to develop algorithms that can find them. Extensive experiments show, for example, that under realistic function failure probabilities, and reasonable capacity limitations, one can obtain 99.9% survival probability with half the number of servers, compared to standard techniques.

Network survivability has been recognized as an issue of major importance in terms of security, stability and prosperity. A crucial research problem in this context is the identification of suitable pairs of disjoint paths. Here, “disjointness” can be considered in terms of either nodes or links. Accordingly, several studies have focused on finding pairs of either link or node disjoint paths with a minimum sum of link weights. In this study, we investigate the gap between the optimal node-disjoint and link-disjoint solutions. Specifically, we formalize several optimization problems that aim at finding minimum-weight link-disjoint paths while restricting the number of its common nodes. We establish that some of these variants are computationally intractable, while for other variants we establish polynomial-time algorithmic solutions. Finally, through extensive simulations, we show that, by allowing link-disjoint paths share a few common nodes, a major improvement is obtained in terms of the quality (i.e., total weight) of the solution.

Coping with network failures has become a major networking challenge. The concept of tunable survivability provides a quantitative measure for specifying any desired level (0%-100%) of survivability, thus offering flexibility in the routing choice. Previous works focused on implementing this concept on unicast transmissions. However, vital network information is often broadcast via spanning trees. Accordingly, in this study, we investigate the application of tunable survivability for efficient maintenance of spanning trees under the presence of failures. We establish efficient algorithmic schemes for optimizing the level of survivability under various QoS requirements. In addition, we derive theoretical bounds on the number of required trees for maximum survivability. Finally, through extensive simulations, we demonstrate the effectiveness of the tunable survivability concept in the construction of spanning trees. Most notably, we show that, typically, negligible reduction in the level of survivability results in major improvement in the QoS performance of the resulting spanning trees.

Stackable Routers, i.e. a class of independent routing units operating together as a single router, constitute an affordable scalable approach for coping with the growing networking requirements of organizations. In this study, we investigate several design problems of stackable routers and develop novel schemes for improving their performance. First, we formalize a mathematical model for optimizing the network topology in terms of throughput and delay, while obeying constraints in the number of ports of each internal routing unit. We then consider the problem of minimizing the diameter of the interconnection topology, as a measure of maximum delay, and establish efficient near-to optimal (explicit) topologies. Furthermore, we also consider the problem of maximizing the throughput of a stackable router. We show its hardness and derive bounds for the optimal solution. While, traditionally, the different routing units of a stackable router are linked together in a ring topology, through simulations we show that a major improvement in the diameter of stackable routers can be accomplished even through the employment of randomly-generated topologies. Finally, we investigate the basic problem of constructing a feasible stackable router and establish some fundamental properties of the required structure of the routing units.

Coping with network failures has become a major networking challenge. The concept of tunable survivability provides a quantitative measure for specifying any desired level (0%-100%) of survivability, thus offering flexibility in the routing choice. Previous works focused on implementing this concept on unicast transmissions. However, vital network information is often broadcasted via spanning trees. Accordingly, in this study, we investigate the application of tunable survivability for efficient maintenance of spanning trees under the presence of failures. We establish efficient algorithmic schemes for optimizing the level of survivability under various QoS requirements. In addition, we derive theoretical bounds on the number of required trees for maximum survivability. Finally, through extensive simulations, we demonstrate the effectiveness of the tunable survivability concept in the construction of spanning trees. Most notably, we show that, typically, negligible reduction in the level of survivability results in major improvement in the QoS performance of the resulting spanning trees.

Coping with network failures has been recognized as an issue of major importance in terms of social security, stability and prosperity. It has become clear that current networking standards fall short of coping with the complex challenge of surviving failures. The need to address this challenge has become a focal point of networking research. In particular, the concept of tunable survivability offers major performance improvements over traditional approaches. Indeed, while the traditional approach is to provide full (100%) protection against network failures through disjoint paths, it was realized that this requirement is too restrictive in practice. Tunable survivability provides a quantitative measure for specifying the desired level (0%-100%) of survivability and offers flexibility in the choice of the routing paths. Previous work focused on the simpler class of “bottleneck” criteria, such as bandwidth. In this study, we focus on the important and much more complex class of additive criteria, such as delay and cost. First, we establish some (in part, counter-intuitive) properties of the optimal solution. Then, we establish efficient algorithmic schemes for optimizing the level of survivability under additive end-to-end QoS bounds. Subsequently, through extensive simulations, we show that, at the price of negligible reduction in the level of survivability, a major improvement (up to a factor of 2) is obtained in terms of end-to-end QoS performance. Finally, we exploit the above findings in the context of a network design problem, in which we need to best invest a given “budget” for improving the performance of the network links.