Patent ID: 7069530

Claim:
A method of routing a net by identifying a set of paths between a set of source routable elements of a net and a set of target routable elements of the net, wherein the set of paths has to have a minimum acceptable number of paths, the method comprising: a) identifying a set of an acceptable number of at least two paths between the set of source routable elements and the set of target routable elements, said identifying comprising: 1) specifying a first total cost; 2) performing a first depth-first search to identify the set of at least two paths that each have a cost that does not exceed the first total cost, wherein each path in the set includes a set of expansions from the set of routable-element sources to the set of routable-element targets; 3) if the search cannot find the acceptable number of paths, incrementing the total cost and performing a second depth-first search to identify the set of paths that each have a cost that does not exceed the incremented total cost, wherein the acceptable number of paths is at least two paths; and b) when the acceptable number of paths is identified, using one of the paths to define a route for the net.