NETS-NBD: RIDR: Towards Robust Inter-Domain Routing: Measurements, Models, and Deployable Tools
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.
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.
Data mining, network traffic, BGP stability, time
- NSF, Award Number: CNS-0721736, Duration:
In addition to the PI, the following people work on
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
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.
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
- 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
- B. Aditya Prakash, Deepayan Chakrabarti, Michalis Faloutsos, Nicholas Valler, Christos Faloutsos "Got the Flu (or Mumps)? Check the Eigenvalue!" arXiv:1004.0060v1 [physics.soc-ph]
- B. Aditya Prakash, Hanghang Tong, Nicholas Valler, Michalis Faloutsos, Christos Faloutsos "Virus Propagation on Time-Varying Networks: Theory and Immunization Algorithms" in ECML-PKDD 2010, Barcelona
- Lei Li, B. Aditya Prakash, Christos Faloutsos "Parsimonious Linear Fingerprinting for Time Series" in VLDB 2010, Singapore
- B. Aditya Prakash, Ashwin Sridharan, Mukund Seshadri, Sridhar Machiraju, Christos Faloutsos "EigenSpokes: Surprising Patterns and Scalable Community Chipping in Large Graphs" in PAKDD 2010, Hyderabad
- B. Aditya Prakash, Nicholas Valler, David Andersen, Michalis Faloutsos and Christos Faloutsos-
"BGP-lens: Patterns and Anomalies in Internet Routing Updates", in SIGKDD 2009, Paris
- 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: July 12,
2010, by B. Aditya Prakash.