NETS-NBD: RIDR: Towards Robust Inter-Domain Routing: Measurements, Models, and Deployable Tools

 
Christos Faloutsos Phone: (412)-268.1457
Department of Computer Science Fax : (412)-268.5576
Carnegie Mellon Univ. Email: christos@cs.cmu.edu
Pittsburgh, PA 15213 WWW page: http://www.cs.cmu.edu/~christos

This material is based upon work supported by the National Science Foundation under Grant No. CNS-0721736. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

1. GENERAL INFORMATION

1.1. Abstract

Link to NSF abstract

Can ten or a hundred compromised BGP routers create Internet-wide instability? How how can we protect against it? BGP routing problems are hard to study, for the following reasons: (a) a lack of complete and accurate BGP topology, (b) difficulty in simulating with regards to computational complexity and accuracy, and (c) difficulty of deploying new tools to improve the BGP security. The goal of this project is exactly to address the above issues, and specifically to measure, model and guard against BGP routing problems. The overarching vision is to provide the foundation for not only improving the current BGP, but also for providing new insight and guidelines for the design of novel inter-domain routing approaches. The work focuses on three related research tasks. In the first task, the work will develop and maintain a relatively complete and accurate BGP topology as an ongoing effort and to generate small realistic topologies for simulations purposes, with provable topological properties. In the second task, the project will use and extend epidemic spreading techniques to model the network-wide propagation of BGP instability. In the third task, the project will develop a comprehensive reactive framework to detect erroneous BGP updates, which could be readily deployed today. Broader Impact. This work is an important step towards a more robust Internet. It is widely feared that the next generation of cyber-attacks could target the control plane. However, even today, BGP routing has its share of vulnerabilities and problems which cost millions of dollars in service disruption.

1.2. Keywords

Data mining, network traffic, BGP stability, time evolution.

1.3. Funding agency

2. PEOPLE INVOLVED

In addition to the PI, the following people work on the project.

3. RESEARCH

3.1. Project goals

The goal of the project is to measure, model and guard against BGP routing problems. Our overarching vision is to provide the foundation for not only improving the current BGP, but also for providing new insight and guidelines for the design of novel inter-domain routing approaches. Our progress spans the proposed tasks. We have developed a series of useful topology models for research studies, and we have developed and explored the dynamics of BGP routing from a fundamental and theoretical point of view. The first proposed task was to develop realistic BGP topologies in order to enable realistic simulations and studies. Second, we address by designing an algorithm to generate small-scale, realistic, and policy-aware topologies. We propose HBR, a network sampling method, which produces topologies that preserve the fundamental properties of the Internet graph, including, in particular, its hierarchical structure. Third, we study and model BGP updates, and we found surprising patterns: prolonged spikes of activity, long intervals of near-constant traffic (~5 updates per minute), and self-similarity. These observations will help us focus our investigations for anomalous behavior.

3.2. Current Results

We worked on studying and modeling the BGP stability. In more detail, the main findings so far are as follows:

3.3. Publications

Last updated: July 12, 2010, by B. Aditya Prakash.