Geographic Locality of IP PrefixesMythili VutukuruJoint work withMichael J. Freedman, Nick Feamster and Hari BalakrishnanInternet Measurement Conference ‘05MotivationACB10.0.0.0/16 Autonomous Systems (ASes) IP Prefixes in BGP messages “Routing handles” Granularity of routing handle –tradeoff between routing table size and ability to control traffic Is prefix the right granularity?Too fine-grained?ABXXX10.1.0.0/1610.3.0.0/1610.5.0.0/16X10.1/1610.3/1610.5/16 Discontiguous prefixes from same location Likely to share fate Multiple routing table entries to be updates Close in geography, far in IP space fine-grainedToo coarse-grained?ABC10.0/1610.1/1610.0/1510.0/1510.0/1610.1/16B aggregatesB does not aggregate Contiguous prefixes from different locations Aggregate less control over traffic Artificially inflates “opportunities” for aggregation Close in IP space, far geographically coarse-grainedQuestions we investigateIP space Geography GranularityFar Close Fine-grainedClose Far Coarse-grainedHow often do ASes announce discontiguous prefixes from same location? How often do ASes announce contiguous prefixes from different locations?Correlation - locality in IP space & geographic localityMajor FindingsDiscontiguous prefixes, close geographically 70% of discontiguous prefix pairs Fragmented allocation to fate-sharing entities Contiguous prefixes, far geographically 25% of contiguous prefix pairs Unsuitable to express traffic control policyMethodCoralCDN[1]Web clients Content serversRandom IPsIPsundns[2]DNS namesLocation(city)Routeviews[3]GOAL: Associate an IP prefix with a set of locations (cities)[1] http://www.coralcdn.org[2] http://www.scriptroute.org[3] http://www.routeviews.orgTracerouteIP PrefixUses naming conventions of routers –city names embedded in DNS namesX XPrefixes too fine-grained70% of discontiguousprefixes have same location65% due to fragmented allocation Analyzed top 20 <AS, location> pairs 23% of them allocated on the same dayImplications Renumber? Change granularity of routing?? Eg: PoP levelAB10.1.0.0/1610.3.0.0/1610.5.0.0/1610.1/1610.3/1610.5/16<A,location><A,location>Prefixes too coarse grained25% of contiguous prefixes - different location CIDR Report[4] Same AS path + close geographically[4] http://www.cidr-report.org10.0/16 A B C D10.1/16 A B C D10.0/15 A B C DPrefix AS Path64% reductionPrefix AS Path Location10.0/15 A B C D L110.0/16 A B C D L110.1/16 A B C D L120% reductionImplicationsPotential for aggregation over-stated Aggregate too coarse grained – poor traffic controlTake-home lessonsIs prefix the right granularity for routing? Prefix too fine-grained Discontiguous prefixes from same location Causes many routing table updates Change routing granularity: group by shared fate? Prefix too coarse-grained Contiguous prefixes from different locations Potential for aggregation is overstated Aggregate prefix unfit for traffic
or
We will never post anything without your permission.
Don't have an account? Sign up