Very-large-scale integration (VLSI) combines thousands of transistor-based systems on a single chip. This paper is a concise and elegant repository of the current state of the art of VLSI global routing. The paper provides background information on the formulation of the VLSI global routing problem. The chosen model is based on a grid graph, whose vertices correspond to the grid cells, where the edges represent the adjacencies between these cells. Three different metrics of routing solutions are introduced: overflow, which is the excess of demand over the edge capacities; total wirelength; and the runtime for a routing solution.

An overview of some of the basic algorithmic paradigms for routing is presented. These include maze routing, pattern routing, monotonic routing, divide-and-conquer strategies, ripup-and-reroute, integer linear programming (ILP) based routing, multi-commodity-based techniques, and paradigms using probability-based congestion prediction. The paper introduces the well-known global routing benchmarks used to evaluate the qualities of different academic routers. These include the ISPD 1998, ISPD 2005, and ISPD 2007 benchmarks.

Some modern routers are summarized, including Labyrinth, BoxRouter, FastRoute, Archer, Fairly Good Router (FGR), MaizeRouter, open-source, and the National Tsing Hua University (NTHU) routing tool. The paper nicely summarizes the basic paradigms on which these algorithms are based.

Some of the basic algorithmic themes shared by many of the well-known academic routers are next discussed, in a fairly detailed manner. Some of these are the single-net tree-topology generation scheme, which is primarily based on Steiner tree construction; the sharing of routing resources; the use of history-based cost functions; and incremental tree restructuring, as used in FGR, Archer, BoxRouter, and MaizeRouter. Schemes for resource recovery and layer assignment for multi-layer routing are also discussed. The paper points out the lack of sufficient work in the area of appropriate internal routing representation. Finally, the paper emphasizes the simplicity of the routing algorithms, which is considered to be the key to most successful routing algorithms.

The paper concludes, interestingly, with certain predictions about research challenges, in terms of more complex benchmarks, the evolution of new algorithms, the emergence of open-source tools, the occurrence of more routing contests in the future, and open problems in new directions.