Hierarchical topological network designing system and method
US7010471B2 · kind B2 · utility
Assignee
Inventor
Key dates
| Filing date | Jan 17, 2003 |
| Grant date | Mar 7, 2006 |
| Priority date | — |
| Expiry date | Apr 2, 2024 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F2113/16
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.