Search

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 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 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. [ABSTRACT FROM AUTHOR]

Programmable data plane technologies enable the systematic reconfiguration of the low-level processing steps applied to network packets and are key drivers toward realizing the next generation of network services and applications. This survey presents recent trends and issues in the design and implementation of programmable network devices, focusing on prominent abstractions, architectures, algorithms, and applications proposed, debated, and realized over the past years. We elaborate on the trends that led to the emergence of this technology and highlight the most important pointers fromthe literature, casting different taxonomies for the field, and identifying avenues for future research. [ABSTRACT FROM AUTHOR]

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 to change and optimize the 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) and coherence (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 to artificially restrict the routing model, to significantly reduce the computational complexity without negatively affecting the route diversity much. [ABSTRACT FROM AUTHOR]

The maintenance of efficient and robust overlay networks is one of the most fundamental and reoccurring themes in networking. This article presents a survey of state-of-the-art algorithms to design and repair overlay networks in a distributed manner. In particular, we discuss basic algorithmic primitives to preserve connectivity, review algorithms for the fundamental problem of graph linearization, and then survey selfstabilizing algorithms for metric and scalable topologies. We also identify open problems and avenues for future research. [ABSTRACT FROM AUTHOR]

Aerial Base Stations (ABSs) promise resilient and perpetual connectivity after unexpected events such as natural disasters. However, the deployment and scheduling of ABSs introduce several algorithmic challenges. In particular, on-demand communication can change over time and be hard to accurately predict, so it needs to be handled in an online manner, accounting also for battery consumption constraints. This paper presents AirNet, an efficient software-based solution to operate ABSs which meet these requirements. AirNet is based on an efficient placement algorithm for ABSs which maximizes the number of covered users, and a scheduler which navigates and recharges ABSs in an energy-aware manner. To this end, we propose an energy-aware deployment algorithm and use an energy model to analyze the power consumption and thereby, improve the flight endurance. In addition, we evaluate a novel scheduling mechanism that efficiently manages the ABSs’ operations. Our simulations indicate that our approach can significantly improve the flight endurance and user coverage compared to a recent state-of-the-art approach. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM PUBLISHER]

Powerline communication networks assume an interesting position in the communication network space: similarly to wireless networks, powerline networks are based on a shared broadcast medium; unlike wireless networks, however, the signal propagation is constrained to the power lines of the electrical infrastructure, which is essentially a graph. This article presents an algorithmic model to study the design of communication services over powerline communication networks. As a case study, we focus on the fundamental broadcast problem, and present and analyze a distributed algorithm $$\textsc {Color}\textsc {Cast}$$ which terminates in at most n communication rounds, where n denotes the network size, even in a model where link qualities are unpredictable and time-varying. For comparison, the achieved broadcast time is lower than what can be achieved by any unknown-topology algorithm (lower bounds $$\varOmega (n\log n / \log (n/D))$$ and $$\varOmega (n \log D)$$ are proved in Kowalski and Pelc (Distrib Comput 18(1):43-57, ) resp. Clementi et al. () where D is the network diameter). Moreover, existing known-topology broadcast algorithms often fail to deliver the broadcast message entirely in this model. This article also presents a general broadcast lower bound for the powerline model. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

This article studies how a mechanism designer can influence games by promising payments to the players depending on their mutual choice of strategies. First, we investigate the cost of implementing a desirable behavior and present algorithms to compute this cost. Whereas a mechanism designer can decide efficiently whether strategy profiles can be implemented at no cost at all our complexity analysis indicates that computing an optimal implementation is generally NP-hard. Second, we introduce and analyze the concept of leverage in a game. The leverage captures the benefits that a benevolent or a malicious mechanism designer can achieve by implementing a certain strategy profile region within economic reason, i.e., by taking the implementation cost into account. Mechanism designers can often manipulate games and change the social welfare by a larger extent than the amount of money invested. Unfortunately, computing the leverage turns out to be intractable as well in the general case. [ABSTRACT FROM AUTHOR]

This article studies the fundamental trade-off between delay and communication cost in networks. We consider an online optimization problem where nodes are organized in a tree topology. The nodes seek to minimize the time until the root is informed about the changes of their states and to use as few transmissions as possible. 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 ω(min(h; c)). For chain networks, we prove a tight competitive ratio of Θ(min(√h; c)). Furthermore, we introduce a model for value-sensitive aggregation, where the cost depends on the number of transmissions and the error at the root. [ABSTRACT FROM AUTHOR]

Reconfigurable optical networks have emerged as a promising technology to efficiently serve the fast-growing traffic produced by the digital society. This paper provides a survey of the field. We first review enabling optical hardware technologies in general and then consider technologies that are specific to data center networks and wide-area networks in more detail. We further provide an overview of the cost models used in the literature as well as the algorithmic problems introduced by these technologies, their first solutions, and discuss systems and implementation aspects. We conclude with a discussion of open challenges. [ABSTRACT FROM AUTHOR]

The virtualization of modern computer networks introduces interesting new opportunities for a more flexible placement of network functions and middleboxes (firewalls, proxies, traffic optimizers, virtual switches, etc.). This paper studies approximation algorithms for the incremental deployment of a minimum number of middleboxes, such that capacity constraints at the middleboxes and length constraints on the communication routes are respected. Based on a new, purely combinatorial and rigorous proof of submodularity, we obtain our main result: a deterministic greedy approximation algorithm which only employs augmenting paths to serve future communication pairs. Hence, our algorithm does not require any changes to the locations of existing middleboxes or the preemption of previously served communication pairs when additional middleboxes are deployed. It is hence particularly attractive for incremental deployments. We prove that the achieved polynomial-time approximation bound is optimal, unless P = NP holds. This paper also initiates the study of a weighted problem variant, in which entire groups of nodes need to communicate via a middlebox, possibly at different rates. We present an LP relaxation and randomized rounding algorithm for this problem, leveraging an interesting connection to scheduling. We complement our formal results with a simulation study of a large set of synthetically generated instances. Our results indicate that the presented algorithms yield near-optimal solutions in practice. [ABSTRACT FROM AUTHOR]