Exterior Gateway Protocols: EGP, BGP-4, CIDR

Exterior Gateway Protocols:EGP, BGP-4, CIDRShivkumar KalyanaramanRensselaer Polytechnic edu/Homepages/shivkumaBased in part upon slides of Tim Griffin (AT&T), Ion Stoica (UCB), J. Kurose (U Mass), Noel Chiappa(MIT)Shivkumar KalyanaramanRensselaer Polytechnic Institute1

Overview Cores, Peers, and the limit of default routesAutonomous systems & EGPBGP4CIDR: reducing router table sizesRefs: Chap 10,14,15. Books: “Routing in Internet” by Huitema, “Interconnections” byPerlman, “BGP4” by Stewart, Sam Halabi, Danny McPherson, Internet RoutingArchitecturesReading: Geoff Huston, Commentary on Inter-domain Routing in the InternetReference: BGP-4 Standards Document: In TXTReading: Norton, Internet Service Providers and PeeringReading: Labovitz et al, Delayed Internet Routing ConvergenceReference: Paxson, End-to-End Routing Behavior in the Internet,Reading: Interdomain Routing: Additional Notes: In PDF In MS WordReference Site: Griffin, Interdomain Routing LinksShivkumar Kalyanaraman Rensselaer Polytechnic Institute2

History: Default Routes: limitsDefault routes partial information Routers/hosts w/ default routes rely on otherrouters to complete the picture. In general routing “signposts” should be: Consistent, I.e., if packet is sent off in onedirection then another direction should not bemore optimal. Complete, I.e., should be able to reach alldestinations Shivkumar KalyanaramanRensselaer Polytechnic Institute3

CoreA small set of routers that have consistent &complete information about all destinations. Outlying routers can have partial informationprovided they point default routes to the core Partial info allows site administrators to makelocal routing changes independently. CORES1.S2SmShivkumar KalyanaramanRensselaer Polytechnic Institute4

Peer BackbonesInitially NSFNET had only one connection toARPANET (router in Pittsburg) only one routebetween the two. Addition of multiple interconnections multiplepossible routes need for dynamic routing Single core replaced by a network of peerbackbones more scalable Today there are over 30 backbones! Routing protocol at cores/peers: GGP - EGP- BGP-4 Shivkumar KalyanaramanRensselaer Polytechnic Institute5

Exterior Gateway Protocol (EGP)A mechanism that allows non-core routers tolearn routes from core (external routes) routersso that they can choose optimal backbone routes A mechanism for non-core routers to inform corerouters about hidden networks (internal routes) Autonomous System (AS) has the responsibilityof advertising reachability info to other ASs. One routers may be designated per AS. Important that reachability info propagates tocore routers Shivkumar KalyanaramanRensselaer Polytechnic Institute6

Purpose of EGPyou can reachnet A via meEGPAS1traffic to AAS2R3R2R1Atable at R1:dest next hopAR2Rborder routerinternal routerKalyanaramanShare connectivity informationShivkumaracrossASesRensselaer Polytechnic Institute7

EGP Operation Neighbor Acquisition: Reliable 2-way handshakeNeighbor Reachability: Hellos: j out of m hellos OK Neighbor UP k out of n hellos NOT OK Neighbor DOWNUpdates/Queries: EGP is an incremental protocol. New info sendupdates Each router can query neighbors as well Reachability advertized; metrics ignored Requires a tree topology of ASes to avoid loops (eg:see next slide)Shivkumar KalyanaramanRensselaer Polytechnic Institute8

Why EGP Requires a Tree Structure.Shivkumar KalyanaramanRensselaer Polytechnic Institute9

EGP weaknesses EGP does not interpret the distance metrics inrouting update messages cannot be computeshorter of two routes As a result it restricts the topology to a treestructure, with the core as the root Rapid growth many networks may betemporarily unreachable Only one path to destination no loadsharing Need new protocol BGP-4Shivkumar KalyanaramanRensselaer Polytechnic Institute10

Today’s Big PictureLarge ISPLarge ISPStubSmall ISPDial-UpISPStubAccessNetworkStubLarge number of diverse networksRensselaer Polytechnic Institute11Shivkumar Kalyanaraman

