Hubbry Logo
RoutingRoutingMain
Open search
Routing
Community hub
Routing
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Routing
Routing
Routing
View on Wikipedia
from Wikipedia

Routing is the process of selecting a path for traffic in a network or between or across multiple networks. Broadly, routing is performed in many types of networks, including circuit-switched networks, such as the public switched telephone network (PSTN), and computer networks, such as the Internet.

In packet switching networks, routing is the higher-level decision-making that directs network packets from their source toward their destination through intermediate network nodes by specific packet forwarding mechanisms. Packet forwarding is the transit of network packets from one network interface to another. Intermediate nodes are typically network hardware devices such as routers, gateways, firewalls, or switches. General-purpose computers also forward packets and perform routing, although they have no specially optimized hardware for the task.

The routing process usually directs forwarding on the basis of routing tables. Routing tables maintain a record of the routes to various network destinations. Routing tables may be specified by an administrator, learned by observing network traffic or built with the assistance of routing protocols.

Routing, in a narrower sense of the term, often refers to IP routing and is contrasted with bridging. IP routing assumes that network addresses are structured and that similar addresses imply proximity within the network. Structured addresses allow a single routing table entry to represent the route to a group of devices. In large networks, structured addressing (routing, in the narrow sense) outperforms unstructured addressing (bridging). Routing has become the dominant form of addressing on the Internet. Bridging is still widely used within local area networks.

Delivery schemes

[edit]
Routing schemes
Unicast

Broadcast

Multicast

Anycast

Routing schemes differ in how they deliver messages:

  • Unicast delivers a message to a single specific node using a one-to-one association between a sender and destination: each destination address uniquely identifies a single receiver endpoint.
  • Broadcast delivers a message to all nodes in the network using a one-to-all association; a single datagram (or packet) from one sender is routed to all of the possibly multiple endpoints associated with the broadcast address. The network automatically replicates datagrams as needed to reach all the recipients within the scope of the broadcast, which is generally an entire network subnet.
  • Multicast delivers a message to a group of nodes that have expressed interest in receiving the message using a one-to-many-of-many or many-to-many-of-many association; datagrams are routed simultaneously in a single transmission to many recipients. Multicast differs from broadcast in that the destination address designates a subset, not necessarily all, of the accessible nodes.
  • Anycast delivers a message to any one out of a group of nodes, typically the one nearest to the source using a one-to-one-of-many[1] association where datagrams are routed to any single member of a group of potential receivers that are all identified by the same destination address. The routing algorithm selects the single receiver from the group based on which is the nearest according to some distance or cost measure.

Unicast is the dominant form of message delivery on the Internet. This article focuses on unicast routing algorithms.

Topology distribution

[edit]

With static routing, small networks may use manually configured routing tables. Larger networks have complex topologies that can change rapidly, making the manual construction of routing tables unfeasible. Nevertheless, most of the public switched telephone network (PSTN) uses pre-computed routing tables, with fallback routes if the most direct route becomes blocked (see routing in the PSTN).

Dynamic routing attempts to solve this problem by constructing routing tables automatically, based on information carried by routing protocols, allowing the network to act nearly autonomously in avoiding network failures and blockages. Dynamic routing dominates the Internet. Examples of dynamic-routing protocols and algorithms include Routing Information Protocol (RIP), Open Shortest Path First (OSPF) and Enhanced Interior Gateway Routing Protocol (EIGRP).

Distance vector algorithms

[edit]
Main article: Distance-vector routing protocol

Distance vector algorithms use the Bellman–Ford algorithm. This approach assigns a cost number to each of the links between each node in the network. Nodes send information from point A to point B via the path that results in the lowest total cost (i.e., the sum of the costs of the links between the nodes used).

When a node first starts, it only knows of its immediate neighbors and the direct cost involved in reaching them. (This information — the list of destinations, the total cost to each, and the next hop to send data to get there — makes up the routing table, or distance table.) Each node, on a regular basis, sends to each neighbor node its own current assessment of the total cost to get to all the destinations it knows of. The neighboring nodes examine this information and compare it to what they already know; anything that represents an improvement on what they already have, they insert in their own table. Over time, all the nodes in the network discover the best next hop and total cost for all destinations.

When a network node goes down, any nodes that used it as their next hop discard the entry and convey the updated routing information to all adjacent nodes, which in turn repeat the process. Eventually, all the nodes in the network receive the updates and discover new paths to all the destinations that do not involve the down node.

[edit]
Main article: Link-state routing protocol

When applying link-state algorithms, a graphical map of the network is the fundamental data used for each node. To produce its map, each node floods the entire network with information about the other nodes it can connect to. Each node then independently assembles this information into a map. Using this map, each router independently determines the least-cost path from itself to every other node using a standard shortest paths algorithm such as Dijkstra's algorithm. The result is a tree graph rooted at the current node, such that the path through the tree from the root to any other node is the least-cost path to that node. This tree then serves to construct the routing table, which specifies the best next hop to get from the current node to any other node.

[edit]
Main article: Optimized Link State Routing Protocol

A link-state routing algorithm optimized for mobile ad hoc networks is the optimized Link State Routing Protocol (OLSR).[2] OLSR is proactive; it uses Hello and Topology Control (TC) messages to discover and disseminate link-state information through the mobile ad hoc network. Using Hello messages, each node discovers 2-hop neighbor information and elects a set of multipoint relays (MPRs). MPRs distinguish OLSR from other link-state routing protocols.

Path-vector protocol

[edit]
Main article: Path-vector routing protocol

Distance vector and link-state routing are both intra-domain routing protocols. They are used inside an autonomous system, but not between autonomous systems. Both of these routing protocols become intractable in large networks and cannot be used in inter-domain routing. Distance vector routing is subject to instability if there are more than a few hops in the domain. Link-state routing needs significant resources to calculate routing tables. It also creates heavy traffic due to flooding.

Path-vector routing is used for inter-domain routing. It is similar to distance vector routing. Path-vector routing assumes that one node (there can be many) in each autonomous system acts on behalf of the entire autonomous system. This node is called the speaker node. The speaker node creates a routing table and advertises it to neighboring speaker nodes in neighboring autonomous systems. The idea is the same as distance vector routing except that only speaker nodes in each autonomous system can communicate with each other. The speaker node advertises the path, not the metric, of the nodes in its autonomous system or other autonomous systems.

