A floating via router based on a saturated zone strategy

This letter describes a new routing algorithm which is oriented towards floating via technology in a two-sided environment. The algorithm builds up "saturated zones" of interconnections and then combines these saturated zones by four tactics which attempt to complete a maximum number of paths selected from a restricted set of path shapes. A router based on this algorithm has been implemented, and has averaged 99.4 percent completion on 24 Illiac IV boards, and attained 100 percent completion on a large printed wiring board. The router averages about one via per wire, uses modest storage, and is generally economical.