Randy's Work Blog

Thomas Holterbach, Emile Aben, Cristel Pelsser, Randy Bush, & Laurent Vanbever; Measurement Vantage Point Selection Using A Similarity Metric; Applied Networking Research Workshop (ANRW 2017)

In a measurement platform with a wide selection of vantage points, it can be challenging to select the most appropriate points to source measurements from. One example of such platform is RIPE Atlas [2] which currently hosts over 9600 active vantage points, which can be selected based on categories, such as origin AS or country. When setting up a measurement, users are limited in how many vantage points they can use. This is not only due to limitations that the mea- surement platform imposes, but collecting data from a large number of vantage points would mean a large volume to analyse and store. It therefore makes sense to optimize for a minimal set of vantage points with a maximum chance of observing the phenomenon in which the user is interested.

Network operators may need to debug a network service with only limited information about the problem (“Our network is slow for users in France!”). A diversity metric would allow selection of the most dissimilar vantage points, in an attempt to explore the network phenomenon from as diverse angles as possible. If one nds an interesting network phenomenon, one could use the similarity metric to advantage by selecting the most similar vantage points to the one exhibiting the phenomenon, in an attempt to validate the phenomenon from multiple vantage points.

We propose a novel means of selecting vantage points, which is not based on categorical properties (such as origin AS, or geo- graphic location), but rather on the topological (dis)similarity be- tween vantage points. We describe a similarity metric across RIPE Atlas probes, and show how this performs better for the purpose of topology discovery than the default probe selection mechanism built into RIPE Atlas.

Anant Shah, Romain Fontugne, Emile Aben, Cristel Pelsser, and Randy Bush; Disco: Fast, Good, and Cheap Outage Detection TMA 2017

Outage detection has been studied from different angles, such as active probing, analysis of background radiations, or control plane information. We approach outage detection from a new perspective. Disco is a detection technique that uses existing long-running TCP connections to identify bursts of disconnections. The benefits are considerable as we can monitor, without adding a single packet to the traffic, Internet-wide swaths of infrastructure that were not monitored previously because they are, for example, not responsive to ICMP probes or behind NATs. With Disco we analyze state changes on connections between RIPE Atlas probes and the RIPE Atlas infrastructure. This data, that is originally logged to monitor probe availability, has a small footprint and is available as a publicly accessible live stream, which makes light-weight near real-time outage detec- tion possible. Probes perform planned traceroute measurements regardless of their connectivity to the RIPE Atlas infrastructure. This gives us a no cost advantage of viewing the outage inside out as the probes experienced it, characterizing the outage after the fact. Thus, we present an outage detection system able to run in near real-time (fast), with a precision of 95% (good), and without generating any new measurement traffic (cheap). We studied historical probe disconnections from 2011 to 2016 and report on the 443 most prominent outages. To validate our results we inspected traceroute results from affected probes and compared our detection to that of Trinocular.

        RFC 8097

        Title:      BGP Prefix Origin Validation State 
                    Extended Community 
        Author:     P. Mohapatra, 
                    K. Patel,
                    J. Scudder, 
                    D. Ward,
                    R. Bush
        Status:     Standards Track
        Stream:     IETF
        Date:       March 2017
        Mailbox:    mpradosh@yahoo.com, 
                    keyur@arrcus.com, 
                    jgs@juniper.net,  
                    dward@cisco.com, 
                    randy@psg.com
        Pages:      6
        Characters: 12287
        Updates/Obsoletes/SeeAlso:   None

        I-D Tag:    draft-ietf-sidr-origin-validation-signaling-11.txt

        URL:        https://www.rfc-editor.org/info/rfc8097

        DOI:        10.17487/RFC8097

This document defines a new BGP opaque extended community to carry
the origination Autonomous System (AS) validation state inside an
autonomous system.  Internal BGP (IBGP) speakers that receive this
validation state can configure local policies that allow it to
influence their decision process.

A Multi-perspective Analysis of Carrier-Grade NAT Deployment
Philipp Richter, Florian Wohlfart, Narseo Vallina-Rodriguez, Mark Allman, Randy Bush, Anja Feldmann, Christian Kreibich, Nicholas Weaver, Vern Paxson
IMC 2016

Awarded ANRP Prize 2017

What do parrots and BGP routers have in common?
David Hauweele, Bruno Quoitin, Cristel Pelsser, Randy Bush
Computer Communication Review, July 2016
[ CCR’s first all-online-only issue ]