The path-vector routing algorithm is similar to the distance vector algorithm in the sense that each border router advertises the destinations it can reach to its neighboring router. However, instead of advertising networks in terms of a destination and the distance to that destination, networks are advertised as destination addresses and path descriptions to reach those destinations. The path, expressed in terms of the domains (or confederations) traversed so far, is carried in a special path attribute that records the sequence of routing domains through which the reachability information has passed. A route is defined as a pairing between a destination and the attributes of the path to that destination, thus the name, path-vector routing; The routers receive a vector that contains paths to a set of destinations.[3]

Path selection

[edit]

Path selection involves applying a routing metric to multiple routes to select (or predict) the best route. Most routing algorithms use only one network path at a time. Multipath routing and specifically equal-cost multi-path routing techniques enable the use of multiple alternative paths.

In computer networking, the metric is computed by a routing algorithm, and can cover information such as bandwidth, network delay, hop count, path cost, load, maximum transmission unit, reliability, and communication cost.[4] The routing table stores only the best possible routes, while link-state or topological databases may store all other information as well.

In case of overlapping or equal routes, algorithms consider the following elements in priority order to decide which routes to install into the routing table:

  1. Prefix length: A matching route table entry with a longer subnet mask is always preferred as it specifies the destination more exactly.
  2. Metric: When comparing routes learned via the same routing protocol, a lower metric is preferred. Metrics cannot be compared between routes learned from different routing protocols.
  3. Administrative distance: When comparing route table entries from different sources, such as different routing protocols and static configuration, a lower administrative distance indicates a more reliable source and thus a preferred route.

Because a routing metric is specific to a given routing protocol, multi-protocol routers must use some external heuristic to select between routes learned from different routing protocols. Cisco routers, for example, attribute a value known as the administrative distance to each route, where smaller administrative distances indicate routes learned from a protocol assumed to be more reliable.

A local administrator can set up host-specific routes that provide more control over network usage, permit testing, and better overall security. This is useful for debugging network connections or routing tables.

In some small systems, a single central device decides ahead of time the complete path of every packet. In some other small systems, whichever edge device injects a packet into the network decides ahead of time the complete path of that particular packet. In either case, the route-planning device needs to know a lot of information about what devices are connected to the network and how they are connected to each other. Once it has this information, it can use an algorithm such as A* search algorithm to find the best path.

In high-speed systems, there are so many packets transmitted every second that it is infeasible for a single device to calculate the complete path for each and every packet. Early high-speed systems dealt with this with circuit switching by setting up a path once for the first packet between some source and some destination; later packets between that same source and that same destination continue to follow the same path without recalculating until the circuit teardown. Later high-speed systems inject packets into the network without any one device ever calculating a complete path for packets.

In large systems, there are so many connections between devices, and those connections change so frequently, that it is infeasible for any one device to even know how all the devices are connected to each other, much less calculate a complete path through them. Such systems generally use next-hop routing.

Most systems use a deterministic dynamic routing algorithm. When a device chooses a path to a particular final destination, that device always chooses the same path to that destination until it receives information that makes it think some other path is better.

A few routing algorithms do not use a deterministic algorithm to find the best link for a packet to get from its original source to its final destination. Instead, to avoid congestion hot spots in packet systems, a few algorithms use a randomized algorithm—Valiant's paradigm—that routes a path to a randomly picked intermediate destination, and from there to its true final destination.[5][6] In many early telephone switches, a randomizer was often used to select the start of a path through a multistage switching fabric.

Depending on the application for which path selection is performed, different metrics can be used. For example, for web requests, one can use minimum latency paths to minimize web page load time, or for bulk data transfers, one can choose the least utilized path to balance load across the network and increase throughput. A popular path selection objective is to reduce the average completion times of traffic flows and the total network bandwidth consumption. Recently, a path selection metric was proposed that computes the total number of bytes scheduled on the edges per path as a selection metric.[7] An empirical analysis of several path selection metrics, including this new proposal, has been made available.[8]

Multiple agents

[edit]

In some networks, routing is complicated by the fact that no single entity is responsible for selecting paths; instead, multiple entities are involved in selecting paths or even parts of a single path. Complications or inefficiency can result if these entities choose paths to optimize their own objectives, which may conflict with the objectives of other participants.

A classic example involves traffic in a road system, in which each driver picks a path that minimizes their travel time. With such routing, the equilibrium routes can be longer than optimal for all drivers. In particular, Braess's paradox shows that adding a new road can lengthen travel times for all drivers.

In a single-agent model used, for example, for routing automated guided vehicles (AGVs) on a terminal, reservations are made for each vehicle to prevent simultaneous use of the same part of an infrastructure. This approach is also referred to as context-aware routing.[9]

The Internet is partitioned into autonomous systems (ASs) such as internet service providers (ISPs), each of which controls routes involving its network. Routing occurs at multiple levels. First, AS-level paths are selected via the BGP protocol that produces a sequence of ASs through which packets flow. Each AS may have multiple paths, offered by neighboring ASs, from which to choose. These routing decisions often correlate with business relationships with these neighboring ASs,[10] which may be unrelated to path quality or latency. Second, once an AS-level path has been selected, there are often multiple corresponding router-level paths to choose from. This is due, in part, because two ISPs may be connected through multiple connections. In choosing the single router-level path, it is common practice for each ISP to employ hot-potato routing: sending traffic along the path that minimizes the distance through the ISP's own network—even if that path lengthens the total distance to the destination.

For example, consider two ISPs, A and B. Each has a presence in New York, connected by a fast link with latency 5 ms—and each has a presence in London connected by a 5 ms link. Suppose both ISPs have trans-Atlantic links that connect their two networks, but A's link has latency 100 ms and B's has latency 120 ms. When routing a message from a source in A's London network to a destination in B's New York network, A may choose to immediately send the message to B in London. This saves A the work of sending it along an expensive trans-Atlantic link, but causes the message to experience latency 125 ms when the other route would have been 20 ms faster.

Additionally, a similar routing challenge can be observed in cellular networks, where different packets are destined for various endpoints, and each link exhibits varying spectral efficiency. In this context, the selection of the optimal path involves considering latency and packet error rate. To address this, multiple independent entities, one for each base station, play a crucial role in path selection while striving to optimize overall network performance.[11]

