Showing 1–34 of 34 results for author: Schapira, M

The Observer Effect in Computer Networks

Authors: Tal Mizrahi, Michael Schapira, Yoram Moses

Abstract: Network measurement involves an inherent tradeoff between accuracy and overhead; higher accuracy typically comes at the expense of greater measurement overhead (measurement frequency, number of probe packets, etc.). Capturing the "right" balance between these two desiderata - high accuracy and low overhead - is a key challenge. However, the manner in which accuracy and overhead are traded off is s… ▽ More Network measurement involves an inherent tradeoff between accuracy and overhead; higher accuracy typically comes at the expense of greater measurement overhead (measurement frequency, number of probe packets, etc.). Capturing the "right" balance between these two desiderata - high accuracy and low overhead - is a key challenge. However, the manner in which accuracy and overhead are traded off is specific to the measurement method, rendering apples-to-apples comparisons difficult. To address this, we put forth a novel analytical framework for quantifying the accuracy-overhead tradeoff for network measurements. Our framework, inspired by the observer effect in modern physics, introduces the notion of a network observer factor, which formally captures the relation between measurement accuracy and overhead. Using our "network observer framework", measurement methods for the same task can be characterized in terms of their network observer factors, allowing for apples-to-apples comparisons. We illustrate the usefulness of our approach by showing how it can be applied to various application domains and validate its conclusions through experimental evaluation. △ Less

Submitted 13 June, 2024; originally announced June 2024.

Comments: This paper is an extended version of "The Observer Effect in Computer Networks", which was published in the ACM Applied Networking Research Workshop (ANRW), 2024

Verifying the Generalization of Deep Learning to Out-of-Distribution Domains

Authors: Guy Amir, Osher Maayan, Tom Zelazny, Guy Katz, Michael Schapira

Abstract: Deep neural networks (DNNs) play a crucial role in the field of machine learning, demonstrating state-of-the-art performance across various application domains. However, despite their success, DNN-based models may occasionally exhibit challenges with generalization, i.e., may fail to handle inputs that were not encountered during training. This limitation is a significant challenge when it comes t… ▽ More Deep neural networks (DNNs) play a crucial role in the field of machine learning, demonstrating state-of-the-art performance across various application domains. However, despite their success, DNN-based models may occasionally exhibit challenges with generalization, i.e., may fail to handle inputs that were not encountered during training. This limitation is a significant challenge when it comes to deploying deep learning for safety-critical tasks, as well as in real-world settings characterized by substantial variability. We introduce a novel approach for harnessing DNN verification technology to identify DNN-driven decision rules that exhibit robust generalization to previously unencountered input domains. Our method assesses generalization within an input domain by measuring the level of agreement between independently trained deep neural networks for inputs in this domain. We also efficiently realize our approach by using off-the-shelf DNN verification engines, and extensively evaluate it on both supervised and unsupervised DNN benchmarks, including a deep reinforcement learning (DRL) system for Internet congestion control -- demonstrating the applicability of our approach for real-world settings. Moreover, our research introduces a fresh objective for formal verification, offering the prospect of mitigating the challenges linked to deploying DNN-driven systems in real-world scenarios. △ Less

Submitted 30 June, 2024; v1 submitted 4 June, 2024; originally announced June 2024.

Comments: To appear in the Journal of Automated Reasoning (JAR), 2024. This is an extended version of a CAV 2023 paper, titled: "Verifying Generalization in Deep Learning"

A Deep Learning Perspective on Network Routing

Authors: Yarin Perry, Felipe Vieira Frujeri, Chaim Hoch, Srikanth Kandula, Ishai Menache, Michael Schapira, Aviv Tamar

Abstract: Routing is, arguably, the most fundamental task in computer networking, and the most extensively studied one. A key challenge for routing in real-world environments is the need to contend with uncertainty about future traffic demands. We present a new approach to routing under demand uncertainty: tackling this challenge as stochastic optimization, and employing deep learning to learn complex patte… ▽ More Routing is, arguably, the most fundamental task in computer networking, and the most extensively studied one. A key challenge for routing in real-world environments is the need to contend with uncertainty about future traffic demands. We present a new approach to routing under demand uncertainty: tackling this challenge as stochastic optimization, and employing deep learning to learn complex patterns in traffic demands. We show that our method provably converges to the global optimum in well-studied theoretical models of multicommodity flow. We exemplify the practical usefulness of our approach by zooming in on the real-world challenge of traffic engineering (TE) on wide-area networks (WANs). Our extensive empirical evaluation on real-world traffic and network topologies establishes that our approach's TE quality almost matches that of an (infeasible) omniscient oracle, outperforming previously proposed approaches, and also substantially lowers runtimes. △ Less

Submitted 5 March, 2023; v1 submitted 1 March, 2023; originally announced March 2023.

Comments: To appear at NSDI 2023

Verifying Generalization in Deep Learning

Authors: Guy Amir, Osher Maayan, Tom Zelazny, Guy Katz, Michael Schapira

Abstract: Deep neural networks (DNNs) are the workhorses of deep learning, which constitutes the state of the art in numerous application domains. However, DNN-based decision rules are notoriously prone to poor generalization, i.e., may prove inadequate on inputs not encountered during training. This limitation poses a significant obstacle to employing deep learning for mission-critical tasks, and also in r… ▽ More Deep neural networks (DNNs) are the workhorses of deep learning, which constitutes the state of the art in numerous application domains. However, DNN-based decision rules are notoriously prone to poor generalization, i.e., may prove inadequate on inputs not encountered during training. This limitation poses a significant obstacle to employing deep learning for mission-critical tasks, and also in real-world environments that exhibit high variability. We propose a novel, verification-driven methodology for identifying DNN-based decision rules that generalize well to new input domains. Our approach quantifies generalization to an input domain by the extent to which decisions reached by independently trained DNNs are in agreement for inputs in this domain. We show how, by harnessing the power of DNN verification, our approach can be efficiently and effectively realized. We evaluate our verification-based approach on three deep reinforcement learning (DRL) benchmarks, including a system for Internet congestion control. Our results establish the usefulness of our approach. More broadly, our work puts forth a novel objective for formal verification, with the potential for mitigating the risks associated with deploying DNN-based systems in the wild. △ Less