The Border Gateway Protocol propagates routing informa- tion accross the Internet in an incremental manner. It only advertises to its peers changes in routing. However, as early as 1998, observations have been made of BGP announcing the same route multiple times, causing router CPU load, memory usage and convergence time higher than expected.

In this paper, by performing controlled experiments, we pinpoint multiple causes of duplicates, ranging from the lack of full RIB-Outs to the discrete processing of update mes- sages. To mitigate these duplicates, we insert a cache at the output of the routers. We test it on public BGP traces and discuss the relation of the cache performance with the existence of bursts of updates in the trace.

The Origin of BGP Duplicates
D. Hauweele, B. Quoitin, C. Pelsser, R. Bush
CoRes 2016

The Border Gateway Protocol propagates routing information accross the Internet in an incremental manner. It only advertises to its peers changes in routing. However, as early as 1998, observations have been made of BGP announcing the same route multiple times, causing router CPU load, memory usage and convergence time higher than expected. In this paper, by performing controlled experiments, we pinpoint multiple causes of duplicates, ranging from the lack of full RIB-Outs to the discrete processing of update messages.

Thomas Holterbach, Cristel Pelsser, Randy Bush, Laurent Vanbever; Quantifying Interference between Measurements on the RIPE Atlas Platform, 2015 ACM Internet Measurement Conference.

Public measurement platforms composed of low-end hardware devices such as RIPE Atlas have gained significant traction in the research community. Such platforms are indeed particularly interesting as they provide Internet-wide measurement capabilities together with an ever growing set of measurement tools. To be scalable though, they allow for concurrent measurements between users. This paper answers a fundamental question for any platform user: Do measurements launched by others impact my results? If so, what can I do about it?

We measured the impact of multiple users running experiments in parallel on the RIPE Atlas platform. We found that overlapping measurements do interfere with each other in at least two ways. First, we show that measurements performed from and towards the platform can significantly in- crease timings reported by the probe. We found that increasing hardware CPU greatly helped in limiting interference on the measured timings. Second, we show that measurement campaigns can end up completely out-of-synch (by up to one hour), due to concurrent loads. In contrast to precision, we found that better hardware does not help.

Codification of AS 0 Processing
W. Kumari, R. Bush, H. Schiller, K. Patel. August 2015

This document updates RFC 4271 and proscribes the use of Autonomous System (AS) 0 in the Border Gateway Protocol (BGP) OPEN, AS_PATH, AS4_PATH, AGGREGATOR, and AS4_AGGREGATOR attributes in the BGP UPDATE message.

Philipp Richter, Mark Allman, Randy Bush, Vern Paxson. A Primer on IPv4 Scarcity, ACM SIGCOMM Computer Communication Review April 2015. Invited paper at SIGCOMM 2015. Not peer reviewed.

With the ongoing exhaustion of free address pools at the registries serving the global demand for IPv4 address space, scarcity has become reality. Networks in need of address space can no longer get more address allocations from their respective registries.

In this work we frame the fundamentals of the IPv4 address exhaustion phenomena and connected issues. We elaborate on how the current ecosystem of IPv4 address space has evolved since the standardization of IPv4, leading to the rather complex and opaque scenario we face today. We outline the evolution in address space management as well as address space use patterns, identifying key factors of the scarcity issues. We characterize the possible solution space to overcome these issues and open the perspective of address blocks as virtual resources, which involves issues such as differentiation between address blocks, the need for resource certification, and issues arising when transferring address space between networks.

Daniele Iamartino, Cristel Pelsser, Randy Bush. Measuring BGP Route Origin Registration and Validation, PAM 2015.

BGP, the de-facto inter-domain routing protocol, was designed without considering security. Recently, network operators have experienced hijacks of their network prefixes, often due to BGP misconfiguration by other operators, sometimes maliciously. In order to address this, prefix origin validation, based on a RPKI infrastructure, was proposed and developed. Today, many organizations are registering their data in the RPKI to protect their prefixes from accidental mis-origination. However, some organizations submit incorrect information to the RPKI repositories or announce prefixes that do not exactly match what they registered. Also, the RPKI repositories of Internet registries are not operationally reliable. The aim of this work is to reveal these problems via measurement. We show how important they are, try to understand the main causes of errors, and explore possible solutions. In this longitudinal study, we see the impact of a policy which discards route announcements with invalid origins would have on the routing table, and to a lesser extent on the traffic at the edge of a large research network.