A 2003 measurement study of Internet routes found that, between pairs of neighboring ISPs, more than 30% of paths have inflated latency due to hot-potato routing, with 5% of paths being delayed by at least 12 ms. Inflation due to AS-level path selection, while substantial, was attributed primarily to BGP's lack of a mechanism to directly optimize for latency, rather than to selfish routing policies. It was also suggested that, were an appropriate mechanism in place, ISPs would be willing to cooperate to reduce latency rather than use hot-potato routing.[12] Such a mechanism was later published by the same authors, first for the case of two ISPs[13] and then for the global case.[14]

Route analytics

[edit]

As the Internet and IP networks have become mission critical business tools, there has been increased interest in techniques and methods to monitor the routing posture of networks. Incorrect routing or routing issues cause undesirable performance degradation, flapping or downtime. Monitoring routing in a network is achieved using route analytics tools and techniques.[15]

Centralized routing

[edit]

In networks where a logically centralized control is available over the forwarding state, for example, using software-defined networking, routing techniques can be used that aim to optimize global and network-wide performance metrics. This has been used by large internet companies that operate many data centers in different geographical locations attached using private optical links, examples of which include Microsoft's Global WAN,[16] Facebook's Express Backbone,[17] and Google's B4.[18]

Global performance metrics to optimize include maximizing network utilization, minimizing traffic flow completion times, maximizing the traffic delivered prior to specific deadlines and reducing the completion times of flows.[19] Work on the later over private WAN discusses modeling routing as a graph optimization problem by pushing all the queuing to the end-points. The authors also propose a heuristic to solve the problem efficiently while sacrificing negligible performance.[20]

See also

[edit]

References

[edit]

Further reading

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Routing

View on Grokipedia
from Grokipedia
Routing is the process of selecting and defining paths for IP-packet traffic within or between computer , enabling efficient data transmission from source to destination while managing overall network traffic. This function is primarily carried out by specialized devices known as routers, which examine packet headers containing destination addresses and use routing tables to determine the optimal forwarding path based on , congestion, and policy considerations. In essence, routing underpins the connectivity of the and enterprise by breaking down data into packets and reassembling them at the endpoint, distinct from switching which handles intra-network traffic. The origins of routing trace back to the development of packet-switched networks in the 1960s, with foundational theoretical work on independently developed by figures such as , , and ; Kleinrock's 1961 publication on demonstrated the feasibility of breaking messages into packets for independent routing. This concept was practically implemented in the , the precursor to the modern , where early routers—initially called Interface Message Processors—facilitated dynamic path selection to ensure reliable communication amid potential link failures. By the 1980s, innovations like the multiprotocol router invented at in 1980 laid the groundwork for commercial products, inspiring the founding of Systems and the widespread adoption of IP-based routing. Key concepts in routing include addressing and forwarding, where IP addresses identify endpoints, and routers perform distributed computations to build and maintain routing tables using algorithms such as distance-vector or link-state methods. Routing protocols automate this process: interior protocols like (Routing Information Protocol), which uses hop count for path selection; (Open Shortest Path First), employing link-state advertisements for faster convergence in large networks; and (Enhanced Interior Gateway Routing Protocol), a Cisco-proprietary hybrid offering rapid updates. For inter-domain routing, (Border Gateway Protocol) manages traffic between autonomous systems, prioritizing policy over mere distance to handle the Internet's scale. In modern networks, routing is crucial for scalability, security, and performance, as it enables traffic engineering to avoid congestion, supports (SDN) for programmable paths, and integrates with for expanded addressing. Without effective routing, devices could not communicate across disparate networks, hindering applications from web browsing to ; advancements continue to address challenges like mobility and high-speed data centers.

Fundamentals of Routing

Definition and Purpose

Routing is the process of selecting paths for traffic in a packet-switched network or across multiple to direct data packets from a source to a destination. In packet-switched networks, data is divided into small units called packets, each containing addressing information that enables intermediate nodes—such as routers—to forward them along determined paths toward the intended recipient. This mechanism ensures efficient and reliable data transmission in complex, interconnected systems where direct connections between all nodes are impractical. The origins of routing trace back to the 1960s with the development of the , a pioneering project funded by the U.S. Department of Defense's Advanced Research Projects Agency (ARPA). introduced as a foundational technology, allowing multiple users to share network resources dynamically. A key milestone occurred on October 29, 1969, when the first host-to-host transmission was successfully routed between a computer at the (UCLA) and one at the Stanford Research Institute, marking the initial demonstration of inter-host routing over the nascent network. This event laid the groundwork for modern internetworking by proving the feasibility of routing packets across geographically dispersed nodes using specialized hardware known as Interface Message Processors (IMPs), the precursors to contemporary routers. At its core, routing involves several basic components that distinguish it from simpler switching mechanisms. Routers are dedicated network devices that examine packet headers and use —data structures populated by routing protocols or manual configuration—to determine the next hop for each packet. The forwarding process occurs in the router's data plane, where packets are rapidly directed based on the (FIB) derived from the routing table, enabling high-speed transmission without recomputing paths for every packet. Unlike , which establishes fixed paths for entire sessions, routing in packet-switched environments dynamically adapts to network changes, ensuring resilience and . Routing can be categorized into static and dynamic types, as well as interior (intra-domain) and exterior (inter-domain). involves manually configured fixed paths, suitable for small, stable networks where changes are infrequent. In contrast, employs protocols that automatically exchange information among routers to compute and update paths in response to changes. Interior routing operates within a single autonomous (AS), such as an organization's internal network, using protocols optimized for local efficiency. Exterior routing, on the other hand, facilitates communication between different ASes, such as across the global , through protocols designed for inter-domain coordination.

Delivery Schemes

