Border Gateway Protocol (BGP)

Every routing protocol is fundamentally an algorithm for computing paths through a network. The algorithm's design determines what information routers exchange, how they compute best paths, and how they handle topology changes. BGP uses a path vector algorithm—a distinct approach that differs fundamentally from both distance vector (used by RIP) and link state (used by OSPF).

Understanding path vector routing is essential for understanding BGP's behavior, limitations, and capabilities. It explains why BGP can prevent routing loops without knowing the complete network topology, why BGP policies can be so flexible, and why BGP convergence is inherently different from IGP convergence.

Before diving into path vector specifics, we need to understand the landscape of routing algorithms. Each paradigm represents a different philosophy about what information routers should share and how they should compute paths.

The Fundamental Tradeoffs:

Routing algorithms must balance several competing concerns:

• Information completeness: How much network topology information does each router need?
• Message overhead: How much bandwidth and processing does route exchange consume?
• Convergence speed: How quickly do routers agree on new paths after changes?
• Scalability: How does the algorithm perform as the network grows?
• Policy flexibility: Can routing decisions reflect requirements beyond shortest path?

Different algorithms make different tradeoffs. Let's examine each paradigm:

Understanding distance vector is essential background for path vector, as path vector evolved to address distance vector's limitations in multi-domain environments.

How Distance Vector Works:

In distance vector routing, each router maintains a table (vector) containing:

• The destination network
• The distance (metric) to reach it
• The next-hop router to use

Routers periodically exchange their entire distance vectors with directly connected neighbors. Upon receiving a neighbor's vector, routers apply the Bellman-Ford algorithm:

For each destination D in neighbor's vector:
    new_distance = distance_to_neighbor + neighbor's_distance_to_D
    if new_distance < current_distance_to_D:
        update route: D via neighbor with new_distance

This distributed computation converges to optimal paths without any router knowing the complete topology.

Distance Vector's Critical Flaw: Count-to-Infinity

Distance vector's simplicity comes with a severe limitation: the count-to-infinity problem. When a destination becomes unreachable, the protocol can enter a loop where routers keep incrementing distances until hitting the maximum (typically 16).

Example Scenario:

1. Network X is connected to Router A, which advertises X with distance 1
2. Router B learns X via A with distance 2
3. Link between A and X fails
4. A has no route to X, but receives B's old advertisement (distance 2)
5. A thinks: "I can reach X via B with distance 3!"
6. B receives A's update, thinks: "I can reach X via A with distance 4!"
7. This continues until distance = infinity (16), route is withdrawn

