1CS519: Computer NetworksLecture 4, Part 5: Mar 1, 2004Internet Routing:CS519AS’s, igp, and BGP| As we said earlier, the Internet is composed of Autonomous Systems (ASs)z Where each AS is a set of routers, links, and hostsz And is controlled by a single administration (autonomous)z An ISP, a large enterprise (Cornell), etc.CS519AS’s, igp, and BGP| Internally, each AS can run any routing protocol it wantsz “interior gateway protocol”, or igpz Examples: RIP, OSPF, IS-IS| ASs run BGP between themz Border Gateway Protocol| Though many stub ASs don’t run BGP, but simply default to their ISPz The ISP runs BGP “on their behalf”CS519AS’s, igp, and BGP2CS519Border routers run both BGP and the igpCS519Two routing protocols, one FIB?CS519Importing and exporting routes| Routing algorithms have to “originate” routesz Which means that the routing algorithm has to “import” the route in some way other than getting it from a neighbor router| Two ways:z From configuration (iface1 has prefix P . . .)z From another routing algorithm!| Likewise, routing algorithms can “export” routesCS519Importing and exporting routes3CS519Limits to importing and exportingCS519Why this limitation?| Semantic mismatch between BGP and igpz BGP is path-vector, and requires the AS-path to the destination prefixz igp’s don’t require this AS-path, and can’t be expected or forced to carry itz Want to maintain independence between igp and BGP| Also, igp convergence may be slow…CS519iBGP and eBGP (interior and exterior)| BGP avoids dependence on igp by running both between ASs (exterior, eBGP) and within ASs (interior, iBGP)| iBGP runs over TCPCS519iBGP and eBGP (interior and exterior)4CS519iBGP and eBGP (interior and exterior)CS519Next hops are weird in iBGPWhat does it mean for e to have c as its next hop to P1, when there are multiple routers between e and c???CS519One option: tunnel across AS| iBGP speakers form IP tunnels across the ASz IP over IP• (perhaps with GRE between them, but lets not get into this now)z This creates a “link” between the two iBGP speakersz Remember, IP doesn’t care what subnet technology it runs over, even if that subnet is IP!!!CS519iBGP next hop using IP-in-IP tunneling5CS519Another option, use both BGP and igp RIBs| iBGP “resolves” the iBGP next hop to its igp next hopz iBGP computes its next hopz iBGP looks into igp RIB to determine igp next hop to iBGP next hopz This becomes the actual next hop| iBGP must advertise external prefixes into the igpCS519iBGP using igp RIB to resolve next hopCS519BGP security model| Authentication is hop-by-hop, like OSPF| But threat is much worse, because no single organization controls all of BGP| So, BGP uses policy to help prevent bogus routesz BGP routers have an expectation of what they should hear from whereCS519BGP policies| Who to peer with (which ASs)| What routes to originate| What routes to import (prevent bogus advertisements)| What routes to export (and how to aggregate them)| What paths to preferz Shorter AS pathsz Some ASs preferred over others• The big ASs (UUnet, AT&T, etc.)• Primary versus backup transit AS6CS519BGP policy limitation (hop by hop policy decisions)AS1AS3AS2AS4 20.1.0/20AS5AS1 chooses AS2 as the path to 20.1.0/20.AS5 is forced to accept the choice of AS1(If AS5 reallydoesn’t like it, it should find a new peer)CS519BGP policy conflictAS1AS3AS2AS4 20.1.0/20AS5AS5 policy is to prefer route to AS4 via AS2AS1 policy is to prefer route to AS4 via AS3Both policies cannot be satisfiedCS519Hot potato routingAS2AS420.1.0/20AS2 and AS4 policies are to route to nearest AS exit.Asymmetric routes result(not necessarily a problem)30.1.0/20CS519Misconfigured policies may lead to oscillationAS2AS420.1.0/20AS1B2B1AS3B2 configured to prefer AS4B1 configured to prefer AS1AS57CS519Misconfigured policies may lead to oscillationAS2AS420.1.0/20AS1B2B1AS3B2 (periodically) updates AS3 with path AS2,AS4AS5AS2,AS4AS3,AS2,AS4CS519Misconfigured policies may lead to oscillationAS2AS420.1.0/20AS1B2B1AS3B1 (periodically) updates AS3 with path AS2,AS1With each period AS3 advertises a different routeAS5AS2,AS1AS3,AS2,AS1CS519Other route flapping| A link continuously goes up and downz The update for this is propagated throughout the internet| Mid-90’s these kinds of problems were severez 1996: 45,000 prefixes, 1,500 unique AS paths, 1,300 ASs, 3-6 million BGP update messages/day• 6 updates per prefix per hour!• (Labovitz et. al.)CS519Today much improved| Better policy tools| Better software| Lots of damping| But still, advances in BGP lead to new policy bugsz Route reflectors published in 2000 (RFC2796)z Inconsistent route reflectors problem published in 2002 (RFC3345)8CS519Policy Tools| Routing Policy Specification Language (RPSL) (RFC 2280)z Earlier policy languages exist| Language to define BGP policiesz Peers, import, export, route preference, aggregation| Posted at Routing Registries (RIPE, RADB, etc.)| Tools created to look for policy inconsistencies (within AS and across ASs)| Tools created to match measured reality (BGP tables, traceroute) with policy expectationsz RAToolSet, USC/ISICS519Lots of Damping| Stop advertising certain prefixes if they go up and down a lotz Improve stabilityz Lower overhead| RIPE guidelines:z Don’t dampen until after 4thflap in a row (in 50 minutes)z /24: dampen 60 minutesz /22,/23, dampen 30-45 minutesz </22, dampen 10-30 minutesCS519Lots of Damping| Helps the internet, but means that you can go away for a long timez Because of some problem in the middle!| Most damping is done on routes that you don’t care aboutz Poorly managed small ISPs| Routes through major ISPs tend to be very stablez Your favorite web sitesCS519Effect of BGP policies on path quality| Ramesh Govindan study (USC)| Methodology:z Learn real physical topology with traceroutes, deduce actual AS connectivity• Imperfect, but not badz Examine used “policy topology” from BGP tables, RADB (routing registry) databasez Compare the two9CS519Effect of BGP policies on path quality| Results:z About ½ of the paths a longer than shortest pathz 20% of policy paths are 50% or more longerz 20% of policy paths are 5 hops or more longerz Policy tends to push paths through major backbones rather than possibly shorter routes• (But shorter routes may not be better routes!)CS519The InternetThe Internet TodayCS519The InternetThe Internet TodayAs mapped by Skitter (www.caida.org)21 monitors probing ~1M