← Previous Tutorial  |  Table of Contents  |  Unit Home  |  Next Tutorial →

Tutorial 8: Border Gateway Protocol (BGP) Expanded

Table of Contents

  1. Learning Objectives
  2. Overview
  3. Detailed Technical Content
  4. Quiz
  5. Exercises
  6. Homework
  7. Summary

Learning Objectives

Overview

Border Gateway Protocol (BGP) is the de facto standard exterior gateway protocol (EGP) used to exchange routing information between Autonomous Systems (ASes) on the Internet. Unlike interior gateway protocols (IGPs) that focus on optimality, BGP is a policy-based path-vector protocol. It enables ASes to implement complex routing policies based on business relationships, traffic engineering, and security considerations. BGP maintains the reachability of IP prefixes and prevents routing loops via the AS-PATH attribute. This tutorial provides a comprehensive examination of BGP, from its message types and attributes to route selection, scalability (route reflectors, confederations), traffic engineering, communities, convergence, and security. We will explore both the theoretical foundations and practical implementations that make BGP the cornerstone of Internet routing.

Detailed Technical and Theoretical Content

1. BGP Overview and Protocol Evolution

BGP was developed to replace EGP (Exterior Gateway Protocol) and is defined in RFC 4271 (BGP-4). It operates over TCP (port 179) to ensure reliable transport. BGP-4 supports CIDR and route aggregation, enabling the Internet to scale. Key milestones: BGP-4 introduced in 1995, later extended for IPv6 (BGP-4+), and with many additions (multiprotocol BGP, BGP communities, etc.). BGP is often called the "glue" of the Internet.

2. BGP Message Types and Session Establishment

BGP uses four message types:

Session establishment: after TCP three-way handshake, peers exchange OPEN messages, negotiate parameters (hold time, capabilities), and if successful, the session is established. Subsequently, they exchange full routing tables via UPDATE messages.

3. Path-Vector Algorithm and BGP Attributes

BGP is a path-vector protocol: each route advertisement includes the path (list of AS numbers) that the route has traversed. This AS-PATH is used for loop detection (if a router sees its own AS in the path, it rejects the route). Key mandatory attributes:

Well-known discretionary attributes:

Optional transitive attributes (e.g., communities) can be passed between ASes.

4. BGP Route Selection Process (Decision Algorithm)

When a BGP router receives multiple routes for the same prefix, it selects the best path based on the following decision process (in order):

  1. Highest LOCAL-PREF: (local policy preference).
  2. Shortest AS-PATH length: (fewer AS hops).
  3. Lowest ORIGIN type: IGP (0) < EGP (1) < incomplete (2).
  4. Lowest MED: (if the paths are from the same neighboring AS).
  5. Prefer eBGP over iBGP: (external routes are preferred over internal routes).
  6. Lowest IGP metric to NEXT-HOP: (the cost to reach the next-hop router).
  7. Lowest Router ID: (if all else equal, tie-breaking).

This process ensures deterministic path selection.

5. eBGP and iBGP – Roles and Rules

eBGP (external BGP) is used between routers in different ASes. The NEXT-HOP attribute is set to the IP address of the eBGP peer's interface. eBGP peers are typically directly connected (though multi-hop is possible).

iBGP (internal BGP) is used between routers in the same AS to distribute external routes. A key rule: a route learned via iBGP is not advertised to another iBGP peer (iBGP split-horizon). This prevents loops but requires a full mesh of iBGP sessions, which is scalable only with route reflectors or confederations.

6. BGP Scalability: Route Reflectors and Confederations

To avoid the O(n²) iBGP full mesh, BGP uses:

7. Policy-Based Routing and Traffic Engineering

Operators manipulate BGP attributes to influence routing decisions:

8. Advanced: BGP Communities, Extended Communities, and Large Communities

Communities are 32-bit values (or 64-bit extended) that can be attached to routes to facilitate policy. Standard communities (RFC 1997) are 4-byte values, often written as AS:value. Extended communities (RFC 4360) are 8-byte, used for MPLS VPN, route target, etc. Large communities (RFC 8092) are 12-byte to support 4-byte AS numbers. Communities allow inter-AS policy signaling.

9. BGP Convergence and Stability (Route Flap Damping)

BGP convergence is relatively slow (minutes) because of hold timers, route damping, and the propagation of updates across multiple ASes. Route flap damping (RFC 2439) penalizes routes that flap (withdraw and advertise repeatedly) by suppressing them for a period, reducing instability.

