BGP-lens: patterns and anomalies in internet routing updates

ABSTRACT

The Border Gateway Protocol (BGP) is one of the fundamental computer communication protocols. Monitoring and mining BGP update messages can directly reveal the health and stability of Internet routing. Here we make two contributions: firstly we find patterns in BGP updates, like self-similarity, power-law and lognormal marginals; secondly using these patterns, we find anomalies. Specifically, we develop BGP-lens, an automated BGP updates analysis tool, that has three desirable properties: (a) It is effective, able to identify phenomena that would otherwise go unnoticed, such as a peculiar 'clothesline' behavior or prolonged 'spikes' that last as long as 8 hours; (b) It is scalable, using algorithms are all linear on the number of time-ticks; and (c) It is admin-friendly, giving useful leads for phenomenon of interest.

We showcase the capabilities of BGP-lens by identifying surprising phenomena verified by syadmins, over a massive trace of BGP updates spanning 2 years, from the publicly available site datapository.net.

REFERENCES

• 1: George Edward Pelham Box , Gwilym M. Jenkins, Time Series Analysis: Forecasting and Control, Prentice Hall PTR, Upper Saddle River, NJ, 1994
• 2: Deepayan Chakrabarti , Christos Faloutsos, F4: large-scale automated forecasting using fractals, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584797]
• 3: Ingrid Daubechies, Ten lectures on wavelets, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 4: Christos Faloutsos , M. Ranganathan , Yannis Manolopoulos, Fast subsequence matching in time-series databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.419-429, May 24-27, 1994, Minneapolis, Minnesota, United States
• 5: Anja Feldmann , Olaf Maennel , Z. Morley Mao , Arthur Berger , Bruce Maggs, Locating internet routing instabilities, ACM SIGCOMM Computer Communication Review, v.34 n.4, October 2004
• 6: D. Field. Scale-invariance and self-similar 'wavelet' transforms: an analysis fo natural scenes and mammalian visual systems. In M. Farge, J. Hunt, and J. Vassilicos, editors, Wavelets, Fractals, and Fourier Transforms, pages 151--193. Clarendon Press, Oxford, 1993.
• 7: Thomas Karagiannis , Michalis Faloutsos , Mart Molle, A user-friendly self-similarity analysis tool, ACM SIGCOMM Computer Communication Review, v.33 n.3, July 2003 [doi>10.1145/956993.957004]
• 8: Eamonn Keogh , Kaushik Chakrabarti , Michael Pazzani , Sharad Mehrotra, Locally adaptive dimensionality reduction for indexing large time series databases, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.151-162, May 21-24, 2001, Santa Barbara, California, United States
• 9: Craig Labovitz , G. Robert Malan , Farnam Jahanian, Internet routing instability, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.115-126, September 14-18, 1997, Cannes, France
• 10: C. Labovitz, G. R. Malan, and F. Jahanian. Origins of internet routing instability. Technical Report CSE-TR-368-98, 1998.
• 11: Will E. Leland , Murad S. Taqqu , Walter Willinger , Daniel V. Wilson, On the self-similar nature of Ethernet traffic, Conference proceedings on Communications architectures, protocols and applications, p.183-193, September 13-17, 1993, San Francisco, California, United States
• 12: Olaf Maennel , Anja Feldmann, Realistic BGP traffic for test labs, ACM SIGCOMM Computer Communication Review, v.32 n.4, October 2002
• 13: H. B. N. Feamster, D. Andersen and F. Kaashoek. Bgp monitor - the datapository project, http://www.datapository.net/bgpmon/.
• 14: A. V. Oppenheim and R. W. Schafer. Digital Signal Processing. Prentice-Hall, Englewood Cliffs, N.J., 1975.
• 15: Spiros Papadimitriou , Anthony Brockwell , Christos Faloutsos, Adaptive, hands-off stream mining, Proceedings of the 29th international conference on Very large data bases, p.560-571, September 09-12, 2003, Berlin, Germany
• 16: W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery. Numerical Recipes in C. Cambridge University Press, 2nd edition, 1992.
• 17: Davood Rafiei , Alberto Mendelzon, Similarity-based queries for time series data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.13-25, May 11-15, 1997, Tucson, Arizona, United States
• 18: T. Sauer. Time series prediction using delay coordinate embedding. In A. S. Weigend and N. A. Gershenfeld, editors, Time Series Prediction: Forecasting the Future and Understanding the Past. Addison-Wesley, 1994.
• 19: M. Schroeder. Fractals, Chaos, Power Laws: Minutes from an Infinite Paradise. W.H. Freeman and Company, New York, 1991.
• 20: Claude E. Shannon , Warren Weaver, A Mathematical Theory of Communication, University of Illinois Press, Champaign, IL, 1963
• 21: Lakshminarayanan Subramanian , Matthew Caesar , Cheng Tien Ee , Mark Handley , Morley Mao , Scott Shenker , Ion Stoica, HLP: a next generation inter-domain routing protocol, ACM SIGCOMM Computer Communication Review, v.35 n.4, October 2005
• 22: Soon Tee Teoh , Ke Zhang , Shih-Ming Tseng , Kwan-Liu Ma , S. Felix Wu, Combining visual and automated data mining for near-real-time anomaly detection and analysis in BGP, Proceedings of the 2004 ACM workshop on Visualization and data mining for computer security, October 29-29, 2004, Washington DC, USA [doi>10.1145/1029208.1029215]
• 23: S.-M. Tseng, S. F. Wu, X. Zhao, and K. Zhang. Reverse Engineering the Management Actions from Observed BGP Data. In IEEE Workshop on Automated Network Management, INFOCOM 2008, 2008.
• 24: David Vernon, Machine vision: automated visual inspection and robot vision, Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
• 25: K. Wang and S. Shamma. Spectral shape analysis in the central auditory system. NNSP, Sept. 1993.
• 26: M. Wang, T. Madhyastha, N. H. Chang, S. Papadimitriou, and C. Faloutsos. Data mining meets performance evaluation: Fast algorithms for modeling bursty traffic. ICDE, Feb. 2002.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Measurement, Security

Keywords:
BGP monitoring, anomalies, patterns, self-similarity