Internet AS Map: caida.orgShivkumar KalyanaramanRensselaer Polytechnic Institute12

Autonomous System(AS)Internet is not a single network Collection of networks controlled by differentadministrations An autonomous system is a network under asingle administrative control An AS owns an IP prefix Every AS has a unique AS number ASes need to inter-network themselves to forma single virtual global network Need a common protocol for communication Shivkumar KalyanaramanRensselaer Polytechnic Institute13

Intra-AS and Inter-AS routingC.bA.aaCGateways:B.abdAA.caabccBb perform inter-ASrouting amongstthemselves perform intra-ASrouters with otherrouters in their ASnetwork layerinter-AS,intra-ASrouting ingateway A.clink layerphysical layerShivkumar KalyanaramanRensselaer Polytechnic Institute14

Who speaks Inter-AS routing?AS2BGPAS1R2R3R1Rborder routerinternal router Two types of routers Border router(Edge), Internal router(Core) Two border routers of different ASes will have a BGPShivkumar KalyanaramanRensselaersessionPolytechnic Institute15

Intra-AS vs Inter-AS An AS is a routing domainWithin an AS: Can run a link-state routing protocol Trust other routers Scale of network is relatively smallBetween ASes: Lack of information about other AS’s network (Linkstate not possible) Crossing trust boundaries Link-state protocol will not scale Routing protocol based on route propagationShivkumar KalyanaramanRensselaer Polytechnic Institute16

Autonomous Systems (ASes)An autonomous system is an autonomous routingdomain that has been assigned an Autonomous SystemNumber (ASN). All parts within an AS remain connected. the administration of an AS appears to other ASes tohave a single coherent interior routing plan and presents aconsistent picture of what networks are reachable through it.RFC 1930: Guidelines for creation, selection,and registration of an Autonomous SystemShivkumar KalyanaramanRensselaer Polytechnic Institute17

IP Address Allocation and Assignment:Internet ripe.orgAPNICwww.apnic.orgAllocate to National and local registries and ISPsAddresses assigned to customers by ISPsRFC 2050 - Internet Registry IP Allocation GuidelinesRFC 1918 - Address Allocation for Private InternetsRFC 1518 - An Architecture for IP Address Allocation with CIDRShivkumar KalyanaramanRensselaer Polytechnic Institute18

AS Numbers (ASNs)ASNs are 16 bit values.64512 through 65535 are “private”Currently over 11,000 in use. Genuity: 1MIT: 3Harvard: 11UC San Diego: 7377AT&T: 7018, 6341, 5074, UUNET: 701, 702, 284, 12199, Sprint: 1239, 1240, 6211, 6242, Shivkumar KalyanaramanASNs represent units of routing policyRensselaer Polytechnic Institute19

Nontransit vs. Transit ASesISP 2ISP 1Traffic NEVERflows from ISP 1through NET A to ISP 2NET AInternet Serviceproviders (ISPs)have transitnetworksNontransit ASmight be a corporateor campus network.Could be a “contentprovider”Shivkumar KalyanaramanRensselaer Polytechnic Institute20

Selective TransitNET BNET A DOES NOTprovide transitBetween NET Dand NET BNET CNET ANET A provides transitbetween NET B and NET Cand between NET Dand NET CNET DMost transit ASes allow only selective transitkey impact of commercialization Shivkumar KalyanaramanRensselaer Polytechnic Institute21

Customers and ProvidersproviderproviderIP trafficcustomercustomerCustomer pays provider for access to the InternetShivkumar KalyanaramanRensselaer Polytechnic Institute22

Customer-Provider HierarchyproviderIP trafficShivkumar KalyanaramancustomerRensselaer Polytechnic Institute23

The Peering RelationshippeerproviderpeercustomerPeers provide transit betweentheir respective customersPeers do not provide transitbetween peerstrafficallowedRensselaer Polytechnic Institutetraffic NOTallowedPeers (often) do not exchange Shivkumar Kalyanaraman24