10. BGP Security: Threats and Mitigations (RPKI, BGPsec)

BGP is vulnerable to:

Mitigations:

Figure 1: BGP Decision Process Summary

1. LOCAL-PREF (highest wins)
2. AS-PATH length (shortest wins)
3. ORIGIN (IGP < EGP < incomplete)
4. MED (lowest wins, same AS)
5. eBGP over iBGP
6. IGP metric to NEXT-HOP (lowest wins)
7. Router ID (lowest wins)

Quiz

Answer each question; check your understanding by revealing the answer.

Question 1: What transport protocol does BGP use and on which port?

Show AnswerTCP, port 179.

Question 2: List the four BGP message types.

Show AnswerOPEN, UPDATE, KEEPALIVE, NOTIFICATION.

Question 3: What is the purpose of the AS-PATH attribute?

Show AnswerTo record the sequence of ASes that a route has traversed, used for loop detection and path selection.

Question 4: What is the LOCAL-PREF attribute and when is it used?

Show AnswerLOCAL-PREF is used within an AS to indicate the preference for a route; higher is better. It is exchanged only over iBGP.

Question 5: What does MED stand for and what is its purpose?

Show AnswerMulti-Exit Discriminator, used to influence the inbound traffic preference in a neighboring AS (lower is better).

Question 6: What is the iBGP split-horizon rule?

Show AnswerA route learned from one iBGP peer cannot be advertised to another iBGP peer; this prevents loops.

Question 7: What are route reflectors used for?

Show AnswerTo reduce the full mesh of iBGP sessions by allowing one router (RR) to reflect routes to its clients.

Question 8: How does BGP prevent routing loops?

Show AnswerBy checking if its own AS number appears in the AS-PATH; if so, the route is rejected.

Question 9: What is AS-PATH prepending?

Show AnswerAdding extra AS numbers to the AS-PATH to make a route appear less preferred (longer path).

Question 10: What is the default BGP keepalive interval?

Show Answer60 seconds (but can be configured).

Question 11: Which route is preferred: one with LOCAL-PREF 100 or one with LOCAL-PREF 200?

Show Answer200 (higher is better).

Question 12: In BGP decision process, which comes first: MED or AS-PATH length?

Show AnswerAS-PATH length is considered before MED.

Question 13: What is the purpose of BGP communities?

Show AnswerTo tag routes for policy signaling and filtering within and between ASes.

Question 14: What is a BGP confederation?

Show AnswerA method to split an AS into smaller sub-ASes to reduce iBGP mesh, using eBGP-like sessions between sub-ASes.

Question 15: What is RPKI and how does it enhance BGP security?

Show AnswerRPKI (Resource Public Key Infrastructure) uses cryptographic ROAs to validate that a prefix is originated by the correct AS, preventing prefix hijacking.

Question 16: What is BGPsec?

Show AnswerAn extension to BGP that provides cryptographic path validation by signing the AS-PATH.

Question 17: What is route flap damping?

Show AnswerA mechanism that penalizes routes that flap (withdraw and readvertise) and suppresses them to reduce instability.

Question 18: In BGP, what does the ORIGIN attribute indicate?

Show AnswerHow the route was introduced: IGP, EGP, or incomplete (e.g., redistributed).

Question 19: When are eBGP and iBGP used?

Show AnswereBGP between ASes, iBGP within an AS.

Question 20: Which BGP attribute is used to set a preference for routes from a specific peer within an AS?

Show AnswerLOCAL-PREF.

Question 21: What is the NEXT-HOP attribute used for?

Show AnswerIt specifies the IP address of the next-hop router to reach the advertised destination.

Question 22: Can a route learned via iBGP be advertised to an eBGP peer? Why?

Show AnswerYes, iBGP routes can be advertised to eBGP peers, but not to other iBGP peers (split-horizon).

Question 23: What is the difference between a community and an extended community?

Show AnswerA community is a 32-bit tag; extended community is 8-byte (64-bit) and used for more complex applications (e.g., VPN route targets).

Question 24: How does a router choose between multiple BGP routes that have identical attributes?

Show AnswerIt uses tie-breakers: lowest Router ID (or lowest IP address if Router ID not set).

Question 25: Why is BGP convergence slower than OSPF?

Show AnswerDue to policy-based decision making, hold-down timers, route damping, and the propagation of updates across multiple ASes.

Exercises

Work through these problems; sample solutions are hidden.

