Impact of Prefix-Match Changes on IP Reachability Yaping

Impact of Prefix-Match Changes on IP Reachability Yaping Zhu [email protected] with: Jennifer Rexford (Princeton University) Subhabrata Sen and Aman Shaikh (AT&T Labs-Research)

BGP and Prefix-Match Changes BGP updates are based on prefixes An IP address can be covered by multiple prefixes – Caused by prefix nesting: – E.g. IP 128.112.0.0 can be covered by two prefixes: 128.112.0.0/16 and 128.112.0.0/24 Longest prefix-match (LPM) determines forwarding LPM for a given destination IP address may change over time Yaping Zhu, Princeton University 2

Prefix Nesting: Load Balancing and Backup Route IP addresses are allocated hierarchically from registries Providers allocate subnets to their customers Multi-homed customers divide their address block for: – Load balancing (more-specific prefix) – Backup route (less-specific prefix) 15.0.0.0 / 17 15.0.128.0 / 17 15.0.0.0 / 16 (backup) 15.0.0.0 / 16 (backup) Provider A Provider B Customer 15.0.0.0 / 16 Yaping Zhu, Princeton University 3

Prefix Nesting: Protect from Prefix Hijacking Prefix hijacking – Announcement of prefix from an AS that does not own the prefix Protect from prefix hijacking by leveraging LPM /9 – Announce12.0.0.0 more-specific prefixes 12.128.0.0 / 9 12.0.0.0 / 8 12.0.0.0 / 8 Prefix hijacking AT&T Princeton IBM Local ISP Comcast Yaping Zhu, Princeton University 4

Why Study Prefix-Match Changes? Even if the most-specific route is withdrawn – Packets can be delivered using a less-specific route 15.0.0.0 / 17 15.0.128.0 / 17 15.0.0.0 / 16 (backup) 15.0.0.0 / 16 (backup) Provider A Provider B Customer 15.0.0.0 / 16 Yaping Zhu, Princeton University 5

Why Study Prefix-Match Changes? Network troubleshooting – Given an IP packet from specific place at specific time, what is the route it traversed to reach the destination? – Reachability and performance problems along the route – Route determined by LPM and changes to it 128.112.0.0/16 AT&T 128.112.0.0/16 Princeton IBM 128.112.0.0/24 128.112.0.0/24 Local ISP Comcast Yaping Zhu, Princeton University 6

Algorithm: Tracking of Prefix-Match Changes Input: – – – – Start time and end time BGP route table (at start time) BGP updates (from start time to end time) List of IP addresses Output: – LPM changes for all IP addresses over time Example: – – – – For IP addresses 12.0.0.0-12.0.255.255 At start time, LPM /16 At t1 /16 withdrawn, LPM /8 (less-specific) At t2 /16 announcement, LPM /16 (more-specific) Yaping Zhu, Princeton University 7

Algorithm: Tracking of Prefix-Match Changes Scalability challenge Prefix set: all matching prefixes for a given IP address Address range: contiguous addresses that have the same prefix set (and same LPM) Track changes of address ranges and their prefix sets Prefix Set { /8, /16 } { /8 } 12/8 12/16 IPs 12.0.0.0 LPM 12.0.255.255 12.1.0.0 /16 12.255.255.255 /8 Yaping Zhu, Princeton University 8

Static Analysis of Prefix Nesting 24% of IP addresses are covered by multiple prefixes BGP routing table dump collected in Feb 09 2009, 00:00:00 from one Route Reflector in AS 7018 Yaping Zhu, Princeton University 9

Dynamic Analysis of Prefix-Match Changes Category Prefix-match unchanged %Upd Possible Explanations 69.5% Route change New prefix announcement 7.4% Existing prefix withdrawal 7.4% More-specific prefix 6.5% Less-specific prefix 6.5% Gain reachability Lose reachability new customer route, sub-prefix hijacking, route leak Load balancing, failover to backup route BGP updates collected in Feb09 from one Route Reflector in AS 7018 Yaping Zhu, Princeton University 10

Example: Destinations Remain Reachable after a BGP Withdrawal BGP prefix-match changes – The IP addresses change from /20 to /17 prefix for about half an hour on February 18, 2009. – Only analyzing the BGP routes is not enough Joint analysis with Netflow traffic data – The IP address range continued receiving the same amount of traffic – Traffic volume at 5-minutes interval collected using Netflow Destinations remain reachable via less-specific prefix Yaping Zhu, Princeton University 11

Conclusion Understanding the impact of prefix-match changes – IP reachability – Network troubleshooting Algorithm for tracking prefix-match changes Static analysis of prefix nesting – 24% of IP addresses are covered by multiple prefixes Dynamic analysis of prefix-match changes – 13% of BGP updates cause prefix-match changes Yaping Zhu, Princeton University 12

Thanks! Questions? Yaping Zhu, Princeton University 13