Project ID:
RFP-2007-026
Title:
Explanation of BGP Update "Background Noise" and "Spikes" in the Internet
Summary:
Many network operators, equipment vendors and researchers have been concerned about the alarming rates of BGP updates and their potential to destabilize the Internet routing infrastructure and increase both the design complexities and cost of next-generation routers [1]. There is little understanding of the root cause of either the constant churn or the "spikes" of BGP updates seen on the Internet. Thus, there is no clear solution to follow to help alleviate the burden of peering in the internet backbone. This RFP seeks research to improve understanding of BGP update dynamics.
Full Description:
There have been many presentations and papers written that BGP operators have to suffer with unnecessary BGP messages, carrying unnecessary transit state (too many prefixes) and therefore that routers are overburdened if not failing in the Internet. What is missing in current literature is a root-cause analysis from more than one Internet mensuration point on the origin of the churn or spikes in BGP update packets. Churn has both routine and pathological components; spikes always result from some pathological or catastrophic event.
Unnecessary BGP update packets are generally considered harmful for a variety of reasons. Within a single AS, BGP updates may trigger routing reconvergence resulting in packet delay variations or losses. In addition, a high volume of BGP updates may cause shifts in traffic patterns across a network backbone when the next-hop BGP attribute changes. Across AS boundaries there may be "disconnections" from large parts of the Internet or massive traffic oscillations or use of less preferred paths.
The churn or noise may be due to a variety of reasons: route oscillations from protocol limitations, failure events, poor implementations of BGP, aspath prepending changes for multihoming and a plethora of others. In general, there is little in the literature that explains events or offers anything in the way of "event signatures."
There have been many attempts to model BGP update dynamics, e.g. [2][3][4]. All are based on observations taken at a single measurement point in the Internet. An open problem is the development of multivariate models of BGP updates, i.e., models based on synchronous observations taken at two or more physically separate points in the Internet.
Examples of research under this RFP include
- Methodology for capturing multivariate BGP data across the internet.
- Development of multivariate models of BGP updates.
- Using BGP probes to define and validate event signatures.
- Observing a failure event and measuring impact on the subsequent BGP update transmissions around the Internet.
References
[1] : RFC4984
[2] : Modeling BGP Table Fluctuations, Ashley Flavel, Matthew Roughan, Nigel Bean and Olaf Maennel, School of Mathematical Sciences, University of Adelaide, pp 141-153 in Managing Traffic Performance in Converged Networks, Springer Verlag 2007
[3] : Link-Rank: a graphical tool for capturing BGP routing dynamics, Lad, M.; Lixia Zhang; Massey, D. IEEE Network Operations and Management Symposium, 2004.
[4] : ON/OFF Model: A New Tool to Understand BGP Update Bursts, X. Zhao, D. Massey, M. Lad, and L. Zhang, USC-CSD Technical Report 04-819, August 2004
Constraints and other information:
IPR will stay with the University. Cisco expects customary scholarly dissemination of results, and hopes that promising results would made available to the community without limiting licenses, royalties, or other encumbrances.
Proposal submission:
Please use the link below to submit a proposal for research responding to this RFP. After a preliminary review, we may ask you to revise and resubmit your proposal.
Create/submit a proposal for this RFP
RFPs may be withdrawn as research proposals are funded, or interest in the specific topic is satisfied. Researchers should plan to submit their proposals as soon as possible. Submissions-to-date are reviewed at the beginning of each calendar quarter.
Questions? Contact: research@cisco.com