Exercise 1: Given two BGP routes for the same prefix: - Route A: AS-PATH = 100 200, LOCAL-PREF = 150, MED = 20, learned via eBGP. - Route B: AS-PATH = 100 300, LOCAL-PREF = 120, MED = 10, learned via eBGP. Which route is selected and why?

Show Sample Solution Route A has higher LOCAL-PREF (150 > 120), so it is selected regardless of other attributes.

Exercise 2: A route has AS-PATH = 65000 65001 65002. How many AS hops does it have? If the receiving AS is 65000, will it accept the route?

Show Sample Solution AS-PATH length = 3 (65000, 65001, 65002). The receiving AS (65000) sees its own AS in the path, so it will reject the route to prevent a loop.

Exercise 3: Explain how a route reflector works. Draw a simple topology with one RR and three clients. How many iBGP sessions are needed compared to a full mesh?

Show Sample Solution With RR, each client peers with the RR (3 sessions), plus perhaps non-client peers if any. Full mesh would require 4*3/2 = 6 sessions. RR reduces to 3 (if all are clients).

Exercise 4: An AS wants to prefer inbound traffic via ISP-A over ISP-B. How can it achieve this using BGP attributes?

Show Sample Solution To influence inbound traffic, the AS can advertise its prefixes with a shorter AS-PATH to ISP-A (e.g., prepend less) or set MED lower on routes sent to ISP-A. However, MED only influences the neighboring AS. More commonly, AS-PATH prepending is used: add extra AS numbers to routes sent to ISP-B to make them less preferred.

Exercise 5: What is the effect of setting LOCAL-PREF to 0 for a route?

Show Sample Solution LOCAL-PREF 0 is the lowest possible preference; it will be less preferred than any other route with LOCAL-PREF > 0 (since values are typically 0-65535, default 100). It may be used to make a route only used as a last resort.

Exercise 6: In a network with two eBGP peers (A and B) and two iBGP routers (R1 and R2), describe the flow of a BGP update from an external AS through R1 to R2.

Show Sample Solution External AS sends UPDATE to R1 via eBGP. R1 installs the route, sets LOCAL-PREF (if configured), and then advertises it via iBGP to R2. R2 receives it, does not advertise it further via iBGP (split-horizon), but can install it in its routing table.

Exercise 7: What is the purpose of the BGP KEEPALIVE message? What happens if KEEPALIVEs are not received within the hold time?

Show Sample Solution KEEPALIVE messages maintain the BGP session. If no KEEPALIVE is received within the hold time (typically 3x keepalive interval), the session is considered dead, and the BGP neighbor is declared down, causing routes from that neighbor to be withdrawn.

Exercise 8: Compare the use of MED and LOCAL-PREF in terms of scope and effect.

Show Sample Solution LOCAL-PREF is used within an AS (iBGP) to set preference for outbound routes (internal). MED is used between ASes (eBGP) to influence the inbound route selection of the neighboring AS. LOCAL-PREF is higher = better, MED is lower = better.

Exercise 9: Explain why BGP requires a full mesh of iBGP sessions (or route reflectors) to guarantee that all routers in an AS learn all external routes.

Show Sample Solution Because iBGP split-horizon prevents a router from advertising an iBGP-learned route to another iBGP peer. Without a full mesh (or RR), some routers would not receive certain external routes, leading to reachability gaps.

Exercise 10: A route with AS-PATH = 100 200 300 and COMMUNITY = 100:10. Describe how the community can be used to set LOCAL-PREF to 200 at the receiving AS, assuming the receiving AS is configured to do so.

Show Sample Solution The receiving AS can have a policy that matches community 100:10 and sets LOCAL-PREF to 200 for routes carrying that community. This is a common way to signal preference.

Homework Assignments

These questions require deeper thought and research. Write comprehensive answers.

Homework 1: Explain in detail the BGP route selection decision process, including the tie-breaking steps. Provide a scenario where two routes have identical LOCAL-PREF, AS-PATH length, and ORIGIN, and show how MED and IGP metric resolve the tie.

Show Answer Outline Detailed steps: LOCAL-PREF > AS-PATH length > ORIGIN > MED (if same AS) > eBGP over iBGP > IGP metric > Router ID. Example scenario with two routes from same AS, different MED values.

Homework 2: Compare and contrast BGP with OSPF in terms of protocol operation, metric, convergence, scalability, and policy support. Why is BGP used for inter-AS routing?

Show Answer Outline BGP: path-vector, policy, slow convergence, scalable to Internet, supports policies. OSPF: link-state, cost, fast convergence, limited to AS. BGP used due to policy and scale.

