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?

409

The performance of distributed applications often critically depends on the throughput of the interconnecting network: how fast data can be carried across a network. Over the last years, great progress has been made in understanding demand-oblivious throughput: how fast a given demand matrix describing pairwise communication requirements, can be served on a given network. However, surprisingly little is known today about the achievable demand-aware throughput: the throughput on a network topology which can be optimized toward the demand. Such demand-aware networks have recently gained popularity in datacenters and are enabled by emerging reconfigurable optical technologies.

AllReduce is a fundamental collective communication operation in distributed computing and a key performance bottleneck for large-scale training and inference. Its completion time is determined by the number of communication steps, which dominate latency-sensitive workloads, and the communication distance affecting both latency- and bandwidth-bound regimes. Direct-connect topologies, such as Google's TPUv4 tori, are particularly prone to large communication distances due to limited bisection bandwidth.

All-to-All collective communication is a key performance bottleneck for distributed machine learning (ML) and high-performance computing (HPC) workloads, where dense traffic increasingly stresses scale-up interconnects. While these ML and HPC workloads have driven unprecedented infrastructure demand, optical reconfigurable networks (ORNs) offer a promising path forward as they can reconfigure the network at runtime. By adapting the physical topology to the active workload, they improve communication cost and bandwidth utilization. However, optical reconfigurable networks introduce a fundamental trade-off for collective communication: each reconfiguration requires global synchronization, during which communication is suspended for at a non-negligible delay. Additionally, their benefit is critically contingent on whether the collective consists of structured phases that can be served by sparse and reusable topology states.

Congestion control protocols regulate sending rates to optimize application performance and network utilization. In heterogeneous networks, however, applications often have different and conflicting performance objectives, making the design of suitable utility functions a challenging task that traditionally requires extensive mathematical analysis and experimental validation.

Modern communication networks support local fast rerouting mechanisms to quickly react to link failures: nodes store a set of conditional rerouting rules which define how to forward an incoming packet in case of incident link failures. Ideally, such rerouting mechanisms provide perfect resilience: any packet is routed from its source s to its target t as long as s and t are still connected in the underlying graph after the link failures. However, ensuring perfect resilience is algorithmically challenging as the rerouting decisions at any node v must rely solely on the local information available at v: the link from which a packet arrived at v (known as the in-port), the target of the packet, and the incident link failures at v. Already in their seminal paper at ACM PODC’12, Feigenbaum, Godfrey, Panda, Schapira, Shenker, and Singla showed that there are instances in which perfect resilience cannot be achieved. While the design of local rerouting algorithms has received much attention since then, we still lack a detailed understanding of when perfect resilience is achievable.

In the nonuniform graph partitioning problem, we are given a capacitated graph G on n vertices, and numbers n1, n2, …, nk summing to n. The goal is to partition the vertices of G into parts S1, S2, …, Sk with |Si| = ni for each i, and minimizing the capacity of edges crossing between distinct parts. This generalizes, for instance, the well-known graph bisection problem.

Plane spanners of bounded degree are efficient communication backbones for networks. However, while existing spanners provide attractive guarantees in the worst-case, they are demand-oblivious and may hence be suboptimal under specific traffic demands. This paper thus initiates the study of demand-aware plane spanners of bounded degree, geometric spanners whose topology accounts for the actual communication traffic. We show that demand-awareness can significantly reduce the distance travelled per bit, and present a spanner which exploits topological flexibilities to account for the demand, without losing desirable guarantees of demand-oblivious spanners, namely constant stretch and degree. We complement our analytical results with heuristic improvements and a simulation study exploring the benefits of demand-awareness under realistic traffic traces.

Public blockchain pseudonymity is vulnerable to off-chain cues: external information from sources such as social media or data leaks that can be linked to on-chain activity, enabling user de-anonymization. This paper provides the first comprehensive framework for systematically investigating this threat. We introduce a taxonomy of off-chain cues and propose methodologies to match such cues to blockchain data. Our empirical evaluation on the Ethereum blockchain quantifies the de-anonymization potential of both individual cues and their combinations, as well as real-world case studies such as the Celsius data leak. The results show that cue effectiveness is largely determined by uniqueness and exactness (e.g., specific transaction quantities, interactions with rare tokens), and that combining even a small number of moderately specific cues can significantly reduce anonymity sets. For users revealing multiple such cues, this can lead to the identification of a single on-chain address. In our Celsius simulation, knowledge of only the transaction day, asset, and exact quantity was sufficient to potentially identify over 85% of depositors. Our findings demonstrate the significant privacy risks posed by off-chain cues in blockchain linkage attacks to users disclosing them. Our work underscores the need for heightened user awareness and the development of effective countermeasures.

In modern datacenters, the effectiveness of end-to-end congestion control (CC) is quickly diminishing with the rapid bandwidth evolution. Per-hop flow control (FC) can react to congestion more promptly. However, a coarse-grained FC can result in Head-Of-Line (HOL) blocking. A fine-grained, per-flow FC can eliminate HOL blocking caused by flow control, however, it does not scale well. This paper presents Pyrrha, a scalable flow control approach that provably eliminates HOL blocking while using a minimum number of queues. In Pyrrha, flow control first takes effect on the root of the congestion, i.e., the port where congestion occurs. And then flows are controlled according to their contributed congestion roots. A prototype of Pyrrha is implemented on Tofino2 switches. Compared with state-of-the-art approaches, the average FCT of uncongested flows is reduced by 42%-98%, and 99th-tail latency can be$1.6\times $-$215\times $lower, without compromising the performance of congested flows.

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.

Traffic in datacenters may follow some pattern: some pairs of servers communicate more frequently than others. Demand-oblivious networks may perform poorly for such workloads, and demand-aware networks optimized for traffic should be used instead. Unfortunately, not all shapes of networks are feasible in real hardware. Practical limitations are usually provided in the form of a topology. For example, a network may be required to be a binary tree, a bounded-degree graph or a Fat tree.

Many applications, such as AI training and distributed storage, rely on cross-datacenter (DC) networks to provide services. For compatibility with existing RDMA hardware and to improve quality of service, network providers connect to datacenters over dedicated lines. However, the current RDMA congestion control has some problems in cross-DC environment. First, due to the large bandwidth delay product (BDP) of cross-DC flows, the switch frequently triggers PFC, which impairs the transmission of all flows. Meanwhile, due to the lag of congestion signals, congestion control algorithms may cause unfair bandwidth allocation between intra-DC flows and cross-DC flows. In addition, cross-DC traffic will experience severe queuing at the data center interconnect (DCI) switch, increasing queuing delay. To address these challenges, this paper proposes MLCC, a cross-datacenter congestion control algorithm based on the fast control loop. MLCC uses micro congestion control loops to achieve fine-grained network state awareness and accurate rate adaptation, and reduce queue length in the transmission path. Experimental results show that MLCC can quickly converge all flows to fairness, achieve high link utilization, and ensure low queue length on the switch. Large-scale simulations show that MLCC can reduce the average FCT of intra-datacenter and cross-datacenter traffic by up to 46% and 27%, respectively.

Machine learning models are highly dependent on the quality of their input data. In industrial settings, where video data is transmitted to the model located in the cloud over a network, transmission artifacts (e.g., congestion or losses) can degrade model performance. These performance issues can compromise process quality and result in costly errors. Despite the increasing interest in using Machine Learning (ML) models for video tasks in industrial use cases, existing research has not adequately assessed the impact of individual video artifacts on model performance, nor has it specifically examined the performance of video-based ML models under these conditions.This study aims to fill this gap by considering the impact of degraded data on the model behavior. As a case study, we consider a defect detection scenario where, e.g., a manufacturing robot is monitored for defections using video. To this end, we train a Multiscale Vision Transformer and use an approach that systematically introduces various artifacts, such as bitrate reduction and pixelation. We then assess their impact on the model’s performance accordingly. Hence, we provide the first insights into possible mitigations.

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.

Traffic shaping is a critical function for the efficient operation of modern networks, with applications ranging from data center networks to home routers. To correctly fulfill their expected task, traffic shapers must keep up with increasing line rates. While it is possible to scale traffic shapers across multiple CPUs via hardware queues, in some cases — such as when enforcing a global rate limit — these algorithms underperform due to lock contentions. This is especially true within the Linux kernel, where scheduling policies are realized as so-called queuing disciplines (qdiscs) and enforcing a global rate limit can only be achieved on what is effectively a single CPU core.In this work, we design and implement a lockless synchronization mechanism that allows qdiscs to efficiently scale rate limiting across multiple hardware queues. To demonstrate its practicality, we integrate this mechanism into the CAKE qdisc, enabling multiple CAKE instances to operate under the MQ qdisc while maintaining a global rate limit. We perform an extensive performance evaluation and find that the implementation achieves close to perfect scaling across cores, with an accuracy deviation with less that 0.25% of the configured rate, while keeping latencies low.

Effective scheduling of software updates is a significant challenge in network operations and management, particularly when considering specific performance and security requirements. This paper focuses on the synthesis of such software updates in the context of emerging virtualized and softwarized networks, such as 5G network infrastructures, with the objective of ensuring vulnerability avoidance and congestion freedom at any time during the updates. We formalize the update synthesis problem and propose an algorithmic solution, called Eagle, that exploits formal methods and mixed integer linear programming, to achieve optimal solutions. We then complement it with a greedy algorithm to support faster computation. We exemplify our framework considering an implementation of a 5G architecture, as the one described in the ETSI 5123 standard, and which relies on kubernetes. Finally, we evaluate our approach through a large range of realistic ISP topologies from the Topology Zoo dataset, and we also perform extensive experiments on our kubernetes cluster, where we execute the software update sequences generated by our tool. This allows us to discuss the scalability of our approach along with its practical applicability.

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.

To achieve fast recovery from link failures, most modern communication networks feature fully decentralized fast re-routing mechanisms. These re-routing mechanisms rely on pre-installed static re-routing rules at the nodes (the routers), which depend only on local failure information, namely on the failed links incident to the node. Ideally, a network is perfectly resilient: the re-routing rules ensure that packets are always successfully routed to their destinations as long as the source and the destination are still physically connected in the underlying network after the failures. Unfortunately, there are examples where achieving perfect resilience is not possible. Surprisingly, only very little is known about the algorithmic aspect of when and how perfect resilience can be achieved. We investigate the computational complexity of analyzing such local fast re-routing mechanisms. Our main result is a negative one: we show that even checking whether a given set of static re-routing rules ensures perfect resilience is coNP-complete. Additionally, we investigate other fundamental variations of the problem. In particular, we show that our coNP-completeness proof also applies to scenarios where the re-routing rules have specific patterns (known as skipping in the literature). On the positive side, for scenarios where nodes do not have information about the link from which a packet arrived (the so-called in-port), we present a linear-time algorithm to realize perfect resilience whenever possible (which we show can also be determined in linear time).

Modern communication networks employ local fast failover mechanisms in the data plane, swiftly reacting to link failures through pre-installed rerouting rules. This paper investigates resilient routing schemes that guarantee packet delivery under up to k link failures, provided the source and destination remain connected in the degraded network. While prior theoretical studies have mainly addressed static failures, where multiple links fail simultaneously and permanently, real networks often experience dynamic failures, such as transient link flapping caused by short-lived faults. We study the limits of basic and source-matched failover routing with packet-header rewriting against dynamic failures in general graphs. In basic routing, forwarding depends only on active links, incoming ports, and the destination, whereas source-matched routing additionally incorporates the source, requiring more memory (and logic) at the router. The 2-resilient source-matched routing for static failures is shown to fail under permanent but non-simultaneous failures. Moreover, even with source matching, we prove that in planar graphs k ≥ 2 resilience is impossible without bit rewriting, and in general graphs, perfect k-resilience is unachievable by only rewriting O(log k) bits. For planar graphs, we introduce ear-decomposition into basic routing and develop novel local rerouting mechanisms that tolerate dynamic failures. These yield tight 2-resilient basic routing by rewriting only one or two bits, closing the gap between lower bounds and practical routing scheme.

This paper revisits a fundamental distributed computing problem in the population protocol model. Provided n agents each starting with an input color in [k], the relative majority problem asks to find the predominant color. In the population protocol model, at each time step, a scheduler selects two agents that first learn each other's states and then update their states based on what they learned.

Liquid democracy is a transitive vote delegation mechanism over voting graphs. It enables each voter to delegate their vote(s) to another better-informed voter, with the goal of collectively making a better decision. The question of whether liquid democracy outperforms direct voting has been previously studied in the context of local delegation mechanisms (where voters can only delegate to someone in their neighbourhood) and binary decision problems. It has previously been shown that it is impossible for local delegation mechanisms to outperform direct voting in general graphs. This raises the question: for which classes of graphs do local delegation mechanisms yield good results?

We revisit the majority problem in the population protocol communication model, as first studied by Angluin et al. (Distributed Computing 2008). We consider a more general version of this problem known as plurality consensus, which has already been studied intensively in the literature. In this problem, each node in a system of n nodes, has initially one of k different opinions, and they need to agree on the (relative) majority opinion. In particular, we consider the important and intensively studied model of Undecided State Dynamics.

In Byzantine collaborative learning, n clients in a peer-to-peer network collectively learn a model without sharing their data by exchanging and aggregating stochastic gradient estimates. Byzantine clients can prevent others from collecting identical sets of gradient estimates. The aggregation step thus needs to be combined with an efficient (approximate) agreement subroutine to ensure convergence of the training process. In this work, we study the geometric median aggregation rule for Byzantine collaborative learning. We show that known approaches do not provide theoretical guarantees on convergence or gradient quality in the agreement subroutine. To satisfy these theoretical guarantees, we present a hyperbox algorithm for geometric median aggregation. We practically evaluate our algorithm in both centralized and decentralized settings under Byzantine attacks on non-i.i.d. data. We show that our geometric median-based approaches can tolerate sign-flip attacks better than known mean-based approaches from the literature.

Resource allocation in distributed and networked systems such as the Cloud is becoming increasingly flexible, allowing these systems to dynamically adjust toward the workloads they serve, in a demand-aware manner.

Payment channel networks (PCNs) are among the most promising solutions to the scalability issues in permissionless blockchains , allowing parties to pay each other off-chain through a path of payment channels (PCs). However, the cost of routing transactions is proportional to the number of intermediaries since each charges a fee. Analogous to other networks, malicious intermediaries on the path can lead to security/privacy threats. Virtual channels (VCs), i.e., bridges over PC paths, mitigate the above PCN issues: Intermediaries participate only in the VC setup but in no future VC payments. However, creating a VC has a cost that must be paid out of the bridged PCs’ balance. Currently, we are missing guidelines on how/where to set up VCs. Ideally, VCs should minimize transaction costs while mitigating security and privacy threats from on-path adversaries. In this work, we address for the first time the VC setup problem, formalizing it as an optimization problem . We present an integer linear program (ILP) computing the globally optimal VC setup strategy in terms of cost, security, and privacy. We accompany this expensive ILP with a fast, greedy algorithm . Our model and algorithms can be used with any on-path adversary whose strategy can be expressed as a set of corrupted nodes. We evaluate the greedy algorithm over a snapshot of the Lightning Network (LN), the largest Bitcoin-based PCN. Our results confirm that the greedy strategy minimizes costs while protecting against security and privacy threats and may serve the LN community as guidelines for VC deployment.

Self-Adjusting Networks (SAN) optimize their physical topology toward the demand in an online manner. Their application in data center networks is motivated by emerging hardware technologies, such as 3D MEMS Optical Circuit Switches (OCS). The Matching Model (MM) has been introduced to study the hybrid architecture of such networks. It abstracts from the electrical switches and focuses on the added (reconfigurable) optical ones. MM defines any SAN topology as a union of matchings over a set of top-of-rack (ToR) nodes, and assumes that rearranging the edges of a single matching comes at a fixed cost. In this work, we propose and study the Scalable Matching Model (SMM), a generalization of the MM, and present OpticNet, a framework that maps a set of ToRs to a set of OCSs to form a SAN topology. We prove that OpticNet uses the minimum number of switches to realize any bounded-degree topology and allows existing SAN algorithms to run on top of it, while preserving amortized performance guarantees. Our experimental results based on real workloads show that OpticNet is a flexible and efficient framework for the implementation and evaluation of SAN algorithms in reconfigurable data center environments.

Programmable Wireless Environments aim to render the communication environment a controllable, software-defined medium. Reconfigurable Intelligent Surfaces (RISes) are the key enabling technology, which can offer the real-time capability to manipulate impinging waves. RISes are expected to be widely deployed in B5G/6G networks to serve a large number of users simultaneously. Despite numerous analyses highlighting the benefits of utilizing previously unexploitable propagation factors through the use of RISes, there is a lack of analysis regarding their relation to the concept of network resource, their allocation to users/stakeholders and their fair pricing. Thus, this paper models RISes as networked resources. Based on this definition, the PRIME algorithm is proposed, the first algorithm for RIS resource allocation and joint pricing. PRIME strives for proportionality between the offered end-user performance level and the corresponding resource pricing, promoting fairness. The algorithm is validated via full-wave electromagnetic simulations and applies to multiple RIS functionalities and frequency bands.

Packet scheduling is a fundamental networking task that recently received renewed attention in the context of programmable data planes. Programmable packet scheduling systems such as those based on Push-In First-Out (PIFO) abstraction enabled flexible scheduling policies, but are too resource-expensive for large-scale line rate operation. This prompted research into practical programmable schedulers (e.g., SP-PIFO, AIFO) approximating PIFO behavior on regular hardware. Yet, their scalability remains limited due to extensive number of memory operations. To address this, we design an effective yet resource-efficient packet scheduler, Range-In First-Out (RIFO), which uses only three mutable memory cells and one FIFO queue per PIFO queue. RIFO is based on multi-criteria decision-making principles and uses small guaranteed admission buffers. Our large-scale simulations in Netbench demonstrate that despite using fewer resources, RIFO generally achieves competitive flow completion times across all studied workloads, and is especially effective in workloads with a significant share of large flows, reducing flow completion time up to$4.91\times $in datamining workload compared to state-of-the-art solutions. Our prototype implementation using P4 on Tofino switches requires only 600 lines of code, is scalable, and runs at line rate.

In this work, we revisit the severely limited throughput problem of cryptocurrencies and propose a novel rebalancing approach for Payment Channel Networks (PCNs). PCNs are a popular solution for increasing the blockchain throughput, however, their benefit depends on the overall users’ liquidity. Rebalancing mechanisms are the state-of-the-art approach to maintaining high liquidity in PCNs. However, existing opt-in rebalancing mechanisms exclude users that may assist in rebalancing for small service fees, leading to suboptimal solutions and under-utilization of the PCNs’ bounded liquidity. We introduce the first rebalancing approach for PCNs that includes all users, following an “all for one and one for all” design philosophy that yields optimal throughput. The proposed approach introduces a double-auction rebalancing problem, which we term Musketeer, where users can participate as buyers (paying fees to rebalance) or sellers (charging fees to route transactions). The desired properties tailored to the unique characteristics of PCNs are formally defined, including the novel property of cyclic budget balance that is a stronger variation of strong budget balance. Basic results derived from auction theory, including an impossibility and multiple mechanisms that either achieve all desiderata under a relaxed model or sacrifice one of the properties, are presented. We also propose a novel mechanism that leverages time delays as an additional cost to users. This mechanism is provably truthful, cyclic budget balanced, individually rational, and economic efficient but only with respect to liquidity.

In modern communication networks with stringent dependability requirements, local fast re-routing (FRR) is essential for a quick response to link failures. Configuring FRR for multiple failures is, however, challenging since a router's forwarding table may take into account only the failed links directly incident to it. We propose SyRep, an efficient method to repair and synthesize resilient FRR forwarding tables. At the heart of SyRep lies a method which identifies and removes ill-defined routing entries and employs symbolic binary decision diagram (BDD) technology to automatically replace the removed entries with correct values. SyRep cannot only be used to efficiently repair existing forwarding tables, but also to synthesize new tables from scratch, using an efficient hybrid approach: by first using fast heuristics that provide close-to-resilient routing tables and then quickly repair the ill-defined entries. We present such a fast heuristic based on novel structural reduction rules and our empirical evaluation shows that SyRep is up to three orders of magnitude faster compared to the state-of-the-art.

Datacenter networks are becoming increasingly flexible with the incorporation of new optical communication technologies, such as optical circuit switches, enabling self-adjusting topologies that can adapt to the traffic pattern in a demand-aware manner. In this paper, we take the first steps toward demand-aware and self-adjusting k-ary tree networks. These are more powerful generalizations of existing binary search tree networks (like SplayNet [22]), which have been at the core of self-adjusting network (SAN) designs. k-ary search tree networks are a natural generalization offering nodes of higher degrees, reduced route lengths, and local routing in spite of reconfigurations (due to maintaining the search property). Our main results are two online heuristics for self-adjusting k-ary tree networks. Empirical results show that our heuristics work better than SplayNet in most of the real network traces and for average to low locality synthetic traces, and are only a little inferior to SplayNet in all remaining traces. We build our online algorithms by first solving the offline case. First, we compute an offline (optimal) static demand-aware network for arbitrary traffic patterns in O(n3 · k) time via dynamic programming, where n is the number of network nodes (e.g., datacenter racks), and also improve the bound for the special case of uniformly distributed traffic. Then, we present a centroid-based approach to demand-aware network designs that we use both in the offline static and online settings. In the offline uniform-workload case, we construct this centroid network in linear time O(n).

Peer review, as a widely used practice to ensure the quality and integrity of publications, lacks a well-defined and common mechanism to self-incentivize virtuous behavior across all the conferences and journals. This is because information about reviewer efforts and author feedback typically remains local to a single venue, while the same group of authors and reviewers participate in the publication process across many venues. Previous attempts to incentivize the reviewing process assume that the quality of reviews and papers authored correlate for the same person, or they assume that the reviewers can receive physical rewards for their work. In this paper, we aim to keep track of reviewing and authoring efforts by users (who review and author) across different venues while ensuring self-incentivization. We show that our system, DecentPeeR, incentivizes reviewers to behave according to the rules, i.e., it has a unique Nash equilibrium in which virtuous behavior is rewarded.

