What Is Routing?

Routing is the process of selecting a path through a network along which data, signals, or traffic are directed from a source to one or more destinations. In computer networking, routing operates at the network layer of the OSI model and determines which nodes a packet traverses between sender and receiver. In very large-scale integration (VLSI) chip design, routing is the phase that draws the physical wire connections between placed logic cells. In both domains, the core problem is the same: given a topology and a set of cost or constraint criteria, find one or more paths that optimize the objective while satisfying capacity, latency, or physical layout constraints.

Routing draws on graph theory, combinatorial optimization, and distributed algorithm design. In networking, the seminal algorithms are shortest-path methods such as Dijkstra's algorithm and the Bellman-Ford algorithm, which underpin most deployed routing protocols. In VLSI design, routing follows placement and involves packing interconnect wires into a finite number of metal layers while minimizing wire length and avoiding violations of design rules.

Unicast Routing Algorithms

Unicast routing delivers a packet from a single source to a single destination. Interior gateway protocols operating within an autonomous system typically use link-state or distance-vector approaches. Link-state protocols such as OSPF (Open Shortest Path First) flood topology information so that each router builds a complete map of the network, then runs Dijkstra's shortest-path algorithm locally to compute forwarding tables. Distance-vector protocols such as RIP (Routing Information Protocol) exchange reachability information only with neighboring routers, converging more slowly but requiring less memory and computation.

Border Gateway Protocol (BGP), the inter-domain routing protocol that glues together the autonomous systems forming the global Internet, is a path-vector protocol. It exchanges not just distance but the full AS-path to each destination, enabling policy-based routing decisions. The IETF RFC 4271 defines the BGP-4 specification that governs peering across Internet exchange points worldwide. Adaptive routing responds to changing congestion conditions by dynamically adjusting paths, a capability covered in depth by IETF datatracker BGP-4 RFC 4271 and its related extension RFCs.

Multicast Routing

Multicast routing delivers a single data stream to multiple receivers simultaneously, building a distribution tree rather than duplicating the packet along separate unicast paths. This is essential for video conferencing, live streaming, and group communication protocols where fan-out to many receivers must be efficient.

Two broad tree structures exist: shortest-path trees, where each receiver gets the minimum-cost path from the source, and shared trees, where all group members share a single tree rooted at a designated rendezvous point. Protocol Independent Multicast (PIM) supports both modes and is the dominant multicast routing protocol in IP networks. Finding the optimal multicast tree that minimizes total wire or link cost is the Steiner tree problem, which is NP-complete; practical routing protocols use polynomial-time heuristics. Research published on IEEE Xplore on multicast routing algorithms for high-speed networks examines the performance trade-offs among Steiner tree heuristics, shortest-path trees, and center-based trees under delay constraints.

VLSI Routing

In integrated circuit design, routing converts a netlist of logical connections, produced after placement assigns logic cells to physical coordinates, into actual metal wire geometries on the chip. Routing proceeds in two stages: global routing assigns nets to coarse routing channels, and detailed routing assigns specific tracks and vias within those channels while obeying design rule constraints.

Modern sub-5 nm process nodes operate with seven or more metal layers and extremely tight spacing rules, making detailed routing an integer programming problem of enormous scale. Specialized routers use maze-routing algorithms (Lee's algorithm) and negotiation-based approaches (Rip-up and Reroute) to resolve congestion. The quality of placement directly constrains routing wirelength and routability; dense clusters of cells increase local congestion and can make detailed routing infeasible. The performance analysis of multicast routing algorithms paper on IEEE Xplore and work on distributed multicast routing for point-to-point networks on IEEE Xplore illustrate the algorithmic breadth spanning both network and circuit routing contexts.

Applications

Routing has applications across a wide range of networking, communication, and electronic design fields, including:

• Internet infrastructure: packet forwarding across ISP networks and Internet exchange points
• Data center fabric design: low-latency, load-balanced routing between servers
• Wireless and mobile networks: dynamic route adaptation for moving nodes
• Integrated circuit physical design: interconnect routing in CPU, GPU, and ASIC tape-outs
• Optical networking: wavelength-path assignment in wavelength-division multiplexed systems