Homework 3: Research the concept of "BGP route reflectors" and provide a detailed example of how they reduce iBGP sessions in a large AS with 50 routers. Compare with confederations.

Show Answer Outline RR reduces sessions from O(n²) to O(n). With 50 routers, full mesh = 1225 sessions; with 2 RRs, each router peers with RRs, so ~100 sessions. Confederations split AS into sub-ASes; each sub-AS uses eBGP-like sessions, also reducing mesh.

Homework 4: Explain the purpose and format of BGP communities. Provide examples of well-known communities (e.g., NO_EXPORT, NO_ADVERTISE) and how they are used.

Show Answer Outline Communities are 32-bit tags (AS:value). Well-known: NO_EXPORT (0xFFFFFF01) prevents advertisement outside confederation; NO_ADVERTISE (0xFFFFFF02) prevents advertisement to any peer. Used for policy control.

Homework 5: Analyze the problem of BGP prefix hijacking. Describe a real-world incident (e.g., YouTube hijacking in 2008) and explain how RPKI could have mitigated it.

Show Answer Outline Incident: Pakistan Telecom accidentally announced YouTube prefixes, causing global misrouting. RPKI would have allowed ISPs to validate origin AS and reject the invalid announcement.

Homework 6: What is the difference between BGP "inbound" and "outbound" traffic engineering? Give specific BGP attribute manipulations for each direction.

Show Answer Outline Outbound: use LOCAL-PREF to prefer one provider over another. Inbound: use AS-PATH prepending or MED to influence which provider is used to enter your AS.

Homework 7: Explain how BGP supports IPv6 (multiprotocol BGP) and what additional attributes are used.

Show Answer Outline Multiprotocol BGP uses MP_REACH_NLRI and MP_UNREACH_NLRI attributes to carry IPv6 prefixes and next-hop information. It also supports other address families.

Homework 8: Discuss the scalability of BGP in terms of the number of prefixes and the number of ASes. What are the limitations and what efforts are underway to improve scalability?

Show Answer Outline BGP table size grows (over 1M prefixes). Limitations: memory, CPU, convergence time. Efforts: aggregation, route filtering, deployment of RPKI and BGPsec, and research on new routing architectures (e.g., path-vector with data-plane validation).

Homework 9: Derive the BGP decision process mathematically for a set of routes with attributes. Provide pseudocode for the selection of the best route.

Show Answer Outline Algorithm: sort routes by LOCAL-PREF (desc), then AS-PATH length (asc), then ORIGIN type, then MED (asc) if same neighbor AS, then prefer eBGP, then IGP metric, then Router ID. Return highest priority.

Homework 10: Explain the concept of "route leakage" in BGP and its consequences. Provide an example and discuss preventive measures.

Show Answer Outline Route leakage occurs when an AS advertises routes from one peer to another, violating policy. Example: a provider advertises its customer's routes to a peer, causing the peer to send traffic through the provider. Prevention: filtering based on prefix lists, communities, and strict policy controls.

Homework 11: Research the deployment status of RPKI and BGPsec. What are the challenges preventing widespread adoption of BGPsec?

Show Answer Outline RPKI is increasingly deployed; BGPsec faces challenges: computational overhead, key management, incremental deployment difficulties, and lack of incentive.

Homework 12: Design a BGP policy for a multi-homed enterprise with two providers (ISP-A and ISP-B) and one peer (IXP). The enterprise wants to use ISP-A as primary for outbound, ISP-B as backup, and use the IXP for peering with a specific content provider. Show the BGP attributes and policy statements.

Show Answer Outline Set LOCAL-PREF higher for ISP-A routes (e.g., 200) than ISP-B (e.g., 100). For inbound, use AS-PATH prepending on routes to ISP-B to make them less preferred. For the IXP, only announce routes to the content provider, not to other peers. Use communities to tag routes.

Summary

This tutorial provided an in-depth examination of BGP, covering its message types, path-vector operation, key attributes, route selection process, scalability mechanisms (route reflectors, confederations), policy-based routing, communities, convergence, and security. BGP is the critical protocol that enables the Internet to function as a federation of networks, each with its own policies. Understanding BGP is essential for network engineers and architects responsible for maintaining and evolving the global Internet infrastructure. The next tutorial will examine how BGP is applied in practice in Internet routing.

← Previous Tutorial  |  Table of Contents  |  Unit Home  |  Next Tutorial →

End of Tutorial 8 .