Delivery schemes in routing determine how packets are addressed and forwarded to recipients, ranging from individual hosts to groups or all nodes in a network. These schemes are fundamental to IP-based communication, enabling efficient transmission based on the number and nature of intended recipients. Routers implement these by examining packet headers and applying appropriate forwarding rules, such as those defined in the (IP). Unicast routing provides one-to-one delivery, where a packet is sent from a single source to a specific destination host by its unique 32-bit . This address consists of a network portion and a host portion, allowing routers to forward the across networks until it reaches the target host. Unicast is the default mode for most IP traffic, supporting reliable point-to-point communication in scenarios like web browsing or file transfers. Multicast routing enables one-to-many delivery, directing packets to a group of recipients sharing a common Class D (ranging from 224.0.0.0 to 239.255.255.255). Routers forward datagrams only to networks containing group members, provided the time-to-live (TTL) field exceeds 1, thus avoiding unnecessary transmission. The (IGMP) manages group memberships by allowing hosts to report their interest to neighboring routers, facilitating efficient distribution for applications like video streaming. Broadcast routing supports one-to-all delivery within a or subnetted network, using special IP addresses like 255.255.255.255 for limited broadcasts or all-ones addresses for directed broadcasts to all hosts on a specific network. Routers employ flooding techniques, such as (RPF), to propagate packets across subnets: a gateway forwards the on all outgoing links except the incoming one, discarding duplicates to prevent loops. This scheme is commonly used in networks for discovery protocols like ARP. Anycast routing delivers packets from one source to the nearest member of a group of hosts sharing the same , selected based on routing metrics like distance or . Routers treat anycast addresses similarly to during forwarding, directing traffic to the topologically closest available node for and load distribution. A prominent example is the DNS root server system, where anycast addresses enable global load balancing by routing queries to the nearest server instance, enhancing availability and reducing latency.
SchemeDelivery TypeAddressing MechanismOverhead CharacteristicsScalability ConsiderationsTypical Use Cases
UnicastOne-to-oneUnique destination Low per packet; scales with traffic volumeHigh for point-to-point; limited by size,
MulticastOne-to-manyShared group (Class D)Reduced bandwidth vs. multiple unicasts; requires group managementEfficient for large groups; challenges in inter-domain routingVideo streaming, stock updates
BroadcastOne-to-allAll-ones (e.g., 255.255.255.255)High due to flooding; loop prevention neededLimited to local/subnet scope; poor for large networksNetwork discovery, ARP requests
AnycastOne-to-nearestShared among group membersSimilar to unicast; potential convergence issuesScalable for global services with default routing; supports millions of groups via cachingDNS resolution, content delivery networks

Topology Discovery and Distribution

Distance Vector Algorithms

Distance vector algorithms, also known as distance vector routing protocols, were developed in the early 1970s as part of the , the pioneering created by the U.S. Defense Advanced Research Projects Agency, to enable in early internetworks. These protocols operate on a distributed basis where each router maintains a table of distances (typically measured in hops or costs) to all known destinations and periodically shares its entire with directly connected neighbors. The core mechanism relies on the Bellman-Ford algorithm, which iteratively relaxes edges to compute shortest paths by propagating distance updates until convergence. In distance vector routing, a router updates its distance to a destination yy by selecting the minimum value among its neighbors, incorporating the cost to each neighbor plus that neighbor's reported distance to yy. This is formalized by the Bellman equation: dx(y)=min⁡v{c(x,v)+dv(y)}d_x(y) = \min_v \left\{ c(x,v) + d_v(y) \right\} where dx(y)d_x(y) is the distance from router xx to destination yy, vv ranges over xx's neighbors, and c(x,v)c(x,v) is the link cost between xx and vv. Updates occur asynchronously upon receiving a neighbor's table or periodically (e.g., every 30 seconds in some implementations), allowing routers to incrementally refine paths without global knowledge of the network topology. A prominent example is the Routing Information Protocol (RIP), first standardized in 1988, which uses hop count as its metric and defines infinity as 16 hops to limit table sizes and prevent indefinite loops. In RIP, routers broadcast their tables to all interfaces every 30 seconds, with entries aging out after 180 seconds of inactivity to trigger updates. Distance vector algorithms offer advantages in simplicity of implementation, requiring only basic table exchanges and minimal processing per update, which results in low computational overhead suitable for resource-constrained devices. However, they suffer from slow convergence times, especially in large networks where changes propagate step-by-step, and are prone to routing loops due to the count-to-infinity problem, where two or more routers incrementally increase distances to a failed destination in a feedback loop. To mitigate this, techniques like split horizon—where routes learned from a neighbor are not advertised back to that neighbor—and poison reverse—where invalid routes are explicitly advertised with infinite distance—are employed, significantly reducing loop formation without eliminating it entirely. Compared to link-state algorithms, distance vector protocols generally exhibit slower convergence to optimal paths after topology changes. Link-state algorithms enable routers to construct a complete of the network by exchanging link-state advertisements (LSAs), which describe the state of local including costs and neighbors. In this process, each router originates LSAs about its directly connected and floods them reliably to all other routers within the routing domain, ensuring synchronization through acknowledgments and retransmissions. This flooding mechanism propagates updates throughout the network, allowing every router to maintain an identical link-state database (LSDB) that represents the entire as a weighted graph, where nodes are routers and edges are with associated metrics such as bandwidth or delay. The approach originated from early implementations in the , where a link-state protocol known as Shortest Path First (SPF) was deployed between 1978 and 1979 to replace distance-vector routing and improve convergence. Once the LSDB is synchronized, each router independently computes the shortest paths to all destinations using , treating the topology as a and calculating a rooted at itself. The algorithm initializes distances from the source router to itself as zero and to all others as , then iteratively selects the unvisited node with the smallest tentative distance and relaxes edges to its neighbors. The key relaxation step updates the distance to a node vv via a neighbor uu as follows: d(v)=min⁡(d(v),d(u)+w(u,v))d(v) = \min(d(v), d(u) + w(u,v)) where d(v)d(v) is the shortest-path distance to vv, d(u)d(u) is the distance to uu, and w(u,v)w(u,v) is the weight of the edge from uu to vv. This process ensures optimal paths based on the chosen metric, with the resulting forwarding table derived from the tree's parent pointers. A prominent example is the (OSPF) protocol, first specified in RFC 1131 in 1989 as an open standard for IP networks. OSPF enhances by organizing the network into areas, where intra-area routing uses detailed information while inter-area routing relies on summarized LSAs from area border routers, reducing the LSDB size in peripheral areas. Neighbor discovery and maintenance occur via the Hello protocol, which sends periodic Hello packets to elect designated routers on multi-access networks and detect link failures through dead intervals. OSPF's design supports fast convergence by immediately flooding topology changes and recomputing paths, while avoiding loops through consistent LSDBs across routers. Link-state algorithms offer advantages such as rapid convergence times, often under a second for local changes due to targeted flooding and independent SPF computations, and inherent loop prevention from the global topology view. They also enable load balancing across equal-cost paths and support hierarchical scaling in protocols like OSPF. However, they require significant bandwidth for initial and periodic LSA floods, especially in large topologies, and impose high computational demands for running on the full LSDB, necessitating capable hardware. Additionally, memory usage grows with network size due to storing the complete LSDB.

