Impact of prefix-match changes on IP reachability

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.