Title: There's something about MRAI: Timing diversity exponentially worsens BGP convergence

To address the demands of interactive applications, individual network operators are decreasing the timers that affect BGP convergence, leading to greater diversity in the settings of these timers across the Internet. We shows that, ironically, timer heterogeneity actually makes routing convergence substantially _worse_. We examine the widely-used Min Route Advertisement Interval timer that rate-limits BGP update messages to reduce router overhead. We show that, while routing systems with homogeneous MRAI timers have _linear_ convergence time, diverse MRAIs can cause _exponential_ increases in both the number of BGP messages and the convergence time (as measured in "activations"), both in eBGP and iBGP. We prove tight upper bounds on these metrics in terms of MRAI timer diversity in general dispute-wheel-free networks, economically sensible (Gao-Rexford) settings, and even Gao-Rexford networks with reasonably natural structures. We also demonstrate significant impacts on the _data plane_: blackholes sometimes last throughout the route-convergence process, and forwarding changes, at best, are only polynomially less frequent than routing changes. We show that these problems vanish with system-wide next-hop routing policies, and in contiguous regions of the Internet with homogeneous MRAIs. This suggests practical strategies for mitigating the problem, particularly for iBGP, where all routers are administered by one institution.

Joint work with Umar Syed and Jennifer Rexford.

Title: How Secure are Secure Interdomain Routing Protocols?

In response to high-profile Internet outages, a number of secure interdomain routing protocols have been designed to prevent various attacks. While it is known that even secure protocols have vulnerabilities, we lack an understanding of the extent of the damage caused when an attacker strategically exploits these weaknesses. This work quantifies the ability of the main proposals (BGP, origin authentication, soBGP, S-BGP, and defensive filtering) to prevent strategic traffic-attraction attacks; that is, ASes that deliberately attract traffic to their networks in order to drop, tamper, or eavesdrop on packets.

We combine simulations on empirical AS-level topologies with theoretical analysis. Our results show that, even with advanced security solutions, an AS that widely announces a short path that is not flagged as invalid can frequently attract traffic from a sizable fraction of the Internet. Worse yet, more damaging attacks exist. We prove that finding the most damaging attack is NP-hard, and that seemingly bizarre strategies, like announcing longer paths, announcing to fewer neighbors, or triggering BGP loop-detection, can be used to attract more traffic. Such attacks are not merely hypothetical; we search the empirical AS topology to identify specific ASes that can launch them. A key implication of this work is that defensive filtering is crucial, even when advanced security solutions like S-BGP are deployed.

This is joint work with Michael Schapira, Pete Hummon, and Jennifer Rexford.

Title: The Impact of Communication Models on Routing-Algorithm Convergence

Autonomous routing algorithms, such as BGP, are intended to reach a globally consistent set of routes after nodes iteratively and independently collect, process, and share network information. Generally, the important role of the mechanism used to share information has been overlooked in previous analyses of these algorithms. Here we explicitly study how the network-communication model affects algorithm convergence. To do this, we consider a variety of factors, including channel reliability, how much information is processed from channels, and how many channels are processed simultaneously. Using these factors, we define a taxonomy of communication models and identify particular models of interest, including those used in previous theoretical work, those that most closely model real-world implementations of BGP, and those of potential interest for the design of future routing algorithms. We characterize an extensive set of relationships among models in our taxonomy and show that convergence depends on the communication model in nontrivial ways. These results highlight that certain models are best for proving conditions that guarantee convergence, while other models are best for characterizing conditions that might permit nonconvergence.

This is joint work with Vijay Ramachandran and Rebecca Wright.

Title: LISP-NERD: Considering trust and reliability trade-offs for Secure Routing

One of the key concern with Public key infrastructure has been ability to reliably verify large numbers of signers. How often, for instance, have you gone to a web site with a certificate that is, for some reason or another, invalid? Routers on the Internet cannot easily make decisions about things they determine to be invalid. LISP-NERD makes use of an experimental approach to Interdomain routing to reduce the number of signers within a PKI, at a cost of concentrating trust into a smaller number of entities through the use of an external mediation layer that is analogous to the current DNS trust model. The result is signed routing updates for end sites, and perhaps a more tractable problem for the s*BGP and the core of the Internet.

Title: The design and implementation of a policy framework for the future Internet

Policy is now crucially important for network design: there are many stakeholders, each of whose requirements a network should support. Among many examples, senders have a legitimate interest in the paths that their packets take, providers have analogous interests based on business relationships, and receivers want to shut off traffic from flooding senders. Unfortunately, it is clear neither how to balance these considerations in principle nor what mechanism can uphold a large union of them in practice. Our premise is that as our community contemplates a future Internet, this blurriness is unacceptable.

To bring the policy issues into focus, we (ironically) avoid predictions about which policy requirements will predominate in a future Internet and instead seek the most general policy framework we can possibly implement. The framework is built on the principle of empowering all stakeholders.

This talk describes the motivation behind this policy principle and how to uphold it in as harsh an environment as today's Internet. Upholding this principle in the context of Internet realities like malicious participants, limited hardware budgets, and decentralized trust brings many technical challenges. As an existence proof that these challenges can be surmounted, this paper describes the design, implementation in hardware, and evaluation of a concrete architecture that enforces the policy principle.

Title: Putting BGP on the Right Path: A Case for Next-Hop Routing

BGP is plagued by many serious problems (protocol divergence, software bugs, misconfigurations, attacks, and more). Rather than continuing to add mechanisms to an already complex protocol, or redesigning interdomain routing from scratch, we propose making BGP *simpler*. We advocate a transition from today's path-based routing to a solution where ASes select and export routes based only on the neighboring ASes. Next-hop routing leads to simpler router implementation and configuration, and naturally expresses bilateral business relationships. Next-hop routing provably achieves faster convergence and incentive compatibility, side-stepping two major problems with today's BGP. Next-hop routing also allows operators to achieve their traffic-engineering and security goals, and enables multipath routing for additional performance and reliability benefits.

Joint work with Yaping Zhu and Jennifer Rexford

Title: Declarative Techniques for Secure Network Routing

In this talk, I present our recent work on using declarative languages to specify, implement, and analyze secure distributed systems, with a focus on secure routing.. In the first half of the talk, I first describe Secure Network Datalog (SeNDlog), a declarative language that unifies declarative networking and logic-based access control languages. SeNDlog enables network routing, distributed systems, and their security policies to be specified and implemented within a common declarative framework. I will focus on a specific use-case, based on an extensible platform for Application-Aware Anonymity (A3) that we have developed.

Title: Measuring Network Resiliency

"Network resiliency" has been used in common language for many years in a variety of contexts. The intent of the usage seems to always have included the notions that a resilient network is one that continues to deliver services in a satisfactory fashion despite possible disruptions in the network infrastructure and/or one that returns to normal operation quickly after a disturbance. In this talk, we consider the former interpretation in detail. The notion of "satisfactory" obviously involves a matter of degree, so a consistent quantitative framework for network resiliency is proposed for the first interpretation. This talk provides a generalization of the various notions that have been used in the past to describe network resiliency and using this generalization to create a quantitative framework for resiliency characterization. The key concepts are the notions of a network with associated delivery function and of delivery importance. We introduce a network resiliency optimization scheme and briefly show how the network interdiction problem can be solved using the proposed network resiliency framework.