GIRO: Geographically Informed Inter-domain RoutingInternet and Autonomous SystemsWhat problem we are solvingOne ExampleSuboptimal route selection !PowerPoint PresentationGIRO Design GoalsGIRO Design ApproachAdding geographic informationGIRO Address SchemePrefix Aggregation in GIROEgress Point SelectionGIRO Decision ProcessEvaluation: Inter-domain route selectionEvaluation: GIRO aggregationGIRO AggregationEvaluation: GIRO AggregationIncremental deployment?But we can do this!Conclusion and future workQuestions? [email protected] shortest-path policy cost more locally?Slide 23Slide 24Slide 25Inremental deployment?1GIRO: Geographically Informed Inter-domain RoutingRicardo Oliveira, Mohit Lad, Beichuan Zhang, Lixia Zhang2Internet and Autonomous SystemsAT&TSprintVerizon•Autonomous System: a set of routers or networks under the same administration•Border routers exchange routing updates via the Border Gateway Protocol (BGP)•Reachability announced through the form of prefixes, i.e. chunks of IP addresses24.143.92/243?rarbrcPrefix P1. Policy: costumers > peers > providers2. Lowest AS hop count3. …What problem we are solving•BGP route selection: how to pick the best one?4One Example •Router A sends packets to prefix P•A has two ways to reach P:•Both AS 577 and AS 3561 are peer links•Following "lowest AS hop" rule: A sends packets to AS 577P: AS 3561, AS 577P: AS 5775Suboptimal route selection !AS3561AS577AS6461Seattle, WAPalo Alto, CAChicago, ILABGP path (~ 3600 miles)Shorter path (~700 miles)P67GIRO Design GoalsGeographical information1. Improve data delivery performance within established routing policies2. Improve routing scalability by reducing the global routing table size8GIRO Design Approach•Adding geographic information into–Routers–BGP routes–IP address •When everything else being equal: select path with shortest distance•Aggregate route announcements by ASes and locations9Adding geographic information•Configure each BGP router with geographic location informaiton•Define a new BGP "location" attribute to be associated with each AS hop e.g. using BGP communities•Enables each router to calculate the total path lengthxinC, yinCCBAxoutB, youtBxinB, yinBxoutA, youtAxorigin, yorigin10GIRO Address SchemeASN geolocation SID Subnet and hostExternal component(G-prefix)Internal component• Including ASN upfront in the address ensures that pkts are routedprimarily based on policies• Geolocation information serves as secondary hint• Traffic slice (SID) divides the incoming traffic to the G-prefix, e.g.one SID per provider• The internal component is not announced to other networks; it’s used to route pkts inside the origin network11DPrefix Aggregation in GIROAECBLos Angeles,CASan Francisco,CAChicago,ILToronto,CANNew York,NYSID=0SID=1G-prefix ASPATHB.US.CA A BB.US.IL A D BB. CAN A D BC.US.NY.NewYork.0 A CC.US.NY.NewYork.1 A D C12Egress Point SelectionlateR1R6R2R3R5R7R0100|12AB50|530|330|390|10earlyshortest-path2000 040|5Geographic distanceIGP weightlate-exitR413GIRO Decision ProcessStep Description1. Highest LocalPref2. Shortest geographic distance w/ resolution 3. Lowest AS hop count4. Lowest origin type5. Early exit (take route of shortest IGP distance)Late-exit (take lowest MED route)Shortest-path (take routes of shortest geographic distance)6. .......14• 70% of paths areshorter using GIRO compared to BGP• 20% of paths arereduced by more than 40%Evaluation: Inter-domain route selection• Used a RocketFuel PoP level topology with 668 inter-AS links and 67 ISPs• For simulations used  =124 miles (equivalent of one sec. delay on fiber)15Evaluation: GIRO aggregation•Extracted prefixes from BGP tables from Jan 2007-March 2007•Mapped each prefix to a geographical location using Maxmind Geolite–Found mapping for ~80% of prefixes (~196K)16GIRO Aggregation•Geographical aggregation: aggregate all the prefixes that originated from the same origin AS and the same geolocation–Do not aggregate prefixes with different AS paths! –Preserve BGP AS path diversity17Evaluation: GIRO Aggregation• GIRO achieves a 75% table size reduction compared to BGP18Incremental deployment?•We do not have this:ASN geolocation SID Subnet and host• Would need IPv6 bits to fit it all in address field …19–Configure each BGP router with geographic location informaiton–Define a new BGP "location" attribute to be associated with each AS hop (by usingcommunities)–Enables each router to calculate the total path lengthxinC, yinCCBAxoutB, youtBxinB, yinBxoutA, youtAxorigin, yoriginBut we can do this!20Conclusion and future work•Geolocation information can help improve path selection under routing policy constraints•Embedding ASN and geographical information in IP address can help improve routing scalability through aggregation•Exploring the possibility of utilizing geolocation in BGP routing, moving forward w/ an I-D very soon…[email protected] shortest-path policy cost more locally?• Comparison between early-exit, late-exit, and shortest-path policy • Shortest-path policy can reduce global cost significantly withoutsacrificing much of local cost Global cost(geographical distance)Local cost2324Internet and Autonomous SystemsAT&TSprintVerizon•Autonomous System: a set of routers or networks under the same administration•Border routers exchange routing updates via the Border Gateway Protocol (BGP)•Reachability announced through the form of prefixes, i.e. chunks of IP addresses24.143.92/2425Evaluation: GIRO Aggregation• GIRO achieves a 75% tablesize reduction compared to BGP• About 40% of GIRO entries resulted from topological aggregation• 60% of entries resulted from geographical aggregation26Inremental deployment?•Incremental deployability of GIRO:–Can embedd geographic info into BGP communities•What information to include in routes: absolute location or relative distance?–ISPs want to disclose minimal info about their networks–Geolocation info can help in doing fault diagnosis•GIRO can also help in:–Prefix hijacking: prefix ownership problem is solved; false link attacks can be mitigated–Source address spoofing, if border routers at origin net stamp (some) data pkts with their