In this article, a problem of rational splitter installation in Fiber‐to‐the‐Home (FTTH) networks is considered. The most expensive and time consuming part of the FTTH deployment is trenching and other labor involved in cable installation. When cables are deployed, the operator can start to connect customers to the network. However, the process still requires expenditures for both passive (splitters) and active (ONUs, OLT cards) equipment. First, we define an optimization problem of rational selection of splitters in the process of connecting new customers to a network. Second, we present two methods for handling the problem. The methods are named SpliSeals (Splitter Selection Algorithms). They take into account the actual take‐up rate and customer arrival patters to minimize the total expected cost of installed splitters. The average cost savings the presented algorithms can provide over rational, computer unaided methods exceed 10%, reaching almost 20% in some groups of cases, or even 40% in particular test cases. SpliSeals not only can be used to minimize the deployment cost of FTTH networks but also to assess the impact of uncertainty on network designs returned by automated methods. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 71(2), 153–165 2018

This work presents an on-line, energy- and communication-aware scheduling strategy for SaaS applications in data centers. The applications are composed of various services and represented as workflows. Each workflow consists of tasks related to each other by precedence constraints and represented by Directed Acyclic Graphs (DAGs). The proposed scheduling strategy combines advantages of state-of-the-art workflow scheduling strategies with energy-aware independent task scheduling approaches. The process of scheduling consists of two phases. In the first phase, virtual deadlines of individual tasks are set in the central scheduler. These deadlines are determined using a novel strategy that favors tasks which are less dependent on other tasks. During the second phase, tasks are dynamically assigned to computing servers based on the current load of network links and servers in a data center. The proposed approach, called Minimum Dependencies Energy-efficient DAG (MinD+ED) scheduling, has been implemented in the GreenCloud simulator. It outperforms other approaches in terms of energy efficiency, while keeping a satisfiable level of tardiness.

The present study deals with Elastic Flow Rerouting (EFR)—an original traffic restoration strategy for protecting traffic flows in communication networks (including wireless networks) against multiple link failures. EFR aims at alleviating the trade‐off between practicability of traffic restoration and the cost of network resources observed in existing networking solutions. We present an extension of EFR capable of managing multiple partial link failures. We describe EFR and its extension, formulate the EFR related optimization problems, and discuss approaches for their resolution. We also discuss numerical results illustrating effectiveness of EFR in terms of the link capacity cost. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(4), 267–281 2015

Abstract In this article, we revisit a classical optimization problem occurring in designing survivable multicommodity flow networks. The problem, referred to as FR, assumes flow restoration that takes advantage of the so‐called stub release. As no compact linear programming (LP) formulation of FR is known and at the same time all known noncompact LP formulations of FR exhibit \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document}\begin{align*}\mathcal{NP}\end{align*} \end{document} ‐hard dual separation, the problem itself is believed to be \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document}\begin{align*}\mathcal{NP}\end{align*} \end{document} ‐hard, although without a proof. In this article, we study a restriction of FR (RFR) that assumes only elementary (cycle‐free) admissible paths—an important case virtually not considered in the literature. The two problems have the same noncompact LP formulations as they differ only in the definition of admissible paths: all paths (also those including cycles) are allowed in FR, while only elementary paths are allowed in RFR. Because of that, RFR is in general computationally more complex than FR. The purpose of this article, is three‐fold. First, the article reveals an interesting special case of RFR—the case with only one failing link—for which a natural noncompact LP formulation obtained by reducing the general RFR formulation still exhibits \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document}\begin{align*}\mathcal{NP}\end{align*} \end{document} ‐hard dual separation, but nevertheless this special case of RFR is polynomial. The constructed example of a polynomial multicommodity flow problem with difficult dual separation is of interest since, to our knowledge, no example of this kind has been known. In this article, we also examine a second special case of RFR, this time assuming two failing links instead of one, which turns out to be \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document}\begin{align*}\mathcal{NP}\end{align*} \end{document} ‐hard. This implies that problem RFR is \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document}\begin{align*}\mathcal{NP}\end{align*} \end{document} ‐hard in general (more precisely, for two or more failure states). This new result is the second contribution of the article. Finally, we discuss the complexity of FR in the light of our new findings, emphasizing the differences between RFR and FR. © 2013 Wiley Periodicals, Inc. NETWORKS, 2013

Abstract In this article we prove 𝒩𝒫‐hardness of two well‐known optimization problems related to the design of multicommodity flow networks with two different methods for providing network resiliency against failures: path diversity and flow restoration. Path diversity is a static mechanism that consists of using, for each demand, a number of paths and oversizing the flows assigned to these paths so that for any failure the total surviving flow is not less than the volume of the demand. By contrast, flow restoration is a dynamic mechanism that consists of reassigning the failed flows to backup paths when a failure occurs. Both mechanisms are of practical interest because although flow restoration is in general superior to path diversity in terms of the required amount of resource capacity, it might be too complicated to implement. By providing an appropriate reduction from the fractional graph coloring problem, we show that both problems are 𝒩𝒫‐hard in the general case of failure scenarios that admit simultaneous failures of multiple links. Finally, we discuss how to efficiently solve the two problems using path generation techniques. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

In the paper we deal with the problem of optimal partitioning of a traffic demand polytope using a hyperplane. In the considered model all possible demand matrices belong to a polytope. The polytope can be divided into parts, and different routing schemes can be considered while dealing with traffic matrices from different parts of the polytope. The model can be applied to all networks that support unrestricted routing of bifurcated flows, e.g., MPLS networks or optical networks. In the paper we present an algorithm that solves one of the most practical versions of the considered problem, i.e., reservation vectors on both sides of the hyperplane have to be the same. Moreover, we present another (faster) algorithm that solves a more restricted version of the problem. Finally, we present numerical results proving the applicability of the introduced algorithms.