In the well-known Minimum Linear Arrangement problem (MinLA), the goal is to arrange the nodes of an undirected graph into a permutation so that the total stretch of the edges is minimized. This paper studies an online variant of MinLA where the graph is not given at the beginning, but rather revealed piece-by-piece. The algorithm starts in a fixed initial permutation, and after a piece of the graph is revealed, the algorithm must update its current permutation to be a MinLA of the subgraph revealed so far. The objective is to minimize the total number of swaps of adjacent nodes as the algorithm updates the permutation. The main result of this paper is an online randomized algorithm that solves the online MinLA problem for the restricted cases where the graph is either a collection of cliques or a collection of lines. We show that the algorithm is$8\ ln n$- competitive, where$n$is the number of nodes of the graph. We complement this result by constructing a lower bound of$\Omega(\ln (n)$for competitiveness of any online algorithm, concluding that our randomized algorithm is asymptotically optimal.

Emerging reconfigurable optical communication technologies allow to enhance datacenter topologies with demand-aware links optimized towards traffic patterns. This paper studies the algorithmic problem of jointly optimizing topology and routing in such demand-aware networks to minimize congestion, along two dimensions: (1) splittable or unsplittable flows, and (2) whether routing is segregated, i.e., whether routes can or cannot combine both demand-aware and demand-oblivious (static) links.For splittable and segregated routing, we show that the problem is generally 2-approximable, but APX-hard even for uniform demands induced by a bipartite demand graph. For unsplittable and segregated routing, we establish upper and lower bounds of O (log m/ log log m) and Ω (log m/ log log m), respectively, for polynomial-time approximation algorithms, where m is the number of static links. We further reveal that under un-/splittable and non-segregated routing, even for demands of a single source (resp., d estina tion), the problem cannot be approximated better than $\Omega \left({\frac{{{c_{\max }}}}{{{c_{\min }}}}}\right)$ unless P=NP, where cmax(resp., cmin) denotes the maximum (resp., minimum) capacity. It remains NP-hard for uniform capacities, but is tractable for a single commodity and uniform capacities.Our trace-driven simulations show a significant reduction in network congestion compared to existing solutions.

We consider a variant of the online caching problem where the items exhibit dependencies among each other: an item can reside in the cache only if all its dependent items are also in the cache. The dependency relations can form any directed acyclic graph. These requirements arise in systems such as CacheFlow (SOSR 2016) that cache forwarding rules for packet classification in IP-based communication networks.First, we present an optimal randomized online caching algorithm which accounts for dependencies among the items. Our randomized algorithm is O(log k)-competitive, where k is the size of the cache, meaning that our algorithm never incurs the cost of O(log k) times higher than even an optimal algorithm that knows the future input sequence.Second, we consider the bypassing model, where requests can be served at a fixed price without fetching the item and its dependencies into the cache — a variant of caching with dependencies introduced by Bienkowski et al. at SPAA 2017. For this setting, we give an $O\left( {\sqrt {k \cdot \log k} } \right)$-competitive algorithm, which significantly improves the best known competitiveness. We conduct a small case study, to find out that our algorithm incurs on average 2x lower cost.

Modern communication networks support local fast re-routing (FRR) to quickly react to link failures. However, configuring such FRR mechanisms is challenging as the rules have to be defined ahead of time, without knowledge of the failures, and can depend only on local decisions made by the nodes incident to a failed link. Designing failover protection against multiple link failures is particularly difficult. We present a novel synthesis approach which addresses this challenge by generating FRR rules in an automated and provably correct manner. Our network model assumes that each node maintains a prioritised list of backup links (a.k.a. skipping forwarding)—an FRR method that allows for a memory-efficient deployment. We study the theoretical properties of the model and implement a synthesis method in our tool SyPer that aims to provide perfect resilience: if there are up to k link failures, we can always route traffic between any two nodes as long as they are still connected in the underlying physical network. To this end, SyPer focuses on the synthesis of efficient forwarding rules using the BDD (binary decision diagram) methodology and our empirical evaluation shows that SyPer is feasible, and can synthesize robust network configuration in realistic settings.

To meet stringent performance requirements, communication networks are becoming increasingly programmable and flexible, supporting fast and frequent adjustments. However, reconfiguring networks in a dependable and transiently consistent manner is known to be algorithmically challenging. This paper revisits the fundamental problem of how to update the routes in a network in a (transiently) loop-free manner, considering both the Strong Loop-Freedom (SLF) and the Relaxed Loop-Freedom (RLF) property.We present two fast algorithms to solve the SLF and RLF problem variants exactly, to optimality. Our algorithms are based on a parameterized integer linear program which would be intractable to solve directly by a classic solver. Our main technical contribution is a lazy cycle breaking strategy which, by adding constraints lazily, improves performance dramatically, and outperforms the state-of-the-art exact algorithms by an order of magnitude on realistic medium-sized networks. We further explore approximate algorithms and show that while a relaxation approach is relatively slow, with a local search approach short update schedules can be found, outperforming the state-of-the-art heuristics.On the theoretical front, we also provide an approximation lower bound for the update time of the state-of-the-art algorithm in the literature. As a contribution to the research community, we made all our code and implementations publicly available.

Microservice architectures and service meshes have become highly popular and face increasingly stringent scalability and dependability requirements. To achieve low-latency service execution and maximize performance, service providers of large-scale distributed systems deploy microservices geographically closer to their users in multi-cluster service mesh environments. However, inter-cluster service dependencies introduce additional latency, and effective load balancing across multiple replicas distributed across clusters is crucial. Addressing this challenge, we present L3, an adaptive latency-aware load-balancing mechanism for multi-cluster service meshes. We conduct extensive simulations on Amazon EC2, and our results of using the microservices of the DeathStarBench suite for three clusters show that L3 reduces the 99th percentile latency by 26% and 22% compared with round-robin and C3.

Emerging network applications ranging from video streaming to virtual/augmented reality should provide stringent quality-of-service (QoS) guarantees in complex and dynamic environments with shared resources. A promising approach to meeting these requirements is to automate complex network operations and create self-adjusting networks. These networks should automatically gather contextual information, analyze how to efficiently ensure QoS requirements, and adapt accordingly. This paper presents REACTNET, a self-adjusting networked system designed to achieve this vision by leveraging emerging network programmability and machine learning techniques. Programmability empowers REACTNET by providing fine-grained telemetry information, while machine learning-based classification techniques enable the system to learn and adjust the network to changing conditions. Our preliminary implementation of REACTNET in P4 and Python demonstrates its effectiveness in video streaming applications.

Given the increasingly stringent requirements on the performance and efficiency of communication networks, over the last years, great efforts have been made to render networks more flexible and programmable. In particular, modern networks support a flexible rerouting of flows, e.g., depending on the dynamically changing traffic or network conditions. However, the underlying algorithmic problems are still not well-understood today.In this paper, we revisit the k-Network Flow Update problem that asks for a schedule to reroute k unsplittable flows from their current paths to the given new paths, in a congestion-free manner in a capacitated network. We show that the problem is already NP-hard for three acyclic flows on simple directed graphs. Our main contribution is an efficient algorithm for sparse networks; specifically the algorithm is fixed parameter tractable in the number of flows and the treewidth of a graph that is the union of all flows. Our results also settle the open complexity question in the literature.

A public ledger is a tamperproof sequence of data that can be read and augmented by everyone. Public ledgers have innumerable and compelling uses. They can secure, in plain sight, all kinds of transactions ---such as titles, sales, and payments--- in the exact order in which they occur. Public ledgers not only curb corruption, but also enable very sophisticated applications ---such as cryptocurrencies and smart contracts. They stand to revolutionize the way a democratic society operates. As currently implemented, however, they scale poorly and cannot achieve their potential. Algorand is a truly democratic and efficient way to implement a public ledger. Unlike prior implementations based on proof of work, it requires a negligible amount of computation, and generates a transaction history that will not "fork" with overwhelmingly high probability. Algorand is based on (a novel and super fast) message-passing Byzantine agreement. For concreteness, we shall describe Algorand only as a money platform.

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.

We revisit the severely limited throughput problem of cryptocurrencies and propose a novel rebalancing approach for Payment Channel Networks (PCNs). PCNs are a popular solution for increasing the blockchain throughput, however, their benefit depends on the overall users' liquidity. Rebalancing mechanisms are the state-of-the-art approach to maintaining high liquidity PCNs. However, existing opt-in rebalancing mechanisms exclude users that may assist in rebalancing for small service fees, leading to suboptimal solutions and under-utilization of the PCNs' bounded liquidity.

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.

Abstract We study the problem of solving consensus in synchronous directed dynamic networks, in which communication is controlled by an oblivious message adversary that picks the communication graph to be used in a round from a fixed set of graphs $$\textbf{D}$$ D arbitrarily. In this fundamental model, determining consensus solvability and designing efficient consensus algorithms is surprisingly difficult. Enabled by a decision procedure that is derived from a well-established previous consensus solvability characterization for a given set $$\textbf{D}$$ D , we study, for the first time, the time complexity of solving consensus in this model: We provide both upper and lower bounds for this time complexity, and also relate it to the number of iterations required by the decision procedure. Among other results, we find that reaching consensus under an oblivious message adversary can take exponentially longer than both deciding consensus solvability and broadcasting the input value of some unknown process to all other processes.

We consider a natural problem dealing with weighted packet selection across a rechargeable link, which e.g., finds applications in cryptocurrency networks. The capacity of a link (u,v) is determined by how much nodes u and v allocate for this link. Specifically, the input is a finite ordered sequence of packets that arrive in both directions along a link. Given (u,v) and a packet of weight x going from u to v, node u can either accept or reject the packet. If u accepts the packet, the capacity on link (u,v) decreases by x. Correspondingly, v's capacity on (u,v) increases by x. If a node rejects the packet, this will entail a cost affinely linear in the weight of the packet. A link is “rechargeable” in the sense that the total capacity of the link has to remain constant, but the allocation of capacity at the ends of the link can depend arbitrarily on the nodes' decisions. The goal is to minimise the sum of the capacity injected into the link and the cost of rejecting packets. We show that the problem is NP-hard, but can be approximated efficiently with a ratio of (1+ε)⋅(1+3) for some arbitrary ε>0.

Throughput is a main performance objective in communication networks. This paper considers a fundamental maximum throughput routing problem — the All-or-Nothing Multicommodity Flow (ANF) problem — in arbitrary directed graphs and in the practically relevant but challenging setting where demands can be (much) larger than the edge capacities, mandating the need for splittable flows (i.e., flows may not follow a single path). Formally, the input for the ANF problem is an edge-capacitated directed graph where we have a given number of source-destination node-pairs with their respective demands and strictly positive weights. The goal is to route a maximum weight subset of the given pairs (i.e., the weighted throughput), respecting the edge capacities: A commodity is routed if all of its demand is routed from its respective source to destination (this is the all-or-nothing aspect). We present a polynomial-time bi-criteria approximation randomized rounding framework for this NP-hard problem that yields an arbitrarily good approximation on the weighted throughput while violating the edge capacity constraints by at most a sublogarithmic multiplicative factor. We present two non-trivial linear programming relaxations that can be used in the framework; the first uses a novel edge-flow formulation and the second uses a packing formulation. We demonstrate the “equivalence” of these formulations and then highlight the advantages of each of the two approaches. We complement our theoretical results with a proof of concept empirical evaluation, considering a variety of network scenarios.

With the increasing scale of communication networks, the likelihood of failures grows as well. Since these networks form a critical backbone of our digital society, it is important that they rely on robust routing algorithms which ensure connectivity despite such failures. While most modern communication networks feature robust routing mechanisms, these mechanisms are often fairly complex to design and verify, as they need to account for the effects of failures and rerouting on communication. This paper conceptualizes the design of robust routing mechanisms, with the aim to avoid such complexity. In particular, we showcase simple and generic blackbox transformations that increase resilience of routing against independently distributed failures, which allows to simulate the routing scheme on the original network, even in the presence of non-benign node failures (henceforth called faults). This is attractive as the system specification and routing policy can simply be preserved. We present a scheme for constructing such a reinforced network, given an existing (synchronous) network and a routing scheme. We prove that this algorithm comes with small constant overheads, and only requires a minimal amount of additional node and edge resources; in fact, if the failure probability is smaller than$1/n$, the algorithm can come without any overhead at all. At the same time, it allows to tolerate a large number of independent random (node) faults, asymptotically almost surely. We complement our analytical results with simulations on different real-world topologies.

We introduce a novel method for the rigorous quantitative evaluation of online algorithms that relaxes the "radical worst-case" perspective of classic competitive analysis. In contrast to prior work, our method, referred to as randomly infused advice (RIA), does not make any assumptions about the input sequence and does not rely on the development of designated online algorithms. Rather, it can be applied to existing online randomized algorithms, introducing a means to evaluate their performance in scenarios that lie outside the radical worst-case regime. More concretely, an online algorithm ALG with RIA benefits from pieces of advice generated by an omniscient but not entirely reliable oracle. The crux of the new method is that the advice is provided to ALG by writing it into the buffer ℬ from which ALG normally reads its random bits, hence allowing us to augment it through a very simple and non-intrusive interface. The (un)reliability of the oracle is captured via a parameter 0 ≤ α ≤ 1 that determines the probability (per round) that the advice is successfully infused by the oracle; if the advice is not infused, which occurs with probability 1 - α, then the buffer ℬ contains fresh random bits (as in the classic online setting). The applicability of the new RIA method is demonstrated by applying it to three extensively studied online problems: paging, uniform metrical task systems, and online set cover. For these problems, we establish new upper bounds on the competitive ratio of classic online algorithms that improve as the infusion parameter α increases. These are complemented with (often tight) lower bounds on the competitive ratio of online algorithms with RIA for the three problems.

We introduce self-adjusting partially ordered lists, a generalization of self-adjusting lists where additionally there may be constraints for the relative order of some nodes in the list. The lists self-adjust to improve performance while serving input sequences exhibiting favorable properties, such as locality of reference, but the constraints must be respected.We design a deterministic adjusting algorithm that operates without any assumptions about the input distribution and without maintaining frequency statistics or timestamps. Despite the more general model, we show that our deterministic algorithm performs closely to optimum (it is 4-competitive). In addition, we design a family of randomized algorithms with improved competitive ratios, handling also a more general rearrangement cost model, scaled by an arbitrary constant d ≥1. Moreover, we observe that different constraints influence the competitiveness of online algorithms, and we shed light on this aspect with a lower bound.We investigate the applicability of our self-adjusting lists in the context of network packet classification. Our evaluations show that our classifier performs similarly to a static list for low-locality traffic, but significantly outperforms Efficuts (by factor 7x), CutSplit (3.6x) and the static list (14x) for high locality and small rulesets.

51

Emerging reconfigurable datacenters allow to dynamically adjust the network topology in a demand-aware manner. These datacenters rely on optical switches which can be reconfigured to provide direct connectivity between racks, in the form of edge-disjoint matchings. While state-of-the-art optical switches in principle support microsecond reconfigurations, the demand-aware topology optimization constitutes a bottleneck.This paper proposes a dynamic algorithms approach to improve the performance of reconfigurable datacenter networks, by supporting faster reactions to changes in the traffic demand. This approach leverages the temporal locality of traffic patterns in order to update the interconnecting matchings incrementally, rather than recomputing them from scratch. In particular, we present six (batch-)dynamic algorithms and compare them to static ones. We conduct an extensive empirical evaluation on 176 synthetic and 39 real-world traces, and find that dynamic algorithms can both significantly improve the running time and reduce the number of changes to the configuration, especially in networks with high temporal locality, while retaining matching weight.

We consider the fundamental problem of designing a self-adjusting tree, which efficiently and locally adapts itself towards the demand it serves (namely accesses to the items stored by the tree nodes), striking a balance between the benefits of such adjustments (enabling faster access) and their costs (reconfigurations). This problem finds applications, among others, in the context of emerging demand-aware and reconfigurable datacenter networks and features connections to self-adjusting data structures. Our main contribution is SeedTree, a dynamically optimal self-adjusting tree which supports local (i.e., greedy) routing, which is particularly attractive under highly dynamic demands. SeedTree relies on an innovative approach which defines a set of unique paths based on randomized item addresses, and uses a small constant number of items per node. We complement our analytical results by showing the benefits of SeedTree empirically, evaluating it on various synthetic and real-world communication traces.

Data dissemination is a fundamental task in distributed computing. This paper studies broadcast problems in various innovative models where the communication network connecting n processes is dynamic (e.g., due to mobility or failures) and controlled by an adversary. In the first model, the processes transitively communicate their ids in synchronous rounds along a rooted tree given in each round by the adversary whose goal is to maximize the number of rounds until at least one id is known by all processes. Previous research has shown a ⌈(3n-1)/2⌉-2 lower bound and an O(nlog log n) upper bound. We show the first linear upper bound for this problem, namely ⌈(1+√2) n-1⌉ ≈ 2.4n. We extend these results to the setting where the adversary gives in each round k-disjoint forests and their goal is to maximize the number of rounds until there is a set of k ids such that each process knows of at least one of them. We give a ⌈3(n-k)/2⌉-1 lower bound and a (π²+6)/6 n+1 ≈ 2.6n upper bound for this problem. Finally, we study the setting where the adversary gives in each round a directed graph with k roots and their goal is to maximize the number of rounds until there exist k ids that are known by all processes. We give a ⌈3(n-3k)/2⌉+2 lower bound and a ⌈(1+√2)n⌉+k-1 ≈ 2.4n+k upper bound for this problem. For the two latter problems no upper or lower bounds were previously known.

We study the problem of solving consensus in synchronous directed dynamic networks, in which communication is controlled by an oblivious message adversary that picks the communication graph to be used in a round from a fixed set of graphs 𝐃 arbitrarily. In this fundamental model, determining consensus solvability and designing efficient consensus algorithms is surprisingly difficult. Enabled by a decision procedure that is derived from a well-established previous consensus solvability characterization for a given set 𝐃, we study, for the first time, the time complexity of solving consensus in this model: We provide both upper and lower bounds for this time complexity, and also relate it to the number of iterations required by the decision procedure. Among other results, we find that reaching consensus under an oblivious message adversary can take exponentially longer than both deciding consensus solvability and broadcasting the input value of some unknown process to all other processes.

Data plane programming gained much attention in the past years, having a fast-growing community both in academia and industry. Many tools have emerged to simplify and/or help the development of reliable data plane programs, including fuzzing, formal verification, and different code generators. However, even the tools themselves must be verified to meet the most stringent dependability requirements. In this paper, we investigate various tools and methods to verify code generators leveraging P4 through the example of P4RROT (an open source code generator focusing on the application layer). We show that our approach is efficient and can indeed successfully find bugs. We identify two bugs and propose reusable ideas, such as the use of ghost code.

Graphical games are a useful framework for modeling the interactions of (selfish) agents who are connected via an underlying topology and whose behaviors influence each other. They have wide applications ranging from computer science to economics and biology. Yet, even though a player's payoff only depends on the actions of their direct neighbors in graphical games, computing the Nash equilibria and making statements about the convergence time of "natural" local dynamics in particular can be highly challenging. In this work, we present a novel approach for classifying complexity of Nash equilibria in graphical games by establishing a connection to local graph algorithms, a subfield of distributed computing. In particular, we make the observation that the equilibria of graphical games are equivalent to locally verifiable labelings (LVL) in graphs; vertex labelings which are verifiable with a constant-round local algorithm. This connection allows us to derive novel lower bounds on the convergence time to equilibrium of best-response dynamics in graphical games. Since we establish that distributed convergence can sometimes be provably slow, we also introduce and give bounds on an intuitive notion of "time-constrained" inefficiency of best responses. We exemplify how our results can be used in the implementation of mechanisms that ensure convergence of best responses to a Nash equilibrium. Our results thus also give insight into the convergence of strategy-proof algorithms for graphical games, which is still not well understood.

Reconfigurable optical topologies are a promising new technology to improve datacenter network performance and cope with the explosive growth of traffic. In particular, these networks allow to directly and adaptively connect racks between which there is currently much traffic, hence making an optimal use of the bandwidth capacity by avoiding multi-hop forwarding.

To achieve fast recovery from link failures, most modern communication networks feature local fast failover mechanisms in the data plane. These failover mechanisms typically rely on pre-installed static rerouting rules which can depend only on local failure information. The locally limited failure information renders the problem of providing a high resilience algorithmically challenging. In this paper, we are interested in algorithms which tolerate a maximal number of k simultaneous link failures to guarantee packet delivery, as long as source and destination remain connected afterwards. Prior work showed that k=1 link failure can always be tolerated in general networks, but already the question of k=2 remained an unresolved problem.

The performance of many large-scale and data-intensive distributed systems critically depends on the capacity of the interconnecting network. This paper is motivated by the vision of self-adjusting infrastructures whose resources can be adjusted according to the workload they currently serve, in a demand-aware manner. Such dynamic adjustments can be exploited to improve network utilization and hence performance, by dynamically moving frequently interacting communication partners closer, e.g., collocating them in the same server or datacenter rack.

Dynamic programming (DP) is one of the fundamental paradigms in algorithm design. However, many DP algorithms have to fill in large DP tables, represented by two-dimensional arrays, which causes at least quadratic running times and space usages. This has led to the development of improved algorithms for special cases when the DPs satisfy additional properties like, e.g., the Monge property or total monotonicity. In this paper, we consider a new condition which assumes (among some other technical assumptions) that the rows of the DP table are monotone. Under this assumption, we introduce a novel data structure for computing $(1+\varepsilon)$-approximate DP solutions in near-linear time and space in the static setting, and with polylogarithmic update times when the DP entries change dynamically. To the best of our knowledge, our new condition is incomparable to previous conditions and is the first which allows to derive dynamic algorithms based on existing DPs. Instead of using two-dimensional arrays to store the DP tables, we store the rows of the DP tables using monotone piecewise constant functions. This allows us to store length-$n$ DP table rows with entries in $[0,W]$ using only polylog$(n,W)$ bits, and to perform operations, such as $(\min,+)$-convolution or rounding, on these functions in polylogarithmic time. We further present several applications of our data structure. For bicriteria versions of $k$-balanced graph partitioning and simultaneous source location, we obtain the first dynamic algorithms with subpolynomial update times, as well as the first static algorithms using only near-linear time and space. Additionally, we obtain the currently fastest algorithm for fully dynamic knapsack.

Datacenter networks have become a critical infrastructure of our digital society and over the last years, great efforts have been made to better understand the communication patterns inside datacenters. In particular, existing empirical studies showed that datacenter traffic typically features much temporal and spatial structure, and that at any given time, some communication pairs interact much more frequently than others. This paper generalizes this study to communication groups and analyzes how clustered the datacenter traffic is, and how stable these clusters are over time. To this end, we propose a methodology which revolves around a biclustering approach, allowing us to identify groups of racks and servers which communicate frequently over the network. In particular, we consider communication patterns occurring in three different Facebook datacenters: a Web cluster consisting of web servers serving web traffic, a Database cluster which mainly consists of MySQL servers, and a Hadoop cluster. Interestingly, we find that in all three clusters, small groups of racks and servers can produce a large fraction of the network traffic, and we can determine these groups even when considering short snapshots of network traffic. We also show empirically that these clusters are fairly stable across time. Our insights on the size and stability of communication clusters hence uncover an interesting potential for resource optimizations in datacenter infrastructures.

The increasingly stringent dependability requirements on communication networks as well as the need to render these networks more adaptive to improve performance, demand for more automated approaches to operate networks. We present AllSynth, a symbolic synthesis tool for updating communication networks in a provably correct and efficient manner. AllSynth automatically synthesizes network update schedules which transiently ensure a wide range of policy properties expressed using linear temporal logic (LTL). In particular, in contrast to existing approaches, AllSynth symbolically computes and compactly represents all feasible and cost-optimal solutions. At its heart, AllSynth relies on a novel parameterized use of binary decision diagrams (BDDs) which greatly improves performance. Indeed, AllSynth not only provides formal correctness guarantees and outperforms existing state-of-the-art tools in terms of generality, but also in terms of runtime as documented by experiments on a benchmark of real-world network topologies.

The performance of many data-centric cloud applications critically depends on the performance of the underlying datacenter network. Reconfigurable optical technologies have recently introduced a novel opportunity to improve datacenter network performance, by allowing to dynamically adjust the network topology according to the demand. However, the vision of self-adjusting networks raises the fundamental question how such networks can be efficiently operated in a scalable and distributed manner. This article presents$DiSplayNet$, the first fully distributed self-adjusting network.$DiSplayNet$relies on algorithms that perform decentralized and concurrent topological adjustments to account for changes in the demand. We propose two natural metrics to evaluate the performance of distributed self-adjusting networks, theamortized work(the cost of routing on and adjusting the network) and themakespan(the time it takes to serve a set of communication requests). We present a rigorous formal analysis of the work and makespan of$DiSplayNet$, which can be seen as an interesting generalization of analyses known from sequential self-adjusting datastructures. We complement our theoretical contribution with an extensive trace-driven simulation study, shedding light on the opportunities and limitations of leveraging spatial and temporal locality and concurrency in self-adjusting networks.

We introduce a runtime verification framework for programmable switches that complements static analysis. To evaluate our approach, we design and developP6, a runtime verification system that automatically detects, localizes, and patches software bugs in P4 programs. Bugs are reported via a violation of pre-specified expected behavior that is captured byP6.P6is based on machine learning-guided fuzzing that tests P4 switch non-intrusively, i.e., without modifying the P4 program for detecting runtime bugs. This enables an automated and real-time localization and patching of bugs. We used aP6prototype to detect and patch existing bugs in various publicly available P4 application programs deployed on two different switch platforms, namely, behavioral model (bmv2) and Tofino. Our evaluation shows thatP6significantly outperforms bug detection baselines while generating fewer packets and patches bugs in large P4 programs, e.g.,switch.p4without triggering any regressions.

The precise estimation of resource usage is a complex and challenging issue due to the high variability and dimensionality of heterogeneous service types and dynamic workloads. Over the last few years, the prediction of resource usage and traffic has received ample attention from the research community. Many machine learning-based workload forecasting models have been developed by exploiting their computational power and learning capabilities. This paper presents the first systematic survey cum performance analysis-based comparative study of diversified machine learning-driven cloud workload prediction models. The discussion initiates with the significance of predictive resource management followed by a schematic description, operational design, motivation, and challenges concerning these workload prediction models. Classification and taxonomy of different prediction approaches into five distinct categories are presented focusing on the theoretical concepts and mathematical functioning of the existing state-of-the-art workload prediction methods. The most prominent prediction approaches belonging to a distinct class of machine learning models are thoroughly surveyed and compared. All five classified machine learning-based workload prediction models are implemented on a common platform for systematic investigation and comparison using three distinct benchmark cloud workload traces via experimental analysis. The essential key performance indicators of state-of-the-art approaches are evaluated for comparison and the paper is concluded by discussing the trade-offs and notable remarks.

Payment channel networks (PCNs) are one of the most prominent solutions to the limited transaction throughput of blockchains. Nevertheless, PCNs suffer themselves from a throughput limitation due to the capital constraints of their channels. A similar dependence on high capital is also found in inter-bank payment settlements, where the so-called netting technique is used to mitigate liquidity demands.

Most modern communication networks feature fast rerouting mechanisms in the data plane. However, design and configuration of such mechanisms even under multiple failures is known to be difficult. In order to increase the resilience of the widely deployed MPLS networks, we propose R-MPLS, an alternative link protection mechanism for MPLS networks that uses recursive protection and can route around multiple simultaneously failed links. Our new R-MPLS approach comes with strong theoretical underpinnings, is implementable in a fully distributed way and executable on existing MPLS hardware, and formally guarantees that no forwarding loops are introduced. We implement our R-MPLS protection in an automated tool which overcomes the complexity of configuring such resilient network data planes, and report on the benefits of recursive protection in realistic network topologies. We find that R-MPLS significantly increases network robustness against multiple failures, with only moderate increase in the number of forwarding rules and communication overhead (both comparable to industry-standards like RSVP-TE FRR).

To meet their stringent requirements in terms of performance and dependability, communication networks should be "well connected". While classic connectivity measures typically revolve around topological properties, e.g., related to cuts, these measures may not reflect well the degree to which a network is actually dependable. We introduce a more refined measure for network connectivity, the hazard value, which is developed to meet the needs of a real network operator. It accounts for crucial aspects affecting the dependability experienced in practice, including actual traffic patterns, distribution of failure probabilities, routing constraints, and alternatives for services with preferences therein. We analytically show that the hazard value fulfills several fundamental desirable properties that make it suitable for comparing different network topologies with one another, and for reasoning about how to efficiently enhance the robustness of a given network. We also present an optimised algorithm to compute the hazard value and an experimental evaluation against networks from the Internet Topology Zoo and classical datacenter topologies, such as fat trees and BCubes. This evaluation shows that the algorithm computes the hazard value within minutes for realistic networks, making it practically usable for network designers.

Modern communication networks feature fully decen-tralized flow rerouting mechanisms which allow them to quickly react to link failures. This paper revisits the fundamental algorithmic problem underlying such local fast rerouting mechanisms. Is it possible to achieve perfect resilience, i.e., to define local routing tables which preserve connectivity as long as the underlying network is still connected? Feigenbaum et al. [1] and Foerster et al. [2] showed that, unfortunately, it is impossible in general.This paper charts a more complete landscape of the feasibility of perfect resilience. We first show a perhaps surprisingly large price of locality in static fast rerouting mechanisms: even when source and destination remain connected by a linear number of link-disjoint paths after link failures, local rerouting algorithms cannot find any of them which leads to a disconnection on the routing level. This motivates us to study resilience in graphs which exclude certain dense minors, such as cliques or a complete bipartite graphs, and in particular, provide characterizations of the possibility of perfect resilience in different routing models. We provide further insights into the price of locality by showing impossibility results for few failures and investigate perfect resilience on Topology Zoo networks.

We revisit the design of self-adjusting single-source tree networks. The problem can be seen as a generalization of the classic list update problem to trees, and finds applications in reconfigurable datacenter networks. We are given a balanced binary tree T connecting n nodes V = {v1,…, vn}. A source node v0, attached to the root of the tree, issues communication requests to nodes in V , in an online and adversarial manner; the access cost of a request to a node v, is given by the current depth of v in T . The online algorithm can try to reduce the access cost by performing swap operations, with which the position of a node is exchanged with the position of its parent in the tree; a swap operation costs one unit. The objective is to design an online algorithm which minimizes the total access cost plus adjustment cost (swapping). Avin et al. [12] (LATIN 2020) recently presented RANDOM-PUSH, a constant competitive online algorithm for this problem, based on random walks, together with a sophisticated analysis exploiting the working set property.This paper studies analytically and empirically, online algorithms for this problem. In particular, we explore how to derandomize RANDOM-PUSH. In the analytical part, we consider a simple derandomized algorithm which we call ROTOR-PUSH, as its behavior is reminiscent of rotor walks. Our first contribution is a proof that ROTOR-PUSH is constant competitive: its competitive ratio is 12 and hence by a factor of five lower than the best existing competitive ratio. Interestingly, in contrast to RANDOM-PUSH, the algorithm does not feature the working set property, which requires a new analysis. We further present a significantly improved and simpler analysis for the randomized algorithm, showing that it is 16-competitive.In the empirical part, we compare all self-adjusting single-source tree networks, using both synthetic and real data. In particular, we shed light on the extent to which these self-adjusting trees can exploit temporal and spatial structure in the workload. Our experimental artefacts and source codes are publicly available.

Google's BBR is the most prominent result of the recently revived quest for efficient, fair, and flexible congestion-control algorithms (CCAs). While BBR has been investigated by numerous studies, previous work still leaves gaps in the understanding of BBR performance: Experiment-based studies generally only consider network settings that researchers can set up with manageable effort, and model-based studies neglect important issues like convergence.

Self-adjusting networks (SANs) utilize novel optical switching technologies to support dynamic physical network topology reconfiguration. SANs rely on online algorithms to exploit this topological flexibility to reduce the cost of serving network traffic, leveraging locality in the demand. While prior work has shown the potential of SANs, the theoretical guarantees rely on a simplified cost model in which traversing and adjusting a single link has uniform cost.We initiate the study of online algorithms for SANs in a more realistic cost model, the Matching Model (MM), in which the network topology is given by the union of a constant number of bipartite matchings (realized by optical switches), and in which changing an entire matching incurs a fixed cost α. The cost of routing is given by the number of hops packets need to traverse.Our main result is a lazy topology adjustment method for designing efficient online SAN algorithms in the MM. We design and analyze online SAN algorithms for line, tree, and bounded degree networks in the MM, with cost ${\mathcal{O}}(\sqrt \alpha )$ times the cost of reference algorithms in the uniform cost model. We report on empirical results considering publicly available datacenter network traces, that verify the theoretical bounds.

Reconfigurable optical topologies promise to improve the performance in datacenters by dynamically optimizing the physical network in a demand-aware manner. State-of-the-art optical technologies allow to establish and update direct connectivity (in the form of edge-disjoint matchings) between top-of-rack switches within microseconds or less. However, to fully exploit temporal structure in the demand, such fine-grained reconfigurations also require fast algorithms for optimizing the interconnecting matchings.Motivated by the desire to offload a maximum amount of demand to the reconfigurable network, this paper initiates the study of fast algorithms to find k disjoint heavy matchings in graphs. We present and analyze six algorithms, based on iterative matchings, b-matching, edge coloring, and node-rankings. We show that the problem is generally ${\mathcal{N}}{\mathcal{P}}{\text{ - hard}}$ and study the achievable approximation ratios.An extensive empirical evaluation of our algorithms on both real-world and synthetic traces (88 in total), including traces collected in Facebook datacenters and in HPC clusters reveals that all our algorithms provide high-quality matchings, and also very fast ones come within 95 % or more of the best solution. However, the running times differ significantly and what is the best algorithm depends on k and the acceptable runtime-quality tradeoff.

We study the broadcast problem on dynamic networks with n processes. The processes communicate in synchronous rounds along an arbitrary rooted tree. The sequence of trees is given by an adversary whose goal is to maximize the number of rounds until at least one process reaches all other processes. Previous research has shown a ⌈(3n-1)/(2)⌉-2 lower bound and an O(n log log n) upper bound. We show the first linear upper bound for this problem, namely ⌈(1 + √2) n-1⌉ ~2.4n. Our result follows from a detailed analysis of the evolution of the adjacency matrix of the network over time.

Today's network devices share buffer across queues to avoid drops during transient congestion and absorb bursts. As the buffer-per-bandwidth-unit in datacenter decreases, the need for optimal buffer utilization becomes more pressing. Typical devices use a hierarchical packet admission control scheme: First, a Buffer Management (BM) scheme decides the maximum length per queue at the device level and then an Active Queue Management (AQM) scheme decides which packets will be admitted at the queue level. Unfortunately, the lack of cooperation between the two control schemes leads to (i) harmful interference across queues, due to the lack of isolation; (ii) increased queueing delay, due to the obliviousness to the per-queue drain time; and (iii) thus unpredictable burst tolerance. To overcome these limitations, we propose ABM, Active Buffer Management which incorporates insights from both BM and AQM. Concretely, ABM accounts for both total buffer occupancy (typically used by BM) and queue drain time (typically used by AQM). We analytically prove that ABM provides isolation, bounded buffer drain time and achieves predictable burst tolerance without sacrificing throughput. We empirically find that ABM improves the 99th percentile FCT for short flows by up to 94% compared to the state-of-the-art buffer management. We further show that ABM improves the performance of advanced datacenter transport protocols in terms of FCT by up to 76% compared to DCTCP, TIMELY and PowerTCP under bursty workloads even at moderate load conditions.

Networked systems are increasingly flexible and reconfigurable. This enables demand-aware infrastructures whose resources can be adjusted according to the traffic pattern they currently serve.

Online algorithms make decisions based on past inputs, with the goal of being competitive against an algorithm that sees also future inputs. In this work, we introduce time-local online algorithms; these are online algorithms in which the output at any given time is a function of only T latest inputs. Our main observation is that time-local online algorithms are closely connected to local distributed graph algorithms: distributed algorithms make decisions based on the local information in the spatial dimension, while time-local online algorithms make decisions based on the local information in the temporal dimension. We formalize this connection, and show how we can directly use the tools developed to study distributed approximability of graph optimization problems to prove upper and lower bounds on the competitive ratio achieved with time-local online algorithms. Moreover, we show how to use computational techniques to synthesize optimal time-local algorithms.

Abstract This paper considers the area convergence problem, which requires a group of robots to gather in a small area not defined a priori. While it is known that robots can gather at a point if they can precisely measure distances, we, in this paper, show that without any agreement on the coordinate system, it is impossible for robots to converge to an area if they cannot measure distances or angles. We denote these robots without the ability to measure distances or angles as monoculus robots. We present a counterexample showing that monoculus robots fail in area convergence even with the capability of measuring angles. However, monoculus robots with a weak notion of distance or minimal agreement on the coordinate system are sufficient to achieve area convergence. In particular, we present area convergence algorithms in asynchronous model for such monoculus robots with one of the two following simple additional capabilities: (1) locality detection ($\mathcal{L}\mathcal{D}$), a notion of distance or (2) orthogonal line agreement ($\mathcal{O}\mathcal{L}\mathcal{A}$), a notion of direction. We discuss extensions corresponding to multiple dimensions and the termination. Additionally, we validate our findings using simulation and show the robustness of our algorithms in the presence of errors in observation or movement.

Off-chain networks provide an attractive solution to the scalability challenges faced by cryptocurrencies such as Bitcoin. While first interesting networks are emerging, we currently have relatively limited insights into the structure and distribution of these networks. Such knowledge, however, is useful, when reasoning about possible performance improvements or the security of the network. For example, information about the different node types and implementations in the network can help when planning the distribution of critical software updates. This paper reports on a large measurement study of Lightning, a leading off-chain network, considering recorded network messages over a period of more than two years. In particular, we present an approach to classify the node types (LND, C-Lightning and Eclair) in the network, and find that we can determine the implementation of 99.9% of nodes correctly in our data set. We then report on geographical aspects of the Lightning Network, showing that proximity is less relevant, and that the Lightning Network is particularly predominant in metropolitan areas. Furthermore, we address various aspects of channels in the Lightning Network combined with the data we classified. We also demonstrate that channel endpoints behave very fairly and rarely cheat, that the same channel endpoints tend not to reconnect after the channel connection has closed and that there are more inactive than active channels in the Lightning Network. As a contribution to the research community, we will release our experimental data together with this paper.

Programmable wireless environments (PWEs) utilize internetworked intelligent metasurfaces to transform wireless propagation into a software-controlled resource. In this article, the interplay is explored between the user devices, the metasurfaces, and the PWE control system from the theory to the end-to-end implementation. This article first discusses the metasurface hardware and software, covering the complete workflow from the user device initialization to its final service via the PWE. Furthermore, to be compatible with the 5G and 6G wireless systems, the software-defined networking (SDN) paradigm is extended to achieve scalable internetworking and central control in PWE deployments with multiple metasurfaces and multihop communication. Subsequently, the set of SDN foundations is exploited in order to abstract the physics behind PWEs and a theoretical framework is established to describe and manipulate them in an algorithmic form. This can lead to smart radio environments that are readily accessible from various engineering disciplines, facilitating their integration into existing networks, wireless systems, and applications. This article is concluded by outlining strategies for the optimal placement of metasurfaces within a PWE-controlled space, open challenges in PWE security, specialized SDN integration issues, and theoretical problems toward the graph-driven modeling of PWEs.

To provide fast traffic recovery upon failures, most modern networks support static Fast Rerouting (FRR) mechanisms for mission critical services. However, configuring FRR mechanisms to toleratemultiplefailures poses challenging algorithmic problems. While state-of-the-art solutions leveraging arc-disjoint arborescence-based network decompositions ensure that failover routes always reach their destinations eventually, even under multiple concurrent failures, these routes may be long and introduce unnecessary loads; moreover, they are tailored to worst-case failure scenarios. This article presents an algorithmic framework for improving a given FRR network decomposition,using postprocessing. In particular, our framework is based on iterative arc swapping strategies and supports a number of use cases, from strengthening the resilience (e.g., in the presence of shared risk link groups) to improving the quality of the resulting routes (e.g., reducing route lengths and induced loads). Our simulations show that postprocessing is indeed beneficial in various scenarios, and can therefore enhance today’s approaches.

ISP networks have become a critical infrastructure in our society. Traffic in these networks is growing and is increasingly dominated by a small number of large CDNs connecting at multiple locations. Simultaneously, the networks are becoming more flexible, in terms of routing, CDN user mapping, and also regarding the IP topology: emerging optical technologies allow to flexibly reconfigure the network. This paper studies the potential gains of these reconfiguration flexibilities. The idea is to make CDN-ISP infrastructure demand-aware, that is, to re-optimize it towards the changing end-user demands over time. We present an optimization framework and conduct an extensive evaluation using data from a large European ISP. We find that such a reconfigurable infrastructure has indeed a high potential: by leveraging spatial and diurnal traffic patterns, the efficiency of ISP networks and CDNs is improved significantly. Specifically, the required backbone capacity is reduced by 15% while reducing path lengths by 30%, on average and during the critical peak hour. Moreover, such infrastructures can leverage re-optimizations during specific events, like the COVID-19 pandemic, and under link failures. We optimistically assume a cooperative environment of ISPs and CDNs, and we conclude by discussing trends that foster the identified benefits in practice.

Emerging communication technologies allow to reconfigure the physical network topology at runtime, enablingdemand-aware networks (DANs): networks whose topology is optimized toward the workload they serve. However, today, only little is known about the fundamental algorithmic problems underlying the design of such demand-aware networks. This paper presents the first bounded-degree, demand-aware network,$\textit {cl-DAN} $, which minimizesbothcongestion and route lengths. The degree bound$\Delta $is given as part of the input. The designed network is provably (asymptotically) optimal in each dimension individually: we show that there do not exist any bounded-degree networks providing shorter routes (independently of the load), nor do there exist networks providing lower loads (independently of the route lengths). The main building block of the designed$\textit {cl-DAN} $networks are$\textit {ego-trees}$: communication sources arrange their communication partners in an optimal tree,individually. While the union of these ego-trees forms the basic structure of$\textit {cl-DANs}$, further techniques are presented to ensure bounded degrees (for scalability).

This paper studies a fundamental algorithmic problem related to the design of demand-aware networks: networks whose topologies adjust toward the traffic patterns they serve, in an online manner. The goal is to strike a tradeoff between the benefits of such adjustments (shorter routes) and their costs (reconfigurations). In particular, we consider the problem of designing a self-adjusting tree network which serves single-source, multi-destination communication. The problem is a central building block for more general self-adjusting network designs and has interesting connections to self-adjusting datastructures. We present two constant-competitive online algorithms for this problem, one randomized and one deterministic. Our approach is based on a natural notion of Most Recently Used (MRU) tree, maintaining a working set. We prove that the working set is a cost lower bound for any online algorithm, and then present a randomized algorithm RANDOM- PUSH which approximates such an MRU tree at low cost, by pushing less recently used communication partners down the tree, along a random walk. Our deterministic algorithm Move-Half does not directly maintain an MRU tree, but its cost is still proportional to the cost of an MRU tree, and also matches the working set lower bound.

Most modern communication networks include fast rerouting mechanisms, implemented entirely in the data plane, to quickly recover connectivity after link failures. By relying on local failure information only, these data plane mechanisms provide very fast reaction times, but at the same time introduce an algorithmic challenge in case of multiple link failures: failover routes need to be robust to additional but locally unknown failures downstream. This paper presents local fast rerouting algorithms which not only provide a high degree of resilience against multiple link failures, but also ensure a low congestion on the resulting failover paths. We consider a randomized approach and focus on networks which are highly connected before the failures occur. Our main contribution are three simple algorithms which come with provable guarantees and provide interesting resilience-load tradeoffs, significantly outperforming any deterministic fast rerouting algorithm with high probability.

Future communication networks are expected to be highly automated, disburdening human operators of their most complex tasks. While the first powerful and automated network analysis tools are emerging, existing tools provide only limited and inefficient support of reasoning aboutfailure scenarios. We present P-REX, a fastwhat-if analysistool, that allows us to test important reachability and policy-compliance properties even under anarbitrary numberof failures and inpolynomial-time, i.e., without enumerating all failure scenarios (the usual approach today, if supported at all). P-REX targets networks based on Multiprotocol Label Switching (MPLS) and its Segment Routing (SR) extension which feature fast rerouting mechanisms with label stacks. In particular, P-REX allows to reason about recursive backup tunnels, by supporting potentially infinite state spaces. As P-REX directly operates on the actual dataplane configuration, i.e., forwarding tables, it is well-suited for debugging. Our tool comes with an expressive query language based on regular expressions. We also report on an industrial case study and demonstrate that our tool can perform what-if reachability analyses on average in about 5 seconds for a 24-router network with over 250,000 MPLS forwarding rules. This is a significant improvement to an earlier prototype of our tool presented in the conference version of our paper where the verification took on average about 1 hour.

Given the explosively growing traffic related to data-centric applications and AI, especially to and from the cloud, it is crucial to make the best use of the given resources of wide-area backbone networks (WANs). An intriguing approach to improve both efficiency and performance of WANs is to render networks more adaptive and "demand-aware", on the physical layer: innovative programmable wide-area topologies support dynamic wavelength assignments. This is enabled by the application of colorless and directionless Reconfigurable Optical Add/Drop Multiplexers (CD ROADM), and by leveraging the capabilities of software-defined controllers.

Since caches are shared and coherent, a memory access of one process may evict from the cache another process' memory block with an address mapped to the same cache line. This property is exploited by several attacks to form side channels. We show that MAC learning in Software Defined Networks (SDNs) has a similar property in the sense that a MAC address discovered by one network device may be revoked by the discovery of the same address at another switch. This allows us to implement Macchiato, a covert channel for SDNs between any two network devices (including hosts); prior SDN covert channels required at least one malicious switch. We evaluate a prototype implementation of Macchiato and discuss how methods to improve the performance of cache side channels (such as deep neural networks) can also be used in Macchiato.

Today's communication networks have stringent availability requirements and hence need to rapidly restore connectivity after failures. Modern networks thus implement various forms of fast reroute mechanisms in the data plane, to bridge the gap to slow global control plane convergence. State-of-the-art fast reroute commonly relies on disjoint route structures, to offer multiple independent paths to the destination.

In order to meet the increasingly stringent throughput and latency requirements in datacenter networks, several innovative network architectures based on reconfigurable optical topologies have been proposed. Examples include demand-oblivious reconfigurable topologies such as RotorNet (SIGCOMM 2017), Opera (NSDI 2020), and Sirius (SIGCOMM 2021), as well as demand-aware topologies such as ProjecToR (SIGCOMM 2016). All these architectures feature attractive performance properties using specific prototypes. However, reproducing these experiments is often difficult due to missing hardware and publicly available software. This paper presents a flexible framework for reconfigurable networks based on off-the-shelf hardware, which supports experimentation and reproducibility at a small scale. We describe how our framework, ExReC, can be instantiated with different configurations, allowing us to emulate existing architectures and to study their trade-offs. Finally, we demonstrate the application of our approach to different use cases and workloads, including distributed machine learning training.

High computational demands of complex deep learning models led to workload distribution across multiple machines. Many frameworks for distributed machine learning (DML) have been developed and are employed in practice for orchestrating workload distribution. In this paper, we analyze and compare network behaviors of three widely used state-of-the-art DML frameworks. The study reveals that traffic can largely vary across the frameworks. While some frameworks exhibit well predictable patterns, others are less structured. We further explore whether and how it is possible to relate the network traffic to the DML jobs' attributes, and present a multiple linear regression model accordingly. Our results can inform the networking community about traffic characteristics and contribute toward the generation of realistic DML traffic for simulation studies.

Providers today run numerous applications on their networks with diverse quality of service requirements. An appealing vision to deal with the resulting complexity of network operation, is to give more control to the network, allowing it to become more autonomous and to dynamically "self-adjust", to meet its requirements. This paper presents an architecture, ReactNet, to realize this vision, by leveraging two enabling technologies. First, we use programmable dataplanes and P4 to get accurate information about the traffic patterns the network currently serves. Second, we leverage Machine Learning (ML) techniques to process this information and react to the network changes dynamically.

Most ISPs use sophisticated traffic engineering strategies based on link weight optimizations to efficiently provision their backbone network and to serve intra-domain traffic. While traditionally, traffic is split among the shortest weighted paths using ECMP, recently, an additional dimension for optimization arose in the context of segment routing: traffic can be steered away from congested shortest paths by inserting intermediate destinations, so-called waypoints.

Path-aware networks (PANs) are emerging as an intriguing new paradigm with the potential to significantly improve the dependability and efficiency of networks. However, the benefits of PANs can only be realized if the adoption of such architectures is economically viable. This paper shows that PANs enable novel interconnection agreements among autonomous systems, which allow to considerably improve both economic profits and path diversity compared to today's Internet. Specifically, by supporting packet forwarding along a path selected by the packet source, PANs do not require the Gao-Rexford conditions to ensure stability. Hence, autonomous systems can establish novel agreements, creating new paths which demonstrably improve latency and bandwidth metrics in many cases. This paper also expounds two methods to set up agreements which are Pareto-optimal, fair, and thus attractive to both parties. We further present a bargaining mechanism that allows two parties to efficiently automate agreement negotiations.

To provide a high availability and to be able to quickly react to link failures, most communication networks feature fast rerouting (FRR) mechanisms in the data plane. However, configuring these mechanisms to provide a high resilience against multiple failures is algorithmically challenging, as rerouting rules can only depend on local failure information and need to be pre-defined. This paper is motivated by the observation that the common approach to design fast rerouting algorithms, based on spanning trees and covering arborescences, comes at a cost of reduced resilience as it does not fully exploit the available links in heterogeneous topologies. We present several novel fast rerouting algorithms which are not limited by spanning trees, but rather extend and combine ("graft") multiple spanning arborescences to improve resilience. We compare our algorithms analytically and empirically, and show that they can significantly improve not only the resilience, but also accelerate the preprocessing to generate the local fast failover rules.

Distributed applications generate a significant amount of network traffic. By collocating frequently communicating nodes (e.g., virtual machines) on the same clusters (e.g., server or rack), we can reduce the network load and improve application performance. However, the communication pattern of different applications is often unknown a priori and may change over time, hence it needs to be learned in an online manner. This paper revisits the online balanced partitioning problem that asks for an algorithm that strikes an optimal tradeoff between the benefits of collocation (i.e., lower network load) and its costs (i.e., migrations). Our first contribution is a significantly improved deterministic lower bound of Ω(k · ℓ) on the competitive ratio, where ℓ is the number of clusters and k is the cluster size, even for a scenario in which the communication pattern is static and can be perfectly partitioned; we also provide an asymptotically tight upper bound of O(k·ℓ) for this scenario. For k = 3, we contribute an asymptotically tight upper bound of Θ(ℓ) for the general model in which the communication pattern can change arbitrarily over time. We improve the result for k = 2 by providing a strictly 6-competitive upper bound for the general model.

We design, develop, and evaluate P6, an automated approach to (a) detect, (b) localize, and (c) patch software bugs in P4 programs. Bugs are reported via a violation of pre-specified expected behavior that is captured by P6. P6 is based on machine learning-guided fuzzing that tests P4 switch non-intrusively, i.e., without modifying the P4 program for detecting runtime bugs. This enables an automated and real-time localization and patching of bugs. We used a P6 prototype to detect and patch existing bugs in various publicly available P4 application programs deployed on two different switch platforms: behavioral model (bmv2) and Tofino. Our evaluation shows that P6 significantly outperforms bug detection baselines while generating fewer packets and patches bugs in large P4 programs such as switch.p4 without triggering any regressions.

This paper studies the design of demand-aware network topologies: networks that dynamically adapt themselves toward the demand they currently serve, in an online manner. While demand-aware networks may be significantly more efficient than demand-oblivious networks, frequent adjustments are still costly. Furthermore, a centralized controller of such networks may become a bottleneck.We present CBNet (Counting-Based self-adjusting Network), a demand-aware network that relies on a distributed control plane supporting concurrent adjustments, while significantly reducing the number of reconfigurations, compared to related work. CBNet comes with formal guarantees and is based on concepts of self-adjusting data structures. We evaluate CBNet analytically and empirically and we find that CBNet can effectively exploit locality structure in the traffic demand.

While operating communication networks adaptively may improve utilization and performance, frequent adjustments also introduce an algorithmic challenge: the re-optimization of traffic engineering solutions is time-consuming and may limit the granularity at which a network can be adjusted. This paper is motivated by question whether the reactivity of a network can be improved by re-optimizing solutions dynamically rather than from scratch, especially if inputs such as link weights do not change significantly. This paper explores to what extent dynamic algorithms can be used to speed up fundamental tasks in network operations. We specifically investigate optimizations related to traffic engineering (namely shortest paths and maximum flow computations), but also consider spanning tree and matching applications. While prior work on dynamic graph algorithms focusses on link insertions and deletions, we are interested in the practical problem of link weight changes. We revisit existing upper bounds in the weight-dynamic model, and present several novel lower bounds on the amortized runtime for recomputing solutions. In general, we find that the potential performance gains depend on the application, and there are also strict limitations on what can be achieved, even if link weights change only slightly.

This paper proposes a new approximation algorithm for the offline Virtual Network Embedding Problem (VNEP) with latency constraints. Our approximation algorithm Flex allows for (slight) violations of the latency constraints in order to greatly lower the runtime. It relies on a reduction to the Restricted Shortest Path Problem (RSP) and leverages a classic result by Goel et al. We complement our formal analysis with a simulation study demonstrating our algorithm's computational benefits. Our results generalize to any other additive edge metric, as e.g., hop count or even packet loss probability.

Payment channel networks are a promising approach to improve the scalability of cryptocurrencies: they allow to perform transactions in a peer-to-peer fashion, along multihop routes in the network, without requiring consensus on the blockchain. However, during the discovery of cost-efficient routes for the transaction, critical information may be revealed about the transacting entities. This paper initiates the study of privacy-preserving route discovery mechanisms for payment channel networks. In particular, we present LightPIR, an approach which allows a client to learn the shortest (or cheapest in terms of fees) path between two nodes without revealing any information about the endpoints of the transaction to the servers. The two main observations which allow for an efficient solution in LightPIR are that: (1) surprisingly, hub labelling algorithms - which were developed to preprocess “street network like” graphs so one can later efficiently compute shortest paths - also perform well for the graphs underlying payment channel networks, and that (2) hub labelling algorithms can be conveniently combined with private information retrieval. LightPIR relies on a simple hub labeling heuristic on top of existing hub labeling algorithms which leverages the specific topological features of cryptocurrency networks to further minimize storage and bandwidth overheads. In a case study considering the Lightning network, we show that our approach is an order of magnitude more efficient compared to a privacy-preserving baseline based on using private information retrieval on a database that stores all pairs shortest paths.

We consider the following online optimization problem. We are given a graph G and each vertex of the graph is assigned to one of ℓ servers, where servers have capacity k and we assume that the graph has ℓ · k vertices. Initially, G does not contain any edges and then the edges of G are revealed one-by-one. The goal is to design an online algorithm ONL, which always places the connected components induced by the revealed edges on the same server and never exceeds the server capacities by more than ∊k for constant ∊ > 0. Whenever ONL learns about a new edge, the algorithm is allowed to move vertices from one server to another. Its objective is to minimize the number of vertex moves. More specifically, ONL should minimize the competitive ratio: the total cost ONL incurs compared to an optimal offline algorithm OPT. The problem was recently introduced by Henzinger et al. (SIGMETRICS'2019) and is related to classic online problems such as online paging and scheduling. It finds applications in the context of resource allocation in the cloud and for optimizing distributed data structures such as union–find data structures. Our main contribution is a polynomial-time randomized algorithm, that is asymptotically optimal: we derive an upper bound of O(log ℓ + log k) on its competitive ratio and show that no randomized online algorithm can achieve a competitive ratio of less than Ω(log ℓ + log k). We also settle the open problem of the achievable competitive ratio by deterministic online algorithms, by deriving a competitive ratio of Θ(ℓ log k); to this end, we present an improved lower bound as well as a deterministic polynomial-time online algorithm. Our algorithms rely on a novel technique which combines efficient integer programming with a combinatorial approach for maintaining ILP solutions. More precisely, we use an ILP to assign the connected components induced by the revealed edges to the servers; this is similar to existing approximation schemes for scheduling algorithms. However, we cannot obtain our competitive ratios if we run the ILP after each edge insertion. Instead, we identify certain types of edge insertions, after which we can manually obtain an optimal ILP solution at zero cost without resolving the ILP. We believe this technique is of independent interest and will find further applications in the future.

Self-adjusting networks (SANs) utilize novel optical switching technologies to support dynamic physical network topology reconfiguration. SANs rely on online algorithms to exploit this topological flexibility to reduce the cost of serving network traffic, leveraging locality in the demand. Models in prior work assign uniform cost for traversing and adjusting a single link (e.g. both cost 1). In this paper, we initiate the study of online algorithms for SANs in a more realistic cost model, the Matching Model (MM), in which the network topology is given by the union of a constant number of bipartite matchings (realized by optical switches), and in which changing an entire matching incurs a fixed cost a. The cost of routing is given by the number of hops packets need to traverse. We present online SAN algorithms in the MM with cost O(√α) times the cost of reference algorithms in the uniform cost model.

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.

Reconfigurable optical topologies are emerging as a promising technology to improve the efficiency of datacenter networks. This paper considers the problem of scheduling opportunistic links in reconfigurable datacenters such as ProjecToR. We study the online setting and aim to minimize flow completion times. The problem is a two-tier generalization of classic switch scheduling problems. We present a stable-matching algorithm which is O(ε^-2 )-competitive against an optimal offline algorithm, in a resource augmentation model: the online algorithm runs 2+ε times faster. Our algorithm and result are fairly general and allow for different link delays and also apply to hybrid topologies which combine fixed and reconfigurable links. Our analysis is based on LP relaxation and dual fitting.

Abstract To ensure a high availability, communication networks provide resilient routing mechanisms that quickly change routes upon failures. However, a fundamental algorithmic question underlying such mechanisms is hardly understood: how to verify whether a given network reroutes flows alongfeasiblepaths, without violating capacity constraints, for up toklink failures? We chart the algorithmic complexity landscape of resilient routing under link failures, considering shortest path routing based on link weights as e.g. deployed in the ECMP protocol. We study two models: apessimisticmodel where flows interfere in a worst-case manner along equal-cost shortest paths, and anoptimisticmodel where flows are routed in a best-case manner, and we present a complete picture of the algorithmic complexities. We further propose a strategic search algorithm that checks only the critical failure scenarios while still providing correctness guarantees. Our experimental evaluation on a benchmark of Internet and datacenter topologies confirms an improved performance of our strategic search by several orders of magnitude.

To ensure high availability, datacenter networks must rely on local fast rerouting mechanisms that allow routers to quickly react to link failures, in a fully decentralized manner. However, configuring these mechanisms to provide a high resilience against multiple failures while avoiding congestion along failover routes is algorithmically challenging, as the rerouting rules can only depend on local failure information and must be defined ahead of time. This paper presents a randomized local fast rerouting algorithm for Clos networks, the predominant datacenter topologies. Given a graph $G=(V,E)$ describing a Clos topology, our algorithm defines local routing rules for each node $v\in V$, which only depend on the packet's destination and are conditioned on the incident link failures. We prove that as long as number of failures at each node does not exceed a certain bound, our algorithm achieves an asymptotically minimal congestion up to polyloglog factors along failover paths. Our lower bounds are developed under some natural routing assumptions.

We show that any algorithm that solves the sinkless orientation problem in the supported LOCAL model requires Ω(log n) rounds, and this is tight. The supported LOCAL is at least as strong as the usual LOCAL model, and as a corollary this also gives a new, short and elementary proof that shows that the round complexity of the sinkless orientation problem in the deterministic LOCAL model is Ω(log n).

The performance of more and more cloud-based applications critically depends on the performance of the interconnecting datacenter network. Emerging reconfigurable datacenter networks have the potential to provide an unprecedented throughput by dynamically reconfiguring their topology in a demand-aware manner. This paper studies the algorithmic problem of how to design low-degree and hence scalable datacenter networks that are optimized toward the current traffic they serve. Our main contribution is a novel network design which provides asymptotically minimal route lengths and congestion. In comparison to prior work, our design reduces the degree requirements by a factor of four for sparse demand matrices. We further show that the problem is already NP-hard for tree-shaped demands, but permits a 2-approximation on the route lengths and a 6-approximation for congestion. We further report on a small empirical study on Facebook traces.

In various contexts of networking research, end-host path selection has recently regained momentum as a design principle. While such path selection has the potential to increase performance and security of networks, there is a prominent concern that it could also lead to network instability (i.e., flow-volume oscillation) if paths are selected in a greedy, load-adaptive fashion. However, the extent and the impact vectors of instability caused by path selection are rarely concretized or quantified, which is essential to discuss the merits and drawbacks of end-host path selection. In this work, we investigate the effect of end-host path selection on various metrics of networks both qualitatively and quantitatively. To achieve general and fundamental insights, we leverage the recently introduced axiomatic perspective on congestion control and adapt it to accommodate joint algorithms for path selection and congestion control, i.e., multi-path congestion-control protocols. Using this approach, we identify equilibria of the multi-path congestion-control dynamics and analytically characterize these equilibria with respect to important metrics of interest in networks (the “axioms”) such as efficiency, fairness, and loss avoidance. Moreover, we analyze how these axiomatic ratings for a general network change compared to a scenario without path selection, thereby obtaining an interpretable and quantitative formalization of the performance impact of end-host path-selection. Finally, we show that there is a fundamental trade-off in multi-path congestion-control protocol design between efficiency, stability, and loss avoidance on one side and fairness and responsiveness on the other side.

In network optimization problems, from traffic engineering to network monitoring, the routing model is typically considered as something given and frozen. This paper is motivated by the fundamental question how the ability tochangeandoptimizethe routing model itself influences the efficiency at which communication networks can be operated. To this end, we identify two main dimensions of a routing model:consistency(of a single route) andcoherence(of sets of routes). We present analytical results on the impact of the routing model on the achievable route diversity as well as on the runtime of solving optimization problems underlying different case studies. We also uncover that it can sometimes be beneficial toartificiallyrestrict the routing model, to significantly reduce the computational complexity without negatively affecting the route diversity much.

Highly dependable communication networks usually rely on some kind of Fast Re-Route (FRR) mechanism which allows to quickly re-route traffic upon failures, entirely in the data plane. This paper studies the design of FRR mechanisms for emerging reconfigurable switches. Our main contribution is an FRR primitive for programmable data planes, PURR, which provides low failover latency and high switch throughput, by avoiding packet recirculation. PURR tolerates multiple concurrent failures and comes with minimal memory requirements, ensuring compact forwarding tables, by unveiling an intriguing connection to classic “string theory” (i.e., stringology), and in particular, the shortest common supersequence problem. PURR is well-suited for high-speed match-action forwarding architectures (e.g., PISA) and supports the implementation of a broad variety of FRR mechanisms. Our simulations and prototype implementation (on an FPGA and a Tofino switch) show that PURR improves TCAM memory occupancy by a factor of 1.5 ×- 10.8 × compared to a naïve encoding when implementing state-of-the-art FRR mechanisms. PURR also improves the latency and throughput of datacenter traffic up to a factor of 2.8 ×- 5.5 × and 1.2 ×- 2 ×, respectively, compared to approaches based on recirculating packets.

Private networks are typically assumed to be trusted as security mechanisms are usually deployed on hosts and the data plane is managed in-house. The increasing number of attacks on network devices, and recent reports on backdoors, forces us to revisit existing security assumptions and demands new approaches to detect malicious activity. This paper presents Preacher, a runtime network policy checker, which leverages a secure, redundant and adaptive sample distribution scheme that allows us to provably detect and localize adversarial switches or routers trying to reroute, mirror, drop, inject, or modify packets (i.e., header and/or payload) even under collusion. The analysis performed by Preacher is highly parallelizable. We show that emerging programmable networks provide an ideal vehicle to detect suspicious network activity. Furthermore, we analytically and empirically evaluate the effectiveness of our approach in different adversarial settings, report on a proof-of-concept implementation using ONOS, and provide insights into the resource and performance overheads of Preacher.

Cryptocurrencies such as Bitcoin are realized using distributed systems and hence critically rely on the performance and security of the interconnecting network. The requirements on these networks and their usage, however can differ significantly from traditional communication networks, with implications on all layers of the protocol stack. This paper is motivated by these differences, and in particular by the observation that many fundamental design aspects of these networks are not well-understood today. In order to support the networking community to contribute to this emerging application domain, we present a structured overview of the field, from topology and neighbor discovery to block and transaction propagation. In particular, we provide the context, highlighting differences and commonalities with traditional networks, review the state-of-the-art, and identify open research challenges. Our paper can hence also be seen as a call-to-arms to improve the foundation on top of which cryptocurrencies are built.

Off-chain transaction networks can mitigate the scalability issues of today's trustless blockchain systems such as Bitcoin. However, these peer-to-peer networks also introduce a new attack surface which is not yet fully understood. This paper identifies and analyzes a novel type of Denial-of-Service attack which is based on attracting routes, i.e., which exploits the way transactions are routed and executed along the channels of the network in order to attract nodes to route through the attacker. This attack is conceptually interesting as it highlights a fundamental design tradeoff for the defender (who determines its own routes): to become less susceptible to hijacking, a rational node has to pay higher fees to nodes that forward its payments.

This paper presents Chameleon, a cloud network providing both predictable latency and high utilization, typically two conflicting goals, especially in multi-tenant datacenters. Chameleon exploits routing flexibilities available in modern communication networks to dynamically adapt toward the demand, and uses network calculus principles along individual paths. More specifically, Chameleon employs source routing on the "queue-level topology", a network abstraction that accounts for the current states of the network queues and, hence, the different delays of different paths. Chameleon is based on a simple greedy algorithm and can be deployed at the edge; it does not require any modifications of network devices. We implement and evaluate Chameleon in simulations and a real testbed. Compared to state-of-the-art, we find that Chameleon can admit and embed significantly, i.e., up to 15 times more flows, improving network utilization while meeting strict latency guarantees.

We present an automated what-if analysis tool AalWiNes for MPLS networks which allows us to verify both logical properties (e.g., related to the policy compliance) as well as quantitative properties (e.g., concerning the latency) under multiple link failures. Our tool relies on weighted pushdown automata, a quantitative extension of classic automata theory, and takes into account the actual dataplane configuration, rendering it especially useful for debugging. In particular, our tool collects the different router forwarding tables and then builds a pushdown system, on which quantitative reachability is performed based on an expressive query language. Our experiments show that our tool outperforms state-of-the-art approaches (which until now have been restricted to logical properties) by several orders of magnitude; furthermore, our quantitative extension only entails a moderate overhead in terms of runtime. The tool comes with a platform-independent user interface and is publicly available as open-source, together with all other experimental artefacts.

Cryptocurrency off-chain networks such as Lightning (e.g., Bitcoin) or Raiden (e.g., Ethereum) aim to increase the scalability of traditional on-chain transactions. To support nodes in learning about possible paths to route their transactions, these networks need to provide gossip and probing mechanisms. This paper explores whether these mechanisms may be exploited to infer sensitive information about the flow of transactions, and eventually harm privacy. In particular, we identify two threats, related to an active and a passive adversary. The first is a probing attack: here the adversary aims to detect the maximum amount which is transferable in a given direction over a target channel by actively probing it and differentiating the response messages it receives. The second is a timing attack: the adversary discovers how close the destination of a routed payment actually is, by acting as a passive man-in-the middle and analyzing the time deltas between sent messages and their corresponding responses. We then analyze the limitations of these attacks and propose remediations for scenarios in which they are able to produce accurate results.

This paper explores the design of dynamic network topologies which adjust to the workload they serve, in a demand-aware and online manner. Such self-adjusting networks (SANs) are enabled by emerging optical technologies, and can be found, e.g., in datacenters. SANs can be used to reduce routing costs by moving frequently communicating nodes topologically closer. However, such reconfigurations also come at a cost, introducing a need for online algorithms which strike an optimal balance between the benefits and costs of reconfigurations.This paper presents SANs which provide, for the first time, provable working set guarantees: the routing cost between node pairs is proportional to how recently these nodes communicated last time. Our SANs rely on a distributed implementation of skip lists (which serves as the topology) and provide additional interesting properties such as local routing. Our first contribution is SASL2, which is a randomized and sequential SAN algorithm that achieves the working set property. Then we show how SASL2can be converted to a distributed algorithm that handles concurrent communication requests and maintains SASL2's properties. Finally, we present deterministic SAN algorithms.

Many modern cloud applications frequently generate multicast traffic, which is becoming one of the primary communication patterns in datacenters. Emerging reconfigurable datacenter technologies enable interesting new opportunities to support such multicast traffic in the physical layer: novel circuit switches offer high-performance inter-rack multicast capabilities. However, not much is known today about the algorithmic challenges introduced by this new technology.This paper presents SplitCast, a preemptive multicast scheduling approach that fully exploits emerging physical-layer multicast capabilities to reduce flow times. SplitCast dynamically reconfigures the circuit switches to adapt to the multicast traffic, accounting for reconfiguration delays. In particular, SplitCast relies on simple single-hop routing and leverages flexibilities by supporting splittable multicast so that a transfer can already be delivered to just a subset of receivers when the circuit capacity is insufficient. Our evaluation results show that SplitCast can reduce flow times significantly compared to state-of-the-art solutions.

Modern communication networks support fast path restoration mechanisms which allow to reroute traffic in case of (possibly multiple) link failures, in a completely decentralized manner and without requiring global route reconvergence. However, devising resilient path restoration algorithms is challenging as these algorithms need to be inherently local. Furthermore, the resulting failover paths often have to fulfill additional requirements related to the policy and function implemented by the network, such as the traversal of certain waypoints (e.g., a firewall). This paper presents local algorithms which ensure a maximally resilient path restoration for a large family of product graphs, including the widely used tori and generalized hypercube topologies. Our algorithms provably ensure that even under multiple link failures, traffic is rerouted to the other endpoint of every failed link whenever possible (i.e. detouring failed links), enforcing waypoints and hence accounting for the network policy. The algorithms are particularly well-suited for emerging segment routing networks based on label stacks.

Distributed applications, including batch processing, streaming, scale-out databases, or machine learning, generate a significant amount of network traffic. By collocating frequently communicating nodes (e.g., virtual machines) on the same clusters (e.g., server or rack), we can reduce the network load and improve application performance. However, the communication pattern of different applications is often unknown a priori and may change over time, hence it needs to be learned in an online manner. This paper revisits the online balanced partitioning problem (introduced by Avin et al. at DISC 2016) that asks for an algorithm that strikes an optimal tradeoff between the benefits of collocation (i.e., lower network load) and its costs (i.e., migrations). Our first contribution is a significantly improved deterministic lower bound of Ω(k · ℓ) on the competitive ratio, where ℓ is the number of clusters and k is the cluster size, even for a scenario in which the communication pattern is static and can be perfectly partitioned; we also provide an asymptotically tight upper bound of O(k · ℓ) for this scenario. For k = 3, we contribute an asymptotically tight upper bound of Θ(ℓ) for the general model in which the communication pattern can change arbitrarily over time. In contrast to most prior work, our algorithms respect all capacity constraints and do not require resource augmentation.

In order to provide a high resilience and to react quickly to link failures, modern computer networks support fully decentralized flow rerouting, also known as local fast failover. In a nutshell, the task of a local fast failover algorithm is to pre-define fast failover rules for each node using locally available information only. Ideally, such a local fast failover algorithm provides a perfect resilience deterministically: a packet emitted from any source can reach any target, as long as the underlying network remains connected. Feigenbaum et al. showed [Feigenbaum and others, 2012] that it is not always possible to provide perfect resilience; on the positive side, the authors also presented an efficient algorithm which achieves at least 1-resilience, tolerating a single failure in any network. Interestingly, not much more is known currently about the feasibility of perfect resilience. This brief announcement revisits perfect resilience with local fast failover, both in a model where the source can and cannot be used for forwarding decisions. By establishing a connection between graph minors and resilience, we prove that it is impossible to achieve perfect resilience on any non-planar graph; On the positive side, we can derive perfect resilience for outerplanar and some planar graphs.

Abstract We initiate the study of a fundamental combinatorial problem: Given a capacitated graph $$G=(V,E)$$ G=(V,E) , find a shortest walk (“route”) from a source $${s\in V}$$ s∈V to a destination $$t\in V$$ t∈V that includes all vertices specified by a set $$WP \subseteq V$$ WP⊆V : the waypoints. This Waypoint Routing Problem finds immediate applications in the context of modern networked systems. Our main contribution is an exact polynomial-time algorithm for graphs of bounded treewidth. We also show that if the number of waypoints is logarithmically bounded, exact polynomial-time algorithms exist even for general graphs. Our two algorithms provide an almost complete characterization of what can be solved exactly in polynomial time: we show that more general problems (e.g., on grid graphs of maximum degree 3, with slightly more waypoints) are computationally intractable.

More and more networks are becoming reconfigurable: not just the routing can be programmed, but the physical layer itself as well. Various technologies enable this programmability, ranging from optical circuit switches to beamformed wireless connections and free-space optical interconnects. Existing reconfigurable network topologies are typically hybrid in nature, consisting of static and a reconfigurable links. However, even though the static and reconfigurable links form a joint structure, routing policies are artificially segregated and hence do not fully exploit the network resources: the state of the art is to route large elephant flows on direct reconfigurable links, whereas the remaining traffic is left to the static network topology. Recent work showed that such artificial segregation is inefficient, but did not provide the tools to actually leverage the benefits on non-segregated routing. In this paper, we provide several algorithms which take advantage of non-segregated routing, by jointly optimizing topology and routing. We compare our algorithms to segregated routing policies and also evaluate their performance in workload-driven simulations, based on real-world traffic traces. We find that our algorithms do not only outperform segregated routing policies, in various settings, but also come close to the optimal solution, computed by a integer linear program formulation, also presented in this paper. Finally, we also provide insights into the complexity of the underlying combinatorial optimization problem, by deriving approximation hardness results.

In manySoftware-Defined Networking(SDN) deployments the control plane ends up beingactuallycentralized, yielding a single point of failure and attack. This paper models the interaction between the data plane and adistributedcontrol plane consisting of a set of failure-prone and potentially malicious (compromised) control devices, and implements a secure and robust controller platform that allows network administrators to integrate new network functionality as with a centralized approach. Concretely, the network administrator may program the data plane from the perspective of a centralized controller without worrying about distribution, asynchrony, failures, attacks, or coordination problems that any of these could cause. We introduce a formal SDN computation model for applying network policies and show that it isimpossibleto implementasynchronous non-blockingand strongly consistent SDN controller platforms in that model. We then present arobustSDNcontroller protocol (RoSCo) which implements (i) a protocol with provablylinearizable semanticsfor applying network policies that is resilient against faulty/malicious control devices as long as acorrect majorityexists, and (ii) a modification to the protocol that improves performance by relaxing the guarantees of linearizability to exploit commutativity among updates. Extensive experiments conducted with a functional prototype of RoSCo over a large networked infrastructure supporting Open vSwitch (OVS)-compatible Agilio CX™ SmartNIC hardware show that RoSCo induces bearable overhead. In fact, RoSCo achieves higher throughput in most cases investigated than the seminal Ravana platform which addresses only benign (crash) failures.

The increasing amount of data replication across datacenters introduces a need for efficient bulk data transfer protocols which provide certain guarantees, most notably timely transfer completion. We present DaRTree which leverages emerging optical reconfiguration technologies, to jointly optimize topology and multicast transfers in software-defined optical Wide-Area Networks (WANs), and thereby maximize throughput and acceptance ratio of transfer requests subject to transfer deadlines. DaRTree is based on a novel integer linear program relaxation and deterministic rounding scheme. To this end, DaRTree uses Steiner trees for forwarding and adaptive routing based on the current network load. DaRTree provides transfer completion guarantees without the need for rescheduling or preemption. Our evaluations show that DaRTree increases the network throughput and the number of accepted requests by up to 1.7×, especially for larger WANs. Moreover, DaRTree even outperforms state-of-the-art solutions when the traffic demands are only unicast transfers or when the WAN topology cannot be reconfigured. While DaRTree determines the rate and route to serve a request at the time of (online) admission control, we show that the acceptance ratio and throughput can be improved by up to 1.3× even further when DaRTree updates the rate and route of admitted transfers also at runtime.

The prevailing wisdom is that a software-defined network (SDN) operates under the premise that the logically centralized control plane has an accurate representation of the actual data plane state. Unfortunately, bugs, misconfigurations, faults or attacks can introduce inconsistencies between the network control and the data plane that can undermine the correct operation at runtime. Through our experiments, we realize that P4 SDNs are no exception, and are prone to similar problems. With the aim to verify the control-data plane inconsistency, we present the design and implementation of P4Consist, a system to detect the inconsistency between control and data plane in P4 SDNs. P4Consist generates active probe-based traffic continuously or periodically as an input to the P4 SDNs to check whether the actual behavior on the data plane corresponds to the expected control plane behavior. In P4Consist, the control plane and the data plane generate independent reports which are later, compared to verify the control-data plane consistency. The previous works in the field of monitoring and verification mostly aim to test the P4 programs through static analysis and thus, are insufficient to verify the network consistency at runtime. Experiments with our prototype implementation of P4Consist are promising and show that P4Consist can verify the control-data plane consistency in the complex datacenter 4-ary fat-tree (20 switches) and multipath grid (4, 9 and 16 switches) topologies with 60k rules per switch within a minimum time of 4 minutes. At the same time, P4Consist scales to multiple source-destination pairs to detect control-data plane inconsistency.

A key trend of current network evolution is in the direction of network softwarization and virtualization. These technological paradigms aim to enable a network to be programmable in a way that makes the network more flexible, scalable, and reliable, and in turn leads to agile service deployment and lower capital and operational expenses. So far, two related widely adopted solutions are software defined networks (SDN) and network function virtualization (NFV). There is one main difference between these two new networking paradigms. SDN separates the control plane from the data plane through a well-defined programming interface, such that the centralized controller can have a complete view of the entire network, while NFV decouples network functions from dedicated physical equipment by means of virtualization technology, and runs the virtual network functions (VNFs) in the general purpose physical or virtual network appliances. Both approaches make the network programmable in order to have the aforementioned desired features. SDN and NFV do not depend on each other, and they actually complement each other. They can work well individually and can also work in tandem for performance reasons. Due to such advantages, both SDN and NFV have become key enabling technologies for 5G networks, and have also been used in a wide range of important areas including IoT, mobile edge computing, smart grid, cloud datacenters, and cognition-based networks.

By delegating path control to end-hosts, future Internet architectures offer flexibility for path selection. However, a concern arises that the distributed routing decisions by endhosts, in particular load-adaptive routing, can lead to oscillations if path selection is performed without coordination or accurate load information. Prior research has addressed this problem by devising local path-selection policies that lead to global stability. However, little is known about the viability of these policies in the Internet context, where selfish end-hosts can deviate from a prescribed policy if such a deviation is beneficial from their individual perspective. In order to achieve network stability in future Internet architectures, it is essential that end-hosts have an incentive to adopt a stability-oriented path-selection policy. In this work, we perform the first incentive analysis of the stability-inducing path-selection policies proposed in the literature. Building on a game-theoretic model of end-host path selection, we show that these policies are in fact incompatible with the self-interest of end-hosts, as these strategies make it worthwhile to pursue an oscillatory path-selection strategy. Therefore, stability in networks with selfish endhosts must be enforced by incentive-compatible mechanisms. We present two such mechanisms and formally prove their incentive compatibility.

This paper initiates the study of the classic balanced graph partitioning problem from an online perspective: Given an arbitrary sequence of pairwise communication requests between $n$ nodes, with patterns that may change over time, the objective is to service these requests efficiently by partitioning the nodes into $L$ clusters, each of size $k$, such that frequently communicating nodes are located in the same cluster. The partitioning can be updated dynamically by migrating nodes between clusters. The goal is to devise online algorithms which jointly minimize the amount of intercluster communication and migration cost. The problem features interesting connections to other well-known online problems. For example, scenarios with $L = 2$ generalize online paging, and scenarios with $k = 2$ constitute a novel online variant of maximum matching. We present several lower bounds and algorithms for settings both with and without cluster-size augmentation. In particular, we prove that any deterministic online algorithm has a competitive ratio of at least $k$, even with significant augmentation. Our main algorithmic contributions are an $O(k \log k)$-competitive deterministic algorithm for the general setting with constant augmentation and a constant competitive algorithm for the maximum matching variant.

The conventional wisdom is that a software-defined network (SDN) operates under the premise that the logically centralized control plane has an accurate representation of the actual data plane state. Unfortunately, bugs, misconfigurations, faults or attacks can introduce inconsistencies that undermine correct operation. Previous work in this area, however, lacks a holistic methodology to tackle this problem and thus, addresses only certain parts of the problem. Yet, the consistency of the overall system is only as good as its least consistent part. Motivated by an analogy of network consistency checking with program testing, we propose to add active probe-based network state fuzzing to our consistency check repertoire. Hereby, our system, Pazz, combines production traffic with active probes to periodically test if the actual forwarding path and decision elements (on the data plane) correspond to the expected ones (on the control plane). Our insight is that active traffic covers the inconsistency cases beyond the ones identified by passive traffic. Pazz prototype was built and evaluated on topologies of varying scale and complexity. Our results show that Pazz requires minimal network resources to detect persistent data plane faults through fuzzing and localize them quickly while outperforming baseline approaches.

Many resource allocation problems in the cloud can be described as a basic Virtual Network Embedding Problem (VNEP): the problem of finding a mapping of a request graph (describing a workload) onto a substrate graph (describing the physical infrastructure). Applications range from mapping testbeds, over the embedding of batch-processing tasks to the embedding of service function chains and come with different mapping restrictions for nodes and edges. The restrictions studied most often are node and edge capacities, node mapping, edge routing and latency restrictions. While the VNEP has been studied intensively, complexity results are only known for specific models and this paper provides a first comprehensive study of the computational complexity of the VNEP by systematically analyzing its hardness for any combination of the above stated mapping restrictions. For all studied variants the NP-completeness of the respective decision problems is shown. Furthermore, NP-completeness results for finding approximate embeddings, which may, e.g., violate capacity constraints by certain factors, are derived. Lastly, it is also shown that all these results pertain when restricting the request graphs to planar and degree-bounded graphs. While theoretic in nature, our results have severe practical implications. Firstly, any optimization variant of the VNEP is NP-hard and cannot be approximated for any of the studied restrictions, unless P = NP. Secondly, we uncover structural hardness properties: the VNEP is NP-hard and inapproximable even if, e.g., only node placement and edge routing restrictions are considered.

To meet their increasingly stringent dependability requirements, communication networks need to be predictable, both in terms of correctness and performance. In principle, Software-Defined Networks (SDN) enable such more predictable networks, however, these networks still depend the underlying switches. This paper presents an empirical study of the predictability of SDN switches. Our extensive benchmarking of seven hardware OpenFlow switches from four different manufacturers raises several concerns regarding the dependability of these switches. We uncover several incorrect and unpredictable behaviors and performance issues. In particular, we identify unpredictable behaviors related to the management of flows and buffers, and observe that existing quality-of-service mechanisms, such as priority queuing, introduce unexpected overheads. The latter, in turn, can lead to violations of latency guarantees. Based on our insights, we discuss first solutions toward more predictable architectures.

A predictable network performance is mission critical for many applications and yet hard to provide due to difficulties in modeling the behavior of the increasingly complex network equipment. This paper studies the problem of providing deterministic latency guarantees in small networks based on low-capacity hardware (e.g., in-cabin and industrial networks): such networks are of increasing importance, need to meet stringent performance requirements, but have hardly been explored so far. Our main contribution is the design, implementation, and evaluation of Loko, a system which provides predictable latency guarantees in programmable networks using low-cost hardware. Loko relies on a novel measurement-based methodology and uses deterministic network calculus to derive a reliable performance model of a given switch. To this end, we also show that state-of-the-art models in the literature like QJump and Silo fall short to model the behavior of such switches, due to incorrect architectural and performance assumptions. As a case study, we implement Loko for the Zodiac FX switch. Our experiments are encouraging: we find that the derived models are indeed accurate, allowing Loko to provide deterministic end-to-end guarantees with low-cost programmable devices.

Highly dependable communication networks usually rely on some kind of Fast Re-Route (FRR) mechanism which allows to quickly re-route traffic upon failures, entirely in the data plane. This paper studies the design of FRR mechanisms for emerging reconfigurable switches.

Efficient and highly available packet classification is fundamental for various security primitives. In this paper, we evaluate whether the de facto Tuple Space Search (TSS) packet classification algorithm used in popular software networking stacks such as the Open vSwitch is robust against low-rate denial-of-service attacks. We present the Tuple Space Explosion (TSE) attack that exploits the fundamental space/time complexity of the TSS algorithm.

To provide high availability despite link failures, many modern communication networks feature fast failover mechanisms in the data plane, which operates orders of magnitude faster than the control plane. While the configuration of highly resilient data planes is known to be a difficult combinatorial problem, over the last years, much progress has been made in the design of algorithms which provably guarantee connectivity even under many concurrent link failures. However, while these algorithms provide connectivity, the resulting routes after failures can be very long, which in turn can harm performance. In this paper, we propose, analyze, and evaluate methods for fast failover algorithms which account for the quality of the routes after failures, in addition to connectivity. In particular, we revisit the existing approach to cover the to-be-protected network with arc-disjoint spanning arborescences to define alternative routes to the destination, aiming to keep the stretch imposed by these trees low (hence the name of our method: Bonsai). We show that the underlying problem is NP-hard on general topologies and present lower bound results that are tight for various topologies, for any class of fast failover algorithms. We also present heuristics for general networks and demonstrate their performance benefits in extensive simulations. Finally, we show that failover algorithms using low-stretch arborescences, as a side effect, can provide connectivity under more general failure models than usually considered in the literature.

Oblivious routing is an attractive paradigm for large distributed systems in which centralized control and frequent reconfigurations are infeasible or undesired (e.g., costly). Over the last almost 20 years, much progress has been made in devising oblivious routing schemes that guarantee close to optimal load and also algorithms for constructing such schemes efficiently have been designed. However, a common drawback of existing oblivious routing schemes is that they are not compact: they require large routing tables (of polynomial size), which does not scale. This paper presents the first oblivious routing scheme which guarantees close to optimal load and is compact at the same time - requiring routing tables of polylogarithmic size. Our algorithm maintains the polylogarithmic competitive ratio of existing algorithms, and is hence particularly well-suited for emerging large-scale networks.

Most modern communication networks include fast rerouting mechanisms, implemented entirely in the data plane, to quickly recover connectivity after link failures. By relying on local failure information only, these data plane mechanisms provide very fast reaction times, but at the same time introduce an algorithmic challenge in case of multiple link failures: failover routes need to be robust to additional but locally unknown failures downstream. This paper presents local fast rerouting algorithms which not only provide a high degree of resilience against multiple link failures, but also ensure a low congestion on the resulting failover paths. We consider a randomized approach and focus on networks which are highly connected before the failures occur. Our main contribution are three simple algorithms which come with provable guarantees and provide interesting resilience-load tradeoffs, significantly outperforming any deterministic fast rerouting algorithm with high probability.

Emerging communication technologies allow to reconfigure the physical network topology at runtime, enabling demand-aware networks (DANs): networks whose topology is optimized toward the workload they serve. However, today, only little is known about the fundamental algorithmic problems underlying the design of such demand-aware networks. This paper presents the first bounded-degree, demand-aware network, ct-DAN, which minimizes both congestion and route lengths. The designed network is provably (asymptotically) optimal in each dimension individually: we show that there do not exist any bounded-degree networks providing shorter routes (independently of the load), nor do there exist networks providing lower loads (independently of the route lengths). The main building block of the designed ct-DAN networks are ego-trees: communication sources arrange their communication partners in an optimal tree, individually. While the union of these ego-trees forms the basic structure of cl-DANs, further techniques are presented to ensure bounded degrees (for scalability).

As communication networks are growing at a fast pace, the need for more scalable approaches to operate such networks is pressing. Decentralization and locality are key concepts to provide scalability. Existing models for which local algorithms are designed fail to model an important aspect of many modern communication networks such as software-defined networks: the possibility to precompute distributed network state. We take this as an opportunity to study the fundamental question of how and to what extent local algorithms can benefit from preprocessing. In particular, we show that preprocessing allows for significant speedups of various networking problems. A main benefit is the precomputation of structural primitives, where purely distributed algorithms have to start from scratch. Maybe surprisingly, we also show that there are strict limitations on how much preprocessing can help in different scenarios. To this end, we provide approximation bounds for the maximum independent set problem-which however show that our obtained speedups are asymptotically optimal. Even though we show that physical link failures in general hinder the power of preprocessing, we can still facilitate the precomputation of symmetry breaking processes to bypass various runtime barriers. We believe that our model and results are of interest beyond the scope of this paper and apply to other dynamic networks as well.

To meet the stringent requirements on the maximally tolerable disruptions of traffic under link failures, many communication networks feature some sort of static failover mechanism for fast rerouting. However, configuring such static failover mechanisms to achieve a high degree of robustness is known to be challenging, in particular when packet tagging or dynamic node state cannot be used. This paper initiates the systematic study of such local fast failover mechanisms which not only provide connectivity guarantees, even under multiple link failures, but also account for the quality of the resulting failover routes, with respect to locality (i.e., route length) and congestion. Failover quality has received less attention in the literature so far, yet it is increasingly important to support emerging applications.We first show that there exists an inherent tradeoff in terms of achievable locality and congestion of failover routes. We then present CASA, an algorithm providing a high degree of robustness as well as a provable quality of fast rerouting. CASA combines two crucial static resilient routing techniques: combinatorial designs and arc-disjoint arborescences. We complement our formal analysis with a simulation study, in which we compare our algorithms with the state-of-the-art in different scenarios and show benefits in terms of stretch, load, and resilience.

This paper considers the following fundamental maximum throughput routing problem: given a set of k (splittable) multicommodity flows with equal demands in an n-node network, select and route a subset of flows such that the total number of commodities routed that satisfy their demands (i.e., the allor-nothing throughput) is maximized. Our main contribution is the first constant (i.e., independent of k and n) through-putapproximation algorithm for this NP-hard problem, with sublin-ear, namely Õ(√k), edge capacity violation ratio. Our algorithm is based on a clever application of randomized rounding. We also present an interesting application of our result in the context of delay-tolerant network scheduling. We complement our theoretical contribution with extensive simulation in two different scenarios, and find that our algorithm performs significantly better than predicted in theory, achieving an edge capacity violation ratio of at most 3.

We consider the problem of designing dynamic network topologies that self-adjust to the (possibly changing) traffic pattern they serve. Such demand-aware networks currently receive much attention, especially in the context of datacenters, due to emerging technologies supporting the fast reconfiguration of the physical topology. We present the first fully distributed, provably efficient self-adjusting network. Our network called DiSptayNet relies on algorithms that perform decentralized and concurrent topological adjustments to account for changes in the demand. We present a rigorous formal analysis of the correctness and performance of DiSptayNet, which can be seen as an interesting generalization of analyses known from sequential self-adjusting datastructures. We also report on results from extensive trace-driven simulations.

The increasing amount of data replication across datacenters introduces a need for efficient bulk data transfer protocols which meet QoS guarantees, notably timely completion. We present DaRTree which leverages emerging optical reconfiguration technologies, to jointly optimize topology and multicast transfers, and thereby maximize throughput and acceptance ratio of transfer requests subject to deadlines. DaRTree is based on a novel integer linear program relaxation and deterministic rounding scheme. To this end, DaRTree uses multicast Steiner trees and adaptive routing based on the current network load. DaRTree provides its guarantees without need for rescheduling or preemption. Our evaluations show that DaRTree increases the network throughput and the number of accepted requests by up to 70%, especially for larger Wide-Area Networks (WANs). In fact, we also find that DaRTree even outperforms state-of-the-art solutions when the network scheduler is only capable of routing unicast transfers or when the WAN topology is bound to be non-reconfigurable.

While SDNs enable more flexible and adaptive network operations, (logically) centralized reconfigurations introduce overheads and delays, which can limit network reactivity. This paper initiates the study of a more distributed approach, in which the consistent network updates are implemented by the switches and routers directly in the data plane. In particular, our approach leverages concepts from local proof labeling systems, which allows the data plane elements to locally check network properties, and we show that this is sufficient to obtain global network guarantees. We demonstrate our approach considering three fundamental use cases, and analyze its benefits in terms of performance and fault-tolerance.

In order to support emerging data-intensive applications, many clever frameworks have been developed over the last years to efficiently and distributedly process big data sets, such as MapReduce. However, these frameworks are often optimized for relatively homogeneous environments, and accounting, e.g., for the varying connectivity of wide-area network infrastructure, may require complex placement algorithms. In this paper, we present Nap, which allows optimizing distributed data processing frameworks such as MapReduce for heterogeneous environments. Nap allows adapting resources dynamically, without requiring complex placement or migration algorithms, or modifications to the logic of the mappers and reducers. Rather, Nap simply changes the data partition, by spawning virtual nodes (e.g., reducers) depending on the demand. To this end, Nap leverages a connection to integer partition problems and employs Young lattices to guarantee minimal completion times (i.e., the makespan). In fact, Nap comes with provable performance guarantees and also supports applications that leverage redundancy to speed up executions further. In particular, to demonstrate our framework, as a case study, we show how to execute multiway joins across wide-area networks with limited bandwidth efficiently. Our experiments, based on a proof-of-concept prototype implementation, confirm the potential of Nap to reduce completion times.

We consider the SDN network update problem in which a controller wants to update the routes of k (unsplittable) flows from their old paths to the new paths, consistently, i.e., without temporary congestion. As updates communicated by the controller take effect asynchronously, the challenge is to perform these updates fast, i.e., using a minimal number of rounds (controller interactions). We present the first fast, i.e., polynomial-time solution for scheduling such congestion-free network updates, for two flows and in the node ordering model. We also show that the problem is already NP-hard for six flows. We complement our formal results with simulations.

Virtualization and multi-tenancy are attractive paradigms to improve the utilization of computing infrastructures and hence to reduce costs. In order to provide a high degree of resource sharing without sacrificing predictable cloud application performance, strict performance isolation needs to be ensured. This is non-trivial and requires models which account for all components where applications may interfere: similarly to security, the predictability of cloud application performance can only be as good as the least predictable component in the model. This paper identifies a new source of potential performance interference that has been overlooked so far: the network hypervisor - a critical component in any multi-tenant network. We present a first measurement study of the performance implications of the network hypervisor in Software-Defined Networks (SDNs). For the purpose of our study, we developed a new open-source benchmarking tool for OpenFlow control and data planes. We show that cloud application performance may appear unpredictable if the network hypervisor is not accounted for: the performance does not only depend on the specific hypervisor implementation and workload (e.g., OpenFlow message types), but also on the number of tenants and the size of the network. Hence, our results suggest that hypervisors should be included in our performance models, and their performance benchmarked and compared similarly to other crucial software components such as the SDN controller.

More and more networks are becoming reconfigurable: not just the routing can be programmed, but the physical layer itself as well. Various technologies enable this programmability, ranging from optical circuit switches to beamformed wireless connections and free-space optical interconnects. Existing reconfigurable network topologies are typically hybrid in nature, consisting of static and a reconfigurable links. However, even though the static and reconfigurable links form a joint structure, routing policies are artificially segregated and hence do not fully exploit the network resources: the state of the art is to route large elephant flows on direct reconfigurable links, whereas the remaining traffic is left to the static network topology. Recent work showed that such artificial segregation is inefficient, but did not provide the tools to actually leverage the benefits on non-segregated routing. In this paper, we provide several algorithms which take advantage of non-segregated routing, by jointly optimizing topology and routing. We compare our algorithms to segregated routing policies and also evaluate their performance in workload-driven simulations, based on real-world traffic traces. We find that our algorithms do not only outperform segregated routing policies, in various settings, but also come close to the optimal solution, computed by a mixed integer program formulation, also presented in this paper. Finally, we also provide insights into the complexity of the underlying combinatorial optimization problem, by deriving approximation hardness results.

With the increasing complexity of communication networks and the resulting threat of disruptions of mission critical services due to manual misconfiguration, automated verification is becoming a key element in today's network operation. In particular, it has recently been shown that a polynomial-time, automated verification of the policy-compliance of network configurations is possible for the important class of MPLS networks, even under failures. However, this approach, while providing polynomial runtimes, is still fairly slow in practice and only allows to detect but not fix configurations. This paper proposes a novel approach to speed up the analysis of network properties as well as to suggest configuration changes in case a network property is not satisfied. More specifically, our solution, DeepMPLS, allows to predict if a network property is satisfiable, and if not, aims to present a counter example. We also show that DeepMPLS may be used to propose new prefix-rewriting rules in the MPLS configuration in order to make it satisfiable. DeepMPLS can hence be used for fast predictions, before more rigorous analyses are performed. DeepMPLS is based on a new extension of graph-based neural networks. Our prototype implementation, using Tensorflow, achieves low execution times and high accuracies in real-world network topologies.

The Price of Anarchy (PoA) is a well-established game-theoretic concept to shed light on coordination issues arising in open distributed systems. Leaving agents to selfishly optimize comes with the risk of ending up in sub-optimal states (in terms of performance and/or costs), compared to a centralized system design. However, the PoA relies on strong assumptions about agents' rationality (e.g., resources and information) and interactions, whereas in many distributed systems agents interact locally with bounded resources. They do so repeatedly over time (in contrast to "one-shot games"), and their strategies may evolve. Using a more realistic evolutionary game model, this paper introduces a realized evolutionary Price of Anarchy (ePoA). The ePoA allows an exploration of equilibrium selection in dynamic distributed systems with multiple equilibria, based on local interactions of simple memoryless agents. Considering a fundamental game related to virus propagation on networks, we present analytical bounds on the ePoA in basic network topologies and for different strategy update dynamics. In particular, deriving stationary distributions of the stochastic evolutionary process, we find that the Nash equilibria are not always the most abundant states, and that different processes can feature significant off-equilibrium behavior, leading to a significantly higher ePoA compared to the PoA studied traditionally in the literature.

This paper investigates the power of preprocessing in the CONGEST model. Schmid and Suomela (ACM HotSDN 2013) introduced the SUPPORTED CONGEST model to study the application of distributed algorithms in Software-Defined Networks (SDNs). In this paper, we show that a large class of lower bounds in the CONGEST model still hold in the SUPPORTED model, highlighting the robustness of these bounds. This also raises the question how much does preprocessing help in the CONGEST model

To provide fast traffic recovery upon failures, most modern networks support static Fast Rerouting (FRR) mechanisms for mission critical services. However, configuring FRR mechanisms to tolerate multiple failures poses challenging algorithmic problems. While state-of-the-art solutions leveraging arc-disjoint arborescence-based network decompositions ensure that failover routes always reach their destinations eventually, even under multiple concurrent failures, these routes may be long and introduce unnecessary loads; moreover, they are tailored to worst-case failure scenarios. This paper presents an algorithmic framework for improving a given FRR network decomposition, using postprocessing. In particular, our framework is based on iterative arc swapping strategies and supports a number of use cases, from strengthening the resilience (e.g., in the presence of shared risk link groups) to improving the quality of the resulting routes (e.g., reducing route lengths and induced loads). Our simulations show that postprocessing is indeed beneficial in various scenarios, and can therefore enhance today's approaches.

Private networks are typically assumed to be trusted as security mechanisms are usually deployed on hosts and the data plane is managed in-house. The increasing number of attacks on network devices, and recent reports on backdoors, forces us to revisit existing security assumptions and demands new approaches to detect malicious activity. This paper presents Preacher, a runtime network policy checker, which leverages a secure, redundant and adaptive sample distribution scheme that allows us to provably detect adversarial switches or routers trying to reroute, mirror, drop, inject, or modify packets (i.e., header and/or payload) even under collusion. Additionally, the analysis performed by Preacher is highly parallelizable. We show that emerging programmable networks provide an ideal vehicle to detect suspicious network activity. Furthermore, we analytically and empirically evaluate the effectiveness of our approach in different adversarial settings, report on a proof-of-concept implementation using ONOS, and provide insights into the resource and performance overheads of Preacher.

This paper explores the design of dynamic network topologies which adjust to the workload they serve, in an online manner. Such self-adjusting networks (SANs) are enabled by emerging optical technologies, and can be found, e.g., in datacenters. SANs can be used to reduce routing costs by moving frequently communicating nodes topologically closer. This paper presents SANs which provide, for the first time, provable working set guarantees: the routing cost between node pairs is proportional to how recently these nodes communicated last time. Our SANs rely on skip lists (which serve as the topology) and provide additional interesting properties such as local routing.

Software-Defined Networks (SDNs) introduce great flexibilities in how packet routes can be defined and changed over time, and enable a more fine-grained and adaptive traffic engineering. The recently introduced support for more accurate synchronization in SDNs further improves the degree of control an operator can have over the packets' forwarding paths, and also allows to avoid disruptions and inconsistencies during network updates, i.e., during the rerouting of flows. However, how to optimally exploit such technology algorithmically - to efficiently schedule the update of multiple flows in such timed SDNs - while accounting for possible interference and congestion, is not well-understood today. We, in this paper, initiate the study of the fundamental problem of how to reroute the updates of multiple network flows in a synchronized SDN in a congestion-free manner. We rigorously prove that the problem is NP-hard for flows of unit size and network links with unit delay. We also show that a greedy approach to update the network can delay the update significantly. Our main contribution is the first solution to this problem: Chronicle. Our approach is based on time-extended network construction and the resource dependency graph, which is implemented by Openflow 1.5 using the scheduled bundles feature. The evaluation results show that Chronicle can reduce the makespan by 63% and reduce the number of changed rules by 50% compared to state-of-the-art.

Communication networks are the key enabling technology for our digital society. In order to sustain their critical services in the future, communication networks need to flexibly accommodate new requirements and changing contexts due to emerging diverse applications. In contrast to traditional networking technologies, software-oriented networking concepts, such as software-defined networking (SDN) and network function virtualization (NFV), provide ample opportunities for highly flexible network operations, enabling fast and simple adaptation of network resources and flows. This paper identifies the opportunities and challenges of adaptable softwarized networks and introduces a conceptual framework for adaptations in softwarized networks. We first explain how softwarized networks contribute to network adaptability through the functional primitives observation, composition, and control. We review the wide range of options for fine-granular observations as well as fine-granular composition and control provided by SDN and NFV. The multitude of fine-granular “tuning knobs” in adaptable softwarized networks complicates the decision making, which is the main focus of this paper. We propose to enhance the functional primitives observation, composition, and control with data-driven decision making, e.g., machine learning modules, resulting in deep observation, composition, and control. The data-driven decision making modules can learn and react to changes in the environment, e.g., new flow demands, so as to support meaningful decision making for adaptation in softwarized networks. Finally, we make the case for employing the concept of empowerment to realize truly “self-driving” networks.

The Minimum Dominating Set (MDS) problem is a fundamental and challenging problem in distributed computing. While it is well known that minimum dominating sets cannot be well approximated locally on general graphs, in recent years there has been much progress on computing good local approximations on sparse graphs and in particular on planar graphs. In this article, we study distributed and deterministic MDS approximation algorithms for graph classes beyond planar graphs. In particular, we show that existing approximation bounds for planar graphs can be lifted to bounded genus graphs and more general graphs, which we call locally embeddable graphs, and present (1) a local constant-time, constant-factor MDS approximation algorithm on locally embeddable graphs, and (2) a local O (log * n )-time (1+ϵ)-approximation scheme for any ϵ > 0 on graphs of bounded genus. Our main technical contribution is a new analysis of a slightly modified variant of an existing algorithm by Lenzen et al. [21]. Interestingly, unlike existing proofs for planar graphs, our analysis does not rely on direct topological arguments but on combinatorial density arguments only.

The softwarization of networks is enabled by the SDN (Software-Defined Networking), NV (Network Virtualization), and NFV (Network Function Virtualization) paradigms, and offers many advantages for network operators, service providers and datacenter providers. Given the strong interest in both industry and academia in the softwarization of telecommunication networks and cloud computing infrastructures, a series of special issues was established in IEEE Transactions on Network and Service Management, which aims at the timely publication of recent innovative research results on management of softwarized networks.

Existing virtual network admission control algorithms targeting high utilization of data center infrastructure are computationally expensive or provide poor performance. In particular, existing algorithms have in common that they are oblivious to the past, i.e., requests are handled in a fire-and-forget manner, not taking into account information from previously solved instances. This can be inefficient and misses out on a basic optimization opportunity: as for any network optimization algorithm that faces repeating problem instances, it may be beneficial to learn from network states and the outcome of acceptance decisions of the past. In this paper, we propose Ismael, a machine learning framework for predicting the acceptance of virtual clusters, one of the most common virtual network abstractions in data centers. Ismael can be configured with, and learn from, different existing algorithms by combining fixed-size feature representations for graphs with a convolutional neural network or a fully connected deep neural network. We report on extensive simulations, which demonstrate that it is possible to mimic existing, computationally intensive admission control algorithms with an accuracy of up to 94 %, while significantly reducing runtime.

The Virtual Network Embedding Problem (VNEP) captures the essence of many resource allocation problems. In the VNEP, customers request resources in the form of Virtual Networks. An embedding of a virtual network on a shared physical infrastructure is the joint mapping of (virtual) nodes to physical servers together with the mapping of (virtual) edges onto paths in the physical network connecting the respective servers. This work initiates the study of approximation algorithms for the VNEP for general request graphs. Concretely, we study the offline setting with admission control: given multiple requests, the task is to embed the most profitable subset while not exceeding resource capacities. Our approximation is based on the randomized rounding of Linear Programming (LP) solutions. Interestingly, we uncover that the standard LP formulation for the VNEP exhibits an inherent structural deficit when considering general virtual network topologies: its solutions cannot be decomposed into valid embeddings. In turn, focusing on the class of cactus request graphs, we devise a novel LP formulation, whose solutions can be decomposed. Proving performance guarantees of our rounding scheme, we obtain the first approximation algorithm for the VNEP in the resource augmentation model. We propose different types of rounding heuristics and evaluate their performance in an extensive computational study. Our results indicate that good solutions can be achieved even without resource augmentations. Specifically, heuristical rounding achieves 77.2% of the baseline's profit on average while respecting capacities.

Emerging data center architectures are becoming reconfigurable. While prior work has shown the practical benefits of reconfigurable topologies, the underlying algorithmic complexity is not yet well understood. In particular, most reconfigurable topologies are hybrid, where parts of the network are reconfigurable (consisting of optical or wireless devices) while other parts are static (consisting of electrical switches). Current proposals enforce a routing policy that routes flows on either part "exclusively" by labeling flows as mice or elephant. We show that such artificial segregation in routing policy results in non-optimal paths and argue for algorithms that route packets across the network seamlessly. In doing so, we present the first algorithmic study of reconfigurable network architectures and provide optimality and hardness proofs in terms of topology and routing policy. Our results show that classical matching algorithms, as used in prior work, are optimal only when the topology consists of one reconfigurable switch, and the routing policy is enforced to be segregated. In other words, if there is an option of routing flows seamlessly along reconfigurable and non-reconfigurable parts of the network, matching algorithms are not optimal. In fact, when the hybrid network is seen from a joint perspective, optimal routing is an NP-hard problem. We further show that optimally routing even two flows in a network with multiple reconfigurable switches is an NP-hard problem as well.

Future communication networks are expected to be highly automated, disburdening human operators of their most complex tasks. However, while first powerful and automated network analysis tools are emerging, existing tools provide only limited (and inefficient) support of reasoning about failure scenarios. We present P-Rex, a fast what-if analysis tool, that allows us to test important reachability and policy-compliance properties even under an arbitrary number of failures, in polynomial-time, i.e., without enumerating all failure scenarios (the usual approach today, if supported at all). P-Rex targets networks based on Multiprotocol Label Switching (MPLS) and its Segment Routing (SR) extension and comes with an expressive query language based on regular expressions. It takes into account the actual router tables, and is hence well-suited for debugging. We also report on an industrial case study and demonstrate that P-Rex supports rich queries, performing what-if analyses in less than 70 minutes in most cases, in a 24-router network with over 100,000 MPLS forwarding rules.

Changing a given configuration in a graph into another one is known as a reconfiguration problem. Such problems have recently received much interest in the context of algorithmic graph theory. We initiate the theoretical study of the following reconfiguration problem: How to reroute k unsplittable flows of a certain demand in a capacitated network from their current paths to their respective new paths, in a congestion-free manner? This problem finds immediate applications, e.g., in traffic engineering in computer networks. We show that the problem is generally NP-hard already for k=2 flows, which motivates us to study rerouting on a most basic class of flow graphs, namely DAGs. Interestingly, we find that for general k, deciding whether an unsplittable multi-commodity flow rerouting schedule exists, is NP-hard even on DAGs. Our main contribution is a polynomial-time (fixed parameter tractable) algorithm to solve the route update problem for a bounded number of flows on DAGs. At the heart of our algorithm lies a novel decomposition of the flow network that allows us to express and resolve reconfiguration dependencies among flows.

By introducing programmability, automated verification, and innovative debugging tools, Software-Defined Networks (SDNs) are poised to meet the increasingly stringent dependability requirements of today's communication networks. However, the design of fault-tolerant SDNs remains an open challenge. This paper considers the design of dependable SDNs through the lenses of self-stabilization - a very strong notion of fault-tolerance. In particular, we develop algorithms for an in-band and distributed control plane for SDNs, called Renaissance, which tolerates a wide range of (concurrent) controller, link, and communication failures. Our self-stabilizing algorithms ensure that after the occurrence of an arbitrary combination of failures, (i) every non-faulty SDN controller can eventually reach any switch in the network within a bounded communication delay (in the presence of a bounded number of concurrent failures) and (ii) every switch is managed by at least one non-faulty controller. We evaluate Renaissance through a rigorous worst-case analysis as well as a prototype implementation (based on OVS and Floodlight), and we report on our experiments using Mininet.

The advent of more accurate synchronization in Software-Defined Networks (SDNs) in general and the notion of timed updates in particular, enables operators to fully exploit the potential of the more fine-grained and adaptive traffic engineering, by avoiding disruptions and inconsistencies during the update. However, little is known today about how to schedule the update of multiple flows in such timed SDNs: As flows compete for limited resources, implementing a congestion-free update remains algorithmically challenging, even in timed SDNs. This paper initiates the study of the fundamental problem of how to reroute the update of multiple network flows in a synchronized SDN in a congestion-free manner. We show that that the problem is NP-hard already for flows of unit size and network links with unit delay. Our main contribution is a first solution for this problem: Chronicle. Our approach is based on a time-extended network construction and resource dependency graph, which is implemented by Openflow 1.5 using the scheduled bundles feature. Evaluation results show that Chronicle can reduce the makespan by 63% and reduce the number of changed rules by 50% compared to state-of-the-art.

Network virtualization enables increasingly diverse network services to cohabit and share a given physical infrastructure and its resources, with the possibility to rely on different network architectures and protocols optimized towards specific requirements. In order to ensure a predictable performance despite shared resources, network virtualization requires a strict performance isolation and hence, resource reservations. Moreover, the creation of virtual networks should be fast and efficient. The underlying NP-hard algorithmic problem is known as the Virtual Network Embedding (VNE) problem and has been studied intensively over the last years. This paper presents NeuroViNE, a novel approach to speed up and improve a wide range of existing VNE algorithms: NeuroViNE is based on a search space reduction mechanism and preprocesses a problem instance by extracting relevant subgraphs, i.e., good combinations of substrate nodes and links. These subgraphs can then be fed to an existing algorithm for faster and more resource-efficient embeddings. NeuroViNE relies on a Hopfield network, and its performance benefits are investigated in simulations for random networks, real substrate networks, and data center networks.

While automated network verification is emerging as a critical enabler to manage large complex networks, current approaches come with a high computational complexity. This paper initiates the study of communication networks whose configurations can be verified fast, namely in polynomial time. In particular, we show that in communication networks based on prefix rewriting, which include MPLS networks, important network properties such as reachability, loop-freedom, and transparency, can be verified efficiently, even in the presence of failures. This enables a fast what-if analysis, addressing a major concern of network administrators: while configuring and testing network policies for a fully functional network is challenging, ensuring policy compliance in the face of (possibly multiple) failures, is almost impossible for human administrators. At the heart of our approach lies an interesting connection to the theory of prefix rewriting systems, a subfield of language and automata theory.

Fast rerouting is an essential mechanism in any dependable communication network, allowing to quickly, i.e., locally, recover from network failures, without invoking the control plane. However, while locality ensures a fast reaction, the absence of global information also renders the design of highly resilient fast rerouting algorithms more challenging. In this paper, we study algorithms for fast rerouting in emerging Segment Routing (SR) networks, where intermediate destinations can be added to packets by nodes along the path. Our main contribution is a maximally resilient polynomial-time fast rerouting algorithm for SR networks based on a hypercube topology. Our algorithm is attractive as it preserves the original paths (and hence waypoints traversed along the way), and does not require packets to carry failure information. We complement our results with an integer linear program formulation for general graphs and exploratory simulation results.

Software Defined Networking (in short SDN, which is also an acronym for Software Defined Network), has emerged as a response to the limitations and complexities of traditional network architectures. At the heart of SDN lies the idea to consolidate the control over network devices into a logically centralized (software) controller separated from the data plane. The separation of the control plane and the data plane is realized via an open programming interface between the data plane switches and the SDN controller. The decoupling allows the control plane to evolve independently of the data plane, which enables faster innovation since software often exceeds hardware in innovation speed. Furthermore, logical centralization has the potential to simplify network operation and management by providing a single focal point where the consequences of management actions can be assessed, and possibly rejected if they would lead to some violation of operational constraints. OpenFlow, the standard SDN protocol today, is based on a simple match-action paradigm which results in great flexibilities, e.g., in terms of traffic engineering, definition of flows, as well as in-band network control functionalities.

The softwarization of networks is enabled by the SDN (Software-Defined Networking), NV (Network Virtualization), and NFV (Network Function Virtualization) paradigms, and offers many advantages for network operators, service providers and datacenter providers. Given the strong interest in both industry and academia in the softwarization of telecommunication networks and cloud computing infrastructures, a series of special section was established in IEEE Transactions on Network and Service Management, which aims at the timely publication of recent innovative research results on management of softwarized networks.

This paper studies the problem of compressing the forwarding information base (FIB), but taking a wider perspective. Indeed, FIB compression goes beyond sheer compression, as the gain in memory use obtained from the compression has consequences on the updates that will have to be applied to the compressed FIB. We are interested in the situation where forwarding rules can change over time, e.g., due to border gateway protocol (BGP) route updates. Accordingly, we frame FIB compression as an online problem and design competitive online algorithms to solve it. In contrast to prior work which mostly focused on static optimizations, we study an online variant of the problem where routes can change over time and where the number of updates to the FIB is taken into account explicitly. The reason to consider this version of the problem is that leveraging temporal locality while accounting for the number of FIB updates helps to keep routers CPU load low and reduces the number of FIB updates to be transferred, e.g., from the network-attached software-defined network controller to a remote switch. This paper introduces a formal model which is an interesting generalization of several classic online aggregation problems. Our main contribution is an O(w)-competitive algorithm, where w is the length of an IP address. We also derive a lower bound which shows that our result is asymptotically optimal within a natural class of algorithms, based on so-called sticks.

Reliable and highly available computer networks must implement resilient fast rerouting mechanisms: upon a link or node failure, an alternative route is determined quickly, without involving the network control plane. Designing such fast failover mechanisms capable of dealing with multiple concurrent failures, however, is challenging, as failover rules need to be installed proactively, i.e., ahead of time, without knowledge of the actual failures happening at runtime. Indeed, only little is known today about the design of resilient routing algorithms. This paper introduces a general framework to reason about and design local failover algorithms that minimize the resulting load after failover on dense networks, beyond destination-based routing. We show that due to the inherent locality of the failover decisions at runtime, the problem is fundamentally related to the field of distributed algorithms without coordination. We derive an intriguing lower bound on the inherent network load overhead any local fast failover scheme that will introduce in the worst case, even though globally seen, much more balanced traffic allocations exist. We then present different randomized and deterministic failover algorithms and analyze their overhead load. In particular, we build upon the theory of combinatorial designs and develop a novel deterministic failover mechanism based on symmetric block design theory, which tolerates a maximal number of link failures while ensuring low loads.

We consider the fundamental problem of updating arbitrary routes in a software-defined network in a (transiently) loop-free manner. Our objective is to compute fast network update schedules which minimize the number of interactions (i.e., rounds) between the controller and the network nodes. We first prove that this problem is difficult in general: The problem of deciding whether a k-round update schedule exists is NP-complete already for k = 3, and there are problem instances requiring Ω(n) rounds, where n is the network size. Given these negative results, we introduce an attractive, relaxed notion of loop-freedom. We show that relaxed loop-freedom admits for much shorter update schedules (up to a factor Ω(n) in the best case), and present a scheduling algorithm which requires at most Θ(log n) rounds.

In cloud environments, the absence of strict network performance guarantees leads to unpredictable job execution times. To address this issue, recently, there have been several proposals on how to provide guaranteed network performance. These proposals, however, rely on computing resource reservation schedules a priori. Unfortunately, this is not practical in today's cloud environments, where application demands are inherently unpredictable, e.g., due to differences in the input data sets or phenomena, such as failures and stragglers. To overcome these limitations, we designed Kraken, a system that allows to dynamically update minimum guarantees for both network bandwidth and compute resources at runtime. Unlike previous work, Kraken does not require prior knowledge about the resource needs of the applications but allows to modify reservations at runtime. Kraken achieves this through an online resource reservation scheme, which comes with provable optimality guarantees. In this paper, we motivate the need for dynamic resource reservation schemes, present how this is provided by Kraken, and evaluate Kraken via extensive simulations and a preliminary Hadoop prototype.

Computer networks have become a critical infrastructure. It is hence increasingly important to guarantee a correct, consistent, and secure network operation at any time, even during route updates. However, most existing works on consistent network update protocols focus on connectivity properties only (e.g., loop-freedom) while ignoring basic (security) policies. This paper studies how to update routes in a software-defined network in a transiently policy-compliant manner. In particular, our goal is to enforce waypoints: at no point in time should it be possible for packets to bypass security critical network functions (such as a firewall). This problem is timely, given the advent of network function virtualization which envisions more flexible middlebox deployments, not limited to the network edge. This paper shows that enforcing waypoint traversal in transient states can be challenging: waypoint enforcement can conflict with loop-freedom. Even worse, we rigorously prove that deciding whether a waypoint enforcing, loop-free network update schedule exists is NP-hard. These results hold for both kinds of loop-freedom used in the literature: strong and relaxed loop-freedom. This paper also presents optimized, exact mixed integer programs to decide feasibility quickly and to compute optimal update schedules. We report on extensive simulation results, and also study scenarios where entire “service chains,” connecting multiple waypoints, need to be updated consistently.

Reliable and highly available computer networks must implement resilient fast rerouting mechanisms: upon a link or node failure, an alternative route is determined quickly, without involving the network control plane. Designing such fast failover mechanisms capable of dealing with multiple concurrent failures however is challenging, as failover rules need to be installed proactively, i.e., ahead of time, without knowledge of the actual failures happening at runtime. Indeed, only little is known today about the design of resilient routing algorithms. This paper presents a deterministic local failover mechanism which we prove to result in a minimum network load for a wide range of communication patterns, solving an open problem. Our mechanism relies on the key insight that resilient routing essentially constitutes a distributed algorithm without coordination. Accordingly, we build upon the theory of combinatorial designs and develop a novel deterministic failover mechanism based on symmetric block design theory which tolerates a maximal number of Ω(n) link failures in an n-node network and in the worst-case, while always ensuring routing connectivity. In particular, we show that at least Ω(φ2) link failures are needed to generate a maximum link load of at least φ, which matches an existing bound on the number of link failures needed for an optimal failover scheme. We complement our formal analysis with simulations, showing that our approach outperforms prior schemes not only in the worst-case.

Software-defined networking is considered a promising new paradigm, enabling more reliable and formally verifiable communication networks. However, this paper shows that the separation of the control plane from the data plane, which lies at the heart of Software-Defined Networks (SDNs), introduces a new vulnerability which we call teleportation. An attacker (e.g., a malicious switch in the data plane or a host connected to the network) can use teleportation to transmit information via the control plane and bypass critical network functions in the data plane (e.g., a firewall), and to violate security policies as well as logical and even physical separations. This paper characterizes the design space for teleportation attacks theoretically, and then identifies four different teleportation techniques. We demonstrate and discuss how these techniques can be exploited for different attacks (e.g., exfiltrating confidential data at high rates), and also initiate the discussion of possible countermeasures. Generally, and given today's trend toward more intent-based networking, we believe that our findings are relevant beyond the use cases considered in this paper.

Adopting distributed control planes is critical towards ensuring high availability and fault-tolerance of dependable Software-Defined Networks (SDNs). However, designing and bootstrapping a distributed SDN control plane is a challenging task, especially if to be done in-band, without a dedicated control network, and without relying on legacy networking protocols. One of the most appealing and powerful notions of fault-tolerance is self-organization and this paper discusses the possibility of self-organizing algorithms for in-band control planes.

Software-Defined Networks (SDNs) introduce interesting new opportunities in how network routes can be defined, verified, and changed over time. Yet despite the logically-centralized perspective offered, an SDN still needs to be considered a distributed system: rule updates communicated from the controller to the individual switches traverse an asynchronous network and may arrive out-of-order, and hence lead to (temporary or permanent) inconsistencies. Accordingly, the consistent network update problem has recently received much attention. Motivated by the advent of tightly synchronized SDNs, we in this paper initiate the study of algorithms for consistent network updates in “timed SDNs”-SDNs in which individual node updates can be scheduled at specific times. This paper presents Chronus, which is based on provably congestion- and loop-free update scheduling algorithms, and avoids the flow table space headroom required by existing two-phase update approaches. We formulate the Minimum Update Time Problem (MUTP) as an optimization program. We propose a tree algorithm to check the feasibility and a greedy algorithm to find a update sequence in polynomial time. Extensive experiments on Mininet and numerical simulations show that Chronus can substantially reduce transient congestion by 75% and save over 60% of the rules compared to the state of the art.

This paper is motivated by the emerging vision of an automated and data-driven optimization of communication networks, making it possible to fully exploit the flexibilities offered by modern network technologies and heralding an era of fast and self-adjusting networks. We build upon our recent study of machine-learning approaches to (statically) optimize resource allocations based on the data produced by network algorithms in the past. We take our study a crucial step further by considering dynamic scenarios: scenarios where communication patterns can change over time. In particular, we investigate network algorithms which learn from the traffic distribution (the feature vector), in order to predict global network allocations (a multi-label problem). As a case study, we consider a well-studied fc-median problem arising in Software-Defined Networks, and aim to imitate and speedup existing heuristics as well as to predict good initial solutions for local search algorithms. We compare different machine learning algorithms by simulation and find that neural network can provide the best abstraction, saving up to two-thirds of the algorithm runtime.

We initiate the study of a natural and practically relevant new variant of online caching where the to-be-cached items can have dependencies. We assume that the universe is a tree T and items are tree nodes; we require that if a node v is cached then the whole subtree T(v) rooted at v is cached as well. This theoretical problem finds an immediate application in the context of forwarding table optimization in IP routing and software-defined networks. We present an elegant online deterministic algorithm TC for this problem, and rigorously prove that its competitive ratio is O(height(T) * k_ALG/(k_ALG-k_OPT+1)), where k_ALG and k_OPT denote the cache sizes of an online and the optimal offline algorithm, respectively. The result is optimal up to a factor of O(height(T)).

Traditionally, networks such as datacenter interconnects are designed to optimize worst-case performance under arbitrary traffic patterns. Such network designs can however be far from optimal when considering the actual workloads and traffic patterns which they serve. This insight led to the development of demand-aware datacenter interconnects which can be reconfigured depending on the workload. Motivated by these trends, this paper initiates the algorithmic study of demand-aware networks (DANs), and in particular the design of bounded-degree networks. The inputs to the network design problem are a discrete communication request distribution, D, defined over communicating pairs from the node set V, and a bound, d, on the maximum degree. In turn, our objective is to design an (undirected) demand-aware network N = (V,E) of bounded-degree d, which provides short routing paths between frequently communicating nodes distributed across N. In particular, the designed network should minimize the expected path length on N (with respect to D), which is a basic measure of the efficiency of the network. We show that this fundamental network design problem exhibits interesting connections to several classic combinatorial problems and to information theory. We derive a general lower bound based on the entropy of the communication pattern D, and present asymptotically optimal network-aware design algorithms for important distribution families, such as sparse distributions and distributions of locally bounded doubling dimensions.

SplayNets are reconfigurable networks which adjust to the communication pattern over time. We present DiSplayNets, a distributed (concurrent and decentralized) implementation of SplayNets.

Software-defined networks (SDNs) introduce interesting new opportunities in how network routes can be defined, verified, and changed over time. Despite the logically-centralized perspective offered, however, an SDN still needs to be considered a distributed system: rule updates communicated from the controller to the individual switches traverse an asynchronous network and may arrive out-of-order. This can lead to (temporary or permanent) inconsistencies and triggered much research over the last years. We, in this paper, initiate the study of algorithms for consistent network updates in “timed SDNs”-SDNs in which individual node updates can be scheduled at specific times. While technology enabling tightly synchronized SDNs is emerging, the resulting algorithmic problems have not been studied yet. This paper presents, implements and evaluates Chronus, a system which provides provably congestion- and loop-free network updates, while avoiding the flow table space headroom required by existing two-phase update approaches. We formulate the minimum update time problem as an optimization program and propose two polynomial-time algorithms which lie at the heart of Chronus: a decision algorithm to check feasibility and a greedy algorithm to find a good update sequence. Extensive experiments on Mininet and numerical simulations show that Chronus can substantially reduce transient congestion and save over 60% of the rules compared with the state of the art.

The quickly growing demand for wireless networks and the numerous application-specific requirements stand in stark contrast to today's inflexible management and operation of wireless networks. While most research focuses on mobile networks, WiFi is often left out of the purview. In this paper, we present and evaluate OpenSDWN, a novel WiFi architecture based on a joint software-defined network and network functions virtualization approach. OpenSDWN exploits virtualization across the wired and wireless network and introduces datapath programmability to enable service differentiation and fine-grained transmission control, facilitating the prioritization of critical applications. OpenSDWN implements per-client virtual access points and per-client virtual middleboxes, to render network functions more flexible and support mobility and seamless migration. Moreover, OpenSDWN also increases the security of upcoming WiFi HotSpot architectures by following a functional split approach. Finally, OpenSDWN can also be used to out-source the control over the home network to a participatory interface or to an Internet service provider.

Topological self-stabilization is the ability of a distributed system to have its nodes themselves establish a meaningful overlay network. Independent from the initial network topology, it converges to the desired topology via forwarding, inserting, and deleting links to neighboring nodes. We adapt a linearization algorithm, originally designed for a shared memory model, to asynchronous message-passing. We use an extended localized pi-calculus to model the algorithm and to formally prove its essential self-stabilization properties: closure and weak convergence for every arbitrary initial configuration, and strong convergence for restricted cases.

Computer networks such as the Internet or datacenter networks have become a a crucial infrastructure for many criticial services. Accordingly, it is important that such networks preserve correctness criteria, even during transitions from one correct configuration to a new correct configuration. This paper initiates the study of how to simultaneously update multiple routes in a Software-Defined Network (SDN) in a transiently consistent and efficient manner. In particular, we study the problem of minimizing the number of switch interactions, in this paper also called "touches". Our main result is a negative one: we rigorously prove that jointly optimizing multiple route updates in a consistent and efficient manner is NP-hard, alreadyfor two routing policies. However, we also present an efficient, polynomial-time algorithm that, given correct update schedules for individual policies, computes an optimal global schedule with minimal touches.

In multi-tenant cloud environments, the absence of strict network performance guarantees leads to unpredictable job execution times. To address this issue, recently there have been several proposals on how to provide guaranteed network performance. These proposals, however, rely on computing resource reservation schedules a priori. Unfortunately, this is not practical in today's cloud environments, where application demands are inherently unpredictable, e.g., due to differences in the input datasets or phenomena such as failures and stragglers. To overcome these limitations, we designed KRAKEN, a system that allows tenants to dynamically request and update minimum guarantees for both network bandwidth and compute resources at runtime. Unlike previous work, Kraken does not require prior knowledge about the resource needs of the tenants' applications but allows tenants to modify their reservation at runtime. Kraken achieves this through an online resource reservation scheme which comes with provable optimality guarantees. In this paper, we motivate the need for dynamic resource reservation schemes, present how this is provided by Kraken, and evaluate Kraken via extensive simulations.

Programmability and verifiability lie at the heart of the software-defined networking paradigm. While OpenFlow and its match-action concept provide primitive operations to manipulate hardware configurations, over the last years, several more expressive network programming languages have been developed. This paper presents WNetKAT, the first network programming language accounting for the fact that networks are inherently weighted, and communications subject to capacity constraints (e.g., in terms of bandwidth) and costs (e.g., latency or monetary costs). WNetKAT is based on a syntactic and semantic extension of the NetKAT algebra. We demonstrate several relevant applications for WNetKAT, including cost and capacity-aware reachability, as well as quality-of-service and fairness aspects. These applications do not only apply to classic, splittable and unsplittable (s,t)-flows, but also generalize to more complex (and stateful) network functions and service chains. For example, WNetKAT allows to model flows which need to traverse certain waypoint functions, which can change the traffic rate. This paper also shows the relationship between the equivalence problem of WNetKAT and the equivalence problem of the weighted finite automata, which implies undecidability of the former. However, this paper also shows the decidability of whether an expression equals to 0, which is sufficient in many practical scenarios, and we initiate the discussion of decidable subsets of the whole language.

The Minimum Dominating Set (MDS) problem is not only one of the most fundamental problems in distributed computing, it is also one of the most challenging ones. While it is well-known that minimum dominating sets cannot be approximated locally on general graphs, over the last years, several breakthroughs have been made on computing local approximations on sparse graphs.

The Internet of Things (IoT) envisions that many devices can connect to a network. Visible Light Communication (VLC) based on Light Emitting Diodes (LEDs) is an attractive communication fabric for the IoT, as LEDs are readily available and can serve as transmitters as well as receivers. LED light bulbs, enhanced with photodiodes, provide an attractive path to extend device-to-device communication to room area networking. This paper describes a VLC system, called EnLighting, based on light bulbs that support an embedded Linux version (and its complete networking stack). These programmable light bulbs can both send and receive; they can communicate with objects in a room as well as with other light bulbs nearby. Bidirectional communication allows a light bulb to actively participate in networking and simplifies deployment, maintenance, configuration, and controllability of indoor lighting installations and services. EnLighting supports low-bandwidth communication services in a room (and via a gateway, beyond the room), which provide the base for other applications, e.g., a location service. This paper includes an initial evaluation of a room area communication and localization network based on prototype Linux-enabled light bulbs, reporting the performance for different network traffic types, and shows the benefits obtained from bidirectional communication. This proof-of- concept system illustrates that simple devices can provide an attractive solution to future communication challenges in the saturated radio spectrum.

Software-Defined Networks (SDNs) promise to overcome the often complex and error-prone operation of tradi- tional computer networks, by enabling programmabil- ity, automation and verifiability. Yet, SDNs also in- troduce new challenges, for example due to the asyn- chronous communication channel between the logically centralized control platform and the switches in the data plane. In particular, the asynchronous commu- nication of network update commands (e.g., OpenFlow FlowMod messages) may lead to transient inconsisten- cies, such as loops or bypassed waypoints (e.g., fire- walls). One approach to ensure transient consistency even in asynchronous environments is to employ smart scheduling algorithms: algorithms which update subsets of switches in each communication round only, where each subset in itself guarantees consistency. In this demo, we show how to change routing policies in a transiently consistent manner. We demonstrate two al- gorithms, namely, Wayup [5] and Peacock [4], which partition the network updates sent from SDN controller towards OpenFlow software switches into multiple rounds as per respective algorithms. Later, the barrier mes- sages are utilized to ensure reliable network updates.

Computer networks have become a critical infrastructure. Especially in shared environments such as datacenters it is important that a correct, consistent and secure network operation is guaranteed at any time, even during routing policy updates. In particular, at no point in time should it be possible for packets to bypass security critical waypoints~(such as a firewall or IDS) or to be forwarded along loops.

Decentralized monitoring and alarming systems can be an attractive alternative to centralized architectures. Distributed sensor nodes (e.g., in the smart grid's distribution network) are closer to an observed event than a global and remote observer or controller. This improves the visibility and response time of the system. Moreover, in a distributed system, local problems may also be handled locally and without overloading the communication network. This paper studies alarming from a distributed computing perspective and for two fundamentally different scenarios: on-duty and off-duty. We model the alarming system as a sensor network consisting of a set of distributed nodes performing local measurements to sense events. In order to avoid false alarms, the sensor nodes cooperate and only escalate an event (i.e., raise an alarm) if the number of sensor nodes sensing an event exceeds a certain threshold. In the on-duty scenario, nodes not affected by the event can actively help in the communication process, while in the off-duty scenario, non-event nodes are inactive. We present and analyze algorithms that minimize the reaction time of the monitoring system while avoiding unnecessary message transmissions. We investigate time and message complexity tradeoffs in different settings, and also shed light on the optimality of our algorithms by deriving cost lower bounds for distributed alarming systems.

This paper initiates the study of locally self-adjusting networks: networks whose topology adapts dynamically and in a decentralized manner, to the communication pattern σ. Our vision can be seen as a distributed generalization of the self-adjusting datastructures introduced by Sleator and Tarjan, 1985: In contrast to their splay trees which dynamically optimize the lookup costs from a single node (namely the tree root), we seek to minimize the routing cost between arbitrary communication pairs in the network. As a first step, we study distributed binary search trees (BSTs), which are attractive for their support of greedy routing. We introduce a simple model which captures the fundamental tradeoff between the benefits and costs of self-adjusting networks. We present the SplayNet algorithm and formally analyze its performance, and prove its optimality in specific case studies. We also introduce lower bound techniques based on interval cuts and edge expansion, to study the limitations of any demand-optimized network. Finally, we extend our study to multi-tree networks, and highlight an intriguing difference between classic and distributed splay trees.

Cloud computing heralded an era where resources can be scaled up and down elastically and in an online manner. This paper initiates the study of cost-effective cloud resource allocation algorithms under price discounts, using a competitive analysis approach. We show that for a single resource, the online resource renting problem can be seen as a 2-dimensional variant of the classic online parking permit problem, and we formally introduce the PPP2problem accordingly. Our main contribution is an online algorithm for PPP2which achieves a deterministic competitive ratio of k (under a certain set of assumptions), where k is the number of resource bundles. This is almost optimal, as we also prove a lower bound of k/3 for any deterministic online algorithm. Our online algorithm makes use of an optimal offline algorithm, which may be of independent interest since it is the first optimal offline algorithm for the 1D and 2D versions of the parking permit problem. Finally, we show that our algorithms and results also generalize to multiple resources (i.e., Multi-dimensional parking permit problems).

Virtualized datacenters offer great flexibilities in terms of resource allocation. In particular, by decoupling applications from the constraints of the underlying infrastructure, virtualization supports an optimized mapping of virtual machines as well as their interconnecting network to their physical counterparts: essentially a graph embedding problem. However, existing embedding algorithms such as Oktopus and Proteus often ignore a crucial dimension of the embedding problem, namely data locality: the input to a cloud application such as MapReduce is typically stored in a distributed, and sometimes redundant, file system. Since moving data is costly, an embedding algorithm should be data locality aware, and allocate computational resources close to the data, in case of redundant storage, the algorithm should also optimize the replica selection. This paper initiates the algorithmic study of data locality aware virtual cluster embeddings on datacenter topologies. We show that despite the multiple degrees of freedom in terms of embedding, replica selection and assignment, many problems can be solved efficiently. We also highlight the limitations of such optimizations, by presenting several NP-hardness proofs, interestingly, our hardness results also hold in uncapacitated networks of small diameter.

This paper presents SHEAR, a highly available hybrid network architecture which marries distributed legacy protocols with Software-Defined Networking (SDN) technology. SHEAR is based on a small deployment of Openflow switches which serve as “observability points”: SHEAR leverages legacy distributed control plane protocols to detect and localize failures, but outsources the actual failover logic to the logically centralized SHEAR controller, which can make faster and more informed routing decisions. Moreover, the Openflow switches are used to logically decompose the legacy network into loopfree components, enabling a simple and flexible traffic-engineering. The deployment problem solved by SHEAR can be seen as a new variant of a network tomography problem, and may be of independent interest. Our simulations show that in enterprise networks, between 2 to 10 % Openflow switches are sufficient to implement SHEAR. We also report on our prototype implementation which detects a failure and reroutes traffic in less than .3 seconds in our testbed-much faster than what is achieved by the less flexible and distributed legacy protocols. More generally, SHEAR demonstrates that in contrast to common belief, operating a hybrid software defined network can be simple, and given its benefits, a partial Openflow deployment may even be a long-term solution.

Software-defined networking (SDN) is a novel paradigm that outsources the control of programmable network switches to a set of software controllers. The most fundamental task of these controllers is the correct implementation of the network policy, i.e., the intended network behavior. In essence, such a policy specifies the rules by which packets must be forwarded across the network. This paper studies a distributed SDN control plane that enables concurrent and robust policy implementation. We introduce a formal model describing the interaction between the data plane and a distributed control plane (consisting of a collection of fault-prone controllers). Then we formulate the problem of consistent composition of concurrent network policy updates (termed the CPC Problem). To anticipate scenarios in which some conflicting policy updates must be rejected, we enable the composition via a natural transactional interface with all-or-nothing semantics. We show that the ability of an f-resilient distributed control plane to process concurrent policy updates depends on the tag complexity, i.e., the number of policy labels (a.k.a. tags) available to the controllers, and describe a CPC protocol with optimal tag complexity f + 2.

We consider the problem of updating arbitrary routes in a software-defined network in a (transiently) loop-free manner. We are interested in fast network updates, i.e., in schedules which minimize the number of interactions (i.e., rounds) between the controller and the network nodes. We first prove that this problem is difficult in general: The problem of deciding whether a k-round schedule exists is NP-complete already for k = 3, and there are problem instances requiring Ω(n) rounds, where n is the network size. Given these negative results, we introduce an attractive, relaxed notion of loop-freedom. We prove that O(log n)-round relaxed loop-free schedules always exist, and can also be computed efficiently.

The quickly growing demand for wireless networks and the numerous application-specific requirements stand in stark contrast to today's inflexible management and operation of WiFi networks. In this paper, we present and evaluate OpenSDWN, a novel WiFi architecture based on an SDN/NFV approach. OpenSDWN exploits datapath programmability to enable service differentiation and fine-grained transmission control, facilitating the prioritization of critical applications. OpenSDWN implements per-client virtual access points and per-client virtual middleboxes, to render network functions more flexible and support mobility and seamless migration. OpenSDWN can also be used to out-source the control over the home network to a participatory interface or to an Internet Service Provider.

It is well-known that without strict network bandwidth guarantees, application performance in multi-tenant cloud environments is unpredictable. While recently proposed systems support explicit bandwidth reservation mechanisms, they require the resource schedules to be announced ahead of time. We argue that this is not practical in today's cloud environments, where application demands are inherently unpredictable, e.g., due to stragglers. We in this paper present KRAKEN, a system that allows tenants to dynamically request and update minimum resource guarantees for both network bandwidth and compute resources at runtime. Unlike previous work, Kraken does not require prior knowledge about the resource needs of the tenants' applications but allows tenants to modify their reservation at runtime. Kraken achieves this through an online resource reservation scheme, and by optimally embedding and reconfiguring virtual networks.

In this work, we propose utilizing the rich connectivity between IXPs and ISPs for inter-domain path stitching, supervised by centralized QoS brokers. In this context, we highlight a novel abstraction of the Internet topology, i.e., the inter-IXP multigraph composed of IXPs and paths crossing the domains of their shared member ISPs. This can potentially serve as a dense Internet-wide substrate for provisioning guaranteed end-to-end (e2e) services with high path diversity and global IPv4 address space reach. We thus map the IXP multigraph, evaluate its potential, and introduce a rich algorithmic framework for path stitching on such graph structures.

Snapshots of the Forwarding Information Base (FIB) in Internet routers can be compressed (or aggregated) to at least half of their original size, as shown by previous studies. However, the permanent stream of updates to the FIB due to routing updates complicates FIB aggregation in practice: keeping a (near-)optimally aggregated FIB in face of these routing updates is algorithmically challenging. A sensible trade-off has to be found between the aggregation gain and the complexity of handling routing updates. This paper investigates whether the spatial and temporal locality properties of routing updates conceal opportunities for improving this trade-off in online FIB aggregation. Our contributions include an empirical study of the locality of updates in public Internet routing data. To facilitate this study, we design the Locality-aware FIB Aggregation (LFA) algorithm. We show, that an algorithm as simple as LFA can effectively leverage the locality of FIB churn to keep low the number of updates to the aggregated FIB, as within time periods of a few seconds or minutes, routing updates affect only a limited number of regions in the FIB.

Networks are critical for the security of many computer systems. However, their complex and asynchronous nature often renders it difficult to formally reason about network behavior. Accordingly, it is challenging to provide correctness guarantees, especially during network updates.

Software-defined networks (SDNs) have the potential to radically simplify the network management by providing a programmatic interface to a logically centralized controller. However, outsourcing the management to the software controller comes at a price, and good tradeoffs have to be found between the benefits of a fine-grained control and its costs. In this paper, we show that OpenFlow, the predominant SDN protocol, allows to implement powerful functions "in the south", i.e., in the data plane. Our approach, called SmartSouth, can be used to reduce interactions with the control plane as well as to make the network more robust. Moreover, while rendering the data plane "smarter", SmartSouth only relies on the standard OpenFlow match-action paradigm; thus, the data plane functions remain formally verifiable---a key benefit of SDN. To demonstrate the potential of SmartSouth, we discuss four basic applications: (1) topology snapshot, (2) anycast, (3) blackhole- and (4) critical node detection.

This paper attends to the well-known problem of compressing the Forwarding Information Base of a router or switch, while preserving a correct forwarding. In contrast to related work, we study an online variant of the problem where BGP routes can change over time, and where the number of updates to the FIB are taken into account explicitly. Minimizing the number of FIB updates is important, especially when they are sent across the network (e.g., from the network-attached SDN controller). This paper pursues a competitive analysis approach and introduces a formal model which is an interesting generalization of several classic online aggregation problems. The main contribution is a O (w)-competitive algorithm, where w is the length of an IP address. We also derive a lower bound which shows that our result is asymptotically optimal within a natural class of algorithms.

This paper considers the problem of how to efficiently share a wireless medium which is subject to harsh external interference or even jamming. While this problem has already been studied intensively for simplistic single-hop or unit disk graph models, we make a leap forward and study MAC protocols for the SINR interference model (a.k.a. the physical model). We make two contributions. First, we introduce a new adversarial SINR model which captures a wide range of interference phenomena. Concretely, we consider a powerful, adaptive adversary which can jam nodes at arbitrary times and which is only limited by some energy budget. The second contribution of this paper is a distributed MAC protocol which provably achieves a constant competitive throughput in this environment: we show that, with high probability, the protocol ensures that a constant fraction of the non-blocked time periods is used for successful transmissions. Our results also highlight an inherent difference between the SINR model and unit disk graph models.

Distributed applications often require high-performance networks with strict connectivity guarantees. For instance, many cloud applications suffer from today's variations of the intra-cloud bandwidth, which leads to poor and unpredictable application performance. Accordingly, we witness a trend towards virtual networks (VNets) which can provide resource isolation. Interestingly, while the problem of where to embed a VNet is fairly well-understood today, much less is known about when to optimally allocate a VNet. This however is important, as the requirements specified for a VNet do not have to be static, but can vary over time and even include certain temporal flexibilities. This paper initiates the study of the temporal VNet embedding problem (TVNEP). We propose a continuous-time mathematical programming approach to solve the TVNEP, and present and compare different algorithms. Based on these insights, we present the CSM-Model which incorporates both symmetry and state-space reductions to significantly speed up the process of computing exact solutions to the TVNEP. Based on the CSM-Model, we derive a greedy algorithm OGA to compute fast approximate solutions. In an extensive computational evaluation, we show that despite the hardness of the TVNEP, the CSM-Model is sufficiently powerful to solve moderately sized instances to optimality within one hour and under different objective functions (such as maximizing the number of embeddable VNets). We also show that the greedy algorithm exploits flexibilities well and yields good solutions. More generally, our results suggest that already little time flexibilities can improve the overall system performance significantly.

Wireless Local Area Networks (WLANs) based on the IEEE 802.11 standard apply a simple contention-based radio access protocol. Downlink communication from access points to mobile stations shares the radio channel with uplink communication from mobile stations to the access points. This protocol is due to the contention-based design that targets the operation in unlicensed spectrum. In the future, because of the growing demand for wireless communication services, WLANs might not only operate in unlicensed but also in licensed spectrum. However, licensed spectrum favors the use of separate (paired) radio channels for downlink and uplink communication - a setup that requires frequency-division-duplex communication. This paper describes and evaluates the feasibility of a WLAN system operating in paired spectrum with a proof of concept implementation. Our testbed employs off-the-shelf WLAN chips (two per device) and driver modifications that enable the system to operate with downlink-uplink separation while still maintaining the ability to function in unlicensed (single-channel) spectrum. We provide insights based on our testbed and evaluate the performance of our solution.

Peer-to-peer systems rely on a scalable overlay network that enables efficient routing between its members. Hypercubic topologies facilitate such operations while each node only needs to connect to a small number of other nodes. In contrast to static communication networks, peer-to-peer networks allow nodes to adapt their neighbor set over time in order to react to join and leave events and failures. This article shows how to maintain such networks in a robust manner. Concretely, we present a distributed and self-stabilizing algorithm that constructs a (slightly extended) skip graph, SKIP + , in polylogarithmic time from any given initial state in which the overlay network is still weakly connected. This is an exponential improvement compared to previously known self-stabilizing algorithms for overlay networks. In addition, our algorithm handles individual joins and leaves locally and efficiently.

This article studies the design of medium access control (MAC) protocols for wireless networks that are provably robust against arbitrary and unpredictable disruptions (e.g., due to unintentional external interference from co-existing networks or due to jamming). We consider a wireless network consisting of a set of n honest and reliable nodes within transmission (and interference) range of each other, and we model the external disruptions with a powerful adaptive adversary. This adversary may know the protocol and its entire history and can use this knowledge to jam the wireless channel at will at any time. It is allowed to jam a (1-ϵ)-fraction of the timesteps, for an arbitrary constant ϵ > 0 unknown to the nodes. The nodes cannot distinguish between the adversarial jamming or a collision of two or more messages that are sent at the same time. We demonstrate, for the first time, that there is a local-control MAC protocol requiring only very limited knowledge about the adversary and the network that achieves a constant (asymptotically optimal) throughput for the nonjammed time periods under any of the aforementioned adversarial strategies. The derived principles are also useful to build robust applications on top of the MAC layer, and we present an exemplary study for leader election, one of the most fundamental tasks in distributed computing.

Today's trend toward network virtualization and software-defined networking enables flexible new distributed systems where resources can be dynamically allocated and migrated to locations where they are most useful. This paper proposes a competitive analysis approach to design and reason about online algorithms that find a good tradeoff between the benefits and costs of a migratable service. A competitive online algorithm provides worst-case performance guarantees under any demand dynamics, and without any information or statistical assumptions on the demand in the future. This is attractive especially in scenarios where the demand is hard to predict and can be subject to unexpected events. As a case study, we describe a service (e.g., an SAP server or a gaming application) that uses network virtualization to improve the quality of service (QoS) experienced by thin client applications running on mobile devices. By decoupling the service from the underlying resource infrastructure, it can be migrated closer to the current client locations while taking into account migration costs. We identify the major cost factors in such a system and formalize the wide-area service migration problem. Our main contributions are a randomized and a deterministic online algorithm that achieve a competitive ratio of O(logn) in a simplified scenario, where n is the size of the substrate network. This is almost optimal. We complement our worst-case analysis with simulations in different specific scenarios and also sketch a migration demonstrator.

This paper demonstrates that virtual networks that are dynamically embedded on a given resource network may constitute a security threat as properties of the infrastructure-typically a business secret-are disclosed. We initiate the study of this new problem and introduce the notion of request complexity which captures the number of virtual network embedding requests needed to fully disclose the infrastructure topology. We derive lower bounds and present algorithms achieving an asymptotically optimal request complexity for the important class of tree and cactus graphs (complexity θ(n)) as well as arbitrary graphs (complexity θ(n2)).

This paper attends to a generalized version of the classic page migration problem where migration costs are not necessarily given by the migration distance only, but may depend on prior migrations, or on the available bandwidth along the migration path. Interestingly, this problem cannot be viewed from a Metrical Task System (MTS) perspective, despite the generality of MTS: The corresponding MTS has an unbounded state space and, thus, an unbounded competitive ratio. Nevertheless, we are able to present an optimal online algorithm for a wide range of problem variants, improving the best upper bounds known so far for more specific problems. For example, we present a tight bound of Θ(log n/log log n) for the competitive ratio of the virtual server migration problem introduced recently.

This paper initiates the study of self-adjusting networks (or distributed data structures) whose topologies dynamically adapt to a communication pattern σ. We present a fully decentralized self-adjusting solution called SplayNet. A SplayNet is a distributed generalization of the classic splay tree concept. It ensures short paths (which can be found using local-greedy routing) between communication partners while minimizing topological rearrangements. We derive an upper bound for the amortized communication cost of a SplayNet based on empirical entropies of σ, and show that SplayNets have several interesting convergence properties. For instance, SplayNets features a provable online optimality under special requests scenarios. We also investigate the optimal static network and prove different lower bounds for the average communication cost based on graph cuts and on the empirical entropy of the communication pattern σ. From these lower bounds it follows, e.g., that SplayNets are optimal in scenarios where the requests follow a product distribution as well. Finally, this paper shows that in contrast to the Minimum Linear Arrangement problem which is generally NP-hard, the optimal static tree network can be computed in polynomial time for any guest graph, despite the exponentially large graph family. We complement our formal analysis with a small simulation study on a Facebook graph.

Visible Light Communication (VLC) with Light Emitting Diodes (LEDs) as transmitters and receivers enables low bitrate wireless adhoc networking. LED-to-LED VLC adhoc networks with VLC devices communicating with each other over free-space optical links typically achieve a throughput of less than a megabit per second at distances of no more than a few meters. LED-to-LED VLC adhoc networks are useful for combining a smart illumination with low-cost networking. We present and evaluate a software-based VLC physical layer and a VLC medium access control layer that retain the simplicity of the LED-to-LED approach. The design satisfies the requirement that LEDs should always be perceived as on with constant brightness. In each VLC device, in addition to an LED, only a low-cost microcontroller is required for handling the software-based communication protocol. The results of our performance measurements confirm recent claims about the potential of LED-to-LED VLC adhoc networks as a useful technology for sensor networks, smart and connected consumer devices, and the Internet-of-Things.

The design of scalable and robust overlay topologies has been a main research subject since the very origins of peerto-peer (p2p) computing. Today, the corresponding optimization tradeoffs are fairly well-understood, at least in the static case and from a worst-case perspective. This paper revisits the peer-to-peer topology design problem from a self-organization perspective. We initiate the study of topologies which are optimized to serve the communication demand, or even self-adjusting as demand changes. The appeal of this new paradigm lies in the opportunity to be able to go beyond the lower bounds and limitations imposed by a static, communication-oblivious, topology. For example, the goal of having short routing paths (in terms of hop count) does no longer conflict with the requirement of having low peer degrees. We propose a simple overlay topology OBST(k) which is composed of k (rooted and directed) Binary Search Trees (BSTs), where k is a parameter. We first prove some fundamental bounds on what can and cannot be achieved optimizing a topology towards a static communication pattern (a static OBST(k)). In particular, we show that the number of BSTs that constitute the overlay can have a large impact on the routing costs, and that a single additional BST may reduce the amortized communication costs from Ω(log n) to O(1), where n is the number of peers. Subsequently, we discuss a natural self-adjusting extension of OBST(k), in which frequently communicating partners are “splayed together”.

Reducing operational costs and increasing energy efficiency are critical for mobile operators. One accepted way to tackle these issues is to make use of virtualization to share the same physical infrastructure among several virtual networks. However, sharing physical infrastructure presents a number of challenges, such as security issues, conflicting hardware control, and fair resource sharing. In our earlier work, we analyzed these challenges and demonstrated how virtualized mobile operator networks can address them. However, to create and manage virtual mobile networks, an automated configuration system is required. This system must incorporate the diverse nature of technology, ownership, and geographic domains into an overarching single virtual network. This paper discusses the main challenges in creating such an architecture. We then present our proposed architecture and describe how it meets these challenges. To conclude, we present our experiences in the real-world implementation of this architecture.

No abstract available.

Interference constitutes a major challenge to availability for communication networks operating over a shared medium. This paper proposes the medium access (MAC) protocol AntiJam, which achieves a high and fair throughput even in harsh environments. Our protocol mitigates internal interference, requiring no knowledge about the number of participants in the network. It is also robust to intentional and unintentional external interference, e.g., due to coexisting networks or jammers. We model external interference using a powerful reactive adversary that can jam a (1-ε) -portion of the time-steps, where 0 <; ε ≤ 1 is an arbitrary constant. The adversary uses carrier sensing to make informed decisions on when it is most harmful to disrupt communications. Moreover, we allow the adversary to be adaptive and to have complete knowledge of the entire protocol history. AntiJam makes efficient use of the nonjammed time periods and achieves, if ε is constant, a Θ(1)-competitive throughput. In addition, AntiJam features a low convergence time and has excellent fairness properties, such that channel access probabilities do not differ among nodes by more than a small constant factor.

The concept of CloudNets, virtual networks connecting cloud resources, has recently attracted much interest from both academic as well as business sides. CloudNets can realize the vision of affordable customized infrastructures. In particular, such networks are expected to be offered even in federated environments with multiple providers. Inter-provider communication about requirements or provisioning of truly customized virtual environments however require a powerful flexible resource description language (RDL). While extensibility and expressiveness seem to be natural requirements for such a language, we identify another less intuitive requirement affecting all actors (or stakeholders) in their economic benefits: the possibility to omit arbitrary specification details and to remainvaguewhile at the same time describing real world scenarios. Not only may a description language ignoring this constraint easily become too bulky to use, it is also likely to force players to focus on details they are not interested in or lack the knowledge to map their actual requirements to. This paper identifies detailed requirements for an RDL to allow for topology and requirement communication in business scenarios. Furthermore, we present the FleRD flexible resource description language for multi-provider virtual network architectures. FleRD is fully incorporated in our own CloudNet prototype architecture.

Tit-for-tat trading lies at the heart of many incentive mechanisms for distributed systems where participants are anonymous. However, since the standard tit-for-tat approach is restricted to bilateral exchanges, data is transferred only between peers with direct and mutual interests. Generalizing tit-for-tat to multi-lateral trades where contributions can occur along cycles of interest may improve the performance of a system in terms of faster downloads without compromising the incentive-compatibility inherent to tit-for-tat trading. In this paper, we study the potential benefits and limitations of such a generalized trading in swarm-based peer-to-peer systems. Extensive simulations are performed to evaluate different techniques and to identify the crucial parameters influencing the obtainable throughput improvements and the corresponding tradeoffs. Moreover, we discuss extensions for overhead reduction and provide an optimized distributed implementation of our techniques. In summary, we find that allowing inter-swarm trades on short trading cycles can improve the throughput significantly; on the other hand, trading on long cycles does not pay off as the communication and management overhead becomes exceedingly large while the additional performance gains are marginal.

This paper initiates the formal study of a fundamental problem: How to efficiently allocate a shared communication medium among a set of K co-existing networks in the presence of arbitrary external interference? While most literature on medium access focuses on how to share a medium among nodes, these approaches are often either not directly applicable to co-existing networks as they would violate the independence requirement, or they yield a low throughput if applied to multiple networks. We present the randomized medium access (MAC) protocol COMAC which guarantees that a given communication channel is shared fairly among competing and independent networks, and that the available bandwidth is used efficiently. These performance guarantees hold in the presence of arbitrary external interference or even under adversarial jamming. Concretely, we show that the co-existing networks can use a Ω(ε2 min{ε, 1 poly(K)})-fraction of the non-jammed time steps for successful message transmissions, where ε is the (arbitrarily distributed) fraction of time which is not jammed.

Intentional interference constitutes a major threat for communication networks operating over a shared medium where availability is imperative. Jamming attacks are often simple and cheap to implement. Today's jammers can perform physical carrier sensing in order to disrupt communication more efficiently, especially in a network of simple wireless devices such as sensor nodes, which usually operate over a single frequency (or a limited frequency band) and which cannot benefit from the use of spread spectrum or other more advanced technologies. This paper proposes the medium access (MAC) protocol ANTIjAM which is provably robust against a powerful reactive adversary who can jam a (1 - ε)-portion of the time steps, where ε is an arbitrary constant. The adversary uses carrier sensing to make informed decisions on when it is most harmful to disrupt communications. Moreover, we allow the adversary to be adaptive and to have complete knowledge of the entire protocol history. Our MAC protocol is able to make efficient use of the nonjammed time periods and achieves a Θ(1) competitive throughput in this harsh scenario, if ε is constant. In addition, ANTIjAM features a low convergence time and has excellent fairness properties in the sense that channel access probabilities among nodes do not differ by more than a small constant factor.

Electing a leader is a fundamental task in distributed computations. Many coordination problems, such as the access to a shared resource, and the resulting inefficiencies, can be avoided by relying on a leader. This paper presents Select, a leader election protocol for wireless networks where nodes communicate over a shared medium. Select is very robust in two respects. First, the protocol is self-stabilizing in the sense that it converges to a correct solution from any possible initial network state (e.g., where no or multiple nodes consider themselves a leader). This is an appealing property, especially for dynamic networks. Second, the described protocol is resilient against a powerful reactive jammer that blocks a significant fraction of all communication rounds. The reactive model is general and of interest beyond jamming (e.g., in the context of co-existing networks). The paper also reports on experimental results obtained from our simulation framework which allows us to study convergence behavior under different types of adversarial jammers.

This article reports on the results of our measurement study of the Kad network. Although several fully decentralized peer-to-peer systems have been proposed in the literature, most existing systems still employ a centralized architecture. The Kad ne

This paper introduces the distributed MAC protocol Jade. We consider a multi-hop wireless network with a single communication channel in which a powerful adversary is able to jam (groups of) nodes individually and during a (1 - ε)-fraction of the entire time, where ε > 0 is an arbitrarily small constant. Despite this harsh environment, Jade exploits the few non-jammed slots effectively and guarantees a high throughput.

It is well-known that the overall efficiency of a distributed system can suffer if the participating entities seek to maximize their individual performance. Consequently, mechanisms have been designed that force the participants to behave more cooperatively. Most of these game-theoretic solutions rely on payments between participants. Unfortunately, such payments are often cumbersome to implement in practice, especially in dynamic networks and where transaction costs are high. In this paper, we investigate the potential of mechanisms which work without payments. We consider the problem of throughput maximization in multi-channel environments and shed light onto the throughput increase that can be achieved with and without payments. We introduce and analyze two different concepts: the worst-caseleveragewhere we assume that players end up in the worst rational strategy profile, and the average-caseleveragewhere player select a random non-dominated strategy. Our theoretical insights are complemented by simulations.

Data dissemination in decentralized networks is often realized by using some form of swarming technique. Swarming enables nodes to gather dynamically in order to fulfill a certain task collaboratively and to exchange resources (typically pieces of files or packets of a multimedia data stream). As in most distributed systems, swarming applications face the problem that the nodes in a network have heterogeneous capabilities or act selfishly. We investigate the problem of efficient live data dissemination (e.g., TV streams) in swarms. The live streams should be distributed in such a way that only nodes with sufficiently large contributions to the system are able to fully receive it-even in the presence of freeloading nodes or nodes that upload substantially less than required to sustain the multimedia stream. In contrast, uncooperative nodes cannot properly receive the data stream as they are unable to fill their data buffers in time, incentivizing a fair sharing of resources. If the number of selfish nodes increases, our emulation results reveal that the situation steadily deteriorates for them, while obedient nodes continue to receive virtually all packets in time.

Peer-to-peer systems rely on scalable overlay networks that enable efficient routing between its members. Hypercubic topologies facilitate such operations while each node only needs to connect to a small number of other nodes. In contrast to static communication networks, peer-to-peer networks allow nodes to adapt their neighbor set over time in order to react to join and leave events and failures. This paper shows how to maintain such networks in a robust manner. Concretely, we present a distributed and self-stabilizing algorithm that constructs a (variant of the) skip graph in polylogarithmic time from any initial state in which the overlay network is still weakly connected. This is an exponential improvement compared to previously known self-stabilizing algorithms for overlay networks. In addition, individual joins and leaves are handled locally and require little work.

Denial of service (DoS) attacks are arguably one of the most cum-bersome problems in the Internet. This paper presents a distributed information system (over a set of completely connected servers) called Chameleon which is robust to DoS attacks on the nodes as well as the operations of the system. In particular, it allows nodes to efficiently look up and insert data items at any time, despite a powerful “past-insider adversary ” which has complete knowledge of the system up to some time point t0 and can use that knowledge in order to block a constant fraction of the nodes and inject lookup and insert requests to selected data. This is achieved with a smart randomized replication policy requiring a polylogarithmic overhead only and the interplay of a permanent and a temporary distributed hash table. All requests in Chameleon can be processed in polylog-arithmic time and work at every node.

Lucrative incentives in grid computing do not only attract honest participants, but also cheaters. To prevent selfish behavior, verification mechanisms are required. Today's solutions mostly base on redundancy and inherently exhibit a considerable overhead. Often, however, the verification of a result takes much less time than its computation. In this paper we propose a distributed checking scheme that exploits this asymmetry. Our mechanism detects wrong results and excludes cheaters in a distributed manner and hence disburdens the central of the grid server. We show how the verification scheme is used in an application which aims at breaking the discrete logarithm problem by a parallel implementation of the Pollard-p algorithm. Our implementation extends the BOINC server software and is robust to various rational attacks even in the presence of colluders.

This paper studies the problem of computing the most frequent element (the mode) by means of a distributed algorithm where the elements are located at the nodes of a network. Let k denote the number of distinct elements and further let mi be the number of occurrences of the element ei in the ordered list of occurrences m1m2≥ ... ≥ mk. We give a deterministic distributed algorithm with time complexity O(D+k) where D denotes the diameter of the graph, which is essentially tight. As our main contribution, a Monte Carlo algorithm is presented which computes the mode in O(D + F2/m12*log k) time with high probability, where the frequency moment Ft is defined as Ft = sumi=1k mit. This algorithm is substantially faster than the deterministic algorithm for various relevant frequency distributions. Moreover, we provide a lower bound of Omega(D+F5/(m15B)), where B is the maximum message size, that captures the effect of the frequency distribution on the time complexity to compute the mode.

This paper studies the fundamental trade-off between communication cost and delay cost arising in various contexts such as control message aggregation or organization theory. An optimization problem is considered where nodes are organized in a tree topology. The nodes seek to minimize the time until the root is informed about their states and to use as few transmissions as possible at the same time. We derive an upper bound on the competitive ratio of O(min(h,c)) where h is the tree's height, and c is the transmission cost per edge. Moreover, we prove that this upper bound is tight in the sense that any oblivious algorithm has a ratio of at least Omega(min(h,c)).

This paper studies a virus inoculation game on social networks. A framework is presented which allows the measuring of the windfall of friendship, i.e., how much players benefit if they care about the welfare of their direct neighbors in the social network graph compared to purely selfish environments. We analyze the corresponding equilibria and show that the computation of the worst and best Nash equilibrium is NP-hard. Intriguingly, even though the windfall of friendship can never be negative, the social welfare does not increase monotonically with the extent to which players care for each other. While these phenomena are known on an anecdotal level, our framework allows us to quantify these effects analytically.

This paper proposes to utilize algorithms from the probabilistic graphical models domain for Peer-to-Peer rating of data items and for computing "social influence" of nodes in a Peer-to-peer social network. We evaluate the practicality of our approach using large- scale simulations over a MSN Live Messenger subgraph consisting of about a million nodes. Our algorithms are general since they can be used for Peer-to-peer monitoring and for the efficient computation of other node ranking methods, such as PageRank and Information Centrality.

Developing algorithms for sensor networks - and proving their correctness and performance - requires simplifying but still realistic models. This paper surveys various models in use today and puts them into perspective. In addition, we propose interesting models which are not widely adopted by the community so far

Until now, the analysis of fault tolerance of peer-to-peer systems usually only covers random faults of some kind. Contrary to traditional algorithmic research, faults as well as joins and leaves occurring in a worst-case manner are hardly considered. In this paper, we devise techniques to build dynamic peer-to-peer systems which remain fully functional in spite of an adversary which continuously adds and removes peers. We exemplify our algorithms on a pancake topology and present a system which maintains peer degree and network diameter O(log n/log log n), where n is the total number of peers in the system

Peer-to-peer systems (p2p) are highly dynamic in nature. They may consist of millions of peers joining only for a limited period of time, resulting in hundreds of join and leave events per second. In this paper we introduce eQuus, a novel distributed hash table (DHT) suitable for highly dynamic environments. eQuus guarantees that lookups are always fast - in terms of both the delay and the total number of routing hops -, although peers may join and leave the network at any time and concurrently

Over the last years, game theory has provided great insights into the behavior of distributed systems by modeling the players as utility-maximizing agents. In particular, it has been shown that selfishness causes many systems to perform in a globally suboptimal fashion. Such systems are said to have a large Price of Anarchy. In this paper, we extend this active field of research by allowing some players to be malicious or Byzantine rather than selfish. We ask: What is the impact of Byzantine players on the system's efficiency compared to purely selfish environments or compared to the social optimum? In particular, we introduce the Price of Malice which captures this efficiency degradation. As an example, we analyze the Price of Malice of a game which models the containment of the spread of viruses. In this game, each node can choose whether or not to install anti-virus software. Then, a virus starts from a random node and iteratively infects all neighboring nodes which are not inoculated. We establish various results about this game. For instance, we quantify how much the presence of Byzantine players can deteriorate or---in case of highly risk-averse selfish players---improve the social welfare of the distributed system.

Current peer-to-peer (P2P) systems often suffer from a large fraction of freeriders not contributing any resources to the network. Various mechanisms have been designed to overcome this problem. However, the selfish behavior of peers has aspects which go beyond resource sharing. This paper studies the effects on the topology of a P2P network if peers selfishly select the peers to connect to. In our model, a peer exploits locality properties in order to minimize the latency (or response times) of its lookup operations. At the same time, the peer aims at not having to maintain links to too many other peers in the system. By giving tight bounds on the price of anarchy, we show that the resulting topologies can be much worse than if peers collaborated. Moreover, the network may never stabilize, even in the absence of churn. Finally, we establish the complexity of Nash equilibria in our game theoretic model of P2P networks. Specifically, we prove that it is NP-hard to decide whether our game has a Nash equilibrium and can stabilize.

We present Cryptree, a cryptographic tree structure which facilitates access control in file systems operating on untrusted storage. Cryptree leverages the file system's folder hierarchy to achieve efficient and intuitive, yet simple, access control. The highlights are its ability to recursively grant access to a folder and all its subfolders in constant time, the dynamic inheritance of access rights which inherently prevents scattering of access rights, and the possibility to grant someone access to a file or folder without revealing the identities of other accessors. To reason about and to visualize Cryptree, we introduce the notion of cryptographic links. We describe the Cryptrees we have used to enforce read and write access in our own file system. Finally, we measure the performance of the Cryptree and compare it to other approaches