Locating BGP missing routes using multiple perspectives

ABSTRACT

There have been many studies on measuring and interpreting inter-domain routing dynamics. Most of them, however, are based on the approach of off-line and passive post-processing BGP routing updates. We propose a new methodology that uses real-time and active monitoring to troubleshoot various BGP routing anomalies. This paper focuses on a specific BGP routing problem -- missing routes that occur when some ASes can reach a prefix while others can't. The idea is to periodically monitor the BGP routing status at multiple vantage points, like Route Views, and when a possible missing route event is detected issue traceroute queries from various looking glasses to learn of the packet-forwarding path status. By comparing previous and current packet-forwarding paths, we can have an idea of where the missing route event takes place. This paper examines the plausibility of this methodology and discusses preliminary experimental results.

REFERENCES

• 1: Anindya Basu , Chih-Hao Luke Ong , April Rasala , F. Bruce Shepherd , Gordon Wilfong, Route oscillations in I-BGP with route reflection, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 2: M. Caesar, L. Subramanian, and R. H. Katz. Root cause analysis of Internet routing dynamics. Technical Report UCB/CSD-04-1302, University of California, Berkeley, 2003.
• 3: Di-Fa Chang , Ramesh Govindan , John Heidemann, The Temporal and Topological Characteristics of BGP Path Changes, Proceedings of the 11th IEEE International Conference on Network Protocols, p.190, November 04-07, 2003
• 4: Anja Feldmann , Olaf Maennel , Z. Morley Mao , Arthur Berger , Bruce Maggs, Locating internet routing instabilities, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 5: T. G. Griffin. What is the sound of one route flapping. In IPAM Workshop on Large-Scale Communication Networks: Topology, Routing, Traffic, and Control, Mar. 2002.
• 6: Timothy G. Griffin , F. Bruce Shepherd , Gordon Wilfong, The stable paths problem and interdomain routing, IEEE/ACM Transactions on Networking (TON), v.10 n.2, April 2002
• 7: Timothy Griffin , Gordon T. Wilfong, Analysis of the MED Oscillation Problem in BGP, Proceedings of the 10th IEEE International Conference on Network Protocols, p.90-99, November 12-15, 2002
• 8: C. Labovitz and A. Ahuja. Shining light on dark Internet address space. In NANOG 23, Oct. 2001.
• 9: Zhuoqing Morley Mao , Ramesh Govindan , George Varghese , Randy H. Katz, Route flap damping exacerbates internet routing convergence, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 10: Z. Mao, D. Johnson, J. Rexford, J. Wang, and R. H. Katz. Scalable and accurate identification of AS-level forwarding paths. In Proceedings of the IEEE INFOCOM, Mar. 2004.
• 11: P. Smith. Troubleshooting BGP. In NANOG 29, Oct. 2003.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network monitoring

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques

General Terms:
Measurement, Performance

Keywords:
BGP, inter-domain routing, missing route