Submitted 9 May, 2023; v1 submitted 11 February, 2023; originally announced February 2023.

Comments: To appear in Proc. 35th Int. Conf. on Computer Aided Verification (CAV)

Verification-Aided Deep Ensemble Selection

Authors: Guy Amir, Tom Zelazny, Guy Katz, Michael Schapira

Abstract: Deep neural networks (DNNs) have become the technology of choice for realizing a variety of complex tasks. However, as highlighted by many recent studies, even an imperceptible perturbation to a correctly classified input can lead to misclassification by a DNN. This renders DNNs vulnerable to strategic input manipulations by attackers, and also oversensitive to environmental noise. To mitigate t… ▽ More Deep neural networks (DNNs) have become the technology of choice for realizing a variety of complex tasks. However, as highlighted by many recent studies, even an imperceptible perturbation to a correctly classified input can lead to misclassification by a DNN. This renders DNNs vulnerable to strategic input manipulations by attackers, and also oversensitive to environmental noise. To mitigate this phenomenon, practitioners apply joint classification by an *ensemble* of DNNs. By aggregating the classification outputs of different individual DNNs for the same input, ensemble-based classification reduces the risk of misclassifications due to the specific realization of the stochastic training process of any single DNN. However, the effectiveness of a DNN ensemble is highly dependent on its members *not simultaneously erring* on many different inputs. In this case study, we harness recent advances in DNN verification to devise a methodology for identifying ensemble compositions that are less prone to simultaneous errors, even when the input is adversarially perturbed -- resulting in more robustly-accurate ensemble-based classification. Our proposed framework uses a DNN verifier as a backend, and includes heuristics that help reduce the high complexity of directly verifying ensembles. More broadly, our work puts forth a novel universal objective for formal verification that can potentially improve the robustness of real-world, deep-learning-based systems across a variety of application domains. △ Less

Submitted 25 July, 2022; v1 submitted 8 February, 2022; originally announced February 2022.

Comments: To appear in FMCAD 2022

Towards Scalable Verification of Deep Reinforcement Learning

Authors: Guy Amir, Michael Schapira, Guy Katz

Abstract: Deep neural networks (DNNs) have gained significant popularity in recent years, becoming the state of the art in a variety of domains. In particular, deep reinforcement learning (DRL) has recently been employed to train DNNs that realize control policies for various types of real-world systems. In this work, we present the whiRL 2.0 tool, which implements a new approach for verifying complex prope… ▽ More Deep neural networks (DNNs) have gained significant popularity in recent years, becoming the state of the art in a variety of domains. In particular, deep reinforcement learning (DRL) has recently been employed to train DNNs that realize control policies for various types of real-world systems. In this work, we present the whiRL 2.0 tool, which implements a new approach for verifying complex properties of interest for DRL systems. To demonstrate the benefits of whiRL 2.0, we apply it to case studies from the communication networks domain that have recently been used to motivate formal verification of DRL systems, and which exhibit characteristics that are conducive for scalable verification. We propose techniques for performing k-induction and semi-automated invariant inference on such systems, and leverage these techniques for proving safety and liveness properties that were previously impossible to verify due to the scalability barriers of prior approaches. Furthermore, we show how our proposed techniques provide insights into the inner workings and the generalizability of DRL systems. whiRL 2.0 is publicly available online. △ Less

Submitted 13 August, 2021; v1 submitted 25 May, 2021; originally announced May 2021.

