The popularity of distributed machine learning applications and hardware training imposes increasingly stringent performance requirements on the interconnecting communication network. A clever scheduling of the computational workload has the potential to greatly improve datacenter resource utilization, by keeping frequently communicating nodes topologically close. A fundamental underlying optimization problem is known as (static) balanced graph partitioning: How to partition a graph (describing a workload) into equally-sized subgraphs (“clusters”) to minimize the number of inter-cluster edges?

Graph augmentation is a fundamental and well-studied problem that arises in network optimization. We consider a new variant of this model motivated by reconfigurable communication networks. In this variant, we consider a given physical network and the measured communication demands between the nodes. Our goal is to augment the given physical network with a matching, so that the shortest path lengths in the augmented network, weighted with the demands, are minimal. We prove that this problem is NP-hard, even if the physical network is a cycle. We then use results from demand-aware network design to provide a constant-factor approximation algorithm for adding a matching in case that only a few nodes in the network cause almost all the communication. For general real-world communication patterns, we design and evaluate a series of heuristics that can deal with arbitrary graphs as the underlying network structure. Our algorithms are validated experimentally using real-world traces (from e.g., Facebook) of data centers.

Demand-aware reconfigurable datacenter networks adapt toward the traffic they serve by providing topological shortcuts between frequently communicating racks. However, only little is known about computing optimized demand-aware networks quickly and in a distributed manner. In this paper, we investigate fast distributed algorithms to compute demand-aware networks for hybrid datacenters, where a fixed capacitated network can be enhanced with a bounded-degree demand-aware network, i.e., with a set of matchings created by optical circuit switches. We make two main contributions. Firstly, we present a distributed algorithm, called the Coordinator algorithm for computing demand-aware networks on all underlying topologies. The algorithm is analyzed in the widely deployed Clos topology and in the Congested Clique model, where it is optimal in terms of quality and nearly optimal in distributed runtime. Secondly, we focus on improving the round complexity at the cost of the quality of the resulting topology. We show that for tree demands, an adaptation of a distributed matching algorithm by Wattenhofer and Wattenhofer (DISC 2004) achieves a$1 / 6$-approximation. Based on this approach, we introduce the Propose and REJECT algorithm for general demands, which we evaluate on real-world Facebook datacenter and HPC traces. Our results show that the Propose and REJECT algorithm, even with limited knowledge of the demand matrix, performs nearly optimally on real traffic demands and covers over 80 % of the demand. This is achieved with significantly fewer communication rounds than the optimal solution computed by the Coordinator algorithm.

Small-world networks are attractive for the efficient routing they provide, requiring only a low link density. They have hence also been considered for the design of distributed systems, such as peer-to-peer networks. However, existing small-world network designs are oblivious to the actual traffic they serve. In this paper, we initiate the study of demand-aware small-world networks. In particular, we extend the Kleinberg graph model, by allowing the nodes to choose the distribution of long-range links according to the traffic demand. We present a formal analysis of the weighted route lengths for the important case of clustered demands. We show both in theory and in simulations, using real-world traffic workloads, that demand-aware small-world graphs can significantly outperform their demand-oblivious counterparts.

Emerging optical switching technologies enable demand-aware datacenter networks, whose topology can be flexibly optimized toward the traffic they serve. This paper revisits the bounded-degree network design problem underlying such demand-aware networks. Namely, given a distribution over communicating node pairs (represented has a demand graph), we want to design a network with bounded maximum degree (called host graph) that minimizes the expected communication distance. We improve the understanding of this problem domain by filling several gaps in prior work. First, we present the first practical algorithm for solving this problem on arbitrary instances without violating the degree bound. Our algorithm is based on novel insights obtained from studying a new Steiner node version of the problem, and we report on an extensive empirical evaluation, using several real-world traffic traces from datacenters, finding that our approach results in improved demand-aware network designs. Second, we shed light on the complexity and hardness of the bounded-degree network design problem by formally establishing its NP-completeness for any degree. We use our techniques to improve prior upper bounds for sparse instances. Finally, we study an intriguing connection between demand-aware network design and the virtual networking embedding problem, and show that the latter cannot be used to approximate the former: there is no universal host graph which can provide a constant approximation for our problem.

