Modern software-defined networks support the implementation of in-network failover mechanisms: mechanisms to quickly re-establish connectivity in data plane without interaction software controller. Interestingly, however, not much is known today about how make use these mechanisms.

This paper initiates the study of locally self-adjusting networks: networks whose topology adapts dynamically and in a decentralized manner, to communication pattern σ. Our vision can be seen as distributed generalization datastructures introduced by Sleator Tarjan, 1985: In contrast their splay trees which optimize lookup costs from single node (namely tree root), we seek minimize routing cost between arbitrary pairs network. As first step, binary search (BSTs), are attractive for support...

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

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 design FRR mechanisms for emerging reconfigurable switches.

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

We propose FrogWild, a novel algorithm for fast approximation of high PageRank vertices, geared towards reducing network costs running traditional algorithms. Our can be seen as quantized version power iteration that performs multiple parallel random walks over directed graph. One important innovation is we introduce modification to the GraphLab framework only partially synchronizes mirror vertices. This partial synchronization vastly reduces traffic generated by algorithms, thus greatly...

We study the stopping times of gossip algorithms for network coding. analyze algebraic (i.e., random linear coding) and consider three information spreading Pull, Push, Exchange. The time is known to be complete graph, but question determining a tight upper bound or lower bounds general graphs still open. take major step in solving this question, prove that on any graph size n O(Δn) where Δ maximum degree graph. This leads Θ(n) bounded an O(n <sup...

Emerging applications expect fast turn-around from in-network failover mechanisms. This paper starts exploring the design space for supporting high availability and low latency using reroute in programmable data planes. In particular, we present a primitive well-known mechanisms that is both efficient terms of packet processing latency, memory requirements, switch throughput.

Software-defined networks (SDNs) have the potential to radically simplify network management by providing a programmatic interface logically centralized controller. However, outsourcing software controller comes at price, and good tradeoffs be found between benefits of fine-grained control its costs.

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 design FRR mechanisms for emerging reconfigurable switches. Our main contribution is an primitive programmable planes, PURR, provides low failover latency and high switch throughput, by avoiding packet recirculation. PURR tolerates multiple concurrent failures comes with minimal memory...

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

Many companies now use crowdsourcing to leverage external (as well as internal) crowds perform specialized work, and so methods of improving efficiency are critical. Tasks in systems with work have multiple steps each step requires skills. Steps may different flexibilities terms obtaining service from one or agents, due varying levels dependency among parts steps. a task precedence constraints them. Moreover, there variations loads types tasks requiring skill-sets availabilities agents...

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 failover mechanisms capable of dealing with multiple concurrent failures, however, challenging, as rules need to be installed proactively, i.e., ahead time, knowledge actual failures happening at runtime. Indeed, only little known today about design routing...

This paper studies the resilient routing and (in-band) fast failover mechanisms supported in Software-Defined Networks (SDN). We analyze potential benefits limitations of such mechanisms, focus on two main metrics: (1) correctness (in terms connectivity loop-freeness) (2) load-balancing. make following contributions. First, we show that worst-case (i.e., under adversarial link failures), usefulness local is rather limited: already a small number failures will violate properties any policy,...

Traffic jams remain a challenging open problem inside and in vicinity of big cities around the world. This leads to loss "precious" working time during rush hours, waste huge amount fuel which is also undesirable terms carbon emission. In this context, traffic light constitutes bottleneck flow system. addition, disregard major cause road accidents. paper, we propose novel system scheduling location are broadcasted, using wireless technology, each (automated) vehicle. Using virtual or...

We propose FrogWild, a novel algorithm for fast approximation of high PageRank vertices, geared towards reducing network costs running traditional algorithms. Our can be seen as quantized version power iteration that performs multiple parallel random walks over directed graph. One important innovation is we introduce modification to the GraphLab framework only partially synchronizes mirror vertices. This partial synchronization vastly reduces traffic generated by algorithms, thus greatly...

Many companies now use crowdsourcing to leverage external as well internal crowds perform specialized work, and so methods of improving efficiency are critical. Tasks in systems with work have multiple steps each step requires skills. Steps may different flexibilities terms obtaining service from one or agents due varying levels dependency among parts steps. a task precedence constraints them. Moreover, there variations loads types tasks requiring skill sets availabilities sets. Considering...

We study the problem of approximating $3$-profile a large graph. $3$-profiles are generalizations triangle counts that specify number times small graph appears as an induced subgraph Our algorithm uses novel concept sparsifiers: sparse graphs can be used to approximate full for given Further, we estimating local and ego $3$-profiles, two quantities characterize neighborhood each vertex is distributed operates program over GraphLab PowerGraph framework. introduce edge pivoting which allows us...

The celebrated Perron--Frobenius (PF) theorem is stated for irreducible nonnegative square matrices, and provides a simple characterization of their eigenvectors eigenvalues. importance this stems from the fact that eigenvalue problems on such matrices arise in many fields science engineering, including dynamical systems theory, economics, statistics optimization. However, real-life scenarios give rise to nonsquare matrices. Despite extensive development spectral theories applicability...