BGP

Recall that an "autonomous system" (AS) or "domain" is a region of an network under a single administrative entity.

Inter-AS Business Relationships

The topology and policy shaped by inter-AS business relationships fall under three basic kinds:

• AS A can be AS B's customer
• AS A can be AS B's provider
• AS A can be AS B's peer

There are a few business implications:

• customer pays provider
• peers don't pay each other (because of the assumption that they exchange roughly equal traffic).

• In this scenario, D's traffic can travel from A to B to E because both A and B have customers directly involved.
• D cannot get to F through B because no customer of B is involved in the routing. It will not provide bandwidth of no one is paying (because E is not involved). This is because of the AS policies set in this scenario (not universal!).

Inter-AS routing

The setup is as follows:

• destinations are IP prefixes (12.0.0.0/8)
• nodes are autonomous systems (ASes) (internals) of each AS are hidden
• links represent both physical links and business relationships
• BGP (border gateway protocol) is the inter-domain routing protocol implemented by AS border routers.

The basic of idea of BGP is a loop of:

• An AS advertises ("exports") its best routes to one or more IP prefixes
• Each AS selects the "best" route it hears advertised for a prefix

BGP is inspired by distance-vectors with four differences:

• shortest-path routes may not be picked to enforce policy.
• path-vector routing to avoid loops
• selective route advertisement (because of policy enforcement) may affect reachability
• routes may be aggregated for scalability (if two destinations are flowing through the same route and share the same prefix, then you can aggregate those prefixes so they take up only one row in forwarding table)

BGP Policies

A policy dictates how routes are selected and exported.

• selection is which path to use? Controls whether/how traffic leaves the network. For example, say there's two path possibilities are provided, selection is deciding the path to export.
• export is which the question of what path to advertise? Controls whether/how traffic enters the network. For example, choose to export to AS 1 but not AS 2.

A typical selection policy is: in decreasing order of priority:

• make/save money (send to customer > peer > provider)
• maximize performance (smallest AS path length)
• minimize use of my network bandwidth ("hot potato")

Gao-Rexford

The typical export policy is

destination prefix advertised by...	export route to...
customer	everyone (provider, peers, other customers)
peer	customers
provider	customers

These are referred to as the "Gao-Rexford" rules. With this, the AS policy graph is a DAG (directed acyclic graph) and the routes are "valley free". Valley free routing is the following concept:

• number the links as (+1, 0, -1) for customer-to-provider, peer-to-peer, and provider-to-customer. Any path should only see sequence of +1, followed by at most one 0, followed by sequence of -1.

The policy dictates how routes are "selected" and "exported".

BGP Protocol Details

"Speaking BGP" means it implements the BGP protocol standard which specifies which messages to exchange with other "BGP speakers". The message can have different type (e.g., route advertisement, updates) and syntax.

To process these messages, it follows the BGP state machine in the protocol spec + policy decision.

Border routers in an AS speak BGP with border routers in other ASes using eBGP sessions.

eBGP are BGP sessions between border routers in different ASes. It learns routes to external destinations.

iBGP are BGP sessions between border routers and other routers within the same AS. It distributes externally learned routers internally.

IGP is the "Interior Gateway Protocol" which is an intra-domain routing protocol. It provides internal reachability. E.g., OSPF, RIP.

eBGP, iBGP, and IGP works together: they learn routes to external destinations using eBGP. Then, iBGP distributes these externally learned routes internally. They then travel the shortest path to egress (leave egress) using IGP.

BGP Messages

The basic messages in BGP:

• Open establishes BGP session (BGP uses TCP)
• Notification reports unusual conditions
• Update informs neighbors of new routes and old routes that become inactive.
  • format <IP prefix: route attributes>, where attribute describes properties of the routes
  • two kinds:
    • announcements: new routes or changes to existing routes
    • withdrawal: removes routes that no longer exist
• Keep-alive informs neighbor that connection is still viable.

Route Attributes

Route attributes describe the route. It is used in route selection/export decisions.

• some attributes are local, i.e., private within an AS, not included in announcements.
• some attributes are propagated with eBGP route announcements
• there are many standardized attributes in BGP.

Standard attributes:

• (1) AS PATH
  • carried in route announcements
  • vector that lists all the ASes a route advertisement has traveled (in reverse order)
  • E.g., if the route advertisement has traversed AS 88 and then AS 7018, then AS path = 7018 88
• (2) LOCAL PREF
  • local preferences in choosing between different AS paths. Local to an AS; carried only in iBGP messages.
  • The higher the value, the more preferred. Typically associated with money.
• (3) MED
  • multi-exit discriminator (MED) is used when ASes are interconnected via 2 or more links; it specifies how close a prefix is to the link it is announced on.
  • Lower is better
  • AS that announces a prefix sets MED
  • AS receiving the prefix (optionally) uses MED to select link.
• (4) IGP cost
  • used for hot-potato routing where each router selects the closest egress point based on the path cost in intra-domain protocol.

Using attributes: rules for route selection in priority order

Priority	Rule	Remarks
1	LOCAL PREF	Pick highest LOCAL PREF
2	ASPATH	Pick shortest ASPATH length
3	MED	Lowest MED preferred
4	eBGP>iBGP	Did AS learn route via eBGP (preferred) or iBGP
5	iBGP path	Lowest IGP cost to next hop (egress router)
6	Router ID	Smallest next-hop router's IP address as tie-breaker

BGP UPDATE processing:

• After we find the best route, then we add the forwarding entries into the IP forwarding table.

Issues in Practice

Reachability, security, convergence, performance.

Reachability:

• in normal routing, if graph is connected then reachability is assured
• with policy routing, this does not always hold, so reachability is not guaranteed

security:

• a AS can claim to serve a prefix that they do not have a route to (black-holing):
  • problem not specific to policy or path vector
  • important because of AS autonomy
  • fixable: make ASes "prove" they have a path

Convergence:

• if all AS policies follow "Gao-Rexford" rules, BGP is guaranteed to converge.
  • A set of rules that decide the preferences of routers. E.g., prefer a route via a customer over a route via a provider or peer
• for arbitrary policies, BGP may fail to converge.

Performance nonissues:

• internal routing
  • domains typically use "hot potato" routing
  • not always optional, but economically expedient.
• policy is not always about performance as policy-driven paths aren't the shortest.
• AS path length can be misleading because 20% of paths inflated by at least 5 router hops.
  • An AS may have many router-level hops, so in this example below, we would choose AS4 but it actually has more router hops to go through.
  • 

Real performance issues: slow convergence

• BGP outages are the biggest source of internet problems
• most popular paths are very stable but outages are still very common.