Path Vector Routing

When you send a packet across the internet, it may traverse dozens of autonomous systems—independent networks operated by ISPs, enterprises, content providers, and government organizations—before reaching its destination. How does each router along the way know not just the next hop, but the complete path through these interconnected networks?

Path vector routing provides the answer. Unlike distance vector protocols that share only cost metrics, or link state protocols that share raw topology data, path vector routing propagates the complete sequence of autonomous systems (AS path) that a packet must traverse to reach each destination. This seemingly simple enhancement transforms how the internet operates, enabling sophisticated routing policies, bulletproof loop prevention, and the remarkable flexibility that allows 70,000+ autonomous systems to cooperate in delivering global connectivity.

Path information is the defining characteristic of path vector routing protocols. Rather than advertising just a destination and a cost (like RIP's hop count) or broadcasting the complete topology (like OSPF's link state advertisements), path vector protocols propagate the entire sequence of autonomous systems through which a route advertisement has passed.

The AS Path Concept:

An AS path is an ordered list of Autonomous System Numbers (ASNs) representing every network that route information has traversed. When a router advertises a route to its neighbors:

1. It prepends its own ASN to the beginning of the path
2. The receiving router sees the complete chain of ASNs
3. This chain reveals exactly how to reach the destination—and through whom

Consider a route advertisement for prefix 192.0.2.0/24:

Destination: 192.0.2.0/24
AS Path: 65001 65010 65020 65030

This tells the receiving router: "To reach 192.0.2.0/24, packets will traverse AS 65001, then AS 65010, then AS 65020, and finally arrive at AS 65030 where the prefix originates."

What Makes Path Information Unique:

Path information fundamentally differs from other routing information types:

The verbosity of path vector is intentional—it trades bandwidth efficiency for routing intelligence. Each router can make decisions based on who the traffic will traverse, not just how many hops or what abstract cost.

AS paths in BGP are not simple lists—they're structured data types that support sophisticated aggregation and confederations. Understanding this structure is essential for interpreting real-world routing information.

AS_SEQUENCE vs AS_SET:

BGP represents AS paths using two segment types:

1. AS_SEQUENCE: An ordered list where position matters. Most AS paths consist entirely of AS_SEQUENCE segments, representing the exact traversal order.

2. AS_SET: An unordered collection of ASNs, typically created during route aggregation when multiple paths are combined. When routes from ASNs 65001, 65002, and 65003 are aggregated, they may appear as a set {65001, 65002, 65003} rather than a sequence.

Why This Matters:

AS_SET segments complicate loop detection. If your ASN appears in an AS_SET, you know the route has some relationship to your network, but you can't determine the exact path. Modern best practices discourage AS_SET usage because it weakens the security and determinism that make path vector routing valuable.

AS Path Length:

The AS path length is a critical metric in path selection. BGP prefers shorter AS paths, under the assumption that fewer AS hops generally mean:

• Lower latency (fewer routing decisions)
• Higher reliability (fewer points of failure)
• More direct connectivity

However, AS path length is measured in ASNs, not actual router hops. A single AS might span continents with hundreds of internal routers, while another might have just one. This creates an important distinction:

AS Path Length ≠ Physical Distance ≠ Latency

Organizations exploit this through AS path prepending—artificially lengthening the path by including their own ASN multiple times. This makes a route less attractive without affecting the actual forwarding path:

Original:   AS_PATH: 65001 65010 65020        (length: 3)
Prepended:  AS_PATH: 65001 65001 65001 65010 65020  (length: 5)

The prepended route is less likely to be selected, enabling coarse-grained traffic engineering.

Understanding how path information flows through the internet reveals the mechanics that enable global routing. Let's trace a route advertisement from origin to global visibility.

The Propagation Process:

Step 1: Origin AS Injects the Route

