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.

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.

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.

This paper presents a novel retransmission strategy for communication networks based on index coding. The particular example of OFDMA downlink networks is taken to illustrate its efficacy. The benefits and challenges in using index coding as a transmission strategy are highlighted. The paper concludes with characterization of expected index coding gain in terms of channel parameters.

Many companies now use crowdsourcing to leverage external (as well as internal) crowds to perform specialized work, and so methods of improving efficiency are critical. Tasks in crowdsourcing systems with specialized work have multiple steps and each step requires multiple skills. Steps may have different flexibilities in terms of obtaining service from one or multiple agents, due to varying levels of dependency among parts of steps. Steps of a task may have precedence constraints among them. Moreover, there are variations in loads of different types of tasks requiring different skill-sets and availabilities of different types of agents with different skill-sets. Considering these constraints together necessitates the design of novel schemes to allocate steps to agents. In addition, large crowdsourcing systems require allocation schemes that are simple, fast, decentralized and offer customers (task requesters) the freedom to choose agents. In this work we study the performance limits of such crowdsourcing systems and propose efficient allocation schemes that provably meet the performance limits under these additional requirements. We demonstrate our algorithms on data from a crowdsourcing platform run by a non-profit company and show significant improvements over current practice.

We present a novel distributed algorithm for counting all four-node induced subgraphs in a big graph. These counts, called the 4-profile, describe a graph's connectivity properties and have found several uses ranging from bioinformatics to spam detection. We also study the more complicated problem of estimating the local 4-profiles centered at each vertex of the graph. The local 4-profile embeds every vertex in an 11-dimensional space that characterizes the local geometry of its neighborhood: vertices that connect different clusters will have different local 4-profiles compared to those that are only part of one dense cluster.

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.

We study the problem of approximating the 3-profile of a large graph. 3-profiles are generalizations of triangle counts that specify the number of times a small graph appears as an induced subgraph of a large graph. Our algorithm uses the novel concept of 3-profile sparsifiers: sparse graphs that can be used to approximate the full 3-profile counts for a given large graph. Further, we study the problem of estimating local and ego 3-profiles, two graph quantities that characterize the local neighborhood of each vertex of a graph.

We propose FrogWild, a novel algorithm for fast approximation of high PageRank vertices, geared towards reducing network costs of running traditional PageRank algorithms. Our algorithm can be seen as a quantized version of power iteration that performs multiple parallel random walks over a directed graph. One important innovation is that we introduce a modification to the GraphLab framework that only partially synchronizes mirror vertices. This partial synchronization vastly reduces the network traffic generated by traditional PageRank algorithms, thus greatly reducing the per-iteration cost of PageRank. On the other hand, this partial synchronization also creates dependencies between the random walks used to estimate PageRank. Our main theoretical innovation is the analysis of the correlations introduced by this partial synchronization process and a bound establishing that our approximation is close to the true PageRank vector. We implement our algorithm in GraphLab and compare it against the default PageRank implementation. We show that our algorithm is very fast, performing each iteration in less than one second on the Twitter graph and can be up to 7x faster compared to the standard GraphLab PageRank implementation.

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.

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”.

The celebrated Perron–Frobenius (PF) theorem is stated for irreducible nonnegative square matrices, and provides a simple characterization of their eigenvectors and eigenvalues. The importance of this theorem stems from the fact that eigenvalue problems on such matrices arise in many fields of science and engineering, including dynamical systems theory, economics, statistics and optimization. However, many real-life scenarios give rise to nonsquare matrices. Despite the extensive development of spectral theories for nonnegative matrices, the applicability of such theories to non-convex optimization problems is not clear. In particular, a natural question is whether the PF Theorem (along with its applications) can be generalized to a nonsquare setting. Our paper provides a generalization of the PF Theorem to nonsquare multiple choice matrices. The extension can be interpreted as representing systems with additional degrees of freedom, where each client entity may choose between multiple servers that can cooperate in serving it (while potentially interfering with other clients). This formulation is motivated by applications to power control in wireless networks, economics and others, all of which extend known examples for the use of the original PF Theorem. We show that the option of cooperation does not improve the situation, in the sense that in the optimum solution, no cooperation is needed, and only one server per client entity needs to work. Hence, the additional power of having several potential servers per client translates into choosing the “best” single server and not into sharing the load between the servers in some way, as one might have expected. The two main contributions of the paper are (i) a generalized PF Theorem that characterizes the optimal solution for a non-convex problem, and (ii) an algorithm for finding the optimal solution in polynomial time. In addition, we extend the definitions of irreducibility and largest eigenvalue of square matrices to nonsquare ones in a novel and non-trivial way, which turns out to be necessary and sufficient for our generalized theorem to hold. To characterize the optimal solution, we use techniques from a wide range of areas. In particular, the analysis exploits combinatorial properties of polytopes, graph-theoretic techniques and analytic tools such as spectral properties of nonnegative matrices and root characterization of integer polynomials.

Consider the problem of source coding with side information in large networks with multiple receivers. In this case, standard coding techniques are either prohibitively complex to decode, or require source-network coding separation, resulting in sub-optimal transmission schemes. To alleviate this problem, we offer a joint network-source coding scheme based on matrix sparsification at the code design phase, which allows the terminals to use an efficient decoding procedure (syndrome decoding using LDPC), despite the network coding throughout the network. Via a novel relation between matrix sparsification and rate-distortion theory, we give lower and upper bounds on the best achievable sparsification performance, and analyze our scheme in the limit of weak side information at the receivers. Simulation results motivate the use of this scheme at non-limiting rates as well.

In this paper we study gossip based information spreading with bounded message sizes. We use algebraic gossip to disseminate k distinct messages to all n nodes in a network. For arbitrary networks we provide a new upper bound for uniform algebraic gossip of O((k + log n + D)Δ) rounds with high probability, where D and Δ are the diameter and the maximum degree in the network, respectively. For many topologies and selections of k this bound improves previous results, in particular, for graphs with a constant maximum degree it implies that uniform gossip is order optimal and the stopping time is Θ(k + D).

We study the stopping times of gossip algorithms for network coding. We analyze algebraic gossip (i.e., random linear coding) and consider three gossip algorithms for information spreading Pull, Push, and Exchange. The stopping time of algebraic gossip is known to be linear for the complete graph, but the question of determining a tight upper bound or lower bounds for general graphs is still open. We take a major step in solving this question, and prove that algebraic gossip on any graph of size n is O(Δn) where Δ is the maximum degree of the graph. This leads to a tight bound of Θ(n) for bounded degree graphs and an upper bound of O(n2) for general graphs. We show that the latter bound is tight by providing an example of a graph with a stopping time of Ω(n2). Our proofs use a novel method that relies on Jackson's queuing theorem to analyze the stopping time of network coding; this technique is likely to become useful for future research.