Path-Vector Protocols

Path-vector protocols represent an evolution of distance-vector routing tailored for inter-domain environments, where routers exchange complete paths—sequences of autonomous system (AS) numbers—rather than mere distance metrics to destinations. This mechanism allows for explicit loop detection: upon receiving an advertisement, a router examines the AS-path attribute; if its own AS number appears within the path, the route is rejected to prevent cycles. Advertisements also include path attributes, such as origin, next-hop, and multi-exit discriminator, which provide additional context for route evaluation and policy application. A core feature of path-vector protocols is their support for , enabling administrators to enforce business, security, or performance preferences through attribute manipulation and selective advertisement or acceptance of paths. This flexibility accommodates the diverse incentives of independent ASes, such as preferring certain transit providers or avoiding geopolitical risks, without relying solely on shortest-path computations. The protocol's design prioritizes stability and control over optimality, making it suitable for large-scale, heterogeneous networks. The (BGP) exemplifies path-vector routing, initially defined in 1989 via RFC 1105 as an inter-AS protocol to replace earlier exterior gateway protocols. BGP advanced significantly with version 4 (BGP-4), specified in RFC 1771 (updated as RFC 4271 in 2006), which incorporated (CIDR) support through aggregated prefix advertisements, reducing table sizes and enabling efficient IPv4 address conservation. BGP operates in a path-vector manner by propagating AS-path prepended updates between external peers, while internal variants (iBGP) distribute routes within an AS using full-mesh or route reflector topologies. Path-vector protocols offer scalability for internet-scale operations, managing expansive topologies through hierarchical AS aggregation and attribute-driven filtering, which has sustained the global Internet's growth since the by interconnecting approximately 78,000 ASes. BGP routing tables, for instance, contain more than IPv4 prefixes as of November 2025, demonstrating resilience to exponential network expansion. Nonetheless, drawbacks include protracted convergence—often minutes to hours due to sequential path withdrawals and explorations—and susceptibility to disputes, where conflicting AS preferences can induce persistent oscillations or blackholing.

Hybrid and Optimized Protocols

Hybrid routing protocols integrate elements of both distance-vector and link-state approaches to mitigate the limitations of each, such as slow convergence in distance-vector protocols and high overhead in full link-state flooding, by employing partial updates that propagate only necessary changes rather than complete network maps or periodic broadcasts. This key concept enables more efficient information dissemination, allowing routers to maintain loop-free paths while reducing bandwidth and computational demands compared to traditional methods. A prominent example of a hybrid protocol is the (EIGRP), developed by Systems and introduced in 1993 as an evolution of the earlier (IGRP). EIGRP leverages the Diffusing Update Algorithm (DUAL) to compute shortest paths and ensure loop-free routing by selecting feasible successors—backup paths that meet a feasibility condition based on reported distances—thus enabling rapid convergence without full topology exchanges. As a , EIGRP has been influential in enterprise networks, supporting features like variable-length subnet masking and unequal-cost load balancing, which enhance in hierarchical topologies. For optimized variants tailored to constrained environments, the Optimized Link State Routing (OLSR) protocol represents a significant advancement, standardized in RFC 3626 in October 2003 specifically for mobile ad hoc networks (MANETs). OLSR optimizes classical link-state routing through multipoint relays (MPRs), where each node selects a minimal set of neighboring nodes to retransmit topology control messages, thereby minimizing flooding overhead by up to 50% in dense networks while preserving full topology knowledge at each node. This partial update mechanism, combined with hello messages for neighborhood detection, allows OLSR to balance fast convergence—typically within seconds of topology changes—with low resource utilization, making it particularly suitable for and mobile networks where bandwidth and energy are limited. These hybrid and optimized protocols offer advantages in convergence speed and over pure distance-vector or link-state methods, achieving sub-second updates in topologies while using significantly less control traffic— for instance, OLSR reduces message overhead by restricting broadcasts to MPRs, which is critical in dynamic scenarios. EIGRP's influence extends to modern routing designs, inspiring open implementations, whereas OLSR's has facilitated its adoption in MANET testbeds and IoT applications requiring robust, low-overhead routing.

Path Selection Mechanisms

Selection Algorithms and Metrics

In routing protocols, the path selection process involves evaluating available routes in the routing table and choosing the one with the lowest overall cost based on predefined metrics, ensuring efficient toward destinations. This decision is made independently by each router using information derived from topology distribution protocols, such as link-state advertisements. The selected path represents the optimal route under the protocol's criteria, with support for equal-cost multipath routing where multiple equivalent paths exist. Common metrics used to quantify path costs include hop count, which measures the number of routers traversed; bandwidth, reflecting available link capacity; delay, accounting for and queuing times; load, indicating current utilization; and reliability, assessing link stability based on rates. In protocols like the (), the metric simplifies to hop count, where each link adds 1 to the total, limiting paths to a maximum of 15 hops to prevent infinite loops. The (OSPF) protocol employs a composite metric centered on , which is configurable but commonly calculated as a function of bandwidth to prioritize higher-capacity links. Path selection algorithms typically compute the weighted shortest path, such as in link-state protocols like OSPF, where the total cost is the sum of individual link costs along candidate paths. In OSPF implementations, link cost is often derived from the formula cost=108interface bandwidth in bps\text{cost} = \frac{10^8}{\text{interface bandwidth in bps}}, yielding lower values for faster interfaces (e.g., a 100 Mbps link has a cost of 1). For tie-breaking when metrics are equal, routers use , a protocol-specific trustworthiness value; for instance, OSPF routes have an administrative distance of 110, preferred over RIP's 120, allowing more reliable protocols to override less trusted ones. In exterior protocols like (BGP), path selection diverges from pure distance metrics, relying instead on policy-driven attributes such as local preference (higher values preferred for exit path selection within an autonomous system), Multi-Exit Discriminator (MED, lower values favored for entry into a neighboring autonomous system), and AS_PATH length (shorter sequences preferred to minimize transit domains). These attributes enable fine-grained control, with the decision process sequentially evaluating them: highest local preference first, then shortest AS_PATH, followed by lowest MED when routes originate from the same neighboring autonomous system. This approach supports scalable inter-domain routing by balancing , , and loop prevention.

