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 - 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
Country/TerritoryUnited States
CityChicago, IL

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Networks and Communications


  • BGP
  • IP reachability
  • Longest-matching prefix


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

Cite this