System and method for deadlock-free routing on arbitrary network topologies
US6992988B2 · kind B2 · utility
5Cited by
5References
51Claims
0Family size
Assignee
Inventors
Key dates
| Filing date | Aug 20, 2001 |
| Grant date | Jan 31, 2006 |
| Priority date | — |
| Expiry date | Dec 28, 2023 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L45/18
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
A system and method for calculating a deadlock-free free set of paths in a network generates an ordered set of deadlock-free sub-topologies, referred to as “layers.” The ordered set of layers is then used to determine a deadlock-free set of paths through the network by performing a shortest-path route calculation with the following constraint: starting at any given layer, for each node, proceed to calculate a shortest path to every other node in the graph where, at any node being utilized to assess a given minimum path, the path may move to any higher-ordered layer, but may not return to a lower-ordered layer.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.