Large-scale IT infrastructures are highly energy-intensive systems. To mitigate the environmental impact of networks, it is crucial to design energy-aware traffic engineering strategies that make the best use of a network’s redundancy in order to maximize energy savings. The Software-Defined Networking (SDN) paradigm is a powerful tool that eases network management by decoupling the control and data planes. Because of its flexibility and controllability, SDN is nowadays widely adopted in data centers and enterprise networks. In this paper, we provide energy-aware traffic solutions for SDNs. We conducted extensive experiments on real switches for a thorough power consumption characterisation. Thanks to this preliminary study, we could fully characterize the solution space of a performance-constrained energy optimization problem. We formulate two optimization problems for the selective activation of switches and ports under hard constraints on traffic demand, considering both a static and dynamic traffic scenario. We show that the proposed problems are NP-hard and provide two polynomial-time heuristics for the static and dynamic case, respectively. Through simulations, we show that our solution outperforms previous approaches in all the considered settings.

Massive failures in communication networks result from natural disasters, heavy blackouts, and military and cyber attacks. After these events, an adequate network recovery plan is key to ensuring emergency-critical service restoration and preventing intolerable downtime and performance degradation. We tackle the problem of minimizing the time and number of interventions to sufficiently restore the communication network to support emergency services after large-scale failures. We propose Proton (Progressive RecOvery and Tomography-based mONitoring), an efficient algorithm for progressive recovery of emergency services. Unlike previous work, assuming centralized routing and complete network observability, Proton addresses the more realistic scenario in which the network relies on the existing routing protocols, and knowledge of the network state is partial and uncertain. Proton relies on Network Tomography for monitoring and acquiring information about the state of nodes and links. Simulation results on real topologies show that our algorithm outperforms previous solutions in terms of cumulative routed flow, repair costs and recovery time in static and dynamic failure scenarios.

Massive failures in communication networks are a consequence of natural disasters, heavy blackouts, military and cyber attacks. We tackle the problem of minimizing the time and number of interventions to sufficiently restore the communication network so as to support emergency services after large-scale failures. We propose PRoTOn (Progressive RecOvery and Tomography-based mONitoring), an efficient algorithm for progressive recovery of emergency services. Unlike previous work, assuming centralized routing and complete network observability, PRoTOn addresses the more realistic scenario in which the network relies on the existing routing protocols, and knowledge of the network state is partial and uncertain. Simulation results carried out on real topologies show that our algorithm outperforms previous solutions in terms of cumulative routed flow, repair costs and recovery time in both static and dynamic failure scenarios.

Boolean Network Tomography (BNT) aims at identifying failures of internal network components by means of end-to-end monitoring paths. However, when the number of failures is not known a priori, failure identification may require a huge number of monitoring paths. We address this problem by designing a Bayesian approach that progressively selects the next path to probe on the basis of its expected information utility, conditioned on prior observations. As the complexity of the computation of posterior probabilities of node failures is exponential in the number of failed paths, we propose a polynomial-time greedy strategy which approximates these values. To consider aging of information in dynamic failure scenarios where node states can change during a monitoring period, we propose a monitoring technique based on a sliding observation window of adaptive length. By means of numerical experiments conducted on real network topologies we demonstrate the practical applicability of our approach, and the superiority of our algorithms with respect to state of the art solutions based on classic BNT as well as sequential group testing.

The multiplication of a matrix by its transpose, ATA, appears as an intermediate operation in the solution of a wide set of problems. In this paper, we propose a new cache-oblivious algorithm (AtA) for computing this product, based upon the classical Strassen algorithm as a sub-routine. In particular, we decrease the computational cost to the time required by Strassen’s algorithm, amounting to floating point operations. AtA works for generic rectangular matrices, and exploits the peculiar symmetry of the resulting product matrix for saving memory. In addition, we provide an extensive implementation study of AtA in a shared memory system, and extend its applicability to a distributed environment. To support our findings, we compare our algorithm with state-of-the-art solutions specialized in the computation of ATA. Our experiments highlight good scalability with respect to both the matrix size and the number of involved processes, as well as favorable performance for both the parallel paradigms and the sequential implementation, when compared with other methods in the literature.

Boolean Network Tomography (BNT) allows to localize network failures by means of end-to-end monitoring paths. Nevertheless, it falls short of providing efficient failure identification in real scenarios, due to the large combinatorial size of the solution space, especially when multiple failures occur concurrently. We aim at maximizing the identification capabilities of a bounded number of monitoring probes. To tackle this problem we propose a progressive approach to failure localization based on stochastic optimization, whose solution is the optimal sequence of monitoring paths to probe. We address the complexity of the problem by proposing a greedy strategy in two variants: one considers exact calculation of posterior probabilities of node failures given the observation, whereas the other approximates these values through a novel failure centrality metric. We discuss the approximation of the proposed approaches. Then, by means of numerical experiments conducted on real network topologies, we demonstrate the practical applicability of our approach. The performance evaluation evidences the superiority of our algorithms with respect to state of the art solutions based on classic Boolean Network Tomography as well as approaches based on sequential group testing.

Boolean network tomography is a powerful tool to infer the state (working/failed) of individual nodes from path-level measurements obtained by edge-nodes. We consider the problem of optimizing the capability of identifying network failures through the design of monitoring schemes. Finding an optimal solution is NP-hard and a large body of work has been devoted to heuristic approaches providing lower bounds. Unlike previous works, we provide upper bounds on the maximum number of identifiable nodes, given the number of monitoring paths and different constraints on the network topology, the routing scheme, and the maximum path length. These upper bounds represent a fundamental limit on identifiability of failures via Boolean network tomography. Our analysis provides insights on how to design topologies and related monitoring schemes to achieve the maximum identifiability under various network settings. Through analysis and experiments we demonstrate the tightness of the bounds and efficacy of the design insights for engineered as well as real networks.