An organization (let's say AS 65030) originates a prefix. They configure BGP to advertise 192.0.2.0/24 with:

• AS_PATH: 65030 (just themselves—the origin)
• NEXT_HOP: Their router's IP
• ORIGIN: IGP (learned from internal routing)

Step 2: Neighboring AS Receives and Processes

AS 65020 (a direct peer of AS 65030) receives the advertisement:

1. Validates the route (checks for loops, policy compliance)
2. Prepends its own ASN: AS_PATH becomes 65020 65030
3. Applies its own attributes (local preference, communities)
4. Advertises to its neighbors with the updated path

Step 3: Transit AS Continues Propagation

AS 65010 (a transit provider) receives from AS 65020:

1. Prepends its ASN: AS_PATH becomes 65010 65020 65030
2. Advertises to all customers and peers (based on policy)
3. Each recipient repeats the process

Step 4: Global Visibility Achieved

Within minutes (typically under 5 minutes for normal propagation), the route is known across the global routing table, with each AS having its own view based on its position in the topology.

eBGP vs iBGP Path Handling:

Path information behaves differently depending on whether it's exchanged between ASNs (eBGP) or within an AS (iBGP):

The fact that iBGP doesn't modify the AS path is crucial—it means the AS path represents the inter-domain path, not internal routing details. This abstraction is what makes path vector routing scalable: internal topology changes don't trigger global reconvergence.

When a BGP router learns multiple paths to the same destination, it must select the best path for installation in the routing table. This selection process uses path information—particularly the AS path—as a key factor, but within a carefully ordered hierarchy of attributes.

The BGP Decision Algorithm:

BGP evaluates paths through a deterministic sequence of tiebreakers. The process stops as soon as a single best path is identified:

Path Information's Role:

Notice that AS path length is evaluated at step 4—after weight, local preference, and local origination. This means:

• Operators can override AS path length with higher-priority attributes
• Path length matters only when higher attributes are equal
• A 10-AS path with high local preference beats a 1-AS path with lower preference

This design is intentional. It allows network operators to implement policy-based routing while still using path length as a sensible default when no explicit policy applies.

Practical Example:

Consider an enterprise (AS 65001) receiving routes to 8.8.8.0/24 (Google DNS) from two upstream providers:

Despite Provider A's path being shorter (2 ASNs vs 4 ASNs), Provider B is selected because local preference (150 > 100) is evaluated before AS path length. The enterprise has explicitly indicated they prefer Provider B—perhaps due to cost, peering agreements, or performance characteristics unknown to BGP.

Understanding why path vector routing uses complete path information—rather than simple distance metrics—requires examining the fundamental problem of inter-domain routing.

The Distance Vector Problem:

In distance vector protocols like RIP, routers share (destination, cost) pairs. This is simple and efficient, but it creates a critical vulnerability: routers have no visibility into the actual path. They trust their neighbors' advertised costs without understanding the route's structure.

This lack of visibility enables:

1. Routing Loops: Without knowing the path, a router may advertise a route back to its source, creating circular advertisements
2. Count-to-Infinity: When a destination becomes unreachable, routers slowly increment their costs without realizing they're counting toward each other
3. Slow Convergence: Techniques like split horizon and poison reverse mitigate but don't fully solve these issues

Why the Verbosity is Worth It:

Path vector's approach—including the entire AS path in every advertisement—seems wasteful compared to a simple integer cost. But at internet scale, this trade-off is essential:

1. Trust Boundaries: The internet is a network of networks with no central authority. Each AS operates under different management, policies, and incentives. Path information allows you to make decisions based on whose networks traffic will traverse, not just how many.

2. Policy Requirements: Organizations have legitimate reasons to route traffic through (or away from) specific networks:

• Legal requirements (data sovereignty, sanctions compliance)
• Performance optimization (known problematic ASNs)
• Business relationships (prefer customers, then peers, then paid transit)
• Security concerns (avoid networks with poor track records)

3. Debugging and Visibility: When something goes wrong, path information provides immediate diagnostic value. "Why is my traffic going through that AS?" can be answered by examining the path, not guessing from metrics.

4. Guaranteed Loop Freedom: This alone justifies the overhead. No amount of split horizon or route poisoning matches the certainty of: "If my ASN is in this path, I'm already in the loop—drop the advertisement."

While the AS path is the signature feature of path vector routing, BGP includes numerous additional path attributes that enrich routing decisions. These attributes work together with path information to provide comprehensive route characterization.

Well-Known Mandatory Attributes:

Every BGP UPDATE must include these attributes:

Well-Known Discretionary Attributes:

Important but not always present:

Optional Transitive Attributes:

Carried through even if not understood:

Communities: The Policy Workhorse:

BGP communities deserve special attention. These 32-bit tags (or 96-bit for large communities) enable operators to mark routes with arbitrary metadata that downstream networks can use for policy decisions.

Common community patterns:

Well-Known Communities:
  NO_EXPORT (0xFFFFFF01): Don't advertise outside AS
  NO_ADVERTISE (0xFFFFFF02): Don't advertise to any peer
  NO_PEER (0xFFFFFF03): Don't advertise to peers (only customers/transit)

Operator-Defined (format: ASN:value):
  65001:100 - Learned from customer
  65001:200 - Learned from peer
  65001:300 - Learned from transit
  65001:1000 - Prepend 1x when advertising to AS 65010
  65001:2000 - Blackhole this prefix

Communities transform BGP from a simple path exchange protocol into a sophisticated policy signaling system. Combined with path information, they enable:

• Inbound traffic engineering: Signal preferences to upstream providers
• Selective advertisement: Control where routes propagate
• Blackhole routing: DDoS mitigation by dropping traffic at network edge
• Route coloring: Track where routes were learned for internal policy

Understanding path information in theory is valuable, but operators need practical skills for examining real routing data. Let's explore how to inspect and interpret path information in operational environments.

Viewing BGP Routes:

On Cisco IOS, the fundamental command is show ip bgp:

Router# show ip bgp 8.8.8.0/24
BGP routing table entry for 8.8.8.0/24, version 12345
Paths: (3 available, best #1)
  Advertised to update-groups:
     1
  15169
    192.168.1.1 from 192.168.1.1 (10.0.0.1)
      Origin IGP, localpref 100, valid, external, best
      Community: 65001:100
  65010 15169
    192.168.2.1 from 192.168.2.1 (10.0.0.2)
      Origin IGP, localpref 100, valid, external
  65020 65030 15169
    192.168.3.1 from 192.168.3.1 (10.0.0.3)
      Origin IGP, localpref 80, valid, external

This output reveals:

• Three paths to Google's DNS prefix
• Path 1 (best): Direct peering with AS 15169 (Google)
• Path 2: Via AS 65010, then to Google
• Path 3: Via two transit ASNs, with lower local preference

AS Path Regular Expressions:

BGP implementations support regular expressions for powerful path filtering. Understanding these patterns is essential for operations:

The underscore _ matches any AS path delimiter (space, start, or end of path), ensuring you match complete ASNs, not substrings.

Path information is the conceptual breakthrough that makes internet-scale routing possible. By sharing the complete sequence of autonomous systems rather than abstract metrics, path vector routing provides the visibility, policy flexibility, and loop prevention that the global internet requires.

Key Concepts Mastered:

What's Next:

With a solid understanding of path information, we turn to one of its most powerful applications: loop prevention. The next page explores how the simple rule of "reject if my ASN is in the path" provides mathematically guaranteed loop freedom—a property that distance vector protocols can only approximate.