Routing

Routing is the essential process of selecting a path for data traffic within a network or across multiple networks. In packet switching networks, routing acts as a high-level decision-making mechanism. It directs network packets from their original source toward a specific destination. This process happens through intermediate network nodes. These nodes are typically hardware devices such as routers, gateways, firewalls, or switches. General-purpose computers can also perform routing, though they lack specially optimized hardware. Routing is critical for the functionality of the Internet and the public switched telephone network (PSTN).

To make these decisions, devices rely on routing tables. A routing table is a record that maintains routes to various network destinations. These tables can be created manually by a network administrator. They can also be learned by observing network traffic or built using routing protocols. In a narrow sense, routing often refers specifically to IP routing. IP routing assumes that network addresses are structured. This means that similar addresses imply proximity within the network. Structured addressing allows one table entry to represent a group of devices. This method outperforms unstructured addressing, known as bridging, in large networks.

Networks use different methods to distribute their topology. Static routing involves manually configuring routing tables. This is useful for small networks but is unfeasible for large, complex topologies that change rapidly. In contrast, dynamic routing constructs routing tables automatically. This is done using information carried by routing protocols. Dynamic routing allows a network to act nearly autonomously to avoid failures or blockages. It is the dominant form of routing on the Internet. Common examples of dynamic-routing protocols include the Routing Information Protocol (RIP), Open Shortest Path First (OSPF), and the Enhanced Interior Gateway Routing Protocol (EIGRP).

There are several distinct algorithms used to determine paths. Distance vector algorithms use the Bellman–Ford algorithm to assign a cost to each link between nodes. Nodes attempt to send data via the path with the lowest total cost. When a node starts, it only knows its immediate neighbors and the direct cost to reach them. Each node regularly sends its assessment of total costs to its neighbors. Neighbors compare this to their own data and update their tables with any improvements. If a node fails, adjacent nodes discard the entry and spread updated information to find new paths.

Link-state algorithms function differently by using a graphical map of the network. Each node floods the network with information about its connections to create this map. Once a node assembles the map, it independently determines the least-cost path using a shortest paths algorithm, such as Dijkstra's algorithm. This creates a tree graph rooted at the current node. The tree specifies the best next hop for any destination. For mobile ad hoc networks, an optimized version called the Optimized Link State Routing (OLSR) protocol is used. OLSR is proactive and uses Hello and Topology Control messages to discover neighbors.

While distance vector and link-state protocols work within a single autonomous system, they cannot manage inter-domain routing. Large networks require path-vector routing to communicate between different autonomous systems. In this system, a designated speaker node acts on behalf of its entire system. The speaker node advertises a routing table to neighboring speaker nodes in other systems. Instead of just sharing a metric, path-vector routing advertises the entire path description. This path is recorded as a special attribute that shows the sequence of routing domains traversed. This prevents the instability and heavy traffic loads seen in other methods.

Path selection is the final step where a routing metric is applied to multiple routes. A metric is a value used to predict the best route based on factors like bandwidth, delay, hop count, or reliability. Most algorithms use only one path at a time, but multipath routing allows for the use of multiple alternative paths. When routes overlap, routers use a specific priority order to choose. They first look at the prefix length to find the most exact destination. They then look at the metric, where a lower value is preferred. Finally, they consider administrative distance, which indicates how reliable a routing source is.

Routing technology has evolved significantly to handle increasing speeds and complexity. Early high-speed systems used circuit switching to set up a path once for a series of packets. Modern high-speed systems often use next-hop routing, where no single device calculates the entire path. This is necessary because the sheer number of connections makes full calculation impossible. Some systems even use a randomized algorithm called Valiant's paradigm to avoid congestion. This routes packets to a random intermediate destination before sending them to the true target. By choosing different metrics, such as minimum latency for web requests, routing ensures the digital world remains efficient.