Mitigations like split horizon (don't advertise a route back to where you learned it) and poison reverse (advertise infinity back to where you learned it) help but don't completely solve the problem in all topologies.

Why This Matters for Path Vector:

The count-to-infinity problem occurs because distance vector routers have no visibility into the actual path. They don't know if their 'improvement' creates a loop. Path vector addresses this directly by including the complete path in every advertisement.

Link state routing takes a fundamentally different approach: give every router complete topology information and let each compute paths independently.

How Link State Works:

1. Discovery: Each router discovers its directly connected neighbors via Hello packets
2. Distribution: Each router floods its link state (neighbors and costs) to all other routers
3. Database: Every router builds an identical Link State Database (LSDB)
4. Computation: Each router runs Dijkstra's SPF algorithm on the LSDB
5. Result: Every router has computed the shortest path to every destination

Advantages of Link State:

Why Link State Doesn't Scale for Inter-Domain Routing:

Despite its elegance, link state is unsuitable for Internet-scale inter-domain routing:

The fundamental problem: link state requires complete topology knowledge, which is both technically infeasible and administratively unacceptable at Internet scale. No competitive ISP wants to share its internal topology with rivals.

Path vector routing combines elements of distance vector with a crucial enhancement: instead of just advertising the distance to a destination, routers advertise the complete path (sequence of ASes) to that destination.

The Path Vector Principle:

When a BGP router advertises a route, it includes:

• The destination prefix (e.g., 192.0.2.0/24)
• The AS_PATH: the ordered sequence of ASes the route has traversed
• Other path attributes (origin, next-hop, local preference, etc.)

When a router receives this advertisement, it:

1. Checks if its own AS is in the AS_PATH (loop detection)
2. If not, prepends its own AS to the path and may readvertise

Example Path Vector Operation:

In this example:

• AS 65001 originates prefix 10.1.0.0/16 with AS_PATH = [65001]
• AS 65002 receives the route, prepends its ASN: AS_PATH = [65002, 65001]
• AS 65003 receives the route, prepends its ASN: AS_PATH = [65003, 65002, 65001]
• AS 65004 receives the route, prepends its ASN: AS_PATH = [65004, 65003, 65002, 65001]

The Power of Path Information:

The AS_PATH provides several critical capabilities:

1. Natural Loop Prevention A router discards any route that contains its own AS in the AS_PATH. This is simple, foolproof, and requires no additional mechanisms.

2. Path Length as Metric The number of ASes in the path serves as a basic metric. All else being equal, shorter AS_PATHs are preferred.

3. Policy Decisions The AS_PATH enables rich policy. You can:

• Prefer routes that pass through specific ASes (trusted partners)
• Reject routes that pass through specific ASes (competitors, untrusted networks)
• Manipulate path length by prepending your own AS multiple times

4. Troubleshooting Visibility When debugging routing issues, the AS_PATH shows exactly how a route reached you—invaluable for diagnosing problems.

Understanding the mathematical properties of path vector helps explain its convergence behavior and policy capabilities.

Path Vector as Modified Bellman-Ford:

The classical Bellman-Ford algorithm maintains:

dist[v] = min over all neighbors u of (dist[u] + weight(u,v))

Path vector modifies this to track the complete path:

path[v] = best_path among all neighbors u of (prepend(self, path[u]))
           where self not in path[u]

The 'best_path' selection is not purely metric-based; it incorporates BGP's complex decision process (local preference, AS_PATH length, origin type, MED, etc.).

Convergence Properties:

Path vector converges because:

1. Finite paths: The number of ASes is finite, so paths have bounded length
2. Monotonic path growth: Each hop adds exactly one AS
3. Loop rejection: Paths containing loops are discarded immediately
4. Eventually stable: After a finite number of message exchanges, all routers agree

Unlike distance vector, there is no count-to-infinity. If a destination becomes unreachable, the path is simply withdrawn—there's no incorrect distance to propagate.

The Algebraic Perspective:

Routing can be formally modeled using algebraic path problems over semirings. This is the theoretical foundation for understanding routing algorithm properties.

For path vector in BGP, the key algebraic properties are:

1. Path Algebra

• Elements: AS paths (sequences of ASNs)
• Operation: Path extension (prepending an AS)
• Preference: Policy-based ordering of paths

2. Isotonicity (Monotonicity) A routing protocol is isotonic if path preferences are preserved under extension. In other words, if path A is preferred over path B, then extending both through the same AS preserves the preference.

BGP is not always isotonic due to policy interactions. Different ASes may make different preference decisions. This is a feature (enabling policy) but can cause convergence problems (BGP oscillation).

3. Convergence Conditions (Gao-Rexford) If ASes follow certain policy guidelines based on their business relationships:

• Prefer customer routes over peer routes over provider routes
• Don't transit traffic between providers
• Export customer routes everywhere, peer routes only to customers

Then BGP is guaranteed to converge. Violations of these conditions can cause persistent routing oscillations.

One of path vector's greatest strengths is enabling policy-based routing. Unlike IGPs that optimize for shortest path, BGP allows each AS to make routing decisions based on arbitrary criteria.

Policy Decision Points:

BGP policy can be applied at several stages:

1. Import Policy (Inbound Filtering) When receiving routes from a neighbor:

• Accept or reject routes based on prefix, AS_PATH, or other attributes
• Modify attributes (set local preference, prepend AS_PATH, etc.)
• Apply route dampening or rate limiting

2. Best Path Selection When choosing among multiple routes to the same destination:

• Apply the BGP decision process with policy-influenced attributes
• Local preference typically reflects business relationships

3. Export Policy (Outbound Filtering) When advertising routes to a neighbor:

• Decide which routes to advertise based on relationship
• Modify attributes for the outgoing advertisement
• Prepend AS_PATH to make routes less attractive

Common Policy Patterns:

Path vector is not without limitations. Understanding these tradeoffs is essential for working effectively with BGP.

Information Hiding:

Path vector abstracts each AS to a single hop, regardless of internal complexity. This creates challenges:

The Shortest Path Fallacy:

BGP's default preference for shorter AS_PATHs assumes that fewer AS hops mean a better path. This is often false:

This is why operators use BGP communities, local preference manipulation, and other mechanisms to override the default path length preference.

The Convergence vs. Stability Tradeoff:

BGP deliberately converges slowly to prevent oscillations. The Minimum Route Advertisement Interval (MRAI) defaults to 30 seconds for eBGP, meaning a complete path change can take minutes to propagate globally. This is acceptable for the Internet (where stability matters more than speed) but can be problematic for real-time applications.

We have explored path vector routing from first principles. Let's consolidate the key insights:

What's Next:

In the next page, we will dive deep into the AS_PATH attribute—the heart of path vector routing in BGP. You will learn the detailed mechanics of AS_PATH propagation, AS_PATH manipulation for traffic engineering, AS_PATH length's role in best path selection, and how AS_PATH enables loop detection and policy enforcement.