Comments: To appear in FMCAD 2021 (see https://fmcad.org/FMCAD21/)

Online Safety Assurance for Deep Reinforcement Learning

Authors: Noga H. Rotman, Michael Schapira, Aviv Tamar

Abstract: Recently, deep learning has been successfully applied to a variety of networking problems. A fundamental challenge is that when the operational environment for a learning-augmented system differs from its training environment, such systems often make badly informed decisions, leading to bad performance. We argue that safely deploying learning-driven systems requires being able to determine, in rea… ▽ More Recently, deep learning has been successfully applied to a variety of networking problems. A fundamental challenge is that when the operational environment for a learning-augmented system differs from its training environment, such systems often make badly informed decisions, leading to bad performance. We argue that safely deploying learning-driven systems requires being able to determine, in real time, whether system behavior is coherent, for the purpose of defaulting to a reasonable heuristic when this is not so. We term this the online safety assurance problem (OSAP). We present three approaches to quantifying decision uncertainty that differ in terms of the signal used to infer uncertainty. We illustrate the usefulness of online safety assurance in the context of the proposed deep reinforcement learning (RL) approach to video streaming. While deep RL for video streaming bests other approaches when the operational and training environments match, it is dominated by simple heuristics when the two differ. Our preliminary findings suggest that transitioning to a default policy when decision uncertainty is detected is key to enjoying the performance benefits afforded by leveraging ML without compromising on safety. △ Less

Submitted 7 October, 2020; originally announced October 2020.

Comments: 8 pages, to appear in The 19th ACM Workshop on Hot Topics in Networks (HotNets 2020)

Pied Piper: Rethinking Internet Data Delivery

Authors: Aran Bergman, Israel Cidon, Isaac Keslassy, Noga Rotman, Michael Schapira, Alex Markuze, Eyal Zohar

Abstract: We contend that, analogously to the transition from resource-limited on-prem computing to resource-abundant cloud computing, Internet data delivery should also be adapted to a reality in which the cloud offers a virtually unlimited resource, i.e., network capacity, and virtualization enables delegating local tasks, such as routing and congestion control, to the cloud. This necessitates rethinking… ▽ More We contend that, analogously to the transition from resource-limited on-prem computing to resource-abundant cloud computing, Internet data delivery should also be adapted to a reality in which the cloud offers a virtually unlimited resource, i.e., network capacity, and virtualization enables delegating local tasks, such as routing and congestion control, to the cloud. This necessitates rethinking the traditional roles of inter- and intra-domain routing and conventional end-to-end congestion control. We introduce Optimized Cloudified Delivery (OCD), a holistic approach for optimizing joint Internet/cloud data delivery, and evaluate OCD through hundreds of thousands of file downloads from multiple locations. We start by examining an OCD baseline approach: traffic from a source A to a destination B successively passes through two cloud virtual machines operating as relays - nearest to A and B; and the two cloud relays employ TCP split. We show that even this naive strategy can outperform recently proposed improved end-to-end congestion control paradigms (BBR and PCC) by an order of magnitude. Next, we present a protocol-free, ideal pipe model of data transmission, and identify where today's Internet data delivery mechanisms diverge from this model. We then design and implement OCD Pied Piper. Pied Piper leverages various techniques, including novel kernel-based transport-layer accelerations, to improve the Internet-Cloud interface so as to approximately match the ideal network pipe model. △ Less

Submitted 20 December, 2018; v1 submitted 13 December, 2018; originally announced December 2018.

Comments: 14 pages, 15 figures. Copyright notice added after submission to IEEE. Fixed error in reference from figure 6 to figure 5

Internet Congestion Control via Deep Reinforcement Learning

Authors: Nathan Jay, Noga H. Rotman, P. Brighten Godfrey, Michael Schapira, Aviv Tamar

Abstract: We present and investigate a novel and timely application domain for deep reinforcement learning (RL): Internet congestion control. Congestion control is the core networking task of modulating traffic sources' data-transmission rates to efficiently utilize network capacity, and is the subject of extensive attention in light of the advent of Internet services such as live video, virtual reality, In… ▽ More We present and investigate a novel and timely application domain for deep reinforcement learning (RL): Internet congestion control. Congestion control is the core networking task of modulating traffic sources' data-transmission rates to efficiently utilize network capacity, and is the subject of extensive attention in light of the advent of Internet services such as live video, virtual reality, Internet-of-Things, and more. We show that casting congestion control as RL enables training deep network policies that capture intricate patterns in data traffic and network conditions, and leverage this to outperform the state-of-the-art. We also highlight significant challenges facing real-world adoption of RL-based congestion control, including fairness, safety, and generalization, which are not trivial to address within conventional RL formalism. To facilitate further research and reproducibility of our results, we present a test suite for RL-guided congestion control based on the OpenAI Gym interface. △ Less

Submitted 21 May, 2019; v1 submitted 7 October, 2018; originally announced October 2018.

Comments: 10 pages, accepted to ICML 2019

Oblivious Routing via Random Walks

Authors: Michael Schapira, Gal Shahaf

Abstract: We present novel oblivious routing algorithms for both splittable and unsplittable multicommodity flow. Our algorithm for minimizing congestion for \emph{unsplittable} multicommodity flow is the first oblivious routing algorithm for this setting. As an intermediate step towards this algorithm, we present a novel generalization of Valiant's classical load balancing scheme for packet-switched networ… ▽ More We present novel oblivious routing algorithms for both splittable and unsplittable multicommodity flow. Our algorithm for minimizing congestion for \emph{unsplittable} multicommodity flow is the first oblivious routing algorithm for this setting. As an intermediate step towards this algorithm, we present a novel generalization of Valiant's classical load balancing scheme for packet-switched networks to arbitrary graphs, which is of independent interest. Our algorithm for minimizing congestion for \emph{splittable} multicommodity flow improves upon the state-of-the-art, in terms of both running time and performance, for graphs that exhibit good expansion guarantees. Our algorithms rely on diffusing traffic via iterative applications of the random walk operator. Consequently, the performance guarantees of our algorithms are derived from the convergence of the random walk operator to the stationary distribution and are expressed in terms of the spectral gap of the graph (which dominates the mixing time). △ Less

Submitted 6 December, 2017; originally announced December 2017.

A Machine Learning Approach to Routing

Authors: Asaf Valadarsky, Michael Schapira, Dafna Shahaf, Aviv Tamar

Abstract: Can ideas and techniques from machine learning be leveraged to automatically generate "good" routing configurations? We investigate the power of data-driven routing protocols. Our results suggest that applying ideas and techniques from deep reinforcement learning to this context yields high performance, motivating further research along these lines. Can ideas and techniques from machine learning be leveraged to automatically generate "good" routing configurations? We investigate the power of data-driven routing protocols. Our results suggest that applying ideas and techniques from deep reinforcement learning to this context yields high performance, motivating further research along these lines. △ Less

Submitted 11 November, 2017; v1 submitted 10 August, 2017; originally announced August 2017.

ACM Class: C.2.2

Stateless Computation

Authors: Danny Dolev, Michael Erdmann, Neil Lutz, Michael Schapira, Adva Zair

Abstract: We present and explore a model of stateless and self-stabilizing distributed computation, inspired by real-world applications such as routing on today's Internet. Processors in our model do not have an internal state, but rather interact by repeatedly mapping incoming messages ("labels") to outgoing messages and output values. While seemingly too restrictive to be of interest, stateless computatio… ▽ More We present and explore a model of stateless and self-stabilizing distributed computation, inspired by real-world applications such as routing on today's Internet. Processors in our model do not have an internal state, but rather interact by repeatedly mapping incoming messages ("labels") to outgoing messages and output values. While seemingly too restrictive to be of interest, stateless computation encompasses both classical game-theoretic notions of strategic interaction and a broad range of practical applications (e.g., Internet protocols, circuits, diffusion of technologies in social networks). We embark on a holistic exploration of stateless computation. We tackle two important questions: (1) Under what conditions is self-stabilization, i.e., guaranteed "convergence" to a "legitimate" global configuration, achievable for stateless computation? and (2) What is the computational power of stateless computation? Our results for self-stabilization include a general necessary condition for self-stabilization and hardness results for verifying that a stateless protocol is self-stabilizing. Our main results for the power of stateless computation show that labels of logarithmic length in the number of processors yield substantial computational power even on ring topologies. We present a separation between unidirectional and bidirectional rings (L/poly vs. P/poly), reflecting the sequential nature of computation on a unidirectional ring, as opposed to the parallelism afforded by the bidirectional ring. We leave the reader with many exciting directions for future research. △ Less

Submitted 30 November, 2016; originally announced November 2016.

Large Fixed-Diameter Graphs are Good Expanders

Authors: Michael Dinitz, Michael Schapira, Gal Shahaf

Abstract: We revisit the classical question of the relationship between the diameter of a graph and its expansion properties. One direction is well understood: expander graphs exhibit essentially the lowest possible diameter. We focus on the reverse direction, showing that "sufficiently large" graphs of fixed diameter and degree must be "good" expanders. We prove this statement for various definitions of "s… ▽ More We revisit the classical question of the relationship between the diameter of a graph and its expansion properties. One direction is well understood: expander graphs exhibit essentially the lowest possible diameter. We focus on the reverse direction, showing that "sufficiently large" graphs of fixed diameter and degree must be "good" expanders. We prove this statement for various definitions of "sufficiently large" (multiplicative/additive factor from the largest possible size), for different forms of expansion (edge, vertex, and spectral expansion), and for both directed and undirected graphs. A recurring theme is that the lower the diameter of the graph and (more importantly) the larger its size, the better the expansion guarantees. Aside from inherent theoretical interest, our motivation stems from the domain of network design. Both low-diameter networks and expanders are prominent approaches to designing high-performance networks in parallel computing, HPC, datacenter networking, and beyond. Our results establish that these two approaches are, in fact, inextricably intertwined. We leave the reader with many intriguing questions for future research. △ Less

Submitted 22 November, 2017; v1 submitted 6 November, 2016; originally announced November 2016.

Lying Your Way to Better Traffic Engineering

Authors: Marco Chiesa, Gábor Rétvári, Michael Schapira

Abstract: To optimize the flow of traffic in IP networks, operators do traffic engineering (TE), i.e., tune routing-protocol parameters in response to traffic demands. TE in IP networks typically involves configuring static link weights and splitting traffic between the resulting shortest-paths via the Equal-Cost-MultiPath (ECMP) mechanism. Unfortunately, ECMP is a notoriously cumbersome and indirect means… ▽ More To optimize the flow of traffic in IP networks, operators do traffic engineering (TE), i.e., tune routing-protocol parameters in response to traffic demands. TE in IP networks typically involves configuring static link weights and splitting traffic between the resulting shortest-paths via the Equal-Cost-MultiPath (ECMP) mechanism. Unfortunately, ECMP is a notoriously cumbersome and indirect means for optimizing traffic flow, often leading to poor network performance. Also, obtaining accurate knowledge of traffic demands as the input to TE is elusive, and traffic conditions can be highly variable, further complicating TE. We leverage recently proposed schemes for increasing ECMP's expressiveness via carefully disseminated bogus information ("lies") to design COYOTE, a readily deployable TE scheme for robust and efficient network utilization. COYOTE leverages new algorithmic ideas to configure (static) traffic splitting ratios that are optimized with respect to all (even adversarially chosen) traffic scenarios within the operator's "uncertainty bounds". Our experimental analyses show that COYOTE significantly outperforms today's prevalent TE schemes in a manner that is robust to traffic uncertainty and variation. We discuss experiments with a prototype implementation of COYOTE. △ Less

Submitted 1 November, 2016; v1 submitted 9 October, 2016; originally announced October 2016.

ACM Class: C.2.1

Nash-Peering: A New Techno-Economic Framework for Internet Interconnections

Authors: Doron Zarchy, Amogh Dhamdhere, Constantine Dovrolis, Michael Schapira

Abstract: The current framework of Internet interconnections, based on transit and settlement-free peering relations, has systemic problems that often cause peering disputes. We propose a new techno-economic interconnection framework called Nash-Peering, which is based on the principles of Nash Bargaining in game theory and economics. Nash-Peering constitutes a radical departure from current interconnection… ▽ More The current framework of Internet interconnections, based on transit and settlement-free peering relations, has systemic problems that often cause peering disputes. We propose a new techno-economic interconnection framework called Nash-Peering, which is based on the principles of Nash Bargaining in game theory and economics. Nash-Peering constitutes a radical departure from current interconnection practices, providing a broader and more economically efficient set of interdomain relations. In particular, the direction of payment is not determined by the direction of traffic or by rigid customer-provider relationships but based on which AS benefits more from the interconnection. We argue that Nash-Peering can address the root cause of various types of peering disputes. △ Less

Submitted 5 October, 2016; originally announced October 2016.

Dynamics at the Boundary of Game Theory and Distributed Computing

Authors: Aaron D. Jaggard, Neil Lutz, Michael Schapira, Rebecca N. Wright

Abstract: We use ideas from distributed computing and game theory to study dynamic and decentralized environments in which computational nodes, or decision makers, interact strategically and with limited information. In such environments, which arise in many real-world settings, the participants act as both economic and computational entities. We exhibit a general non-convergence result for a broad class of… ▽ More We use ideas from distributed computing and game theory to study dynamic and decentralized environments in which computational nodes, or decision makers, interact strategically and with limited information. In such environments, which arise in many real-world settings, the participants act as both economic and computational entities. We exhibit a general non-convergence result for a broad class of dynamics in asynchronous settings. We consider implications of our result across a wide variety of interesting and timely applications: game dynamics, circuit design, social networks, Internet routing, and congestion control. We also study the computational and communication complexity of testing the convergence of asynchronous dynamics. Our work opens a new avenue for research at the intersection of distributed computing and game theory. △ Less

Submitted 4 April, 2017; v1 submitted 9 September, 2015; originally announced September 2015.

Comments: This article includes significantly revised and extended material from the conference paper arXiv:0910.1585

Setting Lower Bounds on Truthfulness

Authors: Ahuva Mu'alem, Michael Schapira

Abstract: We present and discuss general techniques for proving inapproximability results for truthful mechanisms. We make use of these techniques to prove lower bounds on the approximability of several non-utilitarian multi-parameter problems. In particular, we demonstrate the strength of our techniques by exhibiting a lower bound of $2-\frac{1}{m}$ for the scheduling problem with unrelated machines (for… ▽ More We present and discuss general techniques for proving inapproximability results for truthful mechanisms. We make use of these techniques to prove lower bounds on the approximability of several non-utilitarian multi-parameter problems. In particular, we demonstrate the strength of our techniques by exhibiting a lower bound of $2-\frac{1}{m}$ for the scheduling problem with unrelated machines (formulated as a mechanism design problem in the seminal paper of Nisan and Ronen on Algorithmic Mechanism Design). Our lower bound applies to truthful randomized mechanisms (disregarding any computational assumptions on the running time of these mechanisms). Moreover, it holds even for the weaker notion of truthfulness for randomized mechanisms -- i.e., truthfulness in expectation. This lower bound nearly matches the known $\frac{7}{4}$ (randomized) truthful upper bound for the case of two machines (a non-truthful FPTAS exists). No lower bound for truthful randomized mechanisms in multi-parameter settings was previously known. We show an application of our techniques to the workload-minimization problem in networks. We prove our lower bounds for this problem in the inter-domain routing setting presented by Feigenbaum, Papadimitriou, Sami, and Shenker. Finally, we discuss several notions of non-utilitarian "fairness" (Max-Min fairness, Min-Max fairness, and envy minimization). We show how our techniques can be used to prove lower bounds for these notions. △ Less

Submitted 14 February, 2017; v1 submitted 30 July, 2015; originally announced July 2015.

Explicit Expanding Expanders

Authors: Michael Dinitz, Michael Schapira, Asaf Valadarsky

Abstract: Deterministic constructions of expander graphs have been an important topic of research in computer science and mathematics, with many well-studied constructions of infinite families of expanders. In some applications, though, an infinite family is not enough: we need expanders which are "close" to each other. We study the following question: Construct an an infinite sequence of expanders… ▽ More Deterministic constructions of expander graphs have been an important topic of research in computer science and mathematics, with many well-studied constructions of infinite families of expanders. In some applications, though, an infinite family is not enough: we need expanders which are "close" to each other. We study the following question: Construct an an infinite sequence of expanders $G_0,G_1,\dots$, such that for every two consecutive graphs $G_i$ and $G_{i+1}$, $G_{i+1}$ can be obtained from $G_i$ by adding a single vertex and inserting/removing a small number of edges, which we call the expansion cost of transitioning from $G_i$ to $G_{i+1}$. This question is very natural, e.g., in the context of datacenter networks, where the vertices represent racks of servers, and the expansion cost captures the amount of rewiring needed when adding another rack to the network. We present an explicit construction of $d$-regular expanders with expansion cost at most $5d/2$, for any $d\geq 6$. Our construction leverages the notion of a "2-lift" of a graph. This operation was first analyzed by Bilu and Linial, who repeatedly applied 2-lifts to construct an infinite family of expanders which double in size from one expander to the next. Our construction can be viewed as a way to "interpolate" between Bilu-Linial expanders with low expansion cost while preserving good edge expansion throughout. While our main motivation is centralized (datacenter networks), we also get the best-known distributed expander construction in the "self-healing" model. △ Less

Submitted 5 July, 2015; originally announced July 2015.

Comments: Extended abstract appears in ESA 2015

Measuring and mitigating AS-level adversaries against Tor

Authors: Rishab Nithyanand, Oleksii Starov, Adva Zair, Phillipa Gill, Michael Schapira

Abstract: The popularity of Tor as an anonymity system has made it a popular target for a variety of attacks. We focus on traffic correlation attacks, which are no longer solely in the realm of academic research with recent revelations about the NSA and GCHQ actively working to implement them in practice. Our first contribution is an empirical study that allows us to gain a high fidelity snapshot of the t… ▽ More The popularity of Tor as an anonymity system has made it a popular target for a variety of attacks. We focus on traffic correlation attacks, which are no longer solely in the realm of academic research with recent revelations about the NSA and GCHQ actively working to implement them in practice. Our first contribution is an empirical study that allows us to gain a high fidelity snapshot of the threat of traffic correlation attacks in the wild. We find that up to 40% of all circuits created by Tor are vulnerable to attacks by traffic correlation from Autonomous System (AS)-level adversaries, 42% from colluding AS-level adversaries, and 85% from state-level adversaries. In addition, we find that in some regions (notably, China and Iran) there exist many cases where over 95% of all possible circuits are vulnerable to correlation attacks, emphasizing the need for AS-aware relay-selection. To mitigate the threat of such attacks, we build Astoria--an AS-aware Tor client. Astoria leverages recent developments in network measurement to perform path-prediction and intelligent relay selection. Astoria reduces the number of vulnerable circuits to 2% against AS-level adversaries, under 5% against colluding AS-level adversaries, and 25% against state-level adversaries. In addition, Astoria load balances across the Tor network so as to not overload any set of relays. △ Less

Submitted 26 December, 2015; v1 submitted 19 May, 2015; originally announced May 2015.

Comments: Appearing at NDSS 2016

Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension

Authors: Amit Daniely, Michael Schapira, Gal Shahaf

Abstract: Algorithmic mechanism design (AMD) studies the delicate interplay between computational efficiency, truthfulness, and optimality. We focus on AMD's paradigmatic problem: combinatorial auctions. We present a new generalization of the VC dimension to multivalued collections of functions, which encompasses the classical VC dimension, Natarajan dimension, and Steele dimension. We present a correspondi… ▽ More Algorithmic mechanism design (AMD) studies the delicate interplay between computational efficiency, truthfulness, and optimality. We focus on AMD's paradigmatic problem: combinatorial auctions. We present a new generalization of the VC dimension to multivalued collections of functions, which encompasses the classical VC dimension, Natarajan dimension, and Steele dimension. We present a corresponding generalization of the Sauer-Shelah Lemma and harness this VC machinery to establish inapproximability results for deterministic truthful mechanisms. Our results essentially unify all inapproximability results for deterministic truthful mechanisms for combinatorial auctions to date and establish new separation gaps between truthful and non-truthful algorithms. △ Less

Submitted 4 April, 2015; v1 submitted 19 December, 2014; originally announced December 2014.

PCC: Re-architecting Congestion Control for Consistent High Performance

Authors: Mo Dong, Qingxi Li, Doron Zarchy, Brighten Godfrey, Michael Schapira

Abstract: TCP and its variants have suffered from surprisingly poor performance for decades. We argue the TCP family has little hope to achieve consistent high performance due to a fundamental architectural deficiency: hardwiring packet-level events to control responses without understanding the real performance result of its actions. We propose Performance-oriented Congestion Control (PCC), a new congestio… ▽ More TCP and its variants have suffered from surprisingly poor performance for decades. We argue the TCP family has little hope to achieve consistent high performance due to a fundamental architectural deficiency: hardwiring packet-level events to control responses without understanding the real performance result of its actions. We propose Performance-oriented Congestion Control (PCC), a new congestion control architecture in which each sender continuously observes the connection between its actions and empirically experienced performance, enabling it to consistently adopt actions that result in high performance. We prove that PCC converges to a stable and fair equilibrium. Across many real-world and challenging environments, PCC shows consistent and often 10x performance improvement, with better fairness and stability than TCP. PCC requires no router hardware support or new packet format. △ Less

Submitted 10 October, 2014; v1 submitted 24 September, 2014; originally announced September 2014.

Exploring the Limits of Static Failover Routing

Authors: Marco Chiesa, Andrei Gurtov, Aleksander Mądry, Slobodan Mitrović, Ilya Nikolaevkiy, Aurojit Panda, Michael Schapira, Scott Shenker

Abstract: We present and study the Static-Routing-Resiliency problem, motivated by routing on the Internet: Given a graph $G$, a unique destination vertex $d$, and an integer constant $c>0$, does there exist a static and destination-based routing scheme such that the correct delivery of packets from any source $s$ to the destination $d$ is guaranteed so long as (1) no more than $c$ edges fail and (2) there… ▽ More We present and study the Static-Routing-Resiliency problem, motivated by routing on the Internet: Given a graph $G$, a unique destination vertex $d$, and an integer constant $c>0$, does there exist a static and destination-based routing scheme such that the correct delivery of packets from any source $s$ to the destination $d$ is guaranteed so long as (1) no more than $c$ edges fail and (2) there exists a physical path from $s$ to $d$? We embark upon a systematic exploration of this fundamental question in a variety of models (deterministic routing, randomized routing, with packet-duplication, with packet-header-rewriting) and present both positive and negative results that relate the edge-connectivity of a graph, i.e., the minimum number of edges whose deletion partitions $G$, to its resiliency. △ Less

Submitted 27 July, 2016; v1 submitted 29 August, 2014; originally announced September 2014.

Comments: 30 pages

ACM Class: C.2.2

Self-stabilizing uncoupled dynamics

Authors: Aaron D. Jaggard, Neil Lutz, Michael Schapira, Rebecca N. Wright

Abstract: Dynamics in a distributed system are self-stabilizing if they are guaranteed to reach a stable state regardless of how the system is initialized. Game dynamics are uncoupled if each player's behavior is independent of the other players' preferences. Recognizing an equilibrium in this setting is a distributed computational task. Self-stabilizing uncoupled dynamics, then, have both resilience to arb… ▽ More Dynamics in a distributed system are self-stabilizing if they are guaranteed to reach a stable state regardless of how the system is initialized. Game dynamics are uncoupled if each player's behavior is independent of the other players' preferences. Recognizing an equilibrium in this setting is a distributed computational task. Self-stabilizing uncoupled dynamics, then, have both resilience to arbitrary initial states and distribution of knowledge. We study these dynamics by analyzing their behavior in a bounded-recall synchronous environment. We determine, for every "size" of game, the minimum number of periods of play that stochastic (randomized) players must recall in order for uncoupled dynamics to be self-stabilizing. We also do this for the special case when the game is guaranteed to have unique best replies. For deterministic players, we demonstrate two self-stabilizing uncoupled protocols. One applies to all games and uses three steps of recall. The other uses two steps of recall and applies to games where each player has at least four available actions. For uncoupled deterministic players, we prove that a single step of recall is insufficient to achieve self-stabilization, regardless of the number of available actions. △ Less

Submitted 5 May, 2014; v1 submitted 23 March, 2014; originally announced March 2014.

Pay or Play

Authors: Sigal Oren, Michael Schapira, Moshe Tennenholtz

Abstract: We introduce the class of pay or play games, which captures scenarios in which each decision maker is faced with a choice between two actions: one with a fixed payoff and an- other with a payoff dependent on others' selected actions. This is, arguably, the simplest setting that models selection among certain and uncertain outcomes in a multi-agent system. We study the properties of equilibria in s… ▽ More We introduce the class of pay or play games, which captures scenarios in which each decision maker is faced with a choice between two actions: one with a fixed payoff and an- other with a payoff dependent on others' selected actions. This is, arguably, the simplest setting that models selection among certain and uncertain outcomes in a multi-agent system. We study the properties of equilibria in such games from both a game-theoretic perspective and a computational perspective. Our main positive result establishes the existence of a semi-strong equilibrium in every such game. We show that although simple, pay of play games contain a large variety of well-studied environments, e.g., vaccination games. We discuss the interesting implications of our results for these environments. △ Less

Submitted 26 September, 2013; originally announced September 2013.

Comments: Appears in Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence (UAI2013)

Report number: UAI-P-2013-PG-488-497

BGP Security in Partial Deployment: Is the Juice Worth the Squeeze?

Authors: Robert Lychev, Sharon Goldberg, Michael Schapira

Abstract: As the rollout of secure route origin authentication with the RPKI slowly gains traction among network operators, there is a push to standardize secure path validation for BGP (i.e., S*BGP: S-BGP, soBGP, BGPSEC, etc.). Origin authentication already does much to improve routing security. Moreover, the transition to S*BGP is expected to be long and slow, with S*BGP coexisting in "partial deployment"… ▽ More As the rollout of secure route origin authentication with the RPKI slowly gains traction among network operators, there is a push to standardize secure path validation for BGP (i.e., S*BGP: S-BGP, soBGP, BGPSEC, etc.). Origin authentication already does much to improve routing security. Moreover, the transition to S*BGP is expected to be long and slow, with S*BGP coexisting in "partial deployment" alongside BGP for a long time. We therefore use theoretical and experimental approach to study the security benefits provided by partially-deployed S*BGP, vis-a-vis those already provided by origin authentication. Because routing policies have a profound impact on routing security, we use a survey of 100 network operators to find the policies that are likely to be most popular during partial S*BGP deployment. We find that S*BGP provides only meagre benefits over origin authentication when these popular policies are used. We also study the security benefits of other routing policies, provide prescriptive guidelines for partially-deployed S*BGP, and show how interactions between S*BGP and BGP can introduce new vulnerabilities into the routing system. △ Less

Submitted 10 July, 2013; originally announced July 2013.

ACM Class: C.2.2

On the Resilience of Routing Tables

Authors: Joan Feigenbaum, Brighten Godfrey, Aurojit Panda, Michael Schapira, Scott Shenker, Ankit Singla

Abstract: Many modern network designs incorporate "failover" paths into routers' forwarding tables. We initiate the theoretical study of the conditions under which such resilient routing tables can guarantee delivery of packets. Many modern network designs incorporate "failover" paths into routers' forwarding tables. We initiate the theoretical study of the conditions under which such resilient routing tables can guarantee delivery of packets. △ Less

Submitted 3 August, 2012; v1 submitted 16 July, 2012; originally announced July 2012.

Comments: Brief announcement, PODC 2012

Network-Destabilizing Attacks

Authors: Robert Lychev, Sharon Goldberg, Michael Schapira

Abstract: The Border Gateway Protocol (BGP) sets up routes between the smaller networks that make up the Internet. Despite its crucial role, BGP is notoriously vulnerable to serious problems, including (1) propagation of bogus routing information due to attacks or misconfigurations, and (2) network instabilities in the form of persistent routing oscillations. The conditions required to avoid BGP instabiliti… ▽ More The Border Gateway Protocol (BGP) sets up routes between the smaller networks that make up the Internet. Despite its crucial role, BGP is notoriously vulnerable to serious problems, including (1) propagation of bogus routing information due to attacks or misconfigurations, and (2) network instabilities in the form of persistent routing oscillations. The conditions required to avoid BGP instabilities are quite delicate. How, then, can we explain the observed stability of today's Internet in the face of common configuration errors and attacks? This work explains this phenomenon by first noticing that almost every observed attack and misconfiguration to date shares a common characteristic: even when a router announces egregiously bogus information, it will continue to announce the same bogus information for the duration of its attack/misconfiguration. We call these the "fixed-route attacks", and show that, while even simple fixed-route attacks can destabilize a network, the commercial routing policies used in today's Internet prevent such attacks from creating instabilities. △ Less

Submitted 30 August, 2012; v1 submitted 7 March, 2012; originally announced March 2012.

Comments: 14 pages, 1 figure

On the Structure of Weakly Acyclic Games

Authors: Alex Fabrikant, Aaron D. Jaggard, Michael Schapira

Abstract: The class of weakly acyclic games, which includes potential games and dominance-solvable games, captures many practical application domains. In a weakly acyclic game, from any starting state, there is a sequence of better-response moves that leads to a pure Nash equilibrium; informally, these are games in which natural distributed dynamics, such as better-response dynamics, cannot enter inescapabl… ▽ More The class of weakly acyclic games, which includes potential games and dominance-solvable games, captures many practical application domains. In a weakly acyclic game, from any starting state, there is a sequence of better-response moves that leads to a pure Nash equilibrium; informally, these are games in which natural distributed dynamics, such as better-response dynamics, cannot enter inescapable oscillations. We establish a novel link between such games and the existence of pure Nash equilibria in subgames. Specifically, we show that the existence of a unique pure Nash equilibrium in every subgame implies the weak acyclicity of a game. In contrast, the possible existence of multiple pure Nash equilibria in every subgame is insufficient for weak acyclicity in general; here, we also systematically identify the special cases (in terms of the number of players and strategies) for which this is sufficient to guarantee weak acyclicity. △ Less

Submitted 10 August, 2011; originally announced August 2011.

Comments: 17 pages. Revised and expanded version of a paper that appeared in the Proceedings of SAGT 2010

On Communication Protocols that Compute Almost Privately

Authors: Marco Comi, Bhaskar DasGupta, Michael Schapira, Venkatakumar Srinivasan

Abstract: A traditionally desired goal when designing auction mechanisms is incentive compatibility, i.e., ensuring that bidders fare best by truthfully reporting their preferences. A complementary goal, which has, thus far, received significantly less attention, is to preserve privacy, i.e., to ensure that bidders reveal no more information than necessary. We further investigate and generalize the approxim… ▽ More A traditionally desired goal when designing auction mechanisms is incentive compatibility, i.e., ensuring that bidders fare best by truthfully reporting their preferences. A complementary goal, which has, thus far, received significantly less attention, is to preserve privacy, i.e., to ensure that bidders reveal no more information than necessary. We further investigate and generalize the approximate privacy model for two-party communication recently introduced by Feigenbaum et al.[8]. We explore the privacy properties of a natural class of communication protocols that we refer to as "dissection protocols". Dissection protocols include, among others, the bisection auction in [9,10] and the bisection protocol for the millionaires problem in [8]. Informally, in a dissection protocol the communicating parties are restricted to answering simple questions of the form "Is your input between the values αand β(under a predefined order over the possible inputs)?". We prove that for a large class of functions, called tiling functions, which include the 2nd-price Vickrey auction, there always exists a dissection protocol that provides a constant average-case privacy approximation ratio for uniform or "almost uniform" probability distributions over inputs. To establish this result we present an interesting connection between the approximate privacy framework and basic concepts in computational geometry. We show that such a good privacy approximation ratio for tiling functions does not, in general, exist in the worst case. We also discuss extensions of the basic setup to more than two parties and to non-tiling functions, and provide calculations of privacy approximation ratios for two functions of interest. △ Less

Submitted 9 July, 2012; v1 submitted 7 February, 2011; originally announced February 2011.

Comments: to appear in Theoretical Computer Science (series A)

MSC Class: 91B26; 91A99; 68Q99 ACM Class: F.0

Journal ref: Theoretical Computer Science, 457, 45-58, 2012

Approximate Privacy: PARs for Set Problems

Authors: Joan Feigenbaum, Aaron D. Jaggard, Michael Schapira

Abstract: In previous work (arXiv:0910.5714), we introduced the Privacy Approximation Ratio (PAR) and used it to study the privacy of protocols for second-price Vickrey auctions and Yao's millionaires problem. Here, we study the PARs of multiple protocols for both the disjointness problem (in which two participants, each with a private subset of {1,...,k}, determine whether their sets are disjoint) and the… ▽ More In previous work (arXiv:0910.5714), we introduced the Privacy Approximation Ratio (PAR) and used it to study the privacy of protocols for second-price Vickrey auctions and Yao's millionaires problem. Here, we study the PARs of multiple protocols for both the disjointness problem (in which two participants, each with a private subset of {1,...,k}, determine whether their sets are disjoint) and the intersection problem (in which the two participants, each with a private subset of {1,...,k}, determine the intersection of their private sets). We show that the privacy, as measured by the PAR, provided by any protocol for each of these problems is necessarily exponential (in k). We also consider the ratio between the subjective PARs with respect to each player in order to show that one protocol for each of these problems is significantly fairer than the others (in the sense that it has a similarly bad effect on the privacy of both players). △ Less

Submitted 9 June, 2010; v1 submitted 19 January, 2010; originally announced January 2010.

Comments: 34 pages, nine figures, one table. Version 2 adds acknowledgements and Appendix B

Report number: DIMACS TR 2010-01

Approximate Privacy: Foundations and Quantification

Authors: Joan Feigenbaum, Aaron D. Jaggard, Michael Schapira

Abstract: Increasing use of computers and networks in business, government, recreation, and almost all aspects of daily life has led to a proliferation of online sensitive data about individuals and organizations. Consequently, concern about the privacy of these data has become a top priority, particularly those data that are created and used in electronic commerce. There have been many formulations of priv… ▽ More Increasing use of computers and networks in business, government, recreation, and almost all aspects of daily life has led to a proliferation of online sensitive data about individuals and organizations. Consequently, concern about the privacy of these data has become a top priority, particularly those data that are created and used in electronic commerce. There have been many formulations of privacy and, unfortunately, many negative results about the feasibility of maintaining privacy of sensitive data in realistic networked environments. We formulate communication-complexity-based definitions, both worst-case and average-case, of a problem's privacy-approximation ratio. We use our definitions to investigate the extent to which approximate privacy is achievable in two standard problems: the second-price Vickrey auction and the millionaires problem of Yao. For both the second-price Vickrey auction and the millionaires problem, we show that not only is perfect privacy impossible or infeasibly costly to achieve, but even close approximations of perfect privacy suffer from the same lower bounds. By contrast, we show that, if the values of the parties are drawn uniformly at random from {0,...,2^k-1}, then, for both problems, simple and natural communication protocols have privacy-approximation ratios that are linear in k (i.e., logarithmic in the size of the space of possible inputs). We conjecture that this improved privacy-approximation ratio is achievable for any probability distribution. △ Less

Submitted 9 June, 2010; v1 submitted 29 October, 2009; originally announced October 2009.

Comments: 33 pages, seven figures, two tables. Changes in version 2 include an expanded discussion of other approaches to approximate privacy and added acknowledgements

Report number: DIMACS TR 2009-14

Distributed Computing with Adaptive Heuristics

Authors: Aaron D. Jaggard, Michael Schapira, Rebecca N. Wright

Abstract: We use ideas from distributed computing to study dynamic environments in which computational nodes, or decision makers, follow adaptive heuristics (Hart 2005), i.e., simple and unsophisticated rules of behavior, e.g., repeatedly "best replying" to others' actions, and minimizing "regret", that have been extensively studied in game theory and economics. We explore when convergence of such simple dy… ▽ More We use ideas from distributed computing to study dynamic environments in which computational nodes, or decision makers, follow adaptive heuristics (Hart 2005), i.e., simple and unsophisticated rules of behavior, e.g., repeatedly "best replying" to others' actions, and minimizing "regret", that have been extensively studied in game theory and economics. We explore when convergence of such simple dynamics to an equilibrium is guaranteed in asynchronous computational environments, where nodes can act at any time. Our research agenda, distributed computing with adaptive heuristics, lies on the borderline of computer science (including distributed computing and learning) and game theory (including game dynamics and adaptive heuristics). We exhibit a general non-termination result for a broad class of heuristics with bounded recall---that is, simple rules of behavior that depend only on recent history of interaction between nodes. We consider implications of our result across a wide variety of interesting and timely applications: game theory, circuit design, social networks, routing and congestion control. We also study the computational and communication complexity of asynchronous dynamics and present some basic observations regarding the effects of asynchrony on no-regret dynamics. We believe that our work opens a new avenue for research in both distributed computing and game theory. △ Less

Submitted 12 October, 2010; v1 submitted 8 October, 2009; originally announced October 2009.

Comments: 36 pages, four figures. Expands both technical results and discussion of v1. Revised version will appear in the proceedings of Innovations in Computer Science 2011

Neighbor-Specific BGP: More Flexible Routing Policies While Improving Global Stability

Authors: Yi Wang, Michael Schapira, Jennifer Rexford

Abstract: Please Note: This document was written to summarize and facilitate discussion regarding (1) the benefits of changing the way BGP selects routes to selecting the most preferred route allowed by export policies, or more generally, to selecting BGP routes on a per-neighbor basis, (2) the safety condition that guarantees global routing stability under the Neighbor-Specific BGP model, and (3) ways of… ▽ More Please Note: This document was written to summarize and facilitate discussion regarding (1) the benefits of changing the way BGP selects routes to selecting the most preferred route allowed by export policies, or more generally, to selecting BGP routes on a per-neighbor basis, (2) the safety condition that guarantees global routing stability under the Neighbor-Specific BGP model, and (3) ways of deploying this model in practice. A paper presenting the formal model and proof of the stability conditions was published at SIGMETRICS 2009 and is available online. △ Less

Submitted 21 June, 2009; originally announced June 2009.

VC v. VCG: Inapproximability of Combinatorial Auctions via Generalizations of the VC Dimension

Authors: Elchanan Mossel, Christos Papadimitriou, Michael Schapira, Yaron Singer

Abstract: The existence of incentive-compatible computationally-efficient protocols for combinatorial auctions with decent approximation ratios is the paradigmatic problem in computational mechanism design. It is believed that in many cases good approximations for combinatorial auctions may be unattainable due to an inherent clash between truthfulness and computational efficiency. However, to date, resear… ▽ More The existence of incentive-compatible computationally-efficient protocols for combinatorial auctions with decent approximation ratios is the paradigmatic problem in computational mechanism design. It is believed that in many cases good approximations for combinatorial auctions may be unattainable due to an inherent clash between truthfulness and computational efficiency. However, to date, researchers lack the machinery to prove such results. In this paper, we present a new approach that we believe holds great promise for making progress on this important problem. We take the first steps towards the development of new technologies for lower bounding the VC dimension of k-tuples of disjoint sets. We apply this machinery to prove the first computational-complexity inapproximability results for incentive-compatible mechanisms for combinatorial auctions. These results hold for the important class of VCG-based mechanisms, and are based on the complexity assumption that NP has no polynomial-size circuits. △ Less

Submitted 12 May, 2009; originally announced May 2009.