1、The Basics of BGP (Border Gateway Protocol) Routing and its Performance in Todays Internet,Presenter: Sophia PokuSlides taken from presentation by Nina Taft,Outline,1. Highlights 2. Addressing and CIDR 3. BGP Messages and Prefix Attributes 4. BGP Decision and Filtering Processes 5. I-BGP 6. Route Re
2、flectors 7. Multihoming 8. Aggregation 9. Routing Instability 10. BGP Table Growth,Routing Protocols,E-BGP,A,AS2,AS (Autonomous System) - a collection of routers under the same technical and administrative domain.EGP (External Gateway Protocol) - used between two ASs to allow them to exchange routin
3、g information so that traffic can be forwarded across AS borders. Example: BGP,Routers used,Internal Router: directly connects networks belonging to the same area It runs a single copy of the basic routing protocol Border/Boundary Router: exchanges routing information with routers belonging to other
4、 AS,Purpose: to share connectivity information,border router,internal router,BGP,A,AS1,AS2,BGP Sessions,Primary function is to exchange network-reachability information (includes AS #s) Uses TCP to establish connection Initially node advertises ALL routes it wants neighbor to know (could be 50K rout
5、es) Ongoing only inform neighbor of changes One router can participate in many BGP sessions.,AS1,AS2,AS3,Configuration and Policy,A BGP node has a notion of which routes to share with its neighbor. It may only advertise a portion of its routing table to a neighbor. A BGP node does not have to accept
6、 every route that it learns from its neighbor. It can selectively accept and reject messages. What to share with neighbors and what to accept from neighbors is determined by the routing policy, that is specified in a routers configuration file.,Addressing Schemes,Original addressing schemes (class-b
7、ased): 32 bits divided into 2 parts: Class A 0xxx or 1-126 in decimal; subnet mask:255.0.0.0 Class B 10xx or 128-192 in decimal Subnet mask:255.255.0.0 Class C 110x or 192-223 in decimal, Subnet Mask:255.255.255.0,2 million nets 256 hosts,CIDR (Classless Inter-Domain Routing),CIDR introduced to solv
8、e 2 problems: exhaustion of IP address space size and growth rate of routing table,Problem #1: Lifetime of Address Space,Example: an organization needs 500 addresses. A single class C address not enough (256 hosts). Instead a class B address is allocated. (64K hosts) Thats overkill -a huge waste. CI
9、DR allows networks to be assigned on arbitrary bit boundaries. permits arbitrary sized masks: 178.24.14.0/23 is valid requires explicit masks to be passed in routing protocols CIDR solution for example above: organization is allocated a single /23 address (equivalent of 2 class Cs).,Problem #2: Rout
10、ing Table Size,Without CIDR:,232.71.0.0 232.71.1.0 232.71.2.0 232.71.255.0,With CIDR:,232.71.0.0/16,CIDR: Classless Inter-Domain Routing,Address format . The prefix denotes the upper P bits of the IP address. E.g. in CIDR address 206.13.01.48/25, the “/25” indicates the first 25 bits are used to ide
11、ntify a unique network, the remaining bits are hosts Idea - use aggregation - provide routing for a large number of customers by advertising one common prefix. This is possible because nature of addressing is hierarchical Summarizing routing information reduces the size of routing tables, but allows
12、 to maintain connectivity. Aggregation is critical to the scalability and survivability of the Internet,Address Arithmetic: Address Blocks,The pair defines an address block: Examples: 128.15.0.0/16 = 128.15.0.0 - 128.15.255.255 188.24.0.0/13 = 188.24.0.0 - 188.31.255.255 consider 2nd octet in binary
13、: Address block sizes a /13 address block has 232-13 addresses(=524288) (/16 has 232-16 =65536) a /13 address block is 8 times as big as a /16 address block because 232-13 = 232-16 * 23,CIDR: longest prefix match,Because prefixes of arbitrary length allowed, overlapping prefixes can exist. Example:
14、router hears 124.39.0.0/16 from one neighbor and 124.39.11.0/24 from another neighbor Router forwards packet according to most specific forwarding information, called longest prefix match Packet with destination 124.39.11.32 will be forwarded using /24 entry. Packet w/destination 124.39.22.45 will b
15、e forwarded using /16 entry,Will CIDR work ?,For CIDR to be successful need: address registries must assign addresses using CIDR strategy providers and subscribers should configure their networks, and allocate addresses to allow for a maximum amount of aggregation BGP must be configured to do aggreg
16、ation as much as possible Factors that complicate achieving aggregation multihoming, proxy aggregation, changing providers,Four Basic Messages,Open: Establishes BGP session (uses TCP port #179) Notification: Report unusual conditions Update: Inform neighbor of new routes that become active Inform ne
17、ighbor of old routes that become inactive Keepalive: Inform neighbor that connection is still viable,BGP Database,1.Neighbor tableList of BGP neighbors2. BGP forwarding tableList of all networks learned from each neighbor 3. IP routing tableList of best path to destination networks,OPEN Message,Duri
18、ng session establishment, two BGP speakers exchange their AS numbers BGP identifiers (usually one of the routers IP addresses) Router ID Holdtime Open messages are confirmed using a keep-alive message sent by a peer and must be confirmed before updates A BGP speaker has option to refuse a session Se
19、lect the value of the hold timer:maximum time to wait to hear something from other end before assuming session is down. authentication information (optional),NOTIFICATION and KEEPALIVE Messages,NOTIFICATION Indicates an error terminates the TCP session gives receiver an indication of why BGP session
20、 terminated Examples: header errors, hold timer expiry, bad peer AS, bad BGP identifier, malformed attribute list, missing required attribute, AS routing loop, etc. KEEPALIVE protocol requires some data to be sent periodically. If no UPDATE to send within the specified time period, then send KEEPALI
21、VE message to assure partner that connection still alive,UPDATE Message,Updates are sent using TCP to ensure delivery used to either advertise and/or withdraw unfeasible prefixes from routing table path attributes: list of attributes that pertain to ALL the prefixes in the Reachability Info field,Wi
22、thdrawn routes length (2 octets),Withdrawn routes (variable length),Total path attributes length (2 octets),Path Attributes (variable length),Reachability Information (variable length),FORMAT:,Advertising a prefix,When a router advertises a prefix to one of its BGP neighbors: information is valid un
23、til first router explicitly advertises that the information is no longer valid BGP does not require routing information to be refreshed if node A advertises a path for a prefix to node B, then node B can be sure node A is using that path itself to reach the destination.,BGP Attributes,Attributes: ro
24、utes learned via BGP have associated properties that are used to determine the best route to a destination when multiple paths exist to a particular destination Local Preference Multi-Exit Discriminator (MED) Origin AS-path Next-hop,Attribute: ORIGIN,ORIGIN: Who originated the announcement? Where wa
25、s a prefix injected into BGP? indicates how BGP learned about a particular route IGP: route is interior to the originating AS. This value is Value set using network router configuration command to inject router into BGP EGP: route learned via the External Gateway Protocol Incomplete (often used for
26、static routes): origin of routes unknown or learned in some other way,Attributes: AS_PATH,a list of ASs through which the announcement for a prefix has passed each AS prepends its AS # to the AS-PATH attribute when forwarding an announcement useful to detect and prevent loops,Attribute: NEXT HOP,IP
27、address used to reach the advertising router For EBGP session, NEXT HOP = IP address of neighbor that announced the route. For IBGP sessions, if route originated inside AS, NEXT HOP = IP address of neighbor that announced the route For routes originated outside AS, NEXT HOP of EBGP node that learned
28、 of route, is carried unaltered into IBGP.,BGP Table at Router C:,IP Routing Table at Router C:,Next-Hop Contd,Router C advertises 172.16.1.0 with next hop 10.1.1.1 A propagates it within its AS,Attribute: Multi-Exit Discriminator (MED),when ASs interconnected via 2 or more links AS announcing prefi
29、x sets MED enables AS2 to indicate its preference AS receiving prefix uses MED to select link a way to specify how close a prefix is to the link it is announced on,Attribute: Local Preference,Used to prefer an exit point from the local AS Used to indicate preference among multiple paths for the same
30、 prefix anywhere in the internet. The higher the value the more preferred Exchanged between IBGP peers only. Local to the AS. Often used to select a specific exit point for a particular destination,Routing Process Overview,Output policy engine,BGP table,IP routing table,Choose best route,accept, den
31、y, set preferences,forward, not forward set MEDs,Input Policy Engine,Inbound filtering controls outbound traffic filters route updates received from other peers filtering based on IP prefixes, AS_PATH, community denying a prefix means BGP does not want to reach that prefix via the peer that sent the
32、 announcement accepting a prefix means traffic towards that prefix may be forwarded to the peer that sent the announcement Attribute Manipulation sets attributes on accepted routes example: specify LOCAL_PREF to set priorities among multiple peers that can reach a given destination,BGP Decision Proc
33、ess,1. Choose route with highest LOCAL-PREF 2. If have more than 1 route, select route with shortest AS-PATH 3. If have more than 1 route, select according to lowest ORIGIN type where IGP EGP INCOMPLETE 4. If have more than 1 route, select route with lowest MED value 5. Select min cost path to NEXT
34、HOP using IGP metrics 6. If have multiple internal paths, use BGP Router ID to break tie.,Output Policy Engine,Outbound Filtering controls inbound traffic forwarding a route means others may choose to reach the prefix through you not forwarding a route means others must use another router to reach t
35、he prefix may depend upon whether E-BGP or I-BGP peer example: if ORIGIN=EGP and you are a non-transit AS and BGP peer is non-customer, then dont forward Attribute Manipulation sets attributes such as AS_PATH and MEDs,Transit vs. Nontransit AS,Transit traffic = traffic whose source and destination a
36、re outside the AS,Nontransit AS: does not carry transit traffic,Transit AS: does carry transit traffic,Advertise own routes onlyDo not propagate routes learned from other ASscase 1:,Advertises its own routes PLUS routes learned from other ASs,case 2:,Internal BGP (I-BGP),Used to distribute routes le
37、arned via EBGP to all the routers within an AS I-BGP and E-BGP are same protocol in that same message types used same attributes used same state machine BUT use different rules for readvertising prefixes Rule #1: prefixes learned from an E-BGP neighbor can be readvertised to an I-BGP neighbor, and v
38、ice versa Rule #2: prefixes learned from an I-BGP neighbor cannot be readvertised to another I-BGP neighbor,I-BGP: Preventing Loops and Setting Attributes,Why rule #2? To prevent announcements from looping. In E-BGP can detect via AS-PATH. AS-PATH not changed in I-BGP Implication of rule: a full mes
39、h of I-BGP sessions between each pair of routers in an AS is required Setting Attributes: The router that injects the route into the I-BGP mesh is responsible for setting the LOCAL-PREF attribute prepending AS # to AS-PATH,Route Reflectors,Problem: requiring a full mesh of I-BGP sessions between all
40、 pairs of routers is hard to manage for large ASs. Solution: group routers into clusters. Assign a leader to each cluster, called a route reflector (RR). Members of a cluster are called clients of the RR I-BGP Peering clients peer only with their RR RRs must be fully meshed,clients,clusters,RR,RR,Ro
41、ute Reflectors: Rule on Announcements,Provides mechanisms for minimizing the # of updates messages transmitted within an AS and reducing the amount of data propagated in each message. If received from RR, reflect to clients If received from a client, reflect to RRs and clients If received from E-BGP
42、, reflect to all - RRs and clients RRs reflect only the best route to a given prefix, not all announcements they receive. helps size of routing table sometimes clients dont need to carry full table,Avoiding Loops with Route Reflectors,Loops cannot be detected by traditional approach using AS-PATH be
43、cause AS-PATH not modified within an AS. Announcements could leave a cluster and re-enter it. Two new attributes introduced: ORIGINATOR_ID: router id of routes originator in AS rule: announcement discarded if returns to originator CLUSTER_LIST: a sequence of cluster ids. set by RRs. rule: if an RR r
44、eceives an update and the cluster list contains its cluster id, then update is discarded.,Multihoming,Single-homed vs. Multi-homed subscribers,A single-homed network has one connection to the Internet (i.e., to networks outside its domain) A multi-homed network has multiple connections to the Intern
45、et. Two scenarios: can be multi-homed to a single provider can be multi-homed to multiple providers Why multi-home? Reliability Performance,Single-homed AS,Subscriber called a “stub AS” Provider-Subscriber communication for route advertisement: static configuration. most common. Providers router is
46、configured with subscribers prefix. good if customers routes can be represented by small set of aggregate routes bad if customer has many noncontiguous subnets can use BGP between provider and stub AS,R2,Subscriber,R1,Provider,Multihoming to Multiple Providers,Multihoming Issues,Load sharing how dis
47、tribute the traffic over the multiple links? Reliability if load sharing leads to preferencing certain links for certain subnets, is reliability reduced? Address/Aggregation which subnet addresses should the multihomed customer use? how will this affect its providers ability to aggregate routes?,Loa
48、d sharing from ISP to Customer using attributes,Goal: provider splits traffic across 2 links according to prefix Implement this strategy using attributes customer sets MEDs provider sets LOCAL_PREF,R2,Customer,R3,Load sharing from Customer to ISP using policy,Goal: send traffic to ISPs customers on
49、one link; send traffic to the rest of the Internet on 2nd link Implement using policy to control announcements,R3,Customer,R1,ISP,R2,advertise customer routes only,advertise default route 0/0,traffic,blue: announcements red: traffic,Address/Aggregation Issue,Where should the customer get its address block from? 1. From ISP1 2. From ISP2 3. From both ISP1 and ISP2 4. Independently from address registry,(cases 1 and 2 are equivalent),Case 1 & 2: Get address block from one ISP,
