Path Selection
Path Selection is the process by which network devices, such as routers, choose the best route for data to travel from a source to a destination across a network. This decision is based on information gathered by routing protocols and uses various metrics like speed, cost, and reliability to determine the most optimal path.
Late 1960s
3
Definitions
General Networking Context
Path Selection, or Route Selection, is a fundamental function performed by network routers. It involves analyzing all known paths to a destination and choosing the single best path to forward traffic. This chosen path is then installed into the routing table.
Key Concepts
- Routing Protocols: Devices learn about possible paths by using routing protocols (e.g., OSPF, EIGRP, RIP). These protocols exchange routing information with neighboring routers to build a map of the network topology.
- Metrics: Each routing protocol uses one or more metrics to measure the 'cost' or 'desirability' of a path. Common metrics include:
- Hop Count: The number of routers a packet must pass through (used by RIP).
- Bandwidth: The data capacity of a link (a key factor in OSPF and EIGRP).
- Delay: The time it takes for a packet to traverse a path.
- Reliability: A measure of the link's stability.
- Routing Table: The outcome of the Best Path Determination process is the routing table. This table is a database within the router that stores the best routes to various network destinations. When a packet arrives, the router consults this table to make its forwarding decision.
Border Gateway Protocol (BGP) Context
In the context of the global internet, Path Selection is most famously associated with the Border Gateway Protocol (BGP). Unlike interior protocols that use simple metrics, BGP's Best Path Determination is a complex, deterministic process based on a list of Path Attributes (PAs). This allows for granular policy control over how traffic flows between different networks (Autonomous Systems).
The BGP router evaluates attributes in a specific order until a single best path is found. The process stops as soon as a tie is broken.
Abbreviated BGP Path Selection Algorithm
- Highest WEIGHT: A Cisco-proprietary value, local to the router.
- Highest LOCAL_PREF: The most common attribute used to influence outbound traffic flow within an organization.
- Locally Originated: Paths originated by the local router are preferred.
- Shortest AS_PATH: The path that traverses the fewest Autonomous Systems.
- Lowest ORIGIN Type: Prefers paths learned from an interior gateway protocol (IGP) over those learned from an exterior one (EGP), and both over incomplete origins.
- Lowest MED (Multi-Exit Discriminator): Used to influence how a neighboring AS sends traffic into your AS.
- eBGP over iBGP: Prefers paths learned from external neighbors over internal ones.
This step-by-step process ensures that every BGP router in the world can independently and consistently arrive at the same Routing Decision for a given set of paths.
Software-Defined WAN (SD-WAN) Context
Modern SD-WAN solutions have revolutionized Path Selection by making it dynamic and application-aware. Traditional routing makes a Routing Decision based on static metrics and network addresses. SD-WAN elevates this by understanding the applications generating the traffic and the real-time performance of the available network paths.
Key Features
- Application-Aware Routing: SD-WAN identifies traffic by application (e.g., Microsoft 365, Zoom, Salesforce) and applies policies based on the application's requirements. For example, real-time voice traffic can be routed over a path with the lowest latency and jitter.
- Continuous Performance Monitoring: The SD-WAN controller continuously measures the health of all available WAN links (MPLS, broadband, 5G, etc.) for packet loss, latency, and jitter.
- Dynamic Path Selection: If a primary link's performance degrades, the SD-WAN solution can automatically and seamlessly reroute traffic for a specific application to a better-performing link without manual intervention. This ensures optimal application performance and user experience. For example, a video conference call might be moved from a choppy broadband link to a stable 5G connection mid-call to maintain quality.
Origin & History
Etymology
The term is a literal combination of 'Path', referring to a route or course through a network, and 'Selection', meaning the act of choosing. It directly describes the process of choosing a network route.
Historical Context
The concept of **Path Selection** is as old as computer networking itself, originating with the ARPANET in the late 1960s. Early routing protocols, like the Routing Information Protocol (RIP) developed in the 1970s, used a simple metric called hop count for their **Routing Decision**. The path with the fewest routers (hops) was considered the best. As networks grew more complex in the 1980s, the limitations of hop count became apparent. This led to the development of more sophisticated link-state protocols like Open Shortest Path First (OSPF). OSPF introduced the concept of 'cost', a metric typically based on link bandwidth, allowing for more intelligent **Route Selection** that prioritized faster links over simply shorter paths. The explosion of the internet required a protocol to manage routing between different autonomous systems (networks). The Border Gateway Protocol (BGP) was created in the late 1980s. BGP's **Best Path Determination** is not based on simple metrics but on a complex algorithm that evaluates a series of path attributes, enabling policy-based routing essential for the global internet. More recently, the rise of Software-Defined WAN (SD-WAN) has further evolved **Path Selection**, making it application-aware and dynamic, responding in real-time to network conditions.
Usage Examples
In BGP, the network administrator configured a higher local preference to influence Path Selection and force outbound traffic through the primary ISP.
The router's Routing Decision process evaluated two potential routes; the final Route Selection was based on the OSPF cost metric, which favored the higher bandwidth link.
SD-WAN technology automates Best Path Determination by continuously monitoring link quality and dynamically shifting application traffic to the optimal path.
Frequently Asked Questions
What is the primary goal of Path Selection in computer networking?
The primary goal of Path Selection is to find the most efficient and reliable route for data packets to travel from a source to a destination. This process, also known as Best Path Determination, aims to optimize network performance by considering various metrics such as bandwidth, latency, hop count, and cost, ensuring timely and successful data delivery.
What is the difference between a metric and an administrative distance in the context of Path Selection?
A metric is a value used by a single routing protocol to compare different routes to the same destination and determine the best one. For example, OSPF uses 'cost' (based on bandwidth) as its metric.
Administrative Distance (AD), however, is a value used by a router to choose between routes learned from different routing protocols. It represents the trustworthiness of the protocol. A lower AD value is preferred. For instance, if a router learns a route to a destination from both OSPF (AD 110) and RIP (AD 120), it will prefer the OSPF route because it has a lower, more trustworthy AD.