In computer networks, data packets are transferred from one network to another through routers. When a packet needs to travel across multiple networks, routers must select a suitable path to forward the packet toward its destination.
Different routing algorithms are used to determine these paths. One important routing algorithm used for communication between large networks is the Path Vector Routing Algorithm.
Path Vector Routing is mainly used to exchange routing information between different Autonomous Systems (AS) on the Internet. It provides information about the complete path that a packet may follow to reach a destination network.
Unlike Distance Vector Routing, which mainly maintains distance and next-hop information, Path Vector Routing maintains the complete path of Autonomous Systems through which a destination can be reached.
The Border Gateway Protocol (BGP) is the most important example of a path-vector routing protocol. It is widely used to exchange routing information between Internet service providers and large organizations.
What Is Path Vector Routing Algorithm?
Path Vector Routing is a dynamic routing algorithm in which routers advertise destination networks along with the complete path of Autonomous Systems (AS) that must be traversed to reach those destinations.
In this algorithm, routing information is shared between neighboring routers along with the sequence of Autonomous Systems through which the route passes.
When a router receives routing information, it examines the advertised path and selects a suitable route based on routing policies and path attributes.
It also helps prevent routing loops by checking whether its own Autonomous System number is already present in the advertised path.
Path Vector Routing is mainly used for communication between different Autonomous Systems on the Internet.
Important Terms Used in Path Vector Routing
Before understanding the working of Path Vector Routing, it is important to understand the following terms.
1. Autonomous System (AS)
An Autonomous System is a collection of one or more IP networks managed by a single organization under a common routing policy.
Each Autonomous System is identified by a unique Autonomous System Number (ASN).
For example, an Internet Service Provider may operate an Autonomous System to manage its network and exchange routing information with other networks.
2. Path Vector
A Path Vector is a list of Autonomous System numbers that represents the path through which a destination network can be reached.
For example:
AS100 → AS200 → AS300
This path indicates that data travelling from AS100 to a destination in AS300 may pass through AS200.
3. Border Gateway Protocol (BGP)
BGP stands for Border Gateway Protocol. It is a path-vector routing protocol used to exchange routing information between different Autonomous Systems.
It helps routers select routes based on path information and routing policies.
BGP is one of the most important protocols used for routing traffic across the Internet.
4. Routing Table
A routing table is a collection of routing information maintained by a router.
In Path Vector Routing, routing information includes the destination network, AS path, and other path attributes used to select a suitable route.
5. AS Path
AS Path is an important BGP path attribute that contains the sequence of Autonomous Systems through which a route has passed.
It helps routers understand the path to a destination and detect routing loops.
For example, an AS Path such as:
AS200 → AS300 → AS400
indicates that the advertised route passes through these Autonomous Systems.
Working of Path Vector Routing Algorithm
Path Vector Routing works by exchanging destination information along with the complete AS path between neighboring routers.
The working process can be explained through the following steps:
Step 1: Route Advertisement
Initially, an Autonomous System advertises the networks that it can reach to its neighboring Autonomous Systems.
The advertisement contains the destination network and relevant routing information.
Step 2: Receiving Routing Information
The neighboring router receives the route advertisement and examines the destination network and the advertised AS path.
It stores the received routing information for further processing.
Step 3: Adding the AS Number
When a router advertises a route to another Autonomous System, its own AS number is added to the AS Path attribute.
This helps identify the sequence of Autonomous Systems through which the route has travelled.
Step 4: Checking for Routing Loops
Before accepting a route, the router checks whether its own Autonomous System number is already present in the advertised AS path.
If its own AS number is present, the router rejects the route because accepting it could create a routing loop.
Step 5: Selecting the Best Route
If multiple routes are available to reach the same destination, the router evaluates them using BGP path attributes and routing policies.
It may consider factors such as:
- Local Preference.
- AS Path length.
- Origin type.
- MED (Multi-Exit Discriminator).
- Other BGP path attributes.
The router selects the most suitable route according to its configured policies and BGP decision process.
Step 6: Advertising the Selected Route
After selecting a route, the router advertises the destination and updated AS Path information to its neighboring Autonomous Systems, subject to routing policies.
Step 7: Forwarding Data Packets
After the routing information is established, routers use their routing and forwarding tables to send packets toward the selected destination.
In this way, Path Vector Routing supports communication between different Autonomous Systems.
Example of Path Vector Routing Algorithm
Consider a network containing four Autonomous Systems: AS100, AS200, AS300, and AS400.
Suppose AS100 wants to communicate with a destination network located in AS300.
There are two possible paths:
- Path 1: AS100 → AS200 → AS300
- Path 2: AS100 → AS400 → AS200 → AS300
The objective is to select a suitable route using Path Vector Routing.
Step 1: Destination Network Advertisement
Suppose AS300 owns a destination network called Network N.
AS300 advertises Network N to its neighboring Autonomous Systems with the following AS Path:
AS Path: AS300
This indicates that Network N is directly originated by AS300.
Step 2: Advertisement Through AS200
AS200 receives the advertisement from AS300.
It adds its own AS number to the AS Path before advertising the route to AS100.
The updated AS Path becomes:
AS Path: AS200 → AS300
Now AS100 learns that Network N can be reached through AS200.
Step 3: Advertisement Through AS400
AS400 also receives the route information through another network connection.
It adds its own AS number to the advertised path.
The AS Path becomes:
AS Path: AS400 → AS200 → AS300
This route is also advertised toward AS100.
Step 4: Route Comparison
Now AS100 receives two possible routes to reach Network N.
| Route | AS Path | AS Path Length |
|---|---|---|
| Path 1 | AS200 → AS300 | 2 |
| Path 2 | AS400 → AS200 → AS300 | 3 |
If all higher-priority BGP attributes and routing policies are equal, AS100 may prefer Path 1 because it has a shorter AS Path.
Therefore, AS100 selects the route through AS200 to reach Network N.
Important: BGP does not always select the route with the shortest AS Path. It follows a decision process based on several attributes and routing policies. A shorter AS Path may be preferred when the other relevant selection criteria are equal.
Step 5: Routing Loop Prevention
Suppose AS200 receives an advertisement containing the following path:
AS200 → AS300
If this advertisement is received back by AS200, it checks the AS Path and finds its own AS number (AS200) in the path.
Therefore, AS200 rejects the route.
This prevents the routing information from circulating continuously and helps avoid routing loops.
Final Result
After comparing the available paths, AS100 selects the suitable route to Network N according to its routing policies.
The selected path is:
AS100 → AS200 → AS300
Thus, Path Vector Routing helps Autonomous Systems exchange routing information, compare available paths, and select appropriate routes while preventing routing loops.
Characteristics of Path Vector Routing Algorithm
The important characteristics of Path Vector Routing are:
- Complete Path Information: It maintains the sequence of Autonomous Systems through which a destination network can be reached.
- Policy-Based Routing: It allows network administrators to select routes based on organizational requirements and routing policies.
- Loop Prevention: It helps prevent routing loops by checking whether an Autonomous System number is already present in the AS Path.
- Inter-Domain Routing: It is mainly used for exchanging routing information between different Autonomous Systems.
- Dynamic Route Updates: Routing information is updated when network reachability or routing policies change.
- Scalability: It supports communication between a large number of independent networks across the Internet.
- BGP Support: It is implemented by the Border Gateway Protocol.
Advantages of Path Vector Routing Algorithm
Path Vector Routing provides several advantages in computer networks.
- Prevents Routing Loops: It uses the AS Path attribute to identify and reject routes that contain the receiving Autonomous System number.
- Supports Large Networks: It is suitable for communication between large and geographically distributed networks.
- Policy-Based Routing: Network administrators can control route selection according to their requirements.
- Provides Complete Path Information: It gives information about the sequence of Autonomous Systems through which a destination can be reached.
- Flexible Route Selection: It allows different routes to be selected based on path attributes and administrative policies.
- Supports Internet Communication: It plays an important role in connecting different Autonomous Systems across the Internet.
Disadvantages of Path Vector Routing Algorithm
Although Path Vector Routing is useful for large networks, it also has certain limitations.
- Complex Configuration: Configuring and managing routing policies can be difficult.
- Higher Processing Requirements: Routers need to process and evaluate multiple path attributes while selecting routes.
- Large Routing Information: Maintaining routing information for a large number of destination networks requires memory.
- Convergence Delay: Changes in network routes may take time to propagate across different Autonomous Systems.
- Policy Configuration Errors: Incorrect routing policies may result in inefficient route selection or connectivity problems.
- Complex Route Selection: Selecting the best route may require evaluating several path attributes rather than simply choosing the shortest path.
Applications of Path Vector Routing Algorithm
Path Vector Routing is mainly used in large networks that require communication between different Autonomous Systems.
Some important applications include:
1. Internet Service Providers
Internet Service Providers use BGP to exchange routing information with other service providers and connect their networks to the Internet.
2. Large Organizations
Large organizations with multiple networks can use BGP to manage communication with external networks and Internet service providers.
3. Internet Routing
Path Vector Routing plays an important role in determining how traffic travels between different Autonomous Systems across the Internet.
4. Multihomed Networks
Organizations connected to more than one Internet Service Provider can use BGP to manage multiple external connections and select routes according to their routing policies.
5. Inter-Domain Communication
It enables different independently managed networks to exchange routing information and communicate with one another.
Example of Path Vector Routing Protocol – BGP
BGP stands for Border Gateway Protocol. It is the most widely used protocol that implements the Path Vector Routing approach.
It is responsible for exchanging routing information between different Autonomous Systems.
BGP helps routers select suitable routes based on AS Path information, routing policies, and other path attributes.
Important features of BGP include:
- It is a path-vector routing protocol.
- It exchanges routing information between Autonomous Systems.
- It uses the AS Path attribute for loop prevention.
- It supports policy-based route selection.
- It is designed for large-scale Internet routing.
- It supports multiple possible routes to the same destination.
BGP is mainly used for communication between Internet Service Providers and large organizations connected to the Internet.
Difference Between Distance Vector, Link State, and Path Vector Routing
Distance Vector, Link State, and Path Vector are three important routing approaches used in computer networks. They differ in how routing information is collected, shared, and used to select paths.
| Basis | Distance Vector | Link State | Path Vector |
|---|---|---|---|
| Meaning | Uses distance and next-hop information | Uses complete network topology information | Uses the complete AS path to a destination |
| Information Shared | Routing information with neighbors | Link State Advertisements | Destination networks and AS Path information |
| Main Algorithm | Bellman-Ford | Dijkstra’s SPF | BGP path-selection process |
| Network Knowledge | Learns routes from neighbors | Builds a topology database | Maintains AS path information |
| Loop Prevention | Uses techniques such as split horizon and poison reverse in some protocols | Uses topology and SPF calculations | Checks the AS Path for its own AS number |
| Route Selection | Based on routing metrics | Based on link costs | Based on routing policies and path attributes |
| Main Usage | Routing within smaller networks | Routing within an autonomous system | Routing between autonomous systems |
| Example Protocol | RIP | OSPF | BGP |