Transcript ppt
Wen Xu and Jennifer Rexford Department of Computer Science Princeton University Chuck Short CS622 Dr. C. Edward Chow 4/1/2016 CS622 - MIRO Presentation 1 Autonomous System (AS) Border Gateway Protocol (BGP) Internet Service Provider (ISP) 4/1/2016 CS622 - MIRO Presentation 2 Single route advertisement is not flexible enough BGP is sufficient for most traffic Control over path properties rather than complete path is desirable Intermediate router may be willing direct traffic along another path Current methods for influencing path choices are limited 4/1/2016 CS622 - MIRO Presentation 3 BGP Source Routing Single best path selection End to end path selection Overlay Networks 4/1/2016 Virtual network topology CS622 - MIRO Presentation 4 4/1/2016 CS622 - MIRO Presentation 5 4/1/2016 CS622 - MIRO Presentation 6 4/1/2016 CS622 - MIRO Presentation 7 Extension of BGP AS-Level path selection Negotiation for alternate routes Policy driven export of alternate routes Tunnels to direct traffic on alternate routes 4/1/2016 CS622 - MIRO Presentation 8 4/1/2016 CS622 - MIRO Presentation 9 4/1/2016 CS622 - MIRO Presentation 10 Intra-AS Architecture Data Plane Packet Encapsulation AS may consist of many internal routers and paths IP over IP encapsulation Control Plane Tunnel Management 4/1/2016 Creation and destruction of tunnels based upon negotiation CS622 - MIRO Presentation 11 • • • • • Simulated operating environment Infer AS relationships Assume each AS selects and exports routes based on business relationships Each AS treated as one node GAO Algorithm – • L. Gao, “On inferring Autonomous System relationships in the Internet,” IEEE/ACM Trans. Networking, vol. 9, no. 6, pp. 733–745, 2001. Data (October 2000, 2003, 2005) – 4/1/2016 www.routeviews.org CS622 - MIRO Presentation 12 4/1/2016 CS622 - MIRO Presentation 13 Strict Policy Respect Export Policy Responding AS announces routes with same local preference as the original default route Responding AS announces alternate routes using an export policy Most Flexible Policy 4/1/2016 Responding AS announces all possible routes CS622 - MIRO Presentation 14 1) 1-hop set 2) Path set AS negotiates with each immediate neighbor AS negotiates with any AS along BGP path 300 million (source,destination) pairs evaluated 4/1/2016 CS622 - MIRO Presentation 15 4/1/2016 CS622 - MIRO Presentation 16 Avoid for security or performance reasons Calculate triple for every (Source, Destination, AS to avoid) Don’t avoid immediate neighbors 4/1/2016 CS622 - MIRO Presentation 17 4/1/2016 CS622 - MIRO Presentation 18 4/1/2016 CS622 - MIRO Presentation 19 Assumptions Each source generates equal traffic Total traffic estimated by number of sources using link All traffic sent through an intermediate AS always transits through that AS Total traffic a single AS can move if switched to a different route Power node concept 4/1/2016 Node lies on destination path for many sources CS622 - MIRO Presentation 20 4/1/2016 CS622 - MIRO Presentation 21 10,383 multi-homed AS studied Around 90% can move 10% of traffic 50% can move 4/1/2016 40% of traffic under flexible policy 25% of traffic under strict policy CS622 - MIRO Presentation 22 90% of Power Nodes had 200+ neighbors Most likely Tier 1 AS Immediate neighbors only constitute 9% of Power Nodes 68% of Power Nodes are 2 hops away 4/1/2016 CS622 - MIRO Presentation 23 Need negotiation rules Establish and manages negotiation process Need route selection rules 4/1/2016 Filter and rank available alternatives CS622 - MIRO Presentation 24 Potential for oscillation Solution: 4/1/2016 If upstream AS does not advertise the tunnel MIRO is guaranteed to converge whenever BGP converges CS622 - MIRO Presentation 25 MIRO is backward compatible with BGP MIRO can provide the flexibility to negotiate alternate routes as needed MIRO can provide transit AS more control over traffic across their network MIRO is comparable to Source Routing at avoiding an intermediate AS Most alternate route possibilities are provided by the most connected nodes (ISP’s) 4/1/2016 CS622 - MIRO Presentation 26 Build prototype Explore security via AS trust relationships Devise centralized load balancing scheme to prevent oscillation Explore the incorporation of price, performance and load information into the route selection process 4/1/2016 CS622 - MIRO Presentation 27 4/1/2016 CS622 - MIRO Presentation 28 Border Gateway Protocol (BGP) 4/1/2016 http://www.rfc-editor.org/rfc/rfc4271.txt CS622 - MIRO Presentation 29