Impact of prefix-match changes on IP reachability

Yaping Zhu, Jennifer L. Rexford, Subhabrata Sen, Aman Shaikh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations


Although most studies of Internet routing treat each IP address block (or prefix) independently, the relationship between prefixes is important because routers ultimately forward packets based on the"longest-matching prefix." In fact, the most-specific prefix for a given destination address may change over time, as BGP routes are announced and withdrawn. Even if the most-specific route is withdrawn, routers may still be able to deliver packets to the destination using a less-specific route. In this paper, we analyze BGP update messages and Netflow traffic traces from a large ISP to characterize both the changes to the longest-matching prefix over time and the resulting effects on end-to-end reachability of the destination hosts. To drive our analysis, we design and implement an efficient online algorithm for tracking changes in the longest-matching prefix for each IP address. We analyze the BGP message traces to identify the reasons for prefix-match changes, including failures, route flapping, sub-prefix hijacking, and load-balancing policies. Our preliminary analysis of the Netflow data suggests that the relationship between BGP updates and IP reachability is sometimes counterintuitive.

Original languageEnglish (US)
Title of host publicationIMC 2009 - Proceedings of the 2009 ACM SIGCOMM Internet Measurement Conference
Number of pages7
StatePublished - Dec 1 2009
Event2009 9th ACM SIGCOMM Internet Measurement Conference, IMC 2009 - Chicago, IL, United States
Duration: Nov 4 2009Nov 6 2009

Publication series

NameProceedings of the ACM SIGCOMM Internet Measurement Conference, IMC


Other2009 9th ACM SIGCOMM Internet Measurement Conference, IMC 2009
CountryUnited States
CityChicago, IL

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Networks and Communications


  • BGP
  • IP reachability
  • Longest-matching prefix

Fingerprint Dive into the research topics of 'Impact of prefix-match changes on IP reachability'. Together they form a unique fingerprint.

Cite this