Graph augmentation is a fundamental and well-studied problem that arises in network optimization. We consider a new variant of this model motivated by reconfigurable communication networks. In this variant, we differentiate between a given physical network and the measured communication demands between the nodes. Our goal is to minimize the weighted average shortest path length via matching augmentation, where the weights correspond to the communication frequency of any pair of nodes. We use results from demand-aware network design to provide a constant-factor approximation algorithm for adding a matching on a ring in case only a few nodes in the network cause almost all the communication. Since the problem is NP-hard, we design and evaluate a series of heuristics that can deal with arbitrary graphs as underlying network structures. We evaluate our heuristics on general real-world communication patterns and show that already with simple and efficient heuristics we are able to reach near-optimal quality.

Finding large "cliquish" subgraphs is a classic NP-hard graph problem. In this work, we focus on finding maximum $s$-clubs and $s$-plexes, i.e., graphs of diameter $s$ and graphs where each vertex is adjacent to all but $s$ vertices. Preprocessing based on Turing kernelization is a standard tool to tackle these problems, especially on sparse graphs. We provide a new parameterized analysis for the Turing kernelization and demonstrate their usefulness in practice. Moreover, we provide evidence that the new theoretical bounds indeed better explain the observed running times than the existing theoretical running time bounds. To this end, we suggest a general method to compare how well theoretical running time bounds fit to measured running times.

Data reduction rules are an established method in the algorithmic toolbox for tackling computationally challenging problems. A data reduction rule is a polynomial-time algorithm that, given a problem instance as input, outputs an equivalent, typically smaller instance of the same problem. The application of data reduction rules during the preprocessing of problem instances allows in many cases to considerably shrink their size, or even solve them directly. Commonly, these data reduction rules are applied exhaustively and in some fixed order to obtain irreducible instances. It was often observed that by changing the order of the rules, different irreducible instances can be obtained. We propose to "undo" data reduction rules on irreducible instances, by which they become larger, and then subsequently apply data reduction rules again to shrink them. We show that this somewhat counter-intuitive approach can lead to significantly smaller irreducible instances. The process of undoing data reduction rules is not limited to "rolling back" data reduction rules applied to the instance during preprocessing. Instead, we formulate so-called backward rules, which essentially undo a data reduction rule, but without using any information about which data reduction rules were applied to it previously. In particular, based on the example of Vertex Cover we propose two methods applying backward rules to shrink the instances further. In our experiments we show that this way smaller irreducible instances consisting of real-world graphs from the SNAP and DIMACS datasets can be computed.

Editing a graph into a disjoint union of clusters is a standard optimization task in graph-based data clustering. Here, complementing classic work where the clusters shall be cliques, we focus on clusters that shall be 2-clubs, that is, subgraphs of diameter at most two. This naturally leads to the two NP-hard problems 2-Club Cluster Editing (the editing operations are edge insertion and edge deletion) and 2-Club Cluster Vertex Deletion (the editing operations are vertex deletions). Answering an open question, we show that 2-Club Cluster Editing is W[2]-hard with respect to the number of edge modifications, thus contrasting the fixed-parameter tractability result for the classic Cluster Editing problem (considering cliques instead of 2-clubs). Then, focusing on 2-Club Cluster Vertex Deletion, which is easily seen to be fixed-parameter tractable, we show that under standard complexity-theoretic assumptions it does not have a polynomial-size problem kernel when parameterized by the number of vertex deletions. Nevertheless, we develop several effective data reduction and pruning rules, resulting in a competitive solver, outperforming a standard CPLEX solver in most instances of an established biological test data set.

The performance of distributed and data-centric applications often critically depends on the interconnecting network. Applications are hence modeled as virtual networks, also accounting for resource demands on links. At the heart of provisioning such virtual networks lies the NP-hard Virtual Network Embedding Problem (VNEP): how to jointly map the virtual nodes and links onto a physical substrate network at minimum cost while obeying capacities.