Path-vector routing protocol

Overview

A path-vector routing protocol is a type of routing protocol that maintains entire route information as a sequence of intermediate nodes or Autonomous Systems (AS). This allows routers to detect and discard routing loops by checking for their own identifier in the advertised path, thereby avoiding the "count‑to‑infinity" problem common in distance-vector protocols.^[1][2]

Comparison with other protocols

Unlike distance vector routing protocols that advertise only distance, and link state routing protocols that distribute full topology maps, path-vector protocols share both the path (list of ASes) and associated attributes, enabling policy-based decisions. Loop prevention is intrinsic and enforced via path inspection.^[3]

Core characteristics

• Path information: Each entry contains full AS-path, next-hop, and policy attributes.^[4]
• Loop detection: Routers discard updates containing their own AS in the AS_PATH.^[5]
• Policy-based routing: Allows complex filtering, preferences, and attribute manipulation.^[6]
• Scalability: Suitable for large-scale networks (e.g., Internet), though convergence is slower compared to link-state protocols.^[7]

Border Gateway Protocol (BGP)

The canonical implementation of a path-vector protocol is Border Gateway Protocol (BGP), used globally for inter-domain routing.^[8][9]

Operation

BGP exchanges routing information via TCP port 179. It uses four primary message types—Open, Keepalive, Update, Notification—to establish sessions and carry routing updates. There are two main modes:

1. eBGP: Between routers in different ASes.
2. iBGP: Within the same AS.^[8]

Message attributes

Some key BGP path attributes are:

• AS_PATH: Ordered list of AS numbers encoding the path. Used for loop prevention and best‑path selection.^[4]
• NEXT_HOP: IP address for the next-hop.
• LOCAL_PREF: Preference inside an AS.
• MED: Multi Exit Discriminator – suggests preferred entry points to AS.^[4]
• COMMUNITY: Tag for policy grouping.^[4]

Path selection

BGP applies a multi-step decision process: 1. Highest weight (Cisco-specific) 2. Highest LOCAL_PREF 3. Prefer locally originated routes 4. Shortest AS_PATH 5. Lowest ORIGIN 6. Lowest MED 7. Prefer eBGP over iBGP 8. Lowest IGP cost to NEXT_HOP 9. Oldest path 10. Lowest BGP router ID ^[8]

Advantages vs Limitations

Advantages

• Loop-free by design
• Supports robust policy control
• Scales over global Internet^[6]

Limitations

• Slower convergence than link-state protocols
• Large routing tables increase resource requirements
• Susceptible to route flapping (mitigated via damping)^[7]

Research & enhancements

Academic work has improved understanding of convergence and stability:

• Papadimitriou et al. studied instability in path-vector protocols.^[10]

Usage within AS

Though primarily used as an Exterior Gateway Protocol (EGP), BGP is also deployed internally as iBGP in large organizations (e.g., ISPs, Facebook, Microsoft) to manage complex routing policies.^[11][9]

See also

• Distance vector routing
• Link-state routing protocol
• Interior Gateway Protocol
• Network policy-based routing