We present a hierarchical solution method to approximately solve the topological network design problem: given positive integers (n,d,/spl Delta/), minimize the number of arcs required to interconnect n nodes, so that the network diameter does not exceed d, the maximum node degree does not exceed /spl Delta/, and the network is single node survivable. The method uses dynamic programming to piece together small networks to create larger networks. The method was used to plan two high-speed packet networks at AT&T.

In this router, an iterative, non-sequential “supply/demand” router attempts to find conflict-free (non-crossing or overlapping) paths for each net. If 100% interconnection is not achieved with supply/demand routing, the rip-up procedure removes enough nets to eliminate all conflicts. Nets that are ripped-up are returned to the supply/demand router for re-routing. The new router was compared to a Lee-type router on six double-sided boards, and on average obtained 6.8% higher completion.