Routing Tables and Forwarding

Routing tables serve as critical data structures in network routers, storing information about available paths to destinations to enable efficient packet forwarding. These tables, often implemented as the Forwarding Information Base (FIB), contain entries derived from routing protocols or static configurations, optimized for rapid lookups rather than comprehensive route storage found in the Routing Information Base (RIB). Each FIB entry typically includes a destination prefix, which represents a network address range; the next-hop address, indicating the immediate downstream router or interface; a metric or cost, quantifying the path's preference based on factors like hop count or bandwidth; and the outgoing interface, specifying the physical or logical port for transmission. For example, in IPv4 networks, an entry might specify the prefix 192.168.1.0/24 with a next-hop of 10.0.0.2, a metric of 2, and interface eth0. The following table illustrates the core components of a typical routing table entry:
ComponentDescriptionExample (IPv4)
Destination PrefixThe network address range covered by the route, using CIDR notation.192.168.1.0/24
Next-HopThe IP address of the next router or directly connected host.10.0.0.2
Metric/CostA numerical value indicating path quality or distance, used for selection.2 (e.g., hop count)
InterfaceThe local port or virtual interface for forwarding the packet.eth0
This structure ensures that routers can quickly map incoming packet destinations to forwarding actions. Metrics are protocol-specific; for instance, uses hop count up to 15, while OSPF employs a composite cost based on link bandwidth. begins when a router receives an IP datagram, extracts the destination address, and performs a lookup in the FIB to determine the next hop. The process relies on the (LPM) algorithm, which selects the most specific entry by matching the longest common prefix between the destination address and table entries. For example, given destination 10.1.2.3 and entries for 10.1.0.0/16 and 10.1.2.0/24, LPM prefers the /24 route due to its greater specificity. If no match is found, the (0.0.0.0/0 for IPv4) is used as a catch-all, directing packets to a gateway of last resort; otherwise, an ICMP "destination unreachable" message is generated. To achieve efficient LPM lookups, especially with growing table sizes, routers employ trie (prefix tree) data structures, where each bit of the determines branching, allowing logarithmic-time searches. These structures compress internal nodes to minimize memory usage while supporting updates and queries at wire speed. The TTL field is decremented during forwarding, and if it reaches zero, the packet is dropped with an ICMP time exceeded message. Routing tables are dynamically updated by protocols such as RIP, OSPF, and BGP, which exchange information to install, modify, or remove entries based on changes. Dynamic entries include aging mechanisms to invalidate stale routes; for example, RIP uses a of 180 seconds, after which an entry enters a garbage collection phase of 120 seconds before removal if no refresh arrives. OSPF employs (LSA) aging with a maximum age of 3600 seconds to flush outdated information. These prevent routing loops and ensure convergence, though they introduce brief periods of inconsistency during updates. Static entries, by contrast, persist indefinitely unless manually altered. In high-performance routers, forwarding occurs at line rate—matching the input port speed without loss—via specialized hardware like Application-Specific Integrated Circuits (ASICs). These chips implement parallel lookup pipelines and trie traversals in silicon, handling millions of packets per second per port. For instance, modern ASICs support 400 Gbps forwarding with sub-microsecond latencies by offloading computations from general-purpose CPUs. This separation of control (RIB updates) and data planes (FIB forwarding) enhances scalability. IPv6 routing tables tend to be larger than IPv4 counterparts due to the convention of using /64 prefixes for subnets, which supports stateless address autoconfiguration (SLAAC) but results in more granular entries if aggregation is incomplete. While supports prefixes up to /128, forwarding engines must handle any length via LPM, with /64 as the for end-site links to ensure compatibility. The , ::/0, functions analogously to IPv4's 0.0.0.0/0 for unmatched destinations.

Advanced Routing Architectures

Multi-Agent and Distributed Routing

Multi-agent routing involves the coordination of multiple autonomous entities, or agents, each responsible for routing decisions within distinct network domains or protocols, enabling seamless integration in heterogeneous environments. A key aspect is the coexistence of multiple routing protocols, such as (OSPF) for internal gateway routing and (BGP) for external routing, where route redistribution allows routes learned in one protocol to be advertised into another to maintain end-to-end connectivity. This redistribution process, defined in interactions between BGP and OSPF, requires careful configuration to prevent loops, such as by using route tags or administrative distances, ensuring that internal routes are properly injected into external domains without causing instability. Distributed routing extends multi-agent concepts to decentralized environments like mobile ad-hoc networks (MANETs), where nodes make independent routing decisions without a central , adapting to dynamic topologies formed by links. In such networks, mobility poses significant challenges, including frequent link failures and topology changes that lead to route disruptions and increased overhead for route maintenance, necessitating protocols that predict or react to node movements to minimize . Proactive protocols like Destination-Sequenced Vector (DSDV) maintain routing tables continuously but suffer under high mobility, while reactive approaches like Ad-hoc On-Demand Vector (AODV) discover routes on demand, balancing responsiveness with resource constraints. A seminal example of multi-agent routing is , standardized in , which employs home agents on a mobile node's home network and s on visited networks to enable seamless mobility. The home agent intercepts packets destined for the mobile node and tunnels them to the foreign agent's care-of address, where the foreign agent detunnels and delivers them locally, while the mobile node registers its location to maintain binding information. This agent-based mechanism supports transparent routing across IP networks, allowing mobile nodes to change points of attachment without session disruption. Recent advancements, as of 2024, include hybrid SDMANET architectures that integrate SDN controllers with MANET protocols to improve routing and in mobile environments. These approaches offer advantages in resilience and for large, dynamic networks; distributed decisions eliminate single points of failure, enhancing as no central component can collapse the entire system, and agent coordination scales by localizing computations to avoid global synchronization overhead. In expansive ad-hoc deployments, such as disaster recovery scenarios, this supports thousands of nodes by leveraging route sharing, reducing latency compared to centralized alternatives. Since the 2010s, Software-Defined Networking (SDN) has introduced programmable software agents in distributed controllers to enhance routing flexibility, decoupling control logic from data planes for dynamic path optimization. Multiple SDN controllers act as agents, coordinating via east-west interfaces to manage routing across domains, improving scalability in hybrid environments by partitioning control responsibilities and enabling features like traffic engineering through global visibility. This evolution builds on earlier multi-agent ideas, providing resilience through controller replication while supporting programmable policies for adaptive routing.

