Path-vector routing protocol: Difference between revisions

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
VisualWikitext
Added links to other protocols, corrected terminology.
 
imported>BossyPirate
Expanded article with reliable sources, added internal links, corrected citation format using named <ref> tags, and clarified protocol details per Wikipedia guidelines.
 
Line 1: Line 1:
{{Short description|Routing algorithm methodology that allows dynamic updates}}
{{Short description|Routing algorithm methodology that allows dynamic updates}}
{{Unreferenced stub|auto=yes|date=December 2009}}
== 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 System (Internet)|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.<ref name="okeeffe">Dennis O’Keeffe. ''Path Vector Protocol''. Dennis O’Keeffe’s Protocol Notes.</ref><ref name="ucork">Creagh, C., et al. “An Interior Path Vector Routing Protocol.” University College Cork, 2006.</ref>


A '''path-vector routing protocol''' is a network [[routing protocol]] which maintains the path information that gets updated dynamically. Updates that have looped through the network and returned to the same node are easily detected and discarded. This algorithm is sometimes used in [[Bellman–Ford algorithm|Bellman–Ford routing algorithms]] to avoid "Count to Infinity" problems.
== 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.<ref name="stackexc">NetworkEngineering.SE. “What is the difference between distance vector protocol and path‑vector protocol?”</ref>


It is different from the [[distance vector routing]] and [[link state routing]]. Each entry in the routing table contains the destination network, the next router and the path to reach the destination.
== Core characteristics ==
* '''Path information''': Each entry contains full AS-path, next-hop, and policy attributes.<ref name="hpearuba">HPE Aruba Networking. “Using BGP path attributes.”</ref>
* '''Loop detection''': Routers discard updates containing their own AS in the AS_PATH.<ref name="cisco_cmt">Cisco Community. “BGP loop prevention with AS_PATH.”</ref>
* '''Policy-based routing''': Allows complex filtering, preferences, and attribute manipulation.<ref name="catchpoint">Catchpoint. “BGP Path Selection: Tutorial & Examples.”</ref>
* '''Scalability''': Suitable for large-scale networks (e.g., Internet), though convergence is slower compared to link-state protocols.<ref name="peipdf">Pei, D., Zhang, B., Massey, D., Zhang, L. “An Analysis of Path‑Vector Routing Protocol Convergence Algorithms.” UCLA CSD, 2004.</ref>


''[[Border Gateway Protocol]]'' (BGP) is an example of a path vector protocol.  In BGP, the [[Open_Shortest_Path_First#Autonomous_system_boundary_router|autonomous system boundary routers]] (ASBR) send path-vector messages to advertise the reachability of networks. Each router that receives a path vector message must verify the advertised path according to its policy. If the message complies with its policy, the router modifies its routing table and the message before sending the message to the next neighbor. It modifies the routing table to maintain the [[Autonomous system (Internet)|autonomous systems]] that are traversed in order to reach the destination system. It modifies the message to add its AS number and to replace the next router entry with its identification.
== Border Gateway Protocol (BGP) ==
The canonical implementation of a path-vector protocol is [[Border Gateway Protocol]] (BGP), used globally for inter-domain routing.<ref name="ciscopress">Cisco Press. “Operation of BGP: AS_PATH and Path‑vector nature.”</ref><ref name="jumpcloud">JumpCloud. “What is BGP (Border Gateway Protocol)?” May 12, 2025.</ref>


''[[Exterior Gateway Protocol]]'' (EGP) does not use path vectors.
=== 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:
# '''eBGP''': Between routers in different ASes.
# '''iBGP''': Within the same AS.<ref name="ciscopress"/>


It has three phases:  
=== Message attributes ===
# Initiation
Some key BGP path attributes are:
# Sharing
* '''AS_PATH''': Ordered list of AS numbers encoding the path. Used for loop prevention and best‑path selection.<ref name="hpearuba"/>
# Updating
* '''NEXT_HOP''': IP address for the next-hop.
* '''LOCAL_PREF''': Preference inside an AS.
* '''MED''': Multi Exit Discriminator – suggests preferred entry points to AS.<ref name="hpearuba"/>
* '''COMMUNITY''': Tag for policy grouping.<ref name="hpearuba"/>


BGP is commonly referred to as an Exterior Gateway Protocol (EGP) given its role in connecting Autonomous Systems (AS).  
=== 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 
<ref name="ciscopress"/>


Communication protocols within AS are therefore referred to as Interior Gateway Protocols (IGP) which contain [[Open Shortest Path First|OSPF]] and [[IS-IS]] among others.
== Advantages vs Limitations ==
=== Advantages ===
* Loop-free by design 
* Supports robust policy control 
* Scales over global Internet<ref name="catchpoint"/> 


This being said, BGP can be used within an AS, which typically occurs within very large organizations such as Facebook or Microsoft.
=== Limitations ===
* Slower convergence than link-state protocols 
* Large routing tables increase resource requirements 
* Susceptible to route flapping (mitigated via damping)<ref name="peipdf"/>


==See also==
== Research & enhancements ==
Academic work has improved understanding of convergence and stability:
* Papadimitriou et al. studied instability in path-vector protocols.<ref name="papadimitriou">Papadimitriou, D., Coras, F., Cabellos, A. “Path‑vector Routing Stability Analysis.” SIGMETRICS, 2011.</ref>
 
== 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.<ref name="netbeez">NetBeez. “Intro to Routing Protocols: A Beginner’s Guide.”</ref><ref name="jumpcloud"/>
 
== See also ==
* [[Distance vector routing]]
* [[Link-state routing protocol]]
* [[Link-state routing protocol]]
* [[Interior Gateway Protocol]]
* [[Network policy-based routing]]
== References ==
<references/>


{{DEFAULTSORT:Path Vector Protocol}}
{{DEFAULTSORT:Path Vector Protocol}}
[[Category:Routing protocols]]
[[Category:Routing protocols]]
{{Compu-network-stub}}
{{Compu-network-stub}}

Latest revision as of 12:09, 24 June 2025

Template:Short description

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

References

  1. ↑ Dennis O’Keeffe. Path Vector Protocol. Dennis O’Keeffe’s Protocol Notes.
  2. ↑ Creagh, C., et al. “An Interior Path Vector Routing Protocol.” University College Cork, 2006.
  3. ↑ NetworkEngineering.SE. “What is the difference between distance vector protocol and path‑vector protocol?”
  4. ↑ a b c d HPE Aruba Networking. “Using BGP path attributes.”
  5. ↑ Cisco Community. “BGP loop prevention with AS_PATH.”
  6. ↑ a b Catchpoint. “BGP Path Selection: Tutorial & Examples.”
  7. ↑ a b Pei, D., Zhang, B., Massey, D., Zhang, L. “An Analysis of Path‑Vector Routing Protocol Convergence Algorithms.” UCLA CSD, 2004.
  8. ↑ a b c Cisco Press. “Operation of BGP: AS_PATH and Path‑vector nature.”
  9. ↑ a b JumpCloud. “What is BGP (Border Gateway Protocol)?” May 12, 2025.
  10. ↑ Papadimitriou, D., Coras, F., Cabellos, A. “Path‑vector Routing Stability Analysis.” SIGMETRICS, 2011.
  11. ↑ NetBeez. “Intro to Routing Protocols: A Beginner’s Guide.”

Template:Asbox

Retrieved from "http://debianws.lexgopc.com/wiki143/index.php?title=Path-vector_routing_protocol&oldid=2069947"