Directed acyclic graph computation by orienting shortest path links and alternate path links obtained from shortest path computation
US7656857B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Oct 18, 2005 |
| Grant date | Feb 2, 2010 |
| Priority date | — |
| Expiry date | Jun 21, 2027 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L45/12
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
Each network node in a network is configured for calculating a directed acyclic graph that provides at least one path from all the other network nodes toward the one network node. The network node performs a modified shortest path first calculation by identifying next-hop nodes adjacent to the network node, and orienting the link of each next-hop node toward itself (i.e., the origin). The network node also identifies secondary adjacent nodes, adjacent to each of the next hop nodes, and extends paths from next-hop nodes to the associated secondary adjacent nodes while orienting each of the links of the path between adjacent nodes and next-hop nodes toward the next hop nodes. The paths of the nodes form a directed acyclic graph from any other network node toward the origin, enabling distribution of the directed acyclic graph to the other network nodes for optimized reachability to the network node.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.