Centralized Routing Systems

In centralized routing systems, a single authoritative entity, often referred to as a controller, gathers information from edge devices and computes optimal paths before distributing routing instructions back to those devices. This approach decouples the from the data plane, allowing the central controller to maintain a global view of the network state, including link statuses and traffic demands, to perform computations such as shortest-path or load-balanced routing algorithms. For instance, in (SDN) architectures, controllers like the Open Network Operating System (ONOS) collect topology data via southbound APIs (e.g., ) and push forwarding rules to switches, eliminating the need for distributed routing protocols within the fabric itself. Prominent examples of centralized routing include modern deployments, which emerged in the post-2010 era to manage wide-area networks across branch offices and cloud environments. In these systems, a centralized manager, such as Cisco's SD-WAN Controller, acts as a route reflector that aggregates routes from edge routers using the Overlay Management Protocol (OMP), applies policies, and redistributes them to enforce consistent path selection across the network. Historically, early packet-switched networks like the utilized Interface Message Processors (IMPs) designed by Bolt, Beranek and Newman (BBN), who maintained operational control and software updates. While BBN provided centralized management, the core routing was distributed, with IMPs dynamically computing paths using adaptive algorithms. Centralized routing offers advantages such as , where the controller can balance traffic across the entire network to minimize congestion and maximize throughput, often achieving near-100% link utilization in controlled environments. It also simplifies enforcement, enabling uniform application of rules, quality-of-service priorities, and service chaining from a single point, which reduces configuration complexity in large-scale deployments. However, these systems suffer from disadvantages including a , where controller can halt route updates and disrupt the network, and limitations, as the central entity must process data for thousands of devices, potentially leading to computational bottlenecks without distributed clustering. Since the 2000s, centralized routing has been widely adopted in data centers for traffic engineering, where controllers like those in Google's Jupiter networks use Clos topologies to compute multipath routes that adapt to dynamic workloads, scaling bisection bandwidth from tens of Gbps to over 1 Pbps across global sites. This contrasts sharply with distributed protocols like BGP, which rely on peer-to-peer exchanges and exhibit slower convergence times (often seconds to minutes) due to their decentralized nature, making them less suitable for the rapid failure recovery needed in data center environments.

Route Analytics and Monitoring

Route analytics and monitoring encompass the systematic , , and interpretation of routing behaviors in networks to ensure reliability, detect faults, and optimize performance. These practices involve collecting data on path selections, protocol operations, and traffic flows to identify deviations from expected norms, such as unexpected route changes or failures in convergence. Tools and techniques in this domain enable network operators to diagnose issues in real-time or retrospectively, drawing from standardized protocols and specialized software frameworks. A foundational method for route analytics is , which probes the path packets take across a network by incrementing the time-to-live (TTL) field in IP headers, eliciting ICMP time-exceeded responses from intermediate routers to map hop-by-hop routes. This technique, originally developed by in the late , reveals latency, , and details, aiding in connectivity problems and verifying path integrity. For (BGP) monitoring, projects like the University of Oregon's Route Views, established in the mid-1990s, provide real-time and historical BGP routing tables from multiple global vantage points, allowing operators to assess prefix visibility and AS-path dynamics across the . Similarly, the RIPE NCC's Service (RIS) collects BGP data to support global route analysis. Key concepts in route analytics include , which identifies disruptions like blackholing—where traffic is discarded without delivery due to erroneous route advertisements—and prefix hijacks, where an unauthorized AS announces ownership of a legitimate prefix, diverting traffic. These anomalies can stem from misconfigurations or malicious intent, potentially causing widespread outages; for instance, blackholing often results from null-routing invalid prefixes, while hijacks exploit BGP's trust model. Visualization tools such as BGPStream, an open-source framework developed by CAIDA, facilitate the analysis of live and historical BGP data through APIs and command-line interfaces, enabling operators to query updates, filter , and generate graphs of route changes for post-incident investigations. Critical metrics in route monitoring include convergence time, the duration for routing tables to stabilize after a topology change, which directly impacts network availability; studies show BGP convergence can take seconds to minutes depending on update and interactions. Path stability measures the frequency of route fluctuations, quantifying reliability through metrics like the number of AS-path changes over time, which helps evaluate protocol robustness against oscillations. Data collection for these metrics relies on formats like MRT (Multi-threaded Routing Toolkit), a binary standard for dumping BGP messages and tables, used by collectors such as Route Views and RIS to archive raw routing information for offline . The 2008 Pakistan YouTube hijack, where Pakistan Telecom erroneously announced YouTube's prefixes globally, blocking access for millions and exposing BGP vulnerabilities, significantly spurred advancements in route analytics by demonstrating the need for widespread monitoring; analyses from RIS and Route Views revealed how the incident propagated via more-specific prefixes, leading to enhanced efforts. Emerging techniques post-2020 incorporate for , such as graph attention networks to forecast BGP anomalies by modeling update patterns and AS relationships, improving detection accuracy over traditional threshold-based methods. These ML approaches, applied to historical MRT data, enable proactive identification of potential hijacks or instabilities, though challenges remain in handling the scale of routing events.