Peering WarsPeer Don’t PeerReduces upstream transitcostsCan increase end-to-endperformanceMay be the only way toconnect your customersto some part of theInternet (“Tier 1”) You would rather havecustomersPeers are usually yourcompetitionPeering relationships mayrequire periodicrenegotiationPeering struggles are by far the mostcontentious issues in the ISP world!Peering agreements are often confidential.Shivkumar KalyanaramanRensselaer Polytechnic Institute25

Requirements for Inter-AS Routing Should scale for the size of the global Internet. Focus on reachability, not optimality Use address aggregation techniques to minimize corerouting table sizes and associated control traffic At the same time, it should allow flexibility intopological structure (eg: don’t restrict to trees etc) Allow policy-based routing between autonomous systems Policy refers to arbitrary preference among a menu ofavailable routes (based upon routes’ attributes) Fully distributed routing (as opposed to a signaledapproach) is the only possibility. Extensible to meet the demands for newer policies.Shivkumar KalyanaramanRensselaer Polytechnic Institute26

Recall: Distributed Routing TechniquesLink State VectoringTopology information isflooded within the routingdomainBest end-to-end paths arecomputed locally at eachrouter.Best end-to-end pathsdetermine next-hops.Based on minimizing somenotion of distanceWorks only if policy is sharedand uniformExamples: OSPF, IS-IS Each router knows littleabout network topologyOnly best next-hops arechosen by each router foreach destination network.Best end-to-end paths resultfrom composition of all nexthop choicesDoes not require any notionof distanceDoes not require uniformpolicies at all routersExamples: RIP, BGPShivkumar KalyanaramanRensselaer Polytechnic Institute27

BGP-4 BGP Border Gateway Protocol Is a Policy-Based routing protocol Is the de facto EGP of today’s global Internet Relatively simple protocol, but configuration is complexand the entire world can see, and be impacted by, yourmistakes. 1989 : BGP-1 [RFC 1105]–Replacement for EGP (1984, RFC 904) 1990 : BGP-2 [RFC 1163] 1991 : BGP-3 [RFC 1267] 1995 : BGP-4 [RFC 1771]–Support for Classless Interdomain Routing (CIDR)Shivkumar KalyanaramanRensselaer Polytechnic Institute28

BGP Operations (Simplified)Establish session onTCP port 179AS1BGP sessionExchange allactive routesAS2While connectionis ALIVE exchangeroute UPDATE messagesExchange incrementalupdatesRensselaer Polytechnic InstituteShivkumar Kalyanaraman29

Four Types of BGP Messages Open : Establish a peering session. Keep Alive : Handshake at regular intervals. Notification : Shuts down a peering session. Update : Announcing new routes or withdrawingpreviously announced routes.announcement prefix attributes valuesShivkumar KalyanaramanRensselaer Polytechnic Institute30

Border Gateway Protocol (BGP)Allows multiple cores and arbitrary topologies ofAS interconnection. Uses a path-vector concept which enablesloop prevention in complex topologies In AS-level, shortest path may not be preferredfor policy, security, cost reasons. Different routers have different preferences(policy) as packet goes thru network it willencounter different policies Bellman-Ford/Dijkstra don’t work! BGP allows attributes for AS and paths whichcould include policies (policy-based routing). Shivkumar KalyanaramanRensselaer Polytechnic Institute31

BGP (Cont’d) When a BGP Speaker A advertises a prefix to its B that ithas a path to IP prefix C, B can be certain that A isactively using that AS-path to reach that destinationBGP uses TCP between 2 peers (reliability) Exchange entire BGP table first (50K routes!) Later exchanges only incremental updates Application (BGP)-level keepalive messages Hold-down timer (at least 3 sec) locally configInterior and exterior peers: need to exchange reachabilityinformation among interior peers before updating intra-ASforwarding table.Shivkumar KalyanaramanRensselaer Polytechnic Institute32

Two Types of BGP Neighbor RelationshipsAS1eBGP External Neighbor (eBGP) in adifferent Autonomous Systems Internal Neighbor (iBGP) in thesame Autonomous SystemiBGP is routed (using IGP!)iBGPAS2Shivkumar KalyanaramanRensselaer Polytechnic Institute33