NETS-NBD: RIDR: Towards Robust Inter-Domain Routing: Measurements, Models, and Deployable Tools
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
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
- NSF, Award Number: CNS-0721736, Duration:
08/01/2007-07/31/2009 (Expected)
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:
- A macroscopic study of BGP stability using our 'BGP-Lens' tool.
To ground our work, we use real data to understand the macroscopic
behavior of real BGP updates. Using data-mining approaches and
tools, we discover several un-expected facts, which were invisible
by manual inspection and traditional tools.
- CNM (Chaotic Network Model):
An elegant and powerful model of BGP stability. We
propose CNM, a non-linear ('chaotic') model with the intention to
have the simplest possible model with sufficient descriptive power.
Our model brings the full theory of chaos and strange attractors
into attention.
- Identifying fundamental trade-offs: epidemic
threshold. Using CNM, we prove mathematically that the instability
of our network grows with the largest eigenvalue $\lambda_1$ of the
adjacency matrix.
3.3.
Publications
- B. Aditya Prakash, Nicholas Valler, David Andersen, Michalis Faloutsos and Christos Faloutsos-
BGP-lens: Patterns and Anomalies in Internet Routing Updates, (under Review)
- B. Aditya Prakash, Michalis Faloutsos and Christos Faloutsos-
Formalizing the BGP stability problem - patterns and a chaotic model, CMU Tech Report #:CMU-CS-08-165
Last updated: March 08,
2009, by B. Aditya Prakash.