ABSTRACT
Routing is the blue-collar work of integrated circuit design. There are no conceptual difficulties and very little use of higher mathematics. Almost every problem associated with routing is known to be intractable. The simplest routing problem, finding the shortest route for one net in one layer with no obstacles and no design rules, is called the Steiner tree problem. In addition to correctly connecting the nets, routers may also be expected to make sure the design meets timing, has no crosstalk problems, and meets any metal density requirements. This long list of often conflicting objectives is what makes routing difficult. A switchbox router also routes in a rectangular region. However, instead of pins on the top and bottom only, pins may be on all sides of the routing area. Any routing that must be completed in a single layer will require a specialized algorithm, since routes cannot cross.
