# Border Gateway Protocol

#### Routing Protocols

The main job is to distribute the data to build forwarding tables

- These are **intra-domain routing protocols**
  - Or **Interior gateway protocols**
  - When the source and destination are **inside** the **same network**

It is important to distinguish between local and global protocols

- Interior vs Exterior Gateway Protocol (IGP vs EGP)

##### BGPv4

The internet inter-domain routing protocol

- Derives from GGP & EGP
- Deals in IP prefixes and **autonomous systems**
  - autonomous systems are purely administrative
  - Purpose is to enable *policy* to be applied
  - Only prefixes matter in the data-plane
- Internet policy domains
  - Logical construct only
  - No meaning outside BGP
  - Do not map simply onto ISPs or networks
- Currently ~493,000 prefixes & ~46,000 ASs
  - Because we have less ASs, the routing is easily -> less complex
  - Reduces complexity
  - Speeds up performance

BGP uses TCP as transport

- `OPEN`, `UPDATE`, `KEEPALIVE`, `NOTIFICATION`

Sessions between peers have:

- Simple capability negotiation
- Manage simultaneous `OPEN` connections
- Lose everything on session failure

#### Sessions and Routing Information Base (RIBs)

A BGP peer typically has many sessions

- Logically, for each peer, it receives the information about routing from peers, this is sorted into `Adj-RIB-in` table.
- After processing, it produces a `Adj-RIB-out` table which it sends to other peers
  - Advertisements received and to be sent
- Generates a local RIB table from `Adj-RIB-in`
  - Routes to use and potentially distribute
  - Resolved into per-port forwarding tables
- Generate `Adj-RIB-out` from `Loc-RIB` and policy

#### Update messages

- Incremental - indicate *changes* to state
  - These updates could be:
  - Withdrawn routes
  - Path attributes, common to all advertised routes
  - Advertised routes, known as NLRI
- There are ~27 path attributes
  - Only ~12 are in common use
  - Communicate information about prefixes
  - Used to apply policy in BGP *decision process*

##### Path Attributes

Mandatory - every AS has to inform the other ASs about these 3 attributes:

- Next hop
- AS Path
- Origin

Discretionary

- Local preferences
  - Allows prioritisation of ASs 

Optional & transitive

- Aggregator
- Community
- Extended Communities

Optional & non-transitive

- Multi-exit discriminator
- Originator ID

### Path Vectors

**Distance Vector** - prefer lowest cost path (not always)

**Path Vector**

- How do we know if an AS has seen this advert before
- Store the list of ASs in the packet
  - This is called the `AS_PATH`
- This way loops can be broken
  - If our ASN appears in a received `AS_PATH`, drop the advert

##### Decision Process

Drop prefix if:

- `NEXT_HOP` is unreachable via local routing table
- Local AS appears in `AS_PATH` (packet in a loop)

Then (commonly) apply following preference:

1. Higher `weight` (local to this router)
2. Highest `LOCAL_PREF`
3. Shortest `AS_PATH`
4. Lowest `ORIGIN`
5. Lowest `MED`
6. `EGP` to `IGP` (hot potato)
7. Shortest internal path
8. Prefer oldest route
   - Oldest routes are often most stable
9. Lowest interface IP address

### Consistency

Learn external routes on `EBGP` sessions

- `EBGP` defined as peers having different ASNs
- Must ensure every router knows all external routes
- Redistribute external routes inside the network
  - Via `IGP` - only in small networks
  - via `IBGP` - gives full control over route distribution

###### Scaling

Can distribute `IBGP` routes on `IBGP` sessions

- Have to maintain $N\cdot \frac{(N-1)}{2}$ `IBGP` sessions
  - Each carrying up to 490k routes x2 tables
- Two standard solutions
  1. **Route Reflectors**
     - Super nodes re-advertising `IBGP` routes
     - Allows for hierarchy
  2. **AS Confederations**
     - split AS up into mini-ASs

###### Failures

- Handling link failures
  - Bind to loopback
    - If it cant talk to other nodes, will only support communication internally
  - Flap damping
    - A warning message saying don't send traffic to me
    - This can make things worse if this message is delayed
- Process failures
  - Out of memory error due to too many routes

##### Network Inter-connection

- Networks interconnect via `EBGP` sessions
  - POPs - points of presence or IX internet exchanges
- Multi-homing
  - This is all logical
  - http://0x0.st/ooCs.png