Hierarchical topological network designing system and method

Abstract

The present invention provides a method called, the “cluster method”, for designing an efficient and low cost network that satisfies certain requirements, and in particular, that satisfies the requirement of having a prescribed number of nodes. The method first computes a provably optimal (or near optimal, in some cases) solution to small network design problems with the three following constraints. First, the network must be immune to the failure of a single link. Second, the network diameter cannot exceed a prescribed value. Third, the maximum node degree cannot exceed a prescribed value. The solutions to the small problems are combined, using an optimization technique called “dynamic programming,” to design large networks subject to the three above constraints. This cluster method is a hierarchical method, since the solutions to small problems are combined to solve a large problem. The resulting large network design meets the given survivability, diameter and maximum node degree constraints.

Dependencies are inferred from the claim text.