References

  1. https://www.cisco.com/site/us/en/learn/topics/networking/what-is-routing.html
  2. https://www.cisco.com/c/en/us/solutions/small-business/resource-center/networking/how-does-a-router-work.html
  3. https://erieit.edu/introductory-guide-routing-switching/
  4. https://www.livinginternet.com/i/iw_packet_inv.htm
  5. https://sites.cs.ucsb.edu/~almeroth/classes/F04.176A/handouts/history.html
  6. https://otl.stanford.edu/news/inside-invention-stanford-router-inspired-cisco
  7. https://ocw.mit.edu/courses/6-02-introduction-to-eecs-ii-digital-communication-systems-fall-2012/5f691ab218df35a3850df29a6b9a94b3_MIT6_02F12_chap17.pdf
  8. https://community.cisco.com/t5/networking-knowledge-base/dynamic-routing-protocols-ospf-eigrp-ripv2-is-is-bgp/ta-p/4511577
  9. https://www.cisco.com/c/en/us/td/docs/net_mgmt/prime/network/3-8/reference/guide/routpro.html
  10. https://ieeexplore.ieee.org/document/7968589/
  11. https://www.ietf.org/archive/id/draft-farrel-irtf-introduction-to-semantic-routing-02.html
  12. https://datatracker.ietf.org/doc/html/rfc1058
  13. https://dl.acm.org/doi/pdf/10.1145/75247.75273
  14. https://cacm.acm.org/research/breaking-loose/
  15. https://spectrum.ieee.org/todays-internet-still-relies-on-an-arpanetera-protocol-the-request-for-comments
  16. https://www.icann.org/en/blogs/details/the-first-message-transmission-29-10-2019-en
  17. https://datatracker.ietf.org/doc/rfc5772/
  18. https://datatracker.ietf.org/doc/rfc3222/
  19. https://datatracker.ietf.org/doc/html/rfc3746
  20. https://ieeexplore.ieee.org/document/7100406/
  21. https://datatracker.ietf.org/doc/html/rfc1583
  22. https://datatracker.ietf.org/doc/html/rfc791
  23. https://datatracker.ietf.org/doc/html/rfc1112
  24. https://datatracker.ietf.org/doc/html/rfc3376
  25. https://datatracker.ietf.org/doc/html/rfc922
  26. https://datatracker.ietf.org/doc/html/rfc4786
  27. https://www.linfo.org/distance_vector.html
  28. https://www.sciencedirect.com/topics/computer-science/bellman-ford-algorithm
  29. https://datatracker.ietf.org/doc/html/rfc2328#section-2
  30. https://datatracker.ietf.org/doc/html/rfc2328#section-12
  31. https://datatracker.ietf.org/doc/html/rfc2328#section-13
  32. https://annals-extras.org/anecdotes/writing/mcq-on-link-state-routing.pdf
  33. https://datatracker.ietf.org/doc/html/rfc2328#section-16
  34. https://www.cs.princeton.edu/~rs/AlgsDS07/01Fundamentals/04Analysis/03Dijkstra.pdf
  35. https://datatracker.ietf.org/doc/html/rfc2328#section-2.2
  36. https://www.rfc-editor.org/rfc/rfc1131.pdf
  37. https://datatracker.ietf.org/doc/html/rfc2328#section-3
  38. https://datatracker.ietf.org/doc/html/rfc2328#section-7.1
  39. https://datatracker.ietf.org/doc/html/rfc2328#section-4
  40. https://ocw.mit.edu/courses/6-02-introduction-to-eecs-ii-digital-communication-systems-fall-2012/f1f4ce0124f619c98c7329f4bf7d72ec_MIT6_02F12_lec23.pdf
  41. https://datatracker.ietf.org/doc/html/rfc2328#section-1.3
  42. https://datatracker.ietf.org/doc/html/rfc4271
  43. https://homes.cs.washington.edu/~arvind/cs425/doc/griffin99.pdf
  44. https://www.rfc-editor.org/rfc/rfc1105.html
  45. https://bgp.potaroo.net/as2.0/bgp-active.html
  46. https://www.kentik.com/kentipedia/bgp-routing/
  47. https://www.catonetworks.com/glossary/bgp/
  48. https://www.techtarget.com/searchnetworking/feature/BGP-tutorial-The-routing-protocol-that-makes-the-Internet-work
  49. https://datatracker.ietf.org/doc/rfc7868/
  50. https://www.cisco.com/c/en/us/support/docs/ip/enhanced-interior-gateway-routing-protocol-eigrp/13669-1.html
  51. https://www.cisco.com/c/en/us/support/docs/ip/enhanced-interior-gateway-routing-protocol-eigrp/16406-eigrp-toc.html
  52. https://datatracker.ietf.org/doc/html/rfc2328#section-16.8
  53. https://datatracker.ietf.org/doc/html/rfc2328#section-16.1
  54. https://www.cisco.com/c/en/us/support/docs/ip/border-gateway-protocol-bgp/15986-admin-distance.html
  55. https://datatracker.ietf.org/doc/html/rfc4271#section-9.1.2.2
  56. https://datatracker.ietf.org/doc/html/rfc4271#section-5.1.5
  57. https://datatracker.ietf.org/doc/html/rfc4271#section-9.1
  58. https://datatracker.ietf.org/doc/html/rfc3222
  59. https://datatracker.ietf.org/doc/html/rfc1812#section-5.2.4.3
  60. https://datatracker.ietf.org/doc/html/rfc1812#section-2.2.5.2
  61. https://datatracker.ietf.org/doc/html/rfc1812#section-5.2.1.2
  62. https://conferences.sigcomm.org/sigcomm/2003/papers/p201-dharmapurikar.pdf
  63. http://planete.inria.fr/dabbous/publis/ieee-cr01.pdf
  64. https://datatracker.ietf.org/doc/html/rfc1812#section-5.2.1
  65. https://dl.acm.org/doi/pdf/10.1109/TNET.2005.850216
  66. https://datatracker.ietf.org/doc/html/rfc7421
  67. https://datatracker.ietf.org/doc/html/rfc7608
  68. https://datatracker.ietf.org/doc/html/rfc4291
  69. https://datatracker.ietf.org/doc/html/rfc1403
  70. https://www.cisco.com/c/en/us/support/docs/ip/border-gateway-protocol-bgp/5242-bgp-ospf-redis.html
  71. https://ieeexplore.ieee.org/document/995157/
  72. https://www.semanticscholar.org/paper/Scalable-routing-protocols-for-mobile-ad-hoc-Hong-Xu/1d0178a71ccaa22f60395447af01b1bb3dcd596e
  73. https://www.rfc-editor.org/rfc/rfc2002.html
  74. https://ieeexplore.ieee.org/document/10467333/
  75. https://ieeexplore.ieee.org/document/5362356/
  76. https://www.researchgate.net/publication/262805723_Software-Defined_Networking_A_Comprehensive_Survey
  77. https://arxiv.org/pdf/1401.7651
  78. https://opennetworking.org/onos/
  79. https://www.cisco.com/c/en/us/td/docs/solutions/CVD/SDWAN/cisco-sdwan-design-guide.html
  80. https://apps.dtic.mil/sti/tr/pdf/ADA115440.pdf
  81. https://research.google.com/pubs/archive/43837.pdf
  82. https://www.geeksforgeeks.org/system-design/comparison-centralized-decentralized-and-distributed-systems/
  83. https://dl.acm.org/doi/10.1109/TNET.2023.3259541
Add your contribution
Related Hubs
User Avatar
No comments yet.