Locating Internet Instability under Simultaneous Events

Abstract:

Locating internet instability is very important to diagnose internet problems. The existing methods are under the assumption that instability is triggered by only one event, and these methods are not applicable for the scenario of simultaneous events. This paper presents the first study on characterizing the simultaneous events, finding out where the multiple events happened could be visible and how many events are simultaneously happened. Furthermore, a novel scheme is proposed to accurately pinpoint the origins of instability under simultaneous events by exploring cycles, which is theoretically proved to be feasible.

• Periodical: Advanced Engineering Forum (Volume 1)
• Pages: 125-129
• DOI: https://doi.org/10.4028/www.scientific.net/AEF.1.125
• Online since: September 2011
• Authors: Hong Jun Liu, Xiao Feng Hu, Dan Zhao, Xi Cheng Lu
• Keywords: BGP, Instability Origin, Routing Instability, Simultaneous Events

References

[1] Craig Labovitz, G. Robert Malan, Farnam Jahanian, Internet routing instability, IEEE/ACM Transactions on Networks, Vol. 6, No. 5, October (1998).

DOI: 10.1109/90.731185

[2] R. Teixeira and J. Rexford, A Measurement Framework for Pin-Pointing Routing Changes, In Proceedings of ACM SIGCOMM Workshop on Network Troubleshooting, Aug. (2004).

DOI: 10.1145/1016687.1016704

[3] D-Fa Chang, R. Govindan, and J. Heidemann, The temporal and topological characteristics of BGP path changes, in Proc. IEEE International Conference on Network Protocols (ICNP), November (2003).

DOI: 10.1109/icnp.2003.1249770

[4] M. Caesar, L. Subramanian, and R. Katz. Towards localizing root causes of BGP dynamics, Technical Report UCB/CSD-04-1302, U.C. Berkeley, Nov. (2003).

[5] A. Feldmann, O. Maennel, Z. M. Mao, A. Berger, and B. Maggs. Locating Internet routing instabilities, in Proc. ACM SIGCOMM, pages 205–218, Portland, OR, Aug. (2004).

DOI: 10.1145/1030194.1015491

[6] M. Lad, A. Nanavati, D. Massey, and L. Zhang, An algorithmic approach to identifying link failures, in Proc. 10th IEEE Pacific Rim International Symposium on Dependable Computing(PRDDC), March 2004, pp.25-34.

DOI: 10.1109/prdc.2004.1276549

[7] J. Wu, Z. M. Mao, J. Rexford, and J. Wang, Finding a needle in a haystack: Pinpointing significant BGP routing changes in an IP network, in Proc. Networked Systems Design and Implementation (NSDI), May (2005).

[8] M. Lad, R. Oliveira, D. Massey and L. Zhang, Inferring the Origin of Routing Changes using Link Weights, In Proceedings of IEEE ICNP, Oct. (2007).

DOI: 10.1109/icnp.2007.4375840

[9] Y. Huang, N. Feamster, A. Lakhina, and J. Xu. Detecting Network Disruptions with Network-Wide Analysis, in Proc. of ACM SIGMETRICS, (2007).

DOI: 10.1145/1269899.1254890

[10] T. Ogishi, Y. Hei, S. Ano and T. Hasegawa. Empirical Study on Inferring BGP Routing Instability and its Location based on Single Point Observation, ICC (2007).

DOI: 10.1109/icc.2007.30

[11] A. Campisano, L. Cittadini, G. Di Battista, T. Refice, C. Sasso, Tracking Back the Root Cause of a Path Change in Inter-domain Routing, In Proceedings of IEEE/IFIP NOMS, Apr. (2008).

DOI: 10.1109/noms.2008.4575166

[12] Wei Liang, Ye Li, Jingping Bi and Guoqiang Zhang. On the Accurate Identification of Familiar Inter-Domain Routing Instabilities, GLOBECOM (2008).

DOI: 10.1109/glocom.2008.ecp.303

[13] Kuatse, A.M., Teixeira, R., Feamster, N., and Meulle, M. Joint analysis of network incidents and intradomain routing changes, CNSM 2010, pp.198-205.

DOI: 10.1109/cnsm.2010.5691306

[14] M. Watari, A. Tachibana, and S. Ano. Inferring the Origin of Routing Changes based on Preferred Path Changes, PAM (2011).

DOI: 10.1007/978-3-642-19260-9_17

[15] R. Oliveira, B. Zhang, D. Pei, L. Zhang, Quantifying Path Exploration in the Internet, IEEE/ACM Transactions on Networking, vol. 17, no. 2, pp.445-458, Apr. (2009).

DOI: 10